Lower bounding the probability that $\gcd(t,N)≤B$, for a random $t$ and fixed (large) $N$

Question

$\newcommand{\Prb}[1]{\mathcal{P}_{#1}}$ I have the following number theory problem, related to Odlyzko's improvement on Shor’s factoring algorithm (see this cstheory.sx question for details).

Let $N$ be a (large) integer and $1≤B≤N$ a bound. If I chose the integer $1≤t≤N$ uniformly at random, can I lower bound the probability $\Prb B$ that $\gcd(t,N)≤B$ ? How should I chose the least possible $B$ such that $\Prb B$ is bounded away from 0 ? Or asymptotically close to 1 ?

Of course $$\begin{align}\Prb 1&=\frac{ϕ(N)}N>\frac{1}{e^γ\ln\ln N+\frac3{\ln\ln N}};& \Prb N&=1 \end{align}$$ where $ϕ$ is Euler’s totient function and $γ$ is the Euler-Mascheroni constant. More generally, it is easy to see that $$ \Prb B=\frac{\sum_{d\vert N}^{d≤B}ϕ(\frac{N}{d})}N =1-\frac{\sum_{d'\vert N}^{d'<\frac{N}{B}}ϕ(d')}N, $$ but I did not manage to go further.

If I interpret the 1995 “private communication” from Odlyzko to Shor (referred to in arXiv:quant-ph/9508027 and the cstheory.sx question) correctly, $∀ε>0$, $\Prb{(\log N)^{1+ε}}$ is bounded away from 0. However, I did not manage to find a proof of this.

Answer 1

In fact one can prove a stronger result -- namely the probability is bounded away from zero, so long as $B \ge (\log N)^\delta$ for some $\delta >0$. This is best possible, by taking $N$ to be the product of the first few primes. Since $\phi(N/d) \ge \phi(N)/d$, our probability is bounded below by $$ \frac{\phi(N)}{N} \sum_{d|N, d\le B} \frac{1}{d}\ge \frac{\phi(N)}{N}\sum_{d|N, d\le B} \frac{\mu(d)^2}{d}, $$ where in the last sum we have restricted attention to square-free $d$ for simplicity.

Now I claim that for large enough $B$ (and any $N$, independent of $B$) one has $$ \sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \frac{1}{4} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big). \tag{1} $$ Assuming the claim, we get a lower bound for our probability of $$ \ge \frac 14 \frac{\phi(N)}{N} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \ge \frac{1}{4} \prod_{p} \Big(1-\frac 1{p^2}\Big) \prod_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big)= \frac{3}{2\pi^2} \prod_{p|N, p>\sqrt{B}} \Big(1-\frac{1}{p}\Big). $$ If now $B\ge (\log N)^{\delta}$ then $$ \prod_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big) \ge \prod_{(\log N)^{\delta/2}<p <(\log N)^2}\Big(1-\frac 1p\Big) \prod_{p>(\log N)^2, p|N} \Big(1-\frac 1p\Big), $$ and by Mertens's theorem the first factor above is $\gg \delta$, and trivially the second factor is $1+o(1)$. This completes the proof.

It remains to settle the claim (1). With $\alpha =1/\log B$ note that $$ \sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \sum_{\substack{d|N, d\le B \\ p|d \implies p\le \sqrt{B}}} \frac{\mu(d)^2}{d} \ge \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) - B^{-\alpha} \sum_{\substack{d|N\\ p|d\implies p\le \sqrt{B} }} \frac{\mu(d)^2 d^{\alpha}}{d}. $$ The second term above is $$ e^{-1} \prod_{p|N, p\le \sqrt{B}} \Big(1 + \frac{p^{\alpha}}{p}\Big) \le e^{-1} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \exp\Big(\sum_{p|N, p\le \sqrt{B}} \frac{p^{\alpha}-1}{p}\Big). $$ Now for large enough $B$, (since $(e^{t}-1)/t \le (\sqrt{e}-1)/(1/2)$ for $0\le t\le 1/2$) $$ \sum_{p\le \sqrt{B}} \frac{p^{1/\log B}-1}{p} \le\sum_{p\le \sqrt{B}} \frac{\log p}{p\log B} \Big(\frac{\sqrt{e}-1}{1/2}\Big) = \sqrt{e}-1 +o(1), $$ and using this above, we obtain $$ \sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \Big(1- e^{-1} (e^{\sqrt{e}-1}+o(1)) \Big) \ge \frac 14 \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big), $$ proving the claim (1).

Answer 2

One can establish the claim using a logarithmic version of the moment method.

If one factors $N = \prod_{p|N} p^{\operatorname{ord}_p(N)}$, then $\log \operatorname{gcd}(t,N) = \sum_{p|N} \log \operatorname{gcd}( t, p^{\operatorname{ord}_p(N)} )$. Taking expectations, we see from linearity of expectation that

$$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \sum_{p|N} \sum_{1 \leq j \leq \operatorname{ord}_p(N)} \frac{j \log p}{p^j}$$ since the event $\operatorname{gcd}(t,p^{\operatorname{ord}_p(N)}) = p^j$ occurs with probability at most $1/p^j$. The contributions of $j \geq 2$ can be bounded by $O( \sum_p \frac{\log p}{p^2} ) = O(1)$ after summing first in $j$, hence $$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \sum_{p|N} \frac{\log p}{p} + O(1).$$ By Mertens' theorem, the contribution of those primes up to $\log N$ is at most $\log\log N + O(1)$. As for the primes greater than $\log N$ that divide $N$, there are at most $\frac{\log N}{\log\log N}$ of these, and each term is at most $\frac{\log N}{\log\log N}$, so the total contribution is $O(1)$. Thus $$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \log\log N + O(1).$$ By Markov's inequality, this implies that $\log \operatorname{gcd}(t,N) \leq (1+\varepsilon)\log\log N$ with probability bounded away from zero for $N$ sufficiently large depending on $\varepsilon$, which gives the claim.

Answer 3

A justification of Odlyzko's comment has already been provided. Let me supplement this by saying that if you want the probability to tend to 1, you should take $B = (\log{N})^{A}$, where $A \to\infty$ with $N$.

That this is sufficient follows from Terry's answer above. To see it is necessary, let me show that if A is any fixed constant, then $\mathcal{P}_{(\log{N})^A}$ does not tend to $0$ as $N\to\infty$. Let $N$ be the product of the primes up to $z$, where $z$ is a parameter tending to $\infty$. (So $\log{N} \sim z$, by the prime number theorem.) Consider numbers $t \le N$ constructed as a product $de$, where $d$ is squarefree, $z$-smooth, $d \in ((\log{N})^{A},(\log{N})^{2A}]$, and $e$ has no prime factors up to $z$. Then $\gcd(t,N) = d > (\log{N})^{A}$; we will show below there are $\gg N$ such values of $t \in [1,N]$.

Given $d$, the number of possibilities for $e$ is $\gg \frac{N}{d \log{z}} \gg \frac{N}{d \log\log{N}}$, by (e.g.) Brun's sieve. Now we sum on $d$. For $T \le (\log{N})^{2A}$, the number of squarefree $z$-smooth integers $d \in [1,T]$ is $\gg T$. (The distribution of squarefree smooth numbers is understood in quite a wide range; e.g., see work of Naimi.) Now partial summation gives that the sum of $1/d$ is $\gg \log\log{N}$.