School of Mathematical Sciences

The sharp threshold for making squares. menu

The sharp threshold for making squares.

Paul Balister (University of Memphis)
Fri, 29/04/2016 - 16:15
M103 (Mathematical Sciences)
Seminar series: 

Many of the fastest known algorithms for factoring large integers rely on finding subsequences of randomly generated sequences of integers whose product is a perfect square. Motivated by this, in 1994 Pomerance posed the problem of determining the threshold of the event that a random sequence of $N$ integers, each chosen uniformly from the set $\{1,\dots,x\}$, contains a subsequence, the product of whose elements is a perfect square. In 1996, Pomerance gave good bounds on this threshold and also conjectured that it is {\em sharp}.

In a paper published in Annals of Mathematics in 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In recent work, we have confirmed this conjecture. In my talk, I shall give a brief overview of some of the ideas used in the proof, which relies on techniques from number theory, combinatorics and stochastic processes. Joint work with B\'ela Bollob\'as and Robert Morris.