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

### MSC:

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

Sidon sets
Full Text:

### References:

  Alon, N.; Spencer, J., The Probabilistic Method (1992), Wiley: Wiley New York  Barbour, A. D.; Holst, L.; Janson, S., Poisson Approximation (1992), Oxford University Press: Oxford University Press Oxford  Erdős, P.; Freud, S., On sums of a Sidon sequence, J. Number Theory, 38, 196-205 (1991)  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  Halberstam, H.; Roth, K., Sequences (1983), Springer-Verlag: Springer-Verlag New York  Lindström, B., An inequality for $$B_2$$, J. Comb. Theory, 6, 211-212 (1969) · Zbl 0172.01403  Nathanson, M. B., Additive Number Theory: Inverse Problems and the Geometry of Sumsets (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0859.11003  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.