Copositivity, discriminants and nonseparable signed supports

技術要約：コポジティビティ、判別式、および非分離な符号付きサポート

問題提起
本論文は、正の実数直交錐 $\mathbb{R}^n_{>0}$ 上の定義された、実指数を持つ単項式の線形結合である符号付き多項式（signomials）のコポジティビティ（copositivity）を判定する問題に取り組んでいる。具体的には、コポジティブな符号付き多項式の錐の境界、判別式、および符号付きサポート（指数の集合と係数の符号のペア）の組合せ論的構造との関係を調査している。大域的な非負性は実代数幾何学における中心的なトピックであるが、コポジティブな多項式の集合への所属を判定することはNP困難である。既存の手法は、SOS（平方和）、SONC（非負回路の和）、またはSAGE（算術幾何平均指数関数の和）といった非負性の証明（certificate）に依存することが多い。鍵となる未解決の問いは、すべてのコポジティブな符号付き多項式がSONC分解を持つような符号付きサポートの特性を明らかにすることである。

手法
著者らは、符号付き判別式とホモトピー継続法に基づくコポジティビティの判定基準を開発している。

1. 符号付き判別式とパス： 著者らは、符号付き $(A^+, A^-)$-判別式 $\nabla_{>0}(A^+, A^-)$ を、係数ベクトルが（あるいはそのサポートの凸包の面への切断が）正の特異零点を持つような係数ベクトルの集合として定義する。そして、係数の符号を維持しながら、負の項の係数をパラメータ $t$ によってスケーリングする、係数空間内の特定のパス $c(t)$ を構築する。
2. 交差判定： コアとなる理論的ツールは、ある符号付き多項式がコポジティブであるための必要十分条件は、パス $c(t)$ が任意の $t < 1$ に対して符号付き判別式と交差しないことである、という観察である。交差点の集合 $T$ を解析して最小値 $t^*$ を求める。コポジティビティは $t^* \geq 1$ であることと同値である。
3. 非分離な符号付きサポート： 本論文では、「非分離（nonseparable）」な符号付きサポートという組合せ論的概念を導入している。ペア $(A^+, A^-)$ が非分離であるとは、$A^-$ が $A^+$ のすべての正則多面体分割の共通細分によるセル $D$ に含まれていることを指す。この幾何学的条件は、SONC証明が保証されている既知のケースを一般化するものである。
4. ホモトピー継続： 非分離なサポートに対して、著者らは集合 $T$ がちょうど一つの要素 $t^*$ を含むことを証明している。これにより、既知の開始点（符号付き多項式が $x=1$ で特異零点を持つ点）からターゲットとなる符号付き多項式へと、単一の解パスを追跡するパラメータ・ホモトピー継続法を用いることが可能となり、複数のシステムを解いたり、臨界点を直接評価したりする必要がなくなる。

主な貢献と結果

• コポジティビティ判定基準 (Theorem A/Theorem 2.9)： 著者らは、コポジティビティの必要十分条件を確立した。符号付きサポート $(A^+, A^-)$ を持ち、$A^- \subseteq \text{conv}(A^+)$ である符号付き多項式において、コポジティビティが成立するための必要十分条件は、パス $c(t)$ が符号付き判別式（またはそのサポートの切断の判別式）と交差する最小パラメータ $t^*$ が $t^* \geq 1$ を満たすことである。この基準は、臨界点における符号付き多項式の評価に伴う数値誤差を回避する。
• 非分離サポートにおけるSONC分解 (Theorem B/Theorem 3.16)： 本論文は、$A^-$ が $\text{conv}(A^+)$ の面の相対内部にある任意の非分離な符号付きサポートに対して、コポジティブな符号付き多項式の錐はSONC錐と一致することを証明している。言い換えれば、そのようなサポートを持つすべてのコポジティブな符号付き多項式は、非負回路符号付き多項式の和への分解が可能である。これは、特定の幾何学的条件（例：単純な頂点の存在）を要求していた従来の成果を一般化するものである。
• 一意性と非退化性 (Theorem C/Theorem 3.17 & 4.5)： 非分離なサポートの場合、交差集合 $T$ はちょうど一つの点 $t^*$ からなる。さらに、対応する臨界系は、一意で非退化な正の特異零点を持つ。この理論的結果は、数値的手法（ホモトピー継続）がこのクラスの問題に対して頑健かつ効率的であることを保証する。なぜなら、正の次元を持つ零集合によって解を見逃すという事態を回避できるからである。
• 境界の特性化 (Theorem 3.18)： 著者らは、非分離な符号付きサポートにおいて、コポジティブな多項式の錐の代数的境界が、符号付き判別式に含まれ（特定の条件下では一致し）ていることを示している。
• 計算実装： 本論文は、これらの手法を実装したJuliaパッケージ CopositivityDiscriminants.jl を提示している。これは、非分離なサポートにおいて、単一のホモトピーパスを追跡することが、すべてのパスを追跡したりSAGE証明を使用したりする場合と比較して、（数分ではなく数秒という）大幅に効率的であり、かつ、判別式の境界に近い符号付き多項式に対しても数値的に安定していることを実証している。

意義と主張
本論文は、判別式、コポジティビティ、およびSONC分解を結びつける統一的な枠組みを提供すると主張している。その主要な意義は以下の通りである：

1. 一般化： コポジティビティがSONC分解可能性を意味する既知の符号付きサポートのクラスを、より広いクラスである非分離なサポートへと拡張し、単純な頂点の存在といった制限的な仮定を取り除いた。
2. アルゴリズムの効率性： 非分離なサポートが判別式との一意かつ非退化な交差を与えることを証明することで、複数の臨界系を解くという組合せ爆発を回避する、極めて効率的な計算戦略（単一パス・ホモトピー）を可能にした。
3. 数値的安定性： 本手法は、コポジティブ錐の境界付近の符号付き多項式を扱う際、評価ベースの手法やSAGE証明よりも頑健なコポジティビティの証明を提供する。これは、SAGEが小さな摂動によって失敗する一方で、判別式ベースの手法が成功する例によって示されている。

著者らは、本手法は非分離なサポートに対しては強力であるが、臨界系の零集合が正の次元を持つ可能性がある一般的なケースにおいては限界があり、数値実装において解を見逃す可能性があることも指摘している。しかし、一般的な係数については、これらの病理的現象は発生しないことを示している。