binary_four_parity_elimination
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
- binary_quadratic_twice_lift_four_parities_of_fourth_differenceUnder the fourth-difference condition, twice the binary quadratic lift has an explicit representation by four lifted linear forms and one…
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`.
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$.
revert a b u l
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.
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
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.
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