THAT'S MATHSAN INTERNATIONAL workshop on packing problems took place in Trinity College Dublin earlier this week. Packing problems are concerned with storing objects as densely as possible in a container. Usually the goods and the container are of fixed shape and size.
The Foams and Complex Systems Group in TCD have recently discovered some new dense packings of spheres in cylindrical columns. Many packing problems arise in the context of industrial packaging, storage and transport, in biological systems, in crystal structures and in carbon nanotubes (tiny molecular-scale pipes).
Packing problems illustrate the interplay between pure and applied mathematics. They arise in practical situations but are then generalised and studied in an abstract mathematical context. The general results then find application in new practical situations. A specific example of this interplay is the sphere-packing problem.
In 1600, the adventurer Walter Raleigh asked his mathematical adviser Thomas Harriot about the most efficient way of stacking cannon balls on a ship’s deck. Harriot wrote to the famous astronomer Johannes Kepler, who formulated a conjecture that a so-called “face-centred cubic” was the optimal arrangement.
Let’s start with a simpler problem: how much of the table-top can you cover with non-overlapping €1 coins? Circular discs can be arranged quite densely in a plane. If they are set in a square formation, they cover about 79 cent of the surface. But a hexagonal arrangement, such as a honeycomb, with each coin touching six others, covers over 90 per cent; that’s pretty good. Joseph-Louis Lagrange showed in 1773 that no regular arrangement of discs does better than this. But what about irregular arrangements? It took until 1940 to rule them out.
In three dimensions, we could start with a layer of spheres arranged in a hexagonal pattern like the coins, and then build up successive layers, placing spheres in the gaps left in the layer below. This is how grocers instinctively pile oranges, and gunners stack cannon balls. The geometry is a bit trickier than in two dimensions, but it is not too difficult to show that this arrangement gives a packing density of 74 per cent. The great Carl Friedrich Gauss showed this is the best that can be done for a regular or lattice arrangement of spheres.
But again we ask: what about irregular arrangements? Is it not possible to find some exotic method of packing the spheres more densely? Kepler’s conjecture says no, and the problem has interested great mathematicians in the intervening 400 years. In 1900 David Hilbert listed 23 key problems for 20th century mathematicians, and the sphere-packing puzzle was part of his 18th problem.
In 1998 Thomas Hales announced a proof of Kepler’s Conjecture. He broke the problem into a large number of special cases and attacked each one separately. But there were some 100,000 cases, each requiring heavy calculation, far beyond human capacity, so his proof depended in an essential way upon using a computer.
After detailed review, Hales’ work was finally published in 2005 in a 120-page paper in Annals of Mathematics. Thus, Kepler’s Conjecture has become Hales’ Theorem. Most mathematicians accept that the matter is resolved, but there remains some discomfort about reliance on computers to establish mathematical truth.
Why should we concern ourselves with a problem for which grocers and cannoneers knew the solution long ago? Well, in higher dimensions the corresponding problem has more intriguing aspects. It is a key result in data communication: to minimise transmission errors, we design codes that are based on maximising the packing density of hyper-spheres in high- dimensional spaces. So the apparently abstruse conjecture of Kepler has some eminently practical implications for our technological world.
Peter Lynch is professor of meteorology at the school of mathematical sciences, University College Dublin. Visit his blog, thatsmaths.com
