Ich bin vom Collatz-Problem fasziniert , seit ich zum ersten Mal in der High School davon gehört habe.
Nehmen Sie eine beliebige natürliche Zahl . Wenn gerade ist, teilen Sie es durch zu bekommen , Wenn ist ungerade multiplizieren Sie es mit und hinzufügen erhalten . Wiederholen Sie den Vorgang unbegrenzt. Die Vermutung ist, dass Sie, egal mit welcher Zahl Sie beginnen, irgendwann immer erreichen werden . [...]
Paul Erdős sagte über die Collatz-Vermutung: „Die Mathematik ist für solche Probleme noch nicht bereit.“ Er bot $500 USD für seine Lösung an.
FRAGEN :
Für wie wichtig halten Sie die Antwort auf diese Frage? Warum?
Würden Sie darüber spekulieren, was Paul Erdős dazu bewogen haben könnte, ein solches Angebot zu machen?
EDIT: Gibt es einen Grund zu der Annahme, dass ein Beweis der Collatz-Vermutung eher komplex (wie die FLT) als einfach wäre (wie PRIMES in P)? Und kann diese Charakterisierung von FLT vs. PRIMES in P spezifischer gemacht werden als ein Vergleich der Bitlänge?
Die meisten Antworten gingen bisher eher in die Richtung „Warum schwierige Probleme wichtig sind“ als „Warum die Collatz-Vermutung wichtig ist“; Letzteres werde ich versuchen anzusprechen.
Ich denke, die grundlegende Frage, die angesprochen wird, lautet:
Auf welche Weise funktioniert die Primfaktorzerlegung von beeinflussen die Primfaktorzerlegung von ?
Natürlich kann man die Primfaktorzerlegung immer ausmultiplizieren, eins addieren und dann wieder faktorisieren, aber das wirft die Information der Primfaktorzerlegung weg . Beachten Sie, dass diese Frage auch in anderen UFDs sinnvoll ist, z .
Es scheint sehr schwierig zu sein, auf diese Frage Antworten zu finden, die nicht unter die Überschrift „unmittelbar“ fallen, wie etwa unterschiedliche Primzahlen in jeder Faktorisierung. Dies scheint teilweise an einer kleinen Änderung der Primfaktorzerlegung zu liegen (Multiplikation mit einer Primzahl, sagen wir) kann eine große Veränderung in der Primfaktorzerlegung haben (völlig unterschiedliche primäre Unterstützung vielleicht). Daher ist es verlockend, das Hinzufügen von 1 als im Wesentlichen zufälliges Mischen der Primfaktorzerlegung zu betrachten.
Das Auffälligste an der Collatz-Vermutung ist, dass sie eine tiefgreifende Aussage über eine subtile Beziehung zwischen den Primfaktorzerlegungen von zu machen scheint Und . Beachten Sie, dass die Collatz-Iteration aus drei Schritten besteht; zwei davon sind "klein" in Bezug auf die Primfaktorzerlegung, und die andere fügt eine hinzu:
Die Collatz-Vermutung scheint also zu besagen, dass es eine Art abstrakte Größe wie „Energie“ gibt, die nicht beliebig erhöht werden kann, indem man 1 addiert 1 nimmt Sie, schließlich nimmt der Akt des Herausziehens von 2s genug Energie aus dem System, um 1 zu erreichen. Ich denke, aus Gründen wie diesen vermuten Mathematiker, dass eine Lösung der Collatz-Vermutung neue Horizonte eröffnen und neue entwickeln wird Wichtige Techniken der Zahlentheorie.
Die Collatz-Vermutung ist das einfachste offene Problem der Mathematik. Sie können es all Ihren nicht-mathematischen Freunden und sogar kleinen Kindern erklären, die gerade gelernt haben, durch 2 zu teilen. Es erfordert kein Verständnis der Teilbarkeit, sondern nur der Gleichmäßigkeit.
Der Mangel an Verbindungen zwischen dieser Vermutung und bestehenden mathematischen Theorien (wie in einigen anderen Antworten beklagt) ist keine Unzulänglichkeit dieser Vermutung, sondern unserer Theorien.
Dieses Problem hat direkt zu theoretischen Arbeiten von Conway geführt, die zeigen, dass sehr ähnliche Fragen formal unentscheidbar sind , sicherlich ein überraschendes Ergebnis.
Das Problem bezieht sich auch direkt auf chaotische zelluläre Automaten. Wenn Sie sich eine Zahl zur Basis 6 ansehen, werden Sie sehen, dass die Multiplikation mit 3 und die Division durch 2 dieselbe Operation sind (die sich nur um den Faktor 6 unterscheidet, dh die Position des Dezimalpunkts), und die Operation lokal ist: jede neue Ziffer hängt nur von zwei der Ziffern des vorherigen Schritts ab. Unter Verwendung eines 7. Zustands für Zellen, die nicht Teil der Zahl sind, wird ein sehr einfacher zellularer Automat erhalten, bei dem jede Zelle nur einen Nachbarn betrachten muss, um ihren nächsten Wert zu berechnen.(Wolfram Mathworld hat einen Unsinn darüber, dass eine CA-Implementierung aufgrund von Überträgen schwierig sei, aber es gibt keine Überträge, wenn Sie 1 addieren, da die letzte Ziffer nach der Multiplikation mit 3 entweder 0 ist (wird zu einer Nichtziffer, weil die Zahl gerade war, also sollten wir geteilt durch 6) oder 3 (wird 4), also gibt es nie Überträge.)
Dass diese CA chaotisch ist, lässt sich leicht nachweisen: Ändert man die inneren Ziffern in irgendeiner Weise, wächst der Bereich der betroffenen Ziffern immer linear mit der Zeit (um Ziffern pro Schritt). Dies verhindert jegliche Manipulation der Ziffernmuster, die schnell randomisiert werden. Wenn sich die letzte Ziffer zufällig verhält, ist die Vermutung wahr. Offensichtlich hätte jeder Fortschritt bei der Collatz-Vermutung unmittelbar Konsequenzen für die symbolische Dynamik .
Die Tag-Systeme von Emil Post (die er 1920 speziell für das Studium der Grundlagen der Mathematik geschaffen hat) werden seit vielen Jahrzehnten untersucht und bilden seit 1961 die Grundlage der kleinsten universellen Turing-Maschinen (sowie anderer universeller Systeme). 2007 entdeckte Liesbeth De Mol, dass das Collatz-Problem als folgendes Tag-System kodiert werden kann:
In zwei Durchgängen verarbeitet dieses Tag-System das Wort in entweder oder abhängig von der Parität von . Größere Tag-Systeme sind als universell bekannt, und jeder Fortschritt beim 3x+1-Problem wird von diesem Gebiet mit großer Aufmerksamkeit verfolgt.
Kurz gesagt, das Collatz-Problem ist so einfach, dass es jeder verstehen kann, und bezieht sich dennoch nicht nur auf die Zahlentheorie (wie in anderen Antworten beschrieben), sondern auch auf Fragen der Entscheidbarkeit, des Chaos und der Grundlagen der Mathematik und der Berechnung. Das ist ungefähr das Beste für ein Problem, das selbst ein kleines Kind verstehen kann.
So viele Mathematiker und berühmte unter ihnen haben verschiedene Wege versucht, dieses Problem anzugehen, und es ist immer noch so schwer fassbar wie zu Beginn. Die Bedeutung des Problems liegt also darin, dass wirklich neue mathematische Ideen entwickelt werden müssen, um es zu lösen, und solche Ideen können in anderen Bereichen hilfreich sein, in denen es um „wirklich wichtige“ Probleme geht. Beachten Sie, dass Erdős selbst etwas in der Art gesagt hat, dass "wir noch nicht die Mathematik haben, um dieses Problem zu lösen".
Ich glaube nicht, dass dies ein konzeptionell wichtiges Problem ist. Es ist ein Beispiel für ein bodenständiges Problem, das bis zu einem großen Wert numerisch überprüft werden kann und sich seit vielen Jahren einer Lösung widersetzt. Nicht alle derartigen Probleme sind automatisch wichtig (z. B. Nichtvorhandensein ungerader vollkommener Zahlen).
Eine Analogie zur Bedeutung des letzten Satzes von Fermat ist angebracht. Bevor die Verbindung zwischen FLT und tiefen Vermutungen über elliptische Kurven hergestellt wurde, hatte es keine übergeordnete Bedeutung zu wissen, ob FLT wahr ist oder nicht. (Die Verbindung zwischen FLT und der abc-Vermutung wurde ungefähr zur gleichen Zeit hergestellt.) Ja, die Arbeit an FLT war verantwortlich für nützliche Entwicklungen in der algebraischen Zahlentheorie, aber trotzdem war es lange Zeit nicht klar, das Problem zu lösen , oder vielmehr das Finden eines Gegenbeispiels, andere Auswirkungen hätte. Zum Beispiel schrieb Gauß 1816 an seinen Freund Olbers (ein Astronom), dass er kein Interesse an FLT als isoliertem Vorschlag habe.
Wenn morgen jemand zeigen würde, dass die Collatz-Vermutung eine Folge der abc-Vermutung oder eines anderen erkennbar wichtigen ungelösten Problems war, dann würde ich meine Meinung über ihre Bedeutung ändern (weil, wie bei der Verbindung zwischen der Modularitätsvermutung und FLT, ein Gegenbeispiel zu Collatz hätte dann anderswo in der Mathematik echte Implikationen). Aber solange es isoliert bleibt und keine Auswirkungen auf andere Probleme hat, denke ich nicht, dass es eine mathematisch tiefgreifende Frage ist. Dasselbe gilt für ungerade perfekte Zahlen: Wenn nicht jemand zeigt, dass die Existenz einer ungeraden perfekten Zahl anderswo Auswirkungen hat, die wir nicht erwarten (wie ein Gegenbeispiel zu FLT mit einer sehr unerwarteten Implikation für elliptische Kurven), glaube ich nicht, dass der Mainstream dies tun würde halten auch ungerade vollkommene Zahlen für wichtig.
Auf pädagogischer Seite gebe ich aber durchaus zu, dass dies eine schöne Aufgabe ist, um Schülern, die mit fortgeschrittener Mathematik nicht vertraut sind, zu zeigen, dass es wirklich ungelöste mathematische Probleme gibt. Die Leute wissen das nicht unbedingt, sie denken vielleicht, dass alles durch Computer oder so gelöst werden kann.
Ich glaube die Das Problem wird als Testfall für die ergodische Theorie angesehen, dh als Beweis dafür, dass bestimmte Wahrscheinlichkeitserwartungen für Umlaufbahnen eines bestimmten Systems wahr sind. Es gibt Artikel von Sinai, Lagarias und anderen, die probabilistische Modelle geben, ähnlich den asymptotischen Vorhersagen, die bei Fragen zur Verteilung von Primzahlen gemacht werden, wo die Vorhersagen zuverlässig sind, sie aber in jedem einzelnen Fall beweisen (Primzahlzwillinge, , Goldbach, ...) ist ein jahrhundertealtes offenes Problem.
Dies ist analog zu Transzendenz- oder Irrationalitätsbeweisen bestimmter Zahlen: Der Beweis, dass das, was „mit Wahrscheinlichkeit 1 wahr ist“, in einem bestimmten Fall wirklich gilt, ist äußerst schwierig und treibt die Theorie voran. Ansonsten gibt es außerhalb keine Probleme Vermutungen, die dieselbe Iteration verwenden, es handelt sich also um eine Senke und nicht um eine Quelle im Diagramm der Anwendungen der Theorie.
Ich kann der Frage: " Was ist die Bedeutung? " nichts hinzufügen, aber es gibt noch einen weiteren Aspekt, der noch nicht erwähnt wurde. Dies ist das Verhältnis von Potenzen von 3 und Potenzen von 2. Ein Teilproblem der Frage der Zyklen im Collatz führt zu einer kritischen Ungleichung, bei der die Möglichkeit solcher Zyklen vom relativen Abstand von perfekten 2er-Potenzen zu perfekten 3er-Potenzen abhängt. Dies kann auch als Annäherung von log(3)/log(2) an rationale Zahlen ausgedrückt werden. Kurt Mahler hatte dies im Hinblick auf seinen Begriff der z-Zahlen untersucht (aber nur teilweise erfolgreich); aber es hängt auch mit einem ungelösten Detail im Waring-Problem zusammen , wo die rationale Annäherung von Potenzen von 3/2 an ganze Zahlen im Mittelpunkt einer Vermutung steht.
Hmm, ich weiß nicht, ob es sinnvoll ist, hier weiter ins Detail zu gehen, ich denke eher: nein; die Idee der kritischen Ungleichheit wurde von Ray Steiner und später von John Simons und Benne de Weger berücksichtigt; Zu letzterem habe ich im Wikipedia-Artikel zum Collatz-Problem verlinkt. Eine Diskussion von mir zum Approximationsproblem ist hier (sollte aber evtl. mit mehr Kontext angereichert werden) .
Paul Erdős bot Geldpreise für die Lösung von Problemen nach seiner Einschätzung ihrer Schwierigkeit und Wichtigkeit an. Ich glaube, seine Einschätzung der Schwierigkeit dieses Problems hat sich dadurch als richtig erwiesen, dass es offen bleibt.
Ich denke, dieses Problem ist insofern sehr wichtig, als ein großer Teil der Leute, die diese Antwort lesen, sich irgendwann damit beschäftigt haben werden. Daher wäre seine Lösung für viele von Interesse.
Ein weiterer Grund für seine Bedeutung ist, dass er, wie der letzte Satz von Fermat (Satz von Wiles), leicht zu formulieren und zu verstehen ist und daher das Potenzial hat, junge Menschen für die Mathematik zu begeistern. Auch ich lernte es in der High School kennen und konnte seiner Anziehungskraft nicht widerstehen.
Abgesehen von den mathematischen Antworten, die von anderen bereitgestellt werden, ist die rechnerische Überprüfung des Collatz-Problems eine gute Übung für Programmierer . Es gibt viele Optimierungsmöglichkeiten (z. B. Zeit-Raum-Kompromiss unter Verwendung von Nachschlagetabellen, Parallelität), viele Fallstricke (z. B. Überlauf von Integer-Typen), Möglichkeiten, verschiedene Implementierungstricks auszunutzen (z. B. Anweisungen zum Zählen von nachgestellten Nullen, die in moderner Hardware verfügbar sind), usw. Es ist eine einfache Aufgabe, bei der Sie viele grundlegende Programmierkonstruktionen üben können (Verzweigung des Programms, do-while-Schleifen, Rekursion). Und aus diesen Gründen ist dies wohl die häufigste Aufgabe, die Sie in vielen Online- oder Universitätskursen finden (z. B. im CS50-Kurs der Harvard University).
Ich werde auf diese Frage antworten:
Frage : Für wie wichtig halten Sie die Antwort auf diese Frage? Warum?
Siehe die unten angegebene Begründung des Mathematikers Terence Tao hier:
Sehen Sie sich das YouTube-Video von Terence Tao über Collatz Conjecture an, in dem Sie verstehen, dass es mehr Anwendungsmöglichkeiten gibt.
BEARBEITEN :
Sehen Sie sich auch dieses PDF an , das alle Dinge enthält, die von Professor Terence Tao in diesem Video besprochen wurden.
Qiaochu Yuan
Qiaochu Yuan
Dan Brumleve
Michael Lugo
mmyers
Gerry Myerson