Random Sidon Sequences Original Research Article

A subsetAof the set [n]={1, 2, …, n}, A=k, is said to form aSidon(orBh) sequence,hgreater-or-equal, slanted2, if each of the sumsa1+a2+…+ah,a1less-than-or-equals, slanta2less-than-or-equals, slant…less-than-or-equals, slantah;aiset membership, variantA, 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=Anmuch less-thann1/2h, and thatP(Anis Sidon)→0 provided thatknmuch greater-thann1/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→∞) ifknnot, vert, similarLambda;·n1/2h(Λset membership, variantR+), whereλis a constant that depends in a well-specified way onΛ. Multivariate generalizations are presented.