  
%qsharpZ.tex: `A Sharp Upper Bound for the Order of The Recurrence
%Outputted by Zeilberger's Algorithm'
%%a Plain TeX file by Mohamud Mohammed and Doron Zeilberger (xx pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%end macros
 
\bf
\centerline
{
A Sharp Upper Bound for the Order of The Recurrence
Outputted by Zeilberger's Algorithm
\footnote{$^1$}
{\eightrm  \raggedright
Aug. 5, 2004. This replaces an earlier version of June 3, 2004 .
Supported in part by the NSF.
}
}
\rm
\bigskip
\centerline{ 
{\it 
Mohamud MOHAMMED}
\footnote{$^2$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
{\eighttt mohamudm at math dot rutgers dot edu} , 
{\eighttt http://www.math.rutgers.edu/\Tilde mohamudm/.}
}
and
{\it Doron ZEILBERGER}\footnote{$^3$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg at math dot rutgers dot edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
} 
}


{\bf Notation}: $q$ is an indeterminate (that commutes with
everything). In this paper only, $[a]!$ is short for $(1-q) \dots (1-q^a)$,
and $[a]_k$ is short for $(1-q^a)(1-q^{a+1}) \dots (1-q^{a+k-1})$.
The {\it ground field} is $Q(q)$.
The dependence on $q$ is always understood.


{\bf q-Theorem.} Let
$$
F(n,k)=POL(q^n,q^k) \cdot H(n,k)  \quad,
\eqno(qProperHypergeometric)
$$
where $POL(q^n,q^k)$ is a Laurent polynomial in $(q^n,q^k)$, and 
$$
H(n,k)=
{
{\prod_{j=1}^{A} [a'_j n + a_j k + a''_j]!
\,\, \prod_{j=1}^{B} [b'_j n - b_j k + b''_j]!}
\over
{\prod_{j=1}^{C} [c'_j n + c_j k + c''_j]!
\,\, \prod_{j=1}^{D} [d'_j n - d_j k + d''_j]!}
}q^{J k(k-1)/2} z^k \quad,
\eqno(qPureHypergeometric)
$$
where the 
$a_j,a'_j \,\, (1 \leq j \leq A) \,\,$,
$\,\, b_j,b'_j \,\,(1 \leq j \leq B) \,\, $,
$\,\, c_j,c'_j \,\, (1 \leq j \leq C) \,\, $,
$d_j,d'_j \,\, (1 \leq j \leq D)$
are {\it non-negative integers}, and  $z$, 
$a''_j \,\, (1 \leq j \leq A) \,\,$,
$b''_j \,\, (1 \leq j \leq B) \,\,$,
$c''_j \,\, (1 \leq j \leq C) \,\,$,
$d''_j \,\, (1 \leq j \leq D) \,\,$ are 
{\it indeterminates}, and $J$ is an integer.
We also assume that the factorization
in $(ProperHypergeometric)$ is {\it maximal}, i.e. $POL(q^n,q^k)$ is
as large as possible. This entails that the 
difference between any of the affine-linear expressions at the top
and any of those at the bottom, is never a non-negative integer.
Also let
$$
L =
\max \left ( \,\,
J+\sum_{j=1}^{A} {a_j}^2 \, \, , \,  \,
\sum_{j=1}^{C} {c_j}^2  \,\, \right )
+
\max \left ( \,\,
-J + \sum_{j=1}^{D} {d_j}^2 \, \, , \, \,
\sum_{j=1}^{B} {b_j}^2 \,\, \right ) \quad.
\eqno(qZBound)
$$
There exist polynomials in $q^n$, $e_0(q^n), \dots, e_L(q^n)$,
{\it not all zero}, and a rational function $R(q^n,q^k)$ such
that $G(n,k):=R(q^n,q^k)F(n,k)$ satisfies
$$
\sum_{i=0}^L e_i(q^n)F(n+i,k)=G(n,k+1)-G(n,k) \quad.
\eqno(qZpair)
$$

{\bf Proof}: Let
$$
\overline{H}(n,k)=
{
{\prod_{j=1}^{A} [a'_j n + a_j k + a''_j]!
\,\, \prod_{j=1}^{B} [b'_j n - b_j k + b''_j]!}
\over
{\prod_{j=1}^{C} [c'_j n + c_j k + c''_j+c'_j L]!
\,\, \prod_{j=1}^{D} [d'_j n - d_j k + d''_j+d'_jL]!}}
q^{J k(k-1)/2} z^k  \quad,
$$
$$
f(k)=
z q^{Jk} \prod_{j=1}^{A} [a'_j n +a_jk+a''_j+1]_{a_j}
\prod_{j=1}^{D} [d'_j n -d_jk+d''_j+d'_jL-d_j+1]_{d_j} \quad,
$$
and
$$
g(k)=
 \prod_{j=1}^{B} [b'_j n -b_jk+b''_j-b_j+1]_{b_j}
\prod_{j=1}^{C} [c'_j n +c_jk+c''_j+c'_jL+1]_{c_j} \quad.
$$
Note that $\overline{H}(n,k+1)/\overline{H}(n,k)=f(k)/g(k)$.
Write
$$
G(n,k)=g(k-1) X(k) \overline{H} (n,k) \quad.
$$
Substituting into $(Zpair)$ and dividing both sides by
$\overline{H}(n,k)$, shows that it is equivalent to
$$
f(k)X(k+1)-g(k-1)X(k)-h(q^k)=0 \quad ,
\eqno(qGosper)
$$
where 
$$
h(q^k):=
\sum_{i=0}^{L} e_i(n) POL(q^{n}q^{i},q^k) 
\cdot {{H(n+i,k)}\over {\overline{H} (n,k)}}
\quad .
$$
Note that $h(q^k)$ is a {\it Laurent polynomial} (in $q^k$) since
$$
{{H(n+i,k)}\over {\overline{H} (n,k)}}=
$$
$$
\prod_{j=1}^{A} [a'_j n +a_jk+a''_j+1]_{ia'_j}
\prod_{j=1}^{B} [b'_j n -b_jk+b''_j+1]_{ib'_j} 
\prod_{j=1}^{C} [c'_j n +c_jk+c''_j+ic'_j+1]_{(L-i)c'_j}
\prod_{j=1}^{D} [d'_j n -d_jk+d''_j+id'_j+1]_{(L-i)d'_j} \quad .
$$
Let
$$
M_1:=-ldeg(h)-max(-ldeg(f),-ldeg(g)) \quad \quad , \quad \quad
M_2:=deg(h)-max(deg(f),deg(g)) \quad.
$$
We claim that $(qGosper)$ can always be solved (non-trivially)
with $X(k)$ a Laurent polynomial of $q^k$ of low-degree $-M_1$ and
degree $M_2$.
Writing
$$
X(k)=\sum_{i=-M_1}^{M_2} x_i(n) (q^k)^i \quad,
$$
substituting into $(qGosper)$, and 
setting all the coefficients to $0$, yields
$-ldeg(h)+deg(h)+1$ {\it homogeneous} linear equations for the
$M_1+M_2+L+2$ unknowns
$e_0(n), \dots, e_L(n)$, and $x_{-M_1}(n), \dots, x_{M_2}(n)$. For
such a {\it not-all-zero} solution to exist, we need
$\#\, unknowns - \#\, equations -1 \geq 0 $,
i.e. $(M_1+M_2+L+2)- (-ldeg(h)+deg(h)+1)-1 \geq 0$, i.e.
$L \geq max(deg(f),deg(g))+max(-ldeg(f),-ldeg(g))$. 
But
$$
deg(f)=J+\sum_{j=1}^{A} {a_j}^2 \quad , \quad
-ldeg(f)=-J+ \sum_{j=1}^{D} d_j \quad , \quad 
deg(g)= \sum_{j=1}^{C} {c_j}^2 \quad , \quad
-ldeg(g)= \sum_{j=1}^{B} {b_j}^2 \quad.
$$
This concludes the proof {\it except} that we did not rule out
the possibility of $e_0(n), \dots, e_L(n)$ being all zero
(all we are guaranteed, so far, is that it is not possible for 
{\it all} of $e_0(n), \dots, e_L(n)$, 
{\it and} $x_0(n), \dots, x_M(n)$  to be zero).
But if all the $e_i(n)$'s are zeros, then $h(k)$ is zero
and $(Gosper)$ becomes
$$
{{X(k+1)} \over  {X(k)}}=
{{g(k-1)} \over  {f(k)}} \quad .
$$
Since $X(k)$ is a Laurent polynomial in $q^k$, it means that the roots
of $f(k)=0$ differ from the roots of $g(k-1)=0$ by {\it fixed}
non-negative integers, which is not possible because of the
maximality hypothesis about $POL(q^n,q^k)$. Note that
the maximality hypothesis always holds, automatically, whenever
we have the {\it generic} situation with the $a''_j ,b''_j, c''_j, d''_j$
arbitrary {\it symbols}.
\halmos


\end








