A structure theorem for sets of small popular doubling

Abstract

In this paper we prove that every set $A\subset \mathbb{Z}$ satisfying the inequality ${\sum }_x\min (1_A\ast 1_A(x),t)\le (2+\delta )t|A|$ for $t$ and $\delta$ in suitable ranges, then $A$ must be very close to an arithmetic progression. We use this result to improve the estimates of Green and Morris for the probability that a random subset $A\subset \mathbb{N}$ satisfies $|\mathbb{N}\setminus (A+A)|\ge k$; specifically we show that $\mathbb{P}(|\mathbb{N}\setminus (A+A)|\ge k)=\Theta (2^{-k/2})$.