Все, расходимся

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

80 лет на первом этаже

Представьте, что вы стоите на первом этаже башни, бесконечно уходящей ввысь и вглубь. Каждую минуту приходит лифт, который может отвезти вас на один этаж вверх или вниз — направления движения лифтов заранее известны, но вам неподвластны. Допустим, вы хотите убраться как можно дальше от поверхности, скажем, на С этажей — не важно, в каком направлении. По правилам, вы можете выбрать любое число d, и входить в каждый d-й приходящий лифт. Можно ли выбрать такое d и такое k, что через k поездок вы уедете как минимум на C этажей (как уже говорилось, в любом направлении) от первоначального?

Этот вопрос, конечно, в несколько более математической форме, поставил в начале 1930-х годов знаменитый венгерский математик Пауль Эрдёш — большой мастер выдумывать простые на вид, но чрезвычайно сложные для решения математические задачи. Гипотезу Эрдёша о несоответствии (или о расхождении) можно сформулировать так: пусть {x

} — последовательность, состоящая из чисел 1 и −1 — это направления приходящих лифтов. Тогда для любого наперед заданного С найдутся такие k и d, что

Говорят, эта гипотеза была одной из любимых задачек Эрдёша, она вошла в число тех проблем, за который венгерский математик назначил премию из своего кармана в размере 500 долларов. Пауль Эрдёш умер в 1996 году — и ни при его жизни, но много лет позже, до самого недавнего времени, никто не мог даже близко претендовать на заветный чек за доказательство гипотезы о расходимости. Как сказал в интервью изданию Quanta специалист по теории чисел Эндрю Грэнвиль, «Ее многие пробовали на зуб, но всем пришлось отступить. Эта задача — из тех, по которым даже не было написано ни одной толковой статьи, просто потому, что никому в голову не пришло ни одной умной идеи».

Пятый проект и протеже Эрдёша

В 2009 году британский математик, филдсовский медалист Тимоти Гауэрс запустил математическую онлайн коллаборацию, получившую название Polymath Project. Его идеей было воспользовавшись возможностью удобного общения в интернете, объединить математиков в работе над любопытными нерешенными проблемами, в основном, в области теории чисел. Первый проект коллаборации (он касался теоремы Хэйлза-Джуитта) увенчался успехом, второй и третий со временем заглохли, четвертый, целью которого было создать алгоритм, находящий простое число, лежащее между n и 2n не дал решения, но в процессе работы коллабораторам удалось придумать кое-что интересное, чего хватило на публикацию в приличном научном журнале.
В самом начале 2010 года пришло время выбирать тему нового проекта, и Гауэрс стал предлагать в своем блоге разные варианты. Одним из них и была гипотеза Эрдёша о расходимости. Уже 6 января Гаэрс написал: «Экстренный пост: пока я был в отпуске и грелся под солнцем в Люксоре, число комментариев к посту про гипотезу Эрдёша и расходимость зашкалило». Старая венгерская головоломка волновала очень многих! В итоге именно эта задача и была выбрана в качестве пятой проблемы Polymath project.
Кстати, в том же «экстренном» посте Гаэерс замечает, что самая длинная известная на тот момент последовательность из ±1, в которой при любом d сумма членов с номерами 1d, 2d, 3d и т.д. по модулю не превосходит 2, была длинной всего в 1124 символа. Действительно, тогда, почти через 80 лет после появления гипотезы о расходимости, она не была доказана даже для простейшего случая C=2, другими словами, никто не знал, для каждой ли комбинации движения лифта найдется такое d, что выбирая каждый d-й лифт, вы со временем сможете уехать хотя бы на два этажа вверх или вниз.
Polymath начал работу, но спустя два года активность постепенно затухла — в сущности, у коллаборантов не получалось ничего путного. Впрочем, Тимоти Гауэрс не раз отмечал, что изначально видел значение Polymath project не в том, чтобы находить окончательные решения сложных задач, а в том, чтобы совместно специалисты из разных математических областей ускоренно проходили первый этап работы над проблемой — вычленение разумных и бесполезных подходов, развитие своеобразной математической интуиции о предмете. Тут пора заметить, что одним из самых деятельных участников polymath5 был молодой австралийский математик Теренс Тао — к тому времени уже лауреат Филдсовской медали, как и сам Тимоти Гауэрс. У Тао могла быть особенная задача решить любимую задачу Эрдёша — он познакомился с великим венгром в десятилетнем возрасте (тогда же став самым молодым в истории участником Международной математической олимпиады), а в 17 лет получил от него рекомендательное письмо для поступления в Принстонский университет.

Недалекий лифт и счастливый учитель

В начале 2014 года два математика российского происхождения, работающие в Университете Ливерпуля, Алексей Лисица и Борис Конев опубликовали работу, в которой было доказано, что все последовательности ±1 из как минимум 1161 элемента удовлетворяют условию гипотезы Эрдёша при C=2 — это позволило закрыть гипотезу Эрдёша для случая двух этажей. Оба ученых работают в области компьютерных наук, и их доказательство использовала тяжелейший компьютерный расчет — с помощью так называемого алгоритма решения задач булевой сложности. В результате 6-часового вычисления были получены данные общим объемом в 13 гигабайт — больше, чем объем информации во всей Википедии. Хотя в состоятельности доказательства Лисицы и Конев никто всерьез не сомневался, невозможность проверить выкладки без компьютера многих математиков смущала.

В то время Теренс Тао, как и большинство остальных участников polymath6, переключился на работу над другими задачами. Еще работая над гипотезой о расходимости, Тао сумел показать, что достаточно проверить условия задачи только для последовательностей специального вида: тех, у которых на позициях с простыми номерами стоят произвольно +1 или −1, а на любой позиции с номером ab стоят произведения членов последовательности с номером a и с номером b (например, если x

=1, а x

=-1, то x

=-1). Последовательности, описываемые таким свойством, называются мультипликативными, это важный и глубокий объект, представляющий интерес далеко за пределами гипотезы о расходимости.

Но и в контексте гипотезы Эрдёша, мультипликативные последовательности обладают замечательным свойством: если выбрать какое-то d и брать каждый d-й член последовательности, получится последовательность либо в точности совпадающая с исходной, либо отличающаяся от нее умножением на −1. Это, в свою очередь значит, что если лифты увозили вас далеко от поверхности без всяких пропусков, то то же самое будет выполняться для поездок с любыми регулярными пропусками. Именно благодаря этой особенности, достаточно доказывать гипотезу Эрдёша только для них — такой вывод Тао смог сделать с помощью широко используемого в теории чисел преобразования Фурье.

В январе этого года математики Каиса Матомаки из университета Турку и Максим Радживилл из Университета Ратгерса опубликовали

о свойствах мультипликативных последовательностей. Им удалось обнаружить определенную взаимосвязь между членами, стоящими на близких позициях. Матомаки и Радживилла эта тема интересовала в связи с теоретико-числовыми вопросами, достаточно далекими от гипотезы Эрдёша. В частности, они изучали свойства мультипликативных последовательностей в контексте функции Лиувилля — последовательности, на d-й позиции которой стоит 1, если число простых сомножителей d четно и −1, если оно нечетно (легко понять, что такая функция мультипликативна).

Теренс Тао заинтересовался этой работой и 4 сентября на сервер препринтов arxiv.org была выложена уже совместная работа австралийца с Матомаки и Раджвиллом. Об этом Тао рассказал несколько дней спустя

.

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

(обладатель степени Ph.D. по математике из университета Тюбингена), который

: «Рассуждения в духе судоку напоминают мне проект Polymath по доказательству гипотезы Эрдёша о расходимости [...] Нельзя ли использовать/адаптировать/обобщить результаты Матомаки и Радзивилля для этой задачи или это безнадежно?».

Вслед за комментарием Строински тот же пост Тао прокомментировал пользователь с ником «kodlu», написавший «Присоединяюсь к вопросу Строински». Тао ответил обоим — к вопросу Строински он оставил пространный скептический комментарий, но 10 часов спустя ответил и kodlu: «хмм, вообще-то, судя по всему есть связь между гипотезой Эрдёша и тем, о чем мы (с Мотомаки и Радзвиллем — прим. ред.) писали в нашей предыдущей статье, а именно, с гипотезой Эллитота [...] Напишу об этом подробнее в следующем посте».

Меньше чем через две недели, 19 сентября, на arxiv.org появилась

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

Энтропия и антиглобализм

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

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

В статье Тао не забыл поблагодарить Уве Строински, а также Тимоти Гауэрса и других участников проекта polymath5. Работа до сих пор остается в статусе препринта, но в ближайшее время должна выйти в математическом журнале

.

Любопытно, что запуск этого журнала был объявлен одновременно с тем моментом, когда Тао заканчивал свое доказательство. Новое издание (хотя его сложно назвать изданием в полном смысле) было придумано самими Тимоти Гауэрсом, давним оппонентом коммерческих научных журналов, приносящих огромные прибыли своим издателям, таким, как компании Elsiever и требующим от университетов приобретать комплексные подписки за десятки и даже сотни тысяч долларов ежегодно. Гауэрс предложил ученым объединиться, чтобы на общественных началах рецензировать работы, уже опубликованные на arxiv.org. В итоге

будет состоять просто из набора ссылок на отрецензированный редакторами проекта статей.

Первый номер виртуального журнала еще не вышел, по всей видимости, он будет включать работу, которой позавидовали бы лучшие научные издания — статью Теренса Тао с решением задачи, не поддававшейся никому из математиков на протяжении 83 лет.

А сам Тао сможет претендовать на 500 долларов — премию, установленную Паулем Эрдёшом, выплату которой взяли на себя его коллеги, друзья и ученики. Впрочем, когда журнал

у Тао, что он сделает с деньгами, математик ответил: «Даже пока Эрдёш был жив, по традиции его чеки никто не обналичивал. Обычно их вешали в рамочке на стену».

Тао тут, Тао там

В очередной записи своего блога Тимоти Гауэрс написал, что не может в точности оценить, насколько работа проекта polymath5 помогла Тао в доказательстве гипотезы Эрдёша о расходимости. В конце концов, основная идея, которой доказательство обязано проекту (сведение задачи к мультипликативным последовательностям) принадлежала самому Теренсу Тао. «Во всяком случае, я бы сказал, что polymath5 заинтересовал его в задаче и помог ему быстро преодолеть ту стадию, на которой проблему оценивают со многих сторон», — написал Гауэрс. В позапрошлом году Тао сам запустил очередной проект в рамках Polymath Project — polymath8, посвященный одной из самых известных нерешенных задач теории чисел и математики вообще — гипотезе о простых близнецах, согласно которой существует бесконечно много пар простых чисел, отличающихся друг от друга на 2.

Это коллаборация оказалась одной из наиболее продуктивных за всю историю Polymath project, усилиями ее многочисленных участников и самого Тао верхнюю границу на расстояние, разделяющее простые числа в бесконечном числе пар было снижено с 70 000 000 до 6. Для доказательства гипотезы осталось проделать сравнительно совсем небольшой путь — от 6 до 2. Об истории этого исследования мы расскажем в одном из ближайших материалов.

Сергей Немалевич