제7장 - 생성원과 케일리 유향그래프

생성집합은 군이 소수의 원소와 그 역원으로부터 어떻게 조립되는지를 기술한다. 케일리 유향그래프는 이 대수적 기술을 조합론적이고 기하학적인 대상으로 바꾸어 놓는다. 이 장에서는 생성이라는 대수적 개념을 그래프 이론과 연결하고, 군의 표시(presentation)를 위한 토대를 마련한다.

§7.1 생성집합

정의 7.1 (생성집합). $G$를 군이라 하고 $S\subseteq G$라 하자. $S$에 대한 **단어(word)**란 유한 곱

을 말한다. $⟨S⟩$로 표기하는 $S$가 생성하는 부분군은 이러한 모든 단어(빈 단어 포함, 빈 단어는 $e$를 나타낸다)의 집합이다. $⟨S⟩=G$일 때 $S$가 $G$를 생성한다고 말한다.

역원을 포함시키는 것은 필수적이다. 비가환군에서는 양의 단어들만으로는 일반적으로 역원에 대해 닫혀 있지 않으므로, 그것들은 부분군을 이루지 못한다.

정의 7.2 (유한생성군). 군 $G$는 어떤 유한 부분집합 $S\subseteq G$가 존재하여 $⟨S⟩=G$일 때 **유한생성(finitely generated)**이라고 한다.

§7.2 교집합에 의한 특성화

정리 7.3. $G$를 군이라 하고 $S\subseteq G$라 하자. 그러면 $⟨S⟩$는 $S$를 포함하는 $G$의 모든 부분군의 교집합과 같다:

정리 7.3의 증명

1단계: $⟨S⟩$는 $S$를 포함하는 부분군이다. 각 $s\in S$는 $S$에 대한 한 글자 단어이므로 $S\subseteq ⟨S⟩$이다. 빈 단어로부터 $e\in ⟨S⟩$를 얻는다. 만약

$$x=s_1^{{\epsilon }_1}\cdots s_r^{{\epsilon }_r},y=t_1^{{\delta }_1}\cdots t_m^{{\delta }_m},$$

이라면

$$x{y}^{-1}=s_1^{{\epsilon }_1}\cdots s_r^{{\epsilon }_r}{t}_m^{-{\delta }_m}\cdots t_1^{-{\delta }_1}$$

도 다시 $S$와 역원들에 대한 단어이다. 부분군 판정법에 의해 $⟨S⟩\le G$이다.

2단계: $⟨S⟩$는 $S$를 포함하는 모든 부분군에 포함된다. $S\subseteq H$인 $H\le G$를 잡자. $H$는 곱과 역원에 대해 닫혀 있으므로, $S$의 원소들과 그 역원들로 이루어진 모든 유한 단어가 $H$ 안에 들어 있다. 따라서 $⟨S⟩\subseteq H$이다.

3단계: 결론. 1단계에 의해 $⟨S⟩$는 교집합의 대상이 되는 부분군 중 하나이다. 2단계에 의해 $⟨S⟩$는 그러한 각 부분군에 포함된다. 그러므로 $⟨S⟩$는 그 교집합과 같다. $■$

이 정리는 “$S$를 포함하는 가장 작은 부분군”이라는 표현이 비형식적인 말이 아니라, 잘 정의된 폐포(closure) 연산임을 말해 준다.

§7.3 생성의 표준 예시

예시 7.4 ($\mathbb{Z}$, 생성원 하나). 덧셈에 대한 정수는 $\mathbb{Z}=⟨1⟩$을 만족한다. 모든 정수는 $1$ 또는 $-1$의 사본들의 유한 합이다.

예시 7.5 ($\mathbb{Z}$, 생성원 둘). 또한 $\mathbb{Z}=⟨2,3⟩$도 성립한다. 실제로 $1=3+(-2)=3-2$이고, $1$이 $\mathbb{Z}$를 생성하므로 $\{2,3\}$도 그러하다. 이는 생성집합이 극소(minimal)일 필요가 없음을 보여 준다.

예시 7.6 (호환으로 생성되는 $S_n$). 대칭군 $S_n$은 모든 호환(transposition)의 집합으로 생성된다. 모든 순열은 호환들의 곱으로 분해될 수 있다(9장 참고). 따라서

예시 7.7 ($S_3$, 생성원 둘). 더 효율적으로, $S_3=⟨(12),(123)⟩$이다. 다음을 확인할 수 있다:

따라서 세 호환이 모두 얻어진다. 두 3-순환과 항등원과 함께, 여섯 원소가 모두 설명된다.

예시 7.8 (이면체군). 정$n$각형의 대칭들로 이루어진 이면체군 $D_n$은 $D_n=⟨r,s⟩$을 만족하는데, 여기서 $r$은 $2\pi /n$만큼의 회전이고 $s$는 반사이다. 모든 원소는 $0\le k<n$에 대해 $r^k$ 또는 $s{r}^k$로 쓸 수 있으므로 $|D_n|=2n$이고 두 생성원으로 충분하다.

순환군에서의 계산적 판정법

다음 결과는 순환군에서의 생성 문제를 최대공약수(gcd) 계산으로 환원시킨다. 이는 연습문제 7.1–7.2와 “이 부분집합이 ${\mathbb{Z}}_n$을 생성하는가?”를 묻는 모든 문제의 주된 도구이다.

명제 7.8a (순환군에서의 생성). $G=⟨g⟩$의 위수가 $n$이라 하고, $a_1,\dots ,a_r$을 정수라 하자. 그러면

이 부분군은 위수가 $n/d$이고 $G$에서의 지표(index)가 $d$이다.

증명

$H=⟨g^{a_1},\dots ,g^{a_r}⟩$이라 두자. $G$가 순환군이므로 $G$의 모든 부분군은 순환군이고(4장), 따라서 $n$의 어떤 약수 $m$에 대해 $H=⟨g^m⟩$이다. $m=d$임을 보이자.

($d\mid m$): 각 $g^{a_i}\in H=⟨g^m⟩$이므로 $m\mid a_i$이다. 또한 $m\mid n$이므로, $m\mid \gcd (a_1,\dots ,a_r,n)=d$를 얻는다.

($m\mid d$): 베주(Bezout)의 항등식에 의해, 정수 $c_1,\dots ,c_r,c$가 존재하여

$$c_1{a}_1+\cdots +c_r{a}_r+cn=d.$$

가 성립한다. 그러면

$$g^d=(g^{a_1}{)}^{c_1}\cdots (g^{a_r}{)}^{c_r}\cdot \underset{=e}{\underbrace{(g^n{)}^c}}\in H=⟨g^m⟩,$$

이므로 $m\mid d$이다.

그러므로 $m=d$이고, $|⟨g^d⟩|=n/d$이다. $■$

따름정리 (${\mathbb{Z}}_n$의 생성원). 원소 $\bar{a}$가 ${\mathbb{Z}}_n$을 생성할 필요충분조건은 $\gcd (a,n)=1$이다. 따라서 ${\mathbb{Z}}_n$은 정확히 $\phi (n)$개의 생성원을 가지며, 여기서 $\phi$는 오일러 토션트 함수이다.

예시 7.8b. ${\mathbb{Z}}_{20}$에서 $⟨\bar{8},\overline{14}⟩=⟨\overline{\gcd (8,14,20)}⟩=⟨\bar{2}⟩$이며, 이는 위수 $10$인 순환 부분군이다. ${\mathbb{Z}}_{15}$에서 $⟨\bar{6},\overline{10}⟩=⟨\overline{\gcd (6,10,15)}⟩=⟨\bar{1}⟩={\mathbb{Z}}_{15}$이다.

비가환군

이 gcd 판정법은 순환군(그리고 더 일반적으로는 가환군)에만 적용된다. 비가환군에서는 생성 문제를 명시적 계산으로 해결해야 하며, gcd에 유비되는 지름길은 없다. 예를 들어 $S_4$ 안에서 $⟨(12),(34)⟩\cong V_4$(진부분군)인 반면, $⟨(12),(1234)⟩=S_4$(전체 군)이다. 이 차이는 순환의 길이만으로는 드러나지 않는다.

§7.4 케일리 유향그래프

정의 7.9 (케일리 유향그래프). $G$를 군이라 하고 $S$를 $G$의 생성집합이라 하자. 케일리 유향그래프(Cayley digraph) $\mathrm{Cay}(G,S)$는 다음으로 정의되는 유향그래프이다:

• 꼭짓점: $G$의 원소들.
• 변: 각 $g\in G$와 각 $s\in S$에 대해, $s$로 색칠된(혹은 표지된) 유향변 $g\to gs$가 존재한다.

그래프 읽는 법:

§7.5 작은 군에 대한 케일리 유향그래프

예시 7.10 (${\mathbb{Z}}_4$, 생성원 $\{\bar{1}\}$). 그림: $\bar{1}$로 생성되는 ${\mathbb{Z}}_4$의 케일리 유향그래프.

예시 7.11 (${\mathbb{Z}}_6$, 생성원 $\{\bar{1}\}$). 유향 6-순환:

대신 생성집합 $\{\bar{1},\bar{2}\}$를 사용하면 두 번째 변 무리가 추가되어(각 꼭짓점이 두 칸 앞의 꼭짓점에도 연결됨) 같은 꼭짓점 집합 위에서 더 조밀한 그래프가 만들어진다.

예시 7.12 ($V_4=\{e,a,b,c\}$, 생성원 $\{a,b\}$). 클라인 4-군 $V_4\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2$는 $ab=c$, $a^2=b^2=e$를 만족한다. 케일리 유향그래프는 다음을 가진다:

• $a$-변(가령 실선): $e\leftrightarrow a$와 $b\leftrightarrow c$.
• $b$-변(가령 점선): $e\leftrightarrow b$와 $a\leftrightarrow c$.

모든 생성원이 자기 자신의 역원이므로, 각 유향변은 그 역방향 변과 짝을 이루며, 그래프는 마주 보는 변들이 서로 다른 색으로 동일시된 정사각형처럼 보인다.

예시 7.13 ($S_3$, 생성원 $\{(12),(123)\}$). 케일리 유향그래프는 6개의 꼭짓점과 두 변 무리를 가진다. $(123)$-변은 두 개의 유향 3-순환을 이룬다(하나는 $\{e,(123),(132)\}$를 지나고, 다른 하나는 $\{(12),(23),(13)\}$를 지난다). $(12)$-변은 두 3-순환에 걸쳐 원소들을 짝짓는다. 이 그래프는 비가환 구조를 시각적으로 보여 준다: 생성원을 다른 순서로 따라가면 다른 꼭짓점에 도달한다.

예시 7.14 ($D_4$, 생성원 $\{r,s\}$). 케일리 유향그래프는 8개의 꼭짓점을 가진다. $r$-변은 두 개의 유향 4-순환을 이룬다: 하나는 $\{e,r,r^2,r^3\}$를 지나고 다른 하나는 $\{s,sr,s{r}^2,s{r}^3\}$를 지난다. $s$-변은 각 $r^k$를 $s{r}^k$에 연결한다($s^2=e$이므로 역방향으로도 연결됨). 관계 $srs=r^{-1}$은 두 번째 4-순환이 반대 방향으로 순회된다는 사실로 나타난다.

§7.6 케일리 유향그래프가 드러내는 것

정리 7.15 (꼭짓점 추이성). 케일리 유향그래프 $\mathrm{Cay}(G,S)$는 꼭짓점 추이적(vertex-transitive)이다: 임의의 두 꼭짓점 $g,h\in G$에 대해, 사상 $x\mapsto h{g}^{-1}x$는 $g$를 $h$로 보내는 그래프 자기동형사상이다.

정리 7.15의 증명

$\phi :G\to G$를 $\phi (x)=h{g}^{-1}x$로 정의하자. 이는 전단사이다(고정 원소 $h{g}^{-1}$에 의한 왼쪽 곱). 변을 보존함을 확인한다: 만약 $x\stackrel{s}{\to }xs$가 변이라면,

$$\phi (x)=h{g}^{-1}x\stackrel{s}{\to }h{g}^{-1}(xs)=\phi (xs),$$

이므로 상(image)이 되는 쌍도 $s$-변이다. $\phi (g)=h{g}^{-1}g=h$이므로, 이 사상은 $g$를 $h$로 보낸다. $■$

꼭짓점 추이성은 그래프가 “모든 꼭짓점에서 똑같이 보인다”는 것을 뜻하며, 이는 모든 군 원소가 평행이동된 사본의 항등원 역할을 할 수 있다는 대수적 사실을 반영한다.

정리 7.16 (연결성 판정법). 케일리 유향그래프 $\mathrm{Cay}(G,S)$가 연결될 필요충분조건은 $S$가 $G$를 생성하는 것이다.

정리 7.16의 증명

($\Rightarrow$) 그래프가 연결되어 있다면, 모든 $g\in G$에 대해 $e$에서 $g$로 가는 유향 경로가 존재한다. 이 경로는 각 $s_i\in S$인 단어 $s_1^{{\epsilon }_1}\cdots s_r^{{\epsilon }_r}=g$를 철자화한다. 따라서 $g\in ⟨S⟩$이므로 $⟨S⟩=G$이다.

($\Leftarrow$) $S$가 $G$를 생성한다면, 모든 $g\in G$는 $S$와 그 역원들에 대한 단어로 쓸 수 있다. 단어의 각 글자는 변을 순회하는 것에 대응한다($s$에 대해서는 앞으로, $s^{-1}$에 대해서는 뒤로). 따라서 $e$에서 $g$로 가는 경로가 존재한다. 꼭짓점 추이성에 의해 그래프는 연결되어 있다. $■$

순환 구조와 관계. 케일리 유향그래프에서 시작 꼭짓점으로 돌아오는 순환은 생성원들 사이의 관계에 대응한다. 예를 들어 $\mathrm{Cay}({\mathbb{Z}}_4,\{\bar{1}\})$의 4-순환은 관계 $1+1+1+1=0$(즉, ${\bar{1}}^4=\bar{0}$)에 대응한다. $\mathrm{Cay}(D_4,\{r,s\})$에서 순환 $e\stackrel{s}{\to }s\stackrel{r}{\to }sr\stackrel{s}{\to }{r}^{-1}=r^3$(그리고 계속해서 $e$로 돌아옴)은 관계 $srs=r^{-1}$을 부호화한다.

유향그래프로부터 군의 성질 검출하기

가환성. 군 $G$가 가환일 필요충분조건은 모든 생성원 쌍 $s,t\in S$와 모든 꼭짓점 $g$에 대해 두 경로

가 같은 꼭짓점에 도달하는 것이다. 시각적으로는: 두 가지 다른 호 유형으로 이루어진 모든 “평행사변형”이 닫힌다. 꼭짓점 추이성에 의해 단 하나의 꼭짓점(가령 $e$)에서만 확인하면 충분하다: 군이 가환일 필요충분조건은 모든 생성원 쌍 $s,t\in S$에 대해 $st=ts$인 것이다.

예시. $\mathrm{Cay}(S_3,\{(12),(123)\})$에서 $e$에서 출발하자. $(12)$를 따른 뒤 $(123)$를 따르면 $(12)(123)=(23)$을 준다. $(123)$를 따른 뒤 $(12)$를 따르면 $(123)(12)=(13)$을 준다. 서로 다른 꼭짓점이므로 $S_3$은 비가환이다. $\mathrm{Cay}(V_4,\{a,b\})$에서 $e$에서 출발하면: 두 순서 모두 $ab=ba=c$를 준다. 모든 평행사변형이 닫히므로 $V_4$가 가환임이 확인된다.

부분군의 가시성. 만약 $H\le G$이고 $S^{\prime }=S\cap H$가 $H$를 생성한다면, $\mathrm{Cay}(H,S^{\prime })$는 $\mathrm{Cay}(G,S)$ 안에서 꼭짓점 집합 $H$ 위의 유도 부분그래프(induced subgraph)로 나타난다. 좌잉여류 $gH$는 이 부분그래프의 동형인 사본으로 나타난다: $S^{\prime }$-변을 임의의 잉여류로 제한하면 왼쪽 곱만큼 옮겨진 동일한 패턴이 재현된다.

예시. $\mathrm{Cay}(S_3,\{(12),(123)\})$에서 $\{e,(123),(132)\}$로 제한된 $(123)$-변은 유향 3-순환을 이루는데, 이것이 $\mathrm{Cay}(⟨(123)⟩,\{(123)\})$이다. 나머지 세 꼭짓점 $\{(12),(23),(13)\}$은 평행한 3-순환을 이루는데, 이것은 잉여류 $(12)⟨(123)⟩$로서 부분군이 아니라 부분군의 옮겨진 사본이다.

케일리 정리와의 연결. 각 생성원 $s\in S$는 ${\rho }_s(g)=gs$로 순열 ${\rho }_s:G\to G$를 정의한다. 사상 $g\mapsto {\rho }_g$(여기서 ${\rho }_g(x)=xg$)는 단사 준동형사상 $G\hookrightarrow \mathrm{Sym}(G)$로 확장된다. 이것이 바로 **우정칙표현(right regular representation)**이며, 케일리 유향그래프는 그것의 시각적 부호화이다. 이 사상이 단사라는 사실은 케일리 정리(8장)의 내용이다: 모든 군은 어떤 대칭군에 매장(embed)된다.

§7.7 유한생성군

모든 군이 유한생성인 것은 아니다. 다음은 표준적이고 시사적인 예이다.

정리 7.17. 군 $(\mathbb{Q},+)$는 유한생성이 아니다.

정리 7.17의 증명

$\mathbb{Q}$가 기약분수로 쓰인 유한히 많은 유리수

$$\frac{a_1}{b_1},\frac{a_2}{b_2},\dots ,\frac{a_r}{b_r}$$

로 생성된다고 하여 모순을 이끌어 내자. $B=b_1{b}_2\cdots b_r$이라 두자. 이 생성원들의 모든 정수 일차결합은 다음 형태

$$n_1\cdot \frac{a_1}{b_1}+\cdots +n_r\cdot \frac{a_r}{b_r}$$

를 가지며, 공통분모로 모으면 결과는 어떤 정수 $m$에 대해 $m/B$이다(각 분모 $b_i$가 $B$를 나누므로). 그러므로 $⟨a_1/b_1,\dots ,a_r/b_r⟩$의 모든 원소는 $m/B$ 형태를 가진다.

이제 $B$를 나누지 않는 소수 $p$를 잡자(소수는 무한히 많다). 그러면 $1/p$는 어떤 정수 $m$에 대해서도 $m/B$로 쓸 수 없는데, 그러려면 $B=mp$여야 하고 이는 $p\mid B$를 강제하기 때문이다. 이는 $1/p\in \mathbb{Q}=⟨a_1/b_1,\dots ,a_r/b_r⟩$에 모순된다. $■$

이 증명은 유한생성 문제가 어떻게 산술적 장애물로 환원되는지를 보여 주는 모범이다. 핵심은 유리수의 덧셈군에서 유한 생성집합은 분모를 제약하지만, $\mathbb{Q}$는 유계가 아닌 분모를 가진다는 점이다.

참고. 덧셈군 $\mathbb{R}$ 또한 유한생성이 아니다(같은 방식의 논증으로, 혹은 농도에 의해: 가환군의 유한생성 부분군은 가산이지만 $\mathbb{R}$은 비가산이다). 반면 모든 유한군은 유한생성이다($S=G$로 잡으면 된다).

§7.8 관계와 표시

생성집합은 어떤 원소들이 군을 만드는지 알려 주고, **관계(relation)**는 서로 다른 단어가 언제 같은 원소를 나타내는지 알려 준다. **표시(presentation)**는 이 둘을 동형을 무시하고 군을 결정하는 간결한 기술로 묶어 낸다.

자유군

표시를 정밀하게 하려면, 아무런 관계도 없는 군이라는 개념이 필요하다.

정의 7.18 (자유군, 비형식적). 집합 $S$ 위의 자유군(free group) $F(S)$는 알파벳 $S\cup S^{-1}$에 대한 모든 기약 단어로 이루어지는데, 여기서 “기약(reduced)“이란 인접한 쌍 $s{s}^{-1}$이나 $s^{-1}s$가 나타나지 않음을 뜻한다. 곱셈은 이어 붙인 뒤 단어가 기약이 될 때까지 역원 쌍을 소거하는 것이다. 빈 단어가 항등원이다.

생성원 하나에 대한 자유군은 $F(\{a\})\cong \mathbb{Z}$이다: 모든 기약 단어는 어떤 $k\in \mathbb{Z}$에 대해 $a^k$이다. 두 개 이상의 생성원에 대한 자유군은 비가환이고 무한하다. 예를 들어 $F(\{a,b\})$에서 단어 $ab$와 $ba$는 서로 다른 원소이다.

$F(S)$의 핵심 성질은 **보편성(universality)**이다: $|S|$개의 원소로 생성되는 모든 군은 $F(S)$의 몫(quotient)이다. 만약 $G=⟨s_1,\dots ,s_k⟩$라면, 각 형식적 생성원을 그에 대응하는 군 원소로 보내는 사상 $F(\{s_1,\dots ,s_k\})\to G$는 전사 준동형사상이다. 그 핵(kernel)은 정확히 $G$에서 $e$와 같아지는 단어들로 이루어지며, 이것이 관계이다.

표시

정의 7.19 (군의 표시). 군의 표시

는 생성원 $s_1,\dots ,s_k$와 관계 $r_1,r_2,\dots$(각 $r_i$는 생성원에 대한 단어들 사이의 등식)를 명시한다. 형식적으로 $G\cong F(s_1,\dots ,s_k)/N$이며, 여기서 $N=⟨⟨r_1,r_2,\dots ⟩⟩$는 관계자(relator)들의 정규폐포(normal closure), 즉 그것들을 포함하는 $F$의 가장 작은 정규부분군이다.

표시로 정의되는 군은 모든 $r_i$가 성립하면서 $s_i$로 생성되는 “가장 큰” 군이다: 그러한 다른 모든 군은 그것의 몫이다.

예시 7.20 (순환군의 표시).

$F(\{a\})\cong \mathbb{Z}$에서 출발하여, 관계 $a^n=e$는 $a^k=a^{k\mathrm{mod}n}$을 강제하여 $\mathbb{Z}/n\mathbb{Z}$를 준다.

예시 7.21 (이면체군의 표시).

처음 두 관계는 생성원의 위수를 제한한다. 세 번째는 **켤레 관계(conjugation relation)**이다: $r$을 $s$로 켤레화하면 그것을 역원으로 만들어, “반사가 회전을 뒤집는다”를 부호화한다. 동등하게 $sr=r^{-1}s$이며, 이것은 임의의 단어를 표준형 $s^i{r}^j$($i\in \{0,1\}$, $0\le j<n$)로 환원시키는 교환 규칙이다. 이 세 관계는 동형을 무시하고 $D_n$을 완전히 결정한다.

예시 7.22 (클라인 4-군).

가환성 관계 $ab=ba$가 없다면, 군 $⟨a,b\mid a^2=e,b^2=e⟩$는 무한 이면체군 $D_{\infty }$(자유곱 ${\mathbb{Z}}_2\ast {\mathbb{Z}}_2$)가 될 것이다. 가환성을 더하면 이것은 유한군 $V_4$로 붕괴한다.

예시 7.23 (사원수군).

이것은 위수 8인 비가환군으로, $D_4$와 다르다. $D_4$와 $Q_8$의 표시는 오직 두 번째 관계에서만 차이가 난다: $D_4$의 경우 $s^2=e$이고 $Q_8$의 경우 $j^2=i^2$이다. $D_4$에서 반사는 위수가 2이고, $Q_8$에서는 두 생성원 모두 위수가 4이며 위수 2인 유일한 원소는 $i^2=j^2=-1$이다.

단어 문제

표시 $⟨S\mid R⟩$이 주어졌을 때, **단어 문제(word problem)**는 다음을 묻는다: 생성원과 그 역원에 대한 단어 $w$가 주어졌을 때, 표시된 군에서 $w=e$인가? 동등하게, $w$가 관계자들의 정규폐포 안에 들어 있는가?

유한군에 대해서는 이것은 항상 판정 가능하다(모든 원소를 열거하면 된다). 그러나 일반적으로 단어 문제는 **판정 불가능(undecidable)**하다: 노비코프(Novikov, 1955)와 분(Boone, 1959)은 어떤 임의의 단어가 항등원과 같은지 어떤 알고리즘으로도 판정할 수 없는 유한표시군이 존재함을 각각 독립적으로 증명했다.

이는 표시가 간결하더라도 다루기에는 의외로 어려울 수 있음을 뜻한다. 표시는 군을 정확히 정의하지만, 그것으로부터 정보를 추출하는 일(군의 위수, 두 단어가 같은 원소를 나타내는지, 군이 자명한지)은 계산적으로 다루기 어려울 수 있다. 표시의 우아함과 그것으로 계산하는 어려움 사이의 이 긴장은 조합론적 군론의 많은 부분을 관통한다.

표시는 이후 장들에서, 특히 몫군(15장)과 유한표시군의 구조에서 필수 도구가 된다.

풀이 예제

풀이 예제 A. ${\mathbb{Z}}_{12}=⟨\bar{5},\bar{8}⟩$임을 보여라.

생성된 부분군의 모든 $d$에 대해 $\gcd (5,8,12)\mid d$가 필요하지만, 더 직접적으로: ${\mathbb{Z}}_{12}$에서 부분군 $⟨\bar{5},\bar{8}⟩$은 $\bar{5}$와 $\bar{8}$을 포함한다. 그 차는

이제 $\bar{5}-\bar{3}=\bar{2}$이고, $\bar{3}-\bar{2}=\bar{1}$이다. $\bar{1}\in ⟨\bar{5},\bar{8}⟩$이고 $\bar{1}$이 ${\mathbb{Z}}_{12}$를 생성하므로, $⟨\bar{5},\bar{8}⟩={\mathbb{Z}}_{12}$라고 결론짓는다.

대안으로, $\gcd (5,8)=1$이고 $\gcd (1,12)=1$임에 주목하면, $⟨\bar{5},\bar{8}⟩$은 위수 12인 원소를 포함한다.

풀이 예제 B. $S_4$ 안에서 $⟨(12),(34)⟩$를 구하라.

두 생성원 모두 위수가 2이고 서로소(disjoint)이므로 교환된다:

생성된 부분군은 $\{e,(12),(34),(12)(34)\}\cong V_4$이다. 이는 $S_4$의 진부분군이므로, $\{(12),(34)\}$는 $S_4$를 생성하지 않는다.

풀이 예제 C. 생성원 $a=(1,0)$과 $b=(0,1)$을 갖는 ${\mathbb{Z}}_2\times {\mathbb{Z}}_3$의 케일리 유향그래프를 기술하라.

이 군은 6개의 원소를 가진다. $a$-변은 두 “층(layer)” 사이를 맞바꾼다($a$의 위수가 2이므로 각 $a$-변은 2-순환이다): $k=0,1,2$에 대해 $(0,k)\leftrightarrow (1,k)$. $b$-변은 두 개의 유향 3-순환을 이룬다: $(0,0)\to (0,1)\to (0,2)\to (0,0)$과 $(1,0)\to (1,1)\to (1,2)\to (1,0)$. 그래프는 연결되어 있으며, 이는 $\{a,b\}$가 군을 생성함을 확인해 준다. ${\mathbb{Z}}_2\times {\mathbb{Z}}_3\cong {\mathbb{Z}}_6$이므로, 이 그래프는 생성원 $(1,1)$을 사용하여 하나의 유향 6-순환으로 그릴 수도 있다.

