# Thin large subspaces of $\ell^N_1$

Consider a sequence $V_N$ of subspaces of $\ell^N_1$ so that $\dim V_N = N- n$ and $n$ is $\mathsf{o}(N)$. Is it true that these spaces are "thick" (unofficial terminology), i.e. are there constants $K_1,K_2>0$ so that for $N$ large enough, $$\sup_{x \in V, \|x\|_1 \leq K_1} \|x\|_\infty \geq K_2$$ where $\|x\|_\infty$ is (as usual) the supremum of the coordinates of $x$.

A relaxation (or equivalent formulation?) of the above: is there a sequence $x_i \in V_i \subset \ell_1^i \subset \ell_1\mathbb{N}$ which is convergent in the weak$^*$ topology of $\ell_1 \mathbb{N}$ to something else than $0$?

In the $\ell_2$ case, the answer is "overwhelmingly positive". Let $\lbrace e_i\rbrace_{i=1}^N$ be the "standard" basis of $\ell^N_1$. Consider $P_{V_N}$ to be the orthogonal projection on $V_N$, then $$N-n = \dim V_N = \sum_{i=1}^N \langle P_{V_N} e_i \mid e_i \rangle$$ So that, in fact, there are at least $N-2n$ coordinates $i$ so that $\langle P_V e_i \mid e_i \rangle \geq \frac{1}{2}$ and $\langle P_{V_N} e_i \mid e_i \rangle = \| P_{V_N} e_i\|_2^2 \leq 1$.

Improved version of my answer. The following version of Kashin's (1977) result is needed here: For any $\alpha\in(0,1)$ there exists $C=C(\alpha)$ such that for any $N$ there is an $\lceil\alpha N\rceil$-dimensional subspace $L$ of $\ell^N_1$ satisfying $$\forall x\in L\quad \frac1{\sqrt{N}}||x||_1\le||x||_2\le\frac{C}{\sqrt{N}}||x||_1$$ (see e.g. Section 1.10.3 in Brazitikos, Giannopoulos, Valettas, Vritsiou, Geometry of isotropic convex bodies. American Mathematical Society, Providence, RI, 2014).

This can be used to show that there is a sequence $(N(i))$ tending to $\infty$ and subspaces $V_{N(i)}$ of $\ell_1^{N(i)}$ so that dim$V_{N(i)}/N(i)\ge(1-\frac1i)$ and

$$\sup_{x \in V_{N(i)}, \|x\|_1 \leq 1} \|x\|_2 \le\frac1i.$$

Since $\|x\|_\infty\le ||x||_2$ this implies that the answer to the first question is `No'.

We apply Kashin's theorem with $\alpha=1-\frac1i$, let $C$ be the corresponding constant. We pick $N(i)$ so large that $N(i)>i$ and $$\frac{C}{\sqrt{N(i)}}\le\frac 1i.$$ Let $V_{N(i)}$ be the subspace $L$ of the Kashin's theorem corresponding to this situation. It is easy to check that all of the conditions above are satisfied.

• I did not think in such terms. I meant: suppose you want to show that for sufficiently large N you can pick $n=0.0001N$ such that the supremum is $<0.001$. You look at the distance-to-Euclidean constant $C$ in Kashin section of dimension $0.9999N$ and pick $N$ so large that $\sqrt{N}$ kills it (as needed). – Mikhail Ostrovskii Nov 20 '15 at 16:56
• @Antoine The version of the Kashin's result needed here is: For any $\alpha\in(0,1)$ there exists $C=C(\alpha)$ such that for any $N$ there is an $[\alpha N]$-dimensional subspace $L$ of $\ell_1^N$ satisfying $$\forall x\in L\quad \frac1{\sqrt{N}}||x||_1\le||x||_2\le \frac{C}{\sqrt{N}}||x||_1.$$ – Mikhail Ostrovskii Nov 21 '15 at 16:25
• @Antoine I assume that you want to show that for each $\varepsilon>0$ and $\delta>0$ you can find an arbitrarily large $N$ and a subspace $V_N\subset\ell_1^N$ such that dim$(V_N)\ge (1-\varepsilon)N$ and $\sup\{||x||_\infty: x\in V_N, ||x||_1\le 1\}<\delta$. I believe that you can do this using my second and my last comments, as well as the fact that for vectors with nontrivial $||\cdot||_\infty$-norm, $\ell_1$ and $\ell_2$ norms are close to each other. – Mikhail Ostrovskii Nov 21 '15 at 19:28
• OK, it shows that the answer to the question in your first paragraph is "No". It seems that you meant something else. – Mikhail Ostrovskii Nov 21 '15 at 21:09
• @Antoine See my improved answer. – Mikhail Ostrovskii Nov 22 '15 at 0:56

I discussed this question with Pisier over lunch. He later called my attention to the paper

[GG] Garnaev, A. Yu.; Gluskin, E. D.; The widths of a Euclidean ball. (Russian) Dokl. Akad. Nauk 277 (1984), 1048–1052.

Pisier emailed me,

“They get an equivalent of the relevant Kolmogorov numbers of inclusion of $n$-dim Euclidean space into $\ell_\infty^n$.

It says (from my book on the volume p. 81 but there is a misprint- I checked it must be $+1/2$ in the exponent of the log not $-1/2$): $L_1^N$ contains a subspace of codimension $N-n$ with Banach-Mazur distance to Hilbert at most

$$\min \{ \sqrt{N}, (N/n)^{1/2} [\log (1+ N/n)] ^{1/2}\ ”$$

Thus the OP’s question has a negative answer if $n^{-1}\log (1+ N/n)$ tends to zero; i.e., if $n^{-1}\log N \to 0$. What if $n\to \infty$ slower than $\log N$?

Take an $n$ codimensional subspace $V_N$ of $\ell_1^N$. Take an Auerbach basis $y_1,\dots, y_n$ for $V_N^\perp \subset \ell_\infty^N$. Let $1/\epsilon$ be a positive integer; something like $\epsilon = 1/10$ is OK. Tile $[-1, 1]^n$ with boxes of side length $\epsilon/n$; the number of boxes is around $(2n\epsilon/n)^n$. Consequently, if $N> (2n\epsilon)^n$, there exist $1\le i < j \le N$ s.t. $(\langle y_k, e_i \rangle)_{k=1}^n$ and $(\langle y_k, e_j \rangle)_{k=1}^n$ lie in the same box. Since $y_1,\dots, y_n$ is Auerbach, this means that $|\langle y, e_i -e_j\rangle| < \epsilon$ for all norm one $y \in V_N^\perp$. That is, the distance of $e_i -e_j$ to $V_N$ is less than $\epsilon$. Since $\|e_i -e_j\|_1 = 2$ and $\|e_i -e_j\|_\infty =1$, this gives a positive answer to the OP’s question if $N > (2n\epsilon)^n$ for infinitely many $N$; i.e., if $n\log n < \delta \log N$ for a computable $\delta$.

I don’t know where the break point occurs.

By Kashin's theorem you can decompose $\ell_1^{2n}$ into two orthogonal subspaces each of dimension $n$ so that you have $\|x\|_1$ is about $\sqrt{n}\|x\|_2$ for all $x$ in each of these subspaces. So by a trivial estimate between $\|x\|_2$ and $\|x\|_{\infty}$ norms you get $\|x\|_{\infty}$ less than in the order of $1/\sqrt{n}$.

• I'm not sure I understand: I meant n is small o of N, i.e. $n/N \to 0$. But your two subspaces have half the dimension. – ARG Nov 20 '15 at 16:38