THE LAGARIAS-SHOR TILING OF R^{12}

TERENCE TAO

Abstract. We describe Lagarias and Shor’s tiling of R^{12} into unit cubes in which no two cubes share a face.

1. Introduction

Let R^{n} be a Euclidean space. We define a cube in R^{n} to be any translate of the unit cube [0, 1]^{n}. If X ⊂ R^{n} is an (open) subset of Euclidean space, we define a tiling of X to be any partition^{1} X of X into unit cubes. We call X tileable if X admits a tiling.

We call a tiling skew if no two cubes in the tiling share an face (a face is a codimension one facet). We say that X is skew-tileable if it admits a skew tiling.

Simple example of skew-tileable sets are provided by the checkerboard sets

W HIT E_{n} := {(x_{1}, …, x_{n}) ∈ R^{n} : ⌊x_{1}⌋ + … + ⌊x_{n}⌋ is even }

and

BLACK_{n} := {(x_{1}, …, x_{n}) ∈ R^{n} : ⌊x_{1}⌋ + … + ⌊x_{n}⌋ is odd }

where ⌊x⌋ is the greatest integer function.

What is less obvious is whether R^{n} is skew-tileable. In fact

Theorem 1.1. The set R^{n} is skew-tileable when n ≥ 10 [2], and is not skew-tileable when n ≤ 6 [1]

The intermediate dimensions n = 7, 8, 9 remain open.

The purpose of this note is to give an exposition of the argument in [2] in the model case n = 12.

We shall approach this problem in stages. We shall start by considering pathological tilings in R^{1}, and then R^{2}, and then R^{4}, and then finally R^{12}. As we shall see, the higher the dimension, the stranger tilings can become.

We use A ⊎ B to denote the disjoint union of A and B (this is the same as A ∪ B but is only defined when A and B are disjoint). We say that a collection of sets X_{1}, …, X_{k} in R^{n} have distinct skew-tilings if they can be skew-tiled by sets X_{1}, …, X_{k}, no two of which share a cube in common.

2. Pathological tilings of R^{1}

One dimensional tilings are not very pathological, however it is important to note that R can act like a “sliding deadbolt”:

Proposition 2.1. There exist W, B, W′, B′ ⊂ R such that R can be partitioned as R = W ⊎ B = W′ ⊎ B′, and such that W, B, W′, B′ have distinct skew-tilings.

1991 Mathematics Subject Classification. 42A.

1Throughout this note we shall ignore sets of measure zero.

Proof Set W := W HIT E_{1}, B := BLACK_{1}, W′ := W HIT E_{1} + t, B′ := BLACK_{1} + t, where t is any non-integer real (t = 1/2 will do).

3. Pathological tilings of R^{2}

To move from 1d to 2d we shall need some lemmas about Cartesian products. The following lemma is trivial:

Lemma 3.1. Let X ⊂ R^{n} and Y ⊂ R^{m}.

• If X and Y are both tileable, then so is X × Y.

• If X and Y are both skew-tileable, then so is X × Y.

The next lemma is also easy, and is left to the reader:

Lemma 3.2. Let X_{1}, …, X_{k} ⊂ R^{n} be disjoint skew-tileable sets, and let and Y_{1}, …, Y_{k} ⊂ R^{m} be sets with distinct skew-tilings. Then (X_{1} ×Y_{1})⊎…⊎(X_{k} ×Y_{k}) is skew-tileable.

Now we construct a pathological 2D tiling.

Proposition 3.3. There exist sets C, C′, D, D′, G_{1}, G_{2}, G_{3}, G_{4} ⊂ R^{2}, with distinct skew-tilings, such that we have the partitions

R^{2} = C ⊎ D ⊎ G_{1} = C ⊎ D′ ⊎ G_{2} = C′ ⊎ D ⊎ G_{3} = C′ ⊎ D′ ⊎ G_{4}.

The point is that either of C or C′ is free to combine with either of D or D′. This phenomenon of freedom of association only occurs in two dimensions or higher. Proof Let W, B, W′, B′ be as in Proposition 2.1, and set

C := W × W; C′ := W′ × W′; D := B × B′; D′ := B′ × B

and

G_{1} := (W × B′) ∪ (B × W′); G_{2} := (W′ × B) ∪ (B′ × W);
G_{3} := (W × B′) ∪ (B′ × W′); G_{4} := (W′ × B′) ∪ (B′ × W).

The claims are easily verified (using the above Lemmata if necessary).

4. Pathological tilings of R^{4}

Now we move from 2D to 4D. We begin by constructing a tiling in R^{4} with four sets of sliding deadbolts.

Proposition 4.1. There exists a partition

R^{4} = (W HIT E_{1}×R×C)∪(BLACK_{1}×R×C′)∪(R×W HIT E_{1}×D)∪(R×BLACK_{1}×D′)∪Ω

where C, C′, D, D′ ⊂ R^{2} have distinct skew-tilings, and Ω ⊂ R^{4} is also skewtileable.

If the reader wishes to draw pictures, I recommend that C, C′, D, D′ be depicted as one-dimensional and Ω as three dimensional. Proof Let C, C′, D, D′, G_{1}, G_{2}, G_{3}, G_{4} be as in Proposition 3.3. If we set

Ω :=(W HIT E_{1} × W HIT E_{1} × G_{1}) ⊎ (W HIT E_{1} × BLACK_{1} × G_{2})
⊎ (BLACK_{1} × W HIT E_{1} × G_{3}) ⊎ (BLACK_{1} × BLACK_{1} × G_{4})

we see the claims follow from Lemmata 3.1, 3.2.

