AFTD Auto-Formalizing Theoretical Domains

binary_code_parity_class_avoids_odd_dist

theoremverified

For any natural numbers n and odd d, and any parity ε : Fin 2, any two words x, y : Fin n → Fin 2 whose sum of coordinates in Fin 2 equals ε have Hamming distance different from d.

Statement

theorem binary_code_parity_class_avoids_odd_dist (n d : ℕ) (hodd : Odd d) (ε : Fin 2) : ∀ x y : Fin n → Fin 2, (∑ i, x i) = ε → (∑ i, y i) = ε → hammingDist x y ≠ d
Source
arXiv:2611.04523, Proposition 3.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any natural numbers $n$ and $d$, if $d$ is odd, then for any $\varepsilon \in \mathrm{Fin}\ 2$ and any two vectors $x, y : \mathrm{Fin}\ n \to \mathrm{Fin}\ 2$, if the sum of the components of $x$ (in $\mathrm{Fin}\ 2$, i.e., modulo 2) equals $\varepsilon$ and the sum of the components of $y$ (in $\mathrm{Fin}\ 2$, i.e., modulo 2) equals $\varepsilon$, then the Hamming distance between $x$ and $y$ is not equal to $d$.

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 theorem is proved by contradiction: we assume two words $x, y \in (\text{Fin } 2)^n$ have the same coordinate-sum parity $\varepsilon$ but have an odd Hamming distance $d$. In the field of two elements, the difference of coordinates $x_i - y_i$ equals 1 exactly when $x_i \neq y_i$, so the total sum $\sum_i (x_i - y_i)$ is both $\text{hammingDist}(x, y) • 1$ and $\sum x_i - \sum y_i = \varepsilon - \varepsilon = 0$, giving $d • 1 = 0$. On the other hand, because $d = 2k + 1$ is odd, $d • 1 = 1$ in $\text{Fin } 2$, producing the contradiction $0 = 1$.

  1. In `Fin 2`, the difference $a - b$ equals 1 if $a \neq b$ and 0 if $a = b$. automation

    Because `Fin 2` has only two elements ($0$ and $1$), the identity is verified by exhaustively checking all four possible combinations of $a$ and $b$ using computational decision (`decide`).

    lines 1–5

    lemma binary_code_parity_class_avoids_odd_dist_sub_eq_ite (a b : Fin 2) :
        a - b = if a ≠ b then (1 : Fin 2) else 0 := by
      revert a b
      decide
    
  2. For any odd natural number $d$, the scalar multiple $d • 1$ in `Fin 2` equals 1.

    Since $d$ is odd, write $d = 2k + 1$ for some natural number $k$. Distributing scalar multiplication yields $(2k + 1) • 1 = k • (2 • 1) + 1 • 1$. In `Fin 2`, $2 • 1 = 0$, so $k • (2 • 1) = k • 0 = 0$. Thus $0 + 1 = 1$.

    lines 6–12

    uses add_smul, mul_comm, mul_smul, smul_zero, zero_add, one_smul

    lemma binary_code_parity_class_avoids_odd_dist_nsmul_one (d : ℕ) (hodd : Odd d) :
        d • (1 : Fin 2) = 1 := by
      rcases hodd with ⟨k, rfl⟩
      rw [add_smul, mul_comm, mul_smul]
      have h2 : (2 : ℕ) • (1 : Fin 2) = 0 := by decide
      rw [h2, smul_zero, zero_add, one_smul]
    
  3. Assume for contradiction that two binary words with the same coordinate-sum parity $\varepsilon$ have Hamming distance $d$.

    Introduce the words $x, y \in (\text{Fin } 2)^n$, the assumptions that both coordinate sums equal $\varepsilon$, and the hypothesis for contradiction that $\text{hammingDist}(x, y) = d$.

    lines 13–15

    /-- Any two binary words of the same coordinate-sum parity avoid any odd Hamming distance. -/
    theorem binary_code_parity_class_avoids_odd_dist (n d : ℕ) (hodd : Odd d) (ε : Fin 2) : ∀ x y : Fin n → Fin 2, (∑ i, x i) = ε → (∑ i, y i) = ε → hammingDist x y ≠ d := by
      intro x y hx hy hdist
  4. The Hamming distance between $x$ and $y$ satisfies $\text{hammingDist}(x, y) • 1 = 0$ in `Fin 2`.

    For each index $i$, the coordinate difference $x_i - y_i$ is 1 when $x_i \neq y_i$ and 0 otherwise. Summing over all coordinates shows that $\sum_i (x_i - y_i)$ counts the indices where the coordinates differ times 1, which by definition is $\text{hammingDist}(x, y) • 1$. On the other hand, the sum distributes as $\sum_i x_i - \sum_i y_i = \varepsilon - \varepsilon = 0$.

    lines 16–24

    uses binary_code_parity_class_avoids_odd_dist_sub_eq_ite, Finset.sum_filter, Finset.sum_const, Finset.sum_sub_distrib, sub_self

      have h_sum : hammingDist x y • (1 : Fin 2) = 0 := by
        have h (i : Fin n) : x i - y i = if x i ≠ y i then (1 : Fin 2) else 0 :=
          binary_code_parity_class_avoids_odd_dist_sub_eq_ite (x i) (y i)
        have h1 : hammingDist x y • (1 : Fin 2) = ∑ i, (x i - y i) := by
          simp_rw [h]
          rw [← Finset.sum_filter]
          rw [Finset.sum_const]
          rfl
        rw [h1, Finset.sum_sub_distrib, hx, hy, sub_self]
  5. Derive the contradiction $0 = 1$ in `Fin 2`. automation

    Substituting the distance assumption $\text{hammingDist}(x, y) = d$ into $\text{hammingDist}(x, y) • 1 = 0$ yields $d • 1 = 0$. However, since $d$ is odd, the helper lemma gives $d • 1 = 1$, which forces $0 = 1$ in `Fin 2`. This false statement is rejected by `decide`, completing the proof by contradiction.

    lines 25–31

    uses binary_code_parity_class_avoids_odd_dist_nsmul_one

      have h_d : d • (1 : Fin 2) = 0 := by
        rwa [← hdist]
      have h_odd : d • (1 : Fin 2) = 1 :=
        binary_code_parity_class_avoids_odd_dist_nsmul_one d hodd
      rw [h_d] at h_odd
      revert h_odd
      decide
add_smul
Scalar multiplication distributes over addition of scalars: $(r + s) • x = r • x + s • x$.
mul_comm
Multiplication is commutative: $a * b = b * a$.
mul_smul
Scalar multiplication by a product of scalars equals iterated scalar multiplication: $(x * y) • b = x • (y • b)$.
smul_zero
Scalar multiplication of any scalar with zero yields zero: $a • 0 = 0$.
zero_add
Zero is the left identity for addition: $0 + a = a$.
one_smul
Scalar multiplication by 1 is the identity: $1 • b = b$.
binary_code_parity_class_avoids_odd_dist_sub_eq_ite
In `Fin 2`, the difference $a - b$ equals 1 if $a \neq b$ and 0 if $a = b$.
Finset.sum_filter
Summing a function over elements satisfying a predicate equals summing over the whole set with non-satisfying terms replaced by 0.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Finset.sum_sub_distrib
The sum of termwise differences is the difference of the sums: $\sum (f(x) - g(x)) = \sum f(x) - \sum g(x)$.
sub_self
Subtracting an element from itself yields zero: $a - a = 0$.
binary_code_parity_class_avoids_odd_dist_nsmul_one
For any odd natural number $d$, the scalar multiple $d • 1$ in `Fin 2` equals 1.

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

lemma binary_code_parity_class_avoids_odd_dist_sub_eq_ite (a b : Fin 2) :    a - b = if a ≠ b then (1 : Fin 2) else 0 := by  revert a b  decidelemma binary_code_parity_class_avoids_odd_dist_nsmul_one (d : ℕ) (hodd : Odd d) :    d • (1 : Fin 2) = 1 := by  rcases hodd with ⟨k, rfl⟩  rw [add_smul, mul_comm, mul_smul]  have h2 : (2 : ℕ) • (1 : Fin 2) = 0 := by decide  rw [h2, smul_zero, zero_add, one_smul]/-- Any two binary words of the same coordinate-sum parity avoid any odd Hamming distance. -/theorem binary_code_parity_class_avoids_odd_dist (n d : ℕ) (hodd : Odd d) (ε : Fin 2) : ∀ x y : Fin n → Fin 2, (∑ i, x i) = ε → (∑ i, y i) = ε → hammingDist x y ≠ d := by  intro x y hx hy hdist  have h_sum : hammingDist x y • (1 : Fin 2) = 0 := by    have h (i : Fin n) : x i - y i = if x i ≠ y i then (1 : Fin 2) else 0 :=      binary_code_parity_class_avoids_odd_dist_sub_eq_ite (x i) (y i)    have h1 : hammingDist x y • (1 : Fin 2) = ∑ i, (x i - y i) := by      simp_rw [h]      rw [← Finset.sum_filter]      rw [Finset.sum_const]      rfl    rw [h1, Finset.sum_sub_distrib, hx, hy, sub_self]  have h_d : d • (1 : Fin 2) = 0 := by    rwa [← hdist]  have h_odd : d • (1 : Fin 2) = 1 :=    binary_code_parity_class_avoids_odd_dist_nsmul_one d hodd  rw [h_d] at h_odd  revert h_odd  decide
See it in the graphDiscuss this resultChallenge it