풀이 예제 D. ${\mathbb{Z}}_{30}$에서 $⟨\bar{6},\overline{10},\overline{15}⟩$를 결정하고 생성된 부분군의 위수를 구하라.

$d=\gcd (6,10,15,30)$을 계산하자. 단계별로: $\gcd (6,10)=2$, 그다음 $\gcd (2,15)=1$, 그다음 $\gcd (1,30)=1$이다. $d=1$이므로, 명제에 의해 $⟨\bar{6},\overline{10},\overline{15}⟩=⟨\bar{1}⟩={\mathbb{Z}}_{30}$이다.

구체적으로: $\overline{10}-\bar{6}=\bar{4}$, 그다음 $\bar{6}-\bar{4}=\bar{2}$, 그다음 $\overline{15}-7\cdot \bar{2}=\overline{15}-\overline{14}=\bar{1}$이다.

$\{6,10,15\}$ 중 어떤 두 원소만으로는 ${\mathbb{Z}}_{30}$을 생성하지 못함에 주목하라: $\gcd (6,10,30)=2$, $\gcd (6,15,30)=3$, $\gcd (10,15,30)=5$. 세 원소가 모두 필요하다.

풀이 예제 E. $D_3=⟨r,s⟩$($r$ = $2\pi /3$만큼의 회전, $s$ = 반사)의 케일리 유향그래프로부터 다음을 읽어 내라: (a) 각 생성원의 위수, (b) 군이 가환인지 여부, (c) 단일 생성원 변으로부터 보이는 모든 부분군.

(a) $r$-변은 유향 3-순환을 이루므로 $|r|=3$이다. $s$-변은 꼭짓점들을 짝짓는다($s^2=e$)이므로 $|s|=2$이다.

(b) $e$에서 출발하자. 경로 $e\stackrel{r}{\to }r\stackrel{s}{\to }rs$는 $rs$에서 끝난다. 경로 $e\stackrel{s}{\to }s\stackrel{r}{\to }sr$은 $sr$에서 끝난다. $S_3$의 표준 표지법에서 $rs=(13)$이고 $sr=(23)$이므로, 이들은 서로 다른 꼭짓점이다: 군은 비가환이다.

(c) $r$-변만으로 6개의 꼭짓점은 두 개의 유향 3-순환으로 분해된다:

• $\{e,r,r^2\}$: 이것은 부분군 $⟨r⟩\cong {\mathbb{Z}}_3$으로, 지표 2인 유일한 부분군이다.
• $\{s,sr,s{r}^2\}$: 이것은 잉여류 $s⟨r⟩$로, 부분군이 아니다($e$를 포함하지 않는다).

$s$-변은 각 회전을 반사와 짝짓는다. 각 쌍 $\{g,gs\}$는 그 쌍이 $e$를 포함할 때에만 부분군 $⟨gs⟩\cong {\mathbb{Z}}_2$를 준다: 부분군 $\{e,s\}$, $\{e,sr\}$, $\{e,s{r}^2\}$는 각각 $e$로부터의 $s$-변, 그리고 $r$과 $r^2$으로부터의 $s$-변으로 (재표지 후) 보인다. $⟨r⟩$과 자명한 부분군들과 함께, 이들이 $S_3$의 다섯 부분군 전부이다.

풀이 예제 F. $Q_8$의 표시를 쓰고 모든 표준형 원소를 나열하여 $|Q_8|=8$임을 확인하라.

표시는 $Q_8=⟨i,j\mid i^4=e,j^2=i^2,ji{j}^{-1}=i^{-1}⟩$이다.

세 번째 관계는 $ji=i^{-1}j=i^{3}j$를 주며, 이것이 교환 규칙이다. $i,j$에 대한 임의의 단어는 다음으로 환원될 수 있다:

1. $ji=i^{3}j$를 사용하여 모든 $j$를 오른쪽으로 옮긴다.
2. $i$의 거듭제곱을 4로 나눈 나머지로 환원한다($i^4=e$이므로).
3. $j$의 거듭제곱을 지수에서 2로 나눈 나머지로 환원하되, $j^2=i^2$($e$가 아님)에 유의한다. 따라서 $j^2$은 $i^2$으로 대체되고, $j^3=j^2\cdot j=i^{2}j$이다.

표준형: $0\le a\le 3$이고 $b\in \{0,1\}$인 $i^a{j}^b$로, 8개의 원소를 준다:

표준 동일시 하에서: $i^2=-1$, $i^3=-i$, $ij=k$, $i^{2}j=-j$, $i^{3}j=-k$이다.

플래시카드 요약

빠른 복습을 위한 핵심 사실

1. $⟨S⟩$의 구체적 정의: $s_i\in S$인 모든 유한 곱 $s_1^{\pm 1}\cdots s_r^{\pm 1}$(빈 곱 $=e$ 포함).

