The threshold for making squares is sharp up to a factor of 4/pi

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 3rd November 2008, Ernie Croot, Andrew Granville, Robin Pemantle, and Prasad Tetali submitted to arxiv a paper in which they proved that for any $\epsilon>0$ , $\lim\limits_{x\to\infty} P\left(\frac{\pi}{4}(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$ . The authors of the Theorem further conjectured that this holds with $f(x)=e^{-\gamma}J(x)$ . The Theorem proves the upper bound exactly, and the lower bound up to the constant $\frac{\pi}{4}$ .