card_powersetCard_image_sum_ge
For any finite set A of natural numbers and any k ≤ |A|, the number of distinct sums of k-element subsets of A is at least k(|A| - k) + 1.
Statement
theorem card_powersetCard_image_sum_ge (A : Finset ℕ) (k : ℕ) (hk : k ≤ A.card) :
k * (A.card - k) + 1 ≤ ((A.powersetCard k).image (Finset.sum · id)).card- Source
- arXiv:2610.34372, Proof of Lemma 2.1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- admissible_card_sq_add_five_leIf A is a nonempty admissible subset of {1, ..., N}, then the square of the cardinality of A plus 5 is at most 6 times N.
Read back from the Lean
For every finite set of natural numbers $A$ and every natural number $k$ satisfying $k \le |A|$, the number of distinct sums formed by $k$-element subsets of $A$ (that is, the cardinality of the image of the collection of all $k$-subsets of $A$ under the function taking a subset to the sum of its elements) is at least $k(|A| - k) + 1$.
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 is proved by induction on the difference d = |A| - k. When d = 0, |A| = k and A is its own unique k-element subset, giving 1 sum which matches k · 0 + 1. For the inductive step with k > 0, removing the maximum element m from A yields a subset A' of size |A| - 1 with difference d, which produces at least kd + 1 subset sums by the induction hypothesis. Taking the k-element subset T of A' that attains the maximum sum M, replacing each element of T with m yields k new, distinct subset sums that are all strictly greater than M, thus providing k additional sums and completing the induction.
It suffices to prove the theorem parameterized by the difference d = |A| - k.
The statement is generalized by introducing a parameter d = |A| - k so that the proof can proceed by induction on d. Specializing d to |A| - k recovers the desired inequality.
open Finset in suffices ∀ (d : ℕ) (A : Finset ℕ) (k : ℕ) (hk : k ≤ A.card) (hd : A.card - k = d), k * (A.card - k) + 1 ≤ ((A.powersetCard k).image (Finset.sum · id)).card by exact this (A.card - k) A k hk rfl
The base case d = 0 holds: when |A| = k, the number of k-element subset sums is at least 1.
We induct on d. In the base case d = 0, the hypotheses k ≤ |A| and |A| - k = 0 force |A| = k. The only k-element subset of A is A itself (`Finset.powersetCard_self`), so there is exactly one subset sum (`Finset.image_singleton`, `Finset.card_singleton`). Since k(|A| - k) + 1 = k · 0 + 1 = 1, the inequality 1 ≤ 1 holds (`Nat.sub_self`, `mul_zero`, `zero_add`).
uses
Finset.powersetCard_self,Finset.image_singleton,Finset.card_singleton,Nat.sub_self,mul_zero,zero_addintro d induction d with | zero => intro A k hk hd have h_eq : A.card = k := by omega subst h_eq rw [Finset.powersetCard_self, Finset.image_singleton, Finset.card_singleton] rw [Nat.sub_self, mul_zero, zero_add]
In the induction step where |A| - k = d + 1, the claim holds when k = 0. automation
For the induction step, assume the claim holds for difference d, and let |A| - k = d + 1. If k = 0, the lower bound is 0 · (|A| - 0) + 1 = 1, while the empty set is the unique 0-element subset, having sum 0; simplification closes this case.
| succ d ih => intro A k hk hd by_cases hk0 : k = 0 · subst hk0 simpWhen k > 0, removing the maximum element m from A yields a subset A' = A ∖ {m} satisfying the induction hypothesis with difference d.
Since k ≠ 0, k is strictly positive (`Nat.pos_of_ne_zero`), which together with |A| - k = d + 1 implies |A| > 0, so A is nonempty (`Finset.card_pos.mp`). Let m = max(A) and define A' = A ∖ {m}. The cardinality of A' is |A| - 1 (`Finset.card_erase_of_mem`), satisfying k ≤ |A'| and |A'| - k = d. Thus the induction hypothesis applies to A', showing that A' has at least kd + 1 distinct k-element subset sums.
uses
Nat.pos_of_ne_zero,Finset.card_pos.mp,Finset.card_erase_of_memhave hk_pos : 0 < k := Nat.pos_of_ne_zero hk0 have hA_pos : 0 < A.card := by omega have hA_ne : A.Nonempty := Finset.card_pos.mp hA_pos set m := A.max' hA_ne have hmA : m ∈ A := A.max'_mem hA_ne set A' := A.erase m have hA'_card : A'.card = A.card - 1 := Finset.card_erase_of_mem hmA have hkA' : k ≤ A'.card := by omega have hd' : A'.card - k = d := by omega have h_ih := ih A' k hkA' hd'
The set S₁ of k-element subset sums from A' embeds into the k-element subset sums of A, and achieves a maximum sum M at some k-element subset T ⊆ A'.
Since A' ⊆ A (`Finset.erase_subset`), any k-element subset of A' is also a k-element subset of A (`Finset.powersetCard_mono`), so its sum lies in the subset sums of A (`Finset.image_subset_image`). Because k ≤ |A'|, the collection of k-subsets of A' is nonempty (`Finset.powersetCard_nonempty.mpr`), making S₁ nonempty. Let M = max(S₁); by definition, M is attained by some subset T ⊆ A' of size k (`Finset.mem_image`, `Finset.mem_powersetCard`), and every element of S₁ is at most M (`Finset.le_max'`).
uses
Finset.erase_subset,Finset.image_subset_image,Finset.powersetCard_mono,Finset.powersetCard_nonempty.mpr,Finset.mem_image,Finset.mem_powersetCard,Finset.le_max'have hA'_sub : A' ⊆ A := Finset.erase_subset m A set S₁ := (A'.powersetCard k).image (Finset.sum · id) have hS₁_sub : S₁ ⊆ (A.powersetCard k).image (Finset.sum · id) := Finset.image_subset_image (Finset.powersetCard_mono hA'_sub) have hne₁ : (A'.powersetCard k).Nonempty := Finset.powersetCard_nonempty.mpr hkA' have hS₁_ne : S₁.Nonempty := hne₁.image _ set M := S₁.max' hS₁_ne have hM_mem : M ∈ S₁ := S₁.max'_mem hS₁_ne rw [Finset.mem_image] at hM_mem rcases hM_mem with ⟨T, hT, hM_eq⟩ rw [Finset.mem_powersetCard] at hT have hT_sub : T ⊆ A' := hT.1 have hT_card : T.card = k := hT.2 have hM_le : ∀ s ∈ S₁, s ≤ M := fun s hs => Finset.le_max' S₁ s hs
The maximum element m does not belong to T, and every element of A' is strictly less than m.
Because m was removed from A to form A', m ∉ A' (`Finset.notMem_erase`), and since T ⊆ A', m ∉ T. Every x ∈ A' belongs to A (`Finset.mem_of_mem_erase`) with x ≠ m (`Finset.ne_of_mem_erase`). Since m is the maximum of A, x ≤ m (`Finset.le_max'`), so x < m (`lt_of_le_of_ne`).
uses
Finset.notMem_erase,Finset.mem_of_mem_erase,Finset.ne_of_mem_erase,lt_of_le_of_ne,Finset.le_max'have hm_notin_A' : m ∉ A' := Finset.notMem_erase m A have hm_notin_T : m ∉ T := fun h => hm_notin_A' (hT_sub h) have h_lt_m : ∀ x ∈ A', x < m := by intro x hx have hx_mem : x ∈ A := Finset.mem_of_mem_erase hx have hx_ne : x ≠ m := Finset.ne_of_mem_erase hx exact lt_of_le_of_ne (Finset.le_max' A x hx_mem) hx_ne
For each x ∈ T, replacing x with m gives a k-element subset Tx ⊆ A whose sum f(x) satisfies f(x) + x = M + m and f(x) > M.
For each x ∈ T, define Tx = (T ∖ {x}) ∪ {m}. Since m ∉ T, m ∉ T ∖ {x} (`Finset.mem_of_mem_erase`), so Tx ⊆ A has cardinality (|T| - 1) + 1 = k (`Finset.card_insert_of_notMem`, `Finset.card_erase_of_mem`). Its sum f(x) is m plus the sum of T ∖ {x} (`Finset.sum_insert`). Since adding x back restores the sum of T, which is M (`Finset.sum_erase_add`), we have f(x) + x = M + m. Because x ∈ T ⊆ A' implies x < m, it follows that f(x) = M + (m - x) > M.
uses
Finset.mem_of_mem_erase,Finset.card_insert_of_notMem,Finset.card_erase_of_mem,Finset.sum_insert,Finset.sum_erase_addlet Tx (x : ℕ) : Finset ℕ := insert m (T.erase x) let f (x : ℕ) : ℕ := (Tx x).sum id have h_sum_prop : ∀ x ∈ T, (Tx x) ⊆ A ∧ (Tx x).card = k ∧ f x + x = M + m ∧ M < f x := by intro x hx have hmTx : m ∉ T.erase x := fun h => hm_notin_T (Finset.mem_of_mem_erase h) have h1 : Tx x ⊆ A := by intro y hy rcases Finset.mem_insert.mp hy with rfl | hy · exact hmA · exact Finset.mem_of_mem_erase (hT_sub (Finset.mem_of_mem_erase hy)) have h2 : (Tx x).card = k := by dsimp [Tx] rw [Finset.card_insert_of_notMem hmTx, Finset.card_erase_of_mem hx, hT_card] omega have h_ins : (Tx x).sum id = m + (T.erase x).sum id := by dsimp [Tx] rw [Finset.sum_insert hmTx] rfl have h_erase : (T.erase x).sum id + x = T.sum id := Finset.sum_erase_add T id hx have h3 : f x + x = M + m := by dsimp [f] omega have hx_lt_m : x < m := h_lt_m x (hT_sub hx) have h4 : M < f x := by omega exact ⟨h1, h2, h3, h4⟩
The sum function f is injective on T.
If x, y ∈ T satisfy f(x) = f(y), then from f(x) + x = M + m = f(y) + y it follows that x = y.
have hf_inj : Set.InjOn f T := by intro x hx y hy hf_eq have hx_sum := (h_sum_prop x hx).2.2.1 have hy_sum := (h_sum_prop y hy).2.2.1 omega
The image set S₂ = f(T) has cardinality k.
Because f is injective on T (`Finset.card_image_of_injOn`) and |T| = k, the set of new sums S₂ has size exactly k.
uses
Finset.card_image_of_injOnset S₂ := T.image f have hS₂_card : S₂.card = k := by rw [Finset.card_image_of_injOn hf_inj, hT_card]
Every element of S₂ is the sum of a k-element subset of A.
Each s ∈ S₂ is f(x) for some x ∈ T (`Finset.mem_image`), which by construction is the sum of the k-element subset Tx ⊆ A (`Finset.mem_powersetCard`).
uses
Finset.mem_image,Finset.mem_powersetCardhave hS₂_sub : S₂ ⊆ (A.powersetCard k).image (Finset.sum · id) := by intro s hs rw [Finset.mem_image] at hs rcases hs with ⟨x, hx, rfl⟩ have hprop := h_sum_prop x hx rw [Finset.mem_image] refine ⟨Tx x, ?_, rfl⟩ rw [Finset.mem_powersetCard] exact ⟨hprop.1, hprop.2.1⟩
The sets S₁ and S₂ are disjoint.
To verify disjointness (`Finset.disjoint_left`), observe that any element of S₁ is at most M, whereas any element of S₂ is of the form f(y) for some y ∈ T (`Finset.mem_image`), which is strictly greater than M.
uses
Finset.disjoint_left,Finset.mem_imagehave h_disj : Disjoint S₁ S₂ := by rw [Finset.disjoint_left] intro x hx1 hx2 rw [Finset.mem_image] at hx2 rcases hx2 with ⟨y, hy, rfl⟩ have h1 := hM_le (f y) hx1 have h2 := (h_sum_prop y hy).2.2.2 omega
The total number of k-element subset sums of A is at least |S₁| + |S₂|.
Both S₁ and S₂ are subsets of the k-element subset sums of A, so their union is as well (`Finset.union_subset`), meaning |S₁ ∪ S₂| bounds the total count from below (`Finset.card_le_card`). Since S₁ and S₂ are disjoint, |S₁ ∪ S₂| = |S₁| + |S₂| (`Finset.card_union_of_disjoint`).
uses
Finset.union_subset,Finset.card_le_card,Finset.card_union_of_disjointhave h_union : S₁.card + S₂.card ≤ ((A.powersetCard k).image (Finset.sum · id)).card := by have h_sub : S₁ ∪ S₂ ⊆ (A.powersetCard k).image (Finset.sum · id) := Finset.union_subset hS₁_sub hS₂_sub have h_card := Finset.card_le_card h_sub rw [Finset.card_union_of_disjoint h_disj] at h_card exact h_card
The inductive step is complete: k(|A| - k) + 1 ≤ |(A.powersetCard k).image (Finset.sum · id)|. automation
By the induction hypothesis, |S₁| ≥ kd + 1, and we have |S₂| = k. Since |A| - k = d + 1, the total count is at least |S₁| + |S₂| ≥ (kd + 1) + k = k(d + 1) + 1 = k(|A| - k) + 1. Linear arithmetic closes the goal.
rw [hd] have h_split : k * (d + 1) = k * d + k := by ring rw [hd'] at h_ih omega
Finset.card_image_of_injOn- An injective function on a finite set preserves the cardinality of the set under taking its image.
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.card_le_card- If s ⊆ t, then the cardinality of s is at most the cardinality of t.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.card_singleton- A singleton set has cardinality 1.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.disjoint_left- Two sets are disjoint if and only if no element of the first set belongs to the second.
Finset.erase_subset- Erasing an element from a set yields a subset of the original set.
Finset.image_singleton- The image of a singleton under a function is the singleton of the image.
Finset.image_subset_image- If one set is contained in another, its image under a function is contained in the image of the other.
Finset.le_max'- Every element of a nonempty linearly ordered finite set is less than or equal to the maximum element of the set.
Finset.mem_image- An element is in the image of a set under f if and only if it is f(a) for some element a in the set.
Finset.mem_of_mem_erase- If an element is in s ∖ {a}, then it is in s.
Finset.mem_powersetCard- A set s is in the collection of n-element subsets of t if and only if s ⊆ t and |s| = n.
Finset.ne_of_mem_erase- Any element of s ∖ {a} is not equal to a.
Finset.notMem_erase- An element does not belong to the set obtained by removing that element.
Finset.powersetCard_mono- If s ⊆ t, then every n-element subset of s is also an n-element subset of t.
Finset.powersetCard_nonempty.mpr- If n ≤ |s|, then the collection of n-element subsets of s is nonempty.
Finset.powersetCard_self- The only subset of a finite set s having size |s| is s itself.
Finset.sum_erase_add- Adding the value at a to the sum over s ∖ {a} gives the sum over the entire set s.
Finset.sum_insert- The sum over a set with a new element inserted is the value at that element plus the sum over the original set.
Finset.union_subset- If two sets are both subsets of u, their union is also a subset of u.
lt_of_le_of_ne- If a ≤ b and a ≠ b, then a < b.
mul_zero- Multiplying any number by 0 gives 0.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
Nat.sub_self- Subtracting any natural number from itself yields 0.
zero_add- Adding 0 to any element leaves it unchanged.
- The base case handles |A| = k, while the degenerate case k = 0 in the induction step is dispatched by simplification (`simp`).
- The final step relies on integer linear arithmetic (`omega`) to combine the inductive hypothesis with the count of new subset sums.
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.
/-- For any finite set of integers and 0 <= k <= |A|, the number of k-element subset sums is at least k(|A| - k) + 1. -/theorem card_powersetCard_image_sum_ge (A : Finset ℕ) (k : ℕ) (hk : k ≤ A.card) : k * (A.card - k) + 1 ≤ ((A.powersetCard k).image (Finset.sum · id)).card := by open Finset in suffices ∀ (d : ℕ) (A : Finset ℕ) (k : ℕ) (hk : k ≤ A.card) (hd : A.card - k = d), k * (A.card - k) + 1 ≤ ((A.powersetCard k).image (Finset.sum · id)).card by exact this (A.card - k) A k hk rfl intro d induction d with | zero => intro A k hk hd have h_eq : A.card = k := by omega subst h_eq rw [Finset.powersetCard_self, Finset.image_singleton, Finset.card_singleton] rw [Nat.sub_self, mul_zero, zero_add] | succ d ih => intro A k hk hd by_cases hk0 : k = 0 · subst hk0 simp have hk_pos : 0 < k := Nat.pos_of_ne_zero hk0 have hA_pos : 0 < A.card := by omega have hA_ne : A.Nonempty := Finset.card_pos.mp hA_pos set m := A.max' hA_ne have hmA : m ∈ A := A.max'_mem hA_ne set A' := A.erase m have hA'_card : A'.card = A.card - 1 := Finset.card_erase_of_mem hmA have hkA' : k ≤ A'.card := by omega have hd' : A'.card - k = d := by omega have h_ih := ih A' k hkA' hd' have hA'_sub : A' ⊆ A := Finset.erase_subset m A set S₁ := (A'.powersetCard k).image (Finset.sum · id) have hS₁_sub : S₁ ⊆ (A.powersetCard k).image (Finset.sum · id) := Finset.image_subset_image (Finset.powersetCard_mono hA'_sub) have hne₁ : (A'.powersetCard k).Nonempty := Finset.powersetCard_nonempty.mpr hkA' have hS₁_ne : S₁.Nonempty := hne₁.image _ set M := S₁.max' hS₁_ne have hM_mem : M ∈ S₁ := S₁.max'_mem hS₁_ne rw [Finset.mem_image] at hM_mem rcases hM_mem with ⟨T, hT, hM_eq⟩ rw [Finset.mem_powersetCard] at hT have hT_sub : T ⊆ A' := hT.1 have hT_card : T.card = k := hT.2 have hM_le : ∀ s ∈ S₁, s ≤ M := fun s hs => Finset.le_max' S₁ s hs have hm_notin_A' : m ∉ A' := Finset.notMem_erase m A have hm_notin_T : m ∉ T := fun h => hm_notin_A' (hT_sub h) have h_lt_m : ∀ x ∈ A', x < m := by intro x hx have hx_mem : x ∈ A := Finset.mem_of_mem_erase hx have hx_ne : x ≠ m := Finset.ne_of_mem_erase hx exact lt_of_le_of_ne (Finset.le_max' A x hx_mem) hx_ne let Tx (x : ℕ) : Finset ℕ := insert m (T.erase x) let f (x : ℕ) : ℕ := (Tx x).sum id have h_sum_prop : ∀ x ∈ T, (Tx x) ⊆ A ∧ (Tx x).card = k ∧ f x + x = M + m ∧ M < f x := by intro x hx have hmTx : m ∉ T.erase x := fun h => hm_notin_T (Finset.mem_of_mem_erase h) have h1 : Tx x ⊆ A := by intro y hy rcases Finset.mem_insert.mp hy with rfl | hy · exact hmA · exact Finset.mem_of_mem_erase (hT_sub (Finset.mem_of_mem_erase hy)) have h2 : (Tx x).card = k := by dsimp [Tx] rw [Finset.card_insert_of_notMem hmTx, Finset.card_erase_of_mem hx, hT_card] omega have h_ins : (Tx x).sum id = m + (T.erase x).sum id := by dsimp [Tx] rw [Finset.sum_insert hmTx] rfl have h_erase : (T.erase x).sum id + x = T.sum id := Finset.sum_erase_add T id hx have h3 : f x + x = M + m := by dsimp [f] omega have hx_lt_m : x < m := h_lt_m x (hT_sub hx) have h4 : M < f x := by omega exact ⟨h1, h2, h3, h4⟩ have hf_inj : Set.InjOn f T := by intro x hx y hy hf_eq have hx_sum := (h_sum_prop x hx).2.2.1 have hy_sum := (h_sum_prop y hy).2.2.1 omega set S₂ := T.image f have hS₂_card : S₂.card = k := by rw [Finset.card_image_of_injOn hf_inj, hT_card] have hS₂_sub : S₂ ⊆ (A.powersetCard k).image (Finset.sum · id) := by intro s hs rw [Finset.mem_image] at hs rcases hs with ⟨x, hx, rfl⟩ have hprop := h_sum_prop x hx rw [Finset.mem_image] refine ⟨Tx x, ?_, rfl⟩ rw [Finset.mem_powersetCard] exact ⟨hprop.1, hprop.2.1⟩ have h_disj : Disjoint S₁ S₂ := by rw [Finset.disjoint_left] intro x hx1 hx2 rw [Finset.mem_image] at hx2 rcases hx2 with ⟨y, hy, rfl⟩ have h1 := hM_le (f y) hx1 have h2 := (h_sum_prop y hy).2.2.2 omega have h_union : S₁.card + S₂.card ≤ ((A.powersetCard k).image (Finset.sum · id)).card := by have h_sub : S₁ ∪ S₂ ⊆ (A.powersetCard k).image (Finset.sum · id) := Finset.union_subset hS₁_sub hS₂_sub have h_card := Finset.card_le_card h_sub rw [Finset.card_union_of_disjoint h_disj] at h_card exact h_card rw [hd] have h_split : k * (d + 1) = k * d + k := by ring rw [hd'] at h_ih omega