AFTD Auto-Formalizing Theoretical Domains

monomial_mul

theoremverified

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

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.

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

    lines 1–2

    uses gf8_zmod2_cases

    lemma monomial_mul_zmod2_mul_self (a : ZMod 2) : a * a = a := by
      rcases gf8_zmod2_cases a with rfl | rfl <;> ring
  2. 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.

    lines 4–10

    uses Finset.insert_erase, Finset.prod_insert, Finset.notMem_erase, monomial_mul_zmod2_mul_self

    lemma 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]
  3. 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.

    lines 15–16

      ext x
      dsimp [monomial]
  4. 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.

    lines 17–18

    uses Finset.induction_on

      induction J using Finset.induction_on with
      | empty => simp
  5. 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).

    lines 19–21

    uses Finset.prod_insert

      | @insert a s' ha ih =>
        rw [Finset.prod_insert ha]
        by_cases haI : a ∈ I
  6. The 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.

    lines 22–26

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

    lines 27–37

    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

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