Finite automata and algebraic extensions of function fields
Kiran S. Kedlaya1
1Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139, USA
Journal de théorie des nombres de Bordeaux, Volume 18 (2006) no. 2, pp. 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.

Received:
Published online:
DOI: 10.5802/jtnb.551

Kiran S. Kedlaya  1

1 Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139, USA 
Kiran S. Kedlaya. 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
@article{JTNB_2006__18_2_379_0,
     author = {Kiran S. Kedlaya},
     title = {Finite automata and algebraic extensions of function fields},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {379--420},
     year = {2006},
     publisher = {Universit\'e Bordeaux 1},
     volume = {18},
     number = {2},
     doi = {10.5802/jtnb.551},
     mrnumber = {2289431},
     zbl = {05135396},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.551/}
}
TY  - JOUR
AU  - Kiran S. Kedlaya
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  - https://jtnb.centre-mersenne.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 Kiran S. Kedlaya
%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 https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.551/
%R 10.5802/jtnb.551
%G en
%F JTNB_2006__18_2_379_0

[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. | MR | Zbl | Numdam

[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

Cited by Sources: