Gestreckte Exponenten und darüber hinaus

Viele mathematische Probleme beginnen mit einer einfachen Frage: Wie viele gibt es? Ihr unschuldiger und zum Teil naiv wirkender Charakter verbirgt die Tatsache, dass ihre Beantwortung häufig nicht nur schwierig sondern sogar unmöglich ist. Mathematisch ist diese Frage der abzählenden Kombinatorik zuzuordnen, jedoch taucht sie in vielen unterschiedlichen Disziplinen auf, welche von der Informatik (z.B. Analyse von Algorithmen) bis zur Biologie (z.B. phylogenetische Bäume) reichen. Von vordergründigem Interesse sind universelle Phänomene in großen zufälligen Strukturen. Diese beschreiben die Beobachtung, dass viele kombinatorische Strukturen nur von wenigen globalen Eigenschaften beeinflusst werden und nicht von konkreten Details abhängen. Dieses Projekt widmet sich einem solchen Phänomen: dem Auftreten von gestreckten Exponenten in der asymptotischen Abzählung. Doch was bedeutet das? Eine Zahlenfolge ist asymptotisch äquivalent zu einer anderen, wenn ihr gemeinsamer Quotient gegen 1 strebt. Hierbei ist die Idee, dass für eine gegebene komplexe Zahlenfolge die schwierig zu berechnen ist, eine einfachere Darstellung gefunden wird, die deren Größenordnung widerspiegelt. Dadurch lassen sich effizient Approximationen berechnen und verschiedene Zahlenfolgen miteinander vergleichen. Zum Beispiel gibt es n!=n*(n-1)*...*2*1 viele Möglichkeiten n unterschiedliche Spielkarten anzuordnen. Eine asymptotische Formel ist hier durch die Stirlingformel gegeben, die zeigt, dass n! superexponentiell wächst. Asymptotische Formeln können aus verschiedenen Komponenten bestehen, die zum Beispiel das polynomiale oder das exponentielle Wachstum darstellen. Gestreckte Exponenten sind eine bisher selten beobachtete Komponente, die grob gesagt zwischen polynomialem und exponentiellem Wachstum liegt. Sie haben die Form a^(n^s) für reelle Zahlen a und s sowie eine natürliche Zahl n. Kürzlich sind einige offene Probleme gelöst worden, in denen schlussendlich die Existenz von gestreckten Exponenten für deren Schwierigkeit verantwortlich war. Das Ziel dieses Projekts ist es generische Methoden zu entwickeln um solche gestreckten Exponenten nachzuweisen und zu berechnen. Weiters werden wir eine möglichst allgemeine Klasse von 2-parametrigen Rekursionen klassifizieren, die gestreckte Exponenten besitzen. Diese wollen wir dann auf offene Fragestellungen in der Mathematik, Biologie, Physik oder Chemie anwenden und hoffentlich viele neue Beispiele für das Auftreten von gestreckten Exponenten finden. Konkret handelt es sich um Probleme in der Automatentheorie, der Kompression von Datenstrukturen, der Phylogenetik, der algebraischen Gruppentheorie, der Warteschlangentheorie und vielen mehr. Unsere Methode zeichnet sich durch ihre Interdisziplinarität aus und vereint die Gebiete der Kombinatorik, der Computeralgebra und der komplexen Analysis. Unsere Ergebnisse erlauben weiterführend die tiefergehende Analyse von weiteren Parametern wie der typischen Laufzeit von Algorithmen.