번사이드 보조정리

번사이드 보조정리 (Burnside's Lemma)는 군론에서 유한군이 유한 집합에 작용할 때, 그 작용에 의한 궤도의 개수를 계산하는 데 사용되는 정리이다. '궤도-안정자 정리'와 밀접한 관련이 있으며, 조합론적 문제, 특히 대칭성을 고려해야 하는 경우의 수를 셀 때 유용하게 활용된다.

정의

유한군 G가 유한 집합 X에 작용한다고 하자. X의 원소 x의 궤도를 Gx = {gx | g ∈ G} 로 정의하고, g ∈ G에 대해 X의 원소 중 g에 의해 고정되는 원소들의 집합을 Xg = {x ∈ X | gx = x} 로 정의한다. 이때, G의 작용에 의한 X의 궤도의 개수 |X / G|는 다음과 같이 주어진다.

|X / G| = (1 / |G|) ∑_{g ∈ G} |Xg|

즉, 궤도의 개수는 군 G의 모든 원소에 대해 그 원소에 의해 고정되는 X의 원소의 개수를 모두 더한 후, 군 G의 크기로 나눈 값과 같다.

증명

번사이드 보조정리의 증명은 다음과 같이 이루어진다.

먼저, 다음과 같은 집합 S를 정의한다.

S = {(g, x) | g ∈ G, x ∈ X, gx = x}

이 집합의 크기 |S|를 두 가지 방법으로 센다.

1. g를 고정하고 x를 움직이는 경우: |S| = ∑_{g ∈ G} |Xg|
2. x를 고정하고 g를 움직이는 경우: |S| = ∑_{x ∈ X} |Gx| |Gₓ| = ∑_{x ∈ X} |G|

여기서 Gₓ는 x의 안정자군으로, x를 고정시키는 G의 원소들의 집합이다. 궤도-안정자 정리에 의해 |Gx| |Gₓ| = |G| 이 성립한다.

따라서, ∑_{g ∈ G} |Xg| = ∑_{x ∈ X} |G| 이다. X의 원소들은 각 궤도에 속하며, 각 궤도는 서로소이므로, ∑_{x ∈ X} |G| = |X / G| |G| 이다.

결론적으로, ∑_{g ∈ G} |Xg| = |X / G| |G| 이므로, |X / G| = (1 / |G|) ∑_{g ∈ G} |Xg| 이다.

활용 예시

정육면체의 각 면을 n가지 색으로 칠하는 방법의 수를 구하는 문제를 생각해보자. 정육면체의 회전군은 크기가 24인 군이다. 이 군이 정육면체의 각 면을 칠하는 경우의 수 (n^6)에 작용한다. 번사이드 보조정리를 이용하여 궤도의 개수, 즉 서로 다른 색칠 방법의 수를 계산할 수 있다. 이 경우, 각 회전 변환에 대해 그 변환에 의해 고정되는 색칠 방법의 수를 계산하고, 이 값들을 모두 더한 후 24로 나누면 답을 얻을 수 있다.

참고 문헌

• Artin, Michael. Algebra. Prentice Hall, 1991.
• Dummit, David S., and Richard M. Foote. Abstract Algebra. 3rd ed. John Wiley & Sons, 2004.