A METHOD FOR DETERMINING THE MOD-p^{k} BEHAVIOUR OF RECURSIVE SEQUENCES

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

Abstract. We present a method for obtaining congruences modulo powers of a prime number p for combinatorial sequences whose generating function satisfies an algebraic differential equation. This method generalises the one by Kauers and the authors [Electron. J. Combin. 18(2) (2012), Art. P37] from p = 2 to arbitrary primes. Our applications include congruences for numbers of non-crossing graphs and numbers of Kreweras walks modulo powers of 3, as well as congruences for Fuß–Catalan numbers and blossom tree numbers modulo powers of arbitrary primes.

1. Introduction

The purpose of the present article is to generalise the basic theory concerning congruences for combinatorial sequences developed in [12] for 2-power moduli to arbitrary prime power moduli, and to discuss a number of further applications of our method.

Given a prime number p, consider the (formal) power series

Φ(z) = Φ_{p}(z) := ∑_{n≥0} z^{p^{n}}.  (1.1)

The series Φ_{p}(z) is easily seen to be transcendental over ℤ; this can be shown, for instance, by generalising (in a straightforward manner) the density argument given in [12, Lemma 1]. In Lemma 1 below, we provide a different, and more elegant, argument, which however presupposes a number of non-trivial facts concerning certain auxiliary series H_{b_{1},b_{2},...,b_{r}}(z) established in Section 3.

While Φ_{p}(z) is transcendental over ℤ, it is easily seen to be algebraic when considered over finite rings ℤ/p^{γ}ℤ, and the first focus of our paper is on polynomial identities for Φ_{p}(z) modulo a given p-power, which are of minimal degree; cf. the next section. A (still stubbornly unproven) conjecture concerns this minimal degree of Φ_{p}(z) modulo p^{γ}, see Conjecture 4 in the next section. As in [12, Sec. 2] for the case of the prime p = 2, we are only able to establish that the conjectured minimal degree constitutes a lower bound, see Lemma 1.

The basic idea of our method for producing and establishing congruences modulo p-powers for combinatorial sequences is to express solutions of appropriate (formal) differential equations (in technical terms: differentially algebraic power series over the integers satisfying a uniqueness condition) as polynomials in Φ_{p}(z), with coefficients that are Laurent polynomials in z. For each such differential equation, our method may be implemented to (semi-)automatically yield such polynomial expressions in Φ_{p}(z) for arbitrary p-power moduli, provided such expressions do in fact exist.

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

Key words and phrases. Polynomial recurrences, Fuß–Catalan numbers, non-crossing graphs, Kreweras walks, blossom trees.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and F50-N15, the latter in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

∗Research supported by Lise Meitner Grant M1661-N25 of the Austrian Science Foundation FWF.

However, such a procedure as described in the last paragraph would be without any practical value, if we could not, at the same time, provide an efficient algorithm for extracting coefficients from powers of Φ_{p}(z). This is the topic of Section 3. Briefly, the solution to this problem we propose is to (i) expand powers of Φ_{p}(z) into ℤ-linear sums of certain auxiliary series

H_{b_{1},b_{2},...,b_{r}}(z) := ∑_{n_{1}>n_{2}>···>n_{r}≥0} z^{b_{1}p^{n_{1}}+b_{2}p^{n_{2}}+···+b_{r}p^{nr}};  (1.2)

(ii) to show that the set consisting of 1 and the series (1.2) with parameters b_{1}, b_{2}, …, b_{r} relatively prime to p are linearly independent over the ring ℤ[z, z^{−1}], as well as over the rings (ℤ/p^{γ}ℤ)[z, z^{−1}]; (iii) to prove that a series H_{b_{1},b_{2},...,b_{r}}(z), without restrictions on its parameters b_{1}, b_{2}, …, b_{r}, can always be expressed as a linear combination over ℤ[z, z^{−1}] of these linear independent series; and (iv) to demonstrate that coefficient extraction from a series (1.2) with all parameters b_{1}, b_{2}, …, b_{r} relatively prime to p can be done effectively; cf. Equation (3.1), Corollary 7, Proposition 9, and Remark 8.

A detailed description of our method is given in Section 4, while the remaining sections treat a number of applications beyond the case where p = 2: in Section 5, we obtain congruences modulo arbitrary 3-powers for the number of non-crossing graphs with a given number of vertices; Section 6 deals with congruences modulo 3-powers for the number of Kreweras walks of given length in the plane; Section 7 treats the Fuß–Catalan numbers

F (n; k) := \frac{1}{n}\binom{kn}{n − 1}

modulo powers of a prime number p, provided that the parameter k is itself a power of p; finally, the last section studies the number

B(n; p) := \frac{p + 1}{n((p − 1)n + 2)}\binom{pn}{n − 1}

of p-ary blossom trees with n white nodes modulo arbitrary powers of p. See, in particular, Theorems 11, 12, 15, 16, 19, 20, 23, and 25.

We would like to point out that Rowland and Yassawi [17] have developed a completely different method for proving congruences. Their method applies to diagonals of rational functions, and is based on the construction of automata. Our method is complementary: there is a considerable intersection of applications (in particular, if one also adds the variation [13] of the method presented here), but neither can our method cover all diagonals of rational functions nor can their method cover all differentially algebraic series. Applications of our method not covered by [17] can be found in [12, Sections 8–14].

2. The p-power series Φ_{p}(z)

The series Φ_{p}(z) in (1.1) is the principal character in the method for determining congruences of recursive sequences modulo p-powers which we describe in Section 4. For the sake of better readability, we shall usually suppress the index p and simply write Φ(z) for Φ_{p}(z). It is not hard to see that this series is transcendental over ℤ[z] (this follows for instance from Lemma 1 below). However, if the coefficients of Φ(z) are considered modulo a p-power p^{γ}, then Φ(z) obeys a polynomial relation with coefficients that are polynomials in z. The focus of this section is on what may be said concerning such polynomial relations, and, in particular, about those of minimal length. In the proofs of Lemma 1 and Proposition 2 below, we shall already make use of some fundamental results which will only be established later in Section 3. This will not create any circular arguments since Lemma 1 and Proposition 2 will not be needed in Section 3.

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

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

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

We say that a polynomial A(z, t) in z and t is minimal for the modulus p^{γ}, if it is monic (as a polynomial in t), has integral coefficients, satisfies A(z, Φ(z)) = 0 modulo p^{γ}, and there is no monic polynomial B(z, t) with integral coefficients of t-degree less than that of A(z, t) with B(z, Φ(z)) = 0 modulo p^{γ}. (Minimal polynomials are not unique; see Remark 3.) Furthermore, we let v_{p}(α) denote the p-adic valuation of the integer α, that is, the maximal exponent e such that p^{e} divides α.

The lemma below provides a lower bound for the degree of a polynomial that is minimal for the modulus p^{γ}.

Lemma 1. If A(z, t) is minimal for the modulus p^{γ}, then the degree d of A(z, t) in t satisfies v_{p}(d!) ≥ γ. In particular, the series Φ(z) is transcendental over ℤ[z].

Proof. Given positive integers b_{1}, b_{2}, …, b_{r}, define the series H_{b_{1},b_{2},...,b_{r}}(z) by

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

By (3.1) and Proposition 9, a power Φ^{d}(z) can be expressed as a linear combination of series H_{b_{1},b_{2},...,b_{s}}(z) and 1 with coefficients in ℤ[z]. Furthermore, all b_{i}’s in these series are relatively prime to p, and b_{1} + b_{2} + ⋯ + b_{s} ≤ d. In particular, we have

Φ^{d}(z) = d! H_{1,1,...,1}(z) + other terms,  (2.1)

with d repetitions of 1 in the index of H. Since, by Corollary 7, the series H_{b_{1},b_{2},...,b_{s}}(z) and 1 are linearly independent over (ℤ/p^{γ}ℤ)[z], and H_{1,1,...,1}(z) (with d repetitions of 1) does not appear in the expansion of Φ^{e}(z) for e < d, a monic polynomial of degree d in Φ(z) can only vanish modulo p^{γ} if d! ≡ 0 (mod p^{γ}), or, equivalently, if v_{p}(d!) ≥ γ. This establishes the assertion. □

Proposition 2. Minimal polynomials for the moduli p, p^{2}, p^{3}, …, p^{p+1} are

t^{p} − t + z  modulo p,
(t^{p} − t + z)^{2}  modulo p^{2},
. . . . . . . . . . . . . . . . . . . . . . . . . .
(t^{p} − t + z)^{p}  modulo p^{p},
(t^{p} − t + z)^{p} − p^{p−1}(t^{2} − t + z) modulo p^{p+1},

Proof. By (3.1), we have

Φ^{p}(z) = ∑_{r=1}^{p}_{∑_{b_{1},...,b_{r}≥1} ; b_{1}+···+b_{r}=p} \frac{p!}{b_{1}! b_{2}! ⋯ b_{r}!}H_{b_{1},b_{2},...,b_{r}}(z)

= ∑_{n≥0} z^{p^{n+1}} + p ∑_{r=2}^{p}_{∑_{b_{1},...,b_{r}≥1} ; b_{1}+···+b_{r}=p} \frac{(p − 1)!}{b_{1}! b_{2}! ⋯ b_{r}!}H_{b_{1},b_{2},...,b_{r}}(z),

or, equivalently,

Φ^{p}(z) − Φ(z) + z = p ∑_{r=2}^{p}_{∑_{b_{1},...,b_{r}≥1} ; b_{1}+···+b_{r}=p} \frac{(p − 1)!}{b_{1}! b_{2}! ⋯ b_{r}!}H_{b_{1},b_{2},...,b_{r}}(z).  (2.2)

Clearly, this implies the claim modulo p, and, by potentiation, as well the claims modulo p^{i} for i = 2, 3, …, p.

Taking both sides of (2.2) to the p-th power, we obtain

(Φ^{p}(z) − Φ(z) + z)^{p} = p^{p} ∑_{r=2}^{p}_{∑_{b_{1},...,b_{r}≥1} ; b_{1}+···+b_{r}=p} (\frac{(p − 1)!}{b_{1}! b_{2}! ⋯ b_{r}!})^{p} H_{b_{1},b_{2},...,b_{r}}^{p}(z) + O (p^{p+1}) ,

where the expression O (p^{p+1}) subsumes terms all of whose coefficients are divisible by p^{p+1}. If, in the sum over r on the right-hand side, we use the congruences N^{p} ≡ N (mod p), which is valid for any integer N, and

H_{b_{1},b_{2},...,b_{r}}^{p}(z) = H_{b_{1},b_{2},...,b_{r}}(z) + O (p) ,

then, in combination with (2.2) read from right to left, we obtain the claim on the minimal polynomial modulo p^{p+1}. □

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

(t^{p} − t + z)^{2} + p(t^{p} − t + z)

is obviously also a minimal polynomial for the modulus p^{2}.

Based on the observations in Proposition 2 and Lemma 1, we propose the following conjecture.

Conjecture 4. The degree of a minimal polynomial for the modulus p^{γ}, γ ≥ 1, is the least d such that v_{p}(d!) ≥ γ.

Remark 5. (1) Given the p-ary expansion of d, say

d = d_{0} + d_{1} · p + d_{2} · p^{2} + ⋯ + d_{r} · p^{r}, 0 ≤ d_{i} ≤ p − 1,

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

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

= ∑_{i=1}^{r} ∑_{ℓ=1}^{i} d_{i}p^{i−ℓ} = ∑_{i=1}^{r} d_{i} \frac{p^{i} − 1}{p − 1} = \frac{d − s(d)}{p − 1},  (2.3)

where s(d) denotes the sum of digits of d in its p-ary expansion. Consequently, an equivalent way of phrasing Conjecture 4 is to say that the degree of a minimal polynomial for the modulus p^{γ} is the least d with d − s(d) ≥ (p − 1)γ.

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

A_{δ}(z, Φ(z)) = 0 modulo p^{(p^{δ}−1)/(p−1)}.  (2.4)

For, arguing by induction, let us suppose that we have already constructed A_{1}(z, t), A_{2}(z, t), …, A_{m}(z, t) satisfying (2.4). Let α be a positive integer which is divisible by p and

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

be its p-ary expansion. Then we have

∏_{δ=1}^{m} A_{δ}^{α_{δ}}(z, Φ(z)) = 0 modulo ∏_{δ=1}^{m} p^{α_{δ}(p^{δ}−1)/(p−1)} = p^{(α−s(α))/(p−1)}.  (2.5)

On the other hand, the degree of the left-hand side of (2.5) as a polynomial in Φ(z) is ∑_{δ=1}^{m} α_{δ}p^{δ} = α.

Let us put these observations together. In view of (2.3), Lemma 1 says that the degree of a minimal polynomial for the modulus p^{γ} cannot be smaller than the least integer, d^{(γ)} say, for which d^{(γ)} − s(d^{(γ)}) ≥ (p − 1)γ. (We point out that d^{(γ)} must be automatically divisible by p.) If we take into account that the quantity α − s(α), as a function in α, is weakly monotone increasing in α, then (2.5) tells us that, as long as

d^{(γ)} ≤ (p − 1)p + (p − 1)p^{2} + ⋯ + (p − 1)p^{m} = p^{m+1} − p,

we have found a monic polynomial of degree d^{(γ)}, B_{γ}(z, t) say, for which B_{γ}(z, Φ(z)) = 0 modulo p^{γ}, namely the left-hand side of (2.5) with α replaced by d^{(γ)}, to wit

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

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

Since

p^{m+1} − p − s(p^{m+1} − p) = p^{m+1} − p − (p − 1)m,

we have thus found minimal polynomials for all moduli p^{γ} with γ ≤ \frac{p^{m+1}−p}{p−1} − m. Now we should note that the quantity α − s(α) makes a jump from p^{m+1} − p − (p − 1)m to p^{m+1} −1 when we move from α = p^{m+1} −p to α = p^{m+1} (the reader should recall that it suffices to consider α’s which are divisible by p). If we take A_{m}^{p}(z, t), which has degree p · p^{m} = p^{m+1}, then, by (2.4), we also have a minimal polynomial for the modulus

(p^{(p^{m}−1)/(p−1)})^{p} = p^{(p^{m+1}−p)/(p−1)}

and, in view of the preceding remark, as well for all moduli p^{γ} with γ between \frac{p^{m+1}−p}{p−1} − m + 1 and \frac{p^{m+1}−p}{p−1}.

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

