Random Sidon Sequences
1999; Elsevier BV; Volume: 75; Issue: 1 Linguagem: Inglês
10.1006/jnth.1998.2325
ISSN1096-1658
AutoresAnant P. Godbole, Svante Janson, Nicholas Locantore, Rebecca Rapoport,
Tópico(s)Mathematical Approximation and Integration
ResumoA 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.
Referência(s)