26-летний Джаред Дукер Лихтман доказал гипотезу, которая связывает простые числа с широким классом «примитивных» множеств. Для его научного руководителя это стало «настоящим шоком». Подробности рассказываем к старту флагманского курса по Data Science.

Примитивные множества — это последовательности чисел, в которых ни одно число не может делить любое другое число. Простые числа в этом универсуме множеств уникальны.

Простые числа — атомы арифметики — всегда занимали на числовой прямой особое место. Джаред Дюкер Лихтман, 26-летний аспирант Оксфордского университета, разрешил известную гипотезу, нашёл ещё одну грань особого места простых чисел. И, в некотором смысле, даже самое подходящее место. «Это даёт вам более широкий контекст, позволяющий увидеть, чем простые числа неповторимы и как они соотносятся со вселенной множеств, которые больше», — рассказывает он.

Гипотеза имеет дело с примитивными множествами — это последовательности чисел, в которых ни одно число не делится на другое. Каждое простое число делится только на 1 и само на себя, а потому множество всех простых чисел — пример примитивного множества. То же самое можно сказать и о множестве всех чисел, имеющих ровно два, три или 100 простых делителей.

Примитивные множества в 1930-х годах ввёл математик Пал Эрдёш. В то время эти множества стали инструментом, который облегчил доказательство, касающееся совершенных чисел. Но примитивные множества быстро превратились в самостоятельный предмет интереса. Снова и снова Эрдёш будет возвращаться к этим множествам.

Хотя их определение достаточно прямолинейно, примитивные множества оказались по-настоящему странными. Странность эту можно понять, если задать вопрос о том, насколько большим может быть примитивное множество. Рассмотрим множество всех целых чисел до 1000. Все числа от 501 до 1000 (половина набора) образуют примитивное множество: ни одно число не делится ни на какое другое. Таким образом, примитивные множества могут составлять изрядную часть числовой прямой. Но другие примитивные множества, такие как последовательность всех простых чисел, невероятно разрежены. «Это свидетельствует о том, что примитивные множества на самом деле представляют очень широкий класс, до которого трудно добраться напрямую», — рассказывает Лихтман.

В попытке уловить интересные свойства множеств математики изучают различные понятия размера. Например, вместо подсчёта количества чисел множества они могут сделать следующее: каждое число n подставить его в выражение 1/(n log n) и сложить все результаты. Тогда размер множества {2, 3, 55} равен 1/(2 log 2) + 1/(3 log 3) + 1/(55 log 55).

Эрдёш обнаружил, что для любого примитивного множества, включая бесконечное, эта сумма — «сумма Эрдёша» — всегда конечна. Как бы ни выглядело примитивное множество, сумма Эрдёша для него всегда меньше или равна некоторому числу. А поэтому, хотя эта сумма «выглядит, по крайней мере на первый взгляд, совершенно чуждой [множеству] и расплывчатой», рассказывает Лихтман, она в некотором смысле «управляет частью хаоса примитивных множеств», а это делает её подходящим мерилом.

Естественным образом возникает следующий вопрос: какова предельная Эрдёша? Эрдёш предположил, что это число — около 1,64. Таким образом, простые числа — это своего рода крайность.

Джаред Дукер Лихтман назвал этот вопрос своим «постоянным спутником на протяжении последних четырёх лет».

За десятилетия математики частично продвинулись к доказательству. Они доказали, например, что гипотеза верна для определённых типов примитивных множеств.

Тем не менее «было ощущение, что мы не были так уж близки к этому до того, как Джаред начал свою работу», — рассказал Грег Мартин, математик из Университета Британской Колумбии, который работал над смежными задачами. 

С этим согласен Андрас Соркази, математик Будапештского университета и частый партнёр Эрдёша по работе. 

«Конечно, это казалось недосягаемым», — поделился он.

Лихтман начал работать над гипотезой о примитивных множествах в 2018 году, когда учился на последнем курсе Дартмутского колледжа. «Меня сразу же заинтересовал этот вопрос. Просто было крайне загадочно, как что-то подобное может быть правдой, — рассказывает он. — Задача была моим постоянным спутником последние четыре года».

В 2019 году он и Карл Померанс, его советник в Дартмуте (который, по словам Лолы Томпсон, математика из Утрехтского университета и бывшей студентки Померанса, вернулся на работу, чтобы работать с ним), обнаружил, что сумма Эрдёша примитивного множества не может быть больше, чем около 1,78. «Это недалеко, — сказал Мартин.  — примерно на 10% больше, чем в гипотезе для простых чисел».

