Pull to refresh

Сложение с подвохом: что мы до сих пор не понимаем в 1 + 1? Гипотеза Эрдеша о множествах без суммы

Level of difficultyEasy
Reading time8 min
Views1.9K
Original author: Лейла Сломан

Возьмём, к примеру, сложение. Одна из первых истин, которые мы усваиваем: 1 плюс 1 — это 2. Казалось бы, операция элементарная. Но даже она продолжает порождать у математиков вопросы без чётких ответов. Какие глубинные закономерности заложены в сложении? — до сих пор остаётся открытым. «Это фундаментальная операция, — отмечает Бенджамин Бедерт, аспирант Оксфорда, — и тем не менее в ней до сих пор много загадок».

В попытке разобраться в природе сложения, математики заодно пытаются установить его предельные границы. С начала XX века они изучают особый класс чисел — так называемые бессумные множества, в которых ни одна пара чисел не даёт в сумме третьего из этого же множества. К примеру, любое два нечётных числа в сумме дают чётное, значит, все нечётные образуют бессумное множество.

В 1965 году математик Пол Эрдёш задал на первый взгляд скромный вопрос: насколько часто встречаются такие бессумные множества? Ответ на него оказался крайне непростым — десятилетиями в решении этой задачи почти не наблюдалось прогресса.

«Задача кажется элементарной, но мы до сих пор слабо её понимаем», — подчёркивает Джулиан Сахасрабудхе, математик из Кембриджа.

И вот — прорыв. В феврале этого года, спустя почти 60 лет после того, как Эрдёш впервые сформулировал задачу, Бенджамин Бедерт её решил. Он доказал, что любое множество целых чисел — как положительных, так и отрицательных — обязательно содержит крупное подмножество, в котором никакая пара не складывается в третий элемент. Его работа опирается на методы из разных разделов математики и раскрывает глубинную структуру не только в бессумных множествах, но и в других сложных конфигурациях чисел.

«Это выдающееся достижение», — сказал Сахасрабудхе.

Застряли на середине пути

Эрдёш понимал: в любом множестве целых чисел всегда можно найти подмножество, где никакая пара чисел не складывается в третий элемент — то есть бессумное. Например, рассмотрим множество {1, 2, 3}. Само по себе оно не является бессумным, ведь 1 + 2 = 3. Но внутри него есть пять различных бессумных подмножеств — например, {1}, {2, 3} и другие.

Эрдёша интересовало: насколько широко встречается это явление? Если взять огромное множество — скажем, миллион целых чисел — как велико может быть в нём максимальное бессумное подмножество?

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

Пол Эрдёш был знаменит своей способностью формулировать фундаментальные и глубокие задачи, которые десятилетиями задают вектор математических исследований
Пол Эрдёш был знаменит своей способностью формулировать фундаментальные и глубокие задачи, которые десятилетиями задают вектор математических исследований

В своей статье 1965 года Эрдёш дал краткое, всего в несколько строк, но яркое доказательство: любое множество из N целых чисел содержит бессумное подмножество размером не менее N/3. Коллеги-математики называли этот вывод блестящим.

Но сам Эрдёш был не удовлетворён. Его метод давал усреднённую оценку — он вычислял средний размер бессумных подмножеств, и это среднее оказывалось равным N/3. Однако в этом множестве могли быть подмножества значительно больше среднего.

Эрдёша интересовали именно эти максимальные случаи — подмножества, значительно превышающие среднюю планку.

Так возникла гипотеза: по мере роста исходного множества, максимальное бессумное подмножество должно становиться всё больше — и не просто больше, а на всё растущее отклонение от N/3. То есть, по сути, его размер — это N/3 плюс некоторая добавка, стремящаяся к бесконечности. Это и стало известно как гипотеза о множествах без суммы.

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

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

Противостояние норме

