Московский государственный университет имени М. В. Ломоносова

Факультет вычислительной математики и кибернетики

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

Лысиков Владимир Владимирович

Некоторые вопросы теории сложности

билинейных отображений

Специальность 01.01.09 – дискретная математика

и математическая кибернетика

Диссертация на соискание ученой степени

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

Научный руководитель д. ф.-м. н., профессор Алексеев Валерий Борисович Москва – 2013 Содержание Введение.............................. 4 Глава 1. Основные понятия.................. 1.1. Билинейные отображения и алгебры.......... 1.2. Ассоциативные алгебры над полем........... 1.3. Модель вычислений.................... 1.4. Тензорные произведения и расширение кольца скаляров Глава 2. Алгоритмы умножения обобщенных кватернионов................................ 2.1. Алгебры обобщенных кватернионов........... 2.2. Билинейные отображения малого ранга......... 2.3. Сложность умножения обобщенных кватернионов... 2.4. Ранг произведения алгебр обобщенных кватернионов. Глава 3. Полупростые алгебры почти минимального ранга............................... 3.1. Следствия известных оценок............... 3.2. Сложность умножения в алгебрах матриц....... Глава 4. Целочисленные билинейные отображения над полями различных характеристик............ 4.1. Ненулевые тензорные произведения........... 4.2. Связь между билинейными алгоритмами........ 4.3. Метаматематическое доказательство.......... Литература............................. Введение Теория сложности вычислений является одной из важнейших об­ ластей математической кибернетики. После появления компьютеров измерение эффективности используемых алгоритмов и исследова­ ние возможностей их улучшения стали важными практическими вопросами, изучение которых привело, в том числе, к появлению математической теории, в рамках которой исследуется различные характеристики эффективности алгоритмов в различных математиче­ ских моделях вычислений. Наиболее важные из таких характеристик — это время работы алгоритма, т. е. количество элементарных шагов в рассматриваемой модели, и используемая память. Появление теории сложности вычислений можно отнести к пятидесятым годам XX века:

Б. А. Трахтенброт в [30] утверждает, что исследования временной сложности алгоритмов в СССР начались в 1956 г., а М. Сипсер в [25] упоминает письмо К. Гёделя к Дж. фон Нейману, датируемое 1953 г.

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

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

Одной из основных проблем алгебраической теории сложности является задача определения сложности умножения матриц. В 1969 г.

был опубликован алгоритм Ф. Штрассена [27] для умножения квад­ ратных матриц размера, имеющий сложность (log2 7 ) ариф­ метических операций вместо (3 ) для тривиального алгоритма, что положило начало исследованиям асимптотически быстрых алгорит­ мов умножения матриц. Штрассен также заметил связь алгоритмов умножения матриц с алгебраическим понятием тензорного ранга, что позволило применять для изучения сложности этих алгоритмов конструкции мультилинейной алгебры. После нескольких лет иссле­ дований в этой области Д. Копперсмитом и Ш. Виноградом [12] был получен алгоритм с асимптотической сложностью (2.376 ). Недавние исследования с использованием компьютерных средств [26, 31, 36] позволили улучшить эту оценку до (2.373 ). Наилучшая известная на текущее время нижняя оценка сложности умножения квадратных матриц 32 (2 ) была получена М. Лэндсбергом [18]. В случае, если в алгоритме разрешается использовать только ограниченные по модулю некоторой фиксированной константой коэффициенты, извест­ на оценка вида (2 log ) [22]. Подробные обзоры истории верхних оценок сложности матричного умножения и применяемых для их получения методов содержатся в [32] и [5].

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

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

Помимо того, что общие результаты о сложности ассоциативных алгебр включают в качестве частного случая результаты для сложно­ сти матричного умножения, результаты об ассоциативных алгебрах могут использоваться вместе с другими приемами для получения верхних или нижних оценок. Например, базовая конструкция в ал­ горитме Копперсмита-Винограда может быть интерпретирована как приближенный алгоритм для умножения в алгебре определенного вида. В связи с этим интересен вопрос о структуре алгебр с малой сложностью умножения.

В 1981 г. А. Алдером и Ф. Штрассеном [1] была получена нижняя оценка сложности умножения в алгебрах в терминах их структуры.

Эта оценка оказалась неулучшаемой, в связи с чем возник вопрос об описании всех алгебр, на которых она достигается — алгебр мини­ мального ранга и минимальной мультипликативной сложности. Эта задача решалась несколько десятков лет многими исследователями, окончательное описание было получено М. Блезером [3] для ранга и М. Блезером и Б. В. Чокаевым [6] для мультипликативной сложности.

После этого в [7] М. Блезером и А. М. де Вольтером было начато изучение алгебр почти минимального ранга, т. е. алгебр, для которых билинейная сложность на 1 больше оценки Алдера-Штрассена. Одной из целей данной диссертации является продолжение этих исследо­ ваний. В диссертации обобщается результат Блезера и де Вольтера о полупростых алгебрах почти минимального ранга на случай про­ извольного основного поля, характеристика которого отлична от 2.

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

Для классификации полупростых алгебр почти минимально­ го ранга были получены результаты, которые могут представлять самостоятельную ценность. Так, было получено точное значение слож­ ности умножения обобщенных кватернионов. Оптимальный алгоритм умножения кватернионов над полем действительных чисел был полу­ чен в 70х годах [10, 13, 16], однако он не обобщается непосредственным образом на алгебры обобщенных кватернионов над произвольным полем. Задача об определении сложности умножения обобщенных кватернионов была отмечена в [7] как один из ключевых вопросов на пути к описанию алгебр почти минимального ранга.

Также была улучшена на единицу нижняя оценка Блезера для сложности умножения в матричных алгебрах [4]. Несмотря на то, что методы, использованные М. Лэндсбергом в [18] позволяют получить оценку, более сильную асимптотически, наш результат дает лучшую оценку для алгебр малой размерности.

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

Ранее результаты, касающиеся связи сложности одного и того же билинейного отображения над различными кольцами и полями, были получены в [15] и [24]. Т. Д. Хауэлл первым отметил, что билинейная сложность отображения не возрастает при расширении кольца, над которым рассматриваются алгоритмы, а также доказал, что в некото­ рых условиях такое расширение не влияет на сложность, в частности, что минимальная сложность достигается при использовании в каче­ стве основного кольца алгебраически замкнутого поля. А. Шёнхаге рассматривал сложность матричного умножения над различными по­ лями одной характеристики. Он доказал, что асимптотика сложности матричного умножения над полями одной характеристики одинакова с точностью до постоянного множителя. Штрассен в [29] показал, что этот множитель не превосходит 4 при выполнении гипотезы Штрассена о прямой сумме.

Краткое содержание диссертации В главе 1 приводятся основные определения и известные факты, касающиеся билинейных отображений, алгебр и билинейной сложно­ сти.

В главе 2 рассматриваются билинейные отображения малого ранга и алгоритмы умножения кватернионов.

В разделе 2.1 вводится понятие алгебры обобщенных кватернио­ нов.

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

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

В разделе 2.4 рассматривается сложность умножения пар обоб­ щенных кватернионов. Доказывается нижняя оценка 16 для этой сложности.

Глава 3 посвящена классификации полупростых алгебр пояти ми­ нимального ранга над бесконечным полем характеристики, отличной от 2.

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

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

В главе 4 рассматривается связь значений ранга Z-билинейного отображения над полями различных характеристик.

В разделе 4.1 приводятся условия, при которых тензорное про­ изведение двух модулей не явялется тривиальным.

В разделах 4.2 и 4.3 приводятся два разных доказательства основ­ ного результата главы, использующие различные методы. Доказано, что ранг Z-билинейного отображения над алгебраически замкнутым полем характеристики 0, равен рангу этого отображения над все­ ми алгебраически замкнутыми полями простых характеристик, за исключением конечного числа.

Основные результаты диссертации 1. Описана структура оптимальных алгоритмов для класса били­ нейных отображений, ранг которых равен сумме размерностей аргументов.

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

3. Описана конструкция билинейных алгоритмов ранга 8 для умно­ жения в алгебрах обобщенных кватернионов над полем харак­ теристики, отличной от 2.

4. Доказана нижняя оценка сложности умножения в матричных алгебрах над расширением основного поля, улучшающая из­ вестную оценку Блезера.

5. Полностью описана структура полупростых алгебр почти ми­ нимального ранга над бесконечным полем характеристики, от­ личной от 2.

6. Установлено, что значения ранга Z-билинейного отображения над алгебраически замкнутыми полями различных характе­ ристик совпадают за исключением конечного числа простых характеристик.

1.1. Билинейные отображения и алгебры Обычно в литературе по алгебраической теории сложности рас­ сматриваются билинейные отображения векторных пространств над полем, но нам потребуется более общее определение, работающее над коммутативным кольцом, рассмотриваемое, например, в [15]. Анало­ гом понятия векторного пространства в этом случае является понятие модуля над кольцом (см. напр. [19, 34]).

Термин «кольцо» всюду в диссертации будет обозначать комму­ тативное кольцо с единицей.

Определение 1.1. Пусть — кольцо. Модулем над называется абелева группа, + с операцией умножения на элементы кольца, удовлетворяющей соотношениям Кольцо называют кольцом скаляров модуля, а его элемен­ ты — скалярами.

Обычным образом вводятся понятия гомоморфизма, изоморфиз­ ма, подмодуля и прямой суммы модулей.

Определение 1.2. Пусть — кольцо, и — модули над.

Отображение : называется гомоморфизмом модулей, если оно сохраняет операции сложения и умножения на скаляры из, т. е.

Гомоморфизм, являющийся взаимно-однозначным отображени­ ем, называется изоморфизмом.

В случае, когда — поле, гомоморфизмы модулей суть линейные операторы, а изоморфизмы — обратимые линейные операторы.

Определение 1.3. Подмножество модуля называется подмо­ дулем, если оно замкнуто относительно операций сложения и умно­ жения на скаляры, т.е. для любых 1, 2 и сумма 1 + и произведение 1 также принадлежат.

Определение 1.4. Пусть — кольцо, и — модули над.

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

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

Модули вида наиболее близки по свойствам конечномерным век­ торным пространствам над полем, например, в них можно корректно ввести обобщения понятий базиса и линейной зависимости.

Определение 1.5. Пусть — кольцо. Модуль над будем на­ зывать конечномерным свободным модулем, если для неко­ 0. Число будем называть размерностью† свободного торого модуля.

Определение 1.6. Пусть — кольцо, — модуль над. Гомомор­ физмы : будем называть линейными функционалами на.

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

как модуль над, если определить операции следующим образом:

для любых, *,,. Модуль * называется сопря­ женным к M.

Перечислим простейшие свойства конечномерных свободных модулей, которые обобщают аналогичные свойства конечномерных линейных пространств.

Утверждение 1.1 ([19, §III.6]). Пусть — кольцо, — конечно­ мерный свободный модуль над. Справедливы следующие утвер­ ждения:

1. В существует базис, то есть набор элементов 1,..., такой, что любой элемент представляется в виде единственным образом. Количество элементов в базисе равно 2. Сопряженный модуль * также является конечномерным свободным модулем, его размерность совпадает с размерно­ 3. Если 1,..., — базис, то существуют линейные функци­ оналы 1,..., *, удовлетворяющие соотношению Эти функционалы образуют базис *, называемый сопряжен­ 4. Любой линейный функционал * имеет вид Определим теперь основные объекты, сложность которых мы будем изучать — билинейные отображения и алгебры.

Определение 1.7. Пусть — кольцо,,, — модули над. Отоб­ ражение : называется билинейным, если выполняются соотношения В случае, если из контекста не ясно, какое кольцо рассматри­ вается, мы будем использовать термин «-билинейное отображение».

Если,, — конечномерные свободные модули, то для то­ го, чтобы однозначно задать билинейное отображение, достаточно определить его значения на парах базисных элементов и. Дей­ ствительно, пусть в, и фиксированы базисы (1,..., ), (1,... ) и (1,..., ) соответственно. Если заданы значения вычислить, исходя из билинейности:

Таким образом, для полного задания билинейного отображения до­ статочно задать коэффициентов.

Определение 1.8. Пусть — кольцо. Алгеброй над называется модуль с заданной на нем билинейной операцией умножения. Ал­ гебра называется ассоциативной, если умножение ассоциативно, т. е.

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

Заметим, что любое кольцо может рассматриваться как алгеб­ ра над Z, если операцию умножения целого числа на элемент кольца определить обычным образом:

1.2. Ассоциативные алгебры над полем В главах 2 и 3 мы будем рассматривать сложность умножения в конечномерных ассоциативных алгебрах с единицей над полем. Тео­ рия таких алгебр является классическим разделом алгебры, результа­ ты которого изложены во многих монографиях и учебных пособиях, напр. [21, 33, 35]. В этом разделе приведены основные определения и результаты этой теории, которыми мы будем пользоваться.

Термин «алгебра» будет обозначать конечномерную ассоциатив­ ную алгебру с единицей над некоторым полем. Поле можно рассматривать как подмножество алгебры, если отождествить ска­ ляры с элементами · 1.

Определение 1.9. Подмодуль алгебры называется левым иде­ алом, если он замкнут относительно умножения на любой элемент алгебры слева, т. е. для любых, произведение при­ надлежит. Аналогично опредляются правые идеалы. Подмодуль, являющийся одновременно левым и правым идеалом, называется двуcторонним идеалом или просто идеалом. Левый (правый, двусто­ ронний) идеал называется максимальным, если он не содержится ни в каком левом (правом, двустороннем) идеале, кроме всей алгебры.

Определение 1.10. Идеал называется нильпотентным, если для некоторого натурального произведение любых элементов идеала равно 0.

