One lattice, two bases: an orthogonality defect of 7.071 reduced to 1
At its defaults it draws one lattice, two bases: an orthogonality defect of 7.071 reduced to 1. The dots are the lattice generated by (1, 0) and (7, 1) — every one of them, out to ±4 in each coefficient. The long pair of arrows is that basis; the short pair is what LLL returns after 1 steps, in exact rational arithmetic with δ = 3/4. The two bases generate the same set of points, which is checked rather than drawn: the lattice determinant is 1 before and 1 after, and every step of the reduction is a unimodular operation, which is what makes that so. What the reduction changes is the orthogonality defect — the product of the basis vectors' lengths over the determinant — from 7.0711 to 1. One is the floor, and it is attained only by an orthogonal basis.
lattice-basis is one function in lib/figures/integer.js —
exact arithmetic — no residual to print, and a cost measured in the length of the numbers. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
The dots are the lattice generated by (1, 0) and (7, 1) — every one of them, out to ±4 in each coefficient. The long pair of arrows is that basis; the short pair is what LLL returns after 1 steps, in exact rational arithmetic with δ = 3/4. The two bases generate the same set of points, which is checked rather than drawn: the lattice determinant is 1 before and 1 after, and every step of the reduction is a unimodular operation, which is what makes that so. What the reduction changes is the orthogonality defect — the product of the basis vectors' lengths over the determinant — from 7.0711 to 1. One is the floor, and it is attained only by an orthogonal basis.
skew: 7
The arguments are the ones A basis that describes its lattice badly passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The dots are the lattice generated by (1, 0) and (7, 1) — every one of them, out to ±4 in each coefficient. The long pair of arrows is that basis; the short pair is what LLL returns after 1 steps, in exact rational arithmetic with δ = 3/4. The two bases generate the same set of points, which is checked rather than drawn: the lattice determinant is 1 before and 1 after, and every step of the reduction is a unimodular operation, which is what makes that so. What the reduction changes is the orthogonality defect — the product of the basis vectors' lengths over the determinant — from 7.0711 to 1. One is the floor, and it is attained only by an orthogonal basis.
skew: 40
The arguments are the ones A basis that describes its lattice badly passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The dots are the lattice generated by (1, 0) and (40, 1) — every one of them, out to ±4 in each coefficient. The long pair of arrows is that basis; the short pair is what LLL returns after 1 steps, in exact rational arithmetic with δ = 3/4. The two bases generate the same set of points, which is checked rather than drawn: the lattice determinant is 1 before and 1 after, and every step of the reduction is a unimodular operation, which is what makes that so. What the reduction changes is the orthogonality defect — the product of the basis vectors' lengths over the determinant — from 40.012 to 1. One is the floor, and it is attained only by an orthogonal basis.
skew: 2
The arguments are the ones A basis that describes its lattice badly passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The dots are the lattice generated by (1, 0) and (2, 1) — every one of them, out to ±4 in each coefficient. The long pair of arrows is that basis; the short pair is what LLL returns after 1 steps, in exact rational arithmetic with δ = 3/4. The two bases generate the same set of points, which is checked rather than drawn: the lattice determinant is 1 before and 1 after, and every step of the reduction is a unimodular operation, which is what makes that so. What the reduction changes is the orthogonality defect — the product of the basis vectors' lengths over the determinant — from 2.2361 to 1. One is the floor, and it is attained only by an orthogonal basis.
show: "relation", C: 30
The arguments are the ones A relation among digits that were not there passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A relation with integer coefficients up to 30 is planted among 4 numbers, the numbers are scaled to the number of decimal digits on the horizontal axis and handed to a lattice reduction, and the curve is the share of eight trials in which the reduced basis contains the planted coefficients. When the numbers are exact rationals and the scaling is done in integers, the curve rises and stays up: 100 per cent at 40 digits. When the same numbers are rounded to doubles first — which is what a measured quantity is — the curve rises and then comes back down, to 13 per cent, because past the sixteenth digit the scaling is multiplying rounding noise and the lattice finds relations among the noise instead.
show: "relation", C: 300
The arguments are the ones A relation among digits that were not there passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A relation with integer coefficients up to 300 is planted among 4 numbers, the numbers are scaled to the number of decimal digits on the horizontal axis and handed to a lattice reduction, and the curve is the share of eight trials in which the reduced basis contains the planted coefficients. When the numbers are exact rationals and the scaling is done in integers, the curve rises and stays up: 75 per cent at 40 digits. When the same numbers are rounded to doubles first — which is what a measured quantity is — the curve rises and then comes back down, to 0 per cent, because past the sixteenth digit the scaling is multiplying rounding noise and the lattice finds relations among the noise instead.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
80 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
the exact reduction returns an orthogonal basis at 2^40 — checked 10 times
the lattice determinant is unchanged at 2^40, whatever decided the steps — checked 10 times
reducing the basis first is never worse at skew 2 — checked 5 times
this lattice does have an orthogonal basis, and the reduction finds it at skew 2 — checked 5 times
a coefficient size the gap is measured at
a coefficient size the rules are scored at
a coefficient size the searches are compared at
a coefficient size the sweep is drawn at
a dimension the enumeration can afford
a dimension the sweep is drawn at
a family of numbers to plant a relation among
a larger delta never costs fewer steps
a number of quantities the gap is measured for
a number of quantities the reduction can handle
a number of quantities the two searches are compared for
a ratio between the two precisions the sweep draws
a ratio the precision sweep draws
a reading of the lattice this generator draws
an accident rarely clears one digit anywhere
an exponent the sweep is drawn to
an LLL-reduced basis is integral
and a reduced basis is not a guarantee: rounding in it misses the nearest point somewhere
and at and above it the float one returns a basis it would itself refuse
and does not make the basis worse
and in the plane the orthogonality defect predicts how far, to within a factor of two
and nothing beats the nearest point
and the basis it comes back with is the skew minus as much of it as a double could hold
and the basis that comes back barely moves
and the defect, a product of three lengths here, over-predicts it by an order of magnitude
and too little precision does not
below 2^53 the two arithmetics return the same basis
enough lattices to say anything
enough precision recovers the relation when the digits are real
enough settings to compare
every Bareiss division is exact
every setting produced lattices
how badly skewed the starting basis is
LLL does not change the lattice determinant
LLL terminates on this basis
no accident past sixteen digits agrees across the two precisions
no accident past sixteen digits is accepted by the two precisions
no accident's gap reaches three digits
past sixteen digits the narrow family's answers are exact and the wide family's are not
rounding in a badly skewed basis lands far from the nearest point
the assertion refuses a counterexample
the gap sits a little under the room it has
the guarantee more than doubles in strength across the sweep
the reduction never makes a basis worse
which is checkable: the returned basis fails the algorithm's own condition
which is far enough that it is almost never the nearest point
while asking a double for more digits than it has loses the relation it had already found
while being markedly better in the median
while the proved bound improves at every setting
while the work does not fall
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A basis that describes its lattice badly
The same set of points has infinitely many bases, they are all correct, and they are not equally useful. One measurement separates them — the product of the vectors' lengths over the lattice determinant — and the determinant is the invariant the reduction may not change, which is what makes the reduction checkable.
Exact arithmetic, and what it costs insteadA relation among digits that were not there
A lattice finds the exact integer combination of several numbers that vanishes, and it needs enough digits of them to do it. Give it more digits than the numbers have and it finds a relation anyway — among the rounding, with the same confidence and no warning. Recovery runs 8 of 8 at twelve digits and 1 of 8 at forty.
Exact arithmetic, and what it costs insteadRounding a coordinate in the wrong basis
The nearest lattice point is found by writing the target in the basis and rounding each coordinate, which is three lines of arithmetic and is wrong. On a basis skewed by forty it lands a mean of 26 times too far and a worst of 40.02 — the basis's own orthogonality defect, to three figures — and the identical three lines on the reduced basis are exact at every target.
Exact arithmetic, and what it costs insteadThe digits between the two searches
A lattice relation search run at N digits and again at N/10 never agrees with itself on a relation among the rounding, but it does agree on 62 approximate relations at fifteen digits or fewer — accidents that really are the shortest vector there, and that dropping a digit was said to be unable to dislodge, since a combination that cancels to D digits cancels to D − 1. It cancels, but it stops being the shortest. Two digits apart the accepted accidents fall to 17 and three digits apart to 5, while the relations kept fall from 711 of 755 to 652 and 602 — every one of the losses at fifteen digits or fewer. Past a double's sixteen digits the separation costs nothing and buys nothing.
Exact arithmetic, and what it costs insteadThe knob and the rounding
The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect. The one rounding nobody writes down decides everything: above 2⁵³ the reduction returns a basis 12,345 times worse than it should, with the determinant invariant equal to one throughout.
Exact arithmetic, and what it costs insteadThe room a relation has to stand out
A lattice search for an integer relation returns its shortest vector, and the proposal was to return the gap to the next one as well, so a caller could tell a relation from an accident. Measured, the gap is a certificate with a budget: the digits the numbers really have, shared among all but one of them, less the size of the relation. A found relation's gap sits half a digit under that budget, accidents stay near zero, and a one-digit gap vouches for 81 of 96 relations among three numbers and for 1 of 35 among six. The test numbers the proposal came from turned out to have relations of their own.
Exact arithmetic, and what it costs insteadTwo precisions guard the other edge
Run a lattice relation search at N digits and again at N/10, and accept its answer only if both runs return the same vector. Among six measured numbers, where the gap between the shortest and next vector vouches for one found relation in 35, the two runs agree on 34. Past a double's sixteen digits they never once agree on an accident, 0 of 561. They do agree on 62 accidents at fifteen digits or fewer — approximate relations that really are the shortest vector there — and the gap, which cannot see a relation among six numbers, can see those.