Asymptotic enumeration, reinforcement, and effective limit theory

点击翻译按钮获取中文摘要

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 obtainingestimates of a_r from the univariate generating function.In the mutlivariate case, no general method is known forextracting asymptotics of a_r from F. The PI has been workingon this with various collaborators since 1998, along the followinglines: use the Cauchy integral formula to write a_r as an integral;use topological and geometric methods to reduce part of thisintegral to a residue computation; use saddle point methodson the remining integral to find an asymptotic expression for a_r.The research proposed here will extend the class of functions F forwhich we are able to compute asymptotics for the coefficients a_r.A second component of the research is to provide algorithmicmeans for doing the computations.The ultimate goal of this work is to facilitate computation.Suppose an array of numbers is described by a recursion; forexample, 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 theones before, and there is no evident way to jump in and computesay the 1,000,000th entry. The research in this proposal concernsa way to do just that: to compute an entry arbitrarily far outin the sequence or array without having to compute each intervening entry. These computations are approximate but theyare fast. Moreover, they can be automated, and in fact a partof the proposal is to write software that will perform all thenecessary computations.