binary_bilinear_quartic_relations_decomposable
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
- binary_quadratic_decomposable_mod_linear_of_fourth_differenceIf twice the binary lift of a quadratic form has vanishing fourth differences on all cubes, the form is one product of two linear forms…
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).
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.
classical by_cases hz : ∀ v w, B v w = 0 · exact ⟨0,0, by simp [hz]⟩
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.
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
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.
refine ⟨B.flip k, B.flip l, ?_⟩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.
uses
mul_oneintro v w have h := hP v w k l rw [hkl1, mul_one] at h
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.
uses
eq_neg_of_add_eq_zero_left,add_assoc,CharTwo.neg_eqhave 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
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_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