장 16 군의 작용으로 AIME 문제를 압도적으로 풀어내기

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

(AIME 1996) $7\times 7$ 체커보드의 칸 중 두 개를 노란색으로 칠하고, 나머지는 초록색으로 칠합니다. 두 색칠 방식이 보드 평면 상의 회전으로 서로 얻어질 수 있다면 동치라고 합니다. 서로 동치가 아닌 색칠 방식은 몇 가지나 가능합니까?

여기서 무슨 일이 일어나고 있습니까? $X$ 를 보드에 대해 가능한 $\binom{49}{2}$ 가지 색칠 방식들의 집합이라고 합시다. ”회전”에 대한 자연스러운 해석은 무엇입니까? 답: 군 $\mathbb{Z}/4\mathbb{Z}=\left<r\mid r^{4}=1\right>$ 이 어떤 방식으로든 이 집합 $X$ 에 ”작용”하여, 한 상태 $x\in X$ 를 또 다른 상태 $r\cdot x$ 로 보내는데, 이는 그저 $x$ 를 $90^{\circ}$ 회전시킨 것입니다. 직관적으로 말하면, 두 배치가 이 ”작용”에 의해 서로로부터 도달될 수 있다면 같다고 말하는 것입니다.

우리는 군의 작용이라는 개념을 이용해 이 모든 것을 엄밀하게 만들 수 있습니다.

16.1 군의 작용의 정의

대표적인 예: AIME 문제.

정의 16.1.1.

$X$ 를 집합, $G$ 를 군이라고 합시다. 군의 작용이란 이항 연산 $\cdot\colon G\times X\to X$ 으로, 이는 $g\in G$ 가 $x\in X$ 를 $g\cdot 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$ 의 안정화군(stabilizer)은 $\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}$ 도 마찬가지입니다. 하지만 $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\mathcal{O}\right\rvert$ 개의 잉여류가 각각 크기 $\left\lvert S\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 (매스카운츠 챕터 타겟 라운드).

원형 회전판이 크기가 같은 일곱 개의 구역으로 나뉘어 있고, 각 구역은 빨간색 또는 파란색으로 칠해져 있습니다. 두 색칠은 하나를 회전시켜 다른 하나를 얻을 수 있으면 같은 것으로 간주합니다. 회전판을 칠하는 방법은 몇 가지입니까? (답: 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$ 를 군이라 합시다. $G$ 의 중심은 $Z(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).

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

힌트. 번사이드 보조정리(Burnside’s lemma)를 직접 적용하면 $198$ 이라는 답을 얻습니다(관련 군은 $D_{14}$ 입니다).

문제 16B.

같은 켤레류에 속한 두 원소가 같은 위수를 가짐을 보이십시오.

힌트. 이를 확인하는 방법에는 여러 가지가 있습니다. 하나는 그냥 대수적 조작을 하는 것입니다. 다른 하나는 케일리의 정리(Cayley’s theorem)를 사용하여 $G$ 를 대칭군 안에 매장하는 것입니다.

문제 16C.

^†^†margin:

번사이드 보조정리(Burnside’s lemma)를 증명하십시오.

힌트. $g\cdot x=x$ 인 쌍 $(g,x)$ 의 개수를 이중으로 셈하십시오.

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

$G$ 를 유한군이라 하겠습니다. 각 $g\in G$ 에 대해 중심화군(centralizer) $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 (고전적).