### Another one bites the dust (actually many of them)

[Update January 2015: I see that many people reach this modest blog post in search of information about the solution of the Kadison-Singer conjecture, so I figured that it would be a good service to immediately direct them away to better sources:

There are two very recent papers that I have not read yet, but I trust:

The solution to the Kadison-Singer problem: Yet another presentation, by Dan Timotin (recommended to me by friends).

Consequences of the Marcus/Spielman/Srivastava solution of the Kadison-Singer problem, by P. Casazza and J. Tremain.

and there is Terry Tao’s post on this subject that I read and recommend.

Best regards, Orr]

Boom. In the arxiv mailing list of a few days ago appeared the following paper: “Interlacing Families II: Mixed Characteristic Polynomials and The Kadison-Singer Problem” (Markus, Spielman and Srivastava). The abstract says:

We use the method of interlacing families of polynomials to prove Weaver’s conjecture KS2, which is known to imply a positive solution to the Kadison-Singer problem via a projection paving conjecture of Akemann and Anderson. Our proof goes through an analysis of the largest roots of a family of polynomials that we call the “mixed characteristic polynomials” of a collection of matrices.

From the abstract it might not be immediately clear that this paper claims to solve the Kadison-Singer problem, because it says that their result implies KS via another conjecture; what they mean, however, is that the conjecture they prove was proven to be equivalent to another conjecture which has already been shown in the past to be equivalent to a positive solution to the Kadison-Singer problem.

Blog posts on the solution appeared here and here, with links to excellent references. I will add here a few remarks of my own.

The Kadison-Singer problem (KS) was raised by Richard Kadison and Isadore Singer in 1959 (!!). Here is what the problem is (taken from this paper by Casazza, Fickus, Tremian and Weber).

Kadison-Singer Problem (KS). Does every pure state on the algebra $\mathbb{D}$ of bounded diagonal operators on $\ell^2$ have a unique extension to a (pure) state on $B(\ell^2)$, the (algebra of all bounded linear operators on the Hilbert space $\ell^2$?

It has been shown to be equivalent to many other problems, some of them appearing quite different from the original problem, and some of them of interest in engineering (see the above link to the paper by Casazza et. al. By the way, see the introduction of that paper at least to see why the problem was raised – that is also very interesting).

I was very surprised to read about this solution. First, it is always surprising to hear about the solution of a long-standing open problem. But that is not the main reason (I was not surprised that it was a rather combinatorial formulation of the problem that was solved, that was not surprising at all).

I first heard about KS in a beautiful talk by Pete Casazza in Great Plains Operator Symposium (GPOTS) that took place in Cincinnati in 2008 (that was also when I first heard about Pete Casazza). During his talk, Casazza made a point that Kadison and Singer were very clever in that they did not conjecture that KS is true. So it is best referred to as the Kadison-Singer problem. I also got the feeling that Casazza believed that a counter example to one of the problems would eventually be found (but perhaps he was just being safely pessimistic). In any case, on page 3 of this paper (same one as above) Casazza et. al. say that Kadison and Singer themselves thought that this problem has a negative answer (but were careful enough not to make a conjecture).

So that is why I was really surprised to see the solution, and what makes it quite an exciting development. The problem itself now seems more interesting. It seems worthwhile now to study these papers (and Weaver’s paper), for two reasons. First, since there are many problems that are now solved at the proce of one, the results themselves might be useful. Second, it seems to me that the techniques themselves could be worth knowing, even for someone working in operator theory or operator algebras.

3. Their main result, from which they very easily (yet cleverly) derive Weaver’s result, is as follows: Given $\epsilon>0$ and $v_1, \ldots, v_n$ random (column) vectors in $\mathbb{C}^d$ (with finite support) such that the expected value of $\sum v_i v_i^*$ is the identity and the expected value of $\|v_i\|^2$ is less than $\epsilon$, then there is a positive probability that $\|\sum_i v_i v_i^*\|^2 \leq 1+ \sqrt{\epsilon}$. That looks quite obvious, at least for an inexperienced by-stander like me. I looked at that and it took me a few moments to understand: why is that not trivial?