WikiSort.ru - Не сортированное

Покрывающая система (или полная покрывающая система) — это набор

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

конечного числа классов вычетов ${\displaystyle a_{i}(\mathrm {mod} \ {n_{i}})=\{a_{i}+n_{i}x:\ x\in \mathbb {Z} \}}$ , объединение которых покрывает все целые числа.

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

Понятие покрывающей системы ввёл Пал Эрдёш в начале 1930-х.

Примеры покрывающих систем:

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

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

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

Покрывающая система называется дизьюнктной (или точной), если никакие вычеты не относятся к одному и тому же числу (т.е. число не покрывается различными элементами системы).

Покрывающая система называется определённой (или неконгруэнтной), если все модули отличаются (и больше 1).

Покрывающая система называется несократимой (или минимальной), если все классы вычетов необходимы для покрытия целых чисел (нельзя исключить какой-либо класс).

Первые два примера являются дизьюнктными.

Третий пример является определённым.

Система (т.е. несортированный набор множеств)

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

бесконечного числа классов вычетов называется ${\displaystyle m}$ -покрытием, если она покрывает любое число по меньшей мере ${\displaystyle m}$ раз, и точным ${\displaystyle m}$ -покрытием, если она покрывает каждое число в точности ${\displaystyle m}$ раз. Известно, что для любых ${\displaystyle m=2,3,\ldots }$ имеется точное ${\displaystyle m}$ -покрытие, которое нельзя записать как объединение двух покрытий. Например,

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

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

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

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

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

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

a₁ = 20615674205555510, a₂ = 3794765361567513 (последовательность A083216 в OEIS).

В этой последовательности позиции, в которых числа делятся на простое 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). С. Л. Г. Чой показал^[2], что можно построить пример для N = 20, а Пейс П. Нильсен продемонстрировал^[3] существование примера для N = 40, состоящего из более чем ${\displaystyle 10^{50}}$ классов вычетов.

На вопрос Эрдёша ответил отрицательно Боб Хаф^[4]. Хаф использовал локальную лемму Ловаса^[en], чтобы показать, что существует некоторое максимальное N, которое может быть минимальным модулем покрывающей системы. Доказательство удовлетворяет принципам эффективной вычислимости, но явная граница не приведена.

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

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

См. также

• Китайская теорема об остатках
• Покрывающее множество
• Система остаточных классов

Примечания

Литература

Ссылки

• Zhi-Wei Sun: Problems and Results on Covering Systems (a survey) (PDF)
• Zhi-Wei Sun: Classified Publications on Covering Systems (PDF)

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.