AFTD Auto-Formalizing Theoretical Domains

sumset_sum_vectors_finset_mem

theoremverified

For any natural numbers h and k and any vector x : Fin k → ℤ, x belongs to sumset_sum_vectors_finset h k if and only if x belongs to sumset_sum_vectors h k.

Statement

theorem sumset_sum_vectors_finset_mem (h k : ℕ) (x : Fin k → ℤ) :
    x ∈ sumset_sum_vectors_finset h k ↔ x ∈ sumset_sum_vectors h k
Source
arXiv:2611.07303, Section 1
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • sumset_sum_vectorsThe set X_{h,k} is defined as the set of all vectors x : Fin k → ℤ satisfying (∀ i, 0 ≤ x i) and ∑ i, x i = (h : ℤ).
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

For all natural numbers $h$ and $k$, and every vector $x : \mathrm{Fin}(k) \to \mathbb{Z}$, $x$ is an element of sumset_sum_vectors_finset h k if and only if $x$ is an element of sumset_sum_vectors h k.

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 theorem establishes that an integer vector x summing to h has all coordinates in {0, …, h} if and only if all coordinates are non-negative. In the forward direction, each coordinate is the image of a natural number and is therefore non-negative. In the reverse direction, non-negativity guarantees that each coordinate is bounded above by the total sum h, placing it in {0, …, h}.

  1. Membership in `sumset_sum_vectors_finset h k` and `sumset_sum_vectors h k` reduces to comparing coordinate conditions.

    Unfolding the definitions of both sets and the membership conditions for filters, set comprehensions, and Cartesian products rewrites the equivalence: a vector `x` satisfies `∑ i, x i = h` and has all coordinates in the integer image of `{0, …, h}` if and only if `∑ i, x i = h` and all coordinates are non-negative. Splitting the `↔` sets up the two implications to prove.

    lines 4–6

    uses Finset.mem_filter, Set.mem_ofPred_eq, Fintype.mem_piFinset

      simp only [sumset_sum_vectors_finset, sumset_sum_vectors, Finset.mem_filter,
        Set.mem_ofPred_eq, Fintype.mem_piFinset]
      constructor
  2. If each coordinate `x i` belongs to `{0, …, h}`, then `x i ≥ 0`.

    Assume the sum condition and that every coordinate lies in the image of `Finset.range (h + 1)`. The sum condition is retained directly. For each coordinate `x i`, being in the image means `x i = (n : ℤ)` for some natural number `n`. Natural numbers cast to non-negative integers by `Nat.cast_nonneg`, so `0 ≤ x i`.

    lines 7–11

    uses Finset.mem_image.mp, Nat.cast_nonneg

      · rintro ⟨hx, hsum⟩
        refine ⟨fun i => ?_, hsum⟩
        obtain ⟨n, hn, hnx⟩ := Finset.mem_image.mp (hx i)
        rw [← hnx]
        exact Nat.cast_nonneg n
  3. Given `0 ≤ x i` for all `i`, membership in `{0, …, h}` reduces to showing `(x i).toNat < h + 1`.

    Assume `0 ≤ x i` for all `i` and `∑ i, x i = h`. The sum condition is again kept. For each coordinate `x i`, to show it is in the integer image of `{0, …, h}`, we provide its natural-number conversion `(x i).toNat` as a witness; since `x i ≥ 0`, `Int.toNat_of_nonneg` ensures its integer cast equals `x i`. It remains to show that `(x i).toNat` is in `Finset.range (h + 1)`, which means `(x i).toNat < h + 1`.

    lines 12–16

    uses Finset.mem_image, Int.toNat_of_nonneg, Finset.mem_range

      · rintro ⟨hx, hsum⟩
        refine ⟨fun i => ?_, hsum⟩
        rw [Finset.mem_image]
        refine ⟨(x i).toNat, ?_, Int.toNat_of_nonneg (hx i)⟩
        rw [Finset.mem_range]
  4. For each index `i`, `x i ≤ h`.

    Using the assumption that `∑ j, x j = h`, we rewrite the bound as `x i ≤ ∑ j, x j`. Since all components `x j` are non-negative, any individual term `x i` is at most the total sum by `Finset.single_le_sum`.

    lines 17–19

    uses Finset.single_le_sum, Finset.mem_univ

        have hle : x i ≤ (h : ℤ) := by
          rw [← hsum]
          exact Finset.single_le_sum (f := x) (fun j _ => hx j) (Finset.mem_univ i)
  5. `(x i).toNat < h + 1`, completing the equivalence.

    Since `0 ≤ x i`, `(x i).toNat` coerced to an integer equals `x i`. Combining this equality with `x i ≤ h`, linear integer arithmetic (`omega`) deduces `(x i).toNat < h + 1`.

    lines 20–21

    uses Int.toNat_of_nonneg

        have h1 : ((x i).toNat : ℤ) = x i := Int.toNat_of_nonneg (hx i)
        omega
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Set.mem_ofPred_eq
An element belongs to the set `{x | p x}` if and only if it satisfies `p`.
Fintype.mem_piFinset
A function belongs to the product `Fintype.piFinset t` if and only if its value at each input `a` belongs to `t a`.
Finset.mem_image.mp
If an element belongs to `Finset.image f s`, then it is the image `f a` of some `a ∈ s`.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is non-negative.
Finset.mem_image
An element belongs to `Finset.image f s` if and only if it is the image `f a` of some `a ∈ s`.
Int.toNat_of_nonneg
For any non-negative integer `a ≥ 0`, casting its natural-number conversion back to `ℤ` yields `a`.
Finset.mem_range
A natural number `m` belongs to `Finset.range n` if and only if `m < n`.
Finset.single_le_sum
In a sum of non-negative elements over a finite set, each individual term is less than or equal to the total sum.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.

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

/-- Equivalence between sumset_sum_vectors_finset and sumset_sum_vectors. -/theorem sumset_sum_vectors_finset_mem (h k : ℕ) (x : Fin k → ℤ) :    x ∈ sumset_sum_vectors_finset h k ↔ x ∈ sumset_sum_vectors h k := by  simp only [sumset_sum_vectors_finset, sumset_sum_vectors, Finset.mem_filter,    Set.mem_ofPred_eq, Fintype.mem_piFinset]  constructor  · rintro ⟨hx, hsum⟩    refine ⟨fun i => ?_, hsum⟩    obtain ⟨n, hn, hnx⟩ := Finset.mem_image.mp (hx i)    rw [← hnx]    exact Nat.cast_nonneg n  · rintro ⟨hx, hsum⟩    refine ⟨fun i => ?_, hsum⟩    rw [Finset.mem_image]    refine ⟨(x i).toNat, ?_, Int.toNat_of_nonneg (hx i)⟩    rw [Finset.mem_range]    have hle : x i ≤ (h : ℤ) := by      rw [← hsum]      exact Finset.single_le_sum (f := x) (fun j _ => hx j) (Finset.mem_univ i)    have h1 : ((x i).toNat : ℤ) = x i := Int.toNat_of_nonneg (hx i)    omega
See it in the graphDiscuss this resultChallenge it