Another one bites the dust (actually many of them)

by Orr Shalit

[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

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.

Added on June 21: I now read the paper and I want to make some additional comments.

  1. On the one had, the proof looks completely magical to me. On the other the paper is read-able! (I mean to plain humans like me) There are some facts they use which I took on faith, but these facts are carefully listed before they start the proof, with references given. These facts are all “elementary” (you know what I mean).
  2. The main result (Theorem 1.2) they prove is itself “elementary”, meaning that I or anybody else  (any 3rd year math major) can understand what it says. That of course does not counter the fact that it required much ingenuity and experience from the authors to prove it, and also to realize that this main result would prove Weaver’s conjecture.
  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?
  4. On the other hand, the conjecture of Weaver (Conjecture 1.1 in their paper) which they derive made me think: why should that be true? Even more so, the Feichtinger conjecture, to which all of these results are equivalent, is also something that seems too good to be true.
  5. All in all, this paper proves Weaver’s version of the conjecture. To understand why Weaver’s conjecture implies KS it might be best to consult this paper of Casazza, Fickus, Tremain and Weber.
  6. Markus, Spielman and Srivastava have taken down an open problem, but they kindly close their paper with another conjecture and questions.
  7. Contrary to what I hopefully wrote above, there is no chance I will be able to do something with their techniques. There is a very big difference between somehow following a proof, and actually understanding how the techniques work and where to apply them. Obviously, this cannot be done after one quick read, but it seems like it is not worthwhile for me to invest time in trying to master this further.
  8. On the other hand, there is still some hope in me that the result, say the Feichtinger conjecture, will prove useful in some new application in Hilbert space theory.
  9. I was quite surprised and happy to see a paper of Helton and Vinnikov mentioned in the paper (a techniques from a paper of theirs were used in a paper which the authors cite). Victor Vinnikov is my friend, colleague, and next door neighbor here at BGU and was surprised at tea yesterday when I told him about this new paper.
  10. To summarize, this looks like a very nice celebration of the Unity of Mathematics.