Conjunto libre de diferencias cuadráticas

En matemáticas , un conjunto sin diferencias cuadradas es un conjunto de números naturales , ninguno de los cuales difiere en un número cuadrado . Hillel Furstenberg y András Sárközy demostraron a finales de la década de 1970 el teorema de Furstenberg-Sárközy de la teoría aditiva de números, que muestra que, en cierto sentido, estos conjuntos no pueden ser muy grandes. En el juego de restar un cuadrado , las posiciones donde el siguiente jugador pierde forman un conjunto sin diferencias cuadradas. Otro conjunto sin diferencias cuadradas se obtiene al duplicar la secuencia de Moser-de Bruijn .

El límite superior más conocido sobre el tamaño de un conjunto de números sin diferencias cuadradas hasta${\displaystyle n}$es solo ligeramente sublineal, pero los conjuntos más grandes conocidos de esta forma son significativamente más pequeños, de tamaño${\displaystyle \approx n^{0.733412}}$Cerrar la brecha entre estos límites superior e inferior sigue siendo un problema abierto . Los límites de tamaño sublineales en conjuntos libres de diferencias cuadradas pueden generalizarse a conjuntos donde ciertos otros polinomios están prohibidos como diferencias entre pares de elementos.

Un ejemplo de un conjunto sin diferencias cuadradas surge en el juego de restar un cuadrado , inventado por Richard A. Epstein y descrito por primera vez en 1966 por Solomon W. Golomb . En este juego, dos jugadores se turnan para retirar monedas de una pila; el jugador que retira la última moneda gana. En cada turno, el jugador solo puede retirar una cantidad de monedas no nula de la pila. ^{[ 1 ]} Cualquier posición en este juego se puede describir mediante un número entero , su número de monedas. Los enteros no negativos se pueden dividir en posiciones "frías", en las que el jugador que está a punto de moverse está perdiendo, y posiciones "calientes", en las que el jugador que está a punto de moverse puede ganar moviéndose a una posición fría. No puede haber dos posiciones frías que difieran en un cuadrado, porque si lo hicieran, un jugador que se enfrentara a la posición mayor podría moverse a la posición menor y ganar. Por lo tanto, las posiciones frías forman un conjunto sin diferencias cuadradas:

Estas posiciones se pueden generar mediante un algoritmo voraz en el que las posiciones frías se generan en orden numérico, seleccionando en cada paso el número más pequeño que no tenga una diferencia de cuadrado con ningún número seleccionado previamente. ^{[ 1 ] [ 2 ]} Como observó Golomb, las posiciones frías son infinitas, y más aún el número de posiciones frías hasta${\displaystyle n}$es al menos proporcional a${\displaystyle {\sqrt {n}}}$. Porque, si hubiera menos posiciones frías, no habría suficientes para proporcionar un movimiento ganador a cada posición caliente. ^{[ 1 ]} Sin embargo, el teorema de Furstenberg-Sárközy muestra que las posiciones frías son menos frecuentes que las posiciones calientes: para cada${\displaystyle \varepsilon >0}$y para todos los suficientemente grandes${\displaystyle n}$, la proporción de posiciones frías hasta${\displaystyle n}$es como máximo${\displaystyle \varepsilon }$. Es decir, cuando se enfrenta a una posición inicial en el rango de 1 a${\displaystyle n}$, el primer jugador puede ganar desde la mayoría de estas posiciones. ^{[ 3 ]} La evidencia numérica sugiere que el número real de posiciones frías hasta${\displaystyle n}$es aproximadamente${\displaystyle n^{0.7}}$. ^{[ 4 ]}

Según el teorema de Furstenberg-Sárközy, si${\displaystyle S}$es un conjunto libre de diferencias cuadradas, entonces la densidad natural de${\displaystyle S}$es cero. Es decir, para cada${\displaystyle \varepsilon >0}$y para todos suficientemente grandes${\displaystyle n}$, la fracción de los números hasta${\displaystyle n}$que están en${\displaystyle S}$es menor que${\displaystyle \varepsilon }$. De forma equivalente, todo conjunto de números naturales con densidad superior positiva contiene dos números cuya diferencia es un cuadrado, y más fuertemente contiene infinitos pares de este tipo. ^{[ 5 ]} El teorema de Furstenberg-Sárközy fue conjeturado por László Lovász y demostrado independientemente a finales de la década de 1970 por Hillel Furstenberg y András Sárközy , de quienes recibe su nombre. ^{[ 6 ] [ 7 ]} Desde su trabajo, se han publicado varias otras demostraciones del mismo resultado, generalmente simplificando las demostraciones anteriores o reforzando los límites sobre cuán disperso debe ser un conjunto libre de diferencias cuadradas. ^{[ 8 ] [ 9 ] [ 10 ]} El mejor límite superior conocido actualmente se debe a Thomas Bloom y James Maynard , ^{[ 11 ]} quienes demuestran que un conjunto libre de diferencias cuadradas puede incluir como máximo $${\displaystyle O\!\left({\frac {n}{(\log n)^{c\log \log \log n}}}\right)}$$ de los enteros de${\displaystyle 0}$a${\displaystyle n}$, como se expresa en notación de la gran O , donde${\displaystyle c>0}$es una constante absoluta.

La mayoría de estas demostraciones que establecen cotas superiores cuantitativas utilizan el análisis de Fourier o la teoría ergódica , aunque ninguna de ellas es necesaria para demostrar el resultado más débil de que todo conjunto libre de diferencias cuadradas tiene densidad cero. ^{[ 10 ]}

Paul Erdős conjeturó que todo conjunto libre de diferencias cuadradas tiene $${\displaystyle O(n^{1/2}\log ^{k}n)}$$ elementos hasta${\displaystyle n}$, por alguna constante${\displaystyle k}$, pero esto fue refutado por Sárközy, quien demostró que existen secuencias más densas. Sárközy debilitó la conjetura de Erdős para sugerir que, para cada${\displaystyle \varepsilon >0}$, cada conjunto libre de diferencias cuadradas tiene $${\displaystyle O(n^{1/2+\varepsilon })}$$ elementos hasta${\displaystyle n}$. ^{[ 12 ]} Esto, a su vez, fue refutado por Imre Z. Ruzsa , quien encontró conjuntos libres de diferencias cuadradas con hasta $${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{65}7)/2}{\big )}\approx n^{0.733077}}$$ elementos. ^{[ 13 ]}

La construcción de Ruzsa elige un número entero libre de cuadrados.${\displaystyle b}$como la raíz de la base-${\displaystyle b}$notación para los enteros, de modo que exista un conjunto grande${\displaystyle R}$de números de${\displaystyle 0}$a${\displaystyle b-1}$ninguna de cuyas diferencias son cuadrados módulo${\displaystyle b}$. Luego elige su conjunto libre de diferencias cuadradas como los números que, en base-${\displaystyle b}$notación, tienen miembros de${\displaystyle R}$en sus posiciones de dígitos pares . Los dígitos en posiciones impares de estos números pueden ser arbitrarios. Ruzsa encontró el conjunto de siete elementos.${\displaystyle R=\{0,15,21,27,42,48,59\}}$módulo${\displaystyle b=65}$, dando el límite establecido. Posteriormente, la construcción de Ruzsa se ha mejorado utilizando una base diferente,${\displaystyle b=205}$, para dar conjuntos libres de diferencias cuadradas con tamaño ^{[ 14 ] [ 15 ]}$${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{205}12)/2}{\big )}\approx n^{0.733412}.}$$ Cuando se aplica a la base${\displaystyle b=2}$, la misma construcción genera la secuencia de Moser-de Bruijn multiplicada por dos, un conjunto libre de diferencias cuadradas${\displaystyle O(n^{1/2})}$elementos. Esto es demasiado escaso para proporcionar cotas inferiores no triviales en el teorema de Furstenberg-Sárközy, pero la misma secuencia tiene otras propiedades matemáticas notables. ^{[ 16 ]}

Problema sin resolver en matemáticas

¿Hay un exponente?${\displaystyle c<1}$de tal manera que cada subconjunto libre de diferencias cuadradas de${\displaystyle [0,n]}$tiene${\displaystyle O(n^{c})}$¿elementos?

Más problemas sin resolver en matemáticas

Con base en estos resultados, se ha conjeturado que para cada${\displaystyle \varepsilon >0}$ y cada suficientemente grande${\displaystyle n}$existen subconjuntos libres de diferencias cuadradas de los números de${\displaystyle 0}$a${\displaystyle n}$con${\displaystyle \Omega (n^{1-\varepsilon })}$elementos. Es decir, si esta conjetura es cierta, el exponente de uno en las cotas superiores del teorema de Furstenberg-Sárközy no puede disminuirse. ^{[ 9 ]} Como posibilidad alternativa, el exponente 3/4 se ha identificado como "una limitación natural a la construcción de Ruzsa" y otro candidato para la verdadera tasa máxima de crecimiento de estos conjuntos. ^{[ 17 ]}

La cota superior del teorema de Furstenberg-Sárközy se puede generalizar desde conjuntos que evitan diferencias cuadradas a conjuntos que evitan diferencias en${\displaystyle p(\mathbb {N} )}$, los valores en los enteros de un polinomio${\displaystyle p}$con coeficientes enteros , siempre que los valores de${\displaystyle p}$incluir un múltiplo entero de cada entero. La condición sobre los múltiplos de enteros es necesaria para este resultado, porque si hay un entero${\displaystyle k}$cuyos múltiplos no aparecen en${\displaystyle p(\mathbb {N} )}$, entonces los múltiplos de${\displaystyle k}$formarían un conjunto de densidad no nula sin diferencias en${\displaystyle p(\mathbb {N} )}$. ^{[ 18 ]}