The sharp threshold for making squares

Vortrag von Prof. Dr. Rob Morris

Datum: 09.05.18  Zeit: 17.15 - 19.00  Raum: Y27H12

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, at the 1994 ICM 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}.

A few years ago, in major breakthrough, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In the talk we will discuss a proof of their conjecture, which combines techniques from number theory and probabilistic combinatorics. In particular, at the heart of the proof lies a self-correcting random process of non-uniform hypergraphs.

Joint work with Paul Balister and Béla Bollobàs.