Dense ascending waves: A resolution of the Alon-Spencer conjecture

技術要約：高密度上昇波とAlon–Spencer予想の解決

問題提起
本論文は、整数の高密度部分集合内における「上昇波（ascending waves）」に関する極値組合せ論の問題を扱う。正の整数 $n$ に対し、$[n] = \{1, \dots, n\}$ とする。整数からなる厳密に単調増加な数列 $x_1 < \dots < x_k$ が、隣接する差が非減少である（すなわち $x_{t+1} - x_t \ge x_t - x_{t-1}$）とき、これを「上昇波」と定義する。

$g(n)$ を、密度が少なくとも $1/2$ であるすべての部分集合 $A \subseteq [n]$（すなわち $|A| \ge n/2$）が長さ $k$ の上昇波を含むような最大の整数 $k$ とする。AlonとSpencerは、十分に大きな $n$ に対して以下が成り立つことを以前に示した：
$$c_1 \frac{(\log n)^2}{\log \log n} \le g(n) \le c_2 (\log n)^2$$
彼らは、下界における $\log \log n$ という因子は本質的なものではなく、$g(n) = \Theta((\log n)^2)$ であると予想した。本論文の主な目的は、この下界を確立することでこの予想を証明することである。

手法
本証明は、直接的な貪欲法による解析の限界を克服するために、位相空間力学（phase-space dynamics）と決定論的なパッキング議論の新規な統合を採用している。著者は、以前の試みにおいて、数列の初期段階で発生した「投影誤差（projection errors）」が、複数の暫定的な軌道を単一のギャップへと集中させてしまい、ヒット事象に対する独立な確率論的取り扱いを無効にしていたことを指摘している。

これを解決するため、本論文は以下の枠組みを導入する：

1. 位相空間力学とシャドウ写像（Shadow Map）：
   著者らは、位置 $u$ と差 $d$ を成分とする位相点 $p = (u, d) \in \mathbb{R}^2$ を定義する。そして、$T(u, d) = (u+d, d + 2\rho(u+d))$ で定義される「シャドウ写像」$T: D \to X$ を導入する。ここで $\rho(z)$ は集合 $A$ への $z$ のオーバーシュート（overshoot）である。

• 主要な性質： 写像 $T$ は、面積保存型（ルベーグ測度保存型）かつ可逆なボレル同相写像である。
• 意義： 投影誤差 $\rho$ を第二の状態変数として保持することで、力学系は可逆となる。これにより、「集束」現象（多くの軌道が単一のギャップに衝突する現象）を、位相空間における決定論的なパッキング問題へと変換できる。ここでは、固定されたギャップへの繰り返しの「アクティブなヒット」は、互いに素な像のスライスに対応する。

2. 局所平方エネルギー定理（第3節）：
   著者は、スケール $D$ における区間 $I$ の「短ギャップ平方エネルギー（short-gap square energy）」$E_D^<(I)$ を定義する。著者は、局所的な窓 $J$ が十分に低い平方エネルギーを持つ場合（具体的には $E_D^<(J) \le \epsilon D$）、制御された差を持つ長さ $L$ の局所的な上昇波を生成する開始点が $J$ 内に存在することを述べる局所定理（定理3.2）を証明する。

• この証明は、任意のギャップ $G$ に対するアクティブなヒットの総位相空間面積が $5D|G|$ によって抑えられるという「パッキング推定（Lemma 3.1）」を利用している。これにより、エネルギー境界から、オーバーシュート閾値 $D$ を超えることを回避する有効な軌道の存在へと変換することが可能になる。

3. グローバル・スケール選択とマルチスケール・スプライシング（第4節）：
   グローバルな波を構成するために、著者はスケールの列 $D_i = 2^i$ を選択し、多くのスケールにおいて「適格（admissible）」である「共通の開始点」$x^*$ を特定する。

• 適格性： 点がスケール $i$ において適格であるとは、境界内に留まり、大きなギャップを避け、かつ局所平方エネルギーが低いことを指す。
• 選択： ギャップの集合と点の集合に対する平均化議論を用いることで、サイズ $|I| \ge \frac{1}{32} \log n$ のスケールの集合 $I$ において適格な点 $x^*$ が存在することを証明する。
• スプライシング： 幾何学的に間隔を空けた（因子 $Q=128$ で配置された）スケールの部分集合 $I'$ を選択することで、局所定理を反復的に適用する。この大きな分離により、新しい局所的な波の「ブリッジ（橋渡し）」となる差が、前の波の最終的な差よりも大きくなり、連結時にも上昇波の性質が維持される。

主要な貢献と結果

• 予想の解決： 本論文は定理1.2を証明する。すなわち、ある絶対定数 $c > 0$ が存在し、密度が少なくとも $1/2$ であるすべての集合 $A \subseteq [n]$ は、少なくとも $c(\log n)^2$ の長さの上昇波を含む。
• 漸近的なタイト性： AlonとSpencerによる上界と合わせることで、$g(n) = \Theta((\log n)^2)$ であることを確立し、予想1.1を裏付けた。
• 手法の革新性： 本論文は、依存関係のあるヒット事象を扱う問題を、決定論的な面積保存問題へと持ち上げる位相空間のリフト（phase-space lift）を導入している。これにより、従来の解析における独立性の仮定に起因する「対数的損失（logarithmic loss）」を回避している。
• 明示的な構成： 証明は構成的な性質を持ち、純粋な確率論的な存在証明ではなく、特定のエネルギーおよびギャップ条件を満たす点の存在に依拠している。

意義
本論文は、高密度上昇波における下界の「対数的損失」を取り除いたと主張している。これはAlonとSpencerの研究以来、未解決であった問題である。その意義は、単なる定量的改善にとどまらず、手法の質的な転換にある。すなわち、独立性の仮定を、決定論的で面積保存的な力学系のアプローチへと置き換えた点にある。この手法は、位相空間における幾何学的なパッキングを通じて、軌道の集束を制御するものである。この結果は、高密度集合における上昇波関数の漸近的挙動を確定させ、それを $(\log n)^2$ の領域へと確実に関連付けた。