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

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

§7.1 생성집합

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

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

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

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

§7.2 교집합에 의한 특성화

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

정리 7.3의 증명

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

$$x = s_1^{\varepsilon_1} \cdots s_r^{\varepsilon_r}, \qquad y = t_1^{\delta_1} \cdots t_m^{\delta_m},$$

이라면

$$xy^{-1} = s_1^{\varepsilon_1} \cdots s_r^{\varepsilon_r}\, t_m^{-\delta_m} \cdots t_1^{-\delta_1}$$

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

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

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

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

§7.3 생성의 표준 예시

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

예시 7.5 ($\mathbb{Z}$, 생성원 둘). 또한 $\mathbb{Z} = \langle 2, 3 \rangle$도 성립한다. 실제로 $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 = \langle (1\;2),\, (1\;2\;3) \rangle$이다. 다음을 확인할 수 있다:

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

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

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

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

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

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

증명

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

($d \mid m$): 각 $g^{a_i} \in H = \langle g^m \rangle$이므로 $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 \underbrace{(g^n)^c}_{= e} \in H = \langle g^m \rangle,$$

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

그러므로 $m = d$이고, $|\langle g^d \rangle| = n/d$이다. $\blacksquare$

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

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

비가환군

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

§7.4 케일리 유향그래프

정의 7.9 (케일리 유향그래프). $G$를 군이라 하고 $S$를 $G$의 생성집합이라 하자. 케일리 유향그래프(Cayley digraph) $\operatorname{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$, 생성원 $\{(1\;2),\, (1\;2\;3)\}$). 케일리 유향그래프는 6개의 꼭짓점과 두 변 무리를 가진다. $(1\;2\;3)$-변은 두 개의 유향 3-순환을 이룬다(하나는 $\{e, (1\;2\;3), (1\;3\;2)\}$를 지나고, 다른 하나는 $\{(1\;2), (2\;3), (1\;3)\}$를 지난다). $(1\;2)$-변은 두 3-순환에 걸쳐 원소들을 짝짓는다. 이 그래프는 비가환 구조를 시각적으로 보여 준다: 생성원을 다른 순서로 따라가면 다른 꼭짓점에 도달한다.

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

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

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

정리 7.15의 증명

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

$$\varphi(x) = hg^{-1}x \xrightarrow{s} hg^{-1}(xs) = \varphi(xs),$$

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

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

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

정리 7.16의 증명

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

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

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

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

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

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

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

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

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

케일리 정리와의 연결. 각 생성원 $s \in S$는 $\rho_s(g) = gs$로 순열 $\rho_s: G \to G$를 정의한다. 사상 $g \mapsto \rho_g$(여기서 $\rho_g(x) = xg$)는 단사 준동형사상 $G \hookrightarrow \operatorname{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$를 나누므로). 그러므로 $\langle a_1/b_1, \dots, a_r/b_r \rangle$의 모든 원소는 $m/B$ 형태를 가진다.

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

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

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

§7.8 관계와 표시

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

자유군

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

정의 7.18 (자유군, 비형식적). 집합 $S$ 위의 자유군(free group) $F(S)$는 알파벳 $S \cup S^{-1}$에 대한 모든 기약 단어로 이루어지는데, 여기서 “기약(reduced)“이란 인접한 쌍 $ss^{-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 = \langle s_1, \dots, s_k \rangle$라면, 각 형식적 생성원을 그에 대응하는 군 원소로 보내는 사상 $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 = \langle\!\langle r_1, r_2, \dots \rangle\!\rangle$는 관계자(relator)들의 정규폐포(normal closure), 즉 그것들을 포함하는 $F$의 가장 작은 정규부분군이다.

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

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

$F(\{a\}) \cong \mathbb{Z}$에서 출발하여, 관계 $a^n = e$는 $a^k = a^{k \bmod 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$가 없다면, 군 $\langle a, b \mid a^2 = e, b^2 = e \rangle$는 무한 이면체군 $D_\infty$(자유곱 $\mathbb{Z}_2 {*} \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$이다.

단어 문제

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

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

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

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

풀이 예제

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

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

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

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

풀이 예제 B. $S_4$ 안에서 $\langle (1\;2), (3\;4) \rangle$를 구하라.

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

생성된 부분군은 $\{e,\; (1\;2),\; (3\;4),\; (1\;2)(3\;4)\} \cong V_4$이다. 이는 $S_4$의 진부분군이므로, $\{(1\;2), (3\;4)\}$는 $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}$에서 $\langle \bar{6}, \overline{10}, \overline{15} \rangle$를 결정하고 생성된 부분군의 위수를 구하라.

$d = \gcd(6, 10, 15, 30)$을 계산하자. 단계별로: $\gcd(6, 10) = 2$, 그다음 $\gcd(2, 15) = 1$, 그다음 $\gcd(1, 30) = 1$이다. $d = 1$이므로, 명제에 의해 $\langle \bar{6}, \overline{10}, \overline{15} \rangle = \langle \bar{1} \rangle = \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 = \langle r, s \rangle$($r$ = $2\pi/3$만큼의 회전, $s$ = 반사)의 케일리 유향그래프로부터 다음을 읽어 내라: (a) 각 생성원의 위수, (b) 군이 가환인지 여부, (c) 단일 생성원 변으로부터 보이는 모든 부분군.

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

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

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

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

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

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

표시는 $Q_8 = \langle i, j \mid i^4 = e,\; j^2 = i^2,\; jij^{-1} = i^{-1} \rangle$이다.

세 번째 관계는 $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. $\langle S \rangle$의 구체적 정의: $s_i \in S$인 모든 유한 곱 $s_1^{\pm 1} \cdots s_r^{\pm 1}$(빈 곱 $= e$ 포함).

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

3. 생성의 핵심 예시:

   • $\mathbb{Z} = \langle 1 \rangle = \langle 2, 3 \rangle$(그러나 $\langle 2 \rangle = 2\mathbb{Z} \neq \mathbb{Z}$).
   • $S_n = \langle \text{all transpositions} \rangle = \langle (1\;2), (1\;2\;\cdots\;n) \rangle$.
   • $|D_n| = 2n$인 $D_n = \langle r, s \rangle$.

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

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

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

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

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

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

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

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

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

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

14. 핵심 표시: $\mathbb{Z}_n = \langle a \mid a^n \rangle$, $D_n = \langle r, s \mid r^n, s^2, srs r \rangle$, $Q_8 = \langle i, j \mid i^4, j^2 i^{-2}, jij^{-1}i \rangle$.

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

숙달 체크리스트

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

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