МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В.Ломоносова

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи

УДК 512.554.3

Леонтьев Александр Владимирович

Нижние оценки алгебраической сложности

для некоторых классов алгебр

01.01.06 математическая логика, алгебра, теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2011г.

Работа выполнена на кафедре высшей алгебры Механико-Математического факультета Московского государственного университета им. М.В. Ломоносова

Научный руководитель: доктор физ.-мат. наук, профессор Латышев Виктор Николаевич;

Официальные оппоненты: доктор физ.-мат. наук, профессор Михалев Александр Александрович;

кандидат физ.-мат. наук Жданович Дмитрий Валентинович

Ведущая организация: Московский педагогический государственный университет

Защита диссертации состоится 21 января 2011 г. на заседании Диссертационного совета Д 501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ, Механико-Математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механикоматематического факультета МГУ (Главное здание, 14 этаж)

Автореферат разослан 21 января 2010 г.

Ученый секретарь Диссертационного совета Д 501.001. доктор физико-математических наук, профессор А.О. Иванов

1

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Так, в последнее время определенное внимание уделяется сложности вычислений, производимых в алгебрах над полями с билинейным законом умножения. Кроме упоминавшейся уже собственно алгебры полиномов, это вычисление систем билинейных форм, различные расширения полей, различного рода конечномерные ассоциативные алгебры, в частности матричная алгебра, алгебры Ли и многие другие объекты.

В настоящей диссертации рассмотрены вопросы построения нижних оценок для операций (произведений) в следующих классах алгебр: простые классические алгебры Ли серий Al, Bl, Cl, Dl ; нильпотентные и разрешимые алгебры Ли; нильпотентные ассоциативные алгебры. Все алгебры предполагаются конечномерными, характеристика поля равна нулю.

1.2 Обзорные замечания 1.2.1 Алгебры с делением Для некоторых небольших алгебр с делением сравнительно быстро были установлены верхние и нижние оценки.

Так, некоторыми авторами было показано, что поле комплексных чисел, рассматриваемое как алгебра над R, имеет сложность 3.

В 1970-ых годах Dobkin, de Groote, Howell и Lafon, Stross показали, что сложность алгебры кватернионов над R равна В 1977г. Fiduccia и Zalcstein показали, что для алгебры с делением A выполнена оценка (Если A является простым расширением поля, то равенство достигается.) 1.2.2 Матричная алгебра (верхние оценки) Без всякого преувеличения можно утверждать, что наибольшие усилия в изучении сложности алгебр были направлены на матричную алгебру. Перечисление всех работ в этой области было бы затруднительно. Отметим лишь некоторые из них.

Обычный (классический) алгоритм умножения матриц (строка на столбец) требует n3 умножений и n2 (n 1) сложений.

Более быстрый по порядку алгоритм типа разделяй и властвуй“ предложен Штрассеном в 1970г. Первоночально Штрассен представил алгоритм умножения в матричной алгебре M имеющий 7 умножений чисел вместо 8 умножений классического алгоритма. Таким образом была доказана неоптимальность классического алгоритма перемножения матриц. Этот алгоритм может быть распространен на матрицы более высоких порядков рекурсивно (посредством блочного разбиения матриц). На каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате сложность этого алгоритма составляет O(nlog2 7 ) O(n2.807 ). Недостатком данного метода является большая сложность программирования по сравнению со стандартным алгоритмом, численная неустойчивость и большой объём используемой памяти. Разработано большое количество алгоритмов на основе метода Штрассена, которые улучшают его численную устойчивость и объём используемой памяти.

В 1978г. Пан предложил свой метод умножения матриц, сложность которого составила O(n2.78041 ).

В 1979г. группа итальянских учёных во главе с Бини разработала алгоритм умножения матриц с использованием тензоров. Его сложность составляет O(n2.7799 ).

В 1981г. Шёнхаге представил работающий со сложностью O(n2.695 ) метод, который он назвал частичным матричным умножением. Позже ему удалось получить оценку O(n2.6087 ).

Затем Шёнхаге создал метод, названный методом прямых сумм, сложность которого составляет O(n2.548 ). Романи сумел понизить оценку до O(n2.5166 ), а Пан до O(n2.5161 ).

В 1990г. Копперсмит и Виноград опубликовали алгоритм, умножающий матрицы со сложностью O(n2.375 ). Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день алгоритм Копперсмита-Винограда является наиболее быстрым, но он эффективен на очень больших матрицах и поэтому не применяется.

