A METHOD FOR DETERMINING THE MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES (WITH EXPANDED APPENDIX)

C. KRATTENTHALER^{†} AND T. W. MÜLLER^{∗}

Abstract. We present a method for obtaining congruences modulo powers of 3 for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Motzkin numbers, Riordan numbers, Schröder numbers, Eulerian numbers, trinomial coefficients, Delannoy numbers, and to functions counting free subgroups of finite index in the inhomogeneous modular group and its lifts. This leads to numerous new results, including many extensions of known results to higher powers of 3.

1. Introduction

In [3], Deutsch and Sagan present a rather systematic study of the behaviour of Catalan and Motzkin numbers and related sequences (mostly) modulo 2 and 3. In order to arrive at their results, they use clever ad hoc arguments, combining combinatorial and computational techniques. The results in [3] which are of particular interest to us here are those concerning the modulus 3. One finds numerous such theorems there, determining the behaviour of Motzkin numbers, Motzkin prefix numbers, Riordan numbers, central trinomial coefficients, central binomial coefficients, Catalan numbers, central Delannoy numbers, Schröder numbers, hex tree numbers, central Eulerian numbers, and Apéry numbers modulo 3. The purpose of the present paper is to demonstrate that, with the exception of the Apéry numbers, all these — seemingly unrelated — results are in fact direct consequences of a single “master theorem,” namely Theorem 17 in Section 6. Moreover, this same theorem also allows us to refine all these results to congruences modulo arbitrary powers of 3.

A second motivation for our paper comes from [11]. In Theorem 3(i) of that paper, the number of free subgroups of given index in the inhomogeneous modular group P SL_{2}(ℤ) is considered modulo 3. Our original goal was to extend that theorem to higher powers of 3. The corresponding results are described in Section 16. In the course of our work on this problem, we became aware of the paper [3] of Deutsch and Sagan, which pointed the way to many further applications of the method used, and, in particular, to the unifying “master theorem,” of which the numbers of free subgroups of given index in P SL_{2}(ℤ) constitute one instance.

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05E99 11A07 20E06 20E07 68W30.

Key words and phrases. Polynomial recurrences, free subgroup numbers, Catalan numbers, Motzkin numbers, Riordan numbers, Schröder numbers, Eulerian numbers, trinomial coefficients, Delannoy numbers.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”

∗Research supported by Lise Meitner Grant M1201-N13 of the Austrian Science Foundation FWF.

This master theorem embeds itself into a general method which applies to sequences given by a recurrence of finite depth with polynomial coefficients, and gives rise to congruences modulo arbitrarily large powers of 3. More precisely, let

Ψ(z) = ∑_{k≥0} ∑_{n_{1}>···>n_{k}≥0} z^{3^{n_{1}}+3^{n_{2}}+···+3^{n_{k}}} = ∏_{j=0}^{∞}(1 + z^{3^{j}}).  (1.1)

Suppose we are given an integer sequence (f_{n})_{n≥0}, whose generating function F (z) = ∑_{n≥0} f_{n} z^{n} satisfies a (formal) differential equation of the form

P(z; F (z), F′(z), F′′(z), …, F^{(s)}(z)) = 0,  (1.2)

where P is a polynomial with integer coefficients, which has a unique power series solution F (z) with integer coefficients. (In the literature, series obeying a polynomial relation of the form (1.2) are known as differentially algebraic series; see, for instance, [1].) In its simplest form, what our method affords is an algorithmic procedure to find a polynomial in the basic series Ψ(z) given by (1.1) with coefficients which are Laurent polynomials in z and 1 + z, such that this polynomial agrees with F (z) when coefficients are reduced modulo some given power of 3. It turns out that, to make the method more flexible, in applications one will also have to use variations of the basic series Ψ(z) obtained by substitutions of the variable z. See Section 4 for the description of the method and these variations.

We point out that this method is in the spirit of the one developed in [7], where a generating function method was described to determine the behaviour of recursive sequences modulo powers of 2. The most significant difference lies in the choice of the basic series. In [7], one works with the series Φ(z) = ∑_{n≥0} z^{2^{n}} and variations thereof, whereas here we put the series Ψ(z) in the focus of our attention. A second notable difference is that, because of the particular behaviour of powers of Ψ(z) modulo 3, we have to allow powers of 1 + z as denominators in the coefficients of the polynomials of Ψ(z) that we are considering here. (In [7], coefficients of the polynomials in Φ(z) were Laurent polynomials in z only.)

The special feature of the aforementioned master theorem, Theorem 17, is that it treats, in a uniform fashion, functional equations of the form (1.2), which, after reduction modulo 3, become quadratic in F (z), apart from satisfying a few more technical conditions. The ubiquity of applications of Theorem 17, which we describe in Sections 7–17, ultimately stems from the fact that numerous combinatorial sequences have generating functions satisfying a quadratic functional equation.

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 3

In the remainder of this introduction, we briefly describe the contents of the paper. The next two sections discuss our main character, the formal power series Ψ(z) defined in (1.1). The announced method for finding congruences for recursive sequences requires knowledge of certain theoretical properties of Ψ(z). First of all, one needs to know how to extract the explicit value of a concrete coefficient in a polynomial expression in Ψ(z) modulo a given 3-power. This is discussed in Section 2. The appendix provides the resulting congruences modulo 27 for the coefficients of Ψ^{3}(z) and Ψ^{5}(z). Section 2 also contains several theoretical results pertaining to dependence/independence of powers of Ψ(z), which are used in Section 3. Second, it is of great interest to know polynomial identities for Ψ(z) modulo a given 3-power which are of minimal degree. These “minimal polynomials” are the subject of Section 3. While it is indeed easy to see that ψ(z) is algebraic modulo powers of 3, the finding of polynomial relations of minimal degree is quite challenging. We provide a lower bound on the minimal degree, which in particular shows that the series Ψ(z) is transcendental over ℤ[z] (see Theorem 10). In Section 4, we describe our method of expressing the generating function of a recursive sequence, when reduced modulo a given 3-power, as a polynomial in Ψ(z) with coefficients that are Laurent polynomials in z and 1 + z.

We then proceed with a first illustration of our method, by applying it to “almost central” binomial coefficients, see Section 5.

The “centrepiece” of our paper is Section 6, which presents the aforementioned master theorem. This theorem describes a general family of functional-differential equations, where our method from Section 4 works in a completely automatic fashion. We demonstrate the power of this theorem in the subsequent sections by applying it — in this order — to Motzkin numbers, Motzkin prefix numbers, Riordan numbers, central trinomial coefficients, central binomial coefficients and their sums, Catalan numbers, central Delannoy numbers, Schröder numbers, hex tree numbers, free subgroup numbers for lifts of the inhomogeneous modular group, and central Eulerian numbers. All congruence results modulo 3 from [3] are derived completely automatically, and moreover we display the generating function results modulo 9 and 27 which are obtained by applying our method. The case of central Eulerian numbers is in fact quite challenging, since it requires several preparations until one sees that our method is actually applicable, see Section 17. It would cover too much space to display the explicit description of the congruence classes modulo 9 or 27 (or higher 3-powers) for all the above sequences, although this only amounts to routine calculations. We therefore confine ourselves to just one illustration, concerning the free subgroup numbers of P SL_{2}(ℤ), our original motivation for this paper; see Section 16.

We close our paper with a short discussion of congruences modulo powers of 3 for Apéry numbers. They provide examples of number sequences where our method does not work. Nevertheless, the pattern which they satisfy modulo 9 seems to be very interesting; see Conjectures 65 and 66.

Note. This paper is accompanied by a Mathematica file and a Mathematica notebook so that an interested reader is able to redo (most of) the computations that are presented in this article. File and notebook are available at the article’s website

http://www.mat.univie.ac.at/~kratt/artikel/3psl2z.html.

2. Coefficient extraction from powers of Ψ(z)

In Section 4 we are going to describe a method for expressing differentially algebraic formal power series, after the coefficients of the series have been reduced modulo 3^{γ}, as polynomials in the Cantor-like series^{1} Ψ(z) (see (1.1) for the definition), the coefficients being Laurent polynomials in z and 1 + z. Such a method would be without value if we could not, at the same time, provide a procedure for extracting coefficients from the series (1+z)^{−L}Ψ^{K}(z), where K and L are non-negative integers. The description of such a procedure is the topic of this section. Roughly speaking, this procedure consists of expanding powers of Ψ(z) in terms of the auxiliary series in (2.3) (see (2.6) and (2.7)), which can be further expanded using only a subclass of these series (see Lemma 9), and then reading the coefficients from these auxiliary series, which is (more or less) straightforward (see the appendix).

1We call it “Cantor-like” since the exponents of the monomials appearing in Ψ(z) all have a ternary expansion consisting of only 1’s and 0’s. This is reminiscent of the ternary expansion of the numbers in the classical Cantor set all of which have a ternary expansion consisting of 2’s and 0’s only.

We begin with an expansion of Ψ^{2}(z), on which all subsequent arguments in this section will be based.

Lemma 1. We have

Ψ^{2}(z) = \frac{1}{1 + z} ∑_{s≥0} ∑_{k_{1}>···>k_{s}≥0} 3^{s} ∏_{j=1}^{s} \frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}}.  (2.1)

In the sum, the term for s = 0 has to be interpreted as 1.

Proof. We have

Ψ^{2}(z) = ∏_{j=0}^{∞}(1 + z^{3^{j}})^{2}

= \frac{1}{1 + z} ∏_{j=0}^{∞} \frac{(1 + z^{3^{j}})^{3}}{1 + z^{3^{j+1}}}

= \frac{1}{1 + z} ∏_{j=0}^{∞} (1 + 3\frac{z^{3^{j}}(1 + z^{3^{j}})}{1 + z^{3^{j+1}}}) .

Expansion of the product directly results into (2.1). □

Remark. The significance of Lemma 1 lies largely in the fact that, if one considers (2.1) modulo a 3-power, then the sum over s on the right-hand side gets truncated. We shall exploit this frequently. The simplest example is the reduction of (2.1) modulo 3. Using the notation

f(z) = g(z) modulo 3^{γ}

to mean that the coefficients of z^{i} in f(z) and g(z) agree modulo 3^{γ} for all i, this reduction of (2.1) explicitly reads

Ψ^{2}(z) = \frac{1}{1 + z} modulo 3.  (2.2)

We shall make use of this congruence later at several points.

For convenience, we write

H̃_{a_{1},a_{2},...,a_{s}}(z) := ∑_{k_{1}>···>k_{s}≥0} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{a_{j}} .  (2.3)

We point out that H̃_{a_{1},a_{2},...,a_{s}}(z) is the monomial quasi-symmetric function

M_{a_{1},a_{2},...,a_{s}}(R(0), R(1), …),

where

R(k) = \frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}}  (2.4)

(cf. [18, p. 357]). Using this notation, Lemma 1 can be rephrased as

Ψ^{2}(z) = \frac{1}{1 + z} ∑_{s≥0} 3^{s}H̃^{1,1,...,1}_{s times}(z).  (2.5)

It is not difficult to see that powers of Ψ(z) can be expressed in the form

Ψ^{2K}(z) = \frac{1}{(1 + z)^{K}} ∑_{r=1}^{K} ∑_{a_{1},...,a_{r}≥1}c_{K}(a_{1}, a_{2}, …, a_{r})H̃_{a_{1},a_{2},...,a_{r}}(z),  (2.6)

respectively as

Ψ^{2K+1}(z) = \frac{1}{(1 + z)^{K}} Ψ(z) ∑_{r=1}^{K} ∑_{a_{1},...,a_{r}≥1}c_{K}(a_{1}, a_{2}, …, a_{r})H̃_{a_{1},a_{2},...,a_{r}}(z),  (2.7)

where the coefficients c_{K}(a_{1}, a_{2}, …, a_{r}) can be determined explicitly.

Consequently, the coefficient extraction problem will be solved if we are able to say how to extract coefficients from the series

(1 + z)^{−L}H̃_{a_{1},a_{2},...,a_{r}}(z) and (1 + z)^{−L}Ψ(z)H̃_{a_{1},a_{2},...,a_{r}}(z).

This is in fact rather straightforward, if one has the patience to distinguish enough subcases. Roughly speaking, one analyses coefficient extraction from the subexpressions

Ψ(z)\frac{1}{(1 + z)^{L}} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{a_{j}}

and

\frac{1}{(1 + z)^{L}} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{a_{j}} .

This is made more precise in the appendix. How this is used is exemplified for the case of free subgroup numbers of the inhomogeneous modular group in Section 16.

It is also important to have information on dependence or independence of the series H̃_{a_{1},a_{2},...,a_{r}}(z). When a_{1}, a_{2}, …, a_{r} vary over all possible choices, the series H̃_{a_{1},a_{2},...,a_{r}}(z) are not linearly independent over the ring (ℤ/3ℤ)[z], or over (ℤ/3^{γ}ℤ)[z] for a positive integer γ.

However, we shall show below (see Corollary 3) that, if we restrict to a_{i}’s which are not divisible by 3, then the corresponding series H̃_{a_{1},a_{2},...,a_{r}}(z), together with the (trivial) series 1, are linearly independent over (ℤ/3ℤ)[z], and hence as well over (ℤ/3^{γ}ℤ)[z] for arbitrary positive integers γ (and also over ℤ[z]). This fact underpins the arguments in the next section.

All other series H̃_{b_{1},b_{2},...,b_{s}}(z), where we do not make any restriction on the b_{i}’s, can be expressed as a linear combination over (ℤ/3^{γ}ℤ)[z, (1 + z)^{−1}] of 1 and the former series, and this can be carried out in an algorithmic fashion; see Lemma 9.

The problem of linear dependence/independence will be disposed of by transferring it to the problem of dependence/independence of simpler series, namely the series

H_{a_{1},a_{2},...,a_{r}}(z) := ∑_{n_{1}>n_{2}>···>n_{r}≥0} z^{a_{1}3^{n_{1}}+a_{2}3^{n_{2}}+···+a_{r}3^{nr}} .

These series are in fact the analogues for the prime 3 of series which were considered in [7, Sec. 3] for the prime 2, and which were instrumental there in a theory for solving differential and functional equations modulo powers of 2. To see their relevance in the present context, one should observe that

H̃_{a_{1},a_{2},...,a_{r}}(z) = ∑_{k_{1}>···>k_{r}≥0} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{a_{j}}

= ∑_{k_{1}>···>k_{r}≥0} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z)^{3^{k_{j}}}}{(1 + z)^{3^{k_{j} +1}}} )^{a_{j}} modulo 3

= H_{a_{1},a_{2},...,a_{r}} (\frac{z}{(1 + z)^{2}} ) modulo 3.  (2.8)

The idea which we have in mind is that, as a result of the last congruence, independence of (certain) series H_{a_{1},a_{2},...,a_{r}}(z) implies a fortiori independence of the corresponding series H̃_{a_{1},a_{2},...,a_{r}}(z).

The auxiliary results which follow now are analogues of Lemma 6, Corollary 7, and Lemma 9 in [7]. The first of these pertains to the uniqueness of representations of integers as sums of powers of 3 with multiplicities, tailor-made for application to the series H_{a_{1},a_{2},...,a_{r}}(z).

Lemma 2. Let d, r, s be positive integers with r ≥ s, c an integer with |c| ≤ d, and let a_{1}, a_{2}, …, a_{r} respectively b_{1}, b_{2}, …, b_{s} be two sequences of integers, none of them divisible by 3, with 1 ≤ a_{i} ≤ d for 1 ≤ i ≤ r, and 1 ≤ b_{i} ≤ d for 1 ≤ i ≤ s. If

a_{1}3^{2rd} + a_{2}3^{2(r−1)d} + ⋯ + a_{r}3^{2d} = b_{1}3^{n_{1}} + b_{2}3^{n_{2}} + ⋯ + b_{s}3^{n_{s}} + c  (2.9)

for integers n_{1}, n_{2}, …, n_{s} with n_{1} > n_{2} > ⋯ > n_{s} ≥ 0, then r = s, c = 0, a_{i} = b_{i}, and n_{i} = 2d(r + 1 − i) for i = 1, 2, …, r.

Proof. We use induction on r.

First, let r = 1. Then s = 1 as well, and (2.9) becomes

a_{1}3^{2d} = b_{1}3^{n_{1}} + c.  (2.10)

If n_{1} > 2d, then the above equation, together with the assumption that a_{1} is not divisible by 3, implies

a_{1}3^{2d} ≡ c modulo 3^{2d+1}.

However, by assumption, we have |c| ≤ d < a_{1}3^{2d}, which is absurd.

If d < n_{1} < 2d, then it follows from (2.10) that c must be divisible by 3^{n_{1}}. Again by assumption, we have |c| ≤ d < 3^{d} < 3^{n_{1}}, so that c = 0. But then (2.10) cannot be satisfied since b_{1} is assumed not to be divisible by 3.

If 0 ≤ n_{1} ≤ d, then we estimate

b_{1}3^{n_{1}} + c ≤ d (3^{d} + 1) ≤ (3^{d} − 1)(3^{d} + 1) < 3^{2d},

which is again a contradiction to (2.10).

The only remaining possibility is n_{1} = 2d. If this is substituted in (2.10) and the resulting equation is combined with |c| ≤ d < 3^{2d}, then the conclusion is that the equation can only be satisfied if c = 0 and a_{1} = b_{1}, in accordance with the assertion of the lemma.

We now perform the induction step. We assume that the assertion of the lemma is established for all r < R, and we want to show that this implies its validity for r = R. Let t be maximal such that n_{t} ≥ 2d. Then reduction of (2.9) modulo 3^{2d} yields

b_{t+1}3^{n_{t+1}} + b_{t+2}3^{n_{t+2}} + ⋯ + b_{s}3^{n_{s}} + c ≡ 0 modulo 3^{2d}.  (2.11)

Let us write b · 3^{2d} for the left-hand side in (2.11). Then, by dividing (2.9) (with R instead of r) by 3^{2d}, we obtain

a_{1}3^{2(R−1)d}+a_{2}3^{2(R−2)d}+⋯+a_{R−1}3^{2d} = b_{1}3^{n_{1}−2d}+b_{2}3^{n_{2}−2d}+⋯+b_{t}3^{n_{t}−2d}+b−a_{R}. (2.12)

We have

0 ≤ b ≤ 3^{−2d}d (3^{2d−1} + 3^{2d−2} + ⋯ + 3^{2d−s+t} + 1)
≤ 3^{−2d}d (\frac{1}{2}(3^{2d} − 3^{2d−s+t}) + 1) ≤ d.

Consequently, we also have |b − a_{R}| ≤ d. This means that we are in a position to apply the induction hypothesis to (2.12). The conclusion is that t = R−1, b−a_{R} = 0, a_{i} = b_{i}, and n_{i} = 2d(R + 1 − i) for i = 1, 2, …, R − 1. If this is used in (2.9) with r = R, then we obtain

a_{R}3^{2d} = c

or

a_{R}3^{2d} = b_{R}3^{n_{R}} + c,

depending on whether s = R − 1 or s = R. The first case is absurd since c ≤ d < 3^{2d} ≤ a_{R}3^{2d}. On the other hand, the second case has already been considered in (2.10), and we have seen there that it follows that c = 0, a_{R} = b_{R}, and n_{R} = 2d.

This completes the proof of the lemma. □

The independence of the series H_{a_{1},a_{2},...,a_{r}}(z) with all a_{i}’s not divisible by 3 is now an easy consequence.

Corollary 3. The series H_{a_{1},a_{2},...,a_{r}}(z), with all a_{i}’s not divisible by 3, together with the series 1 are linearly independent over (ℤ/3ℤ)[z], and consequently as well over (ℤ/3^{γ}ℤ)[z] for an arbitrary positive integer γ, and over ℤ[z].

Proof. Let us suppose that

p_{0}(z) + ∑_{i=1}^{N} p_{i}(z)H_{a_{1}^{(i)},a_{2}^{(i)},...,a_{r_{i}}^{(i)}}(z) = 0,  (2.13)

where the p_{i}(z)’s are non-zero polynomials in z over ℤ/3ℤ (respectively over ℤ/3^{γ}ℤ or over ℤ), the r_{i}’s are positive integers, and a_{j}^{(i)}, j = 1, 2, …, r_{i}, i = 1, 2, …, N, are integers not divisible by 3. We may also assume that the tuples (a_{1}^{(i)}, a_{2}^{(i)}, …, a_{r_{i}}^{(i)}), i = 1, 2, …, N, are pairwise distinct. Choose i_{0} such that r_{i_{0}} is maximal among the r_{i}’s. Without loss of generality, we may assume that the coefficient of z^{0} in p_{i_{0}}(z) is non-zero (otherwise we could multiply both sides of (2.13) by an appropriate power of z). Let d be the maximum of all a_{j}^{(i)}’s and the absolute values of exponents of z appearing in monomials with non-zero coefficient in the polynomials p_{i}(z), i = 0, 1, …, N. Then, according to Lemma 2 with r = r_{i_{0}}, a_{j} = a_{j}^{(i_{0})}, j = 1, 2, …, r_{i_{0}}, the coefficient of

z^{a_{1}^{(i_{0})}3^{2rd}+a_{2}^{(i_{0})}3^{2(r−1)d}+···+a_{r}^{(i_{0})}3^{2d}}

is 1 in H_{a_{1}^{(i_{0})},a_{2}^{(i_{0})},...,a_{r_{i_{0}}}^{(i_{0})}}(z), while it is zero in series z^{e}H_{a_{1}^{(i_{0})},a_{2}^{(i_{0})},...,a_{r_{i_{0}}}^{(i_{0})}}(z), where e is a

non-zero integer with |e| ≤ d, and in all other series z^{e}H_{a_{1}^{(i)},a_{2}^{(i)},...,a_{r_{i}}^{(i)}}(z), i = 1, …, i_{0} − 1, i_{0} + 1, …, N, where e is a (not necessarily non-zero) integer with |e| ≤ d. This contradiction to (2.13) establishes the assertion of the corollary. □

In view of (2.8), the same result holds for the series H̃_{a_{1},a_{2},...,a_{r}}(z).

Corollary 4. The series H̃_{a_{1},a_{2},...,a_{r}}(z), with all a_{i}’s not divisible by 3, together with the series 1 are linearly independent over (ℤ/3ℤ)[z], and consequently as well over (ℤ/3^{γ}ℤ)[z] for an arbitrary positive integer γ, and over ℤ[z].

The reader should recall from (2.6) and (2.7) that even powers of Ψ(z) can be expanded in the series H̃_{a_{1},a_{2},...,a_{s}}(z), while odd powers can be expanded in the series Ψ(z)H̃_{a_{1},a_{2},...,a_{s}}(z). The next lemma shows that these two families of series are linearly independent from each other.

Lemma 5. Let γ be a positive integer. If

∑_{j=0}^{N} a_{2j}(z)Ψ^{2j}(z) = ∑_{j=1}^{N} a_{2j−1}(z)Ψ^{2j−1}(z)  (2.14)

for polynomials a_{i}(z) in z over ℤ/3^{γ}ℤ, then both sides in (2.14) must be zero.

Proof. We use the expansions (2.6) and (2.7). This leads to a relation of the form

∑ c_{a_{1},a_{2},...,a_{s}}(z)H̃_{a_{1},a_{2},...,a_{s}}(z) = Ψ(z) ∑ d_{a_{1},a_{2},...,a_{s}}(z)H̃_{a_{1},a_{2},...,a_{s}}(z),  (2.15)

for certain polynomials c_{a_{1},a_{2},...,a_{s}}(z) and d_{a_{1},a_{2},h...,a_{s}}(z) in z. We consider this relation modulo 3. By (2.8), we then have

∑ c_{a_{1},a_{2},...,a_{s}}(z)H_{a_{1},a_{2},...,a_{s}} (\frac{z}{(1 + z)^{2}} )

= Ψ(z) ∑ d_{a_{1},a_{2},...,a_{s}}(z)H_{a_{1},a_{2},...,a_{s}} (\frac{z}{(1 + z)^{2}} ) modulo 3.

Next we apply the square root to both sides of (2.2), to obtain

Ψ(z) = (1 + z)^{−1/2} modulo 3.

Substitution of this congruence in the congruence above then yields

∑ c_{a_{1},a_{2},...,a_{s}}(z)H_{a_{1},a_{2},...,a_{s}} (\frac{z}{(1 + z)^{2}} )

= (1 + z)^{−1/2} ∑ d_{a_{1},a_{2},...,a_{s}}(z)H_{a_{1},a_{2},...,a_{s}} (\frac{z}{(1 + z)^{2}} ) modulo 3. (2.16)

Now we expand both sides as Laurent series in 1 + z, allowing only a finite number of positive powers of 1 + z. In order to do so, we observe that

\frac{z^{k}}{(1 + z)^{2k}} = ∑_{ℓ=0}^{k}(−1)^{ℓ}\binom{k}{ℓ}(1 + z)^{−k−ℓ}.

This is used in each term of the expansions corresponding to H_{a_{1},a_{2},...,a_{s}}(z/(1 + z)^{2}). As a consequence, we see that the left-hand side of (2.16) is a (formal) Laurent series in 1 + z with only finitely many positive powers of 1 + z, while the right-hand side is a Laurent series in 1+z of the same type, but multiplied by (1+z)^{−1/2}. This contradiction completes the proof of the lemma. □

We may now combine Corollary 4 and Lemma 5.

Theorem 6. The series H̃_{a_{1},a_{2},...,a_{r}}(z) and Ψ(z)H̃_{a_{1},a_{2},...,a_{r}}(z), with all a_{i}’s not divisible by 3, together with the series 1 are linearly independent over (ℤ/3ℤ)[z], and consequently as well over (ℤ/3^{γ}ℤ)[z] for an arbitrary positive integer γ, and over ℤ[z].

In order to show that each H̃_{b_{1},b_{2},...,b_{s}}(z) can be expressed as a linear combination over (ℤ/3^{γ}ℤ)[z, (1 + z)^{−1}] of the series 1 and series of the form H̃_{a_{1},a_{2},...,a_{r}}(z), where none of the a_{i}’s is divisible by 3 (see Lemma 9 below), we need two auxiliary identities, which are the subject of the following two lemmas.

Lemma 7. Let n and k be positive integers. Then

(\frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}})^{3n} = ∑_{b≥0} 3^{b}\binom{−n}{b} (\frac{z^{3^{k+1}}(1 + z^{3^{k+1}})}{1 + z^{3^{k+2}}})^{n+b}

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{n}{a}\binom{−n}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· (\frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}})^{3(∥s∥+n+b)+∥t∥+a} , (2.17)

where, by convention, s_{0} = n + b, and we write ∥s∥ for s_{1} + s_{2} + ⋯, with an analogous meaning for ∥t∥.

Proof. First we argue that the sum in (2.17) is well-defined as a formal power series. Namely, given a positive integer n + b, non-zero summands in (2.17) arise only for n + b = s_{0} ≥ s_{1} ≥ s_{2} ≥ · · ·. Hence, if we concentrate on vectors s and t for which ∥s∥ + ∥t∥ = N, with N a fixed positive integer, then there is only a finite number of vectors s for which non-zero summands exist. In particular, we have s_{i} = 0 for i > N. In its turn, this entails t_{i} = 0 for i > N if one wants to have a non-vanishing summand. Therefore there are as well only finitely many possibilities for vectors t with ∥t∥ ≤ N.

Now, in order to prove the identity in (2.17), we start with the expansion

(\frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}})^{3n} = z^{3^{k+1}n} \frac{(1 + z^{3^{k+1}})^{n}}{(1 + z^{3^{k+2}})^{n}} \begin{matrix}(1 + 3z^{3^{k}} \frac{1+z^{3^{k}}}{1+z^{3^{k+1}}} ) & n \\ (1 + 3z^{3^{k+1}} \frac{1+z^{3^{k+1}}}{1+z^{3^{k+2}}} ) & n \end{matrix}

= ∑_{a,b≥0} 3^{a+b}\binom{n}{a}\binom{−n}{b} (\frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}})^{a} (\frac{z^{3^{k+1}}(1 + z^{3^{k+1}})}{1 + z^{3^{k+2}}})^{n+b} . (2.18)

The part of the double sum consisting of the terms with a = 0 directly yields the first sum on the right-hand side of (2.17). If a ≥ 1, we want “to get rid of” the power with exponent n + b. In order to do so, we observe that, for an arbitrary positive integer m, we have

(\frac{z^{3^{k+1}}(1 + z^{3^{k+1}})}{1 + z^{3^{k+2}}})^{m} = z^{3^{k+1}m} \frac{(1 + z^{3^{k}})^{3m}}{(1 + z^{3^{k+1}})^{3m}} \begin{matrix}(1 + 3z^{3^{k+1}} \frac{1+z^{3^{k+1}}}{1+z^{3^{k+2}}} ) & m \\ (1 + 3z^{3^{k}} \frac{1+z^{3^{k}}}{1+z^{3^{k+1}}} ) & m \end{matrix}

= ∑_{s_{1},t_{1}≥0} 3^{s_{1}+t_{1}} \binom{m}{s_{1}}\binom{−m}{t_{1}} (\frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}})^{3m+t_{1}} (\frac{z^{3^{k+1}}(1 + z^{3^{k+1}})}{1 + z^{3^{k+2}}})^{s_{1}} .

This relation is now iterated, to get

(\frac{z^{3^{k+1}}(1 + z^{3^{k+1}})}{1 + z^{3^{k+2}}})^{m}

= ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{∥s∥+∥t∥} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}}) (\frac{z^{3^{k}}(1 + z^{3^{k}})}{1 + z^{3^{k+1}}})^{3m+3∥s∥+∥t∥} , (2.19)

where, by convention, s_{0} = m. Finally, if this identity with m = n + b is substituted in (2.18) in the terms with a ≥ 1, then we obtain the right-hand side of (2.17). □

Remark. What Lemma 7 affords is an expansion of a power of

z^{3^{k+1}}(1 + z^{3^{k+1}})/(1 + z^{3^{k+2}})  (2.20)

with exponent divisible by 3 in terms which either have coefficients with higher divisibility by 3 or are a power of (2.20) with exponent of smaller 3-adic valuation than the original exponent (see the term for b = 0 in the first sum on the right-hand side of (2.17)).

Lemma 8. For all non-negative integers j and positive integers α and β, we have

\frac{1}{(1 + z^{3^{j}})^{α}} = Pol_{j,α,β} (z, (1 + z)^{−1}) modulo 3^{β},

where Pol_{j,α,β} (z, (1 + z)^{−1}) is a polynomial in z and (1 + z)^{−1} with integer coefficients.

Proof. We perform an induction with respect to j + β. Clearly, for β = 1 and j = 0, there is nothing to prove.

For the induction step, we write

\frac{1}{(1 + z^{3^{j}})^{α}} = \frac{1}{(1 + z^{3^{j−1}})^{3α}} + \frac{1}{(1 + z^{3^{j}})^{α}} − \frac{1}{(1 + z^{3^{j−1}})^{3α}}

= \frac{1}{(1 + z^{3^{j−1}})^{3α}} + \frac{1}{(1 + z^{3^{j−1}})^{3α}(1 + z^{3^{j}})^{α}} ((1 + z^{3^{j−1}})^{3α} − (1 + z^{3^{j}})^{α})

= \frac{1}{(1 + z^{3^{j−1}})^{3α}} + \frac{1}{(1 + z^{3^{j−1}})^{3α}(1 + z^{3^{j}})^{α}}

× ((1 + 3z^{3^{j−1}} + 3z^{2·3^{j−1}} + z^{3^{j}})^{α} − (1 + z^{3^{j}})^{α})

= \frac{1}{(1 + z^{3^{j−1}})^{3α}} + \frac{1}{(1 + z^{3^{j−1}})^{3α}(1 + z^{3^{j}})^{α}}

× ∑_{ℓ=1}^{α} \binom{α}{ℓ}3^{ℓ} (z^{3^{j−1}} + z^{2·3^{j−1}})^{ℓ} (1 + z^{3^{j}})^{α−ℓ}

= \frac{1}{(1 + z^{3^{j−1}})^{3α}} + ∑_{ℓ=1}^{α} \binom{α}{ℓ}\frac{3^{ℓ}z^{ℓ·3^{j−1}}}{(1 + z^{3^{j−1}})^{3α−ℓ}(1 + z^{3^{j}})^{ℓ}} .

Now the induction hypothesis can be applied, and yields

\frac{1}{(1 + z^{3^{j}})^{α}} = Pol_{j−1,3α,β} (z, (1 + z)^{−1})

+ ∑_{ℓ=1}^{α} \binom{α}{ℓ}3^{ℓ}z^{ℓ·3^{j−1}} Pol_{j−1,3α−ℓ,β−ℓ}^{3α−ℓ} (z, (1 + z)^{−1}) Pol_{j,ℓ,β−ℓ}^{ℓ} (z, (1 + z)^{−1})

modulo 3^{β}.

This completes the induction. □

We are now ready for the proof of the announced expansion result.

Lemma 9. For positive integers b_{1}, b_{2}, …, b_{s} and γ, the series H̃_{b_{1},b_{2},...,b_{s}}(z), can be expressed as a linear combination over (ℤ/3^{γ}ℤ)[z, (1 + z)^{−1}] of the series 1 and series of the form H̃_{a_{1},a_{2},...,a_{r}}(z), where none of the a_{i}’s is divisible by 3.

Remark. What the proof below actually does is to find an expansion of H̃_{b_{1},b_{2},...,b_{s}}(z) over ℤ_{3}[z, (1 + z)^{−1}], where ℤ_{3} denotes the ring of 3-adic integers. As this point of view will not play an explicit role in the sequel, we shall not pursue this aspect any further.

Proof of Lemma 9. With each term

c_{b_{1},b_{2},...,b_{s}} H̃_{b_{1},b_{2},...,b_{s}}(z),

c_{b_{1},b_{2},...,b_{s}} being some integer, we associate the quadruple (s, v, i, t), where

v = v_{3}(c_{b_{1},b_{2},...,b_{s}}),

i is the maximal index such that b_{i} is divisible by 3, and t = v_{3}(b_{i}). We describe an algorithmic procedure for expressing H̃_{b_{1},b_{2},...,b_{s}}(z) in terms of series H̃_{a_{1},a_{2},...,a_{r}}(z) with associated quadruple less than the quadruple associated with H̃_{b_{1},b_{2},...,b_{s}}(z), according to the following total order of quadruples: we define (s_{1}, v_{1}, i_{1}, t_{1}) ≺ (s_{2}, v_{2}, i_{2}, t_{2}) if, and only if,

s_{1} < s_{2},
or s_{1} = s_{2} and v_{1} > v_{2},
or s_{1} = s_{2}, v_{1} = v_{2}, and i_{1} < i_{2},
or s_{1} = s_{2}, v_{1} = v_{2}, i_{1} = i_{2}, and t_{1} < t_{2}.

Our algorithmic procedure consists of four recurrence relations, (2.22)–(2.25) below. These are based on Hou’s reduction idea in [6].

Let h be an integer between 1 and s. Furthermore, we assume that b_{h} is divisible by 3 and that all b_{i}’s with i > h are not divisible by 3. We write b_{h} = 3b′_{h}. Then, from the definition of the series H̃_{b_{1},b_{2},...,b_{s}}(z) and from Lemma 7, we have

H̃_{b_{1},b_{2},...,b_{s}}(z) = ∑_{k_{1}>···>k_{s−1}>k_{s}≥0} (_{∏_{j=1}^{s} ; j≠h} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{b_{j}} ) (\frac{z^{3^{k_{h}}}(1 + z^{3^{k_{h}}})}{1 + z^{3^{k_{h}+1}}})^{3b′_{h}}

= ∑_{b≥0} 3^{b}\binom{−b′_{h}}{b} ∑_{k_{1}>···>k_{s−1}>k_{s}≥0} (_{∏_{j=1}^{s} ; j≠h} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{b_{j}} ) (\frac{z^{3^{k_{h}+1}}(1 + z^{3^{k_{h}+1}})}{1 + z^{3^{k_{h}+2}}})^{b′_{h}+b}

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{b′_{h}}{a}\binom{−b′_{h}}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· ∑_{k_{1}>···>k_{s−1}>k_{s}≥0} (_{∏_{j=1}^{s} ; j≠h} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{b_{j}} ) (\frac{z^{3^{k_{h}}}(1 + z^{3^{k_{h}}})}{1 + z^{3^{k_{h}+1}}})^{3(∥s∥+b′_{h}+b)+∥t∥+a} . (2.21)

Now we distinguish four cases. First let 1 < h < s. In the first of the above sums on the right-hand side, let k′_{h} = k_{h} + 1 be a new summation index. We observe that we have

{(k_{1}, …, k_{h−1}, k_{h}+1, k_{h+1}, …, k_{s}) : k_{1} > ⋯ > k_{h−1} > k_{h} > k_{h+1} > ⋯ > k_{s} ≥ 0}

= ({(k_{1}, …, k_{h−1}, k′_{h}, k_{h+1}, …, k_{s}) : k_{1} > ⋯ > k_{h−1} > k′_{h} > k_{h+1} > ⋯ > k_{s} ≥ 0}

˙∪{(k_{1}, …, k_{h−1}, k_{h−1}, k_{h+1}, …, k_{s}) : k_{1} > ⋯ > k_{h−1} > k_{h+1} > ⋯ > k_{s} ≥ 0})

\{(k_{1}, …, k_{h−1}, k_{h+1} + 1, k_{h+1}, …, k_{s}) : k_{1} > ⋯ > k_{h−1} > k_{h+1} > ⋯ > k_{s} ≥ 0},

where the union is a disjoint union, and the third set on the right-hand side is entirely contained in the union of the first two. If we apply this observation to the (new) index set of the first sum, then, from (2.21), we obtain

H̃_{b_{1},b_{2},...,b_{s}}(z) = ∑_{b≥0} 3^{b}\binom{−b′_{h}}{b} (H̃_{b_{1},b_{2},...,b_{h−1},b′_{h}+b,b_{h+1},...,b_{s}}(z)

+ H̃_{b_{1},b_{2},...,b_{h−1}+b′_{h}+b,b_{h+1},...,b_{s}}(z)

− ∑_{k_{1}>···>k_{s−1}>k_{s}≥0} (_{∏_{j=1}^{s} ; j≠h} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{b_{j}} ) (\frac{z^{3^{k_{h+1}+1}}(1 + z^{3^{k_{h+1}+1}})}{1 + z^{3^{k_{h+1}+2}}})^{b′_{h}+b})

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{b′_{h}}{a}\binom{−b′_{h}}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· H̃_{b_{1},b_{2},...,b_{h−1},3(∥s∥+b′_{h}+b)+∥t∥+a,b_{h+1},...,b_{s}}(z).

To the term with exponent b′_{h} + b we apply the identity (2.19). Then the above relation becomes

H̃_{b_{1},b_{2},...,b_{s}}(z) = ∑_{b≥0} 3^{b}\binom{−b′_{h}}{b} (H̃_{b_{1},b_{2},...,b_{h−1},b′_{h}+b,b_{h+1},...,b_{s}}(z)
+ H̃_{b_{1},b_{2},...,b_{h−1}+b′_{h}+b,b_{h+1},...,b_{s}}(z)

− ∑_{u_{1},u_{2},...,v_{1},v_{2},···≥0} 3^{∥u∥+∥v∥} (∏_{j≥1} \binom{u_{j−1}}{u_{j}}\binom{−u_{j−1}}{v_{j}})

· H̃_{b_{1},b_{2},...,b_{h−1},3(b′_{h}+b+∥u∥)+∥v∥+b_{h+1},...,b_{s}}(z))

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{b′_{h}}{a}\binom{−b′_{h}}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· H̃_{b_{1},b_{2},...,b_{h−1},3(∥s∥+b′_{h}+b)+∥t∥+a,b_{h+1},...,b_{s}}(z).  (2.22)

It should be observed that the quadruples associated with the terms on the right-hand side of (2.22) are indeed less than the quadruple associated with H̃_{b_{1},b_{2},...,b_{s}}(z) in the order ≺.

Next we consider the case where 1 < h = s. Reasoning in a way similar to the one which in the end led to (2.22), we obtain the recurrence relation

H̃_{b_{1},b_{2},...,b_{s}}(z) = ∑_{b≥0} 3^{b}\binom{−b′_{s}}{b}(H̃_{b_{1},b_{2},...,b_{s−1},b′_{s}+b}(z)

+ H̃_{b_{1},b_{2},...,b_{s−1}+b′_{s}+b}(z) − (\frac{z(1 + z)}{1 + z^{3}})^{b′_{s}+b} H̃_{b_{1},b_{2},...,b_{s−1}}(z))

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{b′_{s}}{a}\binom{−b′_{s}}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· H̃_{b_{1},b_{2},...,b_{s−1},3(∥s∥+b′_{s}+b)+∥t∥+a}(z).  (2.23)

Again, the quadruples associated with the terms on the right-hand side of (2.23) are indeed less than the quadruple associated with H̃_{b_{1},b_{2},...,b_{s}}(z) in the order ≺.

Now let 1 = h < s. In this case, we obtain the recurrence relation

H̃_{b_{1},b_{2},...,b_{s}}(z) = ∑_{b≥0} 3^{b}\binom{−b′_{1}}{b} (H̃_{b′_{1}+b,b_{2},...,b_{s}}(z)

− ∑_{u_{1},u_{2},...,v_{1},v_{2},···≥0} 3^{∥u∥+∥v∥} (∏_{j≥1} \binom{u_{j−1}}{u_{j}}\binom{−u_{j−1}}{v_{j}}) H̃_{3(b′_{1}+b+∥u∥)+∥v∥+b_{2},...,b_{s}}(z))

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{b′_{1}}{a}\binom{−b′_{1}}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· H̃_{3(∥s∥+b′_{1}+b)+∥t∥+a,b_{2},...,b_{s}}(z).  (2.24)

Finally, in the degenerate case 1 = h = s, summation over k on both sides of (2.17) with n = b′_{1} directly yields

H̃_{b_{1}}(z) = ∑_{b≥0} 3^{b}\binom{−b′_{1}}{b} (H̃_{b′_{1}+b}(z) − (\frac{z(1 + z)}{1 + z^{3}})^{b′_{1}+b})

+_{∑_{a≥1} ; b≥0} ∑_{s_{1},s_{2},...,t_{1},t_{2},···≥0} 3^{a+b+∥s∥+∥t∥}\binom{b′_{1}}{a}\binom{−b′_{1}}{b} (∏_{j≥1} \binom{s_{j−1}}{s_{j}}\binom{−s_{j−1}}{t_{j}})

· H̃_{3(∥s∥+b′_{1}+b)+∥t∥+a}(z). (2.25)

It is clear that, if we recursively apply (2.22)–(2.25) to a given series H̃_{b_{1},b_{2},...,b_{s}}(z), and use H̃_{∅}(z) = 1 as an initial condition, we will eventually arrive at a linear combination of 1, powers of z(1+z)/(1+z^{3}), and series H̃_{a_{1},a_{2},...,a_{r}}(z) with all a_{i}’s being not divisible by 3, where the coefficients are polynomials in z and (1 + z^{3})^{−1}. In view of Lemma 8, this completes the proof of the lemma. □

How the results of this section are implemented to extract coefficients of concrete powers of z from powers of Ψ(z) modulo a given 3-power is explained in more detail in the appendix. As an illustration, the coefficients of Ψ^{3}(z) and of Ψ^{5}(z) are worked out explicitly modulo 9 and modulo 27, see Propositions 68 and 71.

3. Minimal polynomials for Ψ(z)

Here we consider polynomial relations of the Cantor-like formal power series Ψ(z) defined in (1.1), when coefficients are reduced modulo powers of 3. The series is transcendental over ℤ[z] (see Theorem 10 below). However, if the coefficients of Ψ(z) are considered modulo a 3-power 3^{γ}, then Ψ(z) obeys a polynomial relation with coefficients that are Laurent polynomials in z and 1+z. The focus of this section is on what can be said concerning such polynomial relations, and, in particular, about those of minimal length.

Here and in the sequel, given integral power series (or Laurent series) f(z) and g(z), we write

f(z) = g(z) modulo 3^{γ}

to mean that the coefficients of z^{i} in f(z) and g(z) agree modulo 3^{γ} for all i.

We say that a polynomial A(z, t) in z and t is minimal for the modulus 3^{γ}, if it is monic (as a polynomial in t), has coefficients which are Laurent polynomials in z and 1 + z, satisfies A(z, Ψ(z)) = 0 modulo 3^{γ}, and there is no monic polynomial B(z, t) whose coefficients are Laurent polynomials in z and 1 + z, whose t-degree is less than that of A(z, t), and which satisfies B(z, Ψ(z)) = 0 modulo 3^{γ}. Minimal polynomials are not unique; see Remark 15 below.

Our results concerning minimal polynomials are analogous to the corresponding ones in [7, Sec. 2], albeit more difficult to prove. We start by providing a lower bound on degrees of minimal polynomials. We strongly believe that this lower bound is actually sharp; see Conjecture 12 below. In order to formulate the result, we let v_{3}(α) denote the 3-adic valuation of the integer α, that is, the maximal exponent e such that 3^{e} divides α.

Theorem 10. The degree of a minimal polynomial for the modulus 3^{γ}, γ ≥ 1, is 2d, where d satisfies d + v_{3}(d!) ≥ γ. In particular, the series Ψ(z) is transcendental over ℤ[z].

For the proof of this theorem, we need the following auxiliary result.

Lemma 11. Let a, b, c_{1}, c_{2}, …, c_{d} be positive integers with a > b. Then

∑_{k=0}^{b}(−1)^{b−k}\binom{b}{k} ∏_{j=1}^{a} 3^{c_{j}} \binom{k}{c_{j}}  (3.1)

is divisible by 3^{a}b!. It is even divisible by 3^{a+1}b! if at least one of the c_{j}’s is at least 3.

Proof. We need to recall some facts from classical difference operator calculus (cf. [14]). We denote by E the shift operator defined by Ef(y) = f(y + 1), and by △ the forward difference operator defined by △f(y) = f(y + 1) − f(y). The reader should observe that △ = E − I, where I stands for the identity operator. In terms of these operators, we may rewrite the expression in (3.1) as

∑_{k=0}^{b}(−1)^{b−k}\binom{b}{k}E^{k} ∏_{j=1}^{a} 3^{c_{j}} \binom{y}{c_{j}}|_{y=0} = (E − I)^{b} ∏_{j=1}^{a} 3^{c_{j}} \binom{y}{c_{j}}|_{y=0}

= (∏_{j=1}^{a} \frac{(−3)^{c_{j}}}{c_{j}!} ) △^{b} ∏_{j=1}^{a}(−y)_{c_{j}} |_{y=0},  (3.2)

where the Pochhammer symbol is defined by (α)_{m} = α(α + 1) ⋯ (α + m − 1) for m ≥ 1, and (α)_{0} = 1, The second product over j is a polynomial in y with integer coefficients. It is well-known from difference calculus that the constant term of the bfold application of the operator △ on such a polynomial is divisible by b!. For the sake of self-containedness, we provide the simple argument here: let p(y) be a polynomial in y with integer coefficients. Then we may expand p(y) in Pochhammer symbols,

p(y) = ∑_{m≥0} α_{m}(−y)_{m},

where the coefficients α_{m} are all integers. Since E(−y)_{m} = −m · (−y)_{m−1}, we infer

E^{b}p(y)|_{y=0} = (−1)^{b} ∑_{m≥0} α_{m} \frac{m!}{(m − b)!}(−y)_{m−b}|_{y=0} = (−1)^{b}α_{b}b!,

which is visibly divisible by b!.

If we use what we know in (3.2), together with the easily verified fact that

v_{3}(3^{α}) ≥ \begin{cases}v_{3}(α!) + 1, & if α ≥ 1, \\ v_{3}(α!) + 2, & if α ≥ 3, \end{cases}

then the assertion of the lemma follows immediately. □

Proof of Theorem 10. The first observation is that Lemma 5 implies that minimal polynomials must have even degree, and, moreover, that they can be chosen as even polynomials in t, that is, as polynomials in t^{2}.

So, for a contradiction, let us suppose that A(z, t) is the minimal polynomial for the modulus 3^{γ}, that it is even, and that it has degree 2d, where d + v_{3}(d!) < γ.

Since A(z, t) is even in t, it does not matter whether we consider A(z, t) as a polynomial in t^{2} (and z and (1 + z)^{−1}) or as a polynomial in (t^{2} − \frac{1}{1+z}) (and z and (1 + z)^{−1}). We take the latter point of view.

We now expand a power (Ψ^{2}(z) − \frac{1}{1+z})^{b}, 1 ≤ b ≤ d, in terms of the series H̃_{a_{1},a_{2},...,a_{s}}(z) (see (2.3) for the definition) using (2.5) and the short notation (2.4):

(Ψ^{2}(z) − \frac{1}{1 + z} )^{b} = \frac{1}{(1 + z)^{b}} (∑_{s≥1} 3^{s}H̃^{1,1,...,1}_{s times}(z))^{b}

= \frac{1}{(1 + z)^{b}} (∑_{s≥1} 3^{s} ∑_{k_{1}>···>k_{s}≥0} R(k_{1})R(k_{2}) ⋯ R(k_{s}))^{b}

= \frac{1}{(1 + z)^{b}} (( ∏_{j≥0}(1 + 3R(j))) − 1)^{b}

= \frac{1}{(1 + z)^{b}} ∑_{k=0}^{b}(−1)^{b−k}\binom{b}{k} ∏_{j≥0}(1 + 3R(j))^{k}

= \frac{1}{(1 + z)^{b}} ∑_{s≥1} ∑_{a_{1},...,a_{s}≥1} c(b; a_{1}, a_{2}, …, a_{s}) H̃_{a_{1},a_{2},...,a_{s}}(z), (3.3)

where the c(b; a_{1}, a_{2}, …, a_{s})’s are certain combinatorial (and, hence, integer) coefficients. Not all of the H̃-series which occur with non-zero coefficient c(b; a_{1}, a_{2}, …, a_{s}) will have the property that all indices a_{j} are not divisible by 3. So, in a second step, one will have to apply the reduction procedure described in Lemma 9 to arrive at an expansion of the form

(Ψ^{2}(z) − \frac{1}{1 + z} )^{b} = \frac{1}{(1 + z)^{b}} ∑_{s≥1}_{∑_{a_{1},...,a_{s}≥1} ; 3∤a_{1},...,3∤a_{s}}c̃(b; a_{1}, a_{2}, …, a_{s})H̃_{a_{1},a_{2},...,a_{s}}(z), (3.4)

where the c̃(b; a_{1}, a_{2}, …, a_{s})’s are certain modified coefficients. It should be observed (cf. Corollary 4) that the H̃-series on the right-hand side of (3.4) are linearly independent over (ℤ/3^{γ}ℤ)[z, (1 + z)^{−1}].

We are interested in the coefficient c̃(b; 1, 1, …, 1) with a occurrences of 1. We claim that

c̃(b; \underbrace{1, 1, …, 1}_{a times}) = \begin{cases}3^{a+1} b! N_{1}, & if a < b, \\ 3^{b} b! + 3^{b+v_{3}(b!)+1}N_{2}, & if a = b, \\ 3^{a} b! N_{3}, & if a > b, \end{cases}  (3.5)

where N_{1}, N_{2}, N_{3} are integers (depending on a and b).

In order to see this, we must examine how terms H̃_{1,...,1}(z) with a non-zero coefficient c̃(b; 1, 1, …, 1) in the expansion (3.4) arise from (3.3). From the proof of Lemma 9, we see that such terms come from terms

c(b; 3^{d_{1}}, 3^{d_{2}}, …, 3^{d_{a}}) H̃_{3^{d_{1}},3^{d_{2}},...,3^{da}}(z),

