В.БОРО, Д.ЦАГИР, Ю.РОЛЬФС, Х. КРАФТ. Е. ЯНЦЕН

ЖИВЫЕ ЧИСЛА

ПЯТЬ ЭКСКУРСИЙ

ЖИВЫЕ ЧИСЛА

ПЯТЬ ЭКСКУРСИЙ

Mathematische Miniaturen 1

LEBENDIGE ZAHLEN

FÜNF EXKURSIONEN

WALTER BORHO

DON ZAGIER

JÜRGEN ROHLFS

HANSPETER KRAFT

JENS CARSTEN JANTZEN

Bonner Universität

Birkhäuser Verlag Basel⋅Boston⋅Stuttgart 1981

СОВРЕМЕННАЯ МАТЕМАТИКА

ПОПУЛЯРНАЯ СЕРИЯ

В. БОРО, Д. ЦАГИР, Ю.РОЛЬФС, Х. КРАФТ, Е. ЯНЦЕН

ЖИВЫЕ ЧИСЛА

ПЯТЬ ЭКСКУРСИЙ

Перевод с немецкого Е. Б. ГЛАДКОВОЙ

МОСКВА «МИР» 1985

ББК 22.13 Ж 67 УДК 511

Живые числа

Ж67 Сб. статей 1981 г.: Пер. с нем. — М.: Мир, 1985. — 128 с. ил.

Доступное и занимательное изложение некоторых разделов современной теории чисел: дружественные числа, первые 50 миллионов простых чисел, пифагоровы числа... Элементарные факты удачно сочетаются с результатами научных исследований. Авторы — математики из ФРГ.

Для всех, кто интересуется теорией чисел, начиная со школьников старших классов.

ББК 22.13 517.1

Редакция литературы по математическим наукам

© 1981 Birkhäuser Verlag Basel

© перевод на русский язык, «Мир», 1985

ОТ ИЗДАТЕЛЬСТВА

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

Представленный в сборнике материал практически отсутствует в научно-популярной литературе на русском языке.

Живое и доступное изложение, удачное сочетание элементарных фактов с результатами глубоких исследований делают книгу интересной и полезной для самого широкого круга лиц — от школьников до преподавателей институтов.

Мы надеемся, что читатель получит удовольствие от знакомства с этими пятью прекрасными миниатюрами.

ПРЕДИСЛОВИЕ

Ритуал вступления в ряды преподавателей — старая традиция немецких университетов. После присуждения ученой степени доктора будущий преподаватель продолжает научную работу и через несколько лет представляет факультету более обширный текст — диссертацию для получения Venia Legendi — права самостоятельно обучать студентов и читать лекции. Диссертация докладывается на заседании совета факультета, где и происходит ее научное обсуждение. Через несколько недель ритуал завершается своей кульминацией — открытой вступительной лекцией.

В некоторых университетах вступительные лекции, кажется, утеряли свое значение. В Бонне же мы постарались сохранить традицию и сделать вступительные лекции одной из важных составных частей научной жизни. На этих лекциях серьезная и значительная тема должна быть изложена так, чтобы не только математики, но и представители других естественных наук, а также и студенты могли следить за ходом рассуждений. В лекции надо осветить историю вопроса, связь разделов математики между собой и с другими науками. Кроме того, нужно, чтобы слушатели хотя бы в небольшой степени почувствовали очарование математики и яснее поняли ее роль в духовной жизни общества.

В этом небольшом сборнике публикуются пять вступительных лекций, прочитанных в Боннском университете в 1974—1979 гг.; все они идут под общим девизом «Числа». Я считаю, что издание этого сборника вполне оправданно, так как каждый из авторов изящно и увлекательно излагает избранную им тему и даже открывает перед читателем панораму современных исследований. Надеюсь, что появление настоящей книги будет способствовать выпуску и других сборников вступительных лекций.

Ф. Хирцебрух

Бонн, октябрь 1980

ВСТУПЛЕНИЕ

Каждый из пяти авторов этой небольшой книжки, рассказывая об избранной им математической теме, старался добиться того, чтобы обычные числа предстали перед читателем как живые. Может быть, с помощью этих пяти миниатюр удастся хотя бы в малой степени передать некоторым читателям ощущение чар математики, которое испытывают те, кто избрал ее своей специальностью.

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

Мы приглашаем читателя на пять небольших экскурсий в мир чисел. По красивым и разнообразным местам они ведут к нескольким возвышенностям, с которых можно увидеть вдали первые горные вершины новых исследований. Каждая из прогулок начинается «внизу в долине», т. е. с понятий и задач, для понимания которых достаточно школьных знаний: простые числа, суммы делителей, теорема Пифагора, кривые, разбиения. Однако потом то тут, то там попадаются места, для преодоления которых требуются кое-какие альпинистские навыки, чтобы и более опытным участникам похода не было скучно. Впрочем, каждый сам легко установит, где ему надо будет обойти пару трудных мест. Но ко всем главным возвышенностям, с которых открываются виды, путешественники будут доставлены по канатной дороге и тем избавлены от тяжкого труда подъёма — доказательств.

Расскажем теперь коротко о каждом из пяти маршрутов.

Первый проходит по совсем легкой, ровной тропинке между суммами делителей и критериями простоты числа. Лишь в конце станет видно, что она вливается в важное направление современной математики. Вальтер Боро рассказывает нам замечательную историю о дружественных числах, которая ведет из дворца багдадского халифа в современные вычислительные центры. Мы познакомимся с одним из старых математических видов спорта — охотой за дружественными числами, в котором непревзойденным чемпионом мира долгое время был Леонард Эйлер.

Дон Цагир предъявляет нам список мировых рекордов — наибольших известных простых чисел, и мы с одного взгляда убеждаемся, что простые числа следует признать самыми капризными и строптивыми из всех объектов, какие только изучают математики. И тут же он убеждает нас в прямо противоположном — что простые числа безусловно и чуть ли не с педантической точностью подчиняются определенным законам. Особенно изумляет явная формула Римана для числа π(х) простых чисел, не превосходящих x. А затем снова выявляется строптивость простых чисел при сравнении асимптотических формул Лежандра, Гаусса и Римана для π(х) с фактическим распределением первых 50 миллионов простых чисел, приводящем к дико скачущей кривой, похожей на температурную.

Юрген Рольфс рассказывает нам о суммах двух квадратов. Его маршрут начинается с пифагоровых троек чисел, для которых вмиг выводится общая формула. Вслед за этим определяется число пифагоровых треугольников, у которых длина гипотенузы не превышает заданной величины. При этом оказывается, что тема пифагоровых троек не только не завершается с открытием общей формулы, а наоборот, лишь после этого становится по-настоящему интересной. Кончается путешествие задачей из физики о распространении тепла по спасательному кругу (тору) из тонкой жести. Это распространение

описывается дифференциальным уравнением в частных производных, при решении которого ключевую роль играет число v(m) представлений числа m в виде суммы двух квадратов. Таким образом, здесь теория чисел и математический анализ тесно связаны между собой.

Ханспетер Крафт вводит нас в область, где неразрывно переплелись теория чисел и геометрия, — алгебраические кривые и диофантовы уравнения. И эта экскурсия начинается с формулы для пифагоровых троек, которая выводится с помощью геометрического метода Диофанта. Точно так же можно решить более общую задачу о нахождении всех точек с рациональными координатами, лежащих на кривой второго порядка. Аналогичная задача для кривой третьего порядка оказывается несравненно более трудной и интересной. Нам демонстрируют геометрический метод, которым можно построить все искомые рациональные точки, исходя из некоторого конечного множества таких точек (теорема Морделла). В дальнейшем ходе экскурсии мы узнаем и еще многое другое об эллиптических кривых; правда, рассказ о точках кручения и последних результатах Б. Мазура рассчитан уже на читателя, несколько семестров изучавшего математику.

И в заключение Енс Карстен Ян цен знакомит нас с деятельностью специалистов по комбинаторике — людей, которые делают с конечными множествами всё мыслимое и немыслимое, а потом спрашивают себя, сколькими способами это можно сделать. Он рассказывает нам о перестановках и разбиениях, диаграммах Юнга и канонических таблицах, а также об удивительной связи между этими комбинаторными понятиями. Затем мы узнаём, чем занимаются специалисты по теории представлений и сколь многим обязаны специалистам по комбинаторике те, кто изучает представления симметрических или общих линейных групп. И наконец, новый поворот темы о связи теории представлений с комбинаторикой: теория представлений возвращает долг комбинаторике, унифицируя и обобщая знаменитые тождества Эйлера, Гаусса и Якоби для степенных рядов.

Итак, экскурсии проводятся по пяти совершенно различным маршрутам, да еще мы имеем дело с пятью несхожими индивидуальностями и темпераментами экскурсоводов, так что дорожной скуки опасаться не приходится. При всём том внимательный читатель заметит, что маршруты экскурсий постоянно соприкасаются и пересекаются.

Например, тождество Якоби для степенных рядов встречается не только у Янцена, а дзета-функция Римана не только у Цагира — и то и другое упоминается, пусть и мимоходом, у Боро и Рольфса. Суммы делителей появляются не только в первой, но и в третьей экскурсии. Кому хоть раз довелось погрузиться поглубже в мир математики, известны такие неожиданные взаимосвязи. Зачастую выявляются связи между ее разделами, не имеющими на первый взгляд абсолютно ничего общего. И это — не какая-нибудь там экзотика или случайное периферийное явление, а типичная черта всякой настоящей математики. Маленькие неожиданности, с которыми мы здесь столкнемся, совершенно «невинны» по сравнению с фантастическими сюрпризами такого рода, то и дело встречающимися в математических исследованиях. Обнаружение таких неожиданных, очень часто глубинных связей принадлежит к самым волнующим событиям в жизни математика.

Однако пора нам кончать со сборами и отправляться в дорогу. Обратимся к самим числам.

Вальтер Боро

Енс Карстен Янцен

Ханспетер Крафт

Юрген Рольфс

Дон Цагир

Вальтер Боро

ДРУЖЕСТВЕННЫЕ ЧИСЛА. ДВУХТЫСЯЧЕЛЕТНЯЯ ИСТОРИЯ ОДНОЙ АРИФМЕТИЧЕСКОЙ ЗАДАЧИ

Это история двух чисел

В каждом из них 152 цифры. У первого 800 различных делителей, у второго — 3200. Числа А и В обладают следующим замечательным свойством: сумма 779 собственных делителей1). А равна В, сложив же 3199 собственных делителей B, мы получим Л. Эту интересную пару нашел в 1972 г. амстердамский математик Херман те Риле. Его открытию предшествовала долгая история, начало которой теряется в глубине веков. С этой историей я и хотел бы вас познакомить.

При этом я попытаюсь (в полной мере это вряд ли возможно) удовлетворить как математиков, так и нематематиков. В интересах последних мы по возможности постараемся обходиться без формул, теорем и доказательств, за что я заранее приношу извинения коллегам-профессионалам. Нематематиков же я прошу проявлять терпение в тех редких случаях, когда всё же появится какая-нибудь формула или когда я позволю себе небольшое отступление, понятное только специалисту.

1) То есть делителей, отличных от самого числа. — Прим. перев.

Известно, что в древнем Вавилоне основанием системы счисления служило число 60, о чем до сих пор напоминает обычай делить час на 60 минут, а минуту на 60 секунд. И хотя простые люди и в то время пользовались десятичной системой счисления, математики применяли шестидесятеричную. Дело в том, что действия с дробями не пользовались у них большой популярностью (как и у сегодняшних школьников). Поэтому число 60, сравнительно небольшое и имеющее много делителей, оказалось идеальным основанием системы счисления. Из двенадцати различных делителей числа 60 большинство получило даже особые названия, вошедшие в языки разных народов. Например, немецкие крестьяне и сейчас охотно употребляют при счете дюжины (12), мандели (15) и копы (60) — всё делители шестидесяти.

Античные математики вообще считали очень важным рассматривать вместе с каждым числом все его делители. Числа, имеющие много делителей, назывались «abundant» (избыточными), а имеющие мало делителей, — «defizient» (недостаточными). При этом в качестве меры использовалось не количество, а сумма собственных делителей, которую сравнивали с самим числом. Так например, для десяти сумма делителей

1+2 + 5 = 8 меньше 10,

так что делителей «недостаток». Для двенадцати же

1+2 + 3 + 4 + 6 = 16 больше 12,

т. е. делителей «избыток». Поэтому 10 — «недостаточное», а 12 (и уж тем более 60) — «избыточное» число.

Встречается и «пограничный» случай, когда сумма собственных делителей равна самому числу. Например, для шести

1+2 + 3 = 6.

То же для 28:

1 + 2 + 4 + 7+14 = 28.

Такие числа древние греки особенно ценили и назвали их совершенными. Точно неизвестно, когда и где впервые обратили внимание на совершенные чи-

ела. Предполагают, что они были известны уже в древнем Вавилоне и древнем Египте. Во всяком случае, вплоть до 5-го века н.э. в Египте сохранялся пальцевый счет1), при котором рука с загнутым безымянным пальцем и выпрямленными остальными изображала 6 — первое совершенное число. Тем самым этот палец как бы сам стал причастен к совершенству и потому получил привилегию нести на себе кольцо (фото 1). Таково одно из объяснений того отмечаемого специалистами по истории культуры факта, что почти у всех цивилизованных народов существует обычай носить кольцо именно на безымянном пальце.

Первое доказанное утверждение о совершенных числах принадлежит Эвклиду (примерно 300 г. до н.э.). В его «Началах», выдержавших после библии, пожалуй, наибольшее число изданий, мы находим в

Фото 1. Уже в древние времена существовала традиция носить кольцо на безымянном пальце. Рука Афродиты. Бронза, Греция, 3-й — 2-й в. до н. э. Музей «Уренмузеум» в Вуппертале. (Фотография воспроизводится с любезного разрешения И. Абелера.)

1) Обозначение чисел при помощи пальцев; см., например, Депман И. Я. История арифметики. — М.: Учпедгиз, 1959. — Прим. перев.

книге IX теорему 36, устанавливающую способ получения совершенных чисел. На современном языке она звучит так:

Теорема Эвклида. В тех случаях когда число

р = 1 + 2 + 4 + 8+ ... +2n = 2n+1 — 1

— простое, 2n⋅р является совершенным.

Для доказательства этого утверждения Эвклид использует свою теорему 35 — формулу суммы членов геометрической прогрессии. Позднее Никомах из Герасы указал первые совершенные числа: 6, 28, 496 и 8128. Все они получаются по способу Эвклида.

Большое внимание уделяли в античные времена и числам 220 и 284, у которых было подмечено следующее удивительное свойство: сумма собственных делителей числа 220 равна 284 и, наоборот, сумма собственных делителей 284 равна 220. Их назвали дружественными. Следы этих чисел тоже теряются во тьме веков. Весьма вероятно, что первым обратил на них внимание Пифагор (см. табл. 1). Впрочем, некоторые ссылаются на то более древнее место в библии, где говорится, что Иаков в знак примирения подарил Исаву ровно 220 овец и 220 коз. Средневековые комментаторы библии объясняли своим читателям «тайну», заключенную в числе 220, и считали непреложным фактом, что на магическую силу этого числа и рассчитывал хитроумный Иаков. С помощью аналогичных уловок наши предки будто бы завоевы-

Таблица 1. Хронологическая таблица.

ок. 500 до н. э.

Пифагор

1636

Ферма

ок. 300 до н. э.

Эвклид

1638

Декарт

ок. 1750

Эйлер

ок. 100 н. э.

Никомах

1830

Лежандр

ок. 300

Ямвлих

1851

Чебышев

1911

Диксон

836—901

Сабит

1929

Пуле

1946

Эскотт

ибн Хальдун

1968

Ли

1007

аль-Маджрити

1972

те Риле

1256—1321

ибн аль-Банна

вали также симпатии королей и сановников. В общем, об этом каждый волен иметь собственное мнение, а первым не допускающим двусмысленного толкования документом, содержащим упоминание о дружественных числах, является «Изложение пифагорейского учения» — трактат, написанный в 3-м веке н. э. неким Ямвлихом из Хальциса. Пифагорейская школа получила широкую известность не только благодаря пристрастию ее членов к мистике чисел, но я благодаря тому, что они высоко ценили дружбу. Ямвлих рассказывает, как однажды великий Пифагор на вопрос, кого следует считать другом, ответил: «Того, кто является моим вторым я, как числа 220 и 284».

Некоторые историки не считают Ямвлиха достойным доверия. Они хотели бы располагать свидетельствами современников Пифагора. К сожалению, с такими свидетельствами дела обстоят неважно, так как пифагорейская школа наряду с числовым мистицизмом и культом дружбы славилась еще и приверженностью к таинственности. Разглашение добытых математических знаний считалось кощунством. Сохранилось, например, предание о том, как после открытия Пифагором додекаэдра один из его учеников установил, что этот многогранник можно вписать в шар, и, вопреки традициям школы, обнародовал свое открытие. За такой «богохульный» поступок он понес наказание — утонул в море. Может быть, поэтому истинный первооткрыватель дружественных чисел предпочел остаться неизвестным... Сам я считаю, что проще всё-таки верить Ямвлиху и считать первооткрывателем Пифагора.

Если не учитывать совершенные числа (дружественные, так сказать, самим себе), то в древнем мире была известна единственная пара дружественных чисел — пара Пифагора, со следующим представлением в виде произведения простых1) чисел:

1) Определение простого числа напоминается в начале второго путешествия. — Прим. ред.

Указать какой-нибудь общий способ получения дружественных чисел, дающий эту пару и другие, желательно в бесконечном количестве (что для совершенных чисел удалось сделать Эвклиду) — задача, представляющая значительные трудности и в наши дни. Правда, один способ такого рода указал еще в 9-м веке арабский математик Сабит ибн Корра. Пусть он простит меня, но я не буду называть его полным именем: абу-Хасан Сабит ибн Корра ибн Марван аль-Харрани, которое сегодня представляется несколько длинноватым. Сабит был врачом и астрономом и в то же время одним из самых выдающихся мусульманских математиков. Он жил с 836 по 901 г., последнюю часть жизни — в Багдаде, где был доверенным лицом и советником халифа аль-Мутадида. Найденный Сабитом способ получения дружественных чисел звучит на современном языке так:

Теорема Сабита. Если все три числа р = 3—2n-1—1, q = 3⋅2n — 1 и r = 9⋅22n-1 — 1 — простые, то числа

— дружественные.

При n = 2 числа р = 5, q = 11 и r = 71 — простые, и получается пара чисел, найденная Пифагором. Однако теорема Сабита дает дружественные числа и при других л, например при n = 4 и n = 7:

В настоящее время известно, что этими тремя случаями исчерпываются все значения 20 000, при которых указанный способ дает дружественные числа. Использовал ли сам Сабит свою теорему для отыскания дружественных чисел при n > 2, неизвестно. Открытие второй (n = 4) и третьей (n = 7) пар дружественных чисел приписывалось ранее Ферма и Декарту соответственно, Однако недавно в од-

Фото 2. Страница рукописи арабского математика ибн аль-Банны (1256—1321), содержащая вывод второй пары дружественных чисел 17296 и 18416, открытие которой до сих пор приписывалось Ферма (1601—1665). (Частное собрание профессора филологического факультета Тунисского университета Мохаммеда Суисси, которому мы благодарны за любезное разрешение поместить здесь это факсимиле.)

ном из трактатов марокканского ученого ибн аль-Банны (1256—1321), сына архитектора, были обнаружены следующие строки (фото 2): «Числа 17296 и 18 416 являются дружественными; одно из них избыточно, другое недостаточно. Аллах всеведущ».

С течением времени формулы, предложенные Сабитом, были забыты, а его книгу открыли заново лишь в 19-м в. Впрочем, многие античные и арабские ученые, а также ученые средневековья посвящали в своих трактатах одну из глав совершенным и дружественным числам. Однако большей частью в этих трактатах было мало новых сведений и много ошибок. Кроме того, современного читателя несколько удивит то поразительное единодушие, с которым авторы этих сочинений настаивают на возможности практического использования дружественных чисел. Например, ибн Хальдун прилагает к своему трактату руководство по изготовлению талисмана дружбы, а мадридский ученый аль-Маджрити (ум. в 1007 г.) приводит рецепт, позволяющий добиться взаимности в любви: надо записать на чём-либо числа 220 и 284, меньшее дать съесть предмету страсти, а большее съесть самому; ученый добавляет, что действенность этого способа он проверил на себе.

В начале 17-го в. два французских математика — Пьер Ферма в 1636 г. и Ренэ Декарт в 1638 г. — независимо друг от друга и от Сабита получили те же формулы. О датах и обстоятельствах этих открытий имеются самые точные сведения. Хотя и в то время проблема обмена новыми знаниями еще не была решена— издание книг занимало длительное время, а математических журналов не существовало, — тем не менее дело обстояло значительно лучше, чем во времена Пифагора: ученые письменно сообщали о своих открытиях патеру Мерсенну1), и такое извещение было равноценно письму, отправляемому в настоящее время в редакцию «Mathematischen Annalen»2).

1) Известный французский математик (1588—1648). — Прим. перев.

2) Периодическое издание, сообщающее о математических открытиях. — Прим. перев.

Ферма и Декарт также написали Мерсенну, который в предисловии к своей ближайшей книге назвал их открытие крупным достижением гениальных математиков.

В ходе своих исследований Ферма и Декарт вывели формулу, дающую сумму делителей числа по его представлению в виде произведения степеней простых чисел. Эту формулу легко получить, исходя из следующих двух тождеств:

(1) σ(В⋅С) = σ(В)⋅σ(С), если В и С взаимно просты;

(2)

если р — простое.

Здесь через σ(А) обозначена сумма всех делителей числа А. так что сумма его собственных делителей равна σ(А) — А. Следовательно, условие того, что А и В — дружественные числа, можно записать в виде

или (3)

Эти три формулы удобны для вычислений. Кроме того, равенство (2) представляет исторический интерес, так как оно способствовало открытию знаменитой малой теоремы Ферма:

Если число n + 1 — простое, то оно является делителем pn—1 при любом натуральном р.

В процессе поиска совершенных и дружественных чисел Ферма (как это позже в большем объеме сделал Эйлер) составлял таблицы разложения на простые множители величины σ(pn) и при этом неизбежно «должен» был открыть свою малую теорему.

После периода малозначащих работ, последовавшего за работами Ферма и Декарта, существенного продвижения в решении проблемы дружественных чисел добился Леонард Эйлер. С присущей ему основательностью и энергией начал он штурм этой

задачи. Изложение результатов Эйлера можно найти в многотомном издании полного собрания его сочинений1).

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

Далее Эйлер занялся дружественными числами вида

с простыми р, q, r. (Условимся, что запись произведения abc с точками между сомножителями, т. е. а⋅b⋅с, означает взаимную простоту сомножителей. Это избавит нас в дальнейшем от громоздких формулировок.) Эйлер получил утверждение, очень похожее на теорему Сабита, но чуть более общее. Правда, с помощью своего обобщения он не смог найти новые дружественные числа, так как в то время таблицы простых чисел были составлены только до 100 000. Лишь Лежандр и Чебышев, используя новый критерий простоты чисел, сумели обнаружить с помощью теоремы Эйлера еще одну пару дружественных чисел. В настоящее время применение ЭВМ позволило получить этим методом и другие пары.

Наконец, Эйлер искал дружественные числа и совершенно иного вида, чем его предшественники, в частности нечетные. Он записывал их, например, так:

и либо, задавшись общим множителем а, получал для определения р и q диофантово уравнение второй

1) Opera Omnia; см. разделы: De numeris amicabilibus (О дружественных числах) и De summis divisorum (О суммах делителей).

степени, либо, задавшись двумя из трех простых чисел р, q, r или всеми тремя, искал подходящий общий множитель а. Вторым методом им были найдены, например, следующие пары нечетных дружественных чисел:

В своих работах Эйлер излагает пять различных методов для отыскания дружественных чисел; демонстрируя виртуозность в вычислениях и терпение, показывает на большом количестве примеров, как применять эти методы, и в заключение дарит изумленным современникам (занимавшимся той же проблемой примерно с таким же увлечением, но почти безрезультатно) почти 60 новых пар.

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

Следует отметить, что проблема дружественных чисел благодаря работам Эйлера приобрела совсем другой характер, нежели проблема совершенных чисел. Я лишен возможности систематически изложить дальнейшую, полную событий историю обеих задач со времен Эйлера до наших дней, отраженную в сотнях публикаций. Однако я хотел бы в самых общих чертах обрисовать разницу между ними. Поиски чётных совершенных чисел превратились в высокотехнический вид спорта (по четким правилам Эвклида). Каждое новое достижение здесь было одновременно и новым мировым рекордом в охоте на большие про-

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

Очарование такой охоты и радость при каждой удаче, очевидно, и побуждали Эйлера не довольствоваться тремя, четырьмя примерами, а искать все новые и новые числа. Эти чувства, кроме ловцов бабочек, могут, пожалуй, вполне понять еще лишь математики, втянувшиеся в охоту за конечными простыми группами (и спрашивающие себя, подобно Б. Фишеру, существует ли еще один «ребенок-монстр»). Один из математиков, открывших новые конечные простые группы (а именно, группы «типа G2»), американец Л. Диксон, охотился также и за дружественными числами. Он использовал методы Эйлера, но добыл только две новые пары.

Вообще, как видно из табл. 2, в которой указано число найденных каждым математиком пар дружественных чисел, Эйлер — признанный всеми авторитет — оставался непревзойденным вплоть до последних десятилетий. Первым побил рекорд Эйлера бельгийский математик Поль Пуле. Его двухтомная монография по теории чисел была издана в 1929 г. в Брюсселе под многозначительным названием «La chasse aux nombres» («Охота за числами»). Кроме всего прочего, в ней приведены 62 новые пары дружественных чисел. При этом Пуле — как ранее Лежандр и Чебышев — пошел по пути создания новых критериев простоты чисел. Значительная часть его исследований посвящена развитию идей французского математика Люка, открывшего в высшей степени эффективные критерии простоты.

Таблица 2. Математики, открывшие пары дружественных чисел.

В таблице перечислены все математики, отыскавшие пары дружественных чисел; указаны количество найденных пар и год открытия. (По статье Э. Дж. Ли, Journal of Recreational Mathematics, 1972; дополнено автором.)

Пифагор

1

-500

Вульф

4

1950

ибн аль-Банна

1

ок. 1300

Гарсиа

153

1957

Декарт

1

1638

Рольф

1

1965

Эйлер →

59

1747—1750

Оре, Аланен, Стемпл

9

1967

Лежандр/Чебышёв

1

1830/1851

Боро

41

1967—1974

Паганини

1

1866

Ли →

390

1968—1972

Зеельхофф

2

1884

Брэтли, Мак-Кей

14

1968

Диксон

2

1911

Мэйсон

14

1921

Коэн

62

1970

Пуле | →

108

1929—1948

Дэвид

12

1971 — 1972

Жерардэн

9

те Риле

4

1974

Браун

1

1939

Боро, Хоффманн, Небген, Рекков

25

1979

Эскотт →

219

1946

Новый «мировой рекорд» был установлен американцем Э. Эскоттом, а затем рекорд перешел к его соотечественнику Элвину Дж. Ли. По существу они также пользовались методами Эйлера, хотя и в усовершенствованной форме. Кроме того, Ли прибегнул— впервые в столь больших масштабах — к помощи ЭВМ.

С наступлением эры ЭВМ возник новый метод, о котором Эйлер не мог и помышлять, — перебирать все числа подряд, пока хватит машинного времени. Нашлись люди, которые, видимо, только и ждали, когда появится возможность производить громадные вычисления. Они занимались ими в течение двух лет, не считаясь с затратами, и добрались, кажется, до десятизначных чисел. Как относятся к этому грубому натиску конкурентов тонкие искусные ловцы, охотящиеся за числами подобно Эйлеру, Пуле и Ли? Трудно передать их чувства. Представьте себе страстного рыболова-любителя, неожиданно замечающего у ручья людей, которые просто осушают русло и за-

тем спокойно собирают рыбу! Впрочем, при этом обнаружилось, что рыболовы удили весьма успешно и выловили почти всю рыбу, так что «браконьерам» досталась лишь довольно скромная добыча.

В настоящее время известно в общей сложности около 1100 пар дружественных чисел. Их полный список был опубликован в 1972 г. в журнале «Journal of Recreational Mathematics» («Математика на досуге»). Его составили обладатель мирового рекорда Э. Ли и издатель журнала Дж. Мэдэчи. Пары расположены в порядке возрастания наименьшего числа. Список начинается трехзначной парой Пифагора и кончается 25-значной парой, найденной Эскоттом.

Пока неизвестно, конечно ли множество пар дружественных чисел, и лично я думаю, что это, может быть, так никогда и не будет известно. Впрочем венгерский математик Пауль Эрдёш доказал, что дружественные числа имеют плотность 0, т. е. их доля среди чисел, не превосходящих х, стремится к 0 с ростом x. Брауншвейгский математик Ханс-Иоахим Канольд установил, что в любой паре дружественных чисел одно число должно иметь по крайней мере три различных простых делителя, и поэтому теорема Сабита дает самые простые пары дружественных чисел. Сам я доказал, что пар A, В дружественных чисел, у которых произведение AB имеет заданное количество w простых делителей, существует лишь конечное число, а именно не более чем w2 . Однако на этих и на многих других отдельных результатах теоретического характера я не хотел бы здесь останавливаться, так как считаю, что духу рассматриваемой задачи гораздо больше отвечает построение конкретных числовых примеров.

Поэтому в заключение нашего путешествия я приглашаю вас отправиться вместе со мной на охоту за дружественными числами, вооружившись методом, существенно отличающимся от методов Эйлера. Речь идет об одном рецепте, по которому из уже известных дружественных чисел можно изготовить новые, значительно превосходящие исходные по величине. Я сперва сообщу вам сам рецепт, затем дам несколько пробных примеров его практического применения

и, наконец, намечу вкратце, как прийти к такому рецепту.

Рецепт. Возьмите пару дружественных чисел вида А = а⋅u, B = a⋅s с простым s.

Проверьте, является ли число р = u + s + 1 простым.

Если да и если не окажется (всякое бывает), что а делится на р, то при n = 1,2,3, ... справедливо следующее

Правило: если оба числа

— простые, то числа

— дружественные.

Пример 1. Возьмем пару Пифагора:

Числа s = 71 и p = u + s+ 1 = 55 + 72 = 127 — простые. Поэтому можно использовать указанное правило. При n = 1 числа q1, q2 не являются простыми, но уже при n = 2 мы получаем пару дружественных чисел

Эти, очень большие числа, полученные из пары 220, 284 почти без всяких вычислений, до сих пор не были известны!

Пример 2. Возьмем пару Эйлера

Здесь также числа s = 2699 и p = u + s+ 1 = 5281 являются простыми. Таким образом, по этой паре Эйлера тоже можно построить соответствующее «пра-

вило Сабита». В этом случае уже при n = 1 числа q1, q2 будут простыми, и мы получаем дружественные числа

Теперь я хотел бы наметить путь, который подводит к указанному рецепту. (Главное — «напасть» на такой рецепт. Дать «доказательство» для математика — это уже игрушки.) Будем искать бесконечную последовательность дружественных чисел следующего вида:

(4)

(предполагается, что числа q1, q2, р— простые). Почему именно такого вида — на этом мне не хотелось бы сейчас останавливаться. Выбираются и фиксируются три числа b1, b2, р, и при каждом n = 1,2,3, ... ищутся q1 и q2. Тот факт, что B1 и B2— дружественные числа, означает (согласно (3)), что

откуда

Используя (1) и (2), находим, что

Заметим, что при n → ∞ числа q1 и q2 также стремятся к бесконечности. Таким образом, переходя в последнем равенстве к пределу при n → ∞, получаем

(5)

Последнее соотношение связывает три числа b1, b2 и р, которые следует подставлять в исходную формулу (4). Отыскивая простейшие решения уравнения (5), удовлетворяющие условию задачи, мы после некоторых попыток довольно быстро придем к числам

b1 = 220, b2 = 4 и из (5) найдем для р значение 127. Тем самым мы получим пару, указанную в примере 1. При этом — на первый взгляд случайно — появилось число 220, само являющееся дружественным. Поскольку мы как математики неохотно верим в случайность, поищем причину. Тут мы и обнаружим указанный выше общий «рецепт», как по уже известным дружественным числам строить правила типа правила Сабита, дающие новые пары дружественных чисел.

В литературе встречается (по меньшей мере) 67 пар дружественных чисел требуемого вида. Для 22 из них число р = u + s + 1 действительно оказывается простым. Тем самым найдено 22 «сабитовых правила». Поясненные численными примерами с наименьшими возможными числами, они были опубликованы мной в 1972 г. в журнале «Mathematics of computation» вместе с призывом к специалистам по простым числам просчитать дальнейшие примеры на ЭВМ.

Здесь я хотел бы сказать несколько слов о том, как трудно решить, является ли заданное число q простым. Тривиальный способ — делить q на все числа, не превосходящие квадратного корня из q, — требует √q арифметических действий. Придумано много остроумных усовершенствований этого метода, но в большинстве из них, как обнаруживается при внимательном рассмотрении, требуются те же O(√q)1) арифметических операций. Недавно удалось снизить число операций до O(√q) благодаря тонкому методу Д. Шэнкса, по которому сперва определяется число классов мнимого квадратичного поля Q(√-q). — Если бы знаменитая гипотеза Римана о нулях дзета-функции (а точнее ее обобщение для L-функций Дирихле) оказалась справедливой, то можно было бы доказать, что для решения вопроса, является ли q простым числом, достаточно О ((ln q)3 ln ln ln q) операций. Андрэ Вейлю в 1948 г.

1) То есть, грубо говоря, с√q, где с — некоторая константа.—Прим. перев.

удалось доказать аналог гипотезы Римана для L-функций алгебраических кривых над конечными полями; основываясь на этом, Д. Бёрджесс и Г. Миллер показали, что достаточно О (√q) арифметических операций.

Однако ситуация полностью меняется, если известно разложение числа q + 1 на простые множители. А именно, используя критерий Люка — Лемера (предложенный Э. Люка и усовершенствованный в 1930 г. Д. Лемером (см. Annals of Mathematics)) можно, в большинстве случаев, уже с помощью O(lnq) арифметических операций установить, является ли q простым. То есть количество операций, необходимых для такой проверки, растет лишь пропорционально числу цифр числа q. Этот фантастический результат едва ли может быть улучшен. Впрочем, при оценке требуемого объема вычислений (измеряемого, скажем, в секундах машинного времени) следует принимать во внимание, что числа с таким большим количеством цифр г, как рассматриваемые здесь, — незаурядные объекты даже для современных ЭВМ. При их перемножении вычислительное устройство оказывается занятым невероятно долго — в течение времени, требующегося для O(z2) обыкновенных умножений (это, правда, при традиционном способе умножения; при применении нового, искусно построенного алгоритма быстрого умножения больших чисел, изобретенного А. Шёнхаге и Ф. Штрассеном, достаточно О(z lnz lnz lnz) обыкновенных умножений). Но даже если мы оценим действительный объем вычислений с использованием критерия Люка — Лемера, O((ln)3), то всё же это ошеломляюще быстрый способ выяснения простоты.

С одного взгляда на полученные по нашему рецепту сабитовы правила ясно, что они словно созданы для применения критерия Люка — Лемера. Хотя эта особенность присуща также правилу самого Сабита и его обобщению — правилу Эйлера, однако наши формулы имеют по сравнению с ними еще два важных достоинства: во-первых, одновременно должны быть простыми лишь два, а не три больших числа и, во-

вторых, нашим способом можно получить при желании много новых аналогичных правил, если данное правило недостаточно «производительно».

Мой призыв к вычислителям нашел отклик. Правда, их терпение подверглось суровому испытанию, так как вначале одно из больших чисел q1 и q2 всё время оказывалось составным. Второго октября 1972 г. Херман те Риле написал мне, что по формуле, приведенной в качестве примера 2, лишь при n = 19 снова получаются числа q1, q2, по меньшей мере псевдопростые (псевдопростым называется число q, для которого выполняется заключение малой теоремы Ферма, т. е. q делит aq-1 — 1 при некотором а > 1). Такие числа не обязательно являются простыми, однако это весьма вероятно. — Через четыре дня те Риле сообщил мне, что критерий Люка — Лемера дал положительный результат — оба числа простые. Таким образом и была обнаружена та пара 152-значных дружественных чисел, с которой я начал свой рассказ.

* * *

Вот и вся история, которую я хотел вам рассказать. Как из каждой старой истории, из нее следует извлечь мораль. Некоторым вполне хватает невинного удовольствия, доставляемого подборкой курьезов и анекдотов. Тех же, кто стремится к серьезным знаниям, я хотел бы познакомить с мнением Леонарда Эйлера, высказанным во введении к его работе «De numeris amicabilibus» («О дружественных числах»):

«Inter omnia problemata, quae in Mathesi tractari soient, nunc quidem a plerisque nulla magis sterilia atque ob omni usu abhorrentie existimantur, quam ea, quae in contemplatione naturae numerorum et divisorum investigatione versantur...»

«Из всех проблем, рассматриваемых в математике, нет таких, которые считались бы в настоящее время более бесплодными и бесполезными, чем проблемы, касающиеся природы чисел и их делителей. В этом отношении нынешние математики сильно отличаются от древних, придававших гораздо большее значение исследованиям такого рода... А именно, они не толь-

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

Я хотел бы к этим словам Эйлера добавить лишь несколько примеров, весьма убедительно подтверждающих его мнение. Так, еще и сегодня восхищает рекуррентная формула Эйлера для суммы делителей

(I)

которую более точно можно записать в виде

здесь суммирование ведется по всем целым значениям n, причем считается, что σ(z) = 0 при всех отрицательных z, а σ(0) = А. Эту зависимость Эйлер нашел эмпирически при проведении своих обширных вычислений, связанных с дружественными числами. А отыскивая доказательство, обнаружил знаменитое тождество Эйлера

(II)

из которого после логарифмирования и сравнения коэффициентов получается (I). Сумма в правой части (II) представляет собой так называемую тэта-функцию, и это было самым первым появлением тэта-функции на математической арене, а произведение слева — с точностью до множителя x1/24 дедекиндова эта-функция. Само тождество является частным случаем (при у = x3, z = x-1) формулы Якоби для тэта-

функций (1828 г.)

(III)

играющей важную роль в теории эллиптических функций. Наконец, эти формулы в 1972 г. привели Макдональда к открытию целой серии тождеств для эта-функции Дедекинда — по одному для каждой простой группы Ли G (знаменитая статья в журнале «Inventiones mathematicae»). Формулы Эйлера и Якоби входят в тождества Макдональда как простейший частный случай (G = SL2). У истоков же этой эволюции стоит, несомненно, Эйлер со своей формулой (i) для суммы делителей. Или Пифагор?

Библиографические замечания и дополнения

Самый исчерпывающий из всех когда-либо опубликованных документов, касающихся дружественных чисел, — это вышедшая в трех частях статья Ли и Мэдэчи [12]1). В приведенной там превосходной библиографии, содержащей 67 наименований, представлены оригинальные работы вплоть до 1971 г., так что я могу по существу ограничиться отдельными библиографическими дополнениями и замечаниями. Главное внимание Ли и Мэдэчи [12] уделяют доскональному протоколированию всех численных результатов с указанием получивших их математиков и использованных методов. К их перечню следует добавить лишь описанный выше новый метод [1] и его применение те Риле [18]. Недавно мои студенты Х. Хоффманн, Э. Небген и Р. Рекков подтвердили и существенно расширили результаты те Риле (Вупперталь, 1979 г.; см. [36], [37]).

Тот, кого заинтересовали античная и арабская главы этой истории, может совершить увлекательное путешествие к истокам с помощью четырехтомного труда М. Кантора «История математики» [4]; в нем содержится не только большое количество сведений о совершенных и дружественных числах, но и очерк культурной и исторической обстановки, а также дальнейших результатов. Указание об упоминании числа 220 в библии (Книга Бытия, XXXII, 14) имеется у Диксона [5], который в свою очередь ссылается на комментатора библии Абрахама Азулея; тот же нити-

1) Числа в квадратных скобках отсылают к списку литературы в конце статьи.

рует комментатора 9-го в., некого Рау Наксхона. — Ли и Мэдэчи [12] сообщают, что по мнению П. Таннери число 220, возможно, было «открыто» уже в древнем Египте.

О. Беккер высказал интересные соображения о формуле Эвклида для чётных совершенных чисел [23]; он считает ее изначальной «целью и венцом учения Эвклида о четных и нечетных» и объясняет, как можно было прийти к ее открытию, отталкиваясь от приемов счета на употреблявшихся в древней Греции абаках1). Кроме того, О. Беккер высказывает и пытается обосновать свое мнение, будто доказательство теоремы Эйлера о том, что все четные совершенные числа должны получаться по способу Эвклида, было известно уже в древности, — формулировал же Ямвлих эту теорему Эйлера. Анализируя текст трактата Ямвлиха, Ф. Хульч [26] делает даже вывод, что Ямвлих «в результате ли собственных вычислений, из прежних ли источников знал, что и 8191, и 131071 — простые числа» (эти числа равны соответственно 213 — 1 и 217 — 1), и что, следовательно, в античные времена знания о больших простых и совершенных числах находились на значительно более высоком уровне, чем это принято считать.

Доказательством того, что арабам было известно о совершенных и дружественных числах больше, нежели до сих пор предполагали, мы обязаны профессору Тунисского университета Мохаммеду Суисси, который недавно перевел и опубликовал [32] упоминавшееся ранее сочинение ибн аль-Банны о совершенных и дружественных числах. Кроме того, группа советских историков из Средней Азии [38] обнаружила в рукописях Кутбэддина Ширази (XIII в.) и знаменитого Джемшида аль-Каши (ум. в 1430 г.; в последние годы работал в Самаркандской обсерватории) примечательные рассуждения о дружественных числах. Согласно их данным, числа 17296 и 18416 были известны как в Марокко (аль-Банна), так и в Иране (Кутбэддин) за три с половиной столетия до Ферма. Аль-Банна нашел оба числа (см. фото 2), следуя общему правилу, формулировка которого так точно совпадает с формулировкой Сабита, что это, по-моему, доказывает заимствование ее у последнего (в противоположность мнению Суисси). Аль-Каши, напротив, дает несколько иную формулировку, однако допускает при этом ошибку, полагая без проверки число г простым (обозначения прежние). Поэтому он ошибочно считает 2024 и 2296 второй парой дружественных чисел. Я указываю здесь на эту ошибку, так как в [38] она не была замечена. Далее я хотел бы отметить, что более поздние исламские авторы не приводят никакого доказательства для излагаемого способа, в то время как Сабит написал свое теоретико-числовое сочинение, по образцу «Начал» Эвклида, совершенно строго и потратил на доказательства немало усилий.

1) Прибор типа русских счетов; см., например, Депман И. Я. История арифметики.—М.: Учпедгиз, 1959, или Выгодский М. Я. Арифметика и алгебра в древнем мире. — М.: Наука, 1967, — Прим. перев.

Книга Абу'ль-Касим Маслама ибн Ахмед аль-Маджрити (или аль-Мадшрити), открывшего любовное воздействие дружественных чисел, называется «Цель мудреца» и подробно описана Штайншнайдером [33].

Хотя сочинение Кантора охватывает как средние века, так и новое время до 1799 г., однако применительно к нашей теме существенно больший материал (да еще вплоть до 1919 г.) содержит книга Л. Диксона [5], начинающаяся 50-ю страницами скрупулёзной хроники событий, результатов и публикаций в области совершенных и дружественных чисел и вызванных ими исследований, посвященных суммам делителей. В отличие от Кантора Диксон ограничивается сухим перечнем дат и фактов.

Чтобы получить живое впечатление о работах Ферма и Декарта, рекомендуем полистать переписку Мерсенна [15]. В предисловии к своей «Всеобщей гармонии» Мерсенн пишет:

«Or, si je voulois parler des hommes de grande naissance ou qualité, qui se plaisent tellement en cette partie des mathématiques qu'on se sçauroit peut-être leur rien enseigner, je répéterois le nom de celui à qui le livre de l'orgue est dédie [E. Pascal] et ajouterois Monsieur Fermat, Conseiller au Parlement de Thoulouse, auquel je dois la remarque qu'il a faite des deux nombres 17296 et 18416, dont les parties aliquotes se referont mutuellement, comme tout celles des deux nombres 220 et 284... E, il sçait les règles infaillibles et l'analyse pour en trouver une infinité d'autres semblables.»1)

31-го марта 1638 г. Декарт пишет Мерсенну: «Leur autre question est ce problème: trouver une infinité de nombres, lesquels estant prix deux à deux, l'un est égal aux parties aliquotes de l'autre, et réciproquement l'autre est égal aux parties aliquotes de premier. A quoi je satisfait par cette regle:2) Si sumatur binarius, vel quilibet alius numerus ex solius binarii multiplicatione productus, modo sit talis ut si tollatur unitas ab ejus triplo, fiat numerus primus; et denique si tollatur unitas ab ejus quadrati octodecuplo,

1) «Однако если бы я захотел назвать людей знатного рода или высоких достоинств, которые до того увлеклись этой областью математики, что их, пожалуй, никто не мог бы здесь научить ничему новому, то я повторил бы имя того, кому эта книга торжественно посвящена [Э. Паскаль], и назвал бы еще г-на Ферма, члена Тулузского парламента, о коем я могу заметить, что он нашел два числа, 17296 и 18416, делители которых находятся друг к другу в таком же отношении, как и делители чисел 220 и 284 ... И он знает и умеет обосновать верные правила, как найти беконечное количество других таких пар.» (старо-франц.)

2) «Другим Вашим вопросом была задача: найти бесконечное количество чисел, сгруппированных в пары, в каждой из которых одно число равно сумме делителей другого, и наоборот, второе равно сумме делителей первого. Мой ответ — следующее правило:» (старо-франц.). Правило Декарт формулирует на латыни. — Прим. ред.

fiat numerus primus; ducaturque hic ultimus numerus primus per duplum numeri assumpti; fiat numerus cujus partes aliquotae dabunt alium numerum, qui vice versa partes aliquotas habebit aequales numéro praecedenti. Sic assumendo tres numeros 2, 8 et 64, habeo haec tria paria numerorum.

Таков декартов вариант правила Сабита. Вот русский перевод:

«Берется число 2 или число, получающееся повторным умножением числа 2 самого на себя и обладающее тем свойством, что при вычитании единицы из его трехкратного или шестикратного, а также из восемнадцатикратного его квадрата всякий раз остается простое. Тогда последнее число, умноженное на удвоенное взятое, даст число, сложением делителей которого получается число с суммой делителей, составляющей предыдущее число».

Эти сведения приведены в вышедшей в 1723 г. статье некоего Б. Водарха о «точном познании чисел», в котором также подробно рассмотрены совершенные и дружественные числа. Она была опубликована в самом, пожалуй, старом математическом журнале «Плоды искусства» Гамбургского математического общества, носившего тогда название «Товарищество любящих и занимающихся искусством вычислений» и являющегося самым старым из поныне существующих в мире математических обществ. Я упомянул здесь это сочинение не только в качестве примера исторических реликвий времен Эйлера, но прежде всего потому, что оно ускользнуло от внимания Диксона [5], Ли и Мэдэчи [12] и позволяет внести поправку в [12] (стр. 79, левая колонка, строки 29—31). Диксон вряд ли и мог найти статью Водарха — ведь том считался в Гамбургском математическом обществе утерянным! Так как любителям непросто будет достать этот единственный экземпляр, нашедшийся благодаря случайности, позволю себе процитировать еще несколько мест:

«Кем овладело причудливое желание искать совершенные числа, тому понадобится для этой работы знание простых. Упомянутых совершенных чисел было открыто до сих пор только 8 ...» «Не в меньшей мере потребуется знание простых для отыскания дружественных чисел. Такого рода чисел до сих пор было известно лишь три пары, а именно первая пара — 220 и 284, ...» «Построение таких чисел при помощи различных алгебраических методов относят к области высокого мастерства и искусства знаменитые мужи, а именно многократно упоминавшийся выше профессор Престет во втором томе своих «Элементов математики»; равным образом профессор фон Шотен в своих «Математических открытиях», а также вышеупомянутый Хеллингуэрфф в своих «Висконсинских открытиях». Великий Декарт дает следующее общее правило вычисления таких чисел:»

Далее следует цитированная ранее версия правила Сабита, а затем некоторые примеры вычислений.

«...и вплоть до 46-го значения получал я всё время составные числа и тем самым не нашел подходящего числа, которое могло бы дать четвертую пару дружественных чисел. При 46-м обращении к правилу после указанных умножений получаются числа 211106232532991 и 422212465065983, но мне уже не хочется ут-

руждать себя проверкой того, просты ли они. Ибо если окажется, что оба они простые, то надо будет еще проверить на простоту число 89131682828547379792736944127, каковую работу мне хотелось бы оставить любителям...»

«Поскольку всё же особой пользы от этих вещей нет, я счел возможным остановиться на этом; и так уж я потрудился достаточно, а с напрасной работой хотел бы повременить.»

Согласно этому высказыванию, Водарх проверил формулу Сабита вплоть до 45-го значения л, т. е. значительно дальше, чем это сделали позднее Эйлер (до 8), Лежандр (до 15; 1830 г.) и Ле Лассёр (до 34; 1908 г.), хотя и не так далеко, как Жерардэн (до 200; 1908 г.) и Ризель (до 1000; 1969 г.); φ. [12]. Студенты И. Буль и 3. Мертенс из моего кружка по элементарной теории чисел выяснили, что формула Сабита не дает других пар дружественных чисел, кроме трех известных, даже вплоть до n = 20000 (см. [36], [37]). При этом, кроме числа 3⋅212676 — 1 —монстра из 3817 цифр, оказались простыми еще ровно 30 меньших чисел рассматриваемого в способе Сабита вида 3⋅2n—1.

Работы Эйлера по интересующей нас теме настолько обширны, многосторонни и остроумны, что и теперь их стоит читать в оригинале [7]. Поскольку удачный обзор его важнейших идей и методов имеется как у Диксона [5], так и у Ли и Мэдэчи [12], я считаю возможным не останавливаться здесь на этом подробнее. Что касается моего упоминания в конце экскурсии о рекуррентной формуле Эйлера (I) для суммы делителей, то оно основано непосредственно на подробных оригинальных работах Эйлера [7]. Впрочем, у Скриба [19] (стр. 127—129) можно найти и сводку результатов Эйлера, составленную на основе переписки Эйлера с Гольдбахом. Где-то между 21 марта и 1 апреля 1747 г. Эйлер пишет Гольдбаху: «Недавно я обнаружил весьма удивительную закономерность для чисел, представляющих собой суммы делителей натуральных чисел. Эта закономерность кажется мне тем более странной, что она оказалась тесно связанной с простыми числами. Поэтому прошу Вашу светлость удостоить эту догадку некоторым вниманием.» ... «Причину этой закономерности понять тем труднее, что неясно, как числа 1, 2, 5, 7, 12, 15 и т. д. связаны с делителями. И я не могу похвастаться, что имею ее строгое доказательство. Но если бы я даже не имел никакого обоснования подмеченной закономерности, и то можно было бы не сомневаться в ее справедливости, ибо она выполняется более чем до 300. Между тем я могу вывести эту теорему из следующего утверждения.» — Далее идет тождество (II) для степенного ряда (в то время еще не доказанное), на которое Эйлер натолкнулся в связи с разбиением чисел1) и которое он смог доказать лишь год спустя. О тождествах Эйлера, Лежандра,

1) Разбиением натурального числа называется представление его в виде суммы n = n1 + n2 + ... + ns, где n1 ⩾ 0, n2 ⩾ 0,... ..., ns ⩾ 0. Элементарное доказательство формулы (II) можно найти, например, в книге: Виленкин Н. Я. Комбинаторика. — М.; Наука, 1969, с. 116—120. — Прим. перев.

Гаусса и Якоби (в частности, о тождествах из трактата «Fundamenta nova» последнего) можно почитать также в [19]; по поводу новейших обобщений Макдональда и Каца, полученных с привлечением теории представлений алгебр Ли, отсылаю читателя к оригинальной работе Макдональда [13], а также к экскурсии Енса Карстена Янцена в область теории представлений и комбинаторики и указанной там литературе.

Оживленный и наиболее богатый результатами период «охоты на призрака» — поисков нечётных совершенных чисел — приходится на наше столетие и не охвачен хроникой Диксона [5]; однако имеется подробный обзор П. Мак-Карти [14], в котором представлены результаты, полученные за период с 1919 по 1957 г. По поводу более поздних исследований сошлюсь, например, на оригинальные работы Хейджиса [8] и Роббинса [17] и указанную там литературу. Ссылки на другие интересные работы по этому вопросу можно найти в обзорной лекции Кампса [9], прочитанной в 1975 г., которая никак не опирается на обзор Мак-Карти и вообще носит совершенно иной характер, так как обращена исключительно к нематематикам. В этой прекрасной вступительной лекции, прочитанной в Университете города Констанца, говорится также о чётных совершенных числах и о связанной с ними погоне за рекордными по величине простыми числами. Много новых фактов об этой охоте за рекордами, начиная с Люка (1876 г.), приведено в «рейде» Дона Цагира по первым 50 миллионам простых чисел. С хроникой предшествующего периода можно ознакомиться по Диксону [5]. О последнем1) рекорде калифорнийских школьников Никкела и Нолла, 6533-значном простом числе 221701 — 1, газета «Süddeutsche Zeitung» известила своих читателей 17 ноября 1978 г. под заголовком: «Наибольшее простое число поймано решетом Эратосфена2)» (хорошая шутка, так как решето Эратосфена годится для отыскания таких больших простых чисел примерно так же, как топор для расщепления атомного ядра). Факсимиле американского почтового штампа «211213—1 is pime» («211213—1 — простое число») вместе с выданной ЭВМ распечаткой этого 3376-значного числа можно найти среди других курьезов на страницах раздела занимательной математики журнала «Scientific American»3), которые Мартин Гарднер посвятил «бесполезной красоте» совершенных и дружественных чисел [24].

1) По самым последним сведениям простыми являются также числа 223209—1 (Нолл) и 244497 — 1 [31]. [В январе 1983 г. появилось сообщение, что простым является и 25962-значное число 286243 — 1, найденное Д. Словинским; см., например, журнал «Квант», 1983, № 7, с. 16. — Перев.]

2) Решето Эратосфена — один из способов нахождения простых чисел, практически пригодный для сравнительно небольших чисел. См., например, Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — Прим. перев.

3) Переводящегося с 1983 г. издательством «Мир» под названием «В мире науки». — Прим. ред.

Тот, кто интересуется проверкой больших чисел на простоту и, может быть, еще не знаком с критерием Люка для простых вида 2p — 1 (основанном на варианте малой теоремы Ферма для чисел из полей Q (√5 ) или Q (√3). легко может получить представление об этом вопросе по классическому учебнику Харди и Райта по теории чисел ([25], § 6.14 и 15.5) или по своеобразной книжечке Д. Шэнкса «Решенные и нерешенные проблемы теории чисел» [30], лейтмотив которой — совершенные числа. Те, кто хотел бы точно знать, как самым рациональным образом практически приступить к делу в случае появления (при применении способа Сабита) больших чисел q1, q2, могут ознакомиться по работе [37] с упрощенным вариантом критерия Люка, который очень подходит для этой цели; попутно там дано обстоятельное общее введение в теорию критериев простоты типа Люка. Свой _новый критерий простоты, требующий для любых чисел О(√q) вычислительных операций (кружным путем, через вычисление числа классов модулей), Д. Шэнкс предложил в [30]; между прочим, этот способ имеет по сравнению со многими другими то преимущество, что позволяет при необходимости явно определить множители числа q. О том, как теоретически оценить количество арифметических операций, с помощью которых некий критерий приводит к цели (в предположении, что обобщенная гипотеза Римана верна), можно прочитать у М. Миньотта [27], а как получается оценка O(√q) — у Г. Миллера [28]. Всё это — лишь отдельные примеры из огромного потока новых оригинальных работ, посвященных разложению на множители и проверке больших чисел на простоту, систематический обзор которых потребовал бы отдельной лекции1).

Пожалуй, здесь не будет лишним отметить ошибочность довольно распространенного мнения, будто данная тема — занятие, подходящее лишь для тупых вычислителей, а для настоящих математиков слишком скучное. Я не могу устоять перед искушением процитировать по этому поводу несколько фраз из «Disquisitiones Arithmeticae» («Арифметические исследования») К. Гаусса [40] : «Что задача различать простые и составные числа, а последние разлагать на простые множители, принадлежит к важнейшим и полезнейшим задачам во всей арифметике и что она занимала ум как древних, так и современных математиков, настолько известно, что было бы излишним тратить на это много слов. Тем не менее следует признать, что все до сих пор предложенные методы или ограничиваются частными случаями, или настолько громоздки и трудоемки, что ... в основном едва ли могут быть применимы ... к большим числам ... ; достоинство науки требует, чтобы прилежно усовершенствовались все вспомогательные средства, могущие помочь в решении этой знаменитой проблемы.»

1) Недавно Й. Вольфарт как раз прочитал такую вступительную лекцию. Еще более подробный замечательный современный обзор этой области — со 100 литературными ссылками — дал Х. Уильямс [39].

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

Обзора теоретических исследований по дружественным числам, который сводил бы воедино результаты прежде всего последних десятилетий и, стало быть, служил своего рода продолжением обзора Мак-Карти [14], пока что нет. У Ли и Мэдэчи [12] во главу угла поставлены численные результаты, и хотя у них и перечислены теоретические работы, опубликованные до 1971 г., однако на их обсуждении они почти не останавливаются. Приведенные в моей лекции в качестве примеров теоретические результаты можно найти в [2], [6] и [11]. Читателю, интересующемуся этим направлением, следует также ознакомиться с [3], где улучшены результаты Артюхова [35] и, совсем грубо говоря, показано, что, если не считать некоторого конечного числа исключений, все дружественные числа с заданным количеством различных простых делителей должны удовлетворять неким «сильно обобщенным правилам Сабита». Рекомендуется также просмотреть работы Канольда и Хейджиса, как включенные в приводимый ниже список литературы, так и другие, указанные в [12]. Результат Эрдёша [6] об асимптотическом распределении дружественных чисел был недавно улучшен К. Померансом [41], доказавшим, что сумма величин, обратных дружественным числам, конечна.

В заключение я хотел бы еще отметить заслуживающую всяческого внимания лекцию Канольда [10] о совершенных и дружественных числах, которая, как и лекция Кампса, обращена исключительно к нематематикам, хотя преследует несколько иные цели, чем Кампса и моя. В полную противоположность Ли и Мэдэчи [12], Канольд почти полностью игнорирует конструктивный и вычислительный аспекты темы. Однако, по-моему, таким образом можно рассказывать лишь историю совершенных, но не дружественных чисел, так как эта вторая в значительной степени связана с конкретными примерами (игра с числами, построение чисел, «охота за числами»). Таким взглядом я и руководствовался при составлении плана настоящей экскурсии, и это позволяет мне надеяться, что моя вступительная лекция как раз заполнит пробел между докладом Канольда и хроникой Ли и Мэдэчи. Подбор материала, стиль изложения, общий замысел и расстановку акцентов следует рассматривать именно на фоне уже существующей обзорной литературы, которую я в этих примечаниях и постарался представить возможно полнее.

Литература

[1] W. Borho, On Thabit ibn Kurrah's formula for amicable numbers, Math, of Comp. 26 (1972), 571—578.

[2] W. Borho, Eine Schranke für befreundete Zahlen mit gegebener Teileranzahl, Math. Nachrichten 63 (1974), 297—301.

[3] W. Borho, Befreundete Zahlen mit gegebener Primteileranzahl, Math. Ann. 209 (1974), 183—193.

[4] M. Cantor, Vorlesungen über Geschichte der Mathematik, 4 Bände, Leipzig, 1900—1908.

[5] L. E. Dickson, History of the theory of numbers, Band 1, Washington, 1919.

[6] P. Erdös, On amicable numbers, Publ. Math. Debrecen 4 (1955), 108—111.

[7] L. Euler, Opera Omnia, Teubner, Leipzig und Berlin, 1915; Commentat. 100 (De numeris amicabilibus), 152, 175, 243 (Observatio de summis divisorum), 244.

[8] P. Hagis, A lower bound for the set of odd perfect numbers, Math. Comp. 27 (1973), 951—953.

9] К. Н. Kamps, Vollkommene Zahlen, Konstanzer Universitätsreden 79, Konstanz, 1975.

[10] H.-J. Kanold, Vollkommene und befreundete Zahlen, Natw. Gießener Hochschulgesellschaft 24 (1955), 122—130.

[11] H.-J. Kanold, Über befreundete Zahlen. I—II, Math. Nachr. 9 (1953), 243—248; 10 (1953), 99—111.

[12] E. J. Lee, J. S. Madachy, The history and discovery of amicable numbers. I—III, J. of Recreat. Math. 5 (1972), 77—93, 153—174, 231—249.

[13] I. G. Macdonald, Affine root systems and Dedekind's ν-function, Invent Math. 15 (1972), 91—143.

[14] P. J. McCarthy, Odd perfect numbers, Scripta Mathematica 23 (1957), 43—47.

[15] M. Mersenne, Correspondance du P. Marin Mersenne, Ed. du CNRS, Paris, 1960; в частности, т. 6, письмо № 562 Ферма Мерсенну от 24 июня 1636 г. и т. 7, письмо № 661 Декарта Мерсенну от 31 марта 1638 г.

[16] P. Poulet, La Chasse aux Nombres, Brüssel, Stevens, 1929.

[17] N. Robbins, Lower bounds for the largest prime factor of an odd perfect number which is divisible by a Fermat prime, J. reine angew. Math. 278/279 (1975), 14—21.

[18] H. J. J. te Riele, Four large amicable pairs, Math. Comp. 28 (1974), 309—312.

[19] Ch. J. Scriba, Zur Entwiklung der additiven Zahlentheorie von Fermat bis Jacobi, Jber. Deutsch. Math.-Verein, 72 (1970), 122—142.

[20] В. Tuckerman, The 24th Mersenne prime, Proc. Nat. Acad. Sci. USA. 68 (1971), 2319—2320.

[21] B. A. Wodarch, («Der Wohlmeinende») Anleitung zu einer genauen Zahlen-Erkaentniß, Der hamburgischen Kunst-Rechnungs lieb- und uebenden Societaet Kunst-Fruechte, Samm-

lung 1 (1723), 46—60. (В собрании Гамбургской государственной библиотеки.)

22] I. Wolfari, Primzahltests und Primfaktorzerlegung, Frankfurt. 1980.

[23] О. Becker, Die Lehre vom Geraden und Ungeraden in Neunten Buch der Euklidischen Elemente, Quellen u. Studien Math. 3 (1936), 533—553.

[24] M. Gardner, A short treatise on the useless elegance of perfect numbers and amicable pairs, Scientific American 218 (1968), 121—126. [Имеется перевод: Краткий трактат о бесполезной красоте совершенных чисел. — В кн.: Гарднер М. — Математические новеллы. — М., Мир, 1974.]

[25] G. H. Hardy, Е. М. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford, 1979.

[26] F. Hultsch, Erläuterung zu dem Berichte des Iamblichos über die vollkommenen Zahlen, Gesell, d. Wiss. Gottingen, phil.-hist. Kl., 1895, 246—255.

[27] M. Mignotte, Tests de primauté, preprint. Seminaire d'Informatique, Centre de calcul de l'Esplanade, Université, 7 rue René Descartes, 67, Strasbourg.

[28] G. Miller, Riemann's Hypothesis and Tests for primality. Proc. 7th annual ACM Symp. on the theory of computing, 1975, 234—239.

[29] D. Shanks, Solved and unsolved problems in number theory, Spartan books, Washington, D. C, 1962.

[30] D. Shanks, Class number, a thery of factorization, and genera, Proc. of Symp. in Pure Math. 20 (1969), 415—440.

[31] D. Slowinski, Searching for the 27th Mersenne Prime, J. Recréât. Math. 11 (1979), 258—261.

[32] M. Souissi, Un texte manuscrit d'Ibn-Al Bannâ, Al-Marrakusî (1256—1321) sur les nombres parfaits, abondants, deficients et amiables; published by Hamdard National Foundation, Pakistan, Karachi, 1975.

[33] M. Steinschneider, Zur Pseudopigraphischen Literatur des Mittelalters, Berlin, 1862 (перепечатка с издания: Philo Press, Amsterdam, 1965).

[34] A. Schönhage, V. Strassen, Computing 7, 1971, 281—292.

[35] М. М. Артюхов, К проблемам теории дружественных чисел, Acta Arithmetica 27 (1974), 281—291.

[36] W. Borho, Some new large primes and amicable numbers, Math. Comp. 36 (1981), 303—304.

[37] W. Borho, Große Primzahlen und befreundete Zahlen: Uber den Lucas-Test und Thabit-Regeln, Mitteilungen Math. Ges. Hamburg (в печати).

[38] О. В. Добровольский, А. Каххоров, И. Ходжиев, Совершенные и дружественные числа на средневековом Востоке. — Изв. АН Таджикск. ССР, Отдел, физ.-мат. и геол.-хим. наук, 1976, № 3 (61), с. 24—28.

[39] Н. С. Williams, Primalitv testing on a computer, Ars combinatoria 5 (1978), 127—185.

[40] C. F. Gauss, Disquisitiones Arithmeticae. Издано на нем. языке Х. Мазером (H. Maser) в 1889 г.; переиздание: Chel-

sea, New York, 1965, Artikel 329. [Имеется перевод в кн.: Гаусс К. Ф. Труды по теории чисел. — М.: Изд-во АН СССР, 1959.]

[41] С. Pomerance, On the distribution of amicable numbers. II, J. reine angew. Math, (в печати; первая часть опубликована в том же журнале, 293/294 (1977), 217—222).

Дон Цагир

ПЕРВЫЕ 50 МИЛЛИОНОВ ПРОСТЫХ ЧИСЕЛ

Мне хотелось бы поговорить с вами об одной проблеме, которая, хотя сам я над ней и не работал, всегда меня чрезвычайно привлекала и которая очаровывала математиков, пожалуй, с доисторических времен и до наших дней, — а именно о проблеме распределения простых чисел.

Вам, конечно, известно, что простым числом называется отличное от 1 натуральное число, не делящееся ни на какие иные натуральные числа, кроме 1; во всяком случае, именно такое определение дают специалисты по теории чисел. Правда, другие математики иногда используют и иные определения. Так, для специалиста по теории функций простое число — это целочисленный нуль аналитической функции

Для алгебраиста — это

«характеристика конечного поля»1),

или

«точка из spec Z»2),

или

«неархимедово нормирование»3).

1) См., например, Курош А. Г. Курс высшей алгебры. — М.: Наука, 1968. —Прим. перев.

2) См., например, Ленг С. Алгебра. — М.: Мир, 1968. — Прим. перев.

3) См., например, Коблиц Н. р-адические числа, р-адический анализ и дзета-функции. — М.: Мир, 1982. — Прим. перев.

Для специалиста по комбинаторике простые числа определяются рекуррентной формулой [1]1)

где [х] — целая часть числа x2). И, наконец, логики определяют в последнее время простые числа как положительные значения многочлена [2]

Но я думаю, вы вполне удовлетворены первым из приведенных мной определений.

Имеются два главных факта о распределении простых чисел, о которых я надеюсь рассказать вам так, чтобы они навек запечатлелись в вашей памяти. Первый: простые числа, при своем таком простом определении и при своей роли кирпичиков, из которых строятся все натуральные числа3), являются

1) Числа в квадратных скобках отсылают к примечаниям в конце экскурсии.

2) То есть наибольшее целое число, не превосходящее х. — Прим. перев.

3) Всякое натуральное число, отличное от 1, можно представить (и притом единственным образом) в виде произведения простых чисел. Доказательство см., например, в книге: Калужнин А. А. Основная теорема арифметики. — М.: Наука, 1969. — Прим. перев.

самыми капризными и упрямыми из всех объектов, вообще изучаемых математиками. Они растут среди натуральных чисел как сорная трава, не подчиняясь, кажется, ничему, кроме случая, и никто не может предсказать, где взойдет еще одно простое, а, увидев число, — определить, простое оно или нет. Другой факт озадачивает еще больше, так как он состоит в прямо противоположном утверждении, а именно: простые числа демонстрируют удивительную регулярность, они подчиняются законам, и притом с почти педантичной точностью.

Чтобы пояснить первое утверждение, я покажу вам список простых и составных чисел, не превосходящих 100 (табл. 3), причем, за исключением числа 2, приведены лишь нечетные числа, а затем список простых из ста натуральных чисел, предшествующих и следующих за 10 000 000 (табл. 4). Полагаю, вы согласитесь, что нет явно видимой причины, по которой одно число является простым, а другое — нет. Напротив, при взгляде на эти таблицы возникает ощущение, будто стоишь перед непостижимой тайной творения. Что и математики до сих пор еще не раскрыли эту тайну, пожалуй, наиболее убедительно подтверждает то усердие, с которым они и

Таблица 3. Простые и (нечетные) составные числа от 1 до 100.

простые

составные

2

43

9

63

3

47

15

65

5

53

21

69

7

59

25

75

11

61

27

77

13

67

33

81

17

71

35

85

19

73

39

87

23

79

45

91

29

83

49

93

31

89

51

95

37

97

55

99

41

57

Таблица 4. Простые числа в интервалах длины 1000 слева и справа от 10 миллионов.

между 9 999 900 и 10 000 000

между 10 000 000 и 10 000 100

9 999 901

10 000 019

9 999 907

10 000 079

9 999 929

9 999 931

9 999 937

9 999 943

9 999 971

9 999 973

9 999 991

поныне ищут все большие простые. Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Например в 1876 г. Люка доказал, что число 2127—1 — простое, и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если взглянуть на него:

Только в 1951 г. — после возникновения электронных вычислительных устройств — нашли большее простое число. Сведения о сменявших друг друга числах-рекордсменах вы найдете в табл. 5 [3]. В настоящее время рекордсменом является 6002-значное число 219937 — 1 (я бы не хотел его здесь выписывать); счастливчик, оно можег гордиться своей славой1). Кто сомневается в сказанном, может справиться в книге мировых рекордов Гиннесса.

Однако гораздо интереснее вопрос о законах, которым подчиняются простые числа. Я привел вам

1) С тех пор этот рекорд был неоднократно побит; см. добавление 2 в конце экскурсии. — Прим. перев.

Таблица 5. Наибольшее известное простое число.

ранее в табл. 3 список простых чисел между 1 и 100. На рис. 1 та же информация представлена графически. Функция π(х), о которой теперь пойдет речь, выражает количество простых чисел, меньших или равных х; следовательно, в нуле она имеет значение 0 и скачком увеличивается на 1 в точках х = 2, 3, 5 и т. д., т. е. когда х равно простому числу. Уже из этого графика видно, что растет π(х), несмотря на малые локальные колебания, в общем, довольно регулярно. Если же увеличить область изменения x до 50 000, то регулярность эта становится настолько отчетливой, что дух захватывает (рис. 2). По-моему, плавность, с которой поднимается эта кривая, следует отнести к числу удивительнейших фактов математики.

Но где закономерность, там и ученые, которые пытаются ее разгадать. И данный случай не стал исключением. Нетрудно найти эмпирическую форму-

Рис. 1.

Рис. 2.

лу, хорошо описывающую рост количества простых чисел. От 1 до 100 имеется 25 простых чисел, т. е. четверть всех чисел; до 1000 их 168, т. е. около одной шестой; до 10 000 их 1229, т. е. примерно одна восьмая. Продолжая вычисления до 100 000, 1000 000 и т. д. и определяя каждый раз отношение количества простых к количеству всех натуральных чисел, получим данные, приведенные в табл. 6. (Так скромно выписанные в ней значения π(х) потребовали тысяч часов трудоемких вычислений.) Видно, что отношение x к π(х) при переходе от данной степени десяти к последующей все время увеличивается примерно на 2,3. Математики сразу узнают в числе 2,3 логарифм 10 (разумеется, по основанию е). В результате возникает предположение, что

причем знак ~ означает, что отношение соединенных им выражений с ростом х стремится к 1. Это асимптотическое равенство, впервые доказанное в 1896 г., называется в настоящее время законом распределения простых чисел. Гаусс, величайший из математиков, открыл этот закон в пятнадцатилетнем возрасте, изучая таблицы простых чисел, содержавшиеся в подаренной ему за год до того таблице логарифмов. В течение всей своей жизни Гаусс живо интересовал-

Таблица 6.

x

π(x)

х/π(х)

10

4

2,5

100

25

4,0

1 000

168

6,0

10 000

1 229

8,1

100 000

9 592

10,4

1 000 000

78 498

12,7

10 000 000

664 579

15,0

100 000 000

5 761 455

17,4

1 000 000 000

50 847 534

19,7

10 000 000 000

455 052 512

22,0

ся распределением простых чисел и проводил обширные вычисления для выяснения этого вопроса. В своем письме к Энке [4] Гаусс описывает, как он «очень часто употреблял свободные четверть часа, чтобы то там, то здесь просчитать хилиаду» (т. е. интервал в 1000 чисел), и так до тех пор, пока он не нашел, наконец, все простые, меньшие трех миллионов (!), и не сравнил полученные результаты с предполагаемой формулой их распределения.

Закон распределения простых чисел утверждает, что функция π(х) асимптотически (т. е. с относительной погрешностью1) 0%) равна х/lnх. Однако если мы сравним графики функций х/lnx и π(х), то увидим, что, хотя функция х/lnх качественно и отражает поведение π(x), но всё же согласуется с ней не с такой точностью, которая позволила бы объяснить плавность графика π(х) (рис. 3). Итак, следует поставить вопрос о лучшем приближении. Посмотрев снова на таблицу отношений х/π(х), мы увидим, что это отношение почти точно равно lnx—1. Проведя более тщательные и полные вычисления, Лежандр [5] в 1808 г. обнаружил, что особенно хорошее при-

Рис. 3.

1) Относительной погрешностью называется отношение модуля (абсолютной величины) разности приближенного значения и точного значения к модулю последнего. — Прим. перев.

ближение получается, если вычесть из lnx не 1, а 1,08366, т. е.

Другое очень хорошее приближение π(х), впервые указанное Гауссом, можно получить, исходя из того эмпирически установленного факта, что плотность простых вблизи очень большого числа х почти точно равна 1/lnх. Поэтому количество простых чисел, не превосходящих х, приблизительно выражается логарифмической суммой

или, что примерно то же самое [6], интегральным логарифмом:

Сравнивая графики Li(x) и π(х), приведенные на рис. 4, мы видим, что в рассматриваемом диапазоне в пределах точности рисунка они просто совпадают. Картинку для приближения Лежандра не стоит даже показывать, так как в указанном диапазоне значений x оно еще лучше.

Рис. 4.

Существует еще одно приближение функции π(х), о котором я хотел бы упомянуть. Исследования Римана по простым числам наводят на мысль, что вероятность того, что большое число х является простым, будет с большей точностью задаваться функцией 1/lnx, если учитывать не только сами простые, но и их степени, причем квадрат простого числа считать за половину простого, третью степень — за треть и т. д. Это приводит к следующему приближенному равенству:

или, если «обратить» эту зависимость

Функцию, стоящую в правой части последнего равенства, обозначим (в честь Римана) через R(x). Как видно из табл. 7, она представляет собой удивительно хорошее приближение к π(х). Читателю, немного знакомому с теорией функций, могу сказать, что R (х) — целая функция от lnx, задаваемая быстро сходящимся степенным рядом

Таблица 7.

x

π(x)

R(x)

100 000 000

5 761 455

5 761 552

200 000 000

11 078 937

11 079 090

300 000 000

16 252 325

16 252 355

400 000 000

21 336 326

21 336 185

500 000 000

26 355 867

26 355 517

600 000 000

31 324703

31 324 622

700 000 000

36 252 931

36 252 719

800 000 000

41 146 179

41 146 248

900 000 000

46 009 215

46 009 949

1 000 000 000

50 847 534

50 847455

где ζ(n + 1) — дзета-функция Римана [8]1).

Впрочем, надо подчеркнуть, что приближения Гаусса и Лежандра для π(x) были получены чисто эмпирически и что даже Риман, который пришел к своей функции R(x) с помощью теоретических рассуждений, не доказал асимптотического закона распределения простых чисел. Это было сделано (на основе исследований Римана) лишь в 1896 г. Адамаром и (независимо) Валле Пуссеном.

Я хотел бы еще привести несколько численных примеров, показывающих возможность предсказания фактов о простых числах. Как уже было отмечено, вероятность того, что число порядка х является простым, приблизительно равна 1/lnx; это означает, что количество простых в интервале длины а поблизости от x должно быть примерно равно а/lnх, во всяком случае если длина интервала достаточно велика, чтобы имело смысл заниматься статистикой, но достаточно мала по сравнению с величиной х. Например, в интервале между ста миллионами и ста миллионами плюс 150 000, следует ожидать появления около 8142 простых, так как

Соответственно вероятность того, что два заданных числа вблизи х оба окажутся простыми, приблизительно равна 1/(lnх)2. Поэтому ожидаемое количество простых чисел-близнецов (т. е. пар простых, отличающихся ровно на 2, вроде 11, 13 или 59, 61) в интервале от х до х + а приблизительно равно а/(lnx)2. На самом деле ожидаемая величина немного больше, поскольку если уже известно, что число n является простым, то это несколько изменяет шансы, что и n + 2 будет простым; например, n + 2 в этом случае заведомо нечетно. Несложные эвристические рассуждения [9] показывают, что ожидаемое количество простых чисел-близнецов в интервале

1) С определением и свойствами ζ-функции можно познакомиться, например, по книге: Титчмарш Е. К. Теория дзета-функции Римана. — М.: ИЛ, 1953. — Прим. перев.

Таблица 8. Простые и простые-близнецы в 8 интервалах длины 150 000.

[х, х+а] равно Са/(lnx)2, где С — постоянная, приблизительно равная 1,3 (точнее С = 1,3203236316...). Так, между числами 100 000 000 и 100 150 000 должно быть примерно 1,32 ... X 150000/(18,427 ...)2» «584 простых чисел-близнецов. В табл. 8 я привожу полученные Джоунзом, Лэлом и Бландоном [10] данные о действительном количестве простых чисел и простых чисел-близнецов в этом и в некоторых других интервалах той же длины около больших степеней десяти. Видно, что реальные значения очень хорошо согласуются с ожидаемым результатом. Это особенно удивительно для простых-близнецов, так как пока не удается доказать даже тот факт, что их бесконечно много, не говоря уже об асимптотическом законе их распределения.

В качестве последнего примера на тему о предсказуемости свойств простых чисел упомяну еще про-

интервал

число простых

число простых-близнецов

ожидаемое

фактическое

ожидаемое

фактическое

100 000 000—100 150 000

8142

8154

584

601

1 000 000 000—1 000 150 000

7238

7242

461

466

10 000 000 000—10 000 150 000

6514

6511

374

389

100 000 000 000—100 000 150 000

5922

5974

309

276

1 000 000 000 000—1 000 000 150 000

5429

5433

259

276

10 000 000 000 000—10 000 000 150 000

5011

5065

211

208

100 000 000 000 000—100 000 000 150 000

4653

4643

191

186

1 000 000 000 000 000—1 000 000 000 150 000

4343

4251

166

161

блему о «провалах» между ними. Рассматривая таблицу простых чисел, можно заметить, что иногда встречаются особенно большие интервалы (например, между 113 и 127), совсем не содержащие простых. Пусть g(x)— длина наибольшего из интервалов между 1 и x, не содержащих простых чисел1). Например, для х = 200 самым длинным из них является только что упомянутый интервал от 113 до 127, так что g(200) = 14. Величина g(x) растет, разумеется, очень неравномерно, однако некоторые эвристические соображения [11] приводят к асимптотической формуле

Насколько всё-таки хорошо согласуется с ожидаемым поведением даже эта чрезвычайно сильно скачущая функция g(x), видно из рис. 5.

До сих пор я главное внимание уделял обоснованию утверждения о господствующем среди простых чисел порядке, нежели обоснованию утверждения об их своеволии. Кроме того, я еще не показал, как

Рис. 5.

1) Обозначение происходит от английского gap — пропуск, пробел, разрыв. — Прим. перев.

Рис. 6. Графики приближений Гаусса (1), Лежандра (2) и Римана (3); значения х отложены в миллионах.

было обещано в названии лекции, первые 50 миллионов простых, а привел данные лишь о нескольких тысячах простых. Так вот, на рис. 6 графически представлена функция π(х) в сравнении с приближениями Лежандра, Гаусса и Римана при изменении x до 10 миллионов [12]; так как графики этих четырех функций почти совпадают между собой (как мы это уже видели на рис. 4), то на рис. 6 приведены графики соответствующих разностей.

Думаю, уже одна эта картинка ясно показывает, что ожидает того, кто решается изучать простые числа.

Как видно из рисунка, приближение Лежандра x/(lnx — 1,08366) при небольших х (примерно до 1 миллиона) значительно точнее приближения Гаусса Li(x), однако начиная с 5 миллионов точнее становится Li(x) и можно показать, что с дальнейшим ростом X это становится всё вернее.

До 10 миллионов имеется примерно 600 000 простых чисел. Чтобы представить все обещанные 50 миллионов простых, следует дойти до 1 миллиарда. График разности R(x) — π(х) в этой области показан на рис. 7 [13]. Колебания функции R(x) — π(х) становятся с ростом х всё более сильными, однако не превосходят нескольких сотен даже при таких, почти невообразимо больших х.

Здесь можно упомянуть еще один факт о функции π(х). На рис. 6 приближение Гаусса Li(x) всю-

Рис. 7. График разности R(x) — π(х) на интервале 0 ⩽ х ⩽ 1 000 000 000.

Рис. 8. Значения х отложены в миллионах.

ду больше π(х), и это остается справедливым и до 1 миллиарда, как явствует из рис. 8 (на котором данные отложены в логарифмических шкалах1)). Последний график, несомненно, создает впечатление, что разность Li (x) — π(x) с ростом х стремится к бес-

конечности, т. е. что интегральный логарифм Li(x) принципиально переоценивает количество простых, не превосходящих х (и так как R(x) всегда меньше Li(x), то это соответствовало бы утверждению, что

1) То есть по осям отложены (в выбранном масштабе) не сами числа, а их логарифмы. — Прим. перев.

R(x) дает лучшее приближение, чем Li(x)). Однако дело обстоит иначе. Можно доказать, что существуют точки, в которых π(х) изменяется настолько резко, что становится больше Li(x). Такие числа до сих пор не найдены и, может быть, никогда и не будут найдены, но Литтлвуд доказал, что они существуют, а Скьюз [14] установил даже, что одно из них не превосходит

(По поводу этого числа Харди заметил, что оно, пожалуй, наибольшее из всех, когда-либо служивших в математике какой-нибудь определенной цели.) Во всяком случае, это убедительно показывает, как неразумно делать выводы о свойствах простых, основываясь только на численных данных.

В последней части моего сообщения я хочу рассказать о некоторых теоретических результатах, касающихся π(х), чтобы у вас не сложилось впечатление, будто исследования по простым числам следует отнести исключительно к области экспериментальной математики. Непосвященному может показаться, что свойство числа быть простым слишком случайно и исключает возможность доказательства каких-либо фактов о таких числах. Этот взгляд был опровергнут уже 2200 лет тому назад Эвклидом, доказавшим существование бесконечного множества простых чисел. Его рассуждение укладывается в одну фразу: если бы имелось лишь конечное число простых, то можно было бы их перемножить и, прибавив единицу, получить число, которое не делится ни на одно простое, что невозможно. В 18-м в. Эйлер доказал более сильное утверждение, а именно что ряд, составленный из величин, обратных простым, расходится, т. е. его частичные суммы1) становятся с ростом количества сла-

1) То есть суммы

где pn — это n-е простое число. — Прим. перев.

гаемых больше любого заданного числа. В его (также очень простом1)) доказательстве была использована функция

роль которой для изучения π(х) была полностью оценена лишь позднее, благодаря работам Римана. В этой связи стоит отметить, что, хотя сумма величин, обратных всем простым, бесконечна, однако сумма величин, обратных всем известным простым (т. е. примерно первым 50 миллионам), меньше четырех [15].

Только в 1850 г. Чебышеву удалось сделать первый шаг к доказательству закона распределения простых чисел [16]. Он показал, что при достаточно больших x справедлива оценка

т. е. что закон распределения простых чисел справедлив с относительной погрешностью, не превосходящей 11 %. Его доказательство, использующее биномиальные коэффициенты2), так красиво, что я не могу устоять перед искушением привести его упрощенный вариант (разумеется, ввиду этого, с несколько худшими постоянными).

Покажем, что выполняется такая оценка сверху:

Она непосредственно проверяется для х < 1200. Бу-

1) Совсем элементарное доказательство можно найти, например, в книге: Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении. — М.: Гостехиздат, 1954. — Прим. перев.

2) По поводу определения и используемых в дальнейшем свойств биномиальных коэффициентов см., например, книгу: Виленкин Н. Я. Комбинаторика. — М.: Наука, 1969. Наряду с используемым автором обозначением (n m) для биномиальных коэффициентов употребляется также обозначение Сmn. — Прим. перев.

дем рассуждать по индукции1) и предположим, что наша оценка доказана для всех х ⩽ n. Рассмотрим «центральный» биномиальный коэффициент (2n n). Поскольку он, безусловно, меньше 22n. С другой стороны,

Каждое простое число р, меньшее 2n, входит в числитель, но, если р больше n, не входит в знаменатель. Поэтому (2n n) делится на каждое простое, лежащее между n и 2n:2)

В произведении слева π(2n)— π(n) сомножителей, каждый из которых больше n, поэтому

Прологарифмировав, получим

Согласно предположению индукции, теорема верна для л, т. е.

1) С этим методом можно познакомиться, например, по книге: Соминский И. С. Метод математической индукции. — М.: Наука, 1974. — Прим. перев.

2) Запись b|а означает, что а нацело делится на b. — Прим. перев.

Складывая два последних неравенства, находим, что

т. е. теорема верна и для 2n. Так как

то она справедлива и для 2n + 1, чем и завершается шаг индукции.

Для получения оценки снизу нам понадобится следующая простая лемма, которая легко выводится из известной формулы для показателя степени простого числа, с которым оно входит в n! [17]:

ЛЕММА. Пусть р — простое число. Если pvp—наибольшая степень р, которая входит в (n k), то

СЛЕДСТВИЕ. Для любого биномиального коэффициента (n k) справедлива оценка

Применив утверждение этого следствия ко всем биномиальным коэффициентам с заданным n и сложив полученные неравенства, найдем

или, после логарифмирования,

В заключение я хочу сказать несколько слов о результатах Римана. Хотя Риман и не доказал асимптотического закона распределения простых чисел, зато он сделал нечто гораздо более удивительное —

дал тонную формулу для π(х). Эта формула выглядит так:

где суммирование идет по корням дзета-функции [18]. Корни эти (помимо так называемых «тривиальных корней» ρ = —2, —4, —6, ..., вкладом которых в общую сумму можно пренебречь) являются комплексными числами с вещественной частью, заключенной между 0 и 1; первые 10 из них таковы [19]:

Легко показать, что вместе с каждым ρ в число корней дзета-функции обязательно входит и комплексно-сопряженное с ним число. А вот знаменитая гипотеза Римана, что вещественная часть корня всегда в точности равна 1/2, еще никем не доказана, хотя ее доказательство имело бы для теории простых чисел в высшей степени важное значение [20]. В настоящее время гипотеза проверена для 7 миллионов корней.

С помощью введенной выше функции R(x) формулу Римана можно записать в виде

Это дает в качестве k-го приближения к π(х) функцию

где Tn (x) = — R (xρn) — R (хρn) — слагаемое, отвечающее n-й паре корней дзета-функции; Tn(х) при любом n является гладкой осциллирующей функцией от x, Графики Tn(х) для первых значений n показаны на рис. 9 [21]. Вместе с Tn(х) и Rk(x) является гладкой функцией при любом k. С ростом k эта функция приближается к π(х). На рис. 10 и 11 приведены для иллюстрации графики 10-го и 29-го приближений, а если сравнить эти кривые с графиком π(х)

Рис. 9.

Рис. 10.

Рис. 11.

на интервале от 0 до 100 (см. рис. 1), то получится картина, представленная на рис. 12.

Я надеюсь, что после моего рассказа у вас осталось некоторое впечатление о замечательной красоте простых чисел и о тех неисчислимых сюрпризах, которые они нам готовят.

Рис. 12.

Примечания

[1] J. M. Gandhi, Formulae for the n-th prime, Proc. Washington State Univ. Conf. on Number Theory, Washington State Univ., Pullman, Wash., 1971, 96—106.

[2] J. P. Jones, Diophantine representation of the set of prime numbers, Notices of the AMS 22 (1975), A-326.

[3] К тому что так много чисел из этого списка имеют вид Mk = 2k—1, существует веская причина: согласно одной теореме, восходящей к Люка, число Mk (k ⩾ 2) тогда и только тогда является простым, когда оно делит число Lk-1, где числа Ln определяются рекуррентным соотношением: L1 = 4, Ln+1 = L2n — 2 (так что L2 = 14, L3 = 194, L4 = 37634, ...) и, таким образом, простоту Мk проверить

значительно легче, чем простоту других чисел того же порядка. Простые вида 2k — 1 (в этом случае k само обязательно должно быть простым) называются простыми числами Мерсенна (по имени французского математика, который в 1644 указал в большей своей части верный список всех таких простых, меньших 1079). Числа Мерсенна играют важную роль и в некоторых других проблемах теории чисел. Эвклид обнаружил, что если число 2p — 1 — простое, то число 2р-1(2р— 1) является «совершенным», т.е. равно сумме своих собственных1) делителей (например, 6 = 1 + 2 + 3, 28 = 1 +2 + 4 + 7 + 14, 496 = 1 + 2 + 4 + 6 + 16 + 31 + 62+ 124 + 248), а Эйлер доказал, что все четные совершенные числа имеют указанный вид. Неизвестно, существуют ли вообще нечетные совершенные числа; во всяком случае, такие числа должны быть больше 10100. Имеется ровно 24 значения р < 20 000, при которых число 2p — 1 — простое.

[4] С. F. Gauß, Werke, II, 1872, 444—447. Обсуждение истории вопроса о приближениях π(х) см., например, в статье L. J. Goldstein, A history of the prime number theorem, Amer. Math. Monthly 80 (1973), 599—615.

[5] A. M. Legendre. Essai sur la théorie des Nombres, Paris, 1808, стр. 394.

[6] Точнее, имеют место неравенства

т.е. разность Li(x) и Ls(x) ограничена. Отметим, что в настоящее время интегральный логарифм обычно понимается в смысле главного значения:

однако это определение отличается от приведенного в тексте лишь на константу.

[7] Коэффициент при Li(√x) определяется следующим образом: он равен +1/n, если n есть произведение четного числа различных простых, равен — 1/n, если n — произведение нечетного числа различных простых, и равен 0, если n делится на квадрат какого-нибудь простого.

[8] Эту функцию можно представить и по-другому:

1) См. подстрочное примечание на стр. 11. — Прим. перев.

(ζ(s)—дзета-функция Римана, Γ(s)—гамма-функция) или

(Bk — это k-e число Бернулли; знак = означает, что разность соединенных таким знаком выражений стремится к 0 с ростом х); оба представления указал Рамануджан. См, H. G. Hardy, Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, Cambridge University Press, 1940, гл. 2.

[9] А именно: для пары (m, n) случайно выбранных чисел вероятность того, что m и n оба не сравнимы с 0 по модулю p1), очевидно, равна ((р — 1)/р)2, а для одного случайно выбранного числа n вероятность того, что n и n + 2 оба не сравнимы с 0 по модулю р, равна 1/2 при р = 2 и (р — 2)/р при р ≠ 2. Поэтому вероятность того, что n и n + 2 представляют собой пару «кандидатов в простые по модулю р», отличается от соответствующей вероятности для двух независимых чисел m и n множителем

при р ≠ 2 и множителем 2 или р — 2. Таким образом, интересующая нас вероятность отличается от указанной в тексте наличием множителя

Несколько более тщательно эти рассуждения проведены в книге:

G. H. Hardy, Е. М. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford, 1979, § 22.20, стр. 371—373.

[10] M. F. Jones, M. Lal, W. J. Blundon, Statistics on certain large primes, Math. Comp. 21 (1967), 103—107.

[11] D. Shanks, On maximal gaps between successive primes, Math. Comp. 18 (1964), 646—651.

График g(x) построен с использованием таблиц, приведенных в следующих работах:

L. J. Lander, Т. R. Parkin, On first appearance of prime differences, Math. Comp. 21 (1967), 483—488. R. P. Brent, The first occurrence of large gaps between successive primes, Math. Comp. 27 (1973), 959—963.

[12] Данные для этого графика взяты из таблицы простых чисел Лемера:

1) То есть не делятся на р. — Прим. перев.

D. N. Lehmer, List of Prime Numbers from 1 to 10006721, Hafner Publishing Co., New York, 1956.

[13] Этот и следующий графики построены по значениям π(х), приведенным в статье

D. С. Mapes, Fast method for computing the number of primes less than a given limit, Math. Comp. 17 (1963), 179—185.

В отличие от данных Лемера, использованных при построении предыдущего графика, эти значения вычислены по одной из формул π(х), а не путем непосредственного подсчета простых, не превышающих х.

[14] S. Skewes, On the difference π(х) — li(x). I, J. Lond. Math. Soc. 8 (1933), 277—283.

Приведенную оценку Скьюз сперва доказал в предположении справедливости обсуждаемой далее в тексте гипотезы Римана. Через 22 года он же:

S. Skewes, On the difference π(x) — li(x). II, Proc. Lond. Math. Soc. (3)5 (1955), 48—70.

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

для которого π(х) > Li(x). Эта граница была заменена Коэном и Мейхью на 1010529'7 а Леманом: Е. Lehman, On the difference π(x)—li (x), Acta Arithm. 11 (1966), 397—410.

на 1,65—101165. Леман даже показал, что между 1,53—101165 и 1,65—101165 имеется интервал, содержащий по меньшей мере 10500 чисел, на котором π(х) больше Li(x). Согласно его исследованиям, очень вероятно, что имеется число х, близкое к 6,663—10370, для которого π(х) > Li(x) и нет ни одного числа, меньшего 1020, с тем же свойством.

[15] Вообще, имеет место соотношение (предположенное в 1796 г. Гауссом и доказанное в 1874 г. Мертенсом):

где ε(х) → 0 при x → ∞ и С — константа, приблизительно равная 0,261497. Это выражение при х = 109 меньше 3,3 и даже при х = 1018 еще не превосходит 4.

[16] П. Л. Чебышев, Recherches nouvelles sur les nombres premiers, Paris 1851, C. R. Paris 29 (1849), 397—401, 738—739. Современное изложение доказательства Чебышева на немецком языке см. в книге1):

W. Schwarz, Einführung in Methoden und Ergebnisse der Primzahltheorie, BI-Hochschul-Taschenbuch 278/278a, Mannheim, 1969, § II. 4, стр. 42—48.

1) На русском см., например, Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.

[17] Наибольшая степень р, которая делит n!, есть1)

где [х] обозначает целую часть числа х — наибольшее целое, не превосходящее х; поэтому в обозначениях леммы

В этой сумме каждое слагаемое равно 0, или 11), причем заведомо равно 0 при

(так как тогда [n/рr] = 0). Значит,

откуда и следует утверждение леммы.

[18] Указанное ранее определение в виде ряда

имеет смысл лишь тогда, кода s — комплексное число, вещественная часть которого больше 1 (ибо только при таком условии ряд будет сходящимся), и в этой области ζ(s) не имеет нулей. Функцию ζ(s) можно, однако, доопределить для всех комплексных чисел и рассматривать ее корни в комплексной плоскости. Расширение области определения ζ(s) до полуплоскости Re(s) > 0 получается особенно просто, если воспользоваться справедливым при Re(s) > 1 тождеством

и заметить, что стоящий справа ряд сходится при всех s, имеющих положительную вещественную часть. Отсюда легко вывести, что «интересные» корни дзета-функции, т. е. корни вида ρ = ß + iγ, 0 < ß < 1, задаются двумя уравнениями

1) См. там же.

Ряд по корням р в формуле Римана сходится неабсолютно, и поэтому его члены следует располагать в надлежащем порядке (по возрастанию абсолютного значения Im(ρ)). Наконец, отметим, что точная формула для л(х) была найдена Риманом еще в 1859 г., а доказана Мангольдтом лишь в 1895 г.

[19] Эти корни уже в 1903 г. вычислил Грам:

J.-P. Gram, Sur les zéros de la fonction ξ(s) de Riemann, Acta Math. 27 (1903), 289—304.

Очень удачное изложение теории дзета-функции Римана и методов вычисления ее нулей дано в книге: Н. М. Edwards, Riemann's Zeta Function, Academic Press, New York, 1974.

[20] А именно, из гипотезы Римана вытекает следующее утверждение (верно и обратное): погрешность приближения л(х) функцией Li(x) не превосходит Cx1/2lnx, где С — некоторая постоянная; в то же время неизвестно, меньше ли эта погрешность хс при каком-нибудь с < 1.

[21] Этот график, как и три последующих, заимствован из работы:

Н. Riesel, G. Göhl, Some calculations related to Riemann's prime number formula, Math. Comp. 24 (1970), 969—983.

Добавление

Так как приведенный выше текст, представляющий собой точную запись моей вступительной лекции, уже был опубликован ранее1), я почёл за лучшее не пытаться «осовременить» текст, а оставив его без изменений, упомянуть результаты новейших исследований в этом коротком добавлении.

1. К списку необычных определений простых чисел, с которого мы начали наше путешествие, следует добавить еще одно, на этот раз из теории игр. А именно (по Конвею), отправляясь от N = 2, на каждом шаге мы заменяем N на αN, где α — первое из четырнадцати рациональных чисел

1) Elemente der Mathematik, Beiheft № 15, 1977 [английский перевод: Mathematical Intelligencer 0 (1977),) 7—19].

для которого число αN— целое. Для получающейся при этом последовательности 2, 15, 825, 725, 1925, .., все фигурирующие в ней степени двойки будут иметь вид 2p, где р — простые, идущие в своем естественном порядке! С помощью хорошего калькулятора можно таким путем за несколько минут отыскать первые 4 или 5 простых чисел.

2. С 1971 г. уже три раза был побит мировой рекорд наибольшего известного простого числа; по указанной в примечании 3 причине каждый раз это было снова число Мерсенна 2p—1, а именно с р = 21701, 23 209 и 44 4971). Подробнее об этом сказано в библиографических примечаниях к первой экскурсии.

3. Данные о количестве простых и простых-близнецов (табл. 8) теперь имеются до 1011:

R. Brent, Tables concerning irregularities in the distribution of primes and twin primes to 10", 12 computer sheets deposited in UMT File 21, Review in Math. Comp. 30 (1976) 379. Особенно интересна с этой точки зрения статья

R. Е. Grandall, M. A. Penk, A search for large twin prime pairs. Math. Comp. 33 (1979), 383—388.

В ней не тольке указана наибольшая известная пара близнецов (по 303 цифры в каждом!), но и описана статистическая проверка асимптотической формулы

(число близнецов между х и х + а)

для 132947 случайно выбранных чисел от 1049 до 1054 при ожидаемых 245±25 парах близнецов фактически было найдено 249 пар. В настоящее время и о функции «провалов» g(x) имеется больше данных, чем показано на рис. 5; см.

R. Brent, The distribution of prime gaps in intervals up to 1016, Review in Math. Comp. 28 (1974), 331. В качестве еще одного примера нерегулярности распределения простых чисел следует упомянуть результат Бейза и Хадсона о разности Δ(х) = π4,3(x) — π4,1(х):

С. Bays, R. Hudson, Math. Comp. 32 (1978), 281—286. (πa, b(x) обозначает число простых вида an + b, не превосходящих х.) Эта разность, которая при

1) См. первое подстрочное примечание на стр. 36. — Прим. перев.

малых x всегда положительна и при всех х очень мала (так, π4,i(1010) = 227523275, а π4,3(1010) = 227529235), согласно результатам Бейза и Хадсона, остается положительной до X = 950000000, за исключением менее чем одной тысячи значений, однако до x = 2⋅1010 есть очень большой интервал [1,854⋅1010, 1,895⋅1010], на котором она отрицательна, и ее минимум в этой области равен Δ (18699356297) = —2719.

4. Гипотеза Римана проверена уже для 150 миллионов корней, а именно для всех ρ, у которых IIm ρ| < 32585736,4. См.

R. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), 1361 — 1372.

Юрген Рольфс

О СУММАХ ДВУХ КВАДРАТОВ

Я расскажу о натуральных числах а, b и m, удовлетворяющих уравнению a2 + b2 = m. С помощью этой на первый взгляд простой темы очень удобно продемонстрировать ряд задач и методов, имеющих большое значение для всей теории чисел.

Особенно интересны (и, вероятно, не только мне памятны со школьных лет) так называемые пифагоровы тройки натуральных чисел а, b, с с a2 + b2 = c2. Такие тройки для краткости будем записывать в виде (a, b, с), причем тройки (а, b, с) и (b, а, с) считаются одинаковыми. Примером может служить тройка (3, 4, 5), которая была известна и письменно передавалась из поколения в поколение во всех развитых древних культурах [1]1) (стр. 49, 51, 96, 105). Эта тройка примечательна своим геометрическим содержанием — в ней находит арифметическое выражение древний способ построения прямых углов (см. рис. 13). Еще в 14 г. до н. э. римский писатель Витрувий восславил построение прямого угла с помощью тройки (3, 4, 5) как величайшее достижение всей тогдашней математики [1] (стр. 326). Предполагают, что благодаря найденной — вначале экспериментально — связи тройки (3, 4, 5) с построением прямого угла и возникла вообще идея теоремы Пифагора. Платон считал, что тройка (3, 4, 5) — это символ супружества

Рис. 13.

1) Числа в квадратных скобках отсылают к списку литературы в конце экскурсии.

[1] (стр. 157). Он истолковывал катет длины 4 как женское начало, вертикальный катет длины 3 — как мужское начало, а гипотенузу — как их потомство. Такое мистическое толкование нам сейчас чуждо и совершенно непонятно. Однако его существование показывает, какое большое значение придавалось тройке (3, 4, 5).

В древности пифагоровы тройки использовались на практике — в землемерном деле и в архитектуре, на что имеются даже указания в Библии. Так например, там сказано, что при построении скинии использовались ковры, основной квадрат которых имел измерения 3×4 локтя (Исход, 37.10), а при возведении соломонова храма были изготовлены подставки для жертвенных чаш с боковыми гранями размером 3×4 локтя (I кн. Царств, 7.27). Я думаю, что упоминание этих чисел в связи с великими святынями иудеев должно выражать нечто большее, чем просто гордость практически полезным знанием. Возможно, тройка (3, 4, 5) воспринималась как место соединения мира духовного и мира материального, так что упоминание ее в Библии имело глубокий внутренний смысл.

Естественно возникает задача — найти все пифагоровы тройки. При этом мы порываем со сферой практического применения, так как для построения прямых углов достаточно, конечно, одной-единственной пифагоровой тройки, и ищем теоретические знания ради них самих.

Если (а, b, с) — пифагорова тройка, то таковою будет и тройка (na, nb, nc) при всех n = 1, 2, 3, ... . Поэтому достаточно найти те пифагоровы тройки, у которых наибольший общий делитель а и b равен 1. Такие тройки называются простейшими. Чуть легче найти тройки, называемые квазипростейшими, у которых наибольший общий делитель а и b не превосходит 2. Диофант из Александрии (300 лет до н. э.) предложил следующее решение [1] (стр. 485):

Пусть (x, у) пробегает все пары взаимно простых (т. е. не имеющих отличных от 1 общих делителей) чисел, такие, что х > у. Если взять а = 2ху, b = x2 — y2, с = x2 + y2, то получатся все квазипростейшие пифагоровы тройки и при этом каждая ровно

один раз. Тройка (a, b, с) тогда и только тогда будет простейшей, когда одно из чисел х и у четно, а другое нечётно.

Я хотел бы привести два обоснования этого утверждения.

Простые соображения делимости показывают, что дело сводится в сущности к нахождению всех пар (а, b) рациональных чисел, для которых a2 + b2 = 1, а ≠ 0, b ≠ 0 и точка (а, b) лежит в первом квадранте плоскости1). Рассмотрим прямую g с угловым коэффициентом m, проходящую через точки (а, b) и (0,—1) (рис. 14). Если а и b — рациональные числа, то коэффициент m, очевидно, также рационален. Обратно, если m рационален, то координаты точки пересечения прямой g с указанной на рисунке единичной окружностью определяются как корни квадратного уравнения с рациональными коэффициентами. При этом одно решение, соответствующее точке (0, —1), нам известно, и оно является рациональным. Поэтому и второе решение, соответствующее точке (а, b), тоже будет рациональным. Вычисления дают

Положив m = х/у, получаем требуемые формулы.

Другое обоснование, в меньшей степени использующее геометрические соображения, таково. Пусть а и b — рациональные положительные числа и a2 + b2 = 1. Положим z = b + ia, где i = √—1. Тогда

Рис. 14.

1) То есть в первой координатной четверти. — Прим. перев.

Здесь z = b — ia. Полагая 1 + z = х + iу для рациональных x и у, снова получаем найденное ранее решение. Специалисты заметят, что за этими несколько формальными выкладками скрывается частный случай так называемой теоремы 90 Гильберта.

Очевидно, что в простейших пифагоровых тройках либо а, либо b четно. Указанные формулы дают только те тройки (а, b, с), в которых четно а.

Далее, из формул видно, что в каждой пифагоровой тройке а или b делится на 4. Кроме того, одно из чисел а, b делится на 3. Действительно, если бы ни а, ни b не делилось на 3, то при некоторых натуральных числах j и k выполнялись бы равенства

Но при делении квадрата натурального числа на 3 в остатке может получиться 0 или 1, но не 2. Таким образом, в этом случае сумма a2 + b2 не являлась бы квадратом, вопреки условию. Аналогично доказывается, что одно из чисел a, b, с делится на 5. На примере тройки (3, 4, 5) видно, что других аналогичных утверждений получить нельзя, т. е. что справедлив следующий результат:

Числа 1, 2, 3, 4, 5 образуют максимальное подмножество M множества натуральных чисел, обладающее таким свойством: для каждого элемента n из M в любой пифагоровой тройке есть число, делящееся на n.

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

ординаты. Точки плоскости с целочисленными координатами образуют так называемую целочисленную «решётку», и из таблицы видно, что простейшим пифагоровым тройкам соответствует сравнительно небольшое число точек целочисленной решетки в первом октанте. Далее это обстоятельство будет исследовано более подробно.

Итак, все пифагоровы тройки нам известны. Теперь можно изучать те тройки А, которые обладают каким-либо дополнительным свойством E(Δ), и при этом возникают интересные задачи.

Например, зададимся вопросом, бесконечно ли множество пифагоровых треугольников, у которых длины одного катета и гипотенузы выражаются простыми числами. Если (q, v, р) — тройка с простыми р и q, то (р — v)(p + v) = q2. Следовательно, р — v = 1 и р + v = q2. Поэтому 2р — 1 = q2. С другой стороны, если 2р = q2+ 1, то p2 = q2 + (p — 1)2. Таким образом, зная решения уравнения 2р — = q2 + 1 в простых числах р и q, можно найти все искомые тройки. Однако до настоящего времени неизвестно даже, конечно или бесконечно множество решений этого уравнения.

Другой пример возникает из того занятного наблюдения, что наряду с (5, 12,13) пифагоровой тройкой

Таблица 9.

x

y

а

b

с

2

1

4

3

5

3

1

6

8

10

3

2

12

5

13

4

1

8

15

17

4

3

24

7

25

5

1

10

24

26

5

2

20

21

29

5

3

30

16

34

5

4

40

9

41

6

1

12

35

37

6

5

60

11

61

7

1

14

48

50

7

2

28

45

53

7

3

42

40

58

7

4

56

33

65

7

5

70

24

74

7

6

84

13

85

8

1

16

63

65

8

3

48

55

73

8

5

80

39

89

8

7

112

15

113

9

1

18

80

82

9

2

36

77

85

9

4

72

65

97

9

5

90

56

106

9

7

126

32

130

9

8

144

17

145

10

1

20

99

101

10

3

60

91

109

10

7

140

51

149

10

9

180

19

181

является также (15,112,113). Б. Леви доказал [3], что имеется бесконечно много пифагоровых троек, из которых таким приписыванием спереди цифры 1 снова получается пифагорова тройка, а Сантало [6] — что это справедливо для каждой из цифр 1, 2, 7.

Уточним постановку вопроса. Пусть E(Δ)— некое свойство, которым обладает или не обладает данная пифагорова тройка Δ, и V — некое правило, по которому каждой пифагоровой тройке А ставится в соответствие вещественное число V(Δ). Рассмотрим функцию F, сопоставляющую каждому вещественному числу v число F(v) пифагоровых троек, обладающих свойством E(Δ) и удовлетворяющих неравенству V(Δ) < v. В сокращенной записи

Если lim F(v) = ∞, то исследуется асимптотический рост F(v) при v → ∞, т. е. отыскивается и доказывается равенство вида F(v) = сvα + O(vβ)1), где с, α, ß — вещественные числа, причем α > ß > 0.

В качестве примера (заимствованного у Ламбека и Мозера [4] ) рассмотрим функцию

Метод, с помощью которого она изучается, несложен и часто употребляется в теории чисел, поэтому стоит его здесь продемонстрировать.

Мы располагаем формулами для нахождения квазипростейших пифагоровых троек. В связи с этим разумно ввести функцию

Так как Q(v) = F(v) + F(v/2), то можно выразить F(v) через Q(v):

1) Означающее, что |F(v) — cvα| ⩽ Avβ при всех достаточно больших v, где А — некоторая положительная постоянная. — Прим. перев.

Почти все слагаемые этой бесконечной суммы равны 0. Положим для всякого вещественного числа t > 0

Согласно ранее сказанному, Q(v) = q(v1/2). Пусть

Тогда, очевидно,

где [t] обозначает наибольшее целое число, не превосходящее t. Последнее уравнение можно разрешить относительно q(t), используя так называемую функцию Мёбиуса μ (см. [5], (16.4)1)). Она определяется следующим образом: если n = p1р2 ... рr — разложение n на простые множители pi, то μ(n) = 0, когда в этом разложении есть два одинаковых сомножителя, и μ(n) = (—1)r, когда все сомножители различны. Если положить μ(1) = 1, то каждому n = 1, 2, 3, ... будет поставлено в соответствие ровно одно из чисел —1, 0, 1. В результате получается

Таким образом, для решения первоначальной задачи следует найти асимптотическое выражение для l(t). Мы утверждаем, что

Это означает, что погрешность, возникающая при замене l(t) на (π/8)t2, самое большее пропорциональна t. Для вывода последнего равенства следует заметить,

1) Или Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — Прим. перев.

что число всех узлов целочисленной решетки, лежащих в множестве M точек (х, у) плоскости, для которых х ⩾ у ⩾ 0 и x2 + y2 < t2 (рис. 15), приблизительно равно площади M, а возникающая при этом погрешность пропорциональна числу ячеек решетки, через которые проходит граница М. Эта погрешность, очевидно, пропорциональна длине границы, что и дает указанное соотношение. Это — ключевой момент всего рассуждения1). Оно использовалось в аналогичной ситуации уже Гауссом. Итак,

Но известно, что

Из равенства

Рис. 15.

1) Более подробно об этом см.: Бухштаб А. А. Теория чисел.—М.: Просвещение, 1966.

следует, что Так как

то при t = n2 приходим к равенству

откуда, учитывая, что

получаем наконец,

Величину 2F(v) можно интерпретировать как количество узлов целочисленной решетки с положительными и взаимно простыми координатами, расстояние которых от начала координат есть натуральное число, не превосходящее v. Как мы только что видели, для числа L(v) всех узлов решетки в первом квадранте, расстояние от которых до начала координат меньше v, справедливо равенство

Частное 2F(v)/L(v), асимптотически равное 4/π2v, можно рассматривать как приближенное значение плотности точек, соответствующих простейшим пифагоровым тройкам, среди всех узлов целочисленной решетки, лежащих в первом октанте на расстоянии, меньшем v, от начала координат.

Ламбек и Мозер провели аналогичные рассуждения для функций

Если для функции F(v) найдено асимптотическое представление вида F(v) = cvα + O(vβ), где α > > ß > 0, то на следующем этапе можно пытаться определить асимптотическое поведение разности F(v) — cvα при больших v и т. д. Для функции F = Fa начало таких исследований было положено Р. Уилдом [7].

Во второй части нашей экскурсии мы рассмотрим решения более общего уравнения a2 + b2 = m с целыми а, b и m. Если натуральное число m задано, то прежде всего следует выяснить, имеет ли уравнение вообще целочисленные решения (например, при m = 3 их нет). Еще Диофантом из Александрии было замечено, что это уравнение неразрешимо, если при делении m на 4 получается остаток 3, так как квадраты натуральных чисел могут при делении на 4 давать в остатке лишь 0 или 1, а следовательно, a2 + b2 может дать в остатке 0, 1 или 1 + 1 = 2, но никак не 3. Исчерпывающий ответ на этот вопрос был найден в 1638 г. Ферма. Он показал ([5], § 201)), что m тогда и только тогда представимо в виде a2 + b2 с целыми a и b, когда все простые делители m, дающие при делении на 4 остаток 3, входят в m в четной степени. Кроме того, Ферма удалось даже найти формулу для числа v(m) различных пар (а, b) целых чисел, для которых a2 + b2 — m. А именно,

1) См. также Дэвенпорт Г. Высшая арифметика. — М.: Наука, 1965. — Прим. перев.

где d1(m) и d3(m) — число делителей m, дающих при делении на 4 остатки 1 и 3 соответственно ([5],§ 19.9), Если положить χ(d) = 0 при любом четном натуральном d, χ(d) = (—1)(d-1)/2 при нечётном натуральном d и использовать обозначение d|m для записи высказывания „m делится на d“, то можно также написать

Когда m = р — простое и р = 4j + 3 при некотором натуральном j, мы получаем v(р) = 0; если же р = 4j+1, то v(р) = 8. Число 8 легко объяснимо. Если a2 + b2 = р = 4j + 1, то a ≠ b и имеется 8 различных решений: (a/b), (—а,b), (а,—b), (—а,—b), (b, а), (—b, а), (b, —а), (—b, — а).

Полученную для v(m) формулу можно интерпретировать и совсем иначе. Пусть q принимает вещественные или комплексные значения и |q| < 1, Используя известное выражение для суммы геометрической прогрессии, легко убедиться, что эта формула эквивалентна следующему тождеству для степенных рядов:

Интересно, что Якоби в 1829 г. доказал это тождество совершенно другим путем, занимаясь теорией эллиптических функций (см. по этому поводу [5], § 17 и указанную там литературу). Если положить

то, очевидно,

так что наше утверждение о суммах двух квадратов можно трактовать как разложение так называемой тэта-функции θ(q)2 в степенной ряд. При этом напрашиваются различные обобщения. Например, если

желательно определить количество с(m) различных представлений натурального числа m в виде суммы четырех квадратов целых чисел, то надо «всего лишь» знать разложение функции θ(q)4 в степенной ряд. Якоби нашел, что

здесь штрих означает, что суммирование ведется по всем натуральным числам n, не делящимся на 4 ([5], § 20). Сравнивая коэффициенты в левой и правой частях последнего равенства, получаем, что с(m) равно сумме всех делителей m, не делящихся на 4:

В частности, отсюда вытекает знаменитая теорема, сформулированная Ферма и впервые доказанная Лагранжем: всякое натуральное число можно представить в виде суммы четырех квадратов.

Я не буду пытаться обосновать все перечисленные результаты, а хочу в заключение указать одну физическую задачу, для решения которой нужно знать целочисленные решения уравнения a2 +b2 = m. При этом окажется, что теоретико-числовые и аналитические вопросы «сами собой» своеобразно переплетаются друг с другом.

Рассмотрим двумерный тор Т. Наглядно его можно представить себе как (полый) спасательный круг (рис. 16): формально-математически T = (R/Z)×(R/Z), где R/Z—интервал [0,1] со склеенными точками 0 и 1. Допустим, что наш тор изготовлен из тонкой жести и его неравномерно нагревают паяльной лампой. В момент времени t = 0 уберем лампу. К этому моменту в каждой точке р тора установится некоторая температура u(р,0) = u(р). Очевидно, что во всякий более поздний момент времени t температура в точке р будет иметь вполне определенное значение u(p,t). Его можно определить не только измерением, но и чисто теоретически. А именно, будем

описывать каждую точку р тора Т двумя вещественными числами x, у (координатами), взятыми по модулю 11). Из физики известно, что при выборе надлежащего масштаба времени функция и является однозначно определяемым решением уравнения теплопроводности

с начальным условием u(р > 0) = u(р). Будем считать, что функция u(р, t) периодична с периодом 1 по каждой из переменных х, у и что функцию р |→ u(р, 0) можно разложить в «хорошо» сходящийся ряд вида

где ga,b — комплексные числа, а fа,b (x, y) = ехр (2πi(ах + by) ) (так называемое разложение в ряд Фурье). Строго говоря, u(x, у, 0) задается вещественной частью этого ряда. Имеем

Найдем теперь — совершенно формально — решение уравнения теплопроводности:

Число

можно теперь трактовать как размерность собственного подпространства дифференциального оператора

Рис. 16.

1) То есть 0 ⩽ х < 1, 0 ⩽ y < 1. — Прим. перев.

на Г, отвечающего собственному значению

Спектр оператора d2/dх2 + d2/dу2, а точнее распределение его собственных значений описывается функцией

Она была в 1909 г. исследована Э. Ландау ([2], § 183), который установил, что

