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

российская академия наук ИНСТИТУТ ПРОГРАММНЫХ СИСТЕМ

РГВ од

1 3 ДЕК 20СЗ

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

КАИШЕВ Андрей Игоревич

СИСТЕМА ПРОГРАММ ДЛЯ ИССЛЕДОВАНИЯ КОМБИНАТОРНО-АЛГЕБРАИЧЕСКИХ ИНВАРИАНТОВ ТОПОЛОГИЧЕСКИХ ОБЪЕКТОВ МАЛОЙ РАЗМЕРНОСТИ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Переславль-Залесский - 2000

Работа выполнена в Исследовательском Центре мультипроцессорных систем Института Программных Систем РАН.

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

с. н. с. С.В.Дужин

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

профессор И. С. Красильщик кандидат физико-математических наук С. К. Ландо

Ведущая организация: Математический Институт

им. В. А.Стеклова РАН

Защита состоится "гг. " ш^^л^я 2000 года в на заседании диссертационного Совета Д 200.36.01 при Институте Программных систем по адресу: 152140, Ярославская обл., Переславль-Залесский, м. Ботик, ИПС РАН, конференц-зал.

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

Автореферат разослан " ¿О " ^я 2000 года.

Ученый секретарь диссертационного Совета к.ф.-м.н. В.Н.Юмагужина

В / 03 В 4*2,. 3,03

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

Актуальность темы. Диссертация описывает комплекс компьютерных программ, разработанных автором для решения математических задач, относящихся к теории узлов. Этих задач несколько, и все они так или иначе связаны с так называемыми инвариантами узлов конечного типа, введенными московским математиком В.А.Васильевым в 1990 году'1. Актуальность проблематики подтверждается тем фактом, что в течение 10 лет в мире вышло около 500 работ, посвященных изучению инвариантов Васильева, и в Интернете с 1994 года действует специальная библиографическая страничка2. Несмотря на столь большой объем проведенных исследований, несколько фундаментальных вопросов остаются до сих пор открытыми. К их числу относятся:

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

• проблема полноты системы инвариантов Васильева: верно ли, чт,о при помощи инвариантов Васильева можно различить любые два узла?

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

В последние годы несколькими математиками были предприняты попытки дать на эти вопросы хотя бы частичный ответ при помощи компьютерных вычислений (см., например, работы Д.Бар-Натана3 и Я.Кнайсслера4.

1V. A. Va.ssiliev, Cohomology of knot spaces, Theory of Singularities and Its Applications (ed. V. I. Arnold), Advances in Soviet Math., 1 (1990) 23 G9.

2D. Bar-Nat,an, Bibliography of Vassilie.v Invariants. Web publication http://vnrH.ma.huji.ac.il/~drorbn/VasBib/VasBib.html.

3D. Bar-Nat.an, Some computations related to Vassilie.v invariants. Web publication http://www.ma.huji.ac.il/-drorbn/papers/table.dvi.

4 J. Kneissler, The number of primitive Vassiliev invariants up to degree twelve. Preprint q-alg 970G022, also available at http://rhein.iam.uni-bonn.de/-jk/, June 1997.

Настоящая диссертация примыкает к этому актуальному направлению.

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

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

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

1. Разработан алгоритм нахождения образующих центра уни- ■ версальных обертывающих алгебр для алгебр Ли серий А, В, С, £> и особой алгебры С?2 (см. §2.2). Для этих алгебр вычислены и выражены через образующие центра значения весовых систем Концевича на примитивных элементах алгебры хордовых диаграмм до порядка 4 (§2.5).

2. Предложен алгоритм и реализован комплекс программ для исследования структуры алгебры 3-графов (глава 3). С их помощью найдены линейный базнс и система мультипликативных образующих данной алгебры в малых размерностях (до градиуровки 11).

3. Реализован алгоритм вычисления и .чо^-полпномов (§4.2), в том числе его параллельная версия (§4.3), и составлены таблицы значений .<¡1- и .чо-полиномов на мультипликативных образующих алгебры 3-графов Г (см. таблицу 4.2).

4. Разработана программа для проведения вычислений в алгебре 4-графов Ландо (глава 5). При помощи этой програм-

мы найдено ядро гомоморфизма из алгебры хордовых диаграмм в алгебру 4-графов для степени диаграмм, не превосходящей 7.

Научная и практическая значимость полученных результатов. Работа носит в основном теоретический характер. Ее результаты представляют двоякий интерес: с точки зрения математических исследований, связанных с инвариантами узлов и градуированных алгебр, и с точки зрения разработки и реализации -наукоемких алгоритмов для математических вычислений. Алгоритмы и программы, составляющие предмет диссертации, готовы к использованию в дальнейших исследованиях. Практическим результатом работы является тестирование Т-системы, разработанной в Исследовательском Центре мультипроцессорных систем ИПС РАН в качестве средства автоматического динамического распараллеливания — некоторые результаты диссертации получены посредством исполнения программ в среде Т-системы.

Апробация работы. Основные результаты диссертации до1 кладывались на международной конференции "New Computer Technologies in Control Systems." Переолавль-Залесский, 1995, на международной конференции "Приложения компьютерной алгебры", Санкт-Петербург, июнь 2000, и на семинарах по математике Исследовательского Центра мультипроцессорных систем ИПС РАН. Разработанные программы использовались для проведения комбинаторных вычислений в Независимом Московском университете (С. К. Ландо и ученики) и для тестирования Т-системы автоматического динамического распараллеливания в ИЦМС ИПС РАН под руководством С.М.Абрамова.

Публикации. Основные научные результаты диссертации опубликованы в 5 печатных работах, список которых приведен в конце автореферата. Тексты программы и файлы данных доступны по протоколу ftp на сервере math.botik.ru.

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

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

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

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

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

Особый узел — это гладкое отображение / ориентированной окружности 51 в трехмерное пространство К3, которое всюду является вложением, кроме конечного числа простых двойных точек, т.е. точек трансверсального пересечения двух ветвей замкнутой кривой. Особый узел с п двойными точками назовем п-узлом.

Два п-узла называются изотопными, или эквивалентными, если существует однопараметрическое семейство п-узлов .К^, 0 < t < 1, гладкое зависящее от параметра £ и такое, что Ко и К\ — это два данных узла.

Обозначим через К.п множество классов эквивалентности п-узлов. В частности, /Со — это множество топологических типов обычных узлов без особенностей. Положим К. — ип>о/Сп — это множество классов эквивалентности всех особых узлов.

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

Если задан инвариант обычных узлов / : /Со —Я, то следующая формула определяет его продолжение по Васильеву на особые узлы:

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

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

Хордовая диаграмма степени т — это ориентированная окружность, на которой отмечено т пар точек, соединенных хордами.

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

Двойственным образом, каждому инварианту Васильева V порядка не выше п можно сопоставить функцию -ш,, на множестве хордовых диаграмм по правилу: м„(1)) = ч>(К), где К — такой особый узел, что х{К) — Получаемые таким образом функции не произвольны: они являются весовыми системами.

Весовая система — это функция на множестве хордовых диаграмм, удовлетворяющая 4-членным соотношениям

(Участки окружности, отмеченные пунктиром, могут соединяться другими хордами, одними и теми же для всех четырех диаграмм; разница между диаграммами заключается в двух "подвижных" хордах, показанных на рисунке).

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

Точная связь между инвариантами Васильева и функциями на пространстве хордовых диаграмм заключается в следующем. Обозначим через Уп пространство инвариантов порядка не выше п со значениями в поле нулевой :характеристики Р, а через Т> — факторалгебру алгебры V по дополнительным 1-членным соотношениям (приравниваются к нулю все диаграммы, содержащие изолированную хорду). Тогда имеет место теорема Васильеаа-Концевича: Уп/У„_ 1 = V*, где пространство хордовых диаграмм рассматривается над тем же полем Р, а звездочка обозначает сопряженное пространство, т.е. пространство линейных функций со значениями в Р.

Структура градуированной алгебры Т> — Фп^п известна в настоящее время только до степени п — 12 (Я. Кнайсслер, см. ссылку на стр. 1), поэтому большой интерес представляют компьютерные программы, позволяющие получить частичную информацию об этой алгебре. Программирование вычислений, связанных с пространством хордовых диаграмм, представляет трудности по двум причинам: во-первых (качественная причина), хордовые диаграммы — нестандартный комбинаторный объект, а во-вторых (количественная причина), число образующих и соотношений, определяющих однородную компоненту Т>п, чрезвычайно быстро растут с ростом п.

В диссертации разработана система программ для проведения вычислений в алгебре хордовых диаграмм (глава 2) и связанных с ней алгебре 3-графов (главы 3, 4) и 4-алгебре графов (глава 5).

Во второй главе описан комплекс программ для вычисления весовых систем Концевича со значениями в центре универсальной обертывающей алгебры [/(д) некоторых простых алгебр Ли 0. Мы приводим алгоритм нахождения образующих центра алгебры и (в), вычисляем значения весовых систем на примитивных элементах алгебры хордовых диаграмм и выражаем их через об-

радующие центра в виде многочлена с рациональными коэффициентами.

Весовые системы — линейные функции на алгебре хордовых диаграмм Т> — являются важным инструментом для изучения структуры алгебры V. Практически единственным способом доказательства того, что два элемента ¿'2 £ V различны, является построение весовой системы п> такой, что VI(ё 1) ф 111(^2). Весовые системы со значениями в универсальных обертывающих алгебрах представляют собой самый богатый известный класс весовых систем. Вот конструкция, данная М.Концевичем5.

Пусть элементы е,- образуют базис алгебры Ли 9, — дуальный базис относительно аЛ-инвариантной билинейной формы. Сопоставим каждой хорде диаграммы некоторый индекс и запишем (некоммутативный) моном от элементов в,-, е.* по следующему правилу: начиная с некоторой точки на окружности будем обходить диаграмму в положительном направлении и записывать в моном с.{ при первом прохождении конца хорды с индексом i, а при прохождении второго конца — е*. Например, диаграмме

соответствует моном

После суммирования по всем индексам получается элемент из центра универсальной обертывающей алгебры II(д):

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

Явное нахождение таких весовых систем сопряжено с большими вычислительными трудностями. Исключение составляет са-

SM. Kontsevich, Feynman diagrams and low-dimensional topology, First European Congress of Mathematics II 97 121, Birkhäuser, Basel 1994.

мая маленькая нз всех простых алгебр Ли sl2, для которой найдены специальные, более эффективные алгоритмы счета (см. работы Д. Б ар- Натан а1' и А.Варченко и С.Чмутова7). Вычисление весовых систем Концевича для других алгебр Ли впервые предпринято в настоящей работе. Подчеркнем, что явных формул или рекуррентных соотношений нам найти не удалось, и речь идет о вычислительных алгоритмах и реализующих их компьютерных программах, которые позволили найти значения указанных весовых систем для нескольких первых простых алгебр Ли на хордовых диаграммах малых порядков.

Универсальная обертывающая алгебра U алгебры Ли 0 — это алгебра некоммутативных многочленов от элементов д, в которой перестановочные соотношения для одночленов определяются законом умножения в 0, то есть ху — ух — [х,у\.

Как известно (см. Н. Бурбаки. Группы и алгебры Ли. Гл. 8 §8), центр универсальной обертывающей алгебры представляет собой алгебру коммутативных многочленов от конечного числа переменных. В параграфе 2.2 мы предлагаем алгоритм явного построения системы образующих этой алгебры. Все дальнейшие вычисления проводятся с использованием этой системы образующих. В параграфе 2.3 описывается каноническая матричная реализация простых алгебр Ли серий А, В, С, D и исключительной алгебры G'i- Матричная реализация указанных алгебр в принципе хорошо известна. Новым в нашей работе является доведение ее до того уровня конкретности, который позволяет обращаться с элементами этих алгебр чисто алгоритмически.

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

"D. Bar-Natan, On the Vassilieu knot invariants, Topology, 34 (1995) 423

472.

7S. Chmutov, A. Varchenko, Remarks on the Vassiliev knot invariants corning from sl2, Topology 36 (1997) 153 178.

Список диаграмм, сформированный программой Д. Бар-Натана

РЕЛЬ-программа cd2frm.pl, преобразующая ого в ГОНМ-программу

ЕСЖМ-программа

вычисляющая значение весовой системы па ^__диаграмах

Список значений весовой системы, в виде | многочленов от .

элементов алгебры Ли

Марк-программа, генерирующая прогр.гмму вычисления образующих

ГОЛМ-программа

вычисляющая образующие центра

^гтттт!

Список образующих центра в виде |

многочленов от .

элементов алгебры Ли

Мар1с-программа, выражающая значения^ весовой системы через образующие центра

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

Итог вычислениям главы 2 подводит следующая таблица. В

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

Таблица 2.1. Значения 2(д)-значных весовых систем на примитивных образующих алгебры хордовых диаграмм до

степени 4.

Ч Ч *з и 7/) 4

м 2^1 -42х 82х 82?

>42 32г -9^1 272х 92? - 9^1

Ая -2Х -1621 642х -4/323 + 102? - 88/321

А,4 -2Х ьг1 -25^1 125^1 112? - 5/323 - 65^1

в2 3/2^1 -9/4^1 27/8^1 1/222 +3/22?-3/221

Дч 5/221 -25/421 125/821 1/622 + 5/221 - 25/321

Сз 42х -1621 64^1 -7/322 + 102? - 88/321

#4 32Х -9^1 27^1 321 -

о2 22Х -4^1 82Х 5/22? - 11/321

Основными результатами главы 2 являются:

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

большой вычислительной сложности работоспособен только для нескольких первых алгебр серий А, В, С, Б и для алгебры типа О2 (см. параграф 2.4.3).

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

• Разработан и реализован алгоритм выражения значений весовых систем на образующих центра, использующий изоморфизм Z(g) и алгебры инвариантных многочленов установленный теоремой Хариш-Чандры (см. параграф 2.4.3).

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

Третья глава посвящена исследованию структуры алгебры 3-графов Г, введенной в статье [4].

3-граф — это простой трехвалентный граф, в котором в каждой вершине фиксирован один из двух возможных циклических порядков выходящих из нее ребер. Это понятие отличается от понятия хордовой диаграммы лишь тем, что в нем отсутствует выделенный гамильтонов цикл (внешняя окружность хордовой диаграммы). Аналогом 4-членных соотношений в алгебре 3-графов являются соотношения антисимметрии (АБ) и соотношения Кирхгофа (1НХ):

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

(АЭ):

(1НХ):

© гг^

I_____I

= х-у

Для проведения вычислений в алгебре Г разработана система программ следующего состава:

( С-программа grЗg, составляющая список

V

графов

гГттт^

1 Список регулярных 1 | трехвалентных графов |

При помощи этой системы программ найден базис векторных пространств Гп для п < 10 (базис Гц найден косвенным образом при помощи программ, рассматриваемых в главе 4).

Таблица 3.1. Базис линейных пространств Гп

п (11тГп аддитивные образующие

1 1 О

2 1 О

3 1 о

4 2 о®

5 2 о®

6 3

7 4 О

8 5

9 6

10 8

11 9

Из таблицы 3.1 видно, что мультипликативные образующие Г до градуировки 11 выглядят следующим образом (в нижней строчке указаны соответствующие обозначения: Ь — "пузырь", ?/;,• — "колеса", Л — "додекаэдр"):

Таблица 3.2. Мультипликативные образующие алгебры Г

n 1 4 б 7 8 9 10 И

О @ © @ Ф

b iüj m vi<¡ •»>10 d vin

Основными результатами третьей главы являются:

• Разработка усовершенствованного алгоритма генерации списка всех 3-графов (параграф 3.1).

• Разработка и реализация алгоритма выражения 3-графов через образующие (параграф 3.2). Существенной его частью является алгоритм точного решения систем линейных уравнений специального вида (с матрицей, в каждой строке которой не более трех чисел отличны от 0), который позволил обрабатывать системы из десятков тысяч уравнений.

• В результате работы программы были найдены линейный базис алгебры 3-графов и система мультипликативных образующих до градуировки 10. Эти значения приведены в таблицах 3.1 и 3.2. Имеющиеся в этих таблицах значения градуировки 11 получены в результате работы программ, рассматриваемых в следующей главе.

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

Четвертая глава посвящена вычислению полиномиальных инвариантов 3-графов, связанных с алгебрами Ли и В первом параграфе описана восходящая к Р. Пенроузу8 и М. Кон-цевичу9 конструкция, позволяющая по алгебре Ли g с заданной

SR. Penrose, Applications of negative, dimensional tensors, In: Combinatorial mathematics and its applications (ed. D. J. A. Welsh), New York, London: Acar demie Press, 1971.

йСм. ссылку на стр. 7.

невырожденной аЛ-ннвариантной билинейной формой В (в частности, по любой простой алгебре Ли) построить функцию К® на множестве 3-графов, порождающую гомоморфизм алгебр Г —> К.

Параграф 4.2 посвящен реализации алгоритма вычисления и /»»-полиномов. В тексте диссертации приведена соответствующая программа на псевдокоде.

В параграфе 4.4 изложена параллельная версия алгоритма и ее реализация на языке t2cp в рамках системы автоматического динамического распараллеливания программ (Т-системы10).

Основными результатами четвертой главы являются:

• Реализация алгоритма вычисления и яодг-полиномов, изложенного в параграфе 4.2.

• Разработка параллельной версии этой программы на языке t2cp (см. §4.3-4.4). Наличие этой версии позволило вычислить инвариантные многочлены от графов градуировки 11. Один из примеров был посчитан и в градуировке 12 (граф с 24 вершинами), однако этот расчет проводился на пределе вычислительной мощности имеющейся установки.

• Вычисление .чI- и яо-полиномов для мультипликативных образующих алгебры 3-графов Г (см. таблицу 4.2). Эти значения позволили установить, что элементы градуировки 11, приведенные в таблице 3.1, линейно независимы.

Следующая таблица содержит значения и яо^-полиномов на образующих алгебры Г до степени 11, полученные ы результате исполнения программы ¡гг_1пч. В таблице полиномы приводятся в нормализованном виде (деленные на размерность алгебры); для алгебры .во выражение дается через переменную М = N — 2.

Таблица 4.2. Значения я1- и ло-полиномов на образующих.

10 С.М. Абрамов, А.И.Адамович. Т-система срр.да программирования с. поддержкой автоматического динамического распараллеливания программ // Юбилейный сборник трудов Института иро1раммиых систем. Под ред. проф. В.И. Гурмана, Переславль-Залесский, ИПС РАН, 1999 г.

X slN(x) soN(x)

b 2 N 2 M

VI4 27V4 + 24 N2 2Mi - 6M3 + 60M2 - 48M

m 2 7VB + 647V4 + 967V2 2Mtt - 10Mñ + 160M4 - З68М3 +816M2 - 576M

vi7 27V7 + l28Nh + 128 N* 2M7 - 12M* + 308Mft - 816M4 +1328M3 - 768M

m 2 N* + 2567VK + 2567V4 + 3847V2 2M* - 14M7 + 588Mfi - 1688M' +3216AÍ4 - 4256M3 +9152M2 - 6912M

Wcj 2 7V9 + 5127V7 + 5127V5 + 512 N* 2M9 - 16M* + 1128M7 -3376M6 + 7104M5 - 11200M4 +1267271Í3 + 12288M2 - 184327k

WW 2NW + 10247V* + 10247VK + 10247V4 + 15367V2 2Mw - 18M9 + 2184AT" - 66567 +14880M6 - 26432M5 + 360967Ü -35840M3 + 111360M2 - 952327

d 27V1U + 227V* + 228N* - 2327V4 2Мш - 18M9 4- 88M* - 188M7 +1254M6 + 1038JVÍ5 - 4948M4 -21832M3 + 60144M2 - 355207И

wn 2Nlí + 20487V9 + 20487V7 +20487V5 + 20487V3 2Mu - 20МШ + 4268M9 -13072M8 + 30240M7 - 58240714 +91008M5 - 110080M4 + 9753671 +290816M2 - 331776M

Наконец, в пятой главе речь идет об алгебре, порожденной всеми простыми графами по модулю 4-членных соотношений, введенной С. К. Ландо11.

В работе12 была введена важная характеристика хордовых диаграмм — ее граф пересечений. Пусть хорды «i, «2 € U принадлежат диаграмме D. Будем говорить, что щ и мг пересекаются, если их вершины чередуются при обходе окружности.

11S. К. Lando, On a Hopf Algebra in Graph Theory. Preprint, 1998, submitted to J. of Comb. Theory, Series B.

12S. V. Chmutov, S. V. Duzhin, S. K. Lando, Vas.nlte.v knot invariants I. Introduction, Advances in Soviet Math., 21 (1994) 117-12G.

Графом пересечений !,{П) хордовой диаграммы £> называется граф, вершины которого находятся во взаимно однозначном соответствии с ее хордами, и две вершины соединены ребром в том и только в том случае, если соответствующие им хорды «1, «2 £ V пересекаются.

Например, граф • ■ ■ соответствует хордовой диаграмме

Оказывается, что отображение £) м- л(2?) можно продолжить до гомоморфизма алгебр (даже биалгебр), если в пространстве, порожденном всеми простыми графами (т.е. неориентированными графами без петель и кратных ребер), ввести определенное семейство 4-членных соотношений и рассмотреть факторалгебру по этим соотношениям.

Пусть д — произвольный граф и — упорядоченная пара его вершин. Пара ?/., определяет два преобразования графа д: д м- д\т иди ди„. Оба графа д'п„ и дп„ имеют то же множество вершин, что д. Если вершины и, V соединены ребром в д, то граф д'п„ получается из д удалением ребра ?/.«; в противном случае д'т, получается из д добавлением ребра ни. Граф дп1, получается из д так. Рассмотрим все вершины ы £ У(д) \ {и, ?;}, соединенные ребром с вершиной V, тогда у графа дп„ вершины и и и! соединены в том и только в том случае, если они не соединены в д. Смежность всех остальных пар вершин в д и в дип одинакова.

Алгеброй Ландо С, мы будем называть факторалгебру биалге-бры графов по всем соотношениям

В §5.2 диссертации описывается программа, которая строит систему образующих алгебры £ и позволяет найти в явном виде матрицу гомоморфизма 1,:Т>—¥С. При помощи этой программы получены следующие результаты:

/ _~

9 ~ 9нп — 9ии - ди,г Вот пример такого соотношения:

V

1. Доказано, что образующие алгебры С до градуировки 7 можно выбрать в таком виде:

n dimPn

1 1

2 1 —.

3 1

4 2 И П

5 3 NLO.O

6 5 Ж п/ Г7 П ГХ

7 7 ^ ^ kU ' LJ UJ/ LK L

2. Доказано, что ядро гомоморфизма i: V —> £ до градуировки 7 одномерно и порождено элементом

d\ + <¿4 - 2d.*, - Ad7 + Мя

+2fl?9<ii8 - dyadic - <fndi8 + 2dxidn - Sd^dn

+(i14d16 - 4(ii5(ii6 + 4<if7<i16 4- - rfi7(il8,

Основные научные результаты диссертации опубликованы в следующих работах:

[1| А. И. Каишев, Координатные асимптотики решений од-номерн уравнения Дирака с осциллирующим потенциалом. Математические заметки, т. 37, вып. 3, 1985 г. 345-354.

[21 А. И. Каишев, Уточненная схема построения апостериорного интервального расширения элементарной функции. Вопросы кибернетики, ВК-149. Москва, 1989 г. 14-17.

[3] S. V. Duzhin, A. I. Kaishev. Calculation of central generators of the universal enveloping algebras and Vassiliev-Kontsevich weight systems. Proc. of International Workshop 'New Computer Technologies in Control Systems." Pereslavl-Zalessky, 1995, p. 13-14.

[4] С. В. Дужин, А. И. Каишев, С. В. Чмутов. Алгебра 3-графов. Труды Математического Института им. Стеклова РАН, т. 221, 1998 г., с. 168-196.

[5] С. В. Дужин, А. И. Каишев, Реализация в Т-системе программы вычисления si- и so-полиномов для 3-графов. - В сб. "Программные системы". М.: Наука 1999, стр. 214-223.

[6] А. И. Каишев, Программы и данные, расположенные, на анонимном ftp-сервере, ftp://math.botik.ru/pub/.

1 Комбинаторные объекты, связанные с инвариантами Васильева

1.1 Особые узлы и фильтрация Васильева.

1.2 Инварианты узлов

1.3 Алгебра хордовых диаграмм.

1.4 Алгебра диаграмм Фейнмана.

1.5 Алгебра 3-графов.

1.5.1 Умножение

1.5.2 Некоторые тождества.

1.5.3 Связные диаграммы Фейнмана и 3-графы.

2 Весовые системы со значениями в центре универсальной обертывающей алгебры

2.1 Универсальные обертывающие алгебры.

2.2 Алгоритм построения образующих центра.

2.3 Каноническое представление простых алгебр Ли.

2.3.1 Представление алгебр серии А.

2.3.2 Представление алгебр серии В.

2.3.3 Представление алгебр серии С.

2.3.4 Представление алгебр серии Б.

2.3.5 Представление алгебры С2.

2.4 Система программ для вычисления значений весовых систем

2.4.1 Реализация алгоритма построения образующих центра.

2.4.2 Структура РСЖМ-программ.

2.4.3 Вычисление значений весовой системы на хордовых диаграммах

2.5 Результат.

2.6 Выводы.

3 Структура алгебры 3-графов

3.1 Составление списка графов.

3.2 Выражение графов через образующие.

3.3 Вычисления.

3.4 Результаты.;

3.5 Выводы.

Алгебра 3-графов и алгебры Ли

4.1 Конструкция инварианта Кд.

4.2 Алгоритм вычисления и йо^-полиномов.

4.3 Переход к рекурсивному (параллельному) алгоритму.

4.4 Т-программа вычисления я/- и 5 о-полиномов.

4.5 Показатели эффективности распараллеливания Т-программы

4.6 Результат.

4.7 Выводы.

Алгебра графов Ландо

5.1 Конструкция алгебры Ландо.

5.2 Программа для вычислений в алгебре

Ландо.

5.3 Выражение графов через образующие.

5.4 Гомоморфизм алгебр 7 :£>—>■£.

5.5 Выводы.

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

Инварианты конечного типа, введенные московским математиком В.Васильевым в 1990 году, быстро завоевали широкое признание среди специалистов по теории узлов, и в течение 10 лет в мире вышло около 500 работ, посвященных исследованию инвариантов Васильева. Оказалось, что это понятие позволяет понять с единой точки зрения многие конструкции, введенные в топологии за последние 50 лет. В принципе, существует алгоритм, который дает явное описание всех инвариантов Васильева, но его суперэкспоненциальная сложность не позволяет продвинуться дальше степени 7. По этой причине особое значение имеют разного рода опосредованные алгоритмы, которые позволяют находить те или иные характеристики изучаемых объектов с помощью вспомогательных структур (хордовых диаграмм, алгебр Ли, графов и т.п.). Настоящая диссертация относится как раз к этому подходу. В ней описан разработанный автором пакет программ для исследования комбинаторно-алгебраических структур, возникающих в теории инвариантов Васильева.

Краткое содержание диссертации таково.

В первой главе мы излагаем основные определения и конструкции теории инвариантов Васильева, необходимые для понимания последующего материала. Это, в частности, введенное М. Концевичем понятие весовой системы как функции на алгебре хордовых диаграмм (см. [К], [ВШ]) и введенная С. К. Ландо ([Ьа]) конструкция алгебры графов с 4-членными соотношениями. Несколько подробнее изложена конструкция алгебры 3-графов Г, введенная в статье [сок].

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

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

• составление списка графов,

• нахождение полиномов, выражающих 3-графов через образующие,

• вычисление sl^- и волг-полиномов 3-графов.

Четвертая глава посвящена вычислению полиномиальных инвариантов 3-графов, связанных с алгебрами Ли sijv и son- В первом параграфе описана восходящая к Р. Пенроузу и М. Концевичу конструкцию, позволяющую по алгебре Ли 0 с заданной невырожденной ad-инвариантной билинейной формой В построить функцию Kg на множестве 3-графов, порождающую гомоморфизм алгебр Г —> R

Параграф 4.2 посвящен реализация алгоритма вычисления si- и so-полиномов. В тексте приведена соответствующая программа 1 на псевдокоде.

В параграфе 4.3 изложена параллельная версия алгоритма и ее реализация на языке t2cp в рамках системы автоматического динамического распараллеливания программ (Т-системы, [АА]).

В параграфе 4.5 приведены сведения, показывающие эффективность использования Т-системы для решения рассматриваемой задачи: почти линейное ускорение при увеличении числа процессоров.

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

Основные результаты диссертации, выносимые на захциту.

• Алгоритм нахождения образующих центра универсальных обертывающих алгебр для алгебр Ли серий А, В, С, D и особой алгебры G2 (см. 2.4).

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

• Усовершенствованный алгоритм генерации полного списка трехвалентных графов с данным числом вершин (параграф 3.1).

• Разработка и реализация алгоритма выражения 3-графов через образующие (см. параграф 3.2). Существенной его частью является алгоритм точного решения систем линейных уравнений специального вида (3.6), который позволил обрабатывать системы из десятков тысяч уравнений.

• В результате работы описанного программного комплекса найден линейный базис алгебры 3-графов и система мультипликативных образующих до градуировки 10. Эти значения приведены в таблицах 3.1 и 3.2. Имеющиеся в этих таблицах значения градуировки 11 получены в результате работы программ, рассматриваемых в следующей главе.

5 Выводы

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

• Разработка и реализация алгоритма нахождения образующих алгебры Ландо и выражения элементов этой алгебры через образующие.

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

• Установлено, что естественный гомоморфизм из алгебры хордовых диаграмм в алгебру Ландо является изоморфизмом до градуировки б, а в градуировке 7 представляет собой эпиморфизм с одномерным ядром.

1. Al. J. W. Alexander, Topological invariants of knots and links. Trans. Amer. Math. Soc. 30, (1928), 275-306.

2. A. V. I. Arnold, Vassiliev's theory of discriminants and knots, Plenary lecture at the first European Congress of Mathematicians, Paris, July 1992.

3. BN1. D. Bar-Natan, On the Vassiliev knot invariants, Topology, 34 (1995) 423472.

4. BN2. D. Bar-Natan, Lie algebras and the four color theorem, Arhus University preprint, August 1995, and q-alg/9606016 preprint, June 1996. To appear in Combinatorica.

5. BN3. D. Bar-Natan, Some computations related to Vassiliev invariants. http://www.ma.huj i.ac.il/ drorbn/papers/table.dvi.

6. BN4. D. Bar-Natan, Bibliography of Vassiliev Invariants. Web publication http://www.ma.huj i.ac.il/ drorbn/VasBib/VasBib.html.

7. BG. D. Bar-Natan, S. Garoufalidis, On the Melvin-Morton-Rozansky conjecture Invent. Math. 125 (1996) 103-133.

8. B. J. Birman, New points of view in knot theory, Bull. Amer. Math. Soc. 28, (1993), 253-287.

9. BL. J. Birman and X.-S.Lin, Knot polynomials and Vassiliev invariants, Invent. Math. Ill, (1993), 225-270.

10. BDM. B. McKay, Nauty: a program for computing automorphism groups of graphs, http://cs.anu.edu.au/people/bdm/nauty/.

11. Bou. H. Бурбаки, Группы и алгебры Ли. Главы 1-3. М.: Мир, 1976. Главы 4-6. М.: Мир, 1972. Главы 7-8. М.: Мир, 1978.

12. CD1. S. V. Chmutov, S. V. Duzhin, An upper bound for the number of Vassiliev knot invariants, Journal of Knot Theory and its Ramifications, 3 (1994) 141-151.

13. CD2. S. V. Chmutov, S. V. Duzhin, A lower bound for the number of Fas-siliev knot invariants, Preprint, 21 pp., available as PostScript file at ftp://pier.botik.ru:/pub/local/zmr/lb.ps.gz.

14. CD3. S. Chmutov, S. Duzhin, The Kontsevich integral. Preprint of MaxPlanck-Institut für Mathematik (Bonn, August 1997); 27 pp., available as PostScript file at ftp://pier.botik.ru:/pub/local/zmr/ki.ps.gz.

15. CDK. С. В. Дужин, А. И. Каишев, С. В. Чмутов, Алгебра 3-графов. Труды Математического Института им. Стеклова РАН, т. 221, 1998 г. 168-196

16. CDU. S. V. Chmutov, S. V. Duzhin, S. К. Lando, Vassiliev knot invariants I. Introduction, Advances in Soviet Math., 21 (1994) 117-126.

17. CDL2. S. V. Chmutov, S. V. Duzhin, S. K. Lando, Vassiliev knot invariants II. Intersection Graph Conjecture for Trees, Advances in Soviet Math., 21 (1994) 127-134.

18. CDL3. S. V. Chmutov, S. V. Duzhin, S. K. Lando, Vassiliev knot invariants III. Forest Algebra and Weighted Graphs, Advances in Soviet Math., 21 (1994) 135-145.

19. CV. S. Chmutov, A. Varchenko, Remarks on the Vassiliev knot invariants coming from sl2i Topology 36 (1997) 153-178.

20. C. J. H. Conway, An enumeration of knots and links and some of their algebraic properties. Computational Problems in Abstract Algebra (J.Leech, ed.), Pergamon Press, New York, 1970, 329-358.

21. Das. O. Dasbach, Private communication, July 1997.

22. DK1. С. В. Дужин, А. И. Каишев, Реализация в Т-системе программы вычисления si- и so-полиномов для 3-графов. В сб. 'Программные системы". М.: Наука 1999, стр. 214-223.

23. Ftp. А. И. Каишев, Программы и данные, расположенные на анонимном ftp-cepeepe. ftp: //math. botik. ru/pub/a3g.

24. Kal. А. И. Каишев, Координатные асимптотики решений одномерного уравнения Дирака с осциллирующим потенциалом. Математические заметки, т. 37, вып. 3, 1985 г. 345-354.

25. Ка2. А. И. Каишев, Уточненная схема построения апостериорного интервального расширения элементарной функции. Вопросы кибернетики, ВК-149. Москва, 1989 г. 14-17.

26. Kn. J. Kneissler, The number of primitive Vassiliev invariants up to degree twelve. Preprint q-alg 9706022, also available at http://rhein.iam.uni-bonn.de/ jk/, June 1996.

27. К. M. Kontsevich, Vassiliev's knot invariants, Adv. in Soviet Math., vol. 16, Part 2, pp. 137-150, 1993.

28. Коп. M. Kontsevich, Feynman diagrams and low-dimensional topology, First European Congress of Mathematics II 97-121, Birkhauser, Basel 1994.

29. MM. J. Milnor, J. Moore, On the structure of Hopf algebras, Ann. Math. 81 (1965), 211-264.

30. Pen. R. Penrose, Applications of negative dimensional tensors, In: Combinatorial mathematics and its applications (ed. D. J. A. Welsh), New York, London: Academic Press, 1971.

31. Pont. JI. С. Понтрягин, Непрерывные группы. M.: Наука. 1984

32. PS. В. В. Прасолов, А. Б. Сосинский, Узлы и маломерная топология, специальный семинар, изд-во МК НМУ, 1993.

33. Ro. D. Rolfsen, Knots and Links. Publish or Perish, 1976.

34. Cub. G. Royle. WWW-page containing tables of S-graphs, October 1996. http://www.cs.uwa.edu.au/~gordon/remote/cubics/.

35. S. A. B. Sossinsky, Feynman diagrams and Vassiliev invariants. IHES preprint, Paris, February 1992.

36. W. T. Tutte, A ring in graph theory, Proc. Cambridge Phil. Soc. 43 (1947), 26-40. Reprinted in Selected Papers of W. T. Tutte, Vol. 1, The Charles Babbage Research Center, Manitoba, Canada, 1979.

37. V. A. Vassiliev, Cohomology of knot spaces, Theory of Singularities and Its Applications (ed. V. I. Arnold), Advances in Soviet Math., 1 (1990) 23-69.

38. В.А.Васильев, Топология дополнений к дискриминантам, M., Фазис, 1997, 536 стр.

39. J. A. M. Vermaseren. Computer algebraic system FORM. User's manual. ftp.nikhef.nl:/pub/form/manual/form.dvi.

40. P. Vogel, Algebraic structures on modules of diagrams, Institut de Mathématiques de Jussieu, Prépublication 32, August 1995, 45 pages.