Two precisions guard the other edge

A relation among digits that were not there found that a lattice relation search works inside a window of precisions. Below it the planted relation is not yet the shortest vector in the lattice, and the search returns something else; above it, when doubles are scaled past the sixteen digits they hold, it returns something else again. The essay proposed two things a search could do to tell its successes from these failures without being rerun at higher precision. The room a relation has to stand out measured the first — return the gap between the shortest and the next-shortest reduced vector — and found it a certificate with a budget: a relation among n numbers from doubles has a gap of about sixteen digits over n − 1, less the relation’s own size, and when that budget is small the gap cannot tell a relation from an accident. Among six numbers with coefficients up to 30 it vouched for one found relation in 35.

The second proposal was to run the search at N digits and at N/10, and compare. A relation among the numbers is the same relation whether the numbers are scaled to fifteen digits or fourteen; a relation among the rounding depends on the last digit, and dropping it should change the answer. The essay named the risk in one sentence — that the two scalings might share enough of their rounding to agree spuriously — and left it there. Both halves can be measured on the same runs the gap was measured on: numbers of sixty random digits, so that the planted relation is the only small one there is, a relation with coefficients drawn up to 3, 30 or 300, rounded to doubles and scaled to eight precisions from six digits to thirty, sixteen runs at each.

What changes when a digit is dropped #

The search at N/10 is not a second opinion on the same lattice. Scaling by a tenth divides the first column of the lattice basis — the numbers themselves — by ten and leaves the identity part alone, so the lattice is a different lattice, and its shortest vector is chosen afresh. What the comparison tests is whether the vector the first search returned is still the shortest when the numbers carry one digit less.

For a genuine relation that should hold across a wide range. The relation’s own vector does not change with the scaling — its coefficients are the relation — and its first coordinate, the combination of the scaled numbers, stays tiny at both scales. What could stop it being shortest at N/10 is a digit too few: if N was barely enough for the relation to win, N/10 may not be.

For a relation among the rounding it should fail. The rounding a double scaled to 25 digits leaves in its last nine digits is not the rounding it leaves in its last eight; the two lattices’ short vectors are unrelated, and a relation that makes one set of rounded digits cancel has no reason to make the other set cancel.

With five numbers, 58 of 128 runs return an exact relation. On 50 of them the two searches return the same vector — the filled dots, most of them between nine and eighteen digits — and on 8 they differ. The gap, as the earlier essay found, vouches for only 22 of the 58: most found relations among five numbers sit under a digit, in the band the accidents occupy.

The 70 runs that return something else divide sharply by precision. Past sixteen digits every one of them is a relation among the rounding, and on every one the two searches disagree. At fifteen digits or fewer a few are accidents of a different kind, and on three of those the two searches agree.

Turn the dial to six numbers and the contrast sharpens: 34 of 35 found relations are returned unchanged at both precisions, where the gap vouches for one. Turn it to three and both tests work — agreement on 92 of 96 found relations, the gap on 81.

The rounding is not shared #

The risk the relation essay named can be checked directly, and the answer is as clean as a measurement gets.

Pooled over every count and coefficient size, 561 runs scaled to eighteen digits or more returned something other than a relation, and the search a digit further in returned the same vector on none of them. At eighteen, twenty-one, twenty-five and thirty digits the two-precision test accepts nothing. The two scalings do not share enough of their rounding for the same spurious relation to win both lattices — which is what the arithmetic of rounding suggests, since the ninth-from-last digit of a double scaled by $10^{25}$ and by $10^{24}$ are different digits of different products, but it is the kind of suggestion that a measurement should confirm rather than a sentence claim.

Every accident the two-precision test does accept is at fifteen digits or fewer: 62 of them in all: 22 at six digits, 17 at nine, 10 at twelve and 13 at fifteen. The one-digit gap, on the same runs, accepts accidents almost nowhere — 13 in all, most of them with three numbers, where the gap has the most room and the occasional accident can stand out by a digit.

Accidents that are real #

The accidents the two precisions agree on are not failures of the comparison. They are the other edge of the window.

At six digits for five numbers, the digits the search is given are not enough to make the planted relation the shortest vector. The lattice’s shortest vector is then an approximate relation: a small integer combination of the numbers that vanishes to about the digits given, which exists by counting — among n numbers known to D digits there are always combinations with coefficients near $10^{D/(n-1)}$ that cancel that far. Such a vector is genuinely short in the lattice built from D digits, and in the lattice built from D − 1 digits it is still short, because it cancelled to D digits and so certainly cancels to D − 1. Dropping a digit cannot dislodge it. The comparison was designed to catch vectors that depend on digits that are not there; these depend only on digits that are.

