sumset_sum_vectors_finset_mem
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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}.
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.
uses
Finset.mem_filter,Set.mem_ofPred_eq,Fintype.mem_piFinsetsimp only [sumset_sum_vectors_finset, sumset_sum_vectors, Finset.mem_filter, Set.mem_ofPred_eq, Fintype.mem_piFinset] constructor
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`.
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 nGiven `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`.
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]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`.
uses
Finset.single_le_sum,Finset.mem_univhave hle : x i ≤ (h : ℤ) := by rw [← hsum] exact Finset.single_le_sum (f := x) (fun j _ => hx j) (Finset.mem_univ i)
`(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`.
uses
Int.toNat_of_nonneghave 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
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.
/-- 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