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

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.

Additional references:

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.

Why is Mathematics Possible: Tim Gowers’s Take on the Matter

lnc math

In a previous post I mentioned the question of why is mathematics possible. Among the interesting comments to the post, here is a comment by Tim Gowers:

“Maybe the following would be a way of rephrasing your question. We know that undecidability results don’t show that mathematics is impossible, since we are interested in a tiny fraction of mathematical statements, and in practice only in a tiny fraction of possible proofs (roughly speaking, the comprehensible ones). But why is it that these two classes match up so well? Why is it that nice mathematical statements so often have proofs that are of the kind that we are able to discover?

Continue reading

Polymath8: Bounded Gaps Between Primes

Yitang Zhang’s very recent shocking paper demonstrated that bounded gaps between primes occur infinitely often, with the explicit upper bound of 70,000,000 given for this gap. Polymath8 was launched for the dual purpose of learning Zhang’s proof and improving the upper bound for the gaps. Here are links for three posts (I, II, III) on Terry Tao’s blog, a post on the secret blogging seminar,  and for a post on the polymath blog. And here is the table for the world records so far.

Updates: Record for June 16 – 60,744