A solution over the rationals can be computed modulo a prime power and then recovered — the residue determines the fraction uniquely, but only once the modulus is twice the square of the fraction's longer part. Below that there is no partial credit: the algorithm returns a different fraction with the same residue, and it is a perfectly good one.
The Chinese remainder theorem reconstructs an integer from its residues. A determinant is an
integer, so the modular route finishes there. A solution vector is not: every entry is a ratio of two
determinants, and the reconstruction has one more step in it.
That step is remarkable and it is not obvious it should be possible at all. Given a single residue
u = n/d modulo m — one integer — recover n and d. There are m fractions with that residue and the
claim is that exactly one of them is small enough to be the answer.
Fig. 1 Recovering 355/113 from its residue modulo a prime just above 2ᵉ, for e from 3 to 44. Below 2¹⁸ the
reconstruction returns something else; at and above it, 355/113 exactly, every time.
There is a second surprise in it, which is that the same trick has been in use for two thousand years
under a different description. A continued-fraction expansion of a real number produces the best
rational approximations to it with bounded denominators, and it is computed by the Euclidean
algorithm; recovering n/d from its residue is that expansion run on a pair of integers instead of on
a real, stopped by a size condition instead of by an accuracy one. The convergents of π are the
canonical example and 355/113 is the third of them, which is why it is the fraction the figure
recovers.
Run the extended Euclidean algorithm on (m, u) and stop it early — the first time the remainder falls
below √(m/2). At that point the remainder is the numerator and the accumulated coefficient is the
denominator, up to sign.
That is the whole method. It is the same sequence of divisions that computes a greatest common
divisor, run on a pair it will not be allowed to finish, and its intermediate state is a sequence of
pairs (rᵢ, tᵢ) with rᵢ ≡ tᵢ·u (mod m) at every step. The stopping rule chooses which of those pairs to
return.
Two things about that are worth noticing.
The cost is a gcd, which the field has already priced.The first essay in this
field measured the price of reducing fractions during an
elimination and found it to be a gcd per operation. Here the same routine appears once per entry of
the answer rather than once per arithmetic operation, which is n² times less often, and it is the
reason the modular route reaches an exact solution without ever forming a fraction in the middle.
And it needs no search. There are m candidate fractions and the algorithm looks at about log m of
them, because the Euclidean sequence’s remainders fall geometrically. That is not a heuristic that
usually works: the pairs it skips are provably too large, so the one it stops at is the only one it
could return.
The implementation has one place where it can quietly do the wrong thing, and it is the return value
on failure. When no pair meets the size condition — because the modulus was too small for this
fraction — there is still a pair to return, and returning it is the natural thing for the code to do.
The routine here returns nothing instead, and says so, because a reconstruction that cannot say the
modulus was too small converts a recoverable failure into a silent one. That is the same discipline
the interval-arithmetic essays apply to a verdict of
nothing can be said: it is an outcome, it is useful, and a routine that has no way to express it
will express something else.
The uniqueness is a statement about a lattice, and it is short.
The set of integer pairs (a, b) with a ≡ b·u (mod m) is a lattice in the plane — closed under
addition and integer multiples — and its determinant is m. The answer (n, d) is one of its points.
Any other point (n′, d′) with the same residue is also in it, and if both are shorter than √(m/2) in
each coordinate then the parallelogram they span has area at most 2·(m/2) = m, with equality only in
degenerate cases; a lattice of determinant m has no two independent points spanning less than that.
So the short point is unique, and finding it is finding the short vector in a two-dimensional
lattice — which is what the Euclidean algorithm does.
That is the same object the lattice essay in this field
is about, in the smallest dimension where it has anything to say. Reconstruction is
lattice reduction in two dimensions, and in two dimensions the reduction is exact, terminating, and
older than the problem it is being used on.
The bound is about the larger part, and that is the mistake to avoid #
The natural way to write the bound down is wrong, and the measurement is what said so.
Since there are about m fractions and the answer has parts n and d, the tempting statement is that
the modulus must exceed 2·|n|·d — the product. It reads well and it is false. The condition the
algorithm actually needs is that both parts fall below √(m/2) separately, which requires
m > 2·max(|n|, d)²
and those two are different whenever the parts are of different sizes. For 355/113 the product bound
predicts a crossover at 2¹², and the measured first success is 2¹⁸ — six bits out, in the direction
that would have made a routine budget too little modulus and return the wrong fraction with no
warning.
Fig. 2 355/7, whose product is fifty times smaller and whose crossover is in exactly the same place. The
bound does not know about the denominator until the denominator is the larger part.
The drag range makes the correction visible in one motion: the cliff does not move at all while the
denominator is below the numerator, and then moves two bits for every bit the denominator gains. A
bound proportional to the product would have moved throughout.
The failure below the bound is the thing this essay is really about, and it is unlike every other
failure on this site.
Below the crossover the algorithm does not return an approximation of 355/113. It returns a different
fraction — a genuinely correct one, in the sense that its residue modulo m is the same u, and one
with smaller parts. There is no sense in which it is nearly right. 355/113 and the fraction returned
at 2¹² are not close, they are not related, and no measurement of the returned value would suggest
anything was wrong.
Compare that with every truncation elsewhere on this site. A truncated
model is wrong by an amount the discarded singular
values bound. A restarted Krylov method loses accuracy in a way
its own residual estimate tracks. Even a rank chosen at the wrong
threshold is wrong by one, and the singular value it crossed says by
how much. All of those degrade.
This does not degrade, it substitutes — which puts it in the small class of failures the graph field
opened with, where a rounding does not make an answer slightly wrong but makes it a different answer.
The only defence is arithmetic: know how large the parts can be, and supply a modulus twice the
square of that.
The figure sweeps a fraction against forty-two moduli and records, for each, whether the
reconstruction returned that fraction. It is a binary outcome per modulus, which makes the picture a
pair of blocks rather than a curve — and the sharpness of the boundary between them is the finding.
Between 2³ and 2¹⁷ inclusive, every modulus fails. At 2¹⁸ and every modulus above it, up to 2⁴⁴, the
reconstruction is exact. There is no modulus at which it sometimes works, none at which it returns a
fraction close to the answer, and none at which the failure is marginal. The assertion in the figure
checks that the first success is where the lattice bound puts it, within two bits, and it is: 2¹⁸
against a bound of 2¹⁷·⁹.
That is a stronger claim than the algorithm works when the modulus is large enough and it is worth
the extra apparatus, because the weaker claim is compatible with a routine that is unreliable near
the boundary — which is what a reader would reasonably assume, since almost everything else here is.
Which is answerable, and by the same theorem that budgeted the primes.
By Cramer’s rule every entry of the solution is det(Aᵢ)/det(A), so the denominator is bounded by
Hadamard’s bound on A and the numerator by Hadamard’s bound on the column-replaced matrix. Both are
computable in n² operations before anything is solved. Take the larger, square it, double it, and
that is the modulus the lifting has to reach.
So the whole modular solve is budgeted in advance from end to end: how many p-adic digits to lift,
because the modulus must reach 2·max(bound)²; and then one Euclidean run per entry. The bounds are
generous — Hadamard’s is slack by whatever cancellation the determinant had in it, and the answer’s
parts are usually far below their ceilings — so a routine sized this way does noticeably more lifting
than it needed. That is the same trade the prime budget made and for the same reason: the only
alternative is to watch the reconstruction and stop when it settles, and a reconstruction that
settles has coincided rather than converged. Nothing in it
adapts, nothing watches itself, and as the previous essay
noted that is the opposite of how every iterative method
here terminates.
Fig. 3 The parts being bounded: the answer’s own length against the question’s, where every denominator
divides det A and the numerators can exceed it.
The consequence for cost is a factor of two that is easy to miss. The modulus must be twice the
square of the longer part, so it has about twice as many bits as the answer does. A p-adic solve
that produces k correct digits recovers fractions with about k/2 digits in each part, and a routine
sized against the answer’s own length rather than against twice it will lift exactly half as far as
it needs to and reconstruct confidently wrong fractions.
Where the ratio of the parts matters and where it does not #
The bound being about the larger part has a consequence for how a solve should be posed, and it is
the kind of thing that only shows up once the bound is written correctly.
An entry of the solution whose parts are 10²⁰ and 3 costs the same modulus as one whose parts are
10²⁰ and 10²⁰. So a system whose answer happens to have small denominators is not cheaper to
reconstruct, and the common intuition — nice answers are cheap — is exactly half true: a nice
answer is cheap only if both parts are small.
Where it bites is a system with a mixed answer, some entries large and some tiny. The modulus is
sized against the worst entry and every entry is reconstructed at that modulus, so the cost is set by
one component. That is the same shape as
a stopping test governed by whichever quantity is slowest,
except that here there is nothing to race: the requirement is a maximum over the components and it is
computed rather than observed.
The repair, where one is available, is to reconstruct entry by entry and stop lifting for the entries
that have already been recovered and verified. It works, and it changes the routine’s character from
a fixed budget into an adaptive one — which reintroduces exactly the thing the budget existed to
avoid, since an entry that reconstructs to the same fraction at two successive moduli has not been
verified, it has coincided.
It is worth being concrete about what a caller sees, because the answer is: nothing.
The reconstruction returns a fraction. That fraction, substituted into the original system, does not
satisfy it — so the failure is detectable, by exactly one test: form A·y − d·b in integers and
check that it is the zero vector. That is cheap, it is exact, and it is the check
the essay on the answer’s length argues should be
the return type’s natural form anyway.
Without it there is no signal. The fraction has plausible-sized parts, its residue is the right
residue, and there is no residual to be small or large because nothing was rounded. A routine that
lifts to a modulus it guessed at and does not verify has a silent failure mode with no observable
symptom, and the observable symptom exists and costs one matrix–vector product.
It is worth assembling the three modular essays into the single algorithm they describe, because each
of them is a component and none of them is the method.
Given an integer matrix A, an integer right-hand side b, and a request for the exact rational
solution:
Bound the answer. Hadamard’s bound on A gives a ceiling on every denominator; Hadamard’s bound
on each column-replaced matrix gives one on every numerator. Take the larger, call it B.
Choose a prime and check it. A prime p is usable when A is invertible modulo p, which one
elimination decides. An unlucky prime is rejected here rather than discovered later.
Lift. Solve modulo p, correct, solve again — doubling the number of correct p-adic digits each
round — until the modulus passes 2B². Every operation in this stage is on machine words.
Reconstruct. One truncated Euclidean run per entry recovers the fraction from its residue.
Verify. Form A·y − d·b in integers and check it is the zero vector.
Step 1 is the budget, step 2 is
the unlucky prime, steps 3 and 4 are this essay, and step
5 is the only part that is not an algorithm at all — it is the check that turns the answer into a
certificate, and it costs one matrix–vector product in exact integers.
What is notable about the list is that nothing in it adapts. Every quantity that decides how much
work happens is computed before any work happens, from bounds rather than from observations. A
routine built this way either returns the exact answer or fails a check, and it never returns
something approximately right — which is the whole difference between this field and the rest of the
site, stated as a control flow rather than as a philosophy.
Fig. 4 A denominator larger than the numerator, where the cliff has moved right by the difference.Fig. 5 And the extreme case, a unit numerator, where the bound is entirely about the denominator.Fig. 6 A large numerator and a small denominator, which the product bound would have priced as the same
problem as the last one and is not.Fig. 7 The classical approximation to π, at every modulus from 2³ to 2⁴⁴.Fig. 8 Three-digit entries, where both parts of every entry are longer and the modulus needed doubles with
them.Fig. 9 The two-dimensional lattice reduction this reconstruction is, in the field’s own picture of it.Fig. 10 And at a skew of forty, where the short vector is very much shorter than the basis given.Fig. 11 Hadamard’s bound, which supplies the numbers this reconstruction has to be sized against.Fig. 12 The other way a modular computation returns a correct answer to the wrong question.Fig. 13 The determinant every denominator divides, computed three ways.Fig. 14 And the question of whether the exact answer was worth reconstructing at all.Fig. 15 Iterative refinement, whose p-adic lifting is the analogue and whose failure mode is not.Fig. 16 Buying accuracy back in floating point, where the recovery is gradual rather than a cliff.Fig. 17 A small fraction, recovered at 2^9 rather than 2^18.Fig. 18 A four-digit numerator, where the cliff has moved by eight bits.Fig. 19 And a denominator larger than the numerator, where it moves again.Fig. 20 The parts being recovered, and how long they are.Fig. 21 The bound that supplies the modulus this reconstruction is sized against.Fig. 22 The determinant every denominator divides.Fig. 23 The prime that has to be checked before any lifting starts.Fig. 24 The two-dimensional lattice this reconstruction reduces, at a larger skew.Fig. 25 The invariant factors that decide which primes are unusable.Fig. 26 The growth the p-adic route exists to avoid.Fig. 27 A large numerator with a small denominator.Fig. 28 A five-digit numerator, at 2^35.Fig. 29 The parts of an ill-conditioned system’s answer.Fig. 30 The determinant every denominator divides.Fig. 31 Hadamard, bounding the parts this reconstruction is sized against.Fig. 32 The lattice, at a small skew.Fig. 33 The invariant factors that decide which prime may be lifted from.Fig. 34 The prime that must be rejected before lifting starts.