Sidon sequence

Paul Erdős and Pál Turán proved that, for every $x>0$, the number of elements smaller than $x$ in a Sidon sequence is at most $\backslash sqrt\{x\}+O(\backslash sqrt[4]\{x\})$. Several years earlier, James Singer had constructed Sidon sequences with $\backslash sqrt\{x\}(1-o(1))$ terms less than x. The upper bound was improved to $\backslash sqrt\{x\}+\backslash sqrt[4]\{x\}+1$ in 1969{{Cite journal |last=Linström |first=Bern |date=1969 |title=An inequality for B2-sequences |journal=Journal of Combinatorial Theory |volume=6 |issue=2 |pages=211–212|doi=10.1016/S0021-9800(69)80124-9 }} and to $\backslash sqrt\{x\}+0.998\backslash sqrt[4]\{x\}$ in 2023.{{Cite journal |last1=Balogh |first1=József |last2=Füredi |first2=Zoltán |last3=Roy |first3=Souktik |date=2023-05-28 |title=An Upper Bound on the Size of Sidon Sets |url=https://www.tandfonline.com/doi/full/10.1080/00029890.2023.2176667 |journal=The American Mathematical Monthly |language=en |volume=130 |issue=5 |pages=437–445 |doi=10.1080/00029890.2023.2176667 |s2cid=232417382 |issn=0002-9890|arxiv=2103.15850 }}

In 1994 Erdős offered 500 dollars for a proof or disproof of the bound $\backslash sqrt\{x\}+o(x^\backslash varepsilon)$.{{Cite journal |last=Erdős |first=Paul |date=1994 |title=Some problems in number theory, combinatorics and combinatorial geometry. |url=https://mathematica-pannonica.ttk.pte.hu/articles/mp05-2/mp05-2-261-269.pdf |journal=Mathematica Pannonica |volume=5 |issue=2 |pages=261–269}}

A  Sidon subset $A\backslash subset\; [n]\; :=\; \backslash \{1,2,\backslash dots\; ,n\backslash \}$ is called dense if $\backslash left\; |\; A\backslash right\; |\; =\; \backslash max\; \backslash left\; |\; S\backslash right\; |$ where the maximum is taken over all Sidon subsets of $[n]$. The structure of dense Sidon sets has a rich literature{{Cite journal |last=Prendiville |first=Sean |date=July 2022 |title=Solving equations in dense Sidon sets |url=https://www.cambridge.org/core/product/identifier/S0305004121000402/type/journal_article |journal=Mathematical Proceedings of the Cambridge Philosophical Society |language=en |volume=173 |issue=1 |pages=25–34 |doi=10.1017/S0305004121000402 |issn=0305-0041|arxiv=2005.03484 |bibcode=2022MPCPS.173...25P }}{{Cite journal |last1=Eberhard |first1=Sean |last2=Manners |first2=Freddie |date=2023-02-24 |title=The Apparent Structure of Dense Sidon Sets |url=https://www.combinatorics.org/ojs/index.php/eljc/article/view/v30i1p33 |journal=The Electronic Journal of Combinatorics |volume=30 |language=en |pages=P1.33 |doi=10.37236/11191 |issn=1077-8926|arxiv=2107.05744 }} and classic constructions by Erdős–Turán,{{Cite journal |last1=Erdös |first1=P. |last2=Turán |first2=P. |date=October 1941 |title=On a Problem of Sidon in Additive Number Theory, and on some Related Problems |url=http://doi.wiley.com/10.1112/jlms/s1-16.4.212 |journal=Journal of the London Mathematical Society |language=en |volume=s1-16 |issue=4 |pages=212–215 |doi=10.1112/jlms/s1-16.4.212}} Singer,{{Cite journal |last=Singer |first=James |date=1938 |title=A theorem in finite projective geometry and some applications to number theory |journal=Transactions of the American Mathematical Society |language=en |volume=43 |issue=3 |pages=377–385 |doi=10.1090/S0002-9947-1938-1501951-4 |s2cid=121112335 |issn=0002-9947}} Bose,{{Cite journal |last=Bose |first=R. C. |date=1942-06-01 |title=An Affine Analogue of Singer's Theorem |url=https://www.i-scholar.in/index.php/JIMSIMS/article/view/151305./0 |journal=The Journal of the Indian Mathematical Society |language=en |volume=6 |pages=1–15}} Spence,{{Cite journal |last=Ganley |first=Michael J |date=1977-11-01 |title=Direct product difference sets |url=https://linkinghub.elsevier.com/retrieve/pii/0097316577900231 |journal=Journal of Combinatorial Theory, Series A |volume=23 |issue=3 |pages=321–332 |doi=10.1016/0097-3165(77)90023-1 |issn=0097-3165}}{{Cite journal |last=Ruzsa |first=Imre |date=1993 |title=Solving a linear equation in a set of integers I |url=http://dx.doi.org/10.4064/aa-65-3-259-282 |journal=Acta Arithmetica |volume=65 |issue=3 |pages=259–282 |doi=10.4064/aa-65-3-259-282 |issn=0065-1036}} Hughes{{Cite journal |last=Hughes |first=D. R. |date=November 1955 |title=Planar Division Neo-Rings |url=http://dx.doi.org/10.2307/1993000 |journal=Transactions of the American Mathematical Society |volume=80 |issue=2 |pages=502–527 |doi=10.2307/1993000 |jstor=1993000 |issn=0002-9947}} and Cilleruelo{{Cite journal |last=Cilleruelo |first=Javier |date=2012-05-01 |title=Combinatorial problems in finite fields and Sidon sets |url=https://link.springer.com/article/10.1007/s00493-012-2819-4 |journal=Combinatorica |language=en |volume=32 |issue=5 |pages=497–511 |doi=10.1007/s00493-012-2819-4 |issn=1439-6912|arxiv=1003.3576 }} have established that a dense Sidon set $A$ satisfies $\backslash left\; |\; A\backslash right\; |\; \backslash ge\; \backslash left(1-o(1)\backslash right)\backslash sqrt\{n\}$. As remarked by Ruzsa, "somehow all known constructions of dense Sidon sets involve the primes".{{Cite journal |last=Ruzsa |first=Imre Z. |date=1999-11-01 |title=Erdős and the Integers |url=https://linkinghub.elsevier.com/retrieve/pii/S0022314X99923958 |journal=Journal of Number Theory |volume=79 |issue=1 |pages=115–163 |doi=10.1006/jnth.1999.2395 |issn=0022-314X}}

A recent result of Balasubramanian and Dutta{{cite arXiv |last1=Balasubramanian |first1=R. |title=The $m$-th Element of a Sidon Set |date=2024-09-08 |eprint=2409.01986 |last2=Dutta |first2=Sayan|class=math.NT }} shows that if a dense Sidon set $A\; =\; \backslash \{a\_1,\backslash dots\; ,\; a\_\{\backslash left\; |\; A\backslash right\; |\}\backslash \}\backslash subset\; [n]$

has cardinality $|A|=n^\{1/2\}-L^\backslash prime$, then

$a\_m\; =\; m\backslash cdot\; n^\{1/2\}\; +\; \backslash mathcal\; O\backslash left(\; n^\{7/8\}\backslash right)\; +\; \backslash mathcal\; O\backslash left(L^\{1/2\}\backslash cdot\; n^\{3/4\}\backslash right)$

where $L=\backslash max\backslash \{0,L^\backslash prime\backslash \}$. This directly gives some useful asymptotic results including

$\backslash sum\_\{a\backslash in\; A\}\; a^\backslash ell\; =\; \backslash frac\; \{1\}\{\backslash ell\; +1\}\; \backslash cdot\; n^\{\backslash frac\{2\backslash ell\; +1\}\{2\}\}\; +\; \backslash mathcal\; O\; \backslash left(\; n^\{\backslash frac\{8\backslash ell\; +3\}\{8\}\}\; \backslash right)\; +\; \backslash mathcal\; O\backslash left(\; L^\{1/2\}\backslash cdot\; n^\{\backslash frac\{4\backslash ell\; +1\}\{4\}\}\backslash right)$

for any positive integer $\backslash ell$.

Dense Sidon sets often exhibit surprising symmetries. For example, it is known that dense Sidon sets are uniformly distributed,{{Cite journal |last=Erdős |first=P. |last2=Freud |first2=R. |date=June 1991 |title=On sums of a Sidon-sequence |url=https://doi.org/10.1016/0022-314x(91)90083-n |journal=Journal of Number Theory |volume=38 |issue=2 |pages=196–205 |doi=10.1016/0022-314x(91)90083-n |issn=0022-314X}}{{Citation |last=Graham |first=S. W. |title=Bh sequences |date=1996 |work=Analytic Number Theory |pages=431–449 |url=https://doi.org/10.1007/978-1-4612-4086-0_23 |access-date=2025-04-08 |place=Boston, MA |publisher=Birkhäuser Boston |isbn=978-1-4612-8645-5}}{{Cite journal |last=Cilleruelo |first=Javier |last2=Nathanson |first2=Melvyn B. |date=July 2008 |title=Perfect difference sets constructed from Sidon sets |url=https://doi.org/10.1007/s00493-008-2339-4 |journal=Combinatorica |volume=28 |issue=4 |pages=401–414 |doi=10.1007/s00493-008-2339-4 |issn=0209-9683|arxiv=math/0609244 }} equidistributed in residue classes,{{Cite journal |last=Lindström |first=Bernt |date=April 1998 |title=Well Distribution of Sidon Sets in Residue Classes |url=https://doi.org/10.1006/jnth.1997.2217 |journal=Journal of Number Theory |volume=69 |issue=2 |pages=197–200 |doi=10.1006/jnth.1997.2217 |issn=0022-314X}}{{Cite journal |last=Kolountzakis |first=Mihail N |date=May 1999 |title=On the Uniform Distribution in Residue Classes of Dense Sets of Integers with Distinct Sums |url=https://doi.org/10.1006/jnth.1998.2351 |journal=Journal of Number Theory |volume=76 |issue=1 |pages=147–153 |doi=10.1006/jnth.1998.2351 |issn=0022-314X|arxiv=math/9808061 }} and even in smooth Bohr neighbourhoods.{{Cite journal |last=Ortega |first=Miquel |last2=Prendiville |first2=Sean |date=2023-05-04 |title=Extremal Sidon Sets are Fourier Uniform, with Applications to Partition Regularity |url=https://doi.org/10.5802/jtnb.1239 |journal=Journal de théorie des nombres de Bordeaux |volume=35 |issue=1 |pages=115–134 |doi=10.5802/jtnb.1239 |issn=2118-8572|arxiv=2110.13447 }}

Erdős also showed that, for any particular infinite Sidon sequence $A$ with $A(x)$ denoting the number of its elements up to $x$,

$$\backslash liminf\_\{x\; \backslash to\; \backslash infty\}\; \backslash frac\{A(x)\backslash sqrt\{\backslash log\; x\}\}\{\backslash sqrt\{x\}\}\backslash 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\backslash sqrt[3]\{x\}$ for every $x$.{{cite journal

| last1 = Mian | first1 = Abdul Majid

| last2 = Chowla | first2 = S. | author2-link = Sarvadaman Chowla

| journal = Proc. Natl. Acad. Sci. India A

| mr = 0014114

| pages = 3–4

| title = On the B₂ sequences of Sidon

| volume = 14

| year = 1944}}. Ajtai, Komlós, and Szemerédi improved this with a construction{{cite journal

| first1=M. | last1=Ajtai | author1-link=Miklós Ajtai

| first2=J. | last2=Komlós | author2-link=János Komlós (mathematician)

| first3=E. | last3=Szemerédi | author3-link=Endre Szemerédi

| title=A dense infinite Sidon sequence

| journal=European Journal of Combinatorics

| volume=2

| year=1981

| pages=1–11

| mr=0611925

| issue=1

| doi=10.1016/s0195-6698(81)80014-5 | doi-access=}}. of a Sidon sequence with

$$A(x)>\backslash sqrt[3]\{x\backslash log\; x\}.$$

The best lower bound to date was given by Imre Z. Ruzsa, who proved{{cite journal|first=I. Z.|last=Ruzsa|authorlink=Imre Z. Ruzsa|title=An infinite Sidon sequence|journal=Journal of Number Theory|volume=68|year=1998|pages=63–71|mr=1492889|doi=10.1006/jnth.1997.2192|doi-access=free}}. that a Sidon sequence with

$$A(x)>x^\{\backslash sqrt\{2\}-1-o(1)\}$$

exists. Erdős conjectured that an infinite Sidon set $A$ exists for which $A(x)>x^\{1/2-o(1)\}$ holds. He and Rényi showed{{cite journal|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=A.|last2=Rényi|author2-link=Alfréd Rényi|title=Additive properties of random sequences of positive integers|journal=Acta Arithmetica|volume=6|year=1960|pages=83–110|mr=0120213|url=http://www.renyi.hu/~p_erdos/1960-02.pdf|doi=10.4064/aa-6-1-83-110|doi-access=free}}. the existence of a sequence $\backslash \{a\_0,a\_1,\backslash dots\backslash \}$ with the conjectural density but satisfying only the weaker property that there is a constant $k$ such that for every natural number $n$ there are at most $k$ 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 $c$ with

The existence of Sidon sequences that form an asymptotic basis of order $m$ (meaning that every sufficiently large natural number $n$ can be written as the sum of $m$ numbers from the sequence) has been proved for $m=5$ in 2010,{{Cite journal

| last=Kiss |first=S. Z.

| date=2010-07-01

| title=On Sidon sets which are asymptotic bases

| journal=Acta Mathematica Hungarica

| language=en

| volume=128

| issue=1

| pages=46–58

| doi=10.1007/s10474-010-9155-1

| s2cid=96474687

| issn=1588-2632}} $m=4$ in 2014,{{Cite journal |last1=Kiss |first1=Sándor Z. |last2=Rozgonyi |first2=Eszter |last3=Sándor |first3=Csaba |date=2014-12-01 |title=On Sidon sets which are asymptotic bases of order $4$ |url=https://projecteuclid.org/journals/functiones-et-approximatio-commentarii-mathematici/volume-51/issue-2/On-Sidon-sets-which-are-asymptotic-bases-of-order-4/10.7169/facm/2014.51.2.10.full |journal=Functiones et Approximatio Commentarii Mathematici |volume=51 |issue=2 |doi=10.7169/facm/2014.51.2.10 |arxiv=1304.5749 |s2cid=119121815 |issn=0208-6573}} $m=3+\backslash varepsilon$ (the sum of four terms with one smaller than $n^\backslash varepsilon$, for arbitrarily small positive $\backslash varepsilon$) in 2015{{Cite journal |last=Cilleruelo |first=Javier |date=November 2015 |title=On Sidon sets and asymptotic bases |url=http://doi.wiley.com/10.1112/plms/pdv050 |journal=Proceedings of the London Mathematical Society |language=en |volume=111 |issue=5 |pages=1206–1230 |doi=10.1112/plms/pdv050|s2cid=34849568 }} and $m=3$ in 2024.{{Cite journal |last=Pilatte |first=Cédric |date=2024-05-10 |title=A solution to the Erdős–Sárközy–Sós problem on asymptotic Sidon bases of order 3 |url=http://dx.doi.org/10.1112/s0010437x24007140 |journal=Compositio Mathematica |volume=160 |issue=6 |pages=1418–1432 |doi=10.1112/s0010437x24007140 |issn=0010-437X|arxiv=2303.09659 }}{{Cite web |date=2023-06-05 |title=First-Year Graduate Finds Paradoxical Number Set |url=https://www.quantamagazine.org/first-year-graduate-finds-paradoxical-number-set-20230605/ |access-date=2023-06-13 |website=Quanta Magazine |language=en}} This last one was posed as a problem in a paper of Erdős, Sárközy and Sós in 1994.{{Cite journal |last1=Erdős |first1=P. |last2=Sárközy |first2=A. |last3=Sós |first3=V. T. |date=1994-12-31 |title=On additive properties of general sequences |url=https://dx.doi.org/10.1016/0012-365X%2894%2900108-U |journal=Discrete Mathematics |language=en |volume=136 |issue=1 |pages=75–99 |doi=10.1016/0012-365X(94)00108-U |s2cid=38168554 |issn=0012-365X}}

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

To see this, suppose for a contradiction that $S$ 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 $S$ is a Sidon set. Therefore all Sidon sets must be Golomb rulers. By a similar argument, all Golomb rulers must be Sidon sets.

• Moser–de Bruijn sequence
• Sumset

{{reflist}}

{{DEFAULTSORT:Sidon Sequence}}

Category:Number theory

Category:Combinatorics