Let K be a field of characteristic zero, and consider the field K(𝑥) of rational functions in an indeterminate 𝑥 with coefficients in K. First formulated in [Abr71], the rational summation problem asks, for a given 𝑓 (𝑥) ∈ K(𝑥), to construct 𝑔(𝑥), ℎ(𝑥) ∈ K(𝑥) such that 𝑓 (𝑥) = 𝑔(𝑥 + 1) -𝑔(𝑥) + ℎ(𝑥)
(1.1) and the degree of the denominator of ℎ(𝑥) is as small as possible. Such an ℎ(𝑥) is called a reduced form of 𝑓 (𝑥). The rational summation problem has a long and illustrious history [Abr71, Abr75, Moe77, Kar81, Pau95, Pir95, PS95, MS95, Abr95, Pol08]. It is clear that the problem admits a solution (by the well-ordering principle), and that such a solution is not unique, because for any solution (𝑔(𝑥), ℎ(𝑥)) we obtain another solution (𝑔(𝑥) -ℎ(𝑥), ℎ(𝑥 +1)) since the degree of the denominator of ℎ(𝑥 + 1) is the same as that of ℎ(𝑥).
In comparing the approaches in op. cit., one can then ask for the denominator of 𝑔(𝑥) to be also as small as possible, and/or to compute some (any) solution (𝑔(𝑥), ℎ(𝑥)) to (1.1) as efficiently as possible.
We refer to the introduction of [PS95] for a concise summary and comparison between most of these different approaches.
Every algorithm for solving the rational summation problem also addresses, as a byproduct, the rational summability problem of deciding, for a given 𝑓 (𝑥) ∈ K(𝑥), whether (just yes/no) there exists 𝑔(𝑥) ∈ K(𝑥) such that 𝑓 (𝑥) = 𝑔(𝑥 + 1) -𝑔(𝑥), in which case we say 𝑓 (𝑥) is rationally summable. There are various algorithms for addressing this simpler question, designed to forego the usually expensive and often irrelevant computation of the certificate 𝑔(𝑥), which are presented and discussed for example in [Mat00, GGSZ03, BCCL10, CS12, CHKL15, HW15, GHLZ22] and the references therein.
We center our attention on the approach to rational summability proposed in [CS12]. The discrete residues of 𝑓 (𝑥) ∈ K(𝑥) are constants defined in terms of the complete partial fraction decomposition of 𝑓 (𝑥), and have the obstruction-theoretic property that they are all zero if and only if 𝑓 (𝑥) is rationally summable. Computing these discrete residues directly from their definition is impractical due to the high computational cost, or possible infeasibility, of factoring the denominator of 𝑓 (𝑥) into linear factors. We propose here algorithms for computing these discrete residues relying only on gcd computations and solving systems of linear equations in K. To be clear, the discrete residue data of an arbitrary 𝑓 (𝑥) are in general algebraic over K. We submit that it would be perverse to avoid expensive factorizations throughout the algorithm, only to demand them at the very end! Inspired by [BS93, Thm. 1] our output consists of pairs of polynomials with coefficients in K: one whose roots are the places where 𝑓 (𝑥) has non-zero discrete residues, the other whose evaluation at each such root gives the corresponding discrete residue (see §3 for a more detailed description). Of course, any user who wishes to actually see the discrete residue data of 𝑓 may use the K-polynomials produced by our algorithms to compute them explicitly to their heart's content and at their own risk.
Let us now describe our general strategy for computing discrete residues (cf. Algorithm 4). We apply iteratively Hermite reduction to 𝑓 (𝑥) in order to reduce to the special case where the denominator of 𝑓 (𝑥) is squarefree. Then we compute a reduced form f (𝑥) of 𝑓 (𝑥) whose denominator is both squarefree and shift-free, so that the discrete residues of 𝑓 (𝑥) are the classical first-order residues of f (𝑥). The factorization-free computation of the latter is finally achieved by [Tra76,Lem. 5.1].
Our proposed algorithms to compute discrete residues are obtained by combining in novel ways many old ingredients. Indeed, Hermite reduction is very old [Ost45,Her72], and its iteration in Algorithm 1 is already suggested in [Hor71,§5] for computing iterated integrals of rational functions. And yet, we have not seen this approach being more widely used in the literature, and it seems to us a good trick to have to hand. Indeed, we wonder whether it could provide a reasonable alternative, at least in some cases and for some purposes, to the algorithm in [BS93] for symbolically computing complete partial fraction decompositions over the field of definition. Having thus reduced via Algorithm 1 to the case where 𝑓 (𝑥) has squarefree denominator, many of the varied earlier approaches to the summation and summability problems seem to accidentally collide into essentially the same procedure when restricted to this simpler situation. In this sense, our own reduction procedure described in §5 strikes us as eerily similar to the one presented in [GGSZ03, §5] over 20 years ago -that ours may look simpler is a direct consequence of its being restricted to a simpler class of inputs. The simplicity of our approach allows us to exercise a great deal of control over the form of the outputs, in ways that are particularly useful for developing some extensions of our basic procedures, elaborated in §7. It is not obvious to us (but it would be interesting to see) how the same goals might be better accomplished differently, say by combining the reduction of [GGSZ03] with the symbolic complete partial fraction decomposition algorithm of [BS93].
Our interest in computing discrete residues is motivated by the following variant of the summability problem, which often arises as a subproblem in algorithms for computing (differential) Galois groups associated with (shift) difference equations [vdPS97,Hen98,HS08,Arr17]. Given several 𝑓 1 (𝑥), . . . , 𝑓 𝑛 (𝑥) ∈ K(𝑥), compute (or decide non-existence) of 0 ≠ v = (𝑣 1 , . . . , 𝑣 𝑛 ) ∈ K 𝑛 such that
for some 𝑔 v (𝑥) ∈ K(𝑥). Even if one wishes to compute the certificate 𝑔 v (𝑥) explicitly, it seems wasteful to perform a rational summation algorithm 𝑛 times for each 𝑓 𝑖 (𝑥) separately to produce (𝑔 𝑖 (𝑥), ℎ 𝑖 (𝑥)) as in (1.1) as an intermediate step, because there is no guarantee that ℎ v (𝑥) = 𝑖 𝑣 𝑖 ℎ 𝑖 (𝑥) has smallest possible denominator, so one may need to perform the algorithm an (𝑛 + 1) st time to ℎ v (𝑥) in order to decide summability (this last step may be avoidable by making a more careful sequence of interrelated reduction choices; see e.g. [CHKL15,§5]). These inefficiencies are exacerbated in the more general context of creative telescoping problems [Zei90, Zei91, WZ92], where the unknown 𝑣 𝑖 ∈ K are replaced with unknown linear differential operators L 𝑖 ∈ K 𝑑 𝑑𝑥 (cf. [HS08, Prop. 3.1]). We refer to [Che19] for a succinct and illuminating discussion of the history and computational aspects of creative telescoping problems, and in particular how the "fourth generation" reduction-based approaches bypass the computation of certificates, as our motivating problem (1.2) illustrates.
Our approach based on discrete residues makes it very straightforward how to accommodate several 𝑓 𝑖 (𝑥) simultaneously as in (1.2), which adaptation is less obvious (to us) how to carry out efficiently using other reduction methods. On the other hand, we share in the reader's disappointment that we offer hardly any theoretical or experimental evidence supporting the efficiency of our approach in contrast with other possible alternatives. In fact, we expect that our approach will not be universally more efficient than some future adaptation of [GGSZ03,§5] or [CHKL15, §5] (for example) to the situation of (1.2), but rather that it can be a useful complement to them. We also expect that the conceptual simplicity of our approach will be useful in developing analogues to other related (but more technically challenging) contexts beyond the shift case, such as 𝑞-difference equations, Mahler difference equations, and elliptic difference equations, for which the corresponding notions of discrete residues have also been developed respectively in [CS12], [AZ22,AZ23], and [HS21].
We denote by N the set of strictly positive integers, and by K a computable field of characteristic zero in which it is feasible to compute integer solutions to arbitrary polynomial equations with coefficients in K. Such a field is termed canonical in [Abr71]. We denote by K a fixed algebraic closure of K. We do not assume K is algebraically closed, and we will only refer to K in proofs or for defining theoretical notions, never for computations.
We work in the field K(𝑥) of rational functions in a formal (transcendental) indeterminate 𝑥. For 𝑓 (𝑥) ∈ K(𝑥), we define 𝜎 : 𝑓 (𝑥) ↦ → 𝑓 (𝑥 + 1); and Δ : 𝑓 (𝑥) ↦ → 𝑓 (𝑥 + 1) -𝑓 (𝑥).
Note that 𝜎 is a K-linear field automorphism of K(𝑥) and Δ = 𝜎id is only a K-linear map with ker(Δ) = K. We often suppress the functional notation and write 𝑓 instead of 𝑓 (𝑥), 𝜎 (𝑓 ) instead of 𝑓 (𝑥 + 1), etc., when no confusion is likely to arise.
A proper rational function is either 0 or else has numerator of strictly smaller degree than that of the denominator. We assume implicitly throughout that rational functions are normalized to have monic denominator. Even when our rational functions are obtained as (intermediate) outputs of some procedures, we will take care to arrange things so that this normalization always holds. In particular, we also assume that the outputs of gcd and lcm procedures are also always normalized to be monic. An unadorned gcd or lcm or deg means that it is with respect to 𝑥. On the few occasions where we need a gcd with respect to a different variable 𝑧, we will write gcd 𝑧 . We write 𝑑 𝑑𝑥 (resp., 𝑑 𝑑𝑧 ) for the usual derivation operator with respect to 𝑥 (resp., with respect to 𝑧).
, with deg(𝑏) ≥ 1 and gcd(𝑎, 𝑏) = 1. Suppose further that 𝑏 is squarefree, and that we are given a set 𝑏 1 , . . . , 𝑏 𝑛 ∈ K[𝑥] of monic non-constant polynomials such that 𝑛 𝑖=1 𝑏 𝑖 = 𝑏. Then necessarily gcd(𝑏 𝑖 , 𝑏 𝑗 ) = 1 whenever 𝑖 ≠ 𝑗, and there exist unique non-zero polynomials
. In this situation, we denote ParFrac(𝑓 ; 𝑏 1 , . . . , 𝑏 𝑛 ) := (𝑎 1 , . . . , 𝑎 𝑛 ).
(2.1)
We emphasize that the computation of partial fraction decompositions (2.1) can be done very efficiently [KT77], provided that the denominator 𝑏 of 𝑓 has already been factored into pairwise relatively prime factors 𝑏 𝑖 , which need not be irreducible in K[𝑥]. One can similarly carry out such partial fraction decompositions more generally for pre-factored denominators 𝑏 that are not necessarily squarefree. But here we only need to compute partial fraction decompositions for pre-factored squarefree denominators, in which case the notation (2.1) is conveniently light.
We say
For a reduced rational function 𝑓 = 𝑎 𝑏 ∈ K(𝑥) with gcd(𝑎, 𝑏) = 1 and 𝑏 ∉ K, the polar dispersion pdisp(𝑓 ) := disp(𝑏).
We denote by K/Z the set of orbits for the action of the additive group Z on K. For 𝛼 ∈ K, we denote
the unique orbit in K/Z containing 𝛼. We will often simply write 𝜔 ∈ K/Z whenever there is no need to reference a specific 𝛼 ∈ 𝜔. (3.2)
The relevance of discrete residues to the study of rational summability is captured by the following result. Discrete residues are also intimately related to the computation of reduced forms for 𝑓 , in the sense that, as discussed in [CS12, §2.4], every reduced form ℎ of 𝑓 as in (1.1) has the form
for some arbitrary choice of representatives 𝛼 𝜔 ∈ 𝜔. Conversely, for any ℎ of the form (3.3), Proposition 3.2 immediately yields that 𝑓ℎ is rationally summable. An equivalent characterization for ℎ ∈ K(𝑥) to be a reduced form is for it to have polar dispersion 0 (see [Abr75,Props. 4 & 6]). By (3.3), knowing the dres(𝑓 , 𝜔, 𝑘) is thus "the same" as knowing some/all reduced forms ℎ of 𝑓 . But discrete residues still serve as a very useful organizing principle and technical tool, for both theoretical and practical computations. For a given 𝑓 ∈ K(𝑥), our goal is to compute polynomials 𝐵 𝑘 (𝑥), 𝐷 𝑘 (𝑥) ∈ K[𝑥] for each 𝑘 ∈ N such that (𝐵 𝑘 , 𝐷 𝑘 ) = (1, 0) if and only if dres(𝑓 , 𝜔, 𝑘) = 0 for every 𝜔 ∈ K (which holds for all but finitely many 𝑘 ∈ N) and, for the remaining 𝑘 ∈ N, we have 0 ≤ deg(𝐷 𝑘 ) < deg(𝐵 𝑘 ) and 𝐵 𝑘 is squarefree with disp(𝐵 𝑘 ) = 0. These polynomials will have the property that the set of roots 𝛼 ∈ K of 𝐵 𝑘 is a complete and irredundant set of representatives for all the orbits 𝜔 ∈ K/Z such that dres(𝑓 , 𝜔, 𝑘) ≠ 0, and for each such root 𝛼 ∈ K such that 𝐵 𝑘 (𝛼) = 0, we have dres(𝑓 , 𝜔 (𝛼), 𝑘) = 𝐷 𝑘 (𝛼).
It is immediate that the polynomial part of 𝑓 ∈ K(𝑥) in (3.1) is irrelevant, both for the study of summability as well as for the computation of discrete residues. So in this section we restrict our attention to proper rational functions 𝑓 ∈ K(𝑥).
Our first task is to reduce to the case where 𝑓 has squarefree denominator. In this section we describe how to compute 𝑓 𝑘 ∈ K(𝑥) for 𝑘 ∈ N such that, relative to the theoretical partial fraction decomposition (3.1) of 𝑓 , we have Output: A list (𝑓 1 , . . . , 𝑓 𝑚 ) of 𝑓 𝑘 ∈ K(𝑥) satisfying (4.1), such that 𝑐 𝑘 (𝛼) = 0 for every 𝑘 > 𝑚 and every 𝛼 ∈ K, with 𝑓 𝑚 ≠ 0.
Initialize loop: 𝑚 ← 0; 𝑔 ← 𝑓 ; while 𝑔 ≠ 0 do (𝑔, f 𝑚+1 ) ← HermiteReduction(𝑔); 𝑚 ← 𝑚 + 1; end while; 𝑓 𝑘 ← (-1) 𝑘 -1 (𝑘 -1)! f 𝑘 ; return (𝑓 1 , . . . , 𝑓 𝑚 ).
Defining inductively 𝑔 0 := 𝑓 and
for 𝑘 ∈ N as in Algorithm 1, we obtain by construction that all 𝑔 𝑘 , f 𝑘 ∈ K(𝑥) and every f 𝑘 has squarefree denominator. Moreover,
and therefore the algorithm terminates with 𝑔 𝑚 = 0. Moreover, it follows from (4.4) that
Therefore the elements (-1) 𝑘 -1 (𝑘 -1)! f 𝑘 are squarefree and satisfy (4.3), so they agree with the 𝑓 𝑘 ∈ K(𝑥) satisfying (4.1). □ Remark 4.3. As we mentioned in the introduction, we do not expect Algorithm 1 to be surprising to the experts. What is surprising to us is that this trick is not used more widely since being originally suggested in [Hor71,§5]. We expect the theoretical cost of computing HermiteList(𝑓 ) iteratively as in Algorithm 1 is essentially the same as that of computing HermiteReduction(𝑓 ) only once. This might seem counterintuitive, since the former is defined by applying the latter as many times as the highest order 𝑚 of any pole of 𝑓 . But the size of the successive inputs in the loop decreases so quickly that the cost of the first step essentially dominates the added cost of the remaining steps put together. This conclusion is already drawn in [Hor71, §5] regarding the computational cost of computing iterated integrals of rational functions.
The results of the previous section allow us to further restrict our attention to proper rational functions 𝑓 ∈ K(𝑥) with simple poles, which we write uniquely as 𝑓 = 𝑎 𝑏 with 𝑎, 𝑏 ∈ K[𝑥] such that 𝑏 is monic and squarefree, and either 𝑎 = 0 or else 0 ≤ deg(𝑎) < deg(𝑏).
Our next task is to compute a reduced form f ∈ K(𝑥) such that 𝑓 -f is rationally summable and f has squarefree denominator as well as polar dispersion 0, which we accomplish in Algorithm 3. As we mentioned already in the introduction, many algorithms have been developed beginning with [Abr71] that can compute such a reduced form, even without assuming 𝑓 has only simple poles.
Algorithm 3 requires the computation of the following set of integers, originally defined in [Abr71].
The following Algorithm 2 for computing ShiftSet(𝑏) is based on the observation already made in [Abr71, p. 326], but with minor modifications to optimize the computations.
Algorithm 2 ShiftSet procedure
Proof. As pointed out in [Abr71, p. 326], ShiftSet(𝑏) is the set of positive integer roots of the resultant 𝑅(𝑧) ∈ K[𝑧] defined in Algorithm 2, which is the same as the set of positive integer roots of the square-free part 𝑅(𝑧)/gcd 𝑧 𝑅(𝑧), 𝑑𝑅 𝑑𝑧 (𝑧) . It is clear that 𝑅(0) = 0, and since we do not care for this root, we are now looking for positive integer roots of the polynomial R(𝑧) defined in Algorithm 2. It follows from the definition of 𝑅(𝑧) that 𝑅(ℓ) = 0 if and only if 𝑅(-ℓ) = 0 for every ℓ ∈ K (not just for ℓ ∈ Z), and we see that this property is inherited by R(𝑧). Since 𝑧 ∤ R(𝑧), the even polynomial R(𝑧) = 𝑇 (𝑧 2 ) for a unique 𝑇 (𝑧) ∈ K[𝑧], whose degree is evidently half of that of R(𝑧). □
Remark 5.3. The role of the assumption that K be canonical (cf. §2.1) is made only so that one can compute ShiftSet(𝑏). We note that in [GGSZ03, §6] a much more efficient (and general) algorithm than Algorithm 2 is described, which works for 𝑏 ∈ Z[𝑥]. We remark that in order to compute ShiftSet(𝑏) in general, it is sufficient to be able to compute a basis {𝑤 1 , . . . , 𝑤 𝑠 } of the Q-vector subspace of K spanned by the coefficients of the auxiliary polynomial 𝑇 (𝑧) ∈ K[𝑥] defined in Algorithm 2. Indeed, we could then write 𝑇 (𝑧) = 𝑠 𝑗=1 𝑤 𝑗 𝑇 𝑗 (𝑧) with each 𝑇 𝑗 (𝑧) ∈ Q[𝑧] and simply compute the set of (square) integer roots of T (𝑧) = gcd(𝑇 1 , . . . ,𝑇 𝑠 ), which is the same as the set of (square) integer roots of 𝑇 (𝑧).
The previous Algorithm 2 to compute ShiftSet is called by the following Algorithm 3 to compute reduced forms of rational functions with squarefree denominators.
Proposition 5.4. Algorithm 3 is correct.
Proof. As in Algorithm 3, let 𝑏 denote the denominator of 𝑓 and let 𝑆 = ShiftSet(𝑏). Then indeed if 𝑆 = ∅, pdisp(𝑓 ) = 0, so 𝑓 is already reduced and there is nothing to do. Assume from Algorithm 3 SimpleReduction procedure Input: A proper rational function 𝑓 ∈ K(𝑥) with squarefree denominator. Output: A proper rational function f ∈ K(𝑥) with squarefree denominator, such that 𝑓 -f is rationally summable and either f = 0 or pdisp( f ) = 0.
end if; return f . now on that 𝑆 ≠ ∅, and let us consider roots of polynomials in K.
For each ℓ ∈ 𝑆, the roots of 𝑔 ℓ := gcd(𝑏, 𝜎 -ℓ (𝑏)) are those roots 𝛼 of 𝑏 such that 𝛼ℓ is also a root of 𝑏. Therefore the roots of 𝐺 = lcm(𝑔 ℓ : ℓ ∈ 𝑆) are those roots 𝛼 of 𝑏 such that 𝛼ℓ is also a root of 𝑏 for some ℓ ∈ N (because all possible such ℓ belong to 𝑆, by the definition of 𝑆). It follows that the roots of 𝑏 0 := 𝑏/𝐺 are those roots 𝛼 of 𝑏 such that 𝛼ℓ is not a root of 𝑏 for any ℓ ∈ N.
In particular, disp(𝑏 0 ) = 0. We call 𝑏 0 the divisor of initial roots. Now the roots of 𝑏 ℓ := gcd(𝜎 -ℓ (𝑏 0 ), 𝑏) are those roots 𝛼 of 𝑏 such that 𝛼ℓ is a root of 𝑏 0 , i.e., the roots of 𝑏 which are precisely ℓ shifts away from the initial root in their respective Z-orbits. It may happen that 𝑏 ℓ = 1 for some ℓ ∈ 𝑆, because even though each ℓ ∈ 𝑆 is the difference between two roots of 𝑏, it might be that no such pair of roots of 𝑏 involves any initial roots of 𝑏 0 . Writing
(5.1) Therefore we may uniquely decompose 𝑓 into partial fractions as in (2.1) with respect to the factorization (5.1) as called by Algorithm 3,
. Now this f is a sum of proper rational functions with squarefree denominators, whence f also is proper with squarefree denominator. Since 𝜎 ℓ (𝑏 ℓ ) = gcd(𝑏 0 , 𝜎 ℓ (𝑏)) is a factor of 𝑏 0 for each ℓ ∈ 𝑁 and disp(𝑏 0 ) = 0, we conclude that pdisp( f ) = 0. Finally, for each ℓ ∈ 𝑁 -{0} we see that
whence 𝑓 -f is a sum of rationally summable elements, and is therefore itself rationally summable. □ Remark 5.5. As we stated in the introduction, Algorithm 3 strikes us as being conceptually similar to the one already developed in [GGSZ03, §5], but its description is made simpler by our restriction to rational functions with simple poles only. Having a procedure that is easier for humans to read is not necessarily a computational virtue. But it is so in this case, because the relative simplicity of Algorithm 3 makes it also nimble and adaptable, enabling us in §7 to easily modify it to pursue other related applications beyond plain rational summability.
Now we wish to put together the algorithms presented in the earlier sections to compute symbolically all the discrete residues of an arbitrary proper 𝑓 ∈ K(𝑥), in the sense described in §3. In order to do this, we first recall the following result describing the sense in which we compute classical residues symbolically by means of an auxiliary polynomial, and its short proof which explains how to actually compute this polynomial in practice. Proof. Since the set of poles of 𝑓 (all simple poles) is the set of roots of 𝑏, we know the classical first-order residue 𝑐 1 (𝛼) of 𝑓 at each 𝛼 ∈ K such that 𝑏 (𝛼) = 0 satisfies 0 ≠ 𝑐 1 (𝛼) = 𝑎(𝛼)/ 𝑑𝑏 𝑑𝑥 (𝛼). Using the extended Euclidean algorithm we find the unique 0 ≠ 𝑟 in K[𝑥] such that deg(𝑟 ) < deg(𝑏) and 𝑟 • 𝑑 𝑑𝑥 (𝑏) ≡ 𝑎 (mod 𝑏). □ For 𝑓 ∈ K(𝑥) satisfying the hypotheses of Lemma 6.1, we denote
where 𝑏, 𝑟 ∈ K[𝑥] are also as in the notation of Lemma 6.1. We also define FirstResidues(0) := (1, 0), for convenience. With this, we can now describe the following simple Algorithm 4 to compute a symbolic representation of the discrete residues of 𝑓 .
Theorem 6.2. Algorithm 4 is correct.
Proof. It follows from the correctness of Algorithm 1 proved in Lemma 4.2 that 𝑓 has no poles of order greater than 𝑚, whence by Definition 3.1 every non-zero discrete residue of 𝑓 has order at most 𝑚. Consider now f 𝑘 := SimpleReduction(𝑓 𝑘 ), which by the correctness of Algorithm 3 is such that 𝑓 𝑘 -f 𝑘 is summable. We prove the correctness of Algorithm 4 for each 𝑘 = 1, . . . , 𝑚 depending on whether f 𝑘 = 0 or not.
In case f 𝑘 = 0, Algorithm 4 produces (𝐵 𝑘 , 𝐷 𝑘 ) = (1, 0). In this case we also know that 𝑓 𝑘 is summable, and therefore by (4.2)
In this section we collect some modifications to the procedures described in the previous sections to produce outputs that allow for more immediate comparison of discrete residues across several rational functions and across different orders.
We begin with the parameterized summability problem (1.2) described in the introduction. Let f = (𝑓 1 , . . . , 𝑓 𝑛 ) ∈ K(𝑥) 𝑛 be given, and suppose we wish to compute a K-basis for
f⟩ is summable , (7.1) where ⟨•, •⟩ denotes the usual inner product. By Proposition 3.2, v = (𝑣 1 , . . . , 𝑣 𝑛 ) ∈ 𝑉 (f) ⇐⇒ 𝑛 ∑︁ 𝑖=1 𝑣 𝑖 • dres(𝑓 𝑖 , 𝜔, 𝑘) = 0 (7.2) for every 𝜔 ∈ K/Z and every 𝑘 ∈ N. If only we knew how to write down this linear system explicitly, we would be able to solve for the unknown v. We can apply Algorithm 4 to each 𝑓 𝑖 , and obtain DiscreteResidues(𝑓 𝑖 ) = (𝐵 𝑖,1 , 𝐷 𝑖,1 ), . . . , (𝐵 𝑖,𝑚 𝑖 , 𝐷 𝑖,𝑚 𝑖 )).
But it may happen that many different 𝛼 𝑖,𝑘 ∈ K all belong to the same orbit 𝜔 ∈ K/Z and satisfy 𝐵 𝑖,𝑘 (𝛼 𝑖,𝑘 ) = 0, which leads to very undesirable bookkeping problems.
To address this kind of problem, we introduce in Algorithm 5 a generalization of Algorithm 3 that computes reduced forms for several 𝑓 1 , . . . , 𝑓 𝑛 compatibly, so that whenever 𝑓 𝑖 and 𝑓 𝑗 have nonzero residue of order a given 𝑘 at a given orbit 𝜔 if and only if 𝐵 𝑖,𝑘 and 𝐵 𝑗,𝑘 have a common root 𝛼 ∈ K such that 𝜔 = 𝜔 (𝛼). For this purpose, we may assume as in §5 that the 𝑓 𝑖 are proper and, thanks to Algorithm 1, that they all have squarefree denominators.
Corollary 7.1. Algorithm 5 is correct.
Proof. The proof is very similar to that of Proposition 5.4, so we only sketch the main points. The key difference is that now 𝑏 0 has been defined so that for each root 𝛼 of 𝑏 0 and each root 𝛼 𝑖 of 𝑏 𝑖 belonging to 𝜔 (𝛼) we have that 𝛼 𝑖 -𝛼 ∈ Z ≥0 . The roots of 𝑏 𝑖,ℓ are precisely those roots of 𝑏 𝑖 which are ℓ steps away from the unique root of 𝑏 0 that belongs to the same orbit. By construction, the denominator of each f 𝑖 is a factor of 𝑏 0 , which has disp(𝑏 0 ) = 0 as before. □ Remark 7.2. Algorithm 5 also allows us to fix the deficiency discussed in Remark 6.3. For a non-zero proper 𝑓 ∈ K(𝑥), let us define (𝑓 1 , . . . , 𝑓 𝑚 ) := HermiteList(𝑓 ) as in Algorithm 4. If we now set ( f1 , . . . , f 𝑚 ) := SimpleReduction + (𝑓 1 , . . . , 𝑓 𝑚 ), instead of f 𝑘 := SimpleReduction(𝑓 𝑘 ) separately for 𝑘 = 1, . . . , 𝑚, we will no longer have the problem of the 𝐵 𝑘 being incompatible.
More generally, we can combine Algorithm 5 with the modification proposed in the above Remark 7.2 to compute symbolic representations of the discrete residues dres(𝑓 𝑖 , 𝜔, 𝑘) of several 𝑓 1 , . . . , 𝑓 𝑛 ∈ K(𝑥), which are compatible simultaneously across the different 𝑓 𝑖 as well as across the different 𝑘 ∈ N. This will be done in Algorithm 6, after explaining the following small necessary modification to the FirstResidues procedure defined in (6.1). For an 𝑛-tuple of proper rational functions f = (𝑓 1 , . . . , 𝑓 𝑛 ) with squarefree denominators, suppose FirstResidues(𝑓 𝑖 ) =: (𝑏 𝑖 , 𝑟 𝑖 ) as in (6.1), and let 𝑏 := lcm(𝑏 1 , . . . , 𝑏 𝑛 ). Letting 𝑎 𝑖 := numer(𝑓 𝑖 ) and 𝑑 𝑖 := 𝑏 𝑏 𝑖 , we see that gcd(𝑏 𝑖 , 𝑑 𝑖 ) = 1 because 𝑏 is squarefree, and diagonal systems
where 𝑟 1 , . . . , 𝑟 𝑛 ∈ K(𝑥) × (8.1)
As shown in [vdPS97, §2.2], the difference Galois group of (8.1) is
where 𝐸 ⊆ Z 𝑛 is the subgroup of e = (𝑒 1 , . . . , 𝑒 𝑛 ) such that
𝑝 e (8.2) for some 𝑝 e ∈ K(𝑥) × . Now suppose (8.2) holds, and let us write 𝑓 𝑖 := 𝑑 𝑑𝑥 (𝑟 𝑖 )/𝑟 𝑖 for each 𝑖 = 1, . . . , 𝑛 and 𝑔 e := 𝑑 𝑑𝑥 (𝑝 e )/𝑝 e , so that we have 𝑒 1 𝑓 1 + • • • + 𝑒 𝑛 𝑓 𝑛 = 𝜎 (𝑔 e ) -𝑔 e . (8.3) At first glance, this looks like a version of problem (1.2), but it is even more special because the 𝑓 𝑖 have only first-order residues, all in Z. So we can compute the Q-vector space 𝑉 of solutions to (8.3) using SimpleReduction + (𝑓 1 , . . . , 𝑓 𝑛 ), just as in Proposition 7.4, as a preliminary step. Then we can compute a Z-basis e 1 , . . . , e 𝑠 of the free abelian group Ẽ := 𝑉 ∩ Z 𝑛 . Since each 𝑔 e 𝑗 has only simple poles with integer residues, one can compute explicitly 𝑝 e 𝑗 ∈ K(𝑥) such that 𝑑 𝑑𝑥 𝑝 𝑗 = 𝑔 e 𝑗 𝑝 e 𝑗 , and thence constants 𝛾 𝑗 ∈ K × such that r e 𝑗 = 𝛾 𝑗 . This reduces computation of 𝐸 from the defining multiplicative condition (8.2) in K(𝑥) × modulo the subgroup {𝜎
Let us conclude by illustrating some of our procedures on the following example considered in both [PS95,MS95]. In order to make the computations easier for the human reader to follow, we have allowed ourselves to write down explicitly in this small example the irreducible factorizations of denominators. We emphasize and insist upon the fact that none of our procedures performs any such factorization.
Consider the rational function
We first compute HermiteList(𝑓 ) = (𝑓 1 , 𝑓 2 , 𝑓 3 ) with 𝑓 1 = 787𝑥 5 + 4803𝑥 4 + 9659𝑥 3 + 9721𝑥 2 + 9502𝑥 + 5008 18000(𝑥 2 + 1) (𝑥 + 3) (𝑥 2 + 4𝑥 + 5) (𝑥 + 2)𝑥 ;
𝑓 2 = -787𝑥 3 + 3372𝑥 2 + 4696𝑥 + 1030 18000(𝑥 2 + 4𝑥 + 5)𝑥 (𝑥 + 2)
; and 𝑓 3 := -7𝑥 -1 300(𝑥 + 2)𝑥 ; using Algorithm 1. We apply the remaining procedures to 𝑓 1 onlythe remaining 𝑓 2 and 𝑓 3 are similar, and easier. Denoting 𝑏 := (𝑥 2 + 1) (𝑥 + 3) (𝑥 2 + 4𝑥 + 5) (𝑥 + 2)𝑥 the monic denominator of 𝑓 1 , we compute with Algorithm 2 (or see by inspection) that ShiftSet(𝑏) = {1, 2, 3}. The factorization 𝑏 = 𝑏 0 𝑏 1 𝑏 2 𝑏 3 computed within Algorithm 3 is given by 𝑏 0 = (𝑥 + 3) (𝑥 2 + 4𝑥 + 5); 𝑏 1 = gcd(𝜎 -1 (𝑏 0 ), 𝑏) = 𝑥 + 2;
𝑏 2 = gcd(𝜎 -2 (𝑏 0 ), 𝑏) = 𝑥 2 + 1; 𝑏 3 = gcd(𝜎 -3 (𝑏 0 ), 𝑏) = 𝑥 . Let us compare this output (𝐵 1 , 𝐷 1 ) with the discrete residues dres(𝑓 , 𝜔, 1) of 𝑓 according to the Definition 3.1 in terms of classical residues. We see from the factorization of the denominator of 𝑓 in (9.1) that its set of poles is -3, -2, 0,
and that each of these poles belongs to one of the three orbits
Therefore, 𝑓 has no discrete residues outside of these orbits, and we verify that the set of roots {-3, √ -1 -2, -√ -1 -2} of the polynomial 𝐵 1 correctly contains precisely one representative from each of these orbits (subject to our verification below that the firstorder discrete residues of 𝑓 at these orbits are actually non-zero!). We can compute directly in this small example that the classical first-order residues of 𝑓 at the poles in 𝜔 (0) are given by