Beläggningssystem

Ett täcksystem (eller komplett täcksystem ) är en uppsättning

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

ett ändligt antal restklasser vars förening täcker alla heltal. ${\displaystyle a_{i}{\pmod {n_{i))}=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \))$

Exempel och definitioner

Konceptet med ett täcksystem introducerades av Pal Erdős i början av 1930-talet.

Ett täckande system kallas disjunktivt (eller exakt ) om inga restklasser skär varandra (dvs numret täcks inte av olika delar av systemet).

Ett täckningssystem kallas definitivt (eller inkongruent ) om alla moduler är olika (och större än 1).

Ett täckningssystem sägs vara irreducerbart (eller minimalt ) om alla restklasser behövs för att täcka heltal (ingen klass kan uteslutas).

Några exempel på täcksystem:

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

Här är de två första exemplen disjunktiva och det tredje exemplet är definitivt.

System (d.v.s. osorterad uppsättning uppsättningar)

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

ändligt många restklasser kallas en -cover om den täcker vilket nummer som helst minst gånger, och en exakt -cover om den täcker varje nummer exakt gånger. Det är känt att det för alla finns ett exakt -omslag som inte kan skrivas som en förening av två omslag. Till exempel, $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}}\}$

är exakta 2-kåpor som inte är föreningen av två höljen. Det första exemplet är också ett exakt -omslag (eller bara ett exakt omslag ). $ett$

För alla moduler kommer den exakta täckningen att vara systemet med restklasser för denna modul: $m$

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

Mirsky–Newmans teorem

Mirsky-Newman-satsen, ett specialfall av Herzog-Schönheim-förmodan , säger att det inte finns något disjunktivt definitivt täcksystem. Detta resultat lades fram som en gissning 1950 av Pal Erdős och bevisades kort därefter av Leon Mirsky och Donald Newman , men deras bevis har inte publicerats. Samma bevis hittades oberoende av Harold Davenport och Richard Rado .[1].

Prime-fria sekvenser

Täckande system kan användas för att hitta primtalsfria sekvenser , sekvenser av heltal som uppfyller samma återkommande relation som Fibonacci-tal uppfyller , och sådana att närliggande siffror i sekvensen är coprime , men alla tal i sekvensen är sammansatta . Till exempel börjar en sekvens av denna typ, hittad av Herbert Wilf , med

a 1 = 20615674205555510, a 2 = 3794765361567513 (sekvens A083216 i OEIS ).

I denna sekvens bildar positionerna där talen är delbara med primtal p ett aritmetiskt fortskridande. Till exempel är indexen för jämna tal i en sekvens kongruenta med 1 modulo 3. Progressioner för olika primtal bildar ett täckande system.

Restriktioner för minimimodulen

Pal Erös frågade om det för ett godtyckligt stort N existerar ett inkongruent täcksystem där alla moduler är åtminstone N . Det räcker med att helt enkelt konstruera exempel där minimimodulen är 2 eller (Erdös gav ett exempel där modulerna är divisorer av talet 120, täckningen blir 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 gav ett exempel där minimimodulen är 4 (och modulerna är divisorer av 2880). S. L. G. Choi visade [2] att det är möjligt att konstruera ett exempel för N = 20, och Pace P. Nielsen visade [3] förekomsten av ett exempel för N = 40 som består av mer än restklasser. $10^{50}$

Erdős fråga besvarades nekande av Bob Hough [4] . Hough använde Lovas lokala lemma för att visa att det finns något maximalt N som kan vara minimimodulen för ett täcksystem. Beviset uppfyller principerna för effektiv beräkningsbarhet , men ingen explicit gräns ges.

System med udda moduler

Det finns den berömda olösta gissningen om Erdős och Selfridge - det finns inget bestämt täcksystem (med en minsta modul större än 1) som består av udda moduler. Det är känt att om ett sådant system med kvadratfria moduler existerar måste alla moduler innehålla minst 22 primtalsfaktorer [5] .

Se även

Anteckningar

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

Litteratur

Richard K Guy. Olösta problem i talteorin . - Springer-Verlag , 2004. - S. 383-385. — ISBN 0-387-20860-7 .
Alexander Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. - New York: Springer, 2008. - ISBN 978-0-387-74640-1 .
S.L.G. Choi. Täcker uppsättningen heltal med kongruensklasser med distinkta moduler // Math. Comp. . - Mathematics of Computation, 1971. - V. 25 , nr. 116 . - doi : 10.2307/2004353 . — .
Pace P. Nielsen. Ett täckande system vars minsta modul är 40 // Journal of Number Theory . - 2009. - T. 129 , nummer. 3 . - doi : 10.1016/j.jnt.2008.09.016 .
Bob Hough. Lösning av minimimodulproblemet för täcksystem // Ann. av matte. . - 2015. - T. 181 , nr. 1 . - doi : 10.4007/annals.2015.181.1.6 .
Song Guo, Zhi-Wei Sun. På udda täcksystem med distinkta moduler // Adv. Appl. Math.. - 2005. - V. 35 , nr. 182 . - arXiv : math/0412217 .

Länkar

Zhi-Wei Sun : Problem och resultat på täckande system Arkiverad 3 mars 2016 på Wayback Machine (en undersökning) ( PDF )
Zhi-Wei Sun: Classified Publications on Covering Systems Arkiverad 29 september 2007 på Wayback Machine (PDF)