Kadison–Singer problem

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 φ : A → C such that φ ( I ) = 1 (where I denotes the algebra's multiplicative identity) and φ ( T ) ≥ 0 for every T ≥ 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 φ on D there exists a unique state on B that extends φ .

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:

For every ϵ > 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 C n with zeros on the diagonal there exists a partition of { 1 , … , n } into k sets A 1 , … A k such that ∥ P A j T P A j ∥ ≤ ϵ ∥ T ∥     for all  j = 1 , … , 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 C n .

Note that in this statement, k may only depend on ϵ , not on n .

Equivalent discrepancy statement

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

Suppose vectors u 1 , … , u m ∈ C d are given with ∑ i = 1 m u i u i ∗ = I (the d × d identity matrix) and ∥ u i ∥ 2 2 ≤ δ for all i . Then there exists a partition of { 1 , … , m } into two sets S 1 and S 2 such that ∥ ∑ i ∈ S j u i u i ∗ ∥ ≤ ( 1 + 2 δ ) 2 2  for  j = 1 , 2.

This statement implies the following:

Suppose vectors v 1 , … , v m ∈ R d are given with ∥ v i ∥ 2 2 ≤ α for all i and ∑ i = 1 m ⟨ v i , x ⟩ 2 = 1    for all  x ∈ R d  with  ∥ x ∥ = 1. Then there exists a partition of { 1 , … , m } into two sets S 1 and S 2 such that, for j = 1 , 2 : | ∑ i ∈ S j ⟨ v i , x ⟩ 2 − 1 2 | ≤ 5 α    for all  x ∈ R d  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.