AFTD Auto-Formalizing Theoretical Domains

binary_code_odd_forbidden_dist_max_size

theoremverifiedformalization

Let n ≥ 1 and 1 ≤ d ≤ n be integers such that d is odd. Then every subset F : Finset (Fin n → Fin 2) such that no two elements of F have Hamming distance d satisfies F.card ≤ 2 ^ (n - 1), and there exists a subset F : Finset (Fin n → Fin 2) with no two elements having Hamming distance d whose cardinality is 2 ^ (n - 1).

Statement

theorem binary_code_odd_forbidden_dist_max_size (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (hodd : Odd d) : (∀ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) → F.card ≤ 2 ^ (n - 1)) ∧ ∃ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) ∧ F.card = 2 ^ (n - 1)
Formalizes
arXiv:2611.04523, Proposition 3.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • binary_code_parity_class_avoids_odd_distFor 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…
  • binary_code_parity_class_cardFor any integer n ≥ 1 and any parity ε : Fin 2, the set of words x : Fin n → Fin 2 whose sum of coordinates in Fin 2 equals ε has…
  • binary_code_avoids_odd_dist_card_leLet n ≥ 1 and 1 ≤ d ≤ n. Every finite set of binary words F : Finset (Fin n → Fin 2) such that no two elements have Hamming distance d…

Read back from the Lean

For any natural numbers $n$ and $d$ such that $1 \le n$, $1 \le d \le n$, and $d$ is odd: 1. For every finite subset $F$ of binary words of length $n$ (functions Fin n → Fin 2), if no two (not necessarily distinct) elements $x, y \in F$ have Hamming distance equal to $d$, then the cardinality of $F$ is at most $2^{n - 1}$. 2. There exists a finite subset $F$ of binary words of length $n$ such that no two elements $x, y \in F$ have Hamming distance equal to $d$, and the cardinality of $F$ is exactly $2^{n - 1}$.

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 establishes that the maximum size of a binary code of length n avoiding an odd Hamming distance d is 2^(n-1). The upper bound |F| ≤ 2^(n-1) holds by a previously proved lemma `binary_code_avoids_odd_dist_card_le`. The bound is tight because the code consisting of all words of even parity has size 2^(n-1), and any two words with the same parity differ in an even number of positions, so their Hamming distance can never be the odd integer d.

  1. Every binary code F on {0, 1}ⁿ avoiding Hamming distance d has cardinality at most 2^(n-1).

    This is the upper bound half of the conjunction, which follows directly from the previously proven lemma `binary_code_avoids_odd_dist_card_le`.

    line 3

    uses binary_code_avoids_odd_dist_card_le

      refine ⟨fun F hF => binary_code_avoids_odd_dist_card_le n d hn hd hdn F hF, ?_⟩
  2. It suffices to exhibit the code of even-parity words and show it avoids Hamming distance d with size 2^(n-1).

    We provide the explicit candidate witness F = {x ∈ {0, 1}ⁿ | ∑ i, x i = 0}, the set of all binary words whose coordinate sum is even (zero in Fin 2). This reduces the existence claim to verifying that no two elements in F have Hamming distance d and that |F| = 2^(n-1).

    line 4

      refine ⟨Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = 0), ?_, ?_⟩
  3. No two words in the even-parity code have Hamming distance d.

    Given two words x, y in the filtered set, we unfold the filter definition with `Finset.mem_filter` to extract that both have coordinate sum 0. By `binary_code_parity_class_avoids_odd_dist`, words with the same parity cannot have an odd Hamming distance d.

    lines 5–7

    uses Finset.mem_filter, binary_code_parity_class_avoids_odd_dist

      · intro x hx y hy
        rw [Finset.mem_filter] at hx hy
        exact binary_code_parity_class_avoids_odd_dist n d hodd 0 x y hx.2 hy.2
  4. The even-parity code has cardinality 2^(n-1).

    By `binary_code_parity_class_card`, the parity class with sum 0 of binary words of length n ≥ 1 contains exactly 2^(n-1) elements.

    line 8

    uses binary_code_parity_class_card

      · exact binary_code_parity_class_card n hn 0
binary_code_avoids_odd_dist_card_le
For n ≥ 1 and 1 ≤ d ≤ n, any subset of {0, 1}ⁿ containing no two elements at Hamming distance d has cardinality at most 2^(n-1).
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
binary_code_parity_class_avoids_odd_dist
If d is an odd integer, then any two binary words of length n with the same coordinate sum in Fin 2 (i.e. the same parity) cannot have Hamming distance d.
binary_code_parity_class_card
For n ≥ 1, the number of binary words of length n with a given coordinate sum parity ε ∈ Fin 2 is exactly 2^(n-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

/-- The maximum cardinality of a binary code in {0,1}^n avoiding an odd Hamming distance d is 2^(n-1). -/theorem binary_code_odd_forbidden_dist_max_size (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (hodd : Odd d) : (∀ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) → F.card ≤ 2 ^ (n - 1)) ∧ ∃ F : Finset (Fin n → Fin 2), (∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) ∧ F.card = 2 ^ (n - 1) := by  refine ⟨fun F hF => binary_code_avoids_odd_dist_card_le n d hn hd hdn F hF, ?_⟩  refine ⟨Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = 0), ?_, ?_⟩  · intro x hx y hy    rw [Finset.mem_filter] at hx hy    exact binary_code_parity_class_avoids_odd_dist n d hodd 0 x y hx.2 hy.2  · exact binary_code_parity_class_card n hn 0
See it in the graphDiscuss this resultChallenge it