Published in Journal of Combinatorial Theory, Series A, 111 (2005), no. 1, pp. 89–105.

KLARNER SYSTEMS AND TILING BOXES WITH POLYOMINOES

Michael Reid

University of Central Florida

November 12, 2004

Abstract. Let T be a protoset of d-dimensional polyominoes. Which boxes (rectangular parallelepipeds) can be tiled by T ? A nice result of Klarner and Göbel asserts that the answer to this question can always be given in a particularly simple form, namely, by giving a finite list of “prime” boxes. All other boxes that can be tiled can be deduced from these prime boxes. We give a new, simpler proof of this fundamental result. We also show that there is no upper bound to the number of prime boxes, even when restricting attention to singleton protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.

1. Introduction

A polyomino is a finite union of squares of the infinite chessboard. A d-dimensional polyomino is a finite union of cubes of an infinite d-dimensional “chessboard”. It is traditional also to require that they be “rookwise connected” (equivalently, have connected interior) but we do not require this, and it does not affect our results in any way.

Let T be a protoset of d-dimensional polyominoes. We wish to know which regions can be tiled by the protoset. Here, T is the set of shapes that may occur in the tiling. Any shape in T may be used repeatedly, if desired, and there is no requirement that every shape is actually used.

We will focus our attention on the problem of tiling boxes (i.e. rectangular parallelepipeds) here. Our interest is two-fold. Firstly, boxes are the simplest type of (finite) regions. Secondly, there is some structure; from tilings of several boxes, others can be deduced. The topic of tiling boxes by polyominoes has already received considerable attention, for example [1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 19, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32]

Typeset by AMS-TEX

2000 Mathematics Subject Classification. 52C20 (05B45).

Key words and phrases. tiling, polyomino, rectangle, prime rectangle.

In the next section, we introduce the abstract notion of a Klarner system, and prove a finiteness theorem for such systems. We then interpret this in terms of tiling boxes with polyominoes, to show that every protoset has only finitely many prime boxes. (This is the result of Klarner and Göbel.) In section 4, we show that there is no upper bound to the number of primes, even if restricting attention to a narrow class of protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.

2. Klarner Systems

2.1. Definition. A (d-dimensional) Klarner system is a subset J ⊆ ℕ^{d} with the property that if both (a_{1}, a_{2}, …, a_{i−1}, a_{i}, a_{i+1}, …, a_{d}) and (a_{1}, a_{2}, …, a_{i−1}, a′_{i}, a_{i+1}, …, a_{d}) are in J, then so is (a_{1}, a_{2}, …, a_{i−1}, a_{i} + a′_{i}, a_{i+1}, …, a_{d}).

2.2. Examples.

(1) J = ℕ^{d}.

(2) Let T be a collection of d-dimensional polyominoes, and take

J = {(a_{1}, a_{2}, …, a_{d}) | T tiles an a_{1} × a_{2} × ⋯ × a_{d} box } .

Indeed, if T tiles two boxes that have the same dimensions in all but one coordinate, two such tilings may be juxtaposed to give a tiling of a larger box.

(3) As (2) above, but with T a collection of translation-only polyominoes. This means that the prototiles are each given in a fixed orientation, and when one occurs in the tiling, it must be used in the same orientation.

Examples (2) and (3) are our main motivation.

2.3. Proposition. (a) An increasing union of Klarner systems is also a Klarner system.

(b) Any non-empty intersection of Klarner systems is also a Klarner system.

Proof. Immediate. □

2.4. Definition. Let S ⊆ ℕ^{d} be any set. The Klarner system generated by S is the smallest Klarner system containing S, denoted by K(S). Equivalently, it is the intersection of all Klarner systems that contain S. The Klarner system ℕ^{d} certainly contains S, so this intersection is non-empty.

2.5. Definition. If J ⊆ ℕ^{d} is a Klarner system, then a prime of J is a d-tuple a = (a_{1}, a_{2}, …, a_{d}) ∈ J such that J \ {a} is also a Klarner system.

This definition deserves a few words of explanation. If a ∈ J is not prime, then J \ {a} generates J as a Klarner system. This means that the d-tuple a = (a_{1}, a_{2}, …, a_{d}) can be “decomposed” into two smaller elements of J. In other words, for some index i, there are (a_{1}, a_{2}, …, a_{i−1}, a′_{i}, a_{i+1}, …, a_{d}) and (a_{1}, a_{2}, …, a_{i−1}, a′′_{i}, a_{i+1}, …, a_{d}) in J, with a′_{i} + a′′_{i} = a_{i}. A d-tuple a ∈ J is prime if it cannot be decomposed in this manner.

2.6. Proposition. Let J be a Klarner system, and P its set of primes.

(a) P generates J as a Klarner system.

(b) If S generates J, then P ⊆ S.

Proof. (a) If K(P) ≠ J, then choose a “smallest” d-tuple a ∈ J \ K(P). Then a ∉ K(P) ⊇ P, so it can be decomposed into two smaller elements of J. By minimality of a, these two smaller elements are in K(P), whence a is also, a contradiction.

(b) If a ∈ P \ S, then K(S) ⊆ K(J \ a) = J \ a, a contradiction. □

