AFTD Auto-Formalizing Theoretical Domains

quadratic_mod34_no_seed_witness

theoremverified

The set S={0,4,7,14,21,28,31} modulo 34 avoids red triples of second difference 2 and hits every monic quadratic sequence in its first 17 terms, yet contains no pullback of any translate of the four listed modulo-17 seed sets. The pullback of a residue r contains both r and r+17.

Statement

theorem quadratic_mod34_no_seed_witness : let S : Finset (ZMod 34) := {0, 4, 7, 14, 21, 28, 31}; let T : Finset ℕ := {0, 4, 7, 14, 21, 28, 31}; (∀ x y z : ZMod 34, x ∈ S → y ∈ S → z ∈ S → x - 2*y + z ≠ 2) ∧ (∀ a b : ZMod 34, ∃ k : Fin 17, (k.val : ZMod 34)^2 + a*k.val + b ∈ S) ∧ (∀ t : Fin 17, ∀ A ∈ ([{0,3,6}, {0,5,11}, {0,3,10}, {0,4,8,12}] : List (Finset ℕ)), ∃ r ∈ A, (t.val+r)%17 ∉ T ∨ (t.val+r)%17+17 ∉ T)
Source
Explicit finite counterexample in experiment 25430 for OP-1482.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by exhibiting an explicit seven-element set $S = \{0, 4, 7, 14, 21, 28, 31\} \subseteq \mathbb{Z}/34\mathbb{Z}$ and verifying three properties independently. First, $S$ avoids red triples with second difference 2 by expanding the membership hypotheses into finite disjunctions and exhausting all $7^3 = 343$ triples using modular arithmetic. Second, the condition that $S$ hits every monic quadratic sequence in its first 17 terms is verified by a bounded finite search over all 1156 quadratic polynomials. Third, the avoidance of pullbacks of translates of the four modulo-17 seed sets is confirmed by finite evaluation over all 17 shifts. Finally, the three components are combined into the desired conjunction.

  1. For any $x, y, z \in S$, each variable equals one of the seven residues $0, 4, 7, 14, 21, 28, 31 \pmod{34}$.

    Introduce arbitrary residues $x, y, z \in \mathbb{Z}/34\mathbb{Z}$ assumed to lie in $S$. Unfolding the definition of $S = \{0, 4, 7, 14, 21, 28, 31\}$ and rewriting with `Finset.mem_insert` and `Finset.mem_singleton` expands each membership hypothesis into an explicit seven-way disjunction of equalities.

    lines 8–9

    uses Finset.mem_insert, Finset.mem_singleton

      intro x y z hx hy hz
      simp only [S, Finset.mem_insert, Finset.mem_singleton] at hx hy hz
  2. The set $S$ contains no red triple of second difference 2; that is, $x - 2y + z \ne 2$ for all $x, y, z \in S$. automation

    Perform an exhaustive case analysis across all $7 \times 7 \times 7 = 343$ possible assignments for $(x, y, z) \in S^3$. In each case, substituting the concrete residues reduces the goal to an inequality between known values in $\mathbb{Z}/34\mathbb{Z}$, which is closed by modular arithmetic evaluation (`decide`).

    lines 10–12

      rcases hx with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
        rcases hy with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
        rcases hz with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> decide
  3. Every monic quadratic sequence over $\mathbb{Z}/34\mathbb{Z}$ has at least one of its first 17 terms in $S$. automation

    The goal asserts that for all $a, b \in \mathbb{Z}/34\mathbb{Z}$, there exists $k \in \{0, \dots, 16\}$ such that $k^2 + ak + b \in S$. Because $\mathbb{Z}/34\mathbb{Z}$ has 34 elements, checking all $34^2 = 1156$ pairs $(a, b)$ over the 17 candidate values of $k$ is a finite search over decidable predicates; the decision procedure `decide` proves it by exhaustive evaluation.

    line 15

      decide
  4. No pullback of any translate of the four modulo-17 seed sets is entirely contained in $S$. automation

    The theorem states that for each shift $t \in \{0, \dots, 16\}$ and each seed set $A \in \{\{0,3,6\}, \{0,5,11\}, \{0,3,10\}, \{0,4,8,12\}\}$, there exists $r \in A$ such that $(t+r) \bmod 17 \notin T$ or $(t+r) \bmod 17 + 17 \notin T$. Since the set of shifts is finite and the list contains four finite sets, `decide` verifies this universal claim by exhaustive finite computation.

    line 20

      decide
  5. The set $S$ simultaneously satisfies the red-avoidance, quadratic-hitting, and seed-avoidance properties.

    Assemble the three auxiliary lemmas (`test_mod34_red`, `test_mod34_blue`, and `test_mod34_seeds`) into the required conjunction using the constructor for `∧`.

    line 23

    uses test_mod34_red, test_mod34_blue, test_mod34_seeds

      exact ⟨test_mod34_red, test_mod34_blue, test_mod34_seeds⟩
