Multiplicativity, Determinism, and Randomness

The aim of the Austrian-French joint project is to make progress on various questions that interrelate and link the notion of randomness (or pseudo- randomness) with the notion of determinism in the context of analytic number theory, combinatorics on words, automata theory, quasi-random sequences and nearby disciplines. Many well-known fundamental problems can be captured by this concept. An illustrative example in this area is the classical Möbius function which per se is deterministic but resembles much of the overall behaviour of a random sequence. In this context we are interested in studying the independence between the Möbius function and various deterministic functions such as functions that are produced by a dynamical system of zero entropy or by a simple algorithm based on the binary digital representation. Informally, the difficulty of this independence problem reflects the difficulty of the transition from the digital representation of an integer to its multiplicative representation as a product of prime factors. This field of questions is the source of many important open problems in mathematics and computer science. In particular, we mention the construction of normal numbers, the analysis of pseudo-random and complexity measures, and the search for optimal discrepancy estimates for digitally based sequences or other quasi-random sequences which are main lines of research in this joint project. The Austrian-French Consortium consists of 11 researchers and is based in Graz, Linz, Vienna, Bordeaux, Calais, Marseille, and Nancy. It is an important aim of this joint project to continue and to extend successful long-term collaborations between several of these groups. Additionally it is possible to employ young Post-Doc researchers within this joint project. They will be employed half the time in Austria and the second half in France in order to give them a broader research perspective. Regular research workshops and meetings will be organized, too.

The aim of the Austrian-French joint project was to make progress on various questions that interrelate and link the notion of randomness (or pseudo-randomness) with the notion of determinism in the context of analytic number theory, combinatorics on words, automata theory, quasi-random sequences and nearby disciplines. Many well-known fundamental problems can be captured by this concept. An illustrative example in this area is the classical Möbius function which per se is deterministic but resembles much of the overall behaviour of a random sequence. In this context we are interested in studying the independence between the Möbius function and various deterministic functions such as functions that are produced by a dynamical system of zero entropy or by a simple algorithm based on the binary digital representation. Informally, the difficulty of this independence problem reflects the difficulty of the transition from the digital representation of an integer to its multiplicative representation as a product of prime factors. This field of questions is the source of many important open problems in mathematics and computer science. In particular, we mention its relations to a conjecture due to Peter Sarnak (IAS). The Austrian-French Consortium consisted of eleven researchers and was based in Graz, Linz, Vienna, Bordeaux, Calais, Marseille, and Nancy. According to the plans of the proposal several postdoctorial researchers have been employed partly in France and in Austria. Furthermore five PhD thesis were supervised, two of them in form of a Cotutelle between France and Austria. The consortium has published more than 60 peer reviewed papers (more than 30 with Austrian participation) within the project and has (co-)organized sic scientific conferences and workshop on scientifc topics related to the project. Among the scientific achievements we highlight here some that are related to the Sarnak conjecture and to so-called automatic sequences. Automatic sequences can be generated by finite state machines and the digital (for example the binary or decimal) expansions of positive integers. The most prominent automatic sequence is the Thue-Morse sequence. In a first joint project, members of France and Austria proved the Sarnak conjecture for automatic sequences that are constructed via a synchronizing automaton as well as a prime number theorem for the associated sequences. Secondly, with a very fine study of the underlying graphs, the conjecture was shown for all automatic sequences. Furthermore the project allowed to state and prove that the Thue-Morse sequence is normal along the subsequences of squares, which means that the number of occurrences of any n-tuple of digits is well-distributed in this subsequence. This allows a very simple (and new) explicit construnction of normal sequences. These two results were well beyond reach before MuDeRa. More information can be found on the website http://www.iecl.univ-lorraine.fr/~Thomas.Stoll/MuDeRa/