RTP If a rectangle can be tiled by a finite number of squares then the ratio of the lengths of its sides must be rational.

Definition 1   A baseline is a particular line in the plane.

Definition 2   An arrangement of squares is a set of squares in the plane, such that each square is oriented so that at least one of its sides is parallel to the baseline.

Definition 3   A boundary of a square in an arrangement is either of the sides of the square parallel to the baseline.

Definition 4   Boundaries are concurrent if they are the same perpendicular distance from the baseline. A boundary is said to be free if and only if it is concurrent to no other boundary.

Consider an arrangement $A$ of $n$ squares $\{S_i\}$. Consider also an $n$-dimensional vector space $V$ over $\mathbb{Q}$. Let $\{e_i : i=1\ldots n\}$ be a basis of $V$. Let $v : A \to V$ such that $S_i \mapsto v(S_i) = e_i \forall i$. $v$ is a bijection.

Definition 5   The vector of a square $S$ is the vector $v(S)$ as defined above.

Definition 6   The length of a square $S$ is the length of its sides, denoted $\ell(S)$.

Definition 7   A cross-section is a subset, $X$ of an arrangement of squares generated by a line $L$ parallel to the baseline such that $S \in X \Leftrightarrow L$    cuts $S$. More precisely, $S \in X \Leftrightarrow$ the perpendicular distance of the line $L$ from the baseline is strictly between the perpendicular distances of the boundaries of $S$. The vector and length of a cross-section X are defined respectively as:

$$v(X) = \sum_{S \in X}v(S)$$    and $$\ell(X) = \sum_{S \in X}\ell(S)$$

Definition 8   A cycle is a subset, $C$, of an arrangement of squares such that each boundary of each square in $C$ is concurrent with precisely one other boundary of a square in $C$. The vector of a cycle C is defined as:

$$v(C) = \sum_{S \in C}\epsilon_S v(S)$$

Where $\epsilon_S = \pm1$, chosen such that the length of C, $\ell(C) = \sum_{S \in C}\epsilon_S \ell(S)$, is zero. Existence of such a set $\{\epsilon_S\}$ is obvious by definition of a cycle.

Definition 9   The space, $\sigma(A)$, of an arrangement $A$ is the vector space over $\mathbb{Q}$ spanned by $\{v(X): X \in \mathbb{X} \} \cup \{v(C): C \in \mathbb{C} \}$, where $\mathbb{X}$ and $\mathbb{C}$ are the sets of all cross-sections and cycles in $A$ respectively.

Lemma 1   Considering an arrangement $A$ of $n$ squares $S_1$, ..., $S_n$, let $V$ be a vector space over $\mathbb{Q}$ with basis $\{e_i = v(S_i) : i = 1, \ldots, n\}$. Then $\sigma(A)=V$.

As all cross-sections and cycles are linear combinations of vectors of the squares in $A$, $\sigma(A)$ is a subspace of the space with basis $\{v(S) : S \in A\}$. Hence dim $\sigma(A) \le n$.

Take firstly the case $n=1$. There is at least one non-zero cross-section, so dim $\sigma(A) \ge 1$. Hence $\sigma(A)=V$ for $n=1$.

Now take an arrangement $A_n$ of $n$ squares, satisfying $\sigma(A_n) = V$. Add a new square $S_{n+1}$ to $A_n$ to form a new arrangement $A_{n+1}$.

Case 1   The new square has one free boundary.

As the new square has a free boundary it is not in a cycle. Therefore the set of cycle vectors remains unchanged. As the new square has a free boundary it divides an equivalence class of cross-sections into two. Pick a basis of $\sigma(A)$ consisting of $p$ cross-sections ($x$) and $q = n-p$ cycles ($c$) of $A_n$, $\{x_1, x_2, \ldots, x_p, c_1, \ldots, c_q\}$, such that $x_1$ is the vector of the cross-section from the class divided into two. For every other cross-section $x_i$ of $A_n$, either $x_i$ is a cross-section of $A_{n+1}$ or $x_i+v(S_{n+1})$ is a cross-section of $A_{n+1}$. It is obvious that $\{x_1, x_1+v(S_{n+1}), x_2, x_3, \ldots, x_p, c_1, \ldots, c_q\}$ spans the same space as $\{v(S_{n+1}), x_1, x_2, \ldots, x_p, c_1, \ldots, c_q\}$, which is linearly independent, hence forms a basis for an $(n+1)$-dimensional space. Also, if $x_i$ were to be replaced by $x_i+v(S_{n+1})$ in this basis, it would still span the same space and hence still be a basis. Therefore dim $\sigma(A_{n+1}) = n+1$.

Case 2   The new square has two free boundaries.

The argument runs similarly to case 1, except that the free boundaries divide two equivalence classes of cross-sections. This generates four cross-sections from the previous two, but those cross-sections span a three-dimensional subspace, hence dim $\sigma(A_{n+1}) = n+1$.

Case 3   The new square has no free boundaries, and forms a new cycle.

$\sigma(A_n) =$   span $\{e_1, \ldots, e_n\} =$   span $\mathbb{X} \cup \mathbb{C}$, where $\mathbb{X}$ and $\mathbb{C}$ are sets of all cross-sections and cycles in $A_n$ respectively. As creating a new cycle does not destroy any old cycles, $\mathbb{C'}$ (being the set of all cycles in $A_{n+1}$) = $\mathbb{C} \cup \{c\}$, where $c$ is the vector of the new cycle. However, $c=\sum_{S \in c}v(S)$, which is a linear combination of $\{e_1, \ldots, e_n\}$ and the vector of the new square $e_{n+1} = v(S_{n+1})$. Hence $\sigma(A_{n+1}) =$   span $\{e_1, \ldots, e_{n+1}\}$.

Case 4   The new square has no free boundaries, and forms no new cycle.

The set $X=\{x_1, \ldots, x_p\}$ of the vectors of all cross-sections of $A_n$ is linearly dependent (as it contains the zero vector). Thus there exist $\lambda_i$, not all zero, such that

$$\sum_{i=1}^p \lambda_i x_i = 0$$

Consider the same linear combination of vectors of cross-sections in $A_{n+1}$:

$$\sum_{i=1}^p \lambda_i (x_i + \delta_i e_{n+1}) = \sum_{i=1}^p \lambda_i \delta_i e_{n+1}$$

Where $\delta_i=1$ if the cross-section represented by $x_i$ contains $S_{n+1}$ and $\delta_i=0$ otherwise. Thus $e_{n+1}$ is a linear combination of vectors of cross-sections so long as $\sum \lambda_i \delta_i \ne 0$. If $\sum \lambda_i \delta_i = 0$, then pick another set of $\lambda_i$ such that $\sum \lambda_i \delta_i \ne 0$. Such a set exists, because otherwise the square $S_{n+1}$ will be in a cycle. Hence $e_{n+1}$ is a linear combination of the cross-sections of $A_{n+1}$. Thus $X \cup \{e_{n+1}\}$ spans all cross-sections of $A_{n+1}$, so $\sigma(A_{n+1})=V$.

Hence by induction dim $\sigma(A_n) = n \forall n$. QED.

Lemma 2   In an arrangement $A$, let $\mathbb{X}$ be the set of all cross-sections. Then for all squares $S_i$ and for some $\lambda_X \in \mathbb{Q}$,

$$\ell(S_i) = \sum_{X \in \mathbb{X}}\lambda_X\ell(X)$$

As $v(S)$ is bijective it is possible to define a linear function

$$f : \sigma(A) \to \mathbb{R}: e \mapsto \ell(v^{-1}(e)) \forall \ e$$    of the form $$v(S)$$    for some $$S \in A$$

By linearity, $\ell(X) = f(v(X))$ for cross-sections $X$, and $\ell(C) = f(v(C))$ for cycles $C$. Let $\mathbb{C}$ be the set of all cycles in $A$.

$$v(S_i) = \sum_{X \in \mathbb{X}\cup \mathbb{C}}\lambda_X v(X)$$

$$\ell(S_i) = \sum_{X \in \mathbb{X}\cup \mathbb{C}}\lambda_X \ell(X)$$

But $\ell(C) = 0$ by definition $\forall C \in \mathbb{C}$, so:

$$\ell(S_i) = \sum_{X \in \mathbb{X}}\lambda_X\ell(X)$$

QED.

Now consider a rectangle which is tiled by finitely many squares. Without loss of generality it is possible to uniformly scale the rectangle so that one of the side lengths is rational, and to rotate the rectangle so that the side with rational length is parallel to the baseline.

Lemma 3   Any subset of the tiles in the rectangle form an arrangement.

It is obvious that the sides of each square tile in the rectangle have sides parallel to the sides of the rectangle, otherwise they would leave gaps in the tiling pattern. QED.

Lemma 4   Let $\mathbb{X}$ be the set of all cross-sections in the arrangement of all tiles with irrational side length within the rectangle. Then

$$\ell(X) \in \mathbb{Q} \forall X \in \mathbb{X}$$

The length of any cross-section through the arrangement of all tiles in the rectangle is rational, as the length of the side of the rectangle parallel to the baseline is rational. It is possible to remove a square with rational sides from that arrangement and still have all cross-sections of rational length, as $\mathbb{Q}$ is closed under addition. Hence by induction (and using the fact that there are only finitely many squares), it is possible to remove all squares with rational sides but still have every cross-section having rational length. The remaining squares have irrational side length. QED.

Hence by Lemma 2, for each square $S$, $\ell(S)$ is the sum of rational multiples of rational numbers and hence is rational. Hence by contradiction no such square exists. Therefore each square tile in the rectangle is rational, hence the side perpendicular to the baseline also has rational length. QED.

Hosted by www.Geocities.ws