Square packing is a serious problem

Added: 2026-05-09

[00:00:02]Sphere packing has been an ongoing topic in mathematics for 400 years and we only started making good progress about 100 years ago. For two dimensions, circles naturally arranged themselves in hexagons and in 1773 Lrange proved that this is indeed the most optimal lice packing. The caveat here is the lattice because it means a symmetric repeating pattern. When you have just a few circles, some weird packings turn out to be more efficient.

[00:00:36]Like with 13 circles, this fits optimally inside a square. And by the way, when we say optimal in this video, we mean that the wasted area between our shapes is minimized.

[00:00:50]It was only in 1942 that lazlfest tooth finally proved that hexagonal arrangement is the most optimal packing when we have many circles even when non-lises are considered for three dimensions. The optimal packing of spheres is known as Kepler conjecture and it was solved only with computer aid in 1998.

[00:01:15]Most recently, Marina Vazovska received a Fields Medal for finding optimal packings in dimensions 8 and 24.

[00:01:24]So, spheres and circles are pretty well understood. But the next simple shape, a square, is still very much puzzling.

[00:01:32]What we want is given nunit squares, fit them in the smallest possible square.

[00:01:40]Solutions for less than 10 are pretty simple and proven optimal. And we will see how to prove most of them in a second.

[00:01:47]But with 11, things start to get weird.

[00:01:50]This is the best solution we know. And nothing better was found since 1979.

[00:01:58]Look at the weird tiny gaps.

[00:02:03]And 18 is quite special. We know these four different packings which end up giving exact same packing size.

[00:02:12]How bizarre is that?

[00:02:15]To prove that something like this is optimal, we can use the concept of unavoidable points. These are special points inside a square such that any unit square inside must contain at least one of these points.

[00:02:31]It starts simple. Assume that a unit square has its center somewhere in the unit corner. then it must necessarily contain the point one 1. It's pretty intuitive, but try proving it rigorously.

[00:02:47]Next, we look at the strip between 1 and 1 + 1 over square<unk> 2. No matter how you place the square, it will contain either 1 1 or 1 + 1 over <unk>2 1. You can prove it by contradiction.

[00:03:05]Assume that a square has both of these points on the boundary. Then the square necessarily touches the x aces.

[00:03:14]You can proceed similarly and get a set of unavoidable points.

[00:03:18]Side length three is when we get seven unavoidable points for the first time.

[00:03:23]It means that 8 unit squares can fit here in theory and it would be the optimal packing. And the most trivial packing works here as one such packing.

[00:03:34]But most of the times unavoidable points give us a lower bound because finding a packing that works is not easy. Like here for side length 6 <unk>2 - 4 gives us 18 such unavoidable points.

[00:03:50]But we do not know a packing that works for this size. The best one we know is this. And the square has side length 3 + 4 square<unk> of 2 over 3. So for 19 squares, we have upper and lower bounds.

[00:04:08]All packings that are not proven optimal are quite far away from the best lower bound we know.

[00:04:14]And for upper bounds, Paul Erdos made a major breakthrough in 1975.

[00:04:21]He offers a construction where we tile most of the square perfectly with no gaps and the remaining strips are tiled with tilted squares and then we try to fill the remaining trapezoids with perfect packing as well and then with some tilted squares again.

[00:04:39]Then you can choose sizes so that wasted area is minimized and actually show that wasted area grows as side length to the power 7 over 11.

[00:04:50]What it means in particular is that the percent of wasted area tends to zero while the density of honeycomb packing of circles converges to pi over 2<unk>3 or about 91%.

[00:05:04]This becomes the best known packing for very very large squares.

[00:05:09]But for most squares, including the case of 11, there are still no proofs that existing packings are indeed the optimal ones.

[00:05:19]This problem needs more people involved and this website has an upto-date list of best known packings for you to explore. You can even open any solution and move squares around to try making it more optimal.

[00:05:34]Feel free to contribute your ideas in the comments below.