Crystallography & Symmetry
patterns derived from their groups
Concept

Basis reduction — where it appears

The procedure that replaces a lattice basis by the shortest one, terminating in a few steps and giving a canonical answer. In the plane it is Gauss's algorithm, its two moves generate every change of basis, and its length is that of a continued fraction.

Named by 9 essays across 2 fields — each of them below, with the objects they name alongside it.

Reducing a basis. An 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.

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.

lattices · Lattice Centring the five lattices. Each of the five plane lattices with the midpoint of every cell added, and the type of lattice that results — read off the reduced basis of the new point set rather than looked up. Every centring halves the cell area, so the original lattice is a sublattice of index two in the centred one, and every centred lattice is again one of the five. Two of the five come back as themselves and are therefore no richer for being centred. The rectangular and rhombic lattices exchange, which is what makes them one family under two descriptions. And the hexagonal lattice centred is rectangular — its holohedry falls from 12 to 4, so centring destroys the symmetry it was meant to display.

Centring, counted as a sublattice

Adding the centre of every cell to a lattice produces another lattice, containing the first with index two. Doing it to each of the five in turn shows why the list is five rather than ten, and why only one of the five has a centred description worth keeping.

lattices · Centring In the plane, the lengths do name the lattice. Every reduced binary form with coefficients up to 20 — 1750 lattices — with its theta series computed to 120 terms. No two of them agree. That is Schiemann's theorem for binary forms, which says the theta series determines the lattice in two dimensions and in three, confirmed here as far as the search reaches rather than proved. The closest pair is worth the space: two lattices whose shortest vectors both have squared length twenty agree for 38 terms — because neither has any vector before then — and part at the next one.

The lengths do not name the lattice

Seventeen hundred plane lattices, every one with a theta series shared with no other — the lengths determine the lattice, and an exhaustive search says so. In sixteen dimensions two different lattices have identical counts at every distance, and the example is sixty years old.

lattices · Lengths The region every plane lattice lands in. The shape of a plane lattice is one complex number, τ, and every lattice can be brought by a change of basis into the region shaded here: the strip between 0 and a half, outside the unit circle. Its interior is the oblique lattices. Its left edge is the rectangular ones, its arc and its right edge the centred rectangular ones, and its two corners are the square lattice at i and the hexagonal lattice at ρ. Five kinds, and they are a region, three arcs and two points rather than five things of one sort. The region is unbounded upwards, where the cell gets longer and thinner without limit.

The space every lattice lives in

Five lattices in the plane is the number of *kinds*. The number of lattices is a continuum — and it has a shape: one two-dimensional region with two corners, three edges and an interior, where the five kinds turn out to be a region, three arcs and two points rather than five things of one sort.

lattices · Moduli The region, and its copies. Words in S and T up to length 4, each carrying the region somewhere else. The copies do not overlap and they do not leave gaps: the upper half-plane is tiled by them, one copy per change of basis. That is the whole content of the claim that reduction picks a canonical basis — every basis of every lattice is in exactly one copy, and reduction is the walk back to the shaded one.

Two moves reach every basis

A lattice has infinitely many bases and reduction picks one. Why it can is a fact about a group with two generators and two relations — and the fundamental region tiles the plane with its own copies, one per basis, which is what makes the walk home finite.

lattices · Moduli (17, 5) and (23, 7) reduced in 3 steps. Lagrange's reduction, run on the basis (17, 5), (23, 7). Each step subtracts a whole multiple of the shorter vector from the longer and swaps them; after 3 steps neither can be shortened by the other and the pair is reduced. The faint arrows are the intermediate bases and the solid pair is the answer, of length 1.41. The procedure always terminates and always finds the shortest vector, and in the plane that is a theorem rather than a hope.

The shortest vector, and where it stops being easy

Two moves find the shortest vector of a plane lattice, and they always terminate. Nothing on this site has ever needed more, because every lattice here has two or three dimensions. In general the same question is NP-hard, the best polynomial procedure returns an answer that may be exponentially too long, and an entire branch of cryptography is built on the gap.

lattices · Lattice The whole space of plane lattices, and its corner. Every plane lattice appears exactly once in this picture. Scaling changes no density, so the leading coefficient is fixed at one; reduction then confines the other two to 0 ≤ b ≤ 1 ≤ c, and every lattice has exactly one reduced form. The curves are the levels of constant density, which are parabolas — a density d needs 4c − b² to equal (π/2d)². They crowd toward the corner b = c = 1, which is the hexagonal lattice at π/√12 ≈ 0.9069; the square lattice sits on the left edge at π/4 ≈ 0.7854. The picture is a search over a region rather than over a list, which is what makes the answer a decision: there is nowhere else for a lattice to be.

The densest lattice in the plane

Which arrangement of equal discs covers the most floor is a question about infinitely many lattices, and reduction turns it into a question about a two-parameter region with a corner. The answer is at the corner, and the argument finishes.

applied · Packing 342 unlabelled spots, cell volume 52. A bag of 342 reflection positions with no indices on them, collected out to a bound of 3 on each index. Their pairwise differences generate the reciprocal lattice; a basis of that is taken by integer elimination and then reduced, and the reduced basis is printed. Its determinant is 52, which is the volume of the cell the reflections were computed from — so the cell has been recovered from positions alone, with no intensity used anywhere.

A cell from a bag of spots

A single-crystal experiment returns a list of directions with no labels on them. Recovering the cell is recovering the lattice those directions generate, and the whole of it is take differences, reduce, read the answer. What no quantity of data settles is whether the lattice found is the true one or a sublattice of it.

applied · Indexing One net, six descriptions, four different answers about its symmetry. The honeycomb written against six bases of ℤ², all of them the same net. The detector tests each lattice type's holohedry in standard position, so a symmetry written against another basis is a matrix that is not in the list and is never tried — and the answer comes back as p6m, or an unnamed group of order four, or p2, or cmm, depending on how the voltages were typed. The metric column is the form the net's own edges make, inverted; the reduced column is that form after Lagrange–Gauss reduction, and it is the same in every row, which is what makes the last column a property of the net.

The symmetry a net was written with

A net has no coordinates, so its symmetry is whatever its best drawing has. This collection measured that by handing the drawing to a detector — and the detector tests a fixed list of matrices, so the answer depended on which pair of translations the voltages had been written against. The honeycomb came back as p6m, or p2, or cmm, or nothing, one net and four answers.

applied · Nets

Named alongside it

The objects these essays reach for when they reach for this one.

Quadratic formUnimodular matrixChange of basisHolohedryLatticeCentringDecidabilityFundamental domainLattice typeMeasurementModular groupModuli space

All concepts