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

Allouche, Jean-Paul

Expo. Math. 5, 239-266 (1987).

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\).

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

Keywords:

survey; randomness; automatic sequences; Thue-Morse sequence; Rudin-Shapiro sequences; Baum-Sweet sequence; algebraic functions; uniform substitutions; finite automata; Taylor coefficients of algebraic functions; sums of digits; Dirichlet series; fractals; iteration of functions; Jack symmetric functions; partitions; spherical functions; Schur functions

Citations:

Zbl 0656.10033; Zbl 0472.10035; Zbl 0641.20010; Zbl 0198.04606; Zbl 0104.02803