Secuencia de Sidón

En teoría de números , una sucesión de Sidón es una sucesión de números naturales en la que todas las sumas por pares (para ) son diferentes. Las sucesiones de Sidón también se denominan conjuntos de Sidón ; reciben su nombre del matemático húngaro Simon Sidon , quien introdujo el concepto en sus investigaciones sobre las series de Fourier . ${\displaystyle A=\{a_{0},a_{1},a_{2},\puntos \}}$$Estilo de visualización ai+aj$ ${\displaystyle i\leq j}$

El principal problema en el estudio de las secuencias de Sidon, planteado por Sidon, ^[1] es encontrar el número máximo de elementos que una secuencia de Sidon puede contener, hasta cierto límite . A pesar de un gran cuerpo de investigación, ^[2] la cuestión ha permanecido sin resolver. ^[3]${\estilo de visualización x}$

Paul Erdős y Pál Turán demostraron que, para cada , el número de elementos menores que en una sucesión de Sidón es como máximo . Varios años antes, James Singer había construido sucesiones de Sidón con términos menores que x . El límite superior se mejoró a en 1969 ^[4] y a en 2023. ^[5]${\displaystyle x>0}$${\estilo de visualización x}$${\displaystyle {\sqrt {x}}+O({\sqrt[{4}]{x}})}$${\displaystyle {\sqrt {x}}(1-o(1))}$${\displaystyle {\sqrt {x}}+{\sqrt[{4}]{x}}+1}$${\displaystyle {\sqrt {x}}+0,998{\sqrt[{4}]{x}}}$

En 1994 Erdős ofreció 500 dólares por una prueba o refutación del límite . ^[6]${\displaystyle {\sqrt {x}}+o(x^{\varepsilon })}$

Un subconjunto de Sidón se denomina denso si donde el máximo se toma sobre todos los subconjuntos de Sidón de . La estructura de los conjuntos densos de Sidón tiene una rica literatura ^{[7] [8]} y las construcciones clásicas de Erdős–Turán, ^[9] Singer, ^[10] Bose , ^[11] Spence, ^{[12] [13]} Hughes ^[14] y Cilleruelo ^[15] han establecido que un conjunto denso de Sidón satisface . Como señaló Ruzsa , "de alguna manera todas las construcciones conocidas de conjuntos densos de Sidón involucran a los primos". ^[16]${\displaystyle A\subset [n]:=\{1,2,\puntos ,n\}}$${\displaystyle \izquierda|A\derecha|=\max \izquierda|S\derecha|}$${\estilo de visualización [n]}$ ${\estilo de visualización A}$${\displaystyle \left|A\right|\geq \left(1-o(1)\right){\sqrt {n}}}$

Un resultado reciente de Balasubramanian y Dutta ^[17] muestra que si un conjunto denso de Sidon tiene cardinalidad , entonces ${\displaystyle A=\{a_{1},\dots ,a_{\left|A\right|}\}\subset [n]}$${\displaystyle |A|=n^{1/2}-L^{\prime }}$

${\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)}$

donde . Esto proporciona directamente algunos resultados asintóticos útiles, incluidos ${\displaystyle L=\max\{0,L^{\prime }\}}$

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

para cualquier entero positivo . ${\displaystyle \ell }$

Erdős también demostró que, para cualquier secuencia infinita de Sidón en particular, con denotando el número de sus elementos hasta , Es decir, las secuencias infinitas de Sidón son más delgadas que las secuencias finitas de Sidón más densas. ${\displaystyle A}$${\displaystyle A(x)}$${\displaystyle x}$$${\displaystyle \liminf _{x\to \infty }{\frac {A(x){\sqrt {\log x}}}{\sqrt {x}}}\leq 1.}$$

Para la otra dirección, Chowla y Mian observaron que el algoritmo voraz da una secuencia de Sidon infinita con para cada . ^[18] Ajtai , Komlós y Szemerédi mejoraron esto con una construcción ^[19] de una secuencia de Sidon con ${\displaystyle A(x)>c{\sqrt[{3}]{x}}}$${\displaystyle x}$ $${\displaystyle A(x)>{\sqrt[{3}]{x\log x}}.}$$

El mejor límite inferior hasta la fecha fue dado por Imre Z. Ruzsa , quien demostró ^[20] que existe una secuencia de Sidón con . Erdős conjeturó que existe un conjunto de Sidón infinito para el cual se cumple. Él y Rényi demostraron ^[21] la existencia de una secuencia con la densidad conjetural pero que satisface solo la propiedad más débil de que existe una constante tal que para cada número natural hay como máximo soluciones de la ecuación . (Para ser una secuencia de Sidón se requeriría que .) $${\displaystyle A(x)>x^{{\sqrt {2}}-1-o(1)}}$$${\displaystyle A}$${\displaystyle A(x)>x^{1/2-o(1)}}$${\displaystyle \{a_{0},a_{1},\dots \}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle a_{i}+a_{j}=n}$${\displaystyle k=1}$

Erdős conjeturó además que existe un polinomio de coeficiente entero no constante cuyos valores en los números naturales forman una sucesión de Sidón. En concreto, preguntó si el conjunto de quintas potencias es un conjunto de Sidón. Ruzsa se acercó a esto al demostrar que existe un número real con tal que el rango de la función es una sucesión de Sidón, donde denota la parte entera . Como es irracional, esta función no es un polinomio. La afirmación de que el conjunto de quintas potencias es un conjunto de Sidón es un caso especial de la conjetura posterior de Lander, Parkin y Selfridge . ${\displaystyle c}$${\displaystyle 0<c<1}$${\displaystyle f(x)=x^{5}+\lfloor cx^{4}\rfloor }$${\displaystyle \lfloor \ \rfloor }$${\displaystyle c}$${\displaystyle f(x)}$

La existencia de secuencias de Sidón que forman una base asintótica de orden (lo que significa que cada número natural suficientemente grande puede escribirse como la suma de números de la secuencia) se ha demostrado en 2010, ^[22] en 2014, ^[23] (la suma de cuatro términos con uno menor que , para α positivo arbitrariamente pequeño ) en 2015 ^[24] y en 2023 como preimpresión, ^{[25] [26]} este último se planteó como un problema en un artículo de Erdős, Sárközy y Sós en 1994. ^[27]${\displaystyle m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle m=5}$ ${\displaystyle m=4}$ ${\displaystyle m=3+\varepsilon }$${\displaystyle n^{\varepsilon }}$${\displaystyle \varepsilon }$${\displaystyle m=3}$

Todos los conjuntos finitos de Sidón son reglas de Golomb , y viceversa.

Para ver esto, supongamos que existe una contradicción entre un conjunto de Sidón y un gobernante de Golomb. Como no es un gobernante de Golomb, debe haber cuatro miembros tales que . De ello se deduce que , lo que contradice la proposición de que es un conjunto de Sidón. Por lo tanto, todos los conjuntos de Sidón deben ser gobernantes de Golomb. Por un argumento similar, todos los gobernantes de Golomb deben ser conjuntos de Sidón. ${\displaystyle S}$${\displaystyle a_{i}-a_{j}=a_{k}-a_{l}}$${\displaystyle a_{i}+a_{l}=a_{k}+a_{j}}$${\displaystyle S}$

• Secuencia de Moser-de Bruijn
• Suma