Журнал Компьютерра - Журнал «Компьютерра» №47-48 от 20 декабря 2005 года

• Название: Журнал «Компьютерра» №47-48 от 20 декабря 2005 года
• Автор: Журнал Компьютерра
• Жанр: Прочая околокомпьтерная литература

---

К слову, попутно удалось оптимизировать графики движения некоторых поездов Северо-Кавказской железной дороги. Так любимый всеми ростовчанами дополнительный «летний» поезд №642 Ростов-Адлер стал проводить в пути в одну сторону на три часа меньше, а в другую - почти на два. Оказалось, что научно, с использованием компьютерной техники к этому вопросу раньше не подходили. Таким образом, к удовольствию всех заинтересованных лиц, проблему удалось разрешить бескровно. Дело прекратили, никого не наказали, индюки, видимо, ассимилировались в теплых краях и на родину не вернулись.

Пару лет спустя, встретившись с одноклассником, избравшим карьеру биолога, после совместного распития неизвестных напитков, я узнал следующую историю. Товарищ рассказал, что бюллетень «Вопросы прикладной орнитологии» недавно напечатал интереснейшую статью одного известного ученого, в которой приводились неопровержимые, даже подкрепленные милицейскими документами факты необычайного поведения домашних птиц, в частности индюков. Автор статьи делал вывод, что птицы, проживая долгое время совместно с человеком, серьезно эволюционируют. В них даже просыпается коллективный разум. Причем сила их разума во многом определялась солнечной активностью. Поэтому на юге России птицы изменялись быстрее. Ученый проводил крайне смелые эксперименты, закончившиеся полным успехом. Результаты их могут привести к настоящей революции в орнитологии.

Что же, с нетерпением ожидаю запроса из Академии наук…

Наука: Проблемы 2000 года: Гипотеза Берча-Свиннертон-Дайера

