 
 
 
 
%begin macros
\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
%end macros
 
\centerline{\bf Project Description}
 
{\bf Summary of Results from Previous NSF Support: DMS-8901610 and DMS-9123836}
 
{\bf 1.}The current NSF award number is DMS-9123836
for the period 1992-95, totaling roughly \$61000/year .
 
{\bf 2.} Its title was: ``Computer-Generated and
Computer-Assisted Research in Combinatorics and Special Functions'' 
 
{\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 the end of this section.
The lettered references are to papers given at the end of the section
``Proposed Research''.)
 
{\bf The Alternating Sign Matrix Conjecture}
 
I am especially proud of the proof of the alternating sign matrix 
conjecture[37]. 
This was one of the problems proposed in my previous proposal, and two
of the reviewers criticized the problem as ``too hard''.
 
The proof indeed turned out to be harder (or at least longer)
than I first thought. The first version
was distributed electronically in the early spring of 1993, and submitted
to the J. of the AMS. A few months later the referees found some
gaps.  I am happy to announce that they have all been fixed. The
new version was carefully checked by Dave Bressoud.
The current version (as well as other current papers
and software) is available via anonymous {\tt ftp} to 
{\tt ftp.math.temple.edu} (In directories {\tt pub/zeilberger/papers}
and {\tt pub/zeilberger/programs}.)
 
My other work can be roughly grouped as follows
(the lists of papers following each heading is not disjoint,
since some papers belong to more than one category.)
 
{\bf Computerized Proofs of Identities:} ([2-6][8][9][15-17][19][21-23]
[26][32][39].)
 
This work (in part joint with Herb Wilf)
received considerable attention. It is the subject of
a new section (the only change from the first edition) in the
recently released second edition of
{\it Concrete Mathematics} by Graham, Patashnik, and Knuth[GKP],
and of a long expository article by Pierre Cartier[Ca] in the
famous Bourbaki seminar. It is also covered in the chapter on
asymptotic methods in combinatorics written by Andrew Odlyzko[O]
for the ``Handbook of Combinatorics'' to be published by Van Nostrand.
 
Herb Wilf, Marko Petkovsek, and I, are currently writing a book
on the subject that will also contain new material.
 
 
Maple programs implementing the algorithms for proving
hypergeometric and other identities, as well as other programs
of combinatorial interest, are available by
anonymous ftp to the above-mentioned site.
 
{\bf Enumerative and Algebraic Combinatorics:}([1][7][13][14]
[10][25][28][31][36][38][40].)
 
This work includes the ongoing collaboration with Dominique
Foata([7][10][28][40]). Paper[7], on the new permutation
statistics {\it den} introduced by Marleen Denert
(and named by us), lead to interesting farther work, both by
Foata's student G.N.Han and by Dennis Stanton, Rodica Simion,
Anne de Medicis, and G. Xavier Viennot[MV].
 
Paper [28] (that has the distinction of being the {\it first} paper
to be published in the newly created {\it Electronic J. of Combinatorics}
launched by Herb Wilf and on which both Foata and I serve
 of the editorial board,) gives a combinatorial proof of
the Capelli and Turnbull identities, that complement the
insightful representation-theoretic proofs of Howe[Ho].
We are still thinking how to extend our approach to the proof
of the recent anti-symmetric analogs of Howe-Umeda-Kostand-Sahi([HoU],[KS]).
 
Paper [40] is the beginning of an attempted general theory
of permutation statistics, which will form part of the present
proposal. 
 
Dominique Foata served as a consultant to the expired grant. It would
be very helpful to retain him.
 
{\bf Constant Term Identities and related work:}([20][25][26][27])
The methodology of constant term, using the seminal method of
John Stembridge and Dennis Stanton[Ste][Sta][Zx], proved useful
again. It would be intriguing to combine it with the WZ theory.
 
{\bf Combinatorial Number Theory:}[11]. This was joint work
with Jamie Simpson on Distinct Covering Sequences, 
trying to nibble at Erdos's famous conjecture that
none exists with all odd moduli. Using the elegant
approach of Berger, Felzenbaum, and Fraenkel[BFF], we considerably
improved the lower bound for the number of primes that should participate
there.
 
