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

Уадилова Айгуль Дюсенбековна

ПЕРЕЧИСЛЕНИЕ ТЕРНАРНЫХ АЛГЕБР

И ДЕРЕВЬЕВ

Специальность 01.01.06 – математическая логика, алгебра и теория чисел

Автореферат

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

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

Ульяновск – 2008

Работа выполнена на кафедре алгебро–геометрических вычислений в государственном образовательном учреждении высшего профессионального образования "Ульяновский государственный университет"

Научный руководитель: доктор физико–математических наук, профессор Петроградский Виктор Михайлович

Официальные оппоненты: доктор физико–математических наук, профессор Зайцев Михаил Владимирович кандидат физико–математических наук Рацеев Сергей Михайлович

Ведущая организация: ГОУ ВПО Саратовский государственный университет имени Н. Г. Чернышевского

Защита состоится "29" октября 2008 г. в 1130 на заседании диссертационного совета Д 272.278.02 при Ульяновском государственном университете по адресу: ул. Набережная реки Свияги, 106, корп. 1, ауд. 703.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, авторефератом на сайте вуза http://www.uni.ulsu.ru Отзывы по данной работе просим направлять по адресу:

432000, г. Ульяновск, ул. Л. Толстого, д. 42, УлГУ, Управление научных исследований.

Автореферат разослан " " сентября 2008 г.

Ученый секретарь диссертационного совета М.А. Волков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Выполнение тех или иных тождеств является одним из существенных свойств алгебраических систем. Важные классы различных алгебр выделяются по признаку выполнения (или не выполнения) некоторых тождеств. Фундаментом многих исследований являются работы А. И. Ширшова1, доказавшего теорему о свободе подалгебр в свободных алгебрах Ли.

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

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

За последние десятилетия теория графов2,3 превратилась в один из наиболее бурно развивающихся разделов математики. Это связано с тем, что теория графов, родившаяся при решении головоломок и занимательных задач, стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.

Особенно важна роль теории графов в современном программировании.

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

Основным объектом исследования в данной работе являются многообразия тернарных алгебр, т. е. алгебр с трилинейной операцией. В этом Ширшов А. И. Подалгебры свободных лиевых алгебр. // Математический сборник, т. 33 (75), N 1. 1953. с. 441 – 452.

Ф. Харари, Э. Палмер. Перечисление графов: Перев. с англ. М.: Мир, 1977. 326 с.

Р. Стенли. Перечислительная комбинаторика: Перев. с англ. М.: Мир, 1990. 440 с.

Moon J. W. Counting labelled trees. Canadian Mathematical Monographs N 1, Canadian Mathematical Congress, 1970. 115 p.

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

Цель работы. Целью диссертационной работы является исследование:

1) алгебраичности производящей функции абсолютно свободной тернарной алгебры, а также функций сложности свободных симметричных и кососимметричных алгебр;

2) Шрайеровости многообразий тернарных -алгебр;

3) алгебраичности функций сложности разрешимых и вполне разрешимых алгебр в рассматриваемых многообразиях тернарных алгебр;

4) алгебраичности функций сложности многообразий вполне левонильпотентных и левонильпотентных тернарных алгебр;

5) интерпретации понятий разрешимости и левонильпотентности для тернарных алгебр в терминах запрещенных поддеревьев.

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

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

Научные положения, выносимые на защиту.

1) Алгебраичность производящей функции абсолютно свободной тернарной алгебры, а также функций сложности свободных симметричных и кососимметричных алгебр;

2) Шрайеровость многообразий тернарных -алгебр;

3) Алгебраичность функций сложности разрешимых и вполне разрешимых алгебр в рассматриваемых многообразиях тернарных алгебр;

4) Алгебраичность функций сложности многообразий вполне левонильпотентных и левонильпотентных тернарных алгебр;

5) Интерпретация понятий разрешимости и левонильпотентности для тернарных алгебр в терминах запрещенных поддеревьев.

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

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

Апробация работы. Основные результаты диссертации докладывались на XIV Международной конференции "Проблемы теоретической кибернетики" (Пенза, 2005), международной молодежной научной школе-конференции "Лобачевские чтения 2005" (Казань, 2005), на VI Международной алгебраической конференции на Украине (KamyanetsPodilsky, 2007), семинарах кафедры алгебро-геометрических вычислений УлГУ.

Личный вклад автора. В диссертации изложены результаты, полученные как лично автором, так и совместно с научным руководителем проф. В. М. Петроградским. Постановка задачи выполнена совместно с научным руководителем.

Публикации. По теме диссертации опубликовано 5 работ, список которых приведен в конце автореферата, в том числе 1 статья в журнале из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, пяти глав и списка литературы. Содержит 81 страницу машинописного текста, список литературы из 25 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Нумерация теорем и лемм в данной работе отличается от нумерации, приводимой в диссертации.

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

нарной операцией; т. е. для любых a, b, c L определен элемент d = тернарных алгебр.

Тернарную алгебру L назовем симметричной, если выполняется тождество (a1, a2, a3) = (a(1), a(2), a(3) ), где a1, a2, a3 L и S3. Класс симметричных тернарных алгебр обозначим W1.

Алгебру L с тернарной операцией назовем кососимметричной, если выполняется тождество (a1, a2, a3 ) = (1) (a(1), a(2), a(3) ), где a1, a2, a3 L и S3. Пусть W2 класс всех кососимметричных алгебр.

Тернарную алгебру L назовем циклической, если выполняется тождество (a, b, c) = (b, c, a), для всех a, b, c L. Обозначим через W3 класс таких алгебр.

Двудольная тернарная алгебра L задается тождеством перестановки крайних членов: (a, b, c) = (c, b, a), где a, b, c L. Пусть W4 класс всех таких алгебр.

Далее используем обозначение W, где {0, 1, 2, 3, 4}.

Для произвольного многообразия тернарных алгебр V через F (V, X) будем обозначать его свободную алгебру, порожденную множеством X = {x1,..., xn,... }. Если |X| = s, то получаем относительно свободную алгебру ранга s, которую будем обозначать также F (V, s).

денная счетным множеством X = {xi| i N}. Обозначим через Pn (V ) F (V, X) подпространство всех полилинейных элементов степени n на множестве {x1,..., xn} и рассмотрим размерность этого подпространства:

0, 1, 2,..., которая является важной характеристикой многообразия6,7.

an tn, где an = dimK An называется производящей функцией.

