2.1 Multisets and mask polynomials

Let $M\geq 2$ be a fixed integer. Usually, we will work in either $\mathbb {Z}_M$ or $\mathbb {Z}_N$ for some $N\mid M$. In the context of the tiling problem, we reserve M for the tiling period and N for its divisors. We also reserve K for the number of the distinct prime divisors of M, and use $p_1,\dotsc ,p_K$ to denote those divisors, so that

$$ \begin{align*} M=\prod_{i=1}^K p_i^{n_i}, \end{align*} $$

where $p_1,\dotsc ,p_K$ are distinct primes and $n_1,\dotsc ,n_K\in \mathbb {N}$. We fix this notation and use it throughout the rest of the article. For a prime p, an integer m and a nonnegative integer $\alpha $, we will say that $p^\alpha \parallel m$ if $p^\alpha \mid m$ but $p^{\alpha +1}\nmid m$.

We use $A(X)$, $B(X)$, etc., to denote polynomials modulo $X^M-1$ with integer coefficients. If $A(X)$ is such a polynomial, we define its weight function $w_A:\mathbb {Z}_M\to \mathbb {Z}$ so that $w_A(a)$ is the coefficient of $X^a$ in $A(X)$. Thus $A(X)=\sum _{a\in \mathbb {Z}_M} w_A(a) X^a$. If A has $0$ or $1$ coefficients, then $w_A$ is the characteristic function of a set $A\subset \mathbb {Z}_M$. However, we will also consider polynomials with integer coefficients not necessarily equal to $0$ or $1$. In that case, $A(X)$ will correspond to a weighted multiset in $\mathbb {Z}_M$, which we will also denote by A, with weights $w_A(a)$ assigned to each $a\in \mathbb {Z}_M$. We will use $\mathcal {M}(\mathbb {Z}_M)$ to denote the family of all such weighted multisets in $\mathbb {Z}_M$, and reserve the notation $A\subset \mathbb {Z}_M$ for sets (with $0$ and $1$ weights). If $A\in \mathcal {M}(\mathbb {Z}_M)$, the polynomial $A(X)$ is sometimes called the mask polynomial of A. It will usually be clear from the context whether A refers to the weighted multiset or the corresponding polynomial; whenever there is any possibility of confusion, we will use A for the multiset and $A(X)$ for the polynomial.

If $N\mid M$, then any $A\in \mathcal {M}(\mathbb {Z}_M)$ induces a weighted multiset $A \bmod N$ in $\mathbb {Z}_N$, with the corresponding mask polynomial $A(X) \bmod \left (X^N-1\right )$, and induced weights

