# A counterexample to a strengthening of a question of Milman

Timothy Gowers, Katarzyna Wyczesany

► To cite this version:

Timothy Gowers, Katarzyna Wyczesany. A counterexample to a strengthening of a question of Milman. 2021. hal-05306542

HAL Id: hal-05306542

https://college-de-france.hal.science/hal-05306542v1

Preprint submitted on 9 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A counterexample to a strengthening of a question of Milman

W. T. Gowers and K. B. Wyczesany

## Abstract

Let $| \cdot |$ be the standard Euclidean norm on $\mathbb{R}^n$ and let $X = (\mathbb{R}^n, \| \cdot \|)$ be a normed space. A subspace $Y \subset X$ is *strongly $\alpha$-Euclidean* if there is a constant $t$ such that $t|y| \le \|y\| \le \alpha t|y|$ for every $y \in Y$, and say that it is *strongly $\alpha$-complemented* if $\|P_Y\| \le \alpha$, where $P_Y$ is the orthogonal projection from $X$ to $Y$ and $\|P_Y\|$ denotes the operator norm of $P_Y$ with respect to the norm on $X$. We give an example of a normed space $X$ of arbitrarily high dimension that is strongly 2-Euclidean but contains no 2-dimensional subspace that is both strongly $(1 + \epsilon)$-Euclidean and strongly $(1 + \epsilon)$-complemented, where $\epsilon > 0$ is an absolute constant. This example is closely related to an old question of Vitali Milman.

## 1 Introduction

A famous theorem of Dvoretzky [1] asserts that for every positive integer $k$ and every $\epsilon > 0$ there exists a positive integer $n$ such that every normed space of dimension at least $n$ has a subspace $Y$ of dimension $k$ such that $d(Y, \ell_2^k) \le 1 + \epsilon$, where $d$ is the Banach-Mazur distance. A highly influential second proof of Dvoretzky's theorem was given by Milman [2], which exploited measure concentration and led to many other arguments based on the same fundamental idea.

Let us call an $n$-dimensional normed space $X$ *C-Euclidean* if $d(X, \ell_2^n) \le C$. A fairly straightforward use of Milman's method yields the following statement.

**Theorem 1.1.** For every $C > 1$ and every $\epsilon > 0$ there exists $c > 0$ such that for every $n \in \mathbb{N}$, every $n$-dimensional C-Euclidean normed space $X$ has a subspace $Y$ of dimension at least $cn$ that is $(1 + \epsilon)$-Euclidean.

In other words, under the additional hypothesis that $X$ is C-Euclidean (and in fact under much weaker assumptions than this), one can obtain a linear dependence between the dimension of $Y$ and the dimension of $X$.
There is a large literature on finding 'nice' subspaces of normed spaces under various conditions, but most of this literature pays little attention to how those subspaces sit in the main space. In particular, a desirable property for a subspace $Y \subset X$ is that it should be *complemented*. In an infinite-dimensional context, one says that $Y$ is complemented if $Y = PX$ for a continuous projection $P$ on $X$. In a finite-dimensional context, we need a more quantitative definition: $Y$ is said to be $\alpha$-complemented if $Y = PX$ for a projection $P$ of operator norm at most $\alpha$.

There are several open problems about the existence of complemented subspaces. For example, it is not known whether there is a constant $C$ such that for every $k$ there exists $n_0$ such that for every $n \ge n_0$, every $n$-dimensional normed space has a $C$-complemented subspace of dimension at least $k$ and codimension at least $k$. (For a partial result in this direction, see [3].)

In this paper we consider the following question of Milman.

**Question 1.2.** Let $k \in \mathbb{N}$, let $C \in \mathbb{R}$, and let $\epsilon > 0$. Does there exist $n \in \mathbb{N}$ such that every C-Euclidean normed space $X$ of dimension at least $n$ has a $k$-dimensional subspace $Y$ that is $(1+\epsilon)$-Euclidean and $(1+\epsilon)$-complemented?

We do not answer the question, but we give a negative answer to a question that is sufficiently close to Milman's to suggest very strongly that Milman's question has a negative answer.

To describe our result, we introduce two further definitions. We shall write $|\cdot|$ for the standard Euclidean norm on $\mathbb{R}^n$. Let us call a normed space $X = (\mathbb{R}^n, \|\cdot\|)$ strongly $\alpha$-Euclidean if there is a constant $t$ such that $t|x| \le \|x\| \le \alpha t|x|$ for every $x \in X$, and let us call a subspace $Y$ of $X$ strongly $\alpha$-complemented if the orthogonal projection $P_Y$ from $X$ to $Y$ has operator norm at most $\alpha$ (with respect to the norm $\|\cdot\|$ on $X$). The first definition is stronger than merely being $\alpha$-Euclidean, because instead of asking for any linear map $T$ such that $|Tx| \le \|x\| \le \alpha|Tx|$, we ask for $T$ to be a multiple of the identity, and the second is stronger than merely being $\alpha$-complemented because we ask for the projection to be orthogonal with respect to the standard inner product on $\mathbb{R}^n$.

These are natural strengthenings to consider, in the light of the fact that Milman's proof of Theorem 1.1 begins by observing that without loss of generality $X$ is strongly $C$-Euclidean and then proceeds to find a strongly $(1+\epsilon)$-Euclidean subspace. Thus, one would expect Question 1.2 to have a positive answer if and only if the following question also has a positive answer.

**Question 1.3.** Let $k \in \mathbb{N}$, let $C \in \mathbb{R}$, and let $\epsilon > 0$. Does there exist $n \in \mathbb{N}$ such that every strongly $C$-Euclidean normed space $X$ of dimension at least $n$ has a $k$-dimensional subspace $Y$ that is strongly $(1+\epsilon)$-Euclidean and strongly $(1+\epsilon)$-complemented?

Our main theorem is an example that shows that the answer to Question 1.3 is negative.

**Theorem 1.4.** There exist constants $\epsilon > 0$ and $C \in \mathbb{R}$ such that for all sufficiently large $n \in \mathbb{N}$ there is an $n$-dimensional normed space that is $C$-Euclidean but contains no 2-dimensional subspace that is both strongly $(1+\epsilon)$-Euclidean and strongly $(1+\epsilon)$-complemented.
The rest of the paper is devoted to the proof, apart from a few remarks in the concluding section.

## 2 Good vectors

We start with a definition that allows us to reformulate in a convenient way the condition that $Y$ is strongly $(1 + \epsilon)$-Euclidean and strongly $(1 + \epsilon)$-complemented.

We write $\langle \cdot, \cdot \rangle$ for the standard inner product.

**Definition 2.1.** Let $X = (\mathbb{R}^n, \| \cdot \|)$ be a normed space and let $x \in X$. We say that $x$ is $\epsilon$-good if

$$ \langle x, y \rangle \le (1 + \epsilon) \frac{\|y\|}{\|x\|} |x|^2, $$

for every vector $y \in \mathbb{R}^n$.

To see what this means geometrically, consider the orthogonal projection $P_x$ on to the 1-dimensional subspace of $\mathbb{R}^n$ generated by $x$. Writing $x'$ for the normalized vector $x/|x|$, this has the formula

$$ P_x y = \langle x', y \rangle x'. $$

Hence, the operator norm of $P_x$ (as a map from $X$ to $X$) is the maximum of the quantity

$$ \frac{\langle x', y \rangle \|x'\|}{\|y\|} = \frac{\langle x, y \rangle \|x\|}{|x|^2 \|y\|} $$

over all non-zero $y \in \mathbb{R}^n$. It follows that $x$ is $\epsilon$-good if and only if $P_x$ has operator norm at most $1 + \epsilon$. Since the definition of an $\epsilon$-good point $x$ does not depend on the norm of $x$, it is enough to consider unit vectors. Let us write $S^n = \{x \in \mathbb{R}^{n+1} : |x| = 1\}$.

We now show that a subspace $Y$ of a space $X$ is strongly $(1 + \epsilon)$-Euclidean and strongly $(1 + \epsilon)$-complemented for some small $\epsilon$ if and only if every $y \in Y$ is $\delta$-good for some small $\delta$.

**Lemma 2.2.** Let $X = (\mathbb{R}^n, \| \cdot \|)$ be a normed space and let $Y \subset X$ be a subspace.

1. If $Y$ is strongly $(1 + \epsilon)$-complemented and strongly $(1 + \epsilon)$-Euclidean, then every $y \in Y$ is $(2\epsilon + \epsilon^2)$-good.

