Automata, algebraicity and distribution of sequences of powers

Allouche, Jean-Paul; Deshouillers, Jean-Marc; Kamae, Teturo; Koyanagi, Tadahiro

Annales de l'Institut Fourier, Tome 51 (2001) no. 3, pp. 687-705.

Nous étudions la répartition de ${\left(\left\{f^m\right\}\right)}_{m\ge 0}$, pour $f$ dans $K\left(\right(x\left)\right)$, le corps des séries formelles de Laurent sur un corps fini $K$ de caractéristique $p$, où, si

$$f\left(x\right)=\sum _{n=n_0}^{\infty }{f}_n{x}^n\in K\left(\left(x\right)\right)$$

avec $n_0\in 𝐙$ et $\forall n\ge n_0,f_n\in K$, l’on note

$$\left\{f\right\}:=\sum _{n=0}^{\infty }{f}_n{x}^n\in K\left[\left[x\right]\right].$$

Nous donnons d’abord une nouvelle preuve d’un résultat dû à de Mathan : la répartition générique de ${\left(\left\{f^m\right\}\right)}_{m\ge 0}$ pour les $f$ pour lesquelles il existe $n<0$ avec $f_n\ne 0$, n’est pas la mesure uniforme sur $K\left[\right[x\left]\right]$, mais elle lui est équivalente. La situation est différente dans le cas $f\in K\left[\right[x\left]\right]$, avec $f_0\ne 0$ et $f\ne f_0$ : la mesure de répartition est continue mais de support petit. Nous prouvons que dans ce cas la répartition pour $f^{-1}$ est identique à celle pour $f_0^{-2}f$. Nous étudions ensuite la répartition de ${\left(\left\{f^m\right\}\right)}_{m\ge 0}$ pour $f$ algébrique sur $K\left(x\right)$ en construisant un automate fini qui engendre les coefficients de la série double (algébrique sur $K(x,y)$)

$$F(x,y):=\sum _{m=0}^{\infty }f{\left(x\right)}^m{y}^m$$

(un tel automate existe d’après un théorème de Salon qui étend au cas multidimensionnel le théorème de Christol, Kamae, Mendès France et Rauzy). Nous généralisons ainsi des résultats de Houndonougbo et de Deshouillers, et renforçons des résultats d’Allouche et Deshouillers.

Let $K$ be a finite field of characteristic $p$. Let $K\left(\right(x\left)\right)$ be the field of formal Laurent series $f\left(x\right)$ in $x$ with coefficients in $K$. That is,

$$f\left(x\right)=\sum _{n=n_0}^{\infty }{f}_n{x}^n$$

with $n_0\in 𝐙$ and $f_n\in K(n=n_0,n_0+1,\cdots )$. We discuss the distribution of ${\left(\left\{f^m\right\}\right)}_{m=0,1,2,\cdots }$ for $f\in K\left(\right(x\left)\right)$, where

$$\left\{f\right\}:=\sum _{n=0}^{\infty }{f}_n{x}^n\in K\left[\left[x\right]\right]$$

denotes the nonnegative part of $f\in K\left(\right(x\left)\right)$. This is a little different from the real number case where the fractional part that excludes constant term (digit of order 0) is considered. We give an alternative proof of a result by De Mathan obtaining the generic distribution for $f$ with $f_n\ne 0$ for some $n<0$. This distribution is not the uniform measure on $K\left[\right[x\left]\right]$, but is equivalent to it. We have a different situation for $f\in K\left[\right[x\left]\right]$, where if $f_0\ne 0$ and $f\ne f_0$, then the distribution for $f$ is continuous but has a small support. We prove in this case, that the distribution for $f^{-1}$ is identical with the distribution for $f_0^{-2}f$. Christol, Kamae, Mendès France and Rauzy proved that the algebraicity of $f\left(x\right)\in K\left(\right(x\left)\right)$ over $K\left(x\right)$ is equivalent to the $p$-automaticity of the sequence $\left(f_n\right)$. This result was generalized to the multidimensional case by Salon. Hence, if the Laurent series $f\left(x\right)\in K\left(\right(x\left)\right)$ is algebraic over $K\left(x\right)$, then

$$F(x,y):=\sum _{m=0}^{\infty }f{\left(x\right)}^m{y}^m$$

is $2$-dimensionally $p$-automatic, since it is algebraic over the field $K(x,y)$. We construct a finite automaton recognizing the sequence of coefficients of this double series $F(x,y)$ to discuss the distribution of ${\left(\left\{f^m\right\}\right)}_{m\ge 0}$. Thus, we generalize results by Houndonougbo and Deshouillers, and strengthen results by Allouche and Deshouillers.

[1] J.-P. Allouche; E. Cateland; W. J. Gilbert; H.-O. Peitgen; J. Shallit; G. Skordev Automatic maps on semiring with digits, Theory Comput. Syst. (Math. Systems Theory), Volume 30 (1997), pp. 285-331 | MR | Zbl

[2] J.-P. Allouche; J.-M. Deshouillers Répartition de la suite des puissances d'une série formelle algébrique, Colloque de Théorie Analytique des Nombres Jean Coquet, Journées SMF-CNRS, CIRM Luminy 1985, Volume 88--02 (1988), pp. 37-47 | Zbl

[3] G. Christol Ensembles presque périodiques $k$-reconnaissables, Theoret. Comput. Sci., Volume 9 (1979), pp. 141-145 | MR | Zbl

[4] G. Christol; T. Kamae; M. Mendès; France; G. Rauzy Suites algébriques, automates et substitutions, Bull. Soc. Math. France, Volume 108 (1980), pp. 401-419 | Numdam | MR | Zbl

[5] J.-M. Deshouillers Sur la répartition modulo $1$ des puissances d'un élément de $F_q\left(\left(X\right)\right)$, Proc. Queen's Number Theory Conf. 1979 (Queen's Pap. Pure Appl. Math.), Volume 54 (1980), pp. 437-439 | Zbl

[6] J.-M. Deshouillers La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini, Sém. de Théorie des Nombres de Bordeaux 1979/1980, Volume Exposé no 5 (1980), pp. 1-22 | Zbl

[7] J.-M. Deshouillers La répartition modulo $1$ des puissances d'un élément dans $F_q\left(\left(X\right)\right)$, Recent progress in analytic number theory, (Durham, 1979), Volume Vol. 2 (1981), pp. 69-72 | Zbl

[8] F. Von Haeseler; A. Petersen Automaticity of rational functions, Beiträge zur Algebra und Geometrie, Volume 39 (1998), pp. 219-229 | MR | Zbl

[9] F. Von Haeseler On algebraic properties of sequences generated by substitutions over a group (1996) (preprint of Bremen University)

[10] V. Houndonougbo Mesure de répartition d'une suite ${\left({\theta }^n\right)}_n\in {𝐍}^{*}$ dans un corps de séries formelles sur un corps fini, C. R. Acad. Sci. Paris, Série A, Volume 288 (1979), pp. 997-999 | MR | Zbl

[11] B. de Mathan Approximations diophantiennes dans un corps local, Bull. Soc. Math. France, Suppl., Mém., Volume 21 (1970), pp. 1-93 | Numdam | MR | Zbl

[12] O. Salon Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris, Série I, Volume 305 (1987), pp. 501-504 | MR | Zbl

[13] O. Salon Propriétés arithmétiques des automates multidimensionnels (1989) (Thèse, Université Bordeaux I)