О раскрытии скобок, об Эйлере, Гауссе, Макдональде и об упущенных возможностях

Д. Фукс

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

(a + b)(a – b) = a2 – b2,

(1 – a)(1 + a + ... + an ) = 1 – an+1.

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

1. Тождество Эйлера

В середине XVIII века – дело было в 1748 году или несколькими годами раньше – Леонард Эйлер заинтересовался коэффициентами многочлена

φn(x) = (1 – x)(1 – x2)(1 – x3)...(1 – xn).

Он раскрыл скобки в произведении – и получил поразительный результат. Проделаем эту выкладку и мы:

Многоточия обозначают части многочленов φn(x), содержащие x в степенях, больших 10 (выписать эти многочлены полностью не позволяет формат журнала: многочлен φ10(x), например, имеет степень 55).

Начнём с очевидного, но важного наблюдения: коэффициенты многочлена φn(x) с ростом n «стабилизируются», то есть каждый из них начиная с некоторого n не меняется. Это легко объяснить: переход от φn–1(x) к φn(x), состоящий в умножении на 1 – xn, не оказывает никакого воздействия на коэффициенты при 1, x, ..., xn–1, так что при n > k коэффициент при xk в многочлене φn(x) от n не зависит. (Например, вычисленная часть многочлена φ10(x) не изменится, если вместо φ10 взять φ11, φ12 и т.д.) Ввиду этого мы можем говорить о «бесконечном произведении»

φ(x) = (1 – x)(1 – x2 )(1 – x3 )(1 – x4 )...,

понимая под этим, конечно, не многочлен, а степенной ряд, то есть выражение вида

a0 + a1x + a2x2 + a3x3 + a4x4 + ...,

где a0, a1, a2, a3, a4... – числа; в нашем случае a0, a1, a2, a3, a4 – стабилизирующиеся коэффициенты. Наше вычисление показывает, что

φ(x) называется функцией Эйлера.

Слово «функция» здесь употреблено не случайно: при –1 < x < 1 значения φ(x) можно вычислить (подобно тому, как вычисляют сумму бесконечной геометрической прогрессии).

Теперь – главное. После раскрытия наших скобок очень многое уничтожается, можно сказать – почти всё. Например, результат раскрытия скобок в произведении (1 – x)(1 – x2 )...(1 – x10 ) содержит до приведения подобных 43 слагаемых с x в степенях, меньших или равных 10, в том числе 24 слагаемых с x в степенях 8, 9, 10. После приведения подобных из этих 43 слагаемых остаётся всего 5, в том числе ни одного с x в степенях 8, 9, 10. Более точно, как мы видели, среди коэффициентов a0, a1, a2, ..., a10 три равны 1, два равны –1 и шесть равны 0. Выскажем осторожную гипотезу: коэффициенты ak всегда равны 0, 1 или –1, причём большинство из них равно 0. Дальнейшее вычисление, которое читатель при желании сможет провести сам, не только подтверждает эту гипотезу, но и позволяет её уточнить. Вот, например, часть ряда φ(x), содержащая x в степенях, не превосходящих 100:

Надо полагать, что Эйлер, который не боялся длинных выкладок и отменно считал, примерно столько членов ряда φ(x) и вычислил. А потом он просто не мог не заметить, что коэффициенты, отличные от 0, равны 1 или –1, и при этом единицы и минус единицы расположены не как попало, а в строго определённом порядке: две единицы, две минус единицы, две единицы, две минус единицы и т.д. (Мемуар Эйлера на эту тему полностью приведён в книге Д.Пойа «Математика и правдоподобные рассуждения» (М., «Наука», 1975, с.111). Чтение этого мемуара, как и других глав книги Пойа, несомненно, доставит вам большое удовольствие.) В таблице выписаны показатели степеней x, при которых стоят ненулевые коэффициенты.

Легко угадать, что это за показатели: в n-м столбце нашей таблицы в верхней строке стоят числа ½(3n2 – n), в нижней – число (–1)n. Если это так при всех n, мы приходим к равенству

или, пользуясь принятой в математике сокращённой символикой,

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

2. Тождество Эйлера и число разбиений

