In diesem Blog-Beitrag gebe ich einen kurzen, möglichst für alle verständlichen Einblick in meine Masterarbeit mit dem Titel „Asymptotic Analysis of $q$-Recursive Sequences: General Study and Selected Combinatorial Sequences“, was übersetzt soviel wie „Asymptotische Analyse von $q$-rekursiven Folgen: Allgemeine Untersuchungen und ausgewählte kombinatorische Folgen“ heißt. Die Masterarbeit wurde 2019 unter der Betreuung von Daniel Krenn fertiggestellt.

Spezielle Folgen von Zahlen

Bestimmt habt ihr schon mal die Aufgabe bekommen, eine Folge von Zahlen wie beispielsweise \begin{equation} 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,\ldots \end{equation} logisch fortzusetzen. Der Schlüssel zum Erfolg hierbei liegt darin, die Vorschrift zu entdecken, nach der die ersten Elemente der Folge gebildet wurden. Ist das geschafft, dann ist es leicht, die Folge beliebig zu erweitern. (Einen Vorschlag, wie man die gegebene Folge logisch fortsetzen könnte, gibt es unten. Nur für den Fall… )

Diese Masterarbeit beschäftigt sich mit Folgen von Zahlen, die einer ganz spezifischen, rekursiven Art von Bildungsvorschrift genügen: sogenannte $q$-rekursive Folgen. Rekursiv bedeutet in diesem Zusammenhang, dass man ein Element der Folge sehr leicht bestimmen kann, wenn man alle vorigen Elemente kennt. Vereinfacht gesagt ist eine $q$-rekursive Folge eine Folge, bei der jede Teilfolge mit Indizes modulo $q^{M}$ eine Linearkombination von Teilfolgen mit Indizes modulo $q^{m}$ für ganze Zahlen $q \geq 2$ und $0 \leq m < M$ ist. Es stellt sich heraus, dass diese Eigenschaft viele „natürlich auftretende“ Folgen in der Kombinatorik und der Theoretischen Informatik erfüllen und es deshalb lohnenswert ist, $q$-rekursive Folgen im Detail zu untersuchen. Dies wird in dieser Arbeit erstmals gemacht.

Hilfreich dafür ist das Konzept von sogenannten $q$-regulären Folgen, das von Allouche und Shallit in den 90er-Jahren erstmals eingeführt wurde und sich mittlerweile als zentrales Konzept in verschiedenen Bereichen der Mathematik und der Theoretischen Informatik etabliert hat. Diese $q$-regulären Folgen sind eine Verallgemeinerung von Folgen, die von endlichen deterministischen Automaten erzeugt sind. Charakteristisch für diese Klasse von Folgen ist, dass die Bildungsvorschrift für das $n$te Element der Folge grundlegend von der Zifferndarstellung der Zahl $n$ zur Basis $q$ abhängt.

Resultate

Die Masterarbeit beinhaltet die folgenden Hauptresultate:

• Es wird bewiesen, dass jede $q$-rekursive Folge auch $q$-regulär ist. Damit ist gezeigt, dass alle existierenden Resultate für $q$-reguläre Folgen ebenso auf $q$-rekursive Folgen angewendet werden können.
• Es wird das qualitative und quantitative Verhalten von $q$-rekursiven Folgen für wachsendes $n$ sowie das asymptotische Verhalten der Partialsummen bestimmt. Diese Ergebnisse basieren auf einem sehr allgemeinen Resultat für das asymptotische Verhalten von $q$-regulären Folgen, welches speziell für $q$-rekursive Folgen verbessert wurde.

Nach dem Beweis der Regularität und der Herleitung von allgemeinen asymptotischen Formeln für diese Klasse von Folgen werden drei konkrete Folgen aus der Kombinatorik untersucht. Im Speziellen wird gezeigt, dass

• Sterns diatomische Folge (A002487 in der Online-Enzyklopädie der Zahlenfolgen OEIS),
• die Anzahl der Nicht-Null-Einträge in einem verallgemeinerten Pascal’schen Dreieck sowie
• die Anzahl der unbordered factors in der Thue–Morse-Folge (A309894 in der Online-Enzyklopädie der Zahlenfolgen OEIS)

jeweils $2$-rekursiv sind, und abschließend wird deren asymptotisches Wachstum hergeleitet.

Zu guter Letzt sei hier festgehalten, dass eine Publikation zu dieser Masterarbeit gemeinsam mit Clemens Heuberger und Daniel Krenn kurz vor der Einreichung bei einer peer-reviewten Fachzeitschrift steht. Der begleitende Code zur Masterarbeit ist auf https://trac.sagemath.org/ticket/27940 zu finden und wird voraussichtlich auch bald Teil des quelloffenen Computermathematiksystems SageMath sein.

Außerdem wird es in nächster Zeit auch Blog-Beiträge geben, welche die angesprochenen Thematiken und Resultate aus mathematischer Sicht näher beleuchten.

Auflösung

Es gibt mehrere Möglichkeiten, obige Beispiel-Folge zu interpretieren und eine Bildungsvorschrift für sie zu formulieren. Ich möchte hier kurz auf zwei davon eingehen:

• Die Folge zählt, wie oft sich eine Zahl ohne Rest halbieren lässt; also $1$ gar nicht, $2$ einmal, $3$ gar nicht, $4$ zweimal, $5$ gar nicht, $6$ einmal usw.
• Wir starten mit den Zahlen $0, 1$. Diese Zahlenfolge hängen wir an sie selbst dran, erhalten demnach $0,1,0,1$ und erhöhen die letzte Zahl nun um $1$, was $0,1,0,2$ ergibt. Das sind die ersten vier Zahlen der Folge. Als nächstes hängen wir an $0,1,0,2$ wieder $0,1,0,2$ dran und erhöhen die letzte Zahl um $1$. Das ergibt $0,1,0,2,0,1,0,3$ und somit die ersten acht Zahlen der Folge. Auf gleiche Weise können wir dieses Schema fortführen und erhalten so viele Elemente der Folge wie wir möchten.

Die angegebene Folge ist sowohl $2$-rekursiv also auch $2$-regulär. Es ist die Folge A007814 in der Online-Enzyklopädie der Zahlenfolgen OEIS. Dort findet man weitere Interpretationen der Folge, und bei Bedarf auch die weiteren Folgenglieder.

---

*Ich freue mich über jegliche Kommentare zu diesem Blog-Post per Email! Weiters ist zu beachten, dass die deutsche Version dieses Blog-Posts geringfügig von der englischen Version abweichen kann, der Inhalt ist aber auf jeden Fall derselbe.