Новое доказательство проливает свет на скрытые закономерности, которые проявляются, когда сложение становится невозможным.
Иллюстрация: Нэш Вирасекера для журнала QuantaСохранить Сохранить
Оригинальная версия этой истории была опубликована в журнале Quanta Magazine.
Самые простые идеи в математике могут оказаться и самыми запутанными.
Возьмем сложение. Это простая операция: одна из первых математических истин, которую мы узнаем, заключается в том, что 1 плюс 1 равно 2. Но у математиков все еще есть много неотвеченных вопросов о типах закономерностей, которые может порождать сложение. «Это одна из самых основных вещей, которые вы можете сделать», — сказал Бенджамин Бедерт, аспирант Оксфордского университета. «Так или иначе, это все еще очень загадочно во многих отношениях».
Исследуя эту тайну, математики также надеются понять пределы мощности сложения. С начала 20-го века они изучали природу множеств «без сумм» — множеств чисел, в которых никакие два числа из множества не будут суммироваться с третьим. Например, сложите любые два нечетных числа, и вы получите четное число. Множество нечетных чисел, таким образом, является множеством без сумм.
В статье 1965 года плодовитый математик Пол Эрдёш задал простой вопрос о том, насколько распространены множества без сумм. Но на протяжении десятилетий прогресс в решении этой проблемы был незначительным.
«Это, казалось бы, очень простая вещь, о которой мы имели поразительно мало представления», — сказал Джулиан Сахасрабудхе, математик из Кембриджского университета.
До этого февраля. Спустя шестьдесят лет после того, как Эрдёш сформулировал свою проблему, Бедерт решил ее. Он показал, что в любом множестве, состоящем из целых чисел — положительных и отрицательных чисел подсчета — есть большое подмножество чисел, которые должны быть свободны от сумм. Его доказательство проникает в глубины математики, оттачивая методы из разрозненных областей, чтобы раскрыть скрытую структуру не только в множествах, свободных от сумм, но и во всех видах других настроек.
«Это фантастическое достижение», — сказал Сахасрабудхе.
Застрял посередине
Эрдёш знал, что любой набор целых чисел должен содержать меньшее подмножество без сумм. Рассмотрим набор {1, 2, 3}, который не является подмножеством без сумм. Он содержит пять различных подмножеств без сумм, таких как {1} и {2, 3}.
Эрдёш хотел узнать, насколько далеко простирается это явление. Если у вас есть множество с миллионом целых чисел, насколько велико его наибольшее подмножество без суммы?
Во многих случаях он огромен. Если вы выберете миллион целых чисел наугад, то около половины из них будут нечетными, что даст вам подмножество без сумм с примерно 500 000 элементов.
Пол Эрдёш был известен своей способностью выдвигать глубокие гипотезы, которые продолжают направлять математические исследования и сегодня.
Фотография: Джордж ЧичериВ своей статье 1965 года Эрдёш показал (в доказательстве, которое было длиной всего в несколько строк и было признано другими математиками блестящим), что любой набор из N целых чисел имеет подмножество, свободное от сумм, состоящее по крайней мере из N/3 элементов.
Но он все равно не был удовлетворен. Его доказательство имело дело со средними: он нашел набор подмножеств без сумм и вычислил, что их средний размер был N/3. Но в таком наборе самые большие подмножества обычно считаются намного больше среднего.
Эрдёш хотел измерить размер этих сверхбольших подмножеств, свободных от сумм.
Математики вскоре выдвинули гипотезу, что по мере того, как ваш набор становится больше, самые большие подмножества без сумм будут становиться намного больше, чем N/3. Фактически, отклонение будет расти бесконечно большим. Это предсказание — что размер самого большого подмножества без сумм составляет N/3 плюс некоторое отклонение, которое растет до бесконечности с N — теперь известно как гипотеза множеств без сумм.
«Удивительно, что этот простой вопрос, по-видимому, представляет значительные трудности, — писал Эрдёш в своей оригинальной статье, — но, возможно, мы упускаем из виду очевидное».
Десятилетиями ничего очевидного не появлялось. Никто не мог улучшить доказательство Эрдёша. «Чем дольше люди не могли улучшить эту простую границу, тем большую известность приобретала эта задача», — сказал Бен Грин, научный руководитель Бедерта в Оксфорде. И, добавил он, это была именно та задача, которую «очень, очень трудно решить хоть как-то лучше».
Противостояние норме
После 25 лет без улучшения первоначального результата Эрдёша математики наконец начали медленно двигаться вперед. В 1990 году два исследователя доказали, что любой набор из N целых чисел имеет подмножество без сумм с по крайней мере N/3 + 1/3 элементами, более часто записываемое как (N + 1)/3.
Но поскольку размер множества всегда является целым числом, увеличение на 1/3 часто несущественно. Например, если вы знаете, что подмножество без сумм должно иметь не менее 5/3 элементов, это означает, что его размер гарантированно будет 2 или больше. Если вы добавите 1/3 к 5/3, ваш ответ все еще будет 2. «Забавно, это означает, что на самом деле это не всегда улучшает его», — сказал Дэвид Конлон из Калифорнийского технологического института. «Это улучшает его только тогда, когда N делится на 3».
В 1997 году легенда математики Жан Бургейн поднял границу до (N + 2)/3. Результат, возможно, не казался заслуживающим упоминания, но в статье Бургейна был зарыт поразительный прорыв. Он описал идею, как доказать, что самые большие подмножества без сумм будут произвольно больше этого. Он просто не мог точно определить детали, чтобы превратить это в полное доказательство.
«В статье примерно написано, как я пытался решить проблему и почему это не сработало», — сказал Сахасрабудхе.
Жан Бургейн разработал креативную стратегию для доказательства гипотезы множеств без сумм.
Фотография: Джордж М. Бергман, БерклиБургейн опирался на величину, называемую нормой Литтлвуда, которая измеряет структуру заданного множества. Эта величина, которая происходит из области математики, называемой анализом Фурье, имеет тенденцию быть большой, если множество более случайно, и маленькой, если множество демонстрирует большую структуру.
Бургейн показал, что если множество с N элементами имеет большую норму Литтлвуда, то оно также должно иметь множество без сумм, которое намного больше, чем N/3. Но он не смог добиться прогресса в случае, когда множество имеет маленькую норму Литтлвуда.
«Бургейн славится своей компетентностью», — сказал Шон Эберхард из Университета Уорика. «Это очень яркий показатель того, насколько сложна эта проблема».
В конечном итоге Бургейну пришлось использовать другой аргумент, чтобы получить свою границу (N + 2)/3. Но математики читают между строк: они могли бы использовать норму Литтлвуда, чтобы полностью разрешить эту гипотезу. Им просто нужно было выяснить, как иметь дело с множествами с небольшой нормой Литтлвуда.
Иллюстрация: Нэш Вирасекера для журнала QuantaБыли основания для оптимизма: математики уже знали о множествах с малой нормой Литтлвуда, которые имеют огромные подмножества без сумм. Эти множества, называемые арифметическими прогрессиями, состоят из равномерно распределенных чисел, таких как {5, 10, 15, 20}. Математики подозревали, что любое множество с малой нормой Литтлвуда имеет очень специфическую структуру — что это более или менее набор множества различных арифметических прогрессий (с несколькими изменениями). Они надеялись, что если им удастся это показать, они смогут использовать это свойство, чтобы доказать, что любое множество с малой нормой Литтлвуда имеет большое подмножество без сумм.
Но эта задача была не из легких. «Я, конечно, пытался доказать гипотезу о сумме без использования идей [Бургейна]», — сказал Грин, но «мы все еще не очень понимаем структуру множеств с малой нормой Литтлвуда. Все, что связано с Литтлвудом, сложно».
И хотя математики продолжали верить в стратегию Бургейна, основанную на Литтлвудском подходе, ничего не произошло.
Прошло более двух десятилетий. Затем, осенью 2021 года, Бенджамин Бедерт поступил в аспирантуру.
Известные проблемы
С Грином в качестве его научного руководителя, Бедерт неизбежно столкнулся с гипотезой множеств без сумм. На сайте Грина перечислено 100 открытых задач; эта появляется первой.
Бедерт просмотрел список вскоре после того, как начал учиться в аспирантуре. Сначала он избегал задачи о множествах без сумм. «Я подумал: это суперсложно, я не буду об этом думать», — вспоминал он. «Я оставлю это на будущее».
Будущее наступило достаточно скоро. Летом 2024 года Бедерт решил, что он готов к более рискованному проекту. «Я уже показал некоторые достаточно хорошие результаты в своей докторской диссертации и уже составил диссертацию», — сказал он. «Я начал думать об этих, как мне кажется, более известных проблемах».
Бенджамин Бедерт, аспирант Оксфордского университета, решил десятилетнюю задачу, которая проверяет роль сложения в множествах.
Фотография: Романа МеерайсОн прочитал статью Бургейна 1997 года и начал размышлять о том, как реализовать план Литтлвуда. Почти сразу у него возникла идея, как он мог бы подойти к проблеме множеств с небольшой нормой Литтлвуда.
До сих пор было слишком сложно показать, что множества с малой нормой Литтлвуда всегда напоминают наборы арифметических прогрессий. Но Бедерт посчитал, что может быть полезно доказать что-то более достижимое: что даже если эти множества не построены буквально из арифметических прогрессий, они разделяют некоторые ключевые, прогрессоподобные свойства.
В недавнем проекте Бедерт наткнулся на то, что он считал хорошим кандидатом на свойство, на котором можно было бы сосредоточиться. В арифметических прогрессиях есть много групп чисел, которые имеют одинаковую сумму. Например, в наборе четных чисел (который является арифметической прогрессией) 4 + 8 имеет ту же сумму, что и 2 + 10 и 2 + 4 + 6. Бедерт подумал, что может быть достаточно показать, что наборы с небольшой нормой Литтлвуда всегда подчиняются этому свойству.
За пару недель ему удалось доказать, что свойство истинно. Но даст ли ему результат тот уровень сходства с арифметическими прогрессиями, который ему нужен для доказательства гипотезы множеств без сумм?
«Я был определенно взволнован», — сказал он. «А потом я понял, что мне еще так много предстоит сделать».
Волны прогресса
Во-первых, Бедерт показал, что любой набор с небольшой нормой Литтлвуда может быть «отображен» во второй набор, который имел еще большее сходство с арифметическими прогрессиями. Он подозревал, что именно в этих новых наборах он найдет большие подмножества без сумм.
Иллюстрация: Нэш Вирасекера для журнала QuantaПоследней задачей было показать, каков будет размер такого подмножества без сумм. «В течение рождественских каникул я был одержим этой проблемой», — сказал Бедерт. «К Новому году я так и не нашел последний кусочек головоломки».
Затем, через несколько дней после того, как он вернулся в Оксфорд в январе, к нему пришло это. «Я не уверен, откуда это взялось», — сказал он. «Возможно, эти идеи шевелятся у вас в голове какое-то время, а затем [вы] наконец-то получаете что-то, что работает».
Он представил структуру своих множеств с помощью инструмента, называемого преобразованием Фурье, а затем модифицировал доказательство 1981 года, чтобы показать, что некоторые из отдельных компонентов этого представления должны иметь большую норму Литтлвуда. Поскольку Бургейн уже показал, как обращаться с множествами с большими нормами Литтлвуда, это завершило доказательство.
В конце концов, Бедерт показал, что любой набор из N целых чисел имеет подмножество без сумм с по крайней мере N/3 + log(log N) элементов. Для многих значений N это дает вам подмножество без сумм, которое лишь немного больше среднего размера Эрдёша N/3. Даже если N равно 10100, например, log(log N) составляет всего около 5. Но по мере того, как N приближается к бесконечности, увеличивается и разница в границах Бедерта и Эрдёша — тем самым устанавливая гипотезу.
«Это действительно потрясающий результат», — сказал Ифань Цзин из Университета штата Огайо. Цзин, который также был наставником Грина, приписывает это достижение интенсивной сосредоточенности Бедерта. «Бенджамин действительно глубоко вошел в модификацию доказательства Бургейна и заставил его работать», — сказал он. «Он тратит гораздо больше времени, чем другие люди, на ту же проблему».
Еще многое предстоит понять о подмножествах без сумм — и, следовательно, о степени, в которой сложение влияет на структуру целых чисел. Например, результат Бедерта решает вопрос о том, становится ли наибольшее подмножество без сумм бесконечно больше, чем N/3. Но математики не знают точно, как быстро может расти это отклонение. Благодаря статье Грина и двух его коллег 2014 года они знают, что отклонение растет медленнее, чем N. Но, как сказал Грин, «остается огромный разрыв» между этой верхней границей N и нижней границей Бедерта log(log N).
Работа также дает новое представление о множествах, имеющих малую норму Литтлвуда. Такие множества являются фундаментальными объектами в области анализа, но их очень трудно изучать. Результат Бедерта помог математикам лучше понять их структуру, которую Грин и другие теперь надеются продолжить исследовать. «Это красиво, это интересно, это кажется естественным», — сказал Эберхард. «Вы хотите разгадать тайну, не так ли?»
Для Сахасрабудхе вывод прост. «Старая и сложная проблема решена гениальным парнем», — сказал он. «То, на чем он строит, тонко и с чем трудно работать. Это действительно красивый результат».
Оригинальная статья перепечатана с разрешения журнала Quanta Magazine, редакционно независимого издания Фонда Саймонса, чья миссия заключается в расширении понимания науки общественностью путем освещения научных разработок и тенденций в области математики, физических и биологических наук.
Источник: www.wired.com