2.7. Theorem. If J ⊆ ℕ^{d} is a Klarner system, then its set of primes is finite.

Proof. We note that it suffices to prove that J has a finite generating set. This we prove by induction on the dimension, d.

Suppose that d = 1. If J is empty, then its set of primes is also empty. Otherwise, let m be the minimal element of J. For 1 ≤ i < m, let a_{i} be the smallest element of J that is congruent to i mod m, if it exists. Then the finite set {m, a_{i} | 1 ≤ i < m} generates J. This proves the case d = 1.

Now suppose that the Theorem is true in d−1 dimensions, that is, all (d−1)-dimensional Klarner systems are finitely generated. Let J ⊆ ℕ^{d} be a d-dimensional Klarner system. For m ∈ ℕ, let

J(m) = {(a_{1}, a_{2}, …, a_{d−1}) ∈ ℕ^{d−1} | (a_{1}, a_{2}, …, a_{d−1}, m) ∈ J} .

We note the following properties of these J(m)’s.

(1) J(m) is a (d − 1)-dimensional Klarner system.

(2) J(m) ∩ J(n) ⊆ J(m + n).

(3) If m divides n, then J(m) ⊆ J(n).

Properties (1) and (2) follow immediately from the definition of Klarner system. Then an easy induction on k shows that J(m) ⊆ J(km), whence (3).

We further claim that:

(4) There is a maximal J(m) (with respect to inclusion), and

(5) The sequence {J(m)} is eventually periodic in m.

Let J_{∞} = ⋃_{m=1}^{∞} J(m!), which is an increasing union, and thus is a (d − 1)-dimensional Klarner system. Therefore, by the induction hypothesis, J_{∞} is finitely generated. For any m, we have J(m) ⊆ J(m!) ⊆ J_{∞}. If S ⊆ J_{∞} is a finite generating set, then S ⊆ J(m_{0}) for some m_{0}, whence J_{∞} ⊆ J(m_{0}). Thus J_{∞} = J(m_{0}), which is therefore maximal. This proves (4).

Let m_{0} be as above, so that J(m_{0}) is maximal. For any k, we have J(k) ⊆ J(k + m_{0}), from (2). Consider the increasing chain J(k) ⊆ J(k + m_{0}) ⊆ J(k + 2m_{0}) ⊆ ⋯ for 1 ≤ k ≤ m_{0}, and let J_{∞,k} be its union, which is a (d − 1)-dimensional Klarner system. As before, J_{∞,k} is finitely generated, so it equals J(k + tm_{0}) for sufficiently large t. This shows that the increasing chain stabilizes, and since there are only finitely many such, the sequence {J(m)} is eventually periodic. This proves (5).

We have shown there is M > 0 such that J(k − m_{0}) = J(k) for all k > M. Let S(k) be a finite set of generators of the (d − 1)-dimensional Klarner system J(k), and let

T (k) = {(a_{1}, a_{2}, …, a_{d−1}, k) | (a_{1}, a_{2}, …, a_{d−1}) ∈ S(k)} .

Let T = ⋃_{k=1}^{M} T (k), which is a finite set. To finish the induction step, we will show that T generates J. Suppose (a_{1}, a_{2}, …, a_{d}) ∈ J. If a_{d} ≤ M, then (a_{1}, a_{2}, …, a_{d−1}) ∈ K(S(a_{d})), so (a_{1}, a_{2}, …, a_{d}) ∈ K(T (a_{d})) ⊆ K(T ). If a_{d} > M, then write a_{d} = k + tm_{0}, where M − m_{0} < k ≤ M, and t > 0. Then (a_{1}, a_{2}, …, a_{d−1}) ∈ J(k + tm_{0}) = J(k), because k > M − m_{0}. Therefore, (a_{1}, a_{2}, …, a_{d−1}, k) ∈ K(T (k)) ⊆ K(T ). Also, (a_{1}, a_{2}, …, a_{d−1}) ∈ J(a_{d}) ⊆ J(m_{0}), so (a_{1}, a_{2}, …, a_{d−1}, m_{0}) ∈ K(T (m_{0})) ⊆ K(T ). Finally, because both (a_{1}, a_{2}, …, a_{d−1}, k) and (a_{1}, a_{2}, …, a_{d−1}, m_{0}) are in K(T ), we also have (a_{1}, a_{2}, …, a_{d}) ∈ K(T ). This completes the induction step, and the proof of the Theorem. □

3. Prime Boxes of Protosets

In this section, we interpret the results of the previous section in terms of tiling boxes with polyominoes, and make the connection to Klarner and Göbel’s result.

Let T be a protoset of d-dimensional polyominoes, and let

J = {(a_{1}, a_{2}, …, a_{d}) | T tiles an a_{1} × a_{2} × ⋯ × a_{d} box } .

As we have seen above, J is a d-dimensional Klarner system.

3.1. Definition. A prime box of the protoset T is an a_{1} × a_{2} × ⋯ × a_{d} box that can be tiled by T , and for which the corresponding d-tuple, (a_{1}, a_{2}, …, a_{d}), is a prime of J.

In many cases, indeed, all cases considered in this paper, the prototiles in T may be rotated and reflected. In such a case, the corresponding Klarner system, and therefore also its set of primes, is invariant under permutation of coordinates. We will consider two boxes to be the “same” prime if they have the same dimensions up to permutation.

3.2. Definition. A box is a strong prime of the protoset T if it can be tiled by T , but cannot be tiled by smaller boxes, each of which can be tiled by T .

3.3. Definition. If P is a polyomino, we say that a box is a [strong] prime of P if it is a [strong] prime of the singleton protoset {P}.

3.4. Remark. Our notion of “strong primality” corresponds to Klarner and Göbel’s notion of “primality”. The reader should be alerted to this difference in terminology.

A simple reformulation of Definition 3.1 gives

3.5. Definition. A box is a prime of the protoset T if it can be tiled by T , but cannot be split into two smaller boxes, both of which can be tiled by T .

From this, it becomes clear that “strong primality” is indeed a stronger condition than “primality”. Finally, rephrasing Theorem 2.7 above, we have

3.6. Theorem. Any protoset of d-dimensional polyominoes has a finite set of prime boxes. □

Klarner and Göbel [22] prove that every protoset has a finite set of strong primes. Unfortunately, their proof appears to have a gap in d ≥ 3 dimensions. This is repaired by Klarner in his unpublished note [20]. Since every strongly prime box of a protoset T is a prime of T , Theorem 3.6 extends the result of Klarner and Göbel. In fact, Klarner mentions at the end of his note [20] that an alteration of his argument can obtain this stronger result. Our approach simplifies the proof and simultaneously obtains the stronger statement.

Difference between primes and strong primes.

As remarked above, every strongly prime box is a prime box. It is natural to ask if, for any protoset, it has prime boxes that are not strongly prime. Indeed, there are such protosets for which this phenomenon occurs, even in fairly simple cases. In 3 (or more) dimensions, it can happen even for a singleton protoset. This notion has been considered briefly by Klarner [21]. In particular, he gives Singmaster’s example (3.7) and states Proposition 3.10 (without proof).

3.7. Example. (Singmaster) Let P be a 1 × 3 × 4 box. Then P tiles a 5 × 5 × 12 box, (we leave the construction to the reader) but cannot do so with a plane of cleavage (a plane that “decomposes” the box into two smaller boxes, but without intersecting the interior of any tile). Thus the 5 × 5 × 12 box is a prime of P, but not a strong prime. Since P is itself a box, its only strong prime is itself. The 5 × 5 × 12 box is the only other prime.

There are also cases in 2 dimensions of prime rectangles that are not strongly prime.

3.8. Example. Let T = {  ,  }. Then T tiles a 5 × 5 square, but cannot do

so with a line of cleavage. (In fact, the tiling is just a cross-section of the tiling of Example 3.7.) The 5 × 5 square is a prime of T , but not a strong prime. The only strong primes of T are the 1 × 3 and 1 × 4 rectangles; the 5 × 5 square is the only other prime.

3.9. Question. Is there a singleton protoset in 2 dimensions (in other words, a 2dimensional polyomino) which has a prime rectangle that is not strongly prime?

Here we do not know the answer; for every polyomino we have examined, all known primes are strongly prime. However, Klarner has shown that no rectangular polyomino has a prime rectangle that is not strongly prime. For completeness, we sketch the proof.

3.10. Proposition. (Klarner) If P is a rectangular a × b polyomino, then it has only itself as a prime rectangle.

Proof. If a rectangle can be tiled by a × b rectangles, then it can be tiled by a × 1 rectangles, so one side must be a multiple of a. Similarly, one side (perhaps the same side) must be a multiple of b. Also, by considering how the a × b rectangles fit along a side, we see that each side length has the form ax + by for some x, y ≥ 0. Thus, if a rectangle can be tiled by a × b rectangles, we have either

(1) one side is a multiple of a and the other a multiple of b, or

(2) one side is a multiple of both a and b, and the other has the form ax + by for some positive integers x and y.

It is not necessary to allow x = 0 or y = 0 in case (2), since the resulting rectangles also occur in case (1). In case (1), the rectangle can be divided into a × b rectangles, all oriented in the same direction. This division has lines of cleavage except in the trivial case, when the rectangle is itself an a × b rectangle, which is the only prime in case (1). In case (2), the rectangle can then be cut into two rectangles of type (1). This shows that these rectangles can indeed be tiled by an a × b rectangle, and also that they are not prime. □

See [3] for a nice generalization of this result.

4. Unboundedness of number of primes

In this section, we consider protosets that are invariant under rotations and reflections. As described in the previous section, two prime boxes are considered to be the “same” if they have the same dimensions up to permutation. We will show that there is no upper bound to the number of primes in 2 (and therefore higher) dimensions. While this is quite easy to do for general protosets, we will also prove it in the restricted case of singleton protosets.

4.1. Proposition. For any n > 0, there is a protoset with exactly n prime rectangles.

Proof. Take T to be the collection of rectangular polyominoes of dimensions 2^{k} ×2^{2n−2−k} for 0 ≤ k < n. It is immediate that the set of strong primes is exactly the set of rectangles in T . In fact, there are no other prime rectangles for T . If T tiles an a × b rectangle, then its area must be a multiple of 2^{2n−2}. Let 2^{α} and 2^{β} be the largest powers of 2 dividing a and b, respectively. There is no loss of generality to assume that α ≤ β. If α ≥ n − 1, then both a and b are multiples of 2^{n−1}, so the rectangle can be tiled by the 2^{n−1} × 2^{n−1} square, which is in T . If α < n − 1, then β > (2n − 2) − α, so a is a multiple of 2^{α} and b is a multiple of 2^{(2n−2)−α}, whence the rectangle can be tiled by the 2^{α} × 2^{(2n−2)−α} rectangle, which is in T . □

The number of prime rectangles for a protoset is unbounded, even when we only consider singleton protosets. We prove this by extending a result of Walkup [31, Thm. 1].

4.2. Theorem. Let P denote the (8n − 4)-omino . Then P has exactly n primes, specifically, the rectangles 4(n + k) × (8n − 4), for 0 ≤ k < n.

Note that, in the case n = 1, the polyomino becomes the T -tetromino, and the Theorem is exactly Walkup’s result [31, Thm. 1]. We prove Theorem 4.2 in several steps. (In the following, our illustrations will use the case n = 3.)

4.3. Proposition. If P tiles a rectangle, then both sides are multiples of 4.

Proof. In the case n = 1, the statement reduces to Walkup’s result [31, Thm. 1]. So we now suppose that n > 1. Consider the ways that P can fit along the edge of a rectangle:

Figure 4.4. Four ways that P can fit along the edge of a rectangle.

In the first case, the indicated square cannot be filled. In the second and third cases, there is only one way to fill the marked square:

Figure 4.5. Only way to fill the marked square in second and third cases of 4.4.

In the fourth case, there are eight ways to fill the marked square:

Figure 4.6. Eight ways to fill the marked square in the fourth case of 4.4.

Of these eight cases, the first two can indeed occur along an edge of a rectangle. In the next five cases, the marked square cannot be filled. Finally, in the last case, there is only one way to fill the marked square, and this creates a hole that cannot be filled.

Figure 4.7. The eighth case of Figure 4.6 forces a hole.

Thus this case cannot occur. This shows that the tiles along the edge of the boundary must occur in pairs

Figure 4.8. Tiles along the edge must occur in pairs.

each of which covers a multiple of 4 squares along the edge (the second case covers 4n squares). It follows that each edge of a rectangle tiled by P is a multiple of 4. □

4.9. Proposition. If P tiles a rectangle, then one side is a multiple of 8n − 4.

Proof. In the case n = 1, the statement is the same as the previous proposition, so we assume that n > 1. First note that P itself can be tiled by 2n − 1 T -tetrominoes.

Figure 4.10. Decomposition of P into T -tetrominoes.

Therefore, from a tiling of a rectangle by P, we deduce a tiling of the rectangle by T - tetrominoes. Position the rectangle in the coordinate plane with edges parallel to the axes and so that one (and hence all) of its corners has both coordinates even. Define a block to be a 2 × 2 square, each of whose corners has both coordinates even. Walkup [31, Thm. 2] shows that every T -tetromino in the rectangular tiling covers 3 squares from one block and 1 square from an adjacent block. Therefore, in the tiling of the rectangle by P, each tile must be aligned to the blocks as in Figure 4.11 (perhaps rotated and/or reflected).

Figure 4.11. Alignment of P to blocks.

This shows that every “notch” (indicated by ‘N’) must be filled with the “toe” (indicated by ‘T’) of a different copy of P. Now we can deform each P by removing its “toe” and filling in its “notch”, to obtain a tiling of the rectangle by 2 × (4n − 2) rectangles. Consequently, one of the edges of the rectangle must be a multiple of 4n − 2. Since it is also a multiple of 4, this side is a multiple of 8n − 4. □

4.12. Proposition. If P tiles a rectangle, then each side is at least 4n in length.

Proof. Since each side must be a multiple of 4, it suffices to show that P cannot tile a rectangle with a side ≤ 4n − 4. If it tiles a rectangle with height ≤ 4n − 4, then it can only accommodate tiles in the horizontal orientation. Now consider how the upper left corner can be filled.

Figure 4.13. Two ways to fill the upper left corner of a rectangle.

In the first case, the marked square cannot be filled. In the second case, the marked cell cannot be filled by a horizontally oriented tile, a contradiction. Thus the rectangle cannot be tiled. □

4.14. Proposition. P tiles a 4(n + k) × (8n − 4) rectangle for 0 ≤ k < n.

Proof. In fact, it tiles such a rectangle for any k ≥ 0. Figure 4.15 shows half of a symmetric 4n × (8n − 4) rectangle. (This tiling was given by Golomb in [12, Fig. 5].)

Figure 4.15. Half of a 4(n + k) × (8n − 4) rectangle.

Half of a symmetric 4(n + k) × (8n − 4) rectangle is obtained by appending k copies of the 2-tile shape shown with dashed lines. □

Proof of Theorem 4.2. We have shown that each of these rectangles, 4(n+k)×(8n−4), for 0 ≤ k < n, can indeed be tiled by P. First we will show that these are prime rectangles. If an a × b rectangle can be tiled by P, then one side, say b, is a multiple of 8n − 4, and thus at least 8n − 4. Since both sides are at least 4n, the smallest rectangle than can be tiled by P is 4n × (8n − 4). Now we see that a 4(n + k) × (8n − 4) is prime (for 0 ≤ k < n) for the simple reason that it is too small to contain even two rectangles that can be tiled by P. This also shows that these rectangles are strongly prime.

