Messiness Rules: In high dimensions, disorder packs tightest

Should you find yourself with a 60-dimensional suitcase, the best way to pack it may be the easiest: Throw in everything in a jumble. That’s the way to fit the most high-dimensional spheres into a fixed space, new research suggests.

JUMBLE IS BEST. In three dimensions, disorderly arrangements of spheres, such as this one, are less dense than tidier arrangements. But in very high dimensions, disorderly arrangements seem denser than neat ones. Torquato

The finding may be useful even to people without extra-dimensional luggage. It may improve the design of mathematical procedures called error-correcting codes used in computers to interpret noisy data.

Some 400 years ago, Johannes Kepler speculated that the best scheme for packing three-dimensional spheres is the way that grocers have always done it. Their orderly, pyramidal packing scheme piles the most oranges into the least space. Yet it took mathematicians until 1998 to prove Kepler right (SN: 8/15/98, p. 103:

But what about higher-dimensional spheres? Although a 5- or 6- or 60-dimensional sphere may sound strange, it’s mathematically simple. A sphere in any dimension is the collection of points a fixed distance from a central point.

But in high dimensions, spheres behave oddly. “Anything that can happen will happen if you’re in high enough dimensions,” notes sphere-packing mathematician Henry Cohn of Microsoft Research in Redmond, Wash.

As a result of this odd behavior, mathematicians haven’t yet found the densest packing scheme for homogeneous groups of high-dimensional spheres. A century ago, they determined a range for the best scheme, but there have been only slight improvements since. Salvatore Torquato and Frank Stillinger, both theoretical physicists at Princeton University, now describe an approach that sharply narrows that range.

The pair suggests that in high dimensions, it’s best to pack spheres in patterns that vary from spot to spot, rather than to repeat an arrangement in an orderly way. “People have intuited this might be the case,” says Torquato, “but this provides the first evidence backed up by some solid math.”

The argument, published in the fall Experimental Mathematics, relies on the assertion that certain disordered packing arrangements exist in very high dimensions. Support for that idea comes from physics rather than math. “The arguments they’ve got for the conjecture are nothing like a math proof, but they feel compelling,” Cohn says.

The physicists bring a new approach to a mathematical problem, which ultimately may be more important than the result, Cohn adds. “Regardless of whether [the finding] is true, it injects exciting ideas into the field,” he says.

Furthermore, the results may improve the design of computer equipment. Engineers use high-dimensional sphere packings to generate the error-correcting codes that electronic equipment uses for communication (SN: 10/2/04, p. 219: Torquato says that the new research suggests a much better approach to designing these codes.

More Stories from Science News on Math

From the Nature Index

Paid Content