Asymptotic enumeration, reinforcement, and effective limit theory

Investigator(s):

Robin Pemantle (PI) ; Mark Ward (Co-PI)

Sponsor:

University of Pennsylvania, PA 19104 2158987293

Start Date/Expiration Date

2006-05-01 to 2007-04-30 (amended 2006-04-26)

Awarded Amount to Date:

$65,000

Abstract: Let F be a multivariate generating function for an array {a_r r in Z^d} of numbers of interest. In the univariate (d=1) case broadly applicable methods are known for obtaining estimates of a_r from the univariate generating function. In the mutlivariate case, no general method is known for extracting asymptotics of a_r from F. The PI has been working on this with various collaborators since 1998, along the following lines: use the Cauchy integral formula to write a_r as an integral; use topological and geometric methods to reduce part of this integral to a residue computation; use saddle point methods on the remining integral to find an asymptotic expression for a_r. The research proposed here will extend the class of functions F for which we are able to compute asymptotics for the coefficients a_r. A second component of the research is to provide algorithmic means for doing the computations. The ultimate goal of this work is to facilitate computation. Suppose an array of numbers is described by a recursion; for example, suppose each one is the sum of all the ones immediatley below and to the left. When the definition is recursive, computing one of the numbers may require computing each of the ones before, and there is no evident way to jump in and compute say the 1,000,000th entry. The research in this proposal concerns a way to do just that: to compute an entry arbitrarily far out in the sequence or array without having to compute each intervening entry. These computations are approximate but they are fast. Moreover, they can be automated, and in fact a part of the proposal is to write software that will perform all the necessary computations.

NSF Org:

DMS - Division of Mathematical Sciences

Award Number:

0603821

Award Instrument:

Continuing grant

Program Manager:

Dean M Evasius
DMS Division of Mathematical Sciences
MPS Directorate for Mathematical & Physical Sciences

NSF Program(s):

PROBABILITY

Field Application(s):

Other nsf.applications NEC

Program Reference Code(s):

UNASSIGNED, 0000

Program Element Code(s):

1263