4
$\begingroup$

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

  • 2
    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.2011-11-06

1 Answers 1

4

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 http://www.renyi.hu/~p_erdos/Erdos.html - might be useful for you.)