Thrilling Tilings at Tiring Timings

(Etienne here.)

The date was 24 October 2021. It was late at night, and I was just about to tuck myself in. After all, the next day was the A-Level Physics practical! I needed to be well-rested (spoiler alert - I actually didn't). I was lying comfortably and about to bid a temporary farewell to the waking world, when suddenly, out of nowhere, I was attacked by a sudden thought: For what $r$ could I tile a square with rectangles whose sides had ratio $r$?

This was not a random thought. Earlier in the day, I had somehow encountered this other problem, from the 2018 Simon Marais Mathematical Competition:

For which integers $n$ is it possible to tile a square with $n$ rectangles whose sides have a ratio of $2:1$?

An excellent problem, and I invite the reader to try it in their spare time. The question that had come to me is then a natural generalisation of the above.

There is also another related classical problem, the answer to which is well-known, which can be thought of as the "inverse": For which $r$ can a rectangle with sides $r$ and 1 be tiled with squares? This problem has some neat proofs and definitely deserves an article of its own, but suffice to say, the answer is that it's possible only when $r$ is a rational number. So, then, one might reasonably expect that the answer to my question would also be the same. Right?

Investigations

Firstly, it's not hard to see that rational numbers work. I tried $\sqrt 2$ for a while, but it didn't seem to work. Let's try constructing a "bad" $r$. When we put 2 rectangles with side $1$ together, the other side can be $r$ or $\frac1r$. If we can make $ar+\frac b r=c$ for some positive integers $a$, $b$, and $c$ then we are done, because we can then use copies of this rational rectangle to make a square. But this is just a quadratic equation! So we have the following:

$r$ works if $r$ is a positive real solution to some equation $ar^2-br+c=0$, where $a,b,c$ are positive integers.

This suggests that if $r$ works, then any other positive real solution to its minimal polynomial (that is, the polynomial with minimum degree that has root $r$) should also work. In fact, in this case, the condition is equivalent to:

$r$ works if the degree of its minimal polynomial is 2 and if both solutions are real and positive.

Exercise: Prove that the two conditions are equivalent.

What about the other quadratic numbers, like $2+\sqrt 5$? Well, let's move on to cubics first :)

Let's apply the same wishful thinking: Let's suppose that the sign of the coefficients alternated, and that we could separate the polynomial as follows:

$$x^3+bx=cx^2+d$$

So we construct on the one hand rectangles with sides $x^3$-$x^2$ and $x$-$x^2$ and on the other $x^2$-$x$ and $x$-$1$, hoping that we can make a square. But if we try applying the condition directly, we get

$$x^3+bx=cx^2+d=ex^2+fx$$

If the third expression is equal to either of the first two, we get a polynomial with smaller degree, contradicting the minimality of the original polynomial!

I was stumped. Perhaps we ought to think about it in another way:

Say we use our similar rectangles to construct a rectangle whose sides have a ratio of $s$. What can we do with this new rectangle? Let's suppose that the set of all ratios of sides we can form is $S$. We can make a few deductions:

1. $r\in S$.
2. If $s\in S$, $qs \in S$ for any $q\in \mathbb Q^+$
3. If $s\in S$, $\frac 1s \in S$
4. If $s_1, s_2 \in S$, $s_1+s_2 \in S$

All we need to prove now is that 1 is in $S$. With this, the problem transitions from a geometric one to a fully algebraic one.

Even still, I struggled to make any significant progress after. Prudent readers might recall the setting of our story - yes, 'twas the night before Physics practical, and by the time I had reached this point, it was already 5am! Alas, I tried to make peace with the problem so that I may once more enter the world of dreams, but no! It gnashed and gnawed at me, not unlike the comedic trope in which a dog chases a butcher holding a string of sausages. Faced with this conundrum, I decided to google the answer, which brought me to a 1994 paper by Freiling and Rinne.

Learning the Truth

As it turns out, the answer is that rectangles whose sides have ratio $r$ can tile a square if and only if $r$ is algebraic, and the roots of its minimal polynomial all have positive real part. In the proof, the paper immediately presents this result without much explanation, attributing it merely to "Wall":

Let polynomial $P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots$ have real coefficients, and let $Q(x)=a_{n-1}x^{n-1}+a_{n-3}x^{n-3}+\cdots$. Then all the zeroes of $P(x)$ have negative real parts iff

$$\displaystyle \frac{P(x)-Q(x)}{Q(x)}=c_0x+\frac{1}{c_1x+\frac1{\dots+\frac1{c_{n-1}x}}}\text{where each }c_i>0.$$ 

which left me rather flabbergasted. Why would the position of the roots affect this continued fraction expansion? As it turns out, it takes some effort to prove...

Let us unpack the theorem first. Both the numerator and denominator in the fraction $\frac{P(x)-Q(x)}{Q(x)}$ consist of either odd or even powers of $x$. In fact, for the rest of this article I'll just assume that the degree of $P$ is even, because the argument for the odd case is exactly the same and also because I'm feeling a bit lazy. Then the numerator has only even powers and the denominator has only odd powers, and the degree of the numerator is one more than the denominator. So we can perform "long division":

$$\displaystyle \frac{P_{\text{even}}(x)}{P_{\text{odd}}(x)}=c_0x+\frac{R(x)}{P_{\text{odd}}(x)}$$

where $P_{\text{even}}$ and $P_{\text{odd}}$ are what you think they are, and now the degree of $R(x)$ is $n-2$, which is one less than the degree of $P_{\text{odd}}$. So we can represent it as $\frac1{\frac{P_{\text{odd}}(x)}{R(x)}}$, and repeat this process. In this way we get the continued fraction in the above function.

That's nice and all, but how does this help us? Well, let's suppose that our ratio $r$ has a minimal polynomial $P(x)$ whose roots all have positive real part.

Exercise: Prove that if $P(x)$ has real coefficients and all its roots have positive real part, then its coefficients must alternate sign.

Now if we let $Q(x)=P(-x)$, we have that all of the roots of $Q(x)$ have negative real part, and also that $Q_{\text{even}}(x)=Q_{\text{odd}}(x)$, so $\frac{Q_{\text{even}}(x)}{Q_{\text{odd}}(x)}=1$. Thus 1 may be expressed as the continued fraction up there where $c_i$ are positive and rational. If you, dear reader, would remember our discussion about the set $S$ which consists of the ratio of sides of attainable rectangles, you would realise that $1$ can be found to be in this set by inductively building up fractions.

So the problem is solved! As long as we can prove the theorem above, that is.

Since all polynomials can be written in the manner of the continued fraction, we should focus on what is special in this case, which is that the coefficients $c_i$ are all positive. Firstly, note that $c_0$ is simply $\frac{a_n}{a_{n-1}}$, and the rest of the coefficients can be defined inductively on their respective polynomials.

In particular, we get that $R(x)=P_{\text{even}}(x)-\frac{a_n}{a_{n-1}}xP_{\text{odd}}(x)$.

Secondly, we've gone from $\displaystyle \frac{P_{\text{even}}(x)}{P_{\text{odd}}(x)}\longrightarrow \frac{P_{\text{odd}}(x)}{R(x)}\longrightarrow \cdots$, but what I'd really like is something that characterises $P(x)$. So we add 1 to all our fractions in the chain: $\displaystyle \frac P {P_{\text{odd}}}\longrightarrow \frac{P_{\text{odd}}+R}{R}\longrightarrow \cdots$

Of course, we know what $R$ is, so we can substitute in the value, and the second term becomes

$$\frac{P-\frac{a_n}{a_{n-1}}xP_{\text{odd}}}{P_{\text{even}}-\frac{a_n}{a_{n-1}}xP_{\text{odd}}}$$

Now for a key observation: the denominator consists of all of the even-degree terms of the numerator!

That is, if we let the numerator be $Q(x)$, the denominator is simply $Q_{\text{even}}(x)$, which is of the same form as the first fraction. This suggests that if we can prove that $P(x)$ and $Q(x)$ share some property, then by an inductive argument this property is preserved down the chain of polynomials.

For our case, the property we want to prove is not just that $c_i>0$; in fact, we can prove that the stronger condition that all the roots have negative real part is preserved.

Further Down the Polynomial Path

(Routh-Hurwitz) Call a polynomial stable if all its roots have negative real part. A polynomial $P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots$ with real coefficients is stable if and only if $Q(x)=P(x)-\frac{a_n}{a_{n-1}}(a_{n-1}x^n+a_{n-3}x^{n-2}\cdots)$ is stable, and $a_n$ and $a_{n-1}$ have the same sign.

This is apparently a famous theorem from control theory, which is where the name "stable" comes from. (Hint: it does not refer to a building in which horses are kept.)

There are various proofs of this; I will present an elementary one due to Gjerrit Meinsma of the University of Newcastle.

Before anything else, I will once again assume the degree $n$ is even (out of laziness). We will define the polynomial

$Q_{\eta}(x)=P(x)-\eta x P_{\text{odd}}(x)$ where $\eta$ is some real number.

The main ingredient of the proof is showing that the family of polynomials $\{Q_{\eta}\}$have exactly the same roots on the imaginary axis (that is, roots of the form $\alpha i$ where $\alpha\in\mathbb R$ and $i=\sqrt{-1}$).

To do this, write $Q_{\eta}=(P_{\text{even}}-\eta x P_{\text{odd}})+P_{\text{odd}}$ so that it is the sum of an odd and an even polynomial. For any purely imaginary number, the even part of $Q$ takes only real values and the odd part takes imaginary values. Thus, any imaginary root of $Q$ must also be a root of both $Q_{\text{even}}$ and $Q_{\text{odd}}$, which is the case iff it is also a root of $P_{\text{even}}$ and $P_{\text{odd}}$ (with the same multiplicity, which can be shown by differentiating).

Therefore, as $\eta$ varies from 0 and approaches $\frac{a_n}{a_{n-1}}$, the roots of $Q_{\eta}$ vary continuously also. If at any point the number of roots in the left half-plane is different, a root must have crossed over the imaginary axis, which is impossible. So the number of roots in the left half-plane remains constant. The only time it may change is when $Q_{\eta}$ changes degree, exactly when $\eta=\frac{a_n}{a_{n-1}}$.

But note that as $\eta$ approaches $\frac{a_n}{a_{n-1}}$, the leading coefficient of $Q_{\eta}$ approaches 0, and $n-1$ roots of $Q_{\eta}$ approach those of $Q$, during which none cross the imaginary axis. From Vieta's we have that the sum of roots must be $-\frac{a_{n-1}}{a_n-\eta a_{n-1}}$, which either goes to positive or negative infinity depending on the sign of $a_{n-1}$, and so the last root also tends to either positive or negative infinity. If $a_n$ and $a_{n-1}$ have the same sign, it goes to negative infinity, and therefore $P$ is stable iff $Q$ is stable and the first two coefficients of $P$ have the same sign. (Note: the condition that the sign is the same is necessary only when going to $P$ from $Q$. We know that it is superfluous when going down.)

Sanity Check

To recap, we have shown that if $P$ has all of its roots in the complex right half-plane, then $1$ may be expressed as a continued fraction expansion of $P_{\text{even}}$ over $P_{\text{odd}}$, or vice versa, whose coefficients $c_i$ are all positive. We can also clearly reason that the coefficients are rational, since they are the ratios of coefficients of some polynomials with rational coefficients. And this leads directly to the desired tiling.

Perhaps some readers are still puzzled as to how we obtain a tiling: I will demonstrate. Take for example the ratio $r=2+\sqrt[5]{8}$. Clearly the minimal polynomial for $r$ is $P(x)=(x-2)^5-8$.

The roots of this are $2+\omega_5^n\sqrt[5]{8}$, where $\omega_5$ is the fifth root of unity and $n$ varies from $0$ to $4$, all of which have positive real part because $\sqrt[5]{8}$ is small.

Expanding, we have that $P(x)=x^5-10x^4+40x^3-80x^2+80x-40$. Since $P(r)=0$,

$\begin{aligned} 10r^4+80r^2+40&=r^5+40r^3+80r\\ \displaystyle 1&=\frac{r^5+40r^3+80r}{10r^4+80r^2+40}\\ \displaystyle &=\frac1{10}r+\frac1{\frac{10r^4+80r^2+40}{32r^3+72r}} \\ \displaystyle &=\frac1{10}r+\frac1{\frac{5}{16}r+\frac1{\frac{32r^3+72r}{57.5r^2+40}}}\\ \displaystyle &=\frac1{10}r+\frac1{\frac{5}{16}r+\frac1{\frac{64}{115}r+\frac1{\frac{57.5r^2+40}{\frac{1144}{23}r}}}}\\ &= \frac1{10}r+\frac1{\frac{5}{16}r+\frac1{\frac{64}{115}r+\frac1{\frac{2645}{2288}r+\frac1{\frac{143}{115}r}}}} \end{aligned}$

Hopefully I did the calculations right. Anyway, we construct starting down and work our way up. So we start with a rectangle of ratio $\frac{143}{115}r:1$, which we know we can create. Then we adjoin to the side corresponding to $\frac{143}{115}r$ a rectangle with ratio $\frac{2645}{2288}r:1$, where the side corresponding to $1$ in the latter is touching. In this way, we get the sum $\frac{2645}{2288}r+\frac1{\frac{143}{115}r}$. Eventually, we get something like this:

Where the rectangles are colour-coded with the order of the rainbow starting from $\frac{143}{115}r$ and going upward. (Orange is $\frac{2645}{2288}r$, and so on.)

Diligent readers might realise that we are actually only half-done with the problem! We have proven that algebraic numbers whose conjugates are all positive work, but we didn't prove that these are the only numbers which work. Unfortunately, proving the opposite direction requires more theory than I'm willing to go into in this article. It is however, similar in spirit to the proof of the classical problem of tiling rectangles with squares.

Ending Thoughts

I'm not really sure what the key takeaway from this story is supposed to be. Maybe it's "Try not to have late night thoughts, lest they will haunt you in your sleep." For those wondering, I did indeed do quite well for my practical exam.

Maybe there doesn't need to be a takeaway, and we can simply appreciate the proof presented here: the way in which it takes us on a journey from combinatorics and geometry, through continued fractions, to polynomials. I personally found the continuity argument used to prove the Routh-Hurwitz criterion quite enlightening. A good proof should be like an artwork framed in a museum - evoking awe and emotion through its beauty.

Further Links:

1. Simon Marais Mathematics Competition 2018
   
2. Original Paper by Freiling and Rinne
   
3. Meinsma's Proof of the Routh-Hurwitz Test