Diplomarbeit

Polycyclic presentations for matrix groups

Björn Assmann

Betreuerin Professor Dr. Bettina Eick

Institut für Geometrie Technische Universität Braunschweig

Pockelstr.14 38106 Braunschweig

Braunschweig, den 9. September 2003

Eidesstattliche Erklärung

Hiermit bestätige ich an Eides statt, dass ich die vorliegende Arbeit selbstständig und nur unter Verwendung der angegebenen Hilfsmittel verfasst habe.

Braunschweig, den 9. September 2003 Unterschrift

Contents

1 Introduction 1 1.1 History and related research . . . . . . . . . . . . . . . . . . . 2 1.2 Overview and structure of the thesis . . . . . . . . . . . . . . 3 1.3 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Polycyclic groups 5 2.1 Polycyclic sequences . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Polycyclic presentations . . . . . . . . . . . . . . . . . . . . . 7 2.3 Solvable versus polycyclic . . . . . . . . . . . . . . . . . . . . 8 2.4 Matrix groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Finite solvable matrix groups 11 3.1 Cyclic extensions of constructive pc-sequences . . . . . . . . . 12 3.2 Abelian Upwards Extensions . . . . . . . . . . . . . . . . . . 16 3.3 Constructive polycyclic sequences . . . . . . . . . . . . . . . . 18

4 Algebraic number fields 21

4.1 Computing relation lattices in number fields . . . . . . . . . . 22 4.1.1 Calculating the unit relation lattice . . . . . . . . . . 22 4.1.2 Calculating the relation lattice in U(O) . . . . . . . . 26

4.1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 Constructive polycyclic sequences . . . . . . . . . . . . . . . . 30 4.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Unipotent groups 33 5.1 Conjugation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 Constructive pc-sequences . . . . . . . . . . . . . . . . . . . . 38

6 Rational Module Series 41 6.1 Module Theory and p-congruence subgroups . . . . . . . . . . 41 6.2 Induced Action . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2.1 Integral Basis of rational spaces . . . . . . . . . . . . . 43 6.2.2 Factor modules . . . . . . . . . . . . . . . . . . . . . . 45

6.3 Computing radicals . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3.1 Abelian rational matrix groups . . . . . . . . . . . . . 46 6.3.2 Rational matrix groups . . . . . . . . . . . . . . . . . 49

6.4 Radical series . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.5 Semisimple groups . . . . . . . . . . . . . . . . . . . . . . . . 53

6.5.1 Abelian semisimple groups . . . . . . . . . . . . . . . 53 6.6 Composition series . . . . . . . . . . . . . . . . . . . . . . . . 56

7 Main algorithms 59 7.1 Normal subgroup generators . . . . . . . . . . . . . . . . . . . 59 7.2 Solvability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.2.1 Finite matrix groups . . . . . . . . . . . . . . . . . . . 61 7.2.2 Rational matrix groups . . . . . . . . . . . . . . . . . 61

7.3 Calculating presentations . . . . . . . . . . . . . . . . . . . . 63 7.3.1 Finite matrix groups . . . . . . . . . . . . . . . . . . . 63

7.3.2 Rational matrix groups . . . . . . . . . . . . . . . . . 63 7.4 A further possible refinement . . . . . . . . . . . . . . . . . . 66

8 Performance 67 8.1 Runtimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.2 Bottle necks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Chapter 1

Introduction

A group G is called polycyclic if there exists a subnormal series of the form

G = G_{1} ⊳ G_{2} ⊳ ⋯ G_{n} ⊳ G_{n+1} = 1  (∗)

with cyclic factors G_{i}/G_{i+1}. By a well-known result of Hirsch every polycyclic group is finitely presented (see also Theorem 2.2.2). Among the finite presentations of a polycyclic group G, there are some that reflect the structure of the subnormal series (∗). Such presentations are called polycyclic presentations (pc-presentations) and will be defined in Section 2.2.

If a polycyclic group G is given by a pc-presentation, then many problems of group theory can be solved in practice. For example, one can determine if G is torsion-free and calculate the torsion subgroup T, if T exists. Further, one can compute the derived series and the Hirsch length of the group G. Also various methods for computations with subgroups, factor groups and extensions are available. All these methods are available in the package ’Polycyclic’ [8] of the computer algebra system GAP [24].

Groups often arise in a natural way as matrix groups over ℚ (for instance in the study of symmetries of crystals). But for such matrix groups certain problems are difficult to solve. For example, it is not easy to decide, if the torsion subgroup exists, and to calculate it if it does. On the other hand, these problems are easy to solve once a pc-presentation for a polycyclic group is known. Therefore a method is needed to determine a pc-presentation for a given polycyclic matrix group.

The aim of this thesis is the description and implementation of algorithms for the following tasks: Let G be a finitely generated subgroup of GL(d, R) where the ring R is either ℚ, ℤ or a finite field 𝔽_{q}. Then

• we can test whether G is solvable;

• if G is polycyclic, then we can determine a pc-presentation for G.

If R = ℤ or 𝔽_{q} the group G is polycyclic if and only if G is solvable (see Chapter 2, Section 2.3). Therefore, we can test if such a G is polycyclic.

The implemented algorithms are available in the GAP-package ’Polenta’ [1], which can be downloaded from

http://cayley.math.nat.tu-bs.de/software/content.html

The implementation is based on the computer algebra systems GAP [24] and KANT [10]. Our aim was the development and the implementation of practical algorithms, that is, algorithms which can be applied to a collection of significant examples.

The overall algorithm involves ideas from different areas of computational mathematics. It utilizes classical methods like the orbit-stabilizer algorithm optimized to the given structure. In addition it also uses techniques from algebraic number theory, for example, the factorization of fractional ideals. Finally also representation theory is used, for example, the calculation of certain submodule series plays an important role.

1.1 History and related research

In 1985 John D. Dixon [5] investigated the orbit-stabilizer problem for linear groups. He found a structure theorem for polycyclic subgroups of GL(d, ℚ) (see Corollary 2.4.5), which is important in this context also.

Based on this, Gretchen Ostheimer [14] proved in 1996, that the calculation of a pc-presentation for a polycyclic subgroup of GL(d, ℚ) can be reduced to three simpler problems: the calculation of a pc-presentation for

• solvable groups in GL(d, 𝔽_{q}), where 𝔽_{q} is a finite field;

• multiplicative subgroups of an algebraic extension field of ℚ;

• unipotent subgroups of GL(d, ℚ).

Ostheimer described algorithms for all three steps, but a full implementation was not available.

In 2001 Bettina Eick [6] refined the approach of Ostheimer and described practical approaches for the first two parts of Ostheimer’s method.

Part one is based on an algorithm of Charles C. Sims [22] for the computation of the order of solvable permutation groups. This algorithm together with an efficient implementation is given in this thesis.

Part two is based on computations in algebraic number fields and representation theory, and has been developed with the help of Jürgen Klüners and Florian Hess.

Part three has been known for some time, and can be solved following the ideas of Chapter 9 in the book of Sims [21].

Finally, we note that there exists an alternative approach to compute a polycyclic presentation of a rational polycyclic matrix group by Robert Beals (see for example [2] and [3]). We are not aware of an implementation of this method, which uses randomized methods.

1.2 Overview and structure of the thesis

In Chapter 2 we give a brief introduction to polycyclic groups. It covers polycyclic presentations, polycyclic generating sequences and the connections between solvable and polycyclic groups.

As outlined in Section 1.1, it is possible to reduce the problem of the calculation of a pc-presentation for a polycyclic matrix group G ≤ GL(d, ℚ) to three simpler groups, which are interesting in their own right. These are finite matrix groups, multiplicative subgroups of an algebraic extension of ℚ and unipotent matrix groups:

Chapter 3 describes algorithms to compute a pc-presentation for finite matrix groups over a given ring.

Chapter 4 provides methods to calculate a pc-presentation for multiplicative subgroups of an algebraic extension of ℚ.

In Chapter 5 we outline how to compute pc-presentations of unipotent rational matrix groups.

For the splitting of G ≤ GL(d, ℚ) into the three mentioned kind of groups, some representation theory is needed. Regard ℚ^{d} as the natural ℚG-module. Chapter 6 contains an algorithm for the determination of the radical series of ℚ^{d}. Further, we show that for the p-congruence subgroup K ⊲ G (see Definition 2.4.2) it is possible to compute a composition series of the ℚKmodule ℚ^{d}.

Finally, in Chapter 7 we present the overall algorithm to compute a pcpresentation for a rational polycyclic matrix group and propose some refinements. Further we show that a similar approach can be used to test if a matrix group over ℚ, ℤ or a finite field 𝔽_{q} is solvable or not. For a matrix group over ℤ or 𝔽_{q}, we can also test, if the given group is polycyclic.

In Chapter 8 we give runtimes of the implemented algorithms and describe the bottle necks.

1.3 Acknowledgments

I am grateful for Bettina Eick for her supervision. She was always available when help was needed and I always obtained reliable advice from her. Further, I would like to thank Csaba Schneider for lots of helpful comments on writing this text and Gretchen Ostheimer for giving me a very nice introduction to the topic of this thesis. Finally I want to thank Jürgen Klüners for his help in algebraic number theory and Christian Sievers for his hint for Lemma 5.1.5.

Polycyclic groups

This chapter provides some basic facts about polycyclic groups and a structure theorem for polycyclic matrix groups. For further background on polycyclic groups we refer to [21] chapter 9, [19] page 147ff and [20].

2.1 Polycyclic sequences

2.1.1 Definition: Let G be a polycyclic group with a subnormal series

G = G_{1} ⊳ G_{2} ⊳ ⋯ G_{n} ⊳ G_{n+1} = 1  (∗)

with cyclic factors G_{i}/G_{i+1}. A list G = (g_{1}, …, g_{n}) is called a polycyclic sequence (or sometimes a polycyclic generating sequence) for G if

G_{i}/G_{i+1} = ⟨g_{i}G_{i+1}⟩

for i = 1, …, n. For every factor G_{i}/G_{i+1} we denote by r_{i} ∈ ℕ ∪ {∞} the index of G_{i+1} in G_{i}. We call (r_{1}, …, r_{n}) the relative orders of G.

2.1.2 Lemma: Let g be an element of a polycyclic group G with polycyclic sequence G = (g_{1}, …, g_{n}). Then we can write g uniquely as

g = g_{1}^{e_{1}} · · · · · g_{n}^{e_{n}}

where (e_{1}, …, e_{n}) ∈ ℤ^{n} and 0 ≤ e_{i} < r_{i} if r_{i} < ∞.

Proof: We proof the lemma by induction. Let g ∈ G_{n}. Then g can be uniquely written as g = g_{n}^{e_{n}} where e_{n} ∈ ℤ and 0 ≤ e_{n} < r_{n} if r_{n} < ∞.

Now we assume that g ∈ G_{i} with i < n. Since G_{i}/G_{i+1} = ⟨g_{i}G_{i+1}⟩ there exists an ê_{i} ∈ ℤ such that gG_{i+1} = gê_{i} ; iG_{i+1}. The number ê_{i} is unique if r_{i} = ∞. Then we set e_{i} := ê_{i}. If r_{i} < ∞, then the exponent can be uniquely chosen by setting e_{i} := ê_{i} mod r_{i}. It follows that g_{i}^{−e_{i}}g ∈ G_{i+1}. By induction we can suppose that we can write uniquely g_{i}^{−e_{i}}g = g_{i+1}^{e_{i+1}} ⋯ g_{n}^{e_{n}} where (e_{i+1}, …, e_{n}) ∈ ℤ^{n−i} and 0 ≤ e_{j} < r_{j} if r_{j} < ∞ for j = i + 1, …, n. We deduce that

g = g_{i}^{e_{i}} ⋯ g_{n}^{e_{n}}.

For i = 1 this gives the wanted result. •

2.1.3 Definition: The unique list (e_{1}, …, e_{n}) ∈ ℤ^{n} from the last Lemma 2.1.2 is called the exponent vector of g with respect to G. It will be denoted by exp_{G}(g).

2.1.4 Example: Regard the group G generated by the matrices

g_{1} := ( \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ) , g_{2} := ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) .

We verify that g_{2}^{g_{1}} = g_{2}^{−1} ∈ ⟨g_{2}⟩. Thus

G ⊳ ⟨g_{2}⟩ ⊳ 1

is a subnormal series of G with cyclic factors and so G is polycyclic. The list G = (g_{1}, g_{2}) is a polycyclic sequence for G with relative orders (2, ∞). Consider the element

g := ( \begin{matrix}−1 & 2 \\ 0 & 1 \end{matrix} ) ∈ G.

It is easy to see that g = g_{1}g_{2}^{−2} and so exp_{G}(g) = (1, −2).

2.1.5 Definition: Let G be a polycyclic group. A polycyclic sequence G for G is called a constructive polycyclic sequence (constructive pc-sequence), if the relative orders of G are known and if there exists a practical algorithm, which computes for any element g ∈ G the exponent vector exp_{G}(g).

Note that in general, it is a non-trivial task to find a constructive polycyclic sequence for a polycyclic matrix group.

2.2 Polycyclic presentations

Let G be a polycyclic group with a polycyclic sequence G = (g_{1}, …, g_{n}) and relative orders (r_{1}, …, r_{n}). Denote by I the finite index set of G, that is

I := { i | 1 ≤ i ≤ n, r_{i} ≠ ∞ } .

By the properties of a polycyclic group it follows that g_{i}^{g_{j}^{±1}} ∈ G_{j+1} for 1 ≤ j < i ≤ n and g_{i}^{r_{i}} ∈ G_{i+1} for 1 ≤ i ≤ n and r_{i} ≠ ∞. Thus we can write these expressions as words in the generators g_{j+1}, …, g_{n} respectively g_{i+1}, …, g_{n}.

2.2.1 Definition: The equations

g_{i}^{g_{j}} = g_{j+1}^{a(i,j,j+1)} ⋯ g_{n}^{a(i,j,n)} for 1 ≤ j < i ≤ n,
g_{i}^{g_{j}^{−1}} = g_{j+1}^{b(i,j,j+1)} ⋯ g_{n}^{b(i,j,n)} for 1 ≤ j < i ≤ n and j ∉ I

are called the conjugate relations and

g_{i}^{r_{i}} = g_{i+1}^{c(i,i+1)} ⋯ g_{n}^{c(i,n)} for i ∈ I

are said to be the power relations of the polycyclic sequence G.

The next theorem shows that the power-conjugate relations of a polycyclic sequence give rise to a finite presentation for the group G.

2.2.2 Theorem: Let G be a polycyclic sequence of a polycyclic group G with power-conjugate relations as in Definition 2.2.1. Let F be a free group on the abstract generators in F = { f_{1}, …, f_{n}}. Define R to be the set of relations

f_{i}^{f_{j}} = f_{j+1}^{a(i,j,j+1)} ⋯ f_{n}^{a(i,j,n)} for 1 ≤ j < i ≤ n,
f_{i}^{f_{j}^{−1}} = f_{j+1}^{b(i,j,j+1)} ⋯ f_{n}^{b(i,j,n)} for 1 ≤ j < i ≤ n and j ∉ I
f_{i}^{r_{i}} = f_{i+1}^{c(i,i+1)} ⋯ f_{n}^{c(i,n)} for i ∈ I.

Then ⟨ F | R ⟩ is a presentation for G.

Proof: See [21] Section 9.4. or [6] Chapter 2, Lemma 2.2. •

2.2.3 Definition: The finite presentation ⟨ F | R ⟩ of a polycyclic group G of Theorem 2.2.2 is called a polycyclic presentation (pc-presentation) of G.

2.2.4 Example: Consider the group G defined in Example 2.1.4 with the polycyclic sequence G = (g_{1}, g_{2}). We obtain the power-conjugate relations

g_{2}^{g_{1}} = g_{1}^{0}g_{2}^{−1}
g_{1}^{2} = g_{1}^{0}g_{2}^{0}

of G. By Theorem 2.2.2

⟨ f_{1}, f_{2} | f_{2}^{f_{1}} = f_{2}^{−1}, f_{1}^{2} = 1 ⟩

is a polycyclic presentation for G. Note that G is the infinite dihedral group.

2.2.5 Corollary: Let G be a constructive pc-sequence of a polycyclic group G. Then by calculating the power-conjugate relations we can calculate a polycyclic presentation for G.

2.3 Solvable versus polycyclic

The class of polycyclic groups is closed with respect to forming subgroups, factor groups and extensions (see [21] Section 9.3). Further, every polycyclic group is solvable but the converse is not true. In the following we recall some connections between solvable and polycyclic groups.

2.3.1 Theorem: A group G is polycyclic if and only if it is solvable and every subgroup of G is finitely generated. In particular a finite group is polycyclic if and only if it is solvable.

Proof: See [20] Chapter 1, Proposition 4. •

2.3.2 Theorem: Every solvable group of automorphisms of a polycyclic group is polycyclic.

Proof: See [20] Chapter 2, Theorem 1. •

2.3.3 Corollary: Let G be subgroup of GL(d, ℤ). Then G is polycyclic if and only if G is solvable.

Proof: Let G be a solvable subgroup of GL(d, ℤ). The additive group ℤ^{d} is polycyclic. Therefore, by Theorem 2.3.2, G ≤ GL(d, ℤ) = Aut(ℤ^{d}) is polycyclic. Conversely, we assume that G is a polycyclic group. Then G is solvable by Theorem 2.3.1. •

2.4 Matrix groups

Let G be a subgroup of GL(d, ℚ) which is generated by a finite number of elements g_{1}, …, g_{k}. Define π to be the set of primes which divide a denominator of a matrix entry of g_{1}, …, g_{k}, g_{1}^{−1}, …, g_{k}^{−1}. Denote by ℚ_{π} the set of rational numbers whose denominator is divisible by primes in π only. Then it can be observed readily, that the group G is contained in GL(d, ℚ_{π}).

2.4.1 Definition: Let G ≤ GL(d, ℚ_{π}) and let p be an odd prime which is not contained in π. Then p is called an admissible prime for the matrix group G.

If p ∉ π, then there is an homomorphism

χ_{p} : ℚ_{π} → ℤ/pℤ
\frac{a}{b} → (a + pℤ) · (b + pℤ)^{−1}.

2.4.2 Definition: Let be G be a subgroup of GL(d, ℚ_{π}) and let p be an admissible prime for G. The map

ψ_{p} : G → GL(d, p)

which applies χ_{p} to every entry of a matrix g ∈ G, is said to be the pcongruence homomorphism from G to GL(d, p). The kernel of ψ_{p} is denoted by K_{p}(G) and is said to be the p-congruence subgroup of G. The image of ψ_{p} is called the p-modular image and we denote it by I_{p}(G).

2.4.3 Definition: Let U be a subgroup of GL(d, ℚ). An element u ∈ U is called unipotent if there exists a natural number m ∈ ℕ such that

(u − 1)^{m} = 0.

The group U is called unipotent, if every element in U is unipotent.

We can now formulate the important structure theorem of Dixon on which the algorithms in this book are based.

2.4.4 Theorem: Let G be a finitely generated subgroup of GL(d, ℚ_{π}) and p an admissible prime for G. If the kernel K_{p}(G) of the p-congruence homomorphism has a solvable subgroup of finite index, then the commutator subgroup K_{p}(G)′ is unipotent. Further, the group K_{p}(G) is torsion-free.

Proof: See [5] Lemma 9 and Section 7. • 2.4.5 Corollary: Let G be a polycyclic subgroup of GL(d, ℚ). Then the kernel K_{p}(G) of the p-congruence homomorphism is torsion-free and K_{p}(G)′ is unipotent.

Proof: If G is polycyclic, then K_{p}(G) is polycyclic as well. Thus K_{p}(G) is solvable and we can apply Theorem 2.4.4. •

polycyclic G 1 K_{p}(G)′ torsion-free K_{p}(G)  } abelian } unipotent } ≃ ψ_{p}(G) finite

Figure 2.1: Corollary 2.4.5 to Dixon’s Theorem

Finite solvable matrix groups

Let G ≤ GL(d, R) be a finite matrix group where R is a ring. By Theorem 2.3.1 the group G is solvable if and only if G is polycyclic. In this chapter we want to describe a method to compute a polycyclic presentation (see Definition 2.2.3) for G, if G is solvable. Further, our algorithm can be used to test if G is solvable.

Recall that a constructive polycyclic sequence of a group G is a polycyclic sequence, for which the relative orders are known, and a practical algorithm is given to compute the exponent vector for any element g in G. By Corollary 2.2.5, it is sufficient to calculate a constructive polycyclic sequence for G, to obtain a polycyclic presentation for G.

We use an inductive approach for this purpose. For the trivial subgroup N := {1} ⊲ G a constructive polycyclic sequence is given. For the induction step we assume, that a constructive polycyclic sequence for a normal subgroup N of G is available. In the following Section 3.1 we show how to extend such a constructive polycyclic sequence to a group H := ⟨g, N⟩ where g is in G\N. Then in Section 3.2 we present methods to compute suitable elements g for such an extension. Finally in Section 3.3 the algorithm for the calculation of a constructive polycyclic sequence of a finite solvable matrix group is presented.

3.1 Cyclic extensions of constructive pc-sequences

Let N be a normal subgroup of a finite solvable matrix group G acting faithfully on set W. Suppose that a constructive pc-sequence for N is given, consisting of the elements

N = (n_{1}, …, n_{k})

with relative orders (r_{1}, …, r_{k}). Further let g be an element of G\N and define H := ⟨g, N⟩. The group H is called a cyclic extension of N. We want to extend the constructive pc-sequence of N to a constructive pc-sequence

H = (g, n_{1}, …, n_{k})

of H. The following lemma follows directly from the definition of the relative orders and the exponent vector.

3.1.1 Lemma:

1. Let r be the smallest natural number such that g^{r} ∈ N and hence r = [H : N]. Then the relative orders of H are given by (r, r_{1}, …, r_{k}).

2. Let h = g^{e}n be an arbitrary element of H where e ∈ ℤ and n ∈ N. This implies that

exp_{H}(h) = (e mod r, exp_{N} (n)).

In our way to the extension of a constructive pc-sequence, stabilizers and orbits will play an important role. They allow us to divide the calculation of the relative order r in smaller pieces. For this reason we recall some basic definitions:

3.1.2 Definition: Let G be a group acting on a set W := {1, …, n} and let B := (w_{1}, …, w_{k}) be a sequence of different points in W. Define G_{0} := G and G_{i} := Stab_{G_{i−1}}(w_{i}) for 1 ≤ i ≤ k. Then the series

G = G_{0} ≥ G_{1} ≥ ⋯ ≥ G_{k}

is called the stabilizer-chain corresponding to B. The sequence B is called a base for G, if the group G_{k} is trivial.

Since N is a normal subgroup of the matrix group G, we note that

(wN)g = (wg)N

for all g in G. Therefore G acts on the set of N-orbits in W. The following lemma shows, that the stabilizers H_{i} have the same relationship to the stabilizers N_{i} as H to N. This is the reason, why the concept of a base and its corresponding stabilizers is very useful for the determination of the structure of a cyclic extension.

3.1.3 Lemma: Let N be a normal subgroup of G acting faithfully on a set W. Define the group H to be a cyclic extension of N generated by N and an element g ∈ G\N. Then there exists a natural number l = l(H, N) ∈ ℕ and an element n ∈ N such that

Stab_{H}(w) = ⟨g^{l}n^{−1}, Stab_{N}(w)⟩

for any w ∈ W. Therefore Stab_{H}(w) is a cyclic extension of Stab_{N}(w).

Proof: Let w be an element of W. The group H acts on the set of N-orbits in W and so there exists a l = l(H, N) ∈ ℕ such that we can write wH as the disjoint union

wH = wN ∪ wNg ∪ ⋯ ∪ wNg^{l−1}.

We deduce that wNg^{l} = wN and hence there exists an n ∈ N such that wg^{l} = wn. So the group ⟨g^{l}n^{−1}, Stab_{N}(w)⟩ is contained in the stabilizer of w in H.

Conversely suppose that h is an element of Stab_{H}(w) and write h = g^{e}n̂ for a natural number e ∈ ℕ and n̂ ∈ N. Now it follows that

wN = (wh)N = (wg^{e}n̂)N = wNg^{e}

and so e = k · l by the choice of l. This implies that

g^{e}n̂ = g^{kl}n̂ = (g^{l}n^{−1}n)^{k}n̂ = (g^{l}n^{−1})^{k}n̄n̂

for some n̄ ∈ N. We deduce that n̄n̂ must be an element of Stab_{N}(w), because g^{e}n̂ and (g^{l}n^{−1})^{k} stabilize w. Thus h is contained in ⟨g^{l}n^{−1}, Stab_{N}(w)⟩. •

The following picture resumes the result of Lemma 3.1.3.

N  H := ⟨g, N⟩ Stab_{N}(w)  Stab_{H}(w) = ⟨g^{l}n^{−1}, Stab_{N}(w)⟩

The last lemma leads us to a method for the calculation of the index [H : N].

3.1.4 Proposition: Let N = N_{0} be a normal subgroup of G which acts faithfully on a set W and let B := {w_{1}, …, w_{k}} be base for N. Denote by H = H_{0} the cyclic extension ⟨g, N⟩, where g is an element of G\N. Let B̂ = {w_{1}, …, w_{k}, w_{k+1}, …, wk̂} be a base for H and define H_{i} := Stab_{H_{i−1}}(w_{i}) and N_{i} := Stab_{N_{i−1}}(w_{i}) for 1 ≤ i ≤ k̂. Then the iterated application of Lemma 3.1.3 to the stabilizer-chain H_{i} can be used to calculate the index

[H : N] = ∏_{i=1}^{k̂} l(H_{i−1}, N_{i−1}).

Proof: By repeated application of Lemma 3.1.3 there exists an l_{i} = l(H_{i−1}, N_{i−1}) ∈ ℕ, n_{i} ∈ N_{i−1} such that

H_{i} := ⟨g_{i}^{l_{i}}n_{i}^{−1}, N_{i}⟩

for 1 ≤ i ≤ k where g_{1} := g and g_{i} := g_{i−1}^{l_{i−1}}n_{i−1}^{−1} for 2 ≤ i ≤ k + 1.

Therefore H_{k} = ⟨g_{k}^{l_{k}}n_{k}^{−1}⟩ and so this group is cyclic. If H_{k} is non-trivial we

extend the set B = {w_{1}, …, w_{k}} to a set B̂ = {w_{1}, …, w_{k}, w_{k+1}, …, wk̂} such that Hk̂ is trivial. Then B̂ is a base for H. Recall that the number l_{i} := l(H_{i−1}, N_{i−1}) is defined to be the smallest natural number such that w_{i}g_{i}^{l_{i}} = w_{i} for k + 1 ≤ i ≤ k̂ where g_{i} = g_{i−1}^{l_{i−1}} for k + 2 ≤ i ≤ k̂. Now we claim that

[H : N] = ∏_{i=1}^{k̂} l_{i} = ∏_{i=1}^{k̂} l(H_{i−1}, N_{i−1}).

Since glk̂ ; k̂ ∈ Hk̂ = {1} we deduce that

1 = glk̂ ; k̂ = g_{k+1}^{∏k̂ ; i=k+1 l_{i}} = g^{∏k̂ ; i=1 l_{i}} ñ

for some ñ ∈ N. This implies that [H : N] divides ∏k̂ ; i=1 l_{i}.

Conversely, since l_{1} is the smallest number such that w_{1}N_{0}g_{1}^{l_{1}} = w_{1}N_{0}, we deduce that l_{1} divides [H : N], which is the order gN in G/N. The element g_{2}N = (g_{1}^{l_{1}}n_{1}^{−1})N = g_{1}^{l_{1}}N is of order [H : N]/l_{1} in G/N. Thus the number l_{2} must divide [H : N]/l_{1}, because l_{2} is the smallest number such that

w_{2}N_{1} = w_{2}N_{1}g_{2}^{l_{2}} and g_{2}^{[H:N]/l_{1}} ∈ N_{1}. By induction we follow that ∏k̂ ; i=1 l_{i}

divides the index [H : N], which shows that the equality holds. •

Lemma 3.1.1 demanded first to calculate the index [H : N] for completing the list of relative orders of the pc-sequence of the group H = ⟨g, N⟩. Second for a given element h ∈ H we should be able to determine a natural number e such that h = g^{e}n for an n ∈ N, for the calculation of the exponent vector of h. This can be realized by shifting through the orbits, which arise in the calculation of the index [H : N].

3.1.5 Lemma: Denote by N and H := ⟨g, N⟩ groups like in the Proposition 3.1.4. Suppose that the index [H : N] were calculated by the methods in Proposition 3.1.4 and that the arising orbits of the points w_{i} ∈ B̂ were stored including the corresponding transversals. Let h be an element of H. Then by shifting through the orbits w_{i}N_{i−1} a natural number e can be determined such that h = g^{e}n.

Proof: By induction we want to proof that for h_{i} ∈ H_{i−1} = ⟨g_{i}, N_{i−1}⟩ we can determine a natural number e_{i} such that h_{i} = g_{i}^{e_{i}} ñ_{i} where ñ_{i} ∈ N_{i−1}. For i = 1 this gives the wanted result. First let i = k̂ + 1. Then e_{i} = 0 because Hk̂ is trivial. Now we assume that i ∈ {1, …, k̂}. By construction we know that

w_{i}H_{i−1} = w_{i}N_{i−1} ∪ w_{i}N_{i−1}g_{i} ∪ ⋯ ∪ w_{i}N_{i−1}g_{i}^{l_{i}−1}.

Using the membership test for the orbits, we can determine a natural number s ∈ {0, …, l_{i} − 1} such that w_{i}N_{i−1}h_{i} = w_{i}N_{i−1}g_{i}^{s} and an n̄_{i} ∈ N_{i−1} such that h_{i+1} := h_{i}g_{i}^{−s}n̄_{i} is an element of H_{i} = Stab_{H_{i−1}}(w_{i}). By induction we suppose that we can calculate a natural number e_{i+1} such that h_{i+1} = g_{i+1}^{e_{i+1}} ñ_{i+1}. It follows that

h_{i+1} = g_{i+1}^{e_{i+1}} ñ_{i+1} = (g_{i}^{l_{i}}n_{i}^{−1})^{e_{i+1}} ñ_{i+1} = g_{i}^{l_{i}e_{i+1}} n̂_{i+1}

for some n̂_{i+1} ∈ N. We deduce that

h_{i} = h_{i+1}(n̄_{i}^{−1}g_{i}^{s}) = g_{i}^{l_{i}e_{i+1}} n̂_{i+1}(n̄_{i}^{−1}g_{i}^{s}) = g_{i}^{l_{i}e_{i+1}+s} ˆn̂

for some ˆ n̂ ∈ N. The element ˆ n̂ must be in N_{i−1} because h_{i} and g_{i} stabilize w_{i−1}. Therefore we can set e_{i} := l_{i}e_{i+1} + s. •

Now all the necessary elements for the extension of a constructive polycyclic pc-sequence of N are given. For the implementation we store the arising orbits w_{i}N_{i−1} under H and the corresponding transversals. Together with the relative orders this data structure includes all the necessary data for the determination of exponents vectors and a membership test.

3.2 Abelian Upwards Extensions

Let N be a normal subgroup of G and suppose that N is given by a constructive polycyclic sequence

N = (n_{1}, …, n_{k}).

Our aim is to compute an abelian upwards extension of N. This is a group H such that N ⊲H ⊴G and H/N is abelian. Assume that H is generated by {h_{1}, …, h_{l}} and N. Since H/N is abelian, all groups Ĥ with N ≤ Ĥ ≤ H are normal subgroups of H by the correspondence principle. Therefore

H = (h_{1}, …, h_{l}, n_{1}, …, n_{k})

is a polycyclic sequence for H. So the elements h_{1}, …, h_{l} can be used to extend the constructive polycyclic sequence of N step by step to a constructive pc-sequence of H.

Let g be an arbitrary element of G\N. We describe a method which tests if ⟨g, N⟩^{G} is an abelian upwards extension of N. If the result is positive, then it returns a generator list for H. If ⟨g, N⟩^{G} /N is not abelian, then it returns an element whose use we will discuss later.

The concept is the following: We regard Ē := {gN} as an incomplete generator list for ⟨g, N⟩^{G} /N. Now, we add conjugates under the action of the generators of G to Ē. We iterate this procedure. During the extension of the generator list, we test if all elements in Ē commute, i.e. [ε_{i}N, ε_{j}N] = N holds for all ε_{i}N, ε_{j}N ∈ Ē, which is equivalent to [ε_{i}, ε_{j}] ∈ N (ε_{i} and ε_{j} commute modulo N).

  AbelianUpwardsExtension( G, N, g )
  (01)    set E := {g}
  (02)    # close E under the conjugation action of G
  (03)    for every element ε in E do
  (04)        Ê:= { ε^{g} | g generator of G }
  (05)        if all elements in E ∪ Ê commute modulo N then
  (06)           set E := E ∪ Ê
  (07)        else
  (08)           return [ε_{i}, ε_{j}] such that [ε_{i}, ε_{j}] ∉ N
  (09)        end if
  (10)    end for
  (11)    return E

The algorithm terminates because G is a finite group, and so we can add only a finite number of elements to E. If this method returns a list E, then H := ⟨E, N⟩ is an abelian upwards extension of N. Namely H/N is non empty (because g ∉ N), H/N is abelian and H ⊴ G (because N ⊴ G and (H/N)^{G} = H/N ). If the algorithm returns an element ĝ, then ĝ = [g^{x}, g^{y}] ∉ N where x, y are words in the generators of G. Under the assumption that g is contained in the i-th term G^{(i)} of the derived series, we deduce that ĝ ∈ G^{(i+1)} because g^{x}, g^{y} ∈ G^{(i)}.

The element ĝ can be used for a recursive call with the input (G, N, ĝ). Since the length of the derived series of G ≤ GL(d, R) is bounded by d + 2 (see Theorem 3.3.1), a repetitive application of this algorithm can be made only a finite number of times.

We note that AbelianUpwardsExtension blows up the generator list E in a wasteful manner. In the sixth line we extend the generators list E by elements of Ê. But we do not check, if an element ê ∈ Ê is already contained in the group ⟨E, N⟩. We can respond to this problem, by using extensions of the constructive polycyclic sequence of N described in Section 3.1.

  AbelianUpwardsExtensionFaster( G, N, g )