2. If $\epsilon \le 1/9\pi^2$ and every point in $Y$ is $\epsilon$-good, then $Y$ is strongly $(1 + \epsilon)$-complemented and strongly $(1 + 3\pi \sqrt{\epsilon})$-Euclidean.

Before we prove the statement, note that this characterization reduces Question 1.3 to the following question.
**Question 2.3.** Let $\epsilon > 0$, $C \ge 1$ and $k \in \mathbb{N}$. Does there exist $n$ such that if $\|\cdot\|$ is a norm on $\mathbb{R}^n$ such that $|x| \le \|x\| \le C|x|$ for every $x \in \mathbb{R}^n$, then the space $(\mathbb{R}^n, \|\cdot\|)$ has a subspace $Y$ of dimension $k$ such that every $y \in Y$ is $\epsilon$-good?

**Proof of Lemma 2.2.** Let $P_Y$ be the orthogonal projection onto $Y$. If $Y$ is strongly $(1+\epsilon)$-Euclidean and strongly $(1+\epsilon)$-complemented, then $\|P_Y x\| \le (1+\epsilon)\|x\|$ for every $x \in X$ and there exists $\lambda \in \mathbb{R}$ such that $\lambda|y| \le \|y\| \le (1+\epsilon)\lambda|y|$ for every $y \in Y$. From this it follows that for every $y \in Y$ and every $x \in X$ we have

$$ \langle y, x \rangle = \langle y, P_Y x \rangle \le |y| |P_Y x| \le |y| \frac{1}{\lambda} \|P_Y x\| \le (1+\epsilon)\lambda \frac{|y|^2}{\|y\|} \frac{1}{\lambda} (1+\epsilon)\|x\| = (1+\epsilon)^2 \frac{\|x\|}{\|y\|} |y|^2, $$

which implies that every point $y$ in $Y$ is $(2\epsilon + \epsilon^2)$-good, as claimed.

Conversely, assume that every point in $Y$ is $\epsilon$-good, so that for every $y \in Y$ and every $x \in X$ we have the inequality

$$ \langle y, x \rangle \le (1 + \epsilon) \frac{\|x\|}{\|y\|} |y|^2. $$

Choose $x \in X$. Then $P_Y x \in Y$, so

$$ |P_Y x|^2 = \langle P_Y x, P_Y x \rangle = \langle P_Y x, x \rangle \le (1 + \epsilon) \frac{\|x\|}{\|P_Y x\|} |P_Y x|^2, $$

and therefore $\|P_Y x\| \le (1 + \epsilon)\|x\|$. It follows that $Y$ is strongly $(1+\epsilon)$-complemented.

Now assume for a contradiction that the subspace $Y$ is not strongly $(1+a)$-Euclidean with $0 < a$. In particular, this means that we can find two unit vectors $y, w \in Y$ such that $\|y\| = \|w\|(1+a)$. Without loss of generality we may assume that $a \le 1/2$.

Let us consider a sequence of unit vectors $w = x_0, x_1, \dots, x_{m-1}, x_m = y$ that are equally spaced along the shortest arc that joins $w$ to $y$ (which is unique, since $w$ cannot equal $-y$). By the pigeon-hole principle there exists $i$ such that

$$ \|x_i\|(1 + a)^{1/m} \le \|x_{i+1}\|. $$

We shall choose $m$ to ensure that $x_i$ is a witness for $x_{i+1}$ not being $\epsilon$-good. Indeed, if we assume that $m$ is at least $3\pi^2/a$ then since the angle between $x_i$ and $x_{i+1}$ is at most $\pi/m$ we get that

$$ \begin{aligned} \langle x_{i+1}, x_i \rangle \frac{\|x_{i+1}\|}{\|x_i\| |x_{i+1}|^2} &\ge \cos(\angle x_i x_{i+1}) (1 + a)^{1/m} \ge (1 - \frac{\pi^2}{2m^2}) (1 + \frac{a}{m} - \frac{a^2}{2m}) \\ &\ge 1 + \frac{a}{m} - \frac{a^2 m^2 + \pi^2 m + \pi^2 a}{2m^3} \ge 1 + \frac{a}{2m}. \end{aligned} $$

Here we used the fact that for $0 < \gamma < 1$ and $a > 0$ we have that $(1+a)^\gamma \ge 1 + \gamma a - \frac{\gamma(1-\gamma)}{2}a^2 \ge
$1 + \gamma a - \frac{\gamma a^2}{2}$, and the assumptions that $0 < a \le 1/2$ and $m \ge 3\pi^2/a$.

It follows that the point $x_{i+1}$ is not $\frac{a}{2m}$-good. Therefore, if every point is $\epsilon$-good, we must have that $\frac{a}{|6\pi^2/a|} \le \epsilon$, which implies that $a \le 3\pi\sqrt{\epsilon}$. Thus, we find that $Y$ is strongly $(1 + 3\pi\sqrt{\epsilon})$-Euclidean, which completes the proof. $\square$

Next, we give an equivalent condition for a point to be $\epsilon$-good for some small $\epsilon$. Before we state the result, let us recall that a support functional of a norm $\|\cdot\|$ at $x$ is any non-zero linear functional $f$ such that for every $y$ with $\|y\| \le \|x\|$ we have $f(y) \le f(x)$. Note that if the norm is differentiable, then writing $f(x)$ for $\|x\|$, we have that any multiple of $f'(x)$ is a support functional at $x$.

In the next proposition, we shall use the standard identification of $\mathbb{R}^n$ with its dual. That is, we identify a vector $z$ with the linear functional $y \mapsto \langle y, z \rangle$.

**Proposition 2.4.** Let $(X, \|\cdot\|)$ be a normed space and suppose that $|x| \le \|x\| \le C|x|$ for every $x \in X$. For every $\delta > 0$ there exists $\epsilon > 0$ such that if $x \in X$ is any $\epsilon$-good point, then there exist $y, z$ such that $|x| = |y|$, $|x - y| < \delta|x|$, $z$ is a support functional for $y$, and $|y - z| < \delta|x|$. Conversely, for every $\epsilon > 0$ there exists $\delta > 0$ such that $x$ is an $\epsilon$-good point if there exist $y, z$ such that $|x - y| < \delta|x|$, $z$ is a support functional for $y$, and $|y - z| < \delta|x|$.

*Proof.* We shall do the second part first. Let $0 < \epsilon \le 1$ and suppose that there exist $y, z$ such that $z$ is a support functional for $y$, and $|y - x|$ and $|z - y|$ are both at most $\delta|x|$.

Now let $w \in X$. Then

$$ \langle w, x \rangle = \langle w, z \rangle + \langle w, y - z \rangle + \langle w, x - y \rangle \le \langle w, z \rangle + 2\delta|w||x|. $$

But $z$ is a support functional for $y$, so

$$ \langle w, z \rangle \le \|w\| \|z\|^* = \|w\| \frac{\langle y, z \rangle}{\|y\|} $$

We also have that

$$ \|y\| \ge \|x\| - C|x - y| \ge \|x\| - C\delta|x| \ge (1 - C\delta)\|x\|. $$

Finally, since $|x - z| \le 2\delta|x|$ we have that $|z| \le (1 + 2\delta)|x|$, so

$$ \langle y, z \rangle = \langle x, z \rangle + \langle y - x, z \rangle \le |x||z| + \delta|x||z| \le (1 + \delta)(1 + 2\delta)|x|^2. $$

Putting all this together, we find that

$$ \langle w, x \rangle \le \frac{(1 + \delta)(1 + 2\delta)}{1 - C\delta} \frac{\|w\|}{\|x\|} |x|^2 + 2\delta|w||x| \le \left( \frac{(1 + \delta)(1 + 2\delta)}{1 - C\delta} + 2C\delta \right) \frac{\|w\|}{\|x\|} |x|^2. $$
It can be checked that if we set $\delta = \epsilon/5C$, then the factor in brackets is at most $1 + \epsilon$.

For the other direction, assume that for all $y$ such that $|y| = |x|$ and $|x - y| < \delta|x|$ we have that $|y - z| > \delta|x|$, where $z$ is the support functional at $y$, chosen such that $|z| = |y|$.

We can assume that $|x| = 1$ and that for every unit vector $y$ with $|y - x| < \delta$, we have that $|y - z| \ge \delta$. It follows that

$$ \langle y, z \rangle = 1 - |y - z|^2 / 2 \le 1 - \delta^2 / 2 $$

