AFTD Auto-Formalizing Theoretical Domains

low_half_mul3_gate5_expansion

theoremverified

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

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.

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

    lines 5–6

    uses monomial_mul_zmod2_mul_self

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

    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.

    line 7

      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

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