set E := {g} set H := ⟨ g, N ⟩

    for every element ε in E do
       Ê:= { e^{g} | g generator of G }
       for every element ε̂ ∈ Ê do

         if ε̂ commutes with all elements in ε_{i} ∈ E modulo N then
            if not ε̂ ∈ H

set H := ⟨ ε̂, H ⟩

               (extension of a constructive pc-sequence, see 3.1)
               add ε̂ to E
            end if
         else
            return [ε̂, ε_{i}] such that [ε̂, ε_{i}] ∉ N
         end if
       end for
    end for
    return H

3.3 Constructive polycyclic sequences

Let G ≤ GL(d, R) be a finite matrix group where R is a ring. We present an algorithm which computes a constructive polycyclic sequence for G.

In the last section we remarked, that the function AbelianUpwardsExtensionFaster can be used for a recursive call. We specify this now. Let N be a normal subgroup of G for which a constructive pcsequence is already known. Let g be an element of G\N and let i ∈ ℕ ∪ {0} such that g is in the i-th term G^{(i)} of the derived series. Then the following method can be used to extend the constructive pc-sequence of N to the group ⟨g, N⟩.

  Extension( G, N, g, i )
    if i > bound for the derived length of G then
        return fail (G is not polycyclic)
    end if
    h := AbelianUpwardsExtensionFaster( G, N, g )
    if h is a group element then
        N_{new} := Extension( G, N, h, i + 1 )

        return Extension( G, N_{new}, g, i )

    else
        return h
    end if

In the second line of the last algorithm we need to know the derived length of G (or a least un upper bound for it). This is given by the following theorem.

3.3.1 Theorem: Let G be a polycyclic subgroup of GL(d, R). Then the length of the derived series of G is bounded by d + 2.

Proof: See [16]. •

Now a constructive pc-sequence for the matrix group G can be computed via the following method.

  ConstructivePcSequenceFinite( G )

set N := ⟨1⟩

    for every generator g of G do
        N := Extension( G, N, g, 0)
        if N = fail then
           return "G is not polycyclic"
        end if
    end for
    return N

CHAPTER 3. FINITE SOLVABLE MATRIX GROUPS  20

Algebraic number fields

Denote by 𝔽 an algebraic extension of the field ℚ and let A := {a_{1}, …, a_{n}} be a finite subset of 𝔽 \ {0}, where a_{i} ≠ 0 for i = 1, …, n. The aim of this chapter is to describe an algorithm to calculate a presentation for the abelian multiplicative group A := ⟨a_{1}, …, a_{n}⟩. Certainly A is polycyclic (for example, A is a polycyclic sequence). Therefore by Corollary 2.2.5 it is sufficient to determine a constructive polycyclic sequence for A. This is a polycyclic sequence, for which the relative orders are known and a efficient method is given to calculate exponent vectors (see Definition 2.1.5).

It will turn out, that the following set plays an important role.

4.0.2 Definition: Let E = {h_{1}, …, h_{l}} be a subset of an abelian group A. The relation lattice for E is

rl(E) := { (e_{1}, …, e_{l}) ∈ ℤ^{l} | h_{1}^{e_{1}} ⋯ h_{l}^{e_{l}} = 1 } .

Since A is an abelian group, the sum of two in elements in rl(E) is still in rl(E). Thus, the name lattice is justified.

An algorithm to determine rl(A) is presented in Section 4.1. Afterwards, in Section 4.2, we describe a method that uses the relation lattices to compute a constructive polycyclic sequence for the group A. In Section 4.3 we give an example application.

Before we start the description of the algorithms, we state three basic definitions of algebraic number theory. For further background see [23].

4.0.3 Definition: Let 𝔽 be a subfield of ℂ such that [𝔽 : ℚ] is finite. Then 𝔽 is called a number field or an algebraic extension of ℚ.

4.0.4 Definition: A complex number θ is said to be an algebraic integer, if the minimal polynomial f_{θ} of θ is in ℤ[X].

4.0.5 Definition: Let 𝔽 be a number field. The set of algebraic integers in 𝔽 is called the maximal order O of 𝔽. An element u ∈ O is called a unit, if u^{−1} is also contained in O. The set of all units in O is called the unit group of O and is denoted by U(O).

4.1 Computing relation lattices in number fields

Let A := {a_{1}, …, a_{n}} be a finite subset of a number field 𝔽 with a_{i} ≠ 0 for i = 1, …, n. Our aim is to determine the relation lattice rl(A). Recall that this is defined as

rl(a_{1}, …, a_{n}) := {(e_{1}, …, e_{n}) ∈ ℤ^{n}| ∏ a_{i}^{e_{i}} = 1} .

We proceed in three steps: First we calculate the unit relation lattice, defined as

url(a_{1}, …, a_{n}) := {(e_{1}, …, e_{n}) ∈ ℤ^{n}| ∏ a_{i}^{e_{i}} ∈ U(O)}

where U(O) is the group of units of the maximal order O of 𝔽. Every vector r = (r_{1}, …, r_{n}) in a basis B of url(A) gives rise to a unit

u(r) = a_{1}^{r_{1}} · a_{2}^{r_{2}} ⋯ a_{n}^{r_{n}} ∈ U(O).

Second, we will calculate the relation lattice of the elements

{ u(r) | r ∈ B } .

Third, using the achieved informations we will be able to calculate the relation lattice of the set A.

4.1.1 Calculating the unit relation lattice

Before we start to describe a method for the calculation of the unit relation lattice url(a_{1}, …, a_{n}), we want to show with the following example, how unique factorization can be used for the calculation of a relation lattice of elements in an abelian group.

4.1.1 Example: Suppose that three numbers 49, 21 and 9 are given and our task is to find the relation lattice rl(49, 21, 9), i.e. the set of all relation vectors (r_{1}, r_{2}, r_{3}) in ℤ^{3} such that

49^{r_{1}} · 21^{r_{2}} · 9^{r_{3}} = 1.

If we want to do this in a systematic way, we could do the following: Factorize these numbers and get

49 = 7^{2} , 21 = 7 · 3 , 9 = 3^{2}.

Now we can solve the problem for each of the arising factors. For example, a relation vector (r_{1}, r_{2}, r_{3}) of 49,21 and 9 must eliminate all the occurring powers of 7 and thus

7^{2r_{1}} · 7^{r_{2}} · 7^{0·r_{3}} = 1.

This gives rise to two conditions:

49  21  9
7  2 · r_{1} + 1 · r_{2} + 0 · r_{3} = 0
3  0 · r_{1} + 1 · r_{2} + 2 · r_{3} = 0

Solving these equations we find that rl(49, 21, 9) must be a subset of ℤ(1, −2, 1). Conversely every element of ℤ(1, −2, 1) lies in rl(49, 21, 9) and so we have

rl(49, 21, 9) = { z(1, −2, 1) | z ∈ ℤ }.

Unfortunately we are not always able to determine a unique factorization of the elements a_{i} ∈ 𝔽 into irreducible factors. For example in the ring of integers of ℚ(\sqrt{−5}) we have

6 = 2 · 3 = (1 + \sqrt{−5})(1 − \sqrt{−5})

where 2, 3, (1 + \sqrt{−5}) are (1 − \sqrt{−5}) are irreducible. So in the following we use fractional ideals and describe a method to factorize expressions like (a_{i}) = a_{i}O. First we remind the reader of some results of their arithmetic structure. A more detailed description of fractional ideals can be found in [23] Chapter 5.

4.1.2 Definition: Let 𝔽 be a extension field of ℚ and O its maximal order. An O-submodule 𝔞 of 𝔽 is called a fractional ideal of O, if there exists some non-zero c ∈ O such that c𝔞 ⊂ O.

4.1.3 Lemma: The fractional ideals of O are subsets of 𝔽 of the form c^{−1}𝔟, where 𝔟 is an ideal of O and c is a non-zero element of O.

Proof: Suppose that 𝔞 is a fractional ideal of O and let c ∈ O, c ≠ 0 such that c𝔞 ⊂ O. Then the set 𝔟 := c𝔞 must be an ideal of O and we deduce that 𝔞 = c^{−1}𝔟. •

As it turns out, in an algebraic number field, such fractional ideals can be uniquely factorized into the product of prime ideals.

4.1.4 Theorem: The non-zero fractional ideals of O form an abelian group under multiplication, where the product of two fractional ideals 𝔞_{1}, 𝔞_{2} is

𝔞_{1}𝔞_{2} = (c_{1}^{−1}𝔟_{1})(c_{2}^{−1}𝔟_{2}) = (c_{1}c_{2})^{−1}𝔟_{1}𝔟_{2}

and the inverse of a fractional ideal 𝔞 is defined as 𝔞^{−1} := { x ∈ 𝔽 | x𝔞 ⊂ O }. The identity of this group is O.

Proof: [23] Theorem 5.5. •

Further we need to know what are the prime elements in this arithmetical structure.

4.1.5 Definition: Let R be a ring. An ideal 𝔭 of R is called prime if for any two ideals 𝔞, 𝔟

𝔞𝔟 ⊂ 𝔭 implies 𝔞 ⊂ 𝔭 or 𝔟 ⊂ 𝔭.

4.1.6 Remark: For the motivation of the last definition regard the ring R = ℤ. Here an element p is called prime if from p|ab we can always deduce that p|a or p|b for all a, b ∈ ℤ. Then the element p is prime if and only if pℤ is a prime ideal. The condition 𝔞𝔟 ⊂ 𝔭 corresponds to p | ab.)

4.1.7 Theorem: Every non-zero fractional ideal 𝔞 of O can be written uniquely up to the order of the factors as a finite product of prime ideals of O:

𝔞 = ∏ 𝔭_{i}^{e_{i}} e_{i} ∈ ℤ

Proof: See [23] Theorem 5.6. and page 110. •

There are algorithms available for determining such a factorization (see [4] Section 4.8. and [18] Chapter 7). So we are able to factorize a given fractional ideal into a unique product of prime ideals.

4.1.8 Lemma: Let 𝔽 be a number field and denote by O its maximal order. If a is a non-zero element in 𝔽, then aO is a fractional ideal.

Proof: For a given number field 𝔽, there always exists a complex number θ such that 𝔽 = ℚ(θ). Every element a in 𝔽 can be written as a ℚ-linear combinations of powers of θ. So there exists an m ∈ ℤ ⊂ O such that m · a ∈ ℤ[θ] ⊂ O. Therefore the O-module aO is a fractional ideal. •

In the example 4.1.1 we found relations among the numbers 49, 21 and 9 via the factorization in prime powers. Now we can solve the problem of finding the relations among the fractional ideals a_{i}O via the factorization into prime ideals 𝔭_{1}, …, 𝔭_{l}.

4.1.9 Definition: Let I be a non-zero fractional ideal of O and write

I = ∏_{j=1}^{l} 𝔭_{j}^{e_{j}}

The quantity ν_{𝔭_{j}}(I) := e_{j} is called the 𝔭_{j}-adic valuation of I.

The 𝔭-adic valuation satisfies the property ν_{𝔭}(IJ) = ν_{𝔭}(I) + ν_{𝔭}(J).

Recall that A := {a_{1}, …, a_{n}} is a finite subset of a number field 𝔽 with a_{i} ≠ 0 for i = 1, …, n. Let

(a_{i}) = a_{i}O = ∏_{j=1}^{l} 𝔭_{j}^{e_{ij}}.

We construct the matrix (ν_{𝔭_{j}}(a_{i}O))_{ji}

𝔭_{1} ; 𝔭_{2} ; ⋮ ; 𝔭_{l}  \begin{matrix}(a_{1}) & (a_{2}) & … & (a_{n}) \\ ( & \begin{matrix}e_{11} & & & e_{12} & & & … & & & e_{1n} \\ e_{21} & & & e_{22} & & & … & & & e_{2n} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ e_{l1} & & & e_{l2} & & & … & & & e_{ln} \end{matrix} & ) \end{matrix}

where 𝔭_{1}, …, 𝔭_{l} are the prime ideals appearing in the factorization of all the fractional ideals a_{i}O and ν_{𝔭_{j}}(a_{i}O) is the 𝔭_{j}-adic valuation of a_{i}O.

4.1.10 Proposition:

Let 𝔽 be an extension field of ℚ and a_{1}, …, a_{n} be elements in 𝔽\{0}.

1. Denote by N ≤ ℤ^{n} the integral nullspace N of the matrix (ν_{𝔭_{j}}(a_{i}))_{ji}. Then N = rl(a_{1}O, …, a_{n}O).

2. The relation lattice rl(a_{1}O, …, a_{n}O) is equal to the unit relation lattice url(a_{1}, …, a_{n}) := {(e_{1}, …, e_{n}) ∈ ℤ^{n}| ∏ a_{i}^{e_{i}} ∈ U(O)}.

Proof:

1. Let r = (r_{1}, …, r_{n}) be a vector in ℤ^{n}. Then

(r_{1}, …, r_{n}) ∈ rl(a_{1}O, …, a_{n}O)
⇔ (a_{1})^{r_{1}} ⋯ (a_{n})^{r_{n}} = O
⇔ (∏_{j=1}^{l} 𝔭_{j}^{ν_{𝔭_{j}} (a_{1}O)})^{r_{1}} ⋯ (∏_{j=1}^{l} 𝔭_{j}^{ν_{𝔭_{j}} (a_{n}O)})^{r_{n}} = O
⇔ 𝔭_{1}^{∑_{i=1}^{n} r_{i}ν_{𝔭_{1}}(a_{i}O)} ⋯ 𝔭_{l}^{∑_{i=1}^{n} r_{i}ν_{𝔭_{l}}(a_{i}O)} = O
⇔ ∑_{i=1}^{n} r_{i}ν_{𝔭_{j}}(a_{i}O) = 0 for j = 1, …, l  by Theorem 4.1.7
⇔ (ν_{𝔭_{j}}(a_{i}O))_{ji} · (r_{1}, …, r_{n})^{t} = 0

2. Let r = (r_{1}, …, r_{n}) be a vector in ℤ^{n}. Then

(r_{1}, …, r_{n}) ∈ rl(a_{1}O, …, a_{n}O)
⇔ (a_{1})^{r_{1}} ⋯ (a_{n})^{r_{n}} = O
⇔ ∏_{i=1}^{n} a_{i}^{r_{i}}O = O

⇔ ∏_{i=1}^{n} a_{i}^{r_{i}} ∈ U(O)
⇔ (r_{1}, …, r_{n}) ∈ rul(a_{1}, …, a_{n})
•

4.1.2 Calculating the relation lattice in U(O)

Let u_{1}, …, u_{m} be units of the maximal order O. Our task is to find the relations between these units. Again it is necessary to work in an unique factorization domain whose existence is guaranteed by the following theorem of Dirichlet.

4.1.11 Theorem: Every unit u of an order over ℤ can be written uniquely as

u = ζ^{f_{0}} · ε_{1}^{f_{1}} · ε_{2}^{f_{2}} ⋯ ε_{r}^{f_{r}}

where ζ is the generator of the torsion subgroup of O and ε_{1}, …, ε_{r} are the fundamental units of the maximal order.

Proof: [23] Appendix B. •

There are algorithms available for computing the torsion unit and the fundamental units (see [18] Chapter 6). Now we proceed as in Section 4.1.1.

4.1.12 Lemma: Let u_{1}, …, u_{m} ∈ U(O). For i = 1, …, m write

u_{i} = ζ^{f_{0i}} ∏_{j=1}^{r} ε_{j}^{f_{ji}}

and define o_{ζ} to be the order of ζ. Denote by R_{1} ≤ ℤ^{m} the integral nullspace of the matrix

ε_{1} ; ⋮ ; ε_{r}  \begin{matrix}u_{1} & u_{2} & … & u_{m} \\ ( & \begin{matrix}f_{11} & & f_{12} & & … & & f_{1m} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ f_{r1} & & f_{r2} & & … & & f_{lm} \end{matrix} & ) \end{matrix}

and let R_{2} ≤ ℤ^{m} such that R_{2}/(o_{ζ}ℤ)^{m} is the nullspace of the matrix

ζ  \begin{matrix}u_{1} & u_{2} & … & u_{m} \\ ( & f_{01} f_{02} … f_{0m} & ) \end{matrix}

in ℤ^{m}/(o_{ζ}ℤ)^{m}. Then rl(u_{1}, …, u_{m}) = R_{1} ∩ R_{2}.

Proof: Let r = (r_{1}, …, r_{m}) be a vector in ℤ^{m}. Then

(r_{1}, …, r_{m}) ∈ rl(u_{1}, …, u_{m})
⇔ u_{1}^{r_{1}} ⋯ u_{m}^{r_{m}} = 1
⇔ (ζ^{f_{01}} ∏_{j=1}^{r} ε_{j}^{f_{j1}})^{r_{1}} ⋯ (ζ^{f_{0m}} ∏_{j=1}^{r} ε_{j}^{f_{jm}})^{r_{m}} = 1

⇔ ζ^{∑_{i=1}^{m} f_{0i}r_{i}} ∏_{j=1}^{r} ε_{j}^{∑_{i=1}^{m} f_{ji}r_{i}} = 1

⇔ ∑_{i=1}^{m} f_{0i}r_{i} = 0 mod o_{ζ} and

∑_{i=1}^{m} f_{ji}r_{i} = 0 for j = 1, …, r by Theorem 4.1.11
⇔ (r_{1}, …, r_{m}) ∈ R_{1} ∩ R_{2}
•

4.1.13 Lemma: Let u_{1}, …, u_{m} ∈ U(O). If the multiplicative group

⟨u_{1}, …, u_{m}⟩

is torsion-free then R_{1} ⊂ R_{2}, where R_{1}, R_{2} are defined as in Lemma 4.1.12.

Proof: Suppose that R_{1} ⊄ R_{2}. Then there is an element (r_{1}, …, r_{m}) ∈ R_{1} \ R_{2}. We deduce that

∏_{i=1}^{m} u_{i}^{r_{i}} = ∏_{i=1}^{m}(ζ^{f_{0i}} ∏_{j=1}^{r} ε_{j}^{f_{ji}})^{r_{i}} = \underbrace{ζ^{∑_{i=1}^{m} f_{0i}r_{i}}}_{≠1 since r∉R_{2}} \underbrace{∏_{j=1}^{r} ε_{j}^{∑_{i=1}^{m} f_{ji}r_{i}}}_{=1 since r∈R_{1}} ≠ 1.

This implies that ∏_{i=1}^{m} u_{i}^{r_{i}} would have finite non-trivial order, which is impossible. •

4.1.3 Summary

Let a_{i}, …, a_{n} be arbitrary elements of an extension field of ℚ. Now we are in the position to describe a method to calculate the relation lattice

rl(a_{1}, …, a_{n}) := {(e_{1}, …, e_{n}) ∈ ℤ^{n}| ∏ a_{i}^{e_{i}} = 1}.

Suppose that url(a_{1}, …, a_{n}) ≤ ℤ^{n} has dimension m in ℤ^{n}. Then compute a basis r_{1}, …, r_{m} ∈ ℤ^{n} for url(a_{1}, …, a_{n}) ≤ ℤ^{n} and consider the matrix

R := ( \begin{matrix}r_{1} \\ … \\ r_{m} \end{matrix} ) .

Recall that for r ∈ url(a_{1}, …, a_{n}) we defined the unit u(r) as ∏_{j=1}^{n} a_{i}^{r_{j}}. Let s_{1}, …, s_{o} be a basis for rl (u(r_{1}), …, u(r_{m})) ≤ ℤ^{m} and define the matrix

S := ( \begin{matrix}s_{1} \\ … \\ s_{o} \end{matrix} ) .

4.1.14 Lemma: A generating set for the relation lattice rl(a_{1}, …, a_{n}) is given by the rows of the matrix

T := S · R

Proof: Let t be a row of the matrix T. Then we can write t = s · R where s is a row of the matrix S. This implies

a_{1}^{t_{1}} · a_{2}^{t_{2}} ⋯ a_{n}^{t_{n}}
= a_{1}^{∑_{j=1}^{m} s_{j}r_{j1}} · a_{2}^{∑_{j=1}^{m} s_{j}r_{j2}} ⋯ a_{n}^{∑_{j=1}^{m} s_{j}r_{jn}}
= (∏_{i=1}^{n} a_{i}^{r_{1i}})^{s_{1}} · (∏_{i=1}^{n} a_{i}^{r_{2i}})^{s_{2}} ⋯ (∏_{i=1}^{n} a_{i}^{r_{mi}})^{s_{m}}
= u(r_{1})^{s_{1}} · u(r_{2})^{s_{2}} ⋯ u(r_{m})^{s_{m}}
= 1

and so t is an element of rl(a_{1}, …, a_{n}).

Vice versa assume, that t is an element of rl(a_{1}, …, a_{n}). Then t must be in url(a_{1}, …, a_{n}) and is therefore a ℤ-linear combination of the rows of R, and so t = α · R with α ∈ ℤ^{m}. We deduce, that α must be in the subspace generated by the rows of S, because u(r_{1})^{α_{1}} ⋯ u(r_{m})^{α_{m}} = 1. This implies, that t is a ℤ-linear combination of the rows of T. •

4.2 Constructive polycyclic sequences

Let A be a finitely generated abelian group and suppose that a method is given to calculate the relation lattice rl(E) for an arbitrary finite subset E of A. We want to determine a constructive polycyclic sequence for A.

4.2.1 Lemma: Let A := {a_{1}, …, a_{n}} be an arbitrary generating set for the abelian group A with relation lattice rl(A). Write the vectors of a generating set of rl(A) row by row into a matrix RL. Applying the Smith normal form algorithm to RL we can determine a minimal generating set G for A and calculate the relative orders of G viewed as a polycyclic sequence.

Proof: Suppose that RL ∈ ℤ^{m×n}. We can determine row and column transformations R and C such that R · RL · C is equal to a matrix S ∈ ℤ^{m×n} in Smith normal form. That is, there is some k > 0 such that the entry s_{i} := S_{ii} is positive for i = 1, …, k, S has no other nonzero entries and s_{i} divides s_{i+1} for i = 1, …, k − 1.

Denote by j the smallest natural number such that s_{j} ≠ 1. The matrix C can be interpreted as base change matrix of ℤ^{n} and the multiplication from the left with the matrix R just changes the generating set of the subspace generated by the rows of RL · C. We deduce, that the rows of S are a generating set of rl(A) in coordinate vectors corresponding to the new basis. Then the rows c̄_{j}, …, c̄_{n} ∈ ℤ^{n} between the j-th and the n-th row of C^{−1} give rise to a minimal generating set c̄_{j} + rl(A), …, c̄_{n} + rl(A) for ℤ^{n}/rl(A) (as the preimage of the j-th until the n-th unit vector in the new basis). The elements c̄_{j} + rl(A), …, c̄_{n} + rl(A) have the orders (s_{j}, …, s_{k}, 0, …, 0). They give rise to a minimal generating set

G := { ∏_{i=1}^{n} ac̄_{ki} ; i | k = j, …, n }

for A with relative orders (s_{j}, …, s_{k}, 0, …, 0).

For further background on finitely generated abelian groups and the Smith normal form see [21] Section 8.3. •

It rests to describe a method to compute exponent vectors corresponding to a given polycyclic sequence.

4.2.2 Lemma: Let A := {a_{1}, …, a_{n}} be a minimal generating set for an abelian group A and let a be a non-trivial element of A. Then the exponent vector of the element a corresponding to A can be calculated in determining the relation lattice rl({a} ∪ A).

Proof: Let B be a basis of rl({a}∪A) written row by row in a matrix. Bring B in triangular form (via integer operation) and let r be the first row of the transformed matrix. We deduce that r_{1} is equal to 1 because A is a generating set for A. Then the exponent vector can be read off as

exp_{A}(a) = −(r_{2}, …, r_{n+1}).
•

4.3 Example

The methods described in this chapter were implemented in GAP [24] and are part of the GAP-package ’Alnuth’ [7]. For the fundamental algorithms as the determination of the maximal order, the unit group and the ideal valuation we used the computer algebra system KANT [10]. The GAP-package ’Alnuth’ provides an interface from GAP to KANT.

Let θ ∈ ℂ be a root of the irreducible polynomial

f := x^{4} − 4x^{3} − 28x^{2} + 64x + 16.

Denote by 𝔽 the number field ℚ(θ) and consider the following elements in 𝔽

a_{1} : = 4/3 − 2/3θ − 1θ^{2} − 1/3θ^{3}
a_{2} : = −1/3 − 1θ + 2θ^{2} + 2θ^{3}
a_{3} : = 5/3 − 1θ − 1/2θ^{2} − 1/2θ^{3}
a_{4} : = −1/4 − 3θ^{2} − 1/2θ^{3}
a_{5} : = −1/2θ^{3}
a_{6} : = 129140/3 + 178538θ − 146945/3θ^{2} − 53893/3θ^{3}
a_{7} : = 7843/9 + 10748/3θ − 2243/2θ^{2} − 320θ^{3}.

We want to calculate a presentation for the multiplicative group

A := ⟨a_{1}, …, a_{7}⟩ .

The calculation of the relation lattice

rl(a_{1}, …, a_{7}) := {(e_{1}, …, e_{7}) ∈ ℤ^{7}| ∏_{i=1}^{7} a_{i}^{e_{i}} = 1}.

costed about 10 milliseconds with a Pentium III processor with 850 mhz under the system Linux. The relation lattice is equal to

⟨ (1, 0, 0, 1, 1, −1, 0), (0, 1, 1, 0, 0, 0, −1) ⟩ ≤ ℤ^{7}.

The minimal generating set for A calculated by the algorithm in Lemma 4.2.1 is

(a_{2}, a_{4}, a_{5}, a_{6}, a_{7})

with the relative orders (0, …, 0). This is a constructive polycyclic sequence for A. By Theorem 2.2.2, the group A is isomorphic to the polycyclic presented group

X := ⟨ x_{1}, …, x_{5} | x_{i}^{x_{j}} = x_{i}, x_{i}^{x_{j}^{−1}} = x_{i} for 1 ≤ i < j ≤ 5 ⟩
= ⟨ x_{1}, …, x_{5} | [x_{i}, x_{j}] = 1 for 1 ≤ i < j ≤ 5 ⟩ .

In total the computation of this polycyclic presented group costed about 20 milliseconds.

Unipotent groups

Let U be a subgroup of GL(d, ℚ). Recall that an element u ∈ U is called unipotent if there exists a natural number m ∈ ℕ such that

(u − 1)^{m} = 0,

and that the group U is called unipotent, if every element in U is unipotent.

We will see, that every finitely generated unipotent matrix group U ≤ GL(d, ℚ) is polycyclic. It is our goal to determine a polycyclic presentation of U. According to Corollary 2.2.5, it is sufficient to calculate a constructive polycyclic sequence for U to get a polycyclic presentation. Denote by UT (d, ℤ) the group of all upper unitriangular matrices in GL(d, ℤ), i.e. every element in UT (d, ℤ) has the form

( 1 ∗ … ∗ ; 1 ∗ … ∗ ; ⋮ ; ... ∗ ; 1 ) .

In the next section we describe a method to determine a matrix g such that U^{g} ≤ UT (d, ℤ), if U is finitely generated. Then in section 5.2 we show how to compute a constructive polycyclic sequence for any subgroup of UT (d, ℤ).

5.1 Conjugation

Let U := ⟨u_{1}, …, u_{n}⟩ be an unipotent rational matrix group. In this section we determine a matrix g ∈ GL(d, ℚ) such that U^{g} is a subgroup of UT (d, ℤ).

5.1.1 Definition: Let V be a vector space over a field 𝔽. Regard a chain of subspaces in V

… V_{i−1} ⊂ V_{i} ⊂ V_{i+1} …

Then the chain (V_{i}) is called a flag, if for all i we have V_{i} ≠ V_{i+1}.

Denote by u an unipotent element of GL(d, ℚ). Let

⟨b_{d}⟩ ⊂ ⟨b_{d−1}, b_{d}⟩ ⊂ … ⟨b_{1}, …, b_{d}⟩

be a flag of ℚ^{d}. It is said to be a flag for u if it has the property that

b_{i}u = b_{i} + ∑_{j=i+1}^{d} β_{ij}b_{j}  (∗)

for i = 1, …, d and an unitriangular matrix β ∈ UT (d, ℚ). This is equivalent with the property that b_{i} + ⟨b_{i+1}, …, b_{d}⟩ is a eigenvector to the eigenvalue 1 for u in ℚ^{d}/ ⟨b_{i+1}, …, b_{d}⟩.

5.1.2 Lemma: Let u be a matrix in GL(d, ℚ). Then u is unipotent if and only if all eigenvalues of u are equal to 1.

Proof: If all the eigenvalues of u are equal to 1, we deduce by conjugation to the Jordan-Normal form that u is unipotent. Conversely denote by λ an arbitrary eigenvalue of u with eigenvector x. It follows that

x(u − 1)^{n} = (λ − 1)^{n}x

for every number n ∈ ℕ. Since u is unipotent, there is an m ∈ ℕ such that (u − 1)^{m} = 0. We deduce that (λ − 1)^{m}x = 0 and thus λ = 1. •

5.1.3 Lemma: Denote by u an unipotent element of GL(d, ℚ). Then there exists a flag for u with the property (∗). If {b_{1}, …, b_{d}} is the corresponding basis of this flag, then we define the matrix

b := ( b_{1} ; ⋮ ; b_{d} ) .

Then u^{b^{−1}} is an element of UT (d, ℚ).

Proof: Let m be the smallest natural number such that (u − 1)^{m} = 0. Then there exists a non-trivial vector x ∈ ℚ^{d} such that

x(u − 1)^{m−1} ≠ 0.

Therefore, b_{d} := x(u − 1)^{m−1} is an eigenvector of u with eigenvalue 1. Now induce the action of u to ℚ^{d}/ ⟨b_{d}⟩. Since the induced action is still unipotent we find by induction a flag for u with the property (∗). Let {b_{1}, …, b_{d}} be a basis for this flag. We deduce that there exists an β ∈ UT (d, ℚ) such that bu = βb. It follows that u^{b^{−1}} ∈ UT (d, ℚ). •

So we are able to bring every unipotent matrix in GL(d, ℚ) in unitriangulized form. The next theorem shows, that this is also possible for an unipotent group.

5.1.4 Theorem: Let U be an unipotent subgroup of GL(d, ℚ). Then there exists an element g ∈ GL(d, ℚ) such that U^{g} ≤ UT (d, ℚ).

Proof: See [25] Corollary 1.21 or [19] 8.1.10. •

Let U := ⟨u_{1}, …, u_{n}⟩ be an unipotent subgroup of GL(d, ℚ). Now we construct an element b ∈ GL(d, ℚ) with the property that U^{b^{−1}} ≤ UT (d, ℚ). This is, we calculate a flag with the property (∗) for all generators of U. Define the matrix

û := ( u_{1} − 1 u_{2} − 1 ⋯ u_{n} − 1 ) .

Since U is conjugated to a subgroup of UT (d, ℚ), there exists a non-trivial vector x ∈ ℚ^{d} such that xû = 0. We calculate such a vector x and set b_{d} := x. Now we induce the action of U to ℚ^{d}/ ⟨b_{d}⟩ and get a group Ũ. The group Ũ is still unipotent and so we can proceed by induction. In this way we find the vectors b_{i} for i = 1, …, d with the property (∗) for all generators of U. As in Lemma 5.1.3, we deduce that the matrix

b := ( b_{1} ; ⋮ ; b_{d} )^{.}

has the property that U^{b^{−1}} ≤ UT (d, ℚ).

Finally we have to find a matrix which conjugates a subgroup of UT (d, ℚ) to a subgroup of UT (d, ℤ).

For a number x = \frac{a}{b} ∈ ℚ we denote by 𝔡(x) = b the denominator of x and for the numbers x_{1}, …, x_{k} ∈ ℤ we define lcm(x_{1}, …, x_{k}) to be the least common multiple of x_{1}, …, x_{k}.

5.1.5 Lemma: Let u be an element of UT (d, ℚ). Define

c := ( \begin{matrix}c_{1} \\ & . & . & . \\ & & & & c_{d} \end{matrix} ) ∈ GL(d, ℤ)

to be the diagonal matrix with the entries

c_{1} := 1
c_{i} := lcm(𝔡(c_{1}^{−1}u_{1i}), …, 𝔡(c_{i−1}^{−1}u_{(i−1)i})).

Then u^{c} ∈ UT (d, ℤ).

Proof: Obviously we have that (u^{c})_{ij} = c_{i}^{−1}u_{ij}c_{j}. We deduce that (u^{c})_{ij} = 0 for i > j and that (u^{c})_{ii} = 1 for i = 1, …, d. For j > i we see that

c_{i}^{−1}u_{ij}c_{j} = (c_{i}^{−1}u_{ij})c_{j} = (c_{i}^{−1}u_{ij})lcm(𝔡(c_{1}^{−1}u_{1j}), …, 𝔡(c_{j−1}^{−1}u_{(j−1)j})) ∈ ℤ

and thus u^{c} ∈ UT (d, ℤ). •

5.1.6 Remark: There are easier ways to find a matrix c such that u^{c} ∈ UT (d, ℤ). For example we could choose c := diag(l^{0}, l^{1}, …, l^{d−1}), where l is the least common multiple of the denominators of all entries in u. The approach of Lemma 5.1.5 has the advantage, that it produces a matrix with smaller integer entries.

5.1.7 Corollary: Let U := ⟨u_{1}, …, u_{n}⟩ be a subgroup of UT (d, ℚ). Define

c := ( \begin{matrix}c_{1} \\ & . & . & . \\ & & & & c_{d} \end{matrix} ) ∈ GL(d, ℤ)

to be the diagonal matrix with the entries

c_{1} := 1
c_{i} := lcm( { 𝔡(c_{j}^{−1}(u_{k})_{ji}) | 1 ≤ j ≤ i − 1, 1 ≤ k ≤ n } ).

Then U^{c} ≤ UT (d, ℤ).

CHAPTER 5. UNIPOTENT GROUPS  37

5.1.8 Example: Let U be the unipotent group generated by the matrices

