Automatic asymptotics and probability models

自动渐近和概率模型

• 批准号: 0905937
• 负责人: Robin Pemantle
• 金额: $ 32.61万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-06-01 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0905937&HistoricalAwards=false
• 关键词: Automatic; asymptotics; probability; models

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.

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