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

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

ПОДБЕРЕЗИНА Елена Ивановна

АБЕЛЕВЫ ГРУППЫ КАК АРТИНОВЫ

ИЛИ НЁТЕРОВЫ МОДУЛИ НАД КОЛЬЦАМИ ЭНДОМОРФИЗМОВ

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

АВТОРЕФЕРАТ

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

Москва 1997

Работа выполнена на кафедре алгебры Томского государственного университета.

Научный руководитель:

доктор физико-математических наук, профессор КРЫЛОВ ПА.

Официальные оппоненты:

доктор физико-математических наук, профессор МИХАЛЁВ A.B.

кандидат физико-математических наук, доцент КОМПАНЦЕВА Е.И.

Ведущая организация - Институт математики СО РАН.

Защита состоится «. 199.Х г. в ....{£.... часов

на заседании диссертационного Совета К 053.01.02 в Московском педагогическом государственном университете по адресу: 107140, Москва, Краснопрудная ул., д. 14, математический факультет, ауд. 301.

С диссертацией можно ознакомиться в библиотеке МПГУ по адресу: 119435, Москва, Малая Пироговская ул., д. 1.

Автореферат разослан

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

КАРАСЕВГА

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

АКТУАЛЬНОСТЬ ТЕМЫ. Настоящая работа относится к теории абеле-вых групп и их колец эндоморфизмов - быстро развивающегося раздела алгебры.

Каждой абелевой группе (модулю) А можно сопоставить ассоциативное кольцо с единицей Е(А) всех её эндоморфизмов. Это кольцо несёт определённую информацию о самой группе А . Основную задачу, относящуюся к кольцам эндоморфизмов, можно сформулировать так. Найти по возможности точные соотношения между свойствами группы А и свойствами кольца Е(А) . Истоки теории колец эндоморфизмов лежат в теории линейных преобразований векторных пространств. Важную роль в становлении теории колец эндоморфизмов сыграла книга Бэра [1]. В двухтомной монографии Фукса [2], [3] кольца эндоморфизмов рассматриваются в главе XV . В работе [4] освещены многие результаты о кольцах эндоморфизмов абелевых групп. Основы теории колец эндоморфизмов абелевых групп заложены Бэром, Капланс-ким, Селе, Фуксом, Пирсом, Корнером, Ричменом, Уокером. Кольца эндоморфизмов абелевых групп широко изучаются с различных точек зрения.

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

Двумя важнейшими направлениями в теории колец эндоморфизмов являются рассмотрение групп как модулей над их кольцами эндоморфизмов и изучение групп с кольцами эндоморфизмов специального вида (последнее направление называется также " кольцевые свойства колец эндоморфизмов ")• С достижениями по этому кругу задач можно ознакомиться по обзору [4].

Начало систематическому изучению групп как модулей над их кольцами эндоморфизмов было, наверно, положено работами Ричмена и Уокера [5], Дугласа и Фарахата [6].

Программа исследования колец эндоморфизмов со специальными свойствами была предложена Селе. Она привлекает большое внимание специалистов. Актуальность этого направления подчёркивает постановка проблемы 84 в книге [3]. Ему посвящены §§ 111, 112 этой книги. Имеется в виду следующее. Для некоторого употребительного кольцевого свойства описать абелевы группы, кольца эндоморфизмов которых обладают этим свойством.

В данной работе исследуются абелевы группы, являющиеся арти-новыми или нётеровыми модулями над своими кольцами эндоморфизмов. Рассматриваются также группы с нётеровыми кольцами эндоморфизмов. Артиновы и нётеровы кольца и модули играют исключительно важную роль в теории колец и модулей (см. Ламбек [ 7, §§ 1.4, 3.5], Каш [ 8, гл. 6]). Артиновость или нётеровость модуля представляют по существу некоторые условия конечности.

АбелеЕЫ группы как нётеровы модули над кольцами эндоморфизмов изучались Рейдом [9] и Парасом [10]. В §111 книги СЗ] дано описание абелевых групп, кольца эндоморфизмов которых являются телами, простыми или артиновыми кольцами. Там же характеризуются периодические группы с нётеровыми кольцами эндоморфизмов.

В целях достижения максимальной общности в значительной части работы рассматривается вопрос о том, когда группа гомоморфизмов Нош(А,В) является артиновым или нётеровым модулем над кольцом эндоморфизмов Е(В) группы В или Е(А) группы А . Имеется в виду, что группа Нош(А,В) стандартным способом превращается в левый Е(В)-модуль и в правый Е(А)-модуль. Хорошо известно, что существует естественный изоморфизм левых Е(В)-модулей Hom(Z,B) = В, где группа В также рассматривается как левый Е(В)-модуль. Поскольку далее Нош(А,А) = Е(А) , то еидим, что исследование группы Нот(А,В) как левого Е(В)-модуля и правого Е(А)-модуля действительно включает изучение групп как модулей над их кольцами эндоморфизмов и изучение групп с кольцами эндоморфизмов специального вида.

