[nilkn]

Since this isn't in Lean and it's extremely easy for something like this to contain a subtle mistake, I think I'd prefer this be announced by a professional mathematician. The proof appears relatively short and elementary (not to be confused with easy -- just not using any advanced or modern machinery) so it shouldn't take long for the mathematics community to do a peer review. Without that, you could easily crank out hundreds or thousands of PDFs like this that all look plausible and are beyond the ability of a gifted amateur to review.

[mmoskal]

https://github.com/openai/cdc-lean

[nilkn]

Perfect -- that's great to see. The proof strategy in Lean appears essentially identical to the natural language strategy (as much as is reasonably possible). I think this settles it!

[bigmattystyles]

But they used LateX

[varjag]

…and thank God it's not Lean.

[nilkn]

Nah, if it produced the proof in Lean which is automatically verified to be correct, you could then just write a natural language version of the proof to accompany it (often using AI to do that part too). That's becoming the standard for AI math these days. Generating purely informal natural language proofs via AI is fundamentally bottlenecked by requiring rare professional mathematician review on every single candidate output proof.

[varjag]

Human unreadable proofs have only limited value.

[nilkn]

I disagree. It's the only way to scale AI mathematics far beyond human mathematics. Any interesting verified result would, obviously, be rewritten back into natural language for human understanding and consumption (as well as potentially for the benefit of AI conjecturers too). You are falsely assuming that advances in formal mathematics would not feed back into similar (potentially massive) advances into informal mathematics, and I think that's simply wrong. We're just at the very, very beginning of that curve.

I think this is, in fact, inevitable. It's the exact same RL loop that allowed AlphaGo to vastly exceed the world's top human players. You can theoretically RL formal proof techniques vastly beyond human capability by removing the need for any human review for correctness. It is completely reasonable to assume that "informalization" will become a real sub-field of mathematics in the near future.

[varjag]

I didn't say they have no value. Just limited value. A novel readable proof that expands the horizons of human insight is certainly more valuable than a megabyte sized trychnobezoar of machine generated predicates.

[nilkn]

You are assuming that the latter, once autonomously discovered and verified at scale, could not simply be translated into the former, also perhaps autonomously at scale (or otherwise selectively as determined by human interest, taste, and relevance).

[perching_aix]

Why not both? Not sure why you're presenting this as one or the other.

[UltraSane]

What a ridiculous thing to say. If it was verified in Lean we could be much more confident the proof is correct.

[varjag]

It's not a long proof (it's not in Lean after all) so easy enough to comb through for a domain expert.

[UltraSane]

If it was in Lean anyone could verify it instantly. That is the huge advantage of it. Manual math Proof verification labor might be the most limited resource ever.

[varjag]

How does it matter if it Lean verified or a human verified proof if you comprehend neither?

There can't be too many people working in that corner of graph theory, and I expect the result to them being eminently straightforward.

[jackphilson]

One requires you to trust a human and the other requires you to trust mathematics.