monomial_mul
For any natural number s and any two finite subsets I and J of Fin s, the pointwise product of the coordinate monomials monomial I and monomial J on (Fin s → ZMod 2) to ZMod 2 is equal to the coordinate monomial monomial (I ∪ J).
Statement
theorem monomial_mul {s : ℕ} (I J : Finset (Fin s)) :
(monomial I * monomial J : (Fin s → ZMod 2) → ZMod 2) = monomial (I ∪ J)- Source
- arXiv:2610.29807, Lemma 3.2: Some Results on the Weight Spectrum of Binary Reed-Muller Codes RM(m-7,m)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- gf8_oracle_t_count_ge_20The slice-rank floor of arXiv:2610.01024 Proposition 59 at k = 3: every parity representation of the GF(8) multiplication oracle's…
- monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
- Used by 1
- hamming_norm_sum_two_degree_six_monomialsLet I and J be two 6-element subsets of Fin 12. Then the Hamming norm of the sum of the corresponding coordinate monomials monomial I +…
Read back from the Lean
For any natural number $s$ and any finite subsets $I, J \subseteq \mathrm{Fin}(s)$, the pointwise product of the functions $\mathrm{monomial}(I)$ and $\mathrm{monomial}(J)$ (both of type $(\mathrm{Fin}(s) \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$) is equal to the function $\mathrm{monomial}(I \cup 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
To show that the pointwise product of coordinate monomials equals the monomial of the union of their index sets, we evaluate both sides on an arbitrary input and proceed by finite set induction on the second index set J. The base case J = ∅ is immediate because the empty product is 1 and I ∪ ∅ = I. When adjoining an element a ∉ s' to form J, we factor out x a and branch on whether a ∈ I. If a ∈ I, the factor x a is absorbed into the product over I using the idempotence x a * x a = x a in ZMod 2; if a ∉ I, x a factors out of both sides, and in each case the induction hypothesis completes the step.
Every element a ∈ ZMod 2 satisfies a * a = a.
By case analysis on a ∈ ZMod 2 using gf8_zmod2_cases, a is either 0 or 1. In both cases, 0 * 0 = 0 and 1 * 1 = 1 by ring arithmetic.
uses
gf8_zmod2_caseslemma monomial_mul_zmod2_mul_self (a : ZMod 2) : a * a = a := by rcases gf8_zmod2_cases a with rfl | rfl <;> ring
If a ∈ I, multiplying the coordinate product ∏_{i ∈ I} x i by x a leaves the product unchanged.
Since a ∈ I (ha), we rewrite I as insert a (I.erase a) using Finset.insert_erase. Factoring out x a using Finset.prod_insert and Finset.notMem_erase rewrites the product as (x a * ∏_{i ∈ I.erase a} x i) * x a. Regrouping the terms gives (x a * x a) * ∏_{i ∈ I.erase a} x i, which simplifies to x a * ∏_{i ∈ I.erase a} x i by idempotence in ZMod 2 (monomial_mul_zmod2_mul_self). Recombining x a with the remaining product using Finset.prod_insert and Finset.insert_erase restores ∏_{i ∈ I} x i.
uses
Finset.insert_erase,Finset.prod_insert,Finset.notMem_erase,monomial_mul_zmod2_mul_selflemma monomial_mul_prod_mul_mem {s : ℕ} (I : Finset (Fin s)) (a : Fin s) (ha : a ∈ I) (x : Fin s → ZMod 2) : (∏ i ∈ I, x i) * x a = ∏ i ∈ I, x i := by conv_lhs => rw [← Finset.insert_erase ha] rw [Finset.prod_insert (Finset.notMem_erase a I)] have : (x a * ∏ i ∈ I.erase a, x i) * x a = (x a * x a) * ∏ i ∈ I.erase a, x i := by ring rw [this, monomial_mul_zmod2_mul_self] rw [← Finset.prod_insert (Finset.notMem_erase a I), Finset.insert_erase ha]
To prove monomial I * monomial J = monomial (I ∪ J), it suffices to show (∏_{i ∈ I} x i) * ∏_{j ∈ J} x j = ∏_{k ∈ I ∪ J} x k for every input x : Fin s → ZMod 2.
By function extensionality (ext x), two functions are equal if their values agree on every input x. Unfolding the definition of monomial evaluates both sides pointwise to coordinate products.
ext x dsimp [monomial]
The identity holds in the base case J = ∅.
We proceed by induction on the finite set J using Finset.induction_on. When J = ∅, the empty product is 1 and I ∪ ∅ = I, so both sides simplify to ∏_{i ∈ I} x i.
uses
Finset.induction_oninduction J using Finset.induction_on with | empty => simp
In the inductive step for J = insert a s' with a ∉ s', factor out x a from the product over J and split into cases based on whether a ∈ I.
Assuming the induction hypothesis (ih) for s' and that a ∉ s' (ha), we split the product over insert a s' into x a * ∏_{i ∈ s'} x i using Finset.prod_insert. We then perform a case split on whether a ∈ I (haI).
uses
Finset.prod_insert| @insert a s' ha ih => rw [Finset.prod_insert ha] by_cases haI : a ∈ IThe inductive step holds in the case where a ∈ I.
Because a ∈ I (haI), shifting the insertion across the union using Finset.insert_union_comm and absorbing a into I with Finset.insert_eq_of_mem yields I ∪ insert a s' = I ∪ s'. Regrouping the left-hand side as ((∏_{i ∈ I} x i) * x a) * ∏_{i ∈ s'} x i by ring arithmetic, the factor x a is absorbed into the product over I by monomial_mul_prod_mul_mem. Finally, the induction hypothesis ih completes the equality with ∏_{i ∈ I ∪ s'} x i.
uses
Finset.insert_union_comm,Finset.insert_eq_of_mem,monomial_mul_prod_mul_mem· rw [← Finset.insert_union_comm, Finset.insert_eq_of_mem haI] calc (∏ i ∈ I, x i) * (x a * ∏ i ∈ s', x i) _ = ((∏ i ∈ I, x i) * x a) * ∏ i ∈ s', x i := by ring _ = (∏ i ∈ I, x i) * ∏ i ∈ s', x i := by rw [monomial_mul_prod_mul_mem I a haI x] _ = ∏ i ∈ I ∪ s', x i := ih
The inductive step holds in the case where a ∉ I.
When a ∉ I (haI), we rewrite I ∪ insert a s' as insert a (I ∪ s') using Finset.insert_union_comm and Finset.insert_union. Since a ∉ I and a ∉ s' (ha), a ∉ I ∪ s' (ha_union) by Finset.mem_union. Factoring out x a via Finset.prod_insert gives x a * ∏_{i ∈ I ∪ s'} x i. Commuting and associating multiplication pulls x a to the front on the left-hand side, and applying the induction hypothesis ih to the remaining product completes the equality.
uses
Finset.insert_union_comm,Finset.insert_union,Finset.mem_union,Finset.prod_insert· rw [← Finset.insert_union_comm, Finset.insert_union] have ha_union : a ∉ I ∪ s' := by rw [Finset.mem_union] intro h cases h with | inl h1 => exact haI h1 | inr h2 => exact ha h2 rw [Finset.prod_insert ha_union] calc (∏ i ∈ I, x i) * (x a * ∏ i ∈ s', x i) _ = x a * ((∏ i ∈ I, x i) * ∏ i ∈ s', x i) := by ring _ = x a * (∏ i ∈ I ∪ s', x i) := by rw [ih]
gf8_zmod2_cases- Every element of ZMod 2 is either 0 or 1.
Finset.insert_erase- For any finite set s and element a ∈ s, inserting a into s with a erased yields s.
Finset.prod_insert- If a ∉ s, the product of a function over insert a s is the value at a times the product over s.
Finset.notMem_erase- An element a is not a member of the set s with a erased.
monomial_mul_zmod2_mul_self- Every element a of ZMod 2 satisfies a * a = a (idempotence of elements in ZMod 2).
Finset.induction_on- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved when inserting a fresh element.
Finset.insert_union_comm- Inserting an element into the first set of a union is equal to inserting it into the second set: insert a s ∪ t = s ∪ insert a t.
Finset.insert_eq_of_mem- Inserting an element into a finite set that already contains it leaves the set unchanged.
monomial_mul_prod_mul_mem- Multiplying the product over a finite set I by a coordinate x a where a ∈ I leaves the product unchanged in ZMod 2.
Finset.insert_union- Inserting an element into the first set of a union is equal to inserting it into the union: insert a s ∪ t = insert a (s ∪ t).
Finset.mem_union- An element belongs to the union s ∪ t if and only if it belongs to s or to t.
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.
lemma monomial_mul_zmod2_mul_self (a : ZMod 2) : a * a = a := by rcases gf8_zmod2_cases a with rfl | rfl <;> ringlemma monomial_mul_prod_mul_mem {s : ℕ} (I : Finset (Fin s)) (a : Fin s) (ha : a ∈ I) (x : Fin s → ZMod 2) : (∏ i ∈ I, x i) * x a = ∏ i ∈ I, x i := by conv_lhs => rw [← Finset.insert_erase ha] rw [Finset.prod_insert (Finset.notMem_erase a I)] have : (x a * ∏ i ∈ I.erase a, x i) * x a = (x a * x a) * ∏ i ∈ I.erase a, x i := by ring rw [this, monomial_mul_zmod2_mul_self] rw [← Finset.prod_insert (Finset.notMem_erase a I), Finset.insert_erase ha]/-- The pointwise product of two coordinate monomials is the monomial of their union. -/theorem monomial_mul {s : ℕ} (I J : Finset (Fin s)) : (monomial I * monomial J : (Fin s → ZMod 2) → ZMod 2) = monomial (I ∪ J) := by ext x dsimp [monomial] induction J using Finset.induction_on with | empty => simp | @insert a s' ha ih => rw [Finset.prod_insert ha] by_cases haI : a ∈ I · rw [← Finset.insert_union_comm, Finset.insert_eq_of_mem haI] calc (∏ i ∈ I, x i) * (x a * ∏ i ∈ s', x i) _ = ((∏ i ∈ I, x i) * x a) * ∏ i ∈ s', x i := by ring _ = (∏ i ∈ I, x i) * ∏ i ∈ s', x i := by rw [monomial_mul_prod_mul_mem I a haI x] _ = ∏ i ∈ I ∪ s', x i := ih · rw [← Finset.insert_union_comm, Finset.insert_union] have ha_union : a ∉ I ∪ s' := by rw [Finset.mem_union] intro h cases h with | inl h1 => exact haI h1 | inr h2 => exact ha h2 rw [Finset.prod_insert ha_union] calc (∏ i ∈ I, x i) * (x a * ∏ i ∈ s', x i) _ = x a * ((∏ i ∈ I, x i) * ∏ i ∈ s', x i) := by ring _ = x a * (∏ i ∈ I ∪ s', x i) := by rw [ih]