AFTD Auto-Formalizing Theoretical Domains

CodingTheory.Johnson.inner_shifted_le_expr

theoremverifiedimported Lean

Upper 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 natural numbers for which the Hamming distance between $x$ and $y$ is at least $d$ and the Hamming weights of $x$ and $y$ are each at most $w$. Writing $\hat{x}^\alpha$ and $\hat{y}^\alpha$ for the corresponding shifted vectors in $\mathbb{R}^n$ — the $\pm 1$ embedding of the word minus $\alpha$ times the all-ones vector — their Euclidean inner product satisfies \[ \langle \hat{x}^\alpha, \hat{y}^\alpha \rangle \;\le\; (n - 2d) + \alpha^2 n + 2\alpha\,(2w - n). \]

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open scoped BigOperators RealInnerProductSpace in
open Finset in
lemma CodingTheory.Johnson.inner_shifted_le_expr
    {n d w : ℕ} {α : ℝ} {x y : BitVec n}
    (hα : 0 ≤ α)
    (hxy_dist : d ≤ hdist x y)
    (hx_wt : wt x ≤ w)
    (hy_wt : wt y ≤ w) :
    ⟪shifted α x, shifted α y⟫_[ℝ]
      ≤ ((n : ℝ) - 2 * (d : ℝ))
        + α^2 * (n : ℝ)
        + 2 * α * (2 * (w : ℝ) - (n : ℝ))
Source
TCSlib, `CodingTheory.Johnson.inner_shifted_le_expr`
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 12
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen scoped BigOperators RealInnerProductSpace inopen Finset inlemma CodingTheory.Johnson.inner_shifted_le_expr    {n d w : ℕ} {α : ℝ} {x y : BitVec n}    (hα : 0 ≤ α)    (hxy_dist : d ≤ hdist x y)    (hx_wt : wt x ≤ w)    (hy_wt : wt y ≤ w) :    ⟪shifted α x, shifted α y⟫_[ℝ]      ≤ ((n : ℝ) - 2 * (d : ℝ))        + α^2 * (n : ℝ)        + 2 * α * (2 * (w : ℝ) - (n : ℝ)) := by  have h_inner_bound : (RCLike.wInner 1 (CodingTheory.Johnson.shifted α x) (CodingTheory.Johnson.shifted α y)) = (n - 2 * (hdist x y : ℝ)) - α * (n - 2 * (wt x : ℝ)) - α * (n - 2 * (wt y : ℝ)) + α^2 * n := by    convert inner_shifted_expand α x y using 1;    erw [ inner_pmOne_pmOne, inner_pmOne_ones, inner_ones_ones ] ; norm_num ; ring_nf;    erw [ inner_pmOne_ones ] ; norm_num ; ring_nf ; aesop;  nlinarith [ ( by norm_cast : ( d : ℝ ) ≤ CodingTheory.Johnson.hdist x y ), ( by norm_cast : ( CodingTheory.Johnson.wt x : ℝ ) ≤ w ), ( by norm_cast : ( CodingTheory.Johnson.wt y : ℝ ) ≤ w ) ]
See it in the graphDiscuss this resultChallenge it