Warning: This page is seriously outdated. I hope to fix this soon.

Tiling problems and spectral sets

The basics
Cube tilings
Convex sets
Periodic tiling conjecture
Finite sets which tile integers
Other special cases

The purpose of this page is to discuss some of the many problems concerning tilings of Rn by translates of a single set called a tile. All of them have one thing in common: they are easy to state. Furthermore, many of them do not seem to require much background - in plain English, you don't have to spend a couple of years studying the literature before you can even think about working on them. But be warned that they can be very difficult!

At least for the time being, we consider only tilings by translates of one tile. This means that it is not permitted to rotate the tile, use its symmetric reflections, or use more than one tile. However, there has been a lot of research on tilings where some or all of the above are allowed, and there are many interesting and challenging problems concerning such tilings. (For instance, planar tilings have been used to construct interesting examples of operator algebras.) I might post some relevant materials and links later on.

This page was first posted in June 2001 and will be updated regularly. If you have any comments or suggestions, please write to ilaba@math.ubc.ca.

The basics

Let E be a measurable subset of Rn; we assume that E has positive and finite measure. We say that:
• E tiles Rn by translations if there is a discrete subset T of Rn (the translation set) such that, up to sets of measure 0, the sets E+t, t in T, are disjoint and their union is Rn;

• E is a spectral set if there is a discrete subset S of Rn (the spectrum) such that the functions exp(2 pi i k x), k in S, form an orthogonal basis for L2(E).
For example:
• The unit interval E=[0,1] tiles R with the translation set Z. Since the Fourier series of a function in L2([0,1]) is convergent in L2, Z is also a spectrum for E.

• Let E be the unit square in R2. Of course E is a product of two unit intervals, therefore tiles with the translation set Z2 and has the spectrum Z2. 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 Z2. By Fuglede's theorem (see below), the hexagon is a spectral set and has a lattice spectrum.

• However, there are also sets which tile Rn, 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.
By now you might have started noticing a pattern: all tiles considered so far are spectral sets, and moreover there is a duality between their spectra and translation sets.

Fuglede conjectured in 1974 that a set E in Rn is spectral if and only if it tiles Rn by translations. He proved that the conjecture is true if either the spectrum or the translation set is a lattice. He also proved that a triangle and a disc in the plane are not spectral. The general case is still open, in all dimensions and in both directions. There are, however, many partial results supporting the conjecture; some of them are discussed below.

Cube tilings

So you thought that a cube was boring? Think again.
• Minkowski (1907) conjectured that in any lattice tiling of Rn 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 Zn, but not necessarily Zn 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 Rn 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.

Convex sets

• 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 Rn, 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 Rn and that it is spectral; does it follow that it tiles Rn? Iosevich-Katz-Pedersen (1999) proved that a ball in Rn (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 R2, and that a convex set in Rn 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.

Periodic tiling conjecture

We have seen that there are sets which tile Rn but do not admit lattice tilings, for instance the union of two intervals (0,1) and (2,3). So how complicated can it really get?
• 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 Rn 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 Rn 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.

Finite sets which tile integers

OK, if we really want to consider non-lattice tilings, we have to get our hands dirty and do some algebra and number theory.

Lagarias-Wang (1997) proved a structure theorem for 1-dimensional tilings and reduced the proof of the tiling -> spectrum implication in dimension 1 to the proof of a similar implication for sets of the form E = A + [0,1], where A is a finite subset of Z. Naturally, such an E tiles R by translations if and only if A tiles Z by translations.
• 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 2max(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 Zn 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.

Special cases

In addition to those cases already discussed, Fuglede's conjecture has been proved (in at least one direction) in the following special cases.
• 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.