Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 0 down vote accepted

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?

share|cite|improve this answer
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. – BharatRam Jun 29 '12 at 20:52
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
I get it now :) Thanks for the hint. Need to work out the details though. – BharatRam Jun 30 '12 at 10:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.