Sistema de cobertura

En matemáticas , un sistema de recubrimiento (también llamado sistema de residuos completos ) 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 todos los números enteros.

El concepto de sistema de cobertura fue introducido por Paul Erdős a principios de la década de 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 denomina disjunto (o exacto ) si ningún par de sus miembros se superpone.

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

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 disjuntos.

El tercer ejemplo es distinto.

Un sistema (es decir, un multiconjunto no ordenado)

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

de un número finito de clases de residuos se llama${\displaystyle m}$-cubrir si cubre al menos todos los enteros ${\displaystyle m}$horas y una exacta${\displaystyle m}$-cubre si cubre exactamente cada número entero${\displaystyle m}$veces. Se sabe que para cada ${\displaystyle m=2,3,\ldots }$hay exactos${\displaystyle m}$-cubiertas que no pueden escribirse como la unión de dos cubiertas. Por ejemplo,

${\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 cobertura exacta de 2 que no es una unión de dos coberturas.

El primer ejemplo anterior es una cobertura exacta de 1 (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 solo un caso del siguiente hecho: Para cada módulo entero positivo${\displaystyle m}$, hay una portada exacta:

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

El teorema de Mirsky-Newman, un caso especial de la conjetura de Herzog-Schönheim , afirma que no existe un sistema de recubrimiento 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 demostración. La misma demostración también fue hallada independientemente por Harold Davenport y Richard Rado . ^{[ 2 ]} En 1970, el Problema 8 de la olimpiada matemática soviética para décimo grado era esencialmente un problema de coloración de polígonos equivalente al teorema de Mirsky-Newman. ^{[ 3 ]}

Los sistemas de recubrimiento se pueden utilizar para encontrar secuencias libres de primos , secuencias de enteros que satisfacen la misma relación de recurrencia que los números de Fibonacci , de modo que los números consecutivos en la secuencia son primos entre sí , pero todos los números en la secuencia son 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 son divisibles por un primo p forman una progresión aritmética; por ejemplo, los números pares son aᵢ, donde _i es congruente con 1 módulo 3. Las progresiones divisibles por diferentes primos forman un sistema de recubrimiento, lo que demuestra que cada número de la secuencia es divisible por al menos un primo.

Paul Erdős preguntó si para cualquier N arbitrariamente grande existe un sistema de recubrimiento incongruente cuyo mínimo de 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; un recubrimiento adecuado 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ó ^{[ 7 ]} que es posible dar un ejemplo para N = 20, y Pace P Nielsen demuestra ^{[ 8 ]} la existencia de un ejemplo con N = 40, que consiste en más de${\displaystyle 10^{50}}$congruencias. Tyler Owens ^{[ 9 ]} demuestra la existencia de un ejemplo con N = 42 .

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

Existe una famosa conjetura sin resolver de Erdős y Selfridge : no existe un sistema de recubrimiento incongruente (con módulo mínimo mayor que 1) cuyos módulos sean impares. Se sabe que si existiera tal sistema con módulos libres de cuadrados, el módulo total debe tener al menos 22 factores primos. ^{[ 11 ]}

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

• Zhi-Wei Sun : Problemas y resultados sobre sistemas de cobertura (una revisión) ( PDF )
• Zhi-Wei Sun: Publicaciones clasificadas sobre sistemas de recubrimiento (PDF) Archivado el 29/09/2007 en Wayback Machine