This talk is part of the large-scale structures in random graphs workshop
Robert Morris: The sharp threshold for making squares
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,…,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 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.
This event is free to attend but pre-registration is required. On the day please enter through the main entrance of The British Library and make your way to The Alan Turing Institute, which is located on the first floor.
For any queries email Rebecca Lumb at r.c.lumb@lse.ac.uk or call 020 7955 7494.
Event Support: the Heilbronn Institute for Mathematical Research, The Alan Turing Institute and the Department of Mathematics, LSE.
Add comment