Analytic Combinatorics: Digits, Automata and Trees

Digit expansions, automata and trees are the objects, as well as the tools, of this research proposal. Digit
expansions to various bases with redundant digit sets act as key ingredients for efficient arithmetic operations in
abelian groups. Automata can frequently be used to describe and analyze these digit representations. The
asymptotic and probabilistic behavior of a sequence defined by an automaton depends on certain properties of
the underlying graph, in particular, on connectivity properties. Considering digit expansions as special partitions
leads to an interpretation as certain trees. The analysis of parameters of these trees leads to results on the
corresponding partitions. This project proposes to investigate questions on those topics from the viewpoint of
analytic combinatorics, emphasizing connections between these areas.
Our motivation for studying redundant digit expansions comes from public-key cryptography: It relies on efficient
scalar multiplication in abelian groups such as the point group of an elliptic curve. The redundancy can be used
for minimizing the Hamming weight of the expansion and thus the number of expensive curve operations.
Choosing efficient endomorphisms instead of the classical doubling operation requires digit expansions with
complex bases. Comparing different algorithms requires a precise asymptotic analysis of these expansions.
Many sequences occurring in the analysis of digit expansions are special q-regular sequences. While many can
even be defined as the output of a transducer and thus can be analyzed completely, some questions, such as
the number of minimal expansions, display a different asymptotic behavior. It is one aim of this project to find
suitable conditions on q-regular sequences to extend the analysis from the case of transducers.
Seeing digit expansions as partitions provides a different point of view. The summands of these partitions are
powers of the base, and additional restrictions on the number of equal summands model the digit set. Lifting this
restriction leads to partitions which can be analyzed by a related class of trees.
The quasi-power theorem is an invaluable tool when proving asymptotic normality of some of the occurring
random variables. We intend to prove higher dimensional analogues of this theorem as well as to thoroughly
discuss its variability condition. Other limiting distributions are expected to appear in the analysis of word
problems. These problems, e.g., certain types of runs, come from various digit problems such as addition.
We plan to use methods from analytic combinatorics such as singularity analysis, saddle point method and
Mellin transform as well as tools from probability theory such as limit theorems and mixing theorems.

Schlagworte: Analytic Combinatorics, Digit Expansion, Sequence, Automaton, Tree, Limit Theorem
Kurztitel: Analytic Combinatorics: DAT
Zeitraum: 01.06.2016 - 31.05.2021
Kontakt-Email: -


MitarbeiterInnen Funktion Zeitraum
Clemens Heuberger (intern)
  • Projektleiter/in
  • 01.06.2016 - 31.05.2021
Andrei Asinowski (intern)
  • wiss. Mitarbeiter/in
  • 01.11.2018 - 31.05.2021
Benjamin Hackl (intern)
  • wiss. Mitarbeiter/in
  • Dissertant/in
  • Kooperationspartner/in
  • 01.06.2018 - 31.08.2018
  • 15.01.2018 - 31.05.2018
  • 01.06.2018 - 31.05.2021
Daniel Krenn (intern)
  • Kooperationspartner/in
  • 01.06.2016 - 31.05.2021
Sarah Jane Selkirk (intern)
  • Dissertant/in
  • 07.01.2019 - 31.05.2021


Projekttyp Forschungsförderung (auf Antrag oder Ausschreibung)
Förderungstyp §26
  • Grundlagenforschung
  • 101002 - Analysis
  • 101012 - Kombinatorik
  • 101024 - Wahrscheinlichkeitstheorie
  • 101025 - Zahlentheorie
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz Genderrelevanz nicht ausgewählt
  • Science to Science (Qualitätsindikator: I)
Klassifikationsraster der zugeordneten Organisationseinheiten:
  • Diskrete Mathematik und Optimierung


Organisation Adresse
Uppsala Universitet
S:t Olofsgatan 10B
75105  Uppsala
  +46 (0)18 471 00 00
  +46 (0)18 471 20 00
S:t Olofsgatan 10B
SE - 75105  Uppsala
University of Stellenbosch
7602 Stellenbosch
ZA  7602 Stellenbosch
Academia Sinica
115 Taipei
China (Republik/Taiwan)
TW  115 Taipei
TU Graz
Rechbauerstraße 12
8020  Graz
Rechbauerstraße 12
AT - 8020  Graz