Polycyclic Groups and Polycyclic Presentations

Introduction

A polycyclic group is a group G with a subnormal series G = G₁ > G₂ > .. > G_{n + 1} = 1 in which every quotient G_i / G_{i + 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) >

(i)

I is a subset of {1, .., 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)} ... a_n^{l(i, j, n)}, with 0≤l(i, j, k) < m_k if k∈I.

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₁^e₁ ... a_n^e_n, where the e_i are integers satisfying 0 ≤e_i < m_i if i∈I. This form is called normal form. There exists an algorithm (the collection algorithm), which given an arbitrary word in the generators a₁, ..., 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 [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 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ⁿ, 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₁ ... e_n, where 0≤(e_i) < m_i if i∈I, construct the element x of G given by x = a₁^e₁ ... 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₁, ..., a_n.

ElementToSequence(x) : GrpGPCElt -> [RngIntElt]

Eltseq(x) : GrpGPCElt -> [RngIntElt]

Given an element x belonging to the polycyclic group G, where x = a₁^e₁ ... a_n^e_n in normal form, return the sequence Q of n integers defined by Q[i] = (e_i), 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 a₁^e₁ ... 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₁^e₁ ... 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₁^e₁ ... 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₁^e₁ ... 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∈G_i.

Arithmetic Operations on Elements

Throughout this subsection, G will be a polycyclic group with pc-generators a₁, ..., 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_n) : List(GrpGPCElt) -> GrpGPCElt

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

If g₁, ..., 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₁, ..., 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∈I ⊆{1, ..., n}, where m_i>1 is an integer, and w_{i, i} is Id(F) or a word in the generators a_{i + 1}, ..., a_n for i < n, and w_{i, i} = Id(F) for i = n.

(b)

A conjugate relation a_j^a_ie = w_{e.i, j}, 1 ≤i < j ≤n, where w_{e.i, j} is a word in the generators a_{i + 1}, ..., a_n, e = 1 if i∈I and e∈{-1, 1} if i∉I.

(c)

A power a_i^m_i, i∈I ⊆{1, ..., 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, ..., n (i.e. i∉I), conjugate relations a_j^(a_i ^{- 1}) = w _{- i, j} must be present for i<j≤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 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< x₁, ..., x_n | 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₁, ..., x_n | R >.

The construct x₁, ..., 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-constructor above.

A map f from the free group on x₁, ..., x_n 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.

> 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

> 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

> 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

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

> 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

> 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

> 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