2. $⟨S⟩$의 추상적 정의: $S$를 포함하는 $G$의 모든 부분군의 교집합(정리 7.3).

3. 생성의 핵심 예시:

   • $\mathbb{Z}=⟨1⟩=⟨2,3⟩$(그러나 $⟨2⟩=2\mathbb{Z}\ne \mathbb{Z}$).
   • $S_n=⟨\text{all transpositions}⟩=⟨(12),(12\cdots n)⟩$.
   • $|D_n|=2n$인 $D_n=⟨r,s⟩$.

4. 케일리 유향그래프 $\mathrm{Cay}(G,S)$: 꼭짓점 = 군 원소; 각 생성원 $s$에 대해 변 $g\stackrel{s}{\to }gs$.

5. 꼭짓점 추이적: 임의의 군 원소에 의한 왼쪽 곱은 그래프 자기동형사상이다.

6. $S$가 $G$를 생성할 때에만 연결됨(정리 7.16).

7. 순환 = 생성원들 사이의 관계.

8. 유향그래프는 군뿐 아니라 생성원의 선택에 의존한다.

9. ${\mathbb{Z}}_n$에서의 생성: $⟨{\bar{a}}_1,\dots ,{\bar{a}}_r⟩=⟨\overline{\gcd (a_1,\dots ,a_r,n)}⟩$. $\gcd =1$일 때에만 ${\mathbb{Z}}_n$을 생성한다.

10. 유향그래프로부터의 가환성: 임의의 단일 꼭짓점에서 모든 생성원 쌍 평행사변형이 닫히는지 확인한다.

11. 부분군 가시성: $\mathrm{Cay}(H,S\cap H)$는 유도 부분그래프로 나타나고, 잉여류는 옮겨진 사본으로 나타난다.

12. 유한생성이 아님: $(\mathbb{Q},+)$ — 유한 생성원은 분모를 제약한다.

13. 표시 $G=⟨S\mid R⟩$: 형식적으로 $G\cong F(S)/⟨⟨R⟩⟩$, 자유군을 관계자들의 정규폐포로 나눈 몫.

14. 핵심 표시: ${\mathbb{Z}}_n=⟨a\mid a^n⟩$, $D_n=⟨r,s\mid r^n,s^2,srsr⟩$, $Q_8=⟨i,j\mid i^4,j^2{i}^{-2},ji{j}^{-1}i⟩$.

15. 단어 문제: 표시로부터 $w=e$를 판정하는 것은 일반적으로 판정 불가능하다(노비코프–분).

숙달 체크리스트

7장을 떠나기 전에 다음을 할 수 있는지 확인하라:

• 작은 경우에 대해 ${\mathbb{Z}}_n$, $S_n$, $D_n$에서 $⟨S⟩$를 명시적으로 계산하기.
• $⟨S⟩$가 $S$를 포함하는 모든 부분군의 교집합임을 진술하고 증명하기.
• 생성의 정의에서 왜 역원이 필요한지 설명하기(역원 없이는 반례를 제시하기).
• 주어진 군과 생성집합에 대해 케일리 유향그래프를 그리기; 항등원, 곱셈, 역원을 읽어 내기.
• 진술하고 증명하기: 케일리 유향그래프가 연결될 필요충분조건은 생성집합이 군을 생성하는 것이다.
• $(\mathbb{Q},+)$가 유한생성이 아님을 증명하기.
• $D_n$의 표시를 쓰고 각 관계가 기하학적으로 무엇을 의미하는지 설명하기.
• 주어진 부분집합이 주어진 군을 생성하는지 결정하기(가환인 경우 gcd를 사용하고, 그 외에는 명시적 계산을 사용).
• gcd 판정법을 적용하기: ${\mathbb{Z}}_n$에서 $⟨{\bar{a}}_1,\dots ,{\bar{a}}_r⟩=⟨\overline{\gcd (a_1,\dots ,a_r,n)}⟩$.
• 단일 꼭짓점에서 평행사변형을 확인하여 케일리 유향그래프로부터 가환성을 검출하기.
• 케일리 유향그래프에서 부분군과 그 잉여류를 부분그래프로 식별하기.
• 같은 군에 대한 서로 다른 생성집합이 왜 서로 다른 케일리 유향그래프를 낳는지 설명하기.
• 집합 위의 자유군을 정의하고 표시가 어떻게 몫으로 생겨나는지 설명하기.
• 사원수군의 표시를 진술하고 그것이 $D_4$와 어떻게 다른지 설명하기.
• 단어 문제를 설명하고 그것이 일반적으로 왜 판정 불가능한지 진술하기.
• 준동형사상이 생성원에서의 값으로 결정된다는 사실을 사용하기(연습문제 7.6).