Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - ANT (Automata in Number Theory)

Teaser

Finite automata are fundamental objects in Computer Science, of great importance on one hand for theoretical aspects (formal language theory, decidability, complexity) and on the other for practical applications (parsing). In Mathematics, and especially in number theory...

Summary

Finite automata are fundamental objects in Computer Science, of great importance on one hand for theoretical aspects (formal language theory, decidability, complexity) and on the other for practical applications (parsing). In Mathematics, and especially in number theory, finite automata are mainly used as simple devices for generating sequences of symbols over a finite set (e.g., digital representations of real numbers), and for recognizing some sets of integers or more generally of finitely generated abelian groups or monoids. One of the main features of these automatic structures comes from the fact that they are highly ordered without necessarily being trivial (i.e., periodic). With their rich fractal nature, they lie somewhere between order and chaos, even if, in most respects, their rigidity prevails. Over the last few years, several ground-breaking results have lead to a great renewed interest in the study of automatic structures in arithmetics.

A primary objective of the ANT project is to exploit this opportunity by developing new directions and interactions between automata and number theory. The project is based on three lines of research concerning fundamental number theoretical problems that have baffled mathematicians for decades. They include the study of integer base expansions of classical constants, of arithmetical linear differential equations and their link with enumerative combinatorics, and of arithmetics in positive characteristic. At first glance, these topics may seem unrelated, but, surprisingly enough, the theory of finite automata serves as a natural guideline. We stress that this new point of view on classical questions is a key part of our methodology: we aim at creating a powerful synergy between the different approaches we propose to develop, placing automata theory and related methods at the heart of the subject.

Work performed

Famous real numbers like the square root of 2 of pi admit very simple geometric descriptions. This strongly contrasts with their decimal expansions which seem to be hardly predictable. An old source of frustration for mathematicians thus arises from the study of integer base expansions of classical mathematical constants. Over the years, different ways have been envisaged to formalize this old problem. This reoccurring theme appeared in particular in three fundamental papers using: the language of probability according to Borel in 1909, the language of dynamical systems according to Morse and Hedlund in 1938, and the language of Turing machines according to Hartmanis and
Stearns in 1965. In the period cover by this report, the PI, in collaboration with Cassaigne and Le Gonidec, pushes further a method based on tools from Diophantine analysis (the p-adic subspace theorem) that he introduced with Bugeaud some years ago. One of the major result they obtain is that the expansion in an integer base of an irrational algebraic number cannot be generated by a deterministic pushdown automaton. To date, this is the main achievement towards the Hartmanis-Stearns problem. In collaboration with Faverjon, the PI also develops an old method introduced by Mahler at the end of the 1920s, solving one of the main problem concerning the transcendence of the values of Mahler functions at algebraic points. Mahler\'s method has become a hot topic during the past three years. People from number theory (Adamczewski, Faverjon, Philippon, Bell, Coons, Fernandes), from difference Galois theory (Dreyfus, Hardouin, Roques, Singer, Schäfke), and from computer science (Chyzak, Dumas, Mezzaroba) are now working on this topic with different point of views. Another example is the PhD Thesis of Fernandes, developing Mahler\'s method over function fields of characteristic p. The ANT project clearly contribute to this renewed interest for Mahler\'s equations.

In collaboration with Bell and Delaygue, the PI also develops a totally new method for proving algebraic independence of G-functions, which are a class of fascinating analytic functions introduced by Siegel. Usually the algebraic relations between these functions are studied by using the differential Galois theory for such functions satisfy linear differential equations. The new approach is not based on these differential equations but instead on some infinite family of linear difference equations associated with the Frobenius that are obtained by reduction modulo prime ideals. When these linear difference equations have order one, the coefficients of the corresponding G-functions satisfy congruences reminiscent of a classical theorem of Lucas on binomial coefficients (also related to automatic sequences). At first glance, it may seem somewhat miraculous that a G-function could satisfy Lucas-type congruences for infinitely many prime ideals. Surprisingly enough, they show that this situation occurs remarkably often.

All these results are developed at the same time, creating a great synergy between topics that seem unrelated in appearance. For instance, Siegel G- and E-functions and Mahler functions now emerge as the hidden GEM of the project.

Final results

There are several important results going far beyond the state of the art that I expect until the end of the project. Here are what I consider as the two main problems I hope to contribute about until the end of the project.

First, the PI and Faverjon start a reshape of Mahler\'s method in several variables. Only very partial results have been obtained so far in this direction. This is a very challenging and promising topic because of the possible applications of these results to old problems concerning the expansion of both natural numbers and real numbers in integer bases. In particular, old problems which involve finite automata and base change. To date, essentially nothing is known towards this kind of problems.

A second exciting problem is to transfer the method I develop with Bell and Delaygue to deal with the algebraic independence of E-functions. This is motivated by the famous Siegel-Shidlovskii theorem which applies to the values of such analytic functions. The main difficulty is that, contrary to G-functions, E-functions cannot, in principle, be reduced modulo prime ideals. We plan to use the theory of divided power to try to overcome this difficulty.

Website & more info

More info: https://sites.google.com/site/ercantunivlyon1/home.