Random Sidon sequences. (English) Zbl 0924.11006

Godbole, Anant P.; Janson, Svante; Locantore, Nicholas W. jun.; Rapoport, Rebecca

J. Number Theory 75, No. 1, 7-22 (1999).

Consider a subset \(A\) chosen randomly from the \( n \choose k_n\) subsets of size \(k_n\) of \([1, 2,\dots, n]\). The paper investigates the probability that such a set has the \(B_h\) property, that is, whether the sums of \(h\) elements of \(A\) are all distinct. It is proved that if \(k_n/n^{1/2h} \rightarrow \Lambda \) as \(n \rightarrow \infty \), then this probability tends to \( \exp \bigl( -\kappa _h \Lambda ^{2k} \bigr) \) with certain positive constants \(\kappa _h\). In particular, if \(k_n/n^{1/2h} \rightarrow 0\), then almost all sets have the \(B_h\) property, and if \(k_n/n^{1/2h} \rightarrow \infty \), then almost all do not have it. The proofs are based on Janson’s inequality and the Stein-Chen approximation for positively related random variables.

Reviewer: I.Z.Ruzsa (Budapest)

MSC:

11B13	Additive bases, including sumsets
11B75	Other combinatorial number theory

Keywords:

Sidon sets

References:

[1]	Alon, N.; Spencer, J., The Probabilistic Method (1992), Wiley: Wiley New York
[2]	Barbour, A. D.; Holst, L.; Janson, S., Poisson Approximation (1992), Oxford University Press: Oxford University Press Oxford
[3]	Erdős, P.; Freud, S., On sums of a Sidon sequence, J. Number Theory, 38, 196-205 (1991)
[4]	Graham, S. W., \(B_h\)sequences, (Berndt, B. C.; Diamond, H. G.; Hildebrand, A. J., Analytic Number Theory. Analytic Number Theory, Proceedings of a Conference in Honor of Heini Halberstam (1996), Birkhäuser: Birkhäuser Basel), 431-449 · Zbl 0859.11009
[5]	Halberstam, H.; Roth, K., Sequences (1983), Springer-Verlag: Springer-Verlag New York
[6]	Lindström, B., An inequality for \(B_2\), J. Comb. Theory, 6, 211-212 (1969) · Zbl 0172.01403
[7]	Nathanson, M. B., Additive Number Theory: Inverse Problems and the Geometry of Sumsets (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0859.11003
[8]	Spencer, J.; Tetali, P., Sidon sets with small gaps, (Aldous, D.; Diaconis, P.; Spencer, J.; Steele, J. M., Discrete Probability and Algorithms. Discrete Probability and Algorithms, IMA Vol. Math. Appl., 72 (1995), Springer-Verlag: Springer-Verlag New York) · Zbl 0833.60011