EUVIMEDEUVIMED entdecken
Crossref

Algebraic power series and their automatic complexity modulo prime powers

Eric Rowland, Reem Yassawi

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →