Crystallography & Symmetry
patterns derived from their groups
Lattices

Reduction, and the shortest basis

Every lattice has infinitely many bases and no arithmetic picks a preferred one — until a rule is imposed. Reduction is that rule, it terminates in a handful of steps, and it is what lets a database decide whether two reported crystals are the same crystal.
16 min read 6 figures Symmetry is decidableExactly this manyThe lattice forbids

Two laboratories measure the same compound and report cells that share not one digit. Neither is wrong. A lattice has infinitely many bases, every one of them describes the identical set of points, and the numbers that come out of a diffractometer depend on which the indexing software happened to land on.

Reducing a basisAn awkward basis and the reduced one Gauss's algorithm returns. Both describe the same lattice — the change of basis has determinant one — and the reduced pair is the shortest vector together with the shortest independent of it, checked against an exhaustive search.as given — 3 reduction steps to go|a| = 5.831 |b| = 3.606reduced — shortest, then shortest independent|a| = 1.000 |b| = 1.000same lattice, same cell area, different descriptiondeterminant 1
Fig. 1 An awkward basis and the one reduction returns. Both describe the same lattice — the change of basis has determinant one — and the reduced pair is the shortest vector together with the shortest independent of it, checked against an exhaustive search.

Settling the question needs a rule that picks one basis out of the infinitely many, applies to every lattice, and terminates. In the plane the rule is three lines long and is due to Gauss.

The freedom being removed

Two bases generate the same lattice exactly when one comes from the other by an integer matrix of determinant ±1\pm 1 — a unimodular transformation. There are infinitely many such matrices, so the freedom is infinite, and nothing about the point set prefers one of them.

The determinant condition is not decoration and it is the first thing the figures here check. Determinant ±1\pm 1 means the transformation has an integer inverse, so it can be undone without leaving the lattice. A matrix with determinant 22 generates a sublattice — half the points — which is a perfectly good lattice and a different one. A reduction routine that lost track of this would return the shortest basis of something smaller than what it was given, and the returned numbers would look entirely plausible.

So every panel on this page carries the determinant of its transformation, and the assertion behind the figure refuses a starting basis whose determinant is anything but ±1\pm 1. The check costs one multiplication and it is the difference between comparing two descriptions of one lattice and comparing two lattices.

Gauss’s algorithm

The procedure is short enough to state completely and it is worth stating, because its termination argument is the whole of why reduction works.

Given two vectors a\mathbf{a} and b\mathbf{b}:

  1. If a\mathbf{a} is longer than b\mathbf{b}, swap them.
  2. Compute μ=round⁡ ⁣(b⋅aa⋅a)\mu = \operatorname{round}\!\left(\dfrac{\mathbf{b}\cdot\mathbf{a}}{\mathbf{a}\cdot\mathbf{a}}\right), the nearest whole number of copies of a\mathbf{a} that fit into b\mathbf{b}.
  3. If μ=0\mu = 0, stop. Otherwise replace b\mathbf{b} by b−μa\mathbf{b} - \mu\mathbf{a} and go back to step 1.

Each pass through step 3 strictly shortens b\mathbf{b}, because subtracting the nearest multiple of a\mathbf{a} is exactly the projection that minimises the length. Lengths in a lattice cannot decrease forever — the lattice is discrete, so there is a shortest non-zero vector and nothing below it — so the loop terminates, and it does so quickly: the number of steps is bounded by the logarithm of the ratio of the starting lengths.

What comes out is the shortest vector of the lattice, together with the shortest vector independent of it. Both claims are asserted on this site rather than believed: the reduction’s answer is compared against an exhaustive search over every small integer combination, and the figure fails if the search finds anything shorter.

Reducing a basisAn awkward basis and the reduced one Gauss's algorithm returns. Both describe the same lattice — the change of basis has determinant one — and the reduced pair is the shortest vector together with the shortest independent of it, checked against an exhaustive search.as given — 2 reduction steps to go|a| = 4.359 |b| = 2.646reduced — shortest, then shortest independent|a| = 1.000 |b| = 1.000same lattice, same cell area, different descriptiondeterminant 1
Fig. 2 The same algorithm on a hexagonal lattice, from a worse starting basis. The reduced pair is at 120°120° and equal in length, which is the conventional description — so reduction recovers the standard cell rather than merely a small one.

The algorithm run in full

The default figure on this page starts from the basis a=(3,5)\mathbf{a} = (3, 5) and b=(2,3)\mathbf{b} = (2, 3) on a square lattice, which is a unimodular disguise of the obvious basis — its determinant is 3×3−5×2=−13 \times 3 - 5 \times 2 = -1. Running the loop by hand takes four lines.

