Counting sets with small sumset and applications

We study the number of $k$-element sets $A\subset \{1,\dots ,N\}$ with $|A + A| \leq K|A|$forsome(fixed)$K > 0$. Improving results of the first author and of Alon, Balogh, Samotij and the second author, we determine this number up to a factor of $2^{o(k)}{N}^{o(1)}$ for most $N$ and $k$. As a consequence of this and a further new result concerning the number of sets $A \subset $\mathbf{Z}$/N$\mathbf{Z}$$with$|A +A| \leq c |A|^2$, we deduce that the random Cayley graph on $\mathbf{Z}\mathrm{/}N\mathbf{Z}$ with edge density~$\frac{1}{2}$ has no clique or independent set of size greater than $(2+o(1)){\log }_{2}N$, asymptotically the same as for the Erd\H{o}s-R'enyi random graph. This improves a result of the first author from 2003 in which a bound of $160 \log_2 N$wasobtained\mathrm{.}Asasecondapplication,weshowthatiftheelementsof$A \subset $\mathbf{N}$$arechosenatrandom,eachwithprobability$1/2$, then the probability that $A+A$ misses exactly $k$ elements of $\mathbf{N}$ is equal to $(2+o(1){)}^{-k\mathrm{/}2}$ as $k\to \mathrm{\infty }$.