New Scientist
May 25, 2002

"A fine mess "
by
Dana Mackenzie

It's a fruit-seller's nightmare and a slob's delight. Dana Mackenzie discovers a world where disorder is the rule

WHAT did your suitcase look like the last time you took a trip? Was everything neatly arranged, each item in its own perfect niche? Or did you throw things in, sit on the suitcase, and then cram in some more?

When it comes to packing things into a space, nature seems to like the tidy way. Molecules sit in neat, regular arrays inside crystals, for example. And mathematics agrees with nature, up to a point. If you want to cover a table top with coins, for example, you can cover the largest fraction of the space by placing them in a neat honeycomb pattern in which each coin touches 6 others. If you want to fill a big box with oranges, you should stack them up in hexagonal layers so that each orange touches 12 others. Grocers have known for centuries that this is the densest arrangement, although mathematicians didn't manage to prove it until 1998.

However, this only answers the densest-packing problem in Euclidean space--the kind of geometry we learn about in school, where space is flat like a table top. Mathematicians have known for nearly 200 years that space can be curved. Positive curvature gives you spherical geometry, familiar from the lines of latitude and longitude on a globe. Negative curvature leads to a version of geometry that's much harder to visualise. The 2D version is known as the hyperbolic plane, and in 3D it's called hyperbolic space. Now, for the first time, two mathematicians at the University of Texas have solved the densest-packing problem, essentially how to stack oranges, in hyperbolic geometry. Charles Radin had been working in Euclidean geometry for two decades, but turned to hyperbolic geometry in 1998 when his student and collaborator Lewis Bowen came to Texas. "Lewis is the best student I've had, and the best I'll ever have," Radin says. "He is brilliant." Together they have shown that most of the time, the best way to pack for a journey to hyperbolic space has no repeating pattern at all.

Hyperbolic space is not as far-fetched as it sounds. It may be that the space we live in is negatively curved on the largest scales. And some things you might not even think of as space are also hyperbolic. For example, phylogenetic trees, the branching ancestries used by biologists to map out the descent of species, have a hyperbolic geometry.

To adapt a line from Gertrude Stein, the most important thing about hyperbolic geometry is that there is more "there" there. As you go outwards in all directions from any point, the amount of space you come across increases faster than it does in flat space: so a circle in the hyperbolic plane can have 7 identical neighbours touching it, while a Euclidean circle can only ever have 6. And the bigger a circle gets in hyperbolic space, the more "warpage" it covers and hence the more room there is around it. Thus if a circle is big enough, it could have 20 identical neighbours or a thousand.

Although it's hard to imagine hyperbolic geometry, there are ways, especially if you're fond of horses or art. The hyperbolic plane is often described as being like a saddle, curved downwards in one direction and upwards in the other. If you draw a very small circle on a saddle, its circumference is about pi times its diameter. But if you draw a big circle, the circumference is more than pi times the diameter, which is why you can fit in more than 6 neighbours.

Alternatively, take a look at the woodcuts of M. C. Escher. His Circle Limit IV shows an entire hyperbolic plane, as if viewed through a fisheye lens that squashes the ever-growing space into a flat disc. Escher managed to completely cover the hyperbolic plane with two repeating shapes (an angel and a devil), which mathematicians call a tiling, for obvious reasons. But this is just the sort of regularity that, according to Radin, is the exception rather than the rule in hyperbolic packing.

Instead of designing fancy tiles to cover the space, Radin and Bowen were interested in packing in the simplest shapes of all--circles and spheres. Obviously you can't totally fill a hyperbolic space with spheres, any more than you can in Euclidean space, because there are always gaps between adjacent spheres. So the name of the game in sphere packing is to make the density--that is, the ratio of the volume filled by the spheres to the total volume--as large as possible.

But how do you compute the density of your packing when the number of spheres, as well as the volume of the space they occupy, is infinite? Mathematicians have come up with a variety of ways. In a regular packing, such as a crystal, you can just look at the smallest repeating "unit cell" of the crystal. For example, on a table top covered by coins, the unit cell is a hexagon containing one coin, and the density of the packing is just the ratio of the area of the coin to the area of the hexagon that surrounds it. This works out to about 0.91.

A second way of measuring density, and one that can also be applied to irregular packings, is to take an enormous box, measure the total volume of the spheres inside it, and divide by the volume of the box. If the box is big enough, then any local fluctuations in density should become negligible, and the average density of the packing will emerge.

But strangely, these approaches seem to work only in Euclidean space. Before Radin and Bowen started working on the problem, no one could come up with a definition of density that made sense in hyperbolic space. What stumped everyone was a paradox concocted by Karoly Böröczky in 1974 (see figure). In this figure, sizes are distorted by the lens we are looking through: all the shaded circles and squares are the same size when viewed from within the hyperbolic plane.

Suppose you try to work out the density of Böröczky's packing with the repeating units approach. You could tile the hyperbolic plane with rectangles like the one outlined in bold on the left. This has total area 3, and it has two circles inside it, whose total area is 1. Thus the density of the packing appears to be 1/3. Or is it? You could just as well use a tile like the one outlined on the right. This rectangle has area 3, but contains only one circle, whose area is 1/2, and so the density of the packing is 1/6. It doesn't add up.

The "giant box" approach is equally doomed. You can draw as big a box as you like that has circles inside 2/3 of its squares, but you can also draw one that has circles inside only 1/3 of its squares. The density result you get depends on where you happen to place the centre of your box.

The Böröczky tiling is also paradoxical in an even more profound way. It seems to imply that in a hyperbolic universe, matter can be created out of nowhere. Here's how. Suppose each square of the Böröczky tiling has one person in it. (Remember that all the squares are of equal size, so no one has to get squashed.) Each person agrees to give a gold coin to the person in the square above. Somehow, everybody in this universe turns a profit: they get two gold coins from their neighbours below and give one away to the neighbour above. Matter, not to mention money, seems to have come out of thin air.

In the real world, of course, such a pyramid scheme will eventually run out of people at the "bottom". Even if there were an infinite population, the number of people involved has to grow exponentially with each step down the pyramid, and there simply isn't room for that in a Euclidean universe, because space doesn't grow fast enough as you move down the pyramid. People would get physically squashed.

Hyperbolic space does allow it, however. There, a pyramid scheme based on the Böröczky tiling can make everyone happy. This bizarre conclusion isn't just a bit of irrelevant theorising, because it applies to our own Universe if it is hyperbolic. That kind of free creation of matter and energy would be deeply troublesome for the vast majority of cosmological theories.

Radin and Bowen came up with an ingenious way of resolving the problem. They discovered that although such paradoxical packings are not logically impossible, they are infinitely unlikely. That is, they represent 0 per cent of all possible packings, because for each one there are infinitely many others in which the measure of density makes sense. So we can after all extend the Euclidean definition of density to hyperbolic spaces: the paradox is nothing to worry about.

Radin and Bowen realised that the Böröczky pyramid scheme does not respect any kind of spatial symmetry in the hyperbolic plane. In the real Universe, there is a deep symmetry to space-time: the laws of physics act in the same way at different times and places, and there are no special directions or positions in the space-time. But in the paradox there is a particular direction in which all the gold coins are moving, and this direction would be evident at every point in the Universe, destroying the symmetry of space. If there were a god of hyperbolic space, it could presumably create matter this way. But matter could never spontaneously appear by the operation of the laws of physics, because they recognise no such special direction in space.

SOLVING REAL PROBLEMS

The upshot of all this is that because a sphere-packing like Böröczky's is infinitely unlikely to occur by any physical process, the fact that it has no definable density is irrelevant. In contrast, any real sphere-packing that could be produced by a physical process must have a density, which could be computed by the unit-cell method or the giant box method.

The idea of using physics to determine what is and what isn't allowed might seem extremely odd coming from a pure mathematician. But Radin confesses that he was trained as a physicist, albeit a "highly mathematical" one. Other mathematicians might accept the idea, too, once they see they can solve real problems with it. "The reason that other people didn't see this definition is that they were not brave or clever enough to change the notion of a packing itself in a sensible way," says Greg Kuperberg, a geometer at the University of California at Davis.

Once Radin and Bowen had shown that the definition of density was in fact workable, it was easy to show that densest packings are usually irregular. Remember that in the hyperbolic plane, size matters: a small coin will have a different optimal packing from a large one, because it can nestle next to fewer neighbours. But there are only a few possible periodic arrangements to go around, and an infinite number of possible coin sizes. So for almost every coin size, the optimal packing must be irregular.

Radin is hoping that this excursion into hyperbolic geometry will turn out to be relevant to Euclidean geometry as well. That's because high-dimensional Euclidean space is rather like hyperbolic space in one way. The number of neighbours a ball can have in Euclidean geometry increases rapidly with dimension: 6 in two dimensions, 12 in three, at least 24 in four-dimensional space, 240 in eight dimensions, and so on. Although the number of neighbours doesn't depend on the size of the ball, as it does in hyperbolic geometry, the fact that there can be so many of them means that packing might not work the way it does in flat 3D space. "In high dimensions there's hardly anything known about the densest packings, and whether they are periodic or not," says Bowen. Although they won't come out and say it, Bowen and Radin are clearly putting their money on "not".

If that's the case, it could have practical consequences. Error-correcting codes for telephone transmissions are based on the locations of packed spheres in high-dimensional Euclidean space. Denser packings correspond to more efficient and error-free transmissions. If Bowen and Radin are right then the best error-correction codes of all may correspond to messy, hard-to-calculate irregular packings.

It would also make our 3D space look privileged. If we lived in a higher-dimensional space, crystals might not grow, and greengrocers would have a hard time displaying their tangerines. So the next time you find that your belongings won't fit your suitcase, remember: things could be worse.