NSF Proposal: Symbolic Computation and Combinatorics

NSF PROPOSAL: SYMBOLIC COMPUTATION and COMBINATORICS Doron Zeilberger

Department of Mathematics, Temple University, Philadelphia, PA 19122; zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg .

Project Summary SYMBOLIC COMPUTATION and COMBINATORICS

Doron Zeilberger proposes to continue to develop methodologies for harnessing the great potential of Symbolic Computation to do research in Combinatorics and related areas. In particular he hopes to introduce new computational and conceptual frameworks that would extend the so-called Wilf-Zeilberger proof theory to much wider classes of identities and theorems. He also proposes to continue his efforts in ‘Artificial Combinatorics’, and develop algorithms for the discovery and rigorous proof of theorems in combinatorics whose complexity make them unfeasible for human proofs. This research should be symbiotic, as it is expected that both the concrete results and the underlying methodologies, would help computer algebra developers to improve and enhance their systems.

Note: Previous grants of Zeilberger were supported by the Algebra and Number Theory program, with split-funding from Computational Mathematics and Numeric and Symbolic Computations (Computer Science). The present proposal may also be considered for such split-funding.

Doron Zeilberger

Summary of Results from Previous NSF Support:DMS-9500646 and DMS-9732602

1. The current NSF award number is DMS-9732602 for the period 1997-2000, totaling $180,000 .

2. Its title was: “Targeted Proof Machines in Combinatorics”.

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”.)

Symbolic Computation played a larger and larger role in my research efforts. First, several interesting extensions of WZ theory (that was recognized by the award of the 1998 Steele prize for research to Herb Wilf and myself) were made, mostly in collaboration with my students Tewodros Amdberhan and Akalu Tefera, both of whom were supported at various times by this and the previous NSF grant. Tewodros Amdeberhan and I investigated applications of WZ theory to irrationality proofs, convergence-acceleration formulas, and determinant evaluation. Akalu Tefera developed a very powerful Maple package MultInt that implements the continuous WZ theory for an arbitrary number of variables. Using this package, Tefera found a very interesting new Selberg-like integral formula for several variables.

Computer Algebra was also crucial in the design of the very complicated proof of the Alternating Sign Matrix Conjecture([7]), and in that of the proof of the Refined Alternating Sign Matrix Conjecture([4]), where the punch-line was supplied by the Maple package EKHAD. Both of these proofs are beautifully described (along with background material and Kuperberg’s beautiful simpler proof of the (unrefined, original) ASM conjecture) in Dave Bressoud’s recent book [Br], that won the MAA Bekenbach Book Prize. A nice shorter account was written by Bressoud and Jim Propp ([BP]).

My student Aaron Robertson, who was also supported by this grant for one year, and I, proved a conjecture of Ron Graham about Schur triples ([20]), thereby sharing (with T. Schoen) the prize of $100 that Graham offered. Once again, computer algebra (the Maple package RON) was very important for designing the proof.

My computer, Shalosh B. Ekhad, and I, improved the lower bound for the asymptotics of the number of ternary square-free words ([18]). Together we also proved a conjecture of Alexander Kirillov ([8]). Using WZ theory, Shalosh([22]) proved a conjecture of Scott Ahlgren and Ken Ono, that was needed to finish up a deep conjecture of Frits Beukers ([AO]).

With Dominique Foata, who served as a consultant to this grant, we published several papers in pure combinatorics ([5][10][29][35]). We are especially proud of [29], where a generalization of Hyman Bass’s theorem is proved that was subsequently used by Lin and Wang ([LW]) in Knot Theory.

Shalosh B. Ekhad and I used clever programming and about two weeks of computer time to prove the long-lost ‘Cosmological Theorem’, about the celebrated 1,11,21,1211,111221, ... sequence, supposedly proved, but lost, by Conway ([13]). Because of the length and complexity of the computer proof, it is unlikely that the lost (human) ‘proof’ was complete. Also of the same flavor is the automation of the three-rowed case of David Gale’s game of Chomp ([34]).

Other attempts at ‘artificial combinatorics’ are [17], that automatically finds enumeration schemes for enumerating so-called Wilf classes, and [26] that automatically counts Lego towers, or more prosaically, generalized vertically convex polyominoes. In [27] and [33] the very powerful Goulden-Jackson method is extended and implemented.

In [28], a ‘futuristic’ Geometry textbook is given. It is now incorporated in the much larger, and continuously evolving Maple package RENE, available from the proposer’s website.

In [24], a conjecture of Robbins and Chan was proved. Alex Postnikov and Richard Stanley ([PS]) found interesting ramifications in algebraic combinatorics.

In [30] we give algorithms for finding generating functions for enumerating lattice animals, and self-avoiding polygons and walks of restricted width (both globally and locally).

But the work that I believe to be the most significant, and whose further development constitutes a large part of my planned research to be described below, is the Umbral Transfer-Matrix method ([32]). It combines Gian-Carlo Rota’s seminal notion of umbra with the Transfer-Matrix method, to produce functional equations, as opposed to mere algebraic equations.

Doron Zeilberger

4. List of Publications resulting from the NSF awards in 1996-2000 1996 1.Counting permutations with a prescribed number of forbidden patterns (with John Noonan), Advances in Applied Mathematics 17, 381-407.

2. Self-Avoiding Walks, the language of science, and Fibonacci numbers, J. Stat. Planning and Inference 54, 135-138.

3. Reverend Charles to the aid of Major Percy and Fields-medalist Enrico, Amer. Math. Monthly 103, 501-502.

4. Proof of the refined alternating sign matrix conjecture, New York J. of Mathematics 2, 59-68.

5. (With D. Foata), The graphical major index, J. Comput. Applied Math (special issue on q-series) 68, 79-101.

6. The method of undetermined generalization and specialization illustrated with Fred Galvin’s amazing proof of the Dinitz conjecture, Amer. Math. Monthly 103, 233-239.

7. Proof of the alternating sign matrix conjecture, Elec. J. Comb. 3(2), R13.

8. (With S. B. Ekhad) An explicit formula for the number of solutions of X^{2} = 0 in triangular matrices over GF(q), Elec. J. Comb. 3 R2. 1997

9. (With A. Regev) Proof of a Conjecture about Multisets of Hook Numbers, Annals of Combinatorics 1, 391-394.

10. (With D. Foata) A classic proof of a recurrence for a very classical sequence, J. Comb. Theor.- Ser. A. 80, 380-384.

11. (With C. Krattenthaler) Proof of a Determinant Evaluation Conjectured by Bombieri, Hunt, and van der Poorten, New York J. of Math. 3, 54-102.

12. The Abstract Lace Expansion, Adv. Appl. Math. 19, 355-359.

13. (With S. B. Ekhad) Proof of Conway’s Lost Cosmological Theorem Elect. Res. Announcements of the AMS 3, 78-82.

14. A comparison of two methods for random labellings of balls by vectors of integers in: “Advances in Combinatorial Methods and Applications to Probability and Statistics”, N. Balakrishnan, ed., Birkhauser, 1997 (Mohanty Festschrift). 15.Dodgson’s Determinant-Evaluation Rule Proved by TWO-TIMING MEN and WOMEN Elect.

NSF Proposal: Symbolic Computation and Combinatorics

J. of Combinatorics 4(2), [Wilf Festschrift volume], R22.

16. (With Tewodros Amdeberhan) Hypergeometric Series Acceleration via the WZ method, Elect. J. of Combinatorics 4(2), [Wilf Festschrift volume], R3. 1998

17. Enumeration Schemes, and More Importantly, Their Automatic Generation, Annals of Combinatorics 2, 185-195.

18. (With S. B. Ekhad) There Are More Than 2**(n/17) n-Lettered Ternary Square-Free Words, J. Integer Sequences 98.1.9.

19. (With S. B. Ekhad) Curing the Andrews Syndrome, J. of Difference Equations and Applications 4, 299-310.

20. (With A. Robertson) A 2-Coloring of [1,N] Can Have (1/22)N^{2} + O(N) Monochromatic Schur Triples, But Not Less!, Electronic Journal of Combinatorics 5, R19.

21. (With T. Amdeberhan) q-Apery Irrationality Proofs by q-WZ Pairs, Adv. Appl. Math. 20, 275-283.

22. (With Scott Ahlgren, Shalosh B. Ekhad, and Ken Ono) A Binomial Coefficient Identity Associated to a Conjecture of Beukers, Electronic Journal of Combinatorics 5, R10.

23. How Much Should a Nineteenth-Century French Bastard Inherit, J. Difference Eq. Appl. 3, 385-388. (Special issue in honor of Gerry Ladas.) 1999

