The digits between the two searches

Two precisions guard the other edge added a second test to the lattice relation search. Scale the numbers to N digits and reduce; scale them to N/10 and reduce again; accept the shortest vector only if both reductions return it. A relation among the numbers returns unchanged, because its coefficients are the relation and its combination of the numbers is tiny at both scales. A relation among the rounding a double leaves in the last digits does not, because the two scalings do not share their rounding. Past sixteen digits the test accepted none of 561 such accidents. Below sixteen it accepted 62, and the essay explained them: at six to fifteen digits, too few for the planted relation to win, the lattice’s shortest vector is an approximate relation — a small combination of the numbers that cancels to about the digits given, which exists by counting — and “dropping a digit cannot dislodge it”, since a combination that cancels to D digits certainly cancels to D − 1.

That sentence is about whether the vector is still short. The test asks whether it is still the shortest. Those are different questions, and the same counting argument that guarantees the accident exists says the second is not safe for long: among n numbers known to D digits there are combinations with coefficients near $10^{D/(n-1)}$ that cancel to D digits, and with $D - k$ digits there are combinations a factor $10^{k/(n-1)}$ smaller that cancel to $D - k$. One digit is a factor of 1.58 for six numbers and 3.16 for three — an accident that happened to be that much shorter than typical survives it. Two digits is 2.5 to 10, three is 4 to 32. The essay’s own closing section predicted as much, and asked where the trade between those accidents and the genuine relations near the window’s lower edge would settle.

One, two and three digits apart #

The sweep is the previous essay’s: planted integer relations among three, four, five or six numbers of sixty random digits, with coefficients up to 3, 30 or 300, rounded to doubles and scaled to 6, 9, 12, 15, 18, 21, 25 and 30 digits, sixteen draws at each setting, reduced by LLL. A run’s answer is an exact relation if its first vector’s coefficients annihilate the numbers’ exact rational values — checked in integer arithmetic, since the numbers are rationals over a common denominator — and an accident otherwise. The one change is how far in the second search runs: a factor of 10, 100 or 1000 fewer in the scaling.

The previous essay’s picture is the starting point: at eighteen digits and more the two-precision test accepts nothing, and at six to fifteen it accepts 22, 17, 10 and 13.

Moving the second search further in trades exactly as the counting argument says it should. One digit apart the test keeps 711 of the 755 exact relations and accepts 62 of the 781 accidents. Two digits apart it keeps 652 and accepts 17. Three digits apart it keeps 602 and accepts 5. Each digit of separation removes nearly three quarters of the stable accidents, and costs about eight per cent of the relations. At no separation does it accept an accident past sixteen digits.

Where each side of the trade is paid #

Both sides of the trade are paid in the same place. With the second search one digit in, the accidents it accepts are all at six to fifteen digits, where the planted relation often cannot yet win. Turn the dial to two digits: those counts fall to 5, 5, 3 and 4. To three: 0, 3, 1 and 1. At eighteen digits and above there were none to remove.

The relations it stops keeping are in the same columns. At six digits the one-digit test keeps 77 of 86 relations found; two digits apart, 52; three apart, 33. At nine digits, 113, 99 and 86 of 129; at twelve, 157, 143 and 129 of 160; at fifteen, 172, 166 and 160 of 173. From eighteen digits on the three tests keep the same relations to within one or two: 137 of 139 at eighteen at every separation.

The losses are the lower edge of the window, and the reason is the relations’ own. A relation among n numbers with coefficients of size $\|a\|$ needs about $(n-1)\log_{10}\|a\|$ digits to be the shortest vector, plus whatever margin separates it from the approximate relations. A run at six digits with coefficients up to 300 among four numbers has barely that; the second search two or three digits in has two or three fewer, and there the relation is no longer the shortest vector at all — the second search returns an approximate relation instead, and the acceptance check discards the first search’s correct answer. The previous essay recorded this effect one digit apart as 25 of its 44 disagreements at six and nine digits. Three digits apart it is 153 disagreements, 140 of them at fifteen digits or fewer.

