CodingTheory.Johnson.binary_johnson_card_bound_parametric
theoremverifiedimported Lean
Johnson 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 length $n$ such that any two distinct words of $C$ are at Hamming distance at least $d$, and every word of $C$ has weight at most $w$. Suppose $\alpha \ge 0$ is a real parameter for which the shifted $\pm 1$ vector $\hat{x}^\alpha$ is nonzero for every $x \in C$, and for which \[ (n - 2d) + \alpha^2 n + 2\alpha(2w - n) \le 0 . \] 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_parametric {n d w : ℕ} (_hn : 0 < n) (C : Finset (BitVec n)) (hpair : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → d ≤ hdist x y) (hwt : ∀ x ∈ C, wt x ≤ w) (α : ℝ) (hα : 0 ≤ α) (hnonzero : ∀ x ∈ C, shifted α x ≠ 0) (harith : ((n : ℝ) - 2 * (d : ℝ)) + α^2 * (n : ℝ) + 2 * α * (2 * (w : ℝ) - (n : ℝ)) ≤ 0) : C.card ≤ 2 * n
- Source
- TCSlib, `CodingTheory.Johnson.binary_johnson_card_bound_parametric`
- 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_parametric← CodingTheory.Johnson.binary_johnson_card_bound_parametric (TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:471): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- CodingTheory.Johnson.rankin_finset_boundRankin bound for pairwise obtuse unit vectors. Let $S$ be a finite set of vectors in the Euclidean space $\bbr^n$, each of norm $1$, such…
- CodingTheory.Johnson.BitVecThe type of binary words of length $n$, namely functions $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- CodingTheory.Johnson.inner_shifted_le_exprUpper bound on the shifted inner product. Let $x$ and $y$ be binary words of length $n$, and let $\alpha \ge 0$. Suppose $d$ and $w$ are…
- 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.EucAbbreviation for the $n$-dimensional real Euclidean space $\mathbb{R}^n$ with the $\ell^2$ inner product, i.e.\
EuclideanSpace… - CodingTheory.Johnson.hdistFor binary words $x,y$ of length $n$, the Hamming distance is the number of coordinates on which they differ:…
- 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.normalizeThe rescaling $u \mapsto \norm{u}^{-1} \cdot u$ of a vector of $\mathbb{R}^n$.
- Used by 1
- CodingTheory.Johnson.binary_johnson_card_boundBinary 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…
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_parametric {n d w : ℕ} (_hn : 0 < n) (C : Finset (BitVec n)) (hpair : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → d ≤ hdist x y) (hwt : ∀ x ∈ C, wt x ≤ w) (α : ℝ) (hα : 0 ≤ α) (hnonzero : ∀ x ∈ C, shifted α x ≠ 0) (harith : ((n : ℝ) - 2 * (d : ℝ)) + α^2 * (n : ℝ) + 2 * α * (2 * (w : ℝ) - (n : ℝ)) ≤ 0) : C.card ≤ 2 * n := by classical let u : BitVec n → Euc n := fun x => shifted α x have hpair_u : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → ⟪u x, u y⟫_[ℝ] ≤ 0 := by intro x hx y hy hxy have hdist_xy : d ≤ hdist x y := hpair x hx y hy hxy have hwt_x : wt x ≤ w := hwt x hx have hwt_y : wt y ≤ w := hwt y hy have h1 : ⟪u x, u y⟫_[ℝ] ≤ ((n : ℝ) - 2 * (d : ℝ)) + α^2 * (n : ℝ) + 2 * α * (2 * (w : ℝ) - (n : ℝ)) := by simpa [u] using (inner_shifted_le_expr (n := n) (d := d) (w := w) (α := α) (x := x) (y := y) hα hdist_xy hwt_x hwt_y) linarith let U : Finset (Euc n) := C.image (fun x => normalize (u x)) have h_injOn : Set.InjOn (fun x : BitVec n => normalize (u x)) (↑C : Set (BitVec n)) := by intro x hx y hy; have := hnonzero x hx; have := hnonzero y hy; simp_all +decide [ normalize ] ; intro h_eq; specialize hpair_u x hx y hy; contrapose! hpair_u; simp_all +decide [ RCLike.wInner ] ; -- Since $u x = ‖u x‖ • ‖u y‖⁻¹ • u y$, we can substitute this into the inner product. have h_inner : ∑ i, u y i * u x i = ‖u x‖ * ‖u y‖⁻¹ * ∑ i, u y i * u y i := by have h_inner : u x = ‖u x‖ • ‖u y‖⁻¹ • u y := by rw [ ← h_eq, smul_smul, mul_inv_cancel₀ ( norm_ne_zero_iff.mpr ( hnonzero x hx ) ), one_smul ]; conv_lhs => rw [ h_inner ] ; simp +decide [ mul_assoc, mul_comm, mul_left_comm, Finset.mul_sum _ _ _ ] ; simp +decide only [Finset.mul_sum _ _ _, mul_comm, mul_assoc]; rw [ h_inner ]; refine' mul_pos ( mul_pos ( norm_pos_iff.mpr ( hnonzero x hx ) ) ( inv_pos.mpr ( norm_pos_iff.mpr ( hnonzero y hy ) ) ) ) ( lt_of_le_of_ne ( Finset.sum_nonneg fun _ _ => mul_self_nonneg _ ) ( Ne.symm _ ) ) ; intro H ; simp_all +decide [ Finset.sum_eq_zero_iff_of_nonneg, mul_self_nonneg ] ; exact hnonzero y hy ( PiLp.ext H ) have hcardU : U.card = C.card := by unfold U exact Finset.card_image_of_injOn h_injOn have hunitU : ∀ z ∈ U, ‖z‖ = 1 := by intro z hz rcases Finset.mem_image.mp hz with ⟨x, hxC, rfl⟩ have hx0 : u x ≠ 0 := hnonzero x hxC simp [normalize]; -- The norm of a scalar multiple of a vector is the absolute value of the scalar times the norm of the vector simp [norm_smul, hx0] have hpairU : ∀ a ∈ U, ∀ b ∈ U, a ≠ b → ⟪a, b⟫_[ℝ] ≤ 0 := by intro a ha b hb hab rcases Finset.mem_image.mp ha with ⟨x, hxC, rfl⟩ rcases Finset.mem_image.mp hb with ⟨y, hyC, rfl⟩ have hx0 : u x ≠ 0 := hnonzero x hxC have hy0 : u y ≠ 0 := hnonzero y hyC have hxy : x ≠ y := by intro hEq apply hab simp [normalize, hEq] have hbase : ⟪u x, u y⟫_[ℝ] ≤ 0 := hpair_u x hxC y hyC hxy -- Since the norms are 1 the inner product simplifies to the inner product of the original vectors have h_inner_simplified : ⟪normalize (u x), normalize (u y)⟫_[ℝ] = (1 / (‖u x‖ * ‖u y‖)) * ⟪u x, u y⟫_[ℝ] := by simp +decide [ normalize, RCLike.wInner ] ; ring_nf; simp +decide only [mul_assoc, mul_left_comm, Finset.mul_sum _ _ _]; exact h_inner_simplified.symm ▸ mul_nonpos_of_nonneg_of_nonpos ( one_div_nonneg.mpr ( mul_nonneg ( norm_nonneg _ ) ( norm_nonneg _ ) ) ) hbase have h_rankin : U.card ≤ 2 * n := rankin_finset_bound (n := n) U hunitU hpairU simpa [hcardU] using h_rankin