int_mem_h_fold_sumset_of_list
The sum of a list of h elements of A lies in hA.
Statement
theorem int_mem_h_fold_sumset_of_list (A : Finset ℤ) (l : List ℤ) (hA : ∀ x ∈ l, x ∈ A) :
int_mem_h_fold_sumset l.length A l.sum- Source
- Helper for h-fold sumsets (arXiv:2610.19470 (Positivity and negativity for h-bases for n)), serving postage_stamp_basis_range_eight_neg_four_one_thirteen_fourteen.
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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.
- Used by 8
- postage_stamp_basis_mem_h_fold_sumset_mod_twelve_eq_nineFor any r : ℕ and any m ≤ 36r² + 72r + 33, m belongs to the (12r+9)-fold sumset of {-(2r+2), 2r+2, 4r+5}.
- 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
To show that the sum of a list l of elements from A belongs to the h-fold sumset of A (where h is the length of l), we need an indexing function from Fin l.length to A whose sum equals l.sum. We choose the function that retrieves the elements of the list, i ↦ l[i]. These elements lie in A by assumption, and their sum equals the sum of l because reconstructing a list from its elements yields the original list.
It suffices to show that ∑ i, l.get i = l.sum.
By definition, an integer m is in the h-fold sumset of A if it can be written as the sum of h elements of A, indexed by Fin h. Taking h to be the length of l, we witness this existential with the indexing function i ↦ l.get i. Every element l.get i belongs to the list l by List.get_mem, and therefore belongs to A by the hypothesis hA. This leaves only the requirement that their sum equals l.sum.
uses
List.get_memrefine ⟨fun i => l.get i, fun i => hA _ (List.get_mem l i), ?_⟩
The sum ∑ i, l.get i is equal to l.sum.
By List.sum_ofFn, the sum ∑ i, l.get i equals the sum of the list List.ofFn (fun i => l.get i). By List.ofFn_get, this reconstructed list is identical to l itself, so its sum is l.sum.
uses
List.sum_ofFn,List.ofFn_getsimpa using (List.sum_ofFn (f := fun i => l.get i)).symm.trans (by rw [List.ofFn_get])
List.get_mem- For any list l and index i : Fin l.length, the element l.get i is a member of the list l.
List.sum_ofFn- The sum of the list created from a function f : Fin n → M equals the sum ∑ i, f i over Fin n.
List.ofFn_get- Converting a list to a function via get and back to a list via ofFn recovers the original list.
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_of_list (A : Finset ℤ) (l : List ℤ) (hA : ∀ x ∈ l, x ∈ A) : int_mem_h_fold_sumset l.length A l.sum := by refine ⟨fun i => l.get i, fun i => hA _ (List.get_mem l i), ?_⟩ simpa using (List.sum_ofFn (f := fun i => l.get i)).symm.trans (by rw [List.ofFn_get])