Kadison–Singer problem

In mathematics, the Kadison–Singer problem, posed in 1959, was a problem in functional analysis about whether certain extensions of certain linear functionals on certain C*-algebras were unique. The statement was proven in 2013.

The statement arose from work on the foundations of quantum mechanics done by Paul Dirac in the 1940s and was formalized in 1959 by Richard Kadison and Isadore Singer.^[1] The problem was subsequently shown to be equivalent to numerous open problems in pure mathematics, applied mathematics, engineering and computer science.^[2][3] Kadison/Singer and most later authors believed the statement to be false,^[2][3] but in 2013 it was proven true by Adam Marcus, Daniel Spielman and Nikhil Srivastava,^[4] who received the 2014 Pólya Prize for the achievement.

The solution was made possible by a reformulation provided by Joel Anderson, who showed in 1979 that his "paving conjecture", which only involves operators on finite-dimensional Hilbert spaces, is equivalent to the Kadison–Singer problem. Nik Weaver provided another reformulation in a finite-dimensional setting, and this version was proved true using random polynomials.^[5]

Original formulation

Consider the separable Hilbert space ℓ² and two related C*-algebras: the algebra $B$ of all continuous linear operators from ℓ² to ℓ², and the algebra $D$ of all diagonal continuous linear operators from ℓ² to ℓ².

A state on a C*-algebra $A$ is a continuous linear functional $\varphi:A\to \Bbb{C}$ such that $\varphi(I)=1$ (where $I$ denotes the algebra's multiplicative identity) and $\varphi(T)\ge 0$ for every $T\ge 0$. Such a state is called pure if it is an extremal point in the set of all states on $A$ (i.e. if it cannot be written as a convex combination of other states on $A$.

The Kadison–Singer problem consists in proving or disproving the following statement:

to every pure state $\varphi$ on $D$ there exists a unique state on $B$ that extends $\varphi$.

We now know that this is true.

Paving conjecture reformulation

The Kadison–Singer problem has a positive solution if and only if the following "paving conjecture" is true:^[6]

For every $\epsilon>0$ there exists a natural number $k$ so that the following holds: for every $n$ and every linear operator $T$ on the $n$-dimensional Hilbert space $\Bbb{C}^n$ with zeros on the diagonal there exists a partition of $\{1,\dots,n\}$ into $k$ sets $A_1,\dots A_k$ such that

$\|P_{A_j} T P_{A_j}\| \le \epsilon \|T\| \ \ \text{for all } j=1,\ldots,k.$

Here $P_{A_j}$ denotes the orthogonal projection on the space spanned by the standard unit vectors corresponding to the elements of $A_j$, so that the matrix of $P_{A_j} T P_{A_j}$ is obtained from the matrix of $T$ by replacing all rows and columns that don't correspond to the indices in $A_j$ by 0. The matrix norm $\|.\|$ is the spectral norm, i.e. the operator norm with respect to the Euclidean norm on $\Bbb{C}^n$.

Note that in this statement, $k$ may only depend on $\epsilon$, not on $n$.

Equivalent discrepancy statement

The following "discrepancy" statement, again equivalent to the Kadison–Singer problem because of previous work by Nik Weaver,^[7] was proven by Marcus/Spielman/Srivastava using a technique of random polynomials:

Suppose vectors $u_1,\ldots,u_m\in\Bbb{C}^d$ are given with $\sum_{i=1}^m u_i u_i^* = I$ (the $d\times d$ identity matrix) and $\|u_i\|_2^2\le\delta$ for all $i$. Then there exists a partition of $\{1,\ldots,m\}$ into two sets $S_1$ and $S_2$ such that

$\left\|\sum_{i\in S_j} u_i u_i^*\right\|\le \frac{\left(1+\sqrt{2\delta}\right)^2}{2} \text{ for }j=1,2.$

This statement implies the following:

Suppose vectors $v_1,\ldots,v_m\in\Bbb{R}^d$ are given with $\|v_i\|_2^2\le\alpha$ for all $i$ and

$\sum_{i=1}^m \langle v_i,x\rangle^2 =1 \ \text{ for all }x\in\Bbb{R}^d \text{ with } \|x\|=1.$

Then there exists a partition of $\{1,\ldots,m\}$ into two sets $S_1$ and $S_2$ such that, for $j=1,2$:

$\left|\sum_{i\in S_j} \langle v_i,x\rangle^2 -\frac{1}{2}\right|\le 5\sqrt{\alpha} \ \text{ for all } x\in\Bbb{R}^d \text{ with } \|x\|=1 .$

Here the "discrepancy" becomes visible when α is small enough: the quadratic form on the unit sphere can be split into two roughly equal pieces, i.e. pieces whose values don't differ much from 1/2 on the unit sphere. In this form, the theorem can be used to derive statements about certain partition of graphs.^[5]

References

1. Kadison, R.; Singer, I. (1959). "Extensions of pure states". American Journal of Mathematics (81): 383–400. doi:10.2307/2372748. MR 0123922.
2. Casazza, P. G.; Fickus, M.; Tremain, J. C.; Weber, E. (2006). "The Kadison–Singer problem in mathematics and engineering: a detailed account". Operator theory, operator algebras, and applications. Contemporary Mathematics 414. Providence, RI: American Mathematical Society. pp. 299–355. arXiv:math/0510024. doi:10.1090/conm/414/07820. MR 2277219.
3. Casazza, Peter G. (2015). "Consequences of the Marcus/Spielman/Stivastava solution to the Kadison–Singer Problem". arXiv:1306.3969 [math.CO].
4. Marcus, Adam; Spielman, Daniel A.; Srivastava, Nikhil (2013). "Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem". arXiv:1306.3969 [math.CO].
5. Srivastava, Nikhil (July 11, 2013). "Discrepancy, Graphs, and the Kadison–Singer Problem". Windows on Theory.
6. Anderson, Joel (1979). "Restrictions and representations of states on C∗-algebras". Transactions of the American Mathematical Society (249): 303–329. doi:10.2307/1998793. MR 0525675.
7. Weaver, Nik (2004). "The Kadison-Singer problem in discrepancy theory". Discrete Mathematics (278): 227–239.

External links

• Nicholas J. A. Harvey (July 11, 2013). "An introduction to the Kadison–Singer Problem and the Paving Conjecture" (PDF).