# The Structure of Translational Tilings in $\mathbb{Z}^{d}$

Rachel Greenfeld Partially supported by the Eric and Wendy Schmidt
Postdoctoral Award. Terence Tao Partially supported by NSF grant DMS-1764034
and by a Simons Investigator Award.

###### Abstract

We obtain structural results on translational tilings of periodic functions in
$\mathbb{Z}^{d}$ by finite tiles. In particular, we show that any level one
tiling of a periodic set in $\mathbb{Z}^{2}$ must be weakly periodic (the
disjoint union of sets that are individually periodic in one direction), but
present a counterexample of a higher level tiling of $\mathbb{Z}^{2}$ that
fails to be weakly periodic. We also establish a quantitative version of the
two-dimensional periodic tiling conjecture which asserts that any finite tile
in $\mathbb{Z}^{2}$ that admits a tiling, must admit a periodic tiling, by
providing a polynomial bound on the period; this also gives an exponential-
type bound on the computational complexity of the problem of deciding whether
a given finite subset of $\mathbb{Z}^{2}$ tiles or not. As a byproduct of our
structural theory, we also obtain an explicit formula for a universal period
for all tilings of a one-dimensional tile.

title = The Structure of Translational Tilings in $\mathbb{Z}^{d}$, author =
Rachel Greenfeld and Terence Tao, plaintextauthor = Rachel Greenfeld and
Terence Tao, plaintexttitle = The Structure of Translational Tilings in Z^d,
runningtitle = Structure of Translational Tilings in $\mathbb{Z}^{d}$,
keywords = tiling, periodicity, decidability, year=2021, number=16, received=4
November 2020, published=24 September 2021, doi=10.19086/da.28324,

[classification=text]

##  1 Introduction

###  1.1 Translational tiling

Let $d\geqslant 1$ be an integer, and let $F\subset\mathbb{Z}^{d}$ be a finite
subset of the standard lattice $\mathbb{Z}^{d}$. A _tiling_ 111All tilings in
this paper are by translation; we do not consider tilings that involve
rotation or reflection in addition to translation. of $\mathbb{Z}^{d}$ by $F$
is a subset $A$ of $\mathbb{Z}^{d}$ with the property that every element of
$\mathbb{Z}^{d}$ has precisely one representation of the form $f+a$ with $f\in
F$ and $a\in A$. We refer to $F$ as the _tile_ and $A$ as the _tiling set_ ,
thus $\mathbb{Z}^{d}$ is partitioned (or _tiled_) by translates $F+a$ of the
tile $F$ by elements $a$ of the tiling set. In terms of the convolution
operation

$f*g(x)\coloneqq\sum_{y\in\mathbb{Z}^{d}}f(y)g(x-y)$

on $\mathbb{Z}^{d}$ (which is well-defined if at least one of $f,g$ is
compactly supported, and $f,g$ are real-valued; alternatively, one of $f,g$
can take values in the unit circle $\mathbb{R}/\mathbb{Z}$ if the other is
integer-valued), this property can be expressed as

$\mathds{1}_{F}*\mathds{1}_{A}=1,$

where $\mathds{1}_{F}$ denotes the indicator function of $F$, and similarly
for $A$. More generally, for any natural number $k$ and a subset
$E\subset\mathbb{Z}^{d}$, a _tiling of level $k$_ of $E$ by the tile $F$ is a
set $A$ such that

$\mathds{1}_{F}*\mathds{1}_{A}=k\mathds{1}_{E}.$

We omit the qualifier “of level $k$” if $k=1$, and “of $E$” if
$E=\mathbb{Z}^{d}$.

###  1.2 Periodicity

We call a function $f\colon\mathbb{Z}^{d}\to\mathbb{R}$ _$\Lambda$ -periodic_
for some subgroup $\Lambda$ of $\mathbb{Z}^{d}$ if $f(x+\lambda)=f(x)$ for all
$x\in\mathbb{Z}^{d}$ and $\lambda\in\Lambda$; we simply call $f$ _periodic_ if
it is $\Lambda$-periodic for some $\Lambda$ which is a lattice (a subgroup on
$\mathbb{Z}^{d}$ whose index $[\mathbb{Z}^{d}:\Lambda]$ is finite).

We call a set $E\subset\mathbb{Z}^{d}$ _$\Lambda$ -periodic_ (resp.
_periodic_) if $\mathds{1}_{E}$ is $\Lambda$-periodic (resp. periodic). Note
from Lagrange’s theorem that if $\Lambda$ is a lattice of index
$\ell\coloneqq[\mathbb{Z}^{d}:\Lambda]$, then any $\Lambda$-periodic set or
function will also be $\ell\mathbb{Z}^{d}$-periodic. We call a set
$E\subset\mathbb{Z}^{2}$ _weakly periodic_ if it can be represented as the
disjoint union $E=E_{1}\uplus\dots\uplus E_{m}$ of finitely many sets
$E_{1},\dots,E_{m}$, with each $E_{j}$ $\langle h_{j}\rangle$-periodic along a
one-dimensional subgroup $\langle h_{j}\rangle\coloneqq\\{nh_{j}\colon
n\in\mathbb{Z}\\}$ for some non-zero $h_{j}\in\mathbb{Z}^{2}$.

###  1.3 Periodicity of tiling

In one dimension it is easy to see from the pigeonhole principle that any
tiling $A$ by a finite tile, of any level $k$, is periodic (see [N]). However
in higher dimensions tiling sets need not be periodic. For instance, if $d=2$
and $F_{1}$ is the square $F_{1}=\\{0,1\\}^{2}$, then any set $A_{1}$ of the
form

$A_{1}\coloneqq\\{(2n,2m+a(n))\colon n,m\in\mathbb{Z}\\}$ (1)

with $a\colon\mathbb{Z}\to\\{0,1\\}$ an arbitrary function, is a tiling by
$F_{1}$, but is only periodic if $a$ is periodic. On the other hand, we
observe that this tiling is still $\langle(0,2)\rangle$-periodic. As a
slightly more complex example of this type, if
$F_{2}\coloneqq\\{0,2\\}\times\\{0,1\\}$, then any set $A_{2}$ of the form

$A_{2}\coloneqq\\{(4n,2m+a(n))\colon
n,m\in\mathbb{Z}\\}\cup\\{(4n+1+2b(m),2m)\colon n\in\mathbb{Z}\\}$ (2)

for arbitrary functions $a,b\colon\mathbb{Z}\to\\{0,1\\}$ is a tiling by
$F_{2}$. In general, $A_{2}$ will not be periodic along any non-trivial group
$\Lambda$, but will always be weakly periodic, being the disjoint union of a
$\langle(0,2)\rangle$-periodic set and a $\langle(4,0)\rangle$-periodic set.

Our investigations were primarily motivated by the _periodic tiling
conjecture_ of Lagarias and Wang [LW] (which also implicitly appears
previously in [GS, p. 23]):

######  Conjecture 1.1 (Periodic tiling conjecture).

Let $F\subset\mathbb{Z}^{d}$ be a finite tile. If there is at least one tiling
$A$ by $F$, then there exists a tiling $A^{\prime}$ by $F$ which is periodic.

This conjecture was established in $d=1$ in [N] as a quick application of the
pigeonhole principle. For $d=2$, the conjecture was recently established by
Bhattacharya [B2] using ergodic theory techniques and a “dilation lemma”
proven using elementary number theory (or elementary commutative algebra); see
[WV] for some earlier partial results in the $d=2$ case. For $d>2$ the
conjecture is known when the cardinality $|F|$ of $F$ is prime or equal to $4$
[S5], but remains open in general. On the other hand, the tiling conjecture
for multiple tiles $F_{1},\dots,F_{k}$ in $\mathbb{Z}^{d}$ is known to be
false [B], [R]. Finally, we remark that by a well known argument attributed to
Wang (see [B], [R]), the validity of Conjecture 1.1 at a given dimension $d$
implies that the problem of determining whether a given tile $F$ tiles
$\mathbb{Z}^{d}$ or not is decidable. We refer the reader to [R], [S5] for
further discussion and surveys of tiling problems in lattices.

######  Remark 1.2.

There is also extensive literature on tiling problems on other groups than
$\mathbb{Z}^{d}$, both by indicator functions $\mathds{1}_{F}$ and by more
general tiling functions $f$. For instance, the analogue of Conjecture 1.1 in
$\mathbb{R}^{d}$ is known for convex polytopes [V], [M, M2] and for
topological disks [GN], [K2], and the one-dimensional case is established (for
bounded tiles) in [LM], [LW], [KL]. See the recent papers [L], [KL3] for
further results and open problems of tiling in $\mathbb{R}$ and in
$\mathbb{R}^{d}$. Tiling of more general locally compact groups by functions
is studied in [HN], [LM]. There is also substantial literature on tiling
finite abelian groups, which in this context is also known as _factorization_
; see the text [SS] for a detailed presentation of this topic. Finally, we
note some connections between discrete tilings and low-complexity subshifts of
finite type, see for instance the recent survey [K]. However, the focus of
this paper will be exclusively on tiling problems in lattices
$\mathbb{Z}^{d}$.

###  1.4 Results

We can now state our first main theorem, which clarifies the nature of level
one tilings of periodic sets in two dimensions, in particular revealing a
fundamental difference between level one tilings and higher level tilings.

######  Theorem 1.3 (Tilings in $\mathbb{Z}^{2}$).

  1. (i).

(Level one tilings in the plane are weakly periodic) If
$F\subset\mathbb{Z}^{2}$ is finite and $A$ is a level one tiling of a periodic
set by $F$, then $A$ is weakly periodic.

  2. (ii).

(Higher level tilings in the plane need not be weakly periodic) There exists
an eight-element subset $F\subset\mathbb{Z}^{2}$ and a level $4$ tiling of
$\mathbb{Z}^{2}$ which is not weakly periodic.

Theorem 1.3(ii) is established by an explicit construction which we give in
Section 2; the tiling set is a finite Boolean combination of “Bohr sets”. We
now discuss Theorem 1.3(i). In fact, we have a more quantitative version of
this result. Here and in the sequel we use the asymptotic notation
$X=O_{|F|}(Y)$, $X\ll_{|F|}Y$, or $Y\gg_{|F|}X$ to denote an estimate of the
form $|X|\leqslant C_{|F|}Y$ where $C_{|F|}$ is a quantity depending only on
$|F|$. Similarly with the subscript $|F|$ replaced by other parameters.

######  Theorem 1.4 (Quantitative weak periodicity of level one tilings in
$\mathbb{Z}^{2}$).

Let $F\subset\mathbb{Z}^{2}$ be a tile with $1<|F|<\infty$ and $0\in F$, and
let $A$ be a level one tiling of an $\ell\mathbb{Z}^{2}$-periodic set $E$ by
$F$ for some natural number $\ell$. Then there is a lattice
$\Lambda\subset\ell\mathbb{Z}^{2}$ of index

$[\ell\mathbb{Z}^{2}:\Lambda]\ll_{|F|}\mathrm{diam}(F)^{2(|F|-1)^{2}}$

and pairwise incommensurable vectors $h_{1},\dots,h_{m}\in\mathbb{Z}^{2}$ for
some $1\leqslant m\leqslant|F|-1$ with magnitude bounds

$\|h_{1}\|,\dots,\|h_{m}\|\leqslant\mathrm{diam}(F)^{|F|-1}$ (3)

and a positive integer multiple $L$ of size

$L\ll_{|F|}\mathrm{diam}(F)^{|F|(|F|-1)}$ (4)

such that the intersection of $A$ with each coset of $\Lambda$ is $\langle\ell
Lh_{j}\rangle$-periodic for some $j=1,\dots,m$. Furthermore each $h_{j}$ is an
integer multiple of a vector in $F\backslash\\{0\\}$. The lattice $\Lambda$,
integer $L$, and the vectors $h_{1},\dots,h_{m}$ are allowed to depend on
$E,\ell,F$ but do not otherwise depend on the choice of tiling set $A$.

Note that Theorem 1.4 implies Theorem 1.3(i) after translating the tile $F$ so
that $0\in F$ and dealing with the easy case $|F|=1$ separately. Theorem 1.4
also allows us to classify two-dimensional tilings of level one in terms of
one-dimensional tilings. This classification, in turn, provides a description
of the structure of any two-dimensional tiling of level one. Moreover, using
Theorem 1.4 we prove the following quantitative generalization of the $d=2$
case of Conjecture 1.1, with polynomial type bounds (and also an extension to
tilings of other periodic subsets $E$ of $\mathbb{Z}^{2}$ than the full
lattice $\mathbb{Z}^{2}$):

######  Theorem 1.5 (Quantitative periodic tiling conjecture in two
dimensions).

Let $F\subset\mathbb{Z}^{2}$ be a finite tile, and let
$E\subset\mathbb{Z}^{2}$ be an $\ell\mathbb{Z}^{2}$-periodic set for some
$\ell\geqslant 1$. If there is at least one tiling $A$ of $E$ by $F$, then
there exists a tiling $A^{\prime}$ of $E$ by $F$ by an $\ell
M\mathbb{Z}^{2}$-periodic set with

$M\ll_{|F|}\mathrm{diam}(F)^{O(|F|^{4})}.$

This theorem has the following bound on the computational complexity of
deciding whether a given finite set $F$ is a tile, which is of exponential
type in the diameter of $F$ if $|F|$ is bounded:

