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^\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^{\alpha^3 h d / 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.
From: Eric Rowland [view email]
[v1]
Thu, 1 Aug 2024 17:52:24 UTC (37 KB)
[v2]
Fri, 20 Sep 2024 18:03:12 UTC (37 KB)
[v3]
Mon, 26 Jan 2026 21:35:08 UTC (43 KB)
[v4]
Thu, 25 Jun 2026 17:28:57 UTC (44 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。