Bases for sets of integers (Q1238842)

If every member of a set \(A\) of positive integers can be expressed in the form \(b+b'\) for some \(b\), \(b'\in B\), then the set \(B\) of non-negative integers is called a basis for \(A\). The problem is to find bounds on the size \(m\) of the smallest basis \(B\) for a set \(A\) of type \((n,N)\), i.e. for a set \(A\) with \(n\) elements, the largest of which is \(N\). It is easy to show that \(n^{\frac{1}{2}}\leq m\leq\min\{n+1\text{,}(4N+1)^{\frac{1}{2}}\}\). The authors show that, for most sets \(A\) of type \((n,N)\), \[ m> \min\left\{\frac n{\log N},\frac{\sqrt N}2\right\}, \] so that, for most sets \(A\), the actual value of \(m\) is closer to the upper bound than to the lower bound. A special study is then made of the sequence of squares, \(A=\{1^2,2^2,\dots,n^2\}\), and it is shown that this sequence is untypical since, for arbitrarily large \(M\), \(n^{2/3-\varepsilon}\leq m\leq n/\log ^mn\). (There is an unfortunate misprint at this point.) Closing remarks include the observation that the value of \(m\) depends critically not just on \(n\) and \(N\), but on the arithmetical character of the sequence.