Robin Pemantle
University of Pennsylvania
Title: An upper bound for Pomerance's random squares problem
The following random process is a model for some widely used 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.

This is joint work with Andrew Granville, Ernie Croot and Prasad Tetali.
©2008, Department of Mathematical Sciences
Last Modified: April 22, 2008