u_{1} := ( \begin{matrix}7/3 & 7/3 & 0 & 8/3 \\ −11/9 & −10/9 & −2/9 & −14/9 \\ 1/12 & −1/6 & 1/2 & −5/6 \\ 37/36 & 37/18 & 17/18 & 41/18 \end{matrix} ) , u_{2} := ( \begin{matrix}1/3 & −2/3 & 1 & −1/3 \\ 7/9 & 7/3 & −1/9 & 5/3 \\ −2/3 & −5/3 & 1/4 & −37/12 \\ −2/9 & −1/3 & −1/36 & 13/12 \end{matrix} ) .

First we conjugate U to a subgroup of UT (d, ℚ). The matrix

b := ( \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 0 & 1 & −3 \\ 0 & 1 & 1 & 5 \\ 1 & 2 & 1 & 1 \end{matrix} )

contains row vectors which are a basis of a flag for u_{1}, u_{2} with the property (∗). By conjugation with b^{−1} we get

u_{1}^{b^{−1}} = ( \begin{matrix}1 & −1/12 & 0 & 37/36 \\ 0 & 1 & −1/3 & −3 \\ 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 1 \end{matrix} ) , u_{2}^{b^{−1}} = ( \begin{matrix}1 & 1/12 & 1/9 & −2/9 \\ 0 & 1 & −2/3 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix} ) .

According to Corollary 5.1.7 we calculate

c_{1} := 1
c_{2} := lcm( 𝔡(−1/12), 𝔡(1/12) ) = 12
c_{3} := lcm( 𝔡(0), 𝔡(1/9), 𝔡(c_{2}^{−1}(−1/3)), 𝔡(c_{2}^{−1}(−2/3)) ) = 36
c_{4} := lcm( 𝔡(37/36), 𝔡(−2/9), 𝔡(c_{2}^{−1}(−3)), 𝔡(c_{2}^{−1}0), 𝔡(c_{3}^{−1}4), 𝔡(c_{3}^{−1}(−1)) ) = 36.

Therefore we define

c := ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 12 & 0 & 0 \\ 0 & 0 & 36 & 0 \\ 0 & 0 & 0 & 36 \end{matrix} ) ,

set g := b^{−1}c and get

u_{1}^{g} = ( \begin{matrix}1 & −1 & 0 & 37 \\ 0 & 1 & −1 & 9 \\ 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 1 \end{matrix} ) , u_{2}^{g} = ( \begin{matrix}1 & 1 & 4 & −8 \\ 0 & 1 & −2 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix} ) .

5.2 Constructive pc-sequences

Let U be a subgroup of UT (d, ℤ). In this section we determine a constructive pc-sequence for U. First we show, that the group of all unitriangular matrices over the integers UT (d, ℤ) is polycyclic and give a constructive pcsequence for UT (d, ℤ). Second we induce the constructive pc-sequence of UT (d, ℤ) to a constructive pc-sequence of U. The following example gives a good intuition for the structure of UT (d, ℤ).

5.2.1 Example: Denote by a, b two elements in UT (4, ℤ). We verify that

ab = ( \begin{matrix}1 & a_{12} & ∗ & ∗ \\ & 1 & a_{23} & ∗ \\ & & 1 & a_{34} \\ & & & 1 \end{matrix} ) . ( \begin{matrix}1 & b_{12} & ∗ & ∗ \\ & 1 & b_{23} & ∗ \\ & & 1 & b_{34} \\ & & & 1 \end{matrix} )

= ( \begin{matrix}1 & a_{12} + b_{12} & ∗ & ∗ \\ & 1 & a_{23} + b_{23} & ∗ \\ & & 1 & a_{34} + b_{34} \\ & & & 1 \end{matrix} )

So by matrix calculation, we see that the projection on the first subdiagonal

ϕ : UT (d, ℤ) → ℤ^{d−1}
a ↦ ( a_{12}, a_{23}, …, a_{d−1,d} )

is a homomorphism.

5.2.2 Lemma: The group of all unitriangular matrices over the integers UT (d, ℤ) is polycyclic. Therefore all subgroups of UT (d, ℤ) are polycyclic.

Proof: For k ∈ {1, …, k} we define

U_{k} := {u ∈ UT (d, ℤ) | u_{ij} = 0 if i ≠ j and j − i < k }.

It is easy to see that U_{k} is a subgroup of UT (d, ℤ) for k = 1, …, d.

We proof by induction that U_{k} ≤ UT (d, ℤ) is polycyclic. For k = 1 this gives the wanted result. Certainly U_{d} = {1} is polycyclic. Now we assume that k < d and that U_{k+1} is polycyclic. Define

ϕ_{k} : U_{k} → ℤ^{d−k}
u ↦ ( u_{1,1+k}, u_{2,2+k}, …, u_{d−k,k} )

to be the projection on the k-th subdiagonal. The kernel of ϕ_{k} is equal to U_{k+1} and thus polycyclic by hypothesis. Further Im ϕ_{k} = ℤ^{d−k} is polycyclic. Therefore U_{k} is polycyclic.

We deduce that UT (d, ℤ) is polycyclic. Subgroups of polycyclic groups are polycyclic (see [21] Section 9.3). •

5.2.3 Corollary: Let U := ⟨u_{1}, …, u_{n}⟩ be an unipotent subgroup of GL(d, ℚ). Then the group U is polycyclic.

Proof: In Section 5.1 we showed, that there exists a g ∈ GL(d, ℚ) such that U^{g} ≤ UT (d, ℤ). Thus U is polycyclic. •

In the following example we outline a constructive polycyclic sequence for UT (4, ℤ).

5.2.4 Example: It is easy to verify that the matrices

a_{1} = ( \begin{matrix}1 & 1 & 0 & 0 \\ & 1 & 0 & 0 \\ & & 1 & 0 \\ & & & 1 \end{matrix} ) , a_{2} = ( \begin{matrix}1 & 0 & 0 & 0 \\ & 1 & 1 & 0 \\ & & 1 & 0 \\ & & & 1 \end{matrix} ) , a_{3} = ( \begin{matrix}1 & 0 & 0 & 0 \\ & 1 & 0 & 0 \\ & & 1 & 1 \\ & & & 1 \end{matrix} ) ,

a_{4} = ( \begin{matrix}1 & 0 & 1 & 0 \\ & 1 & 0 & 0 \\ & & 1 & 0 \\ & & & 1 \end{matrix} ) , a_{5} = ( \begin{matrix}1 & 0 & 0 & 0 \\ & 1 & 0 & 1 \\ & & 1 & 0 \\ & & & 1 \end{matrix} ) , a_{6} = ( \begin{matrix}1 & 0 & 0 & 1 \\ & 1 & 0 & 0 \\ & & 1 & 0 \\ & & & 1 \end{matrix} )

are a generating set for UT (4, ℤ). Further they form a polycyclic sequence for UT (4, ℤ). We determine the exponent vector of an element x ∈ UT (4, ℤ) corresponding to the pc-sequence A := (a_{1}, …, a_{6}). For example, we regard the matrix

x := ( \begin{matrix}1 & 3 & −1 & 1 \\ & 1 & 5 & 4 \\ & & 1 & −2 \\ & & & 1 \end{matrix} ) .

The entries on the first subdiagonal are α_{1} = 3, α_{2} = 5 and α_{3} = −2. Therefore (a_{1}^{3}a_{2}^{5}a_{3}^{−2})^{−1}x has only zeros on the first subdiagonal and is equal to

( \begin{matrix}1 & 0 & −16 & −11 \\ 0 & 1 & 0 & 14 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) .

Now on the second subdiagonal we find the entries α_{4} = −16 and α_{5} = 14. So by multiplication from the left with (a_{4}^{−16}a_{5}^{14})^{−1} we get

( \begin{matrix}1 & 0 & 0 & −11 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) .

A further multiplication from the left with (a_{6}^{−11})^{−1} yields the identity matrix. We deduce that

x = a_{1}^{3}a_{2}^{5}a_{3}^{−2}a_{4}^{−16}a_{5}^{14}a_{6}^{−11}.

Therefore the exponent vector of x corresponding to A is

exp_{A}(x) = (3, 5, −2, −16, 14, −11).

We see that in this way we can determine exp_{A}(x) for every x ∈ UT (4, ℤ) in a practical way. Thus A is a constructive polycyclic pc-sequence for UT (4, ℤ).

5.2.5 Corollary: The method presented in Example 5.2.4 can be used to determine a constructive polycyclic sequence for the group UT (d, ℤ).

5.2.6 Lemma: Let U be a subgroup of UT (d, ℤ). A constructive pcsequence for UT (d, ℤ) can be used to determine a constructive pc-sequence for U.

Proof: This is a well-known fact. See for example [6, Chapter 3]. The methods POLY SUBGROUP and POLY MEMBER described in [21, Chapter 9] can also be applied for this purposes. •

Algorithms in the domain of the last Lemma have been implemented already and are part of the ’Polycyclic’-package [8] which is a part of the GAPsystem.

Rational Module Series

Let G be a finitely generated solvable subgroup of GL(d, ℚ). Recall that we defined K_{p}(G) as the kernel of the p-congruence homomorphism

ψ_{p} : G → GL(n, p)

where p is an admissible prime for G (see Definition 2.4.2). The aim of this chapter is to compute a so-called module composition series of the natural ℚK_{p}(G)-module V = ℚ^{d}. This is a sequence of ℚK_{p}(G)-submodules

V = V_{1} > V_{2} > ⋯ > V_{m} = 0

such that V_{i}/V_{i+1} is irreducible as a ℚK_{p}(G)-module. For the case that G is abelian, we describe a method to determine a composition series for ℚ^{d} seen as a ℚG-module.

This chapter is organized as follows: Section 6.1 cites basic definitions and results from module theory. Section 6.2 determines the image and the kernel of the induced action of G to the factors of a modules series. In Section 6.3 and 6.4 we compute a certain submodule series called radical series. Finally we outline in Section 6.5 and Section 6.6 methods to refine a radicals series to a composition series. In our description we follow the presentation in [6, chapter 5].

6.1 Module Theory and p-congruence subgroups

In this section we want to cite some basic results from module theory which will be used throughout this chapter.

6.1.1 Definition: Let G be a group.

1. An abelian group (M, +) is called a G-module, if G operates via automorphisms on M. Thus there is a homomorphism φ : G → Aut(M).

2. Let 𝔽 be a field and M a 𝔽-vectorspace. Then M is called a 𝔽Gmodule, if G operates via 𝔽-linear automorphisms on M. In this case there exists a homomorphism φ : G → GL(M).

Naturally a subset N ⊂ M (subspace N ≤ M) is called a G-submodule (𝔽G-submodule) of M, if N is a G-module (𝔽G-module).

6.1.2 Definition: Let G be a group and V be a ℚG-module.

1. V is said to be irreducible if it does not contain any ℚG-submodule other than 0 and V, and if V ≠ 0.

2. V is said to be semisimple if it is the direct product of irreducible ℚG-modules.

3. We say that V is Artinian if V satisfies the descending chain condition on submodules, that is a sequence

V_{1} ⊃ V_{2} ⊃ V_{3} …

of submodules must stabilize.

6.1.3 Definition: Let G be a subgroup GL(d, ℚ). We define as its algebra

ℚ[G] = { ∑_{i=1}^{k} α_{i}g_{i} | α_{i} ∈ ℚ, g_{i} ∈ G } .

The dimension of ℚ[G] is the dimension of this set as a ℚ-vectorspace. ℚ[G] is a subspace of the matrix algebra M^{d×d}(ℚ) and thus an upper bound of the dimension of ℚ[G] is d^{2}. We can consider ℚ[G] as a ℚG-module where G operates from the right. A basis of a finite dimensional module which is given by module generators can be computed by the well-known and very efficient spinning algorithm (see [12]). The following lemma is essential for our investigations and will be used at various places throughout this chapter.

6.1.4 Lemma: (Schur, modified version) Let G be a group and V an irreducible ℚG-module with φ : G → GL(V). Then every non-zero element of ℚ[G^{φ}] is invertible.

Proof: See [9] Lemma 1.5. •

6.1.5 Corollary: Let A be an abelian group and V an irreducible ℚAmodule with φ : A → GL(V). Then ℚ[A^{φ}] is a field.

6.1.6 Lemma: Let G ≤ GL(d, ℚ_{π}) (see Section 2.4) and V = ℚ^{d} the natural G-module. Then

1. K_{p}(G) = G ∩ K_{p}(GL(d, ℚ_{π})).

2. K_{p}(G^{g}) = (K_{p}(G))^{g} for g ∈ GL(d, ℚ_{π}) and thus K_{p}(G) is invariant under base changes.

3. Let W be a ℚG-submodule of V. For the induced action on V and V/W we obtain that K_{p}(G)_{W} ≤ K_{p}(G_{W}) and K_{p}(G)_{V/W} ≤ K_{p}(G_{V/W}).

Proof: Elementary. •

6.2 Induced Action

The aim of this section is to investigate the induced action of rational matrix groups to the factors of a submodule series.

6.2.1 Integral Basis of rational spaces

In this section we want to examine when a rational space W ≤ ℚ^{d} has an integral basis, which can be extended to a basis of ℤ^{d}.

6.2.1 Definition: Let X be any subset of ℚ^{d}. The dual lattice X^{∗} and the orthogonal space X^{⊥} are defined as

X^{∗} := { y ∈ ℤ^{d} | y · x = 0 for all x ∈ X }
X^{⊥} := { y ∈ ℚ^{d} | y · x = 0 for all x ∈ X }.

6.2.2 Definition: Let L be a sublattice of ℤ^{d}. Then L is called pure if and only if the group ℤ^{d}/L is torsion-free. Further we define the pure hull L̄ of L as the unique sublattice of ℤ^{d} such that L̄/L = T (ℤ^{d}/L), where T (ℤ^{d}/L) is the torsion group of ℤ^{d}/L. Note that T (ℤ^{d}/L) exists because ℤ^{d}/L is abelian.

6.2.3 Lemma: There exists an integral basis of ℤ^{d} through a sublattice L if and only if L is pure. Further the pure hull of L, denoted by L̄, is pure.

Proof: Assume that L is a pure sublattice of dimension k. Then ℤ^{d}/L is isomorphic to ℤ^{d−k}. Denote by {e_{1}, …, e_{d−k}} representatives of a basis of ℤ^{d}/L. Merging this set with a basis of L we get a integral basis of ℤ^{d} through L.

Conversely assume that there exists an integral basis of ℤ^{d} through L. Then ℤ^{d}/L is isomorphic to ℤ^{d−k} and thus L is pure.

Let L̄ be the pure hull of L. We have to show that ℤ^{d}/L̄ is torsion-free. Let z ∈ ℤ^{d} such that there exists a natural number n ∈ ℕ such that nz ∈ L̄. It follows that there is an m ∈ ℕ such that mnz ∈ L. We deduce that z ∈ L̄ and z + L̄ is the trivial element of ℤ^{d}/L̄. •

The following lemma gives us a method to compute the pure hull L̄.

6.2.4 Lemma:

1. Let X be an arbitrary subset of ℚ^{d}. Then it follows that

X^{∗∗} = X^{⊥}^{⊥} ∩ ℤ^{d}

and thus dim_{ℚ}(X^{∗∗}) = dim_{ℚ}(X^{⊥}^{⊥}).

2. Let L ≤ ℤ^{d}. Then L^{∗∗} is equal to the pure hull L̄ of L.

Proof:

1. X^{∗∗} = X^{∗}^{⊥} ∩ ℤ^{d} = (X^{⊥} ∩ ℤ^{d})^{⊥} ∩ ℤ^{d} = X^{⊥}^{⊥} ∩ ℤ^{d}.

2. Let l̄ be an element of L̄. Then there exists a natural number n such that nl̄ = l ∈ L. For all x ∈ L^{∗} we have 0 = x · l = x · (nl̄) = n(x · l̄) and thus x · l̄= 0. This implies that l̄∈ L^{∗∗} and so L̄ ⊂ L^{∗∗}.

Conversely we know by 1. that the ℚ-dimension of L and L^{∗∗} are the same and that

L^{∗∗} = L^{⊥}^{⊥} ∩ ℤ^{d} = ⟨L⟩_{ℚ} ∩ ℤ^{d}.

Therefore we can write every l ∈ L^{∗∗} as l = ∑_{i=1}^{k} \frac{a_{i}}{b_{i}} l_{i} where \frac{a_{i}}{b_{i}} ∈ ℚ and l_{i} ∈ L. Now we get that (∏ b_{i})l ∈ L and so l + L is in the torsion group of ℤ^{d}/L. Therefore L^{∗∗} ⊂ L̄.

•

6.2.5 Corollary: Let W be a subspace of ℚ^{d}. Then there exists an integral basis B of ℤ^{d} through W.

Proof: We know that (W^{∗∗})^{∗∗} = (W ∩ ℤ^{d})^{∗∗} = ((W ∩ ℤ^{d})^{⊥} ∩ ℤ^{d})^{∗} = (W^{⊥} ∩ ℤ^{d})^{∗} = W^{∗∗} and so W^{∗∗} is a pure sublattice of ℤ^{d}. Further we know that the ℚ-dimensions of W^{∗∗} and W are the same, which implies that an integral basis B through W^{∗∗} is also an integral basis through W. •

6.2.2 Factor modules

Let π be a set of primes. Recall that the ring ℚ_{π} was defined as the set of rational numbers whose denominator is divisible by primes in π only. Let K be a subgroup of GL(d, ℚ_{π}) and denote by V the natural K-module ℚ^{d}. Let

