Finite automata and algebraic extensions of function fields

Kedlaya, Kiran S.

Journal de théorie des nombres de Bordeaux, Tome 18 (2006) no. 2, pp. 379-420.

On donne une description, dans le langage des automates finis, de la clôture algébrique du corps des fonctions rationnelles ${𝔽}_q\left(t\right)$ sur un corps fini ${𝔽}_q$. Cette description, qui généralise un résultat de Christol, emploie le corps de Hahn-Mal’cev-Neumann des “séries formelles généralisées” sur ${𝔽}_q$. En passant, on obtient une caractérisation des ensembles bien ordonnés de nombres rationnels dont les représentations $p$-adiques sont générées par un automate fini, et on présente des techniques pour calculer dans la clôture algébrique ; ces techniques incluent une version en caractéristique non nulle de l’algorithme de Newton-Puiseux pour déterminer les développements locaux des courbes planes. On conjecture une généralisation de nos résultats au cas de plusieurs variables.

We give an automata-theoretic description of the algebraic closure of the rational function field ${𝔽}_q\left(t\right)$ over a finite field ${𝔽}_q$, generalizing a result of Christol. The description occurs within the Hahn-Mal’cev-Neumann field of “generalized power series” over ${𝔽}_q$. In passing, we obtain a characterization of well-ordered sets of rational numbers whose base $p$ expansions are generated by a finite automaton, and exhibit some techniques for computing in the algebraic closure; these include an adaptation to positive characteristic of Newton’s algorithm for finding local expansions of plane curves. We also conjecture a generalization of our results to several variables.

[1] S. Abhyankar, Two notes on formal power series. Proc. Amer. Math. Soc. 7 (1956), 903–905. | MR | Zbl

[2] J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge Univ. Press, 2003. | MR | Zbl

[3] C. Chevalley, Introduction to the Theory of Algebraic Functions of One Variable. Amer. Math. Soc., 1951. | MR | Zbl

[4] G. Christol, Ensembles presque periodiques $k$-reconnaissables. Theoret. Comput. Sci. 9 (1979), 141–145. | MR | Zbl

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

[6] P. Deligne, Intégration sur un cycle évanescent. Invent. Math. 76 (1984), 129–143. | MR | Zbl

[7] H. Furstenberg, Algebraic functions over finite fields. J. Alg. 7 (1967), 271–277. | MR | Zbl

[8] H. Hahn, Über die nichtarchimedische Größensysteme (1907). Gesammelte Abhandlungen I, Springer-Verlag, 1995.

[9] D.R. Hayes, A brief introduction to Drinfel’d modules. The Arithmetic of Function Fields (edited by D. Goss, D.R. Hayes, and M.I. Rosen), 1–32, de Gruyter, 1992. | MR | Zbl

[10] I. Kaplansky, Maximal fields with valuations. Duke Math. J. 9 (1942), 303–321. | MR | Zbl

[11] K.S. Kedlaya, The algebraic closure of the power series field in positive characteristic. Proc. Amer. Math. Soc. 129 (2001), 3461–3470. | MR | Zbl

[12] K.S. Kedlaya, Power series and $p$-adic algebraic closures. J. Number Theory 89 (2001), 324–339. | MR | Zbl

[13] K.S. Kedlaya, Algebraic generalized power series and automata. arXiv preprint math. AC/0110089, 2001.

[14] J.B. Kruskal, The theory of well-quasi-ordering: a frequently discovered concept. J. Comb. Theory Ser. A 13 (1972), 297–305. | MR | Zbl

[15] D.S. Passman, The Algebraic Structure of Group Rings. Wiley, 1977. | MR | Zbl

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

[17] O. Salon, Suites automatiques à multi-indices (with an appendix by J. Shallit). Sem. Théorie Nombres Bordeaux 4 (1986–1987), 1–27. | Zbl

[18] J.-P. Serre, Local Fields (translated by M.J. Greenberg). Springer-Verlag, 1979. | MR | Zbl

[19] H. Sharif, C.F. Woodcock, Algebraic functions over a field of positive characteristic and Hadamard products. J. London Math. Soc. 37 (1988), 395–403. | MR | Zbl