数学联邦政治世界观
超小超大

最大的“无和”集 (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),接着再看更方便。

相关小说

再见,亦是千年时 连载中
再见,亦是千年时
叶璇林
本文《再见,亦是千年时》采用“奇迹暖暖”的装扮以及一些幻想图结构出的一篇文。我会不定时更新。“你可以生我气,但你能不能,别不要我”男主:陌清......
6.5万字8个月前
文野乙女小甜饼短篇 连载中
文野乙女小甜饼短篇
陆浅_
「荼蘼园」荼蘼花开,故人归来。文野乙女,小甜饼居多,短篇段子。
10.1万字8个月前
神兵小将之浅红之菱 连载中
神兵小将之浅红之菱
天心恋
鲜艳的玫瑰沾上点点露珠,我的心也砰砰直跳。这是什么样的感觉?年少时的悸动,将在长大后继续下去,因为……我爱你!在穿越到另外一个世界后,神兵小......
7.0万字8个月前
清冷校花的所有物 连载中
清冷校花的所有物
忧郁小锤少
giantess系列文章Q群:355392666封面背景:不时轻声地以俄语遮羞的邻座艾莉同学
0.3万字8个月前
红莲业火:神凰血脉 连载中
红莲业火:神凰血脉
白衣折扇醉无忧
华发雪眉,血色瞳眸,绝世容颜。天生神凰,双翅一展,焚尽余孽。天生的美人,天生的神力。注定的相遇,注定的相离。注定要抉择,注定要孤独。注定的杀......
17.3万字8个月前
月光下的魔术师(新快) 连载中
月光下的魔术师(新快)
梦醒伤人
新快的日常
0.6万字8个月前