. 1
( 4)



>>

The Pursuit of Perfect Packing
The Pursuit of Perfect Packing


Tomaso Aste
Istituto Nazionale per la Fisica della Materia, Genoa,
Italy


and


Denis Weaire
Trinity College, Dublin, Ireland




Institute of Physics Publishing
Bristol and Philadelphia
c IOP Publishing Ltd 2000

All rights reserved. No part of this publication may be reproduced, stored
in a retrieval system or transmitted in any form or by any means, electronic,
mechanical, photocopying, recording or otherwise, without the prior permission
of the publisher. Multiple copying is permitted in accordance with the terms
of licences issued by the Copyright Licensing Agency under the terms of its
agreement with the Committee of Vice-Chancellors and Principals.

British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library.

ISBN 0 7503 0648 3 pbk
0 7503 0647 5 hbk

Library of Congress Cataloging-in-Publication Data are available




Publisher: Nicki Dennis
Commissioning Editor: Jim Revill
Production Editor: Simon Laurenson
Production Control: Sarah Plenty
Cover Design: Victoria Le Billon
Marketing Executive: Colin Fenton

Published by Institute of Physics Publishing, wholly owned by The Institute of
Physics, London
Institute of Physics Publishing, Dirac House, Temple Back, Bristol BS1 6BE,
UK
US Of¬ce: Institute of Physics Publishing, The Public Ledger Building, Suite
1035, 150 South Independence Mall West, Philadelphia, PA 19106, USA

Typeset in TEX using the IOP Bookmaker Macros
Printed in the UK by J W Arrowsmith Ltd, Bristol
Dedicated by TA to Nicoletta
Contents




Preface xi
1 How many sweets in the jar? 1
2 Loose change and tight packing 5
2.1 A handful of coins 5
2.2 When equal shares are best 6
2.3 Regular and semi-regular packings 11
2.4 Disordered, quasi-ordered and fractal packings 13
2.5 The Vorono¨ construction
± 16
3 Hard problems with hard spheres 20
3.1 The greengrocer™s dilemma 20
3.2 Balls in bags 20
3.3 A new way of looking 22
3.4 How many balls in the bag? 24
3.5 Osborne Reynolds: a footprint on the sand 24
3.6 Ordered loose packings 27
3.7 Ordered close packing 27
3.8 The Kepler Conjecture 29
3.9 Marvellous clarity: the life of Kepler 32
3.10 Progress by leaps and bounds? 34
4 Proof positive? 35
4.1 News from the Western Front 35
4.2 The programme of Thomas Hales 37
4.3 At last? 39
4.4 Who cares? 42
4.5 The problem of proof 43
4.6 The power of thought 44
Contents
viii

5 Peas and pips 45
5.1 Vegetable staticks 45
5.2 Stephen Hales 47
5.3 Pomegranate pips 48
5.4 The improbable seed 48
5.5 Biological cells, lead shot and soap bubbles 50
6 Enthusiastic admiration: the honeycomb 54
6.1 The honeycomb problem 54
6.2 What the bees do not know 56
7 Toils and troubles with bubbles 59
7.1 Playing with bubbles 59
7.2 A blind man in the kingdom of the sighted 60
7.3 Proving Plateau 63
7.4 Foam and ether 65
7.5 The Kelvin cell 68
7.6 The twinkling of an eye 70
7.7 Simulated soap 71
7.8 A discovery in Dublin 72
8 The architecture of the world of atoms 75
8.1 Molecular tactics 75
8.2 Atoms and molecules: begging the question 77
8.3 Atoms as points 78
8.4 Playing hardball 80
8.5 Modern crystallography 82
8.6 Crystalline packings 83
8.7 Tetrahedral packing 85
8.8 Quasicrystals 87
8.9 Amorphous solids 89
8.10 Crystal nonsense 90
9 Apollonius and concrete 91
9.1 Mixing concrete 91
9.2 Apollonian packing 93
9.3 Packing fraction and fractal dimension 94
9.4 Packing fraction in granular aggregate 95
10 The Giant™s Causeway 97
10.1 Worth seeing? 97
10.2 Idealization oversteps again 98
10.3 The ¬rst of¬cial report 99
10.4 Mallett™s model 101
10.5 A modern view 102
10.6 Lost city? 102
Contents ix

11 Soccer balls, golf balls and buckyballs 103
11.1 Soccer balls 103
11.2 Golf balls 103
11.3 Buckyballs 105
11.4 Buckminster Fuller 107
11.5 The Thomson problem 107
11.6 The Tammes problem 108
11.7 Helical packings 110
12 Packings and kisses in high dimensions 113
12.1 Packing in many dimensions 113
12.2 A kissing competition 116
12.3 More kisses 117
13 Odds and ends 119
13.1 Parking cars 119
13.2 Stuf¬ng sausages 120
13.3 Filling boxes 121
13.4 Goldberg variations 122
13.5 Packing pentagons 123
13.6 Dodecahedral packing and curved spaces 124
13.7 The Malfatti problem 125
13.8 Microspheres and opals 126
13.9 Order from shaking 127
13.10 Segregation 129
13.11 Turning down the heat: simulated annealing 130
14 Conclusion 133
Index 134
Preface



There are many things which might be packed into a book about packing. Our
choice has been eclectic. Around the mathematical core of the subject we have
gathered examples from far and wide.
It was dif¬cult to decide how to handle references. This is not intended as
a heavyweight monograph or an all-inclusive handbook, but the reader may well
wish to check or pursue particular topics. We have tried to give a broad range
of general references to authoritative books and review articles. In addition we
have identi¬ed the original source of many of the key results which are discussed,
together with enough clues in the text to enable other points to be followed up,
for example with a biographical dictionary.

Thanks are due to many colleagues who have helped us, including Nicolas
Rivier (a constant source of stimulation and esoteric knowledge), Stefan Hutzler
and Robert Phelan. Rob Kusner and J¨ rg Wills made several suggestions for the
o
text, which we have adopted.
Denis Weaire bene¬ted from the research support of Enterprise Ireland and
Shell during the period in which this was written, and Tomaso Aste was a Marie
Curie Research Fellow of the EU during part of it.

Tomaso Aste
Denis Weaire
December 1999




xi
Chapter 1

How many sweets in the jar?




The half-empty suitcase or refrigerator is a rare phenomenon. We seem to spend
much of our lives squeezing things into tight spaces, and scratching our heads
when we fail. The poet might have said: packing and stacking we lay waste our
days.
To the designer of circuit boards or software the challenge carries a stimu-
lating commercial reward: savings can be made by packing things well. How can
we best go about it, and how do we know when the optimal solution has been
found?
This has long been a teasing problem for the mathematical fraternity, one in
which their delicate webs of formal argument somehow fail to capture much cer-
tain knowledge. Their frustration is not shared by the computer scientist, whose
more rough-and-ready tactics have found many practical results.
Physicists also take an interest, being concerned with how things ¬t together
in nature. And many biologists have not been able to resist the temptation to
look for a geometrical story to account for the complexities of life itself. So our
account of packing problems will range from atoms to honeycombs in search of
inspiration and applications.
Unless engaged in smuggling, we are likely to pack our suitcase with mis-
cellaneous items of varying shape and size. This compounds the problem of how
to arrange them. The mathematician would prefer to consider identical objects,
and an in¬nite suitcase. How then can oranges be packed most tightly, if we do
not have to worry about the container? This is a celebrated question, associated
with the name of one of the greatest ¬gures in the history of science, Johannes
Kepler, and highlighted by David Hilbert at the start of the 20th century.

