Secuencia de Sidón

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

El principal problema en el estudio de las secuencias de Sidón, planteado por Sidón, ^{[ 1 ]} es encontrar el número máximo de elementos que una secuencia de Sidón puede contener, hasta cierto límite.${\displaystyle x}$A pesar de la gran cantidad de investigaciones, ^{[ 2 ]} la cuestión sigue sin resolverse. ^{[ 3 ]}

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

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

Un subconjunto de Sidón${\displaystyle A\subset [n]:=\{1,2,\dots ,n\}}$se llama denso si${\displaystyle \left|A\right|=\max \left|S\right|}$donde el máximo se toma sobre todos los subconjuntos de Sidón de${\displaystyle [n]}$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${\displaystyle A}$Satisface${\displaystyle \left|A\right|\geq \left(1-o(1)\right){\sqrt {n}}}$Como señaló Ruzsa , "de alguna manera todas las construcciones conocidas de conjuntos de Sidón densos involucran los números primos". ^{[ 16 ]}

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

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

dónde${\displaystyle L=\max\{0,L^{\prime }\}}$Esto proporciona directamente algunos resultados asintóticos útiles, entre ellos:

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

Los conjuntos densos de Sidon a menudo exhiben simetrías sorprendentes. Por ejemplo, se sabe que los conjuntos densos de Sidon están distribuidos uniformemente, ^{[ 18 ] [ 19 ] [ 20 ]} equidistribuidos en clases de residuos, ^{[ 21 ] [ 22 ]} e incluso en vecindarios de Bohr suaves. ^{[ 23 ]}

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

En la otra dirección, Chowla y Mian observaron que el algoritmo voraz produce una secuencia de Sidón infinita con${\displaystyle A(x)>c{\sqrt[{3}]{x}}}$por cada${\displaystyle x}$. ^{[ 24 ]} Ajtai , Komlós y Szemerédi mejoraron esto con una construcción ^{[ 25 ]} de una secuencia de Sidón con $${\displaystyle A(x)>{\sqrt[{3}]{x\log x}}.}$$

La mejor cota inferior hasta la fecha la dio Imre Z. Ruzsa , quien demostró ^{[ 26 ]} que una secuencia de Sidón con $${\displaystyle A(x)>x^{{\sqrt {2}}-1-o(1)}}$$ Existe. Erdős conjeturó que existe un conjunto infinito de Sidón.${\displaystyle A}$existe para el cual${\displaystyle A(x)>x^{1/2-o(1)}}$se sostiene. Él y Rényi demostraron ^{[ 27 ]} la existencia de una secuencia${\displaystyle \{a_{0},a_{1},\dots \}}$con la densidad conjetural pero satisfaciendo solo la propiedad más débil de que existe una constante${\displaystyle k}$de tal manera que para cada número natural${\displaystyle n}$como máximo hay${\displaystyle k}$soluciones de la ecuación${\displaystyle a_{i}+a_{j}=n}$. (Para ser una secuencia de Sidón se requeriría que${\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. Específicamente, 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${\displaystyle c}$con${\displaystyle 0<c<1}$de tal manera que el rango de la función${\displaystyle f(x)=x^{5}+\lfloor cx^{4}\rfloor }$es una secuencia de Sidón, donde${\displaystyle \lfloor \ \rfloor }$denota la parte entera . Como${\displaystyle c}$es irracional, esta función${\displaystyle f(x)}$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 .

La existencia de secuencias de Sidón que forman una base asintótica de orden${\displaystyle m}$(lo que significa que cada número natural suficientemente grande${\displaystyle n}$se puede escribir como la suma de${\displaystyle m}$números de la secuencia) se ha demostrado para${\displaystyle m=5}$en 2010, ^{[ 28 ]}${\displaystyle m=4}$en 2014, ^{[ 29 ]}${\displaystyle m=3+\varepsilon }$(la suma de cuatro términos con uno menor que${\displaystyle n^{\varepsilon }}$, para valores positivos arbitrariamente pequeños${\displaystyle \varepsilon }$) en 2015 ^{[ 30 ]} y${\displaystyle m=3}$en 2024. ^{[ 31 ] [ 32 ]} Este último fue planteado como un problema en un artículo de Erdős, Sárközy y Sós en 1994. ^{[ 33 ]}

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

Para ver esto, supongamos por contradicción que${\displaystyle S}$es un conjunto de Sidón y no un gobernante de Golomb. Dado que no es un gobernante de Golomb, debe haber cuatro miembros tales que${\displaystyle a_{i}-a_{j}=a_{k}-a_{l}}$De ello se deduce que${\displaystyle a_{i}+a_{l}=a_{k}+a_{j}}$, lo cual contradice la proposición de que${\displaystyle S}$es un conjunto de Sidón. Por lo tanto, todos los conjuntos de Sidón deben ser reglas de Golomb. Siguiendo un razonamiento similar, todas las reglas de Golomb deben ser conjuntos de Sidón.

• secuencia de Moser-de Bruijn
• Conjunto suma