. 4
( 4)

information can be reliably recovered only if these balls are non-overlapping.
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
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
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
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
¾  º º ´½ ½ µ  (12.2)
Packings and kisses in high dimensions

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

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

¾¼ ¼½ ½·“´½µ

(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
When cars are parked at random, R´ nyi 1 determined an integro-functional
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.
Hung. Acad. Sci. 3 109“27.

Odds and ends

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

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

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
½· ¾
½· ”
6 ½¿
½· ” ” ½
7 ¾´¾  ¿µ

½· ” ¾
8 ¿ ½
½ · ”  ” ¿
14 ¾

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
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

(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
” ”
”” ¼

½¼´   ¾µ
“ –“’
Î “ –“’

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
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
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

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
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

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
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

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
Odds and ends

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


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. . .


£½ , 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

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

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
Sierpi´ ski, W, 91


. 4
( 4)