AFTD Auto-Formalizing Theoretical Domains

int_mem_h_fold_sumset_le_of_forall_le

theoremverified

If every element of A is at most b, every element of hA is at most h·b.

Statement

theorem int_mem_h_fold_sumset_le_of_forall_le (h : ℕ) (A : Finset ℤ) (b : ℤ) (hb : ∀ a ∈ A, a ≤ b)
    (m : ℤ) (hm : int_mem_h_fold_sumset h A m) : m ≤ h * b
Source
Helper for h-fold sumsets (arXiv:2610.19470 (Positivity and negativity for h-bases for n)): the boundedness that makes n_h(A) a maximum.
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • int_mem_h_fold_sumsetm belongs to the h-fold sumset hA: m is a sum of exactly h, not necessarily distinct, elements of A.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 7

The proof, explained

By definition, any element m in the h-fold sumset hA is a sum of h elements of A. Since each element of A is bounded above by b, bounding the summands termwise yields m ≤ ∑ b = h · b.

  1. Represent m as a sum of h elements from A.

    By definition of the h-fold sumset (int_mem_h_fold_sumset), there exists a family f : Fin h → ℤ such that each f(i) ∈ A and m = ∑ i, f(i). We unpack this existential witness and substitute m with the sum.

    line 3

      obtain ⟨f, hf, rfl⟩ := hm
  2. ∑ i, f i ≤ ∑ _i : Fin h, b

    Since each f(i) is in A, the hypothesis hb implies f(i) ≤ b for every index i. We apply Finset.sum_le_sum to compare the sums termwise.

    line 4

    uses Finset.sum_le_sum

      calc ∑ i, f i ≤ ∑ _i : Fin h, b := Finset.sum_le_sum fun i _ => hb _ (hf i)
  3. ∑ _i : Fin h, b = h * b automation

    Summing the constant value b over the h-element index set Fin h simplifies directly to h * b, completing the chained inequality for m.

    line 5

        _ = h * b := by simp
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.

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

theorem int_mem_h_fold_sumset_le_of_forall_le (h : ℕ) (A : Finset ℤ) (b : ℤ) (hb : ∀ a ∈ A, a ≤ b)    (m : ℤ) (hm : int_mem_h_fold_sumset h A m) : m ≤ h * b := by  obtain ⟨f, hf, rfl⟩ := hm  calc ∑ i, f i ≤ ∑ _i : Fin h, b := Finset.sum_le_sum fun i _ => hb _ (hf i)    _ = h * b := by simp
See it in the graphDiscuss this resultChallenge it