A Linear Representation for Constant Term Sequences mod p^{a} with Applications

to Uniform Recurrence

Nadav Kohen Department of Mathematics Indiana University Bloomington, IN 47405 USA

                     nkohen@iu.edu

Abstract

Many integer sequences including the Catalan numbers, Motzkin numbers, and the Apéry numbers can be expressed as the constant term of P^{n}Q for Laurent polynomials P and Q. These are often called 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.

1 Introduction

Numerous famous combinatorial sequences admit descriptions of the form s_{n} = ct[P^{n}Q] 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 \underline{A000108}) can be described by C_{n} = ct[(x^{−1} + 2 + x)^{n}(1 − x)], the Motzkin numbers (OEIS \underline{A001006}) can be described by M_{n} = ct[(x^{−1} + 1 + x)^{n}(1 − x^{2})], and the Apéry numbers (OEIS \underline{A005259}, which were used to prove the irrationality of ζ(3)) can be described by

A(n) = ct [(\frac{(1 + x)(1 + y)(1 + z)(1 + y + z + yz + xyz)}{xyz})^{n}] .

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:

Definition 1. A sequence s_{n} is called uniformly recurrent if for every word in s_{n} (i.e., contiguous subsequence), w = s_{i}s_{i+1} ⋯ s_{i+ℓ−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 ≤ C_{w} such that w = s_{i+j}s_{i+j+1} ⋯ s_{i+j+ℓ−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 linearly recurrent.

For background on uniform recurrence in automatic sequences, see [1, Section 10.9] and [8, Section 10.8.8].

In [7], 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 [6], Rampersad and Shallit use these DFAOs in concert with the Walnut library [5] to automatically prove theorems about these sequences using computers. They prove [6, Thm. 10] that, under certain conditions, the sequence T_{n} = ct[(x^{−1} +1+x)^{n}] mod p is uniformly recurrent if and only if it is never 0. They also conjecture [6, Problem 6] that the Motzkin numbers mod p are uniformly recurrent if and only if T_{n} mod p is never 0. In [4], this author showed that this conjecture is true. More generally, if P is a symmetric trinomial in one variable, then ct[P^{n}Q] mod p is uniformly recurrent for every single-variable Q if and only if ct[P^{n}] mod p is never 0 (which can be checked by finite means; see Proposition 12).

In Theorem 33 and Corollary 34 of Section 5 of this paper, we extend the results of [4] to show that ct[P^{n}Q] mod p^{a} and every sequence built from such sequences is linearly recurrent if and only if ct[P^{n}] mod 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}] mod p = 0 then the frequency of 0 is 1 in every ct[P^{n}Q] mod p^{a} and every sequence built from such sequences. Here, the frequency of a value c in a sequence (s_{n})_{n∈ℕ} is the asymptotic density of {n ∈ ℕ | s_{n} = c}.

This is accomplished by generalizing the proof method of [6, Thm. 10] by using constructions from Shallit’s book The Logical Approach to Automatic Sequences [8] along with some novel constructions introduced in Sections 3 and 4. In Section 3, we construct a p-linear representation (Definition 7) for sequences of the form ct[P^{n}Q] mod 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 [6, Thm. 10]. More generally, this p-linear representation seems to be of independent interest as it generalizes a family of Lucas congruences specified in [4, Prop. 1], 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 5.

1.1 Notation and conventions

Throughout this paper, P and Q are Laurent polynomials in r variables with integer coefficients, coef_{k_{1},...,k_{r}}[Q] is the coefficient of x_{1}^{k_{1}} ⋯ 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_{k_{1},...,k_{r}}^{n} denote coef_{−k_{1},...,−k_{r}}[P (x_{1}, …, x_{r})^{n}] = ct[P (x_{1}, …, x_{r})^{n} · x_{1}^{k_{1}} ⋯ x_{r}^{k_{r}}] so that the (r + 1)-dimensional array a_{k_{1},...,k_{r}}^{n} 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},...,k_{r}} to refer to x_{1}^{k_{1}} ⋯ x_{r}^{k_{r}} and when k = (k_{1}, …, k_{r}) ∈ ℤ^{r}, we simply use x^{k}. Furthermore, for such k the notation p | k means that p divides every entry of k. Unless otherwise specified, vectors are column vectors and u^{tr} is the transpose of u⃗ (which is a row if u⃗ is a column).

If Σ is a set, Σ^{∗} denotes the set of words (i.e., strings) of any length whose characters are from Σ (including the empty word). Let |w| denote the length of a word w ∈ Σ^{∗}. If n is a nonnegative integer, and p is a prime, then let n_{p} ∈ 𝔽_{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 ith digit in the base-p expansion of n so that n = ∑_{i∈ℤ_{≥0}} n_{p}[i]p^{i}, then n_{p} = (n_{p}[0])(n_{p}[1]) ⋯ (n_{p}[|n_{p}|−1]). Please note that in this author’s previous paper [4], 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 [8]. Also note that when working with strings, exponents denote repetition. For example, (p − 1)^{k} ∈ 𝔽_{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_{p}0^{k} for every k.

All morphisms in this paper refer to morphisms of strings, which are maps, f : Σ_{1}^{∗} → Σ_{2}^{∗}, such that f(c_{1}c_{2} ⋯) = f(c_{1})f(c_{2}) ⋯, which can be defined by their action on the elements of Σ_{1}. If for every c ∈ Σ_{1}, |f(c)| = ℓ is constant then we say that f is ℓ-uniform. If a morphism is 1-uniform we call it a coding. We say that a morphism, f : Σ^{∗} → Σ^{∗}, is prolongable on c ∈ Σ if f(c) = cw where w ∈ Σ^{∗} and f^{n}(w) is non-empty for all n ≥ 0; in this case, f^{n}(c) = cwf(w)f^{2}(w) ⋯ f^{n−1}(w) for every n ≥ 0 and the infinite word f^{ω}(c) = cwf(w)f^{2}(w) ⋯ is a fixed point of f (i.e., f(f^{ω}(c)) = f^{ω}(c)).

A sequence, a_{n}, is 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 p-linear representation of rank m of a sequence a_{n} over 𝔽_{p} is a triple (v, γ, w) consisting of row vector from 𝔽_{p}^{m}, a matrix-valued morphism, and column vector from 𝔽_{p}^{m}, respectively. The string morphism γ : 𝔽_{p}^{∗} → Mat_{m×m}(𝔽_{p}) uses matrix multiplication instead of concatenation in its co-domain, such that v · γ(n_{p}) · w ≡ a_{n} (mod p) for all n ∈ ℕ. We frequently replace the domain 𝔽_{p} above with ℤ/p^{a}ℤ except in the input alphabet of γ, which is always 𝔽_{p}. If a_{n} has such a p-linear representation, we say it is p-regular. [8, Thm. 9.6.1] says that a sequence with finitely many values is p-automatic if and only if it is p-regular.

2 Preliminaries

The Rowland-Zeilberger automaton is wonderfully described, with examples, in [7]. Its existence shows that constant term sequences modulo prime powers are p-automatic. The general construction is specified in [7]. We repeat some of that exposition here:

Definition 2. For every positive integer k, define Λ_{k} to be the map from (and to) Laurent polynomials over ℤ (or the induced map on quotient rings) defined by

Λ_{k} ( ∑_{i∈[−m,m]^{r}} q_{i}x^{i}) = ∑_{k|i} q_{i}x^{\frac{i}{k}} .

That is, Λ_{k} deletes terms whose exponents are not all multiples of k and then performs the change of variables x_{j}^{k} ↦ x_{j} for every j.

Lemma 3. For all Laurent polynomials P and Q, all primes p, and all integers n and k, we have

ct[P^{pn+k} · Q] ≡ ct[P^{n} · Λ_{p}(P^{k}Q)] (mod p).

Proof. First note the equivalence often referred to as the “generalized freshman’s dream”, P (x_{1}, …, x_{r})^{p} ≡ P (x_{1}^{p}, …, x_{r}^{p}) (mod p), and then note that the change of variables x_{i}^{p} ↦ x_{i} does not affect constant terms. From these two observations, it follows that

ct[P (x_{1}, …, x_{r})^{pn+k} · Q(x_{1}, …, x_{r})]
≡ ct[P (x_{1}^{p}, …, x_{r}^{p})^{n} · P (x_{1}, …, x_{r})^{k}Q(x_{1}, …, x_{r})]
= ct[P (x_{1}, …, x_{r})^{n} · Λ_{p}(P (x_{1}, …, x_{r})^{k}Q(x_{1}, …, x_{r}))].

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 ∈ 𝔽_{p} that lead to (possibly new) states labeled by Q′ = Λ_{p}(P^{k}Q), 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^{n}Q] mod p is a p-automatic sequence.

Lemma 4. For a fixed P, if we define Λ_{p}^{k}(Q) = Λ_{p}(P^{k}Q), then

m := max(deg(P) − 1, deg(Q)) ≥ deg Λ_{p}^{k_{t}}(⋯ Λ_{p}^{k_{0}}(Q) ⋯).

That is, m is a bound on the degree of every polynomial that is the result of iterating Λ_{p}^{k} on input Q for all values of k ∈ 𝔽_{p}. In particular, m bounds the degree of every state, Q, appearing in the Rowland-Zeilberger construction.

Proof. If Q_{0} = ∑_{i∈[−m_{0},m_{0}]^{r}} q_{i}x^{i} is of degree m_{0}, then for all k ≤ p − 1, Λ_{p}^{k} is 𝔽_{p}-linear so that Q_{1} = Λ_{p}^{k}(Q_{0}) = ∑_{i∈[−m_{0},m_{0}]^{r}} q_{i}Λ_{p}(P^{k}x^{i}) and deg Q_{1} = max_{i}(deg(Λ_{p}(P^{k}x^{i}))), which depends only on k, m_{0}, and P. For i ≥ 0, letting |(j_{1}, …, j_{r})| = max_{k} j_{k}, and recalling that a_{−j}^{k} = coef_{j}[P^{k}],

Λ_{p}(P^{k}x^{i}) = Λ_{p} ( ∑_{|j|<k deg P} a_{−j}^{k}x^{i+j}) = ∑_{|j|≤k deg P,p|i+j} a_{−j}^{k}x^{\frac{i+j}{p}} .

From this, since |j| ≤ k deg P ⇒ |\frac{i+j}{p} | ≤ \frac{k deg P +|i|}{p} ≤ \frac{(p−1) deg P +|i|}{p}, we can see that

deg Q_{1} ≤ \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} ≤ 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} ≤ 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} ≤ 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 Λ_{p}(P^{k}Q_{0}) < deg P for all k < p − 1, while deg Λ_{p}(P^{p−1}Q_{0}) = deg P.

For a different analysis yielding Lemma 4, see [9, Thm. 2.4].

We use m as defined in Lemma 4 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 [3] (or see [8, Thm. 5.4.1]). Third, every p-automatic sequence is always p-regular and hence has a p-linear representation (v, γ, w), and the converse (p-regular ⇒ p-automatic) is true for sequences taking on finitely many values. This equivalence is [8, Thm. 9.6.1], 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^{n}Q] mod p directly, we instead derive a p-linear representation for a_{n} by using Lemma 3 directly. This yields a generalization of the Lucas congruences for central binomial (OEIS \underline{A000984}) and trinomial (OEIS \underline{A002426}) coefficients, which were the primary tools used in [4] 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}.

3 A novel linear representation

