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.