On creating convexity in high dimensions

Abstract

Given a subset $A$ of ${\mathbb{R}}^n$, we define \begin{align*} \mathrm{conv}_k(A) := \left\{ λ_1 s_1 + \cdots + λ_k s_k : λ_i \in [0,1], \sum_{i=1}^k λ_i = 1 , s_i \in A \right\} \end{align*} to be the set of vectors in ${\mathbb{R}}^n$ that can be written as a $k$-fold convex combination of vectors in $A$. Let ${\hat{I}}_n^3$ denote the standard Gaussian measure on ${\mathbb{R}}^n$. We show that for every $\epsilon >0$, there exists a subset $A$ of ${\mathbb{R}}^n$ with Gaussian measure ${\hat{I}}_n^3(A)\ge 1-\epsilon$ such that for all $k=O_{\epsilon }(\sqrt{\log \log (n)})$, ${\mathrm{conv}}_k(A)$ contains no convex set $K$ of Gaussian measure ${\hat{I}}_n^3(K)\ge \epsilon$. This result acts as a complement to the recent affirmative resolution of Talagrand's convexity conjecture by Hua, Song, and Tudose, which states that a universal dilation of the threefold Minkowski sum $A+A+A$ of a large set $A$ guarantees a large convex subset. Our approach utilises concentration properties of random copulas and the application of optimal transport techniques to the empirical coordinate measures of vectors in high dimensions.

30 pages, revised following the recent resolution of Talagrand's convexity conjecture by Hua, Song and Tudose