betaFeedback

WorksMathematics

Linear-exponent bounds for the automatic complexity of rational diagonals modulo prime powers

Abstract

Let pp be a prime and let GG be the diagonal of N/QN/Q in mm variables over the pp-adic integers, with Q(0)Q(0) a unit. We prove that the pp-kernel of the coefficients of GG modulo pαp^α has size Kα(G)≤p(∣J∣+1)α−1+(pα−1)/(p−1)K_α(G)\le p^{(|J|+1)α-1}+(p^α-1)/(p-1), where JJ is an explicit finite support set determined by the Newton polytopes of NN and QQ, and ∣J∣≤∏i(hi+1)|J|\le\prod_i(h_i+1) for hi=max⁡(°ziN,°ziQ)h_i=\max(°_{z_i}N,°_{z_i}Q). Thus the minimal automaton has pO(α)p^{O(α)} states for fixed input and prime. The general upper bounds of Rowland and Yassawi have exponents that are cubic in αα for Furstenberg series and of order αm+1α^{m+1} for diagonals in mm variables. The proof combines a δδ-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 FF of bx2y2+(1+ax+dx2)y+cx2bx^2y^2+(1+ax+dx^2)y+cx^2 with odd a,b,c,d∈Z2a,b,c,d\in\mathbb{Z}_2, we prove Kα(F)≥9⋅8α/(64α−32)K_α(F)\ge9\cdot8^α/(64α-32) and lim⁡α→∞α−1log⁡2Kα(F)=3\lim_{α\to\infty}α^{-1}\log_2K_α(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 x2y2+(1+x+x2)y+x2x^2y^2+(1+x+x^2)y+x^2 has exactly 2α+1+α+12^{α+1}+α+1 states, resolving their orbit-size conjecture.

Introduction

Automatic complexity modulo prime powers

Let pp be a prime. By Christol’s theorem [8, 10] (see Theorem 1, §5 of [10]), a power series over Fp\mathbb{F}_p is algebraic over Fp(x)\mathbb{F}_p(x) if and only if its coefficient sequence is pp-automatic. Christol [9] and Denef and Lipshitz [11] (see also Theorem 1.2 of [18]) extended the automaticity statement to Zp\mathbb{Z}_p: if F=∑n≥0a(n)xn∈Zp[[x]]F=\sum_{n\ge0}a(n)x^n\in\mathbb{Z}_p[[x]] is algebraic, then (a(n) mod pα)n≥0(a(n)\bmod p^\alpha)_{n\ge0} is pp-automatic for every α≥1\alpha\ge1; more generally, the same holds for diagonals of rational functions N/QN/Q with Q(0)∈Zp×Q(0)\in\mathbb{Z}_p^\times [11, 18] (see Theorem 2.1 of [18]). Rowland and Yassawi [18] made the construction of such automata for diagonals explicit and used it to prove many congruences.

Throughout, automata read the base-pp digits of nn starting with the least significant digit. The minimal automaton of a sequence is the smallest automaton generating it that is insensitive to leading zeros; by Eilenberg’s theorem its number of states equals the cardinality of the pp-kernel

ker⁡p(a)={(a(pkn+v))n≥0:k≥0, 0≤v<pk}\operatorname{ker}_p(a)=\{(a(p^k n+v))_{n\ge0}: k\ge0,\ 0\le v<p^k\}

(see [19 §2], [12], [2 Ch. 6]). For G=∑g(n)xn∈Zp[[x]]G=\sum g(n)x^n\in\mathbb{Z}_p[[x]] we write

Kα(G):=∣ker⁡p((g(n) mod pα)n≥0)∣.K_\alpha(G):=\left|\operatorname{ker}_p\left((g(n)\bmod p^\alpha)_{n\ge0}\right)\right|.

For α=1\alpha=1 the size of the minimal automaton is well understood: Bridy [7] and Rowland, Stipulanti and Yassawi [17] proved bounds of the form (1+o(1))phd(1+o(1))p^{hd} for algebraic series over Fp\mathbb{F}_p of height hh and degree dd, and Adamczewski, Bostan and Caruso [1] treated multivariate algebraic series and diagonals. For α≥2\alpha\ge2, the constructions of Denef and Lipshitz lead to bounds that are doubly exponential in α\alpha [19 §1]. Rowland and Yassawi [19] recently replaced these by polynomial exponents. For the Furstenberg series FF of P∈Zp[x,y]P \in\mathbb{Z}_p[x,y] with h=deg⁡x(P mod p)=deg⁡xPh=\deg_x(P \bmod p)=\deg_x P and d=deg⁡y(P mod p)=deg⁡yPd=\deg_y(P \bmod p)=\deg_y P, for nonzero FF their Theorem 1 bounds the minimal automaton by

(1+o(1))pα6α(α+1)((2hd−1)α+hd+1)(1+o(1))p^{\frac{\alpha}{6}\alpha(\alpha+1)((2hd-1)\alpha+hd+1)}

and their Theorem 3 bounds it for the diagonal of P/QP/Q in m≥2m\geq2 variables, with each reduced coordinate height hi≥1h_i\geq1, by pMp^M with M=∑k=0α−1∏i=1m((k+1)hi+1)M=\sum_{k=0}^{\alpha-1}\prod_{i=1}^{m}((k+1)h_i+1), whose dominant term is αm+1h1⋯hm/(m+1)\alpha^{m+1}h_1\cdots h_m/(m+1). For m=2m=2 their Theorem 56 improves the leading term to α(α+1)(2α+1)hd/6\alpha(\alpha+1)(2\alpha+1)hd/6.

Main result

Let m≥1m\geq1, z=(z1,…,zm)z=(z_1,\ldots,z_m), 1=(1,…,1)\mathbf{1}=(1,\ldots,1), and let

Diag⁡(∑u∈Z≥0msuzu)=∑n≥0sn1xn.\operatorname{Diag}\left(\sum_{u\in\mathbb{Z}_{\geq0}^{m}}s_u z^u\right)=\sum_{n\geq0}s_{n\mathbf{1}}x^n.

Let N,Q∈Zp[z]N,Q\in\mathbb{Z}_p[z] with Q(0)∈Zp×Q(0)\in\mathbb{Z}_p^\times. Write Δ(Q)=conv⁡(supp⁡Q)\Delta(Q)=\operatorname{conv}(\operatorname{supp}Q) and K(N)=conv⁡(supp⁡N)K(N)=\operatorname{conv}(\operatorname{supp}N) for the Newton polytopes (with K(0)=∅K(0)=\varnothing), and let hi=max⁡(deg⁡ziN,deg⁡ziQ)h_i=\max(\deg_{z_i}N,\deg_{z_i}Q), with deg⁡zi0=−∞\deg_{z_i}0=-\infty.

Definition 1.1. The support set of (N,Q)(N,Q) at the prime pp is

J=Jp(N,Q)={u∈Z≥0m:u+η1∈(1−ε)Δ(Q)+εK(N) for some η∈[0,1), ε∈(0,1/p]}.J=J_p(N,Q)=\left\{u\in\mathbb{Z}_{\geq0}^{m}:u+\eta\mathbf{1}\in(1-\varepsilon)\Delta(Q)+\varepsilon K(N)\text{ for some }\eta\in[0,1),\ \varepsilon\in(0,1/p]\right\}.

The set JJ is contained in the box ∏i{0,1,…,hi}\prod_i\{0,1,\ldots,h_i\} (Lemma 4.1), so ∣J∣≤D:=∏i(hi+1)|J|\leq D:=\prod_i(h_i+1).

Theorem 1.2. Let pp be a prime, m≥1m\geq1, and N,Q∈Zp[z1,…,zm]N,Q\in\mathbb{Z}_p[z_1,\ldots,z_m] with Q(0)∈Zp×Q(0)\in\mathbb{Z}_p^\times. Let G=Diag⁡(N/Q)G=\operatorname{Diag}(N/Q). Then for every α≥1\alpha\geq1

Kα(G)≤p(∣J∣+1)α−1+pα−1p−1≤p(D+1)α−1+pα−1p−1.K_\alpha(G)\leq p^{(|J|+1)\alpha-1}+\frac{p^\alpha-1}{p-1}\leq p^{(D+1)\alpha-1}+\frac{p^\alpha-1}{p-1}.

In particular log⁡pKα(G)≤(∣J∣+1)α+O(1)\log_p K_\alpha(G)\leq(|J|+1)\alpha+O(1) for fixed NN, QQ, mm and pp. No Hasse–Witt invertibility, smoothness or ordinarity hypothesis is used. The proof (Sections 2–5) also produces an explicit automaton with at most this many states (Corollary 5.9): its states are pairs consisting of a window of α−1\alpha-1 digits and a compatible history, and its transitions are given by explicit matrices over Zp\mathbb{Z}_p, reduced modulo pαp^\alpha.

Consequences

Furstenberg’s theorem, in the integral form of Denef and Lipshitz [11 Lemma 6.3] (see [19 Theorem 4]), represents the Furstenberg series of PP as Diag⁡(NF/QF)\operatorname{Diag}(N_F/Q_F) with QF=P(xy,y)/yQ_F=P(xy,y)/y and NF=y∂yP(xy,y)N_F=y\partial_yP(xy,y). Applying Theorem 1.2 to this representation gives:

Corollary 1.3. Let P∈Zp[x,y]P\in\mathbb{Z}_p[x,y] with P(0,0)=0P(0,0)=0 and ∂yP(0,0)∈Zp×\partial_yP(0,0)\in\mathbb{Z}_p^\times, deg⁡xP≤h\deg_xP\leq h and deg⁡yP≤d\deg_yP\leq d, and let FF be its Furstenberg series. Then for every α≥1\alpha\geq1

Kα(F)≤p((h+1)(h+d+1)+1)α−1+pα−1p−1.K_\alpha(F)\leq p^{((h+1)(h+d+1)+1)\alpha-1}+\frac{p^\alpha-1}{p-1}.

For special supports the set JJ is much smaller than the box. For the polynomial x2y2+(1+x+x2)y+x2x^2y^2+(1+x+x^2)y+x^2 from [19 Appendix] and its four-parameter deformation, studied in the appendix below, we find ∣J∣≤5|J|\leq5:

References

  1. [1]B. Adamczewski, A. Bostan, X. Caruso, A sharper multivariate Christol’s theorem with applications to diagonals and Hadamard products, arXiv:2306.02640 (2023).arxiv.org/abs/2306.02640
  2. [2]J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.
  3. [3]P.-G. Becker, k-regular power series and Mahler-type functional equations, J. Number Theory 49 (1994), 269–286.DOI
  4. [4]J. P. Bell, M. Coons, E. Rowland, The rational-transcendental dichotomy of Mahler functions, J. Integer Seq. 16 (2013), Article 13.2.10.arxiv.org/abs/1210.2070
  5. [5]F. Beukers, p-linear schemes for sequences modulo p^r, Indag. Math. 35 (2024), 698–707; doi:10.1016/j.indag.2023.12.003; arXiv:2211.15240.DOI
  6. [6]F. Beukers, M. Vlasenko, Dwork crystals II, Int. Math. Res. Not. IMRN 2021, no. 12, 8807–8844; doi:10.1093/imrn/rnaa119; arXiv:1903.11155.DOI
  7. [7]A. Bridy, Automatic sequences and curves over finite fields, Algebra Number Theory 11 (2017), 685–712; doi:10.2140/ant.2017.11.685; arXiv:1604.08241.DOI
  8. [8]G. Christol, Ensembles presque périodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141–145.DOI
  9. [9]G. Christol, Fonctions et éléments algébriques, Pacific J. Math. 125 (1986), 1–37.DOI
  10. [10]G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401–419.DOI
  11. [11]J. Denef, L. Lipschitz, Algebraic power series and diagonals, J. Number Theory 26 (1987), 46–67.DOI
  12. [12]S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, 1974.
  13. [13]J. A. Henningsen, A. Straub, Generalized Lucas congruences and linear p-schemes, Adv. Appl. Math. 141 (2022), Article 102409; doi:10.1016/j.aam.2022.102409; arXiv:2111.08641.DOI
  14. [14]N. Kohen, A linear representation for constant term sequences mod p^a with applications to uniform recurrence, J. Integer Seq. 29 (2026), Article 26.4.2.arxiv.org/abs/2503.21988
  15. [15]L. Lipschitz, The diagonal of a D-finite power series is D-finite, J. Algebra 113 (1988), 373–378.
  16. [16]Ku. Nishioka, Mahler Functions and Transcendence, Lecture Notes in Math. 1631, Springer, 1996.
  17. [17]E. Rowland, M. Stipulanti, R. Yassawi, An elementary proof of Bridy’s theorem, Finite Fields Appl. 105 (2025), Article 102621; doi:10.1016/j.ffa.2025.102621; arXiv:2308.10977.DOI
  18. [18]E. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, J. Théor. Nombres Bordeaux 27 (2015), 245–288.
  19. [19]E. Rowland, R. Yassawi, Algebraic power series and their automatic complexity modulo prime powers, Math. Comp., published online 25 June 2026, doi:10.1090/mcom/4227; arXiv:2408.00750v4.DOI
  20. [20]A. Straub, On congruence schemes for constant terms and their applications, Res. Number Theory 8 (2022), Article 42; doi:10.1007/s40993-022-00337-6; arXiv:2205.09902.DOI
  21. [21]A. Straub, Gessel–Lucas congruences for sporadic sequences, Monatsh. Math. 203 (2024), 883–898; doi:10.1007/s00605-023-01894-3; arXiv:2301.12248.DOI
  22. [22]M. Vlasenko, Higher Hasse–Witt matrices, Indag. Math. 29 (2018), 1411–1424; arXiv:1605.06440.DOI

Paper details

vlnc:W_ywbsae58
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, ChatGPT, Codex

View statement
Looking for related papers…
Contents