卡迪森-辛格问题

数学上，卡迪森-辛格问题（英语：Kadison–Singer problem）于1959年提出，有关泛函分析，问某个特定C*-代数上的任意线性泛函，延拓到另一个较大的C*-代数时，是仅有唯一的可能，抑或可以有多个不同的延拓。2013年，问题得到解决，答案为肯定（即唯一）。

问题源出1940年代保罗·狄拉克对量子力学理论基础的研究。1959年，理查德·卡迪森与艾沙道尔·辛格给出严格的问题叙述。此后，发现纯数学、应用数学、工程学、电脑科学等学科的多个未解问题，皆与卡迪森-辛格问题等价。卡迪森、辛格，以及日后多个作者，都相信问题答案为否定（即不唯一），然而于2013年，亚当·马库斯、丹尼尔·斯皮尔曼、尼基·斯里瓦斯塔瓦合著论文给出肯定的答案。翌年，三人因此获SIAM颁发波利亚奖。

马-斯-斯三氏皆为电脑科学家，本来并非研究C*-代数。马库斯甚至称自己在解决该问题后，“仍无法用C*-代数的语言来描述它”。解决问题的转捩点，是乔尔·安德森（Joel Anderson）将其重写成不牵涉C*-代数理论的等价形式。安德森于1979年证明，其“铺砌猜想”（英语：paving conjecture）与卡迪森-辛格问题等价。该猜想仅牵涉有限维希尔伯特空间的算子，而相比之下，原问题的空间则是无穷维。此后，亦有其他学者，如尼克·威佛（Nik Weaver），在有限维空间中，给出其他等价问法。威佛的版本吸引了马-斯-斯三氏研究。而此版本用交织多项式族（英语：interlacing family）获解决。

原问题叙述

先引入若干定义：

${\boldsymbol {\ell }}^{2}$

平方可和的复序列空间，即$\ell ^{2}=\left\{(x_{1},x_{2},\ldots ):x_{i}\in \mathbb {C} ,\sum _{i}\left|x_{i}\right|^{2}<\infty \right\}$。此空间为可分希尔伯特空间，内积定义由$\langle x,y\rangle =\sum _{i}x_{i}{\overline {y_{i}}}$给出。

${\boldsymbol {B}}({\boldsymbol {\ell }}^{2})$

从$\ell ^{2}$到$\ell ^{2}$的连续线性算子组成的集合。此集合上，有加减法、乘法、伴随等运算，构成一个C*-代数。

${\boldsymbol {D}}({\boldsymbol {\ell }}^{2})$

从$\ell ^{2}$到$\ell ^{2}$的对角连续线性算子集合。换言之，$D(\ell ^{2})=\left\{\left.f:\ell ^{2}\to \ell ^{2}\right|f(x)=(a_{1}x_{1},a_{2}x_{2},\ldots ),{\text{ 其 中 }}a_{i}\in \mathbb {C} ,{\text{ 且 }}a_{i}{\text{ 有 界 }}\right\}$。$D(\ell ^{2})$包含于$B(\ell ^{2})$，故为其子C*-代数。

态

C*-代数$A$上的态，是连续线性泛函$\varphi :A\to \mathbb {C}$，将单位元$I$映到$1$，且对任意半正定的$T\geq 0$，有$\varphi (T)\geq 0$（即此时$\varphi (T)$要取实值，且该实值为非负）。

纯态

接续上项，$\varphi$称为纯态，意思是在$A$上所有态组成的集合中，$\varphi$是极端点，即不能写成其他态的凸组合。

由哈恩-巴拿赫定理，$D(\ell ^{2})$上的任意泛函，必能延拓到$B(\ell ^{2})$上。卡迪森与辛格二人问，对于纯态，此延拓是否唯一。所以，卡迪森-辛格问题是要证明或否证以下命题：

对$D(\ell ^{2})$上的任意纯态$\varphi$，$B(\ell ^{2})$上都存在唯一的态$\psi$，使$\psi$延拓$\varphi$，即两者限制到$D$时等同。

此命题已证为真。

铺砌猜想叙述

卡迪森-辛格问题的答案为肯定，当且仅当以下铺砌猜想为真：

对任意的$\varepsilon >0$，存在正整数$k$使得：对每个$n$，以及对$n$维希尔伯特空间$\mathbb {C} ^{n}$上的每个线性算子$T$（可视为$n\times n$方阵），若其对角线全零，则存在某种方法将$\{1,\dots ,n\}$分划为$k$份$A_{1},\dots ,A_{k}$，使得

$\|P_{A_{j}}TP_{A_{j}}\|\leq \varepsilon \|T\|$ 对于每个 $j=1,\ldots ,k$ 都成立。

此处$P_{A_{j}}$是正交投影，将$\mathbb {C} ^{n}$（坐标以$1,2,\ldots ,n$为下标）映到坐标仅以$A_{j}$元素为下标的子空间。换言之，$P_{A_{j}}TP_{A_{j}}$是下标为$A_{j}$元素的各行列，相交而得的子方阵。而矩阵范数$\|\cdot \|$取为谱范数，即来自$\mathbb {C} ^{n}$上欧氏范数的算子范数。

注意命题中，$k$只能与$\varepsilon$有关，但不取决于$n$。

偏差叙述

尼克·威佛（Nik Weaver）证明，以下“偏差理论”命题，同样与卡迪森-辛格问题（的肯定答案）等价：

设有向量$u_{1},\ldots ,u_{m}\in \mathbb {C} ^{d}$，满足$\sum _{i=1}^{m}u_{i}u_{i}^{*}=I$（$d\times d$单位方阵），且对每个$i$，$\|u_{i}\|_{2}^{2}\leq \delta$。则存在一种方法将$\{1,\ldots ,m\}$分划成两个子集$S_{1}$和$S_{2}$，使得对于$j=1,2$都有

$\left\|\sum _{i\in S_{j}}u_{i}u_{i}^{*}\right\|\leq {\frac {\left(1+{\sqrt {2\delta }}\right)^{2}}{2}}.$

马库斯、斯皮尔曼、斯里瓦斯塔瓦三人用交织多项式族（英语：interlacing families）的技巧，证明上述命题为真。该命题又有以下推论：

设向量$v_{1},\ldots ,v_{m}\in \mathbb {R} ^{d}$满足$\|v_{i}\|_{2}^{2}\leq \alpha$（对所有$i$），还有

$\sum _{i=1}^{m}\langle v_{i},x\rangle ^{2}=1$ 对满足$\|x\|=1$的所有向量$x\in \mathbb {R} ^{d}$成立。

则可以将$\{1,\ldots ,m\}$分划成两个子集$S_{1}$、$S_{2}$，使得对$j=1,2$，以及满足$\|x\|=1$的任意向量$x\in \mathbb {R} ^{d}$，皆有：

$\left|\sum _{i\in S_{j}}\langle v_{i},x\rangle ^{2}-{\frac {1}{2}}\right|\leq 5{\sqrt {\alpha }}.$

“偏差”一词的含义，在$\alpha$较小时显明：在单位球面上取值恒为$1$的二次型，可以分拆成两个大致相等的二次型，而分拆出来的二次型在单位球面上各处的取值，离$1/2$的偏差很小。利用命题此种形式，可以推导出关于图分划的若干结果。

外部链结

• Nicholas J. A. Harvey. An introduction to the Kadison–Singer Problem and the Paving Conjecture [卡迪森-辛格问题与铺砌猜想的介绍] (PDF). 2013-07-11 [2021-10-16]. （原始内容存档 (PDF)于2021-10-21） （英语）. 
• 陶哲轩. Real stable polynomials and the Kadison-Singer problem [实稳定多项式与卡迪森-辛格问题] (网志). 2013-11-04 [2021-10-16]. （原始内容存档于2022-01-19） （英语）.