Sidon sequence explained

In number theory, a Sidon sequence is a sequence

A=\{a_0,a_1,a_2,...\}

of natural numbers in which all pairwise sums

a_i+a_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,^[1] is to find the maximum number of elements that a Sidon sequence can contain, up to some bound

. Despite a large body of research,^[2] the question has remained unsolved.^[3]

Early results

Paul Erdős and Pál Turán proved that, for every

x>0

, the number of elements smaller than

in a Sidon sequence is at most

\sqrt{x}+O(\sqrt[4]{x})

. Several years earlier, James Singer had constructed Sidon sequences with

\sqrt{x}(1-o(1))

terms less than x. The upper bound was improved to

\sqrt{x}+\sqrt[4]{x}+1

in 1969^[4] and to

\sqrt{x}+0.998\sqrt[4]{x}

in 2023.^[5]

In 1994 Erdős offered 500 dollars for a proof or disproof of the bound

\sqrt{x}+o(x^\varepsilon)

.^[6]

Dense Sidon Sets

A Sidon subset

A\subset[n]:=\{1,2,...,n\}

is called dense if

\left|A\right|=max\left|S\right|

where the maximum is taken over all Sidon subsets of

[n]

. The structure of dense Sidon sets has a rich literature^[7] ^[8] and classic constructions by Erdős–Turán,^[9] Singer,^[10] Bose,^[11] Spence,^[12] ^[13] Hughes^[14] and Cilleruelo^[15] have established that a dense Sidon set

satisfies

\left|A\right|\ge\left(1-o(1)\right)\sqrt{n}

. As remarked by Ruzsa, "somehow all known constructions of dense Sidon sets involve the primes".^[16]

A recent result of Balasubramanian and Dutta^[17] shows that if a dense Sidon set

A=\{a_1,...,a_\left\}\subset[n]

has cardinality

|A|=n^1/2-L^\prime

, then

a_m=m ⋅ n^1/2+lO\left(n^7/8\right)+lO\left(L^1/2 ⋅ n^3/4\right)

where

L=max\{0,L^\prime\}

. This directly gives some useful asymptotic results including

\sum_a\ina^\ell=

	1
	\ell+1

⋅

	2\ell+1
	2

+lO\left(

	8\ell+3
	8

\right)+lO\left(L^1/2 ⋅

	4\ell+1
	4

\right)

for any positive integer

\ell

Infinite Sidon sequences

Erdős also showed that, for any particular infinite Sidon sequence

with

A(x)

denoting the number of its elements up to

\liminf_ \frac\leq 1.

That is, infinite Sidon sequences are thinner than the densest finite Sidon sequences.

For the other direction, Chowla and Mian observed that the greedy algorithm gives an infinite Sidon sequence with

A(x)>c\sqrt[3]{x}

for every

.^[18] Ajtai, Komlós, and Szemerédi improved this with a construction^[19] of a Sidon sequence with

A(x)>\sqrt[3].

The best lower bound to date was given by Imre Z. Ruzsa, who proved^[20] that a Sidon sequence with $A(x)>x^$ exists. Erdős conjectured that an infinite Sidon set

exists for which

A(x)>x^1/2-o(1)

holds. He and Rényi showed^[21] the existence of a sequence

\{a_0,a_1,...\}

with the conjectural density but satisfying only the weaker property that there is a constant

such that for every natural number

there are at most

solutions of the equation

a_i+a_j=n

