结果族 126：Exponential semidefinite complexity of perfect matching · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
皮影戏的秘密:在幕布后摆一个简单的物件,调整角度,让影子恰好是复杂图案。数学里也有这招——用高维空间里一个”好说话”的几何体,投影出低维的复杂形状。论文问:描述”完美匹配”的那个复杂多面体,能不能由一个小物件投影出来?答案:不能,物件必须指数级大。
关键词卡片
看个具体例子
论文的矩阵:行是奇割(奇数个顶点的集合 @@M@@U@@),列是完美匹配 @@M@@M@@,元素为 @@M@@|M\cap\delta(U)|-1+\rho@@。取 @@M@@K_6@@、@@M@@U=\{1,2,3\}@@ 看两个匹配:
匹配穿过奇割的次数必为奇数(1、3、5……),所以矩阵元素都非负。主定理:这张表的 PSD 秩至少 @@M@@2^{cn}@@,于是完美匹配多面体的任何精确半定提升,规模都至少 @@M@@2^{c_0 n}@@。
为什么值得关心
线性表述的指数下界早已知晓,但”半定投影会不会更省”是 Rothvoss 提出的悬案;本文给出否定答案,为”用扩展模型高效求解匹配问题”的设想划出了理论边界。
暂无形式化证明(AI 结果待核验)
第一级台阶
导读的”皮影戏”比喻翻译过来：台前的复杂图案是一个几何体——把图上所有两两配对方案按权重混合填成的完美匹配多面体；幕后的简单物件是高维空间里半正定锥的一个仿射切片。要问的是：能否放一个小的幕后物件，让它的投影恰好是台前的多面体？论文的回答是不能——物件必须指数级大。
第二级台阶
| 用本科术语把道具摆齐：完全图 K_n 上，完美匹配 M 是把全部顶点两两配对的方案；奇割 U 是奇数个顶点组成的子集，δ(U) 是穿过它的边集。核心对象是松弛矩阵：行取奇割、列取完美匹配，元素为 | M∩δ(U) | −1+ρ——因匹配穿过奇割的次数必为正奇数，矩阵元素全非负。矩阵的 PSD 秩是最小的 r，使每个元素都能写成两个 r×r 半正定矩阵的迹乘积；锥分解定理把它等同为最小半定提升的规模。 |
第三级台阶
定理的语境：对任意固定的 0<ρ<1，当偶数 n 足够大时，上述矩阵的 PSD 秩至少 2^{cn}；推论是完美匹配多面体的每个精确半定提升规模至少指数级。假设各有分工：ρ 限制在开区间——端点 ρ=1 存在仅 C(n,2) 规模的对角分解，指数下界不可能覆盖它；因子的构造不设对称性、稀疏性或精度限制，使下界对最一般的分解成立；而”精确”二字不可放松——此前已知存在容许微小误差的亚指数规模分解。结论用这些术语说：Rothvoss 提出的”多项式规模半定提升是否存在”被否定，线性表述的指数下界由此推广到了半定世界。
对任意固定的 @@M@@0<\rho<1@@，奇割—完美匹配矩阵 @@M@@|M\cap\delta(U)|-1+\rho@@ 的实半定秩（PSD rank）至少为 @@M@@2^{cn}@@；因此完全图完美匹配多面体的任何精确半定提升（semidefinite lift）规模必为指数级，负面回答了 Rothvoss 的”多项式规模半定提升”问题。
扩展表述（extended formulation）用高维凸集的投影紧凑描述复杂多面体。Yannakakis 的非负分解框架与 Rothvoß 2014 年的工作证明完美匹配多面体（perfect matching polytope）@@M@@P_n@@ 的任何线性表述都有指数规模，但换成正半定锥仿射切片的投影（半定提升）可能更省，线性下界不自动排除它。Gouveia–Parrilo–Thomas 的锥分解定理把最小半定提升规模等同于松弛矩阵（slack matrix）的 PSD 秩，”匹配是否有多项式规模半定提升”由此悬而未决。此前仅有对称情形（Braun 等）与非负秩（Braun–Pokutta）的指数下界；Kaniewski–Lee–de Wolf 还给出容许误差 @@M@@2^{-\sqrt{n/2}}@@ 的亚指数近似分解，可见精确性必须严苛对待。本文的分离泛函承袭 Grigoriev 针对 Tseitin 矛盾的低度泛函。
主定理：存在 @@M@@c>0@@，对每个固定 @@M@@0<\rho<1@@ 有 @@M@@n_0(\rho)@@，偶数 @@M@@n\ge n_0@@ 时 @@M@@\rank_{psd} A_n(\rho)\ge 2^{cn}@@。行标为 @@M@@K_n@@ 的奇数大小顶点集 @@M@@U@@（奇割，odd cut），列标为完美匹配 @@M@@M@@，元素 @@M@@|M\cap\delta(U)|-1+\rho@@（@@M@@\delta(U)@@ 为割集）；完美匹配穿过奇集的次数为正奇数，矩阵非负。PSD 秩是最小的 @@M@@r@@，使存在实对称半正定因子 @@M@@F_U,G_M\in\mathbb{R}^{r\times r}@@ 满足 @@M@@A_{U,M}=\tr(F_UG_M)@@。端点 @@M@@\rho=1@@ 有 @@M@@\binom n2@@ 规模对角分解，指数下界到不了它。推论：@@M@@A_n(0)@@ 与 Edmonds 描述（度等式+非负性+奇割不等式）的松弛矩阵 @@M@@T_n(0)@@ 的 PSD 秩均为 @@M@@2^{c_0n}@@，故 @@M@@P_n@@ 的每个精确半定提升规模至少 @@M@@2^{c_0n}@@。给 @@M@@A_n(0)@@ 因子追加标量块即得 @@M@@A_n(\rho)@@ 分解，故 @@M@@\rank_{psd} A_n(\rho)\le\rank_{psd} A_n(0)+1@@，平移版蕴含未平移版。
反证法，循 Lee–Raghavendra–Steurer 路线以低度分离泛函对付平方和，难点是把匹配问题传输到奇偶系统并处理正平移。
先造分离泛函。以 @@M@@d=100@@ 个随机完美匹配的并构造 @@M@@t@@ 点 @@M@@d@@-正则二部扩展图（expander）@@M@@H@@，割满足 @@M@@|\delta_H(W)|\ge\beta d\min\{|W|,t-|W|\}@@。给各顶点指定总和为奇的奇偶位 @@M@@b_i@@，则满足各处奇偶约束的位指派 @@M@@y@@ 必有某边两端不同，故 @@M@@f_\epsilon(y)=\sum_e\mathbf 1_{\{y_{u,e}\ne y_{v,e}\}}-\epsilon@@ 严格正。但论文在块 Fourier 特征（Fourier character）上定义线性泛函 @@M@@\mathcal D@@：若 @@M@@p@@ 的关联像是割且块度（block degree）@@M@@\le 2D@@（@@M@@D=\lfloor t/1000\rfloor@@），就用扩展性选唯一小侧 @@M@@S(p)@@ 并给 @@M@@\chi_p@@ 赋值 @@M@@(-1)^{\sum_{i\in S(p)}b_i}@@，否则为零。各割陪集上 @@M@@\mathcal D(\chi_p\chi_{p'})@@ 是秩一半正定块，故对块度 @@M@@\le D@@ 的 @@M@@g@@ 有 @@M@@\mathcal D(g^2)\ge0@@，而 @@M@@\mathcal D(f_\epsilon)=-\epsilon<0@@。
再把奇偶系统嵌入匹配：把 @@M@@H@@ 每个顶点换成 @@M@@k@@ 个顶点的胞（@@M@@k@@ 为先固定的常数），奇割行取每胞中规定奇偶的子集，列匹配每胞留 @@M@@d@@ 个端子、其余顶点胞内配对，辅助边连接对应端子；局部限制使胞内对割位相等，于是 @@M@@|M\cap\delta(U)|-1+\rho=f(y)@@ 精确成立。若存在规模 @@M@@r\le 2^t@@ 的分解，先以 @@M@@\log\det@@ 势归一化迹，再对行因子作限制平均，得 @@M@@\tr(\overline F_m(y)G_{M(m)})=f(y)@@。
最后证明小分解迫使 @@M@@f@@ 接近低块度平方和（sum of squares），靠三个组件：局部平均引理借置换对称性（非常特征空间维数 @@M@@\ge k/2@@）与迹估计得方差压缩 @@M@@O(k^{-1/4}\sqrt{\log k})@@；正交分裂引理以 Helstrom 型谱投影把 @@M@@L@@ 个 PSD 矩阵分入正交子空间；乘积平滑定理逐坐标归纳，以直和堆叠实现新平均、控制新频率重叠并分配分支，势每步至多翻倍。于是可选 @@M@@m@@ 使 @@M@@\overline F_m=\sum_q H_q^{\mathsf T}H_q@@ 且加权 Fourier 质量极小；把每分支截断到中心邻域 @@M@@\mathrm{dist}\le D@@，弃量被指数权重压至 @@M@@n(4L)^{-2t}@@，故 @@M@@f_*@@ 一致逼近 @@M@@f@@。乘以 @@M@@\chi_q@@ 把保留频率平移到块度 @@M@@\le D@@ 而平方不变（支撑平移原理），故 @@M@@\mathcal D(f_*)\ge0@@；但范数界给出 @@M@@|\mathcal D(f-f_*)|\to0@@，与 @@M@@\mathcal D(f)=-\epsilon@@ 矛盾。故 @@M@@r>2^t\ge 2^{n/(2k)}@@。
本文是结果族 126 的主定理载体，本批次该族仅此一篇。局部平均、正交分裂、乘积平滑三个组件独立成节，可单独核验与复用，增强可信度。按任务元信息，主结果暂无 Lean 形式化证明；OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。
问 1：证明中最关键、也最脆弱的一步在哪里？
答：乘积平滑定理（fourier-smoothing 节）。反证假设存在小规模分解后，必须证明行因子的平均可精确写成 Σ H_q^T H_q 且各分支的 Fourier 质量集中在中心 q 的少数块内——逐坐标归纳、以直和堆叠实现新平均、势每步至多翻倍，截断弃量被指数权重压至 n(4L)^{-2t}。最后靠”支撑平移”（乘以 χ_q 把保留频率搬到低块度而平方不变）接上分离泛函 D。任何一处权重与块度参数失配，”D(f*)≥0 与 D(f)<0”的矛盾就接不上。
问 2：为什么平移参数必须落在 0<ρ<1，端点为何例外？
答：ρ=1 时矩阵有 C(n,2) 规模的对角分解（行取割指示、列取匹配指示，迹乘积恰为交点数），指数下界到不了端点——论文明确写出这一点。平移版反而更强：给 A_n(0) 的因子追加标量块即分解 A_n(ρ)，故 rank_psd A_n(ρ)≤rank_psd A_n(0)+1，取 ρ=1/2 便把下界传回未平移版与 Edmonds 松弛矩阵。
问 3：相对既有工作，真正新意是什么？
答：Rothvoß 只排除线性表述；Braun–Pokutta 证的是非负秩（因子为标量）；Braun 等只处理坐标对称的半定表述。本文给出无任何对称性假设的 PSD 秩指数下界，方法上承 Lee–Raghavendra–Steurer 的平方和—低度分离泛函路线，新增两件东西：把奇偶系统传输进匹配的胞构造（处理精确正平移），以及局部平均+正交分裂+乘积平滑三个可复用组件。精确性是关键——Kaniewski–Lee–de Wolf 已有误差 2^{-√(n/2)} 的亚指数近似分解。
问 4：AI 生成证明最可能在哪里出错？
答：常数依赖的次序。胞尺寸 k 是先固定的常数，随后 n→∞，局部平均的方差压缩 O(k^{-1/4}√log k)、不变特征空间维数下界 k/2、正交分裂的无量纲性，都要在”k 充分大→t 个胞→n=kt”的链条上按正确次序取极限，末端才有 r>2^t≥2^{n/(2k)}。机器证明最易在这种多层常数传递中把某个依赖方向弄反。
问 5：分离泛函为什么能既非负于低块度平方、又给 f 记负分？
答：D 在割陪集上是秩一的半正定块，对块度不超过 D 的平方和必然非负；而奇偶位总和为奇使 f 处处为正，D(f)=−(1−ρ) 却为负。这正是”低度平方和证明无法证伪奇偶矛盾”（Grigoriev 对 Tseitin 矛盾的泛函思想）的定量化，矛盾只能由高块度成分造成，而小分解恰恰消不掉它们。
问 6：谁会用这个结果？
答：扩展表述复杂度与 SDP 求解社区——它为”用半定扩展模型紧凑求解匹配”划了理论死刑，也提示匹配多项式可解性依赖的不是凸几何描述。三个组件独立成节，可迁移到其他组合多面体的 PSD 秩下界；容许误差的近似提升下界与其他多面体（如 TSP）的对应问题，论文未展开。
总评
这是把匹配的表述复杂度下界从线性世界推进到无限制半定世界的完整一击，负面回答了 Rothvoss 的悬案；最大风险在未形式化的多层平滑—截断—平移链条，其常数传递次序一旦有误，指数下界便会悄然失效。