Лихтман и Померанс получили эту константу, когда связали новую последовательность кратных чисел с каждым числом в данном примитивном множестве. Снова посмотрим на примитивное множество {2, 3, 55}. С числом 2 связана последовательность всех чётных чисел. С числом 3 — все числа, кратные 3, но не кратные 2. А с числом 55 (5 × 11) будут связаны все числа, кратные 55, такие, что наименьший простой множитель множителя — число, на которое умножается 55, — равен 11. Таким образом, исключены все множители, делящиеся на 2, 3, 5 и 7. Лихтман сравнивает это с тем, как слова индексируются в словаре — только для организации каждой последовательности вместо букв используются простые числа.

Лихтман и Померанс подумали о том, насколько «плотны» эти последовательности кратных, то есть какую часть числовой последовательности они занимают. Например, последовательность всех чётных чисел имеет плотность 1/2: чётные числа составляют половину всех чисел. Математики заметили, что если бы исходное множество было примитивным, то связанные с ним последовательности кратных чисел не перекрывались бы, а потому их общая плотность была бы не больше 1 (плотности всех целых).

Это наблюдение имеет значение, потому что теорема математика Франца Мертенса из XIX века позволила Лихтману и Померансу по-новому интерпретировать сумму Эрдёша примитивного множества, то есть в терминах этих плотностей. Согласно теореме Мертенса, специальная константа (равная приблизительно 1,78) при умножении на член, эквивалентный объединённым плотностям этих кратных, даёт максимальное значение суммы Эрдёша для примитивного множества. А поскольку общая плотность не превышала 1, Лихтман и Померанс доказали, что сумма Эрдёша примитивного множества не превышает 1,78.

«Это был вариант исходных идей Эрдёша, а также изящный, аккуратный способ… получить неточную, но не слишком уж плохую верхнюю границу», — рассказывает Джеймс Мейнард, математик в Оксфорде.

Нескольких лет математикам казалось: это — лучшее, что они могут сделать. Не было понятно, как снизить этот предел до 1,64. Тем временем Лихтман закончил учёбу и переехал в Оксфорд, чтобы получить докторскую степень у Мейнарда, где он в основном работал над другими задачами, также связанными с простыми числами.

«Я знал, что он довольно много думал об этой задаче, — рассказывает Мейнард, — но это был полный шок, когда он ни с того ни с сего пришёл к законченному доказательству».

Лихтман первым понял, что для чисел с относительно небольшими простыми множителями его более ранний аргумент с Померансом всё ещё может работать: относительно просто было показать, что в этом случае константу 1,78 можно уменьшить до значительно меньшего значения в 1,64.

Но числа с относительно большими простыми множителями (в каком-то смысле «близкие» к простым) — это совсем другая история. Чтобы справиться с ними, Лихтман нашёл способ связать с каждым числом не одну, а несколько последовательностей кратных чисел. Как и прежде, суммарная плотность всех этих последовательностей не превышала 1. Но на этот раз, по словам Лихтмана, «эти другие множители растут, как сорняки, и захватывают часть пространства».

Возьмём число 618 (2×3×103). Как правило, связать с ним можно все числа, кратные 618, так что наименьшая фабрика простых чисел множителя — 103. Но последовательности можно построить при помощи некоторых меньших простых множителей, которые были опущены. Например, последовательность может состоять из всех исходных множителей, а также допускать кратные 618, где множитель делится на 5. Здесь некоторые ограничения определяют, какие меньшие простые множители можно использовать.

Наличие этих дополнительных кратных означало, что общая плотность исходных кратных — величина, которая используется в теореме Мертенса. — на самом деле меньше 1. И Лихтман нашёл способ точнее определить, какой может быть эта плотность.

Затем он с осторожностью определил то, как может выглядеть наихудший сценарий для примитивного множества: какой баланс он сможет дать между числами с большими простыми множителями и числами с малыми простыми множителями. Соединив две части своего доказательства, он смог показать, что сумма Эрдёша в этой ситуации даёт значение меньше 1,64.

«Это числовой момент истины, — считает Мейнард. — Я не знаю, удача это или просто факт численной достаточности».

В феврале Лихтман опубликовал своё доказательство в Интернете. Математики отметили, что работа особенно поразительна, поскольку полностью опирается на элементарные рассуждения. «Не то чтобы он [Лихтман] ждал, пока раскрутится весь этот сумасшедший механизм, — рассказывает Томпсон. — У него просто были очень разумные идеи».

Эти идеи закрепили за простыми числами исключительное положение среди примитивных множеств: их сумма Эрдёша властвует безраздельно. «Все мы думаем о простых числах как о чём-то особенном, — сказал Померанс. — И это только добавляет им блеска».

А пока простые числа продолжают проявлять себя, мы поможем прокачать ваши навыки или с самого начала освоить профессию, актуальную в любое время:

• Профессия Data Scientist

• Профессия Fullstack-разработчик на Python

Выбрать другую востребованную профессию.