Мультипликативная сложность умножения в алгебрах

• Автор: Чокаев, Бекхан Вахаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 82 с.

Оглавление
Введение

1 Оценки умножения в алгебрах

1.1 Основные понятия

1.2 Модель вычислений

1.3 Используемые методы

2 Групповые алгебры над полями характеристики

2.1 Алгебра циклической группы над рациональным полем

2.2 Произвольные алгебры над рациональным полем

2.3 Алгебры над произвольным полем характеристики нуль

3 Групповые алгебры над полями простой характеристики

3.1 Групповые алгебры минимального ранга
3.1.1 Алгебры над конечным полем
3.1.2 Алгебры над бесконечным полем
3.1.3 Алгебры не минимального ранга
3.2 Верхняя и нижняя оценки мультипликативной сложности
4 Алгебры минимальной мультипликативной сложности
4.1 Оценка Алдера-Штрассена и алгебры минимальной сложности
4.2 Сверхосновные алгебры
4.3 Локальные алгебры
Оглавление
4.4 Алгебры с условием А/ rad А = к2х2
4.5 Главный результат
4.6 Почти билинейные вычисления
Список литературы

Введение
Алгоритмическое решение задач всегда было одним из основных предметов математики. В течение долгого времени такие решения были основаны на интуитивных соображениях. К началу XX в. много ярких примеров представили алгебра и теория чисел. Среди них — алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами. Эти и другие алгоритмические проблемы были решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале XX в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Одним из важнейших научных достижений в первой половине XX века стала точная математическая формализация понятий вычислимости и алгоритма.
В 1930-х годах был предложен ряд точных математических определений понятия алгоритма. Наиболее известные из них — машина Тьюринга, нормальный алгоритм Маркова, рекурсивные функции, А—исчисление Черча, машина Поста и другие. Все эти формализации алгоритма оказались эквивалентными с точки зрения алгоритмической разрешимости проблем. Последнее было обобщено в известном тезисе Черча о том, что формальное определение алгоритма эквивалентно его интуитивному пониманию.
В первую очередь эти понятия помогли установить алгоритмическую неразреши-
Глава 2. Групповые алгебры над полями характеристики О

Определитель матрицы, составленной из коэффициентов векторов gs aj в базисе eiTij, есть определитель Вандермонда, отличный от нуля, так как е“1 ф е”1 при -/= Этим доказана линейная независимость векторов {gs Oj | j € J, s = 0
Множество Aq замкнуто относительно двух операций в алгебре А: сложения и умножения на рациональное число. Следовательно, Aq есть линейное пространство над рациональным полем с базисом {ga-aj | j € J, s = 0
Докажем, что Aq = (Q[X]/3>n)dim®*m. Обозначим через А,- линейную оболочку векторов {«?„ о, | s = 0
Aq “ х Aj. (2.16)

Докажем, что для каждого j € J алгебра Aj изоморфна алгебре <12[Х]/ФП. Пусть линейное отображение ф ставит в соответствие вектору b, = gs а,- 6 Aj вектор X3 е И2[Х]/ФП, s = 0, |/| — 1. Тогда достаточно доказать, что ф{Ь fy/|-i)
= ф(Ъ) i/»(b|/|_i) = X'moc). Имеет место соотношение
*>1 Vl-i = 9i ' % = Y1 е*_1Л ' е">г (2Л?)

Заметим, что при каждом i € I корень е“1 есть примитивный корень степени п из
единицы и Фп(ех) = 0. Так как скФ„ = |/|, то корень линейно выражается
через корни {eïs | s = 0
Для завершения доказательства леммы осталось доказать, что Aq = Q[X]/„ ® QfXJ/Фт. Обозначим через a единицу алгебры Aq,
a = 'Jai= ]С еЧ- (2Л8)
jeJ ieI,jeJ