In number theory, a Sidon sequence is a sequence A = { a 0 , a 1 , a 2 , … } {\displaystyle A=\{a_{0},a_{1},a_{2},\dots \}} of natural numbers in which all pairwise sums a i + a j {\displaystyle a_{i}+a_{j}} (for i ≤ j {\displaystyle i\leq j} ) are different. Sidon sequences are also called Sidon sets; they are named after the Hungarian mathematician Simon Sidon, who introduced the concept in his investigations of Fourier series. The main problem in the study of Sidon sequences, posed by Sidon, is to find the maximum number of elements that a Sidon sequence can contain, up to some bound x {\displaystyle x} . Despite a large body of research, the question has remained unsolved.
Early results Paul Erdős and Pál Turán proved that, for every x > 0 {\displaystyle x>0} , the number of elements smaller than x {\displaystyle x} in a Sidon sequence is at most x + O ( x 4 ) {\displaystyle {\sqrt {x}}+O({\sqrt[{4}]{x}})} . Several years earlier, James Singer had constructed Sidon sequences with x ( 1 − o ( 1 ) ) {\displaystyle {\sqrt {x}}(1-o(1))} terms less than x. The upper bound was improved to x + x 4 + 1 {\displaystyle {\sqrt {x}}+{\sqrt[{4}]{x}}+1} in 1969 and to x + 0.998 x 4 {\displaystyle {\sqrt {x}}+0.998{\sqrt[{4}]{x}}} in 2023. In 1994 Erdős offered 500 dollars for a proof or disproof of the bound x + o ( x ε ) {\displaystyle {\sqrt {x}}+o(x^{\varepsilon })} .
Dense Sidon Sets A Sidon subset A ⊂ [ n ] := { 1 , 2 , … , n } {\displaystyle A\subset [n]:=\{1,2,\dots ,n\}} is called dense if | A | = max | S | {\displaystyle \left|A\right|=\max \left|S\right|} where the maximum is taken over all Sidon subsets of [ n ] {\displaystyle [n]} . The structure of dense Sidon sets has a rich literature and classic constructions by Erdős–Turán, Singer, Bose, Spence, Hughes and Cilleruelo have established that a dense Sidon set A {\displaystyle A} satisfies | A | ≥ ( 1 − o ( 1 ) ) n {\displaystyle \left|A\right|\geq \left(1-o(1)\right){\sqrt {n}}} . As remarked by Ruzsa, "somehow all known constructions of dense Sidon sets involve the primes". A recent result of Balasubramanian and Dutta shows that if a dense Sidon set A = { a 1 , … , a | A | } ⊂ [ n ] {\displaystyle A=\{a_{1},\dots ,a_{\left|A\right|}\}\subset [n]} has cardinality | A | = n 1 / 2 − L ′ {\displaystyle |A|=n^{1/2}-L^{\prime }} , then
a m = m ⋅ n 1 / 2 + O ( n 7 / 8 ) + O ( L 1 / 2 ⋅ n 3 / 4 ) {\displaystyle a_{m}=m\cdot n^{1/2}+{\mathcal {O}}\left(n^{7/8}\right)+{\mathcal {O}}\left(L^{1/2}\cdot n^{3/4}\right)}
… excerpt ends here. Continue reading the full article.
