AFTD Auto-Formalizing Theoretical Domains

binary_quadratic_twice_lift_four_parities_of_fourth_difference

theoremverified

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

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.

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

    lines 13–14

    uses binary_quadratic_decomposable_mod_linear_of_fourth_difference

      obtain ⟨a,b,l,habl⟩ := binary_quadratic_decomposable_mod_linear_of_fourth_difference Q hfour
      refine ⟨a,b,l,?_⟩
  2. 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)$.

    lines 15–16

      intro v
      rw [habl]
  3. 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}}$.

    lines 17–19

    uses binary_four_parity_elimination, CharTwo.add_self_eq_zero, ZMod.val_zero, Nat.cast_zero, mul_zero, zero_add

      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
  4. 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}}$.

    line 20

      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

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