An ef¬cient coding, which minimizes the energy necessary to transmit the infor-

mation, organizes these balls in the closest possible packing around the origin.

Therefore, the problem relates back to the greengrocer dilemma: how to arrange

these balls most tightly? Which is the maximum density of a packing of solid

spheres in dimensions?

It might be thought that this journey into many dimensions might be unevent-

ful: if you™ve seen one such space, you™ve seen them all? Surely some simple

generalization of the close-packing strategy which works in three dimensions can

be successfully extended? Not so. The possibilities are much richer than this and

include some startling special cases. Who would have thought that dimensions

8 and 24 are very special? In these cases structures of particularly high density

can be found. The eight-dimensional one is called E and dates from the last

century, while the 24-dimensional one was discovered by J Leech of Glasgow in

1965. New dense structures, indeed whole families of them, continue to be con-

structed. For example, in 1995, A Vardy announced a new packing record for 20

dimensions.

We have already seen in chapter 3 how close-packed hexagonal layers of

spheres may be stacked to generate the face-centred cubic lattice, the one de-

scribed by Kepler as ˜the most compact solid™. This is the regular packing with

the highest density in three dimensions. This procedure also works in many

dimensions: -dimensional compact structures are often stacked one upon the

other (or laminated) making an ( · ½)-dimensional packing. There are some

special dimensions where these laminated lattices have remarkable properties in

¾ , the laminated

terms of density and symmetry. A very special one is

lattice for which is the one discovered by Leech in 1965. It has a density of

¼ ¼¼½ ¿ and it is conjectured to be the densest lattice packing in 24 di-

mensions. This packing is highly symmetrical and the symmetry group associated

to it has fundamental importance in the history of group theory. Indeed, the dis-

covery of the Leech lattice in 1968 resulted in the discovery of three new simple

groups.

Group theory is an abstract branch of mathematics which is closely tied to

practical applications throughout physics. Simple groups make a special ¬nite

class of groups from which any ¬nite group can be built up. The largest simple

group, the ˜Monster™, was constructed by R L Griess in 1981 using the Leech

lattice. The classi¬cation of all simple groups was ¬nally completed in 1982 after

having involved the work of many mathematicians for over 50 years.

Low-dimensional sections of the Leech packing produce laminated pack-

¾ but curiously they also produce non-laminated ones.

ing in dimensions

Among them is the K ½¾ lattice ¬rst described by Coxeter and Todd in 1954, which

½¾.

is likely to be the densest lattice packing in

It has been proved that the laminated lattices (£ ) are the densest lattice

packings up to dimension . They are the densest known up to dimension 29

½¼ ½½ ½¾ ½¿ and it seems likely that K ½¾ , £½ and £¾ (the Leech

except for

Packing in many dimensions 115

Table 12.1.

Dimension Density Lattice

£

0 1 ¼

£

1 1 ,Z

½

¼¼ £

”

2 , A¾

¾

¾ ¿

¼¼ £

”

3 , A¿

¿

¿ ¾

¾

¼½ £

4 ,D

½

¾

”¼ £

5 ,D

½ ¾

¿

” ¼¿ ¾ £

6 ,E

¿

¿

¼¾ £

7 ,E

½¼

¼¾ ¿ £

8 ,E

¿

¼¼

12 K½¾

½ ¼

¼ ¼½ £

½

16 ½

½

½¾

¼ ¼¼½ ¿ £

24 ¾

½¾

lattice) are the densest in dimensions 12, 16 and 24. (See table 12.1, courtesy of

Conway.)

Note that even in the ˜very dense™ 24-dimensional Leech lattice, the volume

occupied by the spheres is less than 0.2% of the total. Indeed the density of sphere

packings tends to zero as the dimension goes to in¬nity.

˜Packings of Spheres Cannot be Very Dense™ is the title given by C A Roger

to a chapter of his book Packing and Covering (1964) where he calculates a bound

for the density of sphere packings in any dimension. His bound is calculated

from the generalization to high dimensions of the three-dimensional case of four

spheres in mutual contact with centres on the vertices of a regular tetrahedron

(section 3.10). In dimensions this con¬guration is made of · ½ mutually

contacting spheres. In the large limit it has density

½

” (12.1)

¾

These local con¬gurations of · ½ spheres cannot be tightly assembled in the -

space. Some interstices always remain and so is an upper bound for the density

of -dimensional sphere packings.

Other more restrictive bounds have been given during the years. Summariz-

ing these results, the density of the closest -dimensional packing is between the

bounds

¾ º º ´½ ½ µ (12.2)

Packings and kisses in high dimensions

116

for large . One can see that when the dimension increases by 1, the density of

the closest packing (lattice or non lattice) is divided by a number between 2 and

1.546. . . and therefore goes rapidly to zero when increases.

