Допустимые упорядочения и стандартные базисы дифференциальных идеалов

1.1 Актуальность темы.

В последние пятнадцать лет был достигнут значительный прогресс в области компьютерной алгебры Одной из ее приоритетных задач являе1ся развитие методов решения систем нелинейных ал! ебраических уравнений от нес кольких переменных, а 1акже методов изучения ал! ебраических идеалов, порожденных нелинейными полиномиальными сисчемами Настоящим прорывом в данной области стало появление базисов Гребнера и алюритма их вычисления, предложенно1 о Б Бухбертером в середине 1960;х годов [5, 2, 9] Теория исключений, использовавшаяся ранее для решения систем, оказалась час1ыо новой 'теории, позволяющей приводить произвольную систему уравнений к стандартному виду Неудивительно, чю впоследствии стали разрабатываться различные обобщения понятия базиса Гребнера полиномиального идеала на прочие алгебраические структуры.

Одной из таких структур явились дифференциальные идеалы в кольце дифференциальных мноючленов, моделирующие системы дифференциальных ал1 ебраических уравнений в юм же смысле, в каком полиномиальные идеалы моделирую1 сииемы обычных алгебраических уравнений Для радикальных дифференциальных идеалов в кольце дифференциальных многочленов над алгеброй Рит та был создан эффекiивный метод разложения на характеризуемые компоненты [4, 3, 25], позволяющий, в частности, проверив принадлежность дифференциально! о миоючлспа такому идеалу и ииледоваiь строение множества решений Для произвольных бесконечно порожденных дифференциальных идеалов была доказана алгоритмическая неразрешимое! ь задачи принадлежнос1 и [16] Однако для нерадикальных конечно порожденных идеалов вопрос об алгоритмическом решении задачи принадлежности до сих пор открыт.

