Труды семинара Бурбаки за 1992 г (Семинар Н. Бурбаки), страница 6

Ьес!шев, 1989. Не!Яех В., Я|бззгапй Л. Апа1узе веш|-с!зяз|г|ие роиг !'ег|иаз|оп йе Натрет (ачес аррПсагюп а РециаПоп г1е БсЬгой|ибег ачес сЬазир шабпбз|г|ие), Меш. Бос. МаГЬ. Ргапсе (1988), |з|о. 34, 1 — 113. НеИГег В., БЛоввтапй Л. Апа|уяе зепи-с!аявгПие роиг 1'ециаПоп йе Нзхрег Н. Сошрогзешепз веш|-с!аявн|ие ргея й'ип та!юлие|, Меш. Бос. Ма!Ь. Ргалсе (1990), |з|о.40, 1-139. НеПГег В., Б]ояггапй Л.

Яепи'-с|аваса1 ила|уз|в Еог Натрет'з ег|иагюп 1И, Мбш. Яос. МазЬ. ггапсе (1989), Гз|о. 39, 1 — 124. Нобззайзег Р. В. Епегбу |ече|я апй зчаче Гипс!|пав оЕ В!осЬ е!ее!топя ш а гав!опа| ог |тга!!опа! шабпег|с бе!й, РЬув. Веч., В14 (1976), 2239. чои К1Нтйпб К., Вогйа С., Реррег М. ВеаПяазюп оГ а зев|егзиге вгзлйагй Ьаяей оп Еиийашепга! сопя!апта, РЬув. Веч. Ьессетя, 45 (1980), 494 †4. 1 апйаи 1. ГЗ|ашабпег!вшие г|ег МезаПе, Е.