Magic dimensions

To understand why there are magic dimensions for which very special lattice

packings appear, let us consider the simple case of the hypercubic lattice pack-

ing. In this packing, spheres with unit radius are placed with the centres at posi-

tions ´¾™½ ¾™¾ ¾™ µ where ™ are integer numbers. In two dimensions this

is the square lattice packing, and the elementary local con¬guration is a set of

four spheres with the centres on the vertices of a square. In dimensions the

elementary local con¬guration of this packing is a -dimensional hypercube with

¾ spheres on its vertices. It is easy to see that in¬nite copies of this local con-

¬guration form the whole packing. Each interstice between the ¾ spheres can

”

½. In two dimensions this

” ”

accommodate a sphere with maximum radius

radius is ¾ ½ ¼ ½, in three dimensions it is ¿ ½ ¼ ¿, but in four

”

½ ½, which means that the sphere inserted in the

dimensions this radius is

interstice inside the cube can have the same unit radius of the external ones. Now,

two copies of the cubic packing can be ¬tted together without overlap to form a

new lattice packing with a density that is double the original one. This is known as

checkerboard lattice D , and is the densest lattice in four dimensions. In this pack-

ing the spheres have centres in the points ´¼ ¼ ¼ ¼µ ´½ ½ ¼ ¼µ ´½ ¼ ½ ¼µ . In

general in a packing D the spheres have centres in ´™ ½ ™¾ ™¿ ™ µ where the

™ are integers that add to an even number.

It is the doubling possibility that renders special the dimensions 8 and 24.

Indeed, in the packing D can be doubled in two copies that ¬t together

making the lattice packing E , the densest in . Analogously, in 24 dimen-

sions it is a doubling of a particular lattice packing associated with the Golay code

that forms the Leech lattice packing.

12.2 A kissing competition

How many spheres can be placed around a given sphere, such that they are all

of the same size and touch the central one? Mathematicians often refer to such

contact as ˜kissing™. This was the topic of a famous discussion between Isaac

Newton and David Gregory in 1694. Newton believed that the answer was 12, as

in the compact packing of Kepler, while Gregory thought that 13 was possible.

The problem is not simple. The solid angle occupied by an external sphere is

less than 1/13 of the total and the volume around the central sphere which is

available to touching spheres is, in principle, suf¬cient to contain the volumes of

13 spheres2 . But the correct answer is 12.

¾

In fact, the fraction is 1/13.397 33. . . , the same number which appears in the lower bound on the

average number of cells in a foam of minimal surfaces (chapter 7).

More kisses 117

Table 12.2. Known lower bounds for the kissing numbers up to dimension 10 and for

¾ . Boldface indicates bounds which are realized.

Dimension Kissing number

1 2

2 6

3 12

4 25

5 46

6 82

7 140

8 240

9 380

10 595

24 196 560

Note that a con¬guration of 13 spheres around a central one makes a very

compact packing without quite achieving contact of all spheres with the central

one. This is one of the local con¬gurations that locally pack more tightly than the

Kepler bound (chapter 3).

The 12 spheres can be disposed in the rhombic dodecahedron con¬guration,

in the icosahedral arrangement (where the 12 spheres are separated from each

other and touch only the central one) or in the pentahedral prism (with two spheres

at the north and south poles and ¬ve spheres around each of them). The ¬rst

con¬guration is the most compact global packing (the Kepler close packing). The

other two are packings that are locally more dense than the ¬rst one but that cannot

be continued in the whole space.

12.3 More kisses

As Newton and Gregory did for three dimensions, one can ask which is the great-

est value of the kissing number ( ) that can be attained in a -dimensional packing

of spheres. In one dimension the answer is clearly two, in two dimensions it is six

and in three dimensions the answer is 12. The answer is unknown for dimensions

¾ . In eight dimensions spheres arranged

above three except for and

in the lattice packing E touch 240 neighbours, and in 24 dimensions each sphere

kisses 196 560 neighbours in the Leech lattice £ ¾ . (See table 12.2.)

In dimension the highest known lower bound is 25. Dimension

is the ¬rst dimension in which non-lattice packings are known to be superior to

lattice packings. Here, £ has ¾ ¾ whereas the best bound known is 380.

Remember that the kissing number question aims to ¬nd the best local con¬gu-

Packings and kisses in high dimensions

118

Figure 12.1. Known kissing numbers and the Kabatiansky and Levenshtein bound.

ration (one sphere and its surroundings) while the sphere packing problem is a

global problem.

An upper bound for the attainable kissing numbers in high dimensions has

been calculated by Kabatiansky and Levenshtein who showed that

¾¼ ¼½ ½·“´½µ

(12.3)

(where “´½µ indicates and unknown number which must have a value of order 1).

