Skip to main content
1 of 2
Seva
  • 23k
  • 2
  • 59
  • 141

My answer concerns with the case $d=1$ only. Without loss of generality, we can focus on the subspaces, generated by a vector with all coordinates non-negative. It is easy to verify that for the subspace $L$, generated by the vector $(1,1/\sqrt{2},...,1/\sqrt{n})$, the projection onto $L$ of any non-zero vector $\epsilon\in\{0,1\}^n$ has lenght at most $\frac{2}{\sqrt{\log n}}\,\|\epsilon\|$. This is essentially the worst case as, on the other hand, for any non-zero vector $z\in R^n$ with non-negative coordinates there exists a non-zero vector $\epsilon\in\{0,1\}^n$ such that $$ \langle z,\epsilon \rangle \ge \frac{2}{\sqrt{\log n+4}}\,\|z\|\|\epsilon\|. $$

To see this, write $z=(z_1,...,z_n)$ and, without loss of generality, assume that $$ z_1 \ge \dotsb \ge z_n \ge 0\quad \text{and}\quad \|z\|=1. $$ Let $\tau := 2/\sqrt{\log n+4}$. We will show that there exists $k\in[n]$ with $z_1+...+z_k\ge\tau\sqrt k$; choosing then $\epsilon$ to be the vector with the first $k$ coordinates equal to $1$ and the rest equal to $0$ completes the proof.

Suppose, for a contradiction, that $z_1+...+z_k<\tau\sqrt{k}$ for $k=1,...,n$. Multiplying this inequality by $z_k-z_{k+1}$ for each $k\in[n-1]$, and by $z_n$ for $k=n$, adding up the resulting estimates, and rearranging the terms, we obtain $$ z_1^2+...+z_n^2 < \tau \big(z_1+(\sqrt2-1)z_2 +...+ (\sqrt n-\sqrt{n-1})z_n \big). $$ Using Cauchy-Schwartz now gives $$ 1 < \tau \Big( \sum_{k=1}^n \big(\sqrt k-\sqrt{k-1}\big)^2 \Big)^{1/2} \|z\| < \tau \sqrt{\log n +4}/2, $$ a contradiction.

Seva
  • 23k
  • 2
  • 59
  • 141