Пусть n – натуральное число. Обозначим через p(n) число способов, которыми можно представить n в виде суммы натуральных слагаемых (при этом слагаемые в суммах могут повторяться, и представления, различающиеся лишь порядком слагаемых, считаются одинаковыми). Например:

Числа p(n) входят во многие математические формулы, и их полезно уметь вычислять. Но как это сделать? Попробуйте, например, найти p(10). Вам придется изрядно повозиться, и, если повезёт, вы найдете правильный ответ: 42. А если нужно знать, скажем, p(50)? На помощь приходит тождество Эйлера.

Сначала немного «теории». Положим

π(x) = 1 + p(1)x + p(2)x2 + p(3)x3 + ... = 1 + x + 2x2 + 3x3 + 5x4 + 7x5 + ...

Как и φ(x), π(x) – функция, определённая при –1 < x < 1. Но, опять-таки, нас она интересует только как степенной ряд.

Теорема. Ряды φ(x) и π(x), взаимно обратны, то есть

φ(x) · π(x) = 1.

Вы понимаете, в чем смысл этого равенства? Степенные ряды можно перемножать:

наше утверждение означает, что если перемножить таким образом ряды φ(x) и π(x), то полученное произведение сведётся к 1: коэффициенты при x, x2, x3 ... будут равны нулю.

Доказательство.

= (1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)×...×(1 + xk + x2k + x3k + ...)... .

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

где a1 ..., ak – целые неотрицательные числа. Таким образом, xn войдёт в эту сумму столько раз, сколькими способами n можно представить в виде

a1 + 2a2 + ... + kak.

Но это представление можно переписать так:

Мы видим, что представлений числа n в виде a1 + 2a2 + ... + kak столько же, сколько есть его представлений в виде суммы натуральных слагаемых, то есть p(n). Таким образом, коэффициент при xn в нашем произведении равен p(n), то есть 1/φ(x) = π(x). Теорема доказана.

Положив для удобства p(0) = 1, напишем

(1 – x – x2 + x5 + x7 + ...)(1 + p(1)x + p(2)x2 + ...) = 1

(коэффициенты в первом множителе пишутся согласно тождеству Эйлера!). Раскроем скобки и приравняем нулю коэффициенты при x, x2, x3, ..., xn в левой части. Получим:

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

p(n) = p(n–1) + p(n–2) – p(n–5) – p(n–7) + ... .

Эта формула позволяет быстро составить довольно длинную таблицу чисел p(n). Вот практический совет, как это сделать. Возьмите лист клетчатой бумаги – лучше всего двойной тетрадный лист. Отрежьте вдоль его длинной стороны полоску шириной 3–4 клетки. Положите эту полоску перед собой вертикально и у левого среза в нижней клетке поставьте какой-нибудь знак, скажем звёздочку. Затем, двигаясь вверх, поставьте в первой клетке +, во второй +, в пятой –, в седьмой –, в двенадцатой +, в пятнадцатой + и т.д., насколько хватит длины полоски (рис. 1). Оставшуюся часть листа также положите перед собой вертикально и, отступя 10–15 клеток от её левого среза, проведите на ней вертикальную черту – сверху донизу. В клетки, прилегающие к черте слева, двигаясь сверху вниз, впишите уже известные вам числа p(n), начиная с p(0): 1, 1, 2, 3, 5, 7. Чтобы найти следующее значение, приложите отрезанную полоску справа к вертикальной черте так, чтобы звёздочка оказалась против первой пустой клетки. Теперь из суммы чисел, стоящих против плюсов, вычтите сумму чисел, стоящих против минусов. Что получится – впишите в клетку против звездочки: это – следующее значение функции p(n). Опустите полоску на одну клетку вниз и повторите то же самое. И так далее. Через несколько минут вы получите колонку чисел p(n) высотой в ваш лист.

Пользуясь этим рецептом, я нашел числа p(n) для n ≤ 50. На это потребовалось – честно, по часам – 17 минут. (Несколько первых шагов вычисления я привожу на рисунке 2; красные числа – это новые значения p(n).) В частности,

p(50) = 204226.

Представьте себе, сколько потребовалось бы времени для нахождения этого числа кустарным способом!

3. Доказательство тождества Эйлера

Раскроем скобки в нашем произведении

(1 – x)(1 – x2)(1 – x3)(1 – x4)... .

Получится сумма (бесконечная), в которой xn встретится столько раз, сколькими способами n представляется в виде суммы возрастающей последовательности натуральных чисел: n = n1 + n2 + ... + nk , n1 < n2 < ... < nk ; при этом знак при xn будет +, если k чётно, и –, если k нечётно. Ниже в этом параграфе наборы (n1 , ..., nk ) с n1 + ... + nk = n и n1 < ... < nk называются просто «разбиениями».

Мы будем различать разбиения трёх типов. Обозначим для разбиения (n1 , ..., nk ) через s наибольшее число такое, что nk – nk–s+1 = s – 1, то есть s чисел nk–s+1, ..., nk идут подряд (очевидно, s ≤ k). Например, для разбиения 12=2+4+6 s = 1, для разбиения 12=1+5+6 s = 2, для разбиения 33=4+5+8+9 s = 3. Мы скажем, что разбиение (n1 , ..., nk ) принадлежит

первому типу, если n1 ≤ s, исключая случай n1 = s = k;

второму типу, если n1 > s, исключая случай n1 = s + 1, s = k;

третьему типу в исключённых случаях, то есть если s = k и n1 равно s или s + 1.

Поставим теперь в соответствие разбиению (n1 , ..., nk ) первого типа разбиение

которое относится, очевидно, ко второму типу (проверьте!).

Более того, таким образом между разбиениями первого и второго типа получается взаимно однозначное соответствие: обратное отображение ставит в соответствие разбиению (n1 , ..., nk ) второго типа разбиение

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

(k, k + 1, ..., 2k – 1),

(k + 1, k + 2, ..., 2k),

и им соответствуют (–1)k x½(3k² – k), (–1)k x½(3k² + k) (как вам известно, k + (k + 1) + ... + (2k – 1) = ½(3k2 – k) и (k + 1) + (k + 2) + ... + 2k = ½(3k2 + k) ).

Доказательство окончено.

4. Тождество Гаусса

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

φ3(x) = (1 – x)3(1 – x2)3(1 – x3)3... = 1 – 3x + 5x3 – 7x6 + 9x10 – 11x15...

(я советую вам не полениться и вычислить столько коэффициентов ряда φ3(x)) или

Это тождество Гаусса тем более удивительно, что квадрат функции Эйлера с виду ничем не примечателен:

φ2(x) = 1 – 2x – x2 + 2x3 + x4 + 2x5 – 2x6 – 2x8 – 2x9 + x10...

(не радуют и дальнейшие члены этого ряда: последовательность его коэффициентов не обнаруживает никакой закономерности, в ней появляются тройки, четвёрки и т.д.). Глубину тождества Гаусса подчёркивает то обстоятельство, что известны его доказательства, относящиеся к совершенно разным областям математики – от геометрии Лобачевского до весьма абстрактной гомологической алгебры. Известно и доказательство, по духу близкое к доказательству тождества Эйлера из п. 3, но оно удручающе громоздко. Доказательства, которое можно было бы предложить читателям «Кванта», я не знаю. Может быть, такое доказательство придумает кто-нибудь из читателей?

5. Степени функции Эйлера

Итак, мы знаем, как устроены ряды φ(x) и φ3(x), но не имеем никакой удовлетворительной формулы для φ2(x). А как обстоит дело с рядами φ4(x), φ5(x), ...? Иными словами: при каких n существуют формулы для коэффициентов ряда φn(x)? Для ответа на этот неформальный (то есть не имеющий точного смысла) вопрос я предлагаю использовать следующий полуформальный признак. Если при некотором n среди коэффициентов ряда φn(x) часто попадаются нули – это вряд ли случайно: наверное, для φn(x) есть какое-то тождество типа тождеств Эйлера и Гаусса. Впрочем, если нулей мало или нет вовсе – ничего ещё не известно. По моей просьбе Е. И. Коркина вычислила на ЭВМ коэффициенты, с которыми в ряды φ(x), φ2(x), ..., φ15(x) входят x, x2, ..., x50 (те из вас, кто учится в математической школе и проходит практику на ЭВМ, могут попытаться повторить это вычисление). [Через 20 лет после написания статьи эти строки невозможно читать без улыбки. :) – E.G.A.] Нет смысла приводить результаты вычисления полностью; я ограничусь таблицей, в которой c(n) обозначает число нулей среди коэффициентов при x, ..., x50 в ряде φn(x):

