Analytic Combinatorics: Digits, Automata and Trees

Data encryption (e.g. for secure web sites) relies on the efficient computation of one-way functions. For these functions, it is very time consuming to determine the input given the result. An example is taking powers of an element in a finite structure, where it is extremely difficult to recover the exponent. The standard approach for exponentiation is the so-called square-and-multiply method, where the number of squaring operations depends on the number of digits in the exponent, and the number of multiplications is the number of non-zero digits. Generalizing the notion of digit expansion (for instance, including negative digits) leads to more efficient algorithms. It is one aim of this project to provide a precise estimate of their expected running time in order to be able to compare various methods. The analysis of digit expansion is facilitated by the use of the concept of automata from theoretical computer science. An automaton can be thought of as a black box transforming some input into some output step by step using only a finite amount of memory. An automaton can also be seen as a graph where the vertices correspond to the finite memory, and edges are transitions between them. Investigating connectivity properties of this graph leads to qualitative and quantitative results on the growth of the corresponding sequence. We plan to extend results on automata to the analysis of more general types of sequences. Trees, i.e. connected graphs without cycles, also occur as a natural representation of algorithms, such as data-compression methods. The efficiency of the algorithm can be measured by considering properties of the tree, such as the width or the height. On the one hand, it is intended to investigate additional parameters of suitable classes of trees and their connections to generalized counting problems. On the other hand, trees are a fascinating object of study on their own. For instance, we intend to investigate the maximal number of trees that are possible when the number of neighbours of all vertices are fixed. Other closely related topics will also be investigated. In particular, we intend to further develop tools for proving that most of the quantities encountered in the above problems tend to a normal distribution (Gaussian bell curve). This project proposes to investigate questions on all these topics from the viewpoint of analytic combinatorics, emphasizing the connections between these areas. Parts of the project have an algorithmic aspect. Those results will be implemented in the free, open-source mathematics software system SageMath, so that they can be readily used by the scientific community.

Analytic Combinatorics is a relatively new area within combinatorics-a field of mathematics which studies counting problems. Such problems are by nature discrete, but within Analytic Combinatorics, tools from continuous mathematics are used. One of the main methods uses generating functions which encode sequences of numbers into functions: for example, the sequence 2, 5, 14, 42, 132, can be encoded as f(x) = 2 + 5x + 14x+ 42x + 132x + . In this way we use properties of the continuous functions to determine properties of discrete sequences such as how quickly a sequence grows. Regular sequences were one of the main topics of study of the project. These are sequences where the n-th term is determined by rewriting the number n in a different predetermined base-numbers are commonly used in base 10, i.e. 12 = 110 + 210, but in computers the binary system based on 2 (rather than 10) is used, i.e. 1100 = 12 + 12 + 02 + 02, and in a similar way we can write numbers in any base. These sequences have applications to algorithms known as "divide-and-conquer" algorithms, which usually split data into two almost equally sized parts, repeat this process until data is manageable, and then combine all of the data again. From the research done in this project, the growth of regular sequences has been described very precisely. Another core area of interest of the project was lattice paths. A common example of a lattice path is a graph from the stock market-the price of a stock is measured periodically, and a line segment is drawn from the previous price to the current price. Mathematically, lattice paths can have various restrictions placed on them including their starting and ending point, and the allowed vertical change. A powerful tool from analytic combinatorics for studying lattice paths is the kernel method, which was generalized to what is known as the vectorial kernel method, and used to solve a number of problems involving lattice paths as part of this project. Trees are mathematical structures which are closely related to lattice paths, and are commonly used to store or search for information-the underlying structure of files and folders stored on a computer is a tree. One subject of study of the project was reduction processes in trees, which for example would involve removing the leaves (end-points-files or empty folders in the example) of a tree in consecutive steps. These tree reductions can be used to study parameters in trees such as the height. Such parameters allow one to identify and characterize "main stems" of networks. The project also produced several contributions to SageMath, an open source mathematics software system.