В 2003–2006г. Кох и др. рассмотрели в своих работах алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали (высказали гипотезу) возможность существования алгоритмов умножения матриц со сложностью O(n2 ).

1.2.3 Нижние оценки для некоторых ассоциативных алгебр Нижних оценок в теории сложности известно немного. Для ассоциативных алгебр известны следующие оценки.

Так, например, в 1971г. Hopcroft и Kerr и Winograd показали, что В 1977г. Fiduccia и Zalcstein и Winograd установили сложность алгебры, порожденной одним элементом: если f k[t] ненулевой полином степени n с m различными простыми факторами, то Как уже упоминалось ранее в разделе 1.2.1 для алгебр с делением A выполнена оценка В 1978г. Brockett и Dobkin и Lafon и Winograd для матричной алгебры установили оценку Для ассоциативных конечномерных алгебр с единицей в 1981г. доказана1 также обобщающая оценка:

Alder A., Strassen V., On the algorithmic complexity of the associative algebras. // Theor. Comp. Sci. 1981, 15, 201–211.

Теорема 1.1 (A.Alder, V.Strassen). Пусть A произвольная (конечномерная, с единицей, ассоциативная) алгебра. Тогда для числа нескалярных умножений Cm (A) выполнена следующая оценка:

число максимальных двусторонних идеалов в A.

где T Также: если A/ Rad(A) A1... At (здесь Rad(A) радикал Джекобсона), то Нелинейные нижние оценки сложности умножения матриц отсутствуют. В 2002 году Ран Раз доказал нижнюю оценку O(n2 log n) для сложности умножения квадратных матриц порядка n в модели с ограниченными коэффициентами.

В 1999г. году Маркус Блазер2 (с учетом обобщения ранее полученных результатов) доказал, что умножение матриц над произвольным полем требует не менее операций умножения чисел. Для алгебры верхнетреугольных матриц Tn (с ненулевыми элементами на главной диагонали) получена нижняя оценка (Отметим, что в работе также дана характеризация так называемых алгебр минимального ранга.) Амир Шпилька в 2001 году улучшил результат Блазера для конечных полей:

Markus Blaser, A 2.5 n2 -lower bound for the rank of n x n-matrix multiplication over arbitrary elds. // Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS), 45-50, 1999.

для поля GF (2) и для поля GF (p).

Существует гипотеза о том, что сложность умножения матриц порядка n равна 1.2.4 Групповые алгебры Известен ряд результатов о сложности выполнения операций в групповых алгебрах. Имеется цикл работ (2004–2008г.) Алексеева В.Б., Поспелова А.Д. в этой области. Они исследовали, в частности, групповые алгебры, образуемые абелевыми группами. Также изучались некоммутативные групповые алгебры групп подстановок третьего порядка, симметрий квадрата и четных подстановок четвертого порядка, установлена связь сложности умножения в этих алгебрах со сложностью умножения квадратных матриц второго и третьего порядков.

Так, например, в 6-мерной групповой алгебре C(S3 ) над полем комплексных чисел, базисом которой являются подстановки третьего порядка, найден билинейный алгоритм для умножения с мультипликативной сложностью 9 (вместо тривиальных 36) и доказано, что эта оценка неулучшаема.

В.М. Сидельников, Л.С. Казарин рассмотрели линейное представление (нерегулярное) Dn диэдральной группы порядка 2n с помощью (n n)-матриц с элементами из конечного поля GFq и показали, что если число n взаимно просто с характеристикой поля GFq, то групповая алгебра ADn является прямой суммой колец, каждое из которых изоморфно полному кольцу (2 2)-матриц с элементами из поля GFni, где числа ni опреq деляются степенями неприводимых многочленов, на которые разлагается многочлен xn 1 над полем GFq. Этот результат, объединенный с подобным результатом, полученным авторами ранее для циклической группы, позволяет уменьшить сложность умножения в конечном поле GFi и в кольце матриц второго порядка над полем GFq.

1.2.5 Антикоммутативные алгебры и алгебры Ли В 1993г. в работе Горбацевич В.В. рассмотрел пространство всех конечномерных комплексных антикоммутативных алгебр.

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

В 1990–93г. в заметках и Жошина С.А. рассмотрела мультипликативную сложность простых алгебр типа Al, Bl, Cl, Dl, G2, F4, E6, E7, E8, и полупростых алгебр Ли (прямая сумма простых) над полями. (Хотя в работах и не указана характеристика поля, судя по доказательству, она равна нулю.) В частности, доказаны следующие теоремы3 :

Теорема 1.2 (Жошина С.А.). Пусть L простая алгебра Ли одного из типов G2, F4, E6, E7 или E8. Тогда ее тензорный ранг оценивается снизу неравенством rk (L) dim(L) 1 + f,где Теорема 1.3 (Жошина С.А.). Пусть L простая алгебра Ли одного из типов Al, Bl, Cl или Dl. Тогда ее тензорный ранг оценивается снизу неравенством Жошина С.А., О мультипликативной сложности алгебр Ли. // Вестн. Моск.

Ун-та. Сер. 1, Математика. Механика. 1990, 4, 75–77.

Жошина С.А., О мультипликативной сложности простых алгебр Ли G2, F4, E6, E7, E8 и полупростых алгебр Ли.// Вестн. Моск. Ун-та. Сер. 1, Математика. Механика. 1993, 4, 35–37.

Теорема 1.4 (Жошина С.А.). Пусть L полупростая алгебра Ли. Она представляется в виде прямой суммы простых алгебр Ли L1... Lm. Тогда где f определены выше.

1.3 Цель диссертации Целью диссертации является изучение сложности операций (произведений) в ассоциативных алгебрах и алгебрах Ли над полями характеристики ноль и получение нижних оценок для числа нескалярных умножений при выполнении этих операций (оценка тензорного ранга).

1.4 Научная и практическая ценность Работа имеет теоретический характер. Установленные нижние оценки могут быть применены для характеризации сложности умножения в рассматриваемых классах алгебр и оценки эффективности оптимальных алгоритмов. Работа содержит примеры применения полученных оценок.

1.5 Методы исследования В диссертации используются модели и методы теории сложности; структурные результаты по классификации простых алгебр Ли серий Al, Bl, Cl, Dl над полями характеристики ноль;

классификация алгебр Ли малых размерностей над полями комплексных чисел C и действительных чисел R; основные факты о строении алгебр Ли.

1.6 Публикации По теме диссертации опубликовано 4 работы [1]– [4], из них 3 работы в журналах, содержащихся в перечне ВАК. Все результаты получены автором лично.

1.7 Апробирование Результаты диссертации докладывались: на Международной алгебраической конференции (МГУ, Москва, 2008); на научно-исследовательском семинаре при кафедре высшей алгебры МГУ (2010); на расширенном семинаре исследовательского центра искусственного интеллекта Института программных систем РАН (2010).

1.8 Гипотеза о мультипликативной сложности простых алгебр и несколько замечаний о доказательствах теорем В кругу специалистов по теории сложности известна гипотеза (по всей видимости фольклорного“ происхождения) о мультипликативной сложности простых алгебр: асимптотическая сложность простых алгебр в важнейших классах по крайней мере в 2 раза превосходит размерность алгебр. Ее появление связано скорее всего с работами Brockett и Dobkin, Lafon и Winograd, A.Alder, V.Strassen, где было доказано, что сложность ассоциативных (и, в частности, матричных) простых алгебр в 2 раза асимптотически превосходит размерность самих алгебр. В настоящей работе этот вопрос рассматривается для простых классических алгебр Ли серий Al, Bl, Cl, Dl (см. ниже).

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

В данной работе метод подстановки также является основным. Синтаксический выбор переменных для обнуления структурного тензора по большей части сходен с работой A. Alder, V. Strassen1.

1.9 Научная новизна Все результаты диссертации являются новыми. Установлены или улучшены нижние оценки для числа нескалярных умножений при выполнении операций в следующих классах алгебр (характеристика поля всюду равна нулю, все алгебры конечномерны):

• для простых классических алгебр Ли серий Al, Bl, Cl, Dl (асимптотически в 2 раза улучшена оценка Жошиной3 ) тем самым доказана гипотеза о том, что сложность простых классических алгебр Ли асимптотически по крайней мере в два раза превосходит размерность алгебр (теорема 2.5);

• для произвольных нильпотентных алгебр Ли; приведены примеры достижимости полученных оценок для алгебр различных размерностей, также показано, что константы при слагаемых, участвующих в оценке, не могут быть повышены (теорема 2.9, теорема 2.11);

• для произвольных разрешимых алгебр Ли (теорема 2.12, теорема 2.13);

• для произвольных нильпотентных ассоциативных алгебр;

приведены примеры достижимости полученных оценок для алгебр различных размерностей; также показано, что константы при слагаемых, участвующих в оценке, не могут быть повышены (тем самым расширен класс оцениваемых произведений по сравнению с результатом A. Альдера и V. Штрассена1 и М. Блазера2 ) (теорема 2.18, теорема 2.20).

Кроме того, полученные оценки применены:

• к нильпотентным алгебрам Ли малых размерностей над полями R и C (классификация которых была получена другими авторами ранее);

• к нильпотентной строго верхнетреугольной матричной алгебре Ли (теорема 2.10);

• к разрешимой строго верхнетреугольной матричной алгебре Ли (теорема 2.14);

• к ассоциативной нильпотентной строго верхнетреугольной матричной алгебре (теорема 2.19).

Применение полученных оценок к верхнетреугольным матричным алгебрам (нильпотентным ассоциативным и лиевским и разрешимым лиевским) показало, что в каждом из этих классов существует семейство алгебр, сложность которых по крайней мере в 2 раза превышает размерность этих алгебр.

1.10 Сравнение нижних оценок, полученных автором диссертации, с нижними оценками других авторов Тематика данной работы имеет довольно сильное пересечение с тематикой работ A. Альдера и V. Штрассена1 и С.А.

Жошиной3. С ними и проводится сравнение.

1.10.1 Нижние оценки для простых алгебр Ли Как упоминалось ранее, в работе С.А. Жошиной3 были получены нижние оценки для простых классических алгебр Ли серий Al, Bl, Cl, Dl. В настоящей работе нижние оценки улучшены, в частности, асимптотика улучшена в два раза; также в два раза (асимптотически) вновь полученные оценки превосходят размерность алгебры. Очень грубо оценки могут быть представлены следующим образом (, = 1, 2):

Жошиной: rk (L) 1.10.2 Нижние оценки для нильпотентных ассоциативных алгебр Ранее рассматривались нижние оценки для класса ассоциативных алгебр, см., например, обзорно-обобщающую работу А. Альдера, В. Штрассена1, в которой изучались конечномерные ассоциативные алгебры, в том числе и с ненулевым радикалом Джекобсона R (нильпотентной частью). Они, однако, рассматривали только такие алгебры, которые содержат единицу и, таким образом, не являются нильпотентными. Кроме того, нижние оценки, касающиеся радикальных элементов, получены для достаточно узкого класса произведений. Так, в упомянутой работе не оценивалась: ни сложность умножения радикального элемента r на (другой) радикальный элемент s;

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

Фактически для элемента (вектора) r из радикала R оценивалась его сложность умножения на число, которая, очевидно, есть не менее чем n = dim(R).

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

(здесь 1 единица алгебры, и элементы основного поля, r и s элементы радикала R).

Отметим, что эта оценка не зависит от сложности умножения в радикале R (т.е. от произведения rs) и определяется сложностью умножения вектора на число (т.е. умножениями 1, s и r).

В настоящей работе получена оценка сложности произведений именно для нильпотентных алгебр или, говоря иначе, для произведений rs. Таким образом, по сравнению с работой А. Альдера, В. Штрассена1 в данной работе расширен класс произведений, для которых проводится оценка.

Отметим также, что в работе Блазера2 получена нижняя оценка для алгебры верхнетреугольных матриц Tn с ненулевыми элементами на главной диагонали. В настоящей диссертации даны оценки для строго нильпотентной верхнетреугольной матричной алгебры (с нулевыми элементами на главной диагонали).

1.10.3 Нижние оценки для нильпотентных ассоциативных и нильпотентных и разрешимых алгебр Ли Автору диссертации неизвестны какие-либо нижние оценки других авторов для нильпотентных ассоциативных и нильпотентных и разрешимых алгебр Ли.

1.11 Структура и объем диссертации Диссертация состоит из вводной (предварительной) и оригинальной (основной) частей. Первая часть (2 главы) содержит общую характеризацию работы и предварительные сведения, которые используются в дальнейшем. Вторая часть (4 главы) содержит оригинальные результаты автора.

Общий объем диссертации составляет 92 страницы. Библиография включает 57 наименований.

2 КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В Главе 2 приведены основные понятия, определения и обозначения, используемые в основной части диссертации. В частности, дано определение алгебры Ли и ассоциативной алгебры, нильпотентной алгебры, основные понятия теории сложности.

Также дано определение тензора, его ранга и структурного тензора алгебры (тензора умножения).

2.0.1 О ранге тензора умножения билинейной алгебры Пусть V конечномерная алгебра над полем F с операцией умножения (a, b) a b, необязательно ассоциативной. Если Скаляры ij F называются структурными константами алгебры V в данном базисе. В силу билинейности операции умножения алгебра V полностью определяется заданием базиса и структурных констант в нем.

Определение 2.1. Вычисление (для алгебры V) называют билинейным, если структурный тензор алгебры записан в операция произведения в алгебре; ui, vi L ; wi где:

L L. Выражение (1) также называют билинейным алгоритмом. Билинейным рангом (билинейной сложностью) V называется длина кратчайшего билинейного вычисления (вычисления с наименьшим r). Ранг V обозначается через rk (V).

Определение 2.2. Вычисление (для алгебры V) называют квадратичным, если структурный тензор алгебры записан в где ui, vi (L L) ; wi L L. Выражение (2) также называют квадратичным алгоритмом. Квадратичным рангом (квадратичной сложностью) V называется длина кратчайшего квадратичного вычисления (вычисления с наименьшим r). Ранг V обозначается через rk (V).

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

Основная часть (часть II) содержит оригинальные результаты автора, состоит из четырех глав и посвящена получению нижних оценок тензорного ранга. Характеристика основного поля F всюду равна нулю.

2.0.2 Нижние оценки для простых классических алгебр Ли серий Al, Bl, Cl, Dl В главе 3 рассматриваются простые классические алгебры Ли серий Al, Bl, Cl, Dl над произвольным полем F характеристики ноль.

Определение 2.3. Алебра L (с билинейным законом умножения) называется алгеброй Ли, если операция умножения антикоммутативна, т.е.

и удовлетворяет тождеству Якоби для всех x, y, z L.

Определение 2.4. Алгебра L называется простой, если L не является алгеброй с нулевым умножением и не содержит идеалов, отличных от L и 0.

В главе 3 основной является следующая Теорема 2.5 (Леонтьев А.В.). Тензорный ранг (мультипликативная сложность) простой классической алгебры Ли (для серий Al, Bl, Cl, Dl ), над полем характеристики ноль не менее чем:

2.0.3 Нижние оценки для нильпотентных и разрешимых алгебр Ли Глава 4 посвящена оценкам тензорного ранга нильпотентных и разрешимых алгебр Ли.

Определение 2.6. Пусть A алгебра Ли. Положим A1 = A(0) = A и далее по индукции где для подмножеств B, C алгебры A через BC обозначается F-подмодуль, порожденный всеми произведениями bc, b B, c C. Алгебра называется нильпотентной, если найдется такое n, что An = 0. Алгебра называется разрешимой, если найдется такое m, что A(m) = 0. Наименьшие числа n и m с указанными свойствами называются соответственно индексом нильпотентности и индексом разрешимости алгебры Легко видеть, что алгебра A нильпотентна индекса n в том и только том случае, когда произведение любых n ее элементов с любой расстановкой скобок равно нулю и существует ненулевое произведение n 1 элементов. Всякая нильпотентная алгебра разрешима, но обратное, вообще говоря, неверно.

Определение 2.7. Центром Z(L) алгебры L называется множество элементов x L таких, что xy = yx для любого элемента y L.

Если L алгебра Ли, то центр Z(L) является идеалом, причем L Z(L) = 0.

Определение 2.8. Ниль-радикалом Nil(L) алгебры Ли L называется наибольший нильпотентный идеал.

Заметим, что ниль-радикал определен однозначно (в конечномерном случае).

Для нильпотентных алгебр Ли справедлива следующая оценка.

Теорема 2.9 (Леонтьев А.В.). Пусть I прообраз в нильпотентной алгебре L центра Z(L/L3 ) алгебры L/L3. Тогда для алгебры Ли L справедлива следующая оценка:

Теорема 2.10 (Леонтьев А.В.). Пусть L алгебра Ли верхнетреугольных нильпотентных матриц (порядка n n с нулями на главной диагонали). Тогда С другой стороны, нижние оценки можно строить индуктивно (по степени нильпотентности) следующим образом.

Теорема 2.11 (Леонтьев А.В.). Пусть L нильпотентная алгебра Ли индекса нильпотентности n > 2 (Ln = 0, Ln1 = 0), I прообраз в нильпотентной алгебре L центра Z(L/L3 ) алгебры L/L3. Определим множества Очевидно, Ji идеал в Li.

Тогда справедлива оценка где сумма распространяется на слагаемые с i 2.

Теорема 2.12 (Леонтьев А.В.). Пусть K разрешимая алеё нильрадикал, IN Тогда справедливы следующие оценки:

rk (Nil(K)) Другая оценка для разрешимых алгебр может быть получена индукцией по индексу разрешимости. Пусть K разрешима ступени n (K(n+1) = 0, K(n) = 0), Теорема 2.13 (Леонтьев А.В.). Пусть K разрешимая алгебра ступени n. Тогда справедлива следующая оценка Теорема 2.14 (Леонтьев А.В.). Пусть Tn разрешимая (не нильпотентная) алгебра Ли строго верхнетреугольных матриц (порядка n n с нулями под главной диагональю). Тогда 2.0.4 Нижние оценки для нильпотентных ассоциативных алгебр Глава 5 посвящена классу нильпотентных ассоциативных алгебр. Следует отметить, что первоначально доказательство для нильпотентных алгебр было дано автором для класса алгебр Ли и затем было распространено на класс ассоциативных алгебр. Таким образом, доказательство оценок для класса ассоциативных алгебр очень близко к доказательству, данному автором для класса нильпотентных алгебр Ли. Различие между классом ассоциативных алгебр и алгебр Ли состоит в учете (для ассоциативного случая) некоммутативности умножения.

Определение 2.15. Алгебра (кольцо) R называется ассоциативной, если (ab)c = a(bc) для любых a, b, c R. Соответственно, алгебра R называется коммутативной, если ab = ba.

Определение 2.16. Ассоциативное кольцо R называется нильпотентным, если Rn = 0 для некоторого натурального n, т.е. произведение любых n элементов равно нулю.

Аналогично определяется нильпотентный идеал.

Определение 2.17. Если Y подмножество кольца R, то левый аннулятор ANNL(Y) подмножества Y состоит из всех таких x, что xy = 0 для всех y Y.

Аналогично определяется правый аннулятор.

Обозначим левый и правый аннулятор соответственно через ANNL(L) и ANNR(L), пересечение левого и правого аннулятора с L2 через Annl(L) = L2 ANNL(L) и Annr(L) = L2 ANNR(L). Имеет место следующая Теорема 2.18 (Леонтьев А.В.). Пусть IL и IR прообразы в нильпотентной алгебре L левого Annl(L/L ) и правого Annr(L/L3 ) аннуляторов алгебры L/L3. Тогда для алгебры L справедлива следующая оценка:

В качестве следствия предыдущей теоремы нетрудно получить следующую.

Теорема 2.19 (Леонтьев А.В.). Пусть L ассоциативная алгебра верхнетреугольных нильпотентных матриц (порядка n n с нулями на главной диагонали). Тогда С другой стороны, нижние оценки можно строить индуктивно (по степени нильпотентности) следующим образом. Пусть алгебра L нильпотентна индекса n (Ln = 0, Ln1 = 0). Определим множества Имеет место следующая Теорема 2.20 (Леонтьев А.В.). Пусть L ассоциативная нильпотентная алгебра индекса нильпотентности n (Ln = 0, Ln1 = 0). Тогда справедливы оценки 2.0.5 Нижние оценки для нильпотентных алгебр Ли малых В Главе 6 полученные нижние оценки тензорного ранга для нильпотентных алгебр Ли применены к алгебрам Ли малых размерностей, классификация которых приведена в работах J.M. Ancochea-Bermudez et M.Goze (для поля комплексных чисел до размерности 8 включительно) и Морозова В.В–Умляуфа К.А. (для поля действительных чисел до размерности 6 включительно). Для сравнения приведены также (довольно грубые) верхние оценки.

2.1 Благодарности Автор выражает благодарность научному руководителю профессору Латышеву В.Н. за внимание и поддержку и всем сотрудникам кафедры алгебры МГУ, принимавшим участие в обсуждении данной работы. Также автор выражает благодарность д.ф.-м.н. Знаменскому С.В. и Кормалеву Д.А. за консультации по системе LTEX.

Список литературы [1] Леонтьев А.В., Нижние оценки алгебраической сложности для классических простых алгебр Ли. //Математический сборник, 2008, т.199, ном. 5, стр. 27-34.

[2] Леонтьев А.В. Нижние оценки алгебраических алгоритмов для нильпотентных ассоциативных алгебр // Успехи математических наук, 2008, т. 63, вып. 6(384), стр. 157Леонтьев А.В., Нижние оценки алгебраических алгоритмов для нильпотентных и разрешимых алгебр Ли. // Известия высших учебных заведений. Математика, 2010, ном. 3, стр. 15-22.

[4] Леонтьев А.В., О ранге прямых сумм. // Фундаментальная и прикладная математика 2002, т. 8, вып. 3, стр. 949-