AFTD Auto-Formalizing Theoretical Domains

binary_quadratic_polar_rank_le_two_of_parity_lift

theoremverified

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

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.

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

    line 9

    uses binary_quadratic_polar_rank_le_two_of_fourth_difference

      apply binary_quadratic_polar_rank_le_two_of_fourth_difference Q
  2. The 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.

    lines 10–12

    uses parity_phase_fourth_difference

      intro 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

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