and therefore that

$$ |z - \langle y, z \rangle y|^2 = 1 - \langle y, z \rangle^2 \ge \delta^2 - \delta^4 / 4, $$

which implies that the component of $z$ orthogonal to $y$ has size at least $\sqrt{3}\delta/2 \ge \delta/2$.

It follows that for any $\gamma < \delta$ we can find a path on the unit sphere that starts at $x$ and ends at a point at distance at least $\gamma$ from $x$ such that the norm $\| \cdot \|$ decreases at a rate of at least $\delta/2$ along the path. This gives us a unit vector $\bar{y}$ such that $|\bar{y} - x| \le \gamma$ and

$$ \|\bar{y}\| \le \|x\| - \gamma\delta/2 \le \|x\|(1 - \gamma\delta/2C). $$

It follows that $\langle x, \bar{y} \rangle > 1 - \gamma^2/2$, so

$$ \langle x, \bar{y} \rangle > \frac{(1 - \gamma^2/2)}{(1 - \gamma\delta/2C)} \frac{\|\bar{y}\|}{\|x\|} |x|^2. $$

Setting $\gamma = \delta/2C$, we deduce that $x$ is not $\delta^2/8C^2$-good. $\square$

# 3 Definition of the norm and an important observation

The norm has a fairly simple definition. Let $P$ be a random orthogonal projection of rank $n/2$ and let $A = I + P$. Then we define

$$ \|x\| = \langle x, Ax \rangle^{1/2} + \eta n^{-1/2} \|x\|_1, \quad (1) $$

where $\eta > 0$ is an absolute constant to be chosen later. (Note that $|x| \le \|x\| \le (\sqrt{2} + \eta)|x|$, so as long as $\eta \le 2 - \sqrt{2}$, this norm is strongly 2-Euclidean.) The first part of this norm is a weighted $\ell_2$ norm with respect to a random orthonormal basis, where half the weights are 2 and half are 1, and the second is a multiple of the standard $\ell_1$ norm. Our aim now is to prove that with probability greater than zero (and in fact close to 1) there is no 2D subspace that consists entirely of $\epsilon$-good points, for some absolute constant $\epsilon > 0$. That is, we will prove Theorem 1.4 and therefore give a negative answer to Question 1.3.

The next lemma tells us what the support functionals are at a vector $x$. Let us use the notation
sign(t) for the multivalued function from $\mathbb{R}$ to $\mathbb{R}$ that takes $t$ to 1 if $t > 0$, to -1 if $t < 0$, and to any element of $[-1, 1]$ if $t = 0$. Then if $x \in \mathbb{R}^n$ we write sign($x$) for the result of applying the multivalued function sign pointwise. Let us also write $||x||_A$ for $\langle x, Ax \rangle^{1/2}$.

**Lemma 3.1.** The support functionals at $x$ are multiples of $\frac{Ax}{||x||_A} + \eta n^{-1/2} \text{sign}(x)$.

*Proof.* Essentially this is just a question of calculating the derivative of the norm, except that where the derivative is not defined we may have to give it several values (just as one might say that the derivative of $|x|$ at zero is any element of $[-1, 1]$).

Let $y$ be a sufficiently small vector. Then for any possible choice of sign($x$), we have that

$$ \|x + y\| \ge \|x\| + \frac{\langle Ax, y \rangle}{\|x\|_A} + \eta n^{-1/2} \langle \text{sign}(x), y \rangle + o(y). $$

Therefore, if $y$ is orthogonal to some value of $\frac{Ax}{||x||_A} + \eta n^{-1/2} \text{sign}(x)$, we have that $\|x+y\| \ge \|x\| + o(y)$, from which it follows easily that $\frac{Ax}{||x||_A} + \eta n^{-1/2} \text{sign}(x)$ is a support functional at $x$. $\square$

**Corollary 3.2.** Let $Q$ be such that $P+Q=I$, let $\epsilon$ be sufficiently small and let $Y$ be a 2-dimensional subspace that consists entirely of $\epsilon$-good points. Then for every unit vector $x \in Y$ there exists a unit vector $y$ with $|x-y| \le \delta$ and a value of sign($y$) such that

$$ d(\eta n^{-1/2} \text{sign}(y), PY + QY) \le \delta, $$

where $\delta$ tends to zero with $\epsilon$.

*Proof.* By Lemma 3.1 and Proposition 2.4 we find that if a unit vector $x$ is $\epsilon$-good, then there exists a unit vector $y$, a value of sign($y$), and a scalar $\mu$ such that $|y - x| < \delta$ and

$$ |\mu(\frac{Ay}{\|y\|_A} + \eta n^{-1/2} \text{sign}(y)) - y| < \delta/3, $$

where $\delta > 0$ tends to zero with $\epsilon$. Since $|Ay| \le \sqrt{2}\|y\|_A$ and $n^{-1/2}|\text{sign}(y)| \le 1$, our assumption that $\sqrt{2} + \eta \le 2$ implies that $\mu \ge (1 - \delta/3)/2$. For sufficiently small $\epsilon$, we therefore have that $\mu \ge 1/3$.

Recalling that $A = I + P$ and rearranging, we obtain the inequality

$$ (\frac{1}{\mu} - \frac{2}{\|y\|_A})Py + (\frac{1}{\mu} - \frac{1}{\|y\|_A})Qy \approx_{\delta} \eta n^{-1/2} \text{sign}(y), $$

where we write $u \approx_{\delta} v$ to mean that $|u - v| \le \delta$. (We shall use this convenient notation throughout the rest of this paper.) $\square$

**Corollary 3.2** tells us that if we have a 2-dimensional subspace $Y$ that consists entirely of $\epsilon$-good points, then every unit vector $x \in Y$ is close to a vector $y$ such that sign($y$) is close to the
subspace $PY + QY$, which has dimension at most 4. This is the main observation we shall use to obtain a contradiction.

# 4 Outline of the proof and some technical lemmas

Let us call a non-zero vector a *sign vector* if all its coordinates have the same absolute value. As before, we write $X$ for $(\mathbb{R}^n, ||\cdot||)$, though sometimes we abuse notation and use $X$ to refer simply to the vector space $\mathbb{R}^n$.

In order to show that the norm defined in (1) indeed constitutes a counterexample to Question 1.3, that is, that there is no two-dimensional subspace of $(\mathbb{R}^n, ||\cdot||)$ that consists entirely of $\epsilon$-good points, we shall obtain a contradiction using more precise versions of the following statements.

1. Every $\epsilon$-good point is close to $PX$ or $QX$.

2. With high probability, no point that is close to $PX$ or $QX$ can be approximated by a point with only a few distinct coordinates.

3. If $Y$ is a 2-dimensional subspace that consists entirely of $\epsilon$-good points, then for every $x \in Y$ there exists $x'$ close to $x$ such that $\text{sign}(x')$ is close to the subspace $PY + QY$.

