CodingTheory.Johnson.johnson_arith
theoremverifiedimported Lean
Johnson arithmetic inequality. Let $n$, $d$, and $w$ be natural numbers with $n > 0$ and $2d \le n$, and write $\alpha = \alpha(n,d)$ for the shift parameter and $J_2(n,d)$ for the binary Johnson radius. If $w \le J_2(n,d)$, then \[ (n - 2d) + \alpha^2\, n + 2\alpha\,(2w - n) \;\le\; 0. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators RealInnerProductSpace in open Finset in lemma CodingTheory.Johnson.johnson_arith {n d w : ℕ} (hn : 0 < n) (hd : 2 * d ≤ n) (hw : (w : ℝ) ≤ J2 n d) : ((n : ℝ) - 2 * (d : ℝ)) + (alpha n d)^2 * (n : ℝ) + 2 * (alpha n d) * (2 * (w : ℝ) - (n : ℝ)) ≤ 0
- Source
- TCSlib, `CodingTheory.Johnson.johnson_arith`
- 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.johnson_arith← CodingTheory.Johnson.johnson_arith (TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:160): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- CodingTheory.Johnson.alphaThe real quantity \[ \alpha(n,d) \;=\; \sqrt{\frac{n - 2d}{n}}. \]
- CodingTheory.Johnson.J2The real quantity \[ J_2(n,d) \;=\; \frac{n - \sqrt{n\,(n - 2d)}}{2}. \]
- 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 inlemma CodingTheory.Johnson.johnson_arith {n d w : ℕ} (hn : 0 < n) (hd : 2 * d ≤ n) (hw : (w : ℝ) ≤ J2 n d) : ((n : ℝ) - 2 * (d : ℝ)) + (alpha n d)^2 * (n : ℝ) + 2 * (alpha n d) * (2 * (w : ℝ) - (n : ℝ)) ≤ 0 := by have h_subst : 2 * (w : ℝ) ≤ n - Real.sqrt (n * (n - 2 * d)) := by unfold CodingTheory.Johnson.J2 at hw; linarith; rw [ show ( CodingTheory.Johnson.alpha n d ) = Real.sqrt ( ( n - 2 * d ) / n ) by rfl, Real.sq_sqrt <| div_nonneg ( sub_nonneg.2 <| mod_cast hd ) <| Nat.cast_nonneg _ ]; rw [ Real.sqrt_div ( by nlinarith [ ( by norm_cast : ( 2 * d :ℝ ) ≤ n ) ] ) ] at *; rw [ Real.sqrt_mul <| by positivity ] at h_subst; field_simp; nlinarith [ show 0 ≤ Real.sqrt n * Real.sqrt ( n - 2 * d ) by positivity, show 0 ≤ Real.sqrt n by positivity, show 0 ≤ Real.sqrt ( n - 2 * d ) by positivity, Real.mul_self_sqrt ( show ( n : ℝ ) ≥ 0 by positivity ), Real.mul_self_sqrt ( show ( n - 2 * d : ℝ ) ≥ 0 by exact sub_nonneg_of_le ( mod_cast hd ) ) ]/-The inner product of the projections of two vectors x and y onto the orthogonal complement of u is non-positive, provided x and y have non-positive inner products with each other and with u.-/