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$.

  • $\begingroup$ 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\}$$ $\endgroup$ – Matt F. Aug 8 at 19:34
  • 2
    $\begingroup$ $$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. $\endgroup$ – Matt F. Aug 8 at 20:32

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.

  • $\begingroup$ 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. $\endgroup$ – Matt F. Aug 8 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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