Ейг РЬув., 64 (1930), 629-637. Ьихв!п8ег Л.М. ТЬе е|Гесз оГ а шабпеНс Пе!й оп е!ее!топя |и а репойс ровепНа1, РЬув. Веч., 84 (1951), 814. чаи МоисЬе Р. ТЬе соех!в!епсе ргоЪ|езп Еог зЬе й!всгеге МагЬзеи прети!от, Сошш. МагЬ. РЬув., 122 (1989), 23 — 34. «АВТОМАТИЧЕСКОЕ» ДОКАЗАТЕЛЬСТВО ТОЖДЕСТВ И ГИПЕРГЕОМЕТРИЧЕСКИЕ ФУНКЦИИ (по Д. Цайльбергеру) Пьер Картье' ) ВВЕДЕНИЕ Рассмотрим следующий набор тождеств между биномнэльнымн коэффициентамиг): ~ (:) =' Е:(-'(:) = = ("), 2'(-1)'(и) =(-1)" ("), (2(.

Д (-1( ( ) = (-1)" ( ) ( ) (Д . 1899(. (8) Два первых тождества стандартны — они доказываются специализацией формулы бинома . (4). Учитывая закон симметрии ("„) = („" ), обе формулы (2) можно получить сравнЬнием коэффициентов при подходящих мономах в тождествах (х+у)"(х+ у)" = (х+ у)г" и (х+ у)г»(х — у)г" = (хг уг)г Тождество Диксона (3) не поддается такого рода методам; впрочем, не существует соотвнтствующей формулы ни для ~ „. (,",), ни для более высоких степеней биномнэльных коэффициентов.

'1Сагпег Р1егге. Вешопвегагюп 9авеошас(яое"' д'Ыепс(гев е1 1опсеопв Ьурегкеошегг!чаев (д'аргьв В. ееньегяег).— зеш(па!ге Вопгьаьь 1991-92, и 746, Авгег(вяпе, 206 (1992), р. 41-91. В'соответствии с обычными соглашенияыи ("„) = О, если» > О и Ь не лежит между О и». Следовательно, все приведенные ряды имеют лишь конечное число ненулевых членов и точные гранины суммирования можно не у кавмвать.

36 Пьер Картье Рнс. 1. Треугольник Паскаля из труда Чжу Ши-цзе (Китай, 1303). (Иллюстрация из; Со!!егге З.-Р. Нано!ге г!ее ша«Ьешаг!инее, Ег!!г!оне 'гн!Ьегг.] Во многих рассуждениях формулу бинома (4) можно использовать как определение биномиальных коэффициентов ("„). Поскольку степени вычисляются одна за другой по правилу (х+у)" = (х+у)" '(х+у), 'биномиальные коэффициенты удовлетворяют основной формуле слохсеиил (5) Это позволяет производить быстрые вычисления при помощи таблицы, известной под названием «треугольник Паскаля» (и знакомой китайскому автору 1300 г., см. рисунок). «АВТОМАТИЧЕСКОЕ» ДОКАЗАТЕЛЬСТВО ТОЖДЕСТВ 37 Определение при помощи формулы бинома приводит к комбинаторной интерпретации: ("„) равно числу слов из п букв, в которых )с раз встречаетсл х и и — Й раз у. Эквивалентным образом, (") равно числу Й-элементных подмножеств в множестве из и элементов.

Таким образом, формулы, связывающие биномиальные коэффициенты, интерпретируются в терминах перечисления комбинаторных структур (графов, деревьев, таблиц, путей, слов, ... ). Во многих случаях эти формулы можно доказать построением явных биекций между различными типами структур. Именно таким способом Фоата и я установили в ]Е 1] формулу Диксона и дали различные ее обобщения. Это направление сейчас активно развивается в лотарингской школе Фоата в Страсбурге и квебекской школе братьев Лабеллей.

В тождествах (1) — (3) результат суммирования — это «замкнутое» выражение, представленное как произведение степеней а" и различных биномиальных коэффициентов. Результат не всегда можно выразить так просто: вот, прежде всего, элементарная формула (6) где Ä— это и-е число Фибоначчи, т.е. решение рекуррентноео уравнения Ро = Г -1 + Р -г пРн и > 2, Ро = Г1 = 1.

(7) Для доказательства иррациональности ~(3) Апери [Е 2] должен был просуммировать следующее выражение; (8) ему удалось установить рекуррентное соотношение пзи„— (34пз — 51п~+27п — 5)и 1+(и — 1)зи„т = 0 (и > 2) (9) с начальными условиями ио —— 1, и1 — — 5. Апери не приводит доказательства формулы (9), оно было предложено Загиром и Коэном 38 Пьер Картье (Е 3]. Идея следующая: положим Г(п, й) = ("„) (ч» «); тогда суще. ствует некоторая функция С(п, й), удовлетворяющая тождеству С(п, й) — С(п, й — 1) = и Г(п, й) — (34пз — 51пз+ 27п — 5)Г(п — 1, й) + (п — 1)зГ(п — 2, й). (10) Очевидно, что и„ = ~ Г(п,й) (11) и, кроме того, при фиксированном п «телескопическая сумма» равна нулю.

Соотношение (9) вытекает из (10) после суммирования по й. Этот метод по-английски называется всгеабгге Фе1езсор1п8». Аналогичным образом можно доказать классическое интегральное тождество +о» з » ег '*"е н с(р=в (12) Обозначим подинтегральную функцию через Г(х, р), а затем поло- жим и(х):= Г(х, д) Иу. (13) Нужно доказать равенство и(х) = е *, которое равносильно тому, чтоП Р и(х)+2кхи(х) = О, и(0) = 1. Определим некоторую функцию С(х, у), для которой Р»Г(х, у) + 2кхГ(х, р) = Р„С(х, р). (15) г+' с+со Р, / Г(х,р)4у = / Р,Г(х,р)ау, (16) П Вв, й»,... обозначают производные по х,ж Уравнение (14) выводится из (15) интегрированием по у с учетом двух основных правил — дифференцирования под знака н интеграла и интегрирования по частлль: «АВТОМАТИЧЕСКОЕ> ДОКАЗАТЕЛЬСТВО ТОЖДЕСТВ 39 РгС(х, у) Ну = О, если С(х, хоо) = О.

(17) с и! й,/ й)(и — й).' (18) Поскольку факториал и! определяется условиями и!=п (и — 1)! при п>1, О!=1, (19) формула (18) непосредственно следует из фундаментального от- крытия Паскаля, которое можно выразить так: (формула сложения является его очевидным следствием!). В при- мере Апери, следовательно, г'(п + 1, й) / и + й + 1'1 Р(п,й) (,п-й+1/ ' г'(п,й+1) 1 /и+й+11 Г(и,й) (й+1)4 ~ п-й,/ ' Оказывается также, что и отношение С(и, й)/Г(и, й) — рациональная функция, С(и, й) (си — й'1 г(п,й) \ и+й/ — 4 ( ~ (2и — 1)(й(2й+ 1) — (2и — 1) ). (23) Для доказательства тождества (10) Загира и Коэна можно разделить обе его части на г'(п, й), и останеп1ся простое, но непонятное вычисление с рациональными функциями от п и й.

Аналогично, в интегральном примере, рассмотренном выше, ло« гарифмические производные функции г'(х, у) = ег™в е г 4 — рациональные функции: , у) Р„Р(х, у) = 2я«у, " ' = 2я«(х+1у), (24) р (х, у) ' г'(х, у) Следовательно, интегральная формула (12) восстанавливается ио дифференциальному соотношению (15) ценой нахождения функции С(х, у). В чем причина успеха в обоих случаях? Сначала напомним, что бнномиальные коэффициенты можно выразить через факториалы по формуле Пьер Картье 40 и для функции С(х,у), удовлетворяющей дифференциальному уравнению (15), справедливо равенство = — » (25) Р(х, у) Доказательство дифференциального соотношения (15) в результа- те сводится (после деления на Р(х, у)) к доказательству совсем элементарного тождества между рациональными функциями от х и у.

Для завершения доказательства интегрального соотношения (12) достаточно его проверить при «начальном» условии х = О, т.е. уста- новить соотношение / е '" ду = 1. Все это относится к стадии проверки, но как обстоит дело со сгпадией индукции? Исходя из вида функции Р(п, й) = (",) ("+~) можем ли мы утверждать, что существует рекуррентное уравне- ние вида (9), которому удовлетворяет сумма и„= '> д Р(п,й), и, более того, что существует функция С(п, Й), удовлетворяющая со- отношению (10)? Как явно найти рекурреитное уравнение и функцию С(п, й)? В замечательной серии статей Цайльбергер смог дать два ответа на эти вопросы: ° теоретический ответ, использующий теорию дифференци- альных голономных систем Бернштейна, ° практический ответ, йозволяющий находить алгоритмы, ко- торые дают рекуррентное соотношение и С(п, к).

Все приведенные выше соотношения, включая необычную ре- куррентную формулу Апери, получаются заново систематическим~ и автоматическим способом, н предлагается техника, которая поз-) валяет открывать и доказывать тождества некоторого типа. Ве-,' роятно, близок день, когда классические сборники специальных( функций будут вытеснены экспертными системами, например рас« ширением МАРБЕа. 1. ГОЛОНОМНЫЕ МОДУЛИ [С 3) 1.1.

Обозначим через А, кольцо дифференциальных операторо4 с полиномиальньми коэф4ициентами, действующих на функцид от д переменных; константами являются комплексные числа. Вся' кий оператор единственным образом записывается в виде Р=~ с вх .0о. (26' а в «АВТОМАТИЧЕСКОЕ» ДОКАЗАТЕЛЬСТВО ТОЖДЕСТВ 41 Обозначения классические: ° х = (хы...,х,) обозначает систему из г переменных, Ре— частная производная по хб ° а, )),... обозначают элементы из Е+, т.

