Conjunto de Salem-Spencer

Conjunto de números sin progresión

Para el conjunto {1, 2, 4, 5, 10, 11, 13, 14}, todos los puntos medios de dos elementos (los 28 puntos amarillos) quedan fuera del conjunto, por lo que no hay tres elementos que puedan formar una progresión aritmética.

En matemáticas, y en particular en combinatoria aritmética , un conjunto de Salem-Spencer es un conjunto de números de los cuales no hay tres que formen una progresión aritmética . Los conjuntos de Salem-Spencer también se denominan secuencias libres de 3 AP o conjuntos libres de progresión . También se les ha llamado conjuntos no promediados, ^{[1] [2]} pero este término también se ha utilizado para denotar un conjunto de números enteros, ninguno de los cuales puede obtenerse como el promedio de ningún subconjunto de los otros números. ^[3] Los conjuntos de Salem-Spencer llevan el nombre de Raphaël Salem y Donald C. Spencer , quienes demostraron en 1942 que los conjuntos de Salem-Spencer pueden tener un tamaño casi lineal. Sin embargo, un teorema posterior de Klaus Roth muestra que el tamaño es siempre menor que lineal.

Ejemplos

Para los valores más pequeños de tales que los números de tener un conjunto de elementos Salem-Spencer son ${\displaystyle k=1,2,\dots }$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle k}$

1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, ... (secuencia A065825 en el OEIS )

Por ejemplo, entre los números del 1 al 14, los ocho números

{1, 2, 4, 5, 10, 11, 13, 14}

forman el conjunto único más grande de Salem-Spencer. ^[4]

Este ejemplo se desplaza sumando uno a los elementos de un conjunto infinito de Salem-Spencer, la secuencia de Stanley

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (secuencia A005836 en el OEIS )

de números que, cuando se escriben como un número ternario , usan solo los dígitos 0 y 1. Esta secuencia es el primer conjunto lexicográficamente infinito de Salem-Spencer. ^[5] Otro conjunto infinito de Salem-Spencer está dado por los cubos.

0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ... (secuencia A000578 en el OEIS )

Es un teorema de Leonhard Euler que no hay tres cubos en progresión aritmética. ^[6]

Tamaño

En 1942, Salem y Spencer publicaron una prueba de que los números enteros en el rango de tienen grandes conjuntos de Salem-Spencer, de tamaño . ^[7] El denominador de esta expresión utiliza notación O grande y crece más lentamente que cualquier potencia de , por lo que los conjuntos encontrados por Salem y Spencer tienen un tamaño casi lineal. Este límite refutó una conjetura de Paul Erdős y Pál Turán de que el tamaño de tal conjunto podría ser como máximo para algunos . ^{[4] [8]} La construcción de Salem y Spencer fue mejorada por Felix Behrend en 1946, quien encontró conjuntos de tamaño . ^[9] ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n/e^{O(\log n/\log \log n)}}$ ${\displaystyle n}$ ${\displaystyle n^{1-\delta }}$ ${\displaystyle \delta >0}$ ${\displaystyle n/e^{O({\sqrt {\log n}})}}$

