Polynomial Reduction and Super Congruences

Qing-Hu Hou

                       qh hou@tju.edu.cn

School of Mathematics Tianjin University Tianjin 300350, P. R. China

Yan-Ping Mu

                     yanping.mu@gmail.com

College of Science Tianjin University of Technology Tianjin 300384, P. R. China

Doron Zeilberger

                      doronzeil@gmail.com

Department of Mathematics Rutgers University Piscataway, NJ 08854, USA

Abstract

Based on a reduction processing, we rewrite a hypergeometric term as the sum of the difference of a hypergeometric term and a reduced hypergeometric term (the reduced part, in short). We show that when the initial hypergeometric term has a certain kind of symmetry, the reduced part contains only odd or even powers. As applications, we derived two infinite families of super-congruences.

1 Introduction

In recent years, many super congruences involving combinatorial sequences are discovered, see for example, Sun [16]. The standard methods for proving these congruences include combinatorial identities [18], Gauss sums [5], symbolic computation [14] et al.

We are interested in the following super congruence conjectured by van Hamme [19]

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

where p is a odd prime and (a)_{k} = a(a + 1) ⋯ (a + k − 1) is the rising factorial. This congruence was proved by Mortenson [13] Zudilin [21] and Long [12] by different methods. Sun [17] proved a stronger version for prime p ≥ 5

∑_{k=0}^{\frac{p−1}{2}}(−1)^{k}(4k + 1) (\frac{(1/2)_{k}}{(1)_{k}} )^{3} ≡ (−1)^{\frac{p−1}{2}} p + p^{3}E_{p−3} (mod p^{4}),

where E_{n} is the n-th Euler number defined by

\frac{2}{e^{x} + e^{−x}} = ∑_{n=0}^{∞} E_{n} \frac{x^{n}}{n!} .

A similar congruence was given by van Hamme [19] for p ≡ 1 (mod 4):

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

Long [12] showed that in fact the above congruence holds for arbitrary odd prime modulo p^{4}. Motivated by these two congruences, Guo [8] proposed the following conjectures (corrected version).

Conjecture 1.1 • For any odd prime p, positive integer r and odd integer m, there exists an integer a_{m.p} such that

∑_{k=0}^{\frac{p^{r}−1}{2}}(−1)^{k}(4k + 1)^{m} (\frac{(1/2)_{k}}{(1)_{k}} )^{3} ≡ a_{m,p}p^{r}(−1)^{\frac{(p−1)r}{2}} (mod p^{r+2}).

(1.1)

• For any odd prime p > (m − 1)/2, positive integer r and odd integer m, there exists an integer b_{m,p} such that

∑_{k=0}^{\frac{p^{r}−1}{2}}(4k + 1)^{m} (\frac{(1/2)_{k}}{(1)_{k}} )^{4} ≡ b_{m,p}p^{r} (mod p^{r+3}).  (1.2)

Liu [11] and Wang [20] confirmed the conjectures for r = 1 and some initial values m. Jana and Kalita [10] and Guo [9] confirmed (1.1) for m = 3 and r ≥ 1. We will prove a stronger version of (1.1) for the case of r = 1 and arbitrary odd m and a weaker version of (1.2) for the case of r = 1 and arbitrary odd m by a reduction process.

Recall that a hypergeometric term t_{k} is a function of k such that t_{k+1}/t_{k} is a rational function of k. Our basic idea is to rewrite the product of a polynomial f(k) in k and a hypergeometric term t_{k} as

f(k)t_{k} = Δ(g(k)t_{k}) + h(k)t_{k} = (g(k + 1)t_{k+1} − g(k)t_{k}) + h(k)t_{k},

where g(k), h(k) are polynomials in k such that the degree of h(k) is bounded. To this aim, we construct x(k) such that Δx(k)t_{k} equals the product of t_{k} and a polynomial u(k) and that f(k) and u(k) has the same leading term. Then we have

f(k)t_{k} − Δx(k)t_{k} = (f(k) − u(k))t_{k}

is the product of t_{k} and a polynomial of degree less than f(k). We call such a reduction process one reduction step. Continuing this reduction process, we finally obtain a polynomial h(k) with bounded degree. We will show that for t_{k} = (\frac{(1/2)_{k}}{(1)_{k}} )^{r}, r = 3, 4 and an arbitrary polynomial of form (4k + 1)^{m} with m odd, the reduced polynomial h(k) can be taken as (4k + 1). This enables us to reduce the congruences (1.1) and (1.2) to the special case of m = 1, which is known for r = 1.

