Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T01:24:41Z http://mathoverflow.net/feeds/question/74594 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74594/fastest-growing-set-of-odd-numbers-such-that-any-even-number-can-be-expressed-as Fastest growing set of odd numbers such that any even number can be expressed as the sum of two elements. Gregory Nisbet 2011-09-05T16:21:08Z 2011-09-05T20:29:55Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/74594/fastest-growing-set-of-odd-numbers-such-that-any-even-number-can-be-expressed-as/74597#74597 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. Gjergji Zaimi 2011-09-05T16:55:46Z 2011-09-05T16:55:46Z <p>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. </p> <p>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)$$</p> <p>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 <a href="http://www.renyi.hu/~p_erdos/Erdos.html" rel="nofollow">here</a>) 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.</p> http://mathoverflow.net/questions/74594/fastest-growing-set-of-odd-numbers-such-that-any-even-number-can-be-expressed-as/74598#74598 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. David Speyer 2011-09-05T17:08:27Z 2011-09-05T17:08:27Z <p>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. <a href="http://oeis.org/A005836" rel="nofollow">(Sloane A005836)</a> 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$. </p> <p>Let $x_k$ be the $k$-th number in this sequence. If $2^m \leq k &lt; 2^{m+1}$, then $3^m \leq x_k &lt; 3^{m+1}$. So <code>$x_k \approx k^{\log 3/\log 2}$</code>. This is faster then the primes, which grow like $k \log k$.</p> http://mathoverflow.net/questions/74594/fastest-growing-set-of-odd-numbers-such-that-any-even-number-can-be-expressed-as/74599#74599 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. Richard Stanley 2011-09-05T17:20:25Z 2011-09-05T17:20:25Z <p>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.</p> http://mathoverflow.net/questions/74594/fastest-growing-set-of-odd-numbers-such-that-any-even-number-can-be-expressed-as/74616#74616 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. Will Jagy 2011-09-05T20:29:55Z 2011-09-05T20:29:55Z <p>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.$ </p> <p>Onward and downward.</p>