lattice tilings by cubes: whole, notched and extended

Mihail Kolountzakis Department of Mathematics 1409 W. Green St., University of Illinois, Urbana, IL 61801

               kolount@math.uiuc.edu

Current Address: Department of Mathematics University of Crete 714 09 Iraklio, Greece

               kolount@math.uch.gr

Submitted: April 14, 1997; Accepted: February 14, 1998.

Abstract

We discuss some problems of lattice tiling via Harmonic Analysis methods. We consider lattice tilings of R^{d} by the unit cube in relation to the Minkowski Conjecture (now a theorem of Hajós) and give a new equivalent form of Hajós’s theorem. We also consider “notched cubes” (a cube from which a reactangle has been removed from one of the corners) and show that they admit lattice tilings. This has also been been proved by S. Stein by a direct geometric method. Finally, we exhibit a new class of simple shapes that admit lattice tilings, the “extended cubes”, which are unions of two axis-aligned rectangles that share a vertex and have intersection of odd codimension.

In our approach we consider the Fourier Transform of the indicator function of the tile and try to exhibit a lattice of appropriate volume in its zero-set.

1991 Mathematics Subject Classification. Primary 52C22; Secondary 42.

§0. Introduction

0.1 Results.

We obtain some results about translational tilings of R^{d} with some simple classes of of polyhedra as tiles (cubes as well as “notched” and “extended” cubes–see §2 for a definition of the latter shapes). The approach we use is to study the zero-set of the Fourier Transform (FT) of the indicator function of the tile. If that set contains a lattice except 0 then the set tiles R^{d} when translated at the locations of the dual lattice. This means that the translated copies of the tile cover (almost) every point in R^{d} a constant number of times–see Theorem 2.

In §1 we use our harmonic analysis approach to derive a new equivalent form of the Minkowski conjecture (every lattice tiling of R^{d} with the unit cube contains two cubes which share an entire (d−1)-dimensional face) which was proved by Hajós [Haj] in 1941. This new form of the Minkowski conjecture (Theorem 6) is an elementary number-theoretic statement that involves no inequalities and could conceivably lead to a new, elementary proof of the conjecture.

In §2 we prove that certain classes of polyhedra tile R^{d} if translated by an appropriate lattice. The notched cube (see Figure 1) has already been shown by Stein [St] to tile R^{d} by a lattice (Conlan [Con] has done this in some cases). Stein’s method was a direct geometric one. We give a new proof that the notched cube is a tile using our approach. That is, we find lattices in the zero-set of the FT of the indicator function of the notched cube, which is a very explicit function (see (11)). We find all the tilings discovered by Stein, which, by a deeper theorem of Schmerl [Sch], is the complete list of possible translational tilings (lattice or not) of the notched cube.

However, our approach for the notched cube leads us to the discovery of a whole class of simple tiles of R^{d} (the “extended cubes”–see Figure 2), for which we know of no geometric proof of the fact that they tile. These tiles consist of two axis-aligned rectangles which share a vertex and have intersection of odd codimension, and the lengths of their sides can be completely arbitrary. The tiling lattices for each of these tiles are very simple to describe. Furthermore, the proof that the notched cube tiles essentially proves that the extended cubes tile as well, as the FT of the two indicator functions (that of the notched cube and of that of the extended cube) have the same form and differ only at the values of some parameters.

0.2 Translational tiling in R^{d}.

Let f ∈ L^{1}(R^{d}) and A ⊂ R^{d} be a discrete point set. We say that (the tile) f tiles R^{d} with (the tile set) A and with weight w if for almost all (Lebesgue) x ∈ R^{d} we have

∑_{a∈A} f(x − a) = w,  (1)

where the series above converges absolutely. If f is the indicator function of a (measurable) set T ⊂ R^{d} then we also say that T (the tile) tiles R^{d} with weight w, which then has to be a nonnegative integer. When w = 1 we sometimes write

R^{d} = T ⊕ A.  (2)

We restrict our attention to tile sets A of bounded density. That is, we demand that

# (A ∩ (x + [0, 1]^{d})) ≤ C,  (3)

for all x ∈ R^{d} and for some constant C, a requirement which is automatically fulfilled whenever f ≥ 0.

0.3 A spectral condition for tiling.

In [KLa] a necessary and sufficient condition was given for (1) to hold. It was proved for dimension d = 1 only. Here we state it for arbitrary d. We ommit the proof as it is identical to the one-dimensional case.

For a tempered distribution μ we denote by μ̂ its Fourier Transform (see for example [Str]).

Theorem 1 Assume that f ∈ L^{1}(R^{d}) has Fourier Transform f̂ ∈ C^{∞}(R^{d}) and that the discrete set A ⊂ R^{d} is of bounded density. Write

μ = ∑_{a∈A} δ_{a},  (4)

where δ_{a} is a point mass at a.

(i) If f tiles R^{d} with the tile set A and some weight w then

supp μ̂ ⊆ Z := {0} ∪ {ξ ∈ R^{d} : f̂(ξ) = 0}.  (5)

(ii) If μ̂ is locally a finite measure and supp μ̂ ⊆ Z, then f tiles R^{d} with the tile

set A and weight w = μ̂({0}) ∫_{R^{d}} f.

Note that the requirement that f̂ ∈ C^{∞}(R) is true for all f of compact support.

0.4 Fourier Transform and the Poisson Summation Formula.

The definition of Fourier Transform we use throughout this paper is

f̂(ξ) = ∫_{R^{d}} e^{−2πi⟨ξ,x⟩}f(x) dx,

for f ∈ L^{1}(R^{d}).

Let Λ = AZ^{d}, A a non-singular n × n real matrix, be a lattice in R^{d} and write

Λ^{∗} = {x ∈ R^{d} : ∀λ ∈ Λ ⟨x, λ⟩ ∈ Z}.

It turns out that Λ^{∗} = A^{−⊤}Z^{d} is a lattice which we call the dual lattice of Λ. The Poisson Summation Formula (PSF)

∑_{λ∈Λ} φ(x − λ) = |det A|^{−1} ∑_{λ^{∗}∈Λ^{∗}} φ̂(x − λ^{∗}),

valid for all smooth φ of compact support, can be written as a distribution identity as follows:

(∑_{λ∈Λ} δ_{λ})^{∧} = |det A|^{−1} ∑_{λ^{∗}∈Λ^{∗}} δ_{λ^{∗}}.  (6)

Our spectral criterion for tiling (Theorem 1) then takes the following simpler form for lattice tilings.

Theorem 2 Assume that f ∈ L^{1}(R^{d}). Then f tiles R^{d} with a lattice Λ and some weight w if and only if

Λ^{∗} \ {0} ⊆ {ξ ∈ R^{d} : f̂(ξ) = 0}.  (7)

In this case we have w = |det Λ|^{−1} ∫_{R^{d}} f.

Proof. (without using Theorem 1) Let D be a fundamental parallelepiped of Λ. The function

g(x) = ∑_{λ∈Λ} f(x − λ)

is defined as an absolutely convergent series for almost all x ∈ R^{d} (since f ∈ L^{1}(R^{d})), is Λ-periodic, and g ∈ L^{1}(D).

The dual group of D = R^{d}/Λ is identified with Λ^{∗}. That is the continuous characters of R^{d}/Λ are the functions

ϕ_{λ^{∗}}(x) = exp(2πi⟨λ^{∗}, x⟩), λ^{∗} ∈ Λ^{∗},

and g is constant (i.e., f tiles with Λ) if and only if

f̂(λ^{∗}) = ⟨g, ϕ_{λ^{∗}}⟩ = 0, ∀λ^{∗} ∈ Λ^{∗} \ {0}.

■

An alternative would be to prove Theorem 2 for Λ = Z^{d} using ordinary multiple Fourier series and then use a linear transformation to get the general form of the theorem.

Thus, a measurable T ⊆ R^{d} tiles with Λ (in the ordinary sense of weight 1) if and only if ˆ1_{T} vanishes on Λ^{∗} \ {0} and the volume of Λ is equal to that of T.

All tilings in §1 and §2 are tilings of weight 1.

§1. The Minkowski Conjecture

1.1 Two equivalent forms of the conjecture.

Minkowski’s theorem on linear forms is the following statement.

Theorem 3 (Minkowski) If A ∈ M_{d}(R) has det A = 1 then there is x ∈ Z^{d} \ {0} such that

∥Ax∥_{∞} ≤ 1.

Minkowski conjectured around 1900 that one can always get ∥Ax∥_{∞} < 1 except when A has an integral row. This was proved by Hajós [Haj] in 1941.

Theorem 4 (Hajós) If A ∈ M_{d}(R) has det A = 1 then there is x ∈ Z^{d} such that

∥Ax∥_{∞} < 1,

unless A has an integral row.

Hajós actually worked on the following equivalent form of the Minkowski conjecture, which involves lattice tilings by a cube. This form was already known to Minkowski and most results on Minkowski’s conjecture leading up to Hajós’s eventual proof have used this form.

Theorem 5 If Q = [−1/2, 1/2]^{d} is a cube of unit volume in R^{d}, Λ ⊂ R^{d} is a lattice, and

R^{d} = Q ⊕ Λ

is a lattice tiling of R^{d} then there are two cubes in the tiling that share a (d − 1)- dimensional face. In other words, for some i = 1, …, d, the standard basis vector e_{i} = (0, …, 0, 1, 0, …, 0)^{⊤} ∈ Λ.

Before going on to describe a new equivalent form of the Minkowski conjecture (Theorem 6) we sketch a proof of the equivalence of Theorems 4 and 5. Theorem 4 ⟹ Theorem 5. Let Λ = AZ^{d} with det A = 1, Q ⊕ Λ = R^{d}. Then, either there is a non-zero Λ-point in the interior of 2Q or A has an integral row. The first cannot happen because of the tiling assumption. Therefore a_{ij} ∈ Z for some i and for all j. Again because of tiling it follows that gcd(a_{i1}, …, a_{i,d}) = 1. Let R^{d−1} be the subspace spanned by all e_{j}, j ≠ i, and define Λ′ = Λ∩R^{d−1} and Q′ = Q∩R^{d−1}. It follows that R^{d−1} = Λ′ ⊕Q′ is a tiling of R^{d−1}. By induction then Λ′ contains some vector of the standard basis and so does Λ. ■ Theorem 5 ⟹ Theorem 4.

Theorem 5 easily implies the seemingly stronger statement that, if AZ^{d} ⊕ Q = R^{d} is a tiling then, after a permutation of the coordinate axes, the matrix A takes the form

( \begin{matrix}1 & 0 & 0 & … & 0 \\ a_{2,1} & 1 & 0 & & 0 \\ … & … & … & … & … \\ a_{d,1} & … & … & … & 1 \end{matrix} )  (8)

Using this remark, if AZ^{d}∩(−1, 1)^{d} = {0} we get, since det A = 1, that AZ^{d}⊕Q = R^{d} and, therefore, A is (after permutation of the coordinate axes) of the type (8), and thus has an integral row (which property is preserved under permutation similarity). ■

1.2 A new equivalent form.

In this section we prove that the following is equivalent to the Minkowski conjecture (Theorems 4 and 5).

Theorem 6 Let B ∈ M_{d}(R) have det B = 1 and the property that for all x ∈ Z^{d}\{0} some coordinate of the vector Bx is a non-zero integer. Then B has an integral row.

Remark. One might think that Theorem 6 can be proved equivalent directly to Theorem 4, which it resembles most. It is, indeed, clear that Theorem 4 implies Theorem 6. However, the proof that is given here is that of the equivalence of Theorems 6 and 5 using our spectral criterion for tilings (Theorem 2) and I do not know of a more direct proof that Theorem 6 implies Theorem 4.

We shall need the following simple lemma.

Lemma 1 Let A ∈ M_{d}(R) be a non-singular matrix. The lattice A^{−⊤}Z^{d} contains the basis vector e_{i} if and only if the i-th row of A is integral.

Proof. Without loss of generality assume i = 1.

If e_{1} ∈ A^{−⊤}Z^{d} then e_{1} = A^{−⊤}x for some x ∈ Z^{d}. Therefore, for all y ∈ Z^{d} we have

(Ay)_{1} = e_{1}^{⊤}Ay = x^{⊤}A^{−1}Ay = x^{⊤}y ∈ Z.

It follows that (Ay)_{1} ∈ Z for all y ∈ Z^{d} and the first row of A is integral. Conversely, if the first row of A is integral, then, for all y ∈ Z^{d}

Z ∋ (Ay)_{1} = x^{⊤}y,

where A^{−⊤}x = e_{1} (x ∈ R^{d}). It follows that x ∈ Z^{d} and e_{1} ∈ A^{−⊤}Z^{d}. ■ Proof of the equivalence of Theorems 5 and 6.

Let f(x) = 1 (x ∈ Q) be the indicator function of the unit-volume cube Q = [−1/2, 1/2]^{d}. A simple calculation shows that

f̂(ξ) = ∏_{j=1}^{d} \frac{sin πξ_{j}}{πξ_{j}} ,  (9)

so that

Z = {f̂ = 0} = {ξ ∈ R^{d} : some ξ_{j} is a non-zero integer}.  (10)

Therefore, if Λ = B^{−⊤}Z^{d} then (since Λ has volume 1)

Q ⊕ Λ = R^{d} ⟺ Λ^{∗} \ {0} ⊆ Z,

where Λ^{∗} = BZ^{d}, by Theorem 2. In words, Q tiles with Λ if and only if for every x ∈ Z^{d} \ {0} the vector Bx has some non-zero integral coordinate. Theorem 5 ⟹ Theorem 6. Suppose x ∈ Z^{d} \ {0} implies some (Bx)_{i} ∈ Z \ {0}. Then Q ⊕ Λ = R^{d} and from Theorem 5, say, e_{1} ∈ Λ, which, from Lemma 1, implies that the first row of B is integral. Theorem 6 ⟹ Theorem 5. Assume Q ⊕ Λ = R^{d}. It follows that for every x ∈ Z^{d} \ {0} the vector Bx has some non-zero integral coordinate. By Theorem 6 B must have an integral row, which, by Lemma 1, implies that some e_{i} ∈ Λ. ■

Figure 1: A notched cube in R^{3}.

§2. The notched and the extended cube

In this section we prove that some simple shapes (like those in Figures 1 and 2) admit lattice tilings. That the “extended cubes” (Fig. 2–see Theorem 8) admit lattice tilings has not been shown before.

2.1 The notched cube We now consider the unit cube

Q = [−\frac{1}{2}, \frac{1}{2}]^{d}

from whose corner (say in the positive orthant) a rectangle R has been removed with sides-lengths δ_{1}, …, δ_{d} (0 ≤ δ_{j} ≤ 1). That is, we consider the “notched cube”:

N = Q \ R

where

R = ∏_{j=1}^{d} [\frac{1}{2} − δ_{j}, \frac{1}{2}] .

It is shown in Figure 1.

We give a new proof of the following result of Stein [St].

Theorem 7 The notched cube N admits a lattice tiling of R^{d}.

After a simple calculation we obtain

ˆ1_{N}(ξ) = ∏_{j=1}^{d} \frac{sin πξ_{j}}{πξ_{j}} − F (ξ) ∏_{j=1}^{d} \frac{sin πδ_{j}ξ_{j}}{πξ_{j}} ,  (11)

where F (ξ) = exp(πiK(ξ)) with

K(ξ) = ∑_{j=1}^{d}(δ_{j} − 1)ξ_{j}.  (12)

Using Theorem 2 it is enough to exhibit a lattice Λ ⊂ R^{d}, of volume equal to

|N| = 1 − δ_{1} ⋯ δ_{d},

such that ˆ1_{N} vanishes on Λ^{∗} \ {0}.

2.2 Lattices in the zero-set We define the lattice Λ^{∗} as those points ξ for which

ξ_{1} − δ_{2}ξ_{2} = n_{1},
ξ_{2} − δ_{3}ξ_{3} = n_{2},
…  (13)
ξ_{d} − δ_{1}ξ_{1} = n_{d},

for some n_{1}, …, n_{d} ∈ Z. That is, Λ^{∗} = A^{−1}Z^{d}, where

A = ( \begin{matrix}1 & −δ_{2} \\ & 1 & −δ_{3} \\ & & & . & . & . \\ & & & & & & 1 & −δ_{d} \\ −δ_{1} & & & & & & & 1 \end{matrix} ) .  (14)

Therefore Λ = A^{⊤}Z^{d} and the volume of Λ is equal to |det A|. Expanding A along the first column we get easily that det A = 1 − δ_{1} ⋯ δ_{d}, which is the required volume.

We now verify that ˆ1_{N} vanishes on Λ^{∗} \ {0}.

Assume that 0 ≠ ξ ∈ Λ^{∗}. Adding up the equations in (13) we get

K = K(ξ) = −(n_{1} + ⋯ + n_{d}).

If all the coordinates of ξ are non-zero we can write

ˆ1_{N}(ξ) = \frac{1}{π^{d}ξ_{1} ⋯ ξ_{d}} (∏_{j=1}^{d} sin πξ_{j} − (−1)^{K} ∏_{j=1}^{d} sin πδ_{j}ξ_{j}) .  (15)

Observe from (13) that

sin πξ_{j} = (−1)^{n_{j}} sin πδ_{j+1}ξ_{j+1},

where the subscript arithmetic is done modulo d, from which we get ˆ1_{N}(ξ) = 0, since the factors in the two terms of (15) match one by one.

It remains to show that ˆ1_{N}(ξ) = 0 even when ξ has some coordinate equal to 0, say ξ_{1} = 0.

Consider the numbers ξ_{1}, …, ξ_{d} arranged in a cycle and let

I = {ξ_{m}, ξ_{m+1}, …, ξ_{1}, …, ξ_{k−1}, ξ_{k}}

be an interval around ξ_{1} which is maximal with the property that all its elements are 0. Then ξ_{m−1} ≠ 0 and ξ_{k+1} ≠ 0 and from (13) we get

ξ_{m−1} − δ_{m}ξ_{m} = n_{m} and ξ_{k} − δ_{k+1}ξ_{k+1} = n_{k}.  (16)

We deduce that n_{m} and n_{k} are both non-zero and therefore that ξ_{m−1} and δ_{k+1}ξ_{k+1} are both non-zero integers and sin πξ_{m−1} = sin πδ_{k+1}ξ_{k+1} = 0. This means that both terms in (11) vanish and so does ˆ1_{N}(ξ). ■

So we proved that for the lattice Λ = A^{⊤}Z^{d}, where A is defined in (14), we have N ⊕ Λ = R^{d}. Clearly, if σ is a cyclic permutation of {1, …, d} and if instead of the matrix A we have the matrix A′ whose i-th row has 1 on the diagonal, −δ_{σi} at column σi and 0 elsewhere, we get again a lattice tiling with the lattice (A′)^{⊤}Z^{d}. Stein [St] as well as Schmerl [Sch] have shown that these (d − 1)! lattice tilings of the notched cube (one for each cyclic permutation of {1., …, d}) are all non-isometric when the side-lengths δ_{j} are all distinct.

A deeper result of Schmerl [Sch] is that there are no other translational tilings of the notched cube, lattice or not. This is something that I cannot prove with the harmonic analysis approach.

2.3 Extended cubes

Let us now allow the parameters δ_{1}, …, δ_{d} to take on any non-zero real value subject only to the restriction

δ_{1} ⋯ δ_{d} ≠ 1,  (17)

and let the function φ(ξ) be equal to the right-hand side of (11). Let again the matrix A be defined by (14) and Λ = A^{⊤}Z^{d} as before. We have again det A = 1 − δ_{1} ⋯ δ_{d}.

The calculations we did in §2.2 show that φ vanishes on Λ^{∗} \ {0}, hence, if φ̌ is the inverse FT of φ, φ̌ tiles R^{d} with Λ and weight

