Pinnoitejärjestelmä

Peitejärjestelmä (tai täydellinen peittojärjestelmä ) on sarja

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

äärellinen määrä jäännösluokkia, joiden liitto kattaa kaikki kokonaisluvut. ${\displaystyle a_{i}{\pmod {n_{i))}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \))$

Esimerkkejä ja määritelmiä

Peitejärjestelmän käsitteen esitteli Pal Erdős 1930-luvun alussa.

Peittojärjestelmää kutsutaan disjunktiiviseksi (tai tarkkaksi ), jos mikään jäännösluokkia ei leikkaa (eli järjestelmän eri elementit eivät kata lukua).

Peittojärjestelmää kutsutaan määrätyksi (tai epäjohdonmukaiseksi ), jos kaikki moduulit ovat erilaisia (ja suurempia kuin 1).

Peittojärjestelmän sanotaan olevan redusoitumaton (tai minimaalinen ), jos kaikki jäännösluokat tarvitaan kattamaan kokonaisluvut (yhtään luokkaa ei voida sulkea pois).

Muutamia esimerkkejä peittojärjestelmistä:

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

Tässä kaksi ensimmäistä esimerkkiä ovat disjunktiivisia ja kolmas esimerkki on selvä.

Järjestelmä (eli lajittelematon joukko sarjoja)

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

äärellisen monta jäännösluokkia kutsutaan -coveriksi, jos se peittää minkä tahansa luvun vähintään kerran, ja tarkaksi -coveriksi, jos se peittää jokaisen luvun täsmälleen kerran. Tiedetään, että jokaiselle on olemassa tarkka -kansi, jota ei voida kirjoittaa kahden kannen liitoksi. Esimerkiksi, $m$ $m$ $m$ $m$ $m=2,3,\ldots$ $m$

$\{1{\pmod {2));\ 0{\pmod {3]);\ 2{\pmod {6));\ 0,\,4,\,6,\,8{\ pmod {10}}\};$
${\näyttötyyli 1,\,2,\,4,\,7,\,10,\,13{\pmod {15));\ 5,\,11,\,12,\,22,\,23 ,\,29{\pmod {30}}\}}$

ovat täsmälleen 2-kansia, jotka eivät ole kahden kannen liitto. Ensimmäinen esimerkki on myös tarkka -kansi (tai vain tarkka kansi ). $yksi$

Jokaisen moduulin tarkka kattavuus on tämän moduulin jäämäluokkien järjestelmä: $m$

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

Mirsky–Newman-lause

Mirsky-Newman-lause, Herzog-Schönheim-oletuksen erikoistapaus , väittää, ettei ole olemassa disjunktiivista tarkkaa peittojärjestelmää. Tämän tuloksen esitti olettamuksena vuonna 1950 Pal Erdős , ja pian sen jälkeen Leon Mirsky ja Donald Newman todisti sen , mutta heidän todisteitaan ei ole julkaistu. Saman todisteen löysivät itsenäisesti Harold Davenport ja Richard Rado .[1].

Prime-free-sekvenssit

Peittojärjestelmiä voidaan käyttää alkulukuvapaiden sarjojen etsimiseen , kokonaislukujonoja, jotka täyttävät saman toistuvuussuhteen , jonka Fibonacci-luvut täyttävät , ja siten, että sekvenssin naapuriluvut ovat koalkilukuja , mutta kaikki sekvenssin luvut ovat yhdistelmälukuja . Esimerkiksi tämän tyyppinen sekvenssi, jonka on löytänyt Herbert Wilf , alkaa

a 1 = 206156742055555510, a 2 = 3794765361567513 (sekvenssi A083216 OEIS : ssä ).

Tässä sarjassa paikat, joissa luvut ovat jaollisia alkuluvulla p , muodostavat aritmeettisen jakson. Esimerkiksi sekvenssin parillisten lukujen indeksit ovat yhteneväisiä 1 modulo 3:n kanssa. Eri alkulukujen progressiot muodostavat peittojärjestelmän.

Minimimoduulin rajoitukset

Pal Erös kysyi, onko mielivaltaisen suurelle N :lle olemassa epäyhtenäinen peittojärjestelmä, jossa kaikki moduulit ovat vähintään N. Riittää yksinkertaisesti rakentaa esimerkkejä, joissa minimimoduuli on 2 tai (Erdös antoi esimerkin, jossa moduulit ovat luvun 120 jakajia, peitto tulee olemaan 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 antoi esimerkin, jossa minimimoduuli on 4 (ja moduulit ovat luvun 2880 jakajia). S. L. G. Choi osoitti [2] , että on mahdollista rakentaa esimerkki arvolle N = 20, ja Pace P. Nielsen osoitti [3] , että N = 40 :lle on olemassa esimerkki, joka koostuu useammasta kuin jäännösluokista. $10^{50}$

Bob Hough vastasi Erdősin kysymykseen kieltävästi [4] . Hough käytti Lovasin paikallista lemmaa osoittaakseen, että on olemassa jokin maksimi N , joka voi olla peittojärjestelmän minimimoduuli. Todistus täyttää tehokkaan laskettavuuden periaatteet , mutta selkeää rajaa ei ole annettu.

Parittomien moduulien järjestelmät

Erdősin ja Selfridgen kuuluisa ratkaisematon olettamus - ei ole olemassa varmaa peittojärjestelmää (jonka minimimoduuli on suurempi kuin 1), joka koostuu parittomista moduuleista. Tiedetään, että jos tällainen neliövapailla moduuleilla varustettu järjestelmä on olemassa, kaikkien moduulien tulee sisältää vähintään 22 alkutekijää [5] .

Katso myös

Muistiinpanot

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

Kirjallisuus

Richard K Guy. Ratkaisemattomat ongelmat lukuteoriassa . - Springer-Verlag , 2004. - S. 383-385. — ISBN 0-387-20860-7 .
Aleksanteri Soifer. Matemaattinen värityskirja: Värityksen matematiikka ja sen tekijöiden värikäs elämä. - New York: Springer, 2008. - ISBN 978-0-387-74640-1 .
S.L.G. Choi. Kokonaislukujoukon kattaminen erillisten moduulien kongruenssiluokilla // Math. Comp. . - Laskennan matematiikka, 1971. - V. 25 , no. 116 . - doi : 10.2307/2004353 . — .
Pace P. Nielsen. Peitejärjestelmä, jonka pienin moduuli on 40 // Journal of Number Theory . - 2009. - T. 129 , numero. 3 . - doi : 10.1016/j.jnt.2008.09.016 .
Bob Hough. Peitejärjestelmien minimimoduuliongelman ratkaisu // Ann. matematiikasta. . - 2015. - T. 181 , no. 1 . - doi : 10.4007/annals.2015.181.1.6 .
Song Guo, Zhi-Wei Sun. Parittomat peittojärjestelmät erillisillä moduuleilla // Adv. Appl. Math.. - 2005. - V. 35 , no. 182 . - arXiv : math/0412217 .

Linkit

Zhi-Wei Sun : peittojärjestelmiä koskevat ongelmat ja tulokset arkistoitu 3. maaliskuuta 2016 Wayback Machinessa (kysely) ( PDF )
Zhi-Wei Sun: luokitellut julkaisut peittojärjestelmistä , arkistoitu 29. syyskuuta 2007 Wayback Machinessa (PDF)