Return to Question

I believe the solution posted to the arXiv this morning by Marcus, Spielman, and Srivastava is correct. Apparently I am no longer able to accept answers, but if I could I would accept Jon's answer which cites this preprint. As Jon says, this is fantastic!

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.

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.

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.

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.

I believe the solution posted to the arXiv this morning by Marcus, Spielman, and Srivastava is correct. Apparently I am no longer able to accept answers, but if I could I would accept Jon's answer which cites this preprint. As Jon says, this is fantastic!

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.

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 < .999$$ 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.

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.