# Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements.

Disclaimer: When I say fastest growing set, I mean set with the fastest growing get-the-nth-member function. I don't know the technical term for this property and my math vocabulary is limited.

The Goldbach conjecture states that every even number can be expressed as the sum of two primes. Let's only concern ourselves with odd primes and even numbers >= 6. The growth rate of the nth prime number function ~ n*log(n). Anyway, I can't think of a set that grows more quickly than the odd prime numbers that still satisfies this property, or even another set that grows as quickly that isn't some trivial modification of the set of odd primes.

-

Let the set consist of all numbers whose binary expansion has the form $1+\sum_{i\geq 1} a_i 2^{2i}$ or $1+\sum_{i\geq 1}b_i 2^{2i-1}$. Then $x_k\approx k^2$, which is the largest exponent possible.

-
I'm very curious (yet a bit lazy in this very moment) to know how close is this amazing solution to the largest constant possible in front of $k^2$, which can't be larger than 1/2 if I'm correct. – Pietro Majer Sep 5 '11 at 21:39

Note that the assumption on the parity of numbers and relaxing "every even integer" to "every large enough even integer" do not affect the growth rate of the sequence.

Given a set $B=\lbrace a_1,a_2,\dots\rbrace$ of natural numbers, we say it is an additive basis of order $k$ if every sufficiently large integer can be expressed as the sum of $k$ elements from $B$. We can denote by $r_{B}(n)$ to be the number of solutions of $n=x_1+\cdots+x_k$ where $x_i\in B$. A trivial bound is $$|B\cap [1,n]|^k\geq \sum_{m=1}^n r_B(m)$$

Showing that in the case of an additive basis of order 2, like in your problem the best we can hope for a thin basis is that $|B\cap [1,n]|=n^{1/2+o(1)}$. In "Problems and results in additive number theory", Colloque sur la Théorie des Nombres, Bruxelles, 1955 , pp. 127--137 (which you can find here) Erdős proves that there exists an additive basis of order two which satisfies $r_B(n)\sim \log n$ which is thin in the sense described above.

-

For an explicit example that grows faster than primes, look at the set of numbers whose base $3$ expansion contains only $0$'s and $1$'s. (Sloane A005836) For any integer $n$, write $n$ in base $3$ as $(n_r \ldots n_1 n_0)_3$. Then $n=(a_r \ldots a_1 a_0)_3+(b_r \ldots b_1 b_0)_3$ where $(a_k, b_k) = (0,0)$ if $n_k=0$, $(a_k, b_k) = (0,1)$ if $n_k=1$ and $(a_k, b_k) = (1,1)$ if $n_k=2$.

Let $x_k$ be the $k$-th number in this sequence. If $2^m \leq k < 2^{m+1}$, then $3^m \leq x_k < 3^{m+1}$. So $x_k \approx k^{\log 3/\log 2}$. This is faster then the primes, which grow like $k \log k$.

-
But the question asked for a set of odd numbers. – Gerry Myerson Sep 6 '11 at 1:50
@Gerry Myerson: That's not hard to fix. Double all members of the sequence and add one; now they add up to the positive even numbers. – Charles Sep 6 '11 at 5:35

I think I found the slowest growing set, with the greedy algorithm. 1, then we need 3 to represent 4 and we get 6 for free, then the largest number that will get us the missing 8 is 7. To get 12, the largest number that will work is 11. So our set is simply 1 and all $4k+3,$ as we can never represent any multiple of 4 without using the 1 and a new $4 k +3.$

Onward and downward.

-
well, the slowest growing set is the set of $all$ odd numbers.... – Greg Martin Sep 5 '11 at 20:36
Right, this is a slowest growing where each new odd number is the largest that does get you a representation of the first missing even number, what Manjul Bhargava called the "truant." It seems, if you take instead the smallest that gives you the truant, you do get all odd numbers (you have all odd numbers up to $2k-1,$ the truant is $4k,$ the smallest new odd number that works is indeed $2k+1,$ as $2k-1 + 2k +1=4k$). So all that is at stake is the definition of "greedy" algorithm, which I interpret, in this setting, as taking the largest odd number that gets the truant. – Will Jagy Sep 5 '11 at 20:51