Three-color van der Waerden numbers grow super-exponentially

技術要約：3色のファン・デル・ヴァールデン数が超指数関数的に増大することについて

問題提起
本論文は、ファン・デル・ヴァールデン数 $w(k; r)$ の増大率を扱っている。この数は、集合 $\{1, 2, \dots, N\}$ のあらゆる $r$ 彩色において、長さ $k$ の単色算術級列（k-AP）が含まれる最小の整数 $N$ と定義される。これらの数の存在はファン・デル・ヴァールデン定理によって保証されているが、その正確な漸近的増大率は、依然として根本的な未解決問題である。

歴史的に、$w(k; r)$ の増大は激しい推測の対象となってきた。固定された $r$ に対して、Erdős は $w(k; 2)$ が超指数関数的に増大する（すなわち $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$）と予想した。逆に、線形指数関数的な増大、具体的には $\lim_{k \to \infty} w(k; r)^{1/k} = r$ を示唆する他の予想も存在した。これまでのところ、 $w(k; r)$ の既知の最良の下界は、主にローヴァス・局所補題（Lovász Local Lemma）や特定の代数的構成から導出されており、$w(k; r) \geq r^{k-1}/(4k)$ や、固定された $r \geq 5$ に対しては $(3r/3)^{(1-o(1))k}$ という形式の境界を与えていた。著者らは、Hunter [20] による先行研究が $r \geq 5$ における線形指数関数予想を論破した一方で、$r=3$ の場合（および小さな固定された $r$ に対する一般的な挙動）については未解決のままであったと指摘している。

手法
著者らは、$w(k; r)$ の下界を確立するために、新しい確率的構成法を開発している。この手法は、主に以下の3つの要素に基づいている。

1. 巡回群における高密度な無級列集合：
   著者らは、$k$ 項の算術級列（k-AP）を含まない巡回群 $\mathbb{Z}_N$ の非常に高密度な部分集合を構成している。これには、巡回群に適応させた Erdős-Turán 構成（底数 $p$ において数字 $p-1$ を持たない整数の集合）の拡張を用いている。決定的なのは、「ヒット集合」（補題 2.8）の存在を証明したことである。これは疎（密度 $\leq \epsilon$）でありながら、巡回群におけるあらゆる $k$-AP と、その要素の一定の割合で交差するものである。これは、素数の集合に対する剰余類をランダムに選択することによって達成される。

2. ローヴァス局所補題（LLL）の結果：
   本論文では、対称版のローヴァス局所補題を用いて、どの $k$-AP も「大きな」割合で単色にならないような彩色が存在することを示す。具体的には、補題 3.3 は、小さな素因数を持たない位数 $N$ の群に対して、頂点に色の部分集合を割り当てることで、どの $k$-AP も単色または「ほぼ単色」にならないようにできることを確立している。

3. ランダム・シフト積構成：
   核となる技術的革新は、洗練された「ランダム・シフト積（random shifted product）」構成（補題 4.2 および 4.3）である。標準的な積彩色（product colorings）は色の数を倍増させるが、この手法は、色の数を固定したまま（あるいは制御された範囲内で増加させつつ）、より小さな群の彩色をより大きな群へと組み合わせることを可能にする。

• メカニズム： $H_1$ の彩色 $c_1$ と $H_2$ の彩色 $c_2$ が与えられたとき、この構成は、$H_2$ への射影のファイバーを独立にシフトし、$H_1$ の基底要素の彩色に基づいて色の置換を行うことで、$H_1 \times H_2$ 上の彩色を定義する。
• 反復プロセス： 著者らはこの構成を反復させている。各ステップにおいて、群 $\mathbb{Z}_{n_{j-1}}$ の彩色と、素数位数の巡回群 $\mathbb{Z}_{q_j}$ の彩色を組み合わせる。この構成は、群のサイズを $k$ に対して指数関数的に増加させる一方で、「良質な」色クラスの密度パラメータに対して「二重指数関数的」な損失をもたらす。これらのパラメータを慎重に調整することで、このプロセスを約 $(\log^* k)/2$ 回反復することができる。

主要な貢献と結果

• 3色における超指数関数的増大：
  主要な結果（定理 1）は、十分に大きな $k$ に対して、3色のファン・デル・ヴァールデン数が次を満たすことを証明している：
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  これは、$w(k; 3)$ が $k$ のいかなる指数関数よりも速く増大することを確立しており、$r \geq 3$ において $\lim_{k \to \infty} w(k; r)^{1/k} = r$ となるという予想を論破している。

• 多色における下界：
  定理 2 は、色の数 $r$ が $k$ に対して大きい場合（具体的には $r \geq (\log k)^{3/\epsilon}$）の領域における下界を提供している：
  $$w(k, r) \geq r^{(1-\epsilon)k \log k}$$
  これは、「多色」領域における従来の境界を改善するものである。

• Erdős-Graham 問題の解決：
  著者らは、カノニカルなファン・デル・ヴァールデン数 $H(k)$（$[N]$ のあらゆる彩色が単色またはレインボーな $k$-AP を含む最小の $N$）を取り上げている。Erdős と Graham は $H(k)^{1/k}/k \to \infty$ となるかどうかを予想した。彼らの $w(k, k-1)$ に関する改良された下界を用いることで、著者らは（定理 3）以下を証明した：
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  これにより、$H(k)$ が超指数関数的に増大することを証明し、Erdős と Graham による未解決問題を解決した。

意義
本論文は、3色以上のファン・デル・ヴァールデン数の増大が超指数関数的であることを主張しており、これはこれらの組合せ論的数に関する理解を根本的に変えるものである。その意義は以下の点にある：

1. 線形指数関数予想の論破： $r \geq 3$ において $w(k; r)$ は $r^k$ のようには振る舞わないことを決定的に示した。
2. 手法の進展： 「ランダム・シフト積」構成の導入により、固定された数の色を維持しながら確率論的議論を反復させることが可能となった。これは、 $r \geq 5$ のために使用された以前のバージョンよりも効率的であると著者らは述べている。
3. カノニカル・ラムゼー理論： 本結果は、カノニカルなファン・デル・ヴァールデン数に関する Erdős-Graham 問題に対して強力な解決を提供し、レインボーな級列を許容する場合であっても、必要な $N$ が以前確立された下界よりも遥かに大きいことを示した。

著者らは、彼らの手法は一般的であるが、ここでの具体的な適用はこれらの下界を確立することに焦点を当てていると述べている。彼らは、これらの構成が他の算術ラムゼー数の新しい境界を得るためにも適用可能であると考えており、それは随伴ノート（companion note）で探求する予定であるとしている。本論文は、正確な増大率や上界を決定することを目的としたものではなく、これまで知られていたものよりも大幅に強い下界を確立することを目指したものである。