A relation among digits that were not there

Several numbers are given and the question is whether some integer combination of them is zero. It is the oldest question in this field — the Euclidean algorithm answers it for two, and that is lattice reduction in two dimensions — and it is the one place where a lattice is not a curiosity but the tool.

The construction is short. Scale each number by a large integer N, round it, and build the basis whose i-th row is that rounded value followed by the i-th unit vector. A vector in that lattice is $(\sum_i a_i \lfloor N x_i \rceil, a_1, \ldots, a_n)$ for integers $a_i$, so it is short exactly when the combination is small and the coefficients are small — which is what a relation is. Reduce the basis, and a short vector’s tail is a candidate relation.

The left edge of the picture is the theory, and it is where a reader would expect it. The right edge is not in the theory at all.

The left edge is the relation’s own size #

Too few digits finds nothing, and the reason is a size comparison rather than an accuracy one.

The relation’s vector has length about the size of its coefficients — $\sqrt{\sum a_i^2}$, a few tens here — because its first entry, the scaled combination, is nearly zero. Every other vector in the lattice has a first entry of order N unless its coefficients are enormous, so the relation is the shortest thing in the lattice provided N is large enough that no accidental combination beats it. The threshold is a statement about the lattice’s determinant against the relation’s length: roughly, N must exceed the coefficient size raised to the number of quantities.

The measurement follows that. With coefficients up to 3, six digits is already enough — 8 of 8. Up to 30, six digits recovers 4 of 8 and nine digits recovers 8. Up to 300, nine digits recovers 1 of 8 and twelve digits recovers 8.

The left edge moves with the coefficients and the right edge does not. That is the whole shape of the finding, and the asymmetry is what says the two edges are different kinds of thing.

The right edge is the format the numbers came in #

The collapse on the right is not a property of lattices, of reduction, or of the relation. It is a property of the numbers.

A measured quantity is a double. It carries about sixteen decimal digits and no more, and multiplying it by 10²⁵ does not produce twenty-five digits of anything: it produces sixteen digits of value followed by nine digits of whatever the last rounding left. Feed those to the lattice and the relation that was planted no longer holds in the integers it is given — the combination that was zero is now of order 10⁹ — so it is not short, and it is not what comes back.

What does come back is a perfectly good short vector: a genuine integer relation among the scaled integers the lattice was handed. Those integers are a value and a rounding, so the relation is partly about the numbers and partly about the rounding, and there is no way to tell which from the output. The reduction did not fail. It answered the question it was asked about the numbers it was given.

The same numbers held as exact rationals and scaled in integer arithmetic recover the relation at 8 of 8 through twelve, fifteen, eighteen, twenty-one, twenty-five, thirty and forty digits. There is no right edge. The curve rises once and stays.

The window narrows from both ends #

Two edges make a window, and the question a caller has is how wide it is. It narrows with the number of quantities, from both sides at once.

With coefficients up to 30 and the numbers held as doubles, recovery over eight trials reads:

The left edge moves right and the right edge moves left. More quantities need more digits before the relation is the shortest vector, and more quantities also mean more ways for the rounding to supply a shorter one — so the collapse arrives earlier. At three numbers the window is eighteen digits wide; at five it is about nine.

The extrapolation is the part worth carrying. A window that narrows from both ends closes, and the number of quantities at which it closes is decided by the data’s own precision rather than by anything about lattices: with sixteen digits available, a search over enough quantities has no setting at which it works, and there is no warning of that anywhere in the output. The exact rows of the same table read 8, 8, 8, 8, 8, 8 at three numbers and 0, 7, 8, 8, 8, 8 at five, because a window with no right edge cannot close.

Which makes this a rank decision without a threshold #

The shape belongs to a family this collection has a name for.

The rank depends on the ring establishes that a rank computed in floating point is a decision about a threshold, that removing the arithmetic error removes the threshold, and that the answer is still not a property of the array of numbers. A relation search is the same object one step further on. There is no threshold anywhere in it — the reduction is exact, the comparisons are on integers, nothing is declared negligible — and the answer still depends on something outside the numbers, which is how many of their digits are digits.

The two differ in how the dependence shows. A rank computed with a threshold announces its threshold, and a reader can at least ask whether it was the right one. A relation search announces nothing: it returns integers, they are exact, the combination it reports really is small, and whether it is a relation among the quantities or among their last three digits is a question the output does not contain.

