subsequence_sums_maximal_zero_sum_free_term_mul_pred_eq
Let G be a finite additive commutative group with decidable equality and exponent n (AddMonoid.exponent G = n). Let S be a multiset over G satisfying is_maximal_zero_sum_free n S. If some element t of G has multiplicity n - 1 in S (S.count t = n - 1), then the finite set of n-term subsequence sums of S equals the nonzero elements of G: subsequence_sums n S = (Finset.univ : Finset G) \ {0}.
Statement
theorem subsequence_sums_maximal_zero_sum_free_term_mul_pred_eq {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G] {n : ℕ} (hn : AddMonoid.exponent G = n) (S : Multiset G) (hS : is_maximal_zero_sum_free n S) {t : G} (ht : S.count t = n - 1) : subsequence_sums n S = (Finset.univ : Finset G) \ {0}
- Formalizes
- arXiv:2610.35819 Proposition 8.2
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- is_maximal_zero_sum_free_subsequence_sums_pred_eq_univLet 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…
- 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…
Read back from the Lean
Let $G$ be a finite additive abelian group with decidable equality, and let $n$ be a natural number such that the exponent of $G$ is $n$. Let $S$ be a multiset of elements of $G$ that is maximal $n$-zero-sum-free (meaning: $S$ contains no submultiset of size $n$ summing to $0$, but for every $x \in G$, the multiset $S + \{x\}$ contains a submultiset of size $n$ summing to $0$). Suppose there exists an element $t \in G$ whose multiplicity in $S$ is $n - 1$. Then the set of sums of all submultisets of $S$ of cardinality $n$ is equal to $G \setminus \{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
The theorem states that if S is a maximal n-zero-sum-free multiset in a finite abelian group G of exponent n, and some element t appears n - 1 times in S, then the n-term subsequence sums of S cover all nonzero elements of G, and only those. The zero sum is excluded by the definition of zero-sum-freeness. For any nonzero g, a prior result ensures that (n - 1)-term subsequence sums cover all of G, so g - t is the sum of an (n - 1)-element submultiset U of S. Crucially, U cannot consist entirely of n - 1 copies of t, as that would sum to (n - 1) • t = -t and force g = 0. Therefore, t appears at most n - 2 times in U, meaning we can adjoin one more copy of t to obtain an n-element submultiset U + {t} ≤ S whose sum is (g - t) + t = g.
1 ≤ n
Since G is a finite group, its exponent is strictly positive by AddMonoid.exponent_pos.mpr and AddMonoid.ExponentExists.of_finite. Since n is this exponent, linear arithmetic (omega) yields 1 ≤ n.
uses
AddMonoid.exponent_pos.mpr,AddMonoid.ExponentExists.of_finitehave hn1 : 1 ≤ n := by have h : 0 < AddMonoid.exponent G := AddMonoid.exponent_pos.mpr AddMonoid.ExponentExists.of_finite omega
n • t = 0
Because n is the exponent of G, multiplying any element t by n yields zero in G.
uses
AddMonoid.exponent_nsmul_eq_zerohave hnsmul : n • t = 0 := by rw [← hn] exact AddMonoid.exponent_nsmul_eq_zero t
(n - 1) • t = -t
Using n = (n - 1) + 1, we rewrite n • t as (n - 1) • t + t. Since n • t = 0, this sum is 0, so (n - 1) • t = -t.
uses
Nat.sub_add_cancel,add_nsmul,one_nsmul,eq_neg_of_add_eq_zero_lefthave hpred : (n - 1) • t = -t := by have h : n • t = (n - 1) • t + t := by conv_lhs => rw [show n = (n - 1) + 1 from (Nat.sub_add_cancel hn1).symm] rw [add_nsmul, one_nsmul] have h2 : (n - 1) • t + t = 0 := by rw [← h]; exact hnsmul exact eq_neg_of_add_eq_zero_left h2
Every element x ∈ G is the sum of an (n - 1)-element submultiset of S.
By is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ, the set of (n - 1)-term subsequence sums of the maximal zero-sum-free multiset S covers all of G. Thus every x ∈ G can be written as the sum of some U ≤ S with card U = n - 1.
uses
is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ,Finset.mem_univ,mem_subsequence_sumshave hmemuniv : ∀ x : G, ∃ U ≤ S, U.card = n - 1 ∧ U.sum = x := by intro x have h : x ∈ subsequence_sums (n - 1) S := by rw [is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ hn1 S hS] exact Finset.mem_univ x exact (mem_subsequence_sums S x).mp h
It suffices to show that for every g ∈ G, g is an n-term subsequence sum of S if and only if g ≠ 0.
By set extensionality and the definitions of set difference and subsequence sums, g belongs to Finset.univ \ {0} if and only if g ≠ 0, while belonging to subsequence_sums n S means g is the sum of an n-element submultiset of S.
uses
Finset.mem_sdiff,Finset.mem_singleton,Finset.mem_univ,true_and,mem_subsequence_sumsext g simp only [Finset.mem_sdiff, Finset.mem_singleton, Finset.mem_univ, true_and, mem_subsequence_sums] constructor
No n-term submultiset of S can sum to 0.
If an n-term submultiset U ≤ S had sum 0, it would be an n-term zero-sum subsequence, directly contradicting the first conjunct of the assumption that S is zero-sum-free (hS.1).
· rintro ⟨U, hUle, hUcard, hUsum⟩ hg0 apply hS.1 exact ⟨U, hUle, hUcard, by rw [hUsum, hg0]⟩Given g ≠ 0, there exists an (n - 1)-element submultiset U ≤ S with sum g - t, and U contains t at most n - 1 times.
We represent g - t as the sum of a submultiset U ≤ S of cardinality n - 1. Since U ≤ S, the count of t in U cannot exceed the count of t in S, which is n - 1.
uses
Multiset.le_iff_count.mp· intro hg0 obtain ⟨U, hUle, hUcard, hUsum⟩ := hmemuniv (g - t) have hUcount_le : U.count t ≤ n - 1 := by have h := (Multiset.le_iff_count.mp hUle) t rwa [ht] at h
The multiplicity of t in U cannot equal n - 1.
If t had multiplicity n - 1 in U, then because card U = n - 1, U would consist entirely of n - 1 copies of t. Its sum would then be (n - 1) • t = -t. But its sum is also g - t, which implies g - t = -t and hence g = 0, contradicting g ≠ 0.
uses
Multiset.filter_eq',Multiset.card_replicate,Multiset.eq_of_le_of_card_le,Multiset.filter_le,le_of_eq,Multiset.sum_replicate,congrArgby_cases hc : U.count t = n - 1 · exfalso apply hg0 have hcardf : (U.filter (fun x => x = t)).card = U.card := by rw [Multiset.filter_eq' U t, Multiset.card_replicate, hc, hUcard] have heq : U.filter (fun x => x = t) = U := Multiset.eq_of_le_of_card_le (Multiset.filter_le _ _) (le_of_eq hcardf.symm) have hUeq : U = Multiset.replicate (n - 1) t := by rw [← heq, Multiset.filter_eq' U t, hc] have hgt : g - t = -t := by rw [← hUsum, hUeq, Multiset.sum_replicate, hpred] have hg : g = 0 := by have := congrArg (· + t) hgt simpa using this exact hg
Adjoining t to U produces an n-element submultiset U + {t} ≤ S with sum g.
Since t appears at most n - 2 times in U, adding one copy of t gives a submultiset U + {t} ≤ S because the count of t in U + {t} is at most n - 1 = S.count t, while the counts of all other elements are unchanged. Its cardinality is (n - 1) + 1 = n, and its sum is (g - t) + t = g. This proves g is an n-term subsequence sum.
uses
Multiset.le_iff_count,Multiset.count_add,Multiset.count_singleton,if_pos,if_neg,Multiset.le_iff_count.mp,Multiset.card_add,Multiset.card_singleton,Multiset.sum_add,Multiset.sum_singleton,sub_add_cancel· have hlt : U.count t ≤ n - 2 := by omega refine ⟨U + {t}, ?_, ?_, ?_⟩ · rw [Multiset.le_iff_count] intro a rw [Multiset.count_add, Multiset.count_singleton] by_cases ha : a = t · subst ha rw [if_pos rfl, ht] omega · rw [if_neg ha] have h := (Multiset.le_iff_count.mp hUle) a simpa using h · rw [Multiset.card_add, Multiset.card_singleton, hUcard] omega · rw [Multiset.sum_add, Multiset.sum_singleton, hUsum, sub_add_cancel]
AddMonoid.exponent_pos.mpr- In an additive monoid with a finite exponent, the exponent is strictly positive.
AddMonoid.ExponentExists.of_finite- Every finite additive left-cancellation monoid has a well-defined exponent.
AddMonoid.exponent_nsmul_eq_zero- Multiplying any element of an additive monoid by its exponent gives zero: (exponent G) • g = 0.
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
add_nsmul- Scalar multiplication by natural numbers distributes over addition of scalars: (m + n) • a = m • a + n • a.
one_nsmul- Scalar multiplication by 1 is the identity: 1 • a = a.
eq_neg_of_add_eq_zero_left- In an additive group, if a + b = 0, then a = -b.
is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ- If S is a maximal n-zero-sum-free multiset in G with 1 ≤ n, then its (n - 1)-term subsequence sums cover the entire group G.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
mem_subsequence_sums- An element g belongs to subsequence_sums n S if and only if there is a submultiset U ≤ S of size n summing to g.
Finset.mem_sdiff- An element belongs to a set difference s \ t if and only if it belongs to s and not to t.
Finset.mem_singleton- An element b belongs to the singleton set {a} if and only if b = a.
true_and- The logical conjunction True ∧ p simplifies to p.
Multiset.le_iff_count.mp- If multiset s is contained in t, then the multiplicity of each element in s is at most its multiplicity in t.
Multiset.filter_eq'- Filtering a multiset for elements equal to b produces b replicated by its multiplicity.
Multiset.card_replicate- Replicating an element n times produces a multiset of cardinality n.
Multiset.eq_of_le_of_card_le- If multiset s ≤ t and |t| ≤ |s|, then s = t.
Multiset.filter_le- Filtering a multiset by a predicate yields a submultiset of the original multiset.
le_of_eq- If two elements are equal, then the first is less than or equal to the second.
Multiset.sum_replicate- The sum of n copies of an element a in an additive monoid is n • a.
congrArg- A function applied to equal arguments yields equal values (a = b implies f(a) = f(b)).
Multiset.le_iff_count- Multiset inclusion s ≤ t is equivalent to the multiplicity of every element in s being at most that in t.
Multiset.count_add- The count of an element in a sum of multisets s + t is the sum of its counts in s and in t.
Multiset.count_singleton- The count of a in the singleton multiset {b} is 1 if a = b and 0 otherwise.
if_pos- If condition c is true, then (if c then t else e) evaluates to t.
if_neg- If condition c is false, then (if c then t else e) evaluates to e.
Multiset.card_add- The cardinality of the sum of two multisets is the sum of their cardinalities: |s + t| = |s| + |t|.
Multiset.card_singleton- The cardinality of a singleton multiset {a} is 1.
Multiset.sum_add- The sum of elements in the sum of two multisets is the sum of their respective sums: ∑ (s + t) = ∑ s + ∑ t.
Multiset.sum_singleton- The sum of the single element in {a} is a.
sub_add_cancel- In an additive group, (a - b) + b = a.
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.
/-- If S is maximal without n-term zero-sums and has a term of multiplicity n - 1, its n-term sums cover all nonzero elements. -/theorem subsequence_sums_maximal_zero_sum_free_term_mul_pred_eq {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G] {n : ℕ} (hn : AddMonoid.exponent G = n) (S : Multiset G) (hS : is_maximal_zero_sum_free n S) {t : G} (ht : S.count t = n - 1) : subsequence_sums n S = (Finset.univ : Finset G) \ {0} := by have hn1 : 1 ≤ n := by have h : 0 < AddMonoid.exponent G := AddMonoid.exponent_pos.mpr AddMonoid.ExponentExists.of_finite omega have hnsmul : n • t = 0 := by rw [← hn] exact AddMonoid.exponent_nsmul_eq_zero t have hpred : (n - 1) • t = -t := by have h : n • t = (n - 1) • t + t := by conv_lhs => rw [show n = (n - 1) + 1 from (Nat.sub_add_cancel hn1).symm] rw [add_nsmul, one_nsmul] have h2 : (n - 1) • t + t = 0 := by rw [← h]; exact hnsmul exact eq_neg_of_add_eq_zero_left h2 have hmemuniv : ∀ x : G, ∃ U ≤ S, U.card = n - 1 ∧ U.sum = x := by intro x have h : x ∈ subsequence_sums (n - 1) S := by rw [is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ hn1 S hS] exact Finset.mem_univ x exact (mem_subsequence_sums S x).mp h ext g simp only [Finset.mem_sdiff, Finset.mem_singleton, Finset.mem_univ, true_and, mem_subsequence_sums] constructor · rintro ⟨U, hUle, hUcard, hUsum⟩ hg0 apply hS.1 exact ⟨U, hUle, hUcard, by rw [hUsum, hg0]⟩ · intro hg0 obtain ⟨U, hUle, hUcard, hUsum⟩ := hmemuniv (g - t) have hUcount_le : U.count t ≤ n - 1 := by have h := (Multiset.le_iff_count.mp hUle) t rwa [ht] at h by_cases hc : U.count t = n - 1 · exfalso apply hg0 have hcardf : (U.filter (fun x => x = t)).card = U.card := by rw [Multiset.filter_eq' U t, Multiset.card_replicate, hc, hUcard] have heq : U.filter (fun x => x = t) = U := Multiset.eq_of_le_of_card_le (Multiset.filter_le _ _) (le_of_eq hcardf.symm) have hUeq : U = Multiset.replicate (n - 1) t := by rw [← heq, Multiset.filter_eq' U t, hc] have hgt : g - t = -t := by rw [← hUsum, hUeq, Multiset.sum_replicate, hpred] have hg : g = 0 := by have := congrArg (· + t) hgt simpa using this exact hg · have hlt : U.count t ≤ n - 2 := by omega refine ⟨U + {t}, ?_, ?_, ?_⟩ · rw [Multiset.le_iff_count] intro a rw [Multiset.count_add, Multiset.count_singleton] by_cases ha : a = t · subst ha rw [if_pos rfl, ht] omega · rw [if_neg ha] have h := (Multiset.le_iff_count.mp hUle) a simpa using h · rw [Multiset.card_add, Multiset.card_singleton, hUcard] omega · rw [Multiset.sum_add, Multiset.sum_singleton, hUsum, sub_add_cancel]