[FOM] Actual Logical Complexity

[Harvey Friedman]

What is the actual logical complexity of theorems that have been cited
for the Fields Medal? And for other awards? Of course, much larger
sets of theorems can be considered from this point of view, but those
cited for Fields Medals and other major awards seem more realistically
manageable to analyze. How has this changed over time (if it has)?

I am taking about the usual classification

Pi01, Pi02, Pi03, Pi04, ...

Sigma01, Sigma02, Sigma03, Sigma04,...

Pi11, Pi12, Pi13, Pi14, ...

Sigma11, Sigma12, Sigma13, Sigma14

and higher.

Now there is a problem in making this reasonably precise. After a
Theorem is proved, the Theorem becomes provably equivalent to 0 = 0,
which is in both Pi01 and Sigma01.

So we have to be a bit careful just how we talk about this.

One way of talking about this in a reasonable way is to look at the
Theorem and see what is the lowest form you are able to put it in,
where the equivalence is by general considerations that do not involve
the ideas from the proof of the Theorem.

Of course, this is a bit awkward, and maybe sounds judgmental. BUT I
claim that it is a rough enough guide and that matters are robust
enough, that one can informatively make these calculations.

If things turn out for some reason not to be as robust as expected in
some situations, then that can be given special analysis.

CONJECTURE. The complexity levels for theorems cited for Fields Medal
and related awards have been generally going down over time, and are
as indicated below. Actually, I am NOT all that confident in my
instincts here, and am quite interested in seeing what people find
when they actually look. I just haven't had the time to take a real
look.

1. Pi01. I think this is most common. Most famously, FLT. Riemann
Hypothesis, still open, is Pi01 by reasonably general considerations.
However, using yet more general considerations, perhaps you would not
get down to Pi01. But what would you get down to via various
considerations? And how should we deal with this robustness issue
here?

One way is to step back and expand the problem. So we are looking at
complex functions defined by nice series, and stating some nice
property of the complex function. Well, without dealing specifically
with the Riemann Zeta Function, what can you say about such questions
in terms of logical complexity? If you pick the right level of
generality, presumably you can get precise math logic results about
complexity here.

Then there is Poincare Conjecture, again Pi01 by fairly general
considerations. Once again, step back and expand the problem, and see
what complexity you get, also with an eye to exact math logic
complexity results.

There are many situations like this to explore. Also Goldbach's conjecture.

2. Pi02. Most famously, Twin Prime Conjecture. But it should be
factored in that there are obvious stronger conjectures that are down
to Pi01. The expectation is that any proof would prove such stronger
statements.

3. Pi03. I think a lot of stuff in Diophantine Approximation, and also
stuff in Diophantine Equations where you only get "at most finitely
many solutions".  Roth's theorem, Mordell stuff.

4. Other arithmetic statements. I don't know if we are going to find
Pi04. By the way, the whole field of finite group theory. Is this all
Pi01 and sometimes Sigma01?

5. Now what is cited in Fields Medals and other Awards that is not
arithmetic? Well, what about countable infinite combinatorics? And
infinite graph theory? Here it would seem that one runs across Pi11,
and also Pi12. There will also probably be sometimes, that there are
stronger statements that are arithmetic, and that needs to be factored
in.

6. What about cited results in ergodic theory? Of course, often, and
probably usually, the use of measure is really by general
considerations far closer to the computational than would be indicated
by the usual set theoretic development of measure theory. So I expect
that general considerations would push this cited stuff down into the
Pi01.

7. What about Fields Medals and other Awards in functional analysis
and operator theory? Here there is of course the best chance of seeing
stuff that is not only arithmetic, but maybe not even Pi11. Or maybe
much worse. Of course, there is the continuum hypothesis, but that was
not a theorem. Instead, Cohen won the award for a relative consistency
proof, which was of a Pi01 statement. So Cohen was Pi01.

Harvey Friedman