AFTD Auto-Formalizing Theoretical Domains

reed_muller_four_block_concat_degree_seven

theoremverifiedformalization

Let g0 and g3 be Boolean functions on Fin 12 in the Reed-Muller code reed_muller_code 5 12, and let g1 and g2 be Boolean functions on Fin 12 in reed_muller_code 6 12. Then their four-block concatenation four_block_concat g0 g1 g2 (g1 + g2 + g3) belongs to the Reed-Muller code reed_muller_code 7 14.

Statement

theorem reed_muller_four_block_concat_degree_seven
    (g0 g3 : (Fin 12 → ZMod 2) → ZMod 2) (g1 g2 : (Fin 12 → ZMod 2) → ZMod 2)
    (hg0 : g0 ∈ reed_muller_code 5 12)
    (hg3 : g3 ∈ reed_muller_code 5 12)
    (hg1 : g1 ∈ reed_muller_code 6 12)
    (hg2 : g2 ∈ reed_muller_code 6 12) :
    four_block_concat g0 g1 g2 (g1 + g2 + g3) ∈ reed_muller_code 7 14
Formalizes
arXiv:2610.29807 Lemma 3.1 -- 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 5
  • reed_muller_codeFor natural numbers r and s, the binary Reed-Muller code RM(r, s) is the submodule of Boolean functions from (Fin s → ZMod 2) to ZMod 2…
  • reed_muller_code_monoFor any natural numbers r1, r2, and s such that r1 ≤ r2, the Reed-Muller code reed_muller_code r1 s is a submodule of reed_muller_code r2 s.
  • four_block_concatThe four-block concatenation four_block_concat of four Boolean functions f0, f1, f2, f3 : (Fin m → ZMod 2) → ZMod 2 is the Boolean…
  • four_block_concat_reducedFor any natural number m and Boolean functions g0, g1, g2, g3 on Fin m → ZMod 2, the four-block concatenation four_block_concat g0 g1 g2…
  • 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…

Read back from the Lean