24. Proof Of A Conjecture Of Chan, Robbins, and Yuen, Elec. Trans, of Numerical Analysis 9, 147-148.

25. (With A. Robertson and H. Wilf) Permutation Patterns and Continued Fractions, Elec. J. Combinatorics 6, R38.

26. Automated Counting of LEGO Towers, J. Difference Eq. Appl. 5, 323-333.

27. (With J. Noonan) The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations, Difference Eq. Appl. 5, 355-377.

28. (With S. B. Ekhad) PLANE GEOMETRY: An Elementary School Textbook (ca. 2050), Mathematical Intelligencer 21(3), 64-70.

29. (With D. Foata) Combinatorial Proofs of Bass’s Evaluations of the Ihara-Selberg Zeta function of a Graph, Trans. Amer. Math. Soc. 351, 2257–2274.

2000

30. Symbol-Crunching with the Transfer-Matrix Method in Order to Count Skinny Physical Creatures, INTEGERS, 0, A9 .

31. How Berger, Felzenbaum, and Fraenkel Revolutionized COVERING SYSTEMS The Same Way that George Boole Revolutionized LOGIC, to appear in Elect. J. Combinatorics (special issue in honor of Aviezri Fraenkel).

32. The Umbral Transfer-Matrix Method: I. Foundations, to appear in J. Comb. Theory, Ser. A, Rota memorial issue.

33. (With A. Edlin) The Goulden-Jacskon Cluster Method For Cyclic Words, Advances in Applied Mathematics 25, 228-232.

34. Three-Rowed CHOMP, to appear in Adv. Appl. Math.

35. Babson and Streingrimsson’s permutation statistics are indeed Mahonian, (and sometimes even Euler-Mahonian), submitted.

5. Many of my papers are accompanied by Maple packages that are available, free of charge, from my homepage http://www.math.temple.edu/~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.

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.

7. Education and Human Resources Statement.

In 1997, my Ph.D. students John Majewicz, Tewodros Amdeberhan, and John Noonan finished. Amdeberhan and Noonan were each supported for one year in the penultimate grant. 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. He is currently associate professor there.

All these theses combined experimental mathematics with more theoretical investigations and used computer algebra heavily.

Last year (spring 1999), Aaron Robertson and Melkamu Zeleke, who were each supported for one year by this grant, graduated. Aaron accepted a tenure-track appointment at Colgate University. I am very pleased that he is continuing to do very deep research, both computational and theoretical, in Ramsey theory. Melkamu is currently tenure-track assistant professor at William Patterson University. Melkamu is collaborating very nicely with colleagues in bijective combinatorics.

This year (spring 2000) Akalu Tefera and Anne Edlin received their Ph.D. under my direction. Akalu just started a tenure-track assistant professorship at Grand Valley State University ( in Michigan), and Anne is assistant professor at Holy Family College (New Jersey). As I mentioned above Akalu developed sophisticated software for the continuous WZ method. Anne extended and implemented the Goulden-Jackson method to cyclic words.

Right now I only have one student, Mohamud Mohammed, who is very strong and promising. I also have several other strong prospective students. The research conducted by my students involves large-scale computing that should yield software 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. Since 1988, 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 [2] 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 (that later appeared in the Elec. J. Combinatorics), that won third prize in the 1996 International Science Fair. Lauren is currently a senior at Harvard and plans to specialize in combinatorics.

Doron Zeilberger

PROPOSED RESEARCH: SYMBOLIC COMPUTATION and COMBINATORICS Introduction While the so-called Wilf-Zeilberger (WZ) proof theory and the holonomic paradigm, that has been successfully implemented in all the major computer algebra systems, and are widely used by mathematicians and scientists, can handle a rather wide class of summations and integrations, I feel that it is still but the tip of an iceberg. In this proposal, I will describe my plans to extend WZ theory to sums and integrals with arbitrarily many summation and integration signs, like the celebrated Selberg and Mehta integrals and the Macdonald-Dyson constant term identities for the infinite families of root systems. I also hope to go far beyond the holonomic paradigm, trying to find wider and wider computationally decidable ansatzes. I also hope to continue to do ‘Artificial Combinatorics’. Here one looks at a class of combinatorial problems, for example that of enumerating so-called Wilf classes, and tries to teach the computer how to do research, by formalizing methods and tricks used, usually implicitly, in human research, and programing them. Once the computer ‘learned’ how to perform these ‘tricks’ it can go much further, of course. In addition, I also hope to continue my work on a general theory of permutation statistics, in collaboration with Dominique Foata. WZ Theory: Chapter II Recall the ([WZ]) Fundamental Theorem of Multi-WZ Theory (Discrete Version) ‘Whenever’ we want to prove an identity of the form:

