Why Is This Shape So Terrible to Pack?
Nico Roper for Quanta Magazine
Introduction
For centuries, mathematicians suspected that hexagonal tiles are the best possible way to fill space. By this they mean that if you want to subdivide a large area into tiles of equal size while minimizing the perimeter of each tile, you can’t do any better than hexagons. In 1999, Thomas Hales of the University of Pittsburgh finally proved it. They’re better than squares, triangles, or any other alternative.
But many shapes can’t be tiled without leaving gaps. Circles, for example, obviously can’t. With the best possible formation, a hexagonal-shaped circle packing, you’ll fill nearly 90.69% of the plane.
Mark Belan for Quanta Magazine
In the 1920s, mathematicians began wondering: What’s the worst shape to pack? In other words, what shape forces you to leave the largest gaps, even if you pack it in the best possible way? A new paper by Hales and his former graduate student Koundinya Vajjha, now an engineer at Intel, marks a major breakthrough in the search.
Defining a worst shape requires a few rules. It’s straightforward to come up with arbitrarily bad shapes that contain holes or inward dips, like these hollowed-out squares:
They aren’t all that mathematically interesting, because by making the edges ever thinner, you can easily come up with a shape that forces an arbitrarily large fraction of space to be empty. But if you add in the requirement that the shape be convex — meaning that if you choose any two points in the shape, the line segment connecting them will be contained within the shape — then hollow shapes like this are forbidden, and things become 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 filled: about 89.27%), though mathematicians are nowhere close to being able to prove it’s the worst. Hales and Vajjha worked on the more constrained, and therefore simpler, question: What’s the shape with the worst packing that is both convex and centrally symmetric?
Mathematicians initially believed that it’s a circle. Then, in 1934, a German mathematician named Karl Reinhardt found something worse: an octagon with rounded edges. When those arcs in the corners are drawn using hyperbolas, the total coverage is about 90.24%. The difference between this and the circle’s 90.69% is tiny, but it’s mathematically vital.
Reinhardt couldn’t prove that his rounded octagon was the very worst such shape. Neither could anybody else. “I’ve always believed that Reinhardt is probably right but that the theory was not there to attack this problem,” said Henry Cohn, a mathematician at Microsoft Research known for his work on packing spheres in higher dimensions. “Were we ever going to see a proof? Probably not in my lifetime.”
Such a proof has not yet come. But Hales and Vajjha’s May paper proved a crucial intermediate conjecture.
Even more than for his result on hexagons, Hales is famous for his proof, in the late 1990s, of a 17th-century conjecture by Johannes Kepler about the best way to pack spheres in three dimensions (sometimes called the orange-stacking problem, because it evokes piles of fruit in a market). Because it relied on computer calculations, it took him years after the proof was first published to convince the mathematical community of its validity.
In 2007, while on sabbatical in Vietnam, Hales was tying up some remaining loose ends in his proof of Kepler’s conjecture when he turned his attention from the best possible packings to the worst. But progress was slow.
The Worst is Yet to Come
The worst-packing problem asks for a shape whose greatest packing density has the smallest value. These kinds of constraints fall into a class of problems called minimax problems, which are inherently tricky. A standard way to approach them is through a set of techniques called the calculus of variations. Reinhardt used it on his packing problem to attempt to prove the optimality of the rounded octagons. The rounded points are traced with hyperbolas — curves that shave off as much area as possible without messing with the packing. That meant the expected solution would involve not just curves, but a mix of curves and straight edges.
Hales tried picking up where Reinhardt had left off, but he soon realized that the calculus of variations wasn’t going to be enough to solve the problem. The core issue, he observed, was that while the techniques are good for finding optimal curves to fit a set of desired parameters, the solution he was looking for was not a curve exactly. If the solution was as Reinhardt had conjectured, it would be a more complicated structure that mixed together curves and straight edges.
Decades ago, Thomas Hales became famous for proving things about the best possible packings. Now he’s turned his attention to the worst ones.
Joe Appel
In 2017, after a decade of on-and-off work, Hales posted a preprint that offered a sort of blueprint for a proof. He proposed using a branch of mathematics called optimal control theory, which would be better suited, he believed, to exploring flip-flopping structures. To other mathematicians, an unapproachable problem had suddenly become feasible. “I was very impressed with the creativity,” Cohn said. “But on the other hand, I thought, it’ll take so much work to actually pull it off.”
Not long after Hales set out his blueprint, Vajjha arrived in Pittsburgh feeling a little lost, as many students do early on in graduate school. He was hoping to study formal methods — techniques used to verify software and hardware — and was attending all sorts of talks around town in search of the right problem to focus on. In one of them, he learned about the search for the best worst packer, and he found the deceptive trickiness of the problem intriguing. He was even more interested later that day when he found Hales’ preprint, which proposed a radically new approach to the problem.
The two met the following week. “I told him, ‘If this is so easy, why don’t you just do it?’” Vajjha recalled. Hales replied that they could probably tackle it together in about six months. Vajjha agreed. “Things are never that easy,” he recently said.
In order to prove that the rounded octagon was the shape with the worst packing, Hales and Vajjha effectively had to rule out every other possible shape. Even with constraints like central symmetry and convexity, they were staring down a problem with infinite potential answers, many of which exhibit strange behaviors that can make them appear to be viable solutions, when in fact they aren’t valid. There were candidate shapes, for example, that would flip-flop between straight lines and curves an infinite number of times, called “chattering” solutions. That might sound paradoxical, but such shapes might do better than a circle. Could they even be better than Reinhardt’s rounded octagon?
Hales’ voluminous proof of Kepler’s conjecture had used a computer-assisted approach that involved ruling out a nearly endless array of possible packings with brute force. It was considered pioneering — and, at the time, a bit controversial, as reviewers found the programs hard to verify. Hales hoped to use similar methods to find the worst shape, but potential chattering solutions presented a roadblock. “If things are switching around infinitely many times, then it’s not going to be easy to do on a computer,” Hales said.
Doing away with those and other obscure structures required finding creative ways to rule them out. They tried simplifying the problem by introducing new symmetric constraints and then working their way back up to the original problem. “Just as in physics, there’s this idea in mathematics where if you have symmetry you also have conservation laws,” Hales said. Those laws could help rule some of the structures out.
Koundinya Vajjha, now an engineer at Intel, spent years working on proving that rounded octagons are the worst possible shape to pack.
Vihasi Jani
Still, new possibilities kept coming up. “I knew this problem was hard going into it, but there was always more structure that you could unravel,” Vajjha said. “It was always the case that there was just six months more.” Five years passed, and he was overdue for a degree. He was planning to get married and move to the West Coast. “We could never know when this problem would fight back and stay unresolved for another century.” The idea of leaving an incomplete proof behind was agonizing, but he was simply running out of rope. He graduated in August 2022, briefly worked at an AI startup, and then took a job at Intel formally verifying CPUs, returning to his intended field of study.
Vajjha returned to Pittsburgh the following spring for his graduation ceremony. He and Hales lamented that they had managed to detail many new ideas and methods, but without producing a solid theorem. A week later, Hales had a realization: They had come close to proving a related conjecture made by Kurt Mahler, a mathematician working independently of Reinhardt, in 1946. “I had always sort of dismissed Mahler because he was doing the same thing as Reinhardt, only years later,” Hales said. But Mahler had made an important observation by breaking the problem down into two steps. His first conjecture was that the answer is a smoothed polygon with straight edges and corners rounded with hyperbolas. His second was identical to Reinhardt’s — that a rounded octagon is the worst possible shape. The pair hadn’t quite reached Mahler’s first step, but Hales recognized that they were close. He asked Vajjha for a month to think it over.
That month came and went, and the two began trading emails — revealing more structures and dismissing them, admitting more doubts and exhaustion. A month stretched to a year. Then, finally, Hales sent Vajjha a message. Mahler’s first conjecture, “is back on the horizon. I’m pretty sure I’ve proven it.”
Their proof of Mahler’s first conjecture — after six years, not six months — is a 260-page exploration of the subject, detailing a dizzying array of candidate structures and using a far greater range of theory than even Hales initially imagined would be necessary. The work has yet to be peer reviewed, but mathematicians who have informally reviewed the work, including Cohn and Greg Kuperberg, a mathematician at the University of California, Davis, said they had confidence in the result, given Hales’ reputation for great care with complex proofs.
However, Kuperberg added, “they didn’t really cross the finish line.” Sometimes problems languish for decades, even when the theories are developed and intermediate steps achieved. After all, Hales’ proof of Kepler’s conjecture relied on approaches developed by the Hungarian mathematician László Fejes Tóth 50 years earlier. “Perhaps all the ideas are in place to complete Reinhardt. Perhaps not,” Hales said. “We leave this as a question mark.”
