8
$\begingroup$

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$.

$\endgroup$

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
13
  • 2
    $\begingroup$ 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). $\endgroup$ Nov 20, 2015 at 16:56
  • 1
    $\begingroup$ @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.$$ $\endgroup$ Nov 21, 2015 at 16:25
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 21, 2015 at 19:28
  • 1
    $\begingroup$ OK, it shows that the answer to the question in your first paragraph is "No". It seems that you meant something else. $\endgroup$ Nov 21, 2015 at 21:09
  • 2
    $\begingroup$ @Antoine See my improved answer. $\endgroup$ Nov 22, 2015 at 0:56
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – ARG
    Nov 20, 2015 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.