In ¬gure 12.1 the values of for con¬gurations with a high kissing number

are reported together with the Kabatiansky and Levenshtein bound with exponent

¬xed at ¼ ¼¾ .

Chapter 13

Odds and ends

13.1 Parking cars

That parking can pose problems should come as little surprise to most of us.

For example, imagine a parking space of length Ü where cars of unit length

are parked one by one, completely at random. What, on average, is the maximum

number of cars … ´Üµ that can ¬nd a place in this space (without overlapping

between cars)?

It is always possible to obtain a packing fraction of one by systematically

putting each segment (car) in contact with two others. But if the segments are

disposed in a random way without overlapping and readjustment, then after a cer-

tain stage the line has no remaining spaces large enough to accommodate another

segment.

When cars are parked at random, R´ nyi 1 determined an integro-functional

e

equation that gives … ´Üµ in an implicit form. In the limit of an in¬nitely large

parking space the resulting packing fraction is

¼ (13.1)

The packing fraction and the average of the maximum number of cars are simply

related according to … ´Üµ Ü.

If the random packing is modi¬ed so that a car arriving can move slightly

(up to half segment length) in order to create an available space, then the packing

fraction increases to 0.809.

In the analogous two-dimensional problem, objects with a unit square shape

are placed in a rectangular parking lot. In this case no exact results are available.

½

R´ nyi A 1958 On a one-dimensional problem concerning random space-¬lling Publ. Math. Inst.

e

Hung. Acad. Sci. 3 109“27.

119

Odds and ends

120

Figure 13.1. Sausage packing of ¬ve balls. (Courtesy of J M Wills, University of Siegen,

Germany.)

Palasti (1960) conjectured that the two-dimensional packing fraction has the same

¼

value as in the one-dimensional case. But this conjecture remains

unproved and computer simulations suggest that the packing fraction is slightly

higher than the conjectured value.

13.2 Stuf¬ng sausages

All packings in the real world are ¬nite, even atoms in crystals or sand at the

beach. Finite packing problems have boundaries. This makes their solution more

dif¬cult than for in¬nite packings.

Optimal box for discs

How may we arrange Æ unit discs so as to minimize the area of the smallest

convex ¬gure containing all discs (the convex hull)? It has been shown for all

½¾¼ and for Æ ¿ ¾ ·¿ ·½, that the convex hull tends to be as hexagonal

Æ

as possible2 .

The sausage conjecture

The analogous problem in three dimensions is: how to arrange Æ unit spheres so

as to minimize the volume of the smallest convex ¬gure containing all spheres?

For Æ the best arrangements are conjectured to be ˜sausages™ (the centres

of the spheres all along a straight line). But larger Æ convex hulls with minimum

¨

¾

Wegner G 1986 Uber endliche Kreispackungen in der Ebene Stud. Sci. Math. Hungar. pp 1“28.

Filling boxes 121

volume tend to be associated with more rounded clusters. This might be called

the sausage“haggis transition.

For dimension it has been shown that the ˜sausage™ is the best solution

for Æ up to at least 377 000 3 . The Sausage Conjecture states that for

the arrangement of hyperspheres with a minimal volume convex hull is always a

˜sausage™4 .

13.3 Filling boxes

When objects are packed in spaces of ¬nite size and of given shape, new questions

arise. How many objects can be put inside a given box? Or equivalently, how big

must a box be to contain a given set of objects? Which is the best arrangement

and what is the density of this packing? Is the solution unique?

Let us consider the two-dimensional case ¬rst.

Discs in a circular box

Which is the smallest diameter of a circle which contains Æ packed discs of

diameter 1? The answer to this question is known up to Æ =10 and conjectures

are given for Æ up to 19. For Æ ½ the solution is clearly ½. For ¾ Æ

½ · ½ — ’´ ´Æ ½µµ for

½ · ½ — ’´ Æ µ, and it is

the answer is

. Whereas for Æ ½¼ one ¬nds

Æ .

Discs in a square

An analogous problem is to ¬nd the smallest size of the square containing Æ

½ ½ ¾ ¿.

packed unit circles. Exact results are known for Æ and Æ

Conjectures have been made for Æ ¾ .

For large Æ one has the approximate expression ³ ½ · ¾ ½¾½ Æ ½ ¾ . In

½

such a packing the density is, therefore,

Æ

³ ” ”” (13.2)

½¾ ¿ ½¾Æ

¾

which tends to the density of the hexagonal lattice for large Æ .

It turns out that for small Æ the hexagonal arrangement is not the best.

Square packing is better adapted to the square symmetry of the container and

it results in a denser packing certainly for Æ ¿ and probably up to Æ 5

.

¿

Gandini P M and Zucco A 1992 On the sausage catastrophe in 4-space Mathematika 39 274“8.