The arguments above show at the same time that, supposing that we have already constructed A_{1}(z, t), A_{2}(z, t), …, A_{m}(z, t), the polynomial A_{m}^{p}(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 p. In practice, one can recursively compute polynomials A_{δ}(z, t) satisfying (2.4) by following the procedure outlined in the next-to-last paragraph before Lemma 6 in the next section. It is these computations (part of which are reported in Proposition 2) which have led us to believe in the truth of Conjecture 4.

3. Coefficient extraction from powers of Φ(z)

In the next section we are going to describe a method for expressing formal power series satisfying certain differential equations, after the coefficients of the series have been reduced modulo p^{k}, as polynomials in the p-power series Φ(z) (which has been discussed in the previous section; for the definition see (1.1)), the coefficients being Laurent polynomials in z. Such a method would be without value if we could not, at the same time, provide a procedure for extracting coefficients from powers of Φ(z). The description of such a procedure is the topic of this section.

Clearly, a brute force expansion of a power Φ^{K}(z), where K is a given positive integer, yields

Φ^{K}(z) = ∑_{r=1}^{K}_{∑_{b_{1},...,b_{r}≥1} ; b_{1}+···+b_{r}=K} \frac{K!}{b_{1}! b_{2}! ⋯ b_{r}!}H_{b_{1},b_{2},...,b_{r}}(z),  (3.1)

where

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

The expansion (3.1) is not (yet) suited for our purpose, since, when b_{1}, b_{2}, …, b_{r} vary over all possible choices such that their sum is K, the series H_{b_{1},b_{2},...,b_{r}}(z) are not linearly independent over the ring ℤ[z, z^{−1}] of Laurent polynomials in z over the integers^{1}, and, secondly, coefficient extraction from a series H_{b_{1},b_{2},...,b_{r}}(z) can be a hairy task if some of the b_{i}’s are divisible by p.

However, we shall show (see Corollary 7) that, if we restrict to b_{i}’s which are relatively prime to p, then the corresponding series H_{b_{1},b_{2},...,b_{r}}(z), together with the (trivial) series 1, are linearly independent over ℤ[z, z^{−1}], and there is an efficient algorithm to express an arbitrary series H_{b_{1},b_{2},...,b_{s}}(z), without any restriction on the b_{i}’s, as a linear combination over ℤ[z, z^{−1}] of 1 and the former series (see Proposition 9). Since coefficient extraction from a series H_{b_{1},b_{2},...,b_{r}}(z) with all b_{i}’s relatively prime to p is straightforward (see Remark 8), this solves the problem of coefficient extraction from powers of Φ(z).

As a side result, the procedure which we described in the previous paragraph, and which will be substantiated below, in combination with (3.1), provides all the means for determining minimal polynomials in the sense of Section 2: as explained in Item (2) of Remark 5 at the end of that section, it suffices to find a minimal polynomial for the modulus p^{(p^{δ}−1)/(p−1)}, δ = 1, 2, . . .. For doing this, we would take a minimal polynomial A_{δ−1}(z, t) for the modulus p^{(p^{δ−1}−1)/(p−1)}, expand A_{δ−1}^{p}(z, t), and replace each coefficient c_{α,β} of a monomial z^{α}t^{β} in A_{δ−1}^{p}(z, t) by c_{α,β} + p^{(p^{δ}−p)/(p−1)}x_{α,β}, where x_{α,β} is a variable, thereby obtaining a modified polynomial, B_{δ−1}(z, t) say. Now we would substitute Φ(z) for t, so that we obtain B_{δ−1}(z, Φ(z)). Here, we express powers of Φ(z) in terms of the series H_{a_{1},a_{2},...,a_{r}}(z) with all a_{i}’s relatively prime to p, and collect terms. By reading the coefficients of z^{γ}H_{a_{1},a_{2},...,a_{r}}(z) in this expansion of B_{δ−1}(z, Φ(z)) and equating them to zero modulo p^{(p^{δ}−1)/(p−1)}, we produce a system of linear equations modulo p^{(p^{δ}−1)/(p−1)} in the unknowns x_{α,β}. By the definition of A_{δ−1}(z, t), after division by p^{(p^{δ}−p)/(p−1)}, this system reduces to a system modulo p, that is, to a linear system of equations over the field with p elements. A priori, this system need not have a solution, but experience seems to indicate that it always does; see Conjecture 4.

1The same is true for an arbitrary commutative unital ring in place of the ring ℤ of integers.

We start with an auxiliary result pertaining to the uniqueness of representations of integers as sums of powers of p with multiplicities, tailor-made for application to the series H_{a_{1},a_{2},...,a_{r}}(z).

Lemma 6. 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 the a_{i}’s or b_{i}’s divisible by p, with 1 ≤ a_{i} ≤ d for 1 ≤ i ≤ r, and 1 ≤ b_{i} ≤ d for 1 ≤ i ≤ s. If

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

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 (3.2) becomes

a_{1}p^{2d} = b_{1}p^{n_{1}} + c.  (3.3)

If n_{1} > 2d, then the above equation implies

a_{1}p^{2d} ≡ c modulo p^{2d+1}.  (3.4)

Consequently, the integer c must be divisible by p^{2d}. By assumption, we have |c| ≤ d. Since d < p^{2d}, the only possibility is that c vanishes. But then it follows from (3.4) that a_{1} is divisible by p, a contradiction.

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

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

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

which is again a contradiction to (3.3).

The only remaining possibility is n_{1} = 2d. If this is substituted in (3.3) and the resulting equation is combined with |c| ≤ d < p^{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 (3.2) modulo p^{2d} yields

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

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

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

We have

0 ≤ b ≤ p^{−2d}d (p^{2d−1} + p^{2d−2} + ⋯ + p^{2d−s+t} + 1)

≤ p^{−2d}d (\frac{1}{p−1}(p^{2d} − p^{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 (3.6). 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 (3.2) with r = R, then we obtain

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

or

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

depending on whether s = R − 1 or s = R. The first case is absurd, since c ≤ d < p^{2d} ≤ a_{R}p^{2d}. On the other hand, the second case has already been considered in (3.3), 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 announced independence of the series H_{a_{1},a_{2},...,a_{r}}(z) with all a_{i}’s relatively prime to p is now an easy consequence.

Corollary 7. For any commutative unital ring R, the series H_{a_{1},a_{2},...,a_{r}}(z), with all a_{i}’s relatively prime to p, together with the series 1 are linearly independent over R[z, z^{−1}]. In particular, they are linearly independent over (ℤ/pℤ)[z, z^{−1}], over (ℤ/p^{γ}ℤ)[z, z^{−1}] for an arbitrary positive integer γ, and over ℤ[z, z^{−1}].

Proof. Let us suppose that

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

where the q_{i}(z)’s are non-zero Laurent polynomials in z over R, the r_{i}’s are positive integers, and a_{j}^{(i)}, j = 1, 2, …, r_{i}, i = 1, 2, …, N, are integers relatively prime to p. 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 q_{i_{0}}(z) is non-zero (otherwise we could multiply both sides of (3.7) 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 Laurent polynomials q_{i}(z), i = 0, 1, …, N. Then, according to Lemma 6 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})}p^{2rd}+a_{2}^{(i_{0})}p^{2(r−1)d}+···+a_{r}^{(i_{0})}p^{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 (3.7) establishes the assertion of the corollary. □

Remark 8. Coefficient extraction from a series H_{a_{1},a_{2},...,a_{r}}(z) with all a_{i}’s relatively prime to p is straightforward: if we want to know whether z^{M} appears in H_{a_{1},a_{2},...,a_{r}}(z), that is, whether we can represent M as

M = a_{1}p^{n_{1}} + a_{2}p^{n_{2}} + ⋯ + a_{r}p^{n_{r}}

for some n_{1}, n_{2}, …, n_{r} with n_{1} > n_{2} > ⋯ > n_{r} ≥ 0, then necessarily n_{r} = v_{p}(M), n_{r−1} = v_{p}(M − a_{r}p^{n_{r}}), etc. The term z^{M} appears in H_{a_{1},a_{2},...,a_{r}}(z) if, and only if, the above process terminates after exactly r steps. This means, that, with n_{r}, n_{r−1}, …, n_{1} constructed as above, we have

M − (a_{s}p^{n_{s}} + ⋯ + a_{r−1}p^{n_{r−1}} + a_{r}p^{n_{r}}) > 0

for s > 1, and

M − (a_{1}p^{n_{1}} + ⋯ + a_{r−1}p^{n_{r−1}} + a_{r}p^{n_{r}}) = 0.

It should be noted that, given a_{1}, a_{2}, …, a_{r}, this procedure of coefficient extraction needs at most O(log M) operations, that is, its computational complexity is linear.

It remains to show that an arbitrary series H_{b_{1},b_{2},...,b_{s}}(z) can be expressed as a linear combination over ℤ[z, z^{−1}] of the series 1 and the series H_{a_{1},a_{2},...,a_{r}}(z), where all a_{i}’s are relatively prime to p.

Proposition 9. For any positive integers b_{1}, b_{2}, …, b_{r}, the series H_{b_{1},b_{2},...,b_{s}}(z) can be expressed as a linear combination over ℤ[z] of the series 1 and series of the form H_{a_{1},a_{2},...,a_{s}}(z), where all a_{i}’s are relatively prime to p, s ≤ r, and a_{1} + a_{2} + ⋯ + a_{s} ≤ b_{1} + b_{2} + ⋯ + b_{r}.

Proof. Given H_{b_{1},b_{2},...,b_{s}}(z) where not all b_{i}’s are relatively prime to p, we let h be maximal such that b_{h} ≡ 0 (mod p). If there is no such h, then there is nothing to do. If there is, then we apply the appropriate case of

H_{b_{1},...,b_{h−1},pb′_{h},b_{h+1},...,b_{r}}(z)

= \begin{cases}H_{b_{1},...,b_{h−1},b′_{h},b_{h+1},...,b_{r}}(z) + H_{b_{1},...,b_{h−1}+b′_{h},b_{h+1},...,b_{r}}(z) − H_{b_{1},...,b_{h−1},pb′_{h}+b_{h+1},...,b_{r}}(z), \\ if 1 < h < r, \\ H_{b′_{1},b_{2},...,b_{r}}(z) − H_{pb′_{1}+b_{2},...,b_{r}}(z), & if 1 = h < r, \\ H_{b_{1},...,b_{h−1},b′_{h}}(z) + H_{b_{1},...,b_{h−1}+b′_{h}}(z) − z^{b′_{h}}H_{b_{1},...,b_{h−1}}(z), & if 1 < h = r, \\ H_{b′_{1}}(z) − z^{b′_{1}}, & if 1 = h = r. \end{cases} (3.8)

These identities are due to Hou [11], and they are straightforward to verify. The reduction (3.8) is now applied to the series which arose during the first application of (3.8). This process is repeated until all series H_{a_{1},a_{2},...,a_{s}}(z) in the obtained expression have the property that each index a_{i} is relatively prime to p. From (3.8), it is obvious that all these series satisfy a_{1} + a_{2} + ⋯ + a_{s} ≤ b_{1} + b_{2} + ⋯ + b_{r}. This proves the assertions of the proposition. □

To conclude this section, let us provide an illustration of the above discussion. We set ourselves the task of determining the coefficient of z^{297398301914493} in Φ^{5}(z) for Φ(z) = ∑_{n≥0} z^{3^{n}}. In order to accomplish this task, we first express Φ^{5}(z) in terms of series H_{a_{1},...,a_{r}}(z) with all a_{i}’s being relatively prime to 3. Indeed, by means of the expansion (3.1) and the algorithm described in the proof of Proposition 9, we have

Φ^{5}(z) = 120H_{1,1,1,1,1}(z) + 60H_{2,1,1,1}(z) + 60H_{1,2,1,1}(z) + 60H_{1,1,2,1}(z) + 60H_{1,1,1,2}(z) + 30H_{2,2,1}(z) + 30H_{2,1,2}(z) + 30H_{1,2,2}(z) − 15H_{4,1}(z) − 15H_{1,4}(z) − 9H_{5}(z) + 60H_{1,1,1}(z) + 30H_{2,1}(z) + 30H_{1,2}(z) − 20zH_{1,1}(z) − 10zH_{2}(z) + 10H_{1}(z) − 10z. (3.9)

Now we have to answer the question, in which of the series H_{a_{1},...,a_{r}}(z) that appear in this expansion of Φ^{5}(z) do we find the monomial z^{297398301914493}. Using the algorithm described in Remark 8, we see that

297398301914493 = 3^{30} + 3^{29} + 3^{28},
= 2 · 3^{29} + 2 · 3^{29} + 3^{28},
= 2 · 3^{28} + 3^{28} + 2 · 3^{28} + 183014339639688,
= 3^{30} + 2 · 3^{28} + 2 · 3^{28},
= 4 · 3^{29} + 3^{28},
= 3^{30} + 4 · 3^{28},
= 3^{29} + 3^{29} + 2 · 3^{29} + 3^{28},
= 3^{30} + 3^{28} + 3^{28} + 2 · 328,
= 5 · 3^{28} + 183014339639688,
= 2 · 3^{29} + 3^{28} + 137260754729766,
= 3^{28} + 2 · 28 + 228767924549610,
= 2 · 3^{28} + 251644717004571,
= 3^{28} + 274521509459532.

Here, the first line shows that z^{297398301914493} appears in H_{1,1,1}(z) (thereby making it impossible to appear in H_{1,1,1,1,1}(z), H_{2,1,1,1}(z), or H_{1,2,1,1}(z)), the fifth line shows that it appears in H_{4,1}(z), and the sixth line shows that it appears in H_{4,1}(z), while the remaining lines show that it does not appear in any other term in the expansion of Φ^{5}(z) displayed in (3.9). Hence, by taking into account the coefficients with which the series H_{1,1,1}(z), H_{4,1}(z), and H_{1,4}(z) appear in this expansion, the coefficient of z^{297398301914493} in Φ^{5}(z) is seen to equal 60 − 15 − 15 = 30.

4. The method

We consider a (formal) differential equation

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

where P is a polynomial with integer coefficients, which has a power series solution F (z) with integer coefficients. We assume that this power series solution F (z) is uniquely determined by (4.1) over the integers, and also over all rings (ℤ/p^{γ}ℤ), where p is a fixed prime number and γ any positive integer.

In the above situation, we propose the following algorithmic approach to determining the series F (z) modulo a p-power p^{p^{α}}, for some non-negative integer α. We make the Ansatz

F (z) = ∑_{i=0}^{p^{α+1}−1} a_{i}(z)Φ^{i}(z) modulo p^{p^{α}},  (4.2)

with Φ(z) as given in (1.1), and where the a_{i}(z)’s are (at this point) undetermined Laurent polynomials in z. Now we substitute (4.2) into (4.1), and we shall gradually determine approximations a_{i,β}(z) to a_{i}(z) such that (4.1) holds modulo p^{β}, for β = 1, 2, …, p^{α}. To start the procedure, we consider the differential equation (4.1) modulo p, with

F (z) = F_{1}(z) = ∑_{i=0}^{p^{α+1}−1} a_{i,1}(z)Φ^{i}(z) modulo p.  (4.3)

Using the elementary fact that Φ′(z) = 1 modulo p, we see that the left-hand side of (4.1) is a polynomial in Φ(z) with coefficients that are Laurent polynomials in z. We reduce powers Φ^{k}(z) with k ≥ p^{α+1} using the relation (which is implied by the minimal polynomial for the modulus p given in Proposition 2)^{2}

(Φ^{p}(z) − Φ(z) + z)^{p^{α}} = 0 modulo p^{p^{α}}.  (4.4)

Since, at this point, we are only interested in finding a solution to (4.1) modulo p, the above relation simplifies to

Φ^{p^{α+1}}(z) − Φ^{p^{α}}(z) + z^{p^{α}} = 0 modulo p.  (4.5)

Now we compare coefficients of powers Φ^{k}(z), k = 0, 1, …, p^{α+1} − 1 (see Remark 10). This yields a system of p^{α+1} (differential) equations (modulo p) for the unknown Laurent polynomials a_{i,1}(z), i = 0, 1, …, p^{α+1} − 1, which may or may not have a solution.

Provided we have already found Laurent polynomials a_{i,β}(z), i = 0, 1, …, p^{α+1} − 1, for some β with 1 ≤ β ≤ p^{α} − 1, such that

∑_{i=0}^{p^{α+1}−1} a_{i,β}(z)Φ^{i}(z)  (4.6)

2Actually, if we would like to obtain an optimal result, we should use the relation implied by a minimal polynomial for the modulus p^{p^{α}} in the sense of Section 2. But since we have no general formula available for such a minimal polynomial (cf. Item (2) of Remark 5 in that section), and since we wish to prove results for arbitrary moduli, choosing instead powers of a minimal polynomial for the modulus p is the best compromise. In principle, it may happen that there exists a polynomial in Φ(z) with coefficients that are Laurent polynomials in z, which is identical with F (z) after reduction of its coefficients modulo p^{p^{α}}, but the Ansatz (4.2) combined with the reduction (4.4) fails because it is too restrictive. We are not aware of a concrete example where this obstruction occurs. The subgroup numbers of SL_{2}(ℤ) which are treated modulo 8 in [12, Section 11] by the method described here (specialised to p = 2), and modulo 16 by an enhancement of the method outlined in [12, Appendix D] are a potential candidate when considered modulo 2^{β} for β ≥ 5. On the other hand, once we are successful using this (potentially problematic) Ansatz, then the result can easily be converted into an optimal one by further reducing the polynomial thus obtained, using the relation implied by a minimal polynomial for the modulus p^{p^{α}}.

solves (4.1) modulo p^{β}, we put

a_{i,β+1}(z) := a_{i,β}(z) + p^{β}b_{i,β+1}(z), i = 0, 1, …, p^{α+1} − 1,  (4.7)

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

∑_{i=0}^{p^{α+1}−1} a_{i,β+1}(z)Φ^{i}(z)  (4.8)

for F (z) in (4.1). Using the fact that Φ′(z) = ∑_{n=0}^{β} p^{n}z^{p^{n}−1} modulo p^{β+1}, we expand the left-hand side as a polynomial in Φ(z) (with coefficients being Laurent polynomials in z), we apply again the reduction using relation (4.4), we compare coefficients of powers Φ^{k}(z), k = 0, 1, …, p^{α+1} − 1 (again, see Remark 10), and, as a result, we obtain a system of p^{α+1} (differential) equations (modulo p^{β+1}) for the unknown Laurent polynomials b_{i,β+1}(z), i = 0, 1, …, p^{α+1}−1, which may or may not have a solution. If we manage to push this procedure through until β = p^{α} − 1, then, setting a_{i}(z) = a_{i,p^{α}}(z), i = 0, 1, …, p^{α+1} − 1, the right-hand side of (4.2) is a solution to (4.1) modulo p^{p^{α}}, as required.

Remark 10. As the reader will have noticed, each comparison of coefficients of powers of Φ(z) is based on the “hope” that, if a polynomial in Φ(z) is zero modulo a p-power p^{β} (as a formal Laurent series), then already all coefficients of powers of Φ(z) in this polynomial vanish modulo p^{β}. However, this implication is false in general (see Lemma 39 in [12, Appendix D] for the case of modulus 16). It may thus happen that the method described in this section fails to find a solution modulo p^{β} to a given differential equation in the form of a polynomial in Φ(z) with coefficients that are Laurent polynomials in z over the integers, while such a solution does in fact exist. As a matter of fact, this situation already occurred earlier in [12, Theorem 28] in the context of the analysis modulo 16 of the subgroup numbers of SL_{2}(ℤ). There exists an enhancement of the method, outlined for the case of p = 2 in [12, Appendix D], which (at least in principle) allows us to decide whether or not a solution modulo a given power in terms of a polynomial in Φ(z) with coefficients that are Laurent polynomials in z over the integers exists, and, if so, to explicitly find such a solution. Since we do not make use of this enhancement in the present article, we refrain from presenting it here.

It is not difficult to see that performing the iterative step (4.7) amounts to solving a system of linear differential equations in the unknown functions b_{i,β+1}(z) modulo p, where all of them are Laurent polynomials in z, and where only derivatives up to order p − 1 of the b_{i,β+1}(z)’s occur. Solving such a system is equivalent to solving an ordinary system of linear equations. This equivalence was explained for the case of p = 2 in [12, Lemma 12]. Since we do not need the general version of this lemma for arbitrary primes p in the present article, we leave it to the reader to work out the straightforward details.

We remark that the idea of the method that we have described in this section has certainly further potential. For example, the fact that the series Φ(z) remains invariant under the substitution z → z^{p} (or, more generally, under the substitution z → z^{p^{h}}, where h is some positive integer) — up to a simple additive correction — can be exploited in order to extend the range of applicability of our method to equations where we not only allow differentiation but also this kind of substitution. This idea is actually already used in Section 7, see Theorem 19.

5. The number of non-crossing connected graphs modulo 3-powers

In this section, we apply our method to determining congruences modulo powers of 3 for the numbers of non-crossing connected graphs with a given number of vertices. The origin of this analysis lies in a conjecture of Deutsch and Sagan [5, Conj. 5.18]. See (5.9) and the subsequent paragraph for more information.

A non-crossing graph on n vertices is a graph whose vertices are labelled by 1, 2, …, n, which can be embedded in the plane without crossings of edges in such a manner that the vertices are placed around a circle in clock-wise order. Let N_{n} denote the number of non-crossing connected graphs with n vertices. It is known from [9, Eq. (16)] that

N_{n} = \frac{2^{2n−1}}{n} \binom{\frac{3}{2}n − 2}{n − 1} − \frac{2^{2n−2}}{n} \binom{\frac{3}{2}n − \frac{3}{2}}{n − 1}.  (5.1)

Let N(z) := ∑_{n≥1} N_{n} z^{n} be the corresponding generating function. According to [6, Eq. (47)] (see also [8, Sec. 2.1]), the generating function N(z) satisfies the polynomial equation

N^{3}(z) + N^{2}(z) − 3z N(z) + 2z^{2} = 0.  (5.2)

It is not difficult to see that (5.2) determines N(z) uniquely as a formal power series over ℤ, and as well modulo any power of 3, provided N_{0} = 0 and N_{1} = 1.

Theorem 11. Let Φ(z) = ∑_{n≥0} z^{3^{n}}, and let α be a non-negative integer. Then the generating function N(z), when reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Φ(z) of degree at most 3^{α+1} − 1, with coefficients that are Laurent polynomials in z over the integers.

Remark. Computer experiments seem to indicate that the generating function N(z) in Theorem 11, when reduced modulo 3^{3^{α}}, can in fact be expressed as a polynomial in Φ(z) of degree at most 3^{α+1} − 1, with coefficients that are polynomials in z over the integers.

Proof of Theorem 11. We apply the method from Section 4. We start by substituting the Ansatz (4.3) in (5.2) and reducing the result modulo 3. In this way, we obtain

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

− ∑_{0≤i<j≤3^{α+1}−1} a_{i,1}(z)a_{j,1}(z)Φ^{i+j}(z) + 2z^{2} = 0 modulo 3. (5.3)

We claim that the following choices solve the above congruence:

a_{0,1}(z) = s_{α}^{2}(z) + s_{α}(z) modulo 3,
a_{3^{α},1}(z) = 1 − s_{α}(z) modulo 3,
a_{2·3^{α},1}(z) = 1 modulo 3,  (5.4)

where s_{α}(z) = ∑_{k=0}^{α−1} z^{3^{k}}, with all other a_{i,1}(z) vanishing. In order to verify the claim, we substitute our choices in (5.3). For the left-hand side, we obtain

Φ^{2·3^{α+1}}(z) + (1 − s_{α}^{3}(z)) Φ^{3^{α+1}}(z) + s_{α}^{6}(z) + s_{α}^{3}(z)

+ Φ^{4·3^{α}}(z) + (1 + s_{α}^{2}(z) + s_{α}(z)) Φ^{2·3^{α}}(z) + s_{α}^{4}(z) − s_{α}^{3}(z) + s_{α}^{2}(z)

− (1 − s_{α}(z)) Φ^{3·3^{α}}(z) − (s_{α}^{2}(z) + s_{α}(z)) Φ^{2·3^{α}}(z) − (s_{α}(z) − s_{α}^{3}(z)) Φ^{3^{α}}(z) + 2z^{2}

modulo 3.

Using the relation (4.5) with p = 3 and reducing the obtained expression modulo 3, we arrive at

Φ^{2·3^{α}}(z) − 2z^{3^{α}}Φ^{3^{α}}(z) + z^{2·3^{α}} + (s_{α}(z) − s_{α}^{3}(z)) (Φ^{3^{α}}(z) − z^{3^{α}})

+ Φ^{3^{α}}(z) (Φ^{3^{α}}(z) − z^{3^{α}}) + Φ^{2·3^{α}}(z) + s_{α}^{6}(z) + s_{α}^{4}(z) + s_{α}^{2}(z)
− (s_{α}(z) − s_{α}^{3}(z)) Φ^{3^{α}}(z) + 2z^{2}

= z^{2·3^{α}} − z^{3^{α}}s_{α}(z) + z^{3^{α}}s_{α}^{3}(z) + s_{α}^{6}(z) + s_{α}^{4}(z) + s_{α}^{2}(z) − z^{2} modulo 3.

By using the relation

s_{α}^{3}(z) = s_{α}(z) + z^{3^{α}} − z  modulo 3  (5.5)

several times, this expression can be turned into

z^{2·3^{α}} − z^{3^{α}}s_{α}(z) + z^{3^{α}} (s_{α}(z) + z^{3^{α}} − z) + (s_{α}(z) + z^{3^{α}} − z)^{2}

+ s_{α}(z) (s_{α}(z) + z^{3^{α}} − z) + s_{α}^{2}(z) − z^{2} modulo 3.

After expansion and reduction modulo 3, one sees that this expression reduces to zero.

After we have completed the “base step,” we now proceed with the iterative steps described in Section 4. We consider the Ansatz (4.6)–(4.8), where the coefficients a_{i,β}(z) are supposed to provide a solution F_{β}(z) = ∑_{i=0}^{3^{α+1}−1} a_{i,β}(z)Φ^{i}(z) to (5.2) modulo 3^{β}. This Ansatz, substituted in (5.2), produces the congruence

− 3^{β} ∑_{j=0}^{3^{α+1}−1} ∑_{i=0}^{3^{α+1}−1} a_{j,β}(z)b_{i,β+1}(z)Φ^{i+j}(z) + F_{β}^{3}(z) + F_{β}^{2}(z) − 3zF_{β}(z) + 2z^{2} = 0

modulo 3^{β+1}. (5.6)

Since the sum has the prefactor 3^{β}, we may reduce the a_{i,β}(z) modulo 3. By construction, we have

a_{0,β}(z) = a_{0,1}(z) = s^{2}(α) + s_{α}(z) modulo 3,
a_{3^{α},β}(z) = a_{3^{α},1}(z) = 1 − s_{α}(z) modulo 3,
a_{2·3^{α},β}(z) = a_{2·3^{α},1}(z) = 1 modulo 3,

and a_{i,β} = 0 modulo 3 for all other i’s. If we substitute this in (5.6) and subsequently use (4.5) with p = 3 to reduce high powers of Φ(z), we obtain

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

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

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

− (1 − s_{α}(z)) z^{3^{α}}b_{i+2·3^{α},β+1}(z) − z^{3^{α}}b_{i+3^{α},β+1}(z)) Φ^{i}(z)

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

+ (1 − s_{α}(z)) b_{i+3^{α},β+1}(z) + b_{i,β+1}(z) − z^{3^{α}}b_{i+3^{α},β+1}(z)) Φ^{i}(z)

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

+b_{i−2·3^{α},β+1}(z) + b_{i,β+1}(z)) Φ^{i}(z)

+ F_{β}^{3}(z) + F_{β}^{2}(z) − 3zF_{β}(z) + 2z^{2} = 0 modulo 3^{β+1}.

By our assumption on F_{β}(z), we may divide by 3^{β}. Comparison of powers of Φ(z) then yields a system of congruences of the form

M · b = c modulo 3,  (5.7)

where b is the column vector of unknowns (b_{i,β+1}(z))_{i=0,1,...,3^{α+1}−1}, c is a (known) column vector of Laurent polynomials in z, and M is the matrix

(\begin{matrix}D(s_{α}^{2}(z) + s_{α}(z)) & D(−z^{3^{α}}) & D(−z^{3^{α}}(1 − s_{α}(z))) \\ D(1 − s_{α}(z)) & D(s_{α}^{2}(z) + s_{α}(z) + 1) & D(1 − s_{α}(z) − z^{3^{α}}) \\ D(1) & D(1 − s_{α}(z)) & D(s_{α}^{2}(z) + s_{α}(z) + 1) \end{matrix}) ,

with D(x) denoting the 3^{α} × 3^{α} diagonal matrix whose diagonal entries equal x. We claim that

det(M) = z^{2·3^{α}} modulo 3.

In order to see this, we subtract s_{α}^{2}(z) + s_{α}(z) times row i + 2 · 3^{α} from row i, i = 0, 1, …, 3^{α} − 1, and we subtract 1 − s_{α}(z) times row i + 2 · 3^{α} from row i + 3^{α}, i = 0, 1, …, 3^{α} − 1. If, in addition, we move rows 2 · 3^{α}, 2 · 3^{α} + 1, …, 3^{α+1} − 1 to the top of the matrix, then it attains an upper triangular form, from which one infers that

det(M) = (−1)^{2·3^{α}·3^{α}} det^{2}(D(s_{α}^{3}(z) − s_{α}(z) − z^{3^{α}})) det (D(1))
= (s_{α}^{3}(z) − s_{α}(z) − z^{3^{α}})^{2·3^{α}}
= z^{2·3^{α}} modulo 3,

by means of (5.5), as we claimed. As a consequence, the system (5.7) is (uniquely) solvable. Thus, we have proved that, for an arbitrary non-negative integer α, the algorithm of Section 4 will produce a solution F_{3^{α}}(z) to (5.2) modulo 3^{3^{α}} which is a polynomial in Φ(z) with coefficients that are Laurent polynomials in z. □

We have implemented this algorithm. As an illustration, the next theorem contains the result for the modulus 27.

Theorem 12. Let Φ(z) = ∑_{n≥0} z^{3^{n}}. Then we have

∑_{n≥1} N_{n} z^{n} = 18z^{3} + z^{2} + z + (18z^{3} + 12z^{2})Φ(z) + (3z^{2} + 15z)Φ^{2}(z)

+ (9z^{2} + 5z + 13)Φ^{3}(z) + (9z^{2} + 6z + 24)Φ^{4}(z) + (15z + 6)Φ^{5}(z)

+ (18z + 4)Φ^{6}(z) + (18z + 21)Φ^{7}(z) + 12Φ^{8}(z) modulo 27. (5.8)

In [5, Conj. 5.18], Deutsch and Sagan conjectured that

N_{n} ≡ \begin{cases}1 (mod 3) & if n = 3^{i} or n = 2 · 3^{i} for an integer i ≥ 0, \\ 2 (mod 3) & if n = 3^{i_{1}} + 3^{i_{2}} for integers i_{1} > i_{2} ≥ 0, \\ 0 (mod 3) & otherwise. \end{cases}  (5.9)

This conjecture was proved by Eu, Liu and Yeh [7] by carefully analysing a binomial sum formula for N_{n} modulo 3. A simpler proof was given by Gessel in [9]. It should be noted that his proof is essentially the one resulting from the α = 0 case of Theorem 11. Moreover, our results allow us to generalise this — in principle — to any power of 3. For the sake of illustration, we display the results for the moduli 9 = 3^{2} and 27 = 3^{3}.

Corollary 13. The numbers N_{n} of connected non-crossing graphs obey the following congruences modulo 27:

(i) N_{n} ≡ 1 (mod 27) if, and only if, n = 1, or n = 2 · 3^{i} with i ≥ 0; (ii) N_{n} ≡ 2 (mod 27) if, and only if, n = 10 · 3^{i} with i ≥ 1; (iii) N_{n} ≡ 3 (mod 27) if, and only if, n = 2 · 3^{i} + 1 with i ≥ 1, or n = 3^{i} + 2 with

i ≥ 1, or n = 2 · 3^{i_{1}} + 2 · 3^{i_{2}} with i_{1} > i_{2} ≥ 0, or n = 4 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} with i_{1} − 2 > i_{2} − 1 > i_{3} ≥ 0, or n = 3^{i_{1}} + 4 · 3^{i_{2}} + 3^{i_{3}} with i_{1} − 3 > i_{2} − 1 > i_{3} ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 4 · 3^{i_{3}} with i_{1} − 3 > i_{2} − 2 > i_{3} ≥ 0;

