[Перевод] Деликатные числа. Математики заявили о новом классе простых чисел
Ученые доказали, что существуют особые простые числа, настолько чувствительные, что изменение любой из их цифр превращает такие числа в составные. Однако конкретных примеров исследователи пока не нашли.
Возьмем числа 294 001, 505 447 и 584 141. Заметили в них что-нибудь особенное? Можно догадаться, что все они простые (без остатка делятся только сами на себя и на единицу). Но указанные выше простые числа еще более необычны!
Если вы выберете любую цифру в каждом из этих чисел и измените ее, новое число будет составным и, следовательно, больше не будет являться простым. Изменим, например, цифру 1 в числе 294 001 на 7, и полученное число будет делиться на 7; изменим 1 на 9, и полученное число делится на 3.
Подобные простые числа получили название digitally delicate («чувствительные к замене цифр»), это относительно недавнее математическое открытие. В 1978 году Мюррей Кламкин, математик, а также активный автор и редактор сложных математических задач, увлекся вопросом, существуют ли такие числа. На его вопрос быстро ответил «странствующий математик» Пал Эрдёш, один из самых сильных мастеров по решению задач. Эрдёш доказал, что «чувствительные» простые числа действительно существуют, а также он установил, что таких чисел множество. Полученный Палом результат будет справедлив не только для десятичной, но и для любой другой системы счисления.
С тех пор математики пошли дальше, развив идеи Эрдёша. Среди них и лауреат Филдсовской премии Теренс Тао: в статье 2011 года ученый доказал, что «положительная пропорция» (positive proportion) простых чисел — digitally delicate, то есть чувствительна к замене цифр (для всех систем счисления). Это означает, что интервал между последовательными чувствительными простыми числами практически не меняется — другими словами, простые числа, чувствительные к замене цифр, не будут встречаться реже с их увеличением.
В двух недавних статьях Майкл Филасета из Университета Южной Каролины развил идею дальше, предложив еще более разреженный класс простых чисел, чувствительных к замене цифр.
«Это замечательный результат», — отметил Пол Поллак из Университета Джорджии.
Вдохновленный работами Эрдёша и Тао, Филасета задумался, что произойдет, если добавить бесконечную последовательность нулей в качестве первой части простого числа. Значения чисел 53 и …0000000053 совпадают. Может ли замена любого из этих бесконечных нулей, добавленных к простому числу, автоматически сделать его составным?
Филасета решил назвать такие числа, предполагая, что они существуют, «сильно чувствительными к замене цифр» (widely digitally delicate), и исследовал их свойства в статье, вышедшей в ноябре 2020 года со своим бывшим аспирантом Джеремайей Саутвиком.
Неудивительно, что новое условие затрудняет поиск подобных чисел.»294 001 является чувствительным к замене цифр, но не будет сильно чувствительным, — сказал Поллак, — поскольку, если мы заменим …000 294 001 на …010 294 001, мы получим 10 294 001 — еще одно простое число».
Фактически, Филасета и Саутвик не смогли найти ни одного примера простого числа, сильно чувствительного к замене цифр, в десятичной системе счисления, несмотря на проверку всех целых чисел вплоть до 1 000 000 000. Но это не помешало им сделать несколько убедительных заявлений о подобных, пусть гипотетических, числах.
Во-первых, они показали, что такие числа в десятичной системе счисления действительно возможны, и, более того, их существует бесконечное множество. Ученые пошли дальше и доказали, что положительная пропорция простых чисел сильно чувствительна к замене цифр, так же, как до этого Тао поступил в отношении простых чисел, чувствительных к замене цифр. В докторской диссертации Саутвик достиг тех же результатов для систем счисления, начиная с двоичной и до девятеричной, а также для одиннадцатиричной и тридцатиодноричной.
Поллак был впечатлен результатами. «Мы можем совершать бесконечно много различных операций с этими числами, но, независимо от того, что мы делаем, нам в любом случае вернется составное число», — сказал он.
Майкл Филасета из Университета Южной Каролины помог доказать существование и высокую частоту встречаемости простых чисел, сильно чувствительных к замене цифр. Каждое из них настолько восприимчиво, что изменение любой из их цифр превращает такие числа из простых в составные. На толстовке Майкла Филасеты перечислены первые 20 простых чисел, чувствительных к замене цифр.
Зак Уайт / Университет Южной Каролины
В основе доказательства лежат два инструмента. Первый, использующий понятие «покрывающей системы», был изобретён Эрдёшем в 1950 году для решения другой проблемы теории чисел. «Покрывающая система, — говорит Саутвик, — даёт нам большое количество сегментов, а также гарантирует, что каждое положительное целое число находится хотя бы в одном из этих сегментов». Если, например, вы разделите все положительные целые числа на 2, вы получите два сегмента: один содержит четные числа, в которых остаток равен 0, и другой, содержащий нечетные числа, в которых остаток равен 1. Таким образом, все положительные целые числа были «покрыты», а числа, находящиеся в одном и том же сегменте, считаются «конгруэнтными» друг другу.
Ситуация с простыми числами, сильно чувствительными к замене цифр, конечно, более запутанная. Вам понадобится намного больше сегментов, около 1025 000, и в одном из этих сегментов каждое простое число гарантированно станет составным, если какая-либо из его цифр, включая его начальные нули, будет увеличена.
Сильно чувствительное к замене цифр простое число также должно стать составным, если какая-либо из его цифр уменьшится. Здесь на помощь приходит второй инструмент, — «сито». Теория сита (кстати, появилась еще в Древней Греции) предлагает способ подсчета и оценки для целых чисел, удовлетворяющих определенным свойствам. Филасета и Саутвик использовали подход, аналогичный тому, который использовал Тао в 2011 году, чтобы показать: если вы возьмете простые числа в вышеупомянутом сегменте и уменьшите одну из цифр, положительная пропорция этих простых чисел станет составной. Другими словами, положительная пропорция этих простых чисел сильно чувствительна к замене цифр.
«Теорема Филасеты-Саутвика, — отмечает Поллак, — является красивой и неожиданной иллюстрацией силы покрывающей системы».
В январской статье Филасета и его нынешний аспирант Джейкоб Жуйера сделали еще более поразительное заявление: существуют длинные последовательные ряды простых чисел, каждое из которых сильно чувствительно к замене цифр. Например, можно найти 10 последовательных простых чисел, которые сильно чувствительны к замене цифр. Но для этого вам придется исследовать столько простых чисел, сколько даже нет атомов во Вселенной, утверждает Филасета. Он сравнил этот процесс с выигрышем в лотерею 10 раз подряд: шансы на выигрыш чрезвычайно малы, но все же не нулевые.
Филасета и Жуйера доказали теорему в два этапа. Во-первых, они использовали покрывающие системы, чтобы доказать, что существует сегмент, содержащий бесконечно много простых чисел, все из которых сильно чувствительны к замене цифр.
На втором этапе они применили теорему, доказанную в 2000 году Даниэлем Шиу, чтобы показать, что где-то в списке всех простых чисел существует произвольное количество последовательных простых чисел, содержащихся в этом сегменте. Эти последовательные простые числа в силу того, что они находятся в этом сегменте, обязательно являются сильно чувствительными к замене цифр.
Карлу Померансу из Дартмутского колледжа очень понравились данные статьи, он назвал Филасету мастером в применении покрывающих систем к интригующим задачам теории чисел. Математика может быть не только упражнением с использованием сложных инструментов, а также настоящим развлечением».
В то же время, как отметил Померанс, представление числа в виде его цифр в десятичной системе счисления может быть удобным, но это не имеет отношения к тому, что это за число на самом деле». Он заключает, что существуют более фундаментальные способы представления чисел, например, простые числе Мерсенна — простые числа в виде 2p — 1 для простого числа p.
Филасета согласился. Тем не менее последние статьи поднимают вопросы, которые нам еще предстоит изучить. Филасета интересуется, существуют ли в каждой системе счисления простые числа, сильно чувствительные к замене цифр. Жуйера, со своей стороны, задается вопросом, существует ли «бесконечно много простых чисел, которые становятся составными, если вставить цифру между двумя цифрами, вместо того, чтобы просто заменить цифру».
Еще один мучительный вопрос от Померанса: все ли простые числа в конечном итоге становятся чувствительными к замене цифр либо сильно чувствительными по мере приближения к бесконечности? Ограничено ли количество простых чисел, которые чувствительны к замене цифр (или сильно чувствительны к замене цифр)? Померанс считает, что ответ на этот вопрос, как бы он ни был сформулирован, должен быть отрицательным. Но и Померанс и Филасета считают эти утверждения интригующей гипотезой, которую ни один из них не знает, как доказать, не полагаясь на другую недоказанную гипотезу.
«История математических исследований такова, что нельзя знать заранее, сможете ли вы решить сложную задачу и приведет ли это к чему-то важному, — сказал Померанс. — Ты не можешь определить заранее: сегодня я собираюсь сделать что-то значимое. Хотя, конечно, здорово, когда все складывается именно так».
