Команда из четырех выдающихся математиков, включая двух филдсовских медалистов, доказала гипотезу, описанную как “святой грааль аддитивной комбинаторики”. В течение месяца независимое сотрудничество подтвердило ее с помощью компьютерного доказательства.
В случайно выбранном наборе чисел сложение может быть произвольным.
Сложите вместе каждую пару из такого набора, и в итоге вы получите новый список, в котором, вероятно, будет намного больше чисел, чем в том, с которого вы начинали. Начните с 10 случайных чисел, и этот новый список (называемый sumset) будет содержать около 50 элементов. Начните со 100, и в наборе сумм, вероятно, будет около 5000; из 1000 случайных начальных чисел получится набор сумм длиной 500 000 чисел.
Но если ваш исходный набор имеет структуру, в конечном итоге в сумме может оказаться меньше чисел, чем это. Рассмотрим другой набор из 10 чисел: все четные числа от 2 до 20. Поскольку разные пары в сумме дают одно и то же число — 10 + 12 равно 8 + 14 и 6 + 16 — в сумме получается всего 19 чисел, а не 50. Это различие становится все более существенным по мере увеличения наборов. Структурированный список из 1000 чисел может содержать набор сумм, содержащий всего 2000 чисел.
В 1960—х годах математик по имени Gregory Freiman начал исследовать множества с малыми суммами в попытке исследовать связь между сложением и структурой множества — важнейшую связь, определяющую математическую область аддитивной комбинаторики. Фрейман добился впечатляющего прогресса, доказав, что множество с небольшой суммой должно содержаться в большем наборе, элементы которого расположены на очень регулярном расстоянии друг от друга. Но затем поле застопорилось. “Первоначальное доказательство Фреймана было необычайно трудным для понимания, до такой степени, что никто на самом деле не был абсолютно уверен в его правильности. Так что на самом деле это не оказало того влияния, которое могло бы оказать”, — сказал Timothy Gowers, математик из Коллеж де Франс и Кембриджского университета и обладатель Филдсовской медали. “Но затем на сцену ворвался Imre Ruzsa”.
В серии из двух работ, опубликованных в 1990-х годах, Руза повторно доказал теорему Фреймана с помощью нового элегантного аргумента. Несколько лет спустя Katalin Marton, влиятельный венгерский математик, скончавшаяся в 2019 году, изменила вопрос о том, что означает небольшая сумма в структуре исходного набора. Она заменила типы элементов, которые появлялись в наборе, и тип структуры, на которую следует обращать внимание математикам, полагая, что это позволит математикам извлекать еще больше информации. Гипотеза Мартона имеет связи с системами доказательства, теорией кодирования и криптографией и занимает важное место в аддитивной комбинаторике.
Ее гипотеза “кажется действительно одной из самых фундаментальных вещей, которые мы не понимали”, — сказал Ben Green, математик из Оксфордского университета. Это “просто как бы подкрепило множество вещей, которые меня волнуют”.
Грин объединил усилия с Гауэрсом, Freddie Manners из Калифорнийского университета в Сан-Диего и Terence Tao, медалистом Филдса в Калифорнийском университете в Лос-Анджелесе, чтобы сформировать то, что израильский математик и блогер Gil Kalai назвал “A-team” математиков. Они доказали версию этой гипотезы в статье, опубликованной 9 ноября (shared on November 9.).
Nets Katz, математик из Университета Райса, который не принимал участия в работе, описывает доказательство как “прекрасно понятное” — и “более или менее совершенно неожиданное”.
Courtesy of Péter E. Frenkel / Каталин Мартон, которую можно увидеть здесь на обновленной фотографии, выдвинула гипотезу о структуре успеха, имеющую отношение к системам проверки, теории кодирования и криптографии.
Любезно предоставлено Питером Э. Ренкелем
Затем Tao предпринял попытку формализовать доказательство в Lean, языке программирования, который помогает математикам проверять теоремы. Всего за несколько недель эта попытка увенчалась успехом. Ранним утром во вторник, 5 декабря, Tao announced, что Lean доказал гипотезу без каких—либо “извините” — стандартного заявления, которое появляется, когда компьютер не может проверить определенный шаг. Это самое массовое использование таких инструментов верификации с 2021 года, и оно знаменует собой переломный момент в том, как математики пишут доказательства в терминах, понятных компьютеру. Если эти инструменты станут достаточно простыми в использовании математиками, они, возможно, смогут заменить часто длительный и обременительный процесс рецензирования, сказал Гауэрс.
Компоненты доказательства готовились десятилетиями. Гауэрс задумал свои первые шаги в начале 2000-х. Но потребовалось 20 лет, чтобы доказать то, что Калай назвал “святым Граалем” в этой области.
Внутренняя группа
Чтобы понять гипотезу Мартона, полезно ознакомиться с концепцией группы, математического объекта, состоящего из множества и операции. Подумайте о целых числах — бесконечном наборе чисел — и операции сложения. Каждый раз, когда вы складываете два целых числа вместе, вы получаете другое целое число. Сложение также подчиняется нескольким другим правилам групповых операций, таким как ассоциативность, которая позволяет изменять порядок операций: 3 + (5 + 2) = (3 + 5) + 2.
Внутри группы иногда можно найти наборы меньшего размера, удовлетворяющие всем свойствам группы. Например, если вы сложите любые два четных числа, вы получите еще одно четное число. Четные числа сами по себе являются группой, что делает их подгруппой целых чисел. Нечетные числа, напротив, не являются подгруппой. Если вы сложите два нечетных числа, вы получите четное число — не в исходном наборе. Но вы можете получить все нечетные числа, просто добавив 1 к каждому четному числу. Подобная смещенная подгруппа называется смежной. Он не обладает всеми свойствами подгруппы, но во многих отношениях сохраняет структуру своей подгруппы. Например, как и четные числа, все нечетные числа расположены равномерно.
Patrick Imbert/Collège de France/Тимоти Гауэрс выдвинул идеи о том, как доказать гипотезу Мартона десятилетия назад; они стали центральными в новом доказательстве.
Патрик Имберт/Коллеж де Франс
Мартон предположил, что если у вас есть набор, который мы назовем A, состоящий из элементов группы, сумма которых не намного больше, чем сама A, то существует некоторая подгруппа — назовем ее G — со специальным свойством. Сдвиньте G несколько раз, чтобы создать смежные наборы, и эти смежные наборы, взятые вместе, будут содержать исходный набор A. Более того, она предположила, что число смежных наборов растет не намного быстрее, чем размер суммарного набора — она полагала, что это должно быть связано полиномиальным коэффициентом, в отличие от гораздо более быстрого экспоненциального рост.
Это может показаться сугубо техническим курьезом. Но поскольку это связывает простой тест — что произойдет, если вы добавите всего два элемента в набор? — со всеобъемлющей структурой подгруппы, это очень важно для математиков и специалистов по информатике. Та же общая идея проявляется, когда специалисты по информатике пытаются зашифровать сообщения так, чтобы вы могли расшифровать только часть сообщения за раз. Это также появляется в вероятностно проверяемых доказательствах, форме доказательства, которую специалисты по информатике могут проверить, проверив только несколько изолированных битов информации. В каждом из этих случаев вы работаете всего с парой моментов в структуре — декодируете всего несколько битов из длинного сообщения или проверяете небольшую часть сложного доказательства — и делаете вывод о более крупной структуре более высокого уровня.
“Вы можете либо притвориться, что все является большим подмножеством группы”, — сказал Tom Sanders, бывший студент Гауэрса, который сейчас является коллегой Грина в Оксфорде, либо вы можете “получить все, что хотели, из существования множества аддитивных совпадений. Обе эти точки зрения полезны”.
Руза опубликовала гипотезу Мартон в 1999 году (published Marton’s conjecture in 1999), полностью отдав ей должное. “Она пришла к этой гипотезе независимо от меня и Фреймана и, вероятно, раньше нас”, — сказал он. “Вот почему, когда я поговорил с ней, я решил назвать это ее гипотезой”. Тем не менее, математики сейчас называют это полиномиальной гипотезой Фреймана-Рузсы, или PFR.
Нули и единицы
Группы, как и многие математические объекты, имеют множество различных форм. Мартон предположила, что ее гипотеза верна для всех групп. Это еще предстоит доказать. Новая статья доказывает это для определенного типа групп, которые используют в качестве своих элементов списки двоичных чисел, таких как (0, 1, 1, 1, 0). Поскольку компьютеры работают в двоичном формате, эта группа имеет решающее значение в информатике. Но это также было полезно в аддитивной комбинаторике. “Это похоже на игрушечную среду, в которой вы можете поиграть и попробовать разные вещи”, — сказал Сандерс. “Алгебра намного, намного приятнее”, чем работа с целыми числами, добавил он.
Списки имеют фиксированную длину, и каждый бит может быть либо 0, либо 1. Вы складываете их вместе, добавляя каждую запись к ее аналогу в другом списке, с правилом, что 1 + 1 = 0. Итак (0, 1, 1, 1, 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR — это попытка выяснить, как может выглядеть набор, если он не совсем подгруппа, но имеет некоторые группоподобные функции.
Чтобы уточнить PFR, представьте, что у вас есть набор двоичных списков, называемых A. Теперь возьмите каждую пару элементов из A и сложите их. Полученные суммы составляют набор A, называемый A + A. Если элементы A выбраны случайным образом, то большинство сумм отличаются друг от друга. Если в A есть k элементов, это означает, что в наборе сумм будет около k2/2 элементов. Когда k велико — скажем, 1000 — k2/2 намного больше, чем k. Но если A является подгруппой, каждый элемент A + A находится в A, что означает, что A + A имеет тот же размер, что и сам A.
PFR рассматривает множества, которые не являются случайными, но и не являются подгруппами. В этих наборах количество элементов в A + A несколько невелико — скажем, 10k или 100k. “Это действительно полезно, когда ваше представление о структуре гораздо богаче, чем просто точная алгебраическая структура”, — говорит Shachar Lovett, специалист по информатике из Калифорнийского университета в Сан-Диего.
Все известные математикам множества, которые подчинялись этому свойству, “довольно близки к реальным подгруппам”, — сказал Тао. “Это была интуиция, что вокруг не было никаких других поддельных групп”. Фрейман доказал версию этого утверждения в своей оригинальной работе. В 1999 году Рузса распространил теорему Фреймана с целых чисел на двоичные списки. Он доказал, что когда число элементов в A + A постоянно кратно размеру A, A содержится внутри подгруппы.
Но теорема Рузы требовала, чтобы подгруппа была огромной. Идея Мартона состояла в том, чтобы постулировать, что вместо того, чтобы содержаться в одной гигантской подгруппе, A может содержаться в полиномиальном числе смежных подгрупп подгруппы, которая не больше исходного множества A.
«Я узнаю реальную идею, когда вижу реальную идею»
Примерно на рубеже тысячелетий Гауэрс наткнулся на доказательства теоремы Фреймана Рузсы при изучении другой задачи о множествах, содержащих строки равномерно распределенных чисел. “Мне нужно было что-то вроде этого, чтобы получить структурную информацию из гораздо более разрозненной информации об определенном наборе”, — сказал Гауэрс. “Мне очень повезло, что незадолго до этого Ruzsa представила это абсолютно великолепное доказательство”.
Разработчики начали разрабатывать потенциальное доказательство полиномиальной версии гипотезы. Его идея состояла в том, чтобы начать с множества A, сумма которого была относительно небольшой, затем постепенно преобразовать A в подгруппу. Если бы он мог доказать, что результирующая подгруппа была похожа на исходное множество A, он мог бы легко заключить, что гипотеза верна. Гауэрс поделился своими идеями с коллегами, но никто не смог сформулировать их в полное доказательство. Хотя стратегия Гауэрса в некоторых случаях была успешной, в других манипуляции еще больше уводили от желаемого вывода полиномиальной гипотезы Фреймана-Рузсы.
В конце концов, поле продвинулось дальше. В 2012 году Сандерс почти доказал PFR. Но количество сдвинутых подгрупп, в которых он нуждался, было выше полиномиального уровня, хотя и ненамного. “Как только он это сделал, это означало, что это стало менее срочной задачей, но все еще действительно приятной проблемой, к которой я испытываю большую симпатию”, — сказал Гауэрс.
Но идеи Гауэрса продолжали жить в памяти и на жестких дисках его коллег. “В этом есть реальная идея”, — сказал Грин, который также был студентом Гауэрса. “Я узнаю реальную идею, когда вижу реальную идею”. Этим летом Грин, Мэннерс и Тао наконец-то освободили идеи Гауэрса из их чистилища.
Грин, Тао и Мэннерс проработали в соавторстве 37 страниц, прежде чем решили вернуться к идеям Гауэрса 20-летней давности. В статье от 23 июня они успешно использовали концепцию из теории вероятностей, называемую случайными величинами, для исследования структуры множеств с небольшими суммами. Сделав это переключение, группа могла бы манипулировать своими наборами данных более тонко. “Работа со случайными величинами каким-то образом гораздо менее жесткая, чем работа с наборами”, — сказал Мэннерс. Со случайной величиной “я могу немного изменить одну из вероятностей, и это может дать мне лучшую случайную величину”.
Используя эту вероятностную перспективу, Грин, Мэннерс и Тао смогли перейти от работы с количеством элементов в наборе к измерению информации, содержащейся в случайной переменной, величине, называемой энтропией. Энтропия не была чем-то новым для аддитивной комбинаторики. Фактически, Тао пытался популяризировать эту концепцию в конце 2000-х годов. Но никто еще не пытался использовать ее в полиномиальной гипотезе Фреймана-Рузсы. Грин, Мэннерс и Тао обнаружили, что она эффективна. Но они все равно не смогли доказать эту гипотезу.
Когда группа обдумывала свои новые результаты, они поняли, что наконец-то создали среду, в которой дремлющие идеи Гауэрса могли бы процветать. Если бы они измеряли размер набора, используя его энтропию, а не количество элементов, технические детали могли бы получиться намного лучше. “В какой-то момент мы поняли, что эти старые идеи Тима 20-летней давности на самом деле с большей вероятностью сработают, чем те, которые мы пробовали”, — сказал Тао. “И поэтому мы вернули Тима в проект. И тогда все части на удивление хорошо сошлись”.
Тем не менее, нужно было выяснить много деталей, прежде чем доказательства были собраны воедино. “Было немного глупо, что все четверо из нас были невероятно заняты другими вещами”, — сказал Мэннерс. “Вы хотите опубликовать этот замечательный результат и рассказать миру, но на самом деле вам все равно нужно написать промежуточные экзамены”. В конце концов, группа справилась, и 9 ноября они опубликовали свою работу. Они доказали, что если A + A не больше, чем в k раз больше размера A, то A может быть покрыто не более чем примерно k12 сдвигами подгруппы, которая не больше A. Это потенциально огромное количество сдвигов. Но это многочлен, поэтому он не растет экспоненциально быстрее по мере увеличения k, как это было бы, если бы k было в экспоненте.
Несколько дней спустя Тао приступил к формализации доказательства. Он руководил проектом формализации совместно, используя пакет управления версиями GitHub для координации вклада 25 добровольцев по всему миру. Они использовали инструмент под названием Blueprint, разработанный Патриком Массо, математиком из Университета Париж-Сакле, для организации работы по переводу с того, что Tao называет “математическим английским”, на компьютерный код. Blueprint может, помимо прочего, создавать диаграмму, изображающую различные логические этапы, участвующие в доказательстве. Как только все пузырьки были покрыты тем, что Тао назвал “прекрасным оттенком зеленого”, команда закончила. Они обнаружили несколько очень незначительных опечаток в документе — в онлайн-сообщении Тао отметил, что “наиболее интересные с математической точки зрения части проекта были относительно просты в формализации, но именно технические «очевидные» шаги заняли больше всего времени”.
Мартон умерла всего за несколько лет до того, как была доказана ее знаменитая гипотеза, но доказательство перекликается с работой всей ее жизни по энтропии и теории информации. “Все работает намного лучше, когда вы делаете это в рамках этой энтропийной структуры, чем в рамках, которые я пытался создать”, — сказал Гауэрс. “Мне это все еще кажется чем-то волшебным”.
Quanta проводит серию опросов, чтобы лучше обслуживать нашу аудиторию. Пройдите наш опрос читателей mathematics, и вы получите право выиграть бесплатный товар Quanta. — Quanta is conducting a series of surveys to better serve our audience. Take our mathematics reader survey and you will be entered to win free Quanta merch.