Rounding a coordinate in the wrong basis

A basis that describes its lattice badly establishes what a reduction reduces — the orthogonality defect, the product of the basis vectors’ lengths over the lattice determinant — and what it may not change, which is the determinant itself. It then says what a short basis is worth, in three sentences, and measures none of them. The first is this:

With an orthogonal basis, deciding whether a point is in the lattice is division. With the 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 sentence names an algorithm. Write the target in the basis, round each coordinate to the nearest integer, multiply back: three lines, no search, and a lattice point comes out. It is Babai’s rounding-off, it is what anybody would write, and how wrong it is turns out to be a number the previous page already computed for a different reason.

At a skew of 2 the rounded point is a mean of 1.64 times too far and is the nearest point on half the targets. At 40 it is a mean of 26.16 times too far and is the nearest point on none of them. The same three lines on the reduced basis return the nearest point at every skew and every target.

Seeing the two bases beside the points is most of the explanation. A target sits somewhere inside the parallelogram the long arrows span; rounding its coordinates snaps it to whichever corner of that parallelogram the coordinates are nearest to, and on a cell that is forty times longer than it is wide, the nearest corner and the nearest point are routinely different points. The reduced basis spans a square cell, where they cannot be.

The worst case is the defect #

The number worth staring at is the worst column rather than the mean.

Across skews of 2, 5, 10, 20 and 40 the worst ratio over twenty-four targets reads 3.61, 7.52, 10.29, 22.87 and 40.02. The orthogonality defects of those same five bases are 2.24, 5.10, 10.05, 20.02 and 40.01.

The last three agree to three figures. The quantity the reduction is defined to reduce — which the previous page introduces as a measure of how badly a description was chosen, with a floor at one and a theorem behind it — turns out to be, in the plane, how many times too far rounding a coordinate lands in the worst case. It was a description of the basis; it is also a bound on a specific algorithm’s error, and nothing about the definition says so.

The agreement is not exact and the direction of the gap is the interesting part. At a skew of 2 the worst ratio is 3.61 against a defect of 2.24, so the defect is exceeded by 61 per cent; by a skew of 10 the excess is 2 per cent and by 40 it is four parts in ten thousand. The defect is an asymptotic description of the worst case rather than a bound on it, and it becomes a good one exactly where the failure becomes serious.

And in three dimensions it is not #

The relation is a fact about the plane, which the sweep says immediately when the dimension is raised.

At a skew of 40 in three dimensions the defect is 2,264 and the worst ratio is 106 — the defect over-predicts by a factor of twenty-one. The reason is structural rather than accidental: the defect is a product of n lengths over a determinant, so it grows like the skew to the power n − 1, while the rounding error is a sum of at most n half-basis-vectors and grows like the skew.

So the defect and the error agree in the plane because n − 1 is 1 there, and part company as soon as it is not. A reader taking the two-dimensional agreement for a general law would over-provision by orders of magnitude in any dimension where the question is interesting, and this collection has a standing warning about exactly that shape: a quantity measured in the smallest case, where several different things coincide, and carried into the case where they do not.

The useful half survives. In every dimension drawn the defect bounds the damage, and the bound is tight in two dimensions and loose in three. That is a usable statement — reduce until the defect is small and the rounding is safe — and it is weaker than the one the two-dimensional picture suggests.

What the three lines actually are #

The arithmetic is worth writing out, because the failure is visible in it before any measurement.

The target t is written in the basis by solving Bᵀc = t, exactly, over the rationals — which is the same exact solve the field’s first essay is about and costs nothing here at these sizes. Each coordinate is rounded to the nearest integer, and the coordinates are multiplied back through the basis.

The rounding moves each coordinate by at most a half. The point therefore moves by at most half the sum of the basis vectors’ lengths — and that is the whole of it. On an orthogonal basis half a basis vector is a short distance in a direction no other coordinate can undo, and the rounded point is the nearest one, exactly. On a skewed basis half of a long vector is a long way, and the other coordinates are not free to compensate because they have already been rounded.

Nothing about the arithmetic changes between the two cases. The same solve, the same rounding, the same multiplication, on two descriptions of one set of points — which is the shape this collection files under identical algebra, different arithmetic, except that here even the arithmetic is identical and it is the description that differs.

Reduction is not a guarantee #

The measurement above has a hole in it and it is worth being the one to point it out, because the hole is where the general statement lives.