See Croft H T, Falconer K J and Guy R K 1991 Unsolved Problems in Geometry (New York:

Springer); Wills J M 1998 Spheres and sausages, crystals and catastrophes”and a joint packing theory

Math. Intell. 20 16“21.

See for general reference Melisson H 1997 Packing and Covering with Circles (Proefschrift Uni-

versiteit Utrecht, Met lit. opy.).

Odds and ends

122

Beer distributors should look into hexagonal packings now that they sell

cases of 18 or more cans: the superiority of square packing is not clear for rect-

angular boxes 6. (See table 13.1, from Croft 7 .)

½·½ Æ where is the Æ minimal separation between the Æ points in a

Table 13.1.

unit square.

Æ (side of the square)

1 1

½· ” ½

2 ¾

½· ” ” ½

3 ´ ¾´ ¿ ½µµ

”

4 2

½· ¾

5

½· ”

6 ½¿

½· ” ” ½

7 ¾´¾ ¿µ

½· ” ¾

8 ¿ ½

¿

9

½ · ” ” ¿

14 ¾

16

25

36

13.4 Goldberg variations

The sphere minimizes the surface area for a ¬xed volume, as the soap bubble

teaches us. In three-dimensional packing problems we need to consider shapes

which ¬t together to ¬ll space, and the problem of minimizing surface area is

not so easy. One interesting clue to the best strategy was provided by Michael

Goldberg in 1934.

Goldberg restricted himself to the case of a single polyhedron (not necessar-

ily space ¬lling) with Æ planar sides. What kind of polyhedron is best, in terms

of area?

He conjectured that the solution always has threefold (or trivalent) vertices.

Bearing in mind the ideal of a sphere, it is attractive to conjecture that the solution

is always a regular polyhedron, that is, one with identical faces. This is not always

possible. Goldberg™s conjecture, supported by a good deal of evidence, states that

the solution is always at least close to being regular, in the sense of having only

faces with ’ and ’ · ½ edges.

18 discs can be hexagonally packed in a pattern made of ¬ve lines of 4, 3, 4, 3, 4 inside a rectangular

box.

Croft H T, Falconer K J and Guy R K 1991 Unsolved Problems in Geometry (New York: Springer).

Packing pentagons 123

Figure 13.2. Goldberg polyhedra for Æ ½¾, 14, 15 and 16. They are the building-blocks

of the Weaire“Phelan and other foam structures (chapter 7).

½¾ and 14 are as shown in ¬gure 13.2.

In particular, the solutions for Æ

Although there is no rigorous chain of logic making a connection with the Weaire“

Phelan structure (chapter 7), it turns out to be the combination of these two Gold-

berg polyhedra.

13.5 Packing pentagons

Pentagons cannot be packed together, without leaving some free space. What is

the maximum packing fraction that can be achieved?

There are several obvious ways of arranging the pentagons in a periodic

structure. Figure 13.3 shows two of the densest ones. The structure with packing

fraction 0.92 is thought to be the densest, and it has been found in the air-table

experiments of the Rennes group (section 2.2).

Odds and ends

124

(a) (b)

Figure 13.3. Two dense packings of pentagons, with packing fractions 0.864 65 (a) and

0.921 31 (b).

13.6 Dodecahedral packing and curved spaces

Consider a (not necessarily ordered) packing of equal spheres. Construct around

any sphere the Vorono¨ cell (the polyhedron in which the interior consists of all

±

points of the space which are closer to the centre of the given sphere than to

any other, chapter 2). It was conjectured and proved very recently by Hales and

McLaughlin that the volume of any Vorono¨ cell around any sphere is at least

±

as large as a regular dodecahedron with the sphere inscribed. This provides the

following bound for the densest local sphere packing

” ”

·

Î—”

”” ¼

–

½¼´ ¾µ

(13.3)

“ –“’

Î “ –“’

This is 1% denser than the Kepler packing but this is a local arrangement of

13 spheres that cannot be extended to the whole space. Indeed, regular dodecahe-

dra cannot be packed in ordinary space without gaps.

The situation is similar to that for pentagons in two dimensions. Regular

pentagonal tiles cannot cover a ¬‚oor without leaving any interstitial space. How-

ever, in two dimensions one can immediately see that this close packing can be

achieved by curving the surface. The result is a ¬nite set of 12 closely packed

pentagons that tile the surface of a sphere making a dodecahedron. Analogously,

in three dimensions, regular dodecahedra can closely pack only in a positively

curved space. In this case regular dodecahedra pack without gaps making a closed

structure of 120 cells which is a four-dimensional polytope (that is a polyhedron

in high dimensions) 8.

´

See for general reference: Sadoc J F and Mosseri R 1997 Frustration G´ om´ trique (Paris: Editions

ee

Eyrolles).

