Содержание к диссертации
Введение
Глава 1. Основные понятия 13
1.1. Билинейные отображения и алгебры 13
1.2. Ассоциативные алгебры над полем 19
1.3. Модель вычислений 22
1.4. Тензорные произведения и расширение кольца скаляров 29
Глава 2. Алгоритмы умножения обобщенных кватерни онов 34
2.1. Алгебры обобщенных кватернионов 34
2.2. Билинейные отображения малого ранга 36
2.3. Сложность умножения обобщенных кватернионов . 41
2.4. Ранг произведения алгебр обобщенных кватернионов . 42
Глава 3. Полупростые алгебры почти минимального ранга 47
3.1. Следствия известных оценок 47
3.2. Сложность умножения в алгебрах матриц 52
Глава 4. Целочисленные билинейные отображения над. полями различных характеристик 59
4.1. Ненулевые тензорные произведения 59
4.2. Связь между билинейными алгоритмами 61
4.3. Метаматематическое доказательство 65
Литература
- Ассоциативные алгебры над полем
- Билинейные отображения малого ранга
- Сложность умножения в алгебрах матриц
- Связь между билинейными алгоритмами
Введение к работе
Актуальность темы. Одним из направлений в теории сложности вычислений является алгебраическая теория сложности. Естественно, что алгоритмы, вычисляющие функции, связанные с какой-либо алгебраической структурой на входных данных, например, алгоритмы умножения матриц или вычисления каких-либо полиномов, часто излагаются в терминах этой алгебраической структуры, независимо от того, как конкретно представляются входные данные. В связи с этим сложность вычисления таких функций удобно рассматривать в так называемых алгебраических моделях вычислений, в которых операции рассматриваемой алгебраической структуры считаются элементарными, несмотря на то, что на реальном компьютере они могут представляться не одной командой.
Одной из важных проблем алгебраической теории сложности является задача определения сложности умножения матриц1'2. В 1969 г. был опубликован алгоритм Ф. Штрассена3 для умножения квадратных матриц размера п х п, имеющий сложность 0(п1^7) арифметических операций вместо 0{rv') для тривиального алгоритма, что положило начало исследованиям асимптотически быстрых алгоритмов умножения матриц. После нескольких лет исследований в этой области Д. Копперсмитом и Ш. Виноградом4 был получен алгоритм с асимптотической сложностью 0(п2'376). Недавние исследования с использованием компьютерных средств5'6'7 позволили улучшить эту оценку до 0(п2-373).
Штрассен также заметил связь алгоритмов умножения матриц с алгебра-
1 Алексеев В. Б. Сложность умножения матриц. Обзор // Кибернетич. сборн. — 1988. — № 25. —
С. 189-236.
2 Burgisser P., Clausen М., Shokrollahi М.А. Algebraic Complexity Theory— Springer, 1997.
3 Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. — 1969. — Vol. 13, no. 4. —
P. 354-356.
4 Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // Journal of symbolic
computation. - 1990. - Vol. 9, no. 3. - P. 251-280.
5 Stothers A. J. On the complexity of matrix multiplication : Ph. D. thesis / A. J. Stothers ; University of
Edinburgh. - 2010.
6 Vassilevska Williams V. Multiplying matrices faster than Coppersmith-Winograd // Proceedings of the
44th symposium on Theory of Computing / ACM. — 2012. — P. 887-898.
7 Жданович Д. В. Экспонента сложности матричного умножения // Фундаментальная и прикладная
математика. - 2012. - Т. 17, № 2. - С. 107-166.
ическим понятием тензорного ранга, что позволило применять для изучения сложности этих алгоритмов конструкции мультилинейной алгебры. Эти конструкции и связанная с ними техника могут быть применены не только к алгоритмам умножения матриц, но и к вычислению отображений из более широкого класса — билинейных отображений над полем или кольцом. Модель вычислений, связанная с этим подходом к сложности умножения матриц и вычисления билинейных отображений, называется моделью билинейных алгоритмов.
Определение. Пусть S — кольцо, U^V^W — конечномерные свободные модули над S и (р: U xV —> W — билинейное отображение. Билинейным алгоритмом для if называется последовательность (/i, Z\\ f2-, 92-, %2) ) fr-,9r, %r), где fs Є U*, gs EV*, zs Є W, такая, что для любых х Є U, у Є V выполняется
Ф,У) = ^2fs(x)gs(y)zs.
s=l
Количество троек г называется сложностью билинейного алгоритма. Билинейной сложностью или рангом отображения ср называется минимально возможная сложность билинейного алгоритма для этого отображения. Ранг отображения ср обозначается R(p).
Важным классом билинейных отображений является класс ассоциативных алгебр, то есть билинейных отображений вида А х А —> Л, обладающих свойством ассоциативности. Этот класс отображений удобен тем, что, с одной стороны, включает в себя умножение квадратных матриц, таким образом результаты о сложности умножения в ассоциативных алгебрах могут использоваться при анализе матричного умножения и наоборот, а с другой стороны, позволяет использовать классические результаты о структуре алгебр. Например, базовая конструкция в алгоритме Копперсмита-Винограда4 умножения матриц может быть интерпретирована как приближенный алгоритм для умножения в алгебре определенного вида. В связи с этим интересен вопрос о структуре алгебр с малой сложностью умножения.
В 1981 г. А. Алдером и Ф. Штрассеном8 была получена нижняя оценка
8 Alder A., Strassen V. On the Algorithmic Complexity of Associative Algebras // Theor. Comput. Sci. — 1981. - Vol. 15. - P. 201-211.
сложности умножения в алгебрах в терминах их структуры.
Теорема (А. Алдер, Ф. Штрассен). Пусть F — поле, А — конечномерная ассоциативная алгебра с единицей над F. Для ранга алгебры А справедлива оценка
R(A) ^2 dim A -t(A),
где t(A) — количество максимальных двусторонних идеалов алгебры А.
Эта оценка оказалась неулучшаемой, в связи с чем возник вопрос об описании всех алгебр, на которых она достигается — алгебр минимального ранга. Эта задача решалась несколько десятков лет многими исследователями, окончательное описание было получено М. Блезером9. Одним из ключевых элементов этого описания являются улучшенные нижние оценки сложности умножения в алгебрах матриц10'11.
Теорема (М. Блезер). Пусть D — алгебра с делением, п ^ 2, A = Dnxn — простая алгебра. Тогда
5 R(A) ^ -dimA-Sn.
Теорема (М. Блезер). Для ранга алгебры матриц размера 3x3 над произ-вльным полем F справедлива оценка
i?(F3x3) ^ 19
После этого М. Блезером и А. М. де Вольтером12 было начато изучение алгебр почти минимального ранга, т. е. алгебр, для которых билинейная сложность на 1 больше оценки Алдера-Штрассена. Ими было получено, в частности, описание полупростых алгебр почти минимального ранга над полем действительных чисел.
9 Blaser М. A Complete Characterization of the Algebras of Minimal Bilinear Complexity // SIAM J.
Comput. - 2004. - Vol. 34, no. 2. - P. 277-298.
10 Blaser M. Beyond the Alder-Strassen bound // Theor. Comput. Sci. — 2005.— Vol. 331, no. 1.—
P. 3-21.
11 Blaser M. On the complexity of the multiplication of matrices of small formats // J. Complexity. —
2003. - Vol. 19, no. 1. - P. 43-60.
12 Blaser 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.
Теорема (М. Блезер, А. М. де Вольтер). Любая полупростая алгебра почти минимального ранга над Ж. имеет вид
А ^ Ш х R2x2 х х R2x2 хСх---хСхМх---хМ.
В данной диссертации обобщается результат Блезера и де Вольтера о полупростых алгебрах почти минимального ранга на случай произвольного основного поля, характеристика которого отлична от 2.
Блезером и де Вольтером были отмечены несколько ключевых проблем на пути к этому обобщению. Одним из ключевых вопросов на пути к описанию алгебр почти минимального ранга является вопрос о билинейной сложности умножения обобщенных кватернионов. Оптимальный алгоритм умножения кватернионов над полем действительных чисел был получен в 70х годах13'14'15, однако он не обобщается непосредственным образом на алгебры обобщенных кватернионов над произвольным полем. В диссертации получен критерий почти минимальности для класса локальных алгебр, позволяющий получить оптимальный алгоритм в общем случае.
Для рассмотрения другого проблемного случая необходимо улучшить упомянутую выше нижнюю оценку М. Блезера для сложности умножения в простых алгебрах. Несмотря на то, что методы, использованные М. Лэндсбергом16 позволяют получить оценку, более сильную асимптотически (порядка Зп2), они неприменимы для алгебр малой размерности. В данной работе оценка Блезера улучшается на единицу для матричных алгебр над расширениями основного поля.
Другим вопросом, рассматриваемым в диссертации, является исследование связи между алгоритмами вычисления билинейного отображения с целыми коэффициентами (например, умножения матриц или полиномов) над
13 De Groote Н. F. On the complexity of quaternion multiplication // Information Processing Letters. —
1975. - Vol. 3, no. 6. - P. 177-179.
14 Howell T. D, Lafon J.-C. The complexity of the quaternion product // Cornell University Tech. Rep. —
1975.
15 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.
16 Landsberg J. M. New lower bounds for the rank of matrix multiplication // Preprint, ArXiv:1206.1530. —
2012.
полями различных характеристик. Т. Д. Хауэлл первым отметил, что билинейная сложность отображения не возрастает при расширении кольца, над которым рассматриваются алгоритмы, а также доказал, что в некоторых условиях такое расширение не влияет на сложность, в частности, что минимальная сложность достигается при использовании в качестве основного кольца алгебраически замкнутого поля. А. Шёнхаге18 рассматривал сложность матричного умножения над различными полями одной характеристики. Он доказал, что асимптотика сложности матричного умножения над полями одной характеристики одинакова с точностью до постоянного множителя. Штрассен19 показал, что этот множитель не превосходит 4 при выполнении гипотезы Штрассена о прямой сумме.
В данной работе рассматривается связь рангов билинейного отображения с целочисленными коэффициентами над полями различных характеристик. Насколько известно автору, этот вопрос ранее не рассматривался.
Цель работы: описание структуры различных классов алгебр почти минимального ранга; исследование билинейной сложности Z-билинейных отображений над различными полями.
Методы исследования. В диссертации используются методы алгебраической теории сложности, линейной алгебры, теории колец и теории моделей.
Научная новизна. Результаты диссертации являются новыми.
Основные результаты:
1. Описана структура оптимальных алгоритмов для класса билинейных отображений, ранг которых равен сумме размерностей аргументов.
17 Howell Т. D. Global properties of tensor rank // Linear Algebra and its Applications.— 1978.—
Vol. 22. - P. 9-23.
18 Schonhage A. Partial and total matrix multiplication // SIAM J. Comput. — 1981. — Vol. 10, no. 3. —
P. 434-455.
19 Strassen V. Relative bilinear complexity and matrix multiplication. // Journal fur die reine und
angewandte Mathematik. - 1987. - Vol. 375. - P. 406-443.
-
Получен критерий почти минимальности ранга для локальных алгебр.
-
Описана конструкция билинейных алгоритмов ранга 8 для умножения в алгебрах обобщенных кватернионов над полем характеристики, отличной от 2.
-
Доказана нижняя оценка сложности умножения в матричных алгебрах над расширением основного поля, улучшающая известную оценку Блезера.
-
Полностью описана структура полу простых алгебр почти минимального ранга над бесконечным полем характеристики, отличной от 2.
-
Установлено, что значения ранга Z-билинейного отображения над алгебраически замкнутыми полями различных характеристик совпадают, за исключением конечного числа простых характеристик.
Теоретическая и практическая значимость. Диссертация носит теоретический характер. Полученные результаты могут быть применены для анализа других задач теории сложности билинейных отображений. Приведенный в диссертации алгоритм умножения обобщенных кватернионов может быть использован для построения более сложных алгоритмов.
Публикации. По теме диссертации опубликовано 5 работ, среди них 2 работы [2, 4] в рецензируемых изданиях, включенных в перечень ВАК.
Апробация результатов. Результаты диссертации докладывались на следующих семинарах и конференциях:
— на семинаре «Дискретные функции и сложность алгоритмов» под руководством В. Б. Алексеева, С. С. Марченкова и А. А. Вороненко (кафедра математической кибернетики ВМК МГУ) в 2011-13 гг.;
на XI международном семинаре «Дискретная математика и ее приложения» (Москва, 18-23 июня 2012);
на международной конференции «Мальцевские чтения» (Новосибирск, 12-16 ноября 2012);
на семинаре «Дискретная математика и математическая кибернетика» под руководством В. Б. Алексеева, А. А. Сапоженко и С. А. Ложкина (кафедра математической кибернетики ВМК МГУ) в 2012-13 гг.;
на международном молодежном научном форуме «Ломоносов-2013»;
Структура и объем диссертации. Работа состоит из введения, четырех глав и списка литературы, содержащего 41 наименование. Диссертация содержит 73 страницы и включает 1 таблицу.
Ассоциативные алгебры над полем
В главах 2 и 3 мы будем рассматривать сложность умножения в конечномерных ассоциативных алгебрах с единицей над полем. Тео рия таких алгебр является классическим разделом алгебры, результаты которого изложены во многих монографиях и учебных пособиях, напр. [21, 33, 35]. В этом разделе приведены основные определения и результаты этой теории, которыми мы будем пользоваться.
Термин «алгебра» будет обозначать конечномерную ассоциативную алгебру с единицей над некоторым полем . Поле можно рассматривать как подмножество алгебры , если отождествить скаляры с элементами
Определение 1.9. Подмодуль алгебры называется левым идеалом, если он замкнут относительно умножения на любой элемент алгебры слева, т. е. для любых произведение x принадлежит . Аналогично опредляются правые идеалы. Подмодуль, являющийся одновременно левым и правым идеалом, называется двуcторонним идеалом или просто идеалом. Левый (правый, двусторонний) идеал называется максимальным, если он не содержится ни в каком левом (правом, двустороннем) идеале, кроме всей алгебры
Определение 1.10. Идеал называется нильпотентным, если для некоторого натурального произведение элементов идеала равно 0.
Алгебра называется полупростой, если она не имеет нильпо-тентных идеалов кроме тривиального идеала 0. Алгебра называется простой, если она не имеет идеалов кроме 0 и всей алгебры. Алгебра называется локальной, если она имеет единственный максимальный левый идеал. Алгебра называется алгеброй с делением, если любой ее ненулевой элемент обратим.
Определение 1.11. Квадратные матрицы размера с элементами из алгебры с обычным образом определенным умножением образуют алгебру, которая обозначается и называется алгеброй матриц над.
Прямым произведением алгебр и называется алгебра , состоящая из пар вида с покоординатным умножением.
Теорема 1.1 (Дж. Веддербёрн, Э. Артин). Алгебра полупроста тогда и только тогда, когда она изоморфна прямому произведению конечного числа простых алгебр. Алгебра проста тогда и только тогда, когда она изоморфна алгебре матриц над некоторой алгеброй c делением. алгебра с делением, то для любого элемента множество элементов, представимых в виде линейной ком- бинации степеней , является расширением основного поля , которое называется расширением, порожденным элементом . Расширение, порожденное каким-либо своим элементом, называется простым.
Мы будем рассматривать сложность вычисления билинейных отображений конечномерных свободных модулей. В этом случае элементы модулей можно представлять в виде наборов координат в некотором фиксированном базисе, и можно рассматривать алгоритмы, которые по наборам координат аргументов вычисляют значение билинейного отображения. Элементарными операциями в таком алгоритме естественно считать операции над элементами кольца, над которым рассматривается отображение.
В процессе исследования задачи о сложности умножения матриц был выделен класс алгоритмов, обладающих определенной структурой: вначале над каждым из аргументов производятся линейные операции (умножение на константы и сложение), затем полученные таким образом промежуточные результаты перемножаются, и затем с помощью только линейных операций из произведений получаются координаты результата. Мерой сложности алгоритма при этом считается количество умножений на втором этапе, линейные операции считаются «бесплатными». Дадим формальное определение.
Билинейные отображения малого ранга
Для классификации алгебр почти минимального ранга нам потребуется рассмотреть сложность умножения в алгебрах обобщенных кватернионов. Это некоммутативные ассоциативные алгебры, обобщающие на случай произвольного основного поля F конструкцию алгебры кватернионов, открытую У. Р. Гамильтоном в XIX в.
Определение 2.1. Центром алгебры А называется подалгебра, состоящая из элементов, коммутирующих с любым элементом алгебры:
С (А) = {х\ха = ах Va є А]. Алгебра над F называется центральной, если ее центр совпадает с F.
Определение 2.2. Алгеброй обобщенных кватернионов над F называется простая центральная алгебра размерности 4.
Структура алгебр обобщенных кватернионов определяется следующими утверждениями:
Теорема 2.1 (см. [8]). Если charF = 2, то любая алгебра обобщенных кватернионов порождается двумя элементами і и j, удовлетворяющими условиям і = р, j = q, ij = —ji, где p,q Є F, p,q = 0. Элементы 1, і, j, k = ij образуют базис алгебры. Такую алгебру будем обозначать ( — ) . p,q
Теорема 2.2 (см. [8]). Если charF = 2, то любая алгебра обобщенных кватернионов порождается двумя элементами і и j, удовлетворяющими условиям і (і + 1) = р, j = q, ij=j(i + 1), где p, q Є F, q = 0. Элементы 1, і, j, k = ij образуют базис алгебры.
Теорема 2.3 (см. [8]). Любая алгебра обобщенных кватернионов либо изоморфна алгебре матриц F2x2, либо является некоммутативной алгеброй с делением. Любая некоммутативная алгебра с делением размерности 4 является алгеброй обобщенных кватернионов. 2.2. Билинейные отображения малого ранга
Прежде чем обратиться к сложности умножения кватернионов, мы докажем некоторые общие утверждения о билинейных алгоритмах, ранг которых равен сумме размерностей пространств аргументов.
Определение 2.3. Пусть F — поле, U,V,W — векторные пространт-сва над F, и ср: U х V — W — билинейное отоборажение. Назовем элемент щ Є U (левым) ср-регулярным, если линейный оператор ср(щ, ) инъективен, т.е. ср(щ,у) = 0 тогда и только тогда, когда v = 0.
Определение 2.4. Билинейный алгоритм (/i, д\, z\\...; /r, gr, zr) будем называть двухкомпонентным, если множество индексов {1,.. .,г} можно разбить на непересекающиеся множества I и J такие, что {fi\i Є /} и {gj\j Є J} являются базисами пространств U и V соответственно.
Лемма 2.1. Пусть F — поле, U,V,W — векторные пространт-сва над F, u ср: U х V — W — билинейное отоборажение. Если R( p) = dim U + dim V, lker ер = 0, ив любом базисе пространства U найдется р -регулярный элемент, то любой оптимальный билинейный алгоритм для ср является двухкомпонентным.
Доказательство. Пусть dim U = m, dim V = п. Рассмотрим опти мальный билинейный алгоритм (/i, gi, z\\...; /m+n, 9т+п, zm+n) для (/9. Так как lker (/9 = 0, функционалы /і,..., /то+п порождают все пространство [У . Пусть, без ограничения общности, /і,..., fm — базис U , а элемент щ двойственного базиса щ,..., ит является ср-регулярным. Из ( -регулярности щ следует, что функционалы gi,gm+i,... ,gTO+n порождают все пространство У , так как иначе существует ненулевой элемент v такой, что gi(v) = gm+i{v) = = gm+n{v) = 0, и из определения билинейного алгоритма следует, что (p(ui,v) = 0.
Обозначим через G линейную оболочку множества функционалов {gm__i,..., дт-\-п}. Если G есть все пространство V , то множества индексов / = {1,...,т} и J = {m+1,... т+п} образуют разбиение, требуемое в определении двухкомпонентного алгоритма. В противном случае dim G = п — 1 и существует единственная с точностью до умножения на константу линейная зависимость между #m+i,..., дт+п. Пусть, без ограничения общности, #m+i,..., gm+s входят в уравнение линейной зависимости с ненулевыми коэффициентами, а остальные функционалы — с нулевыми.
Сложность умножения в алгебрах матриц
Случай п = 2, dim D = 2 рассмотрен в [7] для поля F = К. и также не является алгеброй почти минимального ранга. Доказательство не использует специфики поля К. и может быть дословно переписано для любого поля характеристики, отличной от 2. Теорема 3.4 (М. Блезер, А. М. де Вольтер). Если К — алгебраическое расширение поля F, dim К = 2, то R(K2x2) 17.
Оставшиеся два случая (п = 2, dim D = 3 и п = 3, dim D = 2) мы рассмотрим далее. Для доказательства того, что эти алгебры не являются алгебрами почти минимального ранга, мы улучшим оценку теоремы 3.2 в случае, когда алгебра D является расширением поля F.
Сложность умножения в алгебрах матриц Лемма 3.3. Пусть P(xi,... ,хп) — ненулевой многочлен степени к над бесконечным полем F. Тогда существует набор скі,... , ап, в котором не более к ненулевых значений, на котором этот многочлен не равен 0. Если Р существенно зависит от переменной ХІ, то одним из ненулевых значений можно взять СЇІ.
Доказательство. Если многочлен Р не равен тождественно 0, то существует моном, входящий в него с ненулевым коэффициентом. В случае, если Р существенно зависит от ХІ, то существует моном с нену левым коэффициентом, содержащий Х{. Так как степень многочлена равна к, этот моном содержит не более к переменных.
Подставим нули вместо всех переменных, кроме тех, которые входят в этот моном. Получим многочлен Р (х;л , . . . , Xjt), t к. Он содержит рассматриваемый моном, а потому не равен тождественно нулю, т.е. найдутся значения о ,... , о , при подстановке которых полином имеет ненулевое значение. Если при этом рассматривае мый моном содержит переменную ХІ, то Р можно записать в виде У1=о Pj (%)%l, где Р А не зависят от ХІ и не все Р" при j 1 тожде ственно равны нулю. Подставив вместо всех переменных, кроме ХІ, значения так, что хотя бы один из Р" при j 1 не обращается в 0, получим, что Р существенно зависит от ХІ и можно подставить нену левое значение вместо ХІ так, что получившееся значение многочлена Р будет ненулевым. П Лемма 3.4. Пусть К — расширение бесконечного поля F, dim К = d, г: К —F — ненулевой линейный функционал, a U\,... un"2(i некоторый базис F-алгебры Кпхп. Многочлен существенно зависит от всех переменных, кроме тех, которые соответствуют скалярным матрицам = , , если такие элементы содержатся в рассматриваемом базисе. Доказательство. Пусть 1 = . Докажем, что многочлен существенно зависит от 1. Зависимость от остальных переменных доказывается аналогично. Так как 1 — нескалярная матрица, найдется вектор 1 такой, что 1 1 = 2 не пропорционален 1. Дополним пару 1, 2 до -базиса пространства и будем рассматривать матрицы из как операторы в этом базисе. В этом базисе 1 имеет вид где на местах, отмеченных звездочками, могут стоять произвольные ТУ v sr n2d значения из К. Выберем Х{ так, что X = І І=\ хіиі в том же базисе имеет вид diag(Ai, Л2,... , Лп), где все Aj различны. При этом оператор adX: У14 [X, Y] переводит матрицу Y = (у ) в матрицу [X, Y] = ((Aj — Xj)yij). Возьмем /І Є К такой, что r(fi) =0и выберем матрицу что означает, что переменная 1 является существенной.
Лемма 3.5. Пусть К — расширение бесконечного поля F, аП 2. Из любого базиса F-алгебры Кпхп можно выбрать не более Зп — 1 элементов, в линейной оболочке которых найдутся 3 элемента &1,&2,йз такие, что ai и \а\ a2-,(h &з] обратимы. Доказательство. Пусть щ,... ,un2d — рассматриваемый базис. Если в нем есть обратимая матрица щ, то возьмем а\ = щ. Иначе пусть г: К —F — некоторый ненулевой линейный функционал и /І Є К таков, что r(ji) 7 0. Рассмотрим вначале многочлен P(x) = r(det Х Г=і xiui). Он ненулевой, так как существует матрица с определителем /І, и является однородным многочленом степени п (легко проверить, что Р(Хх) = ХпР(х)). По лемме 3.3 можно выбрать значения Хі, на которых Р не равен 0, и среди которых s п ненулевых, то есть в линейной оболочке s элементов базиса найдется невырожденная матрица а\. Далее, рассмотрим базис, составленный из элементов и\ = aj" щ и многочлен n2d n2d Q(x,y) = r(det[ Xiu y Уіи і\)і исследованный в предыдущей лемме. Это однородный многочлен степени 2п. Снова применяя лемму 3.3, получаем, что найдется q 2п элементов нового базиса, содержащих матрицы а 2 = aj" (i i и аз = а\ аз такие, что [ 22 аз] обратима, причем один из элементов базиса может быть задан заранее, если он не является скалярной матрицей. Тогда в линейной оболочке соответствующих элементов исходного базиса содержатся матрицы Й2 и ИЗ.
Связь между билинейными алгоритмами
Доказательство. Рассмотрим оптимальный алгоритм над Q для Z билинейного отображения ср. Так как в алгоритме участвует толь Лч) (Q) (Q) П конечное число коэффициентов j , g- , zk , то подполе г, порожденное этими коэффициентами, будет конечным алгебраическим расширением Q, для которого Rp((p) = Rq(cp). Применяя лемму 4.6 для кольца Ор целых элементов F, получим, что RF( P) = RoF(k(p) для некоторого к. Из доказательства леммы видно, что можно взять к Є Z, так как любое алгебраическое число представляется в виде —, где п — целое алгебраическое и т Є Z.
Кольцо О , рассматриваемое как модуль над Z, является свободным модулем, поэтому тензорное произведение Op 8 z Ip не является нулевым. По лемме 2 получаем RoF(kcp) i?f (&V?) = Rf ( ), если А; = 0. Равенство А; = 0 в Fp выполняется для не более чем конечного числа характеристик р (а именно, для простых делителей к), поэтому неравенство Rq(tp) Rf (ф) выполнено для всех р, кроме, быть может, конечного числа.
Для перехода от билинейных алгоритмов для Z-билинейного отображения tp над полями простой характеристики к алгоритмам над полем характеристики 0 рассмотрим последовательность полей р. Пусть г — минимально возможное число, встречающееся в последовательности Rf (ср) бесконечное число раз. Рассмотрим бесконечное прямое произведение S = II р. p-Rtp(v )=r Любой кратный 1 элемент этого кольца не равен 0, так как он не равен 0 в компонентах произведения, соответствующих достаточно большим р. Как следствие, S zQ. не является нулевым кольцом (по лемме 4.4). Таким образом г = Rs( ) Rq(1 ) по лемме 4.7. Из выбора числа г следует, что неравенство Rf (ср) г может выполняться только для конечного числа простых р. Таким образом, мы получили соотношения R((p) й и Rf ((/?) Rq( p) для всех р, кроме, может быть, конечного числа. Объединяя эти два неравенства, получаем утверждение теоремы.
Метаматематическое доказательство Интересно, что теорему 4.1 можно доказать также методами математической логики, не прибегая к чисто алгебраическим конструкциям. Для этого можно использовать полноту теорий ACFC алгебраически замкнутых полей характеристики с. В дополнение к обычным аксиомам поля в ACFC используется схема аксиом алгебраической замкнутости: для всех натуральных п 1
Теорема 4.2 (А. Робинсон, см. [23]). Для любой характеристики с теория ACFC полна. Из этой теоремы следуют утверждения о связи выводимости формул первого порядка в теориях ACFC.
Утверждение 4.1. Если F — алгебраически замкнутое поле характеристики с, то любая формула Ф общезначима в F тогда и только тогда, когда она выводима в ACFC.
Утверждение 4.2 (см. [20]). Формула Ф выводима в теории ACFQ тогда и только тогда, когда она выводима в ACFp для всех простых р, кроме, может быть, конечного числа.
Приведем теперь второе доказательство теоремы 4.1. Доказательство. Заметим, что для Z-билинейного отображения ip утверждение R((f) г можно записать в виде замкнутой формулы логики предикатов в сигнатуре теории колец (=, +, -,0,1). Действительно, пусть ср задается в некоторой тройке базисов коффициентами tijk в соответствии с (1.1). Исходя из координатного представления билинейного алгоритма (1.3), утверждение R((f) г выполняется тогда и только тогда, когда истинна формула
Так как t k целые, то их можно записать в виде суммы единиц и при необходимости перенести в правую часть, чтобы избавиться от знака «минус». Полученная формула является замкнутой формулой теории колец, и утверждение Rs{(fi) т верно тогда и только тогда, когда эта формула истинна в кольце S. Как следствие, в виде формулы теории колец можно записать и утверждение Rsi p) = т.
Похожие диссертации на Некоторые вопросы теории сложности билинейных отображений
