Random Sidon Sequences

A 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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of number theory 1999-03, Vol.75 (1), p.7-22
Main Authors: Godbole, Anant P., Janson, Svante, Locantore, Nicholas W., Rapoport, Rebecca
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A 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.
ISSN:0022-314X
1096-1658
DOI:10.1006/jnth.1998.2325