Как двое аутсайдеров разгадали тайну арифметических прогрессий

Рассмотрите эту последовательность чисел: 5, 7, 9. Сможете ли вы заметить закономерность? Вот еще один по такому же рисунку: 15, 19, 23. Еще один: 232, 235, 238.  

«Три равноотстоящие друг от друга вещи», — говорит Рагху Мека, ученый-компьютерщик из Калифорнийского университета в Лос-Анджелесе. «Это, наверное, самая простая модель, которую вы можете себе представить».  

Однако уже почти столетие математики в области комбинаторики ломают голову над тем, как узнать, содержит ли бесконечный список чисел такую ​​последовательность, называемую арифметической прогрессией. Другими словами, есть ли способ быть математически уверенным, что набор содержит последовательность из трех или более чисел, расположенных на равном расстоянии друг от друга, даже если вы мало что знаете о том, как были выбраны числа в наборе или какова может быть последовательность? 

Прогресс в этом вопросе был медленным, даже медленным. Но в прошлом году Мека и Зандер Келли, доктор философии. Студент информатики Университета Иллинойса Урбана-Шампейн удивил математиков, совершив экспоненциальный скачок . Исследователи являются аутсайдерами в комбинаторике, которая занимается подсчетом конфигураций чисел, точек или других математических объектов. И этот дуэт не собирался разгадывать тайну арифметической прогрессии.  

Вместо этого Келли и Мека исследовали абстрактные игры в области информатики. Пара искала математический инструмент, который мог бы помочь им понять, как лучше всего снова и снова выигрывать в определенном типе игры. «Меня очень интересует набор методов, подпадающих под категорию «структура против случайности», — говорит Келли. Некоторые из самых ранних достижений в области арифметических прогрессий основывались на таких методах, и именно это побудило Келли и Меку углубиться в эту тему. 

Тайна появления арифметических прогрессий — лишь один из многих математических вопросов, связанных с порядком и беспорядком в наборах объектов. Понимание порядка – а также того, когда и где должны возникать закономерности – является постоянной темой во многих областях математики и информатики.  

Другой пример порядка в объектах гласит, что любая группа из шести человек должна содержать либо группу из не менее трёх общих знакомых (все трое знают друг друга), либо группу из не менее трёх совершенно незнакомых людей (никто другого не знает). Исследования показали, что не имеет значения, кто они, откуда они или как они были выбраны. Есть что-то мощное, может быть, даже пугающее в том факте, что мы можем говорить это — и делать другие подобные утверждения о структуре множеств — с математической уверенностью . 

Разгадка тайны арифметических прогрессий может открыть двери для исследования более сложных отношений между числами в наборе — например, пробелов, которые изменяются более сложным образом. «Это более сложные версии тех же теорем», — говорит Брина Кра, математик из Северо-Западного университета в Эванстоне, штат Иллинойс. «Обычно, когда вы видите арифметическую прогрессию… вы видите другие закономерности».  

После публикации своей работы по арифметическим прогрессиям Келли и Мека вместе с Шахаром Ловеттом из Калифорнийского университета в Сан-Диего импортировали методы своих исследований арифметических прогрессий в другой контекст. Исследователи решили вопрос сложности коммуникации — раздела теоретической информатики, занимающегося эффективной передачей данных между сторонами, обладающими лишь частичной информацией. 

Более того, знание того, что определенные математические структуры должны появляться в определенных ситуациях, может быть полезно в реальных сетях связи и для сжатия изображений. 

Помимо потенциальных приложений, исследователи, изучающие арифметические прогрессии – или другие аспекты чисто теоретической математики – часто мотивированы скорее чистым любопытством, чем какой-либо практической выгодой. Тот факт, что вопросы о таких простых закономерностях и о том, когда они появляются, по большей части остаются без ответа, для многих является достаточной причиной, чтобы заняться ими. 

Что такое арифметические прогрессии? 

