0
$\begingroup$

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.)

1 Answers 1

0

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?

  • 0
    I get it now :) Thanks for the hint. Need to work out the details though.2012-06-30