A $(\log n)^{1/4}$ Bound for the Komlós Problem

技術的要約：Komlós問題における $(\log n)^{1/4}$ 境界

問題設定
本論文は、Komlós予想に対処するものである。この予想は、列のユークリッドノルムが最大1である任意の実行列 $A \in \mathbb{R}^{m \times n}$ に対して、組合せ論的不一致（combinatorial discrepancy）$\text{disc}(A) = \min_{\sigma \in \{-1,1\}^n} \|A\sigma\|_\infty$ が絶対定数によって抑えられると提唱している。Banaszczykは $O(\sqrt{\log n})$ の境界を確立したが、目標は $n$ に依存しない定数へと改善することである。近年の研究であるBansalおよびJiang [BJ25, BJ26] は、アフィン・スペクトル独立性（affine spectral independence）の枠組みを導入し、$O((\log n)^{1/4}(\log \log n)^{7/4})$ の境界を達成した。本論文の目的は、この $(\log \log n)^{7//4}$ という因子を除去することである。

手法および枠組み
本構成は、Bansal–Jiangの枠組みに基づいて構築されており、具体的には彼らのアフィン・スペクトル独立性定理（Theorem A.4）と、半正定値計画法（SDP）によるデカップリングの概念を利用している。核心となる手法は、分数的な彩色（fractional coloring）$b \in [-1, 1]^n$ を符号化された $\sigma$ へと進化させる有限軌道構成である。

主要な技術的要素は以下の通りである：

1. 逐次的な制限とサイズクラス： アルゴリズムは、行を「生存している（凍結されていない）」座標上での二乗質量に基づいた「サイズクラス」に分解することで、行を処理する。行は、大きな係数を残りの部分から分離するために「剥離（peel）」され、これにより各クラスにおける残りの係数が有界になることが保証される。
2. 正則化された不一致とドリフト： 各符号化された制限に対して、正則化された不一致関数 $Z_c^\varepsilon(x)$ が定義される。この関数は、負のドリフトを誘発するために二次エネルギー項を組み込んでいる。構成においては、ある制限の不一致が閾値を超えた場合、その移動勾配（moving gradient）が後続のステップでブロックされ、さらなる増大が防止されることを保証する。
3. 履歴指数和： 「危険な」制限（閾値付近にあるもの）の数を制御するために、本論文では履歴指数和を導入している。これらの和は、制限が退役（凍結）した後も、その履歴を追跡する。ポテンシャル関数 $\Psi_t$ が維持され、これはすべてのサイズクラスおよび列にわたって、指数和の重み付き指数を集計するものである。
4. 有限ステップ解析： 極限プロセスに依存する可能性のある従来のアプローチとは異なり、本構成は有限のメッシュ $\gamma$ を使用する。著者は、4次までのテイラー展開を用いて、精密な1ステップ指数境界（Theorem 5.3）を導出している。この境界は以下に依存する：
   • アフィン・スペクトル独立性： 符号化された応答の和の共分散を制御するため。
   • 負の曲率： 立方体の境界付近の「バッファ」によって提供され、これがポテンシャルの二階微分を負にする。
   • 4次剰余項： 単一ステップにおいて期待値内でポテンシャルが増大しないことを保証するために、一様に有界である。

主要な貢献

• $(\log \log n)$ 因子の除去： 主要な貢献は、Bansal–Jiangの境界に含まれる $(\log \log n)^{7/4}$ 因子の排除であり、結果として $O((\log n)^{1/4})$ の境界を得たことである。
• 明示的な閾値和証明書： 本論文は、サイズクラスにわたる閾値の和に対する明示的かつ正確な数値的証明書を提供している。これにより、最終的な境界において漸近的な値ではなく、精密な定数を得ることが可能となる。
• 規定された深さを持つ部分彩色： 定理1.2は、任意の指定された分数点 $b$ から開始でき、指定された「深さ」$R$ で停止できる部分彩色結果を確立している。これは、残りの分数的な座標の数が、初期の分数的な座標の数を $q$ とすると、高々 $\max\{\lceil q e^{-R} \rceil - 1, 8\}$ に減少することを保証する。
• Leanによる形式化： 有限軌道、正確な閾値和、および最終的な丸めを含む証明全体が、定理証明器であるLeanにおいて形式化されている。唯一の外部仮定はBansal–JiangのTheorem A.4である。

主な結果
本論文は、以下の明示的な境界（Theorem 1.1）を証明している：
$$\text{disc}(A) \le 2395 \left(1 + \log_+ \frac{n}{9}\right)^{1/4} + 2\sqrt{2}$$
ここで $\log_+ t = \max\{0, \log t\}$ である。

さらに、系1.3は、$q$ 個の分数的な座標を持つ任意の開始点 $b$ に対して、既存の符号を保持する符号化 $\sigma$ が存在し、以下を満たすことを示している：
$$\|A(\sigma - b)\|_\infty \le 2395 \left(1 + \log_+ \frac{q}{9}\right)^{1/4} + 2\sqrt{2}$$
$q \le 8$ の場合、直接的なユークリッド丸めにより、境界は $\sqrt{q}$ に改善される。

意義と主張
本論文は、$(\log \log n)$ の対数多項式因子を持たない $O((\log n)^{1/4})$ のレートを達成する、Komlós問題に対する最初の境界を提供したと主張している。4乗根の指数は、生存している集合の次元の対数的な減少と、共分散予算における閾値の4乗とのバランスをとることから生じている。

著者は、構成が「有限」かつ「正確」であり、極限議論を回避していることを強調している。有限のメッシュと明示的な有理定数（例：係数2395）の使用により、厳密でコンピュータ検証可能な証明が可能となっている。本研究は、部分彩色および完全彩色定理を形式化し、Bansal–Jiangの枠組みが、元のスペクトル独立性の議論の構造的完全性を維持しながら、よりタイトで明示的な定数を得るために洗練され得ることを示している。本論文は、Komlós予想（$\log n$ に依存しない定数を必要とする）を解決したと主張するものではないが、対数依存性を単一の根に孤立させることで、それへの重要な一歩を示している。