The lattice in those figures is ℤ² scaled, which has an orthogonal basis, and the reduction finds it: the defect after reduction is exactly 1 at every skew. So “rounding in the reduced basis is exact” is a statement about a lattice that has an orthogonal basis, not about reduction.

Most lattices have no orthogonal basis at all.

On those, rounding in the reduced basis returns the nearest point for every target on 9 of the 20 lattices and misses on the other 11, with a worst mean ratio of 1.56 against the given basis’s 13.65. The reduction buys most of the distance and not the guarantee.

And the part reduction does not buy grows with the dimension. The reduced basis’s median defect runs 1.03, 1.08 and 1.16 at two, three and four dimensions, and the number of lattices on which rounding is exact everywhere runs 13, 9 and 7 of twenty. That is the honest general statement, and it is the one to carry: rounding coordinates is exact when the basis is orthogonal, close when it is nearly so, and reduction makes a basis nearly orthogonal by an amount that degrades as the dimension rises.

What “nearest” means here, and why it can be trusted #

Every ratio on these figures is divided by a distance to the genuinely nearest lattice point, which is a quantity somebody has to compute, and the closest-vector problem is hard in general. It is worth saying exactly what is done instead, because a measurement against a wrong reference is worse than no measurement.

The nearest point is found by enumeration: the target’s coordinates in the reduced basis are rounded to give a centre, and every lattice point whose coefficients lie within a small box of that centre is generated and measured. In two dimensions with a reach of four that is 81 points, in three with a reach of three it is 343, and the winner is the nearest point unless the true nearest lies outside the box.

It cannot, on these lattices, and the reason is the reduced basis rather than the box. The rounded point in a reduced basis is already within a bounded number of cells of the truth — the same statement the figure is measuring, used as a guarantee rather than as a subject — so a box of four cells around it contains the answer with a wide margin. The enumeration is therefore cheap and exact here, and the honest caveat is that it is cheap and exact because the basis was reduced first: the reference for the measurement is computed using the very thing the measurement is about.

That circularity is real and it does not undermine anything, since the reference is checked in the only way that matters — the enumerated point is never further than any of the three candidates, at any target, on any lattice, which is asserted rather than assumed. A box too small would show up as a ratio below one somewhere, and a ratio below one would mean the reference had missed a point that one of the cheap routes found.

The refusals #

The claim worth breaking is the one that is the whole content of the three lines: the nearest lattice point is the one whose coordinates are the rounded coordinates of the target. It is exactly true for an orthogonal basis and it is what anybody writes, and the assertion is fed twenty-four targets on a basis skewed by forty and required to fail. It fails on all twenty-four, at a mean of 26.16 times too far.

The second refusal is a control on the reference. The enumerated nearest point is fed the claim that one of the two cheap routes beat it, and has to refuse: a rounded point closer than the enumerated one would mean the box was too small and every ratio on the page was measured against the wrong number.

And the third is the one that keeps the second half of the essay honest. Fed the random lattices, the claim that rounding in a reduced basis always finds the nearest point has to fail — it does, on eleven of twenty in three dimensions — because the skew family says otherwise and the skew family is the special case.

The repair the field already knows about #

There is a better algorithm and it is worth naming, because the gap between the two is the reason the measurement above is not the end of the subject.

Babai’s nearest-plane method does not round all the coordinates at once. It takes the last Gram–Schmidt direction, rounds only in that, subtracts, and recurses on the remaining subspace — so each rounding is done in a direction orthogonal to everything still to be decided, and the error is bounded by half the Gram–Schmidt lengths rather than half the basis lengths. On a reduced basis those are much shorter, and the bound improves from a product to a sum.

It is not measured here, and the reason is worth stating rather than hiding: it needs the Gram–Schmidt vectors, which are rationals with large numerators on a skewed basis, and the exact arithmetic this field insists on makes it the expensive routine rather than the cheap one. The comparison that would be interesting is nearest-plane in exact rationals against rounding-off in the reduced basis, on the lattices where the reduced basis is not orthogonal — where the first has a proof and the second has eleven lattices of twenty missing the nearest point.

Why the target is not a lattice point, and why that had to be arranged #

A note on the construction, because the first version of this measurement returned exact for every route and every basis, and the reason is instructive.

The skew family’s lattice is ℤ² — every integer point of the plane — and an integer target is therefore a lattice point. The nearest lattice point to a lattice point is itself, at distance zero, and every algorithm finds it: rounding a coordinate that is already an integer rounds to itself. The measurement reported three routes agreeing perfectly and was measuring nothing at all.

The lattice is scaled by a hundred for that reason, so an integer target sits at a generic position inside a cell rather than on a corner. That is the whole of the fix and it is a gap of the kind this collection keeps finding: every number in the first run was correct, every assertion passed, and the experiment had no content. A measurement whose answer is exact everywhere deserves the same suspicion as one whose answer is wrong everywhere.

What this says about the first rung’s other two claims #

The page this one continues makes three claims about what a short basis is worth and measures none of them. One is now measured. The second is the shortest vector, which that page already treats — the reduction finds it exactly in two dimensions and within an exponential factor above — and the third is the conditioning of the basis matrix, which is worth a sentence here because the measurement above gives it a job.

The defect and the condition number “move together”, that page says, and are different quantities. On the skew family both are about k. What this page adds is that the defect has an operational meaning that the condition number does not: it is, in the plane, how many times too far a specific algorithm lands. A condition number describes how much an error could be amplified; the defect describes how much a rounding is, for the one algorithm anybody writes down. That is a stronger kind of statement and it is available only because there is no arithmetic error anywhere in this field to confound it.

Where this sits beside the rest of the field #

Three connections, and the first is the one that makes this page a continuation rather than a digression.

A fraction recovered from one remainder recovers a rational from its residue by running the Euclidean algorithm and stopping early, and the previous page on this ladder identifies that as lattice reduction in two dimensions. What it recovers is the shortest vector of a particular lattice. This page is about the closest vector to a target, which is a different question with a different hardness, and the two are related in the way a homogeneous problem is related to an inhomogeneous one: the shortest vector is the closest vector to the origin, and the origin is the one target for which rounding coordinates cannot go wrong, because its coordinates are all exactly zero.

The second is that this is the discrete version of a complaint this collection makes about continuous bases. A basis that is the same subspace and not the same thing has three spans of one null space behaving differently under a projection, because their bases are conditioned differently. Here three descriptions of one lattice behave differently under a rounding, because their bases are skewed differently — and the discrete case is sharper, because the answer is not slightly wrong. It is a different point.

The third is what this field’s absence of arithmetic error buys. Every number on this page is exact: the coordinates are rationals, the rounding is on a numerator and a denominator, the enumeration compares exact integers, and no quantity here would move if the computation were done again in any precision. So the ratios are properties of the basis and not of the machine, which is what makes a worst case of 40.02 against a defect of 40.01 worth reporting to four figures instead of to one.

What a description costs, across this collection #

The complaint — the object is fine and the description is terrible — has a measurement attached in several fields here, and the measurements are not the same kind of number.

The units the matrix is measured in is a scaling: one problem, many descriptions, and a condition number that reports the description. A condition number scaling cannot move is the counterweight, the part of the difficulty that survives every rescaling and therefore belongs to the object. The fill that is not independent is an ordering whose choice changes the cost by orders of magnitude with the answer untouched.

Against those, the lattice case has the property that makes it worth a page: the badness has a number with a floor, the floor is attained, and the number turns out to be an error bound. A condition number has no best value for a given problem and is not the size of any particular algorithm’s mistake. The orthogonality defect’s best value is 1, a basis achieving it exists whenever the lattice has an orthogonal basis, and in the plane the defect is how many times too far Babai’s rounding lands.

That is three properties a conditioning number does not have, and they are available here for the reason this whole field is: there is no arithmetic error to confound them.

Still open: the defect as a stopping rule #

The reduction here runs to completion, which in two dimensions is one step and in higher dimensions is a loop with a potential function behind it. Nothing in this field asks how much of that loop is needed for the purpose.

A code that reduces a basis in order to round coordinates in it does not need the reduced basis; it needs one whose defect is small enough that the rounding is exact for its targets. The measurements above say that threshold is not a fixed number — it depends on the dimension and on where the targets fall inside the fundamental cell — and a reduction stopped when the defect crosses a caller’s threshold would be a cheaper routine with a checkable postcondition. What that threshold is, as a function of dimension, and whether the defect falls smoothly enough during the loop for an early stop to mean anything, is unmeasured here.

The second open question is the one the previous section names: nearest-plane against rounding-off, in exact arithmetic, priced in the length of the numbers rather than in steps. This field’s whole habit is that the cost of an exact routine is the size of its operands, and the two algorithms differ in exactly that — one rounds an integer coefficient and the other rounds a rational with a Gram–Schmidt denominator behind it.

One line #

Rounding a coordinate finds the nearest lattice point only when the basis is nearly orthogonal, and in the plane the number of times too far it lands is the basis’s own orthogonality defect.