Когда Дэниел Ларсен учился в средней школе, он начал разгадывать кроссворды. Ему пришлось совмещать хобби с другими интересами: шахматами, программированием, фортепиано, скрипкой. Он дважды квалифицировался на Национальную орфографическую пчелу Скриппса недалеко от Вашингтона, округ Колумбия, после победы в своем региональном соревновании. «Он на чем-то сосредотачивается, и это просто бах, бах, бах, пока не добьется успеха», — сказала мать Ларсена, Айелет Линденштраус. Его первые кроссворды были отвергнуты крупными газетами, но он продолжал их и в конце концов взломал. На сегодняшний день он держит рекорд для самого молодого человека, чтобы опубликовать кроссворд в The New York Times, 13 лет. «Он очень настойчив, — сказал Линденштраус.
Тем не менее, последняя одержимость Ларсена казалась другой: «длиннее и интенсивнее, чем большинство других его проектов», — сказала она. Более полутора лет Ларсен не мог перестать думать об одной математической задаче.
Это имело корни в более широком вопросе, который математик Карл Фридрих Гаусс считал одним из самых важных в математике: как отличить простое число (число, которое делится только на 1 и само на себя) от составного числа. В течение сотен лет математики искали эффективный способ сделать это. Проблема также стала актуальной в контексте современной криптографии, поскольку некоторые из наиболее широко используемых сегодня криптосистем предполагают выполнение арифметических операций с огромными простыми числами.
Более века назад в поисках быстрого и мощного теста на простоту математики наткнулись на группу нарушителей спокойствия — чисел, которые обманывают тесты, заставляя думать, что они простые, хотя на самом деле таковыми не являются. Эти псевдопростые числа, известные как числа Кармайкла, было особенно трудно понять. Только в середине 1990-х, например, математики доказали, что их бесконечно много. Возможность сказать что-то еще о том, как они распределяются по числовой прямой, представляет собой еще более сложную задачу.
Затем появился Ларсен с новое доказательство именно об этом, вдохновленном недавней эпохальной работой в другой области теории чисел. В то время ему было всего 17.
Искра
Выросший в Блумингтоне, штат Индиана, Ларсен всегда увлекался математикой. Его родители, оба математики, познакомили его и его старшую сестру с этим предметом, когда они были маленькими. (Сейчас она получает докторскую степень по математике.) Когда Ларсену было 3 года, вспоминает Линденштраус, он начал задавать ей философские вопросы о природе бесконечности. «Я думал, у этого парня математический склад ума», — сказал Линденштраус, профессор Университета Индианы.
Затем несколько лет назад — примерно в то время, когда он был погружен в свои проекты по правописанию и кроссвордам — он наткнулся на документальный фильм в отношении Ийтанг Чжан, неизвестный математик, восставший из безвестности в 2013 году после Доказательство знакового результата которые устанавливают верхнюю границу промежутков между последовательными простыми числами. Что-то щелкнуло в Ларсене. Он не мог перестать думать о теории чисел и о родственной проблеме, которую Чжан и другие математики все еще надеялись решить: гипотезе о простых числах-близнецах, которая утверждает, что существует бесконечно много пар простых чисел, отличающихся всего на 2.
После работы Чжана, которая показала, что существует бесконечно много пар простых чисел, отличающихся менее чем на 70 миллионов, другие вскочили чтобы еще больше понизить эту границу. В течение нескольких месяцев математики Джеймс Мейнард и Теренс Тао независимо доказали еще более сильное утверждение о промежутках между простыми числами. С тех пор этот разрыв сократился до 246.
Ларсен хотел понять кое-что из математики, лежащей в основе работы Мейнарда и Тао, «но для меня это было почти невозможно», — сказал он. Их документы были слишком сложными. Ларсен попытался прочитать родственную работу, но тоже нашел ее неразборчивой. Он продолжал, перескакивая с одного результата на другой, пока, наконец, в феврале 2021 года не наткнулся на статью, которая показалась ему красивой и понятной. Его тема: числа Кармайкла, эти странные составные числа, которые иногда могут выдавать себя за простые.
Все, кроме Прайма
В середине 17 века французский математик Пьер де Ферма написал письмо своему другу и доверенному лицу Френиклю де Бесси, в котором он изложил то, что позже стало известно как его «маленькая теорема». Если N является простым числом, то bN – b всегда кратно N, не важно что b является. Например, 7 — простое число, поэтому 27 – 2 (что равно 126) кратно 7. Аналогично, 37 – 3 кратно 7 и так далее.
Математики увидели потенциал идеальной проверки того, является ли данное число простым или составным. Они знали, что если N простое, bN – b всегда кратно N. Что, если верно и обратное? То есть, если bN – b это кратное N для всех значений b, должен N быть премьером?
Увы, оказалось, что в очень редких случаях N может удовлетворять этому условию и оставаться составным. Наименьшее такое число равно 561: для любого целого числа b, b561 – b всегда кратно 561, даже если 561 не простое число. Подобные числа были названы в честь математика Роберта Кармайкла, которому часто приписывают публикацию первого примера в 1910 году (хотя чешский математик Вацлав Шимерка независимо открыл примеры в 1885 году).
Математики хотели лучше понять эти числа, которые так сильно напоминают самые фундаментальные объекты теории чисел — простые числа. Оказалось, что в 1899 году — за десять лет до результата Кармайкла — другой математик, Алвин Корселт, предложил эквивалентное определение. Он просто не знал, есть ли какие-либо числа, которые соответствуют всем требованиям.
По критерию Корсельта число N является числом Кармайкла тогда и только тогда, когда оно удовлетворяет трем свойствам. Во-первых, оно должно иметь более одного простого множителя. Во-вторых, ни один простой множитель не может повторяться. И в-третьих, для каждого простого p это делит N, p - 1 тоже делит N – 1. Рассмотрим еще раз число 561. Оно равно 3 × 11 × 17, поэтому явно удовлетворяет первым двум свойствам в списке Корсельта. Чтобы показать последнее свойство, вычтите 1 из каждого простого множителя, чтобы получить 2, 10 и 16. Кроме того, вычтите 1 из 561. Все три меньших числа являются делителями 560. Таким образом, число 561 является числом Кармайкла.
Хотя математики подозревали, что существует бесконечно много чисел Кармайкла, их относительно мало по сравнению с простыми числами, что затрудняло их определение. Затем в 1994 году Рэд Алфорд, Эндрю Грэнвилл и Карл Померанс опубликовал прорыв бумаги в котором они окончательно доказали, что таких псевдопростых чисел действительно бесконечно много.
К сожалению, разработанные ими методы не позволили им ничего сказать о том, как выглядели эти числа Кармайкла. Появились ли они группами вдоль числовой линии с большими промежутками между ними? Или вы всегда можете найти число Кармайкла за короткий промежуток времени? «Можно подумать, что если вы сможете доказать, что их бесконечно много, — сказал Грэнвиль, — вы наверняка сможете доказать, что между ними нет больших промежутков, что они должны быть относительно хорошо разнесены».
В частности, он и его соавторы надеялись доказать утверждение, отражающее эту идею, что при достаточно большом числе X, всегда будет число Кармайкла между X и 2X. «Это еще один способ показать, насколько они вездесущи», — сказал Джон Грэнтэм, математик из Института оборонного анализа, проделавший похожую работу.
Но на протяжении десятилетий никто не мог это доказать. Методы, разработанные Алфордом, Грэнвилем и Померансом, «позволили нам показать, что чисел Кармайкла должно быть много, — сказал Померанс, — но на самом деле не дали нам полного контроля над тем, где они будут находиться. ”
Затем, в ноябре 2021 года, Грэнвилл открыл электронное письмо от Ларсена, которому тогда было 17 лет и который учился в старшей школе. А бумаги был прикреплен — и, к удивлению Гранвиля, он выглядел правильно. «Это было не самое легкое чтение, — сказал он. «Но когда я прочитал это, было совершенно ясно, что он не бездельничал. У него были блестящие идеи».
Померанс, прочитавший более позднюю версию произведения, согласился. «Его доказательство действительно весьма продвинуто», — сказал он. «Это была бы статья, написанием которой гордился бы любой математик. А вот это старшеклассник пишет».
Ключом к доказательству Ларсена была работа, которая в первую очередь привлекла его к числам Кармайкла: результаты Мейнарда и Тао о простых промежутках.
Маловероятно — возможно
Когда Ларсен впервые задался целью показать, что число Кармайкла всегда можно найти за короткий промежуток времени, «казалось, что это так очевидно, что как трудно это доказать?» он сказал. Он быстро понял, что это действительно может быть очень трудно. «Это проблема, которая проверяет технологии нашего времени», — сказал он.
В своей статье 1994 года Алфорд, Грэнвиль и Померанс показали, как создать бесконечное множество чисел Кармайкла. Но они не могли контролировать размер простых чисел, которые использовали для их построения. Это то, что Ларсен должен был сделать, чтобы построить числа Кармайкла, которые были бы относительно близки по размеру. Сложность проблемы беспокоила его отца, Майкла Ларсена. «Я не думал, что это невозможно, но я думал, что у него вряд ли получится», — сказал он. «Я видел, сколько времени он тратил на это… и я чувствовал, что для него будет опустошительно, если он отдаст этому так много всего и не получит».
Тем не менее, он знал, что лучше не пытаться отговорить сына. «Когда Дэниел занимается чем-то, что его действительно интересует, он остается с этим несмотря ни на что», — сказал он.
Поэтому Ларсен вернулся к работам Мейнарда — в частности, к работе, показывающей, что если взять определенную последовательность из достаточного количества чисел, то некоторое подмножество этих чисел должно быть простым. Ларсен модифицировал методы Мейнарда, чтобы объединить их с методами, используемыми Алфордом, Грэнвилем и Померансом. Это позволило ему гарантировать, что простые числа, которые он получил, будут различаться по размеру — достаточно, чтобы получить числа Кармайкла, которые попадут в нужные ему интервалы.
«У него больше контроля над вещами, чем у нас когда-либо», — сказал Грэнвилл. И он достиг этого за счет особенно умного использования работы Мейнарда. «Нелегко… использовать этот прогресс на коротких промежутках между простыми числами», — сказал Кайса Матомяки, математик из Университета Турку в Финляндии. «Очень хорошо, что он смог совместить это с вопросом о числах Кармайкла».
На самом деле аргумент Ларсена не просто позволил ему показать, что число Кармайкла всегда должно находиться между X и 2X. Его доказательство работает и для гораздо меньших интервалов. Теперь математики надеются, что это также поможет раскрыть другие аспекты поведения этих странных чисел. — Это другая идея, — сказал Томас Райт, математик из колледжа Уоффорд в Южной Каролине, работающий с псевдопростыми числами. «Это многое меняет в том, как мы можем доказать что-то о числах Кармайкла».
Грэнтэм согласился. «Теперь вы можете делать то, о чем никогда не думали», — сказал он.
Тем временем Ларсен только начал свой первый год обучения в Массачусетском технологическом институте. Он не уверен, над какой проблемой он может работать дальше, но ему не терпится узнать, что там есть. «Я просто посещаю курсы… и стараюсь быть непредубежденным», — сказал он.
«Он сделал все это без высшего образования», — сказал Грэнтэм. «Я могу только представить, что он собирается придумать в аспирантуре».