Давайте на минутку возьмем в руки некоторые наборы чисел и арифметические прогрессии, содержащиеся в этих наборах, начиная с простых чисел, извечных фаворитов энтузиастов математики . Простое число — это любое целое число, которое делится только на себя и на 1; первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Внутри этих чисел мы можем найти несколько арифметических прогрессий. Числа 3, 5 и 7 образуют трехчленную арифметическую прогрессию с интервалом два. Но числа в прогрессии не обязательно должны следовать друг за другом сразу в пределах большего набора: числа 5, 11, 17, 23 и 29 образуют пятичленную арифметическую прогрессию с интервалом в шесть. 

Внутри конечного набора чисел несложно определить, существуют ли арифметические прогрессии. В зависимости от съемочной площадки это может быть утомительно, но в этом нет ничего загадочного. Однако для бесконечных наборов чисел вопрос становится интересным.  

Простые числа продолжаются вечно, и математики задавали множество вопросов (и на некоторые отвечали) об арифметических прогрессиях внутри них. Существует ли максимально длинная арифметическая прогрессия, ограничение на количество членов в простых числах? Или, если смотреть достаточно долго, сможете ли вы найти прогрессию любой конечной длины? В 2004 году математики доказали, что последнее верно . Но вопросы, в том числе о том, как далеко вдоль числовой линии нужно заглянуть, чтобы найти арифметическую прогрессию с заданным количеством членов или заданным размером пробела, остаются активными областями исследований как для простых чисел, так и для других множеств. 

Простые числа содержат бесконечное множество арифметических прогрессий, но некоторые бесконечные множества не содержат ни одной. Рассмотрим степени 10: 1, 10, 100, 1000…. Промежутки между последовательными сроками быстро увеличиваются — 9, 90, 900…. И ни один из них не похож на другой. Немного поиграв с числами, вы сможете убедиться, что никакие две степени 10, последовательные или нет, не имеют такого же разрыва, как любая другая пара. 

В этом контексте мы теперь подходим к вопросу, лежащему в основе нашего исследования: почему в некоторых множествах есть арифметическая прогрессия, а в других нет? Одна большая разница между простыми числами и степенями 10 заключается в том, что простых чисел гораздо больше, чем степеней 10. Вроде того. Оба набора бесконечны, но если вы выберете любое произвольное число в качестве порогового значения и посмотрите, сколько простых чисел или степеней 10 окажется ниже этого числа, простые числа каждый раз выиграют. Существует четыре простых числа от 1 до 10, а не только две степени 10. Существует 25 простых чисел от 1 до 100 и только три степени 10. Простые числа не просто выигрывают каждый раз, они выигрывают с большим преимуществом, и количество они выигрывают, продолжая расти. Таким образом, простые числа «плотнее» — в интуитивном и техническом смысле — чем степени 10.  

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

Плотность в бесконечных множествах

Всерьез изучение арифметических прогрессий в наборах целых чисел началось в 1936 году, когда венгерские математики Пауль Эрдеш и Пал Туран предположили, что любой достаточно плотный набор целых чисел должен содержать арифметические прогрессии любой желаемой длины. 

Для конечных множеств легко понять, что такое плотность. В наборе целых чисел от 1 до 10 плотность простых чисел составляет 4/10, или 0,4. Но если мы хотим понять плотность всего бесконечного набора простых чисел внутри всего бесконечного набора целых чисел, нам нужно найти способ понять смысл бесконечности, разделенной на бесконечность, или ∞/∞.  

Простые числа содержат бесконечное множество арифметических прогрессий, но некоторые бесконечные множества не содержат ни одной. Рассмотрим степени 10: 1, 10, 100, 1000…. Промежутки между последовательными сроками быстро увеличиваются — 9, 90, 900…. И ни один из них не похож на другой. Немного поиграв с числами, вы сможете убедиться, что никакие две степени 10, последовательные или нет, не имеют такого же разрыва, как любая другая пара. 

В этом контексте мы теперь подходим к вопросу, лежащему в основе нашего исследования: почему в некоторых множествах есть арифметическая прогрессия, а в других нет? Одна большая разница между простыми числами и степенями 10 заключается в том, что простых чисел гораздо больше, чем степеней 10. Вроде того. Оба набора бесконечны, но если вы выберете любое произвольное число в качестве порогового значения и посмотрите, сколько простых чисел или степеней 10 окажется ниже этого числа, простые числа каждый раз выиграют. Существует четыре простых числа от 1 до 10, а не только две степени 10. Существует 25 простых чисел от 1 до 100 и только три степени 10. Простые числа не просто выигрывают каждый раз, они выигрывают с большим преимуществом, и количество они выигрывают, продолжая расти. Таким образом, простые числа «плотнее» — в интуитивном и техническом смысле — чем степени 10.  

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