(iv) N_{n} ≡ 4 (mod 27) if, and only if, n = 3;

(v) N_{n} ≡ 5 (mod 27) if, and only if, n = 4 · 3^{i} with i ≥ 1; (vi) N_{n} ≡ 6 (mod 27) if, and only if, n = 22 · 3^{i} with i ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 1

with i_{1} − 1 > i_{2} ≥ 2, or n = 4 · 3^{i_{1}} + 3^{i_{2}} with i_{1} − 1 > i_{2} ≥ 1, or n = 3^{i_{1}} + 4 · 3^{i_{2}} with i_{1} − 2 > i_{2} ≥ 1, or n = 2 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} with i_{1} − 2 > i_{2} − 1 > i_{3} ≥ 0, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} with i_{1} − 1 > i_{2} − 1 > i_{3} ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} with i_{1} − 1 > i_{2} > i_{3} ≥ 0;

(vii) N_{n} ≡ 9 (mod 27) if, and only if, n = 2 · 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or n = 2 · 3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 2 · 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or n = 2 · 3^{i_{1}} + 2 · 3^{i_{2}} + 2 · 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 0,

or n = 2 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 0, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 0, or n = 3^{i_{1}} +3^{i_{2}} +2·3^{i_{3}} +3^{i_{4}} +3^{i_{5}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 0, or n = 3^{i_{1}} +3^{i_{2}} + 3^{i_{3}} +2·3^{i_{4}} +3^{i_{5}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 0, or n = 3^{i_{1}} +3^{i_{2}} +3^{i_{3}} +3^{i_{4}} +2·3^{i_{5}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 0; (viii) N_{n} ≡ 11 (mod 27) if, and only if, n = 3^{i} + 1 with i ≥ 3; (ix) N_{n} ≡ 12 (mod 27) if, and only if, n = 7; or n = 40 · 3^{i} with i ≥ 0, or

n = 2 · 3^{i_{1}} + 3^{i_{2}} + 1 with i_{1} − 1 > i_{2} ≥ 1, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 1 with i_{1} − 1 > i_{2} ≥ 1, or n = 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} with i_{1} − 3 > i_{2} − 2 > i_{3} − 1 > i_{4} ≥ 0;

(x) N_{n} ≡ 13 (mod 27) if, and only if, n = 3^{i} with i ≥ 2; (xi) N_{n} ≡ 15 (mod 27) if, and only if, n = 3^{i} + 4 with i ≥ 3, or n = 4 · 3^{i} + 1 with

i ≥ 2, or n = 13 · 3^{i} with i ≥ 1, or n = 4 · 3^{i_{1}} + 2 · 3^{i_{2}} with i_{1} − 1 > i_{2} ≥ 0, or n = 2 · 3^{i_{1}} + 4 · 3^{i_{2}} with i_{1} − 2 > i_{2} ≥ 0;

(xii) N_{n} ≡ 18 (mod 27) if, and only if, n = 2 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}} +3^{i_{2}} +2·3^{i_{3}} +3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}} +3^{i_{2}} +3^{i_{3}} +2·3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 2 · 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 2 · 3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} + 3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 2·3^{i_{1}}+3^{i_{2}}+3^{i_{3}}+2·3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}}+2·3^{i_{2}}+2·3^{i_{3}}+3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 2 · 3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} + 2 · 3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} + 3^{i_{6}} with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} > i_{6} ≥ 0;