V = V_{0} > V_{1} > ⋯ > V_{n} = 0

be a series of ℚK-modules. We induce the action of K to the factors of this series via the action homomorphism

ν : K → K_{V_{0}/V_{1}} × K_{V_{1}/V_{2}} × ⋯ × K_{V_{n−1}/V_{n}}.

The following Lemma examines the structure of the image and the kernel under this homomorphism.

6.2.6 Lemma: Suppose that K ≤ GL(d, ℚ_{π}) for a set of primes π. Then ker(ν) is a unipotent subgroup of GL(d, ℚ_{π}) and K_{V_{i}/V_{i+1}} ≤ GL(d_{i}, ℚ_{π}) for 1 ≤ i ≤ n, where ∑_{i=1}^{n} d_{i} = d.

Proof: By Corollary 6.2.5 there exists an integral basis B = {b_{1}, …, b_{d}} of ℤ^{d} through the module series. Denote by g := (b_{1}, …, b_{d})^{t}^{−1} ∈ GL(d, ℤ) the corresponding base change matrix from the canonical basis of ℚ^{d} to B. It follows that K^{g} is a subgroup of GL(d, ℚ_{π}) in block-upper-triangular form. That is every element k of K^{g} is of the form

( \begin{matrix}k_{0} & ∗ & ∗ & ∗ \\ & k_{1} & ∗ & ∗ \\ & & ... & ∗ \\ & & & k_{n−1} \end{matrix} )

where k_{i} is a matrix in GL(d_{i}, ℚ_{π}) with ∑_{i=0}^{n−1} d_{i} = d. The induced action of K on the factor V_{i}/V_{i+1} of the module series is conjugated in GL(d_{i}, ℤ) to the matrix group generated by the blocks k_{i} of the matrices k ∈ K^{g}. We deduce that K_{V_{i}/V_{i+1}} is a subgroup of GL(d_{i}, ℚ_{π}). Further ker(ν) is a unipotent subgroup of GL(d, ℚ_{π}), since ker(ν)^{g} is in upper-triangular form. •

6.3 Computing radicals

Let G ≤ GL(d, ℚ) be a finitely generated solvable group and denote by V := ℚ^{d} the natural ℚG-module. We want to determine a basis for the so-called radical Rad_{G}(V).

6.3.1 Definition: Let G be a group and V be a ℚG-module. The radical Rad_{G}(V) is defined as the intersection of all maximal ℚG-submodules of V.

6.3.2 Definition: Let G be a group and V be a ℚG-module. Then G is called semisimple if Rad_{G}(V) = 0.

For our purposes we will need the following lemma which is a part of basic module theory.

6.3.3 Lemma: Let G be a subgroup GL(d, ℚ) and V = ℚ^{d} the natural ℚG-module.

1. ℚ[G] is an Artinian algebra and V is an Artinian module.

2. Rad_{G}(V) < V, and Rad_{G}(V) = 0 if and only if V is semisimple. So V/Rad_{G}(V) is always semisimple.

3. Rad_{G}(V) = V Rad_{G}(ℚ[G])

4. If W is a ℚG-submodule of Rad_{G}(V), then Rad_{G}(V/W) = Rad_{G}(V)/W.

Proof: See [13] Chapter 7, Lemma 7.11., Satz 7.14 and Satz 7.18. •

First we describe a method for computing the radical for an abelian group. Then we extend the method to non-abelian groups.

6.3.1 Abelian rational matrix groups

Let A ≤ GL(d, ℚ) be a finitely generated abelian group. We want to determine the radical Rad_{A}(V). First we have to cite some results from module theory. For more details we refer to [13, Section 7.3.]. Note that the ℚAmodule ℚ[A], with A acting from the right, can be seen as a ring. Under this point of view the ℚA-submodules of ℚ[A] correspond to the right ideals of ℚ[A].

6.3.4 Definition: Let ℜ be ring. An element 𝔯 ∈ ℜ is called nilpotent if there is a natural number n such that 𝔯^{n} = 0.

6.3.5 Proposition: Let ℜ be an abelian artinian ring. The radical Rad(ℜ), which is defined as the intersection of the maximal ideals of ℜ, is composed of the nilpotent elements of ℜ, i.e.

Rad(ℜ) = { 𝔯 ∈ ℜ | 𝔯 nilpotent }

Proof: See [13] Folgerung 7.22. •

We denote a matrix or a matrix group diagonalizable if it is conjugated in GL(d, ℂ) to a diagonal matrix or a diagonal matrix group.

6.3.6 Lemma: Let A ≤ GL(d, ℚ) be a finitely generated abelian group and B be a basis for ℚ[A]. Then Rad_{A}(ℚ[A]) = 0 if and only if each element in B is diagonalizable.

Proof: Assume that Rad_{A}(ℚ[A]) = 0. Then

Rad_{A}(V) = V Rad_{A}(ℚ[A]) = V 0 = 0.

Therefore V is semisimple. So we can write V = ℚ^{d} as the direct product of irreducible ℚ[A]-modules

V = V_{1} ⊕ ⋯ ⊕ V_{r}.

By Schur’s Lemma ℚ[A_{V_{i}}] is a field and thus it is generated by a primitive element a_{i}, which possesses an irreducible minimal polynomial p_{i}. Since ℚ is separable, the polynom p_{i} has no multiple zeros. This implies that a_{i} is diagonalizable. So ℚ[A] is diagonalizable on each V_{i} and therefore ℚ[A] on V too.

Conversely we assume that every element in B is diagonalizable. First we show that all elements in B are simultaneously diagonalizable. It suffices to show by induction that two elements b, c ∈ B are simultaneously diagonalizable. Denote by b_{1}, …, b_{s} the eigenvalues of b and by Eig(b, b_{i}) the space of all eigenvectors of the matrix b of the eigenvalue b_{i}. If e ∈ Eig(b, b_{i}), then it follows that (ec)b = (eb)c = (b_{i}e)c = b_{i}(ec) and so ec ∈ Eig(b, b_{i}). Thus, the vector space Eig(b, b_{i}) is a c-invariant submodule of V for i = 1, …, s. Certainly the matrix c is diagonalizable on Eig(b, b_{i}) and so b and c are simultaneously diagonalizable. This implies that all elements in B are simultaneously diagonalizable.

We deduce, that the algebra ℚ[A] is diagonalizable. So there exists an element c ∈ GL(d, ℂ) such that ℚ[A]^{c} is in diagonal form. Let r ∈ Rad_{A}(ℚ[A]). By Proposition 6.3.5, there exists an n ∈ ℕ such that r^{n} = 0. This implies, that (r^{c})^{n} = 0 and hence r^{c} = 0. We deduce that Rad_{A}(ℚ[A]) = 0. •

6.3.7 Corollary: Let A be an abelian finitely generated rational matrix group. Then A is diagonalizable if and only if Rad_{A}(V) = 0.

Proof: This follows directly by Lemma 6.3.6 and Lemma 6.3.3. •

6.3.8 Lemma: Let A ≤ GL(d, ℚ) be a finitely generated abelian group and B be a basis for ℚ[A]. Let a ∈ ℚ[A] with minimal polynomial f_{a}(x) ∈ ℚ[x] and let f_{a}(x) = f_{1}(x)^{e_{1}} ⋯ f_{r}(x)^{e_{r}} be its factorization into irreducible factors. Then a is diagonalizable if and only if e_{1} = ⋯ = e_{r} = 1. If a is not diagonalizable, then f_{1}(a) ⋯ f_{r}(a) is a non-trivial nilpotent element of Rad_{A}(ℚ[A]).

Proof: The matrix a is is diagonalizable in GL(d, ℂ) if and only if f_{a} has no multiples zeros in ℂ. This is equivalent with e_{1} = ⋯ = e_{r} = 1.

Certainly the element α := f_{1}(a) ⋯ f_{r}(a) is nilpotent since α^{max{e_{i}}} = 0. By Proposition 6.3.5 we know that α ∈ Rad_{A}(ℚ[A]). So if a is not diagonalizable, then there is at least one e_{i} ≠ 1, which implies that α is a non-trivial nilpotent element of Rad_{A}(ℚ[A]). •

Let A ≤ GL(d, ℚ) be a finitely generated abelian group and V = ℚ^{d} the natural ℚA-module. We outline an algorithm to determine the radical Rad_{A}(V). Using the spinning algorithm we calculate a basis for the ℚA-module ℚ[A]. For every new element which we add to the basis, we can check with the help of lemma 6.3.8 if it is diagonalizable. If not we can determine, again with the aid of Lemma 6.3.8, a nilpotent element α ∈ Rad_{A}(ℚ[A]). The ℚA-module W generated by V α is a submodule of Rad_{A}(V) by Lemma 6.3.3. Now proceed by inducing the action of A to the module V/W. The algorithm terminates because the number of diagonalizable elements which we can add to to the basis of ℚ[A] is bounded by d.

  RadicalOfAbelianGroup(A)

set V := ℚ^{d} and W := 0 ≤ V set B := { }

    repeat
        find a new basis element b in ℚ[A]\ ⟨B⟩ (via the spinnig algorithm)
        compute the minimal polynomial f_{b} of b
        determine a factorization of f_{b} = f_{1}^{e_{1}} · · · f_{r}^{e_{r}}
        if there exists an e_{i} ≠ 1 then
           calculate the nilpotent element α:=f_{1}(b) · · · f_{r}(b)
           spin up the ℚA-module U/W generated by (V/W)α
           set W:=U
           induce the action of A to V/W

set B := { }

        else

set B := B ∪ {b}

        end if
    until B is a basis of ℚ[A]
    return W

6.3.2 Rational matrix groups

Let G be a finitely generated solvable subgroup of GL(d, ℚ). This section gives a method to calculate the radical Rad_{G}(V), where V is the natural ℚG-module ℚ^{d}. The kernel of the p-congruence homomorphism K_{p}(G) is unipotent-by-abelian by Theorem 2.4.4 because K_{p}(G) ≤ G is solvable. This is of vital importance for this algorithm. The following theorem shows, that it is sufficient to compute Rad_{K_{p}(G)}(V).

6.3.9 Theorem: Let G ≤ GL(d, ℚ) and N a normal subgroup of G such that [G : N] < ∞. Denote by V the natural ℚG-module ℚ^{d}. Then it follows that Rad_{G}(V) = Rad_{N}(V).

Proof: See [25] 1.5. and 1.8. •

So we need to outline a method to compute the radical of a rational matrix group which is unipotent-by-abelian.

6.3.10 Proposition: Let K ≤ GL(d, ℚ) be an unipotent-by-abelian group. Then K is triangularizable.

Proof: See [15] Corollary 2.8. •

6.3.11 Lemma: Let K be an unipotent-by-abelian subgroup of GL(d, ℚ). Let V be the natural ℚK-module ℚ^{d}. Then for all k ∈ K′ the set V (k − 1) is a subset of Rad_{K}(V).

Proof: By Proposition 6.3.10, there exists an c ∈ GL(d, ℂ) such that K^{c} is in triangular form. The commutator subgroup K′ is unipotent and so (x(k − 1))^{c} = x^{c}(k^{c} − 1) is nilpotent for all x ∈ K and k ∈ K′. It follows that x(k − 1) is nilpotent. Therefore the ideal in ℚ[K] generated by (k − 1) is nilpotent as well. By [13, Lemma 7.20] this implies that (k − 1) is an element of Rad_{K}(ℚ[K]). Now by Lemma 6.3.3 we conclude that V (k − 1) ⊂ Rad_{K}(V). •

Now we are ready to describe a method to compute Rad_{K_{p}(G)}(V) = Rad_{G}(V). Regard the submodule W ≤ V which is spanned up by the set

{ [k, l] − 1 | k, l generators of K_{p}(G) } .

By Lemma 6.3.11 we conclude that W ⊂ Rad_{K_{p}(G)}(V), because K_{p}(G) is unipotent-by-abelian. Further K_{p}(G) acts as an abelian group on V/W and so we can compute Rad_{K_{p}(G)}(V/W) with the algorithm of the section 6.3.1. By Lemma 6.3.3 it follows that Rad_{K_{p}(G)}(V/W) = Rad_{K_{p}(G)}(V)/W and we are done.

In case we have just normal subgroup generators of K_{p}(G), we have to modify this approach. First we have to close the basis of ℚ[K_{p}(G)] under the conjugation action of G. Second it is possible, that we calculate a module W which is ”too small”, i.e. a module W such that K_{p}(G) does not act in an abelian way on V/W. In computing Rad_{K_{p}(G)}(V/W), where W is spanned up by normal subgroup generators only, we have to make sure that ℚ[K_{p}(G)] acting on V/W is abelian. In spinning up a basis of ℚ[K_{p}(G)] we check if each element g which we add to the partial basis {g_{1}, …, g_{j}} commutes with all g_{i} for i = 1, …, j. If there is an i such that gg_{i} ≠ g_{i}g we reset W := ⟨W ([g, g_{i}] − 1)⟩.

Let G be a finitely generated solvable subgroup of GL(d, ℚ) and let K_{p}(G) be the kernel of the p-congruence homomorphism given by a list of normal subgroup generators. The following method determines the radical Rad_{G}(V).

CHAPTER 6. RATIONAL MODULE SERIES  51

Radical(G, K_{p}(G))
let K be a list containing normal subgroup generators of K_{p}(G)

set V := ℚ^{d}

compute the G-submodule W of V generated by {V ([k, l] − 1)|k, l ∈ K}
induce the matrix action of G and K_{p}(G) to V/W

set B := { }

repeat
find a new basis element b in ℚ[⟨K⟩^{G}]\ ⟨B⟩ (via the spinnig algorithm)
if b commutes with all elements in the partial basis B then
compute the minimal polynomial f_{b} of b
determine a factorization of f_{b} = f_{1}^{e_{1}} · · · f_{r}^{e_{r}}
if there exists an e_{i} ≠ 1 then
    calculate the nilpotent element α:=f_{1}(b) · · · f_{r}(b)
    spin up the G-module U/W generated by (V/W)α
    reset W:=U

set B := { }

else

set B := B ∪ {b}

end if
else
determine b̂ ∈ B such that [b, b̂] ≠ 1
spin up the G-module W′ generated by W ([b, b̂] − 1)
reset W := W′

set B := { }

end if
induce the action of G and K_{p}(G) to V/W

until B is a basis for ℚ[⟨K⟩^{G}] = ℚ[K_{p}(G)]

return W

6.3.12 Remark: In the last algorithm Radical(G,K_{p}(G)), we can replace K_{p}(G) by any unipotent-by-abelian group K ⊴ G which is of finite index in G.

6.4 Radical series

Let G be a finitely generated solvable subgroup of GL(d, ℚ) and V = ℚ^{d} its natural ℚG-module. Now it is straightforward to formulate an algorithm to calculate the so-called radical series.

6.4.1 Definition: Let G be a finitely generated solvable subgroup of GL(d, ℚ) and V = ℚ^{d} its natural ℚG-module. The radical series

ℚ^{d} = R_{0} > R_{1} > ⋯ > R_{n} = 0

is defined by R_{i+1} := Rad_{G}(R_{i}).

The algorithm presented in section 6.3.2 can be used in an iterated way as follows

  RadicalSeries(G)
    set Rad:=ℚ^{d}
    set Series:=[Rad]
    determine K_{p}(G) and set K := K_{p}(G)
        while Rad≠ 0 do
           let G_{R} and K_{R} be the induced action of G and K to Rad
           Rad:=Radical(G_{R},K_{R}) (Section 6.3.2)
           add Rad to Series

set G := G_{R} and K := K_{R}

        end while
    return Series

6.4.2 Lemma: The algorithm RadicalSeries ist correct.

Proof: By Remark 6.3.12 it remains to show that in every loop K_{R} is unipotent-by-abelian and of finite index in G_{R}. By Lemma 6.1.6 we have K_{R} = K_{p}(G)_{R} ≤ K_{p}(G_{R}) ⊴ G_{R} and so K_{R} is unipotent-by-abelian. From [G : K_{p}(G)] < ∞ we deduce that [G_{R} : K_{R}] < ∞ by the homomorphism theorem. •

In a similar way we construct the faster algorithm

RadicalSeriesOfAbelianGroup. It works as RadicalSeries with the only

difference that it uses the algorithm RadicalOfAbelianGroup instead of Radical. Note, that for this approach it is not necessary to calculate K_{p}(G).

6.4.3 Remark: By Lemma 6.3.3 Rad_{G}(R_{i}/R_{i+1}) = 0 and thus R_{i}/R_{i+1} is a semisimple ℚG-module.

6.5 Semisimple groups

Let S be a finitely generated semisimple solvable subgroup of GL(d, ℚ). Recall that the group S is called semisimple if Rad_{S}(V) = 0, where V = ℚ^{d}.

6.5.1 Remark: If Rad_{S}(V) = 0 then Rad_{K_{p}(S)}(V) = 0 by Theorem 6.3.9. This implies that V is the direct product of irreducible K_{p}(S)-modules.

We want to determine a splitting of the natural ℚK_{p}(S)-module ℚ^{d} into irreducible modules.

6.5.2 Corollary: Let S ≤ GL(d, ℚ) be a finitely generated semisimple solvable group and denote p as an admissible prime for S. Then K_{p}(S) is abelian and torsion-free.

