Tiling polygons by similar polygons
Table of Contents
By “\(P\) tiles \(Q\)” we will mean that \(Q\) can be decomposed into polygons each of which is similar to \(P\). We will denote by \(R(u)\) the (similarity class of the) rectangle with sides \(1\) and \(u\), and \(T(u)\) will denote the right-angled triangle with perpendicular sides \(1\) and \(u\).
Square by rectangles (warm up)
\(R(u)\) can be tiled by squares iff the ratio of its sides is rational.
A “notion of area for tilings by rectangles”, is a finitely additive measure for unions of rectangles (here simply called a measure) with sides parallel to the axes. For this it is enough to give a biadditive function \({\mathbb{R}}\times {\mathbb{R}}\to\) some Abelian group.
Use measure \(\mu(R(x,y)) = f(x)f(y)\) where \(f : {\mathbb{R}}\to {\mathbb{R}}\) is \({\mathbb{Q}}\)-linear and \(f(1) = 1\), \(f(u) = -1\).
Dehn proved the above in 1903 (he solved Hilbert’s 3rd problem in 1900 –by showing the regular tetrahedron and a cube of equal volume are not equidecomposable). His proof is complicated and builds a system of linear equations representing a tiling with a unique solution. The above argument was impossible before 1905 when Hamel showed there are non-\({\mathbb{R}}\)-linear additive functions.
(Dehn 1903) If a rectangle with ratio \(r_0\) is decomposed into rectangles with ratios \(r_1, \ldots, r_n\), then \(r_0 \in {\mathbb{Q}}(r_1, \ldots, r_n)\).
Use measure \(\mu(R(x,y)) = f(x)f(y)\) where \(f\) is \({\mathbb{Q}}(r_1,\ldots,r_n)\)-linear, \(f(1) = 1, f(r_0) = -1\).
Square by rectangles
(Laczkovich and Szekeres 1995; Freiling and Rinne 1994) A square can be tiled by \(R(u)\) iff \(u\) is algebraic and all of its conjugates have positive real part.
\((\Rightarrow)\) Use measure \(\mu(R(x,y)) = f(x) \overline{f(y)}\) where \(f : {\mathbb{Q}}(u) \hookrightarrow {\mathbb{C}}\).
\((\Leftarrow)\) Closure properties of \(S:=\{x : R(u) \;\mathrm{tiles}\; R(x)\}\):
- \(u \in S\)
- \(x \in S \Rightarrow 1/x \in S\)
- \(x,y \in S \Rightarrow x+y \in S\)
Thus, for \(c_1, \ldots, c_n \in {\mathbb{Q}}_{>0}\), \[c_1 u + \frac{1}{c_2 u + \frac{1}{\ddots + \frac{1}{c_n u}}} \in S.\] Now use the following theorem applied to the minimal polynomial of \(u\):
(Wall 1945) Let \(P(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0\) and \(Q(x) = a_{n-1} x^{n-1} + a_{n-3} x^{n-3} + \cdots\). All roots of \(P(x)\) have positive real part iff \[1-\frac{P(x)}{Q(x)} = c_1 x + \frac{1}{c_2 x + \frac{1}{\ddots + \frac{1}{c_n x}}}\] for positive \(c_1, \ldots, c_n\).
Both pairs of authors use this theorem of Wall’s!
Rectangle by rectangles
(Freiling, Laczkovich, and Rinne 1997) \(R(v)\) can be tiled by \(R(u)\) \(\iff\) there is a rational function with rational coefficients mapping \(u\) to \(v\) and preserving mapping \(\{\Re(z)>0\}\) and \(\{\Re(z)<0\}\) into itself \(\iff\) there is an odd rational function with rational coefficients mapping \(u\) to \(v\) such that all preimages of \(v\) have positive real part.
Square by triangles
(Laczkovich 1990; Szegedy 2001) A triangle \(T\) tiles the square iff \(T\) is either a \(T(u)\) where \(u\) is an algebraic number all of whose real conjugates are positive, or \(T\) is one of the three triangles with angles \[\left( \frac{\pi}{8}, \frac{\pi}{4}, \frac{5\pi}{8} \right), \left( \frac{\pi}{4}, \frac{\pi}{3}, \frac{5\pi}{12} \right), \left( \frac{\pi}{12}, \frac{\pi}{4}, \frac{2\pi}{3} \right)\]
Laczkovich proved the \(\Rightarrow\) direction and also that the three “sporadic” triangles tile the square. Szegedy proved that any \(T(u)\) (for \(u\) algebraic with all real conjugates positive) tiles the square.
In the same paper where he showed his portion of the theorem, Laczkovich shows that if a triangle tiles a rectangle, it is either a right triangle, one of the three sporadic ones for the square or the one with angles \(\left( \frac{\pi}{6}, \frac{\pi}{6}, \frac{2\pi}{3} \right)\) –which tiles \(R(\sqrt{3})\).
The proof is a bit long, so we will only sketch the proofs of the statements about right triangles.
Only those right triangles can possibly tile
If \(P\) is decomposed into triangles, the coordinates of all the vertices of the triangles belong to the field generated by the coordinates of the vertices of \(P\) and the cotangents of the angles of the triangles.
If a convex \(P\) is decomposed into triangles, and two vertices have coordinates in the field generated by the cotangents of the angles of the triangles, then all vertices of the triangles have coordinates in that field.
A collineation is a map that sends colinear triples to colinear triples (with not necessarily distinct points). A map is orientation preserving if it sends positive triangles to either positive or degenerate triangles.
A collineation that preserves orientations, sends a triangle decomposition to another triangle decomposition (maybe combinatorially non-isomorphic!).
Use complex line integrals \(I_\Delta(z) = \frac{1}{2\pi i} \int_{\partial \Delta} \frac{d \zeta}{\zeta - z}\) and the fact that \(\sum \partial\Delta_i\) is preserved.
Let \(P\) be decomposed into triangles and \(f\) be field morphism from the field generated by the coordinates of vertices of \(P\) and the cotangents of the angles of the triangles into \({\mathbb{R}}\) that fixes the vertex coordinate subfield. Then for some triangle, at least two of the \(f(\cot \theta)\) are positive.
Applying \(f\) to each coordinate is a collineation, which must preserve the orientation of at least one triangle (since the sum of oriented areas stays positive, equal to the are of the polygon).
The \(30^\circ, 60^\circ, 90^\circ\) does not tile the square. (This answers a question of Posa.)
(Of the right triangle case.) If \(u\) has a negative real conjugate (which definitely happens if \(u\) is transcedental), then we get a contradiction to the above lemma.
Those triangles do tile
Szegedy proves that if \(u\) is algebraic with all real conjugates positive, then \(T(u)\) does tile the square by cleverly reducing to the result for tiling a square by rectangles.
Let \(P\) be the smallest subset of \({\mathbb{Q}}(t)\) such that
- \(t \in P\)
- \(f \in P \Rightarrow 1/f \in P\)
- \(f, g \in P \Rightarrow f+g \in P\)
- \(f \in P \Rightarrow n\frac{1+t^2}{f+t}+t \in P\)
If \(u>0\) and \(f \in P\), then \(T(u)\) tiles \(R(f(u))\).
We just need to show that \(\{ x : T(u) \;\mathrm{tiles}\; R(x) \}\) has the same closure properties as \(P\). The first three are clear. For the last one draw a rectangle, chop off a \(T(u)\) from each end to leave a parallelogram, divide that into \(n\) thin parallelograms and from each of those chop off a \(T(u)\) from the top and bottom.
If \(p(t)\) is a polynomial with nonnegative real coefficients then \(t p(1+t^2)\) is a pointwise limit of functions in \(P\).
\(P\) is also closed under \(f \mapsto \frac{1+t^2}{1/f+t/n}+\frac{t}{n}\). Iterating this \(k\) times starting with \(t\), gives a sequence (indexed by \(n\)) whose pointwise limit is \(t(1+t^2)^k\).
Let \(S\) be a finite set of complex numbers such that \(S \cap \overline{S} = \emptyset\). Then there is a polynomial \(p(t) \in {\mathbb{R}}_{\ge 0}[t]\) taking specified values on \(S\).
This follows from two claims:
- There is a polynomial \(g(t)\in{\mathbb{R}}[t]\) taking those values.
- There is a polynomial \(h(t)\in{\mathbb{R}}_{\ge 0}[t]\) vanishing on \(S\).
We can then take \(p(t) = g(t) + a(1+t+t^2+\cdots+t^k)h(t)\).
Let \(u\) be an algebraic number all of whose real conjugates is positive. Then there is \(p(t) \in {\mathbb{R}}_{\ge 0}[t]\) such that \(v p(1+v^2) > 0\) for all conjugates \(v\) of \(u\).
Let \(H\) be “half” of the nonreal conjugates of \(u\) and let \(S = \{ 1 + v^2 : v \in H \}\). By the lemma above, there is \(p(t) \in {\mathbb{R}}_{\ge 0}[t]\) such that \(p(1+v^2) = 1/v\) for \(v \in H\), and thus for \(v \in H \cup \overline{H}\). For real conjugates of \(v\), \(v p(1+v^2)\) is also positive, so we are done.
First, pick \(p(t) \in {\mathbb{R}}_{\ge 0}[t]\) such that \(vp(1+v^2)>0\) for all conjugates \(v\) of \(u\). Since \(tp(1+t^2)\) is a pointwise limit of functions in \(P\), there is an \(f \in P\), such that \(\Re(f(v))>0\) for all conjugates \(v\) of \(u\). Since then \(R(f(u))\) tiles the square, and \(T(u)\) tiles \(R(f(u))\), we are done.