Затем расширяем вторую область, добавляя к ней более узкую тропку, которая обходит вокруг всех трех областей, построенных до сих пор.
Продолжаем в том же духе, прокладывая еще более узкую тропинку от третьей области. Затем возвращаемся к первой, добавляем к ней еще более узкую тропинку и т. д.
Повторяем это построение бесконечное число раз. Получившиеся области многократно окружены бесконечно сложной сетью бесконечно узких тропинок. Но поскольку с каждым шагом области подходят все ближе ко всему, построенному до того, в конечном итоге все три области имеют одну и ту же (бесконечно сложную) границу.
Первоначально озера Вады были придуманы с целью показать, что топология плоскости не так проста, как можно вообразить. Много лет спустя выяснилось, что такие области возникают сами собой в численных методах решения алгебраических уравнений. К примеру, кубическое уравнение x³ = 1 имеет лишь одно действительное решение x = 1; кроме того, у него есть два комплексных решения где =√−. Комплексные числа можно представить как точки на плоскости, где число x + iy соответствует точке с координатами (x, y).
Стандартный метод нахождения численных аппроксимаций начинается со случайно выбранного комплексного числа; затем особым образом вычисляется второе число, а затем процесс повторяется, пока числа не сблизятся. Результат, полученный таким образом, близок к решению. К какому именно из трех решений он близок, зависит от того, где вы начинаете, и происходит это весьма хитроумным образом. Предположим, мы окрасим точки на комплексной плоскости в соответствии с тем, к какому решению они ведут: пусть, к примеру, это будет серый цвет, если решение x = 1, светло-серый, если решение и темно-серый, если решение Тогда точки, окрашенные в заданный оттенок серого, обозначат область, и можно доказать, что все три области имеют одну и ту же границу.
В отличие от построения Вады, области здесь не являются связными: они разбиваются на бесконечное множество отдельных кусочков. Однако поразительно, что области такой сложности возникают естественно в такой фундаментальной задаче численного анализа.
Последний лимерик Ферма[28]
И стар и млад в науке шаткой
Лет триста бились над загадкой.
Наконец-то решенье:
Прав Ферма, прочь сомненья…
Толстый том плюс к той записи краткой.
Ошибка Малфатти
Из мемуаров доктора Ватсапа
– Необычайно! – воскликнул я.
Сомс бросил в мою сторону недовольный взгляд, очевидно раздраженный тем, что его прервали, – в тот момент он с упоением копался в своей обширной коллекции гипсовых отпечатков беличьих следов.
– Ответ кажется очевидным, но тем не менее, судя по всему, неверен! – воскликнул я.
– С очевидным это бывает, – заметил Сомс. – В смысле, оказывается неверным, – добавил он тоном пояснения.
– Слышали когда-нибудь о Джан-Франческо Малфатти? – спросил я.
– Убийца с топором?
– Нет, Сомс, это был Фрэнк Макавити по прозвищу Хакер.
– Ах. Мои извинения, Ватсап, вы, разумеется, правы. Я отвлекся. Мой образец следов Ratufa macroura разрушается. Большехвостая гигантская белка.
– Малфатти был итальянским геометром, Сомс. В 1803 г. он заинтересовался вопросом о том, как высечь из клиновидного куска мрамора три цилиндрические колонны так, чтобы максимизировать их суммарный объем. Он предположил, что эта задача эквивалентна тому, чтобы вычертить на треугольном сечении куска мрамора три окружности так, чтобы максимизировать их суммарную площадь.
– Наивное, но, вероятно, верное предположение, – отозвался Сомс. – Хотя колонну, конечно, можно высечь и наискось.
– О-о, я не имел в виду… Но допустим, что его предположение было верным, поскольку вопрос всегда можно нужным образом переформулировать. Малфатти считал очевидным, что решение должно состоять из трех кругов, касающихся друг друга и двух внешних сторон треугольника.
– Понятно, в чем тут промах, – сказал Сомс тем раздражающе небрежным тоном, которым он часто пользуется, когда ему удается мгновенно схватить суть дела, не доступную большинству прочих смертных.
– А я, откровенно говоря, не понимаю, – сказал я. – Ведь если круг лежит внутри треугольника, не перекрывается другими кругами и не касается сторон и соседей так, как описано, то его можно увеличить.
– Верно, – отозвался Сомс. – Но это лишь доказывает достаточность, но не необходимость условий касания.
– Это я понимаю, Сомс. Но… как еще могли бы располагаться круги?
– Ну, касание может быть организовано и другими способами, конечно. К примеру, Ватсап: вы рассматривали простейший случай, с равносторонним внешним треугольником?
– Во-первых, – сказал Сомс, – есть вариант Малфатти, на рисунке слева. Но как насчет варианта справа? Здесь опять же ни один круг не может быть увеличен, но схема касаний иная. Маленькие круги касаются большого, но не касаются друг друга. Вместо этого есть большой круг, который касается всех трех сторон треугольника.
Я вгляделся в рисунки.
– На глаз, Сомс, в первом варианте площадь больше.
Он рассмеялся.
– Что показывает лишь, насколько легко наш глаз обмануть, Ватсап. Предположим, что стороны треугольника имеют единичную длину. Тогда вариант Малфатти имеет площадь 0,31567, но площадь второго варианта составляет 0,31997, то есть немного больше.
Бывают моменты, когда от эрудиции Сомса буквально перехватывает дыхание.
– Может быть, разница и невелика, Сомс, но вывод ясен. Малфатти ошибся.
– В самом деле. Мало того, Ватсап, разница между вариантом Малфатти и правильным решением в некоторых случаях может оказаться намного больше. К примеру, если треугольник будет длинным, тонким и равнобедренным, то верным решением будет расположить круги один на другом, и площадь такого варианта будет почти вдвое превосходить вариант Малфатти.
Он сделал паузу, чтобы швырнуть раскрошившийся гипсовый отпечаток следов Ratufa macroura через всю комнату в камин.
– Ирония в том, – добавил он наконец, – что вариант Малфатти никогда не бывает лучшим. «Жадный» алгоритм – вписать в треугольник наибольший возможный круг, затем найти наибольший круг, который вписывается в оставшиеся промежутки, и напоследок проделать то же самое в третий раз – всегда лучше и всегда приводит к верному ответу.
Дополнительную информацию см. в главе «Загадки разгаданные».
Квадратные остатки
Полные квадраты заканчиваются на одну из цифр 0, 1, 4, 5, 6 или 9. Они не могут заканчиваться на 2, 3, 7 или 8. Более того, последняя цифра квадрата числа зависит только от последней цифры этого числа.
Если число заканчивается на 0, то его квадрат тоже заканчивается на 0.
Если число заканчивается на 1 или 9, то его квадрат заканчивается на 1.
Если число заканчивается на 2 или 8, то его квадрат заканчивается на 4.
Если число заканчивается на 5, то его квадрат тоже заканчивается на 5.
Если число заканчивается на 4 или 6, то его квадрат заканчивается на 6.
Если число заканчивается на 3 или 7, то его квадрат заканчивается на 9.
Специалисты по теории чисел предпочитают описывать подобные эффекты с помощью целых чисел по некоторому модулю. Если взять модуль 10, то достаточно рассмотреть только числа 0–9: возможные остатки от деления любого числа на 10. Их квадраты (по модулю 10) равны
0 1 4 9 6 5 6 9 4 1
и приведенный выше список правил для определения последней цифры квадрата по последней цифре числа – это всего лишь другой способ сказать то же самое.
За исключением начального 0, список квадратов (по модулю 10) симметричен: числа 1, 4, 9, 6 после 5 повторяются в обратном порядке: 6, 9, 4, 1. Симметрия возникает благодаря тому, что квадраты n и 10 – n по модулю 10 равны. В самом деле, 10 – n – то же, что – n (mod 10), а n² = (−n)². Поэтому данные четыре числа в списке фигурируют дважды; 0 и 5 встречаются там только по одному разу, а 2, 3, 7, 8 не встречаются вовсе. Это не слишком демократично, но это так.
Что происходит, если мы берем другой модуль? Величины квадратов по этому модулю называются квадратичными вычетами. (Здесь под «вычетом» подразумевается остаток от деления на модуль.) Остальные цифры при этом становятся квадратичными невычетами.
Предположим, к примеру, что модуль равен 11. Тогда возможные полные квадраты (чисел, меньших 11) равны
0 1 4 9 16 25 36 49 64 81 100.
По модулю 11 это дает
0 1 4 9 5 3 3 5 9 4 1.
Таким образом, квадратичные вычеты (по модулю 11) – это
0 1 3 4 5 9.
А невычеты – это
2 6 7 8.
Приведем небольшую таблицу.
На первый взгляд, никаких особенных закономерностей, кроме уже упомянутых, не заметно. На самом деле этим отчасти и интересна данная область математики: хотя шаблоны существуют, отыскать их непросто. Многие величайшие математики, в том числе Эйлер и Карл Фридрих Гаусс, уделяли внимание этой области.
Возводя число в квадрат, мы умножаем его на самого себя, а там, где речь заходит об умножении, в теории чисел главную роль всегда играют простые числа. Поэтому стоит начать с простых модулей – 2, 3, 5, 7, 11 – в приведенном списке. Модуль 2 уникален: единственные возможные вычеты по модулю 2 – это 0 и 1, и оба они являются полными квадратами. Для всех остальных простых чисел примерно половина вычетов являются квадратами, а остальные – не являются. Точнее, если p – простое число, то существует (p + 1)/2 различных квадратичных вычетов и (p − 1)/2 невычетов. Квадратичные вычеты обычно являются квадратами двух различных чисел, n² и (– n)² для подходящего n. Однако 0 встречается в списке лишь однажды, потому что –0 = 0.
Составные модули усложняют ситуацию. Теперь одни и те же вычеты иногда могут быть квадратами больше чем двух чисел. К примеру, 1 по модулю 8 встречается четыре раза, как квадрат 1, 3, 5 и 7. Лучший способ разобраться во всем этом – воспользоваться современной абстрактной алгеброй, но имеет смысл взглянуть и на модуль 15. У него два простых множителя: 3 × 5. А вот список квадратов:
Таким образом, квадратичные вычеты по модулю 15 равны
0 = 0²
1 = 1², 4², 11², 14²
4 = 2², 7², 8², 13²
6 = 6², 9²
9 = 3², 12²
10 = 5², 10²
Некоторые вычеты возникают один раз, некоторые дважды, некоторые четырежды. Те, которые встречаются в списке меньше четырех раз, являются квадратами чисел, кратных либо 3, либо 5, то есть простым множителям 15. Все остальные числа возникают группами по четыре, где квадраты всех четырех равны.
Это общая закономерность для любого модуля вида pq, где p и q – различные нечетные простые числа. Числа от 0 до pq – 1, не кратные ни p, ни q, разделяются на четверки с равными квадратами. (Это не работает, если одно из простых чисел равно 2: к примеру, 10 = 2 × 5, но мы уже видели, что в этом случае квадраты либо одиноки, либо стоят парами.)
В алгебре мы привыкаем к мысли, что у каждого положительного числа имеется два квадратных корня: один положительный, другой отрицательный. Но в арифметике по модулю pq большая часть чисел (те, что не делятся ни на p, ни на q) имеет по четыре различных квадратных корня.
Этот любопытный факт имеет замечательное приложение, к которому мы и перейдем.
Бросание монетки по телефону
Предположим, что Алиса и Боб хотят сыграть в бросание монетки с вероятностью того или иного результата 50:50. Как мы уже знаем, Алиса находится в Алис-Спрингс, а Боб – в Боббингтоне. Могут ли они бросать монетку по телефону? Главная загвоздка – та же, что при игре в покер. Если бросает монетку (или проделывает любую другую операцию с равновероятным исходом) Алиса и она же сообщает результат Бобу, то тот никак не может быть уверен, что она говорит правду. Конечно, в наше время они могли бы делать это во время общения по скайпу и наблюдать за бросанием монетки, но даже в этом случае результат можно подделать, сняв заранее несколько бросков и показав собеседнику запись вместо онлайн-трансляции.
Бросание монетки – то же, что игра в покер колодой из двух карт, так что игроки вполне могут воспользоваться методикой, описанной выше. Однако существует и другой элегантный способ достичь того же результата с использованием квадратичных вычетов. Вот как это можно сделать.
Алиса выбирает два больших простых числа p и q. Она держит их в секрете, но отправляет Бобу их произведение n = pq. Вы скажете, что Боб мог бы найти p и q путем разложения n на простые множители, но на сегодняшний день, насколько известно, не существует практичного способа сделать это, если числа p и q достаточно велики – скажем, по 100 знаков в каждом. Даже самым быстрым компьютерам, использующим самые быстрые алгоритмы, понадобилось бы на это время, превышающее время жизни Вселенной. Так что Боб останется в неведении.
Однако существуют очень быстрые способы проверить 100-значное число и узнать, является ли оно простым. Так что Алиса сможет подобрать себе p и q методом проб и ошибок.
Боб выбирает произвольное целое x (mod n), которое держит в секрете.
Если он необычайно педантичен, то может быстро проверить, не является ли x произведением p и q: он не будет делить его на эти числа, поскольку их не знает, но найдет наибольший общий делитель (НОД) чисел x и n через алгоритм Евклида. Если результат окажется не равным 1, то получится, что он знает либо p, либо q, и процесс нужно будет начинать заново с новым x. Но на практике можно особо не беспокоиться, поскольку при p и q, содержащих по 100 знаков каждое, вероятность того, что одно из этих чисел окажется делителем произвольно выбранного x, составит 2 × 10–100.
Далее Боб вычисляет x² (mod n), что тоже можно сделать быстро, и отправляет результат Алисе. Они договорились, что если Алиса сможет правильно назвать x или – x, то она выиграет (это будет «орел»). В противном случае – проиграет («решка»).
Из предыдущей главы Алиса знает, что целые числа по модулю pq, не кратные ни p, ни q, имеют ровно по четыре квадратных корня. Поскольку x и – x при возведении в квадрат дают одно и то же, квадратные корни имеют вид a, – a, b, – b для подходящих a и b. Алиса знает p, q и x², из чего следует, что она может быстро вычислить четыре нужных корня. Два из них должны быть равны x и – x; два других – не равны. Так что вероятность угадать ± x верно у Алисы на 50 % – что эквивалентно честному бросанию монетки. Она выбирает одно из четырех чисел, скажем b, и отправляет его Бобу.
Боб сообщает Алисе, действительно b = ± x или нет; то есть права она или нет.
Ах, но как сделать так, чтобы Боб тоже не мог смошенничать? И откуда Бобу знать, что Алиса сделала все так, как должна была сделать?
В любом случае (верно b = ± x или нет) Боб может легко убедиться, что Алиса играла честно, если вычислит b² (mod n). Результат должен совпасть с x².
Если Алиса проигрывает, то она может убедиться в честности Боба, попросив его прислать ей простые множители n, то есть p и q. В обычных условиях это невозможно, но если Алиса проиграла, то Боб знает все четыре квадратных корня из x², а в теории чисел имеется хитрый прием, позволяющий быстро вычислить p и q по этим данным. Наибольшим общим делителем a + b и n является одно из наших двух простых чисел, а НОД опять же можно найти при помощи алгоритма Евклида. После этого второе число можно найти путем деления.
Как устранить нежелательное эхо
Квадратичные вычеты могут показаться типичным примером мудреных умствований, которые так любят математики-теоретики: интеллектуальной игрой, не имеющей никакого практического применения. Но было бы ошибкой думать, что математическая идея бесполезна, только потому, что она не проистекает очевидным образом из практических задач повседневной жизни. Ошибка также считать, что повседневная жизнь настолько прямолинейна, как кажется на поверхностный взгляд. Для изготовления даже такой простой вещи, как банка джема из супермаркета, нужно сварить стекло, вырастить сахарный тростник или сахарную свеклу, очистить сахар… и очень скоро вы обнаружите, что с головой погрузились в статистический анализ испытаний сортов растений на сопротивляемость болезням и в конструирование судов, используемых для перевозки различных компонентов готового продукта по всему земному шару. В мире, где живет 7 млрд человек, массовое производство продуктов питания не сводится к тому, чтобы просто собрать ягоды и сварить их.