Покрывающая система

Покрывающая система (или полная покрывающая система)— это набор
{a1(mod n1), , ak(mod nk)}

 конечного числа классов вычетовai(mod ni)={ai+nix: x\Z}, объединениекоторых покрывает все целые числа.

Примеры иопределения


 Понятие покрывающей системы ввёл Пал Эрдёш в начале 1930-х.
 Примеры покрывающих систем:
{0(mod 3), 1(mod 3), 2(mod 3)},

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

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

 Покрывающая система называется дизьюнктной (или точной), если никакиевычеты не относятся к одному и тому же числу (т.е. число не покрываетсяразличными элементами системы).
 Покрывающая система называется определённой (или неконгруэнтной), есливсе модули отличаются (и больше 1).
 Покрывающая система называется несократимой (или минимальной), если всеклассы вычетов необходимы для покрытия целых чисел (нельзя исключитькакой-либо класс).
 Первые два примера являются дизьюнктными.
 Третий пример является определённым.
 Система (т.е. несортированный набор множеств)
{a1(mod n1), , ak(mod nk)}

 бесконечного числа классов вычетов называется m-покрытием, если онапокрывает любое число по меньшей мере m раз, и точным m-покрытием,если она покрывает каждое число в точности m раз. Известно, что длялюбых m=2,3, имеется точное m-покрытие, которое нельзязаписать как объединение двух покрытий. Например,
{1(mod 2); 0(mod 3); 2(mod 6); 0,4,6,8(mod 10);

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

 является точным 2-покрытием, которое не является объединением двухпокрытий.

ТеоремаМирского–Ньюмана


 Теорема Мирского – Ньюмана, частный случай , утверждает, что несуществует дизъюнктной определённой покрывающей системы. Этот результатбыл высказан в виде гипотезы в 1950 Палом Эрдёшом и доказан вскоре послеэтого и , однако их доказательство не было опубликовано. То же самоедоказательство нашли независимо и .

Свободные от простых чиселпоследовательности


 Покрывающие системы можно использовать для поиска , последовательностейцелых чисел, удовлетворяющих тому же рекуррентному соотношению, которомуудовлетворяют числа Фибоначчи, и таких, что соседние числа впоследовательности взаимно просты, но все числа в последовательностиявляются составными. Например, последовательность этого типа, найденная, начинается с

a1 = 20615674205555510, a2= 3794765361567513 .
 В этой последовательности позиции, в которых числа делятся на простоеp, образуют арифметичесую прогрессию. Например, индексы чётныхчисел в последовательности сравнимы с 1 по модулю 3. Прогрессии дляразличных простых чисел образуют покрывающую систему.

Ограничения на минимальныймодуль


 Пал Эрёш спрашивал, существует ли для произвольно большого Nнеконгруэнтная покрывающая система, в которой все модули не меньшеN. Достаточно просто построить примеры, в которых минимальныймодуль равен 2 или (Эрдёш привёл пример, в котором модули являютсяделителями числа 120, покрытием будет 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) ). Д.Свифт дал пример, в котором минимальный модуль равен 4 (и модулиявляются делителями числа 2880). С. Л. Г. Чой показал, что можнопостроить пример для N = 20, а Пейс П. Нильсен продемонстрировалсуществование примера для N = 40, состоящего из более чем1050 классов вычетов.
 На вопрос Эрдёша ответил отрицательно Боб Хаф. Хаф использовал , чтобыпоказать, что существует некоторое максимальное N, которое можетбыть минимальным модулем покрывающей системы. Доказательствоудовлетворяет принципам эффективной вычислимости, но явная граница неприведена.

Системы нечётныхмодулей


 Имеется знаменитая нерешённая гипотеза Эрдёша и Селфриджа — несуществует определённой покрывающей системы (с минимальным модулем,большим 1), состоящей из нечётных модулей. Известно, что если такаясистема со свободными от квадратов модулями существует, все модулидолжны содержать по меньшей мере 22 простых множителя.