Введение к работе
Актуальность темы. Данная работа относится к некоммутативной компьютерной алгебре, ока посвящена разработке алгоритмов комбинаторной теории супералгебр Ли.
Изучение алгебраических систем, заданных образующими и определяющими соотношениями, (например, групп, полугрупп, колец) началось в начале 20-го века. К настоящему моменту комбинаторная алгебра (комбинаторная теория групп, полугрупп, колец и др.) представляет собой активно развиваемое направление алгебры с широким спектром приложений. Отметим лишь фундаментальные результаты Д. Нильсена, О. Шрейера, В. Магпуса, А. Г. Куроша, А. И. Мальцева, Р. Линдона, Ф. Холла, М. Холла, А. А. Маркова, П. С. Новикова, С. И. Адяна, А. И. Кострикина, А. Л. Шмелькина, А. Ю. Ольшанского, Ю. А. Бахтурнна, М. Шутценберже, А. И. Ширшова, Е. Витта, Л. А. Бокутя, В. Н. Латышева, В. Н. Ремесленникова, О. Г. Харлампо-вич. Интенсивно развивалась алгоритмическая теория алгебр: раздел комбинаторной теории, исследующий существование алгоритмов для решения основных алгоритмических проблем в алгебре (проблемы равенства, вхождения, изоморфизма, рекурсивного базиса и т. д.). Основы алгоритмической теории свободных алгебр были заложены А. Г. Курошем и А. И. Мальцевым. А. И. Ширшовым были получены фундаментальные результаты комбинаторной и алгоритмической теории алгебр Ли. Одной из важных целей комбинаторной алгебры является построение эффективных алгоритмов, решающих определенный класс задач в конкретных областях.
Успешное применение компьютеров в последние 20-30 лет возобновило интерес к эффективным алгебраическим конструкциям. Были пересмотрены конструктивные результаты, полученные в прошлом, что привело к формированию новой самостоятельной области — компьютерной алгебры, выросшей из математики, вычислительной математики и программирования (см., например, монографии [1,2,6,9,19,20,33,36,38,65,78,93,96,102,118,120,131,132]). Разработка новых алгоритмических решений и создание их компьютерных реализаций позволяют применять новые методы совместно со всем предыдущим наработанным материалом для создания высокотехнологичной среды научных исследований с использованием символьных преобразований. В основе современных систем компьютерной алгебры лежат эффективные алгоритмы, позволяющие производить сим-
вольные вычисления. Основные преимущества систем компьютерной алгебры основаны на возможности производить большие алгебраические вычисления. Появились специализированные системы для символьных вычислений (отметим, например, АНАЛИТИК, MAPLE, MACSYMA, MATHEMATICA, AXIOM (SCRATCHPAD), GROBNER, FORM, MACAULAY, PARI, REDUCE, CAYLEY, SMP, SCHOONSHIP, GAP, DERIVE, CoCoa, SAC, AlPi). Регулярно проводятся международные конференции EUROCAL, ISSAC, SYMSAC, EUROSAM, AAECC, Computers and Mathematics, Rewriting Techniques and Applications, конференции в ОИЯИ в Дубне по применениям компьютерных вычислений в физических исследованиях.
При исследованиях в компьютерной алгебре одним из основных моментов является построение алгоритмов. Наиболее разработанным в настоящее время является коммутативный случай (например, за последние несколько лет вышел ряд монографий, посвященных технике канонических базисов идеалов колец многочленов, так называемых базисов Гребнера, [26,55,62,69,70,74,88]). В последнее время значительно возрос интерес к некоммутативной компьютерной алгебре (см., например, [7,26, 56,57, 63,64,71,72,76, 81,87,89-92,94,103,116, 117,134-136,146,169,171,171,174,181,182]). Это вызвано как внутренними потребностями вычислений в некоммутативных алгебраических системах, так и широким спектром реальных задач в теории дифференциальных уравнений и в физике (отметим нелинейные задачи, суперуравнения Кортевега-де-Фриза, уравнения турбулентности, вычисления в псевдомеханических системах, эволюционные уравнения, теории супергравитации и суперструн, пуассоновы структуры) . Ряд пакетов программ позволяет работать с некоммутативными ассоциативными алгебрами (например, BERGMAN, GROEBNER, GRAAL).
С этой точки зрения особый интерес представляют конечно определенные алгебраические системы, то есть системы, заданные конечным числом образующих и определяющих соотношений (в случае алгебр Ли отметим гамильтоновы алгебры, (супер)алгебры Ка-ца-Муди, супералгебры в теории струн). При изучении конечно определенных алгебр в первую очередь необходимо рассмотреть свойства абсолютно свободного объекта.
Изучение свободных алгебр Ли было начато М. Холлом (в 1950-м году он построил базис свободной алгебры Ли — базис Холла, [98]). Базисы Линдона-Ширшова были построены в 1958 году Ченом, Фок-
сом и Линдоном [73] и А. И. Ширшовым [48]. Затем различными авторами был построен ряд других базисов ([51,67,127,158-160,165, 175,176]). Теорема о свободе подалгебр свободных алгебр Ли была доказана А. И. Ширшовым в 1953 г., [46] (аналогичный результат для свободных колец Ли и для ограниченных алгебр Ли был получен Е. Виттом в 1956 г., [179]). А. И. Ширшов развил для алгебр Ли методы А. Г. Куроша работы с подалгебрами свободных алгебр. Канонические базисы идеалов свободных алгебр Ли были введены А. И. Ширшовым в 1962 г., [49,50]. Он доказал теорему о композиции, которая явилась основой для решения серии алгоритмических проблем теории алгебр Ли.
Идея рассмотрения наряду с коммутирующими антикоммути-рующих перемепных восходит к Грассмапу (1844 г.) и Клиффорду. Изучение супералгебр Ли началось в 1950-х годах. Основными источниками их изучения были теория супермногообразий, теория су-персимметрий, деформации алгебраических систем, гомологическая алгебра, алгебраическая топология (заметим, что свободные супералгебры Ли естественным образом возникают в теории гомотопии при рассмотрении гомотопических групп с произведением Уайтхе-да),см. [3,5,8,15,16,27,31,58,86,97,101,119,123,125,130,142-144,148, 153,170,178]. Систематическое изучение простых супералгебр Ли было начато В. Г. Кацем ([106-108]). Изучение свободных супералгебр Ли было начато Р. Ри, И. К. Бабенко, И. Л. Кантором, А. А. Михалевым, А. И. Штерном, А. И. Молевым и Л. М. Цаленко, Г. Мелансоном, см. [A3, А4,3,34,53,110,128,129,148].
Отметим статьи, обзоры и монографии, отражающие различные аспекты применения супералгебр Ли в теоретической физике: [59,77,84,95,104,109,139,177]. 22-градуированные алгебры (супералгебры) успешно применялись в исследованиях в алгебре (например, [18,111-114,162,180]).
Обобщенные (цветные) супералгебры Ли были введены Р. Ри в 1960 г. ([148]). В теоретической физике и теории операторов они естественно возникают как обобщения алгебр и супералгебр Ли ([35,122,137,151,152,154,172,173]). Ряд общих аспектов этой теории отражен в обзоре [126]. Начато изучение тождеств в цветных супералгебрах Ли ([А1,60,61]).
Методы исследования подалгебр свободных алгебр близки к теоретико-групповым методам и восходит к Нильсену и Шрайеру (см. [29,30,141,157]). А. Г. Курош и его школа начали исследова-
ниє относительно свободных алгебр и их подалгебр ([11-14,23-25,47] и др.).
Канонические формы элементов различных алгебраических систем неоднократно использовались для решения алгоритмических проблем. Истоки таких расследований лежат в теории (полу)групп, теории графов, теории колец многочленов (см., например, [100,140]). В некоммутативном случае различные варианты леммы о композиции (о слиянии) применялись в свободных неассоциативных алгебрах (А. И. Жуков [14]), в свободных алгебрах Ли (А. И. Ширшов [49]), в свободных ассоциативных алгебрах (Л. А. Бокуть [7], Дж. Бергман [64], Д. Аник [56], В. Н. Латышев [26], Е. С. Голод [91]).
Свободное дифференциальное исчисление для свободных групп было введено Фоксом в [85]. Дж. Бирман [66] получила матричный критерий распознавания автоморфизмов свободных групп. В [40] У. У. Умирбаев доказал аналог этого результата для свободных алгебр Ли (Ройтенауэр в [149] и В. Шпильрайн в [163] также получили этот критерий; более общая ситуация была рассмотрена В. Шпиль-райном в [163] и У. У. Умирбаевым в [42]). О. Г. Харлампович в [45] использовала свободное дифференциальное исчисление в связи с изучением условия Линдона для алгебр Ли. У. У. Умирбаев в [43] получил критерий для того, чтобы система элементов свободной группы имела данный ранг. В работе [164] В. Шпильрайн определил понятие ранга элемента свободной алгебры Ли и получил описание ранга однородного по длине элемента свободной алгебры Ли в терминах размерности линейного подпространства смешанных частных производных этого элемента.
Отметим основные монографии, в которых затрагиваются различные аспекты комбинаторной теории алгебр Ли: [10] Н. Джекоб-сона, [39] Ж.-П. Серра, [4] Ю. А. Бахтурина, [22] А. И. Кострикина, [37] Ю. П. Размыслова, [17] В. Г. Каца, [150] К. Ройтенауера, [68] Л. А. Бокутя и Г. П. Кукина, а Также обзор [115] О. Г. Харлампович и М. В. Сапира. По комбинаторной теории супералгебр Ли вышло две монографии: [А1] Ю. А. Бахтурина, М. В. Зайцева, А. А. Михалева и В. М. Петроградского, и [А2] А. А. Золотых и А. А. Михалева. По общей теории супералгебр Ли следует упомянуть монографии [155] М. Шойнерта, [5] Ф. А. Березина, [27,28] Д. А. Лейтеса, [80] Б. де Витта.
Таким образом, в рамках некоммутативной компьютерной алгебры сформировалось активно развивающееся новое направление —
комбинаторная теория супералгебр Ли, к которой относится и данная диссертация.
Можно выделить четыре взаимосвязанных направления в компьютерной алгебре: системы символьных преобразований; алгоритмы компьютерной алгебры; сложность алгоритмов; приложения. Под системами понимается развитие языков программирования и сопутствующего программного обеспечения символьных преобразований. Теория алгоритмов компьютерной алгебры связана с исследованием эффективных математических алгоритмов для работы с алгебраическими объектами. Оценки сложности алгоритмов чрезвычайно важны при их практической реализации. Приложения относятся к символьным вычислениям в широком спектре областей знаний и дают важный стимул для развития систем и алгоритмов. Данная диссертация относится ко второму направлению из этих четырех (а именно, к построению алгоритмов и их математическому обоснованию), рассмотрение вопросов сложности созданных алгоритмов ограничивается лишь некоторыми комментариями, поскольку серьезный анализ такого рода составляет самостоятельное паправление, основанное на других методах и идеях.
Цель работы. Целью работы является создание среды символьных вычислений в супералгебрах Ли, основанной на новых результатах автора в комбинаторной теории супералгебр Ли.
Методы исследования. В работе используются последние достижения комбинаторной и компьютерной алгебры, а также следующие разработанные автором методы и техника исследования свободных супералгебр Ли:
техника канонических базисов в символьных преобразованиях;
методы исследования подалгебр свободных алгебр;
свободное дифференциальное исчисление в супералгебрах Ли.
Научная новизна. Основным результатом работы является построение системы алгоритмов комбинаторной теории супералгебр Ли, позволяющих производить символьные вычисления в свободных супералгебрах Ли и в супералгебрах Ли, заданных образующими и определяющими соотношениями (глава 5, алгоритмы 1-51). Эта система алгоритмов состоит из четырех групп алгоритмов:
I алгоритмы линейных вычислений в свободных супералгебрах Ли (параграф 5.1, алгоритмы 1-22);
II алгоритмы, основанные на свойствах приведенных подмножеств (параграф 5.2, алгоритмы 23-28);
-
алгоритмы, использующие канонические базисы идеалов (параграф 5.3, алгоритмы 29-39);
-
алгоритмы, использующие свободное дифференциальное исчисление (параграф 5.4, алгоритмы 40-51).
Алгоритмы изложены в стандарте, принятом в компьютерной алгебре. Основными алгоритмами данной системы являются следующие:
алгоритмы линейных вычислений в свободных супералгебрах Ли (алгоритмы 1-13, 15, 17);
алгоритмы для определения, является ли элемент свободной ассоциативной алгебры суиерлиевским, или нет (алгоритмы 14,
16);
алгоритм для извлечения «квадратного корня» из четного элемента свободной супералгебры Ли (алгоритм 20);
алгоритм преобразования подмножества к приведенному виду (алгоритм 24);
алгоритм для решения проблемы вхождения в конечно порожденную подалгебру свободной супералгебры Ли (алгоритм 26);
алгоритм построения канонического базиса идеала свободной супералгебры Ли, порожденного однородными элементами (алгоритм 32);
алгоритмы приведения к каноническому виду элемента супералгебры Ли, заданной образующими и устойчивым или однородным множеством определяющих соотношений (алгоритмы 33, 34);
алгоритмы для решения проблемы равенства в супералгебрах Ли, заданных устойчивым или однородным множеством определяющих соотношений (алгоритмы 35, 36);
алгоритмы построения канонического базиса супералгебры Ли, заданной однородным или устойчивым множеством определяющих соотношений (алгоритмы 37, 38);
алгоритмы нахождения ранга подалгебр (алгоритмы 24, 40);
алгоритмы для распознавания автоморфизмов свободной (^)су-пералгебры (алгоритмы 28, 46);
алгоритм «интегрирования» суперлиевского элемента по его частным производным (алгоритм 43);
алгоритмы нахождения ранга (р-) суперлиевского элемента (системы элементов) и определения примитивности элемента и системы элементов (алгоритмы 44, 45);
алгоритмы реализации ранга системы элементов и алгоритм построения дополнения к примитивной системе элементов до множества свободных образующих свободной (р-)супералгебры Ли (алгоритмы 49-51).
Отметим, что алгоритмы, связанные с определением рангов и примитивностью систем элементов были получены в соавторстве с А. Л. Золотых при равном вкладе авторов.
Теоретические результаты глав 1-4 являются математическим обоснованием построенных алгоритмов (в частности, они гарантируют корректность алгоритмов и завершение их работы за конечное число шагов). Основными среди них являются следующие:
-
для свободных супералгебр Ли построены линейные базисы и доказана эквивалентность свойств Нильсена и Шрайера, что дает основу для алгоритмических исследований свободных супералгебр Ли (как следствие получена теорема о свободе подалгебр и исследованы свойства подалгебр), (теоремы 1,2, 6-20);
-
для супералгебр Ли и р-супералгебр Ли доказана теорема о композиции (супер-аналог теоремы А. И. Ширшова о композиции) , что дает возможность ввести понятие канонического базиса идеала свободной (р-)супералгебры Ли. В качестве следствий получен базис свободного произведения с объединенной подалгеброй, а также аналог теоремы Пуанкаре -Биркгофа-Витта для дифференциальных супералгебр Ли, (теоремы 25, 32-35);
-
получены результаты о строении подпространств суперлиев-ских элементов свободной ассоциативной алгебры, в частности, найдена структура супералгебр перемешиваний, построены базисы образов внутренних дифференцирований элементов свободных суперколец Ли (теоремы 3-5, 31);
-
для свободных (р-)супералгебр Ли развито свободное дифференциальное исчисление (универсальные дифференцирования, являющиеся аналогами частных производных Фокса в свободных группах):
4а) доказано, что для этих алгебр справедлива гипотеза о якобиане (аналог теоремы Дж.Бирман для свободных групп) (теоремы 37, 38);
46) доказана дифференциальная и финитная отделимость подалгебр (теоремы 26, 28);
4в) рассмотрены орбиты элементов при действии группы автоморфизмов; получен критерий того, что элемент имеет данный ранг (ранг элемента — это наименьшее число свободных образующих, от которых зависит его образ после применения автоморфизма); получены критерии для определения ранга систем элементов; показано, что тестовые элементы мономорфизмов свободных (р-)супералгебр Ли — это элементы максимального ранга, (теоремы 41-45);
5) для примитивных элементов свободных алгебр и супералгебр
Ли получены следующие результаты:
5а) получен критерий примитивности элемента и системы элементов в терминах обратимости матрицы частных производных (решение дифференциального варианта проблемы Серра для алгебр Ли и супералгебр Ли); доказано, что эндоморфизм свободной (^-)супералгебры Ли, сохраняющий свойство примитивности элементов, является автоморфизмом (теоремы 45, 46, 48);
56) построен пример несвободной алгебры Ли когомологической размерности один (три образующих и одно определяющее соотношение; универсальная обертывающая алгебра
этой алгебры Ли является свободной ассоциативной алгеброй ранга два), что дает отрицательное решение проблемы о справедливости аналога теоремы Столлингса-Суона для алгебр Ли (теорема 47).
Отметим, что результаты 4в и 5а были получены совместно с Л. А. Золотых, а 56 — совместно с А. А. Золотых и У. У. Умирбаевым при равном вкладе авторов. А. С. Штерн в [53] независимо построил базис в свободной супералгебре Ли над полем и показал, что справедлива теорема о свободе подалгебр и что четная компонента свободной супералгебры Ли имеет счетный ранг. Примыкающая теорема о свободе Z-градуированных подалгебр свободных супералгебр Ли была доказана Лемейром в [119].
Практическая ценность. Работа носит теоретический характер. Построенная система алгоритмов может быть и уже используется в теоретических исследованиях (так, с ее помощью было найдено отрицательное решение проблемы о справедливости аналога теоремы Столлингса-Суона для алгебр Ли). В ряде случаев (даже для обычных алгебр Ли) построенные алгоритмы оказываются эффективнее имеющихся. Эти алгоритмы могут быть использованы при символьных вычислениях в суперструктурах теоретической физики. В диссертации разобран ряд конкретных примеров вычислений в свободных супералгебрах Ли с использованием построенных алгоритмов. Изложение алгоритмов позволяет включать их в системы компьютерной алгебры. Часть алгоритмов реализована в виде пакета программ А. А. Золотых и А. А. Михалева, включенного на дискете в их монографию [А2] (этот пакет содержит, в частности, базовую арифметику вычислений в свободных супералгебрах Ли, краткое изложение которой приведено в параграфе 5.6).
Апробация работы. Результаты диссертации докладывались на семинарах по алгебре, по компьютерной алгебре и по программированию в Московском Государственном университете, на алгебраических семинарах Варшавского университета, на международных конференциях по алгебре (Новосибирск 1989, Барнаул 1991, Красноярск 1993), на 5-й научной школе по теории многообразий алгебраических систем (Барнаул 1988), на 4-й научной школе «Алгебры Ли и их применения в математике и физике» (Казань 1990), на 6-й научной школе по теории многообразий алгебраических систем
(Магнитогорск 1990), на 6-м симпозиуме по теории колец, алгебр и модулей (Львов 1990), на 1-м Европейском математическом конгрессе (Париж 1992), на 3-й Международной конференции по неассоциативной алгебре (Овьедо 1993), на Международной конференции «Алгебра и анализ» (Казань 1994), на Международном математическом конгрессе (Цюрих 1994), на Международной конференции по теории полугрупп (С-Петербург 1995), на 7-м международном симпозиуме по формальным рядам и алгебраической комбинаторике (Марн-ля-Вал-ле 1995), на конференции «Интеллектуальные системы и компьютерное моделирование» (Москва 1995), на конгрессе молодых ученых «Молодежь и наука: взгляд в третье тысячелетие» (Москва 1996).
Публикации. Результаты диссертации опубликованы в 40 работах автора, список которых приводится в конце автореферата (цикл работ [А16, А18-А21, А24-А26, А28, А40] выполнен в соавторстве с А. А. Золотых; работы [А17] и [А29] выполнены в соавторстве с А. А. Золотых и У. У. Умирбаевым; работа [АЗО] выполнена в соавторстве с Е. А. Васильевой; монография [А1] написана в соавторстве с Ю. А. Бахтуриным, М. В. Зайцевым и В. М. Петроградским; монография [А2] написана в соавторстве с А. А. Золотых).
Объем работы. Диссертация изложена на 291 страницах и состоит из введения и пяти глав. Библиография содержит 298 наименований.
