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.
Hier werden alle mit diesem Projekt in Zusammenhang stehenden Forschungsaktivitäten angezeigt. Mit dem untenstehenden Link können sie sich diese Forschungsaktivitäten in der Suche anzeigen lassen und gegebenenfalls exportieren.
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)