What is known about tiling a rectangle in an irreducible way by smaller rectangles?

Question

Given two naturals $s<t$. Is there always a square (or at least a bigger rectangle) that can be tiled with $s\times t$ rectangles in an irreducible way (i.e. any grid line splitting it cuts at least one of the $s\times t$ rectangles of the tiling)?

E.g. for $(s,t)=(1,2)$, it is well known that a $\underline{6\times 6}$ square has no irreducible tiling, but a $\underline{8\times 8}$ one does, and so do in fact all other rectangles with even area and sides bigger than $5\times 6$. I think I have seen a similar statement for $(s,t)=(2,3)$ somewhere, but can’t seem to find the article anymore. So:

What is known about the existence of such a rectangle for given $(s,t)$, and maybe even about lower/upper bounds for the sides of a minimal one?

Answer 1

The answer is YES, and it's a rather easy claim to prove. I will assume that $k:=gcd(s,t)=1$ since otherwise we can divide everything by $k$. First, note that you can tile square $Q=[st \times st]$ in two different ways. Now take $nQ = [nst \times nst]$ and a standard "brick tiling" of $nQ$, with $stn^2$ copies of translates of $[s\times t]$. There are $\theta(n)$ lines to be "blocked". For every copy of $Q$ inside $nQ$, we can "flip" from one tiling to another. This will block some constantly many lines. Observe that if we flip one $Q$, we cannot flip any neighbors at constant radius. But since the area of $nQ$ grows quadratically and the number of lines linearly, these are plenty of other potential flips to make when $n$ is large enough.

This is not a proof, more like an explanation. Essentially, a random tiling of $nQ$ will work w.h.p. For the real proof, one would need to give an explicit construction of positions of $Q$ which need to be flipped. These can be constructed by starting in the lower left corner $(0,0)$ and making repeated shifts by $(1,\ell)$ for sufficiently large $\ell$; here we take coordinates mod $stn$. E.g. $\ell=2(s+t)$ will work. The details are straightforward.

P.S. Let me mention also a cute paper by Chung, Gilbert, Graham, Shearer and van Lint on such "irreducible" tilings, and our paper which shows how complicated tilings with rectangles can get.

Answer 2

Here's an easy proof in the case that $(h, \ell)=(1, 2k)$, with an explicit bound.

Claim. For $(h, \ell)=(1,2k)$, there is an irreducible tiling of a $8k \times 8k$ square.

Proof. Tile the $(k,2k)$-rectangle horizontally, and the $(2k,k)$-rectangle vertically. Regarding these as $(1,2)$-rectangles and $(2,1)$-rectangles, we then use an irreducible tiling of the $8k \times 8k$ square $S$. Call a line bad if it separates $S$ into two tiled rectangles. Let $b$ be a bad line. By irreducibility and symmetry we may assume that $b$ passes through the interior of some $(k,2k)$-rectangle $R$. In particular, $b$ is horizontal and so $b$ does not meet any vertical rectangle $R$ (including on the boundary of $R$). Therefore, $b$ is actually a bad line for the induced $(1,2)$-tiling, which is a contradiction.

Without loss of generality we may assume that $gcd(h, \ell)=1$, and I think the above proof should work if one of $h$ or $\ell$ is even.