(xiii) N_{n} ≡ 20 (mod 27) if, and only if, n = 10, or n = 3^{i_{1}} + 3^{i_{2}} with i_{1} − 2 > i_{2} ≥ 1; (xiv) N_{n} ≡ 21 (mod 27) if, and only if, n = 7 · 3^{i} with i ≥ 1, or n = 4 · 3^{i_{1}} + 4 · 3^{i_{2}}

with i_{1} −2 > i_{2} ≥ 0, or n = 13·3^{i_{1}} +3^{i_{2}} with i_{1} −1 > i_{2} ≥ 0, or n = 3^{i_{1}} +13·3^{i_{2}} with i_{1} − 3 > i_{2} ≥ 0;

(xv) N_{n} ≡ 23 (mod 27) if, and only if, n = 4; (xvi) N_{n} ≡ 24 (mod 27) if, and only if, n = 13, or n = 16 · 3^{i} with i ≥ 0, or

n = 7 · 3^{i_{1}} + 3^{i_{2}} with i_{1} − 1 > i_{2} ≥ 0; (xvii) in the cases not covered by items (i)–(xvi), N_{n} is divisible by 27; in particular,

N_{n} ≢ 7, 8, 10, 14, 16, 17, 19, 22, 25, 26 (mod 27) for all n.

Proof. We convert the right-hand side of (5.8) into a linear combination of series H_{a_{1},a_{2},...,a_{r}}(z) with all a_{i}’s relatively prime to p, by means of Equation (3.1) and Proposition 9. The result is

∑_{n≥1} N_{n} z^{n} = 9z^{2} + 15z + (18z + 13)H_{1}(z) + (18z + 1)H_{2}(z) + (9z + 20)H_{1,1}(z)

+ 12H_{2,1}(z) + 12H_{1,2}(z) + 24H_{1,1,1}(z) + 12H_{4}(z) + 3H_{2,2}(z)

+ 6H_{2,1,1}(z) + 6H_{1,2,1}(z) + 6H_{1,1,2}(z) + 12H_{1,1,1,1}(z) + 9H_{4,1}(z) + 9H_{1,4}(z) + 9H_{2,2,1}(z) + 9H_{2,1,2}(z) + 9H_{1,2,2}(z) + 18H_{2,1,1,1}(z) + 18H_{1,2,1,1}(z) + 18H_{1,1,2,1}(z) + 18H_{1,1,1,2}(z) + 9H_{1,1,1,1,1}(z) + 9H_{4,2}(z) + 9H_{2,4}(z)

+ 18H_{4,1,1}(z) + 18H_{1,4,1}(z) + 18H_{1,1,4}(z) + 9H_{2,2,2}(z) + 18H_{2,2,1,1}(z) + 18H_{2,1,2,1}(z) + 18H_{2,1,1,2}(z) + 18H_{1,2,2,1}(z) + 18H_{1,2,1,2}(z) + 18H_{1,1,2,2}(z)

+ 9H_{2,1,1,1,1}(z) + 9H_{1,2,1,1,1}(z) + 9H_{1,1,2,1,1}(z)

+ 9H_{1,1,1,2,1}(z) + 9H_{1,1,1,1,2}(z) + 18H_{1,1,1,1,1,1}(z) modulo 27.

Coefficient extraction following the algorithm described in Remark 8 then yields the claimed congruences. □

Considered modulo 9, the above corollary reduces to the following.

Corollary 14. The numbers N_{n} of connected non-crossing graphs obey the following congruences modulo 9:

(i) N_{n} ≡ 1 (mod 9) if, and only if, n = 1, or n = 2 · 3^{i} with i ≥ 0; (ii) N_{n} ≡ 2 (mod 9) if, and only if, n = 3^{i_{1}} + 3^{i_{2}} with i_{1} − 1 > i_{2} ≥ 0; (iii) N_{n} ≡ 3 (mod 9) if, and only if, n = 2·3^{i_{1}}+3^{i_{2}} with i_{1} > i_{2} ≥ 0, or n = 3^{i_{1}}+2·3^{i_{2}}

with i_{1} > i_{2} ≥ 0, or n = 2·3^{i_{1}} +2·3^{i_{2}} with i_{1} > i_{2} ≥ 0, or n = 3^{i_{1}} +3^{i_{2}} +3^{i_{3}} +3^{i_{4}} with i_{1} > i_{2} > i_{3} > i_{4} ≥ 0;

(iv) N_{n} ≡ 4 (mod 9) if, and only if, n = 3^{i} with i ≥ 0;

(v) N_{n} ≡ 5 (mod 9) if, and only if, n = 4 · 3^{i} with i ≥ 0; (vi) N_{n} ≡ 6 (mod 9) if, and only if, n = 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or

n = 2 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or n = 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0, or n = 3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} with i_{1} > i_{2} > i_{3} ≥ 0;

(vi) in the cases not covered by items (i)–(vii), N_{n} is divisible by 9; in particular, N_{n} ≢ 7, 8 (mod 9) for all n.

Remark. In the first proof of the conjecture (5.9) in [7], Eu, Liu and Yeh worked from the sum expression

N_{n} = \frac{1}{n − 1} ∑_{i=n−2}^{2n−4} \binom{3n − 3}{n + i + 1}\binom{i}{n − 2}

which is provided in [8, Theorem 2]. In order to achieve the proof, they considered four auxiliary sums of very similar nature, called there f_{i}(n), i = 1, 2, 3, 4, of which they determined their behaviour modulo 3. These sums, and the numbers N_{n} of connected non-crossing graphs, are reconsidered by Gessel in [9], who provides simpler proofs of the congruences modulo 3 established in [7], and also closed form expressions for the sums f_{i}(n), i = 1, 2, 3, 4. Gessel adds another sum, called f_{5}(n), of which he also determines its behaviour modulo 3.

All these sums can be treated in the same way as the numbers N_{n} in Theorems 11, 12, and Corollaries 13, 14, as we are going to explain now. In particular, in this way the behaviour of any of f_{i}(n), i = 1, 2, 3, 4, 5, modulo any power of 3 can be determined.

The general family of sums introduced by Gessel in [9] is

g_{j,k,l}(n) = ∑_{i=n−l}^{2n+j−k} \binom{3n + j}{n + i + k}\binom{i}{n − l},

of which the sums f_{i}(n), i = 1, 2, 3, 4, 5, are the cases (j, k, l) = (1, 1, 0), (0, 1, 0), (0, 0, 0), (−1, 1, 1), (0, 1, 1), in this order. Gessel [9, Sec. 3] proves that the generating function

G_{j,k,l}(z) = ∑_{n=k−j−l}^{∞} g_{j,k,l}(n)z^{n}

for these sums is given by

G_{j,k,l}(z) = \frac{(1 − 2α(z))^{l} α^{k−j−l}(z)}{(1 − 6α(z) + 6α^{2}(z)) (1 − α(z))^{k−1}} ,

where α(z) is the compositional inverse of z(1 − z)(1 − 2z). The series α(z) thus being algebraic of degree 3, also all series G_{j,k,l}(z) are algebraic of degree 3. Below we list the algebraic equations satisfied by the generating functions for f_{i}(n), i = 1, 2, 3, 4, 5, and in each case we provide the base solution F_{1}(z) for the modulus 3^{3^{α}} (cf. (4.3) with p = 3) for starting our method described in Section 4. The iterative steps carry through as well, as in the proof of Theorem 11. We leave the details to the reader.

