CodingTheory.Johnson.inner_shifted_expand
Bilinear expansion of the shifted inner product. Let $\alpha \in \bbr$, let $x, y$ be binary words of length $n$, and write $\mathbf{1}$ for the all-ones vector in $\bbr^n$ and $s(x), s(y) \in \bbr^n$ for the $\pm 1$ embeddings of $x$ and $y$ (with $i$-th coordinate $-1$ where the corresponding bit is true and $+1$ otherwise). Form the shifted vectors $\hat{x}^\alpha = s(x) - \alpha \mathbf{1}$ and $\hat{y}^\alpha = s(y) - \alpha \mathbf{1}$. Then their Euclidean inner product expands as \[ \langle \hat{x}^\alpha,\, \hat{y}^\alpha \rangle = \langle s(x),\, s(y) \rangle - \alpha\,\langle s(x),\, \mathbf{1} \rangle - \alpha\,\langle s(y),\, \mathbf{1} \rangle + \alpha^2\,\langle \mathbf{1},\, \mathbf{1} \rangle. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators RealInnerProductSpace in open Finset in lemma CodingTheory.Johnson.inner_shifted_expand {n : ℕ} (α : ℝ) (x y : BitVec n) : ⟪shifted α x, shifted α y⟫_[ℝ] = ⟪pmOne x, pmOne y⟫_[ℝ] - α * ⟪pmOne x, ones (n := n)⟫_[ℝ] - α * ⟪pmOne y, ones (n := n)⟫_[ℝ] + α^2 * ⟪ones (n := n), ones (n := n)⟫_[ℝ]
- Source
- TCSlib, `CodingTheory.Johnson.inner_shifted_expand`
- 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.inner_shifted_expand← CodingTheory.Johnson.inner_shifted_expand (TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:99): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- CodingTheory.Johnson.onesThe vector in $\mathbb{R}^n$ all of whose coordinates equal $1$.
- CodingTheory.Johnson.BitVecThe type of binary words of length $n$, namely functions $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- CodingTheory.Johnson.pmOneThe map sending a binary word $x$ to the real vector in $\mathbb{R}^n$ whose $i$-th coordinate is $-1$ if $x_i = \texttt{true}$ and $+1$…
- CodingTheory.Johnson.shiftedFor a real parameter $\alpha$ and a binary word $x$, the vector…
- Used by 1
- 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…
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.inner_shifted_expand {n : ℕ} (α : ℝ) (x y : BitVec n) : ⟪shifted α x, shifted α y⟫_[ℝ] = ⟪pmOne x, pmOne y⟫_[ℝ] - α * ⟪pmOne x, ones (n := n)⟫_[ℝ] - α * ⟪pmOne y, ones (n := n)⟫_[ℝ] + α^2 * ⟪ones (n := n), ones (n := n)⟫_[ℝ] := by unfold shifted simp [RCLike.wInner]; simp [mul_sub, sub_mul, Finset.sum_sub_distrib, Finset.mul_sum _ _ _, pow_two]; simp [mul_comm, mul_assoc, sub_eq_add_neg] ring