AFTD Auto-Formalizing Theoretical Domains

binary_quartic_relations_decomposable

theoremverified

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

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.

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

    lines 5–7

      classical
      by_cases hz : Q = 0
      · exact ⟨0, 0, by simp [hz]⟩
  2. 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.

    lines 8–13

      · 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
  3. 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.

    lines 14–16

    uses resolve_left

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

    lines 17–21

    uses mul_one

        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
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)

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