AFTD Auto-Formalizing Theoretical Domains

binary_quadratic_polar_rank_le_two_of_fourth_difference

theoremverified

For a quadratic form on a finite binary coordinate space, vanishing of every fourth difference of twice its binary lift forces the polar matrix to have rank at most two.

Statement

theorem binary_quadratic_polar_rank_le_two_of_fourth_difference {n : ℕ}
    (Q : QuadraticForm (ZMod 2) (Fin n → ZMod 2))
    (hfour : ∀ u : Fin 4 → (Fin n → ZMod 2),
      (∑ 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) :
    (Matrix.of (fun i j : Fin n =>
      Q.polarBilin (Pi.single i 1) (Pi.single j 1))).rank ≤ 2
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
Used by 1

The proof, explained

The rank bound is deduced from an algebraic criterion for matrices over $\mathbb{Z}/2\mathbb{Z}$: any matrix whose entries satisfy the quartic relation $M_{i j} M_{k l} + M_{i k} M_{j l} + M_{i l} M_{j k} = 0$ for all indices has rank at most two. The assumption that all fourth differences vanish guarantees that the polar bilinear form of $Q$ satisfies this quartic identity on any four vectors. Evaluating this identity on the standard basis vectors verifies the matrix condition and completes the proof.

  1. To show that the polar matrix has rank at most 2, it suffices to show that its entries satisfy the quartic relation $M_{i j} M_{k l} + M_{i k} M_{j l} + M_{i l} M_{j k} = 0$ for all indices $i, j, k, l$.

    Applying the lemma `binary_quartic_relations_rank_le_two` reduces the rank bound $\operatorname{rank}(M) \le 2$ on the binary matrix to verifying this Plücker-type algebraic relation for all quadruples of indices.

    line 9

    uses binary_quartic_relations_rank_le_two

      apply binary_quartic_relations_rank_le_two
  2. The polar matrix satisfies the quartic relation for every quadruple of indices.

    Fix arbitrary indices $i, j, k, l$. The entries of the polar matrix are defined by evaluating the polar bilinear form on the standard basis vectors $e_i, e_j, e_k, e_l$ (written as `Pi.single · 1`). The lemma `binary_quadratic_polar_quartic_relation` establishes that the polar form satisfies this quartic relation on any four vectors whenever the fourth-difference hypothesis `hfour` holds, which immediately dispatches the goal.

    lines 10–12

    uses binary_quadratic_polar_quartic_relation

      intro i j k l
      exact binary_quadratic_polar_quartic_relation Q hfour
        (Pi.single i 1) (Pi.single j 1) (Pi.single k 1) (Pi.single l 1)
binary_quartic_relations_rank_le_two
A matrix over $\mathbb{Z}/2\mathbb{Z}$ has rank at most 2 if its entries satisfy $M_{i j} M_{k l} + M_{i k} M_{j l} + M_{i l} M_{j k} = 0$ for all indices $i, j, k, l$.
binary_quadratic_polar_quartic_relation
If every fourth difference of twice the binary lift of a quadratic form $Q$ over $\mathbb{Z}/2\mathbb{Z}$ vanishes, then its polar bilinear form satisfies $B(v, w) B(y, z) + B(v, y) B(w, z) + B(v, z) B(w, y) = 0$ for all vectors $v, w, y, z$.

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_polar_rank_le_two_of_fourth_difference {n : ℕ}    (Q : QuadraticForm (ZMod 2) (Fin n → ZMod 2))    (hfour : ∀ u : Fin 4 → (Fin n → ZMod 2),      (∑ 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) :    (Matrix.of (fun i j : Fin n =>      Q.polarBilin (Pi.single i 1) (Pi.single j 1))).rank ≤ 2 := by  apply binary_quartic_relations_rank_le_two  intro i j k l  exact binary_quadratic_polar_quartic_relation Q hfour    (Pi.single i 1) (Pi.single j 1) (Pi.single k 1) (Pi.single l 1)
See it in the graphDiscuss this resultChallenge it