That is the practical warning, and it is the one this page exists for. The evidence that a relation is real is not the residual. The residual is small by construction — the algorithm minimised it — and it is small whether or not the numbers had the digits to support it.

What the evidence actually is #

Three things, and only the third is available from a single run.

The coefficients must be small compared with the precision. A relation with coefficients of 10⁶ found from sixteen digits of data is not evidence of anything: there are enough combinations of that size to make a small residual by accident. The rule of thumb the construction gives is that the digits must exceed the number of quantities times the digits in the coefficients, with a margin, and a found relation whose coefficients sit near that boundary should be discarded rather than reported.

The relation must survive more digits, which is the test how many primes the answer needs replaces with a theorem when the quantity being reconstructed has a bound. A real relation among quantities that can be computed to more digits is still there at more digits, and one among the rounding is not — it changes, because the next digits are a different rounding. That is the standard check and it needs the numbers to be computable rather than measured, which is exactly the case where the whole question is interesting.

And the gap must be there. The reduced basis has n vectors and the one to report is the shortest; what says it is a relation rather than the smallest of n arbitrary things is the gap between its length and the next vector’s. On the recovered runs here that gap is several orders of magnitude; on the collapsed ones at forty digits there is a shortest vector and no gap, so the failure is visible from inside the output after all — but only if the second-shortest vector is looked at, and a routine that returns the first one has already thrown that evidence away.

This is the same measurement a fraction recovered from one remainder makes for rational reconstruction, where the recovery is unique above a size bound and below it the algorithm returns a different fraction with the same residue, and it is a perfectly good one. Both are lattice problems, both have a hard threshold, and in both the wrong answer is a correct answer to a question nobody asked.

The picture is worth keeping in mind because it says what the scaling is for. The first coordinate of every basis vector is the scaled combination, and it is enormous; the rest are the coefficients, and they are small. So the lattice is one that has been deliberately stretched along a single axis by a factor of N, which makes any vector with a non-zero first coordinate long, and leaves the relation — the one vector whose first coordinate is nearly zero — as the only short thing in it. The reduction is being used to find the short vector of a lattice that was built to have exactly one.

That is also why the failure at high precision is so quiet. Stretching by 10⁴⁰ when the numbers carry sixteen digits does not fail to stretch: it stretches a different lattice, built from different integers, and that lattice has its own genuinely shortest vector.

The refusals #

The claim worth breaking is the one a caller makes by turning the scaling up: more digits is more evidence. It is true when the digits exist and false as soon as they do not, and the assertion that recovery does not fall as the precision asked for rises is fed the double sweep — 8 of 8 at twelve digits, 4 at eighteen, 0 at twenty-five — and required to fail.

The second refusal is the control that keeps the first from being a claim about lattices. Fed the same relation among the same numbers held as exact rationals, the claim that recovery falls at high precision has to fail: it is 8 of 8 at every setting from nine digits to forty.

And the third covers the left edge, which is the part that is about lattices. Fed six digits and coefficients up to 300, the claim that a lattice recovers any relation given to it has to fail — there is not enough room between the relation’s vector and the accidental ones, and what comes back is an accident.

What the numbers being exact actually buys #

It is worth being precise about the exact side of the comparison, because “exact rationals” can be read as a fix and it is not one.

The rationals here are constructed, so every digit asked for exists — the number is a ratio of two integers and scaling it by 10⁴⁰ is an integer operation with an exact answer. That is the situation when the quantities come from a computation that can be run to any precision: a sum of a series, a continued fraction, an eigenvalue of an integer matrix. It is not the situation when they come from a measurement, and no amount of care in the lattice changes that.

So the honest statement of what the exact curve shows is: when the digits exist, more of them never hurt. The left edge is real, the right edge is an artefact of the data, and a caller who can compute their quantities to more digits should. A caller who cannot has a ceiling on the size of relation they can ever detect, it is set by their data and not by their algorithm, and it is computable in advance from the two numbers above.

Why the failure looks like success #

One more property of the collapse deserves stating, because it is what makes this worth a page rather than a footnote.

At forty digits with doubles the reduction returns a basis whose first vector is short, whose coefficients are modest integers, and whose combination of the given integers is small. Every assertion a routine could reasonably make about its own output passes. The determinant is unchanged; the basis is reduced; the vector is the shortest in the basis; the residual is tiny.

The only thing wrong is that the integers it was given are not the numbers it was asked about, and that is not visible from anywhere inside the computation. It is the same shape as the unlucky prime, where a modular elimination reports a singular matrix and is telling the truth about the field it is working over while being wrong about the problem — nothing in the residue distinguishes the two cases, no quantity is small enough to be suspicious, and the wrong answer is a correct computation of a different question.

The difference is where the substitution happened. There it is the ring; here it is the input, and the input was substituted by the caller rather than by the algorithm. A routine that took the number of valid digits as an argument rather than inferring it from a scaling would make the substitution impossible, and no interface offers that.

What this is not, and what the algorithms built for it do differently #

The construction above is the one anybody can write from the definition of a lattice, and it is not what a code that hunts relations for a living uses. The difference is worth naming, because two of the three findings here transfer and one does not.

The precision is chosen from the answer rather than from the data, and it is chosen in advance. A serious relation search decides how many digits it needs from the size of relation it is willing to report — the number of quantities times the digits in the largest coefficient it will accept, plus a margin — and then obtains the quantities to that many digits, which is possible because they come from a computation rather than from an instrument. That is the discipline the right edge here punishes the absence of: the failure is not that too much precision was asked for, it is that the precision asked for was not checked against the precision available.

The reduction is incremental rather than one shot. Algorithms designed for this run the reduction as quantities arrive and watch a quantity that grows as the relation emerges, which gives them the gap test for free and at every step rather than once at the end. What they do not have is the exact arithmetic this page uses: at the sizes a relation search runs at, the basis entries are hundreds of digits long — the swell an answer with no error in it measures in a different exact routine and the Gram–Schmidt is kept in extended-precision floating point, which puts them squarely in the territory the previous essay on this ladder is about — a rounding of a coefficient, with the determinant invariant unable to see what it did.

And the coefficients are bounded by declaration. A search that will accept any coefficients has no left edge and no evidence; one that will only report coefficients under a stated size can compute, in advance, how many digits it needs and whether it has them. The bound is the whole of the honesty, and it converts the question is this a relation? into the answerable is there a relation with coefficients under this size, given numbers with this many digits?

The third of those is the one this page would most like a reader to take. Both of the failures drawn here — the accident at the left edge and the rounding at the right — are failures to state a bound before looking, and both produce output that is indistinguishable from success.

Three failures that look like answers #

This collection keeps a list of computations whose wrong answer is a correct answer to a question nobody asked, and the relation search belongs on it.

A prime that divides the answer is a modular elimination reporting a singular matrix, truthfully, about a field the caller did not mean to be working over. A fraction recovered from one remainder is a reconstruction below its size bound returning a different fraction with the same residue — a perfectly good one. An exact answer to a measured problem is an exact solve of the system the data defines, wrong in its first digit, because conditioning was never a statement about arithmetic.

All three share a shape and this one adds a fourth instance of it: the substitution happens at the boundary of the computation, so nothing inside can see it. In the first the ring was substituted; in the second the modulus was too small to determine the answer; in the third the data was not what the question was about; and here the digits past the sixteenth are a substitution the caller made by asking for them.

The practical form is the same in all four and it is the only defence any of them has. A routine should take the thing it is trusting as an argument — the field, the size bound, the data’s accuracy, the number of valid digits — rather than inferring it from something that happens to be available. Every one of these four failures is an inference from a scaling, a modulus or a matrix about something that was never encoded in it.

Still open: the gap as a returned quantity #

The third piece of evidence above is computable and is thrown away, which is the obvious repair and is not quite as obvious as it looks.

A relation search that returned the shortest vector and the ratio to the second shortest would let a caller distinguish a relation from an accident without re-running at higher precision. What that ratio should be compared against is the open part: on the recovered runs it is several orders of magnitude and on the collapsed ones it is not, but a threshold between them would have to be a function of the dimension and the coefficient size, and nothing here measures it across enough of either to propose one.

The second open question is whether the collapse can be detected from a single precision. Running the search at N and at N/10 and comparing the coefficients is two reductions rather than one, costs nothing at these sizes, and would separate a relation among the values from one among the rounding — because the first is the same relation at both scalings and the second is not. Whether that test is reliable, or whether the two scalings share enough of their rounding to agree spuriously, is the measurement this page does not make.

One line #

A lattice finds an integer relation when it is given enough digits and finds one among the rounding when it is given more digits than the numbers have, and the output is identical in both cases.