AFTD Auto-Formalizing Theoretical Domains

binary_six_zero_sum_differences_independent

theoremverified

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

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.

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

    line 5

          (fun i : Fin 4 => v ⟨i.val + 1, by omega⟩ + v 0) := by
  2. 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.

    lines 6–12

    uses Fintype.linearIndependent_iff

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

    line 13

      · intro i; fin_cases i <;> assumption
  4. 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.

    lines 14–19

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

    lines 20–25

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

    lines 26–31

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

    lines 32–37

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

    lines 38–43

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

    lines 44–49

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

    lines 50–57

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

    lines 58–63

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

    lines 64–69

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

    lines 70–75

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

    lines 76–83

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

    lines 84–89

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

    lines 90–97

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

    lines 98–105

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

    lines 106–113

    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

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