Generic Proof Tools and Finite Group Theory

Abstract : This thesis presents advances in the use of Canonical Structures, a programming language construct of the Coq proof assistant equivalent to the notion of type classes. It provides a new model for developping hierarchies of mathematical structures using dependent records, and, as an illustration, reformulates the common formal proof of the correctness of the RSA cryptosystem, providing facilities for algebraic reasoning along with a formalization in type theory of the necessary mathematical notions (including cyclic groups, automorphism groups, group isomorphisms). We provide an extension of the Canonical Structure inference mechanism using phantom types, and apply it to treating the notion of partial functions. Next, we consider a generic treatment of several forms of subgroup definitions occurring in the formalization of the Feit-Thompson theorem, a large library of fomalized algebra developed in the Mathematical Components team at the MSR-INRIA joint laboratory. We show that a unified treatment of those 16 subgroups allows us to shorten menial proofs and obtain more composable definitions. We formalize a correspondence between the study of those group functorials, and some common and useful group-theoretic properties represented as the class of groups verifying them. We conclude in exploring the possibilities for analyzing the functoriality of those definitions by inspecting their type, and suggest a path towards obtaining instances of a parametricity result in Coq.
Document type :
Logic in Computer Science [cs.LO]. Ecole Polytechnique X, 2011. English
Contributor : François Garillot <>
Submitted on : Thursday, January 12, 2012 - 11:18:47 AM
Last modification on : Tuesday, July 28, 2015 - 12:58:17 PM
Document(s) archivé(s) le : Monday, November 19, 2012 - 1:20:09 PM


  • HAL Id : pastel-00649586, version 1



François Garillot. Generic Proof Tools and Finite Group Theory. Logic in Computer Science [cs.LO]. Ecole Polytechnique X, 2011. English. <pastel-00649586>




Record views


Document downloads