The Hofstadter consecutive-sum sequence omits infinitely many positive integers

In diesem Artikel beweisen die Autoren, dass die von Hofstadter definierte selbstgenerierende Folge $a_n$ unendlich viele positive ganze Zahlen auslässt, was eine Vermutung im OEIS-Eintrag A005243 bestätigt.

Das Wesentliche

Hier ist eine einfache und bildhafte Erklärung der wissenschaftlichen Arbeit von Quanyu Tang, die sich mit einer besonderen Zahlenfolge befasst.

Das große Rätsel der „versteckten" Zahlen

Stellen Sie sich vor, Sie bauen eine Kette aus Zahlen. Sie beginnen mit den beiden ersten Gliedern: 1 und 2.

Die Regel für den Rest der Kette ist sehr streng und gierig (daher der Name „greedy sequence" oder gierige Folge):
Um die nächste Zahl zu finden, schauen Sie sich alle möglichen Summen an, die Sie aus aufeinanderfolgenden Zahlen der bereits gebauten Kette bilden können.

• Beispiel: Aus 1 und 2 können Sie $1+2=3$ machen.
• Aus 2 und 3 (wenn 3 schon da ist) können Sie $2+3=5$ machen.
• Aus 1, 2, 3 können Sie $1+2+3=6$ machen.

Die Regel besagt: Die nächste Zahl in Ihrer Kette muss die kleinste Zahl sein, die größer als die letzte Zahl ist und die sich als solche Summe bilden lässt.

Wenn Sie das tun, erhalten Sie die Folge:
1, 2, 3, 5, 6, 8, 10, 11, 14, 16, 17, 18, 19, 21, 22, 24, 25, 29, 30, 32...

Aber schauen Sie mal genau hin: Wo sind die 4, die 7, die 9, die 12? Sie tauchen nie auf! Sie sind wie Lücken in einer Mauer, die man nicht füllen kann.

Die große Frage: Gibt es unendlich viele Lücken?

Der berühmte Mathematiker Douglas Hofstadter stellte vor Jahren die Frage: Verschwinden diese Lücken irgendwann, oder gibt es unendlich viele Zahlen, die diese Kette niemals erreicht?

Bislang dachte man, die Kette sei so dicht, dass sie fast alle Zahlen abdeckt. Aber Quanyu Tang hat in diesem Papier bewiesen, dass Hofstadter recht hatte: Es gibt unendlich viele positive ganze Zahlen, die diese Kette niemals erreicht.

Die Beweismethode: Ein mathematisches Detektivspiel

Tang hat das Problem in zwei Teile zerlegt, um es verständlich zu machen:

1. Der qualitative Beweis (Das „Warum")

Stellen Sie sich vor, die Lücken in der Kette wären wie ein Rucksack, der immer schwerer wird.

• Tang definierte eine Hilfszahl $b_n$, die angibt, wie sehr die $n$-te Zahl in der Kette über ihrer Position „schwebt". (Wenn die Kette perfekt wäre und jede Zahl $n$ enthielte, wäre $b_n$ immer 0).
• Er zeigte, dass dieser Rucksack ($b_n$) niemals leer bleibt. Im Gegenteil: Er wird mit jeder neuen Zahl schwerer und schwerer.
• Die Analogie: Stellen Sie sich vor, Sie versuchen, eine Treppe zu bauen, bei der jeder Schritt genau eine Stufe höher ist als der vorherige. Aber die Regel zwingt Sie, manchmal zwei oder drei Stufen auf einmal zu springen. Tang bewies, dass Sie sich mit der Zeit immer weiter von der „perfekten" Treppe entfernen. Da Sie immer weiter springen müssen, bleiben immer mehr Stufen (Zahlen) zwischen Ihren Sprüngen unbetreten.
• Das Ergebnis: Da der Rucksack unendlich schwer wird, gibt es unendlich viele Lücken.

2. Der quantitative Beweis (Das „Wie schnell")

Nicht nur gibt es Lücken, Tang wollte auch wissen: Wie schnell wächst die Kette? Wächst sie langsam wie ein Grasbüschel oder schnell wie ein Raketenstart?

• Hier nutzte er moderne Werkzeuge aus der „Additiven Kombinatorik" (ein Teilgebiet der Mathematik, das sich damit beschäftigt, wie Zahlen sich addieren).
• Er verglich die Summen in der Kette mit einem geometrischen Muster. Er zeigte, dass die möglichen Summen wie Punkte auf einer gekrümmten Linie liegen, die sich nicht so leicht überlappen lassen wie auf einer geraden Linie.
• Das Ergebnis: Die Kette wächst zwar schneller als eine einfache Liste (1, 2, 3, 4...), aber sie wächst nicht explodierend schnell. Tang konnte eine Obergrenze berechnen: Die $n$-te Zahl ist ungefähr proportional zu $n^{1,66}$ (eine etwas komplizierte Zahl, die aber bedeutet: Es ist polynomiales Wachstum, kein Chaos).

Warum ist das wichtig?

1. Es löst ein jahrzehntealtes Rätsel: Seit den 1980er Jahren war unklar, ob diese Folge alle Zahlen irgendwann findet. Tang hat bewiesen: Nein, sie lässt unendlich viele aus.
2. Es zeigt die Kraft der Mathematik: Selbst bei einer sehr einfachen Regel („nimm die kleinste mögliche Summe") entstehen so komplexe Strukturen, dass man tiefgehende mathematische Werkzeuge braucht, um sie zu verstehen.
3. Die Zukunft: Tangs Arbeit ist wie ein Meilenstein. Er hat die Tür geöffnet. Jetzt wissen wir, dass es Lücken gibt. Die nächste Frage ist: Wie genau verteilen sich diese Lücken? Ist die Wachstumsrate noch genauer zu bestimmen?

Zusammenfassung in einem Satz

Quanyu Tang hat bewiesen, dass diese spezielle Zahlenkette, die sich selbst aus ihren eigenen Teilen aufbaut, wie ein Sieb wirkt: Sie fängt viele Zahlen auf, lässt aber unendlich viele durch die Maschen fallen, und er hat zudem berechnet, wie schnell dieses Sieb wächst.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers von Quanyu Tang auf Deutsch:

Titel: Die Hofstadter-Folge der aufeinanderfolgenden Summen überspringt unendlich viele positive ganze Zahlen

1. Problemstellung und Hintergrund

Das Paper untersucht eine spezifische selbstgenerierende, gierige (greedy) Folge von ganzen Zahlen, die als Hofstadter-Folge bekannt ist und im OEIS unter der Eintragnummer A005243 geführt wird.

• Definition: Die Folge $(a_n)_{n \ge 1}$ beginnt mit $a_1 = 1$ und $a_2 = 2$. Für $k \ge 3$ ist $a_k$ die kleinste ganze Zahl, die größer als $a_{k-1}$ ist und sich als Summe von mindestens zwei aufeinanderfolgenden vorherigen Termen der Folge schreiben lässt:
  $$a_k = \sum_{i=p}^{q} a_i \quad \text{für } 1 \le p \le q \le k-1, \quad q-p \ge 1.$$
• Offenes Problem: Die asymptotische Wachstumsrate dieser Folge war eine offene Frage, die von Douglas Hofstadter gestellt wurde. Numerische Berechnungen deuten darauf hin, dass die Folge "die meisten" ganzen Zahlen enthält, aber bereits kleine Lücken (z. B. 4, 7, 9, 12, 13, 15, 20) aufweist.
• Vermutung: Basierend auf den OEIS-Kommentaren wurde die Vermutung (Conjecture 1.2) aufgestellt, dass die Folge unendlich viele positive ganze Zahlen überspringt. Das Ziel des Papers ist der Beweis dieser Vermutung und die Bestimmung einer quantitativen oberen Schranke für das Wachstum.

2. Methodik und Ansatz

Der Beweis gliedert sich in zwei Hauptteile: einen qualitativen Beweis für das Überspringen unendlich vieler Zahlen und einen quantitativen Beweis für eine polynomiale obere Schranke.

A. Qualitativer Beweis (Überspringen unendlich vieler Zahlen)

Der Autor definiert eine verallgemeinerte Folge $(a_n^u)$ für beliebige Startwerte (Seed) $u$ und betrachtet die Differenz $b_n = a_n - n$.

• Monotonie: Es wird gezeigt, dass die Folge $(b_n)$ für $n \ge s$ (wobei $s$ die Länge des Seeds ist) monoton wachsend ist.
• Widerspruchsbeweis: Angenommen, $(b_n)$ wäre beschränkt. Dann müsste die Folge ab einem gewissen Punkt linear verlaufen, d. h., es gäbe ein $B$ mit $a_n = n + B$ für große $n$.
• Diophantische Analyse: Unter der Annahme einer linearen Endphase werden große Potenzen von 2 ($2^r$), die in der Folge auftreten müssen, als Summen aufeinanderfolgender Terme analysiert. Dies führt zu einer Gleichung der Form:
  $$2^r = v^2 + v + E$$
  wobei $E$ aus einer endlichen Menge von Konstanten stammt.
• Schinzel-Tijdeman-Theorem: Hier wird ein Ergebnis von Schinzel und Tijdeman herangezogen, welches besagt, dass die Gleichung $y^k = P(x)$ (mit $P$ als Polynom mit mindestens zwei einfachen Nullstellen) nur endlich viele ganzzahlige Lösungen hat. Da die Annahme einer linearen Folge unendlich viele Lösungen für $k > 2$ implizieren würde, entsteht ein Widerspruch.
• Folgerung: $(b_n)$ ist unbeschränkt, was bedeutet, dass $a_n - n \to \infty$. Da $a_n$ die $n$-te Zahl ist, die in der Folge erscheint, aber $a_n$ viel größer als $n$ ist, müssen unendlich viele Zahlen zwischen den Termen der Folge liegen.

B. Quantitativer Beweis (Obere Schranke)

Für den klassischen Fall (Seed $(1, 2)$) wird eine explizite obere Schranke für $a_n$ hergeleitet.

• Additive Kombinatorik: Der Beweis nutzt die Struktur der Summenmengen. Die Menge der darstellbaren Zahlen $R_m$ (Summen von aufeinanderfolgenden Termen bis zum Index $m$) wird mit der Differenzmenge der Partialsummen $\{s_0, \dots, s_m\}$ in Verbindung gebracht.
• Konvexität: Die Menge der Partialsummen bildet eine konvexe Menge (die Differenzen aufeinanderfolgender Elemente sind streng monoton wachsend).
• Bloom'sche Schranke: Es wird ein neueres Ergebnis von Bloom (2024) über die Größe der Differenzmenge konvexer Mengen verwendet: $|A - A| \ge c |A|^{6681/4175 - \eta}$.
• Rekursion: Durch die Kombination der unteren Schranke für die Anzahl der darstellbaren Zahlen und der gierigen Konstruktion der Folge wird eine rekursive Ungleichung für $a_n$ abgeleitet.
• Iteration: Durch Iteration dieser Rekursion wird eine polynomiale obere Schranke für $a_n$ gewonnen.

3. Hauptergebnisse

1. Theorem 1.4 (Qualitativ): Für jede endliche Startsequenz aus positiven ganzen Zahlen ist die Folge $b_n = a_n - n$ für alle $n \ge s$ monoton wachsend und unbeschränkt.
2. Korollar 1.5: Die Folge $(a_n)$ erfüllt $a_n = n + \omega(1)$. Das bedeutet, dass die Folge unendlich viele positive ganze Zahlen überspringt. Dies bestätigt die Vermutung 1.2 aus dem OEIS.
3. Theorem 1.6 (Quantitativ): Für die klassische Folge gilt für jedes $\varepsilon > 0$ eine obere Schranke:
   $$a_n \ll_\varepsilon n^{4175/2506 + \varepsilon}$$
   Der Exponent $4175/2506 \approx 1.666$. Dies ist der erste polynomiale Beweis für das Wachstum dieser Folge.

4. Bedeutung und Diskussion

• Lösung eines offenen Problems: Das Paper löst ein langjähriges Problem der kombinatorischen Zahlentheorie, das von Hofstadter und Erdős-Problem-Enthusiasten gestellt wurde.
• Verallgemeinerung: Die Ergebnisse gelten nicht nur für den klassischen Seed $(1, 2)$, sondern für beliebige endliche Startwerte.
• Verbindung zur Additiven Kombinatorik: Der Beweis verbindet die Theorie selbstgenerierender Folgen mit modernen Ergebnissen über Differenzmengen konvexer Mengen (Bloom's Theorem).
• Lücke in der Schätzung: Es besteht eine erhebliche Lücke zwischen der unteren Schranke ($a_n \ge n + \omega(1)$) und der oberen Schranke ($a_n \ll n^{1.666}$).
  • Numerische Experimente (bis $n=30.000$) deuten darauf hin, dass das Wachstum viel linearer ist, möglicherweise mit $a_n \approx n + n^\alpha$, wobei $1/5 < \alpha < 1/2$(vermutlich nahe$1/3$).
  • Der Autor merkt an, dass selbst unter der Annahme einer starken Vermutung (nahezu quadratische Größe der Differenzmenge konvexer Mengen) die aktuelle Iterationsmethode nicht ausreicht, um eine lineare Schranke ($a_n \ll n$) zu beweisen.

Fazit

Quanyu Tang beweist rigoros, dass die Hofstadter-Folge der aufeinanderfolgenden Summen Lücken aufweist und unendlich viele ganze Zahlen überspringt. Zudem liefert er den ersten polynomiellen oberen Beweis für das Wachstum der Folge, wobei die genaue asymptotische Rate weiterhin ein offenes und faszinierendes Problem bleibt.