Algebraic power series and their automatic complexity modulo prime powers

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^{\hat{I}}\pm$. Previously, the best known bound on the minimal automaton size for such a sequence was doubly exponential in $\hat{I}\pm$. Under mild conditions, we improve this to a bound whose dominant factor is $p^{\hat{I}{\pm }^{3}hd/3}$, 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.

50 pages, 1 figure, 2 tables; publication version