\documentclass[11pt]{article}
\usepackage{amsfonts}

\def\nref#1{(see \cite{#1})}
\def\eqref#1{(\ref{#1})}
\def\fref#1{Fig. \ref{#1}}
\newcommand{\D}{\displaystyle}
\newcommand{\lcm}{{\rm lcm }}
\newcommand{\KR}{{\cal K}(x)}
\newcommand{\KP}{{\cal K}[x]}
\newcommand{\K}{{\cal K}}
\newcommand{\1}{{\bf 1}}


%----------------------------------
% Theorem-like structures
%----------------------------------
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{exam}{Example}
\newtheorem{remark}{Remark}
\newenvironment{example}{\begin{exam}\rm}{\end{exam}}
\newenvironment{proof}{\noindent{\sl Proof.}\hspace{0.05in}}{\hfill\qed\par\mbox{}\par}
\newenvironment{problem}{\noindent{\bf Problem:}\hspace{0.05in}\sl}{}
\newcommand{\qed}{\hfill \mbox{$\Box$}}
\newcommand{\dis}{\mbox{dis}}


\input{amssym.def}
\input{amssym}
\newcommand{\ndiv}{\nmid}
\parskip1mm
\textwidth16cm
\textheight22cm
\oddsidemargin0mm
\evensidemargin0mm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{A Note On the Minimality Problem\\
in Indefinite Summation of Rational
Functions}

\author{Roberto Pirastu\thanks{Supported by
 the Commission of the European Communities in the frame
 of the program ``Human Capital and Mobility'',
 contract Nr. ERBCHBICT930501. }\\
\small Research Institute for
Symbolic Computation, J. Kepler University, A-4040 Linz}
\begin{document}
\date{}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Introduction}

Consider a field $\K$ of characteristic zero.
The shift operator $E$ on $\KR$ is defined by
$ Ef(x):=  f(x+1)$ for all $f\in \KR$.
The (forward) difference operator is defined by
$\Delta:=E-\1$, where $\1$  operates identically.
Then the problem of indefinite summation of 
rational functions can be stated as follows.

\begin{problem} 
 Given a proper rational function $f \in \KR$, find 
$h,r\in \KR$ such that
\begin{equation} \label{indsummrest}
		 f=\Delta h + r
\end{equation}
and the denominator of $r$ has minimal 
degree among all such decompositions.
We call the 
pair $(h,r)$ a  solution of the
indefinite summation problem for $f$ and call $r$ a {\bf bound} for $f$.
\end{problem}

Each solution $(h,r)$ in \eqref{indsummrest} corresponds
to the following decomposition
\begin{equation}\label{decompsum}
	g(a,b):= \sum_{k=a}^b f(k) = h(b+1)-h(a) + \sum_{k=a}^b r(k)
\end{equation}
In particular,  a solution of \eqref{indsummrest}
with  remainder $r=0$ provides a  {\em closed
form}  for $g$ as a rational expression in $a$ and $b$,
namely $g(a,b)=h(b+1)-h(a)$.

Several algorithms are known for computing solutions of the
indefinite rational summation problem \nref{Moenck,A75,PauleSat}. 
Note that giving an ``Ansatz'' for the denominators
of $h$ and $r$ reduces equation \eqref{indsummrest} to 
a polynomial equation, which can be solved by coefficient
comparison.

Here we describe such candidates for the denominators of $h$ and $r$
which depend only on the denominator of $f$.
 For a certain class of rational summands $f$ the given
estimates are precise. 

Solutions $(h,r)$ are not uniquely determined by $f$. For instance,
the decompositions
$$
\Delta \left(-\frac14 \frac{2x+1}{x(x+1)}\right) -\frac1{2(x^2+4x+4)} \qquad
\mbox{and}\qquad
\Delta \left(-\frac14 \frac{2x^3+7x^2+5x+2}{x^2(x+1)^2}\right) - \frac1{2x^2}
$$
are different solutions for the same rational summand $f=\frac{1}{x(x+2)^2}$.
As one can see, the degree of the denominator of $h$ can vary considerably 
among  solutions. 
For this reason we are interested
in  solutions $(h,r)$ with both $h$ and $r$ of
minimal degree in the denominator. Our observations prove that
the modification of Abramow's algorithm proposed in
\cite{Pirastu,PirastuMTN} produces such {\em minimal} 
solutions for a certain class
of rational summands.



In the following we make use of known results due to 
Abramow and Paule \nref{A75,PauleSat},
to which we refer for an extensive treatment of the
subject.



We say that two polynomials 
$p_1$ and $p_2$ are {\em shift equivalent} if 
$p_1=E^kp_2$ for some integer $k$. In this case
we write $p_1\sim p_2$. Consider, for a polynomial 
$p\in\KP$, the complete factorization (over $\K$)
$p=\alpha p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$, where
all $p_i$ are irreducible and monic and $e_1\cdots e_m\neq 0$,
$\alpha\in\K$. 
Then an equivalence class of the set
of irreducible factors $\{p_1,\dots ,p_m\}$ of $p$ 
under the relation $\sim$
is called a {\em shift class} of $p$. A factor
$\tilde{p}=p_{i_1}^{e_{i_1}}\cdots p_{i_l}^{e_{i_l}}$
of $p$ is called a {\em shift component} of $p$ if
the set $\{ p_{i_1},\dots , p_{i_l}\}$ is 
a shift class of $p$.


\begin{exam}\label{ex1} Consider the polynomial $p\in Q[x]$ given
by the following factorization
$$
	p(x) = (x^2+3)(x^2+2x+4)x(x+1)^2(x+3)(x+5)^2
$$
then the set $\{ x,x+1,x+3,x+5\}$ is a shift class of $p$
and $\tilde{p}=x(x+1)^2(x+3)(x+5)^2$ is the
corresponding shift component.
\end{exam}

Define on the polynomials in a shift class the order
$<$ by: $q<q'$ if there exists a positive integer $k$
such that $E^kq=q'$.
We can represent graphically the shift structure of a
shift class. For instance Fig. \ref{exshift} represents
the situation for $\tilde{p}$ of Example \ref{ex1}.

\begin{figure}[h]\begin{center}
\setlength{\unitlength}{0.007in}%
\begin{picture}(243,60)(102,570)
\thicklines
\put(135,570){\framebox(30,30){}}
\put(165,570){\framebox(30,30){}}
\put(102,570){\line( 1, 0){243}}
\put(225,570){\framebox(30,30){}}
\put(165,600){\framebox(30,30){}}
\put(285,570){\framebox(30,30){}}
\put(285,600){\framebox(30,30){}}
\end{picture}
\caption{Shift structure of $x(x+1)^2(x+3)(x+5)^2$}
\label{exshift}
\end{center}
\end{figure}

We draw $d$ squares at the $i$-th position on a line 
when the polynomial $E^iq_0$ arises with multiplicity
$d$ as a factor of $\tilde{p}$, where $q_0$ denotes the smallest
polynomial w.r.t. the order $<$ in the shift class.  

\begin{definition}
The dispersion of a polynomial $p$ is the maximal integer
distance between roots of $p$ and is denoted by $\dis(p)$.
\end{definition}

For a proper rational function given by a {\em reduced representation} 
$f=p/q$, i.e. $p$ and $q$ are relatively prime
polynomials, we define $\dis(f)=\dis(q)$.
In Example \ref{ex1} we have $\dis(p)=5$, viz. the maximal
distance between  stacks.

\begin{lemma}
For $f\in\KR$ let  $ h, r\in\KR$ be such  that
$f=\Delta h +r $ holds. Then $r$ is a bound for 
$f$ if and only if $\dis(r)=0$.
\end{lemma} 

This means that the problem of indefinite summation
 is solved  for
decompositions $f=\Delta h +r $ where $\dis(r)=0$, i.e. 
where each shift component of the denominator of $r$ 
has only one stack of boxes in the corresponding diagram.

 As we saw, solutions of the indefinite summation are not
uniquely determined.  In the next theorem,
due to Paule,  uniqueness {\em up
to integer shifts} of the denominator of the remainders is stated.

\begin{theorem}\label{shiftuniqueness}
Let $r,r'\in\KR$ be bounds for $f\in\KR$, given by
the reduced representations
$r=p/q,r'=p'/q'$. If $q=q_0^{e_0}\cdots q_m^{e_m}$ is
the complete factorization of $q$ over $\K$, then
$q'=(E^{l_0}q_0^{e_0})\cdots (E^{l_m}q_m^{e_m})$
for some integers $l_0,\dots,l_m$.
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Shift-Structure of the Denominator of $\Delta h$}

In the next section we will discuss the shift-structure of the
denominators of
$(h,r)$ in equation \eqref{indsummrest}.
In anticipation of this,  we will now explicitly make some remarks on
 the denominator of the rational function $\Delta h$ for a
given $h$.

In the following let $h\in \KR$ be given by a 
reduced representation $h=\gamma/\delta$. Then we have

\begin{equation} \label{deltah}
	\Delta h = E\frac{\gamma}{\delta} - \frac{\gamma}{\delta}
 		=\frac{\frac{\D
	\frac{\delta}{\tau}E\gamma - \gamma\frac{E\delta}{\D\tau}}{\D\tau_0}}
	{\D\frac{\delta E\delta}{\D\tau\tau_0}}
	= \frac{\frac{\D
	\frac{\delta}{\tau}E\gamma - \gamma\frac{E\delta}{\D\tau}}{\D\tau_0}}
	{\D\frac{\lcm(\delta, E\delta)}{\D\tau_0}}
\end{equation}
 where
$\tau = \gcd(\delta,E\delta)$ and 
$\tau_0 = \gcd(\frac{\delta}{\tau}E\gamma - \gamma\frac{E\delta}{\D\tau}, \lcm(\delta,E\delta))$ and the right hand side is in reduced form.

\begin{remark} \label{taudivgcd}
In  equation \eqref{deltah} we have
$
	\tau_0 | \tau  
$.
\end{remark}

\begin{proof}
 We know $\tau_0 | \delta E\delta$. Assume now
that there exists a non trivial factor $\tau_1$ of $\tau_0$ such  that  
$\tau_1|\delta$ and $\tau_1\ndiv E\delta$.
Then $\tau_1 |\frac{\delta}{\tau}$ and
$\tau_1 \ndiv \frac{E\delta}{\tau}$. This is a contradiction
to \eqref{deltah}, for 
$\tau_0 | (\frac{\delta}{\tau}E\gamma - \gamma\frac{E\delta}{\tau})$
must hold and $\gamma, \delta$ are relatively prime. 
The case $\tau_1|E\delta$ and $\tau_1\ndiv \delta$ is
analogous.
\end{proof}

From this remark one easily obtains the following property.

\begin{lemma} \label{endDeltah}
	Each shift-component $\pi^{m_0}\cdots (E^{l-1}\pi)^{m_{l-1}}$
of length $l$ in $\delta$ corresponds to a shift-component
$\pi^{m^\prime_0}\cdots (E^{l}\pi)^{m^\prime_{l}}$
of length $l+1$ in the denominator of $\Delta h$. Furthermore
$m_0=m^\prime_0$ and $m_{l-1}=m^\prime_{l}$ holds.
\end{lemma}

\begin{proof} 
  Consider a shift-component of $\delta$, viz.
$
	\pi^{m_0}(E\pi)^{m_1}\cdots (E^{l-1}\pi)^{m_{l-1}} 
$
for some irreducible polynomial $\pi$ and non-negative
integers $m_0,\dots, m_{l-1}$ with $m_0m_{l-1}\neq 0$.
Then obviously 
$
	(E\pi)^{m_0}(E^2\pi)^{m_1}\cdots (E^{l}\pi)^{m_{l-1}}
$
is a shift-component of $E\delta$ and
$$
(E\pi)^{\min (m_0,m_1)}(E^2\pi)^{\min (m_1,m_2)}\cdots 
		(E^{l-1}\pi)^{\min (m_{l-2},m_{l-1})} 
$$
is a shift-component of $\gcd (\delta, E\delta)$, while
$$
	\pi^{m_0} (E\pi)^{\max (m_0,m_1)} \cdots 
		(E^{l-1}\pi)^{\max(m_{l-2},m_{l-1})}(E^{l}\pi)^{m_{l-1}} 		
$$
is a shift-component of $\lcm (\delta, E\delta)$.
From Remark \ref{taudivgcd} we know $\tau_0|\gcd(\delta,E\delta)$,
so $\pi\ndiv\tau_0$ and $E^{l}\pi\ndiv\tau_0$.
This implies the statement.
\end{proof}

Now we give a more precise description of the
factors of $\tau_0$.

\begin{lemma} \label{boundtau}
For all non-trivial factors $\sigma$ of $\gcd (\delta, E\delta)$ we have:
$
	\sigma | \tau_0 \Rightarrow \sigma \ndiv \frac{\delta}{\tau}
	\quad\mbox{and}\quad \sigma \ndiv \frac{E\delta}\tau
$
\end{lemma}

\begin{proof}
 Assume $\sigma | \tau_0$
and $ \sigma | \frac{\delta}{\tau}$. Notice that then
$\sigma \ndiv \frac{E\delta}{\tau}$ immediately follows.
From $\sigma | \tau_0$ we know $\sigma | \frac{\delta}{\tau}E\gamma - 
\gamma\frac{E\delta}{\D\tau}$, so $\sigma | \gamma\frac{E\delta}{\tau}$. 
As $\delta$ and
$\gamma$ are relatively prime, we have $\sigma | \frac{E\delta}{\tau}$.
This implies $\gcd(\frac{E\delta}{\tau},\frac{\delta}{\tau})\neq 1$,
a contradiction to $\tau=\gcd(\delta, E\delta)$. 
Similarly for the assumption $\delta|\tau_0$ 
and $\sigma | \frac{E\delta}{\tau}$.
\end{proof}

 
In other words, if $\pi$
is a factor of $\tau_0$, then $\pi$ and $E^{-1}\pi$ arise
with same multiplicity in $\delta$.
This fact implies that the reduced denominator
of $\Delta h$ might differ from $\lcm (\delta, E\delta)$
only at those places where we have {\em repeated multiplicities}
in the corresponding shift-component of $\delta$.


\begin{example}
Consider a rational function, whose denominator has
the shift-structure as represented in the left part of \fref{extau}.
Then the  shift-structure of $\tau_0$ will be contained in the
diagram in the right part of \fref{extau}.


\begin{figure}[h]\begin{center}
\setlength{\unitlength}{0.007in}%
\begin{picture}(510,66)(45,519)
\thicklines
\put( 60,525){\framebox(30,30){}}
\put( 60,555){\framebox(30,30){}}
\put( 90,555){\framebox(30,30){}}
\put( 90,525){\framebox(30,30){}}
\put(120,525){\framebox(30,30){}}
\put(180,525){\framebox(30,30){}}
\put( 45,525){\line( 1, 0){240}}
\put(210,525){\framebox(30,30){}}
\put(480,525){\framebox(30,30){}}
\put(315,525){\line( 1, 0){240}}
\put(360,555){\framebox(30,30){}}
\put(360,525){\framebox(30,30){}}
\put(330,525){\line( 0,-1){  6}}
\put( 60,525){\line( 0,-1){  6}}
\end{picture}
\caption{{\em Upper bound} for $\tau_0$}
\label{extau}
\end{center}
\end{figure}

\end{example}

  Let us define a particular kind of shift structure
which will play an important role in the following section.


\begin{definition} \label{safe}
Let the shift structure of the polynomial $q$ be
given by one shift component
$$
	q=\pi^{m_0}(E\pi)^{m_1}\cdots (E^l\pi)^{m_l}
$$
where $l>0$ and $m_0m_l>0$. We call
such a shift structure {\bf safe} if
for all $0\le i < j \le l$ such  that $m_i=m_j$ 
one of the following conditions holds
\begin{enumerate}
\item  $i=0$ and $j=l$
\item  $\exists k : i<k<j $ and $m_k > m_i$
\item  $\exists k_1, k_2 : k_1<i<j<k_2$ and $m_{k_1}>m_i$ and $m_{k_2}>m_j$
\end{enumerate}
\end{definition}

