A Note On the Minimality Problem in Indefinite Summation of Rational Functions

Roberto Pirastu^{∗}

Research Institute for Symbolic Computation, J. Kepler University, A-4040 Linz

1 Introduction

Consider a field K of characteristic zero. The shift operator E on K(x) is defined by Ef(x) := f(x + 1) for all f ∈ K(x). The (forward) difference operator is defined by Δ := E − 1, where 1 operates identically. Then the problem of indefinite summation of rational functions can be stated as follows. Problem: Given a proper rational function f ∈ K(x), find h, r ∈ K(x) such that

f = Δh + r  (1)

and the denominator of r has minimal degree among all such decompositions. We call the pair (h, r) a solution of the indefinite summation problem for f and call r a bound for f.

Each solution (h, r) in (1) corresponds to the following decomposition

g(a, b) := ∑_{k=a}^{b} f(k) = h(b + 1) − h(a) + ∑_{k=a}^{b} r(k)  (2)

In particular, a solution of (1) with remainder r = 0 provides a closed form for g as a rational expression in a and b, namely g(a, b) = h(b + 1) − h(a).

Several algorithms are known for computing solutions of the indefinite rational summation problem (see [2, 1, 3]). Note that giving an “Ansatz” for the denominators of h and r reduces equation (1) to a polynomial equation, which can be solved by coefficient comparison.

Here we describe such candidates for the denominators of h and r which depend only on the denominator of f. For a certain class of rational summands f the given estimates are precise.

Solutions (h, r) are not uniquely determined by f. For instance, the decompositions

Δ (−\frac{1}{4} \frac{2x + 1}{x(x + 1)}) − \frac{1}{2(x^{2} + 4x + 4)}  and  Δ (−\frac{1}{4} \frac{2x^{3} + 7x^{2} + 5x + 2}{x^{2}(x + 1)^{2}}) − \frac{1}{2x^{2}}

are different solutions for the same rational summand f = \frac{1}{x(x+2)^{2}} . As one can see, the degree of the denominator of h can vary considerably among solutions. For this reason we are interested in solutions (h, r) with both h and r of minimal degree in the denominator. Our observations prove that the modification of Abramow’s algorithm proposed in [4, 5] produces such minimal solutions for a certain class of rational summands.

∗Supported by the Commission of the European Communities in the frame of the program “Human Capital and Mobility”, contract Nr. ERBCHBICT930501.

In the following we make use of known results due to Abramow and Paule (see [1, 3]), to which we refer for an extensive treatment of the subject.

We say that two polynomials p_{1} and p_{2} are shift equivalent if p_{1} = E^{k}p_{2} for some integer k. In this case we write p_{1} ∼ p_{2}. Consider, for a polynomial p ∈ K[x], the complete factorization (over K) p = αp_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{m}^{e_{m}}, where all p_{i} are irreducible and monic and e_{1} ⋯ e_{m} ≠ 0, α ∈ K. Then an equivalence class of the set of irreducible factors {p_{1}, …, p_{m}} of p under the relation ∼ is called a shift class of p. A factor p̃ = p_{i_{1}}^{e_{i_{1}}} ⋯ p_{i_{l}}^{e_{i_{l}}} of p is called a shift component of p if the set {p_{i_{1}}, …, p_{i_{l}}} is a shift class of p.

Example 1 Consider the polynomial p ∈ Q[x] given by the following factorization

p(x) = (x^{2} + 3)(x^{2} + 2x + 4)x(x + 1)^{2}(x + 3)(x + 5)^{2}

then the set {x, x + 1, x + 3, x + 5} is a shift class of p and p̃ = x(x + 1)^{2}(x + 3)(x + 5)^{2} is the corresponding shift component.

Define on the polynomials in a shift class the order < by: q < q′ if there exists a positive integer k such that E^{k}q = q′. We can represent graphically the shift structure of a shift class. For instance Fig. 1 represents the situation for p̃ of Example 1.

Figure 1: Shift structure of x(x + 1)^{2}(x + 3)(x + 5)^{2}

We draw d squares at the i-th position on a line when the polynomial E^{i}q_{0} arises with multiplicity d as a factor of p̃, where q_{0} denotes the smallest polynomial w.r.t. the order < in the shift class.

Definition 1 The dispersion of a polynomial p is the maximal integer distance between roots of p and is denoted by dis(p).

For a proper rational function given by a reduced representation f = p/q, i.e. p and q are relatively prime polynomials, we define dis(f) = dis(q). In Example 1 we have dis(p) = 5, viz. the maximal distance between stacks.

Lemma 1 For f ∈ K(x) let h, r ∈ K(x) be such that f = Δh + r holds. Then r is a bound for f if and only if dis(r) = 0.

This means that the problem of indefinite summation is solved for decompositions f = Δh+r where dis(r) = 0, i.e. where each shift component of the denominator of r has only one stack of boxes in the corresponding diagram.

As we saw, solutions of the indefinite summation are not uniquely determined. In the next theorem, due to Paule, uniqueness up to integer shifts of the denominator of the remainders is stated.

Theorem 1 Let r, r′ ∈ K(x) be bounds for f ∈ K(x), given by the reduced representations r = p/q, r′ = p′/q′. If q = q_{0}^{e_{0}} ⋯ q_{m}^{e_{m}} is the complete factorization of q over K, then q′ = (E^{l_{0}}q_{0}^{e_{0}}) ⋯ (E^{l_{m}}q_{m}^{e_{m}}) for some integers l_{0}, …, l_{m}.

2 The Shift-Structure of the Denominator of Δh

In the next section we will discuss the shift-structure of the denominators of (h, r) in equation (1). In anticipation of this, we will now explicitly make some remarks on the denominator of the rational function Δh for a given h.

In the following let h ∈ K(x) be given by a reduced representation h = γ/δ. Then we have

Δh = E \frac{γ}{δ} − \frac{γ}{δ} = \frac{\frac{\frac{δ}{τ} Eγ − γ \frac{Eδ}{τ}}{τ_{0}}}{\frac{δEδ}{ττ_{0}}} = \frac{\frac{\frac{δ}{τ} Eγ − γ \frac{Eδ}{τ}}{τ_{0}}}{\frac{lcm(δ, Eδ)}{τ_{0}}}  (3)

where τ = gcd(δ, Eδ) and τ_{0} = gcd(\frac{δ}{τ} Eγ −γ \frac{Eδ}{τ} , lcm(δ, Eδ)) and the right hand side is in reduced form.

Remark 1 In equation (3) we have τ_{0}|τ.

Proof. We know τ_{0}|δEδ. Assume now that there exists a non trivial factor τ_{1} of τ_{0} such that τ_{1}|δ and τ_{1} ∤ Eδ. Then τ_{1}|\frac{δ}{τ} and τ_{1} ∤ \frac{Eδ}{τ}. This is a contradiction to (3), for τ_{0}|(\frac{δ}{τ} Eγ − γ \frac{Eδ}{τ}) must hold and γ, δ are relatively prime. The case τ_{1}|Eδ and τ_{1} ∤ δ is analogous. □

From this remark one easily obtains the following property.

Lemma 2 Each shift-component π^{m_{0}} ⋯ (E^{l−1}π)^{m_{l−1}} of length l in δ corresponds to a shiftcomponent π^{m′_{0}} ⋯ (E^{l}π)^{m′_{l}} of length l + 1 in the denominator of Δh. Furthermore m_{0} = m′_{0} and m_{l−1} = m′_{l} holds.

Proof. Consider a shift-component of δ, viz. π^{m_{0}}(Eπ)^{m_{1}} ⋯ (E^{l−1}π)^{m_{l−1}} for some irreducible polynomial π and non-negative integers m_{0}, …, m_{l−1} with m_{0}m_{l−1} ≠ 0. Then obviously (Eπ)^{m_{0}}(E^{2}π)^{m_{1}} ⋯ (E^{l}π)^{m_{l−1}} is a shift-component of Eδ and

(Eπ)^{min(m_{0},m_{1})}(E^{2}π)^{min(m_{1},m_{2})} ⋯ (E^{l−1}π)^{min(m_{l−2},m_{l−1})}

is a shift-component of gcd(δ, Eδ), while

π^{m_{0}}(Eπ)^{max(m_{0},m_{1})} ⋯ (E^{l−1}π)^{max(m_{l−2},m_{l−1})}(E^{l}π)^{m_{l−1}}

is a shift-component of lcm(δ, Eδ). From Remark 1 we know τ_{0}| gcd(δ, Eδ), so π ∤ τ_{0} and E^{l}π ∤ τ_{0}. This implies the statement. □

Now we give a more precise description of the factors of τ_{0}.

Lemma 3 For all non-trivial factors σ of gcd(δ, Eδ) we have: σ|τ_{0} ⇒ σ ∤ \frac{δ}{τ} and σ ∤ \frac{Eδ}{τ}

Proof. Assume σ|τ_{0} and σ|\frac{δ}{τ}. Notice that then σ ∤ \frac{Eδ}{τ} immediately follows. From σ|τ_{0} we know σ|\frac{δ}{τ} Eγ − γ \frac{Eδ}{τ}, so σ|γ \frac{Eδ}{τ}. As δ and γ are relatively prime, we have σ|\frac{Eδ}{τ}. This implies gcd(\frac{Eδ}{τ} , \frac{δ}{τ}) ≠ 1, a contradiction to τ = gcd(δ, Eδ). Similarly for the assumption δ|τ_{0} and σ|\frac{Eδ}{τ}. □

In other words, if π is a factor of τ_{0}, then π and E^{−1}π arise with same multiplicity in δ. This fact implies that the reduced denominator of Δh might differ from lcm(δ, Eδ) only at those places where we have repeated multiplicities in the corresponding shift-component of δ.

Example 2 Consider a rational function, whose denominator has the shift-structure as represented in the left part of Fig. 2. Then the shift-structure of τ_{0} will be contained in the diagram in the right part of Fig. 2.

Figure 2: Upper bound for τ_{0}

Let us define a particular kind of shift structure which will play an important role in the following section.

Definition 2 Let the shift structure of the polynomial q be given by one shift component

q = π^{m_{0}}(Eπ)^{m_{1}} ⋯ (E^{l}π)^{m_{l}}

where l > 0 and m_{0}m_{l} > 0. We call such a shift structure safe if for all 0 ≤ i < j ≤ l such that m_{i} = m_{j} one of the following conditions holds

1. i = 0 and j = l

2. ∃k : i < k < j and m_{k} > m_{i}

3. ∃k_{1}, k_{2} : k_{1} < i < j < k_{2} and m_{k_{1}} > m_{i} and m_{k_{2}} > m_{j}

This means that if two stacks in the shift structure have the same number of boxes, then there must be an higher stack between them or they have to be enclosed between two higher stacks (or they are the endpoints). The definition naturally generalizes to polynomials with several shift components, i.e. each shift component is supposed to be safe.

3 The j-Shift-Saturation

In order to say more about the shift structure of the denominator polynomials of the solutions, we need the following definition.

Definition 3 Let q ∈ K[x] be given by one shift component q = π^{m_{0}}(Eπ)^{m_{1}} ⋯ (E^{l}π)^{m_{l}}. For all nonnegative integers j ≤ l we call the polynomial

ShiftSat_{j}(q) := π^{t_{0}}(Eπ)^{t_{1}} · · · · · · (E^{l−1}π)^{t_{l−1}}

j-shift-saturation of q, where t_{i} = max{m_{0}, …, m_{i}} for i = 0, …, j and t_{i} = max{m_{i+1}, …, m_{l}} for i = j, …, l − 1.

The definition can be extended to j < 0 or j > l assuming m_{i} = 0 for all i < 0 and i > l. One can visualize the last definition as follows. Fix the j-th stack in the diagram correspond-

ing to the shift structure of the polynomial, then do a saturation from the left of the stacks left of j and a saturation from the right of the stack right of j. After this, one simply erases the j-th stack and shifts the right boxes one step to the left.

In the following theorem the importance of the ShiftSat_{j}(q) for our problem is explained.

Theorem 2 Let f = p/q ∈ K(x) be such that the shift structure of q consists of a unique shift component q = π^{m_{0}}(Eπ)^{m_{1}} ⋯ (E^{l}π)^{m_{l}} with m_{0}m_{l} ≠ 0 and l > 0. Then for all integers j there exist solutions h = γ/δ, r = ε/η of f = Δh + r such that

δ = Shift_{j}(q)  and  η = E^{j}π^{m}

holds, where m = max{m_{0}, …, m_{l}}. Furthermore, if the shift structure of q is safe, then γ/δ is already a reduced representation.

Proof. The existence of a solution for η = (E^{l}π)^{m} is consequence of Theorem 3 in [3]. Consider now the decomposition

\frac{ε}{(E^{l}π)^{m}} = −\frac{Eε}{(E^{l+1}π)^{m}} + \frac{ε}{(E^{l}π)^{m}} + \frac{Eε}{(E^{l+1}π)^{m}}

This means that also h′ = h − r and r′ = Er form a solution to the indefinite summation problem, so a solution with η = (E^{j}π)^{m} exists for all j (and with Theorem 1 all possible η have this form).

Let (h, r) be a solution with η = (E^{j}π)^{m} for a certain j. For simplicity we consider only 0 < j < l, but the proof can be easily extended to the remaining cases. As a consequence of Lemma 2 we know that the denominator δ of the rational part consists of a class of length l − 1, starting with the same factor as q, i.e.

δ = π^{d_{0}}(Eπ)^{d_{1}} ⋯ (E^{l−1}π)^{d_{l−1}}

and d_{0} = m_{0}. We now consider the multiplicities of the factors Eπ, E^{2}π, …, E^{j−1}π of δ. The multiplicity of Eπ in Eδ is d_{0} = m_{0}, while the multiplicity in q is m_{1}. One of the following must hold.

1. m_{1} < d_{0}. From the considerations after Remark 3 this can happen only if we have repeated multiplicities, so d_{1} = d_{0} must hold.

2. m_{1} > d_{0}. This means that d_{1} = m_{1}, for this is the only way to increase the multiplicity.

3. m_{1} = d_{0}. This may happen only if d_{1} ≤ d_{0}.

In the example in Fig. 3 we have d_{0} = m_{0} = 1 and m_{1} = 2, so it follows that d_{1} = 2. In any case we have d_{1} ≤ max{d_{0}, m_{1}} = max{m_{0}, m_{1}}. These comparisons go step by step until we reach the j − th position. From this follows that for all 0 ≤ k < j it holds d_{k} ≤ max{m_{0}, …, m_{k}}.

Now consider the right endpoint of the class. Similarly d_{l−1} = m_{l}, as E^{l}π does not arise as factor of δ. Now we have to compare the (l − 1)-st column, i.e. d_{l−2}, d_{l_{1}} and m_{l−1}. The only possible cases are

1. m_{l−1} < d_{l−2}. Again, after Remark 3 we need the same multiplicity of E^{l−1}π in Eδ, so we have d_{l−2} = d_{l−1}.

2. m_{l−1} > d_{l−2}. This implies that d_{l−2} = m_{l−1}

3. m_{l−1} = d_{l−2}. This means that d_{l−2} ≤ d_{l−1}.

In the example in Fig. 3 we have d_{5} = m_{5} = 1 and m_{4} = 0, so it follows that d_{4} = 1. Again we can iterate until the multiplicity d_{j} is determined. For all j ≤ k < l, d_{k} ≤ max{m_{k+1}, …, m_{l−1}} holds.

[figure: j; Eδ; δ; q]

Figure 3: Determining δ

The steps on the multiplicities can be explained as follows. Going from left to the right we always take the maximal multiplicity ariseng so far. Similarly from the right to left. So δ is a divisor of the j-shift-saturation of q. On the other side, two of the cases above give no freedom of choice (the first and the second). One can easily see that if the denominator of f has a safe shift structure the third case never arises for any choice of j. For such f the rational part γ/δ is already reduced.

In fact, the third case arises only when in q two multiplicities with same value arise as “maxima” in the saturation. In other words, in order to have say m_{k} = d_{k−1} for a k < j there must be m_{k+i} = m_{k} for some positive i but no m_{k+h} > m_{k} with h > 0. Such a structure is unsafe. □

The fact that for safe shift structures the denominator δ of the rational part h is precisely ShiftSat_{j}(q) allows us to compute a solution, where also δ has minimal degree. It is sufficient to choose j such that the corresponding j-shift-saturation is minimal in the degree, i.e. take j where the maximal multiplicity arises.

4 Concluding Remarks

In this note we discussed the shift structure of the denominators of solutions h, r ∈ K(x) to the problem of indefinite rational summation for a given f ∈ K(x).

In Theorem 2 we gave polynomials which were multiples of the denominators of h and r, respectively. We proved that for a certain class of summands the given estimates are precise. This description depends only on the structure of the denominator of the summand f and it is not reasonable to expect lower estimates without considering the numerator of the summand.

Provided ShiftSat_{j}(q) can be computed by some effective algorithm, Theorem 2 leads to an algorithmic solution of the problem. In fact, knowing the denominators of h and r corresponds to reducing equation (1) to a polynomial equation, which can be solved by coefficient comparison.

In addition, our observations prove that the modification of Abramow’s algorithm (see [1]) that we proposed in [4, 5] often yields a solution where both h and r are minimal in the degree of the denominator.

References

[1] S. A. Abramow, The Rational Component of The Solution of a First-Order Linear Recurrence Relation with a Rational Right Side, Zh. vychisl. Mat. mat. fis., 15, N. 4, 1035-1039, 1975

[2] R. Moenck, On computing closed forms for summations, Proceedings of MACSYMA users’ conference, Berkley, pp. 225-236, 1977

[3] P. Paule, Greatest Factorial Factorization and Symbolic Summation I, RISC-Linz Report Series 93-02, J. Kepler University, Linz, 1993, submitted to J. Symb. Comp.

[4] R. Pirastu, Algorithmen zur Summation rationaler Funktionen, (Algorithms for Summation of Rational Functions, in german), Diploma Thesis, Univ. Erlangen-Nürnberg, 1992

[5] R. Pirastu, Algorithms for Indefinite Summation of Rational Functions in Maple, submitted to The Maple Technical Newsletter