binary_code_avoids_odd_dist_card_le
Let n ≥ 1 and 1 ≤ d ≤ n. Every finite set of binary words F : Finset (Fin n → Fin 2) such that no two elements have Hamming distance d satisfies F.card ≤ 2 ^ (n - 1).
Statement
theorem binary_code_avoids_odd_dist_card_le (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (F : Finset (Fin n → Fin 2)) (hF : ∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) : F.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 all natural numbers $n$ and $d$ such that $1 \le n$, $1 \le d$, and $d \le n$, and for every finite set $F$ of binary sequences of length $n$ (elements of $\mathrm{Fin}\ n \to \mathrm{Fin}\ 2$), if no pair of elements $x, y \in F$ has Hamming distance equal to $d$ ($\forall x \in F, \forall y \in F, \operatorname{hammingDist}(x, y) \neq d$), then the cardinality of $F$ is at most $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
The theorem is proved by a translation argument. We construct a fixed binary vector v of length n with Hamming weight d (having ones in its first d coordinates). Translating any codeword by v changes it by Hamming distance d, so the shifted code F' = F + v must be disjoint from F, which avoids distance d by assumption. Because translation is injective, |F'| = |F|, and since F and F' are disjoint subsets of the ambient space {0, 1}^n of size 2^n, their union has size 2|F| ≤ 2^n, which yields |F| ≤ 2^(n - 1).
The support of the shift vector v consists of the indices strictly less than d.
The shift vector v is defined by setting the i-th coordinate to 1 if i < d and 0 otherwise. Since an element of Fin 2 is non-zero if and only if it equals 1, the condition v i ≠ 0 is equivalent to i < d. Filtering the universe of indices Fin n for non-zero coordinates therefore yields the set of indices strictly less than d.
uses
Finset.mem_filter,Finset.mem_univ,true_and,binary_code_avoids_odd_dist_card_le_shiftlemma binary_code_avoids_odd_dist_card_le_card_shift (n d : ℕ) (hdn : d ≤ n) : (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card = d := by have h1 : (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)) = Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) := by ext i simp only [Finset.mem_filter, Finset.mem_univ, true_and] dsimp [binary_code_avoids_odd_dist_card_le_shift] split_ifs with h <;> simp [h] rw [h1]
The shift vector v has Hamming weight d (exactly d non-zero coordinates).
Since d ≤ n, the canonical embedding Fin.castLE maps Finset.univ of Fin d bijectively onto the set of indices in Fin n that are strictly less than d. Rewriting the support of v as the image of Finset.univ under this embedding, its cardinality is given by the cardinality of Fin d, which is d.
uses
Fin.castLE,Fin.castLE_injective,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_map,Function.Embedding.coeFn_mk,Finset.card_map,Finset.card_univ,Fintype.card_finhave h2 : Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) = Finset.map ⟨Fin.castLE hdn, Fin.castLE_injective hdn⟩ Finset.univ := by ext ⟨i, hi⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map, Function.Embedding.coeFn_mk] constructor · intro h refine ⟨⟨i, h⟩, ?_⟩ ext rfl · rintro ⟨⟨j, hj⟩, h⟩ have : j = i := by injection h rw [← this] exact hj rw [h2, Finset.card_map, Finset.card_univ, Fintype.card_fin]
Shifting any binary word by v changes it by Hamming distance d.
By definition, the Hamming distance between x and x + v is the number of coordinates i where x i ≠ (x + v) i. In Fin 2 = ℤ/2ℤ, adding v i alters the coordinate if and only if v i ≠ 0. Therefore, the distance is the number of non-zero coordinates of v, which was shown in binary_code_avoids_odd_dist_card_le_card_shift to equal d.
uses
hammingDist,binary_code_avoids_odd_dist_card_le_card_shiftlemma binary_code_avoids_odd_dist_card_le_hammingDist_shift (n d : ℕ) (hdn : d ≤ n) (x : Fin n → Fin 2) : hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) = d := by have h : hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) = (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card := by unfold hammingDist congr 1 ext i simp rw [h, binary_code_avoids_odd_dist_card_le_card_shift n d hdn]
Define the shift vector v, the translation embedding f(x) = x + v, and the shifted code F' = f(F).
We define v as the shift vector of length n with d ones. Adding v is injective by additive cancellation (add_left_injective), giving an embedding f. We let F' be the image of F under f.
uses
binary_code_avoids_odd_dist_card_le_shift,add_left_injectivetheorem binary_code_avoids_odd_dist_card_le (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (F : Finset (Fin n → Fin 2)) (hF : ∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) : F.card ≤ 2 ^ (n - 1) := by let v := binary_code_avoids_odd_dist_card_le_shift n d let f : (Fin n → Fin 2) ↪ (Fin n → Fin 2) := ⟨fun x => x + v, add_left_injective v⟩ let F' := F.map f
The code F and its shifted copy F' are disjoint.
Suppose for contradiction that an element y belongs to both F and F'. Since y ∈ F', we have y = x + v for some x ∈ F. By binary_code_avoids_odd_dist_card_le_hammingDist_shift, the Hamming distance between x and x + v is d. Since both x and x + v = y belong to F, this contradicts the hypothesis that no two codewords in F have Hamming distance d.
uses
Finset.disjoint_left,Finset.mem_map.mp,binary_code_avoids_odd_dist_card_le_hammingDist_shifthave hdisj : Disjoint F F' := by rw [Finset.disjoint_left] intro y hy1 hy2 rcases Finset.mem_map.mp hy2 with ⟨x, hx, rfl⟩ have hd_eq := binary_code_avoids_odd_dist_card_le_hammingDist_shift n d hdn x exact hF x hx (x + v) hy1 hd_eq
The shifted code has |F'| = |F|, their disjoint union has size 2|F|, and the ambient space has size 2^n.
Because f is an embedding, |F'| = |F| by Finset.card_map. Since F and F' are disjoint, |F ∪ F'| = |F| + |F'| = 2|F| by Finset.card_union_of_disjoint. The union F ∪ F' is a subset of the full space of binary words {0, 1}^n, so its size is at most the total number of words, which is 2^n by Fintype.card_fun and Fintype.card_fin.
uses
Finset.card_map,Finset.card_union_of_disjoint,Finset.card_le_univ,Fintype.card_fun,Fintype.card_finhave h_card_eq : F'.card = F.card := Finset.card_map f have h_union : (F ∪ F').card = F.card + F'.card := Finset.card_union_of_disjoint hdisj have h_le_univ : (F ∪ F').card ≤ Fintype.card (Fin n → Fin 2) := Finset.card_le_univ (F ∪ F') have h_total : Fintype.card (Fin n → Fin 2) = 2 ^ n := by rw [Fintype.card_fun, Fintype.card_fin, Fintype.card_fin]
The cardinality of F is at most 2^(n - 1).
From the preceding bounds we have 2|F| ≤ 2^n. Using 1 ≤ n, we rewrite 2^n as 2^(n - 1 + 1) = 2^(n - 1) * 2 via Nat.sub_add_cancel and pow_succ. Linear integer arithmetic (omega) then divides by 2 to conclude |F| ≤ 2^(n - 1).
uses
Nat.sub_add_cancel,pow_succhave h_sum : F.card + F.card ≤ 2 ^ n := by omega have h_pow : 2 ^ n = 2 ^ (n - 1 + 1) := by rw [Nat.sub_add_cancel hn] rw [h_pow, pow_succ] at h_sum omega
add_left_injective- In an additive structure with right cancellation, the translation map x ↦ x + a is injective.
binary_code_avoids_odd_dist_card_le_card_shift- For d ≤ n, the shift vector has exactly d non-zero coordinates.
binary_code_avoids_odd_dist_card_le_hammingDist_shift- Translating any binary word x by the shift vector yields a word at Hamming distance d from x.
binary_code_avoids_odd_dist_card_le_shift- The binary vector in {0, 1}^n whose i-th coordinate is 1 when i < d and 0 otherwise.
Fin.castLE- The canonical embedding from Fin n to Fin m when n ≤ m.
Fin.castLE_injective- The embedding Fin.castLE is injective.
Finset.card_le_univ- The cardinality of any finset is at most the cardinality of the ambient finite type.
Finset.card_map- The image of a finset under an embedding has the same cardinality as the original finset.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
Finset.card_univ- The cardinality of Finset.univ for a finite type α equals Fintype.card α.
Finset.disjoint_left- Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter- An element x belongs to s.filter p if and only if x ∈ s and p(x) holds.
Finset.mem_map- An element y belongs to Finset.map f s if and only if y = f(x) for some x ∈ s.
Finset.mem_map.mp- If y ∈ Finset.map f s, then there exists some x ∈ s such that f(x) = y.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Fintype.card_fin- The cardinality of Fin n is n.
Fintype.card_fun- The number of functions from a finite type α to a finite type β is |β|^|α|.
Function.Embedding.coeFn_mk- Coercing an embedding ⟨f, inj⟩ to a function yields f.
hammingDist- The Hamming distance between two vectors, defined as the number of coordinates where they differ.
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
pow_succ- For any base a and natural number n, a^(n + 1) = a^n * a.
true_and- The logical proposition True ∧ p is equivalent to p.
- Binary words are represented as functions `Fin n → Fin 2`, where `Fin 2` has the group structure of ℤ/2ℤ (coordinate-wise XOR). Under this addition, x i ≠ (x + v) i if and only if v i ≠ 0.
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.
def binary_code_avoids_odd_dist_card_le_shift (n d : ℕ) : Fin n → Fin 2 := fun i => if (i : ℕ) < d then 1 else 0lemma binary_code_avoids_odd_dist_card_le_card_shift (n d : ℕ) (hdn : d ≤ n) : (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card = d := by have h1 : (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)) = Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) := by ext i simp only [Finset.mem_filter, Finset.mem_univ, true_and] dsimp [binary_code_avoids_odd_dist_card_le_shift] split_ifs with h <;> simp [h] rw [h1] have h2 : Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) = Finset.map ⟨Fin.castLE hdn, Fin.castLE_injective hdn⟩ Finset.univ := by ext ⟨i, hi⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map, Function.Embedding.coeFn_mk] constructor · intro h refine ⟨⟨i, h⟩, ?_⟩ ext rfl · rintro ⟨⟨j, hj⟩, h⟩ have : j = i := by injection h rw [← this] exact hj rw [h2, Finset.card_map, Finset.card_univ, Fintype.card_fin]lemma binary_code_avoids_odd_dist_card_le_hammingDist_shift (n d : ℕ) (hdn : d ≤ n) (x : Fin n → Fin 2) : hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) = d := by have h : hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) = (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card := by unfold hammingDist congr 1 ext i simp rw [h, binary_code_avoids_odd_dist_card_le_card_shift n d hdn]/-- A binary code in {0,1}^n avoiding a distance d with 1 ≤ d ≤ n has cardinality at most 2^(n-1). -/theorem binary_code_avoids_odd_dist_card_le (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (F : Finset (Fin n → Fin 2)) (hF : ∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) : F.card ≤ 2 ^ (n - 1) := by let v := binary_code_avoids_odd_dist_card_le_shift n d let f : (Fin n → Fin 2) ↪ (Fin n → Fin 2) := ⟨fun x => x + v, add_left_injective v⟩ let F' := F.map f have hdisj : Disjoint F F' := by rw [Finset.disjoint_left] intro y hy1 hy2 rcases Finset.mem_map.mp hy2 with ⟨x, hx, rfl⟩ have hd_eq := binary_code_avoids_odd_dist_card_le_hammingDist_shift n d hdn x exact hF x hx (x + v) hy1 hd_eq have h_card_eq : F'.card = F.card := Finset.card_map f have h_union : (F ∪ F').card = F.card + F'.card := Finset.card_union_of_disjoint hdisj have h_le_univ : (F ∪ F').card ≤ Fintype.card (Fin n → Fin 2) := Finset.card_le_univ (F ∪ F') have h_total : Fintype.card (Fin n → Fin 2) = 2 ^ n := by rw [Fintype.card_fun, Fintype.card_fin, Fintype.card_fin] have h_sum : F.card + F.card ≤ 2 ^ n := by omega have h_pow : 2 ^ n = 2 ^ (n - 1 + 1) := by rw [Nat.sub_add_cancel hn] rw [h_pow, pow_succ] at h_sum omega