binary_code_odd_forbidden_dist_max_size
Let 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 Hamming distance d satisfies F.card ≤ 2 ^ (n - 1), and there exists a subset F : Finset (Fin n → Fin 2) with no two elements having Hamming distance d whose cardinality is 2 ^ (n - 1).
Statement
theorem binary_code_odd_forbidden_dist_max_size (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (hodd : Odd d) : (∀ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) → F.card ≤ 2 ^ (n - 1)) ∧ ∃ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) ∧ F.card = 2 ^ (n - 1)- Formalizes
- arXiv:2611.04523, Proposition 3.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- binary_code_parity_class_avoids_odd_distFor any natural numbers n and odd d, and any parity ε : Fin 2, any two words x, y : Fin n → Fin 2 whose sum of coordinates in Fin 2 equals…
- binary_code_parity_class_cardFor 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…
- binary_code_avoids_odd_dist_card_leLet 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…
Read back from the Lean
For any natural numbers $n$ and $d$ such that $1 \le n$, $1 \le d \le n$, and $d$ is odd:
1. For every finite subset $F$ of binary words of length $n$ (functions Fin n → Fin 2), if no two (not necessarily distinct) elements $x, y \in F$ have Hamming distance equal to $d$, then the cardinality of $F$ is at most $2^{n - 1}$.
2. There exists a finite subset $F$ of binary words of length $n$ such that no two elements $x, y \in F$ have Hamming distance equal to $d$, and the cardinality of $F$ is exactly $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 establishes that the maximum size of a binary code of length n avoiding an odd Hamming distance d is 2^(n-1). The upper bound |F| ≤ 2^(n-1) holds by a previously proved lemma `binary_code_avoids_odd_dist_card_le`. The bound is tight because the code consisting of all words of even parity has size 2^(n-1), and any two words with the same parity differ in an even number of positions, so their Hamming distance can never be the odd integer d.
Every binary code F on {0, 1}ⁿ avoiding Hamming distance d has cardinality at most 2^(n-1).
This is the upper bound half of the conjunction, which follows directly from the previously proven lemma `binary_code_avoids_odd_dist_card_le`.
uses
binary_code_avoids_odd_dist_card_lerefine ⟨fun F hF => binary_code_avoids_odd_dist_card_le n d hn hd hdn F hF, ?_⟩
It suffices to exhibit the code of even-parity words and show it avoids Hamming distance d with size 2^(n-1).
We provide the explicit candidate witness F = {x ∈ {0, 1}ⁿ | ∑ i, x i = 0}, the set of all binary words whose coordinate sum is even (zero in Fin 2). This reduces the existence claim to verifying that no two elements in F have Hamming distance d and that |F| = 2^(n-1).
refine ⟨Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = 0), ?_, ?_⟩
No two words in the even-parity code have Hamming distance d.
Given two words x, y in the filtered set, we unfold the filter definition with `Finset.mem_filter` to extract that both have coordinate sum 0. By `binary_code_parity_class_avoids_odd_dist`, words with the same parity cannot have an odd Hamming distance d.
uses
Finset.mem_filter,binary_code_parity_class_avoids_odd_dist· intro x hx y hy rw [Finset.mem_filter] at hx hy exact binary_code_parity_class_avoids_odd_dist n d hodd 0 x y hx.2 hy.2
The even-parity code has cardinality 2^(n-1).
By `binary_code_parity_class_card`, the parity class with sum 0 of binary words of length n ≥ 1 contains exactly 2^(n-1) elements.
uses
binary_code_parity_class_card· exact binary_code_parity_class_card n hn 0
binary_code_avoids_odd_dist_card_le- For n ≥ 1 and 1 ≤ d ≤ n, any subset of {0, 1}ⁿ containing no two elements at Hamming distance d has cardinality at most 2^(n-1).
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
binary_code_parity_class_avoids_odd_dist- If d is an odd integer, then any two binary words of length n with the same coordinate sum in Fin 2 (i.e. the same parity) cannot have Hamming distance d.
binary_code_parity_class_card- For n ≥ 1, the number of binary words of length n with a given coordinate sum parity ε ∈ Fin 2 is exactly 2^(n-1).
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 maximum cardinality of a binary code in {0,1}^n avoiding an odd Hamming distance d is 2^(n-1). -/theorem binary_code_odd_forbidden_dist_max_size (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (hodd : Odd d) : (∀ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) → F.card ≤ 2 ^ (n - 1)) ∧ ∃ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) ∧ F.card = 2 ^ (n - 1) := by refine ⟨fun F hF => binary_code_avoids_odd_dist_card_le n d hn hd hdn F hF, ?_⟩ refine ⟨Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = 0), ?_, ?_⟩ · intro x hx y hy rw [Finset.mem_filter] at hx hy exact binary_code_parity_class_avoids_odd_dist n d hodd 0 x y hx.2 hy.2 · exact binary_code_parity_class_card n hn 0