binary_rank_two_even_zero_sum_support_card_gap
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
- 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 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.
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`.
uses
not_or,not_leclassical by_contra hcon rw [not_or, not_le] at hcon obtain ⟨hne4, hlt8⟩ := hcon
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.
have hcases : S.card = 0 ∨ S.card = 2 ∨ S.card = 4 ∨ S.card = 6 := by obtain ⟨k, hk⟩ := heven omega
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.
uses
Finset.card_eq_zero.mp,Matrix.rank_zerorcases 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
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.
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)
The case |S| = 4 contradicts the hypothesis that |S| ≠ 4.
The case S.card = 4 directly refutes the contradiction hypothesis `hne4 : ¬S.card = 4`.
· exact hne4 h4In 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.
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
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.
uses
Finset.sum_image,Matrix.of_applyhave 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]
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.
uses
binary_six_zero_sum_gram_rankhave 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
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_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