Random sidon sequences

A subset A of the set [n] = {1, 2,..., n}, \A\ = k, is said to form a Sidon (or B-h) sequence, h greater than or equal to 2, if each of the sums a(1) + a(2) +...+ a(h), a(1) less than or equal to a(2) less than or equal to .. .less than or equal to a(h), a(i) is an element of A, are distinct. We inve stigate threshold phenomena for the Sidon property, showing that if A(n) is a random subset of [n], then the probability that A(n) is a B-h sequence t ends to unity as n --> infinity if k(n) = \A(n)\ much less than n(1/2h), an d that P(A(n) is Sidon) --> 0 provided that k(n) much greater than n(1/2h). The main tool employed is the Janson exponential inequality. The validity of the Sidon property at the threshold is studied as well. We prove, using the Stein-Chen method of Poisson approximation, that P(A(n) is Sidon) --> e xp{ - lambda} (n --> infinity) if k(n) similar to Lambda . n(1/2h) (Lambda is an element of R+), where lambda is a constant that depends in a well-spe cified way on Lambda. Multivariate generalizations are presented. (C) 1999 Academic Press.