Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.