子群格基本算法

子群格与子群层级

定义 一个群的子群格是由其所有子群和子群间的包含关系构成的二元组

实际上就是子群所构成的偏序集

定义 子群格中的元素地层数 定义为子群阶数中素因子指数的和

于是我们自然地想到，可以按照层数以此构造出一个群的全体子群

循环扩张基础算法

是一个 层的子群的一个充分不必要条件是存在一个 层子群 和一个元素 使得

使用这种方法我们可以从由一层的子群构造出下一层的子群（注意到这个方法并不永远能构造出全部的子群，在一个群没有完全子群的情况下这是可以的）

接下来遇到的一个问题是，如何保证加入第 层的子群与之前的子群不重合呢？

事实上会发生重合的情况只有以下两种

  1. 是第 ​ 层子群中的元素
  2. 是已经加入第 层的子群中的元素

于是我们给出一个简单的算法

算法 1

1
2
3
4
5
6
7
8
9
10
11
12
13
for U_{i-1} in the layer[i-1]:
	Gamma := G - U_{i-1}
	for W in the layer[i]:
		if U_{i-1} is contained in W:
			Gamma -= W
	while Gamma is not empty:
		choose g from Gamma
		if gU_{i-1} = U_{i-1}g and g^p in U_{i-1} for some prime p:
			U := <U_{i-1}, g>
            add U to layer[i]
            Gamma -= U
        else:
        	Gamma -= {g}

然而我们注意到在上述代码当中有这么一步 的判断，什么时候上述判断为假呢？

于是我们自然而然地想到应该事先把 限定在 ​ 的正规化子当中：

算法 2

1
2
3
4
5
6
7
8
9
10
11
12
13
for U_{i-1} in the layer[i-1]:
	Gamma := Normalizer(U_{i-1}) - U_{i-1}
	for W in the layer[i]:
		if U_{i-1} is contained in W:
			Gamma -= W
	while Gamma is not empty:
		choose g from Gamma
		if g^p in U_{i-1} for some prime p:
			U := <U_{i-1}, g>
            add U to layer[i]
            Gamma -= U
        else:
        	Gamma -= {g}

并且我们暂时不加说明地给出计算正规化子的方法（跟前面的代码高度相似）

1
2
3
4
5
6
7
8
9
10
11
func findNormalizer():
	H := U
	Gamma := G - U
	while Gamma is not empty:
		choose g frome Gamma
		if gH = Hg:
			H = <H, g>
			Gamma -= H
		else:
			Gamma -= Hg
	return H

这样做可以显著提高排除不符合要求的 的效率

循环扩张算法优化

假设 其中 那么， 同样可以将 扩张到

为了证明这一点，只需注意到存在 ，于是

而

于是

这一点指出我们只需要考虑阶为素数的幂次的 即可

另一方面，显然在一个素数阶循环子群（事实上这样的群在早期群论研究中被称为 ）当中，只需取出一个非单位的代表元即可（自证不难）

我们称这个代表元集合为 这样我们得到

算法 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for U_{i-1} in the layer[i-1]:
	Gamma := Normalizer(U_{i-1}) - U_{i-1}
	Gamma := Intersection(Gamma, z_generator) 
	for W in the layer[i]:
		if U_{i-1} is contained in W:
			Gamma -= W
	while Gamma is not empty:
		choose g from Gamma
		if g^p in U_{i-1} for some prime p:
			U := <U_{i-1}, g>
            add U to layer[i]
            Gamma -= U
        else:
        	Gamma -= {g}

该方法显然存在的问题

在这个方法当中的每一个子群都对应这样一条正规子列

其中 然而显然这样的正规子列并不能覆盖整个子群格，在剩下的情况当中有

这种情况下 被称作完全子群，这个问题的解决方案便是检测所有的完全子群（根据数学定理，一个群的所有完全子群都被包含在一个最大的完全子群当中），相关的问题目前在这篇文章中暂且不提（挖坑）

能够被循环扩张方法得到子群格的群被称为 soluble 的（不知道怎么翻译，请指教）