The Coven-Meyerowitz conjecture

The Accidental Mathematician 2023-01-08

The Coven-Meyerowitz conjecture is a tentative characterization of finite sets that tile the integers by translations. It’s also something I have been thinking about, on and off, for more than 2 decades; in the last few years, Itay Londner and I were finally able to make some progress on it. This post will provide a short introduction to the problem, some history, and a little bit of speculation. In a follow-up post (or posts, as there might be more than one), I will say more about our recent work.

The basics. Let $A$ be a set of integers; in this series of posts, we will always assume that $A$ is finite. We will say that $A$ tiles $\mathbb{Z}$ by translations if $\mathbb{Z}$ can be covered by non-overlapping translated copies of $\latex A$. We will use $T$ to denote the set of translations. For example:

The set $A=\{0,1,2\}$ tiles $\mathbb{Z}$ by translations. Indeed, we can just place copies of $A$ next to each other, back to back. A possible translation set is $3\mathbb{Z}=\{... -6, -3, 0, 3, 6, ...\}$ . Note that the translation set need not be unique: for example, $3\mathbb{Z}+1=\{... -5, -2, 1, 4, 7, ...\}$ would also work in this case.
The set $A=\{0,1, 4,5\}$ also tiles $\mathbb{Z}$ by translations. For example, we can add its translate $A+2=\{2,3,6,7\}$ to fill up the discrete interval $\{0,1,2,3,4,5,6,7\}$ , then continue the pattern.
The set $A=\{0,2, 3\}$ does not tile $\mathbb{Z}$ by translations. Once $A$ is in place, there is no way to add a second translate $A+t$ , non-overlapping with $A$ , so that $A+t$ would cover the point 1. (Try it!)

In the above examples, it’s easy to tell whether each set does or does not tile the integers. However, suppose that $A$ is a set of 30 integers between 0 and 100,000. What then? How can we tell whether $A$ tiles the integers or not?

A periodicity argument due to Newman says that the question is decidable, meaning that there is a guaranteed way to get a “yes” or “no” answer in finite time. Specifically, Newman proved the following theorem.

Theorem (Newman). Let $A\subset\mathbb{Z}$ be finite. If $A$ tiles the integers, then every such tiling is periodic with period bounded by $2^{\max(A)-\min(A)}$ .

Here’s the idea of the proof: if $A$ tiles the integers, then it must also tile a discrete interval of length $\max(A)-\min(A)$ . Once it does that, there is only one way to continue the tiling in each direction, and because there are only finitely many configurations of that length available, at some point they have to start repeating themselves, making the tiling periodic. Do this carefully, and you get Newman’s theorem.

Let’s say, then, that $A=\{0,173, 952\}$ . How can we tell whether $A$ tiles the integers? As per the above, we expect the tiling to have period at most $2^{952}$ . We could have a computer check all arrangements of translates of $A$ by shifts between $0$ and $2^{952}$ , and if we do not find a tiling of period bounded by that number, then none exists.

Fortunately, in this case we could also do something more clever than using brute force. Notice that $\{0,173, 952\}$ is a full set of residues modulo $3$ , with $173\equiv 2\mod 3$ and $952\equiv 1\mod 3$ . Therefore $A$ actually tiles the integers with tiling period 3 and the translation set $3\mathbb{Z}$ .

How did I know to check the residues mod $3$ ? Is there a way to do such “smart tricks” more systematically? Also, does this mean that $\{0,173, 951\}$ does not tile the integers?

Let’s see.

The polynomial formulation. Let $A$ tile the integers with period $M$ . This means that the translation set $T$ has period $M$ . so that $T=B\oplus M\mathbb{Z}$ for some finite $B\subset\{0,1,\dots,M-1\}$ . Reducing mod $M$ , we may also assume that $A\subset \{0,1,\dots,M-1\}$ , and write $A\oplus B=\mathbb{Z}_M$ .

(A word on notation: we write $A\oplus B=C$ to say that for every $c\in C$ there is a unique pair $(a,b)\in A\times B$ such that $a+b=c$ . We use $\mathbb{Z}_M$ to denote $\mathbb{Z}$ modulo $M$ . From now on, we will always consider $A,B$ as subsets of $\mathbb{Z}_M$ , with addition mod $M$ .)

We now introduce the polynomial notation. We will use $X$ to denote a variable, and define the mask polynomials

$A(X)=\sum_{a\in A} X^a$ , $\ B(X)=\sum_{b\in B} X^b$ .

(Note that $A(1)=|A|$ , the cardinality of $A$ .) Then the tiling condition $A\oplus B=\mathbb{Z}_M$ is equivalent to

(1) $A(X)B(X)\equiv 1+X+X^2+\dots +X^{M-1} \mod X^{M}-1$ .

This reformulation of the problem is easy (just multiply out the product and compare the exponents), but very useful, because now we can use factorization of polynomials.

Cyclotomic polynomials. The $s$ -th cyclotomic polynomial $\Phi_s$ is the unique irreducible monic polynomial whose roots are the $s$ -th primitive roots of unity. An alternative definition that will be useful to us is based on factorization: for all $M\in\mathbb{N}$ , we have

(2) $X^{M}-1 = \prod_{s|M} \Phi_s(X)$ ,

and this can be used to define all $\Phi_s$ inductively. (Here and below, we always consider only the positive divisors, so that $s\in\mathbb{N}$ .) Start with

$X-1=\Phi_1(X)$ ,

because clearly $X-1$ is irreducible and the only divisor of 1 is 1. Next,

$X^2-1=(X-1)(X+1).$

Since we have already established that $\Phi_1(X)=X-1$ , it follows that $\Phi_2(X)=X+1$ . Similarly,

$X^3-1=(X-1)(X^2+X+1),$

so that $\Phi_3(X)=X^2+X+1$ . This is part of a more general pattern: if $p$ is a prime number, then by the same argument we have $\Phi_p(X)=1+X+X^2+\dots+X^{p-1}$ . Furthermore, if $p$ is prime and $\alpha\in\mathbb{N}$ , we can write

$X^{p^\alpha}-1=(X^{p^{\alpha-1}}-1)(1+X^{p^{\alpha-1}}+\dots+ X^{(p-1)p^{\alpha -1}})$

so that by induction,

(3) $\Phi_{p^\alpha}(X)=1+X^{p^{\alpha-1}}+X^{2p^{\alpha -1}}+\dots+ X^{(p-1)p^{\alpha -1}}=\Phi_p(X^{p^{\alpha-1}}).$

For a composite example, let’s compute $\Phi_6$ :

$X^6-1=(X^3-1)(X^3+1)= \Phi_1(X)\Phi_3(X)(X+1)(X^2-X+1),$

where we used that $X^3-1= \Phi_1(X)\Phi_3(X)$ as above. Also, we already know that $X+1=\Phi_2(X)$ , so that leaves $X^2-X+1$ as $\Phi_6$ .

The Coven-Meyerowitz tiling conditions. Coming back to the tiling equation (1), we see that each $\Phi_s(X)$ with $s|M$ and $s\neq 1$ must divide $A(X)B(X)$ . Since $\Phi_s$ are irreducible (a basic fact from algebra), we get the following.

(4) For all $s|M$ with $s\neq 1$ , the cyclotomic polynomial $\Phi_s$ must divide at least one of $A(X)$ and $B(X)$ (possibly both).

The question of interest is how these cyclotomic divisors are split between $A(X)$ and $B(X)$ . Let $S_A$ be the set of prime powers $p^\alpha$ such that the corresponding cyclotomic polynomial $\Phi_{p^\alpha}(X)$ divides $A(X)$ . In 1998, Coven and Meyerowitz proposed the following tiling conditions.

(T1) $A(1)=\prod_{s\in S_A}\Phi_s(1).$

(T2) If $s_1,\dots,s_m\in S_A$ are powers of distinct primes¹, then $\Phi_{s_1\dots s_m}(X)|A(X).$

