Construction of FP-Groups

An fp-group is normally either constructed by giving a presentation in terms of generators and relations or it is defined to be a subgroup or quotient group of an existing fp-group. However, fp-groups may be also created from finite permutation and matrix groups. Additionally, Magma has separate types for a number of families of fp-groups such as soluble groups which can be defined by power-conjugate presentations thus providing a solution to the word problem. Functions are provided to convert a member of one of these families into a general fp-group.

A finitely presented group \(G\) is a quotient group of some free group having finite rank. The free group of rank \(n\) is constructed by the intrinsic FreeGroup\((n)\). Having constructed an appropriate free group \(F\), an fp-group \(G\) is constructed by specifying relations on the generators of \(F\) that must be satisfied by the corresponding generators of \(G\). The details of how this is achieved are discussed in the following sections.

Relations

A relation is an equality between two words in an fp-group while a relator consists of a word that equals the identity, that is, it is a relation where the right hand side is understood to be the identity. A presentation is a set of symbols called generators together with a set of relations on those generators. To facilitate working with relations, a relation type is provided so that relations can be treated in a similar way to any other object in Magma. Below are the three operations that are specific to relations.

Intrinsics:

w_1 = w_2 : Given words \(w_1\) and \(w_2\) belonging to fp-group \(G\) create the relation \(w_1 = w_2\).

LHS\((r)\) : Given a relation \(r\) over the generators of \(G\), return the left hand side of the relation \(r\) as a word in \(G\).

RHS\((r)\) : Given a relation \(r\) over the generators of \(G\), return the right hand side of the relation \(r\) as a word in \(G\).

Quotient Group Constructors

A group with non-trivial relations is constructed as a quotient of an existing group, usually a free group. For convenience, the necessary free group may be constructed in-line.

Constructors:

quo\(\langle\ F\ |\ R\ \rangle\) : Given an fp-group \(F\), and a set \(R\) of relations and/or relators in the generators of \(F\), construct the quotient \(G\) of \(F\) by the normal subgroup of \(F\) defined by \(R\). The group \(G\) is defined by means of a presentation which consists of the relations for \(F\) (if any), together with the additional relations defined by the list \(R\). The constructor returns the quotient group \(G\) and the natural homomorphism \(\phi : F \rightarrow G\).

\(G\ /\ H\) : Given a subgroup \(H\) of the fp-group \(G\), construct the quotient of \(G\) by the normal closure \(N\) of \(H\). The quotient is formed by taking the presentation for \(G\) and including the generating words of \(H\) as additional relators.

Notes:

(i)

If explicit names are not available, a standard indexing notation is provided for referencing the generators of any group \(G\). Thus, G.i denotes the \(i\)-th generator of \(G\).

(ii)

Individual names may be given to the generators by means of the generator-assignment syntax. Suppose that the group \(G\) is defined on \(r\) generators. Then if \(E\) is an expression creating \(G\) the special assignment

\(G\ \langle\ v_1,\ v_2,\ \ldots,\ v_r\ \rangle\ := E\);

is equivalent to the statements

\(G := E;\ v_1 := G.1;\ v_2 := G.2;\ \dots;\ v_r := G.r\);

Example: Symmetric1 (ex-755b4c)

Three variations of the constructor are used to define the fp-group \(G\) isomorphic to the symmetric group of degree 4 with presentation \(< a, b \ | \ a^2, b^3, (ab)^4 >\). Note that as \(F\) (the free group) and \(G\) (the \(S_4\)-quotient) are two distinct groups it is necessary to have different names for the generators of each. The relations given in the quo expression are relations on the free group generators.

>  F<a, b> := FreeGroup(2);
>  G<x, y>, phi := quo< F | a^2, b^3, (a*b)^4 >;
Finitely presented group G on 2 generators
Relations
    x^2 = Id(G)
    y^3 = Id(G)
    (x * y)^4 = Id(G)

Run in calculatorCopy input

In the next example, the relations are given as a relations list.