The Malfatti problem 125

Figure 13.4. Malfatti™s solution to the problem.

It started with liquids, you know. They didn™t understand liq-

uids. Local geometry is non-space-¬lling. Icosahedra. Trig-

onal bipyramids. Oh, this shape and that shape, lots of them.

More than the thirty-two that ¬ll ordinary space, let me tell you.

That™s why things are liquid, trying to pack themselves in ¬‚at

space, and that™s what I told them.

They couldn™t deal with it. They wanted order, predictability,

regularity. Silly. Local geometry can be packed, I said, just

not in ¬‚at space. So, I said, give them a space of constant cur-

vature and they™ll pack. All they did was laugh. I took some

liquids to a space of constant negative curvature to show them

it would crystallize, and it sucked me up. (Tepper S S Mavin

Manyshaped (New York: Ace Fantasy Books).)

13.7 The Malfatti problem

A parsimonious sculptor wants to cut three cylindrical columns from a piece of

marble which has the shape of a right triangular prism. How should he cut it in

order to waste the least possible amount of marble? The problem is equivalent

to that of inscribing three circles in a triangle so that the sum of their areas is

maximized.

In 1802 Gian Francesco Malfatti (1731“1807) gave a solution to this problem

which thereafter bore his name. Previously Jacques Bernoulli had given a solution

for a special case. In due course other great mathematicians were attracted to it,

including Steiner and Clebsch. Malfatti assumed that the three circles must be

mutually tangent and each tangent to only two sides of the triangle. Under this

assumption the Malfatti solution follows as in ¬gure 13.4.

The problem was considered solved and for more than 100 years nobody

noticed that the Malfatti arrangement shown in ¬gure 13.4 is not the best. For

instance, for an equilateral triangle, the solution of ¬gure 13.5(a) is better than

Malfatti™s one shown in ¬gure 13.5(b). Howard Eves (1965) observed that if the

Odds and ends

126

Figure 13.5. Solutions to the Malfatti problem.

triangle is elongated, three circles in line (as in ¬gure 13.5(c)) have a much greater

area than those of ¬gure 13.5(d).

Finally in 1967, Michael Goldberg showed that the Malfatti con¬guration

is never the solution, whatever the shape of the triangle! The arrangements in

¬gure 13.5(e,f ) are always better. Goldberg arrived at this conclusion by using

graphs and calculations. A full mathematical proof has yet to be produced 9.

13.8 Microspheres and opals

Oranges do not spontaneously form close-packed ordered structures but atoms

sometimes do. Where is the borderline between the static world of the oranges

and the restless, dynamic one of the atoms, continually shuf¬‚ed around by thermal

From Stanley Ogilvy C 1969 Excursion in Geometry (New York: Dover) p 145; 1932 Periodico di

Mathematiche 12 (4th series) is a complete review.

Order from shaking 127

energy”between the church congregation and the night-club crowd?

At or near room temperature, only objects of size less than about 1 m are

effective in exploring alternatives, and perhaps ¬nding the best. A modern in-

dustry is rapidly growing around the technology of making structures just below

this borderline, in the world of the ˜mesoscopic™ between the microscopic and the

macroscopic.

In one such line of research, spheres of diameter less than a micrometre

are produced in large quantities and uniform size using the reaction chemistry

of silica or polymers. Such spheres, when placed in suspension in a liquid, may

take many weeks to settle as a sediment. When they do so, a crystal structure is

formed”none other than the fcc packing of earlier chapters. This crystallinity is

revealed by striking optical effects, similar to those which have been long admired

in natural opal.

Natural opals are made of silica spheres of few hundred nanometres (½ ’‘

‘) in size, packed closely in an fcc crystalline array. Opals are therefore

½¼

made of a very inexpensive material but they are valued as gemstones because

their bright colours change with the angle of view. This iridescence is due to

the interference of light which is scattered by the ordered planes of silica spheres.

Indeed the size of these spheres is typically in the range of visible light wavelength

(430“690 nm).

An important goal of present research in material science is the creation of

arti¬cial structures with such a periodicity, in order to tailor their optical proper-

ties. Several studies begun in the late 1980s showed that a transparent material can

become opaque at certain frequencies provided that a strong and periodic modu-

lation of the refractive index is imposed in space. Structures with these properties

have been constructed for microwave radiation but, until recently, not for visible

light. With conventional microelectronic techniques it is very dif¬cult to shape

structures below 1000 nm (which is 1 m). Arti¬cial opals provide the right

modulation in the diffraction index, opening the way to the construction of new

˜photonic band gap™ materials. Photonic crystals are the ingredients for future

optical transistors, switches and ampli¬ers, promising to become as important to

the development of optical devices as semiconductors have been to electronics.

13.9 Order from shaking

A home-made experiment of spontaneous crystallization can easily be performed

in two dimensions by putting small beads on a dish and gently shaking it. The

result is the triangular arrangement shown in ¬gure 13.6.

Large spheres in a box are not so easily persuaded to form a crystal, but

nevertheless shaking them can have interesting effects.

It was observed in the 1960s that repeated shear or shaking with both vertical

and horizontal motion can increase the density of the packing. Recently a density

of 0.67 was obtained in a packing of glass beads of about 2 mm in diameter slowly

Odds and ends

128

Figure 13.6. Spontaneous ˜crystallization™ into the triangular packing induced by the shak-

ing of an initially disordered arrangement of plastic spheres on a dish.

poured into a container subject to horizontal vibrations 10 . This packing consists of

hexagonal layers stacked randomly one upon the other with few defects. Sponta-

neous crystallization into regular fcc packing was also obtained when the starting

substrate was forced to be a square lattice.

This packing has the minimum potential energy under gravity. The system

spontaneously ¬nds this con¬guration by exploring the possible arrangements un-

der the shaking. The slow pouring lets the system organize itself layer upon layer.

This is analogous to what happens in the microspheric suspensions of a previ-

ous section where the sedimentation is very slow and the shaking is provided by

thermal motion.

½¼

Pouliquen O, Nicolas M and Weidman P D 1997 Crystallization of non-Brownian Spheres under

horizontal shaking Phys. Rev. Lett. 79 3640“3.

Segregation 129

Figure 13.7. Why are Brazil nuts always on top?

13.10 Segregation

Sorting objects of miscellaneous size and weight is a key industrial process. Fil-

tration, sieving or ¬‚otation may be used. With granular materials it is often

enough to shake the mixture for some time. This must be done judiciously; vig-

orous shaking (as in a cement mixer) will produce a uniform mixture. Gentle

agitation, on the other hand, can promote the segregation of particles of different

sizes. The result is quite surprising: the larger, heavier objects tend to rise! This

seems an offence against the laws of physics but it is not. That is not to say that

it is easily explained. Numerous research papers, including the teasingly entitled

˜Why the Brazil Nuts are on Top™ have offered theories 11 .

Figure 13.7 shows a simulation of the effect. It is thought to be essentially

geometric: whenever a large object rises momentarily, smaller ones can intrude

upon the space beneath. Such an explanation calls to mind the manner in which

many prehistoric monuments are thought to have been raised. Note that the en-

ergy increases as the Brazil nut is raised, contradicting intuition and naive rea-

soning. This is not forbidden, because energy is being continuously supplied by

shaking.

By slowly pouring a mixture of two kinds of grain of different sizes and

shapes between two narrow layers of glass, one can observe that the grains sepa-

rate or, under some circumstances, stratify into triangular strips (see ¬gure 13.8).

Large grains are more likely to be found near the base of the pile whereas the

smaller are more likely to be found near the top. The phenomenon is observable

for mixtures of grains in a wide range of size ratios (at least between 1.66 to 6.66

½½

Rosato A, Strandburg K J, Prinz F and Swendsen R H Why the Brazil nuts are on top: size segre-

gation of particular matter by shaking Phys. Rev. Lett. 58 1038.

Odds and ends

130

Figure 13.8. Segregation and strati¬cation in a granular mixture of brown and white sugar

poured between two glass plates.

as reported by Makse et al 12 ). When the large grains have a greater angle of re-

pose13 with respect to the small grains then the mixture strati¬es into triangular

strips. (This can be achieved by making the small grains smooth in shape and

the large grains more faceted.) For instance, a mixture of white and brown sugar

works well for this purpose.

Fineberg has suggested that Cinderella could have utilized this spontaneous

separation phenomenon (instead of help from the birds) when the step-sisters

threw her lentils into the ashes of the cooking ¬re.

13.11 Turning down the heat: simulated annealing

If a suit is to be made from a roll of cloth, how should we cut out the pieces in

such a way as to minimize wastage? This is a packing problem, for we must come

up with a design that squeezes all the required shapes into the minimum area.

No doubt tailors have had traditional rules-of-thumb for this but today™s au-

tomated clothing industry looks for something better. Can a computer supply a

good design?

This type of problem, that of optimization, is tailor-made for today™s pow-

erful computers. The software which searches for a solution does so by a com-

bination of continual small adjustments towards the desired goal, and occasional

½¾

Makse H A, Halvin S, King P R and Stanley E 1997 Spontaneous strati¬cation in a granular mixture

Nature 386 379“82; Fineberg J 1997 From Cinderella™s dilemma to rock slides Nature 386 323“4.

½¿

The angle of repose is the maximum angle of slope in a pile of sand, beyond which it suffers

instability in the form of avalanches.

