Run time bounds for a model related to sieving

Run time bounds for a model related to sieving

-
Robin Pemantle, Tel-Aviv University and IAS
Fine Hall 314

The following problem is very close to one arising in factorization algorithms.Generate random numbers in the interval $[1,N]$ until some subset has a product which is a square. How long does this take (and how can you tell when you're done)?
Crude analogies suggest that this stopping time has a very sharp threshold. We prove upper and lower bounds that are within a factor of $4/\pi$ and conjecture that our upper bound is asymptotically sharp. Joint work with Andrew Granville, Ernie Croot and Prasad Tetali.