Возвращаясь к уравнению теплопроводности, введем обозначение

Пусть dv = dx/\dy — элемент поверхности тора. Непосредственно проверяется, что

Функция F( , , ) называется фундаментальным решением уравнения теплопроводности на торе; зная F, можно найти решение уравнения теплопроводности с любыми заданными начальными условиями. Очевидно,

при t > 0. Функция

— это как бы стенограмма, в которой записаны все v(m). Положив z = i⋅4πt, с = ехр(πiz), получаем вместо последнего выражения

Эта сумма имеет смысл при Im(z) > 0 и определяет в этой области аналитическую функцию (уже встречавшуюся нам под именем тэта-функции). Если совершенно формально сопоставить выражению

функцию

определенную для комплексных s, у которых вещественная часть больше 1, то, как можно доказать,

где бесконечное произведение берется по всем простым числам. Функция с точностью до множителя 4 представляет собой так называемую дзета-функцию поля Q (√—1).

Таким образом, мы видим, что с уравнением теплопроводности на торе тесно связаны некоторые аналитические функции. Их можно определить, зная функцию m| → v(m) и наоборот.

Все затронутые выше вопросы и бегло намеченные связи чрезвычайно легко поддаются обобщению и являются частью живой, полнокровной теории. Я надеюсь, что мне удалось пробудить ваше любопытство.

Литература

[1] М. Cantor, Vorlesungen über Geschichte der Mathematik, Bd. lf Leipzig — Berlin, Teubner, 1922.

[2] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, New York, Chelsea, 1953.

[3] В. Levi, On a Diophantine problem, Math. Notae 5 (1945), 108—119.

[4] I. Lambek, L. Moser, On the distrbution of Pythagorean triangels, Pacific J. Math. 5 (1955), 73—83.

[5] G. H. Hardu, E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford, 1979.

[6] L. A. Santalo, Addendum to the note «On a Diophantine problem», Math. Notae 5 (1945), 162—171.

[7] R. E. Wild, On the number of Pythagorean triangles with area less than n, Pacific J. Math. 5 (1955), 85—91.

[8] D. V. Widder, The heat equation, New York, London, Academic Press, Inc., 1975.

Ханспетер Крафт

АЛГЕБРАИЧЕСКИЕ КРИВЫЕ И ДИОФАНТОВЫ УРАВНЕНИЯ

Те, кому посчастливилось ходить на уроки математики еще до введения теории множеств в школьную программу, несомненно, помнят теорему Пифагора:

В прямоугольном треугольнике сумма площадей квадратов, построенных на катетах, равна площади квадрата, построенного на гипотенузе (рис. 17).

Эта теорема была известна в Вавилонии уже во времена ХАММУРАПИ, а возможно, ее знали и в древнем Египте, однако впервые она была доказана, по-видимому, в пифагорейской школе. Так называлась группа интересующихся математикой философов по имени основателя школы ПИФАГОРА (ок. 580—500 г. до н. э.) — личности довольно мифической. Это был мистик, ученый и политик аристократического толка. Он, должно быть, путешествовал по Вавилонии и Египту, а позднее на юге Италии, в Кротоне, собрал вокруг себя кружок увлеченных юношей, из которого и возникла пифагорейская школа. В настоящее время уже

Рис. 17. Рис. 18.

невозможно установить, какие достижения пифагорейцев принадлежат самому учителю, а какие следует приписать его ученикам.

Пусть длины сторон прямоугольного треугольника ABC (рис. 18) обозначены через а, b, с, причем сторона длины с находится напротив прямого угла. Теорема Пифагора утверждает справедливость равенства

(1)

Оно выполняется, например, если вместо а, b, с подставить числа 3, 4, 5, или 5, 12, 13, или 41, 140, 149. Такие решения уравнения (1) в целых положительных числах нашли уже пифагорейцы, и потому такие решения называют пифагоровыми тройками. Вполне возможно, что поиски этих троек и привели к теореме Пифагора. Впрочем, тройка (3,4, 5) была известна значительно раньше, о чем свидетельствует, скажем, дошедший до нас диалог императора ЧЖОУ-ГУНА (ок 1100 г. до н. э.) и ученого ШАН ГАО ([2]1)), стр. 54—65); более подробно о тройке (3, 4, 5) рассказывается в предыдущей лекции Ю. Рольфса.

Зададимся вопросом, сколько существует пифагоровых троек. Очевидно, умножая все три числа на любое целое n, можно из тройки (а, b, с) получить бесконечно много новых троек; из тройки (3, 4, 5) возникает таким образом последовательность троек (3,4,5) (6,8,10), (9,12,15), (12,16,20),... Поэтому уточним поставленный вопрос и будем искать простейшие пифагоровы тройки (a, b, с), т. е. те, у которых наибольший общий делитель чисел а, b и с равен 1. Решение этой задачи указал ещё ДИОФАНТ из Александрии (ок. 250 г. н. э.):

Если n и m — два взаимно простых целых (положительных) числа, разность которых n — m положительна и нечётна, то (2mn, n2 — m2, n2 + m2) — простейшая пифагорова тройка, и любая из таких троек может быть найдена этим способом.

1) Числа в квадратных скобках отсылают к списку литературы в конце экскурсии.

Первая часть утверждения легко проверяется непосредственной подстановкой; частные случаи этого «правила построения» пифагоровых троек были известны и раньше. Более сложно доказать, что таким образом получаются все простейшие тройки. Сейчас мы установим это с помощью геометрических соображений. Разделив равенство (1) на c2, получим

Поэтому каждая пифагорова тройка (а, b, с) дает решение уравнения

(2)

в рациональных числах (дробях), а именно х = а/с, у = b/с; назовем такую пару рациональным решением уравнения (2). Наоборот, из всякого такого решения, если привести дроби х и у к общему знаменателю: х = а/с, у = b/с, где а, b, с — целые, тотчас возникает пифагорова тройка. Следовательно, наша задача сведена к определению рациональных решений уравнения (2). Это уравнение также хорошо известно из школы — оно задает на эвклидовой плоскости окружность с центром в начале координат и радиусом 1 (рис. 19). Если рассмотреть прямую g с угло-

Рис. 19.

вым коэффициентом X, проходящую через точку (0,-1):

(3)

то координаты обеих точек пересечения S = (0,—1) и Рλ = (хλ, уλ) прямой g с окружностью удовлетворяют уравнениям (2) и (3). Подставляя (3) в (2), получаем

(4)

откуда можно найти координаты (xλ, уλ,) точки Рλ:

(5)

(Легко убедиться подстановкой, что они являются решением уравнения (2).) При рациональных x эти решения, очевидно, будут рациональными. Обратно, если (x0, y0) — рациональное решение уравнения (2) и Р0 — соответствующая ему точка на окружности, то угловой коэффициент прямой, проходящей через точки (0,—1) и Р0, рационален: λ = (y0+1)/х0. Следовательно, (x0, y0) есть решение вида (5). Таким образом, доказано, что все рациональные решения уравнения (2) находятся по формулам (5) с рациональным λ. Если записать λ в виде дроби: λ = n/m, то формулы (5) перепишутся так:

Итак, любая пифагорова тройка представима в виде (2nm, n2— m2, n2+m2), что и требовалось доказать.

Приведенный результат — лишь один из многих, содержащихся в «Арифметике» Диофанта. До нашего времени сохранились 6 книг этого сочинения; об их общем числе можно только строить догадки. Неизвестно также, кем был Диофант. Во всяком случае, его труд — одно из самых великолепных сочинений античной эпохи, в котором собраны весьма разнообразные задачи и часто с чрезвычайно остроумными решениями. (Более подробные сведения интересующийся читатель может найти в удачной книжечке Башмаковой [1].)

Именно сочинение Диофанта — изданное в 1621 г. в переводе Клода Гаспара де Баше де МЕЗИРЬЯКА (1581—1630) —дало повод Пьеру ФЕРМА записать на полях перевода одно из самых достопримечательных и далеко поведших замечаний в истории математики:

«Cubum autem in duos cubos, aut quadrato-quadratum in duos quadrato-quadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duas ejusdem nominis fas est dividere; cujus rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.»

«Невозможно разложить куб на два куба, или биквадрат на два биквадрата, или вообще степень, большую двух, на две степени с тем же самым показателем; я нашел этому поистине чудесное доказательство, однако поля слишком малы, чтобы оно здесь уместилось».

Таким образом, большая теорема Ферма утверждает, что уравнение

(6)

ни при каком натуральном n, большем 2, неразрешимо в целых положительных числах.

Общее доказательство сформулированного утверждения не удалось найти до сих пор, несмотря на то что этим занимались поколения математиков. Вероятнее всего, Ферма ошибался, предполагая, что располагает решением. В 1908 г. Пауль ВОЛЬФСКЕЛЬ завещал премию в сто тысяч марок тому, кто первым представит доказательство. В результате инфляции после первой мировой войны величина премии в настоящее время составляет едва десятую часть первоначальной суммы (см. [15], лекция 1, пункт 7). К тому же, как указывает Г. Эдвардс в своей книге [5] о теореме Ферма, премия назначена лишь за доказательство предположения — контрпример не принесёт ни пфеннига!

Справедливость большой теоремы Ферма для некоторых частных случаев была установлена уже до-

вольно давно: сам Ферма доказал неразрешимость уравнения (6) при n = 4, Л. ЭЙЛЕР — при n = 3 (1770 г.), А. ЛЕЖАНДР —при n = 5 (1825 г.) и Г. ЛАМЕ — при n = 7 (1839 г.). Самые замечательные результаты здесь принадлежат, однако, Э. КУММЕРУ (1810—1893), который своими исследованиями по проблеме Ферма оказал решающее влияние на развитие алгебраической теории чисел. В нашем столетии его методы были усовершенствованы и дополнены (1929 г. и позже) прежде всего благодаря усилиям У. ВАНДИВЕРА, Д. ЛЕМЕРА и Э. ЛЕМЕРА, так что к настоящему времени неразрешимость уравнения (6) доказана (с использованием ЭВМ) для всех n ⩽ 125000 (3. ВАГШТАФФ, 1976 г.; см. также [15], лекция 2, «Последние результаты»). Если принять во внимание, что число 2125000 записывается посредством 37628 цифр, то поиски контрпримера к большой теореме Ферма представляются совершенно безнадежным занятием!

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

(7)

Рассмотрев на эвклидовой плоскости кривую Fn, заданную этим уравнением, получим две качественно

Рис. 20.

различные возможности в зависимости от чётности или нечётности n (см. рис. 20). Кривая Fn называется кривой Ферма порядка n. Поэтому гипотеза Ферма означает, что на кривой Fn порядка выше 2 единственными рациональными точками (т. е. точками с рациональными координатами) являются точки пересечения с осями координат.

Сам собой напрашивается следующий общий вопрос:

Каковы рациональные точки кривой С на эвклидовой плоскости, задаваемой произвольным алгебраическим уравнением

(8)

с целочисленными коэффициентами aij?

Порядок кривой С, т. е. максимальная из степеней i + j одночленов xiуj, входящих в уравнение (8), служит грубой мерой сложности кривой. Очевидно, что чем выше порядок, тем труднее найти рациональные решения уравнения (8). Это обстоятельство находит более точное выражение в гипотезе МОРДЕЛЛА:

На кривой, порядок которой выше или равен четырем, имеется лишь конечное число рациональных точек.

Здесь следует сделать оговорку, что рассматриваются кривые «общего вида»1), а вырожденные случаи во внимание не принимаются.

Относительно справедливости гипотезы Морделла известно очень мало; единственным общим результатом здесь является теорема ЗИГЕЛЯ ([16], 1929 г.):

На кривой общего вида, порядок которой выше 2, лежит лишь конечное число целых точек (точек с целыми координатами), т. е. у соответствующего уравнения (8) существует лишь конечное число целочисленных решений.

1) Формально-математически это означает отсутствие особенностей у соответствующей комплексной проективной кривой, представляющей собой тем самым поверхность Римана рода g > 1.

Для кривых малого порядка d картина следующая: при d = 1 имеем прямую и на ней бесконечно много рациональных (и даже целых) точек; при d = 2 получается квадрика (эллипс, парабола, гипербола); на квадрике либо совсем нет, либо бесконечно много рациональных точек1). Это доказывается тем же геометрическим методом, который выше был применен для нахождения рациональных точек на единичной окружности и который, согласно данным Башмаковой, также восходит к Диофанту ([1], § 5). И именно, прямая с рациональным угловым коэффициентом, проходящая через рациональную точку Р квадрики, пересекает ее в рациональных точках. Поворачивая прямую вокруг точки Р, получаем бесконечно много рациональных точек (рис. 21).

Случай d = 3 является в известном смысле промежуточным между рассмотренными. Как мы видели, на кривой Ферма F3 (рис. 20) лежат лишь две рациональные точки, а сейчас мы приведем пример кривой третьего порядка, на которой бесконечное число рациональных точек. Для этого воспользуемся следующим методом секущих, представляющим собой обобщение указанного ранее способа для квадрик (и этот метод тоже встречается у Диофанта; см. [1], § 6):

Рис. 21. Рис. 22.

1) Случаи, когда квадрика вырождается в точку (как это будет, например, для кривой, задаваемой уравнением x2 + y2 = 0), не принимаются во внимание.

Если Р и Q — две рациональные точки кривой С третьего порядка и прямая, проходящая через Р и Q, пересекает кривую С еще в одной точке R, то R также является рациональной точкой (рис. 22).

Это утверждение доказывается очень просто. Если

(9)

— уравнение прямой, проходящей через точки Р и Q, то г и s — рациональные числа, ибо их можно выразить через координаты (хР, уР) и (xq, уQ) точек Р и Q по формулам

Подставив (9) в уравнение кривой С, получим для х уравнение третьей степени

(10)

с рациональными коэффициентами а, b, с. По условию корнями его являются абсциссы точек пересечения Р, Q и R прямой g с кривой С, т. е. хР, xQ) xR. Однако, зная корни уравнения, можно найти его коэффициенты совершенно так же, как это делается в школе для квадратного уравнения. Например, сумма корней, взятая с противоположным знаком, равна коэффициенту при x2:

По предположению хР и xQ рациональны, поэтому рациональным будет и Xr, а значит, и yR = rхR + s, т. е. R — рациональная точка, что и требовалось доказать.

Опробуем этот способ на кривой Е, заданной уравнением

(11)

отправляясь от точек Р = (—5,0), Q = (0,0) ; R = (5,0) и S = (—4,6) (рис. 23). Сначала, используя прямую SQ, получим точку S1 с координатами

затем получим точку S2

далее точку S3

и т. д. Из уравнения (11) видно также, что кривая Е симметрична относительно оси х: вместе с каждой точкой Т(хT,уT) на кривой лежит и симметричная ей относительно оси х точка T' = (хТ, —уT), и если точка Т рациональна, то и Т' будет рациональной. Это можно подогнать под описанный выше метод секущих следующим образом: дополним кривую Е «несобственной точкой» О в направлении оси у. Прямые, проходящие через О, — это прямые, параллельные оси y, и мы можем получить точку T' как «третью точку пересечения» прямой, проходящей через О и T, с кривой Е. Далее, можно использовать предельный случай метода секущих—метод касательных: вместо прямой, проходящей через рациональные точки Р и Q, брать касательную t к кривой в рациональной точке Р (считая точки Р и Q совпавшими). Рассуждениями, аналогичными проведенным ранее, можно показать, что точка пересечения прямой t с кривой Е тоже будет рациональной (и опять это было известно уже Диофанту; см. [1], § 6).

В разобранном выше примере создается — и совершенно справедливо — впечатление, что проводимые построения никогда не заканчиваются и позволяют найти бесконечно много рациональных точек на кривой Е. Затруднения могли бы возникнуть, лишь если бы мы после конечного числа шагов вернулись к одной из ранее полученных точек, но это представляется весьма маловероятным ввиду все усложняющихся знаменателей.

Следующее утверждение было высказано в 1901 г. А. ПУАНКАРЕ (1854—1912) [14], а доказано только

Рис. 23.

спустя 20 лет (в 1922 г.) Л. МОРДЕЛЛОМ [19]:

Все рациональные точки кривой третьего порядка можно получить из некоторого конечного их числа с помощью описанного способа построения.

Как и в теореме Зигеля, кривая считается «пополненной» своими несобственными точками, и кроме того, предполагается, что она является кривой общего вида (т. е. не имеет особенностей). Такие кривые называются эллиптическими1).

Сформулированная выше теорема Морделла была обобщена в двух различных направлениях: вместо рациональных точек стали рассматривать точки с координатами из заданного числового поля, а вместо эллиптических кривых — поверхности произвольной размерности (так называемые абелевы многообразия). Начало этим обобщениям было положено А. ВЕЙЛЕМ, и окончательный результат называют сейчас теоремой Морделла — Вейля.

В связи с этими вопросами о рациональных точках за последние 15 лет появился ряд отчасти фантастических гипотез (Б. БЕРЧ, Х. П. СУИННЕРТОН-ДАЙЕР, Дж. ТЭЙТ, Э. ОГГ; см. обзорную статью [17]). Справедливость некоторых из них недавно

1) Происхождение этого названия имеет долгую историю. Уже в 17-м столетии при вычислении длин дуг эллипсов и других кривых математики столкнулись с интегралами вида

где f(x)—многочлен степени не выше 4. Исследование этих эллиптических интегралов начал Эйлер. АБЕЛЬ и независимо от него ЯКОБИ рассмотрели обратные функции для этих интегралов. Следуя Якоби, их стали называть эллиптическими функциями. Выяснилось, что это двоякопериодические мероморфные функции, удовлетворяющие дифференциальному уравнению вида

Исходя из этого уравнения, можно показать, что эллиптические функции — это в точности функции, мероморфные на эллиптических кривых (понимаемых как компактные римановы поверхности).

была подтверждена в проложившей новые пути работе Б. МАЗУРА ([8], 1976 г.). Речь идёт о вопросах, связанных с так называемой «тонкой структурой» рациональных точек на эллиптической кривой, и об этом мне хотелось бы немного рассказать в заключение.

Рассмотрим эллиптическую кривую Е, заданную в канонической форме Вейерштрасса, т. е. уравнением вида

(12)

с целочисленными коэффициентами a, b и с. Качественно возможны два показанных на рис. 24 случая, в соответствии с тем, один или три вещественных корня имеет многочлен в правой части (12) (эти корни соответствуют точкам пересечения Е с осью х). Будем опять считать кривую Е пополненной несобственной точкой О в направлении оси у. Следуя А. Пуанкаре [14], определим на кривой Е операцию P*Q: для любых точек Р и Q точка P*Q — это третья точка пересечения прямой PQ с кривой Е, симметрично отраженная относительно оси х (рис. 25).

Легко видеть, что введенная операция коммутативна (т. е. P*Q = Q*P), что точка О является для нее нейтральным элементом (т. е. O*Р = Р = Р*O) и что для каждой точки Р существует обратный элемент— симметричная ей относительно оси х точка Р'

Рис. 24.

(т. е. Р * Р' = 0 = Р'* Р). Несколько сложнее доказать, что эта операция ассоциативна (т. е. (P*Q)*R = P*(Q*R) для любых точек Р, Q, R). На языке современной математики это означает, что точки кривой Е образуют коммутативную группу относительно операции *.

Из предыдущих рассуждений следует, что для любых двух рациональных точек Р, Q точка P*Q также рациональна, — собственно, это и послужило исходным пунктом нашего метода секущих для построения рациональных точек. Итак, рациональные точки Erat кривой Е образуют подгруппу группы Е. (Несобственная точка О считается рациональной.)

Искушенный читатель легко заметит, что теорему Морделла можно теперь сформулировать так:

Рациональные точки эллиптической кривой образуют конечно-порождённую коммутативную группу.

Эта формулировка имеет определенные преимущества, так как для таких групп известны структурные теоремы. Например, группу Erat можно представить в виде произведения некоторой конечной группы ТE и конечного числа бесконечных циклических групп. Количество бесконечных циклических сомножителей называется рангом эллиптической кривой Е, а конечная группа ТЕ — ее группой кручения. О ранге известны до сих пор только отдельные факты. Так, А. НЕРОН ([11], 1953 г.) доказал, что существует кривая, ранг которой не меньше 10, не приведя, правда, явного примера. А. ВИМАН ([20], 1948 г.) построил пример кривой ранга ⩾ 4, Д. ПЕННИ и К. ПОМЕРАНС ([13], 1975 г.) дали пример кривой ранга ⩾ 7, а Ф. ГРЮНЕВАЛЬД и Р. ЦИММЕРТ

Рис. 25.

([6], 1977 г.)—кривой ранга ⩾ 81); к числу кривых ранга ⩾ 8 относится, например, кривая, задаваемая уравнением

Рассмотренная ранее кривая (11) (рис. 23) имеет ранг 1, соответствующая бесконечная циклическая подгруппа порождается точкой S = (—4, 6). Это следует из результатов Р. ВАХЕНДОРФА ( [19], 1974 г.), который исследовал кривые, задаваемые уравнениями вида y2 = x3 — p2х, где р — простое.

Пока неясно, существуют ли эллиптические кривые сколь угодно большого ранга (что считается весьма вероятным). Известно, однако, что ранг оценивается через коэффициенты уравнения (12) (точнее, через число различных простых сомножителей отдельных коэффициентов [18]). Поэтому неудивительно, что в построенных примерах кривых высокого ранга уравнения имеют большие коэффициенты. Согласно одной из упомянутых выше гипотез, ранг эллиптической кривой Е равен кратности нуля так называемого L-ряда LE(z) кривой Е в точке z = 1 (Бёрч и Суиннертон-Дайер [3]).

Рассмотрим, наконец, группу кручения ТЕ. Она состоит из рациональных точек Р конечного порядка (т. е. из тех, для которых n-кратная композиция Р*Р* ... *Р равна О при некотором n), называемых (рациональными) точками кручения. Прежде всего на основании самого вида кривой можно заключить, что справедлива следующая общая структурная теорема: группа ТE либо сама циклична, либо есть произведение группы Z2 порядка 2 на циклическую группу. Это можно обосновать следующим образом. Кривая Е (пополненная) состоит из одной или двух

1) Видоизменив метод Грюневальда и Циммерта, К. НАКАТА нашел недавно пример кривой ранга ⩾ 9 (К. Nakata, Manuscripta Math. 29 (1979)).

замкнутых линий (см. рис. 24), а потому топологически выглядит как одна или две окружности. При этом часть E0, содержащая (несобственную) точку О, образует подгруппу. Можно доказать, что любая конечная подгруппа в E0 циклическая (это делается точно так же, как для группы вращений окружности). Следовательно, если группа кручения ТЕ целиком лежит в E0, то ТЕ— циклическая группа. В противном случае ТЕ есть произведение Z2 на группу Те точек кручения из E0.

О группе кручения кое-что было известно уже довольно давно. Так, Т. НАГЕЛЛЬ ([10], 1935 г.) и, позднее, Л. ЛУТЦ ([7], 1937 г.) получили следующий интересный результат, дающий одновременно метод для явного определения точек кручения конкретных кривых:

Если Р — (рациональная) точка кручения эллиптической кривой Е, заданной уравнением

то ее координаты хР и уР являются целыми числами, причем уР равно или 0, или какому-нибудь делителю дискриминанта D кривой Е.

(Дискриминантом кривой называется определенный многочлен от коэффициентов уравнения; в данном случае дискриминант равен

условие D ≠ 0 является необходимым и достаточным условием регулярности кривой E.) Например, для кривой

группа кручения ТЕ есть циклическая группа порядка 8, порожденная точкой Р = (3, 12). Другим примером служит кривая

с циклической группой кручения порядка 7, порожденной точкой P = (3,8). Весьма занимательно и со-

всем несложно самостоятельно придумать и исследовать другие примеры.

