Infinite Sidon sequences

We give an explicit construction of an infinite Sidon sequence A   of positive integers with counting function A(x)=x2−1+o(1). Ruzsa proved the existence of a Sidon sequence with similar counting function but his proof was not constructive.Our method generalizes to BhBh sequences when h⩾3h⩾3. In this case our constructions are not explicit but they provide the first improvements on the greedy algorithm for these sequences: for all h⩾3h⩾3, there is a BhBh sequence A   with counting function A(x)=x(h−1)2+1−(h−1)+o(1).