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.
The Four Colour Map Theorem
This celebrated theorem was first proved in 1976 with the help of a computer program to check nearly 2000 cases. Mathematicians did not like the idea of a proof checked by code, but Georges Gonthier's 2008 formalisation using the Coq proof assistant definitively established the result. The proof still involved a computer program checking numerous cases, but the program had been generated and proved to be correct within Coq itself.
The four colour proof is too big to be tackled as a single ACS project, but Gonthier has helpfully broken it down into modules, any one of which would be suitable:
- The theory of planar hypermaps, up to the combinatorial Jordan Curve theorem (both ways), configuration cut-and-paste, and maybe configuration isomorphism. (This foundational material is also relevant to the Flyspeck Project.)
- The reducibility procedure, verified against an abstract notion of reducibility (plus possibly unverified colouring generation).
- The reduction to a combinatorial problem, which involves some real topology.
Gonthier's full report on his work explains the necessary mathematics.
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.
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.