low_half_mul3_gate5_expansion
Expansion of the sixth AND gate g_5 over GF(2): (g_1 + a_1)(g_2 + b_1) equals a_0 a_1 b_0 b_1 + g_1 + g_2 + a_1 b_1.
Statement
theorem low_half_mul3_gate5_expansion (v : Fin 6 → ZMod 2) :
(v 0 * v 4 + v 1) * (v 1 * v 3 + v 4) =
v 0 * v 1 * v 3 * v 4 + v 0 * v 4 + v 1 * v 3 + v 1 * v 4- Source
- arXiv:2611.15992 Section 3
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- monomial_mulFor 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…
- Used by 1
- low_half_mul3_six_and_upper_boundFor every input vector v : Fin 6 → ZMod 2 and index k : Fin 3, the k-th output of the explicit six-AND circuit…
Read back from the Lean
For every function $v : \text{Fin } 6 \to \mathbb{Z}/2\mathbb{Z}$, $(v(0) \cdot v(4) + v(1)) \cdot (v(1) \cdot v(3) + v(4)) = v(0) \cdot v(1) \cdot v(3) \cdot v(4) + v(0) \cdot v(4) + v(1) \cdot v(3) + v(1) \cdot v(4)$ in $\mathbb{Z}/2\mathbb{Z}$.
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 proof expands the product of two linear combinations over ℤ/2ℤ and reduces the quadratic terms using idempotency. By applying the identity a² = a to v 4 and v 1, the terms v 0 * (v 4)² and (v 1)² * v 3 simplify to v 0 * v 4 and v 1 * v 3, matching the target expression. The linear_combination tactic completes the verification by showing that the difference between the two sides reduces to a linear combination of these two idempotency relations.
v 4 * v 4 = v 4 and v 1 * v 1 = v 1
In the field ℤ/2ℤ, every element is idempotent under multiplication. Applying monomial_mul_zmod2_mul_self to v 4 and v 1 establishes that (v 4)² = v 4 and (v 1)² = v 1.
uses
monomial_mul_zmod2_mul_selfhave h4 : v 4 * v 4 = v 4 := monomial_mul_zmod2_mul_self (v 4) have h1 : v 1 * v 1 = v 1 := monomial_mul_zmod2_mul_self (v 1)
(v 0 * v 4 + v 1) * (v 1 * v 3 + v 4) = v 0 * v 1 * v 3 * v 4 + v 0 * v 4 + v 1 * v 3 + v 1 * v 4
Expanding the product on the left-hand side produces v 0 * v 1 * v 3 * v 4 + v 0 * (v 4 * v 4) + (v 1 * v 1) * v 3 + v 1 * v 4. Subtracting the right-hand side leaves exactly v 0 * (v 4 * v 4 - v 4) + v 3 * (v 1 * v 1 - v 1), which vanishes by the two established idempotence identities. The linear_combination tactic verifies this polynomial identity.
linear_combination (v 0) * h4 + (v 3) * h1
monomial_mul_zmod2_mul_self- Every element a in ℤ/2ℤ satisfies a * a = a.
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.
/-- Algebraic expansion of gate g_5 over GF(2). -/theorem low_half_mul3_gate5_expansion (v : Fin 6 → ZMod 2) : (v 0 * v 4 + v 1) * (v 1 * v 3 + v 4) = v 0 * v 1 * v 3 * v 4 + v 0 * v 4 + v 1 * v 3 + v 1 * v 4 := by have h4 : v 4 * v 4 = v 4 := monomial_mul_zmod2_mul_self (v 4) have h1 : v 1 * v 1 = v 1 := monomial_mul_zmod2_mul_self (v 1) linear_combination (v 0) * h4 + (v 3) * h1