AFTD Auto-Formalizing Theoretical Domains

binary_quadratic_decomposable_mod_linear_of_fourth_difference

theoremverified

If twice the binary lift of a quadratic form has vanishing fourth differences on all cubes, the form is one product of two linear forms plus a linear form.

Statement

theorem binary_quadratic_decomposable_mod_linear_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, Q v = a v*b v+l v
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 proof decomposes the quadratic form Q over ℤ/2ℤ by first obtaining a decomposition of its associated polar bilinear form. The vanishing fourth difference hypothesis ensures that the polar bilinear form satisfies a quartic relation, which by a previous result allows it to be written as B(v, w) = a(v) b(w) + b(v) a(w) for two linear forms a and b. We then define l(v) = Q(v) - a(v) b(v) and show that l is linear: additivity follows from the cancellation of cross terms between Q and a * b, while scalar compatibility follows from the identity c² = c in ℤ/2ℤ. Finally, Q(v) = a(v) b(v) + l(v) holds by definition of l.

  1. There exist linear forms a, b : V →ₗ[ℤ/2ℤ] ℤ/2ℤ decomposing the polar bilinear form of Q as B(v, w) = a(v) b(w) + b(v) a(w).

    The hypothesis that twice the binary lift of Q has vanishing fourth differences on all cubes implies, via binary_quadratic_polar_quartic_relation, that the polar bilinear form B = Q.polarBilin satisfies the quartic relation 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. By binary_bilinear_quartic_relations_decomposable, any bilinear form over ℤ/2ℤ satisfying this identity can be written as B(v, w) = a(v) b(w) + b(v) a(w) for two linear forms a, b.

    lines 9–10

    uses binary_bilinear_quartic_relations_decomposable, binary_quadratic_polar_quartic_relation

      obtain ⟨a,b,hab⟩ := binary_bilinear_quartic_relations_decomposable Q.polarBilin
        (binary_quadratic_polar_quartic_relation Q hfour)
  2. The map l : V →ₗ[ℤ/2ℤ] ℤ/2ℤ given by l(x) = Q(x) - a(x) b(x) is a linear map.

    We define l(x) = Q(x) - a(x) b(x) and check the two linearity conditions: 1. Additivity: QuadraticMap.map_add expands Q(x + y) into Q(x) + Q(y) + polar(Q)(x, y), which QuadraticMap.polarBilin_apply_apply rewrites as Q.polarBilin(x, y). Using the linearity of a and b (via map_add) and the decomposition hab of the polar bilinear form, the cross term B(x, y) = a(x) b(y) + b(x) a(y) exactly cancels the cross term from (a(x) + a(y))(b(x) + b(y)), leaving the additivity identity to be closed by ring. 2. Homogeneity: Every element c ∈ ℤ/2ℤ satisfies c * c = c, verified by exhaustion via decide. Using QuadraticMap.map_smul, map_smul, and smul_eq_mul, the expression l(c • x) simplifies to (c * c) * Q(x) - (c * a(x)) * (c * b(x)) = (c * c) * (Q(x) - a(x) b(x)). Substituting c * c = c leaves c * l(x).

    lines 11–28

    uses QuadraticMap.map_add, QuadraticMap.polarBilin_apply_apply, map_add, QuadraticMap.map_smul, map_smul, smul_eq_mul

      let l : V →ₗ[ZMod 2] ZMod 2 := {
        toFun := fun x => Q x-a x*b x
        map_add' := by
          intro x y
          simp only [QuadraticMap.map_add Q, ← QuadraticMap.polarBilin_apply_apply,
            map_add, hab]
          ring
        map_smul' := by
          intro c x
          have hc : c*c=c := by
            have hh : ∀ t : ZMod 2, t*t=t := by decide
            exact hh c
          change Q (c • x)-a (c • x)*b (c • x)=c*(Q x-a x*b x)
          simp only [QuadraticMap.map_smul Q, map_smul, smul_eq_mul]
          calc
            (c*c)*Q x-(c*a x)*(c*b x)=(c*c)*(Q x-a x*b x) := by ring
            _ = c*(Q x-a x*b x) := by rw [hc]
      }
  3. The quadratic form decomposes as Q(v) = a(v) b(v) + l(v) for all v ∈ V.

    We provide a, b, and l as the witnesses. For any x ∈ V, the definition of l gives Q(x) = a(x) b(x) + (Q(x) - a(x) b(x)), which is an immediate algebraic identity verified by ring.

    lines 29–32

      refine ⟨a,b,l,?_⟩
      intro x
      change Q x=a x*b x+(Q x-a x*b x)
      ring
binary_bilinear_quartic_relations_decomposable
A bilinear form B over ℤ/2ℤ satisfying the quartic relation B(v, w) B(y, z) + B(v, y) B(w, z) + B(v, z) B(w, y) = 0 decomposes as B(v, w) = a(v) b(w) + b(v) a(w) for some linear forms a, b.
binary_quadratic_polar_quartic_relation
If twice the binary lift of a quadratic form Q has vanishing fourth differences on all cubes, its polar bilinear form satisfies the quartic relation B(v, w) B(y, z) + B(v, y) B(w, z) + B(v, z) B(w, y) = 0.
QuadraticMap.map_add
For any quadratic map f, f(x + y) = f(x) + f(y) + polar(f)(x, y).
QuadraticMap.polarBilin_apply_apply
Evaluating the polar bilinear form of Q at arguments m and y equals the polar form evaluated at m and y.
map_add
An additive map satisfies f(x + y) = f(x) + f(y).
QuadraticMap.map_smul
A quadratic map satisfies Q(a • x) = (a * a) • Q(x).
map_smul
A linear map preserves scalar multiplication: f(c • x) = c • f(x).
smul_eq_mul
Scalar multiplication of ring elements on the ring itself coincides with ring multiplication: a • b = a * b.

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_decomposable_mod_linear_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, Q v = a v*b v+l v := by  obtain ⟨a,b,hab⟩ := binary_bilinear_quartic_relations_decomposable Q.polarBilin    (binary_quadratic_polar_quartic_relation Q hfour)  let l : V →ₗ[ZMod 2] ZMod 2 := {    toFun := fun x => Q x-a x*b x    map_add' := by      intro x y      simp only [QuadraticMap.map_add Q, ← QuadraticMap.polarBilin_apply_apply,        map_add, hab]      ring    map_smul' := by      intro c x      have hc : c*c=c := by        have hh : ∀ t : ZMod 2, t*t=t := by decide        exact hh c      change Q (c • x)-a (c • x)*b (c • x)=c*(Q x-a x*b x)      simp only [QuadraticMap.map_smul Q, map_smul, smul_eq_mul]      calc        (c*c)*Q x-(c*a x)*(c*b x)=(c*c)*(Q x-a x*b x) := by ring        _ = c*(Q x-a x*b x) := by rw [hc]  }  refine ⟨a,b,l,?_⟩  intro x  change Q x=a x*b x+(Q x-a x*b x)  ring
See it in the graphDiscuss this resultChallenge it