Prove that a sub-Gaussian random vector over a finite set $S \subset\mathbb R^n$ implies that $|S|$ is exponentially large Let $X$ be an isotropic random vector (i.e. $E[XX^T]=I_n$) and $X$ takes value in a finite set $S \subset\mathbb R^n$. If $X$ is a sub-Gaussian random vector and the norm $\|X\|_{\psi_2}\le C$ where $C$ is a constant, it will imply that $S$ is expoentially large with dimension $n$.
Note that $X$ is said to be sub-Gaussian with norm $K$ iff the marginal distribution in any direction is a sub-Gaussian with norm less or equal than $K$.
For example, if $X$ is uniformly distributed in $\{-1,+1\}^n$, then $X$ is a sub-Gaussian random vector with constant norm but now $|S|=2^n$. (It can be proved)
How can I prove the proposition? I just have no idea to deal with the "exponential" proof. Thank you!
 A: If $(Z_i)_{1 \leq i \leq N}$ are scalar random variables with $\|Z_i\|_{\Psi_2} \leq C$, then $\mathbf{E} \max Z_i \leq CC'\sqrt{\log N}$ by the usual union bound argument. 
Now let $X$ be an isotropic random vector in $\mathbf{R}^n$ such that $\|\langle X,\theta \rangle \|_{\Psi_2} \leq C $ for every unit vector $\theta$, and let $S$ be the support of $X$. Choose a number $A$ such that $S$ is contained in the ball of radius $A\sqrt{n}$. Since (denoting by $\|\cdot\|$ the Euclidean norm)
$$ ||X||^2 \leq \sup_{x \in S} |\langle X,x\rangle|, $$
it follows from the aforementioned estimate that
$$ n = \mathbf{E} ||X||^2 \leq A \sqrt{n} CC'\sqrt{\log |S|}.$$
In particular, we get $|S| \geq \exp(c(A,C) n)$.
We are going to reduce to the situation where $A$ is bounded. To that end, 
take an isotropic subgaussian random vector $X$ with $||\langle X,\theta \rangle||_{\Psi_2} \leq C$. This implies in particular $\mathbf{E} \langle X,\theta \rangle^4 \leq 4C^2$ (possibly change $4$ into another number depending on which definition of $\|\cdot\|_{\psi_2}$ you use). Define a new random vector as $Y = X {\bf 1}_{\{ ||X|| \leq 4C \sqrt{n}\} }$. The vector $Y$ is not exactly isotropic but satisfies $\frac 12 I_n \leq \mathbf{E} YY^T \leq I_n$. This is because (by Cauchy-Schwarz and Markov inequalities)
$$ \mathbf{E} \left[ \langle X,\theta \rangle^2 {\bf 1}_{\{||X|| > 4C \sqrt{n}\}} \right] \leq \left( \mathbf{E} \left[ \langle X,\theta \rangle^4 \right] \cdot \mathbf{P}(||X||^2 > 16C^2n)\right)^{1/2} \leq \sqrt{\frac{4C^2}{16C^2}} = \frac{1}{2}$$
We are now going to apply the first part of the argument to a linear image $\tilde{Y}$ of $Y$ which is isotropic. The random vector $\tilde{Y}$ is supported in the ball of radius $A\sqrt{n}$ for $A=8C$, and satisfies $\|\langle \tilde{Y},\theta \rangle \|_{\Psi_2} \leq 2C$, so the support of $Y$ (which is contained into $S \cup \{0\}$) contains at least $\exp(c(8C,2C)n)$ points.
A: This conjecture is false. Indeed, let, as in your example, $X$ be uniformly distributed on $\{-1,1\}^n$. Let $Y$ be a random vector uniformly distributed on the set $$S_Y:=\{\sqrt n\,e_1,-\sqrt n\,e_1,\dots,\sqrt n\,e_n,-\sqrt n\,e_n\},$$ where $(e_1,\dots,e_n)$ is the standard basis of $\mathbb R^n$. Then $EYY^T=I_n=EXX^T$. Also, $\|Y\|=\sqrt n=\|X\|$, where $\|\cdot\|$ is the Euclidean norm, so that $Y$ is sub-Gaussian in exactly the same sense as $X$ is. However, $|S_Y|=2n=o(e^{an})$ as $n\to\infty$ for any constant $a>0$.    
