有限呈现群

介绍

本模块介绍了为有限表示群（简称fp-群）设计的计算功能。对应的SymPy对象名为 FpGroup。这里描述的函数或类在**计算群论**下进行研究。所有代码示例假设：

>>> from sympy.combinatorics.free_groups import free_group, vfree_group, xfree_group
>>> from sympy.combinatorics.fp_groups import FpGroup, CosetTable, coset_enumeration_r

设施概览

为浮点数组提供的功能可以自然地分为若干组

  • 使用自由群和该自由群生成元列表中的单词构建 fp-群。

  • 使用著名的 Todd-Coxeter 程序进行索引确定。

  • 使用 低指数子群 算法构建所有指数小于某个（较小）指定正整数的子群。

  • 计算由有限表示定义的群中有限指数子群表示的算法。

对于有限生成群的基本算法描述，我们经常参考 计算群论手册。

有限呈现群的构造

有限呈现群是通过将一个自由群通过一组关系子来构造的。关系子集合作为自由群生成元中的单词列表输入到SymPy中，使用列表为关系子提供了顺序。如果关系子列表为空，则返回相关的自由群。

有限表示群的构造示例。4次对称群可以表示为一个具有表示 \(\left\langle a, b \mid a^2, b^3, (ab)^4 \right\rangle\) 的双生成群。将关系作为关系符列表给出，SymPy中的群可以指定为：

>>> F, a, b = free_group("a, b")
>>> G = FpGroup(F, [a**2, b**3, (a*b)**4])
>>> G
<fp group on the generators (a, b)>

目前，具有类似 \(\left\langle r, s, t \mid r^2, s^2, t^2, rst = str = trs \right\rangle\) 表示的relators的组必须指定为：

>>> F, r, s, t = free_group("r, s, t")
>>> G = FpGroup(F, [r**2, s**2, t**2, r*s*t*r**-1*t**-1*s**-1, s*t*r*s**-1*r**-1*t**-1])

显然，这不是创建该特定组的唯一方法，但重点是，在非身份等同的情况下，用户必须手动完成这一操作。

自由群和词

自由群的构造

free_group("gen0, gen1, ..., gen_(n-1)") 构造了一个自由群 F，其由 n 个生成元生成，其中 n 是一个正整数。可以通过方法 .generators[i] 获取 F 的第 \(i\) 个生成元，\(i = 0, \ldots n-1\)。

>>> F, x, y = free_group("x, y")

创建一个秩为2的自由群 F ，并将变量 x 和 y 分配给两个生成元。

>>> F = vfree_group("x, y")
>>> F
<free group on the generators (x, y)>

创建一个秩为2的自由群 F ，其生成元元组为 F.generators ，并将 x 和 y 作为生成元插入到全局命名空间中。

>>> F = xfree_group("x, y")
>>> F
(<free group on the generators (x, y)>, (x, y))
>>> x**2
x**2

创建一个秩为2的自由群 F[0]，其生成元的元组为 F[1]。

词语的构造

本节适用于``FreeGroup``和``FpGroup``的单词。在SymPy中，当我们提到*单词*时，实际上指的是`约化单词 <https://en.wikipedia.org/wiki/Word_(group_theory)#Reduced_words>`_，因为单词会自动约化。给定一个在`n`个生成元`x_1, x_2, x_3, ldots, x_n`上定义的群``G``，一个单词构造为`s_1^{r_1}s_2^{r_2} cdots s_k^{r_k}`，其中`s_i in {x_1, x_2, ldots, x_n}`，\(r_i \in \mathbb{Z}\)，对于所有`k`。

每个单词可以通过多种方式构造，因为在简化之后它们可能是等价的。

陪集枚举：Todd-Coxeter算法

本节描述了在SymPy中使用陪集枚举技术的用法。用于陪集枚举过程的算法是Todd-Coxeter算法，并在SymPy中使用[Ho05]和[CDHW73]开发。读者应参考[CDHW73]和[Hav91]以获取该算法的总体描述。

我们有两种陪集枚举策略：基于关系 和 基于陪集表，这两种策略分别被实现为 coset_enumeration_r 和 coset_enumeration_c。这两种策略在为陪集生成新定义的方式上有所不同。

虽然从用户的角度来看，建议使用 FpGroup 的 .coset_enumeration 方法并指定 strategy 参数。

strategy:

(default=”relator_based”) 指定要使用的陪集枚举策略，可能的值是 “relator_based” 或 “coset_table_based”。

陪集表

用于操作关于有限呈现群 G 在子群 H 的陪集上的陪集枚举信息的类。

基本上，一个 陪集表 CosetTable(G,H) 是有限生成群在子群陪集上的置换表示。大多数集合论和群函数使用 G 的正则表示，即 G 在平凡子群上的陪集表。

实际的数学陪集表是通过 .table 属性获得的，它是一个列表的列表。对于 G 的每个生成元 g，它包含一列，下一列对应于 g**-1，依此类推其他生成元，因此总共有 2*G.rank() 列。每一列都是一个整数列表。如果 l 是生成元 g 的生成元列表，并且如果 l[i] = j，那么生成元 g 通过从右边乘法将陪集 i 带到陪集 j。

