The shortest vector, and where it stops being easy

A lattice has no canonical basis: any two vectors that generate it will do, and there are infinitely many such pairs. Choosing a good one means choosing a short one, and the shortest basis of a plane lattice is found by a procedure so short it barely deserves a name.

Subtract a whole multiple of the shorter vector from the longer. Swap. Repeat until neither shortens the other.

It always terminates, because each step strictly shortens the longer vector and the lengths are a discrete set bounded below. It always finds the shortest vector, which is a theorem rather than a hope. And it is fast: the number of steps grows with the logarithm of how bad the starting basis was, exactly as Euclid’s algorithm does — which is not a coincidence, since in one dimension the procedure is Euclid’s algorithm, and the continued fraction it computes is the same object.

Everything in this collection that needs a short vector uses it, and nothing here has ever found a case where it struggled. That is because every lattice here has two or three dimensions.

The same question, higher up #

Ask for the shortest non-zero vector of a lattice in n dimensions and the situation changes completely.

Deciding whether a lattice contains a vector shorter than a given length is NP-hard. That is Ajtai’s result of 1998 for the randomised case, with earlier partial results going back to van Emde Boas in 1981. No procedure is known that finds the shortest vector of a general lattice in time polynomial in the dimension, and nobody expects one.

What exists instead is LLL — Lenstra, Lenstra and Lovász, 1982 — which runs in polynomial time and returns a basis whose first vector is guaranteed to be within a factor of $2^{(n-1)/2}$ of the shortest. That guarantee is exponential in the dimension and is essentially useless as a bound; what makes LLL one of the most-used algorithms in computational mathematics is that its typical behaviour is far better than its guarantee.

How much better is a measurement, and it can be made here.

LLL against the truth #

The enumeration is the part that has to be right, and it is worth saying how it is bounded. Every lattice vector is an integer combination of the reduced basis; the coefficients of the shortest one are bounded, but the bound is awkward to state tightly. So the search is run over a range, then over a wider range, and the result is kept only when widening changes nothing. That is the fleet’s standing refinement test, applied to a search range rather than to a grid, and the range that sufficed is reported alongside the answer.

The misses are small and the guarantee is not, and the two facts sit together uncomfortably. In three dimensions a seven per cent error is nothing anybody would notice in a crystallographic context, and in three dimensions the true shortest vector is available anyway by enumeration. The exponential bound only starts to bite at dimensions where enumeration has become impossible — which is exactly where nobody can check.

That is the honest shape of the situation: what can be measured is where the guarantee is not needed, and where the guarantee is needed nothing can be measured.

What LLL actually does #

The algorithm is short enough to describe, and describing it makes clear why the guarantee is exponential.

Take a basis. Compute its Gram–Schmidt orthogonalisation — the vectors obtained by removing from each basis vector its components along the earlier ones. Those are not lattice vectors; they are the sides of the box whose volume is the lattice’s determinant.

Then impose two conditions:

Size reduction. Each basis vector is reduced modulo the earlier ones, so that its Gram–Schmidt coefficients are at most a half in absolute value. That is Lagrange’s subtract a whole multiple, applied in every earlier direction at once.

The Lovász condition. Consecutive Gram–Schmidt vectors must not shrink too fast: the squared length of the k-th must be at least δ − μ² times the previous one’s, with δ usually three quarters. Where it fails, the two basis vectors are swapped and the process backs up.

The exponent comes from the δ. Each step the condition permits allows the orthogonal lengths to fall by a constant factor, so over n dimensions they may fall by that factor to the n-th — and the first basis vector may be that much longer than the shortest. Choosing δ closer to one tightens the bound and slows the algorithm, and the trade is the whole tuning question.

In the plane, the condition with δ = ¾ reduces to Lagrange’s, which is why the two-dimensional column of the table is exact and is asserted to be. That assertion is a check on the implementation rather than on the mathematics — an LLL that missed in two dimensions would have a bug in it.

The cost of the check #

The enumeration that verifies LLL is the expensive half, and its cost is the reason the measurement stops at seven dimensions.

Searching coefficients over a range r in n dimensions costs (2r+1)^n candidates. At r = 3 that is three hundred and forty-three in three dimensions, twenty-four thousand in five, and eight hundred thousand in seven. Two more dimensions and it is on the wrong side of tolerable; five more and it is impossible on any machine.

LLL’s own cost, meanwhile, is a few dozen operations at every dimension in the table. The number of swaps and size reductions it performs grows roughly linearly. That contrast — the checker exploding while the thing being checked strolls — is the entire practical case for LLL.

