AFTD Auto-Formalizing Theoretical Domains

binary_rank_two_even_zero_sum_support_card_gap

theoremverified

A finite set of binary vectors with even cardinality, zero vector sum and Gram rank two has exactly four elements or at least eight.

Statement

theorem binary_rank_two_even_zero_sum_support_card_gap {n : ℕ} (S : Finset (Fin n → ZMod 2)) (heven : Even S.card) (hsum : ∑ v ∈ S, v = 0) (hrank : (Matrix.of (fun i j => ∑ v ∈ S, v i * v j)).rank = 2) : S.card = 4 ∨ 8 ≤ S.card
Source
Supporting OP-3, arXiv:2610.01024, Section E.1; small-support reduction for the three-Hadamard route in IN-184.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The proof proceeds by contradiction: assuming |S| ≠ 4 and |S| < 8, the even cardinality of S must be 0, 2, 4, or 6. Cardinalities 0 and 4 are immediately ruled out because the empty set has Gram rank 0 and |S| ≠ 4 is assumed. Cardinality 2 is impossible because two distinct binary vectors summing to zero in characteristic 2 would have to be identical. Finally, cardinality 6 is refuted by invoking the lemma `binary_six_zero_sum_gram_rank`, which establishes that six distinct zero-sum binary vectors necessarily span a Gram matrix of rank 4, contradicting the hypothesis that the rank is 2.

  1. We may assume for contradiction that |S| ≠ 4 and |S| < 8.

    We proceed by contradiction (`by_contra`). Applying de Morgan's law for disjunction (`not_or`) and order duality (`not_le`), the negation of `S.card = 4 ∨ 8 ≤ S.card` yields two hypotheses: `hne4 : ¬S.card = 4` and `hlt8 : S.card < 8`.

    lines 2–5

    uses not_or, not_le

      classical
      by_contra hcon
      rw [not_or, not_le] at hcon
      obtain ⟨hne4, hlt8⟩ := hcon
  2. The cardinality |S| is restricted to 0, 2, 4, or 6.

    Since |S| is even (`heven`), we can write |S| = 2k. Combining this with the upper bound |S| < 8 (`hlt8`), linear integer arithmetic (`omega`) deduces that |S| must be 0, 2, 4, or 6.

    lines 6–8

      have hcases : S.card = 0 ∨ S.card = 2 ∨ S.card = 4 ∨ S.card = 6 := by
        obtain ⟨k, hk⟩ := heven
        omega
  3. The case |S| = 0 is impossible because the Gram matrix would have rank 0, contradicting rank 2.

    We split into cases on the cardinality of S (`rcases`). If |S| = 0, then S is the empty set (`Finset.card_eq_zero.mp`). The sum defining each entry of the Gram matrix is therefore over the empty set, so the entire matrix is 0. By `Matrix.rank_zero`, the rank of the zero matrix is 0, contradicting `hrank` which states the rank is 2.

    lines 9–16

    uses Finset.card_eq_zero.mp, Matrix.rank_zero

      rcases hcases with h0 | h2 | h4 | h6
      · have hS : S = ∅ := Finset.card_eq_zero.mp h0
        have hzero : (Matrix.of (fun i j => ∑ v ∈ S, v i * v j)) = 0 := by
          rw [hS]
          ext i j
          simp
        rw [hzero, Matrix.rank_zero] at hrank
        omega
  4. The case |S| = 2 is impossible because the zero-sum condition forces the two elements to coincide.

    If |S| = 2, S consists of two distinct vectors a ≠ b (`Finset.card_eq_two.mp`). Their sum is a + b = 0 (`Finset.sum_pair`). Over ℤ/2ℤ, characteristic 2 implies b + b = 0 (`CharTwo.add_self_eq_zero`). Associating addition gives a = a + (b + b) = (a + b) + b = 0 + b = b (`zero_add`, `add_assoc`, `add_zero`), which directly contradicts a ≠ b.

    lines 17–25

    uses Finset.card_eq_two.mp, Finset.sum_pair, CharTwo.add_self_eq_zero, zero_add, add_assoc, add_zero

      · obtain ⟨a, b, hab, hS⟩ := Finset.card_eq_two.mp h2
        rw [hS] at hsum
        rw [Finset.sum_pair hab] at hsum
        have hbb : b + b = (0 : Fin n → ZMod 2) := by
          funext i
          exact CharTwo.add_self_eq_zero (b i)
        have h1 : a + b + b = b := by rw [hsum, zero_add]
        have h2' : a + b + b = a := by rw [add_assoc, hbb, add_zero]
        exact hab (h2'.symm.trans h1)
  5. The case |S| = 4 contradicts the hypothesis that |S| ≠ 4.

    The case S.card = 4 directly refutes the contradiction hypothesis `hne4 : ¬S.card = 4`.

    line 26

      · exact hne4 h4
  6. In the case |S| = 6, S can be parametrized as the image of an injective sequence v : Fin 6 → (Fin n → ℤ/2ℤ).

    Since |S| = 6, we obtain an equivalence e between the subtype ↥S and Fin 6 by chaining `Finset.equivFin` and `finCongr`. Defining v(k) as the vector in S indexed by k under e⁻¹, injectivity of e⁻¹ implies v is injective via `Subtype.ext`. Extensionality together with `Finset.mem_image`, `Finset.mem_univ`, and `true_and` verifies that S equals the image of v over Finset.univ.

    lines 27–40

    uses Finset.equivFin, finCongr, Subtype.ext, Finset.mem_image, Finset.mem_univ, true_and

      · let e : ↥S ≃ Fin 6 := (Finset.equivFin S).trans (finCongr h6)
        set v : Fin 6 → (Fin n → ZMod 2) := fun k => (e.symm k).1 with hv
        have hinj : Function.Injective v := by
          intro a b hab
          have h1 : e.symm a = e.symm b := Subtype.ext hab
          exact e.symm.injective h1
        have hSimage : S = Finset.univ.image v := by
          ext x
          simp only [Finset.mem_image, Finset.mem_univ, true_and]
          constructor
          · intro hx
            exact ⟨e ⟨x, hx⟩, by simp [hv]⟩
          · rintro ⟨k, rfl⟩
            exact (e.symm k).2
  7. The indexed family v has sum zero, and its Gram matrix equals the Gram matrix of S.

    Because v is injective, `Finset.sum_image` reindexes the sum of v_k over Fin 6 into the sum over S, showing ∑ v_k = 0. Similarly, using `Matrix.of_apply` and `Finset.sum_image` entrywise, the Gram matrix of v equals the Gram matrix of S.

    lines 41–53

    uses Finset.sum_image, Matrix.of_apply

        have hsum6 : ∑ k : Fin 6, v k = 0 := by
          have himg : ∑ k : Fin 6, v k = ∑ x ∈ Finset.univ.image v, x :=
            (Finset.sum_image (s := Finset.univ) (g := v) (f := fun x => x)
              (fun a _ b _ h => hinj h)).symm
          rw [himg, ← hSimage]
          exact hsum
        have hG : (Matrix.of (fun i j => ∑ k : Fin 6, v k i * v k j)) = Matrix.of (fun i j => ∑ x ∈ S, x i * x j) := by
          ext i j
          simp only [Matrix.of_apply]
          have himg : (∑ k : Fin 6, v k i * v k j) = ∑ x ∈ Finset.univ.image v, (x i * x j) :=
            (Finset.sum_image (s := Finset.univ) (g := v) (f := fun x => x i * x j)
              (fun a _ b _ h => hinj h)).symm
          rw [himg, ← hSimage]
  8. The case |S| = 6 is impossible because the Gram matrix must have rank 4, contradicting rank 2.

    By `binary_six_zero_sum_gram_rank`, any six distinct binary vectors summing to zero have a Gram matrix of rank 4. Rewriting by the matrix equality from the previous step implies the Gram matrix of S has rank 4, contradicting `hrank` (which asserts it has rank 2). Linear arithmetic (`omega`) closes the contradiction 4 = 2.

    lines 54–56

    uses binary_six_zero_sum_gram_rank

        have h4rank := binary_six_zero_sum_gram_rank v hinj hsum6
        rw [hG] at h4rank
        omega
not_or
The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
not_le
In a linear order, ¬(a ≤ b) is equivalent to b < a.
Finset.card_eq_zero.mp
If the cardinality of a finite set is zero, then the set is empty.
Matrix.rank_zero
The rank of the zero matrix is zero.
Finset.card_eq_two.mp
If the cardinality of a finite set is two, the set consists of two distinct elements {x, y}.
Finset.sum_pair
The sum of a function over a pair {a, b} of distinct elements is f(a) + f(b).
CharTwo.add_self_eq_zero
In a semiring of characteristic two, adding any element to itself gives zero (x + x = 0).
zero_add
Adding zero to any element on the left returns that element (0 + a = a).
add_assoc
Addition is associative: (a + b) + c = a + (b + c).
add_zero
Adding zero to any element on the right returns that element (a + 0 = a).
Finset.equivFin
A finite set s is canonically in bijection with Fin s.card.
finCongr
An equality of natural numbers n = m induces a bijection between Fin n and Fin m.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Finset.mem_image
An element belongs to the image of a set under a function f if and only if it equals f(a) for some element a in the set.
Finset.mem_univ
Every element of a finite type belongs to its universal Finset.
true_and
The proposition True ∧ p is equivalent to p.
Finset.sum_image
If g is injective on s, then summing f over the image g(s) equals summing f ∘ g over s.
Matrix.of_apply
Evaluating the matrix constructed from a function f at indices (i, j) yields f(i, j).
binary_six_zero_sum_gram_rank
Any six distinct binary vectors that sum to zero have a Gram matrix of rank 4.

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_rank_two_even_zero_sum_support_card_gap {n : ℕ} (S : Finset (Fin n → ZMod 2)) (heven : Even S.card) (hsum : ∑ v ∈ S, v = 0) (hrank : (Matrix.of (fun i j => ∑ v ∈ S, v i * v j)).rank = 2) : S.card = 4 ∨ 8 ≤ S.card := by  classical  by_contra hcon  rw [not_or, not_le] at hcon  obtain ⟨hne4, hlt8⟩ := hcon  have hcases : S.card = 0 ∨ S.card = 2 ∨ S.card = 4 ∨ S.card = 6 := by    obtain ⟨k, hk⟩ := heven    omega  rcases hcases with h0 | h2 | h4 | h6  · have hS : S = ∅ := Finset.card_eq_zero.mp h0    have hzero : (Matrix.of (fun i j => ∑ v ∈ S, v i * v j)) = 0 := by      rw [hS]      ext i j      simp    rw [hzero, Matrix.rank_zero] at hrank    omega  · obtain ⟨a, b, hab, hS⟩ := Finset.card_eq_two.mp h2    rw [hS] at hsum    rw [Finset.sum_pair hab] at hsum    have hbb : b + b = (0 : Fin n → ZMod 2) := by      funext i      exact CharTwo.add_self_eq_zero (b i)    have h1 : a + b + b = b := by rw [hsum, zero_add]    have h2' : a + b + b = a := by rw [add_assoc, hbb, add_zero]    exact hab (h2'.symm.trans h1)  · exact hne4 h4  · let e : ↥S ≃ Fin 6 := (Finset.equivFin S).trans (finCongr h6)    set v : Fin 6 → (Fin n → ZMod 2) := fun k => (e.symm k).1 with hv    have hinj : Function.Injective v := by      intro a b hab      have h1 : e.symm a = e.symm b := Subtype.ext hab      exact e.symm.injective h1    have hSimage : S = Finset.univ.image v := by      ext x      simp only [Finset.mem_image, Finset.mem_univ, true_and]      constructor      · intro hx        exact ⟨e ⟨x, hx⟩, by simp [hv]⟩      · rintro ⟨k, rfl⟩        exact (e.symm k).2    have hsum6 : ∑ k : Fin 6, v k = 0 := by      have himg : ∑ k : Fin 6, v k = ∑ x ∈ Finset.univ.image v, x :=        (Finset.sum_image (s := Finset.univ) (g := v) (f := fun x => x)          (fun a _ b _ h => hinj h)).symm      rw [himg, ← hSimage]      exact hsum    have hG : (Matrix.of (fun i j => ∑ k : Fin 6, v k i * v k j)) = Matrix.of (fun i j => ∑ x ∈ S, x i * x j) := by      ext i j      simp only [Matrix.of_apply]      have himg : (∑ k : Fin 6, v k i * v k j) = ∑ x ∈ Finset.univ.image v, (x i * x j) :=        (Finset.sum_image (s := Finset.univ) (g := v) (f := fun x => x i * x j)          (fun a _ b _ h => hinj h)).symm      rw [himg, ← hSimage]    have h4rank := binary_six_zero_sum_gram_rank v hinj hsum6    rw [hG] at h4rank    omega
See it in the graphDiscuss this resultChallenge it