sumset_rep_count_le_choose_mul_choose
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
LinearOrderis aTotalPreorder. - 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 thanLinearOrder— 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).
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.
uses
dif_posopen 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]
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.
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_neprivate 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
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.
uses
sumset_rep_count_le_choose_mul_choose_sv_eq_orderEmb,sumset_rep_count_le_choose_mul_choose_sv_erase_eq,Fin.sum_univ_succAboveprivate 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]
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.
uses
Nat.cast_nonnegprivate 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
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`.
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
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.
uses
Finset.sum_nonpos,sumset_rep_count_le_choose_mul_choose_sum_vec_sumprivate 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
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.
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_memprivate 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
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).
uses
sumset_rep_count_le_choose_mul_choose_dot_succAbove,mul_left_cancel₀,Finset.insert_erase,Finset.card_le_card_of_injOnhave 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
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.
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
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).
uses
Sym.equivNatSumOfFintype,Fintype.card_le_of_injective,Sym.card_sym_eq_choose,Fintype.card_fin,Nat.choose_symmhave 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
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).
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_gthave 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
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.
uses
Finset.card_filter,Finset.sum_product,Finset.sum_le_sum,Finset.sum_const,smul_eq_mul,Nat.mul_le_mul_rightcalc 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.
- The Lean formalisation defines `sumset_finset_sorted_vector` with a conditional branch returning 0 if the set size does not match k, requiring initial helper lemmas to identify it with `orderEmbOfFin` before manipulating dot products.
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.
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