# Sets A such that A+A contains the largest set [0,1,..,t]

I look for a reference for the following problem. Given an integer $$k$$, find a set $$A\subset\mathbb{N}$$ with $$|A|=k$$ that maximizes $$t$$ such that $$\left[0,1,..,t\right]\subset A+A$$.

• For low numbers:$$k=1, t=0: \{0\}$$ $$k=2, t=2: \{0,1\}$$ $$k=3, t=4: \{0,1,2\} \text{ or } \{0,1,3\}$$ $$k=4, t=8: \{0,1,3,4\}$$ – Matt F. Aug 8 '19 at 19:34
• $$k=5, t=12: \{0,1,3,5,6\}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question. – Matt F. Aug 8 '19 at 20:32

## 2 Answers

A table of values for these $$t$$ are given in the introduction Graham and Sloane's On Additive Bases and Harmonius Graphs (your sequence corresponds to $$n_\beta(k)$$ in their notation). Graham and Sloane also give some references to previous work with this sequence, both under the name of "interval basis" (or Abschnittsbasis), going back to a paper in German from Rohrbach in the 1930's, and under the name of "The Postage Stamp Problem".

This is sequence A001212 in the OEIS, which has additional references.

• Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead. – Matt F. Aug 8 '19 at 21:39

This is related to thin additive bases" of order $$2$$. Clearly $$t$$ cannot be larger than $$k(k+1)/2$$. It is also possible to give examples where $$t$$ grows quadratically. Take $$A=A_0 \cup A_1$$ where $$A_0$$ contains all integers below $$t$$ with binary expansion $$\sum_{j} \epsilon_j 2^j$$ with $$\epsilon_j= 0$$ unless $$j$$ is even, and $$A_1$$ consists of numbers with binary digits $$\epsilon_j=0$$ unless $$j$$ is odd. Then $$A$$ has $$O(\sqrt{t})$$ elements in it; or alternatively $$t\ge Ck^2$$ for some constant $$C>0$$. See for example this paper of Blomer which has other references.

• or simply take $A=\{0,1,\ldots,m-1\}\cup \{m,2m,3m,\ldots,m^2\}$ for $m=\lfloor k/2 \rfloor$ – Fedor Petrov Aug 8 '19 at 20:59