AFTD Auto-Formalizing Theoretical Domains

int_mem_h_fold_sumset_of_list

theoremverified

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

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.

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

    line 3

    uses List.get_mem

      refine ⟨fun i => l.get i, fun i => hA _ (List.get_mem l i), ?_⟩
  2. 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.

    line 4

    uses List.sum_ofFn, List.ofFn_get

      simpa 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

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