The cell that settles the argument

The cell is a choice is this site’s standing warning: a lattice has infinitely many bases, crystallography picks one by rule, and a symbol read against the wrong rule means something else. The shortest basis settles it in the plane, where Gauss’s reduction is four lines and terminates in a handful of steps.

In three dimensions the same job is harder and the question it answers is one two crystallographers can genuinely disagree about: are these two cells the same lattice?

Two structure determinations of one compound can report cells with no number in common. The lattice underneath may be identical, described in bases related by an integer matrix of determinant one — of which there are infinitely many, and some of them look nothing alike. Comparing the six numbers directly answers nothing. Reducing both and comparing the reduced forms answers it completely.

What is reduced is the metric, not the cell #

The quantities the algorithm works on are not lengths and angles but the six entries of the Gram matrix: A = a·a, B = b·b, C = c·c, and ξ = 2b·c, η = 2a·c, ζ = 2a·b. For every lattice this site draws they are integers, so the whole reduction is integer arithmetic and the reduced form is exact.

Working on the metric rather than on the cell has a consequence worth stating plainly: a lattice and the same lattice rotated have one Gram matrix. Orientation is not part of the question and cannot enter the answer. Two crystals whose cells differ by a rotation, a reflection or a relabelling of axes have the same reduced form, and two whose lattices genuinely differ do not.

Each of the algorithm’s steps is a change of basis of determinant ±1 — swap two axes, negate two of them, or subtract one from another — so the lattice is untouched throughout and only its description moves. The loop terminates because A + B + C never rises and falls whenever anything changes.

The eight steps, and what each is for #

Krivý and Gruber’s version has eight numbered conditions, and they group into three jobs.

Sorting. The first two put the axes in order of length, so a lattice cannot have two reduced forms differing by which axis was called a.

Choosing a sign convention. The third and fourth make all three angles acute or all three obtuse — the Type I and Type II split — by negating two axes at a time, which is a proper operation and so never turns a right-handed cell into a left-handed one. Without this step the same lattice would reduce to eight forms differing only in signs.

Shortening. Steps five, six and seven subtract one axis from another whenever an angle is too far from a right angle, which is the three-dimensional form of the plane’s Gauss step. Step eight handles the one remaining case, where the body diagonal is shorter than an axis and no pairwise subtraction helps.

The iteration cap in the implementation is a refusal rather than a safeguard. Every step strictly reduces A + B + C or makes an earlier step applicable, so the loop terminates — and a sign error makes it cycle silently, which a cap that throws is the only cheap way to notice. It never fires on a lattice; it fired repeatedly while the steps were being got right.

The round trip #

The claim the whole file exists for is a round trip in this site’s usual sense: describe an object, forget the description, and require the original back.

Take a lattice. Scramble its basis by a random integer matrix of determinant one — built as a product of shears, because a random integer matrix is almost never unimodular and rejection sampling would only ever produce mild bases. Reduce. Compare.

Two hundred scrambles per lattice, on nine lattices, with matrix entries reaching the sixties: every one returns the six integers the lattice started with, and the comparison is an equality of integers with no tolerance in it. A single sign wrong in any of the eight steps breaks it immediately, because the form then depends on which scramble it started from.

The second half of the check is that distinct lattices have distinct forms. The interesting pair is the two cubic centrings: body-centred cubic reduces to (3, 3, 3, −2, −2, −2) and face-centred to (2, 2, 2, 2, 2, 2), while both have the same symmetry. A fingerprint that could not tell those apart would be no use, since they are the two lattices most often confused in practice.

The system, read off the metric #

The reduced form is a fingerprint and it is not, by itself, a classification. What names the system is a second computation: every integer matrix preserving the metric, found by searching a small box for MᵀGM = G with |det M| = 1.

The order of that group settles it — 2 triclinic, 4 monoclinic, 8 orthorhombic, 12 rhombohedral, 16 tetragonal, 24 hexagonal, 48 cubic — and nothing is looked up. The three cubic lattices come out at 48 from metrics with no entries in common, and the hexagonal one at 24, which is the number fourteen lattices and no others derives from the other direction.

Two derivations of the same fact meeting is the usual arrangement here. That essay enumerates the candidate centrings system by system and asks which survive; this searches the matrices that preserve a metric and counts them. The lists agree.

Where the exactness stops, and it is the whole practical difficulty #

Everything above is exact because the Gram entries are integers. Real cells come from a refinement, and their Gram entries are measurements with error bars. Reduction then has to be done with a tolerance, and the tolerance decides the answer.

The figure’s lattice is monoclinic: one off-diagonal entry is not zero, and it is small. In exact arithmetic the symmetry search finds four operations and the lattice is monoclinic. Allow a tolerance larger than the deviation and the search finds eight, and the lattice is orthorhombic.

Neither answer is wrong. They answer different questions — is this metric invariant and is this metric invariant to within ε — and a refinement produces numbers that force the second question whether anybody wants it or not. This is the single place in the whole classification where a number chosen by a person decides what a lattice is.

It is also why the International Tables print a table of lattice characters with tolerances attached rather than a decision procedure, and why two databases can disagree about a compound’s Bravais type while agreeing about every atom in it. The disagreement is not about the crystal. It is about ε.

Two types, and the discontinuity between them #

The Type I / Type II split deserves more than the line it got above, because it is where the exact procedure and the approximate one come apart.

A reduced form is Type I when all three of ξ, η, ζ are positive — all three angles acute — and Type II when none of them is. Those are the only possibilities after step four, and the two are genuinely different shapes of cell: Type I has its three axes clustered around a body diagonal, Type II has them spread.

The awkward case is a lattice with a right angle, where one of the three is exactly zero. It qualifies as Type II by the convention that zero counts as non-positive, and it sits on the boundary: an arbitrarily small perturbation sends it into Type I. That is not a defect of the algorithm — the two forms describe the same lattice and reduce to the same numbers when the arithmetic is exact — but it is why a measured metric near a right angle can reduce to either type, and why the numbers on either side of the boundary are stable while the label is not.

Every lattice with any symmetry at all sits on such a boundary, since symmetry is what makes an entry exactly zero. The forms crystallographers care about most are precisely the ones a tolerance is least able to place, which is the practical shape of the whole difficulty.

One consequence catches people out. The reduced cell is primitive by construction: the algorithm minimises the axes, and a centred cell has a larger volume than the lattice needs. So the reduced form of a face-centred cubic lattice is a rhombohedral-looking primitive cell with all angles 60°, and nothing in it says “cubic F” until the symmetry search is run and returns forty-eight. The reduced form identifies the lattice; the conventional cell is a second, separate choice made afterwards, and it is the one why the bigger cell wins is about.

The failure this prevents, and the one it does not #

What reduction prevents is a duplicate entry in a structural database: the same compound indexed twice under cells that look different. Every crystallographic database reduces before it compares, and the standard duplicate-detection test is the reduced form plus a tolerance.

What it does not prevent is a derivative relationship going unnoticed. A structure whose cell is twice another’s along one axis reduces to a different form, correctly, because it is a different lattice — and no comparison of reduced cells will say that one is a superlattice of the other. That is a different question, answered by the sublattice arithmetic of how many sublattices rather than by reduction, and confusing the two is how a family of related structures gets catalogued as unrelated.

What a database actually does with it #

The procedure has a use that is worth following through, because it is the reason reduction is run millions of times a year.

A structural database holds a few hundred thousand determinations. A new one arrives with a cell, and the question is whether that compound is already there. Comparing cell parameters directly fails: the same lattice can be reported in bases that share no number, and two genuinely different compounds can have cells agreeing to three decimals by coincidence. So the search is done on the reduced form, with a tolerance, and the candidates it returns are then compared atom by atom.

That is a two-stage filter with a stated failure mode in each stage. The reduced form with a tolerance can merge two lattices that are near-degenerate — the pseudo-symmetry case above — which produces extra candidates that the second stage throws out. It can also separate two determinations of one compound measured at different temperatures, if thermal expansion has moved a parameter past the tolerance. The first failure costs time; the second costs a duplicate entry, and duplicates in structural databases are a known and quantified problem for exactly this reason.

What the two computations are each blind to #

It is worth putting the division of labour in one place, because the essay has now met both halves of it and they are easy to run together.

The reduced form cannot name a system. It is six integers derived from lengths and angles, and the face-centred cubic lattice’s are the six of a rhombohedron at sixty degrees. A reader handed (2, 2, 2, 2, 2, 2) and told it is a reduced form has been told which lattice it is and nothing about what symmetry that lattice has.

The symmetry count cannot name a lattice. It is an order — forty-eight, say — and three different lattices return it. A reader handed forty-eight knows the system and cannot tell a primitive cubic lattice from either of its centrings.

And neither of them produces a conventional cell. That is a third computation and it is a choice rather than a derivation: take the smallest cell whose edges lie along the symmetry directions, which for two of the three cubic lattices is not the reduced cell at all. Reduction minimises the description; convention maximises what the description displays; and the two pull in opposite directions on exactly the lattices with the most symmetry to display.

The practical form of that is a piece of advice about reading software output. A program reporting a reduced cell where a reader expects a conventional one produces six numbers that look wrong and are not, and the disagreement between two programs is far more often about which of these three questions each was answering than about any arithmetic.

Who found it, and when #

Niggli published the reduced cell in 1928, building on Selling’s and Delaunay’s earlier reduction of quadratic forms — the subject is older than crystallography, and the mathematics is Gauss’s theory of the reduction of positive definite forms, from the Disquisitiones of 1801.

The crystallographic form of it took another forty years to become usable. Křivý and Gruber gave the algorithm above in 1976, with the numbered conditions the International Tables still print; Gruber refined the treatment of near-degenerate cases in 1973 and again in the 1980s; and Andrews and Bernstein’s later work on the Selling reduction was motivated by precisely the tolerance problem, since Niggli’s conditions are discontinuous at the boundary between types and Selling’s are less so.

That history is the tolerance problem being met repeatedly rather than solved. Every version of the algorithm reduces exactly; every application of it has to decide how nearly equal two measured numbers are.

Why the plane case looked easier than it was #

Comparing the two dimensions is the quickest way to see what the third axis costs, and the cost is not where a reader expects it.

Gauss reduction in the plane is four lines and always terminates, because there is only one way for a basis to be bad: one vector too long relative to the other, fixed by subtracting the right integer multiple. The loop is a Euclidean algorithm in disguise and it converges as fast as one.

In three dimensions there are more ways to be bad and they interact. Shortening a against b can lengthen the angle between a and c; fixing that can undo the first step. The eight conditions exist to sequence those repairs so that a quantity strictly decreases, and the proof that it does is the real content of Krivý and Gruber’s paper. The arithmetic in each step is as simple as the plane’s; the argument that the steps terminate is not.

That is a general feature of reduction problems, and it is why the corresponding question in higher dimensions is hard enough to found a research field: in dimension n the reduction of quadratic forms is the shortest-vector problem, no polynomial algorithm is known, and the best practical answer — LLL — trades exactness for speed. This site’s plane and space cases are the two where exactness is affordable.

Why it terminates, and what the cap is for #

An algorithm that keeps subtracting one basis vector from another needs an argument that it stops, and the argument is short enough to give.

Every step of the reduction is a change of basis of determinant ±1, so the lattice’s volume is fixed throughout — and the sum of the three squared lengths, which is the trace of the Gram matrix, strictly decreases at every shortening step. A subtraction is performed only when it shortens something, the trace is a non-negative quantity, and the entries are integers when the lattice is given in integers. A strictly decreasing sequence of non-negative integers is finite, so the procedure terminates, and no bound on the number of steps is needed to know that it does.

That is why the iteration cap in the implementation is a refusal rather than a safeguard. If the loop ever reaches its cap, the argument above has failed somewhere — a step that was supposed to shorten did not, or a sign convention flipped back and forth between two states of equal trace — and the honest response is to stop and say so, rather than to return whichever basis the loop happened to hold. A cap that quietly returns an answer converts a broken invariant into a plausible cell, and a plausible cell is what this whole rung exists to prevent.

What happens in higher dimensions #

The remark that the third axis costs more than the second understates it, and the shape of the general problem is worth naming, because it is one of the few places where crystallography’s arithmetic turns out to be the easy case of something much harder.

Reduction is a well-posed problem in every dimension and an expensive one. Minkowski reduction — demanding that each basis vector be as short as possible given the ones before it — is defined in all dimensions and is not known to be computable in polynomial time; finding the shortest vector of a lattice at all is NP-hard under randomised reductions. The three-dimensional case is tractable because three is small, not because the problem is easy.

What is available in general is approximate reduction. The LLL algorithm of 1982 returns, in polynomial time, a basis whose first vector is within an exponential factor of the shortest — weak enough to be useless as a fingerprint and strong enough to have become one of the standard tools of computational number theory. The gap between that and what the reduced cell provides here is the whole difficulty: crystallography needs an exact canonical form, because two determinations are being compared for equality, and an approximation that is nearly canonical is not canonical at all.

The hardness has a second life worth mentioning. Lattice problems’ resistance to efficient solution is what several post-quantum cryptosystems are built on, so the difficulty of doing in high dimensions what this page does in three is now load-bearing somewhere else entirely. The fourteen lattices are a small, completely solved corner of a subject that stops being solvable a few dimensions further along.

Where the ladder goes next #

This rung establishes the reduced cell and the round trip. Two rungs are visible above it.

Delaunay reduction and the parallelohedra. Classifying a lattice by the combinatorial type of its Voronoi cell rather than by a basis gives Fedorov’s five parallelohedra in three dimensions, and it is the alternative to the Niggli route — the one that never chooses a basis at all. The cell nobody chose builds the object; the classification by it is the rung above.

The lattice characters. Niggli’s forms fall into forty-four characters, which are the equivalence classes under the symmetry a reduced form can have, and they are what the Tables tabulate. Deriving them rather than transcribing them is a phase’s worth of work, and it is where the tolerance question stops being a footnote and becomes the subject.