AFTD Auto-Formalizing Theoretical Domains

binary_quartic_relations_rank_le_two

theoremverified

A finite binary matrix satisfying all the four-index alternating relations has rank at most two.

Statement

theorem binary_quartic_relations_rank_le_two {n : ℕ}
    (Q : Matrix (Fin n) (Fin n) (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) :
    Q.rank ≤ 2
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 1
Used by 1

The proof, explained

The alternating quartic relations allow Q over ℤ/2ℤ to be decomposed entrywise as Q_ij = a_i b_j + b_i a_j for two vectors a and b. Packing these vectors into an n × 2 matrix A and a 2 × n matrix B expresses Q as the matrix product A * B. The rank of Q is then bounded by the rank of A, which cannot exceed its width of 2.

  1. There exist vectors a and b such that Q = a bᵀ + b aᵀ.

    By binary_quartic_relations_decomposable, the four-index alternating relations imply that Q_ij = a_i b_j + b_i a_j for some vectors a, b : Fin n → ℤ/2ℤ. By extensionality on matrix entries, Q equals the sum of the two vector outer products Matrix.vecMulVec a b and Matrix.vecMulVec b a.

    lines 5–8

    uses binary_quartic_relations_decomposable

      obtain ⟨a, b, hab⟩ := binary_quartic_relations_decomposable Q hQ
      have he : Q = Matrix.vecMulVec a b + Matrix.vecMulVec b a := by
        ext i j
        exact hab i j
  2. Q factors as the matrix product A * B of an n × 2 matrix A and a 2 × n matrix B.

    Define the n × 2 matrix A with rows [a i, b i] and the 2 × n matrix B with rows b and a. After rewriting Q using the outer-product decomposition, extensionality reduces the claim to verifying that a_i b_j + b_i a_j = ∑ k : Fin 2, A i k * B k j. Expanding the definition of A and B and evaluating the sum over Fin 2 via Fin.sum_univ_two yields a_i b_j + b_i a_j, establishing Q = A * B.

    lines 9–15

    uses Fin.sum_univ_two

      let A : Matrix (Fin n) (Fin 2) (ZMod 2) := fun i => ![a i, b i]
      let B : Matrix (Fin 2) (Fin n) (ZMod 2) := ![b, a]
      have hf : Q = A * B := by
        rw [he]
        ext i j
        change a i * b j + b i * a j = ∑ k : Fin 2, A i k * B k j
        simp [A, B, Fin.sum_univ_two]
  3. The rank of Q is at most 2.

    Using the factorization Q = A * B, the rank of Q equals the rank of A * B. By Matrix.rank_mul_le_left, rank(A * B) ≤ rank(A). Since A is an n × 2 matrix, Matrix.rank_le_width bounds rank(A) by 2, concluding the proof.

    lines 16–19

    uses Matrix.rank_mul_le_left, Matrix.rank_le_width

      calc
        Q.rank = (A * B).rank := by rw [hf]
        _ ≤ A.rank := Matrix.rank_mul_le_left _ _
        _ ≤ 2 := Matrix.rank_le_width A
binary_quartic_relations_decomposable
A matrix over ℤ/2ℤ satisfying the four-index alternating relations can be decomposed entrywise as Q i j = a i * b j + b i * a j for some vectors a and b.
Fin.sum_univ_two
The sum of a function over Fin 2 is the sum of its values at 0 and 1: ∑ i, f i = f 0 + f 1.
Matrix.rank_mul_le_left
For any matrices A and B over a commutative ring satisfying the strong rank condition, rank(A * B) ≤ rank(A).
Matrix.rank_le_width
The rank of an m × n matrix is at most its column dimension n.

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_rank_le_two {n : ℕ}    (Q : Matrix (Fin n) (Fin n) (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) :    Q.rank ≤ 2 := by  obtain ⟨a, b, hab⟩ := binary_quartic_relations_decomposable Q hQ  have he : Q = Matrix.vecMulVec a b + Matrix.vecMulVec b a := by    ext i j    exact hab i j  let A : Matrix (Fin n) (Fin 2) (ZMod 2) := fun i => ![a i, b i]  let B : Matrix (Fin 2) (Fin n) (ZMod 2) := ![b, a]  have hf : Q = A * B := by    rw [he]    ext i j    change a i * b j + b i * a j = ∑ k : Fin 2, A i k * B k j    simp [A, B, Fin.sum_univ_two]  calc    Q.rank = (A * B).rank := by rw [hf]    _ ≤ A.rank := Matrix.rank_mul_le_left _ _    _ ≤ 2 := Matrix.rank_le_width A
See it in the graphDiscuss this resultChallenge it