Probabilistic constructions of \(B_2[g]\) sequences (Q1956501)

A sequence of positive integers \(\{a_k\}\) is called a Sidon sequence if all pairwise sums \(a_l + a_k\) (with \(l \leq k\)) are distinct. More generally, we call this a \(B_2[g]\) sequence if the same pairwise sums have multiplicity bounded by \(g\) (then the Sidon property is synonymous with \(B_2[1]\)). Such sequences have been studied extensively in many combinatorial settings: see [\textit{K.\ O'Bryant}, Electron.\ J.\ Comb.\ DS11, 39 p. (2004; Zbl 1142.11312)] for a survey. An obvious counting argument shows that if \(\{a_k\}\) is \(B_2[g]\) for some fixed \(g\), then \(a_k \gg k^2\). When \(g=1\), it is a well-known result of Erdős that a Sidon sequence cannot satisfy \(a_k \ll k^2\), and moreover one cannot have \(a_k = o(k^2 \log k)\). Erdős also conjectured that \(2\) is the critical exponent, meaning that for any \(\varepsilon > 0\) there is a Sidon sequence satisfying \(a_k \ll k^{2+\varepsilon}\). \textit{P. Erdős} and \textit{A. Rényi} [Acta Arith.\ 6, 83--110 (1960; Zbl 0091.04401)] used the probabilistic method to show that random sequences chosen to have growth rate \(a_k \ll k^{2 + 2/g + o(1)}\) are almost surely \(B_2[g]\) after the removal of finitely many terms. Thus, one may approach the exponent \(2\) of Erdős's conjecture if one allows the pairwise sums of the sequence to have some large, but bounded, multiplicity. (It is tempting to believe that this multiplicity could be lowered if we throw out 99\% of the terms while keeping a positive proportion; this provides some intuition for the original conjecture.) The present paper refines this probabilistic construction, significantly sharpening the exponent to \(2 + 1/g\), or more precisely \[ a_k \leq k^{2 + 1/g} (\log k)^{1/g + o(1)}. \] The key advancement comes from requiring the (expected) multiplicities to be bounded in a certain \(L^{g+1}\) sense, rather than uniformly bounded. This allows the author to start with a random sequence of the given density and remove a small fraction of terms from each dyadic block to obtain a \(B_2[g]\) sequence. The techniques are elementary and the paper is pleasantly written. The above result yields the sharpest construction we are aware of for \(B_2[g]\) sequences with \(g \geq 3\) (for smaller \(g\), an ingenious construction of \textit{I. Z. Ruzsa} [J. Number Theory 68, No. 1, 63--71 (1998; Zbl 0927.11005)] gives a Sidon sequence with exponent \(1 + \sqrt{2}\)). Moreover, the paper's main Theorem~1.1 can also be used to construct \(B_2[g]\) sequences restricted to a given set of integers; the author applies this to the problem of \(B_2[g]\) sequences consisting only of perfect squares. Under this restriction we still have the exponent \(2 + 1/g\), which is the best known for any \(g \geq 1\). Compared to the unrestricted problem, there is some mild quantitative weakening: \(a_k \leq k^{2+1/g} (\log k)^{\kappa_g}\), where \(\kappa_g\) is a large constant, exponential in \(g\).