Finite automata and algebraic extensions of function fields

2004/10/17 by Kiran S. Kedlaya, Kedlaya, Kiran S.
Computer Science · Mathematics · #13P05 #Algebraic Geometry and Number Theory #Coding theory and cryptography #Commutative Algebra (math.AC) #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #math.AC #math.NT #msc:13P05

paper · pdf · doi:10.48550/arxiv.math/0410375

40 pages; expanded version of math.AC/0110089; v2: refereed version, includes minor edits

openalex publication_date 2004/10/17 · arxiv created 2005/05/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an automata-theoretic description of the algebraic closure of the rational function field F_q(t) over a finite field, generalizing a result of Christol. The description takes place within the Hahn-Mal'cev-Neumann field of "generalized power series" over F_q. Our approach includes a characterization of well-ordered sets of rational numbers whose base p expansions are generated by a finite automaton, as well as 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.

Related

• Algebraic Generalized Power Series and Automata
• A refinement of Christol's theorem for algebraic power series
• Expansions in completions of global function fields
• A note on Christol's theorem
• On the algebraicity of generalized power series