Published in Discrete Mathematics 214 (2000), no. 1–3, pp. 255–261.

TILING WITH NOTCHED CUBES

Robert Hochberg and Michael Reid

Department of Mathematical Sciences, University of Delaware and Department of Mathematics, Brown University

March 4, 1999

Abstract. In 1966, Golomb showed that any polyomino which tiles a rectangle also tiles a larger copy of itself. Although there is no compelling reason to expect the converse to be true, no counterexamples are known. In 3 dimensions, the analogous result is that any polycube that tiles a box also tiles a larger copy of itself. In this note, we exhibit a polycube (a ‘notched cube’) that tiles a larger copy of itself, but does not tile any box, and obtain several related results about tiling with this figure. We also obtain analogous results in all dimensions d ≥ 3.

Golomb [1] shows that any polyomino that tiles a rectangle also tiles a larger copy of itself. There is no reason to expect that the converse holds; however, every polyomino that is known to tile a larger copy of itself also tiles a rectangle. This is considered, for example, in [2, Problem 6.10]. We examine here the corresponding question in higher dimensions.

Definitions. A cell in d-dimensional space ℝ^{d} is a region

C(n_{1}, n_{2}, …, n_{d}) = {(x_{1}, x_{2}, …, x_{d}) ∈ ℝ^{d} | n_{i} ≤ x_{i} ≤ n_{i} + 1 for i = 1, 2, …, d}

where n_{1}, n_{2}, …, n_{d} are integers. A (d-dimensional) polycube is a finite union of cells, whose interior is connected. A (d-dimensional) box is a subset of ℝ^{d} which is congruent to

{(x_{1}, x_{2}, …, x_{d}) ∈ ℝ^{d} | 0 ≤ x_{i} ≤ a_{i} for i = 1, 2, …, d}

for some positive a_{1}, a_{2}, …, a_{d}. A (d-dimensional) orthant is a subset of ℝ^{d} which is congruent to the positive orthant

{(x_{1}, x_{2}, …, x_{d}) ∈ ℝ^{d} | x_{i} ≥ 0 for i = 1, 2, …, d}.

A reptile is a figure that tiles a figure similar to itself, with ratio of similitude greater than 1. An N-reptiling by a figure is a tiling of a larger figure similar to the original, which uses N tiles. A (d-dimensional) doublecell is a region

Q(2n_{1}, 2n_{2}, …, 2n_{d}) = {(x_{1}, x_{2}, …, x_{d}) ∈ ℝ^{d} | 2n_{i} ≤ x_{i} ≤ 2n_{i} + 2 for i = 1, 2, …, d}

for some integers n_{1}, n_{2}, …, n_{d}. Note that different doublecells do not share any cells.

Typeset by AMS-TEX

Definition. A (d-dimensional) notched cube is a polycube congruent to the closure of Q(0, 0, …, 0) ∖ C(1, 1, …, 1), i.e. the polycube which is the union of the 2^{d} − 1 cells

{C(n_{1}, n_{2}, …, n_{d}) | each n_{i} = 0 or 1, and some n_{i} = 0}.

d = 2  d = 3

Figure 1. Notched cubes.

Some previous authors [3, 4] considered tilings of ℝ^{d} by translates only of a notched cube. Here we allow rotations as well as translations; reflections are redundant.

Proposition 1. The (d-dimensional) notched cube has a unique 2^{d}-reptiling.

Proof. We must tile the region X consisting of cells

{C(n_{1}, n_{2}, …, n_{d}) | each n_{i} = 0, 1, 2 or 3, and some n_{i} = 0 or 1}.

There are 2^{d} − 1 of these cells in which each n_{i} is either 0 or 3. No tile can cover more than one of these cells, so each is covered by a different tile. Each of these 2^{d} − 1 tiles must then be contained in a doublecell. There is one remaining tile to be used, and it must cover one cell of each doublecell of X. Thus it must cover the cells

{C(n_{1}, n_{2}, …, n_{d}) | each n_{i} = 1 or 2, and some n_{i} = 1},

