多环群¶
介绍¶
本模块介绍了为计算多循环群（简称PcGroup）而设计的功能。对应的SymPy对象名为 PolycyclicGroup。此处描述的函数或类在 计算群论 下进行研究。
功能概述¶
从给定的置换群构建多环群。
计算多环生成序列（简称 pcgs）和多环级数（pc_series）。
多环系列的相对顺序计算。
实现了一个可以作为多环群基类的 Collector 类。
多环群表示的实现（简称 pc_presentation）。
计算给定幂零群元素的指数向量、深度和前导指数。
对于多环群基本算法的描述，我们通常使用 计算群论手册。
多环群的构建¶
给定一个置换群，通过计算相应的多循环生成序列、多循环系列及其相对阶数，构建一个多循环群。
多环群的属性¶
pc_sequence: 多环序列是通过收集给定置换群的导出系列中相邻群之间所有缺失的生成元形成的。pc_series: 多环系列是通过在der[i]中添加der[i+1]的所有缺失生成元形成的，其中der表示导出系列。relative_order: 一个列表，由 pc_series 中相邻组的比率计算得出。collector: 默认情况下，它为 None。Collector 类提供了多环表示。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> len(PcGroup.pcgs)
4
>>> pc_series = PcGroup.pc_series
>>> pc_series[0].equals(G) # use equals, not literal `==`
True
>>> gen = pc_series[len(pc_series) - 1].generators[0]
>>> gen.is_identity
True
>>> PcGroup.relative_order
[2, 3, 2, 2]
收集器的构建¶
Collector 是类 PolycyclicGroup 的属性之一。
Collector 的属性¶
Collector 拥有 PolycyclicGroup 的所有属性，此外还有一些额外的属性，定义如下：
free_group: free_group 提供了多环生成序列与自由群元素之间的映射。pc_presentation: 提供了在幂和对合关系帮助下对多环群的表示。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> G = SymmetricGroup(3)
>>> PcGroup = G.polycyclic_group()
>>> Collector = PcGroup.collector
>>> Collector.free_group
<free group on the generators (x0, x1)>
>>> Collector.pc_presentation
{x0**2: (), x1**3: (), x0**-1*x1*x0: x1**2}
计算最小未收集子词¶
在 pc_group 的 free_group 中，如果 V 是 W 的子词，并且 V 具有以下形式之一，则 V 是词 W 的最小未收集子词：
\(v = {x_{i+1}}^{a_j}x_i\)
\(v = {x_{i+1}}^{a_j}{x_i}^{-1}\)
\(v = {x_i}^{a_j}\)
\(a_j \notin \{0, \ldots \mathrm{relative\_order}[j]-1\}\).
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.free_groups import free_group
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> F, x1, x2 = free_group("x1, x2")
>>> word = x2**2*x1**7
>>> collector.minimal_uncollected_subword(word)
((x2, 2),)
子词索引的计算¶
对于给定的单词及其子词，subword_index 计算子词在单词中的起始和结束索引。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.free_groups import free_group
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> F, x1, x2 = free_group("x1, x2")
>>> word = x2**2*x1**7
>>> w = x2**2*x1
>>> collector.subword_index(word, w)
(0, 3)
>>> w = x1**7
>>> collector.subword_index(word, w)
(2, 9)
收集词的计算¶
一个词 W 被称为收集的，如果 W \(= {x_{i_1}}^{a_1} \ldots {x_{i_r}}^{a_r}\) 其中 \(i_1 < i_2< \ldots < i_r\) 且 \(a_j\) 在 \(\{1 \ldots s_{j-1}\}\) 中，其中 \(s_j\) 表示相应的相对顺序。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.free_groups import free_group
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> F, x0, x1, x2, x3 = free_group("x0, x1, x2, x3")
>>> word = x3*x2*x1*x0
>>> collected_word = collector.collected_word(word)
>>> free_to_perm = {}
>>> free_group = collector.free_group
>>> for sym, gen in zip(free_group.symbols, collector.pcgs):
... free_to_perm[sym] = gen
>>> G1 = PermutationGroup()
>>> for w in word:
... sym = w[0]
... perm = free_to_perm[sym]
... G1 = PermutationGroup([perm] + G1.generators)
>>> G2 = PermutationGroup()
>>> for w in collected_word:
... sym = w[0]
... perm = free_to_perm[sym]
... G2 = PermutationGroup([perm] + G2.generators)
两者并不完全相同，但它们是等价的：
>>> G1 == G2
False
>>> G1.equals(G2)
True
多环表示的计算¶
演示的计算从pcgs和多循环系列的底部开始。存储pcgs中的所有先前生成元，然后取最后一个生成元作为共轭器，共轭列表中的所有先前生成元。
为了清晰地了解，首先从一个 SymmetricGroup(4) 的例子开始。对于 S(4)，有 4 个生成元在 pcgs 中，例如 \([x_0, x_1, x_2, x_3]\)，相对阶向量是 [2, 3, 2, 2]。从这个序列的底部开始，演示文稿按以下顺序计算。
仅使用 pcgs 中的 \([x_3]\) 和 pc_series[4] 计算：
\(x_3^2\)
仅使用 pcgs 中的 \([x_3]\) 和 pc_series[3] 计算：
\(x_2^2\)
\(x_2^{-1}x_3x_2\)
使用 pcgs 中的 \([x_3, x_2]\) 和 pc_series[2] 计算：
\(x_1^3\)
\(x_1^{-1}x_3x_1\)
\(x_1^{-1}x_2x_1\)
使用 pcgs 中的 \([x_3, x_2, x_1]\) 和 pc_series[1] 计算：
\(x_0^2\)
\(x_0^{-1}x_3x_0\)
\(x_0^{-1}x_2x_0\)
\(x_0^{-1}x_1x_0\)
需要注意的是，同一组可能由于不同的 derived_series 而具有不同的 pcgs，这导致不同的多循环表示。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.permutations import Permutation
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> pcgs = PcGroup.pcgs
>>> len(pcgs)
4
>>> free_group = collector.free_group
>>> pc_resentation = collector.pc_presentation
>>> free_to_perm = {}
>>> for s, g in zip(free_group.symbols, pcgs):
... free_to_perm[s] = g
>>> for k, v in pc_resentation.items():
... k_array = k.array_form
... if v != ():
... v_array = v.array_form
... lhs = Permutation()
... for gen in k_array:
... s = gen[0]
... e = gen[1]
... lhs = lhs*free_to_perm[s]**e
... if v == ():
... assert lhs.is_identity
... continue
... rhs = Permutation()
... for gen in v_array:
... s = gen[0]
... e = gen[1]
... rhs = rhs*free_to_perm[s]**e
... assert lhs == rhs
指数向量的计算¶
多环群的任何生成元都可以通过其多环生成序列来表示。因此，指数向量的长度等于pcgs的长度。
给定的多循环群生成元 g 可以表示为 \(g = x_1^{e_1} \ldots x_n^{e_n}\)，其中 \(x_i\) 表示多循环生成元，n 是自由群中生成元的数量，等于pcgs的长度。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.permutations import Permutation
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> pcgs = PcGroup.pcgs
>>> collector.exponent_vector(G[0])
[1, 0, 0, 0]
>>> exp = collector.exponent_vector(G[1])
>>> g = Permutation()
>>> for i in range(len(exp)):
... g = g*pcgs[i]**exp[i] if exp[i] else g
>>> assert g == G[1]
多环生成器的深度¶
给定多环生成器的深度定义为指数向量中第一个非零条目的索引。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> G = SymmetricGroup(3)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> collector.depth(G[0])
2
>>> collector.depth(G[1])
1
前导指数的计算¶
前导指数表示在上述深度处的多环生成器的指数。
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> G = SymmetricGroup(3)
>>> PcGroup = G.polycyclic_group()
>>> collector = PcGroup.collector
>>> collector.leading_exponent(G[1])
1
参考文献¶
Derek F. Holt, 计算群论手册。在系列 ‘离散数学及其应用’ 中，Chapman & Hall/CRC 2005, xvi + 514 p。