A constructive solution to Talagrand's Gaussian convexification problem

Abstract

Talagrand asked for a construction of a large convex subset of a bounded Minkowski sum of a large Gaussian set. We first prove a stronger nonsymmetric existential statement: if $A\subset {\mathbb{R}}^n$ is measurable and ${\gamma }_n(A)>2/3$, then $A+A+A$ contains a compact convex set of Gaussian measure at least $1/2$. Let now $A$ be closed with ${\gamma }_n(A)\ge 7/8$, let $\Phi$ be the standard Gaussian distribution function, and put $a_0={\Phi }^{-1}(3/4)$. For every $\Lambda >1$ and every $0<p<2\Phi (\Lambda a_0)-1$ we construct a centrally symmetric finite polytope $C\subset \Lambda (A+A+A)$ with ${\gamma }_n(C)\ge p$. Thus measure $3/4$ is obtained for every $\Lambda >1.705510\dots$. We give matching upper and lower bounds for the optimal high-measure dilation and show that the dilation profile used by the construction is sharp among all symmetric half-measure cores. Finally, if ${\gamma }_n(A)\ge 5/6+\eta$, we construct, for every $0<\epsilon \le 1/2$, a centered ellipsoid $E_{\epsilon }$ with ${\gamma }_n(E_{\epsilon })\ge 1-\epsilon$ and \begin{equation} \frac{c}{Φ^{-1}(1-\varepsilon/2)}\sqrt{\frac{\log n}{n}}\,E_\varepsilon\subset A+A+A. \end{equation} Both the dimension dependence and the dependence on $\epsilon$ are optimal up to constants. The construction also gives a six-summand theorem for balanced sets and a second finite construction based on subgaussian tests.

25 pages, no figures. Substantially revised and expanded: the constructive result now holds for every exterior dilation greater than 1; added a nonsymmetric three-sum theorem, optimality results for the measure--dilation tradeoff, a constructive high-measure ellipsoid theorem, and further balanced-set and subgaussian consequences