Covering and packing want different lattices

A lattice has two natural radii, and they are asked by opposite questions.

Packing. How large can equal spheres centred on the lattice points be before they overlap? Half the shortest vector, with no argument needed: two spheres of that radius touch, and no pair of points is closer.

Covering. How large must they be before they leave no gap? The distance from the lattice to the point of space furthest from it — which is a corner of the Wigner–Seitz cell, since the furthest point from the lattice is the furthest point of the cell from its own centre.

Both are radii of the same cell: the packing radius is its inradius, the covering radius its circumradius. The ratio between them measures how round the cell is, and a round cell is good at both questions at once.

So the natural guess is that one lattice is best at both. In the plane it is right. In space it is wrong, and the failure is the reason the two questions have separate literatures.

The plane, where the guess holds #

The hexagonal lattice packs the plane at density π/√12 = 0.9069, which is the best any lattice does and — by a much harder theorem — the best any arrangement of equal circles does.

It also covers the plane most thinly: a covering by circles of the covering radius has a thickness of 2π/√27 = 1.2092, meaning the average point of the plane lies in 1.21 circles. Every other lattice does worse at both.

The reason the two agree is the cell’s shape. Among all plane lattices of a given area, the hexagonal one has the roundest Voronoi cell — a regular hexagon, whose circumradius exceeds its inradius by only 2/√3 = 1.1547. Both questions reward roundness, so both have the same answer.

Space, where they part #

Face-centred cubic packs space at π/(3√2) = 0.7405, which is the densest lattice packing and — since Hales’s proof in 1998 — the densest packing of any kind.

Its covering is not the thinnest. The body-centred cubic lattice covers space with a thickness of 1.4635 against fcc’s 2.0944, which is not a small difference: fcc needs spheres nearly half again as large in volume to cover what bcc covers.

The reason is the shape of the deep hole. In fcc the Voronoi cell is a rhombic dodecahedron with vertices at two different distances from the centre, and the further ones are far: the octahedral hole in a close packing is a long way from every atom. In bcc the cell is a truncated octahedron, whose vertices are all at nearly the same distance, and it is that near-uniformity that makes the covering thin.

The two figures of merit, and why they are not radii #

The radii are lengths, so they depend on the scale of the lattice and cannot be compared between lattices directly. The quantities that can be compared are dimensionless.

Density is the fraction of space the packing spheres fill: the volume of a sphere of the packing radius, divided by the volume of the cell. It is at most one and larger is better.

Thickness is the same ratio computed with the covering radius: the average number of covering spheres a point lies in. It is at least one and smaller is better.

Both are ratios of a ball’s volume to a cell’s, so both are invariant under scaling and both are properties of the lattice’s shape. That is what makes the comparison meaningful — an fcc lattice with a large cell and one with a small cell have the same density and the same thickness, and the ordering between lattices does not depend on anybody’s choice of unit.

And both are ratios of the two radii in disguise. In dimension d the density is proportional to (packing radius)ᵈ over the cell volume, the thickness to (covering radius)ᵈ over the same volume, so the product of one and the reciprocal of the other is the ratio of the radii raised to the dimension. A cell whose two radii are close has a good density and a good thickness at once, and the dimension is the exponent amplifying the difference.

The ratio of the radii orders the plane lattices by itself #

The four plane lattices measured here all have the same packing radius, because each has been scaled so that its shortest vector is one, and that makes the ratio of the two radii the only thing separating them. Read down the covering column and the ordering is hexagonal 0.5774, oblique 0.6653, square 0.7071, rectangular 0.8602 — which is exactly the ordering by density, 0.9069, 0.7140, 0.7854, 0.5610, except that the square and the oblique change places.

That exception is worth a moment, because it is the plane’s small version of what space does at greater volume. The oblique lattice here covers better than the square one and packs worse. Its cell has a longer diagonal in one direction and a shorter one in the other, so its worst corner is nearer than the square’s while its area per point is larger; density counts the area and thickness counts the worst corner, and the two disagree. Nothing in the plane makes the disagreement large, because the hexagonal lattice wins both and there is only so far from it any plane lattice can be. In space the same disagreement has more room to work in — three dimensions raise both quantities to the third power rather than the second — and it separates fcc from bcc.

So the plane’s tidy answer is not a different phenomenon from space’s untidy one. It is the same phenomenon with less room, and the exponent is the dimension.

Duality, which is why it is these two #

Face-centred and body-centred cubic are duals: the reciprocal lattice of one is the other, up to a scale. That relation is the reason the two optimisations separate, and it is worth seeing why.

Packing is about the shortest vector — the closest pair of points. Covering is about the deepest hole — the point furthest from all of them. Dualising a lattice exchanges the roles of those two quantities in a rough but real sense: a lattice with a very short vector has a dual with a very shallow hole, and vice versa.

