A characterization of flnite sets that tile the integers

Andrew Granville, Yan WangarXiv 2001 · arXiv

Abstract

We say that a finite set of integers $A$ tiles $\mathbb{Z}$ by translations if $\mathbb{Z}$ can be written as a disjoint union of translates of $A$. Coven and Meyerowitz (J. Algebra 212 (1999), 161–174) found necessary and sufficient conditions for $A$ to tile $\mathbb{Z}$ if $|A|$ has at most two distinct prime factors. The purpose of this paper is to extend their result to certain three-prime cases.

Introduction

In the field of additive combinatorics, the problem of characterizing which finite sets of integers can perfectly tile the set of integers $\mathbb{Z}$ has remained a central challenge. A set $A \subset \mathbb{Z}$ tiles the integers if there exists a set $C$ such that every integer $n \in \mathbb{Z}$ has a unique representation as $n = a + c$, where $a \in A$ and $c \in C$. This is equivalent to saying that the translates of $A$ by elements of $C$ form a partition of $\mathbb{Z}$.

In 1999, Coven and Meyerowitz established a landmark framework for this problem by proposing two conditions, (T1) and (T2), based on the roots of the characteristic polynomial of $A$. While they proved that these conditions are sufficient for any tiling, and that (T1) is always necessary, the necessity of (T2) remained unproven for sets whose size $|A|$ involves more than two distinct prime factors. This paper extends the necessity of (T2) to specific cases involving three prime factors ($|A| = p^\alpha q^\beta r^\gamma$), bridging a significant gap in the classification of tiling sets.

The Coven-Meyerowitz Conditions

To understand the contribution of Granville, Laba, and Wang, one must first consider the algebraic representation of a finite set $A$. We define the characteristic polynomial:

$$A(x) = \sum_{a \in A} x^a$$

The tiling property is deeply linked to the divisibility of $A(x)$ by cyclotomic polynomials $\Phi_s(x)$, which are the minimal polynomials of the primitive $s$-th roots of unity. Let $S_A$ be the set of prime powers $s$ such that $\Phi_s(x)$ divides $A(x)$. The Coven-Meyerowitz conditions are defined as:

  1. (T1): $A(1) = \prod_{s \in S_A} \Phi_s(1)$.
  2. (T2): If $s_1, s_2, \dots, s_k \in S_A$ are powers of distinct primes, then their product $s_1 s_2 \dots s_k$ also satisfies $\Phi_{s_1 s_2 \dots s_k}(x) | A(x)$.

Coven and Meyerowitz proved that (T2) is necessary if $|A|$ has at most two prime factors. However, the structural tools used for the two-prime case—specifically Sands' Theorem—fail when a third prime is introduced, as the geometric complexity of the tiling increases significantly.

Methodology: A New Algebraic Identity

The authors shift the problem from pure combinatorics into algebraic number theory. The core innovation of the paper is Theorem 1.2, a novel identity that relates the spatial distribution of the set to its spectral properties.

Specifically, the identity relates:

  • Spatial Distribution: The number of pairs in sets $A$ and $B$ whose difference has a specific greatest common divisor with a period $N$.
  • Frequency Domain: The values of the characteristic polynomials $A(x)$ and $B(x)$ evaluated at various roots of unity.

This identity allows the authors to "count" how a tiling is distributed across multiple modular scales simultaneously. By using this tool, they can bypass the inductive limitations of previous methods, providing a way to analyze how elements are spread out modulo $p, q,$ and $r$.

Key Results: The Three-Prime Case

The primary result of the paper is Theorem 1.1. The authors consider a set $A$ that tiles the integers where $|A| = p^\alpha q^\beta r^\gamma$. They demonstrate that if the "complementary" tiling set $B$ has a specific size ($|B| = pqr$) and $A$ is "balanced" with respect to the individual primes (meaning $\Phi_p, \Phi_q, \Phi_r$ divide $A(x)$), then $A$ must also be balanced with respect to their products.

This implies that $\Phi_{pq}, \Phi_{pr}, \Phi_{qr},$ and $\Phi_{pqr}$ must also divide $A(x)$, confirming that the (T2) condition is indeed necessary for this configuration. This result suggests that the (T2) condition is not merely a byproduct of small prime counts but is likely a fundamental requirement for integer tilings in general.

Implications and Fuglede’s Conjecture

This research has broader implications for Fuglede’s Spectral Set Conjecture. The conjecture suggests that a set $A$ tiles a space by translation if and only if it is "spectral" (i.e., it possesses an orthogonal basis of exponentials). In one dimension, proving the necessity of (T2) for all finite sets would essentially resolve one direction of Fuglede’s conjecture. By cracking the three-prime case, the authors provide a roadmap for a universal proof.

Conclusion

While the proof for the three-prime case in this paper requires certain constraints on the size of the tiling partner set $B$, it represents the first major progress on the (T2) necessity problem in decades. The introduction of the Theorem 1.2 identity provides a powerful new tool for additive combinatorics, moving the mathematical community closer to a complete characterization of finite tiling sets.

Summary updated

Abstract

We say that a flnite set of integers A tiles Z by translations if Z can be written as a disjoint union of translates of A. Coven and Meyerowitz (J. Algebra 212 (1999), 161{174) found necessary and su‐cient conditions for A to tile Z if jAj has at most two distinct prime factors. The purpose of this paper is to extend their result to certain three-prime cases. Mathematics Subject Classiflcation: 11B75.
BibTeX
@misc{granville2001characterization,
  author = {Andrew Granville and Yan Wang},
  title = {{A characterization of flnite sets that tile the integers}},
  year = {2001},
  eprint = {math/0109127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/math/0109127},
}

Loading related content...

Figure