sumset_rep_count_eq_zero_of_gt
For any k ≥ 1, h, q, and integer s > (h + 1) * q, the representation count ν_q(s) is zero.
Statement
theorem sumset_rep_count_eq_zero_of_gt (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ)
(hs : ((h : ℤ) + 1) * (q : ℤ) < s) :
sumset_rep_count h k q s = 0- Formalizes
- arXiv:2611.07303 Proposition 5.7
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
Read back from the Lean
For all natural numbers $k$, $h$, and $q$ with $1 \le k$, and for every integer $s$, if $((h : \mathbb{Z}) + 1) \cdot (q : \mathbb{Z}) < s$, then sumset_rep_count h k q s = 0.
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 a k-element subset A ⊆ {1, ..., q} such that x · A = s. First, a helper lemma characterizes the coordinate vectors as non-negative integers summing to the target bound. In the main proof, since each element of A is bounded above by q and the coordinates of x are non-negative with sum h + 1, the dot product x · A is bounded by (h + 1) * q. Thus, no pair can achieve the sum s > (h + 1) * q, proving that the set of representations is empty and its count is zero.
In the helper lemma, any vector in `sumset_sum_vectors_finset h k` has coordinates satisfying 0 ≤ x i ≤ h.
Unfolding the definition of `sumset_sum_vectors_finset`, a vector x belongs to the set if each coordinate lies in the image of {0, ..., h} under the integer cast and the coordinates sum to h. Since both sides require ∑ x i = h, it suffices to check the coordinate bounds. For the forward direction, each coordinate x i is the cast of some natural number n < h + 1, which implies 0 ≤ x i ≤ h.
uses
Fintype.mem_piFinset,and_congr_left,Finset.mem_image,Finset.mem_rangeunfold sumset_sum_vectors_finset rw [Finset.mem_filter, Fintype.mem_piFinset] apply and_congr_left intro _ constructor · intro h1 i have hi := h1 i rw [Finset.mem_image] at hi obtain ⟨n, hn, heq⟩ := hi rw [Finset.mem_range] at hn rw [← heq] omega
Conversely, any vector whose coordinates satisfy 0 ≤ x i ≤ h has coordinates in the image of {0, ..., h}.
For the reverse implication, given 0 ≤ x i ≤ h, the non-negative integer x i is the cast of its natural number representation (x i).toNat. Because 0 ≤ x i ≤ h, this natural number is strictly less than h + 1, placing it in Finset.range (h + 1) as required.
uses
Finset.mem_image,Finset.mem_range· intro h1 i rw [Finset.mem_image] refine ⟨(x i).toNat, ?_, ?_⟩ · rw [Finset.mem_range] have := (h1 i).1 have := (h1 i).2 omega · have := (h1 i).1 omega
To show the representation count is zero, it suffices to derive a contradiction assuming there exists a pair (x, A) in the product set whose dot product equals s.
Unfolding `sumset_rep_count`, the count is defined as the cardinality of the filtered Cartesian product of sum vectors and k-element subsets of {1, ..., q}. Showing this cardinality is zero is equivalent to showing the filtered set is empty, which means no pair (x, A) satisfies the dot product equality x · A = s.
uses
Finset.card_eq_zero,Finset.filter_eq_empty_iffunfold sumset_rep_count rw [Finset.card_eq_zero] rw [Finset.filter_eq_empty_iff] rintro ⟨x, A⟩ hp simp only intro heq
The vector x has non-negative coordinates summing to h + 1, and A is a k-element subset of {1, ..., q}.
The assumed pair (x, A) belongs to the Cartesian product, so x is in `sumset_sum_vectors_finset (h + 1) k` and A is in `powersetCard k (Icc 1 q)`. By the helper lemma, x has non-negative entries summing to h + 1. By the definition of `powersetCard`, A is a subset of the interval [1, q] with cardinality k.
uses
Finset.mem_product,sumset_rep_count_eq_zero_of_gt_mem_vectors,Finset.mem_powersetCardrw [Finset.mem_product] at hp obtain ⟨hxb, hAb⟩ := hp rw [sumset_rep_count_eq_zero_of_gt_mem_vectors] at hxb obtain ⟨hx0, hxsum⟩ := hxb rw [Finset.mem_powersetCard] at hAb obtain ⟨hAS, hAcard⟩ := hAb
Every coordinate of the sorted vector of A is at most q.
The elements of the sorted vector are values of the order embedding of A. Since each such value belongs to A and A is contained in [1, q], every coordinate is bounded above by q.
uses
Finset.orderEmbOfFin_mem,Finset.mem_Icchave hbound : ∀ i : Fin k, A.orderEmbOfFin hAcard i ≤ (q : ℤ) := by intro i have hh := hAS (Finset.orderEmbOfFin_mem A hAcard i) rw [Finset.mem_Icc] at hh exact hh.2
The dot product of x with the sorted vector of A equals ∑ i, x i * A_i.
Because |A| = k, the sorted vector simplifies to the order embedding of A via `sumset_finset_sorted_vector`. Expanding the definition of `dotProduct` yields the sum of products coordinate by coordinate.
uses
sumset_rep_count_eq_zero_of_gt_sorted,dotProducthave hdot : dotProduct x (sumset_finset_sorted_vector k A) = ∑ i : Fin k, x i * A.orderEmbOfFin hAcard i := by rw [sumset_rep_count_eq_zero_of_gt_sorted k A hAcard] simp only [dotProduct]
The dot product of x with the sorted vector of A is at most (h + 1) * q.
Because x i ≥ 0 and each element A_i is at most q, each term x i * A_i is at most x i * q. Summing over all k coordinates gives ∑ i, x i * A_i ≤ ∑ i, x i * q = (∑ i, x i) * q = (h + 1) * q.
uses
Finset.sum_mul,Finset.sum_le_sum,mul_le_mul_of_nonneg_lefthave hle : dotProduct x (sumset_finset_sorted_vector k A) ≤ ((h : ℤ) + 1) * (q : ℤ) := by rw [hdot] have h1 : ∑ i : Fin k, x i * (q : ℤ) = ((h : ℤ) + 1) * (q : ℤ) := by rw [← Finset.sum_mul, hxsum]; push_cast; ring rw [← h1] apply Finset.sum_le_sum intro i _ exact mul_le_mul_of_nonneg_left (hbound i) (hx0 i).1
A contradiction is obtained, establishing that the representation count is zero. automation
We have established s = x · A ≤ (h + 1) * q, which directly contradicts the hypothesis s > (h + 1) * q. Linear arithmetic detects this contradiction and closes the goal.
omega
and_congr_left- To establish an equivalence between two conjunctions sharing the second conjunct, it suffices to prove the first conjuncts equivalent assuming the second.
dotProduct- The dot product of two vectors indexed by a finite type is the sum of coordinatewise products.
Finset.card_eq_zero- A finite set has cardinality zero if and only if it is empty.
Finset.filter_eq_empty_iff- The filter of a finite set by a predicate is empty if and only if no element of the set satisfies the predicate.
Finset.mem_Icc- An element belongs to a closed interval [a, b] if and only if it is between a and b inclusive.
Finset.mem_image- An element belongs to the image of a finite set under a function if and only if it is the image of some element of the set.
Finset.mem_powersetCard- A subset belongs to powersetCard n t if and only if it is a subset of t and has cardinality n.
Finset.mem_product- An ordered pair belongs to the Cartesian product of two finite sets if and only if its first coordinate belongs to the first set and its second belongs to the second.
Finset.mem_range- A natural number belongs to Finset.range n if and only if it is strictly less than n.
Finset.orderEmbOfFin_mem- Every element in the image of the order embedding of a finite set from Fin k belongs to the set.
Finset.sum_le_sum- If each term of one sum is bounded by the corresponding term of another over the same index set, the first sum is bounded by the second.
Finset.sum_mul- Multiplication on the right distributes over finite sums.
Fintype.mem_piFinset- A dependent function belongs to a Cartesian product of finite sets if and only if each coordinate belongs to the corresponding set.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality by a non-negative number preserves the inequality.
sumset_rep_count_eq_zero_of_gt_mem_vectors- A vector belongs to `sumset_sum_vectors_finset h k` if and only if all its coordinates are between 0 and h and their sum equals h.
sumset_rep_count_eq_zero_of_gt_sorted- If a finite set of integers A has cardinality k, its sorted vector representation equals the order embedding from Fin k into ℤ.
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.
lemma sumset_rep_count_eq_zero_of_gt_sorted (k : ℕ) (A : Finset ℤ) (hA : A.card = k) : sumset_finset_sorted_vector k A = ⇑(A.orderEmbOfFin hA) := dif_pos hAlemma sumset_rep_count_eq_zero_of_gt_mem_vectors (h k : ℕ) (x : Fin k → ℤ) : x ∈ sumset_sum_vectors_finset h k ↔ (∀ i : Fin k, 0 ≤ x i ∧ x i ≤ (h : ℤ)) ∧ ∑ i, x i = (h : ℤ) := by unfold sumset_sum_vectors_finset rw [Finset.mem_filter, Fintype.mem_piFinset] apply and_congr_left intro _ constructor · intro h1 i have hi := h1 i rw [Finset.mem_image] at hi obtain ⟨n, hn, heq⟩ := hi rw [Finset.mem_range] at hn rw [← heq] omega · intro h1 i rw [Finset.mem_image] refine ⟨(x i).toNat, ?_, ?_⟩ · rw [Finset.mem_range] have := (h1 i).1 have := (h1 i).2 omega · have := (h1 i).1 omega/-- The representation count ν_q(s) vanishes for s > (h + 1) * q. -/theorem sumset_rep_count_eq_zero_of_gt (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ) (hs : ((h : ℤ) + 1) * (q : ℤ) < s) : sumset_rep_count h k q s = 0 := by unfold sumset_rep_count rw [Finset.card_eq_zero] rw [Finset.filter_eq_empty_iff] rintro ⟨x, A⟩ hp simp only intro heq rw [Finset.mem_product] at hp obtain ⟨hxb, hAb⟩ := hp rw [sumset_rep_count_eq_zero_of_gt_mem_vectors] at hxb obtain ⟨hx0, hxsum⟩ := hxb rw [Finset.mem_powersetCard] at hAb obtain ⟨hAS, hAcard⟩ := hAb have hbound : ∀ i : Fin k, A.orderEmbOfFin hAcard i ≤ (q : ℤ) := by intro i have hh := hAS (Finset.orderEmbOfFin_mem A hAcard i) rw [Finset.mem_Icc] at hh exact hh.2 have hdot : dotProduct x (sumset_finset_sorted_vector k A) = ∑ i : Fin k, x i * A.orderEmbOfFin hAcard i := by rw [sumset_rep_count_eq_zero_of_gt_sorted k A hAcard] simp only [dotProduct] have hle : dotProduct x (sumset_finset_sorted_vector k A) ≤ ((h : ℤ) + 1) * (q : ℤ) := by rw [hdot] have h1 : ∑ i : Fin k, x i * (q : ℤ) = ((h : ℤ) + 1) * (q : ℤ) := by rw [← Finset.sum_mul, hxsum]; push_cast; ring rw [← h1] apply Finset.sum_le_sum intro i _ exact mul_le_mul_of_nonneg_left (hbound i) (hx0 i).1 omega