AFTD Auto-Formalizing Theoretical Domains

CodingTheory.Johnson.inner_pmOne_ones

theoremverifiedimported Lean

Inner product of the ±1 embedding with the all-ones vector. Let $x$ be a binary word of length $n$, and let $s(x) \in \bbr^n$ denote its $\pm1$ embedding, the vector whose $i$-th coordinate is $-1$ at each position where $x_i$ is set and $+1$ elsewhere. Writing $\mathbf{1}$ for the all-ones vector and $\mathrm{wt}(x)$ for the Hamming weight of $x$ (the number of positions at which $x$ is set), the $\ell^2$ inner product satisfies \[ \langle s(x), \mathbf{1} \rangle = n - 2\,\mathrm{wt}(x). \]

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open scoped BigOperators RealInnerProductSpace in
open Finset in
lemma CodingTheory.Johnson.inner_pmOne_ones {n : ℕ} (x : BitVec n) :
    ⟪pmOne x, ones⟫_[ℝ] = (n : ℝ) - 2 * (wt x : ℝ)
Source
TCSlib, `CodingTheory.Johnson.inner_pmOne_ones`
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 7
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_pmOne_ones {n : ℕ} (x : BitVec n) :    ⟪pmOne x, ones⟫_[ℝ] = (n : ℝ) - 2 * (wt x : ℝ) := by  have h_inner_expanded : RCLike.wInner 1 (CodingTheory.Johnson.pmOne x) CodingTheory.Johnson.ones = ∑ i, (pmOne x i) * (ones i) := by    simp [RCLike.wInner];  have h_sum_simplified : ∑ i, (pmOne x i) * (ones i) = ∑ i, (if x i then -1 else 1 : ℝ) := by    exact Finset.sum_congr rfl fun i _ => by unfold CodingTheory.Johnson.pmOne CodingTheory.Johnson.ones; aesop;  simp_all +decide [ Finset.sum_ite ];  rw [ show ( Finset.univ.filter fun i => x i = Bool.false ) = Finset.univ \ ( Finset.univ.filter fun i => x i = Bool.true ) by ext; aesop, Finset.card_sdiff ] ; norm_num ; ring_nf!;  rw [ Nat.cast_sub ( show _ ≤ _ from le_trans ( Finset.card_le_univ _ ) ( by norm_num ) ) ] ; ring;
See it in the graphDiscuss this resultChallenge it