Their signature is in the other test. The 62 agreeing accidents have gaps of at most 0.80 of a digit, because an approximate relation found by counting is roughly as short as the lattice’s other short vectors — that is what being found by counting means. And their coefficients run from 2 to about 270, which is why they multiply as the caller allows larger relations: with coefficients up to 3 the two-precision test accepts no accident at any count, with coefficients up to 30 it accepts 9, and with coefficients up to 300 it accepts 53.

So the two tests fail at opposite edges. The two-precision test cannot see an accident that is a real short vector of too few digits, and the gap can: those accidents do not stand out. The gap cannot see a relation among many numbers, whose budget is too small, and the two-precision test can: a relation stays the same relation. Neither edge is a defect in the test that misses it. Each test measures one property — stability, distinctness — and each edge of the window is where one property holds and the other does not.

Four ways to accept an answer #

With both quantities computed on every run, the natural rules are the two tests alone, either of them, and both.

With coefficients up to 30, requiring agreement vouches for 92 of 96, 68 of 72, 50 of 58 and 34 of 35 found relations among three to six numbers, and accepts 0, 1, 3 and 5 accidents. The gap vouches for 81, 54, 22 and 1, and accepts 3, 0, 0 and 0. Requiring either test adds almost nothing to agreement and brings in the gap’s three accidents among three numbers. Requiring both is the gap with its three accidents removed: 81, 54, 22 and 1 relations, no accidents.

Neither combination is the right one, because the gap’s threshold of a whole digit is the wrong threshold to pair with agreement. Agreement already excludes the rounding’s accidents; what is left for the gap to exclude are the stable accidents at few digits, whose gaps are under 0.8 of a digit but not near zero. A much weaker gap requirement — 0.3 of a digit, a factor of two between the shortest and next vector — alongside agreement keeps 90, 65, 47 and 32 of the found relations and accepts 0, 0, 2 and 0 accidents.

With coefficients up to 300 the picture is harder in the way the accident arithmetic predicts. Agreement vouches for 68, 43 and 14 found relations among three, four and five numbers, but accepts 8, 10, 12 and 23 accidents — with six numbers it accepts 23 accidents and finds the single relation not at all. The gap accepts almost nothing and vouches for 55, 22 and none. Agreement with a gap of 0.3 digits keeps 65, 36 and 9 relations and accepts 6, 5, 4 and 3 accidents: it cuts the stable accidents by between a quarter and seven-eighths without removing all of them. At this size, among six numbers from doubles, the search has too few digits for the planted relation to win at all, and no test on its output can supply what the digits did not.

The certificate the comparison replaces #

It is worth setting the six-number case beside the earlier essay’s own picture of it, because the two tests read the same runs.

Read by its gap, the six-number sweep is nearly uninformative: 35 found relations and 93 accidents, all but one of them under a digit, the two groups overlapping from a tenth of a digit to eight tenths. Read by agreement, the same 128 runs separate almost perfectly: 34 of the 35 relations come back unchanged a digit further in, and of the 93 accidents 5 do, all at fifteen digits or fewer. Nothing about the runs has changed between the two readings. What changed is the question asked of them — whether the answer stands out, which sixteen digits among six numbers cannot support, or whether the answer depends on its last digit, which they can.

That is also why the comparison is not simply a better gap. The gap measures a property of the lattice at one precision. The comparison measures a property of the answer across two, and a property of the answer is what the caller wanted to know; the lattice is only the means. A basis that describes its lattice badly made the same distinction for bases: the reduction’s guarantee is about the lattice, which never changes, and what a user needs is a statement about the particular basis it returns.

The modular methods met the same two edges #

The failure the two-precision test cannot catch has appeared in this collection before, in a different algorithm, and the comparison is worth making because the earlier essays drew a firm conclusion from it.

A prime that divides the answer found a modular elimination reporting a singular matrix and telling the truth: over the field with p elements the matrix is singular, over the rationals it is not, and nothing in the residue is small enough to be suspicious. A fraction recovered from one remainder found rational reconstruction returning a different fraction with the same residue whenever the modulus is too small — “a perfectly good one”. Both are the stable accident of this essay in another setting: a correct answer to a question slightly different from the one asked, which no rerun that preserves the difference will expose. An approximate relation that cancels to D digits is a correct answer to “which small combination vanishes to D digits”, and dropping a digit asks an easier version of the same question.

The response those essays arrived at was not to rerun until the answer settled. How many primes the answer needs fixed the number of primes in advance, from a theorem about how large a determinant can be, precisely because trying one more prime and stopping when the answer stops changing is a test that a wrong answer can pass. The relation search has the same two options. The two-precision comparison is the “until it settles” test, and it fails in exactly the way that essay warned: on answers that are stable because they are correct answers to an easier question. The room formula is the bound: $(n-1)(\log_{10}\|a\| + 1)$ digits before a relation of size ‖a‖ can stand out by a digit among n numbers, a count a caller can compute before the first reduction runs.

The difference from the modular case is that here the bound can be out of reach. With doubles the digits stop at sixteen whatever the arithmetic that consumes them, and for six numbers and coefficients near 30 the bound asks for more than that. In that regime the comparison is the only test left that still separates anything, and it separates well — as long as the answer is also required to use more digits than an accident of that size would need, which is the bound again, applied to the accidents instead of the relation.

What a search should hand back #

The earlier essay concluded that a relation search should return its gap beside the room the gap had. This one adds a second, independent number: whether the answer survives a digit less. The two cost different things. The gap is free — the second-shortest vector is computed on the way. The comparison costs a second reduction, which for these sizes is the cost of the first again.

Returned together they answer different questions, and the answers are only useful together. A relation that is stable and stands out is as well certified as this search can certify anything. A relation that is stable and does not stand out is either a relation among many numbers whose budget was small — the six-number case, trustworthy — or an approximate relation at too few digits, not trustworthy, and the caller can tell which by asking whether the digits used were enough for a relation of the size it wanted: $(n-1)(\log_{10}\|a\| + 1)$ digits for a one-digit gap, the earlier essay’s room formula run backward. A relation that stands out and is not stable is almost never seen: of all the found relations here, 44 disagreed across the two precisions — 25 of them at six and nine digits, where N had barely enough digits and a digit less had too few, and 13 at twenty-five and thirty, the rare relation found past the double’s digits and lost again a digit further in.

This is the same shape as a lesson the knob and the rounding drew about the reduction’s own arithmetic, from the other direction. There a single number the algorithm exposes — the Lovász parameter — turned out to decide little, and an unexposed detail of the arithmetic decided everything. Here the unexposed detail is the digits the inputs genuinely carry, and the two tests are two ways of asking the answer about it: the gap asks how much room those digits left, and the comparison asks whether the answer used any digit that was not there.

What this does not settle #

Planted relations among three to six numbers of sixty random digits, with coefficients up to 3, 30 and 300, rounded to doubles, sixteen runs at each of eight precisions. The comparison is always between N and N/10; a larger ratio — N and N/1000 — would dislodge more of the stable accidents at few digits, since an approximate relation to D digits need not survive losing three, and would lose more genuine relations at the lower edge of the window for the same reason. Where that trade settles is unmeasured.

The 0.3-digit gap is chosen after seeing the accidents’ gaps, and on these runs it is the largest threshold that keeps most relations among six numbers. It is a reading of this sweep, not a rule derived from anything, and a different family of numbers could move it.

Exact inputs are not compared here: with every digit real there is no rounding to depend on, the upper edge of the window disappears, and the two-precision test would be testing only the lower edge — where it is the weaker of the two.

Still open: the ratio between the two precisions, and a test that uses the room #

How far apart the two precisions should be. Agreement at N and N/10 excludes every relation among the rounding and some of the approximate relations at too few digits. Whether N and N/100 excludes the latter without losing too many of the genuine relations near the window’s lower edge is one more sweep, and it would turn the comparison’s single parameter into a stated choice.

A threshold on the gap that comes from the room. The gap an approximate relation at D digits can have is itself bounded — it is near zero by construction — while the gap a genuine relation has is its room less half a digit. A threshold set per run at a fraction of the room, rather than fixed at 0.3 of a digit, would ask each answer for the gap its own digits make possible, and whether that separates the stable accidents from the relations more cleanly than a single number does is the obvious next measurement.

The same comparison on a different family. Everything here uses numbers with no small relations of their own. The relation essay’s family has many, and there the search past sixteen digits returns a true relation shared by the numbers and their rounding. Whether such a shared relation is stable across a digit — it satisfies two conditions, and dropping a digit changes one of them — would say whether the comparison can tell an intended relation from an unintended true one, which neither test here was built to do.