Now we slide the deadbolts to obtain a doubly skew-tileable set.

Definition 4.2. A set X ⊂ R^{n} is doubly skew-tileable if it has two distinct skewtilings X_{1}, X_{2} (so the two tilings do not share a cube in common).

Such sets are already quite unintuitive, and appear to only exist in four dimensions and higher.

Proposition 4.3. There exists a partition R^{4} = A ⊎ B where A is doubly skewtileable, and B is skew-tileable.

Proof Let t be a real number to be chosen later, and set

B :=(W HIT E_{1} × (W HIT E_{1} + t) × C) ⊎ (BLACK_{1} × (BLACK_{1} + t) × C′)

⊎ ((W HIT E_{1} − t) × W HIT E_{1} × D) ⊎ ((BLACK_{1} − t) × BLACK_{1} × D′)

In other words, we slide the four deadbolts by t, divide them into cubes, and let B be every other cube from the deadbolts. We of course set A to be the complement set:

A := R^{4}\B

= (W HIT E_{1} × (BLACK_{1} + t) × C) ⊎ (BLACK_{1} × (W HIT E_{1} + t) × D)

⊎ ((BLACK_{1} − t) × W HIT E_{1} × E) ⊎ ((W HIT E_{1} − t) × BLACK_{1} × F) ⊎ Ω

Observe that A, B are skew-tileable for generic values of t (for instance, the cubes in Ω will only share a face with a cube in W HIT E_{1} × (BLACK_{1} + t) × C for countably many values of t).

Also, B is symmetric under the reflection

(x_{1}, x_{2}, x_{3}, x_{4}) ↦ (x_{2} − t, x_{1} + t, x_{3}, x_{4})

so A must also be symmetric under this reflection. Since A already has one skewtiling, this reflection gives another skew-tiling, which will be completely disjoint from the first skew-tiling for generic values of t (note that the distinctness assumptions on C, D and E, F the cubes in the deadbolts do not reflect onto each other). Thus A is double skew-tileable, and the proof of Proposition 4.3 is complete.

5. Pathological tilings of R^{12}

Let A, B ∈ R^{4} be as in Proposition 4.3. We are about ready to use these two sets to construct our most pathological tiling, namely a skew-tiling of R^{12}. We first need some intermediate pathologies though.

We begin by creating skew-tileable sets which are translation invariant.

Definition 5.1. A set X ⊂ R^{n} is translation-invariant if there exists a non-zero vector v such that X + tv = X for all t ∈ R.

For instance, any set of the form X = Y × R is translation invariant.

Lemma 5.2. If X ⊂ R^{n} is doubly skew-tileable and Y ⊂ R^{m} is tileable, then X × Y is skew-tileable.

Proof We first partition Y by the disjoint union of two skew-tilings Y_{1} and Y_{2}. Let Y be any tiling of Y. We decompose the cubes in Y into two disjoint subcollections, depending on whether the lower left corner of the cube is in W HIT E_{m} or not. It is easy to verify that each subcollection is skew, and the claim follows.

Since X is doubly skew-tileable, it has two distinct skew-tilings X_{1} and X_{2}. By Lemma 3.2 the collection (X_{1} × Y_{1}) ∪ (X_{2} × Y_{2}) is then a skew-tiling of X × Y, as desired.

The great advantage of having skew-tileable translation invariant sets is that they are easy to glue together:

Lemma 5.3. If X, Y ⊂ R^{n} are disjoint and skew-tileable, and Y is translation invariant, then X ∪ Y is also skew-tileable.

Proof Let X and Y be skew-tilings of X and Y respectively. We would like to conclude that X ∪ Y is skew, but this unfortunately does not always hold. To remedy this we simply use X ∪ (Y + tv) instead, where v is the vector in which Y is translation invariant. Since there are uncountably many values of t and only countably many cubes, it is easy to see that this collection will be skew for at least one value of t, and the claim follows.

Now we can show R^{12} is skew-tileable. Observe the partitioning

R^{12} = (A × A × A) ⊎ (B × B × B) ⊎ (A × B × R^{4}) ⊎ (R^{4} × A × B) ⊎ (B × R^{4} × A). (1)

From Lemmata 3.1, 3.2 we see that (A × A × A) ⊎ (B × B × B) is skew-tileable. From Lemma 5.2 we see that the sets (A × B × R^{4}), (R^{4} × A × B), (B × R^{4} × A) are all translation-invariant and skew-tileable. From Lemma 5.3 we thus see that R^{12} is skew-tileable as desired.

6. Postscript

One can easily show that the above tilings can in fact be placed in a standard form, namely that they are periodic with period (2Z)^{n} and have vertices at (Z/2)^{n}.

Lagarias and Shor can refine the above construction to also show that R^{10} is not skew-tileable. Again their starting point is Proposition 4.3. In the argument above, our main partition was (1), which one can think of as a 3D tiling but with each dimension blown up to four dimensions, thus yielding 12 dimensions at the end. A slightly better strategy is to start with a 4D tiling and blow up only two of the four dimensions. The 4D tiling to use is already given in Proposition 4.1, and only the first two dimensions need to be blown up (the tiling is already skew in the other two dimensions). The reader is invited to make the argument rigorous; in any event the argument is already in [2] (though not quite in the same language).

References

[1] K. Corrádi, S. Szabó, A combinatorial approach to Keller’s conjecture, Period. Math. Hungar. 21 (1990), 91–100.

[2] J. Lagarias, P. Shor, Keller’s cube tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. 27 (1992), 279–283.

Department of Mathematics, UCLA, Los Angeles, CA 90024

   E-mail address: tao@math.ucla.edu