Уже давно существовало предположение, подтверждавшееся всё новыми численными примерами, что порядок группы кручения ограничен. К 1960 г. было известно, что он не может принимать некоторых значений, например кратных 11, 14, 15, ... (см. [4]).

В 1976 г. Б. Мазур существенно продвинулся вперед, доказав, что порядок всякой рациональной точка кручения равен 12 или не превосходит 10 (это уже в 1974 г. предполагал Э. Огг [12]). Тем самым была полностью выяснена структура группы ТЕ.

Имеется 15 возможностей: либо ТЕ — циклическая группа, порядок которой равен 12 или не превосходит 10, либо она есть произведение группы Z2 на циклическую группу порядка 2, 4, 6 или 8.

Выдающимся результатом Б. Мазура была завершена одна из глав теории эллиптических кривых, причем весьма неожиданно даже для некоторых специалистов, считавших, что над этой проблемой придется работать еще долгое время. Можно смело утверждать, что этот результат принадлежит к числу интереснейших математических результатов последних лет. Разумеется, в рамках настоящей лекции невозможно указать даже хотя бы идею метода доказательства Мазура. Да это и не входит в мою задачу.

Я хотел только попытаться пройти вместе с вами небольшую часть пути развития одной математической проблемы — от Пифагора через Диофанта и гипотезу Ферма к рациональным точкам эллиптических кривых — и показать, как в ходе исследования проблему видоизменяли, обобщали и снова конкретизировали, частично решали и возводили на ее основе новые теории. Пусть нематематики простят мне, что время от времени я вынужден был обращаться к математическим понятиям и формулам.

Литература

(Превосходные библиографии имеются в [4] и [17]. По проблеме Ферма полезно сравнить [5] и [15].)

[1] И. Г. Башмакова, Диофант и диофантовы уравнения. — М.: Наука, 1972.

[2] К. L. Biernatzki, Die Arithmetik der Chinesen, J. reine angew, Math. 52 (1856).

[3] B. J. Birch, H. P. F. Swinnerton-Dyer, Notes on elliptic curves. II, J. reine angew. Math. 218 (1965).

[4] I. W. S. Cassels, Diophantine equations with special reference to elliptic, J. London Math. Soc. 41 (1966).

[5] H. M. Edwards, Fermat's Last Theorem, Springer Graduate Texts in Mathematics, vol. 50, Springer-Verlag, New York — Heidelberg — Berlin, 1977. [Имеется перевод: Эдвардс Г. Последняя теорема Ферма. Генетическое введение в алгебраическую теорию чисел. — М.: Мир, 1980.]

[6] F. J. Grunewald, R. Zimmert, Über einige rationale elliptische Kurven mit freiem Rang ⩾ 8, J. reine angew. Math. 296 (1977).

[7] E. Lutz, Sur l'equation y2 = x3 — Ax — В dans les corps p-adiques, J. Math. 177 (1937).

[8] B. Mazur, Modular curves and the Eisenstein ideal, Publ. Math. IHES 47 (1977).

[9] L. I. Mordell, On the rational solutions of the indeterminant equations of the third and fourth degrees, Proc. Cambridge Phil Soc. 21 (1922).

[10] T. Nagell, Solution de quelques problèmes dans la théorie arithmétique des cubiques planes du premier genre, Vid. Akad. Skrifter Oslo 1 (1935), No. 1.

[11] A. Neron, Problèmes arithmétiques et géométriques rattachés à la notion de rang d'une courbe algébriques dans un corps, Bull. Soc. Math. France 80 (1952).

[12] A. P. Ogg, Diophantine equations and modular forms, Bull. Amer. Math. Soc. 81 (1975).

[13] D. E. Penney, C. Pomerance, Three elliptic curves with rank at least seven, Math. Comp. 29 (1975).

[14] H. Poincaré, Sur les propriétés arithmétiques des courbes algébriques, J. de Math. Pures et Appl., ser. 5, 7 (1901).

[15] P. Ribenboim, 13 Lectures on Fermat's Last Theorem, Springer-Verlag, New York — Heidelberg — Berlin, 1979.

[16] C. L. Siegel, Über einige Anwendungen Diophantischer Approximationen, Abh. Preuss. Akad. Wiss. Phys.-Math. Kl. 1 (1929).

[17] J. T. Tate, The arithmetic of elliptic curves, Invent. Math. 23 (1974).

[18] J. T. Tate, Rational Points on Elliptic Curves, Philips Lectures, Haverford College, 1961.

[19] R. Wachendorf, Über den Rang der elliptischen Kurve y2 = x3 — p3x Diplomarbeit, Bonn, 1974.

[20] A. Wiman, Über rationale Punkte auf Kurven dritter Ordnung vom Geschlecht Eins, Acta Math. 80 (1948).

Сведения по истории математики наряду с [1], [4], [5], [15], [17] можно найти в работах:

M. Cantor, Vorlesungen über Geschichte der Mathematik, 4 Bände, Leipzig, 1900—1908.

L. E. Dickson, History of the theory of numbers, Carnegie Institution, Washington, 1919, 1920, 1923.

D. I. Struik, Abriss der Geschichte der Mathematik, Vieweg, Braunschweig, 1976. [Имеется перевод: Стройк Д. Я. Краткий очерк истории математики. — М., Наука, 1978.]

В. L. van der Waerden, Die Pythagoreer, Artemis Verlag, 1979. [См. также: ван дер Варден Б. Л. Пробуждающаяся наука. — М.: Физматгиз, 1959. — Перев.]

Encyclopedic Dictionary of Mathematics, ed. by Math. Soc. Japan, MIT Press, Cambridge Mass. and London.

Енс Карстен Янцен

СВЯЗЬ МЕЖДУ ТЕОРИЕЙ ПРЕДСТАВЛЕНИЙ И КОМБИНАТОРИКОЙ

Я попытаюсь описать вам взаимосвязь двух областей математики — теории представлений и комбинаторики. Начнем со второй, как более простой. Специалисты по комбинаторике сначала делают с конечными множествами всё мыслимое и немыслимое, а затем спрашивают себя, сколькими способами это можно сделать. В качестве конечных множеств мы будем рассматривать множества вида {1, 2, 3, 4, 5, 6, 7, 8, 9}, т. е. множества {1, 2, ..., n}, где n — натуральное число.

Самое простое, что можно сотворить с данным множеством — это записать его элементы в другом порядке, скажем так:

σ: 3, 2, 5, 9, 1, 8, 7, 4, 6

или, в общем случае, σ(1), σ(2), ..., σ(n). Такие последовательности называются перестановками множества (1, 2, п}. Итак, первый комбинаторный вопрос: каково число всех возможных перестановок множества {1, 2, n}? Это — популярное упражнение на принцип математической индукции1). Ответом служит

1⋅2⋅...⋅n = n!

(так что при n = 9 имеется 362880 перестановок).

Можно задать еще несколько далеко ведущих вопросов, например: сколько элементов в самой длинной возрастающей подпоследовательности последовательности σ(1), σ(2), ..., σ(n)? Как найти такую подпоследовательность? В рассматриваемом случае при n = 9 указанная длина равна 3, а примерами возрастающих подпоследовательностей длины 3 являются 1, 4, 6; 2, 5, 9; 3, 5, 8 и многие другие. Напрашивается

1) См. первое подстрочное примечание на стр. 59. — Прим. перев.

и такой вопрос: каково количество N(n,r) перестановок множества {1, 2, ..., n}, для которых число элементов самой длинной возрастающей подпоследовательности равно г? Если рассмотреть все возможные перестановки, скажем, для n = 9 (а их, как уже было сказано, 362880), то получатся значения, указанные в табл. 10.

Таблица 10.

r

1

2

3

4

5

6

7

8

9

N(9, r)

1

4 861

89 497

167 449

83 029

16 465

1513

64

1

Общий ответ на перечисленные вопросы нашел в 1959—1960 гг. К. Шенстед. Для этого он поставил в соответствие каждой перестановке три других объекта комбинаторики, а именно одно разбиение и две канонические таблицы. Объясним эти понятия. Разбиением целого положительного числа n называется всякая невозрастающая последовательность λ = (λ1, λ2, ..., λs) целых положительных чисел, сумма которых равна п:

Например, (3, 3, 2, 1)—одно из разбиений числа 9, всего же их 30, а у числа 200 разбиений уже 3972 999 029 388.

Далее, разбиению λ = (λ1, λ2, ..., λs) поставим в соответствие так называемую диаграмму Юнга (или просто диаграмму) типа λ: поместим в первой строке λ1 клеток, во второй строке (под первой) λ2 клеток, в третьей строке λ3 клеток и т. д. При этом первая клетка должна стоять под первой, вторая — под второй и т. д. Диаграмма для λ = (3, 3, 2, 1) показана на рис. 26.

Рис. 26.

Рис. 27.

Если в каждую клетку диаграммы типа λ вписать по одному числу так, чтобы в каждой строке слева направо и в каждом столбце сверху вниз числа строго возрастали, то заполненная таким образом диаграмма называется таблицей (типа λ). Например, на рис. 27 приведены три таблицы типа (3,2,2). Таблица типа λ, где λ — разбиение числа n, называется канонической, если в ней содержатся все числа от 1 до n. Из трех таблиц на рис. 27 только средняя является канонической; напротив, на рис. 28 обе таблицы — канонические (типа (3, 3, 2, 1)); как мы вскоре увидим, это именно те две таблицы, которые Шенстед ставит в соответствие перестановке а, указанной в самом начале в качестве примера.

Построение канонических таблиц Шенстед проводит поэтапно: каждому из последовательно увеличивающихся «начальных отрезков» последовательности (в рассматриваемом примере каждому из «отрезков» 3; 3, 2; 3, 2, 5; 3, 2, 5, 9; ...) ставится в соответствие таблица по правилу, указывающему, как из таблицы для одного начального отрезка получить таблицу для следующего. Процесс начинается с таблицы типа (1), в единственной клетке которой пишется первое число последовательности. Само правило объясним на примере. Пусть начальному отрезку 3, 2, 5, 9, 1, 8, 7 уже поставлена в соответствие некоторая таблица (рис. 29). Тогда таблица для отрезка 3, 2, 5, 9, 1, 8, 7, 4 получается так: берем новое число (т. е. 4) и рассматриваем первую строку таблицы. Если оно больше всех чисел, стоящих в строке, то добавляем в ее конце еще одну клетку, вписываем туда взятое число, и таблица готова. В противном случае (как

Рис. 28. Рис. 29.

у нас, из-за наличия 5 и 7) находим в первой строке наименьшее число, превосходящее новое (т. е. 5), и заменяем его на это новое (т. е. на 4). Теперь с «вынутым» из первой строки числом m (т.е., в нашем случае, 5) переходим ко второй строке; если все числа в ней меньше m, то удлиняем ее на одну клетку, вписываем туда m, и таблица готова. В противном случае берем наименьшее число второй строки, большее m (в нашем случае 8), заменяем его на m (на 5) и с изъятым из второй строки числом переходим к третьей (рис. 30). Процесс продолжается до тех пор, пока, наконец, к какой-нибудь строке не будет добавлена клетка или же пока не будет изъято число из последней строки (в рассматриваемом примере 9). В этом случае к таблице добавляется новая строка, состоящая из одной-единственной клетки в первом столбце, куда и вписывается число, изгнанное из последней строки старой таблицы. На рис. 31

Рис. 30.

Рис. 31.

приведены таблицы, построенные таким образом одна за другой для последовательности 3,2,5,9,1,8,7,4, 6.

Нетрудно заметить, что при указанной процедуре каждый раз действительно возникает таблица, т. е. что длина строк сверху вниз не увеличивается, а в каждом столбце сверху вниз и в каждой строке слева направо числа возрастают. В конце концов все числа 1, 2, n будут исчерпаны и мы получим каноническую таблицу, которую обозначим A(σ). При этом автоматически возникает еще одна каноническая таблица В(σ) того же типа, что и A(σ). А именно, берем диаграмму, соответствующую таблице A(σ), и в каждую клетку вписываем номер того шага, на котором эта клетка была добавлена при построении A(σ). Таблица B(σ) для рассматриваемого примера изображена на рис. 32.

Теперь можно ответить на первый из поставленных вопросов: число элементов в самой длинной возрастающей подпоследовательности последовательности а в точности равно числу клеток в первой строке таблицы A(σ). Сама такая подпоследовательность (длину которой будем, как и прежде, обозначать через г) может быть выписана по следующему правилу: из таблиц, соответствующих различным начальным отрезкам σ (рис. 31), выбираем любую из уже имеющих в первой строке г клеток (в нашем случае, скажем, предпоследнюю) и через аr обозначаем число, стоящее в r-й клетке этой первой строки (у нас аr = 7). Затем возвращаемся к таблице, построенной до вписывания аr (в нашем случае к шестой), и полагаем ar-1 равным числу, стоящему в ней на (r—1)-м месте

Рис. 32. Рис. 33.

первой строки. Далее берем таблицу, имевшуюся до вписывания ar-1 (вторую), и (r — 2)-е число ее первой строки называем аr-2. Продолжая таким образом, получаем возрастающую подпоследовательность a1, a2, ..., ar последовательности σ (а именно 2, 5, 7). Легко показать, что более длинной возрастающей подпоследовательности не существует.

В рассматриваемом примере первая строка таблицы A(σ) (т. е. 1, 4, 6) сама представляет собой возрастающую подпоследовательность а. Однако это случайность; если взять, скажем, последовательность

то получится таблица, приведенная на рис. 33, и 1, 2, 3, 9 не будет возрастающей подпоследовательностью σ* (хотя ею будет 4, 7, 8, 9). Последовательность σ* есть σ, записанная в обратном порядке. Разумеется, такую операцию можно проделать с любой перестановкой множества (1, 2, ..., n}, и Шенстед доказал, что A(σ*) получается из A (а) «отражением относительно диагонали», т. е. первый, второй, третий, ... столбцы А(σ) становятся соответственно первой, второй, третьей, ... строками A(σ*). Пример на рис. 33 иллюстрирует этот результат. Поэтому, зная A(σ), можно найти число элементов и самой длинной убывающей подпоследовательности перестановки σ — оно равно длине первого столбца таблицы A(σ). Как показал К. Грин, можно дать комбинаторную интерпретацию длине любой строки и любого столбца A(σ).

Научившись для любой перестановки определять самую длинную возрастающую подпоследовательность, перейдем к следующему вопросу: каково число N(n,r) перестановок множества (1, 2, ..., п}, у которых такая подпоследовательность имеет длину r? Здесь большую роль будет играть вторая каноническая таблица В(σ). Прежде всего, σ однозначно определяется упорядоченной парой A(σ), В(σ). Так, в рассматриваемом примере таблица В(σ) показывает, что на последнем шаге построения А(σ) вторая строка увеличилась на одну клетку. Тем самым известен вид предпоследней таблицы, и мы также знаем, что вторая строка, за исключением одной клетки,

и все последующие строки у предпоследней и последней таблиц совпадают. Кроме того, мы знаем, что на последнем шаге из первой строки было вытеснено число 7, и притом вытеснено наибольшим числом, не превосходящим 7, содержащимся в первой строке последней таблицы, т. е. 6-ю. Значит, 6 — последнее число перестановки, и первая строка предпоследней таблицы получается из первой строки последней таблицы заменой 6 на 7. Таким образом, предпоследняя таблица определена полностью, и процесс можно аналогично продолжить.

С помощью такого рассуждения устанавливается не только единственность, но и существование о. Итак, если λ — разбиение числа n и A, В — канонические таблицы типа λ, то имеется одна и только одна перестановка σ множества (1, 2, ..., n}, для которой A(σ) = A, B(σ) = В. Таким образом, существует взаимно-однозначное соответствие между множеством Gn всех перестановок множества {1,2, ..., n} и множеством пар канонических таблиц одинакового типа λ, где λ пробегает все разбиения числа n.

Если для данного разбиения λ через Nλ, обозначить количество канонических таблиц типа λ, то Nλ2 будет равно числу пар таких таблиц. Поэтому ответ на поставленный вопрос можно сформулировать следующим образом: искомое число N(n,r) равно ΣNλ2, где суммирование ведется по всем разбиениям λ = (λ1, λ2, ...) числа n (λ1 ⩾ λ22 ⩾ ...), у которых λ1 = r.

От этой формулы было бы немного толку, если бы не имелось простого способа для вычисления Nλ. Но у Шенстеда была под рукой опубликованная в 1954 г. работа Дж. С. Фрэйма, Г. де Б. Робинсона и Р. М. Тролла, в которой дана очень простая формула для вычисления Nλ. А именно: каждой клетке диаграммы типа λ ставится в соответствие «уголок», состоящий из клеток той же строки, расположенных правее данной, клеток того же столбца, лежащих ниже данной, и ее самой. На рис. 34 слева заштрихован один такой уголок. Количество клеток в уголке называется его длиной. Таким образом, каждой клет-

ке диаграммы типа λ поставлен в соответствие уголок, а следовательно, и его длина. На том же рисунке справа приведены длины уголков для λ = (3, 3, 2, 1). Фрэйм, Робинсон и Тролл показали, что

Так, в рассматриваемом нами примере

К сожалению, Шенстед не знал о более ранней работе Г. де Б. Робинсона 1938 г. В ней уже был описан способ построения А(σ) и B(σ), и поэтому указанное выше взаимно-однозначное соответствие в настоящее время называется соответствием Робинсона—Шенстеда. Однако Робинсон интересовался вовсе не возрастающими и убывающими подпоследовательностями, а теорией представлений симметрических групп, и именно в связи с этой теорией и возник его интерес к числам Nλ.

Итак, пришло время перейти к теории представлений. Правда, теперь я должен предполагать, что вы знаете, что такое «группа», и знаете, что группу образует, к примеру, множество Gn всех перестановок множества (1, 2, .... n) (относительно операции (στ)(j) = σ(τ(j))) — это так называемая симметрическая группа — или же множество GLn(C) всех обратимых n X n-матриц (aij)1 ⩽ i, j ⩽ n с комплексными элементами (относительно матричного умножения). Таким образом, нам понадобятся сведения, сообщаемые студентам-математикам в первом семестре.

Под n-мерным (комплексным) представлением группы G понимается отображение, ставящее в соответствие каждому элементу g группы G некоторую

Рис. 34.

матрицу M (g) из GLn(C):

так, что при всех g и h имеет место равенство

В частности, М(1) является единичной nxn-матрицей (мы всегда считаем, что n > 0).

Простейшими примерами служат тождественное представление группы GLn(C), определяемое соотношением M(g) = g, и «тривиальное» n-мерное представление произвольной группы G, задаваемое равенством M(g) = M(1) для всех элементов g из G. Еще одним, также очень простым примером служит n-мерное представление симметрической группы Gn, ставящее в соответствие каждой перестановке σ матрицу M(σ), в которой на σ(i)-м месте i-го столбца (1 ⩽ i ⩽ n) стоит 1, а на всех остальных местах нули. Если комплексную nxn-матрицу интерпретировать как линейное отображение Сn на себя и через e1, e2, ..., en обозначить канонический базис Сn, то M(σ)(ei) — eσ(i). Определитель матрицы M(σ) называется сигнатурой перестановки а и обозначается через sign (σ). Отображение σ → sign (σ) является гомоморфизмом группы Gп в мультипликативную группу комплексных чисел, т. е. в GL1(C), и его можно поэтому рассматривать как одномерное представление Gn.

Важную информацию о представлении g → M (g) группы G несет его характер χm, т. е. комплекснозначная функция на G, определяемая формулой

В частности, размерность представления n = χM(1). В приведенном выше примере представления симмет-

рической группы χM(σ) равно количеству тех i в перестановке σ множества (1, 2, ..., n}, для которых σ(i) = i У тривиального n-мерного представления χM(g) = n при всех g.

Характер χM (а также и само представление) называется неприводимым, если не существует других характеров χ1, χ2 (необходимо являющихся характерами представлений меньшей размерности), для которых χM(g) = χ1(g) + χ2(g) при всех g из G. Ясно, что характеры одномерных представлений всегда неприводимы. Если χn — характер n-мерного тривиального представления группы G, то χn(g) = nχ1(g); поэтому χп неприводим лишь при n = 1. Характер описанного выше представления группы Gn при n > 1 не является неприводимым. Действительно, если опять рассматривать матрицу M(σ) как линейное преобразование Cn и перейти к базису e1 + e2 + ... + en, e1 — e2, e2 — e3, en-1 — en, то получится матрица вида

При этом σ → М'(σ) будет (n—1)-мерным представлением, и χm(σ) = χM'(σ) + χ1(o), где χ1 — характер одномерного тривиального представления. Здесь мы использовали тот факт, что при переходе от одного базиса к другому след не меняется. А вот характер χM' уже неприводим. То же относится и к характеру тождественного представления группы GLn(C). (Мы допускаем лишь такие представления GLn(C), у которых матричные коэффициенты mij(g) являются аналитическими функциями от элементов gkl матрицы g.)

Одна из основных задач теории представлений — нахождение всех неприводимых характеров (представлений) заданной группы. (Все прочие характеры

получаются как суммы неприводимых.) Первыми нетривиальными случаями, для которых эту задачу удалось решить, были — в начале этого столетия — группы Gn и GLn(C).

Г. Фробениус доказал, что неприводимые характеры группы Gn находятся во взаимно-однозначном соответствии с разбиениями λ числа n. Если обозначить через χλ характер, соответствующий λ, то размерность соответствующего представления равна χλ(1) = Nλ. Отсюда ввиду соответствия Робинсона — Шенстеда вытекает, что

