On the largest sum-free subset of the lattice cube

Peter Keevash と Jeck Lim による論文「On the largest sum-free subset of the lattice cube（格子立方体における最大の和フリー部分集合について）」の詳細な技術的概要を以下に示す。

1. 問題の定義

本論文は、$d$ 次元格子立方体における最大の和フリー部分集合の漸近密度を決定する問題に取り組んでいる。

• 定義: アーベル群の部分集合 $S$ が和フリーであるとは、$x, y, z \in S$ なる $x + y = z$ が存在しないことをいう。著者らは格子立方体 $[n+1]^d = \{0, 1, \dots, n\}^d$ の部分集合を研究する。
• 目的: $S$ を最大の和フリー部分集合としたとき、極限 $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$ を決定すること。
• 背景:
  • $d=1$ の場合、$c_1 = 1/2$ であることはよく知られている。
  • $d=2$ の場合、Elsholtz と Rackham によって $c_2 = 3/5$ が証明された。
  • $d=3, 4$ の場合、Lepsveridze と Sun が最近これらのケースを解決した。
  • 予想: すべての $d$ に対して、最適な集合は超平面によって定義される立方体の「スライス」であると予想されていた。具体的には、スライスの体積を最大化するように選んだ $u$ に対して、集合 $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$ が最大密度を与えるというものである。
  • 連続極限 $[0,1]^d$ におけるそのようなスライスの最大体積を $c^*_d$ とする。この予想は $c_d = c^*_d$ であると述べている。

2. 手法

証明は Lepsveridze と Sun によって確立されたアプローチに従い、線形計画の双対性と**確率的結合（joint mixability）**の組み合わせを利用している。

A. 線形計画への帰着

$|S|$ の上限を評価する問題は、線形計画（LP）問題として再定式化される。

• 主問題: 任意の $x, y, z$ に対して $x+y=z$ ならば $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$ という制約の下で、$\sum |S(x)|$（ここで $S(x)$ は集合 $S$ のファイバー）を最大化する。
• 双対問題: 上限を得るためには、双対 LP の実行可能解（重み）を構成しなければならない。そのような重みの存在は、特定の確率分布を結合（coupling）できる能力に依存する。

B. 結合可能性（Joint Mixability）

核心的な技術的革新は、結合可能性の結果の証明にある。

• 定義: 分布 $\mu_1, \mu_2, \mu_3$ が結合可能（jointly mixable）であるとは、これらの周辺分布を持つ結合 $(X_1, X_2, X_3)$ が存在し、$X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ がほとんど至る所で成り立つことをいう。
• 主要な定理（定理 1.5）: 著者らは、非負整数 $r, s, t$ が $r+s+t = dn$を満たす任意の場合について、離散スライス$L_d(r), L_d(s), L_d(t)$（ここで$L_d(k) = {x \in [n+1]^d : \sum x_i = k}$）上の一様分布が結合可能であることを証明する。
• 証明手法:
  • $d$ に関する帰納法: 基底ケース $d=2$ は、区間と三角不等式に関する既知の結果に依存する。
  • 帰納ステップ（$d \ge 3$）: 著者らは、最初の座標に対する結合を、不動点定理（ブラウワーの不動点定理またはペロン・フロベニウスの定理）を用いた固定点論法によって構成する。彼らは最初の座標のサポート上の確率分布の空間に写像を定義し、不動点が存在することを示す。この不動点は、周辺分布がスライス上の必要な一様分布と一致することを保証し、帰納法の仮定を残りの $d-1$ 個の座標に適用可能にする。

C. 重みの構成とスライスの評価

双対 LP に結合可能性を適用するために:

1. 分割: 領域 $[n+1]^{d-1}$ を、最適スライスパラメータ $u^*_d$ に対する座標の和に基づいて 5 つの集合（$A, B, C, D, E$）に分割する。
2. 重み関数: 結合可能性の結果を用いて、これらの集合の特定の三つ組の集合上でサポートを持つ重み関数 $w(x,y,z)$ を構成する。
3. 解析的評価: 彼らは、一様確率変数の和の確率密度関数（Irwin-Hall 分布）の対数凹性の性質を利用する。構成された重みが双対制約を満たすことを保証するために、スライス体積の比に関する明示的な上限（補題 3.1）を導出する。
   • $d$ が大きい場合、大偏差評価を用いる。
   • $d$ が小さい場合（$5 \le d < 200$）、不等式を数値的に検証する。

3. 主要な貢献

1. すべての $d$ に対する予想の解決: 本論文は、すべての次元 $d \ge 1$ に対して $c_d = c^*_d$ であることを証明する。これにより、最適な和フリー部分集合が実際に超平面 $\sum x_i \in [u^*_d n, 2u^*_d n)$ によって定義されるスライスであることが確認された。
2. 一般結合可能性定理: 定理 1.5 の証明は、確率論および組合せ論への重要な貢献である。これは、定数和となるハイパーキューブの離散スライス上の一様分布が結合可能であることを確立するものであり、特定の低次元に対する既存の知見を一般化するものである。
3. Lepsveridze-Sun 手法の精緻化: 著者らは、$d=3,4$ に対して用いられた手法を任意の次元に一般化し、不動点論法による厳密な帰納的構成を通じて高次元における結合の構築の複雑さを克服した。

4. 主要な結果

• 定理 1.1: 任意の $d \ge 1$ および任意の和フリー部分集合 $S \subseteq [n+1]^d$ に対して、そのサイズは以下によって抑えられる:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  ここで $c^*_d$ はスライス $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$ の最大体積である。
• 系: 極限密度は最適スライスの体積に等しく、Cameron、Green などが提起した自然な予想が解決された。

5. 意義と拡張

• 組合せ数論: この結果は、高次元格子における和フリー集合の構造に関する長年の未解決問題を解決する。それは、スライス構成が低次元だけでなく、普遍的に最適であることを確認するものである。
• 確率的手法: 本論文は、極値組合せ問題を解決する上で、結合可能性および結合手法の威力を実証している。不動点定理を通じた結合の帰納的構成は、新規かつ堅牢な手法である。
• 一般凸集合: 著者らは、この「スライス」の最適性が一般の凸集合に対して成り立つかどうかについて簡単に議論している。彼らは、十分大きな $d$ に対して、最大の和フリー部分集合が線形汎関数によって定義される単一のスライスではないような凸集合が存在することを示す反例（命題 5.1）を提供する。これは、スライスの最適性にはハイパーキューブの対称性が決定的に重要であることを浮き彫りにしている。
• 未解決問題: 本論文は、次元 $d=2$ におけるすべての有界凸集合に対してスライスの最適性が成り立つかどうかという問いを未解決のまま残している。

要約すると、本論文は格子立方体における最大の和フリー部分集合の漸近密度に対する完全な解を提供し、既存の部分的な結果を統合するとともに、任意の次元を扱うための強力な確率的ツールを導入している。