Rendered at 16:57:13 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
Legend2440 3 hours ago [-]
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.
dcss_gardener 3 hours ago [-]
In my experience the actual formal verification practitioners are generally very straightforward about its strengths weaknesses and limitations. Understanding those limitations is fundamental to using them well, gaining any real value from them, beyond what is typical of complex tools.
What you need to watch out for are the people or companies who latch on to proof checkers and formal verification as some sort of shortcut to correctness, intending to use it as a signal of seriousness rather than a serious tool in its own right.
ptk 2 hours ago [-]
I haven’t seen the it yet, but keeping an eye out for “military-grade Lean” or some other nonsense.
guenthert 28 minutes ago [-]
"Worth pointing out that this article is by Kevin Buzzard"
Is it? The site claims that the article is written by the Xena Project. In the comment section it answers on (paraphrasing) "whether proving that a Lean kernel written in Lean and verified by Lean would be a circular proof" with "I’m really sorry, you need to ask these questions elsewhere (e.g. on the Lean Zulip). I am by no means an expert in these matters, all I know is that people who are experts have thought hard about them. "
If that is indeed Kevin Buzzward's writing, it is by no means obvious.
This kind of skepticism and self criticism is typical of good mathematicians and scientists because it's essential to doing good math and science.
samlinnfer 1 hours ago [-]
He’s currently working on formalising Fermat’s Last Theorem in Lean btw.
Xcelerate 36 minutes ago [-]
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.
thomasahle 25 minutes ago [-]
> "Lean-checked" is just another quality improvement, like reviewing your code carefully or adding some unit tests. It's not—it's totally different
I think for most things, this is actually a good way to see it: As a third leg on top of reviewing your code carefully and unit tests.
As you say, people will still make many mistakes in how they write their formal requirements, or miss things they care about.
For math this is not an issue, it's usually easy to check that the lean statement is exactly what you want. But for software, and many other real world applications, it's better thought of as a new orthogonal testing vector that everyone should be using.
guenthert 16 minutes ago [-]
> But for software, and many other real world applications, it's better thought of as a new orthogonal testing vector that everyone should be using.
Not sure about should, but as long as even modestly complex systems like the Signal communication protocol map into millions of lines of Lean, its pretty clear that not everyone will be able to use it. We still need better tools (tools better suited to our monkey brains).
wodenokoto 6 hours ago [-]
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?
throwawayffffas 4 hours ago [-]
The gist of the article is that it's worse.
That it's the equivalent of saying "It's full moon tonight because I wrote this program".
And he states that you have to check that:
1. The statement the author is making corresponds to the statement in the lean program.
2. The lean program actually compiles.
3. There is no shenanigans hidden in the lean program to disguise a trivial proof as the one stated.
4. The program does not exploit bugs in lean.
csande17 4 hours ago [-]
On the bright side, the article claims Lean has built-in tools to do 2-4 as long as you have enough RAM. In particular, there's a formally verified alternative implementation of Lean's checker that would theoretically rule out 4.
That implementation seems to be vibe-coded/vibe-proven in Lean itself (assuming the "con-leche" that my quick Google search turned up is the one he's talking about), so it's kind of turtles all the way down, but it does decrease the chance that a program could be exploiting both a Lean bug and a con-leche bug.
lumost 47 minutes ago [-]
Saying that a "formally verified" program rules out any bugs is a bit of a reach. Formal verification only checks that the properties you claim are true are actually true in the absence of bugs in the proof logic.
Example bug
A verified network program ensures that "data from two addresses are never commingled", but it does not verify that the NIC can't overwrite control flow memory opening up RCE attacks/other memory reads.
It certainly is harder to make bugs in formally verified software than the alternative, but it is not bug free.
paulddraper 2 hours ago [-]
That’s pretty much the same as compiling a program.
1. Yes.
2. Yes.
3. This is “you took 10 KLOC to do what 1 could have.”
4. Yes.
program_whiz 4 hours ago [-]
Reading the friendly article:
It is worth noting that of the 290 OpenAI theorems which come with Lean code, around 38 of them have the property that the Lean code does not even state, let alone prove, the main theorem of the paper.
So even if LEAN is 100% bug-free, its still on the programmer to correctly express the logic and proofs, or they could be proving completely unrelated facts.
bunderbunder 2 hours ago [-]
It also speaks to why I remain skeptical of relying too much on coding agents for code review. They are still pretty iffy on implementing the right thing, and even worse at detecting when a PR didn’t implement the right thing. Ignoring that reality is how you do like Anthropic did and increase your rate of merging changes from 2500/day to 30,000/day without a corresponding increase in the rate at which you deliver useful work product.
skybrian 1 hours ago [-]
OpenAI did a data dump of work in progress, leaving it to the mathematics community to make sense of it. I don’t think they claimed that there were Lean proofs for everything? Did they warn that some Lean proofs were incomplete?
suddenlybananas 1 hours ago [-]
Why did they stop in the middle anyway? Was there a justification given for that?
bunderbunder 57 minutes ago [-]
The cynical answer is that their primary goal was never to meaningfully contribute to mathematics. It was to pick some low-hanging fruit for the marketing department. So they did the 10% of the work that generates 90% of the buzz.
skybrian 42 minutes ago [-]
It’s more likely that their goal was internal research, to test a new LLM before releasing it. But, then they had something that mathematicians would be interested in, so they threw a data dump over the wall. It’s a rather rude way to do it, but this isn’t a company that particularly cares about the things that mathematicians care about.
OpenAI no longer needs to do anything to get publicity. There are some organizations that are so famous that everything they do is newsworthy and anything they do will be covered whether they like it or not. Remaining low-profile is no longer an option.
The people claiming that everything is marketing haven’t come to grips with the inequality of fame.
throwawayffffas 2 hours ago [-]
They could be proving completely unrelated stuff. Or even entirely trivial things like 1 + 1 = 2 over multiple millions of lines of lean code.
fancyfredbot 5 hours ago [-]
I think it's a reasonable point but a bad analogy.
It's more like assuming that because your code is formally proven correct the client will be happy with it.
The code can be right but it may still do the wrong thing.
pasquinelli 5 hours ago [-]
you just said the same thing
fancyfredbot 10 minutes ago [-]
OP said it's like saying the code compiles, but I said formally proven correct.
Formally proven correct is a much stronger guarantee that the code meets its spec than a successful compilation.
bananaflag 5 hours ago [-]
No, because proofs are programs and theorems are types. It is enough to construct a function of the needed type to have a proof of the needed theorem. You don't need to look through all the code to see that the function has the desired type.
Sharlin 4 hours ago [-]
You have to be sure that the formalized theorem matches the informally stated theorem. Which is what GP meant and what the article is about. A program does what is written, not what is meant; a Lean program proves what is written, not what is meant.
bananaflag 4 hours ago [-]
I agree with that. I never said you don't have to check the statement.
lordnacho 4 hours ago [-]
This sounds interesting enough that I think a link would be useful
That's like saying that all memory-safety programs are written in Rust.
There is no fundamental reason why mathematics should be formalized using concepts that are alien to most mathematicians, in the way that type theory is.
(I guess Isabelle/HOL is the Java of formalized mathematics, in the sense that for reasons that are difficult to understand, memory safety of Java-implemented technology does not count.)
Gabriel54 3 hours ago [-]
For relatively "simple" statements in mathematics it is pretty easy to learn enough Lean to verify that the Lean statement correctly encodes the intention of the mathematics. It gets more difficult in certain areas of mathematics where there are many layers of definitions and they haven't been standardized in Lean yet.
yk 4 hours ago [-]
On a technical level, yes. Though lean is build such that "it compiles" is a very strong statement about mathematics while most programming languages are not build to provide a very strong statement about correctness of the program. It is perhaps more similar to checking an equation numerically.
6 hours ago [-]
paulddraper 2 hours ago [-]
Yes it’s a good analogy.
You have to watch out for
1. Translation. Do the author’s claims about the program/theorem match the actual code?
2. Do you employ “shenanigans” to circumvent the checker? Bugs, unsafe operations. — Lean is a very strict checker as compilers go. Some compilers intentionally say “buyer beware.” It’s annoying to check for integer overflow in every operation. Lean doesn’t. But that still doesn’t mean it has zero bugs, in the framework or axioms.
oulipo 6 hours ago [-]
If the proof is valid, it DOES prove what your theorem is saying (except for rare verification kernel bugs). The issue is mostly: did you correctly formalize and check the specification of your theorem itself...
dgellow 5 hours ago [-]
I mean, in some strange way, yes. Because your type system is basically a set of claims that are proven by your compiler. But the analogy doesn’t go further than that. The running program itself is the proof
j16sdiz 6 hours ago [-]
it is more like "unit test pass"
Fresh today, I asked llm to fix a unit test for me, it replaced the test with no-op.
3 hours ago [-]
adleyjulian 39 minutes ago [-]
> 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.
Gander5739 32 minutes ago [-]
If only there was a way to prove the compiler worked exactly as intended in all cases...
> 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.
red_trumpet 5 hours ago [-]
> 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?
CJefferson 4 hours ago [-]
I don't understand this at all, as someone with a PhD in this area, and who uses lean quite a bit.
If 'Challenge.lean' states the theorem, the solution can't change the theorem. The only thing it can do is do a 'sorry', just skip proving some part, but that's printed out very clearly when it happens.
troupo 3 hours ago [-]
They are not talking about changing the theorem. The solution can arbitrarily chose to override or ignore certain things to make sure the theorem passes.
That's what the article means by "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 for the meaning of the statement, I don't know how it is easy in maths. But in code, I've had Claude try and contort the definition of "function accepts integers" to "anything that can look as an integer e.g. a string containing an integer is accepted" and twist the solution to that.
lickonographic 5 hours ago [-]
I think the deeper problem - an I am reading Computational Reflections by Cantwell Smith and that might be colouring my view - is that fundamentally it comes down to the interpretation of what the code or the math says.
The very meaning of interpretation in computer science is at odds with the use in philosophy of language and that is symptomatic.
We're still fundamentally trying to advance Hilbert's program. It's like Göedel's work hasn't sunk in to our collective reasoning about reasoning. It just doesn't seem possible to build a self contained correct and truthful system of symbolic logic. Truth is in the relationship of the system with other systems.
Automating mathematics, like automating software engineering, or automating automation, are all self contradictory propositions. Anything of what we build only ever means anything in how it interacts with us. I mean, people will go round and round in this forum discussing semantics and the meta implication of these unceasing discussions never seems to hit home. Namely, that there is no universal, truthful, correct, system of symbolic logic. It seems in fact impossible to have one. But the results that indicate this impossibility are built with a system of symbolic logic and the validity therein is contingent on people's understanding and, like all symbolic logic systems (including the ones that states the limits to universal symbolic logic systems) they are bootstrapped from axioms one must chose at the start or by default and they can never be fully proved by the very system built atop them.
thechao 3 hours ago [-]
As an ex- mathematician and ex- computer scientist who worked in programming language theory and computer algebra systems, I can assure you that we think about these problems deeply. In fact, outside of a few strongly normalizing toys, the first thing we do in PLT is drop completeness in favor of soundness. The article itself discusses this (the soundness issues that were addressed).
Although, now I'm charmed about the idea of a programming language -- possibly a Brainfuck descendent? -- that drops soundness for completeness.
lickonographic 22 minutes ago [-]
Oh I know how deeply we think about these things in the academy. I also know how practice, not least of all in industry, falls short of the depth of the theoretical thought.
I hear and participate daily in discussions about automation, computation, programming - languages, environments. I have no illusions about the pinnacle of theory filtering down to how people spend their time, how organizations their resources, or how people talk about these problems every day in the context of real world project which tie up very limited resources pursuing things the theory should have made very clear to be out of reach for several decades now.
5 hours ago [-]
fooker 2 hours ago [-]
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.
neurophant 57 minutes ago [-]
[flagged]
philipwhiuk 5 hours ago [-]
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.
yorwba 5 hours ago [-]
Lean needs the ability to call out to external solvers and import proof certificates generated by them. In theory you could have Turing-complete Lean without the ability to interact with other programs or the file system, but you would have to fully reimplement those external solvers in Lean and it would be terribly slow.
kccqzy 2 hours ago [-]
It does. What if you want to use Lean to write say an HTTP server that contains several theorems about how it behaves?
moi2388 4 hours ago [-]
“Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth
troupo 6 hours ago [-]
(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.
mitxela 6 hours ago [-]
Proofs are really hard, good proofs are really really hard. Having any proof at all is a huge step forward from not having one.
2/5
QuesnayJr 6 hours ago [-]
This is a trivial example, but I asked Prover9 (which is a brute-force automated theorem prover) to prove a theorem, and then I asked GPT-6 Sol to explain the proof. Instead of doing that, it said "You don't need most of this" and gave a shorter proof.
lionkor 4 hours ago [-]
You're implying that GPT-6 Sol can do better. That is not how LLMs work! They will write code, and then, in a separate invocation, find 100 problems with that code. Unlike humans, the immediate context massively impacts the immediate next response, and "knowing better" is nearly entirely irrelevant, because even with thinking and reasoning, these machines do not adequately reflect.
Instructing them to reflect also doesn't help; they pull whatever hallucinations make up the "reflection" into immediate context, and now they're even more confused.
sashank_1509 2 hours ago [-]
I can believe that GPT provides shorter proof than automated theorem provers which are effectively brute force searching with far less guidance than an LLM.
But from what I’ve seen, it’a absolutely not true that GPT on average generates shorter proofs than humans. Humans have GPT beat handily on that. Sometimes GPT generates shorter proofs, like in cases where humans missed a connection that GPT found. But most of the time, GPT will generate >10X longer proofs, hundreds, even thousands of pages of inscrutable slop maths where it’s completely unclear what’s going on.
beepbooptheory 2 hours ago [-]
Funny how they always seem to do great on a trivial example. But not too trivial that it isn't worth sharing... Just trivial enough.
xg15 43 minutes ago [-]
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 2 hours ago [-]
> 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!
skybrian 1 hours ago [-]
What did OpenAI actually claim?
choxi 45 minutes ago [-]
> It is worth noting that of the 290 OpenAI theorems which come with Lean code, around 38 of them have the property that the Lean code does not even state, let alone prove, the main theorem of the paper. And OpenAI never claimed that it did! They just said “here is some Lean code which goes with this paper”. Sometimes the code just states and proves some intermediate results — my impression is that OpenAI decided to go live when some of the formalizations were incomplete, so just dumped what they had. To give a concrete example: paper 194 claims to prove Lech’s multiplicity conjecture in commutative algebra, with no restriction on dimension, residue field or characteristic; this question has been open since 1960. The headline theorem in the corresponding Lean code can be checked to be Corollary 5.4 of the paper — already an impressive achievement, but not the headline result.
129298467 3 hours ago [-]
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.
Oarch 4 hours ago [-]
He doesn't tell it to make no mistakes. How can I trust this article!
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?
kccqzy 3 hours ago [-]
The sizes of the total sum of software that enables you and me to write comments here is mind boggling. Probably no human could understand it all. But then why are we comfortable with it? Abstractions.
tomtomtom777 1 hours ago [-]
The purpose of software isn't primarily to understand computers. I wouldn't know the purpose of say a number theory proof other then gaining a deeper understanding.
DoctorOetker 5 hours ago [-]
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.
s-zeng 3 hours ago [-]
Would you be willing to share your concise proof?
ncruces 3 hours ago [-]
The margin is too narrow to contain it.
mihaic 3 hours ago [-]
At this point I've seen so many Lean articles that I have to ask: who check that Lean is actually correct itself?
adrianN 3 hours ago [-]
The article mentions that there are a number of independent lean kernels.
mihaic 3 hours ago [-]
Thank you, I should have actually gone through the whole article before commenting.
It's refreshing to see intellectual honesty about a tool's limitations, from someone still advocating for its strengths.
What you need to watch out for are the people or companies who latch on to proof checkers and formal verification as some sort of shortcut to correctness, intending to use it as a signal of seriousness rather than a serious tool in its own right.
Is it? The site claims that the article is written by the Xena Project. In the comment section it answers on (paraphrasing) "whether proving that a Lean kernel written in Lean and verified by Lean would be a circular proof" with "I’m really sorry, you need to ask these questions elsewhere (e.g. on the Lean Zulip). I am by no means an expert in these matters, all I know is that people who are experts have thought hard about them. "
If that is indeed Kevin Buzzward's writing, it is by no means obvious.
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.
I think for most things, this is actually a good way to see it: As a third leg on top of reviewing your code carefully and unit tests.
As you say, people will still make many mistakes in how they write their formal requirements, or miss things they care about.
For math this is not an issue, it's usually easy to check that the lean statement is exactly what you want. But for software, and many other real world applications, it's better thought of as a new orthogonal testing vector that everyone should be using.
Not sure about should, but as long as even modestly complex systems like the Signal communication protocol map into millions of lines of Lean, its pretty clear that not everyone will be able to use it. We still need better tools (tools better suited to our monkey brains).
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?
That it's the equivalent of saying "It's full moon tonight because I wrote this program".
And he states that you have to check that:
1. The statement the author is making corresponds to the statement in the lean program.
2. The lean program actually compiles.
3. There is no shenanigans hidden in the lean program to disguise a trivial proof as the one stated.
4. The program does not exploit bugs in lean.
That implementation seems to be vibe-coded/vibe-proven in Lean itself (assuming the "con-leche" that my quick Google search turned up is the one he's talking about), so it's kind of turtles all the way down, but it does decrease the chance that a program could be exploiting both a Lean bug and a con-leche bug.
Example bug
A verified network program ensures that "data from two addresses are never commingled", but it does not verify that the NIC can't overwrite control flow memory opening up RCE attacks/other memory reads.
It certainly is harder to make bugs in formally verified software than the alternative, but it is not bug free.
1. Yes.
2. Yes.
3. This is “you took 10 KLOC to do what 1 could have.”
4. Yes.
It is worth noting that of the 290 OpenAI theorems which come with Lean code, around 38 of them have the property that the Lean code does not even state, let alone prove, the main theorem of the paper.
So even if LEAN is 100% bug-free, its still on the programmer to correctly express the logic and proofs, or they could be proving completely unrelated facts.
OpenAI no longer needs to do anything to get publicity. There are some organizations that are so famous that everything they do is newsworthy and anything they do will be covered whether they like it or not. Remaining low-profile is no longer an option.
The people claiming that everything is marketing haven’t come to grips with the inequality of fame.
It's more like assuming that because your code is formally proven correct the client will be happy with it.
The code can be right but it may still do the wrong thing.
Formally proven correct is a much stronger guarantee that the code meets its spec than a successful compilation.
There is no fundamental reason why mathematics should be formalized using concepts that are alien to most mathematicians, in the way that type theory is.
(I guess Isabelle/HOL is the Java of formalized mathematics, in the sense that for reasons that are difficult to understand, memory safety of Java-implemented technology does not count.)
You have to watch out for
1. Translation. Do the author’s claims about the program/theorem match the actual code?
2. Do you employ “shenanigans” to circumvent the checker? Bugs, unsafe operations. — Lean is a very strict checker as compilers go. Some compilers intentionally say “buyer beware.” It’s annoying to check for integer overflow in every operation. Lean doesn’t. But that still doesn’t mean it has zero bugs, in the framework or axioms.
Fresh today, I asked llm to fix a unit test for me, it replaced the test with no-op.
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.
https://xkcd.com/1821/
> 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.
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?
If 'Challenge.lean' states the theorem, the solution can't change the theorem. The only thing it can do is do a 'sorry', just skip proving some part, but that's printed out very clearly when it happens.
As in the infamous 2=1 (https://en.wikipedia.org/wiki/Mathematical_fallacy#Division_...). We ignore that division by zero is undefined, and boom, we get a "proper" solution to the stated theorem.
That's what the article means by "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 for the meaning of the statement, I don't know how it is easy in maths. But in code, I've had Claude try and contort the definition of "function accepts integers" to "anything that can look as an integer e.g. a string containing an integer is accepted" and twist the solution to that.
The very meaning of interpretation in computer science is at odds with the use in philosophy of language and that is symptomatic.
We're still fundamentally trying to advance Hilbert's program. It's like Göedel's work hasn't sunk in to our collective reasoning about reasoning. It just doesn't seem possible to build a self contained correct and truthful system of symbolic logic. Truth is in the relationship of the system with other systems.
Automating mathematics, like automating software engineering, or automating automation, are all self contradictory propositions. Anything of what we build only ever means anything in how it interacts with us. I mean, people will go round and round in this forum discussing semantics and the meta implication of these unceasing discussions never seems to hit home. Namely, that there is no universal, truthful, correct, system of symbolic logic. It seems in fact impossible to have one. But the results that indicate this impossibility are built with a system of symbolic logic and the validity therein is contingent on people's understanding and, like all symbolic logic systems (including the ones that states the limits to universal symbolic logic systems) they are bootstrapped from axioms one must chose at the start or by default and they can never be fully proved by the very system built atop them.
Although, now I'm charmed about the idea of a programming language -- possibly a Brainfuck descendent? -- that drops soundness for completeness.
I hear and participate daily in discussions about automation, computation, programming - languages, environments. I have no illusions about the pinnacle of theory filtering down to how people spend their time, how organizations their resources, or how people talk about these problems every day in the context of real world project which tie up very limited resources pursuing things the theory should have made very clear to be out of reach for several decades now.
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.
> 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.
It also doesn't help that LLMs tend to generate a lot of unnecessary Lean code to prove even the simplest statements.
2/5
Instructing them to reflect also doesn't help; they pull whatever hallucinations make up the "reflection" into immediate context, and now they're even more confused.
But from what I’ve seen, it’a absolutely not true that GPT on average generates shorter proofs than humans. Humans have GPT beat handily on that. Sometimes GPT generates shorter proofs, like in cases where humans missed a connection that GPT found. But most of the time, GPT will generate >10X longer proofs, hundreds, even thousands of pages of inscrutable slop maths where it’s completely unclear what’s going on.
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.
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!
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.
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?
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.