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

В математике , А покрывающая система (также называемая полная система остаток ) представляет собой набор

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

и

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

и

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

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

Система покрытия называется отличной (или неконгруэнтной ), если все модули различны (и больше единицы). $n_{i}$

Система покрытия называется неизбыточной (или минимальной ), если требуется, чтобы все классы вычетов покрывали целые числа.

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

Третий пример особенный.

Система (т. Е. Неупорядоченный мульти-набор)

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

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

\{1(\mathrm {mod} \ {2});\ 0(\mathrm {mod} \ {3});\ 2(\mathrm {mod} \ {6});\ 0,4,6,8(\mathrm {mod} \ {10});

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

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

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

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

Это всего лишь один случай следующего факта: для каждого положительного целочисленного модуля существует точное покрытие: $m$

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

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

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

Последовательности Primefree [ править ]

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

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

В этой последовательности позиции, в которых числа в последовательности делятся на простое число p, образуют арифметическую прогрессию; например, четные числа в последовательности - это числа a _i, где 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). SLG Choi доказал ^[2], что можно привести пример для N = 20, а Pace P Nielsen демонстрирует ^[3] существование примера сN = 40, состоящих из более чем совпадений. $10^{50}$

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

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

Нерешенная задача по математике :

Существует ли накрывающая система с нечетными различными модулями?

(больше нерешенных задач по математике)

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

См. Также [ править ]

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

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

Внешние ссылки [ править ]

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

[soifer-1] Сойфер, Александр (2009). Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей . С предисловиями Бранко Грюнбаума, Питера Д. Джонсона-младшего и Сесила Руссо. Нью-Йорк: Спрингер. С. 1–9. DOI : 10.1007 / 978-0-387-74642-5 . ISBN 978-0-387-74640-1. Руководство по ремонту 2458293 .

[2] Choi, SLG (1971). «Покрытие множества целых чисел конгруэнтными классами различных модулей» . Математика. Комп. 25 (116): 885–895. DOI : 10.2307 / 2004353 . Руководство по ремонту 0297692 .

[3] Перейти ↑ Nielsen, Pace P. (2009). «Система покрытия с наименьшим модулем упругости 40». Журнал теории чисел . 129 (3): 640–666. DOI : 10.1016 / j.jnt.2008.09.016 . Руководство по ремонту 2488595 .

[4] Хаф, Боб (2015). «Решение задачи минимума модуля для покрывающих систем». Анна. математики. 181 (1): 361–382. arXiv : 1307.0874 . DOI : 10.4007 / annals.2015.181.1.6 . Руководство по ремонту 3272928 .

[5] Го, Сун; Сунь, Чжи-Вэй (2005). «О нечетных системах покрытия с различными модулями». Adv. Прил. Математика . 35 (2): 182–187. arXiv : math / 0412217 . DOI : 10.1016 / j.aam.2005.01.004 . Руководство по ремонту 2152886 .

[1]