Плотность в бесконечных множествах

Всерьез изучение арифметических прогрессий в наборах целых чисел началось в 1936 году, когда венгерские математики Пауль Эрдеш и Пал Туран предположили, что любой достаточно плотный набор целых чисел должен содержать арифметические прогрессии любой желаемой длины. 

Для конечных множеств легко понять, что такое плотность. В наборе целых чисел от 1 до 10 плотность простых чисел составляет 4/10, или 0,4. Но если мы хотим понять плотность всего бесконечного набора простых чисел внутри всего бесконечного набора целых чисел, нам нужно найти способ понять смысл бесконечности, разделенной на бесконечность, или ∞/∞.

В 1930-х годах венгерские математики Пауль Эрдеш (слева) и Пал Туран (справа) предположили, что любой достаточно плотный набор чисел должен содержать арифметическую прогрессию.

Математики используют концепцию, называемую асимптотической плотностью, чтобы спорить с плотностью бесконечного набора целых чисел. Основная идея состоит в том, чтобы выбрать некоторое число в качестве точки отсечения N и посмотреть, что произойдет при увеличении N. Если плотность стремится к некоторому фиксированному числу, это асимптотическая плотность множества.  

Вернемся к степеням 10, плотность которых убывает поперек числовой прямой. По мере того, как вы продвигаетесь все дальше и дальше, доля целых чисел, являющихся степенями 10, приближается к нулю — поэтому асимптотическая плотность набора равна нулю. Другие множества имеют положительную асимптотическую плотность, а некоторые вообще никогда не достигают асимптотической плотности.  

Эрдеш и Туран предложили, что любой набор чисел с положительной, а не нулевой асимптотической плотностью должен содержать хотя бы одну арифметическую прогрессию. Для некоторых множеств это очевидно (четные числа имеют асимптотическую плотность 0,5 и обязательно содержат арифметические прогрессии). Но доказать это для любого произвольного набора чисел оказалось непростой задачей. 

Лишь в 1953 году немецко-британский математик Клаус Рот доказал эту гипотезу, открыв дверь к более тонкому пониманию роли плотности в арифметических прогрессиях. Он показал, что любой набор с положительной асимптотической плотностью должен содержать хотя бы одну трехчленную арифметическую прогрессию , или 3-AP. Его аргумент основывался на доказательстве того, что достаточно плотные псевдослучайные множества — те, которые на самом деле не могут быть выбраны случайно, но обладают общими свойствами случайных множеств — должны содержать арифметические прогрессии. Затем он разработал способ увеличения частей непсевдослучайных наборов и показал, что, если исходный набор достаточно плотен, эти увеличенные области должны быть структурированы таким образом, чтобы гарантировать наличие арифметической прогрессии.  

В начале 2021 года Келли и Мека исследовали проблему теории сложности, называемую параллельным повторением игр. Не думайте о «Монополии» или шахматах; «игры», о которых думали исследователи, в ближайшее время не принесут Hasbro денег. «У нас есть тенденция называть игрой все, что есть ходы», — говорит Келли. В типичных играх, которые рассматривали Келли и Мека, игроки имеют доступ к различной информации и должны работать вместе, чтобы найти ответ на вопрос. Но они не могут общаться во время игры, поэтому им необходимо заранее определиться со стратегией. Келли и Мека стремились определить, как максимизировать шансы игроков на победу во многих играх подряд. 

Это не совсем прыжок от параллельного повторения игр к арифметическим прогрессиям, но Келли и Мека справились с этим довольно быстро. «Может быть, через месяц мы столкнулись с проблемой 3-AP», — говорит Мека. В предыдущих исследованиях параллельного повторения игр использовались аргументы в пользу структуры и случайности. Поскольку работа Рота по арифметическим прогрессиям была первой, в которой использовалась такая техника, Келли и Мека заинтересовались этой работой в ее первоначальной среде обитания. 

