AFTD Auto-Formalizing Theoretical Domains

CodingTheory.Johnson.binary_johnson_card_bound

theoremverifiedformalizationimported Lean

Binary Johnson cardinality bound. Let $n \ge 1$ and let $d$ be an integer with $1 \le d$ and $2d \le n$. Suppose $C$ is a finite set of binary words of length $n$ such that any two distinct words of $C$ are at Hamming distance at least $d$, and every word of $C$ has Hamming weight at most $w$. If $w \le J_2(n,d)$, where $J_2(n,d) = \tfrac{1}{2}\bigl(n - \sqrt{n(n-2d)}\bigr)$ is the binary Johnson radius, then $\abs{C} \le 2n$.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open scoped BigOperators RealInnerProductSpace in
open Finset in
open Classical in
open scoped RealInnerProductSpace in
open scoped InnerProductSpace in
open Finset in
theorem CodingTheory.Johnson.binary_johnson_card_bound
    {n d w : ℕ}
    (hn : 0 < n)
    (hd1 : 1 ≤ d)
    (hd : 2 * d ≤ n)
    (C : Finset (BitVec n))
    (hpair : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → d ≤ hdist x y)
    (hwt : ∀ x ∈ C, wt x ≤ w)
    (hwJ : (w : ℝ) ≤ J2 n d) :
    C.card ≤ 2 * n
Formalizes
Binary Johnson cardinality bound, as formalized in TCSlib (`CodingTheory.Johnson.binary_johnson_card_bound`)
Lean proof
By Allan Li, Frederick Dehmel, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen scoped BigOperators RealInnerProductSpace inopen Finset inopen Classical inopen scoped RealInnerProductSpace inopen scoped InnerProductSpace inopen Finset intheorem CodingTheory.Johnson.binary_johnson_card_bound    {n d w : ℕ}    (hn : 0 < n)    (hd1 : 1 ≤ d)    (hd : 2 * d ≤ n)    (C : Finset (BitVec n))    (hpair : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → d ≤ hdist x y)    (hwt : ∀ x ∈ C, wt x ≤ w)    (hwJ : (w : ℝ) ≤ J2 n d) :    C.card ≤ 2 * n := by  let α : ℝ := alpha n d  have hα0 : 0 ≤ α := by    simpa [α] using alpha_nonneg n d  have hα1 : α < 1 := by    simpa [α] using alpha_lt_one_of_hd1 (n := n) (d := d) hn hd1 hd  have hnonzero : ∀ x ∈ C, shifted α x ≠ 0 := by    intro x hx    exact shifted_ne_zero_of_alpha_lt_one (n := n) hn hα0 hα1 x  have harith :      ((n : ℝ) - 2 * (d : ℝ))        + α^2 * (n : ℝ)        + 2 * α * (2 * (w : ℝ) - (n : ℝ))        ≤ 0 := by    simpa [α] using johnson_arith (n := n) (d := d) (w := w) hn hd hwJ  exact binary_johnson_card_bound_parametric    (n := n) (d := d) (w := w)    hn C hpair hwt α hα0 hnonzero harith
See it in the graphDiscuss this resultChallenge it