This means that if two stacks in the shift structure have the
same number of boxes, then there must be an higher stack
between them or they have to be enclosed between two
higher stacks (or they are the endpoints).
The definition naturally generalizes
to polynomials with several shift components, i.e. each
shift component is supposed to be safe.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The $j$-Shift-Saturation}

In order to say more about the shift structure of the
denominator polynomials of the solutions, we need the following
definition.

\begin{definition}
Let $q\in\KP$ be given by one shift
component
$
	q=\pi^{m_0}(E\pi)^{m_1}\cdots (E^l\pi)^{m_l}
$.
For all nonnegative integers $j\le l$ we  call 
the polynomial
$$
	ShiftSat_j(q) := \pi^{t_0}(E\pi)^{t_1}\cdots
		\cdots (E^{l-1}\pi)^{t_{l-1}}
$$
$j$-shift-saturation of $q$, where 
$	t_i = \max\{m_0,\dots, m_i\}$ for $i=0,\dots,j$
and
$	t_i = \max\{m_{i+1},\dots, m_l\}$ for $i= j,\dots,l-1$.
\end{definition}

The definition can be extended to $j<0$ or $j>l$ assuming
$m_i=0$ for all $i<0$ and $i>l$.

One can visualize the last definition as follows. Fix the
$j$-th stack in the diagram corresponding
to the shift structure of the polynomial, then do a saturation from
the left of the stacks left of $j$ and a saturation
from the right of the stack right of $j$. After this,
one simply erases the $j$-th stack and shifts the right 
boxes one step to the left. 

In the following theorem the importance of the $ShiftSat_j(q)$
for our problem is explained. 




\begin{theorem}\label{mainthing}
Let $f=p/q\in\KR$ be  such  that
the shift structure of $q$ consists of a unique shift component 
$
	q=\pi^{m_0}(E\pi)^{m_1}\cdots (E^l\pi)^{m_l}
$
with $m_0m_l\not=0$ and $l>0$.
Then for all integers $j$
there exist solutions $h=\gamma/\delta$, $r=\varepsilon/\eta$
of 
$
	f = \Delta h + r
$
such  that 
$$\delta = Shift_j(q)\qquad\mbox{ and }\qquad \eta = E^j\pi^m $$
holds, where $m=\max\{m_0,\dots,m_l\}$.
Furthermore, if the shift structure of $q$ is safe, then
$\gamma/\delta$ is already a reduced representation.
\end{theorem}



\begin{proof}  The existence
of a solution for $\eta=(E^l\pi)^m$ is consequence
of Theorem 3 in \cite{PauleSat}. Consider now the 
decomposition
$$
	\frac{\varepsilon}{(E^l\pi)^m} =
		-\frac{E\varepsilon}{(E^{l+1}\pi)^m} + \frac{\varepsilon}{(E^l\pi)^m} + \frac{E\varepsilon}{(E^{l+1}\pi)^m} 
$$

This means that  also $h' = h -r$ and $r'=Er$ form  a solution to the
indefinite summation problem, so a solution with $\eta=(E^j\pi)^m$ exists
for all $j$ (and with Theorem \ref{shiftuniqueness} all
possible $\eta$ have this form).

Let $(h,r)$ be a solution with $\eta=(E^j\pi)^m$ for a 
certain $j$.  For simplicity we consider only
$0<j<l$, but the proof can be easily extended to the
remaining cases.
As a consequence  of Lemma \ref{endDeltah} we know
that the denominator $\delta$ of the rational
part consists of a class of length $l-1$, starting with
the same factor as $q$, i.e.
$$
	\delta = \pi^{d_0}(E\pi)^{d_1}\cdots (E^{l-1}\pi)^{d_{l-1}}
$$
and $d_0=m_0$.
We now consider  the multiplicities of  the factors 
$E\pi, E^2\pi,\dots, E^{j-1}\pi$ of $\delta$.
The multiplicity of $E\pi$ in $E\delta$ is $d_0=m_0$, while the
multiplicity in $q$ is $m_1$. 
One of the following must hold.
\begin{enumerate}
\item  $m_1<d_0$. From the  considerations 
after Remark \ref{boundtau} this can happen only if we
have repeated multiplicities, so $d_1=d_0$ must hold.
\item $m_1 > d_0$.  This means that $d_1=m_1$, for this
is the only way to increase the multiplicity.
\item $m_1=d_0$. This may happen only if $d_1\le d_0$. 
\end{enumerate}
In the example in Fig. \ref{satur} we have $d_0=m_0=1$ and
$m_1=2$, so it follows that $d_1=2$.
In any case we have $d_1\le\max\{ d_0,m_1\}=\max\{m_0,m_1\}$.
These comparisons go step by step until we reach the $j-th$ position.
From this follows that for all $0\le k<j$ it holds 
$d_k\le \max\{m_{0},\dots,m_{k}\}$.



Now consider the right endpoint of the class. 
Similarly $d_{l-1}=m_l$, as
$E^l\pi$ does not arise as factor of $\delta$. 
Now we have to compare the $(l-1)$-st column, i.e. $d_{l-2}, d_{l_1}$
and $m_{l-1}$. The only possible cases are  
\begin{enumerate}
\item  $m_{l-1}<d_{l-2}$. Again, after Remark \ref{boundtau} we need the
same multiplicity of $E^{l-1}\pi$ in $E\delta$, so we have $d_{l-2}=d_{l-1}$.
\item $m_{l-1} > d_{l-2}$. This implies that $d_{l-2}=m_{l-1}$
\item $m_{l-1}=d_{l-2}$. This means that $d_{l-2}\le d_{l-1}$.
\end{enumerate}
In the example in Fig. \ref{satur} we have $d_5=m_5=1$ and
$m_4=0$, so it follows that $d_4=1$.
Again we can iterate until the multiplicity $d_j$ is
determined. For all $j\le k<l$,  $d_k\le \max\{m_{k+1},\dots,m_{l-1}\}$ holds.


\begin{figure}[h]\begin{center}
\begin{center}
\setlength{\unitlength}{0.007in}%
\begin{picture}(270,270)(120,405)
\thicklines
\put(135,525){\line( 1, 0){240}}
\put(135,435){\line( 1, 0){255}}
\put(150,435){\framebox(30,30){}}
\put(180,435){\framebox(30,30){}}
\put(180,465){\framebox(30,30){}}
\put(240,435){\framebox(30,30){}}
\put(270,435){\framebox(30,30){}}
\put(330,435){\framebox(0,0){}}
\put(330,435){\framebox(30,30){}}
\put(150,525){\framebox(30,30){}}
\put(180,615){\framebox(30,30){}}
\put(180,525){\framebox(30,30){}}
\put(180,555){\framebox(30,30){}}
\put(210,615){\framebox(30,30){}}
\put(210,645){\framebox(30,30){}}
\put(210,525){\framebox(30,30){}}
\put(210,555){\framebox(30,30){}}
\put(240,615){\framebox(30,30){}}
\put(240,525){\framebox(30,30){}}
\put(330,615){\framebox(30,30){}}
\put(300,525){\framebox(30,30){}}
\put(135,615){\line( 1, 0){240}}
\put(300,615){\framebox(30,30){}}
\put(270,420){\makebox(0,0)[lb]{\smash{$j$}}}
\put(240,465){\framebox(30,30){}}
\put(270,645){\framebox(0,0){}}
\put(270,615){\framebox(30,30){}}
\put(270,525){\framebox(30,30){}}
\put(255,405){\vector( 0, 1){ 30}}
\put(240,645){\framebox(30,30){}}
\put(165,570){\vector( 2, 3){ 30}}
\put(195,615){\vector( 0,-1){ 30}}
\put(195,585){\vector( 1, 1){ 30}}
\put(165,480){\vector( 0, 1){ 30}}
\put(225,615){\vector( 0,-1){ 30}}
\put(225,585){\vector( 1, 1){ 30}}
\put(345,480){\vector( 0, 1){120}}
\put(345,615){\vector(-1,-2){ 30}}
\put(315,555){\vector( 0, 1){ 60}}
\put(315,615){\vector(-1,-2){ 30}}
\put(285,555){\vector( 0, 1){ 60}}
\put(285,615){\vector(-1,-2){ 30}}
\put(120,645){\makebox(0,0)[lb]{\smash{$E\delta$}}}
\put(120,555){\makebox(0,0)[lb]{\smash{$\delta$}}}
\put(120,465){\makebox(0,0)[lb]{\smash{$q$}}}
\end{picture}
\end{center}
\caption{ Determining $\delta$}
\label{satur}
\end{center}
\end{figure}

The steps on the multiplicities can be explained as follows.
Going from left to the right we always take  the maximal 
multiplicity ariseng so far. Similarly from the right to left.
So $\delta$ is a divisor of the $j$-shift-saturation of $q$.
On the other side, two of the cases above give no freedom of choice (the
first and the second). One can easily see that if the denominator
of $f$ has a safe shift structure
the third case never arises for any choice of $j$. 
For such $f$ the rational part $\gamma/\delta$ is already reduced.

In fact, the third case arises only when in $q$ two multiplicities
with same value arise as ``maxima'' in the saturation.
In other words, in order to have say $m_{k}=d_{k-1}$ 
for a $k<j$ there must be $m_{k+i}=m_k$ for some positive $i$
but no $m_{k+h} > m_k$ with $h>0$. Such a structure is unsafe.
\end{proof}

The fact that for safe shift structures 
 the denominator $\delta$ of the rational part $h$ is 
precisely $ShiftSat_j(q)$  allows
us to compute a solution, where also $\delta$ has minimal degree. It is
sufficient to choose $j$ such  that the corresponding
$j$-shift-saturation is minimal in the degree, i.e.
take $j$  where
the maximal multiplicity arises. 


\section{Concluding Remarks}

 In this note we discussed the shift structure
of the denominators of solutions $h,r\in\KR$ to
the problem of indefinite rational summation
for a given $f\in\KR$. 

In Theorem \ref{mainthing} we gave polynomials
which were multiples of the denominators of $h$ and
$r$, respectively. We proved that for a certain class
of summands the given estimates are precise.
 This description depends only on the structure of the denominator
of the summand $f$  and it is not reasonable to expect
lower estimates without considering the numerator of the
summand. 

Provided  $ShiftSat_j(q)$ can be computed by
some effective algorithm,  Theorem \ref{mainthing}
leads to an algorithmic solution of the problem.
In fact, knowing the denominators of $h$ and $r$ corresponds
to reducing equation \eqref{indsummrest} to a polynomial
equation, which can be solved by coefficient comparison.

In addition, our observations prove that the modification
of Abramow's algorithm \nref{A75} that we proposed in
\cite{Pirastu,PirastuMTN} often yields a solution where both
$h$ and $r$ are minimal in the degree of the denominator.







\bibliography{plain}
\begin{thebibliography}{10}

\bibitem{A75} S. A. Abramow, {\em The Rational Component of The 
Solution of a First-Order Linear Recurrence Relation with a Rational
Right Side}, Zh. vychisl. Mat. mat. fis., 15, N. 4, 1035-1039, 1975

\bibitem{Moenck} R. Moenck, {\em On computing closed forms for summations}, Proceedings of MACSYMA users' conference, Berkley, pp. 225-236, 1977

\bibitem{PauleSat} P. Paule, {\em Greatest Factorial Factorization and Symbolic Summation I}, RISC-Linz 
Report Series 93-02, J. Kepler University, Linz, 1993, {\em submitted to J. Symb. Comp.} 

%\bibitem{PPS} P. Paule, R. Pirastu, V. Strehl, {\em Rational Summation Revisited}, manuscript in preparation

\bibitem{Pirastu} R. Pirastu, {\em Algorithmen zur Summation rationaler Funktionen}, {\em (Algorithms for
Summation of Rational
 Functions, in german)}, Diploma Thesis, Univ. Erlangen-N\"urnberg, 1992

\bibitem{PirastuMTN} R. Pirastu, {\em Algorithms for Indefinite
Summation of Rational Functions in Maple}, submitted to 
The Maple Technical Newsletter


\end{thebibliography}

\end{document}