1
How many sweets in the jar?
2




Figure 1.1. Stacking casks of Guinness.




Hilbert™s 18th problem
In 1900, David Hilbert presented to the International Mathematical
Congress in Paris a list of 23 problems which he hoped would guide math-
ematical research in the 20th century. The 18th problem was concerned
with sphere packing and space-¬lling polyhedra.
I point out the following question (. . . ) important to number
theory and perhaps sometimes useful to physics and chemistry:
How one can arrange most densely in space an in¬nite number
of equal solids of given form, e.g. spheres with given radii or
regular tetrahedra with given edges (or in prescribed positions),
that is, how can one so ¬t them together that the ratio of the
¬lled to the un¬lled space may be as great as possible?
How many sweets in the jar? 3




Figure 1.2. Soap bubbles.




Figure 1.3. Packing on a grand scale: Wright T 1750 The Cosmos.


More subtle goals than that of maximum density may be invoked. When
bubbles are packed tightly to form a foam, as in a glass of beer, they can adjust
their shapes and they do so to minimize their surface area. So in this case, the
total volume is ¬xed and it is the total area of the interfaces between the bubbles
that is minimized.
The history of ideas about packing is peopled by many eminent and colourful
characters. An English reverend gentlemen is remembered for his experiments in
squashing peas together in the pursuit of geometrical insights. A blind Belgian
scientist performed by proxy the experiments that laid the ground rules for serious
play with bubbles. An Irishman of unrivalled reputation for dalliance (at least
How many sweets in the jar?
4

among crystallographers) gave us the rules for the random packing of balls. A
Scotsman who was the grand old man of Victorian science was brie¬‚y obsessed
with the parsimonious partitioning of space.
All of them shared the curiosity of the child at the church bazaar: how many
sweets are there in the jar?
Chapter 2

Loose change and tight
packing



2.1 A handful of coins
An ample handful of loose change, spread out on a table, will help us understand
some of the principles of packing. This will serve to introduce some of the basic
notations of the subject, before we tackle the complexity of three dimensions and
the obscurities of higher dimensions.
Let us discard the odd-shaped coins which are becoming fashionable; we
want hard circular discs. Coins come in various sizes, so let us further simplify
the problem by selecting a set of equal size. About ten will do. The question is:
how could a large number of these coins be arranged most tightly?
If we do it in three-dimensional space, then obviously the well known bank-
roll is best for any number of coins. But here we restrict ourselves to two-
dimensional packing on the ¬‚at surface of the table.
Three coins ¬t neatly together in a triangle, as in ¬gure 2.1. There is no
dif¬culty in continuing this strategy, with each coin eventually contacting six
neighbours. A pleasant pattern soon emerges: the triangular close packing in
two dimensions.
The fraction of table covered by coins is called the packing fraction, which
is

Area covered
¼¼ (2.1)
½¾
Total area
This must surely be the largest possible value. But can we prove it? That is
often where the trouble starts, but not in this case. A proof can be constructed as
follows.

5
Loose change and tight packing
6




(a)




(b)




(c)

Figure 2.1. Three equal discs ¬t tightly in an equilateral triangle (a). This con¬guration
can be extended to generate the triangular close packing (b). This is the densest possible
¼¼
arrangement of equal discs, having packing fraction . The regular pattern
drawn by joining the centres of touching discs is the triangular lattice (c).


2.2 When equal shares are best

There is a general principle which helps with many packing problems: it says
that, under certain circumstances, equal shares are best. (We shall resist any
When equal shares are best 7




Figure 2.2. What is the best price for two ¬elds, of a total area of 40 hectares?




temptation to draw moral lessons for politicians at this point.) A parable will
serve to illustrate this principle in action.
A farmer, attracted by certain European subsidies, seeks to purchase two
¬elds with a total area of 40 hectares. The prices for ¬elds depend on the ¬eld
size as shown in the diagram of ¬gure 2.2. What is he to do?
Playing with the different possibilities quickly convinces him that he should
buy two ¬elds of 20 hectares each. The combination of ten and 30 hectares is
more expensive; its price is twice that indicated by the open circle on the diagram,
which lies above the price of a 20 hectare ¬eld.
What property of the price structure forces him to choose equal-sized ¬elds?
It is the upward curvature of ¬gure 2.2, which we may call convexity.


Packing a single disc

A packing problem may be posed for a single disc of radius Ê by requiring it to
¬t into a polygonal boundary”a sheep-pen”which is as small as possible. The
sheep-pen has ’ sides: what shape should it be?
The answer is: a regular polygon (that is, totally symmetric with equal edges
and equal angles between edges).
To demonstrate this we note that the area of a polygon can be divided into
sectors, as shown in ¬gure 2.3(a). Each sector corresponds to an angle and
the angles must add up to ¾ . We need to share this total among ’ angles. But
the area of each sector must be greater or equal than that shown in ¬gure 2.3(b)
(isosceles triangle) and this is a convex function of .
Loose change and tight packing
8




Figure 2.3. (a) A polygon with a disc inside can be divided into triangular sectors with
angles . (b) The isosceles triangle that touches the disc is the sector that minimizes the
area for a given . The area of such a sector is a convex function of , therefore a division
in equal sectors is best.


So equal angles are best, and the strategy of equal shares results in ’ such
isosceles triangles.

Packing many discs
We are ready to complete the proof of the disc-packing problem in two dimen-
sions: what is the most dense arrangement of equal discs, in¬nite in number? The
answer will be the triangular close packing of ¬gure 2.1.
In his book, which covers many such problems 1, Fejes T´ th attributes the
o
½
Fejes T´ th L 1953 Lagerungen in der Ebene auf der Kugel und im Raum (Die Grundlehren der
o
Math. Wiss. 65) (Berlin: Springer).
When equal shares are best 9




Figure 2.4. A Vorono¨ partition around the centres of a disordered assembly of discs.
±


¬rst proof of this result to the Scandinavian mathematician Thue, who in 1892
discussed the problem at the Scandinavian National Science Congress and in 1910
published a longer proof. C A Rogers expresses some objections to these proofs:
˜it is no easy task to establish certain compactness results which he takes for
granted™2.
What we present here is based on one of the proofs given by Fejes T´ th.o
First, we assign to each disc in any given packing its own territory, a polygo-
nal shape which surrounds it (as in ¬gure 2.4). This is done by drawing a line bi-
secting the one which joins the centres of neighbouring discs. This is the Vorono ¨ ±
construction, to which we will return several times in this book.
We can assume that all these boundaries meet at a triple junction. (If not, just
introduce an extra boundary of zero length to make it so.) For an in¬nite number
of circles in the whole plane, a theorem of Euler 3 states that for such a Vorono¨ ±
4
pattern the average number of sides of the polygons is exactly six
’ (2.2)
The triangular pattern has ’ for all the polygons: they are regular hexagons.
If we introduce some polygons with more sides than six, they must be compen-
sated by others with less. Now we can use the result of the last section. The area
of the ’-sided polygons cannot be less than that of the regular polygon which
touches the disc. This is a convex function of ’ (¬gure 2.5), so that once again we
can use the principle of ˜equal shares™, this time of polygon sides. The total area
cannot be less than what we can obtain with ’ for all polygons.
¾
Rogers C A 1964 Packing and Covering (Cambridge: Cambridge University Press).
¿
See Smith C S 1981 A Search for Structure (Cambridge, MA: MIT Press) p 5.
There are certain kinds of tilings where this equation does not hold. See Gr¨ nbaum B and Rollet G C
u
1986 Tilings and Patterns (New York: Freeman).
Loose change and tight packing
10




