AFTD Auto-Formalizing Theoretical Domains

quadratic_red_mod17_certificate

theoremverified

No three elements x,y,z of {0,3,6} modulo 17 satisfy x − 2y + z = 2.

Statement

theorem quadratic_red_mod17_certificate : ∀ x y z : ZMod 17, x ∈ ({0, 3, 6} : Finset (ZMod 17)) → y ∈ ({0, 3, 6} : Finset (ZMod 17)) → z ∈ ({0, 3, 6} : Finset (ZMod 17)) → x - 2 * y + z ≠ 2
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 asserts that no triple $(x, y, z)$ chosen from $\{0, 3, 6\} \subseteq \mathbb{Z}/17\mathbb{Z}$ satisfies the linear relation $x - 2y + z = 2$. Because the domain is finite, the proof proceeds by exhaustive computation via Lean's `decide` tactic under increased resource limits.

  1. For all $x, y, z \in \mathbb{Z}/17\mathbb{Z}$, if $x, y, z \in \{0, 3, 6\}$, then $x - 2y + z \neq 2$ in $\mathbb{Z}/17\mathbb{Z}$. automation

    Since $\mathbb{Z}/17\mathbb{Z}$ is a finite type and membership in the finset $\{0, 3, 6\}$ as well as equality in $\mathbb{Z}/17\mathbb{Z}$ are decidable, the entire universal statement is decidable by exhaustive case analysis. The tactic `decide` evaluates this proposition by brute-force computation across all triples, completing under the increased limits on recursion depth and heartbeats.

    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_red_mod17_certificate : ∀ x y z : ZMod 17, x ∈ ({0, 3, 6} : Finset (ZMod 17)) → y ∈ ({0, 3, 6} : Finset (ZMod 17)) → z ∈ ({0, 3, 6} : Finset (ZMod 17)) → x - 2 * y + z ≠ 2 := by  set_option maxRecDepth 32768 in    set_option maxHeartbeats 3000000 in      decide
See it in the graphDiscuss this resultChallenge it