Дифференциальные стандартные базисы, появившиеся в hcmhoi о отличающихся формах в конце 1980;х гг в работах Ф Оливье [35, 36] и Дж Kappa Ферро [6], являются прямым и естественным обобщением понятия базиса Гребнера, но не позволяю i полное гыо решить задачу принадлежности Сами основатели 1еории подмегили, чю для многих идеалов они могут быть бесконечными 3roi факт на несколько лег приостановил дальнейшие исследования в этой области Однако не так давно автором были получены неожиданные примеры конечных дифференциальных стандартных башсов [59. 63], что снова возродило ишерес к данной теме Автор работы обнаружил связь между процессом редукции Г Леви [30], дающим алгориш проверки принадлежно (1и монома идеалу [ур], и дифференциальными с тан-дар пшми базисами Оливье и Карра Ферро, появившимися поч1И через 50 ле 1 Долioe время (чипиюсь, что стандартные базисы бесконечны даже у таких сравнительно просю ус троенных идеалов, как [?/]. Однако выяснилось, что при более общих упорядочениях идеалы вида [ур приобретают конечный дифференциальный стандартный базис {ур} Такие общие упорядочения (например, degrevlex) являю i с я вполне ec’Teci венными при вычислении башсов Гребнера полиномиальных идеалов. В ю же время в дифференциальном случае они не обладают иекоюрыми свойствами согласованноеiи с дифференцированиями, и потому не рассматривались основа1елями 1еории Грубо юворя, Оливье и Карра Ферро применяли лишь лексикографическое и сначала по степени, затем лексикографическое упорядочения.

1.2 Цель работы.

Целью насюящей рабош являе! ся изучение критериев конечности дифференциальных стандартных базисов идеалов обыкновенно! о кольца дифференциальных многочленов F{y} над нолем консишт Т Перед автором возникли следующие задачи.

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

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

• установить необходимые и досшточные условия конечности дифференциальных стандартных базисов при определенных упорядочениях,.

• с формулировка ib и реализовать в системах компьютерной алюбры алго-ри1м, вычисляющий коночный дифференциальный стандартный базис при определенных упорядочениях.

• изучить поведение дифференциальных стандартных базисов и задачу о принадлежнос ги дифференциального многочлена идеалу при композиции mhoi очлеиов.

Эти задачи успешно решены автром в данной pa6oie 1.3 Научная новизна.

Научная новизна диссертции состоит в следующем.

1 Рассмотрены допустимые упорядочения дифференциальных мономов без дополнительных предположений об их дифференциальных свойствах В частности, доказана полная упорядоченность множества дифференциальных мономов (в ошичие от [48, б, 36]) Исследован феномен сокращения мономов в производных многочлена Усыновлено, что при определенных упорядочениях могут сокращаться С1аршие мономы производных с’ла1аемых многочлена Предложен и реализован в еислеме компышерной алгебры Maple 10 алгоритм, сiроящий дифференциальным многочлен (если он су щес i вует), в ко юром сокращается заданная в общем виде последовательность мономов.

2 Предложено описание упорядочений на дифференциальных мономах в терминах согласованною набора мономиальных матриц (или, чю эквивалентно, с помощью «бесконечных» матриц особого вида). Ранее некоторая довольно громоздкая классификация в терминах линейных форм (предложенная Ф Вайспфеннингом [47, 48]) существовала лишь для довольно узкого класса упорядочений, не охватывающего все требуемые случаи Выделены различные классы упорядочений в зависимоеiи от их связи с дифференцированиями Эти классы обобщают частые случаи лексико! рафического упорядочения (рассмотренного Оливье и Карра Ферро [6, 7, 36]) и упорядочения clegrevlex (неявно применяемою в pa6oie Леви [30]).

3 Дано необходимое и достаточное условие сущее! вования конечною дифференциального сгандарi ного базиса заданно! о идеала при определенных классах упорядочений, что усиливает и распросфаняе! резуль-1аты Карра Ферро [7] для лексикографическо1 о упорядочения Приведены новые примеры конечных и параметрических дифференциальных (ындартых базисов Предложен и реализован 1ак называемый «улучшенный процесс Оливье», заведомо остнавливаклцийся и возвращающий редуцированный дифференциальный стндартный базис идеала в случае его конечноеiи1 Получена связь между дифференциальными ыандаршыми базисами и наборами базисов Гребнера соотве! ствующих полиномиальных идеалов.

4 Резулыаш X Хоша [19, 20] о поведении базисов Гребнера при композиции мноючленов обобщены на дифференциальный случай С помощью доказанных теорем о композиции и работы Леви [30] получено дост1 очное условие существования конечного дифференциальною стандартною базиса при /^-упорядочениях Сформулировано в виде ГШЮ1С5Ы анало1Ичное необходимое условие Исследована (совместно с М В Кондратьевой) задача принадлежности многочлена дифференциальному идеалу, порожденному композицией многочленов ее решение сведено к решению более просюй (с алгоритмической ючки зрения) задачи принадлежносш.

Заключение

.

В работе рассматривались дифференциальные стандартные базисы идеалов (в смысле Дж Карра Ферро [б, 7] и Ф Оливье [36]) обыкновенного кольца дифференциальных многочленов oi одной независимой переменной при самых общих допустимых упорядочениях Доказано, чю каждое допустимое упорядочение на множестве мономов такою кольца задается каноническим согласованным набором мономиальных матриц, или, что эквивалентно, бесконечной матрицей определенного вида. Это обобщает хорошо известный результат о задании мономиальных упорядочений в случае обычных мономов от конечною числа переменных Были введены определенные классы упорядочений на дифференциальных мономах и установлены зависимости между ними Наиболее важные из них указаны на схеме в приложении А.1. Полученная теория была применена к доказательству критериев конечности дифференциальных стандартных базисов Для^{-лексикографических} стандартных базисов этот критерий сводился к существованию квазилинейного мноючлена в идеале Было установлено, чю конечность^{-фиксированных} базисов влечет конечност ь лексикографических базисов, что определяет особую роль чистого лексикографическото упорядочения На основе полученных критериев был разработан «улучшенный процесс Оливье», вычисляющий редуцированный (^-лексикографический дифференциальный стандартный базис идеала и всегда (в отличие от оригинально! о процесса Оливье) заканчивающий работу па идеалах с конечным таким базисом Он был реализован в системе компьютерной алгебры Maple С помощью компьютерных вычислений были получены новые примеры конечных и параметрических базисов.

Отдельно были рассмотрены вопросы конечности дифференциальных стандартных базисов относительно /^-упорядочений, а также разработана теория поведения дифференциальных стандартных базисов при композиции мноючленов Среди допустимых композиций (при определенных упорядочениях) оказались лишь композиции с квазилинейными мноючленами С помощью этих результатов было установлено, что идеалы вида [/" ], где / квазилинейный мноючлен, обладают конечным дифференциальным стандартным базисом из самою fn при любом согласованном с квазили-пеиностью /3-упорядочении Было также предложено в качестве гипотезы необходимое условие конечности дифференциальных стандартных базисов при согласованных с квазилинейное: ыо /^-упорядочениях В pa6oie было 1акже изучено явление сокращения заданной последовательное iи мономов в производных многочленов (в частности, сокращения старших мономов в производных при упорядочениях, не являющихся строю (^-устойчивыми).

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

• изучение «интегральных» дифференциальных идеаловдоказательство гипотезы 1 (или эквивалентной ей гипотезы 2) об интегральных свой-с твах дифференциальных идеалов [у11 ],.

• доказательство гипотезы 3, дающей необходимое условие конечности дифференциальных стандартных базисов при согласованных с квазилинейное гыо /^-упорядочениях;

• построение1 идеала, не имеющего конечною дифференциального стандартною базиса ни при каком упорядочении,.

• дальнейшее исследование классов допустимых упорядочений на дифференциальных мономах, исследование аналогов веера Гребнера в дифференциальном случае, построение аналога универсального базиса Гребнера [2],.

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

• построение (если эю возможно) алгоритма проверки существования в идеале квазилинейного (линейного) мноючлена;

• обобщение всех полученных результатов на случай нескольких дифференцировании и нескольких независимых переменных,.

• разработка теории рекурсивных дифференциальных стандартных базисов.

Все поставленные задачи гесно связаны (о следующей глобальной задачей сцщсствупп ли алгоритм проверки принадлежности дифференциального многочлена конечно пороподенному дифференциальному идеалу в кольче duefxfiepe нциальныг многочленов Т{у}'1' Как было сказано в начале рабо-I ы, л, а задача положи i ел ьио решена лишь в некоюрых частных (но важных) случаях Данная работа позволяет расширить круг идеалов, для которых известно алторитмическое решение задачи принадлежности.