Hermite reduction

The step of symbolic integration that splits the integral of a rational function A/D into a rational function and an integral whose denominator is squarefree, using only extended gcds and no factorization of D. What remains after it integrates to a sum of logarithms.

For $de g A < de g D$ , the integral of $A / D$ is a rational function plus a sum of logarithms, and the rational part comes entirely from the repeated factors of $D$ . Hermite's method removes them one power at a time.^[1] Write $D = U V^{m}$ with $V$ squarefree, $g cd (U, V) = 1$ and $m \geq 2$ . Since $V$ is squarefree, $g cd (V, V^{'}) = 1$ , so $g cd (U V^{'}, V) = 1$ and the extended Euclidean algorithm gives $B$ and $C$ with

U V^{'} B + V C = A

and then

\int \frac{A}{U V ^{m}} = \frac{B}{( 1 - m ) V ^{m - 1}} + \int \frac{C - U B ^{'} / ( 1 - m )}{U V ^{m - 1}}

To check it, differentiate the first term:

(\frac{B}{( 1 - m ) V ^{m - 1}})^{'} = \frac{B ^{'}}{( 1 - m ) V ^{m - 1}} + \frac{B V ^{'}}{V ^{m}}

Adding the integrand on the right, the $B^{'}$ terms cancel and what is left is $\frac{U B V ^{'} + C V}{U V ^{m}} = \frac{A}{U V ^{m}}$ . Each step lowers the power of $V$ by one, so repeating it along the square-free decomposition $D = D_{1} D_{2}^{2} \dots D_{k}^{k}$ ends with a squarefree denominator.

For $\int d x / (x^{2} + 1)^{2}$ : $U = 1$ , $V = x^{2} + 1$ , $m = 2$ , $V^{'} = 2 x$ . Solving $2 x B + (x^{2} + 1) C = 1$ gives $B = - x /2$ , $C = 1$ , and

\int \frac{d x}{( x ^{2} + 1 ) ^{2}} = \frac{- x /2}{- ( x ^{2} + 1 )} + \int \frac{1 - \frac{1}{2}}{x ^{2} + 1} d x = \frac{x}{2 ( x ^{2} + 1 )} + \frac{1}{2} arctan x

The derivative of the result minus the integrand, by central differences with h = 1e-6.

x = 0.3    -3.7e-11
x = 1.0    -2.1e-11
x = 2.5    -7.6e-12

The remaining integral has a squarefree denominator, so it is a sum of logarithms over the algebraic closure; $arctan x$ is $\frac{i}{2} (lo g (x + i) - lo g (x - i))$ . The Rothstein–Trager resultant finds those logarithms without factoring the denominator. Hermite reduction is also the rational part of the Risch algorithm, applied in the top variable of a tower.

Ostrogradsky (1845) and Horowitz (1971) get the same split in one step:^[3]^[2] with $D^{-} = g cd (D, D^{'})$ and $D^{*} = D / D^{-}$ , there are polynomials $P, Q$ with $\int A / D = P / D^{-} + \int Q / D^{*}$ , and their coefficients solve a single linear system.