The generating function for the numbers f_{1}(n) satisfies the equation

(1 − 108z^{2})G_{1,1,0}^{3}(z) − 3G_{1,1,0}(z) + 2 = 0.  (5.10)

A base solution for the modulus 3^{3^{α}} is F_{1}(z) = 1. The generating function for the numbers f_{2}(n) satisfies the equation

(1 − 108z^{2})G_{0,1,0}^{3}(z) − (1 + 9z)G_{0,1,0}(z) + z = 0,  (5.11)

and a base solution is F_{1}(z) = Φ^{3^{α}}(z) + s_{α}(z). Next, the generating function for the numbers f_{3}(n) satisfies the equation

(1 − 108z^{2})G_{0,0,0}^{3}(z) − (1 + 9z)G_{0,0,0}(z) − z = 0.  (5.12)

Here, a base solution is F_{1}(z) = −Φ^{3^{α}}(z) − s_{α}(z) + 1. The generating function for the numbers f_{4}(n) satisfies the equation

(1 − 108z^{2})G_{−1,1,1}^{3}(z) + (1 − 108z^{2})G_{−1,1,1}^{2}(z) + 3z(1 − 12z)G_{−1,1,1}(z) − 4z^{2} = 0. (5.13)

Since, modulo 3, this is the same equation as (5.2), this generating function has the same base solution as N(z), namely the one given by (5.4). Finally, the generating function for the numbers f_{5}(n) satisfies the equation

(1 − 108z^{2})G_{0,1,1}^{3}(z) − G_{0,1,1}(z) − 8z = 0.  (5.14)

Since, modulo 3, this is the same equation as (5.11), (essentially) the same base solution (the difference occurring in the constant term), namely F_{1}(z) = Φ^{3^{α}}(z) + s_{α}(z) + 1, applies.

6. The number of Kreweras walks modulo 3-powers

The subject of this section are congruences modulo powers of 3 for the numbers of so-called “Kreweras walks.” In his thesis [14], Kreweras had considered (among many other things) a three-candidate ballot problem, where each of the three candidates, A, B, C, say, receives n votes. The problem which is posed is how many ways there are to count the votes so that at each point in time candidate A has at least as many votes as the number of votes for each of the other candidates. It is not difficult to see that this problem can be translated into the following problem of counting walks in the quarter plane: how many lattice walks in the plane from the origin to itself are there which consist of 3n steps from the set {(1, 1), (−1, 0), (0, −1)} and stay in the non-negative quadrant? Let K_{n} denote the number of these walks. By definition, we set K_{0} = 1. Kreweras [14] proved that

K_{n} = \frac{4^{n}}{(n + 1)(2n + 1)}\binom{3n}{n};  (6.1)

see also [16]. To prove this formula turned out to be highly non-trivial, as well as the enumerative analysis of the more general question of how many walks there are which end at an arbitrary point in the non-negative quadrant. Kreweras [14] and Niederhausen [16] obtained partial results in this direction. Finally, Bousquet-Mélou [2] succeeded to compute the complete generating function for these numbers of walks.

Let K(z) := ∑_{n≥0} K_{n} z^{n} be the generating function for the “Kreweras numbers” in (6.1). From [2, Theorem 1], it can be derived that

64z^{2} K^{3}(z) + 16z K^{2}(z) − (72z − 1) K(z) + 54z − 1 = 0.  (6.2)

Clearly, this equation determines K(z) uniquely as a formal power series over ℤ, and as well modulo any power of 3.

Theorem 15. Let Φ(z) = ∑_{n≥0} z^{3^{n}}, and let α be a non-negative integer. Then the generating function K(z), when reduced modulo 3^{3^{α}}, can be expressed as a polynomial in Φ(z^{1/2}) of degree at most 3^{α+1} − 1, with coefficients that are Laurent polynomials in z^{1/2} over the integers.

Proof. We apply the method from Section 4. We start by substituting the Ansatz (4.3) with z replaced by z^{1/2} in (6.2) and reducing the result modulo 3. In this way, we obtain

z^{2} ∑_{i=0}^{3^{α+1}−1} a_{i,1}^{3}(z^{1/2})Φ^{3i}(z^{1/2}) + z ∑_{i=0}^{3^{α+1}−1} a_{i,1}^{2}(z^{1/2})Φ^{2i}(z^{1/2})

− z ∑_{0≤i<j≤3^{α+1}−1} a_{i,1}(z^{1/2})a_{j,1}(z^{1/2})Φ^{i+j}(z^{1/2})

+ ∑_{i=0}^{3^{α+1}−1} a_{i,1}(z^{1/2})Φ^{i}(z^{1/2}) − 1 = 0 modulo 3. (6.3)

We claim that the following choices solve the above congruence:

a_{0,1}(z^{1/2}) = z^{−1}s_{α}^{2}(z^{1/2}) modulo 3,
a_{3^{α},1}(z^{1/2}) = −z^{−1}s_{α}(z^{1/2}) modulo 3,
a_{2·3^{α},1}(z^{1/2}) = z^{−1} modulo 3,

where s_{α}(z) is the same polynomial as in Section 5, with all other a_{i,1}(z^{1/2}) vanishing. In order to verify the claim, we substitute our choices in (6.3). For the left-hand side, we obtain

z^{2} (z^{−3}Φ^{2·3^{α+1}}(z^{1/2}) − z^{−3}s_{α}^{3}(z^{1/2})Φ^{3^{α+1}}(z^{1/2}) + z^{−3}s_{α}^{6}(z^{1/2}))

+ z (z^{−2}Φ^{4·3^{α}}(z^{1/2}) + z^{−2}s_{α}^{2}(z^{1/2})Φ^{2·3^{α}}(z^{1/2}) + z^{−2}s_{α}^{4}(z^{1/2}))

− z (−z^{−2}s_{α}(z^{1/2})Φ^{3^{α+1}}(z^{1/2}) + z^{−2}s_{α}^{2}(z^{1/2})Φ^{2·3^{α}}(z^{1/2}) − z^{−2}s_{α}^{3}(z^{1/2})Φ^{3^{α}}(z^{1/2}))

+ z^{−1}Φ^{2·3^{α}}(z^{1/2}) − z^{−1}s_{α}(z^{1/2})Φ^{3^{α}}(z^{1/2}) + z^{−1}s_{α}^{2}(z^{1/2}) − 1 modulo 3.

Using the relation (4.5) with p = 3 and z replaced by z^{1/2}, and reducing the obtained expression modulo 3, we arrive at

(z^{−1}Φ^{2·3^{α}}(z^{1/2}) + Φ^{3^{α}}(z^{1/2})z^{3^{α}/2−1} + z^{3^{α}−1})

− (z^{−1}s_{α}^{3}(z^{1/2})Φ^{3^{α}}(z^{1/2}) − z^{3^{α}/2−1}s_{α}^{3}(z^{1/2})) + z^{−1}s_{α}^{6}(z^{1/2})

+ (z^{−1}Φ^{2·3^{α}}(z^{1/2}) − z^{3^{α}/2−1}Φ^{3^{α}}(z^{1/2})) + z^{−1}s_{α}^{2}(z^{1/2})Φ^{2·3^{α}}(z^{1/2}) + z^{−1}s_{α}^{4}(z^{1/2})

+ (z^{−1}s_{α}(z^{1/2})Φ^{3^{α}}(z^{1/2}) − z^{3^{α}/2−1}s_{α}(z^{1/2}))
− z^{−1}s_{α}^{2}(z^{1/2})Φ^{2·3^{α}}(z^{1/2}) + z^{−1}s_{α}^{3}(z^{1/2})Φ^{3^{α}}(z^{1/2})

+ z^{−1}Φ^{2·3^{α}}(z^{1/2}) − z^{−1}s_{α}(z^{1/2})Φ^{3^{α}}(z^{1/2}) + z^{−1}s_{α}^{2}(z^{1/2}) − 1 modulo 3.

By collecting terms, this expression simplifies to

z^{3^{α}−1} + z^{3^{α}/2−1}s_{α}^{3}(z^{1/2}) + z^{−1}s_{α}^{6}(z^{1/2}) + z^{−1}s_{α}^{4}(z^{1/2})

− z^{3^{α}/2−1}s_{α}(z^{1/2}) + z^{−1}s_{α}^{2}(z^{1/2}) − 1 modulo 3.

By repeatedly using the relation (5.5) with z replaced by z^{1/2}, this expression can be turned into

z^{3^{α}−1} + z^{3^{α}/2−1} (s_{α}(z^{1/2}) + z^{3^{α}/2} − z^{1/2}) + z^{−1} (s_{α}(z^{1/2}) + z^{3^{α}/2} − z^{1/2})^{2}

+z^{−1}s_{α}(z^{1/2}) (s_{α}(z^{1/2}) + z^{3^{α}/2} − z^{1/2})−z^{3^{α}/2−1}s_{α}(z^{1/2})+z^{−1}s_{α}^{2}(z^{1/2})−1 modulo 3.

After expansion and reduction modulo 3, one sees that this expression reduces to zero.

After we have completed the “base step,” we now proceed with the iterative steps described in Section 4. We consider the Ansatz (4.6)–(4.8) with z replaced by z^{1/2}, where the coefficients a_{i,β}(z^{1/2}) are supposed to provide a solution

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

to (5.2) modulo 3^{β}. This Ansatz, substituted in (5.2), produces the congruence

− 3^{β}z ∑_{j=0}^{3^{α+1}−1} ∑_{i=0}^{3^{α+1}−1} a_{j,β}(z^{1/2})b_{i,β+1}(z^{1/2})Φ^{i+j}(z^{1/2}) + 3^{β} ∑_{i=0}^{3^{α+1}−1} b_{i,β+1}(z^{1/2})Φ^{i}(z^{1/2})

+ 64z^{2}F_{β}^{3}(z) + 16zF_{β}^{2}(z) − (72z − 1)F_{β}(z) + 54z − 1 = 0 modulo 3^{β+1}. (6.4)

Since the sum has the prefactor 3^{β}, we may reduce the a_{i,β}(z^{1/2}) modulo 3. By construction, we have

a_{0,β}(z^{1/2}) = a_{0,1}(z^{1/2}) = z^{−1}s_{α}^{2}(z^{1/2}) modulo 3,
a_{3^{α},β}(z^{1/2}) = a_{3^{α},1}(z^{1/2}) = −z^{−1}s_{α}(z^{1/2}) modulo 3,
a_{2·3^{α},β}(z^{1/2}) = a_{2·3^{α},1}(z^{1/2}) = z^{−1} modulo 3,

and a_{i,β} = 0 modulo 3 for all other i’s. If we substitute this in (6.4) and subsequently use (4.5) with p = 3 and z replaced by z^{1/2} to reduce high powers of Φ(z^{1/2}), we obtain

− 3^{β} ∑_{i=0}^{3^{α+1}−1} s_{α}^{2}(z^{1/2})b_{i,β+1}(z^{1/2})Φ^{i}(z^{1/2}) + 3^{β} ∑_{i=0}^{3^{α+1}−1} s_{α}(z^{1/2})b_{i,β+1}(z^{1/2})Φ^{i+3^{α}}(z^{1/2})

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

+ 64z^{2}F_{β}^{3}(z) + 16zF_{β}^{2}(z) − (72z − 1)F_{β}(z) + 54z − 1

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

−z^{3^{α}/2}b_{i+3^{α},β+1}(z^{1/2}) − b_{i,β+1}(z^{1/2})) Φ^{i}(z^{1/2})

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

−s_{α}(z^{1/2})b_{i+3^{α},β+1}(z^{1/2}) − z^{3^{α}/2}b_{i+3^{α},β+1}(z^{1/2})) Φ^{i}(z^{1/2})

− 3^{β} ∑_{i=2·3^{α}}^{3^{α+1}−1} (s_{α}^{2}(z^{1/2})b_{i,β+1}(z^{1/2}) − s_{α}(z^{1/2})b_{i−3^{α},β+1}(z^{1/2}) + b_{i−2·3^{α},β+1}(z^{1/2})) Φ^{i}(z^{1/2})

+ 64z^{2}F_{β}^{3}(z) + 16zF_{β}^{2}(z) − (72z − 1)F_{β}(z) + 54z − 1 = 0 modulo 3^{β+1}.

By our assumption on F_{β}(z), we may divide by 3^{β}. Comparison of powers of Φ(z^{1/2}) then yields a system of congruences of the form

M · b = c modulo 3,  (6.5)

where b is the column vector of unknowns (b_{i,β+1}(z^{1/2}))_{i=0,1,...,3^{α+1}−1}, c is a (known) column vector of Laurent polynomials in z, and M is the matrix

(\begin{matrix}D (s_{α}^{2}(z^{1/2}) − 1) & D (−z^{3^{α}/2}) & D (z^{3^{α}/2}s_{α}(z^{1/2})) \\ D (−s_{α}(z^{1/2})) & D (s_{α}^{2}(z^{1/2})) & D (−s_{α}(z^{1/2}) − z^{3^{α}/2}) \\ D(1) & D (−s_{α}(z^{1/2})) & D (s_{α}^{2}(z^{1/2})) \end{matrix}) ,

with D(x) denoting the 3^{α} × 3^{α} diagonal matrix whose diagonal entries equal x, as before. In the same manner as in the proof of Theorem 11, on sees that

det(M) = z^{3^{α}} modulo 3.

As a consequence, the system (6.5) is (uniquely) solvable. Thus, we have proved that, for an arbitrary non-negative integer α, the algorithm of Section 4 will produce a solution F_{3^{α}}(z) to (5.2) modulo 3^{3^{α}} which is a polynomial in Φ(z^{1/2}) with coefficients that are Laurent polynomials in z. □

We have implemented this algorithm. As an illustration, the next theorem contains the result for the modulus 27.

Theorem 16. Let Φ(z) = ∑_{n≥0} z^{3^{n}}. Then we have

∑_{n≥0} K_{n} z^{n} = 1 + 12Φ^{2}(z^{1/2}) + 11z^{−1/2}Φ^{3}(z^{1/2}) + 6z^{−1}Φ^{4}(z^{1/2}) + 15z^{−1/2}Φ^{5}(z^{1/2})

+ z^{−1}Φ^{6}(z^{1/2}) + 3z^{−1}Φ^{8}(z^{1/2}) modulo 27. (6.6)

Corollary 17. The numbers K_{n} of Kreweras walks obey the following congruences modulo 27:

(i) K_{n} ≡ 1 (mod 27) if, and only if, n = 0; (ii) K_{n} ≡ 2 (mod 27) if, and only if, n = 1; (iii) K_{n} ≡ 3 (mod 27) if, and only if, n = 3^{i} with i ≥ 1, or n = \frac{1}{2}(13 · 3^{i} − 1) with

i ≥ 2, or n = \frac{1}{2}(3^{i} +11) with i ≥ 4, or n = 2·3^{i} +1 with i ≥ 3, or n = 20·3^{i} −1 with i ≥ 1, or n = \frac{1}{2}(3^{i_{1}} +3^{i_{2}} +3^{i_{3}} +3^{i_{4}} −2) with i_{1}−3 > i_{2}−2 > i_{3}−1 > i_{4} ≥ 1;

(iv) K_{n} ≡ 5 (mod 27) if, and only if, n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} − 2) with i_{1} − 2 > i_{2} ≥ 2;

(v) K_{n} ≡ 6 (mod 27) if, and only if, n = 3^{i} + 1 with i ≥ 3, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}}) with i_{1} − 2 > i_{2} ≥ 1, or n = \frac{1}{2}(7 · 3^{i_{1}} + 3^{i_{2}} − 2) with i_{1} − 1 > i_{2} ≥ 1; or n = \frac{1}{2}(3^{i_{1}} + 7 · 3^{i_{2}} − 2) with i_{1} − 1 > i_{2} ≥ 1;

(vi) K_{n} ≡ 7 (mod 27) if, and only if, n = 3^{i} − 1 with i ≥ 2; (vii) K_{n} ≡ 8 (mod 27) if, and only if, n = 4, or n = 2 · 3^{i} − 1 with i ≥ 2; (viii) K_{n} ≡ 9 (mod 27) if, and only if, n = 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} − 1 with i_{1} > i_{2} > i_{3} ≥ 1,

or n = \frac{1}{2}(2 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 2 · 3^{i_{4}} + 3^{i_{5}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 2 · 3^{i_{5}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} ≥ 1;

(ix) K_{n} ≡ 12 (mod 27) if, and only if, n = \frac{1}{2}(4 · 3^{i_{1}} + 3^{i_{2}} − 1) with i_{1} − 1 > i_{2} ≥ 2, or n = \frac{1}{2}(3^{i_{1}} + 4 · 3^{i_{2}} − 1) with i_{1} − 2 > i_{2} ≥ 2, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 2) with i_{1} − 2 > i_{2} ≥ 3, or n = \frac{1}{2}(13 · 3^{i_{1}} + 3^{i_{2}} − 2) with i_{1} − 1 > i_{2} ≥ 1, or n = 2 · 3^{i_{1}} + 2 · 3^{i_{2}} − 1 with i_{1} − 2 > i_{2} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 13 · 3^{i_{2}} − 2) with i_{1} − 3 > i_{2} ≥ 1;

(x) K_{n} ≡ 14 (mod 27) if, and only if, n = \frac{1}{2}(3^{i} + 1) with i ≥ 4, or n = 5 · 3^{i} − 1 with i ≥ 2;

(xi) K_{n} ≡ 15 (mod 27) if, and only if, n = \frac{1}{2}(7 · 3^{i} − 1) with i ≥ 2, or n = \frac{1}{2}(3^{i} + 5) with i ≥ 2, or n = 2 · 3^{i} with i ≥ 1, or n = 11 · 3^{i} − 1 with i ≥ 1, or n = \frac{1}{2}(2·3^{i_{1}}+3^{i_{2}}+3^{i_{3}}−2) with i_{1}−2 > i_{2}−1 > i_{3} ≥ 1, or n = \frac{1}{2}(3^{i_{1}}+2·3^{i_{2}}+3^{i_{3}}−2) with i_{1} − 1 > i_{2} − 1 > i_{3} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} − 2) with i_{1} − 1 > i_{2} > i_{3} ≥ 1;

(xii) K_{n} ≡ 16 (mod 27) if, and only if, n = 2; (xiii) K_{n} ≡ 17 (mod 27) if, and only if, n = 5; (xiv) K_{n} ≡ 18 (mod 27) if, and only if, or n = \frac{1}{2}(2 · 3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} − 2)

with i_{1} > i_{2} > i_{3} > i_{4} ≥ 1, or n = \frac{1}{2}(2 · 3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} + 3^{i_{4}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} ≥ 1, or n = \frac{1}{2}(2 · 3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 2 · 3^{i_{4}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 2 · 3^{i_{2}} + 2 · 3^{i_{3}} + 3^{i_{4}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 2 · 3^{i_{2}} + 3^{i_{3}} + 2 · 3^{i_{4}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 2 · 3^{i_{3}} + 2 · 3^{i_{4}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 3^{i_{3}} + 3^{i_{4}} + 3^{i_{5}} + 3^{i_{6}} − 2) with i_{1} > i_{2} > i_{3} > i_{4} > i_{5} > i_{6} ≥ 1; (xv) K_{n} ≡ 21 (mod 27) if, and only if, n = 19, or n = 3^{i_{1}}+3^{i_{2}}−1 with i_{1} > i_{2} ≥ 1, or

n = \frac{1}{2}(3^{i_{1}}+3^{i_{2}}+3^{i_{3}}−1) with i_{1}−2 > i_{2}−1 > i_{3} ≥ 2, or n = \frac{1}{2}(4·3^{i_{1}}+3^{i_{2}}+3^{i_{3}}−2) with i_{1} − 2 > i_{2} − 1 > i_{3} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 4 · 3^{i_{2}} + 3^{i_{3}} − 2) with i_{1} − 3 > i_{2} − 1 > i_{3} ≥ 1, or n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} + 4 · 3^{i_{3}} − 2) with i_{1} − 3 > i_{2} − 2 > i_{3} ≥ 1;

(xvi) K_{n} ≡ 23 (mod 27) if, and only if, n = 14; (xvii) K_{n} ≡ 24 (mod 27) if, and only if, n = 10, or n = \frac{1}{2}(2 · 3^{i_{1}} + 3^{i_{2}} − 1) with

i_{1} −1 > i_{2} ≥ 2, or n = \frac{1}{2}(3^{i_{1}} +2·3^{i_{2}} −1) with i_{1} > i_{2} ≥ 2, or n = 3^{i_{1}} +2·3^{i_{2}} −1 with i_{1} − 2 > i_{2} ≥ 1, or n = 2 · 3^{i_{1}} + 3^{i_{2}} − 1 with i_{1} > i_{2} ≥ 1;

(xviii) K_{n} ≡ 26 (mod 27) if, and only if, n = \frac{1}{2}(3^{i} − 1) with i ≥ 3; (xix) in the cases not covered by items (i)–(xvii), K_{n} is divisible by 27; in particular,

K_{n} ≢ 4, 10, 11, 13, 19, 20, 22, 25 (mod 27) for all n.

Proof. By means of Equation (3.1) and Proposition 9, we convert the right-hand side of (6.6) into a linear combination of series H_{a_{1},a_{2},...,a_{r}}(z^{1/2}) with all a_{i}’s relatively prime to p. The result is

∑_{n≥0} K_{n} z^{n} = 21z^{−1/2}H_{1}(z^{1/2}) + 7z^{−1}H_{2}(z^{1/2}) + 5z^{−1}H_{1,1}(z^{1/2})

+ 9z^{−1/2}H_{2,1}(z^{1/2}) + 9z^{−1/2}H_{1,2}(z^{1/2}) + 18z^{−1/2}H_{1,1,1}(z^{1/2})
+ 3z^{−1}H_{4}(z^{1/2}) + 21z^{−1}H_{2,2}(z^{1/2}) + 15z^{−1}H_{2,1,1}(z^{1/2})
+ 15z^{−1}H_{1,2,1}(z^{1/2}) + 15z^{−1}H_{1,1,2}(z^{1/2}) + 3z^{−1}H_{1,1,1,1}(z^{1/2})
+ 9z^{−1}H_{4,2}(z^{1/2}) + 9z^{−1}H_{2,4}(z^{1/2}) + 18z^{−1}H_{4,1,1}(z^{1/2}) + 18z^{−1}H_{1,4,1}(z^{1/2})
+ 18z^{−1}H_{1,1,4}(z^{1/2}) + 9z^{−1}H_{2,2,2}(z^{1/2}) + 18z^{−1}H_{2,2,1,1}(z^{1/2})
+ 18z^{−1}H_{2,1,2,1}(z^{1/2}) + 18z^{−1}H_{2,1,1,2}(z^{1/2}) + 18z^{−1}H_{1,2,2,1}(z^{1/2})
+ 18z^{−1}H_{1,2,1,2}(z^{1/2}) + 18z^{−1}H_{1,1,2,2}(z^{1/2}) + 9z^{−1}H_{2,1,1,1,1}(z^{1/2})
+ 9z^{−1}H_{1,2,1,1,1}(z^{1/2}) + 9z^{−1}H_{1,1,2,1,1}(z^{1/2}) + 9z^{−1}H_{1,1,1,2,1}(z^{1/2})

+ 9z^{−1}H_{1,1,1,1,2}(z^{1/2}) + 18z^{−1}H_{1,1,1,1,1,1}(z^{1/2}) modulo 27.

Coefficient extraction following the algorithm described in Remark 8 then yields the claimed congruences. □

If we restrict Corollary 17 to modulus 3, then it reduces to the following simple assertion.

Corollary 18. The number K_{n} of Kreweras walks of length 3n is congruent to 1 modulo 3 if, and only if, n = 3^{i} − 1 with i ≥ 1, it is congruent to 2 modulo 3 if, and only if, n = \frac{1}{2}(3^{i_{1}} + 3^{i_{2}} − 2) with i_{1} > i_{2} ≥ 0, and it is divisible by 3 in all other cases.

7. Fuß–Catalan numbers modulo p-powers

In this section, given a positive integer h and a prime number p, we determine the behaviour of the Fuß–Catalan numbers

F (n; k) := \frac{1}{n}\binom{kn}{n − 1}  (7.1)

modulo powers of p, provided k is itself a power of p, say, k = p^{h}.^{3} These numbers have numerous combinatorial interpretations; cf. [1, pp. 59–60].

By using the Lagrange inversion formula (see [20, Theorem 5.4.2]), it is easy to see that the generating function f_{p;h}(z) = 1 + ∑_{n≥1} \frac{1}{n} \binom{p^{h}n}{n−1}z^{n} satisfies the functional equation

zf_{p;h}^{p^{h}}(z) − f_{p;h}(z) + 1 = 0.  (7.2)

It is straightforward to verify that this equation has a unique formal power series solution over ℤ, and as well over any power of p.

In order to determine the coefficients of f_{p;h}(z) modulo powers of p, we have to use a variant of the series Φ(z) defined in (1.1), namely

Φ_{p;h}(z) = ∑_{n≥0} z^{p^{nh}/(p^{h}−1)}.  (7.3)

The theorem below generalises Theorem 33 in [12] to arbitrary prime numbers.

Theorem 19. For a prime number p and a positive integer h, let Φ_{p;h}(z) be the series defined in (7.3), and let α be a further positive integer. Then the generating function f_{p;h}(z), when reduced modulo p^{p^{α}}, can be expressed as a polynomial in Φ_{p;h}(z) of degree at most p^{(α+1)h} − 1, with coefficients that are Laurent polynomials in z^{1/(p^{h}−1)} over the integers.

Proof. For ease of notation, we replace z by z^{p^{h}−1} in (7.2), thereby obtaining the equation

z^{p^{h}−1}f̃_{p;h}^{p^{h}}(z) − f̃_{p;h}(z) + 1 = 0,  (7.4)

with f̃_{p;h}(z) = f_{p;h}(z^{p^{h}−1}). We now have to prove that, modulo p^{p^{αh}}, the series f̃_{p;h}(z) can be expressed as a polynomial in

Φ̃_{p;h}(z) = ∑_{n=0}^{∞} z^{p^{nh}}  (7.5)

of degree at most p^{(α+1)h} − 1, with coefficients that are Laurent polynomials in z. It is readily verified that

Φ̃_{p;h}^{p^{h}}(z) − Φ̃_{p;h}(z) + z = 0 modulo p,  (7.6)

whence

(Φ̃_{p;h}^{p^{h}}(z) − Φ̃_{p;h}(z) + z)^{p^{αh}} = 0 modulo p^{p^{αh}}.  (7.7)

We modify our Ansatz (4.2) to

f̃_{p;h}(z) = ∑_{i=0}^{p^{(α+1)h}−1} a_{i}(z)Φ̃_{p;h}^{i}(z) modulo p^{p^{αh}},  (7.8)

where the a_{i}(z)’s are (at this point) undetermined Laurent polynomials in z.

3In principle, one could use the generalisations of Lucas’ theorem due to Davis and Webb [4], and to Granville [10], respectively, to analyse the explicit expression for the Fuß–Catalan numbers modulo a given p-power. However, this approach would be rather cumbersome in comparison with our method, and it is doubtful that one would be able to derive a result on the same level of generality as Theorems 19, 20, or Corollaries 21, 22.

Next, we gradually find approximations a_{i,β}(z) to a_{i}(z) such that (7.4) holds modulo p^{β}, for β = 1, 2, …, p^{αh}. To start the procedure, we consider the functional equation (7.4) modulo p, with

f̃_{p;h}(z) = ∑_{i=0}^{p^{(α+1)h}−1} a_{i,1}(z)Φ̃_{p;h}^{i}(z) modulo p.  (7.9)

It is readily verified that the choice of

a_{0,1}(z) = ∑_{k=0}^{α−1} z^{p^{kh}−1},

a_{p^{αh},1}(z) = z^{−1},  (7.10)

with all other a_{i,1}(z)’s equal to zero indeed leads to a solution of (7.4) modulo p.

After we have completed the “base step,” we now proceed with the iterative steps described in Section 4. Our Ansatz here (replacing the corresponding one in (4.6)–(4.8)) is

f̃_{p;h}(z) = ∑_{i=0}^{p^{(α+1)h}−1} a_{i,β+1}(z)Φ̃_{p;h}^{i}(z) modulo p^{β+1},  (7.11)

with

a_{i,β+1}(z) := a_{i,β}(z) + p^{β}b_{i,β+1}(z), i = 0, 1, …, p^{(α+1)h} − 1,  (7.12)

where the coefficients a_{i,β}(z) are supposed to provide a solution

f̃_{β}(z) = ∑_{i=0}^{p^{(α+1)h}−1} a_{i,β}(z)Φ̃_{p;h}^{i}(z)

to (7.4) modulo p^{β}. This Ansatz, substituted in (7.4), produces the congruence

z^{p^{h}−1}f̃_{β}^{p^{h}}(z) − f̃_{β}(z) + p^{β} ∑_{i=0}^{p^{(α+1)h}−1} b_{i,β+1}(z)Φ̃_{p;h}^{i}(z) + 1 = 0 modulo p^{β+1}. (7.13)

By our assumption on f̃_{β}(z), we may divide by p^{β}. Comparison of powers of Φ̃_{p;h}(z) then yields a system of congruences of the form

b_{i,β+1}(z) + Pol_{i}(z) = 0 modulo p,  i = 0, 1, …, p^{(α+1)h} − 1,  (7.14)

where Pol_{i}(z), i = 0, 1, …, p^{(α+1)h} − 1, are certain Laurent polynomials with integer coefficients. This system being trivially uniquely solvable, we have proved that, for an arbitrary positive integer α, the modified algorithm that we have presented here will produce a solution f̃_{p^{αh}}(z) to (7.4) modulo p^{p^{αh}} which is a polynomial in Φ̃_{p;h}(z) with coefficients that are Laurent polynomials inz. □

It should be observed that the α = 0 case of the above proof (see in particular (7.10)) shows that F (n; p^{h}) ≡ 1 (mod p) for n = (p^{hi} − 1)/(p − 1), i = 0, 1, …, and F (n; p^{h}) ≡ 0 (mod p) otherwise.

We have implemented the algorithm contained in the above proof. As an illustration, we display below the result obtained for h = 1 and the modulus p^{2}. This result was first guessed from the automatically obtained results for p = 3, 5, 7, but, once found, it is easily verified directly by substitution in (7.2).

Theorem 20. Let Φ(z) = ∑_{n≥0} z^{p^{n}}. Then we have

∑_{n≥1} \frac{1}{n}\binom{pn}{n − 1} z^{n} = pΦ^{p−1}(z^{1/(p−1)}) − (p − 1)z^{−1/(p−1)}Φ^{p}(z^{1/(p−1)})

+ pz^{−1/(p−1)}Φ^{2p−1}(z^{1/(p−1)}) modulo p^{2}. (7.15)

(Human) inspection reveals that this expression can actually be drastically simplified.

Corollary 21. Let Φ(z) = ∑_{n≥0} z^{p^{n}}. Then we have

∑_{n≥1} \frac{1}{n}\binom{pn}{n − 1} z^{n} = z^{−1/(p−1)}Φ^{p}(z^{1/(p−1)})  modulo p^{2}.  (7.16)

Proof. One applies relation (4.4) with α = 0 and z replaced by z^{1/(p−1)} to the terms in (7.15) which have coefficient p. □

Explicitly, this leads to the following congruences modulo p^{2}.

Corollary 22. The Fuß–Catalan numbers F (n; p) = \frac{1}{n} \binom{pn}{n−1} obey the following congruences modulo p^{2}:

(i) If n = \frac{1}{p−1} (p^{i} − 1) with i ≥ 1, then F (n; p) ≡ 1 (mod p^{2}).

(ii) If

n = \frac{1}{p − 1} (a_{1}p^{i_{1}} + a_{2}p^{i_{2}} + ⋯ + a_{r}p^{i_{r}} − 1)

with all a_{i}’s relatively prime to p, a_{1} + a_{2} + ⋯ + a_{r} = p, r ≥ 2, and i_{1} > i_{2} >

⋯ > i_{r} ≥ 0, then we have

F (n; p) ≡ \frac{p!}{a_{1}! a_{2}! ⋯ a_{r}!} (mod p^{2}).

(iii) In the cases not covered by items (i) and (ii), the Fuß–Catalan number F (n; p) is divisible by p^{2}.

Proof. By means of Equation (3.1) and Proposition 9, we convert the right-hand side of (5.8) into a linear combination of series H_{a_{1},a_{2},...,a_{r}}(z^{1/(p−1)}), with all a_{i}’s relatively prime to p. The result is

∑_{n≥1} \frac{1}{n}\binom{pn}{n − 1} z^{n} = z^{−1/(p−1)}H_{1}(z^{1/(p−1)}) − 1

+ z^{−1/(p−1)} ∑_{r=1}^{p}_{∑_{a_{1},...,a_{r}≥1} ; a_{1}+···+a_{r}=p and r≥2} \frac{p!}{a_{1}! a_{2}! ⋯ a_{r}!}H_{a_{1},a_{2},...,a_{r}}(z^{1/(p−1)}) modulo p^{2}.

Coefficient extraction then leads to our claim. □

8. The number of blossom trees modulo p-powers

The combinatorial objects which we treat in this section are so-called “blossom trees.” These are a particular kind of trees which are of great significance in the combinatorial understanding of the enumeration of maps; see e.g. the survey [3]. The particular blossom trees that we are interested in are the ones in [18, Sec. 3]. Since the precise definition is slightly technical and not needed here, we omit it, and instead refer the reader to [18].

For an odd positive integer k, let B(n; k) be the number of blossom trees constructed from k-ary trees with n white nodes by adding a black node with k−1 buds on each inner edge. Let B_{k}(z) := \frac{k+1}{2} + ∑_{n≥1} B(n; k) z^{n} be the corresponding generating function. Schaeffer [18, Cor. 2] proved that

B(n; k) = \frac{k + 1}{n((k − 1)n + 2)}\binom{kn}{n − 1}.  (8.1)

As we show in the Appendix, the generating function B_{k}(z) satisfies the polynomial equation

z^{2}B_{k}^{k}(z) + ∑_{s=0}^{(k+1)/2}(−1)^{s} \frac{k + 1}{(k − s + 1)(k − s)}\binom{k − s + 1}{s}k^{k−2s+1} (\frac{k − 1}{2})^{s} zB_{k}^{s}(z)

− (−1)^{k} (\frac{k − 1}{2})^{k−1} B_{k}(z) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1} = 0. (8.2)

