

%ansatzII.tex: The Holonomic Ansatz II. Foundations
%%a Plain TeX file by 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}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
The HOLONOMIC ANSATZ
}
\centerline
{II. 
Automatic DISCOVERY(!) And PROOF(!!) of Holonomic Determinant Evaluations}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\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/.}
First version: Feb. 14, 2006.
This version: Feb. 23, 2006.
Accompanied by the Maple package DET available
from {\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/DET} .
Supported in part by the NSF.
} 
}

{\bf Prerequisites}

I assume that readers have read [Z1].


{\bf Experimental Mathematics: 
From Computer-Assisted to Computer-Generated Mathematics}

In a wonderful essay[W] on Experimental Mathematics, Herb Wilf 
outlines the four steps of doing
Experimental Mathematics, in the
way it is usually practiced today.

{\bf 1.} Wondering, by a human, what a ``particular situation
looks like in detail''.

{\bf 2.} Some computer experimentation to show the structure of
that situation for a selection of small values of the parameters.

{\bf 3.} The [human] mathematician {\it gazes} at the computer
output, attempting to see or to codify some pattern,
that hopefully leads him or her to formulate a {\it conjecture}.

{\bf 4.} Human-made proof 
of the human-made conjecture (that was computer-inspired).

Under this scheme, only step {\bf 2} employs the computer.
In the present series of articles, I illustrate, {\bf by example},
how computers can be used, {\bf without any human intervention},
to also do steps {\bf 3}  and {\bf 4}. 
As for step {\bf 1}, the wondering,
this can also be done by machinekind
-it is not too hard to teach the
computer how to wonder. All that we, humans, 
ultimately would have to do is 
{\it meta-wonder}. In other words,
make up new {\bf ansatzes} and write {\bf once and for all}
computer programs teaching the computer how
to {\it wonder} in these ansatzes, {\bf then} {\it gaze} at the pattern,
{\bf then} {\it formulate a conjecture} (within the given ansatz)
and {\bf then}, finally, {\it prove} the conjecture,
{\bf all by itself}, without any human intervention!
No longer just {\bf computer-assisted} but 
fully {\bf computer-generated}.

{\bf The Art of Determinant Evaluations}

To find out about the state of the art in contemporary
explicit determinant evaluations, by {\it homo sapiens},
the reader should consult
Christian Krattenthaler's beautiful surveys [K1] and [K2]. 
\vfill\eject

{\bf Shalosh B. Ekhad vs. Some Great Human Mathematicians}

Consider the determinant evaluation
$$
\det
\left ( {{\mu +i+j} \choose {2i-j}} 
\right )_{0 \leq i,j \leq n-1}
= \prod_{i=1}^{n-1}
Nice(\mu,n,i) \quad,
\eqno(MRR)
$$
where $Nice$ is some explicit expression whose
exact form I omit right now in order not to distract from the 
general ideas.
This determinant-evaluation, discovered and first proved by
William Mills, David Robbins, and Howard Rumsey [MRR1], was
so attractive that other great mathematicians, notably
George Andrews and Dennis Stanton[AS], Marko Petkov\v{s}ek and Herb Wilf [PW],
and Christian Krattenthaler[K1] took the trouble to find
other proofs. 

But if you have Maple, and downloaded the Maple package
{\tt DET} into your computer, 
and gotten into Maple by typing {\tt maple}, and
typed {\tt read DET:}, then typing:

{\tt RproofP(binomial(m+n+p,2*m-n+1),m,n,N,30,R,p,40,60):} ,

and waiting $256$ seconds of CPU time
will, completely {\it ab initio}, conjecture $(MRR)$
and immediately proceed to prove it {\it fully rigorously}.

Once written, {\tt DET} can {\it discover(!)}
and {\it prove(!!)} countless other
determinant evaluations, provided they belong to the right {\it ansatz},
the holonomic ansatz in our case.
You are welcome to look at the webpage of this article\hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde 
zeilberg/mamarim/mamarimhtml/ansatzII.html}\hfill\break
for numerous examples of input and output, in addition to
the Mills-Robbins-Rumsey evaluation mentioned above.
If you have Maple, you can generate many more examples on your
own.

{\bf Caveat}

Unlike WZ theory, where the computer is guaranteed to give
an output (time and space permitting), this is not the case here.
It is not known, and is probably false, that
it is always the case that if $a(i,j)$ is holonomic, and setting
$A(n):=det(a(i,j))_{0 \leq i,j \leq n-1}$, then
$B(n):=A(n+1)/A(n)$ is holonomic in $n$. But it happens
often enough to justify asking the computer to give it a try.

{\bf The General Idea}

Of course, the seed of the method {\it did} originate from humans.
It can be formulated in two equivalent ways.  We have:

{\bf Problem}: Given some explicit expression
$m(i,j)$, define 
the $n \times n$ matrix $M_n$ to be
$$
M_n:= (m(i,j))_{0 \leq i,j \leq n-1} \quad .
$$
Find an {\it explicit} (in some sense) evaluation (in $n$) for
$$
A(n):=\det M_n \quad .
$$

{\bf George Andrews's Approach}

George Andrews
pulls out of a hat an {\it upper-triangular} matrix $U_n$
whose entries are ``nice'', and whose diagonal entries are
all $1$'s, and such that $L_n:=M_nU_n$ is lower-triangular and has a 
``nice'' diagonal (but the other entries are possibly ugly).
Then since $\det(M_n)=\det(L_n)/\det(U_n)$, and
$\det(U_n)=1$, we can express $\det(M_n)$ as a product of
nice things, and hence it is nice itself.

Of course, the reader is never told how $U_n$ was conjectured,
it is just pulled out of the blue. To prove the assertion
one has to prove that $L_n$ is indeed lower-triangular, i.e.
the entries of $M_nU_n$ above the diagonal are all $0$, which boils
down to (usually) proving a hypergeometric identity.
Next, one has to prove that the diagonal entries of $L_n$ are
as claimed, which involves another
hypergeometric identity. These are sometimes proved 
by computer, using
the Zeilberger algorithm, but still in a piecemeal,
{\bf human-centric}, way.

{\bf Dave Robbins's Approach}

Although mathematically equivalent
to George Andrews's LU approach, 
I find Dave Robbins's approach, described in [MRR2], 
more conducive for teaching a computer.

Consider the $n+1$ by $n+1$ matrix $(a(i,j))$, 
for $0 \leq i,j \leq n$. Let
$A(n,j)$ ($0 \leq j \leq n$), be the cofactor
of the $(n,j)$ entry. Then of course
$$
\det (a(i,j))_{0 \leq i,j \leq n}=
\sum_{j=0}^{n} A(n,j) a(n,j) \quad .
$$
Now the $n+1$ unknowns
$A(n,j),j=0 \dots n$ are uniquely determined, up to a normalization
factor (that only depends on $n$), by the $n$ 
linear homogeneous equations
$$
\sum_{j=0}^{n} A(n,j)a(i,j) =0 \quad , \quad (i=0 \dots n-1) \quad .
$$

The normalized cofactors $A'(n,j)$ defined
by $A'(n,j)=A(n,j)/A(n,n)$, are then determined
uniquely, for each specific $n$, by the system
of linear equations
$$
\sum_{j=0}^{n} A'(n,j)a(i,j) =0 \quad, (i=0 \dots n-1) \quad ,
\eqno(Dave1)
$$
subject to
$$
A'(n,n)=1 \quad.
\eqno(Dave2)
$$

Now the human can ask the computer to crank out 
$A'(n,j)$ for $0 \leq j,n \leq N$ for some
$N$ (say $100$), {\it gaze} at the output,
and conjecture some `explicit' form for $A'(n,j)$ and
then prove that they indeed satisfy $(Dave1)$ and
$(Dave2)$. 

Finally, if in luck,
$$
B(n):=\sum_{j=0}^{n} A'(n,j) a(n,j) \quad,
\eqno(Dave3)
$$
turns out to be  `explicit' , and the
human is clever enough to prove it.
Since $A(n,n)=\det (a(i,j))_{0 \leq i,j \leq n-1}$,
it follows that 
$$
{{\det (a(i,j))_{0 \leq i,j \leq n}}
 \over
{\det (a(i,j))_{0 \leq i,j \leq n-1}}
 } =B(n) \quad,
$$
that finally entails that
$$
\det (a(i,j))_{0 \leq i,j \leq n} =
\prod_{j=0}^{n} B(j) \quad,
$$
which should be considered `nice' if $B(j)$ is.


{\bf The Limit of Humans}

If $A'(n,j)$ turns out to be {\it closed-form} then some
clever humans can gaze at it and conjecture
an expression for it. Other humans
will `cheat' and use a computer program (like Krattenthaler's
{\tt rate}) to do the guessing, but in an {\it interactive}
way.

If nothing nice emerges, then these humans use
some tricks of the trade, that only they know, and 
are unwilling (and usually also unable) to divulge, to express
the normalized co-factor $A'(n,j)$
as a single- or double- hypergeometric sum. Then
go through excruciating pain to verify $(Dave1)$ and
evaluate $B(n)$, using $(Dave3)$.
This is indeed the most challenging case, when 
$A'(n,j)$ does not happen to be
a hypergeometric term,
but turns out to be a hypergeometric sum (or even a multisum).

{\bf Enter Computers}

When $A'(n,j)$ turns out to be closed-form, it is easy enough
to teach the computer to guess it empirically (and later on
prove it, see below), but trying to represent it as a hypergemoetric
sum or multisum is an art rather than a science, and does not
seem to be amenable to computerization. But we know, thanks
to WZ theory, that hypergeometric sums and multisums belong
to the Holonomic Ansatz (see [Z1]), so why not start there?

Computers do not play favorites. 
When instructed to operate within the {\it Holonomic
Ansatz}, they have no particular fondness for hypergeometric terms.
A discrete function of two variables being
a hypergeometric term is just the {\it special case}
of the defining recurrences being {\it first-order}.
So staying within the {\it holonomic ansatz},
once the computer generated enough numerical data
$A'(n,j)$ for $0 \leq n,j \leq N$ for a big enough $N$,
instead of {\it gazing}, it keeps {\bf guessing} linear recurrence
equations with polynomial coefficients (see [Z1]) in the
$n$ direction and in the $j$ direction,
not necessarily of the first-order.
It also tries to guess a linear recurrence
equation with polynomial coefficients satisfied by 
$B(n)$, once enough specific values of $B(n)$ , for, say,
$n \leq 100$ (or whatever), have been generated by $(Dave3)$.

Once conjectured, the rest, i.e., proving that 
$(Dave1)$, $(Dave2)$, and $(Dave3)$ 
hold when the `real' $A'(n,j)$ and $B(n)$ are
replaced by the sequences defined by these conjectured
recurrences (subject to the obvious initial conditions),
is algorithmically decidable thanks to
[Z2], at least in principle, but thanks to
Frederic Chyzak's beautiful work[C], probably
also in practice. Once this is completed, it
follows (rigorously!), by the {\it uniqueness} of the
solution to $(Dave1)$ and $(Dave2)$,
that the conjectured recurrences for $A'(n,j)$ are
indeed correct, and since $(Dave3)$ uniquely
determines $B(n)$, that the conjectured recurrence
for $B(n)$ is indeed true.

{\bf The Lucky Case}

When the conjectured recurrences for 
the normalized cofactors $A'(n,j)$ turn out to be
first-order, then they can be easily solved
explicitly, and $A'(n,j)$ turns out to be
(conjecturally for now) a
{\it hypergeometric term} in $(n,j)$. In other
words it is {\it closed-form}, and verifying 
that that conjectured closed-form is indeed correct
boils down to proving that $(Dave1)$ and $(Dave2)$
with $A'(n,j)$ replaced by that conjectured expression
indeed hold.  Then one also needs to verify that
the conjectured expression (or recurrence) for $B(n)$
is compatible with $(Dave3)$ with the $A'(n,j)$ replaced
by the (now proven) expression for it.

All this can be done with the original
`fast' Zeilberger algorithm[Z3][Z4], implemented in my
Maple package {\tt EKHAD} (available from my website),
as well as by the built-in Maple package {\tt SumTools}.
The relevant part of {\tt EKHAD} has been included
in the Maple package {\tt DET}. The
procedures that handle this lucky case
are {\tt Rproof} and {\tt RproofP}.
They give fully rigorous proofs of the conjectured 
expression or recurrence
for $B(n)$ (even when that recurrence is of higher order,
all we need is that the conjectured recurrences for $A'(n,j)$
be of first order in order to take advantage of {\tt Rproof}
and {\tt RproofP}).

{\bf The Unlucky Case}

When the conjectured recurrences for 
the normalized cofactors $A'(n,j)$ turn out to be
of higher order, we need to use Frederic Chyzak's[C]
package instead. Since I am not familiar enough with it,
this case is not yet implemented, and currently {\tt Rproof}
returns {\tt FAIL} in that case. 
Also, it is possible that even once Chyzak's program will
get interfaced with {\tt DET}, it will take too long, in which case
read the next section.

{\bf What If It Takes Too Long?
Let's Settle for a Semi-Rigorous Proof}

Since we {\it know} that if we had a big enough
computer, and good enough software, we can prove
that $(Dave1)$, $(Dave2)$ and $(Dave3)$ 
hold when $A'(n,j)$ and $B(n)$ are replaced by
their conjectured `explicit expressions' (in the sense
of the Holonomic Ansatz, where `explicit expressions'
are given implicitly as solutions of linear recurrence
equations with polynomial coefficients), is it really worth the
trouble? We can prove these facts semi-rigorously as follows.

We can use the conjectured linear recurrences 
for $A'(n,j)$ and $B(n)$ to crank out many more
conjectured values, much faster than by
solving the system of equations $(Dave1)$, $(Dave2)$ and
then computing the $B(n)$ by $(Dave3)$.

Let's temporarily call these new values
$A''(n,j)$ and $B'(n)$ and once found,
plug them into the analogs of
$(Dave1)$, $(Dave2)$ and $(Dave3)$ obtained by
replacing $A'(n,j)$ by $A''(n,j)$ and $B(n)$ by
$B'(n)$.
If they turn out to be right for, say,
$n,j \leq 10000$,
then it means that the conjectured recurrences
are right at least for  $n \leq 10000$,
but most likely we have also proved them for
{\it all} $n$, even though we don't have a rigorous
proof that this is indeed a rigorous proof
(but I bet it is!).

It is like proving that two polynomials are the same
by plugging-in enough special values. In the case of
polynomials of one variable, there is an easy parameter,
the degree plus 1, that tells you how many special values
you have to plug-in in order to rigorously prove 
a conjectured identity between two given polynomials.
The problem now is that it is not so easy to find the
analog of the {\it degree} for a holonomic function, but
if we check them for $n \leq 10000$, this is most likely
more than enough. The notion of {\it semi-rigorous} proof
was introduced in [Z5].

{\bf A Note on Guessing}

There now exist powerful guessing programs, for example
{\tt superseeker} in Neil Sloane's famous site,
Bruno Salvy and Paul Zimmermann's [SZ] Maple packages {\tt Gfun} and
{\tt Mgfun}, and Christian Krattenthaler's Mathematica program
{\tt rate}, that could have been used as subroutines in the
present endeavor. But I found it easier to program everything
{\it ab initio}, borrowing freely, of course, from these pioneering
programs.

{\bf The Maple Package DET}

Everything here is implemented in the Maple package
{\tt DET} available from

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/DET} .

As already mentioned, the webpage of this article \hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde 
zeilberg/mamarim/mamarimhtml/ansatzII.html} \hfill\break
contains sample input and  output.

The main functions are 
{\tt Rproof, RproofP, SRproof, SRproofI}.
To find out about them, in {\tt DET}, type
{\tt ezra(FunctionName);}. For example, for
help with {\tt Rproof}, type {\tt ezra(Rproof);}.

The `engines' driving these functions are
procedures {\tt DaveH} and {\tt DaveV}, that
guess horizontal and vertical pure recurrences 
respectively for the
normalized cofactors $A'(n,m)$. Full details can be
gotten by reading the source code of {\tt DET}.
Let me just mention that {\tt DaveH} works by conjecturing
recurrences, in $m$, for many rows (i.e. for fixed n), 
and then using 
procedure {\tt GR1}, that guesses rational functions, in order
to `interpolate' them, thereby
guessing a unified recurrence, also featuring $n$ 
symbolically.

\vfill\eject

{\bf Future Directions}

{\tt DET} can be further optimized, and translated
into Matlab or C, thereby probably making it much faster.
It would be also worthwhile to interface it with
Frederic Chyzak's packages thereby turning 
the semi-rigorous proofs, that we presently have to
contend with in the {\it unlucky} case mentioned above,
into fully rigorous proofs.

