KAIST SoC 19’

4 minute read

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

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: G_x \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}\]

Leave a comment