Given a set $S$ of non-zero vectors in $\mathbb{R}^n,$ and a subspace $L,$ consider $f(S,L)=\max\_{s \in S}\frac{\|Ps\|\_2}{\|s\|\_2}$ where $Ps$ is the orthogonal projection of $s$ onto $L.$


Specifically, consider the set $X$ consisting of the $2^n-1$ (nonzero) vectors with all coordinates $0$ or $1$. 


A [recent question](https://mathoverflow.net/questions/60604) concerns criteria which might show, for a given subspace $L$, that $f(X,L)$ is small. Here I am concerned with choosing the subspace: 



> 
> For each $n$ and $d<n$, what is the minimum over all $d$-dimensional subspaces of $f(X,L)?$
> 
> 
> 


If that seems too broad, then the case $d=1$ would be of interest. 




---


**Summary**
There are several good answers here. It is a toss-up which one to choose. I'm going to repost the $d>1$ case as a [new question](https://mathoverflow.net/questions/60901).


Here is a somewhat selective review, all for the case $d=1.$


1. Gerhard mentioned that $(1,-1,0,0,\cdots)$ attains $\sqrt{1/2}.$
2. Seva suggested that $(1,1/\sqrt{2},1/\sqrt{3},\cdots)$ is asymptotically optimal attaining $O(\sqrt{1/\log n}).$ This is indeed better but the smallest $n$ for which it beats $\sqrt{1/2}$ is (by my calculations) $n=1203.$ The nice optimality proof references $(1,\sqrt{2}-1,\sqrt{3}-\sqrt{2},\cdots)$ This is actually a better choice, it first beats $\sqrt{1/2}$ for $n=56.$ The two choices are comparable (up to scalar multiple) because $\sqrt{k+1}-\sqrt{k} \approx 1/2\sqrt{k}$. The approximation is pretty good, except for $k=0.$ As this is the largest entry, it takes longer to beat $\sqrt{1/2}$.
3. Denis essentially does mention $(1,\sqrt{2}-1,\sqrt{3}-\sqrt{2},\cdots)$ and, at least in one edit, suggests reflecting in the center: So for $n=6$ use $(a\_1,a\_2,a\_3,-a\_3,-a\_2,-a\_1)$ where $a\_k=\sqrt{k}-\sqrt{k-1}.$ This is superior at $n=4$ and even at $n=3$ with the right rule for the center: It seems obvious that there should be symmetry and entries summing to $0$, but actually $(1,\sqrt{2}-1,-1)$ is the best choice for $n=3$.
4. Emil nicely lays this out in a comment. Here is my somewhat informal explanation (with some minor details skipped) , in case another perspective is useful. I suggest at the end that this should remind one of linear programming.:


There is no harm in assuming that the subspace is generated by a vector $v=(v\_1,v\_2,\cdots,v\_n)$ with $v\_1 > v\_2 > \cdots > v\_n$ (actually, only $\ge$ is clear, but I will ignore that in the interests of brevity.). By a mild abuse of notation, for $j>0$ let $x\_{j}$ be the vector whose first $j$ entries are $1$ and the rest $0$ while $v\_{-j}$ has first $n-j$ entries $0$ and the last $j$ equal to $1$. 


Given $v$, Let $B \subset X$ be the set of vectors in $X$ which attain the maximum of $\frac{\|Px\|}{\|x\|}.$ I make two claims about $B$:


* Every vector in $B$ is $x\_j$ for some $j$ with $v\_j > 0$ or else $x\_{-j}$ for some $j$ with $v\_{n-j} < 0$ (think about why any other vector with $j$ entries equal to $1$ will be worse.)
* Unless $B$ is a basis of $\mathbb{R}^n$, There is a $v$ which gives a better ratio. (Because otherwise we should be able perturb the entries of $v$ in such a way as to lower $\frac{\|Px\|}{\|x\|}$ for the vectors already in $B$ (simultaneously keeping them equal and maximal) while raising that ratio slightly for some $x\_j$ not yet in $B$.


Together these tell us that $B=\lbrace x\_{1},x\_{2},\cdots x\_n\rbrace$ or else $B=\lbrace x\_{1},x\_{2},\cdots x\_q;x\_{q-n},\cdots,x\_{-2},x\_{-1}\rbrace$ where $v\_q>0>v\_{q+1}.$ Since the various ratios must all be the same, we deduce that $v=(\alpha a\_1,\alpha a\_2, \cdots,\alpha a\_q; -\beta a\_{n-q},\cdots,-\beta a\_2,-\beta a\_1)$ for the $a\_k$ as above. Here $\alpha$ and $\beta$ are positive constants. A bit of reflection shows that they must be equal and hence can be taken to be $1$. Finally, $q$ should be $ n/2 $ (rounded if needed).


Comment: (disclaimer: I am an optimist but not an optimizer so the following may inexact.) Here we have the convex optimization problem of choosing $v$ so as to minimize the largest of $\frac{\|Px\|\_2}{\|x\|\_2}.$ Had it been $\frac{\|Px\|\_1}{\|x\|\_1}$ we would have been able to use linear programming. My argument above has the feel of linear programing, perhaps using duality. Perhaps a similar method could uncover optimal subspaces of dimension $d \ge 2.$



Projecting the unit cube onto subspaces
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-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.


