On the Square Dependence Problem

School of Mathematics Colloquium
Thursday, September 29, 2011 - 11:05
1 hour (actually 50 minutes)
Skiles 006
Georgia Tech
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to rapidly determine a subsequence whose product is a square (which we call a `square product').  In his lecture at the 1994 International Congress of Mathematicians, Pomerance observed that the following problem encapsulates all of the key issues:  Select integers a1, a2, ..., at random from the interval [1,x], until some (non-empty) subsequence has product equal to a square.  Find good esimates for the expected stopping time of this process.  A good solution to this problem should help one to determine the optimal choice of parameters for one's factoring algorithm, and therefore this is a central question. In this talk I will discuss the history of this problem, and its somewhat recent solution due to myself, Andrew Granville, Robin Pemantle, and Prasad Tetali.