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