Probabilistic constructions of \(B_2[g]\) sequences
type: Item
instance of: scholarly article
title: Probabilistic constructions of \(B_2[g]\) sequences
zbMATH Open document ID: 1241.11025
author: Javier Cilleruelo
publication date: 2010-09-22T00:00:00Z
review text: 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…
reviewed by: Erick Wong
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 11B13
Mathematics Subject Classification ID: 05D40
zbMATH DE Number: 5790104
zbMATH Keywords: Sidon sequences
zbMATH Keywords: \(B_2[g]\) sequences
zbMATH Keywords: probabilistic method
MaRDI profile type: Publication
full work available at URL: s10114-010-8272-7
OpenAlex ID: W2097126379
cites work: On a Problem of Sidon in Additive Number Theory, and on some Related Problems
cites work: Q4335192
cites work: $B_{2}$-sequences whose terms are squares
cites work: \(B_ 2[g]\) sequences whose terms are squares
DOI: 10.1007/S10114-010-8272-7
published in: Acta Mathematica Sinica, English Series
description: scientific article; zbMATH DE number 5790104