ЦЕЛЬ РАБОТЫ. Изучение абелевых групп, являющихся артиновыми или нётеровыми модулями над своими кольцами эндоморфизмов. Исследование абелевых групп А и В таких, что Нош(А,В) есть арти-нов или нётеров модуль над кольцом эндоморфизмов Е(В) группы В или кольцом эндоморфизмов Е(А) группы А . Изучение абелевых групп с нётеровыми кольцами эндоморфизмов.

МЕТОДЫ ИССЛЕДОВАНИЯ. В диссертации используются методы теории абелевых групп и модулей.

НАУЧНАЯ НОВИЗНА. Все результаты диссертации являются новыми. Основными результатами можно считать следующие:

1) описаны абелевы группы А, являющиеся артиновыми Е(А)-модулями; аналогичная задача для нётеровости сведена к случаю группы А без кручения;

2) описаны абелевы группы А и В такие, что группа гомоморфизмов Нош(А,В) является артиновым модулем над кольцом эндоморфизмов Е(В) группы В или кольцом эндоморфизмов Е(А) группы А ;

3) охарактеризованы абелевы группы А и В , для которых Horn(А,В) есть нётеров Е(В)-модуль или Е(А)-модуль;

4) описаны сепарабельные группы без кручения с нётеровыми слева или справа кольцами эндоморфизмов; подобная проблема для смешанных групп сведена к случаю групп без кручения.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Работа имеет теоретическое значение. Результаты данной работы могут быть использованы при изучении абелевых групп, групп гомоморфизмов абелевых групп, групп как модулей над своими кольцами эндоморфизмов, кольцевых свойств колец эндоморфизмов, могут применяться при решении аналогичных задач в теории модулей и других алгебраических структурах.

АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертации были представлены на III международной конференции по алгебре (Красноярск, 1993), на международной алгебраической конференции (Санкт-Петербург, 1997), докладывались и обсуждались на симпозиуме "Абелевы группы", посвященном 80-летию Л.Я. Куликова (Бийск, 1994), на международной конференции "Всесибирские чтения по математике и механике" (Томск, 1997), на алгебраических семинарах Томского государственного университета.

ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 работ, список которых приведён в конце автореферата [1-8].

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

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИИ. Диссертация состоит из введения, трёх глав и списка литературы, включающего 29 наименований. Полный объём диссертации 106 страниц машинописного текста.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

ТЕОРЕМА 2.2. 1) Группа А эндоартинова тогда и только тогда, когда А = В ® D , где В - ограниченная группа , D - делимая группа с конечным числом ненулевых р-компонент.

2) Группа А эндонётерова тогда и только тогда, когда А = = В © С , где В - ограниченная группа , а С - эндонётерова группа без кручения.

Получена характеризация групп А и В таких, что левый Е(В)-модуль Нош(А,В) артинов. Проблема характеризации групп А и В , для которых Нот(А,В) - артинов Е(А)-модуль, сведена к случаю, когда группа А не имеет кручения, а группа В является одной из следующих групп: Z(p) , Z(p°°) , Q .

Пусть А и В - группы. Положим

Sa(B) = L ciA , Kb (А) = П kerot , ci:A-*B й: А-*В

А = А / К . Подгруппа S называется следом группы А в группе В.

Фактор-группа А - кослед группы В в группе А .

Указаны также некоторые более точные соотношения между следом S , коследом А и группами А , В в ситуации, когда Е(В),-модуль Нош(А,В) .артинов; в частности, приведены некоторые общие условия, при которых след S выделяется в группе В прямым слагаемым. Кроме того, сделаны некоторые выводы о строении следа S и косле-

да А а также групп А и В , если Нсяп(А,В) - артинов Е(А)-модуль.

Будем говорить, что простое число р относится к какой-то группе, если р-компонента этой группы отлична от нуля.

Приведём основные результаты первой главы. Ниже r(G) обозна-

rl

- r ~

чает ранг группы G , rp(G) - её р-ранг, т.е. rp(G) = r(G / pG).

ТЕОРЕМА 3.9. Пусть А и В - некоторые группы. Левый Е(В)-модуль Нош(А,В) артинов тогда и только тогда, когда

S = D®£®QeC , Tl

где D - делимая периодическая группа с конечным числом • р-компонент; С - ограниченная группа; Т1 - некоторый кардинал, а

A = H®L®Q®G , m

где Н - конечная группа; G - редуцированная группа без кручения; ш £ N и для всякого р , относящегося к группе С , редуцированная р-компонента группы В ограничена.

Причём : а) если D * 0 , то А = Н ® G , r(G) < « и r(G) = = rp(G) для всех р , относящихся к группе D ;

b) если D = 0 , но Е® Q * 0 , то r(G) < °° ;

