卡迪森-辛格问题

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

问题源出1940年代保罗·狄拉克对量子力学理论基础的研究。1959年，理查德·卡迪森（英语：Richard Kadison）与艾沙道尔·辛格给出严格的问题叙述。此后，发现纯数学、应用数学、工程学、计算机科学等学科的多个未解问题，皆与卡迪森-辛格问题等价。卡迪森、辛格，以及日后多个作者，都相信问题答案为否定（即不唯一），然而于2013年，亚当·马库斯（英语：Adam Marcus (mathematician)）、丹尼尔·斯皮尔曼（英语：Daniel Spielman）、尼基·斯里瓦斯塔瓦（英语：Nikhil Srivastava）合著论文给出肯定的答案。翌年，三人因此获SIAM（英语：Society for Industrial and Applied Mathematics）颁发波利亚奖（英语：George Pólya Prize）。

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

先引入若干定义：

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

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

此命题已证为真。

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

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

此处${\displaystyle P_{A_j}}$是正交投影，将${\displaystyle {\mathbb{C}}^n}$（坐标以${\displaystyle 1,2,\dots <!--\; \dots \; -->,n}$为下标）映到坐标仅以${\displaystyle A_j}$元素为下标的子空间。换言之，${\displaystyle P_{A_j}T{P}_{A_j}}$是下标为${\displaystyle A_j}$元素的各行列，相交而得的子方阵。而矩阵范数${\displaystyle \Vert <!--\; \Vert \; -->\cdot <!--\; \cdot \; -->\Vert <!--\; \Vert \; -->}$取为谱范数，即来自${\displaystyle {\mathbb{C}}^n}$上欧氏范数的算子范数。

注意命题中，${\displaystyle k}$只能与${\displaystyle \mathrm{\epsilon <!--\; \epsilon \; -->}}$有关，但不取决于${\displaystyle n}$。

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

设有向量${\displaystyle u_1,\dots <!--\; \dots \; -->,u_m\in <!--\; \in \; -->{\mathbb{C}}^d}$，满足${\displaystyle \underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{u}_i{u}_i^{\ast <!--\; \ast \; -->}=I}$（${\displaystyle d\times <!--\; \times \; -->d}$单位方阵），且对每个${\displaystyle i}$，${\displaystyle \Vert <!--\; \Vert \; -->u_i{\Vert <!--\; \Vert \; -->}_2^2\le <!--\; \le \; -->\mathrm{\delta <!--\; \delta \; -->}}$。则存在一种方法将${\displaystyle \{1,\dots <!--\; \dots \; -->,m\}}$分划成两个子集${\displaystyle S_1}$和${\displaystyle S_2}$，使得对于${\displaystyle j=1,2}$都有

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

设向量${\displaystyle v_1,\dots <!--\; \dots \; -->,v_m\in <!--\; \in \; -->{\mathbb{R}}^d}$满足${\displaystyle \Vert <!--\; \Vert \; -->v_i{\Vert <!--\; \Vert \; -->}_2^2\le <!--\; \le \; -->\mathrm{\alpha <!--\; \alpha \; -->}}$（对所有${\displaystyle i}$），还有

则可以将${\displaystyle \{1,\dots <!--\; \dots \; -->,m\}}$分划成两个子集${\displaystyle S_1}$、${\displaystyle S_2}$，使得对${\displaystyle j=1,2}$，以及满足${\displaystyle \Vert <!--\; \Vert \; -->x\Vert <!--\; \Vert \; -->=1}$的任意向量${\displaystyle x\in <!--\; \in \; -->{\mathbb{R}}^d}$，皆有：

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