Random Sidon sequences. (English) Zbl 0924.11006

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.


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


Sidon sets
Full Text: DOI Link


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.