번사이드 보조정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

번사이드 보조정리는 유한군이 집합에 작용할 때 궤도의 개수를 계산하는 데 사용되는 정리이다. 이 정리는 궤도의 개수가 각 군 원소에 의해 고정된 점들의 수의 평균과 같다고 말한다. 번사이드 보조정리는 코시가 처음 발견했고, 윌리엄 번사이드가 그의 저서에 증명을 수록했지만, 번사이드가 직접 증명한 것은 아니다. 이 정리는 정육면체 색칠 문제와 같은 조합론적 문제, 특히 대칭성을 고려해야 하는 문제에 응용된다.

번사이드 보조정리

개요

이름	번사이드 보조정리
분야	군론
관련 항목	번사이드의 정리

내용

공식	만약 유한군 G가 집합 X에 작용하면, 궤도의 수는 다음과 같다. \|X/G\| = 1/\|G\| * Σ \|X^g\|, 여기서 X^g는 g에 의해 고정되는 X의 원소 집합이다.
설명	G가 X에 작용할 때, 각 g ∈ G에 대해 X^g는 g에 의해 고정되는 X의 원소들의 집합을 나타낸다. 번사이드 보조정리는 이러한 고정점들의 수를 이용하여 궤도의 총 개수를 계산하는 방법을 제공한다.

활용

응용	번사이드 보조정리는 조합론적 문제에서 대칭성을 고려하여 경우의 수를 계산하는 데 유용하게 사용된다. 예를 들어, 정다면체를 색칠하는 방법의 수를 계산하거나, 그래프의 동형인 형태의 수를 계산하는 데 활용될 수 있다.

📚 더 읽어볼만한 페이지

군론 - 점군
점군은 도형의 병진 조작을 제외한 대칭 조작들의 집합으로 군론의 공리를 만족하며, 쉐인플리스 기호나 허먼-모건 기호로 표기되고, 대칭 조작에 대응하는 행렬 표현은 가약 표현과 기약 표현으로 분해될 수 있다.
군론 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.
보조정리 - 베주 항등식
베주 항등식은 주 아이디얼 정역에서 두 원소의 최대공약수를 그 두 원소의 정수 배의 합으로 나타낼 수 있다는 정리이며, 확장 유클리드 알고리즘을 통해 베주 계수를 구할 수 있고, 정수, 다항식 등 다양한 대수적 구조로 확장 가능하다.
보조정리 - 모스 이론
모스 이론은 미분다양체 위의 함수의 임계점과 지표를 이용하여 다양체의 위상수학적 성질을 연구하는 이론으로, 함수값에 따른 부분공간 변화를 관찰하여 다양체의 호몰로지를 계산하고 위상수학적 성질을 밝히는 데 응용된다.

1. 개요
2. 정의
3. 증명
4. 역사
5. 응용 예시
- 5.1. 목걸이 문제
- 5.2. 정육면체 색칠 문제
6. 열거 vs 생성

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{>G|}

👆

좌우로 밀어서 보기

(궤도-안정자군 정리)

=\sum_{A\in X/G}\sum_{x\in A}\frac{>G|}

👆

좌우로 밀어서 보기

( $X/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}

👆

좌우로 밀어서 보기

\ =\ |G|\!\sum_{A\in X/G}\, \sum_{x\in A} \frac{1}

👆

좌우로 밀어서 보기

\ =\ |G|\! \sum_{A\in X/G} 1 \ =\ |G|\,|X/G|.

그러므로 다음의 결과를 얻는다.

:

\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년 페르디난트 게오르크 프로베니우스의 논문에도 수록되어 있다. 1897년 윌리엄 번사이드는 자신의 책에서 프로베니우스를 인용하며 이 보조정리의 증명을 수록하였다. 번사이드는 군론에서 수많은 보조정리를 증명했지만, "번사이드 보조정리"는 그가 증명하지 않은 몇 안 되는 보조정리 중 하나이다. 그래서 이 보조정리는 "번사이드가 증명하지 않은 보조정리"라고도 불린다.

번사이드는 1897년 유한군에 관한 저서에서 이 보조정리를 언급하고 증명했는데, 이는 프로베니우스의 공헌으로 여겨진다. 그러나 이 공식은 프로베니우스 이전인 1845년에 이미 코시가 알고 있었다. 따라서 이 보조정리는 때때로 '번사이드의 정리가 아닌 보조정리'라고 불린다. 과학적 발견에 대한 이러한 잘못된 명명은 스티글러의 명명법칙으로 알려져 있다.

번사이드는 《유한군론》(1897년)에서 프로베니우스의 연구를 바탕으로 이 보조정리를 언급하고 증명했다. 그러나 이 공식은 이미 1845년에 코시에 의해 알려져 있었다. 번사이드가 널리 알려진 이 보조정리를 단순히 코시의 공로로 돌리는 것을 생략한 것으로 보인다. 그 결과, 이 보조정리는 종종 '번사이드가 아닌 보조정리'라고도 불린다. 번사이드가 이 분야에 많은 공헌을 했기 때문에, 이러한 명칭이 반드시 이상한 것만은 아니다.

5. 응용 예시

다음은 번사이드 보조정리를 사용하여 정육면체의 면을 3가지 색상으로 칠하는 경우의 수를 구하는 예시이다. 여기서 회전하여 같은 모양이 되는 경우는 동일한 것으로 간주한다.

--

를 특정 방향으로 정육면체의 면을 칠하는 3⁶가지의 모든 색상 조합의 집합이라고 하자. 그리고 정육면체의 회전군 가 에 작용한다고 가정한다. 이때, 의 두 원소가 같은 궤도에 속한다는 것은 한쪽이 다른 쪽을 회전시킨 결과와 같다는 것을 의미한다. 따라서 서로 다른 색칠 방법의 수는 궤도의 수와 같으며, 이는 군 의 24개 원소가 각각 고정하는 집합의 크기를 계산하여 구할 수 있다.

* [[항등원]]: 3⁶개의 모든 원소를 고정한다.
* 면의 90도 회전 (6개): 3³개의 원소를 고정한다. (회전축을 지나는 두 면과 옆면의 색상 조합을 고려)
* 면의 180도 회전 (3개): 3⁴개의 원소를 고정한다. (회전축을 지나는 두 면과 옆면의 두 쌍의 색상 조합을 고려)
* 꼭짓점의 120도 회전 (8개): 3²개의 원소를 고정한다. (회전축을 기준으로 위아래 색상 조합을 고려)
* 변의 180도 회전 (6개): 3³개의 원소를 고정한다. (회전축을 지나는 변에 붙어있는 두 면과 옆면의 색상 조합을 고려)

따라서 각 원소가 고정하는 집합의 크기의 평균은 다음과 같이 계산된다.

: $\frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57$

결론적으로, 정육면체의 면을 3가지 색으로 칠하는 방법은 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를 네 개의 궤도로 분할한다.

: X = {000} ∪ {001, 010, 100} ∪ {011, 101, 110} ∪ {111}.

번사이드 보조정리는 널 회전을 포함하여 3개의 회전 수와 각 회전에 의해 변경되지 않은 비트열의 수를 사용한다. 모든 8개의 비트 벡터는 널 회전에 의해 변경되지 않으며, 두 개(000과 111)는 다른 두 회전에 의해 변경되지 않는다. 따라서 궤도 수는 다음과 같다.

: 4 = ¹⁄₃(8 + 2 + 2).

길이 4의 경우 가능한 비트열은 16개이다. 4개의 회전이 있으며, 널 회전은 모든 16개의 문자열을 변경하지 않고, 1-회전과 3-회전은 각각 두 개의 문자열(0000과 1111)을 변경하지 않으며, 2-회전은 4개의 비트열(0000, 0101, 1010, 1111)을 변경하지 않는다. 따라서 고유한 목걸이의 수는 6 = ¹⁄₄(16 + 2 + 4 + 2)이며, 0000, 0001, 0011, 0101, 0111, 1111의 표준 형태로 나타낸다.

n 비트와 k 색의 일반적인 경우는 목걸이 다항식으로 주어진다.

5.2. 정육면체 색칠 문제

번사이드 보조정리를 사용하면 세 가지 색상을 사용하여 정육면체 면을 회전하여 일치하는 경우를 제외하고 색칠하는 경우의 수를 계산할 수 있다.

먼저, 고정된 정육면체에 3가지 색을 칠하는 모든 경우의 수의 집합을 X라고 하자. |X|=3⁶이다. 이제 정육면체의 회전군 G가 X에 작용한다고 하자. X의 두 원소가 같은 궤도에 있다는 것은 한쪽이 다른 쪽의 회전이라는 의미이다. 따라서 회전하여 일치하는 경우를 제외한 색칠의 수는 궤도의 수와 같고, 이는 G의 각 원소가 고정하는 점의 개수를 세어 계산할 수 있다.

* 항등원: 3⁶개의 모든 원소를 고정한다.
* 90도 면 회전 (6개): 회전축을 통과하는 두 면과 나머지 4개 면(측면)의 색상 조합을 고려하여 3³개의 원소를 고정한다.
* 180도 면 회전 (3개): 회전축을 통과하는 두 면과 측면의 2쌍의 면의 색상 조합을 고려하여 3⁴개의 원소를 고정한다.
* 120도 꼭짓점 회전 (8개): 회전축을 기준으로 위아래 색상 조합을 고려하여 3²개의 원소를 고정한다.
* 180도 모서리 회전 (6개): 회전축을 통과하는 모서리에 접하는 두 면과 나머지 4개 면(측면)의 색상 조합을 고려하여 3³개의 원소를 고정한다.

따라서 각 원소가 고정하는 집합의 크기의 평균은 다음과 같다.

:

\frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57

즉, 정육면체의 면을 3가지 색으로 칠하는 방법은 (회전하여 일치하는 경우를 제외하면) 57가지이다. 일반적으로, n가지 색상으로 정육면체의 면을 칠하는 경우의 수는 다음과 같다.

:

\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보다 작은지 확인하는 것이다. 각 동치류의 사전식으로 가장 작은 원소를 해당 류의 표준 형식으로 사용한다. 이러한 기법으로 생성된 객체의 개수를 세면 번사이드 보조정리가 올바르게 적용되었는지 확인할 수 있다.

이름	번사이드 보조정리
분야	군론
관련 항목	번사이드의 정리

내용

공식	만약 유한군 G가 집합 X에 작용하면, 궤도의 수는 다음과 같다. \|X/G\| = 1/\|G\| * Σ \|X^g\|, 여기서 X^g는 g에 의해 고정되는 X의 원소 집합이다.
설명	G가 X에 작용할 때, 각 g ∈ G에 대해 X^g는 g에 의해 고정되는 X의 원소들의 집합을 나타낸다. 번사이드 보조정리는 이러한 고정점들의 수를 이용하여 궤도의 총 개수를 계산하는 방법을 제공한다.

활용

응용	번사이드 보조정리는 조합론적 문제에서 대칭성을 고려하여 경우의 수를 계산하는 데 유용하게 사용된다. 예를 들어, 정다면체를 색칠하는 방법의 수를 계산하거나, 그래프의 동형인 형태의 수를 계산하는 데 활용될 수 있다.