Determine if there exists a strictly increasing sequence of positive integers a1, a2, ... such that an≤n3 for every positive integer n and that every positive integer can be written uniquely as the difference of two terms in the sequence.
Problem
Source: MOP 2006 Homework - Black Group
Tags: algebra unsolved, algebra, combinatorics
14.03.2019 20:58
Yes, such sequence does exist. Sketch: Some modification of the Sidon sequence, constructed by a greedy algorithm. First, we can construct (by greedy algorithm) an increasing sequence (ai),i=1,2,… such that ai+aj are all distinct (here j,j may be equal). It means we start with a1=1,a2=2 and if a1,a2,…,an are already defined, we define an+1 as the smallest number not belonging to the set {aℓ+am−ak:1≤k≤ℓ≤m≤n}. By definition, all sums/differences of two terms of that sequence are distinct. The set {aℓ+am−ak:1≤k≤ℓ≤m≤n} has at most (n3)+2n2 elements, hence it follows an+1≤(n3)+2n2+1<(n+1)34, when n is large enough and an+1<(n+1)3 for all n∈N. Thus, aj−ai,i<j are distinct, but may not contain all positive integers. So, we make the following modification. We construct a1<a2<⋯<an as above, for some large enough n∈N. If {aj−ai:1≤i<j≤n} hit any integer less than n, we proceed with the above algorithm. If not, let r,r<n be the first integer not represented as such a difference. We define an+1:=2an and an+2:=an+1+r. The new set A={a1,a2,…,an+2} also has the property the differences are distinct, but we have already covered r, since an+2−an+1=r. And of course am+2<m3<(m+2)3. Further, we proceed again with the greedy algorithm, this time the new terms added may be smaller than an+2 , but there will be a moment when the sequence jumps out of the interval 1..an+2. Let m,m>n+2 be the first integer with am>an+2. By the above argument, it holds am<m34, so we proceed in the same way covering the next integer not yet covered by differences aj−ai,i<j≤m.