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

• Леонтьев, Александр Владимирович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Леонтьев, Александр Владимирович

Предисловие

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

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

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

ВВЕДЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Леонтьев, Александр Владимирович, 2010 год

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)