Finite automata and algebraic extensions of function fields
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 (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.

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.

DOI : 10.5802/jtnb.551
Kedlaya, Kiran S. 1

1 Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139, USA
@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},
     pages = {379--420},
     publisher = {Universit\'e Bordeaux 1},
     volume = {18},
     number = {2},
     year = {2006},
     doi = {10.5802/jtnb.551},
     zbl = {05135396},
     mrnumber = {2289431},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.551/}
}
TY  - JOUR
AU  - Kedlaya, Kiran S.
TI  - Finite automata and algebraic extensions of function fields
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2006
SP  - 379
EP  - 420
VL  - 18
IS  - 2
PB  - Université Bordeaux 1
UR  - http://www.numdam.org/articles/10.5802/jtnb.551/
DO  - 10.5802/jtnb.551
LA  - en
ID  - JTNB_2006__18_2_379_0
ER  - 
%0 Journal Article
%A Kedlaya, Kiran S.
%T Finite automata and algebraic extensions of function fields
%J Journal de théorie des nombres de Bordeaux
%D 2006
%P 379-420
%V 18
%N 2
%I Université Bordeaux 1
%U http://www.numdam.org/articles/10.5802/jtnb.551/
%R 10.5802/jtnb.551
%G en
%F 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, Tome 18 (2006) no. 2, pp. 379-420. doi : 10.5802/jtnb.551. http://www.numdam.org/articles/10.5802/jtnb.551/

[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

Cité par Sources :