binary_code_parity_class_avoids_odd_dist
For 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 ε have Hamming distance different from d.
Statement
theorem binary_code_parity_class_avoids_odd_dist (n d : ℕ) (hodd : Odd d) (ε : Fin 2) : ∀ x y : Fin n → Fin 2, (∑ i, x i) = ε → (∑ i, y i) = ε → hammingDist x y ≠ d- 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 numbers $n$ and $d$, if $d$ is odd, then for any $\varepsilon \in \mathrm{Fin}\ 2$ and any two vectors $x, y : \mathrm{Fin}\ n \to \mathrm{Fin}\ 2$, if the sum of the components of $x$ (in $\mathrm{Fin}\ 2$, i.e., modulo 2) equals $\varepsilon$ and the sum of the components of $y$ (in $\mathrm{Fin}\ 2$, i.e., modulo 2) equals $\varepsilon$, then the Hamming distance between $x$ and $y$ is not equal to $d$.
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 contradiction: we assume two words $x, y \in (\text{Fin } 2)^n$ have the same coordinate-sum parity $\varepsilon$ but have an odd Hamming distance $d$. In the field of two elements, the difference of coordinates $x_i - y_i$ equals 1 exactly when $x_i \neq y_i$, so the total sum $\sum_i (x_i - y_i)$ is both $\text{hammingDist}(x, y) • 1$ and $\sum x_i - \sum y_i = \varepsilon - \varepsilon = 0$, giving $d • 1 = 0$. On the other hand, because $d = 2k + 1$ is odd, $d • 1 = 1$ in $\text{Fin } 2$, producing the contradiction $0 = 1$.
In `Fin 2`, the difference $a - b$ equals 1 if $a \neq b$ and 0 if $a = b$. automation
Because `Fin 2` has only two elements ($0$ and $1$), the identity is verified by exhaustively checking all four possible combinations of $a$ and $b$ using computational decision (`decide`).
lemma binary_code_parity_class_avoids_odd_dist_sub_eq_ite (a b : Fin 2) : a - b = if a ≠ b then (1 : Fin 2) else 0 := by revert a b decide
For any odd natural number $d$, the scalar multiple $d • 1$ in `Fin 2` equals 1.
Since $d$ is odd, write $d = 2k + 1$ for some natural number $k$. Distributing scalar multiplication yields $(2k + 1) • 1 = k • (2 • 1) + 1 • 1$. In `Fin 2`, $2 • 1 = 0$, so $k • (2 • 1) = k • 0 = 0$. Thus $0 + 1 = 1$.
uses
add_smul,mul_comm,mul_smul,smul_zero,zero_add,one_smullemma binary_code_parity_class_avoids_odd_dist_nsmul_one (d : ℕ) (hodd : Odd d) : d • (1 : Fin 2) = 1 := by rcases hodd with ⟨k, rfl⟩ rw [add_smul, mul_comm, mul_smul] have h2 : (2 : ℕ) • (1 : Fin 2) = 0 := by decide rw [h2, smul_zero, zero_add, one_smul]
Assume for contradiction that two binary words with the same coordinate-sum parity $\varepsilon$ have Hamming distance $d$.
Introduce the words $x, y \in (\text{Fin } 2)^n$, the assumptions that both coordinate sums equal $\varepsilon$, and the hypothesis for contradiction that $\text{hammingDist}(x, y) = d$.
/-- Any two binary words of the same coordinate-sum parity avoid any odd Hamming distance. -/ theorem binary_code_parity_class_avoids_odd_dist (n d : ℕ) (hodd : Odd d) (ε : Fin 2) : ∀ x y : Fin n → Fin 2, (∑ i, x i) = ε → (∑ i, y i) = ε → hammingDist x y ≠ d := by intro x y hx hy hdist
The Hamming distance between $x$ and $y$ satisfies $\text{hammingDist}(x, y) • 1 = 0$ in `Fin 2`.
For each index $i$, the coordinate difference $x_i - y_i$ is 1 when $x_i \neq y_i$ and 0 otherwise. Summing over all coordinates shows that $\sum_i (x_i - y_i)$ counts the indices where the coordinates differ times 1, which by definition is $\text{hammingDist}(x, y) • 1$. On the other hand, the sum distributes as $\sum_i x_i - \sum_i y_i = \varepsilon - \varepsilon = 0$.
uses
binary_code_parity_class_avoids_odd_dist_sub_eq_ite,Finset.sum_filter,Finset.sum_const,Finset.sum_sub_distrib,sub_selfhave h_sum : hammingDist x y • (1 : Fin 2) = 0 := by have h (i : Fin n) : x i - y i = if x i ≠ y i then (1 : Fin 2) else 0 := binary_code_parity_class_avoids_odd_dist_sub_eq_ite (x i) (y i) have h1 : hammingDist x y • (1 : Fin 2) = ∑ i, (x i - y i) := by simp_rw [h] rw [← Finset.sum_filter] rw [Finset.sum_const] rfl rw [h1, Finset.sum_sub_distrib, hx, hy, sub_self]
Derive the contradiction $0 = 1$ in `Fin 2`. automation
Substituting the distance assumption $\text{hammingDist}(x, y) = d$ into $\text{hammingDist}(x, y) • 1 = 0$ yields $d • 1 = 0$. However, since $d$ is odd, the helper lemma gives $d • 1 = 1$, which forces $0 = 1$ in `Fin 2`. This false statement is rejected by `decide`, completing the proof by contradiction.
uses
binary_code_parity_class_avoids_odd_dist_nsmul_onehave h_d : d • (1 : Fin 2) = 0 := by rwa [← hdist] have h_odd : d • (1 : Fin 2) = 1 := binary_code_parity_class_avoids_odd_dist_nsmul_one d hodd rw [h_d] at h_odd revert h_odd decide
add_smul- Scalar multiplication distributes over addition of scalars: $(r + s) • x = r • x + s • x$.
mul_comm- Multiplication is commutative: $a * b = b * a$.
mul_smul- Scalar multiplication by a product of scalars equals iterated scalar multiplication: $(x * y) • b = x • (y • b)$.
smul_zero- Scalar multiplication of any scalar with zero yields zero: $a • 0 = 0$.
zero_add- Zero is the left identity for addition: $0 + a = a$.
one_smul- Scalar multiplication by 1 is the identity: $1 • b = b$.
binary_code_parity_class_avoids_odd_dist_sub_eq_ite- In `Fin 2`, the difference $a - b$ equals 1 if $a \neq b$ and 0 if $a = b$.
Finset.sum_filter- Summing a function over elements satisfying a predicate equals summing over the whole set with non-satisfying terms replaced by 0.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Finset.sum_sub_distrib- The sum of termwise differences is the difference of the sums: $\sum (f(x) - g(x)) = \sum f(x) - \sum g(x)$.
sub_self- Subtracting an element from itself yields zero: $a - a = 0$.
binary_code_parity_class_avoids_odd_dist_nsmul_one- For any odd natural number $d$, the scalar multiple $d • 1$ in `Fin 2` equals 1.
- The type `Fin 2` represents the two-element field with arithmetic modulo 2; addition and subtraction coincide, and scalar multiplication by a natural number $k • 1$ extracts the parity of $k$.
- The coordinate difference identity and the final contradiction $0 = 1 \implies \text{False}$ are discharged by `decide`, which operates by exhaustive computation over the finite type `Fin 2`.
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.
lemma binary_code_parity_class_avoids_odd_dist_sub_eq_ite (a b : Fin 2) : a - b = if a ≠ b then (1 : Fin 2) else 0 := by revert a b decidelemma binary_code_parity_class_avoids_odd_dist_nsmul_one (d : ℕ) (hodd : Odd d) : d • (1 : Fin 2) = 1 := by rcases hodd with ⟨k, rfl⟩ rw [add_smul, mul_comm, mul_smul] have h2 : (2 : ℕ) • (1 : Fin 2) = 0 := by decide rw [h2, smul_zero, zero_add, one_smul]/-- Any two binary words of the same coordinate-sum parity avoid any odd Hamming distance. -/theorem binary_code_parity_class_avoids_odd_dist (n d : ℕ) (hodd : Odd d) (ε : Fin 2) : ∀ x y : Fin n → Fin 2, (∑ i, x i) = ε → (∑ i, y i) = ε → hammingDist x y ≠ d := by intro x y hx hy hdist have h_sum : hammingDist x y • (1 : Fin 2) = 0 := by have h (i : Fin n) : x i - y i = if x i ≠ y i then (1 : Fin 2) else 0 := binary_code_parity_class_avoids_odd_dist_sub_eq_ite (x i) (y i) have h1 : hammingDist x y • (1 : Fin 2) = ∑ i, (x i - y i) := by simp_rw [h] rw [← Finset.sum_filter] rw [Finset.sum_const] rfl rw [h1, Finset.sum_sub_distrib, hx, hy, sub_self] have h_d : d • (1 : Fin 2) = 0 := by rwa [← hdist] have h_odd : d • (1 : Fin 2) = 1 := binary_code_parity_class_avoids_odd_dist_nsmul_one d hodd rw [h_d] at h_odd revert h_odd decide