\documentclass[twoside]{mfitjournal}
\usepackage{amsbib}
\clubpenalty=10000
\widowpenalty=10000
\newcommand{\MFITnumber}{1}
\newcommand{\MFITom}{12}
\newcommand{\MFITyear}{2016}
\newcommand{\ISSN}{ISSN 2079-6641}
\newcommand{\OISSN}{ISSN 2079-665X}
\newcommand{\DOI}{DOI: 10.18454/2079-6641-\MFITyear-\MFITom-\MFITnumber-\firstpage-\lastpage} %класс статьи
\renewcommand{\firstpage}{5}
\renewcommand{\lastpage}{12}
%\engshortpartit{}
%\shortpartit{}
\SECC{}
\ESECC{}
\begin{document}
\udk{УДК 512.24}% код направления
\rustitle{НАХОЖДЕНИЕ ИНДЕКСА ПОДГРУППЫ И ПРОБЛЕМА ВХОЖДЕНИЯ}
\shorttitle{Нахождение индекса подгруппы и проблема вхождения}%
\author{А.\,П.~Паровик}
\shortauthor{Горюшкин~А.\,П.}
\institute{Камчатский государственный университет имени Витуса Беринга, 683032, \\ г. Петропавловск-Камчатский, ул. Пограничная, 4}
\email{E-mail:}{as2021@mail.ru}
\workabstract {Для отдельных классов групп устанавливаются связи между двумя алгоритмическими проблемами: проблемой вычисления индекса подгруппы и проблемой вхождения.}
\keywords{\it Ключевые слова: группа, подгруппа, индекс подгруппы, алгоритмическая проблема, свободное произведение, прямое произведение}
\rcopyr{Горюшкин~А.\,П.}
%\rdate{Поступила в редакцию 11.09.2010~г.}
%\revisiondate{В окончательном варианте: 11.09.2010}
\msc{MSC 18A32} %http://www.ams.org/msc/
\engtitle{INDEX OF A SUBGROUP FINDING AND OCCURENCE PROBLEM}
%\engshorttitle{Index of a subgroup finding and occurence problem}
\engauthor{A.\,P.~Goryushkin}
%\eauthor{}\engshortauthor{Goryushkin~A.\,P.}
\enginstitute{Vitus Bering Kamchatka State University, 683031, Petropavlovsk-Kamchatsky, \\ Pogranichnaya st., 4, Russia}
\engabstract{For separate classes of groups some relationships are revealed between two algorithmic prob-lems: problem calculation of index of a subgroup and occurrence problem.}
\engkeywords{\it Key words: group, subgroup, index of a subgroup, algorithmic problem, free product, direct product, occur-rence problem.}
\email{E-mail:}{as2021@mail.ru}
\engcopyr{Goryushkin~A.\,P.}
%\engdate{Original article submitted 11.09.2010.}
%\engrevisiondate{Revision submitted: 11.09.2010}
\pagestyle{myheadings}
\maketitle
\engmaketitle
\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE, RO]{\ISSN}
\fancyhead[RE]{Паровик~А.\,П.}
%\fancyhead[LO]{Нахождение индекса подгруппы и проблема вхождения}
\cfoot{\arabic{page}}
\newpage
\section*{Введение}
Проблема индекса для конечно определенной группы G состоит в вопросе о существовании алгоритма, позволяющего по любому конечному множеству элементов $h_i (i = 1, 2,\dots, m)$ группы $G$ выяснить, конечный или бесконечный индекс в $G$ имеет подгруппа $H = \text{гр}(h_1, h_2,\cdots, h_m)$, порожденная этим множеством.
В конечно порожденной группе содержится лишь конечное число подгрупп для каждого данного конечного индекса. Поэтому если в группе $G$ разрешимы проблема вхождения и проблема индекса, то получив информацию, что индекс подгруппы $H$ в $G$ конечен, простым перебором подгрупп конечного индекса в конечное число шагов можно этот индекс вычислить точно (детальное построение см., например, в работе \cite{Gor}, глава 1, § 8, стр. 42–44).
Частным случаем вычисления индекса является определение индекса единичной подгруппы группы $G$, т. е. нахождение порядка группы $G$. Свойство «быть конечной» для группы является марковским свойством, и поэтому в классе всех конечно определенных не существует алгоритма для узнавания, конечна или нет данная группа (впервые показано в работе С. Адяна \cite{Adyan}).
\section*{Примеры групп с разрешимой проблемой индекса}
Для конкретной конечно определенной группы $G$ вычисление ее порядка не является массовой задачей. Однако, если $G$ – бесконечная, то в ней есть подгруппы бесконечного и конечного индексов. Такие индексы имеют, например, тривиальные подгруппы, но, возможно, что в $G$ найдутся и другие подгруппы, как конечного, так и бесконечного индекса.
Если $G$ – бесконечная простая конечно определенная группа, то из разрешимости в $G$ проблемы вхождения следует разрешимость проблемы индекса, так как в такой группе всего одна подгруппа конечного индекса – сама $G$.
Однако обратная ситуация с простыми группами существенно сложнее. Каждая счетная группа изоморфно вложима в двапорожденную простую группу (впервые показано в работе \cite{Gor2}). В частности, конечно определенная группа $S$ с неразрешимой проблемой равенства (а, следовательно, и с неразрешимой проблемой вхождения) так же изоморфно вкладывается в некоторую простую два-порожденную группу $G$. В работе Кузнецова \cite{Kuz} установлено, что в каждой рекурсивно определенной простой группе разрешима проблема равенства. Это значит, что двапорожденная простая группа, содержащая такую $S$, не только не является конечно определённой, она даже не может быть рекурсивно представлена.
Проблема вхождения фактически обсуждается в курсе линейной алгебры. Критерий совместности системы линейных уравнений является решением проблемы вхождения в конечно мерных векторных пространствах. Алгоритм, опирающийся на этот критерий, состоит в вычислении размерности двух вспомогательных подпространств. Эта размерность находится с помощью последовательного изменения порождающих множеств подпространств.
\begin{figure}
\label{pic:mypic}
\centering
\includegraphics[scale=0.5]{1.jpg}
\caption{Это просто пример вставки рисунка}
\end{figure}
Для нахождения индекса подгруппы $H$ в группе $G$ точно так же можно изменять порождающее множество для $H$. Порождающее множество подгруппы видоизменяется с помощью преобразований, аналогичных элементарным преобразованиям порождающего множества подпространства векторного пространства. Преобразования в группе следующие:
– замена элемента $x$ на $x^{-1}$;
– замена элемента $x$ на элемент $xy$ , где $x\neq y$;
– удаление единичного элемента.
Например, если $H$ – подгруппа бесконечной циклической группы $F_1 = < a >$, и $H = \text{гр}(a^{m_1},a^{m_2},\cdots,a^{m_k})$, где $m_1, m_2,\cdots, m_k \in Z$, то с помощью элементарных преобразований можно найти единственный порождающий подгруппы $H$, равный $a^s$, где $s = \text{НОД}(m_1, m_2,\cdots, m_k)$. Индекс равен числу $s$. Таким образом, задача нахождения индекса подгруппы бесконечной циклической группы сводится к отысканию наибольшего общего делителя конечного множества целых чисел. Иначе говоря, проблема индекса для бесконечной циклической группы алгоритмически разрешима.
Бесконечная циклическая группа является частным случаем свободной группы. Группа $<a> = F_1$ -- это свободная группа ранга 1. Задача вычисления индекса произвольной подгруппы свободной группы $F_r$ любого ранга $r$ так же имеет алгоритмическое решение.
Пусть $H = \text{гр}(h_1, h_2,\cdots, h_m)$ -- конечно порожденная подгруппа свободной группы $F_n$. С помощью преобразований порождающего множества в конечное число шагов можно получить свободные порождающие для подгруппы $H$, и таким образом найти ранг $H$. Такой способ получения свободных порождающих подгруппы свободной принято называть \textit{методом Я. Нильсена} (детали доказательства см. например, \cite{Lin}, глава 1, п. 2, стр. 16–21).
О. Шрейер, оперируя не только порождающими элементами подгруппы, но и представителями смежных классов, установил связь между индексом подгруппы свободной группы, рангом этой подгруппы и рангом исходной свободной группы (см. например, \cite{Lin}, стр. глава 1, п. 3, стр. 33–34). Если подгруппа $H$ ранга $k$ имеет конечный индекс в свободной нециклической группе ранга $r$ имеет, то этот индекс равен
\[
\dfrac{k-1}{r-1}.
\]
С помощью формулы Шрейера проблема индекса подгруппы свободной группы сводится к вычислению ранга подгруппы, который можно найти с помощью метода Нильсена (подробнее см. в работе Карраса и Солитэра \cite{Kar}). Таким образом, проблема индекса в свободных группах \textit{алгоритмически разрешима}.
\section*{Примеры групп с неразрешимой проблемой индекса}
Покажем, что не в каждой конечно определенной группе проблема индекса алгоритмически разрешима.
\begin{theorem}[1]
\label{t1}
В прямом произведении двух свободных нециклических групп одинакового ранга проблема конечности индекса алгоритмически неразрешима.
\end{theorem}
\begin{proof}
Пусть группа $G$ является прямым произведением двух свободных групп $A = <a_1, a_2,\cdots, a_m>$ и $B = < b_1, b_2,\cdots, b_m >$, где $m\geq 2$.
Рассмотрим произвольную конечно определенную группу $R$, заданную представлением
\[
R = <r_1, r_2,\cdots, r_k; w_1(r_i),\cdots, w_n(r_i)>.
\]
Пусть число $s$ удовлетворяет неравенству
\[
s\geq \dfrac{k-1}{m-1}.
\]
В группе $A$ есть подгруппы любого конечного индекса; выберем в $A$ подгруппу $P$ индекса $s$. По формуле Шрейера ранг подгруппы $P$ равен $s(m-1) + 1$, причем
\[
s(m-1)+1\geq k.
\]
Если ранг подгруппы $P$ окажется строго больше $k$, то представление группы $R$ пополним еще $s-k$ порождающими элементами и приравняем эти элементы к единице. Без ограничения общности можно считать, что это уже сделано, т. е. $s=k$. Пусть $P$ элементы $p_1, p_2,\cdots, p_k$ свободно порождают подгруппу $P$:
\[
P = <p_1, p_2,\cdots, p_k>.
\]
В группе $B$ выберем подгруппу $Q$ ранга $k$, индекса $s$ в $B$ и со свободными порождающими элементами $q_1, q_2,\cdots, q_k$:
\[
Q = < q_1, q_2,\cdots, q_k >.
\]
Подгруппа группы $G$, порожденная подгруппами $P$ и $Q$, изоморфна прямому произведению $P\times Q$ и имеет в группе $G$ конечный индекс.
Рассмотрим теперь нормальное замыкание элементов $w_1(p_i),\cdots, w_n(p_i)$ в группе $P$:
\[
H_1 = \text{гр}(w_1(p_i),\cdots, w_n(p_i), p_1q_1,\cdots, p_kq_k).
\]
Элементы $r_i$, $q_i$ лежат в различных прямых сомножителях группы $G$, поэтому они перестановочны:
\[
r_iq_i=q_i r_i.
\]
Это значит, что для любого слова $\varphi$ выполняется равенство
\[
\varphi(p_iq_i)= \varphi(p_i) \varphi(q_i)
\]
и поэтому для любого $w_j(p_i)$ имеем равенство:
\[
\varphi^{-1}(p_iq_i) w_j(p_i)\varphi(p_iq_i) = \varphi^{-1}(q_i)\varphi^{-1}(p_i) w_j(p_i)\varphi(p_i)\varphi(q_i) = \varphi^{-1}(p_i) w_j(p_i)\varphi (p_i).
\]
Отсюда следует, что подгруппа $N_1$ содержится в подгруппе $H_1$:
\[
N_1 \subset H_1 \cap P.
\]
С другой стороны, если $\varphi( w_n(p_i), p_iq_i)$ принадлежит $P$, то сумма степеней в слове $ \varphi $ для каждого $q_i$ равна нулю, а это означает, что $\varphi(w_j(p_i), p_iq_i)\in N_1$. Таким образом,
\[
N_1=H_1\cap P.
\]
Проделаем аналогичные построения во втором прямом множителе. Пусть $N_2$ – нормальное замыкание элементов $w_1(q_i),\cdots, w_n(q_i)$ в группе $Q$:
\[
N_2 = <w_1(q_i),\cdots, w_n(q_i)>
\]
и
\[
H_2 = \text{гр}(w_1(q_i),\cdots, w_n(q_i), p_1q_1,\cdots, p_kq_k).
\]
Точно так же, как и для групп $H_1$, $N_1$ и $P$, теперь получаем для групп $H_2$, $N_2$ и $Q$:
\[
N_2=H_2\cap Q.
\]
Для любого $j=1, 2,\cdots, n$ имеем:
\[
w_j(p_iq_i)=w_j(p_i) w_j(q_i),
\]
и, следовательно,
\[
w_j(q_i)=w^{-1}_j(p_i)w_j(p_iq_i).
\]
Это означает, что $H_2 \subset H_1$; по тем же соображениям верно и обратное включение: $H_1 \subset H_2$. Группы $H_1$ и $H_2$ совпадают; обозначим их одной буквой $H$:
\[
H = H_1 = H_2.
\]
Пересечения с подгруппами $P$ и $Q$,
\[
H\cap P = N_1, H\cap Q = N_2.
\]
Если группа $R$ -- конечна, то индексы $N_1$ и $N_2$ в подгруппах $P$ и $Q$ конечны, но $P$ и $Q$ подгруппы конечного индекса в прямых множителях, и, следовательно, индекс $ \left[G: H\right] $ конечен.
Наоборот, если индекс $H$ в группе $G$ конечен, то конечен индекс $N_1$ в подгруппе $P$, и, следовательно, группа $R$ – конечна.
Таким образом, проблема индекса в группе $G$ эквивалентна проблеме конечности в классе всех конечно определенных групп, Проблема конечности неразрешима, а, значит, и проблема индекса для конечно определенной группы тоже алгоритмически неразрешима.
\end{proof}
Алгоритмическая неразрешимость проблемы означает, в частности, что машинного решения такой задачи не существует. Например, никакая техника никогда не сможет по единой программе всегда однозначно отвечать на вопрос, конечен или бесконечен индекс произвольно заданной конечно порожденной подгруппы в группе
\[
G = F_2 \times F_2 = <a, b, c, d; aca^{-1}c^{-1}, ada^{-1}d^{-1}, bcb^{-1}c^{-1}, bdb^{-1}d^{-1}>.
\]
Отметим, впрочем, что в некоторых случаях вычисление индекса подгруппы в конечно определенной группе можно все-таки выполнить с помощью техники. Например, пакет символьных вычислений Maple 18 иногда позволяет вычислить индекс подгруппы в конечно определенной группе, если этот индекс конечен и не превышает числа 128000. Однако машинные результаты, как правило, требуют дополнительной «ручной» проверки. Примеры такого рода вычислений и ручных проверок представлены в работах \cite{Gor3} – \cite{Gor6}.
С. Михайловой в работе \cite{Mikh1} показано, что для группы $F_2 \times F_2$ проблема вхождения неразрешима. Это доказательство (§ 2, теорема 1, стр. 242–244 в \cite{Mikh1}) легко переносится и на более общий случай прямого произведения $F_r \times F_r$ двух свободных групп ранга $r\geq 2$. Таким образом, возникает бесконечная серия конечно определенных групп, для которых проблема вхождения и проблема индекса оказались эквивалентными (обе неразрешимы).
Заметим, что в свободных группах разрешимы и проблема вхождения, и проблема индекса, однако прямое произведение не сохранило ни того, ни другого.
Свободное произведение, в отличие от прямого, разрешимость проблемы вхождения сохраняет: из разрешимости проблемы вхождения в множителях $A$, $B$ следует разрешимость проблемы вхождения в свободном произведении $G = A\ast B$ (Михайлова, \cite{Mikh2}).
\section*{Связь проблемы индекса и проблемы вхождения для свободно разложимых групп}
Методом, близким к методу Нильсена для свободных групп, Д. Молдаванский в работе \cite{Mol1} уточнил результат Михайловой о решении проблемы вхождения в свободном произведении.
Пусть $W$ -- некоторое множество слов из свободного произведения $G = A\ast B$. Расширим множество W до множества $W^{\pm 1}$, замкнутого относительно операции обращения:
\[
W^{\pm 1}=\{g \mid g \in W ~\text{или}~ g^{-1} \in W \}.
\]
Начальный отрезок элемента $g$ из $W$ называют изолированным в $W$, если он не является начальным отрезком никакого другого элемента из $W^{\pm 1}$ . Пусть $W_v(X)$ - множество всех элементов из $W$, имеющих вид $vxv^{-1}$, где $x\in X (X = A~\text{или}~X = B)$. Пару $(v, X)$ называют \textit{типом трансформ} из $W_v(X)$. Символом $S(v, X)$ обозначим множество всех элементов из множителя $X$, являющихся $(l(v)+1)$ слогом некоторого элемента $g$ из множества $(W\setminus W_v(X))^{\pm 1}$, причем начальным отрезком элемента $g$ является $v$, т. е. несократимая форма $g$ имеет вид: $g = vsz$, где $s \in S(v, X)$.
Следуя \cite{Gor5}, назовем множество элементов $W$ из свободного произведения \textit{нильсеновским множеством}, если:
– большой начальный отрезок каждого элемента из $W^{\pm 1}$ изолирован в $W$;
– левая половина каждого элемента четной длины из $W^{\pm 1}$ изолирована в $W$;
– для каждого типа $(v, X)$ множество $S(v, X)$ не содержит элементов из подгруппы $v^{-1}\text{гр}(W_v(X))v$, а множество $S(v, X)$ состоит из представителей различных правых смежных классов группы подгруппе $v^{-1}\text{гр}(W_v(X))v$.
– левая половина каждого элемента из $W^{\pm 1}$, не являющегося трансформой, изолирована в $W$;
Как и для свободных групп, преобразования Нильсена множества $M$ элементов свободного произведения $G$ это:
– замена некоторого элемента $x$ из $M$ элементом $x^{-1}$,
– замена некоторого элемента $x$ элементом $xy^\epsilon (\text{где}~ y \in M, y\neq x, \epsilon = \pm 1)$.
– выбрасывание единицы.
Индукцией по суммарной длине всех слов множества $W$ устанавливается, что с помощью конечной последовательности преобразований любое конечное множество $W$ можно превратить в нильсеновское множество, причем процедура преобразований эффективна, если в свободных множителях разрешима проблема вхождения. Свойства нильсеновского множества означают, что полученные порождающие подгруппы $H$ являются порождающими разложения Куроша- Маклейна этой подгруппы (Молдаванский \cite{Mol1} и \cite{Mol2}).
Таким образом:
– если в группах $A$ и $B$ разрешима проблемы вхождения, то существует эффективная процедура перехода, переводящее любое множество элементов $W$ группы $G$ в нильсеновское множество $W_1$;
– из разрешимости проблемы вхождения в группах $A$ и $B$ следует разрешимость проблемы вхождения в группе $G$;
– если $W_1$ -- нильсеновское множество порождающих для подгруппы $H$ группы $G$, то $H$ является свободным произведением групп, порожденных трансформами одного типа, и бесконечных циклических групп, порожденных элементами из $W_1$, не являющихся трансформами, причем это разложение для $H$ является разложением Куроша-Маклейна.
\begin{theorem}[2]
\label{t2}
Если в группах $A$, $B$ разрешима проблема вхождения, то в свободном произведении $G = A\ast B$ разрешима проблема индекса.
\end{theorem}
\begin{proof}
Пусть $W$ -- некоторое конечное множество элементов из группы $G$, и $H$ -- подгруппа, порожденная множеством $W$. Так как существует эффективная процедура, переводящая каждое конечное множество в нильсеновское, можно считать, что уже $W$ является нильсеновским множеством.
Пусть $ v_iA_iv^{-1}_i$ , $i = 1, 2,\cdots, m$, и $ w_j B_jw^{-1}_j $, $j = 1, 2,\cdots, n$ -- подгруппы, порожденные типами трансформ $\left(v_i,A_i\right)$ и $ \left(w_j,B_j\right) $ соответственно, а $F$ -- свободная группа, порожденная элементами из $W$, не являющимися трансформами. Тогда согласно теореме Куроша о подгруппах свободного произведения подгруппу существуют такие системы представителей двойных смежных классов $s_A(HgA)$ и $s_B(HgB)$, что
– $s_A(HA) = s_B(HB) = 1$;
– если $HgA \neq HA$, то $s_A(HgA)$ заканчивается $B$-слогом, и если $HgB\neq HB$, то $s_A(HgB)$ заканчивается $A$- слогом;
– группа $H$ является свободным произведением;
\[
H=F \ast \prod\limits_{{X \in \{A,B\}},{g \in G}} \ast s_X\left(HgX\right)X\left[s_X\left(HgX\right)^{-1}\right] \cap H,
\]
где $F$ -- свободная группа, не содержащая ни одного сопряжения из групп $A, B$.
В работе \cite{Gor} показано, что если $G$ – нетривиальное свободное произведение $A \ast B$, и $H$ -- конечно разложимая подгруппа в $G$, то индекс разложения $[G : (H, A)]$ по двойному модулю конечен тогда и только тогда, когда индекс $[G: H]$ конечен (\cite{Gor}, глава 1, § 2, стр. 15 – 17).
Рассмотрим разложение группы $G$ по двойному модулю
\[
G = Hg_1A + Hg_2A +\cdots
\]
Если множество $\{g, g_2,\cdots\}$ образует полную систему представителей для разложения $G\mod(H, A)$, то в этом множестве найдется такое подмножество $\{g_{\alpha_1},\cdots,g_{\alpha_m}\}$, что для $i = 1, 2,\cdots, m$
\[
g_{\alpha_i}=v_i \mod(H,A).
\]
Кроме того, для каждого элемента $g$ из $G$, если $g$ сравним по $\mod(H, A)$ с некоторым элементом из разности
\[
Y=\{g,g_2,\cdots\}\setminus\{g_{\alpha_1},\cdots,g_{\alpha_m}\},
\]
то пересечение $H \cap gAg^{-1}$ равно единичной подгруппе.
Аналогичное утверждение выполняется и для подгруппы $B$.
Далее рассмотрим три случая.
\textbf{Случай 1.} Оба свободных множителя $A$ и $B$ является бесконечными группами.
Пусть ранг свободной группы $F$ в разложении для подгруппы $H$ оказался равным $r$. Число $r$, а также числа $m, n$ эффективно вычислимы. Обозначим
\[
k = m+n+r-1.
\]
При фиксированном разложении $G = A \ast B$ число $k$ является инвариантом всевозможных разложений Куроша для подгруппы $H$. В частности, если
\[
H=F_1\ast\prod\limits_{\nu}\ast H_\nu,
\]
– разложение Маклейна для группы $H$, то ранг подгруппы $F_1$ тоже равен $r$.
В работе Куна \cite{Kuh} установлено, что разложение Маклейна обладает следующим свойством: если подгруппа $H$ имеет конечный индекс в свободном произведении $A \ast B$, то ранг свободной части $F_1$ для разложения $H$ равен
\[
[G : H]-[G : (H, A)]-[G : (H, B)] + 1.
\]
Заметим теперь, что в рассматриваемом случае из конечности индекса $H$ в $G$ следует, что $[G: (H, A)] = m$, а $[G: (H, B)] = n$.
Предположим, что $[G: (H, A)] > m$. Тогда множество $Y$ не пусто, следовательно, найдется такой элемент $g$ из $G$, что пересечение $H\cap gAg^{-1}$ единично.
Из того, что группа $A$ бесконечна, следует бесконечность индекса подгруппы $H$ в группе $G$.
Точно такие же рассуждения подходят и для подгруппы $B$.
Отметим еще, что можно считать, что $k > 0$. Действительно, если оказалось, что $k = 0$, то $H$ является бесконечной циклической группой или подгруппой из сопряжения множителя, и, следовательно, индекс $H$ в $G$ бесконечен.
Рассмотрим множество $\Re$ подгрупп группы $G$ индекса $k$ в $G$,
\[
\Re = {K\leq G \mid [G: K] = k}.
\]
Множество $ \Re $ конечно, и можно эффективно найти множества систем порождающих для подгрупп из $ \Re $. Из разрешимости проблемы вхождения в группе $G$ следует разрешимость проблемы вхождения произвольной конечно порожденной подгруппы $P$ из $G$ в множество $ \Re $. Теперь если $H$ имеет конечный индекс в $G$, то выполняется равенство
\[
r = [G: H]-m-n+1,
\]
т. е. $H$ принадлежит $ \Re $. Другими словами, подгруппа $H$ имеет конечный индекс в $G$ тогда и только тогда, когда $H$ лежит $\Re$. Этим заканчивается рассмотрение случая 1.
\textbf{Случай 2.} Группа $G$ является свободным произведением $A\ast B$ конечной группы $A$ и бесконечной группы $B$.
Рассмотрим нормальное замыкание $\bar{B}$ свободного множителя $B$ в группе $G$. Подгруппа $\bar{B}$ является свободным произведением сопряжений подгруппы с помощью элементов из $A$,
\[
\bar{B}=\prod\limits_{a\in A}\ast B^a,
\]
т. е. – это свободное произведение
\[
\bar{B}=B\ast\prod\limits_{a\in A\setminus \{1\}}\ast B^a,
\]
где оба множителя -- бесконечные группы.
Обозначим через $R$ подгруппу группы $G$, порожденную подгруппами $H$ и $ \bar{B} $ , а буквой $D$ обозначим пересечение $ \bar{B}\cap H $. Подгруппа $R$ имеет конечный индекс в $G$, а так как в группе $G$ разрешима проблема вхождения, порождающие для $R$ можно эффективно найти. Кроме того, можно эффективно найти множество $r_1, r_2,\cdots, r_s$, являющееся полной системой представителей правых смежных классов для $ R\mod\bar{B} $. Пересечения $ H\cap Dr_i, i=1,\cdots,s$ не пусты; и если выбрана система элементов $ h_i,\cdots,h_s $ по одному из каждого множества, то это множество образует полную систему представителей правостороннего разложения $H\mod D $. Снова из разрешимости проблемы вхождения в группе $G$ следует существование эффективной процедуры для нахождения множества $ h_i,\cdots,h_s $.
Теперь можно найти порождающие элементы для подгруппы $D$. Так как индекс подгруппы $\bar{B} $ в группе $G$ конечен, подгруппа $H$ имеет конечный индекс в $G$ тогда и только тогда, когда $D$ имеет конечный индекс в $\bar{B}$.
Таким образом, случай 2 сводится к случаю 1.
\textbf{Случай 3.} Группа $G$ – свободное произведение неединичных конечных групп $A$ и $B$.
Рассмотрим $K = [A, B]$, взаимный коммутант $A$ и $B$. Так же, как в случае 2 можно найти порождающие пересечения $D = H \cap K$.
Таким образом, если ранг группы $D$ больше единицы, свести рассматриваемую ситуацию к случаю 1. Если же ранг $D$ равен единице, то $G$ является бесконечной группой диэдра, в которой подгруппа $H$ имеет конечный индекс тогда и только тогда, когда порядок H больше двух.
\end{proof}
Итак, для разрешимости проблемы индекса в свободном произведении $A \ast B$ достаточно разрешимости проблемы вхождения в группах $A$ и $B$.
Покажем, что это достаточное условие является необходимым.
\begin{theorem}[3]
Если в нетривиальном свободном произведении $A\ast B$ разрешима проблема индекса, то в свободных множителях $A$, $B$ разрешима проблема вхождения.
\end{theorem}
\begin{proof}
Покажем, что из разрешимости проблемы индекса в группе $A\ast B$ следует разрешимость проблемы вхождения в группе $A$.
Пусть $A_1$ - произвольная конечно порожденная подгруппа группы $A$, а $x$ – произвольный элемент из группы $A$. С помощью алгоритма, решающего проблему индекса в группе $G$, выясним, принадлежит элемент $x$ подгруппе $A_1$ или нет. Возьмем $b_0$ – неединичный элемент из подгруппы $B$. Алгоритм, решающий проблему вхождения в группе $A$ будет зависеть от того, равен порядок подгруппы B двум или нет.
\textbf{Случай 1.} Порядок группы $B$ больше двух. В группе $G$ рассмотрим подгруппу
\[
H_1=\text{гр}(A_1,B^x,A^{b_0}).
\]
Покажем, что подгруппа $H_1$ имеет конечный индекс в группе $G$ тогда и только тогда, когда $x$ принадлежит $A_1$. Это и будет означать разрешимость проблемы вхождения для группы $A$.
Если $x$ принадлежит $A$, то $H_1$ имеет конечный (равный единице) индекс в $G$. Предположим, что $x\notin A$; тогда $H_1$ разлагается в свободное произведение
\[
H_1=A_1\ast B^x\ast A^{b_0}.
\]
Пусть $b$ – неединичный элемент из $B$, отличный от $b_0$. Тогда подгруппа, порожденная подгруппами $H_1$ и $A_b$, является их свободным произведением,
\[
\text{гр}(H_1,A^b)=H_1\ast A^b
\]
и, следовательно, имеет бесконечный индекс в группе $G$. Этим заканчивается рассмотрение случая, когда порядок больше двух.
\textbf{Случай 2.} Порядок $B$ равен двум. Тогда в группе $G$ возьмем подгруппу
\[
H_2=\text{гр}(A_1,A^{x b_0}, a_0^{-b}A a_0^{b_0}),
\]
где $a_0$ -- неединичный элемент из группы $A$. Подгруппа $H_2$ содержится в нормальном замыкании множителя $A$ в группе $G$; причем
\[
\bar{A}=A\ast b_0^{-1}Ab_0.
\]
Таким образом, группа $ \bar{A} $ попадает в условия предыдущего случая. Сейчас роль группы $B$ исполняет группа $ A^{b_0} $, а роль элемента $b_0$ – элемент $a^{b_0}_0$. Подгруппа $H_2$ в группе построена аналогично подгруппе $H_1$ в группе $A \ast B$. Поэтому снова элемент $x$ принадлежит подгруппе $A_1$ тогда и только тогда, когда $H_2$ имеет конечный индекс в $ \bar{A} $ , и, следовательно, и конечный индекс в группе $G$. Теорема 3 доказана.
\end{proof}
Из теоремы 2 и 3 следует, что для каждой свободно разложимой группы проблема индекса разрешима тогда и только тогда, когда в этой группе разрешима проблема вхождения.
Заметим, что для эквивалентности проблемы индекса и проблемы вхождения группе вовсе не обязательно быть свободно разложимой. Очевидно, что свободное произведение с объединенной конечной нормальной подгруппой или прямое произведение свободного произведение и конечной группы тоже обладают этим свойством.
\section*{Заключение}
В рассмотренных бесконечных сериях групп проблема индекса и проблема вхождения оказались равносильными. Возможно, что эта связь между двумя алгоритмическими проблемами выполняется для всех конечно определенных групп.
ВОПРОС 1. Верно ли, что в классе конечно определенных групп проблема вхождения эквивалентна проблеме индекса?
Заметим, что для разрешимости проблемы индекса в $A \ast B$ не потребовалась разрешимость проблемы индекса в группах $A$ и $B$. Поэтому если бы разрешимость проблемы индекса в множителях оказалась необходимым условием разрешимости проблемы индекса в свободном произведении, то для любой конечно определенной группы из разрешимости проблемы индекса следовала бы разрешимость проблемы вхождения.
С другой стороны, если бы разрешимость проблемы индекса была достаточным условием разрешимости проблемы индекса в свободном произведении, то из разрешимости проблемы индекса следовала бы разрешимость проблемы вхождения.
Таким образом, вопрос, не эквивалентна ли проблема вхождения проблеме индекса, можно сформулировать в виде двух следующих вопросов.
ВОПРОС 2. Верно ли, что из разрешимости проблемы индекса в свободном произведении следует разрешимость проблемы индекса в свободных множителях?
ВОПРОС 3. Верно ли, что из разрешимости проблемы индекса в свободных множителях следует разрешимость проблемы индекса в свободном произведении?
\begin{thebibliography}{99}
\RBibitem{Gor}
\by Горюшкин А.~П.
\book Амальгамированные свободные произведения групп
\publaddr Владивосток
\publ ДВФУ
\yr 2012
\totalpages 158
\RBibitem{Adyan}
\by Адян С.~И.
\paper Алгоритмическая неразрешимость проблем распознавания некоторых свойств групп
\jour Докл. АН СССР
\yr 1955
\vol 103
\issue 4
\pages 533--535
\Bibitem{Gor2}
\by Goryushkin A.~P.
\paper Imbedding of countable groups in 2-generated simple groups
\jour Mathematical Notes
\yr 1974
\vol 16
\issue 2
\pages 725--727
\RBibitem{Kuz}
\by Кузнецов А.~В.
\paper Алгоритмы как операции в алгебраических системах
\jour УМН
\yr 1958
\vol 13
\issue 3
\pages 240--241
\RBibitem{Lin}
\by Линдон Р., Шупп П.
\book Комбинаторная теория групп
\publaddr М.
\publ Мир
\yr 1980
\totalpages 448
\Bibitem{Kar}
\by Karrass A., Solitar D.
\paper On finitely generated subgroups of a free group
\jour Proc. Amer. Math. Soc.
\yr 1969
\vol 22
\issue 1
\pages 209--213
\RBibitem{Gor3}
\by Горюшкин А.~П.
\paper Особенности машинного исследования дискретных групп
\jour Вестник КРАУНЦ. Физ.-мат. науки
\yr 2013
\issue 1(6)
\pages 43--55
\RBibitem{Gor4}
\by Горюшкин А.~П.
\paper Машинное решение задач дискретной математики
\jour Вестник КРАУНЦ. Физ.-мат. науки
\yr 2011
\issue 2(3)
\pages 58--68
\RBibitem{Gor5}
\by Горюшкин А.~П.
\paper О группах с представлением $< a, b; a^n = 1, ab = b^3a^3 >$
\jour Вестник КРАУНЦ. Физ.-мат. науки
\yr 2010
\issue 1(1)
\pages 8--11
\RBibitem{Gor6}
\by Горюшкин А.~П., Горюшкин В.~А.
\book Элементы абстрактной и компьютерной алгебры
\publaddr Петропавловск-Камчатский
\publ КамГУ им. Витуса Беринга
\yr 2011
\totalpages 518
\RBibitem{Mikh1}
\by Михайлова С.~А.
\paper Проблема вхождения для прямых произведений групп
\jour Мат. сб.
\yr 1966
\vol 70
\issue 2
\pages 241--251
\RBibitem{Mikh2}
\by Михайлова С.~А.
\paper Проблема вхождения для свободных произведений групп
\jour Мат. сб.
\yr 1968
\vol 117
\issue 2
\pages 199--210
\RBibitem{Mol1}
\by Молдаванский Д.~И.
\paper Метод Нильсена для свободного произведения групп
\jour Уч. зап. Иванов. гос. пед. ин-та
\yr 1969
\issue 61
\pages 170--182
\RBibitem{Mol2}
\by Молдаванский Д.~И.
\paper О проблеме сопряженности для подгрупп
\jour Уч. зап. Иванов. гос. пед. ин-та
\yr 1972
\issue 106
\pages 123--135
\Bibitem{Kuh}
\by Kuhn H.~W.
\paper Subgroup theorems for groups presented by generators and relations
\jour Ann. of Math.
\yr 1952
\issue 56
\pages 22--46
\end{thebibliography}
\rdata{08.02.2016}
\end{document}
