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.