The knob and the rounding

A lattice reduction is a loop with two moves in it. Size-reduce: subtract an integer multiple of one basis vector from another, the multiple being the nearest integer to a Gram–Schmidt coefficient. Exchange: if the Lovász condition $\|b^*_k\|^2 \ge (\delta - \mu^2)\|b^*_{k-1}\|^2$ fails, swap two vectors and step back.

Both moves are decided by comparing numbers. The first compares a rational against the half-integers to choose which integer to subtract; the second compares two rationals, with a parameter δ in one of them. Everything else in the algorithm is bookkeeping, so if the reduction has a sensitivity to how its numbers are represented, it is in those two comparisons, and the parameter is the one knob anybody is offered.

Neither of those sentences turns out to be a good guide to what decides the answer.

The parameter buys a promise #

Take the knob first, since it is the one a caller is offered and the one the literature is written about.

δ sits in the exchange condition and the algorithm requires it to lie between 1/4 and 1. The classic choice is 3/4, chosen because it makes the termination argument’s potential function shrink by a clean factor; implementations that care take it to 0.99. What it buys is the approximation guarantee: the reduced basis’s first vector is within $(4/(4\delta - 1))^{(n-1)/2}$ of the shortest vector in the lattice, which improves without limit as δ approaches one.

Across δ from 0.50 to 0.99 the bound falls from 16.00 to 1.83 — nearly a factor of nine in the strength of the promise. The step count rises from 11 to 21. And the defect of the basis that actually comes back moves from 1.3248 to 1.3248: all of the change it ever makes arrives between δ = 0.60 and δ = 0.75, and past that it is flat to four figures.

In three dimensions the parameter does nothing at all. The defect is the same number at every δ drawn, to twelve figures, because the reduction reaches the same basis by the same route and the exchange condition it is tested against is never the thing that decides.

So the knob buys a stronger statement about a basis it does not change. That is not a defect in the theory: the guarantee is a worst case over all lattices, the bases here are ordinary ones, and a worst-case bound improving while a typical case does not is the shape this collection meets constantly — the guarantee is exponential and the behaviour is not is the standing version of it. What is worth having is the practical form: the cost is real and the benefit is not, on ordinary input. Ninety-one per cent more steps at n = 5, for a basis that is the same basis.

The honest qualifier is that the bases are random. The lattices where δ matters are the ones the bound was proved for and the constructions that nearly attain it, and nothing here samples those — which is the same caveat the previous essays on this ladder attach to every statement about typical behaviour, and it is the reason the bound exists.

The family is chosen because it makes the algorithm’s two moves separable. There is exactly one size-reduction step, its coefficient is exactly the skew, the exchange condition is satisfied immediately afterwards, and the loop ends — so anything that goes wrong went wrong in the one rounding, and there is nothing else for it to be. A random basis would exercise both moves many times and the failures would be entangled.

It also makes the answer knowable. The correct output is the standard basis of ℤ², defect exactly 1, at every skew, so there is no reference computation to trust: the right answer is written down in advance and anything else is wrong.

And the rounding buys everything #

The other comparison is the one nobody offers as a parameter, and it is where the answer lives.

Take the basis [[1, 0], [k, 1]]. Its Gram–Schmidt coefficient is exactly k — a rational with denominator one — so the reduction is a single size-reduction step that subtracts k times the first vector from the second, leaving [0, 1], and stops. One step, one integer, and the integer is k.

A double holds k exactly up to 2⁵³. Past that it does not, and Math.round(Number(k)) returns a different integer.

The hero figure is what happens. Below 2⁵³ the two arithmetics return the identical basis and the defect is 1. At 2⁵³ + 12345 the double rounds to one less than k, the reduction subtracts one too few, and the basis that comes back is [[1, 0], [1, 1]] — defect 1.414. At 2⁵⁶ the residue is 7 and the defect is 7.07. At 2⁶⁰ it is 57 and 57.01. At 2⁷⁰ the double has lost the whole added constant, the residue is 12,345, and the reduction returns a basis 12,345 times worse than the orthogonal one it should have found.

The defect that comes back is $\sqrt{1 + r^2}$ for the residue $r$, at every exponent, exactly. That is not a fit and not a trend: the returned basis is [[1, 0], [r, 1]], which is the original basis with as much of the skew removed as a double could see. The failure is not noise added to a correct answer, it is the correct answer with a piece of the input still attached.

The check that cannot see it #

The previous essays on this ladder establish that the lattice determinant is the invariant a reduction may not change, and that this makes it the check:

Every step of the reduction is a unimodular operation, 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.

Every run on the hero figure preserves it. The determinant is 1 before and 1 after at 2⁵³, at 2⁶⁰ and at 2⁷⁰, including the run that returns a basis 12,345 times worse than the one it should have.

It has to be. The basis is integral, every operation performed on it is an integer row operation with determinant ±1, and what decided which multiple to subtract is not part of that argument. A size-reduction step subtracting the wrong integer is still a unimodular operation. It is a perfectly legal change of basis for the same lattice; it is simply a useless one.