It is not difficult to see that (8.2) determines B_{k}(z) uniquely as a formal power series over ℤ, and as well over any power of a prime number p as long as k ≢ 1 (mod p).

From now on, let p be a fixed odd prime number.

Theorem 23. Let Φ(z) = ∑_{n≥0} z^{p^{n}}, and let α be a non-negative integer. Then the generating function B_{p}(z), when reduced modulo p^{p^{α}}, can be expressed as a polynomial in Φ (z^{1/(p−1)}) of degree at most p^{α+1} − 1, with coefficients that are Laurent polynomials in z^{1/(p−1)} over the integers.

Proof. Again, we apply the method from Section 4. To begin with, we need a “base solution”

F_{1}(z) = ∑_{i=0}^{p^{α+1}−1} a_{i,1}(z)Φ^{i}(z^{1/(p−1)})  (8.3)

to (8.2) modulo p. At this point, it is useful to observe that, using Fermat’s little theorem, the functional equation (8.2), when taken modulo p, reduces to

z^{2}B_{p}^{p}(z) − 2^{(p+1)/2}zB_{p}^{(p+1)/2}(z) + B_{p}(z) − 2^{−1} = 0 modulo p,  (8.4)

where here, and in the following, 2^{−1} denotes the inverse of 2 modulo p. We claim that the following choices in (8.3) solve the above congruence:

a_{0,1}(z) = 2^{−1}z^{−2/(p−1)}s_{α}^{2}(z^{1/(p−1)}) modulo p,
a_{p^{α},1}(z) = z^{−2/(p−1)}s_{α}(z^{1/(p−1)}) modulo p,
a_{2·p^{α},1}(z) = 2^{−1}z^{−2/(p−1)} modulo p,

where s_{α}(z) = ∑_{k=0}^{α−1} z^{p^{k}}, with all other a_{i,1}(z) vanishing. In order to verify this claim, we first observe that, with the above choices, F_{1}(z) can be expressed as a square, namely

F_{1}(z) = 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2} .

We substitute this in (8.4). For the left-hand side, we obtain

2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2p}

− z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{p+1}

+ 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2} − 2^{−1} modulo p.

Using the relation (4.5) with z replaced by z^{1/(p−1)} and reducing the obtained expression modulo p, we arrive at

2^{−1}z^{−2/(p−1)} (Φ^{p^{α+1}}(z^{1/(p−1)}) + s_{α}^{p}(z^{1/(p−1)}))^{2}

− z^{−2/(p−1)} (Φ^{p^{α+1}}(z^{1/(p−1)}) + s_{α}^{p}(z^{1/(p−1)})) (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))

+ 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2} − 2^{−1}
= 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) − z^{p^{α}/(p−1)} + s_{α+1}(z^{1/(p−1)}) − z^{1/(p−1)})^{2}
− z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) − z^{p^{α}/(p−1)} + s_{α+1}(z^{1/(p−1)}) − z^{1/(p−1)})
× (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))
+ 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2} − 2^{−1}
= 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}) − z^{1/(p−1)})^{2}
− z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}) − z^{1/(p−1)})
× (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))
+ 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2} − 2^{−1} modulo p.

By collecting terms, this expression may be simplified to zero.

After we have completed the “base step,” we now proceed with the iterative steps described in Section 4. Our Ansatz here (replacing the corresponding one in (4.6)–(4.8)) is

B_{p}(z) = ∑_{i=0}^{p^{(α+1)h}−1} a_{i,β+1}(z)Φ^{i} (z^{1/(p−1)}) modulo p^{β+1},  (8.5)

with

a_{i,β+1}(z) := a_{i,β}(z) + p^{β}b_{i,β+1}(z), i = 0, 1, …, p^{(α+1)h} − 1,  (8.6)

where the coefficients a_{i,β}(z) are supposed to provide a solution

F_{β}(z) = ∑_{i=0}^{p^{(α+1)h}−1} a_{i,β}(z)Φ^{i} (z^{1/(p−1)})

to (8.2) modulo p^{β}. This Ansatz, substituted in (8.2), produces the congruence

2(−1)^{(p+1)/2} (\frac{p − 1}{2})^{(p−1)/2} \frac{p + 1}{2}

×p^{β}z ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)})) ( ∑_{j=0}^{p^{α+1}−1} a_{j,β}(z)Φ^{j}(z^{1/(p−1)}))^{(p−1)/2}

+ (\frac{p − 1}{2})^{p−1} p^{β} ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)}))

+ z^{2}F_{β}^{p}(z) + ∑_{s=0}^{(p+1)/2}(−1)^{s} \frac{p + 1}{(p − s + 1)(p − s)}\binom{p − s + 1}{s}p^{p−2s+1} (\frac{p − 1}{2})^{s} zF_{β}^{s}(z)

+ (\frac{p − 1}{2})^{p−1} F_{β}(z) − \frac{p + 1}{2} (\frac{p − 1}{2})^{p−1} = 0 modulo p^{β+1}. (8.7)

Since the sum has the prefactor p^{β}, we may reduce the a_{i,β}(z) modulo p. By construction, we have

a_{0,β}(z) = a_{0,1}(z) = 2^{−1}z^{−2/(p−1)}s_{α}^{2}(z^{1/(p−1)}) modulo p,
a_{p^{α},β}(z) = a_{p^{α},1}(z) = z^{−2/(p−1)}s_{α}(z^{1/(p−1)}) modulo p,
a_{2·p^{α},β}(z) = a_{2·p^{α},1}(z) = 2^{−1}z^{−2/(p−1)} modulo p,

and a_{i,β} = 0 modulo p for all other i’s. Equivalently, we have

F_{β}(z) = 2^{−1}z^{−2/(p−1)} (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{2} modulo p.

If we substitute this in (8.7) and divide both sides of the congruence by p^{β} (which is possible by our assumption on F_{β}(z)), we obtain

− ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)})) (Φ^{p^{α}}(z^{1/(p−1)}) + s_{α}(z^{1/(p−1)}))^{p−1}

+ ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)})) + G_{β}(z)

= − ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)})) (∑_{j=0}^{p−1}(−1)^{j}Φ^{jp^{α}}(z^{1/(p−1)}) s_{α}^{p−j−1}(z^{1/(p−1)}))

+ ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)})) + G_{β}(z) = 0 modulo p,

where G_{β}(z) is some polynomial in Φ (z^{1/(p−1)}) whose coefficients are Laurent polynomials in z^{1/(p−1)} with integer coefficients. Upon using (4.5) with z replaced by z^{1/(p−1)} to reduce high powers of Φ(z^{1/(p−1)}), we convert this congruence into

− ∑_{j=0}^{p−1} ∑_{i=jp^{α}}^{p^{α+1}−1} Φ^{i}(z^{1/(p−1)}) (−1)^{j}b_{i−jp^{α},β+1}(z)s_{α}^{p−j−1}(z^{1/(p−1)})

− ∑_{j=0}^{p−1} ∑_{i=p^{α}}^{(j+1)p^{α}−1} Φ^{i}(z^{1/(p−1)}) (−1)^{j}b_{i+(p−j−1)p^{α},β+1}(z)s_{α}^{p−j−1}(z^{1/(p−1)})

+ ∑_{j=0}^{p−1} ∑_{i=0}^{jp^{α}−1} Φ^{i}(z^{1/(p−1)}) (−1)^{j}z^{p^{α}/(p−1)}b_{i+(p−j)p^{α},β+1}(z)s_{α}^{p−j−1}(z^{1/(p−1)})

+ ( ∑_{i=0}^{p^{α+1}−1} b_{i,β+1}(z)Φ^{i}(z^{1/(p−1)})) + G_{β}(z) = 0 modulo p,

Comparison of powers of Φ(z) then yields a system of congruences of the form

M · b = c modulo p,  (8.8)

where b is the column vector of unknowns (b_{i,β+1}(z))_{i=0,1,...,p^{α+1}−1}, c is a (known) column vector of Laurent polynomials in z, and M is the matrix

(\begin{matrix}D(1 − s_{α}^{p−1}) & D(z^{A}) & D(−z^{A}s_{α}) & … & D(z^{A}s_{α}^{p−3}) & D(−z^{A}s_{α}^{p−2}) \\ D(s_{α}^{p−2}) & D(−s_{α}^{p−1}) & D(s_{α} + z^{A}) & … & D(−s_{α}^{p−3} − z^{A}s_{α}^{p−4}) & D(s_{α}^{p−2} + z^{A}s_{α}^{p−3}) \\ D(−s_{α}^{p−3}) & D(s_{α}^{p−2}) & D(−s_{α}^{p−1}) & … & D(s_{α}^{p−4} + z^{A}s_{α}^{p−5}) & D(−s_{α}^{p−3} − z^{A}s_{α}^{p−4}) \\ ⋮ & ⋮ & ⋮ & ... \\ D(s_{α}) & D(−s_{α}^{2}) & D(s_{α}^{3}) & … & D(−s_{α}^{p−1}) & D(s_{α} + z^{A}) \\ D(−1) & D(s_{α}) & D(−s_{α}^{2}) & … & D(s_{α}^{p−2}) & D(−s_{α}^{p−1}) \end{matrix}) ,

