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

(xenaproject.wordpress.com)

153 points | by matt_d 8 hours ago

17 comments

  • Legend2440 2 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 1 hour 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 40 minutes ago
        I haven’t seen the it yet, but keeping an eye out for “military-grade Lean” or some other nonsense.
    • samlinnfer 7 minutes ago
      He’s currently working on formalising Fermat’s Last Theorem in Lean btw.
    • contubernio 1 hour ago
      This kind of skepticism and self criticism is typical of good mathematicians and scientists because it's essential to doing good math and science.
  • wodenokoto 4 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 3 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 2 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.

      • paulddraper 22 minutes 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 2 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 51 minutes 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 minute 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? Maybe other people assumed that they did, or that the Lean proofs that were there are complete?
      • throwawayffffas 58 minutes 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 3 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.

    • bananaflag 4 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 2 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 2 hours ago
          I agree with that. I never said you don't have to check the statement.
      • lordnacho 3 hours ago
        This sounds interesting enough that I think a link would be useful
    • Gabriel54 1 hour 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 2 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.
    • paulddraper 25 minutes 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 4 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 3 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 4 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.

  • seanwilson 1 hour ago
    > 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 impossible to complete the proof, make it unexpectedly easy, or the proof takes a path that doesn't make sense with the correct statement in mind. 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.

    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, there's opportunities to spot the problem.

  • red_trumpet 4 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 3 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 1 hour 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.

        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.

    • lickonographic 3 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 1 hour 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.

  • fooker 47 minutes 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.

  • moi2388 2 hours ago
    “Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth
  • philipwhiuk 4 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.

    • kccqzy 1 hour ago
      It does. What if you want to use Lean to write say an HTTP server that contains several theorems about how it behaves?
    • yorwba 3 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.
  • troupo 5 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 5 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 4 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 2 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 52 minutes 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 31 minutes 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.
  • cobychapple 5 hours ago
    https://xkcd.com/3201/ "Proof Without Content"
  • hingler36 26 minutes 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!

  • 129298467 2 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 2 hours ago
    He doesn't tell it to make no mistakes. How can I trust this article!
  • barrenko 3 hours ago
    ..."left as an exercise to the reader".
  • taylorbuley 49 minutes ago
    [dead]
  • tomtomtom777 1 hour ago
    The sizes of these proofs are mind boggling.

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

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

    • kccqzy 1 hour 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 minute 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 4 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 2 hours ago
      Would you be willing to share your concise proof?
      • ncruces 1 hour ago
        The margin is too narrow to contain it.
  • mihaic 2 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 1 hour ago
      The article mentions that there are a number of independent lean kernels.
      • mihaic 1 hour ago
        Thank you, I should have actually gone through the whole article before commenting.