# Periodicity of joint co-tiles in $\mathbb{Z}^{d}$

Tom Meyerovitch  Ben-Gurion University of the Negev, Department of
Mathematics, Beer-Sheva, 8410501, Israel<EMAIL_ADDRESS>,  Shrey Sanadhya
Ben-Gurion University of the Negev, Department of Mathematics, Beer-Sheva,
8410501, Israel<EMAIL_ADDRESS>and  Yaar Solomon  Ben-Gurion
University of the Negev. Department of Mathematics. Beer-Sheva, 8410501,
Israel<EMAIL_ADDRESS>
###### Abstract.

An old theorem of Newman asserts that any tiling of $\mathbb{Z}$ by a finite
set is periodic. A few years ago, Bhattacharya proved the periodic tiling
conjecture in $\mathbb{Z}^{2}$. Namely, he proved that for a finite subset $F$
of $\mathbb{Z}^{2}$, if there exists $A\subseteq\mathbb{Z}^{2}$ such that
$F\oplus A=\mathbb{Z}^{2}$ then there exists a periodic
$A^{\prime}\subseteq\mathbb{Z}^{2}$ such that $F\oplus
A^{\prime}=\mathbb{Z}^{2}$. The recent refutation of the periodic tiling
conjecture in high dimensions due to Greenfeld and Tao motivates finding
different generalizations of Newman’s theorem and of Bhattacharya’s theorem
that hold in arbitrary dimension $d$. In this paper, we formulate and prove
such generalizations. We do so by studying the structure of joint co-tiles in
$\mathbb{Z}^{d}$. Our generalization of Newman’s theorem states that for any
$d\geq 1$, any joint co-tile for $d$ independent tiles is periodic. For a
$(d-1)$-tuple of finite subsets of $\mathbb{Z}^{d}$ that satisfy a certain
technical condition that we call property $(\star)$, we prove that any joint
co-tile decomposes into disjoint $(d-1)$-periodic sets. Consequently, we show
that for a $(d-1)$-tuple of finite subsets of $\mathbb{Z}^{d}$ that satisfy
property $(\star)$, the existence of a joint co-tile implies the existence of
periodic joint co-tile. Conversely, we prove that if a finite subset $F$ in
$\mathbb{Z}^{d}$ admits a periodic co-tile $A$, then there exist $(d-1)$
additional tiles that together with $F$ are independent and admit $A$ as a
joint co-tile, and $(d-2)$ additional tiles that together with $F$ satisfy the
property $(\star)$. Combined, our results give a new necessary and sufficient
condition for a subset of $\mathbb{Z}^{d}$ to tile periodically. We also
discuss tilings and joint tilings in other countable abelian groups.

###### Key words and phrases:

translational tilings, periodic tiling conjecture, tiling equations.

###### 2000 Mathematics Subject Classification:

52C22, 37B52, 05B45, 52C23, 37B10

##  1\. Introduction

Let $\Gamma$ be a countable abelian group. Given $A,B\subseteq\Gamma$ the
_sumset_ $A+B$ is given by

$A+B=\left\\{a+b\leavevmode\nobreak\ :\leavevmode\nobreak\ a\in
A,\leavevmode\nobreak\ b\in B\right\\}.$

We write $A\oplus B=C$ if every $c\in C$ has a unique representation as
$c=a+B$ with $a\in A$ and $b\in B$. We denote the cardinality of a set $F$ by
$|F|$. We write $F\Subset\Gamma$ to indicate that $F$ is a finite subset of
$\Gamma$.

One says that $F$ _tiles_ $\Gamma$ if there exists a collection of disjoint
union of translates of $F$ whose union is equal to $\Gamma$. That is, $F$
tiles $\Gamma$ if there exists a set $A\subseteq\Gamma$ such that

$F\oplus A=\Gamma.$ (1)

In that case, we say that $A$ is a co-tile for the tile $F$. Let
$g,h:\Gamma\rightarrow\mathbb{R}$, where $\Gamma$ is a countable abelian
group. When at least one of the functions $g,h:\Gamma\rightarrow\mathbb{R}$ is
finitely supported, the _convolution_ $g*h:\Gamma\rightarrow\mathbb{R}$ is
well defined and given by

$g*h(x)=\sum_{y\in\Gamma}g(y)\cdot h(x-y).$

Using this notation, equation (1) is equivalent to
$\mathbf{1}_{F}*\mathbf{1}_{A}=1$, where $\mathbf{1}_{X}$ denotes the
indicator function of the set $X$.

Elements $g_{1},\ldots,g_{k}\in\Gamma$ of the abelian group $\Gamma$ are
called _independent_ if the only integers $n_{1},\ldots,n_{k}\in\mathbb{Z}$
that satisfy $\sum_{j=1}^{k}n_{j}g_{j}=0$ are $n_{1}=\ldots=n_{k}=0$. The
_rank_ of an abelian group is the maximal size of an independent set.

Suppose that $\Gamma$ is an abelian group of rank $d$ and that $k\leq d$. A
set $C\subseteq\Gamma$ is called $k$-periodic if there exists a subgroup
$L\leq\Gamma$, with $\operatorname{rank}(L)\geq k$, such that $C+L=C$. In the
case that $k=d$ we will also say that $C$ is _periodic_ instead of
$d$-periodic. We say that a tile set $F\Subset\Gamma$ tiles $\Gamma$
periodically if there exits a periodic co-tile for $F$. If $F$ tiles $\Gamma$
but does not admit a periodic co-tile, then the set $F$ is called _aperiodic_.

Newman [New77] proved that any tiling of $\Gamma=\mathbb{Z}$ by a finite set
is periodic. Already for $\Gamma=\mathbb{Z}^{2}$, it is not difficult to find
tilings of $\Gamma$ by a finite set that are not even $1$-periodic. See [GT21,
§1.3] for some examples and a brief discussion. Still, it is natural to ask
for different generalizations of Newman’s theorem to higher-rank abelian
groups. It has been conjectured for some time that for any
$F\Subset\mathbb{Z}^{d}$, if there exists $A\subseteq\mathbb{Z}^{d}$ such that
$F\oplus A=\mathbb{Z}^{d}$ then there exists a periodic
$A^{\prime}\subseteq\mathbb{Z}^{d}$ such that $F\oplus
A^{\prime}=\mathbb{Z}^{d}$ [LW96], [GS87]. This conjecture became known as the
_periodic tiling conjecture_. The periodic tiling conjecture can be
interpreted as an attempt to generalize Newman’s theorem. The $\mathbb{Z}^{2}$
case of the periodic tiling conjecture was proved several years ago by
Bhattacharya [Bha20]. Other instances of the periodic tiling conjecture have
been proved, under additional assumptions [BN91, Khe22, Ken92, Sze98, WvL84].
The periodic tiling conjecture has recently been disproved for sufficiently
large $d$ by Greenfeld and Tao [GT22].

The recent refutation of the periodic tiling conjecture in high dimensions
motivates finding different generalizations of Newman’s theorem and of
Bhattacharya’s theorem that hold in arbitrary dimension $d$. In this paper, we
formulate and prove such generalizations. Our approach is to study the
structure of sets $A\subseteq\mathbb{Z}^{d}$ that satisfy

$F_{j}\oplus A=\mathbb{Z}^{d}\mbox{ for all }j=1,\ldots,k,$ (2)

for subsets $F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$. We refer to such an $A$
as a _joint co-tile_ for $F_{1},\ldots,F_{k}$.

In [GT23], sets $A\subseteq\mathbb{Z}^{d}$ satisfying (2) have been referred
to as solutions to the _system of tiling equations_. It is not difficult to
see that the existence of a joint co-tile for
$F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$ implies that
$|F_{1}|=|F_{2}|=\ldots=|F_{k}|$ (see Proposition 2.5).

Observe that whenever $A\subseteq\mathbb{Z}^{d}$ is a co-tile for
$F\Subset\mathbb{Z}^{d}$, for every $k$ there exists tiles
$F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$ admitting $A$ as a joint co-tile.
For instance, for every $v_{1},\ldots,v_{k}\in\mathbb{Z}^{d}$, the set $A$ is
a co-tile for $F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$, where
$F_{i}=F+v_{i}$, $i=1,\ldots,k$. Furthermore, by the Dilation lemma [GT22,
Lemma 3.1] (see also Lemma 3.2 below) for any $F\Subset\mathbb{Z}^{d}$, and
any $k\in\mathbb{N}$ there exists $r_{1},\ldots,r_{k}\in\mathbb{N}$, such that
any co-tile of $F$ is also a co-tile for $F_{1},\ldots,F_{k}$, where
$F_{i}:=r_{i}F=\\{r_{i}f\leavevmode\nobreak\ :\leavevmode\nobreak\ f\in F\\}$.
Thus, in general, joint co-tiles for $k$-tuples of tile $F_{1},\ldots,F_{k}$
have no more structure than co-tiles for a single tile $F$. However, it turns
out that additional structure on a $A\subset\mathbb{Z}^{d}$ can be concluded
from the fact that it is joint co-tile for $k$ tiles that are “sufficiently
different”, in a natural sense that in particular excludes the stations where
these $k$ tiles cannot be obtained from a single tile by translations and
dilations.

As with ordinary systems of linear equations, it makes sense to introduce a
notion of independence in this setup. For $F\Subset\mathbb{Z}^{d}$ we denote

$F^{*}:=F\setminus\\{0\\}.$

We say that $(F_{1},\ldots,F_{k})$ is an _independent tuple_ of tiles (or _$k$
independent tiles_) if each $F_{j}$ is a finite subset of $\mathbb{Z}^{d}$,
with $0\in F_{j}$, and for every choice of $v_{1}\in F_{1}^{*},\ldots,v_{k}\in
F_{k}^{*}$, the $k$-tuple $(v_{1},\ldots,v_{k})$ is independent (equivalently
here, linearly independent vectors over $\mathbb{Q}$, or similarly over
$\mathbb{R}$ or $\mathbb{C}$), see Figure 1. Notice that if
$(F_{1},\ldots,F_{k})$ is an independent tuple of tiles then $k\leq d$.

Figure 1. Here $F_{1},F_{2},F_{3}\subset\mathbb{Z}^{2}$ and the lower point in
all three of them is $(0,0)$. Each one of the pairs $(F_{1},F_{2})$ and
$(F_{1},F_{3})$ is independent, but the pair $(F_{2},F_{3})$ is not. Also note
that if the points in each of the sets lay on the lines $\\{y=0\\}$,
$\\{y=1\\}$ and $\\{y=2\\}$, then $A=\mathbb{Z}\times 3\mathbb{Z}$ is a joint
co-tile for $F_{1},F_{2},F_{3}$.

Building on methods developed in [Bha20], [GT21] and earlier work, we prove
the following:

######  Theorem 1.1.

For every $1\leq k\leq d$, the indicator function of any joint co-tile for $k$
independent tiles in $\mathbb{Z}^{d}$ is equal, to a sum of $[0,1]$-valued
$k$-periodic functions plus an integer constant.

The case $k=1$ of Theorem 1.1 was proven in [GT21]. As a direct consequence of
Theorem 1.1, we obtain the following multidimensional generalization of
Newman’s result:

######  Theorem 1.2.

For any independent tuple of tiles in $\mathbb{Z}^{d}$, the set of joint co-
tiles is finite. In particular, any joint co-tile for $d$ independent tiles in
$\mathbb{Z}^{d}$ is $d$-periodic. Furthermore, if $(F_{1},\ldots,F_{d})$ is an
independent tuple of tiles in $\mathbb{Z}^{d}$ and
$f:\mathbb{Z}^{d}\to\mathbb{Z}$ is a bounded function that satisfies
$\mathbf{1}_{F_{i}}*f=1$ for every $1\leq i\leq d$, then $f$ is $d$-periodic.

We discuss further generalizations of Newman’s theorem in Section 4 and
particularly to groups of the form $\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$
in Proposition 4.6.

We say that a set $A\subseteq\mathbb{Z}^{d}$ is _piecewise $k$-periodic_ if
there exist $A_{1},\ldots,A_{r}\subset\mathbb{Z}^{d}$ such that
$A=\biguplus_{j=1}^{r}A_{j}$ and each $A_{j}$ is $k$-periodic. Note that
[Bha20], [GT21] and [Khe22] used _weakly periodic_ for piecewise 1-periodic.
In [GT21] it was shown that any $A\subseteq\mathbb{Z}^{2}$ satisfying $F\oplus
A=\mathbb{Z}^{2}$ is piecewise $1$-periodic, whereas in [Bha20] it was shown
that almost every solution to $F\oplus A=\mathbb{Z}^{2}$ is piecewise
$1$-periodic, with respect to any invariant measure on the space of solutions.
The apriori weaker “almost everywhere” result sufficed to prove the
$\mathbb{Z}^{2}$ periodic tiling conjecture. The following result shows that
the existence of piecewise $(d-1)$-periodic joint co-tiles implies the
existence of $d$-periodic joint co-tiles. For $k=1$ and $d=2$ it coincides
with the results in [Bha20], [GT21], deducing $2$-periodicity from piecewise
$1$-periodicity.

######  Theorem 1.3.

Let $k$ and $d$ be positive integers and let
$F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$. If $F_{1},\ldots,F_{k}$ admit a
piecewise $(d-1)$-periodic joint co-tile, then they admit a $d$-period joint
co-tile.

We now define an additional condition on a tuple of tiles, that is needed for
the formulation of a certain generalization of Bhattacharya’s and Greenfeld-
Tao’s theorems to $d>2$:

######  Definition 1.4.

Let $(F_{1},\ldots,F_{d-1})$ be a tuple of tiles in $\mathbb{Z}^{d}$, $d\geq
2$. We say that $(F_{1},\ldots,F_{d-1})$ has _property $(\star)$_ if it is an
independent tuple and for every
$(v_{1},\ldots,v_{d-1}),(w_{1},\ldots,w_{d-1})\in F_{1}^{*}\times\ldots\times
F_{d-1}^{*}$ such that

$\operatorname{span}(v_{1},\ldots,v_{d-1})=\operatorname{span}(w_{1},\ldots,w_{d-1}),$

we have $v_{i}=w_{i}$ for all $1\leq i\leq d-2$.

######  Example 1.5.

Consider the tiles

$F_{1}=\\{(0,0,0),(1,0,0),(0,1,0),(1,1,0)\\}\mbox{ and
}F_{2}=\\{(0,0,0),(1,0,1),(0,1,1),(1,1,1)\\}.$

Then $(F_{1},F_{2})$ has property $(\star)$. Indeed it is easy to see that
$(F_{1},F_{2})$ is an independent tuple of tiles in $\mathbb{Z}^{3}$, and for
any $v_{1}\in F_{1}^{*}$ and $v_{2}\in F_{2}^{*}$ the intersection of
$\operatorname{span}(v_{1},v_{2})$ with the plane
$V=\\{(a,b,0)\leavevmode\nobreak\ :\leavevmode\nobreak\ a,b\in\mathbb{R}\\}$
is equal to $\operatorname{span}(v_{1})$. Also, for $A=2\mathbb{Z}\times
2\mathbb{Z}\times\mathbb{Z}$ we have $F_{1}\oplus A=F_{2}\oplus
A=\mathbb{Z}^{3}$, so $A$ is a (periodic) joint co-tile.

######  Theorem 1.6.

Let $(F_{1},\ldots,F_{d-1})$ be a tuple of tiles in $\mathbb{Z}^{d}$ that has
property $(\star)$. Then any joint co-tile for $F_{1},\ldots,F_{d-1}$ is
piecewise $(d-1)$-periodic.

The next statement follows immediately from Theorem 1.6 together with Theorem
1.3.

######  Corollary 1.7.

Let $(F_{1},\ldots,F_{d-1})$ be a tuple of tiles in $\mathbb{Z}^{d}$ that has
property $(\star)$. If $(F_{1},\ldots,F_{d-1})$ admits a joint co-tile then it
admits a $d$-periodic joint co-tile.

Note that for $d=2$, property $(\star)$ is vacuous, hence Theorem 1.6 reduces
to the statement that any co-tile for a finite subset of $\mathbb{Z}^{2}$ is
piecewise $1$-periodic (Greenfeld-Tao’s theorem) and Corollary 1.7 reduces to
the statement that any finite subset of $\mathbb{Z}^{2}$ that admits a co-tile
also admits a periodic co-tile (Bhattacharya’s theorem). Hence for $d\geq 3$,
it is natural to ask whether property $(\star)$ is a necessary condition for
the existence of a periodic joint co-tile of $(d-1)$ tiles of
$\mathbb{Z}^{d}$.

We note a particular application of our methods, although not directly related
to our main results:

######  Theorem 1.8.

Suppose that $\mathbb{Z}^{d}$ decomposes into $(d-1)$-periodic subsets
$A_{1},\ldots,A_{r}\subset\mathbb{Z}^{d}$, where at least one of them is not
$d$-periodic. Then there exists $\Gamma\leq\mathbb{Z}^{d}$ of rank $d-1$ so
that $A_{j}+\Gamma=A_{j}$ for all $1\leq j\leq r$.

On the other hand, we obtain the following converse results for Theorem 1.2
and Corollary 1.7.

######  Theorem 1.9.

Suppose that $\\{0\\}\subsetneqq F\Subset\mathbb{Z}^{d}$ admits a periodic
tiling $A\subseteq\mathbb{Z}^{d}$, then there exist
$F_{1},\ldots,F_{d-1}\Subset\mathbb{Z}^{d}$ with $0\in F_{j}$ and $F_{j}\oplus
A=\mathbb{Z}^{d}$ for all $1\leq j\leq d$, such that

  1. (a)

$(F_{1},\ldots,F_{d-1},F)$ is a $d$-tuple of independent tiles.

  2. (b)

$(F_{1},\ldots,F_{d-2},F)$ has property $(\star)$.

Combining Corollary 1.7 and Theorem 1.9 (b) we obtain the following:

######  Corollary 1.10.

A finite set $\\{0\\}\subsetneqq F\Subset\mathbb{Z}^{d}$ tiles
$\mathbb{Z}^{d}$ periodically if and only if there exists
$F_{1},\ldots,F_{d-2}\Subset\mathbb{Z}^{d}$ and $A\subset\mathbb{Z}^{d}$ such
that $(F_{1},\ldots,F_{d-2},F)$ has property $(\star)$, $F\oplus
A=\mathbb{Z}^{d}$ and $F_{j}\oplus A=\mathbb{Z}^{d}$ for all $1\leq j\leq
d-2$. In particular, $F\Subset\mathbb{Z}^{3}$ tiles $\mathbb{Z}^{3}$
periodically if and only if there is another co-tile $F^{\prime}$ for $A$ such
that $(F^{\prime},F)$ has property $(\star)$.

The structure of the paper is as follows. Section 2 contains basic background
and definitions. In Section 3 we prove Theorem 3.1, a periodic decomposition
theorem for joint co-tiles, which is a refinement of Theorem 1.1. From Theorem
3.1, we directly deduce Theorem 1.1 and Theorem 1.2. In Section 4, we discuss
generalizations of Theorem 3.1, Theorem 1.1 and Theorem 1.2 to countable
abelian groups. This allows us to extend Newman’s Theorem to tilings of the
group $\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$. In Section 5 we prove
Theorem 1.6, which asserts that property $(\star)$ implies piecewise
$(d-1)$-periodicity of joint co-tiles. Then in Section 6 we prove Theorem 1.8
and deduce Theorem 1.3. Section 7 is dedicated to the proof of Theorem 1.9.
Finally, Section 8 contains concluding remarks and related questions.

Acknowledgement. We thank Itay Londner for discussions about tilings in cyclic
groups and the Coven-Meyerowitz conditions. We thank Ilya Tyomkin for telling
us about the relation between the dimension of the common complex zeros for a
system of multivariate polynomials with integer coefficients, the tropical
variety, and the associated Bieri-Groves set. We also thank Rachel Greenfeld
and Terence Tao for their helpful communications.

##  2\. Preliminaries

A function $f:\mathbb{Z}^{d}\to\mathbb{R}$ is called $L$-periodic, where
$L\leq\mathbb{Z}^{d}$, if for every $x\in\mathbb{Z}^{d}$ and $v\in L$ we have
$f(x+v)=f(x)$. Recall that a set $A\subseteq\mathbb{Z}^{d}$ is _piecewise
$k$-periodic_ if $A$ is the disjoint union of $k$-periodic sets.

######  Definition 2.1.

Let $\Gamma_{1},\Gamma_{2}$ be abelian groups. For $f:\Gamma_{1}\to\Gamma_{2}$
and $v\in\Gamma_{1}$, we define the discrete derivative of $f$ in direction
$v$, $D_{v}f:\Gamma_{1}\to\Gamma_{2}$, by

$D_{v}f(w):=f(w)-f(w-v).$

A function $P:\Gamma_{1}\to\Gamma_{2}$ is called _a polynomial map of degree
at most $r$_ if

$\leavevmode\nobreak\ \forall\,v_{1},\ldots,v_{r+1}\in\Gamma_{1}:\quad
D_{v_{1}}\ldots D_{v_{r+1}}P=0$

(where for consistency $P=0$, is a polynomial of degree $-1$). Given a
subgroup $\Gamma_{3}<\Gamma_{1}$, one says that $P:\Gamma_{1}\to\Gamma_{2}$ is
a _polynomial map of degree at most $r$ with respect to $\Gamma_{3}$_ if

$\leavevmode\nobreak\ \forall\,v_{1},\ldots,v_{r+1}\in\Gamma_{3}:\quad
D_{v_{1}}\ldots D_{v_{r+1}}P=0.$

The following basic facts about polynomials will be useful for us. Lemma 2.2
below is due to Leibman [Lei02, Prop. 1.21]. We include a short proof for the
reader’s convenience.

######  Lemma 2.2.

Let $P:\mathbb{Z}^{d}\to\mathbb{R}$ be a polynomial map with respect to a
finite index subgroup $L\leq\mathbb{Z}^{d}$, which is bounded, then $P$ is
constant on cosets of $L$.

###### Proof.

Let $r\in\mathbb{N}$ denote the degree of $P$, as a polynomial with respect to
$L$. It is clear from Definition 2.1 that if $r$ is equal to $0$, then the
restriction of $P$ to each coset of $L$ is a constant. Similarly, if the
degree of $P$ is equal to $1$, then the restriction of $P$ to each coset of
$L$ is a constant plus a non-trivial homomorphism (see e.g. [Lei02]). For
contradiction, we may assume that $r\geq 1$. Observe that since $P$ is bounded
and for every $v\in L$ we have $D_{v}P\subseteq
P(\mathbb{Z}^{d})-P(\mathbb{Z}^{d})$, thus $D_{v}P$ is bounded. Therefore, for
every $v_{1},\ldots,v_{r-1}\in L$ the function $D_{v_{1}}\ldots D_{v_{r-1}}P$
is a bounded polynomial map of degree exactly one, with respect to $L$. But
non-trivial homomorphisms into $\mathbb{R}$ are unbounded, a contradiction. ∎

######  Definition 2.3.

We say that a bounded function $f:\mathbb{Z}^{d}\to\mathbb{R}$ has mean $m$ if

$\lim_{n\to\infty}\frac{1}{|B_{n}|}\sum_{v\in B_{n}}f(v)=m,$ (3)

where $B_{n}=\\{-n,\ldots,n\\}^{d}$.

One says that $f:\mathbb{Z}^{d}\to\mathbb{R}/\mathbb{Z}$ is equidistributed in
$\mathbb{R}/\mathbb{Z}$ if

$\lim_{n\to\infty}\frac{1}{|B_{n}|}\sum_{v\in
B_{n}}g(f(v))=\int_{0}^{1}g(x)dx$ (4)

holds for every continuous function $g:\mathbb{R}/\mathbb{Z}\to\mathbb{R}$,
where we identify $g:\mathbb{R}/\mathbb{Z}\to\mathbb{R}$ with
$g:\mathbb{R}\to\mathbb{R}$ such that $g(x+1)=x$ for all $x\in\mathbb{R}$.

We will use the following version of Weyl’s equidistribution theorem for
polynomials in several variables [Wey16, Theorem 20]. See also [Tao12, Chapter
1.1] and [Yif22, Theorem 1.2].

######  Theorem 2.4 (Weyl’s equidistribution theorem for polynomials in
several variables).

Let $P:\mathbb{Z}^{d}\to\mathbb{R}/\mathbb{Z}$ be a polynomial map with
respect to a finite index subgroup $\Gamma$ of $\mathbb{Z}^{d}$. Then on every
coset $v+\Gamma$ of $\Gamma$, the restriction of $P$ to $v+\Gamma$ is either
equidistributed in $\mathbb{R}/\mathbb{Z}$ or periodic.

We implicitly rely on the following basic observation (compare [Kol04, Lemma
1.1]).

######  Proposition 2.5.

Let $F\Subset\mathbb{Z}^{d}$. Suppose that $F\subset B_{n_{0}}$ for some
$n_{0}\in\mathbb{N}$ and that $f:\mathbb{Z}^{d}\to\mathbb{R}$ is a bounded
function satisfying $\mathbf{1}_{F}*f=1$. Denote by $C=|F|(\max f-\min f)$.
Then for every $n>n_{0}$ one has

$|B_{n-n_{0}}|-C\left|{B_{n+n_{0}}\setminus
B_{n-n_{0}}}\right|\leq|F|\sum_{w\in
B_{n}}f(w)\leq|B_{n-n_{0}}|+C\left|{B_{n+n_{0}}\setminus B_{n-n_{0}}}\right|,$
(5)

and thus the function $f$ has mean $\frac{1}{|F|}$. In particular, if
$F_{1},F_{2}\Subset\mathbb{Z}^{d}$ satisfy
$\mathbf{1}_{F_{1}}*f=\mathbf{1}_{F_{2}}*f=1$, then $|F_{1}|=|F_{2}|$.

###### Proof.

Pick $n_{0}\in\mathbb{N}$ such that $F\subset B_{n_{0}}$. Observe that
$\mathbf{1}_{F}*f=1$ implies that for every $n>n_{0}$ we have

$\mathbf{1}_{B_{n-n_{0}}}-C\cdot\mathbf{1}_{B_{n+n_{0}}\setminus
B_{n-n_{0}}}\leq\mathbf{1}_{F}*f|_{B_{n}}\leq\mathbf{1}_{B_{n-n_{0}}}+C\cdot\mathbf{1}_{B_{n+n_{0}}\setminus
B_{n-n_{0}}},$

where $f|_{B_{n}}$ denotes the restriction of $f$ to $B_{n}$. Taking the sum
of the values of these functions over all $z\in\mathbb{Z}^{d}$ implies that
(5) holds for every $n>n_{0}$. Since
$\lim_{n\to\infty}\frac{|B_{n-n_{0}}|}{|B_{n}|}=1$ and
$\lim_{n\to\infty}\frac{|B_{n+n_{0}}\setminus B_{n-n_{0}}|}{|B_{n}|}=0$,
dividing (5) by $\left|{F}\right|\cdot\left|{B_{n}}\right|$ and letting
$n\to\infty$ yields the assertion. ∎

######  Remark 2.6.

The mean of a function $f:\Gamma\to\mathbb{R}$ is defined similarly, using
(3), for any countable amenable group $\Gamma$, in which case $B_{n}$ is
replaced by a Følner sequence in $\Gamma$, and an analogue of Proposition 2.5
holds in this more general context as well. In Section 8, we implicitly apply
Proposition 2.5 for countable abelian groups $\Gamma$, which are in particular
amenable.

###  2.1. Shifts of finite type

The space of co-tiles for a given finite set $F\subset\mathbb{Z}^{d}$, or more
generally, the space of joint co-tiles for a given collection of sets, can
naturally be endued with the structure of a compact topological space on which
$\mathbb{Z}^{d}$ acts by homeomorphisms. Topological dynamical systems of this
kind are called _$\mathbb{Z}^{d}$ -subshifts_, more specifically _subshifts of
finite type_. We include here relevant terminology and basic facts from the
field of symbolic dynamics, particularly regarding shifts of finite type. We
refer to [LM95] for a comprehensive introduction to symbolic dynamics.

Let $\Sigma$ be a finite set (alphabet) and $\Gamma$ a finitely generated
abelian group. The set of functions from $\Gamma$ to $\Sigma$, denoted
$\Sigma^{\Gamma}$, is called _the full $\Gamma$-shift_. For
$x\in\Sigma^{\Gamma}$ and $v\in\Gamma$, we use $x_{v}$ to denote the value of
$x$ at $v$ (this is an element of $\Sigma$). Also for $x\in\Sigma^{\Gamma}$
and $v\in\Gamma$ we denote by $\sigma_{v}(x)\in\Sigma^{\Gamma}$ the _shift of
$x$ by $v$_, which is given by

$\sigma_{v}(x)_{w}=x_{v+w}.$

Endowing $\Sigma^{\Gamma}$ with the product topology, where the topology on
$\Sigma$ is the discrete topology, makes $\Sigma^{\Gamma}$ a compact
$\Gamma$-space. A closed, non-empty and $\Gamma$-invariant subset
$X\subseteq\Sigma^{\Gamma}$ is called a _$\Gamma$ -subshift_. For
$x\in\Sigma^{\Gamma}$, the _stabilizer of $x$_ is defined to be

$\operatorname{stab}(x)=\\{v\in\Gamma:\leavevmode\nobreak\
\sigma_{v}(x)=x\\},$

which is a (possibly trivial) subgroup of $\Gamma$. A point
$x\in\Sigma^{\Gamma}$ is called _$k$ -periodic_ if $\operatorname{stab}(x)$ is
a subgroup of rank $k$. When $\Gamma=\mathbb{Z}$, we say that
$x\in\Sigma^{\mathbb{Z}}$ is _periodic_ if it has a non-trivial stabilizer.

######  Definition 2.7.

A $\Gamma$-subshift $X\subseteq\Sigma^{\Gamma}$ is called _a subshift of
finite type (SFT)_ if there exists a finite set $W\subset\Gamma$ and a set
$\mathcal{F}\subseteq\Sigma^{W}$ such that

$X=\left\\{x\in\Sigma^{\Gamma}:\leavevmode\nobreak\ \forall
v\in\Gamma,\leavevmode\nobreak\
\sigma_{v}(x)|_{W}\not\in\mathcal{F}\right\\}.$

For every $F\Subset\mathbb{Z}^{d}$ the space of co-tiles for $F$ is a subshift
of finite type, under the natural identification of the space of co-tiles for
$F$ with

$X_{F}:=\left\\{x\in\\{0,1\\}^{\mathbb{Z}^{d}}:\leavevmode\nobreak\
\mathbf{1}_{F}*x=1\right\\}.$

To see that $X_{F}$ is indeed an SFT, take $W=-F$ and

$\mathcal{F}=\left\\{p\in\\{0,1\\}^{W}\leavevmode\nobreak\
:\leavevmode\nobreak\ \sum_{w\in W}p(w)\neq 1\right\\},$

and then

$X_{F}=\left\\{x\in\\{0,1\\}^{\mathbb{Z}^{d}}\leavevmode\nobreak\
:\leavevmode\nobreak\ \forall v\in\mathbb{Z}^{d},\leavevmode\nobreak\
\sigma_{v}(x)|_{W}\not\in\mathcal{F}\right\\}.$

Since a non-empty intersection of SFTs is also an SFT, it follows that the
space of joint co-tiles for a collection of tiles is an SFT (unless it is
empty).

The following simple result is based on a pigeonhole argument. The proof is
well-known and standard, see for instance [LM95, Exercise 2.2.10]. We include
a proof for completeness.

######  Lemma 2.8.

Every $\mathbb{Z}$-subshift of finite type admits a periodic point.

###### Proof.

Let $X\subseteq\Sigma^{\mathbb{Z}}$ be a $\mathbb{Z}$-subshift of finite type,
where $\Sigma$ is a finite set. Then by definition, there exists a finite set
$W\Subset\mathbb{Z}$ and $\mathcal{F}\subseteq\Sigma^{W}$ such that

$X=\left\\{x\in\Sigma^{\mathbb{Z}}:\leavevmode\nobreak\ \forall
v\in\mathbb{Z},\leavevmode\nobreak\
\sigma_{v}(x)|_{W}\not\in\mathcal{F}\right\\},$

and $X\neq\emptyset$. Fix $x\in X$, and let $N\in\mathbb{N}$ be an integer
bigger than $\max(W)-\min(W)$. Since the set $\Sigma^{\\{1,\ldots,N\\}}$ is
finite, by the pigeonhole principle there exist integers $0\leq
i<j\leq|\Sigma|^{N}$ such that

$x|_{\\{i,\ldots,i+N-1\\}}=x|_{\\{j,\ldots,j+N-1\\}}.$

Let $p=j-i$ and define $\hat{x}\in\Sigma^{\mathbb{Z}}$ by

$\hat{x}_{n}=x_{i+(n\mod p)}.$

Then $\hat{x}$ is a periodic point, and for every $n\in\mathbb{Z}$ there
exists $t\in\\{i,\ldots,j-1\\}$ such that $\hat{x}|_{W+n}=x|_{W+t}$. Hence,
$\hat{x}\in X$, which proves that $X$ admits a periodic point. ∎

We recall the following result in multidimensional symbolic dynamics.

######  Lemma 2.9.

Let $\Gamma$ be a finitely generated abelian group, $\Gamma_{0}\leq\Gamma$ a
subgroup, and $X\subseteq\Sigma^{\Gamma}$ a $\Gamma$-subshift. Let

$X_{\Gamma_{0}}:=\left\\{x\in X\leavevmode\nobreak\
:\Gamma_{0}\leq\operatorname{stab}(x)\right\\}.$ (6)

If $X_{\Gamma_{0}}\neq\emptyset$ then it is a $\Gamma$-subshift. Furthermore,
if $X$ is a subshift of finite type then $X_{\Gamma_{0}}$ is also a subshift
of finite type.

###### Proof.

First, we show that $X_{\Gamma_{0}}$ is a subshift. Since $\Gamma$ is abelian,
for every $v\in\Gamma$, $v_{0}\in\Gamma_{0}$ and $y\in X_{\Gamma_{0}}$ we have

$\sigma_{v_{0}}(\sigma_{v}(y))=\sigma_{v}(\sigma_{v_{0}}(y))=\sigma_{v}(y).$

This shows $\sigma_{v}(y)\in X_{\Gamma_{0}}$ for all $v\in\Gamma$ hence
$X_{\Gamma_{0}}$ is $\Gamma$-invariant. To see that $X_{\Gamma_{0}}$ is a
closed subset of $\Sigma^{\Gamma}$, consider a sequence
$(y_{n})_{n\in\mathbb{N}}\in X_{\Gamma_{0}}$ such that

$\underset{n\rightarrow\infty}{\mathrm{lim}}\,\,y_{n}=y\in\Sigma^{\Gamma}$

in the product topology. Since each $y_{n}\in X_{\Gamma_{0}}\subseteq X$ and
$X$ is a closed subset of $\Sigma^{\Gamma}$, we get $y\in X$. Note that for
any $v_{0}\in\Gamma_{0}$,

$\sigma_{v_{0}}(y)=\sigma_{v_{0}}\,\,\big{(}\underset{n\rightarrow\infty}{\mathrm{lim}}y_{n}\big{)}=\underset{n\rightarrow\infty}{\mathrm{lim}}(\sigma_{v_{0}}(y_{n}))=\underset{n\rightarrow\infty}{\mathrm{lim}}(y_{n})=y,$

which shows $y\in X_{\Gamma_{0}}$ and hence $X_{\Gamma_{0}}$ is a subshift.
Now assuming that $X$ is an SFT we show that $X_{\Gamma_{0}}$ is also an SFT.
Observe that $X_{\Gamma_{0}}=X\cap Y$ where

$Y=\\{x\in\Sigma^{\Gamma}\leavevmode\nobreak\ :\leavevmode\nobreak\
\Gamma_{0}\leq\operatorname{stab}(x)\\}.$

Since $\Gamma_{0}$ is a subgroup of a finitely generated abelian group it is
also finitely generated. Let $\\{\gamma_{1},\ldots,\gamma_{r}\\}$ be a finite
generating set for $\Gamma_{0}$. Then

$Y=\bigcap_{i=1}^{r}\\{x\in\Sigma^{\Gamma}\leavevmode\nobreak\
:\leavevmode\nobreak\ \forall v\in\Gamma,\leavevmode\nobreak\
x_{v+\gamma_{i}}=x_{v}\\}.$

To see that $Y$ is an SFT, let $W=\\{0,\gamma_{1},\ldots,\gamma_{r}\\}$ and

$\mathcal{F}=\left\\{w\in\Sigma^{W}:\leavevmode\nobreak\ \exists 1\leq i\leq
r\mbox{ s.t. }w_{0}\neq w_{\gamma_{i}}\right\\}.$

Then

$Y=\left\\{x\in\Sigma^{\Gamma}\leavevmode\nobreak\ :\leavevmode\nobreak\
\forall v\in\Gamma,\leavevmode\nobreak\
\sigma_{v}(x)|_{W}\notin\mathcal{F}\right\\}.$

Hence $Y$ is an SFT, which completes the argument.

∎

From Lemma 2.9 we deduce the following conclusion:

######  Lemma 2.10.

Let $\Gamma$ be a finitely generated abelian group of rank $d$. If
$X\subseteq\Sigma^{\Gamma}$ is a $\Gamma$-subshift of finite type that admits
a $(d-1)$-periodic point then it admits a $d$-periodic point.

###### Proof.

Suppose $X\subseteq\Sigma^{\Gamma}$ is a $\Gamma$-subshift of finite type that
admits a $(d-1)$-periodic point, namely a point $z\in X$ and a subgroup
$\Gamma_{0}\leq\Gamma$ of rank $d-1$ such that
$\operatorname{stab}(z)=\Gamma_{0}$. Let $X_{\Gamma_{0}}$ be given by (6).
Then $X_{\Gamma_{0}}$ is non-empty, and by Lemma 2.9 it is a subshift of
finite type. Because $\operatorname{rank}(\Gamma_{0})=d-1$, it follows that
$\operatorname{rank}(\Gamma/\Gamma_{0})=1$. Let $v\in\Gamma$ be a vector such
that $k\cdot v\not\in\Gamma_{0}$ for all $k\in\mathbb{N}$. Then
$\Gamma_{0}\oplus\mathbb{Z}v$ is a finite index subgroup of $\Gamma$. Let
$D\subseteq\Gamma$ be a fundamental domain for $\Gamma_{0}\oplus\mathbb{Z}v$,
namely a finite set such that $\Gamma_{0}\oplus\mathbb{Z}v\oplus D=\Gamma$.
Because $D\oplus\mathbb{Z}v$ is a fundamental domain for $\Gamma_{0}$ in
$\Gamma$, it follows that the restriction map
$\rho:X_{\Gamma_{0}}\to\Sigma^{D\oplus\mathbb{Z}v}$ is injective, where $\rho$
is given by $\rho(x)=x\mid_{D\oplus\mathbb{Z}v}$.

Indeed, the inverse $\rho^{-1}:\rho(X_{\Gamma_{0}})\to X_{\Gamma_{0}}$ is
given by $\rho^{-1}(\tilde{x})_{u}=(\tilde{x})_{u^{\prime}}$ for $u\in\Gamma$,
where $u^{\prime}$ is the unique element in $(D\oplus\mathbb{Z}v)$ that
satisfies $u-u^{\prime}\in\Gamma_{0}$. Using the natural identification
$\Sigma^{D\oplus\mathbb{Z}v}\cong(\Sigma^{D})^{\mathbb{Z}}$, we can view
$\rho(X_{\Gamma_{0}})$ as a subset of $(\Sigma^{D})^{\mathbb{Z}}$, which we
denote by $\tilde{X}$.

Let us show that $\tilde{X}$ is a $\mathbb{Z}$-subshift of finite type.
Because $X$ is a $\Gamma$-subshift of finite type, there exists a finite set
$W\subset\Gamma$ and $\mathcal{F}\subset\Sigma^{W}$ such that $X_{\Gamma_{0}}$
is equal to the set of $x\in\Sigma^{\Gamma}$ satisfying $\sigma_{v}(x)=x$ and
$\sigma_{v}(x)\mid_{W}\not\in\mathcal{F}$ for all $v\in\Gamma_{0}$. We can
assume without loss of generality that $W$ is a subset of $\mathbb{Z}v\oplus
D$, because $\mathbb{Z}v\oplus D$ is a fundamental domain for $\Gamma_{0}$.
Let $\tilde{W}=\\{n\in\mathbb{Z}:\leavevmode\nobreak\ (nv+D)\cap
W\neq\emptyset\\}$. Then $W=\biguplus_{n\tilde{W}}(W\cap(nv+D))$. Thus, there
is a natural bijection between $\Sigma^{W}$ and $(\Sigma^{D})^{\tilde{W}}$.
Let $\tilde{\mathcal{F}}$ denote the image of $\mathcal{F}$ under this
bijection. Then it follows directly that

$\tilde{X}=\left\\{x\in(\Sigma^{D})^{\mathbb{Z}}:\leavevmode\nobreak\ \forall
v\in\mathbb{Z}:\leavevmode\nobreak\
\sigma_{v}(x)\mid_{\tilde{W}}\not\in\tilde{\mathcal{F}}\right\\}.$

This proves that $\tilde{X}$ is indeed a $\mathbb{Z}$-subshift of finite type.

Since $\tilde{X}$ is a $\mathbb{Z}$-subshift of finite type, by Lemma 2.8
there exists a periodic point $\tilde{z}$ in $\tilde{X}$. Let
$x=\rho^{-1}(\tilde{z})$, then $x\in X$ is a $d$-periodic point. ∎

######  Remark 2.11.

The simple argument behind Lemma 2.10 has been applied in [Bha20] for the case
$\Gamma=\mathbb{Z}^{2}$, and also in a number of older references. See for
instance [War94] and [Fri97]. We had difficulties finding a precise reference
to the statement of Lemma 2.10 in full generality.

##  3\. The periodic decomposition theorem

The following theorem asserts a certain decomposition for a joint co-tile of
$k$-tuple of tiles in $\mathbb{Z}^{d}$. The case where $k=1$ and $f$ is
$\\{0,1\\}$-valued essentially coincides with [GT21, Theorem 1.7], which is
closely related to [Bha20, Theorem 3.3]. In the particular case that the tuple
of tiles is independent, Theorem 1.1 is a direct consequence. Namely, the
indicator function of any joint co-tile of $k$ independent tiles is a sum of
$k$-periodic functions, each taking values in $[0,1]$. The goal of this
section is to prove the periodic decomposition theorem for joint co-tiles and
to deduce Theorem 1.1 and Theorem 1.2.

######  Theorem 3.1 (Periodic decomposition theorem).

Let $F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$, with $0\in F_{i}$ for all
$1\leq i\leq k$, and let $f:\mathbb{Z}^{d}\to\mathbb{Z}$ be a bounded function
that satisfies $\mathbf{1}_{F_{i}}*f=1$ for all $1\leq i\leq k$. We denote by
$S:=|F_{1}|=\ldots=|F_{k}|$ (see Proposition 2.5). Then for every $1\leq i\leq
k$ and every $(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times F_{i}^{*}$
there exists a function $\phi_{v_{1},\ldots,v_{i}}:\mathbb{Z}^{d}\to[\min
f,\max f]$ with the following properties:

  1. (a)

For $i<k$ we have

$\phi_{v_{1},\ldots,v_{i}}=1-\sum_{v_{i+1}\in
F_{i+1}^{*}}\phi_{v_{1},\ldots,v_{i},v_{i+1}}.$

  2. (b)

$f=(-1)^{i}\sum_{(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times
F_{i}^{*}}\phi_{v_{1},\ldots,v_{i}}+\sum_{j=1}^{i}(-(S-1))^{j-1}.$

  3. (c)

Let $q$ denote the product of all primes less than or equal to $(\max f-\min
f)S$, then

$\left(\mathbb{Z}qv_{1}+\ldots+\mathbb{Z}qv_{i}\right)\leq\operatorname{stab}(\phi_{v_{1},\ldots,v_{i}}),$

  4. (d)

$1_{F_{j}}*\phi_{v_{1},\ldots,v_{i}}=1$ for all $1\leq j\leq k$. In
particular, $\phi_{v_{1},\ldots,v_{i}}$ has mean $1/S$.

There are various extensions of Theorem 3.1. Some of these generalizations
have further applications. For the sake of readability, we do not state the
most general form and instead indicate certain generalizations in the
following sections, at the expense of some repetition.

The proof of Theorem 3.1 relies on Lemma 3.2 below. Various versions of this
lemma, which is referred to as the dilation lemma, have been proved e.g. in
[GT21, Lemma 3.1], [Bha20, Proposition 3.1] for $\Gamma=\mathbb{Z}^{d}$,
$d\geq 1$. We also refer our readers to [Tij95, Theorem 1] where this lemma is
proved for integers. The proof is based on some elementary commutative algebra
and it easily extends to countable abelian groups. For the sake of self-
containment, we include a sketch of the proof below. The proof below is nearly
identical to [GT21, Lemma 3.1], except that we apply the assumption that $r$
is co-prime to the order of torsion elements directly before eq. 7.

######  Lemma 3.2 (Dilation lemma).

Let $\Gamma$ be a countable abelian group. Let $0\in F\Subset\Gamma$,
$\ell\in\mathbb{N}$ and $f:\Gamma\to\mathbb{Z}$ a bounded function satisfying

$\mathbf{1}_{F}*f=\ell.$

Let $q_{1}$ be the product of all primes less than or equal to $(\max f-\min
f)|F|$, let $q_{2}$ be the product of all the orders of the torsion elements
in $(F-F)$, and set $q=q_{1}q_{2}$. Then

$\mathbf{1}_{rF}*f=\ell,$

for all $r\in\mathbb{N}$ such that $r=1\mod q$.

###### Proof.

We use the notation $f^{*p}=\underbrace{f*\ldots*f}_{\times p}$. For any prime
$p$ we have

$\mathbf{1}_{F}^{*p}=\left(\sum_{v\in F}\delta_{v}\right)^{*p}=\sum_{v\in
F}\delta_{v}^{*p}\mod p,$

where the last equality holds by the Frobenius identity
$(f+g)^{*p}=f^{*p}+g^{*p}\mod p$. For integers $p$ that are co-prime to
$q_{2}$ we have that $p(v_{1}-v_{2})\neq 0$ for any $v_{1}\neq v_{2}\in F$, so
the function $v\mapsto pv$ is injective on $F$. Thus:

$\sum_{v\in F}\delta_{v}^{*p}=\sum_{v\in F}\delta_{pv}=\mathbf{1}_{pF}.$ (7)

Now convolving both sides of $\mathbf{1}_{F}*f=\ell$ by
$\mathbf{1}_{F}^{*(p-1)}$ yields $\mathbf{1}_{F}^{*p}*f=\ell|F|^{p-1}$.
Combining the above, for primes $p$ that are co-prime to $q_{2}$ we obtain
$\mathbf{1}_{pF}*f=\ell|F|^{p-1}\mod p$. If additionally $p$ is co-prime to
$|F|$ by Fermat little theorem $|F|^{p-1}=1\mod p$, thus

$\mathbf{1}_{pF}*f=\ell\mod p.$

Note that both $\mathbf{1}_{F}*f$ and $\mathbf{1}_{pF}*f$ take values in
$[|F|\min f,|F|\max f]$. Recall that $\ell=\mathbf{1}_{F}*f$, so
$\ell\in[|F|\min f,|F|\max f]$. Thus, for $p$ that is also greater than the
size of that interval, the above equality holds without the $\mod p$, namely
$\mathbf{1}_{pF}*f=\ell$. Finally, for $r=1\mod q$, $r$ is a product of primes
that satisfy the conditions above, and the result follows by iterating the
equation $\mathbf{1}_{pF}*f=\ell$. ∎

###### Proof of Theorem 3.1.

For $1\leq i\leq k$, $(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times
F_{i}^{*}$ and $N\in\mathbb{N}$ denote:

$\phi^{(N)}_{v_{1},\ldots,v_{i}}:=\dfrac{1}{N^{i}}\sum_{n_{1},\ldots,n_{i}=1}^{N}\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}*f.$
(8)

Let $q$ be the product of all primes less than or equal to $(\max f-\min f)S$.
By applying Lemma 3.2 for $F_{j}$ with $\Gamma=\mathbb{Z}^{d}$ and $\ell=1$ we
get $\mathbf{1}_{rF_{j}}*f=1$ for every $r\in q\mathbb{N}+1$. Since $0\in
F_{j}$ we obtain

$f=1-\sum_{v\in F^{*}_{j}}\delta_{rv}*f\mbox{ for every }1\leq j\leq k.$

For every $N\in\mathbb{N}$, setting $r=1+nq$ for $n\in\\{1,\ldots,N\\}$ and
taking average we conclude that for every $1\leq j\leq k$ we have

$f=1-\sum_{v\in F^{*}_{j}}\dfrac{1}{N}\sum_{n=1}^{N}\delta_{(1+nq)v}*f.$ (9)

Since $\phi_{v_{1}}^{(N)}=\frac{1}{N}\sum_{n=1}^{N}\delta_{(1+nq)v_{1}}*f$
this gives (with $j=1$):

$f=1-\sum_{v_{1}\in F^{*}_{1}}\phi^{(N)}_{v_{1}}.$ (10)

For $1\leq i<k$, choose any $(v_{1},\ldots,v_{i})\in
F_{1}^{*}\times\ldots\times F_{i}^{*}$ and $1\leq n_{1},\ldots,n_{i}\leq N$.
Setting $j=i+1$ in (9) and convolving both sides of the equation by
$\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}$ we obtain

$\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}*f=1-\sum_{v_{i+1}\in
F^{*}_{i+1}}\dfrac{1}{N}\sum_{n_{i+1}=1}^{N}\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}+(1+n_{i+1}q)v_{i+1}}*f.$