And that gap is why every claim in the section above is a claim about small dimensions. The measurement of how often LLL is exact requires knowing what the exact answer is, which requires the enumeration, which is the thing that cannot be run. So the table’s honest reading is not “LLL is nearly always right” but “LLL is nearly always right in the range where anybody can check” — and the range where anybody can check stops five or six dimensions above crystallography and three hundred below cryptography.

What a crystallographer actually uses #

The three-dimensional case has its own procedure and it is worth setting beside LLL.

The Niggli reduced cell is a canonical basis for a three-dimensional lattice, arrived at by a stated sequence of conditions on the Gram matrix. It does more than LLL: it is canonical, so two descriptions of one lattice reduce to identical cells, which is what makes a lattice a searchable key in a crystallographic database. Two cells that reduce alike are the same lattice, and that is how a lattice is identified when its theta series will not do it.

LLL is not canonical. Two bases of one lattice reduce to two short bases that need not be the same. For the purpose LLL was built for — finding a short vector — that does not matter; for the purpose a database has, it matters entirely.

So the two procedures answer different questions, and the crystallographic literature’s insistence on reduction conventions rather than reduction algorithms is about canonicity rather than about shortness.

What a lattice became #

The reason anybody outside crystallography cares about this is worth stating plainly, because it is a change in what the word lattice means to a working mathematician.

Hard lattice problems became a foundation for cryptography. A system whose security rests on the difficulty of finding a short vector in a lattice of a few hundred dimensions has two properties that factoring-based systems lack: there is a worst-case-to-average-case reduction, so a randomly chosen instance is provably about as hard as the hardest one, and no quantum algorithm is known that breaks it.

The consequences are current. The standards selected in 2022 to replace RSA and elliptic-curve cryptography for post-quantum use are lattice-based; the dimensions involved are in the hundreds; and the security estimates are estimates of how long a lattice-reduction algorithm would take, with LLL as the starting point of every attack and its stronger relatives — BKZ and its variants — as the practical ones.

None of that is computed here and none of it is claimed. It is mentioned because a reader arriving at this collection from crystallography will not otherwise learn that the object they have been studying for two hundred years became, in the last thirty, a hard computational object with a security literature attached.

The reversal is worth one more sentence, because it is not the usual kind. Most objects that turn up in cryptography were built for it. A lattice was not: it is the same definition Bravais used, a discrete subgroup of translations, and nothing about it changed. What changed is which question is being asked of it. Crystallography asks what shape a lattice has and what sits on it, and reduces a basis to answer that; cryptography asks for a particular vector in it, and cannot find one. The two subjects share every definition and no computation.

Why two dimensions are special #

It is worth being precise about what makes the plane case work, since the answer is not “it is small”.

Lagrange’s procedure works because a two-dimensional lattice has a unique shortest basis up to signs and order, and because the greedy step — shorten the longer by the shorter — cannot go wrong. In three dimensions the greedy analogue still works: the shortest vector of a three-dimensional lattice is found by a similar procedure, and Gauss knew it.

It fails from four dimensions. A greedily reduced basis in four dimensions need not contain the shortest vector, and the counterexamples are small. That is where the subject stops being elementary, and it is one dimension above everything crystallography needs — including the four-dimensional lattices this collection builds when it asks where five-fold symmetry becomes legal — which is why a crystallographer can go a whole career without meeting the difficulty.

Where the shortest vector turns up in this collection #

It is worth listing, because the quantity is everywhere and is rarely named.

The packing radius of a lattice is half its shortest vector, so how densely a lattice packs circles is a question about the shortest vector and the determinant together.

The crystallographic restriction is proved by a shortest-vector argument in one of its two standard forms: assume a five-fold rotation, produce a shorter vector than the shortest, and conclude. Why five-fold is impossible is exactly that argument, and it works because a lattice has a shortest vector — which is the property that fails for a dense subgroup.

Whether a set of points is a lattice at all is decided by asking whether the shortest vector stops shrinking as the search widens. A five-fold module’s shortest vector keeps falling, and that is what makes it a module and not a lattice.

The reduced cell is built from short vectors, and the Bravais lattice type is read off the reduced cell’s metric.

So a quantity that is computationally trivial in the dimensions crystallography uses is doing structural work in four separate places here — which is a reasonable summary of why nobody in the subject had cause to notice that it is hard.

What is owned, and what is quoted #

Owned: Lagrange reduction implemented and traced, LLL implemented at the usual δ = ¾, the exhaustive enumeration with its widening range, and the comparison between them across dimensions two to seven with the misses reported where they occur.

Quoted: the NP-hardness of the shortest vector problem, LLL’s $2^{(n-1)/2}$ guarantee, and everything in the cryptography section. None of those is derived or checked here, and the essay’s own computations say nothing about any of them — they concern dimensions this enumeration cannot reach.

The refusal that keeps the two apart is that LLL’s answer is never reported as the shortest vector without the enumeration that says whether it is, and the enumeration is required to have contradicted LLL somewhere in its range. A check that has never disagreed with the thing it checks is not a check.

Why hardness is a resource #

A reader whose interest in lattices came from crystals will find the cryptographic use of them perverse: an object studied for two centuries because it is tractable, adopted because it is not. The reversal is worth a paragraph.

A cryptosystem needs a problem that is easy in one direction and hard in the other. Multiplying primes and factoring is the classic pair. Lattices supply another: given a good basis, finding a nearby lattice point is easy; given a bad one, it is not — and a unimodular change of basis turns a good basis into a bad one and is trivially reversible by whoever knows it.

What makes lattices attractive is the shape of the hardness rather than its degree. Factoring is hard on average only as far as anybody knows; lattice problems have a proof that a random instance is about as hard as the worst one, which is a much stronger guarantee and a rare thing to have.

And the shortest vector is the anchor of all of it, because the standard reductions run through it. So the quantity this collection computes in two lines, for lattices of two and three dimensions, is the quantity a security estimate for a few hundred dimensions is an estimate about.

A short vector is guaranteed to exist #

There is a gap between knowing something exists and being able to produce it, and lattices are one of the cleanest places to see it, because the existence result is elementary and the construction is the hard problem of the previous sections.

Minkowski’s theorem says that a symmetric convex region of volume greater than 2ⁿ times a lattice’s determinant contains a non-zero lattice point. Apply it to a ball and the conclusion is immediate: every lattice of determinant d in n dimensions has a non-zero vector no longer than roughly $\sqrt{n} \cdot d^{1/n}$. The proof is a pigeonhole argument on the region’s translates, it takes a paragraph, and it produces nothing.

So a bound on the shortest vector is available in every dimension, cheaply, with no algorithm anywhere. What is not available is the vector. The existence is easy and the construction is NP-hard, and the whole of the subject above lives in that gap.

That is worth setting beside LLL’s guarantee, because the two are of different kinds. Minkowski’s bound is a statement about the answer — the shortest vector is at most this long, whatever it is. LLL’s is a statement about a procedure — the vector it returns is within a factor of the shortest, whatever that is. A cryptosystem is safe when the second factor is large and the first is not helpful, which is exactly the situation from a few dozen dimensions upwards.

How short the shortest vector can be made #

There is a further question in the same neighbourhood, it is a classification rather than an algorithm, and it stops being answerable at about the same place everything else here does.

Minkowski’s bound is not tight. The best possible constant — how short the shortest vector must be, relative to the determinant, in the worst lattice — is Hermite’s constant for that dimension, and the lattices attaining it are the extremal ones. In the plane it is the hexagonal lattice; in three dimensions the face-centred cubic; and the constant is known exactly in dimensions one to eight and in dimension twenty-four, where the answers are the E₈ and Leech lattices.

Everywhere else it is unknown. Dimension nine has bounds and no value, and so does every dimension after it except twenty-four.

That is the same list as the packing and covering results, which is not a coincidence: Hermite’s constant is the densest lattice packing written in a different normalisation, so the two questions are one question and the dimensions where it is settled are the same dimensions. The tractable range of the extremal question and the tractable range of the algorithmic one are both small and they are small for unrelated reasons — one because the classification is hard, the other because the search is — and crystallography sits comfortably inside both.

Where the ladder goes next #

Sideways, to what a reduction is for in crystallography: the cell that settles the argument, where the point is canonicity rather than shortness, and where two descriptions of one lattice are required to produce the same answer.

And into the neighbouring application: recovering a cell from a bag of unlabelled reflections is a reduction problem in disguise, since the differences of the observed vectors generate the reciprocal lattice and a reduced basis of them is the cell.

So the subject divides into three statements that are easy to run together and are of three different kinds: a short vector exists, and that is a theorem; a short-ish vector can be produced, and that is an algorithm with an exponential guarantee; and the shortest vector can be produced, and that is a search nobody has made efficient.