Problemas que implican progresiones aritméticas

Los problemas que involucran progresiones aritméticas son de interés en la teoría de números , ^{[ 1 ]} la combinatoria y la informática , tanto desde puntos de vista teóricos como aplicados.

Halla la cardinalidad (denotada por A _k ( m )) del subconjunto más grande de {1,  2,  ..., m } que no contiene ninguna progresión de k términos distintos. No es necesario que los elementos de las progresiones prohibidas sean consecutivos. Por ejemplo, A ₄ (10) = 8, porque {1, 2, 3, 5, 6, 8, 9, 10} no tiene ninguna progresión aritmética de longitud 4, mientras que todos los subconjuntos de 9 elementos de {1, 2, ..., 10} sí la tienen.              

En 1936, Paul Erdős y Pál Turán plantearon una pregunta relacionada con este número ^{[ 2 ]} y Erdős ofreció un premio de 1000 dólares por la respuesta. El premio fue cobrado por Endre Szemerédi por una solución publicada en 1975, que se conoce como el teorema de Szemerédi .

El teorema de Szemerédi afirma que un conjunto de números naturales con densidad asintótica superior distinta de cero contiene progresiones aritméticas finitas, de cualquier longitud arbitraria k .

Erdős formuló una conjetura más general de la que se seguiría que

La secuencia de números primos contiene progresiones aritméticas de cualquier longitud.

Este resultado fue demostrado por Ben Green y Terence Tao en 2004 y ahora se conoce como el teorema de Green-Tao . ^{[ 3 ]}

Véase también el teorema de Dirichlet sobre progresiones aritméticas .

A partir de 2020, la progresión aritmética de primos más larga conocida tiene una longitud de 27: ^{[ 4 ]}

224584605939537911 + 81292139·23#· n , para n = 0 a 26. ( 23# = 223092870 )

Hasta 2011, la progresión aritmética más larga conocida de primos consecutivos tiene una longitud de 10. Fue descubierta en 1998. ^{[ 5 ] [ 6 ]} La progresión comienza con un número de 93 dígitos.

100 99697 24697 14247 63778 66555 87969 84032 95093 24689

19004 18036 03417 75890 43417 03348 88215 90672 29719

y tiene una diferencia común de 210.

El teorema de los números primos para progresiones aritméticas trata sobre la distribución asintótica de los números primos en una progresión aritmética.

• Encontrar el mínimo l _n tal que cualquier conjunto de n residuos módulo p pueda ser cubierto por una progresión aritmética de longitud l _n . ^{[ 7 ]}
• Para un conjunto S de enteros dado, encuentre el número mínimo de progresiones aritméticas que cubren S.
• Para un conjunto S de enteros dado, encuentre el número mínimo de progresiones aritméticas no superpuestas que cubren S.
• Encuentra el número de maneras de particionar {1,  ..., n } en progresiones aritméticas. ^{[ 8 ]} 
• Encuentra el número de maneras de particionar {1,  ..., n } en progresiones aritméticas de longitud al menos 2 con el mismo período. ^{[ 9 ]} 
• Véase también Sistema de recubrimiento

• Combinatoria aritmética
• PrimeGrid