Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$ =

share|cite|improve this question
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
up vote 4 down vote accepted

Gerry Myerson's comment made me have a closer look at wikipedia's article and I believe that it answers (at least to some extent) the first part your question. It might also suggest some keywords, which might help you find what is known so far about the second part.

The following is a quote from wikipedia article on Erdős–Turán conjecture on additive bases:

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.

The reference given at wikipedia is Erdős, P. (1956). "Problems and results in additive number theory". Colloque sur le Theorie des Nombres: 127–137. (Perhaps some other papers of Erdős - available at - might be useful for you.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.