Proofs: Kovacic's algorithm

Kovacic's algorithm returns a Liouvillian solution exactly when one exists full

This proof shows: correctness, termination.

Let $K$ be a field of characteristic $0$ with algebraic closure $\overline{K}$, and let $r = s/t \in K(x)$ with $s, t$ coprime. Write $L = \partial^2 - r$ with $\partial = d/dx$, and work in a Picard-Vessiot extension $E$ of $\overline{K}(x)$ for $L$. A solution $y \ne 0$ of $L y = 0$ is Liouvillian if it lies in a tower of extensions of $\overline{K}(x)$ obtained by adjoining integrals, exponentials of integrals and algebraic elements.

Lemma 1 (Riccati). For $y \ne 0$ in $E$ put $w = y'/y$. Then $y'' = r y$ if and only if $w' + w^2 = r$. Conversely, if $w$ solves $w' + w^2 = r$ in a differential extension, then $y = e^{\int w}$, an element with $y' = w y$, solves $L y = 0$.

Proof. $y' = w y$ gives $y'' = (w' + w^2) y$, and $y \ne 0$. $\square$

Lemma 2 (Kovacic's theorem). The differential Galois group $G$ of $L$ is an algebraic subgroup of $\mathrm{SL}_2(\overline{K})$, since the Wronskian of two solutions has derivative $0$. Up to conjugation, exactly one of these holds: (1) $G$ is triangular; (2) $G$ is contained in the group of matrices $\mathrm{diag}(c, c^{-1})$ and $\left(\begin{smallmatrix} 0 & c \\ -c^{-1} & 0 \end{smallmatrix}\right)$, and case 1 fails; (3) $G$ is finite and not in case 1 or 2, so its image in $\mathrm{PSL}_2$ is the tetrahedral, octahedral or icosahedral group; (4) $G = \mathrm{SL}_2$. In case 1 there is a solution with $w \in \overline{K}(x)$, in case 2 one with $w$ of degree $2$ over $\overline{K}(x)$, in case 3 all solutions are algebraic and some $w$ has degree $4$, $6$ or $12$ for the three groups, and in case 4 there is no Liouvillian solution. This is the theorem of Kovacic (1986), from the classification of the algebraic subgroups of $\mathrm{SL}_2$, see also van der Put and Singer, Chapter 4. We use it as a cited result.

Lemma 3 (necessary conditions). Kovacic (1986) shows from the Laurent series of $w$ that case 1 is possible only if every pole of $r$ has order $1$ or even order and the order $o$ at infinity is even or above $2$, case 2 only if some pole has order $2$ or odd order at least $3$, and case 3 only if all poles have order at most $2$ and $o \ge 2$. For case 1 this follows from Step 1 below. Skipping a case whose condition fails therefore loses nothing.

Step 1 (local behaviour in case 1). Let $w \in \overline{K}(x)$ solve $w' + w^2 = r$, and let $c$ be a point. Expand $w = \sum_{j \ge j_0} u_j (x - c)^j$ with $u_{j_0} \ne 0$.

• If $j_0 \le -2$, then $w^2$ has a pole of order $-2j_0 \ge 4$ while $w'$ has order $-j_0 + 1 < -2j_0$, so $r$ has a pole of even order $2v = -2j_0$ at $c$, and the terms of $w$ of orders $-v, \ldots, -2$ satisfy $(\cdot)^2 \equiv r$ up to order $-v - 2$. So the polar part of order at least $2$ of $w$ is $\pm [\sqrt r]_c$. Comparing the coefficients of $(x - c)^{-v-1}$ gives $2 a\, \alpha - v a = b$, where $a$ is the leading coefficient of $[\sqrt r]_c$ with the chosen sign, $\alpha = u_{-1}$ and $b$ is the coefficient of $(x - c)^{-v-1}$ in $r - [\sqrt r]_c^2$. So $\alpha = \frac12(\pm b/a + v)$, the two values $\alpha_c^{\pm}$.
• If $j_0 = -1$, comparing the $(x - c)^{-2}$ coefficients gives $-\alpha + \alpha^2 = b$ for $b$ the coefficient of $(x - c)^{-2}$ in $r$. If $r$ has a pole of order $2$, $\alpha \in \{\frac12 \pm \frac12\sqrt{1 + 4b}\}$. If $r$ has a pole of order $1$ or no pole at $c$, then $b = 0$ and $\alpha = 1$, since $\alpha \ne 0$.
• If $j_0 \ge 0$, $w$ is regular at $c$.

So $r$ has no pole of odd order $\ge 3$, and at a pole of order $1$ the residue is $1$. At infinity the same comparison in the variable $1/x$ gives, for $o = -2v \le 0$, a polynomial part $\pm [\sqrt r]_\infty$ and coefficient $\alpha_\infty = \frac12(\pm b/a - v)$ of $1/x$ in $w$; for $o \ge 2$ a coefficient $\alpha_\infty \in \{\frac12 \pm \frac12 \sqrt{1 + 4b}\}$ with $b$ the coefficient of $x^{-2}$ in $r$, and for $o > 2$ this is $\{0, 1\}$; odd $o < 2$ is impossible.

Step 2 (case 1 is complete). Let $w \in \overline{K}(x)$ solve the Riccati equation. By Step 1, the partial fraction decomposition of $w$ is

where $c$ runs over the poles of $r$, the signs $\varepsilon$ and residues $\alpha$ are local choices of line L4, and the $z_j$ are the points where $w$ has a simple pole with residue $1$ but $r$ is regular. Let $\omega$ be the first two sums, the family's rational function of line L6, and $P = \prod_j (x - z_j)$, a monic polynomial of degree $d$, so that $w = \omega + P'/P$. The coefficient of $1/x$ in the expansion of $w$ at infinity is the sum of all residues, $\sum_c \alpha_c + d$, and by Step 1 it is $\alpha_\infty$, since $[\sqrt r]_c$ has no residue and $[\sqrt r]_\infty$ is a polynomial. So $d = \alpha_\infty - \sum_c \alpha_c$ is a nonnegative integer, and the family passes line L5. Finally, $y = P e^{\int \omega}$ has logarithmic derivative $w$, and

so $P$ solves the auxiliary equation of line L7, and the linear system of that line has a nonzero solution. The search of lines L5 to L7 tries every family, so it finds this one or an earlier successful one.

Step 3 (soundness). In case 1, if line L7 finds $P \ne 0$, the identity of Step 2 shows that $y = P e^{\int \omega}$ solves $L y = 0$, and $y$ is Liouvillian since $\omega$ and $P$ are rational. The returned $F = w - (\omega + P'/P)$ has the logarithmic derivative as its root. In case 2, let $P$ solve the third-order auxiliary equation, $\varphi = \theta + P'/P$, and let $w$ be a root of $F = w^2 - \varphi w + \left(\frac12 \varphi' + \frac12 \varphi^2 - r\right)$. Kovacic (1986), in the treatment of case 2, shows that the auxiliary equation is exactly the condition that the two roots $w_\pm$ of $F$ satisfy the Riccati equation, with $w_+ + w_- = \varphi$: writing $w_\pm = \varphi/2 \pm \sqrt{\Delta}$ with $\Delta = \varphi^2/4 - \frac12\varphi' - \frac12 \varphi^2 + r$, the Riccati equation for $w_\pm$ splits into its rational and irrational parts, the irrational part holds identically, and the rational part is a differential equation for $\varphi$ that becomes the auxiliary equation for $P$ after substituting $\varphi = \theta + P'/P$. In case 3, Kovacic (1986), in the treatment of case 3, shows that the recursion for $P_i$ with $P_{-1} = 0$ is the condition that the roots of the returned $F$ satisfy the Riccati equation. In each case the roots of $F$ are algebraic over $\overline{K}(x)$, and Lemma 1 turns them into Liouvillian solutions. Independently of these derivations, a root $w$ of a squarefree $F$ satisfies the Riccati equation exactly when $F$ divides $F_x + F_w (r - w^2)$ in $\overline{K}(x)[w]$, since implicit differentiation gives $w' = -F_x(w)/F_w(w)$, and the implementation checks this divisibility on every output.

Step 4 (cases 2 and 3 are complete). If case 1 fails and a Liouvillian solution exists, Lemma 2 places $G$ in case 2 or 3. Kovacic (1986) shows, by the same local comparison as in Step 1 applied to the symmetric functions of the conjugates of $w$, that at each point the leading data of $\theta$ lie in the finite lists $e_c$ and $e_\infty$ of line L4, that $d = \frac{n}{12}(e_\infty - \sum e_c)$ is the degree of a monic polynomial $P$ collecting the remaining poles, and that $P$ solves the auxiliary equation. So the family is tried at line L5 and line L7 finds a solution. In case 3, the degree $n$ is $4$, $6$ or $12$ by Lemma 2, and all three are tried.

Conclusion. If the algorithm returns at line L8, Step 3 gives a Liouvillian solution. If a Liouvillian solution exists, Lemma 2 puts $G$ in case 1, 2 or 3, Lemma 3 shows that its condition holds at line L2, and Steps 2 and 4 show that some family succeeds. So the return at line L9 happens exactly when no Liouvillian solution exists.

Termination. There are at most three cases and three values of $n$. Each point has finitely many local choices, at most $2$ in case 1, $3$ in case 2 and $n + 1$ in case 3, and there are finitely many points, so there are finitely many families. For each family, line L7 solves a linear system of finite size, $d + 1$ unknowns and finitely many equations from comparing coefficients, by Gaussian elimination. The Laurent expansions of line L4 need only finitely many terms. So the algorithm stops. $\blacksquare$