Układ kryjący

W matematyce system pokrywający (zwany także kompletnym systemem pozostałości ) jest zbiorem

{\ Displaystyle \ {a_ {1} (\ operatorname {mod} \ {n_ {1}}), \ \ ldots ,\ a_{k}(\mathrm {mod} \ {n_{k}})\}}

za ${\ Displaystyle a_ {i} (\ operatorname {mod} \ {n_ {i}})$ re którego suma zawiera wszystkie liczby całkowite.

Przykłady i definicje

Pojęcie systemu pokrycia zostało wprowadzone przez Paula Erdősa na początku lat 30. XX wieku.

Oto przykłady systemów osłonowych:

${\ Displaystyle \ {0 (\ operatorname {mod} \ {3}), \ 1 (\ operatorname$
${\ Displaystyle \ {1 (\ operatorname {mod} \$
${\ Displaystyle \ {0 (\ operatorname {mod} \ {2}), \ 0 (\ operatorname {mod} \ {3}), \ 1 (\ operatorname {mod} \ {4}), \ 5 (\ mathrm {mod} \ {6}),\ 7(\mathrm {mod} \ {12})\}.}$

System pokrywający nazywany jest rozłącznym (lub dokładnym ), jeśli żadne dwa elementy nie zachodzą na siebie.

System pokrywający nazywany jest $, jeśli$ ( lub niespójnym ) moduły są różne (i większe niż 1). Hough i Nielsen (2019) udowodnili, że każdy odrębny system pokrycia ma moduł podzielny przez 2 lub 3.

System pokrywający nazywany jest nieredundantnym (lub minimalnym ), jeśli wszystkie klasy reszt są wymagane do pokrycia liczb całkowitych.

Pierwsze dwa przykłady są rozłączne.

Wyraźny jest trzeci przykład.

System (tj. nieuporządkowany multi-set)

{\ Displaystyle \ {a_ {1} (\ operatorname {mod} \ {n_ {1}}), \ \ ldots ,\ a_{k}(\mathrm {mod} \ {n_{k}})\}}

skończenie wielu klas reszt nazywa się $m {\$ , jeśli obejmuje każdą liczbę całkowitą co najmniej razy, a dokładna -pokrywa, jeśli obejmuje dokładnie każdą liczbę całkowitą $m}$ $displaystyle$ $} \displaystyle m}$ razy. Wiadomo, że dla każdej $okładki$ $istnieją$ , jako sumę dwóch Na przykład,

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

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

to dokładna 2-okładka, która nie jest sumą dwóch okładek.

Pierwszy przykład powyżej to dokładna okładka 1 (nazywana także dokładną okładką ). Inną dokładną osłoną w powszechnym użyciu są liczby nieparzyste i parzyste lub

{\ Displaystyle \ {0 (\ operatorname {mod} \ {2}), \ 1 (\ operatorname {mod} \ {2}) \}.}

To tylko jeden przypadek następującego faktu: dla każdego dodatniego modułu całkowitego istnieje dokładne pokrycie: ${\ displaystyle m}$

{\ Displaystyle \ {0 (\ operatorname {mod} \ {m}), \ 1 (\ operatorname {mod} \ {m}), \ \ ldots, \ {m-1} (\ operatorname {mod} \ { M})\}.}

Twierdzenie Mirsky'ego-Newmana

Twierdzenie Mirsky'ego-Newmana , szczególny przypadek hipotezy Herzoga-Schönheima , stwierdza, że nie ma rozłącznego odrębnego systemu pokrycia. Wynik ten został wysunięty w 1950 roku przez Paula Erdősa i wkrótce potem udowodniony przez Leona Mirsky'ego i Donalda J. Newmana . Jednak Mirsky i Newman nigdy nie opublikowali swojego dowodu. Ten sam dowód został również znaleziony niezależnie przez Harolda Davenporta i Richarda Rado .

Sekwencje Primefree

Systemy pokrywające mogą być używane do znajdowania ciągów bez liczb pierwszych , ciągów liczb całkowitych spełniających tę samą relację rekurencji co liczby Fibonacciego , tak że kolejne liczby w ciągu są względnie pierwsze , ale wszystkie liczby w ciągu są liczbami złożonymi . Na przykład sekwencja tego typu znaleziona przez Herberta Wilfa ma wyrazy początkowe

a ₁ = 20615674205555510, a ₂ = 3794765361567513 (sekwencja A083216 w OEIS ).

W tej sekwencji pozycje, w których liczby w sekwencji są podzielne przez liczbę pierwszą p , tworzą ciąg arytmetyczny; na przykład liczby parzyste w sekwencji to liczby ai , _i gdzie jest zgodne z 1 mod 3. Ciągi podzielne przez różne liczby pierwsze tworzą system obejmujący, pokazujący, że każda liczba w sekwencji jest podzielna przez co najmniej jedną liczbę pierwszą .

Ograniczenie najmniejszego modułu

Paul Erdős zapytał, czy dla dowolnego dowolnie dużego N istnieje niespójny system pokrycia, którego minimum modułów wynosi co najmniej N . Łatwo jest skonstruować przykłady, w których minimum modułów w takim systemie wynosi 2 lub 3 (Erdős podał przykład, w którym moduły są w zbiorze dzielników 120; odpowiednie pokrycie to 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 podał przykład, w którym minimum modułów wynosi 4 (a moduły mieszczą się w zbiorze dzielników liczby 2880). $,$ że można podać przykład dla N = 20, Pace P Nielsen demonstruje istnienie przykładu z N = , składającego się z ponad kongruencji.

Pytanie Erdősa zostało rozstrzygnięte negatywnie przez Boba Hougha. Hough użył lokalnego lematu Lovásza, aby pokazać, że istnieje pewne maksimum N <10 ¹⁶ , które może być minimalnym modułem w układzie pokrywającym.

Układy o modułach nieparzystych

Nierozwiązany problem z matematyki :

Czy istnieje system pokrycia z nieparzystymi odrębnymi modułami?

(więcej nierozwiązanych problemów z matematyki)

Istnieje słynna nierozwiązana hipoteza Erdősa i Selfridge'a : niespójny system pokrycia (z minimalnym modułem większym niż 1), którego moduły są nieparzyste, nie istnieje. Wiadomo, że jeśli taki system istnieje z modułami wolnymi od kwadratów, to całkowity moduł musi mieć co najmniej 22 czynniki pierwsze.

Zobacz też

Linki zewnętrzne

Zhi-Wei Sun : Problemy i wyniki dotyczące systemów osłonowych (ankieta) ( PDF )
Zhi-Wei Sun: niejawne publikacje na temat systemów pokrywających (PDF) ^{[ martwy link ]}