Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Please clarify better the "smallness". "Waring" bases $\{n^q:n\in\mathbb N\}$ are bases of $\mathbb N$ for any $q$, so that choosing $q$ as large as you wish you can "control" the lexigraphical order but not the density of the base. –  Wadim Zudilin May 30 '10 at 11:39
    
After reading your question again I realised that something is wrong with your definition of "minimal" basis. Any basis contains 1, hence if there is another element in it, is should be excluded as a finite sum of 1s... Probably, you define a minimal basis for a fixed order. But then only one such basis can be constructed! So, please make your question clear. –  Wadim Zudilin May 30 '10 at 11:47
2  
@Wadim: I think the OP means that any integer can be written as a sum of two elements from the basis. If that's the case then again the question seems trivial, as the smallest basis is 0,1,3,5,... (all odd numbers). –  Gjergji Zaimi May 30 '10 at 11:58
    
@Gjergji: That's exactly what I mean: if the order (say 2, as in your example) is fixed, then a basis is essentially unique! –  Wadim Zudilin May 30 '10 at 12:15
    
Just to be certain, what is the lexicographic order on these sequences? Is 0, 1, 2, 5, 7, 9, ... smaller or larger than the odd numbers with 0? –  Dror Speiser May 30 '10 at 18:01
show 5 more comments

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Beautiful! Now 0.62875 (or, rather, something slightly less than that) is an upper limit for the best exponent. Obviously 0.5 is a lower limit - is any stronger lower limit known? –  Yaakov Baruch Feb 22 '11 at 13:47
1  
$S$ is the set of integers whose expansion in base 4 either uses only the digits 0 and 1 or only the digits 0 and 2. –  Yaakov Baruch Feb 23 '11 at 7:29
    
The same idea works in any $n^2$ base. Eg., in base 9 take $S$ as the set of integers whose expansion either uses only 0,1,2 or uses only 0,3,6. Again $2\sqrt{N}$ efficiency is reached. –  Yaakov Baruch Feb 23 '11 at 10:08
add comment

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.

share|improve this answer
    
I believe the sets you propose are in fact minimal. –  Dror Speiser May 30 '10 at 18:42
    
Each of these bases is O(k) for $M_{k}$ , while the "ternary" example above is O($k^{2/3}$). Perhaps the intent of the question is how close can one get to $\sqrt{k}$? –  Yaakov Baruch May 30 '10 at 22:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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