binary_quartic_relations_rank_le_two
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
- binary_quartic_relations_decomposableA binary matrix satisfying Qij*Qkl+Qik*Qjl+Qil*Qjk=0 for all four indices can be written Qij=ai*bj+bi*aj.
- Used by 1
- binary_quadratic_polar_rank_le_two_of_fourth_differenceFor a quadratic form on a finite binary coordinate space, vanishing of every fourth difference of twice its binary lift forces the polar…
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.
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.
uses
binary_quartic_relations_decomposableobtain ⟨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
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.
uses
Fin.sum_univ_twolet 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]
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.
uses
Matrix.rank_mul_le_left,Matrix.rank_le_widthcalc 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
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_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