On the largest sum-free subset of the lattice cube

以下是 Peter Keevash 和 Jeck Lim 所著论文《论格立方体中最大无和子集》的详细技术总结。

1. 问题陈述

本文探讨了确定 $d$ 维格立方体中最大无和子集渐近密度的问题。

• 定义：阿贝尔群的一个子集 $S$ 被称为无和的，如果不存在 $x, y, z \in S$ 使得 $x + y = z$。作者研究的是格立方体 $[n+1]^d = \{0, 1, \dots, n\}^d$ 的子集。
• 目标：确定极限 $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$，其中 $S$ 是最大的无和子集。
• 背景：
  • 当 $d=1$ 时，已知 $c_1 = 1/2$。
  • 当 $d=2$ 时，Elsholtz 和 Rackham 证明了 $c_2 = 3/5$。
  • 当 $d=3, 4$ 时，Lepsveridze 和 Sun 最近解决了这些情况。
  • 猜想：有人猜想，对于所有 $d$，最优集合是由超平面定义的立方体“切片”。具体而言，集合 $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$（其中 $u$ 的选取旨在最大化切片的体积）能产生最大密度。
  • 令 $c^*_d$ 为连续极限 $[0,1]^d$ 中此类切片的最大体积。该猜想断言 $c_d = c^*_d$。

2. 方法论

证明遵循 Lepsveridze 和 Sun 建立的方法，利用线性规划对偶和**概率耦合（联合可混合性）**相结合的技术。

A. 归约为线性规划

对 $|S|$ 进行界定的问题被重新表述为一个线性规划（LP）问题。

• 原问题：在满足以下约束的条件下最大化 $\sum |S(x)|$（其中 $S(x)$ 是集合 $S$ 的纤维）：对于任意满足 $x+y=z$ 的 $x, y, z$，有 $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$。
• 对偶问题：为了找到上界，必须为对偶线性规划构造一个可行解（权重）。此类权重的存在性依赖于耦合特定概率分布的能力。

B. 联合可混合性

核心的技术创新是证明了联合可混合性结果。

• 定义：分布 $\mu_1, \mu_2, \mu_3$ 被称为联合可混合的，如果存在具有这些边缘分布的耦合 $(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 = dn$的非负整数$r, s, t$，离散切片$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$）：作者利用不动点论证（Brouwer 不动点定理或 Perron-Frobenius 定理）为第一个坐标构造耦合。他们在第一个坐标支撑集上的概率分布空间上定义了一个映射，并证明了不动点的存在。该不动点确保了边缘分布与切片上的所需均匀分布相匹配，从而允许将归纳假设应用于剩余的 $d-1$ 个坐标。

C. 权重构造与切片估计

为了将联合可混合性应用于对偶线性规划：

1. 划分：根据坐标和相对于最优切片参数 $u^*_d$ 的关系，将定义域 $[n+1]^{d-1}$ 划分为五个集合（$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. 意义与扩展

• 组合数论：这一结果解决了一个关于高维格中无和集结构的长期未决问题。它证实了“切片”构造具有普遍最优性，而不仅仅局限于低维情形。
• 概率方法：本文展示了联合可混合性和耦合技术在解决极值组合问题中的强大力量。通过不动点定理归纳构造耦合是一种新颖且稳健的技术。
• 一般凸集：作者简要讨论了这种“切片”最优性是否适用于一般凸集。他们提供了一个反例（命题 5.1），表明对于足够大的 $d$，存在某些凸集，其最大的无和子集不是由线性泛函定义的单个切片。这突显了超立方体的对称性对于切片最优性至关重要。
• 未解决问题：本文留下了一个未解之谜：在维度 $d=2$ 下，切片最优性是否对所有有界凸集都成立。

总之，本文提供了格立方体中最大无和子集渐近密度的完整解，统一了以往的部分结果，并引入了强大的概率工具来处理任意维度。