logoalt Hacker News

Interpreting claims that a theorem is correct because it was checked in Lean

282 points • by matt_d • yesterday at 7:38 AM • 129 comments • view on HN

Comments

Legend2440 • yesterday at 1:39 PM

Worth pointing out that this article is by Kevin Buzzard, one of the biggest advocates for Lean and automated theorem proving.

It's refreshing to see intellectual honesty about a tool's limitations, from someone still advocating for its strengths.

➕ show 5 replies
trehans • yesterday at 5:33 PM

One thing I'm surprised to see little mention of here is that if you want to use Lean proofs for your code and really want good correspondence between what is proved in Lean and what your code actually does, you need a mathematical model of your programming language embedded in Lean and a deterministic parser converting your code itself into Lean. Otherwise, yes, an AI actually has no checks against hallucination and while writing Lean proofs probably helps AI identify its mistakes it really isn't an end-to-end proof of your code's functionality.

I personally think the future probably involves a combination of unit tests and formal verification to support our confidence in AI-written software, as well as means to align high-level human intent with the low-level intent of individual code pieces, which as this article mentions is the other big piece that can slip with formal proofs: we might not be proving what we think we're proving. For those interested I've written an educational post about this topic here as well: https://kellerai.io/resources/ai-proved-your-code-correct

➕ show 4 replies
wodenokoto • yesterday at 10:56 AM

Isn’t “proof is checked in Lean” kinda similar to assuming your code works just because it compiles.

Sure, the code works, but does it work at doing what you want?

Sure, the proof is valid, but does it prove what you set out to prove?

➕ show 12 replies
adleyjulian • yesterday at 4:18 PM

> Question 4: does the code exploit a bug in Lean’s official kernel?

My understanding is that this has generally been a non issue as one does not exploit a bug unintentionally (at least it hasn't happened yet), but the Huggingface hack shows agents are willing to go through great lengths to cheat to pass evals.

Given an impossible task I could see an agent finding and exploiting a Lean kernel bug and then obfuscating its method.

I suspect the easiest solution to this is to have adversarial agents looking for such cheating.

➕ show 2 replies
dwohnitmok • yesterday at 6:05 PM

Point 3 in this article basically is just a case of bad defaults in Lean (Lean at this point should probably just make `lake comparator` a mandatory part of compilation and that immediately fixes the issue as Buzzard mentions).

Really there's only three things to check that the theorem is correct (leaving aside important questions of whether humans actually understand the proof and only caring about whether theorem is true):

1. Check that the formal statement of the theorem matches the informal statement of the theorem

2. Actually compile the proof (with `lake comparator`)

3. Try to make the Lean kernel as bug-free as possible (the hardest one but also the one with the most amount of attention focused on it) or run with multiple different kernels

Assuming those three, no need to read the potentially millions of lines of proof, if all you care about is correctness and not understanding.

➕ show 1 reply
Xcelerate • yesterday at 4:20 PM

I'm a little worried that the mountain of disclaimers against Lean proofs is going to slow something many industries desperately need: more formalization. (Buzzard's article is great by the way considering its target audience—my comment is more about the broader tech industry's perception of LLM-generated Lean proofs.)

One of the nice things about mathematical theories relevant to the real world (e.g. PA) is that confirming that a proof is correct is a purely mechanical procedure. Now Lean is built on the Calculus of Inductive Constructions (which can indirectly capture PA, but includes a lot more as well), but it's child's play to write a simple PA proof checker. It's probably a few hundred lines of Python, and even for something like a million line proof, confirming or refuting whether a proof is correct will take a few seconds tops (again, pure PA here, not Lean).

The caveats in the article are indeed important (e.g., "Did your formal sentence in the language of first-order arithmetic actually capture what you intended?", "Is there a bug in your proof checker?"), but I'd label these more as human factors than math factors. I'm afraid the general public is starting to get the impression that "Lean-checked" is just another quality improvement, like reviewing your code carefully or adding some unit tests. It's not—it's totally different, and I don't think we should make too many scary disclaimers as to dissuade further progress with formalization.

➕ show 3 replies
red_trumpet • yesterday at 11:34 AM

> Put another way — given a Challenge.lean file with only trusted code imported and the statement of a theorem, and a Solution.lean file with millions of lines of untrusted code imported and the proof of a theorem which looks identical, how do we know for sure that somewhere in the millions of lines of code there is no hack which changes the meaning of the statement, changes the rules from just the axioms of mathematics.

As someone with a PhD in mathematics, but no experience with Lean, I found this pretty surprising. Shouldn't there be some kind of encapsulation, which insulates the statement from the proof?

➕ show 4 replies
seanwilson • yesterday at 2:35 PM

> def FermatsLastTheorem : Prop := ∀ a b c n : ℕ, n ≥ 3 → a^n + b^n ≠ c^n

> This code imports Lean’s mathematics library Mathlib and then defines a mathematical statement which looks at first glance like it might be Fermat’s Last Theorem, but which actually is a trivially false statement because in Lean ℕ contains 0, so a = b = c = 0 and n = 3 gives a counterexample.

...

> The first question which one has to ask when judging a pdf which comes with some Lean code is: “what is the statement of the theorem in the Lean code, and does this correspond to the actual theorem statement in the pdf?” For a human Lean expert, this is typically (but not always) an easy question to answer. For example any Lean-competent human mathematician would be able to read the two lines of code above and observe that this was a mis-statement of Fermat’s Last Theorem.

To add to this, if the statement is wrong, the proof steps and other theorem statements that appear in the full proof are going to follow a path that goes with the wrong statement so there's further opportunities to see there's a mistake.

Often problems with the statement make it suspiciously easy to prove, the proof takes a path that doesn't make sense with the correct statement in mind, or it makes it impossible to complete the proof. In the above example, you would see from the easy counterexample found in the proof that the statement is wrong. The proofs aren't a black box.

And if the proof is taking advantage of a bug in Lean somewhere to prove some faulty intermediate theorem, you can still scrutinise the path that takes the proof, the same as you would to find a problem in a flawed hand-written proof. The flaw would ripple through the rest of the proof.

It's like if your high-level requirements for a computer program (the theorem statement) had a mistake and someone implemented it (the proof). The implementation is going to follow a path that implements that mistake. So by looking at individual function definitions that were implemented and what the code is doing, there's opportunities to spot mistakes in the requirements like missing assumptions or parts that don't make sense. This often happens when you're trying to code something based on flawed requirements, where the problem becomes more obvious as you get into the details of the code. It's the same with proofs.

➕ show 1 reply
moi2388 • yesterday at 1:18 PM

“Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth

tomtomtom777 • yesterday at 2:05 PM

The sizes of these proofs are mind boggling.

This raises the question, is there any value in a proof so complicated that no human could ever understand it?

Is there any purpose to mathematical proofs other than to increase our understanding?

➕ show 4 replies
philipwhiuk • yesterday at 11:39 AM

Thanks, this is really interesting and helpful context to us non-mathematicians.

> It is probably worth stressing again: do not run random Lean code on your local machine unless you sandbox it first. Lean’s mathematics library is safe to run and build upon because this is human-curated and checked by human experts.

I was surprised by this - does Lean need the ability to run arbitrary code? It feels like limiting Lean to not being Turing complete would be an advantage.

➕ show 3 replies
nirinor • yesterday at 5:55 PM

The problem here is that people want a simple fact to deal with many situations.

A) "Someone said Lean4 proof so it must be bullet-proof and fulfill all my hopes!" B) "Eh, lean4 is imperfect, so it means nothing"

