Let be an infinite set of positive integers under the following constraints:
2) For all we have: .
Let be a non-negative integer and let be a set of non-negative integers containing . Define . That is, since contains , the set is the set of all integers that can be written as a sum of at most two non-zero elements of . We now have the following theorem:
Theorem. If , then , where is either or , according to whether the smallest element of larger than (which we shall call ) is even or odd.
In particular, if , then some power of two can be written as sum of at most two elements of . 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 and , then some power of two can be written as sum of at most four elements of . We will now prove the general version.
Proof. When , then, for , at most one of lies in (why does not lie in ?), so we then immediately have . So we may assume that . Furthermore, for , we obviously have . Now assume that, for all we have that the largest set for which no is the sum of at most two elements of , has cardinality at most . We will use this induction hypothesis to prove our Theorem.
Case I. is even.
First some definitions:
Let be a set such that no element of can be written as a sum of at most two elements of .
Let be such that .
Let be such that (note that ).
Let (on which we will use the induction hypothesis, which is allowed, since ).
Let , for .
Now note that, for all relevant , we get , while for we even know (again, why?). What’s left is a direct computation.
Case II. is odd.
We carry over all definitions of Case I, with the exception of the fact that the sets are now defined for , and we may no longer deduce the existence of an index for which . The obvious computation now yields:
And we’re done.