Proof. For \(0 \leq m < M\), we write \[\label{defineNm} N_{m} = a + m A,\tag{7}\] so that ?? and 7 together with the upper bound on \(m\) give us that \(N_{m} \leq Y\). For each divisor \(u \mid N\), pair \(u\) with \(\frac{N}{u}\). Since \(N \leq Y\), we have \(\sqrt{N} \leq \sqrt{Y}\). For each pairing of an expression \(u\) with \(\frac{N}{u}\), at least one expression among \(u\) and \(\frac{N}{u}\) is \(\leq \sqrt{N} \leq \sqrt{Y}\). So, every divisor of \(N\) is accounted for by at most doubling the divisors \(h \mid N\) satisfying \(h \leq \sqrt{Y}\), i.e., so that \[\label{pairingdivisor} d(N) \leq 2 \sum_{\substack{h \leq \sqrt{Y} \\ h \mid N}} 1\tag{8}\] for \(N \leq Y\). From 8 , we write \[\label{reducedouble} \sum_{m=0}^{M-1} d(a + m A) \leq 2 \sum_{m=0}^{M-1} \sum_{\substack{ h \leq \sqrt{Y} \\ h \mid (a + m A) }} 1,\tag{9}\] and we rewrite the upper bound in 9 so that \[\label{rewritehash} \sum_{m=0}^{M-1} d(a + mA) \leq 2 \sum_{h \leq \sqrt{Y}} \#\{ m \in [0, M) : h \mid (a + m A) \}.\tag{10}\] Now, let \(h \leq \sqrt{Y}\) be fixed, and consider values \(m \in [0, M)\) such that the congruence \[\label{amAequiv0} a + m A \equiv 0 \pmod h\tag{11}\] holds. We proceed to consider two cases, as below.

First, suppose that \((h, A) > 1\), writing \(g = (h, A) > 1\). So, if \(h \mid (a + mA)\) (noting that this is equivalent to 11 ), then \[\label{gmidamA} g \mid (a + m A).\tag{12}\] However, since \(g \mid A\), we have that \(g \mid mA\). This consequence together with 12 allow us to deduce that \(g \mid a\), but \(g > 1\) and we thus have a common divisor of \(a\) and \(A\) strictly greater than \(1\), contradicting ?? . So, we have shown that: If \((h, A) > 1\), then no value \(m \in [0, M)\) satisfies the congruence in 11 .

Now, suppose that \((h, A) = 1\). If \(h = 1\), then every integer \(m \in [0, M)\) satisfies the congruence in 11 , so that the number of solutions \(m \in [0, M)\) to 11 is \(M \leq \frac{M}{h} + 1\). If \(h > 1\), then \(A\) is invertible (multiplicatively) modulo \(h\), so that the relation in 11 is equivalent to \[\label{minresidue} m \equiv -aA^{-1} \pmod h.\tag{13}\] In general, we have that the number of integers in \([0, M)\) and in a fixed residue class modulo \(h\) is bounded above by \(\big\lceil \frac{M}{h} \big\rceil \leq \frac{M}{h} + 1\). So, since \(m\) is necessarily in the residue class in 13 , we find that \[\#\{ m\in [0, M) : h \mid (a + m A) \} \leq \begin{cases} 0, & \text{if (h, A) > 1}, \\ \frac{M}{h} + 1, & \text{if (h, A) = 1,} \end{cases}\] so that 10 then gives us that \[\begin{align} \sum_{m=0}^{M-1} d(a + m A) & \leq 2 \sum_{\substack{ h \leq \sqrt{Y} \\ (h, A) = 1 }} \left( \frac{M}{h} + 1 \right) \\ & \leq 2 \sum_{\substack{ h \leq \sqrt{Y} }} \left( \frac{M}{h} + 1 \right). \end{align}\] The desired result then follows by estimating this latter sum in a standard way. More explicitly, we write \[\label{applyharmonic} 2 \sum_{h \leq \sqrt{Y}} \left( \frac{M}{h} + 1 \right) = 2 M \sum_{h \leq \sqrt{Y}} \frac{1}{h} + 2 \sum_{h \leq \sqrt{Y}} 1,\tag{14}\] and then apply to 14 a standard harmonic number estimate. Explicitly, this estimate is such that \[\label{secondharmonic} \sum_{h \leq \sqrt{Y}}\frac{1}{h} \leq 1 + \int_1^{\sqrt{Y}} \frac{dt}{t} = 1 + \frac{1}{2} \log Y,\tag{15}\] with 14 and 15 together giving us that \(\sum_{m=0}^{M-1} d(a + m A)\) \(\leq\) \(2M \big( 1 + \frac{1}{2} \log Y \big) + 2 \sqrt{Y}\). Moreover, if \(\sqrt{Y} \leq M \log Y\), then (using the bound \(Y \geq 3\)) we have that \(2 M \big( 1 + \frac{1}{2} \log Y \big) \leq 3 M \log Y\) and \(2 \sqrt{Y} \leq 2 M \log Y\), and hence the desired bound in ?? . ◻

Proof. Choose \(X_0\) to be large enough so as to guarantee that: For all \(X \geq X_0\), we have that \(k \geq 1\) and that \(L \geq 2\) and that \[\label{Lhalfk} \frac{L}{2} \geq k\tag{16}\] and that \[\label{sqrtLpower} \sqrt{L} + 1 \leq 2^{L/2}.\tag{17}\] This is possible, from the given definitions for \(k\) and \(L\). Rewrite \(\sum_{m=0}^{M-1} T_{m, k}\) so that \[\begin{align} \sum_{m=0}^{M-1} T_{m, k} & = \sum_{m=0}^{M-1} \sum_{\ell \geq k} \frac{d(r + m A + \ell)}{2^{\ell}} \\ & = \sum_{\ell \geq k} 2^{-\ell} \sum_{m=0}^{M-1} d(r + \ell + m A). \end{align}\] Writing \[\begin{align} S_1 & = \sum_{\ell = k}^{L-1} 2^{-\ell} \sum_{m=0}^{M-1} d(r + \ell + m A) \;\text{and} \tag{18} \\ S_{2} & = \sum_{\ell \geq L} 2^{-\ell} \sum_{m=0}^{M-1} d(r + \ell + m A), \tag{19} \end{align}\] i.e., with \(\sum_{m=0}^{M-1} T_{m, k} = S_{1} + S_{2}\). We proceed to bound \(S_{1}\).

Fix \[\label{ellkL} \ell \in [k, L),\tag{20}\] i.e., so that \(\ell\) is among the indices in the outer sum in 18 . We claim that \[\label{coprimerellA} (r + \ell, A) = 1.\tag{21}\] By way of contradiction, suppose that there exists a prime \(p\) such that \(p \mid A\) and \(p \mid (r + \ell)\). Since \(p \mid A\), this same prime is such that that there exists \(j_p \in [0, k)\) such that ?? holds. From ?? together with the congruence \(r + \ell \equiv 0 \pmod p\), we have, as a consequence, that \[\label{elljp0p} \ell - j_p \equiv 0 \pmod p.\tag{22}\] Since \(\ell \geq k\) and since \(j_p \leq k -1\), we have that \(\ell - j_p \geq 1\). Since \(\ell < L\) and since \(j_p \geq 0\), we have that \(\ell - j_p < L\). Consequently, the bounds \(1 \leq \ell - j_p < L\) hold. By assumption, each prime divisor \(p\) of \(A\) is such that \(p > L\), i.e., so that \(1 \leq \ell - j_p < p\), but this contradicts (via 22 ) that \(p\) divides \(\ell - j_p\). This proves the relation in 21 .

Now, set \(a = r + \ell\). Recall that \(r \in \mathbb{N}_{0}\). Also recall that \(k \geq 1\), with \(\ell \geq k\). So, the bound \(a \geq 1\) holds. As above, we have shown that \((a, A) = 1\) holds, i.e., so that the condition displayed in ?? within Lemma 2 holds. We again have that \(\ell \leq L-1\), recalling that we are working under the assumption that \(k\) is in the index set indicated in 20 . With regard to the condition in ?? associated with Lemma 2, we find that \[\begin{align} a + (M-1) A & = r + \ell + (M-1) A \\ & \leq r + (L-1) + (M-1) A, \end{align}\] so that the assumption in ?? gives us that \(a + (M - 1) A \leq Y\) holds, so that all of the fundamental conditions for Lemma 2 are satisfied. Moreover, from the assumption in ?? , Lemma 2 gives us (via ?? ) that \[\sum_{m=0}^{M-1} d(r + \ell + m A) \leq 5 M \log Y,\] i.e., so that \(S_{1} \leq 5 M \log Y \sum_{\ell = k}^{L-1} 2^{-\ell}\), which implies that \[\label{S1final} S_{1} \leq 10 M (\log Y) 2^{-k}.\tag{23}\]

We proceed to bound \(S_2\). In this case, we exploit the elementary bound \[\label{dsqrt} d(N) \leq 2 \sqrt{N},\tag{24}\] which follows from a pairing argument given previously. Starting with the assumption in ?? , from the above assumption that \(L \geq 2\), we have that \(r + (M-1) A \leq Y\), so that \[\label{implyboundY} m \in [0, M) \Longrightarrow r + m A \leq Y.\tag{25}\] We henceforth let \(\ell \geq L\), i.e., so that \(\ell\) is an index associated with the outer sum in 19 . Again letting \(m \in [0, M)\), from 25 , we write \(r + \ell + m A \leq Y + \ell\), so that the divisor bound in 24 gives us that \(d(r + \ell + m A) \leq 2 \sqrt{Y + \ell}\), i.e., so that \[\label{S2elementary} S_{2} \leq 2 M \sum_{\ell \geq L} 2^{-\ell} \sqrt{Y + \ell}.\tag{26}\] Using the inequality \(\sqrt{Y + \ell} \leq \sqrt{Y} + \sqrt{\ell}\), we have that \[\label{detailsforS2} \sum_{\ell \geq L} 2^{-\ell} \sqrt{Y + \ell} \leq \sqrt{Y} \sum_{\ell \geq L} 2^{-\ell} + \sum_{\ell \geq L} 2^{-\ell} \sqrt{\ell},\tag{27}\] by evaluating the first series on the right of 27 in closed form, and by using the bound on \(Y\) in ?? , we find that \[\label{toreindex} \sum_{\ell \geq L} 2^{-\ell} \sqrt{Y + \ell} \leq 2^{1 - L/2} + \sum_{\ell \geq L} 2^{-\ell} \sqrt{\ell}.\tag{28}\] We then apply a reindexing argument to the right-hand series in 28 , writing \[\label{secondsqrtineq} \sum_{\ell \geq L} 2^{-\ell} \sqrt{\ell} = 2^{-L} \sum_{t \geq 0} 2^{-t} \sqrt{L + t},\tag{29}\] and we again exploit an elementary inequality of the form \(\sqrt{L + t} \leq \sqrt{L} + \sqrt{t}\), with 29 giving us that \(\sum_{t \geq 0} 2^{-t} \sqrt{L + t} \leq \sqrt{L} \sum_{t \geq 0} 2^{-t} + \sum_{t \geq 0} 2^{-t} \sqrt{t} \leq C_0 \big( \sqrt{L} + 1 \big)\), for an absolute constant \(C_0\). Exploiting the bound \(\sqrt{L} + 1 \leq 2^{L/2}\) in 17 , we obtain that \[\label{aftersqrtLpow} \sum_{\ell \geq L} 2^{-\ell} \sqrt{\ell} \leq C_0 2^{-L} \big( \sqrt{L} + 1 \big) \leq C_{0} 2^{-L/2}.\tag{30}\] From 28 and 30 , we find that \(\sum_{\ell \geq L} 2^{-\ell} \sqrt{Y + \ell} \leq 2^{1 - L/2} + C_{0} 2^{-L/2}\), i.e., so that \(\sum_{\ell \geq L} 2^{-\ell} \sqrt{Y + \ell} \leq C_{1} 2^{-L/2}\) for an absolute constant \(C_{1}\). Exploiting the bound in 16 , we obtain that \(\sum_{\ell \geq L} 2^{-\ell} \sqrt{Y + \ell} \leq C_{1} 2^{-k}\), i.e., so that \[\label{S2bound} S_{2} \leq 2 C_{1} M 2^{-k}.\tag{31}\] Since \(Y \geq 3\), we obtain from 31 that \[\label{S2final} S_2 \leq 2 C_1 M (\log Y) 2^{-k}.\tag{32}\] From the bounds for \(S_1\) and \(S_2\) in 23 and 32 , we find that there is an absolute constant \(C_{2}\) such that \[\label{finalsumT} \sum_{m=0}^{M-1} T_{m, k} \leq C_{2} M (\log Y) 2^{-k}.\tag{33}\] We proceed to set \(\mathcal{B} = \big\{ 0 \leq m < M : T_{m, k} > 2^{-k/2} \big\}\). For \(m \in \mathcal{B}\), we have that \(T_{m, k} > 2^{-k/2}\), so that \[\label{implicitMarkov} \sum_{m \in \mathcal{B}} T_{m, k} \geq \sum_{m \in \mathcal{B}} 2^{-k/2} = | \mathcal{B} | 2^{-k/2}.\tag{34}\] From 34 , we proceed to write \[\label{afterMarkov} |\mathcal{B}| 2^{-k/2} \leq \sum_{m \in \mathcal{B}} T_{m, k} \leq \sum_{m=0}^{M-1} T_{m, k},\tag{35}\] so that 33 and 35 together give us the desired bound, writing \(C_{\operatorname{tail}} = C_{2}\). ◻

Proof. Let \(X\) be a real number (that is sufficiently large for the purposes of certain applications below). Our strategy, at a basic level, is to construct an integer \(n = n(X)\) such that the \(n^{\text{th}}\) and \((n+1)^{\text{th}}\) binary digits after the binary point of \(E\) are both \(1\). We then let \(X \to \infty\), and we formalize how this is permissible.

Set \(\Lambda = \frac{\log X}{\log 2}\) and \(k = \lfloor \Lambda^{1/10} \rfloor\) and \(L = \lfloor \Lambda^{2} \rfloor\). For sufficiently large values of \(X\), we have that \(k \geq 3\).

We apply the formulation of the Alford–Granville–Pomerance lemma [5] (cf.[3]) given in Lemma 1. Being consistent with the notation in Lemma 1, we set \(\delta = \frac{1}{4}\), and we set \(N = X\), i.e., with the assumption that \(X\) is sufficiently large so that \(X > N_0\). Again adopting the notation from Lemma 1, we write \(\mathcal{D}(N) = \mathcal{D}(X)\) to denote the exceptional set described in this lemma. So, by the AGP lemma, the inequality \[\label{repeatAGP} \pi\big( X; d, a \big) \geq \frac{X}{2 \varphi(d) \log X}\tag{36}\] holds for all moduli \(d \leq N^{1/4} = X^{1/4}\) not divisible by any exceptional element of \(\mathcal{D}(N) = \mathcal{D}(X)\), and 36 also holds for \(a\) coprime to \(d\). Our strategy, at this point, is to construct a modulus \(B\) to which the AGP lemma, with our specified values, is to be applied.

Define \[\begin{gather} \mathcal{P}_{\operatorname{bad}} = \\ \Big\{ p \in (L, 2L) : \text{p is prime and p \mid D for some D \in \mathcal{D}(X) with D \leq X^{1/4}} \Big\}. \end{gather}\] We aim to estimate the size of \(\mathcal{P}_{\operatorname{bad}}\). In this direction, for a positive integer \(D\), we set \[\omega_{(L, 2L)}(D) = \#\big\{ p \in (L, 2L) : \text{p is prime and p \mid D} \big\}.\] If \(\omega_{(L, 2L)}(D) = r\) for some integer \(r\), then \(D\) is divisible by the product of \(r\) distinct primes, each exceeding \(L\), i.e., so that \(D \geq L^{r}\), so that \(r \leq \frac{\log D}{\log L}\). So, if \(D \leq X^{1/4}\), then \(\omega_{(L, 2L)}(D) \leq \frac{\log X}{4 \log L}\). Now, by the Alford–Granville–Pomerance lemma (again adopting notation from Lemma 1), we have that the number of elements in \(\mathcal{D}(N)\) is at most \(\overline{\mathcal{D}} = \overline{\mathcal{D}}(\delta)\) (depending only on \(\delta = \frac{1}{4}\)). We see that \[\begin{align} |\mathcal{P}_{\operatorname{bad}}| & \leq \sum_{\substack{ D \in \mathcal{D}(X) \\ D \leq X^{1/4} }} \omega_{(L, 2L)}(D) \\ & \leq \overline{\mathcal{D}} \frac{\log X}{4 \log L}. \end{align}\] Since we have set \(\delta = \frac{1}{4}\), and since \(\overline{\mathcal{D}} = \overline{\mathcal{D}}(\delta)\) depends only on \(\delta\), we have that \(\overline{\mathcal{D}}\) is fixed, so that \(\left| \mathcal{P}_{\operatorname{bad}} \right| \ll \frac{\log X}{\log L}\).

Let \[\label{mathcalAX} \mathcal{A}_{X} = \{ p \in (L, 2L) : \text{p is prime and p \not\in \mathcal{P}_{\operatorname{bad}}} \}.\tag{37}\] Our construction requires that \(\mathcal{A}_{X}\) contain at least \[\label{closedsubstack} 1 + \sum_{\substack{ 0 \leq j < k \\ j \neq 2 }} (j+1) = \frac{k(k+1)}{2} - 2.\tag{38}\] For \(k \geq 3\), the right-hand side of 38 is \(\leq k^2\). By the prime number theorem, there exists an absolute constant \(c_{\pi} > 0\) such that: For all sufficiently large \(L\), the bound \[\label{pifloor} \pi\left( \lfloor 2L \rfloor - 1 \right) - \pi(L) \geq c_{\pi} \frac{L}{\log L}\tag{39}\] holds. The definition of \(\mathcal{A}_{X}\) gives us, in a direct way, that the cardinality of 37 satisfies \[\label{cardinalityrel} \left| \mathcal{A}_{X} \right| = \pi\left( \lfloor 2L \rfloor - 1 \right) - \pi(L) - \left| \mathcal{P}_{\operatorname{bad}} \right|.\tag{40}\] Applying 39 and the upper bound for \(| \mathcal{P}_{\operatorname{bad}} |\) established above to the cardinality relation in 40 , we find that \[\label{boundcardinal} \left| \mathcal{A}_{X} \right| \geq c_{\pi} \frac{L}{\log L} - \overline{\mathcal{D}} \frac{\log X}{4 \log L}.\tag{41}\] Recall that \(\Lambda = \frac{\log X}{\log 2}\) and that \(L = \lfloor \Lambda^{2} \rfloor\). So, for all sufficiently large \(X\), we have that \[\label{Lquadratically} L \geq \frac{1}{2} \Lambda^{2} = \frac{ (\log X)^{2} }{2 (\log 2)^2}.\tag{42}\] Since \(L\) grows quadratically in \(\log X\) according to 42 , we can conclude that: For sufficiently large \(X\), the relation \[\label{dividelog} \overline{\mathcal{D}} \frac{\log X}{4} \leq \frac{c_{\pi}}{2} L\tag{43}\] holds. From 41 and 43 together, we may deduce that \[\label{boundAlikepi} \left| \mathcal{A}_{X} \right| \geq \frac{c_{\pi}}{2} \frac{L}{\log L}.\tag{44}\] Since \(k = \lfloor \Lambda^{1/10} \rfloor\), we have (for sufficiently large \(X\)) that \(k^2 \leq \Lambda^{1/5}\). In a similar spirit, since \(L = \lfloor \Lambda^{2} \rfloor\), we have that \(\frac{L}{\log L} \asymp \frac{\Lambda^2}{\log \Lambda}\). Consequently, we obtain the relations \(\frac{L/\log L}{k^2} \gg \frac{ \Lambda^2 / \log \Lambda }{\Lambda^{1/5}} = \frac{\Lambda^{9/5}}{\log \Lambda} \to \infty\) as \(X \to \infty\). So, for sufficiently large \(X\), the relation \[\label{lowerksquare} \frac{c_{\pi}}{2} \frac{L}{\log L} \geq k^2\tag{45}\] holds. From 44 and 45 , since \(|\mathcal{A}_{X}| \geq k^2\), we can deduce that: For sufficiently large \(X\), the number of primes in the set \((L, 2L) \setminus \mathcal{P}_{\operatorname{bad}}\) is greater than or equal to the left-hand side of 38 .

From the argument in the preceding paragraph, we are permitted, for sufficiently large \(X\), to choose distinct primes \(q_0\) and \(p_{j, t}\) for \(0 \leq j < k\) and \(j \neq 2\) and \(1 \leq t \leq j +1\) from the set \((L, 2L) \setminus \mathcal{P}_{\operatorname{bad}}\). For \(j \neq 2\), define \[\label{Pprodprime} P_j = \prod_{t=1}^{j+1} p_{j, t}.\tag{46}\] Also define \[\label{Aprodprime} A = q_0^3 \prod_{\substack{ 0 \leq j < k \\ j \neq 2 }} P_{j}^2\tag{47}\] and \[\label{Bprodprime} B = \frac{A}{q_0^2} = q_0 \prod_{\substack{ 0 \leq j < k \\ j \neq 2 }} P_j^2.\tag{48}\]

We claim that \[\label{Broot} B \leq X^{1/4}\tag{49}\] for sufficiently large \(X\). Each chosen prime is \(< 2 L\), and the total number of prime factors of \(B\), counted with multiplicity, is \(O(k^2)\). So, we find that \(\log B = O(k^2 \log L) = O( \Lambda^{1/5} \log \Lambda ) = o(\log X)\), and hence 49 holding for sufficiently large \(X\).

By way of contradiction, suppose that there exists an element \(D \in \mathcal{D}(X)\) that divides \(B\). From 49 , we find that \[\label{DBXquarter} D \leq B \leq X^{1/4}\tag{50}\] for all sufficiently large \(X\). Since each member of \(\mathcal{D}(X)\) exceeds \(\log X\), we have, for sufficiently large \(X\), that \(D > 1\). So, the integer \(D\) has at least one prime divisor. From the assumption that \(D \mid B\), every prime that divides \(D\) also divides \(B\), and thus is among the chosen primes from \((L, 2L)\). We thus choose a prime divisor \(p\) of \(D\), but, since \(D \in \mathcal{D}(X)\) and since 50 gives us that \(D \leq X^{1/4}\), we have that \(p \in \mathcal{P}_{\operatorname{bad}}\). This contradicts that the chosen primes were chosen outside of \(\mathcal{P}_{\operatorname{bad}}\). So, we have that no element in \(\mathcal{D}(X)\) divides \(B\).

Now, recall the formulation of the CRT given above. Our construction gives us, in a direct way, that expressions of the forms \(q_0^3\) and \(P_j^2\) for \(0 \leq j < k\) and \(j \neq 2\) are pairwise coprime. So, the CRT gives us that there is a residue \(r\) simultaneously satisfying \[\label{firstequivCRT} r \equiv q_0^2 - 2 \pmod {q_{0}^{3}}\tag{51}\] and \[\label{secondequivCRT} r \equiv P_j - j \pmod {P_{j}^{2}}\tag{52}\] for \(0 \leq j < k\) and \(j \neq 2\). Moreover, the above residue \(r\) is unique modulo the product of the moduli, which is precisely \(A\) as defined in 47 . We then fix \(r\) as the unique residue class such that \[\label{rbounds} 0 \leq r < A.\tag{53}\] From 51 , we find that \(r+2\) is divisible by \(q_0^2\), and this leads us to define \[\label{defines} s = \frac{r+2}{q_0^2}.\tag{54}\] Since \(0 \leq r < A = q_0^2 B\), we deduce that \[\label{rplus2bound} 0 < r + 2 \leq q_0^2 B + 1.\tag{55}\] Since \(q_0^2 \mid (r+2)\), this and the definition of \(s\) in 54 and the inequalities in 55 gives us that \[\label{sbounds} 1 \leq s \leq B.\tag{56}\] From 51 and the definition of \(s\), we see that \(q_0^2 s \equiv q_0^2 \pmod {q_{0}^{3}}\). Since \(q_0^3 \mid q_0^2 (s-1)\), it follows that \(q_0 \mid (s-1)\), i.e., so that \[\label{s1modq} s \equiv 1 \pmod {{q}_{0}}.\tag{57}\] Recalling 48 , we see that \(q_0 \mid B\). From this divisibility relation and the congruence in 57 , we deduce that it is not the case that \(s= B\). We thus may refine 56 , writing \[\label{stricts} 1 \leq s < B.\tag{58}\]

We claim that \[\label{sB1} (s, B) = 1.\tag{59}\] To begin with, the relation in 57 allows us to deduce that \(q_0 \nmid s\). Now, write \(p\) in place of one of the other prime divisors of \(B\). Observe that \(p \mid P_j\), i.e., for some index \(j \in [0, k) \setminus \{ 2 \}\) associated with the product in 48 (recalling the condition such that \(j \neq 2\)). Moreover, the congruence in 52 allows us to write \(r + j = P_j^2 z + P_j\) for some integer \(z\), so that \(r + j \equiv 0 \bmod p\), so that \(r + 2 \equiv 2 - j \bmod p\), i.e., so that \[\label{q0squareds} q_0^2 s \equiv 2 - j \pmod p.\tag{60}\] By way of contradiction, suppose that \(p \mid s\). With this assumption, the equivalence in 60 allows us to deduce that \[\label{2minusjequiv} 2 - j \equiv 0 \pmod p.\tag{61}\] Since \(j \neq 2\) and \(2 \geq 2 - j > 2 -k\) and \(p > L\) (recalling that \(p \in (L, 2L)\) by construction) and \(L > k\) (recalling that \(k = \lfloor \Lambda^{1/10} \rfloor\) and \(L = \lfloor \Lambda^2 \rfloor\)), we find that \(0 < |2 - j | < p\), contradicting (via 61 ) that \(p \mid (2-j)\). So, the relation \(p \nmid s\) holds, so that 59 holds, as desired.

We proceed to apply the AGP estimate in Lemma 1 and in 36 , with \(d = B\) and \(a = s\). We are permitted to apply Lemma 1, since:

\(\bullet\) \(B \leq X^{1/4}\) by 49 ;

\(\bullet\) \(B\) is not divisible by any element of \(\mathcal{D}(X)\), from the preceding paragraph; and

\(\bullet\) \(s\) and \(B\) are coprime, as established in the preceding paragraph.

So, since the required conditions of Lemma 1 are satisfied, we find that \[\label{applyAlford} \pi(X; B, s) \geq \frac{X}{ 2 \varphi(B) \log X },\tag{62}\] recalling that we are writing \(X\) in place of \(N\). Since \(\varphi(B) \leq B\), we obtain from 62 that \[\label{piX2BlogX} \pi(X; B, s) \geq \frac{X}{ 2 B \log X }.\tag{63}\]

Now, define \[\label{definecapM} M_{X, B} = M = \left\lfloor \frac{X}{B} \right\rfloor + 1.\tag{64}\] For \(M\) as defined in 64 , and for arbitrary \(m \in [0, M)\), we then define \[\label{nmwithoutp} n_m = r + m A.\tag{65}\] Again for \(M\) as in 64 , we also define \[\label{mathcalG} \mathcal{G}_{X, M} = \mathcal{G}_{X} = \{ 0 \leq m < M : s + m B \leq X, \;s + m B \;\text{prime} \}.\tag{66}\]

Since \(1 \leq s < B\) (recalling 58 ), the map \(m \mapsto s + m B\) provides a bijection from \(\mathcal{G}_{X}\) onto the set of primes \(p \leq X\) satisfying \(p \equiv s \bmod B\). Indeed, if \(p \leq X\) and \(p \equiv s \bmod B\), then \(p = s + m B\) for a unique integer \(m\). Since \(p > 0\) and since \(1 \leq s < B\) (again recalling 58 ), the \(m < 0\) case would be impossible, because, otherwise, we would have that \(p = s + m B \leq s - B < 0\). So, we obtain the nonnegativity of \(m \geq 0\). Since \(p \leq X\) and \(s \geq 1\), we find that \(m B = p - s < X\), i.e., so that \(0 \leq m < \frac{X}{B} < M\), with \(m \in \mathcal{G}_{X}\). Conversely, each element \(m \in \mathcal{G}_{X}\) gives rise to a prime of the form \(p = s + m B\), and hence the equality \(|\mathcal{G}_{X}| = \pi(X;B,s)\).

Recalling (via 49 ) that \(B \leq X^{1/4}\), we find that \(\frac{X}{B} \to \infty\), and we can deduce that: For sufficiently large \(X\), the relation \(M \leq \frac{2X}{B}\) holds. From 63 , we have, as a consequence, that \[\label{Mover4logX} |\mathcal{G}_{X}| = \pi(X; B, s) \geq \frac{M}{4 \log X}\tag{67}\] holds for sufficiently large \(X\).

For \(m \in \mathcal{G}_{X}\), set \(p = s + m B\). Then \(p\) is a prime and \(p \leq X\). Moreover, the definition in 65 gives us that \[\label{nmplus2} n_m + 2 = r + 2 + m A.\tag{68}\] The definition of \(s\) in 54 gives us that \(r + 2 = q_0^2 s\), and the definition of \(B\) in 48 gives us that \(A = q_0^2 B\). So, the equality in 68 then gives us that \[\label{nm2factor} n_m + 2 = q_0^2 s + m q_0^2 B = q_0^2 (s + m B) = q_0^2 p.\tag{69}\] From 48 , we obtain the divisibility relation \(q_0 \mid B\), so that \(p = s + m B \equiv s \bmod {{q}_{0}}\). From the congruence in 57 , we then find that \[\label{pequiv1modq} p \equiv 1 \pmod {{q}_{0}},\tag{70}\] and we can see from 70 that \(p \neq q_0\). So, from 69 , we see that \[\label{maind6} d(n_m +2) = d(q_0^2 p) = 6.\tag{71}\] So, a combined application of 67 and 71 gives us that \[\label{GpiMX} \#\big\{ m \in [0, M) : d(n_m + 2) = 6 \big\} \geq |\mathcal{G}_{X}| =\pi(X;B,s) \geq \frac{M}{4 \log X}.\tag{72}\]

Now, we proceed to apply the tail estimate given in Lemma 3, letting \[\label{Yfortail} Y = 2 q_0^2 X.\tag{73}\] We demonstrate, as below, that the required conditions in Lemma 3 are all satisfied.

Recall that \(q_0\) is chosen from the set \((L, 2L) \setminus \mathcal{P}_{\operatorname{bad}}\), i.e., so that \(q_0 < 2 L\). This together with 73 give us that \[\label{applylog2} Y \leq 8 L^2 X.\tag{74}\] We let \(\log_2\) denote the base-2 logarithm. Applying this to both sides of 74 , and using the definition of \(\Lambda = \log_2 X\), we find that \[\label{boundlog2Y} \log_2 Y \leq \Lambda + O(\log L).\tag{75}\] Since \(L = \lfloor \Lambda^2 \rfloor\), applying this in conjunction with 75 allows us to deduce that: For sufficiently large \(X\), the bound \(\log_2 Y \leq L\) holds, i.e., so that \(Y \leq 2^L\), giving us that the condition in ?? holds for sufficiently large \(X\).

Recall (from 49 ) that \(B \leq X^{1/4}\). This gives us that \[\label{MXthreequarters} M = \left\lfloor \frac{X}{B} \right\rfloor + 1 \geq \frac{X}{B} \geq X^{3/4}.\tag{76}\] From the definition in 73 together with the bound \(q_0 < 2 L\), we find that \(\sqrt{Y} \leq 2 \sqrt{2} L X^{1/2}\). Since \(Y = 2 q_0^2 X \geq X\), we find that \(\log Y \geq \log X\). So, we obtain the lower bound \[\label{MlogYoversqrtY} \frac{M \log Y}{\sqrt{Y}} \geq \frac{X^{3/4} \log X}{2 \sqrt{2} L X^{1/2}} = \frac{1}{2\sqrt{2}} \frac{X^{1/4} \log X}{L}.\tag{77}\] Since \(L = \lfloor \Lambda^{2} \rfloor\) and \(\Lambda = \frac{\log X}{\log 2}\), we find that \[\label{reciprocalL} \frac{1}{L} \geq \frac{ (\log 2)^{2} }{ (\log X)^2 }.\tag{78}\] As a consequence of both 77 and 78 , we find that \[\label{betterMlogY} \frac{M \log Y}{\sqrt{Y}} \geq \frac{\log^2 2}{2\sqrt{2}} \frac{X^{1/4}}{\log X}.\tag{79}\] Since the right-hand side of 79 tends to infinity as \(X \to \infty\), we can conclude that \(\frac{M \log Y}{\sqrt{Y}} \geq 1\) for all sufficiently large \(X\), i.e., so that \(\sqrt{Y} \leq M \log Y\) for all sufficiently large \(X\), i.e., so that the desired condition in ?? within Lemma 3 holds.

Recalling the bounds on \(r\) in 53 , and recalling the relation \(A = q_0^2 B\) given in 48 , we find that \[\label{reboundr} 0 \leq r < q_0^2 B.\tag{80}\] Also, recalling the definition of \(M\) on display in 64 , we find that \[\label{boundMminus1} M - 1 \leq \frac{X}{B}.\tag{81}\] A combined application of 80 and 81 then gives us that \[\label{withouto} r + (L-1) + (M-1) A \leq q_0^2 B + L + q_0^2 X.\tag{82}\] Recalling, from 49 , that \(B \leq X^{1/4}\), and recalling that \(L \asymp (\log X)^{2}\) (since \(L = \lfloor \Lambda^{2} \rfloor\) and \(\Lambda = \frac{\log X}{\log 2}\)), we have that \[\label{witho} q_0^2 B + L = o\big( q_0^2 X \big).\tag{83}\] A combined application of 73 , 82 , and 83 then gives us that: For sufficiently large \(X\), the bound \(r + (L-1) + (M-1) A \leq 2 q_0^2 X = Y\) holds. So, the desired condition in ?? within Lemma 3 holds.

Now, every prime divisor of \(A\) is a prime chosen in \((L, 2L)\), i.e., so that if \(p \mid A\), then \(p > L\). So, the desired implication in ?? holds.

Now, for a prime divisor \(p \mid A\), we want to determine a value \(j_p \in \{ 0, 1, \ldots, k - 1 \}\), such that \[\label{rjp0p} r + j_p \equiv 0 \pmod p,\tag{84}\] noting that we are working under the assumption that \(k \geq 3\). Recall that \(q_0^2 \mid (r+2)\), as established above, in our construction of the value \(s\) defined in 54 . So, we find that the prime \(q_0\) divides \(r+2\). So, if \(p\) happens to be equal to \(q_0\), then, in this case, we set \(j_p = j_{q_0} = 2\), i.e., so that the desired congruence relation in 84 holds. Now, recall the consequence of the CRT in 52 . We proceed to rewrite the congruence in 52 so that \(r + j \equiv P_j \pmod {P_{j}^{2}}\). Since \(p_{j, t}\) divides \(P_j\) (and \(P_j^2\)), and since \({P_{j}^{2}}\) divides \(r + j - P_j\), we have that \[\label{pjtmid} p_{j, t} \mid (r + j - P_j).\tag{85}\] Again since \(p_{j, t}\) divides \(P_j\), we deduce from 85 that \(p_{j, t}\) divides \(r + j\). So, if \(p = p_{j, t}\), then we let \(j_p = j\), so that 84 is satisfied. So, we have that the final condition of Lemma 3 holds, in reference to the condition involving ?? .

So, from our above construction, since all of the conditions of Lemma 3 are satisfied, we obtain from Lemma 3 that: There exists an absolute constant \(C_{\operatorname{tail}} > 0\) such that: For all sufficiently large \(X\), the inequality \[\label{bigenumerate} \#\left\{ m \in [0, M) : \sum_{\ell \geq k} \frac{d(n_m + \ell)}{2^\ell} > 2^{-k/2} \right\} \leq C_{\operatorname{tail}} M (\log Y) 2^{-k/2}\tag{86}\] holds.

From the definition of \(Y\) in 73 , we see that \(\log Y = O(\log X)\). Moreover, since \(k = \lfloor \Lambda^{1/10} \rfloor\), we have that \(\Lambda^{1/10} - 1 < k \leq \Lambda^{1/10}\), so that \(\frac{1}{2} \Lambda^{1/10} - \frac{1}{2} < \frac{k}{2} \leq \frac{1}{2} \Lambda^{1/10}\), so that \(\frac{k}{2} = \frac{1}{2} \Lambda^{1/10} + O(1)\), so that, for any positive power \(\alpha\), we obtain that \[\begin{align} 2^{k/2} & = 2^{\frac{1}{2} \Lambda^{1/10} + O(1)} \\ & = \exp\left( \left( \log 2 \right) \left( \frac{1}{2} \Lambda^{1/10} + O(1) \right) \right) \\ & = \exp\left( \frac{\log 2}{2} \Lambda^{1/10} + O(1) \right) \\ & \gg \left( \log X \right)^{\alpha}. \end{align}\] So, since \(2^{-k/2} \ll \frac{1}{(\log X)^{\alpha}}\), we find (setting \(\alpha =3\)) that \(C_{\operatorname{tail}} M (\log Y) 2^{-k/2} = o\left( \frac{M}{\log X} \right)\). So, for all sufficiently large \(X\), the inequality \[\label{upperM4logX} C_{\operatorname{tail}} M (\log Y) 2^{-k/2} < \frac{M}{4 \log X}\tag{87}\] holds. From 72 , there are at least \(\frac{M}{4 \log X}\) integers \(m \in [0, M)\) such that \(d(n_m + 2) = 6\), From 86 and 87 , there are strictly fewer than \(\frac{M}{4 \log X}\) integers \(m \in [0, M)\) satisfying \(\sum_{\ell \geq k} \frac{d(n_m + \ell)}{2^\ell} > 2^{-k/2}\). So, using a “pigeonhole-like” counting argument, there is at least one integer \(m \in [0, M)\) such that both \[\label{clarityrewrite1} d(n_m + 2) = 6\tag{88}\] and \[\label{clarityrewrite2} \sum_{\ell \geq k} \frac{d(n_m + \ell)}{2^\ell} \leq 2^{-k/2}\tag{89}\] hold. We fix such an integer \(m\), and write \(n = n_m\). Writing \(n = n_m\), the relations in 88 and 89 become \[\label{dnplus2} d(n + 2) = 6.\tag{90}\] and \[\label{simplifytail} \sum_{\ell \geq k} \frac{d(n + \ell)}{2^{\ell}} \leq 2^{-k/2}.\tag{91}\]

Let \(j \neq 2\), with \(j \in [0, k)\). Recalling the definition in 47 , we have that \(P_j^2\) divides \(A\). So, since \(n+j = r + m A +j\), we have that \[\label{nplusjequiv} n + j \equiv (r+j) \pmod {P_j^2}.\tag{92}\] Our application of the CRT in 52 then gives us, in conjunction with 92 , that \[\label{Pjmodsquare} n + j \equiv P_j \pmod {P_{j}^{2}}.\tag{93}\] Recalling the definition in 46 , we find that: For \(t = 1, 2, \ldots, j+1\), the prime \(p_{j, t}\) divides \(P_j\), but \(p_{j, t}^2 \nmid P_j\). From 93 , we have that \[\label{capPjsquaredmid} P_j^2 \mid (n + j - P_j).\tag{94}\] So, since \(p_{j, t} \mid P_j^2\) and \(p_{j, t} \mid P_j\), we have that \(p_{j, t} \mid (n + j)\). We also claim that \(p_{j, t}^{2} \nmid (n+j)\), and we proceed by contradiction, assuming instead that \[\label{contradictpjt} p_{j, t}^{2} \mid (n+j).\tag{95}\] From 94 , again since \(p_{j, t}^2 \mid P_{j}^2\), we have that \[\label{usetocontradict} p_{j, t}^2 \mid (n + j - P_j).\tag{96}\] From 95 and 96 , these together would imply that \(p_{j, t}^{2} \mid P_j\), which does not hold. So, we have shown that \(p_{j, t} \mid (n + j)\) and that \(p_{j, t}^{2} \nmid (n + j)\) for fixed \(j\) and for the indices \(t \in [1, j+1]\) associated with the product in 46 . So, the integer \(n+j\) has at least \(j+1\) distinct prime divisors that each have an exponent exactly equal to \(1\) in the prime factorization of \(n + j\). Therefore, the relation \[\label{2jplus1mid} 2^{j+1} \mid d(n+j)\tag{97}\] holds for all \(j \in [0, k) \setminus \{2 \}\).

Now, we rewrite the latter series expansion for the Erdős–Borwein constant in 1 so that \[\label{rewriteE} E = \sum_{1 \leq t < n} \frac{d(t)}{2^t} + \sum_{\substack{0\leq j < k \\ j \neq 2}} \frac{d(n+j)}{2^{n+j}} + \frac{d(n+2)}{2^{n + 2}} + \sum_{\ell \geq k} \frac{d(n +\ell)}{2^{n + \ell}}.\tag{98}\]

Now, write \[\label{mathcalP} \mathcal{P} = \sum_{1 \leq t < n} \frac{d(t)}{2^t} + \sum_{\substack{0 \leq j < k \\ j \neq 2}} \frac{d(n+j)}{2^{n+j}}.\tag{99}\] Our goal, at this point, is to show that \(\mathcal{P}\) is an integer multiple of \(2^{-(n-1)}\). In this direction, if \(1 \leq t < n\), then \(\frac{d(t)}{2^t} = d(t) 2^{n - 1 - t} \, 2^{-(n-1)}\) is an integer multiple of \(2^{-(n-1)}\). If \(j \in [0, k) \setminus \{2 \}\), then, as above, the relation in 97 holds, so that \(\frac{d(n+j)}{2^{n+j}} = \frac{d(n+j)/2^{j+1} }{2^{n-1}}\) is an integer multiple of \(2^{-(n-1)}\). So, there is an integer \(\mathcal{Q}\) satisfying \[\label{PtoQ} \mathcal{P} = \mathcal{Q} 2^{-(n-1)}.\tag{100}\] From 90 , write \[\label{isolatedcase} \frac{d(n+2)}{2^{n+2}} = \frac{3}{4} 2^{-(n-1)}.\tag{101}\] By analogy with 99 , we write \[\label{mathcalR} \mathcal{R} = \sum_{\ell \geq k} \frac{d(n + \ell)}{2^{n + \ell}}.\tag{102}\] Now, the simplified tail estimate in 91 gives us that \(\mathcal{R} = 2^{-n} \sum_{\ell \geq k} \frac{d(n + \ell)}{2^{\ell}} \leq 2^{-n} 2^{-k/2} = 2^{-n-k/2}\). Since we are and have been consistently working under the assumption that \(k \geq 3\), we find that \[\label{boundmathcalR} \mathcal{R} < 2^{-n-1} = \frac{1}{4} 2^{-(n-1)}.\tag{103}\] Now, we rewrite the right-hand side of 98 through a combined use of 100 , 101 , and 102 , with \(E = \mathcal{Q} 2^{-(n-1)} + \frac{3}{4} 2^{-(n-1)} + \mathcal{R}\), where 103 gives us that \(0 \leq \mathcal{R} < \frac{1}{4} 2^{-(n-1)}\). So, we find that \(2^{n-1} E = \mathcal{Q} + \frac{3}{4} + \theta\) for some real number \(\theta \in \big[0, \frac{1}{4} \big)\). So, the fractional part of \(2^{n-1} E\) is in \(\big[ \frac{3}{4}, 1 \big)\). Since \(E\) is irrational [2], the binary expansion of \(E\) is unique (which avoids any ambiguity regarding the possibility of non-terminating binary decimal expansions for rational values). Consequently, the first two binary digits after the binary point of \(2^{n-1}E\) are both \(1\). Consequently, the \(n^{\text{th}}\) and \((n+1)^{\text{th}}\) binary digits after the binary point of \(E\) are both \(1\).

Now, it remains to show (as below) that the \(n^{\text{th}}\) and \((n+1)^{\text{th}}\) positions above are unbounded as \(X \to \infty\).

Since \(n = r + m A\) and \(A\) is divisible by \(q_0^3\), while \(r + 2 \equiv q_0^2 \bmod q_0^3\), we have that \[\label{usefornu} n + 2 \equiv q_0^2 \bmod q_0^3.\tag{104}\] From the congruence in 104 , we see that \(n + 2 - q_0^2 = z q_0^3\) for some integer \(z\), so that \(n + 2 = q_0^2(1 + z q_0)\). This together with the inequivalence \(1 + z q_0 \not\equiv 0 \bmod q_0\) allow us to conclude that \(\nu_{q_0}(n+2)=2\) holds. Also, our construction gives us that \(d(n + 2) =6\). If \(z\) is a positive integer with \(d(z) = 6\), then either \(z = p^5\) for some prime \(p\) or \(z = p^2 q\) for distinct primes \(p\) and \(q\). Since \(\nu_{q_{0}}(n+2)=2\), the first case is impossible, so that the second case forces that \(n + 2 = q_0^2 p\) for some prime \(p \neq q_0\). Consequently, the inequality \(n + 2 \geq 2 q_0^2\) holds. Since \(q_0 > L = \lfloor \Lambda^2 \rfloor \to \infty\) as \(X \to \infty\), we find that \(n \to \infty\). This proves that the positions at which \(11\) occurs are unbounded. ◻