AFTD Auto-Formalizing Theoretical Domains

CodingTheory.Johnson.inner_shifted_expand

theoremverifiedimported Lean

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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
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_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
See it in the graphDiscuss this resultChallenge it