In 2012 Chen and Singer introduced the notion of discrete residues for rational functions as a complete obstruction to rational summability. More explicitly, for a given rational function f(x), there exists a rational function g(x) such that f(x) = g(x + 1) − g(x) if and only if every discrete residue of f(x) is zero. Discrete residues have many important further applications beyond summability: to creative telescoping problems, thence to the determination of (differential-)algebraic relations among hypergeometric sequences, and subsequently to the computation of (differential) Galois groups of difference equations. However, the discrete residues of a rational function are defined in terms of its complete partial fraction decomposition, which makes their direct computation impractical due to the high complexity of completely factoring arbitrary denominator polynomials into linear factors. We develop a factorization-free algorithm to compute discrete residues of rational functions, relying only on gcd computations and linear algebra.

We construct Mahler discrete residues for rational functions and show that they comprise a complete obstruction to the Mahler summability problem of deciding whether a given rational function $f(x)$ is of the form $g(x^p)-g(x)$ for some rational function $g(x)$ and an integer $p > 1$. This extends to the Mahler case the analogous notions, properties, and applications of discrete residues (in the shift case) and q-discrete residues (in the q-difference case) developed by Chen and Singer. Along the way we define several additional notions that promise to be useful for addressing related questions involving Mahler difference fields of rational functions, including in particular telescoping problems and problems in the (differential) Galois theory of Mahler difference equations.

We develop algorithms to compute the differential Galois group G associated to a parameterized second-order homogeneous linear differential equation of the form