- Series
- School of Mathematics Colloquium
- Time
- Thursday, September 29, 2011 - 11:05am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Ernie Croot – Georgia Tech
- Organizer
- Brett Wick
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.