close

Вход

Забыли?

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

?

Алгоритм сопряженности слов в группах Кокстера большого типа.

код для вставкиСкачать
Известия Тульского государственного университета
Естественные науки. 2012. Вып. 2. С. 13–19
Математика
УДК 519.4
Алгоритм сопряженности слов в группах
Кокстера большого типа
В. Н. Безверхний, И. В. Добрынина
Аннотация. Приводится алгоритм сопряженности слов в
группах Кокстера большого типа.
Ключевые слова: группа Кокстера большого типа, алгоритм,
сопряженность.
В [1] доказано, что в группах Кокстера большого типа разрешима
проблема сопряженности слов.
Нашей целью является описание алгоритма сопряженности слов в
группах Кокстера большого типа.
Группа G, заданная системой образующих ai , i ∈ J, |J| < ∞ и
системой определяющих соотношений (ai aj )mij = 1, i, j ∈ J, mij — элемент
симметрической матрицы Кокстера (mij ), i, j ∈ J, соответствующей данной
группе [2]: mii = 1, mij > 2, i 6= j, i, j ∈ J. Если mij > 3 для всех i 6= j, то G
называется группой Кокстера большого типа.
n
Q
Пусть Fi = hai ; a2i i, F =
∗Fi — свободное произведение циклических
i=1
групп порядка 2. Отождествим каждый образующий ai группы F с его
обратным a−1
i . Слово w = ai1 . . . ain группы G называется приведенным в F ,
если индексы рядом стоящих букв aij и aij+1 записи w различны и в w нет
подслов вида a2i , i ∈ J; длина w (w) равна n.
Обозначим через Gij группу Кокстера большого типа с образующими
ai , aj , являющуюся подгруппой G.
Обозначим через Rij множество всех нетривиальных слов, циклически
приведенных в свободном
S произведении Fij и равных 1 в группе Gij . Под R
будем понимать R =
Rij — симметризованное подмножество свободного
i,j∈J
произведения F . Тогда группа Кокстера может быть задана представлением
G = hai ; a2i , Ri, i = 1, n.
Пусть M — приведенная связная, односвязная R-диаграмма группы
Кокстера большого типа.
Простая область D диаграммы M называется деновской, если i(D) < 3.
14
В. Н. Безверхний, И. В. Добрынина
Последовательность областей D1 , D2 , . . . , Dn , n > 2, образует полосу в M ,
если:
T
1) ∀i, 1 6 i 6 n ∂Di ∂M — правильная часть M ;
2) ∀i, 1 6 i < n границы областей Di и Di+1 пересекаются по ребру;
3) i(D1 ) = i(Dn ) = 3 и ∀j, 1 < j < n, i(Dj ) = 4.
Удаление деновской области диаграммы M , то есть удаление ее
граничного пути, называется деновским сокращением диаграммы M или
R-сокращением. Будем говорить, что M является R-приведенной, если она
не содержит деновских областей.
S
T
Пусть
Π — полоса диаграммы M , ∂M = γ (∂Π ∂M ), а γ1 = ∂Π \
T
(∂Π ∂M ). Замену диаграммы M на диаграмму M1 , полученную из M
удалением полосы Π, в результате чего граничный цикл M преобразуется
в граничный цикл ∂M1 = γγ1 , назовем специальным R-сокращением или
R-сокращением. Если M не содержит полос, то назовем M специально
R-приведенной или R-приведенной.
Слово w ∈ G, G — группа Кокстера большого типа, назовем
R-приводимым, если w приведено в F и содержит подслово s, являющееся
подсловом некоторого соотношения r ∈ R, r = sb, где |b| 6 2. Назовем
w циклически R-приведенным, если все его циклические перестановки
являются R-приведенными словами.
Циклически R — приведенное слово w группы G Кокстера большого типа
назовем специально R-приводимым или R-приводимым, если в некоторой его
циклической перестановке можно выделить подслово s1 s2 . . . sn , где каждое
st содержится в некоторой группе Gij и является подсловом соотношения
st dt−1 bt dt+1 ∈ R, причем при t = 1 и t = n |d1 | = |b1 | = |d2 | = |dn | = |bn | =
= |dn+1 | = 1 и для t, 1 < t < n, |dt | = |dt+1 | = 1, |bt | = 2.
Лемма 1 [1]. Пусть w ∈ G, G — группа Кокстера большого типа, w
циклически R-приведено. Тогда если слово w0 получено из w R-приведением
или R — приведением, то |w0 | < |w|.
Теорема 1. В группе Gij разрешима проблема равенства слов.
Лемма 2. Существует алгоритм, позволяющий для любого циклически
приведенного слова w группы Кокстера большого типа выяснить, является
ли w R-приведенным.
Доказательство. Разобьем слово w на подслова w1 , w2 , . . . , wn , то есть
w = w1 w2 . . . wn , где каждое ws ∈ Gis js , s = 1, n.
Рассмотрим подслова ws , |ws | > 4, для которых в Gis js , ws ∈ Gis js ,
выясним, имеет ли решение одно из следующих уравнений: ws = 1, ws = ais ,
ws = ajs , ws ais = ajs , ws ajs = ais .
Лемма 3. Существует алгоритм, позволяющий для любого циклически
R-приведенного слова w из группы Кокстера большого типа выяснить,
является ли w R-приведенным.
Алгоритм сопряженности слов в группах Кокстера большого типа
15
Доказательство. Разбиваем циклическое слово w (слово, записанное
на окружности) на подслова w1 , w2 , . . . , wn , w = w1 w2 . . . wn , где каждое ws
принадлежит подгруппе Gis js .
Строить полосу начинаем с w1 . Пусть w1 ∈ Gi1 j1 , решаем в Gi1 j1
уравнения w1−1 ai1 aj1 ai1 = 1, w1−1 aj1 ai1 aj1 = 1, налагая на левую часть
требование циклической неприводимости в F . Допустим, что уравнение
w1−1 ai1 aj1 ai1 = 1 разрешимо в Gi1 j1 , тогда, заменив w2 на w20 = ai1 w2 ,
решаем уравнение w20 −1 aj2 ai1 = 1 в группе Gi1 j2 , w20 ∈ Gi1 j2 . Если оно имеет
решение и слово w20 −1 aj2 ai1 циклически несократимо, то полоса построена. В
противном случае решаем уравнение w20 −1 aj2 ai1 aj2 = 1 в Gi1 j2 . И так далее.
Теорема 2 [1]. В группах Кокстера большого типа разрешима проблема
равенства слов.
Выполнив в слове w−1 v все возможные сокращения в свободном
произведении F , R-сокращения в G, R-сокращения в G, смотрим равно ли
оно единице в G.
Кольцевую связную приведенную однослойную R-диаграмму M с
граничными циклами σ, τ группы Кокстера большого типа, метки которой
ϕ(σ), ϕ(τ ) приведены в F , ϕ(σ) R-приведено и специально R-приведено,
назовем особо специальной R-диаграммой,
если в M существует одна
T
0
область D такая,
T что |ϕ(∂D \ (∂D σ))| = 3, а для остальных областей D
0
0
|ϕ(∂D \ (∂D σ))| = 4. Слово ϕ(τ ) является циклически R-приведенным
и циклически R-приведенным. Замену слова ϕ(σ) словом ϕ(τ ) назовем
специальным кольцевым R-сокращением.
Лемма 4. Существует алгоритм, позволяющий для любого циклически
R-приведенного циклически R-приведенного слова w из группы Кокстера
большого типа установить, применимо ли к нему специальное кольцевое
R-сокращение.
Доказательство. Покажем, что существует алгоритм α, позволяющий
для любого специально R-приведенного слова w ∈ G выяснить, существует
ли особо специальная R-диаграмма M с внешней граничной меткой ϕ(σ) = w,
где σ, τ соответственно внешней и внутренний граничный циклы M .
(а) Разбиваем циклическое слово w на подслова w1 , w2 , . . . , wn , где каждое
из них принадлежит некоторой группе Gis js .
(б) Выясняем, существует ли такое ws ∈ {wi }, i = 1, n, ws ∈ Gis js , для
которого в Gis js разрешимо уравнение ws ais ajs ais = 1, либо ws ajs ais ajs =
= 1 и которое удовлетворяет условию (α): слово ws ais ajs ais (ws ajs ais ajs )
циклически приведено.
Допустим, что для w1 ∈ Gi1 j1 в группе Gi1 j1 разрешимо уравнение
w1 ai1 aj1 ai1 = 1, левая часть которого удовлетворяет условию (α).
(в) Проверяем, равно ли слово w0 = ai1 wai1 более короткому, чем w, слову.
Рассмотрим кольцевые связные приведенные R-диаграммы M
сопряженности слов групп Кокстера большого типа с граничными циклами
16
В. Н. Безверхний, И. В. Добрынина
σ, τ , у которых не каждая граничная область является простой. При этом
кольцевая
T R-диаграмма M может быть одного из следующих
T видов.
0
1 . σ τ = ∅, каждая область D ∈ M граничная, ∂D ∂M — несвязное
множество,
T i(D) = 2.
20 . σ Tτ 6= ∅.
T
30 . σ τ = ∅, существует область D, i(D) > 2, ∂D ∂M — несвязное
множество.
Будем говорить, что циклически несократимое слово w группы Кокстера
большого типа обладает свойством s, если w циклически R-несократимо,
циклически R-несократимо и к нему неприменимо кольцевое специальное
R-сокращение.
Лемма 5 [1]. Пусть u, v — слова группы G Кокстера большого типа,
обладающие свойством s. Тогда можно эффективно установить, являются
ли слова u, v граничными метками кольцевой связной приведенной Rдиаграммы вида 20 .
Следствие 1. Пусть w — слово группы G Кокстера большого типа,
обладающее свойством s. Тогда можно эффективно осуществить переход
от w к сопряженному слову u, |u| < |w|, с помощью кольцевой диаграммы
вида 20 .
Доказательство. Выписываем все слова, длина которых меньше |w|.
Проверяем, равно ли циклическое слово w каждому из этих слов. Таким
образом, через конечное число шагов мы можем проверить, существует ли
искомое слово u.
Лемма 6 [1]. Пусть u, v — слова группы Кокстера большого типа,
обладающие свойством s. Тогда если u, v — граничные метки кольцевой
связной приведенной R-диаграммы M вида 30 с граничными циклами
σ, τ , ϕ(σ) = u, ϕ(τ ) = v −1 , то существует простой путь χ = e1 e2 ,
принадлежащий граничному циклу некоторой области D, соединяющей
граничные вершины из σ и τ , метка которого может быть эффективно
определена.
Следствие 2. Пусть w — слово группы G Кокстера большого типа,
обладающее свойством s. Тогда можно эффективно осуществить переход
от w к сопряженному слову u, |u| < |w|, с помощью кольцевой диаграммы
вида 30 .
Доказательство. Разбиваем циклическое слово w в направлении
против часовой стрелки на подслова w1 , w2 , . . . , wn , где каждое принадлежит
некоторой группе Gis js . Пусть w1 ∈ Gij . Выписываем все слова,
длина которых меньше |w|. Проверяем, равно ли циклическое слово
v = ai aj w1 w2 . . . wn aj ai (v = aj ai w1 w2 . . . wn ai aj ) каждому из этих слов.
Таким образом, применяя указанный процесс для различных разбиений
словa w, мы через конечное число шагов можем проверить, существует ли
искомое слово u.
Алгоритм сопряженности слов в группах Кокстера большого типа
17
Лемма 7 [1]. Пусть u, v — слова группы Кокстера большого типа,
обладающие свойством s. Тогда можно эффективно установить, являются
ли u, v граничными метками кольцевой связной приведенной R-диаграммы
M вида 10 .
Следствие 3. Пусть w — слово группы G Кокстера большого типа,
обладающее свойством s. Тогда можно эффективно осуществить переход
от w к сопряженному слову u, |u| < |w|, с помощью кольцевой диаграммы
вида 10 .
Доказательство. Разбиваем циклическое слово w в направлении
против часовой стрелки на подслова w1 , w2 , . . . , wn , где каждое принадлежит
некоторой группе Gis js . Пусть w1 ∈ Gij , wn ∈ Gkj . Выписываем все слова,
длина которых меньше |w|. Проверяем, равно ли циклическое слово
v = aj w1 w2 . . . wn aj каждому из этих слов.
Таким образом, применяя указанный процесс для различных разбиений
словa w, мы через конечное число шагов можем проверить, существует ли
искомое слово u.
Пусть w — произвольное слово группы Кокстера большого
типа. Рассмотрим следующие преобразования, укорачивающие длину
циклического слова w:
π1 ) циклическое сокращение w в свободном произведении F ;
π2 ) циклическое R-сокращение в G;
π3 ) циклическое R-сокращение в G;
π4 ) кольцевое специальное R-сокращение в G;
π5 ) переход от w к сопряженному слову u, |u| < |w| с помощью кольцевой
диаграммы вида 10 ;
π6 ) то же, что π5 ), но с помощью кольцевой диаграммы вида 20 ;
π7 ) то же, что π5 ), но с помощью кольцевой диаграммы вида 30 .
Слово w, полученное из v применением к нему преобразований π1 ) − π7 )
в G, назовем тупиковым для v, если оно инвариантно относительно этих
преобразований.
Из лемм 2-7 следует, что для любого слова v ∈ G можно эффективно
построить соответствующее ему тупиковое слово w.
Лемма 8 [1]. Пусть v ∈ G, G — группа Кокстера большого типа, v
обладает свойством s и w — тупиковое для v слово. Тогда никакое слово
u ∈ G, |u| < |w|, не сопряжено с v.
Лемма 9 [1]. Пусть M — связная приведенная минимальная R —
диаграмма группы Кокстера большого типа с граничными циклами σ, τ ;
ϕ(σ), ϕ(τ ) удовлетворяют условию s. Тогда если ϕ(σ) = x, то ϕ(τ ) = y, где
x, y ∈ {a1 , . . . , an }, {ai } — множество образующих группы G.
Пусть M — кольцевая R-диаграмма, v — произвольнаяT точка,
принадлежащая некоторому замкнутому ребру e ∈ M , e = e0 e00 , e0 e00 = v.
Тогда замкнутый путь l ∈ M с начальной и конечной точкой v:
l = e0−1 e1 . . . en t, где t = e0 либо t = e00−1 , либо l = e00 e01 . . . e0n t0 , где t0 = e0 либо
18
В. Н. Безверхний, И. В. Добрынина
t0 = e00−1 назовем циклическим в M , если l гомотопен τ , соответственно
σ. Кратчайший из всех циклических путей кольцевой R-диаграммы M ,
проходящих через некоторую точку v, принадлежащую ребру e, e ∈ M ,
назовем циклическим геодезическим путем с началом и концом в v.
Теорема 3. Существует алгоритм, позволяющий для любых слов u, v
группы Кокстера большого типа G установить, сопряжены они в G или
нет.
Доказательство. Пусть u, v — слова, принадлежащие группе Кокстера
большого типа, заданной на множестве образующих A = {a1 , a2 , . . . , an } с
помощью матрицы Кокстера (mij )i,j∈J , |J| = n. Будем считать, что слова u,
v являются тупиковыми, заранее приведя их к такому виду.
Пусть u = x, x ∈ {ai }i=1,n , тогда v = y, y ∈ {ai }, i = 1, n. Проверяем,
можно ли построить такую последовательность x = x0 , . . . , xi , . . . , xn = y,
xi ∈ {ai }i=1,n , что любые два элемента xi−1 , xi , i = 1, n, сопряжены в Gxi−1 xi
максимальным куском определяющего соотношения группы Gxi−1 xi .
Пусть слова u, v не являются образующими G. В этом случае |u| = |v|.
1. Построим множество всех циклически несократимых слов, длина d
которых равна |u|.
Рассмотрим последовательность таких слов, соответствующую слову u:
u(0) , u(1) , . . . , u(k) ,
(1)
где ∀i, i = 1, k, |u(i) | = |u|, u(0) = u.
2. На основании (1) построим новую последовательность. Выделим из
(1) слово u(0) и все его циклические сдвиги. Получим множество слов
{u(0) } и вычеркнем элементы этого множества из (1). Затем берем первое
слово из оставшейся последовательности. Пусть это будет u(1) . Включаем
u(1) и его циклические сдвиги в множество {u(1) } и так далее. Получаем
последовательность
{u(0) }, {u(1) }, . . . , {u(m) },
(2)
где для некоторого t {u(t) } = {v}, t = 1, m.
3. Начиная с {u(0) }, выполняем следующий алгоритм:
а) сопрягаем произвольный элемент из {u(i) } словом длины 1,
то есть образующим. Если найдется такой элемент u0 из множества
{u(i) } (и образующий), так что после сопряжения не меняется его
длина и u0 переводится в некоторое слово из множества {u(l) },
l ∈ {1, ..., m}, {u(i) } 6= {u(l) }, то {u(i) } дальше не рассматриваем. Если
{u(l) } 6= {v}, то вновь выполняем пункт 3a) для {u(l) }.
б) если {u(l) } = {v}, то u, v сопряжены.
4. Если для любого элемента из {u(i) } не выполняется 3а), то сопрягаем
элементы из {u(i) } словами длины 2. Если найдется такой элемент из {u(i) },
который сопряжением переводится в некоторый элемент множества {v}, то
u, v сопряжены.
Алгоритм сопряженности слов в группах Кокстера большого типа
19
5. Если для любого элемента из {u(i) } не выполняются условия 3а) и 4,
то u, v не сопряжены.
Теорема доказана.
Авторы благодарят профессора М. М. Глухова за постановку задачи.
Список литературы
1. Безверхний В.Н., Добрынина И.В. Решение проблемы сопряженности слов
в группах Кокстера большого типа // Чебышевский сборник: Труды V
Международной конференции «Алгебра и теория чисел: современные проблемы
и приложения». 2003. Т.4, №1(5). С.10–33.
2. Appel K. One Artin groups and Coxeter groups of large type // Contemp. Math.
1984. V.33. P.50–78.
Безверхний Владимир Николаевич (vnbezv@rambler.ru), д.ф.-м.н.,
профессор, кафедра алгебры, математического анализа и геометрии,
Тульский государственный педагогический университет им. Л.Н. Толстого.
Добрынина Ирина Васильевна (dobrynirina@yandex.ru), д.ф.-м.н.,
доцент, кафедра алгебры, математического анализа и геометрии, Тульский
государственный педагогический университет им. Л.Н. Толстого.
Оn the conjugacy algorithm for Coxeter groups of large type
V. N. Bezverkhnii, I. V. Dobrynina
Abstract. We give the conjugacy algorithm for Coxeter groups of large type.
Keywords: Coxeter group of large type, algorithm, conjugacy.
Bezverkhnii Vladimir (vnbezv@rambler.ru), doctor of physical and mathematical sciences, professor, department of algebra, mathematical analysis and
geometry, Tolstoy Tula State Pedagogical University.
Dobrynina Irina (dobrynirina@yandex.ru), doctor of physical and mathematical sciences, assistant professor, department of algebra, mathematical analysis
and geometry, Tolstoy Tula State Pedagogical University.
Поступила 10.05.2012
Документ
Категория
Без категории
Просмотров
4
Размер файла
594 Кб
Теги
типа, алгоритм, большого, группа, слова, кокстера, сопряженности
1/--страниц
Пожаловаться на содержимое документа