最大的“无和”集

我和朋友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ⱼ。

ᵢ₌ᵢ ⱼ₌₁

注意这里我们要求 k ≠ l 于是上文中的sum-free在新的定义下也就是(2,1)-sum-free。

关于(k,l)-sum-free问题的研究开始于Bourgain。他证明了上面关于(2,1)-sum-free（即sum-free）的猜想中的情形，对(3,1)-sum-free set 是成立的。另一方面，Eberhard证明了存在无穷多的N 元集合，其最大的(k,1)-sum-free子集至多是 N/(k＋1)＋ο(N) 。应用非标准分析的工具，我们的第一个结果证明了所有(k,l)-sum-free问题的上界：Theorem 1 (J.-Wu, 2021)

存在无穷多 N 元集，其任意

N

───＋ο(N)

k＋l

大小的子集一定包含一组(k,l)-sum。

另一方面，应用调和分析工具，我们证明了sum-free猜想对无穷多的(k,l)-sum是成立的。

Theorem 2 (J.-Wu, 2021)

存在无穷多组(k,l), 使得对任意包含 N 个正整数的集合，它的最大(k,l)-sum-free子集的大小至少是

N log N

───＋────.

k＋1 log log N

可惜的是我们证明的所谓无穷多组(k,l)并不包含我们最想要的(2,1)，因此上文提到的(2,1)-sum-free的猜想还非常open。不过另一方面，我们的结果（以及目前的一篇后续结果[3]）也许为这个猜想提供了一点“信心”：既然猜想对无穷多(k,l)都对，那就很有可能对所有(k,l)都对啦。。

这里我想主要说一下上界的构造（定理1）。这里我们的目的，是对每组 (k,l)，以及无穷多个 N ，都存在一个 N 元集合 A ，使得对任意 ε ，A 中每个大小为

N

───＋εN

k＋l

的子集都包含一组 (k,l)-sum。

这里我们利用了乘法群的阿贝尔性质，或者更一般的，amenable group的性质。考虑(ℕ＞⁰，·) 上的一族 Følner sequence：即一个无穷的有限子集序列 {Fₙ} ，满足对任意正整数 α ，

|Fₙ △ α · Fₙ|

lim ──────＝0

|Fₙ|

直觉上来说，构造一个集合的 sum-free 子集严重依赖于对某个素数余数的分布：比如所有的奇数是sum-free的，所有被3除余1的数是sum-free的，所有被5除余2,3的数是sum-free的，等等。而对于Følner sequence来说，其恰好满足一个很好的整除性，即任意一个相对N 不是很大的数都是集合中大部分数的因子。从这个观点下，可以猜测也许Følner sequence就是我们想构造的集合 A 。接下来我们大概讲以下证明的思路。证明的主要工具来自非标准分析，我们先通过取超极限，把集合连续的映射到超实数中，然后通过分析集合的Loeb measure来推出矛盾。具体的证明细节可以阅读我们paper的第六节和第七节。

对于不了解 nonstandard analysis 的同学简单介绍一下。我们这里用到的是所谓的“cheap nonstandardanalysis”，也就是我们并没有本质的用到拓扑性质，换句话说，通过更精细的计算，实际上是可以避免使用 nonstandard analysis 的；这里主要是为了简化证明。在使用 ultraproduct 之后，我们可以将“有限”的object转化为“无限”的object，而无限object的组合性质通常要比有限的object容易一些。

对于一个自然数中的无穷集合A ，我们定义 A 的multiple upper density

ˉd(A)＝lim sup lim sup ─↓

N → ∞ n →∞

|A∩(N！· [n])|

─────── ←

n

我们先证明了第一个定理：如果一个集合A 是 (k，l) -sum-free的，那么 ˉd(A) ≤ 1/(k＋l) 。这个定理证明用到了Szemeredi定理，以及很多繁杂的初等技术，以及Łuczak-Schoen定理。这里略去不证，有兴趣的读者可以去看paper的第六节。我们这里主要介绍，如何用multiple upper density的信息来证明整个定理。

我们使用反证法 + 概率方法。假设{Fₙ} 为一组 Følner sequence，通过选取子列，我们可以假设对于每个 Fₙ ，我们都可以找到一个 (k，l) -sum-free子集 fₙ 的大小至少是 δ|Fₙ| ，其中 δ＞1/(k＋l) 。取 Fₙ 以及 fₙ 的超极限，分别为 F，f 。定义相应的 Loeb measure μ 。于是我们有 μ(f)＞δ 。并且根据 Łoś 定理， f 在超整数上也是 (k，l) -sum-free的。注意到对超整数上的任意有限子集 X ，我们都有

μ(X) – μ(α · X)＝lim ─↓

|X∩Fₙ| – |X∩α · Fₙ|

───────── ←

|Fₙ|

|Fₙ △ α · Fₙ|

≤ lim ──────＝0

|Fₙ|

(以上也是唯一用到Følner性质的地方)。对于超整数上的每个非0元素x ，定义自然数子集 Aₓ ，满足 Aₓ＝{n：nx ∈ f} 。由于自然数是超实数的子集，并且 f 在超实数中满足 (k，l) -sum-free，于是 Aₓ 是 (k，l) -sum-free的。于是由Fatou引理，我们有

𝔼ˉd(Aₓ)＝𝔼 lim sup lim sup ─↓

N → ∞ n → ∞

|Aₓ∩(N！· [n])

────── ←

n

|Aₓ∩(N！· [n])|

≥ lim inf lim inf 𝔼(───────)

N → ∞ n → ∞ n

1 ₙ

＝lim inf lim inf ─ ∑ ℙ (jN！x ∈ f)

N → ∞ n → ∞ n ⱼ₌₁

1 ₙ

＝lim inf lim inf ─ ∑ ℙ (x ∈ f)

N → ∞ n → ∞ n ⱼ₌₁

1

＝μ(f) ≥ δ＞──，

k＋l

那么根据抽屉原理，存在一个x 使得 Aₓ 的multiple upper density 大于 1/(k＋l) 。这个和上文中任意 (k，l) -sum-free集合 A 都满足multiple upper density至多为 1/(k＋l) 矛盾。

注意：──线与箭头↓、←符号表示，连接的意思！

解释：因为正常划分会导致错乱与复杂的场景因此使用如上（箭头符号、──制表线符号）表示与描述（过程）！

参考

1. Y. Jing and S. Wu. The largest $(k,\ell)$-sum-free subsets. to appear at Trans. Amer. Math. Soc., 2021.

2. S. Eberhard, B. Green, and F. Manners. Sets of integers with no large sum-free subset. Annals of Math. 180, 621–652, 2014.

3. Y. Jing and S. Wu. A note on the largest sum-free sets of integers. arXiv:2011.09963, 2020.

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。