So a lattice cannot be extreme in both directions at once unless it is self-dual, and in the plane every lattice is — the dual is the same lattice turned through a right angle, whatever the lattice — which is exactly the situation in which the two answers can coincide. In space neither fcc nor bcc is self-dual, and the two questions go to the two ends of the same dual pair.

It is worth being careful about how much that argument proves, because it is an explanation rather than a theorem. Duality does not literally exchange the packing radius and the covering radius; there is no identity saying that one lattice’s shortest vector is the reciprocal of its dual’s deep hole. What is true is softer and still useful: the transform that makes a lattice’s shortest vector long makes its dual’s cell wide, and a wide cell has a deep corner. So the two optima are pushed apart by the same operation that relates the two lattices, and the fact that the winners here are a dual pair is a consequence one should expect rather than one that has been derived.

The self-dual case is where the argument has nothing to push against, and that is the plane’s whole story in one line. A lattice that is its own dual up to rotation and scale cannot be pushed in one direction without being pushed in the other, so its two radii move together and one lattice can be extremal for both.

In the plane that case is not a special one: it is every lattice. UᵀGU is the adjugate of G for the right-angle basis change and for every Gram there is, so a plane lattice’s dual is always the lattice itself, rotated and scaled — which is why the duality argument has nothing to push against anywhere in the plane and why the two prizes can go to one winner. This essay said for a phase that the hexagonal lattice was the only self-dual plane lattice; the identity is an essay of its own and it has no exceptions.

In three dimensions self-duality is a condition and a strong one — the primitive cubic lattice satisfies it and the face-centred and body-centred ones are duals of each other — and the self-dual lattices are not extremal for either question, which is why space has no candidate for both prizes and has to hand them out separately.

How the covering radius is measured here #

The packing radius is exact: half the shortest vector, found by enumeration over a bounded window of integer combinations.

The covering radius is not exact, and the method is stated rather than hidden. A grid is laid over the fundamental cell, each point’s distance to the nearest lattice point is computed, the worst is taken, and the neighbourhood of the worst is then refined by halving steps. That is a measurement with a resolution, and every value reported here carries the grid it was found on.

Two checks keep it honest.

The deep hole must be deep. No lattice point may be nearer to it than the radius claims, which is checked directly.

And nothing may be left uncovered. Every point of an independent, finer grid must lie within the reported radius of some lattice point. A covering radius that is too small by a hair fails this and would otherwise be a number that looks right and leaves a hole.

The cubic lattice is the calibration: its covering radius is exactly half the body diagonal, (√3/2)a, and its packing radius exactly half an edge. The search reproduces both to seven decimal places, which is what licenses the values for the lattices where no closed form is being checked against.

What the two radii are for #

The packing radius is the physical one. Atoms of one element in a metal are, to a first approximation, hard spheres, and close packing is what they do. The packing fraction is a real quantity about a real material, and the difference between 0.74 for close packing and 0.68 for body-centred is why most metals are one of the two.

The covering radius is the awkward one, and it is about the holes. The deep hole, which is a vertex of the cell nobody chose, is where an interstitial atom goes — carbon in iron, hydrogen in palladium — and its size decides which interstitials fit. In fcc — the arrangement two stackings share — the octahedral hole is large, which is why austenite dissolves far more carbon than ferrite does; in bcc the holes are smaller and more numerous.

So the two radii are not an abstract pair. One says how much of the space the atoms occupy and the other says how big the empty places are, and a structure’s chemistry often depends more on the second.

A sanity check the numbers have to pass #

Two inequalities hold for every lattice in every dimension, and any computation of these radii can be checked against them before anything else is believed.

The covering radius is at least the packing radius. A sphere of the packing radius on each point leaves gaps; a covering leaves none; so the covering radius cannot be smaller. Equality would mean a lattice whose spheres touch and leave nothing over, which happens in no dimension at all.

And the thickness is at least one. Covering spheres overlap, so the total volume of one per cell exceeds the cell’s volume. A thickness below one would be a covering using less material than the space it covers.

Every row of the table satisfies both, which is not a demanding test and is exactly the kind that catches a misplaced factor of two. The cases where a computation of this sort goes wrong are rarely subtle: a radius squared instead of cubed, a primitive cell’s volume used with a conventional cell’s vectors, a grid that never reached the deep hole. All three would show as an inequality failing rather than as a plausible wrong number, which is the argument for computing quantities that have known bounds.

Where the exactness stops #

Three limits.

Lattice packings only. Every number here is about spheres centred on a lattice. The densest packing of any kind is a separate and much harder question — settled in the plane by Thue and in space by Hales, in both cases coinciding with the best lattice, and not coinciding in dimension ten and above, where the best known packings are not lattices.

Small dimensions only. The pattern of which lattice wins which prize does not continue tidily. In dimension twenty-four the Leech lattice is extremal for both and by an enormous margin; in most other dimensions neither optimum is known.