{\bf Exposition:}([18][19][21][23][34].) Paper [23], speculates on
the future of mathematics,using the WZ proof theory as a parable.
It arose some
controversy (see George Andrews' critiques [An1][An2] 
and Richard Askey[As1]'s Math Review of [23].)
 
 
{\bf General Hypergeometric Theory:} In [12] I prove that Gauss' classical 
evaluation
of ${}_2 F_1 (a,b;c;1)$ cannot be extended to ${}_2 F_1 (a,b;c;x)$. The
method seems to have wider applicability.
 
{\bf None of the above:}([29][30][35][39].)
Paper[29] shows how a very important inequality due
to Bombieri, follows from the classical Chu-Vandermonde binomial
coefficient identity, via remarkable identities of Beauzamy and Degot[BG]
and Bruce Reznick[Re].
 
{\bf 4. List of Publications resulting from the NSF award.}
 
1. {\it A bijection from ordered trees to binary trees that sends the
pruning order to the Strahler number}, Discrete Math. {\bf 82},
89-92 (1990).
 
2. {\it A Holonomic systems approach to special functions
identities}, J. of Computational and Applied Math. {\bf 32},
321-368 (1990).
 
 
3. (With Shalosh B. Ekhad) {\it A $21^{st}$ century proof of
Dougall's hypergeometric identity}, J. Math. Anal. Appl.,
{\bf 147} 610-611 (1990).
 
 
4.{\it  A Fast Algorithm for proving terminating hypergeometric
identities}, Discrete Math {\bf 80}, 207-211, (1990).
 
 
5. (With H. S. Wilf) {\it Rational functions certify combinatorial
identities}, J. Amer. Math. Soc. {\bf 3}, 147-158 (1990).
 
 
6. (With G. Almkvist) {\it The method of differentiating under the
integral sign}, J. Symbolic Computation {\bf 10}, 571-591 (1990).
 
7. (With D. Foata) {\it Denert's permutation statistic is indeed
Euler-Mahonian}, Studies in Applied Math {\bf 83}, 31-59 (1990).
 
 
8. (With H. S. Wilf) {\it Towards computerized proofs of identities},
Bulletin of the Amer. Math. Soc. {\bf 23}, 77-83 (1990).
  
9. {\it The method of creative telescoping}, J. Symbolic Computation
{\bf 11}, 195-204 (1991).
 
10. (With D. Foata) {\it Multibasic Eulerian polynomials},
Trans. Amer. Math. Soc. {\bf 328}, 843-862 (1991).
 
11. (With R. J. Simpson) {\it Necessary conditions for distinct
covering systems with square-free moduli}, Acta Arithmetica
{\bf 59}, 59-70 (1991).
 
12. {\it Gauss's ${}_2 F_1 (1)$ cannot be generalized to}
${}_2 F_1 (x)$, J. Comp. Appl. Math. {\bf 39},
379-382 (1992).
 
 
13. (With I. Gessel) {\it Random Walk in a Weyl chamber}, Proc.
Amer. Math. Soc. {\bf 115}, 27-31 (1992).
 
14. {\it A proof of Julian West's conjecture that the number of
2-stack-sortable permutations of length $n$ is}
$2 (3n)! /((2n+1)! (n+1)!)$, Discrete Math. {\bf 102}, 85-93 (1992).
 
15. (with H.S. Wilf) {\it An algorithmic proof theory for hypergeometric
(ordinary and "q") multisum/integral identities}, Invent. Math. 
{\bf 108}, 575-633 (1992).
  
16. (With H. S. Wilf) {\it Rational function certification of
hypergeometric multi-integral/sum/"q" identities}, 
Bulletin of the Amer. Math. Soc. {\bf 27} 148-153 (1992).
 
17. {\it Closed Form (pun intended!)}, 
 in: "Special volume in memory of Emil Grosswald", M. Knopp
and M. Sheingorn,
eds., Contemporary Mathematics {\bf 143} 579-607, AMS, Providence (1993).
 
18. {\it Gert Almkvist's generalization of a mistake of Bourbaki},
in:"Special volume in memory of Emil Grosswald", M. Knopp,
ed., Contemporary Mathematics {\bf 143} 609-612, AMS, Providence (1993).
 
 
19. {\it Three recitations on Holonomic Systems and 
Hypergeometric Series}, Proceeding of the S\'eminaire
Lotharingien de combinatoire {\bf 24},5-37, IRMA, Strasbourg. (1993)
(To be reprinted in Journal Symbolic Computation.)
 
20. (With Jane Friedman) A generalization of Odlyzko's conjecture:
the coefficients of 
$(1-q)^{j} /(( 1- q^{2n} ) ... (1- q^{2n+2j} ))$ alternate in
sign,  Proc. Amer. Math. Soc. {\bf 118}, 1013 (1993).
 
21. {\it Identities in search of identity}, J. The. Comp. Sci.,
{\bf 117}, 23-38 (1993).
 
22. (With G.E. Andrews and S.B. Ekhad), {\it A short proof of
Jacobi's formula for the number of representations of an integer
as a sum of four squares}, Amer. Math. Monthly, {\bf 100}, 274-276 (1993).
 
23. {\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 in Math. Intell. {\bf 16 \# 4}, 11-14 (Fall 1994).]
 
24. {\it On an identity of Daubechies},
Amer. Math. Monthly {\bf 100}, 487 (1993).
  
25. {\it A constant term identity featuring the ubiquitous (and mysterious)
Andrews-Mills-Robbins-Rumsey numbers $\{1,2,7,42,429, ...\}$}, 
J. Combinatorial Theory (ser. A) {\bf 66}, 17-27(1994).
 
26. {\it  Towards a WZ proof of Mehta's integral}, SIAM J. Math. Anal.
{\bf 25} , 812-814 (1994).
 
27.{\it Proof of q-analog of a constant term identity 
conjectured by Forrester}, J. Combinatorial Theory {\bf 66}
311-312 (1994).
 
28. (With D. Foata) {\it Combinatorial Proofs of Cappelli's
and Turnbull's Identities from Classical Invariant Theory}, Electronic
J. of Combinatorics, {\bf 1}, Research paper {\bf 1} (1994).
[For the Mosaic(WWW) and Gopher addresses of the El.J.C. one
may finger Herb Wilf at {\tt wilf@central.cis.upenn.edu}.]
 
29. {\it Chu's 1303 identity implies Bombieri's 1990 norm-inequality
[Via an identity of Beauzamy and D\'egot]}, Amer. Math. Monthly, {\bf 101}
,xxx-xxx (Nov. 1994).
 
30. (With L. Ehrenpreis) {\it Two EZ proofs of $\sin^2 z + \cos^2 z =1$},
Amer Math. Monthly {\bf 101}, 691 (1994).
 
31.(with Jane Friedman and Ira Gessel) {\it Talmudic lattice path
counting}, J. Comb. Theory (Ser. A), to appear.
 
32. (with Shalosh B. Ekhad) {\it A  short and elementary,
``formal calculus" proof of the Bieberbach
conjecture (after L. Weinstein)}, Contemporary Math {\bf xxx }, to appear.
 
34. {\it How Joe Gillis discovered Combinatorial Special Function Theory},
Math. Intell., to appear.
 
35. (with C.Orr), {\it A computer algebra approach to the discrete
Dirichlet problem},  J. Symbolic Computation, to appear.
 
36. {\it Self avoiding walks, the language of science, and Fibonacci numbers},
J. Stat. Planning and Inference (Special  issue dedicated to 
Lattice Path combinatorics, proceedings, India 1994', S.G. Mohanty,
editor), to appear.
 
37. {\it Proof of the alternating sign matrix conjecture}, 
accepted for publication in
J. Amer. Math. Soc.  subject to revision and filling in the
details of the minor gaps. [The current version was carefully checked,
and approved, by Dave Bressoud. It is available by anon. ftp to
{\tt ftp.math.temple.edu} as file {\tt zeilberger/pub/papers/asm.tex}.]
 
 
38. {\it A combinatorist's view of the lace expansion}, in preparation.
(Based on a talk given in the Combinatorics Seminar of the
Inst. for Advanced Study, Nov. 1993.)
 
39. {\it A rigorous foundation to semi-rigorous combinatorics},
in preperation. (Based on an invited talk given in the
3rd Ann Arbor conference on algebra and combinatorics, June 1994.)
 
40. (with Dominique Foata){\it The graphical major index}, in preparetion.
 
{\bf 5.} In addition to Maple programs for proving identities,
I have developed a Maple package, SCH\"UTZENBERGER, for handling
formal power series and other combinatorial objects. It is
also vailable by anon. ftp to {\tt ftp.math.temple.edu}.
 
{\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 commection is less obvious.
 
{\bf 7. Education and Human Resources Statement.}
 
My first Ph.D. student, Sheldon Parnes, graduated in the summer of 1993,
and is currently a postdoctoral fellow at the Institute of Computational
Mathematics directed by the Borwein brothers, in Simon Fraser University.
 
My second Ph.D. student, Ethan Lewis, finished in the spring of 1994,
from the neighboring University of Pennsylvania. He is currently
a visiting lecturer at Haverford college.
 
My third Ph.D. student, Craig Orr, finished in the fall of 1994, and
is currently visiting lecturer at the University of Miami.
 
 
All these three theses combined experimental mathematics with
more theoretical investigations and used computer algebra heavily.
 
Currently I have 3 Ph.D. candidates under my supervision: Li Zhang,
John Noonan, and John Majewicz.
 
My recently expired grant supported a graduate student. It would be
nice to be able to retain it, so that each of these students can get
one year off from TAing, in order to free them to dedicate more time
to the current project.  My research, to be described in the next section,
has reached a stage in which it is very `labor intensive', and having
graduate-student time should be very important both to the success
of the project, as well as for the professional development of my students.
 
I am the local expert on computer algebra. In the last five 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 [36] above was studied in a workshop for gifted high-school
students conducted at MIT by Satomi Okazaki, and one of the the students
is currently working on using the method for solving
related problems, and plans to submit it to the Westinghaus
competition.
 
\bigskip
\centerline{\bf PROPOSED RESEARCH:}
\centerline{ \bf COMBINATORICS, SPECIAL FUNCTIONS, and COMPUTER ALGEBRA}
\bigskip
My research area
could be called {\it Manipulatorics}. 
Aptly coined by Adriano Garsia, this is that
part of mathematics that is concerned with {\it concrete} manipulations
of (in my case mostly combinatorial) objects. This swing-of-the-pendulum
back from Bourbaki-style excessive abstraction was
greatly inspired by computers 
and computer algebra, and is a fastly growing area. 
On the other hand, mathematics without any
abstraction is an oxymoron, 
so good Manipulatorics should give new blood and nutrition
to abstract mathematics, which in turn, feeds back ideas into
concrete mathematics. 
 
\centerline{\bf General Outlook}
 
Mathematicians, even pure ones, are finally starting to
appreciate the great power and versatility of the
computer, not only in {\it communicating} mathematics, but
also in {\it creating} it. In addition to the obvious use
in collecting data for the formulation of conjectures,
there is the possibility of computers {\it proving} theorems,
given the right algorithms. The so-called WZ theory, mentioned
in the previous section,
will be probably joined by algorithmic proof theories for many
other branches of mathematics. One such `proof theory' goes
back to Rene Descartes and his `analytical geometry', which
has gotten a new twist with computer algebra
and Gr\"obner bases, thanks to which it is now
possible to prove most theorems in plane 
(and, in principle, any fixed-dimensional) Geometry.
 
The greatest advances will be made by combining
the 3 aspects of research as I see it: `Experimental' exploration,
analogous to experimental science, in which one designs carefully
planned experiments, that are of course guided by theory. `Theoretical',
roughly paralleling theoretical physics, in which one proposes ways
to make sense out of the raw data, and finally, `Mathematical', in which
one insists on complete rigor.
 
In this proposal, these three aspects are intertwined together,
but their relative concentration vary from problem to problem.
I will now list the problems that I hope to make progress on.
 
\centerline{\bf A General Theory Of Permutation Statistics}
 
   The study of permutations is very ancient, and was pursued in
diverse cultures. For example, the Hebrew Book of Creation, {\it Sefer
Yetsira}, that tradition attributes to the patriarch Abraham, and
that was compiled c. 300 AD, lists the number of permutations
of $n$ objects for $2 \leq n \leq 7$. The general formula,$n!$, and its,
completely rigorous,
inductive proof, can be found in ``The book of Number'' written in the 14th
century by Gersonides (Rabbi Levi Ben Gerson , acronymed ``Ralbag'').
 
The more refined counting of permutations, according to various
{\it statistics}, was probably started by Netto, and reached
a climax with the monumental work of MacMahon. In more recent times,
it was taken up by Foata and Sch\"utzenberger. 
It was Foata who coined the name
`statistics' in this context, as well as the name `major index'.
It is nowadays a flourishing part of enumerative and algebraic combinatorics,
with major contributions coming from: Anders Bj\"orner, Jennifer Galovich,
Adriano Garsia, Kevin Kadell, Don Rawlings, Jeff Remmel, Bruce Sagan, 
Richard Stanley, Dennis Stanton,
Dennis White, Michelle Wachs, Xavier (G\'erard) Viennot and many others.
 
One interesting generalization, pursued successfully by Bj\"orner 
and Wachs[BW],
was to extend the classical definition of `inv', `maj', `des' etc.
from permutations to general partially ordered sets. In the generalization
that Foata and I have in mind, we keep the 
classical structures of permutations and words, and instead
generalize the `statistics' themselves.
 
More specificlly, Dominique Foata and I plan to work on a general theory
of permutation statistics that would be analogous to going from 
specific functions (like $cos(x), e^x, x^2$) to general analysis on functions.
We would like to understand what makes the classical statistics `special'.
For example, what are the conditions, for two different permutation
statistics to be equidistributed, i.e. possess the same generating
function? (like `inv'', the number of inversions,
and the so-called major index, `maj'.)
Under what conditions is the generating function
 
$$
F_n(q):=\sum_{\pi \in S_n} q^{stat(\pi)} \quad ,
$$
 
 
a) Closed form? (like in the case of {\it inv} and {\it maj});
b)`q-P-recursive' (q-holonomic)?
(i.e. $F_n (q) $ satisfies a linear recurrence equation with
coefficients that are polynomials in $(q,q^n)$.
c) When is the global exponential generating function
$\sum_{n=0}^{\infty} {{F_n(q) z^n} \over {n!}}$
nice?, like in the case of `des' (when one gets the Eulerian polynomials,
who are not `nice` by themselves, but which possess a nice generating 
function.)
 
What can one say about joint-distributions:
 
$$
F_n(q_1 , \dots , q_k):=\sum_{\pi \in S_n} q_1^{stat_1(\pi)}
\dots q_k^{stat_k(\pi)} \quad ?
$$
 
Can one explain such `coincidences' like the equi-distribution
of the pair (`des', `maj') with that of (`exc', `den') first proved
by Foata and I in paper[7] above, and since given a beautiful bijective
proof by Han Gue-Nu[Han]. Perhaps there is a more
global reason? 
 
The recent beautiful work of Jennifer Galovich an Dennis White
on generalized mahonian statistics should also be useful to the present
research.
 
The classical permutation statistics all concern `pairs'.
For example, the number of inversions, `inv', is the number of pairs
$(i,j)$, with $i<j$ such that $\pi(i) > \pi(j)$.
It would be interesting to explore properties of the analog to
`triples' and general $k-$tuples. The resulting new sequences 
$F_n(q)$, all `analogs' of the sequence $\{n!\}$, should also
be useful in serving as candidates for yet-to-be-discovered classes
of functions and sequences that would generalize the $q-$holonomic paradigm.
One such statistics, that in fact inspired the present generalization,
arose naturally in string theory, in Doron Gepner`s[Gep] work. We would
like to understand this better. To sum up, we have:
 
{\bf Research problem 1: Develop a general theory of permutation
statistics, and classify the ones that have `nice' properties.}
 
\centerline
{\bf Algorithmic Proof Theory for Special Functions and Combinatorial
Summation}
 
I would like to continue the work on `mechanical summation' and
`mechanical definite-integration'([2-6][8][9][15-17][19][21-23][26][32][39])
in two directions. The first one is in improving the current algorithms
to be able to do larger problems. The second, more interesting, direction is
to find increasingly larger and more general `paradigms', in which
one can successfully develop an algorithmic proof theory.
 
{\bf Curing the Andrews Syndrome}
 
In [Anx], and more dramatically, in several invited conference
talks\footnote{$^\dagger$}
{\eightrm For example, the Ann Arbor 3rd conference on algebra and
combinatorics (June 1994), and the Garsia conference (late July. 1994)
held in Taoramina, Sicily) where George Andrews rolled out on the floor
twelve transparencies, taped together,
containing the hairy output of my computer program, applied to a (special
case!) of the identity he was trying to prove.} George Andrews
found some naturally occurring identities whose proof turned out to be
beyond the present power of my Maple programs, running on the
currently available computers. The main problem seemed to be the
memory allocation, since the polynomials that arose were
gargantuan.
 
I propose to improve my algorithm so that Andrews' challenge
problems (that arose naturally in his research, and were not
artificially tailored to challenge my algorithm), and hopefully
others as well, that will arise in the future, would be doable
in `real time' (and more importantly, in `real space'). The key
would probably be to adapt the subroutine that uses the modified
Gosper algorithm so that it would be able to handle polynomials in better
`date structures' then the obvious, expanded one. 
 
What I mean by this is as follows. Take for example
$p(n):={{n} \choose {1000}}$. If you expand it, you would get
a polynomial of degree $1000$, with huge integer coefficients.
But a much better way to describe it would be by saying
that it has degree $1000$ and to give its values at $0$ through
$1000$. (Namely $p(0)= \dots = p(999)$=0,and $p(1000)=1$.)
I hope that the algorithm of [9] could be modified to handle polynomials
in this far more economic data structure (for the present purpose.)
This brings us to:
 
{\bf Research Problem II: Improve the algorithm for
mechanical summation, and its Maple implementation,
so that they could handle Andrews' challenge identities with
currently available technology.}
 
 
As far as the other, more general direction, there are still many
identities that do not fall under what I call the holonomic
paradigm. Recently, I realized that some identities 
that are not `holonomic' can be nevertheless be
handled by the holonomic approach. Take for example Abel's identity 
(e.g. [PGK]):
 
$$
\sum_{k=0}^{n} {{n} \choose {k}} (k+1)^{k-1} (n-k+1)^{n-k} = (n+2)^n \quad.
\eqno(Abel-sp)
$$
 
The summand $F(n,k)$ is neither holonomic in $n$ nor in $k$, and the
right side is not holonomic either. But  $(abel-sp)$ is really a
specialization of
 
 
$$
\sum_{k=0}^{n} {{n} \choose {k}} (tk+1)^{k-1} (t(n-k)+1)^{n-k} = (tn+2)^n \quad.
\eqno(Abel-ge)
$$
 
Now, the summand $F(n,k,t)$ is not holonomic w.r.t. to $n$, but is holonomic
w.r.t. (the discrete variable )$k$ and (the continuous variable)$t$. 
Considering $n$ as a parameter, the holonomic
theory promises us that the left side $a(t):=\sum_{k} F(n,k,t)$ should
be holonomic in $t$, i.e. satisfy a certain linear differential
equation with polynomial coefficients $P(n,t,D_t)a(t)=0$. The proof
is then completed by matching the appropriate `initial values',
at $t=0$ (for which the identity reduces to the binomial theorem
$(1+1)^n=2^n$. )
 
Thus even identities 
that are conspicuously non-holonomic may be doable, because
they are specializations of  `quasi-holonomic' identities, with just
enough variables to make things work. I would like to make
these vague remarks more precise and more general.
 
It would also be interesting to find generalizations to
{\bf bi-basic} (and {\bf multi-basic}) equations, as well
as `dilation-translation' equations, important in wavelets
[DL]. This brings us to:
 
 
{\bf Research Problem 3: Extend the algorithmic proof theory
for hypergeometric and holonomic functions 
and sequences to more general, yet to be discovered
realms of functions.}
 

{\bf Refined enumeration of alternating sign matrices}
 
I have already mentioned, in the report on work done under my
previous grants, that I have succeeded in proving the
Mills-Robbins-Rumsey conjecture about the number of
alternating sign matrices.
 
An {\it alternating sign matrix} is a square matrix whose entries
are drawn from the set $\{ -1,0,1\}$, whose row-sums and column-sums
all add up to $1$, and in which, in each row and each column, the
non-zero entries alternate in sign. Mills, Robbins, and Rumsey[MRR]
(see also [Sta])
alternating sign matrix conjecture stated
that the number of $n \times n$ alternating sign matrices
is given by the formula:
 
$$
A_n := \prod_{i=0}^{n-1} { { (3i+1)!} \over {(n+i)!} } \quad ,
$$
 
There many related problems that are still open ([Ro][Sta]). 
The most pressing is
the refined formula, for the number of $n \times n$ ASMs whose
first row has its (necessarily only) $1$ in the $r^{th}$ column.
This was ``\#3'' in Stanley's [Stanl] `baker's dozen'.
 
Calling this number $A(n,r)$ , Mills, Robbins, and Rumsey, conjectured
that
 
$$
A(n,r)=   {{2n-2} \choose {n-1}}^{-1}
{{n+r-2} \choose {n-1}} {{2n-r-1} \choose {n-1}} A_{n-1} \quad .
$$
 
My proof in [37] is indirect. Constant term expressions were derived
for both the number of ASMs and the number of so-called
totally symmetric self-complementary plane partitions (TSSCPP) for
which Andrews[An1] has recently proved  are also enumerated by $A_n$
above, confirming another conjecture of [MRR] (``\#2'' in Stanley's
`baker's dozen'). Then I prove that
the two constant term expressions are the same.
 
It would be interesting if the constant term expression for the number of
$n \times k$ `Gog Trapezoids' (that reduce to
$n \times n$ ASMs when $n=k$), that I derived in [37] :
 
$$
CT \left [
 { { \Lambda_k ( x_1 , \dots , x_k ) } \over
   { x_1^{n} x_2^{n} \dots x_k^{n} }
} \times
\prod_{i=1}^k ( \bar x_i)^{-n-1-i} \prod_{ 1 \leq i < j \leq k}
(1-x_i x_j )^{-1} (1- \bar x_i x_j )^{-1} \right  ] \qquad ,
$$
 
where $\Lambda_k ( x_1 , \dots , x_k)$ is the polynomial defined in ($Gog_1$).
 
$$
\Lambda_k ( x_1 , \dots , x_k ) = 
(-1)^k \,
\sum_{ g \in W( B_k ) } sgn(g) \,\,
g \left [ \prod_{i=1}^{k} \bar x_i^{k-i} x_i^{k} 
\prod_{1 \leq i < j \leq k} (1- x_i \bar x_j )(1- \bar x_i \bar x_j ) \right ]
\qquad,
$$
 
could be used to prove the formula, $A_n$, directly, perhaps by
using the multi-variate WZ methodology of [15]. Combined with
the equality result proved in [37], this would give a new proof
of Andrews'[Anx] TSSCPP result. More importantly, this method
should work equally well, for the refined enumeration, of $n \times n$
ASMs whose first row has its sole `$1$' in the $r^{th}$ column.
The work in [37] easily implies the following
constant term expression for this number:
 
$$
CT \left [
 { { \Lambda_n ( x_1 , \dots , x_n ) } \over
   { x_1^{n} x_2^{n} \dots x_{n-1}^{n} x_n^{r}}
} \times
\prod_{i=1}^{n-1} ( \bar x_i)^{-n-1-i}  (\bar x_n)^{2n} 
\prod_{ 1 \leq i < j \leq k}
(1-x_i x_j )^{-1} (1- \bar x_i x_j )^{-1} \right  ] \qquad .
$$
 
It may well be that this, more general, problem, might be
easier, since we have two parameters, $n$ and $r$ for a possible
induction argument.
 
The method of [37] seem to me to be suitable for studying
the {\it symmetry classes} of ASMs ([Ro][Stanl]), and perhaps even,
when q-analogized, the q-enumeration of the
one remaining symmetry class for plane partitions, posed in [Stanley],
that of totally symmetric plane partitions. The case q=1 has been
recently settled, in a brilliant way, by John Stembridge[Stem],
using Pfaffians and the powerful method of Gessel and Viennot[GV].
Thus:
 
{\bf Research Problem IV:} Use the method of [37] to prove
the refined ASM conjecture, its symmetry-classes analogs, and
the q-enumeration of TSPPs.
 
 
\bye
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