Proof: By Lemma 6.3.11 every element of the commutator of K_{p}(S) must be trivial. Further K_{p}(S) is torsion-free by Theorem 2.4.4. •

Thus it is sufficient to describe a splitting method for abelian semisimple groups.

6.5.1 Abelian semisimple groups

Let A be a finitely generated abelian semisimple matrix subgroup of GL(d, ℚ). Our aim is to calculate a splitting of the natural ℚA-module V = ℚ^{d} into irreducible modules. The first step will be to determine a primitive element c of the matrix algebra ℚ[A], i.e. an element c such that ℚ[c] = ℚ[A]. Recall that by Lemma 6.3.3 ℚ[A] is semisimple as a ℚA-module if and only if V is semisimple as ℚA-module.

6.5.3 Lemma: Let A := ⟨a_{1}, …, a_{k}⟩ be an abelian semisimple matrix subgroup of GL(d, ℚ). Let B = {b_{1}, …, b_{l}} be a basis for the semisimple algebra ℚ[A]. Then almost all linear combinations of b_{1}, …, b_{l} yield an primitive element for ℚ[A].

Proof: By induction it suffices to show that the statement is true for the case l = 2. So let x, y be the elements of the basis B. We want to show that for almost all a ∈ ℚ we have ℚ[x + ay] = ℚ[x, y]. Thus we have to find two polynomials f, g ∈ ℚ[X] such that f(x + ay) = x and g(x + ay) = y for almost all a ∈ ℚ. By Corollary 6.3.7 we can assume that there exists an element c ∈ GL(d, ℂ) such that ℚ[A^{c}] is in diagonal form. Define x̂ := x^{c} and ŷ:= y^{c}. If x̂_{i} and ŷ_{i} are the entries on the diagonals of x̂ and ŷ we have to find polynomials f, g ∈ ℚ[X] with f(x̂_{i} + aŷ_{i}) = x̂_{i} and g(x̂_{i} + aŷ_{i}) = y_{i} for i = 1, …, d. Complex polynomials f, g ∈ ℂ[X] verifying these conditions can be found by interpolation. We only have to make sure that x̂_{i} + aŷ_{i} = x̂_{j} + aŷ_{j} implies x̂_{i} = x̂_{j} and ŷ_{i} = ŷ_{j}. This is easy to achieve in choosing an a such that a ≠ \frac{x̂_{i}−x̂_{j}}{ŷ_{i}−ŷ_{j}} for all i, j ∈ \{1, …, d\}. We deduce that f(x+ay) = x and g(x + ay) = y. Since x, y and x + ay are rational f, g can be chosen in ℚ[X]. •

It is well-known, that an element c such that ℚ[A] = ℚ[c] has a minimal polynomial whose degree is equal to dim(ℚ[A]). Now we can outline the following algorithm to determine a primitive element of ℚ[A].

  PrimitiveElement(A)
    determine via the spinning algorithm a basis B of ℚ[A].
    repeat
        set c :=RandomLinearCombination(B)
        set m :=MinimalPolynomial(c)
    until (degree of m) = Length(B)
    return c

Note that the length of the basis B is bounded by d because ℚ[A] is diagonalizable.

6.5.4 Definition: A module W is called homogeneous if it it is the direct product of irreducible and isomorphic modules.

Once we are able to calculate a primitive element of ℚ[A] where A is an abelian semisimple group, we can use the following Lemma to split the natural ℚA-module V into the direct product of homogeneous submodules W ≤ V.

6.5.5 Lemma: Let c be a diagonalizable element of GL(d, ℚ). Write the minimal polynomial f of c as the product of irreducible polynomials

f = f_{1} · f_{2} ⋯ f_{r}

(Note that f_{i} ≠ f_{j} for i ≠ j because c is diagonalizable.) Further we define the submodule W_{i} of V = ℚ^{d} as the kernel of the linear mapping defined by f_{i}(c) for i = 1, …, r. Then it follows that 1. V can be written as the direct product of the W_{i}, i.e.

V = W_{1} ⊕ W_{2} ⊕ ⋯ ⊕ W_{r}.

Further W_{i} is ℚ[c]-invariant for i = 1, …, r.

2. W_{i} is a homogeneous ℚ[c]-module for i = 1, …, r.

Proof:

1. The matrix algebra ℚ[c] is abelian and so W_{i} is a ℚ[c]-invariant submodule of V. Via induction over i we want to prove that

ker(f_{1}(c) ⋯ f_{i}(c)) = W_{1} ⊕ W_{2} ⊕ ⋯ ⊕ W_{i}.

For i = r this gives the wanted result.

If i = 1 then we have ker(f_{1}(c)) = W_{1} and so the statement is true. Now assume that ker(f_{1}(c) ⋯ f_{i−1}(c)) = W_{1} ⊕W_{2} ⊕⋯⊕W_{i−1} and let w ∈ ker(f_{1}(c) ⋯ f_{i}(c)). Because f_{i} and f_{1} ⋯ f_{i−1} are coprime, there exist α, β ∈ ℚ such that 1 = αf_{i} + βf_{1} ⋯ f_{i−1}. Thus we can write

w = \underbrace{αf_{i}(c)w}_{∈ker(f_{1}(c)···f_{i−1}(c))} + \underbrace{βf_{1}(c) ⋯ f_{i−1}(c)w}_{∈W_{i}} .

If w ∈ W_{i} and w ∈ ker(f_{1}(c) ⋯ f_{i−1}(c)), then we can deduce that w = 0. It follows that (W_{1}⊕⋯⊕W_{i−1})∩W_{i} = 0 and that ker(f_{1}(c) ⋯ f_{i}(c)) = (W_{1} ⊕ ⋯ ⊕ W_{i−1}) + W_{i}.

2. First we induce the action of ℚ[c] to W_{i}. Now we have f_{i}(c) = 0 and so f_{i} is the minimal polynomial of c. Assume that I ≠ ℚ[c] is an ideal of ℚ[c]. Certainly c + I is a primitive element of ℚ[c]/I. The minimal polynomial f_{c+I} of c + I must be a divisor of f_{i}. Therefore f_{c+I} = f_{i}, because I ≠ ℚ[c], and hence I = 0. We deduce that the algebra ℚ[c] is simple. This implies that W_{i} is homogeneous for i = 1, …, r (see [11] Chapter 17 Corollary 4.5. and Proposition 4.7.).

•

The following Lemma gives a method to split a homogeneous ℚA-module W, where A is an abelian subgroup of GL(d, ℚ).

6.5.6 Lemma: Let A ≤ GL(d, ℚ) be an abelian group and W be a homogeneous ℚA-submodule of ℚ^{d}. Then every non-trivial vector w ∈ W is contained in an irreducible ℚA-submodule of W.

Proof: Let w be a non-trivial vector in W. Denote by U the ℚA-module which is generated by w. It is possible to write W = ⊕_{i=1}^{s}W_{i}, where the W_{i} are irreducible ℚA-modules and hence w = ∑_{i=1}^{s} w_{i} where w_{i} ∈ W_{i}. Because w is non-trivial there is at least one i ∈ {1, …, n} with w_{i} ≠ 0. We want to show that the projection ϕ : U → W_{i} is a bijective ℚAhomomorphism. The map ϕ is clearly a surjective ℚA-homomorphism and so it suffices to show that ϕ is injective. Let u be an element of U such that ϕ(u) = 0. It is possible to write u = w^{a} with a ∈ ℚ[A]. It follows that 0 = ϕ(u) = ϕ(w^{a}) = ϕ(w)^{a} = w_{i}^{a}. By Schur’s lemma (6.1.4) we deduce that a = 0 and so u = 0. We conclude that ϕ is bijective and thus U = W_{i}. Therefore the module U is irreducible. •

Finally we carried all the necessary elements together to achieve the aim of this section: Under the assumption that A is a finitely generated abelian semisimple subgroup of GL(d, ℚ) we want to calculate a direct splitting of the natural ℚA-module V = ℚ^{d} into irreducible modules.

  IrreducibleSplitting(A)
    set c :=PrimitiveElement(ℚ[A]) (see 6.5.3)
    let f be the minimal polynomial of c
    factorize f = f_{1} · · · f_{r} where f_{i} irreducible

set W_{i} := ker(f_{i}(c)) for i = 1, …, r

    # splitting into homogeneous submodules (see 6.5.5)

split V = W_{1} ⊕ ⋯ ⊕ W_{r}

    # splitting into irreducible submodules (see 6.5.6)
    for i = 1 to r do
      split W_{i} by spinning up vectors
    end for
    return the irreducible splitting of V

6.6 Composition series

Now we are ready to outline the main result of this section: Let G be a finitely generated solvable subgroup of GL(d, ℚ). Denote by K_{p}(G) the kernel of the p-congruence homomorphism defined in Section 2.4 and by V the natural ℚK_{p}(G)-module ℚ^{d}. We present an algorithm which calculates a composition series of V, i.e. a sequence of ℚK_{p}(G)-submodules

V = V_{1} > V_{2} > ⋯ > V_{m} = 0

such that V_{i}/V_{i+1} is irreducible. Further we desribe an algorithm which calculates a composition series of V seen as a ℚG-module, under the assumption that G is abelian.

Let ℚ^{d} = R_{0} > R_{1} > ⋯ > R_{n} = 0 be the radical series defined in the section 6.4. By Theorem 6.3.9 Rad_{K_{p}(G)}(V) = Rad_{G}(V) because K_{p}(G) is of finite index in G. Therefore K_{p}(G)_{R_{i}/R_{i+1}} is a semisimple group by Lemma 6.3.3. Further by Lemma 6.1.6 we get that K_{p}(G)_{R_{i}/R_{i+1}} is a subgroup of K_{p}(G_{R_{i}/R_{i+1}}), which is by Corollary 6.5.2 abelian and torsion-free. Thus K_{p}(G)_{R_{i}/R_{i+1}} is a free abelian semisimple group and we can apply the methods of section 6.5.1 to split R_{i}/R_{i+1} into irreducible ℚK_{p}(G)-modules.

CompositionSeries(K_{p}(G))
    # compute the radical series (section 6.4)

compute V = R_{0} > R_{1} > ⋯ > R_{n} = 0

    for all factors of this series do
      induce the action of K_{p}(G) to R_{i}/R_{i+1}
      # irreducible splitting (section 6.5.1)
      split R_{i}/R_{i+1} into irreducible ℚK_{p}(G)-modules
    end for
    return the refined radical series

For abelian groups we can formulate a similar and faster approach.

CompositionSeriesAbelianGroup(G)
    # compute the radical series of an abelian group (section 6.4)

compute V = R_{0} > R_{1} > ⋯ > R_{n} = 0

    for all factors of this series do
      induce the action of G to R_{i}/R_{i+1}
      # irreducible splitting (section 6.5.1)
      split R_{i}/R_{i+1} into irreducible ℚG-modules
    end for
    return the refined radical series

CHAPTER 6. RATIONAL MODULE SERIES  58

Main algorithms

Let G be a finitely generated subgroup of GL(d, ℚ). As the main result of this thesis, we outline in this chapter an algorithm which computes a polycyclic presentation of the group G, if G is polycyclic. Further we show that a similar approach can be used to test if a finitely generated subgroup H ≤ GL(d, R) is solvable, where R = ℚ, ℤ or a finite field 𝔽_{q}. If R = ℤ or 𝔽_{q} the group H is solvable if and only if it is polycyclic (see Section 2.3). Therefore, in this case we can also test if H is polycyclic. We begin this chapter with some remarks about the calculation of normal subgroup generators.

7.1 Normal subgroup generators

We suppose that G := ⟨g_{1}, …, g_{k}⟩ is a finitely generated group and that

φ : G → φ(G)

is a group homomorphism. Further we assume, that we know how to calculate a finite presentation of the group

φ(G) = ⟨ X | R ⟩

where X = {φ(g_{1}), …, φ(g_{k})} and R are relations in X.

[figure: •; G; φ; •; φ(G) = ⟨ X | R ⟩; •; kerφ; φ; •; 1; •; 1]

7.1.1 Lemma: Define the set

R(G) := { r(g_{1}, …, g_{k}) | r ∈ R } .

Then R(G)^{G} = kerφ.

Proof: Let F be a free group on k generators f_{1}, …, f_{k}. Define τ to be the map τ : F → G , f_{i} ↦ g_{i}. Then by the definition of a finite presentation we know that R(F)^{F} = ker(τφ), where R(F) are the relations in R expressed in the elements f_{1}, …, f_{k}. The elements in R(F) are normal subgroup generators of ker(τφ). Thus τ(R(F)) = R(G) are normal subgroup generators for kerφ.

[figure: •; F; τ; •; G; φ; •; φ(G); •; ker(τφ); τ; •; kerφ; φ; •; 1; •; ker(τ); τ; •; 1; •; 1]

•

The calculation of normal subgroup generators of φ gets a little more complicated if we are only able to calculate a finite presentation φ(G) = ⟨Y |S⟩ with Y ≠ X = {φ(g_{1}), …, φ(g_{k})}. In this case we have to convert the presentation φ(G) = ⟨Y |S⟩ to a presentation φ(G) = ⟨X|R⟩.

7.1.2 Proposition: Let H = ⟨Y |S⟩ be a finitely presented group and let X be an arbitrary generating set for H. Then there exists a finite presentation of the form H = ⟨X|R⟩.

Proof: Every element x ∈ X can be written as a word w_{x}(Y) over the set Y ∪ Y^{−1}. Vice versa we can write y = w_{y}(X) for every y ∈ Y. Then we have the following relations in H:

s(w_{y}(X)|y ∈ Y) = 1 for s = s(Y) ∈ S,
x = w_{x}(w_{y}(X)|y ∈ Y) for x ∈ X.

We call these relations R. Define X̂ := {x̂_{1}, …, x̂_{k}} to be a set of abstract symbols and define the group Ĥ := ⟨X̂|R(X̂)⟩. Then there is an epimor-

phism π : Ĥ → H, x̂_{i} ↦ x_{i}, because the elements x_{i} ∈ X fulfill the relations in R. On the other hand the map σ : Y → Ĥ, y_{i} ↦ w_{y_{i}}(X̂) can also be extended to an homomorphism H → Ĥ, since every relation in S is fulfilled by the the elements w_{y_{i}}(X̂) in Ĥ. Further every element x can be expressed as a word in Y and so σ is surjective. Since π and σ are inverse to each other we get that H ≅ Ĥ. •

Assume that a finite presentation of φ(G) = ⟨Y |S⟩ is given, where Y is not equal to X = {φ(g_{1}), …, φ(g_{k})}. Then we can compute normal subgroup generators of kerφ in the following way: Convert the presentation φ(G) = ⟨Y |S⟩ to a presentation φ(G) = ⟨X|R⟩ using Proposition 7.1.2. Then calculate normal subgroup generators of kerφ using Lemma 7.1.1.

7.2 Solvability

7.2.1 Finite matrix groups

Let G be a finite matrix group. Then G is solvable if and only if G is polycyclic by Theorem 2.3.1. Therefore we can use the algorithm ConstructivePcSequenceFinite, explained in Section 3.3, to test if G is solvable.

7.2.2 Rational matrix groups

Let G be a finitely generated subgroup of GL(d, ℚ). In Section 6.4 we described the algorithm RadicalSeries to compute the radical series of the natural ℚG-module ℚ^{d}, if G is solvable. The next Lemma and Proposition show that this algorithm can be used to test if G is solvable.

7.2.1 Lemma: Let K be a finitely generated subgroup of GL(d, ℚ) and let

ℚ^{d} = V_{0} > V_{1} > ⋯ > V_{n} = 0

be a series of ℚK-modules such that K acts in an abelian way on the factors of this series. Then the group K is solvable.

Proof: By Lemma 6.2.6, we can find a matrix g ∈ GL(d, ℚ) such that K^{g} is in block-upper-triangular form. That is, every element k ∈ K^{g} is of the form

( \begin{matrix}k_{0} & ∗ & ∗ & ∗ \\ & k_{1} & ∗ & ∗ \\ & & ... & ∗ \\ & & & k_{n−1} \end{matrix} )

where the k_{i} are matrices in GL(d_{i}, ℚ) with ∑_{i=0}^{n−1} d_{i} = d. The matrices { k_{i} | k ∈ K } correspond to the induced action of K to the factor V_{i}/V_{i+1} (see again Lemma 6.2.6). By hypothesis K_{V_{i}/V_{i+1}} is an abelian group for i = 0, …, n − 1. Therefore the matrices { k_{i} | k ∈ K^{g} } generate an abelian group for i = 0, …, n − 1. Thus, the commutator of two matrices in K^{g} is in upper-triangular form. It follows that the commutator subgroup K′ is unipotent and thus K is unipotent-by-abelian. Therefore the group K is solvable. •

7.2.2 Proposition: Let G be a finitely generated subgroup of GL(d, ℚ). Then the group G is solvable if and only if the image under the p-congruence homomorphism I_{p}(G) is solvable and if the algorithm RadicalSeries (see Section 6.4) returns a submodule series ℚ^{d} = V_{0} > V_{1} > ⋯ > V_{n} = 0.

Proof: Assume that G is solvable. Then I_{p}(G) ≅ G/K_{p}(G) is solvable. Further the algorithm RadicalSeries terminates by Section 6.4.

