первокурсник находит парадоксальный набор чисел | Журнал Кванта

Математики радуются, когда доказывают, что, казалось бы, невозможные вещи существуют. Так обстоит дело с новое доказательство опубликовано в сети в марте автором Седрик Пилат, аспирант первого курса Оксфордского университета.

Пилатт доказал, что можно создать набор — набор чисел — который удовлетворяет двум явно несовместимым свойствам. Во-первых, никакие две пары чисел в наборе не дают в сумме одну и ту же сумму. Например, сложите любые два числа в {1, 3, 5, 11}, и вы всегда получите уникальный номер. Легко построить небольшие «сидоновские» множества, подобные этому, но по мере увеличения числа элементов возрастает и вероятность того, что суммы совпадут, разрушая сидоновость множества.

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

Вопрос о том, существует ли такой набор, стоит десятилетиями, с тех пор как он был поставлен плодовитым венгерским математиком Полом Эрдёшем и двумя сотрудниками в 1993 году. Увлечение Эрдёша множествами Сидона можно проследить до разговора, который он имел в 1932 году с их изобретателем Саймоном Сидоном, который в то время интересовался пониманием скорости роста этих множеств. (Позже Эрдёш назовет Сидона «более сумасшедшим, чем средний математик», что он почти наверняка имел в виду как комплимент.)

Множества Сидона возникают в различных математических контекстах, включая теорию чисел, комбинаторику, гармонический анализ и криптографию, но простой вопрос о том, насколько большими они могут стать, был непреходящей загадкой, над которой Эрдёш размышлял на протяжении большей части своей карьеры. Эрдёш рано понял, что наборы Сидона чрезвычайно трудно масштабировать. В 1941 году он и еще один математик доказанный что наибольшее возможное множество Сидона, все члены которого меньше некоторого целого числа N должно быть меньше квадратного корня из N плюс член, который растет пропорционально корню четвертой степени из N. (К 1969 году Бернт Линдстрём показал, что он меньше, чем $latex sqrt{N}+sqrt[4]{N}+1$, а в 2021 году другая группа математиков ужесточил связанный до $latex sqrt{N}+0.998 умножить на sqrt[4]{N}$.) Другими словами, наборы Сидона должны быть разреженными.

Давно известно, что множество Сидона не может быть асимптотическим базисом второго порядка, где любое целое число может быть представлено в виде суммы не более чем двух чисел. (Например, нечетные числа образуют основу порядка 2.) Как объяснил Пилат, это настолько просто показать, что математики даже не удосужились это записать: «То, что порядок 2 невозможен, вероятно, было известно намного раньше, чем это было явно написано в литературе». Он объяснил, что это связано с тем, что «последовательности Сидона не могут превышать определенную плотность, в то время как асимптотические базы порядка 2 всегда плотнее этого порога, поэтому два свойства не могут сохраняться одновременно».

Обычно считалось, что по множеству Сидона можно построить асимптотический базис третьего порядка, но доказательство этого было другим делом. «Люди считали, что это должно быть правдой», — сказал советник Пилатта. Джеймс Мейнард. «Но были трудности с методами, которые мы использовали».

Некоторый прогресс был достигнут до того, как Пилатт принял вызов. В 2010 году венгерский математик Шандор Кишш показал что множество Сидона может быть асимптотическим базисом 5-го порядка — это означает, что любое достаточно большое целое число может быть записано как сумма не более чем пяти элементов множества — и в 2013 году Кисс и двое его коллег доказанный гипотеза об асимптотическом базисе порядка 4. Два года спустя испанский математик Хавьер Силлеруэло взял эти результаты шаг вперед, доказав, что можно построить множество Сидона, которое является асимптотическим базисом порядка 3 + e, это означает, что любое достаточно большое целое число N можно записать в виде суммы четырех элементов множества Сидона, причем один из них меньше N^e для сколь угодно малого положительного e.

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

Пилатт понял, что вероятностный метод зашел так далеко, как только мог. «Вы можете получить базис 4-го порядка, используя вероятностные методы, но вы не можете получить базис 3-го порядка», — сказал он. «Просто не получается».

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

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

Многочлен — это алгебраическое выражение, состоящее из суммы членов, каждое из которых является произведением постоянного коэффициента и одной или нескольких переменных, возведенных в неотрицательные целые степени. Термины можно комбинировать, используя сложение, вычитание и умножение. Например, 3x² + 22x + 35 — многочлен с тремя членами. Разложение полинома на множители означает его разложение на произведение других, более простых полиномов. В этом примере 3x² + 22x + 35 = (x + 5) (3x + 7). Неприводимый многочлен — тот, который нельзя разложить на множители — это аналог простого числа.

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

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

«Я был очень счастлив, — сказал Пилатте. «Я присоединяюсь к группе людей, которые решили проблему Эрдёша, и это весело».

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

У задач Эрдёша есть сверхъестественная способность обнаруживать связи между предположительно не связанными разделами математики, и открытия, которые математики делают, пытаясь ответить на них, часто более значимы, чем сами ответы. «Они обманчивы в том, насколько они глубоки, и решение Седрика — отличный тому пример», — сказал Блум. «Я уверен, что Эрдёш был бы в восторге».

Исправление: 5 июня 2023
В этой статье изначально был приведен пример набора Сидона, который на самом деле не является набором Сидона. Этот пример был удален.