昆明电子商务网站建设,多语言外贸网站源码,网络专业公司排行榜,wordpress文章标题字体大小Burnside引理
书接上回#xff0c;继续深入研究在群作用下集合的轨道与稳定子群的相关性质
现在我们想要研究这样一个问题#xff1a; 有限群 G 在有限集合 S 上面有一个作用#xff0c;那么 S 的 G − 轨道条数是多少 有限群G在有限集合S上面有一个作用#xff0c;那么…Burnside引理
书接上回继续深入研究在群作用下集合的轨道与稳定子群的相关性质
现在我们想要研究这样一个问题 有限群 G 在有限集合 S 上面有一个作用那么 S 的 G − 轨道条数是多少 有限群G在有限集合S上面有一个作用那么S的G-轨道条数是多少 有限群G在有限集合S上面有一个作用那么S的G−轨道条数是多少 也就是在有限群 G G G作用下集合 S S S的等价类的数量
不妨设 S S S有 r r r条 G G G-轨道条数那么就有 S ⋃ i 1 r O r b ( x i ) S\bigcup_{i1}^{r}Orb(x_i) Si1⋃rOrb(xi) 其中 x i x_i xi就是每一条轨道的代表元。注意到任意两条轨道交集为空所以 ∣ S ∣ ⋃ i 1 r ∣ O r b ( x i ) ∣ ⋃ i 1 r ∣ G ∣ ∣ S t a b ( x i ) ∣ |S|\bigcup_{i1}^{r}|Orb(x_i)|\bigcup_{i1}^{r}\frac{|G|}{|Stab(x_i)|} ∣S∣i1⋃r∣Orb(xi)∣i1⋃r∣Stab(xi)∣∣G∣ 这里有点怪它似乎暗示我们同一个轨道的元素的不变子群的阶都是一样的。我们再仔细研究一下 ∀ x , y ∈ S \forall x,y\in S ∀x,y∈S,且 x x x, y y y在同一条轨道里面 ∃ a ∈ G , a ⋅ x y \exist a\in G,a\cdot xy ∃a∈G,a⋅xy。则 h ∈ S t a b ( y ) ⇔ h ⋅ y y ⇔ h ⋅ ( a ⋅ x ) a ⋅ x ⇔ ( h a ) ⋅ x a ⋅ x ⇔ a − 1 ⋅ ( ( h a ) ⋅ x ) ( a − 1 ⋅ ( a ⋅ x ) ) ⇔ ( a − 1 h a ) ⋅ x x ⇔ a − 1 h a ∈ S t a b ( x ) ⇔ h ∈ a − 1 S t a b ( x ) a h\in Stab(y)\Leftrightarrow h\cdot yy \\ \Leftrightarrow h\cdot(a\cdot x)a\cdot x \\ \Leftrightarrow (ha)\cdot xa\cdot x \\ \Leftrightarrow a^{-1}\cdot ((ha)\cdot x)(a^{-1}\cdot (a\cdot x)) \\ \Leftrightarrow (a^{-1}ha)\cdot xx \\ \Leftrightarrow a^{-1}ha\in Stab(x) \\ \Leftrightarrow h\in a^{-1}Stab(x)a h∈Stab(y)⇔h⋅yy⇔h⋅(a⋅x)a⋅x⇔(ha)⋅xa⋅x⇔a−1⋅((ha)⋅x)(a−1⋅(a⋅x))⇔(a−1ha)⋅xx⇔a−1ha∈Stab(x)⇔h∈a−1Stab(x)a
注意到上述过程都是等价的所以我们很快得到 S t a b ( y ) a − 1 S t a b ( x ) a Stab(y)a^{-1}Stab(x)a Stab(y)a−1Stab(x)a 于是我们得到如下命题 设有限群 G G G在有限集合 S S S上面有一个作用那么同一个 G G G-轨道的点的稳定子群彼此共轭从而它们彼此同构 同构的群之间显然阶数相等这也解答了我们刚刚的疑惑。
现在再来重新审视一个轨道 O r b ( x i ) Orb(x_i) Orb(xi),其内部所有元素的稳定子群的阶是相同的那么内部所有元素的稳定子群的阶数之和就会等于 ∑ ∣ S t a b ( x i ) ∣ ∣ S t a b ( x i ) ∣ ∣ O r b ( x i ∣ ∣ G ∣ \sum |Stab(x_i)||Stab(x_i)||Orb(x_i||G| ∑∣Stab(xi)∣∣Stab(xi)∣∣Orb(xi∣∣G∣ 那么集合内部所有元素的稳定子群的阶之和就会等于 ∑ x ∈ S ∣ S t a b ( x ) ∣ ∑ i 1 r ∣ G ∣ r ∣ G ∣ ( 1 ) \sum_{x\in S}|Stab(x)|\sum_{i1}^{r} |G|r|G|\quad\quad\quad\quad\quad\quad(1) x∈S∑∣Stab(x)∣i1∑r∣G∣r∣G∣(1) 这启发我们用另一种方法来计算 r r r.只要能够得到 ∑ x ∈ S ∣ S t a b ( x ) ∣ \sum_{x\in S}|Stab(x)| ∑x∈S∣Stab(x)∣,再除以 ∣ G ∣ |G| ∣G∣就能得到 r r r 我们考虑 G ∗ S G* S G∗S的一个子集 K { ( a , x ) ∣ a ⋅ x x } K\{(a,x)|a\cdot xx\} K{(a,x)∣a⋅xx},
对于一个给定的 x ∈ S x\in S x∈S,以 x x x作为第二个值的有序对 ( a , x ) (a,x) (a,x)的数量显然就是 ∣ S t a b ( x ) ∣ |Stab(x)| ∣Stab(x)∣,所以 ∣ K ∣ ∑ x ∈ S ∣ S t a b ( x ) ∣ |K|\sum_{x\in S}|Stab(x)| ∣K∣x∈S∑∣Stab(x)∣ 问题又转化成了求 ∣ K ∣ |K| ∣K∣,不过我们离成功已经很近了。
事实上将问题转化成求 ∣ K ∣ |K| ∣K∣是很有好处的因为我们可以以 x x x为关键字来看待它当然也可以以 a a a为关键字来看。如此对于一个给定的 a ∈ G a\in G a∈G,所有以 a a a为第一个值的有序对对应的x组成一个集合 F a { x ∣ a ⋅ x x } F_a\{x|a\cdot xx\} Fa{x∣a⋅xx},我们记其为 a a a的不动点集
那么 ∑ x ∈ S ∣ S t a b ( x ) ∣ ∣ K ∣ ∑ a ∈ G ∣ F a ∣ \sum_{x\in S}|Stab(x)||K|\sum_{a\in G}|F_a| x∈S∑∣Stab(x)∣∣K∣a∈G∑∣Fa∣ 从而由 ( 1 ) (1) (1)式可知 r ∑ x ∈ S ∣ S t a b ( x ) ∣ ∣ G ∣ 1 ∣ G ∣ ∑ a ∈ G ∣ F a ∣ r\frac{\sum_{x\in S}|Stab(x)|}{|G|}\frac{1}{|G|}\sum_{a\in G}|F_a| r∣G∣∑x∈S∣Stab(x)∣∣G∣1a∈G∑∣Fa∣ 于是我们得到 B u r n s i d e Burnside Burnside引理如下 设有限群 G G G在有限集合 S S S上有一个群作用那么 S S S的 G G G-轨道条数 r r r为 r 1 ∣ G ∣ ∑ a ∈ G ∣ F a ∣ r\frac{1}{|G|}\sum_{a\in G}|F_a| r∣G∣1a∈G∑∣Fa∣ 这个引理的意义在于原本单纯只跟集合 S S S有关的问题我们可以借用群 G G G来解决了而群 G G G在一些特定情况下有良好的性质能够帮助我们快速计算 ∑ a ∈ G ∣ F a ∣ \sum_{a\in G}|F_a| ∑a∈G∣Fa∣
应用
来个具体的例子 给定一个大小为n的环环上每一个点有m种染色方案。问总共可以染出多少个本质不同的环。这里环本质不同定义为无法通过旋转得到 不妨记环上点的集合为 B { b 1 , b 2 , . . . b n } B\{b_1,b_2,...b_n\} B{b1,b2,...bn},染色方案集合为 C { c 1 , c 2 , . . . c m } C\{c_1,c_2,...c_m\} C{c1,c2,...cm},考虑集合 S B C { X i } , 其中 X i c i 1 , c i 2 , . . . c i n , 1 ≤ i j ≤ m SB^C\{X_i\},其中X_ic_{i_1},c_{i_2},...c_{i_n},1\leq i_j\leq m SBC{Xi},其中Xici1,ci2,...cin,1≤ij≤m S S S的实际含义就是所有给 B B B中元素染色的方案的集合,每一个方案用一个n元排列表示,显然 ∣ S ∣ m n |S|m^n ∣S∣mn
现在考虑在集合 B B B上的置换群 P e r m ( B ) Perm(B) Perm(B)的子群 G { ( 1 2 . . . n − 1 n 2 3 . . . n 1 ) , ( 1 2 3 . . . n − 1 n 3 4 . . . n 1 2 ) , . . . , ( 1 ) } G\{\bigl(\begin{smallmatrix} 1 2 ... n-1 n\\ 2 3 ... n 1 \end{smallmatrix}\bigr),\bigl(\begin{smallmatrix} 1 2 3 ... n-1 n\\ 3 4 ... n 1 2 \end{smallmatrix}\bigr),...,(1)\} G{(1223......n−1nn1),(13243......nn−11n2),...,(1)},其中 G i ( 1 2 3 4 . . . n − 1 n i 1 i 2 . . . n 1 . . . i ) G_i\bigl(\begin{smallmatrix} 12 34... n-1 n\\ i1 i2 ... n 1 ...i \end{smallmatrix}\bigr) Gi(1i12i23...4n...1n−1...ni)。显然 ∣ G ∣ n |G|n ∣G∣n。此外不难证明 G G G确实是一个群这里就不证了。
至于为什么要这样定义是因为 G G G中元素实际上代表的就是一个环的旋转这一点不难发现与题目给出的本质不同的定义相吻合。整个 G G G就恰好代表了环上的所有旋转操作如果我们能证明有限群 G G G在集合 S S S上有一个作用,那么本质不同的环的数量不就是 S S S的 G G G-轨道条数了吗从而可以用 B u r n s i d e Burnside Burnside引理求解
我们来证明有限群 G G G确实在集合 S S S上有一个作用
证明
考虑 ϕ : G ∗ S → S ( a , x ) ↦ a ⋅ x \phi:G*S\rightarrow S \\ (a,x)\mapsto a\cdot x ϕ:G∗S→S(a,x)↦a⋅x 这里 a a a是一个置换 x x x是一个大小为 n n n的排列那么此时 a ⋅ x a\cdot x a⋅x就是一个普通的 置换在排列上的作用了这样定义显然是合理的。
要证明 G G G在 S S S上有群作用我们只需要证明 e ⋅ x x , ∀ x ∈ S ( a ∘ b ) ⋅ x a ⋅ ( b ⋅ x ) e\cdot xx,\forall x\in S \\ (a\circ b)\cdot xa\cdot (b\cdot x) e⋅xx,∀x∈S(a∘b)⋅xa⋅(b⋅x) 第一点非常显然 G G G中的 e e e就是恒等变换它作用在一个排列上显然保持不变
第二点其实就是置换的复合性质的描述我们当然知道它是成立的
从而 G G G确实在 S S S上有一个群作用那么我们就可以用 B u r n s i d e Burnside Burnside引理来处理这个问题了。 □ \square □
我们要求本质不同的环的数量也就是求 S S S的 G G G-轨道条数 r r r,从而 r 1 ∣ G ∣ ∑ a ∈ G ∣ F a ∣ 1 n ∑ a ∈ G ∣ F a ∣ r\frac{1}{|G|}\sum_{a\in G}|F_a|\frac{1}{n}\sum_{a\in G}|F_a| r∣G∣1a∈G∑∣Fa∣n1a∈G∑∣Fa∣ 此时问题变成对于 G G G内的每一个置换求其不动点集的阶 不妨来看个简单版本我们就令 n 4 n4 n4。此时总共有4个置换 a 1 ( 1 2 3 4 2 3 4 1 ) a_1\bigl(\begin{smallmatrix} 1 2 3 4 \\ 2 3 4 1 \end{smallmatrix}\bigr) a1(12233441),此时显然需要 x i x_i xi内所有 c i j c_{i_j} cij都相等从而 ∣ F a 1 ∣ m |F_{a_1}|m ∣Fa1∣m a 2 ( 1 2 3 4 3 4 1 2 ) a_2\bigl(\begin{smallmatrix} 1 2 3 4 \\ 3 4 1 2 \end{smallmatrix}\bigr) a2(13243142), 1 , 3 1,3 1,3是一组 2 , 4 2,4 2,4是一组所以 ∣ F a 2 ∣ m 2 |F_{a_2}|m^2 ∣Fa2∣m2同理可得 ∣ F a 3 ∣ m |F_{a_3}|m ∣Fa3∣m a 4 ( 1 ) a_4(1) a4(1),每一个排列在 a 4 a_4 a4作用下都保持不变元素对应的颜色自然也不变从而 ∣ F a 4 ∣ ∣ S ∣ m n |F_{a_4}||S|m^n ∣Fa4∣∣S∣mn
从而 r 1 n ( m n 2 m m 2 ) r\frac{1}{n}(m^n2mm^2) rn1(mn2mm2) 但是当 n n n逐渐变大的时候,这种暴力枚举的方法将会变的寸步难行。这里再引入一个概念
置换群的轮换指标
置换型如果 n n n元置换 g g g中有 b i b_i bi个长度为 i i i的轮换那么 g g g的置换型为 x 1 b 1 x 2 b 2 . . . x n b n {x_1}^{b_1}{x_2}^{b_2}...{x_n}^{b_n} x1b1x2b2...xnbn其中 ∑ i ∗ b i n \sum i*b_in ∑i∗bin显然成立。这里 x i x_i xi只是一个形式 设 ( G , ∘ ) (G,\circ) (G,∘)是一个 n n n元置换群那么它的轮换指标定义为 P G ( x 1 , x 2 , . . . x n ) 1 ∣ G ∣ ∑ g ∈ G x 1 b 1 x 2 b 2 . . . x n b n P_G(x_1,x_2,...x_n)\frac{1}{|G|}\sum_{g\in G}x_1^{b_1}x_2^{b_2}...x_{n}^{b_n} PG(x1,x2,...xn)∣G∣1g∈G∑x1b1x2b2...xnbn x i b i {x_i}^{b_i} xibi就表示在一个置换 g g g内有 b i b_i bi个 i i i-轮换而对于一个轮换其内所有点都是可以互相到达的所以轮换内部的点的颜色一定得相同从而这个轮换的染色方案就是 m m m,从而,对于置换 g g g, ∣ F g ∣ m b 1 m b 2 . . . m b n |F_g|m^{b_1}m^{b_2}...m^{b_n} ∣Fg∣mb1mb2...mbn
从而 r 1 ∣ G ∣ ∑ a ∈ G ∣ F a ∣ 1 ∣ G ∣ ∑ a ∈ G x 1 b 1 x 2 b 2 . . . x n b n P G ( x 1 , x 2 , . . . x n ) r\frac{1}{|G|}\sum_{a\in G}|F_a|\frac{1}{|G|}\sum_{a\in G}x_1^{b_1}x_2^{b_2}...x_{n}^{b_n}P_G(x_1,x_2,...x_n) r∣G∣1a∈G∑∣Fa∣∣G∣1a∈G∑x1b1x2b2...xnbnPG(x1,x2,...xn) 现在问题就变成了求置换群 G G G的轮换指标
这里给出一些结论
正n边形的旋转群的轮换指标 P G 1 n ∑ d ∣ n ϕ d x d n d P_G\frac{1}{n}\sum_{d|n}\phi_d{x_d}^{\frac{n}{d}} PGn1d∣n∑ϕdxddn
这其实就是我们刚刚在研究的问题
注意到正n边形的旋转群 G G G中 G i G_i Gi就表示旋转步长为 i i i的置换组成我们有如下结论 ∣ F G i ∣ ( n , i ) |F_{G_i}|(n,i) ∣FGi∣(n,i) 证明 i ∣ n i|n i∣n,每次走i步 n / i n/i n/i次后回到原点所以该置换可以拆成i个轮换每一个轮换的阶为 n / i n/i n/i。显然有 ∣ F G i ∣ i ( n , i ) |F_{G_i}|i(n,i) ∣FGi∣i(n,i) i ∤ n i\nmid n i∤n,每次走 i i i步回到原点需要 l c m ( n , i ) lcm(n,i) lcm(n,i)次从而每一个轮换的阶为 l c m ( n , i ) / i lcm(n,i)/i lcm(n,i)/i,那么 ∣ F G i ∣ n / ( l c m ( n , i ) / i ) n i / l c m ( n , i ) ( n , i ) |F_{G_i}|n/(lcm(n,i)/i)ni/lcm(n,i)(n,i) ∣FGi∣n/(lcm(n,i)/i)ni/lcm(n,i)(n,i) □ \square □
未完待续肝不动了下周回来补…
