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

Question

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

Answer 1

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

Answer 2

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