Введение

В математике система покрытий (также называемая полной системой вычетов) — это набор конечного числа классов вычетов, объединение которых содержит все целые числа.

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

Теорема Мирски — Ньюмана, частный случай гипотезы Герцога — Шёнгейма, утверждает, что не существует системы непересекающихся различных покрытий. Этот результат был предложен в 1950 году Полом Эрдошем и вскоре после этого доказан Леоном Мирски и Дональдом Дж. Ньюманом. Однако Мирски и Ньюман так и не опубликовали своё доказательство. То же самое доказательство было также независимо найдено Гарольдом Давенпортом и Ричардом Радо.

Беспроигрышные последовательности

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

Ограниченность самого маленького модуля

Пол Эрдош задался вопросом, существует ли для любого произвольно большого N несовместимая система покрытий, минимум модулей которой не меньше N. Легко построить примеры, где минимум модулей в такой системе равен 2 или 3 (Эрдош привел пример, где модули принадлежат множеству делителей 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, состоящего более чем из 100 конгруэнций. Вопрос Эрдоша был решен Бобом Хаугом в отрицательном смысле. Хауг использовал локальную лемму Ловаса, чтобы показать, что существует некоторое максимальное N < 10¹⁶, которое может быть минимальным модулем в системе покрытий.

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

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