Return to Answer

2 deleted 1 characters in body

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 Cauchy-Schwarz 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.

1

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.