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:
- We can select from the set 3 rectangles such that $\gcd(p_i, p_j) = \gcd(q_i, q_j)$ for $i \neq j$.
- We can partition the set as in Theorem 5.
- 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 Theorem 5. 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).