where s_{α} is short for s_{α}(z^{1/(p−1)}), A is short for p^{α}/(p−1), and D(x) denotes the p^{α}×p^{α} diagonal matrix whose diagonal entries equal x. More precisely, the (r, t)-block of the matrix, 0 ≤ r, t ≤ p − 1, is given by

D(1 − s_{α}^{p−1}),  if r = t = 0,
D((−1)^{t−1}z^{A}s_{α}^{t−1}),  if r = 0 and t > 0,
D((−1)^{r−t+1}s_{α}^{p−1−r+t}),  if r ≥ t but not r = t = 0,
D((−1)^{t−r−1}s_{α}^{t−r−1}(s_{α} + z^{A})), if 0 < r < t.

We claim that

det(M) = z^{p^{α}} modulo p.

In order to see this, we add 1−s_{α}^{p−1}(z) times row i+(p−1)·p^{α} to row i, i = 0, 1, …, p^{α}−1, and we add s_{α}(z^{1/(p−1)}) times row i + p^{α} to row i, i = p^{α}, p^{α} + 1, …, p^{α+1} − 1. This leads to the matrix

(\begin{matrix}0 & D(s_{α} + z^{A} − s_{α}^{p}) & ∗ & … & ∗ & ∗ \\ 0 & 0 & D(s_{α} + z^{A} − s_{α}^{p}) & … & 0 & 0 \\ 0 & 0 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... \\ 0 & 0 & 0 & … & 0 & D(s_{α} + z^{A} − s_{α}^{p}) \\ D(−1) & D(s_{α}) & D(−s_{α}^{2}) & … & D(s_{α}^{p−2}) & D(−s_{α}^{p−1}) \end{matrix}) .

If, in addition, we move rows (p − 1) · p^{α}, (p − 1) · p^{α} + 1, …, p^{α+1} − 1 to the top of the matrix, then it attains an upper triangular form, from which one infers that

det(M) = (−1)^{(p−1)·p^{α}·p^{α}} det^{p−1}(D(s_{α}(z^{1/(p−1)}) + z^{p^{α}/(p−1)} − s_{α}^{p}(z^{1/(p−1)}))) det (D(1))
= (s_{α}(z^{1/(p−1)}) + z^{p^{α}/(p−1)} − s_{α}^{p}(z^{1/(p−1)}))^{(p−1)·p^{α}}
= z^{p^{α}} modulo p,

as was claimed. As a consequence, the system (8.8) is (uniquely) solvable. Thus, we have proved that, for an arbitrary non-negative integer α, the algorithm of Section 4 will produce a solution F_{p^{α}}(z) to (8.2) modulo p^{p^{α}} which is a polynomial in Φ(z^{1/(p−1)}) with coefficients that are Laurent polynomials in z. □

A direct corollary of the α = 0 case of the preceding proof is the following.

Corollary 24. The blossom tree numbers B(n; p) = \frac{k+1}{n((p−1)n+2)} \binom{pn}{n−1} obey the following congruences modulo p:

(i) If n = \frac{1}{p−1}(p^{i_{1}} + p^{i_{2}} − 2) with i_{1} − 1 > i_{2} ≥ 0, then B(n; p) ≡ 1 (mod p).

(ii) If n = \frac{1}{p−1} (2p^{i} − 2) with i ≥ 1, then B(n; p) ≡ \frac{p+1}{2} (mod p).

(iii) In the cases not covered by items (i) and (ii), the number B(n; p) is divisible by p.

Obviously, one can do better by using an implementation of the algorithm contained in the proof of Theorem 23. As an illustration, we display below the result obtained for the modulus p^{2}. Again, this result was first guessed from the automatically obtained results for p = 3, 5, 7, but, once found, it is easily verified directly by substitution in (8.4).

Theorem 25. Let Φ(z) = ∑_{n≥0} z^{p^{n}}. Then we have

\frac{p + 1}{2} + ∑_{n≥1} B(n; p) z^{n} = (p + 1)z^{−1/(p−1)}Φ(z^{1/(p−1)}) − \frac{p + 1}{2}z^{−2/(p−1)}Φ^{2}(z^{1/(p−1)})

+ z^{−2/(p−1)}Φ^{p+1}(z^{1/(p−1)}) modulo p^{2}. (8.9)

Explicitly, this means the following.

Corollary 26. The blossom tree numbers B(n; p) = \frac{k+1}{n((p−1)n+2)} \binom{pn}{n−1} obey the following congruences modulo p^{2}:

(i) If n = \frac{1}{p−1} ((p + 1)p^{i} − 2) with i ≥ 0, then B(n; p) ≡ 1 (mod p^{2}). (ii) If n = \frac{1}{p−1} (2p^{i} − 2) with i ≥ 1, then B(n; p) ≡ \frac{p+1}{2} (mod p^{2}). (iii) If n = \frac{1}{p−1}(p^{i_{1}} + p^{i_{2}} − 2) with i_{1} − 1 > i_{2} ≥ 0, then B(n; p) ≡ p + 1 (mod p^{2}). (iv) If

n = \frac{1}{p − 1} (a_{1}p^{i_{1}} + a_{2}p^{i_{2}} + ⋯ + a_{r}p^{i_{r}} − 2)

with all a_{i}’s relatively prime to p, a_{1} + a_{2} + ⋯ + a_{r} = p + 1, r ≥ 2, and

i_{1} > i_{2} > ⋯ > i_{r} ≥ 0, then we have

B(n; p) ≡ \frac{(p + 1)!}{a_{1}! a_{2}! ⋯ a_{r}!} (mod p^{2}).

(v) In the cases not covered by items (i)–(iv), the number B(n; p) is divisible by p^{2}.

Proof. By means of Equation (3.1) and Proposition 9, we convert the right-hand side of (8.9) into a linear combination of series H_{a_{1},a_{2},...,a_{r}}(z^{1/(p−1)}) with all a_{i}’s relatively prime to p. The result is

∑_{n≥0} B(n; p) z^{n} = \frac{p + 1}{2}z^{−2/(p−1)}H_{2}(z^{1/(p−1)}) + (p + 1)z^{−2/(p−1)}H_{1,1}(z^{1/(p−1)})

− pz^{−2/(p−1)}H_{p+1}(z^{1/(p−1)})

+ z^{−2/(p−1)} ∑_{r=1}^{p+1}_{∑_{a_{1},...,a_{r}≥1} ; a_{1}+···+a_{r}=p+1 r≥2 and a_{i}≠p for all i} \frac{(p + 1)!}{a_{1}! a_{2}! ⋯ a_{r}!}H_{a_{1},a_{2},...,a_{r}}(z^{1/(p−1)}) modulo p^{2}.

Coefficient extraction then yields the claimed congruences. □

Appendix: Proof of the functional equation (8.2)

Let k be a positive integer and let

T_{k}(z) = ∑_{n≥1} \frac{1}{n}\binom{kn}{n − 1}z^{n}

be the generating function for the general Fuß–Catalan numbers. We claim that the blossom tree generating function B_{k}(z) can be expressed in terms of T_{k}(z) as follows.

Lemma 27. For all positive integers k, we have

B_{k}(z) = (1 + T_{k}(z)) (k − \frac{k − 1}{2}(1 + T_{k}(z))) .  (A.1)

Proof. We verify that the coefficient of z^{n} is the same on both sides of (A.1), for n = 0, 1, … Clearly, the constant coefficient equals (k + 1)/2 on both sides.

Now let n ≥ 1. It is easily seen by Lagrange inversion (see [20, Theorem 5.4.2]), that the series T_{k}(z) satisfies the equation

T_{k}(z) = z(1 + T_{k}(z))^{k}.  (A.2)

In other words, it is the compositional inverse of z/(1 + z)^{k}. By applying Lagrange inversion again, we infer

⟨z^{n}⟩ (1 + T_{k}(z)) (k − \frac{k − 1}{2}(1 + T_{k}(z))) = \frac{1}{n} ⟨z^{−1}⟩ (1 − (k − 1)z) \frac{(1 + z)^{kn}}{z^{n}}

= \frac{1}{n} (⟨z^{n−1}⟩ (1 + z)^{kn} − (k − 1) ⟨z^{n−2}⟩ (1 + z)^{kn})

= \frac{1}{n} (\binom{kn}{n − 1} − (k − 1)\binom{kn}{n − 2})

= \frac{k + 1}{n((k − 1)n + 2)}\binom{kn}{n − 1} = B(n; k).

□

Proof of (8.2). In order to establish (8.2), we substitute the right-hand side of (A.1) for B_{k}(z) in (8.2). After applying the binomial theorem, we obtain

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

+ ∑_{s=0}^{(k+1)/2} ∑_{j=0}^{s}(−1)^{s+j} \frac{k + 1}{(k − s + 1)(k − s)}

· \binom{k − s + 1}{s}\binom{s}{j}k^{k−s−j+1} (\frac{k − 1}{2})^{s+j} zX(z)^{s+j}

− (−1)^{k} (\frac{k − 1}{2})^{k−1} X(z) (k − \frac{k − 1}{2}X(z)) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1}

on the left-hand side, where X(z) = 1 + T_{k}(z). In order to simplify, we use the relation (A.2) in the first term, we replace s by s − j, and then write the sum over j in 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 the Pochhammer symbol (α)_{m} is defined by (α)_{m} := α(α + 1) ⋯ (α + m − 1), m ≥ 1, and (α)_{0} := 1. In this manner, we arrive at

z ∑_{j=0}^{k}(−1)^{j}\binom{k}{j}k^{k−j} (\frac{k − 1}{2})^{j} (X(z) − 1)X(z)^{j}

+ 2(−1)^{k+1} (\frac{k − 1}{2})^{k} zX(z)^{k+1} + (−1)^{k}k(k + 1) (\frac{k − 1}{2})^{k−1} zX(z)^{k}

+ ∑_{s=0}^{k−1}(−1)^{s} \frac{(k + 1) (k − s − 1)!}{(k − 2s + 1)! s!}k^{k−s+1} (\frac{k − 1}{2})^{s}

· zX(z)^{s} _{3}F_{2}[\begin{matrix}k − s, −\frac{s}{2}, −\frac{s}{2} + 1 \\ \frac{k}{2} − s + \frac{1}{2}, \frac{k}{2} − s + 1 \end{matrix}; 1]

− (−1)^{k} (\frac{k − 1}{2})^{k−1} X(z) (k − \frac{k − 1}{2}X(z)) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1}

The _{3}F_{2}-series can be evaluated by means of the Pfaff–Saalschütz summation formula (see [19, (2.3.1.3), Appendix (III.2)])

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

provided n is a non-negative integer. Thus, we obtain

∑_{j=0}^{k}(−1)^{j}\binom{k}{j}k^{k−j} (\frac{k − 1}{2})^{j} z(X(z) − 1)X(z)^{j}

+ 2(−1)^{k+1} (\frac{k − 1}{2})^{k} zX(z)^{k+1} + (−1)^{k}k(k + 1) (\frac{k − 1}{2})^{k−1} zX(z)^{k}

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

− (−1)^{k} (\frac{k − 1}{2})^{k−1} X(z) (k − \frac{k − 1}{2}X(z)) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1}

= ∑_{j=0}^{k}(−1)^{j}\binom{k}{j}k^{k−j} (\frac{k − 1}{2})^{j} z(X(z) − 1)X(z)^{j}

+ (−1)^{k+1} (\frac{k − 1}{2})^{k} zX(z)^{k+1} + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1} zX(z)^{k}

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

− (−1)^{k} (\frac{k − 1}{2})^{k−1} X(z) (k − \frac{k − 1}{2}X(z)) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1} .

In the last expression, the sums can in fact be extended to run over all integers j respectively s. A comparison of powers of X(z) then makes it obvious that the sum over j cancels with the sum over s. To the remaining terms X^{k+1}(z) and X^{k}(z) we apply again the relation (A.2). This turns the above expression into

(−1)^{k+1} (\frac{k − 1}{2})^{k} (X(z) − 1)X(z) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1} (X(z) − 1)

− (−1)^{k} (\frac{k − 1}{2})^{k−1} X(z) (k − \frac{k − 1}{2}X(z)) + (−1)^{k} \frac{k + 1}{2} (\frac{k − 1}{2})^{k−1} = 0,

which finishes the proof of (8.2). □

References

[1] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., vol. 202, no. 949, Amer. Math. Soc., Providence, R.I., 2009.

[2] M. Bousquet–Mélou, Walks in the quarter plane — Kreweras’ algebraic model, Ann. Appl. Probab. 15 (2005), 1451–1491.

[3] M. Bousquet–Mélou, Counting planar maps, coloured or uncoloured, in: Surveys in Combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 1–49.

[4] K. S. Davis and W. A. Webb, Lucas’ theorem for prime powers, Europ. J. Combin. 11 (1990), 229–233.

[5] E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215.

[6] C. Domb and A. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341–358.

[7] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. 116 (2006), 135–144.

[8] P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204 (1999), 203–229.

[9] I. M. Gessel, A short proof of the Deutsch–Sagan congruence for connected noncrossing graphs,

    preprint; arχiv:1403.7656.

[10] 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.

[11] Q.-H. Hou, Comment on paper P37 of volume 18(2), Electron. J. Combin., 2012.

[12] 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.

[13] C. Krattenthaler and T. W. Müller, A method for determining the mod-3^{k} behaviour of recursive sequences, preprint; arχiv:1308.2856.

[14] G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers, Cahiers du B.U.R.O. Univ. de Rech. Opér., 6 (1965), 5–105.

[15] A. M. Legendre, Essai sur la théorie des nombres, 2ed., Courcier, Paris, 1808.

[16] H. Niederhausen, The ballot problem with three candidates, Europ. J. Combin. 4 (1983), 161–167.

[17] E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, J. Théorie Nombres Bordeaux 27 (2015), 245–288.

[18] G. Schaeffer, A combinatorial interpretation of super-Catalan numbers of order two, unpublished manuscript, 2003; available at

    http://www.lix.polytechnique.fr/Labo/Gilles.Schaeffer/Biblio/Sc03.ps.

[19] L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

[20] 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.