A sharp 5/8 bound for an Erd\H{o}s-Sós pairwise-sums problem

技術的要約：Erdős–Sósのペア和問題における鋭い 5/8 の上界

問題文
本論文は、ペア和に関するErdős–Sós予想の特定のケースを扱っている。$f_3(N)$ を、$A \subseteq \{1, \dots, N\}$ という部分集合において、$|A| \geq f_3(N)$ であるすべての $A$ が、互いに異なる要素 $a, b, c \in A$ であり、かつそれらのペア和 $a+b, a+c, b+c$ がすべて $A$ に含まれるという条件を満たすものを含むような最小の整数とする。このような集合は、「ペア和三重つ自由（pairwise-sum triple-free）」と呼ばれる（そのような三重が存在しない場合）。中心となる問題は、$f_3(N)$ の漸近的挙動を決定することである。

本研究以前には、標準的な構成法 $A = [\frac{N}{8}, \frac{N}{4}] \cup [\frac{N}{2}, N]$ により、$f_3(N) \geq \frac{5}{8}N + O(1)$ であることが示されていた。本研究の目的は、この一致する上界を証明し、Erdős Problem 865を解決して、正確な漸近定数を確立することである。

手法
証明は自己完結的であり、組合せ論的帰納法、加法的数論、および「折り畳み（folding）」技術の組み合わせに基づいている。手法は以下の主要なステップに従って進行する：

1. 折り畳まれた加法的補題 (Lemma 2.1):
   著者らはまず、「折り畳まれた」区間に関する補題を確立する。$B \subseteq \{1, \dots, m-1\}$ が、異なるペアの和が $m$ または $B$ の他の要素（mod $m$）に等しくならないとき、この補題は $B$ のサイズを衝突集合 $C(B)$ に対して抑える。具体的には、$|B| - |C(B)| \leq \frac{m}{4} + 2$ であることを証明する。証明では、反射対称性 ($B \to -B$) と $|B|$ に関する帰納的な議論を用い、最小の2つの要素の和が $C(B)$ に含まれるか否かのケースを分析する。

2. 折り畳み補題 (Lemma 3.1):
   著者らは、ピボット要素 $h \in A$ の周りでの「折り畳み」操作を導入する。集合 $A$ を、$h$ より小さい要素からなる集合 ($X$) と、$r < h$ となる $h+r$ の形の要素からなる集合 ($Y$) に分割することで、$A$ のサイズを、交わり $B_h = X \cap Y$ の構造に関連付ける。この補題は、$A$ が三重つ自由であれば、$|X| + |Y|$ の和が $\frac{5}{4}h - |E \setminus C(B_h)| + 1$ によって抑えられることを示す。ここで $E$ は区間 $[1, h-1]$ における「ギャップ」を表す。このステップは、大域的な集合サイズの境界問題を、$h$ を法とする局所的な加法的性質の分析へと実質的に還元する。

3. 帰納的上界 (Section 4):
   主定理は、$N=2H$ としたときの $H$ に関する強帰納法によって証明される。証明は、区間の下半分における最大要素と上半分における最小要素の間のギャップに基づいて、2つのケースに分割される：

   • ケース 1 ($s \leq 4e$): 集合は、上半分の最小要素である $h = q$ の周りで折り畳まれる。著者らは、下半分と上半分 $A$ の間のギャップが、十分な数の「欠落した」要素 ($|E \setminus C(B_h)|$) を強制することを示す。
   • ケース 2 ($s > 4e$): 集合は、下半分の最大要素である $h = p$ の周りで折り畳まれる。ここでは、大きなギャップが集合の下半分が疎であることを意味する。著者らは、下半分のセグメントに対して帰納仮説を適用し、これを折り畳み補題と組み合わせることで、境界を導出する。

主要な貢献と結果

• 鋭い上界: 本論文は、すべての $N$ について、$|A| \geq \frac{5}{8}N + C$ （ある絶対定数 $C$ に対して）を満たすすべての部分集合 $A \subseteq [1, N]$ が、ペア和三重を含むことを証明している。
• Erdős Problem 865の解決: 新しい上界を既存の下界構成と組み合わせることで、本論文は $f_3(N) = \frac{5}{8}N + O(1)$ であることを確立し、Erdős Problem 865を解決した。これにより、定数 $5/8$ が最適であることが確認された。
• 形式化: 著者らは、より粗い境界から鋭い境界への簡約の、以前の条件付きバージョンが Lean 4/Mathlib で形式化されていることを述べている。この形式化は "sorries"（プレースホルダー）や追加の公理を使用せず、簡約ステップの論理的正当性を検証している。
• 洗練された予想: 本論文は、特定の $N \pmod 8$ に対する正確な最大サイズに関して Stijn Cambie によって示唆された、より鋭い予想についても言及しているが、主要な結果は依然として漸近的な $5/8$ の境界である。

意義
本論文は、鋭い $5/8$ の上界を与えることにより、Erdős Problem 865を解決したと主張している。その意義は、既知の構成と、この特定のペア和問題に対する理論的な上限との間のギャップを埋めたことにある。研究は、完全な数学的証明として提示されており、Lean による形式化された簡約によってさらなる厳密さが加えられており、未検証の仮定に依存することなく組合せ論的議論の妥当性を保証している。著者らは、証明が自己完結的であり、すべての暗黙的な定数が絶対的なものであることを明示している。