(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_i, p_j) = \gcd(q_i, q_j) = 1$ for $i \neq j$, 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 rectangles satisfying $\gcd(p_1, p_2) = \gcd(q_1, q_2) = 1$, 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.