多环群#

介绍#

本模块介绍了为计算多环群（简称PcGroup）而设计的功能。相应的SymPy对象的名称是 PolycyclicGroup . 此处描述的函数或类将在下面进行研究 计算群论 .

功能概述#

  • 从给定置换群构造多圈群。

  • 多环生成序列（简称pcgs）和多环级数（pc_级数）的计算。

  • 相对数列的多环阶计算。

  • 类收集器的实现，它可以作为多柱体群的基。

  • 多循环群呈现的实现（简称pcu展示）。

  • 多环群中给定元素的指数向量、深度和前导指数的计算。

对于多环群的基本算法的描述，我们经常使用 计算群论手册 .

多环群的构造#

给定一个置换群，通过计算相应的多环生成序列、多环级数及其相对阶数，构造出多环群。

多循环群的属性#

  • pc_sequence 多环序列是通过收集给定置换群的导出序列中相邻群之间所有缺失的生成元而形成的。

  • pc_series ：多环级数是通过将 der[i+1] 在里面 der[i] 在哪里 der 表示派生系列。

  • relative_order ：一个列表，由pc峎系列中相邻组的比率计算得出。

  • collector ：默认为“无”。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是类多循环组的属性之一。

采集器属性#

Collector拥有polycycycroup的所有属性，另外还有几个属性定义如下：

  • 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}

最小未收集子词的计算#

一句话 V 定义在pcu群的free_群中的生成子词是该词的最小未收集子词 W 如果 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)

The two are not identical but they are equivalent:

>>> G1 == G2
False
>>> G1.equals(G2)
True

多环表示的计算#

表示的计算从pcgs和多环级数的底部开始。存储来自pcgs的所有前一个生成器，然后将最后一个生成器作为一个共轭器并将列表中所有以前的生成器共轭。

要获得清晰的图像，请从SymmetricGroup（4）的示例开始。对于S（4），pcgs中有4个发生器 \([x_0, x_1, x_2, x_3]\) 相对阶向量是 [2，3，2，2] . 从这个序列的底部开始，按如下顺序计算表示。

仅使用 \([x_3]\) 从 pcgs 和 pc_series[4] 计算：

  • \(x_3^2\)

仅使用 \([x_3]\) 从 pcgs 和 pc_series[3] 计算：

  • \(x_2^2\)

  • \(x_2^{-1}x_3x_2\)

使用 \([x_3, x_2]\) 从 pcgs 和 pc_series[2] 计算：

  • \(x_1^3\)

  • \(x_1^{-1}x_3x_1\)

  • \(x_1^{-1}x_2x_1\)

使用 \([x_3, x_2, x_1]\) 从 pcgs 和 pc_series[1] 计算：

  • \(x_0^2\)

  • \(x_0^{-1}x_3x_0\)

  • \(x_0^{-1}x_2x_0\)

  • \(x_0^{-1}x_1x_0\)

有一点需要注意的是，同一组可能会有不同的pcg，这是由于不同的衍生_系列，导致不同的多循环表现。

>>> 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

指数向量的计算#

多环群的任何一个生成元都可以用它的多环生成序列来表示。因此，指数向量的长度等于pcg的长度。

给定的发电机 g 可以表示为 \(g = x_1^{{e_1}} \ldots x_n^{{e_n}}\) 在哪里 \(x_i\) 表示多环发电机和 n free_组中的生成器数等于pcg的长度。

>>> 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

参考文献#

[Ho05]

Derek F. Holt, Handbook of Computational Group Theory. In the series 'Discrete Mathematics and its Applications', Chapman & Hall/CRC 2005, xvi + 514 p.