Перечисление тернарных алгебр и деревьев тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

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

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

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

Автореферат

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

Ульяновск - 2008

003449167

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

Научный руководитель доктор физико-математических наук,

Официальные оппоненты доктор физико-математических наук,

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

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, авторефератом — на сайте вуза http //www um ulsu ru

Отзывы по данной работе просим направлять по адресу 432000, г Ульяновск, ул JT Толстого, д 42, УлГУ, Управление научных исследований

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

профессор

Петроградский Виктор Михайлович

профессор

Зайцев Михаил Владимирович

кандидат физико-математических наук Рацеев Сергей Михайлович

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

Ученый секретарь диссертационного совета

М А Волков

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

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

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

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

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

Основным объектом исследования в данной работе являются многообразия тернарных алгебр, т е алгебр с трилинейной операцией В этом

1 Ширшов А И Подалгебры свободных лиевых алгебр 11 Математический сборник, т 33 (75), N 1 - 1953 - с 441 - 452

2 Ф Харари, Э Палмер Перечисление графов Перев с акп — М Мир, 1977 —326 с 3Р Стенли Перечислительная комбинаторика Перев с англ — М Мир, 1990 —440 с

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

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

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

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

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

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

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

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

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

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

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

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

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

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

мыл алгебр в рассматриваемых мнетообразиях тернарных алгебр,

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

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

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

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

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

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

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

Объем и структура диссертации. Диссертация состоит из введения,

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

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

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

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

Пусть К — основное поле Пусть Ь — алгебра с полилинейной тернарной операцией, т е для любых а, Ь,с е Ь определен элемент (1 = (а,Ь,с) € Ь и ^ полилинейно зависит от а,Ь,с Пусть 2Во — класс всех тернарных алгебр

Тернарную алгебру Ь назовем симметричной, если выполняется тождество (<21,02,аз) = (а<,(1),аст(2),а<7(з))> где а1,а2,а3 6 Ь и а 6 Класс симметричных тернарных алгебр обозначим ШЗ1

Алгебру Ь с тернарной операцией назовем кососимметричной, если выполняется тождество (аь а2, а3) = (—1),т(а0(1),а<,(2).а<т(3)). где а!,а2, аз € Ь и а 6 ¿з Пусть 202 ~ класс всех кососимметричных алгебр

Тернарную алгебру Ь назовем циклической, если выполняется тождество [а, Ь, с) = (Ь, с, а), для всех а, Ь, с С Ь Обозначим через 2Вз класс таких алгебр

Двудольная тернарная алгебра Ь задается тождеством перестановки крайних членов (а,Ь, с) = (с, 6,а), где а, 6,с € Ь Пусть 204 — класс всех таких алгебр

Далее используем обозначение 2Ц;, где 6 € {0,1,2,3,4} Для произвольного многообразия тернарных алгебр 2} через 1, X) будем обозначать его свободную алгебру, порожденную множеством X = {х\, ,хп, } Если |Х| = з, то получаем относительно свободную алгебру ранга в, которую будем обозначать также ^(Ш, в)

Пусть V — мншообразие и F(V,X) —сю свободная алюбра5, порожденная счетным множеством X = {т,| ? 6 N} Обозначим через P„(V) С F(V,X) подпространство всех полилинейных элементов степени п на множестве {zj, ,х„} и рассмотрим размерность этого подпространства

Cn(V) = сп (F(V,X),,К) = dimKPn(V), пе N

Возникает последовательность коразмерностей cn(V), п —

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

00

Для произвольной градуированной алгебры А = ф А„ ряд <I>(í) =

П=1

00

antn, где ап = dirriA'Ai называется производящей функцией

П=1

Рассмотрим свободную алгебру А конечного ранга, она является гра-

сс

дуированной (т е А = ф Ап) Определяем ряд Гильберта-Пуанкаре

п= i

Н{А, t) как производящую функцию

оо

ЩА, = antn, где ап = dimx Ап

П=1

Ю П Размыслов предложил также рассматривать для многообразия алгебр Ли так называемую функцию сложности8 Определим функцию сложности для многообразия V как