(2.1)$$ \begin{align} w_A^N(x)= \sum_{x'\in\mathbb{Z}_M: x'\equiv x\bmod N} w_A(x'),\qquad x\in\mathbb{Z}_N. \end{align} $$

For brevity, we will continue to write A and $A(X)$ for $A \bmod N$ and $A(X) \bmod \left (X^N-1\right )$, respectively, while working in $\mathbb {Z}_N$.

If $A,B\in \mathcal {M}(\mathbb {Z}_M)$, we will use $A+B$ to indicate the weighted multiset corresponding to the sum of mask polynomials, or, equivalently, the sum of weight functions:

$$ \begin{align*} w_{A+B}(x)=w_A(x)+w_B(x),\qquad (A+B)(X)=A(X)+B(X). \end{align*} $$

We will use the convolution notation $A*B$ to denote the weighted sumset of A and B, so that $(A*B)(X)=A(X)B(X)$ and

$$ \begin{align*} w_{A*B}(x)=(w_A*w_B)(x)=\sum_{y\in\mathbb{Z}_M} w_A(x-y)w_B(y). \end{align*} $$

If one of the sets is a singleton, say $A=\{x\}$, we will simplify the notation and write $x*B=\{x\}*B$. The direct sum notation $A\oplus B$ is reserved for tilings – that is, $A\oplus B=\mathbb {Z}_M$ means that $A,B\subset \mathbb {Z}_M$ are both sets and $A(X)B(X)=\frac {X^M-1}{X-1} \bmod \left (X^M-1\right )$.

Since we will not need to use derivatives of polynomials in this article, we will use notation such as $A'$, $A''$, etc., to denote multisets and polynomials that need not have anything to do with the derivatives $\frac {d}{dX}A(X)$, $\frac {d^2}{dX^2}A(X)$ and so on.

2.2 Array coordinates

Suppose that $M=\prod _{i=1}^K p_i^{n_i}$, where $p_1,\dotsc ,p_K$ are distinct primes and $n_i\in \mathbb {N}$. By the Chinese remainder theorem, we have

$$ \begin{align*} \mathbb{Z}_M=\bigoplus_{i=1}^K \mathbb{Z}_{p_i^{n_i}}, \end{align*} $$

which we represent geometrically as a K-dimensional lattice. The tiling $A\oplus B=\mathbb {Z}_M$ can then be interpreted as a tiling of that lattice.

It will be useful to have an explicit coordinate system on $\mathbb {Z}_M$. We fix one as follows. Let $M_i = M/p_i^{n_i} = \prod _{j\neq i} p_j^{n_j}$; then each $x\in \mathbb {Z}_M$ can be written uniquely as

$$ \begin{align*} x=\sum_{i=1}^K \pi_i(x) M_i,\quad \pi_i(x)\in \mathbb{Z}_{p_i^{n_i}}. \end{align*} $$

The mapping $x\to (\pi _1(x),\dotsc ,\pi _k(x))$ identifies x with an element of $\mathbb {Z}_{p_1^{n_1}}\times \dotsb \times \mathbb {Z}_{p_K^{n_K}}$. We will refer to the K-tuple $(\pi _1(x),\dotsc ,\pi _K(x))$ as the M-array coordinates of x.

We state a few easy properties for future reference.

Each coordinate $\pi _i(x)$ of $x\in \mathbb {Z}_M$ can be subdivided further into digits as follows. With $\mathbb {Z}_{p_i^{n_i}}$ represented as $\left \{0,1,\dotsc , p_i^{n_i} -1\right \}$ with addition and multiplication modulo $p_i^{n_i}$, we can write uniquely

$$ \begin{align*} \pi_i(x) = \sum_{j=0}^{n_i-1} \pi_{i,j}(x) p_i^{j},\quad \pi_{i,j}(x) \in\{0,1,\dotsc,p_i-1\}. \end{align*} $$

Observe that $(x -x' ,M)=\prod _{j=1}^K p_i^{\gamma _i}$ if and only if for each $i=1,\dotsc ,K$,

(2.2)$$ \begin{align} \gamma_i = \begin{cases} \min\left\{j: \pi_{i,j}(x)\neq \pi_{i,j}(x') \right\} &\text{if } \pi_i(x)\neq \pi_i(x'), \\ n_i &\text{if } \pi_i(x)=\pi_i(x'). \end{cases} \end{align} $$

2.3 Grids, planes, lines, fibers

Definition 2.2. Let $D\mid M$. A D-grid in $\mathbb {Z}_M$ is a set of the form

$$ \begin{align*} \Lambda(x,D):= x+D\mathbb{Z}_M=\{x'\in\mathbb{Z}_M: D\mid(x-x')\} \end{align*} $$

for some $x\in \mathbb {Z}_M$.

An important case of interest is as follows. Let $N\mid M$. If $N=p_1^{\alpha _1} \dotsm p_K^{\alpha _K}$, with $\alpha _1,\dotsc ,\alpha _K\geq 0$, we define

$$ \begin{align*} D(N):= p_1^{\gamma_1} \dotsm p_K^{\gamma_K}, \end{align*} $$

where $\gamma _i=\max (0,\alpha _i-1)$ for $i=1,\dotsc , K$. Then a $D(N)$-grid is a ‘top-level’ grid on the scale N, and a natural setting to work on that scale.

While a grid $\Lambda $ is always an arithmetic progression in $\mathbb {Z}_M$, it is often helpful to represent $\mathbb {Z}_M$ by a K-dimensional coordinate array as in Section 2.2 and, accordingly, assign a geometric interpretation to $\Lambda $. We point out several useful special cases.

A line through $x\in \mathbb {Z}_M$ in the $p_i$ direction is the set

$$ \begin{align*} \ell_i(x):= \Lambda(x,M_i), \end{align*} $$

and a $(K-1)$-dimensional plane through $x\in \mathbb {Z}_M$ perpendicular to the $p_i$ direction is a set of the form

(2.3)$$ \begin{align} \Pi\left(x,p_i^{\alpha_i}\right):=\Lambda\left(x,p_i^{\alpha_i}\right). \end{align} $$

Note that formula (2.3) defines a plane on the scale $M_ip_i^{\alpha _i}$, which may be different from M.

An M-fiber in the $p_i$ direction is a set of the form $x*F_i$, where $x\in \mathbb {Z}_M$ and

(2.4)$$ \begin{align} F_i=\{0,M/p_i,2M/p_i,\dotsc,(p_i-1)M/p_i\}. \end{align} $$

Thus $x*F_i=\Lambda (x,M/p_i)$. (More complicated multiscale fiber chains will be defined later.) A set $A\subset \mathbb {Z}_M$ is M-fibered in the $p_i$ direction if there is a subset $A'\subset A$ such that $A=A'*F_i$.

2.4 Cyclotomic polynomials and cyclotomic divisibility

We state a few basic facts about cyclotomic polynomials for future reference. By equation (1.2), we have

(2.5)$$ \begin{align} 1+X+X^2+\dotsb+X^{n-1}=\prod_{s\mid n,s\neq 1}\Phi_s(X). \end{align} $$

In particular, if p is a prime number, then $\Phi _p(X)=1+X+\dotsb +X^{p-1}$ and, more generally, by induction,

$$ \begin{align*} \Phi_{p^\alpha}(X)=\Phi_p\left(X^{p^{\alpha-1}}\right) = 1 + X^{p^{\alpha-1}} + X^{2p^{\alpha-1}} + \dotsb + X^{(p-1)p^{\alpha-1}}, \quad \alpha\geq 1. \end{align*} $$

Thus $\Phi _{p^\alpha }(1)=p$, and this together with equation (2.5) implies that $\Phi _s(1)=1$ for all s that are not prime powers.

Suppose that $A\oplus B=\mathbb {Z}_M$, with $M=\prod _{i=1}^K p_i^{n_i}$ as before. By equation (1.1), we have $A(X)B(X)=1+X+\dotsb +X^{M-1} \bmod \left (X^M-1\right )$. For every prime power $s=p^\alpha \mid M$, we must have $\Phi _s(X)\mid A(X)B(X)$, so that

$$ \begin{align*} M= \prod_{i=1}^K \prod_{\alpha_i=1}^{n_i} \Phi_{p_i^{\alpha_i}}(1) \mid A(1)B(1)=\lvert A\rvert\lvert B\rvert=M. \end{align*} $$

It follows that

$$ \begin{align*} \lvert A\vert= \prod_{s\in S_A} \Phi_s(1) \end{align*} $$

and similarly for B, with $S_A$, $S_B$ defined as in Theorem 1.1; this is the proof of the tiling condition (T1) given in [Reference Coven and Meyerowitz2]. Moreover, for any prime power $s=p^{\alpha _i}\mid M$, we have that $\Phi _s(X)$ divides exactly one of $A(X)$ and $B(X)$. (This is not true for $s\mid M$ with two or more distinct prime factors. For such s, the corresponding cyclotomic polynomial $\Phi _s(X)$ may divide either one or both of $A(X)$ and $B(X)$.)

Divisibility by prime-power cyclotomics has the following combinatorial interpretation. For $A\subset \mathbb {Z}_M$, the condition $\Phi _{p_i}\mid A$ means that the elements of A are uniformly distributed modulo $p_i$, so that

$$ \begin{align*} \lvert A\cap\Pi(x,p_i)\rvert=\lvert A\rvert/p_i \quad \forall x\in\mathbb{Z}_M. \end{align*} $$

More generally, for $1\leq \alpha \leq n_i$, we have $\Phi _{p_i^\alpha }(X)\mid A(X)$ if and only if

(2.6)$$ \begin{align} \left\lvert A\cap \Pi\left(x,p_i^\alpha\right)\right\rvert=\frac{1}{p_i} \left\lvert A\cap \Pi\left(x,p_i^{\alpha-1}\right)\right\rvert \quad \forall x\in\mathbb{Z}_M, \end{align} $$

so that the elements of A are uniformly distributed mod $p_i^\alpha $ within each residue class mod $p_i^{\alpha -1}$. In particular, this implies the following bound on the number of points of a tile in a plane on a scale $M_ip_i^{n_i-\alpha _i}$ or, equivalently, in an arithmetic progression of step $p_i^{n_i-\alpha _i}$:

Lemma 2.3 Plane bound

Let $A\oplus B=\mathbb {Z}_M$, where $M=\prod _j p_j^{n_j}$ and $\lvert A\rvert =\prod _j p_j^{\beta _j}$. Then for every $x\in \mathbb {Z}_M$ and $0\leq \alpha _i\leq n_i$ we have

(2.7)$$ \begin{align} \left\lvert A\cap\Pi\left(x,p_i^{n_i-\alpha_i}\right)\right\rvert\leq p_i^{\alpha_i}\prod_{\nu\neq i}p_\nu^{\beta_\nu}. \end{align} $$

This bound is, in general, sharp. For example, if $A\subset p_i^{n_i-1}\mathbb {Z}_M$ and $\Phi _{p_i^{n_i}}\mid A$, then $\left \lvert A\cap \Pi \left (x,p_i^{n_i}\right )\right \rvert =\lvert A\rvert /p_i$, so that estimate (2.7) holds with equality for $\alpha _i=0$. Examples of sets $A\subset \mathbb {Z}_M$ with the foregoing properties are easy to construct using the standard tiling sets defined in Section 3.

We also note the following. Let $N\mid M$. Then the condition

$$ \begin{align*} \Phi_s\mid A \quad \forall s\mid N, s\neq 1, \end{align*} $$

means that $1+X+\dotsb +X^{N-1}$ divides $A(X)$ or, equivalently, that the elements of A are uniformly distributed mod N. For example, let $N= p_1p_2\dotsm p_K$. Suppose that $\lvert A\rvert =N$ and that $\Phi _{p_i}\mid A$ for all $i=1,\dotsc ,K$. Then A satisfies (T2) if and only if $\Phi _s\mid A$ for all $s\mid N$ with $s\neq 1$ or, equivalently, if and only if each residue class mod N contains exactly one element of A.

2.5 Divisor set and divisor exclusion

Definition 2.4 Divisor set

For a set $A\subset \mathbb {Z}_M$, define

(2.8)$$ \begin{align} \mathrm{Div}(A)=\mathrm{Div}_M(A):=\{(a-a',M): a,a'\in A\}. \end{align} $$

Informally, we will refer to the elements of $\mathrm {Div}(A)$ as the divisors of A or differences in A. We also define

$$ \begin{align*} \mathrm{Div}_N(A):=\{(a-a',N): a,a'\in A\} \end{align*} $$

for $A\subset \mathbb {Z}_M$ and $N\mid M$.

Divisor sets will be a key concept in our analysis, thanks to the following theorem due to Sands [Reference Sands37]:

Theorem 2.5 Divisor exclusion [Reference Sands37]

If $A,B\subset \mathbb {Z}_M$ are sets, then $A\oplus B=\mathbb {Z}_M$ if and only if $\lvert A\rvert \lvert B\rvert =M$ and

(2.9)$$ \begin{align} \mathrm{Div}(A) \cap \mathrm{Div}(B)=\{M\}. \end{align} $$

An alternative proof of Sands’ theorem, based on Theorem 4.7 and due to [Reference Granville, Łaba and Wang11], is included in Remark 4.10.

3.1 Standard tiling complements

We continue to assume that $M=\prod _{i=1}^K p_i^{n_i}$, where $p_1,\dotsc ,p_K$ are distinct primes and $n_i>0$. We equip $\mathbb {Z}_M$ with the array coordinate system from Section 2.2 and use the notation of that section. Recall also that the divisor set ${\mathrm {Div}}(A)$ for a set $A\subset \mathbb {Z}_M$ was defined in definition (2.8) which is a little bit circular.

Definition 3.1. Let $A,B$ be sets in $\mathbb {Z}_M$ such that $A\oplus B=\mathbb {Z}_M$. Let

$$ \begin{align*} \mathfrak{A}_i(A) =\left\{\alpha_i \in \{1,2,\dotsc,n_i\}: \Phi_{p_i^{\alpha_i}}(X) \mid A(X) \right\}. \end{align*} $$

The standard tiling set $A^\flat $ is defined via its mask polynomial

(3.1)$$ \begin{align} A^\flat(X) &= \prod_{i=1}^{K} \prod_{\alpha_i\in \mathfrak{A}_i(A)} \Phi_{p_i}\left(X^{M_ip_i^{\alpha_i-1}}\right) \nonumber\\ &= \prod_{i=1}^{K} \prod_{\alpha_i\in \mathfrak{A}_i(A)} \left(1+ X^{M_ip_i^{\alpha_i-1}} + \dotsb + X^{\left(p_i-1\right)M_ip_i^{\alpha_i-1}} \right). \end{align} $$

Figure 1 The standard sets $A^\flat ,B^\flat \subset \mathbb {Z}_{p_i^2p_j^2}$ with $p_i=3, p_j=5$ and $\Phi _{p_i^2}\Phi _{p_j^2}\mid A,\Phi _{p_i}\Phi _{p_j}\mid B$.

Lemma 3.3. Let

$$ \begin{align*} \Psi(X)=1+X^{Np^{\alpha-1}} + X^{2Np^{\alpha-1}} + \dotsb + X^{(p-1)Np^{\alpha-1}} = \Phi_{p}\left(X^{Np^{\alpha-1}}\right), \end{align*} $$

where $(N,p)=1$. Then $\Phi _s(X)\mid \Psi (X)$ if and only if $s=dp^\alpha $ for some $d\mid N$.

Observe that the standard set $A^\flat $, while not necessarily a grid, is highly structured. In terms of array coordinates, we have

(3.2)$$ \begin{align} A^\flat &= \left\{ x\in\mathbb{Z}_M: \pi_i(x)=\sum_{\alpha_i\in \mathfrak{A}_i(A)} \pi_{i,\alpha_i-1}(x)p_i^{\alpha_i-1}, \quad \pi_{i,\alpha_i-1}(x) \in\{ 0,1,\dotsc, p_i-1 \} \right\} \nonumber\\ &= \left\{x\in \mathbb{Z}_M:\ \pi_{i,\alpha_i-1}(x) =0 \text{ for all }i,\alpha_i \text{ such that }\alpha_i\notin \mathfrak{A}_i(A)\right\}. \end{align} $$

The standard divisor set for A is

(3.3)$$ \begin{align} \mathrm{Div} \left(A^\flat \right) = \left\{ \prod_{i=1}^K p_i^{\alpha_i-1}: \alpha_i\in \mathfrak{A}_i(A)\cup\{n_i+1\},\quad i=1,\dotsc,K \right\}. \end{align} $$

We will refer to the elements of $\mathrm {Div} (A^\flat )$ as standard divisors of A. The set $B^\flat $ is defined similarly.

With these definitions, we have the following alternative formulations of (T2):

Proof. The equivalence between (i) and (ii) is a special case of Theorem 2.5. The implication (iii) $\Rightarrow $ (ii) follows from the construction in the proof of [Reference Coven and Meyerowitz2, Theorem A]; the converse implication (ii) $\Rightarrow $ (iii) was not pointed out there, but it also follows from the same construction. Specifically, by Lemma 3.3, $A^\flat (X)$ is divisible by every cyclotomic polynomial $\Phi _s$ such that $p_i^\alpha \parallel s$ for some $i\in \{1,\dotsc ,K\}$ and $\alpha \geq 1$ such that $\Phi _{p_i^\alpha }\mid A$. In other words, the only s such that $s\mid M$ but $\Phi _s$ does not divide $A(X)$ are those with $s=\prod _{i=1}^k p_i^{\beta _i}$, where for each i we have either $\beta _i=0$ or $\Phi _{p_i^{\beta _i}}(X)\mid B(X)$. Let $\mathcal {S}_B$ be the set of such s.

If B satisfies (T2), then all $\Phi _s$ with $s\in \mathcal {S}_B$ divide $B(X)$, which implies (ii). Conversely, suppose that (ii) holds. Then each $\Phi _s$ with $s\mid M$ has to divide $A(X)B(X)$. By Lemma 3.3 again, if $s\in \mathcal {S}_B$, then $\Phi _s$ does not divide $A(X)$, so it must divide $B(X)$. Therefore (T2) holds for B.

For (iv), we shall prove that (ii) implies (iv) and (iv) implies (i). Suppose that (ii) holds. We first claim that

(3.4)$$ \begin{align} \left\lvert B\cap\left(x*A^\flat\right)\right\rvert\leq 1\quad \forall x\in\mathbb{Z}_M. \end{align} $$

Indeed, if $b,b'\in B\cap (x*A^\flat )$, then $b=x+a$ and $b'=x+a'$ for some $a,a'\in A^\flat $, so that $b-a=b'-a'$, contradicting (ii) unless $b=b'$ and $a=a'$.

It remains to prove that $(x_0*A^\flat )\cap B\neq \emptyset $ for each $x_0\in \mathbb {Z}_M$. Set $x_0\in \mathbb {Z}_M$. Since $\mathrm {Div}(B)=\mathrm {Div}(-B)$, we have $A^\flat \oplus (-B)=\mathbb {Z}_M$ by Theorem 2.5. It follows that there must exist $a_0\in A^\flat$ and $-b_0\in (-B)$ such that $a_0-b_0=-x_0$. The latter means $a_0+x_0=b_0$, implying $(x_0*A^\flat )\cap B\neq \emptyset $, as claimed. Hence (iv) follows.

Finally, suppose that (i) fails. Then there exist $b,b'\in B$ and $m\in \mathrm {Div} (A^\flat )\setminus \{M\}$ such that $(b-b',M)=m$. But then $b,b'\in B\cap (b*A^\flat )$ with $b\neq b'$, contradicting (iv).

It is tempting to try to prove that if $A\oplus B=\mathbb {Z}_M$, then we should have $\mathrm {Div} (A^\flat )\subseteq {\mathrm {Div}}(A)$. By Proposition 3.4, this would imply that B satisfies (T2). However, the following example shows that $\mathrm {Div}(A)$ does not in fact have to contain $\mathrm {Div}(A^\flat )$:

3.2 (T2)-equivalence

Definition 3.7. We say that the tilings $A\oplus B=\mathbb {Z}_M$ and $A'\oplus B=\mathbb {Z}_M$ are (T2)-equivalent if

(3.5)$$ \begin{align} A\text{ satisfies (T2)}\Leftrightarrow A'\text{ satisfies (T2).} \end{align} $$

Since the sets A and $A'$ tile the same group $\mathbb {Z}_M$ with the same tiling complement B, they must have the same cardinality and the same prime-power cyclotomic divisors, as discussed in Section 2.4. For brevity, we will sometimes say simply that A is (T2)-equivalent to $A'$ if both M and B are clear from context.

In practice, $A'$ will be a set obtained from A using certain permitted manipulations such as fiber shifts. We will use (T2)-equivalence to reduce proving (T2) for the initial tiling to proving (T2) for related tilings that are increasingly more structured. In particular, the following reduction is sufficient to prove (T2) for both sets in the given tiling:

4.1 Box-product characterisation of tiling

We continue to assume that $M=\prod _{i=1}^K p_i^{n_i}$, where $p_1,\dotsc ,p_K$ are distinct primes. We will use $\phi $ and $\mu $ to denote, respectively, the Euler totient function and the Möbius function: if $n=\prod _{j=1}^L q_j^{r_j}$, where $q_1,\dotsc ,q_L$ are distinct primes, then

$$ \begin{align*} \phi(n)&=n \prod_{j=1}^L \frac{q_j-1}{q_j} = \prod_{j=1}^L \left(q_j-1\right)q_j^{r_j-1},\\ \mu(n)&=\begin{cases} (-1)^L & \text{if }r_1=r_2=\dotsb=r_L=1, \\ 0 & \text{if } \exists j\in\{1,\dotsc,L\} \text{ such that }r_j\geq 2. \end{cases} \end{align*} $$

Let $N\mid M$. Reordering the primes if necessary, we may assume that $N=p_1^{\alpha _1} \dotsm p_k^{\alpha _k}$, with $1\leq k\leq K$ and $\alpha _1,\dotsc ,\alpha _k\geq 1$.

Definition 4.1 N-boxes

An N-box is a k-dimensional matrix

$$ \begin{align*} \mathbb{A}=\left( \mathbb{A}_{\left(\gamma_1,\dotsc,\gamma_k\right)} \right) _{0\leq \gamma_j\leq \alpha_j, j=1,\dotsc,k} \end{align*} $$

of size $(\alpha _1+1)\times \dotsm \times (\alpha _k+1)$, with entries $\mathbb {A}_{\left (\gamma _1,\dotsc ,\gamma _k\right )}\in \mathbb {R}$. Since each multi-index $(\gamma _1,\dotsc ,\gamma _k)$ with $0\leq \gamma _j\leq \alpha _j$ can be uniquely associated with a divisor m of N given by $m=p_1^{\gamma _1}\dotsm p_k^{\gamma _k}$, we will use such divisors to index the entries of $\mathbb {A}$, so that

$$ \begin{align*} \mathbb{A} = ( \mathbb{A}_m )_{m\mid N}, \quad \mathbb{A}_m = \mathbb{A}_{\left(\gamma_1,\dotsc,\gamma_k\right)} \text{ for } m=p_1^{\gamma_1}\dotsm p_k^{\gamma_k}. \end{align*} $$

For any $N\mid M$, N-boxes form a vector space over $\mathbb {R}$, with addition of boxes and multiplication of a box by a scalar defined in the obvious way. We also equip this space with an inner product structure as follows:

Definition 4.2 Box product

If $\mathbb {A}$ and $\mathbb {B}$ are N-boxes, define

(4.1)$$ \begin{align} \langle \mathbb{A}, \mathbb{B} \rangle = \sum_{m\mid N} \frac{1}{\phi(N/m)} \mathbb{A}_m \mathbb{B}_m. \end{align} $$

Of course, this equation depends on N, but since N is determined by the fact of $\mathbb {A}$ and $\mathbb {B}$ being N-boxes, we will not use additional subscripts or superscripts to indicate that.

The N-boxes associated with multisets in $\mathbb {Z}_N$ are as follows:

Definition 4.3 Boxes associated with multisets

Set $A\in \mathcal {M}(\mathbb {Z}_M)$ and let $N\mid M$. Consider the induced multiset $A\in \mathcal {M}(\mathbb {Z}_N)$, with the weight function mod N defined in equation (2.1). For $x\in \mathbb {Z}_N$, define $\mathbb {A}^N[x] = \left (\mathbb {A}^N_m[x]\right )_{m\mid N}$, where

$$ \begin{align*} \mathbb{A}^N_m[x] = \sum_{a\in \mathbb{Z}_N: (x-a,N)=m} w^N_A(a). \end{align*} $$

In particular, if $A\subset \mathbb {Z}_N$ is a set, we have

$$ \begin{align*} \mathbb{A}^N_m[x] & = \# \{a\in A: (x-a,N)=m \}. \end{align*} $$

If $N=M$, we will skip the superscript and write $\mathbb {A}_m[x]=\mathbb {A}^M_m[x]$ whenever there is no possibility of confusion.

Theorem 4.4 explains the reason for Definition 4.2. The theorem is based on [Reference Granville, Łaba and Wang11, Theorem 1] (see Sections 4.2 and 4.3 for details). The equivalence between $A\oplus B=\mathbb {Z}_M$ and the condition in (ii) provides an alternative proof of Theorem 2.5; however, Sands’ proof is easier and does not require Theorem 4.4. The point of Theorem 4.4 is that tiling also implies the formally stronger condition (4.2) for all $N\mid M$ and $x,y\in \mathbb {Z}_M$.

Corollary 4.5. Under the assumptions of Theorem 4.4, let $\mathcal {L}^N(A)$ be the linear space spanned by the boxes $\mathbb {A}^N[x]$ – that is,

$$ \begin{align*} \mathcal{L}^N(A)=\left\{ \sum_{x\in\mathbb{Z}_N} c_x \mathbb{A}^N[x]: c_x\in\mathbb{R}\right\}, \end{align*} $$

and similarly for B. Then for any N-boxes $\mathbb {A}\in \mathcal {L}^N(A)$ and $\mathbb {B}\in \mathcal {L}^N(B)$, we have

(4.4)$$ \begin{align} \langle \mathbb{A}, \mathbb{B} \rangle = \frac{1}{N}\Sigma(\mathbb{A}) \Sigma(\mathbb{B}), \end{align} $$

where $\Sigma (\mathbb {A})=\sum _{m\mid N} \mathbb {A}_m$.

N-boxes $\mathbb {A}^N[x]$, $x\in \mathbb {Z}_M$, are a convenient way of encoding structural information about A. Theorem 4.4 provides a tiling criterion for $A\oplus B=\mathbb {Z}_M$ in terms of the box product, and it is also possible to express cyclotomic divisibility in terms of N-boxes. However, this convenience comes with some loss of information. In [Reference Łaba and Londner24], we have to work with the actual sets A and B, not just with the N-boxes representing them. We do not know whether it is possible to give a proof of properties such as (T2) purely in terms of the N-boxes associated with the sets.

4.2 A Fourier-analytic identity

Fix $N=p_1^{\alpha _1} \dotsm p_k^{\alpha _k}$, where $p_1,\dotsc ,p_k$ are distinct primes and $\alpha _1,\dotsc ,\alpha _k\in \mathbb {N}$. Set $A,B,C,D\in \mathcal {M}(\mathbb {Z}_N)$. For $m\mid N$, we define

$$ \begin{align*} \mathbb{A}_m^N [C] :=\sum_{c\in C}\mathbb{A}^N_m[c] w_C(c) =\sum_{a,c\in\mathbb{Z}_N} w_A(a) w_C(c) \mathbf{1}_{(a-c,N)=m}. \end{align*} $$

In particular, if $A(X)$ is a polynomial with $0$ or $1$ coefficients corresponding to a set $A\subset \mathbb {Z}_N$, then

$$ \begin{align*} \mathbb{A}_m^N[A]= \#\{(a,a')\in A\times A: (a-a',N)=m\}. \end{align*} $$

This defines N-boxes in the sense of Definition 4.3, and in particular we may consider the box product

$$ \begin{align*} \left\langle \mathbb{A}^N[C], \mathbb{B}^N[D] \right\rangle = \sum_{m|N} \frac{1}{\phi(N/m)} \mathbb{A}_m^N[C] \mathbb{B}_m^N[D]. \end{align*} $$

The following theorem is a slight generalisation of the main identity from [Reference Granville, Łaba and Wang11]. Specifically, [Reference Granville, Łaba and Wang11, Theorem 1] states that equation (4.6) holds when $A(X)$ and $B(X)$ are polynomials corresponding to multisets $A,B\subset \mathbb {Z}_N$. We will need an extension of it to four polynomials, not necessarily with nonnegative coefficients. The proof is essentially the same, but since [Reference Granville, Łaba and Wang11] remains unpublished, we include it here for completeness.

Theorem 4.7. Let $A(X),B(X),C(X),D(X)$ be polynomials modulo $X^N-1$ with integer coefficients. Then

(4.5)$$ \begin{align} \left\langle \mathbb{A}^N[C], \mathbb{B}^N[D] \right\rangle=\sum_{d\mid N} \frac{1}{N\phi(d) } \left[ \sum_{\zeta:\Phi_d(\zeta)=0} A(\zeta)\overline{C(\zeta)} \right] \left[ \sum_{\zeta:\Phi_d(\zeta)=0} B(\zeta)\overline{D(\zeta)} \right]. \end{align} $$

In particular,

(4.6)$$ \begin{align} \left\langle \mathbb{A}^N[A], \mathbb{B}^N[B] \right\rangle =\sum_{d\mid N} \frac{1}{N\phi(d) } \mathcal{E}_d(A) \mathcal{E}_d(B), \end{align} $$

where

$$ \begin{align*} \mathcal{E}_d(A)=\sum_{\zeta:\Phi_d(\zeta)=0} \lvert A(\zeta)\rvert^2. \end{align*} $$

The rest of this section is devoted to the proof of Theorem 4.7. We will use the discrete Fourier transform in $\mathbb {Z}_N$: If $f:\mathbb {Z}_N\to \mathbb {C}$ is a function, then

$$ \begin{align*} \widehat{f}(\xi)= \sum_{x\in\mathbb{Z}_N} f(x) e^{2\pi i x\xi/N},\quad \xi\in\mathbb{Z}_N. \end{align*} $$

Lemma 4.8. Define

$$ \begin{align*} \Lambda_m &:=\{x\in\mathbb{Z}_N: m\mid x\}, \\ H_m &:= \{x\in\mathbb{Z}_N: (x,N)=m\} = \Lambda_m \setminus \bigcup_{m': m\mid m'\mid N,m'\neq m} \Lambda_{m'}. \end{align*} $$

Then $\widehat {\mathbf {1}_{H_m}}(\xi )=G_\xi (N/m)$, where

(4.7)$$ \begin{align} G_\xi(v)=\sum_{d\mid(v,\xi)} \mu(v/d) d. \end{align} $$

Proof. Using the fact that

$$ \begin{align*} \widehat{\mathbf{1}_{\Lambda_m}} (\xi)= \frac{N}{m} \mathbf{1}_{\Lambda_{N/m}}(\xi), \end{align*} $$

we get by inclusion-exclusion

$$ \begin{align*} \widehat{\mathbf{1}_{H_m}}(\xi) &= \sum_{d\mid\frac{N}{m}} \mu(d) \widehat{\mathbf{1}_{\Lambda_{md}}}(\xi) \\ &= \sum_{d\mid\frac{N}{m}} \mu(d) \frac{N}{md} \mathbf{1}_{\Lambda_{N/md}}(\xi) \\ &= \sum_{d'\mid\frac{N}{m} } \mu\left( \frac{N}{md'} \right) d' \mathbf{1}_{\Lambda_{d}}(\xi) \\ &= \sum_{d'\mid \left(\frac{N}{m},\xi\right) } \mu\left( \frac{N}{md'} \right) d' \\ &= G_\xi(N/m). \end{align*} $$

Proposition 4.9. We have

(4.8)$$ \begin{align} \sum_{v\mid N} \frac{1}{\phi(v)} G_\xi(v) G_{\xi'}(v) = \begin{cases} \frac{N}{\phi(N/d)} & \text{if } (\xi,N)=(\xi',N)=d, \\ 0 & \text{if } (\xi,N)\neq (\xi',N). \end{cases} \end{align} $$

Proof. We first claim that for every $\xi $, the function $G_\xi (v)$ is multiplicative in v. Indeed, let $(x,y)=1$, $(x,\xi )=t$ and $(y,\xi )=s$. Then $(t,s)=1$ and $(xy,\xi )=ts$. Writing $u=u^\prime \cdot u^{\prime \prime }$, $u^\prime \mid x$ and $u^{\prime \prime }\mid y$, we get

$$ \begin{align*} G_\xi(xy)=\sum_{u\mid(xy,\xi)} \mu\left(\frac{xy}{u}\right) u=\sum_{u^\prime\mid(x,\xi),u^{\prime\prime}\mid(y,\xi)} \mu\left(\frac{x}{u^\prime}\right) \mu\left(\frac{y}{u^{\prime\prime}}\right) u^\prime u^{\prime\prime}=G_\xi(x)G_\xi(y). \end{align*} $$

Therefore, $G_\xi (v)$ is entirely determined by its values $G_\xi (v)$ on prime powers $p_i^j$, $j=0,1,\dotsc ,\alpha _i$, $i=1,\dotsc ,k$. Let $\xi =p_1^{\nu _1}\dotsm p_k^{\nu _k}$. Then $p_i^\kappa \parallel \left (p_i^j,\xi \right )$ for $\kappa =\min (j,\nu _i)$. If $j=0$, we have $\kappa =0$ and $G_\xi \left (p_i^0\right )=G_\xi (1)=1$. If $j\geq 1$, we have

$$ \begin{align*} G_\xi\left(p_i^j\right)=\sum_{u\mid p_i^\kappa}\mu\left(\frac{p_i^j}{u}\right) u= \begin{cases} p_i^j -p_i^{j-1} & \text{if } \kappa=j,\\ -p_i^{j-1} & \text{if } \kappa=j-1,\\ 0 & \text{if } \kappa <j, \end{cases} \end{align*} $$

which is equivalent to

(4.9)$$ \begin{align} G_\xi\left(p_i^j\right)= \begin{cases} p_i^j -p_i^{j-1}=\phi\left(p_i^j\right) & \text{if } j\leq \nu_i,\\ -p_i^{\nu_i} & \text{if } j=\nu_i+1,\\ 0 & \text{if } j>\nu_i+1. \end{cases} \end{align} $$

Next, if F is a multiplicative function, then

$$ \begin{align*} \sum_{v\mid N}F(v) =\sum_{0\leq j_1\leq \alpha_1, \dotsc, 0\leq j_k\leq \alpha_k} F\left(p_{1}^{j_1}\dotsm p_{k}^{j_k}\right) =\prod_{i=1}^k \left(\sum_{j_i=0}^{\alpha_i}F\left(p_i^{j_i}\right)\right). \end{align*} $$

Applying this with $F(v)=G_\xi (v)G_{\xi '}(v)$ for fixed $\xi ,\xi '$, we get

(4.10)$$ \begin{align} \sum_{v\mid N} \frac{1}{\phi(v)} G_\xi (v) G_{\xi^\prime} (v) =\prod_{i=1}^k \left( \sum_{j_i=0}^{\alpha_i} \frac{1}{\phi\left(p_i^{j_i}\right)}G_\xi \left(p_i^{j_i}\right)G_{\xi^\prime} \left(p_i^{j_i}\right) \right). \end{align} $$

Fix a prime divisor $p_i\mid N$, and consider the corresponding factor in equation (4.10). Suppose that $0\leq \nu ,\nu ' \leq \alpha _i$ are such that $p_i^\nu \parallel \xi , p_i^{\nu '} \parallel \xi ^\prime $. Without loss of generality, we may assume that $\nu \leq \nu '$. In accordance with equation (4.9), we have three cases.

• • If $\nu <\nu '\leq \alpha _i$, then $\nu +1\leq \alpha _i$ and

  $$ \begin{align*} \sum_{j=0}^{\alpha_i} \frac{1}{\phi\left(p_i^j\right)} G_\xi\left(p_i^j\right) G_{\xi^\prime}\left(p_i^j\right) & =1+\sum_{j=1}^{\nu} \frac{1}{\phi\left(p_i^j\right)} \phi\left(p_i^j\right) \left(p_i^j -p_i^{j-1}\right) +\frac{1}{\phi\left(p_i^{\nu+1}\right)} \phi\left(p_i^{\nu+1}\right) \left(-p_i^n\right)\\ & = 1+\sum_{j=1}^{\nu} \left(p_i^j -p_i^{j-1}\right) -p^\nu=0. \end{align*} $$

• • If $\nu =\nu ' < \alpha _i$, then $\nu +1=\nu ' +1 \leq \alpha _i$ and

  $$ \begin{align*} \sum_{j=0}^{\alpha_i} \frac{1}{\phi\left(p_i^j\right)} G_\xi\left(p_i^j\right) G_{\xi^\prime}\left(p_i^j\right) =1+\sum_{j=1}^{\nu} \left(p_i^j-p_i^{j-1}\right)+\frac{1}{p_i^{\nu+1}-p_i^\nu} \left(-p_i^\nu\right)^2=\frac{p_i^{\nu+1}}{p_i-1}. \end{align*} $$

• • If $\nu =\nu '=\alpha _i$, then

  $$ \begin{align*} \sum_{j=0}^{\alpha_i} \frac{1}{\phi\left(p_i^j\right)} G_\xi\left(p_i^j\right) G_{\xi^\prime}\left(p_i^j\right) =1+\sum_{j=1}^{\alpha_i} \left(p_i^j-p_i^{j-1}\right)=p_i^{\alpha_i}. \end{align*} $$

Since

$$ \begin{align*} \frac{p_i^{\alpha_i}}{\phi\left(p_i^{\alpha_i-\nu}\right)}= \begin{cases} p^{\alpha_i} & \text{if }\nu=\alpha_i, \\ \frac{p^{\alpha_i}}{\left(p_i-1\right)p_i^{\alpha_i-\nu-1}} = \frac{p_i^{\nu+1}}{p_i-1} & \text{if } \nu<\alpha_i, \end{cases} \end{align*} $$

we conclude that

$$ \begin{align*} \sum_{j=0}^{\alpha_i} \frac{1}{\phi\left(p_i^j\right)} G_\xi\left(p_i^j\right) G_{\xi^\prime}\left(p_i^j\right)= \begin{cases} 0 & \text{if }\nu\neq\nu',\\ \frac{p_i^{\alpha_i}}{\phi\left(p_i^{\alpha_i-\nu}\right)} & \text{if } \nu=\nu'.\\ \end{cases} \end{align*} $$

We now plug this into equation (4.10), and since $p_i$ is no longer fixed, we write $\nu _i$ and $\nu ^{\prime }_i$ instead of $\nu $ and $\nu '$. If $(\xi ,N)\neq (\xi ^\prime ,N)$, then $\nu _i\neq \nu ^{\prime }_i$ for at least one $p_i$, so that

$$ \begin{align*} \sum_{v\mid N} \frac{1}{\phi(v)} G_\xi (v) G_{\xi^\prime} (v)=0. \end{align*} $$

If, on the other hand, $(\xi ,N)=(\xi ^\prime ,N)$, we get

$$ \begin{align*} \sum_{v\mid N} \frac{1}{\phi(v)} G_\xi (v) G_{\xi^\prime} (v) =\prod_{i=1}^k \frac{p_i^{\alpha_i} }{\phi\left(p_i^{\alpha_i-\nu_i}\right)} =\frac{N}{\phi(N/(\xi,N))}, \end{align*} $$

which proves the proposition.

In order to finish the proof of Theorem 4.7, we write

$$ \begin{align*} \begin{split} \mathbb{A}^N_m[C] & =\sum_{x,y,z\in\mathbb{Z}_N} w_A(x)w_C(y)\mathbf{1}_{H_m}(z)\mathbf{1}_{x-y=z} \\ & =\frac{1}{N}\sum_{x,y,z\in\mathbb{Z}_N} w_A(x)w_C(y)\mathbf{1}_{H_m}(z) \sum_{\xi \in \mathbb{Z}_N} e^{-2\pi i \xi (x-y+z)/N} \\ & = \frac{1}{N} \sum_{\xi \in \mathbb{Z}_N} \widehat{w_A}(\xi) \overline{ \widehat{w_C}(\xi) } \widehat{\mathbf{1}_{H_m}}(\xi) \\ & = \frac{1}{N} \sum_{\xi \in \mathbb{Z}_N} \widehat{w_A}(\xi) \overline{ \widehat{w_C}(\xi) } G_\xi (N/m). \end{split} \end{align*} $$

Therefore

$$ \begin{align*} \left\langle \mathbb{A}^N[C], \mathbb{B}^N[D] \right\rangle & =\frac{1}{N^2} \sum_{v\mid N} \frac{1}{\phi(v)} \left(\sum_{\xi \in \mathbb{Z}_N} \widehat{w_A}(\xi) \overline{ \widehat{w_C}(\xi) } G_\xi (v)\right)\left(\sum_{\xi^\prime \in \mathbb{Z}_N} \widehat{w_B}(\xi') \overline{ \widehat{w_D}(\xi') } G_{\xi^\prime} (v)\right) \\ & = \frac{1}{N^2} \sum_{\xi, \xi^\prime \in \mathbb{Z}_N} \widehat{w_A}(\xi) \overline{ \widehat{w_C}(\xi) } \widehat{w_B}(\xi') \overline{ \widehat{w_D}(\xi') } \left[\sum_{v\mid N} \frac{1}{\phi(v)} G_\xi (v) G_{\xi^\prime} (v)\right]. \end{align*} $$

By Proposition 4.9,

$$ \begin{align*} \left\langle \mathbb{A}^N[C], \mathbb{B}^N[D] \right\rangle & =\frac{1}{N^2} \sum_{d\mid N} \frac{N}{\phi(N/d)} \left(\sum_{\xi: \left(\xi,N\right)=d} \widehat{w_A}(\xi) \overline{ \widehat{w_C}(\xi) } \right) \left(\sum_{\xi^\prime: \left(\xi^\prime,N\right)=d} \widehat{w_B}(\xi') \overline{ \widehat{w_D}(\xi') } \right), \end{align*} $$

which is equation (4.6), since $ \widehat {w_A}(\xi ) = A\left (e^{-2\pi i \xi /N}\right )$ and $\zeta = e^{-2\pi i \xi /N}$ is a root of $\Phi _d(X)$ if and only if $(\xi ,N)=N/d$.

4.3 Proof of Theorem 4.4

1. (i) Assume that $A\oplus B=\mathbb {Z}_M$. Let $N\mid M$, and let $C=\{x\}$ and $D=\{y\}$ for $x,y\in \mathbb {Z}_N$. By equation (4.5), we have

   $$ \begin{align*} \left\langle \mathbb{A}^N[x], \mathbb{B}^N[y] \right\rangle =\sum_{d\mid N} \frac{1}{N \phi(d) } \left[ \sum_{\zeta:\Phi_d(\zeta)=0} A(\zeta)\overline{C(\zeta)} \right] \left[ \sum_{\zeta:\Phi_d(\zeta)=0} B(\zeta)\overline{D(\zeta)} \right]. \end{align*} $$
   If $d\neq 1$, then $\Phi _d(X)$ divides at least one of $A(X)$ and $B(X)$. Hence the only nonzero contribution is from $d=1$, which yields
   $$ \begin{align*} \left\langle \mathbb{A}^N[x], \mathbb{B}^N[y] \right\rangle = \frac{1}{N} A(1)C(1)B(1)D(1) = \frac{\lvert A\rvert \lvert B\rvert}{N}. \end{align*} $$
   This proves equation (4.2).

2. (ii) Suppose that $A,B\subset \mathbb {Z}_M$ satisfy $\left \langle \mathbb {A}^M[a], \mathbb {B}^M[b] \right \rangle =1$ for all $a\in A,b\in B$. Then

   $$ \begin{align*} \left\langle \mathbb{A}^M[A], \mathbb{B}^M[B] \right\rangle &= \sum_{a\in A,b\in B} \left\langle \mathbb{A}^M[a], \mathbb{B}^M[b] \right\rangle\\ &= \sum_{a\in A,b\in B} 1 = \lvert A\rvert \lvert B\rvert=M. \end{align*} $$
   By equation (4.6), this implies that
   $$ \begin{align*} \sum_{d\mid M} \frac{1}{\phi(d) } \mathcal{E}_d(A) \mathcal{E}_d(B) = M^2. \end{align*} $$
   However, we are also assuming that $\mathcal {E}_1(A) \mathcal {E}_1(B)= \lvert A\rvert ^2 \lvert B\rvert ^2 = M^2$. Hence $\mathcal {E}_d(A) \mathcal {E}_d(B)=0$ for all $d\mid M$, $d\neq 1$, so that $A\oplus B=\mathbb {Z}_M$ as claimed.

Remark 4.10. We indicate a proof of Theorem 2.5 based on equation (4.6). Suppose that $A\oplus B=\mathbb {Z}_M$ is a tiling, and apply equation (4.6) with $N=M$. Since $\Phi _d(X)\mid A(X)B(X)$ for all $d\mid M$, $d\neq 1$, we get

$$ \begin{align*} \sum_{m\mid M}\frac{1}{\phi(M/m)} \mathbb{A}^M_m[A]\mathbb{B}^M_m[B] = \frac{\lvert A(1)\rvert^2 \lvert B(1)\rvert^2}{M}=M. \end{align*} $$

But we also have $\mathbb {A}^M_M[A]\mathbb {B}^M_M[B]=\lvert A\rvert \lvert B\rvert =M$. Hence all other terms $\mathbb {A}^M_m[A]\mathbb {B}^M_m[B]$ with $m\neq M$ must vanish. This proves Theorem 2.5.

5.1 Definitions

For consistency, we will also write

$$ \begin{align*} \mathbb{A}^{\mathcal{T}} [x] = \mathbb{A}^N_N[x*T],\quad x\in\mathbb{Z}_M. \end{align*} $$

In some situations, it will be easier to write out $\Delta $ in its polynomial form. We will then identify the polynomial $\Delta (X)$ with the corresponding weighted multiset $\Delta $, and write $\mathbb {A}^{\mathcal {T}} [\Delta (X)]$ instead of $\mathbb {A}^{\mathcal {T}} [\Delta ]$.

Definition 5.2. Set $A\in \mathcal {M}(\mathbb {Z}_M)$, and let $\mathcal {T} = (N,\vec \delta ,T)$ be a cuboid type as before. We will say that A is $\mathcal {T}$-null if for every cuboid $\Delta $ of type $\mathcal {T}$,

(5.3)$$ \begin{align} \mathbb{A}^{\mathcal{T}} [\Delta] =0. \end{align} $$

Figure 2 An N-cuboid with N having three prime factors.

5.2 Classic cuboids

Definition 5.4. An N-cuboid is a cuboid of type $\mathcal {T}=(N,\vec {\delta },T)$, where $N\mid M$, $T(X)=1$ and $\delta _j=1$ for all j such that $p_j\mid N$. Thus, N-cuboids have the form

$$ \begin{align*} \Delta(X)= X^c\prod_{p_j\mid N} \left(1-X^{\rho_jN/p_j}\right) \end{align*} $$

with $ (\rho _j,p_j)=1$ for all j, and the associated $\Delta $-evaluation of a multiset $A\in \mathcal {M}(\mathbb {Z}_N)$ is

$$ \begin{align*} \mathbb{A}^N_N[\Delta] = \sum_{ \vec\epsilon\in\{0,1\}^{\lvert\mathfrak{J}\rvert}} w_\Delta\left(x_{\vec\epsilon}\right) \mathbb{A}^N_N\left[x_{\vec\epsilon}\right], \end{align*} $$

where $\mathfrak {J}= \{j: p_j\mid N \}$ and the cuboid vertices $x_{\vec \epsilon }$ are defined in equation (5.2). If $\mathcal {T}$ is as before and $A\in \mathcal {M}(\mathbb {Z}_N)$ is $\mathcal {T}$-null, we will also say for short that A is N-null.

The geometric interpretation of N-cuboids $\Delta $ is as follows. With notation as in Definition 5.4, recall that $D(N)=N/\prod _{j\in \mathfrak {J}}p_j$. Then the vertices $x_{\vec \epsilon }$ of $\Delta $ form a full-dimensional rectangular box in the grid $\Lambda (c,D(N))$, with one vertex at c and alternating $\pm 1$ weights. We reserve the term ‘N-cuboid’, without cuboid type explicitly indicated, to refer to cuboids as in Definition 5.4; for cuboids of any other type, we will always specify $\mathcal {T}$.

The following cyclotomic divisibility test has been known and used previously in the literature (see, for example, [Reference Steinberger42, Section 3] in the context of vanishing sums of roots of unity, or [Reference Kiss, Malikiosis, Somlai and Vizer16, Section 3] and [Reference Kiss, Malikiosis, Somlai and Vizer17] with applications to the ‘spectral implies tiling’ direction of Fuglede’s conjecture.

Proof. Let $m\mid N$ satisfy $m\neq N$. Then $m\mid (N/p_i)$ for some i such that $p_i\mid N$, so that $\Phi _m\mid (1-X^{N/p_i})$. The implication (i) $\Rightarrow $ (ii) now follows from Lemma 5.3.

An alternative proof that (i) implies (ii) (without using Theorem 4.7; compare [Reference Kiss, Malikiosis, Somlai and Vizer16, Reference Steinberger42]) is as follows. By classic results on vanishing sums of roots of unity [Reference de Bruijn3, Reference Lam and Leung28, Reference Mann32, Reference Rédei35, Reference Rédei36, Reference Schoenberg38], $\Phi _N(X)\mid A(X)$ if and only if $A(X)$ is a linear combination of the polynomials $\Phi _p(X^{N/p})$, where p runs over all prime divisors of N, with integer (but not necessarily nonnegative) coefficients. Equivalently, $\Phi _N(X)\mid A(X)$ if and only if A can be represented as a linear combination of N-fibers. It is very easy to see that equation (5.4) holds for all N-cuboids $\Delta $ if $A \bmod N$ is an N-fiber; therefore it also holds if $A \bmod N$ is a linear combination of such fibers.

The proof that (ii) implies (i) is by induction on the number of prime divisors of N (this argument was also known previously in the literature; see, for example, [Reference Steinberger42, Proposition 2.4]). We present it here for completeness.

If $N=p^\alpha $ is a prime power, the claim follows from equation (2.6). Suppose that the claim is true for all $N'$ with at most k prime divisors. Suppose that N has $k+1$ prime divisors, and that $A\in \mathcal {M}(\mathbb {Z}_N)$ obeys equation (5.4) for all N-cuboids $\Delta $ in $\mathbb {Z}_N$. Let p be a prime divisor of N, and let $N'=N/p^\alpha $, where $(N',p)=1$.

Assume first that

(5.5)$$ \begin{align} A\in\mathcal{M}\left( p^{\alpha-1}\mathbb{Z}_N\right). \end{align} $$

Write $A(X)=\sum _{j=0}^{p-1} X^{jN/p } A_j(X)$, where $A_j\in \mathcal {M}(p^{\alpha }\mathbb {Z}_N)$. Each ‘layer’ $A_j$ can be identified in the obvious manner with a multiset in $\mathbb {Z}_{N'}$.

For $j=0,1,\dotsc ,p-1$, let $A_{j,0}$ be the weighted multiset defined via ${A}_{j,0}(X)= {A}_j(X)-{A}_0(X)$. The condition (5.4) implies that, with the obvious notation,

$$ \begin{align*} \left(\mathbb{A}_{j,0}\right)^{N'} [\Delta'] =0 \end{align*} $$

for every full-dimensional cuboid $\Delta '$ in $\mathbb {Z}_{N'}$. By the inductive assumption, $\Phi _{N'}(X)\mid A_{j,0}(X)$. By the structure theorem for vanishing sums of roots of unity, ${A}_{j,0}$ is a linear combination of $N'$-fibers in $\mathbb {Z}_{N'}$. Returning to $\mathbb {Z}_N$ now, and summing in j, we get that $A(X) = A'(X)+A''(X)$, where the following are true:

• • $A'(X)=\sum _{j=0}^{p-1} X^{jN/p } A_{j,0}(X)$. By the foregoing argument, ${A}'$ is a linear combination of fibers in directions perpendicular to p.

• • ${A}''=\sum _{j=0}^{p-1} X^{jN/p} A_0(X)$. This is a linear combination of fibers in the p direction.

Thus ${A}$ is a linear combination of fibers, and therefore $\Phi _N(X)\mid A(X)$.

Finally, in the general case without assumption (5.5), we can write A as a union of multisets $A^{(i)}$, $i=0,1,\dotsc , p^{\alpha -1} -1$, where each $A^{(i)}$ is a translate of a multiset satisfying assumption (5.5). If equation (5.4) holds for A, then it also holds for each $A^{(i)}$. By the previous argument, we get that $\Phi _N(X)\mid A^{(i)}(X)$ for each i, and therefore it divides $A(X)$. This completes the proof that (ii) implies (i).

5.3 Multiscale cuboids

In many situations, we need to work with cuboids on several scales simultaneously. This happens, for example, when we investigate the divisibility of a polynomial $A(X)$ by combinations of cyclotomic polynomials, or when we try to reduce a tiling of $\mathbb {Z}_M$ to tilings of cosets of a subgroup. We will use cuboids with nontrivial templates to facilitate such multiscale cuboid analysis.

Definition 5.7 Folding templates

Let $M=\prod _{i=1}^K p_i^{n_i}$ and $N=\prod _{i=1}^K p_i^{n_i-\alpha _i}$, with $0\leq \alpha _i\leq n_i$ for $i=1,\dotsc ,K$. The folding template $T^M_N$ is given by

$$ \begin{align*} T^M_N(X) = \prod_{i:p_i\mid\frac{M}{N}} \prod_{\nu_i=1}^{\alpha_i} \Psi_{M/p_i^{\nu_i}}(X) \equiv \frac{X^M-1}{X^N-1} \bmod \left(X^M-1\right), \end{align*} $$

where

(5.6)$$ \begin{align} \Psi_{M/p_i^\delta}(X)= \Phi_{p_i}\left(X^{M/p_i^\delta}\right) = 1+X^{M/p_i^{\delta}}+ X^{2M/p_i^{\delta}} + \dotsb + X^{(p_i-1) M/p_i^{\delta}}. \end{align} $$

When M is fixed, we will sometimes write $T_N$ instead of $T^M_N$, for simplicity.

Strictly speaking, $\Psi _{M/p_i^\delta }$ depends on both M and $p_i^\delta $, not just on their quotient; however, both numbers will always be clear from the context. We also note that $\Psi _{M/p_i}=F_i$.

Definition 5.7 allow us to consider N-cuboids as cuboids with templates in $\mathbb {Z}_M$. Specifically, let $N\mid M$ be as in Definition 5.7. Then for any $A\in \mathcal {M}(\mathbb {Z}_M)$ and $x\in \mathbb {Z}_M$,

(5.7)$$ \begin{align} \mathbb{A}^N_N[x]= \mathbb{A}^M_M\left[x*T^M_N\right]. \end{align} $$

Consequently, we have the following:

Lemma 5.8. With M and N as in Definition 5.7, let $\mathcal {T}= (M,\vec {\delta },T^M_N)$, where

(5.8)$$ \begin{align} \delta_i= \begin{cases} \alpha_i+1 & \text{if }\alpha_i<n_i, \\ 0 &\text{if } \alpha_i=n_i, \end{cases} \quad i\in\{1,\dotsc,K\}. \end{align} $$

We will sometimes write $\vec {\delta }=\vec {\delta }^M_N$ to indicate the dependence on M and N. Let $A\in \mathcal {M}(\mathbb {Z}_M)$ be a multiset. Then the following are equivalent:

• • $\Phi _N\mid A$;

• • A is $\mathcal {T}$-null in $\mathbb {Z}_M$;

• • the multiset induced by A in $\mathbb {Z}_N$ is N-null (see Definition 5.4).

Let

(5.9)$$ \begin{align} \Delta=X^c\prod_{i:p_i\mid N} \left(1-X^{d_i}\right), \quad c\in\mathbb{Z}_M,\quad (M,d_i)=M/p_i^{\alpha_i+1}, \end{align} $$

be a cuboid of type $\mathcal {T}$ as in Lemma 5.8. Then the cuboid $\Delta \bmod N$, induced by $\Delta $ in $\mathbb {Z}_N$, is an N-cuboid. Conversely, any N-cuboid $\Delta '$ in $\mathbb {Z}_N$ can be written (not necessarily uniquely) as $\Delta \pmod N$, where $\Delta $ is a cuboid of the form (5.9) in $\mathbb {Z}_M$. Therefore, whenever working on scales N and M simultaneously, we will represent N-cuboids as cuboids of the form (5.9) in $\mathbb {Z}_M$. In this notation, a multiset $A\in \mathcal {M}(\mathbb {Z}_M)$ satisfies any one (therefore all) of the conditions in Lemma 5.8 if and only if

$$ \begin{align*} \mathbb{A}^N_N[\Delta]= \mathbb{A}^{\mathcal{T}}[\Delta]= \mathbb{A}^M_M\left[\Delta*T^M_N\right]=0 \end{align*} $$

for all $\Delta $ as in equation (5.9). Transitions between several intermediate scales $N_1,N_2,\dotsc \mid M$ will be handled similarly, with $\mathbb {Z}_M$ as the default ambient space.

Figure 3 A classic M-cuboid (green) vs. a multiscale cuboid (red) corresponding to the product $\Phi _M\Phi _{M/p_i}$.

Cuboids with more general templates can be used to indicate divisibility by combinations of several cyclotomic polynomials. We will be particularly interested in implications of the form ‘if $\Phi _{s_1},\dotsc ,\Phi _{s_l}$ divide $A(X)$, then A is $\mathcal {T}$-null for a given cuboid type $\mathcal {T}$’. It will not be necessary to aim for ‘if and only if’ conditions such as those in Lemma 5.8.

6.1 Subgroup reduction

In this section, we discuss two ways in which the question of proving (T2) for a tiling $A\oplus B=\mathbb {Z}_M$ (and, more generally, investigating the structure of such tilings) may be reduced to the analogous question for tilings $A'\oplus B'=\mathbb {Z}_{N}$, where $N\mid M$ and $N\neq M$. We start with a recap, in a slightly more general setting, of the reduction that Coven and Meyerowitz used in [Reference Coven and Meyerowitz2] to prove Theorem 1.1.

Proof. We have $A(X)=A'(X^{p_i})$ for some $A'\subset \mathbb {Z}_{N_i}$. Write also

$$ \begin{align*} B(X)\equiv \sum_{\nu=0}^{p_i-1} X^{\nu M/p_i^{n_i-1}} B_\nu( X^{p_i})\mbox{ mod }X^M-1, \end{align*} $$

where $B_\nu \subset \mathbb {Z}_{N_i}$ for $\nu =0,1,\dotsc ,p_i-1$. If $b\in B$ and $b\equiv r \bmod p_i$, then $a+b\equiv r \bmod p_i$ for all $a\in A$; in other words, the tiling breaks down into separate tilings of residue classes mod $p_i$, with $A'\oplus B_\nu =\mathbb {Z}_{N_i}$ for each $\nu $.

By assumption (ii), $A'$ and $B_\nu $ satisfy (T2) for all $\nu $. We need to check that this is still true for A and B. We first claim that for any polynomial $F(X)$ and any $s\in \mathbb {N}$,

(6.1)$$ \begin{align} \Phi_{\tau(s)}(X)\mid F\left(X^{p_i}\right) \Leftrightarrow \Phi_s(X)\mid F(X), \end{align} $$

where

$$ \begin{align*} \tau(s)=\begin{cases} s &\text{if }p_i\nmid s,\\ p_is &\text{if }p_i\mid s. \end{cases} \end{align*} $$

Indeed, we have $\Phi _{\tau (s)}(X)\mid F(X^{p_i})$ if and only if $F(e^{2\pi i p_i/\tau (s)})=0$. This means that $F(e^{2\pi i /s})=0$ if $p_i\mid s$, and $F(e^{2\pi i p_i/s})=0$ if $p_i\nmid s$. In both cases, this is equivalent to $\Phi _s\mid F$.

Observe first that, by equation (2.6), we must have

$$ \begin{align*} \Phi_{p_i}\mid B. \end{align*} $$

Suppose that $s_1,\dotsc ,s_k$ are powers of distinct primes such that $\Phi _{s_1}\dotsm \Phi _{s_k}\mid A$. As already noted, we cannot have $s_j=p_i$ for any j. Let $s^{\prime }_j=s_j/p_i$ if $s_j$ is a power of $p_i$, and $s^{\prime }_j=s_j$ otherwise. Then $s^{\prime }_j$ are prime powers, and $s_j=\tau (s^{\prime }_j)$. By equivalence (6.1), $\Phi _{s^{\prime }_1}\dotsm \Phi _{s^{\prime }_k}\mid A'$, and since (T2) holds for $A'$, we have $\Phi _{s^{\prime }_1\dotsm s^{\prime }_k}\mid A'$. Since $\tau (s^{\prime }_1\dotsm s^{\prime }_k)=s_1\dotsm s_k$, we get that $\Phi _{s_1\dotsm s_k}\mid A$.

Suppose now that $s_1,\dotsc ,s_k$ are powers of distinct primes such that $\Phi _{s_1}\dotsm \Phi _{s_k}\mid B$ and $s_1,\dotsc ,s_k\neq p_i$, and define $s^{\prime }_1,\dotsc ,s^{\prime }_k$ as before. Then for $j=1,\dotsc ,k$ we have $\Phi _{s_j}\nmid A$, and therefore $\Phi _{s^{\prime }_j}\nmid A'$ and, since $A'\oplus B_\nu =\mathbb {Z}_{N_i}$ is a tiling, $\Phi _{s^{\prime }_j}\mid B_\nu $ for each $\nu $. Since $B_\nu $ satisfies (T2), we have $\Phi _{s^{\prime }_1\dotsm s^{\prime }_k}\mid B_\nu $. It follows that $\Phi _{s_1\dotsm s_k}\mid B_\nu (X^{p_i})$ for each $\nu $, and therefore $\Phi _{s_1\dotsm s_k}\mid B$.

Finally, suppose that $s_1,\dotsc ,s_k$ are powers of distinct primes such that $\Phi _{s_1}\dotsm \Phi _{s_k}\mid B$ and $s_1,\dotsc ,s_k$ are not powers of $p_i$, and consider $\Phi _{p_is}$ with $s=s_1\dotsm s_k$. We have

$$ \begin{align*} B \left(e^{2\pi i/p_is}\right)= \sum_{\nu=0}^{p_i-1} e^{2\pi i \nu M/sp_i^{n_i}} B_\nu\left( e^{2\pi is}\right)=0, \end{align*} $$

by (T2), for each $B_\nu $.

6.2 Slab reduction

Our second tiling reduction also involves passing from a tiling $A\oplus B=\mathbb {Z}_M$ to a tiling of a smaller cyclic group. However, instead of restricting to residue classes and thus constructing a family of tilings of a subgroup $p_i\mathbb {Z}_M$, we will use periodicity. Recall that M-fibers $F_i$ and M-fibered sets were defined in Section 2.3 (see formula (2.4)). Let $M=\prod _{i=1}^K p_i^{n_i}$, and define

(6.2)$$ \begin{align} A_{p_i}=\left\{a\in A: 0\leq\pi_i(a)\leq p_i^{n_i-1}-1\right\}, \end{align} $$

where $\pi _i$ is the array coordinate defined in Section 2.2. Suppose that we have $S\oplus B=\mathbb {Z}_M$, where S is the $M/p_i$-periodic extension of $A_{p_i}$ to $\mathbb {Z}_M$:

(6.3)$$ \begin{align} S(X)=A_{p_i}(X)F_i(X). \end{align} $$

Then we may reduce the period of the tiling and write $A_{p_i}\oplus B=\mathbb {Z}_{M/p_i}$, where $A_{p_i}$ and B are now considered mod $M/p_i$.

As a motivating example, suppose that $A\oplus B=\mathbb {Z}_M$, with M as before, and that A is M-fibered in the $p_i$ direction. Let $A'$ be a set obtained from A by choosing one point from each fiber, so that $\lvert A'\rvert =\lvert A\rvert /p_i$ and $A=A'*F_i$. Then A is the periodic extension of $A'$, and we have $A'\oplus B=\mathbb {Z}_{M/p_i}$.

Our main results in this section are Theorem 6.5 and Corollary 6.7, where we develop a criterion for $A_{p_i}$ to admit periodic tilings as described, and prove that passing to such tilings preserves the (T2) property.

Lemma 6.3. Set $ A\in \mathcal {M}(\mathbb {Z}_{M}) $, with M as before. Assume that $\Phi _d\mid A$ for some d such that $p_i^{n_i}\mid d\mid M$. Then for every $1\leq \alpha _i\leq n_i $,

$$ \begin{align*} \Phi_{d/p_i^{\alpha_i}}\mid A \Rightarrow \Phi_{d/p_i^{\alpha_i}}\mid A_{p_i}. \end{align*} $$

Proof. Let $d = M/\prod _{j\neq i} p_j^{\alpha _j}$ and $d'=d/p_i^{\alpha _i}$. Assume that $\Phi _d\Phi _{d'}\mid A$. We would like to show that $\Phi _{d'}\mid A_{p_i}$. To this end, we define cuboid types $\mathcal {T}=(M,\vec \delta ,T_d)$ and $\mathcal {T}'=(M,\vec \delta ',T_{d'})$, where $T_d=T^M_d$, $T_{d'}=T^M_{d'}$ are the folding templates from Definition 5.7 and $\vec {\delta }=\vec {\delta }^M_d$, $\vec {\delta }'=\vec {\delta }^M_{d'}$ are defined as in equation (5.8), with $N=d$ and $N=d'$, respectively.

Let S be the periodic extension of $A_{p_i}$ to $\mathbb {Z}_M$ defined in equation (6.3). We have $\Phi _d\mid F_i$ but $\Phi _{d'}\nmid F_i$, so that $\Phi _{d'}\mid S$ if and only if $\Phi _{d'}\mid A_{p_i}$. We need to prove that

$$ \begin{align*} \mathbb{S}^{d'}_{d'}[\Delta]=0 \end{align*} $$

for all cuboids $\Delta $ of type $\mathcal {T}'$. Fix such a cuboid

$$ \begin{align*} \Delta(X)=X^y\cdot\prod_j \left(1-X^{d_j}\right), \quad y\in\mathbb{Z}_M, \left(d_j,M\right)=M/p_{j}^{\delta^{\prime}_j}. \end{align*} $$

Let

$$ \begin{align*} \Delta_i(X)=X^y\cdot\prod_{j\neq i} \left(1-X^{d_j}\right) \end{align*} $$

so that

$$ \begin{align*} \Delta(X)=\begin{cases} \left(1-X^{d_i}\right)\Delta_i(X)&\text{if }\alpha_i<n_i,\\ \Delta_i(X)&\text{if }\alpha_i=n_i. \end{cases} \end{align*} $$

Observe that if $\rho _i\in \mathbb {Z}_M$ satisfies $(\rho _i,M)=M/p_i$, then $(1-X^{\rho _i})\Delta _i(X)$ is a cuboid of type $\mathcal {T}$. Since A is $\mathcal {T}$-null, we have $\mathbb {A}^d_d [\left (1-X^{\rho _i}\right )\Delta _i(X)]=0$, so that

$$ \begin{align*} \mathbb{A}^d_d[\Delta_i]=\mathbb{A}^d_d[\rho_i*\Delta_i]. \end{align*} $$

Averaging the last equality over all $\rho _i\in \{M/p_i,2M/p_i,\dotsc ,(p_i-1)M/p_i\}$, we get

$$ \begin{align*} \mathbb{A}^d_d[\Delta_i]=\frac{1}{\phi(p_i)}\mathbb{A}^d_d[\Delta_i*(F_i-1)]. \end{align*} $$

Clearly we may take linear combinations of the latter – that is, for any set $V\subset \mathbb {Z}_M$,

(6.4)$$ \begin{align} \mathbb{A}^d_d[\Delta_i*V]=\frac{1}{\phi(p_i)}\mathbb{A}^d_d[\Delta_i*(F_i-1)*V]. \end{align} $$

Let $\Psi \subset \mathbb {Z}_M$ be a set such that $\Psi (X)\equiv \prod _{\nu =2}^{\alpha _i}\Psi _{M/p_i^\nu }(X) \bmod X^{M/p_i}-1$, and

(6.5)$$ \begin{align} 0\leq\pi_i(y+z) \leq p_i^{n_i-1}-1\quad \forall z\in \Psi. \end{align} $$

Then

$$ \begin{align*} T_{d'}(X)&= T_d(X)F_i(X)\Psi(X)\\[3pt] &= T_d(X)\Psi(X) +(F_i-1)T_d(X)\Psi(X) , \end{align*} $$

so that

$$ \begin{align*} \mathbb{A}^{d'}_{d'}[\Delta_i]&= \mathbb{A}^M_M\left[\Delta_i*T_{d'}\right]\\[3pt] &=\mathbb{A}^M_M[\Delta_i*T_d*\Psi ] +\mathbb{A}^M_M[\Delta_i*(F_i-1)*T_d*\Psi]\\[3pt] &=\mathbb{A}^d_d[\Delta_i*\Psi]+\mathbb{A}^d_d[\Delta_i*(F_i-1)*\Psi]. \end{align*} $$

By equation (6.4) with $V=\Psi $, we get

(6.6)$$ \begin{align} \mathbb{A}^{d'}_{d'}[\Delta_i]=\frac{p_i}{\phi(p_i)}\mathbb{A}^d_d[\Delta_i*\Psi]. \end{align} $$

The proof of equation (6.6) used only the fact that $\Phi _d\mid A$. Since S has the same property, it follows that

$$ \begin{align*} \mathbb{S}^{d'}_{d'}[\Delta_i]=\frac{p_i}{\phi(p_i)}\mathbb{S}^d_d[\Delta_i*\Psi], \end{align*} $$

By inequality (6.5), we also have

$$ \begin{align*} \mathbb{A}^d_d[\Delta_i*\Psi]=\mathbb{S}^d_d[\Delta_i*\Psi]. \end{align*} $$

Assume first that $\alpha _i<n_i$, and note that all of the foregoing arguments apply with $\Delta _i$ replaced by $d_i*\Delta _i$, yielding the same conclusions with $\Psi $ replaced by $\Psi '$, such that inequality (6.5) holds with y replaced by $y+d_i$. Recall that A is $\mathcal {T}'$-null, so that

$$ \begin{align*} 0&=\mathbb{A}^{d'}_{d'}[\Delta]\\[3pt] &= \mathbb{A}^{d'}_{d'}[\Delta_i]-\mathbb{A}^{d'}_{d'}[{d_i}*\Delta_i]\\[3pt] &= \frac{p_i}{\phi(p_i)}\left(\mathbb{A}^d_d[\Delta_i*\Psi]-\mathbb{A}^d_d[{d_i}*\Delta_i*\Psi']\right)\\[3pt] &=\frac{p_i}{\phi(p_i)}\left(\mathbb{S}^d_d[\Delta_i*\Psi]-\mathbb{S}^d_d[{d_i}*\Delta_i*\Psi']\right). \end{align*} $$

Taking the convolution with $\Psi _{M/p_i}$, and using the fact that $\Psi (X)\Psi _{M/p_i}(X)\equiv \Psi '(X)\Psi _{M/p_i}(X) \bmod (X^M-1)$, we conclude that

$$ \begin{align*} 0 &= \mathbb{S}^d_d\left[\Delta*\Psi* \Psi_{M/p_i}\right]\\[3pt] &= \mathbb{S}^{d'}_{d'}[\Delta]. \end{align*} $$

It follows that S is $\mathcal {T}'$-null, as required.

If $\alpha _i=n_i$, the proof is the same except that then $\Delta =\Delta _i$, and so the terms with $d_i*\Delta _i$ do not appear in the calculation.

Proof. Let $d = M/\prod _{j\neq i} p_j^{\alpha _j}$ and $d'=d/p_i^{\alpha _i}$. Define the cuboid types $\mathcal {T}=(M,\vec \delta ,T_d)$ and $\mathcal {T}'=(M,\vec \delta ',T_{d'})$ as in the proof of Lemma 6.3.

In order to prove that $\Phi _{d'}\mid A$, it suffices to show $ \mathbb {A}^{d'}_{d'}[\Delta ]=0$ for all cuboids of the form

(6.7)$$ \begin{align} \Delta'(X)=X^y\cdot\prod_j \left(1-X^{d_j}\right), \quad y\in\mathbb{Z}_M, \left(d_j,M\right)=M/p_{j}^{\delta^{\prime}_j}. \end{align} $$

We write $ A(X)=\sum _{\nu =0}^{p_i-1} A_{\nu }(X) $, where

(6.8)$$ \begin{align} A_{\nu}=\left\{a\in A\mid 0\leq\pi_i(a)-\nu p_i^{n_i-1}\leq p_i^{n_i-1}-1\right\},\quad\nu=0,1,\dotsc, p_i-1. \end{align} $$

Then

$$ \begin{align*} \mathbb{A}^{d'}_{d'}[\Delta']=\sum_{\nu=0}^{p_i-1}(\mathbb{A}_\nu)^{d'}_{d'}[\Delta'] =0 \end{align*} $$

using the assumption that $A_\nu $ are $\mathcal {T}'$-null for all $\nu $.

We now prove that $ \Phi _d\mid A $. It suffices to show $\mathbb {A}^d_d[\Delta ]=0$ for any cuboid of the form

(6.9)$$ \begin{align} \Delta(X)=\left(1-X^{M/p_i}\right)\Delta_i(X), \end{align} $$

where $y\in \mathbb {Z}_N$, and

$$ \begin{align*} \Delta_i(X)=X^y\cdot\prod_{j\neq i} \left(1-X^{d_j}\right), \quad y\in\mathbb{Z}_M, \left(d_j,M\right)=M/p_{j}^{\delta_j}. \end{align*} $$

Indeed, any cuboid of type $\mathcal {T}$ can be written as a linear combination of cuboids as in equation (6.9).

Let $\Psi (X)= \prod _{\nu =2}^{\alpha _i}\Psi _{M/p_i^\nu }(X)$, and

$$ \begin{align*} \Delta''(X)=\begin{cases} \left(1-X^{M/p_i^{\alpha_i+1}}\right)\Delta_i(X)&\text{if }\alpha_i<n_i,\\ \Delta_i(X)&\text{if }\alpha_i=n_i. \end{cases} \end{align*} $$

Define also

$$ \begin{align*} A^{\prime}_i&=\left\{a\in A: 0\leq\pi_i(a-y)\leq p_i^{n_i-1}-1\right\},\\[4pt] A^{\prime\prime}_i&=\left\{a\in A: 1\leq\pi_i(a-y)\leq p_i^{n_i-1}\right\}. \end{align*} $$

By our assumption on A, $ \Phi _{d'} $ divides both $A^{\prime }_i$ and $A^{\prime \prime }_i$. Suppose first that $\alpha _i<n_i$. Then

$$ \begin{align*} 0&= \left(\mathbb{A}^{\prime}_i\right)^{d'}_{d'}[\Delta''] = \mathbb{A}^{d}_{d}[\Delta_i*\Psi] - \mathbb{A}^{d}_{d}\left[\left(M/p_i^{\alpha_i+1}\right)*\Delta_i*\Psi\right], \\[4pt] 0&= \left(\mathbb{A}^{\prime\prime}_i\right)^{d'}_{d'}[\Delta''] = \mathbb{A}^{d}_{d}[\Delta_i*\Psi'] - \mathbb{A}^{d}_{d}\left[\left(M/p_i^{\alpha_i+1}\right)*\Delta_i*\Psi\right], \end{align*} $$

where $\Psi '(X)=\Psi -1+X^{M/p_i}$. Taking the difference, we get

$$ \begin{align*} 0&=\left(\mathbb{A}^{\prime}_i\right)^{d'}_{d'}[\Delta''] - \left(\mathbb{A}^{\prime\prime}_i\right)^{d'}_{d'}[\Delta''] \\[4pt] &= \mathbb{A}^{d}_{d}[\Delta_i*\Psi] - \mathbb{A}^{d}_{d}[\Delta_i*\Psi'] \\[4pt] & = \mathbb{A}^{d}_{d}[\Delta], \end{align*} $$

which proves the claim.

If $\alpha _i=n_i$, the proof is the same, except that the terms with $(M/p_i^{\alpha _i+1})*\Delta _i$ are replaced by $0$ in the calculation.

Proof. Let $N_i=M/p_i$. The assumption that $\Phi _{p_i^{n_i}}\mid A$ implies that for any translate $A'$ of A, we have $\left \lvert A^{\prime }_{p_i}\right \rvert =\lvert A\rvert /p_i$, so that

(6.13)$$ \begin{align} \left\lvert A^{\prime}_{p_i}\right\rvert\lvert B\rvert=N_i. \end{align} $$

(i) $\Rightarrow $ (ii): Assume that (i) holds, and suppose that condition (6.11) fails for some $p_i^{n_i}\mid d\mid M$. Then there is an $\alpha _i$ such that $ 1\leq \alpha _i\leq n_i$ and $\Phi _{d/p_i^{\alpha _i}}\nmid B$. Then $\Phi _{d/p_i^{\alpha _i}}\mid A^{\prime }_{p_i}$ for any translate $ A' $ of $ A $. By Lemma 6.4, condition (6.10) must hold.

(ii) $\Rightarrow $ (i): Assume that (ii) holds. With equation (6.13) in place, it suffices to prove that for every $ d'\mid N_i$, $d'>1 $, $ \Phi _{d'}$ divides at least one of $A^{\prime }_{p_i}(X)$ and $B(X)$. Let $d'\mid N_i$, $d'>1$, and suppose that $\Phi _{d'}\nmid B$. Then $d'=d/p_i^{\alpha _i}$ for some $ p_i^{n_i}\mid d\mid M$ and $ 1\leq \alpha _i\leq n_i$. By (ii), we must have $\Phi _d\mid A$. Since $A\oplus B=\mathbb {Z}_M$ is a tiling, we must also have $\Phi _{d'}\mid A$. By Lemma 6.3, we must have $\Phi _{d'}\mid A^{\prime }_{p_i}$ as claimed.

(i) $\Rightarrow $ (iii): Assume that (i) holds. This implies in particular that $A^{\prime }_{p_i}$ and $B \bmod \mathbb {Z}_{N_i}$ are sets, so that $N_i\not \in \mathrm {Div}(B)$ and condition (6.12) holds for $m=M$.

Next, Theorem 2.5 applied to the tiling $A^{\prime }_{p_i}\oplus B=\mathbb {Z}_{N_i}$ implies that

(6.14)$$ \begin{align} \mathrm{Div}_{N_i}(A) \cap \mathrm{Div}_{N_i}(B)= \{N_i\}. \end{align} $$

Suppose that condition (6.12) fails for some $m\neq M$ such that $p_i^{n_i}\mid m\mid M$, so that $m\in \mathrm {Div}(A)$ and $m/p_i\in \mathrm {Div}(B)$. Then $m/p_i \neq N_i$ and $m/p_i\in \mathrm {Div}_{N_i}(A) \cap \mathrm {Div}_{N_i}(B)$. But this contradicts equation (6.14).

(iii) $\Rightarrow $ (i): Assume that (iii) holds. By Theorem 2.5, it suffices to prove that $A^{\prime }_{p_i}, B \bmod \mathbb {Z}_{N_i}$ are sets such that equation (6.14) holds.

We first verify that $A^{\prime }_{p_i}, B \bmod \mathbb {Z}_{N_i}$ are sets. Indeed, if $a,a'\in A^{\prime }_{p_i}$ and $a\equiv a' \bmod N_i$, then $a=a'$ by the definition of $A^{\prime }_{p_i}$. On the other hand, $M\in \mathrm {Div}(A)$ trivially, and by formula (6.12) it follows that $N_i\not \in \mathrm {Div}(B)$, so that $B \bmod N_i$ is also a set.

Suppose now that equation (6.14) fails, with $m_1\in (\mathrm {Div}_{N_i}(A) \cap \mathrm {Div}_{N_i}(B))\setminus \{N_i\}$. Since $\mathrm {Div}(A)\cap \mathrm {Div}(B)=\{M\}$, we must have $m_1=m_2/p_i$ for some $m_2$ with $p_i^{n_i}\mid m_2\mid M$, so that

$$ \begin{align*} m_{j}\in\mathrm{Div}(A^{\prime}_{p_i}),\quad m_{k}\in\mathrm{Div}(B) \end{align*} $$

for some permutation $(j,k)$ of $(1,2)$. By the definition of $A^{\prime }_{p_i}$, we cannot have $p_i^{n_i-1}\parallel s$ for $s\in \mathrm {Div}(A^{\prime }_{p_i})$, so that $j=2$, $k=1$. But this contradicts condition (6.12).

Proof. We are assuming that $A^{\prime }_{p_i}\oplus B=\mathbb {Z}_{M/p_i}$ for any translate $ A'$ of $ A $. By the inductive part of the assumption, $A^{\prime }_{p_i}$ and B satisfy (T2). It remains to prove (T2) for $ A $. Suppose that $d=\prod _{j\in J} p_j^{\alpha _j}$, where $J\subset \{1,\dotsc ,K\}$, $1\leq \alpha _j\leq n_j$ for all $j\in J$, and $\Phi _{p_j^{\alpha _j}}(X)\mid A(X)$ for all $j\in J$. For each prime power $p_j^{\alpha _j}$ with $\alpha _j\neq 0$, the polynomial $\Phi _{p_j^{\alpha _j}}(X)$ can divide only one of A and B in the tiling $A\oplus B=\mathbb {Z}_M$, hence

(6.15)$$ \begin{align} \Phi_{p_j^{\alpha_j}}\nmid B \quad \forall j\in J. \end{align} $$

Write $ A(X)=\sum _{\nu =0}^{p_i-1} A_{\nu }(X) $, where $A_\nu $ are as in formula (6.8), so that $A_\nu \oplus B=\mathbb {Z}_{N_i}$ for each $\nu $. We consider two cases:

• • Assume that either $i\not \in J$, or $i\in J$ but $\alpha _i\neq n_i$. By formula (6.15), we have $\Phi _{p_j^{\alpha _j}}\mid A_\nu $ for all $j\in J$ and $\nu =0,1,\dotsc ,p_i-1$. We are assuming that (T2) holds for $A_\nu $, so that $\Phi _d\mid A_\nu $. Summing over $\nu $, we get that $\Phi _d\mid A$.

• • Assume now that $i\in J$ and $\alpha _i=n_i$, and let $d'=d/p_i^{n_i}$. Then $\Phi _{d'}\mid A^{\prime }_{p_i}$ for any translate $A'$ of A, by the argument in the first case applied to $A'$ instead of A. By Lemma 6.4, it follows that $\Phi _d\mid A$.

We note the following special case:

7.1 Preliminaries

Definition 7.1 Restricted N-boxes

Set $A,X\subseteq \mathbb {Z}_M$, and $x\in \mathbb {Z}_M$. The restriction of $\mathbb {A}^N[x]$ to X is the N-box $\mathbb {A}^N[x\mid X]$ with entries

$$ \begin{align*} \mathbb{A}^N_m[x\mid X] = \sum_{a\in X: (x-a,N)=m} w^N_A(a), \quad m\mid N. \end{align*} $$

In particular,

$$ \begin{align*} \mathbb{A}^M_m[x\mid X] = \# \{a\in A\cap X: (x-a,M)=m\}. \end{align*} $$

The next definition is the key to our analysis of unfibered tilings in [Reference Łaba and Londner24]. While it could be extended in an obvious way to N-boxes with $N\mid M$, our current arguments only use the M-box version here.

Definition 7.2 Saturating sets

Set $A,B\subseteq \mathbb {Z}_M$, and $x,y\in \mathbb {Z}_M$. Define

$$ \begin{gather*} A_{x,y}:=\{a\in A: (x-a,M)=(y-b,M) \text{ for some }b\in B\}, \\ A_{x}:=\bigcup_{b\in B} A_{x,b}. \end{gather*} $$

Equivalently,

(7.1)$$ \begin{align} A_x=\{a\in A: (x-a,M)\in\mathrm{Div}(B)\}. \end{align} $$

We will refer to $A_x$ as the saturating set for x. The sets $B_{y,x}$ and $B_y$ are defined similarly, with A and B interchanged.

With this notation, $A_{x,y}$ is the minimal set that saturates (the A-side of) the product $\left \langle \mathbb {A}^M[x], \mathbb {B}^M[y]\right \rangle $, in the sense that

(7.2)$$ \begin{align} \left\langle \mathbb{A}^M[x\mid X], \mathbb{B}^M[y]\right\rangle = \left\langle \mathbb{A}^M[x], \mathbb{B}^M[y]\right\rangle \end{align} $$

holds for $X=A_{x,y}$, and if $X\subset \mathbb {Z}_M$ is any other set for it holds, then $A_{x,y}\subset X$. The set $A_x$ is the minimal set such that

(7.3)$$ \begin{align} \left\langle \mathbb{A}^M[x\mid A_x], \mathbb{B}^M[b]\right\rangle =\left\langle \mathbb{A}^M[x], \mathbb{B}^M[b]\right\rangle \quad \forall b\in B. \end{align} $$

While Definition 7.2 makes sense for general sets $A,B\subseteq \mathbb {Z}_M$, our intended application is to the tiling situation $A\oplus B= \mathbb {Z}_M$. In that case, by Theorem 4.4, the box products on the right side of equations (7.2) and (7.3) evaluate to $1$. Hence $A_{x,y}$ is the smallest set such that

(7.4)$$ \begin{align} \left\langle \mathbb{A}^M\left[x\mid A_{x,y}\right], \mathbb{B}^M[y]\right\rangle = 1, \end{align} $$

and $A_x$ is the smallest set such that

(7.5)$$ \begin{align} \left\langle \mathbb{A}^M[x\mid A_x], \mathbb{B}^M[b]\right\rangle =1 \quad \forall b\in B. \end{align} $$

Observe in particular that a saturating set for any $x\in \mathbb {Z}_M$ must be nonempty, and that by Theorem 2.5,

(7.6)$$ \begin{align} A_a=\{a\} \quad \forall a\in A. \end{align} $$

In the next few definitions and lemmas, we will work toward geometric descriptions of saturating sets. Assume that $A\oplus B= \mathbb {Z}_M$. Set $x\in \mathbb {Z}_M\setminus A$, and suppose that $a\in A_x$. By equation (7.1) and divisor exclusion, we must have $(x-a,M)\not \in \mathrm {Div}(A)$, and in particular $(x-a,M)\neq (a'-a,M)$ for all $a'\in A$. This motivates the following definition: