# There exists B subset A, |B| = log n, A \cap 2*B = \emptyset

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

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

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

-

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!)]

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