AFTD Auto-Formalizing Theoretical Domains

rigid_sequence_projection_is_zero_sum

theoremverified

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

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

    line 11

      refine ⟨?_, ?_, ?_⟩
  2. 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.

    line 12

    uses Multiset.card_map

      · rw [Multiset.card_map, hW_card]
  3. 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.

    line 13

    uses multiset_sum_apply, Pi.zero_apply

      · rw [multiset_sum_apply, hW_sum, Pi.zero_apply]
  4. 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).

    lines 14–17

    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

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