Rational functions, diagonals, automata and arithmetic. (English) Zbl 0694.10008
Number theory, Proc. 1st Conf. Can. Number Theory Assoc., Banff/Alberta (Can.) 1988, 339-358 (1990).
[For the entire collection see Zbl 0689.00005.]
This paper is a very pleasant survey of the relationships between finite automata, algebraic formal power series, diagonal of rational (or algebraic) multiple power series and arithmetic. If the reader wants to know whether folding a piece of paper gives transcendental numbers, whether the Hadamard product of two algebraic formal power series is itself algebraic, or whether one can find - via automata theory - a two line proof of a result of Deligne, he should definitely enjoy the paper under review.
In the case where the field of constant is not necessarily finite, the reader might also have a look into the (more elementary) survey of the reviewer [Note sur un article de Sharif et Woodcock, Sémin. Théor. Nombres Bordeaux, Sér. II 1, 163-187 (1989)].
This paper is a very pleasant survey of the relationships between finite automata, algebraic formal power series, diagonal of rational (or algebraic) multiple power series and arithmetic. If the reader wants to know whether folding a piece of paper gives transcendental numbers, whether the Hadamard product of two algebraic formal power series is itself algebraic, or whether one can find - via automata theory - a two line proof of a result of Deligne, he should definitely enjoy the paper under review.
In the case where the field of constant is not necessarily finite, the reader might also have a look into the (more elementary) survey of the reviewer [Note sur un article de Sharif et Woodcock, Sémin. Théor. Nombres Bordeaux, Sér. II 1, 163-187 (1989)].
Reviewer: J.-P.Allouche
MSC:
11A63 | Radix representation; digital problems |
68Q42 | Grammars and rewriting systems |
11A99 | Elementary number theory |
11-02 | Research exposition (monographs, survey articles) pertaining to number theory |
11E99 | Forms and linear algebraic groups |
11T55 | Arithmetic theory of polynomial rings over finite fields |
11J81 | Transcendence (general theory) |
Keywords:
Diagonals of power series; survey; finite automata; algebraic formal power series; transcendental numbers; Hadamard productCitations:
Zbl 0689.00005Online Encyclopedia of Integer Sequences:
Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.a(n) = binomial(2n, n)^2.
Apery (Apéry) numbers: Sum_{k=0..n} (binomial(n,k)*binomial(n+k,k))^2.
Zero-one version of Golay-Rudin-Shapiro sequence (or word).
Fixed point of morphism 0 -> 01, 1 -> 02, 2 -> 31, 3 -> 32.