Wednesday, March 04, 2026

The Purpose of Proofs

In discussions of AI and Mathematics, the discussion often goes to mathematical proofs, such as the the First Proof challenge. So let's look at the role of proofs in mathematics.

Without a proof, you don't even know whether a theorem is true or false. It's not even a theorem until you have a proof, just a conjecture or hypothesis. You might have some intuition but you don't know the hardness of a proof until you find it. Even then that only gives you an upper bound on hardness as someone might find a simpler alternative proof in the future,

Proofs give an understanding of why a theorem is true. A proof can look like a piece of art, especially if the proof works in a new or clever way, maybe even a proof from the book like Kelly's Proof of the Sylvester–Gallai theorem. A mathematician often has their most satisfying experiences finding a proof of a theorem they or others have had challenge proving earlier.

Conjectures drive the need for proofs, but often it goes the other direction. A failed proof leads to a new conjecture and maybe a different theorem altogether. My time-space tradeoffs came out of a failed attempt to show NP different from L. Too often I see papers with theorems that are really just what the best proof they can find achieves.

Proofs are supposedly objective, either it is a valid proof or it isn't, the biggest reason AI tackles proofs as we can grade them as right or wrong. Most academic papers have high-level proofs and a referee however needs to make a subjective decision whether the proof has enough details to count as a legitimate proofs. If a proof has minor fixable errors, then it isn't a proof but we usually count it as one.

Now we have proof systems like Lean where we can make proofs truly objective. There's a large mathlib project to formalize much of mathematics in Lean, and talk of a cslib as well. 

Lean excites me less, I'm not sure what we gain by formalizing proofs besides certainty. Will Fermat's last theorem be any more true once we formalize it? One could argue Lean also helps AI reason about mathematics in a grounded way, though could AI just get lost in the logical weeds?

I worry about the heavy task of converting proofs to Lean, even with AI help, takes away from time spent finding and proving new theorems and we lose the beauty of the proofs. If there was a fully lean verified proof of P ≠ NP that you couldn't understand, would you find that satisfying?

4 comments:

  1. Terry Tao in his 2025 Joint Math Meetings talk describes two values of the process. After formalizing their cutting-edge polynomial Freiman-Rusza proof: (1) when they got a suggestion to improve a small early piece of the proof, the formalization allowed them to instantly derive the result with an improved final constant (2) They had used some heavyweight theorem in their original proof, which wasn't yet formalized in Lean - the process forced one of the contributors to the Lean formalization to find a simpler argument that used something previously formalized to replace this heavyweight piece.

    Alex Kontorovich makes an even stronger case for the value of converting proofs to Lean. In one video (I can't recall which one) he describes the beginnings of formalizing complex analysis and discusses a new proof of the Cauchy Integral Theorem that came out of this process. The standard statement requires that the origin be inside the closed curve, which would have required the Jordan Curve Theorem to formalize and even specifying closed curves for Lean can only be done approximately. They realized that integration around rectangles could be specified quite trivially, and the integral over the sum of two adjoining rectilinear curves could be specified quite trivially as can the notions of interior and exterior. Finally, you can essentially express a closed curve as a limit of some sequence of rectilinear curves. This is a fundamentally new proof and is arguably closer to a "Proof from the Book" than any involving messy proofs of the Jordan Curve Theorem.

    ReplyDelete
  2. A very interesting topic. Thank you for blogging about it.

    Part of the reason mathematicians are moving towards formal verification of proofs is because they are getting too complicated for humans to even check that they are correct. That is why e.g. HoTT was created.

    I think the idea gained more traction with AI, cause you need proof verification for systems for math like those that won IMO medals. Without the verifier the system would not perform well.

    Can we replace them with an informal proof assessor? Maybe, but right now those things don't work very well.

    ReplyDelete
  3. If P!=NP, and someone and/or something finds a proof of that, then it seems to me like there's slightly more chance that we'll be able to understand it. Why? Because the statement "P!=NP" is a lot like the statement "proofs are easier to check than to find"...

    So, possibly even if such a proof is really complicated (and/or is an automatically-found Lean-checked proof), and difficult to find, maybe understanding/checking the proof would be simpler? Given how difficult the question seems, I'd guess that understanding such a proof might well still be really difficult.

    But I'm amused that the P vs NP question seems slightly different from, say, some unsolved number theory question, which (presumably) doesn't say anything about whether understanding the proof is easier than finding it...


    ReplyDelete
  4. https://vixra.org/abs/2601.0107

    We introduce a paradox, which we named it Friendship Paradox:
    "EVERY lady chooses less attractive lady as a friend. If so, why opposite, those less attractive lady is a friend of those more attractive lady? Contradiction."

    ReplyDelete