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$
$\endgroup$
2
-
$\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$– user44143Commented Aug 8, 2019 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$– user44143Commented Aug 8, 2019 at 20:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Aug 8, 2019 at 20:56
-
$\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$– user44143Commented Aug 8, 2019 at 21:39
$\begingroup$
$\endgroup$
1
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.
-
6$\begingroup$ or simply take $A=\{0,1,\ldots,m-1\}\cup \{m,2m,3m,\ldots,m^2\}$ for $m=\lfloor k/2 \rfloor$ $\endgroup$ Commented Aug 8, 2019 at 20:59