Conjunto 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) se encuentran 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 ninguno de los tres forma 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 han llamado conjuntos sin promediado, ^{[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 reciben su 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 a tienen un conjunto de Salem-Spencer de elementos 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 la 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 Salem-Spencer más grande y único. ^[4]

Este ejemplo se desplaza añadiendo 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 la OEIS )

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

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

Es un teorema de Leonhard Euler que no existen 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 a tienen grandes conjuntos de Salem-Spencer, de tamaño . ^[7] El denominador de esta expresión usa la 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 que es casi lineal. Este límite refutó una conjetura de Paul Erdős y Pál Turán de que el tamaño de dicho conjunto podría ser como máximo para algún . ^{[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 que son 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 llamado 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ó un límite aún mejor de (para algunos que no se ha calculado explícitamente ) en una preimpresión. ^[17] En 2023, el científico informático Kelley y Meka encontraron un nuevo límite de ^{[18] [19] [20] y, poco después,} Bloom y Sisask dieron una exposición en términos matemáticos más familiares ^{[21] [22],} quienes desde entonces también han mejorado el exponente del límite de Kelly-Meka a (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 los números ternarios que utilizan solo los dígitos 0 y 1, no 2. Un conjunto de este tipo debe ser 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 un radio impar mayor . Su conjunto consiste en los números cuyos dígitos están restringidos al rango de a (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 un valor elegido . ^[9] Si los dígitos de cada número se consideran como 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 sobre ella. ^[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 lo tanto, el conjunto resultante está libre de progresión. ^[9] ${\displaystyle 2d-1}$ ${\displaystyle 0}$ ${\displaystyle d-1}$ ${\displaystyle k}$

Con una elección cuidadosa de , y una elección de como la suma de cuadrados de dígitos que ocurre con mayor frecuencia, Behrend logra su límite. ^[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 la envoltura convexa de puntos dentro de una esfera, en lugar del conjunto de puntos en una esfera, es posible mejorar la construcción por un factor de . ^{[24] [25]} Sin embargo, esto no afecta el límite de tamaño en la forma establecida anteriormente. ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle {\sqrt {\log n}}}$

Generalización

La noción de conjuntos de Salem-Spencer (conjuntos 3-AP-libres) se puede generalizar a conjuntos -AP-libres, en los que los elementos forman una progresión aritmética si y sólo si son todos iguales. Rankin (1961) dio construcciones de grandes conjuntos -AP-libres. ^[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 de sin progresión aritmética. ^[2] Utilizando 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 ramificación y acotación 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 a todas las demás casillas. Las casillas vacías en la diagonal están en las filas 1, 3 y 7, un conjunto de Salem-Spencer de todos los números impares.

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 la 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 grafos extensores [ ^30] y la dificultad basada en la hipótesis del tiempo exponencial fuerte 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 que consiste en colocar la menor cantidad posible de reinas en la diagonal principal de un tablero de ajedrez de modo que se ataquen todas las casillas del tablero. El conjunto de casillas diagonales que permanecen desocupadas debe formar un conjunto de Salem-Spencer, en el que todos los valores tienen la misma paridad (todos impares o todos pares). El conjunto de reinas más pequeño posible es el complemento del subconjunto de Salem-Spencer más grande de los 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 no promediados", 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 3-libres grandes. I. El caso de n pequeño" (PDF) , Journal of Computer and System Sciences , 74 (4): 628–655, doi :10.1016/j.jcss.2007.06.002, MR  2417032
3. Abbott, HL (1976), "Sobre una conjetura de Erdős y Straus sobre conjuntos de números enteros que no se promedian", Actas de la Quinta Conferencia Combinatoria Británica (Universidad de Aberdeen, Aberdeen, 1975) , Congressus Numerantium, vol. XV, Winnipeg, Manitoba: Utilitas Math., págs. 1–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.), "Secuencia A005836", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
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 sucesiones 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. Bloom, Thomas; Sisask, Olaf (2019), "Límites logarítmicos para el teorema de Roth a través de la casi periodicidad", Discrete Analysis , 2019 (4), arXiv : 1810.12791v2 , doi :10.19086/da.7884, S2CID  119583263
12. Heath-Brown, DR (1987), "Conjuntos enteros que no contienen progresiones aritméticas", Journal of the London Mathematical Society , Segunda serie, 35 (3): 385–394, doi :10.1112/jlms/s2-35.3.385, MR  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 los triples en la 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", Anales de Matemáticas , 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", Journal of the London Mathematical Society , Segunda serie, 93 (3): 643–663, arXiv : 1405.5800 , doi :10.1112/jlms/jdw010, MR  3509957, S2CID  27536138
17. Bloom, Thomas; Sisask, Olaf (2020), Rompiendo la barrera logarítmica en el teorema de Roth sobre progresiones aritméticas , arXiv : 2007.03528; ver también Kalai, Gil (8 de julio de 2020), "Para animarte en tiempos difíciles 7: ¡Bloom y Sisask acaban de romper la barrera del logaritmo 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". Actas de la conferencia del 64.º Simposio anual sobre fundamentos de la informática (FOCS) de la IEEE de 2023. 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 progresiones de 3 dimensiones". arXiv : 2302.05537 [math.NT].
20. Sloman, Leila (21 de marzo de 2023). "Una prueba informática sorprendente sorprende a los matemáticos". Revista Quanta .
21. Bloom, Thomas F.; Sisask, Olof (31 de diciembre de 2023). "Los límites de Kelley-Meka para conjuntos libres de progresiones aritméticas de tres términos". Essential Number Theory . 2 (1): 15–44. arXiv : 2302.07211 . doi :10.2140/ent.2023.2.15. ISSN  2834-4634.
22. Bloom, Thomas F.; Sisask, Olof (14 de febrero de 2023). "Los límites de Kelley-Meka para conjuntos libres de progresiones aritméticas de tres términos". arXiv : 2302.07211 [math.NT].
23. Bloom, 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 [math.NT].
24. Elkin, Michael (2011), "Una construcción mejorada de conjuntos libres de progresión", Israel Journal of Mathematics , 184 : 93–128, arXiv : 0801.4310 , doi : 10.1007/s11856-011-0061-1 , MR  2823971
25. Green, Ben ; Wolf, Julia (2010), "Una nota sobre la mejora de Elkin de la construcción de Behrend", en Chudnovsky, David ; Chudnovsky, Gregory (eds.), Teoría de números aditivos: Festschrift en honor del sexagésimo cumpleaños de Melvyn B. Nathanson , Nueva York: Springer, pp. 141–144, arXiv : 0810.0732 , doi :10.1007/978-0-387-68361-4_9, MR  2744752, S2CID  10475217
26. Rankin, RA (1961), "XXIV: Conjuntos de números enteros que no contienen más de un número dado de términos en progresión aritmética", Actas de la Royal Society of Edinburgh, Sección A: Ciencias matemáticas y físicas , 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. Coppersmith, 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 emparejamiento sublineal", en Cramer, Ronald (ed.), Teoría de la criptografía: 9.ª conferencia sobre teoría de la criptografía, TCC 2012, Taormina, Sicilia, Italia, 19-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 ; Hermelin, Danny; Shabtay, Dvir (2019), "Límites inferiores basados ​​en SETH para la suma de subconjuntos y la ruta de bicriterio", en Chan, Timothy M. (ed.), Actas del trigésimo simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2019, San Diego, California, EE. UU., 6-9 de enero de 2019 , Society for Industrial and Applied Mathematics, 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 la dominación de las damas 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