sumset_rep_count_eq_zero_of_lt
For any k ≥ 1, h, q, and integer s < h + 1, the representation count ν_q(s) is zero.
Statement
theorem sumset_rep_count_eq_zero_of_lt (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ)
(hs : s < (h : ℤ) + 1) :
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$, given the hypothesis that $1 \le k$, and for all integers $s$, given the hypothesis that $s < (h : ℤ) + 1$ (strictly), the count sumset_rep_count h k q s is equal to $0$.
Here, sumset_rep_count h k q s counts the number of pairs $(x, A)$ such that:
1. $x : \text{Fin } k \to \mathbb{Z}$ is a vector with non-negative integer components $x_i \in \{0, 1, \dots, h + 1\}$ whose sum $\sum_{i=0}^{k-1} x_i$ equals $h + 1$;
2. $A \subseteq \{1, \dots, q\}$ is a set of integers of cardinality $k$;
3. The dot product of $x$ with the elements of $A$ sorted in strictly increasing order equals $s$.
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) counts pairs (x, A) of a coefficient vector x with non-negative entries summing to h + 1 and a k-element subset A ⊆ {1, ..., q}, such that the dot product x · A equals s. Because each element of A is at least 1 and every coordinate of x is non-negative, each term satisfies x_i * A_i ≥ x_i, so the dot product is at least the sum of the coordinates, h + 1. Consequently, no such pair can satisfy x · A = s when s < h + 1, making the set of representations empty and the count zero.
Membership in sumset_sum_vectors_finset h k reduces to each coordinate lying in the integer image of {0, ..., h} and summing to h.
Unfolding the definition of sumset_sum_vectors_finset as a filtered product of sets over coordinates, we split the if-and-only-if statement into the two directions.
uses
Finset.mem_filter,Fintype.mem_piFinsetunfold sumset_sum_vectors_finset rw [Finset.mem_filter, Fintype.mem_piFinset] constructor
If x is in sumset_sum_vectors_finset h k, then 0 ≤ x_i ≤ h for each coordinate i and ∑ x_i = h.
Each coordinate x_i is by assumption the image of a natural number n < h + 1, so 0 ≤ n ≤ h, meaning 0 ≤ x_i ≤ h. The sum condition holds directly.
uses
Finset.mem_image,Finset.mem_range· rintro ⟨h1, h2⟩ refine ⟨fun i => ?_, h2⟩ have := h1 i simp only [Finset.mem_image, Finset.mem_range] at this obtain ⟨n, hn, heq⟩ := this rw [← heq]; constructor <;> omegaConversely, if 0 ≤ x_i ≤ h for all i and ∑ x_i = h, then x is in sumset_sum_vectors_finset h k.
For each coordinate i, since 0 ≤ x_i ≤ h, its conversion to a natural number (x_i).toNat is strictly less than h + 1 and casts back to x_i, showing x_i is in the image of {0, ..., h}.
uses
Finset.mem_image,Finset.mem_range· rintro ⟨h1, h2⟩ refine ⟨fun i => ?_, h2⟩ obtain ⟨h0, hle⟩ := h1 i simp only [Finset.mem_image, Finset.mem_range] exact ⟨(x i).toNat, by omega, by omega⟩For any finite set A of cardinality k, its sorted vector representation equals its order embedding.
Unfolding the definition of sumset_finset_sorted_vector, the condition |A| = k is satisfied, so the if-then-else expression evaluates to the order embedding A.orderEmbOfFin.
uses
dif_posunfold sumset_finset_sorted_vector rw [dif_pos hA]
To show the representation count ν_q(s) is zero, it suffices to show no pair (x, A) satisfies x · A = s.
By definition, ν_q(s) is the cardinality of the filtered set of pairs (x, A) such that x · A = s. The cardinality is zero if and only if the set is empty, which means no valid pair satisfies this condition.
uses
Finset.card_eq_zero,Finset.filter_eq_empty_iffunfold sumset_rep_count rw [Finset.card_eq_zero] rw [Finset.filter_eq_empty_iff]
Suppose (x, A) satisfies x · A = s; then x has non-negative entries summing to h + 1, and A is a k-element subset of [1, q].
Assuming for contradiction that x · A = s, we unpack membership of (x, A) in the Cartesian product: x belongs to sumset_sum_vectors_finset (h + 1) k (so its coordinates are non-negative and sum to h + 1) and A is a k-element subset of the interval [1, q].
uses
Finset.mem_product,sumset_rep_count_eq_zero_of_lt_aux_mem_vectors,Finset.mem_powersetCardrintro ⟨x, A⟩ hp simp only intro heq rw [Finset.mem_product] at hp obtain ⟨hxb, hAb⟩ := hp rw [sumset_rep_count_eq_zero_of_lt_aux_mem_vectors] at hxb obtain ⟨hx0, hxsum⟩ := hxb rw [Finset.mem_powersetCard] at hAb obtain ⟨hAS, hAcard⟩ := hAb
Each entry of the sorted vector representing A is at least 1.
Each coordinate of the order embedding belongs to A. Since A is a subset of the interval [1, q], every element of A is at least 1.
uses
Finset.orderEmbOfFin_mem,Finset.mem_Icchave hbound : ∀ i : Fin k, (1 : ℤ) ≤ A.orderEmbOfFin hAcard i := by intro i have hh := hAS (Finset.orderEmbOfFin_mem A hAcard i) rw [Finset.mem_Icc] at hh exact hh.1
The dot product x · A equals the sum ∑ x_i * A_i.
Replacing the sorted vector of A with its order embedding via the auxiliary lemma, the dot product simplifies to the sum over all coordinates of x_i * A_i.
uses
sumset_rep_count_eq_zero_of_lt_aux_sortedhave 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_lt_aux_sorted k A hAcard] simp only [dotProduct]
The dot product x · A is at least h + 1.
Since each x_i ≥ 0 and each A_i ≥ 1, each term satisfies x_i ≤ x_i * A_i. Summing these inequalities gives ∑ x_i ≤ ∑ x_i * A_i. Since the coordinates of x sum to h + 1, the dot product is at least h + 1.
uses
Finset.sum_le_sum,mul_le_mul_of_nonneg_lefthave hge : (h : ℤ) + 1 ≤ dotProduct x (sumset_finset_sorted_vector k A) := by rw [hdot] have h1 : ∑ i : Fin k, x i = (h : ℤ) + 1 := by rw [hxsum]; push_cast; ring rw [← h1] apply Finset.sum_le_sum intro i _ calc x i = x i * 1 := by ring _ ≤ x i * A.orderEmbOfFin hAcard i := mul_le_mul_of_nonneg_left (hbound i) (hx0 i).1
Contradiction, hence no representation of s exists and ν_q(s) = 0. automation
Linear integer arithmetic derives a contradiction from s < h + 1 ≤ x · A = s.
omega
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Fintype.mem_piFinset- A function belongs to a finite product of finsets if and only if its value at each index belongs to the corresponding finset.
Finset.mem_image- An element belongs to the image of a finset under a function if and only if it is the image of some element of that finset.
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
dif_pos- A dependent if-then-else evaluates to its then-branch when the condition holds.
Finset.card_eq_zero- A finset has cardinality zero if and only if it is empty.
Finset.filter_eq_empty_iff- A filtered finset is empty if and only if no element of the base finset satisfies the filtering predicate.
Finset.mem_product- A pair belongs to the Cartesian product of two finsets if and only if each component belongs to the respective finset.
sumset_rep_count_eq_zero_of_lt_aux_mem_vectors- A vector x belongs to sumset_sum_vectors_finset h k if and only if 0 ≤ x_i ≤ h for all i and ∑ x_i = h.
Finset.mem_powersetCard- A set belongs to powersetCard k s if and only if it is a subset of s and has cardinality k.
Finset.orderEmbOfFin_mem- The ith element of the order embedding of a finite set belongs to the set.
Finset.mem_Icc- An integer belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
sumset_rep_count_eq_zero_of_lt_aux_sorted- The sorted vector associated to a finset A of cardinality k is given by the order embedding of Fin k into A.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finset, then the sum of f over the finset is at most the sum of g.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality b ≤ c on the left by a non-negative element a yields a * b ≤ a * c.
- The helper lemma sumset_rep_count_eq_zero_of_lt_aux_mem_vectors proves the equivalence between membership in the vector finset and coordinate bounds, which Lean relies on to unpack the definition.
- Linear integer arithmetic is solved by the automated tactic omega at lines 12, 17, and 59.
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.
private theorem sumset_rep_count_eq_zero_of_lt_aux_mem_vectors (h k : ℕ) (x : Fin k → ℤ) : x ∈ sumset_sum_vectors_finset h k ↔ (∀ i, 0 ≤ x i ∧ x i ≤ (h : ℤ)) ∧ ∑ i, x i = (h : ℤ) := by unfold sumset_sum_vectors_finset rw [Finset.mem_filter, Fintype.mem_piFinset] constructor · rintro ⟨h1, h2⟩ refine ⟨fun i => ?_, h2⟩ have := h1 i simp only [Finset.mem_image, Finset.mem_range] at this obtain ⟨n, hn, heq⟩ := this rw [← heq]; constructor <;> omega · rintro ⟨h1, h2⟩ refine ⟨fun i => ?_, h2⟩ obtain ⟨h0, hle⟩ := h1 i simp only [Finset.mem_image, Finset.mem_range] exact ⟨(x i).toNat, by omega, by omega⟩private theorem sumset_rep_count_eq_zero_of_lt_aux_sorted (k : ℕ) (A : Finset ℤ) (hA : A.card = k) : sumset_finset_sorted_vector k A = A.orderEmbOfFin hA := by unfold sumset_finset_sorted_vector rw [dif_pos hA]/-- The representation count ν_q(s) vanishes for s < h + 1. -/theorem sumset_rep_count_eq_zero_of_lt (k h q : ℕ) (hk : 1 ≤ k) (s : ℤ) (hs : s < (h : ℤ) + 1) : 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_lt_aux_mem_vectors] at hxb obtain ⟨hx0, hxsum⟩ := hxb rw [Finset.mem_powersetCard] at hAb obtain ⟨hAS, hAcard⟩ := hAb have hbound : ∀ i : Fin k, (1 : ℤ) ≤ A.orderEmbOfFin hAcard i := by intro i have hh := hAS (Finset.orderEmbOfFin_mem A hAcard i) rw [Finset.mem_Icc] at hh exact hh.1 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_lt_aux_sorted k A hAcard] simp only [dotProduct] have hge : (h : ℤ) + 1 ≤ dotProduct x (sumset_finset_sorted_vector k A) := by rw [hdot] have h1 : ∑ i : Fin k, x i = (h : ℤ) + 1 := by rw [hxsum]; push_cast; ring rw [← h1] apply Finset.sum_le_sum intro i _ calc x i = x i * 1 := by ring _ ≤ x i * A.orderEmbOfFin hAcard i := mul_le_mul_of_nonneg_left (hbound i) (hx0 i).1 omega