4. Using the first two statements, we deduce that the vectors $\text{sign}(x')$ are not approximately contained in a 4-dimensional subspace.

**Corollary 3.2** is our precise version of Statement 3. Let us now prove Statement 1, which is also fairly simple.

**Lemma 4.1.** Let $x$ be an $\epsilon$-good vector in $(X, ||\cdot||)$, such that $|x| = 1$. Then either $d(x, PX) \le 3\delta + 2\eta$ or $d(x, QX) \le 3\delta + 2\eta$, where $\delta$ is given by Proposition 2.4.

*Proof.* From the beginning of the proof of Corollary 3.2 we obtain a unit vector $y$ such that $|x-y| \le \delta$ and such that

$$ \frac{Ay}{||y||_A} + \eta n^{-1/2} \text{sign}(y) \approx_{\delta} \lambda y, $$

where we have written $\lambda$ for $1/\mu$ and used the fact that $\mu \ge 1/3$.

We have that

$$ d(x, PX) \le d(x, y) + d(y, PX) \le \delta + |y - Py| = \delta + |Qy| $$

and similarly for $d(x, QX)$. Hence, our goal is to bound $\min\{|Py|, |Qy|\}$.

But $|Ay| \ge ||y||_A$, and $\eta n^{-1/2}|\text{sign}(y)| \le \eta$, so $\lambda \ge 1 - \eta - \delta$ and

$$ |Ay - \lambda||y||_Ay| < (\delta + \eta)||y||_A \le \sqrt{2}(\delta + \eta). $$
Thus, $y$ is an approximate eigenvector of $A$ and it remains to prove that an approximate eigenvector of $A$ must be close to an eigenvector. (This is of course false for general linear maps.)

Since $P + Q = I$, we have $y = Py + Qy$ and $Ay = 2Py + Qy$, so if $v$ is any scalar, then

$$|Ay - vy|^2 = (2 - v)^2 |Py|^2 + (1 - v)^2 |Qy|^2.$$

Writing $2 - v = a + 1/2$ and $1 - v = a - 1/2$, one can rewrite the right-hand side as

$$(a + \frac{|Py|^2 - |Qy|^2}{2})^2 + \frac{1}{4}(1 - (|Py|^2 - |Qy|^2)^2),$$

from which we see that if $|Ay - vy|^2 \le \tau$ then

$$(|Py|^2 - |Qy|^2)^2 \ge 1 - 4\tau,$$

which implies that either $|Py|^2 \le 2\tau$ or $|Qy|^2 \le 2\tau$. In our case, we may set $\tau = 2(\delta + \eta)^2$, so $\min\{|Py|, |Qy|\} \le 2(\delta + \eta)$, which gives us the bound stated. $\square$

Next, we formulate and prove a suitable version of Statement 2. We begin with a crude upper bound for the volume of the $\gamma$-expansion of the unit sphere of a subspace of dimension $cn$. (Much more accurate estimates exist, but for us a simple argument suffices.)

**Lemma 4.2.** Let $m = cn$ and let $\gamma > 0$. Assume that $2^{n+1}\gamma \ge 1$. Then the probability that a random unit vector has distance at most $\gamma$ from a given subspace $Y \subset X$ of dimension $m$ is at most $24^n\gamma^{n-m}$.

*Proof.* A spherical cap in $S^{n-1}$ of Euclidean radius $2\gamma$ has volume at most $(4\gamma)^{n-1} \le 8^n\gamma^n = (8\gamma)^n$. By standard estimates, we can also find a $\gamma$-net of $Y$ of cardinality at most $(3/\gamma)^m$. But every point of $S^{n-1}$ that is within $\gamma$ of $Y$ is within $2\gamma$ of a point in the $\gamma$-net, and from this the result follows. $\square$

**Lemma 4.3.** Let $k$ be a positive integer, let $c, \gamma > 0$, and let $Y$ be a random subspace of $\ell_2^n$ of dimension $m$. Then the probability that $Y_\gamma$ contains a unit vector $x$ with at most $k$ distinct coordinates is at most $(3/\gamma)^k(48k)^n\gamma^{n-m}$.

*Proof.* The number of partitions of $\{1, 2, \dots, n\}$ into $k$ sets is at most $k^n$, and for each partition $E_1, \dots, E_k$ the set of vectors that are constant on each $E_i$ is a $k$-dimensional subspace, so there is a $\gamma$-net of the unit sphere of this subspace of size at most $(3/\gamma)^k$.

The probability that $Y_\gamma$ contains a vector with at most $k$ distinct coordinates is at most the probability that $Y_{2\gamma}$ contains a point in one of these $\gamma$-nets, which is at most

$$(3/\gamma)^k(24k)^n(2\gamma)^{n-m} \le (3/\gamma)^k(48k)^n\gamma^{n-m}$$

by Lemma 4.2 and a union bound. $\square$
We present one more technical lemma that is similar to Lemma 4.3, and which will be an important part of the argument. Again we make no attempt to optimize bounds.

**Lemma 4.4.** Let $Z$ be a random subspace of $\ell_2^n$ of dimension $m$. Then the probability that $Z_\gamma$ contains a point with support size at most $r$ is at most $288^n \gamma^{n-m-r}$

*Proof.* The number of sets of size at most $r$ is $\binom{n}{r} \le 2^n$. For each such set $E$ the size of a $\gamma$-net of the unit sphere of the space of vectors supported on $E$ is at most $(3/\gamma)^r$, and for each point in such a net the probability that it is in $Z_{2\gamma}$ is at most $24^n(2\gamma)^{n-m}$. Therefore, the probability we wish to bound is at most

$$2^n(3/\gamma)^r 24^n(2\gamma)^{n-m} \le 288^n \gamma^{n-m-r},$$

which proves the lemma. □

The key point we shall need from the above lemma is that for any $c > 0$ there exists $\gamma > 0$ such that if $n - m - r \ge cn$, then the probability that $Z_\gamma$ contains a point with small support is small. In particular, we have the following statement.

**Corollary 4.5.** Let $\gamma = 2^{-37}$. Let $X = \ell_2^n$ with $n \ge 2$, and let $P: X \to X$ be a random orthogonal projection of rank $n/2$ and let $Q = I - P$. Then the probability that either $PX_{2\gamma}$ or $QX_{2\gamma}$ contains a vector of support size at most $n/4$ is at most $(\frac{2}{3})^n$.

*Proof.* Applying Lemma 4.4, we find that the probability that $PX_{2\gamma}$ contains a vector of support size at most $n/4$ is at most $288^n(2\gamma)^{n/4} = (288/512)^n$. The same is true of $QX_{2\gamma}$ and the result follows with room to spare. □

For the remainder of the paper, we shall assume that $P$ has been chosen in such a way that neither $PX_{2\gamma}$ nor $QX_{2\gamma}$ contains a vector of support size at most $n/4$, and neither $PX_\gamma$ nor $QX_\gamma$ contains a vector with at most five distinct coordinates. By Lemma 4.3 and Corollary 4.5 such a $P$ exists.

# 5 The set of signs cannot be squeezed into a 4-dimensional subspace

Before we move to the heart of the argument, which will be a precise version of Statement 4, let us remark that as we move forward we shall be dealing with many parameters. Since we do not wish to choose them straight away we make sure that it is easy to keep track of all the dependencies by stating them clearly and giving each one a label.
If $Y$ is a 2-dimensional subspace that consists entirely of $\epsilon$-good points, then the last formula in the proof of Corollary 3.2 gives us for each unit vector $x \in Y$ a unit vector $y$ with $|x - y| \le \delta$ and coefficients $\alpha_y$ and $\beta_y$ such that

$$n^{-1/2} \operatorname{sign}(y) \approx_{\delta/\eta} \alpha_y Py + \beta_y Qy,$$

where $\alpha_y = \eta^{-1}(\lambda - 2/\|y\|_A)$ and $\beta_y = \eta^{-1}(\lambda - 1/\|y\|_A)$.

Recall also from the beginning of the proof of Lemma 4.1 that we also have the equivalent formula

$$\eta n^{-1/2} \operatorname{sign}(y) \approx_{\delta} \lambda y - \frac{Ay}{\|y\|_A},$$

from which it follows that $|\lambda| \in [1 - \delta - \eta, \sqrt{2} + \delta + \eta]$, since $\|y\|_A \le |Ay| \le \sqrt{2}\|y\|_A$. Therefore, provided that

$$\delta + \eta \le 2 - \sqrt{2} \qquad (2)$$

it follows that $\lambda \in [\sqrt{2} - 1, 2]$. In particular, it follows that $|\alpha_y|$ and $|\beta_y|$ are at most $2\eta^{-1}$. This bound will be important later. Suppose now that

$$3\delta + 2\eta \le \gamma. \qquad (3)$$

If $x \in Y$, then by Lemma 4.1, either $d(x, PX)$ or $d(x, QX)$ is at most $3\delta + 2\eta$. Therefore, for every $y \in Y_y$, either $d(y, PX)$ or $d(y, QX)$ is at most $3\delta + 2\eta + \gamma \le 2\gamma$, so by the assumption made at the end of the previous section, $y$ has support size at least $n/4$. That is, every vector in $Y_y$ has support size at least $n/4$. We shall use this property frequently in the rest of the section.

Now let us choose non-negative real numbers $r_1, \dots, r_n$ and phases $\phi_1, \dots, \phi_n \in [0, 2\pi)$ such that each unit vector in $Y$ is equal to

$$x(\theta) = (r_1 \sin(\theta + \phi_1), \dots, r_n \sin(\theta + \phi_n))$$

for some $\theta \in [0, 2\pi)$. Note that by looking at $\mathbb{E}_{\theta}|x(\theta)|^2$ we find that $\sum_i r_i^2 = 2$.

**Lemma 5.1.** Let $\delta, \xi > 0$ and $y$ be two vectors in $\mathbb{R}^n$ such that $|x - y| \le \delta$. Then the number of $i$ such that $|x_i| \ge \xi n^{-1/2}$ and $\operatorname{sign}(x_i) \ne \operatorname{sign}(y_i)$ is at most $\xi^{-2}\delta^2 n$.

*Proof.* For each such $i$ we have that $|x_i - y_i|^2 \ge \xi^2 n^{-1}$, and our hypothesis is that $\sum_i |x_i - y_i|^2 \le \delta^2$. $\square$

Let $\alpha > 0$ be a constant to be chosen later, let $E = \{i : r_i \ge \alpha n^{-1/2}\}$, and write $P_E$ for the coordinate projection on to $E$. It will also be convenient to write $E_0$ for $\{1, 2, \dots, n\} \setminus E$, which we think of as the set of coordinates where $Y$ almost vanishes.
**Lemma 5.2.** Let $0 < c, \xi < 1$ and let $\theta$ be chosen uniformly at random from $[0, 2\pi)$. Then with probability at least $1 - \xi/\alpha c$, the number of $i \in E$ such that $|x(\theta)_i| < \xi n^{-1/2}$ is less than $c|E|$.

*Proof.* Since $r_i \ge \alpha n^{-1/2}$ for every $i \in E$, and $x(\theta)_i = r_i \sin(\theta + \phi_i)$, we have that for each $i \in E$,

$$ \mathbb{P}[|x(\theta)_i| < \xi n^{-1/2}] \le \mathbb{P}[|\sin(\theta + \phi_i)| < \xi/\alpha] < \xi/\alpha. $$

To see the last inequality, note that $|\sin(\theta + \phi)|$ on the interval $[0, 2\pi)$ has the same distribution as $\sin\theta$ on the interval $[0, \pi/2)$. But if $\theta$ belongs to that interval, then $\sin\theta \ge 2\theta/\pi$ with equality only at 0 and $\pi/2$, so $\sin\theta < \xi/\alpha$ only if $\theta < \pi\xi/2\alpha$, which is true with probability less than $\xi/\alpha$. Therefore, the expected number of $i \in E$ such that $|x(\theta)_i| < \xi n^{-1/2}$ is less than $\xi|E|/\alpha$.

The result now follows from Markov's inequality. $\square$

For choices of $\xi$ and $c$ that we shall make later, let us call $\theta$ and $x(\theta)$ typical if

(i) the number of $i \in E$ such that $|x(\theta)_i| < \xi n^{-1/2}$ is less than $c|E|$ (that is, the conclusion of Lemma 5.2 holds), and

(ii) there is no $i \in E$ with $\theta + \phi_i \in \{0, \pi\}$.

The second condition, which is there for convenience, holds with probability 1 and ensures that $\text{sign}(x(\theta))_i \in \{-1, 1\}$ for every $i \in E$. Later we shall want to be sure that typical vectors exist, for which Lemma 5.2 tells us that a sufficient condition is the inequality

$$ \xi < \alpha c. \qquad (4) $$

Let us now define $\Sigma$ to be the set of all vectors of the form $n^{-1/2}P_E \text{sign}(x(\theta))$ such that $x(\theta)$ is a typical element of $Y$, let $\beta > 0$ be another parameter to be chosen later, and let $2k$ be the size of a maximal centrally symmetric $\beta$-separated subset of $\Sigma$ (so $V$ consists of $k$ antipodal pairs). Note that $V$ is a $\beta$-net of $\Sigma$.

Since $Y \subset PX_\gamma$ or $Y \subset QX_\gamma$ and we chose $P$ in such a way that both $PX_{2\gamma}$ and $QX_{2\gamma}$ does not contain a vector of support size at most $n/4$, we have that every vector in $Y$, and even in $Y_\gamma$, has support size at least $n/4$. Assuming that

$$ \alpha \le \gamma, \qquad (5) $$

it follows that for every $y \in Y$ its set of “large” coordinates $|E|$ has cardinality at least $n/4$, since $|y - P_{E}y| < \alpha$ for every $y \in Y$ and, clearly, $P_{E}y$ has support size $|E|$. Thus, $\Sigma$ consists of vectors in
a sphere of radius $n^{-1/2}|E|^{1/2} \ge 1/2$, so as long as

$$ \beta \le 1 \qquad (6) $$

we can choose any typical vector $x(\theta)$, let $v = n^{-1/2}P_E \operatorname{sign}(x(\theta))$, and thereby obtain a $\beta$-separated subset $\{v, -v\}$ of $\Sigma$. This proves that $k \ge 1$.

We now consider three cases depending on the size of $V$.

## 5.1 Case 1: $k = 1$.

Let $\zeta = \xi/\alpha c$ and let $V = \{v, -v\}$. Since $\theta$ is typical with probability at least $1 - \zeta$, every closed interval of length greater than $2\pi\zeta$ contains a typical $\theta$. If $n^{-1/2}P_E \operatorname{sign}(x(\theta)) \approx_{\beta} v$, then $n^{-1/2}P_E \operatorname{sign}(-x(\theta)) \approx_{\beta} -v$, so there is at least one $\theta$ such that $n^{-1/2}P_E \operatorname{sign}(x(\theta)) \approx_{\beta} v$ and one such that $n^{-1/2}P_E \operatorname{sign}(x(\theta)) \approx_{\beta} -v$.

Let $A$ be the set of typical $x(\theta)$ such that $n^{-1/2}P_E \operatorname{sign}(x(\theta)) \approx_{\beta} v$ and note that $-A$ is the set of typical $x(\theta)$ such that $n^{-1/2}P_E \operatorname{sign}(x(\theta)) \approx_{\beta} -v$. Note also that every typical $x(\theta)$ belongs to $A$ or $-A$, and that therefore neither $A$ nor $-A$ is empty. Writing $B$ for the set of points at distance at most $\pi\zeta$ from $A$, we also have that $B$ and $-B$ are closed and that $B \cup -B$ is the entire unit circle of $Y$. To see the last assertion, let $x(\theta_0)$ be a point in the unit circle of $Y$. Then the closed interval of length $2\pi\zeta$ centred at $\theta_0$ contains a typical point $\theta$, so $x(\theta)$ belongs to $A \cup (-A)$ and therefore $x(\theta_0) \in B \cup -B$, as the distance from $x(\theta_0)$ to $x(\theta)$ is at most $\pi\zeta$. Since the unit circle is connected, $B \cap -B$ is non-empty, from which it follows that there exist typical unit vectors $x, y \in Y$ such that $|x - y| \le 2\pi\zeta$ and such that $n^{-1/2}P_E \operatorname{sign}(x) \approx_{\beta} v$, and $n^{-1/2}P_E \operatorname{sign}(y) \approx_{\beta} -v$.

It follows that $n^{-1/2}P_E \operatorname{sign}(x)$ differs from $v$ in at most $\beta^2 n/4$ coordinates, and $n^{-1/2}P_E \operatorname{sign}(y)$ differs from $-v$ in at most $\beta^2 n/4$ coordinates. Therefore, $P_E \operatorname{sign}(x)$ and $P_E \operatorname{sign}(y)$ are equal in at most $\beta^2 n/2$ coordinates. Moreover, by Lemma 5.1, the number of $i$ for which $\operatorname{sign}(x_i) \ne \operatorname{sign}(y_i)$ and $|x_i| \ge \rho n^{-1/2}$ is at most $\rho^{-2}(2\pi\zeta)^2 n = (2\pi\xi/\alpha c\rho)^2 n$.

From these two facts it follows that the number of coordinates $i \in E$ for which $|x_i| \ge \rho n^{-1/2}$ is at most $((2\pi\xi/\alpha c\rho)^2 + \beta^2/2)n$. Therefore, we find that $x$ has distance at most $\rho$ from a vector of support size at most $((2\pi\xi/\alpha c\rho)^2 + \beta^2/2)n$.

If we choose parameters in such a way that

$$ \rho \le \gamma \qquad (7) $$
and

$$ \left( \frac{2\pi\xi}{\alpha c\rho} \right)^2 + \frac{\beta^2}{2} < 1/4 \qquad (8) $$

we obtain a contradiction with the fact that $Y_γ$ does not contain a vector of support size less than $n/4$.

## 5.2 Case 2: $2 \le k \le 4$

Let $V = \{\pm v_1, \dots, \pm v_k\}$. Since each $v_i$ is of the form $n^{-1/2}P_E \operatorname{sign}(x(\theta))$ for some typical vector $x(\theta) \in Y$, it takes values $\pm n^{-1/2}$ in $E$.

We now show that either this case can be reduced to the case $k = 1$ with $\beta$ replaced by $48\beta$ or there is a subset $V'$ of $V$ consisting of at least two antipodal pairs such that $V'$ is a $3\kappa$-separated $\kappa$-net of $\Sigma$ and $\beta \le \kappa \le 16\beta$.

Since $V$ is a $\beta$-net of $\Sigma$, then if it is $3\beta$ separated then we are done. If not, we can find $i \ne j$ such that $|v_i - v_j| \le 3\beta$. Then we can remove $\pm v_j$ from $V$ and we will still have a $4\beta$-net. Similarly, if $V' = V \setminus \{\pm v_j\}$ is $12\beta$-separated we are done, but if it contains two distinct elements $v_i, v_j$ such that $|v_i - v_j| \le 12\beta$, then again we can remove $\pm v_j$ and we will still have a $16\beta$-net. Finally, if there are two distinct elements $v_i, v_j$ with $|v_i - v_j| \le 48\beta$, then we may remove $\pm v_j$ and end up with $V'$ of the form $\{v, -v\}$ and we are back in case $k = 1$. However, now $\beta$ is replaced by $48\beta$, which we must allow for when choosing our parameters, so we need to strengthen condition (6) to the condition

$$ \beta \le 1/48. \qquad (9) $$

If the process stops before we reach $k = 1$, then we have a $3\kappa$-separated $\kappa$-net $V' = \{\pm v_1, \dots, \pm v_m\}$ of $\Sigma$ such that $2 \le m \le 4$ and $\kappa \le 16\beta$ as claimed.

Recall that every interval of length greater than $2\pi\zeta$ contains a typical $\theta$, and hence by a connectedness argument similar to the one used for the case $k = 1$ there must exist $\theta, \phi$, and $v_i \ne \pm v_j$ such that

$$ |\theta - \phi| \le 2\pi\zeta, $$

$$ |n^{-1/2} P_E \operatorname{sign}(x(\theta)) - v_i| \le \kappa, $$

and

$$ |n^{-1/2} P_E \operatorname{sign}(x(\phi)) - v_j| \le \kappa. $$

Since $|v_i \pm v_j| \ge 3\kappa$, it follows that $n^{-1/2}|P_E \operatorname{sign}(x(\theta)) - P_E \operatorname{sign}(x(\phi))|$ and $n^{-1/2}|P_E \operatorname{sign}(x(\theta)) + P_E \operatorname{sign}(x(\phi))|$ are both at least $\kappa$. Now recall that for every $x \in Y$ we can find $y$ with $|x - y| \le \delta$
such that

$$n^{-1/2} \operatorname{sign}(y) \approx_{\delta/\eta} \alpha_y Py + \beta_y Qy$$

for some constants $\alpha_y$ and $\beta_y$. Let us choose $y(\theta)$ and $y(\phi)$ that have this relationship with $x(\theta)$ and $x(\phi)$, respectively.

By Lemma 5.1 and the assumption that $x$ is typical, the number of coordinates in $E$ such that $\operatorname{sign}(x(\theta))$ and $\operatorname{sign}(y(\theta))$ differ is at most $c|E| + \xi^{-2}\delta^2n \le (c + \xi^{-2}\delta^2)n$, so

$$n^{-1/2}|P_E \operatorname{sign}(x(\theta)) - P_E \operatorname{sign}(y(\theta))| \le 2(c + \xi^{-2}\delta^2)^{1/2},$$

and similarly for $\phi$. If we choose parameters in such a way that

$$c + \xi^{-2}\delta^2 \le \beta^4/256, \quad (10)$$

it follows that these distances are both at most $\beta^2/8$.

Let us write $\alpha(\theta)$ instead of $\alpha_{y(\theta)}$, and similarly for $\phi$. Then

$$n^{-1/2} \operatorname{sign}(y(\theta)) \approx_{\delta/\eta} \alpha(\theta)Py(\theta) + \beta(\theta)Qy(\theta),$$

and

$$n^{-1/2} \operatorname{sign}(y(\phi)) \approx_{\delta/\eta} \alpha(\phi)Py(\phi) + \beta(\phi)Qy(\phi).$$

Also, since $|\theta - \phi| \le 2\pi\zeta$, we have $|x(\theta) - x(\phi)| \le 2\pi\zeta$ (because $|x(\theta) - x(\phi)| < |\theta - \phi|$), and therefore $|y(\theta) - y(\phi)| \le 2\pi\zeta + 2\delta$. It follows that

$$|\alpha(\phi)Py(\phi) + \beta(\phi)Qy(\phi) - (\alpha(\phi)Py(\theta) + \beta(\phi)Qy(\theta))| \le 2(\pi\zeta + \delta)(|\alpha(\phi)| + |\beta(\phi)|).$$

Now recall that $|\alpha(\phi)|$ and $|\beta(\phi)|$ are both at most $2\eta^{-1}$. We therefore obtain the approximation

$$n^{-1/2} \operatorname{sign}(y(\phi)) \approx_{\sigma} \alpha(\phi)Py(\theta) + \beta(\phi)Qy(\theta),$$

$$\text{where } \sigma = \delta/\eta + 8(\pi\zeta + \delta)/\eta = (8\pi\zeta + 9\delta)/\eta.$$

It is convenient to encapsulate our knowledge so far as an approximate matrix equation

$$\begin{pmatrix} \alpha(\theta) & \beta(\theta) \\ \alpha(\phi) & \beta(\phi) \end{pmatrix} \begin{pmatrix} Py(\theta) \\ Qy(\theta) \end{pmatrix} \approx_{\sigma} n^{-1/2} \begin{pmatrix} \operatorname{sign}(y(\theta)) \\ \operatorname{sign}(y(\phi)) \end{pmatrix}$$

where by $\approx_{\sigma}$ in this context we mean that the approximation holds coordinatewise.

The rough idea of what we shall now do is as follows. Because $\operatorname{sign}(y(\theta))$ and $\operatorname{sign}(y(\phi))$ are
not roughly proportional to each other, the matrix $\begin{pmatrix} \alpha(\theta) & \beta(\theta) \\ \alpha(\phi) & \beta(\phi) \end{pmatrix}$ is well-invertible, which allows us to deduce from the approximate matrix equation that $Py(\theta)$ and $Qy(\theta)$ can both be approximated by linear combinations of $n^{-1/2} \text{sign}(y(\theta))$ and $n^{-1/2} \text{sign}(y(\phi))$, with coefficients that are not too large. Therefore, $y(\theta)$ can as well, which implies that $x(\theta)$ can be. But $\text{sign}(y(\theta))$ and $\text{sign}(y(\phi))$ take at most two values each on almost all of $E$, and $x(\theta)$ is small outside $E$, so $x(\theta)$ can be approximated by a vector whose coordinates have at most five distinct values. Then we can obtain a contradiction from Lemma 4.3.

To carry out this argument we begin by making precise the statement that $\text{sign}(y(\theta))$ and $\text{sign}(y(\phi))$ are not roughly proportional.

**Lemma 5.3.** Let $u$ and $v$ be vectors in $\mathbb{R}^n$ that take values $\pm n^{-1/2}$ in a set $E$ of size $m$. Suppose that there are $r$ values in $E$ with $u_i = v_i$ and $s$ values with $u_i \neq v_i$. Then for every $\lambda \in \mathbb{R}$, $|u - \lambda v| \ge 2(rs/mn)^{1/2}$.

*Proof.* We have that

$$n|u - \lambda v|^2 \ge r(1 - \lambda)^2 + s(1 + \lambda)^2 \\ = (1 + \lambda^2)m + 2\lambda(s - r).$$

This is minimized when $\lambda = (r - s)/m$, and the minimum works out to be $4rs/m$. The lemma follows on dividing both sides by $n$ and taking the square root. $\square$

We showed earlier that the distance between $n^{-1/2}P_E \text{sign}(x(\theta))$ and $\pm n^{-1/2}P_E \text{sign}(x(\phi))$ is at least $\kappa$, which by assumption is at least $\beta$. It follows further that the conditions of Lemma 5.3 apply to $n^{-1/2} \text{sign}(x(\theta))$ and $n^{-1/2} \text{sign}(x(\phi))$ with both $r$ and $s$ at least $\beta^2 n/4$. Therefore, using the trivial bound $|E| \le n$, we deduce that

$$n^{-1/2}|\text{sign}(x(\theta)) - \lambda \text{sign}(x(\phi))| \ge \beta^2/2.$$

Therefore, using the fact that

$$n^{-1/2}|\text{sign}(x(\theta)) - \text{sign}(y(\theta))| \le \beta^2/8$$

and

$$n^{-1/2}|\text{sign}(x(\phi)) - \text{sign}(y(\phi))| \le \beta^2/8,$$

we find that

$$n^{-1/2}|\text{sign}(y(\theta)) - \lambda \text{sign}(y(\phi))| \ge \frac{\beta^2}{2} - \frac{\beta^2}{8}(|\lambda| + 1) \ge \beta^2/8$$
when $|\lambda| \le 2$. In case $|\lambda| \ge 2$ we can instead use the bound

$$ (1 + \lambda^2)m + 2\lambda(s - r) \ge (|\lambda| - 1)^2m $$

to deduce that

$$ n^{-1/2} |\operatorname{sign}(x(\theta)) - \lambda \operatorname{sign}(x(\phi))| \ge \frac{\beta^2}{2} (|\lambda| - 1), $$

from which it follows that

$$ n^{-1/2} |\operatorname{sign}(y(\theta)) - \lambda \operatorname{sign}(y(\phi))| \ge \frac{\beta^2}{2} (|\lambda| - 1) - \frac{\beta^2}{8} (|\lambda| + 1), $$

which is again at least $\beta^2/8$.

Now that we have shown in a precise sense that $n^{-1/2} \operatorname{sign}(y(\theta))$ and $n^{-1/2} \operatorname{sign}(y(\phi))$ are not approximately proportional to each other, we turn to deducing that the matrix $\begin{pmatrix} \alpha(\theta) & \beta(\theta) \\ \alpha(\phi) & \beta(\phi) \end{pmatrix}$ is well-invertible, by which we simply mean that its determinant is not too small.

**Lemma 5.4.** Let $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ be a $2 \times 2$ real matrix, let $x$ and $y$ be vectors in a Euclidean space such that $\langle x, y \rangle = 0$, and let

$$ \begin{pmatrix} u \\ v \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}. $$

Then there exists $\lambda$ such that $|u - \lambda v| \le \frac{|x| |y| |\det(A)|}{|v|}$

*Proof.* Consider first the case where $x$ and $y$ are unit vectors. Then

$$ \begin{aligned} |u - \lambda v|^2 &= (a - \lambda c)^2 + (b - \lambda d)^2 \\ &= (c^2 + d^2)\lambda^2 - 2(ac + bd)\lambda + a^2 + b^2. \end{aligned} $$

This is minimized when $\lambda = \frac{ac+bd}{c^2+d^2}$, and the minimum is

$$ a^2 + b^2 - \frac{(ac + bd)^2}{c^2 + d^2} = \frac{(ad - bc)^2}{c^2 + d^2}, $$

which proves the result.

In the general case, we have that

$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a|x| & b|y| \\ c|x| & d|y| \end{pmatrix} \begin{pmatrix} x/|x| \\ y/|y| \end{pmatrix}. $$
Using the case for unit vectors, we deduce that there exists $\lambda$ such that

$$|u - \lambda v|^2 \leq \frac{|x|^2|y|^2 \det(A)^2}{c^2|x|^2 + d^2|y|^2},$$

and again the result is proved. □

Let us now apply this lemma with $A = \begin{pmatrix} \alpha(\theta) & \beta(\theta) \\ \alpha(\phi) & \beta(\phi) \end{pmatrix}$, $x = Py(\theta)$ and $y = Qy(\theta)$. Let $\begin{pmatrix} u' \\ v' \end{pmatrix} = A \begin{pmatrix} x \\ y \end{pmatrix}$ and let $u = n^{-1/2} \text{sign}(y(\theta))$, $v = n^{-1/2} \text{sign}(y(\phi))$. The approximate matrix equation proved earlier states that $|u - u'| \le \sigma$ and $|v - v'| \le \sigma$. It follows from the lemma that there exists $\lambda$ such that

$$\frac{|Py(\theta)| |Qy(\theta)| |\det(A)|}{|v'|} \geq |u' - \lambda v'| \geq |u - \lambda v| - (1 + |\lambda|)\sigma.$$

But we have shown that $n^{-1/2} |\text{sign}(y(\theta)) - \lambda \text{sign}(y(\phi))| \ge \beta^2/8$ for every $\lambda$. Since we also know that $|Py(\theta)| \le 1$ and $|Qy(\theta)| \le 1$, it follows that

$$|\det(A)| \geq (\beta^2/8 - (1 + |\lambda|)\sigma)|v'|.$$

From the proof of the last lemma it follows that the minimum distance is achieved when $\lambda = \frac{\alpha(\phi)\alpha(\theta)|x|^2 + \beta(\phi)\beta(\theta)|y|^2}{|v'|^2}$. Recall also from the beginning of the section that $\alpha(\phi)$, $\alpha(\theta)$, $\beta(\phi)$, $\beta(\theta) \le 2\eta^{-1}$. Since $|v' - v| \le \sigma$, $v = n^{-1/2} \text{sign}(y(\phi))$, and every $y(\phi)$ has support size at least $n/4$, we get that $|v'| \ge 1/2 - \sigma$.

Hence

$$|\lambda| \leq \frac{4}{\eta^2(1/2 - \sigma)^2}.$$

Assuming that

$$\sigma \leq \beta^2 \eta^2 / 2^{10} \qquad (11)$$

we may deduce that $\sigma(1 + |\lambda|) \le \beta^2/16$ and hence that $|\det A| \ge (1/2 - \sigma)\beta^2/16 \ge \beta^2/64$.

Let us rewrite the approximate matrix equation as

$$\begin{pmatrix} \alpha(\theta) & \beta(\theta) \\ \alpha(\phi) & \beta(\phi) \end{pmatrix} \begin{pmatrix} Py(\theta) \\ Qy(\theta) \end{pmatrix} = \begin{pmatrix} u' \\ v' \end{pmatrix} \approx_{\sigma} n^{-1/2} \begin{pmatrix} \text{sign}(y(\theta)) \\ \text{sign}(y(\phi)) \end{pmatrix}.$$

Then

$$\begin{pmatrix} Py(\theta) \\ Qy(\theta) \end{pmatrix} = \det(A)^{-1} \begin{pmatrix} \beta(\phi) & -\beta(\theta) \\ -\alpha(\phi) & \alpha(\theta) \end{pmatrix} \begin{pmatrix} u' \\ v' \end{pmatrix}.$$

Since the coefficients of $A$ have absolute value at most $2\eta^{-1}$, it follows that both $Py(\theta)$ and
$Qy(\theta)$ are linear combinations of $u'$ and $v'$ with coefficients of absolute value at most $128\eta^{-1}\beta^{-2}$. Using again the fact that $|u' - n^{-1/2} \text{sign}(y(\theta))|$ and $|v' - n^{-1/2} \text{sign}(y(\phi))|$ are both at most $\sigma$, it follows that both $Py(\theta)$ and $Qy(\theta)$ can be approximated to within $256\eta^{-1}\beta^{-2}\sigma$ by the corresponding linear combinations of $n^{-1/2} \text{sign}(y(\theta))$ and $n^{-1/2} \text{sign}(y(\phi))$, and hence that $y(\theta)$ can be approximated to within $512\eta^{-1}\beta^{-2}\sigma$ by a linear combination of $n^{-1/2} \text{sign}(y(\theta))$ and $n^{-1/2} \text{sign}(y(\phi))$ with coefficients of absolute value at most $256\eta^{-1}\beta^{-2}$.

Now recall that

$$n^{-1/2}|P_E \text{sign}(x(\theta)) - P_E \text{sign}(y(\theta))| \le 2(c + \xi^{-2}\delta^2)^{1/2},$$

and similarly for $\phi$, which implies in particular that $n^{-1/2}P_E \text{sign}(y(\theta))$ and $n^{-1/2}P_E \text{sign}(y(\phi))$ can be approximated to within $2(c + \xi^{-2}\delta^2)^{1/2}$ by vectors whose coordinates take just the values $\pm n^{-1/2}$ on $E$. This is because $x(\theta)$ and $x(\phi)$ are typical, which implies, by the second condition in the definition of “typical”, that all coordinates of $P_E \text{sign}(x(\theta))$ and $P_E \text{sign}(x(\phi))$ are $\pm 1$.

Putting together the bounds obtained in the last two paragraphs we get that $P_E y(\theta)$ can be approximated by a linear combination of $n^{-1/2}P_E \text{sign}(x(\theta))$ and $n^{-1/2}P_E \text{sign}(y(\phi))$ to within $512\eta^{-1}\beta^{-2}\sigma + 1024\eta^{-1}\beta^{-2}(c + \xi^{-2}\delta^2)^{1/2}$. Thus, $P_E y(\theta)$ can be approximated by a vector with at most four distinct coordinates.

This in turn implies that $P_E x(\theta)$ can be approximated to within $\delta + 512\eta^{-1}\beta^{-2}\sigma + 1024\eta^{-1}\beta^{-2}(c + \xi^{-2}\delta^2)^{1/2}$ by such a vector. But $|x(\theta) - P_E x(\theta)| \le \alpha$, so we end up with the conclusion that $x(\theta)$ can be approximated to within $\alpha + \delta + 512\eta^{-1}\beta^{-2}\sigma + 1024\eta^{-1}\beta^{-2}(c + \xi^{-2}\delta^2)^{1/2}$ by a vector that takes at most five distinct values (the fifth value being zero). But $x(\theta) \in Y$, so it is an $\epsilon$-good point, which implies by Lemma 4.1 that $d(x(\theta), PX) \le 3\delta + 2\eta$ or $d(x(\theta), QX) \le 3\delta + 2\eta$. Provided we have chosen our parameters in such a way that

$$\alpha + 4\delta + 2\eta + 512\eta^{-1}\beta^{-2}\sigma + 1024\eta^{-1}\beta^{-2}(c + \xi^{-2}\delta^2)^{1/2} \le \gamma, \quad (12)$$

this contradicts the fact that $P$ was chosen to ensure that neither $PX_\gamma$ nor $QX_\gamma$ contains a vector with at most five distinct coordinates (see the end of Section 4 where this was shown to be possible).

## 5.3 Case 3: $k \ge 5$.

We begin with a simple lemma to estimate how well we can simultaneously approximate $k$ orthonormal vectors by a $(k-1)$-dimensional subspace.

**Lemma 5.5.** Let $W$ be a $(k-1)$-dimensional subspace of $\mathbb{R}^n$ and let $u_1, \dots, u_k$ be an orthonormal sequence. Then there exists $i$ such that $d(u_i, W) \ge k^{-1/2}$.
*Proof.* Without loss of generality $n = k$. Now let $v$ be a unit vector orthogonal to $W$. Then the orthogonal projection $P_W$ to $W$ is given by the formula $P_W(x) = x - \langle x, v \rangle v$, from which it follows that $d(x, W) = |\langle x, v \rangle|$. But $\sum_{i=1}^k \langle u_i, v \rangle^2 = 1$, so there must exist $i$ such that $|\langle u_i, v \rangle| \ge k^{-1/2}$, which proves the lemma. □

Now, with the help of the assumption that $k \ge 5$, we prove that we cannot find a 4-dimensional subspace that approximately contains all the vectors in $\Sigma$. For convenience, let us reorder the coordinates in such a way that $E = \{1, 2, \dots, m\}$ and $0 \le \phi_1 \le \phi_2 \le \dots \le \phi_m < 2\pi$. Then for every typical vector $x(\theta)$, the set of $i$ such that $x(\theta)_i > 0$ is an interval mod $m$.

**Lemma 5.6.** Let $W$ be a 4-dimensional subspace of $X$. Then $\Sigma$ contains a vector $u$ such that $d(u, W) \ge \beta/2 \sqrt{5}$.

*Proof.* Let $0 \le \theta_1 < \dots < \theta_5 < \pi$ be such that the points $u_j = n^{-1/2}P_E \operatorname{sign}(x(\theta_j)) \in \Sigma$ and that together with the points $-u_j$ form a $\beta$-separated subset of $\Sigma$. For each $j \in \{1, 2, \dots, 5\}$ let $[a_j, b_j]$ be the interval mod $m$ of $i$ such that $(u_j)_i = n^{-1/2}$.

Note that $a_1 \ge \dots \ge a_5$ and $b_1 \ge \dots \ge b_5$, where here we refer to the cyclic ordering on the integers mod $m$. It follows that for each $j$, $(u_{j+1} - u_j)_i = 2n^{-1/2}$ on the interval $[a_{j+1}, a_j)$, $-2n^{-1/2}$ on the interval $(b_{j+1}, b_j]$, and zero everywhere else. In particular, the vectors of the form $u_{j+1} - u_j$ for $j = 1, 2, 3, 4$, together with the vector $u_1 + u_5$, are orthogonal.

Since we have that $|u_i \pm u_j| \ge \beta$ for every $i \ne j$, setting $v_j = \frac{u_{j+1}-u_j}{|u_{j+1}-u_j|}$ for $j = 1, \dots, 4$ and $v_5 = \frac{u_1+u_5}{|u_1+u_5|}$, we may deduce from Lemma 5.5 that $d(v_j, W) \ge 1/\sqrt{5}$ for some $j$. If $j = 1, \dots, 4$ then this implies that $d(u_{j+1} - u_j, W) \ge \beta/\sqrt{5}$, which implies that either $d(u_{j+1}, W) \ge \beta/2\sqrt{5}$ or $d(u_j, W) \ge \beta/2\sqrt{5}$. Similarly, if $j = 5$ we get that either $d(u_1, W) \ge \beta/2\sqrt{5}$ or $d(u_5, W) \ge \beta/2\sqrt{5}$. This proves the lemma. □

Let $u = P_E \operatorname{sign}(x(\theta))$ be given by Lemma 5.6. Recall that (with parameters that satisfy condition (12)) we have

$$n^{-1/2}|P_E \operatorname{sign}(x(\theta)) - P_E \operatorname{sign}(y(\theta))| \le \beta^2/8.$$

Recall also that

$$n^{-1/2} \operatorname{sign}(y(\theta)) \approx_{\delta/\eta} \alpha(\theta)Py(\theta) + \beta(\theta)Qy(\theta)$$

for some coefficients $\alpha(\theta), \beta(\theta)$ that have absolute values at most $2\eta^{-1}$. We also know that $|y(\theta) - x(\theta)| \le \delta$. It follows that

$$n^{-1/2} P_E \operatorname{sign}(x(\theta)) \approx_{\beta^2/8+\delta/\eta+4\delta/\eta} \alpha(\theta) P_E P x(\theta) + \beta(\theta) P_E Q x(\theta).$$

It follows that the distance from $n^{-1/2}P_E \operatorname{sign}(x(\theta))$ to the subspace $P_E(PY + QY)$, which has
dimension at most 4, is at most $\beta^2/8 + 5\delta/\eta$. If we pick parameters in such a way that

$$ \frac{\beta^2}{8} + \frac{5\delta}{\eta} < \frac{\beta}{2\sqrt{5}}, \qquad (13) $$

then this contradicts Lemma 5.6.

## 5.4 Choosing parameters

We conclude by showing that there exists a choice of parameters which fulfils all the conditions. We are not optimizing this choice.

First, recall that we have already chosen $\gamma$ in the Corollary 4.5 to be $2^{-37}$. Further we see that $\beta = 2^{-6}$ satisfies (6) and (9). We can further choose $\eta = 2^{-40}$, $\alpha = 2^{-40}$, $\rho = 2^{-40}$ and then $c = 2^{-205}$, $\xi = 2^{-403}$ and finally $\delta = 2^{-506}$. It is easy to check that these parameters meet all the conditions.

This finishes the proof that the 2-Euclidean norm defined in (1), for $n \ge 35$ (which comes from our choice of $\gamma$ and the condition in Lemma 4.2 and the fact that we use a $2\gamma$-expansion), contains no 2-dimensional subspace which is both strongly $(1 + \epsilon)$-complemented and strongly $(1 + \epsilon)$-Euclidean with $\epsilon = \delta^2/8C^2 = 2^{-1017}$. (the dependence of $\epsilon$ on $\delta$ was established in the proof of Lemma 2.4).

## References

[1] A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123–160. Academic Press, 1961.

[2] V. Milman. New proof of the theorem of A. Dvoretzky on intersections of convex bodies. Functional Analysis and Its Applications, 5(4):288–295, 1971.

[3] S. Szarek and N. Tomczak-Jaegermann. On the nontrivial projection problem. Advances in Mathematics, 221:331–342, 2009.