Констатируем: при n = 1, 3 нулей очень много (это мы уже знаем), при n = 2, 4, 6, 8, 10, 14 их порядочно, при n = 5, 7, 9, 11, 12, 13, 15 их нет вовсе.

Наличие нулей при n = 2, 4 и 6 не должно нас удивлять. Дело в том, что ряды φ(x) и φ3(x) настолько разрежены, что в произведениях φ(x)φ(x), φ(x)φ3(x) и φ3(x)φ3(x) некоторые члены могут отсутствовать ещё до приведения подобных членов. Например, числа 11, 18, 21 (и многие другие) не представляются как суммы двух чисел вида ½(3n2 ± n) и потому члены с x11, x18, x21 отсутствуют в φ2(x). По аналогичной причине члены с x9, x14, x19 (и другие) отсутствуют в φ4(x), а члены с x5, x8, x14 (и другие) отсутствуют в φ6(x).

А вот «подскоки» числа c(n) при n = 8, 10, 14 так просто не объяснить. Оказывается, для φ8(x), φ10(x), φ14(x) имеются некоторые формулы, хотя и не столь изящные, как тождества Эйлера и Гаусса. (Такая формула есть и для φ15(x), но это не сказывается на нашей таблице.) Для иллюстрации я приведу формулу для φ8(x), по существу принадлежащую Ф. Клейну:

где суммирование в правой части происходит по всем тройкам k, l, m целых чисел с k + l + m = 1.

(Хотя эта формула не особенно проста, она позволяет заметить, что если n не представляется в виде –(kl + km + lm), где k, l, m – целые числа с суммой 1, то есть в виде k 2 + l 2 + kl – k – l с произвольными целыми k, l, то член с хn отсутствует в ряде φ8(x). Например, в таком виде не представляются числа, имеющие при делении на 4 остаток 3, а также числа 13, 18, 28, 29.)

Из сказанного видно, что среди целых чисел имеются некие «избранные показатели» n, для которых ряд φn(x) имеет более или менее благоустроенный вид. Загадка «избранных показателей» была (тоже более или менее) разгадана совсем недавно, и главная заслуга в этом принадлежит английскому математику Яну Макдональду. Интересный рассказ об открытии Макдональда содержится в статье Ф. Дж. Дайсона «Упущенные возможности», русский перевод которой опубликован в первом выпуске журнала «Успехи математических наук» за 1980 год.

О Дайсоне и его статье стоит сказать особо. Дайсон – один из крупнейших физиков нашего времени, математик по образованию. [Тем, кто интересуется вопросами развития Интернет-сообщества, наверное, известна его дочь – Эстер Дайсон. – E.G.A.] Главная цель его статьи – показать на ряде ярких примеров, как значительные математические и физические открытия задерживались, порою на десятки лет, из-за отсутствия должного взаимодействия между специалистами в той и другой науке. Хотя статья не адресована школьникам и многое в ней будет вам непонятно, я уверен, что её чтение доставит вам удовольствие. А здесь я приведу (с сокращениями) отрывок из этой статьи, непосредственно касающийся нашего предмета.

6. Рассказ Ф. Дж. Дайсона

«Начну с банальной истории, случившейся со мной. Это живая иллюстрация того, какие возможности упускаются по причине узкой специализации. Свою научную деятельность я начинал с теории чисел. В мои студенческие годы в Кембридже я учился у Г. Харди, уже тогда бывшего легендарной личностью. Даже первокурсникам в те годы было ясно, что теория чисел в духе Харди и Рамануджана устарела и блестящее будущее её не ждёт. Сам Харди в лекции о τ-функции Рамануджана назвал этот сюжет «одной из тихих заводей математики». Значения τ-функции – это коэффициенты ряда:

Рамануджан открыл ряд замечательных арифметических свойств τ(n).

