Asymptotic enumeration, reinforcement, and effective limit theory

设F是感兴趣数组{a_r r in Z^d}的多元母函数。在单变量(d=1)的情况下，从单变量母函数中获得a_r的估计的广泛适用的方法是已知的。在多变量情况下，从F中减去a_r的渐近性的一般方法是已知的。自1998年以来，PI一直在与不同的合作者一起研究这一问题，沿着以下路线：使用柯西积分公式将a_r写成积分；使用拓扑和几何方法将该积分的一部分简化为剩余计算；利用重新挖掘积分中的鞍点方法求出a_r的渐近表达式。本文所提出的研究将扩展我们能够计算系数a_r的渐近性的函数类F。研究的第二个部分是提供进行计算的算法手段。这项工作的最终目的是为了便于计算。假设一个数组用递归来描述，例如，假设每个数组都是紧靠左下方的所有数组的和。当定义是递归的时，计算其中一个数字可能需要计算前面的每个数字，并且没有明显的方法可以跳到并计算第1,000,000个条目。这项建议中的研究涉及一种实现这一点的方法：计算序列或数组中任意远处的条目，而不必计算每个中间的条目。这些计算是近似值，但速度很快。此外，它们可以自动化，事实上，提案的一部分是编写软件来执行所有必要的计算。

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.