84
$\begingroup$

I probably don't have the appropriate background to even ask this question. I know next to nothing about formal or computer-aided proof, and very little even about group theory. And this question is more "tech support" than math.

But: after reading that Georges Gonthier and collaborators had formalized a proof of the Feit-Thompson theorem in Coq, I thought it would be fun to try to verify it on my own computer.

So I installed Coq (8.4pl2), OCaml, etc, on my Ubuntu box, and then went here and downloaded feit_thompson.tar.gz (v2.0). I unpacked it and ran make. It ran various invocations of coqc for about two hours, and then finished with no error reported. A bunch of .vo files were produced, including one for theories/stripped_odd_order_theorem.v, which even the casual observer can see contains what appears to be a statement of the Feit-Thompson theorem.

Is that it? Does that mean that Coq agrees with the correctness of the proof? Or are there more steps?

I was particularly curious because I saw that Makefile.coq has a validate target (which isn't run by just doing make). So I ran make -f Makefile.coq validate. This started a coqchk command which ran for about five minutes and then failed with:

 User error: Signature components for label fun_of_fin do not match
 make: *** [validate] Error 1

Was I not supposed to do that? Or did I just find a flaw in their proof? :-)

Again, I freely admit that I do not really know what I'm doing. In particular, it's not clear to me whether compilation of a Coq file actually verifies the theorems and proofs within it, or merely prepares it for later validation. If an expert answers "Go away until you understand Coq" I'll meekly accept it. But it does seem like it might be helpful for even a newbie to be able to understand how to properly run Coq on a proof created by someone else, and I couldn't find documentation that clearly explained it.

Improve this question
$\endgroup$
21
  • 26
    $\begingroup$ I like this question, and would defend it against potential voters-to-close (saying "ask in a Coq forum") by saying that this is the sort of activity (downloading and stepping through a proof certificate) that the proof assistant community, and others in the pure mathematics community (e.g. Voevodsky) are hoping would be the standard method of checking a proof in mathematics in the future. $\endgroup$
    – David Roberts ♦
    Commented May 2, 2014 at 3:19
  • 9
    $\begingroup$ I'm not going to vote to close, but I don't think MO is the right place for this sort of question in the long run. Questions about how to express a proof in a way understandable to Coq or about the limitations of Coq seem germane, but we should probably find another home for tech support questions like this for the same reason that we don't typically allow Latex or Mathematica questions. $\endgroup$
    – Paul Siegel
    Commented May 2, 2014 at 3:41
  • 11
    $\begingroup$ It has long been agreed that the non-existence of a Q&A site for subject X is not reason for X to be on topic here, btw. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented May 2, 2014 at 5:16
  • 6
    $\begingroup$ @MarianoSuárez-Alvarez: The coq mailing list is a good idea, though it seems more aimed at formal proof experts than newbie working mathematicians. I thought an answer to this question might be useful information for the MO community; there have been several previous questions here about Coq and they were generally well received. As far as asking the authors, I certainly could, but in principle the goal is for me to be able to verify the proof independently; I don't want to have to take the author's word for how to do it. $\endgroup$
    – Nate Eldredge
    Commented May 2, 2014 at 5:19
  • 3
    $\begingroup$ Since this question got bumped, let me mention in a comment here that there is now a Proof Assistant Stack Exchange: proofassistants.stackexchange.com. Future questions like this one would be more appropriate there. $\endgroup$
    – Sam Hopkins
    Commented May 9 at 14:30

3 Answers 3

Reset to default
56
$\begingroup$

The error you get is a real one, but is not in the proof of the odd order theorem. It is in Coq. Let me be more clear: a bug in the kernel of Coq was making the .vo files (the files coqchk checks) incomplete. Some universe constraints coming from module sub typing were forgotten. coqchk correctly spots it, and actually revealed the bug I fixed a while ago. A patchlevel release of Coq including the fix is already on its way.

The bugreport: https://coq.inria.fr/bugs/show_bug.cgi?id=3243

The commit that fixed the bug: https://github.com/coq/coq/commit/a07deb4eac1d5f886159784ef5d8d006892be547

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Many thanks, I don't know how I would have found that myself. So just to be clear, the compilation alone did not verify the proof? $\endgroup$
    – Nate Eldredge
    Commented May 2, 2014 at 16:55
  • 18
    $\begingroup$ @NateEldredge I believe the way to understand this is: make checked the proof, and compiled it to an optimized version; however, because the compilation phase was buggy, the optimized version was not a correct proof. When you ran make validate, coqchk tried to check the optimized proof, but barfed because the optimized proof produced by Coq earlier was not an accurate reflection of the original proof. $\endgroup$
    – Daniel Wagner
    Commented May 2, 2014 at 18:45
  • 1
    $\begingroup$ @DanielWagner: Thanks, that makes it very clear. $\endgroup$
    – Nate Eldredge
    Commented May 2, 2014 at 18:56
30
$\begingroup$

Following Enrico Tassi's answer, I compiled the current snapshot of Coq 8.4pl4 from https://github.com/coq/coq. With it, I was able to successfully compile and validate the proof.

 Modules were successfully checked

What an impressive piece of work!

Improve this answer
$\endgroup$
2
  • $\begingroup$ What does it do/look like when you validate the proof? $\endgroup$
    – David Roberts ♦
    Commented May 3, 2014 at 1:56
  • 9
    $\begingroup$ @DavidRoberts: At the end of make validate it prints the Modules were successfully checked message, and a list of the axioms used. (By default it runs with -silent; I turned that off so I also got a running list of the theorems/lemmas as they were verified. It took about one hour to run.) $\endgroup$
    – Nate Eldredge
    Commented May 3, 2014 at 2:21
27
$\begingroup$

To convince yourself that the proof is indeed valid, you need to do at least two things:

  • read and understand the definitions as well as the theorem statement thus knowing for a fact that the proof is indeed a proof of the right theorem;

  • check the development using a proofchecker you trust.

Now, that second part can be a bit tricky: coqc is quite a big piece of code allowing the use of plugins, the definition of custom tactics, etc. That's why a standalone checker coqchk exists: it can only deal with compiled files (i.e. raw proof terms) and therefore is much simpler thus making it easier to review its code.

It is bothering that coqchk fails on this development. It would be worth mentioning either on coq's bug tracker or on the ML.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .