The Pomerance’s conjecture is true: the threshold for making squares is sharp

You need to know: Perfect square, limits, notation P for the probability, independent events, selection uniformly at random.

Background: We say that a finite sequence S of positive integers has a square dependence if it has a subset $A\subset S$ such that the product $\prod\limits_{n\in A}n$ of all integers in A is a perfect square. For $x>1$ , let us select integers $a_1,a_2,\dots$ independently uniformly at random from $[1,x]$ , and let T be the smallest integer such that the sequence $a_1,a_2,\dots, a_T$ has a square dependence.

The Euler-Mascheroni constant is the limit $\gamma=\lim\limits_{n\to\infty}\left(-\log n+\sum\limits_{k=1}^n\frac{1}{k}\right) = 0.577...$ . Integer n is called y-smooth if all of its prime factors are at most y. Let $\Psi(x,y)$ be the number of y-smooth integers up to x, $\pi(y)$ be the number of primes up to y, and let $J(x) = \min\limits_{2\leq y \leq x} \frac{\pi(y)x}{\Psi(x, y)}$ .

The Theorem: On 12th August 2016, Paul Balister, Béla Bollobás, and Robert Morris submitted to arxiv a paper in which they proved that for any $\epsilon>0$ , we have $\lim\limits_{x\to\infty} P\left((e^{-\gamma}-\epsilon)J(x) \leq T \leq (e^{-\gamma}+\epsilon)J(x)\right) = 1$ , where $\gamma$ is the Euler-Mascheroni constant.

Short context: How many random integers between 1 and x we should select such that the product of some selected integers is a perfect square? This question is important for understanding the performance of fastest known factorisation algorithms. In 1994, Pomerance conjectured that the number T of integers needed for this exhibits a sharp threshold, that is, $\lim\limits_{x\to\infty} P\left((1-\epsilon)f(x) \leq T \leq (1+\epsilon)f(x)\right) = 1$ for some function $f(x)$ and any $\epsilon>0$ . See here for the best partial result towards this conjecture before 2016. The Theorem confirms the conjecture in full.