mem_subsequence_sums
Given 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 to the finite set subsequence_sums n S if and only if there exists a submultiset U ≤ S with card U = n and sum U = g.
Statement
theorem mem_subsequence_sums {n : ℕ} {G : Type*} [AddCommMonoid G] [DecidableEq G] (S : Multiset G) (g : G) : g ∈ subsequence_sums n S ↔ ∃ U ≤ S, U.card = n ∧ U.sum = g
- Source
- arXiv:2610.35819 Section 8
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 2
- 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
For a natural number $n$, an additive commutative monoid $G$ with decidable equality, a multiset $S$ of elements of $G$, and an element $g \in G$, $g \in \text{subsequence\_sums}(n, S)$ if and only if there exists a multiset $U$ such that $U \le S$ (i.e., $U$ is a submultiset of $S$), the cardinality of $U$ is $n$ ($U.\text{card} = n$), and the sum of the elements of $U$ is $g$ ($U.\text{sum} = g$).
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 proof unfolds the definition of `subsequence_sums n S` as the finite set of sums of submultisets of $S$ with cardinality $n$. It rewrites membership in the finite set and multiset image into the existence of a multiset in the filtered powerset with sum $g$. Finally, it unpacks the powerset and filter conditions into $U \le S$ with $\operatorname{card}(U) = n$, completing the equivalence by regrouping conjunctions.
Membership of $g$ in `subsequence_sums n S` is equivalent to the existence of a multiset in the filtered powerset of $S$ whose sum is $g$.
Unfolding the definition of `subsequence_sums` reveals that it is constructed by taking the powerset of $S$, filtering for submultisets of cardinality $n$, mapping the multiset sum over them, and converting the resulting multiset to a `Finset`. Rewriting with `Multiset.mem_toFinset` converts membership in the finite set to membership in the multiset image, and `Multiset.mem_map` turns this into the existence of an element $a$ in the filtered powerset such that $\operatorname{sum}(a) = g$.
uses
Multiset.mem_toFinset,Multiset.mem_mapunfold subsequence_sums rw [Multiset.mem_toFinset, Multiset.mem_map]
Membership of $a$ in the filtered powerset of $S$ is equivalent to $a ≤ S$ and $\operatorname{card}(a) = n$.
Simplifying with `Multiset.mem_filter` and `Multiset.mem_powerset` unpacks the condition: an element $a$ belongs to `Multiset.filter (·.card = n) S.powerset` if and only if $a \in S.\text{powerset}$ and $\operatorname{card}(a) = n$, where $a \in S.\text{powerset}$ is equivalent to $a \le S$. The existential statement becomes $\exists a, (a \le S \land \operatorname{card}(a) = n) \land \operatorname{sum}(a) = g$.
uses
Multiset.mem_filter,Multiset.mem_powersetsimp only [Multiset.mem_filter, Multiset.mem_powerset]The existential statement is equivalent to $\exists U \le S, \operatorname{card}(U) = n \land \operatorname{sum}(U) = g$.
The goal is closed by showing that the two existential statements are logically equivalent: unpacking the conjunction $(a \le S \land \operatorname{card}(a) = n) \land \operatorname{sum}(a) = g$ into its three conjuncts and regrouping them as $a \le S \land (\operatorname{card}(a) = n \land \operatorname{sum}(a) = g)$ gives the desired bi-implication.
exact ⟨fun ⟨U, ⟨hU, hc⟩, hs⟩ => ⟨U, hU, hc, hs⟩, fun ⟨U, hU, hc, hs⟩ => ⟨U, ⟨hU, hc⟩, hs⟩⟩
Multiset.mem_toFinset- An element belongs to the finite set `s.toFinset` if and only if it belongs to the multiset `s`.
Multiset.mem_map- An element `b` belongs to the multiset image `Multiset.map f s` if and only if there exists an element `a ∈ s` such that `f a = b`.
Multiset.mem_filter- An element belongs to `Multiset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Multiset.mem_powerset- A multiset `s` belongs to the powerset of `t` if and only if `s` is a submultiset of `t` (`s ≤ t`).
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.
/-- Membership in subsequence_sums n S is equivalent to the existence of a length-n submultiset with sum g. -/theorem mem_subsequence_sums {n : ℕ} {G : Type*} [AddCommMonoid G] [DecidableEq G] (S : Multiset G) (g : G) : g ∈ subsequence_sums n S ↔ ∃ U ≤ S, U.card = n ∧ U.sum = g := by unfold subsequence_sums rw [Multiset.mem_toFinset, Multiset.mem_map] simp only [Multiset.mem_filter, Multiset.mem_powerset] exact ⟨fun ⟨U, ⟨hU, hc⟩, hs⟩ => ⟨U, hU, hc, hs⟩, fun ⟨U, hU, hc, hs⟩ => ⟨U, ⟨hU, hc⟩, hs⟩⟩