∑_{k_{1}} … ∑_{k_{r}} NICE(n; k_{1}, …, k_{r}) ≡ 1 ,

There exist NICE′_{1}, NICE′_{2}, …, NICE′_{r} such that

Δ_{n}NICE = ∑_{i=1}^{r} Δ_{k_{i}}NICE′_{i}

Furthermore, R_{i} := NICE′_{i}/NICE, (i = 1, …, r), are rational functions of (n; k_{1}, …, k_{r}). We also have the : Fundamental Theorem of Multi-WZ Theory (Continuous Version) ‘Whenever’ we want to prove an identity of the form:

∫ … ∫ NICE(n; x_{1}, …, x_{r}) dx_{1} … dx_{r} ≡ 1 , there exist NICE′_{i}(n; x_{1}, …, x_{r}) (i = 1, …, r), such that

Δ_{n}NICE = ∑_{i=1}^{r} \frac{∂}{∂x_{i}} NICE′_{i} .

Furthermore, R_{i} := NICE′_{i}/NICE are rational functions of (n; x_{1}, …, x_{r}).

Note that the mere existence of NICE′_{i} (or equivalently the R_{i}), together with the trivially verifiable case n = 0, implies the identity, since,

Δ_{n} ∫ … ∫ NICE = ∫ … ∫ Δ_{n}NICE = ∑_{i=1}^{r} ∫ … ∫ \frac{∂}{∂x_{i}} \{NICE′_{i}\} = 0 ,

(because the NICE′_{i} are of compact support).

Two famous examples are

∫_{0}^{1} … ∫_{0}^{1} ∏_{i=1}^{r} t_{i}^{x}(1 − t_{i})^{y} ∏_{1≤i<j≤r}(t_{i} − t_{j})^{2z}dt_{1} … dt_{r}

= ∏_{j=1}^{r} \frac{(x + (j − 1)z)!(y + (j − 1)z)!(jz)!}{(x + y + (r + j − 2)z + 1)!z!} .  (Selberg)

and

∫_{|z_{1}|=1} … ∫_{|z_{r}|=1}\{ ∏_{1≤i≠j≤r}(1 − z_{i}/z_{j})^{a}\}\frac{dz_{1}}{z_{1}} … \frac{dz_{r}}{z_{r}} = \frac{(ra)!}{a!^{r}} .  (Dyson)

[This identity has a good pedigree. It was conjectured in 1960 by Dyson, and proved a year later by Gunson, and by Ken Wilson of Nobel (Renormalization Group) fame. The ‘book’ proof was given, in 1970, by the great statistician I.J. Good.]

At present, using the multi-WZ method, Shalosh B. Ekhad can prove (Selberg),(Dyson) (and any other such multi-dimensional identity), for each specific number of variables r. In practice, Shalosh can do it for r = 1, 2, 3, 4. It did. Then the humans (in this case, myself and Wilf), looked at Shalosh’s proof, detected a common pattern, and it was a trivial, albeit human, step, to formulate a WZ proof for a general r (see [WZ] for a proof of (Selberg)).

But, right now, we still need this human factor.

Another famous example is the Macdonald constant term conjecture (that Ian Macdonald talked about in his plenary talk, at ICM 1998). Right now, Shalosh can do it (in principle) for each specific root system, but it takes a human of the caliber of Cerednick to do it for all root systems.

It would be nice to be able to automatically prove such Selberg-type integrals for arbitrary dimension, keeping the dimension n as a symbol. For that one would have to define precisely the notion of hypergeometric function (what I called ‘nice’) of r variables, where r is not merely a symbol denoting an integer, but is a symbol period. Prototype nice functions should be:

(∑_{i=1}^{r} n_{i})!

∏_{i=1}^{r} NICE(n_{i})

and, probably

∏_{i=1}^{r−1} NICE(n_{i} + n_{i−1}) ,

∏_{1≤i<j≤r} NICE(n_{i} + n_{j}) ,

where NICE is a nice function of a single discrete variable.

The ‘language’ should contain, as primitive symbols, ∏ and ∑, that would have to be incorporated into the algorithm.

