장 16 군 작용으로 AIME 문제를 과하게 풀기

1996년 AIME의 다음 문제를 생각해 봅시다.

(AIME 1996) $7\times 7$ 체커판의 칸 중 두 칸을 노란색으로 칠하고, 나머지 칸은 초록색으로 칠합니다. 판이 놓인 평면에서 회전하여 한 색칠 방법을 다른 색칠 방법으로 만들 수 있으면 두 색칠 방법은 동치입니다. 서로 동치가 아닌 색칠 방법은 몇 가지입니까?

여기서 무슨 일이 일어나고 있습니까? 판을 색칠하는 $\binom{49}{2}$ 가지 방법의 집합을 $X$ 라고 합시다. “회전”을 자연스럽게 해석하면 무엇입니까? 답은 이렇습니다. 군 $\mathbb{Z}/4\mathbb{Z}=\left<r\mid r^{4}=1\right>$ 는 한 상태 $x\in X$ 를 다른 상태 $r\cdot x$ 로 보내는 방식으로 이 집합 $X$ 에 어떤 식으로든 “작용”합니다. 여기서 $r\cdot x$ 는 $x$ 를 $90^{\circ}$ 만큼 회전한 것일 뿐입니다. 직관적으로 말하면, 두 배치가 이 “작용”을 통해 서로에게 도달할 수 있으면 같은 것으로 본다는 뜻입니다.

군 작용이라는 개념을 사용하면 이 모든 것을 엄밀하게 표현할 수 있습니다.

16.1 군 작용의 정의

대표적인 예: AIME 문제입니다.

정의 16.1.1.

$X$ 를 집합, $G$ 를 군이라고 합시다. 군 작용은 $g\in G$ 가 $x\in X$ 를 $g\cdot x$ 로 보내도록 하는 이항 연산 $\cdot\colon G\times X\to X$ 입니다. 군 작용은 다음 공리를 만족합니다.

•

임의의 $g_{1},g_{2}\in G$ 와 모든 $x\in X$ 에 대하여 $(g_{1}g_{2})\cdot x=g_{1}\cdot(g_{2}\cdot x)$ 입니다.
•

임의의 $x\in X$ 에 대하여 $1_{G}\cdot x=x$ 입니다.

예제 16.1.2 (군 작용의 예).

$G=(G,\star)$ 를 군이라고 합시다.

(a)

군 $\mathbb{Z}/4\mathbb{Z}$ 는 $7\times 7$ 판을 노란색 또는 초록색으로 칠하는 방법의 집합에 작용할 수 있습니다.
(b)

군 $\mathbb{Z}/4\mathbb{Z}=\left<r\mid r^{4}=1\right>$ 는 $x y$ -평면 $\mathbb{R}^{2}$ 에 $r\cdot(x,y)=(y,-x)$ 와 같이 작용합니다. 다시 말해, 이는 $90^{\circ}$ 만큼의 회전입니다.
(c)

이면체군 $D_{2n}$ 은 $n$ 각형의 꼭짓점을 색칠하는 방법의 집합에 작용합니다.
(d)

군 $S_{n}$ 은 순열 $\sigma$ 를 적용하는 방식으로 $X=\left\{1,2,\dots,n\right\}$ 에 작용합니다. 즉, $\sigma\cdot x\coloneqq\sigma(x)$ 입니다.
(e)

군 $G$ 는 왼쪽 곱셈으로 자기 자신(즉 $X=G$ )에 작용할 수 있습니다. $g\cdot g^{\prime}\coloneqq g\star g^{\prime}$ 로 두면 됩니다.

연습문제 16.1.3.

군 작용은 $G$ 에서 $S_{X}$ 로 가는 군 준동형사상으로도 동등하게 기술할 수 있음을 보이십시오. 여기서 $S_{X}$ 는 $X$ 위의 순열로 이루어진 대칭군입니다.

16.2 안정자군과 궤도

대표적인 예: 다시 AIME 문제입니다.

$X$ 위의 군 작용 $G$ 가 주어지면, $X$ 위의 동치 관계 $\sim$ 를 다음과 같이 정의할 수 있습니다. 어떤 $g\in G$ 에 대하여 $x=g\cdot y$ 이면 $x\sim y$ 입니다. 예를 들어 AIME 문제에서 $\sim$ 는 “회전을 통해 하나를 다른 하나로 만들 수 있음”을 뜻합니다.

질문 16.2.1.

이것이 동치 관계인 이유는 무엇입니까?

이 경우 AIME 문제에서 구하려는 것은 $\sim$ 에 대한 동치류의 개수입니다. 그러므로 이 동치류에 궤도라는 이름을 붙입시다. 궤도는 보통 $\mathcal{O}$ 로 나타냅니다.

늘 그렇듯이, 궤도는 $X$ 를 동치류로 분할합니다.

이와 매우 밀접하게 관련된 개념은 다음과 같습니다.

정의 16.2.2.

점 $x\in X$ 의 안정자군은 $\operatorname{Stab}_{G}(x)$ 로 표기하며, $x$ 를 고정하는 $g\in G$ 들의 집합입니다. 다시 말해

\operatorname{Stab}_{G}(x)\coloneqq\left\{g\in G\mid g\cdot x=x\right\}.

예제 16.2.3.

AIME 문제를 다시 생각해 봅시다. $X$ 는 가능한 상태들의 집합입니다(이번에도 $G=\mathbb{Z}/4\mathbb{Z}$ 입니다). 서로 마주 보는 두 모서리가 노란색으로 칠해진 배치를 $x$ 라 합시다. $1_{G}$ 는 당연히 $x$ 를 고정하며, $180^{\circ}$ 회전인 $r^{2}$ 도 $x$ 를 고정합니다. 그러나 $r$ 과 $r^{3}$ 은 $x$ 를 보존하지 않으므로 $\operatorname{Stab}_{G}(x)=\{1,r^{2}\}\cong\mathbb{Z}/2\mathbb{Z}$ 입니다.

질문 16.2.4.

$\operatorname{Stab}_{G}(x)$ 는 왜 $G$ 의 부분군입니까?

안정자군이 군이라는 사실을 깨닫고 나면, 제가 개인적으로 “궤도가 얼마나 큰지에 대한 기본 정리”라고 부르는 정리에 이르게 됩니다.

정리 16.2.5 (궤도-안정자군 정리).

$\mathcal{O}$ 를 궤도라 하고, 임의의 $x\in\mathcal{O}$ 를 택합시다. $S=\operatorname{Stab}_{G}(x)$ 를 $G$ 의 부분군이라 합시다. $\mathcal{O}$ 와 왼쪽 잉여류들 사이에는 자연스러운 전단사가 존재합니다. 특히,

\left\lvert\mathcal{O}\right\rvert\left\lvert S\right\rvert=\left\lvert G% \right\rvert.

특히 각 $x\in\mathcal{O}$ 의 안정자군은 모두 크기가 같습니다.

증명.

요점은 각 잉여류 $g S$ 가 $\mathcal{O}$ 의 원소 하나, 즉 $g\cdot x$ 를 지정할 뿐이라는 것입니다. $S$ 가 안정자군이라는 사실로부터 어떤 대표원을 고르든 상관이 없다는 것을 알 수 있습니다.

크기가 각각 $\left\lvert S\right\rvert$ 인 $\left\lvert\mathcal{O}\right\rvert$ 개의 잉여류가 $G$ 를 분할하므로, 두 번째 결과를 얻습니다. ∎

16.3 번사이드 보조정리

이제 이 장의 핵심인 궤도의 개수를 세는 방법을 살펴봅시다.

정리 16.3.1 (번사이드 보조정리).

$G$ 가 집합 $X$ 에 작용한다고 합시다. 이 작용의 궤도 개수는 다음과 같습니다.

\frac{1}{\left\lvert G\right\rvert}\sum_{g\in G}\left\lvert\operatorname{FixPt% }g\right\rvert

여기서 $\operatorname{FixPt}g$ 는 $g\cdot x=x$ 를 만족하는 점 $x\in X$ 들의 집합입니다.

증명은 매우 올림피아드다운 풀이가 있으므로 보너스 문제로 미룹니다. 흔히 그렇듯이 이 보조정리는 실제로 번사이드가 증명한 것이 아닙니다. 코시가 먼저 증명했으며, 그래서 때때로 번사이드의 것이 아닌 보조정리라고 불리기도 합니다. 적용 예시는 다음과 같습니다.

예제 16.3.2 (AIME 1996).

$7\times 7$ 체커판의 칸 중 두 칸은 노란색으로, 나머지는 초록색으로 칠합니다. 두 색칠 방식 중 하나에 판의 평면 위 회전을 적용하여 다른 하나를 얻을 수 있으면 두 방식은 동치입니다. 서로 동치가 아닌 색칠 방식은 몇 가지입니까?

