Random Sidon Sequences

✍ Scribed by Anant P. Godbole; Svante Janson; Nicholas W. Locantore Jr.; Rebecca Rapoport

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 154 KB
• Volume: 75
• Category: Article
• ISSN: 0022-314X
• DOI: 10.1006/jnth.1998.2325

✦ Synopsis

A subset A of the set [n]=[1, 2, ..., n], |A| =k, is said to form a Sidon (or B h ) sequence, h 2, if each of the sums a 1 +a 2 + } } } +a h , a 1 a 2 } } } a h ; a i # A, are distinct. We investigate 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 tends to unity as n Ä if k n = |A n | < >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
, where \* is a constant that depends in a wellspecified way on 4. Multivariate generalizations are presented.
1999 Academic Press h ) sums a 1 +a 2 + } } } +a h ,