Оригинальная версия этой истории появилась в журнале Quanta.
Представьте себе причудливое тренировочное упражнение: группа бегунов начинает бег по круговой дорожке, причем каждый бегун поддерживает уникальный, постоянный темп. Окажется ли каждый бегун хотя бы однажды «одиноким» или относительно далеким от всех остальных, независимо от его скорости?
Математики предполагают, что ответ — да.
Проблема «одинокого бегуна» может показаться простой и несущественной, но в математике она возникает во многих вариантах. Это эквивалентно вопросам по теории чисел, геометрии, теории графов и т. д. — о том, когда можно получить четкую линию обзора в поле препятствий, или о том, где бильярдные шары могут двигаться по столу, или о том, как организовать сеть. "У нее так много граней. Она затрагивает очень много разных математических областей", - сказал Маттиас Бек из Государственного университета Сан-Франциско.
Для двух-трех бегунов доказательство гипотезы элементарно. Математики доказали это на четырех бегунах в 1970-х годах, а к 2007 году их стало уже семь. Но за последние два десятилетия никому не удалось продвинуться дальше.
Затем в прошлом году Матье Розенфельд, математик из Лаборатории компьютерных наук, робототехники и микроэлектроники Монпелье, подтвердил гипотезу для восьми бегунов. И через несколько недель студент второго курса Оксфордского университета по имени Танупат (Пол) Тракултонгчай, опираясь на идеи Розенфельда, доказал это на девяти и десяти бегунах.
Внезапный прогресс возобновил интерес к этой проблеме. «Это действительно квантовый скачок», — сказал Бек, не принимавший участия в работе. Добавление всего лишь одного бегуна делает задачу доказательства гипотезы «экспоненциально сложнее», сказал он. «Увеличить число бегунов с семи до десяти — это потрясающе».
Стартовый рывок
Поначалу проблема одинокого бегуна не имела ничего общего с бегом.
Вместо этого математиков интересовала, казалось бы, несвязанная проблема: как использовать дроби для аппроксимации иррациональных чисел, таких как пи, — задача, имеющая огромное количество приложений. В 1960-х годах аспирант Йорг М. Уиллс предположил, что метод, разработанный столетней давности, является оптимальным и что нет никакого способа улучшить его.
В 1998 году группа математиков переписала эту гипотезу на языке бега. Скажем, N бегунов стартуют с одного и того же места по круговой дорожке длиной в 1 единицу, и каждый бежит с разной постоянной скоростью. Гипотеза Уиллса эквивалентна утверждению, что каждый бегун всегда в какой-то момент оказывается одиноким, независимо от скорости других бегунов. Точнее, каждый бегун в какой-то момент окажется на расстоянии не менее 1/N от любого другого бегуна.
Когда Уиллс увидел статью об одиноком бегуне, он отправил электронное письмо одному из авторов, Луису Годдину из Университета Саймона Фрейзера, чтобы поздравить его с «этим чудесным и поэтичным именем». (Ответ Годдина: «О, ты еще жив».)
Математики также показали, что проблема одинокого бегуна эквивалентна еще одному вопросу. Представьте себе бесконечный лист миллиметровой бумаги. В центре каждой сетки поместите небольшой квадрат. Затем начните с одного из углов сетки и нарисуйте прямую линию. (Линия может указывать в любом направлении, кроме идеально вертикального или горизонтального.) Насколько большими могут стать меньшие квадраты, прежде чем линия дойдет до одного из них?
По мере того как версии проблемы одинокого бегуна распространялись в математике, интерес к этому вопросу рос. Математики доказали разные случаи гипотезы, используя совершенно разные методы. Иногда они полагались на инструменты теории чисел; в других случаях они обращались к геометрии или теории графов.
Но это означало, что у них не было общей стратегии решения проблемы. Скорее, у них была куча умных, но специальных техник, которые могли сработать, скажем, для четырех бегунов, но не для пяти. С каждым дополнительным бегуном
, им пришлось вернуться на стартовую линию.
К середине 2000-х годов математики доказали, что когда по дорожке бегут семь или меньше бегунов, каждому из них в конечном итоге становится одиноко. Они также нашли способы упростить проблему. Например, они поняли, что им не нужно доказывать гипотезу для всех (бесконечно многих) комбинаций скоростей. Вместо этого, если бы они могли показать, что это верно для любой комбинации целочисленных скоростей, это должно было бы быть верно в более широком смысле; они могли игнорировать дроби и иррациональные числа.
Это была гораздо более простая задача, но она по-прежнему подразумевала работу с бесконечно большим числом возможных скоростей. Требовалось нечто большее.
Ограничения скорости
В 2015 году Теренс Тао из Калифорнийского университета в Лос-Анджелесе посеял первое семя. Он показал, что если гипотеза одинокого бегуна справедлива для относительно низких скоростей, то она справедлива и для высоких скоростей. Для любого заданного количества бегунов математикам придется учитывать целочисленную скорость только до определенного порога.
Это свело проблему к конечному числу вычислений — по крайней мере, теоретически. На практике, даже когда вы имеете дело всего с несколькими бегунами, количество комбинаций скоростей, которые вам нужно проверить, по-прежнему «астрономично и совершенно непрактично», — сказал Ноа Кравиц из Оксфордского университета.
Достижения Тао в конечном итоге привлекли внимание Розенфельда, которого интересовали доказательства, использующие компьютер для проверки множества примеров.
Он переформулировал проблему, рассмотрев возможные контрпримеры к этой гипотезе: какими характеристиками должна обладать скорость бегунов, чтобы хотя бы один бегун никогда не оставался один?
Оказалось, что их скорость придется сильно ограничить. Розенфельд использовал компьютерную программу, а также идеи теории чисел, чтобы показать, что если он умножит все скорости вместе, их произведение должно будет делиться на определенные простые числа. Теперь все, что ему нужно было сделать, это доказать, что никакая комбинация скоростей не может удовлетворить этому условию.
Для этого он вернулся к модифицированной версии порога Тао. Затем он переписал ее в терминах произведения скоростей: если гипотеза одинокого бегуна верна для продуктов до заданного размера, она должна быть верной и в целом. Это означало, что если бы гипотеза была ложной, можно было бы найти контрпример с произведением ниже порогового значения.
Но Розенфельд уже показал, что в любом контрпримере произведение должно делиться на все эти простые числа. Такой продукт должен был бы быть массовым. На самом деле настолько массивным, что он намного превысит порог.
Другими словами, контрпример гипотезе об одиноком бегуне не может существовать — по крайней мере, для восьми бегунов. Предположение оказалось верным.
Вне маршрута
Розенфельд начал думать о том, как распространить свое доказательство на девять бегунов. Тем временем Кравиц увидел работу Розенфельда и показал ее многообещающему студенту Полу Тракултонгчаю, которого он обучал в Оксфорде. Он посоветовал Тракултонгчаю поработать над гипотезой для девяти бегунов.
Тракултонгчай использовал общий подход Розенфельда, но разработал более эффективную вычислительную технику для точного определения простых делителей, которые должны были бы иметь контрпримеры. Это позволило ему быстрее исключить все противоположные примеры как для девяти, так и для 10 бегунов: гипотеза была верной в обоих случаях. (Розенфельд независимо доказал эту гипотезу и для девяти бегунов, всего через несколько дней после того, как это сделал Тракултонгчай. Он был рад видеть взрывной прогресс другого математика. Но «в то же время я был немного расстроен», — сказал он со смехом.)
Методы Розенфельда и Тракултонгчай слишком дороги в вычислительном отношении, чтобы их можно было использовать для большего количества бегунов, в результате чего они застревают на следующем случае задачи. «Для того, чтобы достичь 11, я думаю, вам нужен совершенно новый взгляд на вещи.
держись за вещи, — сказал Тракултонгчай.
Но математики воодушевлены этими недавними достижениями, а также тем фактом, что один подход позволил решить три случая одновременно, тогда как раньше каждый новый случай требовал совершенно нового доказательства. «Я действительно вижу новый способ понять всю гипотезу с помощью этой новой идеи», — сказал Маттиас Шимура из Университета Ростока в Германии.
Хотя до доказательства всей гипотезы все еще далеко (и математики пока не пришли к единому мнению, будет ли она справедлива для каких-либо бегунов N), «все начинает двигаться после того, как какое-то время не двигалось», — сказал Кравиц.
Вдохновленные новыми результатами, Шимура и другие организуют семинар по гипотезе одинокого бегуна, который пройдет в Ростоке в октябре этого года. Он соберет вместе исследователей из разных областей, в которых появляется эта гипотеза. Есть надежда, что они подойдут к проблеме с разных точек зрения и «общаются и объединяют различные области», сказал Шимура, чтобы найти потенциальное доказательство или контрпример.
«Я убежден, что проблема будет решена», — сказал Уиллс. «Но это может занять еще около 20, 30 лет».
Оригинальная история перепечатана с разрешения журнала Quanta Magazine, редакционно независимого издания Фонда Саймонса, чья миссия состоит в том, чтобы улучшить общественное понимание науки путем освещения исследовательских разработок и тенденций в области математики, физических наук и наук о жизни.
