On the number of sets with a given doubling constant

Abstract

We study the number of $s$-element subsets $J$ of a given abelian group $G$, such that $|J+J|\le K|J|$. Proving a conjecture of Alon, Balogh, Morris and Samotij, and improving a result of Green and Morris, who proved the conjecture for $K$ fixed, we provide an upper bound on the number of such sets which is tight up to a factor of $2^{o(s)},$ when $G=\mathbb{Z}$ and $K=o(s/(\log n{)}^3)$. We also provide a generalization of this result to arbitrary abelian groups which is tight up to a factor of $2^{o(s)}$ in many cases. The main tool used in the proof is the asymmetric container lemma, introduced recently by Morris, Samotij and Saxton.

11 pages + 10 page appendix. Minor mistakes and typos from the first version were corrected. arXiv admin note: substantial text overlap with arXiv:1806.03706 by other authors