Randomstrasse101: 2025 年の未解決問題

技術的サマリー（日本語）

本論文は、スイス・チューリッヒ工科大学（ETH Zurich）の数学部門に所属する研究グループが運営するブログ「Randomstrasse101」に掲載された 2025 年の 16 の未解決問題（そのうち 7 つが本稿で詳細に議論されている）をまとめたものです。確率論、計算理論、組合せ論、統計学および関連分野における興味深い未解決問題や予想を収集し、学術的な参照を容易にするための安定した記録として機能することを目的としています。

以下に、本稿で取り上げられている主要な 7 つのエントリ（問題）について、問題設定、手法、主要な貢献、結果、および意義を詳細に技術的に要約します。

---

1. テンソル集中不等式 (Tensor Concentration Inequalities)

著者: Kevin Lucca (KL)

問題設定

対称な決定論的テンソル $T_1, \dots, T_n \in (\mathbb{R}^d)^{\otimes r}$ と、独立同分布（i.i.d.）の標準ガウス変数 $g_1, \dots, g_n$ を考える。以下の量の上限を評価することが目的である。
$$\mathbb{E} \left[ \max_{\|x\|_p \le 1} \left| \sum_{i=1}^n g_i \langle T_i, x^{\otimes r} \rangle \right| \right] = \mathbb{E} \left\| \sum_{i=1}^n g_i T_i \right\|_{I_p}$$
ここで $\|\cdot\|_{I_p}$ は対称な注入的 $\ell_p$ ノルムである。

手法と背景

• 既存の知見: $r=p=2$ の場合（対称行列のスペクトルノルム）、Tomczak-Jaegermann や Ahlswede-Winter による結果があり、$\sqrt{\log d}$ の対数因子付きでスカラー変数と同様の振る舞いを示すことが知られている（非可換 Khintchine 不等式など）。
• 課題: 一般の $r, p \ge 2$ の場合、行列のトレースを用いた近似手法（$r=2$ の場合の鍵）が通用せず、注入的ノルムの近似は一般的に NP 困難である。
• アプローチ: この期待値はガウス過程の上限であり、Dudley のエントロピー積分を用いて、距離空間 $B^d_p$ の被覆数 $N(B^d_p, D, \varepsilon)$ を制御することで評価できる。

主要な予想と結果

• 予想 16 (テンソルの Type-2 定数): $p \ge 2$ に対して、以下の不等式が成り立つと予想されている。
  $$\mathbb{E} \left\| \sum_{i=1}^n g_i T_i \right\|_{I_p} \le \tilde{O}_{r,p} \left( d^{\frac{1}{2} - \frac{1}{p}} \sqrt{\sum_{i=1}^n \|T_i\|_{I_p}^2} \right)$$
• 現状: $p \ge 2r$ の領域では、被覆数の評価と鎖状結合（chaining）を用いて解決済み（[BGJ+24]）。しかし、$p < 2r$ の場合（特に $r=p=2$ の純粋な幾何学的証明を含む）は未解決であり、体積的な障壁が存在する。
• 関連研究: 非斉次ランダムテンソルや独立成分を持つ場合の最近の進展（PAC-Bayesian 補題を用いた対数因子の除去など）が言及されているが、一般の場合の粗い境界の証明は依然として困難である。

---

2. ランダム巡回グラフの Lovász 数 (The Lovász number of random circulant graphs)

著者: Daniil Dmitriev (DD)

問題設定

グラフ $G$ における最大独立集合のサイズ $\alpha(G)$ と彩色数 $\chi(G)$ の間に、Lovász 数 $\vartheta(G)$ が存在し、$\alpha(G) \le \vartheta(G) \le \chi(G)$ を満たす。Erdős-Rényi 乱雑グラフ $G(n, 1/2)$ における $\vartheta(G)$ の漸近挙動は未解決だが、構造的な「巡回グラフ（Circulant graphs）」に焦点を当てる。

手法と背景

• 巡回グラフ: 巡回群 $\mathbb{Z}_n$ 上の Cayley グラフであり、隣接行列が巡回行列となる。Paley グラフはその著名な例。
• 定式化: 巡回行列は離散フーリエ変換（DFT）行列 $F$ により対角化可能であるため、Lovász 数の半定数計画（SDP）は線形計画（LP）に帰着される。
• LP の双対性: 「時間領域」と「周波数領域」の 4 つの等価な LP 定式化が提示されている。

主要な予想と結果

• 予想 17: $G(n, 1/2)$ に対して、$\mathbb{E}\vartheta(G) = (1+o(1))\sqrt{n}$。
• 予想 18 (ランダム密な巡回グラフ): ランダムに生成された密な巡回グラフ $G$ に対しても同様に $\mathbb{E}\vartheta(G) = (1+o(1))\sqrt{n}$ が成り立つと予想。
• 現状: [BBD+25] において、下限と上限 $O(\sqrt{n} \log \log n)$ が示された。手法は、LP の修正版と subsampled DFT 行列の制限等距離性（RIP）の解析に基づいている。

---

3. 位相取得の単射性と安定性 (Injectivity and Stability of Phase Retrieval)

著者: Afonso S. Bandeira (ASB)

問題設定

$A \in \mathbb{K}^{N \times M}$ ($\mathbb{K}=\mathbb{R}, \mathbb{C}$) に対し、$|Ax|$から$x$ を復元する「位相取得（Phase Retrieval）」問題。$x$ は大域的な位相（$\mathbb{C}$）または符号（$\mathbb{R}$）を除いて一意に定まるか（単射性）、および安定に復元可能か（安定性）が問われる。

手法と背景

• 単射性の閾値: $\mathbb{C}$ において $N \ge 4M-4$ が十分であるという予想は、$4M-5$ の反例（Vinzant）により否定されたが、$4M-5$ での単射性の確率挙動は未解決。
• 安定性: Balan-Wang 予想は、安定性が行の部分集合の条件数 $\omega(A)$ と密接に関連し、$\omega(A)$ が行ノルムの最大値のべき乗で抑えられると予想している。

主要な予想と結果

• 予想 19: $N=4M-5$ のランダムな $A$ において、単射性の確率 $p_M$ は $M$ に対して $1$未満であり、$M \to \infty$で$0$ に収束する。
• 予想 20 (Balan-Wang 予想): 単射的な $A$ に対して、$\omega(A) \le C \max_k \|A_k\|^\beta$ を満たす普遍定数 $C, \beta$ が存在する。
• Open Problem 21: 標準ガウス行列 $A$ における $\omega(A)$ の値と、上記予想の妥当性、および $\beta$ の値を特定すること。

---

4. 相互に不偏な基底、ETF、および Zauner 予想 (Mutually Unbiased Bases, ETFs, and Zauner's Conjecture)

著者: Afonso S. Bandeira (ASB)

問題設定

• 相互に不偏な基底 (MUB): $\mathbb{C}^d$ における $d+1$ 個の基底の存在。$d$ が素数べきの場合は存在が知られているが、$d=6$ などの合成数では未解決。
• 等角緊密フレーム (ETF): 最小の最大内積を持つ単位ベクトル集合。$n=d^2$ の ETF は量子物理学（SIC-POVM）で重要。

手法と背景

• MUB(6) の未解決性: $d=6$ において、7 つの MUB が存在しないことを示すことが最大の未解決問題の一つ。
• Sum-of-Squares (SoS) 証明: 次数 2 の SoS 緩和では $MUB(6) < 7$ を証明できないことが示されている。
• Zauner 予想: 任意の次元 $d$ に対して $n=d^2$ の ETF（SIC-POVM）が存在する。

主要な予想と結果

• 予想 22: $MUB(6) < 7$。
• Open Problem 23: $MUB(6) < 7$ であることを示す次数 4 の SoS 証明の存在。
• 予想 24 (Zauner 予想): 任意の $d$ に対して $n=d^2$ の ETF が存在する。
• 最新動向: 数論的予想（Stark 予想など）を仮定した条件付き構成が提案されているが、無条件の証明は未だ得られていない。

---

5. Paley グラフのクリーク数 (On the clique number of the Paley Graph)

著者: Afonso S. Bandeira (ASB)

問題設定

$P \equiv 1 \pmod 4$ なる素数 $p$ に対する Paley グラフ $G_p$（頂点 $i, j$ が $i-j$ が平方剰余なら接続）。そのクリーク数 $\omega(G_p)$ の評価。

手法と背景

• 既存の上限: 乱雑グラフと同様に $\omega(G_p) = O(\text{polylog}(p))$ と予想されているが、証明は困難。
• Lovász 数による評価: $\omega(G_p) \le \vartheta(G_p) \le \sqrt{p}$。Hanson-Petridis により $\vartheta(G_p) \le (1+o(1))\sqrt{p/2}$ が示された。
• 局所化と SoS: 1-局所化（隣接頂点の誘導部分グラフ）の Lovász 数や、次数 4 の SoS 緩和による改善の可能性が探られている。

主要な予想と結果

• 予想 26: 1-局所化 $G_{p,1}$ に対して $\vartheta(G_{p,1}) \sim \sqrt{p/2}$。
• 予想 27: 2-局所化 $G_{p,2}$ に対して $\vartheta(G_{p,2}) \le \frac{2}{3}\sqrt{p}$。
• 予想 28: 次数 4 の SoS 緩和により、$\omega(G_p) = O(p^{1/2 - \varepsilon})$ のような多項式的な改善が可能か。
• 予想 29 (Paley ETF 予想): Paley 構成による ETF が、平方根のボトルネックを超えて制限等距離性（RIP）を満たす。

---

6. KLS 予想とその帰結 (The KLS Conjecture and Implications)

著者: Almut Rödder (AR)

問題設定

$\mathbb{R}^n$ 上の対数凹測度（log-concave measure）における等周定数 $\psi_\mu$ の評価。KLS 予想は、対数凹測度において等周定数が半空間による最小化で（普遍定数倍まで）達成されることを主張する。

手法と背景

• 歴史的進展: KLS (1995) は $\psi_n \ge C n^{-1/2}$ を示した。Eldan (2013) は確率的局所化（stochastic localization）を用いて $n^{-1/3}$ を突破。Lee-Vempala (2017) は $n^{-1/4}$ を達成。
• 最近のブレイクスルー:
  • Chen (2021): $\exp(-\sqrt{\log n \log \log n})$ を達成（多項式ボトルネックの突破）。
  • Klartag (2023): $\log(n)^{-1/2}$ を達成（現在の最良の下限）。
• 関連予想:
  • Thin Shell 予想: isotropic 対数凹測度の質量が半径 $\sqrt{n}$ の薄い球殻に集中する。Klartag-Lehec (2025) により解決済み。
  • Bourgain のスライシング問題: 凸体の断面の最大面積の下限。Klartag-Lehec (2025) により解決済み。

主要な結果と意義

• KLS 予想の解決は、ポアンカレ不等式、リプシッツ集中、凸体上のマルコフ連鎖モンテカルロ法（ボールウォーク）の混合時間（$\tilde{O}(n^2)$）の保証など、高次元幾何学と計算論に広範な影響を与える。
• 2025 年の Thin Shell 予想とスライシング問題の解決は、KLS 予想の現状の最良の境界を間接的に裏付ける結果となっている。

---

7. グラフ行列の鋭い境界 (Sharp Bounds for Graph Matrices)

著者: Petar Nizić-Nikolac (PNN)

問題設定

Sum-of-Squares (SoS) 階層による多項式最適化問題の下限証明において、擬似期待値（pseudo-expectation）の正定値性を検証する際に現れる「グラフ行列（Graph matrices）」のスペクトルノルムを精密に評価する問題。

手法と背景

• グラフ行列: 植込みクリーク問題などの文脈で現れ、ランダムな入力（ラデマッハ変数など）の多項式として定義される行列。
• 既存の手法: モメント法を用いると、ノルムが $n^{f(\alpha)} (\log n)^{g(\alpha)}$ のオーダーで抑えられることが示されているが、対数因子 $g(\alpha)$ が不要な場合があるかどうかが不明瞭。
• 行列カオス: グラフ行列は「行列カオス（Matrix Chaos）」の一種であり、自由確率論や非可換 Khintchine 不等式の反復を用いた新しいツールの適用が試みられている。

主要な予想と結果

• 予想 31 (鋭いグラフ行列境界): 形状 $\alpha$ に対して、関数 $f, g$ が存在し、
  $$\mathbb{E}\|M_\alpha\| = \Theta\left( n^{f(\alpha)} (\log n)^{g(\alpha)} \right)$$
  が成り立つ。
• 意義: 現在の反復自由確率ツールでは、すべての形状に対して非可換な振る舞い（追加の定数因子なし）を証明できていない。正確な $f, g$ の同定は、SoS 階層の下限を改善し、擬似較正（pseudo-calibration）ヒューリスティックの理解を深める鍵となる。

---

総括と意義

本稿は、確率論、組合せ論、計算複雑性理論の交差点にある重要な未解決問題群を体系的に整理したものである。特に以下の点が学術的に重要である。

1. 学際的な視点: 各問題が、純粋数学（幾何学、数論）、応用数学（統計、最適化）、理論計算機科学（SoS 階層、アルゴリズム）の複数の分野と深く結びついていることを示している。
2. 最新動向の反映: 2024-2025 年にかけて Klartag や Lehec による高次元凸幾何学の画期的な成果（Thin Shell 予想、スライシング問題の解決）や、Chen による KLS 予想の進展など、極めて最新の研究動向を網羅している。
3. 証明手法の多様性: 確率論的局所化、自由確率論、SoS 緩和、数論的構成など、多様な数学的ツールの応用可能性を示唆しており、今後の研究の指針となる。
4. 未解決問題の具体化: 抽象的な「未解決」ではなく、具体的な定数、次数、漸近挙動に関する明確な予想（Conjecture）として提示されており、研究者が取り組むべき具体的なターゲットを提示している。

このコレクションは、これらの分野における次世代の研究課題を定義し、学術コミュニティの関心を喚起する重要なリソースとなっている。