two_four_code_sync_single_coord
Let $\alpha$ be an alphabet with decidable equality and a distinguished element $0$. Let $\mathcal{C} \subseteq (\mathrm{Fin}\, n \to \alpha)$ be a code containing $0$ such that all distinct codewords have Hamming distance in $\{2, 4\}$. If $x \in \mathcal{C}$ has support cardinality $(\mathrm{codeword\_supp}(x)).\mathrm{card} = 2$, $y \in \mathcal{C}$ has support cardinality $(\mathrm{codeword\_supp}(y)).\mathrm{card} = 2$ or $(\mathrm{codeword\_supp}(y)).\mathrm{card} = 4$, and $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) = \{i\}$, then $x_i = y_i$.
Statement
theorem two_four_code_sync_single_coord {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (C : Set (Fin n → α)) (hC : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → hammingDist x y = 2 ∨ hammingDist x y = 4) (_h0 : 0 ∈ C) (x y : Fin n → α) (hxC : x ∈ C) (hx_wt : (codeword_supp x).card = 2) (hyC : y ∈ C) (hy_wt : (codeword_supp y).card = 2 ∨ (codeword_supp y).card = 4) (i : Fin n) (h_inter : codeword_supp x ∩ codeword_supp y = {i}) : x i = y i
- Formalizes
- arXiv:2610.30613, Lemma 2.1
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- hammingDist_eq_of_codeword_supp_inter_singletonLet $\alpha$ be an alphabet with decidable equality and zero element $0$. For any two codewords $x, y : \mathrm{Fin}\, n \to \alpha$ whose…
- codeword_ne_of_supp_inter_singletonLet $\alpha$ be an alphabet with decidable equality and zero element $0$. If $x, y : \mathrm{Fin}\, n \to \alpha$ are codewords such that…
Read back from the Lean
Let $n$ be a natural number and let $\alpha$ be a type with decidable equality and a zero element. Let $C \subseteq (\text{Fin } n \to \alpha)$ be a set of codewords such that any two distinct codewords $x, y \in C$ have Hamming distance 2 or 4, and such that the zero function $0$ belongs to $C$. Let $x, y \in C$ be codewords such that the support of $x$ has cardinality 2, and the support of $y$ has cardinality 2 or 4. If the intersection of the supports of $x$ and $y$ is the singleton $\{i\}$ for some $i \in \text{Fin } n$, then $x(i) = y(i)$.
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
Since the intersection of the supports of x and y is a single coordinate i and x has support size 2, x and y are distinct, so the code property implies their Hamming distance must be 2 or 4. The general distance formula for two words intersecting at a single coordinate i expresses their Hamming distance as |supp(x)| + |supp(y)| - 2 plus 1 if they differ at i (or 0 if they agree). Assuming for contradiction that x_i ≠ y_i, this formula forces the distance to be 3 when |supp(y)| = 2 and 5 when |supp(y)| = 4, both contradicting the code distance constraint.
The codewords x and y are distinct, their Hamming distance is in {2, 4}, and their Hamming distance equals |codeword_supp x| + |codeword_supp y| - 2 + (if x i = y i then 0 else 1).
Since the support of x has size 2 while its intersection with the support of y is the singleton {i}, x has a non-zero coordinate outside the support of y, so x ≠ y by codeword_ne_of_supp_inter_singleton. Because x and y are distinct codewords in C, hypothesis hC implies hammingDist x y is either 2 or 4. Furthermore, by hammingDist_eq_of_codeword_supp_inter_singleton, the Hamming distance between codewords whose supports meet at a single coordinate i equals the sum of the non-overlapping support sizes plus an indicator for whether the codewords disagree at i.
uses
codeword_ne_of_supp_inter_singleton,hammingDist_eq_of_codeword_supp_inter_singletonhave hne : x ≠ y := codeword_ne_of_supp_inter_singleton x y i hx_wt h_inter have hd := hC x hxC y hyC hne have heq := hammingDist_eq_of_codeword_supp_inter_singleton x y i h_inter
It suffices to show x i = y i in each of the two cases |codeword_supp y| = 2 and |codeword_supp y| = 4.
We perform a case split on the hypothesis hy_wt, which states that |codeword_supp y| is either 2 or 4.
rcases hy_wt with hy | hy
If |codeword_supp y| = 2, then x i = y i.
Suppose, for contradiction, that x i ≠ y i. Then the conditional term in the distance formula evaluates to 1 using if_false. Substituting |codeword_supp x| = 2 and |codeword_supp y| = 2 into the distance formula gives hammingDist x y = 2 + 2 - 2 + 1 = 3. But the Hamming distance must be 2 or 4; linear arithmetic over ℕ (omega) detects that 3 ∉ {2, 4} and derives a contradiction.
uses
if_false· by_contra hxy simp only [hxy, if_false] at heq rw [hx_wt, hy] at heq omega
If |codeword_supp y| = 4, then x i = y i.
Similarly, suppose for contradiction that x i ≠ y i. The conditional term simplifies to 1 via if_false. Substituting |codeword_supp x| = 2 and |codeword_supp y| = 4 into the distance formula yields hammingDist x y = 2 + 4 - 2 + 1 = 5. Linear arithmetic over ℕ (omega) detects that 5 ∉ {2, 4}, deriving a contradiction and concluding the proof.
uses
if_false· by_contra hxy simp only [hxy, if_false] at heq rw [hx_wt, hy] at heq omega
codeword_ne_of_supp_inter_singleton- If the support of a codeword x has cardinality 2 and intersects the support of y at a single coordinate i, then x ≠ y.
hammingDist_eq_of_codeword_supp_inter_singleton- If the supports of x and y intersect at a single coordinate i, then their Hamming distance is |codeword_supp x| + |codeword_supp y| - 2 + (0 if x i = y i else 1).
if_false- An if-then-else expression with a false condition simplifies to its else branch.
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.
/-- Single-coordinate synchronization: in a {2,4}-distance code containing 0, codewords of weight 2 and weight in {2,4} intersecting at a single coordinate must agree at that coordinate. -/theorem two_four_code_sync_single_coord {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (C : Set (Fin n → α)) (hC : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → hammingDist x y = 2 ∨ hammingDist x y = 4) (_h0 : 0 ∈ C) (x y : Fin n → α) (hxC : x ∈ C) (hx_wt : (codeword_supp x).card = 2) (hyC : y ∈ C) (hy_wt : (codeword_supp y).card = 2 ∨ (codeword_supp y).card = 4) (i : Fin n) (h_inter : codeword_supp x ∩ codeword_supp y = {i}) : x i = y i := by have hne : x ≠ y := codeword_ne_of_supp_inter_singleton x y i hx_wt h_inter have hd := hC x hxC y hyC hne have heq := hammingDist_eq_of_codeword_supp_inter_singleton x y i h_inter rcases hy_wt with hy | hy · by_contra hxy simp only [hxy, if_false] at heq rw [hx_wt, hy] at heq omega · by_contra hxy simp only [hxy, if_false] at heq rw [hx_wt, hy] at heq omega