close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
ЧЕБЫШЕВСКИЙ СБОРНИК
Том 13 Выпуск 1 (2012)
Труды IX Международной конференции
Алгебра и теория чисел: современные проблемы и приложения,
посвященной 80-летию профессора Мартина Давидовича
Гриндлингера
80-летию Мартина Давидовича
Гриндлингера посвящается
УДК 510.53+512.54.0+512.54.03+512.54.05+512.543.72
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ,
РАЗРЕШЕННЫХ ОТНОСИТЕЛЬНО НЕИЗВЕСТНЫХ,
С ОГРАНИЧЕНИЯМИ НА РЕШЕНИЯ
В. Г. Дурнев, О. В. Зеткина
Аннотация
Устанавливается алгоритмическая неразрешимость проблемы разрешимости в свободной группе F2 ранга 2 со свободными образующими a и
b для систем уравнений с ограничениями на решения вида
t
(1)
w(x1 , . . . , xn ) = [a, b] & & xi ? F2
i=1
и вида
(2)
w(x1 , . . . , xn ) = [a, b] & x1 ? F2 ,
где w(x1 , . . . , xn ) слово в алфавите неизвестных {x1 , . . . , xn }, [a, b] ком(1)
(2)
мутатор свободных образующих a и b, F2 коммутант группы F2 , а F2
ее второй коммутант.
Устанавливается существование полиномиального алгоритма, позволяющего по произвольному разрешенному относительно неизвестных уравнению вида
w ( x1 , . . . , xn ) = g( a, b ),
где w ( x1 , . . . , xn ) групповое слово в алфавите неизвестных, а g( a, b )
элемент длины меньше 4 свободной группы F2 , определить, существует
ли решение этого уравнения, удовлетворяющее условию
(s)
(s)
x1 ? F2 , . . . , xt ? F2 ,
(s)
где t произвольное фиксированное число между 1 и n, а F2 s-ый
коммутант группы F2 .
Устанавливается алгоритмическая разрешимость аналогичных проблем для уравнений с одним неизвестным.
64
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
Обозначим через Fm свободную группу ранга m со свободными образующими a1 , ..., am .
При m = 2 вместо a1 и a2 будем писать a и b соответственно.
Уточним некоторые определения, относящиеся к системам уравнений в свободных группах.
Системой уравнений с неизвестными x1 ,..., xn в свободной группе Fm называется выражение вида
k
& wi (x1 , . . . , xn , a1 , . . . , am ) = ui (x1 , . . . , xn , a1 , . . . , am ),
i=1
(1)
где wi (x1 , . . . , xn , a1 , . . . , am ) и ui (x1 , . . . , xn , a1 , . . . , am ) слова в алфавите
?1
?1
?1
{ x1 , x?1
1 , . . . , xn , xn , a1 , a1 , . . . , am , am }.
Набор ?g1 , . . . , gn ? элементов группы Fm называется решением системы (1), если
при любом i (i = 1, . . . , k ) в группе Fm выполняется равенство
wi (g1 , . . . , gn , a1 , . . . , am ) = ui (g1 , . . . , gn , a1 , . . . , am ).
Две системы уравнений с одними и теми же неизвестными называются эквивалентными, если множества их решений совпадают.
Используя уравнение
[x, a] = ([x, b] y 2 )2 ,
имеющее в свободной группе Fm при любом m > 2 лишь тривиальное решение x = 1, y = 1, любую систему уравнений (1) можно заменить одним, ей
равносильным, уравнением.
Для уравнений в свободных группах традиционно рассматриваются две основные задачи: проблема существования решения и проблема описания множества всех решений.
Исследование разрешимости уравнений в свободных группах было начато
американскими математиками в конце 50-х годов в связи с проблемой разрешимости элементарных теорий свободных групп, поставленной А. Тарским [1].
В начале исследовались лишь отдельные уравнения, а в 1960г. Р. Линдон [2]
нашел для произвольного уравнения с одним неизвестным описание множества
всех его решений с помощью параметрических слов, т.е. выражений, полученных из образующих рассматриваемой свободной группы с помощью операций
группового умножения и возведения в степень с переменным целочисленным
показателем. Позже А.А. Лоренц [3] и К.И. Аппель [4] уточнили это описание
Р. Линдона, доказав, что общее решение любого уравнения с одним неизвестным в свободной группе представимо конечным числом формул вида AB t C , где
A, B , C конкретные слова, а t параметр, принимающий произвольные целочисленные значения. Дальнейшее продвижение в этом вопросе было достигнуто
в 1970 году Ю.И. Хмелевским [5].
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
65
В 1982 году Г.С. Маканин [6] получил полное решение проблемы распознавания разрешимости уравнений в свободной группе. Он доказал, что если данное уравнение с длиной записи d имеет решение в свободной группе, то длина
каждой компоненты минимального (по максимальной длине компоненты) решения не превосходит числа ?(d), где ?(x) некоторая рекурсивная функция.
Это дает переборный алгоритм для распознавания разрешимости произвольного уравнения в свободной группе.
В связи с уже упоминавшейся выше проблемой А. Тарского о разрешимости элементарной теории произвольной свободной группы представляет интерес
исследование алгоритмической природы фрагментов этой теории. Основные на
сегодняшний день результаты в этой области получены Г.С. Маканиным. Вскоре после опубликования работы [6] ему удалось на том же пути доказать разрешимость экзистенциональной (универсальной) и позитивной теорий любой
свободной группы [7]. При доказательстве разрешимости позитивной теории
свободной группы Г.С. Маканин использовал результат Ю.И. Мерзлякова [8]
об устранимости кванторов общности в позитивных формулах, относящихся к
свободным группам.
А.А. Разборов [9] дал описание множества решений произвольной совместной системы уравнений в свободной группе.
После построения Г.С. Маканиным [6] разрешающего алгоритма для систем
уравнений в свободной группе Fm , особый интерес стал представлять вопрос о
существовании аналогичных алгоритмов для уравнеий в свободных группах с
различными "не слишком сложными"ограничениями на решения.
Вопрос о разрешимости позитивной теории свободной группы был сведен
Ю.И. Мерзляковым [8] к следующей проблеме
существует ли алгоритм, позволяющий для произвольного уравнения
w ( x1 , . . . , xn , a1 , . . . , am ) = 1
в свободной группе счетного ранга определить, имеет ли оно такое решение
g1 , . . ., gn , что
g1 ? Fm1 , g2 ? Fm2 , . . . , gt ? Fmt ,
где m1 6 m2 6 . . . 6 mt , Fmi - свободная группа c образующими a1 , . . ., ami .
Г.С. Маканиным [7] построил искомый алгоритм, и тем самым доказал разрешимость позитивной теории свободной группы.
Хорошо известно, что вопрос о точности матричного представления Гасснер
[10], [11] группы крашеных кос эквивалентен вопросу об отсутствии нетривиального решения в свободной группе Fm уравнения
?1
?1
x1 a1 x?1
1 · x2 a2 x2 · · · xm am xm = a1 · a2 · · · am ,
удовретворяющего условию
x1 ? Fm(2) , . . . xn ? Fm(2) ,
66
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
(2)
где Fm второй коммутант свободной группы Fm . Напомним, что для произвольной группы G через G(2) обозначается ее второй коммутант, т.е. G(2) =
[G(1) , G(1) ], где G(1) = [G, G] коммутант группы G. Кроме того при произвольном t G(t+1) = [G(t) , G(t) ] и G(0) = G.
Обобщая эти ситуации Г.С. Маканин поставил в "Коуровской тетради"[12]
следующую проблему для уравнений в свободных группах
"9.25. Указать алгоритм, который по уравнению
w ( x1 , . . . , xn , a1 , . . . , am ) = 1
в свободной группе Fm и списку конечно порожденных подгрупп H1 ,..., Hn группы Fm позволял бы узнать, существует ли решение этого уравнения с условием
x1 ? H1 , . . . , xn ? Hn ?.
Первые положительные результаты в направлении решения этой проблемы были получены А.Ш. Малхасяном [13].
В. Диекерт [14] показал, что проблема определения по произвольному уравнению
w ( x1 , . . . , xn , a1 , . . . , am ) = 1
в свободной группе Fm и списку регулярных подмножеств (языков) H1 ,..., Hn
группы Fm узнать, существует ли решение этого уравнения с условием
x1 ? H1 , . . . , xn ? Hn ?
разрешима и принадлежит классу P SP ACE . Так как конечно порожденные
подгруппы являются регулярными подмножествами, то тем самым решается и
проблема Г.С. Маканина.
Представляет интерес дальнейшее исследование различных обобщений проблемы Г.С. Маканина для свободных групп, получающихся путем ослабления
ограничений, налагаемых на подгруппы H1 ,..., Hn .
Одна из причин, по которым в формулировке задачи 9.25 речь идет именно о конечно порожденных подгруппах, заключается в том, что для конечно
порожденных подгрупп свободной группы разрешима проблема вхождения.
В то же время проблема вхождения разрешима и для многих бесконечно по(1)
рожденных подгрупп свободной группы, причем, например, для первого Fm и
(2)
второго Fm коммутантов свободной группы Fm проблема вхождения решается
чрезвычайно просто, значительно проще, чем для некоторых конечно порожденных подгрупп. Поэтому представляется достаточно естественным следующее обобщение задачи 9.25.
"9.25a. Существует ли алгоритм, который по уравнению
w ( x1 , . . . , xn a1 , . . . , am ) = 1
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
67
в свободной группе Fm и списку подгрупп H1 ,..., Hn с разрешимыми проблемами
вхождения позволял бы узнать, существует ли решение этого уравнения с
условием x1 ? H1 ,. . . ., xn ? Hn ?".
В работе [15] первого автора был получен следующий результат.
Теорема
1. В свободной группе F2 со свободными образующими a и b
можно построить такое уравнение
w ( x, x1 , . . . , xn , a, b ) = 1
с неизвестными x1 , x2 ,..., xn , константами a и b и параметром x, что не
существует алгоритма, позволяющего для произвольного натурального числа
k определить, существует ли решение уравнения
w ( ak , x1 , . . . , xn , a, b ) = 1,
удовлетворяющее условию
x1 ? [F2 , F2 ], . . . , xt ? [F2 , F2 ],
где t некоторое фиксированное число между 1 и n.
В настоящей заметке существенно усиливается этот результат. Причем в
определеном смысле это усиление близко к окончательно возможному.
В ряде работ [16], [5], [17], [18], [19] рассматривались уравнения вида
w ( x1 , . . . , xn ) = g( a1 , . . . , am ),
где w ( x1 , . . . , xn ) групповое слово в алфавите неизвестных x1 , x2 ,..., xn , т. е.
не содержит констант a1 , ..., am , а g( a1 , . . . , am ) слово в алфавите констант a1 ,
..., am , т. е. не содержит неизвестных. Они получили название уравнений, разрешенных относительно неизвестных, или уравнений с правой частью. Проблема
разрешимости для таких уравнений иногда называется проблемой подстановки
или проблемой сравнения с образцом.
Обозначим через [u, v] коммутатор элементов u и v , т. е. [u, v] = uvu?1 v ?1 .
2. В свободной группе F2 со свободными образующими a и b
можно построить такое семейство разрешенных относительно неизвестных
уравнений
w ( xk , x1 , . . . , xn ) = [ a, b ],
Теорема
где w ( xk , x1 , . . . , xn ) групповое слово в алфавите неизвестных x, x1 , x2 ,...,
xn , что невозможен алгоритм, позволяющий для произвольного натурального
числа k определить, существует ли решение уравнения
w ( xk , x1 , . . . , xn ) = [ a, b ],
удовлетворяющее условию
x1 ? [F2 , F2 ], . . . , xt ? [F2 , F2 ],
где t некоторое фиксированное число между 1 и n.
68
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
Теорема
нению вида
3. Невозможен алгоритм, позволяющий по произвольному урав-
w ( x1 , ..., xn ) = [a, b]
в свободной группе F2 определить, имеет ли оно такое решение g1 , ..., gn , что
(2)
g1 ? F2 .
Предварительно докажем вспомогательную лемму.
1. Уравнение w(x1 , . . . , xn , a, b) = 1 имеет решение в свободной
группе F2 , удовлетворяющее условию
Лемма
(s)
(s)
x 1 ? F2 , . . . , x t ? F2 ,
тогда и только тогда, когда в этой группе следующее уравнение
w4 (x1 , . . . , xn , u, v)[u, v] = [a, b]
имеет решение, удовлетворяющее условию
(s)
(s)
x 1 ? F2 , . . . , x t ? F2 ,
Если уравнение w(x1 , . . . , xn , a, b) = 1 имеет решение
g1 , ..., gn в свободной группе F2 , удовлетворяющее условию
Доказательство.
(s)
(s)
g1 ? F2 , . . . , gt ? F2 ,
то g1 , ..., gn , a, b решение уравнения
w4 (x1 , . . . , xn , u, v)[u, v] = [a, b],
удовлетворяющее условию
(s)
(s)
g1 ? F2 , . . . , gt ? F2 .
Обратно, пусть g1 , ..., gn , ?, ? решение уравнения
w4 (x1 , . . . , xn , u, v)[u, v] = [a, b],
удовлетворяющее условию
(s)
(s)
g1 ? F2 , . . . , gt ? F2 .
А.А. Вдовина [20] доказала, что равенство [u, v][s, t] = w4 влечет в свободной
группе F2 равенство w = 1.
Поэтому равенство
w4 (g1 , . . . , gn , ?, ?)[?, ?] = [a, b]
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
69
влечет равенства w(g1 , . . . , gn , ?, ?) = 1 и [?, ?] = [a, b].
Тогда по теореме А.И. Мальцева [16] ? и ? свободные образующие группы
F2 , поэтому существует автоморфизм ? свободной группы F2 такой, что ?(?) =
a и ?(?) = b.
Применив автоморфизм ? к равенству w(g1 , . . . , gn , ?, ?) = 1, получим
w(?(g1 ), . . . , ?(gn ), a, b) = 1.
(s)
(s)
При этом, если gi ? F2 , то и ?(gi ) ? F2 .
Значит ?(g1 ), ..., ?(gn ) решение уравнения w(x1 , . . . , xn , a1 , a2 ) = 1, удовлетворяющее условию
(s)
(s)
?(g1 ) ? F2 , . . . , ?(gt ) ? F2 .
2
Доказательство.
теоремы 2. Введем предикат
Z(x) ( [ x, a ] = 1 ).
Хорошо известно, что для любого элемента g ? F2 :
F2 |= Z(g)
??
?g ? степень a?.
Рассмотрим предикаты
T ( x1 , x2 )
( [ x1 , a ] = 1 & [ x2 , b ] = 1 ) & ( ? x y ) ( [ x, ab ] = 1 &
?1
& y = xx?1
1 x2 & y ? F2 );
(1)
M ( x1 , x2 , x3 ) ( ? x y z ) ( T ( x2 , x) & [ y, x1 b ] = 1 &
?1
& z = yx?1
& z ? F2 ).
3 x
(1)
Легко понять, что для произвольных элементов g и h группы F2 :
F2 |= T ( g, h ) ??
? существует такое целое число p, что g = ap , h = bp ?.
Нетрудно проверить, что для произвольных целых чисел s, t и r имеет место
эквивалентность
F2 |= M ( as , at , ar ) ?? r = s t.
Воспользуемся целочисленным вариантом непосредственного следствия
теоремы Ю.В. Матиясевича о диофантовости перечислимых множеств [21]:
70
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
Для произвольного рекурсивно перечислимого множества A натуральных
чисел можно построить такую формулу ?A (x1 ) вида
( ? x2 . . . xp ) ?,
s
где ? = & ?i
i=1
и каждая формула ?i имеет один из следующих видов:
xl + xj = xt ,
xj = xl ,
xl xj = xt ,
xj = c,
где c целое число,
что для произвольного натурального числа k имеем:
n ? A тогда и только тогда, когда формула ?A (k) истинна на кольце целых
чисел.
Пусть A рекурсивно перечисленное множество, а ?A ( x1 ) соответствующая формула.
По формуле ?A ( x1 ) построим формулу ?1 (x1 ) следующим образом:
p
?1 ( x1 ) ( ? x2 . . . xp ) ( ?1 & ( & Z ( xi ) ) ),
i=2
где ?1 получено из ? заменой каждой формулы ?i вида xl + xj = xt на xl xj =
xt , формулы вида xl xj = xt на M ( xl , xj , xt ), формулы вида xj = xl на
xj = xl , а формулы вида xj = c на xj = ac .
Подходящим образом переименовав переменные в формуле ?1 ( x1 ) приведем полученную формулу ?(x) к виду
l
t
i=1
j=1
(1)
( ? x1 . . . xn ) ( ( & wi = 1 ) & ( & xj ? F2 ).
Воспользовавшись уравнением [x, a] = ([x, b] y 2 )2 , имеющим лишь тривиl
альное решение x = 1, y = 1, заменим систему уравнений & wi = 1 одним
i=1
уравнением w = 1, ей равносильным, в итоге получим: для произвольного натурального числа k
k ? A ??
F2 |= ( ? x1 . . . xn ) ( w ( ak , x1 , . . . , xn , a, b ) = 1 &
t
(1)
& & xj ? F2 ).
j=1
Воспользовавшись леммой, получим:
для произвольного натурального числа k
k ? A ??
F2 |= ( ? x1 . . . xn u v ) ( w4 ( uk , x1 , . . . , xn , u, v ) [u, v] = [a, b] &
t
(1)
& & xj ? F2 ).
j=1
Если теперь в качестве A взять рекурсивно перечислимое, но нерекурсивное
множество, то доказательство теоремы 2 будет завершено. 2
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
Лемма
71
2. Имеет место эквивалентность
t
& gi ?
i=1
(1)
F2
t
?
??
(2)
[ gi , [ a1 , a2 ] ] ? F2 .
i=1
t
(1)
Доказательство. Если & gi ? F2 , то, конечно,
i=1
t
?
(2)
[ gi , [ a1 , a2 ] ] ? F2 .
i=1
Обратно, пусть
t
?
(2)
[ gi , [ a1 , a2 ] ] ? F2 .
i=1
(2)
Перейдем к факторгруппе F2 /F2 , которую будем обозначать через F2 (S2 ).
Напомним, что F2 (S2 ) это свободная метабелева группа ранга 2. Обозначая
(2)
для упрощения образ элемента g группы F2 в факторгруппе F2 /F2 вновь через
g , что не приведет к недоразумениям, мы получим в группе F2 (S2 ) равенство
t
?
[ gi , [ a1 , a2 ] ] = 1.
i=1
Покажем, что это равенство в группе F2 (S2 ) влечет равенства
t
& g?i = 1
i=2
(1)
в свободной абелевой группе F2 (S1 ) = F2 /F2 , где g? - образ элемента g в группе
F2 (S1 ) при естественном гомоморфизме группы F2 (S2 ) на группу F2 (S1 ).
(2)
Воспользуемся вложением В. Магнуса [22] группы F2 /F2 в группу матриц
(1)
M (F2 /F2 , T )
[
]
g? ?1 t1 + ?2 t2
0
1
(1)
где T свободный Z [ F2 /F2 ]-модуль с базой t1 , t2 ;
(1)
g? ? F2 /F2 ,
относительно отображения
[
w?
w ?
7 ?
0
(1)
где w? образ w в F2 /F2 ,
(1)
?i ? Z[ F2 /F2 ]
?w
t
?a1 1
+
1
?w
t
?a2 2
]
,
72
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
?w
(1)
значение i-той производной Фокса [23] в Z [ F2 /F2 ].
?ai
Непосредственные вычисления в Z[ F2 ] дают равенства
?[a1 , a2 ]
= 1 ? [a1 , a2 ] a2 ,
?a1
?[a1 , a2 ]
= a1 ? [a1 , a2 ].
?a2
Пусть w(a1 , a2 ), u(a1 , a2 ) и v(a1 , a2 ) произвольные элементы свободной группы
F2 . Тогда элемент w(u(a1 , a2 ), v(a1 , a2 )) будем обозначать коротко через w(u, v).
Для его дифференцирования применяем цепное правило
?w(u, v)
?w
?u
?w
?v
=
(u, v) ·
+
(u, v) ·
.
?ai
?a1
?ai
?a2
?ai
Получаем в Z[ F2 ] равенства
?[u, v]
?u
?v
= (1 ? [u, v] v) ·
+ (u ? [u, v]) ·
.
?ai
?ai
?ai
(1)
Перейдя к Z [ F2 /F2 ], получим равенства
?[a1 , a2 ]
?[a1 , a2 ]
= 1 ? a2 ,
= a1 ? 1;
?a1
?a2
?[u, v]
?u
?v
= (1 ? v) ·
+ (u ? 1) ·
.
?ai
?ai
?ai
Прямые вычисления показывают, что элементу [ g, [ a1 , a2 ] ] группы F2 (S2 ) соответствует матрица
[
]
1 (g ? 1)[(1 ? a2 )t1 + (a1 ? 1)t2 ]
.
0
1
Поэтому равенство
t
?
[ gi , [ a1 , a2 ] ] = 1,
i=2
(1)
имеющее место по предположению в группе F2 (S2 ), дает в Z[ F2 /F2 ] равенство
( 1 ? a2 )
t
?
( g i ? 1 ) = 0.
i=2
(1)
(1)
Так как групповое кольцо Z[F2 /F2 ] свободной абелевой группы F2 /F2 не имеет делителей нуля, то
t
?
( g i ? 1 ) = 0.
i=2
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
73
Последнее равенство влечет равенства
t
& g i = 1,
i=2
то есть
t
(1)
& gi ? F2 .
i=2
Доказательство теоремы 3 теперь получается из теоремы 2 и лемм 2 и 1.
Заметим, что слово [a, b], стоящее в правой части рассматриваемых в доказанной теореме уравнений, имеет длину 4. Следующая теорема показывает
невозможность дальнейшего уменьшения длины правой части.
4. Существует полиномиальный алгоритм, позволяющий по
произвольному разрешенному относительно неизвестных уравнению вида
Теорема
w ( x1 , . . . , xn ) = g( a, b ),
где w ( x1 , . . . , xn ) групповое слово в алфавите неизвестных x1 , x2 ,..., xn , а
g( a, b ) элемент длины меньше 4 свободной группы F2 со свободными образующими a и b определить, существует ли решение этого уравнения, удовлетворяющее условию
(s)
(s)
x 1 ? F2 , . . . , x t ? F2 ,
где t произвольное фиксированное число между 1 и n.
Если g групповое слово длины меньше 4 в алфавите
{a, b} свободных образующих группы F2 , то нетрудно убедиться, что g степень
Ak некоторого примитивного элемента A группы F2 .
Покажем, что уравнение
Доказательство.
w(x1 , ..., xn ) = g,
т.е. уравнение
w(x1 , ..., xn ) = Ak ,
имеет решение в группе F2 , удовлетворяющее условию
(s)
(s)
x 1 ? F2 , . . . , x t ? F2 ,
тогда и только тогда, когда в циклической группе F1 с образующим элементом
a разрешимо уравнение
w(1, ..., 1, xt+1 , ..., xn ) = ak .
Вопрос о разрешимости последнего уравнения сводится к вопросу о разрешимости в целых числах линейного уравнения с целыми коэффициентами. А последний вопрос полиномиально разрешим.
74
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
Предположим, что A и B система свободных образующих группы F2 (напомним, что A примитивный элемент этой группы), а ? и ? такие автоморфизмы этой группы, что
? (A) = a,
? (B) = b;
? (a) = A,
? (b) = B.
Пусть g1 , ..., gn решение в группе F2 уравнения
w(x1 , ..., xn ) = Ak ,
удовлетворяющее условию
(s)
(s)
g1 ? F2 , . . . , gt ? F2 .
Применив к равенству w(g1 , ..., gn ) = Ak автоморфизм ?, получим равенство
w(?(g1 ), ..., ?(gn )) = ak .
К последнему равенству применим гомоморфизм ?1 группы F2 на группу F1 ,
заданный равенствами
?1 (a) = a, ?1 (b) = 1,
получим
w(?1 (?(g1 )), ..., ?1 (?(gn ))) = ak .
(s)
Если g ? F2 , то ?1 (?(g)) = 1, поэтому
?1 (?(g1 )) = 1, . . . , ?1 (?(gt )) = 1.
Значит ?1 (?(gt+1 )), ..., ?1 (?(gn )) решение уравнения
w(1, ..., 1, xt+1 , ..., xn ) = ak .
в группе F1 .
Обратно, если ht+1 , ..., hn решение уравнения
w(1, ..., 1, xt+1 , ..., xn ) = ak
в группе F1 , то применив к равенству в группе F2
w(1, ..., 1, ht+1 , ..., hn ) = ak
автоморфизм ? этой группы, получим
w(1, ..., 1, ?(ht+1 ), ..., ?(hn )) = Ak ,
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
75
значит g1 = 1, ..., gt = 1, gt+1 = ?(ht+1 ) gn = ?(hn ) решение в группе F2
уравнения
w(x1 , ..., xn ) = Ak ,
удовлетворяющее условию
(s)
(s)
g1 ? F2 , . . . , gt ? F2 .
2
Для уравнений с одним неизвестным ситуация иная.
(r)
Пусть N r-й коммутант Fn свободной группы Fr или r-й член (Fm )r ее
нижнего центрального ряда.
Теорема
5. Существует полиномиальный алгоритм, позволяющий по
любому уравнению с одним неизвестным
w ( x1 , a1 , . . . , an ) = 1
в свободной группе Fn определить имеет ли оно такое решение x1 , что x1 ? N
А.А. Лоренц [3] и К.И. Аппель [4] доказали, что множество решений уравнения с одним неизвестным задается конечным множеством
параметрических слов, т.е. слов вида A B ? C , где ? - целочисленный параметр.
Д. Бормотов, Р. Гилман и А. Мясников [24] разработали полиномиальный алгоритм для построения по уравнению с одним неизвестным соответствующего
множества параметрических слов.
Тем самым вопрос о существовании решения уравнения
Доказательство.
w ( x1 , a1 , . . . , an ) = 1
(2)
в свободной группе Fn с условием x1 ? N полиномиально сводится к определению, существует ли такое целое число ?, что A B ? C ? N или B ? = A?1 C ?1
в Fn /N, т.е. задача о существовании у уравнения (2) решения с условием x1 ? N
сводится к проблеме степеней для группы Fn /N: существует ли такое целое
число ?, что B ? = A?1 C ?1 в Fn /N. Поэтому для завершения доказатель(r)
ства теоремы достаточно показать, что проблема степеней для групп Fn /Fn и
Fn /(Fn )r полиномиально разрешима. 2
(r)
Напомним, что группа Fn /Fn называется свободной разрешимой группой ранга n ступени разрешимости r и обозначается через Fn ( Sr ), а группа
Fn /(Fn )r называется свободной нильпотентной группой ранга n класса нильпотентности r и обозначается через Fn ( Nr ).
Проблема степеней для произвольной свободной разрешимой группы
Fn ( Sr ) решена в работе [25]. В виду трудной доступности этой работы и для
полноты изложения приведем достаточно простое решение проблемы степеней
для свободной разрешимой группы Fn ( Sr ).
76
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
Следующая ниже лемма впервые доказана в работе [25], для полноты изложения мы дадим, на наш взгляд, более простое ее доказательство, используя дифференцирования группового кольца Z [ Fn / [ N, N ] ] со значениями в
Z [ Fn / N ]. Все необходимые определения и свойства таких дифференцирований можно найти в книгах [23], [22], [11] и статьях [26], [27].
3. Если слово b в образующих a1 , . . . , an имеет длину p и b ?= 1 в
Fn ( Sr ), то при k > p уравнение xk = b не имеет решения в группе Fn ( Sr ).
Лемма
проведем индукцией по r. При r = 1 Fn ( S1 ) свободная абелева группа с базой a1 , . . . , an , поэтому b = a?1 1 . . . a?nn и p =| ?1 |
+ . . . + | ?n |.
Доказательство.
n
Представив x в виде ax1 1 ...axnn , получим систему уравнений & kxi = ?i ,
i=1
которая при k > p > max { | ?i | } не имеет решения, так как при некотором
16i6n
?i0 ?= 0.
Предположив, что утверждение доказано для группы Fn ( Sr ), докажем его
для группы Fn ( Sr+1 ). Пусть b ?= 1 в Fn ( Sr+1 ). Обозначим через b? образ b в
фактор-группе
i0
Fn ( Sr+1 ) / ( Fn ( Sr+1 ) )(r)
?
=
Fn ( Sr ).
Если b? ?= 1 в Fn ( Sr ), т.е. b ?? ( Fn ( Sr+1 ) )(r) , то так как длина b? в образующих a1 , . . . , an группы Fn ( Sr+1 ) / ( Fn ( Sr+1 ) )(r) равна длине b и равна p, то по
индуктивному предположению уравнение xk = b? при k > p не имеет решения,
поэтому в этом случае и уравнение xk = b не имеет решения в Fn ( Sr+1 ).
Пусть теперь b ? ( Fn ( Sr+1 ) )(r) . Предположим, что при k > p уравнение xk = b имеет решение u в Fn ( Sr+1 ). Так как по предположению b ?
( Fn ( Sr+1 ) )(r) , то b? = 1 в Fn ( Sr ), поэтому равенство uk = b влечет равенство
b?k = 1, но группа Fn ( Sr+1 ) без кручения [28], значит u? = 1.
Индукцией по k легко доказать равенство
?uk
?u
= ( 1 + u? + . . . + u?k?1 )
,
?ai
?ai
где
?v
частная производная v по ai [23].
?ai
Поэтому равенство uk = b дает в Z [ Fn ( Sr ) ] систему равенств
n
& k
i=1
?u
?b
=
.
?ai
?ai
Значит все коэффициенты элемента ?b/?ai делятся на k. Индукцией по p
легко доказать, что если элемент b группы Fn ( Sr+1 ) имеет длину p, то все
коэффициенты элемента ?b/?ai по модулю не превосходят p. Так как k > p и
все коэффициенты элемента ?b/?ai делятся на k и не превосходят по модулю p,
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
77
то ?b/?ai = 0. Тогда по теореме 3.5 из [11] b = 1 в Fn ( Sr+1 ), что противоречит
сделанному выше предположению . 2
Из леммы сразу следует [25] существование полиномиального алгоритма,
решающего проблему степеней для свободной разрешимой группы Fn ( Sr+1 ):
для определения является ли b степенью a достаточно для каждого k , по модулю
не превосходящего длины записи b в образующих группы Fn ( Sr+1 ), проверить
k
выполняется ли равенство a
= b.
Если N r-й член (Fn )r нижнего центрального ряда группы Fn , то проблема
степеней для группы Fn /N, конечно, разрешима как частный случай проблемы
вхождения: существует целое ? такое, что B ? = A?1 C ?1 тогда и только тогда, когда A?1 C ?1 входит в циклическую подгруппу, порожденную элементом
B.
Так как нам требуется полиномиальный алгоритм, то ниже приводится более
простое решение проблемы степеней для свободной нильпотентной группы.
Пусть Fn ( Nr ) свободная ранга n нильпотентная группа ступени нильпотентности r со свободными образующими a1 , . . . , an , b - ее отличный от 1
элемент. Известно [29], что b однозначно представим в виде
mt
1
b = cm
i1 ... cit ,
где ci базисные коммутаторы веса, не превосходящего r, i1 < . . . < it , m1 ,
. . . , mt целые числа, отличные от нуля.
Лемма
4. При k > max { | mj | } уравнение xk = b не имеет решения в
16j6t
Fn,r .
проведем индукцией по r. Так как Fn ( N1 ) свободная
абелева группа, то при r = 1 утверждение леммы справедливо.
Докажем утверждение для группы Fn ( Nr+1 ) при условии, что оно справедливо для группы Fn ( Nr ) .
Если b ?? ( Fn ( Nr+1 ) )r , но уравнение xk = b имеет в группе Fn ( Nr+1 )
решение a, то перейдем к фактор-группе
Доказательство.
Fn ( Nr+1 ) / (Fn ( Nr+1 ) )r ?
= Fn ( Nr ).
Обозначим через g? образ элемента g группы Fn ( Nr+1 ) при естественном
гомоморфизме группы Fn ( Nr+1 ) на фактор-группу Fn ( Nr+1 ) / ( Fn ( Nr+1 ) )r ,
q
получим в группе Fn ( Nr ) равенства a?k = b?, b? = c?qj11 ... c?jpp , где c?j1 , ..., c?jp базисные коммутаторы веса, не превосходящего r ? 1. Тогда неравенства
k > max { | mj | } > max { | qs | }
16j6t
16s6p
противоречат индуктивному предположению.
mt
1
Если же b ? ( Fn ( Nr+1 ) )r , то b = cm
i1 ... cit , где cij базисные коммутаторы
k
веса r. Равенство a = b в этом случае влечет равенство a?k = 1 в группе
78
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
Fn ( Nr ). Так как группа Fn ( Nr ) не имеет кручения, то a? = 1 в Fn ( Nr ), т.е.
a ? ( Fn ( Nr+1 ) )r , поэтому a = cpi11 ...cpitt и ci1 , ..., cit базисные коммутаторы
веса r. Так как
ci1 , ..., cit ? ( Fn ( Nr+1 ) )r = Z ( Fn ( Nr+1 ) ),
kpt
1
где Z( G ) центр группы G, то ak = ckp
i1 ... cit , поэтому получаем конъюнкцию
равенств
t
& kpi = mi .
i=1
Так как все числа m1 , . . . , mt не равны нулю, то
k 6 | m1 | 6 max { | mj | },
16j6t
что противоречит условию леммы. 2
Из леммы сразу следует существование полиномиального алгоритма, решающего проблему степеней для свободной нильпотентной группы Fn ( Nr ).
Для определения, является ли b степенью a достаточно представить b в виде
m1
t
ci1 ...cm
it , указанном в лемме, и для каждого k такого, что
| k | 6 max { | mj | },
16j6t
проверить выполняется ли в группе
Fn ( Nr )
равенство
ak = b.
Замечание 1. Очевидно, теорема 5 справедлива для любой такой нормальной подгруппы N, что в факторгруппе Fm /N полиномиально разрешима
проблема степеней.
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
[1] Tarski A., Mostowski A., Robinson R.M. Undecidable theories. NY., 1953.
[2] Lyndon R.C. Equations in free groups // Trans. Amer. Math. Soc. 1960. Volume
96. P. 445 457.
[3] Лоренц А.А. О представлении множеств решений систем уравнений с одним неизвестным в свободных группах. // Доклады АН СССР. 1968. Том
178. ќ2. С. 290 292.
[4] One-variable equations in free groups. // Proc. Amer. Math. Soc. 1968. Volune
19. P. 912 918.
[5] Хмелевский Ю.И. Системы уравнений в свободной группе. I, II. // Известия
АН СССР. Серия математика. 1971. Том 35. ќ6. С. 1237 1268. 1972. Том
36. ќ1. С. 110 179.
ОБ УРАВНЕНИЯХ В СВОБОДНЫХ ГРУППАХ, РАЗРЕШЕННЫХ. . .
79
[6] Маканин Г.С. Уравнения в свободной группе. // Известия АН СССР. Серия
математика. 1982. Том 46. ќ6. С. 1199 1273.
[7] Маканин Г.С. Универсальная теория и позитивная теория свободной группы. // Известия АН СССР. Серия математика. 1984. Том 48. ќ4. С. 735 749.
[8] Мерзляков Ю.И. Позитивные формулы на свободных группах. // Алгебра
и логика. 1966. Том 5. ќ4. С. 25 42.
[9] Разборов А.А. О системах уравнений в свободной группе. // Известия АН
СССР. Серия математика. 1984. Том 48. ќ4. С. 779 832.
[10] Gassner B.J. On braid groups. // Abh. Math. Sem. Univ. Hamburg. 1961.
Volume 25. P. 10 22.
[11] Birman J.S. Braids, links and mapping class groups. Ann.of Math. Studies ќ82.
Princeton University Press. Princeton, 1974.
[12] Коуровская тетрадь. 11-е изд., доп. Новосибирск, 1990.
[13] Малхасян А.Ш. О разрешимости в подгруппах уравнений в свободной группе. // Сборник "Прикладная математика". 1986. Том 2. С. 42 47.
[14] Diekert V. Makanin's Algorithm for Solving Word Equations with Regular
Constraints. Preliminary version of the chapter in M. Lothaire. Algebraic
Combinatorics on Words. Report Nr. 1998/02. Fakultat Informatik. Universitat
Stuttgart. 1998.
[15] Дурнев В.Г. Об уравнениях на свободных полугруппах и группах. // Матем. заметки. 1974. Том 16. ќ5. С. 717 724.
[16] Мальцев А.И. Об уравнении zxyx?1 y ?1 z ?1 = aba?1 b?1 в свободной группе.
// Алгебра и логика. 1962. Том 1. ќ5. С. 45 50.
[17] Schupp P.E. On the substitution problem for free groups. // Proc. Amer. Math.
Soc. 1969. Volume 23. P. 421 423.
[18] Edmunds C.C. On the endomorphisms problem for free group. // Com. Algebra.
1975. Volume 3. P. 7 20.
[19] Дурнев В.Г. О проблеме разрешимости для уравнений с одним коэффициентом. // Матем. заметки. 1996. Том 59. ќ6. С. 832 845.
[20] Вдовина А.А. Произведение коммутаторов и квадратов в свободной группе. // Третья международная конференция по алгебре. Сборник тезисов.
Красноярск: Изд-во. КрГУ, 1993. С. 66 67.
80
В. Г. ДУРНЕВ, О. В. ЗЕТКИНА
[21] Матиясевич Ю.В. Диофантовость перечислимых множеств. // Доклады
АН СССР. 1970. Том 130. ќ3. С. 495 498.
[22] Линдон Р., Шупп П. Комбинаторная теория групп. М.: Мир, 1980.
[23] Кроуэлл Р., Фокс Р. Введение в теорию узлов. М.: Мир, 1967.
[24] Bormotov D., Gilman R., Myasnikov A. Solving one-variable equation in free
groups. // J. Group Theory. 2009. Volume 12. ќ2. P. 317 330.
[25] Каргаполов М.И., Ремесленников В.Н. Проблема сопряженности для свободных разрешимых групп. // Алгебра и логика. 1966. Том 5. ќ6. С. 15 26.
[26] Красников А.Ф. О порождающих элементах групп вида F/[N, N ]. // Матем. заметки. 1978. Том 24. ќ2. С. 167 173.
[27] Ремесленников В.Н., Соколов В.Г. Некоторые свойства вложения Магнуса.
// Алгебра и логика. 1970. Том 9. ќ5. С. 556 578.
[28] Мальцев А.И. О свободных разрешимых группах. // Доклады АН СССР.
1960. Том 130. ќ3. С. 495 498.
[29] Нейман Х. Многообразия групп. М.: Мир, 1969.
Ярославский государственный университет им. П. Г. Демидова.
Получено 18.05.2012
Документ
Категория
Без категории
Просмотров
4
Размер файла
215 Кб
Теги
неизвестный, решение, уравнения, разрешенным, свободных, группа, ограничениями, относительные
1/--страниц
Пожаловаться на содержимое документа