Why does this figure pack so poorly?

Two mathematicians have proven a long-standing conjecture that is a step toward finding the worst possible shape for packing shapes into the plane.

For centuries, mathematicians have suspected that hexagonal tiles are the best way to fill space. By that, they mean that if you want to divide a large area into tiles of equal size and minimize the perimeter of each tile, hexagons are the best. In 1999, Thomas Hales of the University of Pittsburgh finally proved it. They are better than squares, triangles, or any other alternative.

But many shapes can't be tiled without gaps. Circles, for example, obviously can't. With the best possible layout, a hexagonal circle shape, you'll fill almost 90.69% of the plane.

In the 1920s, mathematicians asked themselves: Which shape packs the worst? In other words, which shape causes you to leave the biggest gaps, even if you pack it in the best possible way? The new paper by Hales and his former graduate student Kundinya Wajha, now an engineer at Intel, marks a major breakthrough in this quest.

Determining the worst shape requires following a few rules. It's easy to come up with arbitrarily bad shapes that contain holes or indentations inside, like these hollow squares:

Mathematically, they're not all that interesting, because by making the edges thinner and thinner, you can easily get a shape that makes arbitrarily large parts of the space empty. But if you add the requirement that the shape be convex—that is, that given any two points in the shape, the line segment connecting them be inside the shape—then such hollow shapes become forbidden, and the problem becomes more intriguing.

Mathematicians are interested in shapes that have one additional constraint: central symmetry. Without it, the worst known shape is the seven-sided regular heptagon (space occupancy is about 89.27%), although mathematicians have not yet been able to prove that it is the worst. Hales and Wajha have been working on a more limited and therefore simpler question: what is the worst-packed shape that is both convex and centrally symmetric?

At first, mathematicians thought it was a circle. Then, in 1934, a German mathematician named Karl Reinhardt discovered something worse: an octagon with rounded edges. If you draw arcs at the corners using hyperbolas, the total coverage is about 90.24%. The difference between that and the 90.69% of a circle is tiny, but mathematically it's very important.

Reinhardt couldn’t prove that his rounded octagon was the worst possible shape. And no one else could either. “I always thought Reinhardt was probably right, but there was no theory to solve the problem,” says Henry Cohn, a mathematician at Microsoft Research known for his work on sphere packing in higher dimensions. “Will we ever see a proof? Probably not in my lifetime.”

Such evidence has not yet emerged. But Hales and Wajhi's May paper confirmed a crucial intermediate hypothesis.

Even more than his hexagon result, Hales is best known for his proof in the late 1990s of Johannes Kepler's 17th-century conjecture about the best way to pack spheres in three dimensions (sometimes called the orange-packing problem, because it resembles the fruit pyramids at the market). Because the proof relied on computer calculations, it took him years after its publication to convince the mathematical community of its validity.

In 2007, while on sabbatical in Vietnam, Hales was putting the finishing touches on his proof of Kepler's conjecture when he switched his focus from the best possible packings to the worst. But progress was slow.

The worst is yet to come, of course.

The worst-packing problem asks you to find a shape whose highest packing density covers the smallest fraction of the plane. These kinds of constraints belong to a class of problems called minimax problems, which are inherently tricky. The standard way to solve these problems is with a set of techniques called the calculus of variations. Reinhardt used this in his packing problem to try to prove the optimality of rounded octagons. The rounded points are traced using hyperbolas, curves that shave off as much area as possible without changing the packing pattern. This meant that the expected solution would involve not just curves, but a mixture of curves and straight edges.

Hales tried to continue what Reinhardt had started, but soon realized that the calculus of variations would not be enough to solve the problem. The main problem, he noticed, was that while these methods were good at finding optimal curves that fit a set of desired parameters, the solution was not exactly a curve. If the solution were as Reinhardt had suggested, it would be a more complex structure that combined curves and straight edges.

In 2017, after a decade of continuous work, Hales published preprintin which he proposed a proof plan of sorts. He proposed using a branch of mathematics called optimal control theory, which he thought was better suited to studying flip structures. For other mathematicians, an intractable problem suddenly seemed doable. “I was very impressed by the creativity,” says Cohn. “But on the other hand, I thought it would take a lot of work to actually pull this off.”