We notice that Pirastu-Strehl [15] and Abramov [1, 2] gave the minimal decomposition when t_{k} is a rational function, Abramov-Petkovšek [3,4] gave the minimal decomposition when t_{k} is a hypergeometric term, and Chen-Huang-Kauers-Li [6] applied the reduction to give an efficient creative telescoping algorithm. These algorithms concern a general hypergeometric term. While we focus on a kind of special hypergeometric term so that the reduced part h(k)t_{k} has a nice form.

The paper is organized as follows. In Section 2, we consider the reduction process for a general hypergeometric term t_{k}. Then in Section 3 we consider those t_{k} with the property a(k) is a shift of −b(k), where t_{k+1}/t_{k} = a(k)/b(k). As an application, we prove a stronger version of (1.1) for the case r = 1. Finally, we consider the case of a(k) is a shift of b(k), which corresponds to (1.2). In this case, we show that there is a rational number b_{m} instead of an integer such that (1.2) holds when r = 1.

2 The Difference Space and Polynomial Reduction

Let K be a field and K[k] be the ring of polynomials in k with coefficients in K. Let t_{k} be a hypergeometric term. Suppose that

\frac{t_{k+1}}{t_{k}} = \frac{a(k)}{b(k)},

where a(k), b(k) ∈ K[k]. It is straightforward to verify that

Δ_{k} (b(k − 1)x(k)t_{k}) = (a(k)x(k + 1) − b(k − 1)x(k))t_{k}.  (2.1)

We thus define the difference space corresponding to a(k) and b(k) to be

S_{a,b} = {a(k)x(k + 1) − b(k − 1)x(k): x(k) ∈ K[k]}.

We see that for f(k) ∈ S_{a,b}, we have f(k)t_{k} = Δ_{k}(p(k)t_{k}) for a certain polynomial p(k) ∈ K[k].

Let ℕ, ℤ denote the set of nonnegative integers and the set of integers, respectively. Given a(k), b(k) ∈ K[k], we denote

u(k) = a(k) − b(k − 1),  (2.2)
d = max{deg u(k), deg a(k) − 1},  (2.3)

and

m_{0} = − lc u(k)/ lc a(k),  (2.4)

where lc p(k) denotes the leading coefficient of p(k).

We first introduce the concept of degeneration.

Definition 2.1 Let a(k), b(k) ∈ K[k] and u(k), m_{0} be given by (2.2) and (2.4). If

deg u(k) = deg a(k) − 1 and m_{0} ∈ ℕ,

we say that the pair (a(k), b(k)) is degenerated.

We will see that the degeneration is closely related to the degrees of the elements in S_{a,b}.

Lemma 2.2 Let a(k), b(k) ∈ K[k] and d, m_{0} be given by (2.3) and (2.4). For any polynomial x(k) ∈ K[k], let

p(k) = a(k)x(k + 1) − b(k − 1)x(k).

If (a(k), b(k)) is degenerated and deg x(k) = m_{0}, then deg p(k) < d + m_{0}; Otherwise, deg p(k) = d + deg x(k).

Proof. Notice that

p(k) = u(k)x(k) + a(k)(x(k + 1) − x(k)).

If the leading terms of u(k)x(k) and a(k)(x(k + 1) − x(k)) do not cancel, the degree of p(k) is d + deg x(k). Otherwise, we have deg u(k) = deg a(k) − 1 and

lc u(k) + lc a(k) · deg x(k) = 0,

i.e., deg x(k) = m_{0}.

It is clear that S_{a,b} is a subspace of K[k], but is not a sub-ring of K[k] in general. Let [p(k)] = p(k) + S_{a,b} denote the coset of a polynomial p(k). We see that the quotient space K[k]/S_{a,b} is finite dimensional.

Theorem 2.3 Let a(k), b(k) ∈ K[k] and d, m_{0} be given by (2.3) and (2.4). We have

K[k]/S_{a,b} = \begin{cases}⟨[k^{0}], [k^{1}], …, [k^{d−1}], [k^{d+m_{0}}]⟩, & if (a(k), b(k)) is degenerated, \\ ⟨[k^{0}], [k^{1}], …, [k^{d−1}]⟩, & otherwise. \end{cases}

Proof. For any nonnegative integer s, let

p_{s}(k) = a(k)(k + 1)^{s} − b(k − 1)k^{s}.

We first consider the case when the pair (a(k), b(k)) is not degenerated. By Lemma 2.2, we have

deg p_{s}(k) = d + s, ∀ s ≥ 0.

Suppose that p(k) is a polynomial of degree m ≥ d. Then

p′(k) = p(k) − \frac{lc p(k)}{lc p_{m−d}(k)}p_{m−d}(k)  (2.5)

is a polynomial of degree less than m and p(k) ∈ [p′(k)]. By induction on m, we derive that for any polynomial p(k) of degree ≥ d, there exists a polynomial p̃(k) of degree < d such that p(k) ∈ [p̃(k)]. Therefore,

K[k]/S_{a,b} = ⟨[k^{0}], [k^{1}], …, [k^{d−1}]⟩.

Now assume that (a(k), b(k)) is degenerated. By Lemma 2.2,

deg p_{s}(k) = d + s, ∀ s ≠ m_{0} and deg p_{m_{0}}(k) < d + m_{0}.

The above reduction process (2.5) works well except for the polynomials p(k) of degree d + m_{0}. But in this case,

p(k) − lc p(k) · k^{d+m_{0}}

is a polynomial of degree less than d + m_{0}. Then the reduction process continues until the degree is less than d. We thus derive that

K[k]/S_{a,b} = ⟨[k^{0}], [k^{1}], …, [k^{d−1}], [k^{d+m_{0}}]⟩,

completing the proof.

Example 2.1 Let n be a positive integer and

t_{k} = (−n)_{k}/k!,

where (α)_{k} = α(α + 1) ⋯ (α + k − 1) is the raising factorial. Then

a(k) = k − n, b(k) = k + 1,

and

S_{a,b} = {(k − n) · x(k + 1) − k · x(k): x(k) ∈ K[k]}.

We have

K[k]/S_{a,b} = ⟨[k^{n}]⟩

is of dimension one.

3 The case when a(k) = −b(k + α)

In this section, we consider the case when a(k) = −b(k + α) and b(k) has a symmetric property. We will show that in this case, the reduction process maintains the symmetric property. Notice that in this case

u(k) = a(k) − b(k − 1) = −b(k + α) − b(k − 1)

has the same degree as a(k), the pair (a(k), b(k)) is not degenerated.

We first consider the relation between the symmetric property and the expansion of a polynomial.

Lemma 3.1 Let p(k) ∈ K[k] and β ∈ K. Then the following two statements are equivalent.

(1) p(β + k) = p(β − k) (p(β + k) = −p(β − k), respectively).

(2) p(k) is the linear combination of (k−β)^{2i}, i = 0, 1, … ((k−β)^{2i+1}, i = 0, 1, …, respectively).

Proof. Suppose that

p(β + k) = ∑_{i} c_{i}k^{i}.

Then

p(β − k) = ∑_{i} c_{i}(−k)^{i}.

Therefore,

p(β + k) = p(β − k) ⟺ c_{2i+1} = 0, i = 0, 1, ….

The case of p(β + k) = −p(β − k) can be proved in a similar way.

Now we are ready to state the main theorem.

Theorem 3.2 Let a(k), b(k) ∈ K[k] such that

a(k) = −b(k + α) and b(β + k) = ±b(β − k),

for some α, β ∈ K. Then for any non-negative integer m, we have

[(k + γ)^{2m}] ∈ ⟨[(k + γ)^{2i}]: 0 ≤ 2i < deg a(k)⟩

and

[(k + γ)^{2m+1}] ∈ ⟨[(k + γ)^{2i+1}]: 0 ≤ 2i + 1 < deg a(k)⟩ ,

where

γ = −β + \frac{α − 1}{2}.  (3.1)

Proof. We only prove the case of b(β +k) = b(β −k). The case of b(β +k) = −b(β − k) can be proved in a similar way. By Lemma 3.1, we may assume that

b(k) = b_{r}(k − β)^{r} + b_{r−2}(k − β)^{r−2} + ⋯ + b_{0},

where r = deg a(k) = deg b(k) is even and b_{r}, b_{r−2}, …, b_{0} ∈ K are the coefficients.

Since (a(k), b(k)) is not degenerated, taking

x(k) = x_{s}(k) = −\frac{1}{2} (k + γ − \frac{1}{2})^{s}  (3.2)

in Lemma 2.2, we derive that

p_{s}(k) = a(k)x_{s}(k + 1) − b(k − 1)x_{s}(k)  (3.3)

is a polynomial of degree s + r. More explicitly, we have

p_{s}(k) = \frac{1}{2} (b(k + α) (k + γ + \frac{1}{2})^{s} + b(k − 1) (k + γ − \frac{1}{2})^{s})

is a polynomial with leading term b_{r}k^{s+r}.

Notice that

p_{s}(−γ + k) = \frac{1}{2} (b(k + α − γ) (k + \frac{1}{2})^{s} + b(k − γ − 1) (k − \frac{1}{2})^{s})

and

p_{s}(−γ − k) = \frac{1}{2} (b(−k + α − γ) (−k + \frac{1}{2})^{s} + b(−k − γ − 1) (−k − \frac{1}{2})^{s})

= \frac{(−1)^{s}}{2} (b(−k + α − γ) (k − \frac{1}{2})^{s} + b(−k − γ − 1) (k + \frac{1}{2})^{s}) .

Since b(β + k) = b(β − k), i.e., b(k) = b(2β − k), we deduce that

p_{s}(−γ − k)

= \frac{(−1)^{s}}{2} (b(2β + k − α + γ) (k − \frac{1}{2})^{s} + b(2β + k + γ + 1) (k + \frac{1}{2})^{s}) .

By the relation (3.1), we derive that

p_{s}(−γ − k) = (−1)^{s}p_{s}(−γ + k).

Suppose that p(k) is a linear combination of the even powers of (k + γ) and deg p(k) ≥ r. By Lemma 3.1, we have p(−γ − k) = p(−γ + k) and thus

p′(k) = p(k) − \frac{lc p(k)}{b_{r}} · p_{deg p(k)−r}(k)

also satisfies p′(−γ −k) = p′(−γ +k) since deg p(k) and r are both even. It is clear that p(k) ∈ [p′(k)] and the degree of p′(k) is less than the degree of p(k). Continuing this reduction process, we finally derive that p(k) ∈ [p̃(k)] for some polynomial p̃(k) with degree < r and satisfying p̃(−γ −k) = p̃(−γ +k). Therefore,

[p(k)] ∈ ⟨[(k + γ)^{2i}]: 0 ≤ 2i < r⟩.

Suppose that p(k) is a linear combination of the odd powers of (k + γ) and deg p(k) ≥ r. Then we have p(−γ − k) = −p(−γ + k) and thus

p′(k) = p(k) − \frac{lc p(k)}{b_{r}} · p_{deg p(k)−r}(k)

also satisfies p′(−γ − k) = −p′(−γ + k). Continuing this reduction process, we finally derive that

[p(k)] ∈ ⟨[(k + γ)^{2i+1}]: 0 ≤ 2i + 1 < r⟩.

This completes the proof.

We may further require to express [(k + γ)^{m}] as an integral linear combination of [(k + γ)^{i}], 0 ≤ i < r when b(k) = (k + 1)^{r}.

Theorem 3.3 Let

t_{k} = (−1)^{k} (\frac{(α)_{k}}{k!} )^{r} ,

where r is a positive integer and α is a rational number with denominator D. Then for any positive integer m, there exist integers a_{0}, …, a_{r−1} and a polynomial x(k) ∈ ℤ[k] such that

(2Dk + Dα)^{m}t_{k} = ∑_{i=0}^{r−1} a_{i}(2Dk + Dα)^{i}t_{k} + Δ_{k} (2^{r−1}(Dk)^{r}x(2Dk)t_{k}) .

Moreover, a_{i} = 0 if i ≢ m (mod 2).

Proof. We have

\frac{t_{k+1}}{t_{k}} = \frac{−(k + α)^{r}}{(k + 1)^{r}} .

Let

a(k) = −(k + α)^{r} and b(k) = (k + 1)^{r}.

We see that it is the case of β = −1 and γ = α/2 of Theorem 3.2. From (2.1), we derive that

Δ_{k}(k^{r}x_{s}(k)t_{k}) = p_{s}(k)t_{k},  (3.4)

where x_{s}(k) and p_{s}(k) are given by (3.2) and (3.3) respectively. Multiplying (2D)^{s+r} on both sides, we obtain

Δ_{k}(2^{r−1}(Dk)^{r}x̃_{s}(2Dk)t_{k}) = p̃_{s}(k′)t_{k},  (3.5)

where k′ = 2Dk + Dα,

x̃_{s}(k) = −(k + Dα − D)^{s},  (3.6)

and

p̃_{s}(k) = \frac{1}{2} ((k + Dα)^{r} (k + D)^{s} + (k − Dα)^{r} (k − D)^{s}) .  (3.7)

Notice that x̃_{s}(k), p̃_{s}(k) ∈ ℤ[k] and p̃_{s}(k) is a monic polynomial of degree s + r. Moreover, p̃_{s}(k) contains only even powers of k or only odd powers of k. Using p̃_{s}(k) to do the reduction (2.5), we derive that there exists integers c_{m}, c_{m−2}, … such that