By averaging over $1\leq n_{1},\ldots,n_{i}\leq N$ and applying the definition
in (8) we obtain that

$\phi^{(N)}_{v_{1},\ldots,v_{i}}=1-\sum_{v_{i+1}\in
F^{*}_{i+1}}\dfrac{1}{N^{i+1}}\sum_{n_{1},\ldots,n_{i+1}=1}^{N}\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i+1}q)v_{i+1}}*f=1-\sum_{v_{i+1}\in
F^{*}_{i+1}}\phi^{(N)}_{v_{1},\ldots,v_{i+1}}.$ (11)

Since $|F^{*}_{i}|=S-1$ for $1\leq i\leq k$, using (10), (11) and an inductive
argument we obtain that for every $N\in\mathbb{N}$ and $1\leq i\leq k$ we have

$f=\sum_{j=1}^{i}(-(S-1))^{j-1}+(-1)^{i}\sum_{(v_{1},\ldots,v_{i})\in
F_{1}^{*}\times\ldots\times F_{i}^{*}}\phi^{(N)}_{v_{1},\ldots,v_{i}}$ (12)

Notice that the functions $\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}*f$
are bounded between $\min f$ and $\max f$, thus by (8), the functions
$\phi^{(N)}_{v_{1},\ldots,v_{i}}$ are bounded between $\min f$ and $\max f$
for every $(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times F_{i}^{*}$. In
particular, for every $(v_{1},\ldots,v_{i})\in F^{*}_{1}\times\ldots\times
F^{*}_{i}$ the sequence of functions
$(\phi^{(N)}_{v_{1},\ldots,v_{i}})_{N\in\mathbb{N}}$ is uniformly bounded,
hence by Arzelà–Ascoli theorem (or by a Cantor diagonalization argument), it
converges along a subsequence. We denote the limit by
$\phi_{v_{1},\ldots,v_{i}}$. Then for every $(v_{1},\ldots,v_{i})\in
F^{*}_{1}\times\ldots\times F^{*}_{i}$ we have

$\min f\leq\phi_{v_{1},\ldots,v_{i}}\leq\max f,$

and in view of (11) and (12) we have achieved (a) and (b).

To see (c), using (8), a standard telescoping argument shows that for every
$w\in\mathbb{Z}^{d}$, $v=(v_{1},\ldots,v_{i})\in F^{*}_{1}\times\ldots\times
F^{*}_{i}$ and every $1\leq j\leq i$

$\left|{\phi^{(N)}_{v_{1},\ldots,v_{i}}(w+qv_{j})-\phi^{(N)}_{v_{1},\ldots,v_{i}}(w)}\right|\leq\frac{2N^{i-1}}{N^{i}}\left(\max(f)-\min(f)\right)=\frac{2}{N}\left(\max(f)-\min(f)\right).$

Thus for every $(v_{1},\ldots,v_{i})\in F^{*}_{1}\times\ldots\times F^{*}_{i}$
the function $\phi_{v_{1},\ldots,v_{i}}$ is $qv_{j}$-periodic for every $1\leq
j\leq i$. It remains to show (d). Clearly, since $\mathbf{1}_{F_{j}}*f=1$, for
every $1\leq i,j\leq k$, $(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times
F_{i}^{*}$ and $n_{1},\ldots,n_{i}\in\mathbb{N}$ we have
$\mathbf{1}_{F_{j}}*(\delta_{(1+n_{1}q)v_{1}+\ldots(1+n_{i}q)v_{i}}*f)=1$.
Thus, by (8), $\mathbf{1}_{F_{j}}*\phi_{v_{1},\ldots,v_{i}}^{(N)}=1$ for every
$N\in\mathbb{N}$ and therefore
$\mathbf{1}_{F_{j}}*\phi_{v_{1},\ldots,v_{i}}=1$ for every $1\leq i,j\leq k$.
In particular, by Proposition 2.5, $\phi_{v_{1},\ldots,v_{i}}$ has mean $1/S$.
∎

######  Remark 3.3.

Under the assumption that $f$ is $\\{0,1\\}$-valued, it directly follows from
Theorem 3.1, part (a), that for every $1\leq i<k$ and every
$(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times F_{i}^{*}$, the sum
$\sum_{v_{i+1}\in F^{*}_{i+1}}\phi_{v_{1},\ldots,v_{i},v_{i+1}}$ is a
$[0,1]$-valued function. Theorem 3.1, where $k=1$ and $f$ is
$\\{0,1\\}$-valued, coincides with [GT21, Theorem 1.7]. We will not make use
of the property that $\mathbf{1}_{F_{j}}*\phi_{v_{1},\ldots,v_{i}}=1$ in this
paper. We mention it only for completeness and possibly for future reference.
The fact that the functions $\phi_{v_{1}}$ each have mean $1/S$ played an
implicit role in [Bha20].

Using the assumption that the tuple of tiles is independent Theorem 1.1 is an
immediate corollary of Theorem 3.1, with $f$ being a $\\{0,1\\}$-valued
function. The proof of Theorem 1.2 is straightforward.

###### Proof of Theorem 1.2.

Suppose that $(F_{1},\ldots,F_{d})$ is an independent tuple of tiles in
$\mathbb{Z}^{d}$ and that $f:\mathbb{Z}^{d}\to\mathbb{Z}$ is a bounded
function satisfying $\mathbf{1}_{F_{i}}*f=1$ for all $1\leq i\leq d$. By
Proposition 2.5, we have
$\left|{F_{1}}\right|=\ldots=\left|{F_{d}}\right|:=S$. Let $q$ be the product
of all primes less than or equal to $(\max f-\min f)S$ and let

$L=\bigcap_{(v_{1},\ldots,v_{d})\in F_{1}^{*}\times\ldots\times
F_{d}^{*}}q\mathbb{Z}v_{1}+\ldots+q\mathbb{Z}v_{d}.$

Apply Theorem 3.1 with $k=d$. It follows that $f$ is a sum of functions whose
stabilizers are rank $d$-subgroups, more precisely,

$f=(-1)^{d}\sum_{(v_{1},\ldots,v_{d})\in F_{1}^{*}\times\ldots\times
F_{d}^{*}}\phi_{v_{1},\ldots,v_{d}}+\sum_{j=1}^{d}(-(S-1))^{j-1},$

and for each $(v_{1},\dots,v_{d})\in F_{1}^{*}\times\ldots\times F_{d}^{*}$ we
have that
$q\mathbb{Z}v_{1}+\ldots+q\mathbb{Z}v_{d}\leq\operatorname{stab}(\phi_{v_{1},\ldots,v_{d}})$.
By the above, $\operatorname{stab}(f)$ contains the intersection of
$\operatorname{stab}(\phi_{v_{1},\ldots,v_{d}})$ over $(v_{1},\dots,v_{d})\in
F_{1}^{*}\times\ldots\times F_{d}^{*}$, that in turn contains $L$.

By the assumption that the tuple $(F_{1},\ldots,F_{d})$ is independent,
$q\mathbb{Z}v_{1}+\ldots+q\mathbb{Z}v_{d}$ is a finite index subgroup of
$\mathbb{Z}^{d}$ for every $(v_{1},\dots,v_{d})\in F_{1}^{*}\times\ldots\times
F_{d}^{*}$. Since $L$ is an intersection of finitely many finite index
subgroups, $L$ is also a finite index subgroup. In particular, this proves
that $f$ is $d$-periodic. In particular, any joint co-tile
$A\subseteq\mathbb{Z}^{d}$ for $(F_{1},\ldots,F_{d})$ is $L$-periodic. For any
finite-index subgroup $L$ of $\mathbb{Z}^{d}$ there are finitely many
$L$-periodic subsets, so the set of joint co-tiles for $(F_{1},\ldots,F_{d})$
is finite. ∎

######  Remark 3.4.

It is clear that in any system of tiling equations that admits a finite number
of solutions, the stabilizer of solutions is a finite index subgroup. It turns
out that the converse is also true: If every solution of a certain system of
tiling equations has a finite index stabilizer, it follows that the system
admits only finitely many solutions [BDJ08]. See also [MS19] for further
generalizations of this fact.

##  4\. Joint co-tilings in finitely generated abelian groups

It is natural to ask which of the results about tilings generalize from
$\mathbb{Z}^{d}$ to more general groups. An inspection of the proof of Theorem
3.1 reveals that the statement still holds, and the same proof applies if we
replace $\mathbb{Z}^{d}$ by an arbitrary countable abelian group $\Gamma$, and
change the value of $q$ in Theorem 3.1 (c) by multiplying it with the product
of the orders of all torsion elements in $F-F$.

Recall that elements $g_{1},\ldots,g_{k}$ in a countable abelian group
$\Gamma$ are called _independent_ if the equation
$\sum_{j=1}^{k}n_{j}g_{j}=0$, with $n_{1},\ldots,n_{k}\in\mathbb{Z}$, implies
that $n_{1}=\ldots=n_{k}=0$. With this definition, Theorem 1.1 extends
directly as follows:

######  Theorem 4.1.

Let $\Gamma$ be a countable abelian group. For every $k\in\mathbb{N}$, the
indicator function of any joint co-tile for $k$ independent tiles in $\Gamma$
is equal to a sum of $[0,1]$-valued functions whose stabilizer has rank at
least $k$, plus an integer constant.

######  Remark 4.2.

The structure of a general countable abelian group can be quite complicated.
In contrast, _finitely generated_ abelian groups have a simple structure
theorem: Any finitely generated abelian group is isomorphic to
$\mathbb{Z}^{d}\times G$, for some integer $d\geq 0$ and some finite abelian
group $G$ (which is a product of cyclic groups of the form
$(\mathbb{Z}/m\mathbb{Z}$). However, the following simple observation allows
one to reduce statements about tilings of countable abelian groups by a finite
set to the finitely generated case: Let $\Gamma$ be a countable abelian group
and let $F\Subset\Gamma$ with $0\in F$. Let $\Gamma_{0}$ denote the group
generated by the difference set $F-F$. The assumption $0\in F$ implies that
$F\Subset\Gamma_{0}$. Then for any co-tile $A$ of $F$ we have that
$A\cap\Gamma_{0}$ is a co-tile of $F$ in $\Gamma_{0}$, and tilings of $\Gamma$
by $F$ decompose into tilings of cosets of $\Gamma_{0}$ in $\Gamma$. A
corresponding statement is true also for a tuple of tiles
$(F_{1},\ldots,F_{k})$ and a joint co-tile.

Theorem 1.2 can be extended to finitely generated abelian groups as follows:

######  Theorem 4.3.

Let $\Gamma$ be a finitely generated abelian group of rank $d$. Any joint co-
tile for $d$ independent tiles in $\Gamma$ has a finite orbit.

######  Remark 4.4.

Using Remark 4.2 one can directly conclude the following property for joint
co-tiles of an arbitrary countable group: Let $\Gamma$ be a countable abelian
group and let $(F_{1},\ldots,F_{d})$ be an independent tuple of tiles in
$\Gamma$ so that the group $\Gamma_{0}$ generated by
$\bigcup_{i=1}^{d}(F_{i}-F_{i})$ has rank $d$. Then there are finitely many
set $A_{1},\ldots,A_{m}\subset\Gamma_{0}$ such that the any joint co-tile
$A\subseteq\Gamma$ of $(F_{1},\ldots,F_{d})$ satisfies $A\cap\Gamma_{0}=A_{i}$
for some $1\leq i\leq m$.

A quick remark about the condition of independence for a tuple of tiles for
finitely generated abelian groups with non-trivial torsion:

######  Remark 4.5.

If $\Gamma$ is of the form $\Gamma=\mathbb{Z}^{d}\times G$ where $G$ is a
finite abelian group and $(F_{1},\ldots,F_{k})$ is an independent tuple of
tiles in $\Gamma$, then the only torsion element in each of the sets $F_{i}$
is $0$. For this reason, Newman’s theorem (i.e. any tiling of $\mathbb{Z}$ by
a finite set is periodic) does not hold in abelian groups $\Gamma$ that are
finite extensions of $\mathbb{Z}$.

Figure 2. Non-periodic co-tiles of $\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$
for $n=4$ and $n=3$ for the tile $F=\\{1\\}\times G$, where $G$ is a non-
trivial subgroup of $\mathbb{Z}/n\mathbb{Z}$.

Indeed, let $\Gamma=\mathbb{Z}\times G$, where $G$ is a finite abelian group.
Consider the tile $F=\\{1\\}\times G\Subset\Gamma$. The co-tiles of $F$ are
all the sets $A\subset\Gamma$ of the following form:

$A=\\{(n,g_{n}):\leavevmode\nobreak\ n\in\mathbb{Z}\\},$

for some sequence $(g_{n})_{n\in\mathbb{Z}}$ of elements in $G$. In
particular, it is no longer true that any co-tile of $F$ must be periodic,
unless $G$ is trivial. Nonetheless, if $G$ is a finite cyclic group of prime
order, then the only obstructions to extending Newman’s theorem are of this
form. See [GT21, Lemma 5.1 and Remark 5.2] for related statements.

######  Proposition 4.6.

If $\Gamma=\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$ for some prime number $p$
and $F\Subset\Gamma$ is a finite set, then every co-tile of $F$ is periodic,
unless $F$ is of the form $F=\tilde{F}\times(\mathbb{Z}/p\mathbb{Z})$ for some
finite tile $\tilde{F}\Subset\mathbb{Z}$, in which case the co-tiles of $F$
are all of the form

$A=\\{(n,g_{n}):n\in\tilde{A}\\},\leavevmode\nobreak\
g_{n}\in\mathbb{Z}/p\mathbb{Z},$ (13)

where $\tilde{A}$ is a co-tile of $\tilde{F}\Subset\mathbb{Z}$, which by
Newman’s theorem must be periodic.

The proof of the proposition relies on the following generalization of Theorem
3.1.

######  Theorem 4.7.

Let $\Gamma$ be a countable abelian group, $F_{1},\ldots,F_{k}\Subset\Gamma$
such that $|F_{i}|=S$, and $0\in F_{i}$ for all $1\leq i\leq k$, and let
$f:\Gamma\to\mathbb{Z}$ be a bounded function that satisfies
$\mathbf{1}_{F_{i}}*f=1$ for all $1\leq i\leq k$. For every $1\leq i\leq k$,
let $F^{\operatorname{Tor}}_{i}$ denote the intersection of $F_{i}$ with the
torsion subgroup of $\Gamma$, and let $F_{i}^{*}=F_{i}\setminus
F^{\operatorname{Tor}}_{i}$. Then for every $1\leq i\leq k$ and every
$(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times F_{i}^{*}$ there exists a
function $\phi_{v_{1},\ldots,v_{i}}:\Gamma\to[\min f,\max f]$ with the
following properties:

  1. (a)

For $i<k$ we have

$\mathbf{1}_{F^{\operatorname{Tor}}_{i+1}}*\phi_{v_{1},\ldots,v_{i}}=1-\sum_{v_{i+1}\in
F_{i+1}^{*}}\phi_{v_{1},\ldots,v_{i},v_{i+1}}.$

  2. (b)

For every $1\leq i\leq k$ there is an integer constant $C_{i}$ such that

$\mathbf{1}_{F^{\operatorname{Tor}}_{1}}*\ldots*\mathbf{1}_{F^{\operatorname{Tor}}_{i}}*f=(-1)^{i}\sum_{(v_{1},\ldots,v_{i})\in
F_{1}^{*}\times\ldots\times F_{i}^{*}}\phi_{v_{1},\ldots,v_{i}}+C_{i}.$

  3. (c)

Let $q_{1}$ be the product of all primes less than or equal to $(\max f-\min
f)S$, let $q_{2}$ be the product of all the orders of the torsion elements in
the sets $F_{i}-F_{i}$, for $1\leq i\leq k$, and set $q=q_{1}q_{2}$. Then

$\left(\mathbb{Z}qv_{1}+\ldots+\mathbb{Z}qv_{i}\right)\leq\operatorname{stab}(\phi_{v_{1},\ldots,v_{i}}),$

  4. (d)

$1_{F_{j}}*\phi_{v_{1},\ldots,v_{i}}=1$ for all $1\leq j\leq k$. In
particular, $\phi_{v_{1},\ldots,v_{i}}$ has mean $1/S$.

The proof of Theorem 4.7 below is a minor adaptation of the proof of Theorem
3.1. Note that in the case where $\Gamma$ is a torsion free abelian group,
$F^{\operatorname{Tor}}_{i}=\\{0\\}$. In particular, when
$\Gamma=\mathbb{Z}^{d}$, Theorem 4.7 coincides with Theorem 3.1.

###### Proof.

By applying Lemma 3.2 for $F_{i}$ with $\ell=1$ and $q$ as in (c) we get
$\mathbf{1}_{rF_{i}}*f=1$ for every $r\in q\mathbb{N}+1$. Because $r=1\mod q$,
we have $rF^{\operatorname{Tor}}_{i}=F^{\operatorname{Tor}}_{i}$. Since
$F_{i}=F^{\operatorname{Tor}}_{i}\uplus F_{i}^{*}$ we have

$\mathbf{1}_{F^{\operatorname{Tor}}_{i}}*f=1-\sum_{v\in
F^{*}_{i}}\delta_{rv}*f\mbox{ for every }1\leq i\leq k.$

For every $N\in\mathbb{N}$, setting $r=1+nq$ for $n\in\\{1,\ldots,N\\}$ and
taking average we conclude that for every $1\leq j\leq k$ we have

$\mathbf{1}_{F^{\operatorname{Tor}}_{j}}*f=1-\sum_{v_{j}\in
F^{*}_{j}}\frac{1}{N}\sum_{n_{j}=1}^{N}\delta_{(1+n_{j}q)v_{j}}*f.$ (14)

Applying (14) with $j=i+1$, convolving both sides by
$\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}$ and taking average over
$\frac{1}{N^{i}}\sum_{n_{1},\ldots,n_{i}=1}^{N}$ yields

$\displaystyle\begin{split}\mathbf{1}_{F^{\operatorname{Tor}}_{i+1}}*\left[\frac{1}{N^{i}}\sum_{n_{1},\ldots,n_{i}=1}^{N}\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}*f\right]&=\\\
1-\sum_{v_{i+1}\in
F^{*}_{i+1}}\frac{1}{N^{i+1}}\sum_{n_{1},\ldots,n_{i},n_{i+1}=1}^{N}&\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}+(1+n_{i+1}q)v_{i+1}}*f.\end{split}$

Defining
$\phi_{v_{1},\ldots,v_{i}}^{(N)}=\frac{1}{N^{i}}\sum_{n_{1},\ldots,n_{i}=1}^{N}\delta_{(1+n_{1}q)v_{1}+\ldots+(1+n_{i}q)v_{i}}*f$,
as in (8), we obtain

$\mathbf{1}_{F^{\operatorname{Tor}}_{i+1}}*\phi^{(N)}_{v_{1},\ldots,v_{i}}=1-\sum_{v_{i+1}\in
F^{*}_{i+1}}\phi^{(N)}_{v_{1},\ldots,v_{i},v_{i+1}}.$ (15)

Note that (14) with $j=1$ becomes
$\mathbf{1}_{F^{\operatorname{Tor}}_{1}}*f=1-\sum_{v_{1}\in
F^{*}_{1}}\phi^{(N)}_{v_{1}}$. Convolving both sides by
$\mathbf{1}_{F^{\operatorname{Tor}}_{2}}$ and using (15) with $i=1$ gives

$\mathbf{1}_{F^{\operatorname{Tor}}_{1}}*\mathbf{1}_{F^{\operatorname{Tor}}_{2}}*f=|F^{\operatorname{Tor}}_{2}|-\sum_{v_{1}\in
F^{*}_{1}}\mathbf{1}_{F^{\operatorname{Tor}}_{2}}*\phi^{(N)}_{v_{1}}=|F^{\operatorname{Tor}}_{2}|-\sum_{v_{1}\in
F^{*}_{1}}\left(1-\sum_{v_{2}\in F^{*}_{2}}\phi^{(N)}_{v_{1},v_{2}}\right).$

By an inductive argument we obtain that for every $N\in\mathbb{N}$ and $1\leq
i\leq k$ there is a constant $C_{i}\in\mathbb{Z}$, that does not depend on
$N$, such that

$\mathbf{1}_{F^{\operatorname{Tor}}_{1}}*\ldots\mathbf{1}_{F^{\operatorname{Tor}}_{i}}*f=C_{i}+(-1)^{i}\sum_{(v_{1},\ldots,v_{i})\in
F_{1}^{*}\times\ldots\times F_{i}^{*}}\phi^{(N)}_{v_{1},\ldots,v_{i}}.$ (16)

Items (a) and (b) follow from (15) and (16) respectively. The rest of the
proof is completely identical to the proof of Theorem 3.1 and therefore
omitted. ∎

######  Lemma 4.8.

Let $p$ be a prime number and let $\emptyset\neq
F_{0}\subsetneqq\mathbb{Z}/p\mathbb{Z}$. Then $\mathbf{1}_{F_{0}}$ is an
invertible element of the ring $\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$, where
multiplication in the ring is convolution. In other words, there exists
$g\in\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$ such that
$g*\mathbf{1}_{F_{0}}=\delta_{0}$.

###### Proof.

Consider the ring $\mathbb{Q}[x]/\langle x^{p}-1\rangle$ (with operations of
addition and multiplication of polynomials). It is easy to check that this
ring is isomorphic as a ring to $\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$, with
the operations of pointwise addition and convolution. The isomorphism is given
by identifying an element

$\sum_{i=0}^{p-1}a_{i}x^{i}+\langle x^{p}-1\rangle\in\mathbb{Q}[x]/\langle
x^{p}-1\rangle$

with the function $f\in\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$ given by
$f(i+p\mathbb{Z})=a_{i}$.

Let $F_{0}\subset\mathbb{Z}/p\mathbb{Z}$ be a non-empty proper subset of
$\mathbb{Z}/p\mathbb{Z}$. Then
$\mathbf{1}_{F_{0}}\in\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$ is naturally
identified with the coset of the polynomial $P(x)=\sum_{(i+p\mathbb{Z})\in
F_{0}}x^{i}$ in $\mathbb{Q}[x]/\langle x^{p}-1\rangle$. Then the assumption
that $F_{0}$ is a non-empty proper subset of $\mathbb{Z}/p\mathbb{Z}$ implies
that the polynomial $P$ is co-prime to the cyclotomic polynomial of order $p$,
$\Phi_{p}=\sum_{i=0}^{p-1}x^{i}$. Since $P(1)=|F_{0}|\neq 0$ it follows that
$P$ is co-prime to $x-1$. Because $x^{p}-1=\Phi_{p}(x)(x-1)$, it follows that
$P$ is co-prime to $x^{p}-1$. Hence there exists polynomials
$Q_{1},Q_{2}\in\mathbb{Q}[x]$ such that

$1=Q_{1}(x)P(x)+Q_{2}(x)(x^{p}-1).$

This means that in the ring $\mathbb{Q}[x]/\langle x^{p}-1\rangle$, the coset
of $Q_{1}(x)P(x)$ is the same as the coset of the polynomial $1$. Since the
coset of the polynomial $1$ in $\mathbb{Q}[x]/\langle x^{p}-1\rangle$
corresponds to $\delta_{0}\in\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$, this
implies that $g*\mathbf{1}_{F_{0}}=\delta_{0}$, where
$g\in\mathbb{Q}^{\mathbb{Z}/p\mathbb{Z}}$ is the element corresponding to the
coset of $Q_{1}$. ∎

###### Proof of Proposition 4.6.

Let $p$ be a prime number and
$F\Subset\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$ be a finite set. Suppose
$A\subset\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$ satisfies
$\mathbf{1}_{F}*\mathbf{1}_{A}=1$. Applying Theorem 4.7 with
$\Gamma=\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$ $k=1$, $F_{1}=F$ and
$f=\mathbf{1}_{A}$, we conclude that
$\mathbf{1}_{F^{\operatorname{Tor}}}*\mathbf{1}_{A}$ is a sum functions having
infinite stabilizer, hence
$\mathbf{1}_{F^{\operatorname{Tor}}}*\mathbf{1}_{A}$ is periodic.

First, assume that there is a set $\tilde{F}\Subset\mathbb{Z}$ such that
$F=\tilde{F}\times\mathbb{Z}/p\mathbb{Z}$. So
$\mathbf{1}_{F}=\mathbf{1}_{\tilde{F}\times\\{0\\}}*\mathbf{1}_{\\{0\\}\times(\mathbb{Z}/p\mathbb{Z})}$.
Thus
$\mathbf{1}_{\tilde{F}\times\\{0\\}}*\mathbf{1}_{\\{0\\}\times(\mathbb{Z}/p\mathbb{Z})}*\mathbf{1}_{A}=1$.
This implies that $\mathbf{1}_{\\{0\\}\times(\mathbb{Z}\times
p\mathbb{Z})}*1_{A}\leq 1$, so for every $n\in\mathbb{Z}$ there exists at most
one element $g_{n}\in\mathbb{Z}/p\mathbb{Z}$ such that $(n,g_{n})\in A$.
Hence, in this case, $A$ is of the form (13) for some set
$\tilde{A}\subset\mathbb{Z}$. It follows that
$\mathbf{1}_{\tilde{F}}*\mathbf{1}_{\tilde{A}}=1$, where the convolution here
is with respect to the group $\mathbb{Z}$.

Now suppose that $F$ is not of the above form. This means that there exists
$n\in\mathbb{Z}$ such that $F\cap(\\{n\\}\times\mathbb{Z}/p\mathbb{Z})$ is a
non-empty proper subset of $\\{n\\}\times(\mathbb{Z}/p\mathbb{Z})$. By
translating $F$ we can assume without loss of generality that
$F^{\operatorname{Tor}}$ is neither empty nor equal to
$\\{0\\}\times(\mathbb{Z}/p\mathbb{Z})$. Then there exists a non-empty proper
subset $F_{0}\subset\mathbb{Z}/p\mathbb{Z}$ such that
$F^{\operatorname{Tor}}=\\{0\\}\times F_{0}$. In this case, by Lemma 4.8,
there exists $g:\mathbb{Z}/p\mathbb{Z}\to\mathbb{Q}$ such that
$g*\mathbf{1}_{F_{0}}=\delta_{0}$, where the convolution is in
$(\mathbb{Z}/p\mathbb{Z})$. Let
$\tilde{g}:\mathbb{Z}\times\mathbb{Z}/p\mathbb{Z}\to\mathbb{Q}$ be given by
$\tilde{g}(0,i)=g(i)$ for $i\in\mathbb{Z}/p\mathbb{Z}$ and $g(n,i)=0$ for
every $n\in\mathbb{Z}\setminus\\{0\\}$ and $i\in\mathbb{Z}/p\mathbb{Z}$. Then
$\tilde{g}*\mathbf{1}_{F^{\operatorname{Tor}}}=\delta_{0}$, where this time
the convolution is in $\mathbb{Z}\times(\mathbb{Z}/p\mathbb{Z})$. Since
$\mathbf{1}_{F^{\operatorname{Tor}}}*\mathbf{1}_{A}$ is periodic, so is
$\tilde{g}*\mathbf{1}_{F^{\operatorname{Tor}}}*\mathbf{1}_{A}=\mathbf{1}_{A}$.

We have thus shown that in the case that $F$ is not of the form
$F=\tilde{F}\times(\mathbb{Z}/p\mathbb{Z})$ for some
$\tilde{F}\Subset\mathbb{Z}$, every co-tile is periodic. ∎

##  5\. Property $(\star)$ implies $(d-1)$-piecewise periodicity

In this section, we use property $(\star)$ to deduce Theorem 1.6. To this end,
we will use Theorem 2.4, which is a version of Weyl’s equidistribution theorem
for polynomials in several variables. The relevance of Weyl’s equidistribution
theorem to our setting comes from Lemma 5.1 below. We note that similar
arguments have appeared earlier in [Bha20], [KS20], and [GT21].

######  Lemma 5.1.

Suppose $g,g_{1},\ldots,g_{m}:\Gamma_{1}\to\Gamma_{2}$ are functions, where
$\Gamma_{1},\Gamma_{2}$ are abelian groups, such that $\sum_{i=1}^{m}g_{i}=g$.
Suppose $g$ is a polynomial of degree at most $r\in\mathbb{N}$ with respect to
a subgroup $\Gamma_{0}\leq\Gamma_{1}$. For any $1\leq i<j\leq m$ define the
group $L_{i,j}=\operatorname{stab}(g_{i})+\operatorname{stab}(g_{j})$, and let
$L=\bigcap_{1\leq i<j\leq m}L_{i,j}\cap\Gamma_{0}$. Then each $g_{i}$ is a
polynomial of degree at most $\max\\{m-1,r\\}$ with respect to $L$. In
particular, if $\Gamma_{0}$ and $L_{i,j}$ has finite index in $\Gamma_{1}$ for
every $1\leq i<j\leq m$, then $L$ has finite index in $\Gamma_{1}$, and each
$g_{i}$ is a polynomial with respect to a finite index subgroup of
$\Gamma_{1}$.

###### Proof.

We prove the claim by induction on $m$. If $m=1$ then $g_{1}=g$, so the claim
holds. For $m>1$, take $v\in L$, then in particular $v\in
L_{1,2}\cap\Gamma_{0}$ and thus $v=v_{1}+v_{2}$ for some
$v_{1}\in\operatorname{stab}(g_{1})$ and $v_{2}\in\operatorname{stab}(g_{2})$.
Note that for every function $f:\Gamma_{1}\to\Gamma_{2}$, the identity
$D_{v}f=D_{v_{1}}f\circ\sigma_{v_{2}}+D_{v_{2}}f$ holds, where
$\sigma_{u}:\Gamma_{1}\to\Gamma_{1}$ denotes the shift by $u$,
$\sigma_{u}(w)=w-u$. Since $D_{v_{1}}g_{1}=0$, applying this identity to
$g_{1}=-\sum_{i=2}^{m}g_{i}+g$ yields

$D_{v}g_{1}=D_{v_{2}}g_{1}=-D_{v_{2}}\left(\sum_{i=2}^{m}g_{i}-g\right).$

Since $D_{v_{2}}g_{2}=0$ we have

$D_{v}g_{1}+\sum_{i=3}^{m}D_{v_{2}}g_{i}=D_{v_{2}}g.$ (17)

Note that $v_{2}\in\Gamma_{0}$, hence $D_{v_{2}}g$ is a polynomial of degree
at most $r-1$ with respect to $\Gamma_{0}$. So by the induction hypothesis,
each summand on the left-hand side in (17) is a polynomial of degree at most
$\max\\{m-2,r-1\\}$ with respect to a subgroup $L^{\prime}$, defined in a
similar way to $L$ using the functions
$D_{v}g_{1},D_{v_{2}}g_{3},\ldots,D_{v_{2}}g_{m}$. In particular, for every
$v\in L$ the function $D_{v}g_{1}$ is a polynomial of degree at most
$\max\\{m-2,r-1\\}$ with respect to $L^{\prime}$.

Now observe that for every $f:\Gamma_{1}\to\Gamma_{2}$ and $v\in\Gamma_{1}$ we
have $stab(f)\subseteq stab(D_{v}f)$, thus $L\leq L^{\prime}$ and for every
$v\in L$ we, in particular, have that $D_{v}g_{1}$ is a polynomial of degree
at most $\max\\{m-2,r-1\\}$ with respect to $L$. In a similar way for $2\leq
i\leq m$ and every $v\in L$, each $D_{v}g_{i}$ is a polynomial of degree at
most $\max\\{m-2,r-1\\}$ with respect to $L$, which completes the proof.

∎

######  Lemma 5.2.

Suppose $g:\mathbb{Z}^{d}\to[0,1]$ is a function such that:

  1. (1)

$g\mod 1$ is a polynomial with respect to a finite index subgroup of
$\mathbb{Z}^{d}$.

  2. (2)

$g$ is a sum of finitely many non-negative $(d-1)$-periodic functions.

Then there exists a finite index subgroup $\Gamma\leq\mathbb{Z}^{d}$ such that
the restriction of $g$ to each coset of $\Gamma$ is $(d-1)$-periodic.

###### Proof.

Suppose $g=\sum_{i=1}^{m}g_{i}$, where $g_{i}:\mathbb{Z}^{d}\to[0,1]$ and
$\operatorname{rank}(\operatorname{stab}(g_{i}))\geq d-1$. In case that
$\operatorname{rank}\left(\bigcap_{i=1}^{m}\operatorname{stab}(g_{i})\right)\geq
d-1$, the function $g$ is $(d-1)$-periodic and the assertion follows.
Otherwise, by summing together some of the $g_{i}$’s we can assume without
loss of generality that
$\operatorname{stab}(g_{i})+\operatorname{stab}(g_{j})$ is a finite index
subgroup of $\mathbb{Z}^{d}$, for every $i\neq j$. By Lemma 5.1, because $g$
modulo $1$ is a polynomial with respect to a finite index subgroup, we
conclude that each of the $g_{i}$’s modulo $1$ are polynomials with respect to
a finite index subgroup $\Gamma_{0}\leq\mathbb{Z}^{d}$. Let

$\Gamma=\Gamma_{0}\cap\bigcap_{i\neq
j}\left(\operatorname{stab}(g_{i})+\operatorname{stab}(g_{j})\right).$

We will show that $g$ is $(d-1)$-periodic on each coset of $\Gamma$. Since
$\Gamma\leq\Gamma_{0}$, each $g_{i}$ modulo $1$ is also a polynomials with
respect to $\Gamma$. Hence by Weyl’s equidistribution theorem (Theorem 2.4),
every $g_{i}$ modulo $1$ is either equidistributed or periodic, on each coset
of $\Gamma$.

Fix $u\in\mathbb{Z}^{d}$. Let $g^{(u)}:(u+\Gamma)\to[0,1]$ denote the
restriction of $g$ to this coset. We consider 3 cases:

  1. (1)

Suppose there exists $1\leq i\leq m$ and $v\in(u+\Gamma)$ such that
$g_{i}(v)=1$. Then because $0\leq g(v)\leq 1$ and $g_{j}(v)\geq 0$, we
conclude that $g_{j}(v)=0$ for all $j\neq i$. But $g_{i}(v)=1$ implies that
$g_{i}(v+w_{1})=1$ for all $w_{1}\in\operatorname{stab}(g_{i})$ so by the same
argument $g_{j}(v+w_{1})=0$ for all $w_{1}\in\operatorname{stab}(g_{i})$.
Thus, $g_{j}(v+w_{1}+w_{2})=0$ for all $w_{1}\in\operatorname{stab}(g_{i})$
and $w_{2}\in\operatorname{stab}(g_{j})$. Since
$\Gamma\leq\operatorname{stab}(g_{i})+\operatorname{stab}(g_{j})$, we conclude
that $g_{j}$ is zero on the coset $u+\Gamma$, for all $j\neq i$. This shows
that in this case $g^{(u)}=g_{i}$ on $u+\Gamma$, and in particular $g^{(u)}$
is $(d-1)$-periodic. So in the remaining cases we can assume that none of the
$g_{i}$’s are equal to one, hence the $g_{i}$’s obtain values in the interval
$[0,1)$.

  2. (2)

Suppose there exists $1\leq i\leq m$ such that $g_{i}$ is equidistributed
modulo 1 on $u+\Gamma$. Let $0<\epsilon<1$ be smaller than all the non-zero
values obtained by the (possibly empty) set of $g_{j}$ that are periodic
modulo 1. Because $g_{i}$ is equidistributed modulo 1 on $u+\Gamma$, there
exists $v\in u+\Gamma$ such that $g_{i}(v)>1-\epsilon$. Thus,
$g_{j}(v)<\epsilon$ for all $j\neq i$. As in the previous part, using
$\Gamma\leq\operatorname{stab}(g_{i})+\operatorname{stab}(g_{j})$, we conclude
that $g_{j}(w)<\epsilon$ for all $j\neq i$ and all $w\in u+\Gamma$. This tells
us that in particular that $g_{j}$ is not equidistributed modulo $1$ on
$u+\Gamma$. By the choice of $\epsilon$, $g_{j}(w)=0$ for every periodic
$j\neq i$ and every $w\in u+\Gamma$. We conclude also in this case that
$g=g_{i}$ on $u+\Gamma$ and particular $g^{(u)}$ is $(d-1)$-periodic.

  3. (3)

The remaining case is that for every $i=1,\ldots,m$, the function $g_{i}$
takes values in $[0,1)$ and $g_{i}$ modulo $1$ is periodic on $u+\Gamma$.
Since they take values in $[0,1)$, the $g_{i}$’s themselves are all
$d$-periodic. It follows in this case that $g^{(u)}$ is $d$-periodic, as the
sum of $d$-periodic functions (and in particular $(d-1)$-periodic).

∎

###### Proof of Theorem 1.6.

We conveniently assume $d>2$, because the case $d=2$ is covered by [GT21].
Suppose that $A\subset\mathbb{Z}^{d}$ satisfies $F_{i}\oplus A=\mathbb{Z}^{d}$
for all $1\leq i\leq d-1$, where $(F_{1},\ldots,F_{d-1})$ is a tuple of tiles
in $\mathbb{Z}^{d}$ that has property $(\star)$, see Definition 1.4. Let
$\phi_{v_{1},\ldots,v_{d-1}}:\mathbb{Z}^{d}\rightarrow[0,1]$ be as in Theorem
3.1, applied for $k=d-1$ and $f=\mathbf{1}_{A}$. Given
$(v_{1},\ldots,v_{d-2})\in F_{1}^{*}\times\ldots\times F_{d-2}^{*}$ and a
$(d-1)$-dimensional subspace $V<\mathbb{R}^{d}$ such that
$v_{1},\ldots,v_{d-2}\in V$, define

$\psi_{V}=\sum_{w_{d-1}\in F^{*}_{d-1}\cap
V}\phi_{v_{1},\ldots,v_{d-2},w_{d-1}}.$

Note that by the independence of $(F_{1},\ldots,F_{d-1})$, every $(d-1)$-tuple
in $F_{1}^{*}\times\ldots\times F_{d-1}^{*}$ spans a $(d-1)$-dimensional
subspace. Denote by $H$ the set (counted without multiplicity) of all
$(d-1)$-dimensional subspaces of $\mathbb{R}^{d}$ spanned by $(d-1)$-tuples in
$F_{1}^{*}\times\ldots\times F_{d-1}^{*}$, and for $(v_{1},\ldots,v_{d-2})\in
F_{1}^{*}\times\ldots\times F_{d-2}^{*}$ let $H(v_{1},\ldots,v_{d-2})\subset
H$ be the set of such subspaces of dimension $(d-1)$ that contain
$v_{1},\ldots,v_{d-2}$. Thus, for every fixed tuple $(v_{1},\ldots,v_{d-2})\in
F_{1}^{*}\times\ldots\times F_{d-2}^{*}$ we have

$\sum_{w_{d-1}\in F_{d-1}^{*}}\phi_{v_{1},\ldots,v_{d-2},w_{d-1}}=\sum_{V\in
H(v_{1},\ldots,v_{d-2})}\psi_{V}.$ (18)

By property $(\star)$, $\\{H(v_{1},\ldots,v_{d-2})\leavevmode\nobreak\
:\leavevmode\nobreak\ (v_{1},\ldots,v_{d-2})\in F_{1}^{*}\times\ldots\times
F_{d-2}^{*}\\}$ is a partition of $H$, therefore

$\sum_{(v_{1},\ldots,v_{d-1})\in F_{1}^{*}\times\ldots\times
F_{d-1}^{*}}\phi_{v_{1},\ldots,v_{d-1}}=\sum_{V\in H}\psi_{V}.$ (19)

It follows that the functions $\psi_{V}$ possess the following three
properties:

  1. (i)

$1-\phi_{v_{1},\ldots,v_{d-2}}=\sum_{V\in H(v_{1},\ldots,v_{d-2})}\psi_{V}.$

  2. (ii)

$\operatorname{stab}(\psi_{V})$ is a rank $(d-1)$ subgroup of
$V\cap\mathbb{Z}^{d}$.

  3. (iii)

$\psi_{V}$ modulo $1$ is a polynomial with respect to a finite index subgroup
of $\mathbb{Z}^{d}$.

Indeed, property (i) is a direct consequence of Theorem 3.1 part (a) with
$i=d-1$, combined with (18). Property (ii) follows from Theorem 3.1 part (c).
Setting $\widetilde{\psi_{V}}=\psi_{V}\mod 1$, the equation in Theorem 3.1
part (b) (with $f=\mathbf{1}_{A}$ and $i=d-1$), combined with (19), yields
that $\sum_{V\in H}\widetilde{\psi_{V}}=0$. By property (ii),
$\operatorname{stab}(\widetilde{\psi_{V}})+\operatorname{stab}(\widetilde{\psi_{V^{\prime}}})$
is a finite index subgroup of $\mathbb{Z}^{d}$ whenever $V,V^{\prime}\in H$
and $V\neq V^{\prime}$. Thus property (iii) follows from Lemma 5.1.

In view of these three properties, Lemma 5.2 can be applied to
$g=1-\phi_{v_{1},\ldots,v_{d-2}}$, for any $(v_{1},\ldots,v_{d-2})\in
F_{1}^{*}\times\ldots\times F_{d-2}^{*}$. This implies that there is a finite
index subgroup $\Gamma_{d-2}\leq\mathbb{Z}^{d}$ such that each
$\phi_{v_{1},\ldots,v_{d-2}}$ is a polynomial with respect to $\Gamma_{d-2}$,
and its restriction to every coset $u+\Gamma_{d-2}$ is $(d-1)$-periodic.

Next, we iterate the above argument using the recursion formula in part (a) of
Theorem 3.1 combined with Lemma 5.2. In turn, this yields a finite index
subgroup $\Gamma_{1}\leq\mathbb{Z}^{d}$ such that each $\phi_{v_{1}}$ is a
polynomial with respect to $\Gamma_{1}$, and its restriction to every coset
$u+\Gamma_{1}$ is $(d-1)$-periodic. By part (b) of Theorem 3.1 with $i=1$ we
have that

$1-\mathbf{1}_{A}=\sum_{v_{1}\in F_{1}^{*}}\phi_{v_{1}}.$

So applying Lemma 5.2 to $g=1-\mathbf{1}_{A}$, we obtain a finite index
subgroup $\Gamma\leq\mathbb{Z}^{d}$ such that the restriction of
$1-\mathbf{1}_{A}$ to each coset of $\Gamma$ is $(d-1)$-periodic. Hence the
restriction of $\mathbf{1}_{A}$ to each coset of $\Gamma$ is $(d-1)$-periodic.
Thus, if $u_{1},\ldots,u_{r}$ are cosets representatives of $\Gamma$ in
$\mathbb{Z}^{d}$, setting $A_{u_{i}}=A\cap(u_{i}+\Gamma)\subset\mathbb{Z}^{d}$
yields a decomposition $A=A_{u_{1}}\uplus\ldots\uplus A_{u_{r}}$ of $A$ into
finitely many $(d-1)$-periodic sets, as required. ∎

##  6\. From piecewise $(d-1)$-periodicity to $d$-periodicity

The following lemma extracts an idea that appears within the proof of [GT21,
Theorem 5.4].

######  Lemma 6.1.

Suppose that $f_{1},\ldots,f_{r},f:\mathbb{Z}^{d}\to\mathbb{R}$ are bounded
functions satisfying $f=\sum_{i=1}^{r}f_{i}$. Assume additionally that:

  1. (1)

$\operatorname{stab}(f_{i})+\operatorname{stab}(f_{j})$ is a finite index
subgroup of $\mathbb{Z}^{d}$ for all $1\leq i<j\leq r$.

  2. (2)

$\operatorname{stab}(f)$ is a finite index subgroup of $\mathbb{Z}^{d}$.

Then, for each $1\leq j\leq r$, the group $\operatorname{stab}(f_{j})$ is of
finite index in $\mathbb{Z}^{d}$.

###### Proof.

Let $g_{1}=f_{1}-f$ and $g_{j}=f_{j}$ for $2\leq j\leq r$. Then
$g_{1}+\ldots+g_{r}=0$ and
$\operatorname{stab}(g_{i})+\operatorname{stab}(g_{j})$ is a finite index
subgroup of $\mathbb{Z}^{d}$ for all $1\leq i<j\leq r$. Using the fact that
$0$ is a polynomial, and applying Lemma 5.1, we get that each $g_{i}$ is a
polynomial with respect to a finite index subgroup of $\mathbb{Z}^{d}$. But
each $g_{i}$ is bounded. By Lemma 2.2, a polynomial with respect to a finite
index subgroup of $\mathbb{Z}^{d}$ that is bounded must be constant on cosets
of this finite index subgroup. This implies that for each $1\leq j\leq r$ the
group $\operatorname{stab}(f_{j})$ is of finite index in $\mathbb{Z}^{d}$. ∎

Theorem 1.8 is a direct consequence of the above lemma, as shown below.

###### Proof of Theorem 1.8.

Set $f_{j}=\mathbf{1}_{A_{j}}$, then $\sum_{j=1}^{r}f_{j}=1$. Let
$L_{j}\leq\mathbb{Z}^{d}$ be the subgroups of rank at least $d-1$ that
stabilizes $A_{j}$. Note that for every two such subgroups
$L_{j_{1}},L_{j_{2}}\leq\mathbb{Z}^{d}$, either their intersection has rank
$d-1$ or their sum has finite index in $\mathbb{Z}^{d}$. Assume by
contradiction that the intersection of all $L_{j}$’s is of rank less than
$d-1$. By unifying some of the $A_{j}$’s we can assume without loss of
generality that $L_{j_{1}}+L_{j_{2}}$ is a finite index subgroup of
$\mathbb{Z}^{d}$ for all $1\leq j_{1}<j_{2}\leq r$. By Lemma 6.1, for every
$1\leq j\leq r$ the group $L_{j}=\operatorname{stab}(f_{j})$ is of finite
index in $\mathbb{Z}^{d}$. Since an intersection of finitely many finite index
subgroups of $\mathbb{Z}^{d}$ has rank $d$, the assumption that
$\operatorname{rank}\left(\bigcap_{j=1}^{r}L_{j}\right)<d-1$ is false.

∎

We would also need the following lemma.

######  Lemma 6.2.

Suppose that $\Sigma\Subset\mathbb{R}$ is a finite set of real numbers,
$g_{1},\ldots,g_{r}:\mathbb{Z}^{d}\to\mathbb{R}$ are finitely supported
functions and $f:\mathbb{Z}^{d}\to\Sigma$ is a $(d-1)$-periodic function such
that $g_{j}*f$ is $d$-periodic for every $1\leq j\leq r$. Then there exists a
$d$-periodic function $\tilde{f}:\mathbb{Z}^{d}\to\Sigma$ such that
$g_{j}*f=g_{j}*\tilde{f}$ for every $1\leq j\leq r$.

###### Proof.

Consider the space

$X=\\{\tilde{x}\in\Sigma^{\mathbb{Z}^{d}}:\,\forall 1\leq j\leq
r,\,g_{j}*\tilde{x}=g_{j}*f\\},$

and let $\Gamma=\bigcap_{j=1}^{r}\operatorname{stab}(g_{j}*f)$. Then $X$ is a
$\Gamma$-shift of finite type, and by definition $f\in X$ is a
$(d-1)$-periodic point in $X$. Apply Lemma 2.10 to conclude that there exists
$\tilde{f}\in X$ that is $d$-periodic. Any such point $\tilde{f}$ satisfies
the conclusion of the lemma. ∎

At this stage, we are prepared to present the proof of Theorem 1.3.

###### Proof of Theorem 1.3.

Suppose that $A\subseteq\mathbb{Z}^{d}$ is a piecewise $(d-1)$-periodic joint
co-tile for $F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$. That is, there exists
functions $f_{1},\ldots,f_{r}:\mathbb{Z}^{d}\to\\{0,1\\}$, each $f_{j}$ is
$(d-1)$-periodic, and $\mathbf{1}_{A}=\sum_{j=1}^{r}f_{j}$. Consider first the
case that
$\operatorname{rank}\left(\bigcap_{j}\operatorname{stab}(f_{j})\right)\geq
d-1$. Let
$X=\bigcap_{i=1}^{k}\\{x\in\\{0,1\\}^{\mathbb{Z}^{d}}:\leavevmode\nobreak\
\mathbf{1}_{F_{i}}*x=1\\}$. The elements of $X$ are precisely the indicator
functions of joint co-tiles for $(F_{1},\ldots,F_{k})$. By the discussion
following Definition 2.7, $X$ is a shift of finite type, and
$\mathbf{1}_{A}=\sum_{j=1}^{r}f_{j}\in X$ is a $(d-1)$ periodic point. Thus by
Lemma 2.10 $X$ contains a $d$-periodic point.

It remains to consider the case where
$\operatorname{rank}\left(\bigcap_{j}\operatorname{stab}(f_{j})\right)<d-1$:
Note that for every two subgroups $L_{1},L_{2}\leq\mathbb{Z}^{d}$ having rank
at least $d-1$, either their intersection has rank at least $d-1$ or
$L_{1}+L_{2}$ has finite index in $\mathbb{Z}^{d}$. So as before, by possibly
summing some of the $f_{j}$’s we can assume without loss of generality that
$\operatorname{stab}(f_{l})+\operatorname{stab}(f_{j})$ is a finite index
subgroup of $\mathbb{Z}^{d}$ for all $1\leq l<j\leq r$. Now consider the
functions $\mathbf{1}_{F_{i}}*f_{j}$. Observe that for every $1\leq i\leq k$
we have $\sum_{j=1}^{r}\mathbf{1}_{F_{i}}*f_{j}=1$, and for every $1\leq j\leq
r$ we have
$\operatorname{stab}(f_{j})\leq\operatorname{stab}(\mathbf{1}_{F_{i}}*f_{j})$.
Thus setting $\Lambda_{i,j}:=\operatorname{stab}(\mathbf{1}_{F_{i}}*f_{j})$
yields that $\operatorname{rank}\left(\Lambda_{i,j}\right)\geq d-1$ and
$\Lambda_{i,l}+\Lambda_{i,j}$ is a finite index subgroup of $\mathbb{Z}^{d}$,
for every $1\leq i\leq k$ and $1\leq l<j\leq r$. Applying Lemma 6.1 for each
$1\leq i\leq k$ separately we see that each $\Lambda_{i,j}$ is a finite index
subgroup of $\mathbb{Z}^{d}$. That is, each one of the functions
$\mathbf{1}_{F_{i}}*f_{j}$ is $d$-periodic. For any fixed $1\leq j\leq r$,
applying Lemma 6.2 with $g_{i}=\mathbf{1}_{F_{i}}$ and $f=f_{j}$ and
$\Sigma=\\{0,1\\}$, yields a $d$-periodic function
$\tilde{f}_{j}:\mathbb{Z}^{d}\to\\{0,1\\}$ that satisfies
$\mathbf{1}_{F_{i}}*\tilde{f}_{j}=\mathbf{1}_{F_{i}}*f_{j}$, for all $1\leq
i\leq k$. In particular, the function $f:\mathbb{Z}^{d}\to\mathbb{Z}$ defined
by $f:=\sum_{j=1}^{r}\tilde{f}_{j}$ is bounded, $d$-periodic, and it satisfies

$\forall 1\leq i\leq
k:\qquad\mathbf{1}_{F_{i}}*f=\mathbf{1}_{F_{i}}*\left(\sum_{j=1}^{r}\tilde{f}_{j}\right)=\sum_{j=1}^{r}\mathbf{1}_{F_{i}}*\tilde{f}_{j}=\sum_{j=1}^{r}\mathbf{1}_{F_{i}}*f_{j}=1.$

Since $f=\sum_{j=1}^{r}\tilde{f}_{j}$ is a sum of $\\{0,1\\}$-valued functions
and $1_{F_{i}}*f=1$, it follows that $f$ itself is $\\{0,1\\}$-valued, hence
$f$ is an indicator of a set $\tilde{A}$ that satisfies
$F_{i}\oplus\tilde{A}=\mathbb{Z}^{d}$, for $1\leq i\leq k$. Since each
$\tilde{f}_{j}$ is $d$-periodic, so is $\tilde{A}$. This completes the proof.
∎

##  7\. Constructing independent tiles with property $(\star)$ for a periodic
co-tile

In this section, we prove Theorem 1.9. We repeatedly rely on the following
basic fact:

######  Lemma 7.1.

Let $L\leq\mathbb{Z}^{d}$ be a finite index subgroup and let
$U_{1},\ldots,U_{r}\subset\mathbb{R}^{d}$ be affine subspaces of dimension
strictly smaller than $d$. Then the set $L\setminus\bigcup_{i=1}^{r}U_{i}$ is
infinite.

###### Proof.

For $n\in\mathbb{N}$ let $B_{n}=\\{-n,\ldots,n\\}^{d}$. Then there exist
$c,c_{1},\ldots,c_{r}>0$ such that $\left|{B_{n}\cap L}\right|\geq cn^{d}$
while $\left|{B_{n}\cap U_{i}}\right|\leq c_{i}n^{\dim U_{i}}\leq
c_{i}n^{d-1}$. In particular,
$\left|{B_{n}\cap\left(L\setminus\bigcup_{i=1}^{r}U_{i}\right)}\right|$ tends
to infinity as $n$ tends to infinity. ∎

######  Lemma 7.2.

Let $F\Subset\mathbb{Z}^{d}$, let $A\subseteq\mathbb{Z}^{d}$ such that
$F\oplus A=\mathbb{Z}^{d}$ and let $L\leq\mathbb{Z}^{d}$ be a subgroup
satisfying $A+L=A$. Then for every function $f:F\to L$ the tile set

$F_{f}:=\\{v+f(v)\leavevmode\nobreak\ :\leavevmode\nobreak\ v\in F\\}$

satisfies $F_{f}\oplus A=\mathbb{Z}^{d}$.

###### Proof.

Given a function $f:F\to L$, we show that $F_{f}\oplus A=\mathbb{Z}^{d}$. The
condition $F\oplus A=\mathbb{Z}^{d}$ can be rewritten as
$\mathbb{Z}^{d}=\biguplus_{v\in F}(v+A)$. Since $A+L=A$ and $f(v)\in L$ for
every $v\in F$, it follows that $f(v)+A=A$. Thus,

$\mathbb{Z}^{d}=\biguplus_{v\in F}(v+A)=\biguplus_{v\in
F}(v+f(v)+A)=\biguplus_{\tilde{v}\in F_{f}}(\tilde{v}+A).$

This proves that $F_{f}\oplus A=\mathbb{Z}^{d}$. ∎

Let us introduce some ad-hoc notation:

######  Definition 7.3.

Given $d,m\in\mathbb{N}$, an $m$-tuple of vectors $T=(v_{1},\ldots,v_{m})$
with $v_{i}\in\mathbb{Z}^{d}$ for $1\leq i\leq m$, a function
$g:\\{1,\ldots,m\\}\to\mathbb{Z}^{d}$, a subset $J\subseteq\\{1,\ldots,m\\}$
and a subspace $W<\mathbb{R}^{d}$, let $V_{W}(T,g,J)$ denote the subspace of
$\mathbb{R}^{d}/W$ obtained by projecting
$\operatorname{span}\\{v_{j}+g(j):\leavevmode\nobreak\ j\in J\\}$ into
$\mathbb{R}^{d}/W$ via the map $v\mapsto v+W$.

######  Lemma 7.4.

Suppose we are given $d,m\in\mathbb{N}$, an $m$-tuple of vectors
$T=(v_{1},\ldots,v_{m})$ with $v_{i}\in\mathbb{Z}^{d}$ for $1\leq i\leq m$ and
finite index subgroup $L\leq\mathbb{Z}^{d}$. Then for every finite collection
$\mathcal{W}$ of proper subspaces of $\mathbb{R}^{d}$ there exists a function
$g:\\{1,\ldots,m\\}\to L$ so that for every $J\subseteq\\{1,\ldots,m\\}$ and
every $W\in\mathcal{W}$ we have

$\dim\left(V_{W}(T,g,J)\right)=\min\\{d-\dim(W),|J|\\}.$

###### Proof.

We fix a finite collection $\mathcal{W}$ of proper subspaces of
$\mathbb{R}^{d}$ and prove the claim by induction on $m$. For $m=1$, we only
need to choose $g(1)\in L$ such that $v_{1}+g(1)\not\in W$ for any
$W\in\mathcal{W}$. This is possible by Lemma 7.1. Assume by induction that
$g(1),\dots,g(m)\in L$ have been defined so that the conclusion holds for
every $J\subseteq\\{1,\ldots,m\\}$ and every $W\in\mathcal{W}$. Using Lemma
7.1 we can choose $g(m+1)\in L$ that is not contained in any affine hyperplane
of the form

$U:=-v_{m+1}+\operatorname{span}\\{v_{j}+g(j):\leavevmode\nobreak\ j\in
J\\}+W,$

where $W\in\mathcal{W}$ and $J$ ranges over subsets of $\\{1,\ldots,m\\}$ of
size at most $d-\dim(W)-1$. We need to show that for any
$J\subseteq\\{1,\ldots,m+1\\}$ and $W\in\mathcal{W}$ we have
$\dim\left(V_{W}(T,g,J)\right)=\min\\{d-\dim(W),|J|\\}$. Fix some
$J\subseteq\\{1,\ldots,m+1\\}$ and $W\in\mathcal{W}$. The assertion follows
from the induction hypothesis in case $(m+1)\not\in J$, so suppose $(m+1)\in
J$. By the induction hypothesis,
$\dim\left(V_{W}(T,g,J\setminus\\{m+1\\})\right)=\min\left\\{d-\dim(W),|J\setminus\\{m+1\\}|\right\\}$.
If $|J\setminus\\{m+1\\}|\geq d-\dim(W)$, then
$\dim\left(V_{W}(T,g,J\setminus\\{m+1\\})\right)=d-\dim(W)$, as required.
Otherwise, we have that

$\dim(V_{W}(T,g,J\setminus\\{m+1\\}))=|J\setminus\\{m+1\\}|=|J|-1.$

By our choice of $g(m+1)$, we have that

$v_{m+1}+g(m+1)\not\in\operatorname{span}\left\\{v_{j}+g(v_{j})\leavevmode\nobreak\
:\leavevmode\nobreak\ j\in J\setminus\\{m+1\\}\right\\}+W,$

so

$\dim\left(V_{W}(T,g,J)\right)=\dim(V_{W}(T,g,J\setminus\\{m+1\\}))+1=|J|.$

This completes the induction step, hence the proof. ∎

###### Proof of Theorem 1.9.

Suppose $F\oplus A=\mathbb{Z}^{d}$ where $L\leq\mathbb{Z}^{d}$ is a finite
index subgroup satisfying $A+L=A$. Write $F^{*}=\\{w_{1},\ldots,w_{k}\\}$. We
apply Lemma 7.4 with $m=(d-1)k$ and the $m$-tuple $T=(v_{1},\ldots,v_{m})$,
where $v_{kj+i}=w_{i}$ for $0\leq j\leq d-2$, and $1\leq i\leq k$, and
$\mathcal{W}=\left\\{\operatorname{span}\\{v\\}\leavevmode\nobreak\
:\leavevmode\nobreak\ v\in F\right\\}$ to obtain a function
$g:\\{1,\ldots,m\\}\to L$ so that for every $J\subseteq\\{1,\ldots,m\\}$ and
every $W\in\mathcal{W}$ we have

$\dim\left(V_{W}(T,g,J)\right)=\min\\{d-\dim(W),|J|\\}.$

For $0\leq j\leq d-2$ we set

$F_{j+1}=\\{0\\}\cup\\{v_{kj+i}+g(kj+i):\leavevmode\nobreak\ 1\leq i\leq
k\\}=\\{0\\}\cup\\{w_{i}+g(kj+i):1\leq i\leq k\\}.$

By Lemma 7.2 we indeed have $F_{j}\oplus A=\mathbb{Z}^{d}$ for every $1\leq
j\leq d-1$. To see that $(F_{1},\ldots,F_{d-1},F)$ is a $d$-tuple of
independent tiles, note that for any choice of $(u_{1},\ldots,u_{d-1},v)\in
F_{1}^{*}\times\ldots\times F_{d-1}^{*}\times F$ there exist
$i_{1},\ldots,i_{d-1}\in\\{1,\ldots,k\\}$ so that

$u_{j}=v_{k(j-1)+i_{j}}+g(k(j-1)+i_{j}).$

Hence, there exists a set $J\subset\\{1,\ldots,k(d-1)\\}$ with $|J|=d-1$ so
that

$\operatorname{span}\\{u_{1}+W,\ldots,u_{d-1}+W\\}=V_{W}(T,g,J),$

where $W=\operatorname{span}\\{v\\}$. By the construction of the function
$g:\\{1,\ldots,m\\}\to L$ we have $\dim(V_{W}(T,g,J))=d-1$. It follows that
$\dim(\operatorname{span}\\{u_{1},\ldots,u_{d-1},v\\})=d$.

Let us check that $\\{F_{1},\ldots,F_{d-2},F\\}$ has the property $(\star)$.
Since property $(\star)$ is vacuous in $d=2$, we assume that $d\geq 3$. Choose
two distinct $(d-2)$-tuples

$(u_{1},\ldots,u_{d-2}),(\tilde{u}_{1},\ldots,\tilde{u}_{d-2})\in
F_{1}^{*}\times\ldots\times F_{d-2}^{*},$

and $v,\tilde{v}\in F$. As before, it follows that there exist subsets
$J,\tilde{J}\subset\\{1,\ldots,m\\}$ with $J\neq\tilde{J}$ and
$|J|=|\tilde{J}|=d-2$ so that

$\\{u_{1},\ldots,u_{d-2}\\}=\\{v_{j}:\leavevmode\nobreak\ j\in J\\}\mbox{ and
}\\{\tilde{u}_{1},\ldots,\tilde{u}_{d-2}\\}=\\{v_{j}\leavevmode\nobreak\
:\leavevmode\nobreak\ j\in\tilde{J}\\}.$

Since $J\neq\tilde{J}$, there exists $\ell\in\tilde{J}\setminus J$. It follows
from the property of the function $g$ and the fact that $|J|=|\tilde{J}|=d-2$
that for any $v\in F^{*}$

$\dim(\operatorname{span}(\\{v_{j}\leavevmode\nobreak\ :\leavevmode\nobreak\
j\in J\\}\cup\\{v\\}))=d-1$

and

$\dim(\operatorname{span}(\\{v_{j}\leavevmode\nobreak\ :\leavevmode\nobreak\
j\in J\\}\cup\\{v\\}\cup\\{v_{\ell}\\}))=d.$

This shows that
$v_{\ell}\not\in\operatorname{span}\left(\\{v_{j}\leavevmode\nobreak\
:\leavevmode\nobreak\ j\in J\\}\cup\\{v\\}\right)$. In particular, there does
not exist $v\in F^{*}$ such that

$\operatorname{span}\left(\\{\tilde{u}_{1},\ldots,\tilde{u}_{d-2}\\}\right)\subseteq\operatorname{span}\left(\\{u_{1},\ldots,u_{d-2},v\\}\right).$

This shows that there does not exist $v,\tilde{v}\in F^{*}$ so that

$\operatorname{span}\left(\\{\tilde{u}_{1},\ldots,\tilde{u}_{d-2},\tilde{v}\\}\right)=\operatorname{span}\left(\\{u_{1},\ldots,u_{d-2},v\\}\right),$

which proves that $(F_{1},\ldots,F_{d-2},F)$ has property $(\star)$. ∎

##  8\. Further comments and questions

###  8.1. Integer-valued co-tiles

Given $F\Subset\Gamma$, we say that a bounded function $f:\Gamma\to\mathbb{Z}$
is an _integer-valued co-tile_ for $F$ if $\mathbf{1}_{F}*f=1$. Observe that
our proof of Theorem 1.3 holds for integer-valued co-tile as well, thus we
have:

######  Proposition 8.1.

Let $k$ and $d$ be positive integers and let
$F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$. Suppose that $F_{1},\ldots,F_{k}$
admit an integer-valued joint co-tile $f$ and that $f=\sum_{i=1}^{r}f_{r}$,
where each $f_{i}:\mathbb{Z}^{d}\to\mathbb{Z}$ is bounded and
$(d-1)$-periodic. Then $F_{1},\ldots,F_{k}$ admit a $d$-period integer-valued
joint co-tile.

It is natural to ask whether the existence of an integer-valued co-tile for
$F\Subset\Gamma$ implies the existence of a set $A\subseteq\Gamma$ for which
$\mathbf{1}_{F}*\mathbf{1}_{A}=1$? The simple example below shows that this is
not true even for $\Gamma=\mathbb{Z}$ (or for $\Gamma$ a finite cyclic group,
here $\mathbb{Z}/18\mathbb{Z}$). Let $F_{1}=\\{0,1\\}$, $F_{2}=\\{0,3,6\\}$
and $F=F_{1}\oplus F_{2}=\\{0,1,3,4,6,7\\}$.

We claim that $F$ does not tile $\mathbb{Z}$, but it does admit an integer-
valued co-tile. Note that for $A_{1}=2\mathbb{Z}$ and $A_{2}=\\{0,1,2\\}\oplus
9\mathbb{Z}$ we have

$F_{1}\oplus A_{1}=F_{2}\oplus A_{2}=\mathbb{Z}.$

Furthermore, if $\tilde{A}_{1}$ is a co-tile for $F_{1}$ then $\tilde{A}_{1}$
must be a translate of $A_{1}$. To see that $F$ does not tile $\mathbb{Z}$,
suppose by contradiction that $F\oplus A=\mathbb{Z}$ then
$F_{1}\oplus(F_{2}\oplus A)=\mathbb{Z}$, so we must have that $F_{2}\oplus A$
is a coset of $2\mathbb{Z}$, but this is clearly impossible since $F_{2}$ is
not contained in a coset of $2\mathbb{Z}$. Now take

$f=\mathbf{1}_{A_{1}}-\mathbf{1}_{A_{2}}.$

Then using $\mathbf{1}_{F}=\mathbf{1}_{F_{1}}*\mathbf{1}_{F_{2}}$ and
$\mathbf{1}_{F_{i}}*1=|F_{i}|$ we get:

$\mathbf{1}_{F}*f=\mathbf{1}_{F_{2}}*(\mathbf{1}_{F_{1}}*\mathbf{1}_{A_{1}})-\mathbf{1}_{F_{1}}*(\mathbf{1}_{F_{2}}*\mathbf{1}_{A_{2}})=|F_{2}|-|F_{1}|=1.$

###  8.2. Conditions for joint tilings for $d$ independent tiles in
$\mathbb{Z}^{d}$

In view of Theorem 1.2, the classical Wang argument (see [Ber66], [Rob71])
implies that it is algorithmically decidable whether a set of $d$ independent
tiles in $\mathbb{Z}^{d}$ admit a joint co-tile: Indeed, any such tiling must
be periodic so we can exhaust the possible periodic co-tiles. As in [GT21],
from an upper bound for the period of a co-tile one can directly deduce an
upper bound for the computational complexity of this tiling problem. It is of
interest to find explicit necessary and sufficient conditions for a $d$-tuple
of independent subsets of $\mathbb{Z}^{d}$ to admit a joint co-tile. In view
of Theorem 1.9, the previous problem is closely related to the more basic
question of finding explicit necessary and sufficient conditions for a finite
set of $\mathbb{Z}^{d}$ to tile periodically.

Conversely, one can ask about necessary and sufficient conditions for an
infinite subset of $\mathbb{Z}^{d}$ to be a joint co-tile for $d$-independent
tiles. In view of Theorem 1.2 and Theorem 1.9, this is equivalent to the
question of finding necessary and sufficient conditions for a periodic subset
of $\mathbb{Z}^{d}$ to be a co-tile for a finite tile.

A complete solution to the above questions involves the factorization of
finite abelian groups, namely understanding solutions for $A\oplus B=G$, where
$G$ is a finite abelian group. This is a difficult problem even in the cyclic
case $G=\mathbb{Z}/M\mathbb{Z}$, which comes up in tilings of $\mathbb{Z}$.

Coven and Meyerowitz [CM99] found explicit and efficiently verifiable
sufficient conditions for tiling the integers by a finite set. It has been
conjectured that these conditions are also necessary. This conjecture has been
verified in some specific cases recently [ŁL22a, ŁL22b]. The necessity of the
Coven-Meyerowitz conditions would imply an efficient algorithm for determining
if a given finite subset $F\Subset\mathbb{Z}$ can tile $\mathbb{Z}$, see
[KM09].

###  8.3. Higher level tilings

A level $\ell$ co-tile of $\mathbb{Z}^{d}$ by a finite set
$F\Subset\mathbb{Z}^{d}$ is a set $A\subseteq\mathbb{Z}^{d}$ such that
$\mathbf{1}_{F}*\mathbf{1}_{A}=\ell$. Both Theorem 1.1 and Theorem 1.2
generalize to level $\ell$ tilings. A suitable modification of Proposition 2.5
implies that if $\mathbf{1}_{F}*f=\ell$ then $f$ has mean $\frac{\ell}{|F|}$.
A proof can be obtained via a relatively routine modification of Theorem 3.1
as follows:

######  Theorem 8.2.

Let $\ell_{1},\ldots,\ell_{k}\in\mathbb{N}$,
$F_{1},\ldots,F_{k}\Subset\mathbb{Z}^{d}$, with $0\in F_{i}$ for all $1\leq
i\leq k$, and let $f:\mathbb{Z}^{d}\to\mathbb{Z}$ be a bounded function that
satisfies $\mathbf{1}_{F_{i}}*f=\ell_{i}$ for all $1\leq i\leq k$. Then for
every $1\leq i\leq k$ and every $(v_{1},\ldots,v_{i})\in
F_{1}^{*}\times\ldots\times F_{i}^{*}$ there exists a function
$\phi_{v_{1},\ldots,v_{i}}:\mathbb{Z}^{d}\to[\min f,\max f]$ with the
following properties:

  1. (a)

For $i<k$ we have

$\phi_{v_{1},\ldots,v_{i}}=\ell_{i+1}-\sum_{v_{i+1}\in
F_{i+1}}\phi_{v_{1},\ldots,v_{i},v_{i+1}}.$

  2. (b)

$f=(-1)^{i}\sum_{(v_{1},\ldots,v_{i})\in F_{1}^{*}\times\ldots\times
F_{i}^{*}}\phi_{v_{1},\ldots,v_{i}}+\sum_{j=1}^{i}(-1)^{j-1}\prod_{t=1}^{j}\ell_{t}\prod_{s=1}^{j-1}|F_{s}|.$

  3. (c)

Let $q$ denote the product of all primes less than or equal to $\max_{1\leq
i\leq k}\ell_{k}(\max f-\min f)\max_{1\leq i\leq k}|F_{i}|$, then

$\left(\mathbb{Z}qv_{1}+\ldots+\mathbb{Z}qv_{i}\right)\leq\operatorname{stab}(\phi_{v_{1},\ldots,v_{i}}),$

  4. (d)

$\mathbf{1}_{F_{i}}*\phi_{v_{1},\ldots,v_{i}}=\ell_{i}$ for every $1\leq i\leq
k$. In particular, it has mean $\ell_{i}/|F_{i}|$.

###  8.4. Piecewise $1$-periodicity of co-tiles in
$\mathbb{Z}^{2}\times(\mathbb{Z}/p\mathbb{Z})$

By applying the arguments of Section 4, the methods of [GT21] directly give:

######  Theorem 8.3.

Let $p$ be a prime number,
$\Gamma=\mathbb{Z}^{2}\times(\mathbb{Z}/p\mathbb{Z})$ and $F\Subset\Gamma$ be
a finite set. Then one of the following holds:

  1. (1)

Any $A\subset\Gamma$ satisfying $F\oplus A=\Gamma$ is piecewise $1$-periodic.

  2. (2)

There exists a finite set $\tilde{F}\subset\mathbb{Z}^{2}$ such that
$F=\tilde{F}\times(\mathbb{Z}/p\mathbb{Z})$.

In fact, using Theorem 4.7 and the results of Section 5, we can deduce the
following: For any rank $2$ abelian group $\Gamma$ and any $F\Subset\Gamma$,
if $F\oplus A=\Gamma$ then the set $F^{\operatorname{Tor}}\oplus A$ is
piecewise $1$-periodic, whereas in Section 4, $F^{\operatorname{Tor}}$ is the
intersection of $F$ with the torsion subgroup of $\Gamma$. Then in the case
$\Gamma=\mathbb{Z}^{2}\times(\mathbb{Z}/p\mathbb{Z})$ with $p$ prime, Lemma
4.8 implies Theorem 8.3.

######  Corollary 8.4.

Let $p$ be a prime number,
$\Gamma=\mathbb{Z}^{2}\times(\mathbb{Z}/p\mathbb{Z})$ and $F\Subset\Gamma$ be
a finite set. If $F$ tiles $\Gamma$, then $F$ tiles $\Gamma$ periodically.

Rachel Greenfeld and Terence Tao have informed us in private communication
that they also obtained Corollary 8.4.

###  8.5. A Fourier-analytic and algebraic-geometric approach to the study of
joint co-tiles

Fourier analytic methods are a natural approach to translational tiling
problems, see [Kol04]. Here we outline a specifc application related to [GT21,
Remark 1.8]. Let $g_{1},\ldots,g_{d}:\mathbb{Z}^{d}\to\mathbb{C}$ be finitely
supported functions, by which we mean that $g_{i}(v)=0$ for all but finitely
many $v\in\mathbb{Z}^{d}$. Suppose $f:\mathbb{Z}^{d}\to\mathbb{C}$ is a
bounded function that satisfies $g_{i}*f=1$ for all $1\leq i\leq d$. Taking
distributional Fourier transform on both sides yields

$\hat{g_{i}}\cdot\hat{f}=\delta_{0}.$

Thus, the distributional Fourier transform of $f$ is supported on $0$ and the
intersection of the zeros of $\hat{g_{i}}$. In particular, if
$\hat{g_{1}},\ldots,\hat{g_{d}}$ have finitely many common zeros, $f$ must be
the Fourier transform of a multivariate trigonometric polynomial. From the
multidimensional version of Weyl’s equidistribution theorem, it follows that
$f$ must be either periodic or equidistributed to a measure whose support is
an infinite compact subset of $\mathbb{C}$. So if we further assume $f$ takes
finitely many values (as is the case when $f$ is the indicator function of a
joint co-tile), $f$ must be periodic.

The set of common zeros for $d$ polynomials in $d$ variables is “generically”
a finite set. Given $v=(n_{1},\ldots,n_{d})\in\mathbb{Z}_{+}^{d}$ let
$X^{v}:=x_{1}^{n_{1}}\cdot\ldots\cdot x_{d}^{n_{d}}$ denote the corresponding
monomial in $d$ variables $x_{1},\ldots,x_{d}$. Given a finite set
$F\Subset\mathbb{Z}_{+}^{d}$, let $P_{F}:=\sum_{v\in F}X^{v}$ denote the
corresponding multivariate polynomial. We conclude that whenever
$F_{1},\ldots,F_{d}\Subset\mathbb{Z}_{+}^{d}$ are subsets such that the
algebraic variety

$V(P_{F_{1}},\ldots,P_{F_{d}}):=\bigcap_{i=1}^{d}\left\\{(x_{1},\ldots,x_{d})\in\mathbb{C}^{d}\leavevmode\nobreak\
:\leavevmode\nobreak\ P_{F_{i}}(x_{1},\ldots,x_{d})=0\right\\}$

has a finite intersection with the $d$-sphere, then any joint co-tile for
$F_{1},\ldots,F_{d}$ is periodic.

This raises the question: Is it true that for an independent $d$-tuple
$(F_{1},\ldots,F_{d})$ in $\mathbb{Z}^{d}$ the algebraic variety
$V(P_{F_{1}},\ldots,P_{F_{d}})$ is finite?

We note that it can be shown that $V(P_{F_{1}},\ldots,P_{F_{d}})$ is finite if
we impose the somewhat stronger condition that
$(F_{1}-F_{1},\ldots,F_{d}-F_{d})$ is an independent $d$-tuple in
$\mathbb{Z}^{d}$. This follows from the equality of the tropical variety with
the Bieri-Groves set of the variety (see Theorem 2.2.5 and Corollary 2.2.6 in
[EKL06]), combined with [EKL06, Theorem 2.2.3] and an explicit direct
computation. This connection was kindly explained to us by Ilya Tyomkin. This
argument gives an alternative derivation of the conclusion of Theorem 1.2,
under the slightly stronger assumption that $(F_{1}-F_{1},\ldots,F_{d}-F_{d})$
is an independent tuple of tiles in $\mathbb{Z}^{d}$.

## References

  * [BDJ08] Alexis Ballier, Bruno Durand, and Emmanuel Jeandel.  Structural aspects of tilings.  In STACS 2008: 25th International Symposium on Theoretical Aspects of Computer Science, volume 1 of LIPIcs. Leibniz Int. Proc. Inform., pages 61–72. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2008.
  * [Ber66] R. Berger.  The undecidability of the domino problem.  Mem. Amer. Math. Soc., 66, 1966.
  * [Bha20] S. Bhattacharya.  Periodicity and decidability of tilings of $\mathbb{Z}^{2}$.  Amer. J. Math., 142(1):255–266, 2020.
  * [BN91] D. Beauquier and M. Nivat.  On translating one polyomino to tile the plane.  Discrete Comput. Geom., 6(6):575–592, 1991.
  * [CM99] E. Coven and A. Meyerowitz.  Tiling the integers with translates of one finite set.  J. Algebra, 212(1):161–174, 1999.
  * [EKL06] M. Einsiedler, M. Kapranov, and D. Lind.  Non-Archimedean amoebas and tropical varieties.  J. Reine Angew. Math., 601:139–157, 2006.
  * [Fri97] Shmuel Friedland.  On the entropy of $\mathbb{Z}^{d}$ subshifts of finite type.  Linear Algebra Appl., 252:199–220, 1997.
  * [GS87] B. Grünbaum and G. C. Shephard.  Tilings and patterns.  W. H. Freeman and Company, New York, 1987.
  * [GT21] R. Greenfeld and T. Tao.  The structure of translational tilings in $\mathbb{Z}^{d}$.  Discrete Anal., 16:1–28, 2021.
  * [GT22] R. Greenfeld and T. Tao.  A counterexample to the periodic tiling conjecture.  arXiv:2211.15847, 2022.
  * [GT23] R. Greenfeld and T. Tao.  Undecidable translational tilings with only two tiles, or one nonabelian tile.  Discrete and Computational Geometry, 2023.
  * [Ken92] R. Kenyon.  Rigidity of planar tilings.  Invent. Math., 107(3):637–651, 1992.
  * [Khe22] A. Khetan.  A periodicity result for tilings of $\mathbb{Z}^{3}$ by clusters of prime-squared cardinality.  arXiv:2109.14179, 2022.
  * [KM09] M. N. Kolountzakis and M. Matolcsi.  Algorithms for translational tiling.  J. Math. Music, 3(2):85–97, 2009.
  * [Kol04] M. N. Kolountzakis.  The study of translational tiling with Fourier analysis.  In Fourier analysis and convexity, Appl. Numer. Harmon. Anal., pages 131–187. Birkhäuser Boston, Boston, MA, 2004.
  * [KS20] J. Kari and M. Szabados.  An algebraic geometric approach to Nivat’s conjecture.  Inform. and Comput., 271:104481, 25, 2020.
  * [Lei02] A. Leibman.  Polynomial mappings of groups.  Israel J. Math., 129:29–60, 2002.
  * [ŁL22a] I. Łaba and I. Londner.  The Coven–Meyerowitz tiling conditions for 3 odd prime factors.  Invent. math., 10.1007/s00222-022-01169-y, 2022.
  * [ŁL22b] I. Łaba and I. Londner.  Splitting for integer tilings and the coven-meyerowitz tiling conditions.  arXiv:2207.11809v1, 2022.
  * [LM95] D. Lind and B. Marcus.  An introduction to symbolic dynamics and coding.  Cambridge University Press, Cambridge, 1995.
  * [LW96] J. C. Lagarias and Y. Wang.  Tiling the line with translates of one tile.  Invent. Math., 124:341–365, 1996.
  * [MS19] Tom Meyerovitch and Ville Salo.  On pointwise periodicity in tilings, cellular automata, and subshifts.  Groups Geom. Dyn., 13(2):549–578, 2019.
  * [New77] D. J. Newman.  Tesselation of integers.  J. Number Theory, 9(1):107–111, 1977.
  * [Rob71] R. M. Robinson.  Undecidability and nonperiodicity for tilings of the plane.  Invent. Math., 12:177–209, 1971.
  * [Sze98] M. Szegedy.  Algorithms to tile the infinite grid with finite clusters.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 137–145, 1998.
  * [Tao12] T. Tao.  Higher order Fourier analysis, volume 142 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2012.
  * [Tij95] R. Tijdeman.  Decomposition of the integers as a direct sum of two subsets.  In Number theory (Paris, 1992–1993), volume 215 of London Math. Soc. Lecture Note Ser., pages 261–276. Cambridge Univ. Press, Cambridge, 1995.
  * [War94] Thomas Ward.  Automorphisms of $\mathbb{Z}^{d}$-subshifts of finite type.  Indag. Math. (N.S.), 5(4):495–504, 1994.
  * [Wey16] Hermann Weyl.  Über die Gleichverteilung von Zahlen mod. Eins.  Math. Ann., 77(3):313–352, 1916.
  * [WvL84] H. A. G. Wijshoff and J. van Leeuwen.  Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino.  Inform. and Control, 62(1):1–25, 1984.
  * [Yif22] Y. Yifrach.  A note about weyl equidistribution theorem.  arXiv:2201.07138, 2022.