AFTD Auto-Formalizing Theoretical Domains

card_powersetCard_image_sum_ge

theoremverified

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.

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

    lines 4–7

      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
  2. 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`).

    lines 8–15

    uses Finset.powersetCard_self, Finset.image_singleton, Finset.card_singleton, Nat.sub_self, mul_zero, zero_add

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

    lines 16–20

      | succ d ih =>
        intro A k hk hd
        by_cases hk0 : k = 0
        · subst hk0
          simp
  4. When 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.

    lines 21–31

    uses Nat.pos_of_ne_zero, Finset.card_pos.mp, Finset.card_erase_of_mem

        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'
    
  5. 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'`).

    lines 32–46

    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
    
  6. 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`).

    lines 47–54

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

    lines 55–81

    uses Finset.mem_of_mem_erase, Finset.card_insert_of_notMem, Finset.card_erase_of_mem, Finset.sum_insert, Finset.sum_erase_add

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

    lines 82–87

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

    lines 88–91

    uses Finset.card_image_of_injOn

        set S₂ := T.image f
        have hS₂_card : S₂.card = k := by
          rw [Finset.card_image_of_injOn hf_inj, hT_card]
    
  10. 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`).

    lines 92–101

    uses Finset.mem_image, Finset.mem_powersetCard

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

    lines 102–110

    uses Finset.disjoint_left, Finset.mem_image

        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
    
  12. 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`).

    lines 111–116

    uses Finset.union_subset, Finset.card_le_card, Finset.card_union_of_disjoint

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

    lines 117–120

        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.

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

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