# Least cardinality of a set of integers

If $S_n$ is a set of positive integers >0 of the least cardinality such that every positive integer less then $n$ can be written as the sum of at most two elements of $S_n$, how precisely can we bound the asymptotics of $|S_n|$ as $n\rightarrow\infty$ ?

And for $|S(n,k)|$, if every integer less then n can be written as the sum of at most k elements of $S(n,k)$?

And for $|G(n,k)|$, if every integer less then n can be written as the sum of exactly k elements of $G(n,k)$?

$S(n,2)$ = http://oeis.org/A082429

• I do not think you have to delete the post here as long as you mention that you posted it at MO. I've seen many examples of such questions, one of the is here. Anyway I would think that you should get it a little more time then just 1 hour before rushing to MO. (There have been only 17 views to this question so far.) – Martin Sleziak Nov 6 '11 at 8:23
• My feeling is that this is somewhat related to Erdős–Turán conjecture on additive bases, but I am far from being expert in this area, so this is probably the only useful information I am able to give. – Martin Sleziak Nov 6 '11 at 8:28
• @Martin: I waited almost three weeks before cross-posting, at time of cross-posting my question had about 80 views overall. Waiting less than one day is ridiculous (unless discussed first in the comments/meta thread). – Asaf Karagila Nov 6 '11 at 11:19
• @Martin, I think your link to Erdos-Turan is very much what OP needs. +1 from me. – Gerry Myerson Nov 6 '11 at 11:58
• First easy observation: If $S_n$ has $k$ elements, then $n\le \frac{k(k+1)}2$ (the number of possibilities how to choose at most two summands.) Thus clearly $(k+1)^2\ge 2n$ and $|S_n|\ge \sqrt{2n}-1$. \\ Another easy observation: The set $\{1,2,\dots,\lfloor \sqrt n\rfloor\} \cup \{k\cdot\lfloor \sqrt n\rfloor; 1\le k \le \lceil \sqrt n \rceil \}$ clearly generates $\{1,2,\ldots,n\}$, so we have $|S_n|\le 2\sqrt n$. \\ I hope I did not make a mistake there. – Martin Sleziak Nov 6 '11 at 12:03

Erdős proved that there exists an additive basis $B$ of order 2 and constants $c_1, c_2 > 0$ such that $c_1 \log n \leq r_B(n) \leq c_2 \log n$ for all $n$ sufficiently large. In particular, this implies that there exists an additive basis $B$ such that $r_B(n) = n^{1/2 + o(1)}$, which is essentially best possible.