Нижние оценки алгебраической сложности для некоторых классов алгебр тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.Ломоносова МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 512.554.3

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

Нижние оценки алгебраической сложности для некоторых классов алгебр

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

АВТОРЕФЕРАТ

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

О 3 033 2011

Москва 2011г.

4853783

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

Московский педагогический государственный университет

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

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

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

Ученый секретарь

Диссертационного совета Д 501.0(11.84 доктор физико-математических наук, профессор А.О. Иванов

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

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

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

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

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

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

нительно немного, основные исследования направлены на рассмотрение возможно важных, но частных задач.

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

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

1.2 Обзорные замечания 1.2.1 Алгебры с делением

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

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

В 1970-ых годах Dobkin. de Groote, Howell и Lafon, Stress показали, что сложность алгебры кватернионов над R равна 8.

В 1977г. Fiduccia и Zalcstein показали, что для алгебры с делением А выполнена оценка

Сга(Л) > 2dim(.A) - 1

(Если А является простым расширением поля, то равенство достигается.)

1.2.2 Матричная алгебра (верхние оценки)

Без всякого преувеличения можно утверждать, что наибольшие усилия в изучении сложности алгебр были направлены на матричную алгебру. Перечисление всех работ в этой области было бы затруднительно. Отметим лишь некоторые из них.

Обычный (классический) алгоритм умножения матриц (строка на столбец) требует п3 умножений и п2(п — 1) сложений.

Более быстрый по порядку алгоритм типа „разделяй н властвуй" предложен Штрассеном в 1970г. Первоночалыю Штрас-сен представил алгоритм умножения в матричной алгебре МгХ2 имеющий 7 умножений чисел вместо 8 умножений классического алгоритма. Таким образом была доказана неоптимальность классического алгоритма перемножения матриц. Этот алгоритм может быть распространен на матрицы более высоких порядков рекурсивно (посредством блочного разбиения матриц). На каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате сложность этого алгоритма составляет 0(гс1огг7) и 0(гс2'807). Недостатком данного метода является большая сложность программирования по сравнению со стандартным алгоритмом, численная неустойчивость и большой объём используемой памяти. Разработано большое количество алгоритмов на основе метода Штрассена, которые улучшают его численную устойчивость и объём используемой памяти.

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

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

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

Затем Шёнхаге создал метод, названный методом прямых сумм, сложность которого составляет 0("2'548)- Романи сумел понизить оценку до 0(?г2'5166), а Пан — до 0(п2ЪШ).

В 1990г. Копперсмит и Виноград опубликовали алгоритм,

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

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

1.2.3 Нижние оценки для некоторых ассоциативных алгебр

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

Так, например, в 1971г. Hopcroft и Kerr и Winograd показали, что

С„(М2) = 7

В 1977г. Fiduccia и Zalcstein и Winograd установили сложность алгебры, порожденной одним элементом: если / е fc[t] ненулевой полином степени пет различными простыми факторами, то

Cm(MW)) = 2n - m

Как уже упоминалось ранее в разделе 1.2.1 для алгебр с делением А выполнена оценка

Ст(Л) > 2 dim (А) - 1

В 1978г. Brockett и Dobkin и Lafon и Winograd для матричной алгебры установили оценку

Ст(Мп) > 2п2 - 1 = 2 dim(A/„) - 1

Для ассоциативных конечномерных алгебр с единицей в 1981г. доказана1 также обобщающая оценка:

1 Aider A., Strassen V., On the algorithmic complexity of the associative algebras. // Thcor. Comp. Sei. 1981, 15, 201-211.

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

Ст(А) > 2d\т(А)-Т ,

где Т — число максимальных двусторонних идеалов в А.

Также: если А/ Rad (Л) = А\ х ... х At (здесь Rad (А) — радикал Джекобсона), то

t

Ст(А) > ^(2dim(Ai) - 1) + 2dim(Rad(A)) i—i

□

Нелинейные нижние оценки сложности умножения матриц отсутствуют. В 2002 году Ран Раз доказал нижнюю оценку О (п2 logn) для сложности умножения квадратных матриц порядка п в модели с ограниченными коэффициентами.

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

(5/2)п2 - 3п

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

Cm(Tn)Z (5/2) dim(Tn)- 5/2 + 1

(Отметим, что в работе также дана характеризация так называемых алгебр минимального ранга.)

Амир Шпилька в 2001 году улучшил результат Блазсра для конечных полей:

Ст(Мп) Z Зп2о(п2)

2Markus Blaser, А 2.5 п2-lower bound for the rank of n x n-m.atrix multiplication over arbitrary fields. // Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sei. (FOCS), 45-50, 1999.

для поля С?Р(2) и

Ст(Мп) ^ (5/2 + 3/(2(р3 - 1)))п2 - о(п2))

для поля (7.Р(р).

Существует гипотеза о том, что сложность умножения матриц порядка п равна

п22о(1оеп)

1.2.4 Групповые алгебры

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

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

В.М. Сидельников, Л.С. Казарин рассмотрели линейное представление (нерегулярное) Х>п диэдральной группы порядка 2п с помощью (п х п)-матриц с элементами из конечного поля СЕЧ и показали, что если число п взаимно просто с характеристикой поля СГ?, то групповая алгебра ЛЭ„ является прямой суммой колец, каждое из которых изоморфно полному кольцу (2 х 2)-матриц с элементами из поля СГ™', где числа щ определяются степенями неприводимых многочленов, на которые разлагается многочлен хп — 1 над полем Этот резуль-

тат, объединенный с подобным результатом, полученным авторами ранее для циклической группы, позволяет уменьшить сложность умножения в конечном поле С^ и в кольце матриц второго порядка над полем СР®.

1.2.5 Антикоммутативные алгебры и алгебры Ли

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

В 1990—93г. в заметках и Жошина С.А. рассмотрела мультипликативную сложность простых алгебр типа 21[, 93|, €[, ©2) З4, <£7, и полупростых алгебр Ли (прямая сумма простых) над полями. (Хотя в работах и не указана характеристика поля, судя по доказательству, она равна нулю.) В частности, доказаны следующие теоремы3:

Теорема 1.2 (Жошина С.А.). Пусть £ — простая алгебра Ли одного из типов <52, , (Нб, <£7 или (Не- Тогда ее тензорный ранг оценивается снизу неравенством гк®(£) ^ Шт(£) — 1 + /,г де

'4, £ = ©2;

15, £ = З4;

22, £ = <£6;

34, £ =

.58, £ = е8-

□

Теорема 1.3 (Жошина С.А.). Пусть £ — простая алгебра Ли одного из типов 21|, 25[, £[ или 2)(. Тогда ее тензорный ранг оценивается снизу неравенством

гк8(,С) >аип(£)-1 + /,

3Жошина С.А., О мультипликативной сложности алгебр Ли. /, Вестн. Моск. Ун-та. Сер. 1, Математика. Механика. 1990, 4, 75-77.

Жошина С.А.. О мультипликативной сложности простых алгъбр Ли 02:34, ^7« и полупростых алгебр Ли.// Вестн. Моск. Ун-та. Сер. 1, Математика. Механика. 1993, 4, 35-37.

где

2, £ = 211

21 -2, £ = %,1 > 2,

21 -1, £ = <В 1.1^ 3,

2, £ = <в2

21 -4, £ = 3,

21 -4, £ = 2,

□

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

1п

гк0(£) ^сШп(£)-1 + ^/*;

¡=1

где / определены выше. □

1.3 Цель диссертации

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

1.4 Научная и практическая ценность

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

1.5 Методы исследования

В диссертации используются модели и методы теории сложности; структ}фные результаты по классификации простых ал-

гебр Ли серий 2103;, над полями характеристики ноль;

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

1.6 Публикации

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

1.7 Апробирование

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

1.8 Гипотеза о мультипликативной сложности простых алгебр и несколько замечаний о доказательствах теорем

В кругу специалистов по теории сложности известна гипотеза (по всей видимости „фольклорного" происхождения) о мультипликативной сложности простых алгебр: асимптотическая сложность простых алгебр в важнейших классах по крайней мере в 2 раза превосходит размерность алгебр. Ее появление связано скорее всего с работами Brocket t и Dobkin, Lafon и Winograd. A.Alder. V.Strassen, где было доказано, что сложность ассоциативных (и. в частности, матричных) простых алгебр в 2 раза асимптотически превосходит размерность самих алгебр. В настоящей работе этот вопрос рассматривается для простых классических алгебр Ли серий 21;, 03/. С;. Э; (см. ниже).

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

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

1.9 Научная новизна

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

• для простых классических алгебр Ли серий 21;, 05/, €[. 2); (асимптотически в 2 раза улучшена оценка Жошиной3) — тем самым доказана гипотеза о том, что сложность простых классических алгебр Ли асимптотически по крайней мере в два раза превосходит размерность алгебр (теорема 2.5);

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

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

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

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

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

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

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

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

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

1.10 Сравнение нижних оценок, полученных автором диссертации, с нижними оценками других авторов

Тематика данной работы имеет довольно сильное пересечение с тематикой работ А. Альдера и V. Штрассена1 и С.А. Жошиной3. С ними и проводится сравнение.

1.10.1 Нижние оценки для простых алгебр Ли

Как упоминалось ранее, в работе С.А. Жошиной3 были получены нижние оценки для простых классических алгебр Ли серий 21;, 23;, €;, 3);. В настоящей работе нижние оценки улучшены. в частности, асимптотика улучшена в два раза; также в два раза (асимптотически) вновь полученные оценки превосходят размерность алгебры. Очень грубо оценки могут быть представлены следующим образом (а, /? = 1,2): Жошиной: гк0(£) > Шт(£) + а^/51т(£) автора : гк®(£) > 2сКт(£) — /?-^/с11т(£)

1.10.2 Нижние оценки для нильпотентных ассоциативных алгебр

Ранее рассматривались нижние оценки для класса ассоциативных алгебр, см., например, обзорно-обобщающую работу А. Альдера, В. Штрассена1, в которой изучались конечномерные ассоциативные алгебры, в том числе и с ненулевым радикалом Джекобсона 01 (нильпотентной частью). Они, однако, рассматривали только такие алгебры, которые содержат единицу и, таким образом, не являются нильпотентными. Кроме того, нижние оценки, касающиеся радикальных элементов, получены для достаточно узкого класса произведений. Так, в упомянутой работе не оценивалась: ни сложность умножения радикального элемента г на (другой) радикальный элемент 5; ни сложность умножения радикального элемента г на полупростой элемент р. за исключением его (элемента г) умножения на единичный элемент алгебры 1 (с коэффициентом).

Фактически для элемента (вектора) г из радикала 3? оценивалась его сложность умножения на число, которая, очевидно, есть не менее чем п = сИт(3?).

Так, например, если 'Я — нильпотентная алгебра, то добавив внешним образом единицу (т.е. рассмотрев алгебру 1 © Л) получим алгебру, удовлетворяющую условиям теоремы из рассматриваемой работы1 (конечномерную ассоциативную алгебру с единицей — фактически эта одна из алгебр, которые рас-

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

(а! + г) (/31 + э) = ар! + ац + /3г +

ГБ

А. В. Леонтьев (1-ая и 2-ая оценки)

А.АМег, ЧЛЙиаэыеп

(здесь 1 — единица алгебры, а и /3 — элементы основного поля, г и § — элементы радикала 31).

Отметим, что эта оценка не зависит от сложности умножения в радикале (т.е. от произведения гэ) и определяется сложностью умножения вектора на число (т.е. умножениями а/31, а! и /Зг).

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

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

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

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

1.11 Структура и объем диссертации

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

которые используются в дальнейшем. Вторая часть (4 главы) содержит оригинальные результаты автора.

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

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

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

2.0.1 О ранге тензора умножения билинейной алгебры

Пусть V — конечномерная алгебра над полем Р с операцией умножения (а, 6) —» а * Ь, необязательно ассоциативной. Если (е\,..., еп) — базис пространства V. то

Скаляры 7у 6 Р называются структурными константами алгебры V в данном базисе. В силу билинейности операции умножения * алгебра V полностью определяется заданием базиса и структурных констант в нем.

Определение 2.1. Вычисление (для алгебры У) называют билинейным, если структурный тензор алгебры записан в виде

к

г

где: * — операция произведения в алгебре; € £*; Wi € £ = £**. Выраэ1сеиие (1) также называют билинейным алгоритмом. Билинейным рангом (билинейной слоэ/сностыо) V называется длина кратчайшего билинейного вычисления (вычисления с наименьшим г). Ранг V обозначается через

Определение 2.2. Вычисление (для алгебры V) называют квадратичным, если структурный тензор алгебры записан в виде

где щ, € (£ х £)*; и>( £ £ = £**. Выражение (2) такэ/се называют квадратичным алгоритмом. Квадратичным рангом (квадратичной сложностью) V называется длина кратчайшего квадратичного вычисления (вычисления с наименьшим г). Ранг V обозначается через гк8(У). □

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

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

2.0.2 Нижние оценки для простых классических алгебр Ли серий Я,, ©¡, Э,

В главе 3 рассматриваются простые классические алгебры Ли серий 521/, 03[, над произвольным полем Р характеристи-

ки ноль.

гкяр?). □

Г

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

х2 = 0 ,

и удовлетворяет тождеству Якоби

у, г) = [ху]г + \yz\x + [гх]у = 0 для всех х, у, г е £. □

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

В главе 3 основной является следующая

Теорема 2.5 (Леонтьев А.В.). Тензорный ранг (мультипликативная сложность) простой классической алгебры Ли (для серий 211, С;, над полем характеристики ноль не менее чем:

гк®(21г) ^ 2/2 4- 21 (для алгебр серии %), гк®(93() ^ 4£2 — 21 (для алгебр серии гк®(£/) ^ 4/2 — 21 (для алгебр серии С;), гк®(Э;) > 4£2 — Ы + 2 (для алгебр серии Э^.

□

2.0.3 Нижние оценки для нилыютентных и разрешимых алгебр Ли

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

Определение 2.6. Пусть А — алгебра Ли. Положим Л1 = = А и далее по индукции

Ап-и = ^ А1 А> ; Л("+1) = Л(п)Л(п) ,

¿+.7=71+1

где для подмножеств Ъ, С алгебры А через "ВС обозначается F-подмодуль, порожденный всеми произведениями Ьс, Ь & Ъ,

с € С. Алгебра называется нилъпотентной, если найдется такое п, что Ап = 0. Алгебра называется разрешимой, если найдется такое т, что = 0. Наименьшие числа пит с указанными свойствами называются соответственно индексом нильпотентности и индексом разрешимости алгебры А. □

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

Определение 2.7. Центром Z(£) алгебры £ называется множество элементов х € £ таких, что ху = ух для любого элемента у £ £. □

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

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

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

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

Теорема 2.9 (Леонтьев A.B.). Пуапъ 3 — прообраз в нилъпотентной алгебре £ центра Z(£/£3) алгебры £/£3. Тогда для алгебры Ли £ справедлива следующая оценка:

гк®(£) > 2 dim(£7(Z(£) П £2)) 4- dim(£/J)

□

Теорема 2.10 (Леонтьев A.B.). Пусть £ — алгебра Ли верхнетреугольных нильпотентных матриц (порядка пхп с нулями на главной диагонали). Тогда

rk0(£) > 2dim(£2/ Z(£)) + diiii(£/£2) =

= 2((n - 1 )(n -2)/2~l) + (n-l) = (n- l)2 - 2

□

С другой стороны, нижние оценки можно строить индуктивно (но степени нильпотентности) следующим образом.

Теорема 2.11 (Леонтьев A.B.). Пусть £ — нилъпотентная алгебра Ли индекса нильпотентности п > 2 (Хп = 0, £>п~1 ф 0),3 — прообраз в нильпотентной алгебре jC центра Z(£/£3) алгебры L/L3. Определим множества

f = {х е Г | [!,£] g £2i}

Очевидно, 3' — идеал в Тогда справедлива оценка

гМ-С) >2(^2 dim(£V3')j + dim(£/J)

\i=n-2 /

где сумма распространяется на слагаемые с i ^ 2. □

Теорема 2.12 (Леонтьев A.B.). Пусть % — разрешимая алгебра, Nil(3C) — её нильрадикал, 3jv — прообраз в Nil(3C) центра

Z(Nil(3C)/(Nil(0C))3). Тогда справедливы следующие оценки:

rks(3C) > rk®Nil(3C)

rke(Nil(3C)) ^ 2 dim(Nil(3C)2/(Z(Nil(3C)) П №1(ЗС)2))+ dim(Nil(3C)/aA-)

□

Другая оценка для разрешимых алгебр может быть получена индукцией по индексу разрешимости. Пусть ОС разрешима ступени п (DC("+1) = О, ОС^ ф 0).

di = {k eXii}\[k.X\gX2i}

Теорема 2.13 (Леонтьев A.B.). Пусть % — разрешимая алгебра ступени п. Тогда справедлива следующая оценка

о

i=n

□

Теорема 2.14 (Леонтьев A.B.). Пусть 7п — разрешимая (не нильпотентная) алгебра Ли строго верхнетреугольных матриц (порядка п х п с нулями под главной диагональю). Тогда

rk0(Tn) ^ 2dim(0-2)

2.0.4 Нижние оценки для нильпотентных ассоциативных алгебр

Глава 5 посвящена классу нильпотентных ассоциативных алгебр. Следует отметить, что первоначально доказательство для нильпотентных алгебр было дано автором для класса алгебр Ли и затем было распространено на класс ассоциативных алгебр. Таким образом, доказательство оценок для класса ассоциативных алгебр очень близко к доказательству, данному автором для класса нильпотентных алгебр Ли. Различие между классом ассоциативных алгебр и алгебр Ли состоит в учете (для ассоциативного случая) некоммутативности умножения.

Определение 2.15. Алгебра (кольцо) называется ассоциативной, если (аЬ)с — а(Ъс) для любых а,Ь,с € Соответственно, алгебра $ называется коммутативной, если аЬ = Ьа. □

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

Определение 2.17. Если У — подмножество кольца то левый аннулятор ANNL(V) подмножества У состоит из всех таких х. что ху = 0 для всех у 6 У.

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

Обозначим левый и правый аннулятор соответственно через ANNL(£) и ANNR(£), пересечение левого и правого ан-нулятора с £2 — через Annl(£) = £2 П ANNL(£) и Annr(£) = £2 П ANNR(£). Имеет место следующая

Теорема 2.18 (Леонтьев A.B.). Пусть и Эд — прообразы в нильпотентной алгебре £ левого Annl(£/£3) и правого Annr(£/£3) анпулягпоров алгебры L/L3. Тогда для алгебры С справедлива следующая оценка:

гкэ(£) ^ dim(£2/ Annl(£)) + dim(£2/ Annr(£))+

+ max(dim(£ fJL), dim(£/Зд))

□

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

Теорема 2.19 (Леонтьев A.B.). Пусть £ — ассоциативная алгебра верхнетреугольных нильпотентных матриц (порядка п х п с нулями на главной диагонали). Тогда

rkв(£) > (п - 2)2

□

С другой стороны, нижние оценки можно строить индуктивно (по степени нильпотентности) следующим образом. Пусть алгебра £ нильпотентна индекса п (£" = 0, £"-1 ^ 0). Определим множества

= {х е & | хС Q £2'}, З'л = {х € | Сх Я £2'}

Имеет место следующая

Теорема 2.20 (Леонтьев A.B.). Пусть L — ассоциативная нильпотентная алгебра индекса нильпотентности п (Лп = 0, Cn~l ^ 0) . Тогда справедливы оценки

2

гЫ£) ^ J2 (dim(£73i) + dim(£7ay)+

i=n—1

+ max(dim(£/JL), dim(C/3R))

□

2.0.5 Нижние оценки для нильпотентных алгебр Ли малых размерностей

В Главе 6 полученные нижние оценки тензорного ранга для нильпотентных алгебр Ли применены к алгебрам Ли малых размерностей, классификация которых приведена в работах J.M. Ancochea-Bermudez et M.Goze (для поля комплексных чисел до размерности 8 включительно) и Морозова В.В-Умляуфа К. А. (для поля действительных чисел до размерности 6 включительно). Для сравнения приведены также (довольно грубые) верхние оценки.

2.1 Благодарности

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

Список литературы

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

[2] Леонтьев A.B. Нижние оценки алгебраических алгоритмов для нильпотентных ассоциативных алгебр // Успехи математических наук, 2008, т. 63, вып. 6(384), стр. 157158.

[3] Леонтьев A.B., Нижние оценки алгебраических алгоритмов для нильпотентных и разрешимых алгебр Ли. // Известия высших учебных заведений. Математика, 2010, ном. 3, стр. 15-22.

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

Подписано в печать 13.12.2010 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1062 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Предисловие

Несколько замечаний исторического характера

О тематике диссертации.

I ВВЕДЕНИЕ

1 Общая характеристика работы

1.1 Актуальность темы и обзорные замечания

1.1.1 О перемножении чисел.

1.1.2 О перемножении полиномов

1.1.3 Метод БВЕ.

1.1.4 О вычислении полиномов одного переменного

1.1.4.1 Постановка задач

1.1.4.2 Нижние оценки.

1.1.4.3 Верхние оценки.

1.1.4.4 Общие замечания

1.1.5 О вычислении полиномов многих переменных.

1.1.6 Вычисления в алгебрах.

1.1.6.1 Алгебры с делением.

1.1.6.2 Матричная алгебра (верхние оценки).

1.1.6.3 Нижние оценки для некоторых ассоциативных алгебр.

1.1.6.4 Групповые алгебры

1.1.6.5 Антикоммутативные алгебры и алгебры Ли

1.2 Краткое содержание и основные результаты диссертации

1.2.1 Цель диссертации.

1.2.2 Научная и практическая ценность.

1.2.3 Методы исследования.

1.2.4 Публикации и апробирование.

1.2.5 Личный вклад автора.

1.2.6 Структура и объем диссертации.

1.2.7 Несколько замечаний о доказательствах теорем

1.2.8 Гипотеза о мультипликативной сложности простых алгебр

1.2.9 Научная новизна.

1.2.10 Сравнение нижних оценок, полученных автором диссертации, с нижними оценками других авторов.

1.2.10.1 Нижние оценки для простых алгебр Ли

1.2.10.2 Нижние оценки для пильпотентных и разрешимых алгебр Ли

1.2.10.3 Нижние оценки для нильпотентных ассоциативных алгебр.

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

1.2.11 Основные результаты диссертации, выносимые на защиту

1.2.11.1 Нижние оценки тензорного ранга для классических простых алгебр Ли серий 21/, Ш/, <£/,

1.2.11.2 Нижние оценки тензорного ранга для нильпотентных алгебр Ли.

1.2.11.3 Нижние оценки тензорного ранга для разрешимых алгебр Ли

1.2.11.4 Нижние оценки тензорного ранга для нильпотентных ассоциативных алгебр

1.3 Благодарности.

2 Предварительные сведения, основные определения и обозначения

2.1 Основы алгебраической теории сложности

2.1.1 Направленные схемы (неветвящиеся программы)

2.1.2 Вычислительная модель.

2.1.3 Сложность направленной схемы.

2.1.4 Алгебраическая сложность.

2.1.5 Алгоритмы без деления.

2.2 Кольца и алгебры

2.3 Тензоры.

2.3.1 Определение тензора.

2.3.2 Координаты тензора.

2.3.3 Структурный тензор алгебры.

2.3.4 Тензорный ранг.

2.3.5 Тензорный ранг алгебры.

2.4 Обозначения применяемые в основной части диссертации

2.4.1 Некоторые используемые шрифты.

2.4.2 Некоторые используемые сокращения и обозначения . . 43 2.5 Структуры, рассматриваемые в основной части диссертации

II ОРИГИНАЛЬНЫЕ РЕЗУЛЬТАТЫ АВТОРА

3 Нижние оценки тензорного ранга для классических простых алгебр Ли серий 21/, 23/, С/, £)/

3.1 Обозначения

3.2 Нижние оценки для простых алгебр.

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

4.1 Обозначения

4.2 Нижние оценки для нильпотентных алгебр Ли.

4.3 Об алгебре нильпотентных строго верхнетреугольных матриц

4.4 О константах в оценках для нильпотентных алгебр Ли

4.5 Вторая нижняя оценка.

4.6 Нижние оценки для разрешимых алгебр Ли

5 Нижние оценки тензорного ранга для нильпотентных ассоциативных алгебр

5.1 Обозначения

5.2 Нижние оценки для нильпотентных ассоциативных алгебр

5.3 Первая нижняя оценка

5.4 О коэффициентах при слагаемых в нижних оценках.

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

5.6 Вторая нижняя оценка

6 Применение нижних оценок тензорного ранга к нильпотент-ным алгебрам Ли малых размерностей над полями К и С

6.1 Обозначения

6.2 Алгебры над полем комплексных чисел.

6.2.1 Идеалы в алгебрах.

6.2.2 Некоторые замечания о верхних оценках.

6.2.3 Сравнение верхних и нижних оценок.

6.3 Алгебры над полем действительных чисел

Несколько замечаний исторического характера

Вычислительная сложность в античные времена. Без всякого преувеличения можно утверждать, что возникновение вопросов, касающихся сложности вычислений, относится к тем самым временам, когда происходили первые попытки систематизации математического знания. В качестве примера можно привести составленные в античные времена таблицы отношений хорд к дуге окружности, которые в современной терминологии можно охарактеризовать как „грандиозный вычислительный проект" и который выполнить было бы намного труднее, если бы длину хорды вычисляли традиционным для того времени способом — как периметр вписанных в окружность правильных многоугольников. При подобных вычислениях, однако, широко применялось утверждение, известное как теорема Птолемея: прямоугольник на диагонали вписанного в круг четырехугольника равен сумме прямоугольников на двух парах противолежащих сторон. Данная теорема позволяла „заменять" умножение сложением — имея определенный запас вычисленных хорд, можно довольно просто вычислять некоторые новые хорды из комбинаций уже имеющихся. Этот способ вычисления соответствует современным формулам

8т(а: ± /3) = эт(о;) соб(/3) ± зт(^) соз(а)

2зт2(а/2) = 1 - соз{сх)

Это позволяло значительно сократить объем вычислений и провести их в более сжатые (по меркам того времени) сроки.

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

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

Теория сложности в XX веке. Х1Х-ХХ века открыли новую страницу в теории сложности. Уточнялось понятие алгоритма, были предложены его новые определения, также появилось понимание эквивалентности его различных определений. Это создало серьезный базис для дальнейших теоретических и практических исследований.

В середине XX века под влиянием как инженерно-производственных, так и внутриматематических причин получил новый импульс круг задач довольно широкой тематики, в которых ключевым стало понятие сложности вычислений и который условно можно назвать алгоритмической и дискретной теорией сложности. К этому кругу можно отнести:

• некоторые области теории чисел,

• новые области так называемых быстрых вычислений,

• криптографию,

• алгебраические и комбинаторные алгоритмы,

• теорию булевых функций (схемы из логических элементов) и многие другие области.

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

О тематике диссертации

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

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

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

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

Часть I

ВВЕДЕНИЕ

1. Функционалы {ui,. ,up} линейнонезависимы на множествеOx ?f).2.их (0, у) = . = 1^(0,0) = Оир+1(0 ,У) = . = иг(0> у) = О ^+1(0,2/) = . = vr(0,2/) О3.6)3.7)3.8)

2. Функционалы {их,. , ир} линейнонезависимы на множествеП х 3>? ).их (ж, у) = . = ир(ж, у) = О (3.12)ир+1(ж, у) = . ■ = иг(ж, ?/) = 0 (3.13)Ур+1(ж,у) = . = = 0 (3.14)Глава 3. Нижние оценки для простых алгебр ЛиЧАСТЬ II

3. Функционалы {щ,., ир} линейно независимы (максимально линейно независимая система функционалов) на множестве ( (£2\^(£)) х 0 )•

4. Для элемента х выполнены равенстващ(я;,0) = . = 11р(я;,0) = 0 (4.2)ир+1(я;>0) = . = иР(®>0) = 0 (4.3)ур+1(®,0) = . = уг(®,0) = 0 (4.4)

5. Функционалы {111, ., ир} линейно независимы (максимально линейно независимая система функционалов) на ( (Л2 \ Z(£)) х (Л2 \ Z(£)) ) •

6. Для пары (х, у) выполнены равнстващ(х,у) = . = ир(х,у) = 0 (4.7)у) = . = иг(ж, у) = 0 (4.8). = уг(ж,г/) = 0 (4.9)

7. Функционалы {111,., и^} линейно независимы (максимально линейно независимая система функционалов) на множествег5.1)(£2 \ Апп1(£)) х 0 ) .(£2\Апп1(£)) х 0 ).

8. Для элемента х выполнены равенства111(2;, 0) = . = ир(ж, 0) = 01(я, 0) = . = иг(ж, 0) = 0 0) = . = vr(x, 0) = 05.2)5.3)5.4)Глава 5. Нижние оценки для ассоциативных алгебрЧАСТЬ II

9. Функционалы {111,., ир} линейнонезависимы (максимально линейно независимая система функционалов) на(£2 \ Апп1(£)) х (£2 \ Аппг(£)) >

10. Для пары (ж, у) выполнены равнства111 (ж, у) = --. = у) = 0 (5.7)ир+1(х, у) = . = иг(ж, у) = 0 (5.8)лгр+1(х,у) = . = Vг(х,у) = 0 (5.9)