 
%begin macros 
\def\Tilde{\char126\relax}
\baselineskip=14pt
\parskip=10pt
\def\epsilon{\varepsilon}
\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\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
\def\RightHead{\centerline{NSF Proposal: Targeted Proof Machines}}
\def\LeftHead{ \centerline{Doron Zeilberger}}
 
 
%end macros
\centerline{\bf NSF PROPOSAL: Targeted Proof Machines in Combinatorics}
 
\centerline{ \it Doron Zeilberger}
 
Department of Mathematics, Temple University, Philadelphia, PA 19122;
{\tt zeilberg@math.temple.edu}  
{\tt http://www.math.temple.edu/\Tilde zeilberg} .
 
\centerline{{\bf Table of Contents}}
 
 
Project Summary....................................................2
 
Summary of Results from Previous NSF Support..3
 
List of Publications from the NSF award...............7
 
Education and Human Resources Statement ........9
 
Project Description...............................................10
 
References.............................................................16
 
Biography-Doron Zeilberger, P.I.  .........................18
 
Short Biography-Dominique Foata, Consultant.....18
 
Five Relevant Publications....................................18
 
Five Other Publications........................................19
 
Collaborators and Advisor.....................................19
 
Proposal Budget- Year 1.......................................20
 
Proposal Budget- Year 2.......................................21
 
Proposal Budget- Year 3.......................................22
 
Proposal Budget- Cumulative...............................23
 
Current and Pending Support...............................24
 
\eject
 
\centerline{\bf Project Summary}
\centerline{ \bf TARGETED ``PROOF MACHINES'' IN COMBINATORICS} 
 
Doron Zeilberger proposes to 
develop algorithms for the automatic discovery and proof
of results in combinatorics and related areas. 
In particular he hopes to mechanize Dodgson's method
for evaluating hypergeometric determinants, to use
techniques from computational linguistics to empirically
discover (and then rigorously prove)
`grammars' of combinatorial families,
and to develop a computational Ansatz for multi-variate
rational generating functions. He also proposes to investigate
combinatorial analogs of techniques from combinatorial chemistry,
and to try to prove Mark Haiman's 
``$(n+1)^{n-1}$'' Diagonal Harmonics conjecture
 
\bigskip
 
{\bf Note}: Previous grants of Zeilberger were supported by the
Algebra and Number Theory program, with split-funding from
Analysis, Computational Mathematics,
and Numeric and Symbolic Computations (Computer Science). The present proposal
may also be considered for such split-funding. In this proposal the
Analysis component is less explicit, but the computational
component is even  more pronounced than previously.
 
\eject
 
{\bf Summary of Results from Previous NSF Support: DMS-9123836 and DMS-9500646}
 
{\bf 1.} The current NSF award number is DMS-9500646
for the period 1995-98, totaling \$120,000 .
 
{\bf 2.} Its title was: ``{\it Combinatorics, Special Functions, and
Computer-Algebra}''.
 
{\bf 3. Summary of the results of the completed work.}
 
(The numbered references apply to the list of papers written with
the NSF support of the above grants, given at section 4.
The lettered references are to papers given at the end of the section
``Proposed Research''.)
 
{\bf The Refined Alternating Sign Matrix Conjecture}
 
In my penultimate grant, DMS-9123836, I proposed to prove
the Alternating Sign Matrix Conjecture, which I did([12]).
This conjecture, due to Mills, Robbins, and Rumsey[MRR], asserts
that the number of $n \times n$ {\it alternating sign matrices}
(which are  matrices whose entries are from $\{-1,0,1\}$,
whose row- and column- sums are all $1$, and in which
the non-zero entries in each row and column alternate in
sign) equals 
$[(3n-2)!/(2n-1)!][(3n-5)!/(2n-2)!][(3n-8)!/(2n-3)!] \dots [1!/n!]$.
 
The proof was very long, and was verified by 85 checkers,
who each checked a small part. This was made possible by
the structured form in which the proof was presented, with
lemmas, sublemmas, subsublemmas, ..., forming a coherent
logical web. Each node was assigned a checker, and all he or she
had to do was check that the $(sub)^{i+1}$-lemmas of the
checked $(sub)^{i}$-lemma imply it. In addition, Dave Bressoud
kindly served as an independent global checker.
 
In my ultimate grant, I proposed to extend the method of proof of [12]
to prove the so-called {\it Refined Alternating Sign Matrix
Conjecture}. The refined version, also conjectured in [MRR], gives
a certain explicit expression for the number of $n \times n$
alternating sign matrices whose sole first-row `$1$' is at the
$r^{th}$ column. This I did, but {\it not} in the proposed way,
due to an unexpected, exciting, development.
 
A few months after the appearance of [12], Greg Kuperberg[Ku]
surprised the combinatorial-enumeration community with a much shorter
proof, that was based on the Izergin-Korepin([KBI]) determinant formula
for square-ice from Statistical Physics, that follows, non-trivially,
from the celebrated Yang-Baxter equations. 
When I saw Kuperberg's brilliant proof, I realized that
it should extend to prove the refined ASM conjecture.
This I did ([13]), using, in addition to Kuperberg's ideas,
the seminal work of Dick Askey, George Andrews, and Jim Wilson
on $q-$ analogs of the classical orthogonal polynomials
([AA],[AW]). 
 
Dave Bressoud has just completed 
the first draft of a book([Br2]) on
the Alternating Sign Matrix Conjecture, and its refinement,
that will describe my proof of the refined
version, as well as Kuperberg's proof that lead to it, and
the seminal contributions of Mills,
Robbins, and Rumsey, as well as George Andrews's[An2]
tour-de-force proof of the so-called TSSCPP conjecture
(that my proof in [12] depended on), as well
as background material. Bressoud's book should be
accessible to the proverbial bright advanced undergraduate.
 
{\bf Permutation Statistics }
 
Dominique Foata and I have defined an extension of the 
classical permutation statistics {\it inv} and {\it maj}
parameterized by an arbitrary graph ([14]). We characterized
those graphs that have the {\it Mahonian} property, i.e.
the generating functions of {\it inv} and {\it maj} are
the same. 
 
In [15], John Noonan and I give a new approach to the
counting of permutations with a prescribed number of
occurrences of a given class of `forbidden patterns'.
 
{\bf Hyman Bass's Evaluation of the Zeta Function of a Graph }
 
Also with Foata, we generalized, and gave a combinatorial
proof, of Hyman Bass's ([Ba]) evaluations of the Ihara-Selberg 
Zeta function of a graph. We were able to find connections
to the Amitsur identity and to Lyndon Words.
 
 
{\bf Bijective Proofs}
 
On a lighter note, Foata and I found a bijective
proof of a linear recurrence for the Schr\"oder-Hipparchus
numbers ([31]), meeting a challenge posed by Richard Stanley in
his delightful and erudite article ([Sta2]).
In [25] I give a short involutive proof of Dodgson's rule for
evaluating determinants. It is based on a `racy' model of
$n$ married men and $n$ married women, who each have one extra-marital
affair. This involution should generalize to the case where
each individual is allowed $r$ affairs, which would presumably
prove the generalized Dodgson-Sylvester determinant identities.
 
 
{\bf Determinant Evaluations}
 
I realized that Charles Dodgson's condensation method
(that, incidentally inspired alternating sign matrices) could be used
to explicitly evaluate combinatorial determinants
([16],[AE]). I am currently working on making this
purely mechanical (see the section
on the Dodgson Ansatz below). 
 
In [29], Christian Krattenthaler and I prove an amazing
determinant evaluation conjectured by Enrico Bombieri,
David Hunt, and Alf van der Poorten ([BHP]). This was
(a generalization of) the first open case in an infinite
family of such conjectured determinant-evaluations
that entail far-reaching number-theoretic consequences.
We are currently working on doing the general case.
 
{\bf Computer-Generated Research}
 
A large part of my research effort consists in harnessing
the computer to prove theorems that otherwise would be
very difficult, and sometimes impossible, to do by
human means alone. This theme is 
in the background of most of my research, at least implicitly,
but in a few instances the role of the computer is dominant.
In these cases I put my beloved computer, Shalosh B. Ekhad,
as a coauthor.
 
Shalosh and I are most proud of our recent proof([27]) of
John Conway's ([Co]) {\it Cosmological Theorem}, that
concerns Conway-type `audioactive' sequences whose prototype is
{\bf 1, 11, 21, 1211, 111221, 312211, \dots }.
Here each term `describes' the previous one. For example
one can describe the last term above as : ``one 3, one 1, two 2's, two 1's'',
so the next term is the string: {\bf 13112221}. Conway([Co]) proved that
the length of the $n^{th}$ term is 
asymptotically $C\lambda^n$, where
$\lambda$ is {\it Conway's constant}: $1.303577...$, (see, e.g. [Fi]),
a certain algebraic number whose minimal polynomial has
degree $71$. Conway also stated that the same holds for 
any such sequence derived from an
{\it arbitrary} initial string (except the fixed point
{\bf 22}). This follows from the so-called Cosmological Theorem,
that according to Conway used to have two proofs (one by
Richard Parker and himself, and another one by Mike Guy).
Both of these proofs were very long, and were subsequently
lost. In [27], Ekhad and I give a computer-proof that took
more than a month to run (on a Sun workstation,
running on {\it nice}). More important than the 
proof itself is the methodology behind it, that should
be a paradigm for the ultimate proof of the Four Color
Theorem, and many future theorems: 
computer-generated rather than merely computer-assisted.
 
Another triumph for the computer is the proof([18]) of
a conjecture of Sasha Kirillov and Anna Melnikov ([Ki][KM]). 
In this case it was a dialogue with the computer. 
Using computer explorations, I first found a more
general statement, that was then proved by using the
Maple package {\tt qEKHAD}, that implements the
q-WZ method.
 
Another heavy-duty computer project is [35], where a
Maple package, {\tt LEGO}, is described, that finds
instantaneously many formulas that previously took
months of human effort, and many new ones. 
{\tt LEGO} computes generating functions for the enumeration
of many classes of `toy models' for polyominos, whose
simplest case is Temperley's expression for the generating
function for vertically-convex polyominos.
 
Also falling under this heading is [36], where John Noonan
and I implement, extend in various directions,
and find various applications, of the powerful 
{\it Goulden-Jackson Cluster} method([GJ]) for counting the number of
words that avoid a certain prescribed lexicon of
`bad words' as factors (i.e. subwords consisting of
consecutive letters).
 
{\bf WZ Theory}
 
In 1996, Marko Petkovsek, Herb Wilf, and I published the
book ``A=B'' ([21]). This book was
a dual-main-selection of the {\it Library of Science}
(early summer 1996). Its Japanese translation is about to appear,
and translations to Chinese and Russian are in progress.
 
In [24], Petkovsek, Wilf, Istvan Nemes, and I describe how
many Monthly problems are now routine, thanks to Gosper's algorithm,
the WZ method, and Petkovsek's algorithm {\it HYPER}.
 
In [20], it is shown how the WZ method could have helped
Issac Newton and Samuel Pepys in a probability problem
that arose in gambling. In [4], the continuous version of
the WZ method is used to evaluate Mehta-type integrals.
In [22], George Andrews's {\it Syndrome} ([An3]) is
tackled, thus answering one of the research problems
proposed in the last proposal.
 
In quite a different direction, my
student Tewodros Amdeberhan and I use
the WZ method to find extremely fast-converging
series for $\zeta(3)$[23], and to give Ap\'ery-style
proofs of the irrationality of the q-analogs of
$\log 2$ and the Harmonic series ([30]), previously
proved by Peter Borwein by the use of Pad\'e Approximants.
Our irrationality measure improves on the one implied
by Borwein's approximating sequence in the case of the
q-analog of the Harmonic series, and matches it in the
case of $\log_q 2$. One of the series in [23] was used
by Simon Plouffe, George Fee and others to continuously break
the record for the computation of $\zeta(3)$ to many
digits, see Steve Finch's fascinating website ([Fi]).
 
In [9], it is shown how Leonard Weinstein's short proof of the
Bieberbach conjecture (first proved by deBranges)
could be streamlined, and made even
shorter, by the use of the WZ method. In [1], a WZ proof
is given of Ramanujan's  formula for $\pi$, that
appeared in his famous letter to Hardy.
 
 
{\bf Exposition}
 
In [11] I describe Joe Gillis's serendipitous discovery
that lead to the currently flourishing subject of
Combinatorial Special Function Theory. 
In [17] I
give a motivated account of Fred Galvin's[Ga] astounding
proof of the Dinitz problem about the existence of
generalized $n \times n$
Latin squares where each entry can pick from its own prescribed set
of $n$ objects. The Math Bite [28] is an application of
mathematics to literature.
 
{\bf And Also...}
 
In [2], Jane Friedman, Ira Gessel and I consider `fractional'
enumeration of paths. In [3], a constant-term conjecture
of Peter Forrester is proved. In [5], Dominique Foata and I
give combinatorial interpretations and proofs of
the classical Capelli and Turnbull identities. In [6],
it is shown how Bernard Beauzamy and Jerome D\'egot's ([BD]) brilliant proof of
the Bombieri Norm-Inequality could be streamlined and made
(essentially) `one-line' by using the Chu-Vandermonde
classical binomial identity. In [8], Craig Orr and I
describe how to use Brunu Buchberger's theory of Gr\"obner bases 
to solve discrete Dirichlet problems.
 
In [26] an interesting and potentially useful problem,
that arose in the budding field of {\it Combinatorial Chemistry},
is solved. In [33], the powerful and versatile {\it Lace Expansion}, due
to David Brydges and Tom Spencer, is axiomatized and generalized.
Finally, [34] is an application of the algebra of linear
partial difference operators to an obsolete legal problem.
 
\eject
{\bf 4. List of Publications resulting from the NSF award.}
 
{\bf 1994}
 
1. (With S.B. Ekhad) {\it A one-line WZ proof of a formula of Ramanujan
for $\pi$}, in: ``Geometry, Analysis, and Mechanics''
(Volume to honor Archimedes's 2281st birthday), J. M. Rassias, ed.,
107-108. World Scientific, Singapore.
 
2.(With J. Friedman and I. Gessel) 
{\it Talmudic lattice path counting}, 
J. Combin. Theory Ser. A {\bf 68}, 215-217.
 
3. {\it Proof of q-analog of a constant term identity 
conjectured by Forrester}, J. Combinatorial Theory Ser. A {\bf 66},
311-312.
 
4. {\it  Towards a WZ proof of Mehta's integral}, SIAM J. Math. Anal.
{\bf 25}[Askey-Olver issue] , 812-814.
 
5. (With D. Foata) {\it Combinatorial Proofs of Capelli's
and Turnbull's Identities from Classical Invariant Theory}, Electronic
J. of Combinatorics, {\bf 1} R1.
 
6. {\it Chu's 1303 identity implies Bombieri's 1990 norm-inequality
[Via an identity of Beauzamy and D\'egot]}, Amer. Math. Monthly {\bf 101},
894-895.
 
7. (With L. Ehrenpreis) {\it Two EZ proofs of $\sin^2 z + \cos^2 z =1$},
Amer Math. Monthly {\bf 101}, 691.
  
8. (With C. Orr), {\it A computer algebra approach to the discrete
Dirichlet problem}, J. Symbolic Computation {\bf 18}, 87-90.
 
{\bf 1995}
 
9. (With S. B. Ekhad) {\it A  short and elementary,
``formal calculus" proof of the Bieberbach
conjecture (after L. Weinstein)}, Contemporary Math {\bf 178}, 113-115.
 
10. {\it The J.C.P. Miller Recurrence for Exponentiating a polynomial
and its q-Analog}, J. Difference Eqs. and Appls. {\bf 1}, 57-60.
 
11. {\it How Joe Gillis discovered Combinatorial Special Function Theory},
Math. Intell. {\bf 17(2)}, 65-66.
 
{\bf 1996}
 
12. {\it Proof of the alternating sign matrix conjecture}, Elect. J. 
Combinatorics {\bf 3(2)} [Foata Festschrift], R13 (84 pages).
 
13. {\it Proof of the refined alternating sign matrix conjecture},
New York J. of Math. {\bf 2}, 59-68.
 
 
14. (With D. Foata) {\it The Graphical Major Index}, J. Comp. Appl. Math.
[special issue on q-series] {\bf 68}, 79-101.
 
15. (With J. Noonan) {\it Counting Permutations with a prescribed
number of "forbidden" patterns}, Advances in Applied Math. {\bf 17},
381-407.
 
16. {\it Reverend Charles to the aid of Major Percy and Fields-Medalist
Enrico}, Amer. Math. Monthly {\bf 103}, 501-502.
 
17. {\it The method of undetermined generalization and specialization
illustrated with Fred Galvin's amazing proof of the Dinitz conjecture},
Amer. Math. Monthly {\bf 103}, 233-240.
 
18. {\it An explicit formula for the number of solutions of $X^2=0$
in triangular matrices over GF(q)}, Elect. J. Comb. {\bf 3(1)}, R3.
 
19. {\it Self-Avoiding Walks, the language of science, and Fibonacci numbers},
J. Stat. Planning and Inference {\bf 54}, 135-138.
 
20. {\it If $A_n$ has $6n$ dyes in a box, with which he has to fling at
least $n$ sixes, then $A_n$ has an easier task than $A_{n+1}$,
at Eaven Luck}, Amer. Math. Monthly {\bf 103}, 265.
 
21. (With M. Petkovsek and H. S. Wilf) {\it ``A=B''}, 
AK Peters, Wellesley.
 
{\bf 1997}
 
22. (With S. B. Ekhad) {\it Curing the Andrews Syndrome},
J. of Difference Equations and Applications {\bf 3},  xxx-xxx.
 
23. (With T. Amdeberhan)
{\it Hypergeometric Series Acceleration via the WZ method},
Elect. J. of Combinatorics {\bf 4(2)}[Wilf Festschrift volume], R3.
 
24. (With I. Nemes, M. Petkovsek, and H. S. Wilf)
{\it How to do Monthly Problems on your computer}, Amer. Math. Monthly
{\bf 104}, 505-519.
 
25. {\it Dodgson's Determinant-Evaluation Rule Proved by TWO-TIMING MEN and
WOMEN}, Elect. J. of Combinatorics {\bf 4(2)}, [Wilf Festschrift
volume], R22.
 
26. {\it A comparison of two methods for random labelings of balls
by vectors of integers},
Advances in Combinatorial Methods and Applications
to Probability and Statistics, N. Balakrishnan, ed., Birkhauser, 1997
(Mohanty Festschrift).
 
27. (With S. B. Ekhad)
{\it Proof of Conway's lost cosmological theorem}, 
Elect. Res. Announcements of the AMS {\bf 3}, 78-82.
 
28. {\it 
Math Bite: Proof of an empirical observation made by Amos Oz's character}, 
Math. Magazine {\bf 70 }, 291.
 
29. (With C. Krattenthaler)
{\it Proof of a determinant evaluation conjectured by Bombieri, Hunt, and
van der Poorten}, New York J. of Math. {\bf 3}, xxx-xxx.
 
{\bf To Appear}
 
30. (With T. Amdeberhan)
{\it q-Apery irrationality proofs by q-WZ Pairs}, Advances in Applied
Mathematics.
 
31. (With D. Foata)
{\it A classic proof of a recurrence for a very classical sequence},
J. Combin. Theory Ser. A.
 
32. (With D. Foata)
{\it Combinatorial proofs of Bass's evaluations of the Ihara-Selberg 
Zeta function of a graph}, Trans. Amer. Math. Soc..
 
33. {\it The abstract lace expansion}, Advances in Applied Mathematics.
 
34. {\it How much should a nineteenth-century French bastard inherit},
J. Difference Eq. Appl. (special issue in honor of
Gerry Ladas.).
 
{\bf Submitted}
 
35. {\it Automated counting of LEGO towers}.
 
36. (With J. Noonan)
{\it The Goulden-Jackson cluster method: extensions, applications, and
implementations}.
 
{\bf 5.} Many of my papers are accompanied by Maple packages
that are available, free of charge, from my homepage
{\tt http://www.math.temple.edu/\Tilde zeilberg}.
In addition, there are quite a few packages that
belong to forthcoming papers, or stand by themselves.
Some of them are of a rather general scope, and should
be useful to researchers in combinatorics, number theory,
analysis, statistical physics, and possibly other areas.
 
{\bf 6.}  A large part of the proposed research is a direct continuation
of the previous research, but there are also new directions, in which
the connection is less obvious.
 
{\bf 7. Education and Human Resources Statement.}
 
My first Ph.D. student, Sheldon Parnes, graduated in the summer of 1993,
He then became a postdoctoral fellow at the Institute for Computational
Mathematics directed by the Borwein brothers, in Simon Fraser University.
He is currently in Industry.
 
My second Ph.D. student, Ethan Lewis, finished in the spring of 1994,
from the neighboring University of Pennsylvania. He was first
a visiting lecturer at Haverford college, then spent two years
as a Lady Davis postdoctoral fellow at the Technion, Israel, and
is currently with the National Security Agency.
My third Ph.D. student, Craig Orr, finished in the fall of 1994.
He is currently also with the National Security Agency.
 
In the spring of 1997, another batch of graduate students
finished. John Majewicz has accepted an Associate Professorship
at the Community College of Philadelphia. John Noonan is
Assistant Professor at Mount Vernon Nazarene College, Ohio,
and Tewodros Amdeberhan declined an offer for a postdoc
at Penn-State in favor of a tenure-track appointment at
deVry Inst. of Tech., NJ. 
 
All these six theses combined experimental mathematics with
more theoretical investigations and used computer algebra heavily.
 
Currently I have four Ph.D. candidates under my supervision: 
Anne Edlin, who is working on computer-assisted proofs in
the theory of formal languages, and in the process is
developing a comprehensive Maple package, NOAM, that should
have many applications; Aaron Robertson, who is using
Maple to tackle problems in Ramsey theory; Akalu Tefera,
who is using computer algebra to prove constant term identities,
and Melkamu Zeleke who is working on the discrete Radon transform
and covering congruences.
 
The research conducted by my students involves large-scale
computing, and in the case of Edlin and Tefera, should lead
to Maple packages of wide interest and applicability to
the mathematical community. I am hence requesting student
support, on the level of one student,
that would be split between my students, and would free them
from some teaching obligations.
 
I am the local expert on computer algebra. In the last ten years I have
been teaching both graduate and undergraduate courses that were very well
attended, in using Maple and Mathematica to do research in mathematics.
Since most of the graduate students that attend my classes
are also teaching assistants,
this know-how gets transmitted to the undergraduates.
 
Paper [19] above was studied in a workshop for gifted high-school
students conducted at MIT by Satomi Okazaki, and one of the students,
Lauren Williams (currently a Sophomore at Harvard), used its method
to write a paper([Wi]) that won third prize in the 
1996 International Science Fair.
 
\bigskip
\centerline{\bf PROPOSED RESEARCH:}
\centerline{ \bf TARGETED ``PROOF MACHINES'' IN COMBINATORICS}
 
The title for the current proposal was inspired by the
following quotation of Dave Bressoud ([Br1]), that was
already used in ``A=B'' ([21], p. 6).
 
``The existence of the computer is giving impetus to the discovery
of algorithms that generate proofs. I can still hear the echoes of
the collective sigh of relief that greeted the announcement, in
1970, that there is no general algorithm to test for integer solutions
to polynomial Diophantine equations; Hilbert's tenth problem has
no solution. Yet, as I look at my own field, I see that creating
algorithms that generate proofs constitutes some of the most important
mathematics being done. The all-purpose proof machine may be dead,
but {\it tightly targeted machines} are thriving.''
 
Bressoud continues with the following (omitted in
``A=B'' for obvious reasons): ``One example lies in the
W-Z pairs of Herb Wilf and Doron Zeilberger that can be used to
prove identities for hypergeometric series .... This is mathematics
shaped by the computer. It is exciting. Its directions are
unpredictable.''
 
I propose to develop new `targeted proof machines' for other kinds
of identities and theorems. While I have a fairly good idea how
to proceed in the proposed areas, I am sure, that {\it unpredictable}
developments will occur that would be far more important than
the specific projects proposed here. 
Even more importantly,
the {\it methodology} that would emerge in the process of developing
specific proof-machines for specific classes of
identities and theorems, and the {\it research
style} that would necessarily develop, should contribute to 
the future mathematical culture, and help to make the best 
out of the impending intrusion of the computer in 
the mathematics of the next millennium.
 
{\bf The Dodgson Ansatz: Automated Determinant Evaluations}
 
Many problems in combinatorics (e.g. [An2]), analysis
(e.g. [Di]), number theory (e.g. [BHP]) and elsewhere 
(e.g. string theory! [SW]), reduce
to the explicit evaluation of a determinant of the form:
$$
A(n):=\det \, (a_{i,j})_{1 \leq i,j \leq n} \quad ,
$$
where $a_{i,j}$ is an explicitly given binomial coefficient or
sum of binomial coefficients.
In quite a few known cases, $A(n)$ is known, or conjectured, to
be `nice' in the sense that the ratio $A(n)/A(n-1)$ is `closed form'.
The method initiated in [16], and further used in the joint
paper of my student Tewodros Amdeberhan and my computer Shalosh
B. Ekhad ([AE]), and further extended and explored by
Marko Petkovsek([Pe])
goes as follows. Try to conjecture a `nice'
formula for the more general quantity
$$
B(n;r,s):=\det (a_{i,j}) \quad 
 ( r \leq i \leq n+r-1 \quad , \quad s \leq j \leq n+s-1 ) \quad .
$$
 
Once conjectured, the {\it proof} of the conjecture becomes routine
thanks to Dodgson's rule that implies the non-linear recurrence:
$$
B(n;r,s)= {{B(n-1;r,s) B(n-1;r+1,s+1)- B(n-1;r+1,s) B(n-1;r,s+1)}
\over {B(n-2;r+1,s+1)} } \quad.
\eqno(REC)
$$
 
Whenever $B(n;r,s)$ turns out to be `nice', the nice expression
can be found (at first conjecturally), by the computer, by using,
for example, the {\it gfun} Maple package of Brunu Salvy and 
Paul Zimmermann.
Then the formal proof can also be mechanized, by verifying
$(REC)$. Finally, to get $A(n)$, one substitutes
$r=1, s=1$ into $B(n;r,s)$, since, of course, $A(n)=B(n;1,1)$.
All this has already been implemented in the Maple package 
{\tt DODGSON} that is available from my homepage.
 
Unfortunately, there are many cases where $A(n)$ is known
(or conjectured) to be `nice', but the more general
$B(n;r,s)$ does not seem to be `nice' and probably isn't (e.g. [An1][An2]).
I believe that this failing can be overcome by a more inclusive
definition of `nice'. I am sure that in many cases
(and perhaps even all), $B(n;r,s)$ is `semi-nice' in the sense
that the ratios $B(n;r,s)/B(n-1;r,s)$,
$B(n;r,s)/B(n;r-1,s)$, and $B(n;r,s)/B(n;r,s-1)$ are no longer
`closed-form' but are holonomic (i.e. P-recursive,
which is to say that they satisfy linear recurrences
with polynomial coefficients in each of their variables). 
Since the Holonomic Ansatz is
purely decidable ([Sta1],[Ze],[Ca]), and one can multiply and add there,
it follows that once the defining linear recurrences for the above ratios
are `guessed' (by the computer, of course), then the computer
should be able to verify its own conjecture by
verifying the non-linear recurrence
$(REC)$. Finally it should get the
recurrence for $A(n)/A(n-1)$, where, as before, $A(n)=B(n;1,1)$,
and prove the conjectured expression.
 
In the ultimate algorithm, all the user would have to do is
enter $a_{i,j}$, and the rest would be done by the computer:
the empirical guess, and its proof. A natural candidate
that should work (at least in principle, the memory
consumption might well prove to be excessive), is the
evaluation of John Stembridge's[Ste] determinant
for the enumeration of totally symmetric plane partitions
(TSPP). This determinant was evaluated, by ingenious human means,
by Stembridge himself ([Ste]). Stembridge also has a determinant
for the still open $q-$enumeration. If all goes well
(barring running out of time or memory), the proposed
algorithm should do it.
 
 
{\bf The Chomsky Ansatz: Fitting Grammars into Combinatorial Families}
 
Many combinatorial families can be realized as formal languages. This
was the credo of the great combinatorialist and theoretical 
computer-scientist Marco Sch\"utzenberger, that was used to great
advantage by the `\'Ecole Bordelaise' (e.g. [Vi],[DV],[Bo]).
In some of the work of the Bordeaux school, computer algebra
was used, but only {\it after the grammar was discovered}
(by humans).
 
I propose to go {\it one step beyond}. Have the computer
`guess the grammar', empirically, and then prove that it indeed
generates the combinatorial family, and finally, using the grammar,
the computer should be able to set up the set of equations for
the generating functions (in case the grammar is non-ambiguous),
and finally solve the system. Everything should be done
automatically. All that the user would have to do is
define the combinatorial family (in some computer-readable
format, of course). The Maple package {\tt DIKDUK}, available
from my homepage, is still very preliminary,
and only covers type-3 grammars. I hope to extend it to
(at least) type-2 (i.e. context-free) grammars.
 
{\bf The Multi-Variable Rational Generating Function Ansatz}
 
Suppose that we have a `hard-to-count' combinatorial family
$A(n)$, where it is desired to obtain information (and if
possible, a `formula') for $a(n):=\vert A(n) \vert$. In many cases
one is able to partition $A(n)$ into subsets
$$
A(n)= \bigcup_{(a_1, \dots, a_k) \in R(n)} B(n; a_1, \dots, a_k) \quad, 
$$
where $k$ is fixed, and $R(n)$ is a well-defined subset of
the discrete $k-$dimensional lattice.
Then, because of the extra elbow-room,
one can often set up linear partial difference equations
(with constant coefficients) for 
$b(n; a_1, \dots, a_k):=\vert B(n; a_1, \dots, a_k) \vert$
which translates into an algebraic equation for the
generating function:
$$
f(z;x_1, \dots , x_k)= \sum_{n, a_1, \dots, a_k \geq 0} b(n; a_1, \dots, a_k)
z^n x_1^{a_1} \cdots x_k^{a_k} \quad,
$$
that could often be solved. Finally, all we have to do is translate
this information for $a(n)$.
 
Here is a trivial example. Let's try and count the number
of lattice paths in the plane from $(0,0)$ to $(n,n)$.
Let's call this $a(n)$. This is `hard to count'.
Consider instead the more general problem of counting these
paths from $(0,0)$ to $(m,p)$, let's call these number
$b(m,p)$. Then, of course
$$
b(m,p)=b(m-1,p)+b(m,p-1) \quad, \quad b(0,p)=1, \quad b(m,0)=1 \quad ,
$$
from which $\sum_{m,p \geq 0} b(m,p)x^my^p = 1/(1-x-y)$, and
finally $a(n)=b(n,n)=$ coeff. of $x^ny^n$ in $1/(1-x-y)$.
 
In this trivial case we know that $b(m,p)={{m+p} \choose {m}}$,
and $a(n)={{2n} \choose {n}}$, but in the general case one should
not expect a closed-form expression for the
$b(n; a_1, \dots, a_k)$, only for their generating function,
which would entail a certain constant-term expression for
$a(n)$, from which the WZ method can crank out a linear
recurrence with polynomial coefficients.
 
Eventually all this should be done completely automatically,
once the framework has been specified. It seems that
the enumeration of permutations with forbidden
patterns (the theory of Wilf classes)
should be amenable to the present approach.
 
{\bf Combinatorial Combinatorics}
 
One of the recent breakthroughs in the pharmaceutical industry is
{\it Combinatorial Chemistry} ([PE97]). The idea there
is to automatically generate a large amount of related
compounds, and then test them for biological activity.
 
I believe that this idea can be also used
in combinatorics. Many proofs in combinatorics
rely on the {\it construction} of `good' structures.
With the computer, it should be an easy task to generate
a large `library' of candidate structures, and look for 
a successful one. One is then confronted with the
age-old `needle in the haystack' problem. This can
be tackled with either brute force, backtracking,
simulated annealing, or genetic algorithms. To this arsenal
I propose to add the mathematical analog of
the {\it split and mix} method from combinatorial chemistry,
that I will now briefly recall (see [PE], and its references,
for more details).
 
Suppose that we have three kinds of related components
$A_i$ ($i=1, ..., a$), $B_j$ ($j=1, ..., b$), and
$C_k$ ($k=1, ..., c$). We would like to test all the $abc$
compounds $(A_i,B_j,C_k)$. If $a$, $b$, and $c$ are large
it is too costly to test each of these $abc$ resulting
compounds separately. The split-and-mix method consists
of putting all of the $A$'s in one big pot and mixing well.
Then one
throws in all the $B$'s, mixing well once again. Then the
resulting brew is
split into $c$ separate test tubes, each containing $1/c$ of
the $AB$ mixture mixed with {\it one} of the
$C_k$'s ($k=1, \dots , c$). 
Then each of the $c$ test-tubes is tested for `biological
activity' and the best $C_k$, let's call it $C_{k_0}$ is
found. Then the process is repeated with the $B's$, 
(where only $C_{k_0}$ is to be used), and the best $B_j$,
let's call it $B_{j_0}$ is used. Finally the best $A_i$
to add to the $B_{j_0},C_{k_0}$ mixture is chosen,
Let's call it $i_0$.  The winning compound is $A_{i_0}B_{j_0}C_{k_0}$.
So instead of
making $abc$ tests we only had to make $a+b+c$ of them.
Of course, optimality is no longer guaranteed
(unless the biological activity is the (weighted)
sum of the
activities of its components), but hopefully one would get close.
 
In the above we only used three kinds of components
$\{A_i\},\{B_j\},\{C_k\}$ for ease of exposition. The analogous
process for any number of related components
$\{A^{(1)}_{i_1}\},\{A^{(2)}_{i_2}\}, \dots , \{A^{(r)}_{i_r}\}$, with
$i_1=1, \dots, a_1 \, ; \,, \dots, \,;\, i_r=1, \dots, a_r$ should be clear.
 
Let's now see how this translates to combinatorial searching.
Suppose that we have a certain `fitness function'
$f$, defined on binary vectors $(i_1, \dots, i_n)$,
and it is desired to find the vector on which
$f$ is minimal. The naive algorithm is exponential
(one has to make $2^n$ evaluations). Simulated annealing
and genetic algorithms fare much better, at least for
near-optimality. However, I believe that {\it split-and-mix}
should be given a fair hearing! Here is how it goes.
 
At the $r^{th}$ step,
suppose that  $(I_1, \dots, I_{r-1})$ turned out to be the
best choice from the previous step. 
Compute the {\it average} of $f$
over all $n$-component  binary vectors that start with
$(I_1, \dots, I_{r-1},0)$, and the average
over those vectors that start with $(I_1, \dots, I_{r-1},1)$. If
the former is smaller, let $I_r:=0$, while if the
latter is smaller, let $I_r:=1$. 
 
At first sight
it seems that there is no gain, since computing the
average, from the definition, involves $2^{n-r}$
evaluations of $f$. But, the beauty is that
computing the average of a function over a combinatorial
family can be done {\it cleverly}, by the old trick of
changing the order of summation. For example let
$f(v)$ be the sum of the entries of the binary vector $v$,
i.e. the number of ones. Then ($\chi(statement)$ is 
$0$ or $1$ according to whether the statement is false or true):
$$
\sum_{v \in \{0,1\}^n} f(v)=
\sum_{v \in \{0,1\}^n} \sum_{k=1}^{n} \chi(v_k=1) =
\sum_{k=1}^{n} \sum_{v \in \{0,1\}^n, v_k=1} 1=
\sum_{k=1}^{n} 2^{n-1}=n 2^{n-1} \quad .
$$
Hence the average is $n/2$ (in this utterly trivial case
this also follows from symmetry). The same argument however applies
in much more non-trivial cases. I propose to apply the method
to find `good' van-der-Waerden sequences and other extremal
combinatorial objects from Ramsey theory.
 
This is all very preliminary, but it is worth a try. Perhaps
combining this with genetic algorithms and/or simulated annealing
would prove fruitful. Besides, the variations are endless. 
For example, one
can try and add at each stage `chunks' to the vectors, rather than
a single component.
 
{\bf Haiman's ``Diagonal Harmonics'' Conjecture}
 
In addition to the above computer-heavy research, I hope to
also investigate, in collaboration
with Dominique Foata (who is a consultant to this
proposal), another problem, where the computer should
only serve a secondary role, or be absent altogether.
The problem is Mark Haiman's[Ha] 
notorious $(n+1)^{n-1}$ conjecture, which I will now describe.
 
Let $I_n$ be the ideal
in $K[x_1, \dots , x_n]$ generated by the non-constant
symmetric polynomials. 
It is well known, and easy to see, that the 
quotient ring $K[x_1, \dots , x_n]/I_n$ is a finite-dimensional
vector space, and that its dimension is $n!$.
 
Now, let $J_n$ be the ideal, in 
$K[x_1, \dots , x_n,y_1, \dots , y_n]$ generated by the
non-constant `diagonally-symmetric' polynomials
(i.e. polynomials invariant under the action
$p(x_1, \dots , x_n; y_1, \dots , y_n) \rightarrow
p(x_{\pi(1)}, \dots , x_{\pi(n)}; y_{\pi(1)}, \dots , y_{\pi(n)})$),
for any $\pi$ in the symmetric group on $n$ elements).
Once again, it is easy to see that  the quotient ring
$K[x_1, \dots , x_n,y_1, \dots , y_n]/J_n$ is a finite-dimensional
vector space. Mark Haiman ([Ha]) conjectured that
this dimension equals $(n+1)^{n-1}$, and he verified his conjecture
for $n \leq 7$.
 
Dominique Foata and I have started working on this problem
this summer, and we have made some encouraging progress,
that should at least give new upper bounds for the desired
dimension, and {\it who knows?} perhaps prove it completely.
The approach is to compute the `Gr\"obner basis' of the
ideal $J_n$, but {\it not by computer} (at present
Maple, and even Macaulay, can only do it for specific $n$),
but {\it generally} for {\it general} $n$. Of course, the only hope
is to define the basis recursively. Once we have a global
description for the Gr\"obner basis, one should be able
to describe its leading monomials, from which one
would hopefully get a unified (albeit recursive) description of
the leading monomials, and the problem would be reduced to
a hopefully tractable problem of counting lattice points.
 
Let's illustrate the above
plan with the simple classical case of $I_n$. 
It is easy to show 
that the following is a Gr\"obner basis:
$\{ h_1(x_1, \dots , x_n), h_2(x_2, \dots, x_n), \dots, h_n(x_n) \}$.
Here $h_i$ are the complete symmetric functions, that may be defined
in terms of the generating function
$$
\sum_{i=0}^{\infty} h_i(y_1, \dots , y_m) t^i=
\prod_{j=1}^{m} (1-y_j t)^{-1} \quad .
$$
The leading monomials of the above basis
(with respect to the purely lexicographic order induced by
$x_1>x_2> \dots > x_n$) are $\{ x_1, x_2^2, \dots, x_n^n \}$,
hence a basis for the quotient ring  can be formed from the
monomials of the form $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$,
with $0 \leq a_1 <1, 0 \leq a_2<2, \dots , 0 \leq a_n < n$. 
It follows that the
dimension of the desired quotient ring is indeed $n!$.
 
The Haiman case is much more involved, but we believe that it is still
tractable. We take as `charter members' of our Gr\"obner
basis all the polarizations of the $h_r(x_r, \dots , x_n)$
(i.e. $H_{r,s}:=$Coeff of $t^s$ in  $h_r(x_r+ty_r, \dots, x_n+ty_n)$,
for $1 \leq r \leq n$, $0 \leq s \leq r$).
We can show that they survive to the end. But in addition
we also have the `first-generation', obtained by appending
those $S-$ polynomials of charter members that do not reduce to $0$. This
we can characterize completely. At present we are
trying to characterize the `second generation', and we hope
to go on to the end.
We conjecture that there are $n-2$ generations altogether.
 
Each member of the ultimate
(and also intermediate) Gr\"obner basis can be labeled by 
a binary tree whose leaves are the charter members above.
This polynomial is the reduction of the $S$-polynomial 
of the polynomials belonging to the two subtrees.
 
We hope to characterize the surviving $S$-polynomials
in terms of their corresponding trees, and then to
find the lead-monomials, which should yield the
exact dimension (that is, $(n+1)^{n-1}$, if Haiman's prediction is
correct).
 
\eject
{\bf REFERENCES}
 
[AE] T. Amdeberhan and S. B. Ekhad, {\it A condensed
condensation proof of a determinant evaluation conjectured
by Kuperberg and Propp}, J. Comb. Theory (A), {\bf 70}(1997),
169-170.
 
[An1] G. E. Andrews, {\it Plane Partitions III: the weak
Macdonald conjecture} , Invent. Math. {\bf 53}(1979), 193-225.
 
[An2] G. E. Andrews, {\it Plane Partitions V: the T.S.S.C.P.P
conjecture} , J. Combin. Theory Ser. A, {\bf 66}(1994), 28-39.
 
[An3] G. E. Andrews,
{\it Pfaff's Method (III): comparison with the W-Z method},
Elect. J. of Combinatorics {\bf 3(2)}(1996) [Foata Festschrifft], R21.
 
[AA] G. E. Andrews and R. Askey, {\it Classical orthogonal polynomials},
in:``Polyn\^omes Orthogonaux et Applications'' (Proceedings, Bar-Le-Duc 1984),
edited by C. Brezinski et. al, Lecture Notes in Mathematics {\bf 1171}
36-62, Springer-Verlag, Berlin, 1985.
 
[AW] R. Askey and J. Wilson, {\it ``Some basic hypergeometric orthogonal
Polynomials that generalize Jacobi polynomials''}, Memoirs of the Amer.
Math. Soc. {\bf 319}, 1985.
 
[Ba] H. Bass, {\it The Ihara-Selberg Zeta function of a tree lattice},
Internat. J. Math. {\bf 3}(1992), 717-797.
 
[BD] B. Beauzamy and J. D\'egot, {\it Differential Identities},
Trans. Amer. Math. Soc. {\bf 347}(1995), 2607-2619.
 
[BHP] E. Bombieri, D.C. Hunt, and A.J. van der Poorten, {\it Determinants
in the study of Thue's method and curves with prescribed singularities},
J. Experimental Mathematics {\bf 4}(1995), 87-96.
 
[Bo] M. Bousquet-M\'elou, ``{\it q-\'Enum\'eration de polyominos convexes}'',
Publications de LACIM, UQAM, Montr\'eal, 1991.
 
[Br1] D. Bressoud, {\it Review of ``The problems of mathematics,
second edition'', by Ian Stewart}, Math. Intell. {\bf 15(4)}
(Fall 1993), 71-73.
 
[Br2] D. Bressoud, {\it ``Proofs and Confirmations: The Story
of the Alternating Sign Matrix Conjecture''},
Cambridge University Press, 1999 (expected).
 
[Ca] P. Cartier, {\it D\'emonstration ``automatique'' d'identit\'es et
fonctions hyperg\'eometriques [d'apres D. Zeilberger]}, S\'eminaire
Bourbaki, expos\'e $n^{o}$ $746$, Ast\'erisque {\bf 206}, $41-91$, SMF, 1992.
 
[Co] J.H. Conway, {\it The weird and wonderful chemistry of
audioactive decay}, in: ``{\it Open Problems in Communication
and Computation}'', T.M. Cover and B. Gopinath, eds., Springer,
1987, pp. 173-188.
 
[DV] M.P. Delest and X.G. Viennot, {\it Algebraic languages and polyominoes
enumeration}, Theor. Comp. Sci. {\bf 34}(1984), 169-206.
 
[Di] J. Dieudonn\'e, {\it Fractions continuees et polyn\^omes orthogonaux
dans l'oeuvre de E.N. Laguerre},
in:``Polyn\^omes Orthogonaux et Applications'' (Proceedings, Bar-Le-Duc 1984),
edited by C. Brezinski et. al, Lecture Notes in Mathematics {\bf 1171},
1-15, Springer-Verlag, Berlin, 1985.
 
[Fi] S. Finch, {\it ``Favorite Mathematical Constants Website''},
{\hfill \break
\tt http://www.mathsoft.com/asolve/constant}.
 
[Ga] F. Galvin, {\it The list chromatic index of a
bipartite multigraph}, J. Combin. Theory Ser. B. {\bf 63}(1995), 153-158.
\smallskip
 
[GJ] I. P. Goulden and D. M. Jackson, {\it ``Combinatorial Enumeration''}, 
Wiley, NY, 1983.
 
[Ha] M. Haiman, {\it Conjectures on the quotient ring by diagonal
invariants}, J. Alg. Comb. {\bf 3}(1994), 17-76.
 
[Ki] A.A. Kirillov, {\it On the number of solutions to the
equation $X^2=0$ in triangular matrices over a finite field},
Funct. Anal. and Appl. {\bf 29} (1995), no. 1.
 
[KM] A.A. Kirillov and A. Melnikov, {\it On a remarkable sequence
of polynomials}, preprint.
 
[KBI] V.E. Korepin, N.M. Bogoliubov and A.G. Izergin, 
{\it ``Quantum Inverse Scattering and Correlation Function''},
Cambridge University Press, Cambridge, England, 1993.
 
[Ku] Greg Kuperberg, {\it Another proof of the alternating sign matrix
conjecture}, Inter. Math. Res. Notes {\bf 1996}, no. 3, 139-150.
 
[MRR] W.H. Mills, D.P. Robbins, and H.Rumsey,
{\it Proof of the Macdonald conjecture} , Invent. Math. {\bf 66}(1982),
73-87.
 
[Pe] M. Petkovsek, {\it Determinants in wonderland},
preprint.
 
[PE] M. J. Plunket and J. A. Ellman, {\it Combinatorial
Chemistry and new drugs}, Scientific American {\bf 276(4)}
(April 1997), 68-73.
 
[SW] J. H. Schwarz and C. C. Wu, {\it Evaluations of dual Fermion
amplitudes}, Physical Letters {\bf 47B}(1973), 453-456.
 
[Sta1] R. Stanley, {\it Differentially Finite power series},
Europ. J. Comb. {\bf 1}(1980), 175-188.
 
[Sta2] R. Stanley, {\it Hipparchus, Plutarch, Schr\"oder, and
Hough}, Amer. Math. Monthly {\bf 104}(1997), 344-350.
 
[Ste] J. Stembridge, {\it The enumeration of totally symmetric
plane partitions}, Adv. Math. {\bf 111}(1995), 227-243.
 
[Vi] X.G. Viennot, {\it Probl\`emes combinatoire pos\'es par la 
physique statistique, S\'eminaire Bourbaki $n^{o}$} 626,
Asterisque {\bf 121-122}(1985), 225-246.
 
[Wi] L. Williams, {\it Enumerating up-side self avoiding walks
on integer lattices}, Elec. J. Comb. {\bf 3(1)}(1996), R31.
 
[Ze] D. Zeilberger, {\it A holonomic systems approach to special functions
identities}, J. Comp. Appl. Math. {\bf 32}(1990), 321-368.
 
 
{\bf Biography-Doron Zeilberger, P.I.}
 
Doron Zeilberger received his Ph.D. in 1976 from the
Weizmann Institute of Science, under the direction of
Harry Dym. He is a direct academic descendant of David Hilbert
[Z(1976)$\leftarrow$ Dym(1965) $\leftarrow$ McKean(1955) 
$\leftarrow$ Feller(1926) $\leftarrow$
Courant(1910) $\leftarrow$ Hilbert(1885)]. He is currently a professor
of mathematics at Temple University.  Recent invited presentations
include the Fields Institute workshop on special functions
[principal speaker] (Toronto, June 1995), The Gillis memorial lecture at the
Weizmann Institute of Science (Jan. 1996),
The Wilf Symposium (Philadelphia, June 1996),
SOCA 96' (Tianjin, China, July 1996),
Workshop on Enumeration and Posets, (MSRI, Oct. 1996),
Workshop on experimental mathematics and combinatorics, 
(CRM, Montreal, May 1997), Topics in Number Theory
[plenary speaker] (Penn State, July 1997).
 
He is member of the editorial boards of {\it Advances in Applied
Mathematics}, {\it Annals of Combinatorics},
{\it Electronic Journal of Combinatorics}, {\it Journal of
Difference Equations and Applications}, and {\it The Ramanujan
Quarterly}. He is the proud owner of the computer Shalosh B. Ekhad.
 
 
{\bf Short Biography-Dominique Foata, consultant}
 
Dominique Foata received his {\it doctorat de  \'etat} under
Marcel-Paul Sch\"utzenberger in $1965$. He is currently
distinguished professor of mathematics at the University
of Strasbourg. His many honors include ICM 83',
and the UAP prize, 1985.
 
 
{\bf Five Relevant Publications}
 
 
1. (With M. Petkovsek and H. S. Wilf) {\it A=B}, AK Peters, Wellesley, (1996).
 
2. (With C. Krattenthaler)
{\it Proof of a Determinant Evaluation Conjectured by Bombieri, Hunt, and
van der Poorten}, New York J. of Math. {\bf 3}(1997), xxx-xxx.
 
3. {\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).
 
4. {\it Proof of the alternating sign matrix conjecture}, Elect. J. 
Combinatorics {\bf 3(2)} [Foata Festschrift] R13 (1996).
 
 
5. (With H.S. Wilf) {\it An algorithmic proof theory for hypergeometric
(ordinary and "q") multisum/integral identities}, Invent. Math. 
{\bf 108}, 575-633 (1992).
 
{\bf Five Other Publications}
 
1. (With G. Almkvist) {\it The method of differentiating under the
integral sign}, J. Symbolic Computation {\bf 10}, 571-591 (1990).
 
2. {\it The method of creative telescoping}, J. Symbolic Computation
{\bf 11}, 195-204 (1991).
 
3. {\it A Holonomic systems approach to special functions
identities}, J. of Computational and Applied Math. {\bf 32},
321-368 (1990).
 
4. (With D. Bressoud) {\it A proof of Andrews' q-Dyson conjecture},
Discrete Math. {\bf 54}, 201-224 (1985).
 
5. {\it  Sister Celine's technique and its generalizations}, J. Math.
Anal. Appl. {\bf 85}, 114-145 (1982).
 
{\bf Collaborators and Advisor}
 
My thesis advisor was Harry Dym. My recent collaborators
are  Tewodros Amdeberhan, Shalosh B. Ekhad, Leon Ehrenpreis, 
Dominique Foata, Christian Krattenthaler, 
Istvan Nemes, John Noonan, Craig Orr, Marko Petkovsek, and Herb Wilf.
 
\end
