A fraction recovered from one remainder

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.

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.

The algorithm is one that is already there #

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.

Why exactly one fraction is small enough #

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.

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.

There is no partial credit #

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. When it returns anything, 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.

The qualifier in that paragraph is doing real work, and how much is a measurement rather than a detail — it is the difference between a routine that fails loudly and one that does not.

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 measurement, and what it took to state it #

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¹⁷·⁹.

Whether that is 355/113 or the problem #

One fraction against forty-two moduli establishes the sharpness of the boundary for one fraction, and the sentences above claim it for the method. So the sweep was repeated on sixty random coprime pairs with parts of eight to twenty-eight bits, at every modulus 2ᵉ + 1 from e = 4 up to each fraction’s own bound, and the claim holds in three parts and fails in a fourth.

No fraction is recoverable early. Of 1,628 attempts below the lattice bound, zero returned the right fraction. The bound is not merely sufficient; on random input it is necessary, which is a stronger statement than the lattice argument makes and is the one a budget depends on.

There are no holes. Sweeping past the bound as well, the success region is an up-set in every one of the fractions tried: once a modulus works, every larger one does. Nothing here has the shape the figure would have if reconstruction were flaky near its boundary.

And the cliff is where the bound says. The first success is never below it and never more than three bits above, three bits being the gap between 2·max(|n|, d)² and the next power of two.

The fourth result corrects the paragraph above rather than confirming it. “It returns a different fraction” describes 46% of those 1,628 attempts. The other 54% return nothing at all — the size condition is never met, the routine says so, and the failure is the loud one. More to the point, the proportions are not uniform: within three bits of the cliff, which is exactly where a routine that under-budgeted its lifting would land, 71% refuse.

So the danger is real and it is a minority of the cases, and both halves of that matter. A routine that lifts a little short usually gets told; roughly three times in ten it gets a plausible wrong fraction instead, with no symptom. Every one of the 751 substitutions had a smaller larger-part than the true fraction — 751 of 751 — which is the one clause of the account that is exactly right, and which is also why the substitution is undetectable by inspection: a shorter fraction is precisely what a caller expects a reconstruction to return.

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.

Knowing how large the parts can be #

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.

Two bounds are being composed here and only one of them is slack, which is worth separating. Hadamard’s bound on the determinant is generous, for the reason above: it cannot see the cancellation. The reconstruction bound 2·max(n, d)² is not generous at all — it is essentially attained, and the sweep says so at every scale.

At a denominator of 29 the bound is 2^17.9 and recovery arrives at 2^18; at 1013, 2^21.0 and 2^21; at 9973, 2^27.6 and 2^28; at 99991, 2^34.2 and 2^35. Four denominators spanning four orders of magnitude, and in every case the cliff sits at the first power of two the bound permits. So the lifting cannot be shortened by hoping — there is no margin in this half of the budget to give back, and a routine that lifts one digit short of it recovers nothing rather than something slightly wrong. The slack in the whole chain lives entirely in Hadamard’s estimate of how large the parts might be, not in the modulus those parts then need.

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.

What the failure looks like from outside #

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.

The measurement two sections above sharpens what that verification is buying, and sharpens it in an uncomfortable direction. Most under-budgeted reconstructions announce themselves — the routine returns nothing, and the caller cannot proceed without noticing. The verification step is therefore not the difference between working and failing; it is the difference between the three cases in ten that would otherwise pass silently and everything else. A step whose whole value is a minority of a failure mode is exactly the step that gets dropped when someone measures how often it fires and finds it fires rarely, which is the argument this site’s habit exists to refuse: a check earns its place by what it would catch, not by how often it does.

The whole route, end to end #

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:

1. 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.
2. 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.
3. 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.
4. Reconstruct. One truncated Euclidean run per entry recovers the fraction from its residue.
5. 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.