Algebraic power series and their automatic complexity II: modulo prime powers

2024/08/01 by Rowland, Eric, Yassawi, Reem
#FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.2408.00750

Abstract

Christol and, independently, Denef and Lipshitz showed that an algebraic sequence of p-adic integers (or integers) is p-automatic when reduced modulo p^α. Previously, the best known bound on the minimal automaton size for such a sequence was doubly exponential in α. We improve this bound to the order of p^{α3 h d}, where h and d are the height and degree of the minimal annihilating polynomial modulo p. We achieve this bound by showing that all states in the automaton are naturally represented in a new numeration system. This significantly restricts the set of possible states. Since our approach embeds algebraic sequences as diagonals of rational functions, we also obtain bounds more generally for diagonals of multivariate rational functions.

Related

• Automatic Bounds on Constant Term Sequences Modulo Primes
• A refinement of Christol's theorem for algebraic power series
• Algebraic Generalized Power Series and Automata
• A note on Christol's theorem
• Additive Complexity and the Roots of Polynomials Over Number Fields and p-adic Fields