Theorem 11.3.3 — Dvoretzky-Milman's theorem (Gaussian form)
ProvedHighDimProb.DvoretzkyMilman.dvoretzky_milmanThis is Dvoretzky-Milman's theorem, the book's own closing theorem and the capstone the whole book builds toward: a random Gaussian projection of a high-dimensional set is, with high probability, almost a round ball — quantitatively, the convex hull of the image of a bounded set under a Gaussian random matrix sandwiches between two concentric Euclidean balls whose radii differ by only a factor of , as soon as the number of measurements exceeds (a constant times) the stable dimension of .
Let be an Gaussian random matrix with i.i.d. entries, a bounded set containing the origin, and . Suppose , where is the stable dimension of . Then with probability at least ,
where is the Euclidean ball of radius centered at the origin.
Formalization Note is Ω → Matrix (Fin m) (Fin n) ℝ with IsGaussianMatrix P A.
is StableDimension w diam for explicit real witnesses of GaussianWidth T and
Metric.diam T (see StableDimension's own note on the -vs--based formalization
choice). is convexHull ℝ of the image of under 's mulVec. The
book's own proof reduces the general case to containing the origin by translation
("Translating if necessary, we can assume that contains the origin"; Remark 11.3.4);
this formalization states that WLOG-reduced case directly, adding as an explicit
hypothesis rather than formalizing the translation step itself — a disclosed deviation from
the literal, untranslated printed statement, recorded in STATUS.md.
import Mathlib import Definitions.Def_HighDimProb_DvoretzkyMilman_ExpSup import Definitions.Def_HighDimProb_DvoretzkyMilman_GaussianWidth import Definitions.Def_HighDimProb_DvoretzkyMilman_StableDimension import Definitions.Def_HighDimProb_DvoretzkyMilman_IsGaussianMatrix open MeasureTheory ProbabilityTheory
namespace HighDimProb.DvoretzkyMilman
/-- **Theorem 11.3.3** (Dvoretzky-Milman's theorem: Gaussian form), Vershynin, *High-Dimensional
Probability* (2018), p. 276 (PDF p. 284) — the book's own closing theorem.
"Let `A` be an `m × n` Gaussian random matrix with i.i.d. `N(0, 1)` entries, `T ⊂ ℝⁿ` be a bounded
set, and let `ε ∈ (0,1)`. Suppose `m ≤ cε²d(T)` where `d(T)` is the stable dimension of `T`
introduced in Section 7.6. Then with probability at least `0.99`, we have `(1−ε)B ⊂ conv(AT) ⊂
(1+ε)B` where `B` is a Euclidean ball with radius `w(T)`."
`A` is `Ω → Matrix (Fin m) (Fin n) ℝ` with `IsGaussianMatrix P A` (reused per rule, this chunk's
own copy since `08-matrix-deviation`'s analogous machinery is a still-draft definition). `d(T)` is
`stableDimension w diam` for explicit real witnesses `w`/`diam` of `gaussianWidth T`/`Metric.diam
T` respectively — see `Def_HighDimProb_DvoretzkyMilman_StableDimension.lean` for the disclosed
`w`-vs-`h`-based formalization choice. `conv(AT)` is `convexHull ℝ (image of T under
Matrix.mulVec ∘ A ω)`.
**Ball center**: the book's own proof opens "Translating `T` if necessary, we can assume that `T`
contains the origin," and Remark 11.3.4 confirms the ball `B` is then centered at the origin
(otherwise at an arbitrary fixed point of `T`). This formalization adds `(0 : EuclideanSpace ℝ
(Fin n)) ∈ T` as an explicit hypothesis rather than the fully general (translated) statement, i.e.
states the WLOG-reduced case the book's own proof reduces every case to — disclosed in
`STATUS.md`/`MODERATION_NOTES.md` as a deviation from the literal printed theorem (which has no
such hypothesis, only the surrounding proof's reduction), made for tractability; the general case
follows from this one by the same translation argument the book's own proof performs, and is not
formalized here. -/
theorem dvoretzky_milman :
∃ c : ℝ, 0 < c ∧
∀ {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{m n : ℕ} (A : Ω → Matrix (Fin m) (Fin n) ℝ),
IsGaussianMatrix P A →
∀ (T : Set (EuclideanSpace ℝ (Fin n))), Bornology.IsBounded T →
(0 : EuclideanSpace ℝ (Fin n)) ∈ T →
∀ (ε : ℝ), 0 < ε → ε < 1 →
∀ (w : ℝ), gaussianWidth T = (w : EReal) →
(m : ℝ) ≤ c * ε ^ 2 * stableDimension w (Metric.diam T) →
(99 / 100 : ENNReal) ≤
P {ω |
Metric.closedBall (0 : EuclideanSpace ℝ (Fin m)) ((1 - ε) * w) ⊆
convexHull ℝ ((fun x : EuclideanSpace ℝ (Fin n) =>
(EuclideanSpace.equiv (Fin m) ℝ).symm ((A ω).mulVec x)) '' T) ∧
convexHull ℝ ((fun x : EuclideanSpace ℝ (Fin n) =>
(EuclideanSpace.equiv (Fin m) ℝ).symm ((A ω).mulVec x)) '' T) ⊆
Metric.closedBall (0 : EuclideanSpace ℝ (Fin m)) ((1 + ε) * w)} := by sorry
end HighDimProb.DvoretzkyMilman
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.