harborth_bound_equality_rank_three_implies_six
If every multiset of size 8n - 7 over (ZMod n)^3 has an n-element zero-sum submultiset for all even n ≥ 6 not a power of 2, then every multiset of size 41 over (ZMod 6)^3 has a 6-element zero-sum submultiset.
Statement
theorem harborth_bound_equality_rank_three_implies_six (h : ∀ (n : ℕ), 6 ≤ n → Even n → ¬ n.isPowerOfTwo → ∀ (S : Multiset (Fin 3 → ZMod n)), S.card = 8 * n - 7 → ∃ T : Multiset (Fin 3 → ZMod n), T ≤ S ∧ T.card = n ∧ T.sum = 0) : ∀ (S : Multiset (Fin 3 → ZMod 6)), S.card = 41 → ∃ T : Multiset (Fin 3 → ZMod 6), T ≤ S ∧ T.card = 6 ∧ T.sum = 0- Source
- arXiv:2610.35819 Sec. 10, remark (2)
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Assuming that for every natural number $n$, if $6 \le n$, $n$ is even, and $n$ is not a power of two, then every multiset $S$ with elements in $\mathrm{Fin}\ 3 \to \mathbb{Z}/n\mathbb{Z}$ and cardinality $8n - 7$ contains a submultiset $T \le S$ of cardinality $n$ whose sum is $0$: every multiset $S$ with elements in $\mathrm{Fin}\ 3 \to \mathbb{Z}/6\mathbb{Z}$ and cardinality $41$ contains a submultiset $T \le S$ of cardinality $6$ whose sum is $0$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We specialize the general rank-three Harborth bound hypothesis h to n = 6. The three numerical preconditions—that 6 ≤ 6, that 6 is even, and that 6 is not a power of 2—are discharged by direct arithmetic computation using `decide`. Since 8 * 6 - 7 = 41, applying h to the given multiset S of size 41 immediately yields the desired 6-element zero-sum submultiset.
Every multiset S of size 41 over (ZMod 6)³ contains a submultiset T of size 6 whose sum is 0. automation
Let S be a multiset of size 41 over (ZMod 6)³, with hypothesis hS asserting |S| = 41. We specialize the general hypothesis h to n = 6. This requires three preconditions: 6 ≤ 6, that 6 is even, and that 6 is not a power of 2. All three are decidable arithmetic statements closed automatically by `decide`. Since 8 * 6 - 7 = 41, the hypothesis hS supplies the required multiset cardinality, and h concludes that there is a zero-sum submultiset T ⊆ S of size 6.
theorem harborth_bound_equality_rank_three_implies_six (h : ∀ (n : ℕ), 6 ≤ n → Even n → ¬ n.isPowerOfTwo → ∀ (S : Multiset (Fin 3 → ZMod n)), S.card = 8 * n - 7 → ∃ T : Multiset (Fin 3 → ZMod n), T ≤ S ∧ T.card = n ∧ T.sum = 0) : ∀ (S : Multiset (Fin 3 → ZMod 6)), S.card = 41 → ∃ T : Multiset (Fin 3 → ZMod 6), T ≤ S ∧ T.card = 6 ∧ T.sum = 0 := fun S hS => h 6 (by decide) (by decide) (by decide) S hS
- The cardinality condition 8 * 6 - 7 = 41 holds definitionally in Lean, so the hypothesis S.card = 41 directly satisfies the cardinality requirement of h without requiring an explicit arithmetic rewrite.
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.
/-- The general rank-three Harborth bound equality implies the n = 6 case. -/theorem harborth_bound_equality_rank_three_implies_six (h : ∀ (n : ℕ), 6 ≤ n → Even n → ¬ n.isPowerOfTwo → ∀ (S : Multiset (Fin 3 → ZMod n)), S.card = 8 * n - 7 → ∃ T : Multiset (Fin 3 → ZMod n), T ≤ S ∧ T.card = n ∧ T.sum = 0) : ∀ (S : Multiset (Fin 3 → ZMod 6)), S.card = 41 → ∃ T : Multiset (Fin 3 → ZMod 6), T ≤ S ∧ T.card = 6 ∧ T.sum = 0 := fun S hS => h 6 (by decide) (by decide) (by decide) S hS