What are you looking for?
Mathematicians Complete Quest to Build ‘Spherical Cubes’
Is it possible to fill space “cubically” with shapes that act like spheres? A proof at the intersection of geometry and theoretical computer science says yes.
DVDP for Quanta Magazine
February 10, 2023
complexitycomputational complexitycomputer sciencecrystalsgeometrymathematicsunique games conjectureAll topics
Introduction
In the fourth century, the Greek mathematician Pappus of Alexandria praised bees for their “geometrical forethought.” The hexagonal structure of their honeycomb seemed like the optimal way to partition two-dimensional space into cells of equal area and minimal perimeter — allowing the insects to cut down on how much wax they needed to produce, and to spend less time and energy building their hive.
Or so Pappus and others hypothesized. For millennia, nobody could prove that hexagons were optimal — until finally, in 1999, the mathematician Thomas Hales showed that no other shape could do better. Today, mathematicians still don’t know which shapes can tile three or more dimensions with the smallest possible surface area.
This “foam” problem has turned out to have wide-ranging applications — for physicists studying the behavior of soap bubbles (or foams) and chemists analyzing the structure of crystals, for mathematicians exploring sphere-packing arrangements and statisticians developing effective data-processing techniques.
In the mid-2000s, a particular formulation of the foam problem also caught the eye of theoretical computer scientists, who discovered, to their surprise, that it was deeply connected to an important open problem in their field. They were able to use that connection to find a new high-dimensional shape of minimal surface area.
“I love this back-and-forth,” said Assaf Naor of Princeton University. “Some old mathematics becomes relevant to computer science; computer science pays back and solves the question in mathematics. It’s very nice when this happens.”
But that shape, though optimal, was missing something important: a geometric foundation. Because its existence had been proved using techniques from computer science, its actual geometry was hard to grasp. That’s what Naor, along with Oded Regev, a computer scientist at the Courant Institute at New York University, set out to correct in a proof posted online last month.
“It’s a very nice end to the story,” Regev said.
Cubical Foams
Mathematicians have considered other versions of the foam problem — including what happens if you’re only allowed to partition space according to what’s called the integer lattice. In that version of the problem, you take a square array of evenly spaced points (each 1 unit apart) and make each of those points the center of a shape. The “cubical” foam problem asks what the minimal surface area will be when you’re required to tile space in this way.
Researchers were initially interested in imposing this restriction in order to understand properties of topological spaces called manifolds. But the question took on a life of its own, becoming relevant in data analysis and other applications.
Share this article
Newsletter
Get Quanta Magazine delivered to your inbox
Introduction
It’s also geometrically interesting, because it changes what “optimal” might mean. In two dimensions, for instance, regular hexagons can no longer tile the plane if they can only be shifted by integer amounts in the horizontal and vertical directions. (You have to move them by irrational amounts in one of the two directions.)
Squares can. But is that the best that can be done? As the mathematician Jaigyoung Choe discovered in 1989, the answer is no. The optimal shape is instead a hexagon that has been squashed in one direction and elongated in another. (The perimeter of such a hexagon is approximately 3.86 when its area is 1 — beating out the square’s perimeter of 4.)
These differences might seem trivial, but they get much larger in higher dimensions.
Among all shapes of a given volume, the one that minimizes surface area is the sphere. As n, the number of dimensions, grows, the sphere’s surface area increases in proportion to the square root of n.
But spheres can’t tile a space without leaving gaps. On the other hand, an n-dimensional cube of volume 1 can. The catch is that its surface area is 2n, growing in direct proportion to its dimension. A 10,000-dimensional cube of volume 1 has a surface area of 20,000 — much bigger than 400, the approximate surface area of a 10,000-dimensional sphere.
And so researchers wondered if they could find a “spherical cube” — a shape that tiles n-dimensional space, like a cube, but whose surface area grows slowly, like a sphere’s.
It seemed unlikely. “If you want your bubble to exactly fill up space and be centered on this cubical grid, it’s hard to think about what you would use except for a cubical bubble,” said Ryan O’Donnell, a theoretical computer scientist at Carnegie Mellon University. “It really seems that the cube should be the best.”
We now know that it isn’t.
The Hardness of Hard Problems
For decades, the cubical foam problem went relatively unexplored in higher dimensions. The first researchers to make progress on it came not from the realm of geometry but from theoretical computer science. They came across it by chance, while in search of a way to prove a central statement in their field known as the unique games conjecture. “The unique games conjecture,” Regev said, “is what I view currently as the biggest open question in theoretical computer science.”
Proposed in 2002 by Subhash Khot, a graduate student at the time, the conjecture posits that if a particular problem — one that involves assigning colors to the nodes of a network — can’t be solved exactly, then finding even an approximate solution is very hard. If true, the conjecture would allow researchers to understand the complexity of a vast assortment of other computational tasks in one fell swoop.
Introduction
Computer scientists often classify tasks based on whether they can be solved with an efficient algorithm, or whether they are instead “NP-hard” (meaning they can’t be efficiently solved as the size of the problem grows, so long as a widely believed but unproved conjecture about computational complexity is true). For instance, the traveling salesperson problem, which asks for the shortest path needed to visit every city in a network only once, is NP-hard. So is determining whether a graph — a collection of vertices connected by edges — can be labeled with at most three colors so that any two connected vertices have different colors.
It turns out that it’s NP-hard to find even an approximate solution to many of these tasks. Say you want to label the vertices of a graph with different colors in a way that satisfies some list of constraints. If it’s NP-hard to satisfy all of those constraints, what about trying to fulfill just 90% of them, or 75%, or 50%? Below some threshold, it might be possible to come up with an efficient algorithm, but above that threshold, the problem becomes NP-hard.
For decades, computer scientists have worked to nail down thresholds for different optimization problems of interest. But some questions evade this kind of description. While an algorithm might guarantee 80% of the best solution, it might be NP-hard to achieve 95% of the best solution, leaving unsettled the question of where exactly between 80% and 95% the problem tips into NP-hard territory.
The unique games conjecture, or UGC, offers a way to immediately pinpoint the answer. It makes a statement that at first seems more limited: that it is NP-hard to tell the difference between a graph for which you can satisfy almost all of a certain set of coloring constraints (say, more than 99%) and a graph for which you can satisfy barely any (say, less than 1%).
But shortly after the UGC was proposed in 2002, researchers showed that if the conjecture is true, then you can easily compute the hardness threshold for any constraint satisfaction problem. (This is because the UGC also implies that a known algorithm achieves the best possible approximation for all of these problems.) “It was precisely the linchpin for all these optimization problems,” O’Donnell said.
And so theoretical computer scientists set out to prove the UGC — a task that ultimately led some of them to discover spherical cubes.
Making Hard Problems Harder
In 2005, O’Donnell was working at Microsoft Research. He and two colleagues — Uriel Feige, now at the Weizmann Institute of Science, and Guy Kindler, now at the Hebrew University of Jerusalem — teamed up to tackle the UGC.
They had a vague idea of how they wanted to proceed. They would start with a question about graphs — one that’s very similar to the UGC. The so-called maximum cut (“max-cut”) problem asks, when given a graph, how to partition its vertices into two sets (or colors) so that the number of edges connecting those sets is as large as possible. (You can think of max cut as a question about the best way to color a graph with two colors, so that as few edges as possible connect vertices of the same color.)
It looks like an amoeba. It doesn’t look like what you would expect, a nice tiling body.
Oded Regev, Courant Institute
If the UGC is true, it would imply that, given some random graph, an efficient approximation algorithm can only get within about 87% of the true max cut of that graph. Doing any better would be NP-hard.
Feige, Kindler and O’Donnell instead wanted to go in the opposite direction: They hoped to show that max cut is hard to approximate, and then use that to prove the UGC. Their plan relied on the strength of a technique called parallel repetition — a clever strategy that makes hard problems harder.
Say you know that it’s NP-hard to distinguish between a problem you can solve and one you can mostly solve. Parallel repetition enables you to build on that to show a much stronger hardness result: that it’s also NP-hard to distinguish between a problem you can solve and one you can barely solve at all. “This nonintuitive, deep phenomenon … is in the guts of a lot of computer science today,” Naor said.
But there’s a catch. Parallel repetition doesn’t always amplify a problem’s hardness as much as computer scientists want it to. In particular, there are aspects of the max-cut problem that “create a big headache for parallel repetition,” Regev said.
Feige, Kindler and O’Donnell focused on showing that parallel repetition could work despite the headaches. “This is a really complicated thing to analyze,” said Dana Moshkovitz, a theoretical computer scientist at the University of Texas, Austin. “But this seemed tantalizingly close. Parallel repetition seemed like it would [help make] this connection from max cut to unique games.”
As a warmup, the researchers tried to understand parallel repetition for a simple case of max cut, what Moshkovitz called “the stupidest max cut.” Consider an odd number of vertices connected by edges to form a circle, or “odd cycle.” You want to label each vertex with one of two colors so that no pair of adjacent vertices have the same color. In this case, that’s impossible: One edge will always connect vertices of the same color. You have to delete that edge, “breaking” the odd cycle, to get your graph to satisfy the problem’s constraint. Ultimately, you want to minimize the total fraction of edges you need to delete to properly color your graph.
Parallel repetition allows you to consider a high-dimensional version of this problem — one in which you have to break all the odd cycles that appear. Feige, Kindler and O’Donnell needed to show that as the number of dimensions gets very large, you have to delete a very large fraction of edges to break all the odd cycles. If that was true, it would mean parallel repetition could effectively amplify the hardness of this “stupid max-cut” problem.
That’s when the team discovered a curious coincidence: There was a geometric way to interpret whether parallel repetition would work the way they hoped it would. The secret lay in the surface area of cubical foams.
From Lemons to Lemonade
Their problem, rewritten in the language of foams, boiled down to showing that spherical cubes cannot exist — that it’s impossible to partition high-dimensional space along the integer lattice into cells with surface area much smaller than that of the cube. (A larger surface area corresponds to needing to delete more “bad” edges in the odd-cycles graph, as the computer scientists hoped to show.)
“We were like, oh, what a weird geometry problem, but that’s probably true, right?” O’Donnell said. “We really needed that to be the true answer.” But he, Feige and Kindler couldn’t prove it. So in 2007, they published a paper outlining how they planned to use this problem to help attack the UGC.
Soon enough, their hopes were dashed.
Ran Raz, a theoretical computer scientist at Princeton who had already proved several major results about parallel repetition, was intrigued by their paper. He decided to analyze parallel repetition for the odd-cycle problem, in part because of the connection to geometry that Feige, Kindler and O’Donnell had uncovered.
Raz didn’t start with the foam problem but attacked the computer science version of the question head-on. He showed that you can get away with deleting far fewer edges to break all the odd cycles in a graph. In other words, parallel repetition can’t sufficiently amplify the hardness of this max-cut problem. “The parameters that one gets from parallel repetition exactly, exactly fall short of giving this,” Moshkovitz said.
“Our plan to use parallel repetition to show the hardness of unique games didn’t even work in the simplest case,” O’Donnell said. “This kind of broke the whole plan.”
Although disappointing, Raz’s result also hinted at the existence of spherical cubes: shapes capable of tiling n-dimensional space with a surface area that scaled in proportion to the square root of n. “We were like, well, let’s make lemonade out of lemons and take this disappointing technical result about parallel repetition and discrete graphs, and turn it into a neat, interesting result in geometry,” O’Donnell said.
He and Kindler, in collaboration with the computer scientists Anup Rao and Avi Wigderson, pored over Raz’s proof until they’d learned its techniques well enough to translate them to the foam problem. In 2008, they showed that spherical cubes are indeed possible.
“It’s a nice way to reason about the problem,” said Mark Braverman of Princeton. “It’s beautiful.”
And it raised questions on the geometry side of the story. Because they’d used Raz’s work on parallel repetition to construct their tiling shape, Kindler, O’Donnell, Rao and Wigderson ended up with something ugly and Frankenstein-like. The tile was messy and full of indentations. In mathematical terms, it was not convex. While this worked for their purposes, the spherical cube lacked properties that mathematicians prefer — properties that make a shape more concrete, easier to define and study, and more suitable for potential applications.
“There’s something very unsatisfying about their construction,” Regev said. “It looks like an amoeba. It doesn’t look like what you would expect, a nice tiling body.”
That’s what he and Naor set out to find.
Breaking Free of the Cage
From the outset, Naor and Regev realized they’d have to start from scratch. “Partly because convex bodies are so restrictive, none of the previous techniques had any chance of working,” said Dor Minzer, a theoretical computer scientist at the Massachusetts Institute of Technology.
In fact, it was entirely plausible that convexity would be too restrictive — that a convex spherical cube simply does not exist.
But last month, Naor and Regev proved that you can partition n-dimensional space along integer coordinates with a convex shape whose surface area is pretty close to that of the sphere. And they did it entirely geometrically — returning the problem to its mathematical roots.
They first had to get around a major obstacle. The cubical foam problem requires that each tile be centered at integer coordinates. But in the integer lattice, there are very short distances between some points — and those short distances cause trouble.
Consider a point in the two-dimensional grid. It’s located 1 unit away from its nearest points in the horizontal and vertical directions. But in the diagonal direction, the nearest point is 2–√ units away — a discrepancy that gets worse in larger spaces. In the n-dimensional integer lattice, the nearest points are still 1 unit away, but those “diagonal” points are now n−−√ units away. In, say, 10,000 dimensions, this means that the closest “diagonal” neighbor to any point is 100 units away even though there are 10,000 other points (one in each direction) that are only 1 unit away.
Introduction
In other lattices, those two kinds of distances grow in proportion to one another. Mathematicians have known for decades how to tile such lattices with convex shapes of minimal surface area.
But in the integer lattice, the shortest distances will always be stuck at 1. This gets in the way of constructing a nice-looking tile of optimal surface area. “They kind of put you in this cage,” Regev said. “They make everything very tight around you.”
So Naor and Regev instead considered a slice of the full n-dimensional space. They carefully chose this subspace so that it would still be rich in integer points, but none of those points would be too close together.
In other words, the subspace they ended up with was precisely the type that mathematicians already knew how to tile optimally.
But this was only half the work. Naor and Regev needed to partition the whole space, not just a slice of it. To get an n-dimensional spherical cube, they had to multiply their efficient tile with a tile from the remaining space (akin to how you might multiply a two-dimensional square with a one-dimensional line segment to get a three-dimensional cube). Doing so would lift their construction back into the original space, but it would also increase its surface area.
The pair had to show that the tile from the remaining space, which wasn’t as optimal, didn’t add too much to the surface area. Once they did that, their construction was complete. (Their final shape’s surface area ended up being a little larger than that of the non-convex spherical cube, but they believe that it might be possible to find a convex tile that’s just as efficient as its non-convex counterpart.)
“Their proof is completely different” from previous work on spherical cubes, said the mathematician Noga Alon. “And in retrospect, it’s maybe a more natural proof. This is what someone maybe should have tried to begin with.”
“When things are done differently,” Raz added, “sometimes you find interesting additional implications.”
Hope Rekindled
It’s not yet clear what those implications might be — though the work taps into the potential use of integer lattices in cryptography and other applications. Given how connected this problem is to other fields, “it’s likely to lead to other things,” Alon said.
RELATED:
- ‘Nasty’ Geometry Breaks Decades-Old Tiling Conjecture
- First Big Steps Toward Proving the Unique Games Conjecture
- A Grand Vision for the Impossible
At the moment, computer scientists do not see a way to interpret the convex result in the language of parallel repetition and the UGC. But they haven’t entirely given up on the original plan to use the foam problem to prove the conjecture. “There are various ways you can try to subvert the obvious barriers that we encountered,” Kindler said.
Braverman and Minzer tried one such way when they revisited foams in 2020. Instead of requiring that the tiling shape be convex, they asked that it obey certain symmetries, so that it looks the same no matter how you flip its coordinates. (In 2D, a square would work, but a rectangle would not; neither would the high-dimensional spherical cubes described to date.) Under this new constraint, the pair was able to show what Kindler and others had hoped to 15 years earlier: that you can’t do much better than the surface area of the cube after all.
This corresponded to a different kind of parallel repetition — one that would make the simplest case of max cut as hard as it needed to be. While the result offers some hope for this line of research, it’s not clear whether this version of parallel repetition will work for all max-cut problems. “It doesn’t mean that you are done,” Braverman said. “It just means that you are back in business.”
“There is a lot of potential in geometry,” Minzer said. “It’s just that we don’t understand it well enough.”
