Random Sidon sequences (Q1283038): Difference between revisions

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.