in (3.3) with non-zero coefficient c(…). (To be correct, there are also contributions to c̃(b; 1, 1, …, 1) from other terms, but these will have a higher 3-divisibility than those discussed here. We shall not mention them any further. Suffice it to point out that they are subsumed in the terms N_{4}(b; d_{1}, d_{2}, …, d_{a}) below.) If these observations are put together, one obtains

c̃(b; \underbrace{1, 1, …, 1}_{a times}) = ∑_{d_{1},...,d_{a}≥0} c(b; 3^{d_{1}}, 3^{d_{2}}, …, 3^{d_{a}}) (1 + 3N_{4}(b; d_{1}, d_{2}, …, d_{a})), (3.6)

where the N_{4}(b; d_{1}, d_{2}, …, d_{a})’s are integers.

We must now compute the coefficient c(b; 3^{d_{1}}, 3^{d_{2}}, …, 3^{d_{a}}). As we already said, this is a combinatorial coefficient arising in the expansion (3.3). Recalling the definition (2.3) of the H̃-series, one sees that this coefficient equals the coefficient of

R(0)^{3^{d_{1}}}R(1)^{3^{d_{2}}} ⋯ R(a − 1)^{3^{da}}

in the line just above (3.3). An easy extraction yields

c(b; 3^{d_{1}}, 3^{d_{2}}, …, 3^{d_{a}}) = ∑_{k=0}^{b}(−1)^{b−k}\binom{b}{k} ∏_{j=1}^{a} 3^{3^{d_{j}}} \binom{k}{3^{d_{j}}}.

By Lemma 11 we know that this expression is divisible by 3^{a} b!, and, if one of the d_{j}’s is positive, even by 3^{a+1} b!. If this is used in (3.6), then our claim (3.5) follows without much effort, the term 3^{b} b! (occurring in (3.5) in the case where a = b) being contributed by

c(b; \underbrace{1, 1, …, 1}_{b times}) = 3^{b} b!.

We are now in the position to complete the argument. Let us return to the minimal polynomial A(z, t) for the modulus 3^{γ}. We expand it in powers of (t^{2} − \frac{1}{1+z}),

A(z, t) = ∑_{b=0}^{d} A_{b} (t^{2} − \frac{1}{1 + z} )^{b} ,  (3.7)

where A_{d} = 1. (The reader should recall that minimal polynomials are monic by definition.) We substitute Ψ(z) for t and claim that A(z, Ψ(z)) cannot vanish modulo 3^{γ}. In order to see this, we perform an induction on the index b in (3.7). The claim that we are going to prove by this induction is that the coefficient A_{a} is divisible by 3^{b+v_{3}(b!)−a−v_{3}(a!)} for all a with 1 ≤ a ≤ b. This is trivially true for b = 1, since in that case the only possible a is a = 1, in which case the condition is void.

We proceed to the induction step. In the following, we shall use the short notation H̃_{1^{r}}(z) for H̃_{1,1,...,1}(z) with r occurrences of 1. We consider the coefficient of H̃_{1^{b}}(z) in (t^{2} − \frac{1}{1+z})^{b}. Let us denote it by C. According to (3.5), it equals 3^{b} b! + 3^{b+v_{3}(b!)+1}N_{2}, where N_{2} is some integer. In particular, it is divisible by 3^{b+v_{3}(b!)}, but not by a higher power of 3. By using (3.5) again (this time with a and b interchanged), in combination with the induction hypothesis, we see that the coefficient of H̃_{1^{b}}(z) in the term A_{a} (Ψ^{2}(z) − \frac{1}{1+z})^{a}, a < b, is divisible by 3^{b+v_{3}(a!)}3^{b+v_{3}(b!)−a−v_{3}(a!)} = 3^{2b−a+v_{3}(b!)} ≥ 3^{b+v_{3}(b!)+1}. This is a higher divisibility by 3 than that of the coefficient C. Moreover, by another application of (3.5), the coefficient of H̃_{1^{b}}(z) in the term A_{a} (Ψ^{2}(z) − \frac{1}{1+z})^{a}, a > b, is divisible by

3^{b+1+v_{3}(a!)} ≥ 3^{b+v_{3}((b+1)!)+1} ≥ 3^{b+v_{3}(b!)+1},  (3.8)

which is again a higher 3-divisibility than that of the coefficient C. So none of these terms can cancel C, unless A_{b} is divisible by 3. Assuming the latter, one considers the coefficient of H̃_{1^{b−1}} in A_{b−1} (Ψ^{2}(z) − \frac{1}{1+z})^{b−1} and compares its 3-divisibility to the 3-divisibility of the corresponding coefficients in the other terms. The conclusion is that also A_{b−1} must be divisible by another 3, that is (the reader should recall the induction hypothesis), it must be divisible by 3^{b+v_{3}(b!)−(b−1)−v_{3}((b−1)!)+1}. One repeats this same argument with the coefficient of H̃_{1^{a}} in A_{a} (Ψ^{2}(z) − \frac{1}{1+z})^{a}, a = b − 2, …, 2, 1, to conclude that A_{a} must be divisible by 3^{b+v_{3}(b!)−a−v_{3}(a!)+1}, a = 1, 2, …, b.

Now one returns to the term A_{b} (Ψ^{2}(z) − \frac{1}{1+z})^{b}. So far, we know that A_{b} must be divisible by 3, and that the coefficient of H̃_{1^{b}} in (Ψ^{2}(z) − \frac{1}{1+z})^{b} is divisible by 3^{b+v_{3}(b!)}, but not by a higher power of 3. If we repeat the arguments of the previous paragraph, but take into account that they led to an “improvement” of the induction hypothesis, then one is led to the conclusion that A_{b} must have an even higher 3-divisibility, entailing analogous higher 3-divisibility of the coefficients A_{a} with a < b, until one reaches the conclusion that A_{b} must be divisible by 3^{b+1+v_{3}((b+1)!)−b−v_{3}(b!)} (cf. the middle term in (3.8)), and consequently A_{a} by 3^{b+1+v_{3}((b+1)!)−a−v_{3}(a!)}, a = 1, 2, …, b − 1. This is exactly the induction hypothesis with b replaced by b + 1.

When we use what we have just proven for b = d, then this produces a contradiction. Namely, if A_{a} is divisible by 3^{d+v_{3}(d!)−a−v_{3}(a!)}, a = 1, 2, …, d, then the above arguments would imply that A_{d} must be divisible by (at least) 3. This, however, is impossible since A_{d} = 1.

We have thus shown that, indeed, a minimal polynomial for the modulus 3^{γ}, where d + v_{3}(d!) < γ must have degree larger than 2d. This completes the proof of the theorem. □

Based on the observations in Proposition 14 later in this section and Theorem 10, we propose the following conjecture.

Conjecture 12. The degree of a minimal polynomial for the modulus 3^{γ}, γ ≥ 1, is 2d, where d is the least positive integer such that d + v_{3}(d!) ≥ γ.

Remark 13. (1) Given the ternary expansion of d, say

d = d_{0} + d_{1} · 3 + d_{2} · 9 + ⋯ + d_{r} · 3^{r}, 0 ≤ γ_{i} ≤ 1,

we have, by the well-known formula of Legendre [9, p. 10],

v_{3}(d!) = ∑_{ℓ=1}^{∞} ⌊\frac{d}{3^{ℓ}} ⌋ = ∑_{ℓ=1}^{∞} ⌊∑_{i=0}^{r} d_{i}3^{i−ℓ}⌋ = ∑_{ℓ=1}^{∞} ∑_{i=ℓ}^{r} d_{i}3^{i−ℓ}

= ∑_{i=1}^{r} ∑_{ℓ=1}^{i} d_{i}3^{i−ℓ} = ∑_{i=1}^{r} \frac{d_{i}}{2} (3^{i} − 1) = \frac{1}{2}(d − s(d)),  (3.9)

where s(d) denotes the sum of digits of d in its ternary expansion. Consequently, an equivalent way of phrasing Theorem 10 is to say that the degree of a minimal polynomial for the modulus 3^{γ} is 2d, where d is the least positive integer with \frac{1}{2}(3d − s(d)) ≥ γ.

(2) We claim that, in order to establish Conjecture 12, it suffices to prove the conjecture for γ = \frac{1}{2}(3^{δ+1} − 1), δ = 0, 1, . . .. If we take into account the remark in (1), this means that it is sufficient to prove that, for each δ ≥ 0, there is a polynomial A_{δ}(z, t) of degree 2 · 3^{δ} such that

A_{δ}(z, Ψ(z)) = 0 modulo 3^{(3^{δ+1}−1)/2}.  (3.10)

For, arguing by induction, let us suppose that we have already constructed A_{0}(z, t), A_{1}(z, t), …, A_{m}(z, t) satisfying (3.10). Let

α = α_{0} + α_{1} · 3 + α_{2} · 9 + ⋯ + α_{m} · 3^{m}, 0 ≤ α_{i} ≤ 2,

be the ternary expansion of the positive integer α. In this situation, we have

∏_{δ=0}^{m} A_{δ}^{α_{δ}}(z, Ψ(z)) = 0 modulo ∏_{δ=0}^{m} 3^{α_{δ}(3^{δ+1}−1)/2} = 3^{(3α−s(α))/2}.  (3.11)

On the other hand, the degree of the left-hand side of (3.11) as a polynomial in Ψ(z) is ∑_{δ=0}^{m} α_{δ} · 2 · 3^{δ} = 2α.

Let us put these observations together. In view of (3.9), our lower bound assumption says that the degree of a minimal polynomial for the modulus 3^{γ} cannot be smaller than the least even integer, 2d^{(γ)} say, for which \frac{1}{2}(3d^{(γ)} −s(d^{(γ)})) ≥ γ. If we take into account that the quantity \frac{1}{2}(3α − s(α)), as a function in α, is weakly monotone increasing in α, then (3.11) tells us that, as long as d^{(γ)} ≤ 2 + 2 · 3 + 2 · 9 + ⋯ + 2 · 3^{m} = 3^{m+1} − 1, we have found a monic polynomial of degree 2d^{(γ)}, B_{γ}(z, t) say, for which B_{γ}(z, Ψ(z)) = 0 modulo 3^{γ}, namely the left-hand side of (3.11) with α replaced by d^{(γ)}, to wit

B_{γ}(z, t) = ∏_{δ=1}^{m} A_{δ}^{d_{δ}^{(γ)}}(z, t),

where d^{(γ)} = d_{0}^{(γ)} + d_{1}^{(γ)} · 3 + d_{2}^{(γ)} · 9 + ⋯ + d_{m}^{(γ)} · 3^{m} is the ternary expansion of d^{(γ)}. Hence, it must necessarily be a minimal polynomial for the modulus 3^{γ}.

Since \frac{1}{2}(3(3^{m+1} − 1) − s(3^{m+1} − 1)) = \frac{1}{2}(3^{m+2} − 3 − 2(m + 1)), we have thus found minimal polynomials for all moduli 3^{γ} with γ ≤ \frac{1}{2}(3^{m+2} − 2m − 5). Now we should note that the quantity \frac{1}{2}(3α − s(α)) makes a jump from \frac{1}{2}(3^{m+2} − 2m − 5) to \frac{1}{2}(3^{m+2} − 1) when we move from α = 3^{m+1} − 1 to α = 3^{m+1}. If we take A_{m}^{3}(z, t), which has degree 2 · 3^{m+1}, then, by (3.10), we also have a minimal polynomial for the modulus

(3^{(3^{m+1}−1)/2})^{3} = 3^{(3^{m+2}−3)/2} and, in view of the preceding remark, as well for all moduli 3^{γ} with γ between \frac{1}{2}(3^{m+2} − 2m − 5) and \frac{1}{2}(3^{m+2} − 3).

So, indeed, the first modulus for which we do not have a minimal polynomial is the modulus 3^{(3^{m+2}−1)/2}. This is the role which A_{m+1}(z, t) (see (3.10) with m + 1 in place of δ) would have to play.

(3) The arguments in Item (2) show at the same time that, supposing that we have already constructed A_{0}(z, t), A_{1}(z, t), …, A_{m}(z, t), the polynomial A_{m}^{3}(z, t) is a very close “approximation” to the polynomial A_{m+1}(z, t) that we are actually looking for next, which is only “off” by a factor of 3. This can be used to recursively compute polynomials A_{δ}(z, t) satisfying (3.10), by expanding A_{m}(z, Ψ(z)) in terms of the series H̃_{a_{1},a_{2},...,a_{s}}(z) with all a_{i}’s not divisible by 3, as discussed in the previous section (see in particular (2.5) and Lemma 9), dividing the result through by 3^{(3^{m+1}−1)/2}, and considering the quotient, say

3^{−(3^{m+1}−1)/2}A_{m}(z, Ψ(z)) = ∑_{s≥1} ∑_{a_{1},...,a_{s}≥1} c(a_{1}, a_{2}, …, a_{s}; z)H̃_{a_{1},a_{2},...,a_{s}}(z),

where the coefficients c(a_{1}, a_{2}, …, a_{s}; z) are necessarily in ℤ[z, (1 + z)^{−1}], modulo 3. Then one computes

(3^{−(3^{m+1}−1)/2}A_{m}(z, Ψ(z)))^{3} = ∑_{s≥1} ∑_{a_{1},...,a_{s}≥1} c_{a_{1},a_{2},...,a_{s}}^{3}(z)H̃_{a_{1},a_{2},...,a_{s}}^{3}(z) modulo 3, (3.12)

uses Lemma 9 again to perform the expansion

(H̃_{a_{1},a_{2},...,a_{s}}(z))^{3} = H̃_{a_{1},a_{2},...,a_{s}}(z) + other terms modulo 3,

substitutes this back into (3.12), and expresses whatever remains in terms of powers of A_{i}(z, Ψ(z))’s, with i = 0, 1, …, m. We are not able to actually show that this always works, but it does for small m. The corresponding results are listed in Proposition 14 below.

Proposition 14. Minimal polynomials for the moduli 3, 9, 27, 81, 243, 729, 2187, …, 3^{13} are

A_{0}(z, t) := t^{2} − \frac{1}{1+z}  modulo 3,
A_{0}^{2}(z, t)  modulo 9,
A_{0}^{3}(z, t)  modulo 27,
A_{1}(z, t) := (t^{2} − \frac{1}{1+z})^{3} − \frac{9}{(1+z)^{2}} (t^{2} − \frac{1}{1+z}) + \frac{27z}{(1+z)^{5}}  modulo 81,
A_{0}(z, t)A_{1}(z, t)  modulo 243,
A_{0}^{2}(z, t)A_{1}(z, t)  modulo 729,
A_{1}^{2}(z, t)  modulo 2189,
A_{1}^{2}(z, t)  modulo 3^{8},
A_{0}(z, t)A_{1}^{2}(z, t)  modulo 3^{9},
A_{0}^{2}(z, t)A_{1}^{2}(z, t)  modulo 3^{10},
A_{1}^{3}(z, t)  modulo 3^{11},
A_{1}^{3}(z, t)  modulo 3^{12},
A_{2}(z, t) := A_{1}^{3}(z, t) − \frac{3^{8}}{(1+z)^{6}} A_{1}(z, t)
+ \frac{3^{10}z}{(1+z)^{9}} A_{0}^{2}(z, t) − \frac{3^{11}z(1+z^{2})}{(1+z)^{12}}A_{0}(z, t) + \frac{3^{12}z^{4}}{(1+z)^{17}} modulo 3^{13}.

Proof. To begin with, the reader should recall from Theorem 10 that minimal polynomials always have even degree.

Then, considering (2.5), we see that A_{0}(z, t) is indeed a minimal polynomial for the modulus 3.

Continuing, we follow the procedure outlined in Item (3) of Remark 13. By (2.5), we have

3^{−1}A_{0}(z, Ψ(z)) = \frac{1}{1 + z} H̃_{1}(z) modulo 3,  (3.13)

whence

3^{−3}A_{0}^{3}(z, Ψ(z)) = \frac{1}{(1 + z)^{3}} H̃_{1}^{3}(z) modulo 3

= \frac{1}{(1 + z)^{3}} (H̃_{1}(z) − \frac{z(1 + z)}{1 + z^{3}}) modulo 3.

Putting this together with (3.13) and the simple observation that

\frac{z(1 + z)}{1 + z^{3}} = \frac{z}{(1 + z)^{2}} modulo 3,

it follows immediately that A_{1}(z, Ψ(z)) vanishes indeed modulo 3^{4}. The fact that A_{1}(z, t) is minimal for the modulus 3^{4} follows from the degree bound in Theorem 10. This bound also implies the assertions about minimal polynomials for the moduli 9, 27, 3^{5}, 3^{6}, …, 3^{12}.

The reasoning for A_{2}(z, t) is analogous, albeit more laborious. We leave the details to the reader. □

Remark 15. Minimal polynomials are highly non-unique: for example, the polynomial

(t^{2} − \frac{1}{1 + z} )^{2} + 3 (t^{2} − \frac{1}{1 + z} )

is obviously also a minimal polynomial for the modulus 9.

In the remainder of this section, we show that the derivative of our basic series Ψ(z), when reduced modulo a given power of 3, can be expressed as a multiple of Ψ(z), where the multiplicative factor is a polynomial in z and (1 + z)^{−1}. This is one of the crucial facts which make the method described in Section 4 work.

By straightforward differentiation, we obtain

Ψ′(z) = Ψ(z) ∑_{j=0}^{∞} \frac{3^{j}z^{3^{j}−1}}{1 + z^{3^{j}}} .  (3.14)

Modulo a given 3-power 3^{β}, the sum on the right-hand side of (3.14) is finite. Hence, by Lemma 8, our claim follows.

4. The method

We consider a (formal) differential equation of the form (1.2), satisfied by the integral power series F (z), In this situation, we propose the following algorithmic approach to determining F (z) modulo a 3-power 3^{3^{α}}, for some positive integer α. Let us fix ε ∈ {1, −1} and a positive integer γ. We make the Ansatz

F (z) = ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(εz^{γ}) modulo 3^{3^{α}},  (4.1)

where Ψ(z) is given by (1.1), and where the a_{i}(z)’s are (at this point) undetermined elements of ℤ[z, z^{−1}, (1 + εz^{γ})^{−1}]. Now we substitute (4.1) into (1.2), and we shall gradually determine approximations a_{i,β}(z) to a_{i}(z) such that (1.2) holds modulo 3^{β}, for β = 1, 2, …, 3^{α}. To start the procedure, we consider the differential equation (1.2) modulo 3, with

F (z) = ∑_{i=0}^{2·3^{α}−1} a_{i,1}(z)Ψ^{i}(εz^{γ}) modulo 3.  (4.2)

We have

\frac{d}{dz} (Ψ(εz^{γ})) = \frac{εγz^{γ−1}}{1 + εz^{γ}} Ψ(εz^{γ}) modulo 3.

Consequently, we see that the left-hand side of (1.2) is a polynomial in Ψ(εz^{γ}) with coefficients in ℤ[z, z^{−1}, (1 + εz^{γ})^{−1}]. We reduce powers Ψ^{k}(εz^{γ}) with k ≥ 2 · 3^{α} using the relation

(Ψ^{2}(εz^{γ}) − \frac{1}{1 + εz^{γ}} )^{3^{α}} = 0 modulo 3^{3^{α}},  (4.3)

which is implied by the minimal polynomial for the modulus 3 given in Proposition 14.^{2} Since, at this point, we are only interested in finding a solution to (1.2) modulo 3, Relation (4.3) simplifies to

Ψ^{2·3^{α}}(εz^{γ}) − \frac{1}{(1 + εz^{γ})^{3^{α}}} = 0 modulo 3.  (4.4)

Now we compare coefficients of powers Ψ^{k}(εz^{γ}), k = 0, 1, …, 2 · 3^{α} − 1. This yields a system of 2 · 3^{α} (differential) equations (modulo 3) for unknown functions a_{i,1}(z) in ℤ[z, z^{−1}, (1 + εz^{γ})^{−1}], i = 0, 1, …, 2 · 3^{α} − 1, which may or may not have a solution.

Provided we have already found functions a_{i,β}(z) in ℤ[z, z^{−1}, (1+εz^{γ})^{−1}], i = 0, 1, …, 2 · 3^{α} − 1, for some β with 1 ≤ β ≤ 3^{α} − 1, such that

F (z) = ∑_{i=0}^{2·3^{α}−1} a_{i,β}(z)Ψ^{i}(εz^{γ})  (4.5)

solves (1.2) modulo 3^{β}, we put

a_{i,β+1}(z) := a_{i,β}(z) + 3^{β}b_{i,β+1}(z), i = 0, 1, …, 2 · 3^{α} − 1,  (4.6)

where the b_{i,β+1}(z)’s are (at this point) undetermined elements in ℤ[z, z^{−1}, (1 + εz^{γ})^{−1}]. Next we substitute

F (z) = ∑_{i=0}^{2·3^{α}−1} a_{i,β+1}(z)Ψ^{i}(εz^{γ})

2Actually, if we would like to obtain an optimal result, we should use the relation implied by the minimal polynomial for the modulus 3^{3^{α}} in the sense of Section 3. But since we have no general formula available for such a minimal polynomial (cf. Items (2) and (3) of Remark 13 in that section), and since we wish to prove results for arbitrary moduli, to choose instead powers of the minimal polynomial for the modulus 3 is the best compromise. In principle, it may happen that there exists a polynomial in Ψ(εz^{γ}) with coefficients in ℤ[z, z^{−1}, (1 + εz^{γ})^{−1}], which is identical with F (z) after reduction of its coefficients modulo 3^{3^{α}}, but the Ansatz (4.1) combined with the reduction (4.3) fails because it is too restrictive. However, in all the cases that we treat, this obstruction does not occur. Moreover, once we are successful using this (potentially problematic) Ansatz, then the result can be easily converted into an optimal one by reducing the obtained polynomial further using the relation implied by the actual minimal polynomial for the modulus 3^{3^{α}}.

in (1.2). Using (3.14) and Lemma 8, we see that derivatives of Ψ(εz^{γ}) can be expressed as multiples of Ψ(z), where multiplicative factors are polynomials in z and (1 + εz^{γ})^{−1}. Consequently, we may expand the left-hand side of (1.2) as a polynomial in Ψ(εz^{γ}) with coefficients in ℤ[z, z^{−1}, (1 + εz^{γ})^{−1}]. Subsequently, we apply again the reduction using relation (4.3). By comparing coefficients of powers Ψ^{k}(εz^{γ}), k = 0, 1, …, 2 · 3^{α} − 1, we obtain a system of 2 · 3^{α} (differential) equations (modulo 3^{β+1}) for the unknown functions b_{i,β+1}(z), i = 0, 1, …, 2 · 3^{α} − 1, which may or may not have a solution. If we manage to push this procedure through until β = 3^{α} − 1, then, setting a_{i}(z) = a_{i,3^{α}}(z), i = 0, 1, …, 2 · 3^{α} − 1, the series F (z) as given in (4.1) is a solution to (1.2) modulo 3^{3^{α}}, as required.

We should point out that, in order for the method to be meaningful, we need to assume that the differential equation (1.2), when considered modulo an arbitrary 3power 3^{e}, determines the solution F (z) uniquely modulo 3^{e}. Otherwise, our method could produce several different “solutions,” and it might be difficult to decide which of them actually corresponds to the series F (z) we are interested in. Concerning this point, see the discussion in Section 18.

5. A sample application

In this section, we demonstrate how to apply the method from the previous section, by considering the sequence of “almost central” binomial coefficients (\binom{2n+2}{n})_{n≥0}. To get started, we need a functional equation for the generating function A(z) = ∑_{n≥0} \binom{2n+2}{n}z^{n}. It is not difficult to see that A(z) satisfies the equation

z^{2}A^{2}(z) + A(z) − \frac{1}{1 − 4z} = 0.  (5.1)

We fix α, choose ε = −1 and γ = 1 in the method from Section 4, and make the Ansatz

A(z) = ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(−z) modulo 3^{3^{α}},

where Ψ(z) is given by (1.1), and where the a_{i}(z)’s are (at this point) undetermined Laurent polynomials in z and 1 − z.

The reader should recall that the idea is to gradually determine approximations a_{i,β}(z) to a_{i}(z) such that

A_{β}(z) := ∑_{i=0}^{2·3^{α}−1} a_{i,β}(z)Ψ^{i}(−z)  (5.2)

solves (5.1) modulo 3^{β}, for β = 1, 2, …, 3^{α}.

For the “base step” (that is, for β = 1), we claim that

A_{1}(z) = \frac{1}{z^{2}} − \frac{1}{z^{2}} (1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)}Ψ^{3^{α}}(−z)

solves (5.1) modulo 3. Indeed, substitution of A_{1}(z) for A(z) on the left-hand side of (5.1) yields the expression

\frac{1}{z^{2}} (1 − 2(1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)}Ψ^{3^{α}}(−z) + (1 + z)^{2}(1 − z)^{3^{α}−1}Ψ^{2·3^{α}}(−z))

+ \frac{1}{z^{2}} − \frac{1}{z^{2}} (1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)}Ψ^{3^{α}}(−z) − \frac{1}{1 − z} modulo 3.

Now one uses the relation (4.4) (with ε = −1 and γ = 1) to “get rid of” Ψ^{2·3^{α}}(−z). This leads to the expression

\frac{1}{z^{2}} (1 − 2(1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)}Ψ^{3^{α}}(−z) + (1 + z)^{2}(1 − z)^{−1})

+ \frac{1}{z^{2}} − \frac{1}{z^{2}} (1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)}Ψ^{3^{α}}(−z) − \frac{1}{1 − z}

= \frac{3}{z^{2}(1 − z)} − \frac{3}{z^{2}} (1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)}Ψ^{3^{α}}(−z) modulo 3,

which is indeed 0 modulo 3.

We proceed to the “iteration step.” Supposing that A_{β}(z) as given in (5.2) solves (5.1) modulo 3^{β}, we put

a_{i,β+1}(z) := a_{i,β}(z) + 3^{β}b_{i,β+1}(z), i = 0, 1, …, 2 · 3^{α} − 1,

as in (4.6), where the b_{i,β+1}(z)’s are (at this point) undetermined Laurent polynomials in z and 1 − z. Next we substitute

∑_{i=0}^{2·3^{α}−1} a_{i,β+1}(z)Ψ^{i}(−z)

in (5.1) and consider the result modulo 3^{β+1}. This leads to the congruence

z^{2}A_{β}^{2}(z) + A_{β}(z) − \frac{1}{1 − 4z} + 3^{β} ∑_{i=0}^{2·3^{α}−1} b_{i,β+1}(z)Ψ^{i}(−z)

+ 2 · 3^{β}z^{2} ∑_{i=0}^{2·3^{α}−1} ∑_{j=0}^{2·3^{α}−1} a_{i,β}(z)b_{j,β+1}(z)Ψ^{i+j}(−z) = 0 modulo 3^{β+1}.

By our assumption on A_{β}(z), we may divide by 3^{β}, so that we obtain the congruence

∑_{i=0}^{2·3^{α}−1} Rat_{i}(z)Ψ^{i}(−z) + ∑_{i=0}^{2·3^{α}−1} b_{i,β+1}(z)Ψ^{i}(−z)

− z^{2} ∑_{i=0}^{2·3^{α}−1} ∑_{j=0}^{2·3^{α}−1} a_{i,β}(z)b_{j,β+1}(z)Ψ^{i+j}(−z) = 0 modulo 3, (5.3)

where Rat_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are certain Laurent polynomials in z and 1 − z with integer coefficients. Again, we may reduce powers Ψ^{i+j}(−z) with i + j ≥ 2 · 3^{α} by means of (4.4). Furthermore, by construction, we know that a_{0,β}(z) = 1/z^{2} modulo 3 and that

a_{3^{α},β}(z) = \frac{1}{z^{2}} (1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)} modulo 3.

If we use all this in (5.3), then we obtain

∑_{i=0}^{2·3^{α}−1} Rat_{i}(z)Ψ^{i}(−z) − (1 + z)(1 − z)^{\frac{1}{2} (3^{α}−1)} ∑_{j=0}^{3^{α}−1} b_{j,β+1}(z)Ψ^{j+3^{α}}(−z)

− \frac{1 + z}{(1 − z)^{\frac{1}{2} (3^{α}+1)}} ∑_{j=3^{α}}^{2·3^{α}−1} b_{j,β+1}(z)Ψ^{j−3^{α}}(−z) = 0 modulo 3.

Now we compare coefficients of powers of Ψ(−z). This produces the system of congruences

(1 + z)(1 − z)^{g_{i}}b_{i,β+1}(z) = Rat_{i+3^{α}}(z) modulo 3, i = 0, 1, …, 2 · 3^{α} − 1,

where g_{i} = \frac{1}{2}(3^{α} − 1) if 0 ≤ i < 3^{α}, g_{i} = −\frac{1}{2}(3^{α} + 1) if 3^{α} ≤ i < 2 · 3^{α}, and the index i + 3^{α} in Rat_{i+3^{α}}(z) has to be taken modulo 2 · 3^{α}. Clearly, this system is trivially uniquely solvable. Moreover, in all cases which we looked at, the numerator of the rational function Rat_{i}(z) is divisible by 1 + z, i = 0, 1, …, 2 · 3^{α} − 1. We have no explanation for this, yet. However, under the assumption that this is indeed the case, we see that the algorithm will go through for β = 1, 2, …, 3^{α}, and, consequently, for all non-negative integers α the series A(z), when coefficients are reduced modulo 3^{3^{α}}, can be represented as a polynomial in Ψ(−z) with coefficients that are Laurent polynomials in z and 1 − z.

We have implemented the algorithm explained above. For α = 1, it produces the following result.

Theorem 16. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} \binom{2n + 2}{n} z^{n} = \frac{13}{z^{2}} + 3 (−\frac{z + 1}{z^{2}} + 3\frac{1 − z − z^{2}}{z^{2}(1 − z)} ) Ψ(−z)

+ (4 + \frac{6}{z} − \frac{4}{z^{2}} ) Ψ^{3}(−z) + 3 (4z + 2 − \frac{1}{z} − \frac{5}{z^{2}} ) Ψ^{5}(−z)

modulo 27. (5.4)

The congruence results for Ψ^{3}(z) and Ψ^{5}(z), which one can obtain by following the recipe provided in the appendix, and which are presented explicitly in Propositions 68 and 71, could now be used to find explicit criteria when \binom{2n+2}{n} is congruent to 0, 1, 2, …, 26 modulo 27.^{3} Since a display of such results is rather lengthy, we omit them here, also in most of the subsequent sections. As we already said in the Introduction, we confine ourselves to providing only one illustration of coefficient extraction, namely for the case of free subgroup numbers for P SL_{2}(ℤ); see Section 16.

6. A general theorem on functional–differential equations of quadratic type

The purpose of this section is to show that the method from Section 4 always applies to a certain class of functional-differential equations. The characteristic feature of the equations in this class is that, when reduced modulo 3, they become quadratic equations. Since there are numerous combinatorial objects whose generating functions satisfy quadratic equations, the main theorem of this section has a wide range of applications. These will be discussed in Sections 7–17.

3In principle, such results could also be obtained via the extensions of Lucas’ theorem given in [2] or [5, Theorem 1], which provide a means for determining the congruence class of a binomial coefficient modulo a given prime power.

Theorem 17. Let Ψ(z) be given by (1.1), and let α be some positive integer. Furthermore, suppose that the formal power series F (z) with integer coefficients satisfies the functional-differential equation

c_{2}(z)F^{2}(z) + c_{1}(z)F (z) + c_{0}(z) + 3Q(z; F (z), F′(z), F′′(z), …, F^{(s)}(z)) = 0, (6.1)

where

(1) c_{2}(z) = z^{e_{1}}(1 + εz^{γ})^{e_{2}} modulo 3, with non-negative integers e_{1}, e_{2} and ε ∈ {1, −1};

(2) c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = z^{2f_{1}}(1 + εz^{γ})^{2f_{2}+1} modulo 3, with non-negative integers f_{1}, f_{2};

(3) Q is a polynomial with integer coefficients;

(4) the equation (6.1) has a uniquely determined formal power solution, namely

F (z). Then F (z), when coefficients are reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(εz^{γ}) of the form

F (z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(εz^{γ}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + εz^{γ}.

Before we are able to embark on the proof of Theorem 17, we need to establish an auxiliary result. There, the notion of formal Laurent series is used, by which we mean a formal series ∑_{n≥s} f_{n}z^{n}, where s is some integer.

Lemma 18. Let β be a positive integer. Under the assumptions of Theorem 17, the equation (6.1) has exactly two different solutions in formal Laurent series modulo 3^{β}.

Proof. We proceed by induction on β. For β = 1, the equation (6.1) reduces to

c_{2}(z)F^{2}(z) + c_{1}(z)F (z) + c_{0}(z) = 0 modulo 3.

This is a quadratic equation over a field (namely the field of formal Laurent series over ℤ/3ℤ). Hence, the two solutions are

\frac{−c_{1}(z) ± \sqrt{c_{1}^{2}(z) − 4c_{0}(z)c_{2}(z)}}{2c_{2}(z)} = \frac{−c_{1}(z) ± z^{f_{1}}(1 + εz^{γ})^{f_{2}+ \frac{1}{2}}}{2c_{2}(z)}  modulo 3. (6.2)

Indeed, the square root (1 + εz^{γ})^{1/2} can be computed without any difficulties modulo 3 by means of the binomial theorem. Furthermore, it does not vanish so that (6.2) yields indeed two different formal Laurent series.

Now we suppose that we already know that there are exactly two formal Laurent series, say F_{1}(z) and F_{2}(z), which satisfy (6.1) modulo 3^{β}. In order to find solutions modulo 3^{β+1}, we make the Ansatz F_{i} + 3^{β}G_{i}(z), i = 1, 2, where the G_{i}(z)’s are two unknown formal Laurent series to be determined, we substitute this in (6.1) and reduce modulo 3^{β+1}:

c_{2}(z)(F_{i}^{2}(z) + 2 · 3^{β}F_{i}(z)G_{i}(z)) + c_{1}(z)(F_{i}(z) + 3^{β}G_{i}(z)) + c_{0}(z)

+ 3Q(z; F_{i}(z), F′_{i}(z), F′′_{i}(z), …, F_{i}^{(s)}(z)) = 0 modulo 3^{β+1}.

Rearrangement of terms converts this congruence into

3^{β}G_{i}(z)(c_{1}(z) + 2c_{2}(z)F_{i}(z)) = −c_{2}(z)F_{i}^{2}(z) − c_{1}(z)F_{i}(z) − c_{0}(z)

+ 3Q(z; F_{i}(z), F′_{i}(z), F′′_{i}(z), …, F_{i}^{(s)}(z)) = 0 modulo 3^{β+1}.

By induction hypothesis, we know that the right-hand side is divisible by 3^{β}. We divide both sides by 3^{β} and obtain

G_{i}(z)(c_{1}(z) + 2c_{2}(z)F_{i}(z)) = S(z) modulo 3,

for some explicit formal Laurent series S(z). On the left-hand side, the factor c_{1}(z) + 2c_{2}(z)F_{i}(z) is non-zero since c_{0}(z), c_{1}(z), and c_{2}(z) are polynomials, while F_{i}(z) contains a square root (cf. (6.2)). Hence, for i = 1, 2, we obtain uniquely determined G_{i}(z) modulo 3 such that F_{i}(z) + 3^{β}G_{i}(z) is a solution to (6.1) modulo 3^{β+1}. This completes the induction step. □

Proof of Theorem 17. We apply the method from Section 4. As we discussed there and in the sample application in the previous section, it consists of two steps, a base step, which determines a solution to the functional-differential equation (6.1) modulo 3, and an iteration step, which affords solutions modulo higher and higher powers of 3.

In the entire proof, we always assume without loss of generality that c_{0}(z), c_{1}(z), and c_{2}(z) are already reduced modulo 3 (otherwise we could put terms which are divisible by 3 into the polynomial Q( .)).

Base step. We start by substituting the Ansatz (4.2) in (6.1) and reducing the result modulo 3. In this way, we obtain

c_{2}(z) ∑_{i=0}^{2·3^{α}−1} ∑_{j=0}^{2·3^{α}−1} a_{i,1}(z)a_{j,1}(z)Ψ^{i+j}(εz^{γ})

+ c_{1}(z) ∑_{i=0}^{2·3^{α}−1} a_{i,1}(z)Ψ^{i}(εz^{γ}) + c_{0}(z) = 0 modulo 3.

When i + j ≥ 2 · 3^{α}, we may reduce Ψ^{i+j}(εz^{γ}) further using relation (4.4) (with z replaced by εz^{γ}). This leads to

c_{2}(z)_{∑_{0≤i,j≤2·3^{α}−1} ; i+j<2·3^{α}}a_{i,1}(z)a_{j,1}(z)Ψ^{i+j}(εz^{γ})

+ c_{2}(z)_{∑_{0≤i,j≤2·3^{α}−1} ; i+j≥2·3^{α}}a_{i,1}(z)a_{j,1}(z)\frac{1}{(1 + εz^{γ})^{3^{α}}} Ψ^{i+j−2·3^{α}}(εz^{γ})

+ c_{1}(z) ∑_{i=0}^{2·3^{α}−1} a_{i,1}(z)Ψ^{i}(εz^{γ}) + c_{0}(z) = 0 modulo 3. (6.3)

Now we compare coefficients of Ψ^{i}(εz^{γ}), for i = 0, 1, …, 2 · 3^{α} − 1. We claim that the choice of

a_{0,1}(z) = \frac{c_{1}(z)}{c_{2}(z)} = z^{−e_{1}}(1 + εz^{γ})^{−e_{2}}c_{1}(z),  (6.4)

a_{3^{α},1}(z) = ±\frac{(c_{1}^{2}(z) − c_{0}(z)c_{2}(z))^{1/2}}{c_{2}(z)} (1 + εz^{γ})^{3^{α}/2} = ±z^{f_{1}−e_{1}}(1 + εz^{γ})^{f_{2}−e_{2}+ \frac{1}{2} (3^{α}+1)}, (6.5)

with all other a_{i,1}(z)’s vanishing, provides two solutions (depending on the sign in front of the expression for a_{3^{α},1}(z)) modulo 3 to the system of congruences resulting from (6.3) in rational functions a_{i,1}(z). Namely, if we substitute this choice in the left-hand side of (6.3), then we obtain

c_{2}(z)\frac{c_{1}^{2}(z)}{c_{2}^{2}(z)} + 2c_{2}(z)\frac{c_{1}(z)}{c_{2}(z)}a_{3^{α},1}(z)Ψ^{3^{α}}(εz^{γ}) + c_{2}(z)\frac{c_{1}^{2}(z) − c_{0}(z)c_{2}(z)}{c_{2}^{2}(z)}

+ c_{1}(z)\frac{c_{1}(z)}{c_{2}(z)} + c_{1}(z)a_{3^{α},1}(z)Ψ^{3^{α}}(εz^{γ}) + c_{0}(z),

which indeed vanishes modulo 3.

The two solutions given by (6.4) and (6.5) are different modulo 3 since a_{3^{α},1}(z) ≠ 0. They must be the two different solutions modulo 3 guaranteed by Lemma 18 with β = 1. With both these solutions, we enter the iteration step.

Iteration step. We consider the Ansatz (4.5)–(4.6), where the coefficients a_{i,β}(z) are supposed to provide a solution F_{β}(z) = ∑_{i=0}^{2·3^{α}−1} a_{i,β}(z)Ψ^{i}(εz^{γ}) to (6.1) modulo 3^{β}. This Ansatz, substituted in (6.1), produces the congruence

c_{2}(z)F_{β}^{2}(z) + c_{1}(z)F_{β}(z) + c_{0}(z) + 3Q(z; F_{β}(z), F′_{β}(z), F′′(z), …, F_{β}^{(s)}(z))

+ 3^{β}c_{1}(z) ∑_{i=0}^{2·3^{α}−1} b_{i,β+1}(z)Ψ^{i}(εz^{γ})

+ 2 · 3^{β}c_{2}(z) ∑_{i=0}^{2·3^{α}−1} ∑_{j=0}^{2·3^{α}−1} a_{i,β}(z)b_{j,β+1}(z)Ψ^{i+j}(εz^{γ}) = 0 modulo 3^{β+1}.

By our assumption on F_{β}(z), we may divide by 3^{β}. Furthermore, by construction, we know that a_{0,β}(z) = c_{1}(z)/c_{2}(z) modulo 3 and that

a_{3^{α},β}(z) = ±z^{f_{1}−e_{1}}(1 + εz^{γ})^{f_{2}−e_{2}+ \frac{1}{2} (3^{α}+1)} modulo 3

(the sign ± depending on the sign in (6.5)), while all other a_{i,β}(z)’s vanish modulo 3. If we use these facts and also perform the reduction (4.4), then we arrive at the congruence

∑_{i=0}^{2·3^{α}−1} Rat_{i}(z)Ψ^{i}(εz^{γ}) + c_{1}(z) ∑_{i=0}^{2·3^{α}−1} b_{i,β+1}(z)Ψ^{i}(εz^{γ})

+ 2 · c_{2}(z)(\frac{c_{1}(z)}{c_{2}(z)} ∑_{j=0}^{2·3^{α}−1} b_{j,β+1}(z)Ψ^{j}(εz^{γ})

± z^{f_{1}−e_{1}}(1 + εz^{γ})^{f_{2}−e_{2}+ \frac{1}{2} (3^{α}+1)} ∑_{j=0}^{3^{α}−1} b_{j,β+1}(z)Ψ^{j+3^{α}}(εz^{γ})

± z^{f_{1}−e_{1}}(1 + εz^{γ})^{f_{2}−e_{2}− \frac{1}{2} (3^{α}−1)} ∑_{j=3^{α}}^{2·3^{α}−1} b_{j,β+1}(z)Ψ^{j−3^{α}}(εz^{γ})) = 0 modulo 3,

where Rat_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are certain Laurent polynomials in z and 1 + εz^{γ} with integer coefficients. Reducing further modulo 3, this simplifies to

∑_{i=0}^{2·3^{α}−1} Rat_{i}(z)Ψ^{i}(εz^{γ}) ∓ z^{f_{1}}(1 + εz^{γ})^{f_{2}+ \frac{1}{2} (3^{α}+1)} ∑_{j=0}^{3^{α}−1} b_{j,β+1}(z)Ψ^{j+3^{α}}(εz^{γ})

∓ z^{f_{1}}(1 + εz^{γ})^{f_{2}− \frac{1}{2} (3^{α}−1)} ∑_{j=3^{α}}^{2·3^{α}−1} b_{j,β+1}(z)Ψ^{j−3^{α}}(εz^{γ}) = 0 modulo 3.

Comparison of powers of Ψ(εz^{γ}) then yields the system of congruences

±z^{f_{1}}(1 + εz^{γ})^{g_{i}}b_{i,β+1}(z) = Rat_{i+3^{α}}(z) modulo 3, i = 0, 1, …, 2 · 3^{α} − 1,

where g_{i} = f_{2} + \frac{1}{2}(3^{α} + 1) if 0 ≤ i < 3^{α}, g_{i} = f_{2} − \frac{1}{2}(3^{α} − 1) if 3^{α} ≤ i < 2 · 3^{α}, and the index i + 3^{α} in Rat_{i+3^{α}}(z) has to be taken modulo 2 · 3^{α}. This system is trivially uniquely solvable. Since we had two different solutions modulo 3 to start with, we now obtain two different solutions F_{β}(z) to (6.1) modulo 3^{β}. These must be the two different solutions modulo 3^{β} guaranteed by Lemma 18. When we arrive at β = 3^{α}, the uniqueness condition (4) guarantees that only one of the two obtained solutions corresponds to F (z) modulo 3^{3^{α}}. Thus, we have proven that the algorithm of Section 4 will produce a solution F_{3^{α}}(z) to (6.1) modulo 3^{3^{α}} which is a polynomial in Ψ(εz^{γ}) with coefficients that are Laurent polynomials in z and 1 + εz^{γ}, and which equals any formal power series solution F (z) to (6.1) when coefficients are reduced modulo 3^{3^{α}}. □

7. Motzkin numbers

Let M_{n} be the n-th Motzkin number, that is, the number of lattice paths from (0, 0) to (n, 0) consisting of steps taken from the set {(1, 0), (1, 1), (1, −1)} never running below the x-axis. It is well-known (cf. [18, Ex. 6.37]) that the generating function M(z) = ∑_{n≥0} M_{n} z^{n} is given by

M(z) = \frac{1 − z − \sqrt{1 − 2z − 3z^{2}}}{2z^{2}} ,  (7.1)

and hence satisfies the functional equation

z^{2}M^{2}(z) + (z − 1)M(z) + 1 = 0.  (7.2)

Theorem 19. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function M(z) = ∑_{n≥0} M_{n} z^{n} for the Motzkin numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z^{3}) of the form

M(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{3}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + z.

Proof. Choosing γ = 1, c_{2}(z) = z^{2}, c_{1}(z) = z − 1, c_{0}(z) = 1, we see that the functional equation (7.2) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 2, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(…) = 0. Consequently, the generating function M(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z) = (1 + z)Ψ(z^{3}). In the formulation of the theorem, we have chosen to express everything in terms of Ψ(z^{3}), since this leads to the more elegant expressions for the moduli 9 and 27 given below. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 20. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} M_{n} z^{n} = 13z^{−1} + 14z^{−2} + (9z + 12 + 24z^{−1} + 21z^{−2}) Ψ(z^{3})

+ (9z^{5} + 12z^{4} + 10z^{3} + 23z^{2} + 25z + 19 + 14z^{−1} + 4z^{−2}) Ψ^{3}(z^{3})
− (9z^{7} + 3z^{6} + 24z^{5} + 30z^{4} + 6z^{3} + 21z^{2} + 6z + 3 + 24z^{−1} + 12z^{−2}) Ψ^{5}(z^{3})
modulo 27. (7.3)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 21. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} M_{n} z^{n} = 4z^{−1} + 5z^{−2} − (3 + 6z^{−1} + 3z^{−2}) Ψ(z^{3})

+ (3z^{4} + 4z^{3} + 2z^{2} + 1z + 4 + 2z^{−1} + 7z^{−2}) Ψ^{3}(z^{3}) modulo 9. (7.4)

8. Motzkin prefix numbers

Let MP_{n} be the n-th Motzkin prefix number, that is, the number of lattice paths from (0, 0) consisting of n steps taken from the set {(1, 0), (1, 1), (1, −1)} never running below the x-axis. It is easy to see that the generating function MP (z) = ∑_{n≥0} MP_{n} z^{n} satisfies the functional equation

z(1 − 3z)MP^{2}(z) + (1 − 3z)MP (z) − 1 = 0.  (8.1)

Namely, let again M(z) denote the generating function for Motzkin numbers (see Section 7). Then, by an elementary combinatorial decomposition (a Motzkin prefix can be empty, it can start with a horizontal step followed by a Motzkin prefix, it can start with a step (1, 1) and never return to the x-axis, or start with a step (1, 1), return to the x-axis for the first time by a step (1, −1), and then be followed by a Motzkin prefix), we have

MP (z) = 1 + 2z MP (z) + z^{2}M(z)MP (z).

Combined with (7.1), this yields an explicit expression for MP (z), from which the functional equation (8.1) can be derived.

Theorem 22. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function MP (z) = ∑_{n≥0} MP_{n} z^{n} for the Motzkin prefix numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z) of the form

MP (z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + z.

Proof. Choosing γ = 1, c_{2}(z) = z(1 − 3z), c_{1}(z) = 1 − 3z, c_{0}(z) = −1, we see that the functional equation (8.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 1, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(…) = 0. Consequently, the generating function MP (z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z), as claimed. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 23. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} MP_{n} z^{n} = 13z^{−1} + (9z + 6z^{−1} + 15) Ψ(z) − (6z^{2} + 16z + 4z^{−1} + 14) Ψ^{3}(z)

− (9z^{3} + 15z^{2} + 18z + 15z^{−1}) Ψ^{5}(z) modulo 27. (8.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 24. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} MP_{n} z^{n} = 4z^{−1} + 3 (1 + z^{−1}) Ψ(z) + (3z^{2} − z + 7 + 2z^{−1}) Ψ^{3}(z) modulo 9. (8.3)

9. Riordan numbers

Let R_{n} be the n-th Riordan number, that is, the number of lattice paths from (0, 0) to (n, 0) consisting of steps taken from the set {(1, 0), (1, 1), (1, −1)} never running below the x-axis, and where steps (1, 0) are not allowed on the x-axis. It is easy to see that the generating function R(z) = ∑_{n≥0} R_{n} z^{n} satisfies the functional equation

z(1 + z)R^{2}(z) − (z + 1)R(z) + 1 = 0.  (9.1)

Namely, let again M(z) denote the generating function for Motzkin numbers (see Section 7). Then, by an elementary combinatorial decomposition (a path as above can be empty, or it may start with a step (1, 1), return to the x-axis for the first time by a step (1, −1), and then be followed by a path of the above type), we have

R(z) = 1 + z^{2}M(z)R(z).

Combined with (7.1), this yields an explicit expression for R(z), from which the functional equation (9.1) can be derived.

Theorem 25. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function R(z) = ∑_{n≥0} R_{n} z^{n} for the Riordan numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z^{3}) of the form

R(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{3}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + z.

Proof. Choosing γ = 1, c_{2}(z) = z(1 + z), c_{1}(z) = −z − 1, c_{0}(z) = 1, we see that the functional equation (9.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 1, e_{2} = 1, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(…) = 0. Consequently, the generating function R(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z) = (1 + z)Ψ(z^{3}). In the formulation of the theorem, we have chosen to express everything in terms of Ψ(z^{3}), since this leads to the more elegant expressions for the moduli 9 and 27 given below. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 26. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} R_{n} z^{n} = 14z^{−1} + (9 + 21z^{−1}) Ψ(z) + (9z^{2} + 30z + 25 + 4z^{−1}) Ψ^{3}(z)

+ (18z^{2} + 24z + 21 + 15z^{−1}) Ψ^{5}(z) modulo 27. (9.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 27. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} R_{n} z^{n} = −4z^{−1} − 3z^{−1}Ψ(z) + (3z + 10 + 7z^{−1}) Ψ^{3}(z) modulo 9.  (9.3)

These results generalise Corollary 4.12 in [3], which is an easy consequence.

10. Central trinomial coefficients

Let T_{n} be the n-th central trinomial coefficient, that is, the coefficient of t^{n} in (1 + t + t^{2})^{n}. Already Euler knew that the generating function T (z) = ∑_{n≥0} T_{n} z^{n} equals 1/\sqrt{1 − 2z − 3z^{2}} (cf. [18, solution to Exercise 6.42]). Consequently, T (z) satisfies the functional equation

(1 − 2z − 3z^{2})T^{2}(z) − 1 = 0.  (10.1)

Theorem 28. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function T (z) = ∑_{n≥0} T_{n} z^{n} for the trinomial coefficients, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z^{3}) of the form