Turning down the heat: simulated annealing 131

Figure 13.9. Propagation of stress lines in a disordered packing of discs.

random shuf¬‚ing of components in a spirit of trial and error”much the way that

we might use our own intelligence by a blend of direct and lateral thinking.

A particularly simple strategy was suggested in 1983 by Scott Kirkpatrick

and his colleagues at IBM. Of course, IBM researchers are little concerned with

the cutting (or even the wearing) of suits, but they do care passionately about

semiconductor chip design, where a tiny competitive advantage is well worth a

day™s computing 14. The components in microchips and circuit boards should be

packed as tightly as possible, and there are further requirements and desired fea-

tures which complicate the design process.

The research in question came from the background of solid state physics.

Nature solves large optimization problems all the time, in particular when crystals

grown as a liquid are slowly frozen. Why not think of the components of the suit

or the chip as ˜atoms™, free to bounce around and change places according to the

same spirit of laws which govern the physical world, at high temperatures? Then

gradually cool this imaginary system down and let it seek an optimum arrange-

ment according to whatever property (perhaps just density) is to be maximized.

This is the method of ˜simulated annealing™, the second word being taken

½

Kirkpatrick S, Gelatt C D and Vecchi M P 1983 Optimization by simulated annealling Science 220

671.

Odds and ends

132

from the processing of semiconductors, which are often heated and gradually

cooled, to achieve perfection in their crystal structure.

The idea was simple and it is relatively straightforward to apply”so much so

that incredulous circuit designers were not easily persuaded to try it. Eventually

it was found to be very effective, and hence it has taken its place among the

optimizer™s standard tools. Its skilful use depends on de¬ning a good ˜annealing

schedule™, according to which the temperature is lowered.

The mathematical background to these large and complicated optimization

problems is itself large and complicated. Complexity theory often offers the

gloomy advice that the optimum solution cannot be found in any practical amount

of time, by any program. But, unlike the pure mathematician, the industrial de-

signer wants only a very good packing, not necessarily the best. Beyond a certain

point, further search is pointless, in terms of pro¬t. As Ogden Nash said: ˜A good

rule of thumb, too clever is dumb™.

Chapter 14

Conclusion

We stated at the outset that examples of packing would be drawn from a wide ¬eld

of mathematics, science and technology. Have we revealed enough connections

between them to justify their juxtaposition within the same covers? Recall the

recurrence of the greengrocer™s stacking in the search for dense lattices in higher

dimensions and the threefold interconnection of metallic alloys, chemical com-

pounds and the ideal structure of foam. Such was the doctrine of Cyril Stanley

Smith (1903“92), who called himself a ˜philomorph™ or lover of form. He was

fascinated by such similarities. This is no mere aesthetic conceit: it gives power to

the method of analogy in science. Smith rebelled against the narrow orthodoxies

of conventional science. He saw in materials a richness of form, upon which he

speculated in terms of complexity, analogy, hierarchy, disorder and constraints.

If we have given offence to any specialist in this attempt to follow the exam-

ple of Smith, by over-simpli¬cation or neglect, we are sorry for that. Scientists,

he said, should be allowed to play, and we would rest our case on that.

Smith would have enjoyed being on a bus taking a party of physicists (which

included several philomorphs) to the airport after a conference in Norway in 1999.

A brief ˜comfort stop™ was planned at a motorway service station which included

a small shop. Several of the party disappeared for a time. They had discovered

something remarkable in the shop”a close packing of identical tetrahedral car-

tons! This clever arrangement is possible only because it uses slightly ¬‚exible

cartons and the container (which has an elegant hexagonal shape) is ¬nite. We

would like to give the details but the bus had to leave for the airport. . .

133

Index

£½ , 114 Cauchy, 78

£¾ , 114 CdSO , 27

cellular structures, 54

Almgren, F, 64 cement, 26

AlMn alloys, 87 Chan, J W, 87

amorphous solids, 89 clathrates, 72

amorphous structures, 22 concrete, 91

angle of repose, 130 Conway, J H, 113

aperiodic structures, 88 Coxeter, H S M, 44, 68, 114

Apollonian packing, 16, 93 crystal, 13, 32, 75

Apollonius of Perga, 91 crystalline packing, 34, 83

Archimedean solids, 68 crystalline structures, 13, 34

Archimedean tessellations, 13 crystallography, 75, 82

Archimedes, 91 Curie, P, 83

Aristotle, 77 curved spaces, 124

Barlow, William, 80 Darwin, C, 55

bee, 54, 57 De Nive Sexangula, 30, 31

Bernal, J D, 20 Delaunay decomposition, 38

Bernal packing, 22 dense random packing, 24

biological cells, 50 Descartes, 91

Blech, I, 87 dilatancy, 26

