# inequality between norms of vector

Let $a=(a_1, \ldots, a_n)$ be a vector in $R^n$. It is known that $\|a\|_{\infty}\leq \|a\|_2\leq \sqrt n\|a\|_{\infty}$.

Let $k<<n$. For which kind of vectors the following would be true: $$\sqrt{k}\|a\|_{\infty}\leq \|a\|_2?$$ Thank you.

-
Basically any vector where each entry is roughly the same. –  Alex Becker Sep 9 '12 at 1:37

Equivalently, we can look for vectors with $\|a\|_\infty/\|a\|_2\leq 1/\sqrt k$. Start by considering vectors with $a_i\geq 0$ for all $i$ and $\|a_2\|=1$. The set of such vectors is $[0,1/\sqrt{k}]^n\cap S^{n-1}$, which is a simply connected semialgebraic set. Allowing the sign of each component to be positive or negative gives us a union $X$ of $2^n$ reflected copies of this set. Depending on $k$ and $n$ the resulting set is either (non-simply) connected or has $2^n$ disconnected components. Allowing scaling gives $X\times (0,\infty)$. This accounts for all solutions except the lone trivial solution $a=0$.
Thank you. Just wanted to make sure, by $a=0$, did you mean a zero vector? –  Nick G.H. Sep 11 '12 at 2:45