binary_quadratic_polar_rank_le_two_of_parity_lift
If twice the binary lift of a quadratic form is a finite parity-phase polynomial modulo eight, its polar matrix has rank at most two.
Statement
theorem binary_quadratic_polar_rank_le_two_of_parity_lift {n : ℕ} {ι : Type*} [Fintype ι] (Q : QuadraticForm (ZMod 2) (Fin n → ZMod 2)) (c : ι → ZMod 8) (L : ι → (Fin n → ZMod 2) →ₗ[ZMod 2] ZMod 2) (hrepr : ∀ v, 2 * ((Q v).val : ZMod 8) = ∑ j : ι, c j * ((L j v).val : ZMod 8)) : (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_quadratic_polar_rank_le_two_of_fourth_differenceFor a quadratic form on a finite binary coordinate space, vanishing of every fourth difference of twice its binary lift forces the polar…
- parity_phase_fourth_differenceEvery finite Z/8 linear combination of lifted binary linear forms has zero fourth alternating difference on each four-direction cube.
The proof, explained
The proof reduces the rank bound on the polar matrix of Q to showing that the fourth directional difference of twice the binary lift of Q vanishes modulo 8, via binary_quadratic_polar_rank_le_two_of_fourth_difference. Substituting the assumed representation of 2 * Q as a sum of linear forms modulo 8, this fourth difference vanishes identically by parity_phase_fourth_difference.
It suffices to show that the fourth directional difference of v ↦ 2 * (Q(v) mod 8) vanishes identically for all quadruples of vectors u.
Applying binary_quadratic_polar_rank_le_two_of_fourth_difference reduces the rank bound on the polar matrix of Q to proving that the alternating sum ∑_{x ∈ {0,1}⁴} (-1)^(∑ x_i) · 2(Q(∑ x_i u_i) mod 8) equals 0 in ZMod 8 for every quadruple u.
uses
binary_quadratic_polar_rank_le_two_of_fourth_differenceapply binary_quadratic_polar_rank_le_two_of_fourth_difference QThe fourth directional difference of v ↦ 2 * (Q(v) mod 8) is identically zero for any quadruple u.
Fix an arbitrary quadruple of vectors u. We substitute the hypothesis hrepr, which expresses 2 * (Q(v) mod 8) as the parity-phase sum ∑_j c_j (L_j(v) mod 8). The resulting fourth difference vanishes by parity_phase_fourth_difference.
uses
parity_phase_fourth_differenceintro u simp_rw [hrepr] exact parity_phase_fourth_difference c L u
binary_quadratic_polar_rank_le_two_of_fourth_difference- If the fourth directional difference of twice the binary lift of a quadratic form Q over (ZMod 2)^n vanishes everywhere modulo 8, then the polar matrix of Q has rank at most two.
parity_phase_fourth_difference- The fourth directional difference of any parity-phase polynomial (a linear combination modulo 8 of {0, 1}-valued linear forms) on an F_2-vector space is identically zero modulo 8.
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_parity_lift {n : ℕ} {ι : Type*} [Fintype ι] (Q : QuadraticForm (ZMod 2) (Fin n → ZMod 2)) (c : ι → ZMod 8) (L : ι → (Fin n → ZMod 2) →ₗ[ZMod 2] ZMod 2) (hrepr : ∀ v, 2 * ((Q v).val : ZMod 8) = ∑ j : ι, c j * ((L j v).val : ZMod 8)) : (Matrix.of (fun i j : Fin n => Q.polarBilin (Pi.single i 1) (Pi.single j 1))).rank ≤ 2 := by apply binary_quadratic_polar_rank_le_two_of_fourth_difference Q intro u simp_rw [hrepr] exact parity_phase_fourth_difference c L u