Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 2, 531-536.

Rational Summation of Rational Functions

Laura Felicia Matusevich

University of California at Berkeley e-mail: laura@math.berkeley.edu

Abstract. In this article we characterize rational functions for which their indefinite sum is again a rational function.

1. Introduction

Let k be a field of characteristic 0 and let r be a rational function in one variable over k. Pick an integer j_{0} such that r(j) is defined for j ≥ j_{0}, and consider

y_{x} = ∑_{j=j_{0}}^{x} r(j), x > j_{0}.

If there exists a rational function y such that y(x) = y_{x} for all x > j_{0}, we say that r is rationally summable. Notice that r is rationally summable if and only if the difference equation

Δy = y(x + 1) − y(x) = r(x)  (1)

has a solution in the field k(x) of rational functions in one variable. Of course, this is equivalent to requiring the equation

∇t = t(x) − t(x − 1) = r(x)

to have a rational solution.

We consider the question, suggested by Alberto Grünbaum, of finding necessary and sufficient conditions for rational summability. This is accomplished in Theorems 10 and 11.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

The rational summation problem has been studied by Abramov ([1]), Paule ([2] and [3]), Pirastu and Strehl ([4] and [5]). These authors give algorithms, based on either the Gosper-Petkovšek representation or the shift saturated representation of a rational function, to decide whether a rational function is rationally summable or not. In the affirmative case, a rational solution to (1) is found. Otherwise, the output is a rational function, closest to a solution of (1) in some suitable sense.

Example 1. Let r be a polynomial of degree d in k[x]. We can write r(n) = ∑_{i=0}^{d} a_{i}\binom{n}{i}, where a_{i} ∈ k. Define y(n) = ∑_{i=0}^{d} a_{i}\binom{n}{i+1}. Then Δy = r.

In view of the division algorithm and Example 1, we assume from now on that r = p/q, with p, q polynomials, and deg(p) < deg(q).

2. Characterizing rational summability

We define the forward shift operator, denoted by σ. That is,

(σy)(n) = y(n + 1).

Definition 2. Let f be a polynomial. The dispersion of f is

disp f = max{|l| : l ∈ Z , gcd(f, σ^{l}f) ≠ 1}
= max\{|a − b| : a, b ∈ \overline{k} are roots of f and a − b ∈ Z\}

where \overline{k} is an algebraic closure of k. If disp f = 0, then we say that f is shift-free.

The concept of dispersion was first introduced by Abramov ([1]).

Lemma 3. Let y ∈ k(x) and 0 ≠ Δy = \frac{P}{Q}, with P and Q not necessarily coprime polynomials. Then disp Q > 0.

Proof. Say y = f/g in lowest terms (that is, f and g are relatively prime polynomials). Let a be a root of g (in an algebraic closure of k), and t a nonnegative integer such that g(a−t) = 0, but g(a + 1) and g(a − t − 1) are nonzero. We claim that Q(a) = Q(a − t − 1) = 0. Thus disp Q ≥ t + 1 > 0. To see this, look at

\frac{P}{Q} = Δ\frac{f}{g} = \frac{g(x)f(x + 1) − g(x + 1)f(x)}{g(x)g(x + 1)}

The numbers a and a − t − 1 are roots of g(x)g(x + 1), but not of g(x)f(x + 1) − g(x + 1)f(x), so the factors (x − a), (x − a + t + 1) of g(x)g(x + 1) could not have been cancelled. □

Now we investigate the rational summability of functions of the form

r = ∑_{i=0}^{l−1} \frac{p_{i}}{σ^{−i}q} ; p_{i}, q ∈ k[x]

where the numerators and denominators are not necessarily coprime.

Lemma 4. Let r = ∑_{i=0}^{l−1} p_{i}/σ^{−i}q. Consider the rational function

r^{∗} = ∑_{i=0}^{l−1} \frac{σ^{i}p_{i}}{q} = \frac{∑_{i=0}^{l−1} σ^{i}p_{i}}{q} .

Then r is rationally summable if and only if r^{∗} is rationally summable.

Proof. First notice that r − σ^{−l}r^{∗} is rationally summable. To see this write:

r − σ^{−l}r^{∗} = ∑_{i=0}^{l−1} (\frac{p_{i}}{σ^{−i}q} − σ^{i−l} (\frac{p_{i}}{σ^{−i}q} )) .

Call s_{i} = p_{i}/σ^{−i}q. The telescoping identity

s_{i} − σ^{i−l}s_{i} = ∑_{j=0}^{l−i−1}(σ^{−j}s_{i} − σ^{−j−1}s_{i}) = ∇ ( ∑_{j=0}^{l−i−1} σ^{−j}s_{i})

implies that each summand of r −σ^{−l}r^{∗} is rationally summable, so that r −σ^{−l}r^{∗} is rationally summable as well.

Pick a rational function s such that r − σ^{−l}r^{∗} = Δs. If r is rationally summable, then there exists a rational function y with Δy = r. This means that Δ(y − s) = σ^{−l}r^{∗}, and hence r^{∗} = Δσ^{l}(y − s). Conversely, if r^{∗} is rationally summable, then there exists a rational function u such that Δu = r^{∗}. Hence r = Δ(s − σ^{−l}u). □

Proposition 5. Let r = ∑_{i=0}^{l−1} p_{i}/σ^{−i}q, and suppose q is shift-free. Then r is rationally summable if and only if p_{0} + σp_{1} + ⋯ + σ^{l−1}p_{l−1} = 0. In that case, the rational function

y := ∑_{i=0}^{l−2} \frac{∑_{j=0}^{i} σ^{j−(i+1)}p_{j}}{σ^{−(i+1)}q}

satisfies Δy = r.

Proof. Assume that r is rationally summable. By Lemma 4, so is r^{∗}, whose denominator is shift-free. From Lemma 3 we conclude that r^{∗} = 0, so that ∑_{i=0}^{l−1} σ^{i}p_{i} = 0. The converse follows by direct verification of the formula for y. □

Notice that if we do not assume q to be shift-free, the previous condition is still sufficient, but no longer necessary, as the following example shows.

Example 6. Let

r(x) = \frac{−(x + 1)(x − 2)}{(x + 1)x(x − 1)(x − 2)} + \frac{−3}{x(x − 1)(x − 2)(x − 3)}.

The condition of Proposition 5 is not satisfied; however,

r = Δ (\frac{1}{x(x − 1)(x − 2)} + \frac{1}{x(x − 1)}) .

The goal now is to break up any given r ∈ k(x) into summands of the form of Proposition 5. If f is a polynomial, we denote:

[f]\underline{l} = f (σ^{−1}f) ⋯ (σ^{−(l−1)}f).

Definition 7. Two polynomials f and g are called shift-coprime if

gcd(σ^{i}f, g) = 1 ∀i ∈ Z.

Take r = p/q written in lowest terms, with q monic. We want to have control over the factors of q that differ by an integer. To achieve that, we are going to replace q by a polynomial Q = [Q_{1}]\underline{1} ⋯ [Q_{l}]\underline{l} such that:

1. q divides Q.

2. The polynomials Q_{i} are all shift-free and pairwise shift-coprime.

Following Peter Paule, such a Q is called a shift-saturated multiple of q. For any polynomial, there is a unique shift-saturated multiple of minimal degree. An algorithm for calculating it was proposed in [2]. Unfortunately, the RISC report is not available, and the algorithm does not appear in the published version ([3]). Paule’s algorithm has been implemented in Mathematica by Christian Mallinger, and it is from the comments in the code (kindly sent to me by Peter Paule) that the reference to [2] was obtained. Another algorithm can be found in [4].

Example 8. Let

q = x(x − 10)^{15}(x − 17)(x − 25)^{2}(x − 1/2)(x − 3/2)(x − 1/3)(x − 4/3)^{2}(x − 1/5).

The polynomials

Q = [x − 1/5][(x − 1/2)(x − 1/3)^{2}]\underline{2}[x^{15}]\underline{26}

and

Q′ = [x − 1/5][((x − 1/2)(x − 1/3))^{2}]\underline{5}[(x − 1/7)x^{15}]\underline{26}

are shift-saturated multiples of q. Among all such multiples, Q has minimal degree.

Now suppose r = p/q. Compute Q = [Q_{1}]\underline{1} ⋯ [Q_{l}]\underline{l} a shift-saturation of q. Then r = H/Q for H = pQ/q. Since the Q_{i} are pairwise shift-coprime, we can write (using the extended gcd):

r = ∑_{i=1}^{l} \frac{h_{i}}{[Q_{i}]\underline{i}}

for some polynomials h_{i}.

Proposition 9. An r as above is rationally summable if and only if all h_{i}/[Q_{i}]\underline{i} are rationally summable.