The starting lengths are 34≈5.831\sqrt{34} \approx 5.831 and 13≈3.606\sqrt{13} \approx 3.606, so the first move is a swap. Then μ=round⁡(21/13)=2\mu = \operatorname{round}(21/13) = 2, and b\mathbf{b} becomes (3,5)−2(2,3)=(−1,−1)(3,5) - 2(2,3) = (-1,-1), of length 2\sqrt{2} — already shorter than either vector it started with.

A second swap, then μ=−2\mu = -2, and b\mathbf{b} becomes (0,1)(0, 1): length exactly one, which is as short as this lattice gets. A third swap, μ=−1\mu = -1, and b\mathbf{b} becomes (−1,0)(-1, 0). Now both vectors have length one, the projection of either onto the other is zero, μ\mu comes out zero, and the loop stops.

Three subtractions, from a basis whose longer vector was nearly six times the shortest in the lattice. The determinant is 11 at the end and was −1-1 at the start, which is the sign flip the swaps introduced and is not a change of lattice.

Two details in that trace are worth flagging because they are where implementations go wrong. The rounding in step 2 must be to nearest, not towards zero: rounding 2.52.5 down instead of up still terminates and still returns a basis, just not the shortest one. And the swap has to be re-tested every pass rather than performed once at the start, since a subtraction can easily make the second vector the shorter of the two — which it does twice in this example.

Why the answer is worth having

The reduced basis is nearly canonical, and the qualification in “nearly” is where the practical work is.

Reduction determines the two lengths and the angle between them, and it does not determine the signs or the labelling. The pairs (a,b)(\mathbf{a}, \mathbf{b}) and (−a,−b)(-\mathbf{a}, -\mathbf{b}) and (b,a)(\mathbf{b}, \mathbf{a}) all satisfy the conditions, so a further convention is needed before two reduced cells can be compared digit by digit. That convention is what a reduced cell in the crystallographic sense adds: a list of tie-breaking rules about signs and ordering, arranged so that exactly one basis survives all of them.

Paul Niggli set out the three-dimensional version in 1928, and it is the reason a structural database can answer the question two laboratories cannot. Reduce both reported cells to the Niggli cell and compare; if the numbers agree the structures are candidates for being the same, and if they disagree the lattices are different and no further comparison is needed. The Cambridge Structural Database and the Inorganic Crystal Structure Database both index on the reduced cell for precisely this reason, and duplicate entries are found by exactly this comparison.

The comparison is not free of judgement even so. Measured cell parameters carry uncertainties, so “agree” means “agree within a tolerance”, and a badly chosen tolerance either merges two genuinely different compounds or splits one compound across two entries. That is the one place in this essay where a threshold appears, and it appears at the boundary between the exact procedure and the measured input, which is where thresholds always appear on this site.

What reduction does not do

Three things the algorithm is regularly assumed to deliver and does not.

It does not give the conventional cell. For a centred lattice the reduced basis is the primitive rhombic one, and the cell crystallography publishes is the centred rectangular one, which is larger. Reduction and convention pull in opposite directions: one wants the smallest description, the other wants the one whose axes lie along the symmetry. Software that reports a reduced cell where a reader expects a conventional one produces numbers that look wrong and are not.

It does not identify the lattice type. The reduced basis of a square lattice has two equal vectors at 90°90°, and so does the reduced basis of a rectangular lattice whose two axes happen to have been measured as equal. Distinguishing them requires deciding whether the equality is forced by symmetry or is a numerical coincidence, and that is a question for the diffraction pattern’s own symmetry rather than for the cell parameters.

It does not generalise as easily as it looks. In two dimensions the reduced basis contains the shortest vector and the shortest independent one, and in three dimensions the analogous statement is still true. From dimension five upwards it fails: a reduced basis in the sense of the standard algorithms need not contain a shortest vector at all, and finding one is a computational problem believed to be hard. The plane is a gentle case and gives a misleading impression of the general one.

The square latticeEvery periodic pattern in the plane repeats on one of five lattices. The classification is by which point symmetries the lattice itself admits, and the five are exhaustive — a sixth would need a rotation order no lattice can carry.squareequal lengths, angle 90°the arrows are the basis; the shaded region is one unit cell
Fig. 3 A square lattice over three cells. Reduction returns two equal vectors at a right angle here — and would return the same shape for a rectangular lattice whose axes had been measured as equal, which is why the reduced cell settles the description and not the symmetry.

Three dimensions, where the bookkeeping arrives

The plane needs one loop. Space needs a case analysis, and the reason is worth seeing because it is the first place the problem stops being obvious.

In two dimensions the reduced basis is characterised by a single inequality: the projection of each vector onto the other is at most half its length. In three there are three pairwise projections to control at once, and controlling one can spoil another, so the algorithm cycles through the pairs until nothing changes. It terminates for the same reason — lengths cannot fall forever in a discrete set — but the number of passes is no longer bounded by a simple ratio, and a naive implementation can loop between two states forever on a lattice with near-ties.

The crystallographic answer, Niggli’s, sidesteps the algorithmic question by writing down conditions on the six cell parameters directly: the three lengths ordered, the three angles all acute or all obtuse, and a list of tie-breaking rules for the boundary cases where two lengths are equal or an angle is exactly 90°90°. Those boundary cases are not rare — they are precisely the high-symmetry lattices, which is to say the ones anybody cares about — and about half the printed conditions exist to handle them.

The five plane latticesEvery periodic pattern in the plane repeats on one of five lattices. The classification is by which point symmetries the lattice itself admits, and the five are exhaustive — a sixth would need a rotation order no lattice can carry.obliqueno constraint on lengths or anglerectangularangle 90°, lengths freecentred rectangularequal lengths, angle freesquareequal lengths, angle 90°hexagonalequal lengths, angle 120°the arrows are the basis; the shaded region is one unit cell
Fig. 4 The five plane lattices. Reduction returns a shortest basis for each, and for four of them that basis is the conventional one; for the centred rectangular lattice it is the primitive rhombus, which is not the cell anybody publishes.

The lesson generalises past this subject. An algorithm’s hard part is usually its ties, and the ties in lattice reduction are exactly the configurations that symmetry produces. A procedure that works beautifully on random input and fails on symmetric input is a procedure that will fail on every case of interest.

The generalisation that matters elsewhere

The hardness in high dimensions is not a curiosity, because an approximate answer turned out to be worth a great deal.

In 1982 Lenstra, Lenstra and Lovász published an algorithm — universally called LLL — that reduces a basis in any dimension in polynomial time, returning vectors that are short but not guaranteed shortest. It is Gauss’s algorithm with the exact condition replaced by a relaxed one, and the relaxation is what makes it terminate quickly.

LLL is now everywhere. It factors polynomials with rational coefficients, finds integer relations among real numbers, breaks knapsack cryptosystems, and reconstructs minimal polynomials from numerical approximations. And the hardness of the exact problem — finding a genuinely shortest lattice vector in high dimension — is the assumption underneath lattice-based cryptography, which is the leading candidate for encryption that survives a quantum computer.

So the same three-line loop that tidies up a crystallographer’s cell parameters is, in a hundred dimensions, the reason certain codes are believed unbreakable. Two-dimensional reduction is easy, three-dimensional reduction is a solved bookkeeping problem, and the difficulty grows fast enough with dimension to carry a security argument.

What the round trip checked, and how

The figures on this page are computations rather than illustrations, and three assertions guard each one.

The starting basis generates the lattice. Determinant ±1\pm 1, checked before anything else, for the reason given above.

Reduction preserves the lattice. The determinant after reduction must equal the determinant before, since every step subtracts an integer multiple of one basis vector from the other and that is a unimodular operation. If a step ever changed it, the two panels would be pictures of different point sets.

The result is shortest. Every integer combination ia+jbi\mathbf{a} + j\mathbf{b} within a window is generated and measured, and the shortest found is compared against what reduction returned. The window is finite, so this is a check rather than a proof — but the shortest vector of a lattice cannot have large coefficients in a reduced basis, and the window is chosen well past where anything could hide.

The third check is the one that would catch a genuine error, and it is worth noting what kind. An implementation that rounds μ\mu towards zero rather than to nearest terminates, returns a basis, and produces a picture that looks exactly like a correct reduction. The vectors are merely not the shortest ones, by a factor that is usually small. Nothing about the drawing distinguishes the two, which is the same argument this site makes about patterns and their groups, arriving from a different direction.

