A prime that divides the answer

Modular arithmetic buys the exact-arithmetic field its only route with no growth in it: work modulo a prime below 2²⁶, and every quantity from the first step to the last is a machine word. The price is paid in one place, and it is unlike anything else on this site.

Build a six by six integer matrix whose determinant is 30030. Reduce it modulo 3 and eliminate. The elimination reaches a column of zeros and reports that the determinant is zero.

That report is true. Over the field with three elements the matrix genuinely is singular: its rows are linearly dependent there, its rank is five rather than six, and every statement the elimination made about it is right. What is wrong is nothing at all inside the computation. What is wrong is that a caller asked about the rationals and was answered about 𝔽₃.

Why this has no floating-point analogue #

It is tempting to file this beside the site’s other zero-detection problems and it does not belong there.

Deciding that a zero has arrived is about a quantity that is 10⁻¹⁴ when the theory says zero, and about the judgement required to call it one. Rank is a decision is the same judgement in its most consequential form: a singular value of 10⁻¹² is not zero, calling it zero is a choice, and the choice is where the rank comes from. In both cases there is a small number, somebody has to decide about it, and the essay is about the decision.

Here there is no small number. The residue is the integer 0, exactly, arrived at by a sequence of integer operations none of which rounded. There is nothing to threshold, nothing to be careful about, and no amount of extra precision helps — extra precision is what this route already has infinitely much of. The failure is not in the arithmetic’s accuracy. It is that a different question was answered, correctly.

That makes it the second instance on this site of a class the graph field opened: a computation whose output is right and whose subject is wrong. The first was a partition decided in the last digit, where a correctly computed eigenvector of a degenerate matrix yields a partition that is one of several and the choice among them was made by rounding. Here the substitution is cleaner and more total: not one of several answers, but the answer to a different question, and it does not even have the courtesy to vary with the seed.

How likely it is, and why that is the wrong question #

A prime p is unlucky for a matrix when p divides det A. For a determinant D, the number of primes below N that divide it is at most log₂|D|, so among primes near 2²⁶ the proportion that are unlucky is about log₂|D| divided by the number of primes in the range — a probability of order 10⁻⁶ for a forty-bit determinant, and smaller as the primes get larger.

The figure uses small primes deliberately, because at 26 bits the failure would be invisible and this essay would have nothing to draw. Five of the first twenty-five odd primes divide 30030, which is a rate of twenty per cent; at word-sized primes the same matrix would need millions of draws to hit one.

That the rate falls is not because unlucky primes become rarer — it is because they do not become anything. Widening the pool and counting:

The unlucky primes are the primes dividing 30030, and 30030 has the factorisation it has. The count is a property of the answer, not of the pool, so it is fixed at five however far the search runs.

The unlucky set does not grow with the search. Five of forty, then five of forty-nine: the count is a property of the matrix — the primes dividing one determinant — and widening the range only dilutes it, from 12.5% to 10.2%. That dilution is the whole basis for choosing a prime at random and expecting to be fine.

So the rate runs 16.7%, 14.7%, 12.5%, 10.2% and 7.8% across pools of 30, 34, 40, 49 and 64 — falling purely as 1/π(N), with a numerator that never moves. That is why the probability is the wrong question in the way the heading says: the risk is not small because the event is unlikely in some structural sense, it is small because the numerator is bounded by log₂|D| while the denominator grows without limit. Which also says exactly when the reasoning fails: it fails when the pool is not large, and the pool is not large when the modulus has to be small — a narrow word, an embedded target, a hardware multiplier. On those the numerator has not changed and the denominator has collapsed.

It also says what the cheap defence is, and it is not a larger pool. Since the unlucky primes are exactly the divisors of the determinant, a prime is unlucky if and only if the elimination modulo it loses a pivot — which the elimination discovers on its own, at no cost, in the step where the pivot comes out zero. The check is already being performed and the answer is already known; what is missing is only that the routine reports it rather than continuing. A modular solve that carries the rank it found alongside the residue it computed cannot be surprised by an unlucky prime, whatever the size of the pool it drew from.

The temptation is to treat that probability as a defence, and it is not one, for two reasons.

The determinant is not random and neither are the primes. A matrix arriving from a discretisation or a combinatorial construction very often has a determinant with structure in it — a factorial, a power of two, a product of small primes — and the implementations that use fixed prime tables use the same primes every time. A rare event that is deterministic is not rare in the way the arithmetic suggests: it happens to the same inputs every run, for ever.

And a residue that is genuinely wrong is not slightly wrong. The Chinese remainder theorem combines residues that are jointly consistent with exactly one value modulo the product, so a single corrupted residue gives a completely different value — an integer of comparable length with none of its digits right, and no residual to notice it by.

