AFTD Auto-Formalizing Theoretical Domains

quadratic_blue_mod17_certificate

theoremverified

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.

  1. 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}.

    lines 2–4

      set_option maxRecDepth 32768 in
        set_option maxHeartbeats 3000000 in
          decide

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

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
See it in the graphDiscuss this resultChallenge it