Next we show that any a × b rectangle that can be tiled by P, can be dissected into 4(n + k) × (8n − 4) rectangles for 0 ≤ k < n. As above, one side of the rectangle, say b, is a multiple of 8n − 4. Thus the a × b rectangle can be dissected into a × (8n − 4) rectangles. Moreover, Propositions 4.3 and 4.12 show that a is a multiple of 4 and a ≥ 4n, so we may write a = 4(nt + k), where 0 ≤ k < n, and t ≥ 1. Now we can dissect the a×(8n−4) rectangle into t−1 rectangles of dimensions 4n×(8n−4), and a single rectangle of dimensions 4(n + k) × (8n − 4). □

5. Primes of some small polyominoes

In this section, we determine the prime rectangles of several small polyominoes. For each protoset (which will always be a singleton in this section), there are two tasks. The first is to show that each alleged prime box can indeed be tiled by the protoset. This is usually done by exhibiting a tiling, although it may be conceivable to prove the existence of a tiling without explicitly giving it. For reasons of space, we will do even less here, namely, will we simply assert that the rectangles can be tiled. (All tilings are available from the author on request.) For a given rectangle, it is always a finite computation to find a tiling (or show that one does not exist).

The second task is to show that certain other boxes cannot be tiled by the protoset. This task accomplishes two things; it shows that there are no further primes, and it shows that each purported prime is indeed prime, because in any splitting into two smaller boxes, one of the smaller boxes can’t be tiled. It is possible for a tiling of a box to be known, without knowing if the box is prime. In fact, this has happened historically, as in Example 5.1 below, where the 9×15 rectangle was once believed to be prime. Also, in Examples 5.2 and 5.13 below, some tilings were found by non-exhaustive methods, and were considered to be “possible primes”. For a given box, it is a finite computation to show that it can’t be tiled (or to find a tiling). However, there may be instances where it is required to show that an infinite collection of boxes cannot be tiled. In some cases, this can be accomplished by a finite computation, but in other cases, it may require a more theoretical result.

Finally, after the set of primes has been determined, one wants to know which of the primes are strongly prime. This is always a finite computation, because it amounts to determining which primes can be tiled by the remaining prime boxes. However, this is rather unsatisfactory, and we’d like to see a better method.

The examples below give a good illustration of the variety of methods involved.

5.1. Example. Let L_{5} be the pentomino . L_{5} tiles a 2 × 5 rectangle (easy) and a 7 × 15 rectangle. See [13, Fig. 164] [25, Fig. 11] [26, Fig. 9] for constructions of the latter. These two rectangles are its only primes. In particular, the 9 × 15 rectangle of [18, 22] is not prime; it can be constructed as (2 + 7) × 15, the 2 × 15 component itself being constructed as 2 × (5 + 5 + 5).

To show that L_{5} has no further primes, one can verify that it does not tile any rectangle of width 3 and cannot tile any 5 × (2n + 1) rectangle. These are proven in slightly more generality in [26, Lemmas 3.1 and 3.2]. It also follows from these that the 7 × 15 rectangle is indeed prime. Now, using the fact that 2 × 5 and 7 × 15 are the only primes, it follows that 7×15 is strongly prime for the simple reason that it cannot be tiled by 2×5 rectangles.

5.2. Example. Let Y_{5} be the pentomino , which has already been considered by numerous authors. Y_{5} has 40 prime rectangles, which are

5 × 10,

9 × 20, 9 × 30, 9 × 45, 9 × 55,

10 × 14, 10 × 16, 10 × 23, 10 × 27,

11 × 20, 11 × 30, 11 × 35, 11 × 45,

12 × 50, 12 × 55, 12 × 60, 12 × 65, 12 × 70, 12 × 75, 12 × 80, 12 × 85, 12 × 90, 12 × 95, 13 × 20, 13 × 30, 13 × 35, 13 × 45, 14 × 15, 15 × 15, 15 × 16, 15 × 17, 15 × 19, 15 × 21, 15 × 22, 15 × 23, 17 × 20, 17 × 25, 18 × 25, 18 × 35, and 22 × 25.

Klarner [17, Fig. 2] originally gave the 5 × 10 rectangle. Klarner and Göbel [22] list 10 × 16, 15 × 16, 15 × 22 and 22 × 25 and several other potential primes, which turn out not to be prime. Constructions of these rectangles are shown in [2]. Klarner [19] later gives 9 × 20, 9 × 30, 10 × 14, 11 × 20, 11 × 30, 13 × 20, 13 × 30 and 14 × 15 (without tilings). Haselgrove [15] gives the 15 × 15 square; she also shows that 9 × 25 and 13 × 15 cannot be tiled by Y_{5}. Chvátal, Klarner and Knuth [4, Problem 7] give the 12×80 rectangle (without its tiling). Bitner [1] gives tilings of 12 × (50 + 5k), which are prime for k = 0, 1, 2, …, 9. He also shows that 12 × 5n cannot be tiled by Y_{5}, for n < 10. Scherer [29] gives tilings of the 9 × 20, 9 × 30, 10 × 14, 11 × 20 and 14 × 15 rectangles (these had been listed earlier by Klarner [19]) and several other rectangles that turn out not to be prime.

To show that these rectangles are all prime, and to show that the list of primes is complete, we must demonstrate that certain other rectangles cannot be tiled by Y_{5}. Although we will not work through the computations, we will describe what is involved. We must show that Y_{5} cannot tile any rectangle of width 6, 7 or 8. That it does not tile a rectangle of width 7 is easy; it cannot even tile the first row. Widths 6 and 8 are slightly more difficult; in both cases, Y_{5} tiles an infinite half strip of that width. However, a calculation based upon [26, Prop. 2.1] shows that it cannot tile any rectangle of width 6 or 8. It also follows from these calculations that Y_{5} cannot tile any rectangle of width 1, 2, 3 or 4, although that is easy to show directly. We must also show that Y_{5} cannot tile any rectangle of dimensions 5 × k, where k is not a multiple of 10. This type of calculation also proceeds as described in [26, Prop. 2.1]. Lastly, we must show that several individual rectangles cannot be tiled by Y_{5}. These are 9 × 25, 9 × 35, 10 × 18, 10 × 22, 11 × 15, 11 × 25, 12 × 25, 12 × 30, 12 × 35, 12 × 40, 12 × 45, 13 × 15, 13 × 25 and 15 × 18. Each of these is a straightforward but tedious finite computation. It follows from the impossibility of tiling these rectangles (and also the existence of some tilings) that certain others cannot be tiled by Y_{5}, specifically, 9 × 10, 9 × 15, 10 × 11, 10 × 12, 10 × 13, 10 × 17, 12 × 15 and 12 × 20. (For example, if 9 × 10 could be tiled, then so could 10 × 18, so it not necessary to check that the former can’t be tiled. Similarly, if 10 × 17 could be tiled, then so could 10 × 22, since 10 × 5 can be tiled.)

We will show that these prime rectangles are all strongly prime. We do not have a particularly nice way to do this; perhaps some reader will find a more systematic method.

5.3. Proposition. Suppose a rectangle is decomposed into (n > 1) smaller rectangles, in such a way that does not have a line of cleavage. Assume for convenience that the rectangle is oriented with its sides parallel to the coordinate axes. Then there is a vertical line that intersects the interior of at least 3 rectangles in the decomposition. In particular, the height of the rectangle is the sum of (at least) 3 heights of rectangles in the decomposition.

Proof. Inside the large rectangle, draw all horizontal edges between rectangles of the decomposition. If there is a horizontal gap between these internal edges, as in Figure 5.4, then there is a rectangle that spans the height of the big rectangle.

Figure 5.4. Horizontal gap between horizontal edges.

One of its vertical edges is a line of cleavage of the decomposition. This contradiction shows that there cannot be any horizontal gaps.

Several possibilities remain. If there is only one horizontal edge, then it must span the width of the rectangle, and thus is a line of cleavage, a contradiction. Thus there are at least two horizontal edges. If there is one that overhangs another, as in Figure 5.5, then a vertical line that intersects both also intersects (at least) 3 rectangles of the decomposition.

Figure 5.5. Vertical line intersects (at least) 3 rectangles.

Finally, if no horizontal edge overhangs any other, then the rightmost endpoint of one horizontal edge must lie directly above or below the leftmost endpoint of another horizontal edge, as in Figure 5.6.

Figure 5.6. Vertical line is a line of cleavage.

But then the vertical line through these endpoints is a line of cleavage, since it does not intersect any other horizontal edges. This proves the proposition. □

Since the smallest edge of a rectangle that can be tiled by Y_{5} is 5, Proposition 5.3 shows that any prime rectangle that is not strongly prime, must have smallest dimension at least 15. Moreover, if the width of such a rectangle is 15, its decomposition into primes must have three 5 × 10 rectangles situated as in Figure 5.7. But in that case, the tiling can be rearranged to give a tiling with a line of cleavage.

Figure 5.7. Rearrangement of a tiling of width 15 rectangle.

This shows that the rectangle is not prime, a contradiction.

Neither 17 nor 18 can be written as a sum of three (or more) sides of primes. Therefore, the 17 × 20, 17 × 25, 18 × 25 and 18 × 35 rectangles are all strongly prime.

The only way to express 22 as a sum of three (or more) sides of primes is 5 + 5 + 12. However, even the shortest prime of width 12 (12 × 50) is too long to occur in a decomposition of 22 × 25. Therefore this prime is also strongly prime.

5.8. Example. Let G_{6} be the hexomino . The primes of G_{6} are 9 × 12, 9 × 20, 9 × 28, 12 × 13, 12 × 14, 12 × 17, 12 × 19, 12 × 21, 12 × 24, 12 × 25, 12 × 29, 15 × 28, 15 × 32, 15 × 36, 15 × 40, 15 × 44, 15 × 48, 15 × 52, 16 × 18, 16 × 27, 16 × 30, 16 × 33, 16 × 39, 16 × 42, 20 × 21 and 20 × 24.

