Текст книги "Величайшие математические задачи"

При 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 мы столкнемся с аналогичной идеей в гораздо более хитроумном контексте, где она помогла решить еще более великую топологическую задачу.