CodingTheory.Johnson.shifted_ne_zero_of_alpha_lt_one
theoremverifiedimported Lean
Shifted $\pm 1$ vectors are nonzero for $\alpha < 1$. Let $n \ge 1$ and let $\alpha$ be a real number with $0 \le \alpha < 1$. Then for every binary word $x$ of length $n$, the shifted vector $\hat{x}^\alpha \in \bbr^n$ — obtained from the $\pm 1$ embedding of $x$ by subtracting $\alpha$ times the all-ones vector — is nonzero.
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 lemma CodingTheory.Johnson.shifted_ne_zero_of_alpha_lt_one {n : ℕ} (hn : 0 < n) {α : ℝ} (hα0 : 0 ≤ α) (hα1 : α < 1) (x : BitVec n) : shifted α x ≠ 0
- Source
- TCSlib, `CodingTheory.Johnson.shifted_ne_zero_of_alpha_lt_one`
- 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.shifted_ne_zero_of_alpha_lt_one← CodingTheory.Johnson.shifted_ne_zero_of_alpha_lt_one (TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:454): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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.EucAbbreviation for the $n$-dimensional real Euclidean space $\mathbb{R}^n$ with the $\ell^2$ inner product, i.e.\
EuclideanSpace… - CodingTheory.Johnson.shiftedFor a real parameter $\alpha$ and a binary word $x$, the vector…
- 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 inlemma CodingTheory.Johnson.shifted_ne_zero_of_alpha_lt_one {n : ℕ} (hn : 0 < n) {α : ℝ} (hα0 : 0 ≤ α) (hα1 : α < 1) (x : BitVec n) : shifted α x ≠ 0 := by intro hzero let i : Fin n := ⟨0, hn⟩ have hcoord : shifted α x i = 0 := by have h := congrArg (fun v : Euc n => v i) hzero simpa using h by_cases hx : x i · have hform : shifted α x i = (-1 : ℝ) - α := by simp [shifted, pmOne, ones, hx] linarith · have hform : shifted α x i = (1 : ℝ) - α := by simp [shifted, pmOne, ones, hx] linarith