有限呈现群#

介绍#

This module presents the functionality designed for computing with finitely-presented groups (fp-groups for short). The name of the corresponding SymPy object is FpGroup. The functions or classes described here are studied under computational group theory. All code examples assume:

>>> 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程序确定指数。

  • 索引小于某个（小）指定正整数的所有子群的构造，使用 Low-Index Subgroups 算法。

  • 在由有限表示定义的群中计算有限索引子群表示的算法。

对于有限表示群的基本算法的描述，我们经常使用 计算群论手册 .

有限呈现群的构造#

有限呈现群是由一组关系元分解一个自由群来构造的。在SymPy的自由群生成元中，将关联词集合作为词的列表，利用列表对关系词进行排序。如果relators列表为空，则返回关联的空闲组。

有限呈现群的构造例子。度为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\) 必须指定为：

>>> 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 是一个正整数。这个 \(i\) -th发电机 \(F\) 可使用该方法获得 .generators[i] ， \(i = 0, \ldots n-1\) .

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

创建自由组 F 并分配变量 x 和 y 两台发电机。

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

创建自由组 F 列2，带发电机元组 F.generators ，和插入 x 和 y 作为全局命名空间的生成器。

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

创建自由组 F[0] 列2，带发电机元组 F[1] .

构词#

本节适用于 FreeGroup 以及 FpGroup . 当我们说 word 在SymPy中，它实际上意味着 reduced word ，因为单词会自动减少。给一组 G 定义于 \(n\) 生成器 \(x_1, x_2, x_3, \ldots, x_n\) ，一个单词被构造成 \(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算法#

This section describes the use of coset enumeration techniques in SymPy. The algorithm used for coset enumeration procedure is Todd-Coxeter algorithm and is developed in SymPy using [Ho05] and [CDHW73]. The reader should consult [CDHW73] and [Hav91] for a general description of the algorithm.

我们有两种陪集计数策略 relator-based 和 coset-table based 而这两个已经被实现为 coset_enumeration_r ， coset_enumeration_c 分别。这两种策略在新的定义上有所不同。

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

strategy ：

（default=“relator_-based”）指定要使用的陪集枚举策略，可能的值为 "relator_based" 或 "coset_table_based" .

CosetTable#

类用于操作有关有限呈现群的陪集枚举的信息 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的属性#

为了 CosetTable(G, H) 在哪里？ G 是组和 H 是子组。

  • n ：一个非负整数，不可变的属性，独立计算为活动陪集中的最大值（即。 \(\Omega\) ）

  • table ：列表列表列表，可变属性，数学上表示陪集表。

  • omega ：依赖于内部属性的列表 p . \(\Omega\) 表示live Coset的列表。A 标准 陪护表有它的 \(\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 方法。

Note 该方法更改给定的表，但不创建副本。

有限指数子群#

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

低指数子群#

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\) ，组中的子组为 \(\le n\) .

为子组构建演示文稿#

在本节中，我们将讨论在有限表示群中寻找子群的表示。而 子组 当前只允许作为子组生成器列表形式的输入，则可以预期 陪集表 在不久的将来，作为组中子组的输入。

有两种方法可以从 G . 首先是关于一组Schreier生成器，通常称为reidemeter-Schreier算法或给定列表上的生成器 H .

Reidemeter-Schreier算法#

调用使用 reidemeister_presentation(G, Y) 在哪里？ G 是组和 Y 是子组的生成器列表 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]

约翰·J·坎农、卢西恩·A·迪米诺、乔治·哈瓦斯和简·M·沃森。Todd-Coxeter算法的实现与分析。数学。《比较》，27:463–4901973年。

[Ho05]

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

[Hav91]

乔治·哈瓦斯，陪集枚举策略。《符号与代数计算国际研讨会论文集》（ISSAC'91），波恩，1991年，第191-199页。ACM出版社，1991年。