close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Известия вузов. Математика
2010, № 3, c. 15–22
http://www.ksu.ru/journals/izv_vuz/
Гос. номер статьи по НТЦ "Информрегистр" 0421000123 \0020
А.В. ЛЕОНТЬЕВ
НИЖНИЕ ОЦЕНКИ АЛГЕБРАИЧЕСКИХ АЛГОРИТМОВ
ДЛЯ НИЛЬПОТЕНТНЫХ И РАЗРЕШИМЫХ АЛГЕБР ЛИ
Аннотация. Получены нижние оценки тензорного ранга для класса нильпотентных и разрешимых алгебр Ли (в терминах размерностей некоторых фактор-алгебр), которые в свою
очередь дают нижние оценки сложности алгебраических алгоритмов для этого класса алгебр.
В случае нильпотентных алгебр Ли приведены примеры достижимости полученных оценок
для алгебр различных размерностей.
Ключевые слова: нильпотентные алгебры Ли, разрешимые алгебры Ли, точные алгебраические алгоритмы, алгебраическая сложность, тензорный ранг, нижние оценки.
УДК: 512.55
Abstract. We obtain the lower bounds for the tensor rank for the class of nilpotent and solvable Lie
algebras (in terms of dimensions of certain quotient algebras). These estimates, in turn, give lower
bounds for the complexity of algebraic algorithms for this class of algebras. We adduce examples
of attainable estimates for nilpotent Lie algebras of various dimensions.
Keywords: nilpotent Lie algebras, solvable Lie algebras, exact algebraic algorithms, algebraic
complexity, tensor rank, lower bounds.
1. Введение
В данной работе изучаются нижние оценки для точных алгебраических алгоритмов. Ранее рассматривались нижние оценки для класса ассоциативных (в частности, матричных)
алгебр (см., например, обзорно-обобщающую работу [1]). Оценки для простых алгебр Ли
приведены в [2]–[4].
В статье получены нижние оценки для тензорного ранга нильпотентных и разрешимых
алгебр Ли над полями нулевой характеристики, которые в свою очередь дают нижние оценки сложности алгебраических алгоритмов (в данном случае — алгоритмов, вычисляющих
умножение в алгебре) для этого класса алгебр. Об алгебраической сложности и ее связи с
тензорным рангом (тензорный ранг не превосходит сложность) можно прочитать, например, в [5] или другой подобной литературе. В случае нильпотентных алгебр Ли приведены
примеры достижимости полученных оценок. Автор благодарит В.Н. Латышева за полезные
обсуждения и внимание к работе.
Поступила 28.11.2007
15
16
А.В. ЛЕОНТЬЕВ
2. Нижние оценки для нильпотентных алгебр Ли
Определение 1. Тензорный ранг алгебры — это наименьшее число r для которого существуют такие линейные функционалы ui (x1 , . . . , xn , y1 , . . . , yn ), vi (x1 , . . . , xn , y1 , . . . , yn ) и
элементы алгебры wi , что для любых элементов x = x1 e1 + · · · + xn en и y = y1 e1 + · · · + yn en
выполняется равенство
r
ui (x1 , . . . , xn , y1 , . . . , yn )vi (x1 , . . . , xn , y1 , . . . , yn )wi ,
[x, y] =
i=1
где e1 , . . . , en — некоторый базис алгебры, как линейного пространства над полем F.
Тензорный ранг алгебры L будем обозначать rk⊗ (L), центр алгебры — Z(L), основное
поле (характеристики нуль) — F. Тензор умножения произвольной алгебры L будем записывать в виде
r
ui (a, b)vi (a, b)wi ,
(1)
[a, b] =
i=1
где r — минимальное из возможных (здесь r = rk⊗ (L)); ui (a, b), vi (a, b) — линейные функционалы на L × L; a, b, wi ∈ L.
Рассмотрим произвольную нильпотентную алгебру Ли L над полем F характеристики
нуль.
Замечание 1. Можно считать, что Z(L) ⊆ L2 , поскольку элементы центра, не принадлежащие L2 , не влияют на тензорный ранг алгебры L.
Отметим, что обычная схема доказательств для получения подобного рода оценок —
это синтаксическое приравнивание к нулю коэффициентов тензора умножения, решение
этих уравнений и получение противоречия из полученного решения (в предположении, что
тензор мал, т. е. число уравнений мало). Синтаксический выбор переменных для обнуления
коэффициентов тензора, по большей части, сходен с выбором в работе [1].
Лемма 1. Пусть d = dim(L2 /Z(L)). Тогда перенумерацией слагаемых в (1) и, возможно, перестановкой ui с vi можно добиться, что функционалы {u1 , . . . , ud } будут линейно
независимы на множестве (L2 \ Z(L)) × 0.
Доказательство. Допустим противное. Существуют такое 0 = x ∈ (L2 \ Z(L)) и такое
натуральное p (1 ≤ p < dim(L2 /Z(L))), что (после перенумерации) выполнены следующие
три условия (последующие условия являются следствиями из первого):
1) функционалы {u1 , . . . , up } линейно независимы (максимально линейно независимая
система функционалов) на множестве (L2 \ Z(L)) × 0;
2) для элемента x выполнены равенства
u1 (x, 0) = . . . = up (x, 0) = 0,
(2)
up+1 (x, 0) = . . . = ur (x, 0) = 0,
(3)
vp+1 (x, 0) = . . . = vr (x, 0) = 0;
(4)
3) для любого элемента b ∈ L найдется такой элемент s(b) ∈ L2 , что выполнены равенства
(5)
ui (0, b) = −ui (s(b), 0), где 1 ≤ i ≤ p
(т. е. ui (s(b), b) = 0, 1 ≤ i ≤ p).
НИЖНИЕ ОЦЕНКИ АЛГЕБРАИЧЕСКИХ АЛГОРИТМОВ
17
Далее, для элемента x, удовлетворяющего уравнениям (2)–(4), выберем такой элемент
b ∈ L, что [x, b] = 0. Для элемента b согласно (5) выберем s(b) ∈ L2 . Имеем
[x + s(b), b] − [s(b), b] = [x, b] = 0.
(6)
С другой стороны, для этих элементов согласно (1)
[x + s(b), b] − [s(b), b] = [x, b] =
=
r
r
ui (x + s(b), b)vi (x + s(b), b)wi − [s(b), b] =
i=1
(ui (x, 0) + ui (s(b), b)) (vi (x, 0) + vi (s(b), b)) wi − [s(b), b] =
i=1
r
=
(ui (x, 0)vi (x, 0) + ui (x, 0)vi (s(b), b) + ui (s(b), b)vi (x, 0)+
i=1
+ ui (s(b), b)vi (s(b), b))wi −
=
r
r
ui (s(b), b)vi (s(b), b)wi =
i=1
(ui (x, 0)vi (x, 0) + ui (x, 0)vi (s(b), b) + ui (s(b), b)vi (x, 0)) wi .
i=1
Обозначая коэффициенты
(ui (x, 0)vi (x, 0) + ui (x, 0)vi (s(b), b) + ui (s(b), b)vi (x, 0))
при wi через γi , получаем
[xb] =
p
γi wi +
i=1
r
γi wi .
i=p+1
Заметим, что первая (по (2), (5)) и вторая (по (3), (4)) суммы равны нулю. Следовательно,
[x, b] = 0, что противоречит (6).
Следствие. Для нильпотентных алгебр Ли
r = rk⊗ (L) ≥ dim(L2 /Z(L)).
Лемма 2. Пусть d = dim(L2 /Z(L)). Перенумерацией слагаемых в (1) и, возможно, перестановкой ui с vi можно добиться, что элементы {u1 , . . . , u2d } будут линейно независимы
на множестве (L2 \ Z(L)) × (L2 \ Z(L)).
Доказательство. Будем считать, что выражение (1) удовлетворяет условиям леммы 1, т. е.
функционалы {u1 , . . . , ud } линейно независимы на множестве (L2 \ Z(L)) × 0.
Допустим противное. Существуют такое натуральное p, где dim(L2 /Z(L)) ≤ p < 2d =
2 dim(L2 /Z(L)), и такая пара 0 = x, y ∈ (L2 \ Z(L)) × (L2 \ Z(L)), что (после перенумерации) выполнены следующие три условия (последующие условия являются следствиями
из первого):
1) функционалы {u1 , . . . , up } линейно независимы (максимально линейно независимая
система функционалов) на (L2 \ Z(L)) × (L2 \ Z(L));
18
А.В. ЛЕОНТЬЕВ
2) для пары x, y выполнены равенства
u1 (x, y) = . . . = up (x, y) = 0,
(7)
up+1 (x, y) = . . . = ur (x, y) = 0,
(8)
vp+1 (x, y) = . . . = vr (x, y) = 0;
(9)
3) для любых элементов a, b ∈ L найдутся такие элементы s(a, b), t(a, b) ∈ L2 , что выполнены равенства
ui (a, b) = −ui (s(a, b), t(a, b)), где 1 ≤ i ≤ p
(10)
(т. е. ui (a + s(a, b), b + t(a, b)) = 0, 1 ≤ i ≤ p).
Замечание 2. Нетрудно видеть, что y = 0, иначе 0 = x и уравнения (7) выполнены не
будут.
Выберем пары x, y и a+s(a, b), b+t(a, b), удовлетворяющие уравнениям (7)–(10). Тогда
согласно (1) имеем
z = [x + a + s(a, b), y + b + t(a, b)] − [a + s(a, b), b + t(a, b)] =
=
r
ui (x + a + s(a, b), y + b + t(a, b))vi (x + a + s(a, b), y + b + t(a, b))wi −
i=1
− [a + s(a, b), b + t(a, b)] =
r
{(ui (a + s(a, b), b + t(a, b)) + ui (x, y))×
i=1
× (vi (a + s(a, b), b + t(a, b)) + vi (x, y))}wi − [a + s(a, b), b + t(a, b)] =
=
r
{ui (x, y)vi (a + s(a, b), b + t(a, b))+
i=1
+ ui (a + s(a, b), b + t(a, b))vi (x, y) + ui (x, y)vi (x, y)}wi .
Обозначая коэффициенты при wi через γi , получаем
p
r
γi wi +
γi wi .
z=
i=1
i=p+1
Заметим, что первая (по (7), (10)) и вторая (по (8), (9)) суммы равны нулю. Следовательно,
z = [x+a+s(a, b), y+b+t(a, s)]−[a+s(a, b), b+t(a, b)] = [a+s(a, b), y]+[x, b+t(a, b)]+[x, y] = 0.
Замечание 3. Нетрудно видеть, что в силу линейности функционалов u и v если пара x, y
— решение равенств (7)–(9), то и пара αx, αy для любого α ∈ F также будет решением
этих равенств.
Аналогично, если пара a + s(a, b), b + t(a, b) — решение равенств (10), то и пара βa +
βs(a, b), βb+βt(a, b) для любого β ∈ F также будет решением этих равенств. Следовательно,
для любых α, β ∈ F выполнено
zα,β = [βa + βs(a, b), αy] + [αx, βb + βt(a, b)] + [αx, αy] =
= αβ([a + s(a, b), y] + [x, b + t(a, b)]) + α2 [x, y] = 0.
Отсюда
[a + s(a, b), y] + [x, b + t(a, b)] = 0.
(11)
НИЖНИЕ ОЦЕНКИ АЛГЕБРАИЧЕСКИХ АЛГОРИТМОВ
19
Пусть m — наименьшее натуральное число такое, что либо [L, y] Lm+1 , либо [L, x] Lm+1 . Без ограничения общности можно считать, что это условие выполняется для элемента
y (для элемента x рассуждение симметричное), т. е.
([L, y], [L, x] ⊆ Lm )&([L, y] Lm+1 ).
Тогда, полагая в равенстве (11) b = 0 и выбирая элемент a ∈ L таким, чтобы [a, y] ∈
/ Lm+1 ,
получаем
[ay] = −[s(a, 0), y] − [x, t(a, 0)].
(12)
Поскольку s(a, 0), t(a, 0) ∈ L2 и [L, x], [L, y] ⊆ Lm , то элементы [s(a, 0), y], [x, t(a, 0)] ∈ Lm+1 .
Следовательно, равенство (12) не может выполняться. Полученное противоречие доказывает лемму.
Из леммы 2 получаем
Следствие. Для нильпотентных алгебр Ли справедлива следующая оценка:
r = rk⊗ (L) ≥ 2 dim(L2 /Z(L)).
Лемма 3. Пусть d = dim(L2 /Z(L)), I — прообраз в L центра Z(L/L3 ) алгебры L/L3 ,
M = (L2 \ Z(L)) ∪ (L \ I), e = dim(L/I). Перенумерацией слагаемых в (1) и, возможно,
перестановкой ui с vi можно добиться, что элементы {u1 , . . . , u2d+e } будут линейно независимы на множестве (L2 \ Z(L)) × M .
Доказательство. Будем считать, что выражение (1) удовлетворяет условиям леммы 2, т. е.
функционалы {u1 , . . . , u2d } линейно независимы на множестве (L2 \ Z(L)) × (L2 \ Z(L)).
Допустим противное. Существуют такое p, что 2 dim(L2 /Z(L)) ≤ p < 2 dim(L2 /Z(L)) +
/ I, что (после переdim(L/I), и такая пара 0 = x, y ∈ (L2 \ Z(L)) × M , причем y ∈
нумерации) выполнены три условия, аналогичные условиям леммы 2 (и, следовательно,
уравнения (7)–(10), с той лишь разницей, что y, t(a, b) ∈ L и y ∈
/ I). Далее, пусть пара x, y
удовлетворяет этим условиям. Тогда для элемента z имеем
z = [x + a + s(a, b), y + b + t(a, b)] − [a + s(a, b), b + t(a, b)] = 0
и с учетом замечания 3 заключаем
[a + s(a, b), y] + [x, b + t(a, b)] = 0.
(13)
L3 .
Для элементов a и b выберем элементы
Положим b = 0 и выберем a такой, что [a, y] ∈
/
2
s(a, b) ∈ L и t(a, b) ∈ L, удовлетворяющие уравнениям (10). Так как [s(a, b), y], [x, b +
t(a, b)] ∈ L3 , равенство (13) выполняться не может.
Из леммы 3 вытекает
Теорема 1. Пусть I — прообраз в нильпотентной алгебре L центра Z(L/L3 ) алгебры
L/L3 . Тогда для алгебры Ли L справедлива следующая оценка:
r = rk⊗ (L) ≥ 2 dim(L2 /Z(L)) + dim(L/I)
или, без учета замечания 1,
r = rk⊗ (L) ≥ 2 dim(L2 /(Z(L) ∩ L2 )) + dim(L/I).
(14)
20
А.В. ЛЕОНТЬЕВ
Теорема 2. Пусть L — алгебра верхнетреугольных нильпотентных матриц (порядка
n × n с нулями на главной диагонали). Тогда
r = rk⊗ (L) ≥ 2 dim(L2 /Z(L)) + dim(L/L2 ).
Доказательство. Достаточно заметить, что для алгебры верхнетреугольных нильпотент
ных матриц Z(L/L3 ) = L2 , и применить теорему 1.
Замечание 4. Для трехмерной нильпотентной верхнетреугольной (с нулями под и на главной диагонали) матричной алгебры Ли L порядка 3 × 3 оценка (14) точна. Действительно,
rk⊗ L = 2. Согласно оценке (14) rk⊗ L ≥ 2.
Отметим, что для любого натурального 2n существует алгебра Ли L∗ , у которой тензорный ранг равен 2n и для которой оценка (14) точна — достаточно в качестве L∗ взять
прямое произведение алгебры L n раз.
Поскольку dim(L∗ /I) = 2n, заключаем, что коэффициент при слагаемом dim(L/I) (т. е.
единица) в (14) повышен быть не может.
Замечание 5. Рассмотрим алгебру Ли нильпотентных верхнетреугльных матриц порядка
4 × 4. Определим в ней подалгебру L условием (для матрицы X) x1,2 = x3,4 . Для ненулевых
элементов коммутатора Z = [X, Y ] имеем
z1,3 = x1,2 y2,3 − x2,3 y1,2 ,
z1,4 = x1,2 (y2,4 − y1,3 ) + y1,2 (x1,3 − x2,4 ),
z2,4 = x2,3 y1,2 − x1,2 y2,3 .
Следовательно, тензорный ранг алгебры L не превосходит 6. С другой стороны, равенства
Z(L) = L3 , I = L2 , dim(L2 /Z(L)) = 2 и dim(L/I) = 2 говорят о том, что оценка (14) для
алгебры L точна.
Отметим, что для любого натурального 6n существует алгебра Ли L∗ , у которой тензорный ранг равен 6n и для которой оценка (14) точна — достаточно в качестве L∗ взять
прямое произведение алгебры L n раз.
Учитывая предыдущее замечание, заключаем, что коэффициент при слагаемом
dim(L2 /Z(L)) (т. е. двойка) в (14) повышен быть не может.
3. Нижние оценки для разрешимых алгебр Ли
Рассмотрим произвольную разрешимую алгебру Ли K над полем F характеристики нуль.
Теорема 3. Пусть K — разрешимая алгебра, N(K) — ее нильрадикал, IN — прообраз в
N(K) центра Z(N(K)/(N(K))3 ). Тогда справедливы следующие оценки:
rk⊗ (K) ≥ rk⊗ N(K),
rk⊗ (N(K)) ≥ 2 dim(N(K)2 /(Z(N(K)) ∩ N(K)2 )) + dim(N(K)/IN ).
Доказательство. Поскольку N(L) является нильпотентной подалгеброй, то утверждение
является следствием теоремы 1.
НИЖНИЕ ОЦЕНКИ АЛГЕБРАИЧЕСКИХ АЛГОРИТМОВ
21
Для разрешимых алгебр может быть доказан аналог леммы 2. Пусть K разрешима ступени n (K (n+1) = 0, K (n) = 0),
Ji = {k ∈ K (i) | [k, K] K 2i }.
Положим
Mi = (K (i) \ Ji ) × (K (i) \ Ji ),
Ij =
j
Mi .
i=n
Теорема 4. Пусть K — разрешимая алгебра ступени n. Тогда
rk⊗ (K) ≥ 2
2
dim(K (i) /Ji ),
i=n
где Ji и Ii определены выше.
Лемма 4. Для алгебры K справедлива оценка
rk⊗ (K) ≥ 2 dim(K (n) /Jn ).
Доказательство. Пусть d = dim(K (n) /Jn ). Допустим противное, тогда (после перенумерации функционалов) существуют такое натуральное p (где p < 2d = 2 dim(K (n) /Jn )) и такая
пара 0 = x, y ∈ (K (n) \ Jn ) × (K (n) \ Jn ), что (после перенумерации) выполнены следующие три условия аналогичные условиям леммы 2 (и, следовательно, уравнения (7)–(10), с
той лишь разницей, что a, b ∈ K и s(a, b), t(a, b) ∈ K (n) ).
Далее, для элемента z имеем
z = [x+a+s(a, b), y+b+t(a, s)]−[a+s(a, b), b+t(a, b)] = [a+s(a, b), y]+[x, b+t(a, b)]+[x, y] = 0
и
[a + s(a, b), y] + [x, b + t(a, b)] = 0.
(15)
По условию либо x = 0, либо y = 0. Пусть, например, x = 0 (для y = 0 аналогично).
Выберем такой b, что 0 = [x, b] ∈
/ K (n+1) , и положим a = 0. Из (15) получаем
0 = [xb] = −[s(0, b), y] − [x, t(0, b)] = 0
(16)
так как [s(0, b), y], [x, t(0, b)] ∈ K (n+1) = 0. Полученное противоречие (16) и доказывает
лемму.
Проводя аналогичные рассуждения для множеств In−1 , . . . , I0 , получаем доказательство
теоремы 4.
Теорема 5. Пусть T — разрешимая (не нильпотентная) алгебра Ли верхнетреугольных
матриц (порядка n × n с нулями под главной диагональю). Тогда
r = rk⊗ (T ) ≥ 2 dim(T 2 ).
Доказательство. Достаточно заметить, что [T, T (i) ] = T (i) , и применить теорему 3.
22
А.В. ЛЕОНТЬЕВ
Литература
[1] Alder A., Strassen V. On the algorithmic complexity of the associative algebras // Theor. Comp. Sci. – 1981.
– V. 15. – № 2. – P. 201–211.
[2] Жошина С.А. О мультипликативной сложности алгебр Ли // Вестн. Моск. Ун-та. Сер. 1, Математика.
Механика. – 1990. – № 4. – C. 75–77.
[3] Жошина С.А. О мультипликативной сложности простых алгебр Ли G2 , F4 , E6 , E7 , E8 и полупростых
алгебр Ли // Вестн. Моск. Ун-та. Сер. 1, Математика. Механика. – 1993. – № 4. – C. 35–37.
[4] Леонтьев А.В. Нижние оценки алгебраической сложности для классических простых алгебр Ли //
Матем. сб. – 2008. – T. 199. – № 5. – C. 27-34.
[5] Латышев В.Н. Комбинаторная теория колец. Сложность алгебраических алгоритмов. – М.: Изд-во
Моск. ун-та, 1987. – 105 c.
А.В. Леонтьев
преподаватель, университет города Переславля,
152020, Ярославская обл., г. Переславль-Залесский, ул. Советская, д. 2,
e-mail: alex@leont.botik.ru
A.V. Leont’ev
Lecturer, University of Pereslavl,
2 Sovetskaya str., Pereslavl-Zalessky, Yaroslavl region, 152020 Russia,
e-mail: alex@leont.botik.ru
Документ
Категория
Без категории
Просмотров
4
Размер файла
153 Кб
Теги
оценки, алгоритм, алгебра, разрешимых, нильпотентных, нижний, алгебраический
1/--страниц
Пожаловаться на содержимое документа