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 they can be used to isolate roots of polynomials and to estimate the maximum and minimum value reached by a polynomial. A number of other researchers have formalised this material; machine proofs in other systems (PVS and Coq) exist. Isabelle already contains a small formalisation of Bernstein polynomials, but additional propositions could be proved. They can also be used as the basic for decision procedures, provided time is available.
Infinitesimal Geometry and Newton's Principia Mathematica
During the 1990s, Jacques Fleuriot used Isabelle to formalise some theorems from Isaac Newton's great volume, which developed the mathematical theory of gravity and the orbits of the planets. Where Newton used geometrical arguments involving infinitesimals and other unusual methods, Fleuriot used an axiomatic system for geometry coupled with a formalisation of non-standard analysis. His Ph.D. research gave a rigorous basis to Newton's apparently imprecise use of infinitesimal reasoning, and won a national award. He even found an error in one of Newton's proofs.
The proposal is to redo some of this work using Isabelle as it is now and using a neater axiomatic basis for geometry, proposed by Fleuriot himself. The project will be an unusual combination of interactive theorem proving and the history of science. Isabelle's existing formalisation of non-standard analysis will be used, so the project will be concerned with formalising geometric concepts and applying them to some of Newton's proofs, starting with those treated by Fleuriot.
Mechanised Number Theory
Wilson's theorem and Gauss's law of quadratic reciprocity are two beautiful, fundamental results in number theory. The former states that (n-1)! is congruent to -1 mod n, while the latter gives conditions for the equation x2 = q mod p to have solutions. The project is to formalise these or related results. In fact, Isabelle formalisations of the two theorems mentioned above exist already, but they are very messy, and achieving elegance in proofs is a desirable skill to acquire.
Mechanised Computability Theory
Michael Norrish has recently published some beautiful proofs concerning computability theory (covering the general recursive functions and the λ-calculus), proving results such as the Recursion Theorem and Rice’s Theorem. He did his work using HOL4. The project is to develop some of the same material using Isabelle/HOL.
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, 55 of them had been formalised in Isabelle, the top system being HOL Light at 86.
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.