Т1

c) наконец, если S - ограниченная группа, т.е. S =

= С,то A = H©G и для любого р , относящегося к S , rp(G) < « .

В следующей теореме Т - периодическая часть, a D - делимая часть группы А. Проблема характеризации артинова правого Е(А)-модуля Нош(А,В) оказывается, как показывает следующая теорема, более сложной. Это неудивительно, так как нет даже описания группы А без кручения, для которой Е(А)-модуль Hom(A,Z(p)) неприводим. В работе приводится несколько интересных примеров по этому поводу. Например, если А - свободная группа, то указанный модуль неприводим.

ТЕОРЕМА 4.5. Пусть А и В - некоторые группы. Е(А)-модуль Ногп(А,В) артинов тогда и только тогда, когда след S равен прямой сумме конечной группы и делимой группы конечного ранга; для каждого р , относящегося к группе В , редуцированная р-компо-нента группы А ограничена, группы А и В не содержат одновременно групп Z(p°°) ; Е(А)-модуль Нош(А / Т, Z(p)) артинов, если р относится к следу S , Е(А)-модуль Horn(А / Т, Z(pOT)) артинов, если в следе S содержится группа Z(p°°) и, наконец, Е(А)-модуль Horn (А / (Т + D), Q) артинов, если в следе S содержится группа Q .

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

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

Во второй главе группа Нош(А,В) изучается как нётеров модуль над кольцами эндоморфизмов групп В или А .

Проблема описания произвольных групп А и В , для которых левый Е(В)-модуль Нош(А.В) нётеров, в определённом смысле сводится к случаям циклической группы А простого порядка и групп А и В без кручения. Описание групп А и В таких, что правый Е(А)-модуль Нот(А,В) нётеров, сведено к случаям, когда группы А и В не имеют кручения и редуцированная р-компонента группы А не ограничена хотя бы для одного р , относящегося к следу группы А в группе В . Глава содержит следствия и частные случаи всех основных результатов работы.

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

ТЕОРЕМА 5.7. Пусть А и В - группы. Е(В)-модуль Нот(А,В) нётеров тогда и только тогда, когда _ m

(*) A = H©E®Q©E® Zip") © G ,

n j-1 з

где m,n e N , H - конечная группа, G - редуцированная группа без кручения,

(**) S = CffiE®QffiE®Dp©G' ,

И i=1 1

где С - ограниченная группа, DPl - делимая pi-компонента группы S , G' - редуцированная группа без кручения , П - некоторый кардинал; для любого р , относящегося к группе Н , Е(В)-модуль Hom(Z(p),B) нётеров, причём :

а) если к / 0 , то

_ m

(1) А = Н Z(p") ,

К*,

(2) S = С © Е® Dp ;

1=1

б) если к = 0 , но Т1 / 0 , то

A = H©E®Q©G п

- 9 -

(4) Б = С © Е® 0 © й' ,

П

где г(Б) < <я и Е(В)-модуль НошСй, Б / М) нётеров, где М =

= С ® Е® Ч ; П

в) если к = и = 0 , то

(5) А = Н © в ,

(6) Б = С Ф б',

для любого р , относящегося к группе Б , гр(й) < «> и Е(В)-модуль Нот(В, Б / С) нётеров.

Справедлив канонический изоморфизм Е(В)-модулей Нош(2(р),В) = = ВСр] , где ВСр] = { Ь е В | рЬ = СМ . В связи с теоремой 5.7 возникает задача о нётеровости нижнего слоя ВСр] как Е(В)-моду-ля. Если обе группы А и В не имеют кручения, то в вопросе о нётеровости £(В)-модуля Нош(А,В) (также вытекающем из теоремы) можно лишь надеяться на некоторые частичные результаты. Действительно, даже класс эндонётеровых групп необозрим.

ТЕОРЕМА 6.7. Пусть А и В - некоторые группы и пусть редуцированная р-компонента группы А ограничена для любого р , относящегося к следу Б группы А в группе В . Е(А)-модуль Нош(А,В) нётеров тогда и только тогда, когда

(1) ЬЕ®0р

1-1 1 п

(2) Б - гер00) Ф 2® ч Ф Н © б' ,

1-1 1 ш

где п,ш в N , Т1 - некоторый кардинал, 0Р1 - делимая р^-компонента группы А , С - ограниченная группа, Н - конечная группа, Б и в' - редуцированные группы без кручения, причём: а) если п * О , то

_ п

(3) А = £®ПР © С © б ,

1-1 1

Б = Е® г(р") ® г? о © Н © 5 1-1 1 ш

и Е (А)-модуль Нот (А / М, S) , где М Dp^ ©С , нётеров;

б) если п = 0 , но ш * 0 , то

(5) A = E®Q©C©G,

U

(6) S = Q © Н © G'

ш

и Е(А)-модуль Нош(А / L, S) , где L = Е® Q ® С , нётеров;

U

в) если п = ш = 0 , то есть если

(7) S = Н © G' , то

(8) А = С © G

и Е(А)-модуль Нот(А / С, S) нётеров.

Вторая глава содержит много и других следствий теорем 3.9, 4.5, 5.7, 6.7 (условия нётеровости модуля Нош(А,В) для конкретных классов групп А и В , одновременной артиновости и нётеровости Е(А)-модуля (или Е(В)-модуля) Нош(А,В)) .

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

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

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

ТЕОРЕМА 7.3. Пусть А - смешанная группа. Кольцо Е(А) нёте-рово слева тогда и только тогда, когда А = Т © G , где Т - конечная группа, G - группа без кручения такая, что кольцо E(G) нётерово слева и для любого р , относящегося к группе Т , rp(G) < 00 .

Записанную теорему нельзя улучшить, поскольку описание групп без кручения с нётеровыми как слева, так и справа кольцами эндоморфизмов недостижимо. Отметим,что изучение смешанных групп с нётеровыми кольцами эндоморфизмов тесно связано с изучением группы Hom(G,T) как нётерова модуля над кольцами эндоморфизмов групп G и Т . Здесь G - редуцированная группа без кручения, Т - прямая сум-

- 11 -

ма конечного числа коциклических групп.

В §8 получено описание сепарабельных групп без кручения с нё-теровыми слева (справа) кольцами эндоморфизмов.

ТЕОРЕМА 8.3. Кольцо эндоморфизмов сепарабельной группы без кручения G нётерово справа тогда и только тогда, когда G является вполне разложимой группой конечного ранга и типы её однородных компонент попарно несравнимы.

ТЕОРЕМА 8.7. Пусть G - сепарабельная группа без кручения. Кольцо E(G) нётерово слева тогда и только тогда, когда группа G является вполне разложимой группой конечного ранга и типы её различных однородных компонент или несравнимы, или сравнимы за счёт бесконечностей.

В процессе доказательства теорем 8.3 и 8.7 группа Нош(А,В) , где А и В - группы без кручения ранга 1 , исследуется как нётеров Е(В)-модуль или Е(А)-модуль.

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

ЦИТИРОВАННАЯ ЛИТЕРАТУРА

1. Бэр Р. Линейная алгебра и проективная геометрия. М.: ИЛ, 1955.

2. Фукс Л. Бесконечные абелевы группы. М.: Мир, 1974. Т. 1.

3. Фукс Л. Бесконечные абелевы группы. М.: Мир, 1977. Т. 2.

4. Марков В.Т., Михалев А.В., Скорняков Л.А., Туганбаев А.А. Кольца эндоморфизмов модулей и структуры подмодулей. В кн.: Итоги науки и техники. Алгебра. Топология. Геометрия. 1983. Т. 21. С. 183-254.

5. Richman F., Walker Е. Primary abelian groups as modules over their endomorphism rings//Math. Z. 1965. V. 89. P. 77-81.

6. Douglas A.J., Farahat H.K. The homological dimension of an

abelian group as a mogule over its ring of endomorphism // Mo-natsh. Math. 1965. V.69. P. 294-305.

7. Ламбек И. Кольца и модули. М.: Мир, 1971.

8. Каш Ф. Модули и кольца. М.: Мир, 1981.

9. Reid J.D. Abelian groups finitely generated over their endomorphism rings // Lecture Notes Math. 1981, Y. 874. P. 41-52.

10. Paras A.T. Abelian groups as Noetherian modules over their endomorphism rings // Contem. Math. 1994. V. 171. P. 325-332.

1. Подберезина Е.И. Строение сепарабельных абелевых групп без кручения с нётеровыми кольцами эндоморфизмов. // Абелевы группы и модули. Томск: Иэд-во Том. ун-та, 1990. Вып.9. С. 77-83.

2. Крылов П.А., Подберезина Е.И. Строение смешанных абелевых групп с нётеровыми кольцами эндоморфизмов // Абелевы группы и модули. Томск: Изд-во Том. ун-та, 1994. Вып. 11,12. С.121-129.

3. Крылов П.А., Подберезина Е.И. Группа Нот(А,В) как арти-нов Е(В)-модуль // III межд. конф. по алгебре: Сборник тезисов. Красноярск: Изд-во Краен, ун-та, 1993. С. 187-188.

4. Подберезина Е.И. Об артиновости Е(А)-модуля Нот(А,В) // Симпозиум Абелевы группы : Тезисы выступлений участников. Бийск: НИЦ Би ГВД, 1994. С. 22-23.

5. Крылов П.А., Подберезина Е.И. Группа Нот(А.В) как арти-нов Е(В)-модуль // Абелевы группы и модули. Томск : Изд-во Том. ун-та, 1996. Выл.13,14. С.170-184.

