The Kadison-Singer problem has a positive solution

Analysis 1 Minute

You need to know: Set {\mathbb C} of complex numbers, complex conjugate \bar{z} and absolute value |z| of z\in {\mathbb C}.

Background: Let {\mathbb C}^d be the set of vectors x=(x_1,\dots,x_d) with complex components x_i. Denote \langle x,y \rangle = \sum\limits_{i=1}^d x_i \bar{y_i} the inner product in {\mathbb C}^d. Let ||x||=\sqrt{\langle x,x \rangle} be the norm in {\mathbb C}^d. We say that u\in {\mathbb C}^d is a unit vector if ||u||=1.

The Theorem: On 17th June 2013, Adam Marcus, Daniel Spielman, and Nikhil Srivastava submitted to arxiv a paper in which they proved the following result. There exist universal constants \eta\geq 2 and \theta>0 so that the following holds. Let w_1,\dots,w_m \in {\mathbb C}^d satisfy ||w_i|| \leq 1 for all i and suppose \sum\limits_{i=1}^m |\langle u,w_i \rangle|^2=\eta for every unit vector u\in {\mathbb C}^d. Then there exists a partition S_1, S_2 of \{1,\dots,m\} so that \sum\limits_{i\in S_j} |\langle u,w_i \rangle|^2 \leq \eta - \theta, for every unit vector u\in {\mathbb C}^d and each j\in\{1,2\}.

Short context: The statement of the Theorem is one of many equivalent formulations of famous Kadison-Singer problem. In was posed in 1959 in the language of functional analysis. Later, it was discovered that numerous open problems in pure mathematics, applied mathematics, engineering and computer science are all equivalent to this problem. Hence, it was sufficient to solve one of these problems to solve them all. This is what the Theorem achieves!

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment