ACS Project Proposals by Prof L C Paulson
Each of these proposals involves formalising mathematics using the proof assistant Isabelle/HOL. Such projects will suit students who have a mathematical background, especially if they are already familiar with the theorems that they choose to formalise.
Bernstein Coefficients and Polynomials
Bernstein polynomials have many applications in mathematics and computer science. They underlie Bézier curves and can be used to isolate roots of polynomials and estimate the maximum and minimum value retained by polynomials. A number of other researchers have formalised this material, and detailed outlines of machine proofs in other systems (PVS and Coq) are available. There are three main propositions to prove in this theory, and if time is available, applications could be developed.
A Library of Identities for Binomial Coefficients
The book Concrete Mathematics by Graham, Knuth and Patashnik includes 90 pages of material covering binomial coefficients and the dozens of beautiful identities that they satisfy. This material begins with laws that could be proved by induction and proceeds to increasingly advanced mathematical methods. This project provide experience with a variety of useful mathematical techniques, and the source material is very clear.
Formalising Basic Group Theory
The notion of a group has already been formalised in Isabelle/HOL, as well as a few nontrivial results, such as Sylow's theorem. There is much more that could be done, in particular, to investigate the strengths and weaknesses of the way mathematical abstraction is handled in this formalisation. Even the identification of weaknesses will be a useful outcome of this project, better still if an improved formalisation can be identified.
A Formalisation of Information Theory
Shannon's information theory is fundamental to many aspects of computer science, including cryptography, coding theory, data transmission and compression. It rests on an elaborate mathematical basis that includes integration theory, measure theory and probability theory. Most of this foundation has already been laid: a simple formalisation of information theory already exists in Isabelle. However, many of the fundamental theorems of information theory have yet to be formalised. A paper describing similar work conducted using the Coq system illustrates some of the tasks to be undertaken. Note that Coq proofs cannot easily be ported to Isabelle, because the logical formalisms are very different.
Formalising the Top 100 Theorems using Isabelle
There is an online list of 100 well-known mathematical theorems, and a separate list indicating how many of these have been formalised in a variety of different interactive theorem provers. As of this writing, 49 of them had been formalised in Isabelle, the top system being HOL Light at 85.
The project is merely to identify and prove (using Isabelle) a selection of the not-yet-formalised theorems. The selection needs to be done with care, since typically a theorem is proved in the context of possibly a very substantial theory, which would also have to be developed by proof rather than assumed as a collection of axioms. It is also possible to include theorems that have been proved already, using a different proof. (Some theorems have several substantially different proofs.) It is acceptable to follow an existing HOL Light formalisation, but more interesting is to formalise a textbook development.
It is equally acceptable to formalise interesting theorems not on that list, such as Goodstein's theorem.