For any functions $g_0, g_3, g_1, g_2 : (\mathrm{Fin}\, 12 \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$, if $g_0$ and $g_3$ belong to the Reed–Muller code $\mathcal{RM}(5, 12)$ and $g_1$ and $g_2$ belong to $\mathcal{RM}(6, 12)$, then the four-block concatenation of $g_0, g_1, g_2$, and $g_1 + g_2 + g_3$ belongs to the Reed–Muller code $\mathcal{RM}(7, 14)$.

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 four-block concatenation four_block_concat g0 g1 g2 (g1 + g2 + g3) lies in the Reed-Muller code RM(7, 14), we expand its reduced algebraic formula (1 + y₁) * (1 + y₂) * A + y₁ * B + y₂ * C + y₁ * y₂ * D over ZMod 2, where A, B, C, D are the lifts of g0, g1, g2, g3 to 14 variables and y₁, y₂ are the 13th and 14th coordinate variables. Expanding (1 + y₁)(1 + y₂) into 1 + y₁ + y₂ + y₁ y₂ decomposes the concatenation into a sum of seven terms: A, four single-variable products, and two double-variable products. Helper lemmas establish that lifting preserves code degrees and that multiplying by a monomial of size k increases degree by at most k; since the resulting degrees are all at most 7, each term belongs to RM(7, 14), and submodule closure under addition completes the proof.

  1. Every element of ZMod 2 satisfies a * a = a.

    In ZMod 2 there are only two elements, 0 and 1; by checking both cases, 0 * 0 = 0 and 1 * 1 = 1 hold by definition.

    lines 1–2

    private lemma reed_muller_four_block_concat_degree_seven_zz_mul_self (a : ZMod 2) : a * a = a := by
      fin_cases a <;> rfl
  2. When a ∉ I, multiplying monomial I by the coordinate function x ↦ x a gives monomial (insert a I).

    Evaluating the product pointwise at x gives x a * ∏ i ∈ I, x i. By Finset.prod_insert, since a ∉ I, this product equals the product over {a} ∪ I, which is monomial (insert a I) x.

    lines 4–8

    uses Finset.prod_insert

    private lemma reed_muller_four_block_concat_degree_seven_single_not_mem {s : ℕ} (a : Fin s)
        (I : Finset (Fin s)) (ha : a ∉ I) :
        (fun x : Fin s → ZMod 2 => x a) * monomial I = monomial (insert a I) := by
      funext x
      simp [monomial, Finset.prod_insert ha]
  3. When a ∈ I, multiplying monomial I by the coordinate function x ↦ x a leaves monomial I unchanged.

    Since a ∈ I, we partition I as {a} ∪ (I \ {a}) using Finset.insert_erase and Finset.prod_insert. Multiplying by x a produces (x a * x a) * ∏ i ∈ I \ {a}, x i. By idempotence (reed_muller_four_block_concat_degree_seven_zz_mul_self), x a * x a = x a, reconstructing the product over all of I.

    lines 10–16

    uses Pi.mul_apply, Finset.insert_erase, Finset.prod_insert, Finset.notMem_erase, mul_assoc, reed_muller_four_block_concat_degree_seven_zz_mul_self

    private lemma reed_muller_four_block_concat_degree_seven_single_mem {s : ℕ} (a : Fin s)
        (I : Finset (Fin s)) (ha : a ∈ I) :
        (fun x : Fin s → ZMod 2 => x a) * monomial I = monomial I := by
      funext x
      simp only [Pi.mul_apply, monomial]
      rw [← Finset.insert_erase ha, Finset.prod_insert (Finset.notMem_erase a I)]
      rw [← mul_assoc, reed_muller_four_block_concat_degree_seven_zz_mul_self]
  4. The pointwise product of two monomials, monomial I and monomial J, is monomial (I ∪ J).

    We induct on I using Finset.induction. The empty set gives monomial ∅ * monomial J = 1 * monomial J = monomial J. For the inductive step insert a I, we factor out x a, apply the induction hypothesis to obtain x a * monomial (I ∪ J), and branch on whether a ∈ J: if a ∈ J, then a ∈ I ∪ J and multiplication by x a leaves the monomial unchanged; if a ∉ J, then a ∉ I ∪ J and multiplication by x a inserts a into the index set.

    lines 18–28

    uses Finset.induction, Finset.insert_union, reed_muller_four_block_concat_degree_seven_single_not_mem, mul_assoc, reed_muller_four_block_concat_degree_seven_single_mem, Finset.mem_union_right, Finset.insert_eq_of_mem

    private lemma reed_muller_four_block_concat_degree_seven_monomial_mul {s : ℕ} (I J : Finset (Fin s)) :
        (monomial I * monomial J : (Fin s → ZMod 2) → ZMod 2) = monomial (I ∪ J) := by
      induction I using Finset.induction with
      | empty => funext x; simp [monomial]
      | insert a I ha ih =>
        rw [Finset.insert_union, ← reed_muller_four_block_concat_degree_seven_single_not_mem a I ha,
          mul_assoc, ih]
        by_cases haJ : a ∈ J
        · rw [reed_muller_four_block_concat_degree_seven_single_mem a (I ∪ J) (Finset.mem_union_right I haJ),
            Finset.insert_eq_of_mem (Finset.mem_union_right I haJ)]
        · rw [reed_muller_four_block_concat_degree_seven_single_not_mem a (I ∪ J) (by simp [ha, haJ])]
  5. Multiplying any function f in reed_muller_code r s by monomial T yields a function in reed_muller_code (r + T.card) s.

    We use span induction on f. For a generator monomial U with |U| ≤ r, the product is monomial (T ∪ U); since |T ∪ U| ≤ |T| + |U| ≤ |T| + r, monotonicity places it in reed_muller_code (r + T.card) s. For the zero function, addition, and scalar multiplication, the claim follows from the linearity and distributivity of multiplication.

    lines 34–51

    uses Submodule.span_induction, reed_muller_four_block_concat_degree_seven_monomial_mul, reed_muller_code_mono, reed_muller_four_block_concat_degree_seven_monomial_mem, le_refl, Finset.card_union_le, mul_add, Submodule.add_mem, Pi.mul_apply, smul_eq_mul, Submodule.smul_mem

    private lemma reed_muller_four_block_concat_degree_seven_mul_monomial_mem {s r : ℕ}
        (T : Finset (Fin s)) (f : (Fin s → ZMod 2) → ZMod 2) (hf : f ∈ reed_muller_code r s) :
        monomial T * f ∈ reed_muller_code (r + T.card) s := by
      induction hf using Submodule.span_induction with
      | mem x hx =>
          obtain ⟨U, hU, rfl⟩ := hx
          rw [reed_muller_four_block_concat_degree_seven_monomial_mul]
          refine reed_muller_code_mono ?_ (reed_muller_four_block_concat_degree_seven_monomial_mem _ (le_refl _))
          have := Finset.card_union_le T U
          omega
      | zero => simp
      | add x y hx hy ihx ihy =>
          rw [mul_add]
          exact Submodule.add_mem _ ihx ihy
      | smul a x hx ih =>
          rw [show monomial T * (a • x) = a • (monomial T * x) from by
            funext v; simp [Pi.mul_apply, smul_eq_mul]; ring]
          exact Submodule.smul_mem _ a ih
  6. Lifting a function g in reed_muller_code r m to m + k variables by restricting inputs to the first m coordinates preserves membership in reed_muller_code r (m + k).

    We induct on g via span induction. For a basis monomial U with |U| ≤ r, pulling back along Fin.castAdd k produces the monomial indexed by the image of U. Since Fin.castAdd k is injective, the image has cardinality |U| ≤ r, so the lifted monomial belongs to reed_muller_code r (m + k). The zero, addition, and scalar multiplication cases follow directly from linearity.

    lines 53–82

    uses Submodule.span_induction, Finset.prod_image, Fin.castAdd_injective, reed_muller_four_block_concat_degree_seven_monomial_mem, Finset.card_image_of_injective, Submodule.zero_mem, Submodule.add_mem, Submodule.smul_mem

    private lemma reed_muller_four_block_concat_degree_seven_lift_mem {m k r : ℕ}
        {g : (Fin m → ZMod 2) → ZMod 2} (hg : g ∈ reed_muller_code r m) :
        (fun v : Fin (m + k) → ZMod 2 => g (fun i => v (Fin.castAdd k i))) ∈
          reed_muller_code r (m + k) := by
      induction hg using Submodule.span_induction with
      | mem x hx =>
          obtain ⟨U, hU, rfl⟩ := hx
          have heq : (fun v : Fin (m + k) → ZMod 2 => monomial U (fun i => v (Fin.castAdd k i)))
              = monomial (U.image (Fin.castAdd k)) := by
            funext v
            simp only [monomial]
            exact (Finset.prod_image (f := v) (g := Fin.castAdd k)
              (fun x _ y _ h => Fin.castAdd_injective m k h)).symm
          rw [heq]
          exact reed_muller_four_block_concat_degree_seven_monomial_mem _
            (by rw [Finset.card_image_of_injective _ (Fin.castAdd_injective m k)]; exact hU)
      | zero =>
          have h : (fun v : Fin (m + k) → ZMod 2 =>
              (0 : (Fin m → ZMod 2) → ZMod 2) (fun i => v (Fin.castAdd k i))) = 0 := by
            funext v; rfl
          rw [h]; exact Submodule.zero_mem _
      | add x y hx hy ihx ihy =>
          have h : (fun v : Fin (m + k) → ZMod 2 => (x + y) (fun i => v (Fin.castAdd k i)))
              = (fun v => x (fun i => v (Fin.castAdd k i)))
                + (fun v => y (fun i => v (Fin.castAdd k i))) := by funext v; rfl
          rw [h]; exact Submodule.add_mem _ ihx ihy
      | smul a x hx ih =>
          have h : (fun v : Fin (m + k) → ZMod 2 => (a • x) (fun i => v (Fin.castAdd k i)))
              = a • (fun v => x (fun i => v (Fin.castAdd k i))) := by funext v; rfl
          rw [h]; exact Submodule.smul_mem _ a ih
  7. The four-block concatenation is expressed via the lifted functions A, B, C, D of g0, g1, g2, g3, which belong to degrees 5, 6, 6, 5 respectively (and A also belongs to degree 7).

    Using four_block_concat_reduced, the concatenation is expressed in terms of the variables and the functions g0, g1, g2, g3 lifted to 14 variables as A, B, C, D. By reed_muller_four_block_concat_degree_seven_lift_mem, A and D lie in reed_muller_code 5 14, while B and C lie in reed_muller_code 6 14. By code monotonicity (5 ≤ 7), A also lies in reed_muller_code 7 14.

    lines 92–106

    uses four_block_concat_reduced, reed_muller_four_block_concat_degree_seven_lift_mem, reed_muller_code_mono

      rw [four_block_concat_reduced]
      simp only []
      let A : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g0 (fun i => v (Fin.castAdd 2 i))
      let B : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g1 (fun i => v (Fin.castAdd 2 i))
      let C : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g2 (fun i => v (Fin.castAdd 2 i))
      let D : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g3 (fun i => v (Fin.castAdd 2 i))
      have hA : A ∈ reed_muller_code 5 14 :=
        reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 5) hg0
      have hB : B ∈ reed_muller_code 6 14 :=
        reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 6) hg1
      have hC : C ∈ reed_muller_code 6 14 :=
        reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 6) hg2
      have hD : D ∈ reed_muller_code 5 14 :=
        reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 5) hg3
      have hA7 : A ∈ reed_muller_code 7 14 := reed_muller_code_mono (by norm_num) hA
  8. Each product of a monomial in the last two coordinates with the corresponding lifted function belongs to reed_muller_code 7 14.

    Applying reed_muller_four_block_concat_degree_seven_mul_monomial_mem to each term: multiplying A (degree 5) by singletons {12} or {13} gives degree 5 + 1 = 6 ≤ 7; multiplying A by {12, 13} gives degree 5 + 2 = 7; multiplying B or C (degree 6) by singletons {12} or {13} gives degree 6 + 1 = 7; multiplying D (degree 5) by {12, 13} gives degree 5 + 2 = 7. In every case, reed_muller_code_mono places the product in reed_muller_code 7 14.

    lines 107–138

    uses reed_muller_four_block_concat_degree_seven_mul_monomial_mem, Finset.card_singleton, reed_muller_code_mono

      have ht1 : monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 := by
        have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem
          ({(12 : Fin 14)} : Finset (Fin 14)) A hA
        rw [Finset.card_singleton] at h
        exact reed_muller_code_mono (by norm_num) h
      have ht2 : monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 := by
        have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem
          ({(13 : Fin 14)} : Finset (Fin 14)) A hA
        rw [Finset.card_singleton] at h
        exact reed_muller_code_mono (by norm_num) h
      have ht12 : monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 := by
        have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem
          ({(12 : Fin 14), 13} : Finset (Fin 14)) A hA
        have hc : ({(12 : Fin 14), 13} : Finset (Fin 14)).card = 2 := by simp
        rw [hc] at h
        exact reed_muller_code_mono (by norm_num) h
      have ht3 : monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B ∈ reed_muller_code 7 14 := by
        have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem
          ({(12 : Fin 14)} : Finset (Fin 14)) B hB
        rw [Finset.card_singleton] at h
        exact reed_muller_code_mono (by norm_num) h
      have ht4 : monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C ∈ reed_muller_code 7 14 := by
        have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem
          ({(13 : Fin 14)} : Finset (Fin 14)) C hC
        rw [Finset.card_singleton] at h
        exact reed_muller_code_mono (by norm_num) h
      have ht5 : monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * D ∈ reed_muller_code 7 14 := by
        have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem
          ({(12 : Fin 14), 13} : Finset (Fin 14)) D hD
        have hc : ({(12 : Fin 14), 13} : Finset (Fin 14)).card = 2 := by simp
        rw [hc] at h
        exact reed_muller_code_mono (by norm_num) h
  9. The cumulative sum of A and the six monomial product terms belongs to reed_muller_code 7 14.

    Because reed_muller_code 7 14 is a linear submodule, it is closed under addition. Adding A and the six products x₁₂ A, x₁₃ A, x₁₂ x₁₃ A, x₁₂ B, x₁₃ C, x₁₂ x₁₃ D step by step using Submodule.add_mem confirms that their total sum belongs to reed_muller_code 7 14.

    lines 139–165

    uses Submodule.add_mem

      have s1 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 :=
        Submodule.add_mem _ hA7 ht1
      have s2 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 :=
        Submodule.add_mem _ s1 ht2
      have s3 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 :=
        Submodule.add_mem _ s2 ht12
      have s4 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B ∈ reed_muller_code 7 14 :=
        Submodule.add_mem _ s3 ht3
      have s5 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C ∈ reed_muller_code 7 14 :=
        Submodule.add_mem _ s4 ht4
      have s6 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * D ∈ reed_muller_code 7 14 :=
        Submodule.add_mem _ s5 ht5
  10. The reduced four-block concatenation equals this seven-term sum, proving that it belongs to reed_muller_code 7 14.

    Expanding the algebraic factor (1 + y₁)(1 + y₂) A into A + y₁ A + y₂ A + y₁ y₂ A over ZMod 2 shows that the reduced concatenation identical to the sum of the seven terms. Rewriting with this identity key establishes that four_block_concat g0 g1 g2 (g1 + g2 + g3) equals s6, which was already shown to be in reed_muller_code 7 14.

    lines 166–183

      have key : (fun v : Fin (12+2) → ZMod 2 =>
          (1 + v (Fin.natAdd 12 (0 : Fin 2))) * (1 + v (Fin.natAdd 12 (1 : Fin 2)))
            * g0 (fun i => v (Fin.castAdd 2 i))
          + v (Fin.natAdd 12 (0 : Fin 2)) * g1 (fun i => v (Fin.castAdd 2 i))
          + v (Fin.natAdd 12 (1 : Fin 2)) * g2 (fun i => v (Fin.castAdd 2 i))
          + v (Fin.natAdd 12 (0 : Fin 2)) * v (Fin.natAdd 12 (1 : Fin 2))
            * g3 (fun i => v (Fin.castAdd 2 i)))
          = A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A
          + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B
          + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C
          + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * D := by
        funext v
        simp [A, B, C, D, monomial]
        ring
      rw [key]
      exact s6
