Re:" and the proof is checked in Lean"
by QuesnayJr on Monday November 16, 2026 @05:48AM
(#50516163)
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.
Re:" and the proof is checked in Lean"
by lionkor on Monday November 16, 2026 @08:10AM
(#50517242)
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.
Re:" and the proof is checked in Lean"
by sashank_1509 on Monday November 16, 2026 @09:54AM
(#50518223)
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.
Re:" and the proof is checked in Lean"
by nifets on Monday November 16, 2026 @06:04AM
(#50516250)
it's not really similar at all.
proof checked in lean => proof of statement requires only that the statement is specified correctly (generally very easy to do) and that no lean kernel bugs were abused
code compiles => code satisfies requirements requires checking that all (inputs, outputs) of your program match the expected behaviour which is wildly intractable to verify in general
Re:" and the proof is checked in Lean"
by oulipo on Monday November 16, 2026 @06:05AM
(#50516253)
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...
Re:" and the proof is checked in Lean"
by bananaflag on Monday November 16, 2026 @06:36AM
(#50516441)
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.
Re:" and the proof is checked in Lean"
by Sharlin on Monday November 16, 2026 @07:53AM
(#50517089)
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.
Re:" and the proof is checked in Lean"
by fweimer on Monday November 16, 2026 @11:05AM
(#50519129)
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.)
Re:" and the proof is checked in Lean"
by mentalgear on Monday November 16, 2026 @12:33PM
(#50520254)
That's basically what Typescript also gives you, and it isn't bug free either.
You can proof a logic, but it does not proof that it is the logic that would keep the program secure and bug-free, only that it is internally consistent. So it helps, but by no means a silver bullet !
Re:" and the proof is checked in Lean"
by dgellow on Monday November 16, 2026 @07:16AM
(#50516778)
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
Re:" and the proof is checked in Lean"
by lumost on Monday November 16, 2026 @11:10AM
(#50519196)
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.
Re:" and the proof is checked in Lean"
by program_whiz on Monday November 16, 2026 @08:15AM
(#50517288)
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.
Re:" and the proof is checked in Lean"
by bunderbunder on Monday November 16, 2026 @09:55AM
(#50518233)
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.
Re:" and the proof is checked in Lean"
by skybrian on Monday November 16, 2026 @10:44AM
(#50518828)
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?
Re:" and the proof is checked in Lean"
by bunderbunder on Monday November 16, 2026 @10:59AM
(#50519044)
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.
Re:" and the proof is checked in Lean"
by skybrian on Monday November 16, 2026 @11:15AM
(#50519257)
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.
Re:" and the proof is checked in Lean"
by yk on Monday November 16, 2026 @08:26AM
(#50517382)
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.
Re:" and the proof is checked in Lean"
by Gabriel54 on Monday November 16, 2026 @09:15AM
(#50517814)
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.
Re:" and the proof is checked in Lean"
by paulddraper on Monday November 16, 2026 @10:20AM
(#50518527)
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.
Re:" and the proof is checked in Lean"
by red_trumpet on Monday November 16, 2026 @06:34AM
(#50516425)
> 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?
Re:" and the proof is checked in Lean"
by lickonographic on Monday November 16, 2026 @07:24AM
(#50516851)
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.
Re:" and the proof is checked in Lean"
by thechao on Monday November 16, 2026 @09:27AM
(#50517939)
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.
Re:" and the proof is checked in Lean"
by lickonographic on Monday November 16, 2026 @11:35AM
(#50519528)
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.
Re:" and the proof is checked in Lean"
by CJefferson on Monday November 16, 2026 @07:28AM
(#50516888)
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.
Re:" and the proof is checked in Lean"
by troupo on Monday November 16, 2026 @09:12AM
(#50517782)
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.
Re:" and the proof is checked in Lean"
by yorwba on Monday November 16, 2026 @07:09AM
(#50516712)
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.
Re:" and the proof is checked in Lean"
by DoctorOetker on Monday November 16, 2026 @06:43AM
(#50516507)
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.
Re:" and the proof is checked in Lean"
by 129298467 on Monday November 16, 2026 @08:29AM
(#50517401)
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 liken an auditing company also writing the original financial statements.
Re:" and the proof is checked in Lean"
by dcss_gardener on Monday November 16, 2026 @09:15AM
(#50517813)
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.
Re:" and the proof is checked in Lean"
by guenthert on Monday November 16, 2026 @11:29AM
(#50519446)
"Worth pointing out that this article is by Kevin Buzzard"
Is it? The site claims that the article is written by the Xena Project (some kind of institution or organization or committee allegedly at Imperial College). 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.
Re:" and the proof is checked in Lean"
by Isamu on Monday November 16, 2026 @12:26PM
(#50520166)
Seems more about the limitations of the way it was used
>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.
Re:" and the proof is checked in Lean"
by tomtomtom777 on Monday November 16, 2026 @10:45AM
(#50518843)
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.
Re:" and the proof is checked in Lean"
by guenthert on Monday November 16, 2026 @12:11PM
(#50519973)
The software that enables you and me to write comments here is held together with spit and duck tape. For mathematical proofs we should strive for higher standards.
Re:" and the proof is checked in Lean"
by seanwilson on Monday November 16, 2026 @09:35AM
(#50518037)
> 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 there to see there's a mistake.
In the above example, you would see from the easy counterexample found in the proof that the statement is wrong. Often problems with the statement make it impossible to complete the proof, make it unexpectedly easy, or it takes a path that doesn't make sense. The proofs aren't a black box.
It's like if your high-level requirements for a computer program (the thereom 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, there's opportunities to spot the problem.
Re:" and the proof is checked in Lean"
by thejokeisonme on Monday November 16, 2026 @12:12PM
(#50519981)
This is exactly one reason why human written mechanized proofs are so much more trust worthy. AI isn't really good at judgment calls, and that includes whether it is mechanizing the right things.
Re:" and the proof is checked in Lean"
by hingler36 on Monday November 16, 2026 @10:19AM
(#50518519)
> 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!
Re:" and the proof is checked in Lean"
by choxi on Monday November 16, 2026 @11:11AM
(#50519212)
> 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.
Re:" and the proof is checked in Lean"
by xg15 on Monday November 16, 2026 @11:14AM
(#50519244)
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 comnand 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.
Re:" and the proof is checked in Lean"
by adleyjulian on Monday November 16, 2026 @11:18AM
(#50519285)
> 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.
Re:" and the proof is checked in Lean"
by Xcelerate on Monday November 16, 2026 @11:20AM
(#50519315)
I'm a little worried that the mountain of "disclaimers" against Lean proofs is going to slow something many industries desperately need: more formalization.
One of the nice things about mathematical theories relevant to the real world (e.g. PA) is that, assuming the theory is consistent and sound in the standard model, 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.
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 add so many scary disclaimers as to dissuade further progress with formalization.
Re:" and the proof is checked in Lean"
by thomasahle on Monday November 16, 2026 @11:32AM
(#50519490)
> "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.
Re:" and the proof is checked in Lean"
by guenthert on Monday November 16, 2026 @11:40AM
(#50519601)
> 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).
Re:" and the proof is checked in Lean"
by thejokeisonme on Monday November 16, 2026 @12:09PM
(#50519940)
The problem with your PA proposal is that, while the kernel will be much small, the specifications/theorems will be much harder to read. So you are saving on a one time effort (writing a correct kernel) by sacrificing in many time efforts (writing a correct specification).
Re:" and the proof is checked in Lean"
by trehans on Monday November 16, 2026 @12:33PM
(#50520255)
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
Re:" and the proof is checked in Lean"
by trehans on Monday November 16, 2026 @12:52PM
(#50520521)
Yes, Verus (for Rust) is a good example of programming language level verification. The recent GitHub Next announcement indicates they are using it in their backend.
You're right that if you verify at the assembly language it can give you additional certainty that there are no additional errors in the compilation step. However, it can be easier for AI to reason about proofs written at the programming language level because (from what I can deduce) it matches the level that humans are operating at and it doesn't have additional details such as registers and memory operations to worry about.
Re:" and the proof is checked in Lean"
by fritzo on Monday November 16, 2026 @12:58PM
(#50520609)
You don't need a model of your programming language in Lean, that's overkill.
It's already useful to isolate a DSL in your software and model that in Lean. Sure that only proves that the domain specific code is correct, but now you've factored your proof into proving high-level correctness and low-level correctness.
It also doesn't help that LLM 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.
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?
proof checked in lean => proof of statement requires only that the statement is specified correctly (generally very easy to do) and that no lean kernel bugs were abused
code compiles => code satisfies requirements requires checking that all (inputs, outputs) of your program match the expected behaviour which is wildly intractable to verify in general
Fresh today, I asked llm to fix a unit test for me, it replaced the test with no-op.
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 can proof a logic, but it does not proof that it is the logic that would keep the program secure and bug-free, only that it is internally consistent. So it helps, but by no means a silver bullet !
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.
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 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.
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.
Yes, Lean verifies the algorithm being verified, not hardware or someone else's software.
1. Yes.
2. Yes.
3. This is “you took 10 KLOC to do what 1 could have.”
4. Yes.
Being fairly naive to Lean in general, this always seemed to me like a clear flaw of using Lean solutions as proof of hypotheses
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.
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.
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?
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.
This is a totally unnecessary requirement, noticed by Alfred Tarski roughly two seconds after Göedel's work was announced.
If you don't personally find formal reasoning useful in proving correctness, that's a you problem. The rest of us are progressing forward just fine.
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.
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.
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 liken an auditing company also writing the original financial statements.
It's nice to see intellectual honesty about its limitations, while 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 (some kind of institution or organization or committee allegedly at Imperial College). 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.
>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.
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?
> 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 there to see there's a mistake.
In the above example, you would see from the easy counterexample found in the proof that the statement is wrong. Often problems with the statement make it impossible to complete the proof, make it unexpectedly easy, or it takes a path that doesn't make sense. The proofs aren't a black box.
It's like if your high-level requirements for a computer program (the thereom 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, there's opportunities to spot the problem.
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.
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!
Imagine you know nothing about vi except that it's a famous comnand 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.
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/
One of the nice things about mathematical theories relevant to the real world (e.g. PA) is that, assuming the theory is consistent and sound in the standard model, 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.
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 add so 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).
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
You're right that if you verify at the assembly language it can give you additional certainty that there are no additional errors in the compilation step. However, it can be easier for AI to reason about proofs written at the programming language level because (from what I can deduce) it matches the level that humans are operating at and it doesn't have additional details such as registers and memory operations to worry about.
It's already useful to isolate a DSL in your software and model that in Lean. Sure that only proves that the domain specific code is correct, but now you've factored your proof into proving high-level correctness and low-level correctness.
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).