Shortly after Hales outlined his plan, Wajha arrived in Pittsburgh, feeling a little lost, like many students at the start of graduate school. He hoped to study formal methods—techniques used to verify software and hardware—and attended conferences around the city, looking for a suitable problem to focus on. At one, he learned about finding a better packer, and found the trickiness of the problem intriguing. He was even more intrigued when, that same day, he found a preprint by Hales that proposed a radically new approach to the problem.

They met the following week. I said, “If it’s that easy, why don’t you do it?” Wajha recalls. Hales replied that together they could probably do it in about six months. Wajha agreed. “It’s never that easy,” he said recently.

To prove that the rounded octagon is the worst-packing shape, Hales and Wajha had to rule out all other possible shapes. Even with constraints like central symmetry and convexity, they were faced with a problem with an infinite number of potential answers, many of which exhibit strange behavior that makes them appear to be viable solutions even though they are not. For example, there are candidate shapes that can switch from straight lines to curves infinitely often, called “dangling” solutions. It may seem counterintuitive, but such shapes may be better than a circle. Maybe they’re even better than Reinhardt’s rounded octagon?

Hales’s massive proof of Kepler’s conjecture used a computer approach that involved eliminating an almost infinite number of possible packings by brute force. The work was considered groundbreaking—and somewhat controversial at the time, because reviewers found the programs’ results too difficult to check. Hales had hoped to use similar methods to find the worst-case form, but he was hampered by the sheer number of “extra” solutions. “If everything changes infinitely many times, it’s not going to be easy for a computer to handle,” Hales says.

Getting rid of these and other puzzling structures required finding creative ways to eliminate them. They tried simplifying the problem by introducing new symmetry constraints, then returning to the original problem. “As in physics, there’s an idea in mathematics that if you have symmetry, you have conservation laws,” Hales says. These laws can help eliminate some of the structures.

Still, new opportunities kept popping up. “When I started tackling this problem, I knew it was hard, but when I tried to simplify it, there was always more hidden structure,” Wajha says. “And it was always six months away from being finished.” Five years passed, and he was about to graduate. He was planning to get married and move to the West Coast. “We couldn’t know for sure if this problem would fight back and decide to stay unsolved for another century.” The thought of leaving behind an unfinished proof was tantalizing, but he was running out of options. He graduated in August 2022, worked briefly at an AI startup, then took a job at Intel formally reviewing processors, returning to his intended specialty.

The following spring, Wajha returned to Pittsburgh for his graduation ceremony. He and Hales lamented that they had laid out so many new ideas and methods without producing a solid theorem. A week later, Hales had an epiphany: They were close to proving a related conjecture, posed by Kurt Mahler, a mathematician working independently of Reinhardt, in 1946. “I’d always kind of dismissed Mahler because he was doing the same thing Reinhardt did a few years later,” Hales says. But Mahler made an important observation by breaking the problem into two steps. His first conjecture was that the answer to the problem was a smoothed-out polygon, with straight edges and corners rounded by hyperbolas. His second conjecture matched Reinhardt’s—that a rounded octagon was the worst possible shape. The pair hadn't yet reached Mahler's first move, but Hales realized they were close. He asked Wajha for a month to think it over.

A month passed, and the two began exchanging emails—uncovering more structures and rejecting them, admitting to more doubts and fatigue. The month stretched into a year. Finally, Hales sent Wajha a message. Mahler’s first hunch “was back on the horizon. I’m pretty sure I’ve proved it.”

Their proof of Mahler’s first conjecture — six years, not six months — is a 260-page study of the topic that details a dizzying array of candidate structures and uses a much larger range of theory than even Hales had originally envisaged. The paper has not yet been peer-reviewed, but mathematicians who have informally looked at it, including Kohn and Greg Kuperberg, a mathematician at the University of California, Davis, said they were confident in the result, given Hales’s reputation for being very cautious about difficult proofs.

But, Kuperberg added, “they haven’t really crossed the finish line.” Sometimes problems languish for decades, even after theories have been developed and intermediate steps have been achieved. After all, Hales’s proof of Kepler’s conjecture relied on approaches developed by the Hungarian mathematician László Fejes Tóth 50 years earlier. “Maybe all the ideas for completing Reinhardt’s work are already there. Maybe not,” Hales says. “We’ll leave that as a question mark.”