Конструктивизация нильпотентных групп без кручения

В современном мире, переживающем информационную революцию, связанную с использованием компьютеров и информационных технологий, понятие алгоритма становится едва ли не самым важным из всех математических понятий. Таким образом развитие и совершенствование вычислительной техники способствовало появлению теории конструктивных моделей. Данная теория – один из разделов математики, возникший на границе теории моделей, алгебры и теории рекурсивных функций. Статья А.И. Мальцева в 1961 г. под названием «Конструктивные алгебры» явилась первой обзорной работой по конструктивным моделям, в которой были выработаны и систематизированы основные понятия и намечены дельнейшие пути развития этой теории, он поставил общую задачу: «определить, какие конструктивные нумерации допускают те или иные абстрактно заданные группы». А.И. Мальцеву принадлежит и ряд важнейших результатов по разрешимости элементарных теорий. За этот период теория обогатилась новыми идеями, методами и конструкциями. Конструктивные абелевы группы изучались в работах А.И. Мальцева, Ю.Л. Ершова, С.С. Гончарова, В.П. Добрица, А.Т. Нуртазина, Н.Г. Хисамиева, и других авторов.

В настоящее время теория групп является одной из самых развитых областей алгебры, имеющей многочисленные применения как в самой математике, так и за ее пределами - в топологии, теории функций, квантовой механике и других областях математики и естествознания. Конечной целью собственно теории групп является описание всех групповых композиций. Таким образом, лежащее в фундаменте современной математики понятие группы является весьма разносторонним орудием самой математики - оно используется как важнейшая составная часть ряда сложных алгебраических систем, как чуткий отражатель свойств различных объектов топологии, как испытательный полигон теории алгоритмов и многими иными путями. Важным классом групп является нильпотентные группы. Нильпотентные группы составляют класс, промежуточный между абелевыми и разрешимыми группами. Конструктивные нильпотентные группы исследованы мало. Ю.Л. Ершов [2] доказал, что конструктивизация локально нильпотентной группы без кручения продолжается естественным образом до ее пополнения. В работах В.А. Романькова, Н.Г. Хисамиева [3] доказаны, что матричные группы

,

над коммутативным ассоциативным кольцом К с единицей конструктивизируемы, тогда и только тогда, когда кольцо К конструктивизируемо.

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

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

Пусть G – группа. Отображение множества всех натуральных чисел на G – нумерация группы G. Если существует алгоритм, который по любым числам n, m и s определяет справедливость равенства , то пара (G,v) называется конструктивной группой. Группа G называется конструктивизируемой, если существует такая ее нумерация v, что (G,v) – конструктивная группа, при этом нумерация v – это конструктивизация.

Пусть М – подмножество группы G. Подмножество кольца, группы или полугруппы R, состоящее из элементов, перестановочных (коммутирующих) со всеми элементами из некоторого множества называется централизатором.

,

С(М) – централизатор М в группе G.

Коммутатор элементов g и h есть элемент [g,h]=ghg⁻¹h⁻¹. Элементы g и h называют коммутирующими, если их коммутатор равен единичному элементу группы (такое происходит, когда gh = hg).

Множество всевозможных коммутаторов в группе G порождает подгруппу, называемую коммутантом группы G.

А, В G. Подгруппа из всех коммутаторов [a,b] и их всевозможных произведений образует взаимный коммутант .

Группа без кручения – это группа, не имеющая элементов конечного порядка. Факторгруппа группы без кручения G по ее нормальной подгруппе Н есть группа без кручения тогда и только тогда, когда из того, что хⁿ Н, следует х Н для всех x G и для любого натурального n.

Определим в G возрастающий и убывающий ряды следующим образом: и если подгруппы и уже определены, то и , здесь [A,B] - взаимный коммутант подгрупп А и В. Полученные ряды подгрупп называются соответственно верхним и нижним центральными рядами, а и - n-м централом группы G.

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

Группа G называется нильпотентной группой ступени n, если справедливо равенство (или, что равносильно, ).

Секцией группы G называется всякая факторгруппа В/А, где В, А – подгруппы из G, причем А – нормальная подгруппа в В. Наибольшая полная подгруппа группы G называется ее полной частью.

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

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

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

будет центральный ряд группы . Тогда подгруппы

будут составлять центральный ряд группы G.

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

Пусть G – нильпотентная группа, класс которой не превосходит п. Тогда п–й член нижней центральной цепи этой группы равен е. Иными словами, в группе G будет тождественно выполняться соотношение:

Поэтому, группа G будет факторгруппой некоторой приведенной свободной группы, соответствующей этому тождественному соотношению. Это будет факторгруппа свободной группы F по п–му члену ее нижней центральной цепи.

Факторгруппа сама будет нильпотентной группой класса п; называется ее свободной нильпотентной группой класса п. Число свободных образующих группы F называется рангом группы .

Предложение 1. Пусть (G, ν) – конструктивная группа, а B – ее вычислимо перечислимая подгруппа, содержащаяся в центре Z(G) группы G, такая, что факторгруппа Z(G)/B абелева без кручения и имеет конечный ранг. Тогда подгруппы B и Z(G) вычислимы, а следовательно, подгруппы B,Z(G) и факторгруппы G/B, G/Z(G) с естественными нумерациями, определяемыми по ν, конструктивны.

