Automatic sequences and formal algebraic series

How can we tell whether a (infinite) binary sequence is "random"? Given the difficulty of the question and the non-universal nature of the answers (random in what sense? for what use?), we can imagine asking the question in reverse, so to speak, and asking what a "deterministic" sequence is.

Among deterministic sequences, those generated by "abstract machines" seem the easiest to study. This is the case for sequences generated by finite automata, also known as "automatic sequences", an informal definition of which could be that they are sequences whose n ^e term depends on the value given by a finite automaton (which could be represented as a kind of graph with labels, but for which a formal definition will be given later) into which we enter one after the other the digits of the integer n in a given integer base.

The sequences thus constructed are of course deterministic; some of them may be periodic or ultimately periodic (periodic from a certain rank), but those that are not periodic have the double particularity of being "easy" to generate but also of being "complicated" (as could be "chaotic" or even... random sequences).

In what follows, we present this family of sequences, focusing on the properties of the associated formal series over a finite field. The fundamental result (Christol's theorem) has historically been an important bridge between automata theory (and hence theoretical computer science) and number theory. We will also mention, very briefly, connections with other fields of mathematics, physics (quasicrystals) and even musical composition.

The systematic study of automatic sequences began with three articles by Alan Cobham between 1968 and 1972 . Their development in relation to number theory began with an article by Gilles Christol in 1979 , followed by an article by Gilles Christol, Teturo Kamae, Michel Mendès France and Gérard Rauzy...