\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 \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 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 $n0$ 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