The 9 × 12 rectangle was originally given by Klarner [17, Fig. 3]. We leave to the reader the task of finding tilings of these rectangles. To prove that the list is complete, we first need a theoretical result.

5.9. Theorem. If G_{6} tiles a rectangle, then one side of the rectangle is a multiple of 4.

Proof. See [28, Thm. 5.4]. □

To finish the proof of completeness, one must also show that G_{6} cannot tile any rectangle of width 6, 7, 8, 10 or 11, and that it cannot tile rectangles of sizes 9 × 16, 12 × 12, 12 × 20, 15 × 16, 15 × 20, 15 × 24, 16 × 21 and 16 × 24. These are also left to the reader. All of the primes are strongly prime; this follows easily from Proposition 5.3.

5.10. Example. Let D_{6} be the hexomino . The primes of D_{6} are 4 × 6 and 5 × 12. To show that this list is complete, we need two theoretical results.

5.11. Proposition. If D_{6} tiles a rectangle, then one side is a multiple of 6.

Proof. If a rectangle can be tiled by D_{6}, then its area must be a multiple of 6. Therefore, it suffices to consider rectangles with dimensions (6m+3)×(6n+2) and (6m+3)×(6n+4). Let c_{ij} denote the unit square with lower left corner at the point (i, j), where i, j ∈ ℤ. Number the squares of the infinite grid by