>  F<a, b> := FreeGroup(2);
>  G<x, y>, phi :=  quo< F | a^2 = b^3 = (a*b)^4 = 1>;
> G;
Finitely presented group G on 2 generators
Relations
    x^2 = Id(G)
    y^3 = Id(G)
    (x * y)^4 = Id(G)

Run in calculatorCopy input

Another alternative is to provide a set of relators:

>  F<a, b> := FreeGroup(2);
>  rels := { a^2, b^3, (a*b)^4 };
>  G<x, y>, phi :=  quo< F | rels >;
> G;
Finitely presented group G on 2 generators
Relations
    x^2 = Id(G)
    (x * y)^4 = Id(G)
    y^3 = Id(G)

Run in calculatorCopy input

The relations printed out are in a different order than in the set rels because sets are not ordered. If it is desired to have the relations appear in some particular order then a sequence should be used.

Example: Symmetric2 (ex-17dd50)

A group may be defined using the quo-constructor without first assigning a free group. The $ symbol is used to reference a group whose quotient is being formed. Recalling the indexing notation for generators, the generic names $.1, $.2, etc can be used in this situation.

> S4<x, y> := quo< FreeGroup(2) | $.1^2, $.2^3, ($.1*$.2)^4 >;
> S4;
Finitely presented group S4 on 2 generators
Relations
      x^2 = Id(S4)
      y^3 = Id(S4)
      (x * y)^4 = Id(S4)

Run in calculatorCopy input

FP-Group constructor

For convenience, a constructor is provided which allows the user to define an fp-group without explicitly constructing a free group.

Intrinsics:

FPGroup\(\langle\ X\ |\ R\ \rangle~:\) Given a list \(X\) of variables \(x_1, \ldots, x_r\), and a list of relations \(R\) over these generators, first construct the free group \(F\) on the generators \(x_1, \cdots, x_r\) and then construct the quotient of \(F\) corresponding to the normal subgroup of \(F\) defined by the relations \(R\). The syntax for the relations \(R\) is the same as for the quo-constructor. The intrinsic returns the quotient group \(G\) and the natural homomorphism \(\phi : F \rightarrow G\).

Example: Tetrahedral (ex-20a432)

The FPGroup-constructor is used to create the binary tetrahedral group using the presentation \(< r, s \ | \ r^3 = s^3 = (rs)^2 >:\)

> G<r, s> := FPGroup< r, s | r^3 = s^3 = (r*s)^2 >;
> G;
Finitely presented group G on 2 generators
Relations
    r^3 = (r * s)^2
    s^3 = (r * s)^2

Run in calculatorCopy input

Again, using the FPGroup-constructor, the group \(< r, s, t \ | \ r^2, s^2, t^2, rst = str = trs >\) would be specified as:

> G<r, s, t> := FPGroup<r, s, t | r^2, s^2, t^2, r*s*t = s*t*r = t*r*s>;
> G;
Finitely presented group G on 3 generators
Relations
    r^2 = Id(G)
    s^2 = Id(G)
    t^2 = Id(G)
    r * s * t = t * r * s
    s * t * r = t * r * s

Run in calculatorCopy input

Example: Modular (ex-a5e77e)

As shown in this example, the quo< F | R >-constructor is not restricted to defining the quotient of a free group.

> F<x, y> := FPGroup< x, y | x^2 = y^3 = (x*y)^7 = 1 >;
> F;
Finitely presented group F on 2 generators
Relations
      x^2 = Id(F)
      y^3 = Id(F)
      (x * y)^7 = Id(F)
> G<a, b> := quo< F | (x, y)^8 >;
> G;
Finitely presented group G on 2 generators
Relations
      a^2 = Id(G)
      b^3 = Id(G)
      (a * b)^7 = Id(G)
      (a, b)^8 = Id(G)
> #G;
10752

Run in calculatorCopy input

Example: Coxeter (ex-17488a)

In this example Magma functions are used to represent parametrised families of groups. In the notation of Coxeter, the symbol \((l, m | n, k)\) denotes the family of groups having presentation

