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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

конечного числа классов вычетов , объединение которых покрывает все целые числа.


Примеры и определения[править | править код]

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

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

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

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

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

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

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

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

бесконечного числа классов вычетов называется -покрытием, если она покрывает любое число по меньшей мере раз, и точным -покрытием, если она покрывает каждое число в точности раз. Известно, что для любых имеется точное -покрытие, которое нельзя записать как объединение двух покрытий. Например,

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

Теорема Мирского–Ньюмана[править | править код]

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

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

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

a1 = 20615674205555510, a2 = 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, состоящего из более чем классов вычетов.

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

Системы нечётных модулей[править | править код]

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

См. также[править | править код]

Примечания[править | править код]

  1. Soifer, 2008, с. 1–9.
  2. Choi, 1971, с. 885–895.
  3. Nielsen, 2009, с. 640–666.
  4. Hough, 2015, с. 361–382.
  5. Guo, Sun, 2005.

Литература[править | править код]

Ссылки[править | править код]