Opinions differ widely about Sir Walter Raleigh, who roamed the world’s oceans in the 16th century: was he a gifted seafarer and explorer or was he more of a brutal pirate? Raleigh is best known for putting his cloak in a mud puddle to keep Queen Elizabeth I’s feet from getting dirty. It is not known whether this actually happened. What is certain, however, is that he had a lasting impact on mathematics for many centuries with one simple question – and experts are still racking their brains about it to this day.
During his expeditions, Raleigh was forced to take cannonballs on board to protect himself from enemy incursions. He wanted to sacrifice as little space as possible for this. So he set his scientific advisor Thomas Harriot (1560–1621) a supposedly simple task: he was to calculate how much floor space was required to stack a certain number of cannonballs in a pyramid shape. Harriot quickly found a handy formula for this and was able to present Raleigh with a satisfactory solution.
But the inquisitive explorer Harriot was not satisfied with just counting cannonballs. He wanted to find out whether this really is the closest packing of spheres. Suppose you want to fill the three-dimensional space completely with an infinite number of balls – how should you arrange them so that they take up as little space as possible?
Harriot could find no answer to that. Therefore he wrote a letter to the astronomer Johannes Kepler (1571-1630) in 1606, in which he reported on this question. Kepler seemed equally fascinated by the subject, for five years later he published what became known as Kepler’s conjecture: According to this, the densest arrangement of spheres is that which can be found when stacking oranges in the supermarket (or cannonballs on ships). observed: You start with a sphere in the middle and first add six copies around it. These balls form a kind of hexagon. This polygon has the advantage that you can pave the entire level with it without gaps. That means you can duplicate the hexagonal pattern all over the plane. A second layer is then formed by placing the balls in the resulting cavities, like in an egg carton. The third layer corresponds to the first again – and so the arrangement continues. Kepler was able to calculate how much free space is created by such a stack: about 26 percent.
Is this the best score for layering bullets? 26 percent empty space doesn’t sound like a particularly good pack. In fact, a finite number of balls can be arranged much more efficiently: For example, it saves space to line up five balls in a row like a kind of sausage. But Kepler’s problem revolves around infinitely many spheres in three spatial dimensions. Other configurations studied by Kepler produced larger gaps. However, he could not prove whether the hexagonal pattern is really the optimal one. In 1773, Joseph Louis Lagrange (1736–1813) proved the two-dimensional case: he was able to show that the most space-saving arrangement of circles in the plane is the hexagonal configuration, in which one circle is surrounded by six others. This gives a density of about 90 percent, so there is only 10 percent void space.
Proving that a particular arrangement is optimal proves extremely difficult. One can easily calculate how dense a formation is. This makes it possible to check relatively quickly whether one configuration is denser than another. But to show that there is no way to stack balls in a more space-saving way is a mammoth task. After all, one cannot simply go through and compare all the infinitely many configurations.
In 1831, the exceptional mathematician Carl Friedrich Gauss (1777–1855) nevertheless made a major breakthrough: he was able to prove that Kepler’s conjecture is correct if one assumes that the spheres are only arranged in a regular grid. In this case, it is possible to distribute the first couple of balls around the room, arranging all the others according to the same pattern. While checking which of all the regular lattices is the most space efficient is still not easy, Gauss was able to accomplish the task using the mathematical tools available in the 19th century—pen and paper.
However, Gauss could not eliminate whether there is a chaotic arrangement that is even denser. This possibility makes the problem much more difficult, because in this case each ball can be placed anywhere – and not just for the first few objects. It would be more than a century before the next notable advance was made.
Since it is impossible to test an infinite number of cases, one must attempt to break down Kepler’s conjecture to a problem involving only a finite number of configurations. In 1953, the Hungarian mathematician László Fejes Tóth (1915–2005) proved that it could indeed be done. The basic idea is: You divide the three-dimensional space into infinitely many areas and prove that the Keplerian arrangement is densest in all areas – because then it is also in all space.
For this, Tóth used so-called Voronoi diagrams. Instead of dealing with an infinite number of three-dimensional spheres, he suggested just looking at their centers, because their position determines the entire arrangement. Of course, you have to keep in mind that the centers must each maintain a minimum distance of one sphere diameter – after all, the spheres must not penetrate each other. This gives you a space full of randomly distributed points. This is where the Voronoi diagrams come in handy: this space is divided into different cells, each of which has a sphere in its center. A Voronoi cell contains all points in space that are closer to the center of the sphere than to any other.
Tóth conjectured that the volume of Voronoi cells is always greater than that of regular unit-radius dodecahedrons (one of five Platonic solids composed of twelve pentagons). This would correspond to Kepler’s arrangement of spheres; Tóth could not prove that, however. Therefore, in a next step, he not only looked at individual Voronoi cells, but up to thirteen of them. So the mathematician formulated a new task: If one could show that the volume of the Voronoi cells is always larger than that of dodecahedrons, then Kepler’s conjecture is true.
So instead of playing through an infinite number of possibilities and checking whether the associated packing density is always lower than that suggested by Kepler, one only has to look through a finite number of cases. The only problem: The number of arrangements to be checked is huge – the task still exceeds all human capacities. But as early as the 1950s, Tóth realized that computers would—at least eventually—be able to solve these calculations.
In 1992, the American geometer Thomas Callister Hales began to deal with the problem. Together with his student Samuel Ferguson, he was looking for a way to work through the many cases in order to prove Kepler’s conjecture with Tóth’s preparatory work. To do this, they had to examine more than 5,000 different ball configurations and show that their density is lower than that proposed by Kepler – this led to about 100,000 problems that a computer had to solve. Full implementation took four years.
Hales finally submitted the 250-page proof, including a three-gigabyte computer program, to the prestigious journal Annals of Mathematics in 1998. It took the reviewers another four years to review the evidence – with the result: They are 99 percent sure that the work is correct. While that was enough to get them published in the annals, Hales was not satisfied. Finally, there was a residual doubt that he could have done something wrong or overlooked a special case.
That’s why Hales launched the “FlysPecK” project (short for: Formal proof of Kepler) in 2003 to have his calculations checked by a computer-aided proof assistant. This is a program that verifies logical conclusions in chains of arguments. In recent years, such programs have been used more and more to check complicated mathematical proofs that experts cannot be completely sure of their correctness. The algorithms are extremely useful, but very complex to use. Because for this you have to translate a proof into a language that computers can understand. In addition, you have to transmit to the computer all the connections that are already known (definitions, proven theorems, axioms, and so on). The whole thing proves to be a mammoth task, especially when it comes to complex evidence.
It took another 14 years before FlysPecK was successfully completed. Now computers could check Hales’ work completely – and found no errors. With this, the scientific community can now really be sure that the proof of Kepler’s conjecture (no matter how complex and opaque it may be) is correct.
More than 400 years have passed between Sir Raleigh’s original question and the complete solution of the problem. But that is by no means the end of the subject of dense sphere packings. There is still a lot of exciting mathematics to be found: If you look at the question, for example, in higher dimensions (what is the densest arrangement of four-dimensional spheres in four-dimensional space?) or cases with a finite number of objects (how do you arrange around 53 spheres in the most space-saving way possible?), these are the ones problems to this day. It is to be hoped that answering them does not require quite as much time.
For more than six weeks, the heavily pregnant Alexandra R. from Nuremberg has disappeared without a trace. The police and the homicide squad are faced with a great mystery. What we do and don’t know about the disappearance of the bank boss.
88 police operations, threats, helplessness: in a housing estate in Weingarten, Baden-Württemberg, the neighborhood dispute escalated so much that it is now being reported on nationwide. What happened?
The original of this article “How a pirate occupied all mathematicians in the world for over 400 years” comes from Spektrum.de.
