Counting sets with small sumset and applications
We study the number of $k$-element sets $A \subset \{1,\ldots,N\}$ with $|A + A| \leq K|A|$ for some (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$....
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
2013
|
| _version_ | 1826293047869046784 |
|---|---|
| author | Green, B Morris, R |
| author_facet | Green, B Morris, R |
| author_sort | Green, B |
| collection | OXFORD |
| description | We study the number of $k$-element sets $A \subset \{1,\ldots,N\}$ with $|A + A| \leq K|A|$ for some (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}/N\mathbf{Z}$ with edge density~$\frac{1}{2}$ has no clique or independent set of size greater than $\big( 2 + o(1) \big) \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$ was obtained. As a second application, we show that if the elements of $A \subset \mathbf{N}$ are chosen at random, each with probability $1/2$, then the probability that $A+A$ misses exactly $k$ elements of $\mathbf{N}$ is equal to $\big( 2 + o(1) \big)^{-k/2}$ as $k \to \infty$. |
| first_indexed | 2024-03-07T03:24:04Z |
| format | Journal article |
| id | oxford-uuid:b86abc16-fe93-43b0-9c20-9593ab538229 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:24:04Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | oxford-uuid:b86abc16-fe93-43b0-9c20-9593ab5382292022-03-27T04:55:47ZCounting sets with small sumset and applicationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b86abc16-fe93-43b0-9c20-9593ab538229Symplectic Elements at Oxford2013Green, BMorris, RWe study the number of $k$-element sets $A \subset \{1,\ldots,N\}$ with $|A + A| \leq K|A|$ for some (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}/N\mathbf{Z}$ with edge density~$\frac{1}{2}$ has no clique or independent set of size greater than $\big( 2 + o(1) \big) \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$ was obtained. As a second application, we show that if the elements of $A \subset \mathbf{N}$ are chosen at random, each with probability $1/2$, then the probability that $A+A$ misses exactly $k$ elements of $\mathbf{N}$ is equal to $\big( 2 + o(1) \big)^{-k/2}$ as $k \to \infty$. |
| spellingShingle | Green, B Morris, R Counting sets with small sumset and applications |
| title | Counting sets with small sumset and applications |
| title_full | Counting sets with small sumset and applications |
| title_fullStr | Counting sets with small sumset and applications |
| title_full_unstemmed | Counting sets with small sumset and applications |
| title_short | Counting sets with small sumset and applications |
| title_sort | counting sets with small sumset and applications |
| work_keys_str_mv | AT greenb countingsetswithsmallsumsetandapplications AT morrisr countingsetswithsmallsumsetandapplications |