View source for Kadison–Singer problem

{{Short description|Unique extension of pure states in Hilbert spaces}}
In [[mathematics]], the '''Kadison–Singer problem''', posed in 1959, was a problem in [[functional analysis]] about whether certain extensions of certain [[linear functional]]s on certain [[C*-algebra]]s were unique. The uniqueness was proved 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]].<ref>{{cite journal|first1=R.|last1=Kadison|author1-link=Richard Kadison|first2= I.|last2=Singer|author2-link=Isadore Singer|title=Extensions of pure states|journal=[[American Journal of Mathematics]]|date=1959|volume=81|issue=2|pages=383–400|mr=0123922|doi=10.2307/2372748|jstor=2372748}}</ref> The problem was subsequently shown to be equivalent to numerous open problems in pure mathematics, applied mathematics, engineering and computer science.<ref name=det>{{cite book|last1=Casazza|first1= P. G.|last2= Fickus|first2= M.|last3= Tremain|first3= J. C.|last4= Weber|first4= E.|contribution=The Kadison–Singer problem in mathematics and engineering: a detailed account|series=Contemporary Mathematics|title=Operator theory, operator algebras, and applications|date=2006|volume=414|pages=299–355|arxiv=math/0510024|mr=2277219|doi=10.1090/conm/414/07820|publisher=American Mathematical Society|location=Providence, RI|isbn= 9780821839232}}</ref><ref name=con/> Kadison, Singer, and most later authors believed the statement to be false,<ref name=det/><ref name=con>{{cite arXiv|title=Consequences of the Marcus/Spielman/Stivastava solution to the Kadison–Singer Problem|first=Peter G.|last= Casazza|date=2015|eprint=1407.4768|class=math.FA}}</ref> but, in 2013, it was proven true by [[Adam Marcus (mathematician)|Adam Marcus]], [[Daniel Spielman]] and [[Nikhil Srivastava]],<ref>{{cite arXiv|last1=Marcus|first1= Adam|author1-link=Adam Marcus (mathematician)|last2=Spielman|first2= Daniel A.|author2-link=Daniel Spielman|last3=Srivastava|first3=Nikhil|author3-link=Nikhil Srivastava|year=2013|title=Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem|eprint=1306.3969|class=math.CO}}</ref> who received the 2014 [[George Pólya Prize|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.<ref name=disc>{{cite web|title=Discrepancy, Graphs, and the Kadison–Singer Problem|work=Windows on Theory|first=Nikhil|last=Srivastava|authorlink=Nikhil Srivastava|date=July 11, 2013|url=http://windowsontheory.org/2013/07/11/discrepancy-graphs-and-the-kadison-singer-conjecture-2/}}</ref>

==Original formulation==
Consider the [[Hilbert space#Separable spaces|separable Hilbert space]] [[Sequence space|ℓ<sup>2</sup>]] and two related C*-algebras: the algebra <math>B</math> of all [[bounded operator|continuous linear operators]] from ℓ<sup>2</sup> to ℓ<sup>2</sup>, and the algebra <math>D</math> of all diagonal continuous linear operators from ℓ<sup>2</sup> to ℓ<sup>2</sup>.

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

By the [[Hahn–Banach theorem]], any functional on <math>D</math> can be extended to <math>B</math>.  Kadison and Singer conjectured that, for the case of pure states, this extension is unique.  That is, the Kadison–Singer problem consisted in proving or disproving the following statement: 
:to every pure state <math>\varphi</math> on <math>D</math> there exists a unique state on <math>B</math> that extends <math>\varphi</math>.
This claim is in fact true.

==Paving conjecture reformulation==
The Kadison–Singer problem has a positive solution if and only if the following "paving conjecture" is true:<ref>{{cite journal|first=Joel|last=Anderson|title=Restrictions and representations of states on C∗-algebras|journal=[[Transactions of the American Mathematical Society]]|date=1979|volume=249|pages=303–329|mr=0525675|doi=10.2307/1998793|url=https://www.ams.org/tran/1979-249-02/S0002-9947-1979-0525675-1/|issue=2|jstor=1998793}}</ref>

:For every <math>\varepsilon>0</math> there exists a natural number <math>k</math> so that the following holds: for every <math>n</math> and every linear operator <math>T</math> on the <math>n</math>-dimensional Hilbert space <math>\mathbb{C}^n</math> with zeros on the diagonal there exists a partition of <math>\{1,\dots,n\}</math> into <math>k</math> sets <math>A_1,\dots, A_k</math> such that
::<math>\|P_{A_j} T P_{A_j}\| \le \varepsilon \|T\| \text{ for } j=1,\ldots,k.</math>

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

Note that in this statement, <math>k</math> may only depend on <math>\varepsilon</math>, not {{nowrap|on <math>n</math>.}}

==Equivalent discrepancy statement==
The following "[[discrepancy theory|discrepancy]]" statement, again equivalent to the Kadison–Singer problem because of previous work by Nik Weaver,<ref>{{cite journal|first=Nik|last=Weaver|title=The Kadison-Singer problem in discrepancy theory|journal=Discrete Mathematics|volume=278|pages=227–239|date=2004|doi=10.1016/S0012-365X(03)00253-X|issue=1–3|arxiv=math/0209078|s2cid=5304663 }}</ref> was proven by Marcus/Spielman/Srivastava using a technique of random polynomials:

:Suppose vectors <math>u_1,\ldots,u_m\in\mathbb{C}^d</math> are given with <math>\sum_{i=1}^m u_i u_i^* = I</math> (the <math>d\times d</math> identity matrix) and <math>\|u_i\|_2^2\le\delta</math> for {{nowrap|all <math>i</math>.}} Then there exists a partition of <math>\{1,\ldots,m\}</math> into two sets <math>S_1</math> and <math>S_2</math> such that 
::<math>\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.</math>

This statement implies the following:
:Suppose vectors <math>v_1,\ldots,v_m\in\mathbb{R}^d</math> are given with <math>\|v_i\|_2^2\le\alpha</math> for {{nowrap|all <math>i</math>}} and 
::<math>\sum_{i=1}^m \langle v_i,x\rangle^2 =1 \ \text{ for all }x\in\mathbb{R}^d \text{ with } \|x\|=1.</math>
:Then there exists a partition of <math>\{1,\ldots,m\}</math> into two sets <math>S_1</math> and <math>S_2</math> such that, for <math>j=1,2</math>:
::<math>\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\mathbb{R}^d \text{ with } \|x\|=1 .</math>

Here the "discrepancy" becomes visible when &alpha; 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 partitions of graphs.<ref name=disc/>

==References==
{{reflist}}

==External links==
*{{cite web|title=An introduction to the Kadison–Singer Problem and the Paving Conjecture|author=Nicholas J. A. Harvey|date=July 11, 2013|url=http://www.cs.ubc.ca/~nickhar/papers/KS/KS.pdf}}

{{DEFAULTSORT:Kadison-Singer problem}}
[[Category:Operator algebras]]
[[Category:Quantum mechanics]]
[[Category:Mathematical problems]]