A conjecture in the problem of rational definite summation

Mark van Hoeij

October 10, 2002

Abstract

A conjecture is given that, if true, could lead to an algorithm for computing definite sums of rational functions.

1 The conjecture

Let C be a field of characteristic 0, not necessarily algebraically closed. Let n, k be variables, and consider the ring C(n)[k] of polynomials in k, whose coefficients are rational functions in n.

For all a, b, c ∈ Q with a ≠ 0 we define the C(n)-algebra homomorphism

ψ_{a,b,c} : C(n)[k] → C(n)[k]

as follows:

ψ_{a,b,c}(k) = ak + bn + c.

If B_{1}, B_{2} are irreducible elements of C(n)[k], then we define the following equivalence relation: B_{1} ∼_{p} B_{2} if there exist a, b, c ∈ Q, with a ≠ 0 such that ψ_{a,b,c}(B_{1}) = sB_{2} for some unit s (i.e. s is a nonzero element of C(n)).

Let F ∈ C(n, k) be a nonzero rational function in n and k. The partial fraction decomposition of F = F (n, k) over C(n) has the following form:

F = Q + F_{1} + ⋯ + F_{t}

where Q ∈ C(n)[k], and each F_{i} is a partial fraction term which means the following: there exist a positive integer d_{i}, non-zero A_{i}, B_{i} ∈ C(n)[k] with degree_{k}(A_{i}) < degree_{k}(B_{i}), with B_{i} irreducible, such that

F_{i} = A_{i}/B_{i}^{d_{i}}.

We call two partial-fraction-terms F_{i} and F_{j} equivalent F_{i} ∼ F_{j} when

d_{i} = d_{j} and B_{i} ∼_{p} B_{j}.

Suppose that there are u distinct equivalence classes among F_{1}, …, F_{t}, and number these equivalence classes 1, …, u. Let G_{i} be the sum of all F_{j} in the i’th equivalence class. So we can write

F = Q + G_{1} + ⋯ G_{u}.

Now ∑_{k=0}^{n} F (n, k) is a function in just one variable n. This function is only defined for nonnegative integers n for which the denominator of F (n, k) does not vanish for any k ∈ {0, 1, …, n}. Now assume that this is the case for n ≫ 0.

The question now is: Under this assumption, how to decide if this function ∑_{k=0}^{n} F is a rational function? More precisely: is there a rational function R(n) ∈ C(n) that takes the same values as ∑_{k=0}^{n} F whenever both are defined?

Conjecture: If ∑_{k=0}^{n} F is a rational function, then so is ∑_{k=0}^{n} G_{i} for every i ∈ {1, …, u}.

The conjecture says that the problem of deciding if ∑_{k=0}^{n} F is a rational function (and if so, finding that rational function) can be reduced to the same question for the ∑_{k=0}^{n} G_{i}. This reduces the rational summation problem to a set of smaller summation problems ∑_{k=0}^{n} G_{i}, each of which involves only one equivalence class of partial-fraction-terms.

2 A few remarks

Let B be an irreducible element of C(n)[k]. Define Aut(B) as the set of all ψ_{a,b,c} with a, b, c ∈ Q, a ≠ 0, such that ψ_{a,b,c}(B) = sB for some unit s. It is easy to see that Aut(B) is a group under composition, and that the map

π : Aut(B) → Q^{∗}

sending ψ_{a,b,c} to a is an injective group homomorphism. From this it follows that Aut(B) has either 1, 2, or ∞ many elements. We call B of generic type if Aut(B) has 1 element, symmetric type if Aut(B) has 2 elements, and rational type if Aut(B) has ∞ many elements. Note that B is of rational type if and only if B ∼_{p} k.

G_{i} is a sum of equivalent terms A_{j}/B_{j}^{d_{j}}. We call G_{i} of generic, symmetric, resp. rational type if the B_{j} appearing in G_{i} are of generic, symmetric, resp. rational type. In order to calculate ∑_{k=0}^{n} G_{i} it helps to distinguish these three types. The rational type allows more kinds of cancelations among equivalent terms A_{j}/B_{j}^{d_{j}} than the symmetric type, which in turn allows more kinds of cancelations than the generic type. We give an example of cancelation for the generic type: Let B(n, k) be an arbitrary irreducible polynomial. For example, B(n, k) = k^{3} + kn + 1. Consider:

\frac{1}{B(n, k)} − \frac{1}{B(n, n − k)}  (1)

or

\frac{1}{B(n, k)} + \frac{1}{B(n, k + n + 1)} − \frac{1}{B(n, 2k)} − \frac{1}{B(n, 2k + 1)}.  (2)

These are non-zero rational functions, whose ∑_{k=0}^{n} is 0. The algorithm in [1] would detect cancelations like the one in equation (1) but not cancelations like the one in (2). This problem was the starting point for this paper.

The rational and symmetric types allow additional kinds of cancelation. Here is an example for the rational type:

1/(k + 1) + 2/(k + 2 + n) − 2/(2k + 1)

has sum 0 because it can be rewritten as

2/(k + 1) + 2/(k + 2 + n) − 2/(2k + 1) − 2/(2k + 2).

We can give examples where the sum is a non-zero rational function by modifying the above examples in such a way that all but a constant number of terms cancel. For example, the sum of:

1/(k + 3) + 2/(k + 2 + n) − 2/(2k + 1)  (3)

differs from the sum of 1/(k + 1) + 2/(k + 2 + n) − 2/(2k + 1) (which was 0) by D = 1/(n + 3) + 1/(n − 1 + 3) − 1/(0 + 1) − 1/(1 + 1). To develop an algorithm for rational definite summation, one must identify all possible cancelations and write procedures for each of them. Then, for inputs such as (3), the algorithm must determine if this input can be modified into something that has sum 0, and if so, calculate the difference D like in the example. One could then try to prove that the algorithm completely solves the problem, that it determines for F ∈ C(n, k) if ∑_{k=0}^{n} F is a rational function or not, and if so, finds that rational function. For a preliminary implementation of this algorithm, see: http://www.math.fsu.edu/˜ hoeij/SumRat/ It implements several kinds of cancelations. It is not clear (even if one assumes the conjecture) if this algorithm is complete or not.

A second question: Suppose that the denominator of F has no irreducible factors B ∈ C[n, k] for which there exists P ∈ C[k] with B ∼_{p} P. Suppose furthermore that R(n) := ∑_{k=0}^{n} F (n, k) satisfies a linear recurrence relation ∑_{i=0}^{m} a_{i}(n)R(n + i) = 0 for some polynomials a_{i}(n) ∈ C[n], not all zero. Does it then follow that R(n) is a rational function?

3 An example

Let

B := k + n(n + 1)/2, F := 1/B, R(n) := ∑_{k=0}^{n} F where n > 0.

Then R(n) does not satisfy a linear recurrence with polynomial coefficients.

Proof: Suppose that m is a positive integer and that a_{0}(n), …, a_{m}(n) are in Z[n] such that ∑_{i=0}^{m} a_{i}(n)R(n + i) is identically 0.

Let S_{n} be the set {n(n + 1)/2, 1 + n(n + 1)/2, …, n + n(n + 1)/2}, so R(n) = ∑_{i∈S_{n}} 1/i. Let A_{n}, B_{n} be positive integers, with A_{n}/B_{n} = R(n) and gcd(A_{n}, B_{n}) = 1. The sets S_{1}, S_{2}, … are disjoint and their union is the set of all positive integers. Define p_{n} as the product of all prime numbers in S_{n}. For 0 < i < n, these primes are larger than max(S_{i}), so gcd(p_{n}, B_{i}) = 1.

Assume that a_{0}(n), …, a_{m}(n) ∈ Z[n], and that a_{m}(n) is not identically zero. Then there exists an integer n_{1} such that a_{m}(n) ≠ 0 for all n > n_{1}. If ∑_{i=0}^{m} a_{i}(n)R(n + i) = 0 then a_{m}(n) must be divisible by p_{m+n} because the factors of p_{m+n} appear in the denominator of R(m + n) but not in the denominators of R(n), R(n + 1), …, R(m − 1 + n). Hence p_{m+n} ≤ |a_{m}(n)|. Since each prime factor in p_{m+n} is > \frac{1}{2}n^{2} we see that the number of primes in S_{m+n} is at most ln(|a_{m}(n)|)/ln(\frac{1}{2}n^{2}), which tends to degree(a_{m})/2 for large n. This means that the density of primes in S_{n} is much less than 1/ln(max(S_{n})), contradicting the prime number theorem (note that S_{1}, S_{2}, … are disjoint and their union is the set of all positive integers).

One sees by induction that a_{m−1}, …, a_{0} must be identically 0 as well. So R(n) does not satisfy any nonzero linear recurrence relation over Z[n]. There can not exist a recurrence relation over C[n] either, because if K ⊂ C is the coefficient field of such a recurrence relation, then one can reduce the transcendence degree of the finitely generated field K by switching to a residue field of a valuation. After finitely many steps, we may assume that the transcendence degree is 0, so K is a number field, Then one can multiply the recurrence by an element of K in order to create at least one polynomial a_{i}(n) with leading coefficient 1. Then, after taking the trace over the field of rational numbers, one obtains a nonzero recurrence over Q[n], and by multiplying out the denominators one obtains a recurrence over Z[n]. Hopefully primes (or prime ideals) could be used for the conjecture as well.

Acknowledgments: I would like to thank Sergei Abramov, Ha Le, Sergei Tsarev and Eugene Zima for discussions on these topics.

References

[1] H.Q. Le. Simplification of Definite Sums of Rational Functions by Creative Symmetrizing Method. Proceedings ISSAC’2002, ACM Press, p. 161–167, (2002).