En 1952, Klaus Roth demostró el teorema de Roth estableciendo que el tamaño de un conjunto de Salem-Spencer debe ser . ^[10] Por lo tanto, aunque los conjuntos construidos por Salem, Spencer y Behrend tienen tamaños casi lineales, no es posible mejorarlos y encontrar conjuntos cuyo tamaño sea realmente lineal. Este resultado se convirtió en un caso especial del teorema de Szemerédi sobre la densidad de conjuntos de números enteros que evitan progresiones aritméticas más largas. ^[4] Para distinguir el límite de Roth en los conjuntos de Salem-Spencer del teorema de Roth sobre la aproximación diofántica de números algebraicos , este resultado se ha denominado teorema de Roth sobre progresiones aritméticas . ^[11] Después de varias mejoras adicionales al teorema de Roth, ^{[12] [13] [14] [15]} se ha demostrado que el tamaño de un conjunto de Salem-Spencer es . ^[16] En 2020 se anunció en una preimpresión un límite aún mejor de (para algunos que no se ha calculado explícitamente ). ^[17] En 2023, el informático Kelley an Meka encontró un nuevo límite de ^{[18] [19] [20]} y, poco después , Bloom y Sisask ^{[21] [22]} dieron una exposición en términos matemáticos más familiares. Desde entonces también mejoró el exponente de Kelly-Meka vinculado (y conjeturado ) en una preimpresión. ^[23] ${\displaystyle O(n/\log \log n)}$ ${\displaystyle O{\bigl (}n(\log \log n)^{4}/\log n{\bigr )}}$ ${\displaystyle O{\bigl (}n/(\log n)^{1+\delta }{\bigr )}}$ ${\displaystyle \delta >0}$ ${\displaystyle \exp(-c(\log N)^{1/12})N}$ ${\displaystyle \beta =1/9}$ ${\displaystyle \beta =5/41}$

Construcción

Una construcción sencilla para un conjunto de Salem-Spencer (de tamaño considerablemente menor que el límite de Behrend) es elegir números ternarios que utilicen sólo los dígitos 0 y 1, no 2. Un conjunto de este tipo debe estar libre de progresión, porque si dos de sus elementos y son el primer y segundo miembro de una progresión aritmética, el tercer miembro debe tener el dígito dos en la posición del dígito menos significativo donde y difieren. ^[4] La ilustración muestra un conjunto de esta forma, para los números ternarios de tres dígitos (desplazados en uno para hacer que el elemento más pequeño sea 1 en lugar de 0). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

La construcción de Behrend utiliza una idea similar, para una base impar más grande . Su conjunto consta de números cuyos dígitos están restringidos al rango de hasta (de modo que la suma de estos números no tiene acarreos), con la restricción adicional de que la suma de los cuadrados de los dígitos es algún valor elegido . ^[9] Si los dígitos de cada número se consideran coordenadas de un vector, esta restricción describe una esfera en el espacio vectorial resultante y, por convexidad, el promedio de dos valores distintos en esta esfera será interior a la esfera en lugar de estar en ella. él. ^[24] Por lo tanto, si dos elementos del conjunto de Behrend son los puntos finales de una progresión aritmética, el valor medio de la progresión (su promedio) no estará en el conjunto. Por tanto, el conjunto resultante no tiene progresión. ^[9] ${\displaystyle 2d-1}$ ${\displaystyle 0}$ ${\displaystyle d-1}$ ${\displaystyle k}$

Con una cuidadosa elección de , y una elección de como la suma de cuadrados de dígitos que ocurre con más frecuencia, Behrend logra su objetivo. ^[9] En 1953, Leo Moser demostró que existe una única secuencia infinita de Salem-Spencer que logra la misma densidad asintótica en cada prefijo que la construcción de Behrend. ^[1] Al considerar el casco convexo de puntos dentro de una esfera, en lugar del conjunto de puntos en una esfera, es posible mejorar la construcción en un factor de . ^{[24] [25]} Sin embargo, esto no afecta el tamaño encuadernado en la forma indicada anteriormente. ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle {\sqrt {\log n}}}$

Generalización

La noción de conjuntos de Salem-Spencer (conjunto libre de 3 AP) se puede generalizar a conjuntos libres de AP, en los que los elementos forman una progresión aritmética si y sólo si todos son iguales. Rankin (1961) proporcionó construcciones de grandes conjuntos libres de -AP. ^[26] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Resultados computacionales

Gasarch, Glenn y Kruskal han realizado una comparación de diferentes métodos computacionales para grandes subconjuntos sin progresión aritmética. ^[2] Usando estos métodos encontraron el tamaño exacto del conjunto más grande de este tipo para . Sus resultados incluyen varios límites nuevos para diferentes valores de , encontrados mediante algoritmos de rama y límite que utilizan programación lineal y heurísticas específicas del problema para limitar el tamaño que se puede lograr en cualquier rama del árbol de búsqueda. Una heurística que encontraron particularmente efectiva fue el método de los tercios , en el que dos copias desplazadas de un conjunto de Salem-Spencer para se colocan en el primer y último tercio de un conjunto para . ^[2] ${\displaystyle \{1,\dots n\}}$ ${\displaystyle n\leq 187}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 3n}$

Aplicaciones

Cinco reinas en la diagonal principal de un tablero de ajedrez, atacando todas las demás casillas. Los cuadrados vacíos en la diagonal están en las filas 1, 3 y 7, un conjunto de Salem-Spencer totalmente impar.

En relación con el problema de Ruzsa-Szemerédi , se han utilizado conjuntos de Salem-Spencer para construir gráficos densos en los que cada arista pertenece a un triángulo único . ^[27]

Los conjuntos de Salem-Spencer también se han utilizado en informática teórica. Se han utilizado en el diseño del algoritmo Coppersmith-Winograd para la multiplicación rápida de matrices , ^[28] y en la construcción de pruebas eficientes de conocimiento cero no interactivas . ^[29] Recientemente, se han utilizado para mostrar límites inferiores de tamaño para llaves de gráficos , ^[30] y la fuerte hipótesis del tiempo exponencial basada en la dureza del problema de suma de subconjuntos . ^[31]

Estos conjuntos también se pueden aplicar en matemáticas recreativas a un problema matemático de ajedrez de colocar la menor cantidad posible de reinas en la diagonal principal de un tablero de ajedrez para que todas las casillas del tablero sean atacadas. El conjunto de cuadrados diagonales que quedan desocupados debe formar un conjunto de Salem-Spencer, en el que todos los valores tienen la misma paridad (todos pares o impares). El conjunto de reinas más pequeño posible es el complemento del subconjunto más grande de Salem-Spencer de números impares en . Este subconjunto de Salem-Spencer se puede encontrar duplicando y restando uno de los valores en un subconjunto de Salem-Spencer de todos los números en ^[32] ${\displaystyle n\times n}$ ${\displaystyle \{1,\dots n\}}$ ${\displaystyle \{1,\dots n/2\}.}$

Referencias

1. Moser, Leo (1953), "Sobre conjuntos de números enteros que no promedian", Canadian Journal of Mathematics , 5 : 245–252, doi : 10.4153/cjm-1953-027-0 , MR  0053140, S2CID  124488483
2. Gasarch, William ; Glenn, James; Kruskal, Clyde P. (2008), "Encontrar conjuntos grandes de 3 libres. I. El caso de n pequeña" (PDF) , Journal of Computer and System Sciences , 74 (4): 628–655, doi :10.1016/j. jcss.2007.06.002, señor  2417032
3. Abbott, HL (1976), "Sobre una conjetura de Erdős y Straus sobre conjuntos de números enteros que no promedian", Actas de la Quinta Conferencia Combinatoria Británica (Univ. Aberdeen, Aberdeen, 1975) , Congressus Numerantium, vol. XV, Winnipeg, Manitoba: Utilitas Math., págs. 1 a 4, MR  0406967
4. Dybizbański, Janusz (2012), "Secuencias que no contienen progresiones aritméticas de 3 términos", Electronic Journal of Combinatorics , 19 (2): P15:1–P15:5, doi : 10.37236/2061 , MR  2928630
5. Sloane, N. J. A. (ed.), "Sequence A005836", La enciclopedia en línea de secuencias enteras , Fundación OEIS
6. Erdős, P .; Lev, V.; Rauzy, G.; Sandor, C.; Sárközy, A. (1999), "Algoritmo codicioso, progresiones aritméticas, sumas de subconjuntos y divisibilidad", Matemáticas discretas , 200 (1–3): 119–135, doi :10.1016/S0012-365X(98)00385-9, SEÑOR  1692285
7. Salem, R .; Spencer, DC (diciembre de 1942), "Sobre conjuntos de números enteros que no contienen tres términos en progresión aritmética", Actas de la Academia Nacional de Ciencias , 28 (12): 561–563, Bibcode :1942PNAS...28..561S , doi : 10.1073/pnas.28.12.561 , PMC 1078539 , PMID  16588588 
8. Erdős, Paul ; Turán, Paul (1936), "Sobre algunas secuencias de números enteros" (PDF) , Journal of the London Mathematical Society , 11 (4): 261–264, doi :10.1112/jlms/s1-11.4.261, MR  1574918
9. Behrend, FA (diciembre de 1946), "Sobre conjuntos de números enteros que no contienen tres términos en progresión aritmética", Actas de la Academia Nacional de Ciencias , 32 (12): 331–332, Bibcode :1946PNAS...32. .331B, doi : 10.1073/pnas.32.12.331 , PMC 1078964 , PMID  16578230 
10. Roth, Klaus (1952), "Sur quelques ensembles d'entiers", Comptes rendus de l'Académie des Sciences , 234 : 388–390, SEÑOR  0046374
11. Florecer, Thomas; Sisask, Olaf (2019), "Límites logarítmicos para el teorema de Roth mediante casi periodicidad", Análisis discreto , 2019 (4), arXiv : 1810.12791v2 , doi :10.19086/da.7884, S2CID  119583263
12. Heath-Brown, DR (1987), "Conjuntos de números enteros que no contienen progresiones aritméticas", Revista de la Sociedad Matemática de Londres , Segunda Serie, 35 (3): 385–394, doi :10.1112/jlms/s2-35.3.385, Señor  0889362
13. Szemerédi, E. (1990), "Conjuntos de números enteros que no contienen progresiones aritméticas", Acta Mathematica Hungarica , 56 (1–2): 155–158, doi :10.1007/BF01903717, MR  1100788
14. Bourgain, J. (1999), "Sobre ternas en progresión aritmética", Análisis geométrico y funcional , 9 (5): 968–984, doi :10.1007/s000390050105, MR  1726234, S2CID  392820
15. Sanders, Tom (2011), "Sobre el teorema de Roth sobre progresiones", Annals of Mathematics , segunda serie, 174 (1): 619–636, arXiv : 1011.0104 , doi :10.4007/annals.2011.174.1.20, MR  2811612, S2CID  53331882
16. Bloom, TF (2016), "Una mejora cuantitativa del teorema de Roth sobre progresiones aritméticas", Revista de la Sociedad Matemática de Londres , Segunda Serie, 93 (3): 643–663, arXiv : 1405.5800 , doi :10.1112/jlms/jdw010 , SEÑOR  3509957, S2CID  27536138
17. Florecer, Thomas; Sisask, Olaf (2020), Rompiendo la barrera logarítmica en el teorema de Roth sobre progresiones aritméticas , arXiv : 2007.03528; véase también Kalai, Gil (8 de julio de 2020), "Para animarte en tiempos difíciles 7: ¡Bloom y Sisask acaban de romper la barrera de los logaritmos para el teorema de Roth!", Combinatoria y más
18. Kelley, Zander; Meka, Raghu (6 de noviembre de 2023). "Límites fuertes para 3 progresiones". 2023 64º Simposio anual del IEEE sobre fundamentos de la informática (FOCS): actas de la conferencia . IEEE: 933–973. arXiv : 2302.05537 . doi :10.1109/FOCS57990.2023.00059. ISBN 979-8-3503-1894-4.
19. Kelley, Zander; Meka, Raghu (10 de febrero de 2023). "Límites fuertes para 3 progresiones". arXiv : 2302.05537 [matemáticas.NT].
20. Sloman, Leila (21 de marzo de 2023). "Prueba sorpresa en informática aturde a los matemáticos". Revista Quanta .
21. Floración, Thomas F.; Sisask, Olof (31 de diciembre de 2023). "Los límites Kelley-Meka para conjuntos libres de progresiones aritméticas de tres términos". Teoría de números esencial . 2 (1): 15–44. arXiv : 2302.07211 . doi :10.2140/ent.2023.2.15. ISSN  2834-4634.
22. Floración, Thomas F.; Sisask, Olof (14 de febrero de 2023). "El Kelley--Meka limita a conjuntos libres de progresiones aritméticas de tres términos". arXiv : 2302.07211 [matemáticas.NT].
23. Floración, Thomas F.; Sisask, Olof (5 de septiembre de 2023). "Una mejora de los límites de Kelley-Meka en progresiones aritméticas de tres términos". arXiv : 2309.02353 [matemáticas.NT].
24. Elkin, Michael (2011), "Una construcción mejorada de conjuntos sin progresión", Israel Journal of Mathematics , 184 : 93–128, arXiv : 0801.4310 , doi : 10.1007/s11856-011-0061-1 , MR  2823971
25. Verde, Ben ; Wolf, Julia (2010), "Una nota sobre la mejora de Elkin en la construcción de Behrend", en Chudnovsky, David ; Chudnovsky, Gregory (eds.), Teoría de números aditivos: Festschrift en honor al sexagésimo cumpleaños de Melvyn B. Nathanson , Nueva York: Springer, págs. 141-144, arXiv : 0810.0732 , doi : 10.1007/978-0-387- 68361-4_9, SEÑOR  2744752, S2CID  10475217
26. Rankin, RA (1961), "XXIV: Conjuntos de números enteros que contienen no más de un número determinado de términos en progresión aritmética", Actas de la Royal Society of Edinburgh, Sección A: Ciencias físicas y matemáticas , 65 (4): 332 –344, doi :10.1017/S0080454100017726, S2CID  122037820
27. Ruzsa, IZ ; Szemerédi, E. (1978), "Sistemas triples sin seis puntos que lleven tres triángulos", Combinatoria (Proc. Quinto coloquio húngaro, Keszthely, 1976), vol. II , coloq. Matemáticas. Soc. János Bolyai, vol. 18, Amsterdam y Nueva York: Holanda Septentrional, págs. 939–945, MR  0519318
28. Calderero, Don ; Winograd, Shmuel (1990), "Multiplicación de matrices mediante progresiones aritméticas", Journal of Symbolic Computation , 9 (3): 251–280, doi : 10.1016/S0747-7171(08)80013-2 , MR  1056627
29. Lipmaa, Helger (2012), "Conjuntos libres de progresión y argumentos de conocimiento cero no interactivos basados ​​en emparejamientos sublineales", en Cramer, Ronald (ed.), Teoría de la criptografía: novena conferencia sobre teoría de la criptografía, TCC 2012, Taormina , Sicilia, Italia, 19 al 21 de marzo de 2012, Actas , Lecture Notes in Computer Science, vol. 7194, Springer, págs. 169–189, doi : 10.1007/978-3-642-28914-9_10
30. Abboud, Amir; Bodwin, Greg (2017), "El exponente de llave aditiva 4/3 es ajustado", Journal of the ACM , 64 (4): A28:1–A28:20, arXiv : 1511.00700 , doi :10.1145/3088511, MR  3702458, S2CID  209870748
31. Abboud, Amir; Bringmann, Karl ; Hermelín, Danny; Shabtay, Dvir (2019), "Límites inferiores basados ​​en SETH para suma de subconjuntos y ruta de bicriterios", en Chan, Timothy M. (ed.), Actas del trigésimo simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2019, San Diego , California, EE. UU., 6 al 9 de enero de 2019 , Sociedad de Matemáticas Industriales y Aplicadas, págs. 41–57, arXiv : 1704.04546 , doi :10.1137/1.9781611975482.3, S2CID  15802062
32. Cockayne, EJ; Hedetniemi, ST (1986), "Sobre el problema de dominación de las reinas diagonales", Journal of Combinatorial Theory , Serie A, 42 (1): 137–139, doi :10.1016/0097-3165(86)90012-9, MR  0843468

Enlaces externos

• Búsqueda de conjuntos no promediados, Jarek Wroblewski, Universidad de Wrocław