\[< a, b\ |\ a^l, b^m, (a*b)^n, (a*b^{-1})^k >.\]

> Glmnk := func< l, m, n, k | FPGroup< a, b | a^l, b^m, (a*b)^n, (a*b^-1)^k > >;
> G<a, b> := Glmnk(3, 3, 4, 4);
> G;
Finitely presented group G on 2 generators
Relations
      a^3 = Id(G)
      b^3 = Id(G)
      (a * b)^4 = Id(G)
      (a * b^-1)^4 = Id(G)
> Order(G);
168
> G<a, b> := Glmnk(2, 3, 4, 5);
> G;
Finitely presented group G on 2 generators
Relations
    a^2 = Id(G)
    b^3 = Id(G)
    (a * b)^4 = Id(G)
    (a * b^-1)^5 = Id(G)
> Order(G);
1

Run in calculatorCopy input

Thus \((2, 3 \;\;|\;\; 4, 5 )\) is the trivial group.

Presentation Operations

Intrinsics:

AddGenerator \((G)\) : Add a new generator to the presentation defining \(G\).

AddGenerator \((G,~w)\) : Add a new generator \(z\) and the relation \(z = w\) to the presentation defining \(G\).

AddRelation \((G,~r)\) : Add the relation \(r\) to the presentation defining \(G\).

AddRelation \((G,~r,~i)\) : Add the relation \(r\) after the \(i\)-th relation of the presentation defining \(G\).

DeleteGenerator \((G,~x)\) : Delete the generator \(x\) and all relations involving \(x\) from the presentation defining \(G\).

ReplaceRelation \((G,~s,~r)\) : Here each of \(r\) and \(s\) may be a relation or a word. The relation \(r\) must be part of the presentation for \(G\). The relation \(r\) is replaced by the relation \(s\) in the presentation defining \(G\).

DeleteRelation \((G, ~r)\) : Delete the relation \(r\) from the presentation defining group \(G\).

Generators \((G)\) : The set of generators for \(G\).

NumberOfGenerators \((G)\) : The number of generators used to define \(G\).

PresentationLength \((G)\): The length of the presentation defining \(G\). The length is defined to be the sum of the lengths of the words defining each relation or relator.

Simplify\((G)\) : A simplified presentation for \(G\) is found by using Tietze transformations and substring searching. A new group \(K\) defined by the simplified presentation is returned together with the isomorphism \(f:G\rightarrow K\).

SimplifyLength\((G)\) : This has the same effect as Simplify except that the simplification process terminates when the presentation length starts to increase. While it may be possible to eliminate further generators it is likely that this will significantly lengthen the simplified presentation.

Notes:

(i)

The intrinsic Simplify works by repeatedly eliminating generators and subsequently shortening relators by substitution of substrings that correspond to the left or right hand side of a relation. The transformation process terminates when no more eliminations of generators and no more length reducing substring replacements are possible. The choice of simplification strategy can either be left to Magma or selected by the user, The simplification process can be controlled by a set of parameters described in chapter Finitely Presented Groups.

Example: Simplify1 (ex-c32ec7)

Consider the Fibonacci group \(F(8)\).

> F<x1, x2, x3, x4, x5, x6, x7, x8> := FreeGroup(8);
> F8<x1, x2, x3, x4, x5, x6, x7, x8> :=
>     quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
>              x5*x6=x7, x6*x7=x8, x7*x8=x1, x8*x1=x2>;

Run in calculatorCopy input

The intrinsic Simplify will be applied to obtain a presentation of \(F(8)\) on fewer generators. It is returned as the presentation for a new group \(H\). As the number of generators used in the simplified presentation for \(H\) is unknown it is necessary to use a variation of the generator assignment expression: H<[y]>. This will give the generators of \(H\) the names y[1], y[2], .... Here \(y\) is any variable name.

> H<[y]>, f := Simplify(F8);
> H;
Finitely presented group H on 2 generators
Generators as words in group F8
    y[1] = x3
    y[2] = x4