We also need a notion of ‘global’ niceness for NICE′_{1}, …, NICE′_{r}, i.e., it does not suffice that NICE′_{i} would be nice in its arguments, but we should insist that NICE′_{i}, when also viewed as a function of its subscript i, is nice, in a sense yet to be made precise. Somehow, we should also bring in symmetry.

So hopefully, if this plan succeeds, Macdonald’s constant term identities, the Mehta integral, the Selberg integral, and their kin, would be fully automated.

Beyond the Holonomic Paradigm

Recall that a continuous function of one variable f(x) is holonomic (a.k.a. D-finite) if it satisfies a homogeneous linear differential equation with polynomial coefficients. For functions of several variables one insists on equations on each variable. While this class includes all polynomials and functions of hypergeometric type, and hence most of the classical functions of mathematical physics, it is still a rather special class.

It should be interesting to explore larger classes that would also carry their own proof theory. One obvious choice would be solutions of differential equations with holonomic coefficients, that one could call super holonomic. The simplest such function is e^{e^{x}}. However, preliminary investigations show that a richer theory can be obtained by considering the narrower class of solutions of differential equations with algebraic coefficients.

Another interesting problem would be to extend WZ theory to multibasic sums, i.e. q-hypergeometric sums with several bases.

Enumeration Schemes

Suppose that we have to find a ‘formula’ (in the sense of Wilf, i.e. a polynomial-time algorithm) for computing a_{n} := |A_{n}|, where A_{n} is an infinite family of finite sets, parameterized by n. Usually A_{n} is a natural subset of a larger set B_{n}, and is defined as the set of members of B_{n} that satisfy a certain set of conditions C_{n}. For example if A_{n} is the set of permutations on {1, 2, …, n}, then B_{n} may be taken as the set of words of length n over the alphabet {1, 2, …, n}, and C_{n} can be taken as the condition: ‘no letter can appear twice’. A naive algorithm for enumerating A_{n} would be to actually construct the set, by examining the members of B_{n}, one by one, checking whether they satisfy C_{n}, and admitting those that qualify. Then a_{n}=Cardinality of A_{n}.

But a much better approach would be to find a structure theorem that expresses A_{n}, using unions, Cartesian products, and possibly complements, of well known sets. Failing this, it would be also nice to express A_{n}, recursively, in terms of A_{n−1}, A_{n−2}, …, and easy-to-count sets, getting a recurrence formula. Going back to the permutation example, Levi Ben Gerson proved the structure theorem A_{n} ≡ {1, 2, …, n} × A_{n−1}, from which he deduced the recurrence a_{n} = na_{n−1}, enabling a polynomial-(in fact linear-) time algorithm for computing a_{i}, for 1 ≤ i ≤ n.

Alas, this is not always easy, and for many enumeration sequences, e.g. the number of self-avoiding walks, may well be impossible, and who knows, perhaps one day even provably impossible.

It is conceivable, however, that a combinatorial family A(n), does not possess a recursive structure by itself, but by refining it, using a suitable parameter, one can partition A(n) into the disjoint union:

A(n) = ⋃_{i=1}^{n} B(n, i) ,

and try and find a structure theorem for the two-parameter family B(n, i). This will imply a recurrence for the cardinalities b(n, i) := |B(n, i)|, that would enable a fast algorithm for a(n) = ∑_{i=1}^{n} b(n, i).

Sometimes, not even the B(n, i) suffice. Then we could try to partition B(n, i) into the following disjoint union:

B(n, i) = ⋃_{j=1}^{i−1} C_{1}(n, i, j) ∪ ⋃_{j=i+1}^{n} C_{2}(n, i, j) ,

and try to express C_{1}(n, i, j) and C_{2}(n, i, j) in terms of A(m), B(m, i′), C_{1}(m, i′, j′), and C_{2}(m, i′, j′), with m < n. One can keep going indefinitely. If this process halts after a finite number of refinements, then we have indeed a formula (in the sense of Wilf) for a(n).

In [17] I showed how to enumerate Wilf classes, but the ‘success rate’ was only about 20 percents. I propose to refine and enhance the notion of enumeration schemes to make the success rate closer to 100 percents. I also hope to use the same circle of ideas in enumerating words, special kinds of graphs, and other combinatorial families.

The Umbral Transfer-Matrix Method

