AFTD Auto-Formalizing Theoretical Domains

BadSingle

defimported Lean

For a parameter $\varepsilon\in\mathbb{R}$, a matrix $A$, and a vector $x\in\mathbb{R}^d$, the predicate $\texttt{BadSingle}\,\varepsilon\,A\,x$ holds when the squared-norm distortion is strictly too large: \[ \varepsilon \|x\|^2 < \bigl|\,\|Ax\|^2 - \|x\|^2\,\bigr|. \] This is the ``bad event'' whose probability must be controlled by the JL concentration argument.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in
variable {d k : ℕ} in
noncomputable def BadSingle (ε : ℝ) (A : Matrix (Fin k) (Fin d) ℝ)
    (x : EuclideanSpace ℝ (Fin d)) : Prop
Defined in
TCSlib, `BadSingle`
Lean proof
By Ganesh Sankar, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Ganesh Sankar. All rights reserved, 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
none listed
Used by 9
  • concentration_zeroConcentration bound at the zero vector. Let $\mu$ be a probability measure on a measurable space $\Omega$, let $\omega \mapsto A(\omega)$…
  • exists_isJLEmbedding_of_pair_boundProbabilistic method for JL embeddings. Let $\mu$ be a probability measure on $\Omega$, let $A : \Omega \to \mathbb{R}^{k\times d}$ be a…
  • johnson_lindenstrauss_of_gaussianJohnson–Lindenstrauss embedding from a Gaussian matrix. Fix dimensions $d$ and $k$ with $k \ge 1$, a distortion parameter…
  • johnson_lindenstraussJohnson–Lindenstrauss flattening lemma. Let $0 < \varepsilon < 1$ and let $n \ge 2$ be an integer. Suppose the target dimension $k$…
  • measurableSet_badSingleMeasurability of the single-vector distortion event. Fix a vector $x\in\bbr^d$ and a real number $\varepsilon$, and let…
  • jl_concentration_singleJohnson–Lindenstrauss concentration for a single vector. Let $k \ge 1$ and let $A$ be a random $k \times d$ matrix whose entries $A_{ij}$…
  • jl_concentration_single_via_chi_squaredJohnson–Lindenstrauss concentration for a single vector. Let $k \ge 1$, and let $A$ be a random $k \times d$ real matrix on a probability…
  • jl_union_boundUnion bound for Johnson–Lindenstrauss distortion. Let $(\Omega,\mu)$ be a probability space, and let $A\colon\Omega\to\bbr^{k\times d}$ be…
  • JLDistortion.of_not_badDistortion bound from a controlled single-vector event. Let $\varepsilon \in \bbr$, let $u, v \in \bbr^d$, and let $A$ be a real…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in
variable {d k : ℕ} in
/-- The "bad event" for a single vector `x` under the random projection `A`: the squared norm of `Ax` differs from the squared norm of `x` by strictly more than `ε‖x‖²`, that is, `ε‖x‖² < |‖Ax‖² − ‖x‖²|`. This is the failure event of [DG03, Lemma 2.2] (the event `|‖Ax‖² − ‖x‖²| > ε‖x‖²`), stated with strict inequality. -/
noncomputable def BadSingle (ε : ℝ) (A : Matrix (Fin k) (Fin d) ℝ)
    (x : EuclideanSpace ℝ (Fin d)) : Prop :=
  ε * ‖x‖ ^ 2 < |‖A.toEuclideanLin x‖ ^ 2 - ‖x‖ ^ 2|
See it in the graphDiscuss this resultChallenge it