Алгебра называется полупростой, если она не имеет нильпо­ тентных идеалов кроме тривиального идеала 0. Алгебра называется простой, если она не имеет идеалов кроме 0 и всей алгебры. Алгебра называется локальной, если она имеет единственный максимальный левый идеал. Алгебра называется алгеброй с делением, если любой ее ненулевой элемент обратим.

Определение 1.11. Квадратные матрицы размера с элемен­ тами из алгебры с обычным образом определенным умножением образуют алгебру, которая обозначается и называется алгеброй матриц над.

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

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

Определение 1.12. Коммутативная алгебра с делением над полем сама является полем и называется алгебраическим расширением поля.

Определение 1.13. Если — алгебра с делением, то для любого элемента множество элементов, представимых в виде линейной ком­ бинации степеней, является расширением основного поля, которое называется расширением, порожденным элементом. Расширение, порожденное каким-либо своим элементом, называется простым.

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

В процессе исследования задачи о сложности умножения матриц был выделен класс алгоритмов, обладающих определенной струк­ турой: вначале над каждым из аргументов производятся линейные операции (умножение на константы и сложение), затем полученные таким образом промежуточные результаты перемножаются, и затем с помощью только линейных операций из произведений получаются координаты результата. Мерой сложности алгоритма при этом счи­ тается количество умножений на втором этапе, линейные операции считаются «бесплатными». Дадим формальное определение.

Определение 1.14. Пусть — кольцо,,, — конечномерные свободные модули над и : — билинейное отображе­ ние. Билинейным алгоритмом для называется последовательность такая, что для любых, выполняется Количество троек называется сложностью билинейного ал­ горитма. Билинейной сложностью или рангом отображения на­ зывается минимально возможная сложность билинейного алгоритма для этого отображения. Ранг отображения обозначается ().

Если алгебрa является конечномерным свободным модулем, то ее билинейной сложностью или рангом называется ранг умножения в ней. Ранг алгебры обозначается ().

Определение билинейного алгоритма (1.2) можно записать также в координатной форме. Если отображение задано в некоторых базисах (1,..., ), (1,..., ), (1,..., ) соотношением вида (1.1) с коэффициентами, а составляющие билинейного алгоритма, и имеют в этих базисах координаты, и, т.е.

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

Определение 1.15. Левым ядром lker билинейного отображения : называется множество всех таких, что для любого имеет место (, ) = 0. Аналогично определяется правое ядро rker.

Лемма 1.1. Пусть : — билинейное отображение. Если lker = 0, то в любом билинейном алгоритме (1, 1, 1 ;... ;, ; ) для функционалы порождают в линейной оболочке все простран­ ство * Доказательство. Допустим, что линейная оболочка набора функцио­ налов {1,..., } не совпадает с пространством *. В этом случае су­ ществует ненулевой элемент такой, что 1 () = · · · = () = 0.

Из определения билинейного алгоритма следует, что (, ) = 0 для любого, т.е. lker.

Заметим, что условие доказанной леммы верно, если — умно­ жение в некоторой алгебре с единицей.

Лемма 1.2. Пусть : — билинейное отображение, пространство. Тогда где — количество функционалов, равных тождественно нулю Доказательство. Ограничив все функционалы на подпростран­ ражения |. В нем тройки, для которых | = 0 можно опу­ стить, после чего получится алгоритм для | сложности, существование которого означает, что (| ) A. Алдером и Ф. Штрассеном в [1] была получена нижняя оценка сложности умножения в ассоциативных алгебрах над полем.

Теорема 1.2 (A. Алдер, Ф. Штрассен). Пусть — поле, — ко­ нечномерная ассоциативная алгебра с единицей над. Для ранга алгебры справедлива оценка где () — количество максимальных двуcторонних идеалов алгеб­ В случае, если эта оценка достигается, алгебра называется алгеброй минимального ранга, а если ранг алгебры на единицу больше оценки Алдера-Штрассена — алгеброй почти минимального ранга.

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

Теорема 1.3 (У. Баур, см. [11, теорема 17.27]). Если — алгебра с делением, то существует элемент такой, что справедлива нижняя оценка Для оценки сложности отображений с малой размерностью од­ ного из пространств аргументов можно использовать следующую нижнюю оценку:

Теорема 1.4 (Ф. Штрассен, см. [28]). Пусть — поле, : — билинейное отображение, и операторы определяются соотношением = (, ), причем 1 невырожден. Тогда Де Гроотом в [14] была построена теория эквивалентных преоб­ разований билинейных алгоритмов.

Определение 1.16. Пусть — кольцо,,, — конечномерные свободные модули над, и : — билинейное отображение.

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

Отображения из группы изотропии позволяют получать из би­ линейных алгоритмов для новые билинейные алгоритмы.

Утверждение 1.2. Пусть — кольцо,,, — конечномерные свободные модули над, и : — билинейное отображе­ ние. Если (1, 1, 1 ;... ;,, ) — билинейный алгоритм для, то будет билинейным алгоритмом для.

Доказательство. Непосредственно следует из определений:

Определение 1.17. Билинейные алгоритмы (1, 1, 1 ;... ;,, ) и (1, 1, 1 ;... ;,, ) для называются эквивалентными, если они получаются друг из друга преобразованием, описанным в преды­ дущем утверждении, т. е.

для некоторой тройки (,, ) ().

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

1.4. Тензорные произведения и расширение кольца скаляров В данном разделе термин «алгебра» будет обозначать комму­ тативную ассоциативную алгебру с единицей над кольцом, так что любая алгебра над кольцом также является кольцом.

Введем конструкцию тензорного произведения модулей. Это основная конструкция мультилинейной алгебры, которая широко используется при изучении колец и их модулей (см. напр. [9, 19]).

Определение 1.18. Пусть — кольцо, и — модули над.

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

Элементы тензорного произведения называются тензорами. Тен­ зоры вида называются разложимыми.

Утверждение 1.3 ([17, §X.5]). Имеют место следующие изомор­ физмы В случае, если один или оба модуля в тензорном произведении являются алгебрами, на тензорном произведении также можно ввести дополнительную структуру.

Определение 1.19. Пусть — кольцо, и — алгебры над. На тензорном произведении можно ввести структуру алгебры над, если определить операцию умножения на разложимых тензорах как и распространить на все по билинейности. Эта алгебра назы­ вается тензорным произведением алгебр и.

Определение 1.20. Пусть — кольцо, — алгебра над, а — модуль над. На тензорном произведении можно ввести структуру модуля над, определив умножение следующим образом:

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

Эти определения корректны, т. е. определенные операции согла­ сованы с равенством тензоров (1.4) (см. напр. [19, §§XVI.4-6]).

Так как любое кольцо является алгеброй над Z, можно рассмат­ ривать тензорные произведения колец. На таком произведении можно ввести структуру кольца в соответствии с определением 1.19 и алгеб­ ры над каждым из сомножителей в соответствии с определением 1.20.

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

Определение 1.21. Пусть — кольцо, — алгебра над, а, и — конечномерные свободные модули над. Для любого -билинейного отображения : определим -билинейное отобра­ как а на произвольных тензорах исходя из свойства -билинейности, т. е.

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

Многие важные билинейные отображения, например, умноже­ ние матриц или полиномов, являются Z-билинейными, что значит, что можно рассматривать их сложность над произвольным кольцом.

Интересен вопрос о том, как связаны значения ранга Z-билинейного отображения над различными кольцами. Ясно, что если — алгеб­ ра над, то каждому билинейному алгоритму (1, 1, 1 ;... ;,, ) над соответствует билинейный алгоритм (1, 1, 1 ;... ;,, ) над () (). Этот факт впервые был замечен Т. Д. Хауэллом в работе [15], где также были рассмотрены некоторые случаи, в ко­ торых это неравенство обращается в равенство, то есть переход к алгебре не дает преимуществ при вычислении.

Теорема 1.5 (Т. Д. Хауэлл). Пусть — кольцо, — алгебра над. Для любого -билинейного отображения имеет место нера­ венство () ().

Для любого кольца и любого -билинейного отображения справедливо равенство () = [] ().

Если — алгебраически замкнутое поле, то для любой алгеб­ ры над, = 0, и для любого -билинейного отображения справедливо равенство () = ().

Позже Шёнхаге [24] исследовал вопрос о связи ранга над полями одной характеристики и показал, что при переходе от поля к его рас­ ширению ранг уменьшается не более, чем в константное количество раз. В последней главе данной диссертации мы рассмотрим связь рангов над полями различных характеристик.

Алгоритмы умножения обобщенных В данной главе доказывается критерий почти минимальности ранга локальной алгебры в терминах существования базисов опре­ деленного вида. С помощью этого критерия построен билинейный алгоритм ранга 8 для умножения обобщенных кватернионов над полем характеристики, отличной от 2. Результаты этой главы опуб­ ликованы в [37, 38].

2.1. Алгебры обобщенных кватернионов Для классификации алгебр почти минимального ранга нам по­ требуется рассмотреть сложность умножения в алгебрах обобщенных кватернионов. Это некоммутативные ассоциативные алгебры, обоб­ щающие на случай произвольного основного поля конструкцию алгебры кватернионов, открытую У. Р. Гамильтоном в XIX в.

Определение 2.1. Центром алгебры называется подалгебра, со­ стоящая из элементов, коммутирующих с любым элементом алгебры:

Алгебра над называется центральной, если ее центр совпадает с.

Определение 2.2. Алгеброй обобщенных кватернионов над на­ зывается простая центральная алгебра размерности 4.

Структура алгебр обобщенных кватернионов определяется сле­ дующими утверждениями:

Теорема 2.1 (см. [8]). Если char = 2, то любая алгебра обобщен­ ных кватернионов порождается двумя элементами и, удовле­ творяющими условиям где,,, = 0. Элементы 1,,, = образуют базис алгебры. Такую алгебру будем обозначать,.

Теорема 2.2 (см. [8]). Если char = 2, то любая алгебра обобщен­ ных кватернионов порождается двумя элементами и, удовле­ творяющими условиям где,, = 0. Элементы 1,,, = образуют базис алгебры.

Теорема 2.3 (см. [8]). Любая алгебра обобщенных кватернионов либо изоморфна алгебре матриц 22, либо является некоммутативной алгеброй с делением. Любая некоммутативная алгебра с делением размерности 4 является алгеброй обобщенных кватернионов.

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

Определение 2.3. Пусть — поле,,, — векторные пространт­ сва над, и : — билинейное отоборажение. Назовем элемент 0 (левым) -регулярным, если линейный оператор (0, ·) инъективен, т.е. (0, ) = 0 тогда и только тогда, когда Определение 2.4. Билинейный алгоритм (1, 1, 1 ;... ;,, ) бу­ дем называть двухкомпонентным, если множество индексов {1,..., } можно разбить на непересекающиеся множества и такие, что { | } и { | } являются базисами пространств * и * соответственно.

Лемма 2.1. Пусть — поле,,, — векторные пространт­ сва над, и : — билинейное отоборажение. Если () = dim + dim, lker = 0, и в любом базисе пространства найдется -регулярный элемент, то любой оптимальный били­ нейный алгоритм для является двухкомпонентным.

Доказательство. Пусть dim =, dim =. Рассмотрим опти­ мальный билинейный алгоритм (1, 1, 1 ;... ; +, +, + ) для.

Так как lker = 0, функционалы 1,..., + порождают все про­ странство *. Пусть, без ограничения общности, 1,..., — базис *, а элемент 1 двойственного базиса 1,..., является -регулярным.

Из -регулярности 1 следует, что функционалы 1, +1,..., + порождают все пространство *, так как иначе существует ненулевой элемент такой, что 1 () = +1 () = · · · = + () = 0, и из определения билинейного алгоритма следует, что (1, ) = 0.

Обозначим через линейную оболочку множества функциона­ лов {+1,..., + }. Если есть все пространство *, то множества индексов = {1,..., } и = {+1,..., +} образуют разбиение, требуемое в определении двухкомпонентного алгоритма. В противном случае dim = 1 и существует единственная с точностью до умножения на константу линейная зависимость между +1,..., +.

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

жении его по базису 1,..., элемент 1 присутствует с ненуле­ вым коэффициентом, то множества индексов = {2,...,, } и = {1, + 1,..., + } {} образуют требуемое разбиение. Иначе рассмотрим функционалы 1, ++1,..., +. Эти функционалы не могут порождать все *, так как их количество меньше размерности dim =. Взяв ненулевой элемент 0 такой, что этого промежутка не содержат 1 в разложении по базису (1,..., ).

Получаем противоречие с -регулярностью элемента 1.

Теорема 2.4. Пусть — поле,,, — векторные пространтсва над, и : — билинейное отоборажение. Двухкомпо­ нентный билинейный алгоритм для существует тогда и только тогда, когда существуют базисы 1,..., и 1,..., пространств и соответственно, и наборы 1,..., и 1,..., элементов такие, что для некоторых коэффициентов,.

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

Пусть 1,..., и 1,..., — двойственные им базисы. Тогда и 1,..., — базисы, двойственные к ( ) и ( ) соответственно, то билинейный алгоритм вычисляет. Для того, чтобы проверить это, заметим, что в силу билинейности определение билинейного алгоритма (1.2) достаточно проверить на парах (, ) элементов базисов, а на этих парах оно обращается в равенство (2.1).

Этот результат позволяет получить критерий почти минималь­ ности для локальных алгебр и, в частности, для алгебр с делением.

Если — умножение в алгебре, -регулярные элементы суть обра­ тимые элементы алгебры. Справедливо следующее утверждение об обратимости элементов в локальной алгебре:

Теорема 2.5 ([35, теорема III.2.2]). Элемент локальной алгебры обра­ тим тогда и только тогда, когда он не содержится в максимальном левом идеале.

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

Теорема 2.6. Пусть — поле, — локальная алгебра над, dim =. Если не является алгеброй минимального ранга, то есть () 2, то имеет почти минимальный ранг тогда и только тогда, когда в существует пара базисов 1 = 1, 2,..., такие, что для некоторых,.

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

При этом элементы 1 и 1 можно взять равными 1, так как эквива­ лентное преобразование 1, 1, 1 1 не влияет на выполнение соотношения (2.2).

2.3. Сложность умножения обобщенных кватернионов Докажем, что алгебры обобщенных кватернионов над полем характеристики, отличной от 2, являются алгебрами почти мини­ мального ранга.

Теорема 2.7. Пусть — поле, char = 2, — алгебра обобщенных кватернионов с делением над. Тогда () = 8.

Доказательство. Так как любое подполе алгебры обощенных ква­ тернионов имеет размерность 1 или 2, по теореме 1.3 имеет место нижняя оценка () 8. В силу результатов предыдущего раздела, для доказательства того, что () = 8, достаточно привести при­ 1,..., 4, удовлетворяющих условию (2.2).

Напомним, что по теореме 2.1 в существует базис 1,,, и этот стандартный кватернионный базис:

а наборы и определим следующим образом:

где,, — некоторые ненулевые константы из. Непосредственно проверяется, что условие (2.2) для указанных кватернионов выпол­ няется с коэффициентами, указанными в табл. 2.1.

точным значением ранга.

2.4. Ранг произведения алгебр обобщенных кватернионов Теорема 2.8. Пусть — поле. Если 1 и 2 — алгебры обобщенных кватернионов с делением над, а = 1 2, то () = 16.

Доказательство. Верхняя оценка () 16 следует из теоремы 2.7.

Докажем нижнюю оценку. В тексте доказательства будем отождеств­ лять 1 и 2 с их образами в.

жения в. Так как — алгебра с единицей, функционалы порож­ дают все пространство *.

Если каждый из функционалов равен нулю либо на 1, либо на 2, то, рассмотрев по отдельности тройки алгоритма, соответству­ ющие тем и другим, мы получим билинейные алгоритмы для 2 и для 2 соответственно, и поскольку ранг каждого из них меньше 8, ранг исходного алгоритма не меньше 16.

В противном случае найдется функционал, не равный нулю ни на 1, ни на 2. Для базиса, содержащего такой функционал, в двойственном базисе будет присутствовать обратимый элемент, то есть элемент вида = (, ) с ненулевыми и. При применении эквивалентного преобразования 1, 1 этот элемент переходит в 1. Таким образом, без ограничения общности можно считать, что 1,..., 8 — базис, 1 = 1, 2,..., 8 — двойственный базис. В базисе 1,..., 8 найдется такой элемент = (, ), что. Пусть, без ограничения общности, этот элемент — 2.

чив все на линейную оболочку пары элементов {1, 2 }, мы по­ отображения, полученного ограничением умножения на, причем 1 |, 2 | — двойственный базис к базису 1, 2 подпространства.

Докажем, что сложность этого алгоритма не меньше 10. Допу­ стим, она равна 9, т. е. = 15. Функционалы при = 1, 9,..., образуют базис *, так как в противном случае, взяв ненулевой эле­ мент, на котором они все равны нулю, получим 1 · = 0. Пусть 1, 9..., 15 — двойственный к 1, 9,..., 15 базис. Тогда Так как = 0, из первого равенства следует, что (1) = 0.

чаем Аналогичное равенство должно выполняться для первых компонент соответствующих элементов. Так как — базис, можно выбрать четыре элемента 1 = (1, 1 ),..., 4 = (4, 4 ) такие, что их первые компоненты 1,..., 4 образуют базис 1. Пусть также 2 = (2, 2 ).

Таким образом, равенство (2.3) для первых компонент имеет вид Так как 2 было выбрано так, что 2, имеем 2 = 0. Получаем, что для элементов базиса 1 (2 )1,..., 4 (2 )1 выполнено то есть 1 = (2 ), что противоречит некоммутативности алгебры 1.

Таким образом, алгебра = 1 2 не является алгеброй почти минимального ранга, так как она имеет два максимальных идеала (а именно, 1 и 2 ) и ранг 16 > 2 dim 2 + 1.

Таблица 2.1. Коэффициенты соотношения (2.2) для обобщенных кватернионов.

В данной главе получена классификация полупростых алгебр почти минимального ранга над бесконечным полем характеристики, отличной от 2. Для этого доказана нижняя оценка, улучшающая оценку М. Блезера. Результаты главы опубликованы в [38].

3.1. Следствия известных оценок Рассмотрим вопрос о почти минимальности полупростой алгеб­ ры над полем, разложение Веддерберна-Артина которой состоит из сомножителей: 1 · · ·. В этом случае оценка Алдера­ Штрассена имеет вид так как пересечение любого идеала с сомножителем должно быть идеалом, то есть либо 0, либо и, следовательно, максимальными При анализе структуры полупростых алгебр почти минимально­ го ранга мы будем применять следующую лемму, которая использу­ ется в доказательстве теоремы Алдера-Штрассена.

Лемма 3.1 (А. Алдер, Ф. Штрассен, см. [1]). Если — простая алгебра, — произвольная алгебра, то справедлива оценка Обозначим символом () разность между рангом алгебры () и оценкой Алдера-Штрассена 2 dim (). Из леммы 3. следует, что для полупростых и справедливо соотношение Это значит, что полупростая алгебра минимального ранга ( = 0) является произведением простых алгебр минимального ранга, а полу­ простая алгебра почти минимального ранга ( = 1) — произведением простых алгебр минимального и почти минимального ранга.

Алгебры минимального ранга были описаны в [3]. Из этого описа­ ния следует, что простыми алгебрами минимального ранга являются алгебра матриц 22 и простые алгебраические расширения поля, причем в случае конечного поля размерность расширения не Мы будем рассматривать только бесконечные поля. Пусть простая алгебра изоморфна. В случае = 1 возможны 3 случая для : простое расширение, расширение, не являющееся про­ стым, и некоммутативная алгебра с делением. Простые расширения являются алгебрами минимального ранга. Для оценки сложности расширений, не являющихся простыми, нам потребуются некоторые факты из теории несепарабельных расширений.

Определение 3.1. Неприводимый многочлен называется сепарабель­ ным, если все его корни (принадлежащие алгебраическому замыка­ нию ) различны. Минимальным многочленом элемента алгебры называется многочлен [] такой, что () = 0, имеющий минимально возможную степень и единичный старший коэффициент.

Элемент алгебраического расширения называется сепарабель­ ным, если его минимальный многочлен сепарабелен. Расширение называется сепарабельным, если все его элементы сепарабельны.

Лемма 3.2 (см. [33, §44,§46], [19, упр. V.25]). Любое алгебраическое расширение поля характеристики 0 сепарабельно и просто.

Над полем характеристики размерность любого алгебраиче­ ского расширения имеет вид, где — размерность макси­ мального сепарабельного подрасширения. Расширение является простым тогда и только тогда, когда найдется элемент Таким образом, расширения, не являющиеся простыми, явля­ ются несепарабельными. для разбора этого случая мы применим оценку Баура (теорема 1.3) с учетом приведенной леммы о размерно­ сти несепарабельных расширений. Из этой леммы следует, что если расширение имеет размерность и не является простым, то любое его простое подрасширение () имеет размерность, где — размерность его максимального сепарабельного подполя, и <, так как иначе найдется несепарабельный элемент, для кото­ рого сепарабелен, а несепарабелен, из чего следует простота исходного расширения. Следовательно, по теореме Баура что при = 2 означает, что расширение не является алгеброй почти минимального ранга.

Для некоммутативных алгебр с делением можно применить следующие оценки, полученные М.Блезером [4].

Теорема 3.1 (М. Блезер). Для некоммутативной алгебры с делени­ ем справедлива оценка — простая алгебра. Тогда При > 6 оценка теоремы 3.1 дает неравенство которое означает, что не является алгеброй почти минимального ранга. Так как размерность алегбры над ее центром должна быть квадратом (см. [35, следствие IV.5.2]), некоммутативных алгебр с делением размерностей 2, 3, 5 и 6 не существует. Некоммутативные алгебры с делением размерности 4 — это алгебры обобщенных ква­ тернионов, рассмотренные ранее. Из результатов предыдущей главы следует, что они являются простыми алгебрами почти минимального ранга, причем полупростая алгебра почти минимального ранга не может содержать более одного простого сомножителя такого вида.

При > 1 можно применить оценку теоремы 3.2. Эта оценка позволяет доказать, что простые алгебры с 4, а также с = 3, dim 3 и = 2, dim 4, не являются алгебрами почти минимального ранга.

Рассмотрим оставшиеся случаи. Случай = 2, dim = 1 со­ ответствует алгебре матриц 22, которая является алгеброй ми­ нимального ранга. Случай = 3, dim = 1 — это алгебра 33, рассмотренная в [2], где доказана оценка, свидетельствующая о том, что эта алгебра не является алгеброй почти минимального ранга.

Теорема 3.3 (М. Блезер). ( 33 ) 19.

Случай = 2, dim = 2 рассмотрен в [7] для поля = R и так­ же не является алгеброй почти минимального ранга. Доказательство не использует специфики поля R и может быть дословно переписано для любого поля характеристики, отличной от 2.

Теорема 3.4 (М. Блезер, А. М. де Вольтер). Если — алгебраиче­ ское расширение поля, dim = 2, то ( 22 ) 17.

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

3.2. Сложность умножения в алгебрах матриц Лемма 3.3. Пусть (1,..., ) — ненулевой многочлен степени над бесконечным полем. Тогда существует набор 1,...,, в котором не более ненулевых значений, на котором этот многочлен не равен 0. Если существенно зависит от переменной, то одним из ненулевых значений можно взять.

Доказательство. Если многочлен не равен тождественно 0, то существует моном, входящий в него с ненулевым коэффициентом. В случае, если существенно зависит от, то существует моном с нену­ левым коэффициентом, содержащий. Так как степень многочлена равна, этот моном содержит не более переменных.

Подставим нули вместо всех переменных, кроме тех, которые содержит рассматриваемый моном, а потому не равен тождественно нулю, т.е. найдутся значения 1,...,, при подстановке которых полином имеет ненулевое значение. Если при этом рассматривае­ мый моном содержит переменную, то можно записать в виде =0 (), где не зависят от и не все при 1 тожде­ ственно равны нулю. Подставив вместо всех переменных, кроме, получим, что существенно зависит от и можно подставить нену­ левое значение вместо так, что получившееся значение многочлена будет ненулевым.

Лемма 3.4. Пусть — расширение бесконечного поля, dim =, : — ненулевой линейный функционал, а 1,... 2 — некоторый базис -алгебры. Многочлен существенно зависит от всех переменных, кроме тех, которые соответствуют скалярным матрицам =,, если такие элементы содержатся в рассматриваемом базисе.

Доказательство. Пусть 1 =. Докажем, что многочлен суще­ ственно зависит от 1. Зависимость от остальных переменных дока­ зывается аналогично. Так как 1 — нескалярная матрица, найдется вектор 1 такой, что 1 1 = 2 не пропорционален 1. Дополним пару 1, 2 до -базиса пространства и будем рассматривать мат­ рицы из как операторы в этом базисе. В этом базисе 1 имеет где на местах, отмеченных звездочками, могут стоять произвольные значения из. Выберем так, что = в том же базисе имеет вид diag(1, 2,..., ), где все различны. При этом оператор ad : [, ] переводит матрицу = ( ) в матрицу [, ] = (( ) ). Возьмем такой, что () = 0 и выберем матрицу и + 1 имеет вид Тогда det[, ] = 0, так как первый столбец [, ] будет нулевым, и det[, + 1 ] =. Получаем, что можно выбрать набор (, ) так, что что означает, что переменная 1 является существенной.

Из любого базиса -алгебры можно выбрать не более элементов, в линейной оболочке которых найдутся 3 элемента 1, 2, 3 такие, что 1 и [1 2, 1 3 ] обратимы.