The Finite Transfer-Matrix method is used to weight-enumerate paths on a finite digraph, see [30] for a detailed exposition. Here, we will be considering directed graphs whose set of vertices, V, is infinite, with possibly multiple edges. Even though there are infinitely many vertices, we will assume that they can be partitioned into a finite union of vertex-families, {v_{1}, …, v_{n}}, such that each family v_{i} is an l_{i}-parameter infinite family, parameterized by the l_{i} discrete variables (a_{1}, …, a_{l_{i}}), where (a_{1}, …, a_{l_{i}}) ranges over a well-defined subset D_{i} of {0, 1, 2, 3, …}^{l_{i}}. So the vertex set of our infinite digraph can be partitioned as follows

V = ⋃_{i=1}^{n} ⋃_{(a_{1},...,a_{l_{i}})∈D_{i}} v_{i}(a_{1}, …, a_{l_{i}}) .

We will also assume that for any pair of vertex types v_{i} and v_{j}, there are K(i, j) ≥ 0 families of edges, and for each of k = 1, …, K(i, j), the type-k edge coming out of vertex v_{i}(a_{1}, …, a_{l_{i}}) may wind up in any of the vertices v_{j}(b_{1}, …, b_{l_{j}}), where (b_{1}, …, b_{l_{j}}) may belong to a well-defined subset of D_{j}, let’s call it E_{i,j}^{(k)}(a_{1}, …, a_{l_{i}}). We also assume that every such edge has a certain weight given by a weight-function

W_{i,j}^{(k)}(a_{1}, …, a_{l_{i}}; b_{1}, …, b_{l_{j}}) .

The weight of a path P, W t(P), is the sum of the weights of its participating edges. We are interested in computing the weight-enumerator of all paths

∑_{P ∈P aths} q^{W t(P)} ,

either explicitly, and failing this, to have a polynomial-time algorithm for computing the series expansion, i.e. the first N terms of its power-series expansion, for any given N.

We now digress to define a Rota-Operator.

Definition of an Atomic Rota-Operator: An Atomic Rota operator from the ring of formal power series in r variables Z(q)(x_{1}, …, x_{r}) to the ring of formal power series in s variables Z(q)(y_{1}, …, y_{s}) (with coefficients from the ring of integer-coefficient formal power-series in q), is an operator of the form

T [f(x_{1}, …, x_{r})] = R(q, y_{1}, …, y_{s})D_{x_{1}}^{α_{1}} … D_{x_{r}}^{α_{r}}f(x_{1}, …, x_{r})|_{{x_{1}=m_{1},...,x_{r}=m_{r}}} ,  (ARO)

where R(x, q_{1}, …, x_{r}) is a rational function of all its arguments, D_{x_{1}}, …, D_{x_{r}} are the differentiation operators with respect to x_{1}, …, x_{r} respectively, α_{1}, …, α_{r} are non-negative integers, and m_{1}, …, m_{r} are each monomials in the variables (q, y_{1}, …, y_{s}).

An Example of an Atomic Rota Operator:

f(x_{1}, x_{2}) → \frac{q^{3}y_{1}y_{2}y_{3}}{(1 − qy_{1})(1 − q^{2}y_{1}y_{2}y_{3})}D_{x_{1}}D_{x_{2}}^{3}f(y_{1}y_{2}y_{3}, qy_{3}) .

NSF Proposal: Symbolic Computation and Combinatorics

Definition of a Rota Operator: A Rota Operator is a sum of Atomic Rota Operators. It turns out that in many applications, the following property holds: The Umbral Axiom For every pair of vertex types, v_{i}, v_{j}, and for each of its K(i, j) edge-types connecting them, the following operator from Z(q)(x_{1}, …, x_{l_{i}}) to Z(q)(y_{1}, …, y_{l_{j}}), defined on the basis of monomials by

x_{1}^{a_{1}} ⋯ x_{l_{i}}^{a_{l_{i}}} → ∑_{(b_{1},...,b_{l_{j}})∈E_{i,j}^{k}(a_{1},...,a_{l_{i}})} q^{W_{i,j}^{(k)}(a_{1},...,a_{l_{i}};b_{1},...,b_{l_{j}})}y_{1}^{b_{1}} ⋯ y_{l_{j}}^{b_{l_{j}}}

is an atomic Rota operator, let’s call it Q_{i,j}^{k}. Also, let’s define the transition-operator from vertices of type i to vertices of type j (1 ≤ i, j ≤ n), by

P_{i,j} := ∑_{k∈K(i,j)} Q_{i,j}^{k} .

which by our assumption are all Rota operators. Let’s define the mishkal of a path P, in our digraph, that ends with the vertex v_{i}(a_{1}, …, a_{l_{i}}) by

q^{W t(P)}x_{1}^{a_{1}} … x_{l_{i}}^{a_{l_{i}}} ,

and let’s define the total mishkal of all the paths that end in a type-i vertex by

F_{i}(q; x_{1}, …, x_{l_{i}}) := ∑_{P} mishkal(P) ,

where the sum extends over the infinite set of paths that end in a type-i vertex. It follows immediately from this set-up that the n formal power series F_{j}, (j = 1, …, n) satisfy the following system of n differential-functional equations

F_{j} = [j ∈ Start] + ∑_{i=1}^{n} P_{i,j}F_{i} .  (F undamentalSystem)

In the lucky case, we can solve this system explicitly, but at any rate, we can use it iteratively to find a series expansion in q. In either case, the desired weight-enumerator is given by

∑_{j∈F inish} F_{j}(q; 1, …, 1) .

Note that the variables x_{1}, …, x_{l_{i}} corresponding to the l_{i}-parameter vertex type i, for i = 1, …, n, serve as catalysts, all to be discarded (i.e. substituted by 1) at the end of the “reaction”.

I propose to use this set-up to study important subsets and supersets of ‘hard-to-count’ combinatorial families that arise in statistical physics: lattice animals, self-avoiding walks and polygons, and percolation. Here the number of components in each vertical slice is bounded, but the size itself is indefinitely large. So this can capture many more creatures than the finite-transfer matrix methods in which the creatures are confined to a strip. Even more interesting is the kind of functional equations for the generating functions of these sophisticated toy models. Recall that in the finite transfer-matrix method, one always gets rational functions making the critical behavior clearly unphysical and mathematically boring. The kind of functional equations that one should get now resemble those of the Renormalization Group method, and should give ‘interesting’, and hopefully closer-to-reality, critical behavior.

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, 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 ≤ n ≤ 7. The general formula,n!, and its, completely rigorous, inductive proof, can be found in “Sefer Ma’asei Khosev” written in the 14th century by Rabbi Levi Ben Gerson.

The more refined counting of permutations, according to various 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ützenberger. 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örner, Jennifer Galovich, Adriano Garsia, Kevin Kadell, Don Rawlings, Jeff Remmel, Bruce Sagan, Richard Stanley, Dennis Stanton, Dennis White, Michelle Wachs, Xavier (Gérard) Viennot and many others.

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) := ∑_{π∈S_{n}} q^{stat(π)} ,

a) Closed form? (like in the case of inv and 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 ∑_{n=0}^{∞} \frac{F_{n}(q)z^{n}}{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}, …, q_{k}) := ∑_{π∈S_{n}} q_{1}^{stat_{1}(π)} … q_{k}^{stat_{k}(π)} ?

In a very interesting recent paper, Eric Babson and Einer Steingrimsson [BS] initiated their own theory of ‘pattern-statistics’ that include most of the known permutation statistics. They made several conjectures that Foata and I proved, by combining symbolic computation and ‘human combinatorics’. We hope that our ideas, combined with Babson and Steingrimsson’s seminal concept will prove useful.

Doron Zeilberger

REFERENCES

[A0] S. Ahlgren and K. Ono A Gaussian hypergeometric series evaluation and Apéry number congruences, J. Reine Angew. Math. 518 (2000), 187-212.

[BS] Eric Babson and Einer Steingrimsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Loth. Comb. [http://radon.mat.univie.ac.at/~slc/] 44 (2000), B44b.

[Br] David Bressoud, “Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture”, Cambridge University Press and The Mathematical Association of America, 1999.

[BP] David Bressoud and James Propp, How the alternating sign conjecture was solved, Notices Amer. Math. Soc. 46 (1999), 637-646.

[LW] Xiao-Song Lin and Zhenghan Wang, Random Walk on Knot Diagrams, Colored Jones Polynomial and Ihara-Selberg Zeta Function, preprint, http://xxx.lanl.gov : math.GT/9812039.

[PS] Alexander Postnikov and Richard Stanely, Deformation of Coxeter hyperplane arrangements,

preprint, http://xxx.lanl.gov :  math.CO/9712213.

[WZ] Herb Wilf and Doron Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and ”q”) multisum/integral identities, Invent. Math. 108, 575-633 (1992). Biographical Sketch-Doron Zeilberger, P.I. a. Professional Preparation University of London, Mathematics, B.Sc. (With First Class Honours), 1972. Weizmann Institute of Science, Mathematics, Ph.D., 1976. Institute for Advanced Study, Mathematics, member, 1977-1978. b. Appointments 1990-present: Temple University, Laura H. Carnell Professor(2000-), Professor (1990-1999). 1983-1990: Drexel University, Professor (1988-1990), Associate Professor (1983-1988). 1982-1983: University of Pennsylvania, Lecturer. 1980-1982: Weizmann Institute of Science, Senior Scientist. 1979-1980: University of Illinois, Urbana, Visiting Lecturer. 1978-1979: Georgia Institute of Technology, Visiting Assistant Professor.

NSF Proposal: Symbolic Computation and Combinatorics

c. (i) Five Relevant Publications

1. (With M. Petkovsek and H. S. Wilf) A=B, AK Peters, Wellesley, (1996).

2. (With C. Krattenthaler) Proof of a Determinant Evaluation Conjectured by Bombieri, Hunt, and van der Poorten, New York J. of Math. 3(1997), 54-102.

3. Theorems for a price: Tomorrow’s semi-rigorous mathematical culture, Notices of the Amer. Math. Soc. 40 # 8, 978-981 (Oct. 1993). Reprinted: Math. Intell. 16, no. 4, 11-14 (Fall 1994).

4. A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32, 321-368 (1990).

5. (With H.S. Wilf) An algorithmic proof theory for hypergeometric (ordinary and ”q”) multisum/integral identities, Invent. Math. 108, 575-633 (1992). c. (ii) Five Other Publications

1. (With G. Almkvist) The method of differentiating under the integral sign, J. Symbolic Computation 10, 571-591 (1990).

2. The method of creative telescoping, J. Symbolic Computation 11, 195-204 (1991).

3. Proof of the alternating sign matrix conjecture, Elect. J. Combinatorics 3(2) [Foata Festschrift] R13 (1996).

4. (With D. Bressoud) A proof of Andrews’ q-Dyson conjecture, Discrete Math. 54, 201-224 (1985).

5. Sister Celine’s technique and its generalizations, J. Math. Anal. Appl. 85, 114-145 (1982). d. Synergetic Activities The Wilf-Zeilberger Algorithmic Proof Theory has been widely used by mathematicians and scientists alike, and has been implemented in all major computer algebra systems. Currently, the National Institute of Standards and Technology is ‘wiring’ the classic handbook of mathematical functions (the most widely cited book in science), by using WZ theory as its driving force. My many Maple packages, in addition to doing the specific tasks that they were designed to do, when taken together, constitute a whole ‘research methodology’ for doing computer-assisted and computer-generated research. e. Collaborators and Advisor e(i). Recent Collaborators Tewodros Amdeberhan (deVry Inst.), Shalosh B. Ekhad (Temple Univ.), Dominique Foata (Univ. of Strasbourg), Christian Krattenthaler (Univ. of Vienna), Istvan Nemes (RISC-Linz), John Noo-

Doron Zeilberger

nan (Mount Vernon Nazarene College), Marko Petkovsek (University of Slovenia), and Herb Wilf (University of Pennsylvania). e(ii). Graduate Advisor Harry Dym (Weizmann Institute). e(iii). Thesis Advisor So far, ten students received their Ph.D. degree under by supervision.

* Sheldon Parnes (Industry, Coloardo), 1993.

* Ethan Lewis (IBM, Israel) 1994.

* Craig Orr (NSA), 1994.

* John Majewicz (Comm. College of Philadelphia), 1997.

* John Noonan (Mt. Vernon Nazarene College, OH), 1997.

* Tewodros Amdeberhan (deVry Inst. of Tech., NJ), 1997.

* Melkamu Zeleke (William Patterson Univ., Wayne, NJ), 1998.

* Aaron Robertson (Colgate Univ., Hamilton, NY), 1999.

* Akalu Tefara (Grand Valley State Univ., MI), 2000.

* Anne Edlin (Holy Family College, NJ), 2000. Short Biography-Dominique Foata, consultant Dominique Foata received his doctorat de état under Marcel-Paul Schützenberger 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.