binary_six_zero_sum_differences_independent
For six distinct binary vectors with zero sum, the differences of vectors 1 through 4 from vector 0 are linearly independent.
Statement
theorem binary_six_zero_sum_differences_independent {n : ℕ} (v : Fin 6 → (Fin n → ZMod 2)) (hinj : Function.Injective v) (hsum : ∑ j, v j = 0) : LinearIndependent (ZMod 2) (fun i : Fin 4 => v ⟨i.val + 1, by omega⟩ + v 0)
- 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_six_zero_sum_gram_rankThe sum of the outer squares of six distinct binary vectors with zero sum has matrix rank exactly four.
The proof, explained
The theorem shows that four difference vectors v_{i+1} - v_0 (which equals v_{i+1} + v_0 over ZMod 2) formed from six distinct zero-sum binary vectors are linearly independent. By definition of linear independence over ZMod 2, any vanishing linear combination has coefficients in {0, 1}^4, leading to 16 cases. The all-zero coefficient case is immediate, while every other case forces two distinct vectors among the six to be equal—either directly when 1 or 2 coefficients are non-zero, or after adding the total zero-sum relation ∑ v_j = 0 when 3 or 4 coefficients are non-zero—contradicting injectivity.
For each i in Fin 4, i + 1 is strictly less than 6.
Since i < 4, linear integer arithmetic shows i + 1 < 6, making v(i+1) well-defined.
(fun i : Fin 4 => v ⟨i.val + 1, by omega⟩ + v 0) := by
To establish linear independence, it suffices to show that any vanishing linear combination has all coefficients zero, and we split this into 16 cases.
We apply the definition of linear independence for finite types, which reduces to showing that ∑ g_i (v_{i+1} + v_0) = 0 implies g = 0. Since the scalar field is ZMod 2, each coefficient g_i must be 0 or 1, producing 16 cases.
uses
Fintype.linearIndependent_iffrw [Fintype.linearIndependent_iff] intro g hg have h01 : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide rcases h01 (g 0) with h0 | h0 <;> rcases h01 (g 1) with h1 | h1 <;> rcases h01 (g 2) with h2 | h2 <;> rcases h01 (g 3) with h3 | h3
If all coefficients are zero, the linear independence condition holds trivially.
In the case where g(0)=g(1)=g(2)=g(3)=0, all coefficients are already 0, which directly satisfies the goal.
· intro i; fin_cases i <;> assumption
The coefficient vector (0, 0, 0, 1) is impossible.
The linear combination reduces to v_4 + v_0 = 0, which implies v_4 = v_0, contradicting the injectivity of v since 4 ≠ 0.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (4 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (0, 0, 1, 0) is impossible.
The linear combination reduces to v_3 + v_0 = 0, which implies v_3 = v_0, contradicting the injectivity of v since 3 ≠ 0.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (3 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (0, 0, 1, 1) is impossible.
The linear combination reduces to (v_3 + v_0) + (v_4 + v_0) = 0. In characteristic 2, 2 * v_0 = 0, so v_3 = v_4, contradicting injectivity since 3 ≠ 4.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (3 : Fin 6) ≠ 4 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (0, 1, 0, 0) is impossible.
The linear combination reduces to v_2 + v_0 = 0, so v_2 = v_0, contradicting injectivity since 2 ≠ 0.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (2 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (0, 1, 0, 1) is impossible.
The linear combination reduces to v_2 + v_4 = 0, so v_2 = v_4, contradicting injectivity since 2 ≠ 4.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (2 : Fin 6) ≠ 4 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (0, 1, 1, 0) is impossible.
The linear combination reduces to v_2 + v_3 = 0, so v_2 = v_3, contradicting injectivity since 2 ≠ 3.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (2 : Fin 6) ≠ 3 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (0, 1, 1, 1) is impossible.
The linear combination gives v_2 + v_3 + v_4 + v_0 = 0. Adding the total zero-sum relation ∑ v_j = 0 cancels all terms except v_1 + v_5 = 0, so v_1 = v_5, contradicting injectivity since 1 ≠ 5.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (1 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char
The coefficient vector (1, 0, 0, 0) is impossible.
The linear combination reduces to v_1 + v_0 = 0, so v_1 = v_0, contradicting injectivity since 1 ≠ 0.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (1 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (1, 0, 0, 1) is impossible.
The linear combination reduces to v_1 + v_4 = 0, so v_1 = v_4, contradicting injectivity since 1 ≠ 4.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (1 : Fin 6) ≠ 4 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (1, 0, 1, 0) is impossible.
The linear combination reduces to v_1 + v_3 = 0, so v_1 = v_3, contradicting injectivity since 1 ≠ 3.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (1 : Fin 6) ≠ 3 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (1, 0, 1, 1) is impossible.
Adding the linear combination v_1 + v_3 + v_4 + v_0 = 0 to the total sum ∑ v_j = 0 yields v_2 + v_5 = 0, so v_2 = v_5, contradicting injectivity since 2 ≠ 5.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (2 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char
The coefficient vector (1, 1, 0, 0) is impossible.
The linear combination reduces to v_1 + v_2 = 0, so v_1 = v_2, contradicting injectivity since 1 ≠ 2.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (1 : Fin 6) ≠ 2 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char
The coefficient vector (1, 1, 0, 1) is impossible.
Adding the linear combination v_1 + v_2 + v_4 + v_0 = 0 to the total sum ∑ v_j = 0 yields v_3 + v_5 = 0, so v_3 = v_5, contradicting injectivity since 3 ≠ 5.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (3 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char
The coefficient vector (1, 1, 1, 0) is impossible.
Adding the linear combination v_1 + v_2 + v_3 + v_0 = 0 to the total sum ∑ v_j = 0 yields v_4 + v_5 = 0, so v_4 = v_5, contradicting injectivity since 4 ≠ 5.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (4 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char
The coefficient vector (1, 1, 1, 1) is impossible.
The linear combination gives v_1 + v_2 + v_3 + v_4 = 0 (since 4 * v_0 = 0 in characteristic 2). Adding the total sum ∑ v_j = 0 yields v_0 + v_5 = 0, so v_5 = v_0, contradicting injectivity since 5 ≠ 0.
uses
congrFun,Fin.sum_univ_succ· exfalso apply (show (5 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char
Fintype.linearIndependent_iff- A family of vectors in a finite module is linearly independent if and only if the only vanishing linear combination has all coefficients zero.
congrFun- If two functions are equal, their values at any point are equal.
Fin.sum_univ_succ- Splits the sum over Fin (n + 1) into the first term at 0 and the sum over the remaining terms.
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_six_zero_sum_differences_independent {n : ℕ} (v : Fin 6 → (Fin n → ZMod 2)) (hinj : Function.Injective v) (hsum : ∑ j, v j = 0) : LinearIndependent (ZMod 2) (fun i : Fin 4 => v ⟨i.val + 1, by omega⟩ + v 0) := by rw [Fintype.linearIndependent_iff] intro g hg have h01 : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide rcases h01 (g 0) with h0 | h0 <;> rcases h01 (g 1) with h1 | h1 <;> rcases h01 (g 2) with h2 | h2 <;> rcases h01 (g 3) with h3 | h3 · intro i; fin_cases i <;> assumption · exfalso apply (show (4 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (3 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (3 : Fin 6) ≠ 4 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (2 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (2 : Fin 6) ≠ 4 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (2 : Fin 6) ≠ 3 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (1 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char · exfalso apply (show (1 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (1 : Fin 6) ≠ 4 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (1 : Fin 6) ≠ 3 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (2 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char · exfalso apply (show (1 : Fin 6) ≠ 2 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx linear_combination (norm := ring_nf) hx <;> reduce_mod_char · exfalso apply (show (3 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char · exfalso apply (show (4 : Fin 6) ≠ 5 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char · exfalso apply (show (5 : Fin 6) ≠ 0 by decide) (hinj ?_) funext x have hx := congrFun hg x simp [Fin.sum_univ_succ, h0, h1, h2, h3] at hx have hs := congrFun hsum x simp [Fin.sum_univ_succ] at hs linear_combination (norm := ring_nf) hx + hs <;> reduce_mod_char