T (z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{3}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + z.

Proof. Choosing γ = 1, c_{2}(z) = 1 − 2z − 3z^{2}, c_{1}(z) = 0, c_{0}(z) = −1, we see that the functional equation (10.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 0, e_{2} = 1, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(…) = 0. Consequently, the generating function T (z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z) = (1 + z)Ψ(z^{3}). In the formulation of the theorem, we have chosen to express everything in terms of Ψ(z^{3}), since this leads to the more elegant expressions for the moduli 9 and 27 given below. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 29. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} T_{n} z^{n} = − (9z^{2} + 24z + 15) Ψ(z^{3})+(15z^{5} + 25z^{4} + 4z^{3} + 12z^{2} + 10z + 19) Ψ^{3}(z^{3})

+ (9z^{8} + 6z^{7} + 6z^{6} + 9z^{5} + 21z^{4} + 3z^{3} + 15z + 24) Ψ^{5}(z^{3}) modulo 27. (10.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 30. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} T_{n} z^{n} = −3(z + 1)Ψ(z^{3}) + (−3z^{5} + z^{4} + 7z^{3} + 3z^{2} + 4z + 4) Ψ^{3}(z^{3}) modulo 9.

(10.3)

11. Central binomial coefficients and their sums

In this section we consider the sequence (\binom{2n}{n})_{n≥0} of central binomial numbers. It follows from the binomial theorem that the corresponding generating function CB(z) is given by

CB(z) := ∑_{n≥0} \binom{2n}{n} z^{n} = \frac{1}{\sqrt{1 − 4z}} ,

and hence satisfies the functional equation

(1 − 4z)CB^{2}(z) − 1 = 0.  (11.1)

Theorem 31. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function CB(z) = ∑_{n≥0} \binom{2n}{n} z^{n} for the central binomial numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(−z) of the form

CB(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(−z) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 − z.

Proof. Choosing γ = 1, c_{2}(z) = 1−4z, c_{1}(z) = 0, c_{0}(z) = −1, we see that the functional equation (11.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 − z modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 0, e_{2} = 1, f_{1} = 0, f_{2} = 0, ε = −1, and we have Q(…) = 0. Consequently, the generating function CB(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(−z), as claimed. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 32. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} \binom{2n}{n} z^{n} = (9\frac{1 + z}{1 − z} + 3) Ψ(−z) − (4z + 8)Ψ^{3}(−z)

− (12z^{2} + 12z + 3) Ψ^{5}(−z) modulo 27. (11.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 33. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} \binom{2n}{n} z^{n} = −3Ψ(−z) + (2z + 4)Ψ^{3}(−z) modulo 9.  (11.3)

These results generalise Theorem 4.3 in [3], which is an easy consequence.

We next turn to sums of central binomial coefficients. From (11.1) it follows directly that

(1 − 4z)(1 − z)^{2}SCB^{2}(z) − 1 = 0,  (11.4)

where

SCB(z) := ∑_{n≥0} z^{n} ∑_{k=0}^{n} \binom{2k}{k}.

Theorem 34. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function SCB(z) = ∑_{n≥0} z^{n} ∑_{k=0}^{n} \binom{2k}{k} for sums of central binomial numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(−z) of the form

SCB(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(−z) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 − z.

Proof. Choosing γ = 1, c_{2}(z) = (1 − 4z)(1 − z)^{2}, c_{1}(z) = 0, c_{0}(z) = −1, we see that the functional equation (11.4) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = (1 − z)^{3} modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 0, e_{2} = 3, f_{1} = 0, f_{2} = 1, ε = −1, and we have Q(…) = 0. Consequently, the generating function SCB(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(−z) = (1 − z)Ψ(−z^{3}). In the formulation of the theorem, we have chosen to express everything in terms of Ψ(−z^{3}), since this leads to the more elegant expressions for the moduli 9 and 27 given below. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 35. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} z^{n} ∑_{k=0}^{n} \binom{2k}{k} = + (3 + 9\frac{z + 1}{1 − z}) Ψ(−z^{3}) + (−4z^{3} + 12z + 19) Ψ^{3}(−z^{3})

+ (15z^{6} + 9z^{5} + 15z^{3} + 18z^{2} + 24) Ψ^{5}(−z^{3}) modulo 27. (11.5)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 36. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} z^{n} ∑_{k=0}^{n} \binom{2k}{k} = −3Ψ(−z^{3}) + (4 + 3z + 2z^{3}) Ψ^{3}(−z^{3}) modulo 9.  (11.6)

These results generalise Theorem 5.7 in [3], which is an easy consequence.

12. Catalan numbers

Let C_{n} = \frac{1}{n+1} \binom{2n}{n} be the n-th Catalan number. It is well-known (cf. [18, equation below (6.18) with k = 2]) that the generating function C(z) = ∑_{n≥0} C_{n} z^{n} satisfies the functional equation

zC^{2}(z) − C(z) + 1 = 0.  (12.1)

Theorem 37. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function C(z) = ∑_{n≥0} C_{n}z^{n} for the Catalan numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(−z) of the form

C(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(−z) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 − z.

Proof. Choosing γ = 1, c_{2}(z) = z, c_{1}(z) = −1, c_{0}(z) = 1, we see that the functional equation (12.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 − z modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 1, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = −1, and we have Q(…) = 0. Consequently, the generating function C(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(−z), as claimed. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 38. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} C_{n} z^{n} = −13z^{−1} − 3 (4 + 2z^{−1}) Ψ(−z) + (−8z − 14 + 4z^{−1}) Ψ^{3}(−z)

+ 3 (z^{2} − 6z + 9 − 4z^{−1}) Ψ^{5}(−z) modulo 27. (12.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 39. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} C_{n} z^{n} = −4z^{−1} + 3 (1 − z^{−1}) Ψ(−z) + (4z − 2 − 2z^{−1}) Ψ^{3}(−z) modulo 9. (12.3)

These results generalise Theorem 5.2 in [3], which is an easy consequence.

13. Central Delannoy numbers

Let D_{n} be the n-th central Delannoy number, that is, the the number of lattice paths from (0, 0) to (n, n) consisting of steps taken from the set {(1, 0), (0, 1), (1, 1)}. It is well-known (see [18, Ex. 6.3.8]) that the generating function D(z) = ∑_{n≥0} D_{n} z^{n} equals 1/\sqrt{1 − 6z + z^{2}}. Consequently, D(z) satisfies the functional equation

(1 − 6z + z^{2})D^{2}(z) − 1 = 0.  (13.1)

Theorem 40. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function D(z) = ∑_{n≥0} D_{n} z^{n} for the central Delannoy numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z^{2}) of the form

D(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{2}) modulo 3^{3^{α}},

Proof. Choosing γ = 2, c_{2}(z) = 1 − 6z + z^{2}, c_{1}(z) = 0, c_{0}(z) = −1, we see that the functional equation (13.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z^{2} modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 0, e_{2} = 1, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(…) = 0. Consequently, the generating function D(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z^{2}), as claimed. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 41. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} D_{n} z^{n} = (3 + 9\frac{(z + 2)^{2}}{1 + z^{2}} ) Ψ(z^{2}) + (19z^{2} + 3z + 19) Ψ^{3}(z^{2})

− (3z^{4} + 9z^{3} + 6z^{2} + 9z + 3) Ψ^{5}(z^{2}) modulo 27. (13.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 42. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} D_{n} z^{n} = −3Ψ(z^{2}) + (4z^{2} + 3z + 4) Ψ^{3}(z^{2}) modulo 9.  (13.3)

These results generalise the part on central Delannoy numbers in Theorem 5.15 of [3], which is an easy consequence.

14. Schröder numbers

Let S_{n} be the n-th (large) Schröder number, that is, the number of lattice paths from (0, 0) to (2n, 0) consisting of steps taken from the set {(2, 0), (1, 1), (1, −1)} never running below the x-axis. It is well-known (cf. [18, Second Problem on page 178]) that the generating function S(z) = ∑_{n≥0} S_{n} z^{n} is given by

S(z) = \frac{1 − z − \sqrt{1 − 6z + z^{2}}}{2z} ,

and hence satisfies the functional equation

zS^{2}(z) + (z − 1)S(z) + 1 = 0.  (14.1)

Theorem 43. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function S(z) = ∑_{n≥0} S_{n}z^{n} for the Schröder numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z^{2}) of the form

S(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{2}) modulo 3^{3^{α}},

Proof. Choosing γ = 2, c_{2}(z) = z, c_{1}(z) = z − 1, c_{0}(z) = 1, we see that the functional equation (14.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z^{2} modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 1, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(…) = 0. Consequently, the generating function S(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z^{2}), as claimed. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 44. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} S_{n} z^{n} = 13 + 14z^{−1} + (21z + 18 + 21z^{−1}) Ψ(z^{2})

+ (4z^{3} + 15z^{2} + 17z + 15 + 4z^{−1}) Ψ^{3}(z^{2})

+ (15z^{5} + 9z^{4} + 18z^{3} + 18z^{2} + 18z + 9 + 15z^{−1}) Ψ^{5}(z^{2}) modulo 27. (14.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 45. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} S_{n} z^{n} = 4 + 5z^{−1} − 3 (z + z^{−1}) Ψ(z^{2}) − (2z^{3} + 3z^{2} + 4z + 3 + 2z^{−1}) Ψ^{3}(z^{2})

modulo 9. (14.3)

Schröder numbers have not been considered in [3].

15. Hex tree numbers

Let H_{n} be the n-th hex tree number, that is, the number of planar rooted trees where each vertex may have a left, a middle, or a right descendant, but never a left and middle descendant, and never a middle and right descendant. By an elementary combinatorial decomposition, it is easy to see that the generating function H(z) = ∑_{n≥0} H_{n} z^{n} satisfies the functional equation

z^{2}H^{2}(z) + (3z − 1)H(z) + 1 = 0.  (15.1)

Theorem 46. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function H(z) = ∑_{n≥0} H_{n} z^{n} for the hex tree numbers, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(−z^{2}) of the form

H(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(−z^{2}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 − z^{2}.

Proof. Choosing γ = 2, c_{2}(z) = z^{2}, c_{1}(z) = 3z − 1, c_{0}(z) = 1, we see that the functional equation (15.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 − z^{2} modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 2, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = −1, and we have Q(…) = 0. Consequently, the generating function H(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z^{2}), as claimed. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 47. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} H_{n} z^{n} = 12z^{−1} + 14z^{−2} − 3 (4 + 3z^{−1} + 2z^{−2}) Ψ(−z^{2})

+ (z^{2} + 21z + 13 + 15z^{−1} + 4z^{−2}) Ψ^{3}(−z^{2})

+ 3 (z^{4} + 3z^{3} + 12z^{2} + 21z + 3z^{−1} + 14z^{−2}) Ψ^{5}(−z^{2}) modulo 27. (15.2)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 48. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} H_{n} z^{n} = −4z^{−2} + 3 (1 + 3z^{−1} + 2z^{−2}) Ψ(−z^{2})

+ (4z^{2} + 7 + 7z^{−2}) Ψ^{3}(−z^{2}) modulo 9. (15.3)

These results generalise Theorem 5.3 in [3], which is an easy consequence.

16. Free subgroup numbers for lifts of the inhomogeneous modular group

Let f_{λ} be the number of free subgroups of P SL_{2}(ℤ) of index 6λ. More generally, let f_{λ}(m) denote the number of free subgroups of index 6mλ in the lift Γ_{m}(3) of P SL_{2}(ℤ) defined by

Γ_{m}(3) = C_{2m} ∗_{C_{m}} C_{3m} = ⟨x, y | x^{2m} = y^{3m} = 1, x^{2} = y^{3}⟩, m ≥ 1.

Clearly, we have f_{λ} = f_{λ}(1).

The generating function F_{m}(z) = 1 + ∑_{λ≥1} f_{λ}(m)z^{λ} satisfies the Riccati differential equation (see [10, Eq. (18)] with 𝔊 = Γ_{m}(q), or [7, Eq. (8.1)])

zF_{m}^{2}(z) − (1 − (6m − 2)z)F_{m}(z) + 6mz^{2}F′_{m}(z) + 1 + (1 − 6m + 5m^{2})z = 0. (16.1)

It is not hard to see that, if m is divisible by 3, then v_{3}(f_{λ}(m)) will increase with λ, that is, the sequence f_{λ}(m) is ultimately zero modulo any given 3-power.

Theorem 49. Let Ψ(z) be given by (1.1), let m be a positive integer not divisible by 3, and let α be some positive integer. Then the generating function F_{m}(z) for the free subgroup numbers f_{λ}(m), when reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z^{6}) of the form

F_{m}(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{6}) modulo 3^{3^{α}},

Proof. Choosing γ = 2, c_{2}(z) = −z, c_{1}(z) = 1−(6m−2)z, c_{0}(z) = 1−(1−6m+5m^{2})z, we see that the functional equation (16.1) fits into the framework of Theorem 17, since

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z^{2} modulo 3.

The constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 1, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = 1, and we have Q(⋯) = 6mz^{2}F′_{m}(z). Consequently, the generating function F_{m}(z), when reduced modulo 3^{3^{α}}, can be written as a polynomial in the basic series Ψ(z^{2}) = (1 + z^{2})Ψ(z^{6}). In the formulation of the theorem, we have chosen to express everything in terms of Ψ(z^{6}), since this leads to the more elegant expressions for the moduli 9 and 27 given below. □

We have implemented the algorithm explained in the above proof. For α = 1, it produces the following result.

Theorem 50. Let Ψ(z) be given by (1.1). Then, for all positive integers m ≡ 1 (mod 3), we have

1 + ∑_{λ≥1} f_{λ}(m) z^{λ} = 1 − z^{−1} − 3\frac{(z + 2) (z^{2} + 2z + 2)}{z (z^{2} + 1)} − \frac{9 + 3(m − 1)z^{4}}{(z^{2} + 1)^{2}}

+ (3mz^{3} + (3m + 21)z + 21z^{−1}) Ψ(z^{6})
+ ((−2m + 18)z^{9} + (−m^{2} + 6m + 18)z^{7} + (−3m + 25)z^{5}
+(m + 15)z^{3} + (2m^{2} − 3m + 6)z + 4z^{−1}) Ψ^{3}(z^{6})

+ ((−3m + 9)z^{15} + (−3m + 6)z^{13} + 15z^{11} + (3m + 9)z^{9} + (3m + 3)z^{7}

+3z^{5} + (−3m + 9)z^{3} + (−3m + 6)z + 15z^{−1}) Ψ^{5}(z^{6}) modulo 27. (16.2)

Furthermore, for all positive integers m ≡ 2 (mod 3), we have

1 + ∑_{λ≥1} f_{λ}(m) z^{λ} = 1 − z^{−1} + 3\frac{(z + 1) (z^{2} + z + 2)}{z (z^{2} + 1)}

+ \frac{9 + 18z + 18z^{2} + 9z^{3} + 9z^{4} − (3m − 24)z^{5}}{(z^{2} + 1)^{2}}

+ (−3mz^{3} + (−3m + 21)z + 21z^{−1}) Ψ(z^{6})

+ ((15m^{2} − 4m + 24)z^{9} + (−m^{2} + 3m)z^{7} + (3m − 2)z^{5}
+(−m + 15)z^{3} + (14m^{2} + 18)z + 4z^{−1}) Ψ^{3}(z^{6})

+ ((3m + 9)z^{15} + (3m + 6)z^{13} + 15z^{11} + (−3m + 9)z^{9} + (−3m + 3)z^{7}

+3z^{5} + (3m + 9)z^{3} + (3m + 6)z + 15z^{−1}) Ψ^{5}(z^{6}) modulo 27. (16.3)

In the case of modulus 9, this theorem reduces to the following result.

Corollary 51. Let Ψ(z) be given by (1.1).Then, for all positive integers m ≡ 1 (mod 3), we have

1 + ∑_{λ≥1} f_{λ}(m) z^{λ} = 1 − 4z^{−1} − 3\frac{z^{2}}{z^{2} + 1} − 3z^{−1} (z^{2} + 1)^{2} Ψ(z^{6})

+ (mz^{9} + (m + 1)z^{7} + 7z^{5} + mz^{3} + (m + 1)z + 7z^{−1}) Ψ^{3}(z^{6}) modulo 9. (16.4)

Furthermore, for all positive integers m ≡ 2 (mod 3), we have

1 + ∑_{λ≥1} f_{λ}(m) z^{λ} = 1 + 5z^{−1} + 3\frac{z^{2}}{z^{2} + 1} − 3z^{−1}(1 + z^{2})^{2}Ψ(z^{6})

− (mz^{9} + (m − 1)z^{7} + 2z^{5} + mz^{3} + (m − 1)z + 2z^{−1})Ψ^{3}(z^{6}) modulo 9. (16.5)

We have chosen this section to demonstrate that generating function results such as the ones in Theorem 50 and Corollary 51, in combination with the coefficient extraction procedure described in the beginning of the appendix, lead naturally to an explicit description of the congruence classes modulo any given 3-power of the elements of the sequence that we are considering. We illustrate this point with the sequence of free subgroup numbers f_{λ} = f_{λ}(1) of the inhomogeneous modular group P SL_{2}(ℤ). In the statement of the result below, we use notation from word calculus: by S^{∗}, where S is a set of letters, we mean the set of all words with letters from S. By a slight misuse of notation, the symbol a^{∗}, where a is a letter, will denote the set {ε, a, aa, aaa, … }, with ε standing for the empty word. Finally, if we write S_{1}S_{2}, where S_{1} and S_{2} are two sets of words, then we mean the set of all concatenations w_{1}w_{2} with w_{1} ∈ S_{1} and w_{2} ∈ S_{2}. Since our words represent ternary strings, we make the convention that 0’s at the beginning of a word may be added or deleted at will. (The point of view which we shall adopt later in the statements of Theorem 54, Proposition 68, Corollary 69, Proposition 71, and Corollary 72 is to consider these strings as left-infinite strings, where one has added an infinite string of 0’s on the left of a finite word if necessary.)

Theorem 52. We have:

(1) f_{λ} ≡ 1 (mod 9), if, and only if, the 3-adic expansion of n is an element of

{0} ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k}0^{∗}10^{∗}00 ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k+2}0^{∗}10

∪ ⋃_{k≥0} (22^{∗}00^{∗})^{3k+2}2^{∗}12 ∪ ⋃_{k≥0} (22^{∗}00^{∗})^{3k}2^{∗}12^{∗}22;

(2) f_{λ} ≡ 4 (mod 9), if, and only if, the 3-adic expansion of n is an element of

⋃_{k≥0} (00^{∗}22^{∗})^{3k+2}0^{∗}10^{∗}00 ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k+1}0^{∗}10

∪ ⋃_{k≥0} (22^{∗}00^{∗})^{3k+1}2^{∗}12 ∪ ⋃_{k≥0} (22^{∗}00^{∗})^{3k+2}2^{∗}12^{∗}22;

(3) f_{λ} ≡ 7 (mod 9), if, and only if, the 3-adic expansion of n is an element of

{10} ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k+1}0^{∗}10^{∗}00 ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k}0^{∗}10

∪ ⋃_{k≥0} (22^{∗}00^{∗})^{3k}2^{∗}12 ∪ ⋃_{k≥0} (22^{∗}00^{∗})^{3k+1}2^{∗}12^{∗}22;

(4) f_{λ} ≡ 2 (mod 9), if, and only if, the 3-adic expansion of n is an element of

⋃_{k≥0} (00^{∗}22^{∗})^{3k+2}0^{∗}01 ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k+1}1;

(5) f_{λ} ≡ 5 (mod 9), if, and only if, the 3-adic expansion of n is an element of

⋃_{k≥0} (00^{∗}22^{∗})^{3k}0^{∗}01 ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k+2}1;

(6) f_{λ} ≡ 8 (mod 9), if, and only if, the 3-adic expansion of n is an element of

⋃_{k≥0} (00^{∗}22^{∗})^{3k+1}0^{∗}01 ∪ ⋃_{k≥0} (00^{∗}22^{∗})^{3k+3}1;

(7) f_{λ} ≡ 3 (mod 9), if, and only if, λ ≡ 0 (mod 4) or the 3-adic expansion of n is

an element of

{0, 2}^{∗}11{0, 2}^{∗}1,

(8) f_{λ} ≡ 6 (mod 9), if, and only if, λ ≡ 2 (mod 4) or the 3-adic expansion of n is an element of

{0, 2}^{∗}1022^{∗} ∪ {0, 2}^{∗}1200^{∗} ∪ {0, 2}^{∗}11{0, 2}^{∗}100^{∗} ∪ {0, 2}^{∗}11{0, 2}^{∗}122^{∗}.

(9) In all other cases, this coefficient is divisible by 9.

Proof. One performs a (lengthy) case analysis using Corollary 51 with m = 1 in combination with the descriptions of the coefficients of Ψ^{3}(z) modulo 9, which one obtains by carrying out the approach sketched in Section 2 (see in particular the paragraphs after (2.6) and (2.7)) and the appendix, the resulting congruences being explicitly displayed in Corollary 69. □

The next corollary corrects Theorem 3(i) in [11].

Corollary 53. We have:

(1) f_{λ} ≡ −1 (mod 3) if, and only if, the 3-adic expansion of λ is an element of {0, 2}^{∗}1;

(2) f_{λ} ≡ 1 (mod 3) if, and only if, the 3-adic expansion of λ is an element of

{0, 2}^{∗}100^{∗} ∪ {0, 2}^{∗}122^{∗};

(3) for all other λ, we have f_{λ} ≡ 0 (mod 3).

Remark. The conditions in Items (1) and (2) imply that the 3-adic expansion of λ always contains exactly one digit 1. In Item (1), this 1 is the first digit from the right. In Item (2), this 1 is not the right-most digit, and it has only 0’s or only 2’s to its right.

With some additional effort, by using Theorem 50 with m = 1 and the coefficient congruences modulo 27 for Ψ^{3}(z) and Ψ^{5}(z) worked out in Propositions 68 and 71, one is also able to refine the result in Theorem 52 to a description of the congruence classes of f_{λ} modulo 27. The outcome is lengthy. As an illustration, we provide the explicit characterisation of all λ for which f_{λ} ≡ 1 (mod 27). For the statement of the result, we need to introduce some statistics on strings consisting of 0’s, 1’s, and 2’s. Given a string s = … s_{2}s_{1}s_{0}, we define:

#2str(s) = #(maximal strings of 2’s in s),
#Iso_{3}(s) = #(isolated 0’s and 2’s in s, excluding s_{0}, s_{1}, s_{2}),
#022(s) = #(occurrences of the substring 022 in s),

and similarly for #200(s), #201(s), #21(s), #021(s). Here, by an isolated letter, we mean a letter a whose neighbours are different from a. We use again the word notation explained before Theorem 52. In particular, we consider all strings as infinite strings with infinitely many 0’s added to the left, so that #022(.) also counts an occurrence of 22 at the beginning of a(n originally finite) string.

Theorem 54. We have f_{λ} ≡ 1 (mod 27), if, and only if, the 3-adic expansion of n is an element of {0, 2}^{∗}0100 and satisfies #2str(s) ≡ 0 (mod 3) and

\frac{2 #2str(s)}{3} − #Iso_{3}(s) + #022(s) + #200(s) + #201(s) ≡ 0 (mod 3),

or of {0, 2}^{∗}2100 and satisfies #2str(s) ≡ 0 (mod 3) and

\frac{2 #2str(s)}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 1 (mod 3),

or of {0, 2}^{∗}10^{∗}0000 and satisfies #2str(s) ≡ 0 (mod 3) and

\frac{2 #2str(s)}{3} − #Iso_{3}(s) − #21(s) + #022(s) + #200(s) + #201(s) ≡ 2 (mod 3),

or of {0, 2}^{∗}1000 and satisfies #2str(s) ≡ 0 (mod 3) and

\frac{2 #2str(s)}{3} − #Iso_{3}(s) − #21(s) + #022(s) + #200(s) + #201(s) ≡ 1 (mod 3),

or of {0, 2}^{∗}2210 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−1}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 0 (mod 3),

or of {0, 2}^{∗}0210 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−1}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 1 (mod 3),

or of {0, 2}^{∗}010 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−1}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 2 (mod 3),

or of {0, 2}^{∗}0010 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−1}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 0 (mod 3),

or of {0, 2}^{∗}0012 and satisfies #2str(s) ≡ 0 (mod 3) and

\frac{2 #2str(s)−3}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 0 (mod 3),

or of {0, 2}^{∗}0212 and satisfies #2str(s) ≡ 1 (mod 3) and

\frac{2 #2str(s)−2}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 0 (mod 3),

or of {0, 2}^{∗}2012 and satisfies #2str(s) ≡ 0 (mod 3) and

\frac{2 #2str(s)−3}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 1 (mod 3),

or of {0, 2}^{∗}2212 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 1 (mod 3),

or of {0, 2}^{∗}0122 and satisfies #2str(s) ≡ 1 (mod 3) and

\frac{2 #2str(s)−2}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 0 (mod 3),

or of {0, 2}^{∗}2122 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−4}{3} − #Iso_{3}(s) + #022(s) + #200(s) − #021(s) ≡ 2 (mod 3),

or of {0, 2}^{∗}01222 and satisfies #2str(s) ≡ 1 (mod 3) and

\frac{2 #2str(s)−2}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 2 (mod 3),

or of {0, 2}^{∗}21222 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−1}{3} − #Iso_{3}(s) + #022(s) + #200(s) − #021(s) ≡ 2 (mod 3),

or of {0, 2}^{∗}012^{∗}2222 and satisfies #2str(s) ≡ 1 (mod 3) and

\frac{2 #2str(s)−2}{3} − #Iso_{3}(s) + #022(s) + #200(s) ≡ 2 (mod 3),

or of {0, 2}^{∗}212^{∗}2222 and satisfies #2str(s) ≡ 2 (mod 3) and

\frac{2 #2str(s)−1}{3} − #Iso_{3}(s) + #022(s) + #200(s) − #021(s) ≡ 2 (mod 3).

17. Central Eulerian numbers

The Eulerian number A(n, k) is defined as the number of permutations of {1, 2, …, n} with exactly k − 1 descents. It is well-known that

A(n, k) = ∑_{j=0}^{k}(−1)^{k−j}\binom{n + 1}{k − j}j^{n};  (17.1)

see [17, Eq. (1.37)] (one has to multiply both sides of that equation by (1 − x)^{d+1} and compare coefficients of powers of x). In this section, we analyse the behaviour of central Eulerian numbers, that is, the numbers A(2n, n) = A(2n, n+1) and A(2n−1, n), modulo powers of 3. Theorems 59 and 62 below say that, again, the generating functions for central Eulerian numbers, when coefficients are reduced modulo a given power of 3, can be written in terms of a polynomial in the basic series Ψ(z). However, the arguments establishing this claim are much more elaborate. The principal reason for this is that it is (likely) not possible to find a single differential equation of the form (1.2), which we could use as starting point for the application of our method. Rather, we have to first reduce the central Eulerian numbers partially modulo the relevant 3-power, and only then do we succeed to show that the generating function for the reduced numbers satisfies a functional equation of the type (6.1) so that Theorem 17 can be applied. In order to accomplish this, we need a number of auxiliary results.

Lemma 55. For any positive integer S, we have the (differential) operator equation

((x + 1)\frac{d}{dx})^{S} = ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{S}) (x + 1)^{m} \frac{d^{m}}{dx^{m}} .  (17.2)

Proof. We proceed by induction on S. Clearly, Equation (17.2) holds for S = 1. For the induction step, we compute

((x + 1)\frac{d}{dx})^{S+1} = (x + 1)\frac{d}{dx} ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{S}) (x + 1)^{m} \frac{d^{m}}{dx^{m}}

= ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{S}) m(x + 1)^{m} \frac{d^{m}}{dx^{m}}

+ ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{S}) (x + 1)^{m+1} \frac{d^{m+1}}{dx^{m+1}}

= ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}m (\binom{m}{k} − \binom{m − 1}{k}) k^{S}) (x + 1)^{m} \frac{d^{m}}{dx^{m}}