And the covering radius is measured. Its values here are searched for and refined, with a stated resolution and two independent checks. The exact values for the cubic cases are reproduced to seven places; the others are as good as the grid.

One more use, which is not about atoms #

The two radii have a second life in a subject with no crystals in it, and the vocabulary is worth knowing because it is where most of the modern results come from.

A lattice is a code: the points are messages, and a received signal is decoded to the nearest one. Then the covering radius is the worst-case error the code can correct, and the packing radius is the largest error it can be guaranteed to correct. A good code wants both radii close together, for exactly the reason a good cell is round — the difference between them is the region where decoding is ambiguous.

That is why the same lattices keep appearing: the ones extremal for packing are the ones with good codes, and the Leech lattice in twenty-four dimensions, which is the best known at both, is also the basis of a code used in deep-space communication.

The crystallography and the coding theory are the same computation with different words on it, and the dictionary is short: shortest vector, minimum distance; Voronoi cell, decoding region; packing density, rate.

A third quantity, which ranks them differently again #

Two radii already disagree about which lattice is best. There is a third quantity of the same family, it is an integer rather than a length, and it produces a third ordering.

The kissing number is how many lattice points sit at the shortest distance from a given one — how many spheres touch one sphere in the packing. It is not a radius and it is not a ratio; it is a count, and it is the single most robust thing about a lattice, since it survives any scaling and any change of basis.

In the plane the hexagonal lattice’s kissing number is six and no arrangement of equal circles does better. In space the face-centred cubic lattice’s is twelve, and whether thirteen was possible was the subject of a recorded disagreement between Newton and Gregory in 1694 that took until 1953 to settle — Newton was right, and the reason it took so long is that twelve spheres round one leave enough slack to move about, so the impossibility of a thirteenth is not visible in any picture.

Body-centred cubic has a kissing number of eight, so it loses on this measure to the lattice it beats at covering. Three quantities, three orderings, and no one lattice ahead on all of them — which is the essay’s thesis with a third instrument confirming it rather than a second.

Where the answers are known, and where they stop #

It is worth being explicit about the status of each claim in the neighbourhood, because these problems are famous and their difficulty is wildly uneven.

Packing in the plane is settled for all arrangements, not merely lattices, and has been since Thue and Fejes Tóth. Packing in space was settled for lattices by Gauss in 1831 and in general by Hales in 1998, three and a half centuries after Kepler asked it.

Covering in the plane was settled by Kershner in 1939 — the hexagonal lattice again. Covering in space was settled for lattices by Bambah in 1954, and the answer is the body-centred cubic lattice, which is where the claim above comes from. The general covering problem, over arrangements that are not lattices, is open.

And in high dimensions the pattern breaks in both directions at once. Dimensions eight and twenty-four are the two where everything is known and everything agrees: the E₈ lattice and the Leech lattice are optimal packings, proved by Viazovska in 2016 and by Cohn, Kumar, Miller, Radchenko and Viazovska in 2017, and both have kissing numbers — 240 and 196,560 — that are known to be optimal too. Between and beyond them, almost nothing is settled; the best lattice packing is unproven in every dimension from four upwards except those two, and the best covering is unknown in most.

So the neat table on this page is a report from the two dimensions where the questions have answers. That the plane’s champion wins both prizes is a fact about the plane, not a principle, and the very next dimension is where it stops being true. It is worth reading the rest of this collection’s lattice arithmetic in that light: the fourteen are a complete classification because three dimensions is small, and every extremal question asked of them is a question whose general form is open.

Who worked it out #

The packing problem is the old one: Kepler conjectured the answer for space in 1611, Gauss proved it for lattices in 1831, and Hales settled the general case in 1998 with a proof whose verification took a decade and whose formalisation took another.

The covering problem is younger and less finished. Kershner proved the plane’s answer in 1939. Bambah proved that bcc is the thinnest lattice covering of space in 1954, and the general (non-lattice) covering problem in space is still open. The thinnest coverings in higher dimensions are known in only a handful of cases, and the lattices achieving them — the duals of the root lattices — are a different family from the packers.

Rogers’ monograph of 1964 set both problems side by side, and the observation that they are not the same problem is, in a subject where they are so often assumed to be, the useful contribution.

Where the ladder goes next #

Downwards, into the cell itself. Five parallelohedra and no others classifies the shapes a Voronoi cell of a space lattice can take, and the two radii are the inradius and circumradius of those five shapes — so the whole of this essay is a statement about five polyhedra and their proportions.

Sideways, into what a lattice is for. Both radii are quantities a lattice has as a set of points, with no symmetry entering; the essay next door asks whether a set of points is a lattice at all, and the answer — discrete or dense, and nothing between — is decided by whether the shortest vector stops shrinking when the search widens, which is the first of these two radii asked as a question rather than measured as a number.