Величайшие математические задачи

Доказательство того, что задача о пяти принцах не имеет решения, начинается с предположения о том, что такое решение существует, и это приводит к противоречию. Любое решение должно иметь число точек 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 соседей: шесть в собственном слое, три вверху и три внизу. Количество соседей такое же, как во втором варианте упаковки квадратных слоев, и Кеплер, проведя тщательный геометрический анализ, показывает, что в реальности этот вариант упаковки полностью совпадает со вторым. Единственная разница заключается в том, что квадратные слои лежат не горизонтально, а под углом. Кеплер пишет: «Таким образом, самая плотная трехмерная упаковка с треугольной решеткой не может существовать без квадратной решетки, и наоборот». К этому я еще вернусь: это важно.