Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial

Sequences

William Y.C. Chen^{1}, Qing-Hu Hou^{2}, and Doron Zeilberger^{3}

[Also appeared in J. of Difference Equations and Applications 22 (2016), 780-788.]

1,2 Center for Applied Mathematics, Tianjin University Tianjin 300072, P.R. China chenyc@tju.edu.cn, qh hou@tju.edu.cn

3 Department of Mathematics, Rutgers University (New Brunswick) Piscataway, NJ 08854, USA zeilberg@math.rutgers.edu

Abstract

Many combinatorial sequences (for example, the Catalan and Motzkin numbers) may be expressed as the constant term of P (x)^{k}Q(x), for some Laurent polynomials P (x) and Q(x) in the variable x with integer coefficients. Denoting such a sequence by a_{k}, we obtain a general formula that determines the congruence class, modulo p, of the indefinite sum ∑_{k=0}^{rp−1} a_{k}, for any prime p, and any positive integer r, as a linear combination of sequences that satisfy linear recurrence (alias difference) equations with constant coefficients. This enables us (or rather, our computers) to automatically discover and prove congruence theorems for such partial sums. Moreover, we show that in many cases, the set of the residues is finite, regardless of the prime p.

1. Introduction

Let {a_{k}} be a sequence of integers, and r be a positive integer. We focus on the congruences of the partial sum ∑_{k=0}^{rp−1} a_{k} modulo a general prime p. When a_{k} is a hypergeometric term and r = 1 we get a truncated hypergeometric series, which is closely related to the Gaussian hypergeometric series introduced by Greene [3]. An interesting example is the congruence of the Apéry number [1, 2]

A (\frac{p − 1}{2}) ≡ ∑_{k=0}^{p−1} \binom{2k}{k}^{4}2^{−8k} ≡ γ(p) (mod p),

where

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

and

∑_{j=1}^{∞} γ(n)q^{n} = q ∏_{n=1}^{∞}(1 − q^{2n})^{4}(1 − q^{4n})^{4}.

These congruences are usually obtained case by case and the proofs are complicated. For example, Pan and Sun [5] used a sophisticated combinatorial identity to deduce that

∑_{k=0}^{p−1} \binom{2k}{k + d} ≡ (\frac{p − d}{3}) (mod p), d = 0, 1, …, p,

where (\frac{·}{·}) is the Legendre symbol. We propose an automated method to discover and prove such congruences for a large family of combinatorial sequences {a_{k}}. More precisely, we assume that a_{k} is the constant term of P (x)^{k}Q(x) where P (x) and Q(x) are two Laurent polynomials in the (single) variable x with integer coefficients. Rowland and Zeilberger [6] discovered an algorithm to automatically generate automata for determining the congruences, modulo a prime p, of combinatorial sequences (not the partial sums) but for specific primes p (one at a time).

Throughout the paper, p always denotes a prime number. We write a ≡_{p} b if a is congruent to b modulo p. For a Laurent series f(x) = ∑_{k≥k_{0}} a_{k}x^{k}, we use CT f(x) to denote the coefficient of the free term, x^{0}. The set of integers, rational numbers and complex numbers are denoted by ℤ, ℚ and ℂ, respectively. The finite field with p elements is denoted by 𝔽_{p}.

2. Evaluation

In this section, we show that the above-mentioned partial sums are linear combinations of C-finite sequences, i.e., integer sequences that satisfy a linear recurrence equation with constant coefficients (like 2^{n} and the Fibonacci numbers, to name two famous examples). This would enable us (and our computers) to discover and prove practically infinitely-many theorems about the congruences of such partial sums modulo an arbitrary (symbolic!) prime p.

We have the following formula for the congruences of the partial sums.

Theorem 2.1 Let P (x), Q(x) be two Laurent polynomials in x with integer coefficients and

a_{k} := CT P (x)^{k}Q(x).

Let −m and −n be the lowest degrees of P (x) and Q(x)/(P (x) − 1), respectively. Then for any positive integer r, and any prime p > n, we have

∑_{k=0}^{rp−1} a_{k} ≡_{p} ∑_{j=0}^{rm} c_{j}S_{(rm−j)p} ,  (2.1)

where c_{j} is the coefficient of x^{−rm+j} in P (x)^{r} − 1 and S_{k} is the coefficient of x^{k} in the Laurent expansion of

\frac{Q(x)}{P (x) − 1}.

Proof. Noting that CT is a linear operator, we have

∑_{k=0}^{rp−1} a_{k} = CT ∑_{k=0}^{rp−1} P (x)^{k}Q(x) = CT \frac{(P (x)^{rp} − 1)Q(x)}{P (x) − 1}.

Since the coefficients of P (x) are integers, we have, (by the “Freshman’s Dream Identity” , (a + b)^{p} ≡_{p} a^{p} + b^{p}), P (x)^{p} ≡_{p} P (x^{p}) and hence

∑_{k=0}^{rp−1} a_{k} ≡_{p} CT \frac{Q(x)(P (x^{p})^{r} − 1)}{P (x) − 1}.

By the definition of m and c_{j}, we see that

P (x)^{r} − 1 = ∑_{j=0}^{N} c_{j}x^{−rm+j}.

for some integer N. If j > rm, we have

(−rm + j)p − n > n(−rm + j) − n ≥ 0,

which implies that

CT \frac{Q(x)x^{(−rm+j)p}}{P (x) − 1} = 0.

Hence

CT \frac{Q(x)(P (x^{p})^{r} − 1)}{P (x) − 1} = ∑_{j=0}^{rm} c_{j}CT \frac{Q(x)x^{(−rm+j)p}}{P (x) − 1} = ∑_{j=0}^{rm} c_{j}S_{(rm−j)p}.

This completes the proof.

This theorem is implemented in the Maple package CTcong.txt available from the webpage

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/ctcong.html

where the user can also find sample input and output files.

The Maple command-line is

                   TheoG(P, Q, x, p, C, r),

where P, Q are two Laurent polynomials, with integer coefficients, in the variable x, p is the symbol standing for the prime, C is the name for the sequence of coefficients of Q(x)/(P (x) − 1), while r is as in Equation (2.1). For example, typing (in a Maple session, after reading our Maple package

CTcong.txt)
               TheoG(1/x+2+x, x^d, x, p, C, 1);

immediately outputs Corollary 2.2 Let A(i) be the constant term of the Laurent polynomial

x^{d} (\frac{1}{x} + 2 + x)^{i} ,

and for any prime p, let

B(p) = ∑_{i=0}^{p−1} A(i).

Then

B(p) ≡ C(p) (mod p),

where C(n) is the C-finite sequence defined in terms of the generating function

∑_{i=0}^{∞} C(i)x^{i} = \frac{x^{d+1}}{x^{2} + x + 1}.

Noting that

CT x^{d} (\frac{1}{x} + 2 + x)^{i} = \binom{2i}{i − d} = \binom{2i}{i + d},

and

\frac{x^{d+1}}{x^{2} + x + 1} = x^{d+1}(1 + x^{3} + x^{6} + ⋯ − x − x^{4} − x^{7} − ⋯),

Corollary 2.2 is equivalent to the congruence relation given by Pan and Sun

∑_{k=0}^{p−1} \binom{2k}{k + d} ≡_{p} (\frac{p − d}{3}) .

[Of course this case, and many other ones, for small r, are easily humanlygenerated.]

Using this approach, we found many congruences, including the congruences for the sums of generalized central trinomial coefficients that were considered by Sun in [7].

When Q(x)/(P (x) − 1) is a rational function such that every root of the denominator is a root of unity, the coefficient of x^{k} in Q(x)/(P (x) − 1) can be expressed as a quasi-polynomial in k. We can search for this quasi-polynomial by the method of undetermined coefficients and thus derive theorems presenting explicit forms for the congruences. This is implemented by the procedure TheoQP in our Maple package CTcong.txt. The commandline is

                  TheoQP(P, Q, x, p, r, d) ,

where P, Q are the two Laurent polynomials in x, p is the symbol standing for the prime, r is as above, and d is the expected degree of the searched quasi-polynomial. (In practice, you start, optimistically, with d = 0, and if it fails, you keep increasing d to 1, then 2, until you either find something, or give up.)

For example, typing

                TheoQP(1/x+2+x, 1, x, p, 2, 0);

yields

Corollary 2.3

∑_{k=0}^{2p−1} \binom{2k}{k} ≡_{p} \begin{cases}3, & if p ≡ 1 (mod 3), \\ −3, & if p ≡ 2 (mod 3). \end{cases}

For more examples, we refer to the above-mentioned webpage

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/ctcong.html

3. Reduction

In this section, we consider a further reduction of the coefficients S_{p}, S_{2p}, … in Equation (2.1). We find that in some cases, the set {S_{p} (mod p)} of residues is a finite subset of ℚ when p runs over all primes.

First, let us consider the coefficients S_{k} given by

\frac{ux + v}{a + bx + cx^{2}} = ∑_{k=0}^{∞} S_{k}x^{k},

where u, v, a, b, c are integers, a ≠ 0 and a + bx + cx^{2} is irreducible over ℚ. Let Δ = b^{2} − 4ac be the discriminate of ax^{2} + bx + c. Since a + bx + cx^{2} is irreducible, Δ ≠ 0, and hence Δ ≢_{p} 0 except for finitely many primes p.

