AFTD Auto-Formalizing Theoretical Domains

is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ

theoremverifiedformalization

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

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.

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

    lines 6–9

    uses Finset.eq_univ_of_forall, mem_subsequence_sums

      obtain ⟨hno, hmax⟩ := hS
      apply Finset.eq_univ_of_forall
      intro g
      rw [mem_subsequence_sums]
  2. 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.

    line 10

      obtain ⟨W, hWle, hWcard, hWsum⟩ := hmax (-g)
  3. 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.

    lines 11–25

    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_neg

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

    lines 26–34

    uses Multiset.erase_le_erase, Multiset.count_erase_self, Multiset.count_add, Multiset.count_erase_of_ne

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

    lines 35–37

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

    lines 38–42

    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.

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

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