hammingDist_eq_of_codeword_supp_inter_singleton
Let $\alpha$ be an alphabet with decidable equality and zero element $0$. For any two codewords $x, y : \mathrm{Fin}\, n \to \alpha$ whose supports intersect in a singleton $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) = \{i\}$, their Hamming distance is $\mathrm{hammingDist}(x, y) = (\mathrm{codeword\_supp}(x)).\mathrm{card} + (\mathrm{codeword\_supp}(y)).\mathrm{card} - 2 + (\mathrm{if}\ x\ i = y\ i\ \mathrm{then}\ 0\ \mathrm{else}\ 1)$.
Statement
theorem hammingDist_eq_of_codeword_supp_inter_singleton {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (x y : Fin n → α) (i : Fin n) (h_inter : codeword_supp x ∩ codeword_supp y = {i}) : hammingDist x y = (codeword_supp x).card + (codeword_supp y).card - 2 + (if x i = y i then 0 else 1)
- Source
- arXiv:2610.30613, Lemma 2.1
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- codeword_suppThe support of a codeword $x : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality and zero is the finite set…
- Used by 1
- two_four_code_sync_single_coordLet $\alpha$ be an alphabet with decidable equality and a distinguished element $0$. Let…
Read back from the Lean
For any natural number $n$, any type $\alpha$ with decidable equality and a zero element, any two vectors $x, y : \mathrm{Fin}\ n \to \alpha$, and any index $i : \mathrm{Fin}\ n$, if the intersection of the supports of $x$ and $y$ (the set of indices where both are non-zero) is the singleton $\{i\}$, then the Hamming distance between $x$ and $y$ equals the size of the support of $x$ plus the size of the support of $y$ minus 2, plus 0 if $x(i) = y(i)$ and 1 if $x(i) \neq y(i)$ (using natural number subtraction).
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 computes the Hamming distance between two codewords by partitioning the set of coordinates where they disagree into three pairwise disjoint sets: coordinates where only $x$ is non-zero, coordinates where only $y$ is non-zero, and the singleton coordinate $\{i\}$ where both are non-zero (if $x\ i \ne y\ i$). Since the supports overlap solely at $\{i\}$, the two set-difference parts have cardinalities $|\mathrm{supp}(x)| - 1$ and $|\mathrm{supp}(y)| - 1$, while the singleton contributes $0$ if $x\ i = y\ i$ and $1$ if $x\ i \ne y\ i$. Summing the sizes of these disjoint components and simplifying via integer arithmetic yields the stated formula.
The set of coordinates where $x$ and $y$ disagree partitions into three disjoint sets: coordinates where only $x$ is non-zero, coordinates where only $y$ is non-zero, and coordinates where both are non-zero but distinct.
By set extensionality (`ext j`), an index $j$ satisfies $x\ j \ne y\ j$ if and only if it belongs to $(\mathrm{codeword\_supp}(x) \setminus \mathrm{codeword\_supp}(y)) \cup (\mathrm{codeword\_supp}(y) \setminus \mathrm{codeword\_supp}(x)) \cup \{j \in \mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) \mid x\ j \ne y\ j\}$. Simplifying set memberships into non-zero assertions, a case split on whether $x\ j = 0$ and $y\ j = 0$ places any disagreeing coordinate into one of the three components. Conversely, coordinates in any of the three components have differing values.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_union,Finset.mem_sdiff,Finset.mem_inter,codeword_supp,ne_eq,not_not,Or.inl,Or.inrhave hset : (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n)) = (codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x) ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_sdiff, Finset.mem_inter, codeword_supp, ne_eq, not_not] constructor · intro h by_cases hx : x j = 0 · by_cases hy : y j = 0 · exact absurd (by rw [hx, hy]) h · exact Or.inl (Or.inr ⟨hy, hx⟩) · by_cases hy : y j = 0 · exact Or.inl (Or.inl ⟨hx, hy⟩) · exact Or.inr ⟨⟨hx, hy⟩, h⟩ · intro hmem rcases hmem with (⟨hx, hy⟩ | ⟨hy, hx⟩) | ⟨⟨_, _⟩, h⟩ · exact fun e => hx (e.trans hy) · exact fun e => hy (e.symm.trans hx) · exact h
The index $i$ belongs to the intersection of the supports, the intersection has cardinality $1$, and each support has cardinality at least $1$.
Since $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) = \{i\}$, $i$ is in the intersection and its cardinality is $1$. Because $i$ is in both $\mathrm{codeword\_supp}(x)$ and $\mathrm{codeword\_supp}(y)$, neither support is empty, so each has cardinality at least $1$.
uses
Finset.card_pos.2,Finset.mem_inter.mphave hi : i ∈ codeword_supp x ∩ codeword_supp y := by rw [h_inter]; simp have hcard_inter : (codeword_supp x ∩ codeword_supp y).card = 1 := by rw [h_inter]; simp have hAx : 1 ≤ (codeword_supp x).card := Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).1⟩ have hBy : 1 ≤ (codeword_supp y).card := Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).2⟩
The set differences have sizes $(\mathrm{codeword\_supp}(x)).\mathrm{card} - 1$ and $(\mathrm{codeword\_supp}(y)).\mathrm{card} - 1$, and the filtered intersection has size $0$ if $x\ i = y\ i$ and $1$ if $x\ i \ne y\ i$.
By `Finset.card_sdiff`, $|A \setminus B| = |A| - |A \cap B|$; since the intersection has size $1$, each difference has size one less than the respective support. Because the intersection is the singleton $\{i\}$, filtering it on $x\ j \ne y\ j$ gives $\{i\}$ if $x\ i \ne y\ i$ and $\emptyset$ if $x\ i = y\ i$, which have sizes $1$ and $0$ respectively.
uses
Finset.card_sdiff,Finset.inter_comm,Finset.filter_singletonhave h1 : (codeword_supp x \ codeword_supp y).card = (codeword_supp x).card - 1 := by rw [Finset.card_sdiff, Finset.inter_comm, hcard_inter] have h2 : (codeword_supp y \ codeword_supp x).card = (codeword_supp y).card - 1 := by rw [Finset.card_sdiff, hcard_inter] have h3 : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)).card = (if x i = y i then 0 else 1) := by rw [h_inter, Finset.filter_singleton] by_cases h : x i = y i <;> simp [h]
The three component sets partitioning the disagreement set are pairwise disjoint.
The filtered intersection is a subset of $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y)$ by `Finset.filter_subset`. The differences $\mathrm{codeword\_supp}(x) \setminus \mathrm{codeword\_supp}(y)$ and $\mathrm{codeword\_supp}(y) \setminus \mathrm{codeword\_supp}(x)$ cannot share an element, as membership in one requires non-membership in the other's support. Furthermore, neither difference can intersect the intersection of the supports.
uses
Finset.filter_subset,Finset.disjoint_left,Finset.mem_sdiff.mp,Finset.mem_union.mp,Finset.mem_inter.mphave hCsub : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) ⊆ codeword_supp x ∩ codeword_supp y := Finset.filter_subset _ _ have hd12 : Disjoint (codeword_supp x \ codeword_supp y) (codeword_supp y \ codeword_supp x) := by rw [Finset.disjoint_left] intro a ha hb exact (Finset.mem_sdiff.mp hb).2 (Finset.mem_sdiff.mp ha).1 have hd3 : Disjoint ((codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x)) ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by rw [Finset.disjoint_left] intro a ha hb have hb' := hCsub hb rcases Finset.mem_union.mp ha with ha' | ha' · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').2 · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').1
The cardinality of the union of the three components is $(\mathrm{codeword\_supp}(x)).\mathrm{card} - 1 + ((\mathrm{codeword\_supp}(y)).\mathrm{card} - 1) + (\mathrm{if}\ x\ i = y\ i\ \mathrm{then}\ 0\ \mathrm{else}\ 1)$.
Because the components are pairwise disjoint, `Finset.card_union_of_disjoint` applies twice to express the cardinality of the union as the sum of the cardinalities of the three components, which are then replaced by their previously established formulas.
uses
Finset.card_union_of_disjointhave hcard : ((codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x) ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j))).card = (codeword_supp x).card - 1 + ((codeword_supp y).card - 1) + (if x i = y i then 0 else 1) := by rw [Finset.card_union_of_disjoint hd3, Finset.card_union_of_disjoint hd12, h1, h2, h3]
The Hamming distance between $x$ and $y$ equals $(\mathrm{codeword\_supp}(x)).\mathrm{card} + (\mathrm{codeword\_supp}(y)).\mathrm{card} - 2 + (\mathrm{if}\ x\ i = y\ i\ \mathrm{then}\ 0\ \mathrm{else}\ 1)$. automation
By definition, $\mathrm{hammingDist}(x, y)$ is the number of coordinates where $x$ and $y$ disagree. Substituting the partition and its cardinality reduces the claim to the identity $(a - 1) + (b - 1) + c = a + b - 2 + c$. Since $a \ge 1$ and $b \ge 1$ were established in earlier steps, no underflow occurs in $\mathbb{N}$, and `omega` closes the goal by linear arithmetic.
have hh : hammingDist x y = (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n)).card := rfl rw [hh, hset, hcard] omega
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
true_and- The conjunction `True ∧ p` is logically equivalent to `p`.
Finset.mem_union- An element belongs to the union `s ∪ t` if and only if it belongs to `s` or to `t`.
Finset.mem_sdiff- An element belongs to the set difference `s \ t` if and only if it belongs to `s` and does not belong to `t`.
Finset.mem_inter- An element belongs to the intersection `s ∩ t` if and only if it belongs to `s` and to `t`.
codeword_supp- The support of a codeword `x` is defined as the set of indices `j` where `x j ≠ 0`.
ne_eq- The inequality `a ≠ b` is definitionally `¬(a = b)`.
not_not- Double negation elimination: `¬¬a` is equivalent to `a`.
Or.inl- Injects a proof of `a` into the left branch of a disjunction `a ∨ b`.
Or.inr- Injects a proof of `b` into the right branch of a disjunction `a ∨ b`.
Finset.card_pos.2- A finite set containing an element has cardinality at least 1.
Finset.mem_inter.mp- If an element belongs to `s ∩ t`, then it belongs to `s` and to `t`.
Finset.card_sdiff- The cardinality of `t \ s` equals `t.card - (s ∩ t).card`.
Finset.inter_comm- Intersection of finite sets is commutative: `s₁ ∩ s₂ = s₂ ∩ s₁`.
Finset.filter_singleton- Filtering a singleton set `{a}` with predicate `p` yields `{a}` if `p a` is true, and `∅` otherwise.
Finset.filter_subset- Filtering a finite set produces a subset of the original finite set: `Finset.filter p s ⊆ s`.
Finset.disjoint_left- Two finite sets `s` and `t` are disjoint if and only if no element of `s` belongs to `t`.
Finset.mem_sdiff.mp- If an element belongs to `s \ t`, then it belongs to `s` and does not belong to `t`.
Finset.mem_union.mp- If an element belongs to `s ∪ t`, then it belongs to `s` or to `t`.
Finset.card_union_of_disjoint- If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
- The final step relies on `omega` to close the linear integer arithmetic identity $(a - 1) + (b - 1) + c = a + b - 2 + c$, which holds in ℕ without underflow because $a, b \ge 1$.
- The definition of `hammingDist x y` is definitionally equal to the cardinality of the filter `{j | x j ≠ y j}`, which Lean unfolds by reflexivity (`rfl`).
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.
/-- Hamming distance formula for two codewords whose supports intersect at a single coordinate. -/theorem hammingDist_eq_of_codeword_supp_inter_singleton {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (x y : Fin n → α) (i : Fin n) (h_inter : codeword_supp x ∩ codeword_supp y = {i}) : hammingDist x y = (codeword_supp x).card + (codeword_supp y).card - 2 + (if x i = y i then 0 else 1) := by have hset : (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n)) = (codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x) ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_sdiff, Finset.mem_inter, codeword_supp, ne_eq, not_not] constructor · intro h by_cases hx : x j = 0 · by_cases hy : y j = 0 · exact absurd (by rw [hx, hy]) h · exact Or.inl (Or.inr ⟨hy, hx⟩) · by_cases hy : y j = 0 · exact Or.inl (Or.inl ⟨hx, hy⟩) · exact Or.inr ⟨⟨hx, hy⟩, h⟩ · intro hmem rcases hmem with (⟨hx, hy⟩ | ⟨hy, hx⟩) | ⟨⟨_, _⟩, h⟩ · exact fun e => hx (e.trans hy) · exact fun e => hy (e.symm.trans hx) · exact h have hi : i ∈ codeword_supp x ∩ codeword_supp y := by rw [h_inter]; simp have hcard_inter : (codeword_supp x ∩ codeword_supp y).card = 1 := by rw [h_inter]; simp have hAx : 1 ≤ (codeword_supp x).card := Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).1⟩ have hBy : 1 ≤ (codeword_supp y).card := Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).2⟩ have h1 : (codeword_supp x \ codeword_supp y).card = (codeword_supp x).card - 1 := by rw [Finset.card_sdiff, Finset.inter_comm, hcard_inter] have h2 : (codeword_supp y \ codeword_supp x).card = (codeword_supp y).card - 1 := by rw [Finset.card_sdiff, hcard_inter] have h3 : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)).card = (if x i = y i then 0 else 1) := by rw [h_inter, Finset.filter_singleton] by_cases h : x i = y i <;> simp [h] have hCsub : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) ⊆ codeword_supp x ∩ codeword_supp y := Finset.filter_subset _ _ have hd12 : Disjoint (codeword_supp x \ codeword_supp y) (codeword_supp y \ codeword_supp x) := by rw [Finset.disjoint_left] intro a ha hb exact (Finset.mem_sdiff.mp hb).2 (Finset.mem_sdiff.mp ha).1 have hd3 : Disjoint ((codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x)) ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by rw [Finset.disjoint_left] intro a ha hb have hb' := hCsub hb rcases Finset.mem_union.mp ha with ha' | ha' · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').2 · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').1 have hcard : ((codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x) ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j))).card = (codeword_supp x).card - 1 + ((codeword_supp y).card - 1) + (if x i = y i then 0 else 1) := by rw [Finset.card_union_of_disjoint hd3, Finset.card_union_of_disjoint hd12, h1, h2, h3] have hh : hammingDist x y = (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n)).card := rfl rw [hh, hset, hcard] omega