hamming_dist_eq_exceptional_add_all_distinct
For vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$, the Hamming distance $\mathrm{hammingDist}(x, y)$ equals the number of coordinates where $x$ is exceptional, plus the number where $y$ is exceptional, plus the number where all three coordinates are distinct.
Statement
theorem hamming_dist_eq_exceptional_add_all_distinct {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) : hammingDist x y = (hamming_exceptional_coords x y z).card + (hamming_exceptional_coords y x z).card + (hamming_all_distinct_coords x y z).card
- Source
- arXiv:2610.32789 "Triangle-Free Sets in Exact-Distance Hamming Graphs", Proposition 2.2
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hamming_exceptional_coordsFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality,…
- hamming_all_distinct_coordsFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality,…
- Used by 1
- hamming_equilateral_triangle_local_typesSuppose $x, y, z : \mathrm{Fin}\, n \to \alpha$ satisfy $\mathrm{hammingDist}(x, y) = r$, $\mathrm{hammingDist}(x, z) = r$, and…
Read back from the Lean
For any natural number $n$, any type $\alpha$ with decidable equality, and any three functions $x, y, z : \mathrm{Fin}\; n \to \alpha$, the Hamming distance between $x$ and $y$ equals the sum of:
1. the number of coordinates $i$ where $y(i) = z(i)$ and $x(i) \neq y(i)$ (hamming_exceptional_coords x y z),
2. the number of coordinates $i$ where $x(i) = z(i)$ and $y(i) \neq x(i)$ (hamming_exceptional_coords y x z), and
3. the number of coordinates $i$ where $x(i)$, $y(i)$, and $z(i)$ are all pairwise distinct (hamming_all_distinct_coords x y z).
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 proof partitions the set of coordinates where $x$ and $y$ differ into three pairwise disjoint subsets: indices where $x$ is exceptional ($y_i = z_i$ and $x_i \ne y_i$), indices where $y$ is exceptional ($x_i = z_i$ and $y_i \ne x_i$), and indices where all three vectors differ. This decomposition is established by a propositional equivalence showing that whenever $x_i \ne y_i$, exactly one of these three cases occurs. Since the three subsets are mutually disjoint, the Hamming distance—defined as the number of coordinates where $x_i \ne y_i$—equals the sum of their cardinalities by additivity of set size over disjoint unions.
For any three elements $a, b, c \in \alpha$, $a \ne b$ holds if and only if either ($b = c$ and $a \ne b$), ($a = c$ and $b \ne a$), or all three are pairwise distinct. automation
This is an exhaustive propositional case analysis: whenever $a \ne b$, the third element $c$ must equal $b$, equal $a$, or differ from both. The equivalence is established by propositional logic via `tauto`.
have prop_equiv (a b c : α) : (a ≠ b) ↔ ((b = c ∧ a ≠ b) ∨ (a = c ∧ b ≠ a)) ∨ (a ≠ b ∧ a ≠ c ∧ b ≠ c) := by tauto
The set of coordinates where $x$ and $y$ differ is the union of the coordinates where $x$ is exceptional, where $y$ is exceptional, and where all three vectors differ.
Applying the coordinate-wise equivalence `prop_equiv` across the universe of coordinates via `Finset.filter_congr` rewrites the condition $x_i \ne y_i$ into the three-way disjunction. Distributing the filter over disjunctions using `Finset.filter_or` expresses the set as the union of the three filtered subsets, which match the definitions of the exceptional and all-distinct coordinate sets.
uses
Finset.filter_congr,Finset.filter_orhave h_split : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) = (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z) ∪ hamming_all_distinct_coords x y z := by have h_congr : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) = Finset.filter (fun i => ((y i = z i ∧ x i ≠ y i) ∨ (x i = z i ∧ y i ≠ x i)) ∨ (x i ≠ y i ∧ x i ≠ z i ∧ y i ≠ z i)) Finset.univ := Finset.filter_congr (fun i _ => prop_equiv (x i) (y i) (z i)) rw [h_congr, Finset.filter_or, Finset.filter_or] rfl
The coordinates where $x$ is exceptional and the coordinates where $y$ is exceptional are disjoint.
By `Finset.disjoint_filter`, two filtered sets are disjoint if no coordinate satisfies both predicates. If an index $i$ were in both sets, we would have $y_i = z_i$ and $x_i = z_i$, which together imply $x_i = y_i$, contradicting the assumption $x_i \ne y_i$ in the definition of exceptional coordinates for $x$.
uses
Finset.disjoint_filterhave disj1 : Disjoint (hamming_exceptional_coords x y z) (hamming_exceptional_coords y x z) := by rw [hamming_exceptional_coords, hamming_exceptional_coords, Finset.disjoint_filter] intro i _ ⟨hyz, hxy⟩ ⟨hxz, _⟩ apply hxy rw [hyz, hxz]
The union of both exceptional coordinate sets is disjoint from the set of all-distinct coordinates.
Using `Finset.disjoint_union_left`, it suffices to verify disjointness for each exceptional set separately. If $x$ is exceptional at $i$, then $y_i = z_i$, contradicting the requirement $y_i \ne z_i$ of all-distinct coordinates. Similarly, if $y$ is exceptional at $i$, then $x_i = z_i$, contradicting $x_i \ne z_i$.
uses
Finset.disjoint_union_left,Finset.disjoint_filterhave disj2 : Disjoint (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z) (hamming_all_distinct_coords x y z) := by rw [Finset.disjoint_union_left] constructor · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter] intro i _ ⟨hyz, _⟩ ⟨_, _, hyz'⟩ exact hyz' hyz · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter] intro i _ ⟨hxz, _⟩ ⟨_, hxz', _⟩ exact hxz' hxz
The Hamming distance $\mathrm{hammingDist}(x, y)$ equals the sum of the cardinalities of the three coordinate sets.
By definition, $\mathrm{hammingDist}(x, y)$ is the number of coordinates where $x_i \ne y_i$. Rewriting this set via the partition `h_split` and applying `Finset.card_union_of_disjoint` twice using the disjointness facts `disj2` and `disj1` converts the cardinality of the union into the sum of the three individual cardinalities.
uses
Finset.card_union_of_disjointchange (Finset.filter (fun i => x i ≠ y i) Finset.univ).card = _ rw [h_split, Finset.card_union_of_disjoint disj2, Finset.card_union_of_disjoint disj1]
Finset.filter_congr- If two predicates are equivalent on every element of a finite set, then filtering by either predicate produces the same subset.
Finset.filter_or- Filtering a finite set by a disjunction of two predicates is equal to the union of the two individually filtered sets.
Finset.disjoint_filter- Two subsets formed by filtering a common finite set are disjoint if and only if no element satisfies both predicates simultaneously.
Finset.disjoint_union_left- A union of two sets is disjoint from a third set if and only if each of the two sets is disjoint from the third.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their individual cardinalities.
- On line 34, `change` unfolds the definition of `hammingDist x y` to the cardinality of the coordinates where `x i ≠ y i` via definitional equality.
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 Hamming distance between x and y is the sum of exceptional coordinates for x, exceptional coordinates for y, and all-distinct coordinates. -/theorem hamming_dist_eq_exceptional_add_all_distinct {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) : hammingDist x y = (hamming_exceptional_coords x y z).card + (hamming_exceptional_coords y x z).card + (hamming_all_distinct_coords x y z).card := by have prop_equiv (a b c : α) : (a ≠ b) ↔ ((b = c ∧ a ≠ b) ∨ (a = c ∧ b ≠ a)) ∨ (a ≠ b ∧ a ≠ c ∧ b ≠ c) := by tauto have h_split : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) = (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z) ∪ hamming_all_distinct_coords x y z := by have h_congr : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) = Finset.filter (fun i => ((y i = z i ∧ x i ≠ y i) ∨ (x i = z i ∧ y i ≠ x i)) ∨ (x i ≠ y i ∧ x i ≠ z i ∧ y i ≠ z i)) Finset.univ := Finset.filter_congr (fun i _ => prop_equiv (x i) (y i) (z i)) rw [h_congr, Finset.filter_or, Finset.filter_or] rfl have disj1 : Disjoint (hamming_exceptional_coords x y z) (hamming_exceptional_coords y x z) := by rw [hamming_exceptional_coords, hamming_exceptional_coords, Finset.disjoint_filter] intro i _ ⟨hyz, hxy⟩ ⟨hxz, _⟩ apply hxy rw [hyz, hxz] have disj2 : Disjoint (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z) (hamming_all_distinct_coords x y z) := by rw [Finset.disjoint_union_left] constructor · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter] intro i _ ⟨hyz, _⟩ ⟨_, _, hyz'⟩ exact hyz' hyz · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter] intro i _ ⟨hxz, _⟩ ⟨_, hxz', _⟩ exact hxz' hxz change (Finset.filter (fun i => x i ≠ y i) Finset.univ).card = _ rw [h_split, Finset.card_union_of_disjoint disj2, Finset.card_union_of_disjoint disj1]