Доказательство. Пусть 1,..., 2 — рассматриваемый базис. Ес­ ли в нем есть обратимая матрица, то возьмем 1 =. Ина­ че пусть : — некоторый ненулевой линейный функцио­ нал и таков, что () = 0. Рассмотрим вначале многочлен () = (det с определителем, и является однородным многочленом степени (легко проверить, что () = ()). По лемме 3.3 можно вы­ ненулевых, то есть в линейной оболочке элементов базиса найдется невырожденная матрица 1.

Далее, рассмотрим базис, составленный из элементов = исследованный в предыдущей лемме. Это однородный многочлен степени 2. Снова применяя лемму 3.3, получаем, что найдется 2 элементов нового базиса, содержащих матрицы 2 = 1 2 и 3 = 1 3 такие, что [2, 3 ] обратима, причем один из элементов базиса может быть задан заранее, если он не является скалярной матрицей. Тогда в линейной оболочке соответствующих элементов исходного базиса содержатся матрицы 2 и 3.

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

Доказательство. Пусть (1, 1, 1 ;... ;,, ) — билинейный алго­ ритм умножения в. По лемме 1.1 из набора можно выбрать базис пространства *. По лемме 3.5 из двойственного базиса пространства можно выбрать не более 3 1 элемента, в линейной оболочке которых найдутся элементы 1, 2, 3 такие, что 1 и [1 2, 1 3 ] обратимы. Обозначим линейную оболочку этих трех элементов через Рассмотрим ограничение умножения на линейную оболочку. По теореме 1.4 ранг этого билинейного отображения не меньше dim. По лемме 1.2 ранг исходного алгоритма не меньше (dim 3 + 1) + 3 dim, так как все, кроме соответствующих выбранным Из полученного результата следует, что алгебры вида при dim = 2, = 3 или dim = 3, = 2 не являются алгебрами почти минимального ранга.

Учитывая результаты предыдущего раздела, окончательно по­ лучаем полное описание полупростых алгебр почти минимального ранга.

Теорема 3.6. Любая полупростая алгебра почти минимального ранга над бесконечным полем, char = 2, имеет вид или, где — алгебра обобщенных кватернионов с делением, — полупростая алгебра минимального ранга.

Целочисленные билинейные отображения над полями различных характеристик В главе рассматривается связь рангов Z-билинейного отображе­ ния над полями различной характеристики. Результаты опубликова­ ны в [39–41] 4.1. Ненулевые тензорные произведения При работе с тензорными произведениями следует учитывать тот факт, что произведение ненулевых модулей может быть равно 0. Так, например, Q Z = 0 для любого поля простой характеристики, потому что для любого разложимого тензора справедливо = () = 0 = 0. В этом разделе мы приведем некоторые случаи, в которых тензорное произведение не является нулевым. Эти результаты в алгебре хорошо известны и являются простейшими частными случаями общих теорем (см. напр. [9, 19]) Лемма 4.1. Пусть — кольцо, — конечномерный свободный модуль над, — произвольный ненулевой модуль над. Тогда тензорное произведение не является нулевым модулем.

Доказательство. Следует из простейших свойств тензорного произ­ ведения (утверждение 1.3):

Лемма 4.2. Тензорное произведение ненулевых линейных пространств над полем не является нулевым.

Доказательство. Ненулевое линейное пространство над полем можно представить в виде прямой суммы одномерного пространства и какого-то его дополнения:. Значит и тензорное про­ изведение также содержит некоторое одномерное подпространство, т. к.

Лемма 4.3 (см. [9, §III.3]). Пусть — кольцо без делителей нуля, — его поле частных, — модуль над, содержащий свободный элемент, т. е. элемент, для которого = 0 для любого.

Тогда не является нулевым модулем.

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

Доказательство. Следует из двух предыдущих лемм:

так как и = — линейные пространства над, причем ненулевое по предыдущей лемме.

4.2. Связь между билинейными алгоритмами Мы будем рассматривать Z-билинейное отображение и алго­ ритмы для него над различными кольцами и полями, определенные в разделе 1.3 (определение 1.21). Под «алгеброй» будет пониматься коммутативная ассоциативная алгебра с единицей над кольцом.

Основным инструментом является простое наблюдение, основан­ ное на теореме Хауэлла о том, что ранг отображений над алгебраиче­ ски замкнутым полем минимален (теорема 1.5).

Лемма 4.5. Если — кольцо, — алгебраически замкнутое поле, — Z-билинейное отображение, и Z = 0, то () ().

Доказательство. Так как Z есть алгебра над, то () Z (). Так как Z также есть алгебра над и алгебраически замкнуто, то по теореме 1.5 имеем Z () = ().

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

Лемма 4.6. Пусть — коммутативное кольцо без делителей нуля, — его поле частных и — -билинейное отображение. Тогда верно равенство Доказательство. Если (1, 1, 1 ;... ;,, ) — билинейный алго­ для.

Обратно, пусть (1, 1, 1 ;... ;,, ) — билинейный алгоритм над для. Определим как произведение знаменателей всех ко­ эффициентов всех функционалов в некотором базисе. Аналогично определим и. Тогда последовательность троек ( 1, 1, 1 ;

... ;,, ) образует билинейный алгоритм над для били­ нейного отображения.

следует утверждение леммы.

Лемма 4.7. Пусть — коммутативное кольцо, — -билинейное отображение, { | } — семейство алгебр над и =.

Тогда справедливо равенство Доказательство. Пусть (,1,,1,,1 ;... ;,,,,, ) — оптималь­ ные билинейные алгоритмы над для. Добавив при необходимости нулевые тройки, можно считать что ранг каждого из этих алгоритмов равен = max (). Рассмотрим эти алгоритмы в координатном виде; пусть коэффициенты функционалов,,, и элементов, в стандартных базисах равны,,, и, соответственно. Рассмот­ рим билинейный алгоритм над, коэффициенты,, элемен­ тов которого задаются последовательностями (, | ), (, | ), (, | ) соответственно. Так как соотношение (1.3) выполняется покоординатно, то полученный билинейный алгоритм (,, ) будет алгоритмом для над прямым произведением. Таким образом, (). И наоборот, взяв -ю координату из каждого коэффици­ ента каждого элемента билинейного алгоритма над, мы получим билинейный алгоритм над соответствующей компонентой.

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

Символом Q обозначается алгебраическое замыкание поля рацио­ нальных чисел, символом F — алгебраическое замыкание поля из элементов.

Теорема 4.1. Для любого Z-билинейного отображения справед­ ливо соотношение для всех простых, кроме, быть может, конечного числа.

Доказательство. Рассмотрим оптимальный алгоритм над Q для Zбилинейного отображения. Так как в алгоритме участвует толь­ ко конечное число коэффициентов,,, то подполе, по­ рожденное этими коэффициентами, будет конечным алгебраическим расширением Q, для которого () = Q (). Применяя лемму 4. для кольца целых элементов, получим, что () = () для некоторого. Из доказательства леммы видно, что можно взять где — целое алгебраическое и Z.

Кольцо, рассматриваемое как модуль над Z, является свобод­ ным модулем, поэтому тензорное произведение Z F не является = 0. Равенство = 0 в F выполняется для не более чем конечного числа характеристик (а именно, для простых делителей ), поэто­ му неравенство Q () F () выполнено для всех, кроме, быть может, конечного числа.

Для перехода от билинейных алгоритмов для Z-билинейного отображения над полями простой характеристики к алгоритмам над полем характеристики 0 рассмотрим последовательность полей F. Пусть — минимально возможное число, встречающееся в после­ довательности F () бесконечное число раз. Рассмотрим бесконечное прямое произведение Любой кратный 1 элемент этого кольца не равен 0, так как он не равен 0 в компонентах произведения, соответствующих достаточно большим. Как следствие, Z Q не является нулевым кольцом (по лемме 4.4).

Таким образом = () Q () по лемме 4.7. Из выбора числа следует, что неравенство F () < может выполняться только для конечного числа простых.

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

Объединяя эти два неравенства, получаем утверждение теоремы.

4.3. Метаматематическое доказательство Интересно, что теорему 4.1 можно доказать также методами математической логики, не прибегая к чисто алгебраическим кон­ струкциям. Для этого можно использовать полноту теорий алгебраически замкнутых полей характеристики. В дополнение к обычным аксиомам поля в используется схема аксиом алгебра­ а также аксиомы, определяющие характеристику поля: в случае простой характеристики аксиомой теории будет формула (0 = 1 + · ·· + 1), а теория 0 содержит схему аксиом ¬ для всех простых.

Теорема 4.2 (А. Робинсон, см. [23]). Для любой характеристики теория полна.

Из этой теоремы следуют утверждения о связи выводимости формул первого порядка в теориях.

Утверждение 4.1. Если — алгебраически замкнутое поле ха­ рактеристики, то любая формула общезначима в тогда и только тогда, когда она выводима в.

Утверждение 4.2 (см. [20]). Формула выводима в теории тогда и только тогда, когда она выводима в для всех простых, кроме, может быть, конечного числа.

Приведем теперь второе доказательство теоремы 4.1.

Доказательство. Заметим, что для Z-билинейного отображения утверждение () можно записать в виде замкнутой формулы логики предикатов в сигнатуре теории колец =, +, ·, 0, 1. Действи­ тельно, пусть задается в некоторой тройке базисов коффициентами в соответствии с (1.1). Исходя из координатного представления тогда и только тогда, когда истинна формула Так как целые, то их можно записать в виде суммы единиц и при необходимости перенести в правую часть, чтобы избавиться от знака «минус». Полученная формула является замкнутой формулой теории колец, и утверждение () верно тогда и только тогда, когда эта формула истинна в кольце. Как следствие, в виде формулы теории колец можно записать и утверждение () =.

Применяя эти следствия к формуле, выражающей утверждение () =, получаем утверждение теоремы 4.1.

1. Alder A., Strassen V. On the Algorithmic Complexity of Associative Algebras // Theor. Comput. Sci. — 1981. — Vol. 15. — P. 201–211.

2. Blser M. On the complexity of the multiplication of matrices of small formats // J. Complexity. — 2003. — Vol. 19, no. 1. — P. 43–60.

3. Blser M. A Complete Characterization of the Algebras of Minimal Bilinear Complexity // SIAM J. Comput. — 2004. — Vol. 34, no. 2. — P. 277–298.

4. Blser M. Beyond the Alder-Strassen bound // Theor. Comput. Sci. — 2005. — Vol. 331, no. 1. — P. 3–21.

5. Blser M. Fast matrix multiplication // Preprint. — 2013.

6. Blser M., Chokaev B. Algebras of minimal multiplicative complexity // Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC). — 2012. — P. 224–234.

7. Blser M., de Voltaire A.M. Semisimple algebras of almost minimal rank over the reals // Theor. Comput. Sci. — 2009. — Vol. 410, no. 50. — P. 5202–5214.

8. The Book of Involutions / M.A. Knus, A. Merkurjev, M. Rost, J.-P. Tignol. — AMS, 1998.

9. Bourbaki N. Algebra. Chapters 1–3. — Springer, 1998.

10. Brockett R. W., Dobkin D. On the optimal evaluation of a set of bilinear forms // Linear Algebra and Its Applications. — 1978. — Vol. 19, no. 3. — P. 207–235.

11. B rgisser P., Clausen M., Shokrollahi M.A. Algebraic Complexity Theory. — Springer, 1997.

12. Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // Journal of symbolic computation. — 1990. — Vol. 9, no. 3. — P. 251–280.

13. De Groote H. F. On the complexity of quaternion multiplication // Information Processing Letters. — 1975. — Vol. 3, no. 6. — P. 177–179.

14. De Groote H. F. On varieties of optimal algorithms for the computation of bilinear mappings I. the isotropy group of a bilinear mapping // Theor. Comput. Sci. — 1978. — Vol. 7, no. 1. — P. 1–24.

15. Howell T. D. Global properties of tensor rank // Linear Algebra and its Applications. — 1978. — Vol. 22. — P. 9–23.

16. Howell T. D, Lafon J.-C. The complexity of the quaternion product // Cornell University Tech. Rep. — 1975.

17. Knapp A. W. Basic algebra. — Springer, 2006.

18. Landsberg J. M. New lower bounds for the rank of matrix multiplication // Preprint, ArXiv:1206.1530. — 2012.

19. Lang S. Algebra. — Springer, 2002.

20. Marker D., Messmer M., Pillay A. Model theory of fields. — Springer, 1996.

21. Pierce R. S. The Associative Algebras. — Springer, 1982.

22. Raz R. On the Complexity of Matrix Product // SIAM J. Comput. — 2003. — Vol. 32, no. 5. — P. 1356–1369.

23. Robinson A. On the metamathematics of algebra. — North-Holland, 1951.

24. Schnhage A. Partial and total matrix multiplication // SIAM J.

Comput. — 1981. — Vol. 10, no. 3. — P. 434–455.

25. Sipser M. The history and status of the P versus NP question // Proceedings of the XXIV annual ACM symposium on Theory of computing. — 1992. — P. 603–618.

26. Stothers A. J. On the complexity of matrix multiplication : Ph. D.

thesis / A. J. Stothers ; University of Edinburgh. — 2010.

27. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. — 1969. — Vol. 13, no. 4. — P. 354–356.

28. Strassen V. Rank and optimal computation of generic tensors // Linear algebra and its applications. — 1983. — Vol. 52. — P. 645–685.

29. Strassen V. Relative bilinear complexity and matrix multiplication. // Journal f r die reine und angewandte Mathematik. — 1987. — Vol.

375. — P. 406–443.

30. Trakhtenbrot B. A. A survey of Russian approaches to perebor (brute­ force searches) algorithms // Annals of the History of Computing. — 1984. — Vol. 6, no. 4. — P. 384–400.

31. Vassilevska Williams V. Multiplying matrices faster than Coppersmith-Winograd // Proceedings of the 44th symposium on Theory of Computing / ACM. — 2012. — P. 887–898.

32. Алексеев В. Б. Сложность умножения матриц. Обзор // Кибер­ нетич. сборн. — 1988. — № 25. — С. 189–236.

33. Ван дер Варден Б.Л. Алгебра. — М.: Наукa, 1976.

34. Винберг Э. Б. Курс алгебры. — М.: Пиксел, 2011.

35. Дрозд Ю.А., Кириченко В.В. Конечномерные алгебры. — Киев:

Вища школа, 1980.

36. Жданович Д. В. Экспонента сложности матричного умножения // Фундаментальная и прикладная математика. — 2012. — Т. 17, № 2. — С. 107–166.

37. Лысиков В. В. О билинейных алгоритмах умножения обобщенных кватернионов // Материалы XI международного семинара «Дис­ кретная математика и ее приложения», посвященного 80-летию со дня рождения О. Б. Лупанова / М.: МГУ. — 2012. — С. 141–143.

38. Лысиков В. В. Об алгебрах почти минимального ранга // Дис­ кретная математика. — 2012. — Т. 24, № 4. — С. 3–18.

39. Лысиков В. В. Сложность умножения матриц над полями раз­ личной характеристики // Международная конференция «Маль­ цевские чтения», 12-16 ноября 2012 г. Тезисы докладов / Новоси­ бирск: Институт математики им. С. Л. Соболева, Новосибирский государственный университет. — 2012. — С. 41.

40. Лысиков В. В. О билинейных алгоритмах над полями различных характеристик // Вестник Московского Университета. Серия 15: Вычислительная математика и механика. — 2013. — Т. 4. — С. 33–38.

41. Лысиков В. В. О целочисленных билинейных отображениях // Материалы Международного молодежного научного форума «Ло­ моносов-2013» [Электронный ресурс] / М.: МАКС Пресс. — 2013.