最大的“无和”集 (4-1)

我和朋友Shukun在去年年初一起写的文章The largest (k,l)-sum-free subsets[1]最近刚被接收，刚好借这个机会介绍一下这个结果。这篇文章中研究的问题最早可以追溯到1965年Erdos提出的一个重要的问题：任意一个包含 N 个整数的集合，它最大的无和子集能有多大？

我们先给出所谓的“无和”集（sum-free set）的定义：一个集合A 是sum-free的，如果对于 A 中任意三个元素 x，y，z ，我们都会有 。关于 sum-free set 的研究最早要追溯到对费马大定理的研究，以及哥德巴赫猜想，可以参见我之前写的blog：

假设A＝{1，2，. . .，N} 是前 N 个整数，那么 A 中最大的sum-free set有多大呢？可以很简单的证明，当取 A 中的全部奇数，或者取 A 的后一半区间时，我们会得到一个 A 的sum-free子集，并且这样选取的子集是最大的。也就是说，对于集合 {1，. . .，N} ，它的最大 sum-free 子集大小为 N/2 左右。但是对于一般的 N 元集合 A ，我们通常是取不到这么大的sum-free子集的。

那么，对于任意包含N 个元素的整数集合 A ，它包含的最大sum-free子集至少有多大呢？用精巧的概率方法，Erdos给出了一个下界： N/3 ，证明如下。

证：考虑一维环面 𝕋 ，我们可以将 𝕋 等距嵌入区间 [0，1] ，并且取 Ω＝(1/3，2/3) 。对任意 x∈𝕋 ，定义 Aₓ＝{α ∈ A：αx ∈ Ω} ，显然 Aₓ 是sum-free集合。又由于

N

𝔼ₓ∈𝕋|Aₓ|＝∫𝕋 ∑1Ω(xn)dx＝──，

n∈A 3

根据抽屉原理，存在 x∈𝕋 使得 |Aₓ|＞N/3 ，证毕。

Eberhard，Green，和Manners在2014年[2]通过应用arithmetic regularity lemma以及精巧的调和分析技术，构造了无穷多个 N 元集，其中选取超过 N/3＋ο(N) 个元素，一定会产生一组sum。这篇文章解决了Erdos问题的上界：也就是说，目前我们得到的结果是，对任意 N 元集合，它包含的最大sum-free集合的大小至少是 N/3 ，至多是 N/3＋ο(N) 。

接下来剩下的问题就是确定下界，因为[公式] 这个界看起来是取不到的。下面的猜想被很多人提出过，并且Tao和Vu认为它是加法组合领域最重要的猜想之一：

Conjecture

存在函数 ω(N) → ∞ 当 N → ∞ ，使得对任意包含 N 个正整数的集合，它包含的最大sum-free子集至少是 N/3＋ω(N) 。

上面提到过，Erdos证明了下界至少是N/3 ，Alon和Kleitman证明了下界至少是 (N＋1)/3 ，Bourgain证明了下界至少是 (N＋2)/3 ，这个也是目前这个问题的最佳结果。

另一方面，我们定义更一般的(k,l)-sum-free set：一个集合A 是(k,l)-sum-free的，如果对任意 A 中的k+l个元素 x₁，. . .，xₖ，y₁，. . .，yₗ 我们都有

ₖ ₗ

∑ xᵢ ≠ ∑ yⱼ。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。