Содержание к диссертации
Введение
1 Введение 3
1.1 Актуальность темы 3
1.2 Цель работы 5
1.3 Научная новизна 5
1.4 Практическая и теоретическая ценность 6
1.5 Апробация работы 7
1.6 Публикации 7
1.7 Структура и объем диссертации 7
1.8 Благодарности 7
2 Базисы Гребнера и инволютивные базисы 9
2.1 Основные понятия коммутативной алгебры 9
2.2 Схемы симплификации и стандартные множества 10
2.3 Стандартные базисы 11
2.4 Инволютивные деления 13
2.5 Инволютивные базисы 16
2.6 Сравнение алгоритмов Бухбергера и инволютивного алгоритма 19
3 Инволютивный маршрут Гребнера 24
3.1 Допустимые отношения порядка и весовые вектора . 24
3.2 Шаг инволютивого маршрута Гребнера 27
3.3 Конусы Гребнера и инволютивный маршрут Гребнера . 29
4 Дифференциальный маршрут Гребнера 32
4.1 Основные понятия дифференциальной алгебры 32
4.2 Ранжиры 33
4.3 Характеристические множества 34
4.4 Лидеры характеристических множеств 36
4.5 Дифференциальное разбиение Гребнера 39
4.6 Преобразование характеристических множеств 41
4.7 Дифференциальный маршрут Гребнера 45
4.8 Конечность дифференциального маршрута Гребнера . 46
4.9 Нерешенные проблемы 48
А Приложение
- Практическая и теоретическая ценность
- Схемы симплификации и стандартные множества
- Шаг инволютивого маршрута Гребнера
- Дифференциальное разбиение Гребнера
Введение к работе
Системы полиномиальных уравнений изучаются на протяжении нескольких столетий и имеют множество приложений. На алгебраическом языке системы полиномиальных уравнений описываются идеалами в кольцах многочленов. Особо важна задача канонического представления идеала, вопрос о принадлежности многочлена идеалу и решение систем полиномиальных уравнений. Теория базисов Грёбнера дает алгоритмическое решение этих задач.
Первый алгоритм построения базиса Грёбнера был разработан и реализован Бухбергером в 1965 г. Его основная идея заключается в преобразовании исходной системы многочленов в эквивалентную каноническую систему. Решение системы линейных уравнений методом Гаусса и нахождение наибольшего общего делителя многочленов от одной переменной с помощью алгоритма Евклида являются частными случаями алгоритма Бухбергера. В общем случае алгоритм Бухбергера имеет высокую сложность, для которой не известно хорошей теоретической оценки — наоборот, известны примеры систем, для которых базис Грёбнера имеет экспоненциальный размер. Поэтому становится важной разработка различных методов, позволяющих усовершенствовать алгоритм Бухбергера на практике.
Идея преобразования системы в эквивалентную каноническую присутствует и в работах Жане, Томаса и Поммаре [33, 46, 41] по системам линейных уравнений в частных производных. В этих работах приведение системы к каноническому виду называется приведением в инволюцию. В работах Гердта, Жаркова и Блинкова (например [22]) разработана теория инволютивных делений и инволютивных базисов для систем многочленов. Инволютивные базисы являются нередуцированными базисами Грёбнера [49, 50] и вместе с тем имеют дополнительные полезные свойства [48]. Вид и сложность построения инволютивных базисов зависит от инволютивного деления, грамотный выбор которого позволяет ускорить алгоритм этого построения [23]. Эксперименты показывают, что во многих случаях инволютивный алгоритм работает быстрее, чем алгоритм Бухбергера.
Существует совершенно иной метод усовершенствования алгоритма Бухбергера для построения базисов Грёбнера относительно лексикографического порядка, известный под названием маршрута Грёбнера (Grob-ner Walk). Этот метод основан на известном наблюдении, что время работы алгоритма Бухбергера существенно зависит от выбора отношения порядка на мономах. Например, построение базиса Грёбнера относительно порядка общей степени, как правило, гораздо более эффективно, чем построение базиса для лексикографического порядка. Метод маршрута Грёбнера, впервые предложенный Коллартом, Калкбренером и Маллом в работе [19], позволяет эффективно преобразовывать базис Грёбнера относительно одного порядка на мономах в базис относительно любого другого порядка. Эксперименты показывают [6], что такое косвенное построение может оказаться гораздо эффективнее прямого построения лексикографического базиса Грёбнера.
Для систем нелинейных уравнений в частных производных также существует подход, связанный с приведением системы к каноническому виду и основанный на понятиях из дифференциальной алгебры. Основы дифференциальной алгебры, включая понятие кольца дифференциальных многочленов, дифференциального идеала и характеристического множества, были заложены Риттом [43] и Колчином [34]. Дальнейшее развитие дифференциальная алгебра получила в работах ряда авторов второй половины XX века. В частности, была разработана теория дифференциальных и разностных размерностных многочленов, с которой можно ознакомиться по монографии Кондратьевой, Левина, Михалева и Панкратьева [35]. Характеристические множества дифференциальных идеалов играют роль, сходную с ролью базисов Грёбнера для полиномиальных идеалов. Однако, некоторые важные свойства базисов Грёбнера не переносятся на дифференциальный случай [35]. Например, характеристическое множество дифференциального идеала, вообще говоря, может не порождать этот идеал.
Задача построения характеристических множеств гораздо сложнее ее полиномиального аналога. В случае простых дифференциальных идеалов эта задача может быть решена с помощью алгоритма Розенфельда-Грёбнера [16] или специализированного алгоритма Розенфельда-Грёбне-ра [15]. Однако, в обоих случаях искомое характеристическое множество строится путем прямого вычисления. Такой подход может оказаться неэффективным, особенно в случае исключающего ранжира. Для ре шения этой проблемы Булье [14] предложил алгоритм DFGLM, являющийся дифференциальным обобщением алгоритма FGLM [20] (последний алгоритм был разработан для ускорения подсчета полиномиальных базисов Грёбнера для лексикографического порядка в случае нульмерных идеалов). Однако, как отмечено в работе [14], этот алгоритм применим только к системам, решения которых параметризованы конечным семейством параметров. Алгоритм Кэли, также предложенный в работе [14], применим к произвольным дифференциальным системам, но, как отмечено в [14], менее эффективен, чем DFGLM.
Случай конечного семейства параметров для дифференциальных систем аналогичен случаю нульмерного идеала в кольце многочленов R, который является необходимым условием для применения алгоритма FGLM. Но даже при таком ограничении сложность алгоритма растет с: ростом размерности векторного фактор-пространства R/I. Результаты экспериментов, приведенные в [6, 7], показывают, что, за исключением простейших случаев, маршрут Грёбнера [19] не менее эффективен, чем FGLM, а с ростом размерности R/I первый становится гораздо более эффективным. Кроме того, метод маршрута Грёбнера применим к произвольным полиномиальным идеалам. Данное наблюдение позволяет предположить, что обобщение метода маршрута Грёбнера на дифференциальный случай будет обладать теми же преимуществами по сравнению с алгоритмом [14].
1.2 Цель работы
Целью настоящей работы является исследование связи между инволю-тивными базисами и базисами Грёбнера, обобщение метода маршрута Грёбнера на инволютивный и дифференциальный случаи и экспериментальное сравнение полученных алгоритмов с известными.
1.3 Научная новизна
Научная новизна данной работы состоит в следующем:
1. Понятия базисов Грёбнера и инволютивных базисов изложены в рамках общей теории схем симплификации и стандартных базисов
[і] 2. Получен результат о сходстве алгоритма Бухбергера и алгоритма построения инволютивных базисов. Отмечена связь между выбором инволютивного деления и выбором алгоритма вычисления нормальной формы, являющимся частью алгоритма Бухбергера.
3. Метод маршрута Грёбнера перенесен на случай инволютивных базисов.
4. Алгоритм Бухбергера, алгоритм построения инволютивных базисов и методы маршрута Грёбнера и инволютивного маршрута Грёбнера реализованы в системе компьютерной алгебры Maple, и проведено экспериментальное сравнение их эффективности.
5. Метод маршрута Грёбнера перенесен на дифференциальный случай. Точнее, предложен алгоритм, который по характеристическому множеству Л дифференциального идеала / относительно ранжира В идеала I относительно другого ранжира 2- Данный алгоритм применим в случае простых дифференциальных идеалов и ранжиров Рикье [42, 44, 47], которые включают порядковые и исключающие ранжиры [35, 14]. Теорема Мора и Робиано о конечности разбиений Грёбнера [37, 38] не обобщается напрямую на случай дифференциальных идеалов, для которого приводится пример бесконечного разбиения Грёбнера. Тем не менее доказывается, что дифференциальный маршрут Грёбнера всегда конечен.
1.4 Практическая и теоретическая ценность
Методы и алгоритмы, предложенные в диссертации, могут быть внедрены в существующие системы компьютерной алгебры и таким образом дадут возможность анализировать и решать в символьном виде более сложные системы полиномиальных уравнений и уравнений в частных производных.
Результаты работы могут быть использованы в различных задачах теории базисов Грёбнера, полиномиальных инволютивных базисов и характеристических множеств дифференциальных идеалов в кольце дифференциальных многочленов.
1.5 Апробация работы
Основные результаты диссертации докладывались на Международной конференции по приложениям компьютерной алгебры IMACS АСА в 1998. г., Международной алгебраической конференции по случаю 90-летия А.Г. Куроша в 1998 г., Международном алгебраическом семинаре, посвященном 70-летию кафедры высшей алгебры МГУ в 1999 г., Ежегодном совместном семинаре МГУ и ОИЯИ РАН по компьютерной алгебре в 1999. г., Международном семинаре по компьютерной алгебре и приложениям в физике в 2001 г., и Рейнском семинаре по компьютерной алгебре в 2002 г.
1.6 Публикации
Результаты диссертации опубликованы в шести работах, список которых приведен в конце библиографии.
1.7 Структура и объем диссертации
Диссертационная работа состоит из четырех глав, первая из которых является вводной, и одного приложения и содержит библиографию (56 наименований). Общий объем диссертации составляет 57 страниц. Структура работы отражена в оглавлении.
1.8 Благодарности
Многие из результатов диссертации получены на семинаре по компьютерной алгебре на механико-математическом факультете МГУ под руководством Евгения Васильевича Панкратьева, Андрея Витальевича Аст-релина и Марины Владимировны Кондратьевой. Автор искренне благодарен всем участникам семинара за интересные идеи, примеры и рекомендации.
Автор также благодарит организаторов и участников ежегодного семинара по компьютерной алгебре в Дубне и, в особенности, Владимира Петровича Гердта за оживленные дискуссии по различным вопросам компьютерной алгебры.
Автор признателен Бруно Бухбергеру и Францу Винклеру за исключительную возможность, предоставленную ему приглашением на курсы и конференцию по базисам Гребнера в институте RISC-Linz, Австрия, в январе 1998 г. Лекции Виктора Николаевича Латышева о приложениях высшей алгебры помогли автору проанализировать и выразить результаты в более общей форме.
Огромное спасибо моим родителям и сотрудникам кафедры высшей алгебры и лаборатории вычислительных методов механико-математического факультета МГУ, в особенности Александру Васильевичу Михалеву, Виктору Николаевичу Латышеву, Антону Панкратьеву и Константину Панкратьеву, за поддержку. Наконец, автор хочет выразить глубокую благодарность своему научному руководителю, Евгению Васильевичу Панкратьеву, вклад которого в образование и вообще развитие автора, а также вдохновление и помощь во многих проблемах невозможно оценить.
Практическая и теоретическая ценность
Многие из результатов диссертации получены на семинаре по компьютерной алгебре на механико-математическом факультете МГУ под руководством Евгения Васильевича Панкратьева, Андрея Витальевича Аст-релина и Марины Владимировны Кондратьевой. Автор искренне благодарен всем участникам семинара за интересные идеи, примеры и рекомендации.
Автор также благодарит организаторов и участников ежегодного семинара по компьютерной алгебре в Дубне и, в особенности, Владимира Петровича Гердта за оживленные дискуссии по различным вопросам компьютерной алгебры.
Автор признателен Бруно Бухбергеру и Францу Винклеру за исключительную возможность, предоставленную ему приглашением на курсы и конференцию по базисам Гребнера в институте RISC-Linz, Австрия, в январе 1998 г. Лекции Виктора Николаевича Латышева о приложениях высшей алгебры помогли автору проанализировать и выразить результаты в более общей форме.
Огромное спасибо моим родителям и сотрудникам кафедры высшей алгебры и лаборатории вычислительных методов механико-математического факультета МГУ, в особенности Александру Васильевичу Михалеву, Виктору Николаевичу Латышеву, Антону Панкратьеву и Константину Панкратьеву, за поддержку. Наконец, автор хочет выразить глубокую благодарность своему научному руководителю, Евгению Васильевичу Панкратьеву, вклад которого в образование и вообще развитие автора, а также вдохновление и помощь во многих проблемах невозможно оценить. Базисы Гребнера и инволютивные базисы
Пусть К. — произвольное поле, X = {х\,..., хп} — множество переменных, N — множество натуральных чисел, в которое мы также включаем ноль. Пусть М = {xi ... хг гі,..., іп Є N} — моноид мономов от переменных {#1,..., #п}, в котором единица есть моном 1 = х ... ж„, а ассоциативная операция определена по правилу „Ч „in Зі „in — і+Іі in+3n 1 п 1 " п — 1 п Рассмотрим кольцо многочленов К[Х]. По определению, оно является линейным пространством над полем К с базисом М: К[Х] = {dm + ... + ckuk I k 0, а Є К \ {0}, щ ЄМ,щф щ (г ф j)}. Если / = с\и\ + ... 4- CkUk Є К[Х], то говорят, что мономы щ,..., ик входят в /, а остальные мономы из М не входят в /. Пусть F — {/i,..., /m} — конечное подмножество в К[Х]. Множество / = (F) = {pifi + . -\-Pmfm\Pi Є Щ-Х"]} называется идеалом, порожденным множеством F и обозначается (F). Линейное отношение порядка на множестве М называется допу-стимым, если выполнены следующие условия: 1. Vtt Є М 1 и. 2. V и, v, w Є М (и v = uw vw).
По определению, строгое отношение порядка, соответствующее отношению — это отношение , такое что и v 4Ф- и v Л и ф v. Для удобства, в зависимости от ситуации, мы будем определять лишь строгое или нестрогое отношение порядка, а использовать оба отношения.
Пример 1 Пусть rcj1... хг ж]1... хІ в том и только в том случае, когда существует к Є {1,...,п}, такое что ц = ji при 1 I к, и h: jk- Тогда является допустимым отношением порядка, которое называется лексикографическим и обозначается iex Пример 2 Пусть хг ... хг х± ... xfr тогда и только тогда, когда Н + ... + іп ji + -.. + jn V (г і + ... + г п = Іі + ... + Jn Л x\ ... x% iex x{1... xfr).
Это допустимое отношение порядка называется "порядком общей степени, затем лексикографическим" и обозначается degiex Определение 1 Путь — допустимое отношение порядка на моноиде М. Наибольший относительно моном и Є М, входящий в многочлен f Є ЩХ], называется старшим мономом многочлена f и обозначается ]. Коэффициент при f называется старшим коэффициентом ммхггочлена f. Обозначим f, деленный на свой старший коэффициент через /.
Рассмотрим множество ЩХ] как линейное пространство, порожденное множеством мономов. Пусть V — подмножество в ЩХ]. Определим схему симплификации в пространстве ЩХ], отвечающую множеству V, следующим образом: каждому многочлену f Є V отвечает e
Моноид, порожденный множеством отображений {г// Є V}, называется схемой симплификации и обозначается R{V). Если rj(g) — h, где g,h Є ЩХ], / Є V и g ф h, то говорят, что g редуцируется к h относительно f по моному f. Многочлен g Є ЩХ] называется нормальным (а также редуцированным, или нередуцируемым) относительно схемы симплификации R{V), если V г Є R(V) r(g) = g. Многочлен g Є ЩХ] называется нормальной формой многочлена / Є ЩХ], если g нормален и существует г Є R(V) такое что г(/) = д. Нормальная форма многочлена / Є ЩХ] называется канонической, если она единственна. Если любой многочлен / Є ЩХ] имеет каноническую нормальную форму, то схема симплификации R(V) называется канонической, а само множество V — стандартным. Пусть f,g Є V и / = g, тогда многочлен / — д называется S-элементом. Согласно теории стандартных множеств [1], имеет место следующий критерий: Лемма 1 Множество V является стандартным тогда и только тогда, когда все S-элементы имеют нормальную форму, равную нулю.
Схемы симплификации и стандартные множества
Пусть L — инволютивное деление на моноиде М. Для каждого конечного подмножества U С М, мы имеем семейство подмоноидов {L(u, U) \ и Є М}, которое по определению задает множество существенных произведений E(L, U) - {Еи}иеМ : Еи = {v х и v Є L(u, U)}. Пусть F — конечное подмножество в К[Х]. Назовем схему симпли-фикации, отвечающую множеству существенных произведений E(L, F), инволютивной.
Пусть множество F инволютивно авторедуцировано (то есть, F авто-редуцировано относительно множества существенных произведений E(L, F)). Тогда, согласно теории инволютивных делений, множество VE{L,F){F) всегда является стандартным, значит множество F является стандартным базисом. Это, в частности, означает, что инволютив-ная нормальная форма любого многочлена относительно инволютивно авторедуцированного множества F единственна. Следовательно, можно рассматривать инволютивные деления как способ задания алгоритма вычисления нормальной формы.
Заметим, что линейное пространство, порожденное множеством VE(L,F) может не совпадать с идеалом /, порожденным F, и вообще не быть идеалом. Множество F называется инволютивным базисом идеала /, если F является стандартным базисом (то есть инволютивно авторедуцировано), и линейное пространство, порожденное множеством VE(L)p\, совпадает с идеалом /. Согласно теории инволютивных базисов, справедлив следующий критерий (теорема 2.19 в [23]):
Лемма 4 Следующие условия эквивалентны в случае, если инволютив-ное. деление непрерывно: Множество F является инволютивным базисом идеала I. Множество F инволютивно авторедуцировано и любое немультипликативное продолжение любого многочлена f Є F, то есть произведение вида х /, х Є X \ L(f,F), f Є F, имеет инволю-тивную нормальную форму, равную нулю.
Подмножество мономов U С М (конечное или бесконечное) называется мюномиальным инволютивным базисом, если для любых мономов и Є U,m Е М существует моном v Є U, такой что v\Lfnu. Иначе говоря, подмножество U является мономиальным инволютивным базисом, если любое произведение некоторого монома т Є М на моном из U может быть представлено как существенное произведение на некоторый моном v Є U. Согласно теории мономиальных инволютивных базисов, справедлив следующий критерий (теорема 2.10 в [23]):
Лемма 5 Множество U является мономиальным инволютивным базисом, относительно непрерывного инволютивного деления L тогда и полько тогда, когда V х иух Є Х,и Є U существует моном v Є U. такой что хи Є vL(v, U).
На основе леммы 5 построена следующая процедура пополнения множества мономов U до некоторого множества V D U, являющегося мономиальным инволютивным базисом и порождающего тот же идеал, что и множество U: Procedure InvolutiveMonomialBasis(U\L) repeat done:=true for all x u, x Є X, и Є U do if Д v E U : x и Є vL(v, U) then U:=UU{x-u} done:=false end if end for until done
Если эта процедура завершается, то по лемме 5 множество U является мономиальным инволютивным базисом. Нетрудно видеть, что в случае нетерова инволютивного деления, для любого конечного множества U существует конечный мономиальный инволютивный базис, и поэтому процедура InvohtiveMonomialBasis завершается за конечное время.
Эффективность алгоритма зависит от выбора инволютивного деления. Если два деления L\ и Li таковы, что для каждого монома т Є М и подмножества U С М справедливо включение Li(m,U) С L2{m,U). то деление L,2 не менее эффективно, чем деление Li, так как для Li надо рассматривать меньше инволютивных продолжений, и мономиальный инволютивный базис относительно L\ является также мономиальным инволютивным базисом относительно Ьг.
Ниже приводится версия процедуры InvohtiveMonomialBasis, которая преобразует данное множество многочленов F во множество, порождающее тот же идеал, что и F, и такое, что его старшие мономы образуют мономиальный инволютивный базис.
Procedure InvolutiveMonomialCompletion(F,L) repeat done:=true for all x u, x Є X, и Є F do її fiv Є F :х-иЄ vL(v, F) then for all / Є F such that / = и do F:=FU{x-f} end for done:=false end if end for until done Следующая лемма позволяет построить алгоритм, вычисляющий инволютивный базис (в случае, если последний конечен).
Лемма 6 Пусть множество старших мономов F образует мономиальный инволютивный базис. Пусть также множество F инволютив-но авторедуцировано. Тогда F является инволютивным базисом идеала, им порожденного.
Шаг инволютивого маршрута Гребнера
Доказательство. По лемме 11 Hw является инволютивным базисом (7W), значит, q инволютивно редуцируется к 0 относительно Hw, то есть, существует последовательность редукций 7 i,... ,r k в схеме, отвечающей Hw, такая что r k... r i(q) = 0. Возьмем такую последовательность минимальной длины и докажем утверждение леммы по индукции по к.
Если к = 1, то q = си X inw(/i) для некоторого монома v и константы с Є К, то есть, утверждение леммы справедливо.
Если к 1, то заметим, что rj(g) — однородный многочлен той же w-степени, что и q, редуцирующийся к 0 за меньшее, чем к, количество шагов. Значит, по предположению индукции, для него существует представление вида (1). Поскольку q — r q) 4- cv х inw(/i) для некоторого монома v и константы с Є К, получаем представление вида (1) для q.
Пусть весовой вектор w согласован с отношениями порядка и С. Пусть Н — инволютивный базис / относительно , и Q = {qi,... ,q8} — инволютивный базис (7W) относительно С, полученный с помощью описанного выше алгоритма InvolutiveCompletion из Hw. Тогда многочлены qi w-однородны, так как немультипликативные продолжения и редукции относительно w-однородных многочленов сохраняют свойство w-однородности. Пусть г qi = 22Pij inw(/ij), г = 1... s, 3=1 обозначают представления вида (1) для qi, существование которых гарантировано леммой 12. Заметим также, что многочлены рц могут быть получены по ходу алгоритма InvolutiveCompletion, хотя их можно вычислить и независимо, следуя доказательству леммы 12.
Тогда F = {/j,... ,/s} — инволютивный базис I относительно C Доказательство. Пусть f Є I. Предположим, что / не редуцируем инволютивно к 0 относительно F И порядка «С. Тогда существует его инволютивная нормальная форма / ф 0. Поскольку / Є /, inw(/ ) Є /w-Так как Q является инволютивным базисом (Jw) относительно С, 3 q{ Є Q : m«fe)Lin«(inw(/ )). (3) Но по лемме 12 имеем, что inw(/j) = qi. Следовательно, in (inw(/j)) = in ((/t). Поскольку w согласован с С, выполнены следующие равенства: in«(/i) = in«(&) іп«(Л = in«(inw(/ )).
Подставляя эти равенства в (3), получим, что HI (/J)L in (/ ), то есть / инволютивно редуцируем относительно некоторого элемента множества F, противоречие с нормальностью / . Следовательно, / инволютивно редуцируется к 0, и F — инволютивный базис относительно С.
Обозначим инволютивный базис F относительно С, полученный из инволютивного базиса Н относительно с помощью формулы (2) из последней теоремы, через conv(#, , «С). Вычисление conv(#, , С) называется шагом маршрута Грёбнера. Согласно [19], определим конус Грёбнера, соответствующий идеалу І" и отношению порядка , как множество весовых векторов cone7( ) := [{w Є Пп (/ = (/w)}], где квадратные скобки обозначают замыкание в fi". В статье [37] доказывается, что множество сопе/( ) действительно являются выпуклыми многогранными конусами, и пространство весовых векторов О.71 разбивается на конечное число конусов. Справедливы следующие две леммы: Лемма 13 Если Н Н и Н — инволютивный базис идеала I относительно , то Н также является инволютивным базисом относительно С Доказательство. Так как Н = Н , то множества мономов, инволю-тивно редуцируемых относительно Н, и относительно Н, С, совпадают, откуда следует утверждение леммы.
Лемма 14 Если и С — отношения порядка, которым соответствует один и тот же конус, то есть сопе/( ) = сопе/(-С), и Н — инволютивный базис идеала I относительно , то Н также является инволютивным базисом относительно С Доказательство. Поскольку conej( ) = сопе/( С), имеем, что (/ ) = {/ ). Так как (/ ) и (/ ) являются идеалами, порожденными мономами, / = 7 . Покажем, что из этого следует равенство Н — Н .
Возьмем произвольный многочлен h Є Н и покажем, что m (h) = in g(/i). Предположим противное. Поскольку Н — инволютивный базис относительно , Я — мономиальный инволютивный базис / , то есть, для любого монома и G 1 найдется Ь! Є Я, такой что т. {Ъ!)\ьи. В частности, это справедливо для и = in (/i), причем h ф h, так как в противном случае имеем и in (/i) и in (/i)z,u, противоречие. Но наличие такого К означает, что h инволютивно редуцируем относительно H\{h} и порядка , что противоречит инволюгивной авторедуцированности множества Н.
Следовательно, Н = Я , и можно применить лемму 13.
Ниже приводится описание инволютивного маршрута Грёбнера. Пусть даны два отношения порядка на множестве мономов, и С, и пусть w.s, wt — вектора, являющиеся первыми строками в матрицах, задающих отношения порядка и С соответственно. Другими словами, = Ws и = W(. СоеДИНИМ КОНЦЫ ВеКТОрОВ Ws И Wf ОТреЗКОМ. ПуСТЬ Wi, . . . , Wjt — точки пересечения этого отрезка с границами конусов, занумерованные от w.s к Wf (конечность числа точек пересечения следует из выпуклости и конечности числа конусов).
Дифференциальное разбиение Гребнера
Размеченным характеристическим мноэюеством дифференциального идеала / называется множество дифференциальных многочленов А, такое что для каждого многочлена А отмечена одна из производных, входящих в него, и такое что А является характеристическим множеством для некоторого ранжира, относительно которого отмеченные производные являются лидерами. Для размеченного характеристического множества Л, обозначим через Id А отмеченную производную, входящую в многочлен А Є А. Обозначим через Id Л множество всех отмеченных производных для многочленов из Л. Нашей следующей целью является исследование множества всевозможных ранжиров Рикье , для которых Л является характеристическим множеством дифференциального идеала / и Ы Д = ЫЛ. По теореме 4, любой ранжир Рикье задается некоторой матрицей Q. При определении лидера сначала производные, входящие в многочлен, сравниваются относительно первой строки матрицы, то есть некоторого весового вектора w.
Пусть w Є (Жт+п)+ — весовой вектор. Для производной определим w-степенъ и как скалярное произведение (rn+j) degwu = w-(ib...,zm,0,..., 1 ,..-,0). Для дифференциального монома т — с fja ua /С, определим degw г = maxdegw ua. a Пусть А — размеченное характеристическое множество идеала /. Рассмотрим множество Сл = {w Є (Rm+n)+ I degw(ld A) degwu V А Є Д}, где u пробегает всевозможные производные, входящие в А.
Элементы множества Сд соответствуют первым строкам матриц Q, задающих ранжиры Q, такие что Л — размеченное характеристическое множество относительно Q. Из определения следует, что множество С А является пересечением (Rm+n)+ и конечного числа полупространств в Rm+", границы которых проходят через начало координат. Следовательно, множество Сj является выпуклым многогранным конусом, содержащимся в положительном квадранте. Назовем множество С дифференциальным конусом Грёбнера, а множество дифференциальных конусов для ГОСУДАРСТВЕННАЯ дифференциального идеала / — дифференциальным разбиением Грёбне ра идеала /. В отличие от полиномиального случая, дифференциальное разбиение Грёбнера может быть бесконечным. Для примера, рассмотрим / = [т]. Тогда До = { } — характеристическое множество / относи тельно лексикографического ранжира, при котором х у. Кроме того, для любого г 0, I _ / и и\ \ ду дх / является размеченным характеристическим множеством относительно того же ранжира, и ьа(Л) = {}. Дифференциальным конусом Грёбнера, соответствующим АІ, является множество Сд, = {( 1, 2, з) Є (М3)+ l i w2i}, следовательно, СЛЭСЛЭ..., где все включения строгие.
В параграфе 4.8, будет показано, что несмотря на то, что общее число дифференциальных конусов Грёбнера для дифференциального идеала может быть бесконечным, дифференциальный маршрут Грёбнера состоит из конечного числа шагов. Преобразование характеристических множеств Будем говорить, что весовой вектор w согласован с ранжиром , если для всех производных Ui,ii2 Є QU, из неравенства degwui degw 112 следует неравенство Ui 112.
Пусть А — т\ + .. .+7 — дифференциальный многочлен, представленный в виде суммы дифференциальных мономов. Пусть J = {ii,..., ц} — подмножество в {1,..., к}, такое что для всех j,f Є J, і Є {1,..., к} \ J, degw Tj = degw ту, degw TJ degw 7. Назовем дифференциальный многочлен inw A = 2 Tj w-начальной формой многочлена А. Другими словами, inw А есть сумма всех дифференциальных мономов максимальной w-степени, входящих в А. Для подмножества А С JC{U}, inw(A) = {inw(A) IЛ є Л}. Лемма 18 Если w согласован с ранжиром , и А 6 JC{U}, то \d A = ld (inwA) (7) lp A = lp (inwA) (8) ІА = їт„А (9) SA = S А (10) гк Л = rk (inwA) (11)
Доказательство. Пусть А = Т\ + .. .+7 — представление А в виде суммы дифференциальных мономов, где т\ содержит ld А в максимальной степени. Тогда degw т\ degw тг- (г Є {1,..., к}), поскольку w согласован с ранжиром . Следовательно, т\ входит в inw Л, откуда следуют равенства (7) и (11). Более того, все дифференциальные мономы, содержащие ld А, входят в inWi4, поэтому справедливы равенства (8), (9) и (10).
Дифференциальный многочлен А = т\ + ... + 7 называется w-od-нородным, если degw т\ — ... = degw rjt; по определению, degw А — degw т\. Если А,В — w-однородные дифференциальные многочлены, такие что degw A = degw В, и г — дифференциальный многочлен, такой что degw т degw А, то А + В и тА тоже w- однородны. Однако, многочлен вида 9А, где 9 Є G, не обязательно является w-однородным. Например, пусть А = { 5}, A = uv Є К{и, v}, w = (1,1,0).