and this forces the orientation of the remaining tiles. This gives the unique reptiling. □

Proposition 2. Any (d-dimensional) polycube reptile covers at least one corner of its bounding box. Any reptiling by such a polycube can be placed in the corner of the positive orthant in such a way that the tiling can be extended to a tiling of the positive orthant.

Proof. We refer the reader to [1, Theorem 5], for Golomb’s proof of this result in two dimensions, which easily generalizes. □

Example. The 2^{d}-reptiling constructed in Proposition 1 sits in the corner of the orthant in the same orientation as the individual tile that occurs in the corner. We may consider this as an extension of the individual tile in the corner to a 2^{d}-reptiling. Since this 2^{d}-reptiling occurs in the same orientation, we may extend this to a 4^{d}-reptiling, which also occurs in the same orientation. This can be further extended to an 8^{d}-reptiling, and so forth. The union of these reptilings is a tiling of the positive orthant. We will prove below (Theorem 1) that this is the unique tiling of the positive orthant by notched cubes, if d ≥ 3.

Proposition 3. Let d ≥ 3, and suppose that the positive orthant of ℝ^{d} is tiled by notched cubes and solid cubes of edge length 2. Then each doublecell completely contains one of the tiles. Equivalently, the 2^{d} cells of each doublecell are partitioned either [[2^{d} − 1, 1]] or [[2^{d}]] among different tiles.

Proof. We prove this first for d = 3, and then proceed by induction.

Let d = 3 and suppose that the Proposition is false. Then some doublecell has an invalid partition, i.e. other than [[7, 1]] or [[8]]. Among such doublecells, consider one, Q = Q(n_{1}, n_{2}, n_{3}), which is closest to the origin, in the sense that n_{1} +n_{2} +n_{3} is minimal. Let A, B, C, D, E, F, G and H be the eight cells in Q, where A = C(n_{1}, n_{2}, n_{3}) is the cell closest to the origin, and the others are as indicated in Figure 2.

Figure 2. The doublecell Q.

Claim 1. The tile that covers cell A does not cover any other cells of Q.

Consider the tile that covers cell A; it covers either 1, 2, 3, 4, 7 or 8 cells of the doublecell. If this number is 7 or 8, then the partition is valid, contrary to hypothesis. If this number is 4, say the tile covers cells A, B, G and C, then the tile covers 3 or 4 cells of the doublecell adjacent to Q through face ABGC. But that doublecell is closer to the origin than Q is, and it has an invalid partition, contradiction. Similarly, if the number of cells is 3 or 2, then we have a closer doublecell with an invalid partition summand (4 or 2), again a contradiction. This proves Claim 1.

Note also that the bounding box of the tile that covers A does not contain cell B. If it did, then the tile would necessarily be a notched cube, and it would cover 2 cells from each of three adjacent doublecells. These doublecells are closer than Q, so this is a contradiction. Similarly the bounding box of the tile does not contain cell C or cell D. Claim 2. The tile that covers cell B covers at least one other cell of the doublecell Q.

Suppose, to the contrary, that it covers no other cells of Q. If its bounding box contains either A, F or G, then the tile covers 2 cells from either the doublecell adjacent through face ABF D or the doublecell adjacent through face ABGC. These are both closer than Q, so this is a contradiction. Thus, its bounding box contains one cell in each of 8 different doublecells. The tile then contains 1 cell in at least two of the three doublecells which share edge AB. The same is also true for the tile that covers A, so at least one of these three closer doublecells has two summands of 1 in its partition. This contradiction proves Claim 2.

Similarly, the tile that covers cell C covers at least one other cell of Q, and the same for the tile that covers D. Claim 3. Cells B and C are covered by different tiles.

If they were covered by the same tile, it would necessarily be a notched cube, and would also cover G. Then it either covers the remaining 4 cells of Q, or 4 cells of the doublecell adjacent through face ABGC. In the first case, the partition for Q is [[7, 1]], which is valid, contrary to hypothesis. In the second case, the adjacent doublecell is a closer one with an invalid partition, a contradiction. This proves Claim 3.

Similarly, cells C and D are covered by different tiles, and the same for cells D and B. Therefore these three cells are covered by different tiles, and each of these three tiles covers at least 2 cells of Q. Since 1 + 2 + 3 + 3 > 8, at least two of these tiles cover exactly 2 cells of Q. Up to symmetry, there are two possibilities for these two tiles. Case 1. One tile covers B and F, and the other covers C and E. Then the tile that covers D cannot cover any other cells of Q, which contradicts Claim 2. Case 2. One tile covers B and F, and the other covers C and G. Then the first tile covers either 1 or 2 cells of the doublecell adjacent through face ADF B. This is a closer doublecell, so the tile covers only 1 of its cells. Similarly, the second tile covers 1 cell of the doublecell adjacent through face ABGC. However, the tile that covers A covers 1 cell of either (or both) of these adjacent doublecells. Therefore, one of these closer doublecells has two summands of 1, and thus has an invalid partition, a contradiction.

This completes the proof for d = 3.

Now suppose that the Proposition holds in d − 1 dimensions. Consider a tiling of the positive orthant of ℝ^{d} by notched cubes and solid cubes of edge length 2, and let Q(2n_{1}, 2n_{2}, …, 2n_{d}) be a doublecell. By intersecting the tiling with the hyperplane defined by x_{d} = 2n_{d} + \frac{1}{2}, we get a tiling of a (d − 1)-dimensional orthant by (d − 1)-dimensional notched cubes and (d − 1)-dimensional solid cubes of edge length 2. The induction hypothesis implies that some tile covers at least 2^{d−1} − 1 cells of the (d − 1)-dimensional doublecell Q(2n_{1}, 2n_{2}, …, 2n_{d−1}). The corresponding d-dimensional tile is bounded by either

x_{d} = 2n_{d} − 1  and  x_{d} = 2n_{d} + 1

or by

x_{d} = 2n_{d}  and  x_{d} = 2n_{d} + 2

In the first case, intersect with the hyperplane x_{d−1} = 2n_{d−1} + \frac{1}{2}. The resulting tile covers exactly 2^{d−2} cells from some (d − 1)-dimensional doublecell, which contradicts the induction hypothesis. Therefore the second case holds, and thus the original d-dimensional doublecell completely contains this tile. This shows that the Proposition holds in d dimensions, which completes the induction. □

Proposition 4. If d ≥ 3, then any tiling of the positive orthant of ℝ^{d} by notched cubes occurs from a tiling by 2^{d}-reptilings of the notched cube. Also, the tile that covers the cell in the corner, C(0, 0, …, 0) occurs in the orientation that does not cover the cell C(1, 1, …, 1).

Proof. Each notched cube that is not contained in a single doublecell covers one cell in each of 2^{d} − 1 different doublecells. For each such notched cube, consider that tile, along with the notched cubes that cover the remaining 2^{d} −1 cells of these doublecells. These 2^{d} notched cubes cover all the cells of 2^{d} −1 doublecells, and no other cells. Thus, they form a 2^{d}-reptiling of the notched cube. Furthermore, the reptilings formed this way are disjoint (contain no common cells), and they tile the positive orthant. This proves the first statement. For the second statement, note that any orientation of the 2^{d}-reptiling in the corner of the orthant induces the required orientation of the notched cube in that corner. □

Our desired results now follow quickly.

Theorem 1. If d ≥ 3, then there is a unique tiling of the positive orthant by notched cubes.

Proof. From Proposition 4, any tiling of the orthant by notched cubes is induced from a tiling by 2^{d}-reptilings, which is induced from a tiling by 2^{2d}-reptilings, and so forth. Furthermore, for each k, the 2^{kd}-reptiling in the corner of the orthant occurs in the orientation described in Proposition 4. This 2^{kd}-reptiling is a union of 2^{(k−1)d}-reptilings, so their positions are uniquely determined, from Proposition 1. Each of the 2^{(k−1)d}-reptilings is a union of 2^{(k−2)d}-reptilings, so their positions are also uniquely determined, and so on. Therefore, for each k, the tiling of the 2^{kd}-reptiling in the corner of the orthant is uniquely determined. The union of these 2^{kd}-reptilings, for k = 1, 2, … is the tiling of the entire orthant, so it is uniquely determined. □