Our p-linear representation is the result of interpreting the Rowland-Zeilberger machine within the vector space of Laurent polynomials over 𝔽_{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.

Definition 5. Recall the definition of m from Lemma 4. We wish to encode Laurent polynomials with coefficients in 𝔽_{p} of degree ≤ m as a product of copies of 𝔽_{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 ≤ m. If Q = ∑_{i∈T} q_{i}x^{i} then let vec(Q) be the row vector (q_{j})_{j∈T} and let code_{Q} : (𝔽_{p}^{T})^{∗} → 𝔽_{p}^{∗} be the coding defined by code_{Q}(u⃗) = vec(Q) · u⃗.

Proposition 6. For every k ∈ 𝔽_{p} and i ∈ T, Λ_{p}(P^{k}x^{i}) = ∑_{j∈T} a_{i−pj}^{k}x^{j}.

Proof. Using the definition of Λ_{p}, we get

coef_{j}[Λ_{p}(P^{k}x^{i})] = coef_{pj}[P^{k}x^{i}] = coef_{pj−i}[P^{k}] = a_{i−pj}^{k}.

Definition 7. Notice that the map Q ↦ Λ_{p}(P^{k}Q) is 𝔽_{p}-linear and maps 𝔽_{p}^{T} (the space of bounded-degree Laurent polynomials) to itself by Lemma 4. Thus, this map corresponds to a matrix with entries in 𝔽_{p}, which we denote by γ(k). This map is determined by its action on the standard basis of monomials (written as row vectors to the left of γ(k)). Therefore, we can deduce from Proposition 6 that

γ(k) := (a_{i−pj}^{k})_{i,j∈T} .

The matrix-valued string morphism, γ, defined in this way along with the row vector 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^{n}Q] mod p. This is because the computation vec(Q) · γ(n_{p}) · V (0) when multiplied from left to right is exactly the computation executed by the Rowland-Zeilberger machine yielding a_{n}.

Put another way: in [8, Section 9.3], 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 [8, Thm. 5.5.1] (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 (vec(Q), γ, V (0)) exactly yields the Rowland-Zeilberger DFAO described in this section.

The matrices, γ(k), of Definition 7 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 ↦ ct[Q], and then read the most significant base-p digit, k, of n in order to update to the new linear functional Q ↦ ct[P^{k}Q]. This process is then repeated until the final linear functional is Q ↦ ct[P^{n}Q], as desired. This observation motivates the following definition and lemma.

Definition 8. Let V (n) be the column vector (a_{i}^{n})_{i∈T} ∈ 𝔽_{p}^{T}, which stores the coefficients of P^{n} whose terms have degree at most m.

Lemma 9. For all non-negative integers n and all k ∈ 𝔽_{p}, we have

γ(k) · V (n) = V (pn + k).

Proof. In view of Lemma 3 and Proposition 6, for all i ∈ T, we have

V (pn + k)[i] = a_{i}^{pn+k}

= ct[P^{pn+k}x^{i}]

≡ ct[P^{n} · Λ_{p}(P^{k}x^{i})] (mod p)

= ct[P^{n} · ∑_{j∈T} a_{i−pj}^{k}x^{j}]

= ∑_{j∈T} a_{i−pj}^{k} · ct[P^{n}x^{j}]

= ∑_{j∈T} a_{i−pj}^{k}a_{j}^{n}

= ((a_{i−pj}^{k})_{i,j∈T} · V (n))[i]

= (γ(k) · V (n))[i].

The result follows.

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 [1, Thm. 4.3.3], 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^{n}Q] mod 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∈ℕ} whose elements are in 𝔽_{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∈ℕ} as a fixed point of a prolongable uniform morphism.

Definition 10. When a Laurent polynomial P, a prime p, and an integer m ≥ deg(P) − 1 (and m ≥ deg Q for every Q that we may be considering) are fixed, we define the p-uniform morphism σ : (𝔽_{p}^{T})^{∗} → (𝔽_{p}^{T})^{∗} by

σ(u⃗) := (γ(0) · u⃗)(γ(1) · u⃗) ⋯ (γ(p − 1) · u⃗).

σ is prolongable on V (0) since γ(0) · V (0) = V (0) by Lemma 9, and so

α := σ^{ω}(V (0)) = V (0)V (1)V (2) ⋯ ∈ (𝔽_{p}^{T})^{∗}

whose nth character is V (n), is a fixed point of σ, i.e., σ(α) = α.

To see that α[n] = V (n), note that

σ(V (j)) = (γ(0) · V (j)) ⋯ (γ(p − 1) · V (j)) = V (pj) ⋯ V (pj + p − 1)

and thus σ(V (0)V (1) ⋯ V (p^{n} − 1)) is equal to

(V (0) ⋯ V (p − 1))(V (p) ⋯ V (p^{2} − 1)) ⋯ (V (p^{n+1} − p) ⋯ V (p^{n+1} − 1)).

In essence, we can fluidly and interchangeably utilize all four (compatible) representations of ct[P^{n}Q]; as the Rowland-Zeilberger DFAO (Lemma 3), as the reverse Rowland-Zeilberger DFAO (Lemma 9), using the p-linear representation of Definition 7, and using a coding of the fixed point of Definition 10. 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 vec(Q) in the p-linear representation; transitions from Q to Q′ labeled by k in the DFAO are such that vec(Q) · γ(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 γ(k) · V (i) = V (j). Lastly, the relation γ(k) · V (n) = V (pn + k) describes the progression of the fixed-point, α, which can be useful for reasoning about properties such as uniform recurrence.

We end this section with a fundamental lemma about γ(0):

Lemma 11. Let C be the index associated with the polynomial 1 in T ’s order. There is an integer s ∈ ℕ such that for every s′ ≥ s, γ(0)^{s′} = γ(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.

Proof. The matrix e_{C,C} is characterized by the fact that for every vector u⃗, u^{tr} · e_{C,C} = (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 vec(Q) for some Q, and vec(Q)·γ(0) = vec(Λ_{p}(P^{0}Q)) = vec(Λ_{p}(Q)). Furthermore, Λ_{p}(Q) has degree at most \frac{0·deg P +deg Q}{p} = \frac{deg Q}{p} as seen in Lemma 4. So letting s′ ≥ s = ⌊log_{p}(deg Q)⌋+1 yields vec(Q) · γ(0)^{s′} = vec((Λ_{p}^{0})^{s′}(Q)) = vec(ct[Q]) = (vec(Q)[C])e_{C}^{tr}, as desired.

This lemma can be thought of as partially explaining some of the connection between the sequences ct[P^{n}Q] and ct[P^{n} · 1] since, beginning with Q, we can always reach a state corresponding to Q′ ∈ 𝔽_{p} ⊂ 𝔽_{p}[x_{1}, …, x_{r}, x_{1}^{−1}, …, x_{r}^{−1}] in some fixed number of steps using γ(0^{s}).

4 Classifying uniformly recurrent constant term sequences mod p

We begin by analyzing the case in which ct[P^{n}Q] mod 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}] mod p can be done by only inspecting a prefix of this sequence.

Proposition 12. Let P be any Laurent polynomial and p be prime. There is a B_{P,p} ∈ ℕ, depending on p and deg(P), so that if there exists some n ∈ ℕ such that p | ct[P^{n}], then there exists an n_{0} ∈ ℕ with n_{0} < B_{P,p} such that p | ct[P^{n_{0}}].

Proof. The Rowland-Zeilberger automaton for ct[P^{n}] mod p contains at most one state for each Laurent polynomial of degree at most deg P − 1, that is, there are at most

p^{|T |} = p^{(2m+1)^{r}} = p^{(2·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·deg(P)−1)^{r}}}, then there must be a 0 in our sequence for some n_{0} < B_{P,p}.