6. Подберезина Е.И. Об артиновости Е(А)-модуля Нош(А,В) // Абелевы группы и модули. Томск: Изд-во Том. ун-та, 1996. Вып. 13,14. С. 190-199.

7. Подберезина Е.И. Абелевы группы как нётеровы модули над кольцами эндоморфизмов // Межд. конф. " Всесибирские чтения по математике и механике " : Тезисы докладов. Т.1. Математика. Томск: Изд-во Том. ун-та, 1997. С. 36-37.

8. Подберезина Е.И. Абелевы группы как нётеровы модули над кольцами эндоморфизмов // Межд. алгебр, конф. : Сборник тезисов. СПб., 1997. С. 257-258.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Формальные языки — подмножества свободной полугруппы Л+ над заданным (как правило, конечным) алфавитом А — тесно связаны с полугрупповыми конгруенциями. Теория формальных языков, сложившаяся в течение последних сорока лет, насчитывает немало ярких результатов в этом направлении. Отметим, например, что рациональные (регулярные) языки суть в точности объединения классов конгруенций конечного индекса на А+ .

Для языка, являющегося классом вполне инвариантной конгру-енции на А+ , в [1] был предложен термин эквационалъный. Эквацио-нальные языки возникают естественным образом при исследовании многообразий полугрупп. А именно, полугрупповому многообразию 23 соответствует вполне инвариантная конгруенция на А+ , фактор по которой есть свободная в 91 полугруппа. Отметим такой важный результат: усилиями ряда авторов в конце 80-х — начале 90-х годов было показано, что в свободных полугруппах многообразий уаг{хт=хт+" | т>3, п>1} разрешима проблема равенства, а соответствующие эквациональные языки являются рациональными (в окончательном виде этот результат приведен в [2],[3]).

Эквациональные языки, соответствующие 0-приведенным многообразиям полугрупп (т.е. многообразиям вида var{W¡=0 | г£/}), либо одноэлементны, либо являются вполне инвариантными идеалами полугруппы А+ . Вполне инвариантные идеалы, в свою очередь, составляют очень важный класс языков с точки зрения отношения избегаемости.

Попятно избегаемости, появившееся па рубеже ТО-вО-х годов в комбинаторике слов ([4],[5]), оказало мощное влияние на развитие теории формальных языков. Напомним, что слово {/ избегает слово V, если среди подслов {/ нет гомоморфных образов V. Далее, язык Ь избегает язык Л, если каждое слово из Ь избегает все слова из Л. Слово (язык) называется к-избегаемым, если его избегает некоторый бесконечный язык в ¿-буквенном алфавите. Языки, избегающие некоторые наиболее простые слова и множества слов, привлекают внимание исследователей на протяжении всего нашего века, а в 80-90-е годы наблюдается новый всплеск интереса к ним. Таковы, например, язык БР тернарных бесквадратных слов (т.е. слов, избегающих слово ж2), язык СР бинарных бескубных слов (слов, избегающих слово ж3), язык ОР бинарных сильно бескубных слов (слов, избегающих множество {х3, хухух}).

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

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

С языком Ь 6 А+ тесно связаны такие языки над А, как

• теоретико-множественное дополнение Ь (Ь), которое, в частности, имеет общую с Ь синтаксическую конгруенцию;

• наибольший язык, избегаемый Ь (£"*);

• наибольший язык, избегающий

Нетрудно показать, что — вполне инвариантный идеал в Л+, т.е. эквациональный язык, а = Ь~~*. Кроме того, языки

вида Ь~"~ (соответственно ) образуют систему замыканий на множестве А+, порождаемую оператором замыкания ) (соответственно ' "). Следовательно, языки этих двух видов можно рассматривать как канонические (с точки зрения теории избегаемости), что повышает значимость их исследования.

Таким образом, наряду с языками СР и ОР мы рассматриваем языки СР и ОР (нетрудно видеть, что С Г= С/1, О/1-* = ОР).

Важное подмножество в языке ОР составляет язык ТМ, порождаемый широко известными в комбинаторике словами Туэ-Морса. Пусть А = {а, 6}, ф — эндоморфизм полугруппы , определяемый равенствами

ф(а) = аЬ, ф(Ь) = Ьа Слова Туэ-Морса 1/п и Уп (п > 0) определяются следующим образом:

ип =Р/»п(а), К, = фп(Ь) Язык ТМ состоит из слов Туэ-Морса и всех их подслов. Вместе с языком ТМ мы исследуем языки ТМ ,ТМ~~ и ТМ~"~ .

Напомним, что число р > 0 называется периодом слова IV, если г'-ая буква в XV совпадает с (г + р)-ой для всех г, для которых обе такие буквы в V/ есть. Экспонентной IV называется число

ехр(УУ) = Щ)/рег{\¥),

где ¡(IV) —длина слова IV, а рег(\¥) —его минимальный период. При работе с понятием избегаемости удобно также определить па-следственную экспоненту слова V/ (Ьехр(\У)):

кехр( И7) = тах{ехр(У)| V — подслово в И^}. Будем говорить, что данное слово \У избегает экспоненту (3, если ксхр{\У)<Р. В частности, если /3 — целое число, то IV избегает экспоненту (3 тогда и только тогда, когда оно избегает слово х^.

В терминах экспонент получаем СР — Ь.ехр(\У)<3} ,

ОР = {1У£А+| кехр(\¥)<2} . В диссертации рассматриваются также языки вида Ьр = {И/£Л+| Ь.ехр{И^)</?, 2</?<3}, которые составляют важные подмножества в языке CF.

В диссертации применяются три основных подхода к изучению упомянутых языков. Первый подход — структурный — состоит в изучении комбинаторных свойств этих языков и взаимосвязей между ними. Второй подход предусматривает изучение производных объектов — синтаксических конгруенций и синтаксических полугрупп данных языков. Наконец, третий подход, предельный, состоит в изучении соответствующих этим языкам множеств 2-слов (бесконечных цепочек алфавитных символов, индексированных целыми числами). Результаты, достигнутые в рамках каждого подхода, естественно составляют главы диссертации.

Диссертация состоит из введения, трех глав, разделенных на 10 параграфов, и содержит 8 теорем. Общий объем диссертации составляет 107 страниц. Библиография содержит 43 наименования. Нумерация параграфов сквозная; в нумерации утверждений используются номера глав.

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

Основные результаты работы докладывались на международных конференциях "Полугруппы и их приложения, включая полугрупповые кольца" (С-Петербург, 1995), "Интеллектуальные системы и компьютерные науки" (Москва, 1996), международной алгебраической конференции памяти Д.К.Фаддеева (С-Петербург, 1997) и научных семинарах "Алгоритмические вопросы алгебры" (МГУ), "Алгебра и логика" (НГУ), "Алгебраические системы" (УрГУ) и "Дискретная математика" (УрГУ). Результаты опубликованы в работах [10]—[15].

Первая глава диссертации (§§1-4) посвящена изучению структурных свойств сильно бескубных слов и слов Туэ-Морса. Основными ее результатами являются теорема декомпозиции сильно бескубных слов, устанавливающая точную числовую меру близости сильно бескубных слов к словам Туэ-Морса, и теорема избегаемое™, в которой в явном виде найден язык ТМ~* .

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

Предложения 1.1 и 1.2 показывают, что морфизм Туэ-Морса сохраняет экспоненты и наследственные экспоненты слов в максимально возможном для двухбуквенного алфавита диапазоне.

Предложение 1.1. Пусть Ш £Е А+ и ехр(\№) > 1. Тогда ехр{ф{Ш)) = ехр{\¥).

Предложение 1.2. Пусть £ А+ и кехр(\У) > 2. Тогда 11ехр(ф(Ш)) = Нехр(\¥).

Экспоненты всех сильно бескубных слов (в том числе, элементов языка ТМ), не превосходят двух; естественно предположить, что существуют достаточно жесткие ограничения на квадраты — слова экспоненты 2 — принадлежащие О.Р и ТМ. В Предложении 1.4 доказывается, что условие ХХеОР влечет 1(Х)=2* либо 1(Х)=3-2к (для подходящего к), а в Предложении 1.5 показано, что в случае ХХ£ТМ еще выполняются существенные ограничения на вид слова X и его размещение внутри слова Туэ-Морса.

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

И' =

где 1(с),1(с1) < 1, а каждое из слов С}{ равно аЬ или Ьа. Слова с таким свойством в диссертации'названы равномерными; к равномерному слову IV нужно прибавить не более, чем по одной букве в начало и конец, чтобы получить слово вида ф{11). Это свойство равномерных слов послужило основой для алгоритма обработки сильно бескубных слов, приведенного в §2 и играющего важную роль в доказательстве ряда теорем.

б

Алгоритм А. (Преобразует сильно бескубное слово IV в слово \РА).

Шаг 0, Положить \Уп = IV, к = 0.

Шаг 1. Если 6а} или И^. неравномерно, то положил,

IVд = И4 и остановиться.

Шаг 2. Положить = к = к + 1; вернуться на Шаг

1.

(Через ^(И^-) здесь обозначено минимальное слово вида Ф{и), содержащее равномерное слово И^.).

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

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

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

Теорема 1.1. Произвольное сильно бескубное слово \\г может быть представлено в виде IV — XV Z , где

1) У етм ;

2) X, Я £ А* и выполнены ограничения

1(Х)<1( И/)/4, 1{г) < /(ио/4, ¡(Х) + 1(г) < з-/(ио/ю.

Доказательство теоремы опирается на Алгоритм А. Данная теорема оказывается достаточно сильным утверждением; в частности, из нее немедленно следуют два известных и важных результата.

Следствие 1.1 ([7]). Всякое подслово сильно бескубного 2-слова принадлежит ТМ.

Следствие 1.2 ([8]). Множество эндоморфизмов полугруппы Л+ , сохраняющих язык ОГ, исчерпывается отображениями вида Оф" ,

где 0 —- лшо.мо/к/нгш полугруппы А+, ф — морфпзм Туэ-Морса, а и > 0 .

Последний, четвертый параграф нерпой главы посвящен нахождению языка ТМ~~. Для удобства, язык ТМ~* рассматривается как язык над другим двухбуквенным алфавитом £ = {х, у}. Морфизм Туэ-Морса, заданный на полугруппе , обозначается той же самой буквой ф. Основным результатом является следующая теорема.

Теорема 1.2. Язык ТМ" совпадает со вполне инвариантным идеалом I полугруппы , порожденным множеством

М - {гаг, хухуг, ххухху, хуухуу, Бк (А- > 1), т,п (т > 2)},

где

Г,и = 1ф~1*)ФтШтПФтШф~1*), "» > о-

В доказательстве теоремы опять существенно используется Алгоритм А.

При помощи Теоремы 1.2 доказывается равенство

{ТМ")" - ТМ и {ааЬаа, ЬЬаЬЬ},

демонстрирующее, насколько язык ТМ близок к замкнутому (в смысле упомянутой выше системы замыканий на А+). Отметим одно важное следствие.

Следствие 1.4. Всякий вполне инвариантный идеал в А+ , строго содержащий ТМ" , кофпнптен.

Вторая глава диссертации посвящена изучению синтаксических конгруенций и синтаксических полугрупп исследуемых языков. Напомним, что синтаксическая конгруенция тг[, языка Ь С А+ определяется следующим образом:

^ = {{и, V) е у1+ х.4+1 ур,дел+и{л> (РиоеЬ) (руя^ь)}.

Через А здесь обозначено пустое слово. Конгруенция лявляется наибольшей, для которой Ь является объединением классов. Факторполугруппа А+ /ттс называется синтаксической полугруппой языка Ь. Синтаксические полугруппы языка и его дополнения, очевидно, совпадают.

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

Предложение 2.1. Синтаксическая конгруеиция языка ТМ совпадает с рисовской конгруенцнеП по идеалу ТМ.

Как мы уже отмечали, язык ТМ отличается от эквационалыюго языка ТМ~" всего двумя словами, но этого оказывается достаточно, чтобы конгруенция тгтм— отличалась от рисовской (опять же, всег о двумя парами слов).

Далее в §5 для некоторых вполне инвариантных идеалов доказывается строгое неравенство между синтаксической и рисовской конгруенциями; неизвестно ни одного примера вполне инвариантного идеала, для которого эти конгруенции равны. В частности, синтаксические конгруенции языков ОР и СР отличаются от рн-совских весьма значительно. Следующие два параграфа посвящены изучению более простой из них — конгруенции тгог (совпадающей с тг^).

В шестом параграфе производится разбиение сильно бескубных слов на типы. Выделяются типы предмаксимальных слов (являющихся полсловами лишь конечного числа слов из ОР), продолжаемых вправо/влево слов (являющихся, соответственно, префиксами/суффиксами бесконечного числа слов из ОР) и сильно продолжаемых слов (являющихся полсловами сильно бескубных Z-cлoв; этот класс совпадает с ТМ). Доказанная в шестом параграфе Теорема 2.1 позволяет классифицировать произвольное сильно бескуб-ное слово при помощи Алгоритма А и его модификаций.

Седьмой параграф содержит Предложение 2.8, утверждающее, что элементы ТМ лежат в разных классах конгруенции тгог, и Теорёму 2.2, дающую алгоритмически проверяемое необходимое и достаточное условие равенства продолжаемых вправо слов в синтаксической полугруппе языка ОТ. Это условие таково: два продолжаемых вправо слова равны в полугруппе Л+/яоу тогда и только тогда, когда они содержат общее подслово специального вида.

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

Теорема 2.3. Проблема равенства в полугруппе /1 + /тгог разрешима.

Восьмой параграф некоторые факты о конгруенции 7гсу, устроенной существенно сложнее, чем конгруенция ttof ■

Третья глава диссертации посвящена изучению Z-замыканий языков. Z-замыканне языка L (определяется для бесконечных языков, замкнутых относительно подслов) есть множество Z-cлов, все подслова" которых принадлежат L. Это множество обозначается через Lz.

Девятый параграф содержит характеризацию Z-языка 0FZ (совпадающего с TMZ , как уже отмечалось в Следствии 1.1).

Бесконечные цепочки алфавитных символов, индексированные натуральными (соответственно целыми неположительными) числами, называются w-словами (соответственно ¡¿/-словами); w-слово Туэ-Морса Urxj определяется следующим образом: это и -слово, в котором для любого п > 0 префикс длины 2" совпадает с Un. Аналогично определяются w-слово V^ и ы*-слова ooU и ооК.

Некоторые элементы множества OFz (их счетное число) представляют собой "склеенные" (¿"-слово Туэ-Морса и ы-слово Туэ-Морса. Каждому из оставшихся элементов (называемых Z-словами конечного порядка) ставится в соответствие некоторая последовательность из нулей и единиц, называемая характеристической, после чего доказывается следующая теорема.

Теорема 3.1. (1) Всякая бинарная последовательность с бесконечным числом единиц является характеристической для некоторого сильно бескубного Z -слова конечного порядка.

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

Следствие 3.1 ([9]). Множество TMZ содержит континуум попарно нензоморфных элементов.

В начале десятого параграфа дается ответ на вопрос о том, какие еще языки имеют Z-замыкание, совпадающее с TMZ .

Предложение 3.3. Пусть L = {W е А+ \ hexp(W) < f }, V = {IV G Л+| hcxp(W) < Тогда

■ Lz = TMZ С L'z.

Далее исследуются различия между Z-языками TMZ и L'z. Обобщив понятие уравновешенного бинарного слова (т.е. слова, содержащего равное количество букв а и 6) на Z-слова, можно получить понятие n-уравновешенного Z-слова (Z-слова, в каждом под-слове которого разность между числом букв а и 6 по модулю не превосходит п). Все Z-слова из TMZ являются 2-уравновешенными. Принципиально иная картина имеет место для L'z.

Теорема 3.2. Во множестве L'z есть неуравновешенные Z -слова.

Последняя теорема в работе, Теорема 3.3, показывает, что Z-язык CFZ "отделен" от L'z континуальным упорядоченным множеством 2Г-языков.

Теорема 3.3. Пусть ß — рациональное число; | < ß < 3. Тогда существует Z-слово W такое, что hexp(W) = ß.

Из Теоремы 3.3 следует, что каждому действительному числу из промежутка [j,3] соответствует свой Z-язык, состоящий из всех ¿Г-слов с наследственной экспонентой, меньшей этого числа.

Таковы основные результаты диссертации.

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

Литература

[1] Суханов Е.В.,Шур A.M. Эквационалъные языки// — В кн.: Ме-ждунар. конф. по матем. логике, Новосибирск, 1994; тезисы докладов, 96-98.

[2] Guba V.S. The word problem for the relatively free semigroups satisfying Tm = Tm+n with m > 4 or m = 3, n = 1 // Int.. J. Alg. and Сотр., 3 (1993), 125-140.

[3] Guba V.S. The word problem for the relatively free semigroups satisfying 7™ = Tm+n with m > 3// Int. J. Alg. and Сотр., 3 (1993), 335-348.

[4] Bean D.R.,Ehrenfeucht A.,McNulty G. Avoidable patterns in strings of symbols!/ Pacific J. Math., 85 (1979), 261-294.

[5] Зимин Л.II. Блокирующие множества термов// Мат. Сб., 119 (11)82), 363-375.

[0] C'roi lii inore М. An optimal algorithm for computing the repetitions ni a word// Inf. Proc. Letters, 12 (1981), 244-250.

[7] Gottschalk W.II.,IIedlund G.A. A charactcrization of the Morse minimal set// Proc. of Amer. Math. Soc., 15 (1964), 70-74.

[8] Seebold P. Overlap-free sequences// Lect. Notes Сотр. Sci. 194 (1986), 207-215.

[!)] Gottschalk W.II.,Hedlund G.A. Topological dynamics// Amer. Math. Soc. Colloq. Publ., (1955).

Работы автора по теме диссертации

[10] ILIyp A.M. Бинарная избегаемость и слова Туэ-Морса// Доклады РАН, 348(5) (1996), 598-599.

[11] Шур A.M. Синтаксические полугруппы избегаемых языков// Урал. ун-т. Екатеринбург, 1997, деп. в ВИНИТИ №

от -29 с.

[12] Sliur A.M. Overlap-free words and Thue-Morse sequences// - В кн.: Третья Суслинская конференция. Тезисы докл. Саратов, 1994, 54.

[13] Slnir A.M. Binary words avoided by the Thue-Morse sequence// Semigroup Forum, 53(2) (1996), 212-219.

[14] Sliur A.M. Overlap-free words and Thue-Morse sequences// Int. J. of Alg. and Сотр., 6(3) (1996), 353-367.

[15] Shur A.M. On infinite binary words// - В кн.: Междунар. алгебр. конф. памяти Д.К.Фаддеева. Тезисы докл. Санкт-Петербург, 1997, 116.

Подписано в печ. 01.12.97 60 x 84 1/16

Печать офсетная. Объем 1.0. Тираж 100 экз. Заказ № 3 9Я" Екатеринбург, К-83, пр. Ленина, 51. Типолаборатория УрГУ.