body-centred cubic lattice (bcc), 85 Dirichlet, P G, 18

Boscovitch, R J, 78 disorder, 15

bounds, 34 dodecahedral packing, 124

Boyle, R, 59 Douglas, J, 65

Boys, C V, 60

Bragg, W L, 83 E , 114

Brakke, K, 71 equal shares, 6

Bravais lattices, 82 ether, 66, 78

bubbles, 45, 59 Euclid, 91

buckminsterfullerene, 106 Euler, 9

buckyballs, 105, 106 Euler™s theorem, 9, 105

C ¼ , 106 face-centred cubic (fcc), 32, 83

134

Index 135

Faraday, M, 60 Kepler, J, 30, 32, 48, 88

Fejes T´ th, L, 8, 34, 55, 58

o Kepler Problem, 27, 29

foams, 45, 59 Kirkpatrick, S, 131

fractal, 16, 91 kissing, 93, 116

fractal dimension, 16, 94 Kusner, R, 46

Frank and Kasper faces, 86

Lamarle, E, 63

frustration, 29

Laplace™s law, 61

Gaudin, M-A, 75 Larmor, J, 78

Giant™s Causeway, 97 lattices, 13, 82, 114

Gibbs, J W, 83 Laue, M, 83

global optimization, 11 Leech lattice, 115, 117

Goldberg, M, 122 Leech, J, 114

golden ratio, 15 liquids, 22, 125

golf balls, 103 local optimization, 11

Gosset™s equation, 96 loose packings, 27

granular aggregate, 95 loose random packing, 24

granular packing, 25, 91

Malfatti problem, 125

Gratias D, 87

Mallett, R, 100

greengrocer™s packing fraction, 32

Mandelbrot, B, 64

Ha¨ y, R I, 78

u Maraldi angle, 57

Hales, S, 45 Marvin, J W, 52

Hales, T, 36, 39 Matzke, E B, 53, 70

Harriot, T, 29 Maxwell, J C, 61, 66

helical arrangements, 111 microspheres, 126

Hertz, H R, 67 minimal surfaces, 65

high dimensions, 113 Morgan, F, 56

Hilbert™s 18th problem, 2, 36

NaCl, 84

honeycomb, 54

nanotubes, 106, 111

honeycomb conjecture, 56

Navier, C, 78

Hooke, R, 50

Neptunists, 97

Hsiang, W-Y, 35

Nernst, W, 82

Huygens, C, 78

non-periodic, 88

Hyde, G B, 83

number of faces, 53, 71

ice, 72 number of neighbours, 52

icosahedral symmetry, 87, 103

O™Keeffe, M, 83

K½¾ , 114 opals, 126

Kabatiansky and Levenshtein

bound, 118 packing fraction, 5, 22, 24, 32, 119

Kelvin cell, 68 parking cars, 119

Kelvin™s bed-spring, 69 patterns, 50

Kelvin, Lord, 23, 65 Penrose tiling, 88

Index

136

pentagonal dodecahedron, 52, 103 simulated annealing, 131

pentagons, 123 Sloane, N J A, 113

pentahedral prism, 38 Smith, C S, 9, 64, 102, 133

Phelan, R, 72 snow¬‚akes, 48, 80

phyllotaxis, 111 soccer balls, 103

Plateau™s laws, 61 Soddy, F, 93, 95

Plateau, J A F, 57, 60 space-¬lling packing, 49

Plato, 77 surface evolver, 71

Pliny, 54

Tammes problem, 108

pomegranate, 48

Taylor, J, 64

principle of minimal area, 63

tetrahedrally close packed (tcp), 86

proof, 35, 42

tetrahedrally packed, 85

Q-systems, 38 tetrakaidecahedron, 50, 52, 68

quasi-ordered, 13 Thompson, D™A W, 57

quasicrystals, 17, 87 Thomson problem, 107

quasiperiodic, 88 Thomson, J J, 25, 107

Thomson, W, 65

R¨ ntgen ray, 82

o threefold vertex, 49

random packing, 20, 24 triangular close packing, 5, 8

regular dodecahedra, 46, 50 Tutton, A E H, 90

regular tessellation, 12 Tyndall, J, 89

Reynolds, O, 24, 25

rhombic dodecahedra, 50, 52 Vardy, A, 114

rigid packing, 27 Vegetable Staticks, 45

Rogers, C A, 9, 34 vertex connectivity, 49

Vorono¨ construction, 9, 16, 37, 49

±

saturated packing, 37 Vulcanists, 97

segregation, 129

semi-regular tessellations, 13 Wigner“Seitz, 19

Senechal, M, 87 Wollaston, W, 79, 80

Shechtman, D, 87

x-ray, 82

Sierpi´ ski Gasket, 91

n

Sierpi´ ski, W, 91

n