Please wait
The journal «Bulletin KRAESC. Physical & Mathematical Sciences» publishes the results of basic and applied research in the area of physical and mathematical sciences (mathematical modeling, mathematical physics, information and computational technologies, educational materials) including extended abstracts of doctor or candidate of science dissertations. The journal may also publish flashes, reviews, newsletters, information on scientific events, congresses, conferences, workshops, seminars and so on.
The Journal was founded in August 2010, registered at the Federal Service for Compliance with the Law in Mass Communications and Protection of Cultural Heritage (Media Organization registration certificate FS 77-41501 from 04.08.2010), and re-registered (certificate FS 77-58548 from 14.07.2014).
The Journal founders are the Federal State Budget Research Institution «Vitus Bering Kamchatka State University», and the Federal State Budget Research Institution «Institute of Cosmophysical Research and Radio Wave Propagation Far Eastern Branch of the Russian Academy of Sciences».
The Journal is issued in print (ISSN: 2079-6641) and online (ISSN: 2079-665X) versions four times a year in Russian and it is also translated into English, beginning in 2014 (ISSN: 2313-0156).
The Journal is posted on the «Math.-Net.Ru»Russian Mathematical Portal and is indexed in Google Scholar, DOAJ, Ulrich’s Periodicals Directory, OCLC WorldCat, Bielefeld Academic Search Engine (BASE), Open Access Infrastructure for Research in Europe (OpenAIRE), DataCite, Directory of Research Journals Indexing, Kyberlenika, Soсionet.
\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}
Overleaf is perfect for all types of projects — from papers and presentations to newsletters, CVs and much more! It's also a great way to learn how to use LaTeX and produce professional looking projects quickly.
Upload or create templates for journals you submit to and theses and presentation templates for your institution. Just create it as a project on Overleaf and use the publish menu. It's free! No sign-up required.
New template are added all the time. Follow us on twitter for the highlights!
Overleaf is a free online collaborative LaTeX editor. No sign up required.
Learn more