p(k) = k^{m} − c_{m}p̃_{m−r}(k) − c_{m−2}p̃_{m−r−2}(k) − ⋯

becomes a polynomial of degree less than r. Clearly, p(k) ∈ ℤ[k]. Replacing k by k′ and multiplying t_{k}, we derive that

(k′)^{m}t_{k} = p(k′)t_{k}+Δ_{k}(2^{r−1}(Dk)^{r}(c_{m}x̃_{m−r}(2Dk)+c_{m−2}x̃_{m−r−2}(2Dk)+⋯)t_{k}),

completing the proof.

As an application, we confirm Conjecture 6 of [11].

Theorem 3.4 Let

S_{m} = ∑_{k=0}^{\frac{p−1}{2}}(−1)^{k}(4k + 1)^{m} (\frac{(1/2)_{k}}{(1)_{k}} )^{3} .

For any positive odd integer m, there exist integers a_{m} and c_{m} such that

S_{m} ≡ a_{m} (p(−1)^{\frac{p−1}{2}} + p^{3}E_{p−3}) + p^{3}c_{m} (mod p^{4})

holds for any prime p ≥ 5.

Proof. Taking r = 3 and α = 1/2 in Theorem 3.3, there exist an integer a_{m} and a polynomial q_{m}(k) ∈ ℤ[k] such that

(4k + 1)^{m}t_{k} − a_{m}(4k + 1)t_{k} = Δ_{k}(32k^{3}q_{m}(4k)t_{k}),

where t_{k} = (−1)^{k}(\frac{1}{2})_{k}^{3}/(1)_{k}^{3}. Summing over k from 0 to \frac{p−1}{2}, we derive that

S_{m} − a_{m}S_{1} = 32ω^{3}q_{m}(4ω)(−1)^{ω} (\frac{(1/2)_{ω}}{(1)_{ω}} )^{3} ,

where ω = \frac{p+1}{2}. Noting that

\frac{(1/2)_{ω}}{(1)_{ω}} = p\frac{1}{p + 1} ∏_{i=1}^{\frac{p−1}{2}} \frac{2i − 1}{2i}

and

\frac{1}{p + 1} ∏_{i=1}^{\frac{p−1}{2}} \frac{2i − 1}{2i} = \frac{1}{p + 1} ∏_{i=1}^{\frac{p−1}{2}} \frac{p − 2i}{2i} ≡ (−1)^{\frac{p−1}{2}} (mod p),

we have

(\frac{(1/2)_{ω}}{(1)_{ω}} )^{3} ≡ p^{3}(−1)^{\frac{p−1}{2}} (mod p^{4}).

Hence

S_{m} − a_{m}S_{1} ≡ −32p^{3}ω^{3}q_{m}(4ω) (mod p^{4})

Let c_{m} = −4q_{m}(2). We then have

S_{m} ≡ a_{m}S_{1} + p^{3}c_{m} (mod p^{4}).

Sun [17] proved that for any prime p ≥ 5,

S_{1} ≡ (−1)^{\frac{p−1}{2}} p + p^{3}E_{p−3} (mod p^{4}).

Therefore,

S_{m} ≡ a_{m} (p(−1)^{\frac{p−1}{2}} + p^{3}E_{p−3}) + p^{3}c_{m} (mod p^{4}).

Remark 1. The coefficient a_{m} and the polynomial q_{m}(k) can be computed by the extended Zeilberger’s algorithm [7].

4 The case when a(k) = b(k + α)

We first give a criterion on the degeneration of (a(k), b(k)).

Lemma 4.1 Let a(k), b(k) ∈ K[k] such that a(k) = b(k + α). Suppose that −(α + 1) deg a(k) ∉ ℕ. Then (a(k), b(k)) is not degenerated.

Proof. Let r = deg a(k) = deg b(k) and

u(k) = a(k) − b(k − 1) = b(k + α) − b(k − 1).

It is clear that the coefficient of k^{r} in u(k) is 0 and the coefficient of k^{r−1} in u(k) is lc b(k) · (α + 1)r. Since (α + 1)r ≠ 0, we derive that deg u(k) = r − 1. Thus,

− lc u(k)/ lc a(k) = − lc u(k)/ lc b(k) = −(α + 1)r.

Since −(α + 1)r ∉ ℕ, the pair (a(k), b(k)) is not degenerated.

When a(k) is a shift of b(k), we have a result similar to Theorem 3.2.

