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
    Intuitively, it seems like we can inductively build our set B={v1, v2...vd} so that A + FS(B) is sum-free at every step, as long as |A|.2^d is less than |Z|. But I am unable to make this precise or get the |Z|/2 as required.2012-06-29
  • 0
    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.2012-06-29
  • 0
    I get it now :) Thanks for the hint. Need to work out the details though.2012-06-30