Project description

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 extremly 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 neighbors 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.

Datenverschlüsselung (z.B. für sichere Verbindungen im Internet) beruht auf der effizienten Berechnungen von Einweg-Funktionen, d.h. Funktionen, für die es sehr aufwändig ist, aus dem Resultat Rückschlüsse auf die Eingabe zu ziehen. Ein Beispiel ist Exponentiation in endlichen Strukturen, wo es sehr schwierig ist, aus dem Ergebnis den Exponenten zu bestimmen. Das Standardverfahren für Exponentiation beruht auf sukzessivem Quadrieren und Multiplizieren, wobei die Anzahl der Quadrierungen der Anzahl der Ziffern und die Anzahl der Multiplikationen der Anzahl der von Null verschiedenen Ziffern des Exponenten ist. Verallgemeinerte Ziffernentwicklungen (z.B. mit negativen Ziffern) führen zu effizienteren Algorithmen. Ein Ziel des Projekts ist es, präzise Abschätzungen für deren Laufzeit anzugeben, um verschiedene Verfahren vergleichen zu können.

Die Analyse von Ziffernentwicklungen wird durch die Verwendung von Automaten, einem Konzept aus der theoretischen Informatik, erleichtert. Einen Automaten kann man sich als eine Black Box vorstellen, die ihre Eingabe mittels eines endlichen Speichers in eine Ausgabe umwandelt. Ein Automat kann auch durch einen Graphen dargestellt werden, dessen Knoten dem endlichen Speicher und dessen Kanten Übergänge dazwischen darstellen. Die Untersuchung von Zusammenhangseigenschaften dieses Graphen führt zu qualitativen und quantitativen Resultaten über das Wachstum der zugehörigen Folge. Es ist geplant, Resultate über Automaten so zu verallgemeinern, dass auch allgemeinere Folgentypen analysiert werden können.

Bäume, also kreisfreie Graphen, treten auch als natürliche Darstellungsform verschiedener Algorithmen auf, beispielsweise bei der Datenkompression. Die Effizienz eines solchen Algorithmus kann gemessen werden, indem man Kennzahlen wie Breite oder Höhe des zugehörigen Baumes bestimmt. Einerseits ist geplant, zusätzliche Parameter von Bäumen aus passenden Klassen sowie deren Verbindungen zu verallgemeinerten Zählproblemen zu untersuchen. Andererseits sind Bäume an sich auch ein lohnender Untersuchungsgegenstand. So ist etwa geplant, die größtmögliche Anzahl an Bäumen zu bestimmen, wenn die Anzahl der Nachbarn aller Knoten festgelegt ist.

Andere, eng damit verbundene, Fragestellungen werden ebenfalls untersucht. Insbesondere sollen Methoden weiterentwickelt werden, um zu zeigen, dass die meisten der auftretenden Größen gegen eine Normalverteilung (Gaußsche Glockenkurve) streben.

Dieses Projekt dient der Untersuchung von Fragen zu all diesen Themen vom Standpunkt der analytischen Kombinatorik aus, wobei besonderer Wert auf die Verbindungen zwischen den Gebieten gelegt wird.

Teile des Projekts haben algorithmische Aspekte. Diese werden im freien mathematischen Software-System SageMath implementiert werden, um die Resultate des Projekts der Scientific Community leicht zugänglich zu machen.

Details

Project title Analytic Combinatorics: Digits, Automata, Trees
Principal investigator Clemens Heuberger
Address / Institute Institut für Mathematik Alpen-Adria-Universität Klagenfurt Universitätsstraße 65–67 9020 Klagenfurt am Wörthersee Austria
Funding organization Austrian Science Fund FWF
FWF project number P28466-N35
Approval date 22.06.2015
Lifetime 01.06.2016 – 31.05.2021
Scientific field 101 Mathematics (100%)
Keywords Analytic Combinatorics, Digit Expansion, Sequence, Automaton, Tree, Limit Theorem