번사이드 보조정리
"오늘의AI위키" 는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다."오늘의AI위키" 의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차 보기/숨기기
2. 정의
유한군 G 가 집합 X 위에 (왼쪽에서) 작용 한다고 하자. 각 g\in G 에 대하여,X^g=\{x\in X\colon g\cdot x=x\} g 의 고정점의 집합이라고 하자. 또한,X/G=\{G\cdot x\colon x\in X\} |X/G|=\frac1
\sum_{g\in G}|X^g|
3. 증명
번사이드 보조정리는 다음과 같이 증명할 수 있다.\sum_{g\in G}|X^g| =|\{(g,x)\in G\times X\colon g\cdot x=x\}| =\sum_{x\in X}|G_x| G_x 는 x 의 안정자군이다.)=\sum_{x\in X}\frac
=\sum_{A\in X/G}\sum_{x\in A}\fracX/G 는 X 에 대한 분할 을 이룬다.)=\sum_{A\in X/G}|G| =|X/G|\cdot|G| G 의 원소 g 에 대한 합을 집합 X 의 원소 x 에 대한 합으로 다시 표현하는 것이다.\sum_{g \in G}|X^g| = \#\{(g,x)\in G\times X \mid g \cdot x = x\} = \sum_{x \in X} |G_x|. X^g = \{x \in X \mid g \cdot x = x\} 는 g \in G 에 의해 고정된 X 의 원소들의 집합이고, G_x = \{g \in G \mid g \cdot x = x\} 는 x \in X 를 고정하는 G 의 안정자 부분군이다.x \in X 에 대해 궤도 G\cdot x = \{g\cdot x \mid g \in G\} 와 왼쪽 잉여류 집합 G/G_x 사이에 전단사가 존재한다. 라그랑주 정리 에 의해 다음이 성립한다.|G \cdot x| = [G\,:\,G_x] = |G| / |G_x|. \sum_{x \in X} |G_x| = \sum_{x \in X} \frac = |G| \sum_{x \in X}\frac{1}.X 를 X/G 에서 궤도의 분리된 합(disjoint union)으로 표현하면 다음과 같다.|G|\, \sum_{x \in X}\frac{1}\sum_{g \in G}|X^g| = |G| \cdot |X/G|. G 가 자신에게 작용하는 켤레 작용(conjugate action)을 고려하는 켤레류 방정식의 증명과 유사하다. X = G 이고 g.x = gxg^{-1} 일 때, x 의 안정자(stabilizer)는 x 의 중심화 부분군(centralizer) G_x = Z_G(x) 이다.
4. 역사
이 보조정리는 1845년 오귀스탱 루이 코시 가 이미 알고 있었고, 1887년 페르디난트 게오르크 프로베니우스 의 논문에도 수록되어 있다.윌리엄 번사이드 는 자신의 책에서 프로베니우스를 인용하며 이 보조정리의 증명을 수록하였다.스티글러의 명명법칙 으로 알려져 있다.
5. 응용 예시
다음은 번사이드 보조정리를 사용하여 정육면체 의 면을 3가지 색상으로 칠하는 경우의 수를 구하는 예시이다. 여기서 회전하여 같은 모양이 되는 경우는 동일한 것으로 간주한다.6 가지의 모든 색상 조합의 집합이라고 하자. 그리고 정육면체의 회전군 가 에 작용한다고 가정한다. 이때, 의 두 원소가 같은 궤도에 속한다는 것은 한쪽이 다른 쪽을 회전시킨 결과와 같다는 것을 의미한다. 따라서 서로 다른 색칠 방법의 수는 궤도의 수와 같으며, 이는 군 의 24개 원소가 각각 고정하는 집합의 크기를 계산하여 구할 수 있다.
항등원 6 개의 모든 원소를 고정한다.면의 90도 회전 (6개) : 33 개의 원소를 고정한다. (회전축을 지나는 두 면과 옆면의 색상 조합을 고려)면의 180도 회전 (3개) : 34 개의 원소를 고정한다. (회전축을 지나는 두 면과 옆면의 두 쌍의 색상 조합을 고려)꼭짓점의 120도 회전 (8개) : 32 개의 원소를 고정한다. (회전축을 기준으로 위아래 색상 조합을 고려)변의 180도 회전 (6개) : 33 개의 원소를 고정한다. (회전축을 지나는 변에 붙어있는 두 면과 옆면의 색상 조합을 고려) \frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57 \frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right) 5. 1. 목걸이 문제
길이 3의 가능한 비트 벡터 또는 비트열은 8개이지만, 문자열의 끝을 연결하면 000, 001, 011, 111의 표준 형태로 주어진 길이 3의 4개의 2색 목걸이 만 얻을 수 있다. 다른 문자열 100과 010은 회전에 의해 001과 동일하며, 110과 101은 011과 동일하다. 즉, 회전 등가성은 문자열 집합 ''X''를 네 개의 궤도로 분할한다.1 ⁄3 (8 + 2 + 2).1 ⁄4 (16 + 2 + 4 + 2)이며, 0000, 0001, 0011, 0101, 0111, 1111의 표준 형태로 나타낸다.5. 2. 정육면체 색칠 문제
번사이드 보조정리를 사용하면 세 가지 색상을 사용하여 정육면체 면을 회전하여 일치하는 경우를 제외하고 색칠하는 경우의 수를 계산할 수 있다.색칠된 정육면체 6 이다. 이제 정육면체의 회전군 ''G''가 ''X''에 작용한다고 하자. ''X''의 두 원소가 같은 궤도에 있다는 것은 한쪽이 다른 쪽의 회전이라는 의미이다. 따라서 회전하여 일치하는 경우를 제외한 색칠의 수는 궤도의 수와 같고, 이는 ''G''의 각 원소가 고정하는 점의 개수를 세어 계산할 수 있다.항등원 : 36 개의 모든 원소를 고정한다.90도 면 회전 (6개): 회전축을 통과하는 두 면과 나머지 4개 면(측면)의 색상 조합을 고려하여 33 개의 원소를 고정한다. 180도 면 회전 (3개): 회전축을 통과하는 두 면과 측면의 2쌍의 면의 색상 조합을 고려하여 34 개의 원소를 고정한다. 120도 꼭짓점 회전 (8개): 회전축을 기준으로 위아래 색상 조합을 고려하여 32 개의 원소를 고정한다. 180도 모서리 회전 (6개): 회전축을 통과하는 모서리에 접하는 두 면과 나머지 4개 면(측면)의 색상 조합을 고려하여 33 개의 원소를 고정한다. \frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57 \frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right)
6. 열거 vs 생성
번사이드 보조정리는 서로 다른 객체의 개수를 세지만, 객체를 생성하지는 않는다. 일반적으로 동형 사상 제거를 이용한 조합적 생성은 객체 ''x''에 대한 ''g''의 대칭성을 고려한다. 하지만 ''g.x = x''인지 확인하는 대신, ''g.x''가 이미 생성되었는지 확인한다. 이를 수행하는 한 가지 방법은 ''g.x''가 사전식 순서로 ''x''보다 작은지 확인하는 것이다. 각 동치류의 사전식으로 가장 작은 원소를 해당 류의 표준 형식으로 사용한다.
참조
[1]
문서
Burnside
[2]
문서
Rotman
[3]
간행물
Isomorphism and the N-Queens problem
[4]
간행물
A lemma that is not Burnside's
[5]
저널
Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul
1887
[6]
서적
Theory of groups of finite order
https://archive.org/[...]
Cambridge University Press
1897
[7]
저널
A lemma that is not Burnside’s
1979
CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.help@durumis.com