PROJECT SUMMARY Automated Enumerative Combinatorics

Doron Zeilberger proposes to continue to develop an infra-structure for automated combinatorial enumeration by systematizing and streamlining the many tools that he has already developed, and creating new ones. The novelty of his approach is that it goes far beyond just implementing known algorithms, but rather develops meta-algorithms that enable the computer to discover, all by itself, new algorithms, that either the same, or any other, computer (possibly running on a numeric, more efficient, computing platform) can use to compute many terms of important, and often seemingly intractable, sequences. This way the computer is performing the kind of research that was formerly the monopoly of humans, but of course, because of its computing powers, and great patience, can go much further.

In particular, Zeilberger hopes to introduce a general computational theory of enumeration schemes, that would include, as very special cases, his, and other researchers’, special-purpose enumeration schemes. This theory should be general enough that in addition to its applications to generating new enumeration theorems for problems that are tractable, would also, hopefully, prove intractability in a yet-to-be-found sense that would be inspired by the computer scientists’ notion of #-P-hardness, but tailored to symbolic rather than numeric computation.

He also hopes to continue, and develop much further, his theory of symbolic-computational probability, that offers an attractive alternative to the currently ruling dogma of Kolmogorov-style measuretheoretic foundation, and since probability and statistics are so important nowadays, should be of considerable potential for applications.

Finally, the PI hopes to continue to develop, and extend the scope of, Wilf-Zeilberger algorithmic proof theory, that has already found many applications in both pure mathematics (topology of knots), applied mathematics (numerical analysis, approximation theory), physics (large-scale computations of Feynman integrals), and even economics.

The intellectual merit of this research lies both in expanding our theoretical knowledge in discrete mathematics, and enhancing our understanding of the role of computers in deriving rigorous mathematical results.

Its broader impact is in that the methodologies developed should be applicable to many other areas of not only pure mathematics, but also applied mathematics, and hence it has potential applications to technological advances in software development, and elsewhere.

This research is in the field of Combinatorics, whose usefulness to science and technology is wellknown. In particular, computer science is largely based on combinatorics, as is electronic communication and the World Wide Web.