Let \(I\) be any interval of length \(\leq MN^{-2/(\log \log N)}\), and let \(q\in \mathcal{Q}_A\) such that \(R(A_I;q){\gt} 1/2(\log N)^{1/100}\).

Apply Lemma 5.4 with \(A\) replaced by \(A_I\), and \(k=\frac{\log \log N}{\log 2+\log \log \log N}\), so that \((\log N)^{1/k}=2\log \log N\). We choose \(N\) large enough such that \(k\leq c\log \log N\) (where \(c\) is the constant in the statement of Lemma 5.4) and such that \(\log k\geq 5000\).

This produces some \(d_q\) such that \(qd_q{\gt}\left\lvert I\right\rvert \) and \(\omega (d_q){\lt}\tfrac {1}{1000}\log \log N\), and

assuming \(N\) is sufficiently large. Let

so that, the above inequality states that \(R(A_I^{(q)})\geq (\log N)^{-1/99}\).

We now claim that \(2\log \log N\geq \omega (m) \geq \tfrac {97}{99}\log \log N\) for all \(m\in A_I^{(q)}\). This follows from the trivial \(\omega (mqd_q)\geq \omega (m)\geq \omega (mqd_q)-\omega (qd_q)\), and that \(2\log \log N\geq \omega (mqd_q)\geq \frac{99}{100}\log \log N\) (since \(mqd_q\in A\)) and \(\omega (qd_q)\leq 1+\omega (d_q){\lt}\frac{1}{500}\log \log N\).

We now apply Lemma 5.2 with \(\epsilon =2/99\). This implies that

By definition of \(A_I\), every \(n\in A_I\) with \(qd_q\mid n\) must divide some \(x\in I\), say \(x(n)\). We claim that \(x(n)=x(m)\) for all \(n,m\in A_I\) with \(qd_q\mid n\) and \(qd_q\mid m\). Otherwise \(\left\lvert x(q,n)-x(q,m)\right\rvert \) is a non-zero multiple of \(qd_q\), so \(\left\lvert I\right\rvert {\lt}qd_q\leq \left\lvert x(q,n)-x(q,m)\right\rvert \), which is an integer in \([1,\left\lvert I\right\rvert )\), a contradiction.

Let \(x_q\in I\) be such that \(x(q,n)=x_q\) for all \(n\in A_I\) with \(qd_q \mid n\). We claim that \(\mathcal{Q}_{A_I^{(q)}}\subset \{ r\in \mathcal{Q}_A : r\mid x_q\} \), which concludes the proof using the above bound.

If \(r\in \mathcal{Q}_{A_I^{(q)}}\) then there exists some \(m\in A_I^{(q)}\) such that \(r\mid m\) and \((r,m/r)=1\). Let \(m=n/qd_q\) where \(n\in A\) with \(qd_q\mid n\) and \((qd_q,n/qd_q)=(qd_q,m)=1\). Certainly \(r\mid n = mqd_q\), since \(r\mid m\). Furthermore, \(r\) is coprime to \(qd_q\) since \(r\) divides \(m\). Therefore \((r,n/r)=(r,(m/r)qd_q)=(r,m/r)=1\), and hence \(r\in \mathcal{Q}_A\).

Finally, we need to show that \(r\mid x_q\). Let \(m\in A_I^{(q)}\) be such that \(r\mid m\). Let \(n\in A_I\) be such that \(qd_q\mid n\) and \(m=n/qd_q\). Then \(r\mid n=mqd_q\), and hence since \(n\mid x_q\) we have \(r\mid x_q\) as required.

For every \(q\in \mathcal{D}_I(A;\delta M)\), by definition,

Therefore

Let \(I\) be any interval of length \(\leq MN^{-2/(\log \log N)}\), and let \(A_I\) be those \(n\in A\) that divide some element of \(I\), and \(\mathcal{D}=\mathcal{D}_I(A;M/2(\log N)^{1/100})\). We may assume that \(\left\lvert A\backslash A_I\right\rvert {\lt} M/\log N\).