Theorem (Coven-Meyerowitz). Let $A\subset\{0,1,2,\dots\}$ be finite.

(i) If $A(X)$ satisfies (T1) and (T2), then $A$ tiles the integers by translations.

(ii) If $A$ tiles the integers by translations, then (T1) holds.

(iii) If $A$ tiles the integers by translations and $|A|$ has at most two distinct prime factors, then (T2) holds.

We do not know whether (T2) must hold for all finite sets that tile the integers. The statement that this must be true has become known as the Coven-Meyerowitz conjecture, even though Coven and Meyerowitz did not actually conjecture this in their paper². This is considered to be the main conjecture in the theory of integer tilings in 1 dimension. The problem turned out to be very difficult and there was very little progress on it until my recent work with Itay Londner – but more on that in future posts.

The (T1) and (T2) conditions may look technical and unintuitive at first – I remember that this was my impression the first time I saw them. So, let’s try to unpack them a bit and figure out what is going on.

It’s relatively easy to see that if $A$ tiles the integers, then (T1) holds. Indeed, suppose that $A\oplus B=\mathbb{Z}_M$ for some $M$ and $B\subset\{0,1,\dots,M-1\}$ . Let $S$ be the set of all prime powers dividing $M$ . By (4), we have $S= S_A\cup S_B$ . Also, by (3) we have $\Phi_{p^\alpha}(1)=p$ . Therefore

$M=\prod_{p^\alpha\in S}p \mid \prod_{p^\alpha\in S_A}p \prod_{p^\alpha\in S_B}p$

$\ \ = \prod_{s\in S_A}\Phi_{s}(1)\prod_{s\in S_B}\Phi_{s}(1) \mid A(1)B(1)=M.$

It follows that we must have equality at each step, and in particular (T1) holds for both $A$ and $B$ . (Additionally, this proves that $S_A$ and $S_B$ are disjoint.) I think of it as a “counting condition”, in the following sense: if $A$ is to tile the integers, its mask polynomial cannot afford to have irreducible divisors $Q(X)$ with $Q(1)\neq 1$ other than prime power cyclotomics, each with multiplicity 1. Otherwise, the tiling condition (1) fails because the cardinalities of $A$ and $B$ cannot match the tiling period.

This is enough to prove that the 3-element set $A=\{0,173, 951\}$ (a modification of the earlier example) does not tile the integers. We have $|A|=3$ . If $A$ did tile the integers, there would be exactly one $\alpha$ such that $\Phi_{3^\alpha}|A$ . Divisibility by prime power cyclotomics has a combinatorial interpretation in terms of equidistribution: if $\Phi_3|A$ , then the elements of $A$ are equidistributed mod 3; if $\Phi_9|A$ , then the elements of $A$ within each residue class mod 3 are equidistributed between the 3 available residue classes mod 9; and so on. In the given example, $173\equiv 2\mod 3$ and $951\equiv 0\mod 3$ , so $A$ is not equidistributed mod 3. It cannot satisfy the higher order equidistribution condition, either, because each residue class mod 3 contains fewer than 3 elements of $A$ . Therefore, no tiling for this $A$ .

Going back to $A=\{0,173, 952\}$ , can we use the Coven-Meyerowitz theorem to decide whether $A$ tiles the integers? Yes. First, observe that $|A|=3$ is a prime number, so that the (T2) condition is vacuous. It therefore suffices to check (T1). (This, and the extension to prime powers, was already known to Newman.) We need to look at divisibility of $A(X)$ by $\Phi_s(X)$ , where $s$ runs over powers of 3. Since $\{0,173, 952\}$ is a full set of residues modulo $3$ as pointed out earlier, we see that $A$ tiles the integers with period 3, this time with less wild guessing and a little bit more of a systematic method.

What about (T2), then? This is a deeper structural property that can be understood in several ways. One interpretation is in terms of equidistribution (possibly within residue classes). Suppose, for example, that $\Phi_2(X)\Phi_3(X)|A(X)$ . Since 2 and 3 are powers of distinct primes, in order for $A$ to satisfy (T2) we must also have $\Phi_6(X)|A(X)$ . This means that

