Curves for a tighter fit: number theory provides a novel strategy for packing spheres efficiently.

Curves for a Tighter Fit

Consider the problem of filling a large shipping carton with identical ball bearings. Spheres don't fit together as neatly as, say, cubes. No matter how cleverly you arrange the balls, about one-quarter of the space in the carton -- or in any other container tightly packed with identical balls -- will remain unoccupied.

But is there a best way of packing identical spheres in a space so as to fill the maximum possible volume? That question remains a famous and unsolved problem in mathematics. No mathematician has yet succeeded in proving that a particular way of stacking balls is truly the least wasteful way of packing spheres in three dimensions.

Not content with just one unsolved problem, mathematicians extend the sphere-packing question to other dimensions. They ponder, for instance, the most efficient way of packing the eight-dimensional equivalents of ordinary spheres into an eight-dimensional space.

Two mathematicians, working independently, have now discovered a remarkable new way of finding orderly packings of spheres in higher dimensions. Their technique for constructing such arrangements exploits a mysterious, largely unsuspected link between number theory -- the study of integers -- and the geometrical problem of packing spheres efficiently.

"It's quite a surprising construction," says Andrew M. Odlyzko of AT&T Bell Laboratories in Murray Hill, N.J. "[The discovery] is very exciting because it provides another tool that people can have in their arsenal for attacking sphere-packing problems."

Although higher-dimensional spheres and their packings are difficult to visualize, questions concerning sphere packings interest both mathematicians and scientists. Random arrangements of spheres play a role in the properties of liquids and granular materials. And the study of sphere packings in higher dimensions suggests designs for energy-efficient communications systems, because designing a reliable, efficient signaling system is equivalent to solving the geometric problem of placing points inside a region of space when the points must lie at least a certain distance apart.

Mathematicians can study packings of identical spheres in any dimension simply by keeping track of the coordinates specifying the location of each sphere. In one dimension, one coordinate suffices to define each position; in eight dimensions, a string of eight numbers does the trick. Because these coordinates provide all the information necessary to define a packing, there's no need to draw pictures -- and it's probably not even possible.

In one dimension, the "sphere" is just a line segment of unit length. Such "spheres," placed one after another in a row, cover 100 percent of an infinitely long, one-dimensional line. This packing is as dense as any packing can be.

In the two-dimensional case, the "spheres" are circles. The densest packing of circles on a flat surface is the hexagonal lattice packing, in which each circle is surrounded by six others. The circles in this arrangement cover almost 91 percent of the surface.

The densest known packing in three dimensions, called the face-centered cubic packing, is familiar to anyone who has seen neat piles of oranges at fruit stands. But no one has proved that this arrangement is the very best possible. Conceivably, an irregular packing of some kind might be denser still.

In dimensions higher than three, mathematicians generally concentrate on studying lattice packings, in which spheres sit in regularly repeating patterns. They find irregular or random packings in higher dimensions too complicated and difficult to handle.

Four- and five-dimensional analogs of the face-centered cubic lattice produce the densest lattice packings in four and five dimensions. For dimensions higher than five, the appropriate analog of the face-centered cubic arrangement is no longer the densest lattice packing. And by the time one reaches eight dimensions, the gaps between the spheres in the eight-dimensional analog of the face-centered cubic arrangement are so large that it's possible to slide a copy of the basic lattice into the available gaps without overlapping the spheres.

Perhaps the most remarkable lattice packing, now known as the Leech lattice, sits in 24-dimensional space. Each sphere in the lattice touches 196,560 other spheres. This particular lattice is almost certainly the densest possible sphere-packing in 24 dimensions.

Over the years, mathematicians have developed a variety of techniques for constructing lattice packings. John H. Conway of Princeton (N.J.) University and Neil J.A. Sloane of AT&T Bell Laboratories in Murray Hill describe many of these methods and list sphere packings of record density in their definitive book on the subject: Sphere Packings, Lattices and Groups (1988, Springer-Verlag).

It was this book that introduced number theorist Noam D. Elkies of Harvard University, an expert on so-called elliptic curves, to the sphere-packing problem. "I had the notion that [certain] curves ... might possibly give you good sphere packings," Elkies says. "It's a natural enough thing to try once you have the two problems in mind."

In general, an elliptic curve is the set of solutions to an equation of the form [y.sup.2] = [x.sup.3] + Ax + B, where the coefficients A and B may be integers or certain mathematical expressions. Such equations play an important role in many problems in number theory. For example, they form the basis for a powerful method of factoring composite numbers (SN: 3/9/85, p.151) and may possibly lead to a proof of a famous conjecture known as Fermat's last theorem (SN: 6/20/87, p.397).

Elkies discovered that by choosing appropriate mathematical expressions for the coefficients A and B, he can find sets of solutions to these equations that he can then translate into various sphere-packing lattices. Working independently, mathematician Tetsuji Shioda of Rikkyo University in Tokyo came across several of the same lattice packings during investigations of mathematical forms known as Fermat surfaces.

What's remarkable about the discoveries isn't merely the fact that elliptic curves and Fermat surfaces can lead to lattice packings, but that the resulting packings are so dense -- as good as or better than the lattice packings already known. "There are fundamental reasons for why we get lattices," Elkies says. "What does not seem to be well understood is why we should get good lattices--why, for instance, we get the Leech lattice in dimension 24."

Adds Harvard's Benedict H. Gross, "Almost every lattice that's been previously constructed and analyzed pops out of this method for a suitable elliptic curve. These were all originally constructed up to dimension 24 by completely different ad hoc methods. Now here's one method that constructs them all, and it doesn't stop at dimension 24."

For example, choosing the right elliptic curves generates a sequence of sphere-packing lattices known as the Barnes-Wall lattices. These lattices, originally constructed years before by a quite different method, represent the densest packings known in dimensions four, eight, 16 and 32. However, the original construction leads to a result in dimension 64 that isn't quite as good as other known packings, and the results get worse for even higher dimensions.

Elkies' elliptic-curve method not only reproduces the Barnes-Wall lattices up to dimension 32 but also gets better lattices for dimension 64 and beyond. "Somehow the elliptic curve knows where to put in new points on this Barnes-Wall lattice to get a denser packing," Gross says.

Indeed, the method has generated record sphere-packing densities for a number of dimensions higher than 24. "I can get packings in arbitrarily high dimensions, but as far as I know, they're not very good packings once you get past 1,024," Elkies says. "However, even though the lattices past 1,024 get much worse than the records, they're interesting for number-theoretic reasons."

No one really understands why the elliptic-curve approach works so well. "In this particular case, I just don't know of any nice geometric interpretation of what's going on," Odlyzko says. "That's not totally uncommon. There are a few other known constructions of sphere packings that also show the same feature."

Elkies, Gross and others are now exploring several variations on the elliptic-curve theme to see if they can come up with other useful formulas for generating efficient sphere packings. "There are variations that so far we haven't been able to make work, but we keep on trying," Elkies says.

"It's a beautiful meeting ground of a lot of mathematics," Gross adds. "We're seeing just the tip of the iceberg."