Finset.prod_insert
In a commutative monoid, the product of a function over the insertion of an element a into a finite set s (with a ∉ s) equals f(a) multiplied by the product over s.
Pi.mul_apply
Pointwise multiplication of functions evaluates to the product of their values: (f * g) x = f x * g x.
Finset.insert_erase
For any element a in s, inserting a into s.erase a yields s.
Finset.notMem_erase
An element a does not belong to the set s.erase a.
mul_assoc
Multiplication in a semigroup is associative: (a * b) * c = a * (b * c).
reed_muller_four_block_concat_degree_seven_zz_mul_self
Every element a of ZMod 2 is idempotent: a * a = a.
Finset.induction
Induction principle for finite sets: a property holding for the empty set and preserved under inserting an element holds for all finite sets.
Finset.insert_union
Inserting an element a into s and taking the union with t equals inserting a into s ∪ t.
reed_muller_four_block_concat_degree_seven_single_not_mem
Multiplying the monomial for I by the coordinate function for a (where a ∉ I) yields the monomial for insert a I.
reed_muller_four_block_concat_degree_seven_single_mem
Multiplying the monomial for I by the coordinate function for a (where a ∈ I) leaves the monomial unchanged.
Finset.mem_union_right
If an element a belongs to t, then a belongs to s ∪ t.
Finset.insert_eq_of_mem
Inserting an element a into a finite set s that already contains a leaves s unchanged.
Submodule.span_induction
Induction principle for the span of a set: a property holds for all elements of Submodule.span R s if it holds on generators, at zero, and is preserved under addition and scalar multiplication.
reed_muller_four_block_concat_degree_seven_monomial_mul
The pointwise product of monomial I and monomial J is monomial (I ∪ J).
reed_muller_code_mono
If r1 ≤ r2, then reed_muller_code r1 s is contained in reed_muller_code r2 s.
reed_muller_four_block_concat_degree_seven_monomial_mem
If the cardinality of T is at most r, then monomial T belongs to reed_muller_code r s.
le_refl
The inequality relation ≤ is reflexive: a ≤ a for any a.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
mul_add
Left multiplication distributes over addition: a * (b + c) = a * b + a * c.
Submodule.add_mem
A submodule is closed under addition: if x ∈ p and y ∈ p, then x + y ∈ p.
smul_eq_mul
Scalar multiplication of ring elements by scalars from the same ring coincides with multiplication: a • b = a * b.
Submodule.smul_mem
A submodule is closed under scalar multiplication: if x ∈ p, then r • x ∈ p.
Finset.prod_image
The product of a function over the image of a set under an injective map equals the product of the composite over the original set.
Fin.castAdd_injective
The variable embedding Fin.castAdd n from Fin m to Fin (m + n) is injective.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the original set.
Submodule.zero_mem
The zero element belongs to any submodule.
four_block_concat_reduced
The four-block concatenation of g0, g1, g2, and g1 + g2 + g3 simplifies to (1 + y₁) * (1 + y₂) * g0(x) + y₁ * g1(x) + y₂ * g2(x) + y₁ * y₂ * g3(x).
reed_muller_four_block_concat_degree_seven_lift_mem
Lifting a function g in reed_muller_code r m to m + k variables by composing with Fin.castAdd k produces an element of reed_muller_code r (m + k).
reed_muller_four_block_concat_degree_seven_mul_monomial_mem
Multiplying a function in reed_muller_code r s by monomial T produces a function in reed_muller_code (r + T.card) s.
Finset.card_singleton
A singleton set has cardinality 1: {a}.card = 1.

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