Now we assume that I_{p}(G) is solvable and that the algorithm RadicalSeries(G, K_{p}(G)) terminates (Note that the finite group I_{p}(G) is polycyclic. Therefore normal subgroup generators for K_{p}(G) can be obtained by calculating a polycyclic presentation of I_{p}(G).) Let ℚ^{d} = V_{0} > V_{1} > ⋯ > V_{n} = 0 be the submodule series which is returned by the algorithm. By the construction of the algorithm K_{p}(G)_{V_{i}/V_{i+1}} is abelian for i = 0, …, n − 1. Therefore, K_{p}(G) is solvable by Lemma 7.2.1. This implies that the group G is solvable. •

Therefore we can specify the following algorithm for a finitely generated group G ≤ GL(d, ℚ):

  IsSolvable(G)
    let ψ_{p} : G → GL(d, p) be the p-congruence homomorphism
    # (see Definition 2.4.2 )
    try to determine a constructive pc-sequence for I_{p}(G) = ψ_{p}(G)
    # (see Chapter 3 on finite groups)
    if this fails then
      return 'fail'
      # (I_{p}(G) is not solvable, see Section 7.2.1)
    fi
    calculate normal subgroups generators for K_{p}(G) = ker(ψ_{p})
    # (see Section 7.1)
    try to compute the radical series V = V_{1} > V_{2} > · · · > V_{m} = 0
    # (see Section 6.4)
    if this fails then
      return 'false'
    else
      return 'true'
    fi

7.3 Calculating presentations

7.3.1 Finite matrix groups

Let G be a finite matrix group. By Corollary 2.2.5 it is sufficient to calculate a constructive polycyclic sequence to get a polycyclic presentation of G. This can be done by the algorithm ConstructivePcSequenceFinite, explained in Section 3.3.

7.3.2 Rational matrix groups

Let the group G := ⟨g_{1}, …, g_{k}⟩ be a polycyclic subgroup of GL(d, ℚ). By Corollary 2.2.5 it is sufficient to calculate a constructive polycyclic sequence to get a polycyclic presentation of G. This can be done by the following algorithm:

CHAPTER 7. MAIN ALGORITHMS  64

ConstructivePcSequence(G)
let ψ_{p} : G → GL(d, p) be the p-congruence homomorphism
# (see Definition 2.4.2)
determine a constructive pc-sequence for I_{p}(G) = ψ_{p}(G)
# (see Chapter 3 on finite groups)
calculate normal subgroups generators for K_{p}(G) = ker(ψ_{p})
# (see Section 7.1)
let V := ℚ^{d} be the natural ℚK_{p}(G)−module
compute a composition series V = V_{1} > V_{2} > · · · > V_{m} = 0
# (see Section 6.6)

let ν : K_{p}(G) → K_{p}(G)_{V_{0}/V_{1}} × K_{p}(G)_{V_{1}/V_{2}} × ⋯ × K_{p}(G)_{V_{n−1}/V_{n}}

# (see Section 6.2.2)
for i in [0...(n-1)] do
  determine a constructive pc-sequence C_{i} of K_{p}(G)_{V_{i}/V_{i+1}}
  # K_{p}(G)_{V_{i}/V_{i+1}} ≤ K_{p}(G_{V_{i}/V_{i+1}}) is abelian by Corollary 6.5.2
  # (ℚ[K_{p}(G)_{V_{i}/V_{i+1}}] is a field by Schur's Lemma, apply Chapter 4)
od
merge C_{1}, . . . , C_{n−1} to a constructive pc-sequence of K_{p}(G)^{ν}.
let U_{p}(G) be the kernel of ν
combine I_{p}(G) and K_{p}(G)^{ν} to a constructive pc-sequence of G/U_{p}(G)
calculate normal subgroup generators of U_{p}(G)
determine a constructive pc-sequence for the unipotent group U_{p}(G)
# (see Chapter 5)
combine G/U_{p}(G) and U_{p}(G) to a constructive pc-sequence of G
return the constructive pc-sequence of G

7.3.1 Remark: We have to pay attention to the fact that we can only compute normal subgroup generators for K_{p}(G) and U_{p}(G). Therefore we have to close the constructive pc-sequences for K_{p}(G)^{ν} and U_{p}(G) under the conjugation action of G.

For a finitely generated abelian group A ≤ GL(d, ℚ) we can proceed by a similar but faster approach. The only modification to the last algorithm is, that we can skip the calculations in the finite part I_{p}(G):

  ConstructivePcSequenceAbelianGroup(A)
    let V := ℚ^{d} be the natural ℚA−module
    compute a composition series V = V_{1} > V_{2} > · · · > V_{n} = 0
    # (see Section 6.6)

let ν : A → A_{V_{0}/V_{1}} × A_{V_{1}/V_{2}} × ⋯ × A_{V_{n−1}/V_{n}}

    # (see Section 6.2.2)
    for i in [0...(n-1)] do
      determine a constructive pc-sequence C_{i} of A_{V_{i}/V_{i+1}}
      # (ℚ[A_{V_{i}/V_{i+1}}] is a field by Schur's Lemma, apply Chapter 4)
    od;
    merge C_{1}, . . . , C_{n−1} to a constructive pc-sequence of A^{ν}.
    let U_{p}(A) be the kernel of ν
    calculate normal subgroup generators of U_{p}(A)
    determine a constructive pc-sequence for the unipotent group U_{p}(A)
    # (see Chapter 5)
    combine A^{ν} and U_{p}(A) to a constructive pc-sequence of A
    return the constructive pc-sequence of A

The big advantage of this approach for abelian groups is not that we economize a lot of time in skipping the calculations in the finite part I_{p}(G). In practice this is the fewest time consuming step. Rather, the benefit of this method is, that we use the generators a_{1}, …, a_{k} of the abelian group A instead of the normal subgroup generators of K_{p}(A) for the further computations. In general the matrices a_{1}, …, a_{k} have much smaller entries. Also it is not necessary to close the set A^{ν} under the conjugation action of A.

7.3.2 Remark: The algorithm ConstructivePcSequence works correctly if the input G is a polycyclic group. But what does happen if the finitely generated group G is not polycyclic ?

• Case 1: G is not solvable. Then either the computation of a constructive pc-sequence for the finite image I_{p}(G) or the computation of the radical series with the help of K_{p}(G) must fail (See Section 7.2). The described algorithms detect this.

• Case 2: G is solvable but not polycyclic. In this case the algorithm does not terminate.

The algorithm is able to calculate a constructive pc-sequence for I_{p}(G) and for K_{p}(G)^{ν}. Since K_{p}(G) is of finite index in G, K_{p}(G)^{ν} is a finitely generated abelian group and thus polycyclic. When we close the constructive pc-sequence of K_{p}(G)^{ν}, which is maybe uncomplete because we used only normal subgroup generators of K_{p}(G), under the conjugation action of G, we must finish after a finite number of steps. This is because every strictly ascending chain of subgroups of K_{p}(G)^{ν} is finite (see [20] Chapter 1 Section A.).

The calculation of a constructive pc-sequence for U_{p}(G) does not terminate. This is because we receive an infinite number of generators for U_{p}(G) when we try to close the set of normal subgroup generators for U_{p}(G) under the conjugation action of G.

7.4 A further possible refinement

Let G be a polycyclic subgroup of GL(d, R). Our aim is to describe a further method for the determination of a constructive polycyclic sequence of G. It has not been implemented so far.

Let

R^{d} = V_{0} > V_{1} ⋯ > V_{m} = 0

be a submodule series of the natural G-module R^{d}. We induce the action of G to this series

ν : G → G_{V_{0}/V_{1}} × ⋯ × G_{V_{m−1}/V_{m}}.

The image under this action G^{ν} is the direct product of polycyclic matrix groups of smaller dimension than d. The kernel under this action ker(ν) is an unipotent matrix group. With the algorithms described in Section 7.3 we can calculate a constructive pc-sequence for G_{V_{i}/V_{i+1}} for i = 0, …, m−1 and thus for G^{ν}. Then we calculate normal subgroup generators for ker(ν). Using these we calculate a constructive pc-sequence for the unipotent group ker(ν) (and close this pc-sequence under the conjugation action of G). Finally we combine the constructive pc-sequences of G^{ν} and ker(ν) to a constructive pc-sequence of G.

If R = ℚ we can use for example the radical series as the required submodule series ℚ^{d} = V_{0} > ⋯ > V_{m} = 0. It can be computed by the the algorithm of Section 6.4. If R = 𝔽_{q} we can use the Meataxe (see for example [17]) to calculate a submodule series with irreducible factors.

Performance

In this chapter we present the runtimes of the main algorithms of this thesis for some example groups. Further we give a short desription of the bottle necks of the algorithm for the determination of a constructive polycyclic sequence.

8.1 Runtimes

We outline the runtimes for the following algorithms.

• ConPcsFinite: Determination of a constructive polycyclic sequence for ψ_{p}(G), where G ≤ GL(d, ℚ) is the given group (see Section 3.3).

• IsSolvable: Test if the given group is solvable (see Section 7.2).

• ConPcs: Determination of a constructive polycyclic sequence for the given group (see Section 7.3.2).

• PcPresent: Calculation of a polycyclic presented group isomorphic to the given one (see Section 7.3.2 and Corollary 2.2.5).

Note that every algorithm in this list includes the preceding algorithms.

The following matrix groups are used as examples:

• G_{1} is the group generated by the matrices

( \begin{matrix}73/10 & −35/2 & 42/5 & 63/2 \\ 27/20 & −11/4 & 9/5 & 27/4 \\ −3/5 & 1 & −4/5 & −9 \\ −11/20 & 7/4 & −2/5 & 1/4 \end{matrix} ) , ( \begin{matrix}−42/5 & 423/10 & 27/5 & 479/10 \\ −23/10 & 227/20 & 13/10 & 231/20 \\ 14/5 & −63/5 & −4/5 & −79/5 \\ −1/10 & 9/20 & 1/10 & 37/20 \end{matrix} ) .

• G_{2} is the group generated by the matrices

( \begin{matrix}5 & 2 & −8 & 17 & −1 \\ −69/4 & −15/4 & 449/20 & −163/5 & 53/20 \\ −2 & 4 & 9/5 & 63/5 & 3/5 \\ 13/4 & 3/4 & −121/20 & 57/5 & −17/20 \\ 241/4 & 7/4 & −1477/20 & 319/5 & −189/20 \end{matrix} ) , ( \begin{matrix}19/2 & 0 & −3 & −19/2 & −1/2 \\ −74/5 & 129/20 & 7/4 & 159/4 & 9/10 \\ 53/10 & 4/5 & −4 & 9/2 & −9/10 \\ 37/10 & −41/20 & −7/4 & −29/4 & −3/5 \\ 137/5 & −457/20 & 37/4 & −559/4 & 3/10 \end{matrix} ) .

• G_{3} is the group generated by the matrices

( \begin{matrix}−492568055 & −715902540 & −559233360 & 913773168 \\ 853152732 & 1239979321 & 968620464 & −1582701120 \\ 796991748 & 1158354480 & 904858501 & −1478515764 \\ 543797628 & 790360020 & 617396520 & −1008810083 \end{matrix} ) ,

( \begin{matrix}−348686135 & −530151780 & −271469520 & 913773168 \\ −603941868 & −918249479 & −470198736 & 1582701120 \\ −215499732 & −327651600 & −167777219 & 564742596 \\ −793008492 & −1205711460 & −617396520 & 2078172517 \end{matrix} ) .

• G_{4} is a subgroup of GL(4, ℚ) with 5 generators. In GAP this group can

be found under AlmostCrystallographicGroup(4,2,[0,-3,-2,1,-1,-2,4])

as a part of the ’AcLib’-Package.

• G_{5} is a subgroup of GL(4, ℚ) with 5 generators. In GAP this group can

be found under AlmostCrystallographicGroup(4,86,[0,-2,-1,-2,-1])

as a part of the ’AcLib’-package.

• G_{6} is a subgroup of GL(16, ℤ) with 9 generators. In GAP this group can be found under PolExamples(5) as a part of the ’Polenta’-package.

• G_{7} is a subgroup of GL(16, ℚ) with 5 generators. In GAP this group can be found under PolExamples(24) as a part of the ’Polenta’- package.

The calculations were made on a Pentium 4 with 2 gigahertz under the system Linux. The runtimes are outlined in milliseconds.

Group G ConPcsFinite IsSolvable ConPcs PcPresent
G_{1}  10  50  300  490
G_{2}  10  150 26300  35890
G_{3}  10  20  190  240
G_{4}  10  170  2770  2950
G_{5}  20  170  1720  2060
G_{6}  830  9440 41530  57270
G_{7}  50  600 458330  479040

Note that the runtimes of two computations of a polycyclic presentation for the same group can differ. This is because during the algorithm some random choices are made, which can have a great influence on further computations. For example the orbits points, which are used in ConPcsFinite (see Section 3.1), are randomly choosen. Also the algorithm PrimitiveElement (see Section 6.5) uses randomized methods.

8.2 Bottle necks

The calculation of normal subgroup generators (see Section 7.1) of K_{p}(G) and U_{p}(G) produces matrices with much more complex entries in comparison with these of the input group. This slows down further computations. Further, we have to conjugate the group U_{p}(G) ≤ GL(d, ℚ) to a subgroup of UT (d, ℤ) (see Section 5.1). This operation increases the bit length of the matrix entries to a large extend. That is the reason why the computation of a constructive polycyclic sequence of U_{p}(G) is in the general the most time consuming step. For example the determination of a constructive polycyclic seqeuence of the group G_{7} costed in total 458 seconds. Just for the unipotent part U_{p}(G_{7}) the algoritm needed 450 seconds.

A further problem is, that the storage of the orbits used in the computations in the finite group ψ_{p}(G) (see Section 3.1) can cost too much memory. This happens for example for the wreath product G_{6} wr P ≤ GL(128, ℤ), where P is a polycyclic permutation group of order 8.

CHAPTER 8. PERFORMANCE  70

Bibliography

[1] Björn Assmann, Polenta - Polycyclic presentations for matrix groups - A GAP 4 package, http://cayley.math.nat.tubs.de/software/content.html, 2003.

[2] Robert Beals, Improved algorithms for the Tits alternative, Groups and Computation III (Columbus, OH, 1999), Ohio State Univ. Math. Res. Inst. Publ. 8, pages 63-77, de Gruyter Berlin 2001.

[3] Robert Beals, Towards polynomial time algorithms for matrix groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 28, 1997.

[4] Henri Cohen: A course in computational algbraic number theory, Springer Verlag 1993.

[5] John D. Dixon: The orbit-stabilizer problem for linear groups, Can. J. Math., Vol. 17, No. 2, pages 238-259, 1985.

[6] Bettina Eick, Algorithms for Polycyclic Groups, Habilitationsschrift, Kassel 2001.

[7] Bettina Eick and Björn Assmann, Alnuth - A GAP package containing methods for number fields and an interface to KANT, http://cayley.math.nat.tu-bs.de/software/content.html, 2003.

[8] Bettina Eick and Werner Nickel, Polycyclic - Computation with polycyclic groups. A GAP 4 package, http://cayley.math.nat.tubs.de/software/content.html, 2003.

[9] Martin Isaacs, Character Theory of finite groups, Dover Publications Inc. New York, 1994.

[10] The KANT Group, KANT - Computational Algebraic Number Theory, http://www.math.tu-berlin.de/∼kant/kash.html, 2003.

[11] Serge Lang, Algebra, Addison-Wesley, 1993.

[12] E.M. Luks: Computing in solvable matrix groups, In Proc. 33rd IEEE Sympos. Foundations Comp. Sci., pages 111-120, 1992.

[13] W. Müller: Darstellungtheorie von endlichen Gruppen, Teubner Stuttgart 1980.

[14] Gretchen Ostheimer: Algorithms for polycyclic-by-Finte Groups, Phd Thesis, Rutgers University, Math. Dept., 1996.

[15] Gretchen Ostheimer: Practical Algorithms for Polycyclic Matrix Groups, J. Symbolic Computation 11, 1-000, 2001.

[16] M. F. Newman: The soluble length of soluble linear groups, Math. Z., 126, pages 59-70, 1972

[17] R. Parker: The computer calculation of modular characters. (The Meataxe), in M. Atkinson (ed.), Computational Group Theory, Academic Press, London, pages 267-74, 1984.

[18] Micheal E. Pohst:Computational Algebraic Number Theory, DMV Seminar Band 21, Birkhäuser 1993.

[19] D.J.S. Robinson: A course in the Theory of Groups, volume 80 of Graduate Texts in Math., Springer Verlag, New York, Heidelberg, Berlin 1982.

[20] Daniel Segal: Polycyclic groups, Cambridge University Press, 1983.

[21] Charles C. Sims: Computation with finitely presented groups, Cambrigde University Press, 1994.

[22] Charles C. Sims: Computing the Order of a Solvable Permutation Group, J. Symbolic Computation 9, 699-705, 1990.

[23] Ian Stewart and David Tall: Algebraic number theory and Fermat’s last theorem, A K Peters 2002.

[24] The GAP Group, GAP - Groups, Algorithms and Programming, http://www.gap-system.org, 2003.

[25] B. A. F. Wehrfritz: Infinite linear groups, Springer-Verlag, New York, Heidelberg, Berlin 1973.