п П

п—О

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

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

6 Drensky V , Free algebras and PI algebras —Springer, Singapore 2000 —271 p

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

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

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

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

Пусть Г = ^(2Пг,Х) - свободная алгебра многообразия тернарных ¿-алгебр, порожденная множеством X Определим б-регулярные слова

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

1 Слово и — (и, V, ш) представимо как результат тернарной операции, аргументами которой выступают слова и, V, ю меньшей длины,

2 • и > V > V) в случае <5 = 1,

• и > V > ги в случае 5 — 2,

• и > тах{г),и)}, причем в случае равенства предполагаем и = V > и>, в случае <5 = 3,

• и > ю в случае 5 = 4

Продолжим порядок произвольным образом на все ¿-регулярные слова длины п

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

Будем интерпретировать элементы построенного базиса как тернарное дерево Например, элементу ш = (((ггьжг.яз),^^))^ а-8)^э)), где XI, , жд € X, сопоставим следующее тернарное дерево (рис 1)

Рис 1 Тернарное дерево слова и = ( ^(хь дг2) ж3),а4, ,хе, (хг,х8,хд^ )

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

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

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

В терминах тернарных деревьев функции сложности 5-многообразий Ш3{, 6 € {0,1, ,4} перечисляют некоторые корневые тернарные де-

ревья соответствующих пяти типов, листья которых отмечены различными элементами счетного множества X = {т,| » е IV}

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

Доказано, что, если Ф(<) — производящая функция свободной тернарной ¿-алгебры к) конечного ранга к, $ € {0,1,2,3,4}, то она удовлетворяет уравнению

Ф(г) =

Ф3(г) + м, 5 = о,

т±тт + т + ки ¿ = 1)2, т + ят + н, 6 = з, т + т + к1, г = 4

2 ^ 2

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

00

Теорема 1: Пусть Ф(£) = 2 ~~ производящая функция абсо-

П=1

лютно свободной тернарной алгебры /?(2Во, к) Тогда 1

71—ЮС *

2 Ф(£) алгебраинна и равна

(где г2 = — 1 и под корнями подразумеваем ветви у/1 = 1 и ^/1 = 1)

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

Эют 1ермин возник в связи t классической теоремой О Шрайера о свободе подгрупп в свободной ipynne 10 Друшм примером Шраиерова мноюобразия является класс свободных алгебр Ли (теорема Ширшова-Витта)1 11 Имеет место также теорема о свободе подалгебр в свободных етраниченных алгебрах Ли (Витт11) Аналогичная теорема также верна для свободных цветных супералгебр Ли12 Как правило, свободные подалгебры бесконечно порождены в этом случае и формулы Шрайера нет Однако, в терминах производящих функций Петроградским В N1 найден аналог формулы Шрайера13 Шрайеровы многообразия играют важную роль в современной алгебре14

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

Основной результат третьей главы состоит в следующем Теорема 2* Пусть Н — ненулевая подалгебра свободной тернарной 6-алгебры F = F(%B¡, X) (S = 0, , 4) над полем К Тогда Н — свободная тернарная 8-алгебра для всех <5 = 0, ,4

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

10 Schrcicr О Die Untergruppen der freien Gruppen // Abh Math Sem Univ Hambuig 5 — 1927 — p 161 - 183

" Witt E Die Untcmnge der freien Lieschen Ringe // Math Z 64 -1956 - p 195 - 216

12 Bahturm Yu A , Mikhalev A A , Petrogradsky V M, Zaicev M V Infinite Dimensional Lie Superalgebras — Berlin, New York de Gruyter, 1992 —250 p

13 Petrogradsky V M Schreier's formula for free Lie algebras //Arch Math (Basel) 75 (1) —2000 -D 16-28

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

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

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

И

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

Определим рекуррентно мономы 5о(Л'1) = Х\ и для q > 0 положим

,Л'з7+1) =

Назовем 5-ал1ебру разрешимой ступени если она удовлетворяет тождеству 59(Х\, , Хзя) = 0 Многообразие 5-алгебр, разрешимых ступени q, обозначим как 21'

Определим ряд коммутантов для тернарной 5-алгебры Ь следующим образом = Ь и Ь= ¿М))* для г > 1

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

1 алгебра Ь разрешима ступени д,

2 = О,

3 существует цепочка подалгебр

ь = ь0 э ьх О Э1, = 0, (1)

где Ь, < Ьг-1 и Ьг-1 ^Ьг — абелева для всех г = 1, , ц

Заметим, что подалгебры Ь<•> могут и не быть идеалами для Ь Возьмем некоторую подалгебру Я С Ь и обозначим через /(¿¿(Я) — идеал в Ь, порожденный подал1еброй Я

Назовем ¿-алгебру Ь вполне разрешимой ступени д, если существует цепочка (1), элементы которой являются идеалами в Ь Определим ряд пополненных коммутантов = Ь и для всех г > 1 (г + 1)-ый пополненный коммутант Ь11+11 =

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

1 выполняется условие = О

2 Ь вполне разрешима ступени ц

Класс всех вполне разрешимых й-алгебр обозначим как &1 Введем такое понятие как полное тернарное дерево высоты <] Будем обозначать его Тч Вместо формальною определения изобразим полное тернарное дерево высоты 3 (рис 2)

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

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

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

1 Все 5-регулярные мономы, деревья которых не содержат полные тернарные поддеревья Т4, образуют базис свободной разрешимой 5-алгебры ^(21', X) ступени д

2 Базис вполне разрешимой 6-алгебры ^(6', X) ступени д образуют 5-регулярные мономы, деревья которых не содержат полные тернарные поддеревья Тч высоты д после произвольного числа редукций

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

Теорема 4' Пусть 6| — многообразие вполне разрешимых тернарных алгебр в классе 2Ц$, 5 = 0,1, ,4 Тогда функция сложности ал-гебраична и вычисляется так

С(в36,г) = Мг)+Мг)+

где функции 1р,(г),г = 1, , = задаются рекуррентно ^1(2) — г и для г = 1, , э — 1 функция ^1+1(2) удовлетворяет квадратному уравнению над полем СЦтр^г),

•(рм*)) ФШ+^ЕМ^2+ = о,для 5 = 0,

• (¿тш) -2^ + ^ = 0,для

5= 1,2

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

Теорема 5. Пусть 21ц — многообразие разрешимых ступени ц алгебр

вШ0

1 Рассмотрим функцию сложности /(г) = С(21д, г) Тогда функция /(г) алгебраична и удовлетворяет алгебраическому уравнению степени 2 * З''"2 над С}[г]

oc.it) = /(г),

где функции а,(г) задаются рекуррентно сч(г) — г и для г =

1, ,9-1

о,+1(г) = г + За,(г) (/(г) - аг(г))2 + За,2(г) (/(г) - о,(г)) ■+- а?(г)

2 Лгс? Гильберта-Пуанкаре для относительно свободной алгебры ранга к алгебраичен и равен

Аналогичные утверждения доказаны для многообразий разрешимых ступени q ¿-алгебр, где <5 € {1,2,3,4}

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

Обозначим через '0^ многообразие тернарных ¿-алгебр, определяемое тождеством

