AFTD Auto-Formalizing Theoretical Domains

two_four_code_sync_single_coord

theoremverifiedformalization

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.

  1. 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.

    lines 13–15

    uses codeword_ne_of_supp_inter_singleton, hammingDist_eq_of_codeword_supp_inter_singleton

      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
  2. 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.

    line 16

      rcases hy_wt with hy | hy
  3. 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.

    lines 17–20

    uses if_false

      · by_contra hxy
        simp only [hxy, if_false] at heq
        rw [hx_wt, hy] at heq
        omega
  4. 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.

    lines 21–24

    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

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