binary_quadratic_polar_rank_le_two_of_fourth_difference
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
- binary_quartic_relations_rank_le_twoA finite binary matrix satisfying all the four-index alternating relations has rank at most two.
- binary_quadratic_polar_quartic_relationIf twice the binary lift of a quadratic form has zero fourth alternating difference on every four-direction cube, its polar bilinear form…
- Used by 1
- binary_quadratic_polar_rank_le_two_of_parity_liftIf twice the binary lift of a quadratic form is a finite parity-phase polynomial modulo eight, its polar matrix has rank at most two.
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.
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.
uses
binary_quartic_relations_rank_le_twoapply binary_quartic_relations_rank_le_twoThe 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.
uses
binary_quadratic_polar_quartic_relationintro 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
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_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)