A lower bound for the ratio of $2$- and $\infty$-norms within a linear subspace

Question

Let $M$ be a $k$-dimensional linear subspace of $\mathbb{R}^n$. Define its "distortion" (with respect to $2$- and $\infty$- norms) as $$d(M)=\sup_{x\in M\setminus \{0\}}\frac{\|x\|_2}{\|x\|_\infty} = \sup_{x\in M\setminus \{0\}}\frac{\sqrt{\sum x_i^2}}{\max|x_i|}$$

Is it true that $d(M)\ge \sqrt{k}$?

Partial results

• If the estimate is true, it's sharp because $d(M)= \sqrt{k}$ when $M$ is the span of the first $k$ coordinate axes
• $d(M) \ge \sqrt{2}$ when $M$ is two-dimensional. Indeed, we may assume that $M$ contains a nonzero vector $x$ with $\|x\|_\infty=|x_1|$. Being two-dimensional, it also contains a nonzero vector $y$ such that $y_1=0$. When moving along the line from $x$ to $y$, we encounter a vector $z$ where the 1st coordinate is tied with another one for the largest magnitude. Hence, $\|z\|_2\ge \sqrt{2}\|z\|_\infty$.

Motivation

A good lower bound on $M$ yields a good lower bound in Bounds on Hausdorff distance via singular values.

Answer 1

$\def\RR{\mathbb{R}}$ The bound is correct. Let $Q$ be the cube $[-1,1]^n$. So $V \cap Q$ is a bounded nonempty polytope and it must have a vertex, say $\vec{x} = (x_1, \ldots, x_n)$. After reordering the coordinates and negative signs as necessary, we may assume that $1 = x_1 = x_2 = \cdots = x_r > |x_{r+1}|$, $|x_{r+2}|$, ..., $|x_n|$.

We claim that $r \geq k$. If not, then there is a nonzero vector $\vec{u}$ in $V$ with $\vec{u}_1 = \vec{u}_2 = \cdots = \vec{u}_r=0$. For small enough $t$, both $\vec{x}+t \vec{u}$ and $\vec{x}-t \vec{u}$ would be in $Q \cap V$, contradicting that $\vec{x}$ is a vertex of the intersection.

Then $|\vec{x}|_{\infty}=1$ and $|\vec{x}|_2 \geq \sqrt{r} \geq \sqrt{k}$. $\square$.

Answer 2

I've given this problem some thought over the last couple of days and while this is not an answer, it looks 'promising' in a sense and maybe someone else can take it further. Let$$f(x)=\frac{{\lVert x \rVert}_2}{{\lVert x \rVert}_{\infty}}$$

Notice that for all $\alpha \in \mathbb{R}\setminus{\{0\}}$ and all $x \in M\setminus{\{0\}}$ we have $f(\alpha\cdot x)= f(x)$, so we might as well consider the supremum$$\sup_{\displaystyle x \in \mathbb{S}^{n-1}\cap M}\,\, f(x)$$

Now, on $\mathbb{S}^{n-1}$ we have that $f(x)$ reduces to$$\frac{1}{{\lVert x \rVert}_{\infty}}$$

Hence, we wish to prove that the infimum of $\big(\max_j |x_j|\big)$ subject to $\sum_i {x_i}^2=1$ on some $k$-dimensional subspace $M$ of $\mathbb{R}^n$ is $\frac{1}{\sqrt{k}}$ or less. Notice that because the infimum is taken over a compact set, it is actually a minimum. An equivalent

Prove or disprove: for each $k=1,\dots,n$ and each $k$-dimensional subspace of $\mathbb{R}^n$ it holds that$$\min\limits_{\substack{\displaystyle x \in M\\ \sum_{i=1}^n {x_i}^2=1}}\,\left( \max_{1\leq j \leq n} |x_j|\right)=\min\limits_{\substack{\displaystyle x \in M\\ {\lVert x \rVert}_2=1}} {\lVert x \rVert}_{\infty} \leq \frac{1}{\sqrt{k}}$$

Of course, one may consider a similar approach where instead of taking $\mathbb{S}^{n-1}$, we take the unit $(n-1)$-sphere with respect to the infinity norm; so basically the surface/boundary of the $n$-dimensional solid cube $C$. In this case, $f$ reduces to the $2$-norm and we get an analogous problems.