AFTD Auto-Formalizing Theoretical Domains

binary_bilinear_quartic_relations_decomposable

theoremverified

A binary bilinear form satisfying all four-index alternating relations is the sum of two swapped products of linear functionals.

Statement

theorem binary_bilinear_quartic_relations_decomposable {V : Type*}
    [AddCommGroup V] [Module (ZMod 2) V]
    (B : LinearMap.BilinForm (ZMod 2) V)
    (hP : ∀ v w y z, B v w * B y z + B v y * B w z + B v z * B w y = 0) :
    ∃ a b : V →ₗ[ZMod 2] ZMod 2, ∀ v w, B v w = a v*b w+b v*a w
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
Used by 1

The proof, explained

The proof proceeds by case analysis on whether the bilinear form B is identically zero. If B = 0, the zero linear functionals decompose B trivially. Otherwise, there exist vectors k, l such that B(k, l) ≠ 0, which must equal 1 because the scalars lie in ℤ/2ℤ. Specializing the four-index alternating relation to (v, w, k, l) and using B(k, l) = 1 gives B(v, w) + B(v, k) B(w, l) + B(v, l) B(w, k) = 0. Since -x = x in characteristic 2, this yields B(v, w) = a(v)b(w) + b(v)a(w) for the linear functionals a = B(·, k) and b = B(·, l).

  1. If the bilinear form B is identically zero, the theorem holds with a = 0 and b = 0

    By classical excluded middle, we split into cases on whether B(v, w) = 0 for all v, w ∈ V. If B vanishes identically, choosing both linear functionals a and b to be the zero functional satisfies B(v, w) = 0 = 0 · 0 + 0 · 0 for all v, w.

    lines 6–8

      classical
      by_cases hz : ∀ v w, B v w = 0
      · exact ⟨0,0, by simp [hz]⟩
  2. There exist vectors k and l in V such that B(k, l) = 1

    In the non-zero case, pushing negation through the universal quantifier yields vectors k, l ∈ V with B(k, l) ≠ 0. Since the scalar ring is ℤ/2ℤ, every scalar is either 0 or 1 (checked by finite exhaustion via decide). Since B(k, l) ≠ 0, it must be 1 by resolve_left.

    lines 9–12

    uses resolve_left

      · push Not at hz
        obtain ⟨k,l,hkl⟩ := hz
        have h01 : ∀ t : ZMod 2, t=0 ∨ t=1 := by decide
        have hkl1 : B k l=1 := (h01 _).resolve_left hkl
  3. Choosing a = B(·, k) and b = B(·, l) reduces the problem to showing B(v, w) = B(v, k) B(w, l) + B(v, l) B(w, k) for all v, w

    We instantiate the existential witnesses with the linear functionals obtained by fixing the second argument of B to k and l respectively (represented in Lean by B.flip k and B.flip l). This leaves the decomposition equality to be verified for arbitrary v and w.

    line 13

        refine ⟨B.flip k, B.flip l, ?_⟩
  4. For arbitrary v, w ∈ V, the quartic relation specializes to B(v, w) + B(v, k) B(w, l) + B(v, l) B(w, k) = 0

    Let v, w ∈ V be given. Evaluating the assumed alternating relation hP on the four vectors (v, w, k, l) gives B(v, w) B(k, l) + B(v, k) B(w, l) + B(v, l) B(w, k) = 0. Substituting B(k, l) = 1 simplifies the first term to B(v, w) via mul_one.

    lines 14–16

    uses mul_one

        intro v w
        have h := hP v w k l
        rw [hkl1, mul_one] at h
  5. B(v, w) = B(v, k) B(w, l) + B(v, l) B(w, k), completing the proof

    Regrouping terms via associativity of addition (add_assoc), the relation B(v, w) + (B(v, k) B(w, l) + B(v, l) B(w, k)) = 0 implies B(v, w) = -(B(v, k) B(w, l) + B(v, l) B(w, k)) by eq_neg_of_add_eq_zero_left. In characteristic 2, negation is the identity map (CharTwo.neg_eq), so the minus sign vanishes, yielding the required decomposition.

    lines 17–20

    uses eq_neg_of_add_eq_zero_left, add_assoc, CharTwo.neg_eq

        have he : B v w = -(B v k*B w l+B v l*B w k) :=
          eq_neg_of_add_eq_zero_left (by simpa [add_assoc] using h)
        change B v w = B v k*B w l+B v l*B w k
        simpa only [CharTwo.neg_eq] using he
resolve_left
In a disjunction a ∨ b, if a is false, then b is true
mul_one
Multiplying an element by 1 leaves it unchanged: a * 1 = a
eq_neg_of_add_eq_zero_left
If a + b = 0 in an additive group, then a = -b
add_assoc
Addition is associative: (a + b) + c = a + (b + c)
CharTwo.neg_eq
In a ring of characteristic 2, negation is the identity map: -x = x

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_bilinear_quartic_relations_decomposable {V : Type*}    [AddCommGroup V] [Module (ZMod 2) V]    (B : LinearMap.BilinForm (ZMod 2) V)    (hP : ∀ v w y z, B v w * B y z + B v y * B w z + B v z * B w y = 0) :    ∃ a b : V →ₗ[ZMod 2] ZMod 2, ∀ v w, B v w = a v*b w+b v*a w := by  classical  by_cases hz : ∀ v w, B v w = 0  · exact ⟨0,0, by simp [hz]⟩  · push Not at hz    obtain ⟨k,l,hkl⟩ := hz    have h01 : ∀ t : ZMod 2, t=0 ∨ t=1 := by decide    have hkl1 : B k l=1 := (h01 _).resolve_left hkl    refine ⟨B.flip k, B.flip l, ?_⟩    intro v w    have h := hP v w k l    rw [hkl1, mul_one] at h    have he : B v w = -(B v k*B w l+B v l*B w k) :=      eq_neg_of_add_eq_zero_left (by simpa [add_assoc] using h)    change B v w = B v k*B w l+B v l*B w k    simpa only [CharTwo.neg_eq] using he
See it in the graphDiscuss this resultChallenge it