##
**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.

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 |

### Keywords:

decimal expansion of algebraic irrationals; finite automaton; transcendence; automatic sequences; Mahler’s methods; Hartmanis-Stearns problem; algebraic independence
PDFBibTeX
XMLCite

\textit{J. H. Loxton} and \textit{A. J. van der Poorten}, J. Reine Angew. Math. 392, 57--69 (1988; Zbl 0656.10033)

### Online Encyclopedia of Integer Sequences:

Loxton-van der Poorten sequence: base-4 representation contains only -1, 0, +1.Fixed point of the morphism 1->1321, 2->0021, 3->1300, 0->0000 starting from 1.