Proof. The following claim gives a slightly stronger statement than what we need for an induction on l. Let R = R_{1} + R_{2} ∈ k(x); R_{i} = p_{i}/q_{i}, with q_{1} and q_{2} shift coprime. Then R is rationally summable if and only if R_{1} and R_{2} are rationally summable. The “if” implication is trivial. For the “only if”, we assume that R_{i} are in lowest terms (cancellation does not effect shift-coprimeness). Let y = f/g, with f, g coprime, such that Δy = R. Then g = ABC, where A = ∏(x − α)^{e_{α}}, over the α that are the roots of g (in \overline{k}) and of some integer shift of q_{1}; analogously for B and q_{2}, and C is the leftover. Notice that A, B, C are polynomials over k, because A = gcd(g, ([q_{1}]\underline{t+1})^{N}), for t = disp q_{1}, and N a sufficiently large integer. Likewise for B.

As q_{1} and q_{2} are shift coprime, A, B and C are pairwise relatively prime. Then we can write (using the extended gcd) y = \frac{A_{1}}{A} + \frac{B_{1}}{B} + \frac{C_{1}}{C} , for some polynomials A_{1}, B_{1}, C_{1}, and then

0 = Δy − R = (Δ\frac{A_{1}}{A} − R_{1}) + (Δ\frac{B_{1}}{B} − R_{2}) + Δ\frac{C_{1}}{C} .

So we have three rational functions that add up to zero, and whose denominators are pairwise coprime. Taking into account that the denominators of the first two summands are nonconstant (since the q_{i} are nonconstant) we see that this cannot happen unless those rational functions are zero. In particular R_{1} = Δ\frac{A_{1}}{A} and R_{2} = Δ\frac{B_{1}}{B}. □

Theorem 10. Let r = ∑_{i=1}^{l} h_{i}/[Q_{i}]\underline{i} in the form of Proposition 9. In particular, the Q_{i} are shift free, so that the σ^{−j}Q_{i} are relatively prime. Using the extended gcd, write

r = ∑_{i=1}^{l} ∑_{j=0}^{i−1} \frac{p_{i,j}}{σ^{−j}Q_{i}}

Then r is rational summable if and only if p_{i,0} + σp_{i,1} + ⋯ + σ^{i−1}p_{i,i−1} = 0 for all i. In that case, the rational function:

y := ∑_{i=1}^{l} ∑_{t=0}^{i−2} \frac{∑_{j=0}^{t} σ^{j−(t+1)}p_{i,j}}{σ^{−(t+1)}Q_{i}}

satisfies Δy = r.

Proof. Propositions 5 and 9. □

3. Remarks

• Given r = p/q, it is possible (even symbolically) to find a shift free multiple of q, so that multiplying and dividing by an adequate polynomial, Proposition 5 applies. However, the denominator in such a representation of r will have much larger degree than the one we get by using Theorem 10.

• If we know the complete partial fraction decomposition of our rational function, the previous results can be restated as follows:

Theorem 11. Suppose we are given:

r(x) = ∑_{n=1}^{l} ∑_{i=0}^{s} ∑_{j=1}^{e} \frac{A_{n,i,j}}{(x − α_{n} − i)^{j}}

where α_{n} − α_{m} is not an integer for n ≠ m and the A_{n,i,j} are (not necessarily nonzero) constants. Then r is rational summable if and only if ∑_{i=0}^{s} A_{n,i,j} = 0 for all j, n. In that case, the rational function

y(x) = ∑_{n=1}^{l} ∑_{j=1}^{e} ∑_{t=1}^{s} \frac{∑_{i=0}^{t−1} A_{n,i,j}}{(x − α_{n} − t)^{j}}

satisfies Δy = r.

Proof. The difficult implication is a straightforward consequence of Propositions 5 and 9. □

Acknowledgements. I am very grateful to Alberto Grünbaum, Peter Paule, Marko Petkovšek, Michael Singer and Bernd Sturmfels for their help and encouragement, and to Alicia Dickenstein, for her advice and comments. I would also like to thank the reviewer, who suggested Lemma 4, and greatly improved the presentation. This work was partially supported by the David and Lucile Packard Foundation.

References

[1] Abramov, S. A.: The Rational Component of the Solution of a First-Order Linear Recurrence Relation with a Rational Right Side. Zh. vychisl. Mat. mat. fis. no. 4, 15 (1975), 40–42.

[2] Paule, Peter: Greatest Factorial Factorization and Symbolic Summation 1. RISC-Linz Report Series No. 93-02 (1993).

[3] Paule, Peter: Greatest Factorial Factorization and Symbolic Summation. J. Symbolic Computation 20 (1995), 235–268.

[4] Pirastu, Roberto: Algorithmen zur Summation rationaler Funktionen (in German). Diploma thesis, University of Erlangen-Nürnberg 1992.

[5] Pirastu, Roberto; Strehl, Volker: Rational Summation and the Gosper-Petkovšek Representation. J. Symbolic Computation 20 (1995), 617–635.

Received June 29, 1999