A rectangle made only of squares

Equal area is enough: any two polygons of the same area can be cut into each other with finitely many straight cuts, and the pieces may be any shapes the cutting produces. The whole of the classical theory of dissection lives in that freedom, and the natural way to learn what it buys is to take it away. Restrict the pieces to one kind of shape and ask what can still be cut.

The most restrictive interesting choice is squares. Which rectangles can be cut into finitely many squares — squares of any sizes, as many as wanted, but squares?

The answer is exact and surprising in its form. A rectangle can be cut into squares if and only if the ratio of its sides is a rational number. A $33 \times 32$ rectangle can be; a $1 \times \sqrt 2$ rectangle cannot, however many squares are allowed and however small. Equal area was enough for arbitrary pieces; for squares, what matters is not area at all but whether the two sides share a common unit of length.

The easy half, and why it is easy #

If the sides are commensurable — say $p \times q$ for whole numbers $p$ and $q$, after choosing the unit — then the rectangle can be cut into $pq$ unit squares. That is the whole of one direction, and it is a little disappointing: it uses squares of a single size and says nothing interesting about them.

The interesting squarings use squares of different sizes, and the most interesting use no size twice. Moroń’s rectangle does exactly that with nine squares, and nine is the fewest possible — there are exactly two rectangles that can be cut into nine unequal squares, this one and one of $65 \times 47$, and none with fewer. Finding them was a game of trial and patience in the 1920s. The arrangement in the figure was reconstructed here from the list of sides alone, by a search that repeatedly places some unused square into the lowest, leftmost empty corner and backs up when nothing fits; a nine-piece puzzle is small enough that the search is instant.

What the easy half does not explain is why a rectangle whose sides are not in rational proportion should be out of reach. A $1 \times \sqrt 2$ rectangle has area $\sqrt 2$, and there are plenty of squares whose areas could add up to that. Nothing in the counting of areas rules it out. The obstruction has to be something else.

Squaring greedily, and a squaring that never ends #

There is one obvious procedure for cutting a rectangle into squares: cut off the largest square that fits, then do the same to what is left, and repeat.

On a $13 \times 8$ rectangle this is Euclid’s algorithm in squares: cut an $8 \times 8$ square off the $13 \times 8$ rectangle, leaving $5 \times 8$; cut a $5 \times 5$ square, leaving $5 \times 3$; and so on down to the last $1 \times 1$. The number of squares of each size is the sequence of quotients Euclid’s algorithm produces, and the process ends because the two sides have a common measure. Every rectangle with commensurable sides is squared this way in finitely many steps.

On a $1 \times \sqrt 2$ rectangle the same procedure never ends.

After the first square, the leftover rectangle has sides $1$ and $\sqrt 2 - 1$, and two squares of side $\sqrt 2 - 1$ fit across it, leaving a rectangle whose sides are in the ratio $1 : \sqrt 2$ again, shrunk by a factor of $(\sqrt 2 - 1)^2$. The pattern repeats forever, spiralling into a corner. It is the diagonal that no unit measures, seen as a dissection: the continued fraction of $\sqrt 2$ is infinite, and each partial quotient is a run of equal squares.

This is suggestive and proves nothing. The greedy procedure is one way of squaring a rectangle, and its failure does not show that a cleverer arrangement of squares, of sizes chosen with care, could not fit together exactly. That needs an argument about every possible squaring at once.

A squared rectangle is an electrical circuit #

The argument that settled the question for good was found in 1940 by four undergraduates at Trinity College, Cambridge — Leonard Brooks, Cedric Smith, Arthur Stone and William Tutte — who had set out to find a square cut into unequal squares and ended up with a theory. Their observation is that a squared rectangle is secretly a circuit.

Look at the horizontal lines in a squared rectangle — the maximal horizontal segments made of square edges. Every square sits between two of them: its top edge lies along one, its bottom edge along another. Now make each segment a node of a network, and each square a wire joining the segment along its top to the segment along its bottom.

Give each segment a voltage equal to its height below the top edge, and each wire a current equal to its square’s side. Then two things hold, and both are simply facts about squares.

Ohm’s law, with every resistance one. The voltage drop along a wire is the difference in height between its square’s top and bottom — the square’s side — and so is the current. Current equals voltage drop.

Kirchhoff’s current law. Take any inner segment. The squares sitting on top of it have bottoms along it, and their widths add up to the segment’s length; the squares hanging below it have tops along it, and their widths add up to the same length. So the current flowing into the segment from above equals the current flowing out below.

Every squared rectangle is therefore an electrical network of unit resistors, with a battery across its top and bottom edges. Its width is the total current and its height is the total voltage.

The network knows the answer by itself #

The payoff is that the network determines the squares. Given only which segment each wire joins — no sizes, no positions — Kirchhoff’s laws are a system of linear equations with whole-number coefficients, one equation for each inner node, and such a system has a unique solution once the voltage across the whole is fixed.

Now the theorem falls out. Solving linear equations with whole-number coefficients by elimination only ever adds, subtracts, multiplies and divides whole numbers, so every solution is a rational number. With the voltage across the rectangle set to $1$, every current — every square’s side — is rational, and so is the total current, which is the width. The rectangle’s width divided by its height is a rational number.

That is Dehn’s theorem, in the only direction that was hard: a rectangle cut into squares has commensurable sides. The $1 \times \sqrt 2$ rectangle cannot be squared, because any squaring of it would be a circuit of unit resistors whose total current over total voltage is $\sqrt 2$, and no such circuit exists.

The same computation says where the whole numbers come from. Kirchhoff’s own theorem — a determinant that counts trees — says the natural common denominator of the currents in a network of unit resistors is its number of spanning trees. Moroń’s network has $66$ spanning trees, twice its width, and drawn at the size the network itself prefers, the rectangle is $66 \times 64$ with every square doubled. Brooks, Smith, Stone and Tutte used exactly this to search for squared rectangles: enumerate the networks, solve them, and read the rectangles off.

Dehn’s own argument, and the grid it works on #

Dehn’s original proof in 1903 had no circuits in it. It used an idea that the essay on Hilbert’s third problem met in three dimensions: an invariant that addition respects and that squares and the rectangle cannot share.

Suppose a rectangle with sides $1$ and $x$, with $x$ irrational, were cut into squares. Choose a function $f$ on real numbers that adds correctly — $f(a + b) = f(a) + f(b)$ — with $f(1) = 1$ and $f(x) = -1$. Such a function exists, though nobody can write one down: it is a function that adds and is nowhere a line, built from a basis of the real numbers over the rationals, and it needs $1$ and $x$ to be independent over the rationals — which is exactly what irrationality of $x$ means.

Give every rectangle with sides $a$ and $b$ the “area” $f(a)f(b)$. Because $f$ adds, this area adds too: cut a rectangle in two by a straight line and the two areas sum to the whole. Extending every edge of the squaring into a grid, as in the figure, turns the squaring into a subdivision of both the whole rectangle and each square into the same small rectangles, and adding up over the grid gives

$$f(1)\,f(x) = \sum_{\text{squares}} f(s)^2.$$

The left side is $-1$. The right side is a sum of squares, and is at least $0$. The contradiction proves the theorem, with no picture of a circuit anywhere — and with a function that cannot be constructed doing all the work, which is a strange thing for so concrete a statement to need.

Two proofs, one idea #

The circuit and the additive function look nothing alike, and it is worth seeing that they are the same argument in different clothes.

Both proofs attach a number to every piece in a way that respects gluing. In the circuit, the number is a current, and gluing is Kirchhoff’s law: the currents entering a segment add up to the currents leaving it. In Dehn’s proof, the number is the fake area $f(a)f(b)$, and gluing is additivity: cutting a rectangle in two splits its fake area in two. Each proof then observes that the numbers on the pieces are constrained in a way the whole rectangle cannot match — the currents must be rational, the fake areas of squares must be non-negative.

That is the same shape as every impossibility result on this subject’s first page. Dehn’s invariant for polyhedra attaches a number to each edge that cutting cannot change; the invariant for dissections that only slide attaches a number to each direction. Here, restricting the pieces to squares makes a new invariant available — one that uses the fact that a square’s width and height are equal, which is what forces $f(s)^2$ rather than a product of two different numbers. Relax “square” to “rectangle” and the invariant disappears, and indeed any rectangle can be cut into two rectangles of any proportions.

The circuit reading also connects the question to an unexpected neighbour. A network of unit resistors carrying a current from one terminal to another is a flow, and the maximum flow a network carries is limited by its narrowest cut. In a squared rectangle every vertical line across the rectangle is a cut, and the squares it crosses carry the whole width between them — the rectangle’s version of the statement that current is conserved through every cross-section of a wire. The squares are the flow, drawn to scale.

How many squares a rectangle needs #

Dehn’s theorem says which rectangles can be squared and says nothing about how many squares it takes, which is the question the count of pieces asked for general dissections. For squares it has a definite answer in one direction. A $p \times q$ rectangle in lowest terms can always be squared with the greedy method, using as many squares as the sum of the partial quotients in the continued fraction of $p/q$; for $13 \times 8$ that is six, and for $34 \times 21$, two Fibonacci rectangles further on, it is eight.

Whether fewer squares are possible is a different matter, and the answer can be much smaller than the greedy count. A $n \times (n+1)$ rectangle needs $n + 1$ greedy squares — one $n \times n$ square and then a strip of $n$ unit squares — while cleverer arrangements, in which squares of several sizes interlock rather than stacking into strips, use far fewer once $n$ is large. The exact minimum is known only for small rectangles, by search, and the question of how it grows for general $p \times q$ has upper and lower bounds that do not meet.

A square made of unequal squares #

The question that sent the four undergraduates to their circuits was whether a square can be cut into squares that are all different sizes. Dehn’s theorem permits it — a square’s sides are certainly commensurable — but gives no construction, and several mathematicians had conjectured it impossible.

It is possible. Roland Sprague published the first perfect squared square in 1939, with fifty-five squares, just ahead of the Cambridge group’s own. The smallest possible needs twenty-one, and there is exactly one of that size.

Duijvestijn found it in 1978 by exactly the method the circuit picture suggests — enumerating networks of a given size by computer, solving each, and checking which produced a square with all sides distinct — and showed that nothing smaller exists. The search here runs the other way, from the sizes back to the picture, and it is a small check on the list: the twenty-one squares’ areas add up to $112^2 = 12{,}544$, and they fit together in exactly one way.

The circuit also explains why perfect squarings are rare. Most networks produce rectangles with two equal squares somewhere, because symmetrical parts of a network carry equal currents. A perfect squaring needs a network with no symmetry at all, and the smallest such networks that happen to give a square have twenty-one wires.

What the pictures cannot show #

Every figure above is a rectangle that can be squared, and the theorem is about one that cannot. No picture shows a $1 \times \sqrt 2$ rectangle failing to be squared; the greedy picture shows one procedure failing, which is suggestive and is not the proof. The proof is the circuit argument or Dehn’s additive function, and both are statements about every possible squaring at once — the first by the rationality of solutions to whole-number equations, the second by a function nobody can draw.

The figures also show only squarings, not the richer family the argument covers. The circuit proof works for any tiling of a rectangle by smaller rectangles each of which has its sides in some fixed irrational ratio to each other — and a closely related argument shows that if every small rectangle in a tiling has at least one side of whole-number length, so does the big one. That result has more than a dozen published proofs, collected by Stan Wagon in 1987, and none of them is the picture of a tiling.

And the network picture used here is the simplest version. When squares meet only at corners, or four squares share a point, the segments and the network need more care, and the correspondence between networks and squared rectangles is not one-to-one; the rectangles drawn here were chosen so that it is.

Still open: the fewest squares and the counting #

The existence questions are settled: Dehn characterised the squarable rectangles, Sprague and the Cambridge group showed perfect squared squares exist, and Duijvestijn found the smallest. What remains are questions of counting, which have been pushed forward entirely by computation.

The number of perfect squared squares of each order is known only up to orders in the thirties, from searches that enumerate every network of that size, and no formula or asymptotic for the count is known. The same is true of cubing: no cube can be cut into finitely many smaller cubes of all different sizes — the smallest cube on the bottom face would have to be surrounded by larger ones, and the cube on top of it again, forever — so the three-dimensional analogue of the perfect squared square does not exist, and the argument is a descent rather than a circuit. Whether there is a single principle that explains which dissections into similar pieces are possible — squares, triangles of one shape, cubes — is not known; the answers are each proved by their own device. Even the simplest-sounding version — which rectangles can be cut into squares with every size used at most once, as a function of the proportion — has no characterisation: the perfect squared rectangles of each order are listed by computer, and nothing predicts which proportions appear.