+ \frac{1}{S!} (∑_{k=1}^{S}(−1)^{S−k}\binom{S}{k}k^{S}) (x + 1)^{S+1} \frac{d^{S+1}}{dx^{S+1}}

= ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}m\binom{m − 1}{k − 1}k^{S}) (x + 1)^{m} \frac{d^{m}}{dx^{m}}

+ \frac{1}{S!} (∑_{k=1}^{S}(−1)^{S−k}\binom{S}{k}k^{S}) (x + 1)^{S+1} \frac{d^{S+1}}{dx^{S+1}}

= ∑_{m=1}^{S} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{S+1}) (x + 1)^{m} \frac{d^{m}}{dx^{m}}

+ \frac{1}{S!} (∑_{k=1}^{S}(−1)^{S−k}\binom{S}{k}k^{S}) (x + 1)^{S+1} \frac{d^{S+1}}{dx^{S+1}} .  (17.3)

At this point we use again the shift operator E and the forward difference operator △ defined in the proof of Lemma 11. The symbol I stands for the identity operator. In terms of these operators, we may write

\frac{1}{S!} (∑_{k=1}^{S}(−1)^{S−k}\binom{S}{k}k^{S}) = \frac{1}{S!} (∑_{k=1}^{S}(−1)^{S−k}\binom{S}{k}E^{k}y^{S}|_{y=0})

= \frac{1}{S!}(E − I)^{S}y^{S}|_{y=0} = \frac{1}{S!} △^{S} y^{S}|_{y=0} = 1,

the last equality being due to the fact that the difference operator △ lowers the degree of the polynomial to which it is applied by 1, and it multiplies the leading coefficient by the degree of the corresponding monomial. But then

\frac{1}{S!} (∑_{k=1}^{S}(−1)^{S−k}\binom{S}{k}k^{S}) = \frac{1}{(S + 1)!} (∑_{k=1}^{S+1}(−1)^{S+1−k}\binom{S + 1}{k}k^{S+1}) ,

and if this is substituted back into the last line of (17.3), then we get the required result. □

Lemma 56. For any positive integer M, we have

(−1 + \sqrt{1 + 4z})^{M} − (−1 − \sqrt{1 + 4z})^{M} = (−1)^{M+1}2^{M} \sqrt{1 + 4z} ∑_{ℓ≥0} \binom{M − ℓ − 1}{ℓ}z^{ℓ}

(17.4)

and

(−1 + \sqrt{1 + 4z})^{M} + (−1 − \sqrt{1 + 4z})^{M} = (−1)^{M}2^{M} ∑_{ℓ≥0} \frac{M}{M − ℓ}\binom{M − ℓ}{ℓ}z^{ℓ}. (17.5)

Remark. The sums over ℓ on the right-hand sides of (17.4) and (17.5) are essentially Chebyshev polynomials of the second and first kind, respectively (cf. [13]). It is easy to see (and well-known) that they are polynomials in z with integer coefficients.

Proof of Lemma 56. We start with the proof of (17.4). According to the binomial theorem, the left-hand side can be written as

(−1 + \sqrt{1 + 4z})^{M} − (−1 − \sqrt{1 + 4z})^{M}

= (−1)^{M} ∑_{j=0}^{M} \binom{M}{j} ((−1)^{j}(1 + 4z)^{j/2} − (1 + 4z)^{j/2})

= −2(−1)^{M} ∑_{j≥0} \binom{M}{2j + 1}(1 + 4z)^{j+ \frac{1}{2}}

= −2(−1)^{M} \sqrt{1 + 4z} ∑_{j≥0} ∑_{ℓ=0}^{j} \binom{M}{2j + 1}\binom{j}{ℓ}4^{ℓ}z^{ℓ}.

Using the standard hypergeometric notation

pF_{q}[\begin{matrix}a_{1}, …, a_{p} \\ b_{1}, …, b_{q} \end{matrix}; z] = ∑_{m=0}^{∞} \frac{(a_{1})_{m} ⋯ (a_{p})_{m}}{m! (b_{1})_{m} ⋯ (b_{q})_{m}} z^{m},

where, as before, the Pochhammer symbol is defined by (α)_{m} = α(α +1) ⋯ (α +m−1) for m ≥ 1, and (α)_{0} = 1, we have

∑_{j≥0} \binom{M}{2j + 1}\binom{j}{ℓ} = \binom{M}{2ℓ + 1}_{2}F_{1}[\begin{matrix}\frac{1}{2} + ℓ − \frac{M}{2} , 1 + ℓ − \frac{M}{2} \\ \frac{3}{2} + ℓ \end{matrix}; 1] .

This _{2}F_{1}-series can be summed by means of Gauß’ summation formula (see [15, (1.7.6); Appendix (III.3)])

2F_{1}[\begin{matrix}a, b \\ c \end{matrix}; 1] = \frac{Γ(c) Γ(c − a − b)}{Γ(c − a) Γ(c − b)},

where Γ( .) denotes the gamma function. After some simplification, this leads to

∑_{j≥0} \binom{M}{2j + 1}\binom{j}{ℓ} = 2^{M−2ℓ−1}\binom{M − ℓ − 1}{ℓ}.

The proof of (17.5) is completely analogous, and is left to the reader. □

Proposition 57. For any positive integer s, we have

∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2s} = \frac{1}{2} (1 + \sqrt{1 + 4z}) (1 + p_{s}^{(1)}(z)) ,  (17.6)

where p_{s}^{(1)}(z) is a polynomial in z with integer coefficients all of which are divisible by 3, and which satisfies p_{s}^{(1)}(0) = 0. An explicit expression for p_{s}^{(1)}(z) can be derived from (17.8) and (17.9).

Proof. We write the binomial coefficient in terms of a contour integral,

(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j} = \frac{1}{2πi} ∫_{C} \frac{(1 − t)^{2n+1}}{t^{n+2−j}} dt,

where C is the circle of radius 1/2 (say) about the origin, encircling the origin in positive direction. Moreover, we express j^{2s} as

j^{2s} = ((x + 1)\frac{d}{dx})^{2s} (x + 1)^{j}|_{x=0}.

Using these substitutions, the series on the left-hand side of (17.6) becomes

∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2s}

= \frac{1}{2πi} ∫_{C} ∑_{n≥0} z^{n} ∑_{j=0}^{n+1} \frac{(1 − t)^{2n+1}}{t^{n+2−j}} ((x + 1)\frac{d}{dx})^{2s} (x + 1)^{j}|_{x=0} dt

= \frac{1}{2πi} ∫_{C} \frac{1 − t}{t^{2}} ∑_{n≥0} (\frac{(1 − t)^{2}z}{t} )^{n} ((x + 1)\frac{d}{dx})^{2s} ∑_{j=0}^{n+1} (t(x + 1))^{j}|_{x=0} dt

= \frac{1}{2πi} ∫_{C} \frac{1 − t}{t^{2} (1 − \frac{(1−t)^{2}z}{t})} ((x + 1)\frac{d}{dx})^{2s} \frac{1}{1 − (x + 1)t}|_{x=0} dt.

Here, in order to perform the summation over n, we had to assume that z is sufficiently small, say |z| < 1/9, which we shall do for the moment.

In the last integral, we do the substitution t = u/(1 + u)^{2}. After some simplification, this leads to

∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2s}

= \frac{1}{2πi} ∫_{C} \frac{1 + u}{u (u^{2} + u − z)} ((x + 1)\frac{d}{dx})^{2s} \frac{1}{1 + u − (x + 1)u}|_{x=0} du

= \frac{1}{2πi} ∫_{C} \frac{1 + u}{u (u^{2} + u − z)} ∑_{m=1}^{2s} \frac{1}{m!} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s})

· ((x + 1)^{m} \frac{d^{m}}{dx^{m}} \frac{1}{1 + u − (x + 1)u}) |_{x=0} du

= \frac{1}{2πi} ∫_{C} \frac{1 + u}{u^{2} + u − z} ∑_{m=1}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s}) u^{m−1} du,

where we have used Lemma 55 to obtain the next-to-last line.

The integral can easily be evaluated using the residue theorem. Inside the contour C, there is only one singularity, namely a simple pole at u = −\frac{1}{2} + \frac{1}{2} \sqrt{1 + 4z}. (The other pole, at u = −\frac{1}{2} − \frac{1}{2} \sqrt{1 + 4z}, lies outside the contour C.) Hence, we obtain

∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2s}

= \frac{1 + \sqrt{1 + 4z}}{2\sqrt{1 + 4z}} ( ∑_{m=1}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s}) u^{m−1})|_{u=− \frac{1}{2} + \frac{1}{2} \sqrt{1+4z}}. (17.7)

By analytic continuation, we can now get rid of the restriction |z| < 1/9, and, by the transfer principle between analytic and formal power series, we may argue that Identity (17.7) holds on the level of formal power series.

Let us write the polynomial in u given by the sum over m on the right-hand side of (17.7) as a polynomial in 2u + 1, say

q_{s}^{(1)}(2u + 1) := ∑_{m=1}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s}) u^{m−1}.  (17.8)

We claim that q_{s}^{(1)}( .) is an odd polynomial, that is, q_{s}^{(1)}(−2u − 1) = −q_{s}^{(1)}(2u + 1). In order to see this, we use again classical difference operator calculus. As before, we denote by E the shift operator and by △ the forward difference operator (see the proof of Lemma 55). Furthermore, we let ▽ be the backward difference operator defined by ▽f(y) = f(y − 1) − f(y). The reader should observe that △ = E − I and ▽ = E^{−1} − I, where I stands for the identity operator. In terms of these operators, we may rewrite q_{s}^{(1)}(2u + 1) as

q_{s}^{(1)}(2u + 1) = ∑_{m=1}^{2s} ∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}E^{k}y^{2s}|_{y=0}u^{m−1}

= ∑_{m=1}^{2s} △^{m}y^{2s}|_{y=0}u^{m−1}

= △(I − u△)^{−1}(I − (u△)^{2s})y^{2s}|_{y=0}

= △(I − u△)^{−1}y^{2s}|_{y=0},

where the last line is due to the standard fact that △^{a}y^{b} = 0 for all non-negative integers a and b with a > b. Consequently, for q_{s}^{(1)}(−2u − 1) we obtain

q_{s}^{(1)}(−2u − 1) = △(I + (u + 1)△)^{−1}y^{2s}|_{y=0}

= △(E + u△)^{−1}y^{2s}|_{y=0}

= − ▽ (I − u▽)^{−1}y^{2s}|_{y=0}

= − ▽ (I − u▽)^{−1}(I − (u▽)^{2s})y^{2s}|_{y=0}

= − ∑_{m=1}^{2s} u^{m−1} ▽^{m} y^{2s}|_{y=0}

= − ∑_{m=1}^{2s} ∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}E^{−k}y^{2s}|_{y=0}u^{m−1}

= − ∑_{m=1}^{2s} ∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}(−k)^{2s}u^{m−1} = −q_{s}^{(1)}(−2u − 1),

as we claimed. If we recall that (17.7) implies

1 + p_{s}^{(1)}(z) = \frac{1}{\sqrt{1 + 4z}} q_{s}^{(1)}(\sqrt{1 + 4z}) ,  (17.9)

and take into account that, under the substitution u = −\frac{1}{2} + \frac{1}{2} \sqrt{1 + 4z}, we have 2u+1 = \sqrt{1 + 4z}, this establishes all claims of the lemma except for the special form of the polynomial p_{s}^{(1)}(z).

First we prove that p_{s}^{(1)}(0) = 0. To see this, we put z = 0 in (17.9), and we set u = 0 in (17.8), to get

1 + p_{s}^{(1)}(0) = q_{s}^{(1)}(1) = 1,

so that indeed p_{s}^{(1)}(0) = 0.

Next we prove that p_{s}^{(1)}(z) is a polynomial in z with integer coefficients. We use again the relation between p_{s}^{(1)}( .) and q_{s}^{(1)}( .) given in (17.9). For our purposes, it turns out that it is more convenient to work with an anti-symmetrised version of q_{s}^{(1)}(2u + 1). Namely, since we already know that q_{s}^{(1)}(−2u − 1) = −q_{s}^{(1)}(2u + 1), we may replace q_{s}^{(1)}(2u + 1) by \frac{1}{2} (q_{s}^{(1)}(2u + 1) − q_{s}^{(1)}(−2u − 1)). In view of (17.8), this means that

q_{s}^{(1)}(2u + 1) = \frac{1}{2} ∑_{m=1}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s}) (u^{m−1} − (−1 − u)^{m−1}) .

If this is used in (17.9), then we obtain

1 + p_{s}^{(1)}(z) = \frac{1}{2\sqrt{1 + 4z}} ∑_{m=1}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s})
· ((−\frac{1}{2} + \frac{1}{2} \sqrt{1 + 4z})^{m−1} − (−\frac{1}{2} − \frac{1}{2} \sqrt{1 + 4z})^{m−1})

= \frac{1}{2^{m}\sqrt{1 + 4z}} ∑_{m=2}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s})

· ((−1 + \sqrt{1 + 4z})^{m−1} − (−1 − \sqrt{1 + 4z})^{m−1}) .

The reader should note that we were free to start the summation over m at m = 2 in the last expression, since the bracketed factor vanishes for m = 1. Use of Lemma 56 then transforms this identity into

1 + p_{s}^{(1)}(z) = \frac{(−1)^{m}}{2} ∑_{m=2}^{2s} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s}) ∑_{ℓ≥0} \binom{m − ℓ − 2}{ℓ}z^{ℓ}.

The right-hand side is “almost” a polynomial with integer coefficients, only a denominator of 2 remains. This denominator is taken care of by the sum over k; namely we have

∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s} ≡ ∑_{k≥0}(−1)^{m−2k−1}\binom{m}{2k + 1} (mod 2)

≡ (−1)^{m−1} ∑_{k≥0} \binom{m}{2k + 1} (mod 2)

≡ (−1)^{m−1}2^{m−1} ≡ 0 (mod 2)

for m ≥ 2. Hence, the polynomial p_{s}^{(1)}(z) has indeed integer coefficients.

The last remaining assertion is that the coefficients of p_{s}^{(1)}(z) are divisible by 3. Once we have shown that q_{s}^{(1)}(2u+1) = 2u+1 modulo 3, then, in view of (17.9), this last point will also follow. Consequently, in the sequel we consider q_{s}^{(1)}(2u + 1) with coefficients reduced modulo 3. Since, by assumption, s is a positive integer, we have

q_{s}^{(1)}(2u + 1) = ∑_{m=1}^{2s} u^{m−1}_{∑_{k=0}^{m} ; k≢0 mod 3}(−1)^{m−k}\binom{m}{k} modulo 3

= − ∑_{m=1}^{2s} u^{m−1}∑_{k=0}^{m}(−1)^{m−k}\binom{m}{3k} modulo 3

= ∑_{m=1}^{2s}(−u)^{m−1}∑_{k=0}^{m}(−1)^{3k}\binom{m}{3k} modulo 3.

“Trisection” of the binomial theorem then yields

q_{s}^{(1)}(2u + 1) = \frac{1}{3} ∑_{m=1}^{2s}(−u)^{m−1} ((1 − ω)^{m} + (1 − ω^{2})^{m}) modulo 3,

where ω denotes a primitive third root of unity. Since, for m ≥ 3, we have

\frac{1}{3} ((1 − ω)^{m} + (1 − ω^{2})^{m}) = \frac{1}{3} ((\frac{3−i\sqrt{3}}{2})^{m} + (\frac{3+i\sqrt{3}}{2})^{m}) ≡ 0 (mod 3),

only the summands for m = 1 and m = 2 contribute in the above sum. Thus,

q_{s}^{(1)}(2u + 1) = 1 + 2u modulo 3,

as required. This completes the proof of the lemma. □

Proposition 58. For any positive integer s, we have

∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{2s−1} = \frac{z}{\sqrt{1 + 4z}} (1 + p_{s}^{(2)}(z)) ,  (17.10)

where p_{s}^{(2)}(z) is a polynomial in z with integer coefficients all of which are divisible by 3, and which satisfies p_{s}^{(2)}(0) = 0. An explicit expression for p_{s}^{(2)}(z) can be derived from (17.11) and (17.12).

Proof. The proof is completely analogous to the proof of Proposition 57, so we content ourselves with just stating the crucial identities without proof.

Using the contour integration method, one obtains

∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{2s−1}

= \frac{1}{2πi} ∫_{C} \frac{1 + u}{u^{2} + u − z} ∑_{m=1}^{2s−1} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s−1}) u^{m} du.

Application of the residue theorem then leads to

∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{2s−1}

= \frac{z}{\sqrt{1 + 4z}} ( ∑_{m=1}^{2s−1} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s−1}) u^{m−1})|_{u=− \frac{1}{2} + \frac{1}{2} \sqrt{1+4z}}.

Next one defines

q_{s}^{(2)}(2u + 1) := ∑_{m=1}^{2s−1} (∑_{k=1}^{m}(−1)^{m−k}\binom{m}{k}k^{2s−1}) u^{m−1},  (17.11)

so that

1 + p_{s}^{(2)}(z) = q_{s}^{(2)} (\sqrt{1 + 4z}) .  (17.12)

Now one proves that q_{s}^{(2)}(−2u − 1) = q_{s}^{(2)}(2u + 1) (that is, symmetry of the polynomial q_{s}^{(2)}( .)), establishing that p_{s}^{(2)}(z) is indeed a polynomial in z. By definition, it is obvious that q_{s}^{(2)}(1) = 1, whence p_{s}^{(2)}(0) = 0. Furthermore, using the symmetrisation of q_{s}^{(2)}( .), Identity (17.5), and Relation (17.12), one shows that p_{s}^{(2)}(z) has integer coefficients. In the final step, one proves that all these coefficients are divisible by 3, by demonstrating that

q_{s}^{(2)}(2u + 1) = 1 modulo 3.
□

Theorem 59. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function E^{(1)}(z) = ∑_{n≥0} A(2n, n + 1) z^{n} for central Eulerian numbers with even first index, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z) of the form

E^{(1)}(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{3}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + z.

Proof. By (17.1), we have

A(2n, n + 1) = ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2n}.

In order to analyse this expression modulo 3^{β} (the reader should imagine that β = 3^{α}), we have to distinguish between several cases, depending on the congruence class of n modulo 3^{β−1}. Namely, since φ(3^{β}) = 2 · 3^{β−1} (with φ( .) denoting the Euler totient function), we have

A(2n, n + 1) ≡ ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2s} (mod 3^{β})

for n ≡ s (mod 3^{β−1}) and n, s ≥ \frac{1}{2}(β − 1). (17.13)

(The condition n, s ≥ \frac{1}{2}(β −1) is needed to ensure that j^{2n} ≡ j^{2s} ≡ 0 (mod 3^{β−1}) for all j which are divisible by 3.) From Proposition 57, we know that the generating function for the numbers on the right-hand side of the above congruence, say

E_{s}^{(1)}(z) = ∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2s},

has the form given on the right-hand side of (17.6). Consequently, it satisfies the functional equation

(E_{s}^{(1)})^{2}(z) − (1 + p_{s}^{(1)}(z)) E_{s}^{(1)}(z) − z (1 + p_{s}^{(1)}(z))^{2} = 0.  (17.14)

If we rewrite this in the form

(E_{s}^{(1)})^{2}(z) − E_{s}^{(1)}(z) − z − p_{s}^{(1)}(z)E_{s}^{(1)}(z) − zp_{s}^{(1)}(z) (2 + p_{s}^{(1)}(z)) = 0,

then we see that it fits into the framework of Theorem 17. Indeed, one chooses γ = 1, c_{2}(z) = 1, c_{1}(z) = −1, c_{0}(z) = −z, which implies that

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = 1 + z modulo 3,

so that the constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 0, e_{2} = 0, f_{1} = 0, f_{2} = 0, ε = 1, and we have

Q(…) = −\frac{1}{3}p_{s}^{(1)}(z)E_{s}^{(1)}(z) − \frac{1}{3}zp_{s}^{(1)}(z) (2 + p_{s}^{(1)}(z)) .

This is indeed a polynomial in z and E_{s}^{(1)}(z) with integer coefficients since, by Proposition 57, all coefficients of the polynomial p_{s}^{(1)}(z) are divisible by 3. Consequently, for each s, the generating function E_{s}^{(1)}(z), when reduced modulo 3^{β}, can be written as a polynomial in the basic series Ψ(z).

However, we are actually not interested in all coefficients in E_{s}^{(1)}(z). By (17.13), the relevant coefficients are those of powers z^{n}, where n ≡ s (mod 3^{β−1}). In other words, for each fixed s, we need a particular 3^{β−1}-section of E_{s}^{(1)}(z), and these 3^{β−1}-sections have then to be summed to obtain the series E^{(1)}(z) modulo 3^{β}. To be precise, we have

E^{(1)}(z) = ∑_{s=⌈\frac{1}{2} (β−1)⌉}^{3^{β−1}+⌈\frac{1}{2} (β−1)⌉−1}_{∑_{ℓ∈ℤ} ; s+3^{β−1}ℓ≥0}z^{s+3^{β−1}ℓ} ⟨t^{s+3^{β−1}ℓ}⟩ E_{s}^{(1)}(t) + E(z),

where ⟨t^{m}⟩ f(t) denotes the coefficient of t^{m} in the series f(t), and the polynomial E(z) represents the possible correction which takes care of deviations from the congruence (17.13) for n’s with n < \frac{1}{2}(β − 1). However, computing 3^{β−1}-sections of E_{s}^{(1)}(z) is straightforward, once we observe that

Ψ(z) = Ψ(z^{3^{β−1}}) ∏_{j=0}^{β−2}(1 + z^{3^{j}}).  (17.15)

Each 3^{β−1}-section, with coefficients reduced by 3^{β}, is then a polynomial in Ψ(z^{3^{β−1}}), or, equivalently, if we use (17.15) in the other direction, a polynomial in Ψ(z). Hence, the generating function E^{(1)}(z) of central Eulerian numbers, when coefficients are reduced modulo 3^{β}, can be expressed as a polynomial in Ψ(z), which was exactly our claim. □

How the procedure explained in the above proof works for modulus 9 is described in detail in the proof of the next result.

Theorem 60. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} A(2n, n+1) z^{n} = −1+3(z+1)Ψ(z)+\frac{3z^{4} + 2z^{3} + 6z^{2} + 2}{1 + z}Ψ^{3}(z) modulo 9. (17.16)

Proof. We start by considering the case n ≡ 1 (mod 3). Under this condition, we have

A(2n, n + 1) ≡ ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2} (mod 9).

From Proposition 57, we obtain

E_{1}^{(1)}(z) = ∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{2} = \frac{1}{2} (1 + \sqrt{1 + 4z}) .  (17.17)

Consequently, by applying (17.14) with s = 1 and p_{1}^{(1)}(z) = 0, we see that the series E_{1}^{(1)}(z) satisfies the functional equation

(E_{s}^{(1)})^{2}(z) − E_{s}^{(1)}(z) − z = 0.

If we use the method from Section 4 in the form of Theorem 17, with the relation (4.3) replaced by (2.2), then we obtain

E_{1}^{(1)}(z) = −4 + 3(z + 1)Ψ(z) + (5z^{2} + 7z + 2) Ψ^{3}(z) modulo 9.

In this series, we are only interested in the terms involving powers z^{n} with n ≡ 1 (mod 3). This 3-section of the right-hand side of the above congruence equals

6zΨ(z^{3}) + (4z^{4} + 4z)Ψ^{3}(z^{3}).  (17.18)

In a similar vein, if n ≡ 2 (mod 3), then

A(2n, n + 1) ≡ ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{4} (mod 9).

From Proposition 57, we obtain

E_{2}^{(1)}(z) = ∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{4} = \frac{1}{2} (1 + \sqrt{1 + 4z}) (1 + 12z) (17.19)

Consequently, by applying (17.14) with s = 1 and p_{1}^{(1)}(z) = 12z, we see that the series E_{2}^{(1)}(z) satisfies the functional equation

(E_{s}^{(1)})^{2}(z) − (1 + 12z)E_{s}^{(1)}(z) − z(1 + 12z)^{2} = 0.

The method from Section 4 then yields

E_{2}^{(1)}(z) = −3z − 4 + 3(z + 1)Ψ(z) + (6z^{3} + 8z^{2} + 4z + 2) Ψ^{3}(z) modulo 9.

The relevant part, obtained by extracting only terms involving powers z^{n} with n ≡ 2 (mod 3) is

3z^{2}Ψ(z^{3}) − (z^{5} + z^{2})Ψ^{3}(z^{3}).  (17.20)

