quadratic_blue_mod17_certificate
Every monic quadratic sequence over the residues modulo 17 has a term in {0,3,6} among the first 17 terms.
Statement
theorem quadratic_blue_mod17_certificate : ∀ a b : ZMod 17, ∃ k : Fin 17, (k.val : ZMod 17) ^ 2 + a * k.val + b ∈ ({0, 3, 6} : Finset (ZMod 17))- Source
- Exact finite modular computation for the rational quadratic approach to OP-1482.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem states that every monic quadratic polynomial over the residues modulo 17 takes at least one value in {0, 3, 6}. Because the residue ring ℤ/17ℤ is finite, there are only 17 × 17 = 289 pairs of coefficients (a, b) to test, making the proposition purely decidable. Lean proves this by brute-force evaluation using the decide tactic with increased recursion depth and heartbeat limits.
The finite search over all 289 coefficient pairs (a, b) in (ZMod 17)² succeeds. automation
Because ZMod 17 and Fin 17 are finite types, the quantified assertion is decidable by exhaustive computation. Raising maxRecDepth to 32768 and maxHeartbeats to 3000000 provides sufficient resources for the decide tactic to evaluate all 17 × 17 = 289 choices of (a, b) and verify that each polynomial attains a value in {0, 3, 6}.
set_option maxRecDepth 32768 in set_option maxHeartbeats 3000000 in decide
- The proof is carried out entirely by computational reflection (`decide`) over a finite domain, without an analytic mathematical argument.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem quadratic_blue_mod17_certificate : ∀ a b : ZMod 17, ∃ k : Fin 17, (k.val : ZMod 17) ^ 2 + a * k.val + b ∈ ({0, 3, 6} : Finset (ZMod 17)) := by set_option maxRecDepth 32768 in set_option maxHeartbeats 3000000 in decide