Krycí systém - Covering system - Wikipedia

v matematika, a krycí systém (také nazývaný a kompletní systém zbytků) je sbírka

{ displaystyle {a_ {1} ( mathrm {mod} {n_ {1}}), ldots, a_ {k} ( mathrm {mod} {n_ {k}}) }}

konečně mnoha zbytkové třídy ${ displaystyle a_ {i} ( mathrm {mod} {n_ {i}}) = {a_ {i} + n_ {i} x: x in mathbb {Z} }}$ jehož sjednocení obsahuje každé celé číslo.

Příklady a definice

Pojem krycí systém představil Paul Erdős na počátku 30. let.

Následují příklady krycích systémů:

{ displaystyle {0 ( mathrm {mod} {3}), 1 ( mathrm {mod} {3}), 2 ( mathrm {mod} {3}) },}

a

{ displaystyle {1 ( mathrm {mod} {2}), 2 ( mathrm {mod} {4}), 4 ( mathrm {mod} {8}), 0 ( mathrm {mod} {8}) },}

a

{ displaystyle {0 ( mathrm {mod} {2}), 0 ( mathrm {mod} {3}), 1 ( mathrm {mod} {4}), 5 ( mathrm {mod} {6}), 7 ( mathrm {mod} {12}) }.}

Nazývá se krycí systém disjunktní (nebo přesný) pokud se dva členové nepřekrývají.

Nazývá se krycí systém odlišný (nebo nesourodý) pokud jsou všechny moduly ${ displaystyle n_ {i}}$ jsou různé (a větší než 1).

Nazývá se krycí systém nerozumný (nebo minimální) pokud jsou k pokrytí celých čísel požadovány všechny třídy reziduí.

První dva příklady jsou disjunktní.

Třetí příklad je odlišný.

Systém (tj. Neuspořádaná vícenásobná sada)

{ displaystyle {a_ {1} ( mathrm {mod} {n_ {1}}), ldots, a_ {k} ( mathrm {mod} {n_ {k}}) }}

konečně mnoha tříd reziduí se nazývá ${ displaystyle m}$ -cover, pokud pokrývá alespoň každé celé číslo ${ displaystyle m}$ časy a přesný ${ displaystyle m}$ -cover, pokud přesně pokrývá každé celé číslo ${ displaystyle m}$ krát. Je známo, že pro každého ${ displaystyle m = 2,3, ldots}$ existují přesné ${ displaystyle m}$ -obálky, které nelze zapsat jako spojení dvou obálek. Například,

{ displaystyle {1 ( mathrm {mod} {2}); 0 ( mathrm {mod} {3}); 2 ( mathrm {mod} {6}); 0,4 , 6,8 ( mathrm {mod} {10});}

{ displaystyle 1,2,4,7,10,13 ( mathrm {mod} {15}); 5,11,12,22,23,29 ( mathrm {mod} {30}) }}

je přesný 2 obal, který není spojením dvou obalů.

První příklad výše je přesná 1 obálka (nazývaná také přesný obal). Dalším přesným běžným používáním je krytí lichých a sudá čísla nebo

{ displaystyle {0 ( mathrm {mod} {2}), 1 ( mathrm {mod} {2}) }.}

Toto je pouze jeden případ následující skutečnosti: Pro každý kladný celočíselný modul ${ displaystyle m}$ , existuje přesný obal:

{ displaystyle {0 ( mathrm {mod} {m}), 1 ( mathrm {mod} {m}), ldots, {m-1} ( mathrm {mod} { m}) }.}

Mirsky – Newmanova věta

Mirsky – Newmanova věta, speciální případ Domněnka Herzog – Schönheim, uvádí, že neexistuje disjunktní odlišný krycí systém. Tento výsledek předpokládal v roce 1950 Paul Erdős a brzy poté se ukázalo Leon Mirsky a Donald J. Newman. Mirsky a Newman však svůj důkaz nikdy nezveřejnili. Stejný důkaz nalezl také nezávisle Harold Davenport a Richard Rado.^[1]

Primefree sekvence

K nalezení lze použít krycí systémy primefree sekvence, sekvence celých čísel splňující stejné relace opakování jako Fibonacciho čísla, taková, že po sobě jdoucí čísla v pořadí jsou relativně prime ale všechna čísla v pořadí jsou složená čísla. Například posloupnost tohoto typu nalezená uživatelem Herbert Wilf má počáteční podmínky

A₁ = 20615674205555510, A₂ = 3794765361567513 (sekvence A083216 v OEIS ).

V této posloupnosti jsou pozice, ve kterých jsou čísla v posloupnosti dělitelná prvočíslem p tvoří aritmetický postup; například sudá čísla v pořadí jsou čísla A_i kde i je shodný s 1 módem 3. Postupy dělitelné různými prvočísly tvoří krycí systém, což ukazuje, že každé číslo v posloupnosti je dělitelné alespoň jedním prvočíslem.

Ohraničenost nejmenšího modulu

Paul Erdős zeptal se, zda pro libovolně velké N existuje nesourodý krycí systém, jehož modul je minimálně minimální N. Je snadné sestrojit příklady, kde minimum modulů v takovém systému je 2 nebo 3 (Erdős uvedl příklad, kde jsou moduly v sadě dělitelů 120; vhodný obal je 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 uvedl příklad, kdy minimum modulů je 4 (a moduly jsou v sadě dělitelů 2880). S. L. G. Choi prokázáno^[2] že je možné uvést příklad pro N = 20 a Pace P Nielsen předvádí^[3] existence příkladu s N = 40, skládající se z více než ${ displaystyle 10 ^ {50}}$ shody.

Erdősovu otázku vyřešil záporně Bob Hough.^[4] Hough použil Lovász místní lemma ukázat, že existuje určité maximum N<10¹⁶ což může být minimální modul na krycím systému.

Systémy lichých modulů

Nevyřešený problém v matematice:

Existuje krycí systém s lichými odlišnými moduly?

(více nevyřešených úloh z matematiky)

Existuje slavná nevyřešená domněnka od Erdőse a Selfridge: nesourodý krycí systém (s minimálním modulem větším než 1), jehož moduly jsou liché, neexistuje. Je známo, že pokud takový systém existuje s moduly bez čtverců, celkový modul musí mít alespoň 22 hlavních faktorů.^[5]

Viz také

Reference

^ Soifer, Alexander (2009). Matematická omalovánka: Matematika zbarvení a barevný život jeho tvůrců. S předmluvami Branko Grünbaum, Peter D. Johnson, Jr. a Cecil Rousseau. New York: Springer. s. 1–9. doi:10.1007/978-0-387-74642-5. ISBN 978-0-387-74640-1. PAN 2458293.
^ Choi, S. L. G. (1971). "Pokrytí množiny celých čísel třídami shody různých modulů". Matematika. Comp. 25 (116): 885–895. doi:10.2307/2004353. PAN 0297692.
^ Nielsen, Pace P. (2009). "Krycí systém, jehož nejmenší modul je 40". Žurnál teorie čísel. 129 (3): 640–666. doi:10.1016 / j.jnt.2008.09.016. PAN 2488595.
^ Hough, Bob (2015). "Řešení problému minimálního modulu pro krycí systémy". Ann. matematiky. 181 (1): 361–382. arXiv:1307.0874. doi:10.4007 / annals.2015.181.1.6. PAN 3272928.
^ Guo, píseň; Sun, Zhi-Wei (2005). "Na lichých krycích systémech s odlišnými moduly". Adv. Appl. Matematika. 35 (2): 182–187. arXiv:matematika / 0412217. doi:10.1016 / j.aam.2005.01.004. PAN 2152886.

externí odkazy

Zhi-Wei Sun: Problémy a výsledky na krycích systémech (průzkum) (PDF )
Zhi-Wei Sun: Utajované publikace o krycích systémech (PDF)

[soifer-1] Soifer, Alexander (2009). Matematická omalovánka: Matematika zbarvení a barevný život jeho tvůrců. S předmluvami Branko Grünbaum, Peter D. Johnson, Jr. a Cecil Rousseau. New York: Springer. s. 1–9. doi:10.1007/978-0-387-74642-5. ISBN 978-0-387-74640-1. PAN 2458293.

[2] Choi, S. L. G. (1971). "Pokrytí množiny celých čísel třídami shody různých modulů". Matematika. Comp. 25 (116): 885–895. doi:10.2307/2004353. PAN 0297692.

[3] Nielsen, Pace P. (2009). "Krycí systém, jehož nejmenší modul je 40". Žurnál teorie čísel. 129 (3): 640–666. doi:10.1016 / j.jnt.2008.09.016. PAN 2488595.

[4] Hough, Bob (2015). "Řešení problému minimálního modulu pro krycí systémy". Ann. matematiky. 181 (1): 361–382. arXiv:1307.0874. doi:10.4007 / annals.2015.181.1.6. PAN 3272928.

[5] Guo, píseň; Sun, Zhi-Wei (2005). "Na lichých krycích systémech s odlišnými moduly". Adv. Appl. Matematika. 35 (2): 182–187. arXiv:matematika / 0412217. doi:10.1016 / j.aam.2005.01.004. PAN 2152886.

[1]

[2]

[3]

[4]

[5]