> Along the way, it wrote 13 million lines of Lean and proved 29,500 intermediate theorems.
Pretty insane. I suppose it lends further credence to the idea that anything that can be shown to be correct can be done by a model.
Pretty insane. I suppose it lends further credence to the idea that anything that can be shown to be correct can be done by a model.
My strong hunch is that it was a joke - he knew how difficult the problem was and claiming he had a solution was I think a huge motivating factor for many mathematicians trying to prove it. The greatest nerd snipe troll in history.
In a sense, the proof is a demonstrator not an end in itself. To mathematics enthusiasts it is significant. To the AI it is Tuesday.
Enjoyed that idea. Not sure how true but it was enjoyable.
How have we not merely substituted one verification problem for another?
Your job or the LLM's job is to write code that Lean is satisfied with, creating the link between what you're trying to prove, and mathematical axioms.
If you write a bad proof, the Lean constraint checker will tell you, unless there are bugs in Lean itself, or you defined the goal constraint incorrectly.
> Pretty insane.
I don't think the count of "intermediate theorems" tells you anything. Here's something from an algebra textbook:
---
Let G be a group, let H be a subgroup [of G], and let N be a normal subgroup [of G]. Then
H ∨ N = HN = { hn | h ∈ H, n ∈ N }.
---
This says that the subgroup closure of H and N, the smallest subgroup that contains them both, is identical with the set consisting of all products of an element of H (on the left) and an element of N (on the right).
Part of the proof:
---
Suppose that x and y are elements of [the set of products hn]. Then x = h₁n₁ and y = h₂n₂, where hᵢ ∈ H and nᵢ ∈ N. Now h₂⁻¹n₁h₂ = n₃ ∈ N, as N is normal in G. So n₁h₂ = h₂n₃. In this case
xy = (h₁n₁)(h₂n₂)
= (h₁(n₁h₂)n₂)
= (h₁(h₂n₃)n₂)
= (h₁h₂)(n₃n₂),
---
This will translate directly into lean. If you do it this way, you will prove at least 10 of what would be described in lean as 'intermediate theorems':
∃ h₁ ∈ H, ∃ n₁ ∈ N, x = h₁ * n₁
∃ h₂ ∈ H, ∃ n₂ ∈ N, y = h₂ * n₂
h₂⁻¹ * n₁ * h₂ ∈ N
n₁ * h₂ = h₂ * n₃
x * y = (h₁ * n₁) * (h₂ * n₂)
(h₁ * n₁) * (h₂ * n₂) = (h₁ * (n₁ * h₂) * n₂)
(h₁ * (n₁ * h₂) * n₂) = (h₁ * (h₂ * n₃) * n₂)
(h₁ * (h₂ * n₃) * n₂) = (h₁ * h₂) * (n₃ * n₂)
h₁ * h₂ ∈ H
n₃ * n₂ ∈ N
I probably should know it. Give me 30 minutes to prove it. (Part of the magic is in "normal".)
My algebraic friends surely know it and they would never include it in a paper because everyone knows it.
I'm surprised it's not in mathlib. Perhaps it is and the AI made a copy. Perhaps it isn't and it is a nice PR for beguiners.
The part of the proof that I quoted just proves that the product set HN is closed under multiplication - the product of any two elements in HN is also an element of HN. This is part of proving that HN is a subgroup. You might call it an 'intermediate theorem' to that proof.
My point isn't that this is missing from mathlib, or that this result is part of the work mentioned in the blog post. It's that doing this proof in a way that matches the textbook proof requires you to prove a large number of "intermediate theorems", and that those "intermediate theorems" often look more like computational steps than anything that a mathematician might call "theorems".
In particular, note that the 10 required intermediate theorems I mentioned all refer to free variables.
By the way, there is a steady stream of people who come into the "new members" channel on the Lean zulip and ask for ideas for a minor contribution they can make. The stock answer is generally that the low-hanging fruit has been picked.
But that isn't really accurate. If your goal is to get something, anything, into mathlib with your name on it, you probably can. Choose some undergraduate exercises, try to formalize them using mathlib, and at some point you'll run into some convenience lemmas that you wish were present. You can then produce one of those lemmas and try to get it accepted.
(As part of a project I'm working on, I produced a proof that involved showing that a function was bijective from the already-existing mathlib theorems that it was injective and surjective. There was no one-step existing theorem despite the existence of the injectivity and surjectivity theorems.
When I complained about some other part of my proof, somebody else picked up on that and quickly submitted a convenience theorem directly stating the bijectivity. That's the kind of thing I'm talking about, though you can go more complex than that example.)
13M lines does seem extreme and there is probably a lot of inefficiency given the way the proof was developed. Cutting it down is probably a long road, but is also a very well defined problem that AIs can probably just go do with enough time and budget now.
How can you be so sure its not result of inefficiency?
I have used Fable for formalisation and it will, unless I catch it, reprove results it previously had proven, inline, in other results.