Finset.mem_insert
An element $a$ belongs to $\operatorname{insert} b\ s$ if and only if $a = b$ or $a \in s$.
Finset.mem_singleton
An element belongs to the singleton set $\{a\}$ if and only if it equals $a$.
test_mod34_red
No three elements $x, y, z \in S$ satisfy $x - 2y + z = 2$ in $\mathbb{Z}/34\mathbb{Z}$.
test_mod34_blue
Every monic quadratic sequence $k^2 + ak + b$ over $\mathbb{Z}/34\mathbb{Z}$ has at least one value in $S$ for $k \in \{0, \dots, 16\}$.
test_mod34_seeds
For every shift $t \in \{0, \dots, 16\}$ and each of the four listed modulo-17 seed sets $A$, the pullback of $t + A$ to $\mathbb{Z}/34\mathbb{Z}$ is not entirely contained in $T$.

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

Lean’s trace was cut to the first 400 of 405 tactics.

set_option maxRecDepth 4096set_option maxHeartbeats 5000000private def S : Finset (ZMod 34) := {0,4,7,14,21,28,31}private def T : Finset ℕ := {0,4,7,14,21,28,31}theorem test_mod34_red : ∀ x y z : ZMod 34, x ∈ S → y ∈ S → z ∈ S → x - 2*y + z ≠ 2 := by  intro x y z hx hy hz  simp only [S, Finset.mem_insert, Finset.mem_singleton] at hx hy hz  rcases hx with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>    rcases hy with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>    rcases hz with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> decidetheorem test_mod34_blue : ∀ a b : ZMod 34, ∃ k : Fin 17, (k.val : ZMod 34)^2 + a*k.val + b ∈ S := by  decidetheorem test_mod34_seeds : ∀ t : Fin 17,    ∀ A ∈ ([{0,3,6}, {0,5,11}, {0,3,10}, {0,4,8,12}] : List (Finset ℕ)),      ∃ r ∈ A, (t.val+r)%17 ∉ T ∨ (t.val+r)%17+17 ∉ T := by  decidetheorem quadratic_mod34_no_seed_witness : let S : Finset (ZMod 34) := {0, 4, 7, 14, 21, 28, 31}; let T : Finset ℕ := {0, 4, 7, 14, 21, 28, 31}; (∀ x y z : ZMod 34, x ∈ S → y ∈ S → z ∈ S → x - 2*y + z ≠ 2) ∧ (∀ a b : ZMod 34, ∃ k : Fin 17, (k.val : ZMod 34)^2 + a*k.val + b ∈ S) ∧ (∀ t : Fin 17, ∀ A ∈ ([{0,3,6}, {0,5,11}, {0,3,10}, {0,4,8,12}] : List (Finset ℕ)), ∃ r ∈ A, (t.val+r)%17 ∉ T ∨ (t.val+r)%17+17 ∉ T) := by  exact ⟨test_mod34_red, test_mod34_blue, test_mod34_seeds⟩
See it in the graphDiscuss this resultChallenge it