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.