four_block_concat_reduced
For 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 (g1 + g2 + g3) is identically equal to the function sending v to (1 + y1) * (1 + y2) * g0 x + y1 * g1 x + y2 * g2 x + y1 * y2 * g3 x, where x = fun i => v (Fin.castAdd 2 i), y1 = v (Fin.natAdd m 0), and y2 = v (Fin.natAdd m 1).
Statement
theorem four_block_concat_reduced {m : ℕ} (g0 g1 g2 g3 : (Fin m → ZMod 2) → ZMod 2) : four_block_concat g0 g1 g2 (g1 + g2 + g3) = fun v => let x : Fin m → ZMod 2 := fun i => v (Fin.castAdd 2 i) let y1 : ZMod 2 := v (Fin.natAdd m 0) let y2 : ZMod 2 := v (Fin.natAdd m 1) (1 + y1) * (1 + y2) * g0 x + y1 * g1 x + y2 * g2 x + y1 * y2 * g3 x
- Source
- arXiv:2610.29807, Lemma 3.1
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 1
- reed_muller_four_block_concat_degree_sevenLet 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…
Read back from the Lean
For any natural number $m$ and any functions $g_0, g_1, g_2, g_3 : (\mathrm{Fin}\ m \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$, the function $\mathrm{four\_block\_concat}\ g_0\ g_1\ g_2\ (g_1 + g_2 + g_3)$ is equal to the function mapping each $v : \mathrm{Fin}\ (m + 2) \to \mathbb{Z}/2\mathbb{Z}$ to: $$(1 + y_1)(1 + y_2) g_0(x) + y_1 g_1(x) + y_2 g_2(x) + y_1 y_2 g_3(x)$$ where: - $x : \mathrm{Fin}\ m \to \mathbb{Z}/2\mathbb{Z}$ is defined by $x(i) = v(\mathrm{Fin.castAdd}\ 2\ i)$ (the restriction of $v$ to the first $m$ indices), - $y_1 = v(\mathrm{Fin.natAdd}\ m\ 0)$ (the element at index $m$), and - $y_2 = v(\mathrm{Fin.natAdd}\ m\ 1)$ (the element at index $m + 1$).
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 identity is proved by pointwise evaluation and polynomial simplification over ZMod 2. By function extensionality, the functions are evaluated on an arbitrary input vector v, reducing the theorem to an equality between two polynomials in the coordinates y₁, y₂ and the function values gᵢ x. Expanding both sides into ring normal form and simplifying using the characteristic 2 identity 2 = 0 eliminates the cross terms with coefficient 2, showing that the two functions are identically equal.
The equality of functions reduces to an algebraic identity between the expanded expressions evaluated at an arbitrary input vector v.
Applying function extensionality (`funext`) introduces an arbitrary vector v : Fin (m + 2) → ZMod 2. Unfolding the definition of `four_block_concat` and rewriting function addition pointwise with `Pi.add_apply` replaces (g₁ + g₂ + g₃) x with g₁ x + g₂ x + g₃ x, turning the goal into an equality between two explicit polynomial expressions in ZMod 2.
uses
four_block_concat,Pi.add_applyfunext v simp only [four_block_concat, Pi.add_apply]
2 = 0 in ZMod 2.
Because ZMod 2 has characteristic 2, the integer 2 is zero in this ring. This auxiliary fact h₂ is established by direct computation (`decide`).
have h2 : (2 : ZMod 2) = 0 := by decide
Both expressions are equal after normalizing polynomial terms and eliminating multiples of 2.
The `ring_nf` tactic expands both sides into polynomial normal form with integer coefficients. In this expanded form, the left-hand and right-hand sides are identical except that the left-hand side contains the additional terms 2 * y₁ * y₂ * g₁ x and 2 * y₁ * y₂ * g₂ x. Rewriting with h₂ (2 = 0) and simplifying via `mul_zero` and `add_zero` removes these terms, completing the proof.
uses
mul_zero,add_zeroring_nf simp only [h2, mul_zero, add_zero]
four_block_concat- The definition of four-block concatenation of functions f₀, f₁, f₂, f₃ on Fin m → ZMod 2 into a function on Fin (m + 2) → ZMod 2, defined by (1 + y₁) * (1 + y₂) * f₀ x + y₁ * (1 + y₂) * f₁ x + (1 + y₁) * y₂ * f₂ x + y₁ * y₂ * f₃ x.
Pi.add_apply- Pointwise addition of functions: (f + g) i = f i + g i.
mul_zero- Multiplication by zero on the right: a * 0 = 0.
add_zero- Addition of zero on the right: a + 0 = a.
- Lean's `ring_nf` tactic normalizes polynomials with integer coefficients rather than working directly in characteristic 2. Consequently, it produces terms with an integer coefficient of 2 (such as `2 * y1 * y2 * g1 x`) instead of reducing them to 0, requiring the subsequent explicit reduction using `2 = 0` in `ZMod 2`.
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.
/-- Over characteristic 2, the four-block concatenation g_0 || g_1 || g_2 || (g_1 + g_2 + g_3) simplifies to (1 + y_1)(1 + y_2) g_0 + y_1 g_1 + y_2 g_2 + y_1 y_2 g_3. -/theorem four_block_concat_reduced {m : ℕ} (g0 g1 g2 g3 : (Fin m → ZMod 2) → ZMod 2) : four_block_concat g0 g1 g2 (g1 + g2 + g3) = fun v => let x : Fin m → ZMod 2 := fun i => v (Fin.castAdd 2 i) let y1 : ZMod 2 := v (Fin.natAdd m 0) let y2 : ZMod 2 := v (Fin.natAdd m 1) (1 + y1) * (1 + y2) * g0 x + y1 * g1 x + y2 * g2 x + y1 * y2 * g3 x := by funext v simp only [four_block_concat, Pi.add_apply] have h2 : (2 : ZMod 2) = 0 := by decide ring_nf simp only [h2, mul_zero, add_zero]