If Δ is a square in the finite field 𝔽_{p}, then a + bx + cx^{2} is reducible in 𝔽_{p} so that

\frac{ux + v}{a + bx + cx^{2}} ≡_{p} \frac{A}{1 − αx} + \frac{B}{1 − βx},

for some A, B, α, β ∈ 𝔽_{p}. We thus find that

S_{rp} = Aα^{rp} + Bβ^{rp} ≡_{p} Aα^{r} + Bβ^{r} = S_{r}.

If Δ is not a square in 𝔽_{p}, then a + bx + cx^{2} is irreducible in 𝔽_{p}. Let us consider the extension field 𝔽_{p}(α) with aα^{2} + bα + c = 0 and α ∈ ℂ. Let β ∈ ℂ be another root of the equation ax^{2} + bx + c = 0. By the property of the Frobenius automorphism [8], it follows that in the extension field 𝔽_{p}(α),

α^{p} = β, β^{p} = α.

Hence in the field 𝔽_{p}(α), we have

S_{rp} = Aα^{rp} + Bβ^{rp} = Aβ^{r} + Bα^{r} = \frac{c^{r}}{a^{r}} (Aα^{−r} + Bβ^{−r}) = \frac{c^{r}}{a^{r}} S_{−r},

where S_{−r} is determined by the initial values S_{0}, S_{1} and the recurrence relation

aS_{n} + bS_{n−1} + cS_{n−2} = 0, n ∈ ℤ.

Since S_{rp} and S_{−r} are both rational numbers, we obtain that S_{rp} ≡_{p} S_{−r}.

In general, let q(x) be an irreducible polynomial in ℤ[x] of degree d with non-zero constant term and α_{1}, …, α_{d} be the d roots of x^{d}q(1/x) in ℂ. If the splitting field ℚ(α_{1}, …, α_{d}) equals ℚ(α_{j}) for some 1 ≤ j ≤ d, we say that q(x) is simple. Clearly, every irreducible polynomial of degree 2 is simple.

We have the following finiteness theorem regarding the congruences.

Theorem 3.1 Let P (x), Q(x) be two Laurent polynomials in x with integer coefficients and

a_{k} = CT P (x)^{k}Q(x).

Suppose that each irreducible factor q(x) ≠ x of the denominator of Q(x)/(P (x)− 1) is simple. Then there exists a finite subset A of ℚ such that for any prime p,

∑_{k=0}^{rp−1} a_{k} ≡ a (mod p),

for some a ∈ A.

Proof. By Theorem 2.1, for a sufficiently large prime p, ∑_{k=0}^{rp−1} a_{k} modulo p is a linear combination of S_{0}, S_{p}, S_{2p}, …, where S_{k} is the coefficient of x^{k} in the series

R(x) = \frac{Q(x)}{P (x) − 1}.

To prove the theorem, it suffices to show that for a fixed integer m, the set

⋃_{p} {S_{mp} mod p}

of residues is finite when p runs over all primes.

Consider the partial fraction decomposition of R(x) over ℚ

R(x) = g(x) + ∑_{i=1}^{m} \frac{h_{i}(x)}{q_{i}(x)^{ℓ_{i}}} ,

where g(x) is a Laurent polynomial over ℚ and for each i = 1, …, m, q_{i}(x) ∈ ℤ[x] is irreducible and h_{i}(x) ∈ ℤ is a polynomial with deg h_{i}(x) < deg q_{i}(x). In order to show the finiteness of the set ∪_{p}{S_{mp} mod p}, it suffices to show that the residues of the coefficients of each summand form a finite set.

Let h(x)/q(x)^{ℓ} be one summand and

∑_{k=0}^{∞} s_{k}x^{k} = \frac{h(x)}{q(x)^{ℓ}} .

Let q̃(x) = x^{d}q(1/x) where d = deg q(x) and let α_{1}, …, α_{d} be the roots of q̃(x). By assumption, we have ℚ(α_{1}, …, α_{d}) = ℚ(α) with α ∈ {α_{1}, …, α_{d}}. Denote the splitting field ℚ(α) by K. Since q(x) is irreducible, we have

K = \{\frac{a_{0} + a_{1}α + ⋯ + a_{d−1}α^{d−1}}{b} : a_{0}, …, a_{d−1}, b ∈ ℤ\} .

Let p be a prime larger than the maximal factor of the leading coefficient of q̃(x). Then

K_{p} := \{\frac{a_{0} + a_{1}α + ⋯ + a_{d−1}α^{d−1}}{b} : p ∤ b\} ⊂ K

form a subring of K. There is a natural ring homomorphism τ: K_{p} → 𝔽[x]/⟨q̃(x)⟩ given by

