
  
%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.
Accompanied by the Maple package DET available
from 
\hfill \break
{\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: The diminishing role of humans}

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 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 detract form the essence.
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 Petkovsek and Herb Wilf [PW],
and Christian Krathenthaler [K] took the trouble to find
other proofs. 

So I estimate that at least several months of human-mathematician
time  was spent in discovering, and proving $(MRR)$ in various
ways.

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, a {\it symbolic} 
explicit evaluation, $Nice(\mu,n,i)$  of the determinant
and immediately proceed to prove it {\it fully rigorously}.
It is entirely seamless, and all the r\^ole of the human
was to type the above line. And of course, at present,
write the Maple package {\tt DET}, and create Maple,
and invent the computer (and the transistor, and the chip etc.).

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

{\eighttt http://www.math.rutgers.edu/\Tilde 
zeilberg/mamarim/mamarimhtml/ansatzII.html}

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}
$$
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,i)$ ($0 \leq i \leq n$), be the cofactor
of the $(n,i)$ entry. Then of course
$$
\det (a(i,j))_{0 \leq i,j \leq n}=
\sum_{i=0}^{n} A(n,i) a(n,i) \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,i)$ for $0 \leq i,n \leq N$ for some
$N$ (say $100$), 
and ask the {\bf computer} (rather than
doing it himself) to {\it gaze} at the output,
and to conjecture some `explicit' form for $A'(n,i)$ 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 that one 
is clever enough to prove it.
Since $A(n,n)=\det (a(i,j))_{0 \leq i,j \leq n-1}$,
tt 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,i)$ turns out to be {\it closed-form} then some
clever humans, like George Andrews, can gaze at it and conjecture
an expression for it. Other humans, like Christian Krattenthaler
will `cheat' and use a computer program (like Krattenthaler's
{\tt rate}) to do do the guessing, but {\it interactively}.

If nothing nice emerges, then these humans use
some dirty tricks of the trade, that only they know, and 
are unwilling (and usually also unable) to divulge, to express
the co-factors as a single-sum or double-sum or whatever. Then
they go over excruciating pain, to verify $(Dave1)$ and
evaluate $B(n)$, using $(Dave3)$.
The most challenging  case is when 
the general normalized cofactor, $A'(n,i)$, does not happen to be
a hypergeometric term,
but is rather a hypergeometric sum (or multisum).

{\bf Enter Computers}

But computers do not play favorites. 
When instructed to operate within the {\it Holonomic
Ansatz} (see [Z1]),
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 j,n \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
$j$ direction and in the $m$ direction,
not necessarily of the first-order.
Once conjectured, the rest, i.e.,
proving $(Dave1)$, $(Dave2)$ and `evaluating'
$B(n)$ is algorithmically decidable thanks to
[Z2], at least in principle, but thanks to
Frederic Chyzak's beautiful work[C], probably
also in practice.

{\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
$(Dave1)$ and $(Dave3)$ (once we conjectured
recurrences for $A'(n,j)$ and a
recurrence for $B(n)$), is it really worth the
trouble? We can use the conjectured linear recurrences 
for $A'(n,j)$ to compile a much larger table
of conjectured values, much faster than by direct
computation using the system of equations $(Dave1)$.

So let's temporarily call these new values
$A''(n,j)$, and once found,
plug them into $(Dave1)$ and $(Dave3)$
for say $n \leq 10000$. If $(Dave1)$ and $(Dave3)$ hold
for all these $10000$ values of $n$,
it shows that our conjecture is right at least
up to $100000$.
This is almost a rigorous proof!
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 that it is not so easy to find the
analog of the {\it degree} for a holonomic function, but
if we plug it in for $n \leq 10000$, this is most likely
more than enough. The notion of {\it semi-rigorous} proof
was introduced in [Z3] and critiqued in [A].

{\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 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} .

The webpage of this article

{\eighttt http://www.math.rutgers.edu/\Tilde 
zeilberg/mamarim/mamarimhtml/ansatzII.html}

contains some 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, with
help for {\tt Rproof}, type {\tt ezra(Rproof);}.

The pillars of the above functions are
{\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 for many rows (i.e. for fixed n), and then using the
procedure {\tt GR1} that guesses rational functions in order
to guess a unified recurrence, featuring $n$ symbolically.

{\bf Apology and Future Directions}

This work is a little half-baked, and I hope
that other people can continue to perfect 
{\tt DET} and make it more efficient.

It should be relatively easy to write the q-analog
of {\tt DET}, but the running times would be slower because
of the extra symbol $q$. Also translating from Maple to
$C$ or Matlab should speed things up.


{\bf REFERENCES}

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

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

[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\^vsek 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.

[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

{\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 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







 