Note that it is similarly possible to check whether a constant term sequence, ct[P^{n}Q], 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^{n}Q] mod 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·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:

Conjecture 13. Proposition 12 holds for B_{P,p} = p^{deg(P)} when P has one variable (r = 1).

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.

Theorem 14. If P is any Laurent polynomial and there exists some n ∈ ℕ such that ct[P^{n}] ≡ 0 (mod p), then the frequency of 0 is 1 in every sequence of the form ct[P^{n}Q] mod p for every Laurent polynomial Q. That is, the set of indices, n, such that ct[P^{n}Q] ≡ 0 (mod p) has density 1. In particular, ct[P^{n}Q] mod p contains arbitrarily large runs of 0s and is either the constant 0 sequence or else it is not uniformly recurrent.

Proof. If p | ct[P^{n_{0}}], then there exists s ∈ ℕ by Lemma 11 such that γ(0)^{s}γ(n_{0})γ(0)^{s} = 0. Because ct[P^{n}Q] ≡ vec(Q) · V (n) = vec(Q) · γ(n) · V (0), all n such that n_{p} contains 0^{s}(n_{0})_{p}0^{s} must have ct[P^{n}Q] ≡ 0. If β = |(n_{0})_{p}|, then consider each n ∈ [0, p^{(β+2s)·k}) as corresponding to an element of (𝔽_{p}^{β+2s})^{k} via its base-p representation chunked into blocks of size β + 2s. If any of the k entries in 𝔽_{p}^{β+2s} for n correspond to 0^{s}(n_{0})_{p}0^{s}, then we know that V (n) = 0 and ct[P^{n}Q] ≡ 0, so at least p^{(β+2s)·k} − (p^{β+2s} − 1)^{k} of such n have ct[P^{n}Q] ≡ 0. Therefore,

the frequency of 0 in ct[P^{n}Q] mod p is at least \frac{p^{(β+2s)·k}−(p^{β+2s}−1)^{k}}{p^{(β+2s)·k}} = 1 − (\frac{p^{β+2s}−1}{p^{β+2s}})^{k} → 1 as k → ∞. In fact, this shows that the frequency of 0 in α (of Definition 10) is 1.

We wish to prove that if 0 does not appear in ct[P^{n}] mod p, then ct[P^{n}Q] mod p is uniformly recurrent. Our main result follows from the following proposition about the morphism σ of Definition 10:

Proposition 15. There exists t_{0} ∈ ℕ such that for all n ∈ ℕ, if p does not divide ct[P^{n}] then σ^{t_{0}}(V (n)) = x_{0}V (0)y_{0} with x_{0}, y_{0} ∈ (𝔽_{p}^{T})^{∗}. That is, V (0) is a character in σ^{t_{0}}(V (n)) for every such n.

Proof. Let s ∈ ℕ such that γ(0)^{s} = e_{C,C}. Next, fix s′ ∈ ℕ such that C-term entries (i.e., indexed by C) of σ^{s′}(V (0)) contain all C-term values of V (i) that occur for any i ∈ ℕ. 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] ∈ 𝔽_{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 γ(0)^{s} · V (n) = (V (n)[C])V (0), σ^{s′+s}(V (0)) contains (V (n)[C])V (0), and (V (n)[C])^{p−1} ≡ 1 (mod p) by Fermat’s little theorem. Therefore, we can conclude that σ^{(s′+s)(p−2)+s}(V (n)) contains V (0), as desired.

Note that t_{0} above does not depend on n. We now have everything we need to prove our main result and more.

Theorem 16. If P and Q are Laurent polynomials with integer coefficients, p is prime, and ct[P^{n}Q] mod p is not the constant 0 sequence, then the sequence ct[P^{n}Q] mod p is linearly recurrent if and only if p does not divide ct[P^{n}] for all 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.

Proof. If there exists an n ∈ ℕ such that p | ct[P^{n}], then Proposition 12 tells us that there is such an n < B_{P,p}. And Theorem 14 tells us that ct[P^{n}Q] mod p is not uniformly recurrent.

For the converse, we show that α from Definition 10 is linearly recurrent, from which the result follows since our sequence is the image of α under code_{Q}. The result [8, Thm. 10.8.4] states that if a p-automatic sequence is uniformly recurrent, it is linearly recurrent. Thus, it is sufficient for us to show that α is uniformly recurrent.

If w appears as a word in α, and its first occurrence ends by index i < p^{t_{1}}, then w appears in σ^{t_{1}}(V (0)) = V (0)V (1) ⋯ V (p^{t_{1}} − 1) since σ is p-uniform. We can conclude from Proposition 15 that for all n ∈ ℕ, and all words w appearing in α,

σ^{t_{1}+t_{0}}(V (n)) = σ^{t_{1}}(x_{0}V (0)y_{0}) = σ^{t_{1}}(x_{0})σ^{t_{1}}(V (0))σ^{t_{1}}(y_{0}) = σ^{t_{1}}(x_{0})x_{1}wy_{1}σ^{t_{1}}(y_{0}).

In other words, w appears in every σ^{t_{1}+t_{0}}(V (n)), and since

α = σ^{t_{1}+t_{0}}(α) = σ^{t_{1}+t_{0}}(V (0))σ^{t_{1}+t_{0}}(V (1))σ^{t_{1}+t_{0}}(V (2)) ⋯

and σ is uniform (so that σ^{t_{1}+t_{0}} is also uniform), this implies that α = V (0)V (1)V (2) ⋯ is uniformly recurrent.

Corollary 17. Let X be any set, let F : 𝔽_{p}^{ℓ} → X (which is deterministic) for some ℓ ∈ ℕ, and let b_{n} = F (ct[P^{n+k_{1}}Q_{1}] mod p, …, ct[P^{n+k_{ℓ}}Q_{ℓ}] mod p) where the k_{i} are arbitrary nonnegative integers and the Q_{i} are arbitrary Laurent polynomials such that b_{n} is not the constant sequence F (0, …, 0). Then b_{n} is linearly recurrent if and only if for all n ∈ ℕ, p does not divide ct[P^{n}]. Furthermore, in the case where there exists n such that p | ct[P^{n}], then the frequency of F (0, …, 0) in b_{n} is 1. For example, if F takes a linear combination of its inputs then we get that b_{n} = ∑_{i=0}^{ℓ} β_{i} · (ct[P^{n+k_{i}}Q_{i}] mod p) for arbitrary β_{i} is linearly recurrent if and only if p does not divide ct[P^{n}] for all n.

Proof. The proof of Theorem 16 actually shows that α = V (0)V (1)V (2) ⋯ 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})) ⋯ V (n_{0} + max(k_{i}) + L), we can conclude that the sequence b_{n} is linearly recurrent when α is. Furthermore, if α is not linearly recurrent, it contains 0 vectors with frequency 1 (by Theorem 14), and hence b_{n} contains F (0, …, 0) with frequency 1.

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

