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.CodingTheory.Johnson.binary_johnson_card_bound← CodingTheory.Johnson.binary_johnson_card_bound (TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:554): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 14
- CodingTheory.Johnson.alpha_lt_one_of_hd1The shift parameter is less than one. Let $n$ and $d$ be natural numbers with $n \ge 1$, $d \ge 1$, and $2d \le n$. Then the shift…
- CodingTheory.Johnson.alphaThe real quantity \[ \alpha(n,d) \;=\; \sqrt{\frac{n - 2d}{n}}. \]
- CodingTheory.Johnson.BitVecThe type of binary words of length $n$, namely functions $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- CodingTheory.Johnson.johnson_arithJohnson arithmetic inequality. Let $n$, $d$, and $w$ be natural numbers with $n > 0$ and $2d \le n$, and write $\alpha = \alpha(n,d)$ for…
- CodingTheory.Johnson.binary_johnson_card_bound_parametricJohnson cardinality bound, parametric form. Let $n \ge 1$, let $d, w$ be natural numbers, and let $C$ be a finite set of binary words of…
- CodingTheory.Johnson.shifted_ne_zero_of_alpha_lt_oneShifted $\pm 1$ vectors are nonzero for $\alpha < 1$. Let $n \ge 1$ and let $\alpha$ be a real number with $0 \le \alpha < 1$. Then for…
- CodingTheory.Johnson.wtFor a binary word $x$ of length $n$, its weight is the number of coordinates where $x$ takes the value
true:… - CodingTheory.Johnson.pmOne_apply_trueValue of the ±1 embedding at a true coordinate. Let $x$ be a binary word of length $n$, and let $s(x) \in \bbr^n$ denote its $\pm1$…
- CodingTheory.Johnson.hdistFor binary words $x,y$ of length $n$, the Hamming distance is the number of coordinates on which they differ:…
- CodingTheory.Johnson.alpha_nonnegNonnegativity of the shift parameter. For all natural numbers $n$ and $d$, the shift parameter $\alpha(n,d) = \sqrt{(n - 2d)/n}$ satisfies…
- CodingTheory.Johnson.J2The real quantity \[ J_2(n,d) \;=\; \frac{n - \sqrt{n\,(n - 2d)}}{2}. \]
- CodingTheory.Johnson.pmOne_apply_falseValue of the $\pm 1$ embedding at a false coordinate. Let $x$ be a binary word of length $n$, and let the $\pm 1$ embedding send $x$ to…
- CodingTheory.Johnson.shiftedFor a real parameter $\alpha$ and a binary word $x$, the vector…
- CodingTheory.Johnson.EucAbbreviation for the $n$-dimensional real Euclidean space $\mathbb{R}^n$ with the $\ell^2$ inner product, i.e.\
EuclideanSpace…
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.
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