If \(q\mid (n_1,n_2)\) then \(q\) divides \(\left\lvert n_1-n_2\right\rvert \), and hence in particular \(q\leq N\). The contribution of all prime powers \(p^r\) with \(r\geq 2\) is \(O(1)\), and hence it suffices to show that \(\sum _{p\mid \left\lvert n_1-n_2\right\rvert }\frac{1}{p}\ll \log \log \log N\). Any integer \(\leq N\) is trivially divisible by \(O(\log N)\) many primes. Clearly summing \(1/p\) over \(O(\log N)\) many primes is maximised summing over the smallest \(O(\log N)\) primes. Since there are \(\gg (\log N)^{3/2}\) many primes \(\leq (\log N)^2\), we have

by Mertens’ estimate 2.6.

Since, by definition, every integer \(n\in A\) can be written uniquely as \(q_1\cdots q_t\) for \(q_i\in \mathcal{Q}_A\) for some \(t\in I = [(1-\epsilon )\log \log N, 2\log \log N]\), we have that, since \(t!\geq (t/e)^t\),

Since \((ex/t)^t\) is decreasing in \(t\) for \(x{\lt}t\), either \(\sum _{q\in \mathcal{Q}_A}\frac{1}{q}\geq (1-\epsilon )\log \log N\) (and we are done), or the summand is decreasing in \(t\), and hence we have

The claimed bound follows, using the fact that \(e^{-\frac{\epsilon }{2(1-\epsilon )}}\geq 1-\epsilon \) for \(\epsilon \in (0,1/2)\), choosing \(N\) large enough such that \((2\log \log N)^{2/\log \log N}\leq 1+\epsilon ^2\), say.

To verify the inequality \(e^{-\frac{\epsilon }{2(1-\epsilon )}}\geq 1-\epsilon \) for \(\epsilon \in (0,1/2)\), note that \(\frac{\epsilon }{2(1-\epsilon )}\leq \epsilon \) for all \(\epsilon \in (0,1/2)\), and hence using \(1+x\leq e^{x}\) for all \(x\geq -1\), we have

as required.

We can write every \(d\in D\) uniquely as a product of prime powers \(d=p_1^{r_1}\cdots p_k^{r_k}\), where for each \(i\) either \(r_i=1\) and \(y{\lt}p_i\leq N\), or \(r_i\geq 2\) and \(p_i\leq N\). Therefore the left-hand side is at most

The second product is, using \(1+kx\leq (1+x)^k\),

for some constant \(C_1{\gt}0\), since the product converges. Similarly,

and the product here is \(\ll (\log N/\log y)\) by Mertens’ bound 2.6. Combining these yields the required estimate.

Fix some \(q\) with \(R(A;q)\geq (\log N)^{-1/2}\). Let \(y=\exp ((\log N)^{1-2/k})\). Let \(D\) be the set of all \(d\) such that if \(r\) is a prime power such that \(r\mid d\) and \((r,d/r)=1\) then \(y{\lt}r\leq N\), and furthermore

We first claim that every \(n\in A_q\) is divisible by some \(qd\) with \(d\in D\), such that \((qd,n/qd)=1\). Let \(Q_n\) be the set of prime powers \(r\) dividing \(n\) such that \((r,n/r)=1\), so that \(n=\prod _{r\in Q_n}r\). Let

We let \(d=\prod _{r\in Q_n'}r\). We need to check that \(d\in D\) and \(qd\mid n\). It is immediate from the definitions that if a prime power \(r\) divides \(d\) with \((r,d/r)=1\) then \(r\in Q_n'\), whence \(r{\gt}y\). It is also straightforward to check, by comparing prime powers, that \(qd\mid n\), and hence \(qd\leq n\leq N\). Furthermore,

by definition of \(y\) and the hypothesis that \(\omega (n)\leq (\log N)^{1/k}\). It follows that \(d\in D\) as required.

If we let \(A_q(d)=\{ n \in A_q : qd\mid n\textrm{ and }(qd,n/qd)=1\} \) then we have shown that \(A_q\subseteq \bigcup _{d\in D}A_q(d)\). Therefore

We will control the contribution from those \(d\) with \(\omega (d){\gt}\omega _0= \frac{5}{\log k}\log \log N\) with the trivial bound

using the harmonic sum bound \(\sum _{m\leq N}\frac{1}{m}\leq \log N+1\leq 2\log N\). Therefore

By 5.3 we have

and therefore

Recalling \(\omega _0=\frac{5}{\log k}\log \log N\) and \(y=\exp ((\log N)^{1-2/k})\) the right-hand side here is at most

for sufficiently large \(N\), assuming \(k\leq c\log \log N\) for sufficiently small \(c\).

It follows that

The result follows by averaging, since by 5.3

We will prove the following claim, valid for any finite set \(A\subset \mathbb {N}\) with \(0\not\in A\) and \(\epsilon {\gt}0\), via induction: for all \(i\geq 0\) there exists \(A_i\subseteq A\) and \(Q_i\subseteq \mathcal{Q}_A\) such that

1. the sets \(\mathcal{Q}_{A_i}\) and \(Q_i\) are disjoint,

2. \(R(A_i)\geq R(A)- \epsilon \sum _{q\in Q_i}\frac{1}{q}\),

3. either \(i\leq \left\lvert A\backslash A_i\right\rvert \) or, for all \(q'\in \mathcal{Q}_{A_i}\), \(\epsilon {\lt} R(A_i;q')\).

Given this claim, the stated lemma follows by choosing \(B=A_{\left\lvert A\right\rvert +1}\), noting that in the 5th point above the first alternative cannot hold, and furthermore

by Lemma 2.6, assuming \(N\) is sufficiently large.

To prove the inductive claim, we begin by choosing \(Q_0=\emptyset \), and \(A_0=A\). All of the properties are trivial to verify.

Suppose the proposition is true for \(i\geq 0\), with associated \(A_i,Q_i\). We will now prove it for \(i+1\). If it is true that, for all \(q'\in \mathcal{Q}_{A_i}\), we have \(\epsilon {\lt}R(A_i;q')\), then we let \(A_{i+1}=A_i\) and \(Q_{i+1}=Q_i\).

Otherwise, let \(q'\in \mathcal{Q}_{A_i}\) be such that \(R(A_i;q')\leq \epsilon \), set \(A_{i+1} = A_i\backslash \{ n\in A_i : q'\mid n \textrm{ and }(q',n/q')=1\} \), and \(Q_{i+1}=Q_i\cup \{ q'\} \).

It remains to verify the required properties. That \(Q_{i+1}\subseteq \mathcal{Q}_A\) follows from \(Q_i\subseteq \mathcal{Q}_A\) and \(q'\in \mathcal{Q}_{A_i}\subseteq \mathcal{Q}_A\) (using the general fact that if \(B\subseteq A\) then \(\mathcal{Q}_B\subseteq \mathcal{Q}_A\)).

For point (1), since \(A_{i+1}\subseteq A_i\), and hence \(\mathcal{Q}_{A_{i+1}}\subseteq \mathcal{Q}_{A_i}\), it suffices to show that \(q'\not\in \mathcal{Q}_{A_{i+1}}\). If this were not true, there would be some \(n\in A_{i+1}\) such that \(q'\mid n\) and \((q',n/q')=1\), contradiction to the definition of \(A_{i+1}\).

For point (2), we note that

and point (2) follows from induction and the observation that

since \(q'\in \mathcal{Q}_{A_i}\) and hence \(q'\not\in Q_{i}\).

Finally, for point (3), we note that since we assume that it is not true that for all \(q'\in \mathcal{Q}_{A_i}\), we have \(\epsilon {\lt}R(A_i;q')\), it must be true that \(i\leq \left\lvert A\backslash A_{i}\right\rvert \). We now claim that \(i+1\leq \left\lvert A\backslash A_{i+1}\right\rvert \), for which it suffices to show that \(A_{i+1}\subsetneq A_i\). This is true since \(q'\in \mathcal{Q}_{A_i}\), and hence the set \(\{ n\in A_i : q'\mid n \textrm{ and }(q',n/q')=1\} \) is not empty.

We will prove the following, for all \(N\) sufficiently large, real \(0{\lt}M{\lt}N\), reals \(\epsilon {\gt}0\) and \(\alpha {\gt} 4\epsilon \log \log N\) and finite sets \(A\subseteq [M,N]\) such that \(R(A)\geq \alpha \) and \(R(A;q){\gt} \epsilon \) for all \(q\in \mathcal{Q}_A\), by induction: for all \(i\geq 0\) there exists \(A_i\subseteq A\) such that

1. \(R(A_i)\geq \alpha -1/M\),

2. \(R(A_i;q) {\gt} \epsilon \) for all \(q\in \mathcal{Q}_{A_i}\), and

3. either \(i\leq \left\lvert A\backslash A_i\right\rvert \) or \(R(A_i){\lt}\alpha \).

Given this claim, we prove the lemma as follows. Let \(A'\subseteq A\) be as given by Lemma 5.5, so that the hypotheses of the inductive claim are satisfied for \(A'\). We now apply the inductive claim, and choose \(B=A_{\left\lvert A\right\rvert +1}\), noting that the first alternative of point (3) cannot hold.

It remains to prove the inductive claim. The base case \(i=0\) is immediate by hypotheses, choosing \(A_0=A\).

We now fix some \(i\geq 0\), with associated \(A_i\) as above, and prove the claim for \(i+1\). If \(R(A_i){\lt}\alpha \) then we set \(A_{i+1}=A_i\). Otherwise, we have \(R(A_i)\geq \alpha \). By Lemma 5.5 there exists \(B\subset A_i\) such that

and \(2\epsilon {\lt} R(B;q)\) for all \(q\in \mathcal{Q}_B\). In particular, since \(R(B){\gt}0\), the set \(B\) is not empty. Let \(x\in B\) be arbitrary, and set \(A_{i+1}=A_i\backslash \{ x\} \).

We note that since \(x\in B\subseteq A\), we have \(x\geq M\), and hence \(R(A_{i+1})=R(A_i)-1/x\geq \alpha -1/M\), so point (1) is satisfied. Furthermore, since \(R(A_i)\geq \alpha \), we have \(i\leq \left\lvert A\backslash A_i\right\rvert \), and hence \(i+1 \leq \left\lvert A\backslash A_{i+1}\right\rvert \) and point (3) is satisfied.

For point (2), let \(q\in \mathcal{Q}_{A_{i+1}}\subseteq \mathcal{Q}_{A_i}\). If it is not true that \(q\mid x\) and \((q,x/q)=1\) then

Otherwise, if \(q\mid x\) and \((q,x/q)=1\), then \(q\in \mathcal{Q}_B\). It follows that, since \(B\subseteq A_i\), we have

since \(q\leq \epsilon M\). The inductive claim now follows.