######  Corollary 1.6 (Computational complexity bound for planar tiling).

There is an algorithm which, when given a finite subset $F$ of
$\mathbb{Z}^{2}$ as input, decides whether $F$ can tile $\mathbb{Z}^{2}$ in
time $O_{|F|}(\exp(O_{|F|}(\mathrm{diam}(F)^{O(|F|^{4})})))$ (counting each
arithmetic operation as costing time $O(1)$).

###### Proof.

By Theorem 1.5, it suffices to check tilings $A$ that are
$M\mathbb{Z}^{2}$-periodic for some $M\ll_{|F|}\mathrm{diam}(F)^{O(|F|^{4})}$.
Each such tiling can be checked in time $O_{|F|}(M^{2})$, and the number of
$M\mathbb{Z}^{2}$-periodic tilings is at most $2^{M^{2}}$ for each $M$, giving
the claim. ∎

Note that the results in [B2] established that the tiling problem in
$\mathbb{Z}^{2}$ was decidable, but gave no bound on the computational
complexity. The proof of Corollary 1.6 also shows that for fixed $|F|$, the
decision problem is in the complexity class $NP$ with respect to the diameter
$\mathrm{diam}(F)$; for instance, in the unlikely event that $P=NP$, the
decision problem could now be performed in time polynomial in the diameter. It
seems of interest to see if the exponential bound can be improved without the
$P=NP$ hypothesis in the regime when $|F|$ is bounded. In one dimension the
best complexity bound currently known is
$\exp(O_{\varepsilon}(\mathrm{diam}(F)^{1/3+\varepsilon}))$ for any
$\varepsilon>0$, due to Bíró [B3].

We now discuss further the proof of Theorem 1.4. Our starting point is the
following quite explicit structural theorem valid in all dimensions and
levels, which we believe to be of independent interest:

######  Theorem 1.7 (Structure of tilings).

Let $d\geqslant 1$, let $F$ be a finite subset of $\mathbb{Z}^{d}$, and let
$A\subset\mathbb{Z}^{d}$ be a set such that $\mathds{1}_{F}*\mathds{1}_{A}$ is
$\ell\mathbb{Z}^{d}$-periodic for some $\ell\geqslant 1$. We normalize $0\in
F$. Then there exists a decomposition

$\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\backslash\\{0\\}}\varphi_{f}$ (5)

where for each $f\in F\backslash\\{0\\}$,
$\varphi_{f}\colon\mathbb{Z}^{d}\to[0,1]$ is a function which is $\langle
qf\rangle$-periodic, where $q$ is the least common multiple of $\ell$ and all
the primes less than or equal to $2|F|$.

We establish this result in Section 3. It is a consequence of (a
generalization of) the dilation lemma from [B2], which roughly speaking
asserts that if a set (or multi-set) $A$ is a tiling for a tile $F$, then it
is also a tiling for all dilations $rF$ of that tile, as long as $r$ is
congruent to $1$ with respect to a suitable modulus. This fact is number-
theoretic in nature, ultimately boiling down to the Frobenius identity
$(x+y)^{p}=x^{p}+y^{p}$ that is valid in any commutative ring of
characteristic $p$. Theorem 1.7 is then established by averaging over all such
dilations $r$.

######  Remark 1.8.

Theorem 1.7 has the Fourier-analytic consequence that the distributional
Fourier transform $\widehat{\mathds{1}}_{A}$ of $A$, which is a distribution
on the torus $(\mathbb{R}/\mathbb{Z})^{d}$, is supported on the union of the
finite subgroup $\left(\frac{1}{\ell}\mathbb{Z}/\mathbb{Z}\right)^{d}$ and the
codimension one subgroups
$(qf)^{\perp}\coloneqq\\{\xi\in(\mathbb{R}/\mathbb{Z})^{d}\colon
qf\cdot\xi=0\\}$ for $f\in F\backslash\\{0\\}$. A qualitatively similar
conclusion222We also note a possibly related result of Granville and Rudnick
[GR, Corollary 3.1], which in our notation states that if
$f\colon\mathbb{Z}^{d}\to\mathbb{Z}$ is compactly supported and not
identically zero (e.g., if $f=\mathds{1}_{F}$ for some finite non-empty
$F\subset\mathbb{Z}^{d}$), then the set
$\\{\xi\in(\mathbb{Q}/\mathbb{Z})^{d}:\widehat{f}(\xi)=0\\}$ of roots of unity
in the zero set of $\widehat{f}$ can be placed inside the union of a finite
number of explicitly computable codimension one subgroups; this implies a
special case of a conjecture of Lang [L2]. We thank the anonymous referee for
this reference. regarding the spectral measure of a measure-preserving system
associated to a tiling was obtained in [B2, Lemma 3.2]. Our initial arguments
relied heavily on this Fourier analytic structure, but we found eventually
that physical-space arguments were simpler and gave superior bounds to those
relying on the Fourier transform. Furthermore, the physical-space approach we
developed provided us with more structural data, which in particular allowed
us to gain better understanding of the rigidity of tiling structures in
$\mathbb{Z}^{2}$.

Theorem 1.7 already resembles an assertion of weak periodicity of
$\mathds{1}_{A}$, except that the terms on the right-hand side of (5) are not
indicator functions. Nevertheless, the structural theorem turns out to be
particularly powerful in the case of level one tilings, when it imposes a
powerful pointwise constraint

$\sum_{f\in F\backslash\\{0\\}}\varphi_{f}\leqslant 1$ (6)

on the functions $\varphi_{f}$. Furthermore, by working modulo $1$ to
eliminate the $\mathds{1}_{A}$ and $\mathds{1}_{F}*\mathds{1}_{A}$ terms from
(5), we also have the important identity

$\sum_{f\in F\backslash\\{0\\}}\varphi_{f}=0\hbox{ mod }1.$

In dimension two, one can apply discrete differentiation operators, exploiting
the partial periodicity of the $\varphi_{f}$ to conclude that the functions
$\varphi_{f}\hbox{ mod }1$ are polynomials (after collecting commensurable
terms). The classical Weyl equidistribution theory of these polynomials then
asserts that these functions are either periodic or equidistributed in the
unit circle. The powerful constraint (6) lets us eliminate the equidistributed
case, and some further elementary arguments (involving linear algebra facts
such as Cramer’s rule) then allow us to conclude Theorem 1.4.

The proof of Theorem 1.5 also proceeds by exploiting the dilation lemma,
though in a simpler fashion (there is no need to work modulo $1$ in this
case). One could also establish results similar to Theorem 1.5 but with weaker
bounds (of exponential type in the diameter rather than polynomial) by using
the pigeonhole principle instead of the dilation lemma, but we do not present
these arguments here.

As a further application of our structural results, we establish in Corollary
3.5 an explicit formula for a universal period for all tilings $A$ of a given
one-dimensional tile $F\subset\mathbb{Z}$, which (remarkably) is only of
polynomial size in the diameter, as opposed to exponential, in the regime
where the cardinality $|F|$ of the tile is bounded.

Our results leave open the question of whether the analogue of Conjecture 1.1
for higher level (i.e., whether any tile $F$ that admits a level $k$ tiling,
also admits a level $k$ tiling by a periodic set) is true in two dimensions;
neither our positive or negative results seem strong enough to resolve this
question. In the one dimensional lattice the claim easily follows from the
pigeonhole principle (or from Corollary 3.5 below), which forces all tiling
sets at any level to be periodic. On the other hand, on the continuous line
$\mathbb{R}$ an example was given in [KL2] of an $L^{1}(\mathbb{R})$ function
of unbounded support that tiled $\mathbb{R}$ by a set which was not the finite
union of periodic sets. We also mention the recent result of Liu [L] that if a
function $f\in L^{1}(\mathbb{R}^{d})$ tiles by a finite union of lattices at
some level, then it also tiles by a single lattice at a possibly different
level. We refer the reader to the recent survey [KL3] for further discussion
of tiling results in $\mathbb{R}$ and $\mathbb{R}^{d}$.

We plan to investigate the applications of this theory to higher-dimensional
lattice tilings in subsequent work.

###  1.5 Organization of the paper

In Section 2, we present a constructive proof of Theorem 1.3(ii). This section
is self-contained and will not be used in what follows. In Section 3, we
develop an approach to study tiling structures in $\mathbb{Z}^{d}$ and prove
our structure theorem, Theorem 1.7. The proof relies on Lemma 3.1, which we
refer to as the “dilation lemma”. As a direct corollary of our structure
theorem, we obtain an explicit universal period of one-dimensional tilings, of
polynomial size in the diameter of the tile. In Sections 4, 5 and 6, we apply
the results of Section 3 to level one tilings of periodic sets in
$\mathbb{Z}^{2}$. In more detail:

In Section 4, using polynomial sequences (based on [B2]), we prove Theorem
1.4, which is a quantitative version of Theorem 1.3(i). In Section 5, we prove
Theorem 1.5 by combining the former presented results with a “slicing lemma”.
In Section 6, by combining Theorem 1.4 and the results in Section 5, we
establish a satisfactory description of the structure of any tiling of level
one of a periodic set in $\mathbb{Z}^{2}$. In particular, we show that the
question whether a tile $F\subset\mathbb{Z}^{2}$ admits non one-periodic
tiling, is decidable.

###  1.6 Notation

If $F\subset\mathbb{Z}^{d}$ is a set and $r$ is a natural number, we use
$rF\coloneqq\\{rf:f\in F\\}$ to denote the dilation of $F$ by $r$. In
particular we have the lattices $r\mathbb{Z}^{d}=\\{rn:n\in\mathbb{Z}^{d}\\}$.
We use $|F|$ to denote the cardinality of $F$; by abuse of notation we also
use $|z|$ to denote the magnitude of a real or complex number $z$.

We use $x\mapsto x\hbox{ mod }1$ to denote the projection homomorphism from
$\mathbb{R}$ to the (additive) unit circle $\mathbb{R}/\mathbb{Z}$. A
_polynomial of degree at most $d$_ from $\mathbb{Z}$ to
$\mathbb{R}/\mathbb{Z}$ is a map $P\colon\mathbb{Z}\to\mathbb{R}/\mathbb{Z}$
of the form

$P(n)=\alpha_{0}+\alpha_{1}n+\dots+\alpha_{d}n^{d}$

for some $\alpha_{0},\dots,\alpha_{d}\in\mathbb{R}/\mathbb{Z}$.

Two vectors $h_{1},h_{2}\in\mathbb{Z}^{d}$ are said to be _commensurable_ if
one is a scalar multiple of the other, and _incommensurable_ otherwise. In the
two-dimensional case $d=2$, we define the wedge product $h_{1}\wedge h_{2}$ to
be the determinant of the $2\times 2$ matrix with rows $h_{1},h_{2}$; thus
$h_{1},h_{2}$ are commensurable if and only if $h_{1}\wedge h_{2}=0$. If
$h_{1},h_{2}$ are incommensurable, we observe the _Cramer rule_

$v=\frac{v\wedge h_{2}}{h_{1}\wedge h_{2}}h_{1}+\frac{v\wedge
h_{1}}{h_{2}\wedge h_{1}}h_{2}$ (7)

for any $v\in\mathbb{Z}^{2}$ (this is easily verified by first testing the
cases $v=h_{1},h_{2}$, then extending by linearity). In particular, if we let
$\langle h_{1},h_{2}\rangle$ denote the lattice generated by $h_{1},h_{2}$, we
have the inclusion

$|h_{1}\wedge h_{2}|\mathbb{Z}^{2}\subset\langle h_{1},h_{2}\rangle.$ (8)

This inclusion can also be established from Lagrange’s theorem, since
$|h_{1}\wedge h_{2}|$ is the index of $\langle h_{1},h_{2}\rangle$. From
Hadamard’s inequality one has

$|h_{1}\wedge h_{2}|\leqslant\|h_{1}\|\|h_{2}\|$

where $\|h\|$ denotes the Euclidean length of an element $h$ of
$\mathbb{Z}^{d}$.

An element $h\in\mathbb{Z}^{d}$ is said to be _primitive_ if it cannot be
written as $h=mh^{\prime}$ for some $h^{\prime}\in\mathbb{Z}^{d}$ and some
integer $m>1$. Note that every non-zero element $h$ of $\mathbb{Z}^{d}$ can be
uniquely expressed as $h=mh^{\prime}$ where $m$ is a natural number and
$h^{\prime}\in\mathbb{Z}^{d}$ is primitive.

If $h\in\mathbb{Z}^{d}$, we use $\delta_{h}=\mathds{1}_{\\{h\\}}$ to denote
the Kronecker delta function at $h$, and let $\Delta_{h}$ denote the discrete
differentiation operator

$\Delta_{h}f(x)\coloneqq(\delta_{0}-\delta_{h})*f(x)=f(x)-f(x-h)$

in the direction $h$ applied to a function
$f\colon\mathbb{Z}^{d}\to\mathbb{R}$ (or
$f\colon\mathbb{Z}^{d}\to\mathbb{R}/\mathbb{Z}$) at a location
$x\in\mathbb{Z}^{d}$. Note that these operators $\Delta_{h}$ commute with each
other and with convolution by any additional function $g$:

$\Delta_{h}(f*g)=(\Delta_{h}f)*g=f*\Delta_{h}g.$

##  2 The counterexample

In this section we prove Theorem 1.3(ii). The constructions here are not used
elsewhere in the paper; however, the analysis presented in the rest of the
paper was what led us to the counterexample presented here.

