# 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. (*Note*: Prof Paulson will be on sabbatical for 2017/18.)

## 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.

## 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.

## 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, 76 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 prove 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.

Or formalise interesting theorems not on that list, such as Goodstein's theorem. Another source of examples is the text *Proofs from THE BOOK* by Aigner and Ziegler.