Prove the ratio of the length and width of the rectangle is rational.

The problem is equivlaent to the following statement:

A rectangle with sides 1 and $x$, where $x$ is irrational, cannot be "tiled" by finitely many squares.

It turns out this is a well known problem and the the proof is copied below from the following source:

http://circuit.ucsd.edu/~yhk/ece269-win18/pdfs/matousek.pdf

However I could not find the name of the author.

enter image description here

enter image description here


Indeed, the ratio between length and width must be rational, even if we don't require the squares to be of different size. The first proof of this was given by Max Dehn [Deh03]. A short and elegant proof appears in Proofs from THE BOOK (see [AZ14, Chapter 28]). Furthermore, I worked out a very similar proof in [Dob16], which I intended to be accessible to undergraduate mathematics students at my university. (It is unclear to me who first conceived of this proof; the original proof of Dehn seems to be much more involved.)

A short sketch of the ideas behind this proof: let $s_1,\ldots,s_n$ denote the lengths of the sides of the squares in the tiling, and let $w,h$ denote the width and height of the large rectangle. Furthermore, let $\mathscr{L} \subseteq \mathbb{R}$ be the $\mathbb{Q}$-vector subspace of $\mathbb{R}$ spanned by $s_1,\ldots,s_n$. (In other words: $\mathscr{L}$ is the set of all rational linear combinations of $s_1,\ldots,s_n$.)

The first important observation is this: for an arbitrary $\mathbb{Q}$-vector space $V$ and an arbitrary $\mathbb{Q}$-bilinear map $f : \mathscr{L} \times \mathscr{L} \to V$, one has $$ f(w,h) = \sum_{i=1}^n f(s_i,s_i).\tag{1} $$ Intuitively, this is generalising the idea that the area of the original rectangle is the sum of the areas of the squares in the tiling. Indeed, the usual area function occurs as a special case, if we choose $V = \mathbb{R}$ and $f(x,y) = x\cdot y$. (For a more detailed proof of (1), see [Dob16, Lemma 3.2].)

Now, if $\varphi : \mathscr{L} \to \mathbb{Q}$ is any linear form, we may consider the $\mathbb{Q}$-bilinear map $f_\varphi : \mathscr{L} \times \mathscr{L} \to \mathbb{Q}$ given by $f_\varphi(x,y) = \varphi(x) \cdot \varphi(y)$. By (1), we have $$ \varphi(w)\cdot \varphi(h) = f_\varphi(w,h) = \sum_{i=1}^n f_\varphi(s_i,s_i) = \sum_{i=1}^n \varphi(s_i)^2 \geq 0. $$ In particular, if $\varphi(w) = 0$, then we must have $\varphi(s_1) = \cdots = \varphi(s_n) = 0$, and therefore $\varphi = 0$ (since $\mathscr{L}$ is spanned by $s_1,\ldots,s_n$). From this it is easy to see that $\mathscr{L}^*$, and therefore $\mathscr{L}$, is at most one-dimensional. Clearly we also have $\dim(\mathscr{L}) \geq 1$, since it contains non-zero numbers, so we conclude that $\mathscr{L}$ is one-dimensional.

Since $\mathscr{L}$ contains $s_1,\ldots,s_n$, it also contains $w$ and $h$. It follows that everything in $\mathscr{L}$ is a rational multiple of, say, $w$. In fact, we have proved something stronger: not only the $h$, but also $s_1,\ldots,s_n$ are rational multiples of $w$.

References:

[AZ14]: Martin Aigner, Günter M. Ziegler, Proofs from THE BOOK, Fifth Edition, Springer-Verlag Berlin-Heidelberg, 2014.

[Deh03]: M. Dehn, Über Zerlegung von Rechtecken in Rechtecke, Mathematische Annalen, Vol. 57 (1903), Issue 3, pp. 314-332.

[Dob16]: Josse van Dobben de Bruyn, Tiling a rectangle with squares, notes for the course SPC taught at Leiden University, available here.


For integer $n \ge 1$, let $[n]$ be a short hand for the interval of integers $\{ 1, 2,\ldots, n \}$.

Let $\{ s_1, s_2, \ldots, s_p \}$ be the set of sides of a bunch of squares that cover a rectangle of dimension $w \times h$.

Since $\mathbb{R}$ is a vector space over $\mathbb{Q}$, there is a hamel basis $E$ of $\mathbb{R}$ over $\mathbb{Q}$. Every real number can be uniquely expressed as a finite linear combination of elements from $E$ with rational coefficients. There will be finitely many of $e \in E$ that appear in the expansion of $s_1, \ldots, s_p$. Let $e_1, \ldots, e_q \in E$ be those appear in expansion of some $s_i$. There will be $p \times q$ coefficients $\alpha_{ij} \in \mathbb{Q}, (i,j) \in [p] \times [q]$ such that

$$s_i = \sum_{j=1}^q \alpha_{ij} e_j\quad\text{ for } i \in [p]$$

Furthermore, for each $j \in [q]$, there is some $i \in [p]$ with $\alpha_{ij}\ne 0$.

Rescale $e_i$ if necessary, we can assume all $\alpha_{ij} \in \mathbb{Z}$.

Under this setting, it is easy to see we can find integers $w_j, h_j \in \mathbb{Z}, j \in [q]$ such that

$$w = \sum_{j=1}^q w_j e_j\quad\text{ and }\quad h = \sum_{j=1}^q h_j e_j$$ For any $j \in [q]$, define function $f_j : [0,w] \times [ 0, h ] \to \mathbb{R}$ by $f_j(x,y) = \frac{\alpha_{ij}}{s_i}$ whenever $(x,y)$ is covered by a square of side $s_i$. Aside from a set of measure zero, $f_j$ is well defined. It is a piecewise constant function and integrable over $[0,w]\times[0,h]$. We can evaluate their integral over $[0,w]\times [0,h]$ in two different orders.

Aside from a finite choice of $y_0$, the line $y = y_0$ cut through finitely many squares "normally". Let $s_{i_1}, s_{i_2}, \ldots, s_{i_r}$ be the sides of the squares it cut through. We have

$$\int_0^w f_j(x,y_0) dx = \sum_{k=1}^r \int_{\sum_{\ell=1}^{k-1} s_{i_\ell}}^{\sum_{\ell=1}^{k} s_{i_\ell}}\frac{\alpha_{i_\ell j}}{s_{i_\ell}} dx = \sum_{k=1}^r \alpha_{i_\ell j} \in \mathbb{Z} $$ Notice $$\sum_{j=1}^q e_j \int_0^w f_j(x,y_0) dx = \int_0^w \sum_{j=1}^q e_j f_j(x,y_0) dx = \int_0^w dx = w$$ We obtain

$$\sum_{j=1}^q \left(\sum_{k=1}^r \alpha_{i_\ell j}\right)e_j = w = \sum_{j=1}^q w_j e_j$$

Since $e_j$ are linear independent over $\mathbb{Q}$, we obtain

$$\int_0^w f_j(x,y_0) dx = \sum_{k=1}^r \alpha_{i_\ell j} = w_j$$

From this, we can deduce $$\int_0^h\int_0^w f_j(x,y) dx dy = w_j h$$

By a similar argument, we have

$$\int_0^w\int_0^h f_j(x,y) dy dx = h_j w$$

Since these functions are integrable, we have

$$w_j h = \int_0^h\int_0^w f_j(x,y) dx dy = \int_0^w\int_0^h f_j(x,y) dy dx = h_j w$$

Since $w \ne 0$, some $w_j \ne 0$. Let's say $w_1 \ne 0$, we have $w_1 h = h_1 w \implies h_1 \ne 0$. As a result, $$\frac{w}{h} = \frac{w_1}{h_1} \in \mathbb{Q}$$