Finally, it should be relatively easy to write the $q$-analog
of {\tt DET}, but the running times would be larger because
of the extra symbol $q$. 



{\bf REFERENCES}

[AS] G.E. Andrews and D.W. Stanton, 
{\it Determinants in Plane Partition Enumeration},
Europ. J. Combin. {\bf 19} (1998), 273-282.

[C] F. Chyzak, {\it An extension of Zeilberger's
fast algorithm to general holonomic functions},
Discrete Math. {\bf 217} (2000), 115-134.

[K1] C. Krattenthaler, {\it Advanced Determinant Calculus},
S\'em. Lothar. Comb. {\bf 42} (1999), B42q.
(``The Andrews Festschrift'', D. Foata and G.-N. Han
(eds.))

[K2] C. Krattenthaler, {\it Advanced Determinant Calculus:
A Complement}, preprint, \hfill\break
{\tt http://arXiv.org/abs/math.Co/0503507}.

[MRR1] W.H. Mills, D.H. Robbins, and H. Rumsey,
{\it Enumeration of a Symmetry Class of Plane
Partitions}, Discrete Mathematics {\bf 67} (1987), 43-55.

[MRR2] W.H. Mills, D.H. Robbins, and H. Rumsey,
{\it Proof of the Macdonald conjecture}, Invent. Math.
{\bf 66} (1982), 73-87.

[PW] M. Petkov\v{s}ek and H. Wilf, {\it A high-tech
proof of the Mills-Robbins-Rumsey determinant evaluation},
Elec. J. of Combinatorics {\bf 3} (no.2 ``The Foata Festschrift'')
(1996), \#R19.

[SZ] B. Salvy and P. Zimmermann, {\it Gfun: a Maple package
for the manipulation of generating and holonomic functions
in one variable}, ACM Trans. Math. Software {\bf 20}
(1994).

[W] Herbert S. Wilf, {\it Mathematics: An Experimental Science},
to appear in ``Princeton Companion of Mathematics'' (W.T. Gowers, ed.),
Princeton University Press. Available from 
\hfill\break
{\eighttt http://www.math.upenn.edu/\Tilde wilf/reprints.html}.

[Z1] Doron Zeilberger,
{\it 
The HOLONOMIC ANSATZ I. FOUNDATIONS and Applications to Lattice Walk Counting},
submitted. Available from \hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde 
zeilberg/mamarim/mamarimhtml/ansatzI.html}.

[Z2] Doron Zeilberger, {\it A Holonomic systems approach to special functions
identities}, J. of Computational and Applied Math. {\bf 32},
321-368 (1990).

[Z3] Doron Zeilberger,{\it  A Fast Algorithm for proving 
terminating hypergeometric identities}, Discrete Math {\bf 80} (1990), 
207-211 .


[Z4] Doron Zeilberger,
 {\it The method of creative telescoping}, J. Symbolic Computation
{\bf 11} (1991), 195-204.

[Z5] Doron Zeilberger,
{\it Theorems for a price: Tomorrow's semi-rigorous mathematical culture},
Notices of the Amer. Math. Soc. {\bf 40 \# 8}, 978-981 (Oct. 1993).
Reprinted: Math. Intell. {\bf 16}, no. 4, 11-14 (Fall 1994).

\end







 

