Dense sets without large sumsets

Abstract

We prove, for all fixed $0<\delta <1$, and all sufficiently large $n$, that there exists $S\subset [n]$ with $|S|\ge \delta n$ such that $A+B\not\subset S$ for all $A,B\subset \mathbb{N}$ satisfying $$\min \{|A|,|B|\}\ge (3+o(1))\frac{\log n}{\log (1/\delta )}.$$ A very recent result of Hernández and Hetzel shows that our bound is sharp up to a factor of 3, and together our results settle a conjecture of Kra, Moreira, Richter, and Robertson. In fact, we prove that a $\delta$-dense random subset of $[n]$ is a valid choice for $S$ with high probability, and that one can take $n^{-\alpha }\le \delta \le 1-c$ where $c>0$ is fixed and $\alpha >0$ depends only on the $o(1)$ error, answering another question of the same authors in a strong form.

arXiv commentMinor adjustments for journal submission