论文标题
带有大本集的小子集：超越考奇 - 戴文波特的绑定
Small subsets with large sumset: Beyond the Cauchy--Davenport bound
论文作者
论文摘要
For a subset $A$ of an abelian group $G$, given its size $|A|$, its doubling $κ=|A+A|/|A|$, and a parameter $s$ which is small compared to $|A|$, we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$.我们表明，最多可以找到$ s $的子集$ a'\ subseteq a $大小，以便$ | a+a'| =ω（\ min（κ^{1/3}，s）| a |）$。因此，假设加倍$κ$很大，可以通过有限的尺寸子集来保证大于cauchy-davenport结合的集群。我们以相同的想法为基础，我们解决了Bollobás，Leader和Tiba的猜想，该猜想是$ a，b $ a $ a $ \ mathbb {z} _p {z} _p $的大小，最多是$αp$，适用$α> 0 $，只需要三个元素$ b_1，b_2，b_2，b_2，b_2，b_2，b_2，b_2，b_2，b_2，b_2，b_3 $ | a+\ {b_1，b_2，b_3 \} | \ ge | a |+| b | -1 $。允许使用较大的子集$ a'$，我们表明，对于$ a $ a $的界定加倍，只需要一个带有$ o（| a |）$元素的子集$ a'$即可保证$ a+a+a'= a+a $。我们还谈到了Bollobás，Leader和Tiba提出的另一个猜想，并在高维模拟和集合上提出了一个界定的集合，其集合不能被界面尺寸子集饱和。
For a subset $A$ of an abelian group $G$, given its size $|A|$, its doubling $κ=|A+A|/|A|$, and a parameter $s$ which is small compared to $|A|$, we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$. We show that a subset $A'\subseteq A$ of size at most $s$ can be found so that $|A+A'| = Ω(\min(κ^{1/3},s)|A|)$. Thus a sumset significantly larger than the Cauchy--Davenport bound can be guaranteed by a bounded size subset assuming that the doubling $κ$ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of $\mathbb{Z}_p$ of size at most $αp$ for an appropriate constant $α>0$, one only needs three elements $b_1,b_2,b_3\in B$ to guarantee $|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$. Allowing the use of larger subsets $A'$, we show that for sets $A$ of bounded doubling, one only needs a subset $A'$ with $o(|A|)$ elements to guarantee that $A+A'=A+A$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogs and sets whose sumset cannot be saturated by a bounded size subset.
