Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is exercise 1.8.1 of Additive Combinatorics.

Problem

Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \Omega ( \log n )$, s.t. $A \cap 2*B = \emptyset$.

Here, $2*B$ means $\{ a + b | a, b \in B, a \neq b \}$.

Strategies:

The dumb thing to try is $P(x \in B) = \frac{\log n}{n}$. Unfortunately, the expected value of $A \cap 2B = \Theta(\log^2 n)$, which is achievable via this example:

$A = ( N + [1 .. k]) \cup (2N + [1..k]) \cup (3M + [1 .. 2k])$

Thus, we can't just uniformly, independently, sample the elements of $B$ from $A$.

The next thing to try is to "segment" $A$ into regions of powers of to, i.e. $[1, 2), [2, 4), [4, 8), ... $. Then try to reason about how many elements to pick from each segment. Nothing interesting has happened from this yet.

Question:

What should I be looking for to solve this problem? (This problem comes from the section on Thin Bases, and the chapter on the Probabilistic Method).

share|improve this question
    
Does the notation $2B$ mean $\lbrace 2b: b \in B \rbrace$ or $\lbrace b + b': b,b' \in B \rbrace$? Even if it's the former, the result seems false as stated: just let $A = \lbrace 1, 2, 4, 8, \ldots, 2^{n-1} \rbrace$, and then the only $B \subset A$ such that $A \cap 2B = \emptyset$ are $\emptyset$ and $\lbrace 2^{n-1} \rbrace$. Is there some additional hypothesis on $A$? –  Noam D. Elkies Sep 11 '12 at 5:00
    
@Noam: I misread the exercise. By 2B, I meant to say "the sum of two distinct elements of B". –  user26147 Sep 11 '12 at 6:46
    
I added a missing Omega. I am not sure if OP just wanted to be very polite or if there might now be some confusion regarding notation, thus and since I got briefly puzzled when looking this up: what is written in the book (or at least some version thereof) is the original version OP posted (including sums of equal elements), however this a known misprint. The current version (with the added Omega) is the one one gets when applying the correction indicated in the errata. –  quid Sep 11 '12 at 15:44
    
The dumb thing I would try first is to add the largest log n elements, and analyze why that might not work and what to do when it doesn't. Gerhard "Dumb Ideas Are Often Quick" Paseman, 2012.09.11 –  Gerhard Paseman Sep 11 '12 at 16:05
1  
My dumb thing to try first would be to build the set $B$ recursively. Something about the desired bound $log n$ makes me think that every time we add an element to $B$, something doubles, and life is okay as long as we stay less than $n$. –  Greg Martin Sep 11 '12 at 21:04
show 3 more comments

2 Answers

It seems that this was established by D.A. Klarner, although the proof has not been published till a year 1971 paper by Choi (who credited Klarner for it). The argument is rather straightforward and does not use the probabilistic method; it goes as follows.

For each $b\in A$, let $S(b):=\{a\in A\setminus\{b\}\colon b+a\in A\}$; we thus want to find a large subset $B\subset A$ so that for any $b\in B$, we have $S(b)\cap B=\varnothing$. We choose elements for $B$ one by one, starting with $b_1:=\max A$ and, once $b_1,\ldots,b_{m-1}$ got selected, choosing $b_m$ to be the element of $A\setminus(S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\})$ with $S(b_m)$ of the smallest possible size.

For brevity, write $S:=S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\}$. Observing that if $a$ is one of the $k+1$ largest elements of $A$, then $|S(a)|\le k$, we conclude that $b_m\in A\setminus S$ can be chosen so that $|S(b_m)|\le |S|$; hence, $$ |S(b_m)| \le |S(b_1)|+\dotsb+|S(b_{m-1})| + m-1. $$ A simple induction now confirms that $|S(b_m)|<2^{m-1}$ and therefore, there is a way to choose $b_m$ as long as $2^{m-1}\le|A|$ holds. As a result, we end up with a set $B=\{b_1,\ldots,b_m\}$ such that $m>\log_2|A|$.

share|improve this answer
add comment

[Edited to give more information in reply to Terry Tao's comment and Seva's query]

I told Zach Abel of this problem, and the next day he e-mailed me that Zach and Andrey Grinsphun (both are graduate students at MIT) obtained the following solution:

incrementally take the largest element that doesn't violate the condition. Each insertion at most doubles the number of elements of $A$ that are ruled out, so it gets $\Omega(\log n)$ elements.

In later correspodence Andrey explains that the "ruled out" elements include those of $B$ itself, and it's actually not "doubles" but "doubles and adds 1 to", so after choosing $m$ elements there are at most $2^m-1$ forbidden. In more detail (translating some English into equivalent formulas):

List $A$ in increasing order $A=\lbrace a_1,...,a_n \rbrace$. Start with $B$ empty and note that this forbids at most $2^m-1=0$ elements ($m=|B|$, the size of $B$).

Then if we currently have some $B$ of size $m$, when we choose the largest element that is not forbidden, since $B$ forbids at most $2^m-1$ elements by induction we may add $a_k$ to $B$ for some $k \geq n-2^m+1$. Then the number of new forbidden elements is at most $1+|(A-a_k) \cap A|$ (the $1$ comes from $a_k$ itself). But $|(A-a_k) \cap A| \leq |\lbrace x\in A : x > a_k \rbrace|$, which is at most the number of elements $B$ forbids. In particular, it's at most $2^m-1$, so the number of new forbidden elements is at most $2^m-1+1=2^m$, and so the total number of forbidden elements is at most $2^m+2^m-1 = 2^{m+1}-1$.

[CW because this is not my own argument. I still wonder if $\log n$ is anywhere near the right order; it feels surprisingly small. It's not even obvious to me that there are sets $A$ for which the smallest $B$ has size $o(n)$, let alone $n^{o(1)}$. (See Terry Tao's reply: Ruzsa indeed obtained an $n^{o(1)}$ bound!)]

share|improve this answer
2  
One can improve on the logarithmic factor by a tiny amount (about $\log\log\log\log\log n$), but it requires a surprisingly massive amount of effort: see the paper of Sudakov, Szemeredi, and Vu, projecteuclid.org/… . Presumably this is not best possible. –  Terry Tao Sep 15 '12 at 20:23
    
Thanks for this reference. Do you know of a construction of $A$ that shows that the bound must be $o(n)$? –  Noam D. Elkies Sep 15 '12 at 21:46
    
the best upper bound is $O(\exp(\sqrt{\log n}))$, due to Ruzsa: springerlink.com/content/m02g0814g70131t8 –  Terry Tao Sep 15 '12 at 23:09
1  
A masters student from Lyon, Jehanne Dousse, recently improved [SSV] to log n logloglog n or thereabouts, by replacing the use of Szemeredi's theorem by a density increment argument generalising that of Roth, allowing one to locate inside a dense set A some elements x_1,...,x_k, all of whose midpoints also lie in A. The key is that these configurations can still be detected by Gowers' U2-norm. I have no clue what the correct bound is.... –  Ben Green Sep 16 '12 at 1:11
    
Let $A=[2n,3n]\cup\{4n\}\cup[5n,6n]$. Taking subsequently $6n,6n-1,\ldots,5n$ neither violates the condition nor rules out any element. Then you take $4n$, and the number of elements which are ruled out jumps from $0$ to $n$. What am I missing? –  Seva Sep 19 '12 at 6:00
show 1 more 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.