Smale-Probleme

Die Liste der Smale-Probleme wurde von Stephen Smale 1998 im Mathematical Intelligencer^[1] als Antwort auf eine Anfrage von Wladimir Arnold aufgestellt, eine Nachfolgeliste der Liste offener Probleme von David Hilbert von 1900 aufzustellen (hilbertsche Probleme).

Die Liste von Stephen Smale umfasst 18 damals ungelöste Probleme. Entsprechend seiner Arbeitsrichtung sind dabei viele Probleme aus dem Gebiet Dynamischer Systeme und auch solche, die zur Informatik gehören (zum Beispiel Komplexitätstheorie über reellen oder komplexen Zahlen).

Zwei der Probleme tauchen schon in Hilberts Liste auf (Riemannsche Vermutung und der Teil von Hilberts 16. Problem zur Anzahl und Lage von Grenzzyklen nach Henri Poincaré), und Problem 5 von Smale hat Bezüge zu Verallgemeinerungen von Hilberts 10. Problem. Einige sind eher einem Forschungsprogramm vergleichbar, etwa zur Erweiterung der ökonomischen Gleichgewichtstheorie um dynamische Aspekte oder die Frage der Grenzen der Intelligenz. Vier seiner Probleme stimmen mit den Millennium-Problemen überein (Poincaré-Vermutung, P-NP-Problem, Navier-Stokes-Gleichung, Riemannvermutung).

Problem 2, 14 und 17 gelten als gelöst, für andere gibt es Teillösungen. Die Probleme gelten überwiegend als äußerst schwierig.

Riemannsche Vermutung, das bekannteste offene Problem der Mathematik, von zentraler Bedeutung in der Primzahltheorie. Hilberts achtes Problem.

Poincaré-Vermutung. Gelöst von Grigori Perelman nach Vorarbeit von Richard S. Hamilton.

P-NP-Problem, das bekannteste offene Problem der Informatik und von zentraler, auch praktischer Bedeutung.

Das Problem handelt von den ganzzahligen Nullstellen eines ganzzahligen Polynoms in einer Variablen und ob diese durch eine aus der Komplexitätstheorie von Michael Shub und Smale eingeführte ${\displaystyle \tau =\tau (f)}$-Invariante (die vom Polynom f abhängt) beschränkt sind (${\displaystyle \tau }$-Vermutung von Shub und Smale)^[2]. Die ${\displaystyle \tau }$-Invariante ist dabei die minimale Anzahl von Schritten um ${\displaystyle f}$ rekursiv mit elementaren arithmetischen Operationen (Addition, Subtraktion, Multiplikation) beginnend mit der Variablen ${\displaystyle x}$ aufzubauen. Ist die Anzahl verschiedener ganzzahliger Nullstellen von ${\displaystyle f}$ durch ${\displaystyle \tau ^{c}}$ mit einer universellen Konstante ${\displaystyle c}$ beschränkt? Nach Smale und Shub würde eine positive Antwort bedeuten, dass das Entscheidungsproblem für den Hilbertschen Nullstellensatz unlösbar ist und damit ${\displaystyle P\neq NP}$ für Berechnungen über den komplexen Zahlen gilt.

Das Problem betrifft diophantische polynomiale Kurven ${\displaystyle f(x,y)=0}$ (diophantisch heißt über den ganzen Zahlen definiert) in zwei Variablen von maximalem Grad ${\displaystyle d}$. Kann die Existenz einer Lösung in einer Zeit ${\displaystyle 2^{s^{c}}}$ (also exponentieller Zeit) festgestellt werden? Ist die Frage der Existenz einer Lösung in der Klasse NP?

Dabei ist ${\displaystyle c}$ eine universelle Konstante und ${\displaystyle s=s(f)}$ ist ein Maß für die Größe des Polynoms (eine Höhenfunktion, in deren Definition die Koeffizienten des Polynoms eingehen).

Zur Definition der Höhenfunktion ${\displaystyle s(f)}$:

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

mit

