What rectangles can a set of rectangles tile?

Question

(I asked this question first on math.stackexchange, but did not get any responses so I thought I would try here.)

If we have a set of $p_i \times q_i$ rectangles ($p_i, q_i \in \mathbf{N}$), which $m \times n$ rectangles can be tiled with copies from the set? (No rotation allowed.)

I am particularly interested in the algorithm that realizes Theorem 4 below.

What I know so far:

Theorem 0

• We need $mn = \sum p_iq_ic_i$ for some $c_i \geq 0$.
• Considering how rectangles form the border, we need at least $m = \sum a_ip_i$ and $n = \sum b_iq_i$ for some $a_i \geq 0$ and $b_i \geq 0$.

Theorem 1 For two rectangles with $\gcd(p_1, p_2) = \gcd(q_1, q_2) = 1$, a tiling exists if and only if one of the following holds [2]:

1. $p_1 \mid m$ and $q_1 \mid n$
2. $p_2 \mid m$ and $q_2 \mid n$
3. $p_1q_1 \mid m$ and $ap_2 + bq_2 = n$ for some integers $a, b$
4. $p_2q_2 \mid n$ and $ap_1 + bq_1 = n$ for some integers $a, b$.

Theorem 2 For any number of rectangles, if any side of all rectangles share a common factor, then they can only tile a larger rectangle if one side has the same common factor [3].

(Between these first theorems dealing with sets of two rectangles is easy.)

Theorem 3 A set of three or more rectangles satisfying $\gcd(p_i, p_j) = \gcd(q_i, q_j) = 1$ , for $i \neq j$ there exist some $C$ such that the set will tile any rectangle with $m, n > C$ [4, 5].

How to find such a $C$ is given in [3]. Unfortunately, this $C$ can be quite large, and is not generally tight (there is a smaller $C$ that also works). So there is a whole bunch of rectangles for which it says nothing.

In addition, it says nothing about rectangles that do not satisfy the conditions. For example, it is hard to know much about which rectangles can be tiled by a set with a $6\times 6, 10\times 10$ and $15 \times 15$ rectangle. In this example, pairs of squares share a common factor, but we cannot reduce the tiling problem because there is not a common factor among all tiles.

Theorem 4 For every finite set of rectangular tiles, the tileability problem of an $m\times n$ rectangle can be decided in $O(\log mn)$ time.

This result is mentioned in [4] (and some others), but unfortunately it references a mysterious unpublished manuscript, and there is no details available; no proof, and no hint at what the algorithm might be.

(The unpublished manuscript is Tiling rectangles with rectangles by Lam, Miller and Pak. I also saw a reference to "Packing boxes with boxes", also unpublished, by the same authors, which I suspect is the same. I could find neither one :-/)

---

I also wrote a computer program to investigate some examples. My own optimized-but-still-exponential-time algorithm starts becoming unpractical around for $m, n >80$ with a set of only three tiles, so I have not been able to get much insight from it.

---

[2] Bower, Richard J.; Michael, T.S., When can you tile a box with translates of two given rectangular bricks?, Electron. J. Comb. 11, No. 1, Research paper N7, 9 p. (2004). ZBL1053.05027.

[3] de Bruijn, N.G., Filling boxes with bricks, Am. Math. Mon. 76, 37-40 (1969). ZBL0174.25501.

[4] Labrousse, D.; Ramírez Alfonsín, J.L., A tiling problem and the Frobenius number, Chudnovsky, David (ed.) et al., Additive number theory. Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson. New York, NY: Springer (ISBN 978-0-387-37029-3/hbk; 978-0-387-68361-4/ebook). 203-220 (2010). ZBL1248.11022.

[5] Pak, Igor; Yang, Jed, Tiling simply connected regions with rectangles, J. Comb. Theory, Ser. A 120, No. 7, 1804-1816 (2013). ZBL1314.05034.

Answer 1

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

Answer 2

This is a very late reply, but Igor Pak, one of the authors of your Theorem 4, recently taught a class where he outlined the proof, and I was a student in that class. You can find the proof in my notes here as Corollary 5.3. (My notes have not be thoroughly proofread so there may be errors, let me know if you catch any.)

To sketch the argument, the other answer by Aaron Meyerowitz is correct to refer to Reid's paper on Klarner systems and polyominoes as the main reference. The "prime boxes" mentioned in the paper always lead to eventual periodicity in whether or not $m \times n$ can be tiled. If you know the periods, you can memorize the non-periodic region and use division to test larger rectangles.

Answer 3

This is not a complete answer, but another piece of the puzzle. This all follows from @Aaron Meyerowitz's idea of extending the range of Theorem 3 by building rectangles from your tile set that satisfy the conditions of Theorem 3, so you can prove the set will tile any sufficiently large rectangle.

Theorem 5 (The numbering is just to keep track; it really is a more general version of Theorem 2.)

If we can partition a set of rectangles into two partitions, where the first has a common factor $r$ among their widths, and the second has a common factor $s$ among their heights, then any tileable rectangle either has width with factor $r$, or height with factor $s$.

The proof follows easy from the tiling by rectangles of integer side theorem (Theorem 2 as stated earlier also follows from this) which states that any rectangle which is tileable by rectangles with at least one side an integer, has at least one side an integer. (There are 14 proofs of this fact in [1].)

To prove Theorem 5, convert a tiling problem to a new one with widths and heights divided by $r$ and $s$ respectively. In the new problem, partition 1 rectangles have integer widths, and partition 2 rectangles have integer heights. Together, they can only tile a rectangle with either integer width or integer height. Translating it back to the original problem, we see the original tiles can only tile a rectangle whose width has factor $r$ and height has factor $s$.

---

Applying this to my example problem using the tile set $6\times 6$, $10 \times 10$, and $15 \times 15$, we can form partitions several ways; one way is $\{ 6\times 6, 10\times 10\}$ and $\{15 \times 15\}$, giving us tileable rectangles have either width with a factor of 2, or height with a factor of 16. $r = 2, s = 15$. Other ways of partitioning gives us other conditions; there are 6 in total (here, $m$ and $n$ are the width and height of the rectangle we wish to tile):

1. $2\mid m$ or $15\mid n$
2. $3\mid m$ or $10\mid n$
3. $5\mid m$ or $6\mid n$
4. $15\mid m$ or $2\mid n$
5. $10\mid m$ or $3\mid n$
6. $6\mid m$ or $5\mid n$

Now a tileable rectangle must satisfy all 6 conditions. So, for example, if it has a width $m = 6$, then it must, to comply with conditions 3, 4 and 5, a height with a factor of $6$. It is also not hard to see that a tileable rectangle must have one side with factor 6, 10, or 15; and when one side is prime the other has factor of 30 (which corresponds with my observations from my experiments).

---

Looking a bit more broadly, for all sets of three rectangles, we have one of these cases:

1. $\gcd(p_i, p_j) = \gcd(q_i, q_j) = 1$ for $i \neq j$ (so we can tile any rectangle "sufficiently large").
2. Each rectangle has one side with a factor $r$, so we can only tile rectangles with one side with a factor $r$.
3. We can partition the rectangle as in Theorem 5 (and so we can only tile rectangles which either has width with factor $r$ and height with factor $s$).

When we have the last case, we cannot build 3 rectangles from our set such that no pairs have common factors among either their widths or heights, since for every three rectangles 2 share a factor along either width or height. So we can never apply Theorem 3.

(However, we can say slightly more. I have not worked out the details of this exactly, but sometimes you can tile every rectangle with width of a certain factor for sufficiently large heights.)

---

For larger sets of rectangles, things become interesting again. There are 4 cases, the three above and an additional case where none of the others apply. Currently, my suspicion is that when we are in this case, then we can build bigger rectangles that satisfy the conditions of Theorem 3. I have managed to do this with a handful of examples, but have not yet looked at a general proof. [I will update this answer if I find anything.]

---

Update This is the situation for tile sets with 4 or more rectangles:

Theorem 6 For a set of 4 or more rectangles, one of the following is true:

1. We can select from the set 3 rectangles such that $\gcd(p_i, p_j) = \gcd(q_i, q_j)$ for $i \neq j$.
2. We can partition the set as in Theorem 5.
3. We select four rectangles that can tile any sufficiently large rectangle.

For case 1 and 3 we can therefor tile any sufficiently large rectangle, and for case 2 at least one of the sides must have a certain factor (and therefor there are some rectangles, however large, we cannot tile).

The proof of this is a bit tedious. We can use induction on the number of rectangles in the tile set. The base case for $n = 3$ is is discussed above. The rest is just confirming that adding a rectangle to a set that satisfy one of the three cases will lead to a set that will also follow one of these three cases. (It's tedious because the new rectangle can share factors in various ways with the existing set).

The only tricky bit is dealing with case 3. The basic idea is, supposing the other cases don't hold, that there are four rectangles $R_1, \cdots, R_4$, that satisfy:

• $\gcd(p_1, p_2) = r > 1$
• $\gcd(p_3, p_4) = s > 1$
• $\gcd(q_i, q_j) = 1$, for $i, j = 1, 2, 3, 4$, $i \neq j$
• $\gcd(r, s) = 1$

(OR, symmetrically, all $q$s and $p$s swapped.) $\DeclareMathOperator{\lcm}{lcm}$ Now let $u = \lcm(p_1, p_2)$ and $v = \lcm(p_3, p_4)$. We can then build these rectangles:

• $u \times q_1$
• $u \times q_2$
• $v \times q_3$
• $v \times q_4$

Form the first two, we can then build $u \times x$ for large enough $x$, and from the second two $v \times y$ for large enough $y$. Furthermore, if $x = y$, since $\gcd(u, v) = 1$, from these two rectangles we can build $z \times x$ rectangles for any large enough $z$.

---

This completes the "for sufficiently large" and "has a factor" type characterization; of course there is still what happens if the rectangles we wish to tile is not sufficiently large, or they do have the required factors (since these does not guarantee a tiling exists).

---

[1] Wagon, Stan, Fourteen proofs of a result about tiling a rectangle, Am. Math. Mon. 94, 601-617 (1987). ZBL0691.05011.