Algebraic power series and their automatic complexity modulo prime powers
Mathematics of Computation · 25.06.2026
DOI: 10.1090/mcom/4227 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Computation, online erschienen am 25.06.2026. Verfasst von Eric Rowland und 1 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Gefördert von: Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
Christol and, independently, Denef and Lipshitz showed that an algebraic sequence of p p -adic integers (or integers) is p p -automatic when reduced modulo p α p^\alpha . Previously, the best known bound on the minimal automaton size for such a sequence was doubly exponential in α \alpha . Under mild conditions, we improve this to a bound whose dominant factor is p α 3 h d / 3 p^{\alpha ^3 h d / 3} , where h h and d d are the height and degree of the minimal annihilating polynomial modulo p 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.
Förderung
- Engineering and Physical Sciences Research Council
Zitieren
APA
Rowland, E., & Yassawi, R. (2026). Algebraic power series and their automatic complexity modulo prime powers. Mathematics of Computation. https://doi.org/10.1090/mcom/4227
Vancouver
Rowland E, Yassawi R. Algebraic power series and their automatic complexity modulo prime powers. Mathematics of Computation. 2026. doi:10.1090/mcom/4227
BibTeX
@article{Rowland2026,
author = {Rowland, Eric and Yassawi, Reem},
title = {Algebraic power series and their automatic complexity modulo prime powers},
journal = {Mathematics of Computation},
year = {2026},
doi = {10.1090/mcom/4227}
}
EUVIMED