Better bounds on finite-order Grothendieck constants

技術要約：有限次グロテンドック定数のより良い境界値

問題提起
本論文は、有限次のグロテンドック定数 $KG(d)$の計算に取り組んでいる。これらの定数は、特定のテンソルノルムに関する最適化タスクにおいて、$d$次元の戦略が 1 次元の戦略に対して持つ優位性を定量化するものである。無限次の定数$KG$および$d=2$のケースは十分に研究されているが、$d \geq 3$の値についてはほとんど分かっていない。主な課題は、$d$ 次元の半正定値計画問題（SDP）の値 $SDP_d(M)$ と、1 次元の値 $SDP_1(M)$（これは NP 困難な MaxCut 問題に等しい）との比を最大化する行列 $M$ を見つけることにある。既存の $d \in \{3, \dots, 9\}$ に対する境界値は緩く、高次元のアンサンブル（ansätze）を見つけることは、次元の呪いによって阻まれている。

手法
著者らは、Frank-Wolfe アルゴリズムに基づく最新の射影技術と、強力なバイナリ二次最適化ソルバーを組み合わせて使用している。手法は主に 2 つのアプローチに分かれている。

1. 対称的なインスタンス（ヒューリスティックおよび解析的）:

   • 著者らは、高度に対称的なライン・パッキング（例：$E_7, E_8$ などのルート系や、600細胞、120細胞などの多胞体）を利用して、グラム行列 $P$ を構成する。
   • 対称化された相関多胞体 $SDP_1$ への $P$ の射影のために、Blended Pairwise Conditional Gradient (BPCG) アルゴリズムを採用する。このプロセスは、超平面（ファセット $A$）を介して $P$ を $SDP_1$ から分離することを目指す。
   • 対称構造を用いることで、周囲空間の次元が削減されるため、「推定される」ファセットの導出が可能になる。しかし、これら大規模で対称的なインスタンスに対して正確な $SDP_1(A)$ を計算することは、正確なソルバーではしばしば困難である。したがって、著者らはヒューリスティックな手法（交互最小化／シーソー最適化）を用いて $SDP_1(A)$ を推定し、厳密に証明されたものではないが、非常に示唆に富む下界を得ている。

2. 非対称なインスタンス（厳密な証明）:

   • 厳密に証明された境界値を得るために、行数（$m_1$）が少なく列数（$m_2$）が多い長方形行列 $M$ を構築する。これにより、$SDP_1(M)$ の計算の複雑さが軽減される（$m_1$ に対して指数関数的だが、$m_2$ に対しては線形である）。
   • 著者らは Frank-Wolfe アルゴリズムを使用して分離超平面 $M$ を見つけ、その後、[13] のブランチ・アンド・バウンド・ソルバーおよび QuBowl ソルバー [39] を用いて、結果として得られるバイナリ二次最適化問題（MaxCut）を正確に解く。
   • $d=3$ については、Lasserre hierarchy の第 1 レベルを用いて既存の量子戦略を洗練させ、下界をわずかに改善している。

主要な貢献と結果

• $d \in \{3, 4, 5\}$ に対する厳密に証明された下界:
  本論文は、$d=3, 4, 5$ において最先端（SoA）を改善する、厳密に証明された下界を提供している。$KG(d)$の単調性により、これらの改善はすべての$d \leq 9$ に拡張される。

  • $KG(3) \geq 1.43670$ （従来の $1.43665$ を改善）
  • $KG(4) \geq 1.48579$ （従来の $1.48217$ を改善）
  • $KG(5) \geq 1.49339$ （従来の $1.48217$ を改善）
  • これらの結果は、$d=9$ までの $KG(d)$ の最善の既知の境界値を上回っている。

• 高次元に対するヒューリスティックな境界値:
  高度に対称的な構造（具体的には $E_7$ ルート系および 120 細胞）を用いて、著者らは現在の SoA 値よりも大幅に高いヒューリスティックな下界を導き出している。

  • $KG(7)$について、$E_7$ルート系は$\approx 1.4997$のヒューリスティックな下界をもたらし、これは$KG(5)$ の証明された下界よりも高い。
  • $KG(8)$について、120 細胞は$\approx 1.5138$ のヒューリスティックな下界をもたらす。
  • 著者らは、対応する $SDP_1$ インスタンスを正確に解くことが困難であるため、これらの境界値は現在ヒューリスティックなものであると述べているが、基礎となる対称的なインスタンスは、これらを証明するための将来の研究のために提供されている。

• 一般化された定数 $KG(d \to 2)$:
  著者らは、複素 $d$ 次元量子力学が実数量子力学に対して持つ優位性に関連する、一般化されたグロテンドック定数 $KG(d \to 2)$ への分析を拡張している。

  • 下界: 著者らは、$SDP_2(M)$ を上界付けるために Lasserre hierarchy（レベル 2）を用い、数値的な下界を提供している。これらの境界値は、いくつかの次元（例：$d=3, 4, 5$）において SoA を改善している。
  • 上界: 著者らは、[14] から適応させた分解法を用いて、$KG(3 \to 2) \leq 1.1233\dots$ という厳密な解析的上界を導出している。これは、この特定の定数に対する最初の非自明な上界である。

意義と主張
本論文は、Frank-Wolfe 射影技術と高度なバイナリ最適化ソルバーを組み合わせることで、$3 \leq d \leq 9$ の範囲における有限次のグロテンドック定数の既知の下界を成功裏にタイトにしたと主張している。本研究は、高度に対称的な、高次元のインスタンスを厳密に証明することが依然として計算的に困難であることを浮き彫りにしているが、ヒューリスティックな結果は、これらの定数の真の値がこれまで考えられていたよりも大幅に高い可能性があることを示唆している。

著者らは、量子非局所性との関連性を強調し、$KG(d \to 2)$ を複素量子力学が実数量子力学に対して持つ定量的な優位性と解釈している。彼らの $KG(3 \to 2)$ に対する厳密な上界は、この優位性に具体的な限界を与えるものである。本論文は、提供されたインスタンスと手法が、対称性を利用して残された二次最適化問題を解決し、無限次のグロテンドック定数の最善の既知の下界（$\approx 1.6769$）に匹敵する境界値を得るための道筋を示すものであると結論付けている。