Prolog, constraint programming and algebra

My collaborators and I have written two recent papers which are intended to demonstrate that logic and constraint programming are tools which need to be better known and more widely deployed in pure mathematics. In both cases we used Sicstus Prolog and its CLP(FD) library.

The first paper classified a certain type of simple Lie algebra over the field GF(2) up to dimension 31. At an elementary level, this question boils down to filling out a 31x31 matrix with zeros and ones, subject to a series of constraints which enforce the Lie algebra structure and also the more complicated matter of insisting that it should be simple. It also collapses the Lie algebras into isomorphism classes by deploying a fairly sophisticated technique called toral switching.

It is worth saying that attempting to solve this problem by brute force is completely absurd. Prima facie, the number of 31x31 matrices is 2^{961}; this is many orders of magnitude bigger than the number of atoms in the observable universe. In other words, the success of this approach caused us to be extremely surprised by the power of Prolog's constraint handling.

We wanted to see how Prolog would handle a problem in another field of mathematics. Happily, we came across an unsolved problem in combinatorics which had a direct application to the UK national lottery, which resulted in \cite{CS23}. The problem is to find the minimum number of tickets you need to buy before a particular lottery draw so as to guarantee that no matter what numbers come up, at least one of your tickets will match at least two balls from the draw. In case there are 59 balls---as in the UK national lottery---the answer turns out to be that you need 27 tickets. (Of course you have to choose them rather carefully.)

Our lottery paper generated an enormous amount of media interest: national and international newspapers, radio interviews and so on---perhaps the highlight was seeing David Cushing describing our work on the US news network NBC Now. The prominent public science communicator Matt Parker made a great video about our work that you can watch here: https://www.youtube.com/watch?v=zYkmIxS4ksA.

Prolog is thought of by some as a 50 year-old AI predecessor, though it has typically been at the fringe of academic and industrial interest. That is currently changing and Prolog is being applied to problems as diverse as train scheduling, language processing, government grant assessment, and now also pure mathematics. Prolog is an extremely natural environment in which to approach classification questions in pure mathematics.

This project is about finding ways to better focus Prolog towards pure mathematics and to demonstrate the efficacy of the innovations through applications to problems therein.

Principally, I believe that what is needed is the integration of Prolog's rewriting capacities (for example through definite clause grammars) with the constraint programming library. Prolog needs to be capable of rewriting constraints dynamically through substitution and other algebraic manipulations. So there can be a serious coding component to the problem, which needs an understanding and sensitivity to algebraic methods and algorithms.

The coding side of the project can be balanced against finding solutions to mathematics problems using constraint programming. The creativity here would be to find ways to express mathematical problems through constraints. At least one major task in this direction would be to implement finite fields in Prolog. I also suspect that certain calculations with permutation groups may hugely benefit from interfacing with constraints; in particular, the calculation of (co)homology groups seems ideal for contraint solving.

Eligibility

Applicants should have, or expect to achieve, at least a 2.1 honours degree or a master’s (or international equivalent) in a relevant science or engineering related discipline.

Funding

At Manchester we offer a range of scholarships, studentships and awards at university, faculty and department level, to support both UK and overseas postgraduate researchers applying for competition and self-funded projects.

For more information, visit our funding page or search our funding database for specific scholarships, studentships and awards you may be eligible for.

Before you apply

We strongly recommend that you contact the supervisor(s) for this project before you apply.

How to apply

Apply online through our website: https://uom.link/pgr-apply-fap

When applying, you’ll need to specify the full name of this project, the name of your supervisor, if you already having funding or if you wish to be considered for available funding through the university, details of your previous study, and names and contact details of two referees.

Your application will not be processed without all of the required documents submitted at the time of application, and we cannot accept responsibility for late or missed deadlines. Incomplete applications will not be considered.

After you have applied you will be asked to upload the following supporting documents:

• Final Transcript and certificates of all awarded university level qualifications
• Interim Transcript of any university level qualifications in progress
• CV
• Contact details for two referees (please make sure that the contact email you provide is an official university/work email address as we may need to verify the reference)
• English Language certificate (if applicable)

If you have any questions about making an application, please contact our admissions team by emailing [Email Address Removed].

Equality, diversity and inclusion is fundamental to the success of The University of Manchester, and is at the heart of all of our activities. We know that diversity strengthens our research community, leading to enhanced research creativity, productivity and quality, and societal and economic impact.

We actively encourage applicants from diverse career paths and backgrounds and from all sections of the community, regardless of age, disability, ethnicity, gender, gender expression, sexual orientation and transgender status.

We also support applications from those returning from a career break or other roles. We consider offering flexible study arrangements (including part-time: 50%, 60% or 80%, depending on the project/funder).