Elektrine lite

← Feed

@antoinechambertloir@mathstodon.xyz

2026-09-11 19:46 UTC

#Math #AI 19/n One such example was the formalization, by Georges Gonthier, of the proof by Appel and Haken of the four colour theorem. This theorem says that if you draw a map on sheet of papers, with as many countries as you wish (but countries need to consist of only one piece, no islands nor colonies here), then it is possible to draw countries with only four colours so that countries sharing a common boundary have distinct colors. The history of that theorem is really surprising. It was proved in 19th century, but it took 10 years to observe that the given proof was wrong. It was relatively easy to show that 5 colors indeed suffice, and several new wrong proofs appeared in 20th century. Only in 1976 did Appel and Haken propose a working proof, but that proof used a computer program to enumerate a large number of configurations, which another program could solve effectively, the theorem being that this long list of examples was sufficient to conclude. Several problems arise at once: how can we be sure that the first computer program actually generates all configurations described by the mathematical theorem, and does not miss any, and how can be be sure that all of them are treated correctly? The list is so long that no single human, nor any small group of humans, could check all of them, what we need is really a third computer program that will certify the combination of the mathematical proof, the configuration generator, and the solution for each generated configuration.

Replies (1)

  • #Math #AI 20/n This is what Georges Gonthier did in 2008, thus bringing a definitive certainty to the solution of that long-standing question. In fact, Gonthier discovered that the proof didn't really work, but he could make the argument work. I should (and will) ask Gonthier about his underlying motivation, but my understanding is that, as one of the developers of the proof assistant Coq (now named Rocq), he wished to prove the mathematical community that the technology was mature enough to tackle spectacularly long proofs. Another reason is that Coq/Rocq is also the basis for a purely computer science activity that is very close to checking mathematical proofs, namely checking computer programs, and this has applications in industry.

    Open ##5153669