Bevonatrendszer

A fedőrendszer (vagy teljes burkolati rendszer ) egy készlet

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

véges számú maradékosztály, amelynek uniója minden egész számot lefed . ${\displaystyle a_{i}{\pmod {n_{i))}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \))$

Példák és definíciók

A burkolatrendszer fogalmát Erdős Pál vezette be az 1930-as évek elején.

Egy fedőrendszert diszjunktívnak (vagy egzaktnak ) nevezünk, ha egyetlen maradékosztály sem metszi egymást (azaz a számot nem fedik le a rendszer különböző elemei).

Egy fedőrendszert határozottnak (vagy inkongruensnek ) nevezünk, ha minden modul különböző (és nagyobb 1-nél).

Egy fedőrendszerről azt mondjuk , hogy irreducibilis (vagy minimális ), ha minden maradékosztályra szükség van az egész számok lefedéséhez (egy osztályt sem lehet kizárni).

Néhány példa a fedőrendszerekre:

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

Itt az első két példa diszjunktív, a harmadik pedig határozott.

Rendszer (azaz készletek rendezetlen halmaza)

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

A véges sok maradék osztályt -covernek nevezzük, ha bármely számot legalább egyszer lefed, és pontos -covernek, ha minden számot pontosan többször fed le. Köztudott, hogy bármelyikhez létezik egy pontos -borító, amely nem írható le két borító egyesüléseként. Például, $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}}\}$

pontosan 2-borítók, amelyek nem két borító egyesülését jelentik. Az első példa is egy pontos -cover (vagy csak egy pontos borító ). $egy$

Bármely modul esetében a pontos lefedettség az ehhez a modulhoz tartozó maradékosztályok rendszere lesz: $m$

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

Mirsky–Newman tétel

A Mirsky–Newman-tétel, a Herzog–Schönheim-sejtés speciális esete , kimondja, hogy nincs diszjunktív határozott fedőrendszer. Ezt az eredményt 1950- ben Erdős Pál sejtésként terjesztette elő, majd nem sokkal később Leon Mirsky és Donald Newman is bebizonyította , de bizonyítékukat nem tették közzé. Ugyanezt a bizonyítékot egymástól függetlenül találta meg Harold Davenport és Richard Rado .[1].

Prime-free sorozatok

A lefedő rendszerek használhatók prímmentes sorozatok , egész számok olyan sorozatainak keresésére, amelyek kielégítik ugyanazt az ismétlődési relációt , mint a Fibonacci-számok , és úgy, hogy a sorozatban a szomszédos számok másodprímek , de a sorozatban lévő összes szám összetett . Például egy ilyen típusú sorozat, amelyet Herbert Wilf talált , ezzel kezdődik

a 1 = 206156742055555510, a 2 = 3794765361567513 ( A083216 sorozat az OEIS -ben ).

Ebben a sorozatban azok a pozíciók, ahol a számok oszthatók p prímszámmal , aritmetikai sorozatot alkotnak. Például egy sorozat páros számainak indexei 1 modulo 3-hoz kongruensek. A különböző prímszámok előrehaladása fedőrendszert alkot.

A minimális modulus korlátozása

Erös Pál azt kérdezte, hogy egy tetszőlegesen nagy N esetén létezik-e olyan inkongruens fedőrendszer, amelyben minden modul legalább N . Elég egyszerűen olyan példákat konstruálni, amelyekben a minimális modulus 2 vagy (Erdös adott egy példát, amelyben a modulok a 120-as szám osztói, a lefedettség 0(3), 0(4), 0(5), 1. cikk (6), (8), 2 (10), 11 (12), 1 (15), 14 (20), 5 (24), 8 (30), 6 (40), 58 (60), 26(120) ). D. Swift adott egy példát, ahol a minimális modulus 4 (a modulusok pedig 2880 osztói). S. L. G. Choi megmutatta [2] , hogy lehetséges példát konstruálni N = 20-ra, Pace P. Nielsen pedig bemutatta [3] , hogy létezik egy példa N = 40-re, amely több mint maradékosztályból áll. $10^{50}$

Erdős kérdésére Bob Hough nemmel válaszolt [4] . Hough Lovas lokális lemmáját használta annak kimutatására, hogy van néhány maximális N , amely egy fedőrendszer minimális modulusa lehet. A bizonyítás megfelel a hatékony kiszámíthatóság elveinek , de nincs kifejezett korlát.

Páratlan modulok rendszerei

Erdős és Selfridge híres megfejtetlen sejtése - nincs határozott (1-nél nagyobb modulusú) páratlan modulokból álló fedőrendszer. Ismeretes, hogy ha létezik ilyen négyzetmentes modulokat tartalmazó rendszer, akkor minden modulnak legalább 22 prímtényezőt kell tartalmaznia [5] .

Lásd még

Jegyzetek

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

Irodalom

Richard K Guy. Megoldatlan problémák a számelméletben . - Springer-Verlag , 2004. - S. 383-385. — ISBN 0-387-20860-7 .
Sándor Soifer. A Matematikai kifestőkönyv: A színezés matematikája és alkotóinak színes élete. - New York: Springer, 2008. - ISBN 978-0-387-74640-1 .
S.L.G. Choi. Az egész számok halmazának lefedése különböző modulusok kongruenciaosztályaival // Math. Összeg. . - Számítási matematika, 1971. - V. 25 , sz. 116 . - doi : 10.2307/2004353 . — .
Pace P. Nielsen. Egy fedőrendszer, amelynek legkisebb modulusa 40 // Journal of Number Theory . - 2009. - T. 129 , szám. 3 . - doi : 10.1016/j.jnt.2008.09.016 .
Bob Hough. A fedőrendszerek minimális modulusprobléma megoldása // Ann. a Math. . - 2015. - T. 181 , sz. 1 . - doi : 10.4007/annals.2015.181.1.6 .
Song Guo, Zhi-Wei Sun. Különálló modulokat tartalmazó páratlan fedésű rendszereken // Adv. Appl. Matek.. - 2005. - V. 35 , sz. 182 . - arXiv : math/0412217 .

Linkek

Zhi-Wei Sun : Problémák és eredmények a fedőrendszerekkel kapcsolatban archiválva 2016. március 3-án a Wayback Machine -nél (felmérés) ( PDF )
Zhi-Wei Sun: A fedőrendszerekről szóló minősített kiadványok archiválva 2007. szeptember 29-én a Wayback Machine -nél (PDF)