hamming_dist_binary_zero_add_one
theoremverified
For any binary vector x : Fin n → Fin 2 of length n, the Hamming distance from the all-zeros vector to x plus the Hamming distance from the all-ones vector to x equals n.
Statement
lemma hamming_dist_binary_zero_add_one (n : ℕ) (x : Fin n → Fin 2) : hammingDist (fun _ : Fin n => (0 : Fin 2)) x + hammingDist (fun _ : Fin n => (1 : Fin 2)) x = n
- Source
- arXiv:2611.18156 Equation (16)
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- binary_repetition_code_is_joint_error_correcting_detectingFor an explicit natural number n with 2 ≤ n and natural numbers c, c' such that 2 * c + c' + 1 = n,
binary_repetition_code nis a (c,…
- binary_repetition_code_is_joint_error_correcting_detectingFor an explicit natural number n with 2 ≤ n and natural numbers c, c' such that 2 * c + c' + 1 = n,
Read back from the Lean
For every natural number n and every function x : Fin n → Fin 2, the Hamming distance between the constant zero function on Fin n and x, plus the Hamming distance between the constant one function on Fin n and x, equals n.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- For any binary word x of length n, the sum of its Hamming distances to the all-zeros word and to the all-ones word is n. -/ lemma hamming_dist_binary_zero_add_one (n : ℕ) (x : Fin n → Fin 2) : hammingDist (fun _ : Fin n => (0 : Fin 2)) x + hammingDist (fun _ : Fin n => (1 : Fin 2)) x = n := by have h (i : Fin n) : ((1 : Fin 2) ≠ x i) ↔ ¬ ((0 : Fin 2) ≠ x i) := by generalize x i = a fin_cases a <;> decide have h1 : Finset.filter (fun i => (1 : Fin 2) ≠ x i) Finset.univ = Finset.filter (fun i => ¬ ((0 : Fin 2) ≠ x i)) Finset.univ := Finset.filter_congr fun i _ => h i unfold hammingDist rw [h1, Finset.card_filter_add_card_filter_not] exact Fintype.card_fin n