В одной из предыдущих статей раздела (посвященной гипотезе Ходжа; «КТ» #609) мы уже касались алгебраической геометрии. Тогда же упоминалось, что к ней имеют прямое отношение как минимум три из семи задач на миллион. Об одной из таких задач мы и поговорим: гипотеза Берча-Свиннертон-Дайера касается рациональных точек алгебраических многообразий - иными словами, рациональных решений полиномиальных уравнений.

Введение

Алгебраическую геометрию, как и многие другие области математики, невозможно причислить ни к древним, ни к современным разделам науки. С одной стороны, ничто не ново под луной: еще древних греков, заложивших основы самого метода математического познания, интересовали проблемы, которые и сегодня исследует алгебраическая геометрия. С другой же - о глубине современных методов и задач этой науки древние греки не могли даже догадываться (как зачастую и нынешние математики, работающие в других областях).

Ключевые задачи алгебраической геометрии сформулировать и понять совсем не трудно. Вот, например, общее направление, к которому относится и гипотеза Берча-Свиннертон-Дайера: выяснить, сколько у данного полиномиального уравнения решений в рациональных[Имеющих вид p/q, где p, q - целые. - Л.Л.-М.] числах. Но чтобы сформулировать саму гипотезу, требуется изрядная подготовка.

Немного истории

Как мы уже упоминали, общая проблема поиска рациональных решений была поставлена - и в самых простых частных случаях решена - очень давно. Одна из древнейших формулировок, встречающаяся еще в арабских трактатах X века, имеет геометрическую природу. Это так называемая задача о конгруэнтных числах: какие рациональные числа могут быть площадями прямоугольных треугольников с рациональными длинами сторон? Однажды Фибоначчи[Он же Леонардо Пизанский, итальянский ученый и одновременно купец (1170-1250). - Л.Л.-М.], находясь при дворе Фредерика II, не сходя с места нашел такой треугольник с площадью 5; есть и более экзотические примеры. Ответ таков (желающие могут его проверить): n - конгруэнтное число тогда и только тогда, когда число рациональных решений уравнения y2 = x3 - n2x бесконечно.

Первым, кто поставил проблему поиска рациональных решений в ее современном смысле, был великий французский математик Анри Пуанкаре. Пуанкаре сделал для развития математики (в том числе алгебраической геометрии) и физики очень многое. О других его достижениях у нас еще будет повод поговорить, ведь именно он сформулировал одну из «задач на миллион», в его честь и названную гипотезой Пуанкаре.

Брайан Берч (Bryan Birch) и Питер Свиннертон-Дайер (Peter Swinnerton-Dyer) (да-да, Берч-Свиннертон-Дайер - это два человека, а не три) занимались этой проблемой в начале шестидесятых. Примечательно, что у истоков гипотезы стоит один из ранних компьютеров - кембриджский EDSAC, с помощью которого Берч и Свиннертон-Дайер исследовали поведение так называемых эллиптических кривых (что это такое, поясним чуть позже).

Суть

Итак, в чем же суть проблемы, о которой мы сегодня рассказываем? Рассмотрим кривую, заданную полиномиальным уравнением с двумя переменными. Одна из важнейших характеристик такой кривой - ее род (genus). Дать здесь классическое определение рода кривой будет трудно, но мы приблизимся к нему с другой стороны. Начнем с поверхностей. Наверное, каждый в детстве читал о топологах, которые не могут отличить кружку от бублика - ведь обе поверхности топологически эквивалентны тору. Так вот, у поверхностей тоже есть род; род бублика, например, равен единице. А вообще род поверхности (если быть точным, род «ориентируемой поверхности») - это количество замкнутых кривых, по которым ее можно разрезать так, чтобы она не распалась на отдельные части. Можете сами попробовать: сферу или плоскость так разрезать нельзя, у них род 0, тор (он же бублик[]) можно разрезать один раз, хоть вдоль, хоть поперек, но после этого останется либо цилиндр, либо кусок плоскости, и второго разреза уже не получится. Все ориентируемые поверхности похожи на сферу с ручками (термин из алгебраической геометрии): сколько у сферы ручек, столько и разрезов можно сделать.

Теперь представьте, что уравнение, которое нас интересует, нужно решать в комплексных числах. Тогда множество его решений - это двухмерная поверхность. Ее род в данном случае и называется родом кривой.

Итак, род представляет собой целое неотрицательное число; кривые рода 1 - это и есть эллиптические кривые, которые сейчас находят применение в криптографии. О них и идет речь в гипотезе Берча-Свиннертон-Дайера. Кстати, если ограничиться вещественными числами, эллиптические кривые определяются совсем просто: это кривые, заданные одним из уравнений Вейерштрасса y

Как уже упоминалось, гипотеза касается множества рациональных решений данного уравнения. Берч и Свиннертон-Дайер рассматривали функцию L, вычисляемую через количество рациональных решений по модулю простого числа p (в вещественном случае - количество решений уравнения y2 #8801; x3 + ax +b по модулю p). Функция эта строится аналогично дзета-функции Римана, о которой мы уже рассказывали, и свойства имеет соответствующие: L, если рассмотреть ее как функцию комплексного переменного, сходится на полуплоскости, но при этом аналитически продолжается и на другую половину. Вычислить значения L и ее аналитического продолжения для каждой конкретной кривой не очень просто, но вполне возможно; в частности, это можно сделать автоматически, на компьютере.

Гипотеза Берча-Свиннертон-Дайера утверждает, что количество и структура множества рациональных решений эллиптической кривой тесно связаны с поведением L-функции в единице[Если быть точным, то по этой гипотезе ранг группы рациональных решений есть степень первого ненулевого члена разложения L в ряд Тейлора в единице; иными словами, L(z) около единицы похожа на (z-1)r, где r - ранг.]. В частности, количество рациональных точек бесконечно тогда и только тогда, когда L(1)=0.

Благодаря работам отечественного математика Виктора Александровича Колывагина, а также доказательству теоремы Ферма Эндрю Уайлсом это утверждение уже доказано в одну сторону: если L(1) #8800; 0, то количество рациональных точек конечно. Доказательство в другую сторону - предмет долгих и безуспешных поисков. Кроме того, открыт путь для обобщений гипотезы - в частности, к изучению рациональных точек не только кривых, но и поверхностей более высокой размерности (то есть уравнений с бульшим количеством переменных). Например, Леонард Эйлер еще в 1769 году выдвинул гипотезу, что уравнение x4 + y4 + z4 = t4 не имеет ненулевых решений. Эту гипотезу, как и похожую на нее гипотезу Ферма, долгое время не могли доказать, но результат в данном случае оказался иным: в 1988 году обнаружился контрпример (точнее, бесконечно много контрпримеров). Вот минимальный из них (проверить легко - но представьте, как трудно было бы его найти без развитой теории): 2682440 4 + 15365639 4 + 18796760 4 = 20615673 4

Приложения

Алгебраическая геометрия - наука, приложения которой, как правило, отнюдь не очевидны. Математикам, чтобы годами биться над интересной задачей, приложения и вовсе не нужны: да, великая теорема Ферма имеет некоторый криптографический смысл, но попытки ее доказательства привели к созданию и развитию нескольких важных разделов современной математики задолго до того, как криптография оформилась как математическая дисциплина.