n= Рассмотрим свободную алгебру A конечного ранга, она является граAn ). Определяем ряд Гильберта–Пуанкаре дуированной (т. е. A = H(A, t) как производящую функцию:

Ю. П. Размыслов предложил также рассматривать для многообразия алгебр Ли так называемую функцию сложности8. Определим функцию сложности для многообразия V как Это пример экспоненциальной производящей функции, которая широко используется в комбинаторике9. В. Дренски начал использовать такие функции для многообразий алгебр, а именно, он вычислил их для некоторых ассоциативных многообразий6.

Мальцев А. И. Алгебраические системы. М.: Наука, 1970. 392 с.

Drensky V., Free algebras and PI-algebras. Springer, Singapore, 2000. 271 p.

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

Размыслов Ю. П. Тождества алгебр и их представлений. М.: Наука, 1989. 432 с.

Гульден Я., Джексон Д. Перечислительная комбинаторика. перев. с англ. М.: Наука, 1990. 504 с.

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

Пусть F = F (W, X) свободная алгебра многообразия тернарных -алгебр, порожденная множеством X. Определим -регулярные слова.

Слова длины 1 назовем -регулярными. Предположим, что регулярные слова длины меньше n (n > 1) уже определены и вполне упорядочены. Тогда слово длины n назовем -регулярным, если выполняются следующие условия:

1. Слово = (u, v, w) представимо как результат тернарной операции, аргументами которой выступают слова u, v, w меньшей длины;

• u max{v, w}, причем в случае равенства предполагаем Продолжим порядок произвольным образом на все -регулярные слова длины n.

Лемма 1: Все -регулярные слова образуют базис свободной тернарной -алгебры F (W, X) для всех {0, 1, 2, 3, 4}.

Будем интерпретировать элементы построенного базиса как тернарное дерево. Например, элементу = (((x1, x2, x3), x4, x5), x6, (x7, x8, x9)), где x1,..., x9 X, сопоставим следующее тернарное дерево (рис. 1):

У такого дерева зафиксирован корень, т.е. дерево является корневым.

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

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

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

В терминах тернарных деревьев функции сложности -многообразий {0, 1,..., 4} перечисляют некоторые корневые тернарные деW, ревья соответствующих пяти типов, листья которых отмечены различными элементами счетного множества X = {xi| i N}.

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

Доказано, что, если (t) производящая функция свободной тернарной -алгебры F (W, k) конечного ранга k, {0, 1, 2, 3, 4}, то она удовлетворяет уравнению В случае абсолютно свободной тернарной алгебры также дано следующее описание производящих функций.

лютно свободной тернарной алгебры F (W0, k). Тогда 2. (t) алгебраична и равна (где i2 = 1 и под корнями подразумеваем ветви 1 = 1 и 3 1 = 1).

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

Этот термин возник в связи с классической теоремой О. Шрайера о многообразия является класс свободных алгебр Ли (теорема Ширшова– Витта)1,. Имеет место также теорема о свободе подалгебр в свободных ограниченных алгебрах Ли (Витт11). Аналогичная теорема также верна для свободных цветных супералгебр Ли12. Как правило, свободные подалгебры бесконечно порождены в этом случае и формулы Шрайера нет. Однако, в терминах производящих функций Петроградским В. М.

найден аналог формулы Шрайера13. Шрайеровы многообразия играют важную роль в современной алгебре14.

Многообразие абсолютно свободных алгебр является Шрайеровым, что доказано А. Г. Курошем15. А. И. Ширшовым доказана шрайеровость многообразий коммутативных и антикоммутативных неассоциативных алгебр16. В этом случае Петроградским В. М. также найден аналог формулы Шрайера13.

Основной результат третьей главы состоит в следующем.

Теорема 2: Пусть H ненулевая подалгебра свободной тернарной В четвертой главе в рассматриваемых классах тернарных алгебр изучаются разрешимые и вполне разрешимые алгебры и многообразия.

Schreier O. Die Untergruppen der freien Gruppen. // Abh. Math. Sem. Univ. Hamburg 5. 1927.

p. 161 – 183.

Witt E. Die Unterringe der freien Lieschen Ringe.// Math. Z. 64. 1956. p. 195 – 216.

Bahturin Yu. A., Mikhalev A. A., Petrogradsky V. M., Zaicev M. V. Innite Dimensional Lie Superalgebras. Berlin; New York: de Gruyter, 1992. 250 p.

Petrogradsky V. M. Schreier‘s formula for free Lie algebras. // Arch. Math. (Basel) 75 (1). 2000.

p. 16 – 28.

Mikhalev A. A., Yu J.-T. Primitive, almost primitive, test, and -primitive elements of free algebras with the Nielsen-Schreier property. // J. Algebra 228 (2). 2000. p. 603 – 623.

Курош А. Г. Неассоциативные свободные алгебры и свободные произведения алгебр. // Математический сборник, т. 20 (62), 1947. с. 239 – 262.

Ширшов А. И. Подалгебры свободных коммутативных и свободных антикоммутативных алгебр. // Математический сборник, т. 34 (76), N 1. 1954. с. 81 – 88.

Полученные результаты эквивалентны перечислению тернарных деревьев, которые не содержат некоторых запрещенных поддеревьев.

Определим рекуррентно мономы: S0 (X1) = X1 и для q > 0 положим Sq+1(X1,..., X3q+1 ) = = Sq (X1,..., X3q ), Sq (X3q +1,..., X2·3q ), Sq (X2·3q +1,..., X3q+1 ).

Назовем -алгебру разрешимой ступени q, если она удовлетворяет тождеству Sq (X1,..., X3q ) 0. Многообразие -алгебр, разрешимых ступени q, обозначим как Aq.

Определим ряд коммутантов для тернарной -алгебры L следующим образом: L(0) = L и L(i+1) = (L(i), L(i), L(i) ) для i 1.

Лемма 2: Следующие утверждения эквивалентны:

1. алгебра L разрешима ступени q;

2. L(q) = 0;

3. существует цепочка подалгебр Заметим, что подалгебры L(i) могут и не быть идеалами для L. Возьмем некоторую подалгебру H L и обозначим через IdL(H) идеал в L, порожденный подалгеброй H.

Назовем -алгебру L вполне разрешимой ступени q, если существует цепочка (1), элементы которой являются идеалами в L. Определим ряд пополненных коммутантов: L[0] = L и для всех i 1 (i + 1)-ый пополненный коммутант L[i+1] = IdL ((L[i], L[i], L[i])).

Лемма 3: Следующие условия эквивалентны:

1. выполняется условие L[q] = 0.

2. L вполне разрешима ступени q.

Класс всех вполне разрешимых -алгебр обозначим как Sq.

Введем такое понятие как полное тернарное дерево высоты q. Будем обозначать его T q. Вместо формального определения изобразим полное тернарное дерево высоты 3 (рис. 2).

Рис. 2. Полное тернарное дерево T 3 высоты 3.

Определим редукцию тернарных деревьев следующим образом: зафиксируем вершину, отличную от листа, обрезаем две возрастающие ветви, и рисуем одну линию вместо трех исходных ветвей, что выходят из этой вершины, таким образом удаляя вершину. Например, рассмотрим тернарное дерево (рис. 3) и удалим, например, вершину µ при помощи редукции (рис. 4).

Рис. 3. Тернарное дерево (с обозначенными вершинами µ и ).

Рис. 4. Тернарное дерево с удаленной вершиной µ.

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

Теорема 3: Верны два следующих утверждения:

1. Все -регулярные мономы, деревья которых не содержат полные тернарные поддеревья T q, образуют базис свободной разрешимой -алгебры F (Aq, X) ступени q.

2. Базис вполне разрешимой -алгебры F (Sq, X) ступени q образуют -регулярные мономы, деревья которых не содержат полные тернарные поддеревья T q высоты q после произвольного числа редукций.

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

Теорема 4: Пусть Ss многообразие вполне разрешимых тернарных алгебр в классе W, = 0, 1,..., 4. Тогда функция сложности алгебраична и вычисляется так:

где функции i (z), i = 1,..., s задаются рекуррентно: 1(z) = z и для i = 1,..., s 1 функция i+1(z) удовлетворяет квадратному уравнению над полем Q[1(z),..., s (z)]:

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

Теорема 5: Пусть Aq многообразие разрешимых ступени q алгебр в W0.

1. Рассмотрим функцию сложности f (z) = C(Aq, z). Тогда функция f (z) алгебраична и удовлетворяет алгебраическому уравнению степени 2 3q2 над Q[z]:

где функции i (z) задаются рекуррентно: 1 (z) = z и для i = 2. Ряд Гильберта–Пуанкаре для относительно свободной алгебры ранга k алгебраичен и равен Аналогичные утверждения доказаны для многообразий разрешимых ступени q -алгебр, где {1, 2, 3, 4}.

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

Обозначим через l Ns многообразие тернарных -алгебр, определяемое тождеством Будем называть это многообразие левонильпотентным ступени s.

-алгебра. Определим лево-центральную последовательПусть L ность. Она состоит из следующих подалгебр Лемма 4: Следующие утверждения эквивалентны:

1. алгебра L левонильпотентна ступени s.

3. существует цепочка подалгебр Li, такая что Пусть H такая подалгебра в L, которая обладает следующим свойством: (H, u, v) H, (u, H, v) H и (u, v, H) H для произвольных u, v L. Тогда H называется идеалом L. Пусть L = IdL (H) обозначает минимальный идеал, содержащий множество H.

Замечание. В случаях = 1, 2, 3 подалгебры Li являются идеалами в L. Однако, в случаях = 0, 4 элементы лево-центральной последовательности Li могут и не быть идеалами. Но если предположить, что существует последовательность идеалов вида (3), то будем называть L вполне левонильпотентной ступени s.

Определим лево-вполнецентральную последовательность: L0 = L и Лемма 5: Вполне левонильпотентность ступени s эквивалентна условию Ls = 0.

Согласно замечанию выше, вполне левонильпотентность совпадает с левонильпотентностью в случае = 1, 2, 3. В случае W0 эти два понятия различаются и многообразие вполне левонильпотентных 0-алгебр обозначим как cl Ns.

Для всех s 0 определим дерево Qs, оно имеет s+2 листа и выглядит так.

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

Теорема 6: Верны следующие два утверждения.

1. Все -регулярные мономы, деревья которых не содержат Qs, образуют базис F (l Ns, X) свободной левонильпотентной ступени s 2. Базис F (cl Ns, X) свободной вполне левонильпотентной ступени s 0-алгебры, состоит из регулярных мономов, деревья которых не содержат Qs после произвольного числа редукций.

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

Теорема 7: Пусть V = многообразие вполне левонильпотентных тернарных алгебр ступени s в W0, где s 1. Тогда 1. функция сложности C(V, z) алгебраична, причем C(V, z) = s (z), где функции i (z), i = 1,..., s, задаются рекуррентно:

1 (z) = z и для i = 1,..., s 1 функция i+1(z) удовлетворяет следующему квадратному уравнению над 2. Ряд Гильберта–Пуанкаре относительно свободной алгебры ранга k алгебраичен и равен Теорема 8: Пусть V = l Ns многообразие левонильпотентных тернарных алгебр ступени s в W0. Тогда 1. функция сложности f (z) = C(V, z) алгебраична и удовлетворяет уравнению 2. Ряд Гильберта–Пуанкаре относительно свободной алгебры ранга k алгебраичен и равен Также доказано, что ряды Гильберта–Пуанкаре многообразий левонильпотентных тернарных алгебр ступени s в W, где {1, 2, 3}, полиномиальны.

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

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

2. Многообразия тернарных -алгебр являются Шрайеровыми.

3. Функции сложности разрешимых и вполне разрешимых алгебр в рассматриваемых многообразиях тернарных алгебр алгебраичны.

4. Функции сложности многообразий вполне левонильпотентных и левонильпотентных тернарных алгебр алгебраичны.

5. Понятия разрешимости и левонильпотентности для тернарных алгебр интерпретированы в терминах запрещенных поддеревьев.

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В

СЛЕДУЮЩИХ РАБОТАХ

Работы автора по теме диссертации в журналах списка ВАК [1] Уадилова А. Д. Разрешимые тернарные алгебры и тернарные деревья. // Вестник СамГУ Естественнонаучная серия. N 2 (32).

2008. с. 77 – 90.

[2] Уадилова А. Д. Свободные -алгебры и тернарные деревья. Ученые записки Ульяновского государственного университета. Сер. Фундаментальные проблемы математики и механики. Вып. 1(14) / Под ред. проф.

А. С. Андреева. Ульяновск: УлГУ, 2004. с. 46 – 56.

[3] Уадилова А. Д. Перечисление тернарных деревьев. Проблемы теоретической кибернетики. Материалы XIV Международной конференции (Пенза, 23-28 мая 2005 г.), под ред. О. Б. Лупанова. М.: Изд-во механико-математического факультета МГУ, 2005. с. 158.

[4] Уадилова А. Д. Перечисление разрешимых тернарных алгебр и тернарных деревьев. Труды Математического центра имени Н. И. Лобачевского. Т.31, Казанское математическое общество. "Лобачевские чтения 2005", Материалы Четвертой молодежной научно-практической школы-конференции. Казань: Издательство Казанского математического общества, 2005. с. 159 – 160.

[5] V. M. Petrogradsky, A. D. Uadilova. On subalgebras of ternary algebras. // 6th International Algebraic Conference in Ukraine. Abstracts (KamyanetsPodilsky, July 1 7, 2007). p. 150 – 151.