Доказательство. Пусть – максимальная линейно независимая система элементов группы Z(G)/B. Из эквивалентности νm ∈ Z(G) ⇔ ∃b ∈ B∃m₀ . . .m_n−1 ∈ Z() следует, что центр Z(G) вычислимо перечислим в (G, ν), а следовательно, вычислим. Если в правой части этой эквивалентности дополнительно потребовать условие ∑|m_i| ≠ 0, то νm ∈ Z(G)\B. Отсюда получаем вычислимость подгруппы B.

Теорема 1. Пусть (G,ν) – конструктивная группа и В – ее вычислимо перечислимая подгруппа, содержащаяся в центре Z(G) группы G, такая, что фактор-группа G/B абелева без кручения и ранг Z(G)/ B бесконечен. Тогда существует нумерация m группы G, для которой справедливы следующие свойства:

1) группа (G, ν) конструктивна;

2) подгруппа B вычислима в (G, m);

3) существует такая вычислимо перечислимая система элементов {c_i|iÎI} в (G, m), что смежные классы {c_iB} образуют базис факторгруппы G/B.

Доказательство. Пусть группа (G, ν) и подгруппа B удовлетворяют условиям теоремы. По предложению 1 можно считать, что ранг факторгруппы Z(G)/B бесконечен.

Пусть {B^t | t ∈ ω} – сильно вычислимая последовательность конечных множеств такая, что выполнены условия:

(1) B^t = B, (2)

Пусть – система элементов группы G. t-Оболочкой системы назовем множество

.

Введем множества

, .

Cистему назовем t-независимой, если из

,

где b ∈ B_t, |α_i| ≤ t, следует α₀ = … = α_n−1 = 0.

В данной работе доказано:

Теорема 2. Существует конструктивизируемая двухступенно нильпотентная группа G без кручения, размерность коммутанта которой равна 1, а ее факторгруппа по полной части не конструктивизируема.

Доказательство. В [4] построено вычислимое семейство F вычислимых функций, принимающих значение 0,1,…, p-1, где р – некоторое фиксированное простое число, такое что для любого вычислимого семейства F* F, F*/≈ не имеет однозначной вычислимой нумерации, где ≈ - отношение «почти равно». Пусть F – такое семейство, а ν – его вычислимая нумерация, т.е. и функция , вычислима и . По этой паре (F, ν) зададим группу G образующими а, , d, c и определяющими соотношениями:

,

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

Для доказательства теоремы необходимы следующие леммы:

Лемма 1. Для любых в G справедливо:

, (2)

. (3)

Доказательство проведем индукцией по s. Если s = 1, то (2) следует из (1). Перейдем от s к s+1. Из (1) имеем .

Отсюда и индуктивного предположения получим

, т.е.

, .

Лемма 2. Группа G является конструктивизируемой двухступенно нильпотентной группой без кручения, размерность коммутанта которой равна 1.

Лемма 3. Для любых k, s и элемента справедливо , где

.

Доказательство. По Лемме 1 имеем , t ≤ n.

Отсюда:

Элемент назовем полным, если для любого существует в G.

Лемма 4. Элемент g из централизатора элементов d, a является полным тогда и только тогда, когда делится на при любом s.

Доказательство. Т.к. , то . Из Леммы 3 имеем . Из следует, что элемент g полон тогда и только тогда, когда g₀ полон. Отсюда и из следует, что g полон тогда и только тогда, когда делится на p^s.

Лемма 5. Если факторгруппа Н/Р конструктивизируема, то семейство допускает однозначную вычислимую нумерацию и .

Доказательство. Группа конструктивизируема. Существует такая конструктивизация μ группы F', что подгруппа (е) вычислима в (G, μ). Тогда существует вычислимо перечислимая последовательность представителей μn₀, μn₁, … в смежных классах по подгруппе (е). Очевидно, что можно считать, что F'/(е) – бесконечная группа и μn₀ = (0,0,…). Рассмотрим семейство вычислимых функций {μn_i | }. Любая функция f почти равна некоторой функции μn_i, либо , если n_i ≠ n_j, то μn_i ≠ μn_j. .

Перейдем к доказательству теоремы. По лемме 1 группа G конструктивизируема, а базисом коммутанта есть элемент с, т.е. размерность равна 1. Пусть Н – централизатор элементов a, d. Тогда Н – вычислимая подгруппа и, следовательно, конструктивизируема. Пусть Р – полная часть подгруппы Н. Если бы Н/Р была бы конструктивизируемой, то по лемме 5 нашлось бы семейство такое, что допускала бы однозначную вычислимую нумерацию, что противоречит выбору F. Теорема доказана.

Как следствие к Теореме 2, можно записать следующую теорему.

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

ЛИТЕРАТУРА

1. Мальцев А.И. О рекурсивных абелевых группах, Докл.АН СССР, 146, 5(1962), 1009-1012.

2. Ершов Ю.Л. Существование конструктивизаций, Докл.АН СССР, 204, 5(1972), 1041-1044.

3. Романьков В.А., Хисамиев Н.Г. О конструктивных матричных и упорядоченных группах, Алгебра и логика. 2004, 43, №3. С.353-363.

4. Хисамиев З.Г. Вычислимые нумерации и отношения эквивалентности, Сиб. мат. жур. 1986. Т.27, №5, С.182-187.

5. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели, М., Наука, 1996.

6. Гончаров С.С., Ершов Ю.Л. Конструктивные модели, серия: школа алгебры и логики, Новосибирск, Научная книга, 1999.

7. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп, 4-е изд., М.: Наука, 1996.

8. Гончаров С.С. Автоустойчивость модели и абелевых р-групп, алгебра и логика, 19, 1(1980), 23-44.