AFTD Auto-Formalizing Theoretical Domains

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

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