Величайшие математические задачи Стюарт Иэн
Если все они квадратные, то результат будет 2 2 … 2, т. е. степень двойки. Поэтому, если построение существует, n 1 должно быть степенью двойки. Однако этого условия не всегда достаточно. Если n = 9, n 1 = 8, а это степень двойки. Но Гаусс выяснил, что для правильного девятиугольника построения не существует, поскольку 9 — не простое число{12}. А как насчет следующего шага, на котором мы решаем систему из четырех квадратных уравнений? Степень n 1 соответствующего объединенного уравнения равна 2 2 2 2 = 16. Тогда n = 17, а это простое число.
К этому моменту Гаусс, вероятно, уже понял, что наткнулся на что-то интересное, но оставался еще один технический момент, который вполне мог все испортить. Гаусс убедился, что для существования построения правильного многоугольника с простым числом сторон это простое число должно равняться степени двойки плюс 1. Получалось, что это условие необходимо для существования построения: если оно не выполняется, такого построения не существует. Однако вполне могло оказаться, что этого условия недостаточно; в самом деле, существует множество уравнений 16-й степени, которые не сводятся к системе из четырех квадратных уравнений.
Однако был и повод для оптимизма — греческие построения. Какие простые числа там фигурировали? Только три из них: 2, 3 и 5. Все они на единицу больше какой-либо степени двойки, а именно 20 + 1,21 + 1 и 22 + 1. Алгебра, связанная с пятиугольником, дает дополнительную пищу для размышлений. Обдумывая все это, Гаусс доказал, что многочлен 16-й степени, соответствующий правильному 17-угольнику, действительно может быть сведен к системе квадратных уравнений. Поэтому построение правильного 17-угольника при помощи линейки и циркуля обязательно должно существовать. Аналогичным методом удалось доказать, что то же верно для любого случая, когда количество сторон является простым числом, на 1 превосходящим некоторую степень двойки. Вообще, эта идея наглядно свидетельствует, насколько хорошо Гаусс понимал математические закономерности. В основе их лежат некоторые общие теоремы теории чисел, в которые я сейчас не буду вдаваться; замечу только, что все это не случайно и у этих закономерностей существуют серьезные структурные причины. Просто надо быть Гауссом, чтобы их заметить.
Гаусс не составил полного алгоритма такого построения, но вывел формулу для решений уравнения 16-й степени. А имея формулу, можно при большом желании придумать и построение{13}. Публикуя свои идеи в «Арифметических исследованиях», он опустил несколько подробностей, но заявил, что обладает полным доказательством. Это грандиозное открытие убедило Гаусса в том, что лучше посвятить жизнь математике, а не языкам. Герцог по-прежнему не оставлял Гаусса без финансовой поддержки, но молодому человеку хотелось чего-то более стабильного. Когда астроном Джузеппе Пиацци открыл первый астероид — Цереру, — ученым удалось провести всего несколько наблюдений, прежде чем новооткрытый мир скрылся в сиянии Солнца. Астрономы тревожились, что не смогут вновь найти его. Проявив чудеса изобретательноси и использовав новую методику расчета орбит, Гаусс предсказал, где новооткрытое небесное тело появится вновь, и оказался прав. В результате он получил место профессора астрономии и директора Геттингенской обсерватории и оставался на этом посту до конца своих дней.
Оказалось, что 17 — не единственное новое число такого типа. На сегодня известны еще два подобных числа: 28 + 1 = 257 и 216 + 1 = 65 537. (Еще немного алгебры — и можно показать, что степень двойки, фигурирующая в этом выражении, сама должна быть степенью двойки; в противном случае результат не будет простым.) Однако на 16 эта закономерность прекращается, и 232 + 1 = 4 294 967 297, что равно 641 6 700 417, а значит, не является простым числом. Известно, что так называемые числа Ферма 22n + 1 не являются простыми для n = 5, 6, 7, … и так до 32. Известно также, что многие более крупные числа Ферма тоже не простые. Вообще, больше простых чисел Ферма пока не найдено, но вполне возможно, что они все же существуют. Известно построение для правильного 257-угольника. Один математик посвятил много лет поиску построения для 65 537-угольника — правда, эта задача представляется несколько бессмысленной, и, кроме того, в его результатах есть ошибки{14}.
Итак, основной вывод из проведенного Гауссом анализа состоит в том, что правильный многоугольник может быть построен при помощи линейки и циркуля в том и только том случае, когда число его сторон представляет собой произведение степени двойки и различных нечетных простых чисел Ферма. В частности, правильный девятиугольник так построить нельзя. Из этого сразу следует, что по крайней мере один угол невозможно разделить натрое построением: ведь угол равностороннего треугольника равен 60°, а одна треть такого угла — это 20°. Но, имея такой угол, несложно построить правильный девятиугольник. Следовательно, это невозможно, и общего метода трисекции угла при помощи геометрического построения не существует.
Гаусс, записывая доказательства, опустил немало подробностей, и математики не могли просто так поверить ему на слово. В 1837 г. французский математик Пьер Ванцель опубликовал полное доказательство гауссовой характеризации пригодных для геометрического построения правильных многоугольников и сделал вывод о невозможности трисекции произвольного угла при помощи линейки и циркуля. Он доказал также невозможность построения куба объемом вдвое больше данного (т. е. доказал неразрешимость еще одной древнегреческой задачи, известной как «задача об удвоении куба»).
Причина того, что задачи трисекции угла и удвоения куба оказались неразрешимыми, заключается в том, что задействованные в них длины фигурируют в неприводимых кубических уравнениях — уравнениях третьей степени. Раз 3 не является степенью двойки, это все решает. Однако этот метод, на первый взгляд, не работает для квадратуры круга, причем по достаточно интересным причинам. Круг единичного радиуса имеет площадь , а сторона квадрата той же площади равна . Геометрические построения для квадратного корня существуют, как и построения для квадратов, так что квадратура круга, по существу, сводится к тому, чтобы взять отрезок длиной 1 и построить отрезок длиной . Конечно, если является решением неприводимого кубического уравнения — или любого другого неприводимого уравнения, чья степень не является степенью двойки, — то метод Ванцеля доказал бы, что квадратура круга невозможна.
Однако никто не слышал ни об одном алгебраическом уравнении, решением которого было бы в точности , не говоря уж об уравнении степени, не являющейся степенью двойки. Приближенное значение 22/7 удовлетворяет уравнению 7x 22 = 0, но на самом деле эта дробь немного больше , так что это никак нам не поможет. Если бы можно было доказать, что такого уравнения не существует, — а многие подозревали, что так оно и есть, поскольку если бы уравнение существовало, то его бы нашли, — то из этого следовала бы и невозможность решения задачи квадратуры круга. К несчастью, никто не мог доказать, что такого уравнения не существует. Алгебраический статус пребывал в состоянии неопределенности. В конце концов этот вопрос все же удалось решить, но при помощи методов, далеко выходящих за пределы не только геометрии, но и алгебры.
Чтобы разобраться в существе дела, нам придется начать с более простой концепции. В математике существует важное различие между числами, которые можно точно выразить при помощи дроби p/q, где p и q — целые числа, и числами, которые невозможно выразить таким образом. Первые называются рациональными (поскольку представляют собой отношение, т. е. ratio, целых чисел), а последние — иррациональными. Так, приближенное значение (22/7) рационально. Существуют и более точные приближения; знаменитое 355/113 соответствует до шестого знака после запятой. Однако известно, что никакая дробь не может выразить точно; число иррационально. Это свойство, о котором математики давно догадывались, первым доказал швейцарский математик Иоганн Генрих Ламберт в 1768 г. Его доказательство основано на хитрой формуле для функции тангенса в тригонометрии, где тангенс выражается в виде цепной (непрерывной) дроби — бесконечного множества обычных дробей{15}. В 1873 г. Шарль Эрмит нашел более простое доказательство, основанное на аналитических формулах, которое доказало иррациональность не только , но и . Так что помимо всего прочего не является корнем квадратным из какого-то рационального числа.
Ламберт выдвинул и более серьезные гипотезы. В той же статье, где доказывалась иррациональность , он предположил, что число трансцендентно, т. е. не является решением никакого полиномиального уравнения с целыми коэффициентами. Оно выходит за рамки алгебраического выражения. Более поздние исследования доказали правоту Ламберта. Сделано это было в два этапа. Разработанный Эрмитом новый метод доказательства иррациональности подготовил площадку, намекнув, что удачной стратегией здесь может оказаться исчисление, а точнее, его более строгая версия — анализ. Но Эрмит развил эту идею дальше и нашел чудесное доказательство трансцендентности другого знаменитого и очень любопытного числа e — основания натуральных логарифмов. Численно e приблизительно равно 2,71828, и, пожалуй, оно еще важнее, чем . Эрмитово доказательство трансцендентности волшебно, как кролик, с помпой извлекаемый фокусником из цилиндра математического анализа. Сам кролик — это сложная формула, связанная с гипотетическим алгебраическим уравнением, корнем которого, согласно первоначальному предположению, является e. При помощи алгебраических методов Эрмит доказывает, что эта формула эквивалентна некоему ненулевому целому числу. При помощи математического анализа он доказывает, что число это должно лежать между 1/2 и 1/2. Поскольку единственным целым числом в этом интервале является 0, получаем противоречие. Следовательно, предположение о том, что e является решением некоего алгебраического уравнения, неверно, а значит, e трансцендентно.
В 1882 г. Фердинанд фон Линдеман несколько усовершенствовал метод Эрмита и доказал, что если ненулевое число является решением некоего алгебраического уравнения, то e в степени этого числа не является решением никакого алгебраического уравнения. Затем он воспользовался соотношением, известным еще Эйлеру и связывающим , e и мнимое число i, — знаменитой формулой ei = 1. Предположим, что удовлетворяет некоему алгебраическому уравнению. То же можно сказать и про i, а по теореме Линдемана получим, что 1 не удовлетворяет никакому алгебраическому уравнению. Это очевидно неверно: 1 является решением уравнения x + 1 = 0. Единственный выход из этого логического противоречия заключается в том, что не удовлетворяет никакому алгебраическому уравнению, т. е. трансцендентно. А это означает, что задача квадратуры круга неразрешима.
Путь от евклидовой геометрии к доказательству Линдемана получился долгим кружным. Но математики, хоть и через две с лишним тысячи лет, все же добились своего. Однако вся эта история не просто сообщает нам о невозможности квадратуры круга. Это наглядный урок того, как вообще решаются великие математические задачи. Во-первых, математикам потребовалось точно сформулировать, что они имеют в виду, говоря о «геометрическом построении». Им пришлось определить общие черты таких построений и понять, как эти черты ограничивают возможности построений. Для поиска общих свойств потребовалось связать геометрию с другой областью математики — алгеброй. Но при решении алгебраических задач, даже не самых сложных, таких как построение правильных многоугольников, не обойтись без теории чисел. Сложный случай числа потребовал дополнительных новшеств, и задачу пришлось перенести в еще одну область математики — математический анализ.
Ни один из перечисленных шагов не был простым или очевидным. Уже после того, как основные идеи были высказаны, потребовалось еще около 100 лет, чтобы окончательно доработать доказательство. Математики, бившиеся над этой задачей, были лучшими умами своего времени, а по крайней мере один из них входит в число величайших умов всех времен. Решение подобных задач помимо глубокого понимания математики требует настойчивости и изобретательности. Иногда на это уходят годы сосредоточенных усилий, на первый взгляд, по большей части бесплодных. Но представьте, что чувствует математик, когда его настойчивость приносит плоды, и ему наконец удается расколоть крепкий орешек, над которым человечество билось не один век. Как сказал президент Джон Кеннеди в 1962 г. в одной из речей, посвященных Лунной программе, «мы решили… это сделать… не потому, что это просто, а потому, что это сложно».
Мало что в математике имеет конец, и история числа — не исключение. И сегодня время от времени появляются поразительные новые открытия, имеющие к нему отношение. В 1997 г. Фабрис Беллар объявил, что триллионная цифра числа в двоичном выражении — единица. Замечательным это заявление делает не собственно факт. Поразительно то, что он не вычислял ни одной из предыдущих цифр. Он просто извлек одну конкретную цифру, что называется, из воздуха.
Такой расчет оказался возможен благодаря любопытной формуле для , которую открыли Дэвид Бэйли, Питер Боруэйн и Саймон Плафф в 1996 г. Она может показаться несколько сложноватой, но все же посмотрим:
Большой знак означает «просуммировать» на заданном диапазоне. Здесь n изменяется от 0 до бесконечности (). На самом деле Беллар пользовался формулой, которую вывел сам с использованием аналогичных методов и расчет по которой ведется чуть быстрее:
Ключевая особенность этих формул в том, что многие из используемых в них чисел — 1, 4, 32, 64, 256, а также 24n и 210n — являются степенями двойки, что, конечно, сильно упрощает расчеты в двоичной системе, которая используется для внутренних операций в компьютерах. После этого открытия хлынул целый поток новых формул для и некоторых других интересных чисел. Рекорд вычисления одиночных двоичных цифр числа обновляется регулярно: в 2010 г. Николас Ши из Yahoo рассчитал двухквадрильонную двоичную цифру , которой оказался 0.
При помощи тех же формул можно находить отдельные цифры числа в арифметических операциях с основаниями 4, 8 и 16. Ни для каких других оснований ничего подобного не известно; в частности, мы не можем вычислять десятичные цифры по отдельности. Существуют ли в принципе такие формулы? До открытия формулы Бэйли — Боруэйна — Плаффа никому даже в голову не приходило, что можно это делать хотя бы в двоичной системе.
4. Загадки картографии. Теорема о четырех красках
Многие великие задачи уходят корнями в глубокие и сложные вопросы давних и хорошо известных областей математики. Это те случаи, когда серьезные препятствия вдруг возникают уже после того, как эта область была тщательно изучена. Они, как правило, имеют технический характер, и все заинтересованные лица заранее знают, что они очень сложны, — еще бы, ведь многие специалисты пытались одолеть их и потерпели неудачу. При этом для соответствующей области часто уже разработаны множество мощных методик и объемный математический аппарат, которым может воспользоваться всякий подготовленный человек, но при этом, если задача до сих пор не решена, значит, все очевидные способы воспользоваться этими методиками уже испробованы и не сработали. Так что для решения этой задачи нужно либо использовать испытанные инструменты каким-то другим способом, либо изобретать новые.
Бывало и так, и этак.
Но существуют великие задачи, у которых все иначе. Они появляются из ниоткуда — небрежный чертеж на песке, заметка на полях книги, мимолетная причуда. Их формулировки просты, но поскольку вокруг них нет обширного математического фона, то нет и традиционных методов и подходов к ним. Иногда проходит много лет, прежде чем становится ясен уровень сложности задачи: кажется, что должен существовать какой-то хитрый, но несложный трюк, при помощи которого ее можно решить, и что решение не займет и полстранички. Задача о четырех красках относится именно к этой категории. Прошло не одно десятилетие, прежде чем математики начали осознавать, насколько она сложна. Мало того, большую часть этого времени все думали, что она уже решена, причем именно на нескольких страничках. Вообще, задача казалась второстепенной, и мало кто принимал ее всерьез, а когда это все же происходило, то в существовавшем вроде бы решении обнаруживались изъяны. Окончательное решение устранило все недостатки, но к тому моменту дискуссия стала настолько сложной, что пришлось привлекать на помощь мощные компьютеры.
В конечном итоге оба типа задач, несмотря на разное происхождение, схожи тем, что решение тех и других невозможно без новых подходов. Несмотря на то что задачи первого типа коренятся в хорошо изученных областях математики, традиционных методов для их решения не хватает. А задачи второго типа не принадлежат ни к одной известной области — более того, стимулируют возникновение новых, — и поэтому традиционных методов, которые можно было бы к ним применить, просто не существует. В обоих случаях решение задачи требует изобретения новых методов и установления новых связей с существующим массивом математических знаний.
Происхождение задачи о четырех красках известно, и оно — не математическое. В 1852 г. молодой южноафриканский математик и ботаник Фрэнсис Гутри, готовившийся к получению ученой степени по юриспруденции, попытался раскрасить графства на карте Англии. Он хотел быть уверенным, что любые два смежных графства можно будет раскрасить в разные цвета, чтобы границы между ними были хорошо различимы. Гутри выяснил, что для выполнения задачи ему будет достаточно четырех различных цветов, и после некоторого количества экспериментов убедил себя в том, что это заявление будет верным для абсолютно любой карты. Говоря о «смежных» графствах, он имел в виду, что эти графства имеют общую границу ненулевой длины; если же два графства соприкасались в точке или, к примеру, в нескольких изолированных точках, их можно было при необходимости раскрасить в один и тот же цвет. Без этой оговорки число цветов может быть бесконечным, поскольку в одной точке может встретиться неограниченное число регионов (см. рис. 8 слева).
Заинтересовавшись, не является ли его вывод известной математической теоремой, Гутри задал этот вопрос своему брату Фредерику, изучавшему в то время математику под руководством известного, но эксцентричного ученого Огастеса де Моргана в Университетском колледже Лондона. Де Морган не знал ответа на этот вопрос, поэтому написал еще более известному математику — ирландцу сэру Уильяму Гамильтону:
«Один мой студент [позже выяснилось, что это был Фредерик Гутри] попросил меня сегодня объяснить один факт, про который мне ничего не было известно, — и я до сих пор не уверен, что это действительно факт. Он говорит, что если некая фигура раздлена на части любым способом и ее части раскрашены по-разному, так что фигуры с общей границей в виде линии любой длины окрашены в разные цвета, то для этого может потребоваться четыре краски, но не больше… Вопрос: нельзя ли придумать случай для пяти или более красок… Что скажете? И был ли этот факт, если это правда, замечен ранее?»
Фредерик позже упоминал некое «доказательство», предложенное его братом, но говорил также, что основной идеей там был рисунок, примерно соответствующий рис. 8, а он доказывает лишь, что меньше, чем четырьмя красками, не обойдешься.
Ответ Гамильтона был краток: «Я вряд ли займусь в ближайшее время вашим “кватернионом” красок». В то время Гамильтон работал над алгебраической системой, которой суждено было на всю жизнь стать его пунктиком и любимым коньком. Это система, аналогичная комплексным числам, но включающая четыре типа чисел вместо двух (действительные и мнимые) в комплексной системе. Свои числа он называл «кватернионами». Предложенная им система до сих пор сохраняет свое значение в математике. Мало того, сегодня ее роль, вероятно, более важна, чем во времена Гамильтона. Но высот, о которых мечтал автор, она так и не достигла. Гамильтон просто пошутил в академическом стиле, употребив слово «кватернион» по отношению к четырем краскам. Долгое время действительно казалось, что между его системой и задачей о четырех красках нет никакой связи. Однако задачу можно переформулировать так, что она становится утверждением о кватернионах, так что Гамильтон, сам того не желая, попал в яблочко.
Де Морган, потерпев неудачу в поиске доказательства, рассказал о задаче всем своим знакомым математикам в надежде на то, что кто-нибудь сможет предложить полезную идею. В конце 1860-х гг. американский логик, математик и философ Чарльз Пирс заявил, что нашел решение задачи о четырех красках, а также ответы на аналогичные вопросы о картах на более сложных поверхностях. Предполагаемое доказательство так и не было опубликовано, но вряд ли доступные ему методы были адекватны задаче.
Хотя в задаче о четырех красках говорится вроде бы о картах, сама она не имеет применения в картографии. Практика раскраски карт отражает в основном политические различия, и если при этом соседние регионы должны иметь один цвет, то их и красят одинаково. Смысл этой задачи лежит в области чистой математики — новой области, которая тогда только начала развиваться — топологии. Это «геометрия на резиновом листе», в которой фигуры можно непрерывно деформировать любым способом. Но даже там задача о четырех красках не укладывалась в основное русло исследований, а представлялась всего лишь диковинкой.
Одним из пионеров топологии был Август Мёбиус, известный сегодня благодаря своей односторонней ленте (см. рис. 9). Модель такой ленты несложно изготовить: для этого нужно взять полоску бумаги, свернуть ее в кольцо, похожее на короткий толстый цилиндр, повернуть один из концов на 180° и склеить концы. Однажды друг Мёбиуса лингвист Бенджамин Вейске загадал ему загадку: может ли индийский царь разделить свое царство на пятерых сыновей так, чтобы часть, принадлежащая одному принцу, имела границу ненулевой длины с частями всех остальных? Мёбиус задал эту загадку своим студентам в качестве упражнения, но на следующей лекции извинился за то, что попросил их сделать невозможное. Подразумевалось, что он может доказать невозможность ее решения{16}.
Эту загадку трудно представить геометрически, поскольку формы отдельных частей могут, в принципе, быть очень сложными. Для успешного продвижения в решении этой задачи следует ввести серьезное упрощение: сказать, что существенно только то, какие регионы граничат и как их общие границы расположены относительно друг друга. Эта топологическая информация не зависит от конкретных форм и может быть представлена в четкой и простой форме, известной как граф, или в наши дни — сеть (это более выразительный термин).
Сеть — чрезвычайно простое понятие: набор вершин (они обозначаются точками), некоторые из которых связаны ребрами (обозначаются линиями). Возьмем произвольную карту (см. рис. 10 слева). Чтобы представить ее в виде сети, поставим в каждой области по точке (см. рис. 10 в середине). Там, где две области имеют общий участок границы, соединим соответствующие точки линией, проходящей через этот участок. Если две области имеют несколько общих участков границы, проведем через каждый по отдельной линии. Проделаем все это для всех областей и всех участков границы так, чтобы линии не пересекались друг с другом и не имели самопересечений, а встречались только в точках. Затем выбросим первоначальную карту и оставим себе только точки и линии. Это двойственная сеть — двойник нашей карты (см. рис. 10 справа).
Слово «двойственный» используется потому, что при этой процедуре области, линии и точки (пересечения областей) превращаются в точки, линии и области. Область на карте соответствует точке двойственной сети. Участок границы на карте соответствует линии двойственной сети; не той же самой линии, а линии, которая пересекает границу и связывает соответствующие точки. Точка, в которой на карте сходятся три или больше областей, соответствует области двойственной сети, ограниченной со всех сторон линиями. Так что двойственная сеть — сама по себе карта, поскольку линии здесь ограничивают области; кроме того, оказывается, что двойственной схемой к двойственной схеме является первоначальная карта плюс-минус кое-какие технические подробности, исключающие ненужные точки и линии.
Рассматривая двойственную сеть, задачу о пяти принцах можно сформулировать иначе: можно ли соединить пять точек на плоскости непересекающимися линиями? Ответ — нет, а ключ к нему — формула Эйлера, согласно которой, если карта на плоскости состоит из F участков (областей), E ребер (линий) и V узлов (точек), то F + V — E = 2. Здесь остальная плоскость, оставшаяся вне сети, считается одной большой областью. Эта формула в свое время стала первым указанием на то, что топологические вопросы достойны рассмотрения. Она вновь появится в главе 10.
Доказательство того, что задача о пяти принцах не имеет решения, начинается с предположения о том, что такое решение существует, и это приводит к противоречию. Любое решение должно иметь число точек V = 5. Поскольку каждая пара точек соединяется линиями, а точек у нас 10 пар, то E = 10. Тогда по теореме Эйлера F = E — V + 2 = 7. Области двойственной сети ограничены замкнутыми петлями линий, и каждую пару точек соединяет только одна линия, поэтому каждая из петель должна содержать по крайней мере три линии. Если областей семь, то линий получается по крайней мере 21… Правда, каждая из них считается дважды, поскольку разделяет две области. Так что линий по крайней мере 10,5. Число линий должно быть целым, значит, на практике у нас должно быть по крайней мере 11 линий. Однако мы уже знаем, что линий у нас 10. Это логическое противоречие доказывает, что такой сети не существует. Царь не сможет разделить свои земли так, как ему хочется.
В подобных рассуждениях обнадеживает то, что элегантные топологические методы позволяют нам доказывать интересные и неожиданные факты о картах. Однако, вопреки распространенному мнению, которое де Морган, судя по всему, разделял, невозможность решения задачи о пяти индийских принцах не доказывает теорему о четырех красках. Доказательство может быть неверным, даже если само умозаключение верно, или по крайней мере никому не известно о его неверности. Если где-то в предполагаемом доказательстве мне встретится треугольник с четырьмя сторонами, я прекращу читать, поскольку это доказательство неверно. При этом не имеет значения, что происходит в нем позже или какой из этого делается вывод. Наш ответ на загадку индийских принцев показывает лишь, что один из способов опровержения теоремы о четырех красках не работает. Однако из этого не следует, что не может работать какой-нибудь другой способ. В принципе, может существовать множество причин, по которым карту не удастся раскрасить в четыре цвета. Существование пяти областей, каждая из которых граничит со всеми остальными, лишь одна из этих потенциальных причин. Пока не доказано обратное, может существовать очень сложная карта, скажем, из 703 регионов, на которой, даже если вам удастся раскрасить в четыре цвета 702 из них, последний оставшийся все равно потребует пятой краски. Конечно, этот регион должен будет граничить по крайней мере с четырьмя другими, но это вполне представимо и не требует выполнения условий задачи о пяти принцах. Если бы подобная карта нашлась, она доказала бы, что четырех красок недостаточно. Любое доказательство должно исключить все подобные препятствия. И это утверждение сохраняет силу даже в том случае, если я не смогу продемонстрировать вам конкретный пример такой карты.
На какое-то время задача о четырех красках полностью пропала из виду, но в 1878 г. Артур Кейли упомянул ее на заседании Лондонского математического общества, и она вновь вызвала интерес. Несмотря на название, Общество это представляло всю британскую (или по крайней мере всю английскую) математику, а его основателем был де Морган. Кейли поинтересовался, удалось ли кому-нибудь получить решение этой задачи, и вскоре после заседания его вопрос был опубликован в журнале Nature. Годом позже он опубликовал обширную статью на эту тему в «Трудах Королевского географического общества»{17}. Поскольку речь в задаче вроде бы шла о картах, издание показалось подходящим для публикации. Может быть, статью автору даже заказали. Но на самом деле выбор оказался не слишком удачным — ведь картографам решение этой задачи не нужно и не интересно, разве что из чистого любопытства. По той же причине, к несчастью, мало кто из математиков заметил эту статью, а жаль: в ней Кейли объяснил, почему задача может оказаться сложной.
В главе 1 я писал, что доказательство чем-то напоминает сражение. В военном деле четко различаются тактика и стратегия. Тактика — это искусство выигрывать локальные сражения, а стратегия определяет общую структуру кампании. Тактика определяет передвижение каждой войсковой части; стратегия формирует обширные планы, в рамках которых на каждой стадии возможны самые разные тактические решения. Статья Кейли не блистала тактическими находками, но содержала легчайший намек на стратегию, которая по прошествии времени позволила расколоть этот орешек и решить задачу о четырех красках. Кейли заметил, что добавление областей последовательно, по одной, ничего не дает, если следовать очевидному ходу рассуждений. Но, может быть, если найти другой, менее очевидный ход, из этого что-нибудь получится.
Предположим, мы возьмем произвольную карту и уберем оттуда одну область — сольем ее с соседней или сожмем в точку. Предположим также, что получившуюся карту можно раскрасить в четыре цвета, и мы так и сделаем. А теперь вернем удаленную область на место. Если нам повезет, ее соседи окажутся раскрашенными только в три цвета. Тогда нам останется всего лишь закрасить восстановленную область четвертым — свободным — цветом. Кейли указал, что эта процедура может и не сработать, поскольку соседи нашей области могут оказаться раскрашенными в четыре разных цвета. Но это не означает, что все плохо. Такое препятствие можно обойти двумя способами: сделать вывод либо о том, что мы выбрали не ту область, либо о том, что мы неверно раскрасили уменьшенную карту.
Действуя на основании ничем не подтвержденных предположений (это очень эффективный способ формирования рабочих идей, хотя в какой-то момент их все равно придется обосновать), считаем, что подобные препятствия всегда устранимы. Тогда получается, что любую карту можно раскрасить в четыре цвета, если известно, что некую меньшую карту можно так раскрасить. Может показаться, что такой вывод ничего нам не дает: как мы узнаем, что какую-то меньшую карту можно раскрасить нужным образом? Ответ в том, что эту же процедуру можно применить к меньшей карте, а затем к еще меньшей карте… и т. д. В конце концов, мы доберемся до карты настолько маленькой, что в ней будет всего четыре области, и это гарантирует, что ее можно раскрасить в четыре цвета. Теперь пройдем тот же путь в обратном направлении, на каждом шагу раскрашивая карту чуть побольше, чем в прошлый раз, и, в конце концов, доберемся до первоначальной карты.
Подобные рассуждения называют «доказательством по индукции». Это стандартный метод доказательства наиболее формализованных формулировок, и логику, на которой он основан, можно сделать строгой. Предложенная Кейли стратегия доказательства становится более понятной, если переформулировать ее с использованием логически эквивалентной концепции минимального контрпримера. В данном контексте контрпримером можно считать любую гипотетическую карту, которую невозможно раскрасить в четыре краски. Такая карта будет минимальной, если любую меньшую карту (т. е. карту с меньшим числом областей) можно раскрасить нужным образом. Если хотя бы один контрпример существует, то должен существовать и минимальный контрпример: чтобы его найти, нужно просто взять контрпример с минимальным возможным числом областей. Поэтому если минимального контрпримера не существует, то контрпримеров не существует вообще. А если их нет, то теорема о четырех красках верна.
Доказательство по индукции сводится примерно к следующему. Предположим, мы можем доказать, что минимальный контрпример всегда можно раскрасить в четыре краски, если можно раскрасить так некую связанную с ним меньшую карту. Тогда минимальный контрпример не может считаться собственно контрпримером. Поскольку эта карта минимальна, все меньшие карты можно раскрасить в четыре краски, поэтому, исходя из утверждения, которое, согласно принятому нами предположению, может быть доказано, то же верно в отношении первоначальной карты. Следовательно, минимального контрпримера не существует, а значит, не существует контрпримеров вообще. Эта идея сдвигает фокус проблемы, позволяя рассматривать не все карты сразу, а только гипотетические минимальные контрпримеры, и определяет процедуру редукции — способ последовательно вывести четырехкрасочность первоначальной карты из четырехкрасочности некой соответствующей меньшей карты.
Но зачем возиться с минимальными контрпримерами, не лучше ли поискать обычные? Это вопрос методики. Хотя первоначально мы не знаем, существуют ли контрпримеры, одно из парадоксальных, но очень полезных свойств этой стратегии заключается в том, что мы можем многое сказать о том, как должны выглядеть именно минимальные контрпримеры, если они существуют.
Для этого необходима способность рассуждать логически о гипотетических вещах — жизненно важное умение для любого математика. Чтобы дать вам почувствовать характер процесса, я докажу теорему о шести красках. Для этого мы позаимствуем прием из загадки о пяти принцах и переформулируем все в терминах двойственной сети, в которой области становятся точками. В этом случае задача о четырех красках эквивалентна другому вопросу: если на плоскости задана сеть, линии которой не пересекаются, можно ли раскрасить в четыре цвета точки так, чтобы две точки, соединенные линией, всегда были разного цвета? Точно так же можно переформулировать задачу с любым количеством красок.
Чтобы проиллюстрировать мощь метода минимальных контрпримеров, я докажу с их помощью, что любую плоскую сеть можно раскрасить в шесть цветов. Здесь главным нашим инструментом вновь станет формула Эйлера. Для точки плоской двойственной сети соседними точками назовем те, что соединены с ней линиями. У каждой точки может быть и множество соседей, и всего несколько. Можно показать, что, в соответствии с формулой Эйлера, у некоторых точек должно быть мало соседей. Точнее говоря, в плоской сети все точки не могут иметь по шесть и больше соседей. Доказательство этого момента я поместил в примечание, чтобы не прерывать ход мысли{18}. Этот факт дает нам рычаг, необходимый для того, чтобы разбить задачу на более мелкие подзадачи. Рассмотрим гипотетический минимальный контрпример для теоремы о шести красках. Это сеть, которую невозможно раскрасить в шесть разных цветов, притом что любую меньшую сеть так раскрасить можно. А теперь я доказываю, что такая карта не может существовать. Согласно приведенному выше следствию из формулы Эйлера, в ней должна быть хотя бы одна точка, у которой пять или меньше соседей. Временно уберем эту точку и линии, соединяющие ее с соседями. В получившейся сети меньше точек, поэтому, исходя из минимальности контрпримера, ее можно раскрасить в шесть цветов. (Этот шаг, кстати говоря, мы не сможем сделать, если наш контрпример будет не минимальным.) А теперь вернем удаленную точку и ее линии на место. Эта точка имеет не более пяти соседей, так что шестой цвет для нее всегда найдется. Покрасим ее — и получим успешно раскрашенный в шесть цветов минимальный контрпример; но тогда получается, что это никакой не контрпример. Значит, минимальных контрпримеров для теоремы о шести красках не существует, а значит, теорема верна.
Это внушает оптимизм. До сих пор, насколько нам известно, для раскраски некоторых карт могло потребоваться 20 цветов, или 703, или несколько миллионов. Теперь мы знаем, что такие карты не более реальны, чем горшок золота под концом радуги. Мы знаем, что конкретного ограниченного числа красок точно хватит на любую карту. Это настоящий триумф метода минимальных контрпримеров. Математики, посмотрев на него, взялись за дело с еще большим энтузиазмом, надеясь усилить аргументацию и постепенно заменить шесть красок на пять, а если повезет, и на четыре.
Юристы иногда тоже интересуются математическими задачами. Адвокат по имени Альфред Кемпе присутствовал на том заседании, где Кейли упомянул задачу о четырех красках. В свое время он под руководством Кейли изучал математику в Кембридже, и за годы его интерес к этой науке нисколько не ослаб. Не прошло и года после заседания, а Кемпе уже убедил себя, что ему удалось справиться с задачей. Свое решение он опубликовал в 1879 г. в недавно основанном журнале American Journal of Mathematics. Еще через год он опубликовал упрощенное доказательство, где были исправлены некоторые ошибки, присутствовавшие в первом. Вот как он подошел к вопросу: «Очень небольшое изменение в части карты может привести к необходимости перекрашивать ее целиком. В результате достаточно сложного поиска мне удалось отыскать слабое звено, которое позволило одержать победу».
Я изложу идеи Кемпе в терминах двойственной сети. Опять же он начал с формулы Эйлера и следующего из нее вывода о существовании точки с тремя, четырьмя или пятью соседями. (Точка с двумя соседями лежит на линии и никак не влияет на структуру сети или карты: на нее можно просто не обращать внимания.)
Если существует точка с тремя соседями, то процедуру, которую я использовал для доказательства теоремы о шести красках, можно применить и к четырехкрасочному варианту. Удаляем саму точку и линии, которые в ней сходятся, раскрашиваем в четыре краски результат, возвращаем точку и линии на место и окрашиваем ее в оставшийся свободным цвет. Поэтому мы можем считать, что точки с тремя соседями не существует.
Если существует точка с четырьмя соседями, то вышеописанная методика не срабатывает, потому что при возвращении точки свободного цвета может и не оказаться. Кемпе придумал хитрый способ обойти это препятствие: он предложил так же точно удалить точку, но после этого поменять расцветку получившейся меньшей карты так, чтобы два из четырех ее бывших соседей получили один и тот же цвет. После такой модификации у соседей удаленной точки окажется не больше трех цветов — и в нашем распоряжении окажется свободный четвертый. Основная идея перекраски схемы по Кемпе заключается в том, что две соседние точки должны быть разных цветов — скажем, синего и красного, а еще в схеме используются зеленый и желтый. Если обе оставшиеся точки окажутся зелеными или желтыми, то второй цвет окажется свободным и может быть использован для удаленной точки. Исходя из этого, считаем, что одна из них зеленая, а вторая — желтая. Теперь найдем все точки, которые соединены с синей точкой последовательностью линий, проходящих только через синие и красные точки, и назовем их красно-синей цепочкой Кемпе{19}. По определению, любой сосед любой точки в цепочке Кемпе, не принадлежащий цепочке, должен быть зеленым или желтым, поскольку синий или красный сосед там уже есть. Обратите внимание, что замена цветов в пределах цепочки Кемпе (синий на красный, и наоборот) дает новый вариант карты, в которой по-прежнему выполняется ключевое условие о том, что соседние точки должны быть разных цветов (см. рис. 11).
Если красный сосед нашей точки не является частью выделенной сине-красной цепочки, проведите такую замену. Синий сосед точки сделается красным, а красный останется красным по-прежнему. Теперь соседи нашей точки окрашены не более чем в три цвета: красный, зеленый и желтый, что позволяет нам окрасить точку в синий цвет — и дело сделано. Однако сине-красная цепочка может описать петлю и замкнуться на синем соседе нашей точки. Если так, оставьте в покое синий и красный цвета и проделайте ту же операцию с ее желтыми и зелеными соседями. Начните с зеленой точки и сформируйте желто-зеленую цепочку Кемпе. Заметьте: она не сможет замкнуться на желтого соседа, поскольку на ее пути непременно встретится предыдущая красно-синяя цепочка. Поменяйте желтый и зеленый цвета в цепочке местами, и дело сделано.
Остается последний случай: когда не существует точек с тремя или четырьмя соседями, но по крайней мере одна точка имеет пять соседей. Кемпе предложил аналогичное, но более сложное правило перекраски точек, которое, на первый взгляд, успешно решало и эту проблему. Вывод: теорема о четырех красках верна, и доказал ее Кемпе. Эта заявление попало даже в средства массовой информации: американский журнал The Nation упомянул решение Кемпе в своем обзоре.
Казалось, с проблемой четырех красок было покончено, и математики в большинстве своем с этим согласились. Правда, Питер Тэт продолжал поиски более простого решения и время от времени публиковал статьи на эту тему. Исследования привели его к нескольким полезным открытиям, но простое доказательство по-прежнему не давалось.
И тут на сцене появляется преподаватель математики из Университета Дарема Перси Хивуд, прозванный за свои великолепные ухоженные усы «Котом». Еще студентом в Оксфорде он услышал от профессора геометрии Генри Смита о теореме о четырех красках. Смит сказал ему, что теорема эта, хотя, вероятно, и верна, но не доказана, так что у Хивуда есть шанс. Кроме того, как-то он наткнулся на статью Кемпе и попытался ее понять. Результат своих размышлений Хивуд опубликовал в 1889 г. под названием «Теорема о раскраске карты», высказав при этом сожаление, что цель его статьи более «деструктивна, чем конструктивна, ибо в ней будет показано, что в признанном, кажется, на сегодня доказательстве есть дефект». Кемпе допустил ошибку.
Ошибка была достаточно тонкой и возникала в схеме перекраски в том случае, когда у удаляемой точки было пять соседей. В некоторых случаях изменение цвета одной точки (по схеме Кемпе) могло повлечь за собой невозможность дальнейших изменений. При этом Кемпе считал, что если какая-то точка меняет цвет, то происходит это лишь один раз. Хивуд же нашел карту (или сеть), в которой схема перекраски по Кемпе не срабатывала, и тем самым опроверг его доказательство. Кемпе, узнав об этом, без промедления признал ошибку и добавил, что ему «не удалось исправить этот дефект». Теорема о четырех красках вновь ждала желающих помериться с ней силой.
Хивуд отыскал в этой истории небольшое утешение для Кемпе: его метод успешно доказывал теорему о пяти красках. Кроме того, Хивуд работал еще над двумя обобщенными вариантами задачи: над вариантом с империями, где области могли состоять из нескольких несвязанных кусков, которые все требовали одного цвета, и над картами на более сложных поверхностях. Аналогичная задача на сфере решается точно так же, как на плоскости. Представьте себе карту на сфере, причем разверните сферу так, чтобы Северный полюс оказался внутри одной из областей. Теперь, если удалить точку полюса, то сферу с отверстием можно развернуть в поверхность, топологически эквивалентную бесконечной плоскости. Регион, в котором находился полюс, развернется в бесконечное пространство, окружающее карту. Однако, помимо сферы, существуют и другие, более интересные поверхности. Среди них тор, напоминающий по форме бублик с дыркой (см. рис. 12 слева).
Существует полезный способ визуализации тора, часто упрощающий математикам жизнь. Если разрезать тор вдоль двух замкнутых кривых (см. рис. 12 в середине), то можно развернуть его поверхность так, чтобы получился квадрат (см. рис. 12 справа). Такая трансформация меняет топологию тора, но эту сложность можно обойти, если объявить противоположные стороны получившегося квадрата тождественными. В результате (а строгое определение позволяет точно сформулировать принцип) мы договариваемся считать, что соответствующие точки на этих сторонах совпадают. Чтобы представить, почему так, посмотрите на рисунки в обратном порядке. Мы скатываем квадрат в трубочку, и противоположные его стороны действительно склеиваются, затем сгибаем трубочку в кольцо и соединяем концы. Готово. А теперь самое интересное. Не обязательно на самом деле скручивать квадрат в трубочку и соединять соответствующие стороны. Можно работать с плоским квадратом, достаточно просто помнить о том, что его противоположные стороны — это одно и то же. Всему, что мы будем делать на торе, включая и рисование кривых, имеется точное соответствие на квадрате. Хивуд доказал, что для раскрашивания любой карты на торе необходимо и достаточно семи красок. Рис. 13 (слева) показывает, что семь цветов необходимо; при этом квадрат, как уже говорилось, представляет поверхность тора. Обратите внимание, как сходятся участки на противоположных сторонах квадрата. Существуют поверхности, подобные тору, но имеющие больше отверстий (см. пример на рис. 13 справа). Число отверстий в такой фигуре называется родом и обозначается буквой g (genus — род). Хивуд придумал формулу для числа красок, необходимых для карты на торе с g отверстиями, если g 1: это наибольшее целое число, меньшее или равное
При g от 1 до 10 формула выдает следующие результаты:
7 8 9 10 11 12 12 13 13 14.
Число красок, определяемое формулой, растет медленнее, чем род тора, и нередко добавление лишнего отверстия в торе ничего не меняет. Это удивительно, потому что каждое дополнительное отверстие дает большую свободу для изобретения сложных карт.
Хивуд не просто извлек эту формулу из воздуха. Она возникла из обобщения метода, при помощи которого я доказывал теорему о шести красках на плоскости. Он сумел доказать, что такого числа красок всегда достаточно. Однако вопрос о том, нельзя ли сделать это число меньше, оставался открытым еще много лет. Примеры для небольшого значения рода показывали, что оценка Хивуда — наилучшая из возможных. Только в 1968 г. Герхардт Рингель и Джон Янгс заполнили остававшиеся пробелы и доказали на базе собственных и чужих работ, что формула верна. Они использовали при этом комбинаторные методы, основанные на сетях особого рода и достаточно сложные, чтобы заполнить собой целую книгу.
При g = 0, т. е. для карт на сфере, формула Хивуда дает четыре краски, но его доказательство достаточности на сфере не работает. Несмотря на значительный прогресс для поверхностей хотя бы с одним отверстием, первоначальная теорема о четырех красках никуда не делась. Немногочисленные математики, которые готовы были бросить свои силы на решение этого вопроса, настроились, говоря языком военных, на длительную осаду. Задача оказалась неприступной крепостью, но желающие завоевать ее надеялись построить еще более мощные осадные машины и понемногу, по кусочку, разбить и обрушить стены. Машины были построены, но стены продолжали стоять. Однако атакующие постепенно все больше узнавали о том, как не следует решать эту задачу, и о препятствиях, возникающих на этом пути. Таким образом неудачи создали почву для появления новой стратегии. Она стала естественным продолжением методов Кемпе и Хивуда и состоит из трех частей. Я перечислю их, используя понятия двойственных сетей, поскольку на сегодня это стандартный подход.
1. Рассмотреть минимальный контрпример.
2. Составить список неустранимых конфигураций — меньших сетей, таких, что любой минимальный контрпример обязательно должен содержать какую-нибудь из них.
3. Доказать, что каждая из неустранимых конфигураций сократима. Иными словами, если меньшая сеть, полученная при удалении неизбежной конфигурации, может быть раскрашена в четыре цвета, то эти цвета можно перераспределить таким образом, что при возвращении неустранимой конфигурации раскраску в четыре цвета можно распространить и на нее тоже.
Объединив эти три шага, мы можем доказать, что минимального контрпримера не существует. Если бы он существовал, то обязательно содержал бы хотя бы одну из неустранимых конфигураций. Но остальная часть сети меньше по размеру, поэтому из минимальности контрпримера следует, что он может быть раскрашен в четыре цвета. А сводимость подразумевает, что исходная сеть тоже может быть раскрашена в четыре цвета. Это противоречие.
Исходя из этих посылок, Кемпе составил (причем совершенно верно) список неустранимых конфигураций: это точка с выходящими из нее тремя, четырьмя или пятью линиями (см. рис. 14). Кроме того, Кемпе корректно доказал, что первые две конфигурации сводимы, однако ошибся с доказательством сводимости третьей конфигурации. На самом деле она несводима. Отсюда предложение: замените эту нехорошую конфигурацию более длинным набором конфигураций, следя за тем, чтобы полный набор оставался неизбежным. Проделайте это таким образом, чтобы каждая конфигурация в наборе была сводимой. Иными словами, найдите неустранимой множество сводимых конфигураций. Если у вас получится, это будет означать, что вы доказали теорему о четырех красках.
Такого набора, вообще говоря, может и не быть в природе, но стратегия сама по себе заслуживает внимания, тем более что ничего лучшего никто предложить не сумел. Правда, у этого метода есть один недостаток. С одной стороны, чем длиннее список конфигураций, тем больше шансов на то, что они действительно неизбежны, а это хорошо. С другой стороны, чем длиннее список, тем меньше вероятность того, что каждая конфигурация в нем окажется сводимой; а если это не так, то все доказательство рушится. Эта опасность становится тем острее, чем больше в списке конфигураций, а это плохо. С третьей стороны, более длинный список предоставляет больше возможностей для выбора сводимых конфигураций, и это хорошо. С четвертой — он увеличивает объем работы, необходимый для доказательства сводимости, и это плохо. А с пятой стороны, хороших способов сделать это просто не существовало.
Именно такие препятствия делают великие задачи великими.
Итак, в течение какого-то времени события развивались так: осаждающим удавалось иногда отбить от стены камешек, но это никак не сказывалось на ней. При этом весь остальной математический мир смотрел на эту осаду позевывая, если вообще обращал на нее внимание. Но кое-кто — его звали Генрих Хееш — уже сооружал более мощный таран. Его вкладом в решение задачи стал метод доказательства сводимости конфигурации, который автор называл «разрядкой». По его мысли, точки в сети следовало рассматривать как приблизительный аналог электрических зарядов, а раскрашивание — как перетекание электричества от одной точки к другой.
Но даже при помощи метода Хееша вручную искать неизбежный набор сводимых конфигураций было невероятно сложно. Отдельные конфигурации при этом, вероятно, были бы достаточно небольшими, но их количество… Хееш продолжал упорно работать, а в 1948 г. даже прочитал курс лекций на эту тему. Он полагал, что полный набор конфигураций должен включать порядка 10 000 штук.На тот момент он успел доказать сводимость 500 комбинаций. На одной из лекций Хееша присутствовал молодой человек по имени Вольфганг Хакен. Позже он признавался, что мало что понял из того, о чем говорил Хееш, но некоторые его рассуждения Хакену запомнились. Он продолжил изучать топологию и позже совершил крупное открытие в теории узлов. Это побудило его взяться за гипотезу Пуанкаре (см. главу 10). Исследуя один из подходов к проблеме, Хакен разложил все возможные случаи на 200 вариантов, решил 198 из них и еще 13 лет безуспешно сражался с двумя оставшимися. После этого он сдался и перешел к задаче о четырех красках. Очевидно, Хакен любил по-настоящему сложные проблемы, но его беспокоила мысль о том, что с 10 000 комбинаций Хееша может произойти нечто подобное. Представьте только: успешно разобраться с 9998 комбинациями и застрять на двух последних. Поэтому в 1967 г. он пригласил Хееша к себе в Университет штата Иллинойс, чтобы спросить совета.
В те дни компьютеры уже начинали потихоньку проникать в мир математики, но тогда они были громадными машинами, которые занимали целые здания, а не стояли спокойно на столе и не умещались в портфеле. Хакена интересовало, можно ли прибегнуть для решения задачи к помощи компьютеров. Оказалось, что такая мысль уже приходила Хеешу в голову, и он даже сделал примерную оценку сложности этой задачи. Из нее следовало, что даже лучший компьютер, к которому он мог бы получить доступ, с ней не справится. В Иллинойсе, однако, был гораздо более мощный компьютер ILLIAC–IV, и Хакен подал заявку на машинное время. Оказалось, однако, что компьютер еще не готов, и ему посоветовали обратиться в Брукхейвенскую лабораторию на Лонг-Айленде, где имелся Cray 6600. Директором компьютерного центра лаборатории был Ёсио Симамото, тоже очарованный задачей о четырех красках. Хееш и Хакен вытянули счастливый билетик — и получили вожделенный доступ к машине.
Компьютер оправдал ожидания, но Хакен начал подозревать, что его можно использовать намного эффективнее. Они генерировали множество сводимых комбинаций и надеялись собрать когда-нибудь из них полный неизбежный набор, но при такой стратегии много времени напрасно растрачивалось на комбинации, которые в конечном итоге оказывались несводимыми. Может быть, лучше поступить наоборот: сделать неизбежность основной целью, а со сводимостью разобраться позже? Конечно, все равно придется брать комбинации с хорошими шансами на сводимость, но сам по себе этот способ казался более перспективным. Однако к этому моменту Cray в Брукхейвене уже был занят более важными вещами. Хуже того, уже несколько специалистов сказали Хакену, что методы, которыми он хочет воспользоваться, вообще невозможно воплотить в компьютерных программах. Он поверил специалистам и прочел лекцию о том, что задача о четырех красках не может быть решена без помощи компьютеров, но теперь, похоже, получается, что с компьютерами ее тоже не решишь. В общем, Хакен решил оставить попытки.
Среди слушателей на лекции присутствовал и опытный программист Кеннет Аппель, который сообщил Хакену, что эксперты, на которых тот ссылается, вероятно, просто хотели избавиться от него, поскольку на создание подобных программ пришлось бы затратить много усилий при непредсказуемом результате. Аппель считал, что математических задач, которые невозможно запрограммировать, не существует. Вопрос только в том, сможет ли программа получить результат за разумное время. Хакен и Аппель объединили усилия. Стратегия, разработанная как модификация все того же метода разрядки, заставляла вносить изменения в программу, а изменения в программе, в свою очередь, заставляли вносить новые изменения в метод. Этот процесс привел к новой концепции «географически подходящих» конфигураций, которые не содержали определенных неподходящих конфигураций, препятствующих сводимости. Шанс на то, что такая конфигурация окажется сводимой, был заметно выше обычного, а определяющее свойство было несложным и легко поддавалось проверке. Аппель и Хакен решили доказать теоретически, а не на компьютере, что существует неустранимое множество географически подходящих конфигураций. К 1974 г. им это удалось.
Это внушало оптимизм, но ученые понимали, что теперь, скорее всего, произойдет: некоторые из географически подходящих конфигураций непременно окажутся несводимыми, так что придется их исключать и заменять на еще более длинный и сложный набор конфигураций. Программа будет «гоняться за собственным хвостом», и успех будет достигнут только в том случае, если этот хвост удастся догнать. Не желая тратить годы на бесплодные поиски, Хакен и Аппель прикинули, сколько времени может занять процесс. Результаты обнадеживали, поэтому работа была продолжена. Теория и расчеты подпитывали и модифицировали друг друга. Временами компьютер, казалось, начинал жить собственной жизнью и проявлять интеллект, «открывая» полезные свойства конфигураций. Затем администрация университета приобрела новый, очень мощный компьютер — более мощный, чем те, что были доступны на тот момент университетским ученым. После многочисленных протестов и споров половина машинного времени была выделена на научные нужды. Вечно меняющийся список неизбежных конфигураций Аппеля и Хакена стабилизировался на уровне примерно 2000 штук. В июне 1976 г. компьютер выполнил последний тест на сводимость, и доказательство было завершено. Благодаря The Times эта история попала в средства массовой информации и стремительно разлетелась по всему миру.
Аппелю и Хакену еще нужно было убедиться, что в доказательстве нет глупых ошибок и упущений, а несколько групп ученых уже устремились по их следам. К июлю, уверившись в действенности своего метода, Аппель и Хакен официально объявили математическому сообществу, что им удалось доказать теорему о четырех красках. Они выпустили препринт — предварительный вариант статьи, который печатается до выхода в свет основной публикации. В то время на публикацию серьезной математической статьи обычно уходило от одного до двух лет. Чтобы не сдерживать прогресс, математикам приходилось искать более быстрые способы познакомить профессиональное сообщество с важными результатами, и препринты были одним из них. В наши дни препринты, как правило, публикуются в Интернете. Полная официальная публикация требует рецензирования, и препринты помогают в ее подготовке — ведь кто угодно может читать их, искать ошибки и сообщать о них авторам, а также предлагать улучшения. Именно поэтому опубликованная версия статьи часто сильно отличается от препринтной.
Окончательное доказательство потребовало около 1000 часов компьютерного времени и содержало 487 правил разрядки. Результаты были опубликованы в двух статьях с 450-страничным приложением, в котором показаны все 1482 конфигурации. На тот момент это был верх совершенства.
Однако основной реакцией математического сообщества стало легкое разочарование. Не результатом как таковым и не замечательным компьютерным достижением. Разочарование вызвал метод. В 1970-е гг. математические доказательства составлялись — и проверялись — вручную. Как я уже говорил в главе 1, доказательство — это рассказ, сюжет которого убеждает вас в истинности того или иного утверждения. Но у этого рассказа не было сюжета. Или если и был, то с большой прорехой на самом интересном месте:
«Жила-была на свете красивая Гипотеза. Мать говорила ей никогда не заходить в темный опасный лес. Но однажды маленькая Гипотеза-о-Четырех-Красках улизнула из дома и забрела-таки туда. Она знала, что если каждая конфигурация в лесу сводима, то она сможет получить доказательство и стать маленькой Теоремой-о-Четырех-Красках; тогда ее опубликуют в журнале, которым заведует Принц Цвет. Глубоко-глубоко в лесу набрела маленькая Гипотеза на компьютер в шоколаде, внутри которого сидел Волк, притворившийся программистом. И Волк сказал: “Да, они все сводимы”, — и все они жили счастливо и умерли в один день».
Нет, так не годится. Я, конечно, шучу, но прореха в сюжете этой сказки примерно соответствует прорехе в доказательстве Аппеля — Хакена — или по крайней мере тому, что математики в большинстве своем восприняли как прореху в доказательстве. Откуда нам знать, что Волк сказал правду?
Мы можем запустить собственную компьютерную программу и выяснить, согласуются ли результаты ее работы с опубликованным доказательством. Но, сколько бы раз мы это ни проделывали, нам все равно не удастся получить столь же убедительный результат, как, к примеру, приведенное мной доказательство того, что обрезанную шахматную доску невозможно полностью закрыть костяшками домино. Компьютерное доказательство невозможно воспринять целиком. Его не проверишь вручную, даже если проживешь миллиард лет. Хуже того, даже если бы это было возможно, никто не поверил бы результату. Человеку свойственно ошибаться, а за миллиард лет ошибок накопится множество.
Компьютеры, вообще говоря, не ошибаются. Если компьютер и человек параллельно проведут достаточно сложные арифметические вычисления и их результаты не сойдутся, то в подобном соревновании по-настоящему разумный человек всегда поставит на компьютер. Но в его работе нет определенности. Корректно функционирующий компьютер в принципе может совершить ошибку; к примеру, космическая частица, пролетев сквозь ячейку памяти, может изменить ее состояние с 0 на 1. От этого можно защититься, повторив расчет. Ошибиться может и разработчик компьютера, что гораздо серьезнее. Так, у процессора Intel P5 Pentium в стандартных операциях с плавающей точкой была ошибка: если его просили разделить 4 195 835 на 3 145 727, он выдавал в ответ 1,33373, тогда как верный ответ 1,33382. Как оказалось, четыре ячейки таблицы оставались незаполненными. Кроме того, причина компьютерной ошибки может крыться в операционной системе или в недостатках пользовательской программы.
Утверждение, что доказательство Аппеля — Хакена, полученное при помощи компьютера, изменило саму природу понятия «доказательство», вызвало горячие философские споры. Я понимаю, к чему клонят философы, но на самом деле концепция доказательства, которой пользуются профессиональные математики, отличается от той, что преподают студентам в курсе математической логики. Но даже если взять эту, более формальную концепцию, то ничто в ней не требует, чтобы логику каждого шага непременно проверял человек. Уже несколько столетий математики используют для рутинных арифметических операций механизмы. Даже если человек пройдется по доказательству с карандашом, проверяя каждую его строчку, и не обнаружит ошибок, то кто гарантирует нам, что он ничего не пропустил? Совершенная и безупречная логика — это идеал, к которому мы стремимся. Люди несовершенны; они делают, что могут, но полностью исключить элемент неопределенности невозможно.
Робин Уилсон в книге «Четырех красок достаточно» (Four Colours Suffice) точно сформулировал ключевой социологический аспект реакции общества:
«Аудитория раскололась на два лагеря: тех, кому за 40, невозможно было убедить, что доказательство, проведенное компьютером, может быть верным, а тех, кому еще не исполнилось 40, невозможно было убедить, что верным может быть доказательство, содержащее 700 страниц вычислений вручную».
Если наши машины в чем-то превосходят нас, разумно их использовать. Могут измениться методики доказательства, но они и без компьютеров постоянно меняются: этот процесс и называется «исследованиями». При этом сама концепция доказательства не изменится радикально, если некоторые шаги вместо человека проделает компьютер. Доказательство — это рассказ; доказательство, полученное при помощи компьютера, — это рассказ, сюжет которого слишком длинен для подробного пересказа, и поэтому нам приходится довольствоваться кратким пересказом его основной линии и гигантским приложением в виде машинной распечатки.
После первой прорывной работы Аппеля и Хакена прошло уже немало времени, и математики привыкли к использованию компьютера. Они и сегодня предпочитают доказательства, основанные исключительно на человеческом разуме, но в большинстве своем уже не считают их единственно возможными. В 1990-е гг., правда, кое у кого еще были легкие оправданные сомнения в доказательстве Аппеля — Хакена, и некоторые математики решили повторить его целиком, воспользовавшись новыми теоретическими наработками и гораздо более мощными компьютерами. В 1994 г. Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас взяли из работы Аппеля — Хакена только базовую стратегию, отбросив все остальное, и повторили все с самого начала. За год им удалось найти неустранимый набор из 633 конфигураций, сводимость каждой из которых можно было доказать при помощи 32 правил разрядки. Результат оказался значительно проще, чем 1482 конфигурации и 487 правил разрядки Аппеля и Хакена. Сегодня компьютеры считают так быстро, что это доказательство можно целиком проверить на домашнем компьютере за несколько часов.
Все это, конечно, хорошо, но главным по-прежнему остается компьютер. Можно ли изменить ситуацию? В среде математиков зреет убеждение в том, что в данном случае это не исключено. Возможно, новые открытия, связанные с задачей о четырех красках, позволят когда-нибудь получить более простое доказательство. Для него не понадобится или почти не понадобится помощь компьютера, и математики смогут прочесть его, обдумать и сказать: «Да!» Пока такого доказательства нет, но что-то витает в воздухе…
Математики многое узнали о графах и сетях и узнают с каждым днем все больше. Топологи и геометры обнаруживают глубокие связи между сетями и совершенно далекими, казалось бы, от них областями математики, включая и некоторые разделы математической физики. Время от времени, скажем, всплывает концепция кривизны. Название ее говорит само за себя: кривизна пространства говорит о том, насколько это пространство изогнуто. Если оно плоское, как плоскость, его кривизна равна нулю. Если оно изогнуто в одну сторону — как холм во всех направлениях загибается вниз, — его кривизна положительна. Если пространство, как горный перевал, в некоторых направлениях загибается вниз, а в некоторых вверх, его кривизна отрицательна. Существуют геометрические теоремы (отдаленные потомки формулы Эйлера), связывающие построенные в пространстве сети с кривизной самого пространства. На это же намекает формула Хивуда для тора с g отверстиями. Сфера имеет положительную кривизну; тор, представленный в виде квадрата с тождественными противоположными сторонами (см. рис. 12 справа), имеет нулевую кривизну, а тор с двумя или более отверстиями — отрицательную. Так что между кривизной и раскрашиванием карт определенно существует какая-то связь.
За этой связью стоит одно полезное свойство кривизны: от нее очень сложно избавиться. Это похоже на кошку под ковром. Если ковер лежит на полу ровно, кошки под ним нет, но, если вы видите на ковре горб, значит, под ним кошка. Вы можете гонять эту кошку по всему ковру, но горб будет просто перемещаться с одного места на другое. Так же и кривизну можно сдвинуть, но невозможно убрать. Разве что кошка доберется до края ковра и выскочит наружу, унося кривизну с собой. Правила разрядки Хееша немного напоминают замаскированную кривизну. Они позволяют гонять электрический заряд с места на место, но не ликвидируют его. Не может ли существовать некое понятие кривизны для сети и хитрое правило разрядки, позволяющее, по существу, гонять по нему эту кривизну?
Если так, то нельзя исключить вариант, при котором вам удастся уговорить сеть раскраситься самостоятельно. Присвоить точкам (а может быть, и линиям тоже) кривизну, а затем позволить сети перераспределить ее более равномерно. Возможно, если мы все правильно подготовим, то «равномерность» будет означать как раз достаточность четырех красок. Это всего лишь идея, причем не моя, и я объяснил ее недостаточно подробно, чтобы что-нибудь понять. Но эта идея порождена интуицией какого-то математика и вселяет надежду на то, что в будущем, возможно, будет найдено более концептуальное доказательство теоремы о четырех красках — это будет потрясающая повесть, а не краткий пересказ с приложением в виде миллиарда телефонных справочников. В главе 10 мы столкнемся с аналогичной идеей в гораздо более хитроумном контексте, где она помогла решить еще более великую топологическую задачу.
5. Сферическая симметрия. Гипотеза Кеплера
Все началось со снежинки.
Снег обладает странной красотой. Он падает с небес пушистыми белыми хлопьями; он летит по ветру и образует мягкие холмы и гребни, покрывающие все вокруг; он сам по себе обретает неземные странные формы. Он холодный. По нему можно кататься на лыжах, на санках, можно лепить из него снежки и снеговиков… А если не повезет, можно оказаться погребенным под тысячетонной снежной лавиной. Исчезая, он не возвращается на небо — по крайней мере непосредственно в виде белых хлопьев. Он превращается в обычную воду, которая, конечно, может испариться и вернуться на небо, но может и течь ручьями и реками вниз, к морю, а потом долго-долго обитать в океане. Снег — форма льда, а лед — это замороженная вода.
Все сказанное не ново. Вероятно, это знали еще неандертальцы.
Снежинки ни в коем случае нельзя назвать бесформенными комками. В первозданном виде (до того, как начинается процесс таяния) многие из них представляют собой крохотные затейливые звездочки — плоские, шестигранные и симметричные. Есть и просто шестиугольники. Некоторые снежинки не настолько симметричны, некоторые отличаются заметной толщиной (т. е. имеют третье измерение), но снежинки с шестилучевой симметрией очень типичны и встречаются часто. Снежинки — кристаллы льда. Это тоже не новость, ведь невозможно, увидев кристалл, не узнать его. Но снежинки — не обычные кристаллы с плоскими гранями в виде многоугольников. Самое загадочное свойство снежинок добавляет в картину легкий штрих хаоса: несмотря на одинаковую симметрию, точная структура каждой снежинки уникальна. Говорят, не существует двух одинаковых снежинок. Я часто недоумевал: откуда они могут это знать? Но если достаточно педантично разобраться в том, что считать одинаковым, то выяснится, что цифры говорят в пользу такой позиции.
Почему для снежинок характерна шестилучевая симметрия? Этим вопросом 400 лет назад задался один из великих математиков и астрономов XVII в. — и после некоторых размышлений нашел на него ответ. Поразительно верный ответ, тем более что ученый при этом не проводил никаких особых экспериментов. Он просто свел воедино несколько простых общеизвестных мыслей. К примеру, о том, как располагаются зернышки в гранате.
Этого человека звали Иоганн Кеплер, и у него был очень хороший повод задуматься о снежинках. Жизнь и работа ученого в те времена часто зависели от богатого покровителя, и для Кеплера таковым был Иоганн Вакер фон Вакенфельс. В то время Кеплер служил придворным математиком императора Священной Римской империи Рудольфа II, а Вакер, дипломат, был советником императора. Кеплер хотел сделать своему покровителю новогодний подарок. В идеале он должен был быть недорогим, необычным и занимательным — и приоткрыть перед Вакером дверь в мир замечательных открытий, которые стали возможны благодаря его деньгам. Так что Кеплер собрал свои мысли о снежинках в небольшую книгу, которая и должна была стать подарком. Называлась она «О шестиугольных снежинках» (De Nive Sexangula). Шел 1611 г. В этой книге содержалось короткое замечание (один из основных шагов в рассуждениях Кеплера), и сформулированную в нем математическую загадку никому не удавалось решить на протяжении 387 лет.
Кеплер имел огромный опыт поиска закономерностей. Его важнейшая научная работа — открытие трех фундаментальных законов движения планет. Первый и самый известный из них гласит, что орбиты планет представляют собой эллипсы. Кроме того, Кеплер был мистиком и приверженцем учения пифагорейцев о том, что Вселенная основана на числах, закономерностях и математических формах. Помимо астрономии, он занимался астрологией: математики в те времена нередко выдавали себя за астрологов, поскольку обладали необходимой квалификацией и могли рассчитать, когда асцендент находится в Водолее. Богатые покровители и короли заказывали им составление гороскопов.
В своей книге Кеплер указал, что снег возникает из водяного пара, который сам по себе не имеет формы, но каким-то образом превращается в твердые снежинки с шестилучевой симметрией. Для такого перехода должна быть какая-то причина, считал Кеплер:
«Позволительно спросить, каково это действующее начало, как оно действует, является ли форма искони присущей телу или приобретается под влиянием внешних воздействий, принимает ли материал шестиугольную форму в силу необходимости или по своей природе и что следует считать врожденным: воплощенный в шестиугольном архетип красоты или знание цели, к которой приводит эта форма?»
В поисках ответа на этот вопрос Кеплер рассматривает другие примеры шестиугольных форм в природе. В первую очередь на ум приходят пчелиные соты. Они формируются из двух слоев шестиугольных ячеек, составленных «впритык», так что общие их концы образуют три ромба, т. е. параллелограммы, у которых все четыре стороны одинаковы. Такая форма напомнила Кеплеру о теле, известном как ромбический додекаэдр (см. рис. 15). Это тело не входит в перечень пяти правильных тел, известных пифагорейцам (их систематизировал Евклид), но обладает интересным отличительным свойством: одинаковыми ромбическими додекаэдрами можно полностью, без зазоров заполнить пространство. Эта же форма возникает внутри граната, где маленькие округлые зернышки растут в тесноте и потому вынуждены «изобретать» эффективную упаковку.
Как всякий разумный математик, Кеплер начинает с простейшего случая, при котором сферы (шарики) образуют единственный плоский слой. По существу, это то же самое, что упаковывать одинаковые кружочки на плоскости. Он находит всего две правильные конфигурации. В одной круги укладываются в квадраты (см. рис. 16 слева); в другой — в равносторонние треугольники (см. рис. 16 справа). Эти конфигурации, повторяемые на бесконечной плоскости, образуют квадратную решетку и треугольную решетку. Слово «решетка» говорит об их пространственной периодичности, повторяющейся в двух независимых направлениях. На рисунке по объективным причинам показаны лишь конечные участки решетки, поэтому на края не нужно обращать внимания. То же можно сказать про размещенные ниже рис. 17–20. На рис. 16 слева и справа показано по пять рядов кругов, и в каждом ряду они соприкасаются с соседями. Однако треугольная решетка немного сплюснута, и ее ряды располагаются ближе друг к другу. Так что круги в треугольной решетке упакованы плотнее, чем в квадратной.
Далее Кеплер задается вопросом, как такие слои можно уложить один на другой, и рассматривает четыре случая. В первых двух все слои уложены по квадратной решетке. При укладывании в стопку шарики каждого ряда можно поместить точно над шариками нижнего ряда. Тогда у каждого шарика будет по шесть непосредственных соседей: четыре в своем слое, один сверху и один снизу. Такая упаковка похожа на трехмерную шахматную доску, сделанную из кубиков; в нее она, кстати, и превратится, если надуть шарики так, чтобы дальше расширяться им было уже некуда. Но это, говорит Кеплер, «не самая плотная упаковка». Ее можно сделать еще плотнее, если сдвинуть верхний слой по диагонали так, чтобы его шарики точно легли во впадины между шариками нижнего слоя (см. рис. 17 слева). Повторим этот процесс для всех слоев (см. рис. 17 справа). Теперь у каждого шарика по 12 соседей: четыре в своем слое, четыре вверху и четыре внизу. Если их надуть, пространство заполнится ромбическими додекаэдрами.
В двух других случаях слои складываются по гексагональной решетке. Если при складывании в стопку поставить шарик над шариком, у каждого шарика будет по восемь соседей: шесть в своем слое, один вверху и один внизу. Опять же шарики верхнего слоя можно поставить над промежутками в нижнем. Тогда у каждого из них будет по 12 соседей: шесть в собственном слое, три вверху и три внизу. Количество соседей такое же, как во втором варианте упаковки квадратных слоев, и Кеплер, проведя тщательный геометрический анализ, показывает, что в реальности этот вариант упаковки полностью совпадает со вторым. Единственная разница заключается в том, что квадратные слои лежат не горизонтально, а под углом. Кеплер пишет: «Таким образом, самая плотная трехмерная упаковка с треугольной решеткой не может существовать без квадратной решетки, и наоборот». К этому я еще вернусь: это важно.
Разобравшись с базовой геометрией упаковки шариков, Кеплер возвращается к снежинке с ее шестилучевой симметрией. Шестигранник напоминает ему о треугольной решетке упаковки шариков на плоскости, в которой каждый шарик соседствует с шестью другими, образуя идеальный шестиугольник. В этом, делает вывод Кеплер, должно быть, и заключается причина шестиконечности снежинок.
Эта глава посвящена, строго говоря, не снежинкам, но данное Кеплером объяснение их симметричности очень похоже на то, что предложили бы сегодня мы, так что стыдно было бы остановиться на этом. Почему они такие разные, но при этом все симметричны? Когда вода кристаллизуется, образуя лед, атомы водорода и кислорода, из которых состоят молекулы воды, укладываются в симметричную структуру — кристаллическую решетку. Эта решетка сложнее любой кеплеровой конструкции из шариков, но строится тоже на основе шестилучевой симметрии. Снежинка растет от крохотного «зернышка» всего из нескольких атомов, организованных в виде маленького кусочка решетки. Это зернышко тоже обладает шестилучевой симметрией; именно оно подготавливает сцену для роста ледяного кристалла в грозовой туче, где ветер бросает миллионы этих кристаллов из стороны в сторону.
Великое разнообразие узоров в снежинках — следствие меняющихся внешних условий. В зависимости от температуры и влажности рост кристалла может идти равномерно по всей границе, и тогда атомы с любой стороны добавляются с одной и той же частотой, и получаются простые шестиугольники. Но рост может идти с разной скоростью в разных местах, и тогда получается древовидная структура. Растущая снежинка путешествует по грозовой туче то вверх, то вниз, и условия вокруг постоянно меняются, причем случайным образом. Но сама снежинка настолько мала, что условия во всех шести ее углах в любой момент времени практически одинаковы. Поэтому все шесть лучей делают одно и то же. Каждая снежинка несет на себе отпечаток своей истории. На практике шестилучевая симметрия никогда не бывает строгой, но часто очень близка к идеалу. Лед — загадочное вещество, поэтому возможны и другие формы — пики, плоские круги, шестигранные призмы, призмы с плоскими концами. Полное описание происходящего вышло бы очень сложным, но определяющим фактором является то, как располагаются атомы в кристаллах льда. Во времена Кеплера атомная теория сводилась в лучшем случае к неопределенным предположениям древних греков. Поразительно, как далеко он сумел зайти в своих выводах, опираясь только на народные наблюдения, мысленные эксперименты и собственную интуицию.
Гипотеза Кеплера не имеет отношения к снежинкам как таковым. Все дело в небрежном замечании о том, что укладка слоев из плотно упакованных шариков, при которой шарики верхнего слоя ложатся во впадины между шариками нижнего, дает «самую плотную возможную упаковку в трех измерениях». Неформально эту гипотезу можно сформулировать так: если вы хотите упаковать много апельсинов в большой ящик, заполнив его при этом как можно плотнее, то укладывать плоды нужно так, как это делает любой торговец фруктами.
Трудность здесь не в том, чтобы найти ответ. Кеплер нам все рассказал. Трудность в том, чтобы доказать, что он был прав. За прошедшие столетия ученые собрали немало косвенных тому свидетельств. Никто не смог предложить более плотную упаковку. Именно такое расположение атомов часто встречается в кристаллах, где, как считается, плотность оптимальна для минимизации затрат энергии — это стандартный принцип, по которому созданы многие природные формы. Этого оказалось достаточно, чтобы убедить большинство физиков. И никто не смог доказать, что ничего лучшего не существует. В более простых вопросах такого рода, вроде упаковки кругов на плоскости, обнаружились скрытые глубины. Надо сказать, весь этот раздел математики сложен и полон неожиданностей. Все это тревожило математиков, хотя большинство из них тоже считали, что Кеплер дал верный ответ. В 1958 г. Амброз Роджерс описал гипотезу Кеплера как то, «во что многие математики верят, а все физики знают и так». В этой главе рассказывается, как математики обратили веру в точное знание.
Чтобы понять, что именно они сделали, нам придется как следует приглядеться к кеплеровой конструкции из шариков, известной как гранецентрированная кубическая решетка. Стоит сделать это, и начинают проявляться тонкости стоявшей перед математиками задачи. Первым на ум приходит вопрос: почему мы используем слои с квадратной решеткой? В конце концов, самой плотной упаковкой на плоскости (т. е. для одного слоя) является треугольная решетка. Дело в том, что гранецентрированную кубическую решетку можно получить и из слоев с треугольной укладкой шариков; именно в этом суть замечания Кеплера о том, что «треугольная схема укладки не может существовать без квадратной». Однако гранецентрированную кубическую решетку, сложенную из квадратных слоев, проще описывать. Кроме того, так мы убедимся, что гипотеза Кеплера не столь прямолинейна, как укладка апельсинов в ящики.
Предположим, что мы начинаем с плоского слоя шариков, уложенных треугольниками (см. рис. 16 справа). Между шариками имеются скругленные треугольные выемки, в которые могут лечь шарики следующего слоя. Когда мы начинали с квадратного слоя, мы могли использовать все выемки без исключения, и положение второго и последующих слоев определялось однозначно. С треугольными слоями не так. Мы не можем использовать все выемки, поскольку они располагаются слишком близко друг к другу. Мы можем использовать только половину. Один из вариантов укладки показан на рис. 18 слева при помощи небольших серых точек для наглядности, а рис. 18 справа демонстрирует, как следует расположить следующий слой шариков. Другой способ уложить новый слой в выемки предыдущего показан на рис. 19 слева темными точками. Эти точки совпадают с выемками второго слоя, так что мы добавляем третий слой в соответствующем положении. Результат показан на рис. 19 справа.
Если мы работаем всего лишь с двумя слоями, разница между двумя вариантами не играет никакой роли. Мы можем без труда получить первый вариант укладки, просто повернув второй вариант на 60°. Эти варианты одинаковы «с точностью до симметрии». Но после укладки первых двух слоев у нас появляются два по-настоящему разных варианта для третьего слоя. Каждый новый слой имеет две системы выемок, показанных на рис. 19 слева светлыми и темными точками. В одной из них выемки соответствуют центрам шариков предыдущего слоя, которые на рис. 19 справа видны как светло— серые треугольнички. Во второй выемки соответствуют выемкам предпредыдущего слоя и видны на рис. 19 справа как треугольнички с вписанными в них крохотными белыми шестиугольничками. Чтобы получить гранецентрированную кубическую решетку, мы должны использовать для третьего слоя темно-серые позиции, а затем повторять такой порядок укладки до бесконечности.
Не до конца очевидно, однако, что результатом такой укладки станет гранецентрированная кубическая решетка. Где же здесь квадраты? Дело в том, что квадраты в такой укладке присутствуют, но располагаются наклонно, под углом. На рис. 20 показаны шесть последовательных треугольных слоев, из которых удалена часть шариков. Стрелками указаны ряды и столбцы скрытой внутри квадратной решетки. Все слои, параллельные данному, тоже выстроены по квадратной решетке, а между собой соотносятся в точности так же, как я выстраивал гранецентрированную кубическую решетку.
Насколько компактна такая упаковка? Мы измеряем компактность (эффективность) упаковки ее плотностью: долей общего объема, занимаемой шариками{20}. Чем больше плотность, тем компактнее упаковка. Кубики укладываются в параллелепипед с плотностью 1, заполняя весь объем. Между шариками, очевидно, в любом случае останутся промежутки, так что плотность их упаковки меньше единицы. Плотность гранецентрированной кубической решетки составляет в точности /18, это примерно 0,7405. При такой упаковке шарики заполняют чуть меньше трех четвертей пространства, и гипотеза Кеплера утверждает, что никакая упаковка шариков не может иметь плотность больше этой.
Я сформулировал все это достаточно осторожно. Я не сказал, что «плотность гранецентрированной кубической решетки выше, чем любой другой». Такое утверждение было бы неверным, и в этом несложно убедиться. Для этого вернемся к построению гранецентрированной кубической решетки из треугольных слоев. Я сказал, что после укладки первых двух слоев возникает два варианта укладки третьего. Гранецентрированная кубическая решетка возникает во втором варианте — том, что с темно-серыми точками. Что произойдет, если мы пойдем по первому пути и используем светло-серые точки? Тогда шарики третьего слоя окажутся точно над шариками первого. Продолжив точно так же и помещая каждый новый слой точно над позапрошлым слоем, мы получим второй вариант объемной решетки: гексагональную. Она отличается от гранецентрированной кубической решетки, но имеет ту же плотность. Интуитивно это понятно, поскольку два разных способа укладки третьего слоя симметричны относительно поворота, а сам слой в обоих случаях ложится на предыдущий одинаково плотно.
Это единственные два способа решетчатой упаковки, которые можно получить при укладке стопки треугольных слоев, но в 1883 г. географ и кристаллограф Уильям Барлоу заметил, что для каждого следующего слоя мы можем произвольно выбрать любой из двух вариантов укладки. Поскольку оба варианта вносят в плотность всей стопки одинаковый вклад, плотность всех этих вариантов упаковки будет одинакова и равна /18. При этом существуют бесконечно много случайных последовательностей такого рода и, соответственно, бесконечно много различных вариантов упаковки с одинаковой плотностью.
Короче говоря, нет единственной самой плотной объемной упаковки шариков. Их бесконечно много, и все они одинаково плотные. Отсутствие единственно верного решения — предупреждение: проблема не так проста и прямолинейна. Если Кеплер был прав, то существует оптимальная плотность упаковки, но есть и бесконечное множество различных структур, ею обладающих. И чтобы доказать оптимальность этой плотности, недостаточно успешно пристраивать каждый новый шарик к предыдущим как можно плотнее. Есть варианты.
Конечно, торговцы фруктами обладают невероятно богатым опытом — ведь гранецентрированную кубическую решетку наверняка можно было увидеть на рынках Древнего Египта еще в додинастическую эпоху, — но одним лишь опытом в таком деле никак не обойдешься. Вообще, тот факт, что метод торговцев фруктами дает хороший результат, в определенной мере случайность. Задача торговца фруктами состоит не в том, чтобы упаковать апельсины как можно плотнее в пространстве, где возможна, в принципе, любая конструкция. Его задача — уложить плоды как можно надежнее в мире, где земля плоская, а сила тяжести действует сверху вниз. Поэтому торговец начинает с того, что выкладывает апельсины в один слой — это очень естественно; затем он добавляет сверху еще один слой и т. д. Если ящик, в который укладываются плоды, прямоугольный, то первый слой, скорее всего, будет выложен по квадратной решетке. Если площадь ничем не ограничена, то естественной будет либо квадратная, либо треугольная решетка. В конечном итоге обе дают гранецентрированную кубическую решетку — по крайней мере, если треугольные слои укладываются как следует. Вообще говоря, квадратная решетка представляется не лучшим вариантом — ведь это не самый плотный способ укладки одного слоя. Однако — скорее по счастливой случайности, чем в результате осознанного выбора — это, как оказалось, не имеет значения.
Физики не интересуются апельсинами, их больше занимает то, как соседствуют друг с другом атомы. Кристалл — это регулярная, пространственно периодическая конструкция из атомов. Гипотеза Кеплера утверждает, что периодичность кристалла — это естественное следствие максимально плотной «упаковки» атомов. Для большинства физиков само существование кристаллов является достаточным доказательством, — по их мнению, гипотеза Кеплера очевидно верна. Однако мы только что убедились, что существует бесконечно много способов упаковки шариков с точно такой же плотностью, как у гранецентрированной кубической и гексагональной решеток, и что способы эти не являются пространственно периодическими. Так почему в кристаллах природа использует именно периодические структуры? Возможно, ответ в том, что атомы не следует рассматривать как сферические объекты.
Математики тоже не слишком интересуются апельсинами. Подобно Кеплеру, они предпочитают работать с идеальными и идентичными сферами, и доводы физиков не представляются им убедительными. Судите сами: если при моделировании кристаллов атомы не следует рассматривать как идеально круглые шарики, то существование кристаллов вообще не имеет отношения к гипотезе Кеплера и ничего не доказывает. Либо то, либо другое. Даже если вы скажете, что гипотеза как будто объясняет кристаллическую решетку, а кристаллическая решетка как будто показывает, что гипотеза верна… все равно в таком рассуждении будет логический пробел. Математикам нужно доказательство.
Кеплер не называл свое утверждение гипотезой: он просто высказал его в своей книге. Совершенно неясно, собирался ли он интерпретировать упомянутый факт столь всеобъемлющим образом. Имел ли он в виду, что гранецентрированная кубическая решетка представляет собой «самую плотную упаковку в трех измерениях» из всех представимых способов упаковки шариков? Или просто говорил о том, что это самая плотная упаковка из рассмотренных им лично? Невозможно вернуться в прошлое и спросить об этом. Но, как бы ни обстояло тогда дело, математиков и физиков интересует именно общая, самая смелая формулировка. Та, что требует рассмотреть все возможные способы упаковки бесконечного числа шариков в бесконечном пространстве и показать, что ни один из этих способов не может похвастать большей плотностью, чем гранецентрированная кубическая решетка.
Недооценить сложность гипотезы Кеплера очень легко. Вроде бы логично предположить, что самая плотная упаковка получится, если добавлять шарики по одному, так, чтобы каждый из них касался как можно большего числа соседних. Такой подход непременно даст структуру, о которой говорил Кеплер. То же получится, если вы будете добавлять шарики в правильном порядке и всегда, когда есть альтернативы, выбирать для них верную позицию. Однако нет никакой гарантии, что более дальновидная политика не окажется лучше, чем процесс поштучного добавления шариков. Всякий, кому приходилось укладывать вещи в багажник автомобиля, знает, что при укладке их по одной в багажнике могут остаться промежутки, куда ничего больше не лезет, но если начать сначала и подойти к вопросу более тщательно, то иногда удается втиснуть в то же пространство больше вещей. Конечно, отчасти проблема укладки вещей затрудняется тем, что все они имеют разные размеры и форму, но смысл аналогии достаточно понятен: максимально плотная упаковка на одном небольшом участке пространства может затруднить укладку остальных вещей и не привести к максимально плотной упаковке в большем объеме.
Конструкции, которые рассматривает Кеплер, очень специфичны. Можно предположить, что какой-то совершенно иной принцип позволит упаковать одинаковые шарики еще плотнее. Может быть, выпуклые слои были бы более эффективны. А может быть, «слои» — вообще неудачная идея. Но даже если вы абсолютно убеждены, что все сделано правильно, это все равно нужно доказывать.
Не убеждены? По-прежнему считаете, что здесь все очевидно? Настолько очевидно, что никакого доказательства не требуется? Сейчас я попытаюсь разрушить вашу уверенность в правильности интуитивного решения — на более простом примере, где речь идет об укладке одинаковых кружочков на плоскости. Предположим, я дам вам 49 одинаковых кружочков единичного диаметра. Каким будет размер самого маленького квадрата, способного их все вметить без перекрытия? На рис. 21 слева показан очевидный ответ: расположить их, как ставят молочные бутылки в ящике. Сторона квадрата при этом — ровно 7 единиц. Чтобы убедиться, что это наилучший вариант, обратите внимание на то, что каждый кружок жестко удерживается остальными, так что лишнее место взять неоткуда. Но рис. 21 справа показывает, что этот ответ неверен. Стоит упаковать кружочки вот таким немного нерегулярным образом, и они поместятся в квадрате со стороной чуть меньше 6,98. Так что доказательство тоже неверно. Жесткость упаковки не гарантирует, что невозможно сделать плотнее.
Несложно убедиться, что рассуждения, позволяющие получить ответ «семь», просто не могут быть верными. Для этого достаточно рассмотреть квадрат побольше. Квадратная решетка позволяет поместить n кружков единичного диаметра в квадрат со стороной n. Невозможно повысить плотность такой укладки путем плавного перемещения кругов, ведь укладка-то у нас жесткая. Но для больших n должны существовать и более плотные укладки, потому что, как известно, треугольная решетка эффективнее квадратной. Если взять по-настоящему большой квадрат и упаковать в него как можно больше кругов, используя треугольную решетку, то, в конце концов, треугольная решетка, благодаря своим преимуществам, победит, несмотря на «краевые эффекты» по границе квадрата, где придется оставлять незаполненные промежутки. Периметр квадрата — 4n — невелик по сравнению с n. Треугольная решетка одерживает верх над квадратной как раз при n = 7. Это не очевидно, и доказывать это пришлось бы долго и подробно, но ясно, что рано или поздно размер сработает. Одной только жесткости укладки недостаточно.
На самом деле существует два варианта гипотезы Кеплера. Одна рассматривает только регулярную упаковку; в ней центры шариков образуют пространственную периодическую структуру, которая бесконечно повторяется в трех независимых направлениях, как своего рода объемные обои. Даже в этом случае проблема весьма сложна, поскольку в пространстве возможно множество различных решеток. Кристаллографы различают 14 их типов, различаемых по видам симметрии, и некоторые из этих типов имеют параметры, которые могут принимать бесконечно много различных значений. Но все эти сложности меркнут, когда начинается рассмотрение второго варианта гипотезы, разрешающей любые возможные упаковки. Шарики здесь находятся в пространстве без гравитации и совершенно не обязаны собираться в слои или какие бы то ни было симметричные структуры.
Когда задача представляется слишком сложной, математики обыкновенно убирают ее в долгий ящик и принимаются искать более простые варианты. Рассуждения Кеплера о плоских слоях наводят на мысль о более простой задаче — упаковке кругов на плоскости. Это значит, что на плоскости, где имеется бесконечное число одинаковых кругов, надо собрать их как можно плотнее. В такой задаче плотность — это доля площади, которую покрывают круги. В 1773 г. Жозеф Луи Лагранж доказал, что самая плотная упаковка кругов на плоскости достигается в треугольной решетке, где плотность составляет /12 0,9069. В 1831 г. Гаусс в отзыве на книгу Людвига Зибера (тот обобщил некоторые теоретические выводы Гаусса по уравнениям третьего порядка) отметил: результаты Зибера доказывают, что самую плотную регулярную упаковку в трехмерном пространстве обеспечивают гранецентрированная кубическая и гексагональная решетки. Сегодня математики очень много знают о решетчатой укладке в пространствах с бльшим числом размерностей — четыре, пять, шесть и т. д. Особенно хорошо удалось разобраться с решетками в 24-мерном пространстве. (Да, такая уж это тема.) Несмотря на кажущуюся непрактичность, эта область математики имеет немало применений в теории информации и теории кодирования.
Нерешетчатые укладки — совершенно иное дело. Их бесконечно много, и они не отличаются приятной регулярностью структуры. Почему бы нам не удариться в другую крайность и не попробовать случайную укладку? Стивен Гейлс в своем труде «Статика растений» (1727) рассказал об экспериментах, в ходе которых он «вжимал несколько пакетов свежего гороха в один горшок» и обнаруживал, что при сильном сдавливании они образуют то ли «красивые правильные додекаэдры», то ли «достаточно правильные додекаэдры»[4]. Судя по всему, автор говорил о том, что правильные додекаэдры красивы, а не о том, что додекаэдры получались довольно правильные, но вторая интерпретация лучше, потому что настоящими правильными додекаэдрами невозможно без пустот заполнить пространство. Вероятно, он видел перед собой ромбические додекаэдры, которые, как мы уже убедились, связаны с гранецентрированной кубической решеткой. Дэвид Скотт насыпал в контейнер множество шариков от подшипников, тщательно встряхивал и измерял плотность укладки. По его данным, максимально она равнялась 0,6366. В 2008 г. Сун Чаомин, Ван Бин и Эрнан Макс получили эту же величину аналитически. Однако их результат не подразумевает, что Кеплер был прав, хотя бы потому, что это означало бы, что гранецентрированная кубическая решетка с плотностью 0,74 не может существовать. Простейшее объяснение такого расхождения заключается в том, что их результат не учитывает чрезвычайно редкие исключения, при том что и гранецентрированная кубическая, и гексагональная решетки, и все бесчисленные варианты конструкций из треугольных слоев представляют собой именно такие исключения. По тому же принципу может существовать и еще какая-нибудь конструкция с еще большей плотностью. Это не может быть регулярная конструкция, но найти ее при помощи бессистемного поиска невозможно, ибо ее вероятность равна нулю. Так что исследование случайных вариантов упаковки, хотя и важно для многих областей физики, не слишком много говорит нам о гипотезе Кеплера.
Первый по-настоящему важный прорыв в решении этой задачи произошел в 1892 г., когда Аксель Туэ в ходе лекции на Скандинавском конгрессе естественных наук коротко изложил доказательство того, что никакая упаковка кругов на плоскости не может быть плотнее треугольной решетки. Лекция была опубликована, но формулировки там слишком неопределенны, чтобы можно было реконструировать само доказательство. Новую версию того же доказательства Туэ опубликовал в 1910 г. Оно казалось убедительным, за исключением нескольких технических моментов, которые, как считал автор, можно было без особого труда довести до ума. Но Ласло Фейеш Тот, вместо того чтобы заполнять пробелы в чужом доказательстве, получил в 1940 г. собственное, полное, основанное на других методах. Вскоре после этого Беньямино Сегре и Курт Малер представили альтернативные доказательства. А в 2010 г. Чан Хайчау и Ван Личун выложили в Интернет более простое доказательство.
Задача поиска наибольшей плотности укладки кругов или шариков при определенных условиях относится к классу математических задач, известных как задачи оптимизации. В такой задаче предлагается найти максимальное или минимальное значение некоторой функции (т. е. математического правила вычисления некой величины, которая определенным образом зависит от некоего набора переменных). Правило вычисления функции часто задается формулой, но это не обязательно. К примеру, таким образом можно сформулировать задачу с 49 кругами на плоскости. Переменными здесь будут координаты центров всех 49 кругов, а поскольку на каждый круг потребуется по две координаты, всего переменных получится 98. Сама функция — это размер наименьшего квадрата со сторонами, параллельными координатным осям, в который можно поместить данный набор неперекрывающихся кругов. Задача эквивалентна поиску минимального значения, которое принимает эта функция при значениях переменных, соответствующих всем вариантам решетки.
Функцию можно представить в виде многомерного ландшафта, каждая точка на котором соответствует определенному набору переменных, а высота в этой точке — значению функции. Максимум функции — это высота самого высокого ее пика, а минимум — глубина самой глубокой долины. В принципе задачи оптимизации можно решать методами диференциального исчисления: в максимуме или минимуме функция должна быть горизонтальна (см. рис. 22), и дифференциальное исчисление позволяет отразить это условие в уравнении. Чтобы решить задачу укладки кругов в квадрат этим методом, нам пришлось бы решить систему из 98 уравнений с 98 переменными.
Решение задач оптимизации встречает на пути одно неожиданное препятствие: подобные уравнения часто имеют большое количество решений. Ландшафт может иметь множество локальных максимумов, из которых самый высокий лишь один. Представьте себе, к примеру, Гималаи: кроме пиков, там почти ничего и нет, но лишь Эвересту принадлежит рекорд высоты. Методы поиска пиков, самый очевидный из которых звучит как «иди вверх, пока это возможно», часто выводят на локальные максимумы и застревают на них. Еще одна трудность состоит в том, что с ростом числа переменных растет и вероятное число локальных пиков. Тем не менее иногда такой метод срабатывает. Даже частичные результаты могут оказаться полезными: если вам удалось найти локальный пик, ясно, что настоящий максимум не может быть ниже. Именно так была найдена улучшенная раскладка кругов в квадрате.
Для регулярных укладок функция, максимум которой нужно найти, зависит от конечного числа переменных — направлений и длин, вдоль которых решетка повторяется. Для нерегулярных укладок функция зависит от бесконечно большого числа переменных — центров всех кругов или шариков. В подобных случаях прямое использование дифференциального исчисления и других методик оптимизации ничего не даст. Доказательство Тота основано на хитрой идее переформулировать задачу о нерегулярной упаковке кругов и превратить ее в задачу оптимизации с конечным набором переменных. Позже, в 1953 г., он понял, что тот же трюк в принципе можно проделать и с гипотезой Кеплера. К несчастью, получившаяся функция зависит примерно от полутора сотен переменных — слишком много для ручного расчета. Но Тот прозорливо разглядел возможный выход: «Имея в виду стремительное развитие наших компьютеров, можно предположить, что минимум можно будет определить с высокой точностью».
В то время вычислительная техника только начинала развиваться, и достаточно мощной машины попросту не существовало, так что в последующие годы работа над гипотезой Кеплера шла в других направлениях. Ряд математиков занимался уточнением верхней границы для возможного значения плотности сферической упаковки. К примеру, в 1958 г. Роджерс доказал, что плотность не превосходит 0,7797. И никаких исключений: эта оценка относилась к любым способам укладки шариков. В 1986 г. Дж. Линдси понизил этот предел до 0,77844, а Дуглас Мадер в 1988 г. чуть-чуть улучшил оценку и получил 0,77836. Эти результаты показали, что невозможно получить плотность намного выше, чем 0,7405, характерные для гранецентрированной кубической решетки. Но тем не менее пробел в доказательстве сохранялся.
В 1990 г. американский математик Ву-И Хзянь объявил, что гипотеза Кеплера доказана. Подробности были опубликованы, но сразу появились сомнения. Тот, просмотрев статью в журнале Mathematical Reviews, написал: «Если бы спросили меня, [доказана ли тем самым гипотеза Кеплера] я бы ответил: нет. Надеюсь, что Хзянь дополнит свое сообщение, но мне кажется, что значительная часть работы еще впереди».
Томас Хейлс, посвятивший работе над гипотезой много лет, тоже высказал сомнения в том, что метод Хзяня можно довести до ума. Вместо этого он решил, что настало время всерьез отнестись к подходу, предложенному Тотом. Выросло новое поколение математиков, для которых естественнее обратиться к компьютеру, чем к таблице логарифмов. В 1996 г. Хейлс обрисовал стратегию доказательства, основанную на идее Тота. Эта стратегия требовала определить все возможные способы организации шариков в непосредственной близости от данного шарика. Укладка шариков определяется центрами соответствующих сфер. Для единичных сфер расстояние между центрами должно составлять по крайней мере две единицы. Скажем, что два шарика являются соседями, если их центры разделены расстоянием не более 2,51 единицы. Этот предел следует установить аккуратно: при слишком маленьком расстоянии не хватит места для перестановки шариков и повышения плотности, а при слишком большом количество вариантов расстановки соседних шариков станет просто гигантским. Хейлс выяснил, что 2,51 — это эффективный компромисс. Теперь мы можем представить, как располагаются шарики-соседи, и построить в пространстве бесконечную сеть. Узлами в ней станут центры шариков, а соединяться между собой линиями они будут, если соответствующие шарики — соседи. Эта сеть — своеобразный скелет укладки — содержит всю существенную информацию о соседях каждого шарика.
Для любого шарика мы можем взять непосредственно соседствующие с ним шарики и рассматривать далее только линии между ними, исключив сам первоначальный шарик. В результате получим своего рода клетку, или ячейку, вокруг точки в центре первоначальной сферы. На рис. 23 показаны: (левая пара) соседи шарика в гранецентрированной кубической решетке и соответствующая ячейка; (правая пара) то же самое для особой структуры из шариков — пятиугольной призмы; эта структура оказалась ключевым игроком всего доказательства. Вы видите здесь два плоских пятиугольника, параллельные «экватору» центрального шарика и еще по шарику на каждом полюсе конструкции.
Ячейку можно изобразить как твердое тело с плоскими гранями; при этом плотность укладки вблизи центрального шарика будет определяться геометрией этого тела{21}. Ключевая идея состоит в том, чтобы каждой ячейке поставить в соответствие некое число (назовем его мерой ячейки), которое станет способом оценки плотности упаковки соседей центрального шарика. Мера ячейки — это не собственно плотность; это величина, которая ведет себя лучше и вычисляется проще плотности. В частности, меру ячейки можно найти просто как сумму мер ее граней; с плотностью такой метод не работает. В принципе, множество разных определений меры соответствуют этому условию, но все они сходятся в одном: для гранецентрированной кубической и гексагональной решеток мера, как бы вы ее ни определяли, всегда составляет восемь пунктов. В данном случае пункт равняется вполне конкретному числу:
Так что восемь пунктов на самом деле равняются 0,4429888. Это занятное число вычисляется исходя из особой геометрии гранецентрированной кубической решетки. Ключевое наблюдение Хейлса связывает гипотезу Кеплера с этим числом: если любая ячейка имеет меру восемь или меньше, гипотеза Кеплера верна. Таким образом, фокус доказательства смещается на ячейки и их меры.
Ячейки можно классифицировать по топологии: сколько у них имеется граней с тем или иным числом сторон и как эти грани сочетаются друг с другом. Однако при любой заданной топологии стороны граней ячейки могут быть различной длины. Длина сторон влияет на меру, но топология соединяет множество разных ячеек, и их можно рассматривать в общем. В своем доказательстве Хейлс рассмотрел около 5000 типов ячеек, но основные расчеты велись по нескольким сотням вариантов. В 1992 г. он предложил проект доказательства из пяти этапов:
1. Доказать утверждение в случае, когда все грани ячейки представляют собой треугольники.
2. Показать, что гранецентрированная кубическая и гексагональная укладки имеют более высокую меру, чем любая ячейка с той же топологией.
3. Разобраться со случаем, когда все грани ячейки представляют собой треугольники и четырехугольники, за исключением пятиугольной призмы (это более сложный случай).
4. Разобраться с ячейками, грани которых имеют более четырех сторон.
5. Разобраться с единственным оставшимся случаем — с ячейкой в виде пятиугольной призмы.
Часть 1 была реализована в 1994 г., часть 2 — в 1995 г. По ходу программы Хейлс модифицировал определение ячейки так, чтобы упростить рассуждения (он использовал термин «звезда декомпозиции»). Новое определение не изменило две представленные ячейки и почти не затронуло те части доказательства, которые были уже реализованы. К 1998 г. при помощи новой концепции были завершены все пять предложенных Хейлсом этапов. Часть 5 — хитрый случай с пятиугольной призмой — рассмотрел студент Хейлса Сэмюел Фергюсон.
На всех этапах анализа были масштабно задействованы компьютеры. Хитрость здесь в том, чтобы для каждой локальной сети выбрать такое представление о мере, которое сделало бы вычисления сравнительно несложными. Геометрически замена плотности на меру выглядит как сооружение своеобразной крыши над гладким ландшафтом, максимум которого ищет исследователь. Крыша состоит из нескольких плоских участков (см. рис. 24). Работать с такими формами значительно легче, чем с гладкими поверхностями, поскольку максимумы располагаются в углах, для нахождения которых достаточно решить куда более простые уравнения. Для этого существуют эффективные методы, известные как линейное программирование. Если крыша построена так, что ее пик совпадает с пиком гладкой поверхности, то более простые расчеты, предназначенные для поисков пика крыши, позволят найти не только его, но и пик гладкой поверхности.
У всякого упрощения есть своя цена, и у этого тоже: чтобы найти пик крыши, приходится решать около 100 000 линейных задач. Впрочем, достаточно длинные расчеты, необходимые для этого, вполне по силам современным компьютерам. Когда Хейлс и Фергюсон подготовили свою работу к публикации, в ней оказалось около 250 страниц математического текста и 3 Гбайт компьютерных файлов.
В 1999 г. Хейлс подал подготовленное доказательство в Annals of Mathematics, и журнал специально для этого случая набрал жюри из 12 экспертов. К 2003 г. оно объявило, что «с уверенностью на 99 %» представленное доказательство верно. Оставшийся 1 % неуверенности касался компьютерных расчетов; многие из них жюри повторило, а также иными способами проверило стратегию и тактику доказательства, но некоторые его аспекты проверить не удалось. После значительной задержки журнал опубликовал работу. Хейлс признал, что такой подход к доказательству, вероятно, никогда не будет признан на 100 % корректным, и в 2003 г. объявил о старте проекта по переформатированию доказательства в такой вид, в котором его сможет проверить компьютер при помощи стандартных программ автоматической проверки доказательств.
Это может показаться чем-то вроде перехода из огня в полымя, но на самом деле все предельно понятно и логично. Доказательства, которые математики публикуют в журналах, призваны убеждать людей. Как я уже говорил в главе 1, доказательство — это своего рода рассказ. Компьютеры не сильны в литературе, зато прекрасно справляются с заданиями, которые нам не по зубам: они способны безошибочно выполнять длинные нудные расчеты. Компьютеры идеально сочетаются с формальным определением доказательства в университетских учебниках: серия логических шагов, каждый из которых вытекает из предыдущих.
Компьютерщики научились использовать эту способность. Чтобы проверить доказательство, заставьте компьютер проанализировать каждый логический шаг. Звучит просто, но на самом деле доказательства в журналах пишут не так. Эти рассказы оставляют за скобками все рутинное или очевидное… Все привыкли к традиционным фразам: «Несложно убедиться, что…», «Используя методы Чизбургера и Чипса, модифицированные так, чтобы учитывать изолированные сингулярности, видим, что…», «Несложный расчет показывает…». Компьютеры (пока) с подобными задачами не справляются. Но люди-то всегда могут переписать доказательство, заполнив все подобные пропуски, и тогда компьютер вполне может проверить каждый его шаг.
Мы не прыгаем сразу же обратно в огонь по одной простой причине: программы, которые проверяют доказательство, тоже необходимо проверить, но лишь один раз. Вообще-то это универсальное программное обеспечение, которое применимо к любому доказательству, записанному в надлежащем формате. Все, что может вызывать сомнения, сконцентрировано здесь. Проверьте его — и потом с его помощью можно проверять все остальное. Можно даже упростить себе работу, написав программу проверки доказательства на языке, который позволит проверить ее при помощи гораздо более простой программы проверки.
В последние годы таким образом были проверены доказательства многих ключевых математических теорем. Для этого их нередко требовалось перевести в другую форму, более подходящую для компьютерных манипуляций. Один из последних триумфов — проверка и подтверждение доказательства теоремы Жордана: всякая замкнутая кривая без самопересечений на плоскости делит плоскость на две связные области. Утверждение может показаться очевидным, но пионеры топологии долго не могли строго доказать его. В конце концов это удалось в 1887 г. Камилю Жордану, опубликовавшему доказательство на 80 страницах, но позже его нередко критиковали за необоснованные ограничения. Поэтому слава досталась Освальду Веблену, давшему в 1905 г. более подробное доказательство. Веблен заявил: «[Жорданово] доказательство… не удовлетворяет многих математиков. В нем теорема принимается без доказательства в существенном особом случае, когда речь идет о простом многоугольнике; что же касается дальнейшего изложения, то следует признать по крайней мере, что не все детали в нем приведены».
Математики без колебаний приняли критику Веблена, но недавно Хейлс еще раз проанализировал доказательство Жордана и не нашел в нем «ничего, на что можно было бы возразить». Более того, замечание Веблена о многоугольнике звучит странно: теорема для него достаточно прозрачна, да и доказательство Жордана вовсе не опирается на этот частный случай{22}. У доказательств-рассказов есть собственные проблемы. С ними надо держать ухо востро и проверять, совпадает ли популярная версия рассказа с его оригинальным вариантом.
В процессе работы над гипотезой Кеплера Хейлс получил в 2007 г. формальное, проверенное компьютером доказательство теоремы Жордана, на что потребовалось 60 000 строк компьютерного кода. Вскоре после этого группа математиков, воспользовавшись другим программным обеспечением, получила другое формальное доказательство. Компьютерная проверка не застрахована от ошибок на 100 %, но то же можно сказать и о традиционных доказательствах. Более того, многие математические научные труды, вероятно, содержат технические ошибки. Время от времени такие ошибки обнаруживаются и в большинстве случаев оказываются безвредными. Серьезные ошибки, как правило, замечают раньше, чем они приводят к нарушениям и делают что-то явно бессмысленным. Это еще один недостаток доказательства-рассказа — плата за то, что доказательство делается понятным человеку: иногда нестрогая логика выглядит на первый взгляд очень убедительно.
Хейлс называет свой подход Project FlysPecK. Согласно первоначальной оценке, работа над ним должна была занять около 20 лет. За первые девять лет достигнут очень существенный прогресс, так что проект может завершиться досрочно.
6. Новые решения старой задачи. Гипотеза Морделла
Настало время нам вновь окунуться в теорию чисел и двинуться по направлению к Великой теореме Ферма. Чтобы подготовить почву, я начну с менее известной, но, по мнению некоторых, еще более важной задачи. В 2002 г. Эндрю Гранвиль и Томас Такер представили ее следующим образом:
«В 1922 г. Морделл написал одну из величайших статей в истории математики… В самом конце статьи он задал пять вопросов, которые сыграли важную роль в мотивировании значительной части исследований XX в. в области диофантовой арифметики. Ответ на самый важный и сложный из этих вопросов дал Фальтингс в 1983 г., выдвинув для этого идеи, которые можно назвать одними из наиболее глубоких и мощных в истории математики».
Упомянутый здесь Луис Морделл — британский специалист по теории чисел, родившийся в США в еврейской семье литовского происхождения, а Герд Фальтингс — немецкий математик. Вопрос, о котором идет речь, приобрел известность как гипотеза Морделла. В цитате, помимо прочего, обозначен ее точный статус: блестяще доказана Фальтингсом.
Гипотеза Морделла относится к крупному отделу теории чисел — к диофантовым уравнениям. Они названы так в честь Диофанта Александрийского, написавшего где-то около 250 г. н. э. знаменитую книгу «Арифметика». Считается, что первоначально она включала в себя 13 книг, но до нас дошли лишь шесть, и все в позднейших копиях. Это не был арифметический текст в буквальном смысле, т. е. речь в нем не шла о сложении и умножении. По существу, это был первый текст по алгебре, в котором были собраны почти все познания греков о том, как нужно решать уравнения. В нем использовалась даже некая рудиментарная форма алгебраического языка: судя по всему, для обозначения неизвестного в ней использовался вариант греческой буквы «сигма» (мы для этого используем x), для квадрата неизвестного (вместо нашего x2) — , а для куба неизвестного (вместо нашего x3) — . Сложение обозначалось тем, что символы помещались рядом друг с другом, а вычитание имело собственный символ. Величина, обратная неизвестному (наше 1/x), выглядела как и т. д. Эти обозначения восстановлены на основании позднейших копий и переводов и могут быть не вполне точными. Классическая греческая математика требовала, чтобы решения уравнений были рациональными числами, т. е. дробями вроде 22/7, сформированными из целых чисел. Часто требовалось даже, чтобы они сами были целыми числами. Все задействованные числа были положительными: представление об отрицательных числах появилось несколькими столетиями позже в Китае и Индии. Сегодня мы называем подобные задачи диофантовыми уравнениями. В «Арифметике» можно обнаружить замечательно глубокие результаты. В частности, Диофант, судя по всему, знал, что любое целое число может быть представлено в виде суммы четырех полных квадратов целых чисел (включая нуль). Лагранж впервые доказал это в 1770 г. Но нас в данном случае интересует другой результат — формула для пифагоровых троек, в которых сумма двух полных квадратов дает третий полный квадрат. Название происходит от теоремы Пифагора: именно таким соотношением связаны стороны прямоугольного треугольника. Самый известный пример — знаменитый треугольник 3, 4, 5: (3 + 4 = 5). Еще один пример — треугольник 5, 12, 13: (5 + 12 = 13). Рецепт поиска пифагоровых троек сформулирован в виде двух лемм (вспомогательных утверждений), помещенных перед Предложениями 29 и 30 в Книге X «Начал» Евклида.
Приведенная у Евклида процедура позволяет получить бесконечно много пифагоровых троек. Морделл знал несколько других диофантовых уравнений, для которых существует формула с бесконечным числом решений. Он знал также, что существует другой тип диофантовых уравнений, имеющих бесконечно много решений, которые не описываются формулой. Существуют так называемые эллиптические кривые — достаточно глупое название, поскольку они не имеют практически никакого отношения к эллипсам, — где бесконечность числа решений возникает потому, что любые два решения можно скомбинировать так, чтобы получилось еще одно. Сам Морделл доказал одно из фундаментальных свойств таких уравнений: все бесконечное множество решений может быть получено при помощи этого процесса из конечного их числа.
Помимо этих двух известных типов уравнений, все остальные диофантовы уравнения, которые мог придумать Морделл, попадали в одну из двух категорий. Либо про уравнение было известно, что число его решений конечно (или их просто нет), либо никто не мог сказать наверняка, является ли число его решений конечным или бесконечным. В сущности, ничего нового в этом не было, но Морделлу показалось, что он видит в этом закономерность, которую до него никто не замечал. Закономерность эта относилась вовсе не к теории чисел — скорее, ее можно было отнести к топологии. Чтобы разобраться в этом, необходимо было рассматривать решения уравнений в комплексных числах, а не в рациональных или целых. А это, что ни говори, противоречило самому духу диофантовых уравнений.
Здесь стоит добавить несколько деталей, которые пригодятся нам позже. Не бойтесь формул: они нужны мне в основном для того, чтобы можно было ссылаться на что-то конкретное. Сосредоточьтесь на рассказе, который лежит за ними.
x + y = z.
Разделив обе части уравнения на z, получим
(x/z) + (y/z) = 1.
Согласно главе 3, это означает, что пара рациональных чисел (x/z, y/z) лежит на единичной окружности в плоскости. Далее пифагорово уравнение берет начало в геометрии и имеет геометрическую интерпретацию: связанный с ним треугольник является прямоугольным. Формула, которую я только что вывел, позволяет дать чуть другую геометрическую интерпретацию, причем не одной, а всех пифагоровых троек. Решения пифагорова уравнения непосредственно соответствуют всем рациональным точкам единичной окружности. Мы считаем точку рациональной, если рациональны обе ее координаты.
Из этого можно сделать немало интересных выводов. Если привлечь тригонометрию (но можно обойтись и одной алгеброй), обнаружится, что для любого числа t точка
лежит на единичной окружности. Более того, если t рационально, то рациональна и эта точка. Все рациональные точки возникают подобным образом, так что мы получили исчерпывающую формулу для всех решений пифагорова уравнения. Она эквивалентна евклидовой формуле, которая, в свою очередь, совпадает с диофантовой. К примеру, если t = 22/7, формула даст результат
Можно проверить: 308 + 435 = 533. Для нас точная формула не слишком важна, важно, что она существует.
Это не единственное диофантово уравнение, для всех решений которого существует единая формула, но таких уравнений относительно немного. Например уравнения Пелля, такие как x = 2y + 1. У этого уравнения бесконечно много решений (3 = 2 2 + 1, 17 = 2 12 + 1) и для них существует общая формула. Однако упорядоченность пифагоровых троек этим не ограничивается; геометрия подсказывает нам и другие закономерности. Предположим, мы имеем две пифагоровы тройки. Следственно, существует два соответствующих им решения пифагорова уравнения — две рациональные точки на окружности. Геометрия предлагает естественный способ «сложить» эти точки. Начнем с точки (1, 0), в которой окружность пересекает горизонтальную ось, и найдем углы между этой точкой и двумя точками-решениями. Сложим эти два угла (см. рис. 25) и посмотрим, что получится. Точка, разумеется, тоже лежит на окружности, и короткий расчет покажет, что она также рациональна. Таким образом, имея два любых решения, мы можем получить третье. Математики уже заметили множество подобных фактов, причем большинство из них обретает смысл сразу же, как только мы вспоминаем о рациональных точках на окружности.
«Короткий расчет», который я небрежно пропустил, делается с использованием тригонометрии. Классические тригонометрические функции, такие как синус и косинус, теснейшим образом связаны с геометрией окружности. В расчете, на который я ссылался, используются стандартные, довольно элегантные формулы вычисления синуса и косинуса суммы двух углов через синусы и косинусы самих углов. Существует много способов получения синусов и косинусов, и один из них, достаточно изящный, основан на интегральном исчислении. Если вы будете интегрировать алгебраическую функцию 1/1-x, то результат может быть выражен, используя функцию синус. Точнее, нам нужна функция, обратная синусу: угол, синус которого равен интересующему нас числу{23}.
Интеграл возникает, когда мы пытаемся вывести формулу длины дуги окружности методами математического анализа, а геометрия окружности дает простое, но очень важное следствие для этого результата. Длина единичной окружности равна 2, поэтому пройдя расстояние 2 вдоль окружности, вы окажетесь в точости на том же месте. То же можно сказать о любом расстоянии, кратном 2: по стандартному математическому соглашению положительные целые числа соответствуют направлению против часовой стрелки, а отрицательные — по часовой стрелке. Следовательно, синус и косинус числа остаются неизменными при добавлении к аргументу величины 2, взятой целое число раз. Мы говорим, что эти функции периодические с периодом 2.
Аналитики XVIII и XIX вв. обобщили эту интегральную формулу и нашли целую группу интересных новых функций, аналогичных знакомым тригонометрическим. Эти новые функции выглядели загадочно; они были периодическими, как синус и косинус, но хитроумно периодическими. Вместо одного периода, к примеру 2 (или кратных ему), они имели два независимых периода. Если вы попытаетесь проделать такое с действительными функциями, то получите всего лишь константы, но для комплексных чисел здесь открываются широкие возможности.
Начало исследованиям в этой области положили итальянский математик Джулио ди Фаньяно и плодовитый Эйлер. Фаньяно пытался при помощи интегрального исчисления найти длину дуги эллипса, но не сумел вывести формулу в явном виде. Сегодня это уже не удивительно, ведь мы знаем, что такой формулы не существует. Однако он заметил, что длины различных особых дуг эллипса находятся между собой в определенных отношениях. Результаты своих исследований Фаньяно опубликовал в 1750 г. Эйлер в аналогичной ситуации заметил те же отношения и представил их в виде формального отношения интегралов. Они похожи на интеграл, связанный с функцией синуса, но квадратичное выражение под знаком квадратного корня сменяется кубическим многочленом или многочленом четвертой степени, к примеру, таким: (1 x) (1 4x).
В 1811 г. Адриен Мари Лежандр опубликовал первую книгу объемного трехтомного трактата об этих интегралах, известных как эллиптические благодаря своей связи с длиной дуги сегмента эллипса. Однако он умудрился пройти мимо самого важного их свойства: существования новых функций, аналогичных синусу и косинусу, обратные функции к которым достаточно просто выражают величину интеграла{24}. Гаусс, Нильс Хенрик Абель и Карл Якоби быстро заметили упущение. Гаусс оставил свои мысли при себе, что для него вполне типично. Абель в 1826 г. представил во Французскую академию собственную работу, но Коши, президент Академии, потерял рукопись, и опубликована она была только в 1841 г., через 12 лет после трагической ранней кончины Абеля от чахотки. Однако в 1827 г. вышла другая статья Абеля на ту же тему. Якоби положил новые «эллиптические функции» в основу громадного тома, опубликованного в 1829 г., и этот труд направил исследования в области комплексного анализа по совершенно новому пути.
В результате был выявлен целый комплекс взаимосвязанных свойств, аналогичных свойствам тригонометрических функций. Оказалось, что соотношение, замеченное Фаньяно и Эйлером, можно интерпретировать иначе, в виде простого списка формул, связывающих эллиптические функции суммы двух чисел с эллиптическими функциями самих чисел. Но самая интересная черта эллиптических функций оставляет тригонометрические функции далеко позади. Эллиптические функции не просто периодические; для них характерна двойная периодичность. Линия одномерна, поэтому и рисунок ее может повторяться только в одном направлении, вдоль линии. Комплексная плоскость двумерна, так что рисунок на ней может повторяться, как на обоях: вдоль бумажной полосы и одновременно поперек — вдоль стены, на соседние полосы. С каждой эллиптической функцией связаны два независимых комплексных числа (ее периоды), прибавление любого из которых к переменной не меняет значение функции.
Повторяя этот процесс, мы приходим к выводу, что значение функции не меняется при добавлении к переменной любой целочисленной комбинации двух периодов. Эти комбинации можно интерпретировать и геометрически: они определяют на комплексной плоскости решетку, которая разбивает плоскость на параллелограммы; все, что происходит в одном параллелограмме, повторяется и во всех остальных (см. рис. 26). Если мы рассмотрим отдельно взятый параллелограмм и то, как он соединяется с соседними, то получим, что нам придется отождествить противоположные его стороны, как тор определяется через отождествление противоположных сторон квадрата (см. рис. 12). Параллелограмм, противоположные стороны которого попарно отождествляются, топологически тоже представляет собой тор. Иными словами, точно так же, как синус и косинус связаны с окружностью, эллиптические функции связаны с тором.
Есть здесь и связь с теорией чисел. Я сказал, что функция, обратная синусу, получается путем интегрирования формулы, в которой фигурирует квадратный корень из квадратного трехчлена (т. е. многочлена второй степени). Эллиптические функции в этом похожи, но квадратный трехчлен в них заменяется на многочлен третьей или четвертой степени. Случай с четвертой степенью уже упоминался, потому что исторически он появился первым, но теперь давайте сосредоточимся на случае с многочленом третьей степени. Если мы обозначим квадратный корень как y, а многочлен как ax + bx + cx + d, где a, b, c и d — числовые коэффициенты, то x и y удовлетворяют уравнению:
y = ax + bx + cx + d.
Это уравнение можно рассматривать в нескольких различных контекстах, в зависимости от того, какие ограничения наложены на переменные и коэффициенты. Если все это действительные числа, уравнение определяет кривую на плоскости. Если это комплексные числа, то специалисты по алгебраической геометрии все равно называют множество решений этого уравнения кривой просто по аналогии. Но теперь это кривая в пространстве пар комплексных чисел, четырехмерном в действительных координатах. И кривая в данном случае — это поверхность с точки зрения действительных координат.
На рис. 27 показаны типичные действительные эллиптические кривые y = 4x 3x + 2 и y = 4x 3x. Поскольку y появляется в уравнении в виде квадрата, кривая симметрична относительно горизонтальной оси. В зависимости от коэффициентов это либо одна волнообразная кривая, либо кривая с отдельным овальным компонентом. В комплексных числах кривая всегда представляет собой единое связное множество.
Если мы потребуем, чтобы переменные и коэффициенты были рациональными, в игру вступит теория чисел и мы получим диофантово уравнение. Его графическое представление зачем-то называется эллиптической кривой, хотя совершенно не похоже на эллипс. Все дело в том, что это уравнение связано с эллиптическими функциями. Это как назвать окружность треугольной кривой только потому, что она связана с тригонометрией. Однако это название уже высечено на скрижалях, так что нам придется мириться с ним.
Теория эллиптических функций — глубокая и богатая теория, математики открыли у эллиптических кривых бессчетное количество красивых свойств. Одно из них аналогично тому, как мы объединяем два решения пифагорова уравнения, складывая соответствующие углы и получая третье решение. Две точки на эллиптической кривой можно «сложить», проведя через них прямую линию и посмотрев, в какой точке она пересечет кривую в третий раз (см. рис. 28). (Заметим, что третья точка обязательно существует, поскольку уравнение кубическое. Однако она может оказаться «в бесконечности» или совпасть с одной из первых двух точек, если прямая пройдет по касательной к кривой.) Если первые две точки у нас обозначены как P и Q, обозначим третью как P*Q.
Расчет показывает, что если P и Q — рациональные точки, то и точка P*Q рациональна. Операция * придает набору рациональных точек алгебраическую структуру, но оказывается полезной и при рассмотрении еще одной связанной с этим операции. Выберм любую рациональную точку O на кривой и определим:
P + Q = (P*Q) *O.
Эта новая операция подчиняется некоторым фундаментальным законам обычной алгебры, причем O ведет себя как нуль и превращает множество всех рациональных точек в то, что специалисты по алгебре называют группой (см. главу 10). Важно, что здесь, как с пифагоровыми тройками, можно «сложить» любые два решения и получить третье. То, что «групповой закон» действует на рациональные точки, поразительно: в частности, это означает, что стоит нам найти два рациональных решения диофантова уравнения, и мы автоматически получим множество других решений.
Около 1908 г. Пуанкаре задался вопросом: существует ли конечный набор решений, такой, чтобы из него можно было получить все остальные решения последовательным применением групповой операции? Это важно, потому что из существования такого набора следует, что все рациональные решения можно охарактеризовать при помощи конечного списка решений. В интереснейшей работе 1922 г. Морделл доказал, что ответ на вопрос Пуанкаре положителен. После этого эллиптические кривые стали центральным элементом теории чисел, поскольку далеко не все диофантовы уравнения могут похвастать такой степенью контроля. Итак, эллиптические кривые, как и пифагорово уравнение, имеют бесконечное множество рациональных решений. Многие диофантовы уравнения, напротив, имеют конечное число или вообще не имеют решений. Я собираюсь немного отклониться от темы и поговорить о целом семействе подобных уравнений и полученном недавно замечательном доказательстве того, что существуют лишь очевидные решения.
Пифагорейцы были увлечены своим уравнением, потому что верили: в основе Вселенной лежат числа. В поддержку этой философии они обнаружили, что музыкальной гармонией управляют простые числовые отношения. Это было установлено экспериментально при помощи наблюдений за звучанием натянутой струны. Струна с такой же степенью натяжения, но вдвое меньшей длины, дает ноту на октаву выше. Это самое гармоничное сочетание двух нот — настолько гармоничное, что звучит даже несколько простовато. В западной музыке следующая по значению гармония — кварта, где одна струна по длине составляет 3/4 другой струны, и квинта, где длина одной струны составляет 2/3 от длины другой.
Начав с 1 и умножая последовательно на 2 или 3, можно получить числа 2, 3, 4, 6, 8, 9, 12 и т. д. — числа вида 2a3b. Благодаря связи с музыкой они получили название гармонических. В XIII в. во Франции еврейский ученый по имени Гершон бен Соломон Каталан написал книгу «Врата небес», посвятив три ее части физике, астрономии и метафизике. В 1343 г. епископ Мо убедил его сына (по крайней мере историки считают, что, вероятно, это был его сын) Леви бен Гершома написать математическую книгу «Гармония чисел». В нее вошла, в частности, задача, которую впервые поставил композитор и теоретик музыки Филипп де Витри: когда два гармонических числа могут различаться на единицу? Подобные пары найти несложно: сам де Витри знал их четыре: (1, 2), (2, 3), (3, 4) и (8, 9). Но Гершом доказал, что это все возможные решения и других не существует.
Среди перечисленных де Витри пар гармонических чисел наибольший интерес привлекает пара (8, 9). Первое число в ней — куб, 2; второе — квадрат, 3. Математики заинтересовались, могут ли другие квадраты и кубы различаться на единицу; Эйлер доказал, что не могут, за исключением тривиального случая (0, 1) и случая (1, 0), если разрешены отрицательные числа. В 1844 г. уже другой Каталан опубликовал более всеобъемлющее заявление, о котором, должно быть, думали многие математики, но которое никто до него не счел нужным озвучить. Речь идет о бельгийском математике Эжене Шарле Каталане, который в 1844 г. написал в один из ведущих математических журналов того времени Journal fr die Riene und Angewandte Mathematik следующее:
«Покорнейше прошу вас, сударь, объявить в вашем журнале следующую теорему, кою я почитаю верной, хотя до сего момента и не преуспел в доказательстве; быть может, другие добьются большего успеха. Два последовательных целых числа, кроме 8 и 9, не могут быть последовательными степенями; иначе говоря, уравнение xm yn = 1, в котором все неизвестные — положительные целые числа, допускает лишь одно решение».
Это утверждение получило известность как гипотеза Каталана. Показатели степени m и n здесь — целые числа больше 1.
Несмотря на частичные успехи, гипотеза Каталана долгое время упорно противостояла всем усилиям математиков, пока в 2002 г. ее не доказал вдруг Преда Михайлеску. Этот математик родился в 1955 г. в Румынии, а в 1973 г. поселился в Швейцарии и к тому времени только что получил докторскую степень. Темой его диссертации было «Деление кругов и проверка на простоту», и речь в ней шла о применении теории чисел при проверке на простоту (глава 2). Эта задача не имеет особого отношения к гипотезе Каталана, но Михайлеску пришло в голову, что методы-то его точно имеют к ней отношение. В них он отталкивался от идей, уже упоминавшихся мной в главе 3: гауссового построения правильного 17-угольника и связанных с этим алгебраических уравнений, решения которых называют круговыми числами. Доказательство получилось достаточно сложным и произвело в математическом сообществе настоящий фурор. Из него явствует, что какие бы величины мы ни выбрали для двух показателей степени, число решений остается конечным — и помимо очевидных решений с участием 0 и ±1 единственное решение, представляющее интерес, это 3 2 = 1.
Приведенные примеры наглядно показывают, что одни диофантовы уравнения имеют бесконечное множество решений, а другие — нет. Что тут интересного, скажете вы, эти два варианта перекрывают весь спектр возможностей. Но если вы спросите, какие уравнения к какому типу относятся, все станет намного интереснее.
Морделл готовил учебник по диофантовым уравнениям. В то время эта область математики напоминала биологию на раннем этапе ее развития: множество собранных коллекционерами бабочек, и никакой систематической классификации. Наука пребывала почти в том же состоянии, в каком ее оставил Диофант, только беспорядка стало еще больше: это был бессистемный набор ловких трюков, для каждого типа уравнений свой, и вот такой не слишком подходящий для учебника материал отчаянно нуждался в систематизации, чем Морделл и занялся.
В какой-то момент он, должно быть, заметил, что все уравнения, достоверно имеющие бесконечное множество рациональных решений, — такие как пифагорово уравнение или эллиптические кривые — имеют одну общую черту. Он сосредоточился на одном классе уравнений — на тех, в которых (после перевода в рациональную форму, как я сделал с пифагоровым уравнением) присутствует всего две переменных. Есть два случая, когда нам заранее известно, как найти бесконечное множество решений. Пример одного из них — пифагорово уравнение в эквивалентной форме x + y = 1. В этом случае существует формула для нахождения решений. Вставьте в эту формулу любое рациональное число и получите рациональное решение, причем формула позволяет получить все решения. Пример второго случая — эллиптические кривые: здесь существует процесс, позволяющий получать новые решения из старых, и гарантия того, что если начать с подходящего конечного набора решений, этот процесс позволит получить их все.
Гипотеза Морделла утверждает, что во всех случаях, когда уравнение имеет бесконечное множество рациональных решений, должно присутствовать одно из названных свойств. Существует либо общая формула, либо процесс, позволяющий получить все решения из подходящего конечного их набора. Во всех остальных случаях число рациональных решений конечно; примером могут служить уравнения вида xsup>m — yn = 1, которые фигурируют в гипотезе Каталана. Решения здесь в каком-то смысле случайны и не имеют никакой структурной основы.
Морделл пришел к этому наблюдению немного иным путем. Он обратил внимание на то, что все уравнения с бесконечным числом рациональных решений имеют одно поразительное топологическое свойство. У всех у них род равен 0 или 1. Вспомните из главы 4, что род — это понятие из области топологии кривых, которое указывает на то, сколько в данной поверхности отверстий. Род сферы равен 0, род тора — 1, род тора с двумя отверстиями равен 2 и т. д. Но откуда берутся поверхности в задаче из теории чисел? Из координатной геометрии. Мы видели, что пифагорово уравнение, которое интерпретировано в терминах рациональных чисел и допускает действительные решения, определяет окружность. Морделл сделал еще один шаг и допустил комплексные решения. Любое уравнение с двумя комплексными переменными определяет то, что специалисты по алгебраической геометрии называют комплексной кривой. Однако с точки зрения действительных чисел и зрительного восприятия человека каждое комплексное число двумерно: у него на деле две компоненты — действительная и мнимая части. Так что «кривая» в комплексном смысле есть поверхность для нас с вами. И, как у всякой поверхности, у нее есть род, — вот и все.
Всякий раз, когда про уравнение было известно, что оно имеет конечное число решений, его род равнялся по крайней мере двум. Род важных уравнений, статус которых относительно числа решений не был известен, тоже равнялся по крайней мере двум. Морделл на основании достаточно хлипких, как тогда казалось, указаний сделал отчаянно смелый шаг: он предположил, что любое диофантово уравнение с родом 2 или больше имеет конечное число рациональных решений. Так, по мановению его руки, диофантовы бабочки аккуратно распределились по родственным семействам; точнее говоря, по родам (даже термин подходящий).
В гипотезе Морделла была всего лишь одна крохотная загвоздка. Она связала между собой две чрезвычайно разные вещи: рациональные решения и топологию. В то время подобная связь казалась в высшей степени неубедительной. Если даже она существовала, то никто не знал, как ее искать; непонятно было даже, как подступиться к этой проблеме. Так что гипотеза представляла собой отчаянное, ничем не подтвержденное заявление, обещавшее, однако, громадные потенциальные дивиденды.