AFTD Auto-Formalizing Theoretical Domains

sumset_rep_count_eq_zero_of_lt

theoremverifiedformalization

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

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.

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

    lines 4–6

    uses Finset.mem_filter, Fintype.mem_piFinset

      unfold sumset_sum_vectors_finset
      rw [Finset.mem_filter, Fintype.mem_piFinset]
      constructor
  2. 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.

    lines 7–12

    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 <;> omega
  3. Conversely, 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}.

    lines 13–17

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

    lines 21–22

    uses dif_pos

      unfold sumset_finset_sorted_vector
      rw [dif_pos hA]
  5. 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.

    lines 28–30

    uses Finset.card_eq_zero, Finset.filter_eq_empty_iff

      unfold sumset_rep_count
      rw [Finset.card_eq_zero]
      rw [Finset.filter_eq_empty_iff]
  6. 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].

    lines 31–39

    uses Finset.mem_product, sumset_rep_count_eq_zero_of_lt_aux_mem_vectors, Finset.mem_powersetCard

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

    lines 40–44

    uses Finset.orderEmbOfFin_mem, Finset.mem_Icc

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

    lines 45–48

    uses sumset_rep_count_eq_zero_of_lt_aux_sorted

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

    lines 49–58

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left

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

    line 59

      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.

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

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