##
**Finite automata in number theory.
(Automates finis en théorie des nombres.)**
*(French)*
Zbl 0641.10041

This is a readable and pleasant survey. Its contents are as follows: The author briefly introduces the notion of “randomness” of a sequence. Then we are reminded, with all details, of the standard interesting examples of automatic sequences (the Thue-Morse and Rudin-Shapiro sequences, the Baum-Sweet sequence – which arises in the study of algebraic functions in positive characteristic with bounded partial quotients in their continued fraction expansion, and the celebrated paperfolding sequence). If \((a_n)\) is \(p\)-automatic then \(\sum a_nX^n\) is algebraic over \(\mathbb F_p(x)\) and the series is a diagonal of a rational function over \(\mathbb F_p\) in several variables.

Then there is a discussion of sequences generated by uniform substitutions and of the theorem of G. Christol, T. Kamae, M. Mendès-France and G. Rauzy [Bull. Soc. Math. Fr. 108, 401–419 (1980; Zbl 0472.10035)] identifying such substitutions, finite automata and reductions of the sequence of Taylor coefficients of algebraic functions. The theorem of J. H. Loxton and A. J. van der Poorten [see also “Arithmetic properties of automata: regular sequences”, J. Reine Angew. Math. 392, 57–69 (1988; Zbl 0656.10033)], shows that the digits of the expansion, in any base, of an algebraic irrational number do not yield an automatic sequence.

Next, the author cites the relationship of finite automata with various matters of representing numbers – sums of digits, “folded” continued fractions,.... Then here is extensive mention of results and conjectures concerning Dirichlet series with coefficients generated by finite automata. Finally, there are brief reports on automata, fractals, and iteration of functions; on automata and combinatorics; and on the work of Mendès France on automata and theoretical physics.

There is a useful list of references; I add a recent paper of P. Hanlon [J. Comb. Theory, Ser. A 47, No. 1, 37–70 (1988; Zbl 0641.20010)].

The Jack symmetric functions, \(J_{\lambda}(\alpha;x)\) are symmetric functions indexed by partitions \(\lambda\) which depend on an indeterminate \(\alpha\) [see H. Jack, Proc. R. Soc. Edinb., Sect. A 69, 1–18 (1970; Zbl 0198.04606)]. These functions are of recent interest because they are common generalizations of two sets of spherical functions, the Schur functions \(s_{\lambda}(x)\) and the zonal polynomials \(Z_{\lambda}(x)\) [see A. T. James, Ann. Math., II. Ser. 74, 456-469 (1961; Zbl 0104.02803)]. Write \(J_{\lambda}(\alpha,x)\) in terms of the monomial symmetric functions \(J_{\lambda}(\alpha,x)=\sum_{\mu}C_{\lambda \mu}(\alpha)m_{\mu}(x)\).

This paper stems from an effort to settle the still open question of whether the coefficients \(C_{\lambda \mu}(\alpha)\) are polynomials in \(\alpha\).

Then there is a discussion of sequences generated by uniform substitutions and of the theorem of G. Christol, T. Kamae, M. Mendès-France and G. Rauzy [Bull. Soc. Math. Fr. 108, 401–419 (1980; Zbl 0472.10035)] identifying such substitutions, finite automata and reductions of the sequence of Taylor coefficients of algebraic functions. The theorem of J. H. Loxton and A. J. van der Poorten [see also “Arithmetic properties of automata: regular sequences”, J. Reine Angew. Math. 392, 57–69 (1988; Zbl 0656.10033)], shows that the digits of the expansion, in any base, of an algebraic irrational number do not yield an automatic sequence.

Next, the author cites the relationship of finite automata with various matters of representing numbers – sums of digits, “folded” continued fractions,.... Then here is extensive mention of results and conjectures concerning Dirichlet series with coefficients generated by finite automata. Finally, there are brief reports on automata, fractals, and iteration of functions; on automata and combinatorics; and on the work of Mendès France on automata and theoretical physics.

There is a useful list of references; I add a recent paper of P. Hanlon [J. Comb. Theory, Ser. A 47, No. 1, 37–70 (1988; Zbl 0641.20010)].

The Jack symmetric functions, \(J_{\lambda}(\alpha;x)\) are symmetric functions indexed by partitions \(\lambda\) which depend on an indeterminate \(\alpha\) [see H. Jack, Proc. R. Soc. Edinb., Sect. A 69, 1–18 (1970; Zbl 0198.04606)]. These functions are of recent interest because they are common generalizations of two sets of spherical functions, the Schur functions \(s_{\lambda}(x)\) and the zonal polynomials \(Z_{\lambda}(x)\) [see A. T. James, Ann. Math., II. Ser. 74, 456-469 (1961; Zbl 0104.02803)]. Write \(J_{\lambda}(\alpha,x)\) in terms of the monomial symmetric functions \(J_{\lambda}(\alpha,x)=\sum_{\mu}C_{\lambda \mu}(\alpha)m_{\mu}(x)\).

This paper stems from an effort to settle the still open question of whether the coefficients \(C_{\lambda \mu}(\alpha)\) are polynomials in \(\alpha\).

Reviewer: Ya. G. Berkovich

### MSC:

11B85 | Automata sequences |

11K31 | Special sequences |

68Q70 | Algebraic theory of languages and automata |

11A63 | Radix representation; digital problems |

42A61 | Probabilistic methods for one variable harmonic analysis |

20C30 | Representations of finite symmetric groups |

05A17 | Combinatorial aspects of partitions of integers |

33C55 | Spherical harmonics |