A reduction with one rule

The cell that settles the argument builds Niggli’s reduction: eight numbered conditions, several with sub-cases, applied in order until none applies. It is what the International Tables print, it produces a canonical cell, and it is a page of case analysis that is easy to implement almost correctly.

There is another reduction, from Selling in 1874, and it has one rule.

Four vectors that sum to zero #

Take a basis b₁, b₂, b₃ and add a fourth vector b₄ = −(b₁ + b₂ + b₃). The four sum to nothing, and that is the whole trick: they are on an equal footing, and the six pairwise products

p_ij = bᵢ · bⱼ

sit on the six edges of a tetrahedron whose vertices are the four vectors. There is no distinguished direction and no ordering to get wrong.

The reduction is:

While some p_ij is positive, replace bᵢ by −bᵢ and add the old bᵢ to the two vectors that are neither i nor j.

That is all of it. The four still sum to zero afterwards — the vector that changed sign is cancelled by the two that gained it — so the object the rule acts on is preserved, which is the property that makes a single rule sufficient where a basis would need cases to keep itself a basis. There are no cases to distinguish, no order of application to fix, and no condition that fires only when another has already been satisfied.

Why it stops #

A rule with no cases still has to terminate, and Selling’s does for a reason that is a single quantity: the sum of the four vectors’ squared lengths falls at every step.

That is checked here rather than quoted. Every reduction in the sweep — several thousand random integer lattices — is run with the total recomputed after each step and required to have fallen, and it always has. A sum of squares that strictly decreases through non-negative integers cannot go on for ever, which is the termination proof, and having watched it fall is a different kind of confidence from having read it.

Selling is also faster in practice on these lattices — a mean of four and a half steps against Niggli’s five and three-quarters — though that comparison is worth less than it looks, since a “step” means different amounts of work in the two. The comparison that matters is the one in the source: eight numbered conditions against one rule.

The parameters are the cell #

Here is the reason to care, and it is not about speed.

When the reduction stops, all six parameters are non-positive, and the seven relevant vectors of the lattice — the ones whose bisecting planes are the faces of the Voronoi cell — are exactly the four bᵢ and the three sums bᵢ + bⱼ over opposite pairs of edges. Seven pairs, fourteen faces: the generic count five parallelohedra and no others derives from the seven classes of the lattice modulo twice itself.

A parameter that vanishes removes a pair of faces. So the shape of the cell is not something to compute afterwards; it is read off which of the six numbers are zero.

That statement needs checking, and checking it means computing the cell independently. The faces here are found by taking each of the seven classes modulo 2Λ and asking whether its shortest vector is unique up to sign — a tie means the bisector is cut off and the face is not there. The vertices are found separately, by solving every triple of face planes and keeping the solutions that satisfy all the others. Those two computations share no step, and Euler’s formula is what says they agree.

Six patterns, five solids #

Sweeping random lattices and recording which parameters vanish gives six patterns — labelled so that renumbering the four superbasis vectors cannot change the label, which takes a minimum over the twenty-four ways of numbering them.

Each pattern gives one cell and only one. And the distinct cells are five:

• no zeros — fourteen faces, twenty-four vertices: the truncated octahedron;
• one zero — twelve faces, eighteen vertices: the elongated dodecahedron;
• two zeros on disjoint edges — twelve faces, fourteen vertices: the rhombic dodecahedron;
• two zeros sharing a vertex — eight faces: the hexagonal prism;
• three zeros, two ways — six faces: the parallelepiped.

That is Fedorov’s five, arrived at from a reduction rule. The classification of the parallelohedra is normally a theorem about solids that tile by translation; here it falls out of asking which of six numbers can be zero at once, and the two twelve-faced solids — which a face count alone cannot tell apart — are separated by their vertex counts without anybody looking at their shapes.

The parallelepiped arriving from two patterns is worth a moment. It is not a defect of the labelling: three zeros can sit as a path through the tetrahedron or as a triangle on three of its vertices, those are genuinely different arrangements, and both leave the cell a parallelepiped. A classification of patterns is finer than a classification of cells, which is exactly the gap Delaunay’s twenty-four lattice characters live in, and which five parallelohedra and no others records as uncomputed.

The bound that had to be in the right basis #

One thing in this account was wrong first, and it is the most useful part of it.

Finding the relevant vectors means searching each class modulo 2Λ for its shortest member. A search needs a radius. The radius was first taken in the basis the lattice arrived with — and for a skew lattice, whose shortest vectors have large coordinates on that basis, a search out to eight cells still missed them. The cell came back with faces it does not have, two lattices with the same zero pattern came back with different cells, and it looked like a finding.

A bound in the wrong basis is not a bound. It reports a number, the number is wrong, and nothing about the computation says so — which is the characteristic failure mode of every search in this collection, arriving here in a place where the fix was already sitting in the same file. The reduction is not a tidying step before the interesting part; it is what makes the interesting part computable at all.

That is also the honest answer to why anybody reduces a cell. Not for canonical form, and not for tables: because the quantities one wants to compute are only reachable from a basis on which the lattice’s own short vectors are short.

What a superbasis is doing #

The four-vectors-summing-to-zero trick looks like a device and is not, and the reason is worth extracting because it recurs.

A basis of a lattice singles out three directions and treats a fourth — the one along −(b₁+b₂+b₃) — as derived. But nothing about the lattice singles out three directions: the relevant vectors that make the Voronoi cell come in seven classes, and the basis names three of them and leaves four unnamed. The superbasis names four and leaves three, and the three it leaves are the sums bᵢ + bⱼ, which the four then determine symmetrically.

That is why the six parameters are the natural coordinates. Six is the number of independent entries in a symmetric three-by-three matrix — the dimension of the space of lattice shapes — so the parameters are a complete description with nothing spare, and they are attached to the tetrahedron rather than to an ordered triple of vectors. Renumbering the four vectors permutes the six parameters through the twenty-four symmetries of the tetrahedron, and a quantity computed from them is a genuine property of the lattice exactly when it is invariant under those twenty-four.

The zero pattern is such a quantity, once it is canonicalised over the twenty-four — which is what the labelling above does, and which is not optional. Two descriptions of one lattice can produce the same zeros in different places, and comparing the raw strings would report them as different lattices.

This is the same lesson the cell is a choice draws for bases in general, one level up: the description has a symmetry group of its own, and a property of the object is a function on descriptions that the group leaves alone. Selling’s parameters are unusual in that the group is small enough to quotient by explicitly — twenty-four permutations, applied and minimised over — where the general problem of deciding whether two Gram matrices describe one lattice is a harder question with its own essay.

Reading the zeros #

It is worth saying in words what a vanishing parameter means geometrically, since the whole classification hangs on it.

p_ij = bᵢ · bⱼ = 0 says two of the four superbasis vectors are perpendicular. In the Voronoi cell, the face pair that disappears is the one perpendicular to bᵢ + bⱼ — because when bᵢ and bⱼ are perpendicular, |bᵢ + bⱼ|² = |bᵢ|² + |bⱼ|², and the vector bᵢ + bⱼ is then exactly as long as the diagonal of a rectangle whose sides are already faces. Its bisector is cut off by theirs, and the face is gone.

So a right angle among the superbasis vectors costs the cell two faces, and the parallelohedron a lattice gets is decided by how many right angles its reduced superbasis has and how they are arranged. The truncated octahedron is the shape of a lattice with none; the cube is the shape of one with three, and the two arrangements of three that occur are the two ways of having three right angles among four vectors that sum to zero.

That reading explains the earlier observation that the generic cell has the most faces rather than the fewest. Faces are lost to coincidences, coincidences are what symmetry produces, and a lattice with no symmetry has none — so it uses all seven classes and gets fourteen faces, and every more symmetric lattice gets fewer.

Selling against Niggli, honestly #

Two reductions, and it is worth saying what each is for rather than picking a winner.

Niggli’s produces a canonical cell, which is what a database needs: two descriptions of one lattice reduce to the same six numbers, so a cell can be looked up. That is what the conditions are numerous for — they pin down a unique representative, including in the degenerate cases where several are tied.

Selling’s produces the Voronoi data, which is what a geometric question needs. It does not give a canonical cell — several superbases can be reduced — and it gives the six parameters, from which the cell, the relevant vectors and the parallelohedron type all follow immediately.

The historical note in the cell that settles the argument turns out to be about exactly this trade: Andrews and Bernstein’s later work on the Selling reduction was motivated by a tolerance problem, because Niggli’s conditions are discontinuous at the boundary between lattice types while Selling’s parameters move continuously. A canonical form has to make a discrete choice somewhere, and the place it makes it is a place where nearly-equal lattices are put in different boxes.

Where the reduction is used, and where it is not #

Two reductions are in this collection now and they answer different questions, so it is worth naming which essays need which.

Anything that asks “is this the same lattice as that one” needs a canonical form, and that is Niggli’s. The cell that settles the argument is the essay; matching a measured cell against a database is the use; and the discontinuity at type boundaries is the price, since two lattices a hair apart can reduce to visibly different cells.

Anything that asks “what shape is this lattice’s cell” or “which vectors are short” needs a basis on which the answer is visible, and Selling’s is the cheapest one. Five parallelohedra and no others computes the cells directly, from perpendicular bisectors, with a search whose width it has to defend; the route here reaches the same cells with the width question answered by the reduction rather than by widening.

And anything that asks “how far apart are these two lattices” needs neither, because a distance between shapes is not a property of any single reduced form — which is its own question and the reason the continuity of Selling’s parameters matters there.

The one place the two reductions genuinely compete is a practical one: identifying a lattice from a measured cell with errors in it. A canonical form is what the identification wants and is exactly what behaves badly near a boundary; parameters that move continuously are what the errors want and do not identify anything on their own. The usable answer is to reduce both ways and compare, which is what modern cell-matching does, and it is a good example of two constructions being right about different halves of one problem.

What this does not settle #

It is not Delaunay’s classification. The six patterns are coarser than the twenty-four lattice characters Delaunay’s classification records, and finer than the five parallelohedra. Getting the twenty-four needs an equivalence this essay does not settle — classifying by which parameters are equal as well as which vanish gives about fifty classes among integer lattices, which is finer than twenty-four, so the classical count uses something in between and the definition has to be pinned down before the number can be computed. That is recorded as open rather than guessed at.

And the sweep is over integer lattices in a stated range. The five cells and the six patterns are what that range produces; a proof that there are no others is Fedorov’s, and this collection does not carry it. What the computation supplies is the mechanism — which parameters can vanish together — and a demonstration that the mechanism produces the classical answer.

What the six numbers say about symmetry #

There is a last reading of the parameters that connects them to the rest of this collection, and it costs nothing once the reduction is in hand.

The Bravais type of a lattice is a statement about its point group, and the point group is a statement about coincidences among lengths and angles. Those coincidences are visible in the six parameters directly: a cubic lattice’s reduced superbasis has parameters that are equal in threes, a tetragonal one in pairs, a triclinic one not at all. Which parameters are equal is the symmetry; which are zero is the cell shape, and the two questions are asked of the same six numbers.

That is why the classification by zeros gives five classes and the classification by zeros and equalities gives many more. The first is a question about the Voronoi cell, which is a coarse object — it has only five shapes to be. The second is a question about the point group, which has fourteen answers in the Bravais classification and more if the equalities are read literally.

A reader who has both essays now has the two classifications side by side and can see they are genuinely different sortings of the same lattices: the primitive cubic, tetragonal and orthorhombic lattices are three Bravais types and one parallelohedron, and the face-centred cubic and a generic triclinic lattice are two Bravais types at opposite ends of the symmetry scale and the same twelve-faced solid. Neither classification refines the other, which is the observation five parallelohedra and no others makes and which the six parameters make almost visible.

The one thing to carry #

A reduction is a change of basis that makes short vectors have small coordinates, and everything else it is used for is downstream of that. Selling’s is the shortest statement of one: four vectors summing to zero, six products, and a rule that runs while any product is positive.

What comes out is not merely a tidy cell. It is the Voronoi cell’s face structure, in six numbers, with the classification of the parallelohedra readable in which of them are zero — a classification that took Fedorov a book, sitting in the output of a loop with one condition in it.