«В теоретической информатике люди ищут в математике какие-то инструменты, которые они могли бы использовать, и если вы не готовы навлечь на себя какие-то серьезные проблемы, обычно вы смотрите, можете ли вы использовать эти инструменты, а затем, можете ли вы» «Ну, иди дальше», — говорит Келли. «Вы не пытаетесь открыть их и посмотреть, какие они». Но он и Мека так и сделали, зная, что могут провалиться в глубокую кроличью нору и в конечном итоге не получить ничего, что можно было бы отдать за потраченное время и усилия. Они углубились в аргументы Рота, а также в более поздние исследования по той же теме, чтобы посмотреть, смогут ли они продвинуть работу дальше. И вот они обнаружили, что смотрят на арифметические прогрессии. 

Достижение новых пределов 

Вклад Рота был более весомым, чем просто показ того, что любое множество с положительной асимптотической плотностью должно содержать 3-AP. Он также доказал, что некоторые множества с асимптотической плотностью, равной нулю, если плотность стремится к нулю достаточно медленно при выходе вдоль числовой прямой, также должны содержать хотя бы один 3-АП.  

Думайте о плотности как о необходимости пройти под полосой неопределенности. Если набор становится разреженным слишком медленно, он не сможет его преодолеть и должен содержать арифметическую прогрессию. Но множество, плотность которого приближается к нулю, достаточно быстро ныряет под воду. Для этого набора подойдет все что угодно: такая прогрессия может быть, а может и не быть. 

Первоначальное доказательство Рота выявило верхний предел того, где должна находиться полоса неопределенности. Он показал, что любой набор, плотность которого приближается к нулю со скоростью, аналогичной выражению 1/log(log(N)) или меньшей, должен содержать хотя бы одну арифметическую прогрессию. Log означает логарифмирование, и помните, что N — это число, выбранное в качестве произвольного отсечения в бесконечном множестве. Мы рассматриваем, что происходит при увеличении N.  

Логарифмы растут медленно, примерно так же, как количество цифр в числе. Логарифм 1 равен нулю, 10 — 1, 100 — 2, 1000 — 3 и так далее. Но логарифмирование этих логарифмов дает гораздо более вялый рост. Чтобы подтолкнуть log(log(N)) от нуля до 1, нам нужно переместить N с 10 до 10 миллиардов. Разделив 1 на этот двойной логарифм, как показано в работе Рота, мы получим плотность, которая постепенно приближается к нулю. 

Несколькими годами ранее, в 1946 году, математик Феликс Беренд исследовал нижний предел полосы неопределенности. Он разработал рецепт создания наборов без 3-AP, показав, что любой такой набор действительно должен быть чрезвычайно разреженным. Его пределом была плотность, которая стремится к нулю примерно с той же скоростью, что и 1/e ^{(log(N))^½} . Это выражение может показаться вам незнакомым, но в знаменателе есть показательная функция. Логарифм и степень ½ немного замедляют процесс, но все выражение стремится к нулю гораздо быстрее, чем двойной логарифм, который позже обнаружил Рот. 

В последние несколько десятилетий исследователи пытались сократить разрыв между оценками в стиле Рота для самых разреженных множеств, которые должны содержать 3-AP, и оценками в стиле Беренда для самых плотных множеств, которые его не содержат. В 2020 году математики Томас Блум из Оксфордского университета и Олоф Сисаск из Стокгольмского университета преодолели то, что стало известно как логарифмический барьер для верхнего предела лимбо-бара в стиле Рота, показав, что любое множество с плотностью, достигающей ноль медленнее, чем 1/log(N), должен содержать хотя бы один 3-AP. Работа была расценена как прорыв в этой области, хотя верхний предел все же был ближе к предыдущему, самому известному верхнему пределу, чем к нижнему пределу Беренда.  

Келли и Мека резко снизили верхний предел. Их результатом стала скорость, которая стремится к нулю примерно с той же скоростью, что и 1/e ^{(log(N))^1/11} . Эта формула очень похожа на нижний предел Беренда. Впервые верхний и нижний пределы находятся на расстоянии выстрела друг от друга. Закрытие этого пробела позволит выявить конкретное расположение полосы неопределенности и, таким образом, даст четкий ответ на то, какие наборы должны содержать хотя бы один 3-AP. 

