The typical structure of sets with large sumset

Abstract

Given $m\in \mathbb{N}$ and a $p$-random subset $A\subseteq \mathbb{N}$, we asymptotically determine $\log \mathrm{Pr}(|\mathbb{N}\setminus (A+A)|\ge m)$ for $p$ above the threshold for this property. As an application, we show that a uniformly at random chosen subset $A\subseteq \{1,\dots ,n\}$ of size $k$ such that $|A+A|\le \lambda k$, for $\lambda =o(k^{1/4}/{\log }^{1/2}n)$, with high probability belongs to an arithmetic progression of length $\lambda k/2+o(\lambda k)$. Both proofs are based on a bespoke container argument, exploiting the additive robustness of the considered sets.

arXiv comment24 pages