“…and the proof is checked in Lean”

(xenaproject.wordpress.com)

80 points | by matt_d 6 hours ago ago

34 comments

  • Legend2440 16 minutes ago 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.

  • wodenokoto 3 hours ago 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 an hour ago 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 43 minutes ago 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.

    • program_whiz 40 minutes ago 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.

    • bananaflag 2 hours ago 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 an hour ago 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 38 minutes ago ago

          I agree with that. I never said you don't have to check the statement.

      • lordnacho an hour ago ago

        This sounds interesting enough that I think a link would be useful

    • fancyfredbot 2 hours ago 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 2 hours ago ago

        you just said the same thing

    • yk 29 minutes ago 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.

    • oulipo 3 hours ago 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 2 hours ago 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 3 hours ago 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.

  • moi2388 37 minutes ago ago

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

  • red_trumpet 2 hours ago 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 an hour ago 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.

    • lickonographic 2 hours ago 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.

  • troupo 3 hours ago 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 3 hours ago 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 3 hours ago 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 an hour ago 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.

  • philipwhiuk 2 hours ago 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 2 hours ago 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.

  • 129298467 26 minutes ago 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 an hour ago ago

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

  • barrenko 2 hours ago ago

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

  • cobychapple 3 hours ago ago

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

  • mihaic 24 minutes ago 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 a few seconds ago ago

      The article mentions that there are a number of independent lean kernels.

  • DoctorOetker 2 hours ago 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 20 minutes ago ago

      Would you be willing to share your concise proof?