После четверти века безуспешных попыток превзойти результат Эрдёша математикам всё же удалось сделать первый шаг вперёд. В 1990 году двое исследователей доказали: в любом множестве из N целых чисел можно найти бессумное подмножество, содержащее как минимум N/3 + 1/3 элемента — или, в более привычной форме, (N + 1)/3.

Но это улучшение оказалось формальным. Поскольку размер множества — величина целая, прибавка в одну треть далеко не всегда имеет практический эффект. Например, если (N + 1)/3 даёт в итоге 5/3, то в действительности подмножество должно быть просто не меньше 2 — а это и так следует из оценки N/3. «Ирония в том, что прибавка 1/3 часто не меняет ничего, — поясняет Дэвид Конлон из Caltech. — Это срабатывает только в случае, если N делится на 3».

Следующий значимый результат появился в 1997 году. Жан Буржан — один из ярчайших умов в математике своего времени — довёл нижнюю границу до (N + 2)/3. На первый взгляд, прирост вновь казался скромным, но настоящая ценность заключалась не в числе, а в подходе. В статье Буржана содержалась идея, как можно доказать, что бессумные подмножества могут быть сколь угодно большими по сравнению с N/3 — просто ему не хватило технических средств, чтобы довести довод до конца и оформить полное доказательство.

«Эта статья скорее напоминает размышление вслух, — комментирует Сахасрабудхе. — Она показывает ход мысли, попытку, и честное признание, почему довести её до конца не получилось».

Жан Буржан разработал креативную стратегию для доказательства гипотезы о множествах без суммы
Жан Буржан разработал креативную стратегию для доказательства гипотезы о множествах без суммы

Норма Литтлвуда и тупик

В своей попытке расширить границы теории, Буржан опирался на важную математическую характеристику — норму Литтлвуда. Эта величина, пришедшая из анализа Фурье, позволяет измерять, насколько «хаотичным» или, наоборот, структурированным является множество. Чем более оно беспорядочное, тем выше норма; упорядоченные множества, напротив, демонстрируют низкие значения.

Буржан показал: если множество из N чисел обладает высокой нормой Литтлвуда, то в нём обязательно найдётся бессумное подмножество, значительно превышающее N/3. Но этот подход переставал работать, когда норма была малой — и именно такие множества оставались неразгаданными.

«Буржан — чрезвычайно глубокий математик, — подчёркивает Шон Эберхард из Уорикского университета. — Его попытка — отличный пример того, насколько трудна эта проблема даже для самых сильных умов».

В конечном итоге Буржану пришлось использовать другую стратегию, чтобы обосновать свой результат (N + 2)/3. Однако в его попытке читатели увидели больше, чем было прямо сказано: возможно, норма Литтлвуда действительно может привести к полному решению гипотезы. Оставалось главное — научиться работать с множествами, у которых эта норма мала.

Надежда у математиков была. Они уже знали примеры таких «спокойных» множеств — например, арифметические прогрессии, вроде {5, 10, 15, 20}, где элементы идут с равным шагом. Эти множества, несмотря на свою низкую норму Литтлвуда, содержат богатое разнообразие бессумных подмножеств.

Возникла гипотеза: возможно, любое множество с малой нормой можно представить как сочетание (с некоторыми искажениями) нескольких арифметических прогрессий. Если это удастся доказать, то можно будет распространить на них и саму идею Буржана — и, наконец, подступиться к гипотезе вплотную.

Но всё оказалось непросто. «Я тоже пытался использовать идеи Буржана, — признаётся Бен Грин, — но структура множеств с малой нормой Литтлвуда всё ещё крайне слабо понятна. Всё, что связано с Литтлвудом, — чертовски сложно».

Тем не менее, вера в метод оставалась. Более двадцати лет стратегию Буржана никто не развивал. Пока, в один осенний день 2021 года, в аспирантуру не поступил Бенджамин Бедерт.

Пресловутые проблемы