private lemma reed_muller_four_block_concat_degree_seven_zz_mul_self (a : ZMod 2) : a * a = a := by  fin_cases a <;> rflprivate lemma reed_muller_four_block_concat_degree_seven_single_not_mem {s : ℕ} (a : Fin s)    (I : Finset (Fin s)) (ha : a ∉ I) :    (fun x : Fin s → ZMod 2 => x a) * monomial I = monomial (insert a I) := by  funext x  simp [monomial, Finset.prod_insert ha]private lemma reed_muller_four_block_concat_degree_seven_single_mem {s : ℕ} (a : Fin s)    (I : Finset (Fin s)) (ha : a ∈ I) :    (fun x : Fin s → ZMod 2 => x a) * monomial I = monomial I := by  funext x  simp only [Pi.mul_apply, monomial]  rw [← Finset.insert_erase ha, Finset.prod_insert (Finset.notMem_erase a I)]  rw [← mul_assoc, reed_muller_four_block_concat_degree_seven_zz_mul_self]private lemma reed_muller_four_block_concat_degree_seven_monomial_mul {s : ℕ} (I J : Finset (Fin s)) :    (monomial I * monomial J : (Fin s → ZMod 2) → ZMod 2) = monomial (I ∪ J) := by  induction I using Finset.induction with  | empty => funext x; simp [monomial]  | insert a I ha ih =>    rw [Finset.insert_union, ← reed_muller_four_block_concat_degree_seven_single_not_mem a I ha,      mul_assoc, ih]    by_cases haJ : a ∈ J    · rw [reed_muller_four_block_concat_degree_seven_single_mem a (I ∪ J) (Finset.mem_union_right I haJ),        Finset.insert_eq_of_mem (Finset.mem_union_right I haJ)]    · rw [reed_muller_four_block_concat_degree_seven_single_not_mem a (I ∪ J) (by simp [ha, haJ])]private lemma reed_muller_four_block_concat_degree_seven_monomial_mem {s r : ℕ} (T : Finset (Fin s))    (hT : T.card ≤ r) : monomial T ∈ reed_muller_code r s :=  Submodule.subset_span ⟨T, hT, rfl⟩private lemma reed_muller_four_block_concat_degree_seven_mul_monomial_mem {s r : ℕ}    (T : Finset (Fin s)) (f : (Fin s → ZMod 2) → ZMod 2) (hf : f ∈ reed_muller_code r s) :    monomial T * f ∈ reed_muller_code (r + T.card) s := by  induction hf using Submodule.span_induction with  | mem x hx =>      obtain ⟨U, hU, rfl⟩ := hx      rw [reed_muller_four_block_concat_degree_seven_monomial_mul]      refine reed_muller_code_mono ?_ (reed_muller_four_block_concat_degree_seven_monomial_mem _ (le_refl _))      have := Finset.card_union_le T U      omega  | zero => simp  | add x y hx hy ihx ihy =>      rw [mul_add]      exact Submodule.add_mem _ ihx ihy  | smul a x hx ih =>      rw [show monomial T * (a • x) = a • (monomial T * x) from by        funext v; simp [Pi.mul_apply, smul_eq_mul]; ring]      exact Submodule.smul_mem _ a ihprivate lemma reed_muller_four_block_concat_degree_seven_lift_mem {m k r : ℕ}    {g : (Fin m → ZMod 2) → ZMod 2} (hg : g ∈ reed_muller_code r m) :    (fun v : Fin (m + k) → ZMod 2 => g (fun i => v (Fin.castAdd k i))) ∈      reed_muller_code r (m + k) := by  induction hg using Submodule.span_induction with  | mem x hx =>      obtain ⟨U, hU, rfl⟩ := hx      have heq : (fun v : Fin (m + k) → ZMod 2 => monomial U (fun i => v (Fin.castAdd k i)))          = monomial (U.image (Fin.castAdd k)) := by        funext v        simp only [monomial]        exact (Finset.prod_image (f := v) (g := Fin.castAdd k)          (fun x _ y _ h => Fin.castAdd_injective m k h)).symm      rw [heq]      exact reed_muller_four_block_concat_degree_seven_monomial_mem _        (by rw [Finset.card_image_of_injective _ (Fin.castAdd_injective m k)]; exact hU)  | zero =>      have h : (fun v : Fin (m + k) → ZMod 2 =>          (0 : (Fin m → ZMod 2) → ZMod 2) (fun i => v (Fin.castAdd k i))) = 0 := by        funext v; rfl      rw [h]; exact Submodule.zero_mem _  | add x y hx hy ihx ihy =>      have h : (fun v : Fin (m + k) → ZMod 2 => (x + y) (fun i => v (Fin.castAdd k i)))          = (fun v => x (fun i => v (Fin.castAdd k i)))            + (fun v => y (fun i => v (Fin.castAdd k i))) := by funext v; rfl      rw [h]; exact Submodule.add_mem _ ihx ihy  | smul a x hx ih =>      have h : (fun v : Fin (m + k) → ZMod 2 => (a • x) (fun i => v (Fin.castAdd k i)))          = a • (fun v => x (fun i => v (Fin.castAdd k i))) := by funext v; rfl      rw [h]; exact Submodule.smul_mem _ a ih/-- The four-block concatenation g_0 || g_1 || g_2 || (g_1 + g_2 + g_3) of functions g_0, g_3 in RM(5, 12) and g_1, g_2 in RM(6, 12) lies in RM(7, 14). -/theorem reed_muller_four_block_concat_degree_seven    (g0 g3 : (Fin 12 → ZMod 2) → ZMod 2) (g1 g2 : (Fin 12 → ZMod 2) → ZMod 2)    (hg0 : g0 ∈ reed_muller_code 5 12)    (hg3 : g3 ∈ reed_muller_code 5 12)    (hg1 : g1 ∈ reed_muller_code 6 12)    (hg2 : g2 ∈ reed_muller_code 6 12) :    four_block_concat g0 g1 g2 (g1 + g2 + g3) ∈ reed_muller_code 7 14 := by  rw [four_block_concat_reduced]  simp only []  let A : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g0 (fun i => v (Fin.castAdd 2 i))  let B : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g1 (fun i => v (Fin.castAdd 2 i))  let C : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g2 (fun i => v (Fin.castAdd 2 i))  let D : (Fin 14 → ZMod 2) → ZMod 2 := fun v => g3 (fun i => v (Fin.castAdd 2 i))  have hA : A ∈ reed_muller_code 5 14 :=    reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 5) hg0  have hB : B ∈ reed_muller_code 6 14 :=    reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 6) hg1  have hC : C ∈ reed_muller_code 6 14 :=    reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 6) hg2  have hD : D ∈ reed_muller_code 5 14 :=    reed_muller_four_block_concat_degree_seven_lift_mem (m := 12) (k := 2) (r := 5) hg3  have hA7 : A ∈ reed_muller_code 7 14 := reed_muller_code_mono (by norm_num) hA  have ht1 : monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 := by    have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem      ({(12 : Fin 14)} : Finset (Fin 14)) A hA    rw [Finset.card_singleton] at h    exact reed_muller_code_mono (by norm_num) h  have ht2 : monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 := by    have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem      ({(13 : Fin 14)} : Finset (Fin 14)) A hA    rw [Finset.card_singleton] at h    exact reed_muller_code_mono (by norm_num) h  have ht12 : monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 := by    have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem      ({(12 : Fin 14), 13} : Finset (Fin 14)) A hA    have hc : ({(12 : Fin 14), 13} : Finset (Fin 14)).card = 2 := by simp    rw [hc] at h    exact reed_muller_code_mono (by norm_num) h  have ht3 : monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B ∈ reed_muller_code 7 14 := by    have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem      ({(12 : Fin 14)} : Finset (Fin 14)) B hB    rw [Finset.card_singleton] at h    exact reed_muller_code_mono (by norm_num) h  have ht4 : monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C ∈ reed_muller_code 7 14 := by    have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem      ({(13 : Fin 14)} : Finset (Fin 14)) C hC    rw [Finset.card_singleton] at h    exact reed_muller_code_mono (by norm_num) h  have ht5 : monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * D ∈ reed_muller_code 7 14 := by    have h := reed_muller_four_block_concat_degree_seven_mul_monomial_mem      ({(12 : Fin 14), 13} : Finset (Fin 14)) D hD    have hc : ({(12 : Fin 14), 13} : Finset (Fin 14)).card = 2 := by simp    rw [hc] at h    exact reed_muller_code_mono (by norm_num) h  have s1 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 :=    Submodule.add_mem _ hA7 ht1  have s2 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 :=    Submodule.add_mem _ s1 ht2  have s3 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A ∈ reed_muller_code 7 14 :=    Submodule.add_mem _ s2 ht12  have s4 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B ∈ reed_muller_code 7 14 :=    Submodule.add_mem _ s3 ht3  have s5 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C ∈ reed_muller_code 7 14 :=    Submodule.add_mem _ s4 ht4  have s6 : A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * D ∈ reed_muller_code 7 14 :=    Submodule.add_mem _ s5 ht5  have key : (fun v : Fin (12+2) → ZMod 2 =>      (1 + v (Fin.natAdd 12 (0 : Fin 2))) * (1 + v (Fin.natAdd 12 (1 : Fin 2)))        * g0 (fun i => v (Fin.castAdd 2 i))      + v (Fin.natAdd 12 (0 : Fin 2)) * g1 (fun i => v (Fin.castAdd 2 i))      + v (Fin.natAdd 12 (1 : Fin 2)) * g2 (fun i => v (Fin.castAdd 2 i))      + v (Fin.natAdd 12 (0 : Fin 2)) * v (Fin.natAdd 12 (1 : Fin 2))        * g3 (fun i => v (Fin.castAdd 2 i)))      = A + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * A      + monomial ({(12 : Fin 14)} : Finset (Fin 14)) * B      + monomial ({(13 : Fin 14)} : Finset (Fin 14)) * C      + monomial ({(12 : Fin 14), 13} : Finset (Fin 14)) * D := by    funext v    simp [A, B, C, D, monomial]    ring  rw [key]  exact s6
See it in the graphDiscuss this resultChallenge it