느그 나비의 차례! *이 포스팅에서는 Lang1 ~ Lang5라는 이름의 보조정리를 차용한다. 익숙하지 않은 사람은 2편을 보고 오자.Butterfly Lemma (Zassenhaus) 그냥 봐서는 별로 쓸모가 없어 보이지만 비중이 큰 이 lemma. 그래도 쓸모가 있으니까 lemma겠지?이름이 butterfly lemma인 이유는 Hasse diagram이 나비처럼 생겨서. Wikipedia에서 보고 오자.이 Lemma는 (Group, Normal subgroup) pair 2개로 구성된 계에 대해서 적용할 수 있다. Lemma. (Zassenhaus) \(U' \unlhd U\), \(V' \unlhd V\)라고 하자. 이 때\(U'(U \cap V') \unlhd U'(U \cap V)\) && \..

2편에서 다룬 Lang1 ~ Lang5를 활용해서 Solvability와 관련된 이야기를 해보도록 하자.사실 Solvable group의 떡밥은 Galois Theory쯤 가야 풀리지만, 우리 랭형은 존나 강하시기 때문에 그런 건 신경쓰지 않으신다. 꼬우면 너가 Chapter IV를 보던가! 하신다. Tower of subgroups Group \(G\)에 대해서, \(G_{i} \ge G_{i+1}\)인 subgroup들의 나열을 Tower라고 한다. $$\{G_{i}\} := G = G_{0} \ge G_{1} \ge G_{2} \ge \cdots \ge G_{m} $$ 만약 모든 \(i\)에 대해서 \(G_{i+1} \unlhd G_{i}\)면 이 Tower를 Normal tower라고 한다.Nor..

A B C D E F CodeForces Gym일부러 집중력이 떨어진 상태에서 짧은 대회를 쳐봤다. 어떤 실수를 얼마나 하는지 보려고..템플릿도 안 켜고, 중간에 엎드려 잘 뻔하고... 결국 집중력 저하로 1시간만에 던졌다.DE는 풀 수 있을 것 같은데, PS를 크게 쉰 이후로 자료구조 구현에 굉장히 오랜 시간이 걸리고 있다. 보완이 필요하다. 풀이는 D E 푼 뒤에 올리는 걸로 하자.

계속해서 가자.Canonical Map Canonical Map \(\varphi : G \to G/H\)는 말 그대로 \(\varphi(x) = xH\)인 '압축' Map이다.이 자체가 중요하다기보단, 앞으로 Group Homomorphism을 쪼갤(factorize) 때 얘가 factor로 많이 등장한다. Lang1. 얘에 따로 이름이 있긴 한 것 같은데, 책 저자마다 번호가 다르단다. 난 그냥 Lang1이라고 부른다. Group homomorphism \(f : G \to G'\)이 있다. 이 때 \(H = \ker (f)\)라고 하자. 이 때 \(f\)를 (Canonical Map \(\varphi\)) + (유일하게 정의되는 injective map \(f_{*} : G/H \to G'\))로 ..

Lang에게 열심히 고통받고 있다.앞으로도 이해가 안 가는 내용을 부정기적으로 끄적거리려고 한다. Note. 여기서는 Lang만 쓰는 것 같은 Group - wise 곱셈 notation을 차용한다.즉, \(aG = \left\{ ag : g \in G\right\}, Ga = \left\{ ga : g \in G\right\}\)이고, \(GH = \left\{ gh : g \in G, h \in H \right\}\)이다.이것들을 굉장히 암시적으로, 또 빈번히 써먹을 예정이다. 따라서 계산 하나하나가 그다지 자명하지 않으니 잘 따라와주시길. Motivation: Kernel Group Normal subgroup의 아이디어는 Group homomorphism의 Kernel에서 시작한다. Group h..

Lagrange's theorem은 군 \(G\)의 부분군 \(H \le G\)에 대해, \(|H|\)가 \(|G|\)의 약수라는 정리이다.조금 더 일반적으로는 이렇게 쓸 수 있다.$$ (G : K) = (G : H)(H : K) $$ \(H \le G\)에 대해 \((G : H)\)는 \(H\)의 coset의 개수를 의미한다. \(H\)의 coset들이 \(G\)를 분할한다는 것은 쉽게 알 수 있다. Proof. \(H = \bigsqcup_{i} x_{i} K\), \(G = \bigsqcup_{j} y_{j} H\)라고 두자. \(\bigsqcup\)은 disjoint - union을 의미한다. 그렇다면 \(G = \bigcup_{i,j} y_{j}x_{i} K\)로 나타낼 수 있고, 모든 \(y_..