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³

¹ CNRS, LRI, Bâtiment 490, 91405 Orsay Cedex (France)
² Université de Bordeaux I, Laboratoire de Mathématiques, 351 cours de la Libération, 33405 Talence Cedex (France)
³ Osaka City University, Department of Mathematics, Osaka 558-8585 (Japon)

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

Abstract (VO)

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.

Résumé

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.

Détail

DOI : 10.5802/aif.1833

Classification : 11K41, 11B85, 68R15
Keywords: distribution of powers, algebraic formal Laurent series, automatic sequences
Mots-clés : répartition de puissances, séries formelles de Laurent algébriques, suites automatiques