MathLabs

解法:马库斯–斯皮尔曼–斯里瓦斯塔瓦利用交错族给出的证明(2013年)

第 6/8 步:势垒函数:亲手计算出根的界
通俗地说

知道一个多项式是实根的,只能告诉我们根存在且性质良好,却不能告诉我们它们究竟有多大。为了确定具体数值,Marcus、Spielman 与 Srivastava 重新利用了 Batson、Spielman 与 Srivastava(2012年)最初为构造图的稀疏近似而发明的一种技术:一个「势垒函数」,它像是紧贴在最大根右侧的一道栅栏,当从上方逼近某个根时,其值会趋向无穷大。

策略是证明:每往运行中的和里再加入一个向量的贡献,都绝不会把这道栅栏推过某个固定位置,因此在加入全部 mm 个向量之后,最大根仍被困在该固定位置之下——这就好比证明一摞箱子永远不会倒,只需检验每加入一个箱子时,重心的移动都不会太远。

Φu(A):=tr⁡(uI−A)−1,roots of p(x)≤max⁡{u:Φu stays below a fixed threshold}\Phi^u(A) := \operatorname{tr}(uI-A)^{-1}, \qquad \text{roots of } p(x) \le \max\{u : \Phi^u \text{ stays below a fixed threshold}\}
详细分析

多变量势垒函数论证在逐个向量构造 A=∑i≤kvivi∗A = \sum_{i \le k} v_iv_i^* 的每一步都追踪一个势函数 Φu(A)=tr⁡(uI−A)−1\Phi^u(A) = \operatorname{tr}(uI-A)^{-1}(选定阈值 uu):只要 uu 超过 AA 的所有特征值,这个量就是有限的,而当 uu 从上方逼近最大特征值时,它会无界增长。Batson、Spielman 与 Srivastava 最初(针对单个矩阵)的势垒方法(2012年)表明,只要 Φu(A)\Phi^u(A) 一开始就低于某个固定的界,那么加入一个 ∥v∥2\|v\|^2 足够小的秩一项 vv∗vv^*,只会使势垒移动一个受控的小量。

Marcus、Spielman 与 Srivastava 把这一方法推广到多变量实稳定的场景:由于混合特征多项式可以逐个向量地构造(每加入一个 vivi∗v_iv_i^* 就对应于再对一个 ziz_i 求导),同样的势函数记账方式表明,在整个构造过程中,p(x)p(x) 的最大根始终保持在 u∗=(1+2δ)2/2u^* = (1+\sqrt{2\delta})^2/2 之下,其中 δ=max⁡i∥vi∥2\delta = \max_i \|v_i\|^2;这正是 Weaver 在 KS2KS_2 中猜想的常数。

这是整个证明中计算最密集的一步:正是在这里,实稳定性与交错族这套抽象机制被转化为一个诚实、可验证的数值不等式,弥合了「根是实数」与「根被证明至多为这个具体数值」之间的鸿沟。

本步骤中的术语
势垒函数/势函数
一个关于矩阵的实值函数,例如 (uI−A)−1(uI-A)^{-1} 的迹,在 uu 明显大于 AA 的所有特征值时保持较小,而当 uu 逼近最大特征值时会急剧增大;追踪这个量能定量控制某个操作能把最大特征值移动多少。
本步骤用到的知识