Arithmetic properties of automata: regular sequences.

*(English)*Zbl 0656.10033In 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.

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 |