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

Posted on June 19, 2013 by Gil Kalai

…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.

Update (Nov 29, 2015):  Erica Klarreich wrote a very nice article about it on Quanta Magazine  ‘Outsiders’ Crack 50-Year-Old Math Problem,  and here is a link to a SIAM news article, Kadison–Singer Problem Solved By Dana Mackenzie.

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.

This entry was posted in Analysis, Computer Science and Optimization, Physics, Updates and tagged , , , , , . Bookmark the permalink.

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

  1. Sanjay Gupta says:
    June 20, 2013 at 1:19 am

    I don’t understand the statement of Conjecture 1.1 of the MSS paper you have linked. Is it not true that \sum_{i=1}^{m} | |^2 = |k|^2 \eta ???

    Reply
  2. Sanjay Gupta says:
    June 20, 2013 at 1:23 am

    Aargh latex! Try again \sum_{i=1}^{m} | |^2 = |k|^2 \eta . i.e. how could equation (1) hold for all vectors u \in C^d.

    Reply
  3. Sanjay Gupta says:
    June 20, 2013 at 1:27 am

    Only example I can think of is trivial: w_i = 0 and \eta = 0.

    Reply
    • Orr Shalit says:
      June 20, 2013 at 7:14 am

      If \{w_1, \ldots, w_n\} is the union of two orthonormal bases, and \eta = 2, then (1) holds, and (2) works with \epsilon = 1.
      BTW there is a tiny typo in Conjecture 1.1 of the paper (maybe that confused you), m should be n.

      Reply

  4. Pingback: Another one bites the dust (actually many of them) | Noncommutative Analysis

  5. Leonid Gurvits says:
    June 20, 2013 at 2:56 pm

    Great achievement and very clear exposition! Roughly, the main approach, which will certainly produce many more cool results and PROOFS, can be summarized as follows: associate with
    a stability preserving operation OPER, possibly from some restricted class, a functional F(p) on polynomials such that there is
    a bound F(OPER(p)) \geq Const(…)F(p) and iterate this bound over the products of those preservers.
    The main problem to overcome: this functional F should be close(or better equal)
    on “small” degree polynomials to the thing you are really interested in. If all this done then
    an easy induction proof results. When I was dealing with the Van Der Waerden- Schrijver
    like inequalities, the preservers are partial differentiations with zeroing and the best functional happened to be what I called the capacity. Actually,
    the capacity is essentially a measure of stability. But I understood this fact after coming up with the
    idea. Interestingly, the capacity was suggested by the (numerical) approach in STOC-2000 paper
    with Alex Samorodnitsky(itself motivated by two Technion’s papers on the SCALING: Nemirovski-Rothblum and David London). The functional in MSS paper is what they call “Barrier Function”, in a way a “numerical’
    thing as well. I envision many more algorithmic applications of the approach as well. An interesting
    extension, barely touched, is to go beyond stable polynomials. For instance, the Mixed Discriminant
    is related to a nice stable polynomial(the determinant) but the Mixed Volume is not. I did some
    work in this direction in http://arxiv.org/abs/0812.3687(with CONJECTURES!) and http://arxiv.org/abs/cs/0702013.
    Gil, your blog and https://www.facebook.com/ellina.gurvits?fref=ts are my main two WEB favorites.
    Toda Roba!

    Reply

  6. Pingback: Kadison-Singer: solved? | Since it is not ...

  7. Pingback: Philosophy and Physics in the Kadison-Singer Conjecture | Soul Physics

  8. Anonymous says:
    June 21, 2013 at 9:50 am

    It is worth point out that, not only did they solve the Weaver’s conjecture, but they solve it with optimal parameters (up to constants).

    Of course, the fact that they have two sets in Corollary 1.3 (i.e. r=2) is optimal, and the bound of 1/2 + O(sqrt(alpha)) that they achieve in equation (5) is also optimal, as is shown in Section 3 of Weaver’s paper.

    Reply
  9. Nik Weaver says:
    June 26, 2013 at 8:25 am

    Gil, the statement of the original form of Kadison-Singer is a bit garbled. It should be: every pure state on an atomic maximal abelian subalgebra of B(H) has a unique extension to a pure state on B(H).

    Also, +1 to Anonymous for the comment about optimal parameters. Indeed, this is the best we could have hoped for!

    Reply

  10. Pingback: An introduction to interlacing families | Short, Fat Matrices

  11. Pingback: What does Kadison-Singer have to do with Quantum Mechanics? | tcs math - some mathematics of theoretical computer science

  12. Pingback: Not mentioned recently on The Aperiodical | The Aperiodical

  13. Leonid Gurvits says:
    July 18, 2013 at 12:44 am

    Tip my hat, again, to Adam,Dan and Nikhil! Let me stress why their proof looks so magically effortless and why some many experts failed before: the proof is not (random) matrix theoretic: matrices disappeared after the first application of the elementary first order differential operator,
    but the proved Lax Conjecture(a hermitian solution due to Boris Dubrovin(1983) is sufficient)
    allows to use (simple) matrix stuff to prove the needed convexity and monotonicity.
    A similar observation applies to the comparison of A. Schrijver’s and mine proofs(no Lax though!,
    but it was used in the earlier attempt http://arxiv.org/abs/math/0404474 and in STOC-2006 version).
    On the other hand, in the context of the permanent, Lex proved much more in his paper
    http://homepages.cwi.nl/~lex/files/countpms2.pdf and it has been heavily used in
    http://arxiv.org/abs/1106.2844 to nail finally down Friedland’s conjecture on the monomer-dimer entropy(about the coefficients of the matching polynomial!).

    I was thinking about possible extensions and generalizations. Of course, one natural question,
    related to the description of maximizers is MSS paper, is to incorporate the ranks of A_i to
    the (main) bound of Theorem 5.1. It looks like this body of work, starting with sparsifiers,
    can be applied to an approximation of homogeneous real-stable polynomials, at least
    multilinear ones, by polynomials with “few” variables. I noticed that the monotonicity/convexity
    (Lemma 5.7) really needs just log-concavity, at least in one variable: take any log-concave function
    F(t) that is
    positive on [a, \infty) together with derivatives up to the third order. Then the ratio (F^{(1)}(t)/F(t))
    is decreasing and convex on [a, \infty). With that in mind, I wonder about possible generalization
    of the main (balancing) result of MSS to the Minkowski sums (aka zonotopes) of vector intervals \{a X_i: |a| \leq 1, X_i \in R^n\}. Of course, one will need to deal with mixed volumes instead of mixed discriminants,
    the luxury of real roots and interlacing is gone, there are no known proved analogues of the Lax
    conjectures…yet the Van der Waerden like bound was proved by an induction based
    on the multiple partial differentiations.

    Reply
    • Gil Kalai says:
      July 26, 2013 at 9:08 am

      Dear Leonid, this is very interesting. What is the generalization of MSS’s result to zonotopes you have in mind?

      Reply
      • Leonid Gurvits says:
        July 27, 2013 at 9:23 pm

        Dear Gil, roughly something of the kind:
        Consider m symmetric vector intervals [X_1],...,[X_m] and the Minkowski(volume) polynomial
        Vol(y_1[X_1]+...+y_m[X_m]). Let \beta be the maximum coordinate of the gradient of
        the logarithm of the volume polynomial \log(Vol)
        at (1,…,1). Then there exists a partition (1,2,…,m) = A \cap B such that
        \sum_{i \in A}[X_i] \subset (.5 + O(\sqrt{\beta}) \sum_{1 \leq j \leq m}[X_j]
        and \sum_{i \in B}[X_i] \subset (.5 + O(\sqrt{\beta}) \sum_{1 \leq j \leq m}[X_j].

        Needless to say, it is a very preliminary statement. Can be easily rephrased in terms of
        sums of support functions.

      • Gil Kalai says:
        July 28, 2013 at 12:46 am

        Dear Leonid, That’s very interesting! On another matter you might be interested in the recent added comments at the end of my old post on BosonSamplin. It looks that Gaussian permanents, and perhaps even general outcomes of Boson machines are very noise-sensitive in the sense of Benjamini, Schramm and me. It would be nice to prove a general theorem of this kind (for permanents it is easy), and relate it to classical simulability perhaps via your old results on Boson machines.

  14. Leonid Gurvits says:
    July 28, 2013 at 7:24 pm

    Dear Gil, thanks for the pointers on noise-sensitivities. I am not very familiar with this line of research. Yet, it the context of bosons I made this observation: quantum optical distributions
    are much worse concentrated than their classical approximations. To be more precise:
    consider a square complex $ n \times n$ unitary matrix $U$ and associate with it two homogeneous
    polynomials with non-negative coefficients:
    (quantum) Q(x_1,…,x_n) = Per(UDiag(x_1,…,x_n)U^{*});
    (classical) C(x_1,…,x_n) = \prod_{1 \leq i \leq n} ( \sum_{1 \leq j \leq n} |U(i,j|^2 x_j).
    The sum of coefficients of both of them is 1. So they both give some prob. distributions
    on integer vectors \{(r_1,…,r_n): r_1+…+r_n = n \}. Moreover, both random vectors have the same
    mean, namely $(1,1,…,1)$.

    Now, the coefficients of Q satisfy the
    upper bound $q_{r_1,…,r_n} \leq \prod_{1 \leq i \leq n} \frac{r_i !}{r_i^{r_i}};
    and the coefficients of C satisfy much smaller upper bound
    $c_{r_1,…,r_n} \leq \prod_{1 \leq i \leq n} \frac{1}{r_i^{r_i}}, which is due to the simple inequality
    $C(x_1,…,x_n) \leq n^{-n}(x_1+….+x_n)^n$. I do conjecture that in general
    $q_{r_1,…,r_n} \leq (\prod_{1 \leq i \leq n} r_i ! ) c_{r_1,…,r_n}$.

    Both bounds are sharp. Also, the distribution of $C$ can be exactly efficiently classically simulated,
    even though the individual probabilities are the permanents.

    Actually, the polynomial $C$ is log-concave(even stable, like those in MSS paper) on the positive orthant and Q is not.

    Best, Leonid.

    Reply
  15. Leonid Gurvits says:
    August 11, 2013 at 10:50 pm

    Dear Gil, it occurred to me that there is a connection between boson sampling and Kadison-Singer Problem:
    Consider linear quantum optical distribution for $n$ bosons and $m$ detectors given by $n \times m$ “unitary” matrix $U$, i.e. $UU^{*} = I$. Let $v$ be the maximum $l_2$ norm of columns of $U$.
    Let $Pr(S)$ be the probability that all bosons observed by the detectors from the subset $S$.
    Then there exists a partition of detectors into two sets $[1,.,.,m] = S \cup T$ such that
    $(.5)^n(1 – const v)^{n} \leq Pr(S) \leq (.5)^n(1 + const v)^{n}$ and
    $(.5)^n(1 – const v)^{n} \leq Pr(T) \leq (.5)^n(1 + const v)^{n}$, where $const$ is some universal constant.

    Perhaps there is a direct way to prove this, i.e. without using MSS paper.

    Best, Leonid.

    Reply
  16. Abdulrahman Oladiipupo Ibraheem says:
    November 4, 2013 at 2:27 pm

    Dan Spielman is gifted!

    Reply
  18. Oren Kolman says:
    August 26, 2014 at 9:57 pm

    Nik Weaver and Charles Akemann mention that “it seems likely that the statement ‘‘every pure
    state on B(H) restricts to a pure state on some atomic masa’’ is also consistent with standard set theory.” Has there been progress on this since 2008? Is anything known, e.g. under an appropriate forcing axiom? Or has CH been eliminated from the proof?

    Reply
  19. Oren Kolman says:
    August 28, 2014 at 2:25 am

    A query more than anything else…

    Charles Akemann and Nik Weaver note in their 2008 PNAS paper that confirmation of the Kadison-Singer conjecture implies (S1) and (S2) are equivalent. The statement (S1) is that ‘‘every pure state on $\mathcal{B}(H)$ restricts to a pure state on some atomic masa’’, and (S2) is Anderson’s conjecture that every pure state on $\mathcal{B}(H)$ is diagonalizable, that is, of the form $f(A) =lim_{U}\langle Ae_{n}, e_{n}\rangle$ for some orthonormal basis $(e_{n})$ and some ultrafilter $U$ over $\mathbf{N}$. Prior to showing that the Continuum Hypothesis (CH) refutes (S1), they remark: “It seems likely that the statement ‘‘every pure state on $\mathcal{B}(H)$ restricts to a pure state on some atomic masa’’ is also consistent with standard set theory.”

    Has there been any further progress on whether (S1) (and hence now (S2)) is relatively consistent with ZFC, e.g. under a forcing axiom? Or has CH been eliminated or weakened?

    Reply

  20. Pingback: Thanks for Additivity | Gödel's Lost Letter and P=NP

  21. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem | Top News

  22. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem | BTS

  23. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem – Hacker Planet

  24. Pingback: Engadget Today » ‘Outsiders’ Crack a 50-Year-Old Math Problem

  25. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem | Hacker Spot

  26. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem | Wiki News Tech | Tech Hub For Techgig

  27. Pingback: 'Outsiders' Crack 50-Year-Old Math Problem | Daily Hackers News

  28. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem | Gadgetleader

  29. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem | News

  30. Pingback: Thanks for Additivity | TRIFORCE STUDIO

  31. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem – qwe

  32. Pingback: ‘Outsiders’ Crack a 50-Year-Old Math Problem – BRING THE NEWS

  33. Pingback: Solvig Kadison-Singer Problem - Skeptic Society

  34. Pingback: Pc Scientists Resolve Kadison-Singer Thunder | Quanta Magazine | A1A

  35. Pingback: Computer Scientists Solve Kadison-Singer Tell | Quanta Journal – Startupon.net

  36. Pingback: Computer Scientists Solve Kadison-Singer Problem | Quanta Magazine | Digitators

  37. Buddy Freund says:
    February 5, 2018 at 10:49 pm

    Numerous colleges and universities are designed some entrance tests for explicit
    topics to allow students to be certified for admission in preferential applications https://math-problem-solver.com/ .
    Calculus introduces two elementary ideas which enable us to explain and examine functions.

    Reply

Leave a comment