«Команда А» математики доказывает критическую связь между сложением и множествами | Журнал Кванта

В случайно выбранном наборе чисел сложение может пойти вразнос.

Сложите все пары из такого набора, и вы получите новый список, в котором, скорее всего, будет гораздо больше чисел, чем в начале. Начните с 10 случайных чисел, и этот новый список (называемый суммой) будет содержать около 50 элементов. Начните со 100, и в сумме, вероятно, будет около 5,000; 1,000 случайных начальных чисел составят сумму длиной 500,000 XNUMX чисел.

Но если ваш исходный набор имеет структуру, в сумме может оказаться меньше чисел, чем это. Рассмотрим другой набор из 10 чисел: все четные числа от 2 до 20. Поскольку разные пары в сумме дают одно и то же число — 10 + 12 — это то же самое, что 8 + 14 и 6 + 16, — в сумме всего 19 чисел, а не 50. Эта разница становится все более и более глубокой по мере того, как наборы становятся больше. Структурированный список из 1,000 чисел может содержать сумму всего из 2,000 чисел.

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

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

Ее гипотеза «на самом деле кажется одной из самых фундаментальных вещей, которые мы не поняли», — сказал он. Бен Грин, математик из Оксфордского университета. Это «просто послужило основой для многих вещей, которые меня волнуют».

Грин объединил усилия с Гауэрсом. Фредди Мэннерс Калифорнийского университета в Сан-Диего и Теренс Тао, медалист Филдса Калифорнийского университета в Лос-Анджелесе, сформировал то, что израильский математик и блоггер Гил Калай называется «Команда» математиков. Они доказали версию гипотезы в статье опубликовано 9 ноября.

Нетс Кац, математик из Университета Райса, не принимавший участия в работе, описывает доказательство как «прекрасно простое» — и «более или менее совершенно неожиданное».

Затем Тао предпринял попытку формализовать доказательство в виде Наклонитесь, язык программирования, который помогает математикам проверять теоремы. Всего за несколько недель эта попытка увенчалась успехом. Рано утром во вторник 5 декабря. Тао объявил что Лин доказал свою гипотезу без каких-либо «извинений» — стандартного заявления, которое появляется, когда компьютер не может проверить определенный шаг. Это самое громкое использование такого инструменты проверки с 2021 года, и знаменует собой переломный момент в том, как математики пишут доказательства в терминах, понятных компьютеру. Если эти инструменты станут достаточно простыми для использования математиками, они смогут заменить часто длительный и обременительный процесс экспертной оценки, сказал Гауэрс.

Ингредиенты доказательства кипели десятилетиями. Гауэрс задумал свои первые шаги в начале 2000-х годов. Но потребовалось 20 лет, чтобы доказать то, что Калай назвал «Святым Граалем» в этой области.

В группе

Чтобы понять гипотезу Мартона, полезно ознакомиться с концепцией группы — математического объекта, состоящего из множества и операции. Подумайте о целых числах — бесконечном наборе чисел — и операции сложения. Каждый раз, когда вы складываете два целых числа, вы получаете еще одно целое число. Сложение также подчиняется некоторым другим правилам групповых операций, например ассоциативности, которая позволяет изменять порядок операций: 3 + (5 + 2) = (3 + 5) + 2.

Внутри группы иногда можно найти меньшие наборы, удовлетворяющие всем свойствам группы. Например, если вы сложите любые два четных числа, вы получите еще одно четное число. Четные числа представляют собой отдельную группу, что делает их подгруппой целых чисел. Нечетные числа, напротив, не являются подгруппой. Если сложить два нечетных числа, получится четное число, которого нет в исходном наборе. Но вы можете получить все нечетные числа, просто прибавляя 1 к каждому четному числу. Подобная сдвинутая подгруппа называется смежным классом. Он не обладает всеми свойствами подгруппы, но во многих отношениях сохраняет структуру своей подгруппы. Например, как и четные числа, все нечетные числа расположены на одинаковом расстоянии друг от друга.

Мартон предположил, что если у вас есть набор, мы позвоним A состоит из групповых элементов, сумма которых ненамного больше, чем A сама по себе, то существует некоторая подгруппа — назовем ее G — с особым свойством. Сдвиг G несколько раз, чтобы создать смежные классы, и эти смежные классы, вместе взятые, будут содержать исходный набор A. Более того, она предположила, что число смежных классов не растет намного быстрее, чем размер совокупности — она полагала, что оно должно быть связано полиномиальным коэффициентом, а не гораздо более быстрым экспоненциальным ростом.

Это может звучать как весьма технический курьёз. Но поскольку речь идет о простом тесте, что произойдет, если вы добавите в набор всего два элемента? — для всеобъемлющей структуры подгруппы это очень важно для математиков и компьютерщиков. Та же самая общая идея проявляется, когда ученые-компьютерщики пытаются зашифровать сообщения, чтобы за раз можно было декодировать только часть сообщения. Оно также появляется в вероятностно проверяемых доказательствах — форме доказательства, которую ученые-компьютерщики могут проверить, проверив лишь несколько изолированных битов информации. В каждом из этих случаев вы работаете всего с парой точек структуры — декодируя всего несколько битов длинного сообщения или проверяя небольшую часть сложного доказательства — и делаете вывод о более крупной структуре более высокого уровня.

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

Ружа опубликовал гипотезу Мартона в 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 выбираются случайным образом, то большинство сумм отличаются друг от друга. Если есть k элементы в A, это значит, что вокруг будет k²/2 элемента в сумме. Когда k большое — скажем, 1,000 — k²/2 намного больше, чем k, Но если A является подгруппой, каждый элемент A + A В A, означающий, что A + A такого же размера, как A себя.