We first need to locate a sign pattern on $\mathbb{Z}^{2}$ that obeys certain
cancellation properties.

######  Lemma 2.1.

There exists a $4\mathbb{Z}^{2}$-periodic function
$\chi:\mathbb{Z}^{2}\to\\{-1,1\\}$ such that one has the cancellations

$\displaystyle\chi*\mathds{1}_{\\{(0,0),(0,2)\\}}$ $\displaystyle=0$ (9)
$\displaystyle\chi*\mathds{1}_{\\{(0,0),(1,0)\\}}$ $\displaystyle=0.$ (10)

###### Proof.

It is a routine matter to check that the function

$\chi(m_{1},m_{2})\coloneqq(-1)^{\lfloor m_{2}/2\rfloor+m_{1}}$ (11)

satisfies the claimed properties, where $\lfloor\cdot\rfloor$ is the integer
part function. ∎

Note that (9) and (10) imply

$\chi*\mathds{1}_{\\{(0,0),(2,-2)\\}}=0$ (12)

since

$\mathds{1}_{\\{(0,0),(2,-2)\\}}=\mathds{1}_{\\{(0,0),(0,2)\\}}*\mathds{1}_{\\{(0,-2)\\}}+\mathds{1}_{\\{(0,0),(1,0)\\}}*(\mathds{1}_{\\{(1,-2)\\}}-\mathds{1}_{\\{(0,-2)\\}}).$

Let $\alpha$ be an arbitrary irrational number (e.g., $\alpha=\sqrt{2}$).
Consider the function333The function $(m_{1},m_{2})\mapsto\\{\alpha
m_{1}\\}+\\{\alpha m_{2}\\}-\\{\alpha(m_{1}+m_{2})\\}$ was also mentioned in a
closely related context in [KS, Example 4], [S4, Example 3.4.6].

$a(m_{1},m_{2})\coloneqq\chi(m_{1},m_{2})\left(\\{\alpha m_{1}\\}+\\{\alpha
m_{2}\\}-\\{\alpha(m_{1}+m_{2})\\}-1/2\right)+1/2$

on $\mathbb{Z}^{2}$, where $\chi$ is as in Lemma 2.1 and $\\{x\\}=x-\lfloor
x\rfloor\in[0,1)$ denotes the fractional part of $x\in\mathbb{R}$. Observe
that $\\{\alpha(m_{1}+m_{2})\\}$ is either equal to $\\{\alpha
m_{1}\\}+\\{\alpha m_{2}\\}$ or $\\{\alpha m_{1}\\}+\\{\alpha m_{2}\\}-1$,
hence $a(m_{1},m_{2})$ takes values in $\\{0,1\\}$. Hence this is the
indicator function of some set $A\subset\mathbb{Z}^{2}$:

$\mathds{1}_{A}(m_{1},m_{2})\coloneqq\chi(m_{1},m_{2})(\\{\alpha
m_{1}\\}+\\{\alpha m_{2}\\}-\\{\alpha(m_{1}+m_{2})\\}-1/2)+1/2.$

Now introduce the eight-element tile

$F\coloneqq\\{t_{1}(0,2)+t_{2}(1,0)+t_{3}(2,-2):t_{1},t_{2},t_{3}\in\\{0,1\\}\\}.$

Note that we have the factorization

$\mathds{1}_{F}=\mathds{1}_{\\{(0,0),(0,2)\\}}*\mathds{1}_{\\{(0,0),(1,0)\\}}*\mathds{1}_{\\{(0,0),(2,-2)\\}}.$

From (9) we see that the functions

$(m_{1},m_{2})\mapsto\chi(m_{1},m_{2}),\quad(m_{1},m_{2})\mapsto\chi(m_{1},m_{2})\\{\alpha
m_{1}\\}$

are annihilated by convolution with $\mathds{1}_{\\{(0,0),(0,2)\\}}$.
Similarly, from (10) we see that

$(m_{1},m_{2})\mapsto\chi(m_{1},m_{2})\\{\alpha m_{2}\\}$

is annihilated by convolution with $\mathds{1}_{\\{(0,0),(1,0)\\}}$, and from
(12) we see that

$(m_{1},m_{2})\mapsto\chi(m_{1},m_{2})\\{\alpha(m_{1}+m_{2})\\}$

is annihilated by convolution with $\mathds{1}_{\\{(0,0),(2,-2)\\}}$. Finally,
we have $\mathds{1}_{F}*1=\mathds{1}_{F}*\mathds{1}_{\mathbb{Z}^{2}}=|F|=8$.
Using the bilinear, commutative, and associative properties of convolution, we
conclude that

$\mathds{1}_{F}*\mathds{1}_{A}=4.$

It remains to show that $A$ is not weakly periodic. Suppose for contradiction
that we had a decomposition

$\mathds{1}_{A}=\mathds{1}_{A_{1}}+\dots+\mathds{1}_{A_{m}}$ (13)

where each $A_{i}$ is $\langle h_{i}\rangle$-periodic for some non-zero
$h_{i}\in\mathbb{Z}^{2}$. By repeatedly grouping together sets $A_{i}$
corresponding to commensurate $h_{i}$ and passing to least common multiples,
we may assume that the $h_{i}$ are pairwise incommensurable. In particular, at
most one of the $h_{i}$ is commensurate with $(1,0)$; by relabeling we may
assume that $h_{i}$ is incommensurate with $(1,0)$ for all $2\leqslant
i\leqslant m$; by adding a dummy index if necessary (and an empty set $A_{1}$)
we may assume that $h_{1}$ is commensurate with $(1,0)$. We now rearrange (13)
as

$\begin{split}\chi(m_{1},m_{2})\\{\alpha
m_{2}\\}-\mathds{1}_{A_{1}}(m_{1},m_{2})&=\sum_{i=2}^{m}\mathds{1}_{A_{i}}(m_{1},m_{2})-\chi(m_{1},m_{2})\\{\alpha
m_{1}\\}\\\
&\quad+\chi(m_{1},m_{2})\\{\alpha(m_{1}+m_{2})\\}+\tfrac{1}{2}\chi(m_{1},m_{2})-\tfrac{1}{2}.\end{split}$
(14)

The two terms on the left-hand side of (14) are $\langle(4,0)\rangle$-periodic
and $\langle h_{1}\rangle$-periodic respectively, thus the left-hand side of
(14) is $\langle 4h_{1}\rangle$-periodic. Meanwhile, each of the terms on the
right-hand side of (14) is $\langle h\rangle$-periodic with respect to some
$h$ incommensurate with $(1,0)$ and hence with $4h_{1}$. Let
$\tilde{e}\in\mathbb{Z}^{2}$ be a vector incommensurate with all of these
periods $h$. Then we may find an integer multiple $e=N\tilde{e}$ of
$\tilde{e}$ which lies in $\langle 4h_{1},h\rangle$ for all the periods $h$ on
the right-hand side of (14), thus one has a decomposition

$e=a_{h}(4h_{1})+b_{h}h$

for each such $h$. Applying the discrete differentiation operator
$\Delta_{e-a_{h}(4h_{1})}$ then annihilates any term on the right-hand side of
(14) that is $\langle h\rangle$-periodic, and the operator is equivalent to
$\Delta_{e}$ when applied to the left-hand side of (14). Applying enough of
these discrete differentiation operators to annihilate the entire right-hand
side of (14), we conclude that

$\Delta_{e}^{k}(\chi(m_{1},m_{2})\\{\alpha
m_{2}\\}-\mathds{1}_{A_{1}}(m_{1},m_{2}))=0$

for some integer $k$. Thus, when evaluated on any coset of $\langle
e\rangle=\\{ne:n\in\mathbb{Z}\\}$, the $k^{\mathrm{th}}$ discrete derivative
of function

$\chi(m_{1},m_{2})\\{\alpha m_{2}\\}-\mathds{1}_{A_{1}}(m_{1},m_{2})$ (15)

vanishes. A simple induction on $k$ then shows that (15) is a polynomial (of
degree at most $k-1$); it is also bounded, hence it is constant. In other
words, (15) is $\langle e\rangle$-periodic. As it is also $\langle
4h_{1}\rangle$-periodic, it is in fact periodic, and thus attains at most
finitely many values. But this implies that $\\{\alpha m_{2}\\}$ attains at
most finitely many values, contradicting the irrationality of $\alpha$. This
concludes the proof of Theorem 1.3(ii).

######  Remark 2.2.

Since $\\{(0,0),(0,2)\\}$ admits a periodic tiling of level $1$, $F$ admits a
periodic tiling of level $4$. Hence this example does not provide a
counterexample to the higher level version of Conjecture 1.1, which remains
open even in two dimensions.

##  3 A dilation lemma and the structure theorem

In [B2, Proposition 3.1], some elementary commutative algebra was used to
establish a dilation lemma that asserted, roughly speaking, that if $A$ was a
(multi-set) tiling of $\mathbb{Z}^{d}$ of a tile $F$ at some level $k$, then
$A$ was also a tiling of the dilate $rF$ for an arithmetic progression of
$r$’s. A one-dimensional version of this lemma previously appeared in [T2];
see also [HIPRV, Proposition 3.2] (or [IMP, Theorem 3.3]) for a related
Fourier-analytic dilation lemma for tilings of $\mathbb{F}_{p}^{d}$. Variants
of this lemma were also established in [S5, Lemma 10] and [KS, Lemma 2]. We
re-prove this lemma using elementary number theory, and generalize it from
tilings of $\mathbb{Z}^{d}$ to tilings of periodic level functions.

######  Lemma 3.1 (Dilation lemma).

Let $F$ be a finite subset of $\mathbb{Z}^{d}$ for some $d\geqslant 1$, and
let $g\colon\mathbb{Z}^{d}\to\mathbb{Z}$ be a bounded function.

  1. (i).

If $\mathds{1}_{F}*g=k$ for some integer $k$, then for any prime $p$ with
$p>(\sup g-\inf g)|F|$, one has $\mathds{1}_{pF}*g=k$.

  2. (ii).

If $\mathds{1}_{F}*g=k$ for some integer $k$, and $q$ is the product of all
primes less than or equal to $(\sup g-\inf g)|F|$, then one has
$\mathds{1}_{rF}*g=k$ whenever $r$ is a natural number coprime to $q$.

  3. (iii).

If $\mathds{1}_{F}*g$ is $\ell\mathbb{Z}^{d}$-periodic for some $\ell\geqslant
1$, and $q$ is the least common multiple of $\ell$ and all primes less than or
equal to $2(\sup g-\inf g)|F|$, then $\mathds{1}_{rF}*g=\mathds{1}_{F}*g$
whenever $r$ is a natural number with $r=1\hbox{ mod }q$.

###### Proof.

We begin with (i). The claim is easily verified when $g$ is constant, so we
may assume that $g$ is non-constant, in particular $p>|F|$. We convolve the
equation $\mathds{1}_{F}*g=k$ by $p-1$ further copies of $\mathds{1}_{F}$
using the identity $\mathds{1}_{F}*1=|F|$ to conclude that

$(\mathds{1}_{F})^{*p}*g=|F|^{p-1}k$

where $(\mathds{1}_{F})^{*p}$ is the convolution of $p$ copies of
$\mathds{1}_{F}$. As all functions here are integer-valued, this identity also
holds modulo $p$:

$(\mathds{1}_{F})^{*p}*g=|F|^{p-1}k\hbox{ mod }p.$

By Fermat’s little theorem we have $|F|^{p-1}=1\hbox{ mod }p$. Also, from the
binomial theorem444Alternatively, one can apply the Frobenius endomorphism
$f\mapsto f^{*p}$ to the group algebra $\mathcal{F}_{p}[\mathbb{Z}^{d}]$,
where $\mathcal{F}_{p}$ denotes the finite field of order $p$. we have
$(f+g)^{*p}=f^{*p}+g^{*p}\hbox{ mod }p$ for all finitely supported functions
$f,g\colon\mathbb{Z}^{d}\to\mathbb{Z}$. Iterating this observation and writing
$\mathds{1}_{F}=\sum_{f\in F}\delta_{f}$ as the sum of Kronecker delta
functions $\delta_{f}$, we see that

$(\mathds{1}_{F})^{*p}=\mathds{1}_{pF}\hbox{ mod }p.$

We conclude that

$\mathds{1}_{pF}*g=\mathds{1}_{F}*g\hbox{ mod }p$

or equivalently

$(\mathds{1}_{pF}-\mathds{1}_{F})*g=0\hbox{ mod }p.$

Observe that the left-hand side takes values in the integers of magnitude at
most $(\sup g-\inf g)|F|$ (to show this, one can first shift $g$ by a constant
to normalize $\inf g=0$ if desired). By the assumption on $p$, we thus see
that $(\mathds{1}_{pF}-\mathds{1}_{F})*g=0$, and (i) follows.

To prove (ii), observe from the fundamental theorem of arithmetic that any
$r=1\hbox{ mod }q$ is the product of a finite number of primes $p>(\sup g-\inf
g)|F|$ (possibly with repetition). The claim then follows by iterating (i).

Finally, we prove (iii). If $\mathds{1}_{F}*g$ is
$\ell\mathbb{Z}^{d}$-periodic, then for any $\lambda\in\ell\mathbb{Z}^{d}$ we
have

$\mathds{1}_{F}*\Delta_{\lambda}g=\Delta_{\lambda}(\mathds{1}_{F}*g)=0.$

The discrete derivative $\Delta_{\lambda}g$ takes values in the integers of
magnitude at most $\sup g-\inf g$. Applying (ii), we conclude that

$\mathds{1}_{rF}*\Delta_{\lambda}g=0$

whenever $\lambda\in\ell\mathbb{Z}^{d}$ and $r=1\hbox{ mod }q$. Equivalently,
$\mathds{1}_{rF}*g$ is $\ell\mathbb{Z}^{d}$-periodic for all $r=1\hbox{ mod
}q$, which implies that

$(\mathds{1}_{rF}-\mathds{1}_{F})*g$

is $\ell\mathbb{Z}^{d}$-periodic. In particular, if $B_{R}$ denotes a Følner
sequence on $\ell\mathbb{Z}^{d}$ (for instance one can take
$B_{R}\coloneqq\ell\\{-R,\dots,R\\}^{d}$), then we have

$(\mathds{1}_{rF}-\mathds{1}_{F})*g=(\mathds{1}_{rF}-\mathds{1}_{F})*\frac{1}{|B_{R}|}\mathds{1}_{B_{R}}*g$
(16)

for any $R>0$. But as $r-1$ is a multiple of $\ell$, we have
$rf-f\in\ell\mathbb{Z}^{d}$ for all $f\in F$. From the Følner property we then
have

$\lim_{R\to\infty}\left\|(\delta_{rf}-\delta_{f})*\frac{1}{|B_{R}|}\mathds{1}_{B_{R}}\right\|_{\ell^{1}(\mathbb{Z}^{d})}=0$

for all $f$; from Young’s inequality and the boundedness of $g$ we hence have

$\lim_{R\to\infty}\left\|(\delta_{rf}-\delta_{f})*\frac{1}{|B_{R}|}\mathds{1}_{B_{R}}*g\right\|_{\ell^{\infty}(\mathbb{Z}^{d})}=0$

and hence by the triangle inequality

$\lim_{R\to\infty}\left\|(1_{rF}-1_{F})*\frac{1}{|B_{R}|}\mathds{1}_{B_{R}}*g\right\|_{\ell^{\infty}(\mathbb{Z}^{d})}=0.$

Combining this with (16) one has $(\mathds{1}_{rF}-\mathds{1}_{F})*g=0$, which
gives (iii). ∎

######  Remark 3.2.

The above proof shows that if the requirement $r=1\hbox{ mod }q$ in Lemma
3.1(iii) is relaxed to $r$ merely being coprime to $q$, then
$\mathds{1}_{rF}*g$ is no longer necessarily equal to $\mathds{1}_{F}*g$, but
will still be $\ell\mathbb{Z}^{2}$-periodic. In [S5, Theorems 10, 13] it is
also shown that if $\mathds{1}_{F}*\mathds{1}_{A}=1$ then
$\mathds{1}_{-F}*\mathds{1}_{A}=1$, and also
$\mathds{1}_{rF}*\mathds{1}_{A}\leqslant 1$ whenever $r$ is an integer coprime
to $|F|$. (In fact one can improve the inequality
$\mathds{1}_{rF}*\mathds{1}_{A}\leqslant 1$ to
$\mathds{1}_{F}*\mathds{1}_{A}=1$ by volume packing arguments; see, e.g.,
[GL2, Lemma 3.2].)

Now we can prove Theorem 1.7.

###### Proof of Theorem 1.7.

Let the notation and hypotheses be as in that theorem. From Lemma 3.1(iii) we
have

$\mathds{1}_{rF}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}$

for all natural numbers $r$ with $r=1\hbox{ mod }q$, where $q$ being as in
Lemma 3.1(iii). As $0\in F$, we can rewrite this identity as

$\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\backslash\\{0\\}}\delta_{rf}*\mathds{1}_{A}.$

We can average this to obtain

$\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\backslash\\{0\\}}\varphi_{f,N}$

for any natural number $N\geqslant 1$, where
$\varphi_{f,N}\colon\mathbb{Z}^{d}\to[0,1]$ is the function

$\varphi_{f,N}\coloneqq\frac{1}{N}\sum_{n=1}^{N}\delta_{(1+nq)f}*\mathds{1}_{A}.$

It is clear that $\varphi_{f,N}$ takes values in $[0,1]$. Also from
telescoping series we have

$|\varphi_{f,N}(x+qf)-\varphi_{f,N}(x)|\leqslant\frac{2}{N}$ (17)

for any $x\in\mathbb{Z}^{d}$. By the Arzelá-Ascoli theorem, we can find a
sequence $N_{i}\to\infty$ such that for every $f\in F\backslash\\{0\\}$,
$\varphi_{f,N_{i}}$ converges locally uniformly to a limit $\varphi_{f}$,
which then also takes values in $[0,1]$, and we now have

$\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\backslash\\{0\\}}\varphi_{f}.$

Setting $N=N_{i}$ in (17) and taking limits, we conclude that
$\varphi_{f}(x+qf)-\varphi_{f}(x)=0$ for all $x\in\mathbb{Z}^{d}$, thus
$\varphi_{f}$ is $\langle qf\rangle$-periodic, and Theorem 1.7 follows. ∎

######  Remark 3.3.

The above argument shows that one can interpret $\varphi_{f}(x)$ as a limiting
density of $A$ along the ray $\\{x+(1+nq)f\colon n\in\mathbb{N}\\}$. A similar
averaging argument (using ultrafilter limits instead of generalized limits)
appears in [S4, Section 7.3] in a related context, under different
assumptions.

For our application it is convenient to group together “commensurable” terms
in Theorem 1.7.

######  Theorem 3.4 (Structure of tilings, II).

Let $d,\ell,k\geqslant 1$, let $F$ be a finite subset of $\mathbb{Z}^{d}$, let
$E$ be an $\ell\mathbb{Z}^{d}$-periodic subset of $\mathbb{Z}^{d}$, and let
$A$ be a tiling of $E$ by $F$ of level $k$. We normalize $0\in F$, and assume
$|F|>1$. Then there exists a decomposition

$\mathds{1}_{A}=k\mathds{1}_{E}-\sum_{j=1}^{m}\varphi_{j}$ (18)

where $1\leqslant m\leqslant|F|-1$, and each
$\varphi_{j}\colon\mathbb{Z}^{d}\to[0,k]$ is $\langle qh_{j}\rangle$-periodic,
where $q$ is the least common multiple of $\ell$ and all the primes less than
or equal to $2|F|$, and $h_{1},\dots,h_{m}$ are pairwise incommensurable
elements of $\mathbb{Z}^{d}$ such that

$\prod_{j=1}^{m}\|h_{j}\|\leqslant\mathrm{diam}(F)^{|F|-1}.$ (19)

In particular, we have the upper bounds

$q\ll_{|F|}\ell$ (20)

and

$\sum_{j=1}^{m}\varphi_{j}\leqslant k.$ (21)

Furthermore, each $h_{j}$ is an integer multiple of an element of
$F\backslash\\{0\\}$.

###### Proof.

From Theorem 1.7 one has

$\mathds{1}_{A}=k\mathds{1}_{E}-\sum_{f\in
F\backslash\\{0\\}}\tilde{\varphi}_{f}$

where each $\tilde{\varphi}_{f}\colon\mathbb{Z}^{d}\to[0,1]$ is $\langle
qf\rangle$-periodic. We define an equivalence relation on $F\backslash\\{0\\}$
by declaring $f\sim f^{\prime}$ if $f,f^{\prime}$ are commensurable (namely,
$f=pf^{\prime}$ for some rational $p$). If we let $C_{1},\dots,C_{m}$ be the
equivalence classes of this relation, then $1\leqslant m\leqslant|F|-1$ and we
have a decomposition (18) with

$\varphi_{j}\coloneqq\sum_{f\in C_{j}}\tilde{\varphi}_{f}.$

In particular the $\varphi_{j}$ are non-negative, and then from (18) and the
non-negativity of $\mathds{1}_{A}$ we conclude that all the $\varphi_{j}$ are
also bounded by $k$, as well as the bound (21). Since each
$\tilde{\varphi}_{f}$ is $\langle qf\rangle$-periodic, we see on taking least
common multiples that $\varphi_{j}$ is $\langle qh_{j}\rangle$-periodic for
some non-zero $h_{j}\in\mathbb{Z}^{2}$ commensurable to the elements of
$C_{j}$ and of magnitude at most

$\|h_{j}\|\leqslant\prod_{f\in C_{j}}\|f\|\leqslant\mathrm{diam}(F)^{|C_{j}|}$

(note that $\|f\|\leqslant\mathrm{diam}(F)$ for all $f\in F$ since $0\in F$).
In particular we have (19). Since the $C_{j}$ are pairwise incommensurable,
the $h_{j}$ are also pairwise incommensurable. Finally, the bound (20) is
clear from definition of $q$. ∎

We have found that the bound (21) is particularly powerful in the level one
case $k=1$, as it can be used in that case to completely rule out
“equidistributed” scenarios in which at least one of the $\varphi_{j}$ has
values that equidistribute in the unit interval $[0,1]$. However, in higher
level settings it is possible for multiple equidistributed $\varphi_{j}$ to
coexist, which is what led us to the counterexample constructed in Section 2.

As another quick application of Theorem 1.7, we obtain an explicit formula for
a universal period of one-dimensional tiles:

######  Corollary 3.5 (Universal period of one-dimensional tiles).

Let $F$ be a finite subset of $\mathbb{Z}$, and let $A\subset\mathbb{Z}$ be a
set such that $\mathds{1}_{F}*\mathds{1}_{A}$ is $\langle\ell\rangle$-periodic
for some $\ell\geqslant 1$. We normalize $0\in F$. Then $A$ is $\langle
qn\rangle$-periodic, where $q$ is the least common multiple of $\ell$ and all
the primes less than or equal to $2|F|$, and $n$ is the least common multiple
of $\|f\|$ for all $f\in F\backslash\\{0\\}$.

###### Proof.

From Theorem 1.7 we see that $\mathds{1}_{A}$ is the linear combination of a
finite number of terms, each of which is $qn$-periodic. The claim follows. ∎

As first observed in [N], an easy application of the pigeonhole principle
already gives that all one-dimensional tilings are periodic; however, the
bound produced is exponential in the diameter $\mathrm{diam}(F)$ if done
naively. In contrast, the bound here is polynomial in the diameter (for fixed
$|F|$), and further is uniform over _all_ tilings $A$ of an
$\langle\ell\rangle$-periodic set by a fixed tile $F$, whereas the period
produced by pigeonhole principle arguments will depend on the choice of
tiling. In [S2] it was shown that if the cardinality $|F|$ of the tile is not
held fixed, the period of a one-dimensional tiling can grow superpolynomially
in the diameter $n\coloneqq\mathrm{diam}(F)$ (in fact a lower bound
$\exp(\log^{2}n/4\log\log n)$ is demonstrated for infinitely many $n$); there
is also an exponential lower bound for indecomposable tilings of higher level
[S3]. Conversely, the best known upper bound for the period for a tile of
diameter $n$ (with no restriction on $|F|$) is
$\exp(O_{\varepsilon}(n^{1/3+\varepsilon}))$ [B3].

######  Remark 3.6.

In the special case of Corollary 3.5 when $\mathds{1}_{F}*\mathds{1}_{A}=1$,
the dilation lemma of Tijdeman [T2, Theorem 1] (see also [CM] for an alternate
proof) allows one to replace “all the primes less than or equal to $2|F|$”
with “all the primes dividing $|F|$”.

##  4 Weak periodicity of two-dimensional tilings of level one

We now prove Theorem 1.4. Our starting point is the decomposition in Theorem
3.4. Accordingly, let $m,\varphi_{1},\dots,\varphi_{m},h_{1},\dots,h_{m},q$ be
as in that theorem. If $m=1$ then (18) ensures that $A$ is $\langle
qh_{1}\rangle$-periodic, and we are already done. Henceforth we assume
$m\geqslant 2$, hence $|F|\geqslant 3$.

Since there are at most $|F|-1$ vectors $h_{1},\dots,h_{m}$, and they are all
non-zero, one can find a vector $\tilde{e}\in\mathbb{Z}^{2}$ of size
$O_{|F|}(1)$ which is incommensurable to all of the $h_{1},\dots,h_{m}$. Next,
let $N$ be the least common multiple of all the determinant magnitudes
$|h_{i}\wedge h_{j}|$ for $1\leqslant i<j\leqslant m$, thus by (8) one has

$N\mathbb{Z}^{2}\subset\langle h_{i},h_{j}\rangle$ (22)

for all $1\leqslant i<j\leqslant m$. We also have the bounds

$\begin{split}N&\leqslant\prod_{1\leqslant i<j\leqslant
m}\|h_{i}\|\|h_{j}\|\\\ &\leqslant(\prod_{j=1}^{m}\|h_{j}\|)^{m-1}\\\
&\leqslant\mathrm{diam}(F)^{(|F|-1)(|F|-2)}.\end{split}$ (23)

For any $x\in\mathbb{Z}^{2}$ and $j=1,\dots,m$, we introduce the one-
dimensional functions $P_{x,j}\colon\mathbb{Z}\to[0,1]$ by the formula

$P_{x,j}(n)\coloneqq\varphi_{j}(x+ne),$ (24)

where $e=qN\tilde{e}$. These functions enjoy several useful properties:

######  Proposition 4.1 (Properties of $P_{x,j}$).

Let $x\in\mathbb{Z}^{2}$.

  1. (i).

One has $\sum_{j=1}^{m}P_{x,j}(n)=0\hbox{ mod }1$ for all $n\in\mathbb{Z}$.

  2. (ii).

For each $1\leqslant j\leqslant m$, the map $n\mapsto P_{x,j}(n)\hbox{ mod }1$
is a polynomial of degree at most $m-2$.

  3. (iii).

For any $1\leqslant i<j\leqslant m$, one has
$\sup_{n\in\mathbb{Z}}P_{x,i}(n)+\sup_{n\in\mathbb{Z}}P_{x,j}(n)\leqslant 1$.

We remark that the polynomiality property (ii) was previously observed in [B2,
Lemma 4.3]. The linear forms $\alpha m_{1}\hbox{ mod }1,\alpha m_{2}\hbox{ mod
}1,\alpha(m_{1}+m_{2})\hbox{ mod }1$ implicitly appearing in Section 2 are
essentially examples of the polynomials appearing in Proposition 4.1, in the
context of higher level tilings. However, we will eliminate this sort of
“equidistributed” behavior in the level one case in Proposition 4.4 below.

###### Proof of Proposition 4.1.

If starts with (18) and works modulo $1$ to eliminate the $\mathds{1}_{A}$ and
$\mathds{1}_{E}$ terms, we have

$\sum_{j=1}^{m}\varphi_{j}=0\hbox{ mod }1.$ (25)

Evaluating this at $x+ne$ we obtain (i).

Now we prove (ii). Let $1\leqslant j\leqslant m$. From (22) we see that for
any $1\leqslant i\leqslant m$ distinct from $j$, that

$e=qN\tilde{e}\in q\langle h_{i},h_{j}\rangle,$

that is to say we have

$e=a_{i,j}qh_{i}+b_{i,j}qh_{j}$ (26)

for some integers $a_{i,j},b_{i,j}$. In particular, from the $\langle
qh_{i}\rangle$-periodicity of $\varphi_{i}$ we have

$\Delta_{e-b_{i,j}qh_{j}}\varphi_{i}=0$

while from the $\langle qh_{j}\rangle$-periodicity of $\varphi_{j}$ we have

$\Delta_{e-b_{i,j}qh_{j}}\varphi_{j}=\Delta_{e}\varphi_{j}.$

If we then apply the discrete derivative operators $\Delta_{e-b_{i,j}qh_{j}}$
for each $1\leqslant i\leqslant m$ distinct from $j$ in turn to (25) to
eliminate all the $\varphi_{i}$ other than $\varphi_{j}$, we conclude that

$\Delta_{e}^{m-1}*\varphi_{j}=0\hbox{ mod }1.$

(Note that the discrete derivative operators only involve convolution with
integer-valued functions and are well defined on functions that are only
defined modulo $1$.) Evaluating this on the line $\\{x+ne:n\in\mathbb{Z}\\}$
using (24), we conclude the one-dimensional identity

$\Delta_{1}^{m-1}P_{x,j}=0\hbox{ mod }1.$

That is to say, the $(m-1)^{\mathrm{th}}$ discrete derivative of
$P_{x,j}\hbox{ mod }1$ vanishes. A simple induction on $m$ then shows that
$P_{x,j}\hbox{ mod }1$ is a polynomial of degree at most $m-2$, giving (ii) as
claimed.

Now we prove (iii). Let $1\leqslant i<j\leqslant m$. As in (26), we write $e$
as a linear combination (26) of $qh_{i},qh_{j}$. In particular, for any
$n_{1},n_{2}\in\mathbb{Z}$ one has the identity

$(x+n_{1}e)+a_{i,j}(n_{2}-n_{1})qh_{i}=(x+n_{2}e)-b_{i,j}(n_{2}-n_{1})qh_{j}.$

Evaluating (21) at this point, we conclude in particular that

$\varphi_{i}((x+n_{1}e)+a_{i,j}(n_{2}-n_{1})qh_{i})+\varphi_{j}((x+n_{1}e)-b_{i,j}(n_{2}-n_{1})qh_{j})\leqslant
1.$

Using (24), the $\langle qh_{i}\rangle$-periodicity of $\varphi_{i}$, and the
$\langle qh_{j}\rangle$-periodicity of $\varphi_{j}$, we conclude that

$P_{x,i}(n_{1})+P_{x,j}(n_{2})\leqslant 1.$

Taking suprema in $n_{1},n_{2}$, we obtain (iii). ∎

To exploit these properties, we use the following exponential sum
estimate555We thank Igor Shparlinski for this reference. from analytic number
theory.

######  Lemma 4.2 (Exponential sum estimate).

Let $d\geqslant 1$, and let $P\colon\mathbb{Z}\to\mathbb{R}/\mathbb{Z}$ be a
nonconstant polynomial of degree at most $d$ whose nonconstant coefficients
are rational with denominators having least common multiple $Q$; in particular
$P$ is periodic with period $Q$. Then one has

$\left|\sum_{n=1}^{Q}e^{2\pi iP(n)}\right|\ll_{d}Q^{1-\frac{1}{d}}.$

###### Proof.

See [S]. ∎

We also remark that bounds of this type (but with the gain $1/d$ replaced by
an exponent that decays exponentially in $d$) can be established by the Weyl
differencing (or van der Corput) method; see for instance [T, Lemma 1.1.16].

######  Lemma 4.3 (Polynomials only fail to equidistribute when periodic).

Let $P\colon\mathbb{Z}\to\mathbb{R}/\mathbb{Z}$ be a polynomial of some degree
$d$ that avoids an interval $I$ of positive length in $\mathbb{R}/\mathbb{Z}$.
Then $P$ is periodic with period at most $O_{d,I}(1)$.

###### Proof.

Since $P$ is not equidistributed666We say that a function
$P\colon\mathbb{Z}\to\mathbb{R}/\mathbb{Z}$ is equidistributed if we have
$\lim_{N\to\infty}\frac{1}{2N+1}\sum_{n=-N}^{N}F(P(n))=\int_{\mathbb{R}/\mathbb{Z}}F(t)\
dt$ for all continuous $F\colon\mathbb{R}/\mathbb{Z}\to\mathbb{R}$., we see
from the Weyl equidistribution theorem that all the non-constant coefficients
of $P$ must be rational. We let $Q$ be the least common multiple of the
denominators of these coefficients, then $P$ is periodic with period $Q$. By
the Weierstrass approximation theorem, one can find a trigonometric polynomial
$f$ (depending only on $I$) that is periodic with period $1$, has mean zero,
and is at least $1$ outside of $I$. Then

$\frac{1}{Q}\sum_{n=1}^{Q}f(P(n))\geqslant 1.$

By the pigeonhole principle, we can thus find a non-zero integer $k=O_{I}(1)$
such that

$\left|\frac{1}{Q}\sum_{n=1}^{Q}e^{2\pi ikP(n)}\right|\gg_{I}1.$

Note that the least common multiple of the denominators of $kP(n)$ is
$\gg_{d,I}Q$. Applying Lemma 4.2, we conclude that $Q=O_{d,I}(1)$, giving the
claim. ∎

Let $M$ be the least common multiple of $|\tilde{e}\wedge h_{j}|$ for
$1\leqslant j\leqslant m$. Let $\Lambda\coloneqq\langle e,qNMh_{1}\rangle$ be
the lattice generated by $e,qNMh_{1}$. Note in particular that

$\Lambda\subset q\mathbb{Z}^{2}\subset\ell\mathbb{Z}^{2}.$

######  Proposition 4.4 (One-dimensional periodicity in each coset).

On each coset $x+\Lambda$, the set $A\cap(x+\Lambda)$ is $\langle
Q_{m}M^{2}Nqh_{j}\rangle$-periodic for some $1\leqslant j\leqslant m$, where
$Q_{m}$ depends only on $m$ and $Q_{m}M^{2}Nqh_{j}\in\Lambda$.

###### Proof.

From (8) one has

$M\mathbb{Z}^{2}\subset\langle\tilde{e},h_{i}\rangle$

for all $1\leqslant i\leqslant m$. In particular, for each $1\leqslant
i\leqslant m$ one has

$qNMh_{1}=a_{i}qh_{i}+b_{i}e$ (27)

where $e=qN\tilde{e}$ and $a_{i},b_{i}$ are the integers

$a_{i}\coloneqq NM\frac{h_{1}\wedge\tilde{e}}{h_{i}\wedge\tilde{e}}$ (28)

and

$b_{i}\coloneqq M\frac{h_{1}\wedge h_{i}}{\tilde{e}\wedge h_{i}}.$

In particular we have

$\Lambda=\langle e,a_{i}qh_{i}\rangle$

for all $1\leqslant i\leqslant m$.

Fix $x\in\mathbb{Z}^{2}$. From (27) we have for any integers $s,t$ that

$\displaystyle\varphi_{i}(x+se+tqNMh_{1})$
$\displaystyle=\varphi_{i}(x+(s+b_{i}t)e+ta_{i}qh_{i})$
$\displaystyle=\varphi_{i}(x+(s+b_{i}t)e)$ $\displaystyle=P_{x,i}(s+b_{i}t)$

thanks to the $\langle qh_{i}\rangle$-periodicity of $\varphi_{i}$, and (24).
Also, since $q$ is a multiple of $\ell$, $e$ is a multiple of $q$, and $E$ is
$\ell\mathbb{Z}^{2}$-periodic, one has

$\mathds{1}_{E}(x+se+tqNMh_{1})=\mathds{1}_{E}(x).$

Thus we have the decomposition

$\mathds{1}_{A}(x+se+tqNMh_{1})=\mathds{1}_{E}(x)-\sum_{j=1}^{m}P_{x,j}(s+b_{i}t).$
(29)

Suppose first that $\sup_{n\in\mathbb{Z}}P_{x,j}(n)=1$ for some $1\leqslant
j\leqslant m$. Then from Proposition 4.1(iii) we have $P_{x,i}(n)=0$ for all
other $i$, hence by Proposition 4.1(i), $P_{x,j}$ takes values in $\\{0,1\\}$.
The decomposition (29) then simplifies to

$\mathds{1}_{A}(x+se+tqNMh_{1})=\mathds{1}_{E}(x)-P_{x,j}(s+b_{j}t)$

for all $s,t\in\mathbb{Z}$. From (27) and the change of variables
$s^{\prime}\coloneqq s+b_{j}t$ this implies that

$\mathds{1}_{A}(x+s^{\prime}e+ta_{j}qh_{j})=\mathds{1}_{E}(x)-P_{x,j}(s^{\prime})$

for all $s^{\prime},t\in\mathbb{Z}$. In particular, on the coset $x+\Lambda$,
the function $\mathds{1}_{A}$ is $\langle a_{j}qh_{j}\rangle$-periodic, and
hence $\langle M^{2}Nqh_{j}\rangle$-periodic by (28) and the construction of
$M$. Note that this argument also shows that $M^{2}Nqh_{j}\in\Lambda$.

Now suppose we are in the opposite case that

$\sup_{n\in\mathbb{Z}}P_{x,j}(n)<1$

for all $1\leqslant j\leqslant m$. From Proposition 4.1(iii) this implies that

$\sup_{n\in\mathbb{Z}}P_{x,i}(n)\leqslant 1/2$

for all $1\leqslant i\leqslant m$ with at most one exception; thus, with at
most one exception, $P_{x,i}\hbox{ mod }1$ takes values in $[0,1/2]\hbox{ mod
}1$. By Proposition 4.1(ii) and Lemma 4.3 this implies that with at most one
exception, the $P_{x,i}\hbox{ mod }1$ are periodic with period $O_{m}(1)$.
Using Proposition 4.1(i) and Lemma 4.3, an exception cannot occur. Taking a
common denominator, we conclude that there is a positive integer $Q_{m}$
depending only on $m$, such that the $P_{x,i}\hbox{ mod }1$ for all
$1\leqslant i\leqslant m$ are $\langle Q_{m}\rangle$-periodic; since all the
$P_{x,i}$ have supremum strictly less than $1$, we see that the $P_{x,i}$ are
also $\langle Q_{m}\rangle$-periodic (note we no longer work modulo $1$). From
(29) we conclude that on the coset $x+\Lambda$, $A$ is $\langle
Q_{m}MNqh_{1}\rangle$-periodic. Thus in either case we obtain the proposition.
∎

We finally conclude Theorem 1.4.

###### Proof of Theorem 1.4.

From (19) we can bound

$\displaystyle M$
$\displaystyle\leqslant\prod_{j=1}^{m}\|h_{j}\|\|\tilde{e}\|$
$\displaystyle\ll_{|F|}\mathrm{diam}(F)^{|F|-1}$

and then from this and (19), (20), (23) the lattice $\Lambda\coloneqq\langle
qN\tilde{e},qNMh_{1}\rangle$ has index in $\ell\mathbb{Z}^{2}$ at most

$\displaystyle qN\|\tilde{e}\|qNM\|h_{1}\|/\ell^{2}$
$\displaystyle\ll_{|F|}N^{2}M\mathrm{diam}(F)^{|F|-1}$
$\displaystyle\ll_{|F|}\mathrm{diam}(F)^{2(|F|-1)^{2}}.$

A similar computation shows that the quantity $L\coloneqq Q_{m}M^{2}Nq/\ell$
is an integer of magnitude at most

