Polycyclic and, especially, finitely generated nilpotent groups exhibit a rich structure allowing a special approach towards multiplication using polynomials. The so-called Deep Thought algorithm introduced in [LS98] computes these polynomials in practice for a suitable presentation of a finitely generated nilpotent group. Such a presentation is of the following form
\[ \langle a_1, \ldots, a_n \mid a_i^{s_i} = a_{i+1}^{c_{i, i, i+1}} \cdots a_n^{c_{i, i, n}}, 1 \leq i \leq n, a_j a_i = a_i a_j a_{j+1}^{c_{i, j, j+1}} \cdots a_n^{c_{i, j, n}}, 1 \leq i < j \leq n \rangle \]
with \(s_i \in \mathbb{N} \cup \{ \infty \}\) and \(c_{i, j, k} \in \mathbb{Z}\). If \(s_i = \infty\), then the power relation \(a_i^{s_i}\) is skipped.
Let \(G\) denote the group presented by the above presentation. Then every element in \(G\) can be written uniquely in a so-called normal form. That is, if \(G_i := \langle a_i, \ldots, a_n \rangle\) and \(r_i := | G_i : G_{i+1}|\), \(1 \leq i \leq n\), are the relative orders, then for certain \(e_i \in \mathbb{Z}\) each element can be written as
\[ a_1^{e_1} \cdots a_n^{e_n} \]
with \(0 \leq e_i < r_i\) if \(r_i < \infty\). A presentation is called confluent if and only if \(s_i = r_i\) for all \(1 \leq i \leq n\). If a presentation is not confluent, not all functions provided in this package are applicable, see function DTP_DTapplicability. For more theoretical background see for example the documentation of the GAP package Polycyclic.
The Deep Thought algorithm computes rational polynomials \(f_1, \ldots, f_n\) in \(2n\) indeterminates such that if \( x := a_1^{x_1} \cdots a_n^{x_n} \) and \(y := a_1^{y_1} \cdots a_n^{y_n} \) are two elements (in normal form or not with \(x_1, \ldots, x_n, y_1, \ldots, y_n \in \mathbb{Z}\)), then their product \(xy\) is given by
\[a_1^{f_1(x_1, \ldots, x_n, y_1, \ldots, y_n)} \cdots a_n^{f_n(x_1, \ldots, x_n, y_1, \ldots, y_n)}.\]
If the collector is confluent, also the normal form of the product can be computed. Otherwise this is not possible. Moreover, there exists a second version of the Deep Thought algorithms which computes \(n^2\) polynomials \(f_{rs}\), \(1 \leq r, s \leq n\), suitable for multiplications of the form
\[(a_1^{x_1} \cdots a_n^{x_n}) \cdot a_s^{y_s} = a_1^{f_{1s}(x_1, \ldots, x_n, y_s)} \cdots a_n^{f_{ns}(x_1, \ldots, x_n, y_s)} \]
for \(1 \leq s \leq n\). Each general multiplication can be expressed using these special multiplications. Depending on the presentation, polynomials of one version may be more efficient for computations than the polynomials of the other version. For a suggestion on which polynomials to use for a given presentation, see DTP_DTapplicability. In the following, Deep Thought type \(f_r\) refers to the Deep Thought algorithm which uses \(n\) polynomials and type \(f_{rs}\) refers to the Deep Thought algorithm using \(n^2\) polynomials.
In order to work with the Deep Thought functions, the group presentation is expected to be given as a collector coll, as defined in the GAP package Polycyclic. Moreover, the Polycyclic package introduces the structure of exponent vectors expvec, which will be used also in this package to represent group elements. In the following text, a group element \(a_1^{x_1} \cdots a_n^{x_n}\) is identified with its exponent vector in form of the list [x_1, ..., x_n]. For example, if expvec1, expvec2 are exponent vectors of elements in the same group, then expvec1 * expvec2 describes the multiplication of the corresponding group elements, and so on. Note that generally exponent vectors are not assumed to represent normal forms.
This package uses the category DTObj. A DTObj is a IsFromTheLeftCollectorRep with certain further list entries to store the Deep Thought polynomials of a collector together with some additional information. That is, the functions DTP_DTpols_r and DTP_DTpols_rs return a DTObj which has entries as IsFromTheLeftCollectorRep and additionally:
DTObj![PC_DTPPolynomials]: Deep Thought polynomials in form of (nested) lists
DTObj![PC_DTPOrders]: list containing orders of group generators if the collector is confluent
DTObj![PC_DTPConfluent]: boolean value indicating whether the collector is confluent or not
generated by GAPDoc2HTML