Minimal basis of set of positive integers

Question

Let $A$ be a set of positive integers and $A+A = \{a_1 + a_2 | a_1,a_2 \in A \}$. If $A+A$ contains all positive integers, $A$ is called a basis (of order 2) of the set of positive integers. A basis $A$ is called a minimal basis, if no proper subset of $A$ is a basis.

E.g. the set of all numbers with only "0"s and "1"s in ternary representation is a (even minimal) basis. This is somehow the discrete analogon to the well known fact that the sumset of two Cantor ternary sets is the closed interval [0,2].

I'm looking for a 'smallest' minimal basis of the set of positive integers ('smallest' in the sense of the lexikographic order - also other orders would be interesting, e.g. the order induced by sum of inverse squares of the elements of the basis).

There are a lot of articles about minimal asymptotic basis of the set of positive integers ("asymptotic" meaning that only every \textit{sufficiently large} natural number is the sum of two elements of the basis). But I'm struggling to get or find my question above answered.

ADDENDUM: Sorry for not having been clear, and thank you for your comments. I hope the following remarks will clarify things a bit: a) Yes, I consider only order 2. b) To make my intention clearer, lets consider the finite set $M_n = \{0, 1, 2, 3, \ldots, n-1\}$ and ask for a basis $A$ such that $M_n \subset A + A$. E.g. $A = \{0,1,3,4,9,10,12,13\}$ is a basis of $M_{27}$ (this is just the ternary construction mentionned above). In the finite case I'm looking for the basis with the smallest number of elements and in case of a tie (same number of elements), I prefer the basis which comes later in lexicographic order (i.e. I would prefer $\{0,1,3,4,10\}$ to $\{0,1,3,4,9\}$. My intention with the question was to ask this problem not for finite $M_n$, but for $M_{\infty} = \mathbb{N}$ (sorry also for the confusion whether to include "0" or not). Since the cardinality of the "ternary basis" scales with $n^{2/3}$ and the cardinality ofthe proposed basis of odd numbers is $n/2$, I regard the "ternary basis" as a better one. Perhaps the problem is still not well defined and/or there is no such "best" basis. This would also be helpful for me to know.

Answer 1

The exponent can be arbitrarily close to $\frac{1}{2}$: If $n=r^2$ then $A+B=\lbrace 0,1,2,\cdots n-1 \rbrace$ where $A=\lbrace 0,1,2,\cdots r-1\rbrace$ and $B=\lbrace 0,r,2r,\cdots,(r-1)r\rbrace$. This means that $S=A \cup B$ is a set of size $2r=2\sqrt{n} $ with $S+S \supset \lbrace 0,1,2,\cdots n-1 \rbrace$. So by iteration (as described in the old answer) we can have exponent $\frac{1}{2}+\log_n(2)$.

Modifying this a bit gives a construction I probably have seen before: Let $A=\lbrace 0,1,4,5,16,17,20,21\cdots\rbrace$ be the (infinite) set of non-negative integers whose binary expansion is $0$ in all the odd positions and $B=2A$ the set of those with $0$ in all the even positions. Here both have exponent $\frac{1}{2}$ and $A+B=\mathbb{N}_0$. Then $S=A \cup B$ has about $2\sqrt{N}$ members less than $N$ and $S+S=\mathbb{N}_0.$

---

Old Answer Here is a nice ad hoc start: The set $S=\lbrace 0, 1, 3, 5, 6, 13, 15, 16, 18, 25, 26, 28, 30, 31 \rbrace$ has $S+S=\lbrace 0,1,2,\cdots,62 \rbrace$ (It is the start of a sequence in the OEIS with next term 63, but I'm not sure if that helps). Then $T=S+63S$ has 196 members the largest being $1984$ and $T+T=\lbrace 0,1,2,\cdots,3968 \rbrace$. Now $14=31^{0.63944}$ and $196=3968^{0.63699}$ and further iterating will continue to give examples sparser than $k^{2/3}$. The same trick can be done with any finite example. The densities decrease but only very very slightly. LATER the set $S'=\lbrace 0, 1, 3, 5, 6, 13, 14,17, 18, 25, 26, 28, 30, 31 \rbrace$ also has $S'+S'=\lbrace 0,1,2,\cdots,62 \rbrace.$

Observe that the places where $S$ has a jump from $j$ to $2j+1$ are at $0,1,6,31$ (numbers of the form $\frac{5^j-1}{4}$) and that there is a central symmetry for $0,1$ and for $0,1,3,5,6$ and for $S$. This suggests a treasure hunt for an symmetric extension with largest member $1+5+25+125=156$.

UPDATE For any one of the four choices $(a,b)=(68,69),(68,72),(69,70),(70,71)$ the set $V=S \cup \lbrace 63, 64, a,b,156-b,156-a, 92, 93 \rbrace \cup (S+125)$ has $36$ members, the largest being $156$. and $V+V=\lbrace 0,1,2,\cdots,312\rbrace$ There is only one way to similarly extend $S'$ to a set of size $36$ with the same properties, it has lower half $S' \cup \lbrace 63, 65, 67, 69 \rbrace$. These are better than the examples above since $36=312^{0.62398}$. Also, these can be iterated as above.

Maybe an even lower density is possible for $W=V \cup \lbrace ?? \rbrace \cup(V+625)$ where the set in the middle is made of several pairs $q,781-q$. I'd guess 8 pairs leading to $88=1562^{0.60885}$ but that is pure speculation. Of course there might be better examples which are not symmetric (or even ones which are). There turns out to be no advantage at this stage to putting the exact middle of $78$ in $V$ (for any of the 5 choices). I don't think it would help get a better $W$ but I am not sure.

Answer 2

Consider a set that starts with 0, 1, 2, ..., n, 2n+1, 3n+2, .... For each k from 0 to n, the only way to get 2n+1+k is by summing 2n+1 with k, so we can't remove any of the terms 0, 1, ..., n. Then this set contains a minimal basis that begins with 0, 1, ..., n, and there are arbitrarily "small" minimal bases.