번사이드 보조정리

이 번사이드 보조정리는 유한 대칭군 위에서 기술되어 있습니다.

0. 유한군 용어

유한 집합 $X$에 대해

• $X$의 대칭군symmetric group = $S_X = \{ \sigma \in X \times X : \sigma \text{ is bijective function}\}$
• $X$의 순열군permutation group은 대칭군의 부분군

이다.

1. 정의

$(G,\circ,id)$를 유한 집합 $X$의 순열군으로 놓자. 그러면 다음이 성립한다:

$|X/G| = \frac {1}{|G|} \sum _{\sigma \in G} | X_\sigma |$

여기서 사용되었고 또 앞으로 사용할 집합들의 의미는 다음과 같습니다:

• $G(x) = \{ \sigma (x) : \sigma \in G\}$ for each $x \in X$
• $X/G = \{ G(x) : x \in X \}$
• $X\_\sigma = \{ x \in X: \sigma (x) =x \}$ for each $ \sigma \in G$
• $G_x = \{\sigma \in G : \sigma(x) = x \}$ for each $x \in X$

1.1. 예시

입체 도형을 색칠하는 경우의 수를 구할 때 사용됩니다. $X$를 주어진 색깔로 각 면을 칠하는 방법으로 놓고, $G$에서 회전을 고려해주면 됩니다.

문제. 정육면체를 4가지 색으로 칠하는 방법의 가짓수는 얼마인가? 단, 돌렸을 때 같아지는 것은 하나로 센다.

‘색칠’과 ‘돌리기’를 동시에 고려해서 개수를 세는 것은 힘들기 때문에 이 대상을 군으로 바라보면서 그 둘을 분리할 수 있도록 번사이드 보조정리를 사용합니다.

• $X=\{1,2,3,4\}^6$, $x \in X$는 (윗면, 앞면, 오른면, 뒷면, 왼면, 아랫면) 순서로 색칠된다.
• $G \subset X \times X$, 정육면체를 회전하는 방법

이 때, $G$가 $X$의 순열군이라는 것은 어렵지 않게 보일 수 있습니다.

• $G \subseteq S_X$
• $(G, \circ$)는 군이다.
  • $\forall \sigma_1 , \sigma_2 \in G, \sigma_1 \circ \sigma_2 \in G$ (닫혀있음)
  • 항등함수($id$)가 $G$에 포함된다.
  • $\forall \sigma_1 , \sigma_2 , \sigma_3 \in G, (\sigma_1 \circ \sigma_2) \circ \sigma_3 = \sigma_1 \circ (\sigma_2 \circ \sigma_3)$ (결합법칙)
  • $\forall \sigma \in G, \exists \sigma^{-1} \in G \; \sigma \circ \sigma ^{-1} = \sigma^{-1} \circ \sigma = id$ (역원)

이제 번사이드 보조정리를 사용하기 위해서는 회전 함수로 이루어진 $G$를 직접 세워야 합니다. 일단 6개의 면이 있고 각 면에 대해 옆면을 회전하는 방법이 4가지이므로, $\vert G\vert = 24$입니다.

이제 각 $\sigma \in G$에 대해 $X_\sigma$를 구하기 앞서 $G$의 모든 원소들을 찾아야 하는데, 헷갈리면 큐브 하나를 옆에 들고 돌려가면서 세는 ㄷ것도 괜찮습니다.

• 돌리지 않음 ( $\{id\}$)
• 면에 대해 90도 회전하는 방법 6가지 ($G_1$)
• 면에 대해 180도 회전하는 방법 3가지 ($G_2$)
• 꼭짓점에 대해 120도 회전하는 방법 8가지 ($G_3$)
• 모서리에 대해 180도 회전하는 방법 6가지 ($G_4$)

‘면에 대해 회전한다’는 것은 면의 중심을 관통하는 회전축을 기준으로 고정된 방향(시계방향, 반시계방향 중 하나 선택)으로 돌린다는 것을 뜻합니다.

‘꼭짓점에 대해 회전한다’는 정육면체에서 양 끝에 있는 꼭짓점을 관통하는 회전축을 기준으로 돌리는 것을 의미합니다.

‘모서리에 대해 회전한다’는 모서리의 절반과 반대쪽 모서리의 절반을 관통하는 회전축을 기준으로 합니다.

이 방법들이 서로 다르고 개수를 모두 더했을 때 24가 되므로 회전하는 방법을 이렇게 나눌 수 있다는 것을 확인할 수 있습니다. 즉, $\{G_1, G_2 ,G_3, G_4, \{id\} \}$는 $G$의 분할partition입니다.

이제 번사이드 보조정리를 사용하면

• $\vert G\vert = 24$
• $\vert X\_{id}\vert = \vert X\vert = 4^6$
• $\forall \sigma \in G_{1} , \;\vert X_\sigma\vert = 4^3$ (윗면에 대해 회전했다면 윗면, 옆면, 아랫면 색깔에 의해 결정된다)
• $\forall \sigma \in G*2,\; \vert X*\sigma\vert = 4^4$ (윗면에 대해 회전했다면 윗면, 아랫면, 옆면1, 옆면2 색깔에 의해 결정된다)
• $\forall \sigma \in G*3, \; \vert X*\sigma\vert = 4^2$ (대상 꼭짓점에 인접한 면과 그렇지 않은 면의 색깔에 의해 결정된다)
• $\forall \sigma \in G*4, \;\vert X*\sigma\vert = 4^3$ (대상 모서리에 인접한 면과 그 반대쪽에 있는 면, 그리고 옆면의 색깔에 의해 결정된다)

$|X/G| = \frac 1 {|G|} \sum _{ \sigma \in G} |X_\sigma| = \frac 1 {24} (4^6 + 6 \times 4^3 + 3 \times 4^4 + 8 \times 4^2 + 6 \times 4^3 )$

마지막으로 얻는 식에서 알 수 있는 점은 칠할 수 있는 색깔의 가짓수는 사실 식의 형태에 큰 영향을 주지 않는다는 거에요! 만약 정육면체를 $n$개의 색으로 칠하는 방법의 수를 구한다면 다음과 같습니다:

$\frac 1 {24} ( n^6 + 3n^4 + 12n^3 + 8n^2 )$

2. 증명

2.1. 유한군에서의 궤도-안정자군 정리

$|G_x| |G(x)| = |G|$

이 부분이 가장 힘든 단계입니다.

증명

$G_x$를 확장해서 다루기 위해 $H_{x,y}$를 다음과 같이 정의하자:

$H_{x,y} = \{ \sigma \in G : \sigma(x) = y \}$

1. $y \in G(x)$일 때, $\vert H_{x,y}\vert = \vert G_x\vert $이다.

$ f: Gx \to H{x,y} $를 다음과 같이 정의한다:

$f(\sigma) = h \circ \sigma \quad \text{where } h(x) = y$

$f \in G_x \times H_{x,y}$이고, 모든 $\sigma \in G_x$가 $H_{x,y}$로 대응되므로 $f$는 함수이다.

$h$는 일대일대응bijective이다.

$h^{-1} \in G$이고, 따라서 $f^{-1}(\sigma) = h^{-1} \circ \sigma$로 정의했을 때 $f^{-1}$은 $f$의 역함수이다.

따라서 $f$는 일대일대응bijective이다. 즉, $\vert H\_{x,y} \vert = \vert G_x\vert$이다.

2. 임의의 $x \in X$에 대해 $\{H_{x,y}:y \in G(x)\}$는 $G$의 분할이다

분할의 정의를 하나씩 확인해보면 됩니다. 겹치는 일이 없고, 모두 합쳤을 때 $G$가 됩니다.

2.2. 나머지 과정

다음과 같은 관계relation을 고려합니다:

$R = \{(x , \sigma )\in X \times G : \sigma(x) = x\}$

이런 관계를 정의하면 좋은 이유는 두 번 세면서 등식을 얻어내기 좋기 때문이에요.

$|R| = \sum _{x \in X} | G_x | = \sum _{ \sigma \in G } |X_\sigma |$

이대로 위에서 증명한 보조정리를 써가면서 전개하면 원하던 결과를 얻을 수 있습니다.

$\begin{aligned} \frac 1 {|G|} \sum _{\sigma \in G} |X_\sigma| &= \sum _{x \in X} \frac {|G_x|}{|G|} \\ &= \sum _{x\in X} \frac {1}{|G(x)|} = \sum _{A \in X/G} \sum _{x \in A} \frac {1}{|A|} = |X/G| \end{aligned}$