MathLabs

解法: 交差族によるMarcus–Spielman–Srivastavaの証明(2013年)

ステップ 3/8: 実安定多項式:多変数版の「すべての根が実数」
ざっくり言うと

一変数の多項式にとって、根がすべて実数であることは強力で有用な性質である:これはグラフが xx 軸に触れるだけで、複素領域には決して入り込まないことを意味する。実安定性はこの発想を複数変数の多項式へ自然に一般化したものであり、多数の行列を同時に操作する際に現れる演算—和、積、代入、微分—のもとで驚くほど良く振る舞うことが分かっている。

統計物理学のLee–Yangプログラムに関するBorceaとBrändénの数十年にわたる研究に基づくこの一つの代数的性質こそが、証明全体を支える耐力壁である:以降のすべてはこの性質を一度証明できれば、いくつもの変換を無償で通せるという事実にかかっている。

p(z1,…,zm) real stable  ⟺  p(z1,…,zm)≠0 whenever Im⁡(zi)>0 ∀ip(z_1,\ldots,z_m) \text{ real stable} \iff p(z_1,\ldots,z_m)\ne 0 \text{ whenever } \operatorname{Im}(z_i) > 0 \ \forall i
詳しい解説

実係数を持つ多変数多項式 p(z1,…,zm)p(z_1,\ldots,z_m) が、すべての変数 ziz_i の虚部が厳密に正であるとき常に p(z1,…,zm)≠0p(z_1,\ldots,z_m) \ne 0 となるならば実安定と呼ばれる。m=1m=1 のとき、これは根がすべて実数であることに正確に帰着する。実安定性は、統計物理学におけるLeeとYangの古典的研究、およびHeilmannとLiebの単量体–二量体多項式に関する研究を拡張する形で、Julius BorceaとPetter Brändén(2008–2010年)によって体系的な理論として発展させられた。

実安定性をこれほど強力にしている重要な工学的事実は、それがわずかな種類の演算のもとで保存されることである:変数を互いに等しく置くこと、微分すること、そしてある種の線形代入は、いずれも実安定多項式を実安定多項式へ写す(最初の二つの場合は変数が一つ減る)。これにより、単純な構成要素から複雑な実安定多項式を構築し、変数を特殊化することでそこから一変数の実根多項式を取り出すことができる—これはまさに前段の多項式族を厳密に定義するのに必要な道具立てである。

次の段階では、この機構がWeaverの KS2KS_2 に現れる具体的な行列 vivi∗v_iv_i^* に適用され、「混合特性多項式」が生み出される。これこそがMarcus–Spielman–Srivastavaの証明における真の主役である。

このステップの用語
実安定性
「根がすべて実数である」ことの多変数版一般化:多項式 p(z1,…,zm)p(z_1,\ldots,z_m) は、すべての変数が同時に複素平面の開いた上半分に置かれたとき決して零にならないならば実安定である。
このステップで使う知識