quadratic_mod34_no_seed_witness
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.
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.
uses
Finset.mem_insert,Finset.mem_singletonintro x y z hx hy hz simp only [S, Finset.mem_insert, Finset.mem_singleton] at hx hy hz
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`).
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
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.
decideNo 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.
decideThe 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 `∧`.
uses
test_mod34_red,test_mod34_blue,test_mod34_seedsexact ⟨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$.
- The proofs of `test_mod34_blue` and `test_mod34_seeds` rely entirely on the `decide` tactic, which verifies the finite universal quantifications (over all 1156 monic quadratic sequences and all 17 shifts of the four seed sets) by kernel evaluation without generating human-readable witnesses.
- In `test_mod34_red`, the 343 individual arithmetic inequalities $x - 2y + z \ne 2$ are verified in parallel across all case branches via `<;> decide`.
- The witness set is defined both as $S \subseteq \mathbb{Z}/34\mathbb{Z}$ for the algebraic properties and as $T \subseteq \mathbb{N}$ for the modular pullback condition.
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.
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⟩