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


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