int_mem_h_fold_sumset_le_of_forall_le
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 7
- postage_stamp_basis_range_eight_neg_four_one_thirteen_fourteenThe set A = {−4, 1, 13, 14} is an 8-basis for 99: every integer in [0, 99] is a sum of exactly 8 elements of A, so n_8(A) ≥ 99.
- postage_stamp_basis_range_ge_of_mod_four_eq_twoFor h = 4w − 2 (w ≥ 1), the set A = {−w, w, w + 1} satisfies n_h(A) ≥ (w + 1)h = (h² + 6h)/4.
- postage_stamp_basis_range_zero_one_ge_of_mod_four_eq_zeroFor h = 4w (w ≥ 1), the basis {0, 1, 2w + 1} = {0, 1, (h+2)/2} has h-range at least w(4w + 6) = (h² + 6h)/4: every integer in [0, w(4w+6)]…
- postage_stamp_number_three_eight_eqThe classical postage stamp number with four stamps (one of them 0) and h = 8: n_8(3) = 89, attained by {0, 1, 9, 14}.
- postage_stamp_basis_range_zero_one_ge_of_mod_four_eq_twoFor h = 4w - 2 (w ≥ 1), the basis {0, 1, 2w} = {0, 1, (h+2)/2} has h-range at least (w+1)h = (h² + 6h)/4: every integer in [0, (w+1)h] is…
- postage_stamp_basis_range_zero_one_ge_of_oddFor odd h = 2m + 1, Stöhr's extremal basis {0, 1, (h+3)/2} = {0, 1, m+2} has h-range at least m² + 4m + 2 = (h² + 6h + 1)/4: every integer…
- postage_stamp_basis_range_ge_of_mod_four_eq_zeroFor h = 4w with w ≥ 2, the set A = {−(w − 1), w, w + 2} satisfies n_h(A) ≥ w(4w + 6) = (h² + 6h)/4.
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.
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.
obtain ⟨f, hf, rfl⟩ := hm
∑ 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.
uses
Finset.sum_le_sumcalc ∑ i, f i ≤ ∑ _i : Fin h, b := Finset.sum_le_sum fun i _ => hb _ (hf i)
∑ _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.
_ = 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
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.
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