е. векторы а = (аы..., а„) с целыми неотрицательными координатами; ° кроме того, ]а] = а1 +... + а„х = х, '... х„', РВ = Р~'... РВ". В формуле (26) лишь конечное число коэффициентов со В отлично от О. Порядок т оператора Р равен максимальному из чисел ])1] для таких )т', что с л Р 0; главный символ в(Р) оператора Р— это поли- НОМ 2 ) СоЛХоСВ От ПЕРЕМЕННЫХ (Х,С) = (ХЫ...,Х„,СЫ...,С«); он однороден степени т по С. Вот основные правила: ° если Р имеет порядок т, а Я вЂ” порядок и, то порядок РЯ равен т+ и, а порядок коммутатора ]Р, Я = РЯ вЂ” ЯР не превосходит та+и — 1; ° имеют место равенства' ) в(РЯ) = в(Р)вЯ), в(]Р, Я]) = (сс(Р), в(Я)). (27) В последней формуле мы используем скобку Пуассона двух поли- номов от х, с, определяемую следующим образом: — 3 г (28) Все это можно представить и более алгебраично. Как алгебра над полем С комплексных чисел А, определяется 2г образующими х; и Р, и соотношениями (29) Р Р" С Р +", ]Р,Рн] С Р +" '.

(30) Ц Во второй формуле предполагается, что порядок коммутатора (Р, «)] равен ш -~- и — Ц что эквивалентно соотношению (о(Р), е(м)) Р О. ]х,,х.] = О, ]РьРт] = О, ]Р,,ху] = 60. Обозначим через Г = Г А„множество операторов порядка < т. Это векторное пространство над С, последовательность (Г ) является возрастающей (Ро С г'г С Рг С... ), Ро = С]хы., ., х,] и приведенные выше правила записываются в виде 42 Пьер Картье Благодаря этим свойствам можно определить структуру алгебры в ассоциированном градуированном пространстве вгрА =ЕР УР 1' юв>0 определим изоморфизм этой алгебры на алгебру полиномов С]х, с], отображая в а(Р) класс РщопР ' (для всех Р из Р УР ').