AFTD Auto-Formalizing Theoretical Domains

sumset_rep_count_le_choose_mul_choose

theoremverifiedformalization

For any k ≥ 1, h, q, and integer s, the representation count ν_q(s) is bounded above by (h + k choose k - 1) * (q choose k - 1).

Statement

theorem sumset_rep_count_le_choose_mul_choose (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ) :
    sumset_rep_count h k q s ≤ Nat.choose (h + k) (k - 1) * Nat.choose q (k - 1)
Formalizes
arXiv:2611.07303 Sec. 5.2, Question 3
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • sumset_rep_countFor natural numbers h, k, q and integer s, sumset_rep_count h k q s is the number of pairs (x, A) in (sumset_sum_vectors_finset (h + 1) k)…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • sumset_finset_sorted_vectorFor a natural number k and a finset A of integers, sumset_finset_sorted_vector k A is the vector in Fin k → ℤ whose entries are the…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • sumset_sum_vectors_finsetFor natural numbers h and k, the finite set sumset_sum_vectors_finset h k is the finset of all vectors x : Fin k → ℤ with components in…
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

For all natural numbers $k$, $h$, and $q$ such that $1 \le k$, and for every integer $s$, sumset_rep_count h k q s is less than or equal to $\binom{h + k}{k - 1} \binom{q}{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 representation count ν_q(s) is the number of pairs (x, A) of a non-negative integer vector x summing to h + 1 and an (n + 1)-element subset A ⊆ {1, ..., q} with sorted dot product x · A = s, where k = n + 1. Since ∑ x_i = h + 1 > 0 and each x_i ≥ 0, there is always an index i where x_i > 0. For each fixed x, removing the i-th element of A defines an injective map from the fiber {A : x · A = s} into the n-element subsets of {1, ..., q}, because the value of the removed element is uniquely determined by the dot product equation; hence each fiber has size at most (q choose n). The total number of valid vectors x is bounded by (h + n + 1 choose n) via the stars-and-bars bijection with symmetric powers. Summing the fiber bound over all vectors x yields the product bound (h + k choose k - 1) * (q choose k - 1).

  1. The sorted vector of any finite set A of integers of size k equals the canonical order embedding from Fin k to A.

    The definition of `sumset_finset_sorted_vector` branches on whether |A| = k. Since the hypothesis assumes |A| = k, `dif_pos` evaluates the conditional expression directly to the order embedding A.orderEmbOfFin.

    lines 1–6

    uses dif_pos

    open Finset
    
    private lemma sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb {k : ℕ} (A : Finset ℤ) (hA : A.card = k) :
        sumset_finset_sorted_vector k A = ⇑(A.orderEmbOfFin hA) := by
      funext i; rw [sumset_finset_sorted_vector, dif_pos hA]
    
  2. Erasing the i-th element of a sorted (n+1)-element set leaves an n-element set whose sorted vector is the original order embedding composed with i.succAbove.

    Let A have size n+1 and let a_i be its i-th element. Erasing a_i leaves a subset B of size n. The function j ↦ a_{succAbove_i(j)} maps Fin n into B because succAbove_i skips index i. Furthermore, it is strictly monotonic as a composition of order embeddings. By the uniqueness of the order-preserving bijection from Fin n onto B (`orderEmbOfFin_unique`), this composite function is the canonical order embedding of B.

    lines 7–20

    uses Finset.orderEmbOfFin_mem, Finset.card_erase_of_mem, sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb, Finset.orderEmbOfFin_unique, Finset.mem_erase, Fin.succAbove_ne

    private lemma sumset_rep_count_le_choose_mul_choose_sv_erase_eq {n : ℕ} (A : Finset ℤ) (hA : A.card = n + 1) (i : Fin (n+1)) :
        sumset_finset_sorted_vector n (A.erase (A.orderEmbOfFin hA i)) =
          fun j : Fin n => A.orderEmbOfFin hA (i.succAbove j) := by
      have h1 : A.orderEmbOfFin hA i ∈ A := Finset.orderEmbOfFin_mem A hA i
      have hB : (A.erase (A.orderEmbOfFin hA i)).card = n := by
        rw [Finset.card_erase_of_mem h1, hA]; simp
      rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb _ hB]
      refine (Finset.orderEmbOfFin_unique (s := A.erase (A.orderEmbOfFin hA i))
        (f := fun j : Fin n => A.orderEmbOfFin hA (i.succAbove j)) hB ?_ ?_).symm
      · intro j; rw [Finset.mem_erase]
        exact ⟨fun h => (Fin.succAbove_ne i j) ((A.orderEmbOfFin hA).injective h),
          Finset.orderEmbOfFin_mem A hA (i.succAbove j)⟩
      · exact (A.orderEmbOfFin hA).strictMono.comp (Fin.succAboveOrderEmb i).strictMono
    
  3. The dot product x · sorted(A) decomposes into x_i * a_i plus the dot product of x on the remaining indices with the sorted vector of A without a_i.

    Rewriting with the previous two lemmas identifies the sorted vectors with order embeddings. The dot product then becomes the sum ∑_j x_j a_j. Applying `Fin.sum_univ_succAbove` isolates the i-th term x_i * a_i, while the remaining terms form the dot product over the erased set.

    lines 21–30

    uses sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb, sumset_rep_count_le_choose_mul_choose_sv_erase_eq, Fin.sum_univ_succAbove

    private lemma sumset_rep_count_le_choose_mul_choose_dot_succAbove {n : ℕ} (x : Fin (n+1) → ℤ) (A : Finset ℤ) (hA : A.card = n+1) (i : Fin (n+1)) :
        dotProduct x (sumset_finset_sorted_vector (n+1) A) =
          x i * sumset_finset_sorted_vector (n+1) A i +
          dotProduct (fun j : Fin n => x (i.succAbove j))
            (sumset_finset_sorted_vector n (A.erase (sumset_finset_sorted_vector (n+1) A i))) := by
      rw [show sumset_finset_sorted_vector (n+1) A = ⇑(A.orderEmbOfFin hA) from sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb A hA,
        show sumset_finset_sorted_vector n (A.erase (A.orderEmbOfFin hA i)) =
          fun j : Fin n => A.orderEmbOfFin hA (i.succAbove j) from sumset_rep_count_le_choose_mul_choose_sv_erase_eq A hA i]
      simp only [dotProduct]; rw [Fin.sum_univ_succAbove _ i]
    
  4. Every coordinate of a vector in `sumset_sum_vectors_finset (h+1) k` is non-negative.

    By definition of `sumset_sum_vectors_finset`, each coordinate x_i is the integer cast of some natural number m from a bounded range. The cast of a natural number into ℤ is always non-negative.

    lines 31–36

    uses Nat.cast_nonneg

    private lemma sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg {k h : ℕ} {x : Fin k → ℤ} (hx : x ∈ sumset_sum_vectors_finset (h+1) k) (i : Fin k) : 0 ≤ x i := by
      simp only [sumset_sum_vectors_finset, Finset.mem_filter, Fintype.mem_piFinset, Finset.mem_image, Finset.mem_range] at hx
      rcases hx.1 i with ⟨m, -, hm⟩
      rw [← hm]
      exact Nat.cast_nonneg m
    
  5. The coordinates of any vector in `sumset_sum_vectors_finset (h+1) k` sum to h + 1.

    This is immediate from the filtering condition in the definition of `sumset_sum_vectors_finset (h+1) k`.

    lines 37–39

    private lemma sumset_rep_count_le_choose_mul_choose_sum_vec_sum {k h : ℕ} {x : Fin k → ℤ} (hx : x ∈ sumset_sum_vectors_finset (h+1) k) : ∑ i, x i = ((h:ℤ) + 1) := by
      simp only [sumset_sum_vectors_finset, Finset.mem_filter] at hx; rw [hx.2]; push_cast; ring
    
  6. Every vector in `sumset_sum_vectors_finset (h+1) k` has at least one strictly positive coordinate.

    Suppose, for contradiction, that x_i ≤ 0 for all i. Then the sum of all coordinates satisfies ∑_i x_i ≤ 0 by `Finset.sum_nonpos`. However, the sum is h + 1 ≥ 1, which contradicts ∑_i x_i ≤ 0. Therefore, at least one coordinate satisfies x_i > 0.

    lines 40–46

    uses Finset.sum_nonpos, sumset_rep_count_le_choose_mul_choose_sum_vec_sum

    private lemma sumset_rep_count_le_choose_mul_choose_sum_vec_exists_pos {k h : ℕ} {x : Fin k → ℤ} (hx : x ∈ sumset_sum_vectors_finset (h+1) k) : ∃ i, 0 < x i := by
      by_contra hcon; push Not at hcon
      have h1 : ∑ i, x i ≤ 0 := by
        have h2 := Finset.sum_nonpos (s := (Finset.univ : Finset (Fin k))) (f := x) (fun i _ => hcon i)
        simpa using h2
      have h2 := sumset_rep_count_le_choose_mul_choose_sum_vec_sum hx; linarith
    
  7. Erasing the i-th element maps the fiber F of subsets A with x · sorted(A) = s into the collection Z of n-element subsets of {1, ..., q}.

    Let Z be the collection of all n-element subsets of {1, ..., q}, which has cardinality (q choose n). For any (n+1)-element subset A ∈ F, removing the i-th element a_i leaves a subset g(A) = A \ {a_i} of size n contained in {1, ..., q}, so g(A) ∈ Z.

    lines 47–71

    uses Finset.card_powersetCard, Int.card_Icc, Int.toNat_natCast, Finset.mem_powersetCard, Finset.mem_of_mem_erase, Finset.orderEmbOfFin_mem, Finset.card_erase_of_mem

    private lemma sumset_rep_count_le_choose_mul_choose_filter_card_le_choose {n : ℕ} (x : Fin (n+1) → ℤ) (i : Fin (n+1))
        (hi : x i ≠ 0) (q : ℕ) (s : ℤ) :
        (((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter
          (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)).card ≤ Nat.choose q n := by
      classical
      set Z := (Finset.Icc 1 (q:ℤ)).powersetCard n with hZ
      have hZcard : Z.card = Nat.choose q n := by
        rw [hZ, Finset.card_powersetCard, Int.card_Icc]
        have h1 : (q:ℤ) + 1 - 1 = (q:ℤ) := by ring
        rw [h1, Int.toNat_natCast]
      let F := ((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter
          (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)
      let g : Finset ℤ → Finset ℤ := fun A => A.erase (sumset_finset_sorted_vector (n+1) A i)
      have hmaps : Set.MapsTo g ↑F ↑Z := by
        intro A hA
        simp only [Finset.mem_coe, F, Finset.mem_filter] at hA
        obtain ⟨hAY, -⟩ := hA
        rw [Finset.mem_powersetCard] at hAY
        show g A ∈ Z
        rw [hZ, Finset.mem_powersetCard]
        refine ⟨fun b hb => hAY.1 (Finset.mem_of_mem_erase hb), ?_⟩
        have hmemv : sumset_finset_sorted_vector (n+1) A i ∈ A := by
          rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb A hAY.2]; exact Finset.orderEmbOfFin_mem A hAY.2 i
        show (A.erase (sumset_finset_sorted_vector (n+1) A i)).card = n
        rw [Finset.card_erase_of_mem hmemv, hAY.2]; simp
  8. The map g is injective on F, implying |F| ≤ (q choose n).

    Assume g(A) = g(B), meaning A \ {a_i} = B \ {b_i}. Using the dot product decomposition, s = x_i a_i + dotProduct_rest(A) and s = x_i b_i + dotProduct_rest(B). Since the restricted sets are identical, the remaining dot products are equal, leaving x_i a_i = x_i b_i. Because x_i ≠ 0, left cancellation yields a_i = b_i. Reinserting this element into the identical erased sets gives A = B, establishing injectivity and hence |F| ≤ |Z| = (q choose n).

    lines 72–97

    uses sumset_rep_count_le_choose_mul_choose_dot_succAbove, mul_left_cancel₀, Finset.insert_erase, Finset.card_le_card_of_injOn

      have hinj : Set.InjOn g ↑F := by
        intro A hA B hB heq
        simp only [Finset.mem_coe, F, Finset.mem_filter] at hA hB
        obtain ⟨hAY, hAP⟩ := hA
        obtain ⟨hBY, hBP⟩ := hB
        rw [Finset.mem_powersetCard] at hAY hBY
        have heq2 : A.erase (sumset_finset_sorted_vector (n+1) A i) =
            B.erase (sumset_finset_sorted_vector (n+1) B i) := heq
        have dA := sumset_rep_count_le_choose_mul_choose_dot_succAbove x A hAY.2 i
        have dB := sumset_rep_count_le_choose_mul_choose_dot_succAbove x B hBY.2 i
        rw [dA] at hAP
        rw [dB] at hBP
        rw [heq2] at hAP
        have hkey : x i * sumset_finset_sorted_vector (n+1) A i =
            x i * sumset_finset_sorted_vector (n+1) B i := by linarith
        have hab : sumset_finset_sorted_vector (n+1) A i =
            sumset_finset_sorted_vector (n+1) B i := mul_left_cancel₀ hi hkey
        have hAm : sumset_finset_sorted_vector (n+1) A i ∈ A := by
          rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb A hAY.2]; exact Finset.orderEmbOfFin_mem A hAY.2 i
        have hBm : sumset_finset_sorted_vector (n+1) B i ∈ B := by
          rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb B hBY.2]; exact Finset.orderEmbOfFin_mem B hBY.2 i
        rw [← Finset.insert_erase hAm, ← Finset.insert_erase hBm, ← heq2, hab]
      have h := Finset.card_le_card_of_injOn g hmaps hinj
      rw [hZcard] at h
      exact h
    
  9. Writing k = n + 1, the sum of the natural conversions of the coordinates of any vector in the sum-vectors set equals h + 1.

    Since k ≥ 1, we write k = n + 1 with n = k - 1. Because all coordinates x_i are non-negative, each x_i equals its natural part (x_i).toNat. Thus the sum of natural numbers ∑_i (x_i).toNat equals the integer sum ∑_i x_i = h + 1.

    lines 98–112

    uses sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg, Finset.sum_congr, Int.toNat_of_nonneg, sumset_rep_count_le_choose_mul_choose_sum_vec_sum

    /-- Universal upper bound on sumset representation count ν_q(s) ≤ (h+k choose k-1) * (q choose k-1). -/
    theorem sumset_rep_count_le_choose_mul_choose (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ) :
        sumset_rep_count h k q s ≤ Nat.choose (h + k) (k - 1) * Nat.choose q (k - 1) := by
      classical
      obtain ⟨n, rfl⟩ : ∃ n, k = n + 1 := ⟨k - 1, by omega⟩
      have he : (n+1) - 1 = n := by omega
      rw [he]
      have hsum : ∀ x ∈ sumset_sum_vectors_finset (h+1) (n+1), ∑ i, (x i).toNat = h+1 := by
        intro x hx
        have h2 : ∀ i, 0 ≤ x i := fun i => sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg hx i
        have e2 : ((∑ i, (x i).toNat : ℕ) : ℤ) = ∑ i, x i := by
          push_cast
          exact Finset.sum_congr rfl fun i _ => Int.toNat_of_nonneg (h2 i)
        have h3 := e2.trans (sumset_rep_count_le_choose_mul_choose_sum_vec_sum hx)
        omega
  10. The number of sum-vectors in `sumset_sum_vectors_finset (h+1) (n+1)` is bounded above by (h + n + 1 choose n).

    Each vector x corresponds to a tuple of non-negative integers summing to h + 1, which is in bijection with the symmetric power Sym(Fin(n+1), h+1) via `Sym.equivNatSumOfFintype`. This assignment is injective, so the cardinality of the sum-vectors set is at most |Sym(Fin(n+1), h+1)| = ((n+1) + (h+1) - 1 choose h+1). By the symmetry of binomial coefficients, (h + n + 1 choose h + 1) = (h + n + 1 choose n).

    lines 113–135

    uses Sym.equivNatSumOfFintype, Fintype.card_le_of_injective, Sym.card_sym_eq_choose, Fintype.card_fin, Nat.choose_symm

      have hsub : (sumset_sum_vectors_finset (h+1) (n+1)).card ≤ (h + (n+1)).choose n := by
        set S := sumset_sum_vectors_finset (h+1) (n+1)
        let g : S → Sym (Fin (n+1)) (h+1) := fun x =>
          (Sym.equivNatSumOfFintype (Fin (n+1)) (h+1)).symm ⟨fun i => (x.1 i).toNat, hsum x.1 x.2⟩
        have hinj : Function.Injective g := by
          intro x y hxy
          have hh := congrArg (fun z => ((Sym.equivNatSumOfFintype (Fin (n+1)) (h+1)) z : Fin (n+1) → ℕ)) hxy
          simp only [g, Equiv.apply_symm_apply] at hh
          refine Subtype.ext (funext fun i => ?_)
          have h1 := congrFun hh i
          have hx' := sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg x.2 i
          have hy' := sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg y.2 i
          have hc : ((x.1 i).toNat : ℤ) = ((y.1 i).toNat : ℤ) := by rw [h1]
          rw [Int.toNat_of_nonneg hx', Int.toNat_of_nonneg hy'] at hc
          exact hc
        calc S.card = Fintype.card S := (Fintype.card_coe S).symm
          _ ≤ Fintype.card (Sym (Fin (n+1)) (h+1)) := Fintype.card_le_of_injective g hinj
          _ = ((n+1) + (h+1) - 1).choose (h+1) := by rw [Sym.card_sym_eq_choose, Fintype.card_fin]
          _ = (h + (n+1)).choose n := by
              have e1 : (n+1) + (h+1) - 1 = h + (n+1) := by omega
              rw [e1, ← Nat.choose_symm (show h + 1 ≤ h + (n+1) by omega)]
              congr 1
              omega
  11. Every sum-vector x has a fiber of subsets A whose size is bounded by (q choose n).

    Every sum-vector x has at least one coordinate x_i > 0, so x_i ≠ 0. Applying the fiber cardinality bound from the earlier lemma gives that the number of (n+1)-element subsets A with x · sorted(A) = s is at most (q choose n).

    lines 136–141

    uses sumset_rep_count_le_choose_mul_choose_sum_vec_exists_pos, sumset_rep_count_le_choose_mul_choose_filter_card_le_choose, ne_of_gt

      have hfiber : ∀ x ∈ sumset_sum_vectors_finset (h+1) (n+1),
          (((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter
            (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)).card ≤ Nat.choose q n := by
        intro x hx
        obtain ⟨i, hi⟩ := sumset_rep_count_le_choose_mul_choose_sum_vec_exists_pos hx
        exact sumset_rep_count_le_choose_mul_choose_filter_card_le_choose x i (ne_of_gt hi) q s
  12. The total representation count ν_q(s) is bounded by (h + k choose k - 1) * (q choose k - 1).

    By definition, ν_q(s) is the double sum over all sum-vectors x of the size of the fiber of A. Bounding each fiber by (q choose n) bounds the sum by |S| * (q choose n), where S is the sum-vectors set. Substituting the upper bound |S| ≤ (h + n + 1 choose n) completes the proof.

    lines 142–149

    uses Finset.card_filter, Finset.sum_product, Finset.sum_le_sum, Finset.sum_const, smul_eq_mul, Nat.mul_le_mul_right

      calc sumset_rep_count h (n+1) q s
          = ∑ x ∈ sumset_sum_vectors_finset (h+1) (n+1),
              (((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter
                (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)).card := by
            simp only [sumset_rep_count, Finset.card_filter, Finset.sum_product]
        _ ≤ ∑ x ∈ sumset_sum_vectors_finset (h+1) (n+1), Nat.choose q n := Finset.sum_le_sum hfiber
        _ = (sumset_sum_vectors_finset (h+1) (n+1)).card * Nat.choose q n := by rw [Finset.sum_const, smul_eq_mul]
        _ ≤ (h + (n+1)).choose n * Nat.choose q n := Nat.mul_le_mul_right _ hsub
dif_pos
A dependent if-then-else evaluates to its `then` branch when the condition is true.
Finset.orderEmbOfFin_mem
The values of the order embedding from Fin k into a finite set s of size k are elements of s.
Finset.card_erase_of_mem
Erasing an element from a finite set decreases its cardinality by 1.
sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb
The sorted vector of a finite set of size k equals the canonical order embedding of Fin k into the set.
Finset.orderEmbOfFin_unique
Any strictly monotonic function from Fin k onto a finite set s of size k equals the canonical order embedding.
Finset.mem_erase
An element belongs to s with b removed if and only if it belongs to s and is not equal to b.
Fin.succAbove_ne
The map succAbove p skips the index p, so its output is never equal to p.
sumset_rep_count_le_choose_mul_choose_sv_erase_eq
Removing the i-th element from a sorted (n+1)-element set results in the sorted n-element set obtained by composing the original order embedding with succAbove i.
Fin.sum_univ_succAbove
A sum over Fin (n+1) can be decomposed into the term at index x plus the sum over the remaining indices indexed via succAbove x.
Nat.cast_nonneg
The cast of any natural number into an ordered ring is non-negative.
Finset.sum_nonpos
A sum of non-positive elements in an ordered additive group is non-positive.
sumset_rep_count_le_choose_mul_choose_sum_vec_sum
The sum of the components of any vector in the sumset sum-vectors set equals h + 1.
Finset.card_powersetCard
The number of n-element subsets of a finite set s is given by the binomial coefficient (|s| choose n).
Int.card_Icc
The cardinality of the closed integer interval [a, b] is (b + 1 - a).toNat.
Int.toNat_natCast
Converting a natural number cast to an integer back to a natural number yields the original number.
Finset.mem_powersetCard
A set s belongs to the n-subsets of t if and only if s is a subset of t and has cardinality n.
Finset.mem_of_mem_erase
Any element of s with an element removed is an element of s.
sumset_rep_count_le_choose_mul_choose_dot_succAbove
The dot product of a vector x with the sorted vector of an (n+1)-element set A decomposes into x_i * a_i plus the dot product of x on the remaining indices with the sorted vector of A without a_i.
mul_left_cancel₀
In a structure with cancellation, multiplication by a non-zero element on the left can be cancelled.
Finset.insert_erase
Reinserting an element that was erased from a finite set recovers the original set.
Finset.card_le_card_of_injOn
If a function maps a finite set s into t and is injective on s, then |s| ≤ |t|.
sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg
Every coordinate of a vector in the sumset sum-vectors set is non-negative.
Finset.sum_congr
Two sums over identical finite sets are equal if the summands agree on every element.
Int.toNat_of_nonneg
The integer cast of the natural part of a non-negative integer is the integer itself.
Sym.equivNatSumOfFintype
Symmetric n-th powers of a finite type α are in bijection with functions from α to ℕ summing to n.
Fintype.card_le_of_injective
An injective map between finite types implies the cardinality of the domain is at most the cardinality of the codomain.
Sym.card_sym_eq_choose
The number of multisubsets of size k from a set of size m is given by ((m + k - 1) choose k).
Fintype.card_fin
The finite type Fin n has cardinality n.
Nat.choose_symm
Binomial coefficients satisfy the symmetry (n choose n - k) = (n choose k).
sumset_rep_count_le_choose_mul_choose_sum_vec_exists_pos
Every sum-vector has at least one strictly positive coordinate.
sumset_rep_count_le_choose_mul_choose_filter_card_le_choose
For any sum-vector with a non-zero coordinate, the number of (n+1)-subsets of [1, q] whose sorted dot product equals s is at most (q choose n).
ne_of_gt
A strictly greater element is not equal to the smaller element.
Finset.card_filter
The cardinality of a filtered subset equals the sum over the set of the indicator of the predicate.
Finset.sum_product
A sum over a Cartesian product of finite sets can be evaluated as an iterated sum.
Finset.sum_le_sum
A sum of smaller or equal terms is less than or equal to the sum of the larger terms.
Finset.sum_const
Summing a constant value b over a finite set s yields |s| • b.
smul_eq_mul
Scalar multiplication of natural numbers or rings is ordinary multiplication.
Nat.mul_le_mul_right
Multiplying both sides of an inequality of natural numbers by a constant on the right preserves the inequality.

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

open Finsetprivate lemma sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb {k : ℕ} (A : Finset ℤ) (hA : A.card = k) :    sumset_finset_sorted_vector k A = ⇑(A.orderEmbOfFin hA) := by  funext i; rw [sumset_finset_sorted_vector, dif_pos hA]private lemma sumset_rep_count_le_choose_mul_choose_sv_erase_eq {n : ℕ} (A : Finset ℤ) (hA : A.card = n + 1) (i : Fin (n+1)) :    sumset_finset_sorted_vector n (A.erase (A.orderEmbOfFin hA i)) =      fun j : Fin n => A.orderEmbOfFin hA (i.succAbove j) := by  have h1 : A.orderEmbOfFin hA i ∈ A := Finset.orderEmbOfFin_mem A hA i  have hB : (A.erase (A.orderEmbOfFin hA i)).card = n := by    rw [Finset.card_erase_of_mem h1, hA]; simp  rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb _ hB]  refine (Finset.orderEmbOfFin_unique (s := A.erase (A.orderEmbOfFin hA i))    (f := fun j : Fin n => A.orderEmbOfFin hA (i.succAbove j)) hB ?_ ?_).symm  · intro j; rw [Finset.mem_erase]    exact ⟨fun h => (Fin.succAbove_ne i j) ((A.orderEmbOfFin hA).injective h),      Finset.orderEmbOfFin_mem A hA (i.succAbove j)⟩  · exact (A.orderEmbOfFin hA).strictMono.comp (Fin.succAboveOrderEmb i).strictMonoprivate lemma sumset_rep_count_le_choose_mul_choose_dot_succAbove {n : ℕ} (x : Fin (n+1) → ℤ) (A : Finset ℤ) (hA : A.card = n+1) (i : Fin (n+1)) :    dotProduct x (sumset_finset_sorted_vector (n+1) A) =      x i * sumset_finset_sorted_vector (n+1) A i +      dotProduct (fun j : Fin n => x (i.succAbove j))        (sumset_finset_sorted_vector n (A.erase (sumset_finset_sorted_vector (n+1) A i))) := by  rw [show sumset_finset_sorted_vector (n+1) A = ⇑(A.orderEmbOfFin hA) from sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb A hA,    show sumset_finset_sorted_vector n (A.erase (A.orderEmbOfFin hA i)) =      fun j : Fin n => A.orderEmbOfFin hA (i.succAbove j) from sumset_rep_count_le_choose_mul_choose_sv_erase_eq A hA i]  simp only [dotProduct]; rw [Fin.sum_univ_succAbove _ i]private lemma sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg {k h : ℕ} {x : Fin k → ℤ} (hx : x ∈ sumset_sum_vectors_finset (h+1) k) (i : Fin k) : 0 ≤ x i := by  simp only [sumset_sum_vectors_finset, Finset.mem_filter, Fintype.mem_piFinset, Finset.mem_image, Finset.mem_range] at hx  rcases hx.1 i with ⟨m, -, hm⟩  rw [← hm]  exact Nat.cast_nonneg mprivate lemma sumset_rep_count_le_choose_mul_choose_sum_vec_sum {k h : ℕ} {x : Fin k → ℤ} (hx : x ∈ sumset_sum_vectors_finset (h+1) k) : ∑ i, x i = ((h:ℤ) + 1) := by  simp only [sumset_sum_vectors_finset, Finset.mem_filter] at hx; rw [hx.2]; push_cast; ringprivate lemma sumset_rep_count_le_choose_mul_choose_sum_vec_exists_pos {k h : ℕ} {x : Fin k → ℤ} (hx : x ∈ sumset_sum_vectors_finset (h+1) k) : ∃ i, 0 < x i := by  by_contra hcon; push Not at hcon  have h1 : ∑ i, x i ≤ 0 := by    have h2 := Finset.sum_nonpos (s := (Finset.univ : Finset (Fin k))) (f := x) (fun i _ => hcon i)    simpa using h2  have h2 := sumset_rep_count_le_choose_mul_choose_sum_vec_sum hx; linarithprivate lemma sumset_rep_count_le_choose_mul_choose_filter_card_le_choose {n : ℕ} (x : Fin (n+1) → ℤ) (i : Fin (n+1))    (hi : x i ≠ 0) (q : ℕ) (s : ℤ) :    (((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter      (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)).card ≤ Nat.choose q n := by  classical  set Z := (Finset.Icc 1 (q:ℤ)).powersetCard n with hZ  have hZcard : Z.card = Nat.choose q n := by    rw [hZ, Finset.card_powersetCard, Int.card_Icc]    have h1 : (q:ℤ) + 1 - 1 = (q:ℤ) := by ring    rw [h1, Int.toNat_natCast]  let F := ((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter      (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)  let g : Finset ℤ → Finset ℤ := fun A => A.erase (sumset_finset_sorted_vector (n+1) A i)  have hmaps : Set.MapsTo g ↑F ↑Z := by    intro A hA    simp only [Finset.mem_coe, F, Finset.mem_filter] at hA    obtain ⟨hAY, -⟩ := hA    rw [Finset.mem_powersetCard] at hAY    show g A ∈ Z    rw [hZ, Finset.mem_powersetCard]    refine ⟨fun b hb => hAY.1 (Finset.mem_of_mem_erase hb), ?_⟩    have hmemv : sumset_finset_sorted_vector (n+1) A i ∈ A := by      rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb A hAY.2]; exact Finset.orderEmbOfFin_mem A hAY.2 i    show (A.erase (sumset_finset_sorted_vector (n+1) A i)).card = n    rw [Finset.card_erase_of_mem hmemv, hAY.2]; simp  have hinj : Set.InjOn g ↑F := by    intro A hA B hB heq    simp only [Finset.mem_coe, F, Finset.mem_filter] at hA hB    obtain ⟨hAY, hAP⟩ := hA    obtain ⟨hBY, hBP⟩ := hB    rw [Finset.mem_powersetCard] at hAY hBY    have heq2 : A.erase (sumset_finset_sorted_vector (n+1) A i) =        B.erase (sumset_finset_sorted_vector (n+1) B i) := heq    have dA := sumset_rep_count_le_choose_mul_choose_dot_succAbove x A hAY.2 i    have dB := sumset_rep_count_le_choose_mul_choose_dot_succAbove x B hBY.2 i    rw [dA] at hAP    rw [dB] at hBP    rw [heq2] at hAP    have hkey : x i * sumset_finset_sorted_vector (n+1) A i =        x i * sumset_finset_sorted_vector (n+1) B i := by linarith    have hab : sumset_finset_sorted_vector (n+1) A i =        sumset_finset_sorted_vector (n+1) B i := mul_left_cancel₀ hi hkey    have hAm : sumset_finset_sorted_vector (n+1) A i ∈ A := by      rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb A hAY.2]; exact Finset.orderEmbOfFin_mem A hAY.2 i    have hBm : sumset_finset_sorted_vector (n+1) B i ∈ B := by      rw [sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb B hBY.2]; exact Finset.orderEmbOfFin_mem B hBY.2 i    rw [← Finset.insert_erase hAm, ← Finset.insert_erase hBm, ← heq2, hab]  have h := Finset.card_le_card_of_injOn g hmaps hinj  rw [hZcard] at h  exact h/-- Universal upper bound on sumset representation count ν_q(s) ≤ (h+k choose k-1) * (q choose k-1). -/theorem sumset_rep_count_le_choose_mul_choose (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ) :    sumset_rep_count h k q s ≤ Nat.choose (h + k) (k - 1) * Nat.choose q (k - 1) := by  classical  obtain ⟨n, rfl⟩ : ∃ n, k = n + 1 := ⟨k - 1, by omega⟩  have he : (n+1) - 1 = n := by omega  rw [he]  have hsum : ∀ x ∈ sumset_sum_vectors_finset (h+1) (n+1), ∑ i, (x i).toNat = h+1 := by    intro x hx    have h2 : ∀ i, 0 ≤ x i := fun i => sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg hx i    have e2 : ((∑ i, (x i).toNat : ℕ) : ℤ) = ∑ i, x i := by      push_cast      exact Finset.sum_congr rfl fun i _ => Int.toNat_of_nonneg (h2 i)    have h3 := e2.trans (sumset_rep_count_le_choose_mul_choose_sum_vec_sum hx)    omega  have hsub : (sumset_sum_vectors_finset (h+1) (n+1)).card ≤ (h + (n+1)).choose n := by    set S := sumset_sum_vectors_finset (h+1) (n+1)    let g : S → Sym (Fin (n+1)) (h+1) := fun x =>      (Sym.equivNatSumOfFintype (Fin (n+1)) (h+1)).symm ⟨fun i => (x.1 i).toNat, hsum x.1 x.2⟩    have hinj : Function.Injective g := by      intro x y hxy      have hh := congrArg (fun z => ((Sym.equivNatSumOfFintype (Fin (n+1)) (h+1)) z : Fin (n+1) → ℕ)) hxy      simp only [g, Equiv.apply_symm_apply] at hh      refine Subtype.ext (funext fun i => ?_)      have h1 := congrFun hh i      have hx' := sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg x.2 i      have hy' := sumset_rep_count_le_choose_mul_choose_sum_vec_nonneg y.2 i      have hc : ((x.1 i).toNat : ℤ) = ((y.1 i).toNat : ℤ) := by rw [h1]      rw [Int.toNat_of_nonneg hx', Int.toNat_of_nonneg hy'] at hc      exact hc    calc S.card = Fintype.card S := (Fintype.card_coe S).symm      _ ≤ Fintype.card (Sym (Fin (n+1)) (h+1)) := Fintype.card_le_of_injective g hinj      _ = ((n+1) + (h+1) - 1).choose (h+1) := by rw [Sym.card_sym_eq_choose, Fintype.card_fin]      _ = (h + (n+1)).choose n := by          have e1 : (n+1) + (h+1) - 1 = h + (n+1) := by omega          rw [e1, ← Nat.choose_symm (show h + 1 ≤ h + (n+1) by omega)]          congr 1          omega  have hfiber : ∀ x ∈ sumset_sum_vectors_finset (h+1) (n+1),      (((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter        (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)).card ≤ Nat.choose q n := by    intro x hx    obtain ⟨i, hi⟩ := sumset_rep_count_le_choose_mul_choose_sum_vec_exists_pos hx    exact sumset_rep_count_le_choose_mul_choose_filter_card_le_choose x i (ne_of_gt hi) q s  calc sumset_rep_count h (n+1) q s      = ∑ x ∈ sumset_sum_vectors_finset (h+1) (n+1),          (((Finset.Icc 1 (q:ℤ)).powersetCard (n+1)).filter            (fun A => dotProduct x (sumset_finset_sorted_vector (n+1) A) = s)).card := by        simp only [sumset_rep_count, Finset.card_filter, Finset.sum_product]    _ ≤ ∑ x ∈ sumset_sum_vectors_finset (h+1) (n+1), Nat.choose q n := Finset.sum_le_sum hfiber    _ = (sumset_sum_vectors_finset (h+1) (n+1)).card * Nat.choose q n := by rw [Finset.sum_const, smul_eq_mul]    _ ≤ (h + (n+1)).choose n * Nat.choose q n := Nat.mul_le_mul_right _ hsub
See it in the graphDiscuss this resultChallenge it