Величайшие математические задачи - Йен Стюарт

Чтобы дать вам некоторое представление об этой новой и очень интересной области математики, я опишу одну из простейших сложных систем и объясню, почему мы не понимаем ее до конца. Эта система называется муравьем Лэнгтона. Кристофер Лэнгтон был одним из первых сотрудников Института Санта-Фе, который основали в 1984 г. физики Джордж Коуэн, Марри Гелл-Ман и другие для развития теории и приложений сложных систем. Лэнгтон придумал своего муравья в 1986 г. Технически это клеточный автомат, система клеток квадратной решетки, состояния которых обозначаются цветом. На каждом временно́м шаге цвет каждой клетки изменяется в соответствии с цветом соседних с ней клеток.

Правила просты до нелепости. Муравей живет на бесконечной квадратной решетке из клеток, и первоначально все они белые. Он всегда носит с собой неиссякаемый горшочек с черной краской и такой же горшочек с белой краской. Он может идти на север, на восток, на юг или на запад. Из соображений симметрии скажем, что первый шаг он делает на север. В каждый момент времени муравей смотрит на цвет клетки, в которой оказался, и перекрашивает ее из черной в белую или из белой в черную. Если клетка была белой, то после перекрашивания муравей поворачивает на 90° направо и делает один шаг вперед. Если клетка была черной, то он поворачивает на 90° налево и делает то же самое. И так до бесконечности. Если вы смоделируете поведение муравья, то сначала он будет рисовать простой симметричный узор из белых и черных квадратов. Время от времени он возвращается на клетку, где уже был, но петля при этом не замыкается, потому что цвет клетки изменился, и муравей повернет в другую сторону. Моделирование продолжается, и рисунок становится хаотичным и случайным. При этом в нем невозможно различить никаких закономерностей: в основе своей это просто беспорядок. На этой стадии можно подумать (и вполне здраво), что такое хаотичное поведение будет продолжаться бесконечно. В конце концов, вернувшись в хаотично раскрашенный регион, муравей непременно сделает серию хаотичных шагов. Если вы будете продолжать моделирование, то следующие примерно 10 000 шагов подтвердят ваше предположение. Однако затем, если вы будете настойчивы, проявится закономерность. В движениях муравья возникнет повторяющийся цикл из 104 шагов, в результате которого он проходит две клетки по диагонали. После этого он будет двигаться, прорисовывая широкую диагональную полосу из черных и белых клеток, которую иногда называют магистралью, и так до бесконечности (см. рис. 49).

Все описанное до сих пор может быть доказано по всей строгости просто последовательным перебором муравьиных шагов. Это будет достаточно длинное доказательство — список из 10 000 шагов, — но все же доказательство. Но математика системы станет более интересной, если мы зададимся чуть более общим вопросом. Что если еще до начала движения муравья мы перекрасим некоторое конечное число клеток решетки в черный цвет? Мы можем выбрать для этого любые клетки: это может быть случайный набор, черный квадрат или Мона Лиза. Их может быть миллион, или миллиард, или еще больше, но не бесконечное количество. Что произойдет?

Обычное движение муравья резко меняется при встрече с любой из новых черных клеток. Он может долго бродить окрест, рисуя сложные орнаменты и раз за разом перерисовывая их заново… Но во всех до сих пор предпринятых попытках, какой бы ни была первоначальная конфигурация, в конце концов муравей непременно принимался за строительство магистрали при помощи все того же 104-шагового цикла. Всегда ли это происходит? Является ли магистраль единственным «аттрактором» движения муравья? Никто не знает. Это одна из фундаментальных нерешенных задач теории сложности. Максимум, что нам известно, — это то, что, какой бы ни была первоначальная конфигурация черных клеток, муравей не останется навечно в пределах ограниченной области поля.

Матрица Адамара, названная в честь Жака Адамара, представляет собой квадратную матрицу из нулей и единиц, такую, что в любых двух ее рядах или столбцах половина элементов совпадает, а другая половина — отличается. На рис. 50 можно увидеть матрицы размеров 2, 4, 8, 12, 16, 20, 24 и 28, где 0 и 1 обозначены черным и белым цветом. Такие матрицы появляются во многих математических задачах и в компьютерных науках, в первую очередь в теории кодирования. (В некоторых приложениях, в том числе в задаче, которой первоначально занимался Адамар, белые квадраты соответствуют −1, а не 0.)

Адамар доказал, что подобные матрицы могут существовать только при n = 2 или n, кратном 4. Теорема Пейли 1933 г. доказывает, что матрица Адамара существует всегда для n, кратного 4 и равного 2a(pb + 1), где p — нечетное простое число. Из чисел, кратных 4, под эту теорему не подпадают 92, 116, 156, 172, 184, 188, 232, 236, 260, 268 и другие, более крупные значения n. Гипотеза утверждает, что матрица Адамара существует любых размеров, кратных 4. В 1985 г. К. Савад нашел матрицу размера 268. Есть и другие числа, не удовлетворяющие условию теоремы Пейли, с которыми уже разобрались. В 2004 г. Хади Харагани и Бехруз Тайфех-Резайе нашли матрицу Адамара размера 428, и теперь минимальное значение n, для которого она неизвестна, составляет 668.

Это диофантово уравнение xa +yb = zc, где a, b и c — положительные целые числа, показатели степени. Я назову это уравнение уравнением Ферма — Каталана, потому что его решения имеют отношение как к Великой теореме Ферма (см. главу 7), так и к гипотезе Каталана (см. главу 6). Если a, b и c малы, ненулевые целые решения не особенно удивительны. К примеру, если все они равны 2, мы имеем уравнение Пифагора, которое, как известно со времен Евклида, имеет бесконечно много решений. Так что основной интерес представляют те случаи, когда показатели степени велики. Формально они являются «большими», когда s = 1/a + 1/b + 1/c меньше 1. Известно лишь десять больших решений уравнения Ферма — Каталана: