$\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.
Best Answer
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).