# Automata, algebraicity and distribution of sequences of powers

• [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)
• Volume: 51, Issue: 3, page 687-705
• ISSN: 0373-0956

top

## Abstract

top
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.

## How to cite

top

Allouche, Jean-Paul, et al. "Automata, algebraicity and distribution of sequences of powers." Annales de l’institut Fourier 51.3 (2001): 687-705. <http://eudml.org/doc/115926>.

@article{Allouche2001,
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)=\sum \_\{n = n\_0\}^\{\infty \}f\_nx^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$\lbrace f\rbrace :=\sum \_\{n=0\}^\{\infty \}f\_nx^n\in 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&lt;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):=\sum \_\{m=0\}^\infty f(x)^my^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.},
affiliation = {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); Osaka City University, Department of Mathematics, Osaka 558-8585 (Japon)},
author = {Allouche, Jean-Paul, Deshouillers, Jean-Marc, Kamae, Teturo, Koyanagi, Tadahiro},
journal = {Annales de l’institut Fourier},
keywords = {distribution of powers; algebraic formal Laurent series; automatic sequences},
language = {eng},
number = {3},
pages = {687-705},
publisher = {Association des Annales de l'Institut Fourier},
title = {Automata, algebraicity and distribution of sequences of powers},
url = {http://eudml.org/doc/115926},
volume = {51},
year = {2001},
}

TY - JOUR
AU - Allouche, Jean-Paul
AU - Deshouillers, Jean-Marc
AU - Kamae, Teturo
TI - Automata, algebraicity and distribution of sequences of powers
JO - Annales de l’institut Fourier
PY - 2001
PB - Association des Annales de l'Institut Fourier
VL - 51
IS - 3
SP - 687
EP - 705
AB - 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)=\sum _{n = n_0}^{\infty }f_nx^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$\lbrace f\rbrace :=\sum _{n=0}^{\infty }f_nx^n\in 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&lt;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):=\sum _{m=0}^\infty f(x)^my^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.
LA - eng
KW - distribution of powers; algebraic formal Laurent series; automatic sequences
UR - http://eudml.org/doc/115926
ER -

## References

top
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) 30 (1997), 285-331 Zbl0870.68105MR1432196
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 88--02 (1988), 37-47, Publications Mathématiques d'Orsay Zbl0713.11045
3. G. Christol, Ensembles presque périodiques $k$-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141-145 Zbl0402.68044MR535129
4. G. Christol, T. Kamae, M. Mendès, France, G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401-419 Zbl0472.10035MR614317
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 54 (1980), 437-439 Zbl0466.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 Exposé no 5 (1980), 1-22 Zbl0435.10023
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) Vol. 2 (1981), 69-72, Academic Press, London-New York Zbl0466.10031
8. F. Von Haeseler, A. Petersen, Automaticity of rational functions, Beiträge zur Algebra und Geometrie 39 (1998), 219-229 Zbl0895.68093MR1614440
9. F. Von Haeseler, On algebraic properties of sequences generated by substitutions over a group, (1996)
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 288 (1979), 997-999 Zbl0422.10029MR540376
11. B. de Mathan, Approximations diophantiennes dans un corps local, Bull. Soc. Math. France, Suppl., Mém. 21 (1970), 1-93 Zbl0221.10037MR274396
12. O. Salon, Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris, Série I 305 (1987), 501-504 Zbl0628.10007MR916320
13. O. Salon, Propriétés arithmétiques des automates multidimensionnels, (1989)

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.