Proportion of vertices of a hypercube lying inside an ellipsoid

95 Views Asked by At

Let $E$ be a closed ellipsoid in $\mathbb{R}^n$ with semiaxes of length $r_1,\dots,r_n \in [1,\infty]$ and assume that $\sum_{k=1}^n \frac{1}{r_k^2} = 1$. Does there exist an absolute constant $\rho>0$ (not depending on $n$ or the ellipsoid) such that at least $\rho 2^n$ of the vertices $(\pm 1, \dots \pm 1)$ of the $n$-dimensional hypercube lie in $E$?

An alternative way of stating the question is as follows: Let $Y$ be a random vector distributed uniformly on the hypercube vertices. Does there exists $\rho > 0$ such that $\mathbb{P}(Y^T Q Y \le \mathrm{Tr}\,Q) \ge \rho$ for any positive semi-definite matrix $Q$? (Here one can check that $\mathrm{Tr}\,Q = \mathbb{E} Y^T Q Y$.)

One can for instance check that if you let $Q$ to be the graph Laplacian matrix of a clique, i.e. the diagonal elements of $Q$ are $n-1$ and the off-diagonal ones are $-1$, then as $n \to \infty$ the probability approaches $\mathbb{P}(|N(0,1)| \ge 1) \approx 0.3173\dots$. The same matrix in dimension $6$ gives the upper bound $\rho \le 0.21875$, but I don't know how far from the optimal these results are.