Hitting Arithmetic Progressions at the Square-Root Scale

技術要約：平方根スケールにおける算術級数の捕捉

問題設定
本論文は、集合 $A \subseteq \{0, 1, \dots, N-1\}$ の中で、区間内に含まれるすべての $k$ 項算術級数（AP）と交差する最小の濃度 $f(N, k)$ を調査している。この問題は、進行なし集合（progression-free sets）に関する古典的な極値問題の補集合である。$f(N, k)$ の挙動は、$k$ が固定されている場合（Szemerédiの定理により $f(N, k) = N - o(N)$）、および $k$ が $N$ の累乗として成長する場合（$f(N, k) \ll N^{1-\epsilon}$）についてはよく理解されているが、本論文は $k \approx \sqrt{N}$ である「平方根スケール」の領域、すなわち $N = n^2$ かつ $k \approx n$ という遷移点に焦点を当てている。この地点では、単純な構成法（素数の倍数など）が、自明なブロック下限値に自動的に一致しなくなる。

手法
本論文は、初等的な組合せ論的議論、数論的補題、および確率的構成法の組み合わせを用いている。

• 下限値: 証明は、区間 $[0, n^2-1]$ を長さ $k$ の連続するブロックに分割することに基づいている。著者らは、「シングルトン・ラン（singleton runs）」、すなわち選択された点がちょうど1つだけ含まれる連続したブロックの列を分析している。これらの点の相対的な位置に基づく「降下列（descent sequence）」を定義することにより、著者らは強い除数制約を導き出している。主要な構成要素は「降下合同性補題（Descent Congruence Lemma）」（補題2.2）であり、これは非定数な降下列が二次的な総質量を持つことを確立するものである。この補題と有限合同論を組み合わせることで、ヒット集合のサイズが自明な境界を特定の二次の項によって超えることを強制している。
• 上限値: 上限値の構成は、「ランダム化されたフロント（randomized front）」法とそれに続く変更ステップを利用している。区間 $[0, p^2-1]$ は、行と列のグリッドとして捉えられる。構成法は、「フロント」の行を用いることで、大きな公差および特定の剰余類を決定論的にカバーする。残りの進行（上部の行に限定された小さな公差を持つもの）については、点のランダムな割り当てが使用される。著者らは、漏れた進行の期待値を計算し、その期待値が、無視できる程度の数の点を追加することによって修復できるほど十分に小さいことを示す。

主要な貢献と結果

1. 改善された臨界下限値 (Theorem 1.1):
   著者らは、$f(n^2, n)$ の下限値における第二次の項の主要定数を改善した。Trussは以前 $f(n^2, n) > n + \frac{1}{2}n^{1/2} - 2$ であることを証明したが、本論文は以下を確立する：
   $$f(n^2, n) \ge n + \left(\frac{1}{\sqrt{2}} + o(1)\right)n^{1/2}$$
   この結果は、長いシングルトン・ブロックの連続における降下列の制約を分析することによって導かれる。

2. 一般化された臨界未満の下限値 (Theorem 1.2):
   結果は、$k = n - \theta n^{1/2} + O(1)$ （ただし $\theta \ge 0$ は固定された定数）の領域へと拡張される。本論文は以下を証明する：
   $$f(n^2, k) \ge \left\lfloor \frac{n^2}{k} \right\rfloor + \left( \frac{\sqrt{\theta^2 + 2} - \theta}{2} + o(1) \right) n^{1/2}$$
   この公式は、臨界スケールと $k$ が $n$ よりわずかに小さい領域との間を補間する。

3. より強い漸近的上限値 (Theorem 1.3):
   素数平方のケース $N=p^2, k=p$ において、著者らは $2p-2$ という従来の境界（Brown and Freedman）およびその後の対数的な節約を改善する。彼らは以下を証明する：
   $$f(p^2, p) \le 2p - \left(\sqrt{\frac{2}{3}} - o(1)\right)\sqrt{\frac{p}{\log p}}$$
   これは、変更ステップを伴うランダム化されたフロント構成を通じて達成され、$\sqrt{p/\log p}$ のオーダーの項を節約している。

4. 遷移点の分析 (Proposition 1.4):
   本論文は、$k = N^{1/2}$ が遷移点であることを確認している。$k = N^c$ で $c > 1/2$ の場合、関数は $f(N, k) = (1+o(1))N/k$ として振る舞い、自明なブロック下限値と一致する。平方根スケールは、単純な素数剰余構成が自動的にこの境界に一致しなくなる閾値として特定されている。

意義と主張
本論文は、Trussによる下限値の定数を発表以来初めて改善したと主張しており、平方根スケールにおけるヒット集合のサイズに関する理解を精緻化している。上限値の側面においては、素数平方のケースに対するより強い漸近的な結果を提示しており、$\sqrt{p/\log p}$ を含む項によって、下限と上限の間のギャップを狭められることを示している。著者らは、下限値の証明は降下列の除数特性に依存する初等的なものである一方、上限値は決定論的な修復ステップを伴う確率的手法に依存していることを強調している。本研究は、進行なし集合およびヒット集合の定量的推定という、加法的組合せ論のより広い文脈の中に位置づけられる。