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

2012-12-17T20:09:25Z

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.

Answer by Wolfgang for tiling a rectangle with squares: how unique are the minimal solutions?

2012-12-21T15:20:36Z

I just found that the answer to the first question about uniqueness is negative.

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

an irreducible one (squares of sides 19,15,14,10,10 clockwise and 4x1 in the middle)

a reducible one (squares of sides 17,17,12,12,6,4,4,4 clockwise and another one of side 6 in the middle)

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

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

Answer by Wolfgang for tiling a rectangle with squares: how unique are the minimal solutions?