A basis that describes its lattice badly

A lattice is the set of integer combinations of some vectors. The vectors are a basis; the lattice is the set of points; and unlike a vector space over the reals, where any two bases of the same subspace are related by an invertible matrix, here the relation has to be unimodular — integer entries, integer inverse, determinant ±1 — because the integer combinations have to land on the same points either way.

That leaves a great deal of freedom, and it is freedom to describe a very simple object extremely badly.

The lattice in the figure is all of ℤ² — the integer points of the plane, the simplest lattice there is. The basis it is handed describes those points as combinations of (1, 0) and (7, 1), which is true, and which makes the coefficient of a point like (0, 1) equal to (−7, 1) rather than to anything obvious. Nothing is wrong. Every point is reachable, uniquely, with integer coefficients. The description is simply seven times worse than it has to be, and at a skew of 10²⁰ it would be 10²⁰ times worse without ever becoming incorrect.

The quantity that separates two bases of one lattice #

Any basis of a lattice spans a fundamental cell, and every basis of the same lattice spans a cell of the same volume, because the determinant of a unimodular change is ±1. So the volume — the lattice determinant — is an invariant: it belongs to the lattice and not to the description.

What varies is the shape. Hadamard’s inequality says the product of the basis vectors’ lengths is at least the volume they enclose, with equality exactly when they are mutually orthogonal, so the ratio

orthogonality defect  =  (Π ‖bᵢ‖) / |det B|

is at least one for every basis, equal to one only for an orthogonal one, and larger the more skewed the description is. It is a single number and it is exactly the thing a reduction reduces.

That is the same inequality the modular route budgets primes with, used the other way round: there it bounds a determinant from above by row lengths, here it bounds row lengths from below by a determinant. It is one theorem doing two jobs in one field, which is worth noticing because the two look unrelated.

Reduced in exact arithmetic, and why that is not fussiness #

The reduction here runs in exact rational arithmetic: the Gram–Schmidt coefficients are fractions, the size-reduction rounds an exact rational to the nearest integer, and the exchange condition is decided by comparing two exact rationals.

That is not a purity gesture. A lattice reduction is a discrete algorithm whose decisions are comparisons — swap or do not swap, subtract this integer multiple or that one — and a comparison decided by a float that is a rounding away from the boundary is a different algorithm on some inputs. It is the same shape of failure as a partition decided in the last digit: the output is not a number that could be slightly wrong, it is a basis that is either this one or that one.

The rounding inside is the part most likely to be got wrong quietly. The coefficient being rounded can exceed 2⁵³ on a basis with long vectors, and Math.round(Number(q)) then rounds the wrong integer — which leaves the basis unreduced without failing anything, because the algorithm’s postcondition is about sizes rather than about that particular step. So the rounding here is written on the numerator and denominator directly, and the reduced basis is asserted to be integral before it is returned.

The conserved quantity is the check #

Every step of the reduction is a unimodular operation: subtract an integer multiple of one basis vector from another, or exchange two. So the lattice determinant must be unchanged at the end, exactly — not to a tolerance, as an integer.

That is the check, and it is a good one because it is sensitive to precisely the mistakes an implementation makes. A size reduction with the wrong rounding still preserves it. A swap implemented as an overwrite does not. A coefficient computed as a float and truncated does not. The determinant is 1 before and 1 after on the hero’s lattice, and the assertion compares integers.

The defect, meanwhile, is asserted to have gone down rather than up — which sounds trivial and is the other half of the pair. A reduction that preserved the determinant and made the basis worse would be a correct unimodular transformation and a useless one.

What the reduction actually does here, in one step #

On this family the algorithm is short enough to follow completely, and following it makes the two halves of a reduction visible separately.

The basis is (1, 0) and (k, 1). The Gram–Schmidt coefficient of the second against the first is exactly k — a rational whose denominator is 1 — so the size-reduction step subtracts k times the first vector from the second and leaves (0, 1). The exchange condition is then satisfied, the loop ends, and the returned basis is the standard one.

One step, at every skew from 2 to 40. The defect falls from a little over k to exactly 1, the determinant is 1 throughout, and the number of steps does not grow with the skew at all — which is worth noticing, because the size of the coefficient does. A size reduction on a basis with a skew of 10²⁰ is one step whose coefficient has sixty-seven bits in it, and it is the arithmetic on that coefficient rather than the number of steps that costs.

That is the field’s usual observation arriving in a new place: the operation count is one and the price is the length of the operand. It is also why the exact rounding matters. A coefficient of 10²⁰ does not survive a round-trip through a double, and the step that should have cleared the basis in one move would leave it skewed by whatever the rounding lost.

What this has to do with the rest of the field #

Two connections, and the first is that this essay is a generalisation of one already written.

Rational reconstruction recovers n/d from a residue by running the Euclidean algorithm and stopping early. The set of pairs (a, b) with a ≡ b·u (mod m) is a two-dimensional lattice of determinant m; the answer is its shortest vector; and the Euclidean algorithm is lattice reduction in two dimensions, where it is exact, terminating, and two thousand years older than the problem. Everything in that essay — the uniqueness of the short vector, the bound at √(m/2), the cliff rather than the slope — is a statement about a lattice with a determinant, read in the smallest case.

The second connection is that a lattice is what the Smith normal form describes. An integer matrix’s rows generate a lattice; the Hermite normal form is a canonical basis for it; the Smith form describes the quotient. So this field has three descriptions of one object — a canonical basis, a quotient decomposition, and a short basis — and only the third is not canonical, because shortness does not determine a basis uniquely. Which is the reverse of the usual situation here, where the canonical object is the expensive one and the practical routine returns something non-unique: a Hermite form is unique and costly, a reduced basis is cheap and is one of many, and both are correct answers to different questions about the same set of points.

Why the reduction terminates at all #

There is one thing about the algorithm that is genuinely surprising and is worth a paragraph, because it is the only part of the whole construction that is not immediate.

The loop alternates between size reduction, which does not change any Gram–Schmidt length, and exchanges, which do. A basis could in principle be swapped back and forth for ever. What prevents it is a quantity that strictly decreases: the product of the Gram–Schmidt lengths raised to descending powers, which is a positive integer for an integral basis and which an exchange multiplies by at most δ = 3/4. A positive integer that shrinks by a quarter each time cannot do so many times.

So termination rests on the basis being integral, which is why the routine asserts that the returned vectors have denominator 1 rather than assuming it, and why a reduction implemented over the reals needs an entirely different argument. The guard in the code is a step cap with an assertion attached; on every lattice drawn here the cap is never approached, and if it were the figure would fail rather than silently return a basis the loop had abandoned.

What a short basis is worth #

Reduction is worth doing because a skewed basis makes easy questions hard.

Is a given point in the lattice? With an orthogonal basis it is division. With the hero’s skewed basis the coefficients are large and alternate in sign, and rounding to the nearest lattice point by rounding each coefficient is simply wrong — the nearest point in coefficient space is not the nearest point in the plane when the basis is skewed. That failure is the same one the essay on a basis of a subspace describes in the continuous setting, where two spans of one null space behave differently under exactly the operations that are supposed not to care.

How short is the shortest vector? The reduced basis’s first vector is within a factor of $2^{(n-1)/2}$ of it, which is a bound rather than an answer and is the property the whole algorithm is named for. In two dimensions the reduction finds the shortest vector exactly, which is why reconstruction can be said to find rather than approximate — and it is the reason the previous essay could assert a cliff rather than a trend.

And the conditioning of the basis matrix. The defect and the condition number are different quantities and they move together: a defect of 40 on the hero’s lattice comes with a basis matrix whose two-norm condition number is about 40 as well. The relation is not exact — the defect is a product of lengths over a determinant, the condition number is a ratio of singular values — but they are both measuring the same skew, from the two directions this site usually measures things from. It is the one place in this field where a condition number is still doing work: not amplifying an error, since there is none, but describing how badly a description was chosen.

Where a badly chosen description turns up elsewhere on this site #

The general complaint — the object is fine and the description is terrible — is one this collection has made in four other places, and collecting them is the fastest way to see what is particular about the lattice case.

A basis that is the same subspace and not the same thing is the continuous version: three spans of one null space, identical as subspaces, behaving differently under a projection because their bases are conditioned differently. The units the matrix is measured in is the same complaint about a scaling: one problem, many descriptions, and a condition number that reports the description rather than the problem. A condition number scaling cannot move is the counterweight — the part of the difficulty that survives every rescaling and therefore does belong to the object. And the ordering a sparse elimination is given is a description whose choice changes the cost by orders of magnitude with the answer untouched.

What is unusual here is that the badness has a number with a floor, and the floor is attained. A condition number has no natural best value for a given problem; the orthogonality defect’s best value is 1, it is 1 exactly when the description is as good as descriptions get, and there is a theorem saying so. That is a rarity on this site, where most quantities are compared against a bound nobody reaches.

The refusal, which is a bound rather than a preference #

The claim worth breaking is that a reduced basis is orthogonal. It is not, and cannot be in general: most lattices have no orthogonal basis at all, and the reduction returns the best it can find in polynomial time rather than the best that exists.

The defect after reduction on the hero’s lattice is exactly 1, because ℤ² does have an orthogonal basis and the reduction finds it. On a lattice that does not, the defect after reduction is above 1 and stays there — and the assertion that a reduced basis achieves a defect below one is fed the reduced basis and has to reject it, because Hadamard’s inequality forbids it for every basis of every lattice.

That is a refusal of a different kind from most on this site. Usually the claim being broken is one somebody might reasonably hold; this one is broken by a theorem, and the assertion exists to make sure the code’s notion of the defect is the one the theorem is about. A defect computed with a determinant of the wrong sign, or with lengths rather than squared lengths, would sail below one and nothing else in the routine would notice.

Higher dimensions, and what is not measured here #

Everything above is drawn in two dimensions, where the reduction finds the genuinely shortest vector and the picture can show the lattice. That is a real limitation and it is worth stating what it hides.

In dimension n the algorithm guarantees only that its first vector is within $2^{(n-1)/2}$ of the shortest — a bound that is exponential in n and is nearly attained on constructed examples. So “reduced” means something much weaker than it does here: a basis whose defect has been improved by a provable factor rather than a basis that is as good as the lattice allows. Finding the shortest vector exactly is believed to be hard, and a great deal of modern cryptography rests on its being so.

The implementation here is the original algorithm with δ = 3/4, in exact rationals, which means it is correct and it is not fast: a full Gram–Schmidt is recomputed after every step rather than updated, and the coefficients are exact fractions rather than floating point with a controlled error. Both choices are deliberate — the whole point of this field is that the comparisons are decided exactly — and both would be wrong in a routine meant for the dimensions where the algorithm is actually used.

What the two-dimensional case does give is the complete picture: a conserved quantity, a reduced quantity, a bound relating them, and a reduction that attains the bound. The n-dimensional case has all four objects and attains nothing, and the honest way to introduce it is with the case where the arithmetic can be watched.

What the higher dimensions actually do #

Saying the bound is exponential and nearly attained on constructed examples leaves out what happens on a basis nobody constructed, and that is worth having, because a guarantee this loose says almost nothing about the typical case either way.

Twenty random bases per dimension with entries uniform on [−20, 20], the shortest vector found by enumerating integer coefficients over a box, and ‖b₁‖ divided by it:

The median is exactly 1 at every dimension. On a random basis the algorithm returns the genuinely shortest vector rather than an approximation to it, and the worst of a hundred runs is 1.37. The gap between the guarantee and the behaviour widens with n — at n = 6 the bound permits 5.66 and the worst observed is 1.22 — which is what “nearly attained on constructed examples” means seen from the other side. The constructions are what attain it, and an ordinary basis is nowhere near.

That does not weaken the cryptographic point above, and it is worth saying why. The hardness rests on the worst case in dimensions of several hundred, and a bound that is a factor of five loose at n = 6 is a bound that is a factor of 10³⁰ loose at n = 200 only if the median keeps behaving. Nothing here measures that, and the whole reason the constructions exist is that it does not.

The bug this measurement found #

Sweeping signed bases — rather than the positive skews the figures draw — is the whole of what was needed, and it found a defect in the reduction itself.

nearestInt, the routine that rounds a Gram–Schmidt coefficient to the integer the size-reduction step subtracts, computed ⌊q − ½⌋ rather than the nearest integer whenever q was negative. So every step with a negative coefficient subtracted roughly twice as much of bⱼ as it should. On [[−13, 3], [7, −3]] the reduction returned [[−13, 3], [−19, 3]] after one step — a second vector two and a half times longer than the one it replaced — and reported it as reduced. The median approximation factor at n = 3 was 1.43 with a worst case of 4.65, which is above the guarantee the algorithm is supposed to satisfy, and a ratio above its own bound is the shape of evidence that says bug rather than loose bound.

It survived because every basis drawn on this page is [[1, 0], [k, 1]] with k positive, where the branch is never taken. Every drawn case is byte-identical after the fix — defect 5.099 → 1 at a skew of five, the identity basis out at all eight skews — which is what a repair to a shared computation should look like when the figures never exercised the broken path. It is also a defect of absence rather than of value — every check asked whether the output was well-formed and integral, and none asked whether it was better than the input, which is the gap a bound that is proved is about.

assertTheReductionSucceedsOnRandomBases now sweeps signed bases at four dimensions, checks the reduction against enumeration, and requires the median factor to be exactly one.