You are currently browsing the monthly archive for November 2022.

Rachel Greenfeld and I have just uploaded to the arXiv our paper “A counterexample to the periodic tiling conjecture“. This is the full version of the result I announced on this blog a few months ago, in which we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. The paper took a little longer than expected to finish, due to a technical issue that we did not realize at the time of the announcement that required a workaround.

In more detail: the original strategy, as described in the announcement, was to build a “tiling language” that was capable of encoding a certain “ ${p}$-adic Sudoku puzzle”, and then show that the latter type of puzzle had only non-periodic solutions if ${p}$ was a sufficiently large prime. As it turns out, the second half of this strategy worked out, but there was an issue in the first part: our tiling language was able (using ${2}$-group-valued functions) to encode arbitrary boolean relationships between boolean functions, and was also able (using ${{\bf Z}/p{\bf Z}}$-valued functions) to encode “clock” functions such as ${n \mapsto n \hbox{ mod } p}$ that were part of our ${p}$-adic Sudoku puzzle, but we were not able to make these two types of functions “talk” to each other in the way that was needed to encode the ${p}$-adic Sudoku puzzle (the basic problem being that if ${H}$ is a finite abelian ${2}$-group then there are no non-trivial subgroups of ${H \times {\bf Z}/p{\bf Z}}$ that are not contained in ${H}$ or trivial in the ${{\bf Z}/p{\bf Z}}$ direction). As a consequence, we had to replace our “ ${p}$-adic Sudoku puzzle” by a “ ${2}$-adic Sudoku puzzle” which basically amounts to replacing the prime ${p}$ by a sufficiently large power of ${2}$ (we believe ${2^{10}}$ will suffice). This solved the encoding issue, but the analysis of the ${2}$-adic Sudoku puzzles was a little bit more complicated than the ${p}$-adic case, for the following reason. The following is a nice exercise in analysis:

Theorem 1 (Linearity in three directions implies full linearity) Let ${F: {\bf R}^2 \rightarrow {\bf R}}$ be a smooth function which is affine-linear on every horizontal line, diagonal (line of slope ${1}$), and anti-diagonal (line of slope ${-1}$). In other words, for any ${c \in {\bf R}}$, the functions ${x \mapsto F(x,c)}$, ${x \mapsto F(x,c+x)}$, and ${x \mapsto F(x,c-x)}$ are each affine functions on ${{\bf R}}$. Then ${F}$ is an affine function on ${{\bf R}^2}$.

Indeed, the property of being affine in three directions shows that the quadratic form associated to the Hessian ${\nabla^2 F(x,y)}$ at any given point vanishes at ${(1,0)}$, ${(1,1)}$, and ${(1,-1)}$, and thus must vanish everywhere. In fact the smoothness hypothesis is not necessary; we leave this as an exercise to the interested reader. The same statement turns out to be true if one replaces ${{\bf R}}$ with the cyclic group ${{\bf Z}/p{\bf Z}}$ as long as ${p}$ is odd; this is the key for us to showing that our ${p}$-adic Sudoku puzzles have an (approximate) two-dimensional affine structure, which on further analysis can then be used to show that it is in fact non-periodic. However, it turns out that the corresponding claim for cyclic groups ${{\bf Z}/q{\bf Z}}$ can fail when ${q}$ is a sufficiently large power of ${2}$! In fact the general form of functions ${F: ({\bf Z}/q{\bf Z})^2 \rightarrow {\bf Z}/q{\bf Z}}$ that are affine on every horizontal line, diagonal, and anti-diagonal takes the form $\displaystyle F(x,y) = Ax + By + C + D \frac{q}{4} y(x-y)$

for some integer coefficients ${A,B,C,D}$. This additional “pseudo-affine” term ${D \frac{q}{4} y(x-y)}$ causes some additional technical complications but ultimately turns out to be manageable.

