$\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.

  • 7
    $\begingroup$ After seeing the proofs here, I'm not at all embarrassed that I didn't remember Odlyzko's proof (if the proof had been easy, I probably still wouldn't remember it, but I'd be embarrassed about it). $\endgroup$
    – Peter Shor
    Aug 1 '15 at 23:48
  • 1
    $\begingroup$ Thanks for the three answers ! I wish I could vote for all three. I opted for @Lucia’s, because it is the one with the strongest positive result. I’m still working to understand the proofs, but I think I’ve learnt enough number theory over the last few days to understand the broad lines of each proof. Thank again ! $\endgroup$ Aug 2 '15 at 17:49

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).

  • 4
    $\begingroup$ Up to a constant, the estimate (1) can also be deduced from Lemma 2.1 of this paper of Granville, Koukoulopoulos, and Matomaki: arxiv.org/abs/1205.0413 , which has a nice elementary proof. (EDIT: actually one needs a minor modification of the lemma to handle the restriction to squarefrees.) $\endgroup$
    – Terry Tao
    Jul 31 '15 at 22:27
  • 1
    $\begingroup$ @Lucia : I plan to cite this in an academic paper. Would you prefer to be cited by another name than “Lucia” ? $\endgroup$ May 20 '16 at 12:29

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.


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}$.

  • $\begingroup$ I plan to cite this in an academic paper. Would you prefer to be credited by another name than “so-called friend Don” ? $\endgroup$ May 20 '16 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.