\documentstyle[11pt]{article} \input{fullpage.sty} \newcommand{\N}{\mbox{N\hspace{-.730em}\rule{0.02em}{0.68em}\hspace{.7em}}} \newcommand{\C}{{\rm \mbox{C\hspace{-.455em}\rule{0.035em}{0.67em}\hspace{.5em}}}} \newcommand{\R}{\mbox{\rm R\hspace{-.730em}\rule{0.05em}{0.68em}\hspace{.7em}}} \newcommand{\Q}{\rm \mbox{\bf$Q\hspace{-.51em}$\rule{0.05em}{0.49em}\hspace{.4em}}} \newcommand{\Z}{\mbox{\sf Z \hspace{-1.1em} Z}} \def\miprod{{\scriptstyle \bigcirc\hspace{-0.23cm}\raisebox{0.02cm} {${\scriptstyle s}$}}\hspace{0.1cm}} \newtheorem{theorem}{Theorem} \newtheorem{definition}{Definition} \newtheorem{proposition}{Proposition} \newtheorem{lemma}{Lemma} \newcommand{\eindebewijs}{\begin{flushright} $\Box$ \end{flushright}} % \usepackage{maple2e} \begin{document} \title{Finite Singularities and Hypergeometric Solutions of Linear Recurrence Equations} \author{Mark van Hoeij\footnote{Department of Mathematics, Florida State University, Tallahassee, FL 32306-3027. This research was partially supported by CRC/FYAP Grant 132859548}} \maketitle \abstract{In this paper the notion of finite singularities of difference operators is introduced, in order to adapt methods for differential equations to the case of recurrence equations.} \section{Introduction} The goal of this paper is to introduce the notion of finite singularities of difference equations (recurrence equations) and to give some of their applications. So far only the singularity at infinity has been studied because that is the only point in $P^1(\C)$ which is invariant under the shift operator $\tau$, where $\tau(x)=x+1$. Since $x \mapsto x+1$ does not leave the elements of $\C$ invariant, the finite singularities should be elements of $\C/\Z$ instead of $\C$. In the theory of differential operators, a singularity $p$ is studied by considering differential operators over $\C((x-p))$, or $\C((1/x))$ if $p=\infty$. The shift operator $\tau: \C(x) \rightarrow \C(x)$ can be extended to $\C((1/x))$ but not to $\C((x-p))$ for $p \in \C$, and so for finite singularities we can not use a construction similar to the differential case. For a finite singularity $p \in \C/\Z$ we will consider left solutions % $u: \{q-M,q-(M+1),q-(M+2),\ldots\} \rightarrow \C$ and right solutions % $u: \{q+M,q+M+1,q+M+2,\ldots\} \rightarrow \C$ of the difference equation. % , where $M$ is a sufficiently large integer. We will show how one can obtain right solutions from left solutions by deforming the difference equation with $x \mapsto x+\epsilon$. After the deformation the left solutions are defined over a larger field of constants $\C(\epsilon)$, and a 1-1 map from these left solutions to the corresponding right solutions can be given. Then one can study the difference in $\epsilon$-valuation between these left and right solutions. That yields integers, called the {\em valuation growths}, that give useful information about the singularity, information that only depends on the {\em type} of the equation. These integers lead to an algorithm for computing hypergeometric solutions, given in section~\ref{hypergeomsols}. This algorithm is the analogue of the Beke/Schlesinger algorithm which treats the equivalent problem for the differential case, see \cite{beke} and section~\ref{section_expsols}. We can also use this deformation to define a map from the left solutions to the right solutions of the original (not deformed) equation, and a map from the right to the left solutions. In section~\ref{improvements} we use the ranks of these maps to prove two theorems that show over which field of constants the hypergeometric solutions can be found. This makes it possible to avoid the main bottleneck (splitting fields) in the computation of hypergeometric solutions. Previously only degree bounds were known, but not the fields themselves, so there was no easy way to avoid splitting fields. % (one would have to compute % all subfields of a certain degree of a splitting field). The theorems in section~\ref{improvements} are essential for the efficiency in case these splitting fields are large. We also give two relations between infinite and finite singularities in the case of an equation of order 1, similar to Fuchs' relation in the differential case. % In section~\ref{matrix} the valuation growths will be defined for systems % of first order difference equations. This way hypergeometric solutions of % such systems can be computed without converting the system to a % scalar equation $L(u)=0$ using a cyclic vector. \subsection{Differential and difference operators} A linear homogeneous differential equation \[ a_ny^{(n)} + a_{n-1}y^{(n-1)}+\cdots+a_1y'+a_0y=0 \] corresponds to a {\em differential operator} \[ L=a_n\partial^n + a_{n-1}\partial^{n-1}+\cdots+a_0\partial^0 \] acting on $y$. The coefficients $a_i$ that are considered here are elements of the differential field $\C(x)$ and $\partial$ is a differentiation $d/dx$. The differential operator $L$ is an element of the non-commutative ring $\C(x)[\partial]$, which is an {\em Ore ring}, cf.\ \cite{Ore}. Multiplication in this ring corresponds to composition of operators. A factorization $L=L_1L_2$ where $L_1,L_2 \in \C(x)[\partial]$ is useful for computing solutions of $L$ because solutions of the right-hand factor $L_2$ are solutions of $L$ as well. Right-hand factors of order 1 are particularly interesting because these are easy to solve. A right-hand factor $\partial - r$ where $r \in \C(x)$ corresponds to an {\em exponential solution} ${\rm exp}(\int r)$. Multiplying $L$ on the left by $1/a_n$ does not change the solution space, so without loss of generality we may assume that $a_n=1$, i.e. $L$ is {\em monic}. Similarly one can also study {\em difference operators} \[ L=a_n\tau^n + a_{n-1}\tau^{n-1}+\cdots+a_0\tau^0 \] where $\tau$ maps $x$ to $x+1$. Such a difference operator corresponds to a {\em difference equation} or {\em recurrence equation} \[ L(u)=a_nu(x+n)+ a_{n-1}u(x+n-1)+\cdots+a_0u(x)=0. \] Often one is interested in solutions that are sequences: $u(0),u(1),u(2),\ldots$, so then $u$ is a function from $\N$ to $\C$. It will be useful to consider other kinds of solutions as well. If $u$ is a solution of a difference equation of order $1$, so $u(x+1)=r(x)u(x)$ for some rational function $r \in \C(x)$, then $u$ is called {\em hypergeometric}. Just like exponential solutions in the differential case, hypergeometric solutions correspond to first order right-hand factors $\tau-r \in \C(x)[\tau]$ of $L$. \subsection{Finding exponential solutions} \label{section_expsols} Consider the function ${\rm exp}(\int r)$ where $r \in \C(x)$. How to find such solutions for a monic operator $L = \partial^n + a_{n-1}\partial^{n-1}+\cdots+a_0\partial^0$? In \cite{global} two methods are given, the classical method \cite{beke} that dates back to the previous century, and a new method. The classical method can be explained as follows. The function ${\rm exp}(\int r)$ is meromorphic at all but a finite number of points $p \in P^1(\C) = \C \bigcup \{\infty\}$. The ``non-meromorphicness'' of ${\rm exp}(\int r)$ at a point $p \in P^1(\C)$ can be classified by the so-called {\em exponential part} which (in this case) is an element of $\C[x^{-1}]/\Z$. For example the function $x^{1/3} = {\rm exp}(\int \frac{1/3}x )$ has exponential part $1/3 + \Z$ at the point $0$. If $e \in \C[x^{-1}]$ then ${\rm exp}(\int \frac{e}x )$ has exponential part $e + \Z$ at $x=0$. The collection of the exponential parts of ${\rm exp}(\int r)$ at all points $p \in P^1(\C)$ corresponds 1--1 with the {\em type} of ${\rm exp}(\int r)$. The type describes the ``non-meromorphicness'' of ${\rm exp}(\int r)$. Two exponential functions ${\rm exp}(\int r_1)$ and ${\rm exp}(\int r_2)$ have the same type if and only if their quotient is a rational function, so if and only if $r_1-r_2 = y'/y$ for some $y \in \C(x)$. At every singularity $p \in P^1(\C)$ of the operator $L$ one can compute the ``non-meromorphicness'' of all local solutions; one can compute all exponential parts at $p$. The number of different exponential parts at $p$ is at most the order of the operator $L$. There are only finitely many singularities, and at regular points only the trivial exponential part occurs. This leaves only a finite number (but possibly exponentially large number) of cases for the type of an exponential solution ${\rm exp}(\int r)$. When the type of an exponential solution $s$ is known, then $s$ is known up to a rational factor, so $s=y \cdot {\rm exp}(\int r)$ for some known $r \in \C(x)$ and unknown $y \in \C(x)$. The $\C(x)$-automorphism of $\C(x)[\partial]$ given by $\partial \mapsto \partial+r$ transforms $L$ into an operator $L \miprod (\partial+r)$. The solutions of this operator are the solutions of $L$ divided by ${\rm exp}(\int r)$. This way, finding $s$ is reduced to finding rational solutions $y \in \C(x)$ of $L \miprod (\partial+r)$. So computing exponential solutions can be done by making a finite list of possible types, and computing rational solutions for each case. \subsection{Finding hypergeometric solutions} Similar to the differential case, computing hypergeometric solutions is equivalent to computing first order factors $\tau-r \in \C(x)[\tau]$ of a difference operator $L$. Two hypergeometric expressions $u_1$ and $u_2$ have the same type if their quotient is a rational function. These $u_1$ and $u_2$ are solutions of $\tau-r_1$ and $\tau-r_2$ where $r_i=\tau(u_i)/u_i$. The two operators $\tau-r_1$ and $\tau-r_2$ have the same type (meaning that their solutions have the same type) if $r_1/r_2 = \tau(y)/y$ for some $y \in \C(x)^* = \C(x) \setminus \{0\}$. One can compute local information about solutions at the point $\infty$, cf. \cite{MR95k:39004,MR86h:12011}. This is similar to the differential case. In the differential case all singularities are needed for determining the possible types. Likewise, in the difference case, the singularity at infinity is not sufficient. Finite singularities are needed as well. % In the differential case, % to compute locally at a singularity $p$ is done algebraically % by replacing the differential % field $\C(x)$ by $\C((x-p))$ if $p \in \C$ % or $\C((1/x))$ if $p=\infty$. % In the difference case The $\C(x)$-automorphism $\tau$ which maps $x$ to $x+1$ can be extended to $\C((1/x))$ but not to $\C((x-p))$. As a consequence, % although computing % at the point infinity is very similar in the difference % and in the differential case, for finite $p$ a construction like in the differential case does not work in the difference case. This is why finite singularities of difference equations have not been studied before; a different approach is needed for this case. The key to find the definition of finite singularities is to study what is needed to be able to mimic methods (in particular: exponential solutions) from the differential case to the case of difference operators. In the differential case, the exponential parts determine the local type of an exponential solution, and the combination of all local types determines the type. Once the possible types are known, computing exponential solutions becomes easy. What kind of local data is needed to determine the type of a hypergeometric solution of a difference operator, or equivalently, the type of a first order right-hand factor? Consider the following example: $u(n)=n!=\Gamma(n+1)$, then $u$ is a solution of $\tau-(x+1)$. At negative integers, $u$ has a pole of order 1 (the valuation is $-1$) and at positive integers the valuation is 0 (i.e. $u$ has no pole and no root at positive integers). So, going through the integers from the left to the right, the valuation increases by $1$. For $p \in \C/\Z$ the {\em valuation growth} of $u$ is $1$ at $p=0+\Z \in \C/\Z$, and it is $0$ otherwise. % (because if % $n \not\in \Z$ then the valuation of $u$ at $n$ is 0). At the point infinity one can compute local data that resembles the exponential parts in the differential case. We will show that the valuation growths at each element of $\C/\Z$ combined with local data at infinity determines the type of $u$. So by determining the possible valuation growths and computing some local data at infinity it is possible to give a finite list of possible types of hypergeometric solutions. Similar to differential equations, for each possible type in this list one needs to compute rational solutions of a certain transformation of the operator $L$. The behavior of $L$ at $p \in \C/\Z$ will be studied by considering a deformation of $L$. This way a finite set $\overline{g}_p(L)$ can be computed, and it is shown that for all hypergeometric solutions of $L$ the valuation growth at $p$ is an element of $\overline{g}_p(L)$. % The converse is not true, not every element of this set needs % to occur as a valuation growth of a hypergeometric solution. A finite list of possible types can then be determined, and then we can proceed as in the Beke/Schlesinger method sketched in section~\ref{section_expsols}. \subsection{An example in Maple} % file: hyp_example on lars Consider the following difference operator $L \in \C(x)[\tau]$ \begin{eqnarray*} \lefteqn{L = (3\,x + 8)\,(3\,x + 10)\,(x + 3)\,(x + 2)\,(x + 1) \,\tau ^{3} - 3\,(3\,x + 5)\,(3\,x + 7)\,(x + 2)\,(x + 1)\,\tau ^{2}} \\ & & \mbox{} + 3\,(3\,x + 2)\,(3\,x + 4)\,(x + 1)\,\tau - (3\,x - 1)\,(3\,x + 1)\mbox{\hspace{135pt}} \end{eqnarray*} Solving the corresponding recurrence equation with Maple 5.4 and simplifying the result gives \[ \mathrm{u}(x)={\displaystyle \frac {1}{2}} \,{\displaystyle \frac { - (x - 1)\,(x - 2)\,\mathrm{u}(0) - 16\,x\,(x - 2)\, \mathrm{u}(1) + 70\,x\,(x - 1)\,\mathrm{u}(2)}{(3\,x - 1)\,(3\,x + 1)\, \Gamma (x + 1)}} \] All solutions of this difference operator $L$ have the same type; each solution $u(x)$ is a rational function times $1/\Gamma(x+1)$. However, the algorithm in \cite{MR94a:39006} will still distinguish a number of different cases. The number of cases in this example can be reduced to $1$ by computing the $\overline{g}_p(L)$ defined in section~\ref{finite}. In fact, whenever all solutions of a difference operator $L$ are hypergeometric and of the same type, the number of cases in the algorithm in section~\ref{hypergeomsols} is always 1, whereas in the method in \cite{MR94a:39006} the number of cases to check can still be exponentially high. Both methods are fast on this example though, because of the fact that all roots of the leading and trailing coefficients (the coefficients of the highest and of the lowest power of $\tau$ in $L$) are rational numbers, which makes this example relatively easy. \subsection{A harder example} % Not an artificial example because it was a bug-report % implying that user was interested in it. The following example was a motivation to start working on this problem. It was sent to Maple as a bug-report in the procedure {\tt hypergeomsols} in the LREtools package. After having fixed the bug, the algorithm still did not perform satisfactory; it takes weeks to run this example. \begin{eqnarray*} L &=& a_3\tau^3+a_2\tau^2+a_1\tau+a_0 \\ % {\rm \ \ \ \ where}\\ a_0&=& 18\, (2\,x+3 ) (x+2 ) (140\,{x}^{3}+1151\,{ x}^{2}+3114\,x+2781 ) (x+1 )^{2} \\ a_1&=& - (x+2 ) (23660\,{x}^{6}+302879\,{x}^{5}+1581604\,{x}^{4}+4314577 \,{x}^{3} \\ & & +6487290\,{x}^{2} +5099454\,x +1638144 ) \\ a_2&=&( 18380306\,{x}^{2}+13291032\,x +237304\,{x}^{6}+1637876\,{x}^{5}+4046652 \\ & & +14560\,{x}^{7}+6200310\,{x}^{4} +13887720\,{x}^{3} ) \\ a_3&=&-4\, (140\,{x}^{3}+731\,{x}^{2}+1232\,x+678 ) (2\,x+7 )^{2} (x+3 )^{2}. \end{eqnarray*} The current algorithm tries all combinations of all factors in $\C[x]$ of $a_3$ and all factors of $a_0$, that is 6912 cases. Computing with these factors requires computing with the splitting field of $a_0a_3$. This makes the computation slow. The computation can be done much faster by computing the sets $\overline{g}_p(L)$ for each finite singularity $p \in \C/\Z$, as defined in section~\ref{finite}. The roots of $a_3$ are $-7/2, -3, \alpha_1 ,\alpha_2,\alpha_3$ where $\alpha_i \in \C$ are the three roots of $140x^3+731x^2+1232x+678$. The roots of $a_0$ are $-3/2, -2, -1, \alpha_1-1,\alpha_2-1, \alpha_3-1$. The finite singularities of $L$ are the roots of $a_0a_3$ modulo the integers, so the finite singularities are $p_1=\alpha_1+\Z, p_2=\alpha_2+\Z, p_3=\alpha_3+\Z, p_4= 0+\Z , p_5=1/2+\Z$. Using a deformation of $L$ we will show how in section~\ref{computing_g_p} how to compute the sets \begin{eqnarray*} \overline{g}_{p_1}(L)=\overline{g}_{p_2}(L) =\overline{g}_{p_3}(L)&=&\{0\} \\ \overline{g}_{p_4}(L)&=&\{-2,-1,0,1,2\} \\ \overline{g}_{p_5}(L)&=&\{-2,-1,0,1\} \end{eqnarray*} Hence if $u$ is a hypergeometric solution, then for its valuation growth at $p$ where $p \in \C/\Z$ there are 5 cases if $p=p_4$, 4 cases if $p=p_5$ and only 1 case otherwise. So this leaves only $4 \cdot 5=20$ cases instead of the 6912 cases in the algorithm in \cite{MR94a:39006}. The singularity at infinity is not taken into consideration in this comparison, although it would make the difference slightly larger because of Fuchs' relations that we will introduce. What is more important for the computation timings than this 6912 to 20 ratio is that in our method the only singularities that really matter (i.e. where there is more than 1 case) are $p_4$ and $p_5$. So these 20 cases involve no algebraic extensions, and hence each of these cases is much easier than most of the 6912 cases (most of those do involve algebraic extensions). This way the computation can be done in less than a minute, which is more than 10000 times faster than Maple's implementation of \cite{MR94a:39006}. The result of the computation is that this example has no non-zero hypergeometric solutions. Splitting fields could be avoided in this example because of the fact that $p_1,p_2,p_3$ were apparent singularities. The same conclusion could (in this example, not in general) also be drawn by computing local information at infinity. But even without this information we could still obtain this conclusion from theorem~\ref{order3} in section~\ref{improvements}. If an operator does not have hypergeometric solutions then this can often quickly be detected by computing the {\em p-curvature}, see \cite{book} for a definition. However, in the example above this does not help because even though it does not have first order factors in characteristic 0, it does have first order factors modulo prime numbers. We verified this for primes $\leq 29$. \section{Preliminaries and definitions} Let $k = \C(x)$ and $\tau$ the $\C$-automorphism of $k$ defined by $\tau(x)=x+1$. A {\em difference operator} is an operator \begin{equation} L=a_n \tau^n + \cdots a_0 \tau^0 \label{hi} \end{equation} that acts in the following way on a function $f$ \[ (L(f))(x) = a_n(x) f(x+n) + \cdots + a_0(x) f(x). \] In this paper the coefficients $a_i$ will be elements of $k$. The function $L(f)$ is defined for those $x \in \C$ for which $f(x),\ldots,f(x+n)$ and $a_0(x),\ldots,a_n(x)$ are defined. If $a_n \neq 0$ then $n$ is called the {\em order} of $L$. The set of all difference operators is \[ k[\tau] = \{ a_n \tau^n + \cdots a_0 \tau^0 | n \in \N , a_0,\ldots,a_n \in k \}. \] The following \begin{equation} \tau \cdot a = \tau(a)\tau \label{product} \end{equation} defines the multiplication on $k[\tau]$. This turns $k[\tau]$ into a non-commutative ring. Using this relation any product of difference operators can be written in a unique way in the form~(\ref{hi}), i.e. the coefficients in $k$ appear on the left of the $\tau^i$. Multiplication in $k[\tau]$ corresponds to composition of difference operators; if $L= L_1 \cdot L_2$ then $L(f)$ coincides with $L_1(L_2(f))$ on the subset of $\C$ where both are defined. A sequence $u(0), u(1), u(2), \ldots$ of complex numbers is a function \[ u: \N \rightarrow \C. \] A function $u$ is called a solution of $L$ if $L(u)=0$, i.e. \[ L(u)(x) = a_n u(x+n) + \cdots + a_0 u(x) = 0 \] for all $x$ for which $L(u)(x)$ is defined. So a difference operator $L = a_n \tau^n + \cdots a_0 \tau^0$ of order $n$ corresponds to a recurrence relation of order $n$. For example the sequence $u: \N \rightarrow \C$, $u(m)=m!=\Gamma(m+1)$ is a solution of $L=\tau-(x+1)$. We would also like to consider sequences that are solutions of an operator like $L=\tau-1/(x-3)$, however, the coefficients of this $L$ are not defined for all $x \in \N$. To avoid such problems with domains of definition we will consider sets $V_{p,r}$ and $V_{p,l}$ consisting of germs of sequences, just like the set ${\cal S}$ in \cite{book}. A {\em germ} of a sequence $u$ is $u$ modulo the ideal of sequences with finite support. So two sequences have the same germ if and only if their difference has finite support. Denote $q+\N = \{q,q+1,q+2,\ldots\} \subset q+\Z$ and $q-\N = \{q,q-1,q-2,\ldots\} \subset q+\Z$. For $a,b$ in $q+\Z$ define an ordering by $a>b$ iff $a-b>0$. Define $V_{q,l}$ as the set of germs of functions $u: q-\N \rightarrow \C$. So $V_{q,l}$ is the ring of all functions from $q-\N$ to $\C$ modulo the ideal of functions that are non-zero at only finitely many points $x$ in $q-\N$. Note that if $q_1 - q_2 \in \Z$ then $V_{q_1,l}$ and $V_{q_2,l}$ can be identified, and so $V_{p,l}$ can be defined for $p \in \C/\Z$ as well. Similarly define $V_{q,r}$ as the set of germs of functions $u: q+\N \rightarrow \C$. Multiplication and addition in $V_{p,r}$ where $p=q+\Z$ corresponds to multiplication and addition of functions $u:q+\N \rightarrow \C$. The invertible elements of $V_{p,r}$ correspond to those $u$ for which $u(x)=0$ for only finitely many $x \in q+\N$. If $u$ is zero for infinitely many $x \in q+\N$ then $1/u$ is not defined. In this case $u$ is either $0$ in $V_{p,r}$ (if $u$ has finite support) or a zero-divisor in $V_{p,r}$ otherwise. Each element $f \in k$ is a function from $\C$ to $\C$ that is defined on all but a finite number of elements of $\C$. %, so $f$ is defined on % the set $\{q+M,q+M+1,\ldots\} \subset \C$ whenever $M$ is sufficiently % large. Hence $k$ can be embedded in the ring $V_{p,r}$, and also in $V_{p,l}$. Now $V_{p,r}$ and $V_{p,l}$ are $k$-algebras and $k[\tau]$-modules. \begin{definition} Let $L=a_n \tau^n + \cdots + a_0 \tau^0 \in k[\tau]$ and $L \neq 0$. Denote \[ {\rm ord}(L) = {\rm max}\{ i | a_i \neq 0\} \ - \ {\rm min}\{i|a_i \neq 0\} \] \[ {\rm order}(L) = {\rm max}\{ i | a_i \neq 0\}. \] $L$ is called {\em normal} if $a_0 \neq 0$, i.e. if ${\rm ord}(L)={\rm order}(L)$. Let \[ V_{p,r}(L) = \{u \in V_{p,r} | L(u)=0 \} \] \[ V_{p,l}(L) = \{u \in V_{p,l} | L(u)=0 \} \] be the kernels of $L$ on $V_{p,r}$ and on $V_{p,l}$. These are the solution spaces of $L$ in $V_{p,r}$ and in $V_{p,l}$. \end{definition} The {\em leading} coefficient of $L$ is the highest non-zero coefficient of $L$ (which is $a_n$ if $a_n \neq 0$). The {\em trailing} coefficient is the lowest non-zero coefficient of $L$ (which is $a_0$ if $L$ is normal). $L$ is called {\em monic} if the leading coefficient is 1. The set $V_{0,r}$ is called ${\cal S}$ in \cite{book}, where it is shown that the Picard-Vessiot ring of $L$ over $k$ can be embedded in ${\cal S}$. % The construction of $V_{p,r}$ and $V_{p,l}$ is very similar to ${\cal S}$, The same proof also shows that the Picard-Vessiot ring can be embedded in each of the $V_{p,r}$ and $V_{p,l}$, and hence the following proposition holds (this is part 2 of proposition~4.1 in chapter 4 in \cite{book}). \begin{proposition} \label{proposition1} The dimension (as a $\C$-vector space) of the solution spaces is \[ {\rm dim}(V_{p,r}(L))={\rm dim}(V_{p,l}(L)) ={\rm ord}(L). \] \end{proposition} Problems with vanishing of the leading or trailing coefficients of $L$, or coefficients having poles, have been eliminated by taking germs of sequences. Hence the proposition corresponds to the well-known statement that recurrence relations of order $n$, for which the leading and trailing coefficients do not vanish, have an $n$-dimensional solution space. \begin{definition} A $k$-algebra $V$ is called a {\em universal extension} of $k$ if the following three conditions hold \begin{enumerate} \item $\tau: V \rightarrow V$ is an automorphism that extends $\tau:k \rightarrow k$. \item For every $L \in k[\tau]$ the kernel of $L: V \rightarrow V$ is an ${\rm ord}(L)$-dimensional $\C$-vector space. \item For every $u \in V$ there exists a non-zero $L \in k[\tau]$ such that $L(u)=0$. \end{enumerate} \end{definition} A universal extension exists because one can verify that $\{u \in V_{p,r} | \exists_L \ L(u)=0\}$ is a $k[\tau]$-module and $k$-algebra (to show closure under addition and multiplication use LCLM and symmetric products of operators, a definition follows later). See section 6.2 in \cite{book} for another existence proof, where a universal extension is constructed using a difference ring extension of $\C((1/x))$ (so a local construction at the point $p=\infty$). Let $V$ be a universal extension of $k$. $V$ is unique (see \cite{book}) up to difference isomorphisms (i.e. isomorphisms that commute with $\tau$). $V$ can be embedded in each of the $V_{p,r}$ and $V_{p,l}$ for any $p \in \C/\Z$ but not in a unique way because $V$ has many difference automorphisms. We denote the solution space of $L$ in $V$ by $V(L)$. From now on, unless mentioned otherwise, by {\em solutions} of a difference operator $L$ we will mean elements of $V(L)$. A solution $y \in V(L)$ can also be interpreted as an element of $V_{p,r}(L)$ or $V_{p,l}$, but only after having chosen an embedding of $V$ in those rings. The ring of difference operators $k[\tau]$ is a non-commutative Euclidean ring; one can compute ${\rm GCRD}(L_1,L_2)$, the {\em greatest common right divisor} of two operators $L_1$ and $L_2$, c.f.\ \cite{Ore,MR96m:34013}. One can also compute an operator ${\rm LCLM}(L_1,L_2)$, the {\em least common left multiple}. Requiring that the LCLM and GCRD are monic makes them uniquely defined. \begin{lemma} For every non-zero $M \in k[\tau]$ there exists a unique monic normal $L \in k[\tau]$ for which $V(L)=V(M)$. If $L_1$ and $L_2$ are normal operators then \begin{enumerate} \item $L_1$ is a right-hand factor of $L_2$ if and only if $V(L_1) \subset V(L_2)$. \item $L_3={\rm GCRD}(L_1,L_2)$ is normal and $V(L_3)=V(L_1) \bigcap V(L_2)$. \item $L_4={\rm LCLM}(L_1,L_2)$ is normal and $V(L_4)=V(L_1) + V(L_2)$. \end{enumerate} \end{lemma} Later in the paper we will often only consider operators that are normal, or normal and monic. According to the lemma this is no real restriction. The lemma appears to be known but not explicitly written down. It is a immediate consequence of the fact that every finite dimensional $G$-invariant subspace of $V$ (such as $V(L_1) \bigcap V(L_2)$ and $V(L_1)+V(L_2)$) is the solution space of some element of $k[\tau]$, where $G$ is the difference Galois group. This is a non-trivial result, proven in \cite{hendriks_singer}, where it is also shown that the dimension of the solution space is always $\leq {\rm ord}(L)$ in any Picard-Vessiot extension of $k$. \begin{definition} An element $u$ of $V_{p,r}$ or $V_{p,l}$ or $V$ is called {\em rational} if it is an element of $k$, and it is called {\em hypergeometric} if it is a solution of an operator of order 1, so $\tau(u)=ru$ for some $r \in k$. The set of all hypergeometric elements of $V$ is denoted by $H$. \end{definition} For example the sequence $u(n)=n!=\Gamma(n+1)$ is hypergeometric. The sequence $c^n$ where $c \in \C$ is also hypergeometric. Rational sequences ($u$ is a rational function in $n$) are also hypergeometric. $H^*=H \setminus \{0\}$ is a group under multiplication; hence products: \[ u \in {\cal S}=V_{0,r}, \ \ \ u(n) = c^n R(n) \Gamma(n+a_1)^{e_1} \cdots \Gamma(n+a_s)^{e_s} \] are also hypergeometric, where $c,a_i \in \C$, $e_i \in \Z$ and $R$ is a rational function. Every hypergeometric element of $V_{0,r}$ can be represented in this way. If $u \in H^*$ and $L \in k[\tau]$ then $L(u)/u \in k$ and hence $L(u) \in H$. However, $H$ is not a $k[\tau]$-module because $H$ is not closed under addition. Similar to the differential case one can define \begin{definition} Let $L_1, L_2 \in k[\tau]$ be normal and of order $\geq 1$. Then the {\em symmetric product} $L= L_1 \miprod L_2$ is defined as the normal monic operator of minimal order such that $y_1y_2 \in V(L)$ for all $y_1 \in V(L_1)$ and $y_2 \in V(L_2)$. \end{definition} Any $\tau^i(y_1)$ can be written as a $k$-linear combination of $\tau^0(y_1),\ldots,\tau^{n-1}(y_1)$ using the relation $L_1(y_1)=0$, where $n={\rm order}(L_1)$. A similar statement holds for the $\tau^i(y_2)$. Then $L$ can be obtained by computing a $k$-linear relation between $y_1y_2$, $\tau(y_1)\tau(y_2)$, $\tau^2(y_1)\tau^2(y_2)$, $\ldots$. The same construction is also found in the proof of lemma~6.8 in \cite{hendriks_singer}, where it is also shown that every finite dimensional $G$-invariant subspace of $V$ occurs as the solution space of an element of $k[\tau]$, which implies that $V(L_1 \miprod L_2)$ is spanned by $\{y_1y_2 | y_1 \in V(L_1), \ y_2 \in V(L_2) \}$. Note that the situation is easier when one of these two operators has order 1. Then $L_1 \miprod L_2$ can be computed without solving linear equations. \begin{lemma} If $L_1=\tau-r$ with $r \in k^*$, $u \in H^*$ with $L_1(u)=0$, and $L_2$ is monic and normal then \[ su \cdot L_2 \cdot \frac1u = L_1 \miprod L_2 \in k[\tau] {\rm \ \ \ where \ \ \ } s={\tau^{{\rm order}(L_2)}(u)}/u \in k^*. \] \end{lemma} To prove this note that $su \cdot L_2 \cdot \frac1u$ is monic and has the same solution space as $L_1 \miprod L_2$. Furthermore $L_2 \cdot v \in v \cdot k[\tau]$ for every $v \in H^*$ so $su \cdot L_2 \cdot \frac1u \in su \cdot 1/u \cdot k[\tau]=k[\tau]$. \section{The point at infinity} \label{infinity} The local properties of the operator $L$ at the point $p=\infty$ have been well studied (see \cite{MR95k:39004,MR86h:12011,Tournier,levelt} and references therein). This in contrast to finite singularities of $L$, which have not been considered before, but are useful as well. In this section we will review the local information we need from the singularity at infinity (we consider the point at infinity to be a singularity of every difference operator). Finite singularities will be introduced in section~\ref{finite}. The local types at all singularities (finite singularities and the point at infinity) will be used in section~\ref{hypergeomsols} to give a new and more efficient algorithm for computing hypergeometric solutions of difference equations. This algorithm can be viewed as the analogue for the difference case of the Beke/Schlesinger algorithm. Other local properties at finite singularities (the maps $E_{p,l}$ and $E_{p,r}$) will be introduced % which make it possible to in order to prove the theorems in section~\ref{improvements}. Those theorems are used to improve the efficiency of the algorithm in section~\ref{hypergeomsols}. Let $L=a \cdot (\tau-r)$ for some $a$ and $r$ in $k^*$. Define the commutative group \[ {\cal H}_{\infty} = \C^* \times \Z \times (\C/\Z). \] We will use the additive notation for this group, $(c_1,n_1,d_1)+(c_2,n_2,d_2)= (c_1c_2,n_1+n_2,d_1+d_2) \in {\cal H}_{\infty}$. Let $t=1/x$. Then $r$ can be written in the form $r=c \cdot t^n \cdot (1+dt+{\cal O}(t^2))$ for some $c,d \in \C$. % and $e \in t^2 \C[[t]]$. Now define the {\em local type} of $L$ at $\infty$ as \[ g_{\infty}(L)=(c,n,d+\Z) \in {\cal H}_{\infty}. \] Define the following groups with multiplication $\miprod$ \[ k^*_{\miprod} = \{ \tau -r | r \in k^* \} \ \ \ \ {\rm and} \ \ \ \ k^*_R = \{ \tau -\tau(r)/r | r \in k^* \} \subset k^*_{\miprod} \] We have $(\tau-r_1) \miprod (\tau-r_2) = \tau-r_1r_2$ so $k^*_{\miprod}$ is isomorphic with the multiplicative group $k^*$. It is easy to verify that $g_{\infty}$ is a surjective group homomorphism from $k^*_{\miprod}$ to ${\cal H}_{\infty}$. Furthermore $g_{\infty}(\tau-r)=g_{\infty}(\tau-\tau(r))$ and hence $k^*_R$ is a subgroup of the kernel of $g_{\infty}$. So $g_{\infty}(L)$ only depends on the type (see definition below) of $L$. \begin{definition} Let $L=a(\tau-r)$ where $a,r \in k^*$. Then the {\em type} of $L$ is defined as the image of $\tau-r$ in the group (with $\miprod$ as multiplication) $k^*_{\miprod}/k^*_R$. \end{definition} The type is trivial, i.e. ${\rm type}(L)$ is the identity in $k^*_{\miprod}/k^*_R$, if and only if the solutions of $L$ are rational. The type can be defined for operators of higher order as well: \begin{definition} Two operators $L_1$ and $L_2$ have the same {\em type} if and only if ${\rm ord}(L_1)={\rm ord}(L_2)$ and there exists an operator $r \in k[\tau]$ such that $r(V(L_1))=V(L_2)$. \end{definition} This is equivalent with the existence of two operators $r,r' \in k[\tau]$ for which $r(V(L_1))=V(L_2)$ and $r'(V(L_2))=V(L_1)$. This $r'$ can be computed from $r$ by the extended Euclidean algorithm for $k[\tau]$. With this algorithm one can find $r',s \in k[\tau]$ for which $r'r + sL_1=1$. For order 1 the two definitions of the type coincide. See \cite{testing_reducibility} for several characterizations of the notion of type for the differential case (the difference case works in the same way). The field $\C((t))$ where $t=1/x$ is a difference field extension of $k$, where $\tau(t)=\tau(1/x)=1/(x+1)=t/(1+t) \in \C((t))$. The definition of $g_{\infty}(L)$ for a normal operator $L$ with ${\rm order}(L)=1$ applies for $\C((t))[\tau]$ as well. \begin{definition} Let $L \in \C((t))[\tau]$ be normal. Then $\overline{g}_{\infty}(L)$ is defined as the set of $g_{\infty}(M)$ for all right-hand factors $M \in \C((t))[\tau]$ of $L$ of order 1. \end{definition} If $L \in k[\tau]$ then the set of $g_{\infty}(M)$ for all first order right-hand factors $M \in k[\tau]$ can be a proper subset of $\overline{g}_{\infty}(L)$, because $L$ may have more right-hand factors in $\C((t))[\tau]$ than in $k[\tau]$. The {\em characteristic classes} in \cite{levelt} determine the isomorphism classes of all factors in $\C((t))[\tau]$ of $L$, whereas the set $\overline{g}_{\infty}(L)$ determines only the isomorphism classes of first order factors of $L$ in $\C((t))[\tau]$. The set $\overline{g}_{\infty}(L)$ gives a part of the information encoded in the characteristic classes, namely the part that we use for computing hypergeometric solutions. So the following lemma can be viewed as a special case of results in \cite{levelt}. \begin{lemma} The number of elements of $\overline{g}_{\infty}(L)$ is at most ${\rm order}(L)$. \end{lemma} This lemma follows from factorization properties in $\C((t))[\tau]$, and also from the structure of the formal solutions at the point $\infty$. We give a brief sketch, for more details on factorization and formal solutions see \cite{MR95k:39004,MR86h:12011,Tournier}. The elements $(c,n,d) \in {\cal H}_{\infty}$ of $\overline{g}_{\infty}(L)$ can be computed as follows: For the ring $\C((t))[\tau]$ one can define a Newton polygon and Newton polynomial (called the $\tau$-polygon and characteristic equation in \cite{MR95k:39004}). The slopes of that polygon give the possible values for $n$, and $c$ must be a root of the corresponding Newton polynomial. To find $d$ we take the symmetric product of the operator with $\tau-1/(ct^n)$, then we need to search for factors of the form $\tau-(1+dt+{\cal O}(t^2))$. Let $\delta=\tau-1$. By writing the operator as a polynomial in $\delta$ instead of $\tau$ one can define a different Newton polygon (called the $\delta$-polygon in \cite{MR95k:39004}). Then $d$ can be computed using the Newton polynomial for slope 1. This way the $(c,n,d)$, and hence $\overline{g}_{\infty}(L)$, can be obtained with little computational effort. % In fact if we let $d \in \C$ instead of $d \in \C/\Z$ then the number of % possible $(c,n,d)$ is still at most the order of $L$. % apparent singularity? Or semi-regular? \section{Finite singularities of difference equations} \label{finite} The two previous sections (preliminaries and the singularity at infinity) form a summary of known work that we will use. The new results in this paper are the definitions in this section and their applications (theorems~\ref{order2},~\ref{order3} and the algorithm in section~\ref{hypergeomsols}). \begin{definition} Let $L=a_n \tau^n + \cdots a_0 \tau^0 \in k[\tau]$ with $a_n \neq 0$ and $a_0 \neq 0$. After multiplying $L$ on the left by a suitable element of $k$ we may assume the coefficients $a_i$ are in $\C[x]$ and ${\rm gcd}(a_0,\ldots,a_n)=1$. Then $q \in \C$ is called a {\em problem point} of $L$ if $q$ is a root of the polynomial $a_0(x)a_n(x-n)$. And $p \in \C/\Z$ is called a {\em singularity} of $L$ if $a_0a_n$ has a root in $p$. The point $\infty$ is considered a singularity as well. \end{definition} If using the recurrence relation for solutions $u$ of $L$ we can not determine $u(q)$ from $u(q-1),\ldots,u(q-n)$, or we can not determine $u(q)$ from $u(q+1),\ldots,u(q+n)$, then the point $q \in \C$ is a problem point. The finite singularities in $\C/\Z$ are the problem points modulo $\Z$. The set of singularities of $L$ is a finite subset of $\C/\Z \bigcup \{\infty\}$. Let $q \in \C$ and $r \in k^*$. The {\em valuation} $v_q(r)$ of $r$ at $q$ (also called the order at $q$) is the largest integer $n$ such that $r/(x-q)^n \in \C[[x-q]]$. The valuation of $0$ is $\infty$. \begin{definition} \label{def_g_u} Let $p \in \C/\Z$. Define the group homomorphism $v_p: k^* \rightarrow \Z$ as \[ v_p(r)=\sum_{q \in p} v_q(r). \] Let $L=a \cdot (\tau-r)$ for some $a,r \in k^*$. Then the {\em valuation growth} or {\em local type} of $L$ at $p$ is defined as \[ g_p(L)=v_p(r) \in \Z. \] Define ${\cal H}$ as the product of the additive group of all functions $\C/\Z \rightarrow \Z$ with finite support and the group ${\cal H}_{\infty}$. Then define the collection of all local types \[ g(L)=( p \mapsto g_p(u) , g_{\infty}(u) ) \in {\cal H}. \] \end{definition} For example $u(n)=n! \cdot 2^n$, $u \in H^*$. Then $g_p(u)$ is 1 if $p=\Z$, it is $(2,-1,\Z)$ if $p=\infty$ and $0$ otherwise. The map $g_p$ where $p \in \C/\Z$ is a group homomorphism from $k^*_{\miprod}$ to $\Z$. Furthermore $v_p(\tau(r))=v_p(r)$ and so $k^*_R$ is contained in the kernel of $g_p$ for finite $p$ as well. Hence $g(L)$ only depends on ${\rm type}(L) \in k^*_{\miprod}/k^*_R$. \begin{definition} Let ${\cal H}_F$ be the set of all $(f,(c,n,d+\Z)) \in {\cal H}$ where $f: \C/\Z \rightarrow \Z$ and $c,d \in \C$ and $n \in \Z$ for which: \begin{equation} n+\sum_{p \in \C/\Z} f(p)=0 {\rm \ \ \ \ and \ \ \ } d+\sum_{p \in \C/\Z} f(p)p \equiv 0 {\rm \ \ mod \ \ } \Z. \label{relation} \end{equation} \end{definition} The relations~(\ref{relation}) are called {\em Fuchs' relations}, because in the differential case a similar relation with the same name (lemma 9.2 in \cite{global}) exists between the {\em exponential parts}, which are the differential equivalent of the $g_p(L)$. So ${\cal H}_F$ is the set of all elements of ${\cal H}$ that satisfy the Fuchs' relations. It is a subgroup of ${\cal H}$. Note that the two sums are defined because $f$ has a finite support; $f(p) \neq 0$ for only finitely many $p \in \C/\Z$. \begin{theorem} \label{theorem1} The map $g: k^*_{\miprod} \rightarrow {\cal H}$ is a group homomorphism. The kernel is $k^*_R$. The image is ${\cal H}_F$. So $g$ induces an isomorphism between the group of types of normal operators of order 1 and the group ${\cal H}_F$. \end{theorem} % So the type of an operator of order 1 is determined by its local types. \\ {\bf Proof:} To show that the image is contained in ${\cal H}_F$ we only need to verify that this is true for the generators $\tau-c$ and $\tau-(x-q)$ of the group $k^*_{\miprod}$, where $c \in \C^*$ and $q \in \C$. The map is surjective because if $F=(f,(c,n,d+\Z)) \in {\cal H}_F$ then $F=g(F')$ where $F' = \tau-c(x-q_1)^{f(q_1)} \cdots (x-q_m)^{f(q_m)}$. Here $q_1,\ldots,q_m$ are representants in $\C$ for the $p_1,\ldots,p_m \in \C/\Z$ for which $f(p_i) \neq 0$, and $p_i \neq p_j$ if $i \neq j$. It is easy to see that such $F'$ can only be in $k^*_R$ if $c=1$ and $f=0$, i.e. if $F=(0,(1,0,\Z))$ which is the identity in ${\cal H}_F$. So the kernel is contained in $k^*_R$, and hence equal to $k^*_R$. \eindebewijs That the kernel is $k^*_R$ is lemma~2.1 in section~2.1 in \cite{book}. The rest of this theorem (the Fuchs' relations and the group homomorphism $g$) appears to be new. The map $u \mapsto \tau-\tau(u)/u$ (note that $u$ is a solution of $\tau-\tau(u)/u)$ induces group isomorphisms $H^*/\C^* \rightarrow k^*_{\miprod}$ and $H^*/k^* \rightarrow k^*_{\miprod}/k^*_R$. This way the local types $g_p(u)$ of $u$ at $p \in \C/\Z \bigcup \{\infty\}$ can be defined for $u \in H^*$ or $u \in H^*/k^*$. \\[10pt] \subsection{Valuation growths} According to theorem~\ref{theorem1} the type of $u \in H^*$ (i.e. the type of operators $L=\tau-\tau(u)/u$ of order 1) is determined by the local types $g_p(u)$ at all $p \in \C/\Z \bigcup \{\infty\}$. To determine all hypergeometric solutions $u \in H^*$ of an operator $L$ of order $>1$ we will define in this section for every finite singularity $p \in \C/\Z$ a finite set $\overline{g}_p(L)$ of valuation growths such that $g_p(u) \in \overline{g}_p(L)$ for every hypergeometric solution $u$ of $L$. Then, by trying all combinations that satisfy Fuchs' relations, we obtain a finite set of possibilities for the type of $u$. For each type, we divide all solutions of $L$ by a $u' \in H^*$ with the same type, so $u/u' \in k^*$, and then to find $u$ the problem is reduced to finding rational solutions. This leads to the algorithm in section~\ref{hypergeomsols}, given in more detail in section~\ref{improvements}. First we will give an intuitive idea of valuation growths using an example. Then we will define the set of valuation growths, and show in section~\ref{computing_g_p} how it can be computed, and that this set is finite. {\bf Example.} Let $u \in H^*$ be the gamma function $u(n)=\Gamma(n)=(n-1)!$. This is a function on $\C$ that has poles of order 1 (interpret this as valuation $-1$) at the non-positive integers. It has no poles and no roots (i.e. valuation 0) at the positive integers. So, going trough the integers from the left to the right (passing the {\em problem point}), the valuation increases by 1; the valuation growth $g_p(u)=1$ at $p = \Z \in \C/\Z$. If $p \in \C/\Z$ is not equal to $\Z$ then $u$ has valuation 0 (i.e. no poles and no roots) on $p$, so going trough $p$ from the left to the right, the valuation remains the same; $g_p(u)=0$. Also, if $p \neq \Z$ then there are no problem points on $p$ so $p$ is not a singularity. This $u$ is a solution of $L=\tau-x$, and indeed $g_p(L)$ is $1$ if $p=\Z$ and $0$ for all other $p \in \C/\Z$. The statement that the solution $u$ of $L$ has valuation $0$ at positive integers and valuation $-1$ at negative integers uses analytic continuation, because this is a property of the function $\Gamma(n)$, and that is a continuation of $(n-1)!$. We can not perform exact analytic continuation on a computer, so to make this algorithmic requires an algebraic definition of the valuation of a solution at a point. This will be done by extending the field of constants to $\C(\epsilon)$ where $\epsilon$ is transcendental over $\C$, so $\epsilon$ is a new indeterminate. Then we can consider solutions $\tilde{u}: \Z \rightarrow \C(\epsilon)$ of an operator $L_{\epsilon}=\tau-(x+\epsilon) \in \C(\epsilon,x)[\tau]$. We can take a solution $\tilde{u}$ of $L_{\epsilon}$ for which $\tilde{u}(1)=1$. Then $\tilde{u}(n)=\prod_{i=1}^{n-1}(i+\epsilon)$ for $n \geq 1$, and $\tilde{u}(n)=1/\prod_{i=n}^{0}(i+\epsilon)$ for $n \leq 0$. Now $\tilde{u}(n)$ has value $u(n)$ at $\epsilon=0$ for every integer $n \geq 1$. For $n \leq 0$, $\tilde{u}(n)$ has a pole at $\epsilon=0$ of order 1, i.e. the $\epsilon$-valuation $v_{\epsilon}(\tilde{u}(n))$ is $-1$ for $n \leq 0$, a definition follows later. Now the valuation growth is \[\liminf_{n \rightarrow \infty} v_{\epsilon}(\tilde{u}(n)) \ \ - \ \ \liminf_{n \rightarrow -\infty} v_{\epsilon}(\tilde{u}(n))\] which is $1$ in this example. The liminf suggests that this describes local behavior at infinity. However, that is not the case because in this liminf $n$ does not need to go to $\infty$ or $-\infty$ but only needs to pass the problem points. Note that substituting $\epsilon=0$ in $\tilde{u}$ results in an non-zero right-solution of $L$, i.e. a non-zero element of $V_{0,r}(L)$. Evaluating $\epsilon \cdot \tilde{u}$ at $\epsilon=0$ results in a non-zero left-solution of $L$. So apparently there is a canonical way to define maps $E_{0,r}:V_{0,l}(L) \rightarrow V_{0,r}(L)$ and $E_{0,l}:V_{0,r}(L) \rightarrow V_{0,l}(L)$ in this example. Such maps can be defined in general as well. We will use the ranks of these maps to avoid splitting fields in the computation of hypergeometric solutions. \\ \begin{definition} Let $L \in k[\tau]$ and suppose $p \in \C/\Z$ is not a singularity. Then define $V_p(L)$ as the set of functions $u: p \rightarrow \C$ that are solutions of $L$. If $p$ is not a singularity then $V_{p,l}(L)$ and $V_{p,r}(L)$ can both be identified with $V_p(L)$. \end{definition} The dimension of $V_p(L)$ equals ${\rm ord}(L)$, c.f. proposition~\ref{proposition1}. This identification of $V_{p,l}(L)$ with $V_{p,r}(L)$ for non-singular $p$ yields identification maps $E_{p,l}: V_{p,r}(L) \rightarrow V_{p,l}(L)$ and $E_{p,r}: V_{p,l}(L) \rightarrow V_{p,r}(L)$. Later we will generalize these maps to singular $p$ as well, in which case we will see that these maps are $1-1$ if and only if $p$ is a {\em semi-apparent} singularity, definitions follow later. \begin{definition} Let $\epsilon$ be a new indeterminate; $\epsilon$ is transcendental over $\C$. Define the action of $\tau$ on $\C(\epsilon,x)$ as $\tau(\epsilon)=\epsilon$ and $\tau(x)=x+1$. This turns $\C(\epsilon,x)$ into a difference field with $\C(\epsilon)$ as the field of constants. For $a \in \C(\epsilon)$ the $\epsilon$-valuation is \[ v_{\epsilon}(a) = {\rm sup}\{m \in \Z| a \in \epsilon^m \C[[\epsilon]] \} \in \Z \bigcup \{\infty\}. \] Let $L \in k[\tau]$. Define $L_{\epsilon} \in \C(\epsilon,x)[\tau]$ as the operator one obtains from $L$ by replacing $x$ by $x+\epsilon$. We call $L_{\epsilon}$ the {\em deformation} of $L$. \end{definition} The map $L \mapsto L_{\epsilon}$ defines an embedding (as non-commutative rings) of $k[\tau]$ in $\C(\epsilon,x)[\tau]$; if $L=MN$ then $L_{\epsilon}=M_{\epsilon}N_{\epsilon}$. Suppose $\tilde{u}:q+\N \rightarrow \C(\epsilon)$ with $q \in \C$, and $\tilde{L} \in \C(\epsilon,x)[\tau]$. Let $\tilde{u}_{\epsilon=0}:q+\N \rightarrow \C$ and $\tilde{L}_{\epsilon=0} \in k[\tau]$ be the result of substituting $\epsilon=0$ in $\tilde{u}$ and $\tilde{L}$, and assume that this substitution can be done, i.e. that there are no poles at $\epsilon=0$. Then $(\tilde{L}(\tilde{u}))_{\epsilon=0} = \tilde{L}_{\epsilon=0}(\tilde{u}_{\epsilon=0})$, i.e. substituting $\epsilon=0$ commutes with applying an operator. In particular, if $\tilde{u}: q+\N \rightarrow \C(\epsilon)$ is a solution of $L_{\epsilon}$, then $\tilde{u}_{\epsilon=0}$ (if the substitution $\epsilon=0$ can be done) is a solution of $L$. If $L \in k[\tau]$ and $p \in \C/\Z \subset \C(\epsilon)/\Z$ then $p$ is not a singularity of $L_{\epsilon}$. So the ${\rm ord}(L)$-dimensional $\C(\epsilon)$-vector spaces $V_{p,l}(L_{\epsilon})$ and $V_{p,r}(L_{\epsilon})$ can be identified with $V_p(L_{\epsilon})= \{ \tilde{u}:p \rightarrow \C(\epsilon) | L_{\epsilon}(\tilde{u})=0 \}$. Let $L = a_n\tau^0 + \cdots + a_0\tau^0 \in k[\tau]$ with $a_n \neq 0$ and $a_0 \neq 0$, and let $p \in \C/\Z$. Let $q_l$ (resp. $q_r$) be the smallest (resp. largest) root of $a_0(x)a_n(x-n)$ in $p$, so $q_l$ (resp. $q_r$) is the smallest (resp. largest) {\em problem point} at $p$. If $p$ is not a singularity (so then there are no problem points at $p$) then choose arbitrary elements $q_l,q_r \in p$. \begin{definition} With notations as above, for non-zero $\tilde{u} \in V_p(L_{\epsilon})$ define the {\em left valuation} {\rm \[ v_{\epsilon,l}(\tilde{u})= {\rm min}\{v_{\epsilon}(\tilde{u}(m)) | m \in q_l-1-\N \} \]} {\em the right valuation} {\rm \[ v_{\epsilon,r}(\tilde{u})={\rm min}\{v_{\epsilon}(\tilde{u}(m)) | m \in q_r+1+\N \} \]} and the {\em valuation growth} \[ g_{p,\epsilon}(\tilde{u})=v_{\epsilon,r}(\tilde{u})-v_{\epsilon,l}(\tilde{u}) \in \Z. \] Define the {\em set of valuation growths of $L$ at} $p$ \[ \overline{g}_p(L)=\{g_{p,\epsilon}(\tilde{u}) | \tilde{u} \in V_p(L_{\epsilon}), \ \tilde{u} \neq 0 \} \subset \Z. \] If $v_{\epsilon,l}(\tilde{u}) \geq 0$ then the {\em left projection} $\rho_l(\tilde{u}) \in V_{p,l}(L)$ is defined by substituting $\epsilon=0$ in $\tilde{u}$. Similarly if $v_{\epsilon,r}(\tilde{u}) \geq 0$ then the {\em right projection} $\rho_r(\tilde{u}) \in V_{p,r}(L)$ is defined. \end{definition} Note that for all $m \in q_l-1-\N$ the leading and trailing coefficient of $L_{\epsilon}$ have $\epsilon$-valuation $0$ and all other coefficients of $L_{\epsilon}$ have $\epsilon$-valuation $\geq 0$. Since the $\tilde{u}(m)$ for $m \in q_l-1-\N$ are determined by $L_{\epsilon}$ and the $\tilde{u}(m)$ for $m \in \{q_l-1,q_l-2,\ldots,q_l-n\}$, it follows that {\rm \[ v_{\epsilon,l}(\tilde{u})= {\rm min}\{v_{\epsilon}(\tilde{u}(m)) | m \in \{q_l-1,q_l-2,\ldots,q_l-n\} \} \] } and similarly {\rm \[ v_{\epsilon,r}(\tilde{u})= {\rm min}\{v_{\epsilon}(\tilde{u}(m)) | m \in \{q_r+1,q_r+2,\ldots,q_r+n\} \}. \]} In fact, if $S$ is any set of $n$ consecutive elements of $q_l-1-\N$ then one can apply the same argument and show that $v_{\epsilon,l}(\tilde{u})={\rm min}\{v_{\epsilon}(\tilde{u}(m))| m \in S \}$. Hence, for $\tilde{u} \in V_p(L_{\epsilon})$, $\tilde{u} \neq 0$ \[ v_{\epsilon,l}(\tilde{u}) = \liminf_{m \rightarrow -\infty} v_{\epsilon}(\tilde{u}(m)) \] and \[ v_{\epsilon,r}(\tilde{u}) = \liminf_{m \rightarrow \infty} v_{\epsilon}(\tilde{u}(m)) \] where the two limits are taken over $m \in p$ using the ordering $<$ that was defined on the set $p$. It is easy to compute the valuation growth of $\tilde{u} \in V_p(L_{\epsilon})$ if $L$ has order $n=1$, and one obtains: \begin{lemma} If $L$ is normal and ${\rm order}(L)=1$ then the set $\overline{g}_p(L)$ contains only one element, $\overline{g}_p(L) = \{ g_p(L) \}$. \end{lemma} \begin{lemma} Let $L,N,M \in k[\tau]$ be normal, $L=NM$. Then $\overline{g}_p(M) \subset \overline{g}_p(L)$. \end{lemma} {\bf Proof:} $M$ is a right-hand factor of $L$, so $M_{\epsilon}$ is a right-hand factor of $L_{\epsilon}$, so $V_p(M_{\epsilon})\subset V_p(L_{\epsilon})$ and hence the lemma follows for $p \in \C/Z$. For $p=\infty$ the statement follows directly from the definitions. \eindebewijs Without proof we mention that $\overline{g}_p(N) \subset \overline{g}_p(L)$ as well, and that $\overline{g}_{\infty}(L)=\overline{g}_{\infty}(M) \bigcup \overline{g}_{\infty}(N)$. % The first inclusion can be reduced to the second one by % applying the adjoint (for a definition see \cite{abr_hoeij}). % The adjoint is a 1-1 anti-isomorphism $k[\tau] \rightarrow k[\tau^{-1}]$, % it switches the order of multiplication. \eindebewijs However, if $p$ is finite then examples show that in general the set $\overline{g}_p(L)$ is not determined by $\overline{g}_p(M)$ and $\overline{g}_p(N)$. The two lemmas show that \[ \{ g_p(u) | u \in V(L) \bigcap H^* \} \subset \overline{g}_p(L) \] (recall that $g_p(u)$ for $u \in H^*$ has been defined as $g_p(\tau-r)$ where $r=\tau(u)/u \in k^*$). This inclusion is not always an equality. \subsection{Computing the set of valuation growths} \label{computing_g_p} With $L=a_n \tau^n + \cdots + a_0 \tau^0$, $a_na_0 \neq 0$, $q_l$ and $q_r$ as before, define $u_i: q_l-1-\N \rightarrow \C$ by: for $1 \leq j \leq n$ let $u_i(q_l-j)$ be 1 if $i=j$ and $0$ otherwise. The other values of $u_i$ are determined by the recurrence equation $L(u_i)=0$. Now $u_1,\ldots,u_n$ is a basis of $V_{p,l}(L)$. Similarly we can define a basis $v_1,\ldots,v_n$ of $V_{p,r}(L)$ where $v_i:q_r+1+\N \rightarrow \C$. For each basis element $u_i$ of $V_{p,l}(L)$ we can choose $\tilde{u}_i \in V_p(L_{\epsilon})$ with left valuation $\geq 0$ and $\rho_l(\tilde{u}_i)=u_i$, by setting $\tilde{u}_i(q_l-j)=u_i(q_l-j)$ for $j$ from 1 through $n$. Similarly we can choose $\tilde{v}_i \in V_p(L_{\epsilon})$ with right valuation $\geq 0$ and $\rho_r(\tilde{v}_i)=v_i$. \begin{definition} With notations as above, define the {\em minimum valuation growth} of $L$ at $p$ as \[ g_{p,r}(L) ={\rm min}\{g_{p,\epsilon}(\tilde{u}_i)| 1 \leq i \leq n\} \in \Z. \] Define the {\em maximum valuation growth} as \[ g_{p,l}(L)= {\rm max}\{g_{p,\epsilon}(\tilde{v}_i)| 1 \leq i \leq n\} \in \Z. \] Define the following $\C$-linear maps by their action on the basis elements $u_i$ and $v_i$ \begin{eqnarray*} E_{p,r}: V_{p,l}(L) \rightarrow V_{p,r}(L) & {\rm \ \ \ \ \ \ } & E_{p,r}(u_i)= \rho_r(\tilde{u_i}/\epsilon^{g_{p,r}(L)}) \\ E_{p,l}: V_{p,r}(L) \rightarrow V_{p,l}(L) & {\rm \ \ \ \ \ \ } & E_{p,l}(v_i)= \rho_l(\tilde{v_i} \cdot \epsilon^{g_{p,l}(L)}). \end{eqnarray*} \end{definition} With $\tilde{u}_i$ and $\tilde{v}_i$ as above, every non-zero $\tilde{u} \in V_p(L_{\epsilon})$ can be written as \[ \tilde{u}=\epsilon^{v_{\epsilon,l}(\tilde{u})} \sum_i a_i \tilde{u}_i =\epsilon^{v_{\epsilon,r}(\tilde{u})} \sum_i b_i \tilde{v}_i \] for some $a_i,b_i \in \C(\epsilon)$ with $v_{\epsilon}(a_i) \geq 0$ and $v_{\epsilon}(b_i) \geq 0$. As a consequence \[ g_{p,r}(L)={\rm min}(\overline{g}_p(L)) {\rm \ \ \ and \ \ \ } g_{p,l}(L)={\rm max}(\overline{g}_p(L)). \] If $p \in \C/\Z$ is not singular then $\overline{g}_p(L)=\{0\}$. If $p \in \C/\Z$ is singular and $\overline{g}_p(L)=\{0\}$ then $p$ is called an {\em apparent} singularity. If $\overline{g}_p(L)$ has only 1 element then $p$ is called a {\em semi-apparent} singularity. If $\overline{g}_p(L)$ has more than 1 element then $p$ is called an {\em essential} singularity. Note that the definition of $E_{p,r}$ and $E_{p,l}$ depends on $L$ because $g_{p,r}(L)$ and $g_{p,l}(L)$ depend on $L$. So, if ambiguity could occur, these maps should be denoted as $E_{p,r,L}$ and $E_{p,l,L}$. If $g_{p,\epsilon}(\tilde{u}_i) < g_{p,\epsilon}(\tilde{v}_j)$ then one can verify that \[ \{ g_{p,\epsilon}(\tilde{u}_i + c \epsilon^m \tilde{v}_j)|c \in \C, \ m \in \Z\} = \{ e \in \Z | g_{p,\epsilon}(\tilde{u}_i) \leq e \leq g_{p,\epsilon}(\tilde{v}_j)\} \] and hence the set of valuation growths $\overline{g}_p(L)$ is given by the following formula \[ \overline{g}_p(L)=\{e \in \Z | g_{p,r}(L) \leq e \leq g_{p,l}(L) \} \subset \Z. \] To compute this set we need to use the recurrence relation (the operator $L_{\epsilon})$ to compute the values of the $\tilde{u}_i$ at the points on the right of $q_r$ (recall that $q_r$ is the largest problem point at $p$); we need to compute $\tilde{u}_i(q_r+1),\ldots,\tilde{u}_i(q_r+n)$. And we need to compute the values of the $\tilde{v}_i$ on the left of $q_l$. Then $g_{p,r}(L)$ and $g_{p,l}(L)$ can be determined from the $\epsilon$-valuation of these values. This computation should be done modulo a suitable power of $\epsilon$ in order to reduce intermediate expression swell. We can combine this with modular arithmetic to eliminate expression swell. The $\epsilon$-valuations of these $\tilde{u}_i$ and $\tilde{v}_i$ at the points between $q_l$ and $q_r$ can be used to bound the denominators of rational solutions (this statement is the content of \cite{issac98}). The valuation growth $g_p$ has been defined for (solutions of) operators $L$ of order $1$ (c.f. definition~\ref{def_g_u}) and corresponds to the valuation growth $g_{p,\epsilon}$ of solutions of $L_{\epsilon}$. For higher order $L$, if $u \in V(L)$ is hypergeometric, $g_p(u)$ has been defined as the valuation growth of the corresponding right-hand factor $\tau-\tau(u)/u \in k[\tau]$ of $L$. However, in general $g_p(u)$ can not be defined for every $u \in V(L)$. Because if $g_p(u)$ for $u \in V(L)$ can be defined, and $p$ is an essential singularity, then $g_p(u)$ is either not minimal, or not maximal (or both), so (use any embedding $V \rightarrow V_{p,r}$ and $V \rightarrow V_{p,l})$ we have $u \in {\rm Ker}(E_{p,r})$, or $u \in {\rm Ker}(E_{p,l})$ (or both). This can not hold for all $u \in V(L)$ because a vector space $V(L)$ can not be the union of two vector spaces ${\rm Ker}(E_{p,r})$ and ${\rm Ker}(E_{p,l})$ of lower dimension. Hence one can not define $g_p(u)$ for all $u \in V(L)$ in a way that corresponds to the definition of $g_{p,\epsilon}$. If $L_1$ and $L_2$ are normal operators of order 1, then we have seen that $g(L_1 \miprod L_2)=g(L_1)+g(L_2)$. It is not difficult to prove the following generalization \begin{lemma} Let $L_1,L_2 \in k[\tau]$ be normal, and let ${\rm order}(L_2)=1$. Then $\overline{g}_p(L_1 \miprod L_2) = \{ e+ g_p(L_2) | e \in \overline{g}_p(L_1) \}$ for all $p \in \C/\Z \bigcup \{\infty\}$. \end{lemma} \begin{lemma} \label{imker} If $g_{p,r}(L)=g_{p,l}(L)$ (i.e. $p$ is a semi-apparent singularity) then $E_{p,r}$ and $E_{p,l}$ are each other's inverses. If $g_{p,r}(L) \neq g_{p,l}(L)$ (i.e. $p$ is an essential singularity) then $E_{p,r} \circ E_{p,l} =0$ and $E_{p,l} \circ E_{p,r} =0$, in other words \[ {\rm Im}(E_{p,r}) \subset {\rm Ker}(E_{p,l}) {\rm \ \ \ and \ \ \ } {\rm Im}(E_{p,l}) \subset {\rm Ker}(E_{p,r}). \] \end{lemma} {\bf Proof:} $E_{p,r}(E_{p,l}(v_i))=E_{p,r}(\rho_l(\tilde{v}_i \epsilon^{g_{p,l}(L)})) =\rho_r(\tilde{v}_i \epsilon^{g_{p,l}(L)} / \epsilon^{g_{p,r}(L)}) =\rho_r(\tilde{v}_i \epsilon^s)$ where $s=g_{p,l}(L)-g_{p,r}(L)$. Now $v_{\epsilon,r}(\tilde{v}_i \epsilon^s)=v_{\epsilon,r}(\tilde{v}_i)+s=s$, which is $>0$ if $p$ is an essential singularity and $0$ otherwise. In the former case $\rho_r(\tilde{v}_i \epsilon^s)=0$, and in the latter case $\rho_r(\tilde{v}_i \epsilon^s)=v_i$. The linear map $E_{p,l} \circ E_{p,r}$ can be computed in the same way. \eindebewijs If $p \in \C/\Z$ is not a singularity then $E_{p,l}$ and $E_{p,r}$ are isomorphisms of $G$-modules where $G$ is the {\em difference Galois group} (for a definition see \cite{book}) of $L$. However, at essential singularities the linear maps $E_{p,r}$ and $E_{p,l}$ are in general not $G$-homomorphisms, because at essential singularities the kernels and images are non-trivial even when $L$ is irreducible. \section{Computing hypergeometric solutions} \label{hypergeomsols} Computing hypergeometric solutions is equivalent to computing first order right-hand factors; if $u \in H^*$ is a non-zero hypergeometric solution then $\tau-\tau(u)/u \in k[\tau]$ is a right-hand factor of $L$. The type of $u$ is determined by $g(u)$, so when $g(u)$ is known, an operator $\tau-r$ with the same type can be constructed. By taking the symmetric product with $\tau-1/r$ we get a right-hand factor $\tau-(\tau(u)/u)/r$ which has the trivial type and hence a rational solution. So $u$ can be found by trying all possible values of $g(u)$ and computing rational solutions for each case. This leads to the following algorithm. \\ \noindent {\bf Algorithm hypergeometric solutions} \\ {\bf Input:} $L=a_n \tau^n + \cdots + a_0 \tau^0 \in k[\tau]$ with $a_n \neq 0$, $a_0 \neq 0$ and $n \geq 2$. \\ {\bf Output:} All hypergeometric solutions, parametrized by constants $c_i$. \begin{enumerate} \item Let $S=\{p_1,\ldots,p_m\} \subset \C/\Z \bigcup \{\infty\}$ be the set of singularities. \item ${\rm result}:=\{\}$ \item For all $h=(h_1,\ldots,h_m)$ with $h_i \in \overline{g}_{p_i}(L)$ that satisfy Fuchs' relations do \begin{enumerate} \item Construct $r \in k^*$ such that all singularities of $\tau-r$ are in $S$, and $g_{p_i}(\tau-r)=h_i$. \item Let $b_1,\ldots,b_q \in k$ be a basis of rational solutions of $L \miprod (\tau-1/r)$. \item If $q>0$ then ${\rm result}:={\rm result} \bigcup \{ u \cdot (c_1b_1 + \cdots + c_qb_q) \}$ where $c_i$ are parameters and $u \in H^*$ is a solution of $\tau-r$. \end{enumerate} \item Output: result. \end{enumerate} Step 3a is theorem~\ref{theorem1} and computing $\overline{g}_{p_i}(L)$ is section~\ref{computing_g_p}. Note that we could remove all apparent finite singularities from $S$, that would not change the computation. Furthermore we can compute $r \in k^*$ such that $\{ g_p(\tau-r) \}=\overline{g}_p(L)$ for all semi-apparent singularities $p \in \C/\Z$ and such that $\tau-r$ does not have other finite singularities. Then $L \miprod (\tau-1/r)$ has an apparent singularity at all these $p$, and this way these $p$ can be discarded as well. For $L \in k[\tau]$ the {\em field of definition} is the smallest subfield $C_0$ of $\C$ such that $L \in C_0(x)[\tau]$. This is always a finite extension of $\Q$ and hence not an algebraically closed field. After multiplying by a polynomial we may assume that the coefficients $a_i$ of $L=a_n \tau^n+\cdots+a_0\tau^0$ are in $C_0[x]$. Then the algorithm in \cite{MR94a:39006} computes in the splitting field of $a_na_0$ over $K$. The degree of this field extension can be very high, in which case the computation becomes infeasible. Avoiding large algebraic extensions is the main problem in computing hypergeometric solutions. Results on this are given in~\cite{hendriks} for order 2, where one tries all factors of the discriminant of the defining polynomial of the singularities. If $C_0 = \Q$ then one has to factor in $\Z$ (works fine unless the coefficients are big) but for larger fields this becomes complicated. The algorithm above computes in a splitting field; the field generated by all essential singularities. This is a subfield of the splitting field of $a_na_0$. Since semi-apparent singularities do not contribute to this subfield, it can be much smaller than the splitting field of $a_na_0$, and this makes significant difference. However, although less frequent, the problem of exponentially large algebraic extensions can still occur in the above algorithm, causing the computer to ``run forever'' or run out of memory. So the main problem has been reduced, not yet solved. The introduction of finite singularities is the main result of this paper because it makes it possible to solve this problem. For order $<4$ this is done in section~\ref{improvements} using the maps $E_{p,l}$ and $E_{p,r}$. The higher order case is more technical as there are more cases to distinguish. This will be done later. Another advantage of our algorithm is that the number of cases (the number of loops in step 3) in our algorithm is in general much smaller than (but at most equal to) the number of cases in \cite{MR94a:39006}, where one takes all combinations of all factors of $a_0$ with all factors of $a_n$. If $a_n$ is square-free then the number of factors of $a_n$ is $2^d$ where $d$ is the degree. % Fuchs' relations have been introduced to decrease the number % of loops in our algorithm. Note that these relations could % also be used in the algorithm from % \cite{MR94a:39006}. \section{Avoiding splitting fields.} \label{improvements} When during the computation a hypergeometric solution $u$ is found (equivalently: when a first order right hand factor $\tau-r$ is found where $r =\tau(u)/u \in k^*$), we can write $L=L_2 \cdot (\tau-r)$. Let $M=L \miprod (\tau-1/r) = L_3 \cdot (\tau-1)$ for some $L_3$ with ${\rm order}(L_3)={\rm order}(L)-1$. The non-constant hypergeometric solutions of $M$ can be obtained by computing the hypergeometric solutions of $L_3$ and applying Gosper's algorithm (c.f. \cite{MR58:5497} or \cite{abr_hoeij}). Multiplying the hypergeometric solutions of $M$ by $u$ gives the hypergeometric solutions of $L$. This process is known as {\em reduction of order}. It may speed up the algorithm in the previous section if a hypergeometric solution is found early in the computation, but it is not always an improvement. If all singularities are semi-apparent then the algorithm in the previous section is fast because there are few cases to check in step 3. If $p \in \C/\Z$ is not semi-apparent then in some cases we can use the images and kernels of $E_{p,r}$ and $E_{p,l}$ to find factors or hypergeometric solutions of $L$. For example if $L$ is normal and has order 2 then by lemma~\ref{imker} we have ${\rm Im}(E_{p,r}) = {\rm Ker}(E_{p,l})$ and ${\rm Im}(E_{p,l}) = {\rm Ker}(E_{p,r})$ at every essential singularity $p$. If $u \in H^*$ is a hypergeometric solution of $L$, then either $g_p(u)=g_{p,r}(L)$ or $u \in {\rm Ker}(E_{p,r})$. And either $g_p(u)=g_{p,l}(L)$ or $u \in {\rm Ker}(E_{p,l})$. So $u \in {\rm Ker}(E_{p,r})$ or $u \in {\rm Ker}(E_{p,l})$ (or both). Let $r=\tau(u)/u \in k^*$. If we had bounds on the degrees of the numerator and denominator of $r$ then $r$ can be computed by checking two cases $u \in {\rm Ker}(E_{p,r})$ or $u \in {\rm Ker}(E_{p,l})$. So there are at most two possible $r$. Such bounds can be obtained by a careful study of the algorithm in the previous section. Let $C_p \subset \C$ be the smallest field over which $p$ and $L$ are defined. Then all right-hand factors $\tau-r$ that we find are defined over $C_p$, because ${\rm Ker}(E_{p,r})$ and ${\rm Ker}(E_{p,l})$ are 1-dimensional and are defined over $C_p$. So then $r$ must be an element of $C_p(x)$ for every essential singularity $p$, and we can conclude \begin{theorem} \label{order2} Let $L \in C_0(x)[\tau]$ be an operator of order 2, where $C_0 \subset \C$ and let $C_p=C_0(q)$ if $p=q+ \Z$ for some $q \in \C$. Let $S \subset \C/\Z$ be the set of essential singularities. If $S \neq \emptyset$ then the number of first order monic right-hand factors $\tau-r$ is at most two, and they are elements of $K(x)[\tau]$ where $K = \bigcap_{p \in S} C_p$. \end{theorem} If $S=\emptyset$ then computing the first order right-hand factors is easy. In this case the only algebraic extension needed is the $c \in \C^*$ in $(c,n,d)$ at infinity, which can be at most an extension of degree ${\rm order}(L)=2$. If $S \neq \emptyset$ then we can skip all cases in the algorithm that would lead to an extension larger than $K$. This way computations with exponentially large algebraic extensions are avoided in the algorithm in the case of order 2. A similar result can be obtained for order 3. To compute the hypergeometric solutions efficiently, we first try only those $r$ in step 3a of the algorithm that involve no algebraic extensions. Splitting fields over $C_0$ are not needed for this computation. If no hypergeometric solutions are found this way then we use the lemma and theorem below in order to find all hypergeometric solutions (including the ones that involve algebraic extensions) without having to compute with splitting fields. \begin{lemma} \label{lemma8} Let $L \in C_0(x)[\tau]$ a monic normal operator of order 3. If $L$ has a first order right-hand factor $\tau-r \in k[\tau]$ and no first order right-hand factor in $C_0(x)[\tau]$ then $L$ can be written as $L={\rm LCLM}(\tau-r_1,\tau-r_2,\tau-r_3)$ for some $r_i \in \overline{C_0}(x)$ or as $L=L_1 L_2$ for some $L_1, \ L_2 \in C_0(x)[\partial]$ with ${\rm order}(L_2)=2$. \end{lemma} {\bf Proof}: If $L$ has a first order right-hand factor in $k[\tau]$ then using the algorithm in section~\ref{hypergeomsols} we can find a first order right-hand factor $\tau-r \in \overline{C_0}(x)[\tau]$. Then take $L_2$ as the LCLM of $\tau-r$ and its conjugates over $C_0$. One sees that $L_2$ is invariant under the Galois group of $\overline{C_0}/C_0$ and hence $L_2 \in C_0(x)[\partial]$. If ${\rm order}(L_2)=3$ then the first case holds, otherwise the second case. \eindebewijs In the second case in the lemma we can find $L_1$ by computing those hypergeometric solutions of the adjoint of $L$ (see \cite{abr_hoeij} for a definition) that involve no algebraic extensions of $C_0$. Then to compute the hypergeometric solutions of $L$ we apply theorem~\ref{order2} on $L_2$. The remaining case is that $L$ is an LCLM of three first-order operators in $\overline{C_0}(x)[\tau]$. \begin{theorem} \label{order3} Let $L \in C_0(x)[\tau]$ be a monic normal operator of order 3 which is reducible in $k[\tau]$. Let $p \in \C/\Z$ be an essential singularity. Then $L$ is reducible in $C_p(x)[\tau]$. \end{theorem} {\bf Proof}: We may assume that $L$ is irreducible in $C_0(x)[\tau]$ and reducible in $k[\tau]$. Then lemma~\ref{lemma8} says that $L={\rm LCLM}(\tau-r_1,\tau-r_2,\tau-r_3)$ for some $r_i \in \overline{C_0}(x)$. Let $u_i \in H^*$ be a solution of $\tau-r_i$, for $i \in \{1,2,3\}$. The solution space of ${\rm LCLM}(\tau-r_1,\tau-r_2,\tau-r_3)$ is spanned by the $u_i$, and hence the $u_i$ are linearly independent. For each of the $u_i$, the valuation growth is not minimal (then $u_i \in {\rm Ker}(E_{p,r})$) or not maximal (then $u_i \in {\rm Ker}(E_{p,l})$). The dimension of these kernels is at most 2 (the order minus 1). At least one of the following two cases must hold: at least two $u_i$ do not have minimal valuation growth, or at least two $u_i$ do not have maximal valuation growth. Hence at least one of the the two kernels is spanned by two of the $u_i$. Assume that ${\rm Ker}(E_{p,r})$ is spanned by $u_1,u_2$. Let $M={\rm LCLM}(\tau-r_1,\tau-r_2)$. Then $V_{p,l}(M)= {\rm Ker}(E_{p,r})$, and hence this solution space is defined over the field $C_p$, or equivalently, the Galois group of $\overline{C_0}/C_p$ maps $V_{p,l}(M)$ to itself. Since the monic normal operator $M$ is uniquely determined by its solution space, it follows that $M$ is invariant under this Galois group as well, and hence $L$ has a right-hand factor $M \in C_p(x)[\tau]$ of order 2. Now $L=NM$ for some $N \in C_p(x)[\tau]$ of order $1$. To find a right-hand factor in $C_p(x)[\tau]$ of $L$ of order 1, we can compute those hypergeometric solutions of $L$ that have the same type as $N$. \eindebewijs Note that if there are no essential singularities, then the only algebraic extension needed in the algorithm is the $c$ of the $(c,n,d)$ at the point infinity. This is an algebraic extension of degree $\leq 3$. The consequence of theorems~\ref{order2} and~\ref{order3} is that computing hypergeometric solutions of operators of order $\leq 3$ can be done very efficiently, because either a singularity $p$ is semi-apparent (and can be discarded after a transformation of $L$), or $p$ reduces the algebraic extension of $C_0$ over which solutions have to be searched. For order $\leq 3$ the algebraic extensions we have to compute with will be small because of this. Once we know a field $C$ over which the solutions can be found, then we do not need to use splitting fields anymore, because we can apply the following algorithm. \\ \noindent {\bf Algorithm:} Compute all hypergeometric solutions that are defined over a given field $C \subset \C$. \\ {\bf Input:} $L = \sum_{i=0}^n a_i \tau^i$ where $a_i \in C[x]$ with $a_0$ and $a_n$ non-zero. \\ {\bf Output:} all solutions $u$ of $L$ for which $\tau(u)/u \in C(x)$. \begin{enumerate} \item Let $S$ be the set of irreducible monic factors of $a_0a_n$ in $C[x]$. Whenever $S$ contains two factors $P \neq Q$ for which $P(x)=Q(x+i)$ for some integer $i$ remove either $P$ or $Q$, until there are no more factors in $S$ that are an integer shift of each other. Let $S=\{P_1,\ldots,P_{m-1}\}$ be the set of factors that remains. The singularities are the roots (modulo the integers) of these polynomials and the point at infinity. \item Compute $\overline{g}_{\infty}(L)$ using the $\tau$ and $\delta$ polygon, see section~\ref{infinity}. Remove the elements from $\overline{g}_{\infty}(L)$ that are not defined over $C$. If there are no elements left then then there are no non-zero hypergeometric solutions defined over $C$. \item For each $P_k \in S$ do \begin{enumerate} \item Let $\alpha_k$ be root of $P_k$. This can be done by introducing a new variable $Y$ and letting $C(\alpha_k)=C[Y]/(P_k(Y))$. Now $p_k=\alpha_k+\Z \in \C/\Z$ is a finite singularity of $L$. Compute the roots of $a_0$ and $a_n$ on $p_k$ and determine the smallest and largest problem point $q_l$ and $q_r$ on $p_k$. \item Let $\tilde{u}_i(q_l-j)$ be $1$ if $i=j$ and $0$ if $i\neq j$ for all integers $i,j$ from 1 to $n$, and the same for $\tilde{v}_i(q_r+j)$. \item Letting $\tilde{u}_i$ and $\tilde{v}_i$ be solutions of $L_{\epsilon}$ determines $\tilde{u}_i(q), \tilde{v}_i(q) \in C(\alpha_k,\epsilon)$ for every $q \in p_k$. These values can be computed by applying the recurrence relation given by $L_{\epsilon}$. \item $\overline{g}_{p_k}(L)$ is a set of consecutive integers. Compute the right-valuation of the $\tilde{u}_i$ by computing the smallest $\epsilon$-valuation of $\tilde{u}_i(q_r+j)$ where $j$ runs from 1 through $n$. The smallest right-valuation of the $\tilde{u}_i$ equals the smallest element of $\overline{g}_{p_k}(L)$. Then compute the smallest left-valuation of the $\tilde{v}_i$. Multiply this by $-1$ to obtain the largest element of $\overline{g}_{p_k}(L)$. \end{enumerate} \item Let $p_m=\infty$. For every combination $(e_1,\ldots,e_m)$ with $e_i \in \overline{g}_{p_i}(L)$ that satisfies the Fuchs' relations do \begin{enumerate} \item Now $e_1,\ldots,e_{m-1}$ are integers and that $e_m$ is a 3-tuple. Let $c$ be the first entry of $e_m$. Let $r = c \prod_{i=1}^{m-1} P_i^{e_i}$, so $g_{p_i}(\tau-r)=e_i$ for $i$ from 1 through $m-1$. Note that the fact that the $e_i$ satisfy Fuchs' relations simply means that $g_{\infty}(\tau-r)=e_m$. \item Compute the rational solutions of $L \miprod (\tau-1/r)$. Multiply them by a non-zero solution of $\tau-r$ and return the product as output. Note that to compute rational solutions we first need to bound the denominators of rational solutions; for each point $q$ we need a lower bound for the valuation of these rational solutions at $q$. Such a bound can be obtained from the $\epsilon$-valuation of the $\tilde{u}_i(q)$ and $\tilde{v}_i(q)$. This idea is treated in more detail for the case of systems in \cite{issac98}. \end{enumerate} \end{enumerate} The following remarks are topics for a subsequent paper. % There are a lot % of implementation details and tricks one can use to speed up the % computation. % For example, intermediate results in the % computation of the $\overline{g}_p(L)$ % can also be used to find rational solutions in step 3b; % it is not necessary to compute bounds for the denominators of % rational solutions in every loop. % More important: using similar ideas as in theorems~\ref{order2} % and~\ref{order3} % it is always possible to avoid splitting fields for higher order % operators as well. The set $\overline{g}_p$ can also be defined and computed for systems of equations $\tau(Y)=AY$ where $A \in GL_n(k)$, without having to use cyclic vectors, so our algorithm works for systems as well. In fact the definition for systems when $p$ is finite is less technical than the one for operators given in this paper. Furthermore certain facts, for example that $\overline{g}_p(L)$ depends only on the type of $L$, are easier to prove using systems. A reason for treating only operators in this paper is that the three given theorems easier to prove that way. % Using modular arithmetic it is also possible to construct fast % tests The same methods can also be used to compute solutions that are {\em m-interlacings of hypergeometric sequences} (see \cite{hendriks_singer} for a definition), because the valuation growths are the same and computing bounds for the denominators of interlacings of rational functions also works the same. The methods in this paper can be applied for $q$-difference equations as well if $q$ is not a root of unity. The main difference is that in the $q$-difference case there are two special singularities (0 and infinity) instead of just one, and so the Fuchs' relations will be different. \begin{thebibliography}{1} \bibitem{abr_hoeij} S.A. Abramov, M. van Hoeij. A method for the Integration of Solutions of Ore Equations, {\em ISSAC'97 Proceedings}, p. 172 -- 175, 1997. \bibitem{AbrBarkatou} S.~A.~Abramov, M.A.~Barkatou. Rational Solutions of First Order Linear Difference Systems, {\em to appear in ISSAC'98 Proceedings} (1998). \bibitem{qdif} S.A. Abramov, P. Paule and M. Petkov{\v{s}}ek. $q$-Hypergeometric solutions of $q$-difference equations. {\em Discrete Math} 180:(1-3) 3--22, 1998. \bibitem{MR95k:39004} M.A.~Barkatou, A.~Duval. \newblock Sur les s\'eries formelles solutions d'\'equations aux diff\'erences polynomiales. \newblock {\em Ann. Inst. Fourier (Grenoble)}, 44(2):495--524, 1994. \bibitem{beke} E. Beke. Die Irreduzibilit\"at der homogenen linearen Differentialgleichungen, {\em Math. Ann.} {\bf 45}, p.\ 278-294, 1894. \bibitem{MR96m:34013} M. Bronstein and M. Petkov{\v{s}}ek. \newblock An introduction to pseudo-linear algebra. \newblock {\em Theoret. Comput. Sci.}, 157(1):3--33, 1996. \bibitem{MR86h:12011} A. Duval. \newblock Lemmes de {H}ensel et factorisation formelle pour les op\'erateurs aux diff\'erences. \newblock {\em Funkcial. Ekvac.}, 26(3):349--368, 1983. \bibitem{MR58:5497} Jr. Gosper, R.~William. \newblock Decision procedure for indefinite hypergeometric summation. \newblock {\em Proc. Nat. Acad. Sci. U.S.A.}, 75(1):40--42, 1978. \bibitem{hendriks} P. A. Hendriks. Algebraic aspects of linear differential and difference equations. {\em Ph.D thesis}. Rijksuniversiteit Groningen, 1996. \bibitem{hendriks_singer} P. A. Hendriks, M.F. Singer. Solving Difference Equations in Finite Terms. {\em preprint}. Available from \verb+http://www.math.ncsu.edu/~singer+ \bibitem{global} M. van Hoeij. Factorization of Differential Operators with Rational Functions Coefficients. {\em J. Symbolic Comput.}, 24, 537-561, 1997. \bibitem{issac98} M. van Hoeij. Rational Solutions of Linear Difference Equations. {\em to appear in ISSAC'98 Proceedings}, 1998. Available from \verb+http://www.math.fsu.edu/~hoeij/papers.html+ \bibitem{levelt} A.H.M. Levelt, A. Fahim. Characteristic classes for difference operators. {\em to appear in Compositio Mathematica}. \bibitem{Ore} O.~Ore. The theory of non-commutative polynomials, {\em Ann. Maths.} {\bf 34}, 480 -- 508, 1933. \bibitem{MR94a:39006} M. Petkov{\v{s}}ek. \newblock Hypergeometric solutions of linear recurrences with polynomial coefficients. \newblock {\em J. Symbolic Comput.}, 14(2-3):243--264, 1992. \bibitem{book} M. van der Put, M.F. Singer. Galois Theory of Difference Equations. Lecture Notes in Mathematics, Vol. 1666, Springer-Verlag, ISBN 3-540-63243-3, 1997. \bibitem{testing_reducibility} M.F. Singer. Testing reducibility of linear differential operators: a group theoretic perspective. {\em Applicable Algebra in Engineering, Communication and Computing}, {\bf 7}, 77--104, 1996. \bibitem{Tournier} E. Tournier. Solutions formelles d'\'equations diff\'erentielles, {\em Th\`ese d'Etat, Facult\'e des Sciences de Grenoble}, 1987. \end{thebibliography} \end{document}