Inconveniently, both of those caricatures are wrong.

Lean4 gives us a high level of confidence in the _theorem validated, under the assumptions allowed_.

This makes it high value to learn to read lean4 theorems (not proofs).

xg15 • yesterday at 4:14 PM

I remember some frustrating math courses back when I was studying CS. The experience was somewhat like this:

Imagine you know nothing about vi except that it's a famous command line utility for linux. One day, your supervisor is tasked to give you an introduction to it.

However, he doesn't tell you what vi is for or why it exists or how you use it - instead, he just sends you a tarball with the entire source code of it. Then he spends an hour with you going through the main function line by line, stopping whenever he finds a construct particularly clever or elegant. At the end, he runs "make" once to demonstrate that everything compiles.

He asks if you have any questions. You have none - you're still far away from being able to formulate meaningful questions. He is satisfied, declares you Knowledgeable in Vi and calls it a day.

It feels as if seasoned mathematicians now have a similar experience with AI generated proofs like the one students had in introductory math lectures like this one.

I'm hoping a bit that this could motivate people to develop better didactics for math.

hingler36 • yesterday at 3:19 PM

> OpenAI never claimed that it did! They just said “here is some Lean code which goes with this paper”.

Maybe I'm misunderstanding this, but it feels like TFA is giving OpenAI entirely too much credibility here.

If I told you "My grandma makes great chicken enchiladas" and put a plate in front of you containing an enchilada filled with dog crap, you'd be rightfully confused and upset when you bit into it. Sure, I never specified what the enchilada in front of you was filled with, but come on!

➕ show 1 reply
breakwaterlabs • yesterday at 6:41 PM

The issues in the article sound eerily familiar to anyone who has seen the passing unit tests that LLMs love to generate.

129298467 • yesterday at 1:29 PM

Both the Lean kernel and the so called independent Con Leche kernel have massive Claude contributions.

Asking the same entity to write the proof checkers as well as the proofs is not good practice. I'm very curious why Buzzard omits this fundamental fact.

This is just like an auditing company also writing the original financial statements.

➕ show 1 reply
troupo • yesterday at 10:36 AM

(Judging from my very limited experience with Lean, and with Lean written by LLMs)

It also doesn't help that LLMs tend to generate a lot of unnecessary Lean code to prove even the simplest statements.

➕ show 1 reply
Oarch • yesterday at 1:00 PM

He doesn't tell it to make no mistakes. How can I trust this article!

cobychapple • yesterday at 10:44 AM

https://xkcd.com/3201/ "Proof Without Content"

fooker • yesterday at 2:58 PM

I am not looking forward to bugs in code becoming bugs in specifications instead.

It is far more pleasant to deal with bugs in code.

For complex things like compilers, we like to deliberately leave some parts of the spec weak to make the code pragmatic. Welp.

➕ show 1 reply
barrenko • yesterday at 11:48 AM

..."left as an exercise to the reader".

taylorbuley • yesterday at 2:56 PM

[dead]

DoctorOetker • yesterday at 11:43 AM

I have a concise proof of FLT.

96 cores and 500 GB RAM to ... verify FLT?

The huge size of the proof is also remarkable, since brute forcing a long sequence of steps is much harder than brute forcing a shorter sequence of steps.

I thought the whole "tactics" approach in Lean was supposed to permit shorter proofs? to skip the low level stuff?

If I formalize my short proof of FLT in MetaMath, it would just be a small file and any computer would be able to verify it.

This reflects so poorly on both OAI as well as the Lean project.

➕ show 1 reply
mihaic • yesterday at 1:31 PM

At this point I've seen so many Lean articles that I have to ask: who check that Lean is actually correct itself?

➕ show 1 reply