Finite automata and algebraic extensions of function fields
Journal de théorie des nombres de Bordeaux, Volume 18 (2006) no. 2, p. 379-420

We give an automata-theoretic description of the algebraic closure of the rational function field 𝔽 q (t) 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.

On donne une description, dans le langage des automates finis, de la clôture algébrique du corps des fonctions rationnelles 𝔽 q (t) 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.

@article{JTNB_2006__18_2_379_0,
     author = {Kedlaya, Kiran S.},
     title = {Finite automata and algebraic extensions of function fields},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux 1},
     volume = {18},
     number = {2},
     year = {2006},
     pages = {379-420},
     doi = {10.5802/jtnb.551},
     mrnumber = {2289431},
     zbl = {05135396},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2006__18_2_379_0}
}
Kedlaya, Kiran S. Finite automata and algebraic extensions of function fields. Journal de théorie des nombres de Bordeaux, Volume 18 (2006) no. 2, pp. 379-420. doi : 10.5802/jtnb.551. http://www.numdam.org/item/JTNB_2006__18_2_379_0/

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

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

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

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

[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 614317 | Zbl 0472.10035

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

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

[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 1196509 | Zbl 0793.11015

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

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

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

[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 306057 | Zbl 0244.06002

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

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

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

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

[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 939116 | Zbl 0612.12018