FOM: Smale's list of mathematical problems for the next century

[joe shipman]

In the Spring 1998 Mathematical Intelligencer, Steve Smale (responding to a
query by V.I. Arnold on behalf of the International Mathematical Union) lists
18 important "mathematical problems" for the next century.  This provides a 
good set of examples for my project to classify open problems by logical type.

Smale's list is not intended to encompass all areas of math, but rather areas
he is acquainted with; presumably Arnold will collate responses from a number
of mathematicians to arrive at broad list worthy of being compared with
Hilbert's famous list of 1900.  (Is there any mathematician alive today who
even approaches the breadth of Hilbert and Poincare?  Can anyone name someone
who has made significant contributions to more than two mathematical areas?)

Remark: It is not necessary for a problem to be precisely stated in the
formal language of mathematics for it to be a good and important problem;
Hilbert's 10th problem is one of several on his list which did not admit 
precise formulations at the time.

The first three problems on Smale's list are the Riemann Hypothesis, the 
Poincare Conjecture, and the P=?NP question.  As I observed last month,
these are provably equivalent to sentences which are pi^0_1, pi^0_2, and
pi^0_2.  Interestingly, Smale's versions of the statements are of much higher
logical type.  He states the Riemann Hypothesis in terms of the zeta function
defined by analytic continuation from the series 1^(-s)+2^(-s)+... which is at
least 3 levels of powerset above arithmetic (analytic continuation involves 
sets of functions of complex numbers -- I don't regard the passage from 
reals to complex numbers (pairs of reals) as going up in type).  His version
of the Poincare conjecture involves the differentiable category rather than
the topological, PL, or simplicial categories, which is also at least 3 levels 
up.  The theorems that these categories are all equivalent in dimension 3 
(by the way, who proved these equivalences?) reduce the statement to a 
combinatorial one.  Finally, Smale even states Pnot=NP in a version that
requires real numbers ("There is no polynomial-time algorithm for deciding
the Hilbert Nullstellensatz over C").  This requires defining "computation 
over C" and Smale cites his papers with Blum, Shub, and Cucker which 
develop this theory.  Here at least Smale remarks that replacing C with Z2
gives a provable equivalent to the classic conjecture Pnot=NP.

I won't attempt to classify all of Smale's 18 here; but I will discuss the
ones which in my opinion are the most interesting.  Nearly all of the 18
involve computation theory, dynamical systems, or both.

5: Can the set of solvable 2-variable diophantine equations be decided in
time O(2^(s^c)) for some constant c, where s is the input size (sum over all  
coefficients a of (1+log(|a|+1)))?

8. Extend the mathematical model of general equilibrium theory to include
price adjustments.  (This one is imprecise, and I would regard it as too far
out to be in such a list, unlike the problems of mathematical physics.  But
the flaws in the current model are clear enough and this problem could
conceivably be solved in a useful way.)

9. Is there a polynomial-time algorithm over the real numbers which decides
the feasibility of the linear system of inequalities Ax>=b?  (I can't get
excited about this one given the solution of the analogous, more famous 
problem over Q by Khachian and its practical implementation by Karmarkar).

13.  Hilbert's 16th problem: dx/dt=P(x,y) dy/dt=Q(x,y) diff eq on |R^2.
Is there a bound K on the number of limit cycles of the form K <= d^q,
where d=max(deg P, deg Q) and q is a universal constant?

15. Do the Navier-Stokes equations on a 3-dimensional domain in |R^3 have a
unique smooth solution for all time?

16. The Jacobian Conjecture: Must every polynomial map from |C^n to |C^n 
whose derivative at each point is non-singular be injective?  (This very nice
problem is the only one on Smale's list I would add to my own list.)

18. "What are the limits of intelligence, both artificial and human?"
This at first looks ridiculously imprecise, but mathematics could conceivably
have something important to say here.  Godel's Incompleteness Theorem is
relevant, and physical "Theories of Everything" could have nontrivial 
implications regarding what we could theoretically come to know.

I suspect all of the precisely stated problems in Smale's list can be rendered
in second-order arithmetic by the usual methods of coding for functions on
complete separable metric spaces--can Steve or Harvey confirm this?  Can we
apply Absoluteness theorems like Shoenfield's to conclude that Smale's 16  
precisely stated problems are absolute in some useful sense (e.g. true in V
iff true in L)?

My favorite problem that Smale left off is the Invariant Subspace Conjecture
("every bounded operator on Hilbert space has a nontrivial invariant subspace").
It is equivalent by straightforward coding to a pi^1_2 sentence (use the
representation of Hilbert space as l2(|R), the set of square-summable 
sequences).

Can anyone out there suggest some more problems?  I'd like to end up with
four classes, in order of decreasing definiteness:
1) Problems equivalent to arithmetical statements
2) Problems not in 1) which are still absolute (and can someone please 
suggest a good sense of "absolute" to use here; if I can't find a fully
satisfactory one I'll replace "absolute" with "equivalent to statements of
second-order arithmetic").
3) Problems equivalent to statements in the language of set theory
4) Imprecisely stated problems.

Of course, a problem in category 4 could end up being regarded as much more
definite than one in category 3, as the examples of Hilbert's 1st and 10th
problems prove!

-- Joe Shipman