is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ
Let G be a finite additive commutative group with decidable equality, let n ≥ 1 be a natural number, and let S be a multiset over G satisfying is_maximal_zero_sum_free n S. Then the finite set of (n - 1)-term subsequence sums of S, subsequence_sums (n - 1) S, equals the universal set Finset.univ of G.
Statement
theorem is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G] {n : ℕ} (hn : 1 ≤ n) (S : Multiset G) (hS : is_maximal_zero_sum_free n S) : subsequence_sums (n - 1) S = (Finset.univ : Finset G)
- Formalizes
- arXiv:2610.35819 Section 8
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- subsequence_sumsFor a natural number n and a multiset S of elements of an additive commutative monoid G with decidable equality, subsequence_sums n S is…
- is_maximal_zero_sum_freeFor a natural number n, an additive commutative group G, and a multiset S of elements of G, is_maximal_zero_sum_free n S asserts that S…
- mem_subsequence_sumsGiven a natural number n, an additive commutative monoid G with decidable equality, a multiset S over G, and an element g of G, g belongs…
- Used by 1
- subsequence_sums_maximal_zero_sum_free_term_mul_pred_eqLet G be a finite additive commutative group with decidable equality and exponent n (AddMonoid.exponent G = n). Let S be a multiset over G…
Read back from the Lean
Let $G$ be a finite additive abelian group with decidable equality, and let $n \ge 1$ be a natural number. Let $S$ be a multiset of elements of $G$.
Assume that $S$ is maximal $n$-zero-sum-free, meaning:
1. There is no submultiset $W \le S$ with cardinality $n$ and sum $0$; and
2. For every $x \in G$, there exists a submultiset $W \le S + \{x\}$ with cardinality $n$ and sum $0$.
Then the set of sums of all submultisets of $S$ of cardinality $n - 1$ (subsequence_sums (n - 1) S) is equal to the universe of $G$ (Finset.univ). In other words, every element of $G$ can be written as the sum of an $(n-1)$-element submultiset of $S$.
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
To show that the (n - 1)-term subsequence sums of a maximal zero-sum-free multiset S cover all of G, we consider an arbitrary g ∈ G and use the maximality of S to obtain an n-term zero-sum sub-multiset W ≤ S + {-g}. Since S has no n-term zero-sums, W must contain the appended element -g. Removing -g leaves an (n - 1)-term sub-multiset W \ {-g} ≤ S whose sum is -(-g) = g, showing that every element of G is achieved.
To show that the (n - 1)-term subsequence sums cover all of G, it suffices to express an arbitrary element g ∈ G as the sum of an (n - 1)-term sub-multiset of S.
We split the hypothesis that S is maximal zero-sum-free into two parts: S contains no n-term zero-sums, and adding any element to S creates an n-term zero-sum. By Finset.eq_univ_of_forall, the set of subsequence sums equals the universal set if every g ∈ G belongs to it. By mem_subsequence_sums, membership of g means finding a sub-multiset U ≤ S with |U| = n - 1 and sum g.
uses
Finset.eq_univ_of_forall,mem_subsequence_sumsobtain ⟨hno, hmax⟩ := hS apply Finset.eq_univ_of_forall intro g rw [mem_subsequence_sums]
There exists an n-element sub-multiset W ≤ S + {-g} whose sum is 0.
Applying the maximality of S to the group element -g, we obtain an n-element sub-multiset W of S + {-g} with sum 0.
obtain ⟨W, hWle, hWcard, hWsum⟩ := hmax (-g)The element -g must belong to W.
Suppose for contradiction that -g ∉ W. By comparing multiplicities with Multiset.le_iff_count, W would be a sub-multiset of S: for any a ≠ -g, the multiplicity of a in S + {-g} equals that in S, and for a = -g, the multiplicity in W is 0 because -g ∉ W. Hence W ≤ S, which contradicts the hypothesis that S has no n-term zero-sum subsequence.
uses
Multiset.le_iff_count,Multiset.le_iff_count.mp,Multiset.count_add,Multiset.count_singleton,if_pos,Nat.add_zero,Multiset.count_eq_zero.mpr,Nat.zero_le,if_neghave hxmem : -g ∈ W := by by_contra hx apply hno refine ⟨W, ?_, hWcard, hWsum⟩ rw [Multiset.le_iff_count] intro a have h := (Multiset.le_iff_count.mp hWle) a rw [Multiset.count_add, Multiset.count_singleton] at h by_cases ha : a = -g · subst ha rw [if_pos rfl, Nat.add_zero] at h rw [Multiset.count_eq_zero.mpr hx] exact Nat.zero_le _ · rw [if_neg ha] at h simpa using h
Erasing -g from W yields a sub-multiset W \ {-g} ≤ S.
We choose W \ {-g} as our candidate subsequence. Erasing -g from both sides of W ≤ S + {-g} yields W \ {-g} ≤ (S + {-g}) \ {-g}. By comparing multiplicities for each element (distinguishing whether it equals -g or not), (S + {-g}) \ {-g} equals S, so W \ {-g} ≤ S.
uses
Multiset.erase_le_erase,Multiset.count_erase_self,Multiset.count_add,Multiset.count_erase_of_nerefine ⟨W.erase (-g), ?_, ?_, ?_⟩ · have h := Multiset.erase_le_erase (-g) hWle have h1 : (S + {-g}).erase (-g) = S := by ext a by_cases h' : a = -g · subst h' simp [Multiset.count_erase_self, Multiset.count_add] · simp [Multiset.count_erase_of_ne, h', Multiset.count_add] rwa [h1] at h
The cardinality of W \ {-g} is n - 1.
Since -g ∈ W, erasing it decreases the cardinality of W by 1, leaving n - 1 elements. Since n ≥ 1, n ≠ 0, so n is the successor of some natural number k, and its predecessor simplifies to n - 1.
uses
Multiset.card_erase_of_mem,Nat.exists_eq_succ_of_ne_zero· rw [Multiset.card_erase_of_mem hxmem, hWcard] obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0) simp
The sum of the elements in W \ {-g} is g.
By Multiset.sum_erase, the sum of W decomposes as -g + ∑ (W \ {-g}). Since ∑ W = 0, we have ∑ (W \ {-g}) + (-g) = 0, which implies that ∑ (W \ {-g}) = -(-g) = g.
uses
Multiset.sum_erase,add_comm,eq_neg_of_add_eq_zero_left· have h := Multiset.sum_erase hxmem rw [hWsum] at h have h2 : (W.erase (-g)).sum + (-g) = 0 := by rw [add_comm]; exact h have : (W.erase (-g)).sum = -(-g) := eq_neg_of_add_eq_zero_left h2 simpa using this
Finset.eq_univ_of_forall- A finite subset contains every element of a finite type if and only if it equals the universal set.
mem_subsequence_sums- An element belongs to the set of n-term subsequence sums of a multiset if and only if it is the sum of some n-element sub-multiset.
Multiset.le_iff_count- A multiset is a sub-multiset of another if and only if each element has multiplicity in the first at most its multiplicity in the second.
Multiset.le_iff_count.mp- If a multiset is a sub-multiset of another, then the multiplicity of any element in the first is at most its multiplicity in the second.
Multiset.count_add- The multiplicity of an element in the sum of two multisets is the sum of its multiplicities in each.
Multiset.count_singleton- The multiplicity of an element a in the singleton multiset {b} is 1 if a = b and 0 otherwise.
if_pos- If a condition c holds, then the conditional expression if c then t else e evaluates to t.
Nat.add_zero- Adding zero to any natural number leaves it unchanged.
Multiset.count_eq_zero.mpr- If an element does not belong to a multiset, its multiplicity in that multiset is 0.
Nat.zero_le- Zero is less than or equal to every natural number.
if_neg- If a condition c does not hold, then the conditional expression if c then t else e evaluates to e.
Multiset.erase_le_erase- Erasing an element from both sides of a multiset inequality preserves the inequality.
Multiset.count_erase_self- Erasing an occurrence of an element from a multiset decreases its multiplicity by 1.
Multiset.count_erase_of_ne- Erasing an element distinct from a does not change the multiplicity of a in the multiset.
Multiset.card_erase_of_mem- Erasing an element from a multiset decreases its cardinality by 1.
Nat.exists_eq_succ_of_ne_zero- Every nonzero natural number is the successor of some natural number.
Multiset.sum_erase- The sum of a multiset equals any of its elements plus the sum of the multiset obtained by erasing that element.
add_comm- Addition in an additive commutative group is commutative.
eq_neg_of_add_eq_zero_left- If the sum of two elements is zero, the first equals the negation of the second.
- Proving that (S + {-g}) \ {-g} = S requires an elementwise case-split on whether an element equals -g to verify equality of multiplicities, which is mathematically immediate.
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.
/-- A maximal sequence without n-term zero-sums covers all elements as (n-1)-term subsequence sums. -/theorem is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G] {n : ℕ} (hn : 1 ≤ n) (S : Multiset G) (hS : is_maximal_zero_sum_free n S) : subsequence_sums (n - 1) S = (Finset.univ : Finset G) := by obtain ⟨hno, hmax⟩ := hS apply Finset.eq_univ_of_forall intro g rw [mem_subsequence_sums] obtain ⟨W, hWle, hWcard, hWsum⟩ := hmax (-g) have hxmem : -g ∈ W := by by_contra hx apply hno refine ⟨W, ?_, hWcard, hWsum⟩ rw [Multiset.le_iff_count] intro a have h := (Multiset.le_iff_count.mp hWle) a rw [Multiset.count_add, Multiset.count_singleton] at h by_cases ha : a = -g · subst ha rw [if_pos rfl, Nat.add_zero] at h rw [Multiset.count_eq_zero.mpr hx] exact Nat.zero_le _ · rw [if_neg ha] at h simpa using h refine ⟨W.erase (-g), ?_, ?_, ?_⟩ · have h := Multiset.erase_le_erase (-g) hWle have h1 : (S + {-g}).erase (-g) = S := by ext a by_cases h' : a = -g · subst h' simp [Multiset.count_erase_self, Multiset.count_add] · simp [Multiset.count_erase_of_ne, h', Multiset.count_add] rwa [h1] at h · rw [Multiset.card_erase_of_mem hxmem, hWcard] obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0) simp · have h := Multiset.sum_erase hxmem rw [hWsum] at h have h2 : (W.erase (-g)).sum + (-g) = 0 := by rw [add_comm]; exact h have : (W.erase (-g)).sum = -(-g) := eq_neg_of_add_eq_zero_left h2 simpa using this