Polycyclic Groups and Polycyclic Presentations

Introduction

A polycyclic group is a group \(G\) with a subnormal series \(G = G_1 \triangleright G_2 \triangleright\ldots\triangleright G_{n+1} = 1\) in which each of the quotients \(G_i/G_{i+1}\) is cyclic. Every polycyclic group \(G\) has a presentation of the form

\[\begin{split}\begin{aligned}< a_1, \ldots,a_n\ |\ &a_i ^{m_i}= w_{i,i} \quad (i\in I) ,\\ &a_j ^{a_i}= w_{i,j}\quad (1 \leq i < j\leq n),\\ &a_j ^{a_i^{-1}}= w_{-i,j}\quad (1 \leq i < j\leq n, i\notin I) >\end{aligned}\end{split}\]

where

(i)

\(I\subseteq \{1,\ldots, n\}\),

(ii)

\(m_i > 1\) for \(i\in I\), and

(iii)

the words \(w_{i,j}\) are of the form \(w_{i,j} = a_{|i|+1}^{l(i,j,|i|+1)}\ldots a_n^{l(i,j,n)}\), with \(0\leq l(i,j,k) < m_k\) if \(k\in I\).

Such a presentation is called a polycyclic presentation for \(G\). For \(1\leq i\leq n\), let \(G_i\) be the subgroup of \(G\) generated by \(a_i,\ldots,a_n\) and define \(G_{n+1}\) to be the trivial group. The presentation is called consistent, if \(|G_i/G_{i+1}|=m_i\) whenever \(i\in I\) and \(G_i/G_{i+1}\) is infinite whenever \(i\notin I\). The generators \(a_1,\ldots a_n\) are referred to as polycyclic generators (pc-generators) for \(G\) and the values \(m_i\) (\(i\in I\)) are called the corresponding pc-exponents.

In Magma, the user can define a polycyclic group by providing a consistent polycyclic presentation or by using one of the existing category transfer functions.

Given a consistent polycyclic presentation for \(G\), every element \(a\) of \(G\) can be written uniquely in the form \(a=a_1^{e_1}\ldots a_n^{e_n}\), where the \(e_i\) are integers satisfying \(0 \leq e_i < m_i\) if \(i\in I\). This form is called normal form. There exists an algorithm (the collection algorithm), which given an arbitrary word in the generators \(a_1, \ldots, a_n\), will determine the corresponding normal word. Magma uses a collection algorithm written by Volker Gebhardt. The cost of collection for this algorithm grows logarithmically in a bound on the absolute values of the exponents \(e_i\) occurring during the collection [Gebhardt, 2002].

Infinite polycyclic groups are a comparatively new topic in computational group theory and the number of available algorithms is much smaller than in the case of finite polycyclic groups. For this reason, the data type GrpPC (cf. Chapter Finite Soluble Groups) should be preferred for finite polycyclic groups.

Specification of Elements

Elements of polycyclic groups are words. A word is defined inductively as follows:

(i)

A generator is a word;

(ii)

The expression \((u)\) is a word, where \(u\) is a word;

(iii)

The product \(u*v\) of the words \(u\) and \(v\) is a word;

(iv)

The conjugate \(u^v\) of the word \(u\) by the word \(v\) is a word (\(u^v\) expands into the word \(v^{-1}*u*v\));

(v)

The power of a word \(u^n\), where \(u\) is a word and \(n\) is an integer, is a word;

(vi)

The commutator \((u, v)\) of the words \(u\) and \(v\) is a word ( \((u, v)\) expands into the word \(u^{-1}*v^{-1}*u*v\)).

G ! Q: GrpGPC, [RngIntElt] -> GrpGPCElt

Given the polycyclic group \(G\) and a sequence \(Q\) of length \(n\), containing integers \(e_1\ldots e_n\), where \(0\leq {e_i} < m_{i}\) if \(i\in I\), construct the element \(x\) of \(G\) given by

\[x = a_1^{e_1}\ldots a_n^{e_n}.\]

Identity(G): GrpGPC -> GrpGPCElt

Id(G): GrpGPC -> GrpGPCElt

G ! 1: GrpGPC, RngIntElt -> GrpGPCElt

Construct the identity element of the polycyclic group \(G\).

Access Functions for Elements

Throughout this subsection, \(G\) will be a polycyclic group with pc-generators \(a_1, \dots, a_n\).

ElementToSequence(x): GrpGPCElt -> [RngIntElt]

Eltseq(x): GrpGPCElt -> [RngIntElt]

Given an element \(x\) belonging to the polycyclic group \(G\), where \(x = a_1^{e_1}\ldots a_n^{e_n}\) in normal form, return the sequence \(Q\) of \(n\) integers defined by \(Q[i] = {e_i}\), for \(i = 1,\ldots,n\).

LeadingTerm(x): GrpGPCElt -> GrpGPCElt

Given an element \(x\) of a polycyclic group \(G\) with \(n\) pc-generators, where \(x\) is of the form \(a_1^{e_1}\ldots a_n^{e_n}\), return \(a_i^{e_i}\) for the smallest \(i\) such that \(e_i > 0\). If \(x\) is the identity of \(G\), then the identity is returned.

LeadingGenerator(x): GrpGPCElt -> GrpGPCElt

Given an element \(x\) of a polycyclic group \(G\) with \(n\) pc-generators, where \(x\) is of the form \(a_1^{e_1}\ldots a_n^{e_n}\), return \(a_i\) for the smallest \(i\) such that \(e_i > 0\). If \(x\) is the identity of \(G\), then the identity is returned.

LeadingExponent(x): GrpGPCElt -> RngIntElt

Given an element \(x\) of a polycyclic group \(G\) with \(n\) pc-generators, where \(x\) is of the form \(a_1^{e_1}\ldots a_n^{e_n}\), return \(e_i\) for the smallest \(i\) such that \(e_i > 0\). If \(x\) is the identity of \(G\), then \(0\) is returned.

Depth(x): GrpGPCElt -> RngIntElt

Given an element \(x\) of a polycyclic group \(G\) with \(n\) pc-generators, where \(x\) is of the form \(a_1^{e_1}\ldots a_n^{e_n}\), return the smallest \(i\) such that \(e_i > 0\). If \(x\) is the identity of \(G\), then \(n+1\) is returned.

Depth returns the maximal value of \(i\), such that \(x\in G_i\).

Arithmetic Operations on Elements

Throughout this subsection, \(G\) will be a polycyclic group with pc-generators \(a_1, \dots, a_n\).

g * h: GrpGPCElt, GrpGPCElt -> GrpGPCElt

Product of the element \(g\) and the element \(h\), where \(g\) and \(h\) belong to some common subgroup \(G\) of a polycyclic group \(U\). If \(g\) and \(h\) are given as elements belonging to the same proper subgroup \(G\) of \(U\), then the result will be returned as an element of \(G\); if \(g\) and \(h\) are given as elements belonging to distinct subgroups \(H\) and \(K\) of \(U\), then the product is returned as an element of \(G\), where \(G\) is the smallest subgroup of \(U\) known to contain both elements.

g *:= h: GrpGPCElt, GrpGPCElt

Replace \(g\) with the product of element \(g\) and element \(h\).

g ^ n: GrpGPCElt, RngIntElt -> GrpGPCElt

The \(n\)-th power of the element \(g\), where \(n\) is a positive or negative integer.

g ^:= n: GrpGPCElt, RngIntElt

Replace \(g\) with the \(n\)-th power of the element \(g\).

g / h: GrpGPCElt, GrpGPCElt -> GrpGPCElt

Quotient of the element \(g\) by the element \(h\), i.e. the element \(g*h^{-1}\). Here \(g\) and \(h\) must belong to some common subgroup \(G\) of a polycyclic group \(U\). The rules for determining the parent group of \(g/h\) are the same as for \(g*h\).

g /:= h: GrpGPCElt, GrpGPCElt

Replace \(g\) with \(g*h^{-1}\).

g ^ h: GrpGPCElt, GrpGPCElt -> GrpGPCElt

Conjugate of the element \(g\) by the element \(h\), i.e. the element \(h^{-1}*g*h\). Here \(g\) and \(h\) must belong to some common subgroup \(G\) of a polycyclic group \(U\). The rules for determining the parent group of \(g^h\) are the same as for \(g*h\).

g ^:= h: GrpGPCElt, GrpGPCElt

Replace \(g\) with the conjugate of the element \(g\) by the element \(h\).

(g₁, ..., gₙ): List(GrpGPCElt) -> GrpGPCElt

Given the \(n\) words \(g_1, \ldots, g_n\) belonging to some common subgroup \(G\) of a polycyclic group \(U\), compute the left-normed commutator of \(g_1,\ldots,g_n\). This is defined inductively as follows: \((g_1,g_2) = g_1^{-1}*g_2^{-1}*g_1*g_2\) and \((g_1,\ldots,g_n) = ((g_1,\ldots,g_{n-1}),g_n)\).

If \(g_1, \ldots, g_n\) are given as elements belonging to the same proper subgroup \(G\) of \(U\), then the result will be returned as an element of \(G\); if \(g_1, \ldots, g_n\) are given as elements belonging to distinct subgroups of \(U\), then the product is returned as an element of \(G\), where \(G\) is the smallest subgroup of \(U\) known to contain all elements.

Operators for Elements

Order(x): GrpGPCElt -> RngIntElt

The order of the element \(x\).

IsFinite(x): GrpGPCElt -> BoolElt

Returns true if the order of the element \(x\) is finite, false otherwise.

Parent(x): GrpGPCElt -> GrpGPC

The parent group \(G\) of the element \(x\).

Comparison Operators for Elements

g eq h: GrpGPCElt, GrpGPCElt -> BoolElt

Given elements \(g\) and \(h\) belonging to a common polycyclic group, return true if \(g\) and \(h\) are the same element, false otherwise.

g ne h: GrpGPCElt, GrpGPCElt -> BoolElt

Given elements \(g\) and \(h\) belonging to a common polycyclic group, return true if \(g\) and \(h\) are distinct elements, false otherwise.

IsIdentity(g): GrpGPCElt -> BoolElt

IsId(g): GrpGPCElt -> BoolElt

Returns true if \(g\) is the identity element, false otherwise.

Specification of a Polycyclic Presentation

quo< GrpGPC : F | R : parameters >: GrpFP, List(GrpFPRel) -> GrpGPC, Map

Check: BoolElt                    Default: true

Given a free group \(F\) of rank \(n\) with generating set \(X\), and a collection \(R\) of polycyclic relations on \(X\), construct the polycyclic group \(G\) defined by the polycyclic presentation \(< X | R >\). The construct \(R\) denotes a list of polycyclic relations. Thus, an element of \(R\) must be one of:

(a)

A power relation \(a_i^{m_i} = w_{i,i}\), \(i\in I \subseteq \{1,\ldots,n\}\), where \(m_i>1\) is an integer, and \(w_{i,i}\) is \(Id(F)\) or a word in the generators \(a_{i+1}, \ldots,a_n\) for \(i < n\), and \(w_{i,i} = Id(F)\) for \(i = n\).

(b)

A conjugate relation \(a_j^{a_i^e} = w_{e\cdot i,j}\), \(1 \leq i < j \leq n\), where \(w_{e\cdot i,j}\) is a word in the generators \(a_{i+1}, \ldots, a_n\), \(e = 1\) if \(i\in I\) and \(e\in\{-1, 1\}\) if \(i\notin I\).

(c)

A power \(a_i^{m_i}\), \(i\in I \subseteq \{1,\ldots,n\}\), where \(m_i>1\) is an integer, which is treated as the power relation \(a_i^{m_i} = Id(F)\).