. (To be a Sidon sequence would require that

k=1

Erdős further conjectured that there exists a nonconstant integer-coefficient polynomial whose values at the natural numbers form a Sidon sequence. Specifically, he asked if the set of fifth powers is a Sidon set. Ruzsa came close to this by showing that there is a real number

with

0<c<1

such that the range of the function

f(x)=x^5+\lfloorcx^4\rfloor

is a Sidon sequence, where

\lfloor \rfloor

denotes the integer part. As

is irrational, this function

f(x)

is not a polynomial. The statement that the set of fifth powers is a Sidon set is a special case of the later conjecture of Lander, Parkin and Selfridge.

Sidon sequences which are asymptotic bases

The existence of Sidon sequences that form an asymptotic basis of order

(meaning that every sufficiently large natural number

can be written as the sum of

numbers from the sequence) has been proved for

m=5

in 2010,^[22]

m=4

in 2014,^[23]

m=3+\varepsilon

(the sum of four terms with one smaller than

n^\varepsilon

, for arbitrarily small positive

\varepsilon

) in 2015^[24] and

m=3

in 2023 as a preprint,^[25] ^[26] this later one was posed as a problem in a paper of Erdős, Sárközy and Sós in 1994.^[27]

Relationship to Golomb rulers

All finite Sidon sets are Golomb rulers, and vice versa.

To see this, suppose for a contradiction that

is a Sidon set and not a Golomb ruler. Since it is not a Golomb ruler, there must be four members such that

a_i-a_j=a_k-a_l

. It follows that

a_i+a_l=a_k+a_j

, which contradicts the proposition that

is a Sidon set. Therefore all Sidon sets must be Golomb rulers. By a similar argument, all Golomb rulers must be Sidon sets.

Notes and References

P.. Erdős. Paul Erdős. P.. Turán. Pál Turán. On a problem of Sidon in additive number theory and on some related problems. J. London Math. Soc.. 16. 1941. 4 . 212–215. 10.1112/jlms/s1-16.4.212. . Addendum, 19 (1944), 208.
K.. O'Bryant. A complete annotated bibliography of work related to Sidon sequences. Electronic Journal of Combinatorics. 11. 2004. 39. 10.37236/32. free. .
Book: Guy, Richard K. . Richard K. Guy . Unsolved problems in number theory . . 3rd . 2004 . 0-387-20860-7 . 1058.11001. C9: Packing sums in pairs. 175–180.
Linström . Bern . 1969 . An inequality for B2-sequences . Journal of Combinatorial Theory . 6 . 2 . 211–212. 10.1016/S0021-9800(69)80124-9 .
Balogh . József . Füredi . Zoltán . Roy . Souktik . 2023-05-28 . An Upper Bound on the Size of Sidon Sets . The American Mathematical Monthly . en . 130 . 5 . 437–445 . 10.1080/00029890.2023.2176667 . 232417382 . 0002-9890. 2103.15850 .
Erdős . Paul . 1994 . Some problems in number theory, combinatorics and combinatorial geometry. . Mathematica Pannonica . 5 . 2 . 261–269.
Prendiville . Sean . July 2022 . Solving equations in dense Sidon sets . Mathematical Proceedings of the Cambridge Philosophical Society . en . 173 . 1 . 25–34 . 10.1017/S0305004121000402 . 0305-0041. 2005.03484 . 2022MPCPS.173...25P .
Eberhard . Sean . Manners . Freddie . 2023-02-24 . The Apparent Structure of Dense Sidon Sets . The Electronic Journal of Combinatorics . 30 . en . P1.33 . 10.37236/11191 . 1077-8926. 2107.05744 .
Erdös . P. . Turán . P. . October 1941 . On a Problem of Sidon in Additive Number Theory, and on some Related Problems . Journal of the London Mathematical Society . en . s1-16 . 4 . 212–215 . 10.1112/jlms/s1-16.4.212.
Singer . James . 1938 . A theorem in finite projective geometry and some applications to number theory . Transactions of the American Mathematical Society . en . 43 . 3 . 377–385 . 10.1090/S0002-9947-1938-1501951-4 . 121112335 . 0002-9947.
Bose . R. C. . 1942-06-01 . An Affine Analogue of Singer's Theorem . The Journal of the Indian Mathematical Society . en . 6 . 1–15.
Ganley . Michael J . 1977-11-01 . Direct product difference sets . Journal of Combinatorial Theory, Series A . 23 . 3 . 321–332 . 10.1016/0097-3165(77)90023-1 . 0097-3165.
Ruzsa . Imre . 1993 . Solving a linear equation in a set of integers I . Acta Arithmetica . 65 . 3 . 259–282 . 10.4064/aa-65-3-259-282 . 0065-1036.
Hughes . D. R. . November 1955 . Planar Division Neo-Rings . Transactions of the American Mathematical Society . 80 . 2 . 502–527 . 10.2307/1993000 . 1993000 . 0002-9947.
Cilleruelo . Javier . 2012-05-01 . Combinatorial problems in finite fields and Sidon sets . Combinatorica . en . 32 . 5 . 497–511 . 10.1007/s00493-012-2819-4 . 1439-6912.
Ruzsa . Imre Z. . 1999-11-01 . Erdős and the Integers . Journal of Number Theory . 79 . 1 . 115–163 . 10.1006/jnth.1999.2395 . 0022-314X.
Balasubramanian . R. . The $m$-th Element of a Sidon Set . 2024-09-08 . 2409.01986 . Dutta . Sayan. math.NT .
Mian . Abdul Majid . Chowla . S. . Sarvadaman Chowla . Proc. Natl. Acad. Sci. India A . 0014114 . 3–4 . On the B₂ sequences of Sidon . 14 . 1944. .
M. . Ajtai . Miklós Ajtai. J. . Komlós . János Komlós (mathematician). E. . Szemerédi . Endre Szemerédi. A dense infinite Sidon sequence. European Journal of Combinatorics. 2. 1981. 1–11. 0611925. 1. 10.1016/s0195-6698(81)80014-5 . .
I. Z.. Ruzsa. Imre Z. Ruzsa. An infinite Sidon sequence. Journal of Number Theory. 68. 1998. 63–71. 1492889. 10.1006/jnth.1997.2192. free. .
P.. Erdős. Paul Erdős. A.. Rényi. Alfréd Rényi. Additive properties of random sequences of positive integers. Acta Arithmetica. 6. 1960. 83–110. 0120213. 10.4064/aa-6-1-83-110. free. .
Kiss . S. Z.. 2010-07-01. On Sidon sets which are asymptotic bases. Acta Mathematica Hungarica. en. 128. 1. 46–58. 10.1007/s10474-010-9155-1. 96474687. 1588-2632.
Kiss . Sándor Z. . Rozgonyi . Eszter . Sándor . Csaba . 2014-12-01 . On Sidon sets which are asymptotic bases of order $4$ . Functiones et Approximatio Commentarii Mathematici . 51 . 2 . 10.7169/facm/2014.51.2.10 . 1304.5749 . 119121815 . 0208-6573.
Cilleruelo . Javier . November 2015 . On Sidon sets and asymptotic bases . Proceedings of the London Mathematical Society . en . 111 . 5 . 1206–1230 . 10.1112/plms/pdv050. 34849568 .
Pilatte . Cédric . 2024-05-10 . A solution to the Erdős–Sárközy–Sós problem on asymptotic Sidon bases of order 3 . Compositio Mathematica . 160 . 6 . 1418–1432 . 10.1112/s0010437x24007140 . 0010-437X. 2303.09659 .
Web site: 2023-06-05 . First-Year Graduate Finds Paradoxical Number Set . 2023-06-13 . Quanta Magazine . en.
Erdős . P. . Sárközy . A. . Sós . V. T. . 1994-12-31 . On additive properties of general sequences . Discrete Mathematics . en . 136 . 1 . 75–99 . 10.1016/0012-365X(94)00108-U . 38168554 . 0012-365X.