Finally, if n ≡ 0 (mod 3), then

A(2n, n + 1) ≡ ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{6} (mod 9).

(Although n = 0 violates the inequality n ≥ \frac{1}{2}(β − 1) = \frac{1}{2} in (17.13), this holds indeed for all n ≥ 0 which are divisible by 3.) From Proposition 57, we obtain

E_{3}^{(1)}(z) = ∑_{n≥0} z^{n} ∑_{j=0}^{n+1}(−1)^{n+1−j}\binom{2n + 1}{n + 1 − j}j^{6} = \frac{1}{2} (1 + \sqrt{1 + 4z}) (1 + 60z + 360z^{2})

(17.21)

Consequently, the series E_{2}^{(1)}(z) satisfies the functional equation

(E_{s}^{(1)})^{2}(z) − (1 + 60z + 360z^{2})E_{s}^{(1)}(z) − z(1 + 60z + 360z^{2})^{2} = 0.

The method from Section 4 then yields

E_{3}^{(1)}(z) = 3z − 4 + 3(z + 1)Ψ(z) + (3z^{3} + 2z^{2} + z + 2) Ψ^{3}(z) modulo 9.

The relevant part, obtained by extracting only terms involving powers z^{n} with n ≡ 0 (mod 3) is

−1 + 3Ψ(z^{3}) + (2 + 5z^{3} + 3z^{6})Ψ^{3}(z^{3}).  (17.22)

Summing the expressions (17.18), (17.20), and (17.22), we arrive at (17.16). □

Applying the same procedure for the modulus 27, now involving an analysis of 9 different cases which have to be combined in the end, one is able to prove the following result.

Theorem 61. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} A(2n, n + 1) z^{n} = 14 + 3 (3z^{2} − 4z + 2) Ψ(z) + (21z^{3} + 20z^{2} + 13z + 23) Ψ^{3}(z)

+ 3 (6z^{4} + 4z^{3} + 3z^{2} + 4) Ψ^{5}(z) modulo 27. (17.23)

These results generalise Theorem 5.17 in [3], which is an easy consequence.

Now we turn to the analogous theorems for the central Eulerian numbers A(2n−1, n).

Theorem 62. Let Ψ(z) be given by (1.1), and let α be some positive integer. Then the generating function E^{(2)}(z) = ∑_{n≥0} A(2n − 1, n) z^{n} for central Eulerian numbers with odd first index, reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Ψ(z) of the form

E^{(2)}(z) = a_{0}(z) + ∑_{i=0}^{2·3^{α}−1} a_{i}(z)Ψ^{i}(z^{3}) modulo 3^{3^{α}},

where the coefficients a_{i}(z), i = 0, 1, …, 2 · 3^{α} − 1, are Laurent polynomials in z and 1 + z.

Proof. By (17.1), we have

A(2n − 1, n) = ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{2n−1}.

Again, in order to analyse this expression modulo 3^{β} (the reader should imagine that β = 3^{α}), we have to distinguish several cases, depending on the congruence class of n modulo 3^{β−1}. Namely, we have

A(2n − 1, n) ≡ ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{2s−1} (mod 3^{β})

for n ≡ s (mod 3^{β−1}). and n, s ≥ \frac{β}{2} . (17.24)

(The condition n, s ≥ \frac{β}{2} is needed to ensure that j^{2n−1} ≡ j^{2s−1} ≡ 0 (mod 3^{β−1}) for all j which are divisible by 3.) From Proposition 58, we know that the generating function for the numbers on the right-hand side of the above congruence, say

E_{s}^{(2)}(z) = ∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{2s−1},

has the form given on the right-hand side of (17.10). Consequently, it satisfies the functional equation

(4z + 1)(E_{s}^{(2)})^{2}(z) − z^{2} (1 + p_{s}^{(2)}(z))^{2} = 0.  (17.25)

If we rewrite this in the form

(1 + z)(E_{s}^{(2)})^{2}(z) − z^{2} + 3(E_{s}^{(2)})^{2}(z) − z^{2}p_{s}^{(2)}(z) (2 + p_{s}^{(2)}(z)) = 0,

then we see that it fits the framework of Theorem 17. Here, one chooses γ = 1, c_{2}(z) = 1 + z, c_{1}(z) = 0, c_{0}(z) = −z^{2}, which implies that

c_{1}^{2}(z) − c_{0}(z)c_{2}(z) = z^{2}(1 + z) modulo 3,

so that the constants e_{1}, e_{2}, f_{1}, f_{2} are given by e_{1} = 0, e_{2} = 1, f_{1} = 1, f_{2} = 0, ε = 1, and we have

Q(…) = (E_{s}^{(2)})^{2}(z) − \frac{1}{3}zp_{s}^{(2)}(z) (2 + p_{s}^{(2)}(z)) .

This is indeed a polynomial in z and E_{s}^{(2)}(z) with integer coefficients since, by Proposition 58, all coefficients of the polynomial p_{s}^{(2)}(z) are divisible by 3. Consequently, for each s, the generating function E_{s}^{(2)}(z), when reduced modulo 3^{β}, can be written as a polynomial in the basic series Ψ(z).

The rest of the argument is identical with corresponding arguments in the proof of Theorem 59. □

For the modulus 9, the procedure explained in the above proof leads to the following result.

Theorem 63. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} A(2n − 1, n) z^{n} = −3zΨ(z) + (6z^{4} + 6z^{3} + 4z^{2} + 4z) Ψ^{3}(z) modulo 9. (17.26)

Proof. As in the proof of Theorem 60, we distinguish three cases, depending on the congruence class of n modulo 3. In order to address the case where n ≡ 1 (mod 3), from Proposition 58 we compute

∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{7} = \frac{z}{\sqrt{1 + 4z}} (1 + 126z + 1680z^{2} + 5040z^{3}). (17.27)

58 C. KRATTENTHALER AND T. W. MÜLLER

Consequently, by applying (17.14) with s = 1 and p_{1}^{(2)}(z) = 1 + 126z + 1680z^{2} + 5040z^{3}, we see that the series E_{2}^{(2)}(z) satisfies the functional equation

(1 + 4z)(E_{s}^{(2)})^{2}(z) − z^{2}(1 + 126z + 1680z^{2} + 5040z^{3})^{2} = 0.

The method from Section 4 in the form of Theorem 17 then yields

E_{1}^{(2)}(z) = −3zΨ(z) + (6z^{4} + 6z^{3} + 7z^{2} + 4z) Ψ^{3}(z) modulo 9,

and the relevant part of it, consisting only of terms involving powers z^{n} with n ≡ 1 (mod 3) is

−3zΨ(z^{3}) + (6z^{7} + 4z^{4} + 4z) Ψ^{3}(z^{3}).  (17.28)

Next, addressing the case where n ≡ 2 (mod 3), we have

∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{3} = \frac{z}{\sqrt{1 + 4z}} (1 + 6z),  (17.29)

so that this series satisfies the functional equation

(1 + 4z)(E_{s}^{(2)})^{2}(z) − z^{2}(1 + 6z)^{2} = 0.

Our algorithm then yields

E_{2}^{(2)}(z) = −3zΨ(z) + (6z^{3} + 4z^{2} + 4z) Ψ^{3}(z) modulo 9,

with the relevant part being

−3z^{2}Ψ(z^{3}) + (22z^{5} + 16z^{2})Ψ^{3}(z^{3}).  (17.30)

Finally, in order to address the case where n ≡ 0 (mod 3), we compute

∑_{n≥0} z^{n} ∑_{j=0}^{n}(−1)^{n−j}\binom{2n}{n − j}j^{5} = \frac{z}{\sqrt{1 + 4z}} (1 + 30z + 120z^{2}),  (17.31)

so that this series satisfies the functional equation

(1 + 4z)(E_{s}^{(2)})^{2}(z) − z^{2}(1 + 30z + 120z^{2})^{2} = 0.

Our algorithm yields

E_{3}^{(2)}(z) = −3zΨ(z) + (3z^{4} + 6z^{3} + z^{2} + 4z) Ψ^{3}(z) modulo 9,

with the relevant part being

(15z^{6} + 21z^{3})Ψ^{3}(z^{3}).  (17.32)

Summation of (17.28), (17.30), and (17.32) then leads to (17.26). □

The same procedure produces the following result for the modulus 27. Theorem 64. Let Ψ(z) be given by (1.1). Then, we have

∑_{n≥0} A(2n − 1, n) z^{n} = −3z (3z^{2} + 5)Ψ(z) + z (24z^{3} + 15z^{2} + 10z + 19) Ψ^{3}(z)

+ 3z (3z^{4} + 6z^{3} + 2z^{2} + 7z + 8) Ψ^{5}(z) modulo 27. (17.33)

These results generalise Theorem 5.16 in [3], which is an easy consequence.

Remark. It is obvious that we could also treat “almost” central Eulerian numbers, such as A(2n, n − 1) or A(2n − 1, n − 1), modulo powers of 3 using the same approach, and this would lead to similar results.

18. Apéry numbers

In [3], Deutsch and Sagan also discuss Apéry numbers (and, in fact, generalised Apéry numbers), and they derive in particular explicit congruences for Apéry numbers modulo 3. The corresponding result, Theorem 5.14 in [3], has a form which seems to suggest that our method from Section 4 should be applicable here as well. It turns out however that this is not the case. As a matter of fact, we are not even able to make our method work for the modulus 3, due to the fact that we were not able to find an equation for the corresponding generating functions which would be suitable for our method.

Let us begin with the Apéry numbers of the first kind, defined by

A_{n}^{(2)} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}.  (18.1)

They are associated with ζ(2), see e.g. [4].

There is a well-known recurrence relation for these numbers. Namely, Apéry computed (and the Gosper–Zeilberger algorithm (cf. [12, Ch. 6]) finds automatically) the recurrence

(n + 2)^{2}A_{n+2}^{(2)} − (11n^{2} + 33n + 25) A_{n+1}^{(2)} − (n + 1)^{2}A_{n}^{(2)} = 0.  (18.2)

This translates into the linear differential equation

(z + 3)A^{(2)}(z) + (3z^{2} + 22z − 1) (A^{(2)})′(z) + (z^{3} + 11z^{2} − z) (A^{(2)})′′(z) = 0 (18.3)

for the generating function A^{(2)}(z) := ∑_{n≥0} A_{n}^{(2)} z^{n}, with initial conditions A^{(2)}(0) = 1 and (A^{(2)})′(0) = 3. Unfortunately, this equation is not suitable for our method, as Equation (18.3) does not determine a unique solution modulo 3 (see the last paragraph in Section 4). Thus, in lack of a different equation, we cannot apply our method.

As it turns out, there is apparently a deeper reason why our method does not apply. By looking at enough data, we have worked out a conjectural description of the Apéry numbers of the first kind modulo 9, see the conjecture below. The patterns describing the various congruence classes do not fit with the patterns which appear in the descriptions of the coefficients of Ψ^{3}(z) modulo 9 which one obtains by carrying out the approach sketched in Section 2 (see in particular the paragraphs after (2.6) and (2.7)), the resulting congruences being explicitly displayed in Corollary 69.

Conjecture 65. The Apéry numbers A_{n}^{(2)} obey the following congruences modulo 9: (i) A_{n}^{(2)} ≡ 1 (mod 9) if, and only if, the 3-adic expansion of n is an element of

{0, 2}^{∗};

(ii) A_{n}^{(2)} ≡ 3 (mod 9) if, and only if, the 3-adic expansion of n has exactly one

occurrence of the string 01 and otherwise contains only 0’s and 2’s; (iii) A_{n}^{(2)} ≡ 6 (mod 9) if, and only if, the 3-adic expansion of n has exactly one

occurrence of the string 21 and otherwise contains only 0’s and 2’s; (iv) in the cases not covered by Items (i)–(iii), A_{n}^{(2)} is divisible by 9; in particular,

A_{n}^{(2)} ≢ 2, 4, 5, 7, 8 (mod 9) for all n.

The Apéry numbers of the second kind are defined by

A_{n}^{(3)} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2}.

They are associated with ζ(3), see e.g. [4].

These numbers satisfy also a well-known recurrence relation which Apéry computed (and the Gosper–Zeilberger algorithm finds automatically), namely

(n + 2)^{3}A_{n+2}^{(3)} − (2n + 3) (17n^{2} + 51n + 39) A_{n+1}^{(3)} + (n + 1)^{3}A_{n}^{(3)} = 0.

This translates into the linear differential equation

(z − 5)A^{(3)}(z) + (7z^{2} − 112z + 1) (A^{(3)})′(z)

+ 3 (2z^{3} − 51z^{2} + z) (A^{(3)})′′(z) + (z^{4} − 34z^{3} + z^{2}) (A^{(3)})′′′(z) = 0 (18.4)

for the generating function A^{(3)}(z) := ∑_{n≥0} A_{n}^{(3)} z^{n}, with initial conditions A^{(3)}(0) = 1 and (A^{(3)})′(0) = 5. Again, this equation is not suitable for our method, for the same reason as before.

Also here we have worked out a conjectural description modulo 9, displaying patterns which do not fit with those appearing in the description of the coefficients of Ψ^{3}(z) modulo 9.

Conjecture 66. The Apéry numbers A_{n}^{(3)} obey the following congruences modulo 9:

(i) A_{n}^{(3)} ≡ 1 (mod 9) if, and only if, the 3-adic expansion of n contains 6k digits 1, for some k, and otherwise only 0’s and 2’s;

(ii) A_{n}^{(3)} ≡ 2 (mod 9) if, and only if, the 3-adic expansion of n contains 6k + 5 digits

1, for some k, and otherwise only 0’s and 2’s; (iii) A_{n}^{(3)} ≡ 4 (mod 9) if, and only if, the 3-adic expansion of n contains 6k + 4 digits

1, for some k, and otherwise only 0’s and 2’s; (iv) A_{n}^{(3)} ≡ 5 (mod 9) if, and only if, the 3-adic expansion of n contains 6k + 1 digits

1, for some k, and otherwise only 0’s and 2’s;

(v) A_{n}^{(3)} ≡ 7 (mod 9) if, and only if, the 3-adic expansion of n contains 6k + 2 digits 1, for some k, and otherwise only 0’s and 2’s;

(vi) A_{n}^{(3)} ≡ 8 (mod 9) if, and only if, the 3-adic expansion of n contains 6k + 3 digits

1, for some k, and otherwise only 0’s and 2’s; (vii) in the cases not covered by Items (i)–(vi), A_{n}^{(3)} is divisible by 9; in particular,

A_{n}^{(3)} ≢ 3, 6 (mod 9) for all n.

Note

Conjectures 65 and 66 have been proven by Rowland and Yassawi [16], and independently by the authors of the present paper [8].

Appendix: Expansions of powers of the Cantor-like power series Ψ(z)

In this section, we indicate how to explicitly extract coefficients from powers of Ψ(z) modulo 3^{e}, where e is a given positive integer. The reader should recall that, by (2.6) and (2.7), it suffices to explain how to extract coefficients from expressions of the form

Ψ(z)\frac{1}{(1 + z)^{K}} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{a_{j}}  (A.1)

and

\frac{1}{(1 + z)^{K}} ∏_{j=1}^{s} (\frac{z^{3^{k_{j}}} (1 + z^{3^{k_{j}}})}{1 + z^{3^{k_{j} +1}}})^{a_{j}} .  (A.2)

We describe below how to deal with (A.1). The coefficient extraction from expressions of the form (A.2) is even simpler since these are rational functions in z.

Rather than providing a general description of how to proceed (which is possible but would be hardly comprehensible), we prefer to work through the special case where s = 2, that is,

Ψ(z)\frac{1}{(1 + z)^{K}} (\frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}})^{a_{1}} (\frac{z^{3^{k_{2}}}(1 + z^{3^{k_{2}}})}{1 + z^{3^{k_{2}+1}}})^{a_{2}} ,  (A.3)

where k_{1} > k_{2} ≥ 0 and a_{1}, a_{2} ≥ 1. We have to distinguish several cases, depending on whether K, k_{1}, k_{2} are “close to each other,” or not.

First let K ≤ k_{2} and k_{2} + a_{2} < k_{1}. In that case, the expression (A.3) can be transformed into

∏_{i=1}^{K−1}(1 − z + z^{2} − ⋯ + z^{3^{i}−1}) ∏_{i=K}^{k_{2}−1}(1 + z^{3^{i}})

× (1 + z^{3^{k_{2}}})(z^{3^{k_{2}}} + z^{2·3^{k_{2}}})^{a_{2}} ∏_{i=k_{2}+2}^{k_{2}+a_{2}}(1 − z^{3^{k_{2}+1}} + z^{2·3^{k_{2}+1}} − ⋯ + z^{3^{i}−3^{k_{2}+1}}) ∏_{i=k_{2}+a_{2}+1}^{k_{1}−1}(1 + z^{3^{i}})

×(1+z^{3^{k_{1}}})(z^{3^{k_{1}}} +z^{2·3^{k_{1}}})^{a_{1}} ∏_{i=k_{1}+2}^{k_{1}+a_{1}}(1−z^{3^{k_{1}+1}} +z^{2·3^{k_{1}+1}} −⋯+z^{3^{i}−3^{k_{1}+1}}) ∏_{i=k_{1}+a_{1}+1}^{∞}(1+z^{3^{i}}).

We write this as

P_{0}(z) ( ∏_{i=K}^{k_{2}−1}(1 + z^{3^{i}})) P_{1}(z) ( ∏_{i=k_{2}+a_{2}+1}^{k_{1}−1}(1 + z^{3^{i}})) P_{2}(z) ( ∏_{i=k_{1}+a_{1}+1}^{∞}(1 + z^{3^{i}})) , (A.4)

which implicitly defines the polynomials P_{0}(z), P_{1}(z), and P_{2}(z). It should be noted that P_{0}(z) has degree at most 3^{K}, P_{1}(z) has order a_{2}3^{k_{2}} and degree at most 3^{k_{2}+a_{2}}, and P_{2}(z) has order a_{1}3^{k_{1}} and degree at most 3^{k_{1}+a_{1}}. We “organise” the polynomials P_{0}(z), P_{1}(z), P_{2}(z) in the form

P_{0}(z) = ∑_{γ∈ℤ} γ ∑_{(n)_{3}∈Z_{γ}} z^{n},

P_{1}(z) = ∑_{β∈ℤ} β ∑_{(n)_{3}∈Y_{β}0^{k_{2}}} z^{n},

P_{2}(z) = ∑_{α∈ℤ} α ∑_{(n)_{3}∈X_{α}0^{k_{1}}} z^{n},

where (n)_{3} denotes the 3-adic representation of the integer n, considered as a string of 0’s, 1’s, and 2’s, Z_{γ} is an appropriate set of strings contained in {0, 1, 2}^{K}, Y_{β} is an appropriate set of strings contained in {0, 1, 2}^{a_{2}+1}, and X_{α} is an appropriate set of strings contained in {0, 1, 2}^{a_{1}+1}. Inspection of (A.4) makes it now obvious that the coefficients c_{n} in the series ∑_{n≥0} c_{n}z^{n} given by (A.3) can be described in the form

c_{n} = C if, and and only if,

(n)_{3} ∈ ⋃_{α·β·γ=C} ( ⋃_{X∈X_{α}, Y ∈Y_{β}, Z∈Z_{γ}}{0, 1}^{∗}X{0, 1}^{k_{1}−k_{2}−a_{2}−1}Y {0, 1}^{k_{2}−K}Z),

where we used again the word notation explained before Theorem 52.

Next let K > k_{2} ≥ 0 (“k_{2} is close to K”) and K +a_{2} ≤ k_{1}. In this case, the expression (A.3) can be transformed into

∏_{i=1}^{K−1}(1 − z + z^{2} − ⋯ + z^{3^{i}−1})

× (z^{3^{k_{2}}} + z^{2·3^{k_{2}}})^{a_{2}} ∏_{i=K}^{K+a_{2}−1}(1 − z^{3^{k_{2}+1}} + z^{2·3^{k_{2}+1}} − ⋯ + z^{3^{i}−3^{k_{2}+1}}) ∏_{i=K+a_{2}}^{k_{1}−1}(1 + z^{3^{i}})

×(1+z^{3^{k_{1}}})(z^{3^{k_{1}}} +z^{2·3^{k_{1}}})^{a_{1}} ∏_{i=k_{1}+2}^{k_{1}+a_{1}}(1−z^{3^{k_{1}+1}} +z^{2·3^{k_{1}+1}} −⋯+z^{3^{i}−3^{k_{1}+1}}) ∏_{i=k_{1}+a_{1}+1}^{∞}(1+z^{3^{i}}).

Here, we write this as

P_{1}(z) ( ∏_{i=K+a_{2}}^{k_{1}−1}(1 + z^{3^{i}})) P_{2}(z) ( ∏_{i=k_{1}+a_{1}+1}^{∞}(1 + z^{3^{i}})) ,  (A.5)

which implicitly defines the polynomials P_{1}(z) and P_{2}(z). By going through the same reasoning as before, one comes to the conclusion that in the present case the coefficients c_{n} in the series ∑_{n≥0} c_{n}z^{n} given by (A.3) can be described in the form

c_{n} = C if, and and only if, (n)_{3} ∈ ⋃_{α·β=C} ( ⋃_{X∈X_{α}, Y ∈Y_{β}}{0, 1}^{∗}X{0, 1}^{k_{1}−a_{2}−K}Y ),

for appropriate sets of strings X_{α} and Y_{β}.

The other cases to be discussed are the case where K ≤ k_{2} and k_{2} + a_{2} ≥ k_{1} (“k_{1} is close to k_{2}”; we always assume k_{2} < k_{1}), and the case where K ≥ k_{1} > k_{2} ≥ 0 (“K, k_{1}, k_{2} are all close to each other”). Both of them can be treated in a similar fashion.

We illustrate the above procedure by making explicit how to extract coefficients from odd powers of Ψ(z) modulo 27. By Lemma 1, we have

Ψ^{3}(z) = \frac{1}{1 + z} Ψ(z)(1 + 3 ∑_{k_{1}≥0} \frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} + 9 ∑_{k_{1}>k_{2}≥0} \frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})})

modulo 27. (A.6)

The following lemma provides the means for coefficient extraction from Ψ^{3}(z) modulo any power of 3.

Lemma 67. (1) If k_{1} = 0, we have

\frac{1}{1 + z} Ψ(z)\frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} = Ψ(z)\frac{z}{1 + z^{3}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{01,02\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

while, if k_{1} ≥ 1, we have

\frac{1}{1 + z} Ψ(z)\frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−1}0, \\ 2, & if (n)_{3} ∈ \{0, 1\}^{∗}02\{0, 1\}^{k_{1}−1}0, \\ 0, & otherwise. \end{cases}

(2) If k_{2} = 0, we have

\frac{1}{1 + z} Ψ(z)\frac{z^{3^{k_{2}+1}+3^{k_{2}}}(1 + z^{3^{k_{2}}})}{1 + z^{3^{k_{2}+2}}} = Ψ(z)\frac{z^{4}}{1 + z^{9}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{011,012,021,022\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

while, if k_{2} ≥ 1, we have

\frac{1}{1 + z} Ψ(z)\frac{z^{3^{k_{2}+1}+3^{k_{2}}}(1 + z^{3^{k_{2}}})}{1 + z^{3^{k_{2}+2}}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{011,020,021,100\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{2}−1}0, \\ 2, & if (n)_{3} ∈ ⋃_{X∈\{012,022\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{2}−1}0, \\ 0, & otherwise. \end{cases}

(3) If k_{1} − 1 > k_{2} = 0, we have

\frac{1}{1 + z} Ψ(z)\frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})} = Ψ(z)\frac{z^{3^{k_{1}}+1}(1 + z^{3^{k_{1}}})}{(1 + z^{3})(1 + z^{3^{k_{1}+1}})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}, Y ∈\{01,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}Y, \\ 2, & if (n)_{3} ∈ ⋃_{X∈\{01,02\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−2}X, \\ 0, & otherwise, \end{cases}

while, if k_{1} − 1 > k_{2} ≥ 1, we have

\frac{1}{1 + z} Ψ(z)\frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X,Y ∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−k_{2}−2}Y \{0, 1\}^{k_{2}−1}0, \\ 2, & if (n)_{3} ∈ ( ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−k_{2}−2}X\{0, 1\}^{k_{2}−1}0) \\ & ∪( ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−k_{2}−2}02\{0, 1\}^{k_{2}−1}0), \\ 4, & if (n)_{3} ∈ \{0, 1\}^{∗}02\{0, 1\}^{k_{1}−k_{2}−2}02\{0, 1\}^{k_{2}−1}0, \\ 0, & otherwise. \end{cases}

For convenience, given a (left-infinite) string s = … s_{2}s_{1}s_{0} consisting of 0’s, 1’s, and 2’s, we introduce the following notation:

#1str(s) = #(maximal strings of 1’s in s),
#iso_{2}(s) = #(isolated 0’s and 1’s in s, excluding s_{0} and s_{1}),
#iso_{3}(s) = #(isolated 0’s and 1’s in s, excluding s_{0}, s_{1}, s_{2}),
end(s; e) = \begin{cases}1 & if s ends with the string e, \\ 0 & otherwise, \end{cases}
#100_{1}(s) = #(occurrences of the substring 100 in s not involving s_{0}),
#011(s) = #(occurrences of the substring 011 in s),

and similarly for #020(s), #021(s), #102(s), #10(s), #01(s).

Proposition 68. Let s denote the 3-adic expansion of the non-negative integer n. The coefficient of z^{n} in the series Ψ^{3}(z), when reduced modulo 27, equals

(1) 1, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{2 #1str(s)−1}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 0 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{2 #1str(s)}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 0 (mod 3);

(2) 4, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 0 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{2 #1str(s)−1}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 0 (mod 3);

(3) 7, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{2 #1str(s)−3}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 2 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 2 (mod 3);

(4) 10, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{2 #1str(s)−1}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 1 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{2 #1str(s)}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 1 (mod 3);

(5) 13, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 1 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{2 #1str(s)−1}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 1 (mod 3);

(6) 16, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{2 #1str(s)−3}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 0 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 0 (mod 3);

(7) 19, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{2 #1str(s)−1}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 2 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{2 #1str(s)}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 2 (mod 3);

(8) 22, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 2 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{2 #1str(s)−1}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 2 (mod 3);

(9) 25, if, and only if, s is either an element of {0, 1}^{∗}10 and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{2 #1str(s)−3}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 1 (mod 3),

or of {0, 1}^{∗}00 and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{2 #1str(s)−2}{3} − #iso_{2}(s) + #011(s) + #100_{1}(s) ≡ 1 (mod 3);

(10) 9, if, and only if, the 3-adic expansion of n is an element of

({0, 1}^{∗}02{0, 1}^{∗}02{0, 1}^{∗}0) ∪ ( ⋃_{X∈{011,012,021,022}}{0, 1}^{∗}X);

(11) 18, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{X∈{01,02}}{0, 1}^{∗}02{0, 1}^{∗}X) ∪ ( ⋃_{X∈{012,022}}{0, 1}^{∗}X{0, 1}^{∗}0);

(12) 3, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{01,02}} (11^{∗}00^{∗})^{3k+1}11^{∗}X) ∪ ( ⋃_{k≥0, X∈{01,02}} (11^{∗}00^{∗})^{3k+2}11^{∗}0^{∗}0X) ∪ {1, 2};

(13) 12, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{01,02}} (11^{∗}00^{∗})^{3k}11^{∗}X) ∪ ( ⋃_{k≥0, X∈{01,02}} (11^{∗}00^{∗})^{3k+1}11^{∗}0^{∗}0X);

(14) 21, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{01,02}} (11^{∗}00^{∗})^{3k+2}11^{∗}X) ∪ ( ⋃_{k≥0, X∈{01,02}} (11^{∗}00^{∗})^{3k}11^{∗}0^{∗}0X);

(15) 6, if, and only if, s is either an element of {0, 1}^{∗}02{0, 1}^{∗}00 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) ≡ 0 (mod 3),

or an element of {0, 1}^{∗}02{0, 1}^{∗}10 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) ≡ 2 (mod 3),

or an element of {0, 1}^{∗}020 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) − 1 ≡ 0 (mod 3);

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 67

(16) 15, if, and only if, s is either an element of {0, 1}^{∗}02{0, 1}^{∗}00 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) ≡ 1 (mod 3), or an element of {0, 1}^{∗}02{0, 1}^{∗}10 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) ≡ 0 (mod 3), or an element of {0, 1}^{∗}020 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) − 1 ≡ 1 (mod 3);

(17) 24, if, and only if, s is either an element of {0, 1}^{∗}02{0, 1}^{∗}00 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) ≡ 2 (mod 3), or an element of {0, 1}^{∗}02{0, 1}^{∗}10 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) ≡ 1 (mod 3), or an element of {0, 1}^{∗}020 and satisfies

#020(s) + #021(s) + #102(s) − #01(s) − #10(s) − 1 ≡ 2 (mod 3);

(18) In all other cases, this coefficient is divisible by 27. In particular, it is never congruent to 2 modulo 3.

If the above proposition is specialised to modulus 9, then one obtains the following result. Corollary 69. The coefficient of z^{n} in the series Ψ^{3}(z), when reduced modulo 9, equals

(1) 1, if, and only if, the 3-adic expansion of n is an element of

{0} ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}0 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k}0^{∗}00;

(2) 4, if, and only if, the 3-adic expansion of n is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}0 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}0^{∗}00;

(3) 7, if, and only if, the 3-adic expansion of n is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k+3}0 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}0^{∗}00;

(4) 3, if, and only if, the 3-adic expansion of n is an element of {0, 1}^{∗}01 ∪ {0, 1}^{∗}02,

(5) 6, if, and only if, the 3-adic expansion of n is an element of {0, 1}^{∗}02{0, 1}^{∗}0.

(6) In all other cases, this coefficient is divisible by 9. In particular, it is never congruent to 2 modulo 3.

Now we turn our attention to coefficient extraction from Ψ^{5}(z) modulo 27. By Lemma 1, we have

Ψ^{5}(z) = \frac{1}{(1 + z)^{2}} Ψ(z)(1+6 ∑_{k_{1}≥0} \frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} +9 ∑_{k_{1}>k_{2}≥0} \frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})}

+ 9 ∑_{k_{1}≥0} \frac{z^{2·3^{k_{1}}}(1 + z^{3^{k_{1}}})^{2}}{(1 + z^{3^{k_{1}+1}})^{2}} ) modulo 27. (A.7)

The following lemma provides the means for coefficient extraction from Ψ^{5}(z) modulo any power of 3.

Lemma 70. (1) We have

\frac{1}{(1 + z)^{2}} Ψ(z) = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{00,02\}}\{0, 1\}^{∗}X, \\ −1, & if (n)_{3} ∈ \{0, 1\}^{∗}01, \\ 0, & otherwise. \end{cases}

(2) If k_{1} = 0, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} = Ψ(z)\frac{z}{(1 + z)(1 + z^{3})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ \{0, 1\}^{∗}01, \\ 0, & otherwise, \end{cases}

if k_{1} = 1, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} = Ψ(z)\frac{z(1 − z + z^{2})}{(1 + z)(1 + z^{9})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{010,012,020,022\}}\{0, 1\}^{∗}X, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{011,021\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

while, if k_{1} ≥ 2, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{1}}}(1 + z^{3^{k_{1}}})}{1 + z^{3^{k_{1}+1}}} = ∑_{n≥0} c_{n}z^{n},

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 69

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}Y, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}01, \\ 2, & if (n)_{3} ∈ ⋃_{X∈\{00,02\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−2}X, \\ −2, & if (n)_{3} ∈ \{0, 1\}^{∗}02\{0, 1\}^{k_{1}−2}01, \\ 0, & otherwise. \end{cases}

(3) If k_{2} = 0, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{2}+1}+3^{k_{2}}}(1 + z^{3^{k_{2}}})}{1 + z^{3^{k_{2}+2}}} = Ψ(z)\frac{z^{4}}{(1 + z)(1 + z^{9})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{011,021\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

if k_{2} = 1, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{2}+1}+3^{k_{2}}}(1 + z^{3^{k_{2}}})}{1 + z^{3^{k_{2}+2}}} = Ψ(z)\frac{z^{12}(1 − z + z^{2})}{(1 + z)(1 + z^{27})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{0110,0112,0120,0122,0210,0212,0220,0222\}}\{0, 1\}^{∗}X, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{0111,0121,0211,0221\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

while, if k_{2} ≥ 2, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{2}+1}+3^{k_{2}}}(1 + z^{3^{k_{2}}})}{1 + z^{3^{k_{2}+2}}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{011,020,021,100\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{2}−2}Y, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{011,020,021,100\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{2}−2}01, \\ 2, & if (n)_{3} ∈ ⋃_{X∈\{012,022\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{2}−2}Y, \\ −2, & if (n)_{3} ∈ ⋃_{X∈\{012,022\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{2}−2}01, \\ 0, & otherwise. \end{cases}

(4) If k_{1} − 1 > k_{2} = 0, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})}

= Ψ(z)\frac{z^{3^{k_{1}}+1}(1 + z^{3^{k_{1}}})}{(1 + z)(1 + z^{3})(1 + z^{3^{k_{1}+1}})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}01, \\ 2, & if (n)_{3} ∈ \{0, 1\}^{∗}02\{0, 1\}^{k_{1}−2}01, \\ 0, & otherwise, \end{cases}

if k_{1} − 1 > k_{2} = 1, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})}

= Ψ(z)\frac{z^{3^{k_{1}}+3}(1 − z + z^{2})(1 + z^{3^{k_{1}}})}{(1 + z)(1 + z^{9})(1 + z^{3^{k_{1}+1}})} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}, Y ∈\{010,012,020,022\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−3}Y, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{01,10\}, Y ∈\{011,021\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−3}Y, \\ 2, & if (n)_{3} ∈ ⋃_{X∈\{010,012,020,022\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−3}X, \\ −2, & if (n)_{3} ∈ ⋃_{X∈\{011,021\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−3}X, \\ 0, & otherwise, \end{cases}

while, if k_{1} − 1 > k_{2} ≥ 2, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{3^{k_{1}}+3^{k_{2}}}(1 + z^{3^{k_{1}}})(1 + z^{3^{k_{2}}})}{(1 + z^{3^{k_{1}+1}})(1 + z^{3^{k_{2}+1}})} = ∑_{n≥0} c_{n}z^{n},

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X,Y ∈\{01,10\}, Z∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−k_{2}−2}Y \{0, 1\}^{k_{2}−2}Z, \\ −1, & if (n)_{3} ∈ ⋃_{X,Y ∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−k_{2}−2}Y \{0, 1\}^{k_{2}−2}01, \\ 2, & if (n)_{3} ∈ (  ⋃_{X∈\{01,10\}, Y ∈\{00,02\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−k_{2}−2}X\{0, 1\}^{k_{2}−2}Y ) \\ & ∪(  ⋃_{X∈\{01,10\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−k_{2}−2}02\{0, 1\}^{k_{2}−2}Y ), \\ −2, & if (n)_{3} ∈ ( ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−k_{2}−2}X\{0, 1\}^{k_{2}−2}01) \\ & ∪( ⋃_{X∈\{01,10\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−k_{2}−2}02\{0, 1\}^{k_{2}−2}01), \\ 4, & if (n)_{3} ∈ ⋃_{X∈\{00,02\}}\{0, 1\}^{∗}02\{0, 1\}^{k_{1}−k_{2}−2}02\{0, 1\}^{k_{2}−2}X, \\ −4, & if (n)_{3} ∈ \{0, 1\}^{∗}02\{0, 1\}^{k_{1}−k_{2}−2}02\{0, 1\}^{k_{2}−2}01, \\ 0, & otherwise. \end{cases}

(5) If k_{1} = 0, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{2·3^{k_{1}}}(1 + z^{3^{k_{1}}})^{2}}{(1 + z^{3^{k_{1}+1}})^{2}} = Ψ(z)\frac{z^{2}}{(1 + z^{3})^{2}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{002,010,022,100\}}\{0, 1\}^{∗}X, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{012,020\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

if k_{1} = 1, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{2·3^{k_{1}}}(1 + z^{3^{k_{1}}})^{2}}{(1 + z^{3^{k_{1}+1}})^{2}} = Ψ(z)\frac{z^{6}(1 − z + z^{2})(1 + z^{3})}{(1 + z)(1 + z^{9})^{2}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{0020,0022,0110,0112,0121,0211,0220,0222,1010,1012\}}\{0, 1\}^{∗}X, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{0021,0111,0120,0122,0210,0212,0221,1011\}}\{0, 1\}^{∗}X, \\ 2, & if (n)_{3} ∈ ⋃_{X∈\{0100,0102,0201,1000,1002\}}\{0, 1\}^{∗}X, \\ −2, & if (n)_{3} ∈ ⋃_{X∈\{0101,0200,0202,1001\}}\{0, 1\}^{∗}X, \\ 0, & otherwise, \end{cases}

while, if k_{1} ≥ 2, we have

\frac{1}{(1 + z)^{2}} Ψ(z)\frac{z^{2·3^{k_{1}}}(1 + z^{3^{k_{1}}})^{2}}{(1 + z^{3^{k_{1}+1}})^{2}} = ∑_{n≥0} c_{n}z^{n},

where

c_{n} = \begin{cases}1, & if (n)_{3} ∈ ⋃_{X∈\{002,102\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}Y, \\ −1, & if (n)_{3} ∈ ⋃_{X∈\{002,102\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}01, \\ 3, & if (n)_{3} ∈ ⋃_{X∈\{010,011,100,101\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}Y \\ & ∪ ⋃_{X∈\{020,021\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}01, \\ −3, & if (n)_{3} ∈ ⋃_{X∈\{010,011,100,101\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}01 \\ & ∪  ⋃_{X∈\{020,021\}, Y ∈\{00,02\}}\{0, 1\}^{∗}X\{0, 1\}^{k_{1}−2}Y, \\ 0, & otherwise. \end{cases}

Proposition 71. Let s denote the 3-adic expansion of the non-negative integer n. The coefficient of z^{n} in the series Ψ^{5}(z), when reduced modulo 27, equals

(1) 1, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{4 #1str(s)}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 0 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 2 (mod 3) and \frac{4 #1str(s)−2}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 100) + 2 end(s; 0102) ≡ 0 (mod 3);

(2) 10, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 0 (mod 3) and \frac{4 #1str(s)}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 1 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{4 #1str(s)−2}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 100) + 2 end(s; 0102) ≡ 1 (mod 3);

(3) 19, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{4 #1str(s)}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 2 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{4 #1str(s)−2}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 100) + 2 end(s; 0102) ≡ 2 (mod 3);

(4) 4, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{4 #1str(s)−1}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 0 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{4 #1str(s)−3}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 100) + 2 end(s; 0102) ≡ 0 (mod 3);

(5) 13, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{4 #1str(s)−1}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 1 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{4 #1str(s)−3}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 100) + 2 end(s; 0102) ≡ 1 (mod 3);

(6) 22, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 1 (mod 3) and

\frac{4 #1str(s)−1}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s) + end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 2 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 0 (mod 3) and

\frac{4 #1str(s)−3}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

74 C. KRATTENTHALER AND T. W. MÜLLER

+ end(s; 100) + 2 end(s; 0102) ≡ 2 (mod 3);

(7) 7, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{4 #1str(s)−2}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 0 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 1 (mod 3) and \frac{4 #1str(s)−4}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 100) + 2 end(s; 0102) ≡ 0 (mod 3);

(8) 16, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{4 #1str(s)−2}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 1 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 1 (mod 3) and \frac{4 #1str(s)−4}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 100) + 2 end(s; 0102) ≡ 1 (mod 3);

(9) 25, if, and only if, s is either an element of ⋃_{X∈{000,002}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 2 (mod 3) and

\frac{4 #1str(s)−2}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 002) + end(s; 1000) + end(s; 1002) ≡ 2 (mod 3),

or of ⋃_{X∈{100,102}}{0, 1}^{∗}X and satisfies #1str(s) ≡ 1 (mod 3) and \frac{4 #1str(s)−4}{3} − #iso_{3}(s) + #011(s) + #100_{1}(s)

+ end(s; 100) + 2 end(s; 0102) ≡ 2 (mod 3);

(10) 2, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 1 (mod 3) and \frac{1−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 2 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 0 (mod 3) and \frac{3−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 2 (mod 3);

(11) 11, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 1 (mod 3) and \frac{1−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 0 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 0 (mod 3) and \frac{3−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 0 (mod 3);

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 75

(12) 20, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 1 (mod 3) and \frac{1−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 1 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 0 (mod 3) and \frac{3−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 1 (mod 3);

(13) 5, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 0 (mod 3) and −\frac{4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 2 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 2 (mod 3) and \frac{2−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 2 (mod 3);

(14) 14, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 0 (mod 3) and −\frac{4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 0 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 2 (mod 3) and \frac{2−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 0 (mod 3);

(15) 23, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 0 (mod 3) and −\frac{4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 1 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 2 (mod 3) and \frac{2−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 1 (mod 3);

(16) 8, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 2 (mod 3) and −\frac{1+4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 2 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 1 (mod 3) and \frac{1−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 2 (mod 3);

(17) 17, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 2 (mod 3) and −\frac{1+4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 0 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 1 (mod 3) and \frac{1−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 0 (mod 3);

(18) 26, if, and only if, s is either an element of {0, 1}^{∗}001 and satisfies #1str(s) ≡ 2 (mod 3) and −\frac{1+4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − end(s; 1001) ≡ 1 (mod 3), or of {0, 1}^{∗}101 and satisfies #1str(s) ≡ 1 (mod 3) and \frac{1−4 #1str(s)}{3} + #iso_{3}(s) − #011(s) − #100_{1}(s) − 2 end(s; 1001) ≡ 1 (mod 3);

76 C. KRATTENTHALER AND T. W. MÜLLER

(19) 9, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{X∈{0111,0121,0211,0221}}{0, 1}^{∗}X) ∪ ( ⋃_{X∈{012,022}}{0, 1}^{∗}X{0, 1}^{∗}01)

∪ ( ⋃_{X∈{011,021}}{0, 1}^{∗}02{0, 1}^{∗}X) ∪ ( ⋃_{X∈{00,02}}{0, 1}^{∗}02{0, 1}^{∗}02{0, 1}^{∗}X);

(20) 18, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{X∈{0110,0112,0220,0222}}{0, 1}^{∗}X) ∪ ( ⋃_{X∈{012,022}, Y ∈{00,02}}{0, 1}^{∗}X{0, 1}^{∗}Y )

∪ ( ⋃_{X∈{010,012,020,022}}{0, 1}^{∗}02{0, 1}^{∗}X) ∪ ({0, 1}^{∗}02{0, 1}^{∗}02{0, 1}^{∗}01);

(21) 6, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0} (11^{∗}00^{∗})^{3k+2}0201) ∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3)} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), k_{2}>0} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), k_{2}>0} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3)} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3)} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ((11^{∗}00^{∗})^{3k+1}010) ∪ ((11^{∗}00^{∗})^{3k+2}012)

∪ ((11^{∗}00^{∗})^{3k}020) ∪ ((11^{∗}00^{∗})^{3k+2}022)

∪ ((11^{∗}00^{∗})^{3k}11^{∗}010) ∪ ((11^{∗}00^{∗})^{3k+1}11^{∗}012) ∪ ((11^{∗}00^{∗})^{3k}11^{∗}020) ∪ ((11^{∗}00^{∗})^{3k+2}11^{∗}022);

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 77

(22) 15, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0} (11^{∗}00^{∗})^{3k+1}0201) ∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3)} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), k_{2}>0} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), k_{2}>0} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3)} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3)} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ((11^{∗}00^{∗})^{3k}010) ∪ ((11^{∗}00^{∗})^{3k+1}012)

∪ ((11^{∗}00^{∗})^{3k+2}020) ∪ ((11^{∗}00^{∗})^{3k+1}022)

∪ ((11^{∗}00^{∗})^{3k+2}11^{∗}010) ∪ ((11^{∗}00^{∗})^{3k}11^{∗}012)

∪ ((11^{∗}00^{∗})^{3k+2}11^{∗}020) ∪ ((11^{∗}00^{∗})^{3k+1}11^{∗}022);

(23) 24, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0} (11^{∗}00^{∗})^{3k}0201) ∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3)} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), k_{2}>0} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), k_{2}>0} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}01)

78 C. KRATTENTHALER AND T. W. MÜLLER

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3)} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3)} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3)} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ((11^{∗}00^{∗})^{3k+2}010) ∪ ((11^{∗}00^{∗})^{3k}012) ∪ ((11^{∗}00^{∗})^{3k+1}020) ∪ ((11^{∗}00^{∗})^{3k}022)

∪ ((11^{∗}00^{∗})^{3k+1}11^{∗}010) ∪ ((11^{∗}00^{∗})^{3k+2}11^{∗}012)

∪ ((11^{∗}00^{∗})^{3k+1}11^{∗}020) ∪ ((11^{∗}00^{∗})^{3k}11^{∗}022);

(24) 3, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{00,02}} (11^{∗}00^{∗})^{3k+1}02X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 79

∪ ((11^{∗}00^{∗})^{3k+1}011) ∪ ((11^{∗}00^{∗})^{3k+2}021)

∪ ((11^{∗}00^{∗})^{3k}11^{∗}011) ∪ ((11^{∗}00^{∗})^{3k+2}11^{∗}021);

(25) 12, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{00,02}} (11^{∗}00^{∗})^{3k+2}02X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ((11^{∗}00^{∗})^{3k+2}011) ∪ ((11^{∗}00^{∗})^{3k}021)

∪ ((11^{∗}00^{∗})^{3k+1}11^{∗}011) ∪ ((11^{∗}00^{∗})^{3k}11^{∗}021);

(26) 21, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{00,02}} (11^{∗}00^{∗})^{3k}02X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

80 C. KRATTENTHALER AND T. W. MÜLLER

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡1 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡2 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1}+k_{2}≡0 (mod 3), X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ((11^{∗}00^{∗})^{3k}011) ∪ ((11^{∗}00^{∗})^{3k+1}021)

∪ ((11^{∗}00^{∗})^{3k+2}11^{∗}011) ∪ ((11^{∗}00^{∗})^{3k+1}11^{∗}021).

(27) In all other cases, this coefficient is divisible by 27. If the above proposition is specialised to modulus 9, then one obtains the following

result. Corollary 72. Let s denote the 3-adic expansion of the non-negative integer n. The coefficient of z^{n} in the series Ψ^{5}(z), when reduced modulo 9, equals

(1) 1, if, and only if, s is an element of

{0} ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k}000 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k}002

∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}00 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}02;

(2) 4, if, and only if, s is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}000 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}002 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+3}00 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+3}02;

(3) 7, if, and only if, s is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}000 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}002 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}00 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}02;

(4) 2, if, and only if, s is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}001 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+3}01;

MOD-3^{k} BEHAVIOUR OF RECURSIVE SEQUENCES 81

(5) 5, if, and only if, s is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k}001 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}01;

(6) 8, if, and only if, s is an element of

⋃_{k≥0} (00^{∗}11^{∗})^{3k+2}001 ∪ ⋃_{k≥0} (00^{∗}11^{∗})^{3k+1}01;

(7) 6, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0} (11^{∗}00^{∗})^{k}0201) ∪ ( ⋃_{k_{1},k_{2}≥0} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1},k_{2}≥0} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}≥0, k_{2}>0} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1}≥0, k_{2}>0} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}01)

∪ ( ⋃_{k_{1},k_{2}≥0} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1},k_{2}≥0} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1},k_{2}≥0} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ( ⋃_{k_{1},k_{2}≥0} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}01)

∪ ((11^{∗}00^{∗})^{k}010) ∪ ((11^{∗}00^{∗})^{k}012) ∪ ((11^{∗}00^{∗})^{k}020) ∪ ((11^{∗}00^{∗})^{k}022)

∪ ((11^{∗}00^{∗})^{k}11^{∗}010) ∪ ((11^{∗}00^{∗})^{k}11^{∗}012)

∪ ((11^{∗}00^{∗})^{k}11^{∗}020) ∪ ((11^{∗}00^{∗})^{k}11^{∗}022);

(8) 3, if, and only if, the 3-adic expansion of n is an element of

( ⋃_{k≥0, X∈{00,02}} (11^{∗}00^{∗})^{k}02X)

∪ ( ⋃_{k_{1},k_{2}≥0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1},k_{2}≥0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1},k_{2}≥0, k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1},k_{2}≥0, k_{2}>0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}X)

∪ ( ⋃_{k_{1},k_{2}≥0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1},k_{2}≥0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}0200^{∗}(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1},k_{2}≥0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ( ⋃_{k_{1},k_{2}≥0, X∈{00,02}} (11^{∗}00^{∗})^{k_{1}}11^{∗}02(11^{∗}00^{∗})^{k_{2}}11^{∗}X)

∪ ((11^{∗}00^{∗})^{k}011) ∪ ((11^{∗}00^{∗})^{k}021) ∪ ((11^{∗}00^{∗})^{k}11^{∗}011) ∪ ((11^{∗}00^{∗})^{k}11^{∗}021);

(9) In all other cases, this coefficient is divisible by 9.

References

[1] F. Bergeron and C. Reutenauer, Combinatorial resolution of systems of differential equations III: a special class of differentially algebraic series, Europ. J. Combin. 11 (1990), 501–512.

[2] K. S. Davis and W. A. Webb, Lucas’ theorem for prime powers, Europ. J. Combin. 11 (1990), 229–233.

[3] E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215.

[4] S. Fischler, Irrationalité de valeurs de zêta (d’après Apéry, Rivoal, ...), Séminaire Bourbaki 2002– 2003, exposé no. 910, Astérisque 294 (2004), 27–62.

[5] A. Granville, Arithmetic properties of binomial coefficients, I: Binomial coefficients modulo prime powers, in: Organic mathematics (Burnaby, BC, 1995), CMS Conf. Proc., vol. 20, Amer. Math. Soc., Providence, RI, 1997, pp. 253–276.

[6] Q.-H. Hou, Comment on paper P37 of volume 18(2), Electron. J. Combin., 2012.

[7] M. Kauers, C. Krattenthaler and T. W. Müller, A method for determining the mod-2^{k} behaviour of recursive sequences, with applications to subgroup counting, Electron. J. Combin. 18(2) (2012), Article P37, 83 pp.

[8] C. Krattenthaler and T. W. Müller, Generalised Apéry numbers modulo 9, preprint; arχiv:??.

[9] A. M. Legendre, Essai sur la théorie des nombres, 2ed., Courcier, Paris, 1808.

[10] T. W. Müller, Parity patterns in Hecke groups and Fermat primes. In: Groups: Topological, Combinatorial, and Arithmetic Aspects, Proceedings of a conference held 1999 in Bielefeld (T. W. Müller, ed.), LMS Lecture Note Series vol. 311, Cambridge University Press, Cambridge, 2004, 327–374.

[11] T. W. Müller and J.-C. Schlage-Puchta, Divisibility properties of subgroup numbers for the modular group, New York J. Math. 11 (2005), 205–224.

[12] M. Petkovšek, H. Wilf and D. Zeilberger, A=B, A. K. Peters, Wellesley, 1996.

[13] T. J. Rivlin, Chebyshev polynomials, 2nd edition, John Wiley & Sons, New York, 1990.

[14] G.-C. Rota, D. Kahaner, and A. Odlyzko, On the foundations of combinatorial theory, VIII: Finite operator calculus, J. Math. Anal. Appl. 42 (1973), 684–760.

[15] L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

[16] E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, J. Théorie Nombres Bordeaux 27 (2015), 245–288.

[17] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998.

[18] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

†∗Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090

Vienna, Austria. WWW: http://www.mat.univie.ac.at/~kratt.

∗School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.