т. е. порядок группы Gn равен сумме квадратов размерностей неприводимых представлений. Это — общая теорема для конечных групп. Для случая группы Gnп ее элементарное комбинаторное доказательство получается с помощью методов, описанных в первой части нашего рассказа. (При отображении разбиению λ = (n) соответствует, например, характер одномерного тривиального разбиения, a χ(n-1, 1) равно упомянутому выше χM'.)

Фактически Фробениус получил более сильный результат. С каждым разбиением λ = (λ1, λ2, ..., λs) (λ1 ⩾ λ2 ⩾ ... ⩾ λs) он связал две функции от m > n переменных Х1, Х2, ..., Хm

(предполагается, что λj = 0 при j > s). Функции Sλ и Uλ являются симметрическими многочленами от Х1, Х2, ..., Хm (для Uλ, это следует из одного тожде-

ства Якоби и Труди) и связаны одна с другой равенством

(1)

Фробениус указал для каждой перестановки σ∈Gn такое разбиение μ, что χλ(σ) = χμλ при всех λ (Надо записать σ в виде произведения циклов, не имеющих общих элементов; если μ1 ⩾ μ2 ⩾ ... ⩾ μs — длины этих циклов, то μ = (μ1, μ2, ..., μs)—искомое разбиение.)

Соотношение (1) можно рассматривать как систему уравнений, которую следует решить. При μ = (n) решение легко находится:

Очевидно, что равно произведению S(μj) Поэтому для определения в общем случае полезно иметь формулу для произведения Uλ, а именно равенство вида

(2)

(если λ — разбиение числа n1, a μ —разбиение n2, то суммирование ведется по всем разбиениям v числа n1 + n2).

Систему уравнений (2) желательно уметь решать и по другой причине. И. Шур в 1901 г. показал, что если λ = (λ1, λ2, ..., λs)—разбиение с s ⩽ m, то, сопоставив каждой матрице g число Uλ(ξ1, ξ2, ... , ξm), где ξ1, ξ2, ..., ξm — собственные значения g, мы получим неприводимый характер группы GLm(C). Кроме того, указанными функциями по существу исчерпываются все неприводимые характеры группы GLm(C). Поэтому числа cνλμ можно трактовать как кратности в тензорных произведениях представлений GLm(C). Таким образом, сνλμ должны быть целыми неотрицательными.

Числа сνλμ вызывают интерес еще и потому, что они описывают умножение в кольце когомологий многообразия Грассмана.

Перейдем теперь к определению сνλμ, Прежде всего, можно доказать, что νλμ отлично от нуля, лишь если λ1 ⩽ ν1, λ2 ⩽ ν2, .... Пусть эти условия выполнены. Тогда можно ввести понятие «косой» канонической таблицы типа ν/λ. Такие таблицы строятся следующим образом. В диаграмме типа ν отбрасываем первые λ1 клеток первой строки, первые λ2 клеток второй строки и т. д. (см. рис. 35, где ν = (5, 4, 2, 2), λ = (3, 2, 1)). Вписав в клетки этой диаграммы числа от 1 до (ν1 — λ1) + (ν2— λ2) + ... так, чтобы в каждом столбце сверху вниз и в каждой строке слева направо числа возрастали, получим косую каноническую таблицу типа v/λ (для указанных выше ν и λ пример такой таблицы приведен на рис. 36).

Косую каноническую таблицу можно преобразовать в обычную. Для этого выберем в диаграмме типа X какую-нибудь клетку, стоящую на последнем месте как в своей строке, так и в своем столбце. В диаграмме типа ν/λ соответствующее место «вакантно» (скажем, на рис. 36 второе место второй строки). Возьмем теперь в таблице типа ν/λ ту из двух клеток, находящихся непосредственно справа или непосредственно снизу от рассматриваемого вакантного места, в которой записано меньшее число (а если такая клетка только одна, то ее саму), и сдвинем ее на вакантное место (см. рис. 37, где вакантные места обозначены жирной точкой). При этом получится новое

Рис. 35.

Рис. 36.

вакантное место. Если правее и ниже него ничего нет, то первый этап закончен. В противном случае берем клетку непосредственно правее или непосредственно ниже, содержащую меньшее число (или единственную), и сдвигаем ее на вакантное место. Процесс продолжаем до тех пор, пока правее и ниже возникающего вакантного места не останется больше клеток. В результате возникает новая косая каноническая таблица (для рассматриваемого примера — типа (5, 4, 2, 1)/(3,1,1); см. рис. 37). Описанную процедуру можно повторять, пока не получится обычная каноническая таблица. Результат не зависит от выбора начального вакантного места. Продолжение процесса для нашего примера показано на рис. 38, Так вот, справедливо утверждение: число косых канонических таблиц типа ν/λ, которые описанным способом

Рис. 38.

Рис. 37.

переводятся в заданную каноническую таблицу типа μ, равно cνλμ.

В формулировке этого утверждения я следую М. П. Шютценберже. А само утверждение восходит к Д. Э. Литтлвуду и Э. Р. Ричардсону, которые указали в 1934 г. правило, позволяющее (в нашей терминологии) явно описать косые канонические таблицы, преобразующиеся в «тривиальную» каноническую таблицу типа у которой в первой строке записаны числа 1, 2, ..., μ1, во второй — числа μ1 + 1, μ +2, ... ..., μ + μ2 и т. д. В их работе правило было дано без доказательства. Впервые его привел в 1938 г. Г. де Б. Робинсон в той же статье, где описан и рассмотренный в начале экскурсии способ построения таблицы А(σ). Последний можно теперь рассматривать как частный случай изложенной процедуры: сопоставив перестановке σ косую каноническую таблицу типа (n, n— 1, 1)/(n — 1, n — 2, 1) (рис. 39) и используя только что указанный метод, получим А(σ).

Упомянутые до сих пор связи комбинаторики с теорией представлений заключались в том, что комбинаторные результаты можно использовать в теории пред-

Рис. 39.

ставлений, а последняя дает импульс для комбинаторных исследований, причем подчас специалисты по теории представлений находят решение комбинаторных вопросов (пример — формула для Nλ). В последние годы была обнаружена новая связь между этими областями: с помощью теории представлений удалось заново доказать несколько старых комбинаторных формул и найти большое число новых.

Обратимся еще раз к функциям Как показал Шур, они позволяют определить по существу все неприводимые характеры группы GLm(C). При этом разбиение λ = (0) отвечает тривиальному одномерному представлению, характер которого тождественно равен 1. Поэтому U(0) = 1 и

Но это не что иное, как формула для определителя Вандермонда, которую мы тем самым заново доказали бы с помощью теории представлений, если бы эта формула не использовалась существенным образом в работе Шура.

Вместо группы GLm(C) или ее алгебры Ли gl(m, С) (для теории представлений разница невелика) можно рассмотреть целый ряд бесконечномерных алгебр Ли (эвклидовы алгебры Каца — Муди, которые являются алгебрами Ли над С и по существу устроены как g®С[Х, X-1], где g — некоторая простая конечномерная алгебра Ли над С, а X — переменная). Для каждой такой алгебры Ли получается своя формула для характеров, которая, как и в случае GLm(C), дает соответствующее тождество уже для нескольких переменных (такие тождества сперва были найдены И. Г. Макдональдом несколько по-иному, а затем таким вот образом интерпретированы Кацем и Муди).

Подставляя вместо переменных подходящие многочлены от одной переменной X, можно получать

различные тождества для функции Эйлера

Эйлер исследовал эту функцию в связи с найденной им формулой

где р(n)—количество разбиений числа n. Комбинируя эту формулу с первым из указанных ниже тождеств, можно получить итерационную формулу для р(n), с помощью которой майор П. Мак-Мэйон вычислил значения р(n) для n ⩽ 200. Из его (опубликованной Харди и Рамануджаном) таблицы и заимствовано указанное ранее значение р(200).

С помощью упомянутых выше подстановок получаются (в так называемом случае «первого порядка») следующие тождества для φ(X) :

(Эйлер),

(Якоби),

(Гаусс),

(Гаусс),

(Гордон),

(Гордон),

Суммирование везде ведется по всем целым k; в двух последних формулах (n/3) это символ Лежандра1), т. е. —1, 0 или 1, смотря по тому, с чем сравнимо число n по модулю 3. В скобках справа приведены фамилии математиков, впервые обнаруживших формулу. Подстановку, приводящую к тождеству Якоби, указал Макдональд, а подстановку, с помощью которой получается первое тождество Гаусса, — Дж. Леповски. Подстановки для всех остальных случаев нашел В. Г. Кац.

Я надеюсь, эти примеры убедили вас, что теория представлений может подарить комбинаторике не только проблемы, но и интересные результаты.

Литература

ПО КОМБИНАТОРИКЕ:

С. Schensted, Longest increasing and decreasing sequences, Canad. J. Math. 13 (1961), 179—192.

M. P. Schützenberger, Quelques remarques sur une construction de Schensted, Math. Scand. 12 (1963), 117—128.

C. Greene, An extension of Schensted's theorem, Advances in Math. 14 (1974), 254—265.

Combinatoire et Representation du Groupe Symétrique (ed. D. Foata), Springer, Lecture Notes in Math. 579, Berlin — Heidelberg—New York, 1977.

ПО ТЕОРИИ ПРЕДСТАВЛЕНИЙ:

G. Frobenius, Uber die Charaktere der symmetrischen Gruppe, Sitzungsber. Preuß. Akad. Berlin 1900, стр. 516 и далее. [См. также: Фробениус Г. Теория характеров и представлений групп. — Харьков: 1937. — Перев.]

I. Schur, Uber eine Klasse von Matrices, die sich einer gegebenen Matrix zuordnen lassen, Diss. Berlin, 1901.

D. E. Littlewood, A. R. Richardson, Group characters and algebra Phil. Trans. Roy. Soc. A, 233 (1934), 99—141.

G. de B. Robinson, On the representations of the symmetric group, Amer. J. Math. 60 (1938), 745—760.

H. Weyl, The Classical Groups, Princeton, 1946. [Имеется перевод: Вейль Г. Классические группы, их инварианты и представления. — М.: ИЛ, 1947.]

1) См. Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — Прим. перев.

D. E. Littlewood, The Theory of Group Characters and Matrix Representations of Groups, 2nd ed., Oxford, 1950.

J. S. Frame, G. de В. Robinson, R. M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316—324.

G. D. James, The Representation Theory of the Symmetric Groups, Springer, Lecture Notes n Math. 682, Berlin — Heidelberg — New York, 1978.

ПО ТОЖДЕСТВАМ ДЛЯ φ(x):

L. Euler, Observationes analyticae variae de combinationibus, 1741—1743; Commentarii academiae scientiarum Petropolitanae 13 (1751), 64—93 ( = Opera Omnia, Serie 1, Band 2, Leipzig—Berlin, 1915, 163—193).

L. Euler, Demonstratio theorematis circa ordinem in summis divisorum observatum, 1754—1755, Novi commentarii academiae scientiarum Petropolitanae 5 (1760), 75—83 ( = Opera Omnia, там же, 309—398).

С. F. Gauss, Summatio quarundam serierum singularum, 1808, Commentationes societatis regiae scientiarum Gottingensis recentiores 1, 1811 ( = Werke, Band 2, Göttingen, 1876, 9—45).

C. F. Gauss, Zur Theorie der transscendenten Funktionen gehörig, по-видимому около 1808; впервые опубликовано в: Werke, Band 3, Göttingen, 1876, 436—445.

С. G. J. Jacobi, Fundamenta nova theoriae functionum ellipticarum, Regensburg, 1829 ( = Ges. Werke, Band 1, Berlin, 1881, 49—239).

P. Bachmann, Die analytische Zahlentheorie, Leipzig, 1894.

G. H. Hardy, S. Ramanujanf Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. (2) 17 (1918), 75—115.

G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford, 1979.

B. Gordon, A combinatorial generalization of the Rogers-Ramanujan identities, Amer. J. Math. 83 (1961), 393—399.

G. E. Andrews, The Theory of Partitions, Reading., Mass., 1976. [Имеется перевод: Эндрюс Г. Теория разбиений. — М.: Наука, 1982.]

ПО ТОЖДЕСТВАМ МАКДОНАЛЬДА:

I. G. Macdonald, Affine root systems and Dedekind's η-function, Invent. Math. 15 (1972), 91—143.

В. Г. Кац, Бесконечномерные алгебры Ли и η-функция Дедекинда. — Функциональный анализ и его прилож., 1974, 8, с. 68—70.

R. V. Moody, Macdonald identities and Euclidean Lie algebras, Proc. Amer. Math. Soc. 48 (1975), 43—52.

J. Lepowsky, Macdonald-type identities, Advances in Math. 27 (1978), 230—234.

J. Lepowsky, Generalized Verma modules, loop space cohomology and Macdonald-type identities, Ann. Scient. Ec. Norm. Sup. (4) 12 (1979), 169—234.

В. Г. Кац, Infinite dimensional algebras, Dedekind's η-function, classical Möbius function and the very strange formula, Advances in Math. 30 (1978), 85—136.

ИМЕННОЙ УКАЗАТЕЛЬ

Абелер (J. Abeler) 13

Абель (N. Н. Abel) 97

Адамар (J. Hadamard) 52

Азулей (Abraham Azulai) 31

Аланен (Alanen) 23

аль-Банна см. ибн аль-Банна аль-Каши 32

аль-Маджрити 14, 18, 33

аль-Мутатид 16

Артюхов М. М. 38

Башмакова И. Г. 90, 94

Бейз (С. Bays) 70, 71

Беккер (О. Becker) 32

Бёрджесс (D. A. Burgess) 28

Бёрч (В. J. Birch) 97, 100

Бландон (W. J. Blandon) 53

Боро (W. Borho) 8, 10, 11, 23

Браун (Brown) 23

Брэтли (Bratley) 23

Буль (J. Buhl) 35

Бухштаб А. А. 36, 66, 78, 79, 122

Вагштафф (S. S. Wagstaff) 92

Валле-Пуссен (С. de la Vallée Poussin) 52

Вандивер (U. S. Vandiver) 92

Вахендорф (R. Wachendorf) 100

Вейль (A. Weil) 27, 97

Виленкин Н. Я. 35, 58

Виман (A. Wiman) 98

Витрувий 71

Водарх (В. А. Wodarch) 34, 35

Вольфарт (J. Wolfart) 37

Вольфскель (P. Wolfskehl) 91

Вульф (Wulf) 23

Выгодский М. Я. 32

Гарднер (M. Gardner) 36

Гарсиа (Garcia) 23

Гаусс (С. F. Gauß) 8, 9, 36, 40, 41, 48—55, 67, 79, 121

Гиллис (Gillies) 46

Гильберт (D. Hilbert) 75

Гольдбах (С. Goldbach) 35

Гордон (В. Gordon) 121

Грам (J.-P. Gram) 69

Грин (С. Greene) 110

Грюневальд (F. J. Grunewald) 99, 100

Декарт (R. Descartes) 14, 16, 18—20, 23, 33, 34

Депман И. Я. 13, 32

Джоунз (М. F. Jones) 53

Диксон (L. Е. Dickson) 14, 23, 31, 33—36

Диофант 9, 73, 81, 88, 90, 91, 94, 96, 102

Дирихле (P. G. L. Dirichlet) 27

Дэвенпорт (W. Н. Davenport) 81

Дэвид (David) 23

Жерардэн (Gerardin) 23, 35

Зеельхофф (Seelhoff) 23

Зигель (С. L. Siegel) 93

ибн аль-Банна 14, 17, 18, 23, 32

ибн Хальдун 14, 18

Калужнин А. А. 43

Кампс (К. Н. Kamps) 36, 38

Канольд (H.-J. Kanold) 24, 38

Кантор (М. Cantor) 31, 33

Кац В. Г. 36, 120

Коблиц (N. I. Koblitz) 42

Конвей (Conway) 69

Коэн (Cohen) 23, 67

Крафт (Н. Kraft) 9, 10

Куммер (Е. Kummer) 92

Курош А. Г. 42

Кутбэддин Ширази 32

Лагранж (С. Lagrange) 83

Ламбек (I. Lambek) 77, 81

Ламе (G. Lamé) 92

Ландау (Е. Landau) 85

Леви (В. Levi) 77

Лежандр (A. M. Legendre) 8, 14, 20, 22, 23, 35, 36, 49—52, 55, 92

Ле Лассёр (Le Lasseur) 35

Леман (Е. Lehman) 67

Лемер Д. (D. Н. Lehmer) 28, 46, 70, 71, 92

Лемер Э. (Е. Lehmer) 92

Ленг (S. Lang) 42

Леповски (J. Lepowsky) 122

Ли (Е. J. Lee) 14, 23, 24, 31, 32, 34, 35, 38

Литтлвуд Д. (D. Е. Littlewood) 119

Литтлвуд Дж. (J. Е. Littlewood) 57

Лутц (Е. Lutz) 101

Лэл (M. Lal) 53

Люка (Е. Lucas) 22, 28, 36, 37, 45, 46, 64

Мазур (В. Mazur) 9, 98, 102

Макдональд (I. G. Macdonald) 31, 36, 120, 122

Мак-Карти (Р. J. McCarthy) 36, 38

Мак-Кей (McKay) 23

Мак-Мэйон (P. A. MacMahon) 121

Мангольдт (Mangoldt) 69

Мезирьяк (С. G. de Bachet de Meziriac) 91

Мейхью (Mayhew) 66

Мерсенн (M. Mersenne) 18, 33, 65

Мертенс (S. Mertens) 35, 67

Миллер (G. Miller) 28, 37, 44

Миньотт (M. Mignotte) 37

Мозер (L. Moser) 77, 81

Морделл (L. I. Mordell) 9, 93, 97

Муди (R. V. Moody) 120

Мэдэчи (J. S. Madachy) 24, 31, 32, 34, 35, 38

Мэйсон (Mason) 23

Нагелль (T. Nagell) 101

Наката (К. Nakata) 100

Наксхон (Rau Nachshon) 32

Небген (Е. Nebgen) 23, 31

Нерон (A. Neron) 99

Никкел (Nickel) 36

Никомах 14

Нолл (Noll) 36

Огг (А. Р. Ogg) 97, 102

Оре (Ore) 23

Паганини (Paganini) 23

Паскаль (Е. Pascal) 33

Пенни (D. Е. Penney) 99

Пифагор 14—16, 18, 23, 24, 31, 87, 102

Платон 72

Померанс (С. Pomerance) 38, 99

Престет (Prestet) 34

Пуанкаре (H. Poincaré) 96, 98

Пуле (P. Poulet) 14, 22, 23

Райт (Е. М. Wright) 37

Рамануджан (S. Ramanujan) 66, 121

Рекков (R. Reckow) 23, 31

Ризель (Н. Riesel) 35, 46

Риман (В. Riemann) 8, 10, 27, 28, 37, 51, 52, 55, 58, 60, 68

Ричардсон (A. R. Richardson) 119

Роббинс (N. Robbins) 36

Робинсон (G. de В. Robinson) 46, 111, 112, 119

Рольф (Rolf) 23

Рольфс (J. Rohlfs) 8, 10, 72

Сабит 14, 16, 18, 28, 32

Сантало (L. A. Santalo) 92

Селфридж (Selfridge) 46

Скриба (Ch. J. Scriba) 35

Скьюз (S. Skewes) 57, 67

Словинский (D. Slowinski) 36

Соминский И. С. 59

Стемпл (Stemple) 23

Суиннертон-Дайер (Н. Р. F. Swinnerton-Dyer) 97, 100

Суисси (M. Souissi) 17, 32

Таккермэн (В. Tuckerman) 46

те Риле (H. J. J. te Riele) 11, 14, 23, 29, 31

Титчмарш (Е. С. Titchmarsh) 52

Тролл (R. M. Thrall) 111, 112

Труди (Trudi) 116

Тэйт (J. Tate) 97

Таннери (P. Tannery) 32

Уилд (R. E. Wild) 81

Уилер (Wheeler) 47

Уильяме (Н. С. Williams) 37

Ферма (P. Fermat) 14, 16—19, 32, 33, 81, 83, 91, 92, 102

Феррье (Ferner) 46

Фишер (В. Fischer) 22

фон Шотен (von Schooten) 34

Фробениус (G. Frobenius) 115, 116

Фрэйм (J. S. Frame) 111,112

Хадсон (R. Hudson) 70, 71

Хаммурапи 87

Харди (G. H. Hardi) 37, 57, 121

Хейджис (P. Hagis) 36, 38

Хеллингуэрфф (Hellingwerff) 34

Хирцебрух (F. Hirzebruch) 5, 6

Хоффманн (H. Hoffmann) 23, 31

Хульч (F. Hultsch) 32

Хурвитц (Hurwitz) 46

Цагир (D. Zagier) 8, 10, 22, 36, 42

Циммерт (R. Zimmert) 99, 100

Чебышев П. Л. 14, 20, 22, 23, 58, 67

Чжоу-Гун 88

Шан Гао 88

Шенстед (С. Schensted) 106, 107, 110, 111

Шёнхаге (A. Schönhage) 28

Штайншнайдер (М. Steinschneider) 33

Штрассен (V. Strassen) 28

Шур (I. Schur) 116, 120

Шэнкс (D. Shanks) 27, 37

Шютценберже (М. Р. Schützenberger) 119

Эвклид 13, 14, 16, 20,21,32,64

Эдвардс (Н. М. Edwards) 91

Эйлер (L. Euler) 8, 9, 14, 19— 25, 28—31, 34—36, 65, 92, 97, 121

Энке (J. F. Enke) 49

Эрдёш (Р. Erdös) 24, 38

Эскотт (Е. В. Escott) 14, 23, 24

Яглом А. М. 58

Яглом И. М. 58

Якоби (С. G. J. Jacobi) 9, 10, 30, 31, 36, 82, 83, 97, 116, 121

Ямвлих 14, 15, 32

Янцен (J. С. Jantzen) 9, 10, 36, 105

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

абелево многообразие 108

ассоциативность 99

Бернулли числа 66

Вандермонда определитель 120

Вейерштрасса каноническая форма 98

Гаусса тождества 121

Гордона тождества 121

группа коммутативная 99

дзета-функция 51, 58, 86

диаграмма 106

диофантово уравнение 21

дискриминант кривой 101

дружественные числа 14

закон распределения простых чисел 48

избыточное число 12

индукция 59

интегральный логарифм 50

каноническая таблица 107

— — косая 117

касательных метод 96

Каца — Муди эвклидова алгебра 120

квадрика 94

коммутативность 98

кручения группа 99

— точка 100

Лежандра символ 121

логарифмическая сумма 50

Мерсенна число 65

Мёбиуса функция 78

Морделла гипотеза 93

— теорема 97, 99

Морделла — Вейля теорема 97

недостаточное число 12

нейтральный элемент 98

несобственная точка 96

обратный элемент 98

перестановка 105

Пифагора пара 15

— теорема 87

пифагорова тройка 72, 88

— — квазипростейшая 73

— — простейшая 73, 88

порядок точки кручения 100

представление группы 112

— неприводимое 114

— тождественное 113

— тривиальное 113

простое число 42—43

псевдопростое число 29

разбиение натурального числа 35, 106

ранг эллиптической кривой 99

решётка 76

Римана гипотеза 61

— формула 61

Робинсона — Шенстеда соответствие 112

Сабита правило 25—27, 34

— теорема 16

секущих метод 94

сигнатура перестановки 113

симметрическая группа 112

собственный делитель 11

совершенное число 12

тор 83

тэта-функция 30, 82

Ферма большая теорема 91

— кривая 93

— малая теорема 19

Фурье ряд 84

характер 113

— неприводимый 114

целая часть 43

частичная сумма 57

Эвклида теорема 14

Эйлера рекуррентная формула для суммы делителей 30

— тождество 30, 121

— функция 121

эллиптическая кривая 97

— функция 30

эллиптический итеграл 91

Эратосфена решето 36

эта-фукция 30

Юнга диаграмма 106

Якоби тождество 121

формула для тэта-функций 30—31

СОДЕРЖАНИЕ

От издательства..................5

Ф. Хирцебрух

Предисловие...................6

Вступление .................... 7

Вальтер Боро

Дружественные числа. Двухтысячелетняя история одной арифметической задачи...............11

Дон Цагир

Первые 50 миллионов простых чисел..........42

Юрген Рольфс

О суммах двух квадратов............. 72

Ханспетер Крафт

Алгебраические кривые и диофантовы уравнения.....87

Енс Карстен Янцен

Связь теории представлений с комбинаторикой......105

Именной указатель................124

Предметный указатель .............127

Вальтер Боро, Дон Цагир, Юрген Рольфс, Ханспетер Крафт, Енс Карстен Янцен

«ЖИВЫЕ ЧИСЛА»

Старший научный редактор В. И. Авербух. Мл. научный редактор Н. С. Полякова. Художник А. В. Шипов. Художественный редактор В. И. Шаповалов. Технический редактор Л. В. Рыбалко. Корректор Л. В. Байкова.

ИБ № 4045

Сдано в набор 26.12.84. Подписано к печати 17.09.85. Формат 84×108/82. Бумага кн.-журнальная. Печать высокая. Гарнитура литературная. Объем 2,00 бум. л. Усл. печ. л.6,72. Усл. кр,«отт.7,03. Уч.-изд. л. 6,17. Изд. № 1/3421, Тираж 50 000 экз. Зак. 471. Цена 30 коп.

ИЗДАТЕЛЬСТВО МИР

129820. ГСП, Москва, И-110, 1-й Рижский пер., 2.

Ленинградская типография № 2 головное предприятие ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли, 198052, г. Ленинград, Л-52, Измайловский проспект, 29.

30 к.

Настоящая книга предлагает читателю совершить пять небольших экскурсий в богатый и разнообразный мир чисел. Каждая из экскурсий начинается «внизу», в долине, неподалеку от школы, а заканчивается уже в местах, требующих некоторой альпинистской подготовки, чтобы и более опытным участникам похода не было скучно. Но ко всем главным возвышенностям, с которых открываются виды, путешественники будут доставлены по канатной дороге и тем избавлены от тяжкого труда подъема — доказательств.