Система покрытия - Covering system

В математика, а система покрытия (также называемый полная система остатков) это коллекция

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

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

Система покрытия называется отчетливый (или же несовместимый) если все модули ${\displaystyle n_{i}}$ разные (и больше 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-покрытием, которое не является объединением двух покрытий.

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

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

Это всего лишь один случай следующего факта: для каждого положительного целочисленного модуля ${\displaystyle m}$, есть точная обложка:

${\displaystyle \{0(\mathrm {mod} \ {m}),\ 1(\mathrm {mod} \ {m}),\ \ldots ,\ {m-1}(\mathrm {mod} \ {m})\}.}$

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

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

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

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

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

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

Вопрос Эрдеша был решен отрицательно Бобом Хафом.^[4] Хаф использовал Локальная лемма Ловаса чтобы показать, что есть максимум N<10¹⁶ который может быть минимальным модулем на покрывающей системе.

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

Нерешенная проблема в математике: Существует ли накрывающая система с нечетными различными модулями? (больше нерешенных задач по математике)

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

Смотрите также

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

Рекомендации

1. Сойфер Александр (2009). Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей. С предисловиями Бранко Грюнбаума, Питера Д. Джонсона-младшего и Сесила Руссо. Нью-Йорк: Спрингер. С. 1–9. Дои:10.1007/978-0-387-74642-5. ISBN  978-0-387-74640-1. МИСТЕР  2458293.
2. Цой, С. Л. Г. (1971). «Покрытие множества целых чисел конгруэнтными классами различных модулей». Математика. Комп. 25 (116): 885–895. Дои:10.2307/2004353. МИСТЕР  0297692.
3. Нильсен, Пейс П. (2009). «Система покрытия с наименьшим модулем упругости 40». Журнал теории чисел. 129 (3): 640–666. Дои:10.1016 / j.jnt.2008.09.016. МИСТЕР  2488595.
4. Хаф, Боб (2015). «Решение задачи минимума модуля для покрывающих систем». Анна. математики. 181 (1): 361–382. arXiv:1307.0874. Дои:10.4007 / анналы.2015.181.1.6. МИСТЕР  3272928.
5. Го, Сун; Сунь, Чжи-Вэй (2005). «О нечетных системах покрытия с различными модулями». Adv. Appl. Математика. 35 (2): 182–187. arXiv:математика / 0412217. Дои:10.1016 / j.aam.2005.01.004. МИСТЕР  2152886.

внешняя ссылка

• Чжи-Вэй Сунь: Проблемы и результаты по системам покрытия (опрос) (PDF )
• Чжи-Вэй Сунь: Секретные публикации по системам покрытия (PDF)