Smale problems

The list of Smale problems was drawn up by Stephen Smale in 1998 in the Mathematical Intelligencer in response to a request from Vladimir Arnold to draw up a successor list to the list of open problems by David Hilbert from 1900 ( Hilbert problems ).

Stephen Smale's list includes 18 then unsolved problems. According to his direction of work, there are many problems from the field of dynamic systems and also those that belong to computer science (for example complexity theory using real or complex numbers).

Two of the problems appear in Hilbert's list ( Riemann's conjecture and the part of Hilbert's 16th problem on the number and location of limit cycles according to Henri Poincaré ), and Smale's problem 5 has references to generalizations of Hilbert's 10th problem. Some are more like a research program, for example on the expansion of economic equilibrium theory to include dynamic aspects or the question of the limits of intelligence. Four of his problems agree with the Millennium problems ( Poincaré conjecture , P-NP problem , Navier-Stokes equation , Riemann conjecture).

Problems 2, 14 and 17 are considered solved, for others there are partial solutions. Most of the problems are considered extremely difficult.

List of problems

Problem 1

Riemann's Hypothesis , the best-known open problem in mathematics, is of central importance in prime number theory. Hilbert's eighth problem.

Problem 2

Poincaré conjecture . Solved by Grigori Perelman after preparatory work by Richard S. Hamilton .

Problem 3

P-NP problem , the best known open problem in computer science and of central, also practical importance.

Problem 4

The problem is about the integer zeros of an integer polynomial in a variable and whether these are limited by an -invariant introduced from the complexity theory of Michael Shub and Smale (which depends on the polynomial f) ( -conjecture by Shub and Smale). The invariant is the minimum number of steps to build up recursively with elementary arithmetic operations (addition, subtraction, multiplication) starting with the variable . Is the number of different integer zeros of through limited by a universal constant ? According to Smale and Shub, a positive answer would mean that the decision problem for Hilbert's zero theorem is unsolvable and therefore applies to calculations over complex numbers. ${\ displaystyle \ tau = \ tau (f)}$ ${\ displaystyle \ tau}$ ${\ displaystyle \ tau}$ ${\ displaystyle f}$ ${\ displaystyle x}$ ${\ displaystyle f}$ ${\ displaystyle \ tau ^ {c}}$ ${\ displaystyle c}$ ${\ displaystyle P \ neq NP}$

Problem 5

The problem concerns Diophantine polynomial curves (Diophantine means defined over the whole numbers) in two variables of maximum degree . Can the existence of a solution be determined in a time (i.e. exponential time)? Is the question of the existence of a solution in class NP ? ${\ displaystyle f (x, y) = 0}$ ${\ displaystyle d}$ ${\ displaystyle 2 ^ {s ^ {c}}}$

Here is a universal constant and is a measure of the size of the polynomial (a height function, the definition of which includes the coefficients of the polynomial). ${\ displaystyle c}$ ${\ displaystyle s = s (f)}$

To define the height function : ${\ displaystyle s (f)}$

{\ displaystyle s (f) = \ sum _ {| \ alpha | \ leq d} \ max (\ log | a _ {\ alpha} |, 1)}

With

{\ displaystyle f (x, y) = \ sum _ {| \ alpha | \ leq d} a _ {\ alpha} x ^ {\ alpha _ {1}} y ^ {\ alpha _ {2}}, \; \ alpha = (\ alpha _ {1}, \ alpha _ {2}), \; | \ alpha | = \ alpha _ {1} + \ alpha _ {2}, \; \ alpha _ {i} \ geq 0.}

Smale suspects that the problem is very difficult, since the related 10th Hilbert problem, i.e. the decision problem of the solvability of Diophantine equations without restriction of the number of variables, is unsolvable according to Yuri Wladimirowitsch Matijassewitsch .

Another problem from this environment is whether there is an algorithm to decide whether a polynomial equation can be solved in rational numbers (for any number of variables). For integer polynomials this is the 10th Hilbert problem.

Problem 6

The problem that Aurel Wintner posed in his textbook on celestial mechanics in 1941 asks about the finiteness of the number of relative equilibrium points in the n-body problem of celestial mechanics for more than three bodies. Relative equilibrium points are not fixed points, but move on simple paths (uniform rotation around a center). In the case of the restricted three-body problem, there are five (the Lagrange points ). The finiteness in the case N = 3 was shown by Wintner, N = 4 by M. Hampton and R. Moeckel and for N = 5 the finiteness was shown in 2012 by A. Albouy and V. Kaloshin. For N> 5 the problem is open.

Problem 7

The problem is about the distribution of points on the 2-sphere under the influence of a potential. Specifically, Smale asked for an algorithm for finding N points on the sphere whose interaction potential is (with ) such that is with a constant and the minimum of the potential when varying over all . The algorithm should depend on N polynomially with regard to the holding time. Instead of a logarithmic potential, the Coulomb potential can also be used (so that the problem corresponds to the arrangement of N electrons on the sphere, Thomson problem ) or potentials with other power laws. According to Smale, the problem arose from his collaboration with Michael Shub (search for a starting polynomial suitable for a homotopy algorithm in the fundamental theorem of algebra ), but, as already mentioned, it is part of an old circle of problems about uniform point distributions on the sphere. ${\ displaystyle x_ {i}}$ ${\ displaystyle V_ {N} (x) = \ sum _ {1 \ leq i <j \ leq N} \ log \ left ({\ frac {1} {r_ {ij}}} \ right)}$ ${\ displaystyle r_ {ij} = | x_ {i} -x_ {j} |}$ ${\ displaystyle V_ {N} (x) -V _ {\ mathrm {min}} \ leq c \ log N}$ ${\ displaystyle c}$ ${\ displaystyle V _ {\ mathrm {min}}}$ ${\ displaystyle x_ {i}}$

This is also an algorithmic version of the Fekete problem ( Michael Fekete 1923). The corresponding points that minimize the energy are also called fekete points.

Problem 8

Introduction of dynamics (adjustment of prices) in economic equilibrium theory ( Arrow-Debreu equilibrium model ). The problem arose out of Smale's own preoccupation with mathematical economics.

Problem 9

A problem of linear programming : is there a polynomial-time algorithm over the real numbers for the determination of the solvability of the linear system of inequalities ? ${\ displaystyle Ax \ geq b}$

The problem is a decidable version of the question of a solution algorithm for the corresponding system in linear programming (where a function is also to be maximized). ${\ displaystyle cx}$

The simplex algorithm solves both problems, but in the worst case it is exponentially slow (even if it is polynomial on average according to Karl Heinz Borgwardt ). Nevertheless, there are polynomial solution algorithms for problems in linear programming. B. the ellipsoid method or the interior point method .

Problem 10

The general closing lemma in the theory of dynamic systems. For the Pughs is closure lemma ( Charles Pugh , 1967). What is needed is the solution for . ${\ displaystyle C ^ {1}}$ ${\ displaystyle C ^ {r}, r> 1}$

Let p be a non-migrating point of the diffeomorphism of a compact manifold . Can S be approximated with arbitrary precision by a diffeomorphism such that p is a periodic point of T ( i.e. fixed point of an iterate of T). ${\ displaystyle S \ colon M \ to M}$ ${\ displaystyle M}$ ${\ displaystyle C ^ {r}}$ ${\ displaystyle T \ colon M \ to M}$

Problem 11

Are one-dimensional dynamical systems in general hyperbolic?

A dynamic system given by a diffeomorphism is hyperbolic at a point if the derivative does not have an eigenvalue that is equal to an absolute value . be the closure of the set of non-moving points of the dynamic system. A dynamical system is hyperbolic (fulfills axiom A) if the periodic points are close in and is hyperbolic. ${\ displaystyle T}$ ${\ displaystyle x}$ ${\ displaystyle DT (x)}$ ${\ displaystyle 1}$ ${\ displaystyle \ Omega}$ ${\ displaystyle \ Omega}$ ${\ displaystyle \ Omega}$

More precisely, Smale formulated the problem as follows: Be a complex polynomial. The discrete dynamic system defined by the iterations of mappings is considered. Can be approximated by a polynomial of the same degree, so that every critical point tends towards a periodic point which is a sink? ${\ displaystyle T \ colon \ mathbb {C} \ to \ mathbb {C}}$ ${\ displaystyle T}$ ${\ displaystyle z_ {i} = T (z_ {i-1})}$ ${\ displaystyle T}$

A periodic point is a fixed point of the iterates of , . A critical point is a point with , a sink is a fixed point of with ${\ displaystyle p}$ ${\ displaystyle T}$ ${\ displaystyle T ^ {k} (p) = p}$ ${\ displaystyle w}$ ${\ displaystyle {\ frac {\ partial T} {\ partial z}} = 0}$ ${\ displaystyle T}$ ${\ displaystyle \ left | {\ frac {\ partial T} {\ partial z}} \ right | <1}$