So the invariant certifies that the output describes the right lattice, which is exactly what it was introduced to certify and is not what a caller wants to know. The quantity that would have caught this is the defect, which is asserted to have gone down — and it did go down, from 2⁷⁰ to 12,345, which is a reduction by a factor of 10¹⁶ and is not a reduced basis.

The check that does catch it is the algorithm’s own postcondition: is the returned basis LLL-reduced? Every coefficient at most a half in magnitude, every exchange condition satisfied. Tested exactly, the float reduction’s output fails at every exponent from 2⁵³ up. That test costs one Gram–Schmidt of the output and it is not in any implementation this collection has looked at, because the output of a reduction is reduced by construction — which it is, when the construction’s arithmetic is exact.

Which of the two comparisons tolerates a float #

The natural conclusion from the hero figure is that lattice reduction needs exact arithmetic throughout, and that is not what the measurement says. It says something narrower and more useful.

The exchange comparison tolerates floating point well. Running the whole reduction with the Gram–Schmidt coefficients computed in doubles — but recomputed from the current integer basis at every step rather than updated — returns the identical basis to the exact reduction on every random lattice drawn, in three and five dimensions, at entry sizes from 2¹⁰ up to 10²⁵. Not nearly the same basis: the same integers.

The size-reduction comparison does not, and the boundary is exactly where the integer stops fitting in a double.

That asymmetry has a cause worth stating. The exchange condition compares two positive quantities and acts on the sign of their difference; a relative error of 10⁻¹⁶ in each changes the decision only when the two are within 10⁻¹⁶ of each other, which is a measure-zero coincidence on random input and costs one unnecessary swap when it happens. The size reduction does not compare, it selects an integer — and an integer selected wrongly is wrong by at least one, which is not a small perturbation of anything. A comparison can be nearly right. A choice of integer cannot.

That is the same distinction a partition decided in the last digit draws in a different field, and the one the first essay on this ladder gives as the reason for exact arithmetic here: the output is not a number that could be slightly wrong, it is a basis that is either this one or that one. The measurement refines it. Of the two decisions the algorithm is made of, one is a comparison and survives doubles, and one is a selection and does not.

The two ways the selection has been got wrong here #

This site’s own routine has had both of the available bugs in that one line, and they are worth setting beside each other because they failed in opposite directions and neither failed loudly.

The first was the magnitude. Math.round(Number(q)) is the natural way to round a rational to an integer and it is what the hero figure measures: correct to 2⁵², wrong above it, and wrong by an amount that is the part of the coefficient a double could not represent. The routine here computes the nearest integer on the numerator and denominator directly for that reason, and the comment saying so predates this measurement.

The second was the sign. The rounding computed ⌊q − ½⌋ rather than the nearest integer whenever q was negative, so every step with a negative coefficient subtracted about twice as much as it should. On [[−13, 3], [7, −3]] the reduction returned a second vector two and a half times longer than the one it replaced and reported the basis as reduced. It survived because every basis drawn on this ladder is [[1, 0], [k, 1]] with k positive, where the branch is never taken.

Both bugs are in the same expression, both preserve the determinant exactly, both return a legal basis for the right lattice, and both were found by a measurement rather than by a check — the shape a bound that is proved is about, where a quantity’s absence is what no gate asks after. The sign bug was found by sweeping signed bases and comparing against enumeration; the magnitude bug was found by reasoning about 2⁵³ and is now drawn. The postcondition test would have caught both, and it is three lines.

The exchange condition, measured rather than assumed #

The claim that the exchange comparison tolerates doubles deserves the numbers behind it, since the whole recommendation rests on it.

The reduction was run twice on each of a series of ensembles — once in exact rationals, once with the Gram–Schmidt recomputed in doubles from the current integer basis at every step and the exchange decided on those — and the two output bases compared entry by entry as integers. Random bases in three and five dimensions with entries up to 2¹⁰, 2³⁰, 2⁵² and 2⁷⁰, and relation lattices — whose Gram–Schmidt is far worse conditioned, because one column is enormous and the rest are an identity — at scalings of 10⁶, 10¹², 10¹⁸ and 10²⁵ in three, four and five dimensions: sixty bases, sixty identical, and the comparison is on integers rather than on a tolerance.

Not one swap decided differently, at any size drawn. That is a stronger result than expected and it is worth being clear about what it is evidence for. It says the decision the exchange condition makes is robust, because it is a comparison of two quantities that are rarely close; it does not say a float Gram–Schmidt is accurate, and on the relation lattices it certainly is not. The reduction survives an inaccurate Gram–Schmidt because it only ever asks that Gram–Schmidt for the sign of a difference.

Which is the useful form of the finding. An algorithm that only asks its arithmetic for comparisons is far more robust than one that asks it for values, and the reduction asks for one value — the integer to subtract — and one comparison. It is the value that fails.

The refusals #

The claim worth breaking is the one the first essay on this ladder states as the check: every step is unimodular, so the determinant is preserved, and that is the test. It is true as far as it goes and it is not a test of the reduction. The assertion that an unchanged determinant implies a reduced basis is fed the run at 2⁷⁰ — determinant 1 before, determinant 1 after, orthogonality defect 12,345 — and required to fail.

The second refusal covers the over-reading in the other direction, which is that floating point cannot be used here at all. Fed the runs below 2⁵³, where the two arithmetics return byte-identical bases, the claim that a float reduction differs from an exact one has to fail.

And the third is a control on the family. The exact reduction is fed the claim that it returns something other than the orthogonal basis at some skew, and has to refuse at every exponent drawn — a page whose whole subject is one routine going wrong needs the other routine to be right, and needs to say how it knows.

What a routine should do about it #

Short, and it follows from the asymmetry above.

Compute the size-reduction coefficient exactly, on the numerator and denominator, or in an integer arithmetic wide enough for the basis. This is cheap: it is one rounding per step, against a Gram–Schmidt per step.

Compute the Gram–Schmidt in whatever is fast, which is the reverse of what an answer with no error in it recommends for the routines whose whole cost is the length of their operands. The measurement says doubles reproduce the exact reduction on every lattice drawn here, and the implementations that are genuinely fragile update μ incrementally rather than recomputing it — which is a different arithmetic and is not what is measured on this page.

Check the postcondition. One Gram–Schmidt of the output, every coefficient at most a half, every exchange condition satisfied. It costs one step’s worth of work at the end of a loop that ran for many steps, it is an exact test with no tolerance in it, and it is the only thing here that would have caught either bug on the day it was written.

And do not spend anything on δ. The measurements above say 0.75 and 0.99 return the same basis on ordinary input and the second costs 91 per cent more steps. A caller who needs the guarantee the parameter improves is a caller working on the lattices the guarantee was proved for, and they will know it.

What this does not measure #

Not an incremental Gram–Schmidt. The float reduction here recomputes the coefficients from the integer basis at every step, which is the arrangement that is most accurate and least like a fast implementation. The received wisdom about floating-point LLL being delicate is about implementations that update μ through the swaps, where errors accumulate across the run, and the boundary such an implementation has is not the one drawn here.

Not large dimensions. Everything above is two, three and five dimensions — the range a basis that describes its lattice badly can draw and enumerate against, where the exact arithmetic is affordable and the answer can be compared against. The dimension where lattice reduction is actually used is a few hundred, and there the exact routine is not available to compare against — which is precisely why implementations use floats and why the postcondition test matters more rather than less.

And not the cost. The exact reduction here recomputes a full rational Gram–Schmidt after every step, which is quadratically wasteful, and the numbers in it grow. How much of the exact routine’s price is the exactness and how much is that arrangement is a separate measurement, and it belongs beside the answer is longer than the question, where the length of the output is a floor under every exact solver rather than a property of one.

Where a decision decided by arithmetic has been met before #

This collection has a standing interest in computations whose output is a choice rather than a number, because a choice cannot be slightly wrong.

A partition decided in the last digit is the spectral field’s version: a Fiedler vector’s sign decides which side of a cut a vertex falls on, and a rounding at the boundary moves a vertex rather than perturbing an answer. An ordering that does not wait for the numbers is the sparse field’s, where a symbolic decision is made before any value is read precisely so that no arithmetic can move it. A threshold between fill and growth is the case where the choice is deliberately made to depend on the numbers, with the dependence bounded.

The reduction here has one of each, in the same loop. The exchange is a comparison whose answer moves by one swap when it is wrong, and a swap taken a sweep early or late is absorbed by the loop. The size reduction selects an integer, and an integer selected wrongly is a different basis. Two decisions, one arithmetic, and only one of them is a hazard — which is a more useful statement than this algorithm needs exact arithmetic, and it is the one the measurement supports.

Still open: what a reduction should return besides a basis #

The postcondition test is cheap enough to run always, which raises the question of what a routine should hand back.

A reduced basis with its own defect attached is a strictly more useful object than a reduced basis: the number is computed on the way, the caller of a rounding routine needs it to know whether rounding coordinates in that basis means anything, and a defect that came back larger than expected is the signal that the arithmetic went wrong. Nothing here returns it, and there is no reason not to.

The harder question is what a routine should do when its own postcondition fails. Re-running in wider arithmetic is the obvious answer and it is expensive; re-running only the steps whose coefficient exceeded the representable range would be cheaper and needs the routine to have recorded which those were. Whether a reduction can be repaired from a failed postcondition without starting again — whether the residue can simply be reduced a second time, which on the family here would work and in general may not — is unmeasured.

One line #

The parameter a lattice reduction is specified by strengthens a promise and returns the same basis, while the rounding nobody writes down decides the answer outright — and the invariant the reduction is checked against certifies both.