During the writing process we also discovered that the encoding part of the proof becomes more modular and conceptual once one introduces two new definitions, that of an “expressible property” and a “weakly expressible property”. These concepts are somewhat analogous to that of ${\Pi^0_0}$ sentences and ${\Sigma^0_1}$ sentences in the arithmetic hierarchy, or to algebraic sets and semi-algebraic sets in real algebraic geometry. Roughly speaking, an expressible property is a property of a tuple of functions ${f_w: G \rightarrow H_w}$, ${w \in {\mathcal W}}$ from an abelian group ${G}$ to finite abelian groups ${H_w}$, such that the property can be expressed in terms of one or more tiling equations on the graph $\displaystyle A := \{ (x, (f_w(x))_{w \in {\mathcal W}} \subset G \times \prod_{w \in {\mathcal W}} H_w.$

For instance, the property that two functions ${f,g: {\bf Z} \rightarrow H}$ differ by a constant can be expressed in terms of the tiling equation $\displaystyle A \oplus (\{0\} \times H^2) = {\bf Z} \times H^2$

(the vertical line test), as well as $\displaystyle A \oplus (\{0\} \times \Delta \cup \{1\} \times (H^2 \backslash \Delta)) = G \times H^2,$

where ${\Delta = \{ (h,h): h \in H \}}$ is the diagonal subgroup of ${H^2}$. A weakly expressible property ${P}$ is an existential quantification of some expressible property ${P^*}$, so that a tuple of functions ${(f_w)_{w \in W}}$ obeys the property ${P}$ if and only if there exists an extension of this tuple by some additional functions that obey the property ${P^*}$. It turns out that weakly expressible properties are closed under a number of useful operations, and allow us to easily construct quite complicated weakly expressible properties out of a “library” of simple weakly expressible properties, much as a complex computer program can be constructed out of simple library routines. In particular we will be able to “program” our Sudoku puzzle as a weakly expressible property.

It’s been a while since I’ve actively participated in social media outside of this blog – I was active in Google Buzz/Google+ for a while, until that service closed – but I’ve decided to try out Mathstodon, one of the servers of the open source social media software platform Mastodon. As I understand it, Mastodon functions in many ways similar to the significantly more well-known platform Twitter, but is decentralized into a federation of servers that share content with each other but can have their own moderation rules and add-ons. For instance, the Mathstodon server has the additional feature of supporting LaTeX in its posts. Another consequence of this decentralization is that if one for some reason ends up disagreeing with the administration of the server one is in, one has the option of transferring one’s account to a different server while staying on the same platform.

I just created an account at Mathstodon and it currently has very little content, but I hope to add some soon (though I will probably not be as prolific as some other mathematicians already on that site, such as John Baez or Nalini Joshi).

In 2010, the UCLA mathematics department launched a scholarship opportunity for entering freshman students with exceptional background and promise in mathematics. This program was unfortunately suspended for a while due to technical reasons, but we are once again able to offer one scholarship each year.  The UCLA Math Undergraduate Merit Scholarship provides for full tuition, and a room and board allowance for 4 years, contingent on continued high academic performance. In addition, scholarship recipients follow an individualized accelerated program of study, as determined after consultation with UCLA faculty.   The program of study leads to a Masters degree in Mathematics in four years.

More information and an application form for the scholarship can be found on the web at: Anonymous on Hilbert’s seventh proble… Sam on 245A, Notes 5: Differentiation… Webmaster on Mathematics for Humanity initi… Yingyuan Li on Analysis I Terence Tao makes de… on The Collatz conjecture, Little… TK on Heath-Brown’s theorem on… TK on Heath-Brown’s theorem on… TK on Heath-Brown’s theorem on… TK on Heath-Brown’s theorem on… Anonymous on A Host–Kra F^omega_2-sys… Anonymous on A Host–Kra F^omega_2-sys… alex on Would it be possible to create… Yingyuan Li on Analysis I alonsoquixano on Would it be possible to create… Yingyuan Li on Analysis I