${\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 vermutet, dass das Problem sehr schwierig ist, da das verwandte 10. Hilbertsche Problem, also das Entscheidungsproblem der Lösbarkeit diophantischer Gleichungen ohne Einschränkung der Anzahl der Variablen, nach Juri Wladimirowitsch Matijassewitsch unlösbar ist.

Ein anderes Problem aus diesem Umfeld ist, ob es einen Algorithmus gibt zu entscheiden, ob eine polynomiale Gleichung in rationalen Zahlen lösbar ist (für beliebige Anzahl von Variablen). Für ganzzahlige Polynome ist das das 10. Hilbert-Problem.

Das Problem, das von Aurel Wintner 1941 in seinem Lehrbuch der Himmelsmechanik gestellt wurde, fragt nach der Endlichkeit der Anzahl relativer Gleichgewichtspunkte im n-Körper-Problem der Himmelsmechanik für mehr als drei Körper. Relative Gleichgewichtspunkte sind dabei keine Fixpunkte, bewegen sich aber auf einfachen Bahnen (gleichförmige Rotation um ein Zentrum). Im Fall des eingeschränkten Dreikörperproblems gibt es fünf (die Lagrange-Punkte). Die Endlichkeit im Fall N=3 wurde von Wintner gezeigt,^[3] N=4 von M. Hampton und R. Moeckel^[4] und für N=5 wurde die Endlichkeit 2012 von A. Albouy und V. Kaloshin gezeigt^[5]. Für N > 5 ist das Problem offen.

Das Problem handelt von der Verteilung von Punkten auf der 2-Sphäre unter dem Einfluss eines Potentials. Speziell fragte Smale nach einem Algorithmus dafür, N Punkte ${\displaystyle x_{i}}$ auf der Sphäre zu finden, deren Wechselwirkungspotential ${\displaystyle V_{N}(x)=\sum _{1\leq i<j\leq N}\log \left({\frac {1}{r_{ij}}}\right)}$ ist (mit ${\displaystyle r_{ij}=|x_{i}-x_{j}|}$), so dass ${\displaystyle V_{N}(x)-V_{\mathrm {min} }\leq c\log N}$ ist mit einer Konstanten ${\displaystyle c}$ und ${\displaystyle V_{\mathrm {min} }}$ dem Minimum des Potentials bei Variation über alle ${\displaystyle x_{i}}$. Der Algorithmus sollte bezüglich der Haltezeit polynomial von N abhängen. Statt eines logarithmischen Potentials kann auch das Coulombpotential genommen werden (so dass das Problem dem der Anordnung von N Elektronen auf der Sphäre entspricht, Thomson-Problem) oder Potentiale mit anderen Potenzgesetzen. Das Problem entstand nach Smale aus seiner Zusammenarbeit mit Michael Shub (Suche nach einem für einen Homotopiealgorithmus beim Fundamentalsatz der Algebra geeigneten Start-Polynom), es ist aber wie erwähnt Teil eines alten Kreises von Problemen über gleichmäßige Punktverteilungen auf der Sphäre.^[6]

Dies ist auch eine algorithmische Version des Fekete-Problems (Michael Fekete 1923). Die entsprechenden Punkte, die die Energie minimalisieren, heißen auch Fekete-Punkte.

Einführung der Dynamik (Anpassung von Preisen) in der ökonomischen Gleichgewichtstheorie (Arrow-Debreu-Gleichgewichtsmodell). Das Problem entstand aus Smales eigener Beschäftigung mit mathematischer Ökonomie.

Ein Problem der linearen Programmierung: Gibt es einen polynomzeitlichen Algorithmus über den reellen Zahlen für die Feststellung der Lösbarkeit des linearen Systems von Ungleichungen ${\displaystyle Ax\geq b}$ ?

Das Problem ist eine Entscheidbarkeits-Version der Frage nach einem Lösungsalgorithmus des entsprechenden Systems in der linearen Programmierung (wo zusätzlich eine Funktion ${\displaystyle cx}$ maximiert werden soll).

Der Simplex-Algorithmus löst zwar beide Probleme, ist aber im schlechtesten Fall exponentiell langsam (auch wenn er im Mittel polynomial ist nach Karl Heinz Borgwardt). Trotzdem gibt es polynomielle Lösungsalgorithmen für Probleme der linearen Programmierung, dazu zählen z. B. die Ellipsoidmethode oder die Innere-Punkte-Methode.

Das allgemeine Schließungslemma (Closing Lemma) in der Theorie dynamischer Systeme. Für ${\displaystyle C^{1}}$ ist das Pughs Schließungslemma (Charles Pugh, 1967). Gefragt ist nach der Lösung für ${\displaystyle C^{r},r>1}$.

Sei p ein nicht-wandernder Punkt des Diffeomorphismus ${\displaystyle S\colon M\to M}$ einer kompakten Mannigfaltigkeit ${\displaystyle M}$. Kann S beliebig genau ${\displaystyle C^{r}}$-approximiert werden^[7] durch einen Diffeomorphismus ${\displaystyle T\colon M\to M}$, so dass p ein periodischer Punkt von T ist (das heißt Fixpunkt einer Iterierten von T)?

Sind eindimensionale dynamische Systeme im Allgemeinen hyperbolisch?

Dabei ist ein durch einen Diffeomorphismus ${\displaystyle T}$ gegebenes dynamisches System hyperbolisch in einem Punkt ${\displaystyle x}$, wenn die Ableitung ${\displaystyle DT(x)}$ keinen Eigenwert mit Absolutwert gleich ${\displaystyle 1}$ hat. ${\displaystyle \Omega }$ sei der Abschluss der Menge nicht-wandernder Punkte des dynamischen Systems. Ein dynamisches System ist hyperbolisch (erfüllt Axiom A) wenn die periodischen Punkte dicht in ${\displaystyle \Omega }$ liegen und ${\displaystyle \Omega }$ hyperbolisch ist.

Smale formulierte das Problem genauer so: Sei ${\displaystyle T\colon \mathbb {C} \to \mathbb {C} }$ ein komplexes Polynom. Betrachtet wird das durch die Iterationen von Abbildungen mit ${\displaystyle T}$ definierte diskrete dynamische System ${\displaystyle z_{i}=T(z_{i-1})}$ Kann ${\displaystyle T}$ durch ein Polynom gleichen Grades approximiert werden, so dass jeder kritische Punkt gegen einen periodischen Punkt strebt, der eine Senke ist?

Ein periodischer Punkt ${\displaystyle p}$ ist ein Fixpunkt einer Iterierten von ${\displaystyle T}$, ${\displaystyle T^{k}(p)=p}$. Ein kritischer Punkt ist ein Punkt ${\displaystyle w}$ mit ${\displaystyle {\frac {\partial T}{\partial z}}=0}$, eine Senke ist ein Fixpunkt von ${\displaystyle T}$ mit ${\displaystyle \left|{\frac {\partial T}{\partial z}}\right|<1}$.

Das so gestellte Problem ist selbst für Polynome vom Grad 2 ungelöst (hier ist es äquivalent zu der Aussage, dass jede Komponente des Inneren der Mandelbrot-Menge hyperbolisch ist).

Eine äquivalente Formulierung aus der komplexen Dynamik ist: Kann eine polynomiale Abbildung ${\displaystyle T}$ durch eine hyperbolische Abbildung genähert werden?

Nach Smale gab sein Student John Guckenheimer in seiner Dissertation 1970 zwar eine positive Antwort auf das Problem, später stellte sich aber heraus, dass sein Beweis eine Lücke enthielt. Ebenso gab Smales Doktorand Zbigniew Nitecki 1969 eine positive Antwort für den reellen Fall (Abbildung des Einheitsintervalls), der sich auch später als fehlerhaft herausstellte.

M. Jakobson lieferte eine Lösung für ${\displaystyle C^{1}}$-Näherungen im reellen Fall (1971). 1997 löste Mikhail Lyubich und unabhängig Grzegorz Swiatek und J. Graczyk den reellen Fall für quadratische Polynome. Den allgemeinen Fall reeller Polynome lösten Oleg Kozlovski, Weixiao Shen, Sebastian van Strien 2007^[8].

Existenz von Zentralisatoren von Diffeomorphismen: Hat ein Diffeomorphismus einer kompakten Mannigfaltigkeit ${\displaystyle M}$ eine ${\displaystyle C^{r}}$-Näherung (${\displaystyle r\geq 1}$) durch einen Diffeomorphismus ${\displaystyle T\colon M\to M}$, der nur mit seinen Iterierten kommutiert (Zentralisator)? Für ${\displaystyle n=\dim(M)=1}$ von Nancy Kopell in ihrer Dissertation bei Smale bewiesen. Selbst in zwei Dimensionen offen.

Im ${\displaystyle C^{1}}$-Fall 2009 von Christian Bonatti, Sylvain Crovisier und Amie Wilkinson gelöst.^[9]

Gibt es eine obere Schranke für die Anzahl der Grenzzyklen im ebenen dynamischen System:

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

Dabei sind ${\displaystyle P,Q}$ Polynome von maximalem Grad ${\displaystyle d}$. Gefragt ist nach einer oberen Schranke ${\displaystyle d^{q}}$ für die Anzahl der Grenzzyklen mit einer universellen Konstante ${\displaystyle q}$. Dies ist eine Konkretisierung des zweiten Teils von Hilberts 16. Problem. Smale hielt das neben der Riemannvermutung für das am schwersten greifbare (most elusive) der Probleme seiner Liste.

Existenz des Lorenz-Attraktors. Bewiesen 2002 von Warwick Tucker mit Intervallarithmetik.^[10]

Die Frage der Existenz glatter Lösungen (für alle positiven Zeiten) der Navier-Stokes-Gleichung (Anfangswertproblem für ${\displaystyle t=0}$) in drei Dimensionen (genauer in einem Gebiet des ${\displaystyle \mathbb {R} ^{3}}$) und deren Eindeutigkeit. Für zwei Dimensionen und drei Dimensionen bei genügend kurzen Zeiten lautet die Antwort ja. Eine Lösung des Problems wäre wahrscheinlich ein großer Schritt zum mathematischen Verständnis der Turbulenz. Dies ist auch eines der Millennium-Probleme.

Die Jacobi-Vermutung von Ott-Heinrich Keller (1939) (siehe auch den Artikel zu Keller). Sei ${\displaystyle f\colon \mathbb {C} ^{n}\to \mathbb {C} ^{n}}$ eine polynomiale Abbildung, deren Jacobideterminante nirgends verschwindet. Ist die Abbildung dann bijektiv? Ein sehr bekanntes offenes Problem mit vielen Beweisversuchen im Lauf der Zeit.^[11]

Können die Nullstellen eines Systems aus n komplexen polynomialen Gleichungen in n Unbekannten durch einen Algorithmus gefunden werden, der im Mittel in polynomialer Zeit operiert. Dies ist möglich, wie Carlos Beltrán und Luis Miguel Pardo 2008 bewiesen.^[12] Der Algorithmus von Beltrán und Pardo war ein Las-Vegas-Algorithmus, deterministische Versionen fanden Felipe Cucker und Peter Bürgisser 2011^[13] (mit Laufzeit ${\displaystyle N^{O(\log \log N)}}$) und Pierre Lairez (im Mittel in polynomialer Zeit)^[14]. Das Problem gilt somit als gelöst.

Grenzen der künstlichen und menschlichen Intelligenz. Er bezieht sich dabei auf Überlegungen von Roger Penrose, wozu nach Smale aber zunächst bessere mathematische Modelle der Intelligenz (sowohl für Computer als auch für das Gehirn) entwickelt werden müssten. Für den Aspekt des Lösens von Problemen mit dem Computer wurde bisher das Turingmaschinen-Modell favorisiert. Lenore Blum, F. Cucker, Michael Shub und Smale (BCCS) sprachen sich für ein besseres Modell beim Rechnen mit reellen Zahlen aus.^[15] Eine noch engere Eingrenzung ist nach Smale das Problem des Lösens von Systemen polynomialer Gleichungen über einem Körper, etwa den reellen Zahlen. Nach Smale hat das Ähnlichkeit zur Trennung zwischen Digital- und Analogcomputern (diskrete und stetige Probleme) und auch beim Gehirn und anderen natürlichen Systemen (Quantenmechanik) sieht er eher Ähnlichkeiten zu Analogcomputern und ist aus diesem Grund wie Penrose skeptisch bei der Argumentation der Begrenztheit intelligenter Systeme über den Gödelschen Unvollständigkeitssatz. Modelle der Berechnung mit reellen Zahlen (im Rahmen von Erweiterungen der Komplexitätstheorie) sollten in diesem Zusammenhang nach Smale auch zufällige Komponenten berücksichtigen und Näherungen bei In- und Output. Neben reinem Problemlösen ist Wechselwirkung mit der Umgebung (Lernen) ein wichtiger Aspekt der Intelligenz.

• Ungelöste Probleme der Mathematik

• Weisstein, Eric W.: Smale's Problems, MathWorld
• Smale, Mathematical problems for the next century, pdf

1. ↑ Smale, Mathematical problems for the next century, Mathematical Intelligencer, 1998, Nr. 2, S. 7–15, nachgedruckt 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 Nullstellensatz and an algebraic version of "NP≠P ?", Duke Math. J., Band 81, 2005, S. 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., Band 163, 2006, S. 289–312
5. ↑ Albouy, Kaloshin, Finiteness of central configurations of five bodies in the plane, Annals of Mathematics, Band 176, 2012, S. 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 (Hrsg. F. Cucker u. a.)
7. ↑ Das heißt mit Ableitungen, die bis zur Ordnung r stetig sind
8. ↑ O. Kozlovski, W. Shen, S. van Strien: Density of hyperbolicity in dimension one, Annals of Mathematics, Band 166, 2007, S. 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., Band 2, 2002, S. 53–117
11. ↑ Jacobi-Vermutung bei Mathworld
12. ↑ Beltran, Pardo, On Smale's 17th Problem: a Probabilistic Positive Solution, Found. Comput. Math., Band 8, 2008, S. 1–43
13. ↑ Cucker, Bürgisser, On a problem posed by Steve Smale, Annals of Mathematics, Band 174, 2011, S. 1785–1836
14. ↑ Lairez, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Foundations of Computational Mathematics 2016
15. ↑ Blum, Cucker, Shub, Smale, Complexity and real computation, Springer 1997