Основная задача теории отсеивания заключается в понимании того, что происходит, когда мы начинаем с целых чисел (или некоторого подынтервала целых чисел) и удаляем некоторые классы вычетов для различных модулей. В данном случае мы рассматриваем простое условие, когда мы отсеиваем все целые числа, а не интервал, и удаляем лишь конечное число классов вычетов.
В этом случае множество целых чисел, оставшихся после отсеивания, является периодическим с периодом, поэтому можно работать без потери общности в циклической группе. Тогда возникает вопрос: какова плотность просеянного множества?
Если все модули взаимно просты, то из китайской теоремы об остатках легко увидеть, что плотность задаётся произведением.
Когда модули не являются взаимно простыми, ситуация усложняется. Можно использовать формулу включения-исключения, чтобы получить сложное выражение для плотности, но с ним нелегко работать. Теория отсеивания также предоставляет различные полезные верхние и нижние оценки (начиная с классических неравенств Бонферрони), но не даёт точных формул.
Теорема Роджерса
Для фиксированных параметров плотность просеянного множества максимальна, когда все параметры исчезают.
Пример:
Если мы отсеем числа 2, 3 и 5, то останется только число 1, что даёт плотность 1/6. С другой стороны, если мы отсеем числа 2, 3 и 7, то оставшиеся элементы будут 1 и 5, что даёт большую плотность 2/6.
Результат, о котором идёт речь, был описан в работе Халберстама и Рота, где авторы в сноске пишут, что результат «не опубликован; сообщено авторам профессором Роджерсом». Мне удалось найти его упоминание только в трёх источниках: в статье Льюиса 1996 года, в статье Филасаты, Форда, Конягина, Померанса и Ю 2007 года (где они приписывают Тененбауму за то, что он обратил их внимание на эту ссылку) и кратко упоминается в статье Форда 2008 года.
Насколько я могу судить, результат недоступен в интернете, что могло бы объяснить, почему на него редко ссылаются (и также почему он неизвестен инструментам искусственного интеллекта). Это стало актуально недавно в связи с задачей Эрдаша № 281, поставленной Эрдашем и Грэмом в 1980 году, которая была недавно решена Нилом Сомани с помощью элегантного аргумента из теории динамических систем. Однако вскоре после того, как было найдено это решение, Коишичан обнаружил, что теорема Роджерса немедленно сводит эту задачу к очень старому результату Дэвенпорта и Эрдаша 1936 года.
Теорема Роджерса является непосредственным следствием двух наблюдений:
Теорема 5 (Теорема Роджерса для циклических групп простого порядка)
Теорема Роджерса верна, когда для некоторой степени простого числа.
Теорема 6 (Теорема Роджерса сохраняется при произведениях)
Если теорема Роджерса верна для двух конечных абелевых групп взаимно простых порядков, то она также верна для их произведения.
В этом случае просто выбирается наибольший из, который имеет тот же размер, что и, и, следовательно, имеет меньшую или равную мощность.
Используя классификацию конечных абелевых групп, теорема Роджерса является непосредственным следствием двух наблюдений.