τ (\frac{a_{0} + a_{1}α + ⋯ a_{d−1}α^{d−1}}{b} ) = a_{0}b^{−1} + a_{1}b^{−1}x + ⋯ + a_{d−1}b^{−1}x^{d−1}.

Clearly, the kernel of the map τ is pK_{p}.

It is well-known that the coefficients s_{k} can be expressed as

s_{k} = ∑_{i=1}^{d} f_{i}(k)α_{i}^{k},

where f_{i}(k) is a polynomial over ℚ(α) of degree less than ℓ. It is easy to see that

τ(f_{i}(mp)) = τ(c_{i}),

where c_{i} is the constant term of f_{i}(x). Since q̃(x) ∈ ℤ[x], for each i = 1, …, d, we have

q̃(τ(α_{i}^{p})) = τ(q̃(α_{i}^{p})) = τ((q̃(α_{i}))^{p}) = 0.

Hence τ(α_{i}^{p}) = τ(α_{j}) for some 1 ≤ j ≤ d. Let σ be the map given by τ(α_{i}^{p}) = τ(α_{σ(i)}). We thus have

τ(s_{mp}) = ∑_{i=1}^{d} τ(c_{i})τ(α_{σ(i)}^{m}) = τ (∑_{i=1}^{d} c_{i}α_{σ(i)}^{m}) .

Let

∑_{i=1}^{d} c_{i}α_{σ(i)}^{m} = r_{0} + r_{1}α + ⋯ + r_{d−1}α^{d−1}.

Since τ(s_{mp}) ∈ ℚ, we have

τ(s_{mp}) = τ(r_{0}),

and hence s_{mp} ≡_{p} r_{0}. Noting that there are only finitely many choices for σ, hence the set ∪_{p}{s_{mp} mod p} is finite.

Example. Suppose that

P (x) = \frac{x^{3} − 2x + 1}{x}, and Q(x) = 1.

We have

\frac{Q(x)}{P (x) − 1} = \frac{x}{x^{3} − 3x + 1}.

Let

α = −0.532 …, β = 0.6527 …, γ = 2.879 …

be the three roots of x^{3} − 3x^{2} + 1. Using the approximate values of the three roots, we may use the LLL algorithm [4] to find integral relations among β, γ and powers of α. Using Maple, we get two possible relations

β = 2 + 2α − α^{2}, γ = 1 − 3α + α^{2}.  (3.1)

It is easy to verify that

(2 + 2α − α^{2})^{3} − 3(2 + 2α − α^{2})^{2} + 1 = 0,

and

(1 − 3α + α^{2})^{3} − 3(1 − 3α + α^{2})^{2} + 1 = 0.

which means that 2 + 2α − α^{2} and 1 − 3α + α^{2} are roots of x^{3} − 3x^{2} + 1. So we claim the relations in (3.1). Therefore, ℚ(α, β, γ) = ℚ(α) and hence x^{3} − 3x + 1 is simple. By Theorem 3.1, the set

{∑_{k=0}^{2p−1} CT P (x)^{k} mod p}

is finite. In fact, when p > 3, the only possibilities are −1 and 2.

We conclude with an example where the denominator is not simple.

Example. Let

P (x) = −2x^{2} + 1 + \frac{1}{x}, Q(x) = 1.

Then

\frac{Q(x)}{P (x) − 1} = \frac{x}{1 − 2x^{3}} = x + 2x^{4} + 2^{2}x^{7} + · · · .

Hence for p ≡ 1 (mod 3), we have

∑_{k=0}^{p−1} CT P (x)^{k} ≡ 2^{\frac{p−1}{3}} ≡ 2^{− \frac{1}{3}} (mod p).

It seems that the set \{2^{− \frac{1}{3}} (mod p)\} is not finite.

Acknowledgements. We wish to thank Zhi-Wei Sun for valuable suggestions. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, and the National Science Foundation of China.

References

[1] S. Ahlgreen and K. Ono. A Gaussian hypergeometric series evaluation and Apéry number congruences. Journal fur die Reine und Angewandte Mathematik, pages 187–212, 2000.

[2] F. Beukers. Another congruence for the Apéry numbers. Journal of Number Theory, 25(2):201–210, 1987.

[3] J. Greene. Hypergeometric functions over finite fields. Transactions of the American Mathematical Society, 301(1):77–101, 1987.

[4] A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.

[5] H. Pan and Z.-W. Sun. A combinatorial identity with application to Catalan numbers. Discrete mathematics, 306(16):1921–1940, 2006.

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

[7] Z.-W. Sun. Congruences involving generalized central trinomial coefficients. Science China Mathematics, 57(7):1375–1400, 2014.

[8] Z.-X. Wan. Lectures on Finite Fields and Galois Rings. World Scientific, 2003.