reed_muller_four_block_concat_degree_seven
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.
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.
private lemma reed_muller_four_block_concat_degree_seven_zz_mul_self (a : ZMod 2) : a * a = a := by fin_cases a <;> rfl
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.
uses
Finset.prod_insertprivate 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]
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.
uses
Pi.mul_apply,Finset.insert_erase,Finset.prod_insert,Finset.notMem_erase,mul_assoc,reed_muller_four_block_concat_degree_seven_zz_mul_selfprivate 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]
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.
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_memprivate 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])]
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.
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_memprivate 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
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.
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_memprivate 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 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.
uses
four_block_concat_reduced,reed_muller_four_block_concat_degree_seven_lift_mem,reed_muller_code_monorw [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
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.
uses
reed_muller_four_block_concat_degree_seven_mul_monomial_mem,Finset.card_singleton,reed_muller_code_monohave 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
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.
uses
Submodule.add_memhave 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
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.
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.
- In characteristic 2, addition and subtraction coincide, so the expansion of (1 + y₁)(1 + y₂) is 1 + y₁ + y₂ + y₁ y₂ with all signs positive.
- The proof relies on five helper lemmas proved immediately beforehand in the same file: idempotence in ZMod 2, monomial multiplication rules, degree bounds for products with monomials, and invariance of Reed-Muller codes under variable lifting.
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.
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