# tiling a rectangle with squares: how unique are the minimal solutions?

This is a follow-up of my recent thread about tiling a $m\times n$ rectangle with squares:

I'm wondering to what extent a minimal tiling is essentially unique, that is, up to reflections of the whole rectangle or of (tiled) rectangles contained in it. I guess this definition is tantamount to saying that the collection of the square sides is unique.

First, let me suggest a more suitable definition of reducibility than in the other thread:

We'll call a rectangle (or a minimal tiling of it) reducible if it can be split into two (tiled) rectangles.

By playing around a bit with irreducible tilings, I have the impression that there are always some of the squares that form a smaller rectangle, but that apart from reflections inside of those smaller rectangle(s), such a tiling is unique.

Are all irreducible tilings essentially unique?

Do all minimal tilings contain a (tiled) rectangle?

The smallest irreducible rectangles are

$(13,11)\quad (17,16)\quad (19,16)\quad (19,17)\quad (19,18)\quad (20,17)\quad (21,19)\quad (25,23)\quad$ $(26,22)\quad (27,23)\quad (27,25)\quad (28,27)\quad (29,25)\quad (29,27)\quad (31,23)\quad (31,25)\quad$ $(31,26)\quad (31,27)\quad (31,28)\quad (31,29)\quad (31,30)\quad (32,27)\quad (32,29)\quad (32,31)\quad$ $(33,26)\quad (33,28)\quad (34,25)\quad (34,32)\quad (35,31)\quad (35,34)\quad (36,31)\quad (37,29)$.

Now looking at reducible rectangles:

Note that a reducible rectangle can be splittable horizontally or vertically, often in several ways, and sometimes both at a time. For example, $f(15,8)=f(7,8)+f(8,8)=f(15,3)+f(15,5)$. So those tilings are far from unique. But now:

We'll call a rectangle (or a minimal tiling of it) coprime-reducible if the rectangle can be split into two (tiled) rectangles that have coprime sides each.

For a given $m\le 85$, the majority (in average about 90%) of the $m\times n$ rectangles with $n\lt m$ are reducible. But in the whole range, there is no rectangle that is coprime-reducible...

Is it possible to show that coprime-reducible rectangles don't exist?

EDIT: Note that as the values $f(m,n)$ for given m and for coprime $n$ between $m/2$ and $2m$ are seemingly very close to each other, the value of a coprime-reducible one in this range would have to be about the double of the others. This sort of rules out their existence heuristically.

-
I think it is feasible to do a near-brute force search on minimal square tilings for rectangles of small dimensions. Knowing that a tiling of O(log(pq)) exists for a p by q rectangle means a branch and bound algorithm can scan the possibilities pretty quickly to find all minimal tilings. Using theory to make good choices for p and q should allow a nice exploration, perhaps even for p into the thousands. Gerhard "Ask Me About System Design" Paseman, 2012.12.17 –  Gerhard Paseman Dec 17 '12 at 21:49

We have $f(34,29)=9$, and there are at least two essential different minimal tilings: