Question

This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest possible proof strategies?

I have vectors $v_1, \ldots, v_k$ in ${\bf R}^n$. Each of them has euclidean length at most $.01$, and for every unit vector $u \in {\bf R}^n$ they satisfy $$\sum_{i=1}^k |\langle u,v_i\rangle|^2 = 1.$$ Is it possible to find a set of indices $S \subset \{1, \ldots, k\}$ such that $$.0001 < \sum_{i \in S} |\langle u,v_i\rangle|^2 < .9999$$ for every unit vector $u$? This will imply the same bounds when summing over the complement of $S$.

The $.01$ and $.0001$ aren't important; I just need the result for some positive $\delta$ and $\epsilon$. But they have to be independent of $k$ and $n$. (This may seem unlikely, until you try to construct a counterexample.)

The motivation is that this is a (very slightly simplified) equivalent version of the famous Kadison-Singer problem. A solution would have important consequences in operator theory, harmonic analysis, and C*-algebra. Many people have worked on this problem, but perhaps not in the above form, which I feel exposes the combinatorial difficulty which is the real root of the problem.

Answer 1

This is mainly a comment. My first guess would be that if it is true, then a random subset of density $1/2$ works. A result in this direction is Lemma 3.2 in

M. Rudelson, Contact points of convex bodies, Israel Journal of Mathematics, 1997, Volume 101, Number 1, Pages 93-124.

It says:

Lemma :Let $x_1,...,x_k$ be vectors in $\mathbb R^n$, $\varepsilon_1,...,\varepsilon_k$ be independent Bernoulli variables, taking values $1,-1$ with probability $1/2$. Then $${\mathbb E} \left\| \sum_{i=1}^k \varepsilon_i |x_i\rangle {\langle x_i} | \right\|\leq C \log(n) \sqrt{\log(k)} \max_i \|x_i\| \left\| \sum_{i=1}^k |x_i\rangle \langle x_i| \right\|^{1/2}$$ for some absolute constant C.

In your case, this says that a random set of density $1/2$ solves the easier problem where $\delta$ may depend on $n$ and $k$. At the same time it proves much more, since there is even concentration around $1/2$. More precisely, if $ \sum_{i=1}^k |x_i\rangle \langle x_i| =1$ and $\|x_i\|< \delta$, then

$${\mathbb E} \left\|\frac12 - \sum_{i=1}^k \eta_i |x_i\rangle {\langle x_i} | \right\|\leq C/2 \log(n) \sqrt{\log(k)} \cdot \delta,$$ where $\eta_i$ are independent Bernoulli with values in ${0,1}$.

Since $n \leq k \delta^2$ (looking at the trace), an easy calculation shows that $\delta$ only depends on $k$. At the same time, it seems to me that the problem is getting easier if $k$ is larger, but I cannot substantiate this claim. Remark 3.3 in the same paper shows that the inequality cannot be improved to become independent of $n$ and $k$. This somehow shows that choosing a random subset is too naive; at least when one studies the expected value of the norm as in the inequality above.