AFTD Auto-Formalizing Theoretical Domains

sumset_rep_count_eq_zero_of_gt

theoremverifiedformalization

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

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

    lines 7–18

    uses Fintype.mem_piFinset, and_congr_left, Finset.mem_image, Finset.mem_range

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

    lines 19–27

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

    lines 33–38

    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]
      rintro ⟨x, A⟩ hp
      simp only
      intro heq
  4. 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.

    lines 39–44

    uses Finset.mem_product, sumset_rep_count_eq_zero_of_gt_mem_vectors, Finset.mem_powersetCard

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

    lines 45–49

    uses Finset.orderEmbOfFin_mem, Finset.mem_Icc

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

    lines 50–53

    uses sumset_rep_count_eq_zero_of_gt_sorted, dotProduct

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

    lines 54–61

    uses Finset.sum_mul, Finset.sum_le_sum, mul_le_mul_of_nonneg_left

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

    line 62

      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

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