$\Phi_2(X)\Phi_3(X)\Phi_6(X)= 1+X+X^2+\dots+X^5|A(X)$ ,

so that $A$ must be equidistributed mod 6. For example, the set $\{0,3,4,5,7,8\}$ (a complete set of residues mod 6) satisfies (T2) and tiles the integers. On the other hand, if we let $A=\{0,1,2,3,7,8\}$ , then this set is equidistributed mod 2 and mod 3 (hence $\Phi_2(X) \Phi_3(X)|A(X)$ ), but is not equidistributed mod 6. Therefore (T2) fails, and by the Coven-Meyerowitz theorem for 2 prime factors, $A$ does not tile the integers. Of course, for this particular set, we could also see it by inspection (there is no way to cover the numbers 4,5,6 by a translate $A+t$ not overlapping with $A$ ). However, it’s easy to make up examples that look more complicated, but are actually equivalent once you know what to look for. For instance, $\{0,31,62,75, 355, 608\}$ might be less obvious, but has the same set of residues mod 6 as $\{0,1,2,3,7,8\}$ , and does not tile the integers for the same reason.

Another way to understand (T2) that turned out to be rather important in our work is in terms of “standard” tiling complements. Suppose that $A$ satisfies (T1) and (T2). To prove that $A$ must then tile the integers, Coven and Meyerowitz constructed a tiling with period $M=lcm(S_A)$ and an explicit tiling complement $B$ that depends only on the prime power cyclotomic divisors of $A(X)$ . (This happens in the proof of Theorem A in their paper.) Londner and I prove in Section 4.1 of our first paper that having this standard tiling complement is in fact equivalent to (T2). Therefore, to prove that (T2) holds for all finite tiles, it suffices to prove the following: whenever $A$ tiles the integers, it also admits a tiling $A\oplus B^\flat =\mathbb{Z}_M$ , where $M=lcm(S_A)$ and $B^\flat$ is the standard tiling complement for $A$ constructed according to the Coven-Meyerowitz algorithm.

For the sets we considered so far, the standard tiling complements are very simple. If $A$ is a 3-element set with $\Phi_3(X)|A(X)$ , we have $lcm(S_A)=3$ and $B^\flat = \{0\}$ . Similarly, if $A$ is a 6-element set with $\Phi_2(X)\Phi_3(X)\Phi_6(X)|A(X)$ , we have $lcm(S_A)=6$ and $B^\flat = \{0\}$ . Note that the set may have other tiling complements: for instance, if $A=\{0,4,8\}$ , then there is also a tiling of minimal period 12, namely $A\oplus B=\mathbb{Z}_{12}$ with $B=\{0,1,2,3\}$ . (But we still have the standard tiling of period 3.)

In general, we get $B^\flat$ by “filling in” the cyclotomic divisors that might be missing from $A$ . Let’s say for example that $S_A=\{4,9\}$ , and assume also that $A$ satisfies (T2). Since $lcm(S_A)=36$ , we will try to construct a tiling $A\oplus B^\flat=\mathbb{Z}_{36}$ . Note that 2 and 3 are not included in $S_A$ , so that by (4), we must have $\Phi_2(X)\Phi_3(X)|B^\flat(X)$ . If we just try

$B^\flat (X):=\Phi_2(X)\Phi_3(X)=(1+X)(1+X+X^2)$

$=1+X+2X^2+X^3+X^4$ ,

there are two problems with that. First of all, this is not a mask polynomial of a set (because the coefficient of $X^2$ is 2). Second, we need all cyclotomic polynomials $\Phi_s$ with $s|36$ and $s\neq 1$ to divide one of $A(X)$ and $B(X)$ , and our assumptions on $A$ only guarantee that $\Phi_4,\Phi_9,\Phi_{36}$ divide $A(X)$ . (It is possible that $A(X)$ also has some of the other “mixed” cyclotomic divisors, but we do not know that.) So, we will assign preemptively all of the remaining cyclotomic divisors to $B^\flat$ . We can do that by letting