$\displaystyle L$ $\displaystyle\ll_{|F|}M^{2}N$
$\displaystyle\ll_{|F|}\mathrm{diam}(F)^{(|F|-1)|F|}.$

This establishes Theorem 1.4 (note from an inspection of the arguments that
none of the quantities $h_{1},\dots,h_{m},L,\Lambda$ constructed depends
directly on $A$). ∎

##  5 Converting weakly periodic tilings to periodic tilings

A simple pigeonholing argument777This argument is analogous to Newman’s proof
of the one-dimensional periodic tiling conjecture ([N]). shows that the
existence of a weakly periodic tiling implies the existence of a periodic
tiling (see, e.g., [B2, Theorem 2.3], [RX, Proposition 2.1]). In this section
we introduce a constructive way to convert any weakly periodic tiling to a
periodic tiling. This constructive approach allows us to achieve the
significantly better bound in Theorem 1.5, on the periods of the obtained
periodic tiling. This bound is polynomial in the diameter of the tile $F$ (for
fixed $|F|$).

We first give a “slicing lemma” that allows one to “slice” the tile $F$ along
cosets along which the tiling set $A$ already exhibits some periodicity, while
retaining the periodicity of the set being tiled.

######  Lemma 5.1 (Slicing lemma).

Let $\ell,k\geqslant 1$ be natural numbers, and let $h$ be a primitive element
of $\mathbb{Z}^{2}$. Suppose that $F$ is a finite subset of $\mathbb{Z}^{2}$,
and $A$ is a $\langle\ell kh\rangle$-periodic subset of $\mathbb{Z}^{2}$ such
that $\mathds{1}_{F}*\mathds{1}_{A}$ is $\ell\mathbb{Z}^{2}$-periodic. Then
for every coset $x+\langle h\rangle$ of $\langle h\rangle$, the function
$\mathds{1}_{F\cap(x+\langle h\rangle)}*\mathds{1}_{A}$ is
$qks\mathbb{Z}^{2}$-periodic, where $q$ is the least common multiple of $\ell$
and all the primes less than or equal to $2|F|$, and $s$ is the least common
multiple of the $|h\wedge(f-f^{\prime})|$ for all $f,f^{\prime}\in F$ with
$f-f^{\prime}$ incommensurate with $h$.

###### Proof.

We may assume that $F$ intersects $x+\langle h\rangle$, as the claim is
trivial otherwise; by relabeling we may then assume $x\in F$. By translating
$F$ and $x$ we then may assume that $x=0$ and $0\in F$. From Lemma 3.1(iii) we
have

$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{rF}*\mathds{1}_{A}$

whenever $r=1\hbox{ mod }q$. If we strengthen the condition on $r$ to
$r=1\hbox{ mod }qk$, then for each $f\in F\cap\langle h\rangle$, we have
$rf-f\in\langle qkh\rangle\subset\langle\ell kh\rangle$, hence by the
$\langle\ell kh\rangle$-periodicity of $A$ we have

$(\mathds{1}_{r(F\cap\langle h\rangle)}-\mathds{1}_{F\cap\langle
h\rangle})*\mathds{1}_{A}=0.$

Combining the two equations, we see that

$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{F\cap\langle
h\rangle}*\mathds{1}_{A}+\sum_{f\in F\backslash\langle
h\rangle}\delta_{rf}*\mathds{1}_{A}$

and thus

$\mathds{1}_{F\cap\langle
h\rangle}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\backslash\langle h\rangle}\delta_{rf}*\mathds{1}_{A}$

whenever $r=1\hbox{ mod }qk$. Note that all the terms on the right-hand side
are $\langle\ell kh\rangle$-periodic, since $\mathds{1}_{A}$ is. Averaging
over $r$ and using the Arzelá-Ascoli theorem to extract a limit as in the
proof of Theorem 1.7, we see that

$\mathds{1}_{F\cap\langle
h\rangle}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\backslash\langle h\rangle}\varphi_{f}$

for some functions $\varphi_{f}$ which are both $\langle\ell
kh\rangle$-periodic and $\langle qkf\rangle$-periodic. By (8) and the
definition of $s$ and $q$, each $\varphi_{f}$ is $qks\mathbb{Z}^{2}$-periodic,
as is $\mathds{1}_{F}*\mathds{1}_{A}$, and the claim follows. ∎

######  Remark 5.2.

The above argument is in fact applicable to any $d$-dimensional one-periodic
tiling of a periodic set. More precisely, it shows that if
$F\subset\mathbb{Z}^{d}$ is finite, $h\in\mathbb{Z}^{d}$ is primitive and
$A\subset\mathbb{Z}^{d}$ is a $\langle kh\rangle$-periodic set such that
$\mathds{1}_{F}*\mathds{1}_{A}$ is periodic, then the “slice”
$\mathds{1}_{F\cap\langle h\rangle}*\mathds{1}_{A}$ can be written as

$\mathds{1}_{F\cap\langle
h\rangle}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A}-\sum_{f\in
F\setminus\langle h\rangle}\varphi_{f},$

where for any $f\in F\setminus\langle h\rangle$, the function
$\varphi_{f}:\mathbb{Z}^{d}\to[0,1]$ is $\langle kh,qkf\rangle$-periodic, for
some $q(F)\in\mathbb{Z}$.

We now use the slicing lemma to improve the periodicity properties of a
tiling. The slicing lemma allows us to reduce the two-dimensional tiling to a
collection of one-dimensional tilings, by considering slices (or “cut and
project” sets) of both the tile $F$ and the tiling set $A$. We remark that
similar argument was used in [JP] and [GL] in a different context.

######  Corollary 5.3 (Improving a tiling, I).

Let $\ell,k\geqslant 1$ be natural numbers, and let $h$ be a primitive element
of $\mathbb{Z}^{2}$. Suppose that $F$ is a finite subset of $\mathbb{Z}^{2}$,
and $A$ is a $\langle\ell kh\rangle$-periodic subset of $\mathbb{Z}^{2}$ such
that $\mathds{1}_{F}*\mathds{1}_{A}$ is $\ell\mathbb{Z}^{2}$-periodic. Then
there exists a $qks\mathbb{Z}^{2}$-periodic set $A^{\prime}$ such that
$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}}$, where
$q,s$ are as in Lemma 5.1. In fact we have the stronger statement

$\mathds{1}_{F}*\mathds{1}_{A\cap(\langle
h\rangle+y)}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}\cap(\langle h\rangle+y)}$

for any coset $\langle h\rangle+y$ of $\langle h\rangle$.

###### Proof.

By applying an invertible linear transformation in
$\mathrm{SL}_{2}(\mathbb{Z})$ we may assume without loss of generality that
the primitive element $h$ is equal to $(1,0)$. For every integer
$y\in\mathbb{Z}$, we introduce the one-dimensional slices

$F_{y}\coloneqq\\{x\in\mathbb{Z}:(x,y)\in F\\}$

and

$A_{y}\coloneqq\\{x\in\mathbb{Z}:(x,y)\in A\\}.$

From Lemma 5.1 we know that for each $y$, the set
$\mathds{1}_{F_{y}\times\\{y\\}}*\mathds{1}_{A}$ is
$qks\mathbb{Z}^{2}$-periodic, which in particular implies on taking slices
that

$\mathds{1}_{F_{y}}*\mathds{1}_{A_{z}}=\mathds{1}_{F_{y}}*\mathds{1}_{A_{z+qks}}$

for all $y,z\in\mathbb{Z}$, that is to say the map
$z\mapsto\mathds{1}_{F_{y}}*\mathds{1}_{A_{z}}$ is periodic in $z$.

Let $\Sigma$ denote the collection of all $\langle\ell k\rangle$-periodic
subsets of $\mathbb{Z}$; this is a finite set that contains $A_{z}$ for all
$z\in\mathbb{Z}$. Introduce an equivalence relation on $\Sigma$ by declaring
$B\sim B^{\prime}$ if
$\mathds{1}_{F_{y}}*\mathds{1}_{B}=\mathds{1}_{F_{y}}*\mathds{1}_{B^{\prime}}$
for all $y\in\mathbb{Z}$. Thus we have $A_{z+qks}\sim A_{z}$ for all
$z\in\mathbb{Z}$. Now arbitrarily place a total ordering on the finite set
$\Sigma$, and for each $z\in\mathbb{Z}$ let $\tilde{A}_{z}\in\Sigma$ denote
the minimal element in the equivalence class $\\{B\in\Sigma:B\sim A_{z}\\}$.
Then we have $\tilde{A}_{z+qks}=\tilde{A}_{z}\sim A_{z}$ for all
$z\in\mathbb{Z}$. If we then define the modified set

$\tilde{A}\coloneqq\\{(x,z):z\in\mathbb{Z},x\in\tilde{A}_{z}\\}$

then $\tilde{A}$ is $qks\mathbb{Z}^{2}$-periodic, and we have

$\mathds{1}_{F_{y}\times\\{y\\}}*\mathds{1}_{\tilde{A}}=\mathds{1}_{F_{y}\times\\{y\\}}*\mathds{1}_{A}$

for all $y$, which on taking horizontal slices implies that

$\mathds{1}_{F_{y}\times\\{y\\}}*\mathds{1}_{\tilde{A}\cap(\mathbb{Z}\times\\{z\\})}=\mathds{1}_{F_{y}\times\\{y\\}}*\mathds{1}_{A\cap(\mathbb{Z}\times\\{z\\})}$

for all $y,z\in\mathbb{Z}$. Summing in $y$, we conclude that

$\mathds{1}_{F}*\mathds{1}_{\tilde{A}\cap(\mathbb{Z}\times\\{z\\})}=\mathds{1}_{F}*\mathds{1}_{A\cap(\mathbb{Z}\times\\{z\\})},$

giving the claim. ∎

Now we combine this corollary with the argument used to establish Proposition
4.1(ii) to convert weakly periodic tilings to periodic tilings.

######  Theorem 5.4 (Improving a tiling, II).

Let $\ell\geqslant 1$ and $m\geqslant 2$ be natural numbers, and let
$h_{1},\dots,h_{m}$ be pairwise incommensurable elements of $\mathbb{Z}^{2}$.
Suppose that $F$ is a finite subset of $\mathbb{Z}^{2}$, that $E$ is an
$\ell\mathbb{Z}^{2}$-periodic subset of $\mathbb{Z}^{2}$, and $A$ is a tiling
of $E$ by $F$. Suppose that $A$ is weakly periodic, and more specifically that
$A$ is the disjoint union $A=A_{1}\uplus\dots\uplus A_{m}$ where each $A_{j}$
is $\langle\ell h_{j}\rangle$-periodic. Then there exists a $\ell
M\mathbb{Z}^{2}$-periodic set $A^{\prime}$ such that
$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}}=\mathds{1}_{E}$,
where $M$ is an integer with the bound

$M\ll_{|F|}(\prod_{i=1}^{m}\|h_{i}\|)^{m+|F|(|F|-1)/2}\mathrm{diam}(F)^{m|F|(|F|-1)/2}.$

Furthermore each $\mathds{1}_{F}*\mathds{1}_{A_{j}}$ is $\ell
N_{j}\mathbb{Z}^{2}$-periodic for some integer $N_{j}$ with bound

$N_{j}\ll_{|F|}(\prod_{i=1}^{m}\|h_{i}\|)^{m-1}\|h_{j}\|.$

###### Proof.

We can locate an element $\tilde{e}\in\mathbb{Z}^{2}$ of magnitude $O_{m}(1)$
which is incommensurable with all of the $h_{i}$. We define $N$ to be the
least common multiple of the $|h_{i}\wedge h_{j}|$ for $1\leqslant
i<j\leqslant m$, and set $e\coloneqq\ell N\tilde{e}$. Observe that

$N\leqslant\prod_{1\leqslant i<j\leqslant m}|h_{i}\wedge
h_{j}|\leqslant(\prod_{i=1}^{m}\|h_{i}\|)^{m-1}.$

Let $1\leqslant j\leqslant m$. We have the identity

$\mathds{1}_{F}*\mathds{1}_{A_{j}}+\sum_{i\in\\{1,\dots,m\\}\setminus\\{j\\}}\mathds{1}_{F}*\mathds{1}_{A_{i}}=\mathds{1}_{E}$

To eliminate all the terms besides $\mathds{1}_{F}*\mathds{1}_{A_{j}}$ we
apply discrete differentiation operators as in the proof of Proposition
4.1(ii). From (8) we can write

$e=a_{i,j}\ell h_{i}+b_{i,j}\ell h_{j}$

for all $1\leqslant i\leqslant m$ distinct from $j$ and some integers
$a_{i,j},b_{i,j}$. Then from the periodicity properties of the $A_{i}$,
$A_{j}$ we have

$\Delta_{e-b_{i,j}\ell h_{j}}(\mathds{1}_{F}*\mathds{1}_{A_{i}})=0$

and

$\Delta_{e-b_{i,j}\ell
h_{j}}(\mathds{1}_{F}*\mathds{1}_{A_{j}})=\Delta_{e}(\mathds{1}_{F}*\mathds{1}_{A_{j}});$

also from the $\ell\mathbb{Z}^{2}$-periodicity of $E$ one has

$\Delta_{e-b_{i,j}\ell h_{j}}\mathds{1}_{E}=0.$

Applying each of the discrete derivative operators $\Delta_{e-b_{i,j}\ell
h_{j}}$ in turn, we conclude that

$\Delta_{e}^{m-1}(\mathds{1}_{F}*\mathds{1}_{A_{j}})=0.$

Thus, for any $x$, the map $n\mapsto\mathds{1}_{F}*\mathds{1}_{A_{j}}(x+ne)$
is polynomial in $n$; but it is also bounded, hence constant. Thus
$\mathds{1}_{F}*\mathds{1}_{A_{j}}$ is $\langle e\rangle$-periodic and
$\langle\ell h_{j}\rangle$-periodic, hence by (8) it is $\ell
NM_{j}\mathbb{Z}^{2}$-periodic for some integer $M_{j}$ with
$M_{j}\ll_{m}\|h_{j}\|$. We now split $h_{j}=k_{j}h^{\prime}_{j}$ where
$k_{j}$ is a natural number and $h^{\prime}_{j}$ is primitive. By Corollary
5.3 we see that we can find a $q_{j}k_{j}s_{j}\mathbb{Z}^{2}$-periodic set
$A^{\prime}_{j}$ such that
$\mathds{1}_{F}*\mathds{1}_{A_{j}}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}_{j}}$,
where $q_{j}=\ell NM_{j}C_{j}$ for some $C_{j}=O_{|F|}(1)$, and $s_{j}$ is a
positive integer with the bound

$s_{j}\leqslant(\|h^{\prime}_{j}\|\mathrm{diam}(F))^{|F|(|F|-1)/2}.$

We conclude that $q_{j}k_{j}s_{j}=\ell NL_{j}$ with

$L_{j}\ll_{|F|}\|h_{j}\|^{1+|F|(|F|-1)/2}\mathrm{diam}(F)^{|F|(|F|-1)/2}.$

Summing over $j$, we have

$\mathds{1}_{F}*\sum_{j=1}^{m}\mathds{1}_{A^{\prime}_{j}}=\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{E}.$

In particular this shows that $\sum_{j=1}^{m}\mathds{1}_{A^{\prime}_{j}}$ is
bounded by $1$, that is to say the $A^{\prime}_{j}$ are disjoint. If we set
$A^{\prime}\coloneqq\bigcup_{j=1}^{m}A^{\prime}_{j}$, we then have
$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}}=\mathds{1}_{E}$,
and $A^{\prime}$ is $\ell M\mathbb{Z}^{2}$-periodic with

$M\leqslant
N\prod_{j=1}^{m}L_{j}\ll_{|F|}(\prod_{i=1}^{m}\|h_{i}\|)^{m+|F|(|F|-1)/2}\mathrm{diam}(F)^{m|F|(|F|-1)/2}$

giving the claim. ∎

We can now conclude the proof of Theorem 1.5.

###### Proof of Theorem 1.5.

The claim is trivial for $|F|=1$, so suppose $|F|>1$. By Theorem 1.4, there
exist $m,h_{1},\dots,h_{m},L$ obeying the conclusions of that theorem, such
that $A$ is the disjoint union of $\langle\ell Lh_{j}\rangle$-periodic sets
for $j=1,\dots,m$. Applying Theorem 5.4 (with $\ell$ replaced by $\ell L$), we
can find an $\ell LM^{\prime}\mathbb{Z}^{2}$-periodic set $A^{\prime}$ with
$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}}=\mathds{1}_{E}$,
where

$M^{\prime}\ll_{|F|}(\prod_{i=1}^{m}\|h_{i}\|)^{\tfrac{1}{2}(|F|+2)(|F|-1)}\mathrm{diam}(F)^{\tfrac{1}{2}|F|(|F|-1)^{2}}.$

Using the bounds (3), (4), we have

$LM^{\prime}\ll_{|F|}\mathrm{diam}(F)^{|F|(|F|-1)}\mathrm{diam}(F)^{\tfrac{1}{2}(|F|+2)(|F|-1)^{3}}\mathrm{diam}(F)^{\tfrac{1}{2}|F|(|F|-1)^{2}}.$

The claim follows. ∎

##  6 One-periodic tilings

Call a set $A$ _one-periodic_ if $A$ is $\langle h\rangle$-periodic for some
non-zero $h$. For any given tile $F$ of $\mathbb{Z}^{2}$, we consider888We
thank Mihalis Kolountzakis (private communication) for suggesting this
question. the following question:

######  Question 6.1.

Let $F$ be a finite tile of $\mathbb{Z}^{2}$. Does there exist a tiling of
$\mathbb{Z}^{2}$ by $F$ which is not one-periodic?

The answer to this question is positive for some tiles and negative for
others, as the following examples show:

  1. (i).

If $F_{0}$ is the square $\\{0,1\\}^{2}$, then every tiling of
$\mathbb{Z}^{2}$ by $F_{0}$ can be seen to be either
$\langle(2,0)\rangle$-periodic or $\langle(0,2)\rangle$-periodic, and hence
the answer to Question 6.1 is negative in this case. More generally, from [S5,
Theorem 19] it follows that the answer to Question 6.1 is negative for any
tile of cardinality $4$ that contains zero and generates $\mathbb{Z}^{2}$.

  2. (ii).

On the other hand, in Subsection 1.3 it was shown that the four-element tile
$F_{1}\coloneqq\\{0,2\\}\times\\{0,1\\}$ (which does _not_ generate
$\mathbb{Z}^{2}$) admits tilings $A$ of $\mathbb{Z}^{2}$ that are not one-
periodic. Note that if $A$ is a tiling of $\mathbb{Z}^{2}$ by $F_{2}$, then
$2A$ is a tiling of $\mathbb{Z}^{2}$ by $F_{2}\coloneqq
2F_{1}+\\{0,1\\}^{2}=\\{0,4\\}\times\\{0,2\\}+\\{0,1\\}^{2}$. Thus the answer
to Question 6.1 is positive for the tiles $F_{1},F_{2}$. In particular it is
possible to have non-one-periodic tilings even when the tile $F$ contains $0$
and generates all of $\mathbb{Z}^{2}$ as an abelian group.

  3. (iii).

If the tile $F$ is collinear (it lies in a one-dimensional affine subspace of
$\mathbb{R}^{2}$), then Corollary 3.5 implies that all tilings of
$\mathbb{Z}^{2}$ by $F$ are $\langle h\rangle$-periodic for some universal
period $h$ that is parallel to the line that $F$ lies in. Hence the answer to
Question 6.1 is negative in this case.

  4. (iv).

If the tile $F$ is “connected” in the sense that
$F+[-\tfrac{1}{2},\tfrac{1}{2}]^{2}$ is simply connected, then by [GN, Theorem
5.5], $F$ admits only one-periodic tilings of $\mathbb{Z}^{2}$. Hence the
answer to Question 6.1 is negative in this case. This of course contains the
first part of (i) as a special case.

  5. (v).

From [S5, Theorem 17] it follows that if $F$ has prime order $|F|=p$ then
every tiling of $\mathbb{Z}^{2}$ by $F$ is $p\mathbb{Z}^{2}$-periodic, so the
answer to Question 6.1 is negative in this case.

We do not have a full classification of the tiles $F$ which have a negative
answer to Question 6.1. However, the results presented in our paper do at
least show that this question is decidable for any given tile, even if one
replaces the set $\mathbb{Z}^{2}$ by more general periodic subsets of
$\mathbb{Z}^{2}$.

######  Theorem 6.2 (Decidability of Question 6.1).

There is an algorithm which, when given periodic subset $E$ of
$\mathbb{Z}^{2}$ and a finite set $F$ that tiles $E$ as input999Note that a
periodic subset $E$ of $\mathbb{Z}^{2}$ can be stored using a finite amount of
memory, by first storing a pair of generators for the periodicity lattice, and
then storing a coset representative for each of the cosets of that lattice
that lie in $E$., decides in finite time whether $F$ admits a non one-periodic
tiling of $E$, or not.

###### Proof.

Suppose that $F$ is a tile of an $\ell\mathbb{Z}^{2}$ periodic set $E$. From
Theorem 1.4 and Theorem 5.4 we can compute positive integers
$m,N_{1},\dots,N_{m}$ and pairwise incommensurable
$h_{1},\dots,h_{m}\in\mathbb{Z}^{2}$, with the property that for every tiling
set $A$ of $E$ by $F$, there exists partitions $A=A_{1}\uplus\dots\uplus
A_{m}$ and $E=E_{1}\uplus\dots\uplus E_{m}$, where for each $1\leqslant
j\leqslant m$, $A_{j}$ is $\langle h_{j}\rangle$-periodic, $E_{j}$ is
$N_{j}\mathbb{Z}^{2}$-periodic, and $A_{j}$ is a tiling set for $E_{j}$ by
$F$: $\mathds{1}_{F}*\mathds{1}_{A_{j}}=\mathds{1}_{E_{j}}$. We write
$h_{j}=k_{j}h^{\prime}_{j}$ for a (computable) natural number $k_{j}$ and
primitive $h^{\prime}_{j}$. By Corollary 5.3, we can then compute positive
integers $M_{1},\dots,M_{m}$ such that whenever
$A,A_{1},\dots,A_{m},E_{1},\dots,E_{m}$ are as above, one can find an
$M_{j}\mathbb{Z}^{2}$-periodic set $A^{\prime}_{j}$ for each $j=1,\dots,m$
such that

$A_{j}\cap(\langle
h^{\prime}_{j}\rangle+y)\equiv_{F}A^{\prime}_{j}\cap(\langle
h^{\prime}_{j}\rangle+y)$

for all cosets $\langle h^{\prime}_{j}\rangle+y$, where we use
$A\equiv_{F}A^{\prime}$ to denote the equivalence relation
$\mathds{1}_{F}*\mathds{1}_{A}=\mathds{1}_{F}*\mathds{1}_{A^{\prime}}$. By
construction we have

$\sum_{j=1}^{m}\mathds{1}_{F}*\mathds{1}_{A^{\prime}_{j}}=\sum_{j=1}^{m}\mathds{1}_{F}*\mathds{1}_{A_{j}}=\sum_{j=1}^{m}\mathds{1}_{E_{j}}=\mathds{1}_{E}.$

Conversely, if for each $j=1,\dots,m$ we locate a
$M_{j}\mathbb{Z}^{2}$-periodic set $A^{\prime}_{j}$ such that

$\sum_{j=1}^{m}\mathds{1}_{F}*\mathds{1}_{A^{\prime}_{j}}=\mathds{1}_{E}$ (30)

and then for each coset $A^{\prime}_{j}\cap(\langle h^{\prime}_{j}\rangle+y)$
we find a $\langle h_{j}\rangle$-periodic subset $A_{j,\langle
h^{\prime}_{j}\rangle+y}$ of $\langle h^{\prime}_{j}\rangle+y$ such that

$A_{j,\langle h^{\prime}_{j}\rangle+y}\equiv_{F}A^{\prime}_{j}\cap(\langle
h^{\prime}_{j}\rangle+y)$ (31)

then the sets

$A_{j}\coloneqq\bigcup_{\langle
h^{\prime}_{j}\rangle+y\in\mathbb{Z}^{2}/\langle
h^{\prime}_{j}\rangle}A_{j,\langle h^{\prime}_{j}\rangle+y}$

are such that

$A_{j}\equiv_{F}A^{\prime}_{j}$

and hence

$\sum_{j=1}^{m}\mathds{1}_{F}*\mathds{1}_{A_{j}}=\mathds{1}_{E}.$

In particular, the $A_{j}$ are disjoint and their union

$A\coloneqq\bigcup_{j=1}^{m}A_{j}=\bigcup_{j=1}^{m}\bigcup_{y\in\langle
h^{\prime}_{j}\rangle^{\perp}}A_{j,\langle h^{\prime}_{j}\rangle+y}$ (32)

tiles $E$ by $F$. Thus, we have a way of completely describing all the tilings
$A$ of $E$ by $F$: we first locate all tuples
$(A^{\prime}_{1},\dots,A^{\prime}_{m})$ of $M_{j}\mathbb{Z}^{2}$-periodic sets
$A^{\prime}_{j}$ obeying (30), then for each such tuple, each $j=1,\dots,m$,
and each coset $\langle h^{\prime}_{j}\rangle+y$, we choose a $\langle
h_{j}\rangle$-periodic subset $A_{j,\langle h^{\prime}_{j}\rangle+y}$ obeying
(31), then the unions (32) give all the possible tilings of $E$ by $F$.

Note that there are only finitely many $M_{j}\mathbb{Z}^{2}$-periodic subsets
of $\mathbb{Z}^{2}$ (in fact there are $2^{M_{j}^{2}}$ many), so there are
only finitely many possible tuples $(A^{\prime}_{1},\dots,A^{\prime}_{m})$
that can arise in this fashion. For each such tuple, the identity (30) can be
verified or disproved in finite time. Hence we can completely enumerate all
the possible tuples $(A^{\prime}_{1},\dots,A^{\prime}_{m})$ that can arise in
the above construction. Similarly, for each coset $\langle
h^{\prime}_{j}\rangle+y$ and any fixed choice of $A^{\prime}_{j}$, the set of
all $\langle h_{j}\rangle$-periodic subsets $A_{j,\langle
h^{\prime}_{j}\rangle+y}$ of $\langle h^{\prime}_{j}\rangle+y$ obeying (31) is
also finite and can be enumerated in finite time. However, there are
infinitely many such cosets, and hence one may potentially need to loop over
an infinite number of choices in order to enumerate all possible tilings (cf.
the tilings (1), (2)).

