AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it