AFTD Auto-Formalizing Theoretical Domains

binary_four_parity_elimination

theoremverified

For binary a,b,u,l, the sum of the four lifts u,u+a,u+b,u+a+b minus twice the lift of a*b+l equals (2+4*lift(a*b+l))*lift(u+l)+2*lift(a+b+u), modulo eight.

Statement

theorem binary_four_parity_elimination (a b u l : ZMod 2) :
    ((u.val : ZMod 8) + ((u+a).val : ZMod 8) +
      ((u+b).val : ZMod 8) + ((u+a+b).val : ZMod 8)) -
        2 * ((a*b+l).val : ZMod 8) =
      (2 + 4 * ((a*b+l).val : ZMod 8)) * ((u+l).val : ZMod 8) +
        2 * ((a+b+u).val : ZMod 8)
Source
Supporting algebra for OP-3, arXiv:2610.01024, Section E.1; developed in deep session IN-184. These helpers do not establish a lower bound for arbitrary circuit gate lists.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem establishes an algebraic identity in $\mathbb{Z}/8\mathbb{Z}$ relating the integer lifts of several linear combinations of binary variables $a, b, u, l \in \mathbb{Z}/2\mathbb{Z}$. Since each variable can take only two values, the domain $(\mathbb{Z}/2\mathbb{Z})^4$ has only 16 elements. The proof generalizes over all four variables and verifies the identity by exhaustive finite case evaluation via `decide`.

  1. It suffices to prove that the identity holds for all $a, b, u, l \in \mathbb{Z}/2\mathbb{Z}$.

    Reverting the four variables $a, b, u, l$ places them back into the goal under universal quantifiers, yielding a closed, universally quantified proposition over the finite domain $(\mathbb{Z}/2\mathbb{Z})^4$.

    line 10

      revert a b u l
  2. The identity holds for all $a, b, u, l \in \mathbb{Z}/2\mathbb{Z}$. automation

    Because $\mathbb{Z}/2\mathbb{Z}$ has only two elements, universal quantification over $(\mathbb{Z}/2\mathbb{Z})^4$ reduces to evaluating the identity on $2^4 = 16$ cases. The `decide` tactic checks every case by finite computational evaluation, completing the proof.

    line 11

      decide

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

set_option maxRecDepth 100000set_option maxHeartbeats 50000000theorem binary_four_parity_elimination (a b u l : ZMod 2) :    ((u.val : ZMod 8) + ((u+a).val : ZMod 8) +      ((u+b).val : ZMod 8) + ((u+a+b).val : ZMod 8)) -        2 * ((a*b+l).val : ZMod 8) =      (2 + 4 * ((a*b+l).val : ZMod 8)) * ((u+l).val : ZMod 8) +        2 * ((a+b+u).val : ZMod 8) := by  revert a b u l  decide
See it in the graphDiscuss this resultChallenge it