Поскольку научным руководителем Бенджамина Бедерта в аспирантуре был сам Бен Грин, встреча с гипотезой о множествах без суммы была лишь вопросом времени. На личном сайте Грина размещён список из 100 нерешённых математических задач — и именно эта стоит в нём под номером один.

Бедерт увидел этот список вскоре после поступления в аспирантуру. Но изначально он сознательно обходил задачу стороной. «Я подумал, что она слишком трудная, — вспоминает он. — И решил просто пока не вникать».

Но «пока» продлилось недолго. Летом 2024 года он почувствовал, что готов к риску. «К тому моменту у меня уже был солидный прогресс по диссертации, в целом работа была написана, — рассказывает Бедерт. — И я начал присматриваться к более известным, амбициозным задачам».

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

Он вернулся к статье Жана Буржана 1997 года и начал размышлять, как можно реализовать стратегию с использованием нормы Литтлвуда. Почти сразу появилась идея как подступиться к множествам с малой нормой.

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

Во время недавнего исследовательского проекта он наткнулся на, как ему показалось, удачную идею. Он заметил, что в арифметических прогрессиях много подмножеств, у которых одинаковая сумма. Например, в множестве чётных чисел сумма 4 + 8 равна 2 + 10, и также равна 2 + 4 + 6. Это — специфическое свойство прогрессий. Бедерт решил: возможно, будет достаточно показать, что множества с малой нормой Литтлвуда всегда демонстрируют такое поведение.

Через пару недель ему удалось это доказать. Но означало ли это, что он приблизился к настоящему сходству с арифметическими прогрессиями — настолько, чтобы подступиться к самой гипотезе?

«Я был в восторге, — признаётся он. — А потом понял: впереди ещё долгий путь».

Волны прогресса

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

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

«Во время рождественских каникул я постоянно крутил это в голове, — вспоминает Бедерт. — Но к Новому году финальное звено всё ещё не складывалось».

А потом, спустя несколько дней после возвращения в Оксфорд в январе, он внезапно увидел решение. «Я не могу точно сказать, откуда оно пришло, — признаётся он. — Видимо, эти идеи давно варились в голове, и наконец сложились в нечто осмысленное».

Он использовал преобразование Фурье, чтобы описать структуру полученных множеств, и затем адаптировал идею из доказательства 1981 года. Это позволило показать, что некоторые отдельные компоненты этих множеств всё же обязаны обладать большой нормой Литтлвуда. А значит, с ними уже можно было работать — с опорой на методы, разработанные Буржаном. Всё сошлось. Доказательство замкнулось.

Бедерт доказал, что в любом множестве из N целых чисел существует бессумное подмножество, размер которого не меньше N/3 + log(log N). Для небольших и даже умеренно больших N эта прибавка к N/3 — символическая. Даже если N = 10¹⁰⁰, логарифм логарифма — это лишь около 5. Но важно другое: по мере роста N это отставание от границы Эрдёша только увеличивается, и гипотеза, выдвинутая 60 лет назад, наконец подтверждена.

Это один из тех редких случаев, когда многолетняя теоретическая работа завершилась простым и элегантным ответом.

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

И всё же впереди остаются открытые вопросы. Мы до сих пор не знаем, насколько быстро может расти это отклонение от N/3. Да, теперь ясно, что оно больше, чем log(log N), и медленнее, чем N. Но между этими двумя точками по-прежнему зияет огромная пропасть. «Между верхней границей в N и нижней границей в log(log N) — целый континент неизвестного», — говорит Грин.

И есть ещё один важный эффект этой работы: она открыла новое окно в мир множеств с малой нормой Литтлвуда. Эти множества давно считались фундаментальными в анализе, но оставались почти непроницаемыми. Теперь, благодаря Бедерту, их структура стала хотя бы немного понятнее. «Это красиво, глубоко и естественно, — считает Шон Эберхард. — И ты хочешь разгадать эту тайну до конца. Не так ли?»

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

Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+8
Comments5

Articles