…while we keep discussing why mathematics is possible…
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
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 is the extension of some pure state of some maximal abelian algebra’ (where 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
Jean Bourgain and Lior Tzafriri considered the following scenario: Let be a real number. Let be a matrix with norm 1 and with zeroes on the diagonal. An by principal minor is “good” if the norm of is less than .
Consider the following hypergraph :
The vertices correspond to indices . A set belongs to if the sub-matrix of is good.
Bourgain and Tzafriri showed that for every there is so that for every matrix we can find so that .
Moreover, they showed that for every nonnegative weights there is so that the sum of the weights in is at least times the total weight. In other words, (by LP duality,) the vertices of the hypergraph can be fractionally covered by edges.
The “big question” is if there a real number so that for every matrix can be covered by good sets. Or, in other words, if the vertices of can be covered by 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.
KADISON-SINGER MEETS BOURGAIN-TZAFRIRI by PETER G. CASAZZA, ROMAN VERSHYNIN, The Kadison-Singer Problem in Mathematics and Engineering: A Detailed Account pdf, and many other recent publications by Pete Casazza.