\frac{φ(0)}{|1 − δ_{1} ⋯ δ_{d}|} = sgn(1 − δ_{1} ⋯ δ_{d}),  (18)

where sgn(x) = ±1 is the sign of x.

The function φ̌ is given by

φ̌(x) = 1_{Q}(x) − sgn(δ_{1} ⋯ δ_{d})ψ(x),  (19)

where

ψ(x) = 1_{Q} (\frac{x_{1} − (1 − δ_{1})/2}{|δ_{1}|}, …, \frac{x_{d} − (1 − δ_{d})/2}{|δ_{d}|}) .  (20)

Figure 2: Some extended cubes in R^{3} that admit lattice tilings. The codimension of the intersection is 1 (left) and 3 (right).

Notice that ψ(x) is the indicator function of a rectangle R = R(δ_{1}, …, δ_{d}) with sidelengths |δ_{1}|, …, |δ_{d}| centered at the point

P = (\frac{1}{2}, …, \frac{1}{2}) − \frac{1}{2} (δ_{1}, …, δ_{d}) .  (21)

The rectangle R intersects the interior of Q only in the case δ_{1} > 0, …, δ_{d} > 0 and when this happens φ̌ is an indicator function only if we also have δ_{1} ≤ 1, …, δ_{d} ≤ 1, which is the case of the notched cube that we examined in §2.2.

Otherwise (not all the δs are non-negative) φ̌ is an indicator function only when sgn(δ_{1} ⋯ δ_{d}) = −1, i.e., the number of negative δs is odd. In this case we have that

φ̌ = 1_{Q∪R}

and from (18) we get that Q ∪ R tiles with Λ and weight 1. We can now prove the following.

Theorem 8 (Lattice tiling by extended cubes) Let Q and R be two axis-aligned rectangles in R^{d} with sides of arbitrary length and disjoint interiors. Assume also that Q and R have a vertex K in common and intersection of odd codimension.

Then Q ∪ R admits a lattice tiling of R^{d} of weight 1.

For example, the extended cubes shown in Figure 2 admit lattice tilings of R^{3}. Proof. After a linear transformation we can assume that Q = [−1/2, 1/2]^{d}, that Q and R share the vertex K = (1/2, …, 1/2) and that Q ∩ R has codimension k (an odd number) and

Q ∩ R ⊆ \{x ∈ Q : x_{1} = ⋯ = x_{k} = \frac{1}{2}\}.

Let the side-lengths of R be γ_{1}, …, γ_{d} > 0. Define

δ_{j} = \{ \begin{matrix}−γ_{j}, & if 1 ≤ j ≤ k, \\ γ_{j}, & if k + 1 ≤ j ≤ d. \end{matrix}

It follows that, with this assignment for the δ_{j}, the indicator function of R is equal to the function −sgn(δ_{1} ⋯ δ_{d})ψ(x) of (19) and tiling follows from the previous discussion. ■

I believe that extended cubes with an intersection of even codimension do not tile, at least not for general side-lengths. This is clear in dimension two and it is conceivable that some combinatorial argument could easily show this in any dimension. The Harmonic Analysis approach does not seem to be very helpful when one tries to disprove that something is a (translational) tile.

§3. Bibliography

[Con] J.P Conlan, Derived tilings, J. Comb. Th. (A) 20 (1976), 34-40.

[Haj] G. Hajós, Über einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem Würfelgitter, Math. Z. 47 (1941), 427-467.

[K] M.N. Kolountzakis, A new estimate for a problem of Steinhaus, Inter. Math. Res. Notices, 1996, 11, 547-555.

[KLa] M.N. Kolountzakis and J.C. Lagarias, Tilings of the line by translates of a function, Duke Math. J. 82 (1996), 3, 653-678.

[Sch] J.H. Schmerl, Tiling space with notched cubes, Discr. Math. 133 (1994), 225-235.

[St] S. Stein, The notched cube tiles R^{n}, Discr. Math. 80 (1990), 335-337.

[Str] R. Strichartz, A guide to distribution theory and Fourier Transforms, CRC Press, Boca-Raton, Florida (1994).