Fortunately, for the question of whether there admit non-one-periodic tilings
we do not need to exhaust over infinitely many possibilities, and can instead
reason as follows. Let us call a slice $A^{\prime}_{j}\cap(\langle
h^{\prime}_{j}\rangle+y)$ of an $M_{j}\mathbb{Z}^{2}$-periodic set
$A^{\prime}_{j}$ by a coset $(\langle h^{\prime}_{j}\rangle+y)$ a _chameleon_
if there exists a $\langle h_{j}\rangle$-periodic subsets $A_{j,\langle
h^{\prime}_{j}\rangle+y}$ of $\langle h^{\prime}_{j}\rangle+y$ obeying (31)
which is not equal to $A^{\prime}_{j}\cap(\langle h^{\prime}_{j}\rangle+y)$,
in which case we say that $A^{\prime}_{j}$ _contains a chameleon slice_. Note
that for any given $M_{j}\mathbb{Z}^{2}$-periodic set $A^{\prime}_{j}$, the
slices of $A^{\prime}_{j}\cap(\langle h^{\prime}_{j}\rangle+y)$ repeat
periodically in $y$ and hence one can determine whether $A^{\prime}_{j}$
contains a chameleon slice or not in finite time.

Suppose first that $A$ arises from a tuple
$(A^{\prime}_{1},\dots,A^{\prime}_{m})$ with the property that at most one of
the $A^{\prime}_{j}$ admits a chameleon slice, thus we have some $j_{0}$ such
that $A^{\prime}_{j}$ does not admit a chameleon slice for any $j\neq j_{0}$.
Then for $j\neq j_{0}$, the set $A_{j,\langle h^{\prime}_{j}\rangle+y}$ is
necessarily equal to $A^{\prime}_{j}\cap(\langle h^{\prime}_{j}\rangle+y)$ for
every $y$, hence $A_{j}$ is necessarily equal to the
$M_{j}\mathbb{Z}^{2}$-periodic set $A^{\prime}_{j}$. Since $A_{j_{0}}$ is also
$\langle h_{j_{0}}\rangle$-periodic, we conclude that the set $A$ constructed
in (32) is one-periodic in this case.

Now suppose that $A$ arises from a tuple
$(A^{\prime}_{1},\dots,A^{\prime}_{m})$ with the property that there are at
least two sets $A^{\prime}_{j_{1}},A^{\prime}_{j_{2}}$ which admit chameleon
slices $A^{\prime}_{j_{1}}\cap(\langle h^{\prime}_{j_{1}}+y_{1})$,
$A^{\prime}_{j_{2}}\cap(\langle h^{\prime}_{j_{2}}+y_{2})$ respectively. Thus
for $i=1,2$, we may find a $\langle h_{j_{i}}\rangle$-periodic subset
$A^{(i)}$ of $\langle h^{\prime}_{j_{i}}\rangle+y_{i}$ that is distinct from
$(A^{\prime})^{(i)}\coloneqq A^{\prime}_{j_{i}}\cap\langle
h^{\prime}_{j_{i}}\rangle+y_{i}$ such that

$A^{(i)}\equiv_{F}(A^{\prime})^{(i)}.$

In particular, if we set $A^{\prime}\coloneqq\bigcup_{j=1}^{m}A^{\prime}_{j}$,
and let $A$ be the set formed from $A^{\prime}$ by replacing
$(A^{\prime})^{(i)}$ with $A^{(i)}$ for $i=1,2$, so that

$\mathds{1}_{A}=\mathds{1}_{A^{\prime}}+\sum_{i=1}^{2}(\mathds{1}_{A^{(i)}}-\mathds{1}_{(A^{\prime})^{(i)}}),$

then $A$ is equivalent to $A^{\prime}$:

$\mathds{1}_{A}*\mathds{1}_{F}=\mathds{1}_{A^{\prime}}*\mathds{1}_{F}=\mathds{1}_{E}.$

We claim that $A$ is not one-periodic. Since $\mathds{1}_{A^{\prime}}$ is
$M\mathbb{Z}^{2}$-periodic for some $M$, it suffices to show that
$\sum_{i=1}^{2}(\mathds{1}_{A^{(i)}}-\mathds{1}_{(A^{\prime})^{(i)}})$ is not
one-periodic. But each summand
$\mathds{1}_{A^{(i)}}-\mathds{1}_{(A^{\prime})^{(i)}}$ is a non-trivial one-
periodic function supported on the coset $\langle
h^{\prime}_{j_{i}}+y_{i}\rangle$, and the claim is then evident from the
incommensurability of $h^{\prime}_{j_{1}}$ and $h^{\prime}_{j_{2}}$.

From the above discussion, we conclude that $F$ admits non-one-periodic
tilings if and only if there exist $M_{j}\mathbb{Z}^{2}$-periodic sets
$A^{\prime}_{j}$ for $j=1,\dots,m$ obeying (30) such that at least two of the
$A^{\prime}_{j}$ admit chameleon slices. Since we can computably enumerate all
the tuples $(A^{\prime}_{1},\dots,A^{\prime}_{m})$ obeying (30) and test all
of them for chameleon slices, the claim follows. ∎

Informally, the proof of Theorem 6.2 tells us that all the tilings of a given
periodic set $E$ by a given tile $F$ arise from starting with a doubly
periodic tiling $A^{\prime}=A^{\prime}_{1}\uplus\dots\uplus A^{\prime}_{m}$
(which is drawn from a finite list of such tilings) and performing a (possibly
infinite) number of “slide moves” in which one or more slices
$A^{\prime}_{j}\cap(\langle h^{\prime}_{j}\rangle+y)$ is replaced with an
equivalent (one-periodic) set $A_{j,\langle h^{\prime}_{j}\rangle+y}$, in the
spirit of (1) or (2). In principle, this should reduce any reasonable question
about such tilings to a finite computation for any fixed choice of $E,F$, with
the existence of non-one-periodic tilings serving as just one representative
example of such a question.

## Acknowledgments

We thank Jarkko Kari for alerting us to the relevant references [K], [KS],
[S4]. We also thank Mihalis Kolountzakis for helpful suggestions, and Nishant
Chandgotia and several readers of the second author’s blog for further
comments and corrections. We have also implemented several suggestions of the
anonymous referee.

## References

  * [B] R. Berger, _The undecidability of the domino problem_ , Mem. Amer. Math. Soc. Not. 66 (1966), 72.
  * [B2] S. Bhattacharya, _Periodicity and Decidability of Tilings of $\mathbb{Z}^{2}$_, Amer. J. Math., 142, (2020), 255–266.
  * [B3] A. Bíró, _Divisibility of integer polynomials and tilings of the integers_ , Acta Arith. 118 (2005), 117–127.
  * [CM] E. Coven, A. Meyerowitz, _Tiling the integers with translates of one finite set_ , J. Algebra 212 (1999), no. 1, 161–174.
  * [GN] D. Girault-Beauquier, M. Nivat, _Tiling the plane with one tile_ , In Topology and category theory in computer science (Oxford, 1989), Oxford Sci. Publ., 291–333. Oxford Univ. Press, New York, 1991.
  * [GL] R. Greenfeld, N. Lev, Spectrality and tiling by cylindric domains, Journal of Functional Analysis, 271 (2016), 2808–2821.
  * [GL2] R. Greenfeld, N. Lev, Spectrality of product domains and Fuglede’s conjecture for convex polytopes, Journal d’Analyse Mathematique, 140 (2020) 409–441.
  * [GR] A. Granville, Z. Rudnick, Torsion points on curves, Equidistribution in number theory, an introduction, 85–92, NATO Sci. Ser. II Math. Phys. Chem., 237, Springer, Dordrecht, 2007.
  * [GS] B. Grunbaum, G. C. Shephard, Tilings and Patterns. New York: Freeman 1987.
  * [HIPRV] C. D. Haessig, A. Iosevich, J. Pakianathan, S. Robins, L. Vaicunas, _Tiling, circle packing and exponential sums over finite fields_ , Anal. Math. 44 (2018), no. 4, 433–449.
  * [HN] B. Helffer, J. Nourrigat, _Caractérisation des opérateurs hypoelliptiques homogènes invariants à gauche sur un groupe de Lie nilpotent gradué_ , Comm. Partial Differential Equations 4 (1979), 899–958.
  * [IMP] A. Iosevich, A. Mayeli, J. Pakianathan, _The Fuglede conjecture holds in $\mathbb{Z}_{p}\times\mathbb{Z}_{p}$_, Anal. PDE 10 (2017), no. 4, 757–764.
  * [IP] A. Iosevich, S. Pedersen, Spectral and tiling properties of the unit cube, Int. Math. Res. Not. IMRN (1998), no. 16, 819–828.
  * [JP] P. E. T. Jorgensen, S. Pedersen, Spectral pairs in cartesian coordinates, Journal of Fourier Analysis and Applications, 5, (1999), 285–302.
  * [K] J. Kari, _Low-Complexity Tilings of the Plane_ , preprint. arXiv:1905.04183
  * [K2] R. Kenyon, _Rigidity of planar tilings_ , Invent. Math. 107 (1992), 637–651.
  * [KL] M. N. Kolountzakis, J. C. Lagarias, _Structure of tilings of the line by a function_ , Duke Math. J. 82 (1996), 653–678.
  * [KL2] M. Kolountzakis, N. Lev, _On non-periodic tilings of the real line by a function_ , Int. Math. Res. Not. IMRN 15 (2016), 4588–4601.
  * [KL3] M. N. Kolountzakis, N. Lev, _Tiling by translates of a function: results and open problems_ , preprint. arXiv:2009.09410
  * [KS] J. Kari, M. Szabados, _An algebraic geometric approach to Nivat’s conjecture_ Automata, languages, and programming. Part II, 273–285, Lecture Notes in Comput. Sci., 9135, Springer, Heidelberg, 2015
  * [LM] H. Leptin, D. Müller, _Uniform partitions of unity on locally compact groups_ , Adv. Math. 90 (1991), no. 1, 1–14.
  * [L] B. Liu, _Periodic structure of translational multi-tilings in the plane_ , preprint. arXiv:1809.03440
  * [L2] S. Lang, _Division points on curves_ , Ann. Mat. Pura Appl. 70 (1965), 229–234.
  * [LW] J. C. Lagarias, Y. Wang, _Tiling the line with translates of one tile_ , Invent. Math. 124 (1996), no. 1-3, 341–365.
  * [M] P. McMullen, _Convex bodies which tile space by translations_ , Mathematika 27 (1980), 113–121.
  * [M2] P. McMullen, _Acknowledgement of priority: “Convex bodies which tile space by translation”_ , Mathematika, 28, (1981), no. 2, 191.
  * [N] D. J. Newman, _Tesselation of integers_ , J. Number Theory 9 (1977), no. 1, 107–111.
  * [RX] H. Rao, Y. M. Xue, _Tiling $\mathbb{Z}^{2}$ with translations of one set_, Discrete Mathematics and Theoretical Computer Science, DMTCS, (2006), 8, 129-–140.
  * [R] R. M. Robinson, _Undecidability and nonperiodicity for tilings of the plane_ , Invent. Math. 12 (1971), 177–209.
  * [S] S. B. Stechkin, _Estimate of a complete rational trigonometric sum_ , Trudy Mat. Inst. Steklov. 143 (1977), 188–220. Translated in Proc. Steklov Inst. Math. 1 (1980), 201–220.
  * [S2] J. Steinberger, _Tilings of the integers can have superpolynomial periods_ , Combinatorica 29 (2009), no. 4, 503–509.
  * [S3] J. Steinberger, _Indecomposable tilings of the integers with exponentially long periods_ , Electron. J. Combin. 12 (2005), Research Paper 36, 20 pp.
  * [SS] S. Szabó, A. Sands, _Factoring groups into subsets. Lecture Notes in Pure and Applied Mathematics_ , 257. CRC Press, Boca Raton, FL, 2009.
  * [S4] M. Szabados, _An Algebraic Approach to Nivat’s Conjecture_ , TUCS Dissertations No. 234 (2018), Turku Centre for Computer Science.
  * [S5] M. Szegedy, _Algorithms to tile the infinite grid with finite clusters_ , Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS ’98), IEEE Computer Society, Los Alamitos, CA, (1998), 137–145.
  * [T] T. Tao, Higher order Fourier analysis, Graduate Studies in Mathematics, 142. American Mathematical Society, Providence, RI, (2012).
  * [T2] R. Tijdeman, _Decomposition of the integers as a direct sum of two subsets_ , Number theory (Paris, 1992–1993), 261–276, London Math. Soc. Lecture Note Ser., 215, Cambridge Univ. Press, Cambridge, 1995.
  * [V] B. A. Venkov, _On a class of Euclidean polyhedra_ , Vestnik Leningrad Univ. Ser. Math. Fiz. Him. 9 (1954), 11–31.
  * [WV] H. A. G. Wijshoff, J. van Leeuwen, _Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino_ , Inform. and Control 62 (1984), 1–25.

[RG] Rachel Greenfeld
UCLA Department of Mathematics
Los Angeles, CA 90095-1555

greenfeldmath.uclaedu
https://www.math.ucla.edu/ greenfeld [tao] Terence Tao
UCLA Department of Mathematics
Los Angeles, CA 90095-1555
taomath.uclaedu
https://www.math.ucla.edu/ tao