The structure of translational tilings in $\mathbb{Z}^d$

Abstract

The structure of translational tilings in $\mathbb{Z}^d$, Discrete Analysis 2021:16, 28 pp. A significant theme in harmonic analysis, already represented by three previous papers in this journal, is that of tiling. In general, a tiling of a group $G$ by a function $f$ is a collection of translates of $f$ that add up to a constant function, and there are many interesting questions about their existence and properties. An important special case, which explains the word "tiling", is when $f$ is the characteristic function of a finite set $A$ and the constant function takes the value 1 everywhere -- this is a partition of $G$ into translates of $A$. (In the non-Abelian case one specifies whether one is taking left translates or right translates.) This paper concerns tilings of $\mathbb Z^d$, and in particular $\mathbb Z^2$, by characteristic functions of finite sets, but as well as the special case just discussed, they also look at _level-$k$_ tilings, which are tilings for which the constant function takes the value $k$, or in other words every point is covered exactly $k$ times by the translates of the set in question. The paper is partly motivated by a conjecture of Jeffrey Lagarias and Yang Wang from 1996. Among other results, they showed that every tiling of $\mathbb R$ of any level $k$ is periodic. The corresponding statement for $\mathbb Z$, which was proved by Donald Newman in 1977 and is broadly similar but simpler, can be seen as follows. Note first that if an interval $r,r+1,\dots,s$ of length greater than the diameter of $A$ can be covered $k$ times by translates of $A$, then any extension of that covering to a level-$k$ tiling of $\mathbb Z$ must be unique: at each stage the smallest not fully covered integer bigger than $s$ must be covered by the smallest element of a translate of $A$ and the largest not fully covered integer smaller than $r$ must be covered by the largest element of a translate of $A$. But by the pigeonhole principle there must be two such intervals that are covered in exactly the same way, and from that the periodicity follows. A higher-dimensional tiling $A$ is said to be periodic if the set of translates used is a lattice $\Lambda$ (that is, a subgroup of $\mathbb Z^d$ of finite index). Easy examples show that higher-dimensional tilings do not have to be periodic: for instance one can cover $\mathbb Z^2$ by translates of $\{0,1,\dots,n-1\}^2$ in the obvious way and then shift each "column of squares" vertically by an arbitrary amount. However, for this example one sees that even though there exists a non-periodic tiling by $A$, there also exists a periodic tiling. Lagarias and Wang conjectured that this is always the case: that is, if there is a tiling of $\mathbb R^d$ by translates of a finite set $A$, then there must also be a periodic tiling by translates of $A$. Even for $\mathbb Z^d$ this is open. It has recently been proved when $d=2$, but the argument, due to Bhattacharya, used ergodic theory methods (as well as a number-theoretic argument) and gave no bound for the period in terms of the tile. One of the main results of this paper is to give a different and more elementary proof of Bhattacharya's result, as a consequence of which they show that the period is $\text{diam}(A)^{O(|A|^4)}$. In particular, for a given cardinality $|A|$ there is a polynomial dependence on the diameter. This in turn implies that there is an algorithm that determines whether a set $A$ tiles $\mathbb Z^2$ in time roughly exponential in the upper bound just given. Bhattacharya's result showed (via standard arguments) that this problem was decidable -- which was one of the motivations for the conjecture of Lagarias and Wang -- but gave no bound for its computational complexity. The example given above of a non-periodic tiling of $\mathbb Z^2$ mentioned earlier did at least have _some_ periodicity, since it was invariant under translates by $(0,n)$. A tiling of $\mathbb Z^2$ is said to be _weakly periodic_ if the tiles can be partitioned into finitely many sets, each of which is invariant under a one-dimensional group of translations. (There are slightly more complicated examples, including one given in Section 1.3 of the paper, that demonstrate that this partitioning is needed.) Another of the main results of the paper is that every level-1 tiling of $\mathbb Z^2$ by a finite set $A$ is weakly periodic, but that there exists a level-4 tiling by an 8-element set $A$ that is not weakly periodic. Although this paper has been placed into the harmonic analysis section of the journal, the proof methods are elementary. The results are very appealing and the paper introduces important new ideas into the area. The authors have also followed it up with further work. For example, in [this paper](https://arxiv.org/abs/2108.07902) they find a finite Abelian group $G_0$ and two finite subsets of $\mathbb Z^2\times G_0$ such that it is undecidable whether the two subsets tile $\mathbb Z^2\times G_0$. The following talk by one of the authors gives a nice introduction to the area, including to the results of this paper.