AFTD Auto-Formalizing Theoretical Domains

BadPair

defimported Lean

Given a $k \times d$ matrix $A$ and a finite set $V \subseteq \mathbb{R}^d$, BadPair $\varepsilon\; V\; A$ holds when there exists some ordered pair $(u, v) \in V \times V$ whose images under $A$ fail the distortion predicate, i.e.\ the projection distorts that pair by more than a factor of $\varepsilon$.

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 BadPair (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d)))
    (A : Matrix (Fin k) (Fin d) ℝ) : Prop
Defined in
TCSlib, `BadPair`
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
Built on 1
  • JLDistortionFor $\varepsilon \in \mathbb{R}$, vectors $u, v \in \mathbb{R}^d$, and their images $u', v' \in \mathbb{R}^k$, JLDistortion…
Used by 2
  • 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…
  • 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…

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 the whole set `V` under the matrix `A`: some ordered pair `(u, v) ∈ V × V` fails the `(1 ± ε)` distortion bound `JLDistortion` under `A` [DG03, proof of Thm 2.1]. -/
noncomputable def BadPair (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d)))
    (A : Matrix (Fin k) (Fin d) ℝ) : Prop :=
  ∃ u ∈ V, ∃ v ∈ V, ¬ JLDistortion ε u v
    (A.toEuclideanLin u) (A.toEuclideanLin v)
See it in the graphDiscuss this resultChallenge it