The rectangles a square can be cut into

A rectangle made only of squares proved Max Dehn’s theorem of 1903: a rectangle can be cut into finitely many squares, of any sizes, exactly when the ratio of its sides is a rational number. A rectangle of sides one and $\sqrt2$ cannot be squared, however small the squares are allowed to get.

Turn the question round. Instead of a rectangle cut into squares, take a square and cut it into rectangles — and require all the rectangles to have the same shape, the same ratio $r$ of long side to short, in whatever sizes and either way round. Dehn’s question is the case where the tile is a square and the thing tiled is a rectangle; this one fixes the outside and lets the tile have any shape. Which shapes can tile a square?

A rational ratio is easy: rectangles of ratio $5/2$, or any $p/q$, can be packed into a square by cutting the square into a grid of $p$ rows and $q$ columns, each cell a rectangle of width $1/q$ and height $1/p$ — ratio $p/q$. Nothing about shape restricts rational ratios, just as nothing about area restricts the cutting of one polygon into another in equal area is enough, and equal volume is not, where any polygon can be cut and reassembled into any other of the same area. A restriction on the pieces’ shape is a different kind of constraint, closer to the one in slid, but never turned, where the pieces may move but not rotate and a new invariant appears. The irrational ratios are the interesting ones, and the answer, found independently by Chris Freiling and Dan Rinne and by Miklós Laczkovich and György Szekeres in 1994–95, is that a square can be tiled by rectangles of ratio $r$ exactly when $r$ is a root of a polynomial with rational coefficients and every other root of its minimal polynomial has positive real part. For a number of the form $a + b\sqrt d$ the other root is $a - b\sqrt d$, and the condition is simply that this partner is positive.

The golden ratio $\varphi = (1 + \sqrt5)/2$ has partner $(1 - \sqrt5)/2 \approx -0.618$, negative: no square can be cut into golden rectangles. Its square $\varphi^2 = (3 + \sqrt5)/2$ has partner $(3 - \sqrt5)/2 \approx 0.382$, positive: a square can be, and the hero figure shows one way with six pieces.

Side by side and one above the other #

The tilings in this essay are found by a search that builds them from smaller ones, and the way it builds them is worth describing because it turns geometry into arithmetic. Describe a rectangle by its aspect, width divided by height. A tile of ratio $r$ has aspect $r$ lying down and $1/r$ standing up.

Put two rectangles of the same height side by side and the result has the same height and the sum of the widths, so its aspect is the sum of their aspects. Put two rectangles of the same width one above the other and the result has the sum of the heights, so the reciprocal of its aspect is the sum of their reciprocals. These are exactly the rules for combining electrical resistances in series and in parallel, which is the analogy a rectangle made only of squares used in the other direction: there, a squared rectangle was a network of unit resistors, and here a tiling built this way is a network of resistors of size $r$ and $1/r$. A square is a network whose total resistance is one.

So the search starts from the two aspects $r$ and $1/r$ and repeatedly combines what it has in the two ways, keeping every new aspect it finds, until it finds the aspect $1$. Every number involved is of the form $a + b\sqrt d$ with $a$ and $b$ rational, and the arithmetic is done exactly in that form, so a square found is a square and not a near miss.

Negative resistors never add up to one #

For the tilings the search can build, the impossibility of golden rectangles has a proof that uses nothing but the two combining rules. Apply the partner map $\sigma$ to every aspect in a side-by-side and stacked construction. Because $\sigma$ respects sums and products, it respects both rules: the partner of a side-by-side combination is the sum of the partners, and the partner of a stacked one is the reciprocal of the sum of the reciprocal partners. So the partners of the aspects are combined by the same series and parallel rules as the aspects themselves.

For golden rectangles the starting aspects $\varphi$ and $1/\varphi$ have partners $-0.618$ and $-1.618$, both negative. A sum of negative numbers is negative, and so is the parallel combination $1/(1/x + 1/y)$ of two negative numbers. Every aspect the construction can ever reach therefore has a negative partner. The square has aspect $1$, whose partner is $1$, positive. It is never reached, at nine tiles or nine million. In electrical terms, a network built from resistors of negative resistance, in series and parallel, always has negative total resistance, and a square is a one-ohm network.

For $\varphi^2$ the starting partners are $0.382$ and $2.618$, both positive, and positive numbers combine to positive numbers, so the argument forbids nothing — and the search finds a square. The figure of counts was a picture of this argument without its words: the golden column could grow to any height without containing a shape whose partner is positive.

The argument covers only the constructions the search uses. Its extension to every tiling is the area argument below, which needs no assumption about how the tiling was built.

Rectangles of the golden ratio squared, length by length #