Let \(\mathcal{E}\) be the set of those \(q\in \mathcal{Q}_A\) such that \(R(A_I;q){\gt} 1/2(\log N)^{1/100}\), so that by Lemma 6.2 we have \(\mathcal{D}\subset \mathcal{E}\). By Lemma 6.1 for each \(q\in \mathcal{E}\) there exists \(x_q\in I\) such that \(q\mid x_q\) and

Let \(X=\{ x_q : q\in \mathcal{E}\} \). Suppose that \(\left\lvert X\right\rvert \geq 3\), and say \(x,y,z\in X\) are three distinct elements. Then

where the last three sums are restricted to prime powers.

Since \(\sum _{q\in \mathcal{Q}_A}\frac{1}{q}\leq (1+o(1))\log \log N\leq 1.01\log \log N\), say, by Lemma 2.6, it follows that

But since \(x,y\in I\) we have, by Lemma 5.1,

and similarly for the other sums, and so the left-hand side is \(O(\log \log \log N)\), which is a contradiction for large enough \(N\).

Therefore \(\left\lvert X\right\rvert \leq 2\). If \(\mathcal{D}\) is empty the second conclusion trivially holds, and therefore we may assume there is some \(q\in \mathcal{E}\) and hence some \(x_q\in X\), so \(\left\lvert X\right\rvert \geq 1\). If \(\left\lvert X\right\rvert =1\) then we are in the second conclusion, letting \(x\) be the unique element of \(X\), since by construction \(x=x_q\) for all \(q\in \mathcal{D}\), and hence in particular \(q\mid x\) for all \(q\in \mathcal{D}_I\) as required.

Finally, we deal with the case \(\left\lvert X\right\rvert =2\). Say \(X=\{ w_1,w_2\} \) with \(w_1\neq w_2\) (and both are elements of \(I\)). Let \(A^{(i)}=\{ n\in A: n\mid w_i\} \) and \(A^{(0)}=A\backslash (A^{(1)}\cup A^{(2)})\). Without loss of generality, label the \(w_i\) such that \(R(A^{(1)})\geq R(A^{(2)})\). Suppose first that \(R(A^{(0)}){\lt}R(A)/3\). In this case, since \(R(A^{(0)})+R(A^{(1)})+R(A^{(2)})\geq R(A)\), we have \(R(A^{(1)})\geq R(A)/3\). Furthermore, note that

As above, by Lemma 2.6, the assumed lower bound on the sum over \(q\mid w_2\), and Lemma 5.1, for sufficiently large \(N\) the right-hand side is

Every \(q\mid \mathcal{Q}_{A^{(1)}}\) is in \(\mathcal{Q}_A\) and divides \(w_1\), and hence

and we are in case (1) with \(B=A^{(1)}\).

