Automata, algebraicity and distribution of sequences of powers

[Automates, algébricité et répartition de suites de puissances]

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

Annales de l'Institut Fourier, Tome 51 (2001), p. 687-705 / Harvested from Numdam

Résumé

Nous étudions la répartition de $(\lbrace f^m\rbrace )_{m \ge 0}$, pour $f$ dans $K((x))$, le corps des séries formelles de Laurent sur un corps fini $K$ de caractéristique $p$, où, si f(x)=∑ n=n 0 ∞ f n x n ∈K((x)) avec $n_0 \in {\bf Z}$ et $\forall n \ge n_0, \ f_n \in K$, l’on note {f}:=∑ n=0 ∞ f n x n ∈K[[x]]. Nous donnons d’abord une nouvelle preuve d’un résultat dû à de Mathan : la répartition générique de $(\lbrace f^m\rbrace )_{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[[x]]$, mais elle lui est équivalente. La situation est différente dans le cas $f\in K[[x]]$, 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 $(\lbrace f^m\rbrace )_{m \ge 0}$ pour $f$ algébrique sur $K(x)$ en construisant un automate fini qui engendre les coefficients de la série double (algébrique sur $K(x,y)$) F(x,y):=∑ m=0 ∞ f(x) 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.

Abstract

Let $K$ be a finite field of characteristic $p$. Let $K((x))$ be the field of formal Laurent series $f(x)$ in $x$ with coefficients in $K$. That is, f(x)=∑ n=n 0 ∞ f n x n with $n_0\in {\bf Z}$ and $f_n\in K (n=n_0,n_0+1,\cdots )$. We discuss the distribution of $(\lbrace f^m\rbrace )_{m=0,1,2,\cdots }$ for $f\in K((x))$, where {f}:=∑ n=0 ∞ f n x n ∈K[[x]] denotes the nonnegative part of $f\in K((x))$. 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[[x]]$, but is equivalent to it. We have a different situation for $f\in K[[x]]$, 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(x)\in K((x))$ over $K(x)$ is equivalent to the $p$-automaticity of the sequence $(f_n)$. This result was generalized to the multidimensional case by Salon. Hence, if the Laurent series $f(x)\in K((x))$ is algebraic over $K(x)$, then F(x,y):=∑ m=0 ∞ f(x) 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 $(\lbrace f^m\rbrace )_{m\ge 0}$. Thus, we generalize results by Houndonougbo and Deshouillers, and strengthen results by Allouche and Deshouillers.

Détail

Publié le : 2001-01-01

Zbl 1068.11048

DOI : https://doi.org/10.5802/aif.1833
Classification:  11K41,  11B85,  68R15
Mots clés: répartition de puissances, séries formelles de Laurent algébriques, suites automatiques

Bibliographie

[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), Tome 30 (1997), pp. 285-331 | MR 1432196 | Zbl 0870.68105

[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, Publications Mathématiques d'Orsay, Tome 88--02 (1988), pp. 37-47 | Zbl 0713.11045

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

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

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

[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, Tome Exposé no 5 (1980), pp. 1-22 | Zbl 0435.10023

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

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

[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 $(\theta^n)_n\in\mathbf N^*$ dans un corps de séries formelles sur un corps fini, C. R. Acad. Sci. Paris, Série A, Tome 288 (1979), pp. 997-999 | MR 540376 | Zbl 0422.10029

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

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

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