Relations
    y[2] * y[1]^-2 * y[2] * y[1]^-1 * y[2]^2 * y[1] * y[2]^2 *
       y[1]^-1 = Id(H)
    y[1] * y[2] * y[1] * y[2]^2 * y[1] * y[2] * y[1]^2 * y[2]^-1
       * y[1] = Id(H)

Run in calculatorCopy input

The isomorphism \(f\) can be used to express the old generators in terms of the new ones.

> f;
Mapping from: GrpFP: F8 to GrpFP: H
> f(x1);
y[1]^2 * y[2]^-1

Run in calculatorCopy input

Operations on Words

The words \(u\) and \(v\) in the intrinsics below must belong to a common fp-group \(G\).

Intrinsics:

\(u\ *\ v\) : The product of words \(u\) and \(v\).

\(u^{-1}\) : The inverse of word \(u\).

Identity (\(G)\) : The identity element for group \(G\). Other notations are Id (\(G)\) and \(G!1\).

\(u^n\) : The \(n\)-th power of \(u\).

\(u^v\) : The conjugate \(v^{-1}*u*v\) of words \(u\) and \(v\).

\((u, v)\) : The commutator \(u^{-1}*v^{-1}*u*v\) of words \(u\) and \(v\).

\(u\ \)eq\(\ v\) : Returns true if the words \(u\) and \(v\) are identical when freely reduced. NB When \(G\) is not a free group and false is returned, this does not imply that \(u\) and \(v\) do not represent the same element of \(G\).

\(u\ \)ne\(\ v\) : Returns true if the words \(u\) and \(v\) are distinct when freely reduced. NB When \(G\) is not a free group and true is returned, this does not imply that \(u\) and \(v\) do not represent the same element of \(G\).

Presentations for Popular Groups

Intrinsics are provided for constructing presentations for a number of familiar groups.

Intrinsics:

AbelianFPGroup \((Q)\) : The abelian group defined by the sequence of integers \(Q\).

CyclicFPGroup \((n)\) : The cyclic group of order \(n\).

AlternatingFPGroup \((n)\) : The alternating group of degree \(n\) on two generators.

BraidFPGroup \((n)\) : The braid group on \(n\) strings on \(n-1\) Artin generators.

DihedralFPGroup \((n)\) : For \(n > 2\), the dihedral group of order \(2n\) on two generators.

SymmetricFPGroup\((n)\) : The symmetric group of degree \(n\) on two generators.

Example: Abelian (ex-318133)

An abelian group is presented as a direct product of cyclic groups. This direct product is defined by a sequence of integers giving the orders of the cyclic factors, where \(0\) indicates \({\mathbb{Z}}\). To illustrate this the code below constructs the abelian group \({\mathbb{Z}}_4 \times {\mathbb{Z}}_9 \times {\mathbb{Z}}\).

> A<a, b, c> := AbelianFPGroup([4, 9, 0]);
> A;
Finitely presented group A on 3 generators
Relations
    a^4 = Id(A)
    b^9 = Id(A)
    a * b = b * a
    a * c = c * a
    b * c = c * b

Run in calculatorCopy input

Example: Symetric (ex-169352)

In this example the symmetric group \({\operatorname{Sym}}(8)\) is constructed as an fp-group:-

> S8<x, y> := SymmetricFPGroup(8);
> S8;
Finitely presented group S8 on 2 generators
Relations
    x^8 = Id(S8)
    y^2 = Id(S8)
    (x * y)^7 = Id(S8)
    (x^-1 * y * x * y)^3 = Id(S8)
    (y * x^-2 * y * x^2)^2 = Id(S8)
    (y * x^-3 * y * x^3)^2 = Id(S8)
    (y * x^-4 * y * x^4)^2 = Id(S8)

Run in calculatorCopy input

Constructions for FP-Groups

Intrinsics are provided to construct products of fp-groups and also to to transform groups defined by various types of polycyclic presentations into fp-groups. In addition there are intrinsics which construct a presentation for a finite permutation or matrix group \(G\) and return a fp-group isomorphic to \(G\).

