binary_code_parity_class_card
For any integer n ≥ 1 and any parity ε : Fin 2, the set of words x : Fin n → Fin 2 whose sum of coordinates in Fin 2 equals ε has cardinality 2 ^ (n - 1).
Statement
theorem binary_code_parity_class_card (n : ℕ) (hn : 1 ≤ n) (ε : Fin 2) : (Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = ε)).card = 2 ^ (n - 1)
- Source
- arXiv:2611.04523, Proposition 3.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- binary_code_odd_forbidden_dist_max_sizeLet n ≥ 1 and 1 ≤ d ≤ n be integers such that d is odd. Then every subset F : Finset (Fin n → Fin 2) such that no two elements of F have…
Read back from the Lean
For any natural number $n$ with $1 \le n$ and any $\varepsilon \in \text{Fin } 2$, the cardinality of the finset of functions $x : \text{Fin } n \to \text{Fin } 2$ whose sum over all $i \in \text{Fin } n$ equals $\varepsilon$ (under addition in $\text{Fin } 2$) is equal to $2^{n - 1}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Since n ≥ 1, we can write n = m + 1. We establish a bijection between the parity class of words of length m + 1 and the set of all unrestricted binary words of length m by projecting onto the first m coordinates. The inverse map appends the unique final coordinate needed to achieve total coordinate sum ε; because there are 2^m unrestricted words of length m, the parity class has cardinality 2^m = 2^(n - 1).
We can write n = m + 1 for some natural number m, and define s as the parity class of words of length m + 1 and t as the set of all binary words of length m.
Since n ≥ 1 > 0, n is positive, so it is the successor m + 1 of some natural number m. We let s be the subset of (Fin (m + 1) → Fin 2) consisting of words whose coordinate sum equals ε, and let t be the entire set of binary words of length m.
uses
Nat.exists_eq_succ_of_ne_zero,Nat.ne_of_gt,Nat.lt_of_lt_of_le,Nat.zero_lt_oneobtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (Nat.ne_of_gt (Nat.lt_of_lt_of_le Nat.zero_lt_one hn)) classical let s : Finset (Fin (m + 1) → Fin 2) := Finset.univ.filter (fun x => (∑ i, x i) = ε) let t : Finset (Fin m → Fin 2) := Finset.univ
To show |s| = |t|, it suffices to establish that the restriction map dropping the last coordinate is a bijection from s to t, and this map is well-defined.
We apply `Finset.card_bij` with the map sending each word x ∈ s to its restriction (x₀, …, x_{m-1}) of length m. Since t contains all binary words of length m, every word restricts to an element of t.
uses
Finset.card_bijhave hcard : s.card = t.card := by refine Finset.card_bij (fun x _ => fun i : Fin m => x i.castSucc) ?_ ?_ ?_ · intro x hx simp [t]
The restriction map from s to t is injective.
Suppose x, y ∈ s have the same restriction to their first m coordinates. Since both coordinate sums equal ε, decomposing each sum into the sum of the first m coordinates plus the final coordinate gives ∑_{i < m} x_i + x_m = ε = ∑_{i < m} y_i + y_m. Because the initial segments agree, their prefix sums are identical, and cancelling this sum yields x_m = y_m. Recombining the identical initial segments with the identical final coordinates implies x = y.
uses
Finset.mem_filter.mp,Fin.sum_univ_castSucc,add_left_cancel,Fin.snoc_init_self· intro x hx y hy hxy have hxsum : (∑ i, x i) = ε := by simpa [s] using (Finset.mem_filter.mp hx).2 have hysum : (∑ i, y i) = ε := by simpa [s] using (Finset.mem_filter.mp hy).2 have hrest : (fun i : Fin m => x i.castSucc) = (fun i : Fin m => y i.castSucc) := hxy have hxy_sum : (∑ i : Fin m, x i.castSucc) = (∑ i : Fin m, y i.castSucc) := by rw [hrest] have hx' := hxsum rw [Fin.sum_univ_castSucc] at hx' have hy' := hysum rw [Fin.sum_univ_castSucc] at hy' have hlast : x (Fin.last m) = y (Fin.last m) := by have h1 : (∑ i : Fin m, x i.castSucc) + x (Fin.last m) = (∑ i : Fin m, y i.castSucc) + y (Fin.last m) := by rw [hx', hy'] apply add_left_cancel (a := (∑ i : Fin m, x i.castSucc)) rw [h1, ← hxy_sum] calc x = Fin.snoc (Fin.init x) (x (Fin.last m)) := (Fin.snoc_init_self x).symm _ = Fin.snoc (fun i : Fin m => x i.castSucc) (x (Fin.last m)) := by rfl _ = Fin.snoc (fun i : Fin m => y i.castSucc) (y (Fin.last m)) := by rw [hrest, hlast] _ = Fin.snoc (Fin.init y) (y (Fin.last m)) := by rfl _ = y := Fin.snoc_init_self y
The restriction map from s to t is surjective.
Given any binary word y of length m, we extend it to a word x of length m + 1 by appending the coordinate ε - ∑_{i < m} y_i. The coordinate sum of x is (∑_{i < m} y_i) + (ε - ∑_{i < m} y_i) = ε, so x ∈ s, and its restriction to the first m coordinates is y by construction.
uses
Fin.sum_snoc,add_sub_cancel· intro y hy let x : Fin (m + 1) → Fin 2 := Fin.snoc y (ε - ∑ i, y i) refine ⟨x, ?_, ?_⟩ · have hsum : (∑ i : Fin (m + 1), x i) = ε := by dsimp [x] rw [Fin.sum_snoc] exact add_sub_cancel _ _ simp [s, hsum] · funext i simp [x]
The cardinality of the parity class s is 2 ^ (n - 1). automation
Because |s| = |t|, the problem reduces to computing the size of t. The set t of all functions from a set of size m to a set of size 2 has cardinality 2^m, which equals 2 ^ (n - 1) since n = m + 1.
rw [hcard] simp [t]
Nat.ne_of_gt- A natural number with a strictly smaller natural number is not equal to that smaller number.
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number is the successor of some natural number.
Nat.lt_of_lt_of_le- Strict inequality is preserved when composed with a weak inequality: if n < m and m ≤ k, then n < k.
Nat.zero_lt_one- Zero is strictly less than one.
Finset.card_bij- Two finite sets have equal cardinality if there exists a well-defined bijection between them.
Finset.mem_filter.mp- An element in a filtered finite set satisfies the defining predicate.
Fin.sum_univ_castSucc- The sum of a sequence of length n + 1 equals the sum of its first n elements plus the value at the final index.
add_left_cancel- In an additive structure with left-cancellation, a + b = a + c implies b = c.
Fin.snoc_init_self- Appending the last element of a sequence of length n + 1 to its initial segment of length n reconstructs the original sequence.
Fin.sum_snoc- The sum of a sequence of length n with an element appended at the end equals the sum of the sequence plus that element.
add_sub_cancel- In an additive group, a + (b - a) = b.
- In Lean, the type `Fin 2` has an additive group structure isomorphic to ℤ/2ℤ, so coordinate sums and differences take place modulo 2.
- Indexing is 0-based: `Fin.castSucc` embeds the first m coordinates into the m + 1 coordinates, and `Fin.last m` represents the final coordinate.
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.
/-- The set of binary words of given coordinate-sum parity has cardinality 2^(n-1). -/theorem binary_code_parity_class_card (n : ℕ) (hn : 1 ≤ n) (ε : Fin 2) : (Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = ε)).card = 2 ^ (n - 1) := by obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (Nat.ne_of_gt (Nat.lt_of_lt_of_le Nat.zero_lt_one hn)) classical let s : Finset (Fin (m + 1) → Fin 2) := Finset.univ.filter (fun x => (∑ i, x i) = ε) let t : Finset (Fin m → Fin 2) := Finset.univ have hcard : s.card = t.card := by refine Finset.card_bij (fun x _ => fun i : Fin m => x i.castSucc) ?_ ?_ ?_ · intro x hx simp [t] · intro x hx y hy hxy have hxsum : (∑ i, x i) = ε := by simpa [s] using (Finset.mem_filter.mp hx).2 have hysum : (∑ i, y i) = ε := by simpa [s] using (Finset.mem_filter.mp hy).2 have hrest : (fun i : Fin m => x i.castSucc) = (fun i : Fin m => y i.castSucc) := hxy have hxy_sum : (∑ i : Fin m, x i.castSucc) = (∑ i : Fin m, y i.castSucc) := by rw [hrest] have hx' := hxsum rw [Fin.sum_univ_castSucc] at hx' have hy' := hysum rw [Fin.sum_univ_castSucc] at hy' have hlast : x (Fin.last m) = y (Fin.last m) := by have h1 : (∑ i : Fin m, x i.castSucc) + x (Fin.last m) = (∑ i : Fin m, y i.castSucc) + y (Fin.last m) := by rw [hx', hy'] apply add_left_cancel (a := (∑ i : Fin m, x i.castSucc)) rw [h1, ← hxy_sum] calc x = Fin.snoc (Fin.init x) (x (Fin.last m)) := (Fin.snoc_init_self x).symm _ = Fin.snoc (fun i : Fin m => x i.castSucc) (x (Fin.last m)) := by rfl _ = Fin.snoc (fun i : Fin m => y i.castSucc) (y (Fin.last m)) := by rw [hrest, hlast] _ = Fin.snoc (Fin.init y) (y (Fin.last m)) := by rfl _ = y := Fin.snoc_init_self y · intro y hy let x : Fin (m + 1) → Fin 2 := Fin.snoc y (ε - ∑ i, y i) refine ⟨x, ?_, ?_⟩ · have hsum : (∑ i : Fin (m + 1), x i) = ε := by dsimp [x] rw [Fin.sum_snoc] exact add_sub_cancel _ _ simp [s, hsum] · funext i simp [x] rw [hcard] simp [t]