(( ((ХЪХЬХ3),Х4,Х5) ),Хъ,Х2з^=0 (2)

Будем называть это многообразие левонильпотентным ступени ч Пусть Ь — ё-алгебра Определим лево-цегппралъную последовательность Она состоит из следующих подалгебр

Ь° = Ь и Ьм = (¿Д Ь, Ь) для к > О

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

1 алгебра Ь левонилъпотентна ступени 5

2 Ьь = О

3 существует цепочка подалгебр Ь,, такая что

Ь = ¿о 2 Э Э Ь5 = 0 и (Ь„ Ь, Ь) С ¿1+1 при г = О, , в

(3)

Пусть Я—такая подалгебра в которая обладает следующим свойством (Я, и,г>) С Н,{и,Н,г>) С Я и (и,и,Л) С Я для произвольных и,и 6 Ь Тогда Я называется идеалом Ь Пусть X = /¿¿(Я) обозначает минимальный идеал, содержащий множество Я Замечание В случаях 5 = 1,2,3 подалгебры являются идеалами в I/ Однако, в случаях 5 — 0,4 элементы лево-центральной последовательности ¿г могут и не быть идеалами Но если предположить, что существует последовательность идеалов вида (3), то будем называть Ь вполне левонильпотентной ступени в

Определим лево-вполнецентралъную последовательность I/0 = Ь и

= для г > О

Лемма 5. Вполне левонильпотентность ступени э эквивалентна условию Ь" = О

Согласно замечанию выше, вполне левонильпотентность совпадает с левонильпотентностью в случае <5 = 1,2,3 В случае 2Ио эти два понятия различаются и многообразие вполне левонильпотентных 0-алгебр обозначим как а<УЦ)

Для всех .ч > О определим дерево С^, оно имеет .ч + 2 листа и выглядит так.

Рис. 6. Дерево

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

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

1. Все <5-регулярные мономы, деревья которых не содержат С?5, образуют базис Р(1Щ,Х) - свободной левонилъпотентной ступени в <5-алгебры.

2. Базис Р{с1%, X) — свободной вполне левонилъпотентной ступени в 0-алгебры, состоит из регулярных мономов, деревья которых не содержат после произвольного числа редукций.

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

Теорема 7: Пусть V = с,(Ло ~~ многообразие вполне левонильпотентных тернарных алгебр ступени в в где я > 1. Тогда

1. функция сложности С(V, г) алгебраична, причем С(V, г) — аДг), где функции а,(г), г = 1,..., 5, задаются рекуррентно:

4'+ 2

поддеревьев.

щ(г) = г и для г = 1, ,s — 1 функция л,+)(г) удовлетворяет следующему квадратному уравнению над

С[о,(г), ,аф)]

a.(z)a,2+1(z) ~ 0^+1(2) + г = О

2 Ряд Гильберта-Пуанкаре относительно свободной алгебры ранга к алгебраичен и равен

H{F(V, k),t) = C(V, kt)

Теорема 8: Пусть V = 'ЭДц — многообразие левонильпотентных тернарных алгебр ступени s в 2Во Тогда

1 функция сложности f(z) = C(V, z) алгебраична и удовлетворят уравнению

f(z) = z{l + f(z) + nz)+

2 Ряд Гильберта-Пуанкаре относительно свободной алгебры ранга к алгебраичен и равен

H(F(V, к), t) — C(V, kt)

Также доказано, что ряды Гильберта-Пуанкаре многообразий левонильпотентных тернарных алгебр ступени s в fflg, где 5 £ {1,2,3}, полиномиальны

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

выводы

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

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

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

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

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

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

Работы автора по теме диссертации в журналах списка ВАК

[1] Уадилова А Д Разрешимые тернарные алгебры и тернарные деревья // Вестник СамГУ— Естественнонаучная серия — N 2 (32) — 2008 - с 77-90

Публикации в прочих изданиях

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

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

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

|5] V М Petrogradbky, A D Uadilova On subalgebras of ternary algebras // 6th International Algebraic Conference m Ukraine Abstracts (Kamyanets-Podilsky, July 1 - 7, 2007) - p 150 - 151

Подписано в печать 19 09 2008 Формат 60x84/16 Уел печ л 1,40 Тираж 80 эй Заказ -103 9

Типография УлГТУ, 432027, г Ульяновск, ул Сев Венец, 32

1 Введение

1.1 Тернарные 5-алгебры и производящие функции

1.2 Свободные 5-алгебры и тернарные деревья.

1.3 Шрайеровость многообразий алгебр.

1.4 Разрешимые и вполне разрешимые тернарные 5-алгебры, запрещенные поддеревья и производящие функции.

1.5 Нильпотентность тернарных 5-алгебр.

2 Свободные 5-алгебры и тернарные деревья

2.1 Свойства экспоненциальных производящих функций

2.2 Связь тернарных 5-алгебр и тернарных деревьев.

2.3 Производящие функции абсолютно свободных тернарных алгебр

2.4 Тернарные алгебры с тождеством симметричности и про---- странственные тернарные деревья------- . .

2.5 Тернарные алгебры со свойством кососимметричности и пространственные несимметричные тернарные деревья.

2.6 Циклические тернарные алгебры и пространственные "зонтичные" тернарные деревья.

2.7 Двудольные тернарные алгебры.

3 Шрайеровость многообразий 5-алгебр

3.1 Свойства свободного тернарного группоида.

3.2 Порождающие множества для некоторых алгебр.

3.3 Фильтрация и градуировка (5-тернарных алгебр

4 Разрешимые и вполне разрешимые тернарные 5-алгебры, запрещенные поддеревья и производящие функции

4.1 Геометрическая интерпретация разрешимых и вполне разрешимых тернарных алгебр.

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

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

5 Нильпотентность тернарных <5-алгебр

5.1 Два понятия левонильпотентности и вполне левонильпотент-ности.

5.2 Связь левонильпотентных алгебр и тернарных деревьев

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

5.4 Ряд Гильберта-Пуанкаре левонильпотентных тернарных алгебр

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

Фундаментом многих исследований являются работы А. И. Ширшова, доказавшего теорему о свободе подалгебр в свободных алгебрах Ли ([16]).

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

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

За последние десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики ([13], [14]). Это связано с тем, что теория графов, родившаяся при решении головоломок и занимательных задач, стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно интерпретировать, например, схемы дорог и электронные схемы, географические карты и молекулы химических соединений, связи между людьми и многое другое. Это привело к широкому использованию теории графов в физике и кибернетике, химии и биологии, экономике и статистике и других науках. Особенно важна роль теории графов в современном программировании.

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

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

В Главе 1 данной работы приведены основные определения и формул-лировки полученных результатов

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

В главе 3 изучается шрайеровость многообразий тернарных алгебр.

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

Этот термин возник в связи с классической теоремой О. Шрайера о свободе подгрупп в свободной группе [24]. В качестве основного результата доказана шрайеровость многообразий тернарных алгебр.

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

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

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

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

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

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

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

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

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

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

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

4. Мальцев А. И. Алгебраические системы. — М.: Наука, 1970.— 392 с.10.~Михалев"АТ"А7^Подалгебры свободных"цветных супералгебр~Лиг"//Мат. заметки, т. 37. —1985. — с. 653 651.

5. Петроградский В. М. Рост полилинейных многообразий алгебр Ли и быстро растущие функции. // Математический сборник, т. 188, N6. — 1997.-е. 119 138.

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

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

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

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

10. Ширшов А. И. Подалгебры свободных лиевых алгебр. // Математический сборник, т. 33 (75), N 1. — 1953.-е. 441 452.

11. Bahturin Yu. A., Mikhalev A. A., Petrogradsky V. М., Zaicev М. V. Infinite Dimensional Lie Superalgebras. — Berlin; New York: de Gruyter, 1992.— 250 p.

12. Drensky V., Free algebras and Pi-algebras. — Springer, Singapore, 2000.— 271 p.

13. Mikhalev A. A. Primitive elements and automorphisms of free algebras of---Schreier-varieties. // J- Math.Sci.,.(New York) 102 (6). — 2000. -p.4627- 4639.

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

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

16. Petrogradsky V. M. Schreier's formula for free Lie algebras. // Arch. Math. (Basel) 75 (1). 2000. - p. 16 - 28.

17. Petrogradsky V. M. Enumeration of algebras close to absolutely free algebras and binary trees // Journal of Algebra, N 290(2). — 2005. — p. 337 371.

18. Schreier O. Die Untergruppen der freien Gruppen. // Abh. Math. Sem. Univ. Hamburg 5.-1927, —p. 161 183.

19. Witt E. Die Unterringe der freien Lieschen Ringe. // Math. Z. 64,— 1956.-p. 195-216.