Automatic asymptotics and probability models

拟议的研究分为两类。第一个是关于从多变量生成函数导出渐近的计算装置的发展。这是用复解析方法完成的。在一个变量中，分析组合学的学科得到了很好的发展，但在多个变量中，方法才刚刚开始被理解。生成函数的奇异变化的几何性质变得重要，需要在构造适当的变形和有效地计算所得到的积分方面做进一步的工作。建议研究的第二个领域涉及几个概率模型的分析。其中之一是求随机整数乘积的完全平方。该模型是因式分解的筛分方法中出现的。在过去的工作中，我们分析了一种被认为具有渐近最短可能运行时间的平方查找算法。事实上，我们知道它在最佳运行时间的30%以内，但我们想证明它实际上是渐近最优的。一个正的结果将告诉我们该算法实际上是在寻找一个渐近最优见证。提案中的其他概率模型包括指数增长树的搜索和抽样，以及计算似然函数的鞍点积分。这里有一个“大局观”的描述，说明这项研究是如何与一般科学兴趣的问题相联系的。生成函数可能是用于计数或估计组合类大小的最广泛应用的技术。生成函数编码递归信息：当类的大小满足递归时，存在可处理的生成函数。通常更需要对这些数字进行显式（非递归）描述。例如，斐波那契数的递归定义，a(n) = a(n-1) + a(n-2)，虽然非常简单，但对于大小估计来说，不如显式公式a(n) = (1+o(1)) b^n有用，其中b是黄金比例。如何将单变量生成函数转化为显式渐近公式已经有几十年的历史了。PI和其他人最近的研究将这种知识扩展到生成多元数组的函数。提出的研究的一个重要组成部分是这些新的多变量技术的自动化，这需要开发有效的工具来计算多项式的代数和拓扑不变量。提出的平方子积研究的效用的一个方面是显而易见的：它为我们提供了一个基本的和广泛使用的因子分解算法的主要组件的运行时间。分析的方法是证明随机整数的分解在适当的意义上收敛于某一泊松过程。概率极限定理在解析数论中很常见，但这种分析所需的极限结构需要跟踪所有因子的乘积的大小。因此，提出的研究意义的第二个方面是，它将开发一个包含比以前的模型更多信息的数论概率模型，并且随机整数的实际分解可能被严格地证明是收敛的。提案中关于指数增长图的搜索和抽样部分的动机部分来自于均匀抽样和大小估计之间的联系。

The proposed research falls into two categories. The first concerns development of a computational apparatus to derive asymptotics from mutlivariate generating functions. This is done using complex analytic methods. In one variable, the subject of analytic combinatorics is well developed, but in more than one variable, methods are only now beginning to be understood. Geometric properties of the singular variety of the generating function become important, requiring further work both in the construction of appropriate deformations and in the effective computation of the resulting integrals.The second area of proposed research concerns analysis of several probability models. One of these is to find perfect squares in products of random integers. This model, due to Pomerance, arises in sieving methods of factorization. In past work, we analyzed a square-finding algorithm believed to have asymptotically the shortest possible run time. In fact we know it to be within about 30% of the best run time, but would like to prove that it is in fact asymptotically optimal. A positive result would tell us the algorithm in fact searches for an asymptotically optimal witness. Other probability models in the proposal include searches and sampling in trees of exponential growth, and computations saddle point integrals for likelihood functions. Here follows a "big-picture" description of how this research is situated with respect to problems of general scientific interest.Generating functions are perhaps the single most widely applicable technique for counting or estimating the size of combinatorial classes.Generating functions encode recursive information: tractable generating functions exist when the sizes of the classes satisfy a recursion. An explicit (non-recursive) descriptions of these numbers is usually more desirable. For example, the recursive definition of the Fibonacci numbers, a(n) = a(n-1) + a(n-2), while remakably simple, is less useful for size estimation than the explicit formula a(n) = (1+o(1)) b^n where b is the Golden ratio. It has been known for several decades how to convert one-variable generating functions into explicit asymptotic formulae. Recent research of the PI and others extends this knowledge to generating functions for multivariate arrays. An important component of the proposed research is the automation of these new mutlivariate techniques, which requires development of effective tools for computing algebraic and topological invariants of polynomials. One aspect of the utility of the proposed research on square subproducts is obvious: it gives us the run time of the main component of a basic and widely used factoring algorithm. The method of analysis is to show that the factorizations of random integers converge, in an appropriate sense, to a certain Poisson process. Probability limit theorems are common in analytic number theory, but the limit structure required for this analysis requires keeping track of the magnitude ofthe product of all the factors. A second aspect of the significanceof the proposed research, therefore, is that it will develop a number-theoretic probability model containing more information than previous models, and to which actual factorizations of random integers may be shown rigorously to converge. The part of the proposal concerning searches and sampling on graphs of exponential growth is motivated by in part by the connection between uniform sampling and size estimation.