(d)

A set of (a) – (c).

(e)

A sequence of (a) – (c).

Note the following points:

(i)

If there is no power relation for some generator \(a_i\), \(i = 1, \ldots, n\) (i.e. \(i\notin I\)), conjugate relations \(a_j^{a_i^{-1}} = w_{-i,j}\) must be present for \(i<j\leq n\) (except for pairs of commuting generators). If there is a power relation for \(a_i\), on the other hand, conjugate relations involving \(a_i^{-1}\) are not permitted.

(ii)

Conjugate relations for pairs of commuting generators may be omitted. If no conjugate relations are given for a certain pair of generators, the corresponding generators are assumed to commute.

(iii)

The words \(w_{{i,j}}\) must be in normal form.

(iv)

The presentation must be consistent. In particular, right hand sides of conjugate relations must not be the empty word.

This constructor returns a polycyclic group because the category GrpGPC is stated. If no category were stated, it would return an fp-group. The parameter GrpGPC:quo:Check may be used to indicate whether or not the presentation should be checked for consistency. Disabling this check can be useful for avoiding runtime errors if the constructor is called in user written loops or functions. The boolean valued function IsConsistent is provided to check presentations obtained with disabled consistency check. It should be noted that the results of working with an inconsistent presentation are undefined, hence it is strongly advised to enable the consistency check in the constructor or to use the function IsConsistent. The natural homomorphism from \(F \rightarrow G\) is returned as second return value.

PolycyclicGroup< x₁, ..., xₙ | R : parameters >: List(Identifiers), List(GrpFPRel) -> GrpGPC, Map

Check: BoolElt                      Default: true
Class: MonStgElt                    Default: 

Construct the polycyclic group \(G\) defined by the consistent polycyclic presentation \(< x_1, \ldots, x_n | R >\).

The construct \(x_1, \ldots, x_n\) defines names for the generators of \(G\) that are local to the constructor, i.e. they are used when writing down the relations to the right of the bar. However, no assignment of names to these generators is made. If the user wants to refer to the generators by these (or other) names, then the generators assignment construct must be used on the left hand side of an assignment statement.

The construct \(R\) denotes a list of polycyclic relations. The syntax and semantics for the relations clause is identical to that appearing in the quo< GrpGPC : F | R : parameters >-constructor above.

A map \(f\) from the free group on \(x_1, \ldots, x_n\) to \(G\) is returned as second return value.

The parameter Check may be used as described for the quo< GrpGPC : F | R : parameters >-constructor.

If \(R\) is both, a valid power-conjugate presentation for a finite soluble group (cf. Chapter Finite Soluble Groups) and a consistent polycyclic presentation, this constructor by default returns a group in the category GrpPC. To force creation of a group in the category GrpGPC, the parameter Class must be set to "GrpGPC" in these situations.

Example: Constructor (ex-600748)

Consider the infinite polycyclic group defined by the presentation

\[< a, b, c\ |\ b^a = b*c, (a,c), (b,c) >.\]

Starting from a free group and giving the relations in the form of a sequence, this presentation would be specified as follows:

> F<a,b,c> := FreeGroup(3);
> rels := [ b^a = b*c, b^(a^-1) = b*c^-1 ];
> G<a,b,c> := quo< GrpGPC : F | rels >;
> G;
GrpGPC : G of infinite order on 3 PC-generators
PC-Relations:
    b^a = b * c,
    b^(a^-1) = b * c^-1

Run in calculatorCopy input

Note, that the relation \(b^{a^{-1}} = b*c^{-1}\) has to be included, although it can be derived from the relations \(b^a = b*c\) and \((a,b)\).

The infinite dihedral group is obtained as epimorphic image of the free group of rank two as follows:

