A Pragmatic Approach to Extending Provers by Computer Algebra — with Applications to Coding Theory

Abstract

The use of computer algebra is usually considered beneficial for mechanised reasoning in mathematical domains. We present a case study, in the application domain of coding theory, that supports this claim: the mechanised proofs depend on non-trivial algorithms from computer algebra and increase the reasoning power of the theorem prover. The unsoundness of computer algebra systems is a major problem in interfacing them to theorem provers. Our approach to obtaining a sound overall system is not blanket distrust but based on the distinction between algorithms we call sound and ad hoc respectively. This distinction is blurred in most computer algebra systems. Our experimental interface therefore uses a computer algebra library. It is based on formal specifications for the algorithms, and links the computer algebra library Sumit to the prover Isabelle. We give details of the interface, the use of the computer algebra system on the tactic-level of Isabelle and its integration into proof procedures.