Theorem 4.2 Let a(k), b(k) ∈ K[k] such that

a(k) = b(k + α) and b(β + k) = ±b(β − k),

for some α, β ∈ K. Assume further that −(α + 1) deg a(k) ∉ ℕ. Then for any non-negative integer m, we have

(k + γ)^{2m} ∈ ⟨[(k + γ)^{2i}]: 0 ≤ 2i < deg a(k) − 1⟩

and

(k + γ)^{2m+1} ∈ ⟨[(k + γ)^{2i+1}]: 0 ≤ 2i + 1 < deg a(k) − 1⟩ ,

where

γ = −β + \frac{α − 1}{2}.

Proof. The proof is parallel to the proof of Theorem 3.2. Instead of (3.2), we take

x(k) = x_{s}(k) = (k + γ − \frac{1}{2})^{s}

in Lemma 2.2. By Lemma 4.1, (a(k), b(k)) is not degenerated and

deg(a(k) − b(k − 1)) = deg a(k) − 1.

Hence the polynomial

p_{s}(k) = a(k)x_{s}(k + 1) − b(k − 1)x_{s}(k)

satisfies

deg p_{s}(k) = s + deg a(k) − 1.

Moreover, we have

p_{s}(−γ − k) = (−1)^{s+1}p_{s}(−γ + k),

so that the reduction process maintains the symmetric property. Therefore, the reduction process continues until the degree is less than deg a(k) − 1.

Similar to Theorem 3.3, we have the following result.

Theorem 4.3 Let

t_{k} = (\frac{(α)_{k}}{k!} )^{r} ,

where r is a positive integer and α is a rational number with denominator D. Suppose that −αr ∉ ℕ. Then for any positive integer m, there exist integers a_{0}, …, a_{r−2} and a polynomial x(k) ∈ ℤ[k] such that

(2Dk +Dα)^{m}t_{k} = \frac{1}{C_{m}} ∑_{i=0}^{r−2} a_{i}(2Dk +Dα)^{i}t_{k} + \frac{1}{C_{m}} Δ_{k} (2^{r−1}(Dk)^{r}x(2Dk)t_{k}) ,

where

C_{m} = ∏_{0≤2i≤m−r+1}((αr + m − r + 1 − 2i) · D).

Moreover, a_{i} = 0 if i ≢ m (mod 2).

Proof. The proof is parallel to the proof of Theorem 3.3. Instead of (3.6) and (3.7), we take

x̃_{s}(k) = (k + Dα − D)^{s}  (4.1)

and

p̃_{s}(k) = \frac{1}{2}((k + Dα)^{r} (k + D)^{s} − (k − Dα)^{r} (k − D)^{s}),  (4.2)

so that (3.5) still holds. It is clear that x̃_{s}(k), p̃_{s}(k) ∈ ℤ[k]. But in this case, p̃_{s}(k) is not monic. The leading term of p̃_{s}(k) is

(αr + s)D · k^{s+r−1}.

Now let us consider the reduction process. Let p(k) ∈ ℤ[k] be a polynomial of degree ℓ ≥ r − 1. Assume further that p(k) contains only even powers of k or only odd powers of k. Setting

p′(k) = lc p̃_{ℓ−r+1}(k) · p(k) − lc p(k) · p̃_{ℓ−r+1}(k)
= (αr + ℓ − r + 1)D · p(k) − lc p(k) · p̃_{ℓ−r+1}(k),

we see that p′(k) ∈ ℤ[k] and deg p′(k) < ℓ. Since p̃_{ℓ−r+1}(k) contains only even powers of k or only odd powers of k, so does p′(k). Therefore, deg p′(k) ≤ ℓ − 2.

Continuing this reduction process until ℓ < r − 1, we finally obtain that there exist integers c_{m}, c_{m−2}, … such that

C_{m}k^{m} − c_{m}p̃_{m−r+1}(k) − c_{m−2}p̃_{m−r−1}(k) − ⋯,

is a polynomial of degree less than r −1 and with integral coefficients, where C_{m} is the product of the leading coefficient of p̃_{m−r+1}(k), p̃_{m−r−1}(k), …

C_{m} = ∏_{0≤2i≤m−r+1} ((αr + m − r + 1 − 2i)D) ,

as desired.

For the special case of t_{k} = (1/2)_{k}^{4}/(1)_{k}^{4}, we may further reduce the factor C_{m}.

Lemma 4.4 Let m be a positive integer and

t_{k} = \frac{(1/2)_{k}^{4}}{(1)_{k}^{4}} .

