binary_quadratic_twice_lift_four_parities_of_fourth_difference
Under the fourth-difference condition, twice the binary quadratic lift has an explicit representation by four lifted linear forms and one even-coefficient linear correction modulo eight.
Statement
theorem binary_quadratic_twice_lift_four_parities_of_fourth_difference {V : Type*} [AddCommGroup V] [Module (ZMod 2) V] (Q : QuadraticForm (ZMod 2) V) (hfour : ∀ u : Fin 4 → V, (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (2 * ((Q (∑ i : Fin 4, x i • u i)).val : ZMod 8))) = 0) : ∃ a b l : V →ₗ[ZMod 2] ZMod 2, ∀ v, 2 * ((Q v).val : ZMod 8) = ((l v).val : ZMod 8) + ((l v+a v).val : ZMod 8) + ((l v+b v).val : ZMod 8) + ((l v+a v+b v).val : ZMod 8) - 2 * ((a v+b v+l v).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- Built on 2
- binary_four_parity_eliminationFor 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…
- binary_quadratic_decomposable_mod_linear_of_fourth_differenceIf twice the binary lift of a quadratic form has vanishing fourth differences on all cubes, the form is one product of two linear forms…
The proof, explained
Under the fourth-difference condition, the quadratic form $Q$ decomposes as $Q(v) = a(v)b(v) + l(v)$ for linear forms $a, b, l$. For each vector $v$, setting $u = l(v)$ in the algebraic identity binary_four_parity_elimination causes the cross term containing $u + l = l(v) + l(v) = 0$ to vanish in characteristic 2. The resulting simplified relation rearranges directly into the desired five-term parity representation of $2(Q(v))_{\mathrm{val}}$ modulo 8.
There exist linear forms $a, b, l : V \to \mathbb{Z}/2\mathbb{Z}$ decomposing $Q$ as $Q(v) = a(v)b(v) + l(v)$, which serve as witnesses for the existential statement.
By binary_quadratic_decomposable_mod_linear_of_fourth_difference, the vanishing fourth-difference hypothesis implies that $Q$ decomposes into the product of two linear forms plus a linear form. We supply these three forms as the witnesses.
uses
binary_quadratic_decomposable_mod_linear_of_fourth_differenceobtain ⟨a,b,l,habl⟩ := binary_quadratic_decomposable_mod_linear_of_fourth_difference Q hfour refine ⟨a,b,l,?_⟩
For an arbitrary vector $v \in V$, the goal reduces to an identity where $Q(v)$ is replaced by $a(v)b(v) + l(v)$.
We fix an arbitrary vector $v \in V$ and rewrite $Q(v)$ using the decomposition $Q(v) = a(v)b(v) + l(v)$.
intro v rw [habl]
In $\mathbb{Z}/8\mathbb{Z}$, the sum of the four parity lifts minus $2(a(v)b(v) + l(v))_{\mathrm{val}}$ equals $2(a(v) + b(v) + l(v))_{\mathrm{val}}$.
We instantiate the algebraic identity binary_four_parity_elimination with $a = a(v)$, $b = b(v)$, and $u = l = l(v)$. The right-hand side has a factor of $(l(v) + l(v))_{\mathrm{val}}$. In characteristic 2, $l(v) + l(v) = 0$ by CharTwo.add_self_eq_zero, and since the integer lift of 0 is 0 (ZMod.val_zero, Nat.cast_zero), multiplying by zero eliminates that entire term (mul_zero, zero_add), leaving only $2(a(v) + b(v) + l(v))_{\mathrm{val}}$.
uses
binary_four_parity_elimination,CharTwo.add_self_eq_zero,ZMod.val_zero,Nat.cast_zero,mul_zero,zero_addhave he := binary_four_parity_elimination (a v) (b v) (l v) (l v) simp only [CharTwo.add_self_eq_zero, ZMod.val_zero, Nat.cast_zero, mul_zero, zero_add] at he
The desired identity holds.
Rearranging the simplified identity (subtracting it from both sides) directly yields the equation $2(a(v)b(v) + l(v))_{\mathrm{val}} = (l(v))_{\mathrm{val}} + (l(v)+a(v))_{\mathrm{val}} + (l(v)+b(v))_{\mathrm{val}} + (l(v)+a(v)+b(v))_{\mathrm{val}} - 2(a(v)+b(v)+l(v))_{\mathrm{val}}$.
linear_combination -he
binary_quadratic_decomposable_mod_linear_of_fourth_difference- A quadratic form over $\mathbb{Z}/2\mathbb{Z}$ whose fourth difference vanishes modulo 8 decomposes as $Q(v) = a(v)b(v) + l(v)$ for some linear forms $a, b, l$.
binary_four_parity_elimination- An identity in $\mathbb{Z}/8\mathbb{Z}$ relating the sum of four parity evaluations to a product term involving $u+l$ and a linear term $a+b+u$.
CharTwo.add_self_eq_zero- In characteristic 2, adding any element to itself gives zero ($x + x = 0$).
ZMod.val_zero- The integer lift of $0 \in \mathbb{Z}/n\mathbb{Z}$ to $\{0, \dots, n-1\}$ is $0$.
Nat.cast_zero- The canonical coercion of $0 \in \mathbb{N}$ into an additive monoid with one is $0$.
mul_zero- Multiplying any element by zero on the right yields zero ($a \cdot 0 = 0$).
zero_add- Adding zero on the left is the identity ($0 + 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.
theorem binary_quadratic_twice_lift_four_parities_of_fourth_difference {V : Type*} [AddCommGroup V] [Module (ZMod 2) V] (Q : QuadraticForm (ZMod 2) V) (hfour : ∀ u : Fin 4 → V, (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (2 * ((Q (∑ i : Fin 4, x i • u i)).val : ZMod 8))) = 0) : ∃ a b l : V →ₗ[ZMod 2] ZMod 2, ∀ v, 2 * ((Q v).val : ZMod 8) = ((l v).val : ZMod 8) + ((l v+a v).val : ZMod 8) + ((l v+b v).val : ZMod 8) + ((l v+a v+b v).val : ZMod 8) - 2 * ((a v+b v+l v).val : ZMod 8) := by obtain ⟨a,b,l,habl⟩ := binary_quadratic_decomposable_mod_linear_of_fourth_difference Q hfour refine ⟨a,b,l,?_⟩ intro v rw [habl] have he := binary_four_parity_elimination (a v) (b v) (l v) (l v) simp only [CharTwo.add_self_eq_zero, ZMod.val_zero, Nat.cast_zero, mul_zero, zero_add] at he linear_combination -he