Stretched exponentials and beyond

PR Abstract

Many mathematical problems begin with a simple question: "How many … are there?" Its innocent and sometimes naive character hides the fact that its answer is often not only difficult but even impossible. Mathematically, this question belongs to enumerative combinatorics, but it appears in many different disciplines, ranging from computer science (e.g., analysis of algorithms) to biology (e.g., phylogenetic trees). Of primary interest are universal phenomena in large random structures. These describe the observation that many combinatorial structures are influenced by only a few global properties and do not depend on concrete details. This project is devoted to one such phenomenon: the occurrence of stretched exponentials in asymptotic counting. But what does this mean?

A sequence of numbers is asymptotically equivalent to another if their common quotient tends towards 1. The idea here is that for a given complicated number sequence that is difficult to compute, a simpler representation is found that reflects its order of magnitude. In this way, approximations can be calculated efficiently and different number sequences can be compared with each other. For example, there are n!=n*(n-1)*...*2*1 many ways to arrange n different playing cards. An asymptotic formula is given here by Stirling's formula, which shows that n! grows superexponentially. Asymptotic formulas can consist of different components that represent, for example, polynomial or exponential growth. Stretched exponentials are a component rarely observed so far, which roughly speaking lies between polynomial and exponential growth. They have the form a^(n^s) for real numbers a and s as well as a natural number n. Recently, some open problems have been solved in which the existence of stretched exponentials was ultimately responsible for their difficulty.

The aim of this project is to develop generic methods to prove and compute such stretched exponentials. Furthermore, we want to classify a general class of two-parameter recurrence relations that have stretched exponentials. We then want to apply this result to open problems in mathematics, biology, physics or chemistry and hopefully find many new examples for the occurrence of stretched exponentials. Specifically, these are problems in automata theory, the compression of data structures, phylogenetics, algebraic group theory, queueing theory and many more. Our method is characterized by its interdisciplinarity and combines the fields of combinatorics, computer algebra, and complex analysis. Our results allow further in-depth analysis of additional parameters such as the typical running time of algorithms.

Scientific Abstract

This project aims at shedding light on the large-scale behavior of random discrete structures, such as trees and tree-like structures. Such objects appear in numerous scientific fields, ranging from automata theory in computer science to phylogenetic trees in biology. In each case one is interested in understanding the typical shape of such objects, however the precise questions studied can be as diverse as the objects themselves. There are many conjectures about the behavior of these objects, which are in many cases widely open. Often not even the basic counting problem has been solved. In some cases the difficulties arise due to the still mysterious phenomenon of stretched exponentials m^(n^s), where m>0 and 0<\s<1.


Research questions and objectives

The aim of the project is to gain new insights into the presence of stretched exponentials in asymptotic enumeration. We plan to address the following subjects:

  • developing a generic method to prove Theta-results involving stretched exponentials
  • determining the multiplicative constant and the D-finite behavior
  • analyzing the shape characteristics of directed acyclic graphs and related structures

Approach and methods

At the core lies the detailed analysis of a class of two-parameter recurrence relations with special weights. This class is motivated by a weighted model of lattice paths that is bijectively connected to the tree-like structures we will analyze using, e.g., the symbolic method and generating functions. The further analysis then requires the usage of computer algebra in order to numerically and heuristically conjecture and prove the asymptotics. Hereby, we need to analyze ordinary differential equations and work with Newton polygons. Furthermore, we will refine the analysis to derive expressions for the involved constants using, e.g., the saddle point method and singularity analysis.


Level of originality and innovation

The biggest innovation is a new generic method to prove stretched exponentials and analyze the respective counting sequences. So far the saddle point method is the only generic method for proving such a phenomenon. This is the gap that this research project will close: We will develop a new versatile method to prove stretched exponentials and show that this phenomenon is not as rare as could be expected also proving many open conjectures. Our approach enables a detailed analysis of these objects and gives access to their limit shape characteristics.



Project Contributors



Contributor

Michael Wallner (PI)

Contributor

Manosij Ghosh Dastidar (PhD student)

Publications

  1. A Combinatorial Framework for the Pons-Batle Identity: Young Tableaux, Lattice Paths, and Limit Laws
    Hexuan Liu, Guan-Ru Yu, and Michael Wallner; submitted.
  2. Combinatorics of nondeterministic walks
    Élie de Panafieu and Michael Wallner; submitted.
  3. Bijections and congruences involving lattice paths and integer compositions
    Manosij Ghosh Dastidar and Michael Wallner; submitted.
  4. The decompressed tree size of k-ary chains
    Michael Wallner; submitted.
  5. p(5n+4) again
    George Andrews and Manosij Ghosh Dastidar; The Ramanujan Journal, Volume 69, article number 26, 2026.
  6. The decompressed tree size of k-ary chains (extended abstract)
    Michael Wallner; in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb'25), 2025.
  7. Bivariate asymptotics via random walks: application to large genus maps
    Andrew Elvey Price, Wenjie Fang, Baptiste Louf, andGeorge Andrews and Michael Wallner; in the Proceedings of the 37th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2025), 2025.
  8. Enumerative and Distributional Results for d-combining Tree-Child Networks
    Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Guan-Ru Yu, and Michael Wallner; Advances in Applied Mathematics, 157 (2024), 102704, 2024.
  9. Walks avoiding a quadrant and the reflection principle
    Mireille Bousquet-Mélou and Michael Wallner; European Journal of Combinatorics, 119 (2024), Paper No. 103803, 2024.
  10. Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
    Cyril Banderier, Markus Kuba, and Michael Wallner; Annals of Applied Probability, Volume 34(5), pages 4635-4693, 2024.
  11. Composition schemes: q-enumerations and phase transitions
    Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner; in the Proceedings 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024.
  12. A bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes
    Florian Schager and Michael Wallner; in the Proceedings of GASCom 2024 conference, 2024.
  13. Asymptotics of relaxed k-ary trees
    Michael Wallner; in the Proceedings 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024.
  14. Bijections between variants of Dyck paths and integer compositions
    Manosij Ghosh Dastidar and Michael Wallner; in the Proceedings of GASCom 2024 conference, 2024.
  15. The binary digits of n+t
    Lukas Spiegelhofer and Michael Wallner; Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, (5) 24 (2023), no. 1, 1--31, 2023.
  16. Dyck paths and inversion tables
    Michael Wallner; extended abstract in Permutation Patterns 2023, 142-144, 2023.
  17. Inequalities for the partition function arising from truncated theta series
    Koustav Banerjee and Manosij Ghosh Dastidar; RISC Report Series; 22-20, 2023.
  18. Enumeration of d-combining Tree-Child Networks
    Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Guan-Ru Yu, and Michael Wallner; in the Proceedings of the 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022), 2022.
  19. On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks
    Michael Wallner; Aequationes mathematicae, 96, 815-826 (2022), 2022.
  20. Young tableaux with periodic walls: counting with the density method
    Cyril Banderier and Michael Wallner; in the Proceedings of the 33rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC21), 2021.