Sistem de acoperire

Un sistem de acoperire (sau un sistem complet de acoperire ) este un set

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

un număr finit de clase de reziduuri a căror unire acoperă toate numerele întregi. $a_{i}{\pmod {n_{i)}}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \)$

Exemple și definiții

Conceptul de sistem de acoperire a fost introdus de Pal Erdős la începutul anilor 1930.

Un sistem de acoperire se numește disjunctiv (sau exact ) dacă nu se intersectează clase de reziduuri (adică numărul nu este acoperit de diferite elemente ale sistemului).

Un sistem de acoperire se numește definit (sau incongruent ) dacă toate modulele sunt diferite (și mai mari decât 1).

Se spune că un sistem de acoperire este ireductibil (sau minim ) dacă toate clasele de reziduuri sunt necesare pentru a acoperi numerele întregi (nicio clasă nu poate fi exclusă).

Câteva exemple de sisteme de acoperire:

$\{0{\pmod {3}),\ 1{\pmod {3)),\ 2{\pmod {3}}\},$
$\{1{\pmod {2}),\ 2{\pmod {4)],\ 4{\pmod {8)),\ 0{\pmod {8))\},$
$\{0(\mathrm {mod} \ {2}),\ 0(\mathrm {mod} \ {3}),\ 1(\mathrm {mod} \ {4}),\ 5(\ mathrm {mod} \ {6}),\ 7(\mathrm {mod} \ {12})\}.$

Aici primele două exemple sunt disjunctive, iar al treilea exemplu este definitiv.

Sistem (adică set nesortat de seturi)

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

un număr finit de clase de reziduuri se numește -acoperire dacă acoperă orice număr de cel puțin ori și o acoperire exactă dacă acoperă fiecare număr de exact ori. Se știe că pentru oricare există o copertă exactă care nu poate fi scrisă ca unirea a două coperți. De exemplu, $m$ $m$ $m$ $m$ $m=2,3,\ldots$ $m$

$\{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}}\}$

sunt exact 2-coperte care nu sunt unirea a două capace. Primul exemplu este, de asemenea, o acoperire exactă (sau doar o acoperire exactă ). $unu$

Pentru orice modul , acoperirea exactă va fi sistemul de clase de reziduuri pentru acest modul: $m$

\{0{\pmod {m)),\ 1{\pmod {m)],\ \ldots ,\ {m-1}{\pmod {m))\}.

Teorema Mirsky–Newman

Teorema Mirsky–Newman, un caz special al conjecturii Herzog–Schönheim , afirmă că nu există un sistem de acoperire definit disjunctiv. Acest rezultat a fost prezentat ca o presupunere în 1950 de Pal Erdős și dovedit la scurt timp după aceea de Leon Mirsky și Donald Newman , dar dovada lor nu a fost publicată. Aceeași dovadă a fost găsită independent de Harold Davenport și Richard Rado .[1].

Secvențe fără prim

Sistemele de acoperire pot fi folosite pentru a găsi secvențe fără prime , secvențe de numere întregi care satisfac aceeași relație de recurență pe care o satisfac numerele Fibonacci și astfel încât numerele învecinate din șir să fie coprime , dar toate numerele din șir sunt compuse . De exemplu, o secvență de acest tip, găsită de Herbert Wilf , începe cu

a 1 = 20615674205555510, a 2 = 3794765361567513 (secvența A083216 în OEIS ).

În această secvență, pozițiile în care numerele sunt divizibile cu primul p formează o progresie aritmetică. De exemplu, indicii numerelor pare dintr-o succesiune sunt congruenți cu 1 modulo 3. Progresiile pentru diverse numere prime formează un sistem de acoperire.

Restricții privind modulul minim

Pal Erös a întrebat dacă, pentru un N arbitrar mare , există un sistem de acoperire incongruent în care toți modulele sunt cel puțin N. Este suficient să construiți pur și simplu exemple în care modulul minim este 2 sau (Erdös a dat un exemplu în care modulele sunt divizori ai numărului 120, acoperirea va fi 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 a dat un exemplu în care modulul minim este 4 (și modulele sunt divizori ai lui 2880). S. L. G. Choi a arătat [2] că este posibil să se construiască un exemplu pentru N = 20, iar Pace P. Nielsen a demonstrat [3] existența unui exemplu pentru N = 40 constând din mai mult decât clase de reziduuri. $10^{50}$

Întrebarea lui Erdős a primit un răspuns negativ de către Bob Hough [4] . Hough a folosit lema locală a lui Lovas pentru a arăta că există un N maxim care poate fi modulul minim al unui sistem de acoperire. Dovada satisface principiile calculabilității efective , dar nu este dată nicio limită explicită.

Sisteme de module impare

Există faimoasa presupunere nerezolvată a lui Erdős și Selfridge - nu există un sistem de acoperire definit (cu un modul minim mai mare de 1) constând din module impare. Se știe că dacă există un astfel de sistem cu module fără pătrat, toate modulele trebuie să conțină cel puțin 22 de factori primi [5] .

Vezi și

Note

↑ Soifer, 2008 , p. 1–9.
↑ Choi, 1971 , p. 885–895.
↑ Nielsen, 2009 , p. 640–666.
↑ Hough, 2015 , p. 361–382.
↑ Guo, Sun, 2005 .

Literatură

Richard K Guy. Probleme nerezolvate în teoria numerelor . - Springer-Verlag , 2004. - S. 383-385. — ISBN 0-387-20860-7 .
Alexandru Soifer. Cartea de colorat matematică: matematica colorării și viața plină de culoare a creatorilor săi. - New York: Springer, 2008. - ISBN 978-0-387-74640-1 .
S.L.G. Choi. Acoperirea multimii numerelor întregi prin clase de congruență de module distincte // Math. Comp. . - Matematica calculului, 1971. - V. 25 , nr. 116 . - doi : 10.2307/2004353 . — .
Pace P. Nielsen. Un sistem de acoperire al cărui modul cel mai mic este 40 // Journal of Number Theory . - 2009. - T. 129 , nr. 3 . - doi : 10.1016/j.jnt.2008.09.016 .
Bob Hough. Rezolvarea problemei modulului minim pentru sisteme de acoperire // Ann. de Matematică. . - 2015. - T. 181 , nr. 1 . - doi : 10.4007/annals.2015.181.1.6 .
Song Guo, Zhi-Wei Sun. Pe sisteme de acoperire ciudate cu module distincte // Adv. Aplic. Matematică.. - 2005. - V. 35 , nr. 182 . - arXiv : math/0412217 .

Link -uri

Zhi-Wei Sun : Probleme și rezultate privind sistemele de acoperire Arhivat 3 martie 2016 la Wayback Machine (un sondaj) ( PDF )
Zhi-Wei Sun: Publicații clasificate despre sistemele de acoperire Arhivat 29 septembrie 2007 la Wayback Machine (PDF)