The room a relation has to stand out

A relation among digits that were not there found the integer combination of several numbers that vanishes by building a lattice from them and reducing it, and found the method working inside a window. With too few digits the planted relation is not the shortest vector in the lattice and the reduction returns something else. With more digits than the numbers have — doubles scaled past their sixteenth digit — it returns something else again, and says nothing different about it. It ended on a proposal that looked cheap. The reduction computes the second-shortest vector along with the shortest and throws it away. Return the ratio of their lengths, and a caller could tell a relation from an accident without running the search again at higher precision: on the recovered runs the ratio was several orders of magnitude, on the collapsed ones it was not. What threshold to compare it against, as a function of how many numbers there are and how large the relation’s coefficients are, was left open.

Measuring that turned up something about the test first, and it changes what “accident” means.

What the returned vector is #

A relation is a claim anyone can check, if the numbers are known exactly — the property an answer with no error in it priced for linear systems. The planted numbers here are exact rationals, so the vector a reduction returns can be multiplied out in integers and tested: either its coefficients combine the numbers to exactly zero, or they do not. The relation essay recorded whether the returned vector was the planted relation. It did not record whether it was a relation at all.

On the relation essay’s own family the answer is unexpected. Its numbers are two numerators of about a million over one denominator of about a million, and a third fixed by the planted relation. Scaled from doubles to 30 digits, the reduction returns the planted relation on none of sixteen runs — the collapse the essay reported, which on this family begins at 21 digits, where half the runs still find it — and an exact relation among the numbers on all sixteen. The vector is not a relation among the rounding. It is a true relation, with coefficients near $10^5$.

The reason is arithmetic about the family rather than about lattices. Three integers of about a million satisfy an integer relation with coefficients near a thousand — any three do, by counting — so three rationals over one such denominator have exact relations of their own that nobody planted. Handed doubles and more digits than the doubles hold, the reduction looks for the vector that makes the scaled, rounded numbers vanish, and among the numbers’ own relations there is one that the rounding errors happen to satisfy too: in three dimensions two linear conditions leave a line, and the shortest integer vector on it is short enough to win. The planted relation, with coefficients up to 30, leaves a residual of the rounding times $10^{30}$ and loses.

So the relation essay’s collapse is real — the planted relation is lost past the double’s digits — and its account of what comes back instead needs a qualification: on that family, what comes back is correct and uninformative. To ask whether a gap can tell a relation from an accident, the numbers must have no small relations of their own. Every measurement below uses numbers of sixty random digits, for which the only small relation is the planted one. On that family the vector returned past sixteen digits is exact on none of 32 runs at 25 and 30 digits — it genuinely is a relation among the rounding, as the essay said.

The gap has a budget #

A reduced basis of an n-dimensional lattice built from numbers scaled to D digits has, for a generic lattice, vectors of length around $10^{D/(n-1)}$: the digits are shared among the coordinates, and that is the length at which integer combinations of D-digit numbers start to cancel by accident. A planted relation with coefficient vector a has length about ‖a‖ — reduction’s short vectors are what made rounding a coordinate in the wrong basis go right or wrong. If it is the shortest vector, the next is a generic one, and the gap between them — in digits — has room of about $D/(n-1) - \log_{10}\|a\|$. With doubles, D is capped at the sixteen digits a double holds, however many are asked for.

With four numbers and coefficients up to 30 the found relations climb with the dashed line, from under a digit at six digits of scaling to three at fifteen, and every one sits under it. Past the double’s sixteen digits the line goes flat and the found relations fall away from it — at eighteen digits the last two scaled digits are rounding, and the gap shrinks before the relation is lost — and from twenty-one digits on nearly every run returns something that is not a relation at all. Those accidents sit in a band under one digit. Of 72 runs that found a relation, 54 have a gap of a digit or more; of 56 that did not, none do.

Turn the dial up to six numbers and the picture is the same shape at a smaller scale. The room at sixteen digits is 1.63 digits instead of 3.84, the found relations barely leave the band the accidents occupy, and one of 35 found relations has a gap of a digit. Turn it down to three and the room is over six digits; the found relations are far above the accidents.

Across every setting with at least four found relations at precisions a double can supply — fifteen digits or fewer — the median gap sits a little under the room: by 0.3 to 1.4 digits, the shortfall growing with the coefficient size, because a larger planted relation competes with more nearby lattice vectors. Past sixteen digits the formula stops describing the lattice at all. The integers the reduction is handed then end in digits that are rounding, which eats the gap from below, and the lattice’s generic vectors are set by the digits asked for rather than the sixteen that were real, which can push it above; the figure leaves those precisions out because the room computed for them is not the room the lattice has. The room is therefore not a bound somebody proved; it is a measurement, and the gap a relation will show can be computed before the search is run, from the number of numbers, the digits they carry and the size of relation the caller is looking for.

A one-digit gap, as a certificate #

A certificate needs two properties: accidents must rarely pass it, and relations must usually pass it. The one-digit gap — the second-shortest vector ten times longer than the shortest — has the first property almost everywhere measured and the second only in part of the range.

Accidents clear a digit on at most four runs in any setting — 3 of 28 with three numbers and coefficients up to 3, and none at all in eight of the twelve settings. Found relations clear it on 99 of 100 runs with three numbers and coefficients up to 3, 81 of 96 with coefficients up to 30, and 55 of 73 up to 300. With four numbers the figures are 85 of 94, 54 of 72 and 22 of 46; with five, 65 of 85, 22 of 58 and none of 18; with six, 38 of 77, 1 of 35, and none.

That is the threshold the relation essay asked for, and it is a function of the count and the coefficient size in the way it guessed. With sixteen digits to share, a relation among n numbers with coefficients of size ‖a‖ has a gap of about $16/(n-1) - \log_{10}\|a\|$ digits less half a digit, and a one-digit certificate can vouch for it only while that exceeds one. For three numbers that allows coefficients up to about $10^{6.5}$; for four, $10^{3.8}$; for five, $10^{2.5}$; for six, about fifty. Past that the search may still find the relation, and the gap cannot say so.

Six numbers, twice #

The dial’s last stop is worth a picture of its own, because it is where the certificate stops working and it is easy to read the wrong reason into that.

With six numbers from doubles, 35 runs of 128 return an exact relation — the search does find it, from twelve to eighteen digits of scaling — and their gaps sit between a fifth and one and a half digits, most of them under one. The 93 runs that return something else have gaps under a digit too. The two groups overlap almost entirely, and one found relation in 35 clears the threshold. Read quickly, this says the gap is useless for six numbers. It says something narrower: sixteen digits shared among five coordinates leaves about three digits for a generic vector’s length, a relation with coefficients near 30 uses one and a half of them, and there is almost nothing left for the relation to stand out by.

Hold the same numbers exactly and scale them in integers, and the room has no ceiling. The found relations climb along the dashed line at a fifth of a digit per digit — one divided by the five coordinates the digits are shared among — from under half a digit at fifteen digits to one at about eighteen, two at twenty-one, four at thirty and six at forty. Of 160 runs over ten precisions, 129 find the planted relation and 95 of those have a gap of a digit or more; every run from twenty-one digits on is both found and vouched for. The 31 runs that return something else are all at twelve digits or fewer, where the relation is not yet the shortest vector, and none of them has a gap as large as a digit.

So the certificate works for six numbers, given the digits. What failed with doubles was the digits: a search among six measured quantities has sixteen digits to share and cannot buy more. The room formula says how many it would need — $(n-1)(1 + \log_{10}\|a\| + \tfrac12)$ for a one-digit gap on a relation of size ‖a‖, about 18 for six numbers and coefficients near 30 — and the exact sweep puts the crossing at eighteen to twenty-one.

What a search should hand back #

The gap is worth returning, and it is worth returning beside the number it should be compared with: the room. A gap of three digits on a search whose room was four is a strong result; a gap of three digits where the room was nine is a relation much larger than the caller hoped for, or not the relation at all. Neither is visible from the gap alone. The room needs one number from the caller — how large a relation it is looking for — and the digits the numbers genuinely carry, which only the caller knows.

Worked through at fifteen digits from doubles, for a relation with coefficients up to 30, the reading is concrete. With three numbers the room is 6.04 digits and the sixteen runs return gaps from 4.64 to a median of 5.17: a caller who sees a gap of five digits against a room of six has as clear a result as this search can give. With four numbers the room is 3.45 and the gaps run from 1.76 to a median of 2.84 — still well clear of the accidents, which stay under a digit. With five the room is 2.18, the median gap 1.40 and the smallest 0.84: a returned gap of one digit is then neither good nor bad, because it is roughly what a found relation shows and roughly the most an accident shows. With six the room is 1.39 and the median gap 0.64, and nothing the gap says can be relied on.

The room turns those four lines into one statement a caller can act on before running anything: the gap a found relation will show, less about half a digit. Where that is below one digit, the search’s own output cannot distinguish its result from an accident, and the caller should either supply more digits or check the returned relation some other way — which is where the two-precision comparison below comes in. Where it is well above, a small gap on the day is itself the warning: it means the relation found is larger than the one the caller described, or not the one that was there.

That last point is the same one the knob and the rounding made about the reduction itself: what decides the answer is often not the parameter the algorithm exposes but a property of the arithmetic the inputs went through. A search told “these are doubles” can cap D at sixteen; a search told “these are exact” can use every digit it is given; a search told nothing will compute a room from the digits it was handed and overstate it.

The numbers that were not what they seemed #

The narrow family deserves one more sentence, because the mistake it caused is general. A test of whether a search can find a planted relation is only a test if the numbers have no other relations of comparable size, and rationals with modest denominators always do — the same counting that lets a fraction be recovered from one remainder, since small numerator and denominator pairs are rare among all residues and common among all relations. A basis that describes its lattice badly built its lattices from integers, where every vector is exact and the question never arises; the relation search is the first place in these essays where the input’s own arithmetic structure is part of the answer. The fix — sixty random digits a number — is cheap, and the qualification it adds to the relation essay is narrow: the collapse is real on both families; what comes back is a false relation on one and a true, unwanted one on the other.

What this does not settle #

Planted relations with coefficients drawn uniformly up to 3, 30 and 300, among three to six numbers, sixteen runs at each of eight precisions, from doubles. The shortfall of the gap under its room grows with the coefficient size and is measured here, not derived, and the one-digit threshold is a choice — two digits would vouch for fewer accidents and fewer relations, and the table would move accordingly.

The room assumes the second-shortest vector is generic. When the numbers have a second relation of their own, as the narrow family does, the second-shortest vector is that relation and the gap measures the ratio of two relations, not a relation’s distinctness — and a caller cannot tell those apart from the gap either.

Exact inputs are drawn only for six numbers and one coefficient size. The climb there is the room formula’s, and the relation essay’s exact-input sweep showed the recovery itself holding to forty digits at every count it tried; whether the shortfall under the room stays at half a digit for larger coefficients with exact inputs is not measured.

Still open: the same relation at two precisions, and a room for exact inputs #

Two scalings. The relation essay’s other proposal — run the search at N and at N/10 and compare — asks a different question from the gap: not whether the vector stands out, but whether it is the same vector when the digits change. An accident among the rounding should change with the last digit and a relation among the numbers should not. Whether that comparison catches the accidents the gap misses — among five and six numbers, where the room is too small for a gap to mean anything — is the direct test, and it needs no statement from the caller about the inputs.

The room when the digits are real. For exact inputs the room is $D/(n-1) - \log_{10}\|a\|$ with no cap, and a caller choosing how many digits to compute — the decision how many primes the answer needs makes for a determinant — could choose D to buy a stated room: two digits of gap for a relation of size ‖a‖ among n numbers needs $(n-1)(2 + \log_{10}\|a\|)$ digits. Whether the shortfall stays at half a digit when D is chosen that way, rather than swept, is one more measurement.