> F<a,b> := FreeGroup(2);
> D<u,v>, pi := quo<GrpGPC: F | a^2, b^a = b^-1>;
> D;
GrpGPC : D of infinite order on 2 PC-generators
PC-Relations:
    u^2 = Id(D),
    v^u = v^-1
> pi;
Mapping from: GrpFP: F to GrpGPC: D

Run in calculatorCopy input

We create an element \(e\) of the group \(D\) defined above from a sequence of coefficients and extract both its leading generator and its leading exponent.

> e := D ! [1,42];
> e;
u * v^42
> gen := LeadingGenerator(e);
> gen;
u
> Parent(gen);
GrpGPC : D of infinite order on 2 PC-generators
PC-Relations:
    u^2 = Id(D),
    v^u = v^-1
> exp := LeadingExponent(e);
> exp;
1

Run in calculatorCopy input

We obtain an element of depth 2 from \(e\), by replacing \(e\) with its quotient by the appropriate power of the leading generator.

> e /:= gen^exp;
> Depth(e);
2
> e;
v^-42
> ElementToSequence(e);
[ 0, -42 ]

Run in calculatorCopy input

Example: Polycyclic Group (ex-a6668b)

Using the constructor PolycyclicGroup< x₁, ..., xₙ | R : parameters > with different values of the parameter Class, we construct the dihedral group of order 10 first as a finite soluble group given by a power-conjugate presentation (GrpPC) and next as a general polycyclic group (GrpGPC). Note that the presentation \(\langle a,b \,|\, a^2, b^5, b^a=b^4 \rangle\) is both a valid power-conjugate presentation and a consistent polycyclic presentation, so we have to set the parameter Class to "GrpGPC" if we want to construct a group in the category GrpGPC.

> G1<a,b> := PolycyclicGroup< a,b | a^2, b^5, b^a=b^4 >;
> G1;
GrpPC : G1 of order 10 = 2 * 5
PC-Relations:
    a^2 = Id(G1),
    b^5 = Id(G1),
    b^a = b^4
> G2<a,b> := PolycyclicGroup< a,b | a^2, b^5, b^a=b^4 : Class := "GrpGPC">;
> G2;
GrpGPC : G2 of order 10 = 2 * 5 on 2 PC-generators
PC-Relations:
    a^2 = Id(G2),
    b^5 = Id(G2),
    b^a = b^4

Run in calculatorCopy input

We construct the infinite dihedral group as a group in the category GrpGPC from a consistent polycyclic presentation. We do not have to use the parameter Class in this case.

> G3<a,b> := PolycyclicGroup< a,b | a^2, b^a=b^-1>;
> G3;
GrpGPC : G3 of infinite order on 2 PC-generators
PC-Relations:
    a^2 = Id(G3),
    b^a = b^-1

Run in calculatorCopy input

The presentation \(\langle a,b \,|\, a^2, b^4, b^a=b^3 \rangle\) is not a valid power-conjugate presentation for the dihedral group of order 8, since the exponent of \(b\) is not prime. However, it is a consistent polycyclic presentation. Consequently, the constructor PolycyclicGroup without specifying a value for the parameter Class returns a group in the category GrpGPC.

> G4<a,b> := PolycyclicGroup< a,b | a^2, b^4, b^a=b^3 >;
> G4;
GrpGPC : G4 of order 2^3 on 2 PC-generators
PC-Relations:
    a^2 = Id(G3),
    b^4 = Id(G3),
    b^a = b^3

Run in calculatorCopy input

Properties of a Polycyclic Presentation

IsConsistent(G): GrpGPC -> BoolElt

Returns true if the stored presentation for \(G\) is consistent, false otherwise.

IsIdenticalPresentation(G, H): GrpGPC, GrpGPC -> BoolElt

Returns true if the polycyclic presentations for \(G\) and \(H\) are identical, false otherwise.

PresentationIsSmall(G): GrpGPC -> BoolElt

Returns true if only small integers occur in the presentation of \(G\), false otherwise. The category transfer functions FPGroup and PCGroup currently support only groups with a small presentation.