The Kadison-Singer Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava

…while we keep discussing why mathematics is possible…

The news

Adam Marcus, Dan Spielman, and Nikhil Srivastava posted a paper entitled “Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem,” where they prove the 1959 Kadison-Singer conjecture.

(We discussed part I of “interlacing families” in this post about new Ramanujan graphs.  Looks like a nice series.)

The Kadison-Singer conjecture refers to a positive answer to a question posed by Kadison and Singer: “They asked ‘whether or not each pure state of $\cal B$ is the extension of some pure state of some maximal abelian algebra’ (where $\cal B$ is the collection of bounded linear transformations on a Hilbert space.”) I heard about this question in a different formulation known as the “Bourgain-Tzafriri conjecture” (I will state it below) and the paper addresses a related well known discrepancy formulation by Weaver. (See also Weaver’s comment on the appropriate “quantum” formulation of the conjecture.)

Updates: A very nice post on the relation of the Kadison-Singer Conjecture  to foundation 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 another nice post on Yemon Choi’s blog and how could I miss the very nice post on James Lee’s blog.. Nov 4, 2013: A new post with essentially the whole proof appeared on Terry tao’s blog, Real stable polynomials and the Kadison Singer Problem.

Update: A very nice blog post on the new result was written by  Nikhil Srivastava on “Windows on theory.” It emphasizes the discrapancy-theoretic nature of the new result, and explains the application for partitioning graphs into expanders.

The Bourgain-Tzafriri theorem and conjecture

Let me tell again (see this post about Lior, Michael, and Aryeh where I told it first) about a theorem of Bourgain and Tzafriri related to the Kadison-Singer conjecture.

Jean Bourgain and Lior Tzafriri considered the following scenario: Let $a > 0$ be a real number. Let $A$ be a $n \times n$ matrix with norm 1 and with zeroes on the diagonal. An $s$ by $s$ principal minor $M$ is “good” if the norm of $M$ is less than $a$.

Consider the following hypergraph $F$:

The vertices correspond to indices ${}[n]=\{1,2,\dots,n\}$. A set $S \subset [n]$ belongs to $F$ if the $S \times S$ sub-matrix of $M$ is good.

Bourgain and Tzafriri showed that for every $a > 0$ there is $C(a) > 0$ so that for every matrix $A$ we can find $S \in F$ so that $|S| \ge C(a)n$.

Moreover, they showed that for every nonnegative weights $w_1,w_2,\dots w_n$ there is $S \in F$ so that the sum of the weights in $S$ is at least $C(a)$ times the total weight. In other words, (by LP duality,) the vertices of the hypergraph can be fractionally covered by $C(a)$ edges.

The “big question” is if there a real number $C'(a) > 0$ so that for every matrix $M,$ ${}[n]$ can be covered by $C'(a)$ good sets. Or, in other words, if the vertices of $F$ can be covered by $C'(a)$ edges. This question is known to be equivalent to an old conjecture by Kadison and Singer (it is also known as the “paving conjecture”). In view of what was already proved by Bourgain and Tzafriri what is needed is to show that the covering number is bounded from above by a function of the fractional covering number. So if you wish, the Kadison-Singer conjecture had become a statement about bounded integrality gap. Before proving the full result, Marcus, Spielman and Srivastava gave a new proof of the Bourgain-Tzafriti theorem.