Polycyclic Groups and Polycyclic Presentations

Contents

Introduction

A polycyclic group is a group G with a subnormal series G = G1 > G2 > .. > Gn + 1 = 1 in which every quotient Gi / Gi + 1 is cyclic. Every polycyclic group G has a presentation of the form 

 < a_1,..,a_n | a_i ^(m_i)= w_(i,i)        (i in I) ,
                a_j ^(a_i)= w_(i,j)        (1 <= i < j <= n),
                a_j ^(a_i^(-1))= w_(-i,j)  (1 <= i < j <= n, i not in I) >
where
(i)
I is a subset of {1, .., n},
(ii)
mi > 1 for i in I, and
(iii)
the words wi, j are of the form wi, j = a|i| + 1l(i, j, |i| + 1) ... anl(i, j, n), with 0≤l(i, j, k) < mk if k∈I.

Such a presentation is called a polycyclic presentation for G. For 1≤i≤n, let Gi be the subgroup of G generated by ai, ..., an and define Gn + 1 to be the trivial group. The presentation is called consistent, if |Gi / Gi + 1|=mi whenever i is in I and the quotient Gi / Gi + 1 is infinite whenever i is not in I. The generators a1, ... an are referred to as polycyclic generators (pc-generators) for G and the values mi (i∈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=a1e1 ... anen, where the ei are integers satisfying 0 ≤ei < mi if i∈I. This form is called normal form. There exists an algorithm (the collection algorithm), which given an arbitrary word in the generators a1, ..., an, 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 ei occurring during the collection [Geb02].

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 uv of the word u by the word v is a word (uv expands into the word v - 1 * u * v);
(v)
The power of a word un, 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 e1 ... en, where 0≤(ei) < mi if i∈I, construct the element x of G given by x = a1e1 ... anen.
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 a1, ..., an.

ElementToSequence(x) : GrpGPCElt -> [RngIntElt]
Eltseq(x) : GrpGPCElt -> [RngIntElt]
Given an element x belonging to the polycyclic group G, where x = a1e1 ... anen in normal form, return the sequence Q of n integers defined by Q[i] = (ei), for i = 1, ..., n.
LeadingTerm(x) : GrpGPCElt -> GrpGPCElt
Given an element x of a polycyclic group G with n pc-generators, where x is of the form a1e1 ... anen, return aiei for the smallest i such that ei > 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 a1e1 ... anen, return ai for the smallest i such that ei > 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 a1e1 ... anen, return ei for the smallest i such that ei > 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 a1e1 ... anen, return the smallest i such that ei > 0. If x is the identity of G, then n + 1 is returned.

Depth returns the maximal value of i, such that x∈Gi.

Arithmetic Operations on Elements

Throughout this subsection, G will be a polycyclic group with pc-generators a1, ..., an.

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 gh are the same as for g * h.
g ^:= h : GrpGPCElt, GrpGPCElt ->
Replace g with the conjugate of the element g by the element h.
(g1, ..., gn) : List(GrpGPCElt) -> GrpGPCElt
Given the n words g1, ..., gn belonging to some common subgroup G of a polycyclic group U, compute the left-normed commutator of g1, ..., gn. This is defined inductively as follows: (g1, g2) = g1 - 1 * g2 - 1 * g1 * g2 and (g1, ..., gn) = ((g1, ..., gn - 1), gn).

If g1, ..., gn 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 g1, ..., gn 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 aimi = wi, i, i∈I ⊆{1, ..., n}, where mi>1 is an integer, and wi, i is Id(F) or a word in the generators ai + 1, ..., an for i < n, and wi, i = Id(F) for i = n.
(b)
A conjugate relation ajaie = we.i, j, 1 ≤i < j ≤n, where we.i, j is a word in the generators ai + 1, ..., an, e = 1 if i∈I and e∈{-1, 1} if i∉I.
(c)
A power aimi, i∈I ⊆{1, ..., n}, where mi>1 is an integer, which is treated as the power relation aimi = 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 ai, i = 1, ..., n (i.e. i∉I), conjugate relations aj^(ai - 1) = w - i, j must be present for i<j≤n (except for pairs of commuting generators). If there is a power relation for ai, on the other hand, conjugate relations involving ai - 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 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 -> G is returned as second return value.

PolycyclicGroup< x1, ..., xn | 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 < x1, ..., xn | R >.

The construct x1, ..., xn 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-constructor above.

A map f from the free group on x1, ..., xn to G is returned as second return value.

The parameter Check may be used as described for the quo-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 GrpGPC_Constructor (H79E1)

(1)
Consider the infinite polycyclic group defined by the presentation < a, b, c | ba = 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
Note, that the relation b^(a - 1) = b * c - 1 has to be included, although it can be derived from the relations ba = b * c and (a, b).
(2)
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
(3)
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
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 ]

Example GrpGPC_PolycyclicGroup (H79E2)

Using the constructor PolycyclicGroup 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 < a, b | a2, b5, ba=b4 > 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
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
The presentation < a, b | a2, b4, ba=b3 > 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

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.
V2.28, 13 July 2023