Counting sets with small sumset and applications

Publication date 22 February 2018

Abstract: We study the number of

k

-element sets

A s u b s e t 1, l d o t s, N

with

| A + A | l e q 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 s u b s e t m a t h b f Z / N m a t h b f Z

with

| A + A | l e q c | A |^{2}

, we deduce that the random Cayley graph on

m a t h b f Z / N m a t h b f Z

with edge density~

f r a c 12

has no clique or independent set of size greater than

, asymptotically the same as for the ErdH{o}s-R'enyi random graph. This improves a result of the first author from 2003 in which a bound of

160 l o g_{2} N

was obtained. As a second application, we show that if the elements of

A s u b s e t m a t h b f N

are chosen at random, each with probability

1 / 2

, then the probability that

A + A

misses exactly

k

elements of

m a t h b f N

is equal to

as

k o i n f t y

.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Counting sets with small sumset and applications