The six-piece tiling in the hero figure has a simple structure, which the next figure makes explicit by writing every length exactly.

Each horizontal strip is a tile standing up beside a tile lying down. Their aspects add, and $1/\varphi^2 + \varphi^2 = 3$ exactly — the irrational parts cancel, because $1/\varphi^2 = (3 - \sqrt5)/2$ is the partner of $\varphi^2$. So each strip is a rectangle three times as wide as it is tall, and three such strips stacked make a square. The cancellation is the whole trick, and it shows up immediately why the partner matters: $\varphi^2$ and its partner multiply to one, so the turned tile carries exactly the irrational part that the lying tile needs removed.

The other quadratic shapes need the same kind of cancellation, arranged differently. For $2 + \sqrt2$ the search finds six tiles: a row of four standing tiles under one lying tile across the top. For $2 + \sqrt3$ it needs eight. In each case the irrational parts of the widths and heights are forced to cancel along every edge of the square, and the tiles arrange themselves so that they do. The search does not know the theorem; it only combines aspects and checks for one, and it finds tilings exactly for shapes the theorem allows.

Thousands of golden shapes, and never a square #

For golden rectangles the search runs and finds nothing.

The number of distinct aspects grows about fivefold with each tile — 2, 6, 20, 74, 316, 1,382, 6,462, 31,072 and 154,120 — and the aspect $1$ is not among them. A search of this kind can never prove impossibility on its own: it covers only tilings built by these two operations, and only up to nine pieces. The tilings it misses include every one that cannot be split by a straight cut running all the way across, which are most tilings with many pieces. So the empty column is evidence and nothing more. The proof that golden rectangles never tile a square is a different kind of argument, and it is short.

Change the sign of the square root #

Every number of the form $a + b\sqrt5$ has a partner $a - b\sqrt5$, and the map $\sigma$ that sends each number to its partner has a remarkable property: it respects addition and multiplication. The partner of a sum is the sum of the partners, the partner of a product is the product of the partners, and the partner of a rational number is itself. That is easy to check — the sign of $\sqrt5$ is never used in any rule of arithmetic, only its square, which is $5$ either way. In the language of a tower whose degrees multiply, $\sigma$ is a symmetry of the field $\mathbb{Q}(\sqrt5)$. What it does not respect is size: it sends the large number $\varphi$ to the negative number $-0.618$.

Suppose a square were tiled by golden rectangles, and suppose every width and height in the tiling were a number of the form $a + b\sqrt5$. The tiles’ areas add up to the square’s:

$$\sum_i w_i h_i = 1.$$

Apply $\sigma$ to both sides. Since it respects sums and products and fixes $1$,

$$\sum_i \sigma(w_i)\,\sigma(h_i) = 1.$$

Now each tile is golden: either $w_i = \varphi\, h_i$ or $h_i = \varphi\, w_i$. In the first case $\sigma(w_i)\sigma(h_i) = \sigma(\varphi)\,\sigma(h_i)^2$, and in the second it is $\sigma(w_i)^2/\sigma(\varphi)$. Either way it is a square times $\sigma(\varphi) = -0.618$, or a square divided by it, and so it is negative or nought. A sum of numbers that are all at most nought cannot be one. The tiling does not exist.

For the $\varphi^2$ tiling, the same computation goes through with a positive partner, and nothing goes wrong: the conjugate areas are $0.0424$ for the lying tiles and $0.2909$ for the standing ones — each orientation’s area and conjugate area swapped, since $\varphi^2$ and its partner are reciprocals — all positive, and they add up to one exactly, as the figure checks. The argument is not a trick that happens to work for the golden ratio. It is a test every tiling must pass, and the sign of the partner decides whether passing is possible.

The step the argument skipped #

The proof assumed that every width and height lies in $\mathbb{Q}(\sqrt5)$. A tiling found by drawing need not have that property — its lengths could be any real numbers that happen to fit. The gap is closed by a fact about linear equations. A tiling’s combinatorics — which tiles touch which, along which edges, and which way round each tile lies — determines a system of linear equations for the lengths: edges that line up have equal coordinates, each tile’s sides are in ratio $\varphi$ or $1/\varphi$, the outside is a unit square. All the coefficients lie in $\mathbb{Q}(\sqrt5)$. If such a system has a solution with all lengths positive, it has one with all lengths in the field, because positive solutions form an open part of the solution space and the solutions in the field are dense in it. So a tiling of any kind can be replaced by one of the same combinatorial shape with lengths in the field, and the sign argument applies to that one.

This is the same move as in the obstruction that was the only one, where Dehn’s invariant needed a function that was additive on angles without being anything like the size of an angle, and in no odd number of equal triangles, where Paul Monsky’s proof coloured the plane with a valuation that respects arithmetic and ignores distance. All three arguments find a map that keeps the algebra of a dissection and forgets its geometry, and then show that the algebra, once the geometry is forgotten, contradicts itself.

Which shapes can, and which cannot #

The test is easy to apply to any quadratic ratio, and the next figure sorts a family of them.

Twelve of the twenty-seven shapes are ruled out by the sign. Among the fifteen the theorem allows, the search with at most six tiles finds tilings for only some. The others are not counterexamples: the theorem guarantees a tiling, not a small one. A shape whose partner is positive but small has conjugate areas that are tiny for one orientation of tile and large for the other, and balancing them to sum to one needs more tiles in a more carefully weighted arrangement: $2 + \sqrt3$, with partner $0.268$, needed eight tiles in the search against six for $2 + \sqrt2$, whose partner is $0.586$. A further search up to ten tiles still finds no tiling for $3 + \sqrt2$, whose partner $1.59$ is comfortably positive, so even a healthy partner can demand many pieces when the ratio itself is large.

The general theorem, for ratios of higher degree, uses the same idea with every conjugate: a cubic ratio has two partners, possibly a complex pair, and each defines a map that respects arithmetic. The necessary condition is that each map sends the tile shape somewhere with positive real part, so that the conjugate areas cannot all cancel to nothing. The hard half of the theorem is the converse, that the condition is also sufficient, and its proofs construct tilings explicitly for every admissible $r$, which is far harder than ruling the others out.

A golden rectangle that eats itself, and cannot make a square #

The golden rectangle’s failure is ironic in view of its most famous property. The rectangle that eats itself is a golden rectangle with a square cut off, leaving a smaller golden rectangle: so a golden rectangle is a square plus a golden rectangle, and by repeating the cut, a square plus a square plus a square and so on, with a golden remainder that shrinks for ever. Golden rectangles are made of squares, infinitely many of them. Squares cannot be made of golden rectangles, finitely or — in any arrangement that stops — at all.

The asymmetry is the content of the partner’s sign. Dehn’s theorem says the golden rectangle cannot be cut into finitely many squares, because its ratio is irrational — the fact the diagonal no unit measures proved by exactly this endless cutting of squares from a pentagon’s diagonal; the infinite cutting is the closest it comes. The theorem here says the square cannot be cut into finitely many golden rectangles, because the golden ratio’s partner is negative. The ratio $\varphi^2$, whose partner is positive, is still irrational and so still cannot be cut into squares; but a square can be cut into it, with six pieces.

The two theorems test different things about the same number. Dehn’s asks whether $r$ is rational, which no amount of algebra can make true of $\varphi$ or $\varphi^2$. This one asks where $r$’s partners lie, which is a question about the polynomial $r$ satisfies: $\varphi$ is a root of $x^2 - x - 1$, whose other root is negative, and $\varphi^2$ a root of $x^2 - 3x + 1$, whose other root is positive. The two polynomials have the same field of definition and very different shapes, and the tiling question can see the difference while the squaring question cannot. A reader who wants to know whether a quadratic shape tiles a square needs only its polynomial $x^2 - sx + p$: the shape tiles exactly when both roots are positive, which for a real quadratic with a positive root means exactly when $s$ and $p$ are both positive.

What a search of this kind cannot do #

The tilings drawn here were found by one family of constructions, and the search is honest only within that family. Every tiling in it can be split into two parts by one straight cut, and each part split again, until single tiles remain; such tilings are called guillotine tilings, and many tilings are not of that kind. The counts of reachable shapes are therefore lower bounds on what $k$ tiles can do, and the sizes of the smallest tilings drawn are the smallest guillotine tilings, which may be beaten by others. A search over all tilings, guillotine or not, needs a description of how rectangles can meet that is far harder to enumerate.

The figures also cannot show the hard half of the theorem. Seeing that $\varphi$ is impossible takes one line of algebra; seeing that every shape with positive partners is possible requires a construction that works for all of them, and the small examples drawn here are evidence for it rather than a proof.

Still open: how many pieces #

For a ratio that can tile a square, how many tiles are needed? The question has a definite answer for each ratio and no known formula. For quadratic ratios the evidence of the searches is that the number grows as the partner approaches nought, which is what the sign argument suggests — a partner near nought makes the conjugate areas of the two orientations very unequal, and many tiles are needed to balance them — and also as the ratio itself grows, since long thin tiles fill a square slowly. Neither dependence has been made precise. Even for $\varphi^2$, whether six is the fewest possible over all tilings, guillotine or not, is a finite question that a search over non-guillotine arrangements could settle and that the search here does not.