%From hoeij@zeno.math.fsu.edu Tue Nov 10 13:50:57 1998 %Return-Path: %To: hoeij@lars.math.fsu.edu, Manuel.Bronstein@sophia.inria.fr, % ragot@marie.polytechnique.fr, ulmer@felix.univ-rennes1.fr, % weil@unilim.fr %Subject: our paper % Felix, I added 1 line to section F_36, to point out that U^3 is % omega*identity, and hence in G. % I think the paper is ready now, and Jacques-Arthur wrote me he thinks the % same, so we can hand it over to our patient editor (sorry for letting you % wait so long!). % Regards, % Mark %%%%%%%%%%%%%%%%%%%%%%%%%%% LATEX %%%%%%%%%%%%%%%%%%%%%%%%% % version revised, 11 %\documentclass[twoside,12pt]{article} \documentstyle{jsc} %\usepackage{latexsym} %\sloppy %\input amssym.def %\input amssym %\pagestyle{headings} \addtolength{\topmargin}{-60pt} \addtolength{\topmargin}{17mm} \addtolength{\headsep}{12pt} \addtolength{\textheight}{60pt} \addtolength{\oddsidemargin}{0.4cm} % 0.4 \addtolength{\evensidemargin}{-1.1cm} % -1.0 \textwidth15.5cm \hoffset-1.5cm \parindent 0mm \newcommand{\n}{\mbox{N\hspace{- .730em}\rule{0.02em}{0.68em}\hspace{.7em}}} \newcommand{\co}{\mbox{C\hspace{- .455em}\rule{0.035em}{0.67em}\hspace{.5em}}} \newcommand{\rr}{\mbox{\rm R\hspace{- .730em}\rule{0.05em}{0.68em}\hspace{.7em}}} \newcommand{\q}{\mbox{\bf$Q\hspace{- .51em}$\rule{0.05em}{0.49em}\hspace{.4em}}} \newcommand{\z}{\mbox{\sf Z \hspace{-1.1em} Z}} \newcommand{\glk}[2]{\hbox{{\rm GL}}(#1,\,#2)} \newcommand{\slk}[2]{\hbox{{\rm SL}}(#1,\,#2)} \newcommand{\bold}[1]{\mbox{\boldmath $#1$}} \newcommand{\cC}{{\cal C}} \newcommand{\cG}{{\cal G}} \newcommand{\cP}{{\cal P}} \newcommand{\cS}{{\cal S}} \newcommand{\cT}{{\cal T}} \newcommand{\cA}{{\cal A}} \def\ZX{{\Bbb Z}} \def\CX{{\Bbb C}} \def\QX{{\Bbb Q}} \def\RX{{\Bbb R}} \def\NX{{\Bbb N}} \def\Cbar{{\overline{\cal C}}} \def\Ctilde{\tilde{\cal C}} \def\GAL{{\cal G}(L)} \def\Ly{{L(y)=0}} \def\QC{\overline{\QX}} \def\miprod{{\scriptstyle \bigcirc\hspace{-0.23cm}\raisebox{0.02cm}{${\scriptstyle s}$}}\hspace{0.1cm}} \def\symmetricpower{\mathop{\mathinner{ \bigcirc\mskip-13.5mu \raise0.5pt\vbox{\hbox{$s$}}\mskip3mu}}} \newcommand{\sympower}{\mbox{\footnotesize \vbox{\hbox{$\symmetricpower \,$}}}} \newcommand{\Lsympower}[1]{\mbox{ $L^{\raise2pt\vbox{\hbox{$\sympower $}} \raise3pt\vbox{\hbox{$\sSS #1$}}} $}} \newcommand{\eqcap}{\mbox{$\bigcap\mskip-4mu \raise0.15pt\vbox{\hbox{\footnotesize$)$}}$}} \newcommand{\eqcup}{\mbox{$\bigcup\mskip-4mu \raise0.55pt\vbox{\hbox{\footnotesize$)$}}$}} \def\pgcd{\hbox{{\rm pgcd}}} % -usual numbers \def\C{{\rm\kern.24em \vrule width.02em height1.4ex depth-.05ex \kern-.26em C}}\def\D{{\rm I\kern-.25em D}} \def\N{{\rm I\kern-.25em N}} \def\P{{\rm I\kern-.25em P}} \def\Q{{\rm\kern.24em \vrule width.02em height1.4ex depth-.05ex \kern-.26em Q}}\def\R{{\rm I\kern-.25em R}} \def\Z{{\rm\kern.26em \vrule width.02em height0.5ex depth 0ex \kern.04em \vrule width.02em height1.47ex depth-1ex \kern-.34em Z}} \def\Qbar{\overline{\Q}} \def\qbar{\Qbar} \def\pgcd{\hbox{{\rm pgcd}}} \def\gz{G/Z(G)} %%%%%%%%%%%%%%%%%%%%%%%%%%% \def\from{ From } %% this is to avoid email problems %\newenvironment{preuve}{{\em D\'emonstration.}}{\hfill$\Box$\\} %\newenvironment{proof}{{\em Proof.}}{\hfill$\Box$\\} %\newcounter{exo} %\def\thepart {\arabic{part}} % \newenvironment{remark}{ {\em Remark: }}{\hfill$\diamond$} \newenvironment{example}{ {\em Example: }}{\hfill$\diamond$} \newtheorem{theoreme}{Theorem} \newtheorem{theorem}{Theorem} \newtheorem{definition}{Definition} \newtheorem{corollaire}{Corollary} \newtheorem{proposition}{Proposition} \newtheorem{lemme}{Lemma} \newtheorem{lemma}{Lemma} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} %\pagestyle{myheadings} %\markright{\it Liouvillian solutions of linear differential equations} \label{firstpage} \title{Liouvillian Solutions of Linear Differential Equations of Order Three and Higher} \author[M. van Hoeij, J.~F. Ragot, F. Ulmer, and J.~A. Weil]{MARK VAN HOEIJ$^{\dagger}$, JEAN-FRAN\c{C}OIS RAGOT$^{\ddagger}$, FELIX ULMER$^{\star}$, AND JACQUES-ARTHUR WEIL$^{\ddagger}$ \\ $^{\dagger}$ Florida State University, U.S.A, hoeij@math.fsu.edu\nextaddress $^{\ddagger}$ Universit\'e de Limoges, France, ragot@unilim.fr, weil@unilim.fr\nextaddress $^{\star}$ Universit\'e de Rennes I, France, ulmer@univ-rennes1.fr } \date{July 98} \pagerange{\pageref{firstpage}--\pageref{lastpage}} \maketitle \begin{abstract} Singer and Ulmer (1997) gave an algorithm to compute Liouvillian (``closed-form'') solutions of homogeneous linear differential equations. However, there were several efficiency problems that made computations often not practical. In this paper we address these problems. We extend the algorithm in van Hoeij and Weil (1997) to compute semi-invariants and a theorem in Singer and Ulmer (1997) in such a way that, by computing one semi-invariant that factors into linear forms, one gets {\em all} coefficients of the minimal polynomial of an algebraic solution of the Riccati equation, instead of only one coefficient. %This way we no longer need to %% solve systems of polynomial equations %do large computations %to obtain the remaining coefficients. These %remaining coefficients come ``for free'' as a byproduct of our algorithm for computing semi-invariants. We specifically detail the algorithm in the cases of equations of order 3 (order 2 equations are handled by the algorithm of Kovacic (1986), see also Ulmer and Weil (1996) or Fakler (1997)).\\ In the appendix, we present several methods to decide when a multivariate polynomial depending on parameters can admit linear factors, which is a necessary ingredient in the algorithm. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% \section{Introduction} In this paper $k$ will denote a differential field whose field of constants ${\cal C}$ is algebraically closed of characteristic $0$. For the computations, however (Section \ref{comp}), we will consider more concretely the field ${\C}(x)$ with the usual derivation $d/dx$. We denote by $L = \partial^n + a_{n-1}\partial^{n-1} + \cdots + a_0 \partial^0$ ($a_i \in k$, $L \in k[\partial]$) a differential operator and by $L(y)=y^{(n)}+a_{n-1}y^{(n- 1)}+\cdots+a_0y=0$ the corresponding linear homogeneous differential equation. % We refer to %\cite{Mag94,Sin97} for definitions of a {\em Picard-Vessiot %extension\/} (PVE) of $k$, of the {\em differential Galois group\/} %$G$ and of {\em Liouvillian solutions\/} of $L(y)=0$. We now briefly recall the basic definitions from differential Galois theory that are needed later on (see Magid, 1994, Singer, 1997, or van der Put, 1998, for details and references).\\ A {\em Picard-Vessiot extension\/} (PVE) $K$ of $k$ for $L$ is a differential field extension $K=k$, where $\{y_1,\ldots,y_n\}$ a fundamental set of solutions, with no new constants in $K$. It is the equivalent of a splitting field for $L(y)=0$. Under our assumptions a PVE exists and is unique up to differential automorphisms. We denote by $V(L)$ the solution space $V(L)=\{y \in K | L(y)=0 \}$ of an operator $L$. The dimension of $V(L)$ equals the order of $L$. The {\em differential Galois group} $G$ of $L$ is the group of differential automorphisms of $K/k$. It acts faithfully on the vector space $V(L)$, and so $G$ can be viewed as a subgroup of $GL(V(L))$; more precisely, it is a linear algebraic group over ${\cal C}$. %The group $G$ acts faithfully on the vector space $V(L)$, and so $G$ %can %be viewed as a subgroup of $GL(V(L))$. There is a Galois correspondence between algebraic subgroups of $G$ and differential subfields of the PVE of $L(y)=0$. The fixed field of $G$ under this correspondence is $k$. \\ A solution of $L(y)=0$ in $k$ is called a {\em rational solution\/}, a solution in an algebraic extension of $k$ is called an {\em algebraic solution\/}, a solution whose logarithmic derivative is in $k$ is called an {\em exponential solution\/} and a solution belonging to a differential field obtained by successive adjunctions of integrals, exponentials of integrals and algebraic extensions is called a {\em Liouvillian solution\/}. If $L$ has a Liouvillian solution then $L$ also has a Liouvillian solution of the form $y={\rm exp}(\int r)$ where $r \in \overline{k}$ is algebraic over $k$ (see Singer, 1981 \& 1997). \begin{definition} An element $r$ of the PVE is called a {\em Riccati solution} for $L$ if $r$ is the logarithmic derivative $r=y'/y$ of some non-zero solution $y$ of $L$. If $r$ is an algebraic Riccati solution (a Riccati solution in $\overline{k}$) then the minimum polynomial of $r$ over $k$ is called a {\em Riccati polynomial} of $L$. \end{definition} \begin{definition} An element $I \in Sym^m(V(L))$ is called a {\em semi-invariant} of the differential Galois group $G$ of $L$ of degree $m$ if there is a character $\chi: G\mapsto{\cal C}$ of degree $1$ such that for all $g \in G$ the action of $g$ on $I$ is $g(I)=\chi(g)I$. If $\chi$ is the trivial character, i.e. $\forall g \in G, \, g(I)=I$, then $I$ is called an {\em invariant}. \end{definition} We call a polynomial or semi-invariant {\em completely factorable} if it is a product of linear factors. It is known (see section 2 in Singer and Ulmer, 1997) that an algebraic Riccati solution $r$ of degree $m$ over $k$ corresponds to a completely factorable semi-invariant $I$ of degree $m$ of the differential Galois group $G$. In Singer and Ulmer (1997), the Riccati polynomial of $r$ is computed as follows: \begin{enumerate} \item Compute the spaces of all semi-invariants up to a certain degree. This degree can be bounded in terms of the order of the operator using group theory. %(associated to some given characters) \item In each such space, find a completely factorable semi-invariant $I \in Sym^m(V(L))$ where $m$ is the degree. If such a semi-invariant is found, then $L(y)=0$ has an algebraic Riccati solution and the first coefficient of the associated Riccati polynomial is given by the logarithmic derivative of the value of $I$. The value of $I$ is the image of $I$ in $K$. \item In Singer and Ulmer (1997), the factorization of $I$ into linear forms is used to compute the remaining coefficients. This involves computing with splitting fields and so this step could be costly. \end{enumerate} % The goal of this % paper is, if a Liouvillian solution exists, to compute an algebraic Riccati % solution and its minimum polynomial over $k$ in an efficient way. % The main objective in this paper is to give an efficient method to compute (if it exists) a Riccati polynomial. The goal is a method that is efficient enough to handle operators of order 3 on a computer, or sometimes even higher order if the Riccati polynomial is not too big. First we extend the algorithm in van Hoeij and Weil (1997) for computing invariants to the case of semi-invariants. If a completely factorable semi-invariant is known and given in a certain form, then theorem~\ref{ricpoly} immediately gives us all coefficients of the Riccati polynomial. This central result avoids the third step above and makes the computation much more feasible in practice. In the appendix we discuss methods for finding the linear combinations of the basis corresponding to a completely factorable semi-invariant $I$ (second step). If the dimension of the vector space of semi-invariants for a character is high then it is a very costly step. This can be resolved by looking at semi-invariants (not always of minimal degree) that are guaranteed to be completely factorable. This is particularly interesting because the second step above, i.e.\ selecting a completely factorable semi-invariant which can be a very costly step, is then no longer needed. The result is a Kovacic-like algorithm for ${\rm order}(L)=3$, given in section~\ref{order3}. \vskip 1truecm \noindent{\bf Acknowledgments:} We thank Anne Bellido, Marius van der Put and Michael F.~Singer for fruitful conversations during the preparation of this paper.\\ J.A. Weil specially thanks Marius van der Put and the NWO {\sc aida} project for their material and intellectual support.\\ This research was partially supported by the European Cathode II working group and, for the third author, also by the {\sc Calife} project (INTAS-RBFR 95-0412).\\ Most computations were realized thanks to the French CNRS-UMS {\sc Medicis}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% \section{Semi-invariants of differential Galois groups} \label{semi-invariants} \subsection{The formalism} The basis of our approach is the following useful formalism: \begin{proposition}\label{phi} (van Hoeij and Weil, 1997, Proposition 2.5) Let $K$ be the Picard-Vessiot extension and $G$ the differential Galois group of $L$. Define the ${\cal C}$-algebra homomorphism \[ \phi: Sym(V(L)) \rightarrow K[X_1,\ldots,X_n] \] by (it suffices to define $\phi$ for homogeneous elements $\overline{y}$ of degree 1) \[ \phi(\overline{y})=\sum_{i=1}^n X_i y^{(i-1)} {\rm \ \ \ for \ \ \ } y \in V(L). \] Here $\overline{y}$ is the element of $Sym^1(V(L)) \subset Sym(V(L))$ that corresponds to the solution $y \in V(L) \subset K$ of $L$. Then $\phi$ is an embedding (as ${\cal C}$-algebra and as $G$- module) of $Sym(V(L))$ in $K[X_1,\ldots,X_n]$, where the action of $G$ on $X_1,\ldots,X_n$ is trivial. \end{proposition} If $I\in Sym(V(L))$, then we say that $\phi(I)$ is the {\em canonical image} of $I$ in $K[X_1,\ldots,X_n]$. Often the two vector spaces $V(L)$, which is a subset of $K$, and $Sym^1(V(L))$, which is a subset of $Sym(V(L))$, are identified. In this paper we can not directly do so because multiplication in $K$ is not the same as multiplication in $Sym(V(L))$. The following extension of Theorem $3$ of Singer and Ulmer (1997) illustrates the usefulness of the above formalism and is central to our approach. \begin{theorem} \label{ricpoly} Let $L(y)=0$ be a homogeneous linear differential equation over $k$. Let $K$ be a Picard-Vessiot extension of $k$ for $L$ and $G$ be its differential Galois group. Assume that $G$ has a semi-invariant $I \in Sym^m\left(V(L)\right)$ that is a product of linear factors and assume that the degree $m$ of $I$ is minimal with this property. Let $P(X_1,\ldots,X_n) = \phi(I) \in K[X_{1},\ldots,X_{n}]$ be its canonical image. Let $a$ be the coefficient of $X_{1}^m$ in $P$. Then: \begin{enumerate} \item $a \neq 0$ \item Let $Q:=\frac{1}{a} P(X,-1,0,\ldots,0)$. Then $Q\in k[X]$ and $Q$ is a Riccati polynomial. \end{enumerate} \end{theorem} \begin{proof} The semi-invariant $I$ is completely factorable, so $I=\prod_{i=1}^m \overline{y}_i$ where $\overline{y}_i \in Sym^1(V(L)) \subset Sym(V(L))$ and $y_i \in V(L)$ are the corresponding solutions of $L(y)=0$. Thus, as $P=\phi(I)$, we have \[ P = \prod_{i=1}^m (y_i X_1 + y_i' X_2 + \cdots + y_i^{(n-1)} X_n) \] If $g \in G$ then $g(y_i) \in {\cal C} y_j$ for some $j$ because of the uniqueness of factorization in $Sym(V(L))$ (which is isomorphic to a polynomial ring in $n$ variables over ${\cal C}$). Hence $G$ permutes the set $\{ \frac{y_1'}{y_1},\ldots,\frac{y_m'}{y_m} \}$. The action of $G$ on this set is transitive because $m$ is minimal. Note that $a = \prod y_i \neq 0$ because $P \neq 0$. \[ Q = \prod_{i=1}^m \frac1{y_i}(y_i \cdot X + y_i' \cdot (-1) + y_i'' \cdot 0 + \cdots + y_i^{(n-1)} \cdot 0 ) = \prod_{i=1}^m (X - \frac{y_i'}{y_i}). \] Since $G$ permutes the $\frac{y_i'}{y_i}$ it follows that $Q$ is invariant under $G$ and hence by the Galois correspondence $Q \in k[X]$. $Q$ is irreducible because the action of $G$ on the $\frac{y_i'}{y_i}$ is transitive. The Riccati solutions $\frac{y_i'}{y_i}$ are the roots of $Q$ and hence they are algebraic functions with minimum polynomial $Q$. \end{proof} Remark: with notations as above, if $m$ is not minimal, then it is easily seen that the polynomial $Q$ is either irreducible or a product of Riccati polynomials. Conversely, theorem 3 of Singer and Ulmer (1997) (combined with our theorem) shows immediately that any Riccati polynomial is obtained that way. This is used implicitly in section \ref{order3}.\\ % Remark: this criterion extends straightforwardly to systems %(without priorly converting % them to an equation). % MVH: how? % JAW: if Y= {}^t (Y1,..,Y_n) is a (Liouvillian) solution %then the min.poly % of $Y_2/Y_1$ is given by the above criterion (same proof!). % one obtains similarly the minpoly of $Y_i/Y_j$ The algorithm presented in van Hoeij and Weil (1997) computes the invariants $I$ of $G$ by computing their images $\phi(I)$. The reason for using $\phi$ in van Hoeij and Weil (1997) was to be able to compute invariants without having to compute symmetric powers $Sym^m(L) \in k[\partial]$. In the following, this same approach is extended to the computation of semi-invariants. The above then shows that this approach does not only produce the semi-invariant whose logarithmic derivative is the first coefficient of the Riccati polynomial, but in fact gives all the coefficients. This makes this algorithm for computing (semi)-invariants very suitable for finding Liouvillian solutions. We now proceed with the computation of semi-invariants via the above formalism. The next subsection is rather technical and will be easier if the reader knows about the paper of van Hoeij and Weil (1997) and about Beke's method for computing exponential solutions of operators (see van Hoeij, 1997, Singer, 1997, or Pfl\"ugel, 1998 for details and additional references). \subsection{Computation of semi-invariants} \label{comp} \begin{lemma} The image of a semi-invariant under the embedding $\phi$ is an element of $a \cdot k[X_1,\ldots,X_n]$ where $a={\rm exp}(\int y)$ for some $y \in k$. \end{lemma} \begin{proof} Let $I$ be a semi-invariant of degree $m$, and $P=\phi(I)$. Because $\phi$ is a $G$-homomorphism, $g(P)=\chi(g)\cdot P$ for some character $\chi$. Let $a \in K$ be one of the non-zero coefficients of $P \in K[X_1,\ldots,X_n]$. Now $g(\frac1a P)=g(\frac1a)\chi(g) P = \left( a\, g(\frac1a)\, \chi(g)\right) \frac1a P$. The action of $G$ on the $X_i$ is trivial, so that the coefficients of $g(\frac1a P)$ are just the image of the corresponding coefficients under $g$. One of the coefficients of $\frac1a P$ equals 1 and since $g(1)=1$ the corresponding coefficient of $g(\frac1a P)$ must also be 1. Hence $\forall g \in G,\, a g(\frac1a) \chi(g) =1$ and so $\frac1a P$ is invariant under $G$. By the Galois correspondence \[ \frac1a P \in k[X_1,\ldots,X_n]. \] Furthermore $\forall g \in G,\, g(a)=\chi(g) \cdot a$ showing that $a'/a$ is left invariant by $G$ and thus $y=a'/a \in k$. \end{proof} \begin{remark} Using the embedding $\phi$, we will often identify semi-invariants with elements of $K[X_1,\ldots,X_n]$. \end{remark} \begin{definition} For $t \in k$, we note $\cS_t^*$ the $k$-automorphism of $k[\partial]$ defined by $\cS_t^*(\partial)=\partial+t$. \end{definition} % ... % We would like to view this map as multiplication by $a^m$. This is % problematic, however, because $Sym^m(V(L))$ is not a $K$-vector % space but a ${\cal C}$-vector space; % multiplication by $a^m$ is not defined on $Sym^m(V(L))$. % Instead we will % examine which map $\cdot a$ induces on % $\phi(Sym(V(L))) \subset K[X_1,\ldots,X_n]$. % This induced map on $\phi(Sym(V(L)))$ is denoted by $\phi_a$. % A solution $y \in V(L)$ is mapped by $\cdot a$ to $ay$. % Now $(ay)'=a y'+a'y=a(y'+ty)$ where % $t=a'/a \in k$, % and $(ay)^{(i)}=a(y^{(i)}+\alpha(t,i,i-1)y^{(i-1)}+ % \cdots+\alpha(t,i,0)y)$ for some $\alpha(t,i,j) \in k$. % So $\phi_a$ acts on $(yX_1+y'X_2+\cdots+y^{(n-1)}X_n)$ % as the following substitution: % \begin{equation} % (X_1,X_2,\ldots,X_n)^t \mapsto a \cA \cdot (X_1,X_2,\ldots,X_n)^t % \label{subs_X} % \end{equation} % where $\cA$ is a lower triangular matrix, with $1$'s on the diagonal, and % entries $\cA_{i,j}=\alpha(t,i-1,j-1) \in k$ below the diagonal. % Because all elements of $\phi(Sym^m(V(L)))$ are sums of products of % expressions of the form $yX_1+y'X_2+\cdots+y^{(n-1)}X_n$, the % substitution~(\ref{subs_X}) describes $\phi_a$. % On the vector of all monomials in $X_1,\ldots,X_n$ of degree $m$, % $\phi_a$ acts as $a^m M$ for some unipotent matrix $M$ % (computed from matrix $\cA$) with entries in $k$. % If $S=b \cdot I$ is a semi-invariant of degree $m$ % where $b'/b \in k$ and $I \in k[X_1,\ldots,X_n]$, then % $\phi_a(S)$ is a semi-invariant of the form $a^mb I_1$ for some % $I_1 \in k[X_1,\ldots,X_n]$. % In particular, $\phi_a(S)$ is an % invariant if and only if $a^mb \in k$. % %MVH: we don't need this analysis, so I replaced it with something shorter % below the following definition. \begin{definition} The equivalence relation $\sim$ on $k$ is defined as follows: $t_1 \sim t_2$ %iff when there exists $y \in k$ for which $t_1 - t_2=y'/y$. \end{definition} Let $V(L) \subset K$, $a \in K$ and assume $t = a'/a \in k$. Then multiplication by $a$ is a ${\cal C}$-linear map \[ \mu_a: V(L) \rightarrow V(\cS_{-t}^*(L)). \] % It is a $G$-isomorphism if and only if $a \in k$. The map $\mu_a$ induces a 1-1 linear map \[ \mu_a: Sym^m(V(L)) \rightarrow Sym^m(V(\cS_{-t}^*(L))). \] Let $S \in Sym^m(V(L))$, $g \in G$. Then $g(\mu_a(S))=\mu_a(g(S)) \cdot g(a^m)/a^m$ % (note that $g \mapsto g(a^m)/a^m$ is a character of degree 1 of $G$) so if $S$ is a semi-invariant then $\mu_a(S)$ is an invariant if and only if $g(S)=S \cdot a^m/g(a^m)$ for all $g \in G$. % Furthermore % $S$ is a semi-invariant if and only if $\mu_a(S)$ is a % semi-invariant. % Furthermore $\mu_a$ is a $G$-isomorphism from $Sym^m(V(L))$ to % $Sym^m(V(\cS_{-t}^*(L)))$ if and only if $a^m \in k$, if and only if % $mt \sim 0$. If $S$ is a semi-invariant then $\phi(S)$ is of the form $\phi(S)=b \cdot I$ for some $I \in k[X_1,\ldots,X_n]$, $b \in K$ with $t_1 = b'/b \in k$. Then $g(S)=S \cdot g(b)/b$, so $\mu_a(S)$ is an invariant if and only if $g(b)/b = a^m/g(a^m)$ for all $g \in G$. This holds if and only if $b \cdot a^m \in k$, if and only if $-tm \sim t_1$. %The map $\mu_a$ induces a map on $\phi(Sym^m(V(L)))$ that we will %denote by $\phi_a$. Let $L$ be a differential operator and $K$ the Picard-Vessiot extension. Let $S \in \phi(Sym^m(V(L))) \subset K[X_1,\ldots,X_n]$ be a semi-invariant of degree $m$. So $S = b \cdot I \in K[X_1,\ldots,X_n]$ for some $b \in K$, $I \in k[X_1,\ldots,X_n]$. Let $t_1=b'/b \in k$. %% MOVED The map $\mu_a$ induces a map on $\phi(Sym^m(V(L)))$ that we will denote by $\phi_a$. %% Then $\phi_{{\rm exp}(\int -t/m)}(S)$ is an invariant of $\cS_{t/m}^*(L)$ if and only if $t \sim t_1$. In order to compute all semi-invariants of degree $m$, we will construct from $L$ a finite set $B$, such that whenever $L$ has a semi-invariant in $b \cdot k[X_1,\ldots,X_n]$ then $(b'/b \ {\rm mod} \sim) \in B$. Then for each $t_1 \in B$ we take a $t \in k$ with $t \sim t_1$ and determine the invariants of $\cS_{t/m}^*(L)$. If $I \in k[X_1,\ldots,X_n]$ is an invariant of $\cS_{t/m}^*(L)$, then the corresponding semi-invariant of $L$ is $S = \phi_{{\rm exp}(\int t/m)}(I)$. The remaining problem is to determine the set $B$, which will be done using the generalized exponents, in a way similar to the computation of the bounds in van Hoeij and Weil (1997). This leads to the algorithm below. \\ %\subsection{Computation of semi-invariants} %\label{comp} In the rest of this section, we assume that $k= \C(x)$. \noindent{\bf Algorithm Semi-invariants.} \\ {\bf Input:} a differential operator $L \in \C(x)[\partial]$ of order $n$, and an integer $m$. \\ {\bf Output:} all semi-invariants of degree $m$. \\ {\bf Step 1}. Compute a finite set $B \subset \C(x)/\sim$ such that for all semi-invariants $aI$ of $L$, $a \in K$, $I \in \C(x)[X_1,\ldots,X_n]$ the equivalence class of $\frac{a'}{a}$ is an element of $B$. \\ {\bf Step 2}. For each element of $B$ take a representant $t \in \C(x)$ and compute the invariants of $\cS_{t/m}^*(L)$. These correspond to semi- invariants of $L$.\\ Note that this algorithm resembles Beke's algorithm for computing exponential solutions ${\rm exp}(\int t)$ with $t \in \C(x)$. We give the same sketch of this algorithm as in section~4 in van Hoeij (1997): \\ {\bf Step 1}. Compute a finite set $B \subset \C(x)/\sim$ such that for all exponential solutions $a$ one has $(\frac{a'}{a} {\rm \ mod} \sim) \in B$. \\ {\bf Step 2}. For each element of $B$ take a representant $t \in \C(x)$ and compute the rational solutions of $\cS_t^*(L)$. Return the corresponding exponential solutions of $L$.\\ {\it Computation of set $B$ in step 1 of algorithm semi-invariants:} \\ % {\bf here, recall sketchy def of % generalized exponents via formal sols + ref}\\ In van Hoeij and Weil (1997) and van Hoeij (1997) a generalization of the classical notion of exponents has been defined. A generalized exponent is an element of $\C[x^{-1/r}]$ for some integer $r$ (called the ramification index). In the regular singular case the generalized exponents are the exponents and the ramification index is 1 in this case. For $t \in \C(x)$ and $p \in \P^1(\C)$ denote $EP_p(\partial-t) \in \C[x^{-1}]/\z$ as the generalized exponent $e \in \C[x^{-1}]$ at the point $p$ of $\partial-t$ modulo the integers. $EP_p(\partial-t)$ is the {\em exponential part} of $\partial-t$ at $p$. Now $t$ modulo $\sim$ is determined by the $EP_p(\partial-t)$ for all $p$ (van Hoeij, 1997). Let $e \in \C[x^{-1}]$ be the generalized exponent of $\partial-t$ at the point $p$. Then $e/m$ is the generalized exponent of $\partial-t/m$ at $p$. The generalized exponents of $\cS_{t/m}^*(L)$ at $p$ equal $-e/m$ plus the generalized exponents of $L$ at $p$. So the generalized exponents of the monomials in lemma~28 in section~4.1 in van Hoeij and Weil (1997) for $\cS_{t/m}^*(L)$ are $-e$ plus the generalized exponents of the monomials for $L$. According to this lemma, at least one of those generalized exponents should be in $\frac1r \z$ (where $r$ is the ramification index at $p$) if $\cS_{t/m}^*(L)$ has an invariant. This leaves only finitely many possibilities for $e$ modulo $\z$ and hence for $EP_p(\partial-t) = e+\z \in \C[x^{- 1}]/\z$. At regular points, there is only one possibility for $e+\z$, namely $e+\z=\z$, because $r=1$ and the generalized exponents are integers at regular points. At a singular point $p$, we can compute all generalized exponents of $L$, and all generalized exponents of the monomials in the lemma (these are sums of $m$ generalized exponents of $L$) and so we can compute a finite set of possible values of $EP_p(\partial-t)$. If $p_1,\ldots,p_l$ are the singularities, and we find $N_i$ possible $EP_{p_i}(\partial-t)$ then we have $N=N_1 \cdot N_2 \cdots N_l$ possible combinations, so we find at % most\footnote{although $t$ modulo $\sim$ is determined the % $EP_p(\partial-t)$ at all singularities, not every combination of %exponential % parts $EP_p(\partial-t)$ can occur because there exists a relation %between % these $EP_p(\partial-t)$, namely lemma~26 in section~3.9.1 in %\cite{vHthesis}} most\footnote{not every combination of exponential parts corresponds to a $t$, only those combinations that satisfy %% ADDED a generalized %% Fuchs' relation (lemma 9.2 in van Hoeij, 1997)} $N$ possible values of $t$ modulo $\sim$. These $t$ modulo $\sim$ are the elements of the set $B$ in the algorithm. \\ A comment on step 2: We need to compute invariants of a number of operators (one for each element of $B$). It can be faster first to apply the heuristic algorithm in van Hoeij and Weil (1997), and to apply the complete algorithm invariants in van Hoeij and Weil (1997) only for the cases when the heuristic does not prove that no invariants exist. \\ Another efficiency improvement can be obtained as follows: For computing the invariants of $\cS_{t/m}^*(L)$ we need the generalized exponents of $\cS_{t/m}^*(L)$ at all singularities. However, these can be easily computed from $t$ and the generalized exponents of $L$. Furthermore we compute with formal solutions of $\cS_{t/m}^*(L)$ at one singularity, but these can be computed from the formal solutions of $L$. This way we only need to compute generalized exponents and formal solutions of $L$, not of each $\cS_{t/m}^*(L)$ for every $t \in B$. \\ Our algorithm for computing semi-invariants has the same drawback as Beke's algorithm for computing exponential solutions: If the singularities or the generalized exponents involve algebraic extensions over the coefficients field then the algorithm may need to compute in exponentially large algebraic extensions. For $m=1$ it is in fact the same algorithm. If the set $B$ is very large then the computation can also be long. However, in many examples the generalized exponents are rational numbers, and the number of singularities is small (typically 3) so that $B$ will not be big. In such examples computing semi-invariants will not be so hard. \\ Sometimes, e.g. step [2.1] in section~\ref{algo_order3}, we need to compute only those semi-invariants whose $n$-th power is rational (with $n\in\N$ given). The computation is then shorter: in step 2 of algorithm semi-invariants, we need only to consider those $t \in B$ for which $nt \sim 0$ (i.e. the generalized exponents of $\partial-t$ are in $\frac1n \z$). This will be used in section~\ref{order3}. Invariants are rational solutions of a system of differential equations, the symmetric power system $Y'=S^m(A)Y$ in section 2.1.2 of van Hoeij and Weil (1997). Semi-invariants are exponential solutions of this system. So invariants and semi-invariants can be obtained by applying the algorithms in Barkatou (1998) and Pfl\"ugel (1997) on the symmetric power system. However, this can be a costly computation because the dimension of the $S^m(A)$ can be very high, and because the algorithms in Barkatou (1998) and Pfl\"ugel (1997) are general, so they do not benefit from the special structure of the symmetric power system. \subsection{A fourth-order example with group FP28} The following operator (constructed with the methods of van der Put and Ulmer, 1998) has a Galois group which is a central extension of $S_5$ (FP28 in the notation of Hessinger, 1998). \begin{eqnarray*} L = & \partial^4 +4\frac{(2x-1)\partial^3}{x(x-1)} +\frac{ (2295x^2-2032x+105 )\partial^2}{ 160 x^2(x-1)^2} + \frac {(1500x^2-287x+105)\partial}{320(x-1)^2x^3} \\ & +\frac{7(148000x+9375x^4-10088x^3-67250x^2-73125)}{2560000 x^4(x-1)^4}. \end{eqnarray*} Its exponents at the singularities $0$, $1$, and $\infty$ are \[ E_0 = \{ -{\frac {7}{8}},\frac18,{\frac {9}{8}},{\frac {13}{8}} \}, \ E_1 = \{ \frac1{10},\frac3{10},{\frac {7}{10}},{\frac {9}{10}} \}, {\rm \ and \ } E_{\infty} = \{ \frac18, \frac38, \frac58, \frac78 \}. \] The group FP28 has semi-invariants of degree 5, including a completely factorable semi-invariant. Following our method, we do the following to compute all semi-invariants of degree $5$. Let $E_p+E_p+E_p+E_p+E_p$ be the set of all sums of $5$ exponents at $x=p$. Let $F_p$ be this set modulo $\frac1{r_p} \z$ where $r_p$ is the ramification index. All ramification indices $r_p$ are $1$ in this example, so $F_p$ is just $E_p+\cdots+E_p$ modulo the integers (i.e. we take the fractional parts of the elements of $E_p+\cdots+E_p$). Then one finds $F_0=\{1/8, 5/8\}$, $F_1=\{1/10, 3/10, 1/2, 9/10, 7/10\}$ and $F_{\infty}=\{1/8, 3/8, 7/8, 5/8\}$. We need to try $\cS_{t/5}^*(L)$ for all $t = c_0/x + c_1/(x-1)$ for which \begin{enumerate} \item $0 \leq c_i < 1$ for $i \in \{0,1\}$. \item $(c_p + \frac1{r_p}\z) \bigcap F_p$ is non-empty for $p \in \{0,1,\infty\}$, where $c_{\infty}=-c_0-c_1$. \end{enumerate} In general the $c_i$ are taken in $\co[x^{-1/r_p}]$ modulo $\frac1{r_p}\z$, but since all generalized exponents are rational numbers we can take $c_i$ to be non-negative rational numbers smaller than $1$. The above conditions leave only very few (namely 2) cases for $t$, so computing all semi-invariants of $L$ of degree $5$ does not take much computer time here. Let $\tilde{L}={\cal S}^*_{t/5}(L)$ where $t=5/(8x) + 1/(2(x-1))$. With the algorithm from van Hoeij and Weil (1997), we compute the 2-dimensional space of invariants of degree 5 of $\tilde{L}$, and determine an invariant that factors into linear factors using the appendix. We then apply theorem~\ref{ricpoly} and obtain the following Riccati polynomial: \begin{eqnarray*} P = & X^5 (122683392\,{x}^{3}+246481521\,{x}^{2}+184373150\,x-557519375) \\& +X^4 (245366784\,{x}^{3}+ 739444563\,{x}^{2}+737492600\,x-2787596875)/ x \\& + X^3(966131712\,{x}^{4}+3750651762\,{x}^{3}+2746408210\,{x}^{2} \\& -33407163250\,x+27875968750)/ (5\left (x-1\right ){x}^{2}) \\ & + X^2(1878589440\,{x}^{5}+10760213334\,{x}^{4}+11619977980\,{x}^{3} \\& - 183778983600\,{x}^{2}+297197002500\,x-139379843750)/(25\left (x-1\right )^{2}{x}^{3}) \\ & + X(1808142336\,{x}^{6}+15408360513\,{x}^{5}+43238642915\,{x}^{4} \\& -522670373950\,{x}^{3}+1182921498750\,{x}^{2}-1068395471875\,x+ \\& 348449609375)/(125\left (x-1\right )^{3}{x}^{4})\\ & + X^0 (3451908096\,{x}^{7}+41967774147\,{x}^{6}+302211588068\,{x}^{5} \\& -3042266659625\,{x}^{4}+8490891950000\,{x}^{3}-11023761109375\,{x}^{2} \\& +6968992187500\,x-1742248046875)/(3125\left (x-1\right )^{4}{x}^{5}) \end{eqnarray*} Let $r \in \overline{ \co(x) }$ be a root of $P$. Then ${\rm exp}(\int r \ dx)$ is a Liouvillian solution (in fact: algebraic solution, but we have not computed its minimum polynomial) of $\tilde{L}$. To obtain a solution of $L$ we have to multiply by ${\rm exp}(\int t/5 \ dx)$, so we find the following Liouvillian solution of $L$ \[ {\rm exp}(\int (r+\frac{t}5) \ dx) = x^{1/8}(x-1)^{1/10} \cdot {\rm exp}(\int r \ dx) \in V(L). \] We could also compute a semi-invariant of $L$ from the invariant of $\tilde{L}$, and apply theorem~\ref{ricpoly} on that. The Riccati polynomial obtained that way has $r+\frac{t}5$ as solution, so it can be also be obtained from $P$ by a substitution. In most examples we prefer to compute a Riccati polynomial through invariants, not semi-invariants, because invariants are easier to compute. However, FP28 has a 5-dimensional space of invariants of degree $8$, and no invariants of lower degree. So computing a completely factorable invariant will be very difficult because it has to be selected from a high dimensional space. So for FP28 it is easier to use semi-invariants. \subsection{Constructors of semi-invariants} \label{constructors} In this part, we list some results from Weil (1995b) that will be used in section \ref{order3}. Let $X$ denote the transposed vector $(X_1,\ldots,X_n)^t$. Let $D$ be the derivation on $K[X_1,\ldots,X_n]$ defined by $D(X)=-A^t X$ and $D$ is the usual derivation on $K$. Then, $\phi(Sym(V(L)))=\{ P\in K[X_1,\ldots,X_n] : D(P)=0\}$ (Weil, 1995a)\footnote{In fact, this derivation turns $K[X_1,\ldots,X_n]$ into a differential module isomorphic to $Sym\left({\cal D}/{\cal D}L\right)$.}. Let $S$ be a semi-invariant of degree $m$, and $P=\phi(S)$ be its canonical image in $K[X_1,\ldots,X_n]$. In this setting, it is shown in Weil (1995b, proposition 50, section 6, page 57) that the Hessian of $P$ (with respect to $X_1,\ldots,X_n$) is again, up to multiples, the canonical image of a semi-invariant (same results hold for the bordered Hessian and the Jacobian). Thus, once a semi-invariant is known, we can apply directly Hessians and related constructors on its canonical image (see Weil, 1995b, section 6.3 page 65 for a fairly detailed example). In view of theorem~\ref{ricpoly}, this will allow (in section \ref{order3}) to construct Riccati polynomials of high degrees directly from invariants of small degree. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%% \section{Computing Liouvillian solutions of equations of order $n$} \label{ordern} \begin{lemma} If $L$ is reducible and $L$ has a Liouvillian solution then $L$ has an irreducible right-hand factor $R \in \C(x)[\partial]$ that has a Liouvillian solution. \end{lemma} \begin{proof} The Liouvillian solutions of $L$ form a subspace of $V(L)$ that is invariant under the differential Galois group. Hence there exists a right-hand factor $R'$ having this subspace as solution space. Now take for $R$ any irreducible right-hand factor of $R'$. \end{proof} \from the fact that an operator $M$ that has a Liouvillian solution must have a solution of the form ${\rm exp}(\int r)$ for some algebraic function $r \in \overline{\C(x)}$, i.e.\ $M$ has a right-hand factor of order 1 in $\overline{\C(x)}[\partial]$, it follows by induction that if all solutions are Liouvillian then $M$ is completely factorable in $\overline{\C(x)}[\partial]$ (i.e. $M$ is a product of operators of order 1). Conversely, if $M$ is completely factorable then all solutions are Liouvillian. Hence the operator $R'$ in the lemma is the highest order right-hand factor of $L$ that is completely factorable in $\overline{\C(x)}[\partial]$. \begin{itemize} \item[1] Reducible case. If $L$ is reducible and has a Liouvillian solution then according to the lemma there exists an irreducible right-hand factor that has a Liouvillian solution. Though there may be infinitely many different right-hand factors, there are only finitely many {\em types} (Tsarev, 1996, Singer, 1995) of irreducible right-hand factors. For each type we need to compute one right-hand factor and compute the Liouvillian solutions of that factor. This way we find a Liouvillian solution of $L$, if such solution exists. \item[2] Irreducible case. In Singer and Ulmer (1993b) and references therein, the authors give an upper bound for the lowest degree of (if it exists) a Riccati polynomial of $L$. So, by checking a finite number of degrees, one can decide if a Riccati polynomial exists. For each possible degree $m$, compute the semi- invariants of degree $m$ and check (see appendix A) if there is a completely factorable semi-invariant. If so, return the corresponding Riccati polynomial. % If we have a classification of the possible groups, % then one can reduce the % number of different degrees $m$ that need to be checked. \end{itemize} In the algorithms the irreducible case is usually split into the imprimitive and the primitive case (containing only a finite list of possible groups); this is explained in Singer and Ulmer (1993b).\\ Several ideas from section \ref{order3} below can be re-used when handling equations of higher order (e.g.\ the fact that knowing in advance which groups to check for allows us to check only a small number of degrees for the semi-invariants). The important classification work of Hessinger (1998) should pave the way to a better algorithm for computing Liouvillian solutions of equations of order~4. \section{Computing Liouvillian solutions of equations of order 3} \label{order3} The general algorithm can be improved in several ways. First of all, the computation of semi-invariants can often be avoided. For example in the case that $L$ is irreducible of order $2$, we know from Ulmer and Weil (1996) that it is sufficient to compute only invariants, which are easier to compute than semi-invariants. The factorization of a semi-invariant (cf.\ appendix A) becomes a problematic step if the number of parameters is not small. For second order equations this problem does not occur because any invariant will factor into linear forms. For third order equations we will use section~\ref{constructors} to find invariants that are guaranteed to factor, so that appendix A can be avoided in most cases. Furthermore we can reduce the size and number of different degrees $m$ that need to be checked by studying the possible Galois groups. In this section, we develop along these guidelines a Kovacic-like algorithm for computing Liouvillian solutions of linear differential equations of order 3. For the possible Galois groups, we follow the notations from Singer and Ulmer (1993a, 1993b). \subsection{The algorithm} \label{algo_order3} Let $L = \partial^3 + a_2 \partial^2 + a_1 \partial + a_0$ where the $a_i \in \C(x)$. If there exists an $f\in k$ such that $f'/f=a_{2}$, then $G \subset SL_3$; if not, then we can first apply $\cS_{-a_2/3}^*$ to $L$ so that the coefficient $a_2$ will vanish. Hence, we may assume in all that follows that the Galois group is unimodular, i.e. $G \subset SL_3$. Remark: in the algorithm below, the sentences ``there are $s$ invariants of degree $m$'' should be understood as ``the vector space of all invariants of degree $m$ has dimension $s$''. %\noindent{\bf Algorithm for Liouvillian solutions.} \\ \begin{itemize} \item[1] Reducible case. \subitem[1.1] If $L$ can be written as $L_1 \cdot (\partial-r)$ for some $r \in \C(x)$ then let $a={\rm exp}(\int r)$ and compute a basis $y_1,y_2$ of solutions of $L_1$. Return $a,a \int\left(y_1/a\right),a \int\left(y_2/a\right)$. \subitem[1.2] If $L$ allows only a factorization $L=L_1 L_2$, where $L_2$ has order 2. Then %$L$ has a Liouvillian solution only if % $L_2$ has a Liouvillian solution. apply the Kovacic algorithm on $L_2$. If a basis of Liouvillian solutions is found, then (assume that $L$ is monic) $L$ can be factored as $(\partial -r )(\partial - a)(\partial-b)$ for some algebraic functions $a$ and $b$ and rational function $r$. Let $z_1={\rm exp}(\int (a-b)\,dx)$ and $z_2=\int {\rm exp}(\int (r- a)\,dx)\,dx$. Then $y_1 = {\rm exp}(\int b \, dx)$, $y_2 = y_1 \int z_1 \, dx$ and $y_3 = y_1 \int z_1z_2 \, dx$ is a basis of Liouvillian solutions of $L$. % apply reduction of order to obtain the % remaining solution \item[2] Test if the group is imprimitive by doing one of the following steps, 2.1 or 2.2: \subitem[2.1] Compute all semi-invariants of degree 3 whose square is invariant (see the remark at the end of section~\ref{comp}). Decide if one of these semi-invariants has a linear factor (use Appendix A if there is a semi-invariant linearly depending on parameters\footnote{i.e.\ a vector space of semi-invariants corresponding to the same character.}). If this is the case then the group is imprimitive; return the Riccati polynomial $Q$ using theorem~\ref{ricpoly}. Otherwise the group is not imprimitive; proceed with step 3. \subitem[2.2] Compute invariants of degree 6 and decide which of those is a square (see Appendix~A4). The corresponding square roots are all semi-invariants of degree three whose square is invariant. Now proceed as in [2.1]. \item[3] Compute the invariants of degree 2. If there is one (there can not be more) then compute the invariants of degree 6 and one of the following two cases applies; otherwise proceed with step 4. \subitem[3.1] Either there is ONE invariant of degree 6; then $G \simeq PSL_2^{SL_3}$ and there is no Liouvillian solution. \subitem[3.2] Or there are TWO invariants of degree 6; then $G\simeq A_5^{SL_3}$. Return either the unique Riccati polynomial of degree 6 (the corresponding completely factorable invariant must be found in a space of dimension $2$) or the unique Riccati polynomial of degree 15 %corresponding to the unique invariant of degree $15$ obtained from section \ref{A5}. \item[4] Compute invariants of degree 4. If there is one (there can not be more), then $G \simeq G_{168}^{SL_3}$. Return the Riccati polynomial of degree 21 %corresponding to the unique invariant of degree 21. obtained in section \ref{G168} \item[5] Compute invariants of degree 6: % \footnote{Note that, if step 2.2 has % been used, then these invariants of degree 6 are already computed.} \subitem[5.1] If there are NO such invariants then one of the following 2 cases applies; otherwise proceed with step 5.2. % $\gz\simeq H_{216}^{SL_3}$ or $G \simeq SL_3$. \subsubitem[5.1.1] If there is one invariant of degree 9 (there can not be more), then $G \simeq H_{216}^{SL_3}$. Return the corresponding Riccati polynomial of degree $9$. \subsubitem[5.1.2] Else, the group is $SL_3$ and there are no Liouvillian solutions. \subitem[5.2] If there is ONE invariant of degree 6, then one of the following 4 cases applies; if there are more invariants of degree 6 then proceed with step 5.3. %$\gz\simeq PSL_2^{SL_3} \times C_3$ %or $\gz\simeq G_{168}^{SL_3}\times C_3$ %or $\gz\simeq A_6^{SL_3}$ %or $\gz\simeq H_{72}^{SL_3}$. \subsubitem[5.2.1] If the invariant is a cube (Appendix A4), then $G \simeq PSL_2^{SL_3} \times C_3$ and there are no Liouvillian solutions. \subsubitem[5.2.2] %Compute invariants of degree 9. If there is one invariant of degree 9 (there can not be more), then $G\simeq H_{72}^{SL_3}$. Return the corresponding Riccati polynomial of degree $9$. \subsubitem[5.2.3] If there is an invariant\footnote{Alternatively, at this step, one could directly search for a (unique) semi-invariant of degree 4 whose cube is rational. Or, to avoid factorisation, one could compute the dimension of the space of invariants of degree 18 (dimension 2 for $G_{168}^{SL_3}\times C_3$ and dimension 3 for $A_6^{SL_3}$).} of degree 12 which is the cube of a semi-invariant $S$ (Appendix A4), then $G \simeq G_{168}^{SL_3}\times C_3$. Return the Riccati polynomial of degree 21 corresponding to the unique invariant of degree 21 obtained in section \ref{G168xC3} \subsubitem[5.2.4] Else $G\simeq A_{6}^{SL_{3}}$. Return the Riccati polynomial of degree 45 corresponding to the unique invariant of degree 45 obtained in section \ref{A6} \subitem[5.3] If there are TWO invariants of degree 6, then one of the following 2 cases applies: %either $\gz\simeq A_5^{SL_3}\times C_3$ %or $\gz\simeq F_{36}^{SL_3}$. \subsubitem[5.3.1] %Compute invariants of degree $9$. If there is one invariant of degree 9 (there can not be more), then $G \simeq F_{36}^{SL_3}$; Return the corresponding Riccati polynomial of degree 9. \subsubitem[5.3.2] Else, $G \simeq A_5^{SL_3}\times C_3$. Return either the unique Riccati polynomial of degree 6 (the corresponding completely factorable invariant must be found in a space of dimension $2$) or the Riccati polynomial of degree $15$ %corresponding to the unique invariant of degree 15 obtained in section \ref{A5xC3}. \end{itemize} \subsection{Practical remarks on the algorithm} We note that, in practice, some cases from the algorithm can be quickly excluded by the necessary conditions from Singer and Ulmer (1995) and/or the heuristic from section 4.1 in van Hoeij and Weil (1997). For example, if the equation is not Fuchsian, then there are Liouvillian solutions if and only if step 1 or step 2 succeeds.\\ One consequence of the above algorithm is that we can decide whether an irreducible third order equation has Liouvillian solutions by using only invariants of degrees 2, 4, 6, and 9.\\ Another remark concerns the rationality problem: % if we compute as much % as possible with invariants, then we % constant field in the course of the computation (see %\cite{VPH94,Ulm94,UWe96} % for more details). % MVH: I wanted to be very careful here, the output of algorithm %invariants % is rational, and that is all that is important at this point. % But I want to avoid giving readers the impression that no % algebraic extensions appear during the computation, and so things %have % to be formulated very precisely. % JAW: agreed. The algorithm we use for computing invariants, unlike for semi- invariants, does not introduce algebraic extensions in its output $\phi(I)$. % In particular, % it follows from (\cite{VPH94,Ulm94}) % and our decomposition above that The only case of an irreducible operator $L$ of order 3 where we compute a Riccati polynomial that may require an extension of the constant field is the imprimitive case (there may be an extension of degree at most 4, see Hendriks and van der Put, 1994, Ulmer, 1994), because this is the only case where semi-invariants and appendix A need to be used.\\ Choosing step [2.2] instead of [2.1] to handle the imprimitive case has several extra advantages. For example, in step 3 and 5, we need not recompute the invariants of degree 6 (note, however, that one can not safely perform step 3 before step 2). Also, if the dimension of the space of invariants of degree 6 is bigger than 2, then we know automatically that the group is imprimitive (this follows from the properties of the primitive subgroups of $SL_3(\C)$). Furthermore we do not need to compute semi-invariants this way. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% %%%%%%%% PROOFS FOR THE ALGO \subsection{Correctness of the algorithm} The fact that the successions of tests proposed in the algorithms yield the correct groups follow from the decomposition of the symmetrisations of the characters (Singer and Ulmer, 1993a) for all primitive subgroups of $SL_3$. To prove that the corresponding degrees of algebraic Riccati solutions are correct, we proceed by inspection of all imprimitive and finite primitive subgroups of $SL_3$. \subsubsection{Imprimitive groups} Assume that $G$ is irreducible. If there is a semi-invariant of degree 3, then the group is either imprimitive or $F_{36}^{SL_3}$ (Singer and Ulmer, 1993a, Table 2 and Proposition 3.6). In both cases there is a Liouvillian solution. If the group is $F_{36}^{SL_3}$, then there is no semi-invariant of degree $3$ corresponding to a character of order $2$ (i.e. whose square is an invariant). Thus, if there is a semi-invariant of degree $3$ corresponding to a character of order $2$ then the group must be imprimitive. An imprimitive group of degree $3$ is monomial, i.e. there exists a basis $\{y_1,y_2,y_3\}$ such that an element of $G$ has only one non zero entry in row and column. Since $G\subset SL(3,\C)$, we have $\forall g \in G$, $g(y_1y_2y_3) =\pm y_1y_2y_3$ (Singer and Ulmer, 1993a, Proposition 3.6). There are at least one and at most $4$ Riccati polynomials of degree $3$ in this case (Hendriks and van der Put, 1994, Ulmer, 1994). \subsubsection{$A_5$} \label{A5} \begin{lemma} If $G\simeq A_5$ then there is exactly one Riccati polynomial of degree 6 and exactly one of degree 15. The Riccati polynomial of degree 6 can be obtained by applying appendix A on the 2-dimensional space of invariants of degree 6.\\ The canonical image of the invariant of degree 15 is obtained the following way: compute the images $P_2$ and $P_6$ of the invariants of degrees 2 and 6. Let $P_{10}$ be their bordered Hessian, and $P_{15}$ be the Jacobian of these three ($P_{15}$ is unique and does not depend on the choice of $P_6$). \end{lemma} \begin{proof} That there exists a Riccati polynomial of degree $6$ is proven in Singer and Ulmer (1993b). Its uniqueness follows from the fact that there are $6$ conjugate non-Abelian subgroups of index $6$ having each one common eigenvector. So we turn to degree 15.\\ There are $5$ conjugate subgroups of order $4$ in $A_5$ which are all Abelian of exponent $2$. Using the matrix representation of $A_5$ given in Singer and Ulmer (1993b), we get that one such group, say $H$, is generated by the matrices $\{E_2 E_1 E_2 E_3 E_2 E_1, E_3 E_1 \}$ which have % \[ [\frac{9}{46}+\frac{1}{23}\alpha^3+ % \frac{3}{46}\alpha^2-\frac{27}{46}\alpha,1,-\frac{27}{46}\alpha+ % \frac{1}{23}\alpha^3+\frac{3}{46}\alpha^2+\frac{55}{46}]\] %%% MVH: I simplified this formula to the following: %%% $(1/2-\sqrt{5}/2, 1, 3/2 - \sqrt{5}/2)$ %%% but it turns out that it's just plain wrong. What's going on here??? $(-\zeta_5^{3}+\zeta_5+1,\zeta_5,1)^t$ as a common eigenvector, where $\zeta_5={\rm exp}(2\pi i/5)$. % where $\alpha^4+2\alpha^3-7\alpha^2- % 8\alpha+31=0$ and % \begin{eqnarray*} % \sqrt{5} & = & -\frac{2}{23}\alpha^3-\frac{3}{23}\alpha^2+ % \frac{27}{23}\alpha+\frac{14}{23} \\ % \xi = \sqrt[5]{1} & = & \frac{2}{23}\alpha^3+\frac{3}{23}\alpha^2- % \frac{4}{23}\alpha-\frac{14}{23} % \end{eqnarray*} % In order to find the corresponding semi-invariant that factors into linear forms, we look at a set {\small \[ {\cal S}=\{id, E_1^{-1},E_2^{-1},E_3^{-1},E_2^{-1}E_1^{-1}, E_1^{-1}E_2^{-1}, E_2^{-1}E_3^{-1}, E_1^{-1}E_2^{-1}E_1^{-1}, E_3^{-1}E_2^{-1}E_1^{-1}, \] \[ E_1^{-2}E_2^{-1}, E_2^{-1}E_1^{-1}E_2^{-1}, E_1^{-1}E_2^{-1}E_3^{-1}, E_1^{-2}E_2^{-1}E_1^{-1}, E_3^{-1}E_1^{-1}E_2^{-1}E_1^{-1}, E_1^{-1}E_3^{-1}E_2^{-1}E_1^{-1}\}\] } of left coset representatives of $H$ in $A_5$. The resulting polynomial % \[ \prod_{g \in {\cal S}} \left( g\left( \left(\frac{9}{46}+ % \frac{1}{23}\alpha^3+\frac{3}{46}\alpha^2- % \frac{27}{46}\alpha\right)y_1+ % y_2+\left(- % \frac{27}{46}\alpha+\frac{1}{23}\alpha^3+\frac{3}{46}\alpha^2+ % \frac{55}{46}\right)y_3\right)\right) \] \[ \prod_{g \in {\cal S}} g \left( ( -\zeta_5^{3}+\zeta_5+1 ) y_1 + \zeta_5 y_2+y_3\right) \] which by construction factors into linear forms over the complex numbers, is a semi-invariant and thus an invariant\footnote{This invariant does not correspond to the invariants given in Singer and Ulmer (1993b) where another basis of the solution space was chosen in order to express the invariants.} of the simple group $A_5$. The length of the orbit of the logarithmic derivative of the eigenvector, i.e.\ the degree of its minimal polynomial, divides $15=[A_5:H]$. \from Singer and Ulmer (1993b), we know that this degree must be $\ge 6$, so the degree must be $15$ and that the associated polynomial must be a Riccati polynomial of degree 15. Note that there is, up to multiple, a unique invariant of degree $15$ which thus must factor into linear forms.\\ The statement on the construction of the invariant of degree 15 from the invariants of degree 2 and 6 follows from the uniqueness and from a simple direct computation on classical invariants (Miller, Blichfeldt, and Dickson, 1938, paragraph 125 pp 253--255). \end{proof} \subsubsection{$G_{168}$} \label{G168} \begin{lemma} If $G\simeq G_{168}$, then there is a unique Riccati polynomial of degree 21.\\ Its canonical image $P_{21}$ is obtained the following way. Let $P_4$ be the image of the invariant of degree 4, let $P_6$ be its Hessian, and let $P_{14}$ be the bordered Hessian of $P_4$ and $P_6$; then $P_{21}$ is obtained from the Jacobian of $P_4,P_6,P_{14}$. \end{lemma} \begin{proof} \from Singer and Ulmer (1993b) we get that there exists a Riccati polynomial of degree 21. Since the group is simple, any semi-invariant must be an invariant. There is a unique trivial summand in the decomposition of the character of the 21-th symmetric power of the faithful irreducible unimodular 3-dimensional characters, we get that the semi-invariant must correspond to the, up to multiple, unique invariant of degree $21$ and thus factor into linear forms. The corresponding group $H$ and the coset representatives are given in Singer and Ulmer (1993b).\\ The statement on $P_{21}$ follows from the uniqueness and from direct computation on classical invariants (Miller, Blichfeldt, and Dickson, 1938, paragraph 125 pp 253--255). \end{proof} %\subsubsection{$H_{216}^{SL_3}$} \subsubsection{$H_{216}^{SL_3}$ and $H_{72}^{SL_3}$} \label{H216} \label{H72} \from Singer and Ulmer (1993b), we get that there exists a Riccati polynomial of degree 9. Since there is no non-trivial character of degree $1$ and a unique trivial summand in the decomposition of the character of the 9-th symmetric power of the faithful irreducible unimodular 3-dimensional characters, we get that the semi-invariant must correspond to the, up to multiple, unique invariant of degree $9$ which thus must factor into linear forms. The corresponding group $H$ and the coset representatives are given in Singer and Ulmer (1993b). %\subsubsection{$H_{72}^{SL_3}$} %\label{H72} % %\from Singer and Ulmer (1993b), we get that there exists %Riccati polynomial of degree 9. %Since there is no % non-trivial character of degree $1$ and a unique trivial summand in %the %decomposition of the character of the 9-th symmetric power of the %faithful irreducible unimodular 3-dimensional characters, we get that %the semi-invariant %must correspond to the, up to multiple, unique invariant of degree $9$ % which thus must factor into linear forms. The corresponding group %$H$ %and the coset representatives are given in Singer and Ulmer (1993b). % \subsubsection{$G_{168}\times C_{3}$} \label{G168xC3} The, up to multiple, unique invariant of degree $21$ of $G_{168}$ factors into linear forms (see section~\ref{G168}). Since its order is divisible by $3$ it is also an invariant of $C_3$ and thus a, up to multiple, unique invariant of $G_{168}\times C_3$ that factors into linear forms. Since $21$ is the minimal degree of a Riccati polynomial in this case (Singer and Ulmer, 1993b), it must correspond to a Riccati polynomial. This Riccati polynomial can be constructed from the semi-invariant of degree $4$ (whose cube is rational) as in section \ref{G168}. \subsubsection{$A_{6}^{SL_3}$} \label{A6} \begin{lemma} If $G\simeq A_{6}^{SL_3}$, then there is exactly one Riccati polynomial of degree 45, and it is obtained from an invariant, which can be computed in the following way: let $P_6$ be the invariant of degree 6, let $P_{12}$ be the Hessian of $P_6$, and let $P_{30}$ be the bordered Hessian of $P_{6}$ and $P_{12}$. Then $P_{45}$ is obtained from the Jacobian of $P_6,P_{12},P_{30}$. \end{lemma} We note that there is also a Riccati polynomial of degree 36 (Singer and Ulmer, 1993b) but we know of no simple formula to obtain it; furthermore, the space of invariants of degree 36 for $A_6^{SL_3}$ has dimension $5$ so selecting the completely factorable invariant would be a very hard task. \begin{proof} There are $3$ types of non conjugate subgroups of order $24$ in $A_6^{SL_3}$. Only one type consisting of $45$ conjugate non Abelian subgroups of order $24$ is $1$-reducible (the $24$ elements have a common eigenvector). Using the matrix representation of $A_6^{SL_3}$ given in Singer and Ulmer (1993b), we get that one such group, say $H$, is generated by the matrices $\{E_4 E_1 E_2 E_3 E_1 E_2 E_1^{-1} E_4$, $(E_4 E_1^{-1})^2$, $E_3 E_2 E_4 E_3, E_3 E_4 E_3 \}$ which have % \[ [-\frac{24}{23}-\frac{3}{46}\alpha^3+ % \frac{7}{46}\alpha^2-\frac{29}{46}\alpha,\frac{5}{23}\alpha- % \frac{5}{46}\alpha^3+\frac{2}{23}\alpha^2-\frac{11}{46},1]\] as a %%% MVH: I DO NOT TRUST THE CORRECTNESS OF THIS VECTOR SO I DELETED IT. %%% PLEASE VERIFY VERY CAREFULLY BEFORE REENTERING THIS IN OUR PAPER. % a common eigenvector. % % (here we use the same notation as for $A_5$). % NOTE::: $\alpha=\sqrt{5}+\sqrt[3]{1}$. In order to find the corresponding semi-invariant that factors into linear forms, we look at a set ${\cal S}$ of left coset representatives of $H$ in $A_6^{SL_3}$ (containing $45$ elements). Since the group is perfect and has no non-trivial character of degree $1$, the semi-invariant must be an invariant. There is, up to multiple, only one invariant of degree $45$ for this group which thus must factor into linear forms by the above. The length of the orbit of the logarithmic derivative of the eigenvector divides $45=[A_6^{SL_3}:H]$. \from Singer and Ulmer (1993b), we get that this degree must be $\ge 36$ and thus that the degree must be $45$ and that the associated polynomial must be a Riccati polynomial of degree 45. The statement on $P_{45}$ follows from the uniqueness and from direct computation on classical invariants (Miller, Blichfeldt, and Dickson, 1938, paragraph 125 pp 253--255). \end{proof} \subsubsection{$F_{36}^{SL_3}$} \label{F36} There are $9$ conjugate subgroups of order $12$ in $F_{36}^{SL_3}$ which are all Abelian. Using the matrix representation of $F_{36}^{SL_3}$ given in Singer and Ulmer, 1993b, we get that one such group, say $H$, is generated by the matrices $\{ V, U^3\}$ which have $(0,-1,1)^t$ (see Singer and Ulmer, 1993b for the notations) as a common eigenvector. Note that $U^3$ is $\omega$ times the identity where $\omega$ is a third root of unity, and that $U^3$ is in $F_{36}^{SL_3}$. In order to find the corresponding semi-invariant that factors into linear forms, we look at a set ${\cal S}=\{id$, $S$, $T$, $S^{-1}$, $T^{-1}$, $T^{-1}S^{-1}$, $TS^{-1}$, $T^{-1}S$, $TS\}$ of left coset representatives of $H$ in $F_{36}^{SL_3}$. The resulting polynomial \[ \prod_{g \in {\cal S}} \left( g(-y_2+y_3) \right) = -y_3^3y_2^6+y_1^3y_2^6-y_1^6y_2^3+y_3^6y_2^3- y_3^6y_1^3+y_1^6y_3^3 \] which by construction factors into linear forms over the complex numbers, is in fact an invariant\footnote{Note that if the result would be a semi invariant, one could find the corresponding one dimensional character using this construction.} of $F_{36}^{SL_3}$ (check using the generators). The length of the orbit of the logarithmic derivative of the eigenvector, i.e.\ the degree of its minimal polynomial, divides $9=[F_{36}^{SL_3}:H]$. \from Singer and Ulmer (1993b) we know that this degree must be $\ge 6$, so the degree must be $9$ and the associated minimal polynomial must be an irreducible Riccati polynomial of degree $9$.\\ \subsubsection{$A_5^{SL_3}\times C_3$} \label{A5xC3} The, up to multiple, unique invariant of degree $15$ of $A_5$ which, by section \ref{A5}, factors into linear forms is, since its order is divisible by $3$, also an invariant of $C_3$ and thus an, up to multiple, unique invariant of $A_5\times C_3$ which factors into linear forms. Since $6$ is the minimal degree of a Riccati polynomial in this case (Singer and Ulmer, 1993b), it must correspond to % the minimal polynomial of such a Riccati polynomial. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% \subsection{Example} \begin{eqnarray*} % %L=\partial^3 + %\frac{21\left(x^2-x+1\right)}{25\,x^2\left(x-1\right)^2}\partial %- \frac{21\left(5\,x-2-3\,x^2+2\,x^3\right)}{50\,x^3\left(x-1\right)^3} % L=\partial^3 + \frac{21\left(x^2-x+1\right)}{25\,x^2\,(x-1)^2}\partial - \frac{21\,(2\,x-1)\left(x^2-x+2\right)}{50\,x^3\,(x-1)^3} \end{eqnarray*} The operator is irreducible. % (checked using the methods of {Hoe97}). There is a two-dimensional space of invariants of degree 6. None of them is a square so we proceed to step 3. There is one invariant of degree 2, so we know that $\gz\simeq A_5^{SL_3}$. The invariants of degree 6 (variables ${\overline y}_{i}$, parameters $a_1,a_2$) are: \begin{eqnarray*} && (2560\,a_{1}-30\,a_2)\,{{\overline y}_{1}}^3\,{{\overline y}_{2}} ^3 + 6\,{\overline y}_{3}\,{{\overline y}_{1}}^5\,a_{1} \\ &&\quad\mbox{} + (-1024\,a_{1 }+30\,a_2)\,{{\overline y}_{3}}^6 - 393216\,{\overline y}_{3}\,{{\overline y}_{2}}^5\,a_{1} \\ &&\quad\mbox{} + (15360\,a_{1}-90\,a_2)\,{\overline y}_{1}\,{\overline y}_{2}\,{\overline y}_{3}^4 + 90\,{{\overline y}_{3}}^2\,{{\overline y}_{2}}^2\,{{\overline y}_{1}}^2\,a_2 \end{eqnarray*} Using a complete factorization approach, we find that for $256 a_1=3a_2$ we have the following factor (up to conjugation): $$ {\overline y}_{1} - \alpha^2{\overline y}_{2} + \alpha {\overline y}_{3},\, \qquad \hbox{\rm where } \; \alpha^5-256=0 $$ and the remaining factor is simply ${\overline y}_{3}$. The coefficients of the corresponding canonical image are: \begin{eqnarray*} && \Bigl[\, -4608\,x^4\,(x-1)^4,\, -3072\,(-1+2\,x) \,x^3\,(x-1)^3,\, \\ &&\quad\mbox{} -1536/5\,x^2\left(7\,x^2-7\,x-3 \right)(x-1)^2,\, \\ &&\quad\mbox{} -\frac{1536}{25}\,x^2\left(133\,x^ 2-133\,x+33\right)(x-1)^2,\, \\ &&\quad\mbox{} -\frac{2304}{125}\,x\,( x-1)\,(-1+2\,x)\left(77\,x^2-77\,x-34\right),\, -\frac{110592}{625} \\ &&\quad\mbox{} + \frac{1204224}{625}\,x^3 - \frac{602112}{625}\,x^ 4 - \frac{562176}{625}\,x - \frac{39936}{625}\,x^2,\, \\ &&\quad\mbox{} -\frac{13824}{125}\,x\,(x-1)\,(7\,x-4)\,(- 1+2\,x)\,( 7\,x-3),\, \frac{262656}{625}\\ &&\quad\mbox{} + \frac{4666368}{625} \,x^3 - \frac{2333184}{625}\,x^4 - \frac{479232}{625}\,x - \frac{ 1853952}{625}\,x^2,\, \\ &&\quad\mbox{} -\frac{3072\,(- 1+2\,x)\left( 637\,x^4-1274\,x^3+25\,x^2+612\,x+126\right)}{3125\,x\,(x-1)},\, \ldots %\\ &&\quad\mbox{} -\frac{4608\left(14\,x^2-11\,x- %6\right)\left(14\,x^2 %-17\,x-3\right)\left(7\,x^2-7\,x-6\right)}{15625\,x^2\,(x-1)^2},\, %\\ &&\quad\mbox{} -\frac{539136}{625} + %\frac{17912832}{625}\,x^3 - %\frac{8956416}{625}\,x^4 + \frac{4396032}{625}\,x - %\frac{13352448}{ %625}\,x^2,\, \\ &&\quad\mbox{} -\frac{768\,(- %1+2\,x)\left(9947\,x^4- %19894\,x^3+7760\,x^2+2187\,x-1134\right)}{3125\,x\,(x-1)},\, %\\ &&\quad\mbox{} -\frac{256\left(98784\,x^6- %296352\,x^5+223271\,x^4+ %47378\,x^3-76429\,x^2+3348\,x+5184\right)}{15625\,x^2\,(x-1)^2},\, %\\ &&\quad\mbox{} -\frac{1536\,(-1+2\,x)\left(13034\,x^6- %39102\,x^5+ %18207\,x^4+28756\,x^3-11337\,x^2-9558\,x- %1188\right)}{78125\,x^3\,(x-1 %)^3},\, \\ &&\quad\mbox{} -\frac{6144\left(12330\,x^2-10869\,x^3- %42659 %\,x^4+30821\,x^5+34545\,x^6+324+4644\,x+9604\,x^8- %38416\,x^7\right)}{ %390625\,x^4\,(x-1)^4},\, \\ &&\quad\mbox{} -\frac{3072\,(-1+2\,x) %\left(9604\,x^4-19208\,x^3+14275\,x^2- %4671\,x+567\right)}{3125\,x\,(x- %1)},\, \\ &&\quad\mbox{} -\frac{384\left(-41089\,x^2-267202\,x^3+ %781871\,x^4-7452+45036\,x+259308\,x^6- %777924\,x^5\right)}{15625\,x^2\, %(x-1)^2},\, \\ &&\quad\mbox{} -\frac{3072\,(- %1+2\,x)\left(26411\,x^6- %79233\,x^5+58863\,x^4+14329\,x^3- %21018\,x^2+648\,x+1458\right)}{78125 %\,x^3\,(x-1)^3},\, \\ &&\quad\mbox{} -\frac{384\left(304617\,x^2+ %438117\,x^3-1884124\,x^4+169477\,x^5+2991177\,x^6-16848- %60048\,x+ %653072\,x^8-2612288\,x^7\right)}{390625\,x^4\,(x-1)^4},\, %\\ &&\quad\mbox{} -\frac{4608\,(-1+2\,x)\left(38416\,x^8- %153664\,x^7+ %131957\,x^6+141953\,x^5-181949\,x^4- %51965\,x^3+53652\,x^2+21600\,x+ %1728\right)}{1953125\,x^5\,(x-1)^5},\, \\ &&\quad\mbox{} %-\frac{384 %\left(-1932417\,x^2-365292\,x^3+8406464\,x^4+1808922\,x^5- %16838536\,x^ %6+7462308\,x^7+6201783\,x^8-15552-440640\,x- %5378240\,x^9+1075648\,x^{ %10}\right)}{9765625\,x^6\,(x-1)^6},\, \\ &&\quad\mbox{} %-\frac{1152 %\left(16807\,x^4-33614\,x^3+24907\,x^2-8100\,x+972\right)(- %1+2\,x)^2}{ %3125\,x^2\,(x-1)^2},\, \\ &&\quad\mbox{} -\frac{768\,(-1+2\,x)\left( %16807\,x^6-50421\,x^5+50421\,x^4-16807\,x^3-2997\,x^2+2997\,x- %486 %\right)}{3125\,x^3\,(x-1)^3},\, \\ &&\quad\mbox{} -\frac{384\left(- %87015\,x^2+531285\,x^3-475156\,x^4- %1254491\,x^5+2928009\,x^6+7776- %29160\,x+537824\,x^8-2151296\,x^7\right)}{78125\,x^4\,(x-1)^4},\, %\\ &&\quad\mbox{} -\frac{4608\,(-1+2\,x)\left(33614\,x^8- %134456\,x^7+ %151263\,x^6+16807\,x^5-103420\,x^4+21963\,x^3+17307\,x^2- %3078\,x-972 %\right)}{390625\,x^5\,(x-1)^5},\, \\ &&\quad\mbox{} %-\frac{384\left(- %234783\,x^2-1392660\,x^3+2054168\,x^4+4931910\,x^5- %9352552\,x^6+153468 %\,x^7+8028993\,x^8+15552+114048\,x- %5378240\,x^9+1075648\,x^{10}\right) %}{1953125\,x^6\,(x-1)^6},\, \\ &&\quad\mbox{} -\frac{768\,(-1+2\,x) %\left(268912\,x^{10}-1344560\,x^9+1294139\,x^8+2890804\,x^7- %5369317\,x %^6+342985\,x^5+2771632\,x^4-53181\,x^3-642006\,x^2-159408\,x- %7776 %\right)}{9765625\,x^7\,(x-1)^7},\, \\ &&\quad\mbox{} %\frac{1152\left( %588245\,x^8-2352980\,x^7+2470629\,x^6+823543\,x^5- %1843807\,x^4-430101 %\,x^3+501228\,x^2+243243\,x+31104\right)}{9765625\,x^7\,(x-1)^7} \,\Bigr] \end{eqnarray*} \from this, we read the coefficients of the minimum polynomial of an algebraic solution of the corresponding Riccati equation using theorem~\ref{ricpoly}. We use rows that correspond to the monomials $X_1^lX_2^{6-l}$, $l=0,1,\ldots,6$. The way we numbered the monomials $X_1^{l_1} X_2^{l_2} X_3^{6-l_1-l_2}$, this corresponds to rows 1, 2, 4, 7, 11, 16, 22. We obtain: \begin{eqnarray*} && X^6 - 4\,\frac{(-1+2\,x)\,X^5}{x\,(x-1)} + \frac{ \left(133\,x^2-133\,x+33\right)X^4}{5\,x^2\,(x-1)^2} \\ &&\quad\mbox{} - \frac{12\,(7\,x-4)\,(-1+2\,x)\,(7\,x-3)\,X^3}{25\,x^3\,(x-1)^3} \\ &&\quad\mbox{} + \frac{\left(351-11662\,x^3+5831\,x^4- 2862\,x+8693 \,x^2\right)X^2}{125\,x^4\,(x-1)^4} \\ &&\quad\mbox{} - \frac{4\,(- 1+2 \,x)\left(9604\,x^4-19208\,x^3+14275\,x^2- 4671\,x+567\right)X}{3125\,x ^5\,(x-1)^5} \\ &&\quad\mbox{} + \frac{\left(16807\,x^4-33614\,x^3+ 24907\,x^2-8100\,x+972\right)(-1+2\,x)^2}{12500\,x^6\,(x-1)^6} \end{eqnarray*} Alternatively, we can avoid the factoring by using sections \ref{constructors} and section \ref{A5} to construct directly the (unique) Riccati polynomial of degree 15 via bordered Hessian and Jacobian applied on the invariants of degree 2 and 6. The result is the following irreducible Riccati polynomial: \begin{eqnarray*} && X^{15} - 6\,\frac{\left(7\,x^4-14\,x^3-4\,x^2+11 \,x-3\right)}{x\,(x-1)\,(-2+x)\,(-1+2\,x)\,(x+1)} X^{14} \\ &&\quad\mbox{} + \frac{21\left(49\,x^4-98\,x^3-20\,x^2+69\,x-18 \right)}{5\,x^2\,(x+1)\,(-2+x)\,(x-1)^2} X^{13} \\ &&\quad\mbox{} - \frac{13\left(9604\,x^6-28812\,x^5+19119\,x^4+9782\,x^3- 15741\,x^2+ 6048\,x-756\right)}{50\,x^3\,(-2+x)\,(-1+2\,x)\,(x+1)\,(x-1)^3} X^{12} \\ &&\quad\mbox{} + \frac{13\left(50421\,x^6- 151263\,x^5+107203\,x^4+ 37699\,x^3-71843\,x^2+27783\,x-3402\right)}{125\,x^4\,(x+1)\,(-2 +x)\,(x-1)^4} X^{11} +\dots \\ &&\quad\mbox{} %+ \dots % +\frac{3\left( %678223072849\,x^{16}- %5425784582792\,x^{15}+19777181729879\,x^{14}- %43489041910293\,x^{13}+64253353953964\,x^{12}- %67035777407011\,x^{11}+ %50252656129935\,x^{10}- %26684823831344\,x^9+9282826373822\,x^8- %1408708944115\,x^7-488923115409\,x^6+400636669716\,x^5- %136950272775\,x %^4+28601190153\,x^3-3754440396\,x^2+285383817\,x- %9565938\right)}{ %1220703125\,(x+1)\,(-2+x)\,(x-1)^{14}\,x^{14}}X %\\ &&\quad\mbox{} - %\frac{(-1+2\,x)\left(4747561509943\,x^{16}- %37980492079544\,x^{15}+ %138611169634798\,x^{14}- %305619576051566\,x^{13}+453664070594161\,x^{12 %}-477042324513860\,x^{11}+362502527461921\,x^{10}- %197549252349218\,x^9 %+73059335474869\,x^8-14480269840548\,x^7- %1404208957023\,x^6+ %2134416582810\,x^5-792411765138\,x^4+170344240272\,x^3- %22611810717\,x^ %2+1721868840\,x-57395628\right)}{61035156250\,(x+1)\,(- %2+x)\,(x-1)^{15 %}\,x^{15}} \end{eqnarray*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% \section*{Appendix: Deciding when a homogeneous polynomials admits linear factors} If $A$ is a ring, we denote by $A[X_1,\ldots,X_n]_m$ the space of homogeneous polynomials of total degree $m$ in the variables $X_i$. Let $P\in \C[t_1,\ldots,t_s][X_1,\ldots,X_n]_m$ be homogeneous of degree $m$ in the variables $X_i$. In this appendix, we show how to compute potential values of the parameters $t_i$ such that $P$ (then viewed as a homogeneous polynomial in $\C[X_1,\ldots,X_n]$) admits a linear factor. The subproblem relevant in this paper is the following: Let $P=\sum t_i P_i$ where $P_i\in \C[X_1,\ldots,X_n]_m$. Decide for which values of the $t_i$ the polynomial $P$ admits a linear factor. This problem is part of the general problem of absolute factorization of polynomials. For the latter, the reader may consult Ragot (1997) where several methods and abundant references are given. %This problem takes part of a more general one, %which is {\em absolute factorization} %of polynomials. Given a polynomial $P$ %with coefficients in a field $k\,$, one %wishes to compute the %decomposition of $P$ in irreducible factors over an algebraic %closure of $k\,$. % %Two implemented algorithms are now available. %The first one is due to Barry Trager and Carlo Traverso and %constitutes the %procedure {\sc AFactor} of Maple. The second is a Maple %implementation by J-F %Ragot of a method of D. Duval, using a package of M. van Hoeij. See %{Rag97} for references about these algorithms and other works %on absolute %factorization. % %These methods, and particularly both algorithms mentioned above, %are not really %suitable to our problem. \subsection*{A1: Brill's equations} Completely factorable polynomials of degree $m$ form a Zariski closed set. The defining equations, the Brill equations, are homogeneous equations of degree $m$ that can be computed (Brill, 1898, Gelfan'd, Kapranov, and Zelevinski, 1994). This can be used (Singer and Ulmer, 1997) to select the completely factorable semi-invariants. \subsection*{A2: Complete factorization of non-parametrized polynomials} If there are no parameters in $P$, then many methods exist (Hohl, 1995, Kobayashi, Fujise, and Furukawa, 1988, and Ragot, 1997, for another method and references). We outline below a method that seems, from our experience, to be the most interesting. The tools and results are similar to the ones that are used in the three papers mentioned above. Let $C$ be a perfect field (usually $C$ is $\q$ or a finite extension of $\q$). \begin{definition}\em Let $P$ be a polynomial of $C[X_1, \dots, X_n]_m$ of degree $d>0$ in $X_1\,$. A $n-1$-tuple $(a_2,\dots,a_{n})$ of $C^{n-1}$ is called a {\em non critical value} for $P$ in $X_1$ if the polynomial $P(T,a_2,\dots,a_n)$ is square-free and of degree $d\,$. This implies in particular that all roots of $P(T,a_2,\dots,a_n)$ are simple. \end{definition} {\it Remark}~: The existence of such a non-critical value for $P$ implies that $P$ is square-free. \from now on, let $\underline{Z}$ denote the multi-variable $X_3, \dots, X_n\,$. % \begin{lemma}\label{le:cons-deg-trans} Let $P$ be a homogeneous square-free polynomial of $C[X_1, X_2, \underline{Z}]_m\,$, of degree $d>0$ in $X_1\,$. Assume that $P$ is of degree $m$ in $X_2\,$, and let $(1, 0, \dots, 0)$ be a non critical value for $P$ in $X_1\,$. Denote by $p(T)$ the polynomial $P(T,1,\underline{0})$ and let $\alpha$ be a root of $p(T)\,$. Then $P(X_1+\alpha\,X_2, X_2, \underline{Z})$ is of degree $m-1$ in $X_2\,$. \end{lemma} \begin{proof}{}Let $\bar{P}(X_1, X_2)=P(X_1, X_2,\underline{0})\,$. It is a homogeneous polynomial of $C[X_1, X_2]\,$. Write $$\bar{P}=X_2^{m-d} \sum_{i=0}^d b_i\,X_1^i\,X_2^{d-i}\:;$$ It factors in $\overline{C}[X_1, X_2]$ as $$b\,X_2^{m-d} \, \prod_{i=1}^d (X_1-\alpha_i\,X_2)\:$$ where the $\alpha_i\,$, with $i$ from 1 to $d$, are the roots of $p(T)\,$. Hence $$\bar{P}(X_1+\alpha\,X_2,X_2)=b\,X_2^{m-d} \, \prod_{i=1}^d \left(X_1+(\alpha-\alpha_i)\,X_2\right)\:.$$ The roots of $p(T)$ are simple, so $\alpha-\alpha_i=0$ for one unique $i\,$, which proves that $\bar{P}(X_1+\alpha\,X_2,X_2)$ is of degree $m-1$ in $X_2\,$. It is also true for $P(X_1+\alpha\,X_2, X_2,\underline{Z})\,$, since $\bar{P}(X_1+\alpha\,X_2,X_2)$ is its evaluation in $\underline{Z}=\underline{0}\,$. \end{proof} \begin{proposition}\label{factor} Let notations and assumptions be as above, and let $\tilde{P}_T(X_1, X_2,\underline{Z})=P(X_1+T\, X_2,X_2,\underline{Z})$; then $P$ admits a linear factor in $\overline{C}[X_1, X_2,\underline{Z}]$ if and only if there exists a root $\alpha$ of $p$ such that $\displaystyle \frac{\partial^{m-1}\tilde{P}_{\alpha}}{\partial\, X_2^{m-1}}$ is a linear factor of $\tilde{P}_{\alpha}$ in $C(\alpha)[X_1,\underline{Z}]\,$. \end{proposition} % \begin{proof}{} Let $L=X_1+a\,X_2+\sum_{i=3}^n c_i\,X_i$ be a linear factor of $P$ and let $C'$ be the field of its coefficients. Denote by $r$ the degree of $C'$ over $C\,$. The polynomial $L$ is absolutely irreducible and by theorem 1.2.2 of Ragot (1997), $F=Norm_{C'/C}(L)$ is an irreducible polynomial of $C[X_1,X_2,\underline{Z}]\,$. It is clearly of degree $r\,$, and it is a factor of $P\,$. The polynomial $F(T,1,0,\dots,0)$ is a factor of $p(T)\,$, it is hence square-free. On the other hand, $F(T,1,0,\dots,0)=Norm_{C'/C}(L(T,1,0,\dots,0))=Norm_{C'/C}(T+a)\,$, and by lemma 1.2.1 of Ragot (1997) (or theorem 2.1 of Trager (1976) extended to perfect fields), $Norm_{C'/C}(T+a)$ is a power of an irreducible polynomial of $C[T]\,$. This implies that $F(T,1,0,\dots,0)$ is an irreducible polynomial of degree $r\,$. Let $\alpha=-a\,$; then $\alpha$ is of degree $r$ and $C'=C(\alpha)\,$. Hence, $$L=X_1 - \alpha\,X_2 + \sum_{i=3}^n c_i(\alpha)\,X_i$$ where the $c_i$'s are polynomials with coefficients in $C\,$. Let $P=L\cdot Q\,$, then $\tilde{P}_{\alpha} = \tilde{L}_{\alpha}\cdot\tilde{Q}_{\alpha} = \left(X_1 + \sum_{i=3}^n c_i(\alpha)\,X_i\right)\cdot\tilde{Q}_{\alpha}\,$. Now $\tilde{P}_{\alpha}\,$, and then $\tilde{Q}_{\alpha}\,$, are of degree $m-1$ in $X_2$ (lemma~\ref{le:cons-deg-trans}) and so $$\displaystyle \frac{\partial^{m-1}\tilde{P}_{\alpha}}{\partial\, X_2^{m-1}} =c(\alpha)\cdot \left(X_1 + \sum_{i=3}^n c_i(\alpha)\,X_i\right)\:.$$ Conversely, if $X_1 + \sum_{i=3}^n c_i(\alpha)\,X_i$ is a factor of $\tilde{P}_{\alpha}\,$ then $X_1 - \alpha\,X_2 + \sum_{i=3}^n c_i(\alpha)\,X_i$ is a factor of $P\,$. \end{proof} This suggests the following fast algorithm to check whether a given square-free polynomial has linear factors (and compute them as a byproduct). After maybe a linear change of variables\footnote{The condition on a change of variables to be such that $P$ satisfies the hypothesis of proposition \ref{factor} are easily seen to form a Zariski closed set so ``almost any'' change of variables will do.} %see \cite{Lan92} corollary 1.7 and 1.8 section 4.1.} we may assume that $P$ satisfies the hypotheses of proposition \ref{factor}. Form $P_\alpha$ and $L_\alpha$ as in proposition \ref{factor}. Then the corresponding $L$ is a factor of $P$ if and only if $L_\alpha$ divides all coefficients of powers of $X_2$ in $P_\alpha$; the latter conditions are easily stated via resultants or even Euclidean divisions and, together with the relation $p(\alpha)=0$, they yield a system of polynomial equations for $\alpha$: our polynomial $P$ has a linear factor if and only if the latter system is consistent. \subsection*{A3: Complete factorization of parametrized polynomials} The above method can be adapted to polynomials depending on parameters, although the conditions that $P$ be square-free and that $(1,0,\ldots,0)$ be non-critical may induce some nuisance (non-linear branchings); if one avoids the branching, then the algorithm is incomplete but yields an interesting heuristic. The following straightforward method can also be used, without any restrictions on the parameters. Write $L=X_1+\sum_{i=2}^n c_i X_i$. We want conditions for $L$ to be a factor of $P$. Let $R:={\rm resultant}(P,L,X_1)=P(-\sum_{i=2}^n c_i X_i)$ (note that $R=P(-\sum_{i=2}^n c_n X^n,X_2,\ldots,X_n)$). Of course, there is a linear factor if and only if $R$ is the zero polynomial. The coefficients of $R$ depend on the $t_i$ and the $c_i$; equating all these to zero yields a polynomial system that we solve with any available method (see e.g Cox, Little, and O'Shea (1992) for an introduction to these).\\ In our specific problem, the system is linear in the $t_i$ and non-linear in the $c_i$ so we can also apply the methods of Sit (1992) for solving it. Surprisingly, this simple method is quite satisfactory in practice and %seems to can be faster than (our implementation of) the Brill equations. We may interpret this experimental fact as follows. Using the Brill equations is like solving the system that we would obtain by first eliminating the $c_i$; however, here, it may be that another solving strategy is better (e.g because of the linearity in the $t_i$) so it could compensate for the fact of adding the extra variables $c_i$. \subsection*{A4: Deciding when a polynomial is an $k$-th power} % of another polynomial} \label{A4} Let $P$ be of the form $P=\sum t_i P_i$ where the $P_i \in \C[X_1,\ldots,X_n]$ are homogeneous of degree $m$. After a linear transformation we may assume that the degree of $P$ in $X_1$ equals $m$. %, which the degree of $P$ in $X_1,\ldots,X_n$. \\ Assume that $P=Q^k$. Let $L$ be the coefficient of $X_1^m$. We need to distinguish two cases: After substituting values in $\C$ for the $t_i$ either $L$ vanishes or $L$ remains non-zero. First we compute under the assumption that $L$ vanishes. So we have a linear relation $L=0$ between the parameters $t_i$ ($P$ is linear in the $t_i$). We use this relation to eliminate one of the $t_i$ and then apply recursion. Afterwards we may assume that $L$ does not vanish. Because $P$ is homogeneous in the $t_i$ we may then assume that $L=1$. We use this relation to eliminate one of the $t_i$. Then $P$ is a monic polynomial in $X_1$ with coefficients in $\C[t_1,\ldots,t_s,X_2,\ldots,X_n]$, and the degree of $Q$ in $X_1$ is $d=m/k$. Write $Q=\sum_{i=0}^d q_i X_1^i$ where $q_d=1$. Taking the coefficient of $X_1^{m-1}$ on both sides of the equation $P=Q^k$ (the coefficient on the right-hand side is $kq_{d-1}$) we find $q_{d-1} \in \C[t_1,\ldots,t_s,X_2,\ldots,X_n]$. Repeating this for the next coefficients $X_1^{m-2},X_1^{m- 3},\ldots,X_1^{m-d}$ we determine $q_{d-2},q_{d-3},\ldots,q_0 \in %C[t_1,\ldots,t_s,q_d,X_2,\ldots,X_n]$. \C[t_1,\ldots,t_s,X_2,\ldots,X_n]$. %%JAW: we have assumed that q_d=1 Then we can compute $P-Q^k$ and equate all coefficients with respect to $X_1,\ldots,X_n$ to $0$. This gives a set of polynomial equations in the parameters $t_i$. Solving it gives the values of $t_i$ for which $P$ is a $k$-th power. %%%%%%%%%%%%%%%%%%%%%%% References \begin{thebibliography}{99} \item %\bibitem{barkatou} Barkatou, M.A. (1998). { On rational solutions of systems of linear differential equations}, {\em This volume}. \item %\bibitem{pflubar} Barkatou, M. A., Pfl\"ugel, E. (1998) An Algorithm Computing the Regular Formal Solutions of a System of Linear Differential Equations, {\em This volume} \item %\bibitem{Bri98} Brill, A. (1998) { \"Uber die Zerf\"allung einer Tern\"arform in Linearfactoren}, {\em Math. Ann. {\bf 50}, p. 157-182.} \item %\bibitem{CLO92} Cox, D., Little, J., O'Shea, D. (1992). {\em Ideals, varieties, and Algorithms} Undergraduate Texts in Math, Springer % \item %\bibitem{DLR92} Duval A. \& Loday-Richaud M. (1992) % {\em Kovacic's algorithm and its % application to some families of special functions} % Appl.\ Alg.\ in Eng.\ Comm.\ % and Comp.\ Journal {\bf 3}, 1992. \item %\bibitem{Fak97} Fakler, W. (1997). { On second order homogeneous linear differential equations with Liouvillian solutions}. {\em Theoretical Computer Science {\bf 187} (1-2):27-48.} \item %\bibitem{GKZ94} Gelfan'd, I.M, Kapranov, M.M, Zelevinski, A.V (1994). {\em Discriminants, Resultants, and Multidimensional Determinants} Birkha\"user. % \item %\bibitem{GUl97} Geiselmann W. \& Ulmer F (1997). % {\em Constructing a third order differential equation}, % proceedings of the "4-th Rhine Workshop on % Computer Algebra", to appear in: Theoretical Computer Science. \item %\bibitem[HvP94]{VPH94} Hendriks, P., van der Put, M. (1995). { Galois action on solutions of a differential equation}, {\em J. Symb. Comp. {\bf 19}, pp. 559-576}. \item %\bibitem{Hes98} Hessinger, S. (1998). {\em Galois groups of fourth order linear differential equations} PhD dissertation, North Carolina State University. \item %\bibitem{Hoe97} Hoeij, M. van (1997). {Factorization of Differential Operators with Rational Functions Coefficients}, {\em J. Symb. Comp. {\bf 24}, 1-30}. \item %\bibitem[HWe97]{hwmega} Hoeij, M. van, Weil, J.-A. (1997). { An algorithm for computing invariants of differential Galois groups}, {\em J. Pure and Applied Alg., {\bf 117 \& 118}, 353-379}. \item %\bibitem{Hoh95} Hohl, J.-C. (1995). Massively parallel search for linear factors in polynomials with many variables, {\em ICM preprint} . \item %\bibitem{KFF88} Kobayashi, H., Fujise, T., Furukawa, A. (1988). {Solving systems of algebraic equations by a general elimination method}, {\em J. Symb. Comp, Vol {\bf 5}, 303-320}. \item %\bibitem{Kov86} Kovacic, J. (1986). { An algorithm for solving second order linear homogeneous differential equations} {\em J. Symb. Comp {\bf 2} 3-43}. \item %\bibitem{Lan92} Lang, S. (1992). {\em Algebra} Third edition, Addison-Wesley. \item %\bibitem{Mag94} Magid, A. (1994). {\em Lectures on Differential Galois Theory}, {\it University Lecture Series} of the American Mathematical Society. \item %\bibitem{MBD38} Miller, G.A., Blichfeldt, H.F., Dickson L.E. (1938). {\em Theory and Applications of Finite Groups.} New York: G. G. Stechert and Co. \item %\bibitem{pfluegel} Pfl\"ugel, E. (1997). {An Algorithm for Computing Exponential Solutions of First Order Linear Differential Systems}, {\em ISSAC'97 Proceedings, ACM Press}. % \item %\bibitem{Put95} % Put, M. van der (1995) % {\em Singular complex differential equations: an introduction} % Nieuw Achief voor Wiskunde, $4^{\hbox{\rm de}}$ serie {\bf 13} No. %3 (1995) pp% . 451-470. \item %\bibitem{Put97} Put, M. van der (1998) Galois theory of differential equations, Algebraic groups and Lie algebras, {\em This volume} \item Put, M. van der, Ulmer, F. (1998) Differential equations and finite groups, {\em MSRI Preprint \#1998-058 .} \item %\bibitem{Rag97} Ragot, J.-~F. (1997). {\em Sur la factorisation absolue des polyn\^omes}, PhD dissertation, Universit\'e de Limoges. \item %\bibitem{Sin81} Singer, M.~F. (1981). {Liouvillian Solutions of $n^{th}$ Order Linear Differential Equations} {\em Am. J. Math. {\bf 103}, 661--682}. \item %\bibitem{Sin95} Singer, M.~F. (1995). {Testing reducibility of linear differential operators: a group theoretic perspective}, {\em J.\ of Appl.\ Alg.\ in Eng.\ Comm.\ and Comp.\, {\bf 7}, 77-104}. \item %\bibitem{Sin97} Singer, M.~F. (1997). {Direct and inverse problems in differential Galois theory.\/} To appear in: {\em Collected Works of Ellis R. Kolchin}. \item %\bibitem{SUl93a} Singer, M.~F., Ulmer, F. (1993a). {Galois groups for second and third order linear differential equations } {\em J.Symb.Comp {\bf 16} No. 1, 1-36}. \item %\bibitem{SUl93b} Singer, M.~F., Ulmer, F. (1993b). {Liouvillian and algebraic solutions of second and third order linear differential equations} {\em J.Symb.Comp {\bf 16} No. 1, 37-73}. \item %\bibitem{SUl94} Singer, M.~F., Ulmer, F. (1995). {Necessary conditions for Liouvillian solutions of (third order) linear differential equations} {\em J.\ of Appl.\ Alg.\ in Eng.\ Comm.\ and Comp.\ vol {\bf 6} No. 1, 1-22}. \item %\bibitem{SUl97} Singer, M.~F., Ulmer, F. (1997). { Linear differential equations and products of linear forms.} {\em J. Pure and Applied Alg., {\bf 117 \& 118}, 549-564}. \item %\bibitem{Sit92} Sit, W. (1992). { An algorithm for solving parametric linear systems}, {\em J. Symb. Comp. vol {\bf 13}, No 4, 353-413}. % \item %\bibitem{Stu94} Sturmfels B (1994) % {\em Algorithms in invariant theory} RISC series, Springer. \item %\bibitem{Tra76} Trager, B.~M. (1976). {Algebraic Factoring and Rational Function Integration.} {\em Proceedings of the 1976 ACM Symposium on Symbolic and algebraic Computation}. \item %\bibitem{Tsa96} Tsarev, S.~P. (1996). { An Algorithm for Complete Enumeration of All Factorizations of a Linear Ordinary Differential Operator}, {\em ISSAC'96 Proceedings, ACM Press}. \item %\bibitem{Ulm94} Ulmer, F. (1994). {Irreducible linear differential equations of prime order} {\em J. Symb. Comp. vol {\bf 18} No 4 , 385-401}. \item %\bibitem{UWe96} Ulmer, F., Weil, J.-A. (1996). { Note on Kovacic's algorithm} {\em J.Symb.Comp. vol {\bf 22} n$^\circ$ 2, 179-200}. \item %\bibitem{Wei95a} Weil, J.-A. (1995a). {First integrals and Darboux polynomials of homogeneous linear differential systems}, {\em Proceedings of AAECC 11 (Ed. M. Giusti \& T. Mora), Lect. Notes in Comp. Sci. {\bf 948}, Springer}. \item %\bibitem{Wei95b} Weil, J.-A. (1995b). {\em Constantes et polyn\^omes de Darboux en alg\`ebre diff\'erentielle~: application aux syst\`emes diff\'erentiels lin\'eaires}, PhD dissertation, \'Ecole Polytechnique. \end{thebibliography} \label{lastpage} %%%% \end{document} \vspace{1truecm} \noindent Jacques-Arthur Weil\\ D\'epartement de math\'ematiques\\ Facult\'e des sciences\\ 123 Avenue Albert Thomas\\ F-87060 Limoges.\\ \vskip .5truecm \noindent {\em Adresse \'electronique~:} weil@unilim.fr