Reducing a basisAn awkward basis and the reduced one Gauss's algorithm returns. Both describe the same lattice — the change of basis has determinant one — and the reduced pair is the shortest vector together with the shortest independent of it, checked against an exhaustive search.as given — 2 reduction steps to go|a| = 4.317 |b| = 5.689reduced — shortest, then shortest independent|a| = 1.000 |b| = 1.400same lattice, same cell area, different descriptiondeterminant 1
Fig. 5 A third starting basis, on a rectangular lattice. The reduction takes a different number of steps and arrives at the same kind of answer — the shortest vector and the shortest independent of it — which is the whole claim the algorithm makes.
Building the reciprocal lattice from spacingsEach family of lattice rows has a spacing, and each contributes one reciprocal point: perpendicular to the rows, at the inverse of the spacing. The points built that way were compared against the algebraic definition and agree exactly.5 families of rows1,00,11,11,-12,1one point per family, at 1 ÷ spacingthe geometric construction and the algebra agree exactly
Fig. 6 The reciprocal lattice built from the row spacings of a square lattice. Reduction on one side has a counterpart on the other — a short vector in the crystal is a widely spaced family of rows, so a badly chosen cell shows up as an awkwardly indexed diffraction pattern.

What a shortest vector is good for

Reduction is bookkeeping until something depends on the answer, and three things do.

Indexing. A diffraction experiment produces a list of directions in which the crystal scattered, and turning that list into a cell means finding the lattice whose reciprocal contains all of them. Every indexing algorithm is a lattice-reduction algorithm with a tolerance attached, and the failure mode is finding a sublattice — a cell twice as large as the true one, which indexes everything correctly and predicts reflections that are never seen. The absences it predicts look exactly like centring absences, and telling the two apart is a standard headache.

Twinning and supercells. A structure whose true cell is a doubling of a smaller one shows weak extra reflections between the strong ones. Deciding whether they are real or an artefact is a decision about which lattice the data belong to, and the reduced cell of each candidate is what gets compared.

Deciding sameness. Two structures are the same structure only if their lattices agree, and lattices agree only if their reduced cells do. Everything else in a comparison — atom positions, space group, composition — is downstream of that, and can be skipped when the cells differ.

In all three the useful property of the reduced basis is not that it is small but that it is determined. A canonical answer can be compared; a merely convenient one cannot.

Who found it

The two-dimensional algorithm is Gauss’s, from the Disquisitiones Arithmeticae of 1801, where it appears not as geometry but as the reduction theory of binary quadratic forms — a lattice basis and a quadratic form being two descriptions of the same object.

Hermite extended it to higher dimensions in the 1840s, with a bound on how much longer a reduced basis can be than the shortest possible, which still carries his name. Minkowski’s Geometrie der Zahlen of 1896 turned the subject into geometry properly, and his theorem on convex bodies containing lattice points is the tool that bounds everything in the field.

Niggli’s crystallographic reduction arrived in 1928, and its adoption was slow: the International Tables did not print the reduced-cell conditions until the 1969 edition, by which time the growth of structural databases had made the question of “is this the same cell” urgent enough that a convention had to be agreed.

Where the ladder goes next

The freedom reduction removes is the choice of cell, and the one case where crystallography deliberately declines the reduced answer is centring.

The classification that reduction cannot perform is the five lattice types, which is decided by symmetry rather than by shape.

The dual construction, where a short vector becomes a long one, is the reciprocal lattice, and the constraint that keeps every one of these lattices to five types is the crystallographic restriction.

What the pictures here cannot show. Both panels of a reduction figure show finitely many points, and the claim that they are the same lattice is a claim about every point, including all the ones off the edge of the drawing. What guarantees it is the determinant of the transformation, which is a number rather than a picture — and a reader looking at the two panels and finding them convincing is agreeing with the algebra rather than checking it.

Where this goes next

centred rectangularequal lengths, angle freethe arrows are the basis; the shaded region is one unit cell The cell is a choice, the lattice is not Every lattice has infinitely many unit cells and infinitely many bases, and crystallography picks one by convention. Knowing which convention is in force is the difference between a symbol that means something and a symbol that means nothing. centred rectangular cellthe same points, primitive cell40 of 81 absent — h + k oddan absence is a fact about the description until it is shown to be one about the structureaxis ratio 1.55 Centring, and why cm is not pm A centred cell has a lattice point in the middle and twice the area it needs, and crystallography prefers it anyway. The preference has a price, and the price is paid in reflections that vanish for reasons that have nothing to do with the crystal. obliqueno constraint on lengths or anglerectangularangle 90°, lengths freecentred rectangularequal lengths, angle freesquareequal lengths, angle 90°hexagonalequal lengths, angle 120°the arrows are the basis; the shaded region is one unit cell Five lattices, and no others A repeating grid can be oblique, rectangular, centred, square or hexagonal. That is the complete list for the plane, and the argument that closes it is a page long.