Направлялся к нулю

То, насколько быстро плотность набора приближается к нулю по мере продвижения вдоль числовой линии (вставки), может показать, должен ли этот набор содержать арифметическую прогрессию. В 2023 году ученые-компьютерщики Зандер Келли и Рагху Мека показали, что если плотность приближается к нулю со скоростью, примерно такой же или меньшей, чем черная линия выше, набор должен содержать прогрессию. Этот верхний предел значительно ниже «логарифмического барьера» (пройденного в 2020 году и показанного красным), но он все еще далек от нижнего предела (определенного Феликсом Берендом несколько десятилетий назад).

Верхний и нижний пределы для наборов, содержащих арифметическую прогрессию.

Что дальше? 

Когда Келли и Мека приступили к решению проблемы 3-AP, они думали, что им, вероятно, придется просто покопаться в поисках препятствий на пути перемещения верхнего предела вниз. Год спустя они оба писали статью о своем прорыве. «Я думаю, что одна вещь, которая поддерживала нас, — это то, что мы никогда не чувствовали, что мы полностью упираемся в стену», — говорит Мека. «Всегда казалось, что мы либо учимся чему-то полезному, либо действительно добиваемся прогресса».  

Мека описывает свой общий подход, основанный на ранних методах Рота, как использование «желаемой дихотомии» между случайностью и структурой. Для своей работы они разработали определение псевдослучайности и показали, что для этого определения любой достаточно плотный псевдослучайный набор должен содержать хотя бы одну арифметическую прогрессию. 

Обработав псевдослучайный случай, команда рассмотрела более структурированные наборы чисел и показала, что эти наборы тоже должны демонстрировать желаемые закономерности. Наконец, Келли и Мека расширили наборы этих типов до всех достаточно больших наборов чисел, доказав, что эти наборы должны обладать свойствами либо псевдослучайных, либо структурированных наборов.  

Самое примечательное в работе Келли и Меки то, что им удалось добиться такого впечатляющего прогресса, не разрабатывая нового подхода к арифметическим прогрессиям. Хотя они принесли новые идеи и установили новые связи с предыдущей работой, они не создали нового оборудования.  

«Продвигать эти методы казалось совершенно невыполнимым, — говорит Сисаск, — пока эта статья Келли и Меки не попала в мой почтовый ящик». Он и Блум, ранее преодолевшие логарифмический барьер, «потратили некоторое время на то, чтобы переварить статью и поговорить о ней, пока не поняли ее на своем родном языке», — говорит он.  

Математики и ученые-компьютерщики склонны использовать разные обозначения и терминологию, но Сисаск, Блум и другие эксперты в этой области быстро признали работу надежной. Усвоив аргументы, Сисаск и Блум написали объяснение работы с некоторыми тонкими техническими улучшениями, ориентированное на других исследователей комбинаторики. Несколько месяцев спустя команда еще немного снизила верхний предел , получив новую границу 1/e ^{(log(N))^1/9} . 

Исследователи комбинаторики все еще пытаются выяснить, насколько низко они могут опуститься. Смогут ли они довести верхний предел до самого известного нижнего предела, или всегда будет небольшой пробел, где наши знания будут неполными? Келли и Мека используют инструменты, которые они отточили в области арифметических прогрессий, для продолжения работы над проблемами теории сложности и других областей теоретической информатики. 

Когда я спросил Меку, как два учёных-компьютерщика добились такого большого прогресса в решении математической проблемы, которая многие годы ставила в тупик экспертов по комбинаторике, он ответил, что не уверен. Он думает, что, возможно, их преимущество связано с тем, что они были новичками в этом вызове.  

«Проблема существует уже давно, и прогресс, похоже, застопорился», — говорит он. Фактически, после того, как он и Келли уже были на пути к публикации, Келли говорит, что наткнулся на сообщение в блоге 2011 года , в котором подробно описывалось, почему математики были пессимистичны в отношении самого подхода, который они оба в конечном итоге использовали.  

«Люди думали, что эти методы не смогут преодолеть существующие барьеры, — говорит Мека, — но, возможно, мы не знали, что эти барьеры существуют».