## Archive for June, 2012

### Sumsets not containing a power of two

June 26, 2012

Let $A = \{a_1, a_2, .. \}$ be an infinite set of positive integers under the following constraints:

1) $a_1 = 1$.
2) For all $k$ we have: $a_k < a_{k+1} \le 2a_k + 1$.

Let $n$ be a non-negative integer and let $S \subseteq \{0, 1, .., n\}$ be a set of non-negative integers containing $0$. Define $S + S = \{x + y | x,y \in S\}$. That is, since $S$ contains $0$, the set $S + S$ is the set of all integers that can be written as a sum of at most two non-zero elements of $S$. We now have the following theorem:

Theorem. If $(S + S) \cap A = \emptyset$, then $|S| \le (n+j)/2$, where $j$ is either $1$ or $2$, according to whether the smallest element of $A$ larger than $n$ (which we shall call $a_{k+1}$) is even or odd.

In particular, if $|S| \ge n/2 + 1$, then some power of two can be written as sum of at most two elements of $S$. In Additive Number Theory: Inverse Problems and the Geometry of Sumsets (which is an awesome book, by the way!) this special case is proved and then used to prove the neat fact that if $S \subseteq \{1, 2, .., n\}$ and $|S| > n/3$, then some power of two can be written as sum of at most four elements of $S$. We will now prove the general version.

Proof. When $n \in A$, then, for $i = 0, 1, .., \lfloor (n-1)/2 \rfloor$,  at most one of $i, n-i$ lies in $S$ (why does $n/2$ not lie in $S$?), so we then immediately have $|S| \le (n+1)/2$. So we may assume that $n \notin A$. Furthermore, for $n = 0$, we obviously have $|S| \le (n+2)/2$. Now assume that, for all $n' < n$ we have that the largest set $S' \subseteq \{0, 1, .., n'\}$ for which no $a_i$ is the sum of at most two elements of $S'$, has cardinality at most $(n'+2)/2$. We will use this induction hypothesis to prove our Theorem.

Case I. $a_{k+1}$ is even.

First some definitions:

Let $S \subseteq \{0, 1, .., n\}$ be a set such that no element of $A$ can be written as a sum of at most two elements of $S$.
Let $k$ be such that $a_k < n < a_{k+1}$.
Let $m$ be such that $n + m = a_{k+1}$ (note that $m = a_{k+1} - n \le a_{k+1} - a_k - 1 \le (a_{k+1}-1)/2 \le a_k < n$).
Let $S_0 = S \cap \{0, 1, .., m-1\}$ (on which we will use the induction hypothesis, which is allowed, since $m-1 < n$).
Let $S_{i-m+1} = S \cap \{i, a_{k+1} - i\}$, for $i = m, m+1, .., a_{k+1}/2$.

Now note that, for all relevant $i \ge 1$, we get $|S_i| \le 1$, while for $i = a_{k+1}/2$ we even know $|S_{i-m+1}| = 0$ (again, why?). What’s left is a direct computation.

$|S| = |S_0| + \displaystyle \sum_{i=1}^{a_{k+1}/2 - m} |S_{i}| \\ \le (m+1)/2 + a_{k+1}/2 - m \\ = a_{k+1}/2 - (m-1)/2 \\ = (n+1)/2$

Case II. $a_{k+1}$ is odd.

We carry over all definitions of Case I, with the exception of the fact that the sets $S_{i-m+1}$ are now defined for $i = m, m+1, .., (a_{k+1} - 1)/2$, and we may no longer deduce the existence of an index $i$ for which $|S_i| = 0$. The obvious computation now yields:

$|S| = |S_0| + \displaystyle \sum_{i=1}^{(a_{k+1} + 1)/2 - m} |S_i| \\ \le (m+1)/2 + (a_{k+1} + 1)/2 - m \\ = (a_{k+1} + 1)/2 - (m-1)/2 \\ = (n+2)/2$

And we’re done.