Содержание к диссертации
Введение
I Основы теории рациональных множеств в группах 15
1 Основные определения 16
2 Связь двух определений рациональности 23
3 Множества решений уравнений в к. п. нильпотентных группах 27
II О классах рациональных подмножеств групп, замкнутых относительно пересечения и дополнения 34
4 Абелевы группы 36
5 Полициклические группы 41
6 Метабелевы группы 46
III О классе групп, рациональные подмножества которых — булевы алгебры 51
7 Свободные произведения 51
IV О разрешимых группах типа FP 55
8 О почти абелевости некоторых разрешимых групп типа FPoo 55
Литература 59
- Множества решений уравнений в к. п. нильпотентных группах
- Полициклические группы
- О разрешимых группах типа FP
- О почти абелевости некоторых разрешимых групп типа FPoo
Введение к работе
Изучение конечных автоматов и рациональных (регулярных, распознаваемых) множеств началось в 50-х годах XX века в работах [1], [2], [3], [4]. Стимулом и своеобразным "социальным заказом" послужило начало развития вычислительной техники. Понятие конечного автомата близко также таким областям интеллектуальной деятельности, как лингвистика, философия, биология (в которых они часто используются для моделирования). Для математики в данный момент конечные автоматы и рациональные множества — это хорошо известные и привычные объекты теории полугрупп (также хорошо известна параллель между этими объектами, которая устанавливается классической теоремой Клини) — см., например, монографии [5], [6], [7]. Однако классическая теория полугрупп ограничивается изучением рациональных множеств и конечных автоматов в свободных моноидах, хотя определения этих понятий естественно переносятся на случай произвольного моноида (в частности, группы). Идея использования конечных автоматов (причем в разных пониманиях) в данный момент актуальна для теории групп, и работы, связанные с этой тематикой, вызывают большой интерес. Например, известны понятия рациональной структуры, автоматной и биавтоматной структур, комбингов ("причесываний") на группе и др.; возникла новая содержательная теория — см., например, [8], [9], [10]. Однако в рамках этого подхода также рассматриваются лишь рациональные подмножества свободных моноидов, а связь с группой реализуется с помощью понятия "выбор порождающих". Эта связь, на наш взгляд, не всегда адекватно отражает то, что происходит непосредственно в группе. Например, в рамках данной теории определение рационального подмножества группы зависит от рациональной структуры на группе и не инвариантно относительно ее выбора. Кроме того, оно имеет смысл лишь в
конечно порожденных группах. Тем более естественно изучать рациональные подмножества групп в смысле непосредственного определения. В этой области лучше всего изучены свободные группы. Отметим, например, такие работы, как [11], [12], [13]. Данная диссертация также следует этому подходу. Однако в ней более подробно изучаются не свободные группы, а разрешимые.
Вначале расскажем более подробно о том, что такое конечные автоматы. Пусть задан некоторый конечный алфавит А (то есть просто некоторое конечное множество). Его элементы будем называть буквами и обозначать символами а,Ь,с... Словом алфавита А будем называть произвольную конечную последовательность а\ ап букв из алфавита А. В частности, словом является (единственная) пустая последовательность, которую обычно обозначают е. Множество всех слов алфавита А обозначается А*. Число п — это длина слова а,\ -ап, длина пустого слова — нулевая. Длина слова w Є А* обычно обозначается |ги|. На множестве А* х А* пар слов из А* определена операция конкатенации, или "склеивания": из двух слов w = а і ап, v = Ъ± Ьт она конструирует новое слово wv = ai anbi -bm длины т 4- п — \w\ + \v\. Ясно, что эта операция ассоциативна, и слово нулевой длины є является единицей относительно этой операции: для любого w Є А* имеем we = ew = w. Это означает, что множество А* относительно операции конкатенации является моноидом. В действительности моноид А* является свободным: если задан другой моноид М (т.е. множество с определенной на нем бинарной операцией, которая ассоциативна и обладает единицей), то любое отображение / : А -4 М (единственным образом) продолжается до морфизма / : А* —> М, то есть до отображения, "сохраняющего операцию": f(wv) = f(w)f(v), и /(є) = 1. (Способ продолжения при этом очевиден: f(ai---an) = /(ai) f(an), если аг- принадлежат А. Также
очевидно, что так определенное отображение будет "сохраняющим операцию". Содержательной частью утверждения здесь является то, что данное определение не приводит к противоречиям — ведь слово из А* записывается как произведение букв единственным образом. Это и есть "свобода" А*.) Любое подмножество L С А* называется языком над алфавитом А. Можно рассматривать данное понятие языка как некоторую модель "естественного" языка (например, русского или английского). Конечно, аналогия получается довольно грубая, потому что границы естественного языка всегда несколько расплывчаты — например, по поводу принадлежности некоторых высказываний к языку носители языка могут расходиться во мнениях, кроме того, не совсем ясно, что считать "словом" — ведь нельзя понимать русский язык просто как набор слов, "минимальной смысловой единицей" должно быть по меньшей мере предложение. Однако для искусственного и строго формализованного языка (например, языки программирования) модель получается вполне адекватной.
Если мы рассматриваем языки как подмножества свободных моноидов, то сразу же приходится накладывать определенные ограничения, иначе никакой содержательной информации о них получить не удастся. Эти ограничения должны состоять в требовании от языков некоторой степени "разумности", и, по-разному формализуя это понятие, получим различные классы языков, с которыми можно разумно работать. Например, можно потребовать, чтобы принадлежность слова к языку можно было проверять некоторым механическим способом. С другой стороны, можно потребовать, чтобы существовал некоторый механический способ генерирования всех элементов данного языка. Например, можно изучать рекурсивные или рекурсивно перечислимые языки — для первых существуют машины Тьюринга, эффективно проверяющие принадлежность слова к данному языку, для вторых существует алгоритм (реали-
зуемый с помощью машин Тьюринга), выдающий по очереди все слова из данного языка. Аналогично, рациональные языки — это в точности языки, связанные с конечными автоматами, причем можно понимать это и в том смысле, что конечный автомат проверяет принадлежность слова к данному языку, и в том смысле, что конечный автомат генерирует все слова из данного языка. Рассмотрим следующий пример конечного автомата:
а ^^
Здесь окружности — это вершины или, по-другому, состояния автомата, линии, соединяющие вершины — это ребра или стрелки (они имеют направление, и это тоже отражено на рисунке). Ребра имеют метки — это буквы, скажем, алфавита А. Две вершины на данном рисунке играют особую роль. Они помечены, соответственно, входящей стрелкой, у которой нет начала, и выходящей стрелкой, которая не ведет ни в какую вершину. Первая вершина называется начальной, вторая — выходной. У всякого конечного автомата должна быть единственная начальная вершина и по крайней мере одна выходная. Конечный автомат генерирует множество слов следующим образом. В нем есть пути — например, путь 2 — 3 — 3 — 3 — 4 (здесь числа — это номера вершин). По пути определяется его метка, которая является последовательностью меток тех ребер, из которых этот путь состоит — для данного пути это bccb. Теперь будем рассматривать только те пути, которые начинаются
в первой (т.е. начальной) вершине и заканчиваются в четвертой (выходной). Множество их меток — это и есть множество слов, которое генерируется данным автоматом.
С другой стороны, заметим, что в данном автомате из каждой вершины выходит не более одной стрелки с каждой меткой (такой конечный автомат называется детерминированным). Поэтому для каждого слова w (например, для слова w — abcb) существует не более одного пути из начальной вершины с меткой w. (Ясно, что для w = abcb из вершины номер 1 путь должен вести в вершину номер 2, иначе первая буква его метки будет не а, далее в вершину номер 3, потом снова в вершину номер 3 и, наконец, в вершину номер 4.) При такой попытке восстановить путь по слову есть три возможности — либо получен путь с данной меткой из начальной вершины в выходную (пример — слово abcb), либо получен путь с данной меткой из начальной вершины в вершину, которая выходной не является (пример — слово Ьссс), либо процесс оборвался на том, что из какой-то вершины просто нет стрелок с нужной меткой (пример — слово aab). Но ясно, что в первом случае явным образом получено доказательство того, что данное слово принадлежит языку, заданному этим автоматом, а в последних двух случаях наша неудача означает, что данное слово не может принадлежать этому языку. Таким образом, детерминированный конечный автомат можно понимать также как машину, которая проверяет принадлежность слова некоторому языку. Но, как показано, например, в [8], любой язык, заданный конечным автоматом, задан и некоторым детерминированным конечным автоматом. Значит, можно понимать связь между языком и автоматом и в этом смысле.
Заметим, что конечные автоматы по сравнению с машинами Тьюринга довольно примитивны и обладают очень ограниченными возможностями. С другой стороны, заданные ими языки гораздо более понятно
устроены. Существует множество в каком-то смысле промежуточных устройств, способных распознавать формальные языки. Общая идея в том, чтобы возможные варианты работы устройства со словом оставались достаточно обозримыми, как для конечного автомата, но ресурсы, используемые для вычислений, были достаточно богатыми. По существу, берется конечный автомат и оснащается дополнительно некоторым запоминающим устройством (например, стеком или счетчиком). Так, в частности, задан класс контекстно-свободных языков — с помощью определенного типа машин со стеком.
Итак, рациональные языки можно задавать с помощью конечных автоматов. Существуют и другие способы их определения. Известно, например, что любой рациональный язык можно задать с помощью так называемого рационального выражения. Например, язык, который задан изображенным выше автоматом, можно записать с помощью рационального выражения abc*b + bc*b. Здесь сумма означает объединение множеств, звездочка — порождение множеством подмоноида. Вообще класс рациональных подмножеств свободного моноида А* можно определить как замыкание класса всех его конечных подмножеств относительно операций объединения, произведения двух множеств и порождения множеством подмоноида. То, как рациональное множество получается из конечных с помощью указанных операций, и отражает рациональное выражение — конечные множества записываются просто как суммы слов, произведение множеств соответствует приписыванию к одному рациональному выражению другого, объединение соответствует сумме, "навешивание" звездочки — это порождение моноида. В конечных автоматах, соответственно, параллельное соединение двух составных частей эквивалентно объединению, последовательное — произведению, "зацикливание" (петли) дает порождение подмоноида. Отсюда интуитивно понятно, почему рациональные выражения и конечные автоматы поро-
ждают один и тот же класс языков.
Если вместо свободного моноида А* взять произвольный моноид М (например, группу), то определить рациональные множества (в общем случае мы говорим "множества", а не "языки") можно полностью аналогично — как порожденные конечными автоматами с метками из М, а также как замыкание класса конечных подмножеств относительно объединения, произведения и порождения подмоноида. Разница в том, что теперь конечный автомат уже нельзя понимать как машину, которая эффективно вычисляет, принадлежит ли элемент данному множеству или нет. Более того, в общем случае такой машины может и не существовать, даже если рассматривать максимально широкий класс машин — машины Тьюринга (см., например, [19]). Заметим, что в общем случае любое рациональное подмножество М может быть получено как гомоморфный образ некоторого рационального подмножества конечно порожденного свободного моноида.
С другой стороны, так как любой конечно порожденный моноид М является гомоморфным образом конечно порожденного свободного моноида А*, то можно характеризовать подмножества S С М их прообразами из А* или пересечениями этих прообразов с некоторым языком L С А*, в частности, рациональность S определять как рациональность прообраза. Известен такой вопрос: пусть L С А* — полный прообраз единицы при некотором морфизме / : А* —> G, где G — группа. Язык L называют проблемой равенства слов. Задача состоит в том, чтобы описать все группы G, у которых проблема равенства слов принадлежит к определенному классу формальных языков. Например, известно, что рациональной проблемой равенства слов обладают конечные группы и только они. У свободных групп конечного ранга проблема равенства слов — контекстно-свободный язык. Можно поставить вопрос иначе: если группа задана с помощью конечного множества порождающих и мно-
жества определяющих соотношений R из некоторого класса формальных языков, что можно сказать об этой группе? Легко доказать, что если R рационально, то группа конечно определена. В действительности верно большее: если R контекстно-свободное, то группа конечно определена. Можно заметить, что требование, чтобы проблема равенства была "хорошей" или существовал "хороший" набор определяющих соотношений — это некоторое условие на "ядро" данного представления, на то, что "сокращается". Можно подойти с другой стороны и задавать некоторые требования хороших алгоритмических свойств "того, что остается" . Можно, например, выбрать в А* некоторое (скажем, рациональное) множество L представителей всех элементов данной группы и спросить, нельзя ли построить машину, которая бы по слову w Є L находила представитель v из L для его произведения на некоторый фиксированный порождающий. Если ограничить себя условием, что эта машина должна быть некоторым конечным автоматом "от двух переменных", то получается понятие автоматной группы (более точно см. в [8]). Более широкий класс групп, соответствующий более широкому классу машин, — асинхронно автоматные группы. Изучается также класс биавтоматных групп, который содержится в классе автоматных, но неизвестно, совпадают ли они. Автоматные группы обладают рядом полезных свойств, например, они являются конечно определенными и удовлетворяют квадратичному изопериметрическому неравенству, то есть, если задано некоторое представление автоматной группы, то любой элемент свободной группы w, представляющий единицу, может быть записан как произведение не более чем С|г«|2 сопряженных с соотношениями и их обратными, где С не зависит от выбора w. В биавтоматной группе разрешима проблема сопряженности, то есть существует машина Тьюринга, которая, получая на входе два слова, определяет, сопряжены ли заданные ими элементы группы. Примерами автоматных групп являются гиперболи-
ческие и абелевы. С другой стороны, [8] асинхронно автоматная почти нильпотентная группа — почти абелева, то есть нильпотентная группа может быть автоматной лишь в "вырожденном" случае. Далее, как показано в [9], полициклическая группа может быть подгруппой биав-томатной группы лишь в том случае, если она почти абелева. В целом ситуация выглядит так: в свободных группах и близких к ним имеется хорошая корреляция с автоматами, в разрешимом случае (за исключением абелевых) — плохая. Интересно, что при постановке алгоритмических вопросов для группы не с помощью перевода на язык свободных моноидов, а непосредственно наблюдаются очень похожие явления. Так, например, при изучении вопроса о том, когда рациональные подмножества группы замкнуты не только относительно рациональных операций — объединения, произведения, порождения подмоноида, но и относительно пересечения, дополнения в группе, разности множеств, то есть образуют булеву алгебру множеств, выясняется, что это выполняется для свободных групп, а также для абелевых. С другой стороны, (это основной результат данной диссертации) для полициклических и мета-белевых групп это выполняется лишь в том случае, если группа почти абелева. Опять-таки разрешимый случай оказывается "неавтоматным". К сожалению, для общего случая разрешимой группы задача еще не решена, хотя представляется вполне решаемой.
Целью данной диссертации являлось:
дать ответ на вопрос о рациональности множеств решений уравнений от одной неизвестной в классе конечно порожденных нильпотентных групп;
дать описание метабелевых, полициклических групп и разрешимых групп типа .FPoo, У которых классы рациональных подмножеств являются булевыми алгебрами;
3) исследовать класс групп, у которых классы рациональных подмножеств — булевы алгебры, на замкнутость относительно свободных и прямых произведений, подгрупп, факторгрупп и конечных расширений.
Методы исследования опираются на теорию групп и теорию конечных автоматов.
Результаты диссертации являются новыми, носят теоретический характер и могут найти применение в дальнейших исследованиях рациональных подмножеств в группах.
Результаты диссертации докладывались на алгебраическом семинаре Омского университета, на семинаре "Алгебра и логика" Института Математики СО РАН, а также на Международной конференции "Комбинаторные и вычислительные методы в математике" (Омск, 1998).
По теме диссертации опубликовано 7 работ.
Диссертация состоит из введения и четырех глав, содержащих 8 параграфов. Объем работы — 61 страница, список литературы включает 26 наименований.
Содержание диссертации
Множества решений уравнений в к. п. нильпотентных группах
Известно [14], что в свободной группе конечного ранга любое уравнение от одной неизвестной имеет рациональное множество решений. Нетрудно доказать, что аналогичное утверждение верно для конечно порожденных абелевых групп. (Действительно, над абелевой группой А любое уравнение от одной неизвестной эквивалентно уравнению вида пх = а, где х — неизвестная, п натуральное, а а Є А. Но множество решений такого уравнения либо пусто, либо совпадает с некоторым классом смежности по подгруппе Ап = {х Є А\пх = 0}. Если А конечно порождена, то Ап, как и любая ее подгруппа, конечно порождена (и даже конечна, так как содержится в периодической части А), но тогда и Ап, и любой класс смежности по ней рациональны.) Ниже мы даем ответ на известный вопрос о рациональности множеств решений уравнений от одной неизвестной в классе конечно порожденных нильпотентных групп. Мы докажем, что любое уравнение от одной неизвестной в конечно порожденной двуступенно нильпотентной группе имеет рациональное множество решений, а также приведем пример уравнения от одной неизвестной в свободной трехступенно нильпотентной группе ранга два, множество решений которого не рационально.
Начнем с одного технического результата. Лемма 3.1. [20] Пусть К — группа, G — ее подгруппа, Н — нормальная подгруппа G, и пусть [К, G] С Н. Пусть периодическая часть абе-левой группы G/H конечна. Предположим, что любое уравнение вида где йі Є К,ЄІ = ±1,г = 1,...,п, х - неизвестная, s = "=1 Є{ ф О, имеет в Н конечное множество решений. Тогда любое уравнение вида (1) имеет в G конечное множество решений.
Доказательство. Пусть S — множество решений (1) в G. Можно считать его непустым. Пусть ,г] Є S. Элемент v% — а\Єі апЄп можно представить в виде v$ = sc ai -ап, где с% Є [К,G]. Аналогично vv = CLxrf1 anrfn = rfcrjdi -an, где с, Є [K,G]. Так как v% = I = vn, то SC = 77SQ? и r) st;s = c cJ1, а так как для некоторого h Є Н имеем q s s = (r) lt;)sh, то элемент r) lt; факторгруппы G/H имеет конечный порядок. Пусть bi,...,bm — периодическая часть G/H. Тогда Т7_1 равно некоторому 6j, и Є D — (J Li ФІН. Пусть Qi: і = 1,..., m, — множество решений уравнения
Из предыдущей леммы сразу вытекает следующее утверждение, которое, в частности, показывает, что над любой конечно порожденной нильпотентнои группой достаточно широкий класс уравнений от одной неизвестной имеет рациональное множество решений — а именно, если сумма показателей при неизвестной в уравнении ненулевая ("невырожденный случай"), то множество решений рационально. Лемма 3.2. [20] Пусть К — конечно порожденная нилъпотентная группа. Тогда любое уравнение вида (1) имеет в К конечное множество решений. — произвольный центральный ряд. Докажем по индукции, что уравнение (1) имеет в КІ конечное множество решений. Но если для і утверждение верно, то по лемме 3.1, где в качестве G нужно взять Кі+1, а в качестве Н — КІ, оно верно и для і + 1. Лемма доказана.
Замечание 3.1. Хорошо известно, что конечно порожденная нилъпотентная группа без кручения К имеет центральный ряд, факторы которого — без кручения (например, верхний центральный ряд). Поэтому для такой группы леммы 3.1 и 3.2 можно уточнить: любое уравнение вида (1) либо не имеет решений, либо имеет единственное решение (доказательства повторяются практически дословно).
Сейчас мы рассмотрим более подробно конечно порожденные дву-ступенно нильпотентные группы. Как мы увидим, в них ситуация не намного сложнее, чем в абелевых группах. По лемме 3.2 множество решений уравнения с ненулевой суммой показателей при неизвестной конечно, а если эта сумма нулевая, то уравнение эквивалентно уравнению вида [х, а] = Ь, где х — неизвестная, а и Ь — элементы группы (эквивалентность имеет место, так как степени х в левой части уравнения 9oXeig\ -хЄпдп = 1 можно перебрасывать налево через элементы группы — ах1 = х1а[а, х1}, а возникающие при этом коммутаторы центральны в силу двуступенной нильпотентности и их можно собирать справа, далее, так как сумма показателей при неизвестной нулевая, то в конце концов мы получим эквивалентное первоначальному уравнение вида ho[hi,xl1] [hk, xlk] = 1, где hi — элементы группы, a U — целые числа. Но, в силу двуступенной нильпотентности, т.е. центральности коммутанта, выполняющиеся в любой группе для любых о, 6, с равенства [ab,c] = [а,с]ь[Ь,с], [c,ab] = [c,b][c,a]b превращаются в "полилинейность" коммутатора: [ab,c] — [a,c][b,c], [c,ab] = [с, о][с, 6], и, как следствие, [а1, Ь] — [а, Ь1} — [а, Ь]1, где / целое. Поэтому наше уравнение приводится к виду ha[h,х] — 1, что и требовалось.). Но множеством решений уравнения вида [х, a] = b является либо некоторый класс смежности по централизатору а, который будет рациональным подмножеством в силу того, что централизатор а, как и любая подгруппа конечно порожденной нильпотентной (и даже полициклической) группы, конечно порожден, либо пустое множество.
Полициклические группы
Итак, как известно из предыдущего параграфа, рациональные подмножества конечно порожденной почти абелевой группы образуют булеву алгебру. Оказывается, можно доказать, что если рациональные подмножества 71(G) полициклической группы G — булева алгебра, то G почти абелева. Данный параграф будет посвящен доказательству этого факта. Данный результат был получен вначале для более узкого класса групп, чем полициклические — для конечно порожденных нильпотент-ных групп, и опубликован в [20]. Приведем вначале доказательство для этого частного случая, просто потому, что здесь ситуация гораздо прозрачнее, что позволяет нам лучше понять основной смысл.
Сначала заметим, что и для полициклических групп в целом очень упрощает дело тот факт, что все подгруппы полициклической группы G конечно порождены, поэтому если 71(G) — булева алгебра, то для любых подгрупп К Н G (по лемме 1.3) получим, что Н/К — булева алгебра. Ясно, что в общем случае далеко не на всякую факторгруппу переносится свойство замкнутости класса рациональных подмножеств относительно дополнения — ведь любая конечно порожденная группа является гомоморфным образом свободной группы конечного ранга, а свободная группа конечного ранга обладает этим свойством.
В нильпотентном случае доказательство можно проводить индукци ей по ступени нильпотентности. Если Со (С) = {1}, d(G) — C(G) = {д Є G\4h EG gh = hg} центр группы G, Cn(G)/Cn-i(G) = C(G/C„_i( 3)) — верхний центральный ряд группы G, то по индукции G/C,\{G) по чти абелева, но, так как она — конечно порожденная нильпотентная группа, это означает, что ее центр имеет в ней конечный индекс. То гда (,2{G) имеет конечный индекс в G. Таким образом, достаточно до казать, что (двуступенно нильпотентная) группа C2{G) почти абелева. Для этого достаточно показать, что для любых х, у Є (2(G) коммутатор [х, у] = х 1у 1ху имеет конечный порядок. (Если это так, то коммутант Сг(С) конечен, и центр {G) имеет конечный индекс.) Но если [х, у] име ет бесконечный порядок, то элементы х,у — свободные порождающие свободной нильпотентнои группы N ступени 2 и ранга 2. Любой д Є N имеет вид где к,1,т - целые и определены однозначно. Положим — это множество всех д Є N, для которых в формуле (9) к = I 0. Далее, пусть S = х у — это множество всех д Є N, для которых в формуле (9) т = 0, к,1 0. Множество R Г\ S = {хпуп\п 0} рационально, тогда по лемме 1 существуют такие u,v ф 1, ги Є N, что uv w С R П S. Положим q = uvu l,r = uw. Тогда q r С RnS. Пусть q = xkyl[x,y]m,r = xKyx[x,yY. Тогда qnr = хпк+кут+х у пт -гЛк-\ікп[п-і)ш Получаем для любого п 0 равенства откуда к = I, kl = 0, is. q = 1. Полученное противоречие завершает доказательство. Интуитивно, для нильпотентной группы G "тестовыми" являются всевозможные двуступенно нильпотентные двупорожденные подгруппы Н — х,у ее гомоморфных образов. С одной стороны, для замкнутости ее класса рациональных подмножеств относительно дополнения требуется, чтобы для каждой такой Н ее коммутант [х, у] был конечным (и это доказывается с помощью "леммы о накачивании"), с другой стороны, это дает "почти абелевость" всей группы G. В более общем случае, когда G полициклическая, таким "тестовым" случаем является полупрямое произведение бесконечной циклической группы X Z и свободной абелевой группы конечного ранга А Zk, для которой необходимо доказать, что действие некоторой степени xN на А тождественно.
Теорема 5.1. [21] Пусть G — полициклическая группа. Если класс ее рациональных подмножеств — булева алгебра, то G почти абелева. Сначала мы докажем эту теорему для частного случая (см. замечание выше). Напомним, что в силу леммы 1.2 нам не нужно заботиться о том, относительно какой группы данное множество рационально или не рационально. Лемма 5.1. Пусть группа G разлагается в полупрямое произведение G = НА, где А Zk — нормальная подгруппа G, а Н — некоторая циклическая подгруппа G, и Н П А = {1}. Пусть класс рациональных подмножеств G — булева алгебра. Тогда G почти абелева. Доказательство. Пусть Н порождена элементом ip. Можно считать ip элементом бесконечного порядка. Сначала докажем, что некоторый элемент А Э g Ф 1 и некоторая степень fm,m 0, коммутируют. Пусть А Э х ф 1 — произвольное. Рассмотрим множество
R = {ір-пх рп\п 0,пє Z). Если R конечно, то имеем ip nxipn = р 1х(р1 для некоторых п /, откуда [х, ipn l] — 1. Пусть теперь R бесконечно. Заметим, что R рационально, т.к. оно равно (((/) 1) з;(/? ) П А. Тогда по лемме 1.1 R содержит подмножество Р — {aql\l 0}, a,q Є A, q ф 1. Пусть I — такое множество индексов, что Р = {у пх(рп\п Є /}. Пусть S = { рп\п Є /}. Множество S рационально, т.к. оно равно ср П (x lip P). Так как / бесконечно, то S также бесконечно. Тогда оно содержит подмножество Т = іра(ір@) , где а,(3 — целые, (3 0. Множество Q = {h lxh\h Є Т} = (T lxT) П А рационально и содержится в Р.
Так как А изоморфна свободной абелевой группе (конечного) ранга к, можно считать ее подмножеством Rfe. Пусть — какая-нибудь стандартная норма на Rfc. С этого момента операцию на А будем обозначать знаком +. Пусть є — любое положительное действительное число. Выберем натуральное / так, что aq1 (или, в другой записи, a+lq) принадлежит Q, и выполнено неравенство
О разрешимых группах типа FP
Определение 8.2. Группа G имеет конечную когомологическую размерность, если для нее существует проективная резольвента конечной длины, то есть такая, что, начиная с некоторого номера п, все Pj равны нулю. Следующая теорема является главным "ингредиентом" доказательства основного результата данной главы. Теорема 8.1. [16] Пусть G — разрешимая группа типа FP . Тогда найдется такая подгруппа конечного индекса Н G, что Н имеет конечную когомологическую размерность. Нам понадобится также следующая стандартная для данной теории Лемма 8.1. Пусть G — группа конечной когомологической размерности. Тогда 1) G — без кручения; 2) найдется такое натуральное N, что если А G, А Zk, к оо, то к N. Следующая теорема является основным результатом данной главы. Теорема 8.2. [26] Пусть G — разрешимая группа типа FP , рациональные подмножества которой образуют булеву алгебру. Тогда G — конечно порожденная почти абелева группа. Доказательство. Так как 71(G) — булева алгебра, то G конечно порождена. По теореме 8.1 существует подгруппа конечного индекса Н G конечной когомологической размерности. По лемме 1.2 и лемме 1.4 класс рациональных подмножеств 11(H) — булева алгебра, по лемме 8.1, 1), группа Н — без кручения. По теореме Каргаполова [17] если ранги абелевых подгрупп разрешимой группы конечны, то и сама она имеет конечный ранг, то есть существует число N такое, что любая ее конечно порожденная подгруппа порождена не более чем N элементами. Но по лемме 8.1, 2), ранги абелевых подгрупп Н конечны. Значит, Н имеет конечный ранг. Как известно [15], конечно порожденная разрешимая группа К конечного ранга является минимаксной, то есть в ней есть субнормальный ряд 1 = KQ К\ 3 ... Кп = К, в котором каждый фактор Ki+i/Ki удовлетворяет либо условию минимальности для подгрупп, либо условию максимальности для подгрупп (теорема Робинсона - Зайцева). Разрешимая минимаксная группа без кручения является расширением нильпотентной группы с помощью почти абелевой группы [15]. Пусть К Н, К — нильпотентная, Н/К — почти абелева. Группа К должна быть абелевой: пусть 1 1 Сі (К) ... — верхний центральный ряд группы К (Ck{K)/Ck i{K) — центр K/(k_i(K)); если х Є К, у Є (,2{К) не коммутируют, то [х,у] — элемент бесконечного порядка, потому что К без кручения. Значит, подгруппа, порожденная х и у, равна свободной нильпотентной группе ступени два ранга два. Но по теореме 5.1 это невозможно. Значит, Сг(-Ю — Сі(-Ю- Так как группа К нильпотентна, то она совпадает со своим центром.
Замечание 8.1. Доказательство предыдущей теоремы использует идею (известную автору от Г. А. Носкова), которая позволяет доказать, что разрешимая биавтоматная группа G почти абелева. Это дает ответ на известный вопрос о существовании не почти абелевых разрешимых биавтоматных групп (см. [8]). Доказательство полностью состоит из ссылок на известные результаты. Его структура практически та же, что и у приведенного выше доказательства теоремы 8.2. Первый шаг доказательства — ссылка на теорему 10.2.6 из [8], из которой следует, что разрешимые биавтоматные группы принадлежат к типу FPcx). Далее, как и выше, по теореме 8.1 существует подгруппа конечного индекса Н G конечной когомологической размерности. По лемме 8.1, 1), группа Н — без кручения. По лемме 8.1, 2), ранги абелевых подгрупп Н конечны. Значит, по теореме Каргаполова Н имеет конечный ранг. По теореме Робинсона - Зайцева Н является минимаксной. Пусть К Н, К — нильпотентная, Н/К — почти абелева. Группа К должна быть абелевой: пусть 1 ь(,\(К) 3... — верхний центральный ряд группы К; если х Є К, у Є Сі{К) не коммутируют, то [х, у] — элемент бесконечного порядка, и подгруппа, порожденная х и у, изоморфна свободной нильпотентной группе ступени два ранга два. Но это невозможно, так как полициклическая подгруппа биавто-матной группы почти абелева [9]. Значит, (,ъ{К) = С\(К) = К.
Итак, Н конечно порождена и почти метабелева. Тогда она удовлетворяет условию минимальности для централизаторов [15]. (Условие минимальности для централизаторов означает следующее: если S — класс подгрупп М группы Н вида М = Сн{Х) = {h Є H\\fx Є Х[/і, ж] = 1}, где X С Н, то любая последовательность групп вида М0 Э MI D ... Мп Э ..., где все Мп принадлежат классу S, должна стабилизироваться, то есть для всех п, больших некоторого натурального N, должно быть Мп = Мп+і.) Биавтоматная группа с условием минимальности для централизаторов удовлетворяет условию максимальности для абелевых подгрупп [9]. Далее, разрешимая группа с условием максимальности для абелевых подгрупп полициклична (теорема Мальцева, [17]). Так как Н биавтоматна как подгруппа биав-томатной группы конечного индекса, то она полициклическая, и по теореме из [9] о почти абелевости полициклических подгрупп биавто-матных групп Н почти абелева, значит, G почти абелева.
О почти абелевости некоторых разрешимых групп типа FPoo
В этой главе мы изучаем замкнутость класса групп, рациональные подмножества которых — булевы алгебры, относительно различных операций. В силу лемм 1.2, 1.3 и 1.4, если G принадлежит этому классу, то ему принадлежат любая конечно порожденная подгруппа G, любой ее образ относительно гомоморфизма с конечно порожденным ядром, а также любое конечное расширение. В параграфе 7 мы докажем, что этот класс замкнут также относительно свободного произведения. Напротив, прямое произведение групп из этого класса может ему не принадлежать. В частности, свободная группа конечного ранга принадлежит этому классу, но, как хорошо известно, прямое произведение двух свободных групп (хотя бы одна из которых нециклическая) не обладает свойством Хаусона (например, пусть группа F2 — свободная группа ранга два, свободно порожденная элементами х, у, а А = а — бесконечная циклическая группа. Тогда в их прямом произведении подгруппа F2n ar, ay — это в точности нормальное замыкание xFi = хуП\п Є Z элемента х в F2, которое является свободной группой счетного ранга. Значит, прямое произведение F2 х А не обладает свойством Хаусона), а в предыдущем параграфе было замечено, что группы из данного класса обладают свойством Хаусона.
Свободные произведения ных подмножеств — булевы алгебры. Тогда класс рациональных подмножеств их свободного произведения G H — также булева алгебра.
Доказательство. Пусть R С G Н рационально. Покажем, что его дополнение также рационально. Пусть R задано автоматом Г. Можно считать, что все метки ребер Г принадлежат GUH, и, кроме того, если некоторые вершины связаны путем с меткой 1, то они связаны и ребром с меткой 1. Пусть и, v — вершины Г. Определим множества Au v, Bu v следующим образом: Ащг) — множество всех меток путей в Г с началом в и и концом в v, принадлежащих G. Аналогично, Bu v состоит из всех меток путей из и в v, принадлежащих Н. Заметим, что Ащу рационально в G. Автомат над G, задающий Au v, получается из Г с помощью переноса начальной и выходных вершин и удаления всех ребер с метками не из G. (Если х Є AUjV, то кратчайший путь из и в и с меткой х в автомате Г не содержит ребер с метками не из G.) Аналогично, Bu v рационально в Я.
Рассмотрим все множества вида где XUtV есть либо AUj„, либо G \ Au,v, a Y есть либо {1}, либо G \ {1}. Эти множества попарно не пересекаются, рациональны в G, и каждое AU)V (а также его дополнение) представимо в виде объединения таких множеств. Пусть ао, ai,..., ап — список всех непустых множеств такого вида, причем ао = {1}. Аналогично, пусть bo = {1},6і,... ,6m — непустые попарно непересекающиеся рациональные подмножества Н, такие, что каждое BUtV и его дополнение представимы как объединения множеств из данного списка.
Введем конечный алфавит Е = {otj,... ,ап, /Зі,...,@т}. Построим автомат Г\ над Е следующим образом: множество вершин совпадает с множеством вершин Г. Для каждой пары вершин (u,v), если AUiV — Ujejaj, то соединим и и v ребром с меткой а; для каждого і Є I \ {0}, а в случае, если 0 Є /, также ребром с меткой е. (Здесь є — слово нулевой длины.) Аналогично поступим для Bu v вместо ЛиД), ЬІ вместо а и / вместо oij. Пусть L — рациональное множество, заданное Г і. Пусть С — это множество всех слов из Е вида (Лгі)/ ла»2/ 2 aik(@h)- (Любую из букв в скобках можно опустить; слово є тоже будем считать словом такого вида.) Ясно, что С рационально. Обозначим Л = С \ L. Пусть w = (cti PjiCtizPfe ... aik((3jk), тогда положим
Множество S = ишел(ш) рационально и совпадает с G H\R. Действительно, пусть Г2 — автомат над Е , задающий Л. Можно считать, что в Гг все метки принадлежат Е. Заменим в Г2 каждое ребро с меткой at (соответственно, /) на автомат Д (соответственно, Д), задающий йг (соответственно, bj). При этом мы должны позаботиться, чтобы каждый автомат Д имел единственную выходную вершину и не имел ребер, выходящих из нее, а также не имел ребер, входящих в начальную вершину. В результате получаем автомат, задающий 5.
Покажем, что S = G H\R. Прежде всего заметим, что если ги\ Ф w2, Wi,w2 Є С, то (і«і) П {w2) = 0. Пусть ібй. Пусть -к = {vi,fi,v2, h, — это путь в Г, где Vi — вершины, fi — метка некоторого ребра с началом в Vi и концом в иг+1, vx — начальная и Vk+\ — выходная вершины, а метка /і... Д пути тс равна х. По условию /І принадлежит G U Я. Определим элементы qx = /і... / , q2 = fil+i... fi2, таким образом, что все qt принадлежат G U Я, и если qi принадлежит G (соответственно, Я), то qi+i не принадлежит G (соответственно, Я). В частности, либо и = 1, либо ни один из qi не равен единице. Элемент qi принадлежит Ащ._ +1)«,.+1 (или, соответственно, Вщ._ +1М.+1). Пусть х ф 1. Тогда элемент qi принадлежит а3- (соответственно, bj) для некоторого j 0. Тогда существует слово ш LflC такое, что ж Є (w). Тогда х не может принадлежать S. Аналогично, если х = 1, то и = 1, 1 AVltVk+1, отсюда є Є L, и 5і не может содержать единицу. Значит, і?П S — 0. С другой стороны, пусть х R. Существует слово w Є С такое, что х Є ,(w). Если бы w принадлежало L, то х принадлежал бы R. Поэтому w Є Л, и х Є S. Значит, G Н \ R С S. Отсюда G H\R = S. Теорема доказана.
