🔢 mathematics

Optimally Packing a Large Square by Unit Squares

The paper demonstrates that a large square of side length $x$ can be packed with unit squares such that the resulting wasted space is bounded by $O(x^{3/5})$ .

Original authors: Rory McClenagan

Published 2026-02-03

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Rory McClenagan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, square room (let's call it Room X) and a huge pile of identical, one-foot-by-one-foot floor tiles. Your goal is to cover as much of the floor as possible with these tiles without them overlapping.

If the room is exactly 10 feet wide, you can lay 10 rows of 10 tiles perfectly. No gaps. But what if the room is 10.3 feet wide?

The Problem: The "Naive" Gap

If you try to lay the tiles straight up and down (parallel to the walls), you hit a problem. You can fit 10 full tiles, but you are left with a thin, 0.3-foot strip of empty space running the entire length of the room.

If the room is 1,000 feet wide, that strip is 1,000 feet long.
The "wasted space" (the empty area you can't cover) is huge.

For decades, mathematicians tried to find a better way to tile these rooms to minimize that wasted space. The best previous method involved tilting the tiles slightly, which reduced the waste, but it was still quite large.

The Solution: A "Staircase" of Angles

This paper, by Rory McClenagan, introduces a new, clever way to pack the tiles that significantly reduces the wasted space. Instead of just tilting the tiles once, the author uses a two-step "dance" of angles that cancels out the errors.

Here is the analogy of how it works:

Step 1: The "Tilted Stacks"

Imagine you don't lay the tiles in straight rows. Instead, you build them in diagonal stacks.

You lean the stacks slightly against the wall.
Because they are leaning, they fit together in a way that creates a jagged, stair-step pattern along the edges.
This leaves a few small, triangular gaps at the very top and bottom of the room, but it fills the middle very efficiently.

Step 2: The "Angle Correction" (The Two Algorithms)

Here is the tricky part. If you keep leaning the stacks the same way all the way down the room, the "jaggedness" gets worse and worse, creating a big gap at the end.

The author's breakthrough is using two different packing patterns that work together like a pair of scissors or a zipper:

The First Pattern: You pack a section of the room by leaning the tiles one way. This creates a specific angle of "waste" at the top of that section.
The Second Pattern: Immediately after, you switch to a second pattern that leans the tiles the opposite way (or adjusts the angle just enough) to "undo" the mistake made by the first pattern.

Think of it like walking up a hill and then immediately walking down a slope of the exact same steepness. You end up back at the same level, having covered the distance without gaining or losing height.

By alternating these two patterns over and over, the author ensures that the "wasted space" (the gaps) stays tiny and doesn't grow as the room gets bigger.

The Result: A Mathematical Magic Trick

The paper proves that by using this specific "tilted stack" method with the "angle correction" dance:

The amount of wasted space is no longer proportional to the length of the room.
Instead, the wasted space grows much, much slower.

Mathematically, if the room has a side length of $x$ , the wasted space is roughly $x^{3/5}$ .

Old way: Wasted space was roughly $x$ (a straight line).
New way: Wasted space is roughly $x^{0.6}$ (a curve that flattens out).

For a massive room, this difference is enormous. It means you can cover a giant square floor with unit tiles and leave behind a tiny fraction of empty space compared to previous methods.

Summary

The paper doesn't just say "tilt the tiles." It provides a precise recipe for how much to tilt them and when to switch the tilt direction so that the errors cancel each other out. This allows us to pack a large square with unit squares more efficiently than ever before, leaving behind the smallest amount of "wasted" floor space mathematically possible with this approach.

Technical Summary: Optimally Packing a Large Square by Unit Squares

Problem Statement
The paper addresses the problem of packing a large square $S(x)$ of side length $x$ with unit squares having disjoint interiors. The objective is to minimize the wasted space $W(x)$ , defined as the area of $S(x)$ not covered by the unit squares. While $W(x) = 0$ when $x$ is an integer, the problem becomes non-trivial when $x$ is not an integer. A naive alignment of unit squares parallel to the sides of $S(x)$ yields a wasted space of $W(x) = O(x\{x\})$ , which simplifies to $O(x)$ if the fractional part $\{x\}$ is bounded away from zero. The central challenge is to determine the optimal asymptotic growth rate of $W(x)$ by allowing unit squares to be oriented at slight angles.

Historical Context and Prior Bounds
The paper situates its contribution within a timeline of established bounds:

Lower Bound: Roth and Vaughan (1978) proved that $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$ , establishing that the bound cannot be better than $\Omega(x^{1/2})$ .
Upper Bounds:
- Erdős and Graham (1975) showed $W(x) = O(x^{7/11})$ .
- Montgomery improved this to $O(x^{(3-\sqrt{3})/2})$ .
- Chung and Graham (2009) further refined the bound to $O(x^{(3+\sqrt{2})/7} \log x)$ .
- In 2020, Chung and Graham claimed a bound of $O(x^{3/5})$ , but the paper notes this result contained an error, reverting the best known bound to the 2009 result until the current work.

Methodology
The paper proposes a new algorithm to achieve the $O(x^{3/5})$ bound, correcting the error in the 2020 claim. The proof proceeds in four distinct stages:

Initial Trivial Packing: The square $S(x)$ is first packed trivially with unit squares aligned parallel to the sides, leaving two narrow rectangular regions of width $h$ . One such rectangle, $R$ , is selected for further processing.
Stacking with Inclination: Rectangle $R$ is packed using "stacks" of $n$ unit squares inclined at an angle $\theta$ . These stacks touch both the vertical and inclined walls of the rectangle. This process leaves behind a trapezoidal region $T$ at the ends. The angle $\theta$ is chosen such that $\theta \asymp h^{-1/2}$ .
Two-Stage Trapezoidal Packing: The core of the algorithm involves filling the trapezoid $T$ $T$ using two complementary sub-algorithms:
- Algorithm 1: Packs $T$ using near-horizontal and vertical stacks of decreasing length ( $m, m-1, \dots$ ). This algorithm introduces a specific angular shift, changing the inclination from $\psi$ at the bottom to $\phi$ at the top, where the difference $\phi - \psi \approx \theta$ .
- Algorithm 2: Designed to "undo" the angular shift introduced by Algorithm 1. It begins where Algorithm 1 ends, packing stacks of length $m+1$ and $m$ to restore the geometry required to restart Algorithm 1.
- Iterative Application: These two algorithms are applied back-to-back in a cycle. The paper demonstrates that the parameters ( $\phi, \psi, \theta, m$ ) can be fixed or adjusted such that the error terms ( $\epsilon, \epsilon'$ ) do not accumulate destructively over iterations.
Parameter Optimization: The width $w$ of the trapezoid $T$ and the number of iterations are optimized. The algorithm is applied $\approx \sqrt{h}$ times to cover the trapezoid.

Key Results and Analysis
The paper derives the total wasted space $W(x)$ by summing the waste from the vertical stacks and the waste generated within the trapezoidal regions:

Waste from Stacks: Packing the $O(x)$ vertical stacks with inclination $\theta$ generates waste proportional to $O(x\theta)$ .
Waste from Trapezoids: The iterative application of the two packing algorithms on the trapezoid $T$ generates a total waste of $O(h^{3/4})$ .
Optimization: The total waste is bounded by $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$ . By equating the two terms ( $x h^{-1/2} \sim h^{3/4}$ ), the optimal choice is $h \sim x^{4/5}$ .

Substituting $h = x^{4/5}$ into the bound yields:
$W(x) = O(x^{3/5})$

Significance and Claims
The paper claims to rigorously prove that the wasted space in packing a large square by unit squares is bounded by $O(x^{3/5})$ . This result validates the claim previously made by Chung and Graham in 2020, which had been retracted due to an error. The significance lies in providing a corrected proof for this specific asymptotic bound, improving upon the previous best-known bound of $O(x^{(3+\sqrt{2})/7} \log x)$ . The authors emphasize that this is achieved through a specific constructive algorithm involving the interplay of two packing strategies that manage angular discrepancies and error accumulation within trapezoidal sub-regions. The paper does not propose further applications or future implications beyond establishing this specific upper bound.