卡迪森-辛格问题

先引入若干定义：

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

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

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

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

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

从${\displaystyle \ell ^{2}}$ 到${\displaystyle \ell ^{2}}$ 的对角连续线性算子集合。换言之，${\displaystyle 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\}}$ 。${\displaystyle D(\ell ^{2})}$ 包含于${\displaystyle B(\ell ^{2})}$ ，故为其子C*-代数。

态

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

纯态

接续上项，${\displaystyle \varphi }$ 称为纯态，意思是在${\displaystyle A}$ 上所有态组成的集合中，${\displaystyle \varphi }$ 是极端点（英语：Extreme point），即不能写成其他态的凸组合。

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

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

此命题已证为真。^[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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） （英语）.