macintosh.world | Log In | Register

Today | News | Books | Recipes
Notes | QuickTake | Wiki | Browse
Maps | Reference | Reddit | YouTube
Chat | Games | About

Back to HN

Lean verification of the Riemann Hypothesis

by g-b-r | 1087 points | 907 comments | 2026-11-21 08:36:45 Central

Open Source Link | Read Source Here

Open on Hacker News

Comments

rcr-anti
While still possible, the proof exploiting a bug is
vanishingly small now. Following a few bugs and bad proofs
this year, there are a number of different
implementations, in different languages, and with
different levels of proofs of their consistency. con-leche
and con-ron are the heavy hitters, with consistency proofs
of themselves. So for RH to be false, there'd have to be a
bug in all the kernels that affects both the consistency
proofs and the RH proof itself.

  > magicalhippo
Since I'm not terribly familiar with Lean, math folks
are generally satisfied the provided proof encodes the
RH correctly I presume?edit: I need to learn to read,
that's the first part of their statement.The statement
of the Riemann Hypothesis is correct. This statement
is part of Mathlib: RiemannHypothesis and has been
carefully vetted by experts in Lean and number theory.

    > > brooke2k
The statement of RH that it proves is taken
directly from Mathlib, so it's extremely
well-vetted and longstanding (from my
understanding).

      > > > jychang
Correct.They don't use some random definition
of RiemannHypothesis, they use the version
here:
https://leanprover-community.github.io/mathlib
4_docs/Mathlib...Note that this definition is
years old. It's very well vetted. It's not a
case of "the proof works, it just doesn't
actually prove what you think it proves".If
you read the blog post, it says they added a
"Challenge.lean" file. What that means is that
instead of taking for granted the proof is
trying to prove Riemann, they added a small
file which reads RiemannHypothesis from the
Mathlib library mentioned above, and forces
the proof to match that.They also mention
running comparator, which is important because
it checks for all the ways a proof might
mathematically "cheat". For example, if you
are trying to prove 1+2=5, and you redefine 2
as 4, then your bad proof would actually
compile in Lean at first, but then comparator
checks would discover all the tricks like that
and declare the proof invalid.Additionally,
they mention compiling the proof with
different Lean kernels, not just the mainline
one. This rules out a way a proof This means
the proof cannot just take advantage of a bug
in the mainline Lean kernel. Importantly, they
mention compiling the proof with con-leche,
which uses a kernel that has been
mathematically verified. Using con-leche is a
lot slower, but the fact that the proof works
on multiple kernels including con-leche means
that it's not taking advantage of some bug in
Lean.At this point, I would say the proof is
almost certainly true. The only obvious way it
could be false is if ZFC itself is
inconsistent or something wild like that, and
the proof took advantage of it. But if ZFC is
inconsistent, all of mathematics is in
trouble.

        > > > > meowface
I wonder if in N years, when we (might)
have crazy ASIs that make Fable 5.2 look
like a nematode, maybe we'll see things
like this as completely trivial and
banal.A machine intelligence might devise
something as (seemingly) difficult as the
Riemann hypothesis, but checking if what
it posits is correct might be like a fast
test command in a git repo, and so it can
keep iterating on many ideas without being
bottlenecked by waiting centuries or,
perhaps even hours, to know if the ideas
are true.But then one could even imagine
they'll one day be so powerful they could
do this and more without ever using a
formal system. They will just naturally be
that comprehensive and rigorous
internally, with something like Lean
making them 100% instead of 99.99..%
confident.And eventually this would extend
to almost everything, besides maybe
biology where it may only be able to
compress a human century into a day rather
than into a second.

        > > > > intuitionist
Isn't Lean stronger than ZFC? I thought
you could prove Con(ZFC) within Lean. So
it's possible that the formal system
encoded by Lean is inconsistent but ZFC is
not. (I don't consider this that likely,
though.)

          > > > > > btilly
Yes, Lean is stronger than ZFC. But
two of the checkers, con=leche and
con-ron, don't just verify based on
Lean. They come with a formal proof
from set theory that they cannot wind
up accepting an incorrect proof.In
other words you can ignore Lean. We
have a proof from ZFC, of the Riemann
Hypothesis. We have a proof,
acceptable in ZFC, that this proof is
correct.In other words Lean's
dependent type theory is used to
arrange its understanding of the
proof. But the actual reasoning that
you wind up with for this proof does
not need anything that doesn't follow
from ZFC.

          > > > > > tkz1312
Yes, Lean is stronger than ZFC. lean
has been shown to be consistent with
ZFC + infinitely many inaccessible
cardinals.

        > > > > hazenut
why is the verification is so fast this
time while last time (a few weeks ago? and
I can't remember name of that theorem) it
took a few weeks and they finally found an
error in Claude's proof?

          > > > > > mcherm
I am not certain which "last time" you
are thinking of, but I suspect that
the answer IS the Lean verification.If
an AI writes a paper with an argument
that X is true, it might be that X is
true, or it might be that the argument
in the paper is subtly flawed and X
isn't trueOn the other hand, if an AI
generates a step-by-step proof in
which each step can be mechanically
verified, then people might have
problems understanding the underlying
ideas, but once it has been verified
we know it won't have subtle errors.
And that is basically what Lean is.In
this case, they not only have a Lean
proof, they've verified it with more
than one verification tool (so it's
unlikely to be a bug in the
verification tool) and double-checked
whether the thing being proved really
is what we intended to prove. That's
rock solid.Getting an UNDERSTANDING of
the proof is another challenge, but at
this point we can be quite certain it
doesn't have errors.

          > > > > > gus_massa
The guy waited until he has the
verification before anouncing it. I'll
quote myself from the pararell
universe were he announced it with a
English only proof:> Meh. Lean or it
didn't happen.

        > > > > cyanite
If ZFC is inconsistent, every well-formed
closed formula is s theorem, and thus has
a proof.

          > > > > > jibalt
True but irrelevant ... in fact,
that's a fallacy of affirmation of the
consequent. That every statement can
be proven from logical explosion (if
ZFC is not consistent) does not mean
that every proof is a result of
logical explosion.Consider Euclid's
proof that there is no greatest prime.
It is valid regardless of whether ZFC
is consistent.Similarly, the Lean
proof of the Riemann Hypothesis
depends on Lean's type theory, not
ZFC's consistency. It's an explicit
machine-checked proof term, not a
non-constructive consequence of
logical explosion.

            > > > > > > mcherm
I don't think that's precisely
correct.> the Lean proof of the
Riemann Hypothesis depends on
Lean's type theory, not ZFC's
consistency.I believe it depends
on Lean's type theory which itself
depends on ZFC and that if ZFC
were inconsistent then Lean's type
theory would also be
inconsistent.> It's an explicit
machine-checked proof term, not a
non-constructive consequence of
logical explosion.It is possible
to make "constructive proofs" that
make sure never to use an argument
saying "not-foo is false,
therefore foo must be true". Such
a proof really would survive even
if ZFC were inconsistent (at least
inconsistent in certain ways).
However, I don't believe this
proof of the Reimann Hypothesis is
constructive. (I haven't read the
proof, but if it were, that would
be remarkable and people would be
discussing it: most proofs are not
constructive.)

            > > > > > > NonHyloMorph
So what is the exact relation of
zfc and leans type-theory? Are
they proofably aequivalent or what
does that depends on say?

        > > > > xeonmc
Given such a massive proof, is there any
possibility of accidental tautology
inadvertently hiding inside the mess to
the effect of "Assume A is true. A million
lines later: therefore A is true"?

          > > > > > johncolanduoni
Lean keeps track of any such
assumptions when constructing the
proof term, and would not allow them
to line up with an unconditional
statement like RH.

          > > > > > gpm
That there are tautology's in the
billions of line? Yes, absolutely.
There's every chance that the proof
isn't efficient and includes lines
that can be removed.That the end
result relies on those tautologies?
No. All lean would derive from doing
that is "a implies a" (which it would
let you introduce directly) and not
the statement "a". This is what
computers are perfect at, keeping
millions of different records straight
and not accidentally forgetting the
first half of the implication.

            > > > > > > wging
I think they intended to ask about
whether the proof could
effectively introduce unproven
statements equivalent to RH as
axioms (i.e. unintentionally
proving "RH implies RH" rather
than just "RH" by assuming RH at
some point within the body of the
proof; or the same, but instead of
assuming RH, assuming some other
statement necessary to the
proof).I believe the blog post
does answer that question, though.
They say in the article above that
"The four criteria in
https://xenaproject.wordpress.com/
2026/11/12/and-the-proof-i... are
all satisfied", and Question 3 in
that linked post covers such
cases. ("How do we know for sure
that there is no trick hidden in
the millions of lines of proof
files which [some words
omitted]... adds a new axiom to
mathematics saying that the
theorem is true?")

          > > > > > jibalt
Of course it's possible that the proof
is flawed, in that or numerous other
ways. That's why it's being formally
verified in multiple independent ways.

    > > tito
I made a tool so anyone can run the proof on their
computer, and you don't even need to understand
Lean. And there's a global leaderboard
too!https://riemann-at-home.github.io/riemann-at-h
ome/

  > ComplexSystems
For those of us who grew up on Gödel's incompleteness
theorem, can someone explain how these kernels can
prove their own consistency?

    > > dwohnitmok
They prove its consistency relative to another
mathematical theory we assume to be consistent.
That is if that mathematical theory is consistent
then so is the kernel. In the case of Lean's
con-leche and con-ron, it is proved consistent
relative to ZFC + infinitely many inaccessible
cardinals.ZFC + infinitely many inaccessible
cardinals is a fairly weak extension of ZFC widely
thought by set theorists to be consistent. This is
especially the case if ZFC is consistent (although
by Godel we can't know for sure!).ZFC + infinitely
many inaccessible cardinals being inconsistent
would be a really big deal! Given how confident
set theorists are about inaccessible cardinals
most likely it would mean that ZFC itself is
inconsistent.

    > > sunshowers
They can't - any kind of formal verification is
always with respect to a TCB - but you can get
pretty high assurance through making the TCBs
smaller and smaller, and making multiple
independent TCBs. The Lean community has done
both. I think at this point the chance of there
being an error is smaller than the chance that
aliens show up in the next year or similar.

      > > > haberman
Does this mean that the aspirations of
Principia Mathematica are now in effect
achievable? Whitehead and Russell were just a
century too early?

        > > > > btilly
No. Those aspirations are not possible.
Mathematics cannot be reduced to pure
logic alone - you have to assume
something.However we are now extremely
clear on what you need to assume. And why
some assumptions are necessary. And we
have collections of assumptions that are
very reasonable indeed.The result is that
there is a step of faith. But it is a step
that people are very comfortable and
confident with.That said, I would be
fascinated to know if this proof can be
transformed into a proof that does not
need all of the power of Lean. Can it be
turned into a proof using the Peano Axioms
alone? I think that has a good shot of
being true. But it would take a lot of
work.

          > > > > > stouset
Is it even true that there is a step
of faith?We have many proofs given a
set of axioms. But those axioms aren't
even taken on faith as much as they
are assumed to be true. In a universe
where they are true, the conclusions
are true. We could assume they are
false and prove other things about
universes for which they are false.I'm
thinking along the lines of Euclidean
vs. non-Euclidean geometry. Euclid
made certain assumptions about
geometry that were instrumental in
proving various theorems. But you can
also find geometries where those
axioms are not true! And the existence
of other geometries doesn't invalidate
Euclid's conclusions, it just means
that they're only true when its axioms
are taken.

            > > > > > > tga_d
Assuming we're not going down the
route of paraconsistent logics
(which ZFC etc. are not),
consistency isn't really something
you can do anything interesting
with if it's violated. If it turns
out you can also prove the Riemann
Hypothesis false under ZFC (which
would take out every other theorem
along with it), that's just bad
for math. So we have to take the
leap of faith that won't happen.

        > > > > bobson381
Ask the next gen of LLMs. We shall see
      > > > gpvos
TCB = trusted computing base
      > > > bmitc
What is a TCB in Lean or formal verification?
        > > > > sunshowers
The core set of things that, if you assume
they are correct, the proof holds.For a
non-Lean example, a memory-safe language
like Rust has unsafe code that forms its
TCB. Assuming that the unsafe code is
correct, safe Rust can't cause undefined
behavior.

          > > > > > alethic
To be clear, formal verification is
both with respect to a trusted
computing base, and with respect to a
theoretical framework. Any such
guarantees from formal verification
are contingent on the theorem
statement being correct, the
implementation of whatever framework
you're using being trustable, and the
meta-theory being sound.Rust doesn't
actually have a theoretical framework,
as far as I'm aware. I don't think
that existing work (ex. RustBelt) have
come close to capturing the full
extent of Rust in practice yet. As
such, it's totally possible in
principle for safe Rust to have
theoretically unresolvable memory
safety bugs... although it's pretty
obvious that it like, doesn't.

      > > > wavemode
> I think at this point the chance of there
being an error is smaller than the chance that
aliens show up in the next year or
similar.hah, so you're saying the chance is
less than 2%
(https://polymarket.com/event/will-the-us-conf
irm-that-aliens...)

        > > > > odo1242
There's a pretty big difference between
"the US confirms that extraterrestrial
life / aliens exist" and "aliens show up"

          > > > > > yard2010
Imagine 300 millions ago, something
living on a not far planet, thinking,
is there anybody out there? Doesn't
know that space and time are entwined
meaning it's not a question of where,
but a question of when

        > > > > jibalt
The chance that the polymarket is an
accurate Bayesian evaluation is 0%

          > > > > > wavemode
early in the year it was trading at
something crazy like 17%. was
basically free money.

      > > > wizzwizz4
When the same bugs show up in multiple
"independent" implementations of the "trusted
computing base", I start suspecting that
they're all ports of each other, making the
same unforced choices of algorithm etc. Many
folk from the LCF school will point and laugh
at the description of Lean's TCB as "smaller".
(Does the Lean kernel still contain an entire
copy of GMP?) If reimplementing the kernel is
much more than a weekend project, I'm
certainly not willing to bet against the
existence of errors, regardless of whether
people claim to have proven their absence.

        > > > > jibalt
> When the same bugs show up in multiple
"independent" implementations of the
"trusted computing base"Let us know when,
because that hasn't happened.

          > > > > > alethic
This did happen, in late July.
https://leodemoura.github.io/blog/2026
-8-1-postmortem-for-ke....The "Summer
of Soundness Bugs" was the main
motivation for the development of
con-leche.
https://leodemoura.github.io/blog/2026
-10-15-lean-now-ships-... con-leche
makes this pretty unlikely to occur
again, though. It's a formally
verified kernel with respect to a
set-theoretical model of Lean, that's
been implemented in both Lean and
Rust, and also has a version that's
been compiled using a formally
verified compiler with regards to the
Kraken x86 semantics. The
set-theoretic model theoretically
could be inconsistent, but it's quite
reasonably designed (ZFC w/o infinity
or choice and w/ a universe
hierarchy), so that's unlikely.

            > > > > > > jibalt
> checking with an independent
kernel still works, since it
required two distinct bugs in two
implementationsSo no, it ("the
same bugs") didn't happen.

            > > > > > > alethic
That line is not correct -- likely
AI slop. I have no idea why he
does this, but Leo de Moura
appears to slop out about half of
his blog posts. Not like, half of
his overall blog posts, but half
of each blog post -- every one is
this weird mixture between AI
prose and his own prose, from what
I can tell from the tone (and the
factual issues, like this one).
It's really unpleasant. Sadly,
they're also canonical reports, as
far as the history of Lean
goes.The same bug (in the handling
of nested inductive types) was
indeed present in two kernels. It
was present in Lean's standard
kernel, and it was present in the
independent lean4lean kernel. The
"Collatz proof" using it actually
slipped by three kernels in total,
because the construction it used
just-so-happened to also exploit a
different bug in nomeda.

            > > > > > > jibalt
I quoted your own source. If you
think it is AI slop then don't
post it.

            > > > > > > alethic
Buddy, read the source better! The
contradiction is obvious.

        > > > > sunshowers
Sure, and aliens could show up tomorrow as
well.

    > > ComplexSystems
I feel like the real answer has gotten buried
here, so I will answer my own question. The
kernels are not "proven consistent" in any
absolute sense. They are proven equiconsistent
with ZFC plus inaccessible cardinals. This means
it is "as consistent as everything else we have
been doing for the last century," which is good
enough.

    > > mathisfun123
They don't - the lean kernel isn't written in
lean.

      > > > alethic
This is just a performance issue. In theory,
the Lean kernel could be written in Lean.These
independent kernels do not prove their own
consistency -- rather, their function is to
act as slower but more idiomatic/simpler
implementations of Lean's meta-theory. It
doesn't matter that they don't correspond 1:1
with Lean's official kernel at either a
theoretical or an implementation level,
because the independent kernels are not for
proving Lean correct -- they're for auditing
complex proofs, in a simpler system.What is
particularly interesting is that then these
independent kernels are "proven correct"! This
notion of correctness is specifically that
con-leche (et al) will only accept theorems
that are also correct with regards to a
particular model of set theory, with
membership / extensionality / other standard
ZF axioms, and an infinite hierarchy of
universes. This is (vaguely speaking) a
set-theoretic model of Lean. It is here that
Gödel's incompleteness theorems come into
play. Lean indeed cannot verify that this
set-theoretic model is "correct": what it can
verify, however, is that the type-theoretic
machinery is correct with respect to the
set-theoretic machinery. This removes the
possibility of an invalid proof slipping by by
way Lean's comparator (which can run
alternative kernels) by way of an
implementation bug.It leaves the possibility
that Lean's metatheory is inconsistent. This
is quite unlikely. The foundations of
mathematics have been well-studied, and Lean
builds directly on the huge amount of work
that has been done, particularly by the Coq
community, in figuring out what is and isn't
consistent. The Coq theorem prover was really
developed in conjunction with modern type
theory... Lean came in after a lot of
meta-theoretic issues had been ironed out,
thanks to them.

        > > > > ComplexSystems
That makes sense, but what is this model
of ZFC, and how does one specify it in
first-order logic?

          > > > > > alethic
https://github.com/leanprover/con-lech
e#set-theory-assumptio...

      > > > cloudbonsai
This is incorrect. There are multiple kernels
that are written in Lean: con-leche (written
in Lean) and lean4lean (written in Lean 4).
They both agreed that the proof is sound. See
https://math.mit.edu/~drew/grh/ for details.

      > > > koolala
"Con-leche is the first kernel for Lean
written in Lean and proven consistent."

    > > dev_dan_2
I am sure you will get some more detailed answers;
I am a bit lazy today; so I will give you the very
high level / informal version of the answer (Edit
from the future: It grew longer than expected,
whelp :D):Gödel's two incompleteness theorems
basically amount to "As soon as your system can do
a ridicolously little amount of things, then
either of two things is true in this system: 1)
You can express facts in your system that you
cannot prove within your system or 2) your system
claims that some false statement is true."Now,
because 2) is way way worse than 1), you design
your systems so that you are firmly in the 1) camp
- that way, we gain full confidence in the results
our systems proofs, and the price we pay is that
our system is less powerfull than it could be.With
Lean, it's similar. The foundation of Lean comes
from type theory. There, we do something that is
familar to above: We restrict our power (i.e.
"which Lean statements do get verified by lean?",
and we gain absolute confidence in its proofs
(ignoring implementation errors, hardware
limitations etc. for now). Intuitively: We have to
work harder to satisfy the typechecker/prover, but
when it is satisfied, then we have confidence in
it.-------------- Deeper down the rabbit holeYou
might have noticed that I seem to muddle the
waters a bit with programs, proofs, types and so
on... There is a deep reason behind it! In a very
strong sense, programs = types = proofs... So,
here is how it is all connected (including the
RH):- Lean is a programming language (like
Haskell, Rust, ... There is nothing stopping you
from writing a server in Lean and deploying that
binary somewhere in the cloud. Regarding developer
experience, you could think of it like a modern
Haskell without lazy evaluation and without its
historical warts)- programs can be tied to types:
We first check if the whole program as such has a
type ("do all of its parts fit together in a
strictly defined way?"). Only if it does, we
proceed (and for example, run it). If it does not,
then the compiler declares "this program is not
good! here is a type error!". Now, here is the
price hat Gödel proved we cannot avoid (if we
want to trust the typechecker): There are programs
that don't type check, but behave perfectly fine
at runtime. (That's the "we limit our power" part
- those are perfectly good programs where the
compiler throws their hand in the air and gives
up!)- Enter the third puzzle piece: proofs and the
Riemann Hypothesis: turns out, we can think of
types as theorems, and a successful type check as
a correct proof! And the RH is a hypothesis we
would like to prove...- So here is how it all ties
together: RH is written so that it can be used as
a type, in the Lean programming language. The
"main program" is basically just another ordinary
function with some input types, and returns the
type version of the RH being true. Because the
function needs an implementation, we are forced to
implement that function body - which are many
small functions that correspond to mathematical
theorems/lemmas if you look at it with the proof
glasses on. From the programming pov, it is just
functions that call functions that call functions
and so on. And from the typechecking point of
view; we compose a bunch of functions and check
whether input types and output types match
up.Finally, the payoff: *If that program
typechecks, then we know RH is true*, which is
what just happened!(PS: The same principle is
behind the computational proof of the
four-color-theorem. The proof of the four color
theorem is "simply" a program that typechecks,
where the final type happens to correspond to "can
we color any planar graph with at most 4
colors?")-------------- Further readingIf you want
to read up more about this, here would be some
sources (note: I am not up to date with how the
cool kids these days learn about this topic; so
there might now be better resources to learn
from!): - Here is how I learned about it first:
https://existentialtype.wordpress.com/2011/03/27/t
he-holy-trinity/
- wiki:
https://en.wikipedia.org/wiki/Curry%E2%80%93Howard
_correspondence
- "That's all cute and stuff, but basically fast
food for me, give me the good stuff!" okay, okay!
how about...
- tying quantum physics, topology, logic and
computing together?
https://math.ucr.edu/home/baez/rosetta.pdf
- anything on the nLab (a wiki/community(?) that
collects and explores those kinds of things...
nerds, I tell ya (no, I am not envious at all,
naaaah)). For example, this page is about the
relation between logic and types:
https://ncatlab.org/nlab/show/propositions+as+type
s

      > > > vbezhenar
So while I'm not going to question if that's
good approach, because if it's so popular, it
must be good enough.But on intuitive level it
looks so weird to encode math in types.When I
was taught math, the proofs were more like
sequence of statements. So if I would decide
to implement proof checker, I'd invent formal
language, which looks very close to commonly
used math language and which allows to just
write proof like it's written in book.
Probably a lot more verbose, without skips and
implied statements, but in the end, it'd look
just like a verbose and formal proof.Why did
math gone this lean type way and not the way I
described?

        > > > > alethic
This is a very good question! There are
two answers.First off, you can absolutely
do what you are describing. There are
systems like Metamath that assume nothing
beyond first-order logic and the axioms of
set theory, and apply these verbose
rewrites. See
https://en.wikipedia.org/wiki/Metamath for
more. However, Lean (and many past theorem
provers, too) have 1) preferred to
represent mathematical objects as types
rather than sets, and 2) built a large
amount of interactive tooling rather than
the blind rewriting of Metamath. The first
choice is essentially of elegance -- the
Curry-Howard correspondence indeed lets
you write propositions as types and proofs
as terms inhabiting those types, which is
a connection of deep beauty.
Ontologically, there is also an argument
to be made that representing a
mathematical object as a type is more
"correct". We don't really think of ex.
two as "{{},{{}}}" or "{{{}}}". We think
of it as "Two", or maybe "Zero +1 +1".
This is a win for types. Mathematical
objects are not grocery bags.Second, the
historical approach to theorem proving has
been interactive theorem proving. Theorem
provers were supposed to be a second brain
for students and computer scientists and
mathematicians... keeping track of
assumptions, suggesting possible tactics
to take... aiding the human in the process
of proof (and subsequently understanding),
rather than replacing them. The path of
uncritical adoption of AI that Lean has
taken, sadly, much replaces the human.
There is no real pragmatic reason for Lean
to retain its interactive (human) elements
any more (besides inertia) as AI scales
up. It might as well be Metamath, indeed.

        > > > > still_grokking
It's the most natural thing possible to
encode math in a programming language like
LEAN.Because logical propositions are
types (in such a language). That's just a
very fundamental part of math itself.Watch
this and you'll be
enlightened:https://www.youtube.com/watch?
v=IOiZatlZtGULEAN code looks actually
exactly like you propose; it supports most
conventional (Unicode-linearizable) math
notation, and you just write expressions
like in any other functional language.
Close to the textbook, but more verbose
and stiff as it's a formal language, while
math notation isn't.

          > > > > > NonHyloMorph
That lack of relative verbosity and
stiffness of mathnotation (what a
thing to say haha) to be considered as
a proper strength evtly. I'm consider
myself as layity in this, but is an
interface thinkable?

        > > > > rramadass
The main issue is on how you define a
"Type". There are two different logics
here;1) Classical Logic/Set Theory (this
is the one you are talking about). Here
Type = Set of values defined by membership
rules (extensional/intensional).2)
Intuitionistic Constructive Logic/Type
Theory (this is what is preferred for
proof assistants). Here Type = Set of
constructive (often inductive) proofs
where the proof itself is the value.As an
example, think of defining the Type
"Even_t"; under (1) it can be a predicate
"x % 2 == 0", while under (2) it is
defined inductively as "0 is Even_t; if
construct(n) is Even_t so is
construct(n+2)".Notice that in the latter
case a Type maps nicely into the idea of
"a computation" and the fact that the very
act of generation of one of its
inhabitants constitutes "the proof" that
the value has that property!Whereas in Set
theory Types are just subsets. But because
you can mix anything into a set, an
untyped term can be nonsense and will only
get caught when you try to use it. Type
Theory disallows it by construction.This
leads to the "Curry-Howard Correspondence"
so you get a mapping between logic and
type theory concepts -
https://en.wikipedia.org/wiki/Curry%E2%80%
93Howard_correspon...This idea of "Typing"
can further be extended (with additions of
Dependent Types etc.) giving a complex
matrix of powerful Type Theories
represented by what is known as "Lambda
Cube"
(https://en.wikipedia.org/wiki/Lambda_cube
) and their implementations in proof
assistants eg. Calculus of Constructions
(CoC), Calculus of Inductive Constructions
(CIC) etc.Finally, note that not all proof
assistants use constructive logic, several
use straight ZFC/HOL. Amongst those that
use constructive logic it is usually only
the kernel (containing the Type System)
which models it while the rest of the
system still uses classical logic.PS: See
also the previous discussion Why is
dependent type theory more suitable than
set theory for proof assistants? -
https://news.ycombinator.com/item?id=25167
468

        > > > > dev_dan_2
To add to the other answers, let me
address the experience of "a series of
steps" versus "a big single expression
with a type" - real life is calling, so I
have to make this quicker than I would
like to; feel free to ask any followup
questions / for clarification! I am sure
others or later, I when I am back on the
screen can answer :)So the very short
version: There is no difference between
those two worlds if you squint your eyes
hard enough! They are equally powerfull;
just different ways of expressing the same
truth. This is the whole declarative
("WHAT should the end result be") vs.
implerative ("HOW to achieve the end
result")stuff, but it's all the same at
the end. Some examples: - SQL is
declarative; but under the hood, it will
get translated to a sequence of operations
on the database by the query engine (or
however it's called)
- HTML is declarative; but there is no
theoretical reason stopping you from
building some sort of "imperative" HTML
where you just add elements and stuff in a
sequence of steps and at the end; are
shown the same webpage (in fact, there are
GUI frameworks that build up the GUI in an
imperative manner; for the web,
transmitting a declaration of what you
want rather than a program that constructs
it was the more practical choice I assume)
- Haskell is often considered declarative
(for good reasons), but if you think about
the IO type as ("Hey I am a wrapper type
and all I do is to enforce that step A
happens before step B"), then you are
pretty close to a imperative way of doing
things again
- Go/Java/C#/Python with types are almost
always considered imperative; but you can
also put on the type checking hat and
pretend that the program is just one big
function that will - if written correctly
- have a final type. How does composition
happen here? It's basically the line
break, line :103 is executed before line
:104, so lines :103-:104 can be viewed as:
"the function that does whatever :103
does, then whatever :104 does", and it has
the type "whatever input type :103 has and
whatever input type :104 has", and type
checking ensures that all those pieces fit
together neatly.

They can even be mixed; in the proof
assistant Rocq (formerly known as coq),
there where both styles used often. In
Lean, as I vaguely remember, you can pick
both style too, so to say.I think the
pragmatic answer is that most such
languages originated from the "one big
function" school, and so it is more
natural to program/proove in that
way.---------------------------*Wait, does
this mean that every proof I learned can
also be done in this "one big function"
way, instead of "a series of steps"?*Yep!
But you will find that it is not really
practical to do so. A good exercise for
sure though; and something I did (by that
I mean: infering types on paper; not
really taking proofs I know and doing them
be type inference on paper) by hand when
diving deeper into this topic in grad
school.Here is how that approach looks
like, roughly:
https://www.researchgate.net/figure/Exampl
e-of-type-inferenc... (the term I search
for regarding illustration is: "type
inference examples")

      > > > matltc
Thank you very much for this explanation and
the list of sources.

        > > > > dev_dan_2
Sure, and I am very glad to hear that you
liked it! :> (I really want to start
blogging soon! Then I can simply link it /
paste from it haha)

  > davidguetta
how unreasonable is it to think that during the ai
assited claude bruteforce process, it bruteforced also
the kernel and built on a randomly found logical
inconsistency

    > > grandpa
This is covered in point 4 of the linked post. The
exported raw proof has been checked by several
different kernels, not just one.

    > > Levitz
>claude bruteforce processI keep seeing people
referring to bruteforcing, and I don't see how the
concept makes any sense at all in this context. If
one was to "bruteforce" a lean proof, why would
that require AI at all?

      > > > rcxdude
It's a vague bit of terminology. Perhaps
"guided fuzzing" might be a better term (such
fuzzing still often being considered a kind of
brute forcing). You're still throwing a ton of
stuff at the wall and seeing what sticks but
you're been much smarter about it than just
generating completely random strings and
checking each of them. Generally it's
intractable to generate a Lean proof by 'pure'
brute force: the space of possible proofs
quickly dwarfs the universe, so you are really
depending on the intelligence to do most of
the work: the raw number of attempts is what
pushes something that's currently barely
possible over the finish line.(Also, it's not
obvious how much raw compute was spent on
this: the claim of the proof mentions fairly
close engagement as opposed to OpenAI's
'massive unattended swarm' approach to the
Navier-Stoke's problem. Obviously quite a lot
would have been available but I don't think
there's public information on how this was
actually done)

        > > > > bigDinosaur
You just described all of research which
uses the scientific method which when it
comes down to it is making educated
guesses (fine, hypotheses) and then
validating them in some logical or
empirical way.

          > > > > > ShinyLeftPad
When you can have 100 Claude instances
going at it in parallel at 100x speed
each without requiring food or sleep
it def helps;)

      > > > davidguetta
10000+ agents in parallel sounds like a form
of bruteforcing to me even if not the original
meaning

        > > > > riedel
In empirical research you would call that
p-value hacking. The improbable becomes
more probable. However, IMHO, randomly
hitting a bug seems still quite improbable
but certainly more probable as if this was
a single human. LLMs rather being
optimistic than doubtful certainly does
not help in this case. But I guess like in
other software development running other
agents to find those bits in the proof
seems equally feasible.

        > > > > inglor_cz
That is not what bruteforcing means.
Parallel work is basically how modern
science operates - there is approximately
10 million active human scientists across
science, which means thousands studying
the same thing globally.For an analogy ...
imagine 10000 lockpickers studying the
same type of lock and trying to unlock it.
That is what it is.Bruteforcing would mean
smashing the lock with a sledgehammer. You
don't even need 10000 sledgehammers for
that. The difference is that you don't try
to understand the lock, you just overwhelm
its construction by sheer force.

          > > > > > shunted22
That is basically what brute forcing
is in computer science.Imagine I'm try
to guess a key design that works and
spin up an insane amount of compute to
keep trying different designs and
eventually find the needle in the
haystack. That's basically
bruteforcing it because you find it
due to compute power instead of any
particularly elegant solutions.

            > > > > > > inglor_cz
I guess this is similar to judging
at what point a heap of sand
starts being a heap. There is
somewhat of a spectrum for
bruteforcing.Trying the entire
solution space out blindly -
definitely brute forcing.Reducing
the tries by half using some
primitive reasoning - still brute
forcing.(somewhere here, brute
forcing stops being true brute
forcing, but everyone's criterion
is a bit different)Reducing the
tries logarithmically - not really
a bruteforcing anymore, a good
reduction.

        > > > > Levitz
Linux development was bruteforced then I
guess

        > > > > cchance
But 100000 scientists doing it isn't?
        > > > > jibalt
Everything sounds like a form of something
else by that logic.

      > > > smalltime-eel
Because LLMs are trained on a massive corpus,
require hundreds of billions of dollars of
resources, have billions of parameters and run
on manhattan-sized datacenters.So yes it's not
the traditional definition of bruteforce, but
yeah. LLMs are brute forcing stuff

        > > > > inglor_cz
You're getting confused by your own
words.LLMs indeed wield huge cognitive
force, bigger than our brains can, but
being really smart is not the same as
bruteforcing stuff. If it was, we would
call Einstein or von Neumann bruteforce
scientists. They weren't, they were just
very, very smart.

        > > > > jibalt
They aren't, AND that's not the question
in the comment you responded to.

    > > 8note
couldn't you similarly brute force claude to find
and point out that inconsistency?

    > > dev_dan_2
very, due to the precautions explained in the
link. For example, they used multiple kernels with
different implementations etc.

    > > quantumspandex
As unreasonable as assuming all human's peer
reviewed proofs to be incorrect due to an error
collectively missed by all humans.

      > > > davidguetta
Godel theorem kinda adresses one form of that.
Its not an super far fetched idea on the first
place

        > > > > inglor_cz
I would classify this supervague utterance
as "nicht einmal falsch".

      > > > awesome_dude
Which isn't actually unreasonable. The chance
of it happening is vanishing small, but
collective errors have existed before in
software and humans (usually stemming from
some shared misunderstanding)FTR I am not
saying this is an example, just that it's
always possible.

    > > jibalt
Infinitely unreasonable.
    > > throw310822
Who said that Claude bruteforced anything, btw?
    > > anon291
Highly unlikely. The lean kernel has been heavily
scrutinized

  > acchow
My understanding is that the Lean kernels only
demonstrate that the Lean expression is correct.The
actual Lean proof (written by human + AI) still goes
through a compiler to generate the Lean expression. So
it's still possible there are compiler bugs.I'm hoping
someone with a deeper understanding of this system can
dive in.

  > psychoslave
Even exploiting bugs would be interesting and
constructive, as it would reveal some things to fix.

    > > Timwi
Well yeah, if we can find the bug(s). The big
worry is that we might overlook the bug and go on
our merry way assuming the claimed results are
true when they're not. (I don't see that happening
in the case of the Riemann hypothesis, but the
same worry exists for all proofs that exist only
in the form of Lean code, such as the massive dump
from OpenAI.)

      > > > TeMPOraL
It's math. Presumably if it's wrong after all,
sooner or later it'll be found out because
stuff built on top of this result will not add
up.

        > > > > soVeryTired
I wouldn't be so sure - people have
assumed both the Riemann hypothesis and
its negation for 150 years and haven't
been able to derive a contraction in
either case.What would be interesting is
if we challenged an LLM to prove a known
false statement close to the Riemann
hypothesis. If it manages to do that, we
know it's exploiting a bug.

          > > > > > Timwi
That would be interesting indeed, but
it would be difficult to control for
the circumstance that the LLM likely
knows that the statement in question
is known to be false (while it
certainly knew Riemann to be an
unsolved problem).

        > > > > jibalt
It's the opposite ... anything built upon
an erroneous premise "adds up".

      > > > geysersam
While it's possible there is a bug, the models
are better at finding bugs than they are at
proving theorems. I find it hard to believe a
model can deliberately exploit a bug to obtain
a proof, but the same model cannot find and
demonstrate the bug if tasked to do so. That
leaves the option that there is a bug that
accidentally let us incorrectly prove GRH,
without having any know impact on any other
proofs, and having exactly the same effect in
all lean implementations. It seems too
unlikely to be a reasonable concern at this
point, except perhaps for the people
responsible for administering the price money.

        > > > > gus_massa
I agree, but I expect the models to reuse
the bugs to prove any crap. Like:fake
quote> In section 1 we prove that the RH,
in section 2 we prove ¬RH, and in section
3 we use the previous results to prove
that 2+2=5.It is possible that the bugs
are so subtle that are only useful to make
a fake proof RH but not other false
stuff.But from my experience adding bugs
to Racket (and cleaning them mostly before
sending the PR or before the release),
once you find a bug, it's posible to
minimize the code, isolate the bug and
create a regresion test that is almost
comical because it's obviously wrong.

  > orblivion
Thinking more - as more such redundant tools are
developed, surely someone will run all the existing
big proofs against them, including this one. So we'll
have more confirmations over time.

  > jgalt212
> the proof exploiting a bug is vanishingly small
now.Why do you say this? LLMs have been very recently
finding all sorts of heretofore unknown bugs and
exploits for languages and applications that have been
around for decades.

    > > LPisGood
If multiple implementations have proven each other
to be consistent, that would mean the consistency
proves themselves would have to have a bug

      > > > jgalt212
I hear what you're saying, but you can't be
too careful these days.

        > > > > stouset
There's being careful and there's being
conspiratorial. At this point, believing
that there's multiple soundness errors in
every Lean kernel that could all be
exploited simultaneously leans heavily
toward the latter.To be clear, that
doesn't mean it isn't possible. It just
means that it's extremely unlikely and we
have no a priori reason to to believe it's
plausible or even possible to do.

  > whimsicalism
is it still possible absent a flaw in the hardware
model for con-leche?

    > > layer8
The underlying type theory could theoretically
turn out to be unsound.

      > > > bwestergard
Which is perhaps not such a far-fetched
possibility?While I have not studied this
topic enough to really understand _how_, but
I've been told that type systems laid out in
frequently cited papers by the likes of Girard
and Martin-Löf were found to be unsound more
than a decade after publication. These issues
were then "patched", so to speak.Can anyone
better versed in type theory explain how
likely that is for the type system of Lean?

        > > > > NoahZuniga
Con leche has been proved to be consistent
if zfc is, so if it turns out to be
inconsistent the entire foundation of
modern day math turns out to be broken

          > > > > > pfdietz
I believe it's consistent if zfc +
existence of an inaccessible cardinal
is consistent. Is that equiconsistent
with zfc?

          > > > > > bwestergard
Wait, but wasn't that only "proven"
with Claude, in Lean 4 itself? So that
doesn't help us establish the
soundness of the Lean 4 type system.

  > luke5441
"This year" hints at them all being created this year.
Does that mean they have all been created via LLM from
the same corpus?

  > philipwhiuk
What about GRH? The post doesn't really address that
bit.

  > bannister7
> While still possible, the proof exploiting a bug is
vanishingly small nowThat's not how mathematical
proofs work, though. What you have proven is not RH
but rather the statement "either Lean has a bug or RH
is true". So at this point you might as well be
celebrating a Lean fuzzer.

    > > gus_massa
For traditional proof, it means "either X is true,
or the author and the editor and the peer reviewer
missed the mistake". I've seen errors in math
articles published in serious journals, mostly at
the typo level.

    > > stouset
There are multiple independent implementations of
the Lean kernel."Either RH is true or every
separate Lean implementation-some of which have
their own soundness proofs-has a soundness error
that can be independently exploited without
triggering errors in any of the other Lean
implementations."

    > > bannister7
There's also
https://emeraldbook.org/news/nov-2126/people will
believe any bullshit the most fascist companies
put out

killerstorm
If I understand correctly, for the purpose of the proof
Claude formalized a huge chunk of all modern math. So it's
a big result not only for GRH, but math foundations and
formalization.

  > jkhdigital
Yeah I'm wondering how on Earth a single conjecture
can require 17 million lines of code to prove, but if
it involved building up an entire ecosystem of
theorems that had not yet been formalized then I
suppose it makes sense.

    > > remus
> ...if it involved building up an entire
ecosystem of theorems that had not yet been
formalized then I suppose it makes sense.This is
pretty much it. Pre LLMs very little maths had
been formally verified and a lot of it relied on
proofs from humans convincing other humans, and
issues did arise which would occasionally mean
chunks of maths we previously thought were true
had to be reconsidered.Proving something in lean
probably involves writing a lot of proofs for new
areas, and the formal proofs are usually
significantly more verbose than a human proof
where a lot is often left for the reader.

      > > > gamer191
Out of interest, which maths needed to be
reconsidered as a result of attempted lean
proofs failing?

        > > > > zamadatix
I believe they were talking about humans
correcting human proofs pre-LLMs enabling
us to define things in Lean at a useful
scale.But, to your question, I don't think
any important error findings due to Lean
have been unrepairable yet (for some
definition of important). So far the ones
which have really failed to be patched or
been plain incorrect conclusions have,
thankfully, had a very small blast radius.

      > > > bmitc
> issues did arise which would occasionally
mean chunks of maths we previously thought
were true had to be reconsideredExamples?