Conjunto libre de diferencias cuadradas

Números cuyas diferencias no son cuadrados

En matemáticas , un conjunto libre de diferencias al cuadrado es un conjunto de números naturales , de los cuales ninguno de los dos difiere en un número al cuadrado . Hillel Furstenberg y András Sárközy demostraron a finales de los años 1970 el teorema de Furstenberg-Sárközy de la teoría aditiva de números, mostrando que, en cierto sentido, estos conjuntos no pueden ser muy grandes. En el juego de restar un cuadrado , las posiciones en las que el siguiente jugador pierde forman un conjunto libre de diferencias al cuadrado. Otro conjunto libre de diferencias al cuadrado se obtiene duplicando la sucesión de Moser–de Bruijn .

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

Ejemplo

Un ejemplo de un conjunto sin diferencias de cuadrados 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 de monedas; el jugador que retira la última moneda gana. En cada turno, el jugador solo puede retirar un número de monedas distinto de cero de la pila. ^[1] Cualquier posición en este juego puede describirse mediante un 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 mover está perdiendo, y posiciones "calientes", en las que el jugador que está a punto de mover puede ganar moviéndose a una posición fría. No hay dos posiciones frías que puedan diferir en un cuadrado, porque si lo hicieran, entonces un jugador que se enfrenta a la mayor de las dos posiciones podría moverse a la posición más pequeña y ganar. Por lo tanto, las posiciones frías forman un conjunto sin diferencia de cuadrados:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (secuencia A030193 en la OEIS )

Estas posiciones pueden generarse 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 al cuadrado con ningún número seleccionado previamente. ^{[1] [2]} Como observó Golomb, las posiciones frías son infinitas y, más fuertemente, el número de posiciones frías hasta es al menos proporcional a . Porque, si hubiera menos posiciones frías, no habría suficientes para proporcionar un movimiento ganador a cada posición caliente. ^[1] El teorema de Furstenberg-Sárközy muestra, sin embargo, que las posiciones frías son menos frecuentes que las posiciones calientes: para cada , y para todos los suficientemente grandes , la proporción de posiciones frías hasta es como máximo . Es decir, cuando se enfrenta a una posición inicial en el rango de 1 a , 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 es aproximadamente . ^[4] ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n^{0.7}}$

Límites superiores

Según el teorema de Furstenberg-Sárközy, si es un conjunto libre de diferencias al cuadrado, entonces la densidad natural de es cero. Es decir, para cada , y para todos los suficientemente grandes , la fracción de los números hasta que están en es menor que . Equivalentemente, cada 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 fines 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 fortaleciendo los límites sobre cuán disperso debe ser un conjunto libre de diferencias al cuadrado. ^{[8] [9] [10]} El mejor límite superior conocido actualmente se debe a Thomas Bloom y James Maynard , ^[11] quienes muestran que un conjunto libre de diferencias al cuadrado puede incluir como máximo los números enteros de a , expresados ​​en notación O grande , donde es alguna constante absoluta. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ $${\displaystyle O\!\left({\frac {n}{(\log n)^{c\log \log \log n}}}\right)}$$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle c>0}$

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

Límites inferiores

Paul Erdős conjeturó que todo conjunto libre de diferencias cuadradas tiene elementos hasta , para alguna constante , 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 , todo conjunto libre de diferencias cuadradas tiene elementos hasta . ^[12] Esto, a su vez, fue refutado por Imre Z. Ruzsa , quien encontró conjuntos libres de diferencias cuadradas con hasta elementos. ^[13] $${\displaystyle O(n^{1/2}\log ^{k}n)}$$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon >0}$ $${\displaystyle O(n^{1/2+\varepsilon })}$$ ${\displaystyle n}$ $${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{65}7)/2}{\big )}\approx n^{0.733077}}$$

La construcción de Ruzsa elige un entero sin cuadrados como el radio de la notación base para los enteros, de modo que existe un gran conjunto de números de a ninguno de cuyas diferencias son cuadrados módulo . Luego elige su conjunto sin diferencias cuadradas para que sean los números que, en la notación base, tienen miembros de 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 módulo , dando el límite establecido. Posteriormente, la construcción de Ruzsa se ha mejorado utilizando una base diferente, , para dar conjuntos sin diferencias cuadradas con tamaño ^{[14] [15]} Cuando se aplica a la base , la misma construcción genera la secuencia de Moser–de Bruijn multiplicada por dos, un conjunto de elementos sin diferencias cuadradas . Esto es demasiado escaso para proporcionar límites inferiores no triviales en el teorema de Furstenberg–Sárközy, pero la misma secuencia tiene otras propiedades matemáticas notables. ^[16] ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle 0}$ ${\displaystyle b-1}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle R=\{0,15,21,27,42,48,59\}}$ ${\displaystyle b=65}$ ${\displaystyle b=205}$ $${\displaystyle \Omega {\big (}n^{(1\,+\,\log _{205}12)/2}{\big )}\approx n^{0.733412}.}$$ ${\displaystyle b=2}$ ${\displaystyle O(n^{1/2})}$

Problema sin resolver en matemáticas :

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

(más problemas sin resolver en matemáticas)

Con base en estos resultados, se ha conjeturado que para cada uno de los conjuntos suficientemente grandes existen subconjuntos libres de diferencias cuadradas de los números de a con elementos. Es decir, si esta conjetura es cierta, el exponente de uno en los límites superiores del teorema de Furstenberg-Sárközy no puede reducirse. ^[9] Como posibilidad alternativa, el exponente 3/4 ha sido 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] ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle \Omega (n^{1-\varepsilon })}$

Generalización a otros polinomios

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

Referencias

1. Golomb, Solomon W. (1966), "Una investigación matemática de los juegos de "quitar"", Revista de teoría combinatoria , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , MR  0209015.
2. Sloane, N. J. A. (ed.), "Secuencia A030193", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
3. La aplicabilidad de este teorema a la secuencia producida por el algoritmo voraz está implícita en Ruzsa (1984), quien comienza su artículo con la afirmación de que, "obviamente", la secuencia voraz debe tener un tamaño al menos proporcional a la raíz cuadrada. Lyall y Rice (2015) afirman que una construcción de Ruzsa (1984) genera conjuntos "mucho más grandes que el conjunto producido por el algoritmo voraz", pero no proporcionan límites ni citas que detallen el tamaño del conjunto voraz.
4. Eppstein, David (2018), "Evaluación más rápida de juegos de resta", en Ito, Hiro; Leonardi, Stefano; Pagli, Linda ; Prencipe, Giuseppe (eds.), Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Schloss Dagstuhl, págs. 20:1–20:12, arXiv : 1804.06515 , doi : 10.4230/LIPIcs.FUN.2018.20 , ISBN 9783959770675, Número de identificación del sujeto  4952124
5. Eisner, Tanja ; Farkas, Bálint; Haase, Markus; Nagel, Rainer (2015), "20.5 El teorema de Furstenberg–Sárközy", Operator Theoretic Aspects of Ergodic Theory , Textos de posgrado en matemáticas , vol. 272, Cham, Suiza: Springer, págs. 455–457, doi :10.1007/978-3-319-16898-2, ISBN 978-3-319-16897-5, Sr.  3410920.
6. Furstenberg, Harry (1977), "Comportamiento ergódico de medidas diagonales y un teorema de Szemerédi sobre progresiones aritméticas", Journal d'Analyse Mathématique , 31 : 204–256, doi :10.1007/BF02813304, MR  0498471, S2CID  120917478.
7. Sárkőzy, A. (1978), "Sobre conjuntos diferenciales de secuencias de números enteros. I" (PDF) , Acta Mathematica Academiae Scientiarum Hungaricae , 31 (1–2): 125–149, doi : 10.1007/BF01896079 , MR  0466059, S2CID  122018775.
8. Green, Ben (2002), "Sobre estructuras aritméticas en conjuntos densos de números enteros", Duke Mathematical Journal , 114 (2): 215–238, doi :10.1215/S0012-7094-02-11422-7, MR  1920188.
9. Lyall, Neil (2013), "Una nueva prueba del teorema de Sárközy", Actas de la American Mathematical Society , 141 (7): 2253–2264, arXiv : 1107.0243 , doi : 10.1090/S0002-9939-2013-11628-X , MR  3043007, S2CID  16842750.
10. Tao, Terry (28 de febrero de 2013), "Una prueba libre de Fourier del teorema de Furstenberg-Sarkozy", Novedades
11. Bloom, Thomas F.; Maynard, James (24 de febrero de 2021). "Un nuevo límite superior para conjuntos sin diferencias cuadradas". arXiv : 2011.13266 [math.NT].
12. Sárközy, A. (1978), "Sobre conjuntos diferenciales de secuencias de números enteros. II", Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae , 21 : 45–53 (1979), MR  0536201.
13. Ruzsa, IZ (1984), "Conjuntos de diferencias sin cuadrados", Periodica Mathematica Hungarica , 15 (3): 205–209, doi :10.1007/BF02454169, MR  0756185, S2CID  122624503.
14. Beigel, Richard; Gasarch, William (2008), Conjuntos de tamaño libres de diferencias cuadradas , arXiv : 0804.4892 , Bibcode :2008arXiv0804.4892B ${\displaystyle \Omega (n^{0.7334\dots })}$.
15. Lewko, Mark (2015), "Un límite inferior mejorado relacionado con el teorema de Furstenberg-Sárközy", Electronic Journal of Combinatorics , 22 (1), artículo P1.32, 6pp, doi : 10.37236/4656 , MR  3315474.
16. Sloane, N. J. A. (ed.), "Secuencia A000695 (secuencia de Moser-de Bruijn)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
17. Lyall, Neil; Rice, Alex (2015), Conjuntos de diferencias y polinomios , arXiv : 1504.04904 , Bibcode :2015arXiv150404904L.
18. Rice, Alex (2019), "Una extensión máxima de los límites más conocidos para el teorema de Furstenberg–Sárközy", Acta Arithmetica , 187 (1): 1–41, arXiv : 1612.01760 , doi :10.4064/aa170828-26-8, MR  3884220, S2CID  119139825