What an unlucky prime does to a determinant, which is nothing #

The natural next paragraph is the defence: compute more residues than the budget requires and compare, so an unlucky prime is at least detected. That paragraph was here and it was wrong, in a way worth keeping on the page rather than quietly deleting, because the mistake is the one the whole field is prone to.

Reduction modulo p is a ring homomorphism. So det(A mod p) = det(A) mod p, for every prime, whether or not p divides det A. A prime that divides the determinant produces the residue 0, and 0 is the correct residue. The Chinese remainder theorem is being handed correct data and returns the correct integer.

Measured on the hero’s own construction, with all six of 2, 3, 5, 7, 11 and 13 deliberately in the prime set rather than avoided:

seed    primes used    unlucky primes among them    reconstruction    det A
 17         21                    6                     30030         30030
 23         21                    6                     30030         30030
 31         31                    6                     30030         30030

Six unlucky primes, and the answer is exactly right. There is nothing to detect, because nothing went wrong. The determinant route is immune to unlucky primes, and no redundancy is needed to defend it.

Which raises the question of what the opening of this essay was about, and the answer is that the failure is real and sits one level up. The elimination modulo 3 reports zero and that report is correct; the failure is a caller who reads a zero residue as “singular over ℚ”. That is the substitution the essay is named for and it survives this correction untouched. What does not survive is the idea that the substitution propagates through the reconstruction.

Where an unlucky prime genuinely bites is where the algorithm has to divide. Solving, inverting and p-adic lifting all need the matrix to be invertible modulo p, and a prime dividing the determinant makes it not — there the first solve fails and nothing after it recovers, which is the section on lifting below. And it bites the rank, which is not a residue of anything: the rank over 𝔽ₚ is a different function of the matrix, it is a lower bound rather than a congruence, and no reconstruction puts it back. Those are the two cases, and the determinant is in neither.

What redundancy buys, where redundancy is needed #

For the quantities where a residue can be wrong — a solve, a lift, a rank — the defence is to compute more than the budget requires and compare. Reconstruct from the first k primes, where k is what Hadamard’s bound required, and reconstruct again from k+1: if every residue was right the two agree, and if one was not they differ, because they are consistent with different values.

The extra prime does not tell which residue was wrong and does not repair anything. It converts an undetected wrong answer into a detected one, which in a field whose selling point is that the answer is a certificate is the difference between the route being usable and not. Recovering is a retry.

And even there it is not the cheapest detector available, which is the second thing the measurement turned up. Hadamard’s bound already brackets the answer, so a reconstruction that exceeds it is provably wrong at no cost whatever — no extra prime, no second elimination, one comparison of two integers. Corrupting one residue in seventy-three ways across three matrices, seventy-one of the seventy-three land outside the bound, with a median wrong-to-true ratio of 2.4·10²⁶. The two that do not are the cases where the budget had almost no slack, which is exactly where the extra prime is cheapest.

So the honest ordering of the defences is: check the bound, because it is free and catches ninety-seven per cent of what there is to catch; add a prime when the budget is tight; and for the determinant specifically, do neither on account of unlucky primes, because they cannot hurt it.

There is a cheaper defence available for a determinant specifically and it is worth naming because it does not generalise. If any single residue is nonzero then det A is nonzero, since a zero determinant has zero residue at every prime. So a nonsingularity certificate needs one lucky prime rather than a full budget — and a singularity claim needs the full reconstruction, because a matrix can be singular modulo every prime anybody tried and not singular. The asymmetry is the useful part: one of the two answers is cheap to prove and the other is not.

The rank moves too, and it does not come back #

The determinant is the easy case, because it is one number and a wrong residue makes the whole reconstruction disagree. The rank is worse.

Rank over 𝔽ₚ is computed by the same elimination and it is never larger than the rank over the rationals — a dependency among rows over ℚ is a dependency over 𝔽ₚ, but not conversely. So a modular rank is a lower bound on the true rank, and it is a silent lower bound: the elimination does not report having lost anything, because from its point of view nothing was lost.

Which primes lose rank is not arbitrary either. It is exactly the primes dividing the invariant factors of the matrix — the diagonal of its Smith normal form — which means the failure is a property of the matrix’s structure rather than of the arithmetic. Two essays further on, the invariant factors get computed for their own sake; here they are the answer to which primes are unlucky, and for what.

Lifting instead of spreading, and the same trap #

There is a second modular strategy that avoids many primes entirely, and it meets the same problem in a form that is easier to get wrong.

Instead of computing modulo p₁, p₂, … and combining, compute modulo a single prime power p, p², p⁴, … by lifting: solve modulo p, use the residual to correct, solve modulo p again, and each round doubles the number of correct p-adic digits. It is the exact-arithmetic analogue of iterative refinement, and the analogy is close enough to be useful and close enough to mislead.

Refinement in floating point converges when the residual is computed accurately enough and the matrix is not too ill conditioned; it is a numerical statement with a numerical failure mode. Lifting converges when the matrix is invertible modulo p, and if it is not, the very first solve fails and nothing after it can recover. There is no gradual degradation and there is no conditioning: the matrix is invertible mod p or the whole route is unavailable.

So the lifting route has to test one prime for luck at the start and can then forget the question, where the spreading route has to worry about every prime it uses. That is a genuine advantage and it comes with a matching disadvantage — one prime is one point of failure, and a prime chosen badly by a fixed table is chosen badly every run.

Which primes are unlucky is a question with an exact answer #

The probability argument above is the one usually given and it is the weaker of the two available. There is an exact characterisation, and it is worth stating because it turns a risk into a fact about the matrix.

A prime p is unlucky for the determinant exactly when p divides det A. It is unlucky for the rank exactly when p divides one of the invariant factors — the diagonal entries of the Smith normal form — and the number of ranks lost is the number of invariant factors it divides. The matrix in the hero has invariant factors 1, 1, 1, 1, 1, 30030, so the six primes dividing 30030 each cost it one rank and nothing else does.

That is not an estimate and it does not involve a distribution. It means the set of unlucky primes is a finite, computable, matrix-specific list, and that a routine which knew the invariant factors would know exactly which primes to avoid. Of course computing them is harder than the determinant was — which is the usual shape of these things, and is why the practical defence stays probabilistic.

What it does buy is the right mental model. An unlucky prime is not noise and it is not bad luck in any useful sense; it is one of a handful of specific numbers attached to the matrix, and if the matrix came from a construction with small numbers in it then those numbers are small.

What a caller should ask for #

The practical upshot is a rule about interfaces, and it applies well outside this field.

A modular routine should not return “the determinant”. It should return the determinant together with the modulus its answer is certain to, because that is what it actually knows — and a caller that wanted a rational answer can then check whether the modulus was large enough while a caller that wanted a residue can use it directly. Returning the number alone throws away the only information that distinguishes a finished computation from an unfinished one.

That is the same complaint the essay about what a method reports makes about an iterative solver returning its own estimated residual as though it were the true one, and the same complaint the certificate essays make about a routine that returns an answer where it could have returned an answer and a proof. A number without its warranty is a number somebody will use outside the range it was true in, which is the failure the essay about a tolerance nobody meets describes from the other end.

The cost of the defence, measured against what it defends #

The redundancy is one extra elimination out of k, so it costs 1/k of the route — three per cent on a determinant needing thirty primes, thirty-three on one needing three. That is an unusual cost curve: the check is cheapest exactly where the computation is largest, and most expensive on the small problems where a fraction-free elimination would have been affordable anyway.

Which suggests the rule the field actually follows, for the quantities that need the defence at all. Below the size where the modular route wins, fraction-free elimination has no unlucky primes and should be used; above it, the redundancy is nearly free and should be taken. The middle regime — where the check is expensive — is exactly the regime where the other route is available, which is why there is no gap.

For a determinant reconstructed by remaindering, the whole calculation is moot: the section above measures six unlucky primes producing exactly the right answer, so the check being bought is a check against nothing. What is worth taking there is the free one — compare the reconstruction against Hadamard’s bound — which costs a comparison and catches the failures that can happen, namely a residue that is wrong rather than a prime that is unlucky.

The refusal #

The claim this essay exists to break is the natural one: a nonzero determinant has a nonzero residue at every prime, so a modular elimination reporting zero has found a singular matrix. It sounds like a statement about arithmetic and it is a statement about nothing.

The construction that refuses it is built rather than searched for. Take diag(1, …, 1, 30030) and conjugate it by two unimodular matrices — integer matrices with determinant ±1, so the Smith normal form is untouched and the determinant is exactly 30030. The result is a matrix with no visible structure, entries in the hundreds, nonsingular over ℚ, and singular modulo each of 2, 3, 5, 7, 11 and 13. The assertion is fed that matrix and has to reject it.

Searching random matrices for one would have made the figure a statement about the search. Building it makes the six unlucky primes a stated property of the construction, which is what lets the figure assert that the residue is zero exactly at the primes dividing the determinant rather than merely observing that some are.

The distinction is the same one the site makes about every constructed counterexample. A matrix found by looking is evidence that such matrices exist; a matrix built from a property is evidence about what the property does, and it can carry an assertion that fails if the property stops holding. Here the assertion is an equivalence rather than an example: the residue is zero at p if and only if p divides the determinant, checked at every prime in the sweep, so a change to the construction that broke the correspondence would be caught rather than merely making the picture less striking.