$B^\flat (X):=\Phi_2(X^{9})\Phi_3(X^{4})=(1+X^{9})(1+X^{4}+X^{8})$

$=1+X^{4}+X^{8}+X^{9}+X^{13}+X^{17}$ ,

which fixes both problems. (If you’ve read everything here so far, verifying this is a good exercise.) This produces a tiling complement $B^\flat=\{0,4,8,3,13,17\}$ which is both highly structured (a sumset of the arithmetic progressions $\{0,4,8\}$ and $\{0,9\}$ ) and determined entirely by the prime power cyclotomic divisors of $A(X)$ .

More math next time, but this post would not be complete without some speculation.

Do I think that the conjecture is true? I honestly don’t know, and there are good reasons to expect either outcome. On the negative side, integer tilings can get rather complicated very quickly. There is already a huge jump in difficulty when passing from the 2-prime case to the simplest genuinely 3-prime tilings (the Coven-Meyerowitz paper has 12 pages; my papers with Londner add up to about 200). Beyond that, there be dragons nobody really knows. Wide-sweeping conjectures about tiling and group factorization do not have a good track record of being true without further restrictions, see for example Keller’s conjecture on face sharing in cube tilings, Fuglede’s spectral set conjecture, the conjectures of Hajós and Tijdeman on factorization of finite abelian groups, or, more recently, the periodic tiling conjecture. A general philosophy regarding questions of this type is mentioned in this Quanta Magazine article on the unit conjecture in algebra, which was eventually disproved: “At the time, there was little evidence either way. If anything, there was a philosophical reason to disbelieve the conjectures: As the mathematician Mikhael Gromov is said to have observed, the menagerie of groups is so diverse that any sweeping, universal statement about groups is almost always false, unless there’s some obvious reason why it should be true.” Tilings, too, can be quite diverse and there is a good chance that we do not understand yet the full complexity of the problem, so that situation here may well be similar³.

On the other hand, the Coven-Meyerowitz conjecture does not try to claim anything about tiling and abelian groups in general. It is, specifically, a statement about tilings of the integers, and that makes it a conjecture in number theory at least as much as one in algebra. In number theory, of course, heuristic considerations are quite different. “Serious” conjectures are generally expected, and often confirmed in the end, to be true unless there is some clear reason why this should not be the case.

So, ultimately, I think it will be a tug of war between these two sides of the conjecture. If the resolution turns out to depend on its algebraic aspects, it will likely be negative. If on the other hand the number-theoretic considerations prevail, then the conjecture should be expected to be true, although probably very difficult to prove. Based on my experience (for example, my work with Londner depends very strongly on the fact that we are in a number-theoretic setting), I expect that number theory is more likely to win here. I don’t consider it anywhere close to guaranteed, though, so I’d give it the odds of maybe 55-60%.

If you’d like to tell me what you think, the comments here are closed and will stay closed, but I’m on Twitter and Mastodon (see the sidebar for links), and if that format is not sufficient then I also have a Discord server for math discussions (ask me about getting an invite).

¹ Note that $s_1,\dots,s_m$ should be powers of distinct primes, and not just distinct prime powers. For example, if we assume that $\Phi_2(X)\Phi_3(X)\Phi_4(X)|A(X)$ , then (T2) says that $\Phi_6$ and $\Phi_{12}$ also divide $A(X)$ , but it does not say anything about $\Phi_8$ .

² This is common practice in mathematics. For example, the Kakeya conjecture (a subset of $\mathbb{R}^n$ that contains a unit line segment in every direction must have Hausdorff dimension $n$ ) was named after Sōichi Kakeya, who did not conjecture any such thing. The question that he did ask concerned rotating a needle in the plane, and said nothing about either higher-dimensional spaces or the Hausdorff dimension.

³ For the same reasons, I had not expected the periodic tiling conjecture to be true. I said so when I was interviewed for the Quanta article about it. I was probably not alone in it, either. Instead, Quanta chose to publish a straightforward “mathematicians believed it was true” story and to quote me only on something technical.