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

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

2011-09-05T16:21:08Z

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.

Answer by Gjergji Zaimi for Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements.

2011-09-05T16:55:46Z

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.

Answer by David Speyer for Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements.

2011-09-05T17:08:27Z

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

Answer by Richard Stanley for Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements.

2011-09-05T17:20:25Z

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.

Answer by Will Jagy for Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements.

2011-09-05T20:29:55Z

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.