토드-콕시터 알고리즘

그룹 이론에서, J. A에 의해 만들어진 Todd-Coxeter 알고리즘. 1936년 토드와 H. S. M. Coxeter는 코셋 열거 문제를 해결하기 위한 알고리즘이다.발생기와 관계 및 G의 부분군 H에 의한 그룹 G의 표시에 대해 알고리즘은 G에 H의 코세트를 열거하고 코세트의 공간에 대한 G의 순열 표현을 설명한다(왼쪽 곱셈 작용에 의해 주어짐).그룹 G의 순서가 상대적으로 작고 부분군 H가 복잡하지 않은 것으로 알려진 경우(예: 주기적 그룹) 알고리즘은 손으로 수행할 수 있으며 그룹 G에 대한 합리적인 설명을 제공한다.Coxeter와 Todd는 알고리즘을 사용하여 알려진 그룹의 생성자 사이의 특정 관계 시스템이 완전하다는 것을 보여주었다. 즉, 관계를 정의하는 시스템을 구성한다.

Todd-Coxeter 알고리즘은 무한 그룹에 적용할 수 있으며, G에서 H의 지수가 유한하다면, 유한한 수의 스텝으로 종료되는 것으로 알려져 있다.한편, 그룹 표시와 하위 그룹으로 구성된 일반 쌍의 경우, 실행 시간은 하위 그룹의 지수와 입력 데이터의 크기에 대한 계산 가능한 함수에 의해 제한되지 않는다.

알고리즘 설명

알고리즘의 한 구현은 다음과 같이 진행된다.Suppose that $G=\langle X\mid R\rangle$ , where $X$ is a set of generators and $R$ is a set of relations and denote by $X'$ the set of generators $X$ and their inverses.Let $H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle$ where the $h_{i}$ are words of elements of $X'$ . There are three types of tables that will be used: a coset table, a relation table for each relation in ${\displaystyle R$ $}$ , 그리고 $H$ $H$ 의 $h_{i}$ 각 발생기 $h_{i}$ $h_{i}$ ${\$ 에 대한 하위 그룹 테이블 $H$ 정보가 점차 이들 테이블에 추가되고, 일단 입력되면 모든 코세트가 열거되어 알고리즘이 종료된다.

코셋 테이블은 제너레이터에 의해 곱할 때 알려진 코셋 간의 관계를 저장하는 데 사용된다.It has rows representing cosets of $H$ and a column for each element of $X'$ . Let $C_{i}$ denote the coset of the ith row of the coset table, and let $g_{j}\in X'$ denote generator of the jth column.i행, column j에 있는 coset 테이블의 항목은 (알고 있는 경우) k로 정의된다. 여기서 $C_{k}=C_{i}g_{j}$ 는 C $C_{k}=C_{i}g_{j}$ = $C_{k}=C_{i}g_{j}$ $C_{k}=C_{i}g_{j}$ $C_{k}=C_{i}g_{j}$ {\ $displaystyle C_{k}=C_{i}g_{j$

관계표는 우리가 발견한 코세트의 일부가 실제로 동등한지를 감지하는 데 사용된다. $R$ $R$ 의 각 관계에 대해 하나의 관계 테이블이 유지된다 $R$ .Let $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ = $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ n $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ g $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ ⋯ $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ t ${\$ }:{ $n_{$ 2}}\ $cdots$ g_ ${n_{t}}}}$ 은(는)R {\ $displaystyle$ R $}$ 의 관계가 된다 $1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ $R$ 여기서 g $g_{n_{i}}\in X'$ X $′{$ 관계 테이블에는 코셋 테이블과 같이 $H$ $H$ 의 코세트를 나타내는 행이 있다.It has t columns, and the entry in the ith row and jth column is defined to be (if known) k, where $C_{k}=C_{i}g_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ . In particular, the $(i,t)$ 'th entry is initially i, since $g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1$ $g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1$ $g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1$ $g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1$ $g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1$ = $g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1$ ${\displaystyle g_{n_{1$ }} $g_{n_$ {2 $}}\cdots g_{n_{t}=1$

Finally, the subgroup tables are similar to the relation tables, except that they keep track of possible relations of the generators of $H$ . For each generator $h_{n}=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}$ of $H$ , with $g_{n_{i}}\in X'$ $g_{n_{i}}\in X'$ $g_{n_{i}}\in X'$ $g_{n_{i}}\in X'$ $g_{n_{i}}\in X'$ $g_{n_{i}}\in X'$ ${\$ X $'}$ 에서 하위 그룹 테이블을 생성한다 $g_{n_{i}}\in X'$ $H$ $H$ 자체의 $H$ 코세트에 해당하는 행이 하나만 있다.t 열을 가지며, j번째 열의 항목은 k로 정의된다(알고 있는 경우). $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ 서 $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ k $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ = $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ g $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ $C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}$ ${\$ 2}}:\ $cdots g_{n_$ {n_ ${j$

관계 또는 부분군 테이블의 행이 완료되면, $g\in X'$ 정보 $C_{i}=C_{j}g$ i $C_{i}=C_{j}g$ = $C_{i}=C_{j}g$ $C_{i}=C_{j}g$ $C_{i}=C_{j}g$ ${\displaystyle C_{i}=C_{j}g$ g $g\in X'$ $g\in X'$ $g\in X'$ ${\$ 이 $g\in X'$ 가) 발견된다.이것을 추리라고 한다.공제로부터 관계 및 부분군 표의 추가 항목을 기입할 수 있어 추가 공제 가능성이 있을 수 있다.방정식 $C_{i}=C_{j}g$ $C_{i}=C_{j}g$ = $C_{i}=C_{j}g$ j $C_{i}=C_{j}g$ $C_{i}=C_{j}g$ 와 $C_{i}=C_{j}g$ $C_{j}=C_{i}g^{-1}$ $C_{j}=C_{i}g^{-1}$ = C $C_{j}=C_{i}g^{-1}$ $C_{j}=C_{i}g^{-1}$ - $C_{j}=C_{i}g^{-1}$ ${\$ 에 해당하는 코제트 테이블의 항목을 채울 수 있다 $C_{j}=C_{i}g^{-1}$

그러나 코제트 표를 채울 때는 이미 방정식에 대한 엔트리가 있을 수 있지만 엔트리는 다른 값을 가지고 있을 수 있다.이 경우, 우리는 우리의 두 코세트가 실제로 같은 것으로, 우연의 일치로 알려져 있다는 것을 발견했다. $i<j$ $C_{i}=C_{j}$ = $C_{i}=C_{j}$ $C_{i}=C_{j}$ ${\$ 를 $i<j$ < ${\displaystyle$ i $<j$ }로 가정합시다 $i<j$ 표에 있는 j의 모든 인스턴스를 i로 교체한다.그리고 나서, 우리는 표의 가능한 모든 항목들을 채워서, 아마도 더 많은 추론과 우연의 일치로 이어질 것이다.

모든 공제 및 우연을 처리한 후 표에 빈 항목이 있는 경우 표에 새 코세트를 추가하고 과정을 반복하십시오.코스메트를 추가할 때 Hx가 알려진 코스메트인 $g\in X'$ , 어느 $g\in X'$ 에 모든 g $g\in X'$ ∈ X $g\in X'$ ${\$ X $g\in X'$ 에 대해 Hxg가 추가되도록 한다.(이것은 $|G:H|$ : $|G:H|$ $displaystyle$ G:H $}$ 이(가 $|G:H|$ ) 유한하다는 것을 보장하는데 필요하다.)