### 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 of bounded diagonal operators on have a unique extension to a (pure) state on , the (algebra of all bounded linear operators on the Hilbert space ?

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.

- 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).
- 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.
- Their main result, from which they very easily (yet cleverly) derive Weaver’s result, is as follows:
*Given and random (column) vectors in (with finite support) such that the expected value of is the identity and the expected value of is less than , then there is a positive probability that .*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?* - 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. - 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.
- Markus, Spielman and Srivastava have taken down an open problem, but they kindly close their paper with another conjecture and questions.
- 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.
- 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.
- 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.
- To summarize, this looks like a very nice celebration of the Unity of Mathematics.

[…] Orr Shallit has also picked up on this, and offers some thoughts from the perspective of an operator algebraist/operator theorist. […]

[…] of quantum mechanics is in this post in Bryan Roberts‘ blog Soul Physics. Here is a very nice post on the mathematics of the conjecture with ten interesting comments on the proof by Orr Shalit, and […]

[…] June 2013. Orr Shalit at Noncommutative Analysis some very nice comments on the proof of the K-S […]

Kadison and Singer (1959) write: “The results that we have obtained leave the question of uniqueness of an extension of the singular pure states of [a discrete maximal abelian subalgebra] $A_d$ open. We incline to the view that such an extension is non-unique.”

They’re certainly within epsilon of conjecturing that the K-S statement is false! But perhaps “inclining toward” falls just short of “conjecturing” when the mathematician says it. At any rate, it’s not so surprising that they would have said this, after having just shown that when $A_c$ is a continuous maximal abelian subalgebra, such extensions can indeed be non-unique!

K&S 1959: http://www.jstor.org/stable/10.2307/2372748

Thanks for bringing the precise statement. I completely disagree!

Most mathematicians I know always have some inclination one way or another when working on a problem. Sometimes, to themselves, they call such inclination a “conjecture”, but making an official conjecture in press is something that they would be very careful making, and would have very solid reasons (such as evidence, or strong heuristics).

I never met Singer, but I bet that if Kadison were to make a conjecture (for example that KS is false) there would be no doubt that he is making a conjecture.

P.S. – That was a very interesting post you wrote on KS.

Thanks. And point taken. One does often use “inclination” to describe how one would attack a problem, as opposed to a belief in its truth or falsity.

http://www.siam.org/prizes/sponsored/polya.php

[…] the post I put up soon after appearance of the paper I wrote (referring to the new proof of KS2) that […]

[…] Para os iniciados, o problema e a solução estão bem explicados aqui (está em inglês). […]

[…] Piece by piece, the researchers developed a new technique for working with so-called “interlacing polynomials” to capture this underlying structure, and finally, on June 17, 2013, Marcus sent an email to Weaver, who had been his undergraduate advisor at Washington University 10 years earlier. “I hope you remember me,” Marcus wrote. “The reason I am writing is because we … think we have solved your conjecture (the one that you showed was equivalent to Kadison-Singer).” Within days, news of the team’s achievement had spread across the blogosphere. […]

[…] Piece by piece, the researchers developed a new technique for working with so-called “interlacing polynomials” to capture this underlying structure, and finally, on June 17, 2013, Marcus sent an email to Weaver, who had been his undergraduate advisor at Washington University 10 years earlier. “I hope you remember me,” Marcus wrote. “The reason I am writing is because we … think we have solved your conjecture (the one that you showed was equivalent to Kadison-Singer).” Within days, news of the team’s achievement had spread across the blogosphere. […]

Reblogged this on Artificial Intelligence Research Blog.