Рост коразмерностей метабелевых алгебр

3. Салова Т.В. Одновременная достижимость центральных показателей четырехмерных гамильтоновых систем при бесконечно малых гамильтоновых возмущениях // Дифференц. уравнения. 2014. 50, № 11. 1441-1454.

4. Сергеев И.Н. К теории показателей Ляпунова линейных систем дифференциальных уравнений // Тр. семинара им. И. Г. Петровского. 1983. Вып. 9. 111-166.

5. Фам Фу. О достижимости центральных показателей линейной гамильтоновой системы. I // Дифференц. уравнения. 1980. 16, № И. 2012-2022.

6. Сергеев И.Н. Точные границы подвижности показателей Ляпунова линейных гамильтоновых систем при малых в среднем возмущениях // Тр. семинара им. И. Г. Петровского. 1989. Вып. 14. 125-139.

7. Хьюзмоллер Д. Расслоенные пространства. М.: Мир, 1970.

8. Хауедорф Ф. Теория множеств. М.: Едиториал УРСС, 2004.

Поступила в редакцию 03.03.2017

УДК 512.572

РОСТ КОРАЗМЕРНОСТЕЙ МЕТАБЕЛЕВЫХ АЛГЕБР

М. В. Зайцев1

В статье рассматриваются числовые характеристики тождеств неассоциативных алгебр. Установлено, что последовательность коразмерностей тождеств любой конечно-порожденной метабелевой алгебры имеет экспоненциально ограниченный рост. Показано, что верхняя PI-экспонента алгебры возрастает не более чем на 1 после присоединения внешней единицы. Для двуступенно-левонильпотентных алгебр доказано, что нижняя PI-экспонента возрастает не менее чем на 1.

Ключевые слова: тождества, коразмерности, метабелевы алгебры, PI-экспонента.

We consider numerical invariants of identities of nonassociative algebras. We prove that codimension sequence of any finitely generated metabelian algebra has exponentially bounded codimension growth. It is shown that the upper Pi-exponent increases at most to 1 after adjoining an external unit. For two-step left-nilpotent algebras it is proved that the lower Pi-exponent increases at least to 1.

Key words: identities, codimensions, metabelian algebras, Pi-exponent.

В работе изучаются числовые характеристики, связанные с тождествами различных алгебр. Пусть F — поле нулевой характристики. С каждой алгеброй А над F ассоциирована целочисленная последовательность {сп(А)},п = 1,2,..., характеризующая количество ее тождественных соотношений. Анализ асимптотического поведения последоватеьности {сп(А)} играет важную роль в количественной теории полилинейных тождеств. Все необходимые сведения по теории тождеств и о числовых характеристиках последних можно найти в публикациях [1-3].

Пусть F{X} — абсолютно свободная алгебра над полем F со счетным множеством порождающих X. Совокупность всех тождеств алгебры А образует идеал Id (Л) в F{X}, инвариантный относительно всех эндоморфизмов F{X}. Обозначим через Рп подпространство всех полилинейных многочленов от х\,..., хп в F{X}. Тогда РгаПМ(А) состоит из всех полилинейных тождеств степени п алгебры А. Положим

РЛА) = ТГТЩаГ

Величину сп(А) называют п-й коразмерностью тождеств алгебры А, а последовательность {сп{А)} — последовательностью коразмерностей А. В общем случае величина сп(А) может быть ограничена лишь размерностью самого пространства Рп, т.е.

сп(А)^ dim Рп = ^-\п\,

1 Зайцев Михаил Владимирович — доктор физ.-мат. наук, проф. каф. высшей алгебры мех.-мат. ф-та МГУ. e-mail: zaicevmvQmail .ru.

где

С{п) = ±С£±2

— число Каталана, равное количеству расстановок скобок на n-буквенном слове. Если А — ассоциативная алгебра, то сп(А) ^ п!, а в случае алгебр Ли сп(А) ^ (п — 1)!. Тем не менее во многих частных случаях последовательность коразмерностей можно ограничить экспоненциальной функцией. Например, если А — ассоциативная PI-алгебра, то сп(А) ^ ап для некоторой константы а (см. [4, 5]). Если А — произвольная конечномерная алгебра, dim А = d, то Сп{А) ^ dn+1 [6, 7]. Подобная оценка справедлива также и для бесконечномерных простых алгебр Ли картановского типа [8], алгебр Кана Мулл [9] и многих других. В настоящей работе мы доказываем, что рост последовательности {сп(А)} не более чем экспоненциален для любой метабелевой алгебры с конечным числом порождающих (теорема 1). Заметим, что сп(А) = п — 1 для любой ненильпотентной метабелевой алгебры Ли. Кроме того, если алгебра Ли трехступенно-разрешима и конечно-порождена, то рост последовательности ее коразмерностей ограничен экспоненциальной функцией [9].

В случае экспоненциально ограниченного роста последовательности {сп(А)} существуют верхний и нижний пределы

Шр(А) = lim sup \/сп(А), ехр(А) = lim inf л/cJÄ),

га—)• оо го—юо

называемые верхней и нижней PI-экспонентами алгебры А соответственно, и можно определить (обычную) Р1-экспоненту

ехр(А) = lim ^сп(А),

га—>оо

если ехр (А) = ехр(А). Долгое время вопрос о существовании PI-экспоненты оставался открытым. Однако сравнительно недавно было показано, что для любого вещественного а > 1 существует алгебра Ra, у которой exp(_Ra) = 1, exp(_Ra) = а [10]. При этом в Ra выполняется тождество

x

Из тождества (2) очевидно следует тождество

(xy)(zt) = О,

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

Одним из открытых вопросов в количественной PI-теории является вопрос об изменении характера роста последовательности коразмерностей после присоединения к алгебре внешней единицы. Для заданной алгебры А будем обозначать через А* алгебру, полученную из А присоединением внешней единицы. В работе [11] показано, что для любой ассоциативной PI-алгебры А либо ехр(А#) = ехр(А), либо ехр(А#) = ехр(А) + 1. В статье автора [12] был поставлен вопрос: верно ли, что ехр(А^) существует всегда, когда существует ехр(А), и что ехр(А^) равна ехр(А) или ехр(А)+1? Для ряда случаев эта гипотеза подтвердилась, причем в [13, 14] были построены бесконечные серии примеров, подтверждающих эту гипотезу в классе алгебр с тождеством (2). В работе [15] отмечено, что ехр(А^) = ехр(А) для любой алгебры с единицей. Очевидно, что ехр(А^) ^ ехр(А), ёхр(А^) ^ ехр (А). Одним из результатов настоящей работы является доказательство неравенства

Шр(А#) ^ ёхр(А) + 1,

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

ехр (А*) ^ ехр (А) + 1

(теорема 3). Отсюда, в частности, следует, что если ехр(А) существует, то и ехр(А^) существует и равна ехр(А) + 1 для любой алгебры с тождеством (2), что является обобщением основного результата работы [14] и теоремы 2 работы [13].

Для получения верхней оценки на рост коразмерностей нам понадобятся следующие кострук-ции. Через Sn мы будем обозначать симметрическую группу. Известно, что все неизоморфные неприводимые представления Sn находятся во взаимно однозначном соответствии с разбиениями Л числа п (см. [16]). Характер такого представления мы будем обозначать через ха5 а его размерность — через deg%A- Любой конечномерный i*1^-модуль М можно разложить на неприводимые компоненты. Тот факт, что в разложении М модуль с характером ха встречается т\ раз, удобно записывать в виде

Х(М) = ^шаХА. Ahn

При ЭТОМ

dim M = ^mA deg ха •

Ah п

Пространства Рп и Рп(А) ^Sn~M.op^4-лями с естественным действием подстановок ^^ по-

рождающих xi,..., хп. Обозначим

Xn

Ahn

Высотой разбиения Л = (Ai,...,Afc) назовем величину h(А) = к. Нам понадобится следующее утверждение.

Лемма 1. Пусть А — метабелева t-порожденная алгебра. Тогда т\ = 0 в (4) для любого разбиения А с h(А) ^ t + 2. Если же А = (Ai,..., At+i), то At+i = 1.

Доказательство. Пусть А = (Ai,..., А к) — разбиение п с высотой h{ А) = к ^ t + 2. Рассмотрим неприводимый ^б^-подмодуль М в Рп(А) с характером хх- Из строения квазиидемпотентов етх групповой алгебры FSn, соответствующих таблицам Юнга Т\, следует, что М порождается полилинейным многочленом / = f(x\,... ,хп), кососиммеричным по одному из наборов порождающих {хгг,..., Хгк}. Выберем в А базис, состоящий из t порождающих а... ,at, которые можно считать линейно независимыми по модулю А2, и некоторых элементов Ъ\, &2, • • • из А2. Если подставить хотя бы два элемента bj,bm вместо {х^,... ,Xik} в /, то мы получим нуль, поскольку (А2)2 = 0. Если же подставить в / не более одного bi, то как минимум два порождающих из {х... ,Xik} придется заменить на один и тот же элемент a,j. И в этом случае / принимает нулевое значение в силу кососимметричности. Следовательно, М С И(Д). Аналогичные рассуждения показывают, что при At+i > 1 в / есть два кососимметричных набора порождающих мощности t + 1 и опять невозможно получить ненулевое значение / при какой-либо подстановке. Лемма полностью доказана. Теорема 1. Пусть А — метабелева алгебра с t порождающими. Тогда

cn(A)^(4(t + l)2r

для всех достаточно больших п.

Доказательство. Заметим сначала, что если зафиксировать расстановку скобок на одночлене степени п и рассмотреть в свободной алгебре F{X} подмодуль Рп С Рц порожденный всеми ПОЛИЛИ™ нейными одночленами с этой расстановкой скобок, то Рп — FSn как левый ^¿^-модуль. Поскольку кратности неприводимых компонент в регулярном представлении Sn равны их размерностям, то

шА ^ С{п) degXA

в формуле (4), где С(п) — п-е число Каталана (1). По лемме 1 высота h(А) не превосходит t + 1. Более того, At+i ^ 1. Если h(А) ^ t, то из формулы крюков для размерностей неприводимых представлений Sn следует неравенство

deg Ха < (n + t)Hn.

При At+i = 1 можно рассмотреть разбиение ц, (п — 1), равное (Ai,... ,\t). Тогда

deg хх ^п deg Xß <

Поэтому при достаточно больших п мы получаем

ША < 4n{t + 1)п,

так как любой биномиальный коэффициент С^ меньше 2т.

Заметим, что число разбиений Л Ь п с высотой Л-(Л) ^ ¿ + 1 и с условием А^-ц ^ 1 не превосходит пг+1. Следовательно, положив М = Рп(А) в (3) с учетом (5) и (6), мы получаем

сп(А) = тЛ ск^Хл < + 1)2га

для всех достаточно больших п, и теорема доказана.

Отметим, что если метабелева алгебра не порождается конечным числом элементов, то рост коразмерностей может быть сверхэкспоненциальным. Например, в алгебре А с базисом ао, а\,... ,Ь\, &2, • • • и таблицей умножения

аА+1 = ец+1, г = 0,1,... (остальные произведения — нулевые), левонормированные одночлены

ха(1)   -Х(т(п)1 & €

линейно независимы по модулю идеала тождеств алгебры А. В частности, сп(А) ^ п\. При этом алгеба А удовлетворяет тождеству левой нильпотентности ступени три х(уг) = 0, а значит, и тождеству метабелевости.

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

Теорема 2. Пусть А — алгебра, с экспоненциально ограниченным ростом коразмерностей. Если пол,учена из А присоединением внешней единицы, то рост последовательности коразмерностей {Сп{А^)} также экспоненциально ограничен, причем

Шр(А#) ^ ёхр(А) + 1.

Доказательство. Напомним, что Р<п — подпространство полилинеиных многочленов от -у \...., хп в свободной алгебре Р{Х}. Выберем в Рп произвольный базис, например, из одночленов, ..., /лг, где N = сЦтРга = С(п)  п\ (см. (1)). Пусть I = {г\,... — произвольное подмножество в {1,..., п} и ,] = {1,..., п} \ I = ..., .]п-к}, причем < ... < ]п-к- Для произвольного / € Рп обозначим через = ... ,х^п_к) многочлен в ... полученный из / "вычер-

киванием" переменных х^,..., Хгк.

Нетрудно заметить, что / = 0 — тождество алгебры А& тогда и только тогда, когда в А выполняется система тождеств

/7 = 0, У/с{1,...,п}.

Рассмотрим одно из подмножеств I С {1,... ,п} и положим .] = ,...,]п-к} = {1, - - -,та} \ Обозначим = Ск{А) и зафиксируем в ..., х^п_к) базис д\,..., дап к по модулю Ы(А).

Если / = Л1/1 + ... + Алг/лг) Л1,..., Ад? - некоторый многочлен из Рп, то

I1 = »191 + • • • + ^ап_к9ап_к + 9,

где д = д(х^,..., х^п_к) € М(А), а скаляры ¡л^ являются линейными комбинациями А1,..., Адг- Это означает, что тождество = 0 при фиксированном I задает ап-к линейных уравнений ¡л\ = ... =

Vап-к = 0 на м-

Оценим общее количество уравнений в системе (7). Пусть ехр(А) = с!. Тогда для любого вещественного е > 0 можно найти такое натуральное £ = ¿(е), что ап-к ^ (б, + е)п~к для всех п — к ^ т.е. к ^ п — Тогда число М уравнений в системе (7) будет удовлетворять условию

М = ^2Спап-к = ^ Скап_к + ^ С^а-п-к-

к п—кп—к<1

Обозначим первую сумму в правой части (8) через £1, а вторую через £2- Тогда

п—Ь п

£1 < I] + е)п~к < ^ Ск1к{<1 + е)п~к = {! + <! + е)п-к=0 0

С другой стороны, сумма Е2 с ростом п ограничена полиномом степени t от п. Следовательно,

М <

для всех достаточно больших п. Поскольку ранг системы (7) не превосходит М, размерность пространства Рп П Id(.A) ограничена снизу величиной N — М, и сп(А^ (1 + d + 2е)п при больших п, как следует из (8), (9). В силу произвольного выбора е > 0 мы получаем ограничение ёзф(А#) ^ ёхр(А) + 1, и теорема доказана.

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

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

ехр{А*) ^ ехр(А) + 1,

где Ä& получена из А присоединением внешней единицы.

Доказательство. Пусть I = {¿i,..., С {1,... ,п}, J = {1,... ,п}\1 = {ji,... ,jn-k}- Как и в

теореме 2, обозначим at = ct(A) и выберем базис   , /Fäfc_fc подпространства Pn-k{xj1,..., Xjn_k) по модулю Id(yl). Положим

С" = 97f

Лемма 2. Система полином,ов g™~k из (10), 0 ^ k ^ п,1 ^ j ^ an-k,I С {1,... ,п}, линейно независима по модулю идеала Id(A^).

Доказательство. Предположим, что некоторая линейная комбинация g элементов (10) является тождеством алгебры А*. Подставляя вместо всех xs всевозможные значения из А, мы видим, что все коэффициенты при gß ..., g^ а равны нулю, поскольку x(yz) = 0 — тождество А. Теперь, подставляя единицу вместо одной из переменных и элементы из А вместо остальных, мы видим, что коэффициенты при всех gj j равны нулю, где J — произвольное одноэлементное множество. Продолжая этот процесс, мы доказываем, что все коэффициенты в разложении полинома g равны нулю, и лемма доказана.

Чтобы завершить доказательство теоремы 3, заметим, что при фиксированном подмножестве I С {1,... ,п} число полиномов g™~k равно ап-к• Поэтому

п

Cn

к=О

Обозначим d = ехр(А). Тогда для любого вещественного е > 0 коразмерности алгебры А удовлетворяют неравенству ^ (d — е)к для всех к начиная с некоторого номера ко = ко (б). В силу (11) мы имеем

п п п fco—1

сп

fc=0 fc=0 fc=fc0 fc=о

Вторая сумма в правой части (12) растет не быстрее полинома степени ко с ростом п. Поэтому

п

Сп(А*) > - 2е)к = (! + d - 2еТ-

к=О

В силу произвольного выбора е > 0 мы получаем нужную оценку ехр(А^) ^ ехр(А) + 1, и теорема доказана.

Следствие 1. Пусть А — двуступенно-левонильпотентная алгебра с экспоненциально ограниченным рост,ом, коразмерностей. Если Р1-экспон,ен,т,а, А существует, то существует и, PI-экспонента алгебры Ä^, полученной из А присоединением внешней единицы. Более того,

ехр

Замечание 1. Теорема 3 верна и для двуступенно-правонильпотентных алгебр. Доказательство для них повторяется дословно, поэтому следствие 1 верно и для правонильпотентных алгебр.

Замечание 2. В основной теореме из работы [14] и в теореме 2 из [13] соотношение (13) доказано для серии левонильпотентных ступени 2 алгебр. Поэтому следствие 1 является обобщением упомянутых результатов. При этом оно получено более простым способом. Работа поддержана Российским научным фондом, грант № 16-11-10013.

СПИСОК ЛИТЕРАТУРЫ

1. Giambruno A., Zaicev М. Polynomial identities and asymptotic methods // Math. Surv. and Monogr. Vol. 122. Amer. Math. Soc. Providence, RI, 2005.

2. Бахтурин Ю.А. Тождества в алгебрах Ли. М.: Наука, 1985.

3. Drensky V. Free algebras and Pi-algebras. Graduate course in algebra. Singapore: Springer-Verlag Singapore, 2000.

4. Regev A. Existence of identities in A <g> В // Isr. J. Math. 1972. 11. 131-152.

5. Латышев B.H. К теореме Регева о тождествах тензорного произведения PI-алгебр // Успехи матем. наук. 1972. 27, № 4. 213-214.

6. Bakhturin Yu.V., Drensky V. Graded polynomial identities of matrices // Linear Algebra and Its Appl. 2002. 357. 15-34.

7. Giambruno A., Zaicev M. Codimension growth of special simple Jordan algebras // Trans. Amer. Math. Soc. 2010. 362, N 6. 3107-3123.

8. Мищенко С.П. Рост многообразий алгебр Ли // Успехи матем. наук. 1990. 45. 25-45.

9. Зайцев М.В. Многообразия аффинных алгебр Каца-Мудп // Матем. заметки. 1997. 62, вып. 1. 95-102.

10. Zaicev М. On existence of Pi-exponents of codimension growth // Electronic Research Announcements in Mathematical Sciences. 2014. 21. 113-119.

11. Giambruno A., Zaicev M. Proper identities, Lie identities and exponential codimension growth //J. Algebra. 2008. 320, N 5. 1933-1962.

12. Зайцев М.В. Тождества конечномерных унитарных алгебр // Алгебра и логика. 2011. 50, № 5. 563-594.

13. Зайцев М.В., Реповш Д. Экспоненциальный рост коразмерностей тождеств алгебр с единицей // Матем. сб. 2015. 206, № 10. 103-126.

14. Dusan R., Zaicev М. Numerical invariants of identities of unital algebras // Communs Algebra. 2015. 43, N 9. 3823-3839.

15. Везущак O.E., Беляев А.А., Зайцев М.В. Экспоненты тождеств алгебр с присоединенной единицей // Вшник Кшвск. нац. ун-ту iM. Т. Шевченка. Сер. ф1зико-математичш науки. 2012. Bin. 3. 7-9.

16. Джеймс Г. Теория представлений симметрических групп. М.: Наука, 1982.

Поступила в редакцию 15.03.2017

УДК 511

БЫСТРЫЙ АЛГОРИТМ ГЕОМЕТРИЧЕСКОГО КОДИРОВАНИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

Г. В. Носовский1, А. Ю. Чекунов2, С. А. Подлипаев3

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

1 Носове кий Глеб Владимирович — канд. физ.-мат. наук, доцент каф. дифференциальной геометрии и приложений мех.-мат. ф-та МГУ, e-mail: gleb.nosovskiyQgmail.com.

2 Чекунов Алексей Юрьевич — асп. каф. дифференциальной геометрии и приложений мех.-мат. ф-та МГУ, e-mail: alexey. chekunovQmail .ru.

3Подлипаев Сергей Алексеевич — студ. каф. дифференциальной геометрии и приложений мех.-мат. ф-та МГУ, e-mail: podlipaev.sergeyQgmail.com.