• If m is odd, then there exist an integer c and a polynomial x(k) ∈ ℤ[k] such that

(4k + 1)^{m}t_{k} = \frac{c}{C′_{m}} (4k + 1)t_{k} + \frac{1}{C′_{m}} Δ_{k} (32k^{4}x(4k)t_{k}) ,

where C′_{m} = (\frac{m−1}{2})!.

• If m is even, then there exist integers c, c′ and a polynomial x(k) ∈ ℤ[k] such that

(4k + 1)^{m}t_{k} = \frac{1}{C′_{m}} (c + (4k + 1)^{2}c′)t_{k} + \frac{1}{C′_{m}} Δ_{k} (64k^{4}x(4k)t_{k}) ,

where C′_{m} = (m − 1)!!.

Proof. This is the special case of Theorem 4.3 for α = 1/2 and r = 4. Therefore, D = 2 and αr − r + 1 = −1.

We need only to show that the coefficients of p̃_{s}(k) given by (4.2) is divisible by 2 when s is odd and is divisible by 4 when s is even. Then we may replace x̃_{s}(k) given by (4.1) by x̃_{s}(k)/4 and x̃_{s}(k)/2 so that the leading coefficient of p̃_{s}(k) is reduced. Correspondingly, the product C_{m} of the leading coefficients becomes

∏_{0≤2i≤m−3} \frac{1}{2} lc p̃_{m−3−2i}(k) = ∏_{0≤2i≤m−3}(m − 1 − 2i) = (m − 1)!!, m even,

and

∏_{0≤2i≤m−3} \frac{1}{4} lc p̃_{m−3−2i}(k) = ∏_{0≤2i≤m−3} \frac{m − 1 − 2i}{2} = (\frac{m − 1}{2})!, m odd.

Notice that

p̃_{s}(k) = \frac{1}{2}((k + 1)^{4} (k + 2)^{s} − (k − 1)^{4} (k − 2)^{s}).

The coefficient of k^{j} is

\frac{1 − (−1)^{s−j}}{2} ∑_{0≤ℓ≤4, 0≤j−ℓ≤s} \binom{4}{ℓ}\binom{s}{j − ℓ}2^{s−j+ℓ}.

If j − ℓ < s, the corresponding summand is divisible by 2. If j − ℓ = s and ℓ is even, then (−1)^{s−j} = 1 and the coefficient is 0. Otherwise, ℓ = 1 or ℓ = 3, and thus 4 | \binom{4}{ℓ}. Therefore, the coefficient must be divisible by 2.

Now consider the case of s being even. If j −ℓ < s−1, the corresponding summand is divisible by 4. Otherwise j − ℓ = s or j − ℓ = s − 1. We have seen that if j − ℓ = s, then the coefficient is divisible by 4. If j − ℓ = s − 1. Then

\binom{s}{j − ℓ} = s and 2^{s−j+ℓ} = 2.

Thus the summand is also divisible by 4.

Example 4.2 Consider the case of m = 11. We have

(4k + 1)^{11}t_{k} + 10515(4k + 1)t_{k} = Δ_{k}(32k^{4}p(k)t_{k})

where

p(k) = \frac{1}{5}(4k−1)^{8}− \frac{249}{20}(4k−1)^{6}+ \frac{20207}{60}(4k−1)^{4}− \frac{89909}{20}(4k−1)^{2}+ \frac{524029}{20}.

As an application, we obtain the following congruences.

Theorem 4.5 Let m be a positive odd integer and μ = (m − 1)/2. Denote

S_{m} = ∑_{k=0}^{\frac{p−1}{2}}(4k + 1)^{m} (\frac{(1/2)_{k}}{(1)_{k}} )^{4} .

Then there exists an integer a_{m} such that for each prime p > μ,

S_{m} ≡ \frac{a_{m}}{μ!} p (mod p^{4}).

Proof. By Lemma 4.4, there exist an integer a_{m} and a polynomial q_{m}(k) ∈ ℤ[k] such that

(4k + 1)^{m}t_{k} − \frac{a_{m}}{μ!} (4k + 1)t_{k} = \frac{1}{μ!}Δ_{k} (32k^{4}q_{m}(k)t_{k}) ,

where t_{k} = (\frac{(1/2)_{k}}{(1)_{k}} )^{4}. Summing over k from 0 to (p − 1)/2, we obtain

S_{m} − \frac{a_{m}}{μ!} S_{1} = 32ω^{4} \frac{q_{m}(4ω)}{μ!} (\frac{(1/2)_{ω}}{(1)_{ω}} )^{4} ,

where ω = (p + 1)/2. When p > μ, 1/μ! is a p-adic integer and

(\frac{(1/2)_{ω}}{(1)_{ω}} )^{4} ≡ 0 (mod p^{4}).

Therefore,

S_{m} ≡ \frac{a_{m}}{μ!} S_{1} (mod p^{4}).

It is shown by Long [12] that

S_{1} ≡ p (mod p^{4}),

completing the proof.

The integer a_{m} and the polynomial q_{m}(k) can be computed by the extended Zeilberger’s algorithm.

By checking the initial values, we propose the following conjecture.

Conjecture 4.6 For any positive odd integer m, the coefficient a_{m}/(\frac{m−1}{2})! is an integer.

Acknowledgement. The work was supported by the National Natural Science Foundation of China (grants 11471244, 11771330 and 11701420).

References

[1] S.A. Abramov, The rational component of the solution of a first-order linear recurrence relation with rational right-hand side, Comput. Math. Math. Phys. 15 (1975) 1035–1039.

[2] S.A. Abramov, Indefinite sums of rational functions, in: Proc. ISSAC95, ACM Press, New York, 1995, 303–308.

[3] S.A. Abramov and M. Petkovšek, Minimal decomposition of indefinite hypergeometric sums, in: Proc. ISSAC2001 ACM Press, New York, 2001, 7–14.

[4] S.A. Abramov and M. Petkovšek, Rational normal forms and minimal decompositions of hypergeometric terms, J. Symbolic Comput. 33 (2002) 521–543.

[5] S. Ahlgren and K. Ono, A Gaussian hypergeometric series evaluation and Apéry number congruences, J. reine angew. Math. 518 (2000) 187– 212

[6] S. Chen, H. Huang, M. Kauers, and Z. Li, A modified Abramov-Petkovšek reduction and creative telescoping for hypergeometric terms, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. ACM, 2015, p. 117–124.

[7] W. Y. C. Chen, Q.-H. Hou, and Y.-P. Mu, The extended Zeilberger algorithm with parameters, J. Symbolic Comput. 47(6) (2012) 643– 654.

[8] V.J.W. Guo, Some generalizations of a supercongruence of van Hamme, Integral Transforms Spec. Funct. 28(12) (2017) 888–899.

[9] V.J.W. Guo, Common q-analogues of some dif-

ferent  supercongruences,  Results  Math.,  in  press;

https://doi.org/10.1007/s00025-019-1056-1.

[10] A. Jana and G. Kalita, Supercongruences for sums involving rising factorial (\frac{1}{ℓ})_{k}^{3}, Integral Transforms Spec. Funct., in press;

https://doi.org/10.1080/10652469.2019.1604700.

[11] J.-C. Liu, Semi-automated proof of supercongruences on partial sum of hypergeometric series, J. Symbolic Comput., to appear.

[12] L. Long, Hypergeometric evaluation identities and supercongruences, Pac. J. Math. 249 (2011) 405–418.

[13] E. Mortenson, A p-adic supercongruence conjecture of van Hamme. Proc. Am. Math. Soc. 136 (2008) 4321–4328.

[14] R. Osburn and C. Schneider, Gaussian hypergeometric series and supercongruences, Math. Comp. 78(265) (2009) 275–292.

[15] R. Pirastu and V. Strehl, Rational summation and Gosper-Petkovsek representation, J. Symbolic Comput. 20 (1995) 617–635.

[16] Z.-W. Sun, On sums related to central binomial and trinomial coefficients, in: M. B. Nathanson (ed.), Combinatorial and Additive Number Theory: CANT 2011 and 2012, Springer Proc. in Math. & Stat., Vol. 101, Springer, New York, 2014, pp. 257–312.

[17] Z.-W. Sun, A refinement of a congruence result by van Hamme and Mortenson, Ill. J. Math. 56 (2012) 967–979.

[18] Z.-W. Sun, Supecongruences involving products of two binomial coefficients, Finite Fields Appl. 22 (2013) 24–44.

[19] L. van Hamme, Some conjectures concerning partial sums of generalized hypergeometric series, in: p-adic Functional Analysis (Nijmegen, 1996), pp. 223–236, Lecture Notes in Pure and Appl. Math., Vol., 192, Dekker, 1997.

[20] S.-D. Wang, Some supercongruences involving \binom{2k}{k}^{4}, J. Differ. Equ. Appl., to appear.

[21] W. Zudilin, Ramanujan-type supercongruences. J. Number Theory 129 (2009) 1848–1857.