Доказательство и обобщение этих свойств Морделлом, Гекке и другими сыграли важную роль в развитии модулярных форм. Но сами τ-функции по-прежнему оставались тихой заводью, далёкой от основного русла математики, где дилетанты могли плескаться в своё удовольствие, не тревожимые конкуренцией с профессионалами. Уже став физиком, много лет спустя, я сохранил сентиментальную привязанность к τ-функции и отдыхал от такого серьёзного дела, как физика, время от времени возвращаясь к работам Рамануджана и размышляя над многими увлекательными проблемами, которые он оставил нерешёнными. Четыре года тому назад (статья Дайсона написана в 1972 году – Д. Ф.), во время такого отдыха от физики, я нашёл новую формулу для τ-функции, столь красивую, что просто поразительно, как сам Рамануджан не додумался до неё. Выглядит она так:

Суммирование ведётся по всем пятёркам целых чисел a, b, c, d, e, имеющих при делении на 5, соответственно, остатки 1, 2, 3, 4, 0 и таких, что a + b + c + d + e = 0, a2 + b2 + c2 + d2 + e2 = 10n. Пользуясь (1), можно записать эту формулу в виде выражения для φ24(x) (сравните с приведённым выше выражением для φ8(x) – Д. Ф.).

Я пришёл к ней под влиянием письма Винквиста, получившего похожее выражение для φ10(x).

Продолжая своим доморощенным способом исследования этих тождеств, я обнаружил существование столь же красивой формулы, как (2), для n-х степеней φ в тех случаях, когда n принадлежит следующей последовательности целых чисел:

(вот они, «избранные показатели»! – Д. Ф.). На этом я остановился. Довольно недолго я разглядывал странную последовательность (3). Будучи в то время теоретиком-числовиком, я ничего в ней не увидел. Перегородки в сознании помешали мне заметить, что я неоднократно встречал эти числа в качестве физика. Попадись они мне на глаза в контексте какой-нибудь физической задачи, я бы, наверное, узнал в них размерности конечномерных простых алгебр Ли, если не считать число 26. Почему сюда попало 26 не знаю до сих пор».

Простите, я забыл, что вы не знаете, что такое простые алгебры Ли. Это неважно. Я постараюсь объяснить вам, что такое числа (3). Вспомните, что вращения плоскости вокруг фиксированной точки зависят от одного параметра – угла поворота. Вращения трёхмерного пространства зависят от трёх параметров – широты и долготы оси вращения и угла поворота. Вообще, «вращения» n-мерного пространства зависят от ½n(n – 1) параметров, а «вращения» n-мерного «комплексного пространства» – от n2 – 1 параметров. К числам ½n(n – 1) и n2 – 1 (то есть 1, 3, 6, 10, 15, 21, 28, ... и 3, 8, 15, 24, 35, ...) нужно присоединить пять «особых размерностей» 14, 52, 78, 133 и 248. Если ещё выбросить, как это и делает Дайсон, числа 1 и 6, получится последовательность (3), которую, конечно, твёрдо помнит любой физик-теоретик.

«Так я упустил возможность заметить глубокую связь между модулярными формами и алгебрами Ли только потому, что Дайсон теоретик-числовик не поговорил с Дайсоном физиком.

У этой истории счастливый конец. Неизвестный мне в то время английский математик Ян Макдональд получил эти же формулы, как частный случай более общей теории. Алгебры Ли входили в его теорию с самого начала, а связь с модулярными формами появилась нежданно-негаданно. Так или иначе, Макдональд выявил эту связь и использовал возможность, которую я упустил. Выяснилось также, что Макдональд находился в Институте высших исследований в Принстоне, когда мы оба работали над этой проблемой. Поскольку наши дочери учились в одном классе, мы виделись время от времени в течение всего его годичного пребывания в Принстоне. Но так как он был математиком, а я физиком, мы не говорили о своей работе. То, что мы думали над одним и тем же вопросом, находясь столь близко друг от друга, выяснилось лишь по его возвращении в Оксфорд. Вот упущенная возможность, но не столь драматичная, поскольку Макдональд прекрасно во всём разобрался и без моей помощи».

7. Заключение

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