$G=\mathbb{Z}/4\mathbb{Z}$ 가 가능한 $\binom{49}{2}$ 가지 색칠 방식의 집합 $X$ 에 작용함을 알고 있습니다. 이제 각 $g\in\mathbb{Z}/4\mathbb{Z}$ 에 대해 $\operatorname{FixPt}g$ 를 명시적으로 계산할 수 있습니다.

•

$g=1_{G}$ 이면 모든 색칠이 고정되므로 그 개수는 $\binom{49}{2}=1176$ 입니다.
•

$g=r^{2}$ 이면 $g$ 에 의해 고정되는 색칠 방식은 정확히 $24$ 가지입니다. 이는 두 칸이 중심에 대해 서로 대칭일 때, 즉 $180^{\circ}$ 회전에 대해 보존될 때 일어납니다.
•

$g=r$ 또는 $g=r^{3}$ 이면 고정되는 색칠 방식이 없습니다.

$\left\lvert G\right\rvert=4$ 이므로 평균은 다음과 같습니다.

\frac{1176+24+0+0}{4}=300.

연습문제 16.3.3 (MathCounts 장 Target Round).

원형 돌림판이 크기가 같은 일곱 구역으로 나뉘어 있고, 각 구역은 빨간색 또는 파란색으로 칠해집니다. 한 색칠을 회전하여 다른 색칠을 얻을 수 있으면 두 색칠은 같은 것으로 간주합니다. 돌림판을 칠하는 방법은 몇 가지입니까? (답: 20)

“실전적인” 적용 예시를 더 보려면 [MAX13]를 참고하십시오.

16.4 원소의 켤레화

대표적인 예: $S_{n}$ 에서 켤레류는 “순환 유형”입니다.

특히 자주 쓰이는 작용으로 이른바 켤레화가 있습니다. $G$ 가 다음과 같이 자기 자신에 작용하도록 합니다:

g\colon h\mapsto ghg^{-1}.

이 정의가 다소 인위적이라고 생각하실 수도 있습니다. 원소 $ghg^{-1}$ 에 누가 관심을 가지겠습니까? 이 정의가 그리 부자연스럽지 않다는 것을 설득해 보겠습니다.

예제 16.4.1 ( $S_{n}$ 에서의 켤레).

$G=S_{5}$ 라 하고 $\pi\in S_{5}$ 를 하나 고정합시다. 질문은 이것입니다. $\pi\sigma\pi^{-1}$ 는 $\sigma$ 와 관련이 있습니까? 이를 보여 주기 위해 순열 $\sigma\in S_{5}$ 의 예를 완전히 무작위로 하나 적어 보겠습니다.

\text{만약}\sigma=\;\begin{array}[]{ccc}1&\mapsto&3\\ 2&\mapsto&1\\ 3&\mapsto&5\\ 4&\mapsto&2\\ 5&\mapsto&4\end{array}\qquad\text{그러면}\qquad\pi\sigma\pi^{-1}=\begin{array}[]{% ccc}\pi(1)&\mapsto&\pi(3)\\ \pi(2)&\mapsto&\pi(1)\\ \pi(3)&\mapsto&\pi(5)\\ \pi(4)&\mapsto&\pi(2)\\ \pi(5)&\mapsto&\pi(4)\end{array}

따라서 고정한 $\pi$ 는 $\sigma$ 의 구조를 사실상 전혀 바꾸지 않습니다: 단지 각 원소 $1$ , $2$ , $3$ , $4$ , $5$ 의 “이름을” $\pi(1)$ , $\pi(2)$ , $\pi(3)$ , $\pi(4)$ , $\pi(5)$ 로 바꿀 뿐입니다.

하지만 잠깐, 이렇게 말씀하실 수도 있습니다. 그것은 켤레화에 대해 좋은 성질을 보이는 아주 특수한 유형의 군일 뿐이지 않습니까? 이것이 왜 더 일반적으로도 의미가 있습니까? 제가 드릴 말씀은 이것뿐입니다: 케일리 정리를 기억하십시오! (이는 문제 1F이었습니다.)

어쨌든, 이제 다음과 같이 정의할 수 있습니다:

정의 16.4.2.

군 $G$ 의 켤레류는 켤레화 작용에 대한 $G$ 의 궤도입니다.

예를 들어, $S_{n}$ 의 켤레류가 무엇인지 살펴봅시다.

예제 16.4.3 ( $S_{n}$ 의 켤레류는 순환 유형에 대응합니다).

직관적으로 위의 논의는 $S_{n}$ 의 두 원소가 같은 “모양”을 가지면 원소들의 이름이 무엇이든 서로 켤레여야 한다는 것을 말해 줍니다. “모양”이라는 개념을 엄밀하게 만드는 올바른 방법은 순환 표기입니다. 예를 들어 다음 순열을 생각해 봅시다.

\sigma_{1}=(1\;3\;5)(2\;4)

이는 순환 표기로, $1\mapsto 3\mapsto 5\mapsto 1$ 이고 $2\mapsto 4\mapsto 2$ 라는 뜻입니다. 이 순열은 다음 순열과 켤레입니다.

\sigma_{2}=(1\;2\;3)(4\;5)

또는 원소의 이름을 다른 어떤 방식으로 바꾼 치환과도 켤레입니다. 따라서 $\sigma$ 의 켤레류를 다음과 같이 생각할 수 있습니다

(-\;-\;-)(-\;-).

더 일반적으로, $S_{n}$ 의 두 원소가 켤레일 필요충분조건은 순환 분해에서 같은 “모양”을 가지는 것임을 보일 수 있습니다.

질문 16.4.4.

$S_{n}$ 의 켤레류의 개수가 $n$ 의 분할의 개수와 같음을 보이십시오.

위의 그림을 제시한 김에, 다음도 정의해 두겠습니다:

정의 16.4.5.

$G$ 를 군이라 합시다. $Z(G)$ 로 표기하는 $G$ 의 중심은 모든 $g\in G$ 에 대해 $xg=gx$ 를 만족하는 원소 $x\in G$ 들의 집합입니다. 더 간결하게 쓰면,

Z(G)\coloneqq\left\{x\in G\mid gx=xg\;\forall g\in G\right\}.

이것이 실제로 $G$ 의 부분군임을 확인할 수 있습니다.

질문 16.4.6.

$Z(G)$ 는 왜 $G$ 의 정규 부분군입니까?

질문 16.4.7.

중심에 속한 원소들의 켤레류는 무엇입니까?

충분히 자주 쓰이므로 명시적으로 짚고 넘어가야 할 자명한 결과입니다:

따름정리 16.4.8 (아벨 군에서의 켤레화는 자명합니다).

$G$ 가 아벨 군이면, 켤레류의 크기는 모두 1입니다.

16.5 생각해 볼 만한 조금 더 어려운 문제

문제 16A (PUMaC 2009 C8).

타오타오는 구슬 일곱 개로 이루어진 팔찌를 사려고 하며, 각 구슬은 주황색, 흰색, 검은색 중 하나입니다. (팔찌는 공간에서 회전하거나 뒤집을 수 있습니다.) 가능한 팔찌의 개수를 구하십시오.

힌트. 번사이드 보조정리를 그대로 적용하면 $198$ 이라는 답을 얻습니다(해당 군은 $D_{14}$ 입니다).

문제 16B.

같은 켤레류에 속하는 두 원소의 위수가 같음을 보이십시오.

힌트. 이를 확인하는 방법은 여러 가지가 있습니다. 하나는 그냥 대수적으로 식을 조작하는 것입니다. 다른 하나는 케일리 정리를 사용하여 $G$ 를 대칭군에 매장하는 것입니다.

문제 16C.

^†^†margin:

번사이드 보조정리를 증명하십시오.

힌트. $g\cdot x=x$ 인 순서쌍 $(g,x)$ 를 두 가지 방법으로 세십시오.

문제 16D (“류 방정식”).

$G$ 가 유한군이라고 합시다. 각 $g\in G$ 에 대하여 중심화 부분군 $C_{G}(g)=\{x\in G\mid xg=gx\}$ 를 정의합니다. 다음을 보이십시오.

\left\lvert G\right\rvert=\left\lvert Z(G)\right\rvert+\sum_{s\in S}\frac{% \left\lvert G\right\rvert}{\left\lvert C_{G}(s)\right\rvert}

여기서 $S\subseteq G$ 는 다음과 같이 정의됩니다. $|C|>1$ 인 각 켤레류 $C\subseteq G$ 에 대하여 $C$ 의 대표원을 하나 골라 $S$ 에 추가합니다.

문제 16E (고전).