A set *X* of natural numbers written in base *p* is
*p-recognisable* if there is a finite state automaton which
recognises *X*. In the project you will consider several alternative
characterisations of *p*-recognisable sets of numbers. Further work
would lead in the direction of Cobham's theorem which states that a set
*X* of natural numbers is *p*-recognisable and
*q*-recognisable for independent *p* and *q* (that is,
neither is a power of the other) if and only if *X* is ultimately
periodic, that is, if and only if *X* is a finite union of arithmetic
progressions.

**Prerequisite**: Formal Languages and Automata (059208)

**References:**
For basic ideas about finite state automata

P Linz, *An introduction to formal languages and automata* (SK
1 LIN).

Further relevant references will be provided when the
project is started.

How can one describe a group? One way which has proved very useful is to use `generators and relations'. A set of generators for a group G is a subset of G such that every element of G can be written as a product of integer powers of the generators. In such a product, a given generator may occur in several positions since we do not assume commutativity. However, there may be some `relations' which hold among the generators which allow the expressions for general elements to be simplified. For example, if a,b,c are generators and we have ba = ac and ca = ac, then any product of powers of generators is equal to one which has only one power of a as a leftmost factor. If we are given `generators and relations' for a group, we say that we have a presention for the group; the word problem for a presentation asks whether we can decide when a product of powers of generators is equal to the identity of the group. To formalise these ideas we first have to study some infinite groups called free groups. Preliminary reading might be the appropriate sections in the first reference.

**Prerequisite**:
Groups and Rings (059019)

(for MMath students) Advanced Algebra (059406)

**References:**

J.B.Fraleigh, A First Course in Abstract Algebra

J.J.Rotman, The Theory of Groups: An Introduction

This project continues from the group theory part of the course
*Advanced Algebra*. As explained in the course, the finite simple
groups form the building blocks from which all finite groups are made.
The idea of the project is to find out more about some of the
nonabelian finite simple groups mentioned in the course, and to prove that
they are actually
simple. As well as the alternating groups, the projective special linear
groups and the Mathieu groups will be considered.

**Prerequisite**: Advanced Algebra (059406)

**Reference:**

J F Humphries, *A Course in Group Theory.*

This project continues from the ring theory part of the course
*Advanced Algebra*. The rings considered are the rings of integers
in quadratic number fields rather than the fields themselves. In the
project
you will look at the problem of when the ring of integers a
unique factorisation domain. This is not always the case, and this leads
to the consideration of ideals. It is the case that every proper
non-zero ideal is a product of prime ideals. For those rings which are
not principal ideals, there is the question of the relation between
prime ideals and prime integers. From this point the project might
consider the abstract approach to commutative rings in which every proper
non-zero ideal is a product of prime ideals, or investigate a group
called the ideal class group whose elements are equivalence classes of
ideals.

**Prerequisite**: Advanced Algebra (059406)

**Reference:**

M Artin, *Algebra* (Chapter 11).

At the beginning of the twentieth century, David Hilbert, one of the
leading mathematicians of the time, proposed that it should be possible
to decide all arithmetical
truths algorithmically from first order logic together with axioms for
the natural numbers. This proposal collapsed in 1931 with the publication of
Godel's "incompleteness theorem". Much effort in the 1930s was devoted
to the question of what an algorithm actually is. One answer, due to
Alan Turing, led to the notion of what we now call a Turing machine. In
the project you will give an account of Turing machines, and consider
several undecidable problems, and some decidable ones.

J E Hopcroft, R Motwani and J D Ullman, *Introduction to automata theory, languages,
and computation* (S 9.9 HOP).

P Linz, *An introduction to formal languages and automata* (SK
1 LIN).

An *algorithm* or *effective procedure* is a mechanical
rule, or automatic method, or programme for performing some mathematical
operation. In 1936, Turing introduced what are now known as
*Turing machines* to formalise this idea. The notion was first
used to prove that there are some mathematical problems for which no
algorithms exist to solve the problem. With the advent of computers,
it was realised that a Turing machine is, in some ways, a reasonable
model of a general purpose computer. However, even when a problem is
algorithmically solvable in principle, it may not be solvable in
practice, if the algorithm requires a vast amount of time or memory.
The theory of computational complexity is the investigation of the time,
or memory required for solving computational problems. The theory leads
to many *complexity classes* of problems. Which complexity class
a problem is in is regarded as a measure of the difficulty of solving
the problem. Two famous classes are P (problems decidable in polynomial
time) and NP (problems decidable in nondeterministic polynomial
time). Describing exactly what these two phrases mean will be part of
the project. It is unknown whether or not P=NP, and this has been an
outstanding problem for many years. You do not have to solve the problem
in your project, but if you do there is a prize of a million dollars.

**References:**

J E Hopcroft, R Motwani and J D Ullman, *Introduction to automata
theory, languages, and computation* (S 9.9 HOP).

P Linz, *An introduction to formal languages and automata* (SK
1 LIN).

M.R.Garey and D.S.Johnson, *Computers and
Intractability: A Guide
to the Theory of NP-Completeness* (SK1 GAR).

If *f,g* are polynomials with coefficients in a field *F*,
then one can use the Euclidean algorithm to find their highest common
factor, say *d*. Then the ideal *I* generated by *f* and
*g* is equal to the principal ideal generated by *d*, and one
can test
for membership of *I* by dividing by *d* and seeing if the
remainder is zero. Groebner bases and the algorithm to find them devised
by Buchberger extend these ideas to polynomials in several variables.
Thus if *R* is the polynomial ring in *n* variables, and
*I* is the ideal generated by some polynomials *f,g,...*, then
the algorithm finds a generating set (a Groebner basis) for *I* such
that a polynomial *h* is in *I* if and only if each of the
polynomials in the Groebner basis is a factor of *h*. In the
project, you will explain these ideas more fully, and calculate some
Groebner bases, either by hand or by computer.

**Prerequisite**: Groups and Rings (059019) (for BA/BSc students);
Advanced Algebra (059406) (for MMath students)

**Reference:**

J J Rotman, *A First Course in Abstract Algebra* (Section 6.5)

Further references will be provided when the project is in progress.

Change ringing is the practice, more common in England than
elsewhere, of ringing a set of *n* bells in all possible orders.
However, this is not done in an arbitrary way. A *change* consists
of ringing the *n* bells once each in some order. Thus if the
*n* bells are labelled *1,2,...,n*, then a change corresponds
to a permutation of *1,2,...,n*. An *extent* consists of
*n!+1* successive changes which satisfy certain conditions, one being
that every permutation of *1,2,...,n* appears in the extent.
Studying extents leads to consideration of coset decompositions of the
symmetric group of degree *n* with respect to a suitable subgroup.
The project will essentially be an exposition of this connection with
some calculations for small *n*. Only elementary notions from group
theory are needed, namely subgroups and cosets.