Tiling problems and spectral sets

• E tiles Rⁿ by translations if there is a discrete subset T of Rⁿ (the translation set) such that, up to sets of measure 0, the sets E+t, t in T, are disjoint and their union is Rⁿ;
  
  
• E is a spectral set if there is a discrete subset S of Rⁿ (the spectrum) such that the functions exp(2 pi i k x), k in S, form an orthogonal basis for L²(E).

• The unit interval E=[0,1] tiles R with the translation set Z. Since the Fourier series of a function in L²([0,1]) is convergent in L², Z is also a spectrum for E.
  
  
• Let E be the unit square in R². Of course E is a product of two unit intervals, therefore tiles with the translation set Z² and has the spectrum Z². However, it also admits other tilings ("sliding columns"), as shown below. It turns out that the translation sets in those tilings are also spectra for E.
  
  
  Examples of planar tilings: the boring plaid; sliding columns; and the honeycomb.
  
  
• Up to affine transformations, there are only two different convex sets which tile the plane, namely the square and the hexagon. Note that the translation set in the "honeycomb tiling" shown above is a lattice, i.e., an affine image of Z². By Fuglede's theorem (see below), the hexagon is a spectral set and has a lattice spectrum.
  
  
• However, there are also sets which tile Rⁿ, but do not admit lattice tilings. For instance, let E be the union of two intervals [0,1/2] and [1,3/2]. Then E tiles R with the translation set T={0,1/2} + 2Z, and is a spectral set with the spectrum T. Yet E does not have either a lattice tiling or a lattice spectrum. In dimensions 3 and higher, one can construct similar examples in which E is connected.

• Minkowski (1907) conjectured that in any lattice tiling of Rⁿ by translates of the unit cube there must be two translates which share a whole (n-1)-dimensional facet. (By a lattice we always mean an affine image of Zⁿ, but not necessarily Zⁿ itself. In particular, a "sliding column" tiling can be a lattice tiling.) Keller (1930) conjectured that the same should be true for all cube tilings, lattice or not. Minkowski's conjecture was proved by Hajos in 1942. Keller's conjecture was proved by Perron in 1940 in dimensions 6 and less. However, in 1992 Lagarias and Shor constructed counterexamples to Keller's conjecture in dimensions 10 and higher. They write in their Bull. AMS paper that this "illustrates the general phenomenon that Euclidean space allows more freedom of movement in high dimensions..." The lowest value of n for which Keller's conjecture fails is still not known.
  
  
• Now that we realize that cube tilings are complicated business, the following result might be of interest: T is a spectrum for a unit cube if and only if the cube tiles Rⁿ with T as the translation set. There are several different proofs of this, given (almost simultaneously) by Iosevich-Pedersen, Lagarias-Reeds-Wang, and Kolountzakis. (The two- and three-dimensional cases were settled earlier by Jorgensen-Pedersen.) The open problem is of course to understand the relationship between spectra and translation sets for E other than the cube.

• A convex polygon which tiles the plane must be either a parallelogram or a hexagon; in both cases it admits a lattice tiling and therefore has a lattice spectrum.
  
  
• In higher dimensions there are of course more possibilities. However, Venkov (1954) and P. McMullen (1980) proved that if E is convex and tiles Rⁿ, then (freedom of movement notwithstanding) it is a symmetric polytope and has a lattice tiling. Again, it follows from Fuglede's theorem that E is a spectral set.
  
  
• Assume now that E is a convex subset of Rⁿ and that it is spectral; does it follow that it tiles Rⁿ? Iosevich-Katz-Pedersen (1999) proved that a ball in Rⁿ (which obviously does not tile) is not a spectral set. Kolountzakis (1999) proved that any convex spectral set E must be symmetric. Iosevich-Katz-Tao (1999, 2001) then proved that any convex spectral set in dimension 2 must indeed tile R², and that a convex set in Rⁿ with smooth boundary (which clearly does not tile the space) cannot be spectral.
  
  This is proved mostly by Fourier-analytic methods. Let f be the Fourier transform of the characteristic function of E, and suppose that E has a spectrum S. By the orthogonality condition in the definition of a spectrum, f(s-s')=0 for all s,s' in S. Hence the set Z of the zeros of f contains the difference set S-S; since (by completeness) Z and S have comparable densities, it follows that Z has nontrivial combinatorial structure. But on the other hand, a lot of information about the distribution of the zeros of f can be obtained by Fourier-analytic arguments, in particular by the stationary phase method. If E does not tile, this information is not compatible with the combinatorial structure just mentioned.

• If E is a bounded and measurable set in dimension 1 which tiles the line, then the translation set is always periodic (i.e., it is a union of a finite number of lattices). This was proved by Lagarias-Wang (1995; published in 1997) with some additional regularity assumptions, and by Kolountzakis-Lagarias (1996) as stated. The same problem for unbounded sets is still open.
  
  
• It is easy to construct aperiodic tilings in Rⁿ for n greater than 1. For example, if E is a square, it suffices to take a "sliding columns" tiling with appropriately chosen translations. However, a square also has the obvious lattice tiling. Therefore one can ask the following question: if E tiles Rⁿ by translations, does it necessarily admit a periodic tiling? This is a major open problem known as the periodic tiling conjecture.
  
  
• We have already seen that the conjecture is true for convex sets in any dimension - if a convex set tiles the space, it also has a lattice tiling.
  
  
• The conjecture has also been proved for topological discs in the plane, by Girault-Beauquier and Nivat (1989) with additional regularity assumptions and by Kenyon (1992) in general.
  
  
• Kolountzakis and I have recently proved that if E tiles the plane and if it is "close enough" to a square, in the sense that it contains a unit square and is contained in a square of sidelength 1 + epsilon for epsilon > 0 small enough, then it also has a lattice tiling. We do not assume anything about the regularity or topology of E, except that it is measurable. In particular, E might have infinitely many connected components.
  
  
  
  Our proof works for epsilon < 1/33; we don't know what is the optimal upper bound for epsilon. Also, we don't know whether a similar result holds in higher dimensions.
  
  
• In the last three cases (convex sets, topological discs, and near-squares), E has a lattice tiling. By Fuglede's theorem, it follows that E is a spectral set.

• It is a classic result (Hajos 1950, deBruijn 1950, Swenson 1974, Newman 1977) that all tilings of Z by finite sets are periodic. This links our tiling problem to several interesting problems in factorization of finite groups (replacement of factors, quasiperiodicity, etc); more on that soon. Meanwhile, a related question which is still unsolved is the following: given a finite set A which tiles Z, what is the minimal period of all tilings by A? From Newman's proof, the period of any tiling by A is bounded by 2^{max(A)-min(A)}. On the other hand, I don't know of any tilings of period greater than 2(max(A)-min(A)). (This number comes from the simple example A={0,n}.)
  
  
• A very nice algebraic characterization of all finite sets A which tile Z was conjectured by Coven and Meyerowitz (J. Algebra 1999; also available online, click here to download it). Coven and Meyerowitz proved that their conditions are always sufficient, and that they are also necessary if #A has at most 2 prime factors. The general case is still open; however, Andrew Granville, Yang Wang and I have recently made some progress and should be able to report on it really soon.
  
  It turns out that the Coven-Meyerowitz conditions are exactly what is needed to prove the tiling -> spectrum implication! Need I add that the authors had not even heard of Fuglede's conjecture until some time after they published the paper?
  
  
• What about higher dimensions? It is easy to construct aperiodic tilings of Zⁿ by finite sets if n is at least 2. But do all such sets also admit a periodic tiling? This actually seems to be a difficult and interesting problem (another way of saying that the 1-dimensional methods do not work). Proving or disproving this would be an important contribution towards understanding the periodic tiling conjecture.
  
  

• If E tiles the half-line R⁺ by translations, it is a spectral set (Pedersen-Wang 1998).
• The conjecture is true (in both directions) if E is a union of two intervals in R (Laba 2000)
• The conjecture is also true (in both directions) if E is a measurable subset of R such that |E|=1 and E is contained in an interval of length strictly less than 3/2 (Koluntzakis-Laba 2001).
• A polytope with "unbalanced side areas" (see below) cannot tile the space, just because the side areas do not match. Kolountzakis-Papadimitrakis (2001) proved that such polytopes cannot be spectral.
  
  
  A polygon with unbalanced side lengths: one of the vertical edges is much longer than the other.

• Alex Iosevich
• Palle Jorgensen
• Nets Katz
• Richard Kenyon
• Mihalis Kolountzakis
• Jeff Lagarias
• Steen Pedersen
• Terence Tao
• Peter Shor
• Yang Wang