rigid_sequence_projection_is_zero_sum
Let n, m, and t be natural numbers, and for each i in Fin t let S(i) be a sequence in Multiset (G(i)) where each G(i) is an additive commutative group. If W is an n-term zero-sum subsequence of the rigid sequence tensor product of S with parameters n and m, then for each coordinate j in Fin t, the projection of W to coordinate j has cardinality n, sum 0, and support contained in S(j).
Statement
lemma rigid_sequence_projection_is_zero_sum {n m t : ℕ} {G : Fin t → Type*} [∀ i, AddCommGroup (G i)] [∀ i, DecidableEq (G i)] (S : (i : Fin t) → Multiset (G i)) (W : Multiset ((i : Fin t) → G i)) (hW_le : W ≤ rigid_sequence_tensor_product n m S) (hW_card : W.card = n) (hW_sum : W.sum = 0) (j : Fin t) : (W.map (fun x => x j)).card = n ∧ (W.map (fun x => x j)).sum = 0 ∧ (∀ y ∈ W.map (fun x => x j), y ∈ S j)
- Source
- arXiv:2610.35819 Proof of Theorem 4.3
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- multiset_sum_applyFor any finite family of additive commutative monoids G_i over i in Fin t, any multiset W of dependent functions x : (i : Fin t) -> G_i,…
- rigid_sequence_tensor_product_mem_coordLet n and m be natural numbers, t a natural number, and for each i in Fin t let S(i) be a sequence in Multiset (G(i)). If x is an element…
- rigid_sequence_tensor_productGiven natural numbers n and m, a natural number t, a family of types G(i) with decidable equality for each i in Fin t, and a sequence S(i)…
Read back from the Lean
Let $n, m, t \in \mathbb{N}$. For each $i \in \mathrm{Fin}\; t$, let $G_i$ be an additive abelian group with decidable equality. Let $S$ be a family of multisets $S_i$ over $G_i$ (for $i \in \mathrm{Fin}\; t$). Let $W$ be a multiset of elements of the product type $\prod_{i : \mathrm{Fin}\; t} G_i$. Assume: 1. $W \le \mathrm{rigid\_sequence\_tensor\_product}(n, m, S)$; 2. The cardinality of $W$ is $n$ ($W.\mathrm{card} = n$); 3. The sum of the elements of $W$ in $\prod_{i} G_i$ is $0$ ($W.\mathrm{sum} = 0$). Then, for any index $j \in \mathrm{Fin}\; t$: 1. The projection of $W$ onto coordinate $j$, viewed as a multiset over $G_j$, has cardinality $n$; 2. The sum of the elements in this projected multiset is $0 \in G_j$; 3. Every element in this projected multiset belongs to $S_j$ (i.e., has count $> 0$ in $S_j$).
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 proof decomposes the goal into three separate assertions about the multiset projection of W to coordinate j: its cardinality, its sum, and its support. Multiset projection preserves cardinality, and it commutes with summation so that the zero-sum property of W carries over coordinatewise. Finally, because W is a submultiset of the tensor product, each tuple in W belongs to the tensor product, which by construction only contains tuples whose j-th coordinate lies in S(j).
It suffices to verify three conditions for the coordinate projection of W: its cardinality is n, its sum is 0, and each of its elements belongs to S(j).
The target is a three-part conjunction; we split the proof into three independent subgoals.
refine ⟨?_, ?_, ?_⟩The multiset projection of W to coordinate j has cardinality n.
Applying a function to each element of a multiset does not change its cardinality (Multiset.card_map), and W has cardinality n by assumption.
uses
Multiset.card_map· rw [Multiset.card_map, hW_card]The sum of the multiset projection of W to coordinate j is 0.
By multiset_sum_apply, the sum of coordinate projections equals the j-th coordinate of the total sum W.sum. Since W is zero-sum by hypothesis (W.sum = 0), evaluating this zero function at j gives 0 by Pi.zero_apply.
uses
multiset_sum_apply,Pi.zero_apply· rw [multiset_sum_apply, hW_sum, Pi.zero_apply]Every element of the multiset projection of W to coordinate j belongs to S(j).
Given any element y in the projection, it must be the j-th coordinate x(j) of some tuple x in W by Multiset.mem_map.mp. Since W is a submultiset of the tensor product, x is also an element of the rigid sequence tensor product by Multiset.mem_of_le. Then rigid_sequence_tensor_product_mem_coord ensures that every tuple in this tensor product has its j-th coordinate in S(j), so y ∈ S(j).
uses
Multiset.mem_map.mp,Multiset.mem_of_le,rigid_sequence_tensor_product_mem_coord· intro y hy obtain ⟨x, hx, rfl⟩ := Multiset.mem_map.mp hy have hx_le : x ∈ rigid_sequence_tensor_product n m S := Multiset.mem_of_le hW_le hx exact rigid_sequence_tensor_product_mem_coord S x hx_le j
Multiset.card_map- The cardinality of the image of a multiset under a map equals the cardinality of the original multiset.
multiset_sum_apply- For a multiset of tuples, the sum of their projections at coordinate j equals the j-th coordinate of the sum of the multiset.
Pi.zero_apply- Evaluating the zero element of a function space at an index yields zero.
Multiset.mem_map.mp- An element is in the image of a multiset under a map if and only if it is the image of some element of the multiset.
Multiset.mem_of_le- If one multiset is a submultiset of another, any element belonging to the first also belongs to the second.
rigid_sequence_tensor_product_mem_coord- Every tuple in the rigid sequence tensor product of sequences S has its j-th coordinate in S(j).
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.
/-- Coordinate projections of an n-term zero-sum subsequence of the tensor product are n-term zero-sums on the factors. -/lemma rigid_sequence_projection_is_zero_sum {n m t : ℕ} {G : Fin t → Type*} [∀ i, AddCommGroup (G i)] [∀ i, DecidableEq (G i)] (S : (i : Fin t) → Multiset (G i)) (W : Multiset ((i : Fin t) → G i)) (hW_le : W ≤ rigid_sequence_tensor_product n m S) (hW_card : W.card = n) (hW_sum : W.sum = 0) (j : Fin t) : (W.map (fun x => x j)).card = n ∧ (W.map (fun x => x j)).sum = 0 ∧ (∀ y ∈ W.map (fun x => x j), y ∈ S j) := by refine ⟨?_, ?_, ?_⟩ · rw [Multiset.card_map, hW_card] · rw [multiset_sum_apply, hW_sum, Pi.zero_apply] · intro y hy obtain ⟨x, hx, rfl⟩ := Multiset.mem_map.mp hy have hx_le : x ∈ rigid_sequence_tensor_product n m S := Multiset.mem_of_le hW_le hx exact rigid_sequence_tensor_product_mem_coord S x hx_le j