PFR рассматривает множества, которые не являются случайными, но и не являются подгруппами. В этих наборах количество элементов в A + A немного мало — скажем, 10kИли 100k. «Это действительно полезно, когда ваше представление о структуре гораздо более богато, чем просто точная алгебраическая структура», — сказал Шачар Ловетт, ученый-компьютерщик из Калифорнийского университета в Сан-Диего.

Все известные математикам множества, подчиняющиеся этому свойству, «довольно близки к реальным подгруппам», сказал Тао. «Это была интуиция, что никаких других фейковых групп поблизости не было». Фрейман доказал версию этого утверждения в своей оригинальной работе. В 1999 году Ружа расширил теорему Фреймана от целых чисел до двоичных списков. Он доказал что когда количество элементов в A + A является постоянным кратным размеру A, A содержится в подгруппе.

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

«Я узнаю настоящую идею, когда вижу настоящую идею»

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

Гауэрс начал разрабатывать потенциальное доказательство полиномиальной версии гипотезы. Его идея заключалась в том, чтобы начать с набора A чья сумма была относительно небольшой, затем постепенно манипулируйте A в подгруппу. Если бы он мог доказать, что полученная подгруппа подобна исходному множеству A, он мог легко заключить, что гипотеза верна. Гауэрс поделился своими идеями с коллегами, но никто не смог превратить их в полноценное доказательство. Хотя стратегия Гауэрса в некоторых случаях была успешной, в других манипуляции A еще дальше от желаемого вывода полиномиальной гипотезы Фреймана-Рузы.

В конце концов, поле двинулось дальше. В 2012 году Сандерс почти доказал ПФР. Но количество необходимых ему сдвинутых подгрупп было выше полиномиального уровня, хотя и ненамного. «Как только он это сделал, это означало, что эта проблема стала менее срочной, но по-прежнему остается действительно приятной проблемой, к которой я очень привязан», — сказал Гауэрс.

Но идеи Гауэрса остались в воспоминаниях и на жестких дисках его коллег. «Здесь есть реальная идея», — сказал Грин, который также был студентом Гауэрса. «Я узнаю настоящую идею, когда вижу настоящую идею». Этим летом Грин, Мэннерс и Тао наконец освободили идеи Гауэрса из чистилища.

Грин, Тао и Мэннерс проработали вместе 37 страниц, прежде чем решили вернуться к идеям 20-летней давности Гауэрса. 23 июня бумагиОни успешно использовали концепцию теории вероятностей, называемую случайными величинами, для исследования структуры множеств с небольшими суммами. Сделав этот переключатель, группа могла более тонко манипулировать своими сетами. «Работа со случайными величинами в некотором смысле гораздо менее жесткая, чем работа с множествами», — сказал Мэннерс. Что касается случайной величины: «Я могу немного подкорректировать одну из вероятностей, и это может дать мне лучшую случайную величину».

Используя эту вероятностную перспективу, Грин, Мэннерс и Тао могли перейти от работы с количеством элементов в наборе к измерению информации, содержащейся в случайной величине, величине, называемой энтропией. Энтропия не была чем-то новым для аддитивной комбинаторики. На самом деле, Тао пытался для популяризации этой концепции в конце 2000-х годов. Но никто еще не пытался использовать его для решения полиномиальной гипотезы Фреймана-Рузы. Грин, Мэннерс и Тао обнаружили, что это мощно. Но они так и не смогли доказать свою гипотезу.

Обдумывая новые результаты, группа осознала, что наконец-то создала среду, в которой дремлющие идеи Гауэрса могут процветать. Если бы они измеряли размер множества, используя его энтропию, а не количество элементов, технические детали могли бы оказаться намного лучше. «В какой-то момент мы поняли, что эти старые идеи Тима 20-летней давности на самом деле с большей вероятностью сработают, чем те, которые мы пробовали», — сказал Тао. «И поэтому мы вернули Тима в проект. И тогда все детали на удивление хорошо сочетаются друг с другом».

Тем не менее, нужно было выяснить множество деталей, прежде чем появилось доказательство. «Было довольно глупо, что все четверо были невероятно заняты другими делами», — сказал Мэннерс. «Вы хотите опубликовать этот замечательный результат и рассказать об этом всему миру, но на самом деле вам все еще нужно написать промежуточные экзамены». В конце концов группа добилась успеха и 9 ноября опубликовала свою статью. Они доказали, что если A + A не больше, чем k раз больше размера A, то A может быть покрыто не более чем примерно k¹² сдвиги подгруппы размером не более A. Это потенциально огромное количество смен. Но это полином, поэтому он не растет экспоненциально быстрее, поскольку k становится больше, как если бы k были в экспоненте.

Несколько дней спустя Тао начал формализовать доказательство. Он совместно руководил проектом формализации, используя пакет управления версиями GitHub для координации вкладов 25 волонтеров по всему миру. Они использовали инструмент под названием План разработанная Патрик Массо, математик из Университета Париж-Сакле, чтобы организовать усилия по переводу того, что Дао под названием «Математический английский» в компьютерный код. Blueprint может, среди прочего, создать наметить изображающие различные логические этапы доказательства. Как только все пузыри покрылись тем, что Тао назвал «прекрасным оттенком зеленого», команда завершила работу. Они обнаружили в статье несколько очень мелких опечаток — в онлайн-версии. сообщениеТао отметил, что «наиболее математически интересные части проекта было относительно легко формализовать, но именно технические «очевидные» шаги заняли больше всего времени».

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

Quanta проводит серию опросов, чтобы лучше обслуживать нашу аудиторию. Возьми наш опрос читателей по математике и вы будете участвовать в бесплатном выигрыше Quanta мерч.