Proving a theorem is a one-way function

✨ With all the healthy chatter about "verifiability" ignited by Andrej Karpathy, I want to point out that even if "verifying" (a program) can be hard, it is still easier than coming up with a good idea for a program. I'll get back to verifiability because I think it is also missing a lot of dimensions, but let's first consider why verifying might be easier than creating the concept to verify: I'll use an idea from cryptology (one-way functions) and illustrate it with math (proving or verifying a theorem vs. coming up with a theorem worth proving).

📈 Researchers have been making enormous progress toward theorem-proving algorithms, bolstered by the breathtaking pace of genAI advances. And yet, however difficult it is to prove theorems, however heroic the efforts to prove or disprove conjectures, it all pales in comparison to the power of willing these theorems and conjectures into being in the first place.

Why, you ask?

📚 One could write an entire infinite library made up of books that prove, flawlessly, trillions upon trillions of irrelevant theorems. In the terribly infinite space of all possible theorems and conjectures, the ones that have value, the ones that advance knowledge, the ones that open up vast spaces of previously unimagined mathematical landscapes, all add up to an ensemble of measure 0. They are impossible to find, unless intuited by a human brain of un-algorithmic creativity. Well, at least that’s my conjecture.

🧠 Think of the Riemann Hypothesis, Hilbert’s other problems, the Twin Prime conjecture, Goldbach’s conjecture, Poincaré’s theorem, the Hodge conjecture, Navier-Stokes existence and smoothness, the Collatz conjecture, the now-disproved Hirsch, Kaplansky unit, Euler’s sum of powers, Borsuk conjectures, or the now-proved Sensitivity, Zariski and Fermat’s last theorems? They all sparked major discoveries, programs of research, often in multiple fields and directions, sometimes requiring the confluence of multiple disciplines to address.

The ageless elegance of these conjectures and theorems is testament to the ingenuity and creativity of humans and also suggest that, just as it is easy to multiply two extremely large prime numbers but very hard to factor the product, it is somewhat easy (ok, easier) to prove theorems (except of course for the ones listed above) and very hard to come up with a theorem worth proving. Proving a theorem is a one-way function. For now.

@terence tao

@jean-philippe bouchaud

@peter thiel

@tudor achim

@vlad tenev

Image modified from a great post, The Unreasonable Ineffectiveness of AI for Math: link