Figure 2.5. The area of regular polygons with a circle inscribed is a convex function of the
number of sides of the polygons (’).


Here we have a pattern which, were we not to construct it in the imagination,
presents itself to us in daily life, in the packing and stacking of drinking straws
and other cylindrical objects, or the layout of eggs in a carton. It would even form
spontaneously, at least locally, if we shuf¬‚ed our coins together for long enough.
There is a research group in Northern France which does just this sort of
experiment, using a gigantic air table. This is a surface with small holes through
which air is pumped, so that ¬‚at objects can glide upon it without friction.
Later we will encounter other problems which look very similar to this one,
but few of them submit to such a straightforward argument. Indeed a false sense
of security may be induced by this example. It turns out that almost any variation
of the problem renders it more mysterious.
So what is so special about the packing of these discs? It is the convenient
fact that there is a best local packing which can be extended without variation to
the whole structure. If we restore our handful of mixed change, or try to stack
Regular and semi-regular packings 11




Figure 2.6. The giant air table machine (4.5 m high) constructed, in Rennes by D Bideau
and others, in order to investigate two-dimensional packings. The two men in the photo-
graph are the builders of the system.


oranges in three dimensions instead, no such elementary argument will work.
The problem becomes one of a global optimization, which cannot always be
achieved by local optimization. It takes its place alongside many others which
practical people have to face. Under speci¬ed conditions how do we maximize
some global quantity? Given life and liberty how do we best pursue happiness,
allowing for the limitations of human nature and the competing demands of indi-
viduals?
As every democrat knows, global optimization is a matter of dif¬cult com-
promise. Perfection is rarely achieved, and how do you know when you have
it?


2.3 Regular and semi-regular packings
In the previous section we learned that dividing space into equal, regular shapes
is often the most convenient strategy. In the densest packing of equal discs, each
disc is in contact with six others. Upon joining the centre of each disc with the
centres of the ones in contact with it, there emerges a tessellation (or tiling) of
Loose change and tight packing
12




Figure 2.7. Spontaneous clustering into the triangular lattice for bearings on a plane shaken
vertically from high (top) to low accelerations (bottom). Single images (right column) and
second averaged images (left column). (Courtesy of J S Olafsen and J S Urbach.)


the plane made with equal, regular triangular tiles. This tessellation has three
properties:
(1) all the vertices are identical, that is, lines come together in the same way at
each of them;
(2) all tiles are regular (that is, completely symmetrical) polygons;
(3) all polygons are identical.
This is called a regular tessellation. How many tessellations with such regularity
exist? The answer is three: they correspond to the triangular, square and hexag-
onal cases, which are shown in ¬gure 2.9. In these three packings the discs are
locally disposed in highly symmetrical arrangements and the whole packing can
be generated by translating on the plane a unique local con¬guration, as in the
simplest kinds of wallpaper.
Disordered, quasi-ordered and fractal packings 13




(a) (b)

Figure 2.8. Ordered and disordered tessellations, from the pavements of Lisbon.


By relaxing the third condition, and allowing more than one type of regular
polygon as tiles, eight other packings can be constructed. These tessellations are
named semi-regular or Archimedean by analogy with the names used for ¬nite
polyhedra in three dimensions. Figure 2.10 shows these eight semi-regular pack-
ings and their packing fractions. Note that the lowest packing fraction among
these cases ( ³ ¼ ¿ ½) is attained by the structure made with triangular and do-
decagonal tiles. This brings us back to the equal shares principle, used this time
in the opposite way: very different shares give bad packing fractions.
In these semi-regular packings the whole structure can again be generated by
translating a unique local con¬guration (indicated by lines in ¬gure 2.10). Such
structures are called lattices or crystalline structures. In metals, in quartz, in
diamond, and in many other solids, atoms are disposed regularly in space as in
the two-dimensional arrangements of discs previously discussed. These solids
are named crystals.
But nature is rich and diversi¬ed, and other types of packings different from
the simple crystalline ones are also found.


2.4 Disordered, quasi-ordered and fractal packings
We know that when equal coins are placed tightly on the table, an ordered, regular
con¬guration emerges: the triangular lattice. What happens if coins of different
sizes are used instead? Let us try to construct this packing: start with equal coins
packed regularly in the tightest way, then insert a coin of a different size. If the
coin is much smaller than the others (relative diameter less than 15% 5 ), it can be
inserted in one of the holes of the regular packing without modifying the whole
structure. In the technical jargon of the subject, this is sometimes called a ˜rattler™,

” 
Inside the hole between three coins of diameter , packed in the tightest way, a fourth coin of
diameter equal or smaller than ¼ ´¾ ¿ ½µ ´¼ ½ µ can be inserted.
Loose change and tight packing
14




Figure 2.9. Regular packings of equal discs. Here the patterns formed by joining the
centres of the circles mutually in contact have identical vertices and regular, identical

polygons as tiles. These are triangles (a), squares (b) and hexagons (c). The packing
½¾ ¼ ¼ ¼

fractions are respectively (a), (b) and
¾ ¼¼ (c).


since it is free to rattle around the space available.
On the other hand, if the inserted coin is very large it requires the removal of
the original coins to accommodate it and, in the tight packing around this inter-
Disordered, quasi-ordered and fractal packings 15




Figure 2.10. Semi-regular packings of equal discs. Here the patterns formed by joining
the centres of the circles mutually in contact have identical vertices and tiles which are
different kinds of regular polygons.


loper, the whole structure is modi¬ed.
In general, it turns out that when differently sized discs are packed tightly
together there is a strong tendency towards disorder. This is especially true when
there is a marked difference in the disc sizes (at least 25%) and the effect is
stronger when a few large discs are mixed with small ones 6 .
When discs with special size ratios are chosen, beautiful arrangements can


be created. This, for instance, is the case when equal quantities of discs with two
diameters in the ratio ´¿   µ are chosen (here ´½· µ ¾ ½ ½ ,
is the ˜golden ratio™, which is the ratio between the base and the height of the
golden rectangle: the shape with perfect proportion for the ancient Greeks). In
¬gure 2.12 different arrangements obtained by using this mixture are shown. (The
diameter ratio of the US cent and quarter coins is very close to this ratio , and
their contrasting colours make nice ¬gures.)
The packing fraction can be arbitrarily increased by taking a variety of discs
with sizes in an arbitrarily large range. This, for instance, is the case in the packing
See, for instance, Nelson D R, Rubinstein M and Spaepen F 1982 Order in two dimensional binary
random arrays Phil. Mag. A 46 105“26; Dodds J A 1975 Simplest statistical geometric model of the
simplest version of the multicomponent random packing problem Nature 256 187“9.
Loose change and tight packing
16




(a)




(b)

Figure 2.11. A disordered assembly of equal discs (a), and a packing of discs with two
different sizes (b).


illustrated in ¬gure 2.13 which is known by the name of Apollonian packing (to
which we return in chapter 9).
Such structures are typical examples of a fractal 7 . The structure repeats sim-
ilar patterns on each length scale. Looking at it through a microscope one would
see much the same structure for any degree of magni¬cation.


2.5 The Vorono¨ construction
±
We have already encountered a geometrical construction which will recur
throughout this book. This has become attached to the name of Vorono¨ (1868“
±
Mandelbrot B B 1977 The Fractal Geometry of Nature (New York: Freeman).
The Vorono¨ construction
± 17




Figure 2.12. Various tilings obtained using a binary mixture of discs. (From Lancon F and
¸
Billard L 1995 Binary tilings tools for models Lectures on Quasicrystals ed F Hippert and
D Gratins (Les Vlis: ed. de physique) pp 265“81.)
Loose change and tight packing
18




(a)




(b)

Figure 2.13. Two examples of fractal packings: the Apollonian packing (a), the loxo-
dromic sequence of circles (b). (See Coxeter H S I 1966 Loxodromic sequences of tangent
spheres AEQ. MATH 1 104“21.)


1908) but the primary credit probably belongs to Dirichlet, in 1850. Both he and
Vorono¨ used the construction for a rather abstract mathematical purpose in the
±
study of quadratic forms. Since then, it has played a supporting role in many
important theories.
The modern use of Vorono¨ diagrams in physical science (in two, three or in
±
many dimensions) began with crystallography but has since become much more
general. In geography and ecology, indeed everywhere that spatial patterns are
The Vorono¨ construction
± 19

analysed, this construction has proved useful.
The German term ˜Wirkungsbereich™ for a Vorono¨ cell is particularly apt; it
±
refers to a region of activity or in¬‚uence. It has often been considered to be a good
basis for dividing political territories, given a set of pre-existing centres in major
towns. Indeed, the division of France into Departments, laid down by Napoleon,
corresponds rather well to the Vorono¨ regions around their principal cities.
±
In solid state physics the name Wigner“Seitz cell has been used instead,
since 1933, and it was used to calculate the changes in the energy of electrons
when atoms were packed together.
A recent monograph on the subject, although con¬ned largely to two-dimen-
sional patterns, ran to over 500 pages, so it evidently has many rami¬cations 8 .




Okabe A, Boots B and Sugihara K 1992 Spatial Tessellations: Concepts and Applications of
Vorono¨ Diagrams (Chichester: Wiley).
±
Chapter 3

Hard problems with hard
spheres



3.1 The greengrocer™s dilemma
Now we will exchange our coins for a heap of oranges or a bag of ball bearings.
It is much more dif¬cult to see the possibilities that they present, in the mind™s
eye or in reality. But one thing becomes quite clear at an early stage: no amount
of shaking the bag will cause the balls to come together in an elegant ordered
structure. By the same token, the greengrocer must take time and care to stack
his oranges neatly. Is his stacking the densest possible? Of course, this is not
his objective. For our greengrocer, considerations of stability and aesthetics are
paramount. If he is an amateur mathematician perhaps he might just wonder. . . .


3.2 Balls in bags
Let us look more closely at the ball bearings in the bag. In order to ¬x their
positions, wax may be poured in and the contents then dissected. The ¬rst person
to undertake this experiment systematically was J D Bernal, or rather his student
John Finney, in the 1950s 1. The random packing of balls became known as Bernal
packing. One might wonder why it was not done before. Certainly it is tedious,
but such tedium is often part of the price of a PhD.
The preceding century, in which the detailed atomic arrangements of crystals
were hypothesized and powerful theories of symmetry applied to them, was one
in which perfect order was the ideal (as one might expect in an imperial age).
½
Bernal J D 1959 A geometrical approach to the structure of liquids Nature 183 141“7.

20
Balls in bags 21




(a) (b)




(c)

Figure 3.1. This is the sphere packing commonly found on fruit stands, in piles of cannon
balls on war memorials and in the crystalline structures of many materials.


Order and beauty were often interchangeable in the sensibility of the admirer of
nature.

L` , tout n™est qu™ordre et beaut e
a ´
Charles Baudelaire (1821“67)

At the century end, as the old order fell into decay, the mood began to change.
The poet Hopkins gloried in ˜dappled things™, the commonly observed disarray
of the real world. Nevertheless, words like ˜impurity™ and ˜defect™, applied to
departures from perfect order, still carried a prejudicial overtone in physics, even
as they eventually emerged as the basis of the semiconductor industry.
Those whose curiosity centred on the structure of liquids still tended to pic-
ture them as defective crystals or construct elegant formal theories that had little
to do with their characteristically random geometry.
Eventually Bernal, perhaps because of his biological interests, saw the ne-
cessity to examine this geometry more explicitly, to confront and even admire its
Hard problems with hard spheres
22




(a) (b)

Figure 3.2. Bernal packing of spheres.


variety. He also recognized the dif¬culty of doing so, other than by direct obser-
vation of a model system. Why not ball bearings? He called this unsophisticated
approach ˜a new way of looking™ at liquids.
Hence the shaking and kneading of ball bearings in a bag, the pouring in of
wax, the meticulous measurement of the positions of balls as the random cluster
was disassembled. The packing fraction of the Bernal packing was found to be
roughly 0.64; or slightly less if the balls are not kneaded to encourage them to
come together closely. Although particular local arrangements recur within it,
they are variable in shape and random in distribution 2 .
Subsequently, the chief scienti¬c interest of the Bernal structure has been
in its application to describe the structures of amorphous (i.e. non-crystalline)
metals.

Si l™ordre satisfait la raison,
le d´ sordre fait les d´ lices de l™imagination.
e e
Paul Claudel (1868“1955)

3.3 A new way of looking
Desmond Bernal, born in 1901 on an Irish farm, was one of the prime movers of
modern crystallography and biophysics. He is thought to have narrowly missed
a Nobel Prize for his work on sex hormones. This would have been singularly
appropriate for a man whose sexual appetite was rumoured to be prodigious. This
¾
Bernal J D and Mason J 1960 Co-ordination of randomly packed spheres Nature 385 910“11.
A new way of looking 23




Figure 3.3. Desmond Bernal (1901“71).



is unusual in a scientist, as Bernal himself found out when curiosity moved him
to check the historical record for the exploits of others. He found that typically
they had less adventurous erotic curricula vitae than his. Certainly, few can have
enjoyed the excitement of being pursued down the street by a naval of¬cer with a
revolver after a brusque interruption of an amorous interlude.
His intellectual brilliance is better documented. It would have found more
positive expression if it had not been de¬‚ected into political channels (he was an
ardent Communist”some of his sociopolitical writings are still highly regarded).
Despite such distractions, he gathered around him in London an outstanding in-
ternational research group.
Among the thoughts that most fascinated him from the outset were ideas of
packing. They eventually found expression in his study of the structure of liq-
uids, which proceeded directly along the down-to-earth lines advocated by Lord
Kelvin, the founder of the ˜hands-on™ school of British crystallography whose
crowning achievement was the discovery of the spiral structure of DNA.
Bernal used his hands and those of his students to build large models or take
apart packings of ball bearings. He showed that geometrical constraints impose
organization and local order on such random structures.
Hard problems with hard spheres
24

3.4 How many balls in the bag?
The Bernal packing falls well short of the maximum density that can be achieved
in an ordered packing. Nevertheless it has acquired its own signi¬cance as the
best random packing. It is dif¬cult to give to this notion any precise meaning, but
many experiments and computer simulations of different kinds do reproduce the
same value (to within a percent or so). For example, spheres may be added to a
growing cluster, according to various rules, and the eventual result is a random
packing not very different from that of Bernal. This was the ¬nding of Charles
Bennett, who wrote various computer programs for such ˜serial deposition™ at
Harvard University in the mid-1960s. (Bennett has gone on to be one of the most
authoritative and imaginative theoreticians in the science of computation.)
From the outset, this was called dense random packing, to distinguish it from
looser packings of spheres which were found in some experiments. Attempts to
de¬ne a unique density for random loose packings are probably futile, because it
must depend on the precise circumstances, and physical effects (such as friction)
which contribute to it. For instance, G D Scott poured thousands of ball bearings
into spherical ¬‚asks of various sizes 3 . When the ¬‚ask was gently shaken to op-
¼ ¿   ¼ ¿¿Æ  ½ ¿, with
timize the packing, the density was found to be
Æ being the number of balls. When the ¬‚ask was not shaken, the loosest random
¼ ¼   ¼ ¿ Æ  ½ ¿. Lower values for the packing
packing was found to have
fraction can be obtained by eliminating the effect of gravity. The lowest densities
which can be experimentally obtained are around ³ ¼ 4 .
Although his approach was an original one, Bernal™s investigations followed
in the footprints of an eminent English scientist of the 19th century.


3.5 Osborne Reynolds: a footprint on the sand
It is seldom left for the philosopher to discover anything which has
a direct in¬‚uence on pecuniary interests; and when corn was bought
and sold by measure, it was in the interest of the vendor to make the
interstices as large as possible, and of the vendee to make them as small
(. . . ).
If we want to get elastic materials light we shake them up (. . . ) to
get these dense we squeeze them into the measure. With corn it is the
reverse; (. . . ) if we try to press it into the measure we make it light”to
get it dense we must shake it”which, owing the surface of the measure
being free, causes a rearrangement in which the grains take the closest
order5.
¿
Scott G D 1960 Packing of spheres Nature 188 908“9; 1969 Brit. J. Appl. Phys. 2 863.
Onoda G Y and Linger E G 1990 Random loose packing of uniform spheres and the dilatancy onset
Phys. Rev. Lett. 64 2727“30.
Reynolds O 1886 Experiment showing dilatancy, a property of granular material, possibly con-
nected with gravitation Proc. Royal Institution of Great Britain Read 12 February.
Osborne Reynolds: a footprint on the sand 25

With these words Osborne Reynolds described this ˜paradoxical™ property of
granular packings.
When granular material, such as sand or rice, is poured into a jar its density is
relatively low and it ¬‚ows rather like an ordinary ¬‚uid. A stick can be inserted into
it and removed again easily. If the vessel, with the stick inside, is gently shaken
the level of the sand decreases and the packing density increases. Eventually the
stick can no longer be easily removed and when raised it will support the whole
jar. This conveys a strong sense of the ultimate jamming together of the grains, in
the manner described by Bernal.
Such procedures have been the subject of research in physics laboratories in
recent years6 , but they can be traced back to the words of Osborne Reynolds.

At the present day the measure for corn has been replaced by the scales,
but years ago corn was bought and sold by measure only, and measuring
was then an art which is still preserved. (. . . ) The measure is ¬lled over
full and the top struck with a round pin called the strake or strickle.
The universal art is to put the strake end on into the measure before
commencing to ¬ll it. Then when heaped full, to pull the strake gently
out and strike the top; if now the measure be shaken it will be seen that
it is only nine-tenths full.

J J Thomson, the discoverer of the electron, called Reynolds ˜one of the most
original and independent of men™, having attended his lectures at Owens College,
Manchester. Thomson described Reynolds™ chaotic lecturing style which, though
it failed to impart much actual knowledge, ˜showed the working of a very acute
mind grappling with a new problem™. His rambling and inconclusive manner of
teaching was due in part to his failure to consult the existing literature before
developing his own thoughts. He was fond of what Thomson called ˜out-of-door™
physics, including the calming effect of rain or a ¬lm of oil on waves, the singing
of a kettle and”in the episode that concerns us here”the properties of ˜sand,
shingle, grain and piles of shot™. He noted that ˜ideal rigid particles have been used
in almost all attempts to build fundamental dynamical hypotheses of matter™, yet
it did not appear ˜that any attempts have been made to investigate the dynamical
properties of a medium consisting of smooth hard particles (. . . )™, although some
of these had ˜long been known by those who buy and sell corn™.
While consistent with his love of out-of-door physics, this preoccupation
with sand arose in a more arcane context. Like many others, he had set out to
invent an appropriate material structure for the ether of space. The ether was a
Holy Grail for the classical physicist, which was also pursued by Lord Kelvin at
about the same time, as we shall recount in chapter 7.
Similar experiments are reported by: Jenkin C F 1931 The extended pressure by granular material:
an application of the principles of dilatancy Proc. R. Soc. A 131 53“89; Weighardt K 1975 Ann. Rev.
Fluid. Mech. 7 89; Dahmane C D and Molodtso¬n Y 1993 Powders & Grains 93 ed C Thornton
(Rotterdam: Balkema) p 369; Horav´ th V K, J´ nosi I M and Vella P J 1996 Anomalous density
a a
dependence of static friction in sand Phys. Rev. E 54 2005“9.
Hard problems with hard spheres
26

Could the electromagnetic properties of space be somehow akin to the me-
chanical properties of sand? Reynolds somehow convinced himself of this, as-
serting the ˜ordinary electrical machine™ then in use as a generator ˜resembles in
all essential particulars the machines used by seedsmen for separating two kinds
of seed, trefoil and rye grass, which grow together (. . . )™.
So inspired was he by this notion that his last paper was entitled ˜The Sub-
mechanics of the Universe™. But he hedged his bets by saying that his work also
offered ˜a new ¬eld for philosophical and mathematical research quite indepen-
dent of the ether™. Most of his readers probably agreed with J J Thomson that
this ˜was the most obscure of his writings, as at this time his mind was beginning
to fail™. Oliver Lodge diplomatically wrote that ˜Osborne Reynolds was a genius
whose ideas are not to be despised, and until we know more about the ether it is
just as well to bear this heroic speculation in mind™.
In his speech at the British Association Meeting (Aberdeen 1885) 7 Reynolds
explained that a granular material in a dense state must expand in order to ¬‚ow or
deform
As the foot presses upon the sand when the falling tide leaves it ¬rm,
that portion of it immediately surrounding the foot becomes momentar-
ily dry (. . . ). The pressure of the foot causes dilatation of the sand, and
so more water is (drawn) through the interstices of the surrounding sand
(. . . ) leaving it dry. . . .
Lord Kelvin spoke admiringly of this observation:
Of all the two hundred thousand million men, women, and children
who, from the beginning of the world, have ever walked on wet sand,
how many, prior to the British Association Meeting in Aberdeen in
1885, if asked, ˜Is the sand compressed under your foot?™ would have
answered otherwise than ˜Yes™? 8
What Reynolds observed he called dilatancy, since the sand dilates. An
expansion is required to allow any deformation (typically the distance between
grains increases by about 1%).
In public lectures he dramatically demonstrated dilatancy (his ˜paradoxical
or anti-sponge property™) by ¬lling a bag with sand and showing that if only just
enough water was added to ¬ll the interstices, the sealed bag became rigid.
Reynolds was remembered thereafter for his contributions to the dynamics of
¬‚uids (including the Reynolds number) but his work on granular materials enjoys
belated celebrity today. It has become a fashionable ¬eld of physics, one in which
fundamental explanations are sought for phenomena long known to engineers.
In one practical example, dry cement is stocked in large hoppers from which
it is dispensed at the bottom. Normally, the cement comes out with a constant
Reynolds O 1885 British Association Report Aberdeen p 897; 1885 On the dilatancy of media
composed of rigid particles in contact. With experimental illustrations Phil. Mag. 20 223.
Lord Kelvin 1904 Baltimore Lectures p 625.
Ordered loose packings 27

¬‚ux independent of the ¬lling of the hopper (which is not what a normal liquid
would do). Occasionally, when it is not been allowed enough time to settle, the
cement behaves in a much more ¬‚uid manner. A disaster ensues when the hopper
is opened9.

3.6 Ordered loose packings
Ordered loose packings sometimes occur in the study of crystal structures. Here
our question may be turned on its head: what is the lowest possible density for
a packing of hard spheres which is still mechanically stable or ˜rigid™? For such
rigidity, each sphere needs at least four contacts and these cannot be all in the same
hemisphere. Many loose crystalline packings have been proposed. For instance,
¼ ½¾¿ . It was proposed many years
the structure shown in ¬gure 3.4(a) has
ago by Heesch and Laves and has been long considered to be the least dense stable
¼ ½¼¿¿ (¬gure 3.4(b)) was obtained
sphere packing. Recently a packing with
by decorating, with tetrahedra, the vertices of the CdSO net10 .
¼¼ 11
The lowest known density for stable packing is . This value
is about ten times smaller than the one for the loose random packing. But this is
not surprising, since structures such as those in ¬gure 3.4 are highly symmetric
and cannot be obtained or approximated by simply mixing spheres at random.

3.7 Ordered close packing
What about dense ordered packings of spheres, the central question, from which
we have digressed?
Back at the greengrocer™s shop, the proprietor, unconcerned about theory,
has stacked his oranges in a neat pyramidal pile. He proceeds by ¬rst laying out
the fruit in the manner of the coins of chapter 2, and observes that this ” creates
½
resting-places for the next layer, and so on. The packing fraction is
¼¼ . Is this the best that can be done?
It has been remarked that all mathematicians think and all physicists know
that this is the best. Some metallurgists have gone one step further by declaring in
textbooks that such an assertion has been proved. At least prior to August 1998,
such a statement was quite incorrect. This is the longstanding Kepler Problem.
Let us resort to theoretical argument, following the line of chapter 2. In three
dimensions the counterpart of the trio of coins in mutual contact is the regular
tetrahedron (¬gure 3.5). If these fourfold units could be tightly assembled we
might well expect them to give us ” best possible structure in three dimensions,
the
and its packing fraction would be ½ “— ½ ´ ½ µ   ¿ ¼ .
¿

Duran J 2000 Sands, Powders and Grains (New York: Springer).
½¼
O™Keeffe M and Hyde G B 1996 Crystal Structures (Washington, DC: Mineralogical Society of
America).
½½
Gardner M 1966 Packing spheres Martin Gardner™s New Mathematical Diversions from Scienti¬c
American (New York: Simon and Schuster).
Hard problems with hard spheres
28




(a)




(b)

Figure 3.4. (a) A structure (called D4) of stable equal-sphere packing with low density
(the circles indicate the centres of the spheres and the lines connect neighbours in contact).
(b) This structure (called W4) is obtained by replacing the vertices of the CdSO net with
tetrahedra.
The Kepler Conjecture 29




Figure 3.5. Four spheres can be assembled mutually in contact on the vertices of a
regular tetrahedron (a). This disposition is the closest possible with packing fraction
¼ . But regular tetrahedra cannot be combined to ¬ll the whole Euclidean
“— ½ ´ ¿ µ ¾ ½¼ ,
½
space. The angle between two faces of the tetrahedron is
which means that around a common edge one can dispose ¬ve tetrahedra, but an interstice
“— ½ ´ ¿ µ ¼ ½¾ will remain (b). Twenty tetrahedra can be disposed around
 
of ¾ ½


a common vertex; the 12 external vertices make an irregular icosahedron (c).


But they cannot be so combined. This strategy fails.
Such a packing would necessarily involve tetrahedra which share a common
“—  ½ ´ ½ µ) does not
edge, but the angle between two faces (dihedral angle, ¿
allow this, as ¬gure 3.5 shows. Local desiderata are incompatible with global
constraints, and this is sometimes categorized by the apt term ˜frustration™ 12.
One strategy to relieve this frustration would be to relax the condition that
the tetrahedra be regular (perfectly symmetric), as they must be if all four balls
are in contact with each other. We shall return to this possibility in chapter 8.


3.8 The Kepler Conjecture
Science is notoriously dependent on military motives. In 1591 Walter Raleigh
needed a formula to count the number of cannonballs in a stack. His friend
Thomas Harriot 13 , who was his surveyor/geographer on the second expedition
to Virginia, developed a formula without much dif¬culty and made a study of
close packing. He was an accomplished mathematician, later credited with some
of the theorems of elementary algebra still taught today.
He was also active in promoting the atomic theory, which hypothesized that
´
½¾
Sadoc J-F and Mosseri R 1997 Frustration G´ om´ trique (Paris: Editions Eyrolles).
ee
½¿
See Rukeyser M 1972 The Traces of Thomas Harriott (London: Gollanz)
Hard problems with hard spheres
30




Figure 3.6. Thomas Harriot (1560“1621). Courtesy of Trinity College Oxford.


matter was composed of atoms. In a letter in 1607, he tried to persuade Kepler to
adopt an atomic theory in his study of optics. Kepler declined, but a few years later
in his De Nive Sexangula (1611) he adopted an atomistic approach to describe the
origin of the hexagonal shape of snow¬‚akes. To do this he assumed that the
snow¬‚akes are composed of tiny spheres 14 .
Kepler recognized the analogy with the bee™s honeycomb. He therefore stud-
ied the shape resulting from compressing spheres arranged in the closest way. The
construction of the ˜most compact solid™ is described as follows:

For in general equal pellets, when collected in any vessel, come to a mu-
tual arrangement in two modes according to the two modes of arranging
them in a plane.
If equal pellets are loose in the same horizontal plane and you drive
them together so tightly that they touch each other, they come together
either in a three-cornered or in a four-cornered pattern. In the former
case six surround one; in the latter four. Throughout there is the same
pattern of contact between all the pellets except the outermost. With
a ¬ve-sided pattern uniformity cannot be maintained. A six-sided pat-
tern breaks up into three-sided. Thus there are only the two patterns as
described.
½
See Leppmeier M 1997 Kugelpackungen von Kepler bis heute (Wiesbaden: Vieweg).
The Kepler Conjecture 31




Figure 3.7. The original page of ˜De Nive Sexangula™ where the two regular packings of
spheres in the plane are drawn. Square (A) and triangular (B).



Now if you proceed to pack the solid bodies as tightly as possible, and
set the ¬les that are ¬rst arranged on the level on top of others, layer on
layer, the pellets will be either in squares (A in diagram), or in trian-
gles (B in diagram). If in squares, either each single pellet of the upper
range will rest on a single pellet of the lower, or, on the other hand,
each single pellet of the upper range will settle between every four of
Hard problems with hard spheres
32

the lower. In the former mode any pellet is touched by four neighbours
in the same plane, and by one above and one below, and so on through-
out, each touched by six others. The arrangement will be cubic, and the
pellets, when subjected to pressure, will become cubes. But this will
not be the tightest packing. In the second mode not only is every pellet
touched by it four neighbours in the same plane, but also by four in the
plane above and by four below, and so throughout one will be touched
by twelve, and under pressure spherical pellets will become rhomboid.
This arrangement will be more comparable to the octahedron and pyra-
mid. This arrangement will be the tightest possible, so that in no other
arrangement could more pellets be packed into the same container 15.

The structure here described by Kepler is cubic close packing, also called
¼¼ .
face-centred cubic (fcc). It has the greengrocer™s packing fraction
It is a regular structure: the local con¬gurations repeat periodically in space like
wall paper but in three dimensions. Such a periodic structure is now often called
crystalline because it corresponds to the internal structure of crystals.
Kepler™s work was the ¬rst attempt to associate the external geometrical
shape of crystals with their internal composition of regularly packed microscopic
elements. It was very unusual for his time, when the word ˜crystal™ was applied
only to quartz, which was thought to be permanently frozen ice.
Kepler asserted that the cubic close packing ˜will be the tightest possible,
so that in no other arrangements could more pellets be packed into the same
container™. Despite Kepler™s con¬dence this conjecture long resisted proof and
became the oldest unsolved problem in discrete geometry.


3.9 Marvellous clarity: the life of Kepler
Kepler was born in Weil der Stadt (near Leonenberg, Germany) in 1571. He was
originally destined for the priesthood, but instead took up a position as school
teacher of mathematics and astronomy in Graz.
When Kepler arrived in Graz he was 25 years old and much occupied with
astrology. He issued a calendar and prognostication for 1595 which contained
predictions of bitter cold, a peasant uprising and invasions by the Turks. All were
ful¬lled, greatly enhancing his local reputation.
Kepler was an enthusiastic Copernican. Today he is chie¬‚y remembered for
his three laws on planetary motion but his search for cosmic harmonies was much
broader, ranging from celestial physics to sphere packings.
Kepler™s personality has been described as ˜neurotically anxious™. Certainly
he had an unhappy personal life. The story goes that, in seeking to optimize the
partner for his second marriage, he carefully analysed the merits of no less than
½
Quoted from: Kepler 1966 The Six-cornered Snow¬‚ake translated by C Hardie (Oxford: Claren-
don).
Marvellous clarity: the life of Kepler 33




Figure 3.8. Johannes Kepler (1571“1630).


11 girls”before choosing the wrong one. The word ˜nerd™ may be inappropriate
for a giant of the Renaissance but it springs to mind.
On the other hand Kepler™s scienti¬c writing presents us with what he called
a ˜holy rapture™ of compelling power. One young scientist in this century who was
inspired by its fusion of scienti¬c insight and religious mysticism was
L L Whyte16 . This is his translation of the breathless cadenza from Kepler™s
Harmony of the Worlds.

But now, since eighteen months ago the ¬rst light dawned, since three
moons the full day, and since a few days the sunshine of the most mar-
vellous clarity now nothing holds me back: now I may give in to this
holy rapture. Let the children of men scorn my daring confession: Yes!
I have stolen the golden vessels of the Egyptians to build from them a
temple for my God, far from the borders of Egypt. If you forgive me, I
am glad; if you are angry I must bear it. So here I throw my dice and
write a book, for today or for posterity. I care not. Should it wait a
hundred years for a reader, well, God himself has waited six thousand
years for a man to read his work.

Whyte suggested that there should be a verb ˜to kepler, meaning to iden-
tify a conceivable form of order as an aim of search™. Perhaps it could have the
secondary meaning ˜to over-idealize real systems, in an attempt to scienti¬cally
analyse them™, as in Kepler™s search for a wife.

½
Whyte L L 1963 Focus and Diversions (London: Cresset Press).
Hard problems with hard spheres
34

3.10 Progress by leaps and bounds?
While the Kepler problem remained unsolved, many mathematicians contributed
to this study by offering something less than the full theorem that is required.
Gauss contributed to the problem by demonstrating that the face-centred cu-
bic structure is the densest crystalline 17 packing in three dimensions. But this
is not suf¬cient since denser local con¬gurations exist (such as the tetrahedral
con¬guration of four spheres mutually in contact) and therefore non-crystalline
structures could conceivably have packing fractions higher than that of the cubic
close packing.
Fejes T´ th reduced the problem to a ¬nite but impossibly large calculation:
o
˜It seems that the problem can be reduced to the determination of the minimum
of a function of a ¬nite number of variables™ 18 .
Often mathematicians set themselves the task of proving that the highest den-
sity must be lower than some value . This is an upper bound. With no thought
½ ¼ for an upper bound of , and with some subtlety
at all we can offer
much better values may be found. Obviously if we could show that 0.7404. . . is
an upper bound, then, we would also know we can reach it by the method of the
greengrocer. The ball game would be over, apart from questions of uniqueness.
A particularly nice bound is that of C A Rogers (1958); it is precisely the
packing fraction that we recognized as appropriate to a perfect tetrahedral packing
(which cannot exist), that is, ¼ . Better bounds have followed:
¼ (Lindsey 1987), ¼ ¿ (Muder 1988), 0.7731 (Muder 1993)
and others. There are older ones as well 0.828 (Rankin 1947), ¼ ¿ (Bich-
19
feldt 1929) .
This was progress by bounds but hardly by leaps. A proof of the original
proposition still seemed far off, until recently.




½
In which each sphere is in an equivalent position. The term lattice packing is also used as a syn-
onym.
½
Fejes T´ th L 1964 Regular Figures (New York: Pergamon).
o
½
Conway J H and Sloane N J A 1988 Sphere Packings, Lattices and Groups (Berlin: Springer).
Chapter 4

Proof positive?



4.1 News from the Western Front
It may be safely assumed that quite a few experts have devoted some small frac-
tion of their time to looking for a solution to the Kepler problem, rather as the
punter places a small bet on a long-odds horse. One would not want to stake
a whole career on it, but the potential rewards are attractive enough to compel
attention.
The problem was included in a celebrated list drawn up by David Hilbert at
the dawn on this century, which was like a map of the mathematical universe for
academic explorers and treasure hunters. We have already cited his challenge to
posterity in chapter 1. Some of his treasures were found from time to time, but
the key to Kepler™s conjecture lay deeply buried. As D J Muder said, ˜It™s one of
those problems that tells us that we are not as smart as we think we are™.
In 1991 it seemed that the key had ¬nally been found by Wu-Yi Hsiang. The
announcement of the long awaited proof came from the lofty academic heights
of Berkeley, California. Hsiang had been a professor there since 1968, having
graduated from Taiwan University and taken a PhD at Princeton. Few American
universities enjoy comparable prestige, so the mathematical community was at
¬rst inclined to accept the news uncritically. When Ian Stewart told the story in
1992 in his Problems of Mathematics, he described Hsiang™s work in heroic terms,
but wisely added some cautionary touches to the tale.
Many mathematical proofs are long and involved, taxing the patience of even
the initiated. There has to be a strong element of trust in the early acceptance of
a new theorem. So the meaning of the word proof is a delicate philosophical and
practical problem. The latest computer-generated proofs have redoubled this dif-
¬culty. In the present case, most of the mathematics was of an old-fashioned va-
riety, close to that of school-level geometry. Indeed Hsiang claimed that a retreat

35
Proof positive?
36

from sophistication to more elementary methods was one secret of his success.
Nevertheless his preprint ran to about 100 pages and was not easily digested even
by those hungry for information. As his colleagues and competitors picked over
the details, some errors became apparent.
This is not unusual. Another recent claim, of an even more dramatic result”
the proof of Fermat™s Last Theorem”has required some running repairs, but is
still considered roadworthy and indeed prizeworthy. However, Hsiang did not
immediately succeed in rehabilitating his paper.
Exchanges with his critics failed to reach a resolution. A broadside was
eventually launched at Hsiang by Thomas Hales in the pages of the splendidly
entertaining Mathematical Intelligencer. Hales™ piece lies at the serious end of
that excellent magazine™s spectrum but nevertheless it grips the reader with its
layers of implication and irony, most unusual in a debate on a piece of inscrutable
academic reasoning.
Despite the inclusion of some conciliatory gestures (˜promising programme™,
˜improves the method™) the overall effect is that of a Gatling gun, apparently punc-
turing the supposed proof in many places. Hales begins with the statement that
˜many of the experts in the ¬eld have come to the conclusion that [Hsiang™s]
work does not merit serious consideration™ and ends with a demand that the claim
should be withdrawn: ˜Mathematicians can easily spot the difference between
hand-waving and proof™.
Hsiang replied at length in the same magazine, protesting against the use of a
˜fake counter example™. Meanwhile Hales and others were themselves engaged in
de¬ning programmes for further work, as the explorer stocks supplies and makes
sketch-maps for a hopeful expedition. Indeed he was already at base camp.



A comment by Kantor on Hilbert™s 18th problem

Hilbert™s text gives the impression that he did not anticipate the
success and the developments this problem would have.
The hexagonal packing in plane is the densest (proof by Thue
in 1892, completed by Fejes in 1940). In space, the problem
is still not solved. Although there is very recent progress by
Hales. For spheres whose centres lie on a lattice, the problem
is solved in up to eight dimensions. The subject has various
rami¬cations: applications to the geometry of numbers, deep
relations between coding theory and sphere-packing theory, the
very rich geometry of the densest known lattices. (Kantor J M
1996 Math. Intelligencer Winter, p 27)
The programme of Thomas Hales 37

4.2 The programme of Thomas Hales
Mathematicians often speak of a ˜programme™ 1 upon whose construction they are
engaged, and do not mean a computer program. Rather, it is a tactical plan de-
signed to achieve some objective. Like mountaineers who wish to conquer Ever-
est, they de¬ne in advance the route and various camps which must be established
along the way. It is in this spirit that Thomas Hales has attacked the Kepler prob-
lem. He had established base camp when we set out to write this book. He had
proved a number of intermediate results and felt that the summit could be reached.
Hales™ programme was based on reducing the Kepler problem to certain lo-
cal statements about packing. Earlier we pointed to the impossibility of packing
regular tetrahedra (chapter 3), and saw the Kepler problem as one of ˜frustration™,
for this reason. But this does not mean that the global packing problem cannot be
reduced to a local one, in some more subtle sense.
Hales considers a saturated packing, which is an assembly of non-inter-
secting spheres where no further non-intersecting spheres can be added. He uses
shells: local con¬gurations made of a sphere and its surrounding neighbours. He
calculates the local density and a score, this quantity is associated with the empty
and occupied volume in the local packing around the sphere. The programme of
Hales was to prove that all the possible local con¬gurations have scores lower or
equal than 8.0, that is, the one associated with Kepler™s dense packing. This is
enough to prove Kepler™s conjecture.
Hales started the implementation of this programme around 1992. He soon
proved that a large class of local packings score less than eight, but there remained
a few local con¬gurations for which this proof was extremely tricky. In spring
1998 one could read on his home-page on the Internet: ˜When asked how long all
this will take, I leave myself a year or two. But I hope these pages convince you
that the end is in sight!™. He estimated that would take until year 2000 to ¬nish
the proof.
The main problem in this kind of proof is to ¬nd a good way to partition
a packing into local con¬gurations. This is a key issue: how does one properly
de¬ne ˜shells™ in the packing? All the major breakthroughs in the history of the
Kepler conjecture (including the Hsiang attempt) are associated with different
ways of partitioning space. In particular, there are two natural ways to divide the
space around a given sphere in a packing.
The ¬rst is the Vorono¨ decomposition (chapter 2). The Vorono¨ cell is a
± ±
polyhedron, the interior of which consists of all points of the space which are
closer to the centre of the given sphere than to any other. This was the kind of
decomposition adopted by Fejes T´ th to reduce the Kepler problem to the ˜de-
o
termination of the minimum of a function of a ¬nite number of variables™. But
this method meets with dif¬culties for some local con¬gurations, such as when
a sphere is surrounded by 12 spheres with centres on the vertices of a regular
½
Only east of the Atlantic are there extra letters which maintain a useful distinction between these
two spellings.
Proof positive?
38




Figure 4.1. The assembly of 12 spheres around a central one in a pentahedral prism con-
¬guration.


icosahedron. In this case the local packing fraction associated with the Voronoi
¼
cell is which is bigger than the value of the Kepler packing
¼ ¼ ) and its score is bigger than eight.
(
The second natural way of dividing space is the Delaunay decomposition.
Here space is divided in Delaunay simplexes which are tetrahedra with vertices
on the centres of the neighbouring spheres chosen in a way that no other spheres

. 1
( 4)



>>