对于有限呈现的群，陪集表是通过Todd-Coxeter陪集枚举计算的。请注意，您可以通过更改变量 CosetTable.coset_table_max_limit 的值来影响该枚举的性能。

陪集表的属性

对于 CosetTable(G, H) ，其中 G 是群，H 是子群。

  • n: 一个非负整数，不可变属性，依赖于活陪集（即 \(\Omega\)）中的最大值计算得出。

  • table: 一个列表的列表，可变属性，在数学上表示陪集表。

  • omega: 一个列表，依赖于内部属性 p。\(\Omega\) 表示活陪集的列表。一个 标准 陪集表有其 \(\Omega = \{0, 1, \ldots, index-1 \}\)，其中 \(index\) 是子群 \(H\) 在 \(G\) 中的指数。

对于有经验的用户，我们提供了一些参数，可以用来操作算法，例如

  • coset_table_max_limit (默认值 = \(4096000\)): 控制陪集枚举中允许的最大陪集数量，即陪集表中允许的行数。如果子群没有有限指数，陪集枚举将不会完成，即使它有，也可能需要比子群的实际指数多得多的中间陪集。为了避免陪集枚举“失控”，SymPy 内置了一个“安全停止”机制。这由这个变量控制。要更改它，请使用 \(max_cosets\) 关键字。例如：

    >>> F, a, b = free_group("a, b")
>>> Cox = FpGroup(F, [a**6, b**6, (a*b)**2, (a**2*b**2)**2, (a**3*b**3)**5])
>>> C_r = coset_enumeration_r(Cox, [a], max_cosets=50)
Traceback (most recent call last):
  ...
ValueError: the coset enumeration has defined more than 50 cosets

  • max_stack_size (默认值 = \(500\))：操作 deduction_stack 的最大大小，当其大小等于或超过此值时，栈将被清空。

压缩与标准化

对于陪集表中的任意两个条目 \(i, j\) 且 \(i < j\)，\(i\) 在陪集表中的首次出现先于 \(j\) 的首次出现，相对于表条目的常规逐行排序。我们称这样的表为标准陪集表。要标准化一个 CosetTable，我们使用 .standardize 方法。

注意 该方法会修改给定的表格，它不会创建副本。

有限指数的子群

本节中的功能涉及有限指数子群的构造。我们描述了一种计算所有指数不超过某个（适度）整数界限的子群的方法。

低指数子群

low_index_subgroups(G, N): 给定一个有限表示的群 \(G = \left\langle X \mid R \right\rangle`（可以是自由群），以及一个正整数 ``N`\)，确定 G 中指数小于或等于 N 的子群的共轭类。

例如，要找到 \(G = \left\langle a, b \mid a^2 = b^3 = (ab)^4 = 1 \right\rangle\) 的所有指数 \(\le\) 4 的子群，可以按如下方式找到：

>>> from sympy.combinatorics.fp_groups import low_index_subgroups
>>> F, a, b = free_group("a, b")
>>> G = FpGroup(F, [a**2, b**3, (a*b)**4])
>>> l = low_index_subgroups(G, 4)
>>> for coset_table in l:
...     print(coset_table.table)
...
[[0, 0, 0, 0]]
[[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 3, 3]]
[[0, 0, 1, 2], [2, 2, 2, 0], [1, 1, 0, 1]]
[[1, 1, 0, 0], [0, 0, 1, 1]]

这将返回满足以下性质的子群的陪集表：子群在群中的指数 \(index\) 不超过 \(n\)。

为子组构建演示文稿

在本节中，我们讨论在一个有限表示群中找到子群的表示。虽然 子群 目前只允许以子群生成元列表的形式作为输入，但您可以预期在不久的将来， 陪集表 将作为子群在群中的输入功能。

有两种方法可以从 G 的定义关系中构造子群的定义关系。第一种是基于一组 Schreier 生成元，通常称为 Reidemeister-Schreier 算法，或者基于给定的 H 的生成元列表。

Reidemeister Schreier 算法

通过 reidemeister_presentation(G, Y) 调用，其中 G 是群，Y 是子群 H 的生成元列表，我们想要找到 H 的表示。

>>> from sympy.combinatorics.fp_groups import reidemeister_presentation
>>> F, x, y = free_group("x, y")
>>> f = FpGroup(F, [x**3, y**5, (x*y)**2])
>>> H = [x*y, x**-1*y**-1*x*y*x]
>>> p1 = reidemeister_presentation(f, H)
>>> p1
((y_1, y_2), (y_1**2, y_2**3, y_2*y_1*y_2*y_1*y_2*y_1))

参考文献

[CDHW73]

John J. Cannon, Lucien A. Dimino, George Havas, 和 Jane M. Watson. Todd-Coxeter 算法的实现与分析。Math. Comp., 27:463–490, 1973.

[Ho05]

Derek F. Holt, 计算群论手册。在系列 ‘离散数学及其应用’ 中，Chapman & Hall/CRC 2005, xvi + 514 p。

[Hav91]

George Havas, 陪集枚举策略。在符号和代数计算国际研讨会（ISSAC’91）的会议录中，波恩 1991，第191–199页。ACM出版社，1991年。