# ANNALES DE L'INSTITUT FOURIER

Automata, algebraicity and distribution of sequences of powers
Annales de l'Institut Fourier, Volume 51 (2001) no. 3, pp. 687-705.

Let $K$ be a finite field of characteristic $p$. Let $K\left(\left(x\right)\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\left(n={n}_{0},{n}_{0}+1,\cdots \right)$. We discuss the distribution of ${\left(\left\{{f}^{m}\right\}\right)}_{m=0,1,2,\cdots }$ for $f\in K\left(\left(x\right)\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(\left(x\right)\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[\left[x\right]\right]$, but is equivalent to it. We have a different situation for $f\in K\left[\left[x\right]\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(\left(x\right)\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(\left(x\right)\right)$ is algebraic over $K\left(x\right)$, then
 $F\left(x,y\right):=\sum _{m=0}^{\infty }f{\left(x\right)}^{m}{y}^{m}$
is $2$-dimensionally $p$-automatic, since it is algebraic over the field $K\left(x,y\right)$. We construct a finite automaton recognizing the sequence of coefficients of this double series $F\left(x,y\right)$ 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.

Nous étudions la répartition de ${\left(\left\{{f}^{m}\right\}\right)}_{m\ge 0}$, pour $f$ dans $K\left(\left(x\right)\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},\phantom{\rule{4pt}{0ex}}{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[\left[x\right]\right]$, mais elle lui est équivalente. La situation est différente dans le cas $f\in K\left[\left[x\right]\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\left(x,y\right)$)
 $F\left(x,y\right):=\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.

DOI: 10.5802/aif.1833
Classification: 11K41,  11B85,  68R15
Keywords: distribution of powers, algebraic formal Laurent series, automatic sequences
Allouche, Jean-Paul 1; Deshouillers, Jean-Marc 2; Kamae, Teturo 3; Koyanagi, Tadahiro 3

1 CNRS, LRI, Bâtiment 490, 91405 Orsay Cedex (France)
2 Université de Bordeaux I, Laboratoire de Mathématiques, 351 cours de la Libération, 33405 Talence Cedex (France)
3 Osaka City University, Department of Mathematics, Osaka 558-8585 (Japon)
@article{AIF_2001__51_3_687_0,
author = {Allouche, Jean-Paul and Deshouillers, Jean-Marc and Kamae, Teturo and Koyanagi, Tadahiro},
title = {Automata, algebraicity and distribution of sequences of powers},
journal = {Annales de l'Institut Fourier},
pages = {687--705},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {51},
number = {3},
year = {2001},
doi = {10.5802/aif.1833},
zbl = {1068.11048},
language = {en},
url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1833/}
}
TY  - JOUR
TI  - Automata, algebraicity and distribution of sequences of powers
JO  - Annales de l'Institut Fourier
PY  - 2001
DA  - 2001///
SP  - 687
EP  - 705
VL  - 51
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.1833/
UR  - https://zbmath.org/?q=an%3A1068.11048
UR  - https://doi.org/10.5802/aif.1833
DO  - 10.5802/aif.1833
LA  - en
ID  - AIF_2001__51_3_687_0
ER  - 
%0 Journal Article
%T Automata, algebraicity and distribution of sequences of powers
%J Annales de l'Institut Fourier
%D 2001
%P 687-705
%V 51
%N 3
%I Association des Annales de l’institut Fourier
%U https://doi.org/10.5802/aif.1833
%R 10.5802/aif.1833
%G en
%F AIF_2001__51_3_687_0
Allouche, Jean-Paul; Deshouillers, Jean-Marc; Kamae, Teturo; Koyanagi, Tadahiro. Automata, algebraicity and distribution of sequences of powers. Annales de l'Institut Fourier, Volume 51 (2001) no. 3, pp. 687-705. doi : 10.5802/aif.1833. https://aif.centre-mersenne.org/articles/10.5802/aif.1833/

[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)

Cited by Sources: