# Sumset using first moment method

This is problem 1.1.6 from the book "Additive Combinatorics" by Tao and Vu.

Suppose A is a subset of an additive group Z. We need to show that there exists a d-element subset of Z, denoted B = { v1, v2, ... vd } with d = O( log |Z|/|A| ) such that A + FS(B) is of size at least |Z|/2. ( FS(B) is the subset sums of B)

So I tried taking a random d-element subset of Z and a specific z in Z so that I can bound the probability that z is contained in A + FS(B) and then apply the first moment to get a bound on the average size of the set. But I am unable to get a bound. Please help if possible. (This is not part of any homework.)

-

Hint: try an inductive construction rather than a random construction. Picking $z\in Z$ uniformly, the expected order of $A \cup (A+z)$ is what?
Sum-free is too strict - there are sparse sets $A$ such that $A-A=Z$. But you can get $|A+FS(B)|\geq |A|c^{|B|}$ for some constant $c>1$ by answering my second hint above. – Colin McQuillan Jun 29 '12 at 21:04