Abstract:
This aim of this report is to explain the theory of finitely generated abelian groups, and
some computational methods pertaining to them. Knowledge of introductory group theory
is required to understand the main ideas.
There is no algorithm to determine if a given finite presentation defines a group of
finite order (or even defines the trivial group). However, such an algorithm exists if the
group is also known to be abelian. We give a procedure in this report which, given a
description of a finitely generated abelian group G, calculates integers d1,...,dr, k such
that G ≥= Zd1 ü ··· ü Zdr ü Zk. The description of G is given by an integer matrix, which
we transform into a diagonal matrix, known as its Smith Normal Form.
Naive algorithms inspired by Gaussian elimination often fail because of integer overflow.
Intermediate matrices have entries which are very large even for relatively small inputs,
making calculations in practice far too expensive to carry out. We will explore some useful
techniques, which allow us to perform calculations with respect to an appropriate modulus.