Why one digit left the accidents in place #

The counting argument puts a number on how much shorter than typical an accident must be to survive. A random approximate relation at D digits among n numbers has coefficients near $10^{D/(n-1)}$; the one returned is the shortest of many, so it is somewhat shorter than that, and when the digits drop by k the typical size drops by $10^{k/(n-1)}$. The returned accident survives if its own shortness beats that drop.

With more numbers the drop per digit is smaller — a factor of 1.58 with six numbers against 3.16 with three — and more accidents survive a single digit: 8 of 115 with three numbers, 11 of 172 with four, 15 of 223 with five, 28 of 271 with six. Two digits apart those are 2, 2, 6 and 7; three apart, 1, 1, 1 and 2. The six-number accidents, which the one-digit test found hardest to remove, are removed by the wider test at the same rate as the others. The previous essay’s sentence was right about the vector and wrong about its rank: an accident at D digits does cancel to D − 1, and so do shorter combinations the lattice at D − 1 digits contains, and one of them takes its place.

The five that survive three digits #

Three digits apart, five accidents are still accepted, and they can be read one by one. All five come from the largest coefficient bound, 300. Two are among six numbers, at nine and fifteen digits; one each among three, four and five numbers, at nine, twelve and nine. Their largest coefficients run from about four to about eighty-five — and their gaps to the next vector are 0.36 to 0.56 of a digit, the same small gaps the one-digit test’s accidents had.

What sets them apart is how far each sits below the counting bound. The bound says an approximate relation among n numbers at D digits needs coefficients near $10^{D/(n-1)}$; each of the five has coefficients shorter than that by between 1.0 and 2.9 digits. The counting argument above says an accident survives k dropped digits only if it is at least $k/(n-1)$ digits shorter than typical, which for three digits is 1.5 digits among three numbers, 1.0 among four, 0.75 among five and 0.6 among six. Every one of the five clears its own threshold: 2.9 against 1.5, 2.1 against 1.0, 1.7 against 0.75, and 1.0 and 1.2 against 0.6. The survivors are the accidents that were unusually short to begin with — short enough that the lattice three digits in has nothing shorter to offer.

That turns the separation into a statement a caller can use. A test k digits apart accepts only the accidents that are at least $k/(n-1)$ digits shorter than the counting bound predicts, and an accident that short is rare in proportion. The residual risk after three digits apart is five runs in 781, each a relation among the numbers that holds to its digits, is exceptionally short for its precision, and would be found by a search at a few digits more.

What the separation should be #

Stated as the share of accepted answers that are accidents, below sixteen digits: one digit apart, 62 of 581 accepted, or 10.7 per cent; two digits, 17 of 477, 3.6 per cent; three digits, 5 of 413, 1.2 per cent. Above sixteen digits it is zero at every separation, and every separation keeps the same relations there. So the choice is a choice about the lower half of the window only, and the two currencies are explicit: each digit of separation divides the false acceptances there by three or four and gives up about one relation in nine.

A caller who knows what the search is for can choose. A search whose answer is going to be proved afterwards — whose relation will be checked exactly, as every relation here is — loses nothing by a false acceptance except the check, and should keep the one-digit test’s relations. A search whose answer is going to be used without a check, where an accident is a wrong result, should use three digits apart and pay the relations. And a search at eighteen digits or more should use one digit apart, because nothing wider buys anything there; the double’s rounding is not shared by any two scalings, and the approximate relations the counting argument supplies are all longer than the planted one by then.

This is the reading the room a relation has to stand out could not supply for many numbers, where the planted relation’s gap is too small to stand out, and the reason the two-precision test was added. Widening it keeps that advantage: with six numbers, three digits apart keeps 80 of 113 relations found and accepts 2 of 271 accidents, where the one-digit gap vouches for almost none of the relations.

Two tests, and what a certificate would add #

Neither test proves anything. The two-precision comparison and the gap are both statistics of one lattice reduction’s output, and every relation this sweep scores as found was confirmed separately — in integer arithmetic, by checking that its coefficients annihilate the numbers’ exact rational values. That check is available here because the numbers were built as rationals. For numbers known only to finitely many digits it is not: the most a caller can do is ask how the answer behaves as the digits change, which is what the second search does, and how much it stands out from its neighbours, which is what the gap does.

The collection’s certificates elsewhere have a different shape. Proving the answer is in the box encloses a solution rigorously, with interval arithmetic that carries its rounding along, and a bound that is proved set such an enclosure beside the estimates it replaces; its guarantee is about an answer that exists, not about whether a candidate is the answer. A relation search’s version would be a bound, from the digits given, on the height of any relation the search could have missed — which LLL’s reduction guarantees supply, as a factor exponential in the dimension times the shortest vector’s length. A basis that describes its lattice badly measured how far LLL’s output sits from the best basis; that factor is the price of turning either test into a certificate, and at six numbers it is large enough that the statistical tests are the practical ones.

So the separation between the two searches is a statistical choice with statistical currencies: false acceptances divided by three or four per digit, relations lost at about one in nine per digit, both confined to the low-precision half of the window. What it cannot do is replace a check a caller is able to make. Where the exact check is available, the one-digit test is enough, because its false acceptances are cheap to catch; where it is not, three digits apart is the setting whose false acceptances are all exceptionally short accidents at precisions a little more work would lift the search out of.

Why a second reduction is the price #

The comparison costs one more reduction, and at these sizes that is the cost of the first again whatever the separation. A wider separation is cheaper, if anything: the second lattice is scaled by a smaller number, so its integers are shorter and LLL’s arithmetic on them is lighter. A relation among digits that were not there showed the search inventing relations out of digits the numbers do not have, which is what the scaling’s size controls; a second search three digits in carries about seven fewer bits in its first column than one a digit in. So the separation is a free parameter in cost and a real one only in the trade above — which is the situation in which a stated choice, rather than the first value tried, is owed.

The knob and the rounding found the reduction’s own Lovász parameter deciding little and an unexposed detail of the arithmetic deciding a great deal. The separation between the two searches is the opposite case: an exposed parameter, left at its first value because nothing measured the alternative, that moves the false acceptances by a factor of twelve.

Sixty random digits, where the planted relation is the only small one #

The same family as before — numbers with sixty random digits, so the planted relation is the only small one — and sixteen draws at each setting. The relation essay’s narrow family, whose numbers have many small relations of their own, is not run here; there a search past sixteen digits can return a true relation the numbers and their rounding share, and whether a wider separation tells an intended relation from an unintended true one is a different question.

The reductions are exact integer LLL at the classical Lovász parameter; rounding a coordinate in the wrong basis showed how much a reduced basis’s quality matters to what is read off it, and a weaker reduction — a smaller parameter, or a floating-point LLL — would move the accidents’ shortness and with it which of them survive. The counting argument explains the direction and rough size of every trend and does not predict the counts; a relation’s margin over the approximate relations depends on its coefficients and on the numbers, and neither is controlled here beyond their size.

Still open: a separation that reads the room, and a shared relation #

A separation set by the room. The previous essay’s room formula says how many digits a relation of a given size needs among n numbers. A test that set the second search’s precision to just above that — as far in as a relation of the requested size could still be the shortest vector — would take the most accidents out and lose no relations of that size. The prediction with a sign is that it accepts fewer accidents than three digits apart and keeps more relations than one digit apart, because it spends the separation only where the relation has digits to spare.

A threshold on the gap that comes from the room. The other proposal the previous essay left: a gap threshold set per run at a fraction of the room, rather than fixed. Combined with the two-precision test at a separation of two or three digits, it would be tested on the accidents that survive both — five to seventeen of them here — which is a small enough set to read one by one.

The same comparison on a family with relations of its own. Where the numbers share a true relation with their rounding, dropping digits changes whether the rounding still satisfies it. Whether a wide separation removes such shared relations as well as it removes approximate ones is the case this test was never built for, and the one a caller searching among constants with known relations would meet first.