Seit einigen Tagen liegt ein vorgeblicher Beweis der Collatz-Vermutung auf dem ArXiv, gestern schaffte es ein Artikel über den Beweisversuch sogar in die Top-Meldungen von Spiegel Online.

i-fc2bf85945cd0d55dd8535dc181b4705-collatz_conjecture.png

xkcd

Bei der Collatz-Vermutung (auch als ‘3n+1’-Vermutung bekannt) geht es um folgende Prozedur:
– man beginnt mit einer natürlichen Zahl n
– wenn sie gerade ist, dividiert man sie durch 2
– wenn sie ungerade ist, bildet man 3n+1.
Die Vermutung ist, daß man mit dieser Prozedur letztlich immer im Zykel 4,2,1 endet.

Als Beispiel, mit Startwert 37:
37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

In der Arbeit An analytical approach to the Collatz 3n+1 Problem (bei Mathematics of Computation eingereicht und seit einigen Tagen auf dem ArXiv) wird nun ein Beweis dieser Vermutung behauptet.

Ich habe die Arbeit kurz überflogen und habe auch kurz gegoogelt, was man im Netz dazu findet.

In der Arbeit wird etwas irreführend der Eindruck erweckt, daß man die Collatz-Vermutung auf ein funktionentheoretisches Problem zurückgeführt und dieses gelöst habe. Tatsächlich haben Berg und Meinardus in zwei 1994 und 1995 veröffentlichten Arbeiten zwei lineare Operatoren U,V:H–>H eingeführt (hier ist H der Vektorraum der holomorphen Funktionen auf der Einheitskreisscheibe), haben gezeigt, daß Δ2 ⊆ ker(U)∩ker(V) (hier ist Δ2H der Unterraum aus allen Linearkombinationen von φ1(z)=1 und φ2=z/(1-z)) und haben gezeigt, daß die Gleichheit Δ2 = ker(U)∩ker(V) dann und nur dann gilt, wenn die Collatz-Vermutung richtig ist.

Diese auf Berg-Meinardus zurückgehende Äquivalenz der Collatz-Vermutung zu einem funktionentheoretischen Problem wird in der neuen Arbeit zwar ausführlich besprochen, geht aber offenbar (auch wenn in der Arbeit der gegenteilige Eindruck erweckt wird) in den eigentlichen Beweisversuch gar nicht ein. Tatsächlich handelt es sich bei dem versuchten Beweis ganz klassisch um eine Analyse des Baumes, den man erhält, wenn man startend von 1 (oder von 4) die möglichen vorhergehenden Zahlenwerte rückwärts verfolgt (wie im unten abgebildeten Baum aus der Wikipedia).
Auf Seite 12 folgt dann der Hauptsatz:

Theorem 4.17. Regardlass [sic] of the start value 2l > 8, the annihilation algorithm will always end with 2l = 8.
Proof. This follows from the properties of the annihilation graph. Every start value 2l > 8 defines a vertex of the graph and because of the tree structure it always ends at 2l = 8.

Das ist, so wie es dort steht, natürlich eine Trivialität: von jedem Punkt des Baumes kommt man bei Anwendung des Algorithmus letzlich zum Zykel 4,2,1 – der Baum war ja gerade so definiert, daß er aus denjenigen Zahlen besteht, die man bei Rückwärtsanwendung des Algorithmus aus 1,2,4 bekommt.
Interessanter wäre die Frage, warum der Baum alle natürlichen Zahlen enthält. Und diese Frage wird in der Arbeit allem Anschein nach nicht beantwortet.

i-08cddf457e31d946100ad16dd4848caa-2000px-Collatz-graph-all-30-no27.svg.png

Wikipedia

Kommentare (20)

  1. #1 Engywuck
    7. Juni 2011

    ist das nun ein “Beweis durch falsche Annahme” oder ein “Beweis durch Verwirrung”? (http://kamelopedia.mormo.org/index.php/Beweis) 😉

    Schade, wäre schön gewesen, so etwas vermeintlich einfaches gelöst zu sehen. Aber Fermats Vermutung hat ja auch ein paar Jahrhunderte durchgehalten… (gibt’s dazu inzwischen eine “laientaugliche” Version des Beweises? Also ohne sich in alle modernen Teilgebiete der Mathematik je 5 Jahre einlernen zu müssen?)

  2. #2 adenosine
    7. Juni 2011

    Hat denn so eine Vermutung irgendeine Relevanz , einen Bezug zu realen Problemen?

  3. #3 Ex-Esoteriker
    7. Juni 2011

    Hallo Leute,

    also ich als Laie kann nur eins sagen: So muss Mathematik sein, faszinierend aber auch gerade leicht verständlich für Nichtmathematiker 🙂

    Besonders schön finde ich am Baumdiagramm folgende Zahlenwiederholungen:

    1, 2, 4

    dann:

    10, 20, 40

    dannach:

    11, 22, 44

    Weis jemand, wie es weiter geht? Bzw. ob es ein größeres Baumdiagramm gibt?

  4. #4 cero
    7. Juni 2011

    Ich habe jetzt leider keine Zeit mir den Artikel durchzulesen, aber irgendwie kann ich mir nicht vorstellen, dass ein Mathematikprofessor wirklich so einen dämlichen Fehler begeht und das dann nicht mal bemerkt bevor er es veröffentlicht.

    Mit dieser Denkweise schafft man es doch nicht mal durch die Mathematik-Klausuren im Studium. oO

  5. #5 Thilo
    7. Juni 2011

    @ adenosine: Die Collatz-Vermutung ist sicher kein zentrales Problem der mathematischen Forschung, sondern eher wegen ihrer scheinbaren Einfachheit populär. Aber irgendwie hängt in der Mathematik alles mit allem zusammen und aus den Arbeiten von Berg-Meinardus folgt ja eben, daß man mit dem Beweis der Collatz-Vermutung dann auch alle Lösungen eines bestimmten Differentialgleichungssystems kennen würde, was bestimmt wieder irgendwo anders Anwendungen besitzt …
    @ cero: Das sollte man eigentlich meinen.

  6. #6 Sim
    7. Juni 2011

    Ich hab bis vor kurzem noch gar nichts von dieser Collatz-Vermutung gehört. Aber die Vermutung scheint tatsächlich sehr einfach zu verstehen zu sein.

    Wenn ich das also richtig verstanden habe, dann müsste es ja wenn die Vermutung nicht gilt, eine natürliche Zahl geben, die, nach den gegebenen Regeln, eine Folge produziert die nicht die 1 enthällt. Wenn die Folge nur endlich viele verschiedene Glieder hat, dann müsste das ein Zyklus im Graphen sein, wenn es unendlich viele verschiedene Glieder wären würde sie über alle Grenzen hinauswachsen. Wenn man also zeigen kann, dass beides niemals der Fall sein kann, dann wäre die Vermutung bewiesen. Aber mindestens eine der beiden Alternativen wird wohl nicht so leicht zu zeigen sein.

  7. #7 Georg Hoffmann
    7. Juni 2011

    Thilo
    Im Spiegel Artikel stand, dass ein Experte der Collatz Vermutung auch schon ganz angetan war. Tja, wat nu?

  8. #8 Thilo
    7. Juni 2011

    Der vom Spiegel zitierte (inzwischen übrigens über 80-jährige) Professor ist einer der beiden Autoren der funktionentheoretischen Arbeiten von 1994-95, die auf den ersten 4 Seiten des Artikels ausführlich referiert werden. Vermutlich hat er gefunden, daß die dort aus seinen Arbeiten zitierten Tatsachen alle korrekt sind – das bezweifelt ja auch niemand. Möglicherweise sind auch alle weiteren Rechnungen, die im Artikel danach noch kommen, korrekt. Es ist nur eben so, daß der oben kopierte Satz 4.17. erstens trivial ist (man also die ganzen Berechnungen vorher nicht benötigt hätte) und zweitens nicht die Collatz-Vermutung impliziert.

  9. #9 Jonathan
    7. Juni 2011

    Ich habe mir doch direkt gedacht, dass man einem SpOn-Artikel über ein wissenschaftliches Thema nicht einfach so glauben schenken kann 😉
    Ich finds allerdings auch schade, dass in dem Artikel nicht einmal versucht wird die Problemlösung zu erklären oder wenigstens eine Vereinfachung.

  10. #10 Maximilian Schirm
    11. Juni 2011

    Sollte ich mich irren bitte ich darum, mich zu korrigieren, aber ist es nicht so, dass eine ungerade Zahl * 2 immer eine gerade Zahl sein muss, und wenn man zu einer geraden Zahl dann irgendeine ungerade Zahl addiert, dann wird die Zahl wieder ungerade.
    Wenn man jetzt zu dieser ungeraden Zahl wieder 1 hinzufügt, dann wird die Zahl wieder gerade.
    Teilt man egal welche gerade Zahl nach dem Prinzip, dass das Ergebnis (im Falle, dass es ungerade ist (also nur wenn man bei 6 ankommt) mit 3n + 1 gerade gemacht wird, so kommt man zwangsläufig wieder auf die zahlen 4, 2, 1 !
    Ich verstehe gar nicht, was hierbei so weltbewegend ist, aber ich wollte nur mal meine Meinung dazu äußern 😉

  11. #11 Thilo
    11. Juni 2011

    @ Maxmilian Schirm: Wenn man eine ungerade Zahl n hat und 3n+1 berechnet, bekommt man zwar eine gerade Zahl, es könnte aber sein, daß man dann beim Dividieren durch 2 (im nächsten oder auch einem späteren Schritt) nicht bei 4, sondern bei einer ungeraden Zahl landet.
    Im Beispiel aus dem Artikel mit n=37, bekommt man 3n+1=112, und beim Dividieren durch 2 landet man dann über 56,28,14 bei 7, also zunächst nicht bei 4,2,1. (Später dann schon.)

  12. #12 Maximilian Schirm
    12. Juni 2011

    Ja eben 🙂

  13. #13 Thilo
    15. Juni 2011
  14. #14 Ulfi
    15. Juni 2011

    @Maximilian so einfach ist es eben nicht. Da du ungerade Zahlen mit 3n+1 verarbeitest, werdne sie zwar gerade, aber (3n+1)/2 kann ja wieder ungerade sein. und wnen du das Ergebnis dann wieder mit 3 muliplizierst und 1 addierst, wirst du größer als dein Startwert.
    Es könnte also schon möglich sein, dass für einen bestimmten Startwert die Zahl immer weiter wächst.

  15. #15 CHP
    15. Juni 2011

    Ich habe damit mal ein wenig “numerisch” herumgespielt. Dabei habe ich 3n+1 durch 3n+x ersetzt, wobei x ungerade ist. Das ganze habe ich für x von 1 bis 25 und n von 1 bis 1000000 berechnet:

    x: Anzahl_Schleifen[Schl.Längen] Max:n_der_zuletzt_gefundene_Schleife
     1: 1[3]
     3: 1[3]
     5: 6[4,8,3,8,44,44] Max:171
     7: 2[6,3] Max:7
     9: 1[3]
    11: 3[8,22,3] Max:11
    13:10[5,3,39,13,13,13,13,13,13,13] Max:319
    15: 6[8,4,3,8,44,44] Max:337
    17: 3[9,49,3] Max:17
    19: 2[16,3] Max:19
    21: 2[6,3] Max:7
    23: 4[69,7,7,2] Max:23
    25: 8[24,12,4,8,3,8,44,44] Max:855
    

    Auffällig ist zumindest, daß bei höheren n keine neuen Schleifen mehr hinzukommen. Daß die Wahrscheinlichkeit für weitere Schleifen bei höheren n abnimmt ist leider kein Beweis.

    Interessant ist auch die Verteilung der n auf die Schleifen:
    13: 476.858 76.923 252.152 33.401 38.848 19.107 43.010 19.709 25.406 14.585
    25: 423.991 376.009 28.286 99.078 39.999 18.673 6.457 7.506

  16. #17 shoe lifts men
    http://www.deelsonheels.com
    2. April 2013

    Good breakdown, you assisted me in understanding this topic a lot easier. Thank you plenty for the fantastic write up.

  17. #18 Herbert Helling
    Warburg
    11. Januar 2015

    Collatz-Problem Analyse Algorithmus Lösung

    Collatz06012015.wordpress.de
    http://www.herbert-helling.de/Collatz

  18. #19 Slash
    14. Januar 2015

    Hallo Herbert,
    ich habe mir deinen Beweisversuch angeschaut. Leider muss ich dir mitteilen, dass er falsch ist. Näheres auf Matroids Matheplanet unter folgendem Link:

    http://www.matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=203240

    Gruß, Slash