Return to Answer

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.

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.

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.

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.

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.

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

$V=S \cup \lbrace 63, 64, 70, 71, 78, 85, 86, 92, 93 \rbrace \cup (S+125)$ has $37$ members, the largest being $156$. and $V+V=\lbrace 0,1,2,\cdots,312\rbrace$ This is better than the examples above since $37=312^{0.62875}$. and it 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 am not sure if the set in the middle of $V$ is the smallest possible.

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.