Cobertura (matemáticas)

En matemáticas, unha cobertura (tamén chamado sistema completo de residuos) é unha colección: ${a_{1}{\pmod {n_{1}}},\ldots ,\ a_{k}{\pmod {n_{k}}}}$

de moitas clases de residuos finitas

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

cuxa unión contén a todos os enteiros.

Exemplos e definicións

A noción de cobertura foi introducida por Paul Erdős a principios da década de 1930.

Os seguintes son exemplos de cobertura:

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

Unha cobertura denomínase disxunta (ou exacta) se non hai dous membros que se solapen.

Unha cobertura chámase distinta (ou incongruente) se todos os módulos $n_{i}$ son diferentes (e maiores que 1). Hough e Nielsen (2019)^[1] demostraron que calquera cobertura distinta ten un módulo que é divisible por 2 ou 3.

Unha cobertura chámase non redundante (ou mínima) se todas as clases de residuos son necesarias para cubrir os números enteiros.

Os dous primeiros exemplos son disxuntas.

O terceiro exemplo é distinta.

Un sistema (é dicir, un conxunto múltiple non ordenado)

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

dun número finito de clases de residuos chámase unha $m$ -cobertura se cobre cada número enteiro polo menos $m$ veces, e unha $m$ -cobertura exacta se cobre cada enteiro exactamente $m$ veces. Sábese que para cada $m=2,3,\ldots$ hai $m$ -cobertura exactas que non poden escribirse como unión de dúas coberturas. Por exemplo,

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

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

é unha 2-cobertura exacta que non é a unión de dúas coberturas.

O primeiro exemplo anterior é unha 1-cobertura exacta. Outra cobertura exacta de uso común é a dos números pares e impares, ou

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

Isto é só un caso do seguinte feito: para cada módulo enteiro positivo $m$ , hai unha cobertura exacta:

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

Teorema de Mirsky-Newman

O teorema de Mirsky-Newman, un caso especial da conxectura de Herzog-Schönheim, afirma que non existen coberturas disxuntas distintas. Este resultado foi conxecturado en 1950 por Paul Erdős e demostrado pouco despois por Leon Mirsky e Donald J. Newman. Con todo, Mirsky e Newman nunca publicaron a súa demostración. A mesma proba tamén foi atopada independentemente por Harold Davenport e Richard Rado ^[2]

Secuencias Libres de Primos

As coberturas pódense usar para atopar secuencias libres de primos, secuencias de enteiros que satisfagan a mesma relación de recorrencia que os números de Fibonacci, de xeito que os números consecutivos da secuencia son coprimos, mais todos os números da secuencia son números compostos. Por exemplo, unha secuencia deste tipo atopada por Herbert Wilf ten termos iniciais

a₁ = 206156742055555510, a₂ = 3794765361567513 (secuencia A083216 na OEIS).

Nesta secuencia, as posicións nas que os números da secuencia son divisibles por un p primo forman unha progresión aritmética; por exemplo, os números pares da secuencia son os números a_i onde i é congruente con 1 módulo 3. As progresións divisibles por diferentes números primos forman unha cobertura, que mostra que cada número da secuencia é divisible polo menos por un primo.

Límite do módulo máis pequeno

Paul Erdős preguntou se para calquera N arbitrariamente grande existe unha cobertura incongruente cuxo mínimo módulo sexa polo menos N. É doado construír exemplos onde o mínimo dos módulos nun sistema deste tipo é 2 ou 3 (Erdős deu un exemplo onde os módulos están no conxunto dos divisores de 120; unha cobertura adecuada é ( 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 deu un exemplo onde o mínimo dos módulos é 4 (e os módulos están no conxunto dos divisores de 2880). S. L. G. Choi demostrou^[3] que é posible dar un exemplo para N = 20, e Pace P Nielsen demostra^[4] a existencia dun exemplo con N = 40, que consta de máis de $10^{50}$ congruencias.

A pregunta de Erdős foi resolvida negativamente por Bob Hough.^[5] Hough utilizou o lema local de Lovász para mostrar que hai un máximo de N<10¹⁶ que pode ser o módulo mínimo dunha cuberta.

Sistemas de módulos impares

Hai unha famosa conxectura sen resolver de Erdős e Selfridge: non existe unha cobertura incongruente (co módulo mínimo maior que 1) cuxos módulos son impares. Sábese que se existe tal sistema con módulos libres de cadrados, o módulo global debe ter polo menos 22 factores primos.^[6]

Notas

↑ R. D. Hough, P. P. Nielsen (2019). "Covering systems with restricted divisibility". Duke Math. J. 168 (17): 3261–3295. arXiv:1703.02133. doi:10.1215/00127094-2019-0058.
↑ Soifer, Alexander (2009). The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. New York: Springer. pp. 1–9. ISBN 978-0-387-74640-1. MR 2458293. doi:10.1007/978-0-387-74642-5.
↑ Choi, S. L. G. (1971). "Covering the set of integers by congruence classes of distinct moduli". Math. Comp. 25 (116): 885–895. MR 0297692. doi:10.2307/2004353.
↑ Nielsen, Pace P. (2009). "Un sistema de cobertura cuxo módulo máis pequeno é 40". Revista de Teoría de Números 129: 640–666. MR 2488595. doi:10.1016/j.jnt.2008.09.016.
↑ Hough, Bob (2015). "Solution of the minimum modulus problem for covering systems". Ann. of Math. 181 (1): 361–382. MR 3272928. arXiv:1307.0874. doi:10.4007/annals.2015.181.1.6.
↑ Guo, Song; Sun, Zhi-Wei (2005). "On odd covering systems with distinct moduli". Adv. Appl. Math. 35 (2): 182–187. MR 2152886. arXiv:math/0412217. doi:10.1016/j.aam.2005.01.004.

Véxase tamén

Outros artigos

Ligazóns externas

Zhi-Wei Sun: Problems and Results on Covering Systems (a survey) (PDF)
Zhi-Wei Sun: Classified Publications on Covering Systems(PDF) Arquivado 2007-09-29 en Wayback Machine.

[1] R. D. Hough, P. P. Nielsen (2019). "Covering systems with restricted divisibility". Duke Math. J. 168 (17): 3261–3295. arXiv:1703.02133. doi:10.1215/00127094-2019-0058.

[2] Soifer, Alexander (2009). The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. New York: Springer. pp. 1–9. ISBN 978-0-387-74640-1. MR 2458293. doi:10.1007/978-0-387-74642-5.

[3] Choi, S. L. G. (1971). "Covering the set of integers by congruence classes of distinct moduli". Math. Comp. 25 (116): 885–895. MR 0297692. doi:10.2307/2004353.

[4] Nielsen, Pace P. (2009). "Un sistema de cobertura cuxo módulo máis pequeno é 40". Revista de Teoría de Números 129: 640–666. MR 2488595. doi:10.1016/j.jnt.2008.09.016.

[5] Hough, Bob (2015). "Solution of the minimum modulus problem for covering systems". Ann. of Math. 181 (1): 361–382. MR 3272928. arXiv:1307.0874. doi:10.4007/annals.2015.181.1.6.

[6] Guo, Song; Sun, Zhi-Wei (2005). "On odd covering systems with distinct moduli". Adv. Appl. Math. 35 (2): 182–187. MR 2152886. arXiv:math/0412217. doi:10.1016/j.aam.2005.01.004.

[1]

[2]

[3]

[4]

[5]

[6]