This shows that the only tiling of the orthant by notched cubes is the one described in the Example above.

Theorem 2. If d ≥ 3, then there is an m^{d}-reptiling of the notched cube if and only if m is a power of 2. Furthermore, if m is a power of 2, there is a unique m^{d}-reptiling.

Proof. We argue by induction on m. The result is trivial for m = 1. Let m > 1, and suppose the Theorem holds for all integers less than m. Suppose there is an m^{d}-reptiling. From Proposition 2, the reptiling occurs in the corner of the positive orthant for some tiling of the orthant. It is easy to see that if m > 1 is odd, then any placement of an m^{d}-reptiling of the notched cube covers exactly 2^{d−1} cells from some doublecell. From Proposition 3, such an m^{d}-reptiling cannot be extended to a tiling of the orthant.

Thus m = 2n is even. The reptiling can be placed in the corner of the orthant so that it can be extended to a tiling of the orthant. Any orientation of the m^{d}-reptiling in the corner covers either all or none of the cells from a given doublecell. Therefore, as in the proof of Proposition 4, the m^{d}-reptiling is the union of 2^{d}-reptilings. These reptilings, n^{d} in number, form an n^{d}-reptiling of the notched cube. From the induction hypothesis, n is a power of 2, whence m = 2n is also. Furthermore, the n^{d}-reptiling is unique, from the induction hypothesis. Since the 2^{d}-reptiling is unique (Proposition 1), so is the m^{d}-reptiling. This completes the induction. □

Theorem 3. If d ≥ 3, then the notched cube does not tile any box.

Proof. Suppose to the contrary, that it tiles an n_{1} × n_{2} × ⋯ × n_{d} box. These boxes tile an N × N × ⋯ × N cube, where N = n_{1}n_{2} ⋯ n_{d}, which in turn tile an N^{d}-reptiling of the notched cube. However, N = n_{1}n_{2} ⋯ n_{d} is divisible by 2^{d} − 1, so it isn’t a power of 2, which contradicts Theorem 2. □

It might be worthwhile to mention what happens in 2 dimensions. In this case, the notched cube is the L tromino. The L tromino tiles a 2 × 3 rectangle and it has m^{2}-reptilings for all m; they are unique only for m = 1 and m = 2. It also tiles a quadrant in uncountably many different ways. The question remains open — to prove or disprove the existence of a (2-dimensional) reptile polyomino which does not tile a rectangle.

References

1. Solomon W. Golomb, Tiling with polyominoes, Journal of Combinatorial Theory 1 (1966), 280–296. MR 33 #6498

2. George E. Martin, Polyominoes, Mathematical Association of America, Washington, DC, 1991. MR 93d:00006

3. James H. Schmerl, Tiling space with notched cubes, Discrete Mathematics 133 (1994), no. 1–3, 225–235. MR 95h:52033 4. Sherman Stein, The notched cube tiles ℝ^{n}, Discrete Mathematics 80 (1990), no. 3, 335–337. MR 91b:52016

Old addresses:  Current addresses:
Robert Hochberg  Robert Hochberg
Department of Mathematical Sciences  Department of Mathematics
University of Delaware  University of Dallas
Newark, DE 19716  1845 East Northgate Drive
U.S.A.  Irving, TX 75062

hochberg@dimacs.rutgers.edu  U.S.A.

                                                         hochberg@udallas.edu

Michael Reid  Michael Reid
Department of Mathematics  Department of Mathematics
Box 1917  University of Central Florida
Brown University  Orlando, FL 32816
Providence, RI 02912  U.S.A.

U.S.A.  reid@cflmath.com

reid@math.brown.edu