En matemáticas , un sistema de cobertura (también llamado sistema de residuos completo ) es una colección
de un número finito de clases de residuos cuya unión contiene todos los enteros.
Ejemplos y definiciones
La noción de sistema de cobertura fue introducida por Paul Erdős a principios de la década de 1930.
Los siguientes son ejemplos de sistemas de cobertura:
y
y
Un sistema de cobertura se llama disjunto (o exacto ) si no se superponen dos miembros.
Un sistema de cobertura se llama distinto (o incongruente ) si todos los módulos son diferentes (y mayores que 1).
Un sistema de cobertura se denomina irredundante (o mínimo ) si se requieren todas las clases de residuos para cubrir los números enteros.
Los dos primeros ejemplos son inconexos.
El tercer ejemplo es distinto.
Un sistema (es decir, un conjunto múltiple desordenado)
de un número finito de clases de residuos se denomina -cubra si cubre todos los enteros al menos veces, y una exacta -cubrir si cubre cada entero exactamente veces. Se sabe que para cada hay exactos -cubiertas que no se pueden escribir como unión de dos portadas. Por ejemplo,
es una 2 tapas exacta que no es una unión de dos tapas.
El primer ejemplo anterior es una portada 1 exacta (también llamada portada exacta ). Otra cobertura exacta de uso común es el de los impares y los números pares o
Este es solo un caso del siguiente hecho: para cada módulo entero positivo , hay una portada exacta:
Teorema de Mirsky-Newman
El teorema de Mirsky-Newman, un caso especial de la conjetura de Herzog-Schönheim , establece que no existe un sistema de cobertura distinto disjunto. Este resultado fue conjeturado en 1950 por Paul Erdős y probado poco después por Leon Mirsky y Donald J. Newman . Sin embargo, Mirsky y Newman nunca publicaron su prueba. La misma prueba también fue encontrada de forma independiente por Harold Davenport y Richard Rado . [1]
Secuencias Primefree
Los sistemas de cobertura se pueden usar para encontrar secuencias sin primos , secuencias de números enteros que satisfacen la misma relación de recurrencia que los números de Fibonacci , de manera que los números consecutivos en la secuencia sean relativamente primos pero todos los números en la secuencia son números compuestos . Por ejemplo, una secuencia de este tipo encontrada por Herbert Wilf tiene términos iniciales
En esta secuencia, las posiciones en las que los números de la secuencia son divisibles por un primo p forman una progresión aritmética; por ejemplo, los números pares en la secuencia son los números a i donde i es congruente con 1 mod 3. Las progresiones divisibles por diferentes primos forman un sistema de cobertura, mostrando que cada número en la secuencia es divisible por al menos un primo.
Delimitación del módulo más pequeño
Paul Erdős preguntó si para cualquier arbitrariamente grande N existe un sistema incongruente que cubre el mínimo de cuyos módulos es al menos N . Es fácil construir ejemplos donde el mínimo de los módulos en tal sistema es 2, o 3 (Erdős dio un ejemplo donde los módulos están en el conjunto de los divisores de 120; una cobertura adecuada es 0 (3), 0 ( 4), 0 (5), 1 (6), 1 (8), 2 (10), 11 (12), 1 (15), 14 (20), 5 (24), 8 (30), 6 ( 40), 58 (60), 26 (120)) D. Swift dio un ejemplo donde el mínimo de los módulos es 4 (y los módulos están en el conjunto de los divisores de 2880). SLG Choi demostró [2] que es posible dar un ejemplo para N = 20, y Pace P Nielsen demuestra [3] la existencia de un ejemplo con N = 40, que consta de más de congruencias.
La pregunta de Erdős fue resuelta negativamente por Bob Hough. [4] Hough usó el lema local de Lovász para mostrar que hay un máximo N <10 16 que puede ser el módulo mínimo en un sistema de cobertura.
Sistemas de módulos impares
¿Existe un sistema de cobertura con módulos distintos e impares?
Hay una famosa conjetura sin resolver de Erdős y Selfridge : un sistema de cobertura incongruente (con el módulo mínimo mayor que 1) cuyos módulos son impares, no existe. Se sabe que si tal sistema existe con módulos libres de cuadrados, el módulo general debe tener al menos 22 factores primos. [5]
Ver también
Referencias
- ^ Soifer, Alexander (2009). The Mathematical Coloring Book: Matemáticas para colorear y la colorida vida de sus creadores . Con prólogo de Branko Grünbaum, Peter D. Johnson, Jr. y Cecil Rousseau. Nueva York: Springer. págs. 1–9. doi : 10.1007 / 978-0-387-74642-5 . ISBN 978-0-387-74640-1. Señor 2458293 .
- ^ Choi, SLG (1971). "Cubriendo el conjunto de enteros por clases de congruencia de distintos módulos" . Matemáticas. Comp. 25 (116): 885–895. doi : 10.2307 / 2004353 . Señor 0297692 .
- ^ Nielsen, Pace P. (2009). "Un sistema de recubrimiento cuyo módulo más pequeño es 40" . Revista de teoría de números . 129 (3): 640–666. doi : 10.1016 / j.jnt.2008.09.016 . Señor 2488595 .
- ^ Hough, Bob (2015). "Solución del problema de módulo mínimo para sistemas de recubrimiento". Ana. de Matemáticas. 181 (1): 361–382. arXiv : 1307.0874 . doi : 10.4007 / annals.2015.181.1.6 . Señor 3272928 .
- ^ Guo, Song; Sun, Zhi-Wei (2005). "Sobre sistemas de cobertura impares con módulos distintos". Adv. Apl. Matemáticas . 35 (2): 182–187. arXiv : matemáticas / 0412217 . doi : 10.1016 / j.aam.2005.01.004 . Señor 2152886 .
enlaces externos
- Zhi-Wei Sun : Problemas y resultados de los sistemas de revestimiento (una encuesta) ( PDF )
- Zhi-Wei Sun: Publicaciones clasificadas sobre sistemas de recubrimiento (PDF)