subsequence_sums
def
For a natural number n and a multiset S of elements of an additive commutative monoid G with decidable equality, subsequence_sums n S is the finite set (Finset G) of all elements of G that can be written as the sum of a submultiset of S of cardinality n.
Statement
def subsequence_sums (n : ℕ) {G : Type*} [AddCommMonoid G] [DecidableEq G] (S : Multiset G) : Finset G
- Defined in
- arXiv:2610.35819 Section 8
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 3
- 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…
- 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…
- 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
Given a natural number n, an additive commutative monoid G with decidable equality, and a multiset S of elements of G, subsequence_sums n S is defined as the finite set (Finset G) of all sums of sub-multisets of S that have cardinality equal to n (that is, the set { ∑_{x ∈ U} x | U ≤ S, Multiset.card U = n }).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The finite set of sums of all length-n submultisets of a multiset S. -/ def subsequence_sums (n : ℕ) {G : Type*} [AddCommMonoid G] [DecidableEq G] (S : Multiset G) : Finset G := ((S.powerset.filter (fun U => U.card = n)).map Multiset.sum).toFinset