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.

A subset A of a semigroup S (with operation multiplication) generates
S if every element of S

can be written as a product of elements of A. A relation is an expression
of the form

a_1...a_m = b_1...b_n where the a´s and b´s belong to A.
For example, if S is commutative,

then the relation ab = ba holds for all a and b in A.

Given a set A and a set R of relations, there is a unique semigroup
T with generators A such

that all the relations in R are true in T, and every relation which
holds in T is a consequence

of those in R. This has to be made precise and be proved. We say that
< A : R > is a presentation for T.

Here are two examples:

1. < a,b : a^2 = a, b^2 = b, ab = ba > is a presentation for

the three element semigroup {a,b,c} with multiplication table

a b c

a a c c

b c b c

c c c c

2. < a,b :ab 0 ba > is a presentaion for the infinite semigroup

{a^mb^n : m,n are non-negative integers, not both zero} with

product (a^mb^n)(a^hb^k) = a^{m+h}b^{n+k}.

As the second example shows, presentations allow some infinite semigroups
to be defined

by a finite amount of information.

In the first part of the project, you will develop the (easy)
ideas needed to prove the claim

in the second paragraph. In the second part of the project, you will
examine some semigroup

constructions and how to find presentations for the constructed semigroups
from presentations

of their constituent parts.

**Prerequisite**: Semigroup Theory (054503)

**Preliminary Reading**: Fundamentals of Semigroup Theory by J.M.Howie.

For basic ideas, see Section 1.1; for an introduction to presentations
see Section 1.6;

for some constructions, see p.70 for Rees matrix semigroups, pp105/106
for semilattices

of semigroups, and p.171 for Bruck-Reilly extensions.

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.