\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{psfig}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\newcommand{\N}[0]{\mathbb{N}}
\newcommand{\Z}[0]{\mathbb{Z}}
\newcommand{\F}[0]{\mathbb{F}}
\newcommand{\x}{\mathbf{x}}
\DeclareMathOperator{\constantterm}{ct}
\newcommand{\ct}[1]{\constantterm[#1]}
\DeclareMathOperator{\coefficient}{coef}
\newcommand{\coef}[2]{\coefficient_{#1}[#2]}
\DeclareMathOperator{\code}{code}

\begin{document}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}


\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\begin{center}
\vskip 1cm{\LARGE\bf A Linear Representation for Constant Term\\
Sequences mod $p^a$ with Applications\\ 
\vskip .1in
to Uniform Recurrence
}
\vskip 1cm
\large
Nadav Kohen\\
Department of Mathematics\\
Indiana University\\
Bloomington, IN 47405\\
USA\\
\href{mailto:nkohen@iu.edu}{\tt nkohen@iu.edu} \\
\end{center}

\vskip .2 in
\begin{abstract}
Many integer sequences including the Catalan numbers, Motzkin numbers,
and the Ap{\'e}ry numbers can be expressed as the constant term of $P^nQ$
for Laurent polynomials $P$ and $Q$. These are often called \emph{constant
term sequences}. In this paper, we characterize the prime powers for
which sequences of this form modulo $p^a$, and others built from these
sequences, are uniformly recurrent. For all other prime powers, we show
that the frequency of $0$ is $1$. We accomplish this by introducing a
novel linear representation of constant term sequences modulo $p^a$,
which is of independent interest.
\end{abstract}


\section{Introduction}\label{sec:intro}
Numerous famous combinatorial sequences admit descriptions of the form $s_n = \ct{P^nQ}$ where $P$ and $Q$ are integral Laurent polynomials (of possibly many variables) and ct extracts the constant term of a Laurent polynomial. For example, the Catalan numbers (OEIS \seqnum{A000108}) can be described by $C_n = \ct{(x^{-1} + 2 + x)^n(1-x)}$, the Motzkin numbers (OEIS \seqnum{A001006}) can be described by $M_n = \ct{(x^{-1} + 1 + x)^n(1-x^2)}$, and the Ap{\'e}ry numbers (OEIS \seqnum{A005259}, which were used to prove the irrationality of $\zeta(3)$) can be described by 
$$A(n) = {\rm ct} \left[{\left(\frac{(1+x)(1+y)(1+z)(1+y+z+yz+xyz)}{xyz}\right)^n} \right].$$

This paper is primarily focused on showing when sequences mod prime powers are uniformly recurrent, which can be thought of as a weaker form of periodicity:
\begin{definition} A sequence $s_n$ is called \emph{uniformly recurrent} if for every word in $s_n$ (i.e., contiguous subsequence), $w = s_is_{i+1}\cdots s_{i+\ell-1}$, there is a constant $C_w$ such that every occurrence of $w$ is followed by another occurrence of $w$ at a distance of at most $C_w$. That is, there is a $j\leq C_w$ such that $w = s_{i+j}s_{i+j+1}\cdots s_{i + j + \ell - 1}$. If for all $w$, $C_w$ is bounded by a constant multiple of the length of $w$, then we say that $s_n$ is \emph{linearly recurrent}.
\end{definition}
For background on uniform recurrence in automatic sequences, see \cite[Section~10.9]{Allouche_Shallit_Book} and \cite[Section~10.8.8]{ShallitBook}.

In \cite{rowlandzeilberger}, Rowland and Zeilberger give an algorithm for constructing a deterministic finite automaton with output (DFAO) that computes such constant term sequences modulo a prime power. In \cite{CongruenceAutomaton}, Rampersad and Shallit use these DFAOs in concert with the Walnut library \cite{walnut} to automatically prove theorems about these sequences using computers. They prove \cite[Thm.\ 10]{CongruenceAutomaton} that, under certain conditions, the sequence $T_n = \ct{(x^{-1} + 1 + x)^n}\bmod p$ is uniformly recurrent if and only if it is never $0$. They also conjecture \cite[Problem~6]{CongruenceAutomaton} that the Motzkin numbers mod $p$ are uniformly recurrent if and only if $T_n\bmod p$ is never $0$. In \cite{KohenUR}, this author showed that this conjecture is true. More generally, if $P$ is a symmetric trinomial in one variable, then $\ct{P^nQ}\bmod p$ is uniformly recurrent for every single-variable $Q$ if and only if $\ct{P^n}\bmod p$ is never $0$ (which can be checked by finite means; see Proposition~\ref{check_bound}).

In Theorem~\ref{main_power} and Corollary~\ref{combinations_power} of Section~\ref{sec:prime-powers} of this paper, we extend the results of \cite{KohenUR} to show that $\ct{P^nQ}\bmod p^a$ and every sequence built from such sequences is linearly recurrent if and only if $\ct{P^n}\bmod p$ is never $0$, and here, no constraints are put on $P$ and both polynomials may have any number of variables. Furthermore, if there exists an $n$ such that $\ct{P^n}\bmod p = 0$ then the frequency of $0$ is $1$ in every $\ct{P^nQ}\bmod p^a$ and every sequence built from such sequences. Here, the frequency of a value $c$ in a sequence $(s_n)_{n\in\N}$ is the asymptotic density of $\{n\in\N\mid s_n = c\}$.

This is accomplished by generalizing the proof method of \cite[Thm.\ 10]{CongruenceAutomaton} by using constructions from Shallit's book \emph{The Logical Approach to Automatic Sequences} \cite{ShallitBook} along with some novel constructions introduced in Sections~\ref{sec:linrep} and~\ref{sec:classify-p}. In Section~\ref{sec:linrep}, we construct a $p$-linear representation (Definition~\ref{linrepdef}) for sequences of the form $\ct{P^nQ}\bmod p$. This $p$-linear representation is in some sense equivalent to the Rowland-Zeilberger automaton, but it makes many properties of these sequences more apparent and allows us to do away with an assumption made in \cite[Thm.\ 10]{CongruenceAutomaton}. More generally, this $p$-linear representation seems to be of independent interest as it generalizes a family of Lucas congruences specified in \cite[Prop.\ 1]{KohenUR}, is amenable to efficient computation associated with constant term sequences mod $p$, and is largely independent of $Q$. This construction is generalized to constant term sequences modulo prime powers in Section~\ref{sec:prime-powers}.

\subsection{Notation and conventions}\label{sec:notation}
Throughout this paper, $P$ and $Q$ are Laurent polynomials in $r$ variables with integer coefficients, $\coef{k_1,\ldots,k_r}{Q}$ is the coefficient of $x_1^{k_1}\cdots x_r^{k_r}$, $\ct{Q}$ is the constant term of $Q$, and $\deg Q$ denotes the largest absolute value of any exponent on any single variable in $Q$ (for example, $\deg(5x^{-3}y^{-2} + 2xy^{-1}) = 3$). For a fixed $P$, we let $a^n_{k_1,\ldots,k_r}$ denote $\coef{-k_1,\ldots,-k_r}{P(x_1,\ldots,x_r)^n} = \ct{P(x_1,\ldots,x_r)^n\cdot x_1^{k_1}\cdots x_r^{k_r}}$ so that the $(r+1)$-dimensional array $a^n_{k_1,\ldots,k_r}$ forms an $(r+1)$-dimensional pyramid that generalizes Pascal's triangle (which is achieved when $P = x^{-1} + x$). To make notation less verbose, we use the bold $\x^{k_1,\ldots,k_r}$ to refer to $x_1^{k_1}\cdots x_r^{k_r}$ and when $k = (k_1,\ldots, k_r)\in \Z^r$, we simply use $\x^k$. Furthermore, for such $k$ the notation $p\mid k$ means that $p$ divides every entry of $k$. Unless otherwise specified, vectors are column vectors and $\vec{u}^{tr}$ is the transpose of $\vec{u}$ (which is a row if $\vec{u}$ is a column).

If $\Sigma$ is a set, $\Sigma^*$ denotes the set of words (i.e., strings) of any length whose characters are from $\Sigma$ (including the empty word). Let $\vert w\vert$ denote the length of a word $w\in\Sigma^*$. If $n$ is a non-negative integer, and $p$ is a prime, then let $n_p\in\F_p^*$ be the word whose characters are the digits of $n$ in base $p$, with the least significant digit first. That is, if we let $n_p[i]$ denote the $i$th digit in the base-$p$ expansion of $n$ so that $n = \sum_{i\in\Z_{\geq 0}} n_p[i]p^i$, then $n_p = (n_p[0])(n_p[1])\cdots(n_p[\vert n_p\vert-1])$. Please note that in this author's previous paper \cite{KohenUR}, most-significant-digit first (the reverse of this convention) was used, but here we use least-significant-digit first to more closely follow constructions in \cite{ShallitBook}. Also note that when working with strings, exponents denote repetition. For example, $(p-1)^k\in\F_p^*$ denotes a run of $k$ characters that are all the character $(p-1)$. Lastly, note that every statement made in this paper about $n_p$ should also hold for $n_p0^k$ for every $k$.

All \emph{morphisms} in this paper refer to morphisms of strings, which are maps, $f: \Sigma_1^*\rightarrow\Sigma_2^*$, such that $f(c_1c_2\cdots) = f(c_1)f(c_2)\cdots$, which can be defined by their action on the elements of $\Sigma_1$. If for every $c\in\Sigma_1$, $\vert f(c)\vert = \ell$ is constant then we say that $f$ is \emph{$\ell$-uniform}. If a morphism is $1$-uniform we call it a \emph{coding}. We say that a morphism, $f:\Sigma^*\rightarrow\Sigma^*$, is \emph{prolongable} on $c\in\Sigma$ if $f(c) = cw$ where $w\in \Sigma^*$ and $f^n(w)$ is non-empty for all $n\geq 0$; in this case, $f^n(c) = cwf(w)f^2(w)\cdots f^{n-1}(w)$ for every $n\geq 0$ and the infinite word $f^\omega(c) = cwf(w)f^2(w)\cdots$ is a fixed point of $f$ (i.e., $f(f^\omega(c)) = f^\omega(c)$).

A sequence, $a_n$, is \emph{$p$-automatic} if it has values in some finite alphabet, and there exists a deterministic finite automaton with output (DFAO) that, given an index $n$ in its base-$p$ representation, $n_p$, ends on a state whose output is $a_n$.

A \emph{$p$-linear representation} of rank $m$ of a sequence $a_n$ over $\F_p$ is a triple $(v,\gamma, w)$ consisting of row vector from $\F_p^m$, a matrix-valued morphism, and column vector from $\F_p^m$, respectively. The string morphism $\gamma: \F_p^*\rightarrow \text{Mat}_{m\times m}(\F_p)$ uses matrix multiplication instead of concatenation in its co-domain, such that $v\cdot\gamma(n_p)\cdot w \equiv a_n$ (mod $p$) for all $n\in\N$. We frequently replace the domain $\F_p$ above with $\Z/p^a\Z$ except in the input alphabet of $\gamma$, which is always $\F_p$. If $a_n$ has such a $p$-linear representation, we say it is \emph{$p$-regular}. \cite[Thm.\ 9.6.1]{ShallitBook} says that a sequence with finitely many values is $p$-automatic if and only if it is $p$-regular.


\section{Preliminaries}\label{sec:prelim}
The Rowland-Zeilberger automaton is wonderfully described, with examples, in \cite{rowlandzeilberger}. Its existence shows that constant term sequences modulo prime powers are $p$-automatic. The general construction is specified in \cite{rowlandzeilberger}. We repeat some of that exposition here:

\begin{definition}
For every positive integer $k$, define $\Lambda_k$ to be the map from (and to) Laurent polynomials over $\Z$ (or the induced map on quotient rings) defined by $$\Lambda_k\left(\sum_{i\in [-m,m]^r}q_i\x^i\right) = \sum_{k\mid i}q_i\x^{\frac{i}{k}}.$$ That is, $\Lambda_k$ deletes terms whose exponents are not all multiples of $k$ and then performs the change of variables $x_j^k\mapsto x_j$ for every $j$.
\end{definition}

\begin{lemma}\label{RZ_cong}
For all Laurent polynomials $P$ and $Q$, all primes $p$, and all integers $n$ and $k$, we have
$$\ct{P^{pn+k}\cdot Q}\equiv \ct{P^n\cdot\Lambda_p(P^kQ)}\pmod p.$$
\end{lemma}
\begin{proof}
First note the equivalence often referred to as the ``generalized freshman's dream'', $P(x_1,\ldots, x_r)^p\equiv P(x_1^p,\ldots,x_r^p)$ (mod $p$), and then note that the change of variables $x_i^p\mapsto x_i$ does not affect constant terms. From these two observations, it follows that
\begin{align*}
\constantterm[P(x_1,\ldots, x_r)^{pn+k} &\cdot Q(x_1,\ldots, x_r)]\\
&\equiv \ct{P(x_1^p,\ldots,x_r^p)^n\cdot P(x_1,\ldots, x_r)^kQ(x_1,\ldots, x_r)}\\
&= \ct{P(x_1,\ldots, x_r)^n\cdot\Lambda_p(P(x_1,\ldots, x_r)^kQ(x_1,\ldots, x_r))}.
\end{align*}
\end{proof}

Using this congruence, we can construct a deterministic finite automaton with output (DFAO) whose states are labeled with Laurent polynomials by beginning with the state $Q$, and then having transitions labeled $k$ for $k\in\F_p$ that lead to (possibly new) states labeled by $Q' = \Lambda_p(P^kQ)$, and repeating this process until no new states can be reached (see the following lemma to understand why this terminates). The output of a state labeled $Q$ is $\ct{Q}$. This DFAO is known as the Rowland-Zeilberger automaton, and its construction constitutes a proof that $a_n = \ct{P^nQ}\bmod p$ is a $p$-automatic sequence.

\begin{lemma}\label{deg_bound}
For a fixed $P$, if we define $\Lambda_p^k(Q) = \Lambda_p(P^kQ)$, then $$m := \max(\deg (P) - 1, \deg (Q))\geq \deg\Lambda_p^{k_t}(\cdots \Lambda_p^{k_0}(Q)\cdots ).$$ That is, $m$ is a bound on the degree of every polynomial that is the result of iterating $\Lambda_p^k$ on input $Q$ for all values of $k\in\F_p$. In particular, $m$ bounds the degree of every state, $Q$, appearing in the Rowland-Zeilberger construction.
\end{lemma}
\begin{proof}
If $Q_0 = \sum_{i\in[-m_0,m_0]^r} q_i\x^i$ is of degree $m_0$, then for all $k\leq p-1$, $\Lambda_p^k$ is $\F_p$-linear so that $Q_1 = \Lambda_p^k(Q_0) = \sum_{i\in[-m_0,m_0]^r}q_i\Lambda_p(P^k\x^i)$ and $\deg Q_1 = \max_i(\deg(\Lambda_p(P^k\x^i)))$, which depends only on $k, m_0,$ and $P$. For $i\geq 0$, letting $\vert (j_1,\ldots,j_r)\vert = \max_k j_k$, and recalling that $a_{-j}^k = \coef{j}{P^k}$, $$\Lambda_p(P^k\x^i) = \Lambda_p\left(\sum_{\vert j\vert<k\deg P}a^k_{-j}\x^{i+j}\right) = \sum_{\vert j\vert\leq k\deg P, p\mid i+j}a^k_{-j}\x^{\frac{i+j}{p}}.$$ From this, since $\vert j\vert \leq k\deg P\Rightarrow \vert\frac{i+j}{p}\vert\leq \frac{k\deg P + \vert i\vert}{p}\leq \frac{(p-1)\deg P + \vert i\vert}{p}$, we can see that $$\deg Q_1\leq \frac{p-1}{p}\deg P + \frac{\deg Q_0}{p},$$ independently of $k$. And in general, a simple induction shows that every $Q_n$ reached from $Q_0$ in $n$ steps has $$\deg Q_n\leq \deg P + \frac{\deg Q_0 - \deg P}{p^n}.$$ From this, we can immediately see that if $\deg Q_0 < \deg P$ then $\deg Q_n < \deg P$ as well for all $n$. Furthermore, the degrees of our $Q_i$s are decreasing when $\deg Q_0 > \deg P$ since this implies that $\deg Q_1\leq \deg P + \frac{\deg Q_0 - \deg P}{p} = \frac{(p-1)\deg P + \deg Q_0}{p} < \deg Q_0$; in particular, if $\log_p(\deg Q_0 - \deg P) < n$ then $\deg Q_n\leq \deg P$ for every $Q_n$ reachable from $Q_0$ in $n$ steps. Lastly, if $\deg Q_0 = \deg P$, then $\deg Q_1 = \deg\Lambda_p(P^{k}Q_0) < \deg P$ for all $k < p-1$, while $\deg\Lambda_p(P^{p-1}Q_0) = \deg P$.
\end{proof}

For a different analysis yielding Lemma~\ref{deg_bound}, see \cite[Thm.\ 2.4]{statebound}.

We use $m$ as defined in Lemma~\ref{deg_bound} for the remainder of the paper when $P$ and $Q$ are understood from context.

In general, $p$-automatic sequences have (at least) three useful descriptions. First, as a sequence determined by a DFAO as above. Second, as the result of coding a fixed point of a prolongable uniform morphism, whose equivalence to the first description is known as Cobham's little theorem \cite{CobhamLittleThm} (or see \cite[Thm.\ 5.4.1]{ShallitBook}). Third, every $p$-automatic sequence is always $p$-regular and hence has a $p$-linear representation $(v,\gamma,w)$, and the converse ($p$-regular $\Rightarrow$ $p$-automatic) is true for sequences taking on finitely many values. This equivalence is \cite[Thm.\ 9.6.1]{ShallitBook}, and the proof is constructive: using the $p$-linear representation of our sequence, a prolongable uniform morphism is built whose infinite fixed-point has a coding yielding the same sequence.

We make use of all three types of descriptions to prove our results, but the ``free'' constructions are not sufficient for our purposes. Hence, rather than using the Rowland-Zeilberger automaton for $a_n = \ct{P^nQ}\bmod p$ directly, we instead derive a $p$-linear representation for $a_n$ by using Lemma~\ref{RZ_cong} directly. This yields a generalization of the Lucas congruences for central binomial (OEIS \seqnum{A000984}) and trinomial (OEIS \seqnum{A002426}) coefficients, which were the primary tools used in \cite{KohenUR} to derive similar uniform recurrence results when $P$ is of degree at most $1$. We then use this $p$-linear representation to build our other descriptions of $a_n$.

\section{A novel linear representation}\label{sec:linrep}
Our $p$-linear representation is the result of interpreting the Rowland-Zeilberger machine within the vector space of Laurent polynomials over $\F_p$ of degree bounded by $m$. Note that this construction differs from the standard construction creating a $p$-linear representation from a DFAO, which uses the states of the DFAO as a basis rather than, for example, the standard basis of powers of $\x$.

\begin{definition}
Recall the definition of $m$ from Lemma~\ref{deg_bound}. We wish to encode Laurent polynomials with coefficients in $\F_p$ of degree $\leq m$ as a product of copies of $\F_p$, and so we must choose a computational basis: Impose an order on $T = [-m,m]^r$ (e.g., lexicographical), where $T$ indexes the set of coefficients in a polynomial with degree $\leq m$. If $Q = \sum_{i\in T}q_i\x^i$ then let $\text{vec}(Q)$ be the row vector $(q_j)_{j\in T}$ and let $\code_Q:(\F_p^T)^*\rightarrow\F_p^*$ be the coding defined by $\code_Q(\vec{u}) = \text{vec}(Q)\cdot\vec{u}$.
\end{definition}

\begin{proposition}\label{bookkeeping}
For every $k\in\F_p$ and $i\in T$, $\Lambda_p(P^k\x^i) = \sum_{j\in T}a_{i-pj}^k\x^j$.
\end{proposition}
\begin{proof}
Using the definition of $\Lambda_p$, we get
$$\coef{j}{\Lambda_p(P^k\x^i)} = \coef{pj}{P^k\x^i} = \coef{pj - i}{P^k} = a_{i-pj}^k.$$
\end{proof}

\begin{definition}\label{linrepdef}
Notice that the map $Q\mapsto \Lambda_p(P^kQ)$ is $\F_p$-linear and maps $\F_p^T$ (the space of bounded-degree Laurent polynomials) to itself by Lemma~\ref{deg_bound}. Thus, this map corresponds to a matrix with entries in $\F_p$, which we denote by $\gamma(k)$. This map is determined by its action on the standard basis of monomials (written as row vectors to the left of $\gamma(k)$). Therefore, we can deduce from Proposition~\ref{bookkeeping} that $$\gamma(k) := (a^k_{i - pj})_{i,j\in T}.$$ The matrix-valued string morphism, $\gamma$, defined in this way along with the row vector \text{vec}($Q$) and the column vector, $V(0)$, whose only non-zero entry is at the index corresponding to the constant term constitute a $p$-linear representation for the sequence $a_n = \ct{P^nQ}\bmod p$. This is because the computation vec$(Q)\cdot \gamma(n_p)\cdot V(0)$ when multiplied from left to right is exactly the computation executed by the Rowland-Zeilberger machine yielding $a_n$.
\end{definition}

Put another way: in \cite[Section~9.3]{ShallitBook}, Shallit describes how to convert a $p$-linear representation of a $p$-automatic sequence into a set of relations of its finite $p$-kernel, and then \cite[Thm.\ 5.5.1]{ShallitBook} (which shows constructively that a sequence has finite $p$-kernel if and only if it is $p$-automatic) describes a process for converting this finite set of relations into a DFAO describing the sequence. Successively applying these two algorithms to the $p$-linear representation $(\text{vec}(Q), \gamma, V(0))$ exactly yields the Rowland-Zeilberger DFAO described in this section.

The matrices, $\gamma(k)$, of Definition~\ref{linrepdef} can also be interpreted as acting on the left of column vectors that correspond to linear functionals. That is, we begin with $V(0)$, which corresponds to the linear functional $Q\mapsto \ct{Q}$, and then read the most significant base-$p$ digit, $k$, of $n$ in order to update to the new linear functional $Q\mapsto \ct{P^k Q}$. This process is then repeated until the final linear functional is $Q\mapsto \ct{P^nQ}$, as desired. This observation motivates the following definition and lemma.

\begin{definition}\label{Vdef}
Let $V(n)$ be the column vector $(a^n_i)_{i\in T}\in\F_p^T$, which stores the coefficients of $P^n$ whose terms have degree at most $m$.
\end{definition}

\begin{lemma}\label{Vlemma} For all non-negative integers $n$ and all $k\in\F_p$, we have
$$\gamma(k)\cdot V(n) = V(pn+k).$$
\end{lemma}
\begin{proof}
In view of Lemma~\ref{RZ_cong} and Proposition~\ref{bookkeeping}, for all $i\in T$, we have
\begin{align*}
V(pn+k)[i] &= a^{pn+k}_i\\
&= \ct{P^{pn+k}\x^i}\\
&\equiv \ct{P^n\cdot\Lambda_p(P^k\x^i)}\pmod p\\
&= \ct{P^n\cdot\sum_{j\in T}a^k_{i-pj}\x^j}\\
&= \sum_{j\in T}a^k_{i-pj}\cdot \ct{P^n\x^j}\\
&= \sum_{j\in T}a^k_{i-pj}a^n_j\\
&= ((a^k_{i-pj})_{i,j\in T}\cdot V(n))[i]\\
&= (\gamma(k)\cdot V(n))[i].
\end{align*}
The result follows.
\end{proof}

Remarkably, this lemma shows that modulo $p$, the low-degree coefficients of $P^n$ can be efficiently computed without reference to higher degree coefficients (except for those of $P^k$ with $k<p$). It also details the process executed by our new reverse Rowland-Zeilberger machine whose states are the $V(i)$, which have output $\code_Q(V(i))$. This machine is essentially an instantiation of the reversal of a generic DFAO given in \cite[Thm.\ 4.3.3]{Allouche_Shallit_Book}, except that we keep the algebraic information inherited from the fact that we are computing constant term sequences. This description also shows that directly computing the reverse Rowland-Zeilberger machine is not, in principle, more expensive than computing the usual machine. Finally, the primary benefit of this description of $\ct{P^nQ}\bmod p$ is that it is independent of $Q$ until the output is computed from the final state. That is, we can study the sequence $(V(n))_{n\in\N}$ whose elements are in $\F_p^T$ and think of all of our constant term sequences as the images of this one sequence under various codings.

To this end, we introduce a description of the sequence $(V(n))_{n\in\N}$ as a fixed point of a prolongable uniform morphism.

\begin{definition}\label{morph}
When a Laurent polynomial $P$, a prime $p$, and an integer $m\geq \deg(P) - 1$ (and $m\geq \deg Q$ for every $Q$ that we may be considering) are fixed, we define the $p$-uniform morphism $\sigma:(\F_p^T)^*\rightarrow(\F_p^T)^*$ by $$\sigma(\vec{u}) := (\gamma(0)\cdot\vec{u})(\gamma(1)\cdot\vec{u})\cdots(\gamma(p-1)\cdot\vec{u}).$$
$\sigma$ is prolongable on $V(0)$ since $\gamma(0)\cdot V(0) = V(0)$ by Lemma~\ref{Vlemma}, and so $$\alpha:= \sigma^\omega(V(0)) = V(0)V(1)V(2)\cdots\in(\F_p^T)^*$$ whose $n$th character is $V(n)$, is a fixed point of $\sigma$, i.e., $\sigma(\alpha) = \alpha$.

To see that $\alpha[n] = V(n)$, note that $$\sigma(V(j)) = (\gamma(0)\cdot V(j))\cdots(\gamma(p-1)\cdot V(j)) = V(pj)\cdots V(pj+p-1)$$ and thus $\sigma(V(0)V(1)\cdots V(p^n-1))$ is equal to $$(V(0)\cdots V(p-1))(V(p)\cdots V(p^2-1))\cdots (V(p^{n+1}-p)\cdots V(p^{n+1}-1)).$$
\end{definition}

In essence, we can fluidly and interchangeably utilize all four (compatible) representations of $\ct{P^nQ}$; as the Rowland-Zeilberger DFAO (Lemma~\ref{RZ_cong}), as the reverse Rowland-Zeilberger DFAO (Lemma~\ref{Vlemma}), using the $p$-linear representation of Definition~\ref{linrepdef}, and using a coding of the fixed point of Definition~\ref{morph}. The dictionary allowing us to go between these representations is most easily stated by relating each description to the $p$-linear representation as follows: The states of the Rowland-Zeilberger DFAO are labeled by polynomials $Q$, corresponding to $\text{vec}(Q)$ in the $p$-linear representation; transitions from $Q$ to $Q'$ labeled by $k$ in the DFAO are such that $\text{vec}(Q)\cdot\gamma(k) = Q'$. Likewise, the states of the reverse Rowland-Zeilberger DFAO are labeled by the $V(i)$ with transitions from $V(i)$ to $V(j)$ labeled by $k$ such that $\gamma(k)\cdot V(i) = V(j)$. Lastly, the relation $\gamma(k)\cdot V(n) = V(pn+k)$ describes the progression of the fixed-point, $\alpha$, which can be useful for reasoning about properties such as uniform recurrence.

We end this section with a fundamental lemma about $\gamma(0)$:

\begin{lemma}\label{zero_out}
Let $C$ be the index associated with the polynomial $1$ in $T$'s order. There is an integer $s\in\N$ such that for every $s'\geq s$, $\gamma(0)^{s'} = \gamma(0^{s'}) = e_{C,C}$, that is to say it has a $1$ in the row and column corresponding to the constant term and zeros everywhere else.
\end{lemma}
\begin{proof}
The matrix $e_{C,C}$ is characterized by the fact that for every vector $\vec{u}$, $\vec{u}^{tr}\cdot e_{C,C} = (\vec{u}[C])e_C^{tr}$ since, in particular, this being true for the basis vectors $e_i^{tr}$ implies that all rows other than the $C$ row are zero and that the $C$ row is $e_C^{tr}$. Every row vector can be written as $\text{vec}(Q)$ for some $Q$, and $\text{vec}(Q)\cdot\gamma(0) = \text{vec}(\Lambda_p(P^0Q)) = \text{vec}(\Lambda_p(Q))$. Furthermore, $\Lambda_p(Q)$ has degree at most $\frac{0\cdot\deg P + \deg Q}{p} = \frac{\deg Q}{p}$ as seen in Lemma~\ref{deg_bound}. So letting $s'\geq s = \lfloor\log_p(\deg Q)\rfloor + 1$ yields $\text{vec}(Q)\cdot\gamma(0)^{s'} = \text{vec}((\Lambda_p^0)^{s'}(Q)) = \text{vec}(\ct{Q}) = (\text{vec}(Q)[C])e_C^{tr}$, as desired.
\end{proof}

This lemma can be thought of as partially explaining some of the connection between the sequences $\ct{P^nQ}$ and $\ct{P^n\cdot 1}$ since, beginning with $Q$, we can always reach a state corresponding to $Q'\in\F_p\subset\F_p[x_1,\ldots, x_r,x_1^{-1},\ldots,x_r^{-1}]$ in some fixed number of steps using $\gamma(0^s)$.

\section{Classifying uniformly recurrent constant term sequences mod $p$}\label{sec:classify-p}
We begin by analyzing the case in which $\ct{P^nQ}\bmod p$ is not uniformly recurrent, in which case the frequency of $0$ is $1$. First, we note that checking whether a $0$ appears in $\ct{P^n}\bmod p$ can be done by only inspecting a prefix of this sequence.

\begin{proposition}\label{check_bound}
Let $P$ be any Laurent polynomial and $p$ be prime. There is a $B_{P,p}\in\N$, depending on $p$ and $\deg(P)$, so that if there exists some $n\in\N$ such that $p\mid \ct{P^n}$, then there exists an $n_0\in\N$ with $n_0<B_{P,p}$ such that $p\mid \ct{P^{n_0}}$.
\end{proposition}
\begin{proof}
The Rowland-Zeilberger automaton for $\ct{P^n}\bmod p$ contains at most one state for each Laurent polynomial of degree at most $\deg P - 1$, that is, there are at most 
$$p^{\vert T\vert} = p^{(2m+1)^r} = p^{(2\cdot\deg(P)-1)^r}$$
states. If one of the states has output $0$, then there must be a path to it from the starting state of length less than the number of states. Thus, if we let $B_{P,p} = p^{p^{(2\cdot\deg(P)-1)^r}}$, then there must be a $0$ in our sequence for some $n_0<B_{P,p}$.
\end{proof}

Note that it is similarly possible to check whether a constant term sequence, $\ct{P^nQ}$, mod $p$ is equal to the zero sequence by inspecting a finite prefix of the sequence. This is because if such a sequence is ever congruent to some non-zero value, then the Rowland-Zeilberger automaton for $\ct{P^nQ}\bmod p$ will have a state with non-zero output, reachable in a bounded number of base-$p$ digits.

However, this bound of $p^{p^{(2\cdot\deg(P)-1)^r}}$ seems far too large. In the author's brief computer experimentation in one variable, no sequence or prime was found violating the following bound:

\begin{conjecture}
Proposition~\ref{check_bound} holds for $B_{P,p} = p^{\deg(P)}$ when $P$ has one variable ($r=1$).
\end{conjecture}

Now, we show one direction of our main result: non-zero constant term sequences are not uniformly recurrent when the corresponding $Q=1$ constant term sequence has an entry divisible by $p$.

\begin{theorem}\label{zero_density}
If $P$ is any Laurent polynomial and there exists some $n\in\N$ such that $\ct{P^n}\equiv 0$ (mod $p$), then the frequency of $0$ is $1$ in every sequence of the form $\ct{P^nQ}\bmod p$ for every Laurent polynomial $Q$. That is, the set of indices, $n$, such that $\ct{P^nQ}\equiv 0$ (mod $p$) has density $1$. In particular, $\ct{P^nQ}\bmod p$ contains arbitrarily large runs of $0$s and is either the constant $0$ sequence or else it is not uniformly recurrent.
\end{theorem}
\begin{proof}
If $p\mid \ct{P^{n_0}}$, then there exists $s\in\N$ by Lemma~\ref{zero_out} such that $\gamma(0)^s\gamma(n_0)\gamma(0)^s = 0$. Because $\ct{P^nQ} \equiv \text{vec}(Q)\cdot V(n) = \text{vec}(Q)\cdot\gamma(n)\cdot V(0)$, all $n$ such that $n_p$ contains $0^s(n_0)_p0^s$ must have $\ct{P^nQ} \equiv 0$. If $\beta = \vert (n_0)_p\vert$, then consider each $n\in [0, p^{(\beta+2s)\cdot k})$ as corresponding to an element of $(\F_p^{\beta+2s})^k$ via its base-$p$ representation chunked into blocks of size $\beta+2s$. If any of the $k$ entries in $\F_p^{\beta+2s}$ for $n$ correspond to $0^s(n_0)_p0^s$, then we know that $V(n)=0$ and $\ct{P^nQ}\equiv 0$, so at least $p^{(\beta+2s)\cdot k} - (p^{\beta+2s} - 1)^k$ of such $n$ have $\ct{P^nQ} \equiv 0$. Therefore, the frequency of $0$ in $\ct{P^nQ}\bmod p$ is at least $\frac{p^{(\beta+2s)\cdot k} - (p^{\beta+2s} - 1)^k}{p^{(\beta+2s)\cdot k}} = 1 - \left(\frac{p^{\beta+2s} - 1}{p^{\beta+2s}}\right)^k\rightarrow 1$ as $k\rightarrow\infty$. In fact, this shows that the frequency of $0$ in $\alpha$ (of Definition~\ref{morph}) is $1$.
\end{proof}

We wish to prove that if $0$ does not appear in $\ct{P^n}\bmod p$, then $\ct{P^nQ}\bmod p$ is uniformly recurrent. Our main result follows from the following proposition about the morphism $\sigma$ of Definition~\ref{morph}:

\begin{proposition}\label{v0_appears}
There exists $t_0\in\N$ such that for all $n\in\N$, if $p$ does not divide $\ct{P^n}$ then $\sigma^{t_0}(V(n)) = x_0V(0)y_0$ with $x_0,y_0\in(\F_p^T)^*$. That is, $V(0)$ is a character in $\sigma^{t_0}(V(n))$ for every such $n$.
\end{proposition}
\begin{proof}
Let $s\in\N$ such that $\gamma(0)^s = e_{C,C}$. Next, fix $s'\in\N$ such that $C$-term entries (i.e., indexed by $C$) of $\sigma^{s'}(V(0))$ contain all $C$-term values of $V(i)$ that occur for any $i\in\N$. Recall that the $C$-term value of $V(i)$ is the constant coefficient of $P^i$. An $s'$ exists since there are finitely many (namely, $p$) values that $C$-term entries of $V(i)$ can take on, each initially occurring at some finite value of $i$. Let $V(n)[C]\in\F_p$ denote the entry of $V(n)$ corresponding to the constant term, which is not $0$ by our assumption that $p$ does not divide $\ct{P^n}$. Finally, we have that $\gamma(0)^s\cdot V(n) = (V(n)[C])V(0)$, $\sigma^{s' + s}(V(0))$ contains $(V(n)[C])V(0)$, and $(V(n)[C])^{p-1}\equiv 1$ (mod $p$) by Fermat's little theorem. Therefore, we can conclude that $\sigma^{(s'+s)(p-2)+s}(V(n))$ contains $V(0)$, as desired.
\end{proof}

Note that $t_0$ above does not depend on $n$. We now have everything we need to prove our main result and more.

\begin{theorem}\label{main}
If $P$ and $Q$ are Laurent polynomials with integer coefficients, $p$ is prime, and $\ct{P^nQ}\bmod p$ is not the constant $0$ sequence, then the sequence $\ct{P^nQ}\bmod p$ is linearly recurrent if and only if $p$ does not divide $\ct{P^n}$ for all $n\in\N$, and this can be checked for bounded $n<B_{P,p}$. When the sequence is not linearly recurrent, it is $0$ with frequency $1$. This classification is independent of $Q$.
\end{theorem}
\begin{proof}
If there exists an $n\in\N$ such that $p\mid \ct{P^n}$, then Proposition~\ref{check_bound} tells us that there is such an $n<B_{P,p}$. And Theorem~\ref{zero_density} tells us that $\ct{P^nQ}\bmod p$ is not uniformly recurrent.

For the converse, we show that $\alpha$ from Definition~\ref{morph} is linearly recurrent, from which the result follows since our sequence is the image of $\alpha$ under $\code_Q$. The result \cite[Thm.\ 10.8.4]{ShallitBook} states that if a $p$-automatic sequence is uniformly recurrent, it is linearly recurrent. Thus, it is sufficient for us to show that $\alpha$ is uniformly recurrent.

If $w$ appears as a word in $\alpha$, and its first occurrence ends by index $i<p^{t_1}$, then $w$ appears in $\sigma^{t_1}(V(0)) = V(0)V(1)\cdots V(p^{t_1}-1)$ since $\sigma$ is $p$-uniform. We can conclude from Proposition~\ref{v0_appears} that for all $n\in\N$, and all words $w$ appearing in $\alpha$, $$\sigma^{t_1 + t_0}(V(n)) = \sigma^{t_1}(x_0V(0)y_0) = \sigma^{t_1}(x_0)\sigma^{t_1}(V(0))\sigma^{t_1}(y_0) = \sigma^{t_1}(x_0)x_1wy_1\sigma^{t_1}(y_0).$$
In other words, $w$ appears in every $\sigma^{t_1 + t_0}(V(n))$, and since $$\alpha = \sigma^{t_1 + t_0}(\alpha) = \sigma^{t_1 + t_0}(V(0))\sigma^{t_1 + t_0}(V(1))\sigma^{t_1 + t_0}(V(2))\cdots$$ and $\sigma$ is uniform (so that $\sigma^{t_1 + t_0}$ is also uniform), this implies that $\alpha = V(0)V(1)V(2)\cdots$ is uniformly recurrent.
\end{proof}

\begin{corollary}\label{combinations}
Let $X$ be any set, let $F: \F_p^\ell\rightarrow X$ (which is deterministic) for some $\ell\in\N$, and let $b_n = F(\ct{P^{n+k_1}Q_1}\bmod p, \ldots, \ct{P^{n+k_\ell}Q_\ell}\bmod p)$ where the $k_i$ are arbitrary non-negative integers and the $Q_i$ are arbitrary Laurent polynomials such that $b_n$ is not the constant sequence $F(0,\ldots, 0)$. Then $b_n$ is linearly recurrent if and only if for all $n\in\N$, $p$ does not divide $\ct{P^n}$. Furthermore, in the case where there exists $n$ such that $p\mid \ct{P^n}$, then the frequency of $F(0,\ldots,0)$ in $b_n$ is $1$. For example, if $F$ takes a linear combination of its inputs then we get that $b_n = \sum_{i=0}^\ell \beta_i\cdot(\ct{P^{n+k_i}Q_i}\bmod p)$ for arbitrary $\beta_i$ is linearly recurrent if and only if $p$ does not divide $\ct{P^n}$ for all $n$.
\end{corollary}
\begin{proof}
The proof of Theorem~\ref{main} actually shows that $\alpha = V(0)V(1)V(2)\cdots$ is linearly recurrent. Since each word beginning with $b_{n_0}$ of length $L$ is determined by the word $V(n_0-\min(k_i))\cdots V(n_0+\max(k_i)+L)$, we can conclude that the sequence $b_n$ is linearly recurrent when $\alpha$ is. Furthermore, if $\alpha$ is not linearly recurrent, it contains $0$ vectors with frequency $1$ (by Theorem~\ref{zero_density}), and hence $b_n$ contains $F(0,\ldots,0)$ with frequency $1$.
\end{proof}

We conclude this section by noting that even in the case where $p\mid \ct{P^{n_0}}$ for some $n_0$, resulting in $\alpha$ containing $0$ vectors with frequency $1$, we still have that $\alpha$ is recurrent (see below) so long as there exists an $n$ such that $p$ does not divide $\ct{P^n}$.

\begin{definition}
A sequence $s_n$ is called \emph{recurrent} if for every occurrence of a word, $w = s_is_{i+1}\cdots s_{i+\ell-1}$, there is another later occurrence. That is, there is a $j > 0$ such that $w = s_{i+j}s_{i+j+1}\cdots s_{i + j + \ell - 1}$. This is equivalent to saying that every word that appears recurs infinitely often, but there is no bound on gaps between occurrences.
\end{definition}

\begin{proposition}\label{recurrent}
If $P$ and $Q$ are Laurent polynomials and $p$ is prime, and there exists some $n_0>0$ such that $p$ does not divide $\ct{P^{n_0}}$, then the sequence $b_n = \ct{P^nQ}\bmod p$ is recurrent.
\end{proposition}
\begin{proof}
Proposition~\ref{v0_appears} assures us that $\sigma^{t_0}(V(n_0))$ contains $V(0)$. Therefore, if $w$ is a word in $\alpha$ and we consider an occurrence of $w$ that ends by index $i < p^{t_2}$, then $w$ appears in $\sigma^{t_2}(V(0))$ and thus $w$ appears in $\sigma^{t_2 + t_0}(V(n_0))$. Finally, since $$\alpha = \sigma^{t_2 + t_0}(\alpha) = \sigma^{t_2 + t_0}(V(0))\sigma^{t_2 + t_0}(V(1))\cdots\sigma^{t_2 + t_0}(V(n_0))\cdots$$ we can conclude that $w$ recurs and consequently the corresponding words in $b_n$ do as well. Specifically, the occurrence of $w$ we began with is in the first segment, $\sigma^{t_2+t_0}(V(0))$, of the above decomposition of $\alpha$ and there is a subsequent occurrence in the $\sigma^{t_2+t_0}(V(n_0))$ segment. Note that the obstruction to uniform recurrence is the dependence of $t_2$ on the index of the occurrence of $w$ since there can be arbitrarily large gaps between constructed occurrences.
\end{proof}

\begin{question}
What can be said about the recurrence (or non-recurrence) of $\ct{P^nQ}$ when $\ct{P^n}\equiv 0$ for all $n>0$? For example, $\ct{P^n}\equiv 0$ for all $n>0$ when $P(x) = x^{p-1} + x^{-1}$.
\end{question}

\section{Extending results to prime powers}\label{sec:prime-powers}
Analogous results to Theorem~\ref{main} and Corollary~\ref{combinations} hold when we consider constant term sequences modulo general prime powers, but some extra care is required in this case. To avoid unnecessary confusion in the case of primes (as presented above), the discussion of prime powers has been excised to this section.

The construction of the Rowland-Zeilberger automaton in \cite{rowlandzeilberger} becomes mildly more complicated mod $p^a$ for $a>1$ because Lemma~\ref{RZ_cong} no longer holds. However, after reading fewer than $a$ base-$p$ digits, we have a result analogous to Lemma~\ref{RZ_cong}.

\begin{definition}
When the integer Laurent polynomial $P$ and modulus $p^a$ are fixed, we define $\tilde{P}(\x)$ to be such that $P(x_1, \ldots, x_r)^{p^{a-1}} \equiv \tilde{P}(x_1^{p^\ell}, \ldots, x_r^{p^\ell})$ (mod $p^a$) where $\ell$ is taken to be as large as possible. Note that since $P(x_1, \ldots, x_r)^p\equiv P(x_1^p,\ldots, x_r^p)$ (mod $p$), it follows that $$P(x_1,\ldots, x_r)^{p^a} = (P(x_1,\ldots, x_r)^p)^{p^{a-1}}\equiv P(x_1^p, \ldots, x_r^p)^{p^{a-1}}\pmod {p^a}.$$ Thus, $\tilde{P}(x_1^{p^\ell}, \ldots, x_r^{p^\ell})^p\equiv \tilde{P}(x_1^{p^\ell\cdot p}, \ldots, x_r^{p^\ell\cdot p})$ (mod $p^a$), or equivalently, by a change of variables, $$\tilde{P}(x_1,\ldots, x_r)^p\equiv \tilde{P}(x_1^p,\ldots, x_r^p)\pmod{p^a}.$$
Consequently, $\tilde{P}$ is stable under Rowland-Zeilberger transitions, i.e., $\tilde{\tilde{P}} = \tilde{P}$. Also note that when $a=1$, this section coincides with the previous one if we take $\tilde{P} = P$.
\end{definition}

\begin{lemma}\label{zero_conversion}
For all Laurent polynomials $P$ and primes $p$, there exists an $n_0\in\N$ such that $p\mid\ct{P^{n_0}}$ if and only if there exists an $n_1\in\N$ such that $p\mid\ct{\tilde{P}^{n_1}}$. Furthermore, if $n_0$ exists one can take $n_1$ to be $n_0$.
\end{lemma}
\begin{proof}
Because $\ct{\tilde{P}(x_1,\ldots, x_r)^n} = \ct{\tilde{P}(x_1^{p^\ell}, \ldots, x_r^{p^\ell})^n} = \ct{P(x_1,\ldots, x_r)^{p^{a-1}n}}$, the sequence $(\ct{\tilde{P}^n})_{n\in\N}$ is a subsequence of $(\ct{P^n})_{n\in\N}$. Thus, it is sufficient to show that when $\ct{P^{n_0}}\not\equiv 0$ (mod $p$), then $\ct{\tilde{P}^{n_0}}\not\equiv 0$ (mod $p$).

By Lemma~\ref{zero_out} and Definition~\ref{Vdef} we have that $\gamma(0)^s\cdot V(n_0)\neq 0$. Furthermore, using Lemmas~\ref{zero_out} and~\ref{Vlemma},
we get $$\gamma(0)^s\cdot V(n_0) = \gamma(0)^{s+a-1}\cdot V(n_0) = \gamma(0)^s\cdot \gamma(0)^{a-1}\cdot V(n_0) = \gamma(0)^s\cdot V(p^{a-1}n_0)\neq 0,$$ from which we can conclude that $\ct{\tilde{P}^{n_0}}\equiv \ct{P^{p^{a-1}n_0}}\not\equiv 0$ (mod $p$).
\end{proof}

We now apply some simple tricks to describe $\ct{P^nQ}$ (mod $p^a$) in terms of sequences of the form $\ct{\tilde{P}^nQ}$ (mod $p^a$). For $\tilde{P}$, since $\ct{\tilde{P}(x_1,\ldots, x_r)^p}\equiv \ct{\tilde{P}(x_1^p, \ldots, x_r^p)}$ (mod $p^a$), all of our completed analysis applies so long as we replace calculations modulo $p$ with calculations modulo $p^a$ and replace various symbols with their (mod $p^a$)-counterparts, which are decorated with a tilde ($\sim$) in this section. These translations are so direct that we omit proofs for most of the results and instead reference the analogous results above.

\begin{proposition}\label{conversion}
For all Laurent polynomials $P$ and $Q$, all $n\in\N$, and all $k\in\Z/p^{a-1}\Z$, we have
$$\ct{P^{p^{a-1}n+k}Q}\equiv \ct{\tilde{P}^n\cdot\Lambda_{p^\ell}(P^kQ)}\pmod{p^a}.$$
\end{proposition}
\begin{proof}
\begin{align*}
\constantterm[P(x_1, \ldots, x_r)^{p^{a-1}n+k} & Q(x_1, \ldots, x_r)]\\
&= \ct{(P(x_1, \ldots, x_r)^{p^{a-1}})^nP(x_1, \ldots, x_r)^kQ(x_1, \ldots, x_r)}\\
&\equiv \ct{\tilde{P}(x_1^{p^\ell}, \ldots, x_r^{p^\ell})^nP(x_1, \ldots, x_r)^kQ(x_1, \ldots, x_r)}\\
&\equiv \ct{\tilde{P}(x_1, \ldots, x_r)^n\Lambda_{p^\ell}(P(x_1, \ldots, x_r)^kQ(x_1, \ldots, x_r))}.
\end{align*}
\end{proof}

Now we can compute $\ct{P^{n'}Q}\bmod{p^a}$ as follows. Let $k$ be the integer formed by the $a-1$ least significant base-$p$ digits of $n'$, and let $n$ be the integer formed by the remaining digits. Then compute $\ct{\tilde{P}^n\cdot\Lambda_{p^\ell}(P^kQ)}\bmod{p^a}$, where $\tilde{P}$ satisfies $\tilde{P}(x_1, \ldots, x_r)^p\equiv \tilde{P}(x_1^p, \ldots, x_r^p)$ (mod $p^a$). Using this congruence, we obtain lemmas analogous to Lemma~\ref{RZ_cong} and Lemma~\ref{deg_bound} for $\tilde{P}$:

\begin{lemma} For all $k\in\F_p$, $n\in\N$, and all integer Laurent polynomials, $\tilde{P}(\x)$, satisfying the congruence $\tilde{P}(x_1, \ldots, x_r)^p\equiv \tilde{P}(x_1^p, \ldots, x_r^p)$ (mod $p^a$), we have $$\ct{\tilde{P}^{pn + k}Q}\equiv \ct{\tilde{P}^n\cdot\Lambda_p(\tilde{P}^kQ)}\pmod{p^a}.$$
\end{lemma}

\begin{lemma}
For a fixed $\tilde{P}$, $$\tilde{m} := \max(\deg (\tilde{P}) - 1, \deg (Q_0))\geq \deg\Lambda_p^{k_t}(\cdots \Lambda_p^{k_0}(Q_0)\cdots ).$$ That is, $\tilde{m}$ is a bound on the degree of every polynomial that is the result of iterating $\Lambda_p^k$ on input $Q_0$ for all values of $k\in\F_p$. In particular, $\tilde{m}$ bounds the degree of every $Q_0$ appearing in the Rowland-Zeilberger construction.
\end{lemma}

Note that by Proposition~\ref{conversion}, the maximum that defines $\tilde{m}$ must be taken over $\deg(\tilde{P})-1$ and $Q_0 = \deg(\Lambda_{p^\ell}(P^kQ))$ for all $k\in\Z/p^{a-1}\Z$ for all values of $Q$ we are considering.

\begin{definition}
We wish to encode Laurent polynomials, with coefficients viewed modulo $p^a$, of degree $\leq m$ as a product of copies of $\Z/p^a\Z$, and so we must choose a computational basis: Impose an order on $\tilde{T} = [-\tilde{m},\tilde{m}]^r$ (e.g., lexicographical), where $\tilde{T}$ indexes the set of coefficients in a polynomial with degree $\leq \tilde{m}$. If $Q = \sum_{i\in \tilde{T}}q_i\x^i$ then let $\text{vec}(Q)$ be the row vector $(q_i)_{i\in \tilde{T}}$ and let $\code_Q:((\Z/p^a\Z)^{\tilde{T}})^*\rightarrow(\Z/p^a\Z)^*$ be the coding defined by $\code_Q(\vec{u}) = \text{vec}(Q)\cdot\vec{u}$.
\end{definition}

Just as in Definition~\ref{linrepdef}, the map $Q\mapsto \Lambda_p(\tilde{P}^kQ)$ is $(\Z/p^a\Z)$-linear and has the following matrix description:

\begin{definition}
If $\tilde{\gamma}(k) := (\coef{pj-i}{\tilde{P}^k})_{i,j\in \tilde{T}}$, then $\text{vec}(Q)\cdot\tilde{\gamma}(k) = \text{vec}(\Lambda_p(\tilde{P}^kQ))$. Defining $\tilde{\gamma}$ as a matrix-valued string morphism in this way yields the $p$-linear representation $(\text{vec}(Q), \tilde{\gamma}, \tilde{V}(0))$ for the sequence $(\ct{\tilde{P}^nQ}\bmod {p^a})_{n\in\N}$, where the only non-zero entry of $\tilde{V}(0)$ is at the index corresponding to the constant term, where it is $1$. More generally, define $\tilde{V}(n)$ to be the column vector $(\ct{\tilde{P}^n\x^i}\bmod{p^a})_{i\in \tilde{T}}\in (\Z/p^a\Z)^{\tilde{T}}$.
\end{definition}

Just as with Lemma~\ref{Vlemma}:

\begin{lemma}
For all non-negative integers $n$ and all $k\in\F_p$, 
we have
$$\tilde{\gamma}(k)\cdot \tilde{V}(n) = \tilde{V}(pn + k).$$
\end{lemma}

\begin{definition}
Just as in Definition~\ref{morph}, we use $\tilde{\gamma}$ to define the $p$-uniform string morphism $\tilde{\sigma}: ((\Z/p^a\Z)^{\tilde{T}})^*\rightarrow ((\Z/p^a\Z)^{\tilde{T}})^*$ by $$\tilde{\sigma}(\vec{u}) := (\tilde{\gamma}(0)\cdot\vec{u})(\tilde{\gamma}(1)\cdot\vec{u})\cdots (\tilde{\gamma}(p-1)\cdot\vec{u}).$$ Then define $\tilde{\alpha} := \tilde{\sigma}^\omega(\tilde{V}(0)) = \tilde{V}(0)\tilde{V}(1)\tilde{V}(2)\cdots\in ((\Z/p^a\Z)^{\tilde{T}})^*$.
\end{definition}

Just as with Lemma~\ref{zero_out}:

\begin{lemma}
Let $C$ be the index of the polynomial $1$ in $\tilde{T}$'s order. There is an integer $s\in\N$ such that for every $s'\geq s\in\N$, $\tilde{\gamma}(0)^s = \tilde{\gamma}(0^s) = e_{C,C}$, that is to say, it has a $1$ in the row and column corresponding to the constant term and $0$s everywhere else.
\end{lemma}

In analogy with Theorem~\ref{zero_density}:

\begin{lemma}\label{zero_density_power}
If $\tilde{P}$ is a Laurent polynomial satisfying $\tilde{P}(x_1,x_2,\ldots,x_r)^p\equiv \tilde{P}(x_1^p,x_2^p,\ldots,x_r^p)$ (mod $p^a$) and there exists some $n_0\in\N$ such that $\ct{\tilde{P}^{n_0}}\equiv 0$ (mod $p$), then the frequency of $0$ is $1$ in every sequence of the form $\ct{\tilde{P}^nQ}\bmod {p^a}$ for every Laurent polynomial $Q$.
\end{lemma}
\begin{proof}
If $p\mid \ct{\tilde{P}^{n_0}}$, then $\tilde{\gamma}(0)^s\tilde{\gamma}(n_0)\tilde{\gamma}(0)^s$ is a zero-divisor multiple of $e_{C,C}$, so that there exists some $t$ such that $(\tilde{\gamma}(0)^s\tilde{\gamma}(n_0)\tilde{\gamma}(0)^s)^{t} = 0$. Since $\ct{\tilde{P}^nQ} \equiv \text{vec}(Q)\cdot \tilde{V}(n) = \text{vec}(Q)\cdot\tilde{\gamma}(n)\cdot \tilde{V}(0)$ all $n$ such that $n_p$ contains $(0^s(n_0)_p0^s)^{t}$ must have $\ct{\tilde{P}^nQ} \equiv 0$ (mod $p^a$).

If $\beta = \vert (n_0)_p\vert$, then consider each $n\in [0, p^{t(\beta+2s)\cdot k})$ as corresponding to an element of $(\F_p^{t(\beta+2s)})^k$ via its base-$p$ representation chunked into blocks of size $t(\beta+2s)$. If any of the $k$ entries for $n$ correspond to $(0^s(n_0)_p0^s)^{t}$, then we know that $\tilde{V}(n)=0$ and $\ct{\tilde{P}^nQ}\equiv 0$, so at least $p^{t(\beta+2s)\cdot k} - (p^{t(\beta+2s)} - 1)^k$ of such $n$ have $\ct{\tilde{P}^nQ} \equiv 0$. Therefore, the frequency of $0$ in $\ct{\tilde{P}^nQ}\bmod {p^a}$ is at least $\frac{p^{t(\beta+2s)\cdot k} - (p^{t(\beta+2s)} - 1)^k}{p^{t(\beta+2s)\cdot k}} = 1 - \left(\frac{p^{t(\beta+2s)} - 1}{p^{t(\beta+2s)}}\right)^k\rightarrow 1$ as $k\rightarrow\infty$. In fact, this shows that the frequency of $0$ in $\tilde{\alpha}$ is $1$.
\end{proof}

The last thing we need before we can prove our main results is the following proposition analogous to Proposition~\ref{v0_appears}:

\begin{proposition}\label{v0_appears_power}
There exists $t_0\in\N$ such that for all $n\in\N$, if $p$ does not divide $\ct{\tilde{P}^n}$ then $\tilde{\sigma}^{t_0}(\tilde{V}(n)) = x_0\tilde{V}(0)y_0$ with $x_0,y_0\in((\Z/p^a\Z)^{\tilde{T}})^*$. That is, $\tilde{V}(0)$ is a character in $\tilde{\sigma}^{t_0}(\tilde{V}(n))$ for every such $n$.
\end{proposition}
\begin{proof}
Let $s\in\N$ such that $\tilde{\gamma}(0)^s = e_{C,C}$. Next, fix $s'\in\N$ such that $C$-term entries (i.e., indexed by $C$) of $\tilde{\sigma}^{s'}(\tilde{V}(0))$ contain all $C$-term values of $\tilde{V}(i)$ that ever occur for any $i\in\N$. Recall that the $C$-term value of $\tilde{V}(i)$ is the constant coefficient of $\tilde{P}^i$. Note that $\tilde{V}(n)[C]\not\equiv 0$ (mod $p^a$) by our assumption that $p$ does not divide $\ct{\tilde{P}^n}$. Finally, we have that $\tilde{\gamma}(0)^s\cdot \tilde{V}(n) = (\tilde{V}(n)[C])\tilde{V}(0)$, $\tilde{\sigma}^{s' + s}(\tilde{V}(0))$ contains $(\tilde{V}(n)[C])\tilde{V}(0)$, and $(\tilde{V}(n)[C])^{\varphi(p^a)} = 1$ by Euler's theorem (where $\varphi$ is Euler's totient function). Therefore, we can conclude that $\tilde{\sigma}^{(s'+s)(\varphi(p^a)-1)+s}(\tilde{V}(n))$ contains $\tilde{V}(0)$, as desired.
\end{proof}

Note that $t_0$ does not depend on $n$. We are now ready to state our main result.

\begin{theorem}\label{main_power}
If $P$ and $Q$ are Laurent polynomials with integer coefficients, $p^a$ is a prime power, and $\ct{P^nQ}\bmod p^a$ is not the constant $0$ sequence, then the sequence $\ct{P^nQ}\bmod {p^a}$ is linearly recurrent if and only if $p$ does not divide $\ct{P^n}$ for all $n\in\N$, and this can be checked for bounded $n<B_{P,p}$. When the sequence is not linearly recurrent, it is $0$ with frequency $1$. This classification is independent of $Q$, as well as the exponent $a$.
\end{theorem}
\begin{proof}
For every $k\in\Z/p^{a-1}\Z$ and Laurent polynomial $Q$, define $$\code_{Q, k}(\vec{u}) = \text{vec}(\Lambda_{p^\ell}(P^kQ))\cdot \vec{u}$$ where $\vec{u}$ is from $(\Z/p^a\Z)^{\tilde{T}}$. Then for Laurent polynomials $P$ and $Q$, define the coding $$\code_{P, Q}(\vec{u}) = (\code_{Q,0}(\vec{u}), \code_{Q,1}(\vec{u}), \ldots, \code_{Q,p^{a-1}-1}(\vec{u}))\in (\Z/p^a\Z)^{p^{a-1}}.$$ Let $\iota: ((\Z/p^a\Z)^{p^{a-1}})^*\rightarrow (\Z/p^a\Z)^*$ denote the morphism determined by the canonical injection on letters, $$\iota(j_1,j_2,\ldots,j_{p^a-1}) = j_1j_2\cdots j_{p^a-1}.$$ Then, by Proposition~\ref{conversion}, the sequence $$\beta := \iota(\code_{P, Q}(\tilde{\alpha}))$$ has $\ct{P^nQ}\bmod{p^a}$ as its $n$th term.

If there is some $n_0\in\N$ such that $p\mid\ct{P^{n_0}}$, then Lemma~\ref{zero_conversion} gives an $n_1\in\N$ with $p\mid\ct{\tilde{P}^{n_1}}$. By Lemma~\ref{zero_density_power}, the frequency of $0$ in $\tilde{\alpha}$ is $1$, and consequently the frequency of $0$ in $\beta$ is $1$. In particular, $\beta$ is not uniformly recurrent.

If there is no such $n_0$, and if $w$ appears as a word in $\beta$, then we can extend $w$ to a word $w'$ in $\beta$ corresponding to a word in $\tilde{\alpha}$. That is, $w'$ contains $w$ but starts on an index that is a multiple of $p^{a-1}$ and ends on an index one less than a multiple of $p^{a-1}$. Thus, it is sufficient to show that $\tilde{\alpha}$ is uniformly recurrent as this forces uniform recurrence for $w'$ and consequently for $w$.

Given a word $w$ in $\tilde{\alpha}$, choose $t_1$ such that $w$ has its first occurrence ending before the index $p^{t_1}$. Thus, $w$ appears in $\tilde{\sigma}^{t_1}(\tilde{V}(0))$. We can conclude from Proposition~\ref{v0_appears_power} that for all $n\in \N$, $$\tilde{\sigma}^{t_1 + t_0}(\tilde{V}(n)) = \tilde{\sigma}^{t_1}(x_0\tilde{V}(0)y_0) = \tilde{\sigma}^{t_1}(x_0)x_1wy_1\tilde{\sigma}^{t_1}(y_0).$$ In other words, $w$ appears in every $\tilde{\sigma}^{t_1 + t_0}(\tilde{V}(n))$, and since $$\tilde{\alpha} = \tilde{\sigma}^{t_1+t_0}(\tilde{\alpha}) = \tilde{\sigma}^{t_1 + t_0}(\tilde{V}(0))\tilde{\sigma}^{t_1 + t_0}(\tilde{V}(1))\tilde{\sigma}^{t_1 + t_0}(\tilde{V}(2))\cdots$$ and $\tilde{\sigma}$ is uniform (so that $\tilde{\sigma}^{t_1 + t_0}$ is also uniform), this implies that $\tilde{\alpha}$ is uniformly recurrent, and in turn $\beta$ is uniformly recurrent. Finally, \cite[Thm.\ 10.8.4]{ShallitBook} tells us that $p$-automatic uniformly recurrent sequences are linearly recurrent.
\end{proof}

Counterintuitively, this theorem shows that $\ct{P^nQ}\bmod {p^a}$ is linearly recurrent or else $0$ has frequency $1$ for all values $a\geq 1$ simultaneously. Furthermore, just as in Corollary~\ref{combinations}, the same generalization applies to prime powers:

\begin{corollary}\label{combinations_power}
Let $X$ be any set, let $F: (\Z/p^a\Z)^\ell\rightarrow X$ (which is deterministic) for some $\ell\in\N$, and let $b_n = F(\ct{P^{n+k_1}Q_1}\bmod {p^a}, \ldots, \ct{P^{n+k_\ell}Q_\ell}\bmod {p^a})$ where the $k_i$ are arbitrary non-negative integers and the $Q_i$ are arbitrary Laurent polynomials such that $b_n$ is not the constant sequence $F(0,\ldots,0)$. Then $b_n$ is linearly recurrent if and only if for all $n\in\N$, $p$ does not divide $\ct{P^n}$. Furthermore, in the case where there exists $n$ such that $p\mid \ct{P^n}$, then the frequency of $F(0,\ldots,0)$ in $b_n$ is $1$.
\end{corollary}

Lastly, using the same construction of $\beta$ as in the proof of Theorem~\ref{main_power}, we have the analogous result to Proposition~\ref{recurrent} where we can refer to $P$ and not $\tilde{P}$ because we have Lemma~\ref{zero_conversion}:

\begin{proposition}\label{recurrent_power}
If $P$ and $Q$ are Laurent polynomials and $p^a$ is a prime power, and there exists some $n_0>0$ such that $\ct{P^{n_0}}\bmod p\neq 0$, then the sequence $b_n = \ct{P^nQ}\bmod {p^a}$ is recurrent.
\end{proposition}

\section{Application to representation theory}\label{sec:reptheory}
In this section, we briefly interpret Theorem~\ref{main_power} (or more precisely, Corollary~\ref{combinations_power}) in the context of sequential tensor powers of semisimple Lie algebra representations. This context is a great source of constant term sequences.

Let $\mathfrak{g}$ be a semisimple Lie algebra, and let $V$ be a representation of $\mathfrak{g}$ whose formal character is $P\in \Z[\x,\x^{-1}]$. If $W$ is an irreducible representation of $\mathfrak{g}$, then let $a_{W, n}$ denote the multiplicity of $W$ in the direct sum decomposition of $V^{\otimes n}$, which has character $P^n$. It is a consequence of the Weyl integral formula (see, for example, \cite[Section~IV.1]{reptheory}) that a multiple of $a_{W, n}$ is a constant term sequence; in particular, if $Q$ is the product of the formal character of $W$ with the square of the Weyl denominator, then $C\cdot a_{W,n} = \ct{P^nQ}$, where $C$ is the order of the Weyl group. The following theorem follows as a result of Corollary~\ref{combinations_power}.

\begin{theorem}\label{rep_app} Let $\mathfrak{g}$ be a semisimple Lie algebra whose irreducible representations are $\{W_i\}$ and let $V$ be a representation of $\mathfrak{g}$ whose formal character is $P\in\Z[\x,\x^{-1}]$. Let $a_{i,n}$ denote the multiplicity of $W_i$ in the direct sum decomposition of $V^{\otimes n}$. Then for each prime $p$, either all of the sequences $(a_{i,n}\bmod {p^a})_{n\in\N}$ simultaneously have $0$ with frequency $1$ or else all of these sequences that are not the constant $0$ sequence are all linearly recurrent for every $a\geq 1$ and every $i$. In particular, the non-zero sequences are linearly recurrent if and only if there does not exist an $n_0<B_{P,p}$ such that $p\mid \ct{P^{n_0}}$.
\end{theorem}

\begin{example}
Consider $\mathfrak{g}=\mathfrak{sl}_2$, which has one irreducible representation, $L_n$, of dimension $n+1$ for each $n\geq 0$. The character of $L_d$ is $x^{-d} + x^{-d+2} + \cdots + x^{d-2} + x^d$. Let us characterize the consequences of Theorem~\ref{rep_app} for the sequences $a_{i,n}$ described by the multiplicity of $L_i$ in the direct sum decomposition of $L_2^{\otimes n}$. It is straightforward to use characters to verify that $L_2\otimes L_m\cong L_{m-2}\oplus L_m\oplus L_{m+2}$ for all $m\geq 2$. Hence, $a_{i,n}$ is the zero sequence for all odd $i$. More generally, since the Weyl denominator of $\mathfrak{g}$ is $x - x^{-1}$ and the Weyl group of $\mathfrak{g}$ has order $C=2$, we can conclude that $$2\cdot a_{i,n} = \ct{(x^{-2} + 1 + x^2)^n(x^{-i-2} - x^{-i} - x^i + x^{i+2})} = 2\cdot \ct{(x^{-2} + 1 + x^2)^n(x^{i+2} - x^i)}.$$ The second equality is true because of the symmetry of $x^{-2} + 1 + x^2$, which implies that $\ct{(x^{-2} + 1 + x^2)^n(x^{-i-2} - x^{-i})} = \ct{(x^{-2} + 1 + x^2)^n(x^{i+2} - x^i)}$. Thus, we can conclude that $a_{i,n}$ is the constant term sequence $\ct{(x^{-2} + 1 + x^2)^n(x^{i+2} - x^i)}$. It is again easy to see from this description that $a_{i,n}$ is the zero sequence for odd $i$. If $i=2j$, then $$a_{i,n} = \ct{(x^{-2} + 1 + x^2)^n(x^{2j+2} - x^{2j})} = \ct{(x^{-1} + 1 + x)^n(x^{j+1} -x^j)}$$ by a change of variables. Therefore, we can conclude by Theorem~\ref{main_power} that for all $a\geq 1$ and every even $i$, the sequences $(a_{i,n})_{n\in\N}$ (mod $p^a$) are all simultaneously linearly recurrent if and only if $p$ is in the sequence \seqnum{A113305} of primes not dividing any central trinomial coefficient. For the complement of these primes, all of these sequences simultaneously contain $0$ with frequency $1$.
\end{example}

\begin{thebibliography}{1}

\bibitem{Allouche_Shallit_Book}
J.-P. Allouche and J. Shallit, {\it Automatic Sequences: Theory, Applications, Generalizations}, Cambridge University Press, 2003.

\bibitem{reptheory}
T. Br{\"o}cker and T. tom Dieck, {\it Representations of Compact Lie Groups}, Springer, 1985.

\bibitem{CobhamLittleThm}
A. Cobham, Uniform tag sequences, {\it Math. Systems Theory} {\bf 6} (1972), 164--192.

\bibitem{KohenUR}
N. Kohen, Uniform recurrence in the Motzkin numbers and related sequences mod $p$, {\it Electron. J. Combin.} {\bf 32} (2025), Paper No. P2.44.

\bibitem{walnut}
H. Mousavi, Automatic theorem proving in Walnut, arxiv preprint arXiv:1603.06017 [cs.FL], 2021. Available at \url{https://arxiv.org/abs/1603.06017}.

\bibitem{CongruenceAutomaton}
N. Rampersad and J. Shallit, Congruence properties of combinatorial sequences via Walnut and the Rowland-Yassawi-Zeilberger automaton, {\it Electron. J. Combin.} {\bf 29} (2022), Paper No. 3.36.

\bibitem{rowlandzeilberger}
E. S. Rowland and D. Zeilberger, A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences, {\it J. Difference Equ. Appl.} {\bf 20} (2014), 973--988.

\bibitem{ShallitBook}
J. Shallit, {\it The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut}, Cambridge University Press, 2022.

\bibitem{statebound}
A. Straub, On congruence schemes for constant terms and their applications, {\it Res. Number Theory} {\bf 8} (2022), Paper No. 42.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11B50; Secondary 11B85, 68R15.

\noindent \emph{Keywords: } constant term sequence, uniform recurrence, linear recurrence, linear representation, automatic sequence, Rowland-Zeilberger automaton, Motzkin number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000984},
\seqnum{A001006},
\seqnum{A002426},
\seqnum{A005259}, and
\seqnum{A113305}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 1 2025; 
revised version received June 14 2026.
Published in {\it Journal of Integer Sequences},  June 30 2026.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in


\end{document}
