The Number of Sidon Sets and the Maximum Size of Sidon Sets Contained in a Sparse Random Set of Integers

Abstract

A set A of non-negative integers is called a Sidon set if all the sums a1+a(2), with a(1)<= a(2) and a(1), a(2), are distinct. A well-known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of [n]={0,1,...,n-1}. Results of Chowla, Erdos, Singer and Turan from the 1940s give that F(n)=(1+o(1))root n. We study Sidon subsets of sparse random sets of integers, replacing the dense environment' [n] by a sparse, random subset R of [n], and ask how large a subset S< subset of>R can be, if we require that S should be a Sidon set. Let R=[n]m be a random subset of [n] of cardinality m=m(n), with all the subsets of [n] equiprobable. We investigate the random variable F([n]m)=max|S|, where the maximum is taken over all Sidon subsets S< subset of>[n]m, and obtain quite precise information on F([n]m) for the whole range of m, as illustrated by the following abridged version of our results. Let 0a1 be a fixed constant and suppose m=m(n)=(1+o(1))na. We show that there is a constant b=b(a) such that, almost surely, we have F([n]m)=nb+o(1). As it turns out, the function b=b(a) is a continuous, piecewise linear function of a that is non-differentiable at two critical' points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function b=b(a) is constant. Our approach is based on estimating the number of Sidon sets of a given cardinality contained in [n]. Our estimates also directly address a problem raised by Cameron and Erds (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61-79).