c_{ij} ↦ \{ \begin{matrix}1 & if 3 divides i and i + j is even, \\ −1 & if 3 divides i and i + j is odd, \\ 0 & otherwise (i.e. 3 does not divide i). \end{matrix}

It is easy to show that every possible placement of a D_{6} tile covers a total of 0. However, (6m + 3) × (6n + 2) and (6m + 3) × (6n + 4) rectangles can be placed so they cover a non-zero total, which shows that they cannot be tiled by D_{6}. □

A more difficult result is the following, which is stated without proof in [28, Thm. 7.1].

5.12. Theorem. If D_{6} tiles a rectangle, then one side is a multiple of 4.

Proof. We use the boundary word method, in particular, a representation proof, as described in [28]. It suffices to show that D_{6} cannot tile any rectangle with dimensions (12m + 6) × (12n + 6). Consider the permutations

x = (1, 5, 28, 23, 26, 16, 11, 15, 14, 24, 2, 12)(3, 19)(4, 32)
(6, 31, 18, 21, 7, 20)(8, 9, 13, 27, 22, 10)(17, 29, 25, 30),
y = (1, 5, 13, 27, 17, 29, 18, 21, 28, 23, 3, 19)(2, 12, 22, 10)
(4, 11, 15, 7, 20, 25, 30, 8, 9, 14, 24, 32)(6, 31, 26, 16)

of S_{32}. One easily checks that the boundary word of each possible orientation of D_{6} is the identity element of S_{32}, that is x^{4}yx^{−1}yx^{−2}y^{−1}x^{−1}y^{−1} = y^{4}x^{−1}y^{−1}x^{−1}y^{−2}xy^{−1}x = x^{−4}y^{−1}xy^{−1}x^{2}yxy = y^{−4}xyxy^{2}x^{−1}yx^{−1} = 1. However, the boundary word of a (12m + 6) × (12n + 6) rectangle is non-trivial, i.e. x^{12m+6}y^{12n+6}x^{−(12m+6)}y^{−(12n+6)} ≠ 1. (For this latter assertion, it is useful to note that x^{12} = y^{12} = 1.) □

To show that 4 × 6 and 5 × 12 are the only primes, it remains to show that D_{6} cannot tile any rectangle of width 2, 3 or 7. This is easy, as it cannot even tile the first row of such a rectangle. Moreover, it is now easy to show that both primes are strong primes.

5.13. Example. Let L_{6} be the hexomino . The primes of L_{6} are 2 × 6, 7 × 12, 8 × 15, 9 × 14, 9 × 16, 9 × 34, 10 × 15, and 11 × 18.

The 9 × 14 rectangle was given in [25, Fig. 13] and [26, Fig. 11]. The 2 × 6, 7 × 12 and 9 × 16 rectangles were given in [9], along with some larger rectangles that are not prime.

To verify completeness of this list, one must show that L_{6} cannot tile rectangle of width 3 or 5, cannot tile any rectangle of the form 4 × (6n + 3), 6 × (2n + 1) or 7 × (12n + 6), and cannot tile rectangles of sizes 9 × 18, 9 × 20 and 9 × 22. The eight prime rectangles are all strongly prime, but we leave the details to the reader.

References

1. James Bitner, Tiling 5n × 12 Rectangles with Y -pentominoes, Journal of Recreational Mathematics 7 (1974), no. 4, 276–278. MR 55 #149

2. C.J. Bouwkamp and D.A. Klarner, Packing a Box with Y -pentacubes, Journal of Recreational Mathematics 3 (1970), no. 1, 10–26.

3. Richard J. Bower and T.S. Michael, When can you tile a box with translates of two given rectangular bricks?, The Electronic Journal of Combinatorics 11 (2004), no. 1, N7, 9 pages,

http://www.combinatorics.org/Volume 11/Abstracts/v11i1n7.html. MR 2005a:05062

4. V. Chvátal, D.A. Klarner and D.E. Knuth, Selected Combinatorial Research Problems, Technical Report STAN-CS-72-292, Stanford University (June 1972), 31 pages (unpublished)

http://www-db.stanford.edu/TR/CS-TR-72-292.html.

5. Andrew L. Clarke, Packing Boxes with Congruent Polycubes, Journal of Recreational Mathematics 10 (1977–78), no. 3, 177–182.

6. Karl A. Dahlke, The Y -hexomino has order 92, Journal of Combinatorial Theory, Series A 51 (1989), no. 1, 125–126. MR 90b:05041

7. Karl A. Dahlke, A Heptomino of Order 76, Journal of Combinatorial Theory, Series A 51 (1989), no. 1, 127–128. MR 90b:05042 Erratum, Journal of Combinatorial Theory, Series A 52 (1990), no. 2, 321. MR 90j:05053

8. Karl A. Dahlke, Solomon W. Golomb and Herbert Taylor, An Octomino of High Order, Journal of Combinatorial Theory, Series A 70 (1995), no. 1, 157–158. MR 96b:05049

9. Raymond R. Fletcher III, Tiling Rectangles with Symmetric Hexagonal Polyominoes, Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, 1996, Congressus Numerantium 122 (1996), 3–29. MR 99a:05026

10. S.W. Golomb, Covering a Rectangle with L-tetrominoes, Problem E1543, American Mathematical Monthly 69 (1962), 920. Solution by D.A. Klarner, American Mathematical Monthly 70 (1963), 760–761.

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

12. Solomon W. Golomb, Polyominoes Which Tile Rectangles, Journal of Combinatorial Theory, Series A 51 (1989), no. 1, 117–124. MR 90b:05040

13. Solomon W. Golomb, Polyominoes, Second Edition, second printing, and first paperback printing, Princeton University Press, Princeton, NJ, 1996.

14. Solomon W. Golomb, Tiling Rectangles with Polyominoes, The Mathematical Intelligencer 18 (1996), no. 2, 38–47. MR 97f:05047

15. Jenifer Haselgrove, Packing a Square with Y -pentominoes, Journal of Recreational Mathematics 7 (1974), no. 3, 229.

16. Robert Hochberg and Michael Reid, Tiling with Notched Cubes, Discrete Mathematics 214 (2000), no. 1–3, 255–261. MR 2001a:52022

17. David A. Klarner, Some Results Concerning Polyominoes, Fibonacci Quarterly 3 (1965), 9–20. MR 32 #4028

18. David A. Klarner, Packing a Rectangle with Congruent N-ominoes, Journal of Combinatorial Theory 7 (1969), 107–115. MR 40 #1894

19. David A. Klarner, Letter to the Editor, Journal of Recreational Mathematics 3 (1970), no. 4, 258.

20. David A. Klarner, A Finite Basis Theorem Revisited, Technical Report STAN-CS-73-338, Stanford University (February 1973), 10 pages (unpublished) http://www-db.stanford.edu/TR/CS-TR-73-

    338.html.

21. D. Klarner, My life among the polyominoes, Nieuw Archief voor Wiskunde, Derde Serie 29 (1981), no. 2, 156–177. MR 83e:05038

22. D.A. Klarner and F. Göbel, Packing boxes with congruent figures, Indagationes Mathematicae 31 (1969), 465–472. MR 40 #6362

23. Miklós Laczkovich, Tiling with T -tetrominoes, Problem 1263, Mathematics Magazine 60 (1987), no. 2, 114. Solution by Jerrold W. Grossman, Mathematics Magazine 61 (1988), no. 2, 119–120.

24. T.W. Marlow, Grid Dissections, Chessics 23 (1985), 78–79.

25. William Rex Marshall, Packing Rectangles with Congruent Polyominoes, Journal of Combinatorial Theory, Series A 77 (1997), no. 2, 181–192. MR 98e:05026

26. Michael Reid, Tiling Rectangles and Half Strips with Congruent Polyominoes, Journal of Combinatorial Theory, Series A 80 (1997), no. 1, 106–123. MR 98i:05046

27. Michael Reid, Tiling a Square with Eight Congruent Polyominoes, Journal of Combinatorial Theory, Series A 83 (1998), no. 1, 158.

28. Michael Reid, Tile Homotopy Groups, L’Enseignement Mathématique 49 (2003), no. 1–2, 123–155. MR 2004f:52020

29. Karl Scherer, Some New Results on Y -pentominoes, Journal of Recreational Mathematics 12 (1979– 80), no. 3, 201–204. MR 81g:05054

30. Robert Spira, Impossibility of Covering a Rectangle with L-Hexominoes, Problem E1983, American Mathematical Monthly 74 (1967), no. 4, 439. Solution by Dennis Gannon, American Mathematical Monthly 75 (1968), no. 7, 785–786.

31. D.W. Walkup, Covering a Rectangle with T -tetrominoes, American Mathematical Monthly 72 (1965), 986–988. MR 32 #1582

32. Ingo Wrede, Rechteckzerlegungen mit kleinen polyominos (1990), Unpublished thesis, Technische Universität Braunschweig.

Michael Reid Department of Mathematics University of Central Florida Orlando, FL 32816 U.S.A.

reid@cflmath.com