AFTD Auto-Formalizing Theoretical Domains

subsequence_sums_maximal_zero_sum_free_term_mul_pred_eq

theoremverifiedformalization

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

    lines 8–11

    uses AddMonoid.exponent_pos.mpr, AddMonoid.ExponentExists.of_finite

      have hn1 : 1 ≤ n := by
        have h : 0 < AddMonoid.exponent G :=
          AddMonoid.exponent_pos.mpr AddMonoid.ExponentExists.of_finite
        omega
  2. n • t = 0

    Because n is the exponent of G, multiplying any element t by n yields zero in G.

    lines 12–14

    uses AddMonoid.exponent_nsmul_eq_zero

      have hnsmul : n • t = 0 := by
        rw [← hn]
        exact AddMonoid.exponent_nsmul_eq_zero t
  3. (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.

    lines 15–20

    uses Nat.sub_add_cancel, add_nsmul, one_nsmul, eq_neg_of_add_eq_zero_left

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

    lines 21–26

    uses is_maximal_zero_sum_free_subsequence_sums_pred_eq_univ, Finset.mem_univ, mem_subsequence_sums

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

    lines 27–30

    uses Finset.mem_sdiff, Finset.mem_singleton, Finset.mem_univ, true_and, mem_subsequence_sums

      ext g
      simp only [Finset.mem_sdiff, Finset.mem_singleton, Finset.mem_univ, true_and,
        mem_subsequence_sums]
      constructor
  6. 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).

    lines 31–33

      · rintro ⟨U, hUle, hUcard, hUsum⟩ hg0
        apply hS.1
        exact ⟨U, hUle, hUcard, by rw [hUsum, hg0]⟩
  7. 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.

    lines 34–38

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

    lines 39–53

    uses Multiset.filter_eq', Multiset.card_replicate, Multiset.eq_of_le_of_card_le, Multiset.filter_le, le_of_eq, Multiset.sum_replicate, congrArg

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

    lines 54–68

    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

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