AFTD Auto-Formalizing Theoretical Domains

harborth_bound_equality_rank_three_implies_six

theoremverified

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.

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

    line 2

    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

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

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