Arithmetic properties of automata: regular sequences.(English)Zbl 0656.10033

In 1980 G. Christol, T. Kamae, M. Mendès-France and G. Rauzy [Bull. Soc. Math. Fr. 108, 401-419 (1980; Zbl 0472.10035)] proved that a formal power series with coefficients in the finite field $${\mathbb{F}}_ q$$ is algebraic over the field of rational functions $${\mathbb{F}}_ q(X)$$ if and only if the sequence of its coefficients is q- automatic. Using a (combinatorial) theorem of A. Cobham they deduced the following typical result: If $$(a_ n)$$ is a sequence with values 0 and 1, which is not ultimately periodic, then the series $$\sum a_ nX^ n$$ cannot be algebraic over both $${\mathbb{F}}_ 2(X)$$ and $${\mathbb{F}}_ 3(X).$$
Then they asked the natural question: let $$(a_ n)$$ be a nonperiodic sequence as above. Prove that if the series $$\sum a_ nX^ n$$ is algebraic over $${\mathbb{F}}_ 2(X)$$, then the real number $$\sum a_ n2^{- n}$$ is transcendental over $${\mathbb{Q}}.$$
The authors gave an answer to this question [J. Reine Angew. Math. 330, 159-172 (1982; Zbl 0468.10019)], which depended on a technical hypothesis that they could not verify in all cases. The aim of the paper under review is to provide a complete proof (giving also algebraic independence of “automatic” real numbers): the sequence of digits of an irrational algebraic number in any base cannot be generated by a finite automaton. They use “à la Mahler” techniques: very roughly, if a function F(X) satisfies a relation $$\sum P_ k(X)F(X^{p^ k})=0$$, where the $$P_ k's$$ are polynomials, then the values F(a) are transcendental for reasonable a’s.
One of the consequences of the above mentioned result is a partial answer to the problem of J. Hartmanis and R. E. Stearns [Trans. Am. Math. Soc. 117, 285-306 (1965; Zbl 0131.154)], as well as a contribution (at least an indirect contribution) to the extremely difficult conjecture on the normality of every irrational algebraic number.
Reviewer: J.-P.Allouche

MSC:

 11J81 Transcendence (general theory) 68Q70 Algebraic theory of languages and automata 11J85 Algebraic independence; Gel’fond’s method 11B99 Sequences and sets
Full Text: