NSF Proposal: Targeted Proof Machines NSF PROPOSAL: Targeted Proof Machines in Combinatorics Doron Zeilberger

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

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

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

Doron Zeilberger

Project Summary 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

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.

NSF Proposal: Targeted Proof Machines

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

1. The current NSF award number is DMS-9500646 for the period 1995-98, totaling $120,000 .

2. Its title was: “Combinatorics, Special Functions, and Computer-Algebra”.

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

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 × n 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)!] … [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 Refined Alternating Sign Matrix Conjecture. The refined version, also conjectured in [MRR], gives a certain explicit expression for the number of n × n alternating sign matrices whose sole first-row ‘1’ is at the r^{th} column. This I did, but not in the proposed way, due to an unexpected, exciting, development.

A few months after the appearance of [12], Greg Kuperberg[Ku] surprised the combinatorialenumeration 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.

Permutation Statistics

Dominique Foata and I have defined an extension of the classical permutation statistics inv and maj parameterized by an arbitrary graph ([14]). We characterized those graphs that have the Mahonian property, i.e. the generating functions of inv and 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’.

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.

Bijective Proofs

On a lighter note, Foata and I found a bijective proof of a linear recurrence for the Schröder-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.

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.

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]) Cosmological Theorem, that concerns Conway-type ‘audioactive’ sequences whose prototype is 1, 11, 21, 1211, 111221, 312211, . . .. 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: 13112221. Conway([Co]) proved that the length of the n^{th} term is asymptotically Cλ^{n}, where λ is 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 arbitrary initial string (except the fixed point 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 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 qEKHAD, that implements the q-WZ method.

Another heavy-duty computer project is [35], where a Maple package, LEGO, is described, that finds instantaneously many formulas that previously took months of human effort, and many new ones. 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 verticallyconvex 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 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).

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 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 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 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 ζ(3)[23], and to give Apéry-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é 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 ζ(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 π, that appeared in his famous letter to Hardy.

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×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.

And Also...

In [2], Jane Friedman, Ira Gessel and I consider ‘fractional’ enumeration of paths. In [3], a constantterm 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égot’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öbner bases to solve discrete Dirichlet problems.

In [26] an interesting and potentially useful problem, that arose in the budding field of Combinatorial Chemistry, is solved. In [33], the powerful and versatile 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.

NSF Proposal: Targeted Proof Machines

4. List of Publications resulting from the NSF award. 1994

1. (With S.B. Ekhad) A one-line WZ proof of a formula of Ramanujan for π, 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) Talmudic lattice path counting, J. Combin. Theory Ser. A 68, 215-217.

3. Proof of q-analog of a constant term identity conjectured by Forrester, J. Combinatorial Theory Ser. A 66, 311-312.

4. Towards a WZ proof of Mehta’s integral, SIAM J. Math. Anal. 25[Askey-Olver issue] , 812-814.

5. (With D. Foata) Combinatorial Proofs of Capelli’s and Turnbull’s Identities from Classical Invariant Theory, Electronic J. of Combinatorics, 1 R1.

6. Chu’s 1303 identity implies Bombieri’s 1990 norm-inequality [Via an identity of Beauzamy and Dégot], Amer. Math. Monthly 101, 894-895.

7. (With L. Ehrenpreis) Two EZ proofs of sin^{2} z + cos^{2} z = 1, Amer Math. Monthly 101, 691.

8. (With C. Orr), A computer algebra approach to the discrete Dirichlet problem, J. Symbolic Computation 18, 87-90. 1995

9. (With S. B. Ekhad) A short and elementary, “formal calculus” proof of the Bieberbach conjecture (after L. Weinstein), Contemporary Math 178, 113-115.

10. The J.C.P. Miller Recurrence for Exponentiating a polynomial and its q-Analog, J. Difference Eqs. and Appls. 1, 57-60.

11. How Joe Gillis discovered Combinatorial Special Function Theory, Math. Intell. 17(2), 65-66. 1996

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

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

14. (With D. Foata) The Graphical Major Index, J. Comp. Appl. Math. [special issue on q-series] 68, 79-101.

Doron Zeilberger

15. (With J. Noonan) Counting Permutations with a prescribed number of ”forbidden” patterns, Advances in Applied Math. 17, 381-407.

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

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

18. An explicit formula for the number of solutions of X^{2} = 0 in triangular matrices over GF(q), Elect. J. Comb. 3(1), R3.

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

20. 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 103, 265.

21. (With M. Petkovsek and H. S. Wilf) “A=B”, AK Peters, Wellesley. 1997

22. (With S. B. Ekhad) Curing the Andrews Syndrome, J. of Difference Equations and Applications 3, xxx-xxx.

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

24. (With I. Nemes, M. Petkovsek, and H. S. Wilf) How to do Monthly Problems on your computer, Amer. Math. Monthly 104, 505-519.

25. Dodgson’s Determinant-Evaluation Rule Proved by TWO-TIMING MEN and WOMEN, Elect. J. of Combinatorics 4(2), [Wilf Festschrift volume], R22.

26. 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) Proof of Conway’s lost cosmological theorem, Elect. Res. Announcements of the AMS 3, 78-82.

28. Math Bite: Proof of an empirical observation made by Amos Oz’s character, Math. Magazine 70 , 291.

29. (With C. Krattenthaler) Proof of a determinant evaluation conjectured by Bombieri, Hunt, and van der Poorten, New York J. of Math. 3, xxx-xxx.

To Appear

30. (With T. Amdeberhan) q-Apery irrationality proofs by q-WZ Pairs, Advances in Applied Mathematics.

31. (With D. Foata) A classic proof of a recurrence for a very classical sequence, J. Combin. Theory Ser. A.

32. (With D. Foata) Combinatorial proofs of Bass’s evaluations of the Ihara-Selberg Zeta function of a graph, Trans. Amer. Math. Soc..

33. The abstract lace expansion, Advances in Applied Mathematics.

34. How much should a nineteenth-century French bastard inherit, J. Difference Eq. Appl. (special issue in honor of Gerry Ladas.).

Submitted

35. Automated counting of LEGO towers.

36. (With J. Noonan) The Goulden-Jackson cluster method: extensions, applications, and implementations.

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.

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.

PROPOSED RESEARCH: 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 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 unpredictable developments will occur that would be far more important than the specific projects proposed here. Even more importantly, the methodology that would emerge in the process of developing specific proof-machines for specific classes of identities and theorems, and the 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.

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≤i,j≤n} ,

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}) (r ≤ i ≤ n + r − 1 , s ≤ j ≤ n + s − 1) .

Once conjectured, the proof of the conjecture becomes routine thanks to Dodgson’s rule that implies the non-linear recurrence:

B(n; r, s) = \frac{B(n − 1; r, s)B(n − 1; r + 1, s + 1) − B(n − 1; r + 1, s)B(n − 1; r, s + 1)}{B(n − 2; r + 1, s + 1)} . (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 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 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.

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ützenberger, that was used to great advantage by the ‘École Bordelaise’ (e.g. [Vi],[DV],[Bo]). In some of the work of the Bordeaux school, computer algebra was used, but only after the grammar was discovered (by humans).

I propose to go 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 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.

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) := |A(n)|. In many cases one is able to partition A(n) into subsets

A(n) = ⋃_{(a_{1},...,a_{k})∈R(n)} B(n; a_{1}, …, a_{k}) ,

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}, …, a_{k}) := |B(n; a_{1}, …, a_{k})| which translates into an algebraic equation for the generating function:

f(z; x_{1}, …, x_{k}) = ∑_{n,a_{1},...,a_{k}≥0} b(n; a_{1}, …, a_{k})z^{n}x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}} ,

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) , b(0, p) = 1, b(m, 0) = 1 ,

from which ∑_{m,p≥0} b(m, p)x^{m}y^{p} = 1/(1 − x − y), and finally a(n) = b(n, n) = coeff. of x^{n}y^{n} in 1/(1 − x − y).

In this trivial case we know that b(m, p) = \binom{m+p}{m}, and a(n) = \binom{2n}{n}, but in the general case one should not expect a closed-form expression for the b(n; a_{1}, …, 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.

Combinatorial Combinatorics

One of the recent breakthroughs in the pharmaceutical industry is 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 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 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 one of the C_{k}’s (k = 1, …, 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_{i_{1}}^{(1)}}, {A_{i_{2}}^{(2)}}, …, {A_{i_{r}}^{(r)}}, with i_{1} = 1, …, a_{1} ; , …, ; i_{r} = 1, …, 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}, …, 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 split-and-mix should be given a fair hearing! Here is how it goes.

At the r^{th} step, suppose that (I_{1}, …, I_{r−1}) turned out to be the best choice from the previous step. Compute the average of f over all n-component binary vectors that start with (I_{1}, …, I_{r−1}, 0), and the average over those vectors that start with (I_{1}, …, 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 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 (χ(statement) is 0 or 1 according to whether the statement is false or true):

∑_{v∈{0,1}^{n}} f(v) = ∑_{v∈{0,1}^{n}} ∑_{k=1}^{n} χ(v_{k} = 1) = ∑_{k=1}^{n} ∑_{v∈{0,1}^{n},v_{k}=1} 1 = ∑_{k=1}^{n} 2^{n−1} = n2^{n−1} .

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.

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}, …, x_{n}] generated by the non-constant symmetric polynomials. It is well known, and easy to see, that the quotient ring K[x_{1}, …, 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}, …, x_{n}, y_{1}, …, y_{n}] generated by the non-constant ‘diagonallysymmetric’ polynomials (i.e. polynomials invariant under the action p(x_{1}, …, x_{n}; y_{1}, …, y_{n}) → p(x_{π(1)}, …, x_{π(n)}; y_{π(1)}, …, y_{π(n)})), for any π in the symmetric group on n elements). Once again, it is easy to see that the quotient ring K[x_{1}, …, x_{n}, y_{1}, …, 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 ≤ 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 who knows? perhaps prove it completely. The approach is to compute the ‘Gröbner basis’ of the ideal J_{n}, but not by computer (at present Maple, and even Macaulay, can only do it for specific n), but generally for general n. Of course, the only hope is to define the basis recursively. Once we have a global description for the Gröbner 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öbner basis: {h_{1}(x_{1}, …, x_{n}), h_{2}(x_{2}, …, x_{n}), …, h_{n}(x_{n})}. Here h_{i} are the complete symmetric functions, that may be defined in terms of the generating function

∑_{i=0}^{∞} h_{i}(y_{1}, …, y_{m})t^{i} = ∏_{j=1}^{m}(1 − y_{j}t)^{−1} .

The leading monomials of the above basis (with respect to the purely lexicographic order induced by x_{1} > x_{2} > … > x_{n}) are {x_{1}, x_{2}^{2}, …, 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}} ⋯ x_{n}^{a_{n}}, with 0 ≤ a_{1} < 1, 0 ≤ a_{2} < 2, …, 0 ≤ 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öbner basis all the polarizations of the h_{r}(x_{r}, …, x_{n}) (i.e. H_{r,s} :=Coeff of t^{s} in h_{r}(x_{r} + ty_{r}, …, x_{n} + ty_{n}), for 1 ≤ r ≤ n, 0 ≤ s ≤ 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öbner 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).

Doron Zeilberger

REFERENCES

[AE] T. Amdeberhan and S. B. Ekhad, A condensed condensation proof of a determinant evaluation conjectured by Kuperberg and Propp, J. Comb. Theory (A), 70(1997), 169-170.

[An1] G. E. Andrews, Plane Partitions III: the weak Macdonald conjecture , Invent. Math. 53(1979), 193-225.

[An2] G. E. Andrews, Plane Partitions V: the T.S.S.C.P.P conjecture , J. Combin. Theory Ser. A, 66(1994), 28-39.

[An3] G. E. Andrews, Pfaff’s Method (III): comparison with the W-Z method, Elect. J. of Combinatorics 3(2)(1996) [Foata Festschrifft], R21.

[AA] G. E. Andrews and R. Askey, Classical orthogonal polynomials, in:“Polynômes Orthogonaux et Applications” (Proceedings, Bar-Le-Duc 1984), edited by C. Brezinski et. al, Lecture Notes in Mathematics 1171 36-62, Springer-Verlag, Berlin, 1985.

[AW] R. Askey and J. Wilson, “Some basic hypergeometric orthogonal Polynomials that generalize Jacobi polynomials”, Memoirs of the Amer. Math. Soc. 319, 1985.

[Ba] H. Bass, The Ihara-Selberg Zeta function of a tree lattice, Internat. J. Math. 3(1992), 717-797.

[BD] B. Beauzamy and J. Dégot, Differential Identities, Trans. Amer. Math. Soc. 347(1995), 2607-2619.

[BHP] E. Bombieri, D.C. Hunt, and A.J. van der Poorten, Determinants in the study of Thue’s method and curves with prescribed singularities, J. Experimental Mathematics 4(1995), 87-96.

[Bo] M. Bousquet-Mélou, “q-Énumération de polyominos convexes”, Publications de LACIM, UQAM, Montréal, 1991.

[Br1] D. Bressoud, Review of “The problems of mathematics, second edition”, by Ian Stewart, Math. Intell. 15(4) (Fall 1993), 71-73.

[Br2] D. Bressoud, “Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture”, Cambridge University Press, 1999 (expected).

[Ca] P. Cartier, Démonstration “automatique” d’identités et fonctions hypergéometriques [d’apres D. Zeilberger], Séminaire Bourbaki, exposé n^{o} 746, Astérisque 206, 41 − 91, SMF, 1992.

[Co] J.H. Conway, The weird and wonderful chemistry of audioactive decay, in: “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, Algebraic languages and polyominoes enumeration, Theor.

NSF Proposal: Targeted Proof Machines

Comp. Sci. 34(1984), 169-206.

[Di] J. Dieudonné, Fractions continuees et polynômes orthogonaux dans l’oeuvre de E.N. Laguerre, in:“Polynômes Orthogonaux et Applications” (Proceedings, Bar-Le-Duc 1984), edited by C. Brezinski et. al, Lecture Notes in Mathematics 1171, 1-15, Springer-Verlag, Berlin, 1985.

[Fi] S. Finch, “Favorite Mathematical Constants Website”,

http://www.mathsoft.com/asolve/constant.

[Ga] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B. 63(1995), 153-158.

[GJ] I. P. Goulden and D. M. Jackson, “Combinatorial Enumeration”, Wiley, NY, 1983.

[Ha] M. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Alg. Comb. 3(1994), 17-76.

[Ki] A.A. Kirillov, On the number of solutions to the equation X^{2} = 0 in triangular matrices over a finite field, Funct. Anal. and Appl. 29 (1995), no. 1.

[KM] A.A. Kirillov and A. Melnikov, On a remarkable sequence of polynomials, preprint.

[KBI] V.E. Korepin, N.M. Bogoliubov and A.G. Izergin, “Quantum Inverse Scattering and Correlation Function”, Cambridge University Press, Cambridge, England, 1993.

[Ku] Greg Kuperberg, Another proof of the alternating sign matrix conjecture, Inter. Math. Res. Notes 1996, no. 3, 139-150.

[MRR] W.H. Mills, D.P. Robbins, and H.Rumsey, Proof of the Macdonald conjecture , Invent. Math. 66(1982), 73-87.

[Pe] M. Petkovsek, Determinants in wonderland, preprint.

[PE] M. J. Plunket and J. A. Ellman, Combinatorial Chemistry and new drugs, Scientific American 276(4) (April 1997), 68-73.

[SW] J. H. Schwarz and C. C. Wu, Evaluations of dual Fermion amplitudes, Physical Letters 47B(1973), 453-456.

[Sta1] R. Stanley, Differentially Finite power series, Europ. J. Comb. 1(1980), 175-188.

[Sta2] R. Stanley, Hipparchus, Plutarch, Schröder, and Hough, Amer. Math. Monthly 104(1997), 344-350.

[Ste] J. Stembridge, The enumeration of totally symmetric plane partitions, Adv. Math. 111(1995), 227-243.

[Vi] X.G. Viennot, Problèmes combinatoire posés par la physique statistique, Séminaire Bourbaki n^{o} 626, Asterisque 121-122(1985), 225-246.

[Wi] L. Williams, Enumerating up-side self avoiding walks on integer lattices, Elec. J. Comb. 3(1)(1996), R31.

[Ze] D. Zeilberger, A holonomic systems approach to special functions identities, J. Comp. Appl. Math. 32(1990), 321-368.

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)← Dym(1965) ← McKean(1955) ← Feller(1926) ← Courant(1910) ← 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 Advances in Applied Mathematics, Annals of Combinatorics, Electronic Journal of Combinatorics, Journal of Difference Equations and Applications, and The Ramanujan Quarterly. He is the proud owner of the computer Shalosh B. Ekhad.

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.

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), xxx-xxx.

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. Proof of the alternating sign matrix conjecture, Elect. J. Combinatorics 3(2) [Foata Festschrift] R13 (1996).

5. (With H.S. Wilf) An algorithmic proof theory for hypergeometric (ordinary and ”q”) multi-

NSF Proposal: Targeted Proof Machines

sum/integral identities, Invent. Math. 108, 575-633 (1992). 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. A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32, 321-368 (1990).

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