Sistema de cobertura

En matemáticas , un sistema de cobertura (también llamado sistema de residuos completo ) es una colección

${\displaystyle \{a_{1}{\pmod {n_{1}}},\ \ldots ,\ a_{k}{\pmod {n_{k}}}\}}$

de un número finito de clases de residuos

${\displaystyle a_{i}{\pmod {n_{i}}}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \},}$

cuya unión contiene cada número entero.

Ejemplos y definiciones

El concepto de sistema de cobertura fue introducido por Paul Erdős a principios de los años 1930.

Los siguientes son ejemplos de sistemas de cobertura:

1. ${\displaystyle \{0{\pmod {3}},\ 1{\pmod {3}},\ 2{\pmod {3}}\},}$
2. ${\displaystyle \{1{\pmod {2}},\ 2{\pmod {4}},\ 4{\pmod {8}},\ 0{\pmod {8}}\},}$
3. ${\displaystyle \{0{\pmod {2}},\ 0{\pmod {3}},\ 1{\pmod {4}},\ 5{\pmod {6}},\ 7{\pmod {12}}\}.}$

Un sistema de cobertura se llama disjunto (o exacto ) si no hay dos miembros que se superpongan.

Un sistema de cobertura se llama distinto (o incongruente ) si todos los módulos son diferentes (y mayores que 1). Hough y Nielsen (2019) ^[1] demostraron que cualquier sistema de cobertura distinto tiene un módulo divisible por 2 o 3. ${\displaystyle n_{i}}$

Un sistema de cobertura se llama irredundante (o mínimo ) si se requieren todas las clases de residuos para cubrir los números enteros.

Los dos primeros ejemplos son disjuntos.

El tercer ejemplo es distinto.

Un sistema (es decir, un conjunto múltiple desordenado)

${\displaystyle \{a_{1}{\pmod {n_{1}}},\ \ldots ,\ a_{k}{\pmod {n_{k}}}\}}$

de un número finito de clases de residuos se denomina cobertura si cubre cada número entero al menos veces, y cobertura exacta si cubre cada número entero exactamente veces. Se sabe que para cada uno hay portadas exactas que no pueden escribirse como una unión de dos portadas. Por ejemplo, ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m=2,3,\ldots }$ ${\displaystyle m}$

${\displaystyle \{1{\pmod {2}};\ 0{\pmod {3}};\ 2{\pmod {6}};\ 0,4,6,8{\pmod {10}};}$

${\displaystyle 1,2,4,7,10,13{\pmod {15}};\ 5,11,12,22,23,29{\pmod {30}}\}}$

es una 2-cubierta exacta que no es una unión de dos cubiertas.

El primer ejemplo anterior es una cobertura 1 exacta (también llamada cobertura exacta ). Otra cobertura exacta de uso común es la de números pares e impares , o

${\displaystyle \{0{\pmod {2}},\ 1{\pmod {2}}\}.}$

Este es sólo un caso del siguiente hecho: para cada módulo entero positivo , existe una cobertura exacta: ${\displaystyle m}$

${\displaystyle \{0{\pmod {m}},\ 1{\pmod {m}},\ \ldots ,\ {m-1}{\pmod {m}}\}.}$

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 y disjunto. Este resultado fue conjeturado en 1950 por Paul Erdős y demostrado poco después por Leon Mirsky y Donald J. Newman . Sin embargo, Mirsky y Newman nunca publicaron su prueba. Harold Davenport y Richard Rado también encontraron la misma prueba de forma independiente . ^[2]

Secuencias Primefree

Los sistemas de cobertura se pueden utilizar 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 son primos relativos 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

a ₁ = 20615674205555510, a ₂ = 3794765361567513 (secuencia A083216 en el OEIS ).

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 de 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, lo que muestra que cada número de la secuencia es divisible por al menos un primo.

Acotación del módulo más pequeño

Paul Erdős preguntó si para cualquier N arbitrariamente grande existe un sistema de cobertura incongruente cuyo mínimo de módulos sea al menos N. Es fácil construir ejemplos donde el mínimo de los módulos en dicho sistema sea 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ó ^[3] que es posible dar un ejemplo para N = 20, y Pace P Nielsen demuestra ^[4] la existencia de un ejemplo con N = 40, que consta de más que congruencias. ${\displaystyle 10^{50}}$

La pregunta de Erdős fue resuelta negativamente por Bob Hough. ^[5] Hough utilizó el lema local de Lovász para demostrar que existe un máximo N <10 ¹⁶ que puede ser el módulo mínimo en un sistema de cobertura.

Sistemas de módulos impares

Problema no resuelto en matemáticas :

¿Existe un sistema de cobertura con módulos distintos impares?

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

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 sean impares, no existe. Se sabe que si existe un sistema de este tipo con módulos libres de cuadrados, el módulo total debe tener al menos 22 factores primos. ^[6]

Ver también

• Teorema del resto chino
• Juego de revestimiento
• Sistema de numeración de residuos

Referencias

1. RD Hough, PP Nielsen (2019). "Sistemas de cobertura con divisibilidad restringida". Duque Matemáticas. J.​ 168 (17): 3261–3295. arXiv : 1703.02133 . doi :10.1215/00127094-2019-0058.
2. Soifer, Alejandro (2009). El libro de colorear matemático: las matemáticas de colorear y la colorida vida de sus creadores . Con prólogos 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.
3. Choi, SLG (1971). "Cubriendo el conjunto de números enteros por clases de congruencia de distintos módulos". Matemáticas. comp. 25 (116): 885–895. doi : 10.2307/2004353 . SEÑOR  0297692.
4. Nielsen, Pace P. (2009). "Un sistema de cobertura 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.
5. Hough, Bob (2015). "Solución del problema del módulo mínimo para sistemas de cobertura". Ana. de Matemáticas. 181 (1): 361–382. arXiv : 1307.0874 . doi :10.4007/annals.2015.181.1.6. SEÑOR  3272928.
6. Guo, canción; Sol, Zhi-Wei (2005). "Sobre sistemas de cobertura impares con módulos distintos". Adv. Aplica. 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 cobertura (una encuesta) ( PDF )
• Zhi-Wei Sun: Publicaciones clasificadas sobre sistemas de cobertura (PDF) Archivado el 29 de septiembre de 2007 en Wayback Machine.