Finally, suppose that \(R(A^{(0)})\geq R(A)/3\). We will derive a contradiction, assuming \(N\) is large enough. Let \(A'\subset A^{(0)}\) be the set of those \(n\in A_I\cap A^{(0)}\) such that if \(n\in A_q\) then \(q\in \mathcal{E}\). By definition of \(\mathcal{E}\) and Mertens’ estimate 2.6, and the earlier assumption that \(\left\lvert A\backslash A_I\right\rvert {\lt}M/\log N\),

and so in particular, since \(R(A)\geq (\log N)^{-1/101}\), we have \(R(A')\gg (\log N)^{-1/101}\).

In particular, \(\left\lvert A'\right\rvert \gg M/(\log N)^{-1/101}\). Every \(n\in A'\) divides some \(x\in I\), and there are at most \(MN^{-2/\log \log N}\) many \(x\in I\), so by the pigeonhole principle there must exist some \(x\in I\) (necessarily \(x\neq w_1\) and \(x\neq w_2\) since \(A'\subset A^{(0)}\)) such that, if \(A''=\{ n\in A' : n\mid x\} \), then

and hence \(\left\lvert A''\right\rvert \geq N^{3/2\log \log N}\), say, assuming \(N\) is sufficiently large.

However, if \(n\in A''\) then both \(n\mid x\) and \(n\mid w_1w_2\) (since every \(q\) with \(n\in A_q\) is in \(\mathcal{E}\) and so divides either \(w_1\) or \(w_2\)), and hence \(n\) divides

Therefore the size of \(A''\) is at most the number of divisors of some fixed integer \(m\leq N^2\), which is at most \(N^{(1+o(1))2\log 2/\log \log N}\) by Lemma 2.5, and hence we have a contradiction for large enough \(N\), since \(2\log 2{\lt} 3/2\).

Let \(I\) be any interval of length \(\leq MN^{-2/(\log \log N)}\), and let \(A_I\) be those \(n\in A\) that divide some element of \(I\), and \(\mathcal{D}=\mathcal{D}_I(A;M/2q(\log N)^{1/00})\). We may assume that \(\left\lvert A\backslash A_I\right\rvert {\lt} M/\log N\).

By Lemmas 6.1 and 6.2 for each \(q\in \mathcal{D}\) there exists \(x_q\in I\) such that \(q\mid x_q\) and

Let \(X=\{ x_q : q\in \mathcal{D}\} \). Suppose that \(\left\lvert X\right\rvert \geq 2\), and say \(x,y\in X\) are two distinct elements. Then

where the third sum is restricted to prime powers. Using our assumed bounds, this implies

say.

But since \(x,y\in I\) we have, by Lemma 5.1,

which is a contradiction for large enough \(N\).

Therefore \(\left\lvert X\right\rvert \leq 1\). If \(\mathcal{D}\) is empty then the second conclusion trivially holds, for any \(x\in I\). Therefore there exists some \(q\in \mathcal{D}\), therefore there exists some \(x_q\in X\), and hence \(\left\lvert X\right\rvert =1\). Let \(x\in I\) be the unique element of \(X\). By construction \(x=x_q\) for all \(q\in \mathcal{D}\), and hence in particular \(q\mid x\) for all \(q\in \mathcal{D}_I\) as required.

In the proof below, we write \(t_i=\min (\lceil y\rceil +i, \lfloor w\rfloor )\) for all integer \(i\geq 0\) for simplicity. It is convenient to note at the outset that \(t_0=\lceil y\rceil \), \(t_i\leq w\) for all \(i\), for all \(i\geq 0\) we have \(t_{i+1}\in [t_i,t_i+1]\), and if \(t_i{\lt} \lfloor w\rfloor \) then \(t_{i+1}=t_i+1\). Furthermore, if \(i\geq \lfloor w\rfloor -\lceil y\rceil \), then \(t_i=\lfloor w\rfloor \).

We will prove by induction on \(i\) that, under the same hypotheses as in the lemma, for all \(0\leq i\) there exists \( A_i\subseteq A\) and integer \(d_i\) with \(y\leq d_i\leq t_i\) such that

1. \(R(A_i) \in [2/d_i-1/M, 2/d_i)\),

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

3. there are no multiples of any \(m\in [y,d_i)\) in \(A\), and

4. either there exists a multiple of \(d_i\) in \(A_i\), or nothing in \(A_i\) is divisible by any \(d\in [y,t_i]\).

Given this inductive claim, the lemma follows by letting \(A' = A_{\lfloor w\rfloor -\lceil y\rceil }\) and \(d=d_{\lfloor w\rfloor -\lceil y\rceil }\), so that then \(t_{\lfloor w\rfloor -\lceil y\rceil }=\lfloor w\rfloor \), noting that the assumptions imply that \(2/d-1/M\geq 2/w-1/M{\gt}0\) and hence \(R(A'){\gt}0\) and so \(A'\neq \emptyset \), and furthermore by assumption the second alternative of point (3) cannot hold. It remains to prove the inductive claim.

For the base case \(i=0\), we set \(d_0=\lceil y\rceil \) and apply Lemma 5.6 with \(\alpha =2/d_0\) to find some \(A_0\subseteq A\) such that \(R(A_0)\in [2/d_0-1/M,2/d_0)\) and for all \(q\in \mathcal{Q}_{A_0}\) we have \(\epsilon {\lt} R(A_0;q)\). (To see that point (4) holds, note that \(d_0\) is the unique integer in \([y,t_0]\).)

For the inductive step, suppose that \(A_i,d_i\) are as given for \(i\geq 0\). If there exists a multiple of \(d_i\) in \(A_i\), then we set \(d_{i+1}=d_i\) and \(A_{i+1}=A_i\).

If not, then nothing in \(A_i\) is divisible by any \(d\in [y,t_i]\). We now set \(d_{i+1}=t_{i+1}\) and apply Lemma 5.6 to \(A_i\) with \(\alpha =2/d_{i+1}\). To be able to apply this, we need to verify that

and

For the first, we note that \(d_{i+1}\leq w\), and hence we are done since \(2/w{\gt}4/w^2\geq 6\epsilon \log \log N\).

For the second, we note that by assumption, every \(n\in A\) is divisible by some \(d\in [y,w]\), and hence since we are assuming that nothing in \(A_i\) is divisible by any \(d\in [y,t_i]\), we must have \(t_i{\lt}\lfloor w\rfloor \), and hence \(d_{i+1}=t_{i+1}=t_i+1\geq d_i+1\). Therefore

since \(1/M \leq \epsilon \log \log N\), and furthermore

and hence \(R(A_i)\geq \alpha +2\epsilon \log \log N\) as required.

Thus we can apply Lemma 5.6, to produce some \(A_{i+1}\subseteq A_i\) such that \(R(A_{i+1})\in [2/d_{i+1}-1/M,2/d_{i+1})\), such that for all \(q\in \mathcal{Q}_{A_{i+1}}\) we have \(R(A_{i+1};q){\gt}\epsilon \). Furthermore, if there is something in \(A_{i+1}\) divisible by some \(d\in [y,t_{i+1}]\), then since \(A_{i+1}\subseteq A_i\) there must be something in \(A_{i+1}\) divisible by some \(d\in [y,t_{i+1}]\backslash [y,t_i]\). Since \(t_{i+1}\in [t_i,t_i+1]\), the only integer that could be in \([y,t_{i+1}]\backslash [y,t_i]\) is \(t_{i+1}=d_{i+1}\), and the proof is complete.

Let \(M=N^{1-1/\log \log N}\). Apply Lemma 6.5 with \(w=z/4\) and \(\epsilon =N^{-5/\log \log N}\) to find some corresponding \(A'\) and \(d\).

Suppose first that case (2) of Proposition 6.3 holds for \(A'\). The hypotheses of Proposition 4.22 are now met with \(k=d\), \(\eta =1/2(\log N)^{1/100}\), and \(K=MN^{-2/\log \log N}\). This yields some \(S\subset A'\subset A\) such that \(R(S)=1/d_j\) as required.

Otherwise, Proposition 6.3 yields some \(B\subset A'\) such that

and where \(\sum _{q\in \mathcal{Q}_B}\frac{1}{q}\leq \frac{2}{3}\log \log N\).

We apply Lemma 6.5 again, with \(y=4d\) and \(w=z\), to produce some corresponding \(B'\subset B\) and \(d'\in [4d,z]\). Since \(\sum _{q\in \mathcal{Q}_{B'}}\frac{1}{q}\leq \sum _{q\in \mathcal{Q}_B}\frac{1}{q}\leq \frac{2}{3}\log \log N\) we can apply Proposition 6.4. The hypotheses of Proposition 4.22 are now met with \(k=d'\) and \(\eta ,K\) as above, and thus there is some \(S\subset B'\subset A\) such that \(R(S)=1/d'\) as required.