The problem posed in this way is unsolved even for polynomials of degree 2 (also in the even more special case of the Mandelbrot set ).

An equivalent formulation from the complex dynamics is: Can a polynomial mapping be approximated by a hyperbolic mapping? ${\ displaystyle T}$

According to Smale, his student John Guckenheimer gave a positive answer to the problem in his 1970 dissertation, but later it turned out that his proof contained a gap. Likewise, in 1969 , Smale's doctoral student Zbigniew Nitecki gave a positive answer for the real case (illustration of the unit interval), which later turned out to be faulty.

M. Jakobson provided a solution for approximations in the real case (1971). In 1997 Mikhail Lyubich and independently Grzegorz Swiatek and J. Graczyk solved the real case for quadratic polynomials. The general case of real polynomials was solved by Oleg Kozlovski , Weixiao Shen , Sebastian van Strien 2007 ${\ displaystyle C ^ {1}}$

Problem 12

Existence of centralizers of diffeomorphisms : Does a diffeomorphism of a compact manifold have an approximation ( ) by a diffeomorphism that only commutes with its iterates (centralizer)? For proven by Nancy Kopell in her dissertation at Smale. Open even in two dimensions. ${\ displaystyle M}$ ${\ displaystyle C ^ {r}}$ ${\ displaystyle r \ geq 1}$ ${\ displaystyle T \ colon M \ to M}$ ${\ displaystyle n = \ dim (M) = 1}$

In -case 2009 by Christian Bonatti , Sylvain Crovisier and Amie Wilkinson solved. ${\ displaystyle C ^ {1}}$

Problem 13

Is there an upper bound for the number of limit cycles in the planar dynamic system:

{\ displaystyle {\ frac {dx} {dt}} = P (x, y), \ qquad {\ frac {dy} {dt}} = Q (x, y)}

Here are polynomials of maximum degree . What is required is an upper limit for the number of limit cycles with a universal constant . This is a specification of the second part of Hilbert's 16th problem. Along with the Riemann assumption, Smale considered this to be the most elusive of the problems on his list. ${\ displaystyle P, Q}$ ${\ displaystyle d}$ ${\ displaystyle d ^ {q}}$ ${\ displaystyle q}$

Problem 14

Existence of the Lorenz attractor . Proved in 2002 by Warwick Tucker using interval arithmetic .

Problem 15

The question of the existence of smooth solutions (for all positive times) of the Navier-Stokes equation (initial value problem for ) in three dimensions (more precisely in a region of ) and their uniqueness. For two dimensions and three dimensions with sufficiently short times, the answer is yes. Solving the problem would likely be a big step towards mathematically understanding turbulence . This is also one of the Millennium Problems. ${\ displaystyle t = 0}$ ${\ displaystyle \ mathbb {R} ^ {3}}$

Problem 16

The Jacobi conjecture by Ott-Heinrich Keller (1939) (see also the article on Keller). Let be a polynomial map whose Jacobide terminant does not vanish anywhere. Is the mapping then bijective ? A very well known open problem with many attempts at evidence over time. ${\ displaystyle f \ colon \ mathbb {C} ^ {n} \ to \ mathbb {C} ^ {n}}$

Problem 17

Can the zeros of a system of n complex polynomial equations in n unknowns be found by an algorithm that operates on average in polynomial time. This is possible, as Carlos Beltrán and Luis Miguel Pardo proved in 2008. Beltrán and Pardo 's algorithm was a Las Vegas algorithm ; Felipe Cucker and Peter Bürgisser found deterministic versions in 2011 (with running time ) and Pierre Lairez (on average in polynomial time). The problem is therefore considered to be solved. ${\ displaystyle N ^ {O (\ log \ log N)}}$

Problem 18

Limits of Artificial and Human Intelligence. He refers to the considerations of Roger Penrose , which, according to Smale, would first have to develop better mathematical models of intelligence (both for computers and for the brain). For the aspect of solving problems with the computer, the Turing machine model has so far been favored. Lenore Blum , F. Cucker, Michael Shub and Smale (BCCS) came out in favor of a better model for calculating with real numbers. According to Smale, an even narrower limitation is the problem of solving systems of polynomial equations over a body, such as real numbers. According to Smale, this is similar to the separation between digital and analog computers (discrete and continuous problems) and also with the brain and other natural systems (quantum mechanics) he sees more similarities to analog computers and for this reason, like Penrose, is skeptical when arguing the limitations of intelligent systems about Gödel's incompleteness theorem . In this context, according to Smale, models of calculation with real numbers (within the scope of extensions to complexity theory) should also take into account random components and approximations for input and output. In addition to pure problem-solving, interaction with the environment (learning) is an important aspect of intelligence.

Web links

Individual evidence

↑ Smale, Mathematical problems for the next century , Mathematical Intelligencer, 1998, No. 2, pp. 7-15, reprinted in V. Arnold, M. Atiyah, P. Lax, B. Mazur: Mathematics: Frontiers and Perspectives 2000, American Mathematical Society 2000
↑ Shub, Smale, On the intractability of Hilbert's Nullstellsatz and an algebraic version of "NP ≠ P?", Duke Math. J., Volume 81, 2005, pp. 47-54
↑ Wintner, Analytical Foundations of Celestial Mechanics, Princeton UP 1941
↑ Hampton, Moeckel, Finiteness of relative equilibria in the four body problem, Inv. Math., Vol. 163, 2006, pp. 289-312
↑ Albouy, Kaloshin, Finiteness of central configurations of five bodies in the plane, Annals of Mathematics, Volume 176, 2012, pp. 535-588
^ C. Beltrán: The State of the Art in Smale's 7th Problem, Foundations of Computational Mathematics, Budapest 2011, London Math. Society Lecture Note Series 403 (Ed. F. Cucker et al.)
↑ That means with derivatives that are continuous up to order r
^ O. Kozlovski, W. Shen, S. van Strien: Density of hyperbolicity in dimension one, Annals of Mathematics, Volume 166, 2007, pp. 145-182
↑ C. Bonatti, S. Crovisier, A. Wilkinson The C1-generic diffeomorphism has trivial centralizer , Publications Mathématiques de l'IHÉS, 109, 2009, 185–244
^ Tucker, A Rigorous ODE Solver and Smale's 14th Problem, Found. Comput. Math., Vol. 2, 2002, pp. 53-117
^ Jacobi conjecture at Mathworld
↑ Beltran, Pardo, On Smale's 17th Problem: a Probabilistic Positive Solution, Found. Comput. Math., Volume 8, 2008, pp. 1-43
^ Cucker, Bürgisser, On a problem posed by Steve Smale, Annals of Mathematics, Volume 174, 2011, pp. 1785–1836
↑ Lairez, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial time average, Foundations of Computational Mathematics 2016
↑ Blum, Cucker, Shub, Smale, Complexity and real computation, Springer 1997

[1] Smale, Mathematical problems for the next century , Mathematical Intelligencer, 1998, No. 2, pp. 7-15, reprinted in V. Arnold, M. Atiyah, P. Lax, B. Mazur: Mathematics: Frontiers and Perspectives 2000, American Mathematical Society 2000

[2] Shub, Smale, On the intractability of Hilbert's Nullstellsatz and an algebraic version of "NP ≠ P?", Duke Math. J., Volume 81, 2005, pp. 47-54

[3] Wintner, Analytical Foundations of Celestial Mechanics, Princeton UP 1941

[4] Hampton, Moeckel, Finiteness of relative equilibria in the four body problem, Inv. Math., Vol. 163, 2006, pp. 289-312

[5] Albouy, Kaloshin, Finiteness of central configurations of five bodies in the plane, Annals of Mathematics, Volume 176, 2012, pp. 535-588

[6] C. Beltrán: The State of the Art in Smale's 7th Problem, Foundations of Computational Mathematics, Budapest 2011, London Math. Society Lecture Note Series 403 (Ed. F. Cucker et al.)

[7] That means with derivatives that are continuous up to order r

[8] O. Kozlovski, W. Shen, S. van Strien: Density of hyperbolicity in dimension one, Annals of Mathematics, Volume 166, 2007, pp. 145-182

[9] C. Bonatti, S. Crovisier, A. Wilkinson The C1-generic diffeomorphism has trivial centralizer , Publications Mathématiques de l'IHÉS, 109, 2009, 185–244

[10] Tucker, A Rigorous ODE Solver and Smale's 14th Problem, Found. Comput. Math., Vol. 2, 2002, pp. 53-117

[11] Jacobi conjecture at Mathworld

[12] Beltran, Pardo, On Smale's 17th Problem: a Probabilistic Positive Solution, Found. Comput. Math., Volume 8, 2008, pp. 1-43

[13] Cucker, Bürgisser, On a problem posed by Steve Smale, Annals of Mathematics, Volume 174, 2011, pp. 1785–1836

[14] Lairez, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial time average, Foundations of Computational Mathematics 2016

[15] Blum, Cucker, Shub, Smale, Complexity and real computation, Springer 1997