Definition 18. A sequence s_{n} is called recurrent if for every occurrence of a word, w = s_{i}s_{i+1} ⋯ s_{i+ℓ−1}, there is another later occurrence. That is, there is a j > 0 such that w = s_{i+j}s_{i+j+1} ⋯ s_{i+j+ℓ−1}. This is equivalent to saying that every word that appears recurs infinitely often, but there is no bound on gaps between occurrences.

Proposition 19. 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^{n}Q] mod p is recurrent.

Proof. Proposition 15 assures us that σ^{t_{0}}(V (n_{0})) contains V (0). Therefore, if w is a word in α and we consider an occurrence of w that ends by index i < p^{t_{2}}, then w appears in σ^{t_{2}}(V (0)) and thus w appears in σ^{t_{2}+t_{0}}(V (n_{0})). Finally, since

α = σ^{t_{2}+t_{0}}(α) = σ^{t_{2}+t_{0}}(V (0))σ^{t_{2}+t_{0}}(V (1)) ⋯ σ^{t_{2}+t_{0}}(V (n_{0})) ⋯

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, σ^{t_{2}+t_{0}}(V (0)), of the above decomposition of α and there is a subsequent occurrence in the σ^{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.

Question 20. What can be said about the recurrence (or non-recurrence) of ct[P^{n}Q] when ct[P^{n}] ≡ 0 for all n > 0? For example, ct[P^{n}] ≡ 0 for all n > 0 when P (x) = x^{p−1} + x^{−1}.

5 Extending results to prime powers

Analogous results to Theorem 16 and Corollary 17 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 [7] becomes mildly more complicated mod p^{a} for a > 1 because Lemma 3 no longer holds. However, after reading fewer than a base-p digits, we have a result analogous to Lemma 3.

Definition 21. When the integer Laurent polynomial P and modulus p^{a} are fixed, we define P̃(x) to be such that P (x_{1}, …, x_{r})^{p^{a−1}} ≡ P̃(x_{1}^{p^{ℓ}}, …, x_{r}^{p^{ℓ}}) (mod p^{a}) where ℓ is taken to be as large as possible. Note that since P (x_{1}, …, x_{r})^{p} ≡ P (x_{1}^{p}, …, x_{r}^{p}) (mod p), it follows that

P (x_{1}, …, x_{r})^{p^{a}} = (P (x_{1}, …, x_{r})^{p})^{p^{a−1}} ≡ P (x_{1}^{p}, …, x_{r}^{p})^{p^{a−1}} (mod p^{a}).

Thus, P̃(x_{1}^{p^{ℓ}}, …, x_{r}^{p^{ℓ}})^{p} ≡ P̃(x_{1}^{p^{ℓ}·p}, …, x_{r}^{p^{ℓ}·p}) (mod p^{a}), or equivalently, by a change of variables,

P̃(x_{1}, …, x_{r})^{p} ≡ P̃(x_{1}^{p}, …, x_{r}^{p}) (mod p^{a}).

Consequently, P̃ is stable under Rowland-Zeilberger transitions, i.e., ˜ P̃ = P̃. Also note that when a = 1, this section coincides with the previous one if we take P̃ = P.

Lemma 22. For all Laurent polynomials P and primes p, there exists an n_{0} ∈ ℕ such that p | ct[P^{n_{0}}] if and only if there exists an n_{1} ∈ ℕ such that p | ct[P̃^{n_{1}}]. Furthermore, if n_{0} exists one can take n_{1} to be n_{0}.

Proof. Because ct[P̃(x_{1}, …, x_{r})^{n}] = ct[P̃(x_{1}^{p^{ℓ}}, …, x_{r}^{p^{ℓ}})^{n}] = ct[P (x_{1}, …, x_{r})^{p^{a−1}n}], the sequence (ct[P̃^{n}])_{n∈ℕ} is a subsequence of (ct[P^{n}])_{n∈ℕ}. Thus, it is sufficient to show that when ct[P^{n_{0}}] ≢ 0 (mod p), then ct[P̃^{n_{0}}] ≢ 0 (mod p).

By Lemma 11 and Definition 8 we have that γ(0)^{s} · V (n_{0}) ≠ 0. Furthermore, using Lemmas 11 and 9, we get

γ(0)^{s} · V (n_{0}) = γ(0)^{s+a−1} · V (n_{0}) = γ(0)^{s} · γ(0)^{a−1} · V (n_{0}) = γ(0)^{s} · V (p^{a−1}n_{0}) ≠ 0,

from which we can conclude that ct[P̃^{n_{0}}] ≡ ct[P^{p^{a−1}n_{0}}] ≢ 0 (mod p).

We now apply some simple tricks to describe ct[P^{n}Q] (mod p^{a}) in terms of sequences of the form ct[P̃^{n}Q] (mod p^{a}). For P̃, since ct[P̃(x_{1}, …, x_{r})^{p}] ≡ ct[P̃(x_{1}^{p}, …, 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 (∼) in this section. These translations are so direct that we omit proofs for most of the results and instead reference the analogous results above.

Proposition 23. For all Laurent polynomials P and Q, all n ∈ ℕ, and all k ∈ ℤ/p^{a−1}ℤ, we have

ct[P^{p^{a−1}n+k}Q] ≡ ct[P̃^{n} · Λ_{p^{ℓ}}(P^{k}Q)] (mod p^{a}).

Proof.

ct[P (x_{1}, …, x_{r})^{p^{a−1}n+k}Q(x_{1}, …, x_{r})]
= ct[(P (x_{1}, …, x_{r})^{p^{a−1}})^{n}P (x_{1}, …, x_{r})^{k}Q(x_{1}, …, x_{r})]
≡ ct[P̃(x_{1}^{p^{ℓ}}, …, x_{r}^{p^{ℓ}})^{n}P (x_{1}, …, x_{r})^{k}Q(x_{1}, …, x_{r})]
≡ ct[P̃(x_{1}, …, x_{r})^{n}Λ_{p^{ℓ}}(P (x_{1}, …, x_{r})^{k}Q(x_{1}, …, x_{r}))].

Now we can compute ct[P^{n′}Q] mod 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[P̃^{n} · Λ_{p^{ℓ}}(P^{k}Q)] mod p^{a}, where P̃ satisfies P̃(x_{1}, …, x_{r})^{p} ≡ P̃(x_{1}^{p}, …, x_{r}^{p}) (mod p^{a}). Using this congruence, we obtain lemmas analogous to Lemma 3 and Lemma 4 for P̃:

Lemma 24. For all k ∈ 𝔽_{p}, n ∈ ℕ, and all integer Laurent polynomials, P̃(x), satisfying the congruence P̃(x_{1}, …, x_{r})^{p} ≡ P̃(x_{1}^{p}, …, x_{r}^{p}) (mod p^{a}), we have

ct[P̃^{pn+k}Q] ≡ ct[P̃^{n} · Λ_{p}(P̃^{k}Q)] (mod p^{a}).

Lemma 25. For a fixed P̃,

m̃ := max(deg(P̃) − 1, deg(Q_{0})) ≥ deg Λ_{p}^{k_{t}}(⋯ Λ_{p}^{k_{0}}(Q_{0}) ⋯).

That is, m̃ is a bound on the degree of every polynomial that is the result of iterating Λ_{p}^{k} on input Q_{0} for all values of k ∈ 𝔽_{p}. In particular, m̃ bounds the degree of every Q_{0} appearing in the Rowland-Zeilberger construction.

Note that by Proposition 23, the maximum that defines m̃ must be taken over deg(P̃)−1 and Q_{0} = deg(Λ_{p^{ℓ}}(P^{k}Q)) for all k ∈ ℤ/p^{a−1}ℤ for all values of Q we are considering.

Definition 26. We wish to encode Laurent polynomials, with coefficients viewed modulo p^{a}, of degree ≤ m as a product of copies of ℤ/p^{a}ℤ, 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 ≤ m̃. If Q = ∑_{i∈T̃} q_{i}x^{i} then let vec(Q) be the row vector (q_{i})_{i∈T̃} and let code_{Q} : ((ℤ/p^{a}ℤ)T̃)^{∗} → (ℤ/p^{a}ℤ)^{∗} be the coding defined by code_{Q}(u⃗) = vec(Q) · u⃗.

Just as in Definition 7, the map Q ↦ Λ_{p}(P̃^{k}Q) is (ℤ/p^{a}ℤ)-linear and has the following matrix description:

Definition 27. If γ̃(k) := (coef_{pj−i}[P̃^{k}])_{i,j∈T̃}, then vec(Q) · γ̃(k) = vec(Λ_{p}(P̃^{k}Q)). Defining γ̃ as a matrix-valued string morphism in this way yields the p-linear representation (vec(Q), γ̃, Ṽ (0)) for the sequence (ct[P̃^{n}Q] mod p^{a})_{n∈ℕ}, where the only non-zero entry of Ṽ (0) is at the index corresponding to the constant term, where it is 1. More generally, define Ṽ (n) to be the column vector (ct[P̃^{n}x^{i}] mod p^{a})_{i∈T̃} ∈ (ℤ/p^{a}ℤ)T̃.

Just as with Lemma 9:

Lemma 28. For all non-negative integers n and all k ∈ 𝔽_{p}, we have

γ̃(k) · Ṽ (n) = Ṽ (pn + k).

Definition 29. Just as in Definition 10, we use γ̃ to define the p-uniform string morphism σ̃ : ((ℤ/p^{a}ℤ)T̃)^{∗} → ((ℤ/p^{a}ℤ)T̃)^{∗} by

σ̃(u⃗) := (γ̃(0) · u⃗)(γ̃(1) · u⃗) ⋯ (γ̃(p − 1) · u⃗).

Then define α̃ := σ̃^{ω}(Ṽ (0)) = Ṽ (0)Ṽ (1)Ṽ (2) ⋯ ∈ ((ℤ/p^{a}ℤ)T̃)^{∗}.

Just as with Lemma 11:

Lemma 30. Let C be the index of the polynomial 1 in T̃’s order. There is an integer s ∈ ℕ such that for every s′ ≥ s ∈ ℕ, γ̃(0)^{s} = γ̃(0^{s}) = e_{C,C}, that is to say, it has a 1 in the row and column corresponding to the constant term and 0s everywhere else.

In analogy with Theorem 14:

Lemma 31. If P̃ is a Laurent polynomial satisfying P̃(x_{1}, x_{2}, …, x_{r})^{p} ≡ P̃(x_{1}^{p}, x_{2}^{p}, …, x_{r}^{p}) (mod p^{a}) and there exists some n_{0} ∈ ℕ such that ct[P̃^{n_{0}}] ≡ 0 (mod p), then the frequency of 0 is 1 in every sequence of the form ct[P̃^{n}Q] mod p^{a} for every Laurent polynomial Q.

Proof. If p | ct[P̃^{n_{0}}], then γ̃(0)^{s}γ̃(n_{0})γ̃(0)^{s} is a zero-divisor multiple of e_{C,C}, so that there exists some t such that (γ̃(0)^{s}γ̃(n_{0})γ̃(0)^{s})^{t} = 0. Since ct[P̃^{n}Q] ≡ vec(Q) · Ṽ (n) = vec(Q) · γ̃(n) · Ṽ (0) all n such that n_{p} contains (0^{s}(n_{0})_{p}0^{s})^{t} must have ct[P̃^{n}Q] ≡ 0 (mod p^{a}).

If β = |(n_{0})_{p}|, then consider each n ∈ [0, p^{t(β+2s)·k}) as corresponding to an element of (𝔽_{p}^{t(β+2s)})^{k} via its base-p representation chunked into blocks of size t(β + 2s). If any of the k entries for n correspond to (0^{s}(n_{0})_{p}0^{s})^{t}, then we know that Ṽ (n) = 0 and ct[P̃^{n}Q] ≡ 0, so at least p^{t(β+2s)·k} − (p^{t(β+2s)} − 1)^{k} of such n have ct[P̃^{n}Q] ≡ 0. Therefore, the frequency of

0 in ct[P̃^{n}Q] mod p^{a} is at least \frac{p^{t(β+2s)·k}−(p^{t(β+2s)}−1)^{k}}{p^{t(β+2s)·k}} = 1 − (\frac{p^{t(β+2s)}−1}{p^{t(β+2s)}})^{k} → 1 as k → ∞. In fact, this shows that the frequency of 0 in α̃ is 1.

The last thing we need before we can prove our main results is the following proposition analogous to Proposition 15:

Proposition 32. There exists t_{0} ∈ ℕ such that for all n ∈ ℕ, if p does not divide ct[P̃^{n}] then σ̃^{t_{0}}(Ṽ (n)) = x_{0}Ṽ (0)y_{0} with x_{0}, y_{0} ∈ ((ℤ/p^{a}ℤ)T̃)^{∗}. That is, Ṽ (0) is a character in σ̃^{t_{0}}(Ṽ (n)) for every such n.

Proof. Let s ∈ ℕ such that γ̃(0)^{s} = e_{C,C}. Next, fix s′ ∈ ℕ such that C-term entries (i.e., indexed by C) of σ̃^{s′}(Ṽ (0)) contain all C-term values of Ṽ (i) that ever occur for any i ∈ ℕ. Recall that the C-term value of Ṽ (i) is the constant coefficient of P̃^{i}. Note that Ṽ (n)[C] ≢ 0 (mod p^{a}) by our assumption that p does not divide ct[P̃^{n}]. Finally, we have that γ̃(0)^{s} · Ṽ (n) = (Ṽ (n)[C])Ṽ (0), σ̃^{s′+s}(Ṽ (0)) contains (Ṽ (n)[C])Ṽ (0), and (Ṽ (n)[C])^{φ(p^{a})} = 1 by Euler’s theorem (where φ is Euler’s totient function). Therefore, we can conclude that σ̃^{(s′+s)(φ(p^{a})−1)+s}(Ṽ (n)) contains Ṽ (0), as desired.

Note that t_{0} does not depend on n. We are now ready to state our main result.

Theorem 33. If P and Q are Laurent polynomials with integer coefficients, p^{a} is a prime power, and ct[P^{n}Q] mod p^{a} is not the constant 0 sequence, then the sequence ct[P^{n}Q] mod p^{a} is linearly recurrent if and only if p does not divide ct[P^{n}] for all 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.

Proof. For every k ∈ ℤ/p^{a−1}ℤ and Laurent polynomial Q, define

code_{Q,k}(u⃗) = vec(Λ_{p^{ℓ}}(P^{k}Q)) · u⃗

where u⃗ is from (ℤ/p^{a}ℤ)T̃. Then for Laurent polynomials P and Q, define the coding

code_{P,Q}(u⃗) = (code_{Q,0}(u⃗), code_{Q,1}(u⃗), …, code_{Q,p^{a−1}−1}(u⃗)) ∈ (ℤ/p^{a}ℤ)^{p^{a−1}}.

Let ι : ((ℤ/p^{a}ℤ)^{p^{a−1}})^{∗} → (ℤ/p^{a}ℤ)^{∗} denote the morphism determined by the canonical injection on letters,

ι(j_{1}, j_{2}, …, j_{p^{a}−1}) = j_{1}j_{2} ⋯ j_{p^{a}−1}.

Then, by Proposition 23, the sequence

β := ι(code_{P,Q}(α̃))

has ct[P^{n}Q] mod p^{a} as its nth term.

If there is some n_{0} ∈ ℕ such that p | ct[P^{n_{0}}], then Lemma 22 gives an n_{1} ∈ ℕ with p | ct[P̃^{n_{1}}]. By Lemma 31, the frequency of 0 in α̃ is 1, and consequently the frequency of 0 in β is 1. In particular, β is not uniformly recurrent.

If there is no such n_{0}, and if w appears as a word in β, then we can extend w to a word w′ in β corresponding to a word in α̃. 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 α̃ is uniformly recurrent as this forces uniform recurrence for w′ and consequently for w.

Given a word w in α̃, choose t_{1} such that w has its first occurrence ending before the index p^{t_{1}}. Thus, w appears in σ̃^{t_{1}}(Ṽ (0)). We can conclude from Proposition 32 that for all n ∈ ℕ,

σ̃^{t_{1}+t_{0}}(Ṽ (n)) = σ̃^{t_{1}}(x_{0}Ṽ (0)y_{0}) = σ̃^{t_{1}}(x_{0})x_{1}wy_{1}σ̃^{t_{1}}(y_{0}).

In other words, w appears in every σ̃^{t_{1}+t_{0}}(Ṽ (n)), and since

α̃ = σ̃^{t_{1}+t_{0}}(α̃) = σ̃^{t_{1}+t_{0}}(Ṽ (0))σ̃^{t_{1}+t_{0}}(Ṽ (1))σ̃^{t_{1}+t_{0}}(Ṽ (2)) ⋯

and σ̃ is uniform (so that σ̃^{t_{1}+t_{0}} is also uniform), this implies that α̃ is uniformly recurrent, and in turn β is uniformly recurrent. Finally, [8, Thm. 10.8.4] tells us that p-automatic uniformly recurrent sequences are linearly recurrent.

Counterintuitively, this theorem shows that ct[P^{n}Q] mod p^{a} is linearly recurrent or else 0 has frequency 1 for all values a ≥ 1 simultaneously. Furthermore, just as in Corollary 17, the same generalization applies to prime powers:

Corollary 34. Let X be any set, let F : (ℤ/p^{a}ℤ)^{ℓ} → X (which is deterministic) for some ℓ ∈ ℕ, and let b_{n} = F (ct[P^{n+k_{1}}Q_{1}] mod p^{a}, …, ct[P^{n+k_{ℓ}}Q_{ℓ}] mod 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, …, 0). Then b_{n} is linearly recurrent if and only if for all n ∈ ℕ, p does not divide ct[P^{n}]. Furthermore, in the case where there exists n such that p | ct[P^{n}], then the frequency of F (0, …, 0) in b_{n} is 1.

Lastly, using the same construction of β as in the proof of Theorem 33, we have the analogous result to Proposition 19 where we can refer to P and not P̃ because we have Lemma 22:

Proposition 35. 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}}] mod p ≠ 0, then the sequence b_{n} = ct[P^{n}Q] mod p^{a} is recurrent.

6 Application to representation theory

In this section, we briefly interpret Theorem 33 (or more precisely, Corollary 34) in the context of sequential tensor powers of semisimple Lie algebra representations. This context is a great source of constant term sequences.

Let 𝔤 be a semisimple Lie algebra, and let V be a representation of 𝔤 whose formal character is P ∈ ℤ[x, x^{−1}]. If W is an irreducible representation of 𝔤, then let a_{W,n} denote the multiplicity of W in the direct sum decomposition of V^{⊗n}, which has character P^{n}. It is a consequence of the Weyl integral formula (see, for example, [2, Section IV.1]) 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 · a_{W,n} = ct[P^{n}Q], where C is the order of the Weyl group. The following theorem follows as a result of Corollary 34.

Theorem 36. Let 𝔤 be a semisimple Lie algebra whose irreducible representations are {W_{i}} and let V be a representation of 𝔤 whose formal character is P ∈ ℤ[x, x^{−1}]. Let a_{i,n} denote the multiplicity of W_{i} in the direct sum decomposition of V^{⊗n}. Then for each prime p, either all of the sequences (a_{i,n} mod p^{a})_{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 ≥ 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 | ct[P^{n_{0}}].

Example 37. Consider 𝔤 = 𝔰𝔩_{2}, which has one irreducible representation, L_{n}, of dimension n+1 for each n ≥ 0. The character of L_{d} is x^{−d} +x^{−d+2} +⋯+x^{d−2} +x^{d}. Let us characterize the consequences of Theorem 36 for the sequences a_{i,n} described by the multiplicity of L_{i} in the direct sum decomposition of L_{2}^{⊗n}. It is straightforward to use characters to verify that L_{2} ⊗ L_{m} ≅ L_{m−2} ⊕ L_{m} ⊕ L_{m+2} for all m ≥ 2. Hence, a_{i,n} is the zero sequence for all odd i. More generally, since the Weyl denominator of 𝔤 is x − x^{−1} and the Weyl group of 𝔤 has order C = 2, we can conclude that

2 · a_{i,n} = ct[(x^{−2} + 1 + x^{2})^{n}(x^{−i−2} − x^{−i} − x^{i} + x^{i+2})] = 2 · 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 33 that for all a ≥ 1 and every even i, the sequences (a_{i,n})_{n∈ℕ} (mod p^{a}) are all simultaneously linearly recurrent if and only if p is in the sequence \underline{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.

References

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[2] T. Bröcker and T. tom Dieck, Representations of Compact Lie Groups, Springer, 1985.

[3] A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.

[4] N. Kohen, Uniform recurrence in the Motzkin numbers and related sequences mod p, Electron. J. Combin. 32 (2025), Paper No. P2.44.

[5] H. Mousavi, Automatic theorem proving in Walnut, arxiv preprint arXiv:1603.06017

   [cs.FL], 2021. Available at https://arxiv.org/abs/1603.06017.

[6] N. Rampersad and J. Shallit, Congruence properties of combinatorial sequences via Walnut and the Rowland-Yassawi-Zeilberger automaton, Electron. J. Combin. 29 (2022), Paper No. 3.36.

[7] E. S. Rowland and D. Zeilberger, A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences, J. Difference Equ. Appl. 20 (2014), 973–988.

[8] J. Shallit, The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut, Cambridge University Press, 2022.

[9] A. Straub, On congruence schemes for constant terms and their applications, Res. Number Theory 8 (2022), Paper No. 42.

2020 Mathematics Subject Classification: Primary 11B50; Secondary 11B85, 68R15. Keywords: constant term sequence, uniform recurrence, linear recurrence, linear representation, automatic sequence, Rowland-Zeilberger automaton, Motzkin number.

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

Received May 1 2025; revised version received June 14 2026. Published in Journal of Integer Sequences, June 30 2026.

Return to Journal of Integer Sequences home page.