binary_quartic_relations_decomposable
A binary matrix satisfying Qij*Qkl+Qik*Qjl+Qil*Qjk=0 for all four indices can be written Qij=ai*bj+bi*aj.
Statement
theorem binary_quartic_relations_decomposable {ι : Type*} (Q : Matrix ι ι (ZMod 2)) (hQ : ∀ i j k l, Q i j * Q k l + Q i k * Q j l + Q i l * Q j k = 0) : ∃ a b : ι → ZMod 2, ∀ i j, Q i j = a i * b j + b i * a j
- 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_quartic_relations_rank_le_twoA finite binary matrix satisfying all the four-index alternating relations has rank at most two.
The proof, explained
The proof proceeds by case analysis on whether Q is zero. If Q = 0, taking a and b to be the zero vectors trivially works. Otherwise, Q has some non-zero entry Q k l, which must equal 1 since the scalar ring is ℤ/2ℤ. Fixing this non-zero entry, we define a i = Q i k and b i = Q i l; specializing the given four-index relation to (i, j, k, l) and using Q k l = 1 immediately gives Q i j = a i * b j + b i * a j in characteristic 2.
When Q is the zero matrix, the zero vectors a = 0 and b = 0 provide the decomposition.
We enable classical logic and branch on whether Q = 0. When Q = 0, choosing a = 0 and b = 0 gives a i * b j + b i * a j = 0 = Q i j for all i, j.
classical by_cases hz : Q = 0 · exact ⟨0, 0, by simp [hz]⟩
When Q ≠ 0, there exist indices k and l such that Q k l ≠ 0.
We proceed by contradiction: if every entry of Q were zero, matrix extensionality would force Q = 0, contradicting the hypothesis Q ≠ 0. Hence there exist k and l with Q k l ≠ 0.
· obtain ⟨k, l, hkl⟩ : ∃ k l, Q k l ≠ 0 := by by_contra h push Not at h apply hz ext i j exact h i j
The non-zero entry Q k l is equal to 1.
Every element of ℤ/2ℤ is either 0 or 1, checked by exhaustive evaluation (decide). Because Q k l ≠ 0, resolving this disjunction via resolve_left yields Q k l = 1.
uses
resolve_lefthave hkl1 : Q k l = 1 := by have h01 : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide exact (h01 (Q k l)).resolve_left hkl
The column vectors a i = Q i k and b i = Q i l satisfy Q i j = a i * b j + b i * a j for all i, j.
We define the witnesses a and b to be the k-th and l-th columns of Q: a i = Q i k and b i = Q i l. For arbitrary indices i and j, we instantiate the given quartic relation hQ at (i, j, k, l), yielding Q i j * Q k l + Q i k * Q j l + Q i l * Q j k = 0. Substituting Q k l = 1 and applying mul_one simplifies this to Q i j + Q i k * Q j l + Q i l * Q j k = 0. Since the base field has characteristic 2, addition is its own inverse, and the relation rearranges to Q i j = a i * b j + b i * a j.
uses
mul_onerefine ⟨fun i => Q i k, fun i => Q i l, ?_⟩ intro i j have h := hQ i j k l rw [hkl1, mul_one] at h linear_combination (norm := ring_nf) h <;> reduce_mod_char
resolve_left- if an alternative a ∨ b holds and ¬a is known, then b holds
mul_one- multiplying an element by 1 on the right leaves it unchanged (a * 1 = a)
- Over ℤ/2ℤ, the identity Q i j + a i * b j + b i * a j = 0 implies Q i j = a i * b j + b i * a j because 1 = -1; the proof discharges this step via linear_combination together with reduce_mod_char to eliminate terms with coefficient 2.
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_quartic_relations_decomposable {ι : Type*} (Q : Matrix ι ι (ZMod 2)) (hQ : ∀ i j k l, Q i j * Q k l + Q i k * Q j l + Q i l * Q j k = 0) : ∃ a b : ι → ZMod 2, ∀ i j, Q i j = a i * b j + b i * a j := by classical by_cases hz : Q = 0 · exact ⟨0, 0, by simp [hz]⟩ · obtain ⟨k, l, hkl⟩ : ∃ k l, Q k l ≠ 0 := by by_contra h push Not at h apply hz ext i j exact h i j have hkl1 : Q k l = 1 := by have h01 : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide exact (h01 (Q k l)).resolve_left hkl refine ⟨fun i => Q i k, fun i => Q i l, ?_⟩ intro i j have h := hQ i j k l rw [hkl1, mul_one] at h linear_combination (norm := ring_nf) h <;> reduce_mod_char/- The fourth finite difference of twice a binary quadratic form isfour times its four-variable alternating coefficient. -/