Intrinsics:

DirectProduct \((G, H)\) : The direct product of the fp-groups \(G\) and \(H\).

FreeProduct \((G, H)\) : The free product of the fp-groups \(G\) and \(H\).

FPGroup \((T)\) : If \(T\) is a finite nilpotent or soluble group defined by a polycyclic presentation return an fp-group \(G\) isomorphic to \(T\) together with the isomorphism \(\phi: T \rightarrow G\).

FPGroup \((T)\) : If \(T\) is a finite permutation or matrix group of moderate size then return an fp-group \(G\) isomorphic to \(T\) together with the isomorphism \(\phi: G \rightarrow T\).

FPGroupStrong \((T)\) : If \(T\) is a finite permutation or matrix group which may have order much greater than a million return an fp-group \(G\) isomorphic to \(T\). While FPGroup returns a presentation on the permutation/matrix generators, FPGroupStrong constructs a presentation on a larger set of generators (strong generators for \(T\)). An isomorphism \(\phi: G \rightarrow T\) is also returned.

Notes:

(i)

Note that the intrinsic FPGroup applied to permutation or matrix groups may need to construct the coset table of \(G\) over the identity and hence is limited to groups of order less than a million. The exact limit is determined by the amount of memory available.

Example: Product F Ps (ex-7dc82f)

The direct product and free product of the alternating group of degree \(7\) and the cyclic group of order \(2\) are created as follows:-

> A7<a, b> := AlternatingFPGroup(7);
> A7;
Finitely presented group A7 on 2 generators
Relations
    a^5 = Id(A7)
    b^3 = Id(A7)
    (a * b)^7 = Id(A7)
    (b * a^-1 * b * a)^2 = Id(A7)
    (b * a^-2 * b * a^2)^2 = Id(A7)
> Z2<c> := CyclicFPGroup(2);
Finitely presented group Z2 on 1 generator
Relations
    c^2 = Id(Z2)
> G<x, y, z> := DirectProduct(A7, Z2);
> G;
Finitely presented group G on 3 generators
Relations
    x^5 = Id(G)
    y^3 = Id(G)
    (x * y)^7 = Id(G)
    (y * x^-1 * y * x)^2 = Id(G)
    (y * x^-2 * y * x^2)^2 = Id(G)
    z^2 = Id(G)
    x * z = z * x
    y * z = z * y
> H<x, y, z> := FreeProduct(A7, Z2);
> H;
Finitely presented group H on 3 generators
Relations
    x^5 = Id(H)
    y^3 = Id(H)
    (x * y)^7 = Id(H)
    (y * x^-1 * y * x)^2 = Id(H)
    (y * x^-2 * y * x^2)^2 = Id(H)
    z^2 = Id(H)

Run in calculatorCopy input

Note that the free product is always an infinite group.

Example: FP Group (ex-c105bf)

In this example, an fp-group \(G\) that is isomorphic to GL\((3, 4)\) of order 181440 is created.

> k<u> := GF(4);
> T := GL(3, k); #T;
181440
> T;
MatrixGroup(3, GF(2^2)) of order 2^6 * 3^4 * 5 * 7
Generators:
    [    u     0     0]
    [    0     1     0]
    [    0     0     1]

    [    1     0     1]
    [    1     0     0]
    [    0     1     0]

> G<x, y> := FPGroup(T);
> G;
Finitely presented group G on 2 generators
Relations
      x^3 = Id(G)
      y^7 = Id(G)
      (x, y)^3 = Id(G)
      (x*y^-1*x^-1*y^2)^3 = Id(G)
      x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x*y*x*y^-1*x*y*x*y^-1 = Id(G)
      y^-1*x^-1*y*x^-1*y^-1*x*y^-1*x^-1*y^-1*x*y*x*y^-1*x*y^3*x^-1 = Id(G)
      (y^-1*x^-1*y^-1*x*y^-2)^3 = Id(G)

Run in calculatorCopy input