Automatic asymptotics and probability models

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

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 of the product of all the factors. A second aspect of the significance of 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.