Random Sidon Sequences

AbstractA subsetAof the set [n]={1,2,…,n}, |A|=k, is said to form aSidon(orBh) sequence,h⩾2, if each of the sumsa1+a2+…+ah,a1⩽a2⩽…⩽ah;ai∈A, are distinct. We investigate threshold phenomena for the Sidon property, showing that ifAnis a random subset of [n], then the probability thatAnis aBhsequence tends to unity asn→∞ ifkn=|An|⪡n1/2h, and thatP(Anis Sidon)→0 provided thatkn⪢n1/2h. The main tool employed is the Janson exponential inequality. The validity of the Sidon propertyatthe threshold is studied as well. We prove, using the Stein–Chen method of Poisson approximation, thatP(Anis Sidon) →exp{−λ} (n→∞) ifkn∼Lambda;·n1/2h(Λ∈R+), whereλis a constant that depends in a well-specified way onΛ. Multivariate generalizations are presented