Linear-exponent bounds for the automatic complexity of rational diagonals modulo prime powers
Abstract
Let $p$ be a prime and let $G$ be the diagonal of $N/Q$ in $m$ variables over the $p$-adic integers, with $Q(0)$ a unit. We prove that the $p$-kernel of the coefficients of $G$ modulo $p^\alpha$ has size $K_\alpha(G)\le p^{(|J|+1)\alpha-1}+(p^\alpha-1)/(p-1)$, where $J$ is an explicit finite support set determined by the Newton polytopes of $N$ and $Q$, and $|J|\le\prod_i(h_i+1)$ for $h_i=\max(\deg_{z_i}N,\deg_{z_i}Q)$. Thus the minimal automaton has $p^{O(\alpha)}$ states for fixed input and prime. The general upper bounds of Rowland and Yassawi have exponents that are cubic in $\alpha$ for Furstenberg series and of order $\alpha^{m+1}$ for diagonals in $m$ variables. The proof combines a $\delta$-decomposition with synchronous Cartier sections and a count of compatible histories; it requires no smoothness or ordinarity assumption. We give explicit transitions and derive bounds for Furstenberg series. For the Furstenberg series $F$ of $bx^2y^2+(1+ax+dx^2)y+cx^2$ with odd $a,b,c,d\in\mathbb{Z}_2$, we prove $K_\alpha(F)\ge9\cdot8^\alpha/(64\alpha-32)$ and $\lim_{\alpha\to\infty}\alpha^{-1}\log_2K_\alpha(F)=3$. This exponent result rests on primitive reachability, parameter-independent normalized window frames, and an overlap estimate certified in a finite quotient of a rational Cartier lattice. An appendix also proves that the zero orbit in the Rowland-Yassawi automaton for $x^2y^2+(1+x+x^2)y+x^2$ has exactly $2^{\alpha+1}+\alpha+1$ states, resolving their orbit-size conjecture.