← Blog

Modulo Details: Failure of an Elementary Method

This post is presented in the LLM-Lensed Iterative Blogging format: a hand-written summary by me first, then a full version generated by an LLM from that summary.

Summary

Written by hand.

Let's think about Diophantine equations through the lens of proof/decidability. They have a solution or they don't. If they do, giving the solution (plus a bounded computation) is always a valid proof. In the case of nonexistence of solutions, there is no equivalent guaranteed proof strategy. For multivariate polynomials, one elementary nonexistence proof strategy shows up frequently, especially in contest math: consider the problem modulo m. For example, neither 6x+15y−2 = 0 nor x2+4y−2 = 0 has integer solutions, and the easiest proofs work modulo m.

But there can't be any uniform nonexistence procedure by MRDP (Matiyasevich 1970). In fact, if every Diophantine equation with no solutions also had no solutions modulo some m, we would get a very concrete dovetail algorithm contradicting the negative solution to Hilbert's Tenth Problem. Thus, from purely logical/computational reasoning, we have, nonconstructively, that there must be some integer polynomial with no integer solutions but solutions modulo m for every m ∈ ℤ+.

We can get constructivity quickly. MRDP's result isn't just a negative result to H10; it shows that every r.e. set is cut out by a Diophantine equation. Even further, it gives an effective, uniform procedure for turning a description of a Σ1 formula into an integer polynomial (introducing extra variables). ZFC is (much more than) strong enough to carry out any modular nonexistence proof and to prove the MRDP result (in fact IΣ1 is enough (Gaifman and Dimitracopoulos 1980)). The existence of a proof of ⊥ in ZFC is a Σ1 sentence. Thus, there is a concrete Diophantine equation pZFC(x, ȳ) = 0 which ZFC knows has a solution iff x codes a proof of ⊥ in ZFC. Assuming ZFC is consistent, pZFC(x, ȳ) has no solutions, but if there were some m for which pZFC(x, ȳ) had no solutions in ℤ/m then ZFC could check the finitely many options for x and ȳ, conclude there is no solution in ℤ/m, and thus no solution in ℤ and further that there is no proof of ⊥, i.e. that ZFC is consistent. By Gödel's Second Incompleteness Theorem, (assuming consistency) ZFC cannot prove its own consistency, so pZFC(x, ȳ) cannot have a solution modulo any m. This is constructive, but the degree and number of variables in pZFC(x, ȳ) are immense.

Are any such polynomials human-understandable? Are there any you could write down? After mulling in the background for a few weeks I realized we get a very clean example from Lagrange's Four Square Theorem: x2+y2+z2+w2+1 = 0. It has no integer solutions by positivity of the left side, but for any m ∈ ℤ+ there are a,b,c,d such that a2+b2+c2+d2 = m−1 and thus a2+b2+c2+d2+1 = m ≡ 0 mod m. We can actually get a similarly nice quadratic of three variables with this property by using a generalization of Lagrange's Four Square Theorem to triangular numbers (part of a too-good-to-be-true family of geometric theorems) and clearing denominators. But can we use fewer than three variables?

I had some number theorist friends who knew classical examples of small Diophantine equations with no integer solutions but solutions modulo p for each prime p. But the general m case was not obvious. Years later, in the present day, I decided to ask Claude. Claude found the answer quickly and when asked was able to give the relevant sources. The answer is that quintics like (x3−x−1)(x2+23) can have no solutions in ℤ but solutions in every ℤ/m, but quartics with no solution will always witness their lack of solution in some modulus. The reason for both is a fun and enlightening journey through some Galois theory you can experience for yourself below.

Generated by claude-opus-4-8

The text below is AI-generated from the summary above.

The last paragraph promised a journey, so let's take it. We want to understand two facts, which turn out to be two faces of one coin:

The engine behind both is the same. We will translate the analytic-looking question “does f have a root mod p?” into a question about a finite permutation group — the Galois group of f — and then simply read off both answers. The single load-bearing idea, when we get there, is an elementary fact about group actions due to Jordan. Everything else is plumbing to connect that fact to prime numbers.

Throughout, f is a monic polynomial with integer coefficients. Monicity is a convenience worth one sentence: by the rational root theorem, any rational root of a monic integer polynomial is an integer, so for our examples “no integer root” and “no rational root” are the same statement, and I'll use them interchangeably.

Step 1: From “every modulus” to “every prime”

The phrase “a root modulo every m” sounds like infinitely many unrelated conditions, but two classical tools collapse it down to primes.

First, the Chinese Remainder Theorem: if m = p1e1 ··· pkek then ℤ/m ≅ the product of the ℤ/piei, and a root of f mod m is exactly a compatible tuple of roots mod each prime power. So “f has a root mod every m” is equivalent to “f has a root mod every prime power pe.”

Second, Hensel's lemma: if f(a) ≡ 0 (mod p) and f′(a) ≢ 0 (mod p) — a simple root mod p — then that root lifts uniquely to a root mod pe for every e. The derivative f′ can vanish at a root only for primes dividing the discriminant disc(f), and there are only finitely many of those. So for all but finitely many primes, “root mod p” already gives “root mod pe for all e” for free.

The upshot: up to a finite, explicitly checkable set of bad primes (the ones dividing the discriminant), the whole question reduces to does f have a root modulo each prime p? We'll do the bad-prime bookkeeping for our concrete example by hand at the end.

Step 2: The roots carry a group

Let f be squarefree, with roots Ω = {α1, …, αn} in ℂ and splitting field K = ℚ(α1, …, αn). The Galois group G = Gal(K/ℚ) permutes the roots, faithfully, so it is a subgroup of the symmetric group: G ≤ Sym(Ω) ≅ Sn.

Two dictionary entries are all we need:

So f has a rational root if and only if G has an orbit of size 1 (a linear factor). Our target polynomials will have no such orbit.

Step 3: Reducing mod p is applying a Frobenius

Fix a prime p not dividing disc(f). Reducing the roots modulo a prime of K lying over p lands them in an algebraic closure of 𝔽p, and there the Frobenius map φ: t ↦ tp permutes them. As an element of G it is only well-defined up to conjugacy (the choice of prime above p), giving a conjugacy class Frobp ⊆ G.

Dedekind's factorization theorem says the cycle type of Frobp acting on Ω matches the degrees of the irreducible factors of f mod p. We only need the simplest consequence. A root of f in 𝔽p is a root β with βp = β — that is, a fixed point of Frobenius. Hence:

f has a root mod p  ⇔  Frobp has a fixed point on Ω.

Step 4: Every group element is some Frobenius

Which classes actually occur as Frobp? All of them. The Chebotarev density theorem says each conjugacy class C ⊆ G equals Frobp for a positive density of primes p; we need only the older, weaker fact that every class occurs for infinitely many p. Combining with Step 3:

f has a root mod almost every p  ⇔  every element of G has a fixed point on Ω.

(Left to right: if some g ∈ G has no fixed point, choose p with Frobp = g; then f has no root mod p. Right to left is immediate.)

Step 5: The problem is now pure group theory

Strip away the number theory and here is what's left. We have a finite group G acting on a finite set Ω with |Ω| = n = deg f, and:

Call an element with no fixed point a derangement. We are hunting for a group action with no orbit of size 1 but no derangements at all, and we'd like n = |Ω| as small as possible. That is the entire problem.

Step 6: Jordan's theorem — transitive actions always derange

Here is the one real theorem, and it is genuinely elementary.

Theorem (Jordan). If a finite group G acts transitively on a set Ω with |Ω| ≥ 2, then some element of G is a derangement.

Proof. By the orbit-counting (Burnside) lemma, the average number of fixed points over the group equals the number of orbits:

(1/|G|) ∑g∈G |Fix(g)| = #{orbits} = 1,

the last equality because the action is transitive. The identity alone fixes all |Ω| ≥ 2 points, contributing strictly more than the average of 1. For the average to come back down to 1, some element must fix strictly fewer than 1 point — i.e. fix none. ■

The consequence for us is immediate and strong. If f is irreducible of degree ≥ 2, then G acts transitively on its ≥ 2 roots, so it has a derangement, so f misses a root modulo infinitely many primes. An irreducible polynomial of degree at least 2 is never a root-mod-every-prime example. To have any hope, f must factor — we need at least two orbits.

Step 7: Degrees 1 through 4 are impossible

Now minimize n = ∑i |Oi| over actions with every orbit size ≥ 2 and no derangement. We rule out everything below 5.

So no action on n ≤ 4 points avoids derangements without a size-1 orbit. Translating back through Steps 3–4: every polynomial of degree ≤ 4 with no rational root has a derangement in its Galois group, hence a prime p at which it has no root. That is claim (B): an unsolvable quartic always betrays itself modulo some prime. (For the original integer-coefficient framing the only gap is non-monic low-degree cases like 2x−1, which fail a modulus even more cheaply — here mod 2.)

Step 8: Degree 5 works — the S3 pattern

The only orbit shape left to try at n = 5 with all parts ≥ 2 is 3+2. Take G = S3 and let it act on two sets at once:

Now act on the disjoint union Ω = Ω3 ⊔ Ω2. An element deranges the union only if it deranges both pieces. But the derangements of Ω3 are the 3-cycles, which are even, lie in A3, and therefore fix Ω2; and the derangements of Ω2 are the transpositions, which fix a point of Ω3. The two derangement sets are disjoint, so no element of S3 deranges both — every element fixes a point of Ω. Neither orbit has size 1. We have exactly the action we wanted, on 3+2 = 5 points. Any polynomial whose Galois group acts this way has a root mod almost every prime but no rational root.

Step 9: Writing it down — (x3−x−1)(x2+23)

The cubic. g(x) = x3−x−1 has no rational root (±1 both fail), so it is irreducible. Its discriminant is Δ = −4(−1)3 − 27(−1)2 = 4 − 27 = −23. An irreducible cubic has Galois group A3 exactly when its discriminant is a perfect square, and S3 otherwise; since −23 is not a square, Gal(g) = S3. The splitting field of g therefore contains a unique quadratic subfield, the one fixed by A3, namely ℚ(√−23).

Choosing the quadratic factor. We want the size-2 orbit of Step 8 to be this quadratic subfield, so that its stabilizer is A3 and the 3-cycles fix it. The quadratic whose splitting field is ℚ(√−23) is x2+23, with roots ±√−23. So we set f = (x3−x−1)(x2+23); its splitting field is just the S3 field of g, and G = S3 acts as the 3+2 pattern above.

This is exactly where the sign matters. x2−23 would give the different field ℚ(√23), which is not the subfield A3 fixes, and the alignment breaks — the congruence check below shows (x3−x−1)(x2−23) already fails modulo 3.

The same fact as congruences. It is worth seeing the covering of Step 8 turn into Legendre symbols. The polynomial f has no root mod p iff g has none and x2+23 has none. Now g has no root mod p iff Frobp is a 3-cycle, which forces Frobp ∈ A3, i.e. p splits in ℚ(√−23), i.e. the Legendre symbol (−23 / p) = +1. But (−23 / p) = +1 is precisely the condition that x2+23 has a root mod p. So whenever the cubic loses its root, the quadratic gains one: they cannot fail together, and f has a root modulo every unramified prime. (For x2−23 the relevant symbol is (23 / p), and when (−23 / p) = 1 we have (23 / p) = (−23 / p)(−1 / p) = (−1 / p), which is −1 for p ≡ 3 (mod 4) — both factors fail, as at p = 3.)

The bad primes and prime powers. Only p = 2 and p = 23 divide disc(f), so only these need care; everywhere else the root found above is simple and Hensel lifts it to all powers.

With CRT stitching the prime powers together, f has a root modulo every m. And it has no integer root at all: g has none, and x2+23 = 0 has no real solution. That is claim (A), completely explicit.

Why 5, and not less

Putting the pieces side by side: the existence in (A) and the impossibility in (B) are the same computation run in two directions. Both ask when a finite group can act without a global fixed point yet without any derangement. Jordan's theorem forbids it for a single orbit, the little case analysis forbids it through four points, and S3 acting as 3+2 achieves it at five. The quintic (x3−x−1)(x2+23) is simply the smallest faithful arithmetic incarnation of that group action. Polynomials like it — with a root modulo every integer but no rational root — are called intersective, and the group-theoretic heart of the whole story is Jordan's lemma; Serre's On a theorem of Jordan is the beautiful modern account, and the natural place to read further.

References

  1. Yu. V. Matiyasevich, Enumerable sets are Diophantine, Doklady Akademii Nauk SSSR 191 (1970), 279–282; English translation in Soviet Mathematics Doklady 11 (1970), 354–358.
  2. H. Gaifman and C. Dimitracopoulos, Fragments of Peano's arithmetic and the MRDP theorem, in Logic and Algorithmic (Zürich, 1980), Monographie 30 de L'Enseignement Mathématique, Geneva, 1982, pp. 187–206.
  3. J.-P. Serre, On a theorem of Jordan, Bulletin of the American Mathematical Society 40 (2003), no. 4, 429–440.
  4. H. W. Lenstra Jr. and P. Stevenhagen, Chebotarev and his density theorem, The Mathematical Intelligencer 18 (1996), no. 2, 26–37.
  5. D. S. Dummit and R. M. Foote, Abstract Algebra, 3rd ed., Wiley, 2004 (Galois theory, Hensel's lemma, and the discriminant criterion for the Galois group of a cubic).
← All posts