Determine if there exists a strictly increasing sequence of positive integers $a_1$, $a_2$, ... such that $a_n \le n^3$ 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 $(a_i), i=1,2,\dots$ such that $a_i+a_j$ are all distinct (here $j,j$ may be equal). It means we start with $a_1=1,a_2=2$ and if $a_1,a_2,\dots,a_n$ are already defined, we define $a_{n+1}$ as the smallest number not belonging to the set $\{a_{\ell}+a_m-a_k : 1\leq k\leq \ell\leq m\leq n\}$. By definition, all sums/differences of two terms of that sequence are distinct. The set $\{a_{\ell}+a_m-a_k : 1\leq k\leq \ell\leq m\leq n\}$ has at most $\binom{n}{3}+2n^2$ elements, hence it follows $a_{n+1}\leq \binom{n}{3}+2n^2 +1<\frac{(n+1)^3}{4}$, when $n$ is large enough and $a_{n+1}<(n+1)^3$ for all $n\in\mathbb{N}$. Thus, $a_j-a_i, i<j$ are distinct, but may not contain all positive integers. So, we make the following modification. We construct $a_1<a_2<\dots<a_n$ as above, for some large enough $n\in \mathbb{N}$. If $\{a_j-a_i:1\leq i<j\leq 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 $a_{n+1}:=2a_n$ and $a_{n+2}:=a_{n+1}+r$. The new set $A=\{a_1,a_2,\dots,a_{n+2}\}$ also has the property the differences are distinct, but we have already covered $r$, since $a_{n+2}-a_{n+1}=r$. And of course $a_{m+2}<m^3<(m+2)^3$. Further, we proceed again with the greedy algorithm, this time the new terms added may be smaller than $a_{n+2}$ , but there will be a moment when the sequence jumps out of the interval $1..a_{n+2}$. Let $m, m>n+2$ be the first integer with $a_m>a_{n+2}$. By the above argument, it holds $a_m<\frac{m^3}{4}$, so we proceed in the same way covering the next integer not yet covered by differences $a_j-a_i, i<j\leq m$.