M. R. Gabdullin, S. V. Konyagin, V. V. Iudelevich, “Karatsuba's divisor problem and related questions”, Sb. Math., 214:7 (2023), 919

Loading [MathJax]/jax/element/mml/optable/MathOperators.js

$\begin{equation*} \Phi (x)=\sum_{p \leqslant x} \frac{1}{\tau(p-1)} \end{equation*} \notag$

$\begin{equation*} D(x)=\sum_{p\leqslant x}\tau(p-1). \end{equation*} \notag$

$\begin{equation*} D(x) \sim \frac{\zeta(2)\zeta(3)}{\zeta(6)}x, \qquad x\to\infty, \end{equation*} \notag$

$\begin{equation*} T(x)=\sum_{n\leqslant x}\frac{1}{\tau(n)}. \end{equation*} \notag$

$\begin{equation} T(x)=c_0\frac{x}{\sqrt{\log x}}\biggl( 1+O\biggl(\frac{1}{\sqrt{\log x}} \biggr)\biggr) , \end{equation} \tag{1.1}$

$\begin{equation*} c_0=\frac{1}{\sqrt{\pi}} \prod_{p} \sqrt{p^2 - p} \log \frac{p}{p-1}= 0.5486\dots\,. \end{equation*} \notag$

$\begin{equation*} \Phi(x)\leqslant 4K\frac{x}{(\log x)^{3/2}}+O\biggl( \frac{x\log\log x}{(\log x)^{5/2}}\biggr), \end{equation*} \notag$

$\begin{equation*} K=\frac{1}{\sqrt{\pi}}\prod_{p}\sqrt{\frac{p}{p-1}}\biggl(p\log\frac{p}{p-1} -\frac{1}{p-1}\biggr)=0.2532\dots\,. \end{equation*} \notag$

$\begin{equation*} \Phi(x) \sim K\frac{x}{(\log x)^{3/2}}, \qquad x\to\infty, \end{equation*} \notag$

Theorem 1.1. We have

$\begin{equation*} \Phi (x) \gg \frac{x}{(\log x)^{3/2}}. \end{equation*} \notag$

$\begin{equation*} \Phi(x)\asymp \frac{x}{(\log x)^{3/2}}, \end{equation*} \notag$

$\begin{equation*} F(x)=\sum_{n \leqslant x} \frac{1}{\tau(n^2+1)} \end{equation*} \notag$

Theorem 1.2. We have

$\begin{equation*} F(x)\asymp \frac{x}{(\log x)^{1/2}}. \end{equation*} \notag$

$\begin{equation} \Phi(x)=\sum_{\substack{a \leqslant x \\ p\mid a \ \Rightarrow\ p \leqslant z}} \frac{1}{\tau(a)} \sum_{\substack{b \leqslant (x-1)/a \\ p\mid b \ \Rightarrow\ p>z \\ ab +1\text{ is prime}}} \frac{1}{\tau(b)}, \end{equation} \tag{1.2}$

$\begin{equation*} \Phi(x)\gg_\varepsilon \sum_{a\leqslant x^\varepsilon} \frac{1}{\tau(a)} \sum_{\substack{b \leqslant (x-1)/a \\ p\mid b \ \Rightarrow\ p>x^\varepsilon \\ ab +1\text{ is prime}}} 1. \end{equation*} \notag$

$\begin{equation*} \frac{x}{a(\log x)^2}-R(x;a), \end{equation*} \notag$

$\begin{equation*} \Phi(x) \gg_\varepsilon \frac{x}{(\log x)^2}\sum_{a\leqslant x^\varepsilon} \frac{1}{a\tau(a)}\gg_\varepsilon \frac{x}{(\log x)^{3/2}}, \end{equation*} \notag$

$\begin{equation*} \sum_{p\leqslant x}\frac{1}{\tau_k(p-1)}\asymp_k x (\log x)^{1/k-2}. \end{equation*} \notag$

$\begin{equation} \mathcal{A}_d=Xg(d)+r_d, \end{equation} \tag{2.1}$

$\begin{equation*} \begin{gathered} \, V_j=\prod _{p \in \mathcal{P}_r} (1-g(p)), \qquad L_j=\log V_j^{-1}, \qquad E=\sum _{j=1}^{t} \frac{e^{L_j} (L_j)^{k_j+1}}{(k_j+1)!}, \\ R=\sum _{\substack{d_j\mid P_j\\ \omega(d_j) \leqslant k_j}} |r_{d_1 \dotsb d_t}| \quad\text{and}\quad R'=\sum _{l=1}^t \sum _{\substack{d_j\mid P_j \\ \omega(d_j) \leqslant k_j,\, j \ne l \\ \omega(d_l)=k_l+1}} |r_{d_1 \dotsb d_t}|. \end{gathered} \end{equation*} \notag$

Theorem 3.1. Let assumption (2.1) be met. Then

$\begin{equation*} S(\mathcal{A}, \mathcal{P}) \leqslant X \prod_{p \in \mathcal{P}} (1-g(p))e^{E} + R \end{equation*} \notag$

and

$\begin{equation*} S(\mathcal{A}, \mathcal{P}) \geqslant X \prod_{p \in \mathcal{P}} (1-g(p))(1-E) - R - R'. \end{equation*} \notag$

Lemma 3.2. Let $a \leqslant x^{1/40}$ be an even positive integer, and let

$\begin{equation*} F_a(x)=\#\biggl\{ n \leqslant \frac{x-1}a\colon an+1\textit{ is a prime number and } P^{-}(n)>x^{{1}/{40}} \biggr\}. \end{equation*} \notag$

Then for

$x\geqslant x_0$ ,

$\begin{equation*} F_a(x) \geqslant \frac{c_1\pi(x)}{\varphi(a)\log x}-R_1, \end{equation*} \notag$

where

$c_1>0$ is an absolute constant and

$\begin{equation*} 0\leqslant R_1\leqslant \sum_{d\leqslant x^{13/40}}|R(x;ad,1)|. \end{equation*} \notag$

Remark 3.3. Similar upper bounds without the error term $R_1$ can be obtained by sifting the set

$\begin{equation*} \biggl\{(an+1)(n+P)\colon n\leqslant\frac{x-1}a\biggr\}, \quad\text{where } P=\prod_{p\leqslant z}p. \end{equation*} \notag$

Proof of Lemma 3.2. We apply Theorem 3.1 to the sets

$\begin{equation*} \mathcal{A}=\biggl\{n \leqslant \frac{x-1}a\colon an + 1\text{ is prime}\biggr\} \end{equation*} \notag$

and

$\mathcal{P} = \{p \leqslant z\}$ , where

$z=x^{1/40}$ (the other parameters will be chosen later). Then

$F_a(x)=S(\mathcal{A}, \mathcal{P})$ , and for each

$d\mid P=\prod_{p\leqslant z}p$ we have

$\begin{equation*} \mathcal{A}_d=\#\biggl\{k\leqslant \frac{x-1}{ad}\colon adk+1\text{ is prime}\biggr\} =\pi(x; ad,1)=\frac{\pi(x)}{\varphi(ad)}+R(x; ad,1). \end{equation*} \notag$

Now we write a number

$d\mid P$ in the form

$d=d_1d_2$ , where

$(d_1,a)=1$ and

$d_2$ consists only of primes dividing

$a$ . Then, since

$\varphi(ad_2)=ad_2\prod_{p\mid a}(1-1/p)=d_2\varphi(a)$ , we find that

$\begin{equation*} \frac{1}{\varphi(ad)}=\frac{1}{\varphi(d_1)\varphi(ad_2)} =\frac{1}{\varphi(d_1)d_2\varphi(a)}, \end{equation*} \notag$

hence (2.1) holds for

$X= {\pi(x)}/{\varphi(a)}$ , the multiplicative function

$g$ defined by

$\begin{equation*} g(p)=\begin{cases} \dfrac{1}{p-1}&\text{if}\ (p,a)=1, \\ \dfrac{1}{p}&\text{otherwise}, \end{cases} \end{equation*} \notag$

and

$\begin{equation*} r_d=R(x; ad, 1). \end{equation*} \notag$

In addition, we have

$\begin{equation*} \prod_{p \in \mathcal{P}}(1-g(p))\asymp \frac{1}{\log x}, \end{equation*} \notag$

with an absolute implied constant.

Now we choose a partition of $\mathcal{P}$ and define the numbers $\{k_j\}_{j=1}^t$ . Set $z_j= z^{2^{1-j}}$ and

$\begin{equation*} \mathcal{P}_j=\mathcal{P} \cap (z_{j+1}, z_j]; \end{equation*} \notag$

then

$t$ is the unique positive integer such that

$z_{t+1} < 2 \leqslant z_t$ . Let

$k_j = b + 2(j-1)$ , where

$b \geqslant 2$ is even and will be chosen later. We also set

$\begin{equation*} C=\prod_{p>2}\biggl(1+\frac{1}{p^2-2p}\biggr)\leqslant 1.52. \end{equation*} \notag$

By [10], Theorem 7 (see (3.26) and (3.27) in that paper), for any

$x>1$ ,

$\begin{equation} \frac{e^{-\gamma}}{\log x}\biggl(1-\frac{1}{\log^2x}\biggr) < \prod_{p\leqslant x}\biggl(1-\frac1p\biggr) < \frac{e^{-\gamma}}{\log x}\biggl(1+\frac{1}{2\log^2x}\biggr), \end{equation} \tag{3.1}$

where

$\gamma$ is the Euler constant. Hence, for any

$z\geqslant \sqrt2$ we have

$\begin{equation} \prod_{z<p\leqslant z^2}\biggl(1-\frac1p\biggr)^{-1}\leqslant 3; \end{equation} \tag{3.2}$

indeed, this follows from (3.1) for

$z\geqslant 4$ and can be checked manually for

${\sqrt{2}\,{\leqslant}\,z\,{<}\,4}$ . Thus,

$\begin{equation*} V_j^{-1}=\prod_{z_{j+1} < p \leqslant z_j} (1 - g(p))^{-1} \leqslant C\prod_{z_{j+1}<p\leqslant z_j}\biggl(1-\frac1p\biggr)^{-1} \leqslant 3C\leqslant 5. \end{equation*} \notag$

Hence

$L_j = \log V_j^{-1}\leqslant L=\log 5$ and

$\begin{equation*} E=\sum_{j=1}^t \frac{e^{L_j} L_j^{k_j+1}}{(k_j+1)!} \leqslant e^L\sum_{j=1}^t\frac{L^{b+2j-1}}{(b+2j-1)!}. \end{equation*} \notag$

Now we estimate $R+R'$ . If an integer $d$ corresponds to a summand in $R$ , then $d=d_1 \dotsb d_t$ , where $d_j \mid {P}_j$ and $\omega(d_j) \leqslant k_j=b+2(j-1)$ . Therefore,

$\begin{equation*} d \leqslant z_1^{k_1} \dotsb z_t^{k_t} \leqslant z^{b+(b+2)/2+(b+4)/4+\dotsb}=z^{2b+4}. \end{equation*} \notag$

If a number

$d$ corresponds to a summand in

$R'$ , then we find similarly that

${d\leqslant z^{2b+4} z = z^{2b+5}}$ . Since the numbers

$d$ corresponding to the sums

$R$ and

$R'$ are distinct and do not exceed

$z^{2b+5}$ , we see that

$\begin{equation*} R+R' \leqslant \sum_{d \leqslant z^{2b+5}} |r_d|. \end{equation*} \notag$

Now we take

$b=4$ . Then

$2b+5=13$ ,

$\begin{equation*} E\leqslant 5\sum_{j=1}^{\infty}\frac{(\log 5)^{2j+3}}{(2j+3)!} \leqslant 0.48 \end{equation*} \notag$

and

$\begin{equation*} R+R' \leqslant \sum_{d \leqslant x^{13/40}} |R(x;ad,1)|. \end{equation*} \notag$

The claim follows.

$\begin{equation*} \mathcal{M}=\bigl\{ a \geqslant 1\colon a \mid n^2 + 1 \text{ for some } n \geqslant 1 \bigr\}. \end{equation*} \notag$

Lemma 3.4. Let $2\leqslant a, z\leqslant x^{1/30}$ , $a \in \mathcal{M}$ and $P^{+}(a)\leqslant z$ . Let

$\begin{equation*} W_a(x,z)=\# \biggl\{ n \leqslant x\colon a\mid (n^2 + 1) \textit{ and } P^-\biggl(\frac{n^2+1}{a}\biggr) > z \biggr\}. \end{equation*} \notag$

Then

$\begin{equation*} W_a(x,z) \asymp \frac{2^{\omega(a)}}{\varphi(a)}\,\frac{x}{\log z} . \end{equation*} \notag$

Proof. Setting

$\mathcal{A}=\{k\colon ak=n^2+1 \text{ for some } n\leqslant x\}$ and

$\begin{equation*} \mathcal{P}= \begin{cases} \{p \leqslant z\colon p\equiv 1\ (\operatorname{mod}4)\} &\text{if $a$ is even}, \\ \{2\}\cup \{p \leqslant z\colon p\equiv 1\ (\operatorname{mod}4)\} &\text{if $a$ is odd}. \end{cases} \end{equation*} \notag$

We have

$W_a(x,z) = S(\mathcal{A}, \mathcal{P})$ . As before, we write each

$d$ dividing

$P=\prod_{p\in\mathcal{P}}p$ as

$d=d_1d_2$ , where

$(d_1,a)=1$ and

$d_2$ consists only of primes dividing

$a$ . Suppose that one of the integers

$d$ and

$a$ is even. Then by the Chinese remainder theorem and the fact that the congruence

$x^2+1\equiv0\ (\operatorname{mod}p)$ has two solutions for

$p\equiv 1\ (\operatorname{mod}4)$ and one solution for

$p=2$ , we obtain

$\begin{equation*} \begin{aligned} \, \mathcal{A}_d &=\#\{n\leqslant x\colon n^2+1 \equiv 0 \ (\operatorname{mod}ad) \} \\ &= \frac{x2^{\omega(ad)-1}}{ad}+O(2^{\omega(ad)}) =\frac{x2^{\omega(a)+\omega(d_1)-1}}{ad_1d_2}+O(2^{\omega(ad)}). \end{aligned} \end{equation*} \notag$

If both

$a$ and

$d$ are odd, then a similar argument shows that

$\begin{equation*} \mathcal{A}_d= \frac{x2^{\omega(a)+\omega(d_1)}}{ad_1d_2}+O(2^{\omega(ad)}). \end{equation*} \notag$

In both cases we have

$\begin{equation*} \mathcal{A}_d=\frac{x2^{\omega(a)+\omega(d_1)-\mathbb I(2\mid ad)}}{ad_1d_2}+O(2^{\omega(ad)}) =\frac{x2^{\omega(a)-\mathbb I(2\mid a)}}{a}\frac{2^{\omega(d_1)-\mathbb I(2\mid d_1)}}{d_1d_2}+O(\tau(ad)), \end{equation*} \notag$

where

$\mathbb I(2\mid l)$ is equal to one if

$l$ is even and to zero otherwise. Thus we see that condition (2.1) holds for

$X= (x2^{\omega(a)-\mathbb I(2\mid a)})/a$ , the multiplicative function

$g$ defined on the prime numbers in

$\mathcal{P}$ by

$\begin{equation*} g(p)=\begin{cases} \dfrac{2}{p} &\text{if } p\nmid a, \\ \dfrac{1}{p} &\text{if } p\mid a \end{cases} \end{equation*} \notag$

(and also

$g(2)=1/2$ in the case of odd

$a$ ), and

$\begin{equation*} r_d=O(\tau(ad)). \end{equation*} \notag$

It is well known that

$\begin{equation} \prod _{\substack{p\leqslant x \\ p\equiv 1\, (\operatorname{mod}4)}}\biggl(1-\frac{1}{p} \biggr)\asymp \frac{1}{\sqrt{\log x}} \end{equation} \tag{3.3}$

(see [11]). Thus, in both cases in the definition of

$\mathcal{P}$ we have

$\begin{equation*} \prod_{p \in \mathcal{P}}(1-g(p))\asymp \prod_{p\in \mathcal{P}, \, p>2}\biggl(1-\frac2p\biggr) \prod_{p\mid a,\,p>2}\frac{1-1/p}{1-2/p} \asymp \frac{a}{\varphi(a)\log z} \end{equation*} \notag$

for an absolute implied constant.

Now we choose a partition of $\mathcal{P}$ and define the numbers $\{k_j\}_{j=1}^t$ . Again, we set $z_j= z^{2^{1-j }}$ and

$\begin{equation*} \mathcal{P}_j=\mathcal{P} \cap (z_{j+1}, z_j], \end{equation*} \notag$

where

$t$ is the unique positive integer such that

$z_{t+1} < 2 \leqslant z_t$ and

$k_j = b + 2(j-1)$ for some even

$b \geqslant 2$ . Now (3.2) implies that

$\begin{equation*} \begin{aligned} \, V_j^{-1} &=\prod_{z_{j+1} < p \leqslant z_j} (1 - g(p))^{-1} \leqslant 2\prod_{z_{j+1}<p\leqslant z_j, \, p\neq2}\biggl(1-\frac2p\biggr)^{-1} \\ &=2\prod_{z_{j+1}<p\leqslant z_j, \, p\neq2}\biggl(1-\frac1p\biggr)^{-2}\frac{(1-1/p)^2}{1-2/p} \leqslant 18C\leqslant 28. \end{aligned} \end{equation*} \notag$

Therefore,

$L_j = \log V_j^{-1}\leqslant L=\log 28$ and

$\begin{equation*} E=\sum_{j=1}^t \frac{e^{L_j} L_j^{k_j+1}}{(k_j+1)!} \leqslant e^L\sum_{j=1}^t\frac{L^{b+2j-1}}{(b+2j-1)!}. \end{equation*} \notag$

Now we take

$b=10$ ; then

$E\leqslant 0.43$ and

$2b+5=25$ . As in the proof of Lemma 3.2, we obtain

$\begin{equation*} R+R' \leqslant \sum_{d \leqslant z^{2b+5}} |r_d|\ll \tau(a)\sum_{d\leqslant z^{25}}\tau(d)\ll x^{1/30}z^{25} \ll x^{26/30}, \end{equation*} \notag$

and the main term is at least

$\begin{equation*} X\prod_{p\in \mathcal{P}}(1-g(p)) \asymp\frac{x2^{\omega(a)}}{\varphi(a)\log z} \gg\frac{x^{1-1/30}}{\log x}. \end{equation*} \notag$

An application of Theorem 3.1 completes the proof.

Lemma 3.5. Let $R>0$ be fixed. Then there exist positive constants $A=A(R)$ and $B=B(R)$ such that, for all $1\leqslant k \leqslant R\log\log x$ ,

$\begin{equation*} \#\bigl\{n\leqslant x\colon \omega(n^2+1)=k\bigr\} \leqslant \frac{Ax(\log\log x+B)^{k-1}}{(k-1)!\, \log x}. \end{equation*} \notag$

Proof. For

$m\geqslant 2$ and

$y\geqslant2$ we define the ‘

$y$ -smooth part’ of

$m$ by

$\begin{equation*} d(m,y)=\max\bigl\{d\mid m\colon P^+(d)\leqslant y\bigr \}. \end{equation*} \notag$

For each

$n\leqslant x$ the number

$n^2+1$ can be written as the product

$ab$ , where

$\begin{equation*} a=a(n)=\max\bigl\{d(n^2+1,y)\colon d(n^2+1,y)\leqslant x^{1/30} \bigr\} \end{equation*} \notag$

and

$b=b(n)=(n^2+1)/a$ ; note that

$(a,b)=1$ . Now we set

$\begin{equation*} \begin{gathered} \, A_1 =\bigl\{ n\leqslant x\colon a\leqslant x^{1/60},\, P^-(b)>x^{1/60},\, b>1\bigr\}, \\ A_2 =\bigl\{ n\leqslant x\colon a\leqslant x^{1/60},\, P^-(b)\leqslant x^{1/60},\, b>1\bigr\} \end{gathered} \end{equation*} \notag$

and

$\begin{equation*} A_3 =\bigl\{ n\leqslant x\colon x^{1/60}< a \leqslant x^{1/30},\, b>1 \bigr\}. \end{equation*} \notag$

Since the number of integers

$n\leqslant x$ for which

$b(n)=1$ does not exceed

$x^{1/60}$ , we conclude that

$\begin{equation} \#\bigl\{n\leqslant x\colon \omega(n^2+1)=k\bigr\}=N_1+N_2+N_3+O(x^{1/60}), \end{equation} \tag{3.4}$

where

$\begin{equation*} N_i=\#\bigl\{n\in A_i\colon \omega(n^2+1)=k \bigr\}, \qquad i=1, 2, 3. \end{equation*} \notag$

First we estimate $N_1$ . In this case $1\leqslant \omega(b)\leqslant 120$ ; by Lemma 3.4 we have

$\begin{equation} \begin{aligned} \, \notag N_1 &\leqslant \sum_{l=k-120}^{k-1}\sum_{\substack{a\leqslant x^{1/60}, \, a\in \mathcal{M} \\ \omega(a)=l }} W_a(x, x^{1/60}) \ll \sum_{l=k-120}^{k-1}\sum_{\substack{a\leqslant x^{1/60}, \, a\in \mathcal{M} \\ \omega(a)=l }}\frac{x2^{\omega(a)}}{\varphi(a)\log x} \\ &\leqslant \frac{x}{\log x}\sum_{l=k-120}^{k-1}2^l\sum_{\substack{a\leqslant x^{1/60}, \, a\in \mathcal{M} \\ \omega(a)=l }}\frac{1}{\varphi(a)}. \end{aligned} \end{equation} \tag{3.5}$

Taking the logarithm of both sides of (3.3) we obtain

$\begin{equation*} \sum _{\substack{p\leqslant x \\ p\equiv 1\, (\operatorname{mod}4)}}\frac{1}{p}= \frac{1}{2}\log\log x+O(1). \end{equation*} \notag$

Hence for each

$l\geqslant 0$ the inner sum in (3.5) is at most

$\begin{equation*} \frac{1}{l!}\biggl(\,\sum_{p\leqslant x^{1/60},\, p\neq 3\, (\operatorname{mod}4)}\frac{1}{\varphi(p)}+\frac{1}{\varphi(p^2)}+\dotsb \biggr)^l \leqslant \frac{1}{l!}\biggl(\frac{1}{2}\log\log x+B_1\biggr)^l \end{equation*} \notag$

for some absolute positive constant

$B_1$ . Thus,

$\begin{equation} N_1\ll \frac{x(\log\log x+B_1)^{k-1}}{(k-1)!\,\log x}\bigl(1+R+\dots+R^{120} \bigr). \end{equation} \tag{3.6}$

Now we estimate $N_2$ . Let $p=P^-(b)$ , and let $r$ be the largest integer such that $p^r\mid b$ . Then by the definition of $a$ , we have $ap^r>x^{1/30}$ . Thus, for any $n\in A_2$ we have $p^r> x^{1/60}$ , and since $p\leqslant x^{1/60}$ , we see that $r\geqslant 2$ . Let $\nu = \min\{{u\geqslant 1}$ : ${p^u>x^{1/60}}\}$ . Then $2\leqslant \nu\leqslant r$ and $p^{\nu-1}\leqslant x^{1/60}$ . Hence ${p^\nu\leqslant x^{1/60}p\leqslant x^{1/30}}$ . We conclude that for each $n\in A_2$ the integer $n^2+1$ is divisible by $p^\nu$ , where $p$ is a prime number such that $x^{1/60}<p^\nu\leqslant x^{1/30}$ and $\nu\geqslant 2$ . Therefore,

$\begin{equation*} N_2\leqslant\sum_{x^{1/60}<p^\nu\leqslant x^{1/30},\,\nu\geqslant 2}\biggl( \frac{2x}{p^\nu}+O(1)\biggr)\ll \sum_{x^{1/60}<p^\nu \leqslant x^{1/30},\,\nu\geqslant 2}\frac{x}{p^\nu}. \end{equation*} \notag$

Note that

$p^{\nu} \geqslant \max\{p^2, x^{1/60}\}$ , and therefore

$p^{\nu}\geqslant px^{1/120}$ . It follows that

$\begin{equation} N_2\ll \sum_{p\leqslant x^{1/30}}\frac{x}{px^{1/120}} \ll x^{1-1/120}\log\log x. \end{equation} \tag{3.7}$

Finally, consider $N_3$ . Setting $q=P^+(a)$ , we have $P^-(b)\geqslant q+1$ and

$\begin{equation} \omega(b)\leqslant \frac{\log (x^2+1)}{\log (q+1)}\leqslant \frac{2\log x}{\log q}=:\eta. \end{equation} \tag{3.8}$

Lemma 3.4 implies that

$\begin{equation} \begin{aligned} \, N_3 &\leqslant \sum_{\substack{q\leqslant x^{1/30} \\ q\not{\equiv} 3\, (\operatorname{mod}4)}}\sum_{k-\eta\leqslant l\leqslant k-1}\sum_{\substack{x^{1/60}<a\leqslant x^{1/30} \\ P^+(a)=q, \, \omega(a)=l}}W_a(x,q) \nonumber \\ &\ll x\sum_{\substack{q\leqslant x^{1/30} \\ q\not{\equiv} 3\, (\operatorname{mod}4)}}\frac{1}{\log q}\sum_{k-\eta\leqslant l\leqslant k-1}2^l\sum_{\substack{x^{1/60}<a\leqslant x^{1/30} \\ P^+(a)=q, \, \omega(a)=l}}\frac{1}{\varphi(a)}. \end{aligned} \end{equation} \tag{3.9}$

Let

$\begin{equation} \delta=\frac{C}{\log q}, \quad\text{where } C=120\log(R+2)+60. \end{equation} \tag{3.10}$

Let us denote by

$N_3^{(1)}$ and

$N_3^{(2)}$ the contributions from

$q\leqslant e^{2C}$ and

$q>e^{2C}$ , respectively. Since

$\begin{equation*} \varphi(a)\gg\frac{a}{\log\log a}\gg\frac{x^{1/60}}{\log\log x}, \end{equation*} \notag$

we have

$\begin{equation} N_3^{(1)}\ll x^{59/60}\log\log x\sum_{q\leqslant e^{2C}}\sum_{1\leqslant l\leqslant \pi(q)}2^l\sum_{\substack{a\leqslant x^{1/30} \\ P^+(a)=q}}1 \ll x^{59/60}(\log x)^{c_R}, \end{equation} \tag{3.11}$

where

$c_R>0$ depends only on

$R$ . Now we turn to

$N_3^{(2)}$ . For fixed

$q$ and

$l$ we see that

$\begin{equation*} \begin{aligned} \, S_{q,l} &:=\sum_{\substack{x^{1/60}<a\leqslant x^{1/30} \\ P^+(a)=q, \, \omega(a)=l}}\frac{1}{\varphi(a)} \leqslant \sum_{\substack{a\leqslant x^{1/30} \\ P^+(a)=q, \, \omega(a)=l}}\biggl(\frac{a}{x^{1/60}}\biggr)^{\delta}\frac{1}{\varphi(a)} \\ &\leqslant x^{-\delta/60}\frac{1}{(l-1)!}\biggl(\sum_{\substack{p<q \\ p\not{\equiv} 3\, (\operatorname{mod}4)}}\frac{p^{\delta}}{\varphi(p)} +\frac{p^{2\delta}}{\varphi(p^2)}+\dotsb \biggr)^{l-1}\biggl(\frac{q^{\delta}}{\varphi(q)} +\frac{q^{2\delta}}{\varphi(q^2)}+\dotsb\biggr). \end{aligned} \end{equation*} \notag$

Note that

$\begin{equation*} \frac{q^{\delta}}{\varphi(q)}+\frac{q^{2\delta}}{\varphi(q^2)}+\dotsb \ll_R \frac1q \quad\text{for } q>e^{2C}, \end{equation*} \notag$

and the sum over the primes

$p$ is (since

$e^u\leqslant 1+O_K(u)$ for

$0\leqslant u\leqslant K$ ) equal to

$\begin{equation*} \begin{aligned} \, &\sum_{\substack{p<q \\ p\not{\equiv} 3\, (\operatorname{mod}4)}}\frac{p^\delta}{p}+O_R(1) \\ &\qquad=\sum_{\substack{p<q \\ p\not{\equiv} 3\, (\operatorname{mod}4)}}\frac{1}{p}+ O_R\biggl(\delta\sum_{\substack{p<q \\ p\not{\equiv} 3\, (\operatorname{mod}4)}}\frac{\log p}{p}+1\biggr)\leqslant \frac{1}{2}\log\log x+B, \end{aligned} \end{equation*} \notag$

where

$B=B(R)>0$ . Thus,

$\begin{equation*} S_{q,l}\ll_R \frac{x^{-\delta/60}}{q(l-1)!}\biggl(\frac{1}{2}\log\log x+B\biggr)^{l-1} \end{equation*} \notag$

and

$\begin{equation} \begin{aligned} \, N_3^{(2)} &\ll_R x\sum_{\substack{e^{2C}<q\leqslant x^{1/30} \\ q\not\equiv 3\, (\operatorname{mod}4)}}\frac{x^{-\delta/60}}{q\log q}\sum_{k-\eta\leqslant l\leqslant k-1}\frac{2^l(1/2\log\log x+B)^{l-1}}{(l-1)!}\notag \\ &\ll \frac{x(\log\log x+2B)^{k-1}}{(k-1)!}\sum_{q\leqslant x^{1/30}}\frac{x^{-\delta/60}}{q\log q}(1+R+\dots +R^{[\eta]}). \end{aligned} \end{equation} \tag{3.12}$

Using the inequality

$\begin{equation*} 1+R+\dots+R^{[\eta]}\leqslant (R+2)^{\eta+1} \end{equation*} \notag$

and the fact that

$\begin{equation*} (R+2)^\eta x^{-\delta/60}=x^{-1/\log q} \end{equation*} \notag$

(which follows from the definitions (3.8) and (3.10) of

$\eta$ and

$\delta$ , respectively), we see that the sum over primes

$q$ in (3.12) is at most

$\begin{equation*} \begin{aligned} \, &(R+2) \sum_{q\leqslant x^{1/30}}\frac{(R+2)^{\eta}x^{-\delta/60}}{q\log q} \leqslant (R+2)\sum_{q\leqslant x^{1/2}}\frac{x^{-1/\log q}}{q\log q} \\ &\qquad\leqslant \frac{R+2}{\log x}\sum_{j\geqslant 1}\sum_{q\in (x^{2^{-(j+1)}}, \,x^{-2^j}]}\frac1q \,2^{j+1}\exp(-2^j) \ll_R \frac{1}{\log x}\,. \end{aligned} \end{equation*} \notag$

Substituting this into (3.12) and taking (3.11) into account we find that

$\begin{equation} N_3 \ll_R \frac{x(\log\log x+2B)^{k-1}}{(k-1)!\,\log x}. \end{equation} \tag{3.13}$

Combining (3.4), (3.6), (3.7) and (3.13) we complete the proof.

$\begin{equation*} \Phi(x)=\sum_{\substack{a \leqslant x \\ P^+(a) \leqslant x^{1/40}}} \frac{1}{\tau(a)} \sum_{\substack{b \leqslant (x-1)/a \\ P^-(b) > x^{{1}/{40}} \\ ab +1\text{ is prime}}} \frac{1}{\tau(b)}. \end{equation*} \notag$

$\begin{equation*} x^{ (\alpha_1 + \alpha_2 + \dots + \alpha_s)/40} < b \leqslant x, \end{equation*} \notag$

$\begin{equation*} \tau(b)=(\alpha_1+1) \dotsb (\alpha_s+1) \leqslant 2^{\alpha_1+\dots+\alpha_s} < 2^{40}. \end{equation*} \notag$

$\begin{equation*} \Phi(x) \geqslant 2^{-40} \sum_{\substack{a \leqslant x \\ P^+(a) \leqslant x^{1/40}}} \frac{1}{\tau(a)} \sum_{\substack{b \leqslant (x-1)/a \\ P^-(b) > x^{1/40} \\ ab +1\text{ is prime}}} 1 \geqslant 2^{-40} \sum_{\substack{a \leqslant x^{1/40} \\ a \text{ is even}}} \frac{1}{\tau(a)}F_a(x) . \end{equation*} \notag$

$\begin{equation*} \Phi(x) \geqslant \frac{c_2 \pi(x)}{\log x}\sum_{\substack{a \leqslant x^{1/40} \\ a \text{ is even}}} \frac{1}{\tau(a)\varphi(a)}-R_2, \end{equation*} \notag$

$\begin{equation*} 0\leqslant R_2 \leqslant \sum_{a\leqslant x^{1/40}}\sum_{d\leqslant x^{13/40}}|R(x;ad,1)| \leqslant \sum_{q\leqslant x^{7/20}}\tau(q)|R(x;q,1)|. \end{equation*} \notag$

$\begin{equation*} \begin{aligned} \, R_2 &\ll x^{1/2} \sum_{q \leqslant x^{0.35}} \frac{\tau(q)}{q^{1/2}} (|R(x; q, 1)|)^{1/2} \\ &\leqslant x^{1/2} \biggl(\sum_{q \leqslant x^{0.35}} \frac{\tau^2(q)}{q}\biggr)^{1/2} \biggl(\sum_{q \leqslant x^{0.35}} |R(x; q, 1)|\biggr)^{1/2}. \end{aligned} \end{equation*} \notag$

$\begin{equation*} \sum_{n\leqslant x}\frac{\tau^2(n)}{n} \asymp (\log x)^4, \end{equation*} \notag$

$\begin{equation*} R_2 \ll_A x^{1/2}(\log x)^2 \frac{x^{1/2}}{(\log x)^{A/2}}= \frac{x}{(\log x)^{A/2-2}}. \end{equation*} \notag$

$\begin{equation*} R_2 \ll \frac{x}{(\log x)^{10}}. \end{equation*} \notag$

$\begin{equation*} T_1=\sum_{\substack{a \leqslant x^{1/40} \\ a \text{ is even}}} \frac{1}{\tau(a) \varphi(a)}=\sum_{l \leqslant 0.5x^{1/40}} \frac{1}{\tau(2l)\varphi(2l)}. \end{equation*} \notag$

$\begin{equation*} T_1\gg \sum_{l \leqslant 0.5x^{1/40}} \frac{1}{\tau(l)l}. \end{equation*} \notag$

$\begin{equation*} T_1\gg (\log x)^{1/2}. \end{equation*} \notag$

$\begin{equation*} \Phi(x)\gg \frac{\pi(x)}{(\log x)^{1/2}}-O\biggl( \frac{x}{(\log x)^{10}}\biggr)\gg \frac{x}{(\log x)^{3/2}}. \end{equation*} \notag$

$\begin{equation*} F(x)=\sum_{n \leqslant x} \frac{1}{\tau(n^2+1)}=\sum_{\substack{ab=n^2 + 1,\,n \leqslant x\\ P^+(a) \leqslant z,\, P^-(b) > z}} \frac{1}{\tau(ab)}. \end{equation*} \notag$

$\begin{equation*} \begin{aligned} \, F(x) &\geqslant 2^{-60} \sum_{\substack{a \leqslant x^{1/30} \\ a \in \mathcal{M}}} \frac{1}{\tau(a)} W_a(x, x^{1/30})\gg \frac{x}{\log x} \sum_{\substack{a \leqslant x^{1/30} \\ a \in \mathcal{M}}} \frac{2^{\omega(a)}}{\tau(a)\varphi(a)} \\ &\geqslant \frac{x}{\log x}\sum_{\substack{a \leqslant x^{1/30} \\ a \in \mathcal{M} \\ a\text{ is square-free}}}\frac{1}{a}= \frac{x}{\log x}\sum_{\substack{a \leqslant x^{1/30} \\ a \in \mathcal{M}}} \frac{1}{a}\,\sum_{\delta^2\mid a}\mu(\delta). \end{aligned} \end{equation*} \notag$

$\begin{equation*} \sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}, \end{equation*} \notag$

$\begin{equation} F(x)\gg \frac{x}{\log x}\sum_{\substack{\delta \leqslant x^{1/60} \\ \delta \in \mathcal{M}}} \frac{\mu(\delta)}{\delta^2} \sum_{\substack{a \leqslant x^{1/30}\delta^{-2} \\ a \in \mathcal{M} }} \frac{1}{a} \geqslant \biggl( 2-\frac{\pi^2}{6}\biggr)\frac{x}{\log x}\sum_{\substack{a \leqslant x^{1/30} \\ a \in \mathcal{M}}} \frac{1}{a}. \end{equation} \tag{5.1}$

$\begin{equation*} \# \{a\leqslant y\colon p\mid a \ \Rightarrow\ p\equiv 1\ (\operatorname{mod} 4)\} \asymp \frac{y}{(\log y)^{1/2}}. \end{equation*} \notag$

$\begin{equation*} \sum_{\substack{a\leqslant y \\ p\mid a \ \Rightarrow\ p\equiv 1\, (\operatorname{mod} 4) }}\frac{1}{a}\asymp (\log y)^{1/2}. \end{equation*} \notag$

$\begin{equation*} F(x)\gg \frac{x}{(\log x)^{1/2}}, \end{equation*} \notag$

$\begin{equation*} \begin{aligned} \, F(x)&\leqslant \sum_{n\leqslant x}\frac{1}{2^{\omega(n^2+1)}} \\ &=\sum_{k\leqslant 2\log\log x}\frac{\#\{n\leqslant x\colon \omega(n^2+1)=k\}}{2^k} + O\biggl(\sum_{k>2\log\log x}\frac{x}{2^k}\biggr) \\ &\ll \frac{x}{\log x}\sum_{k=1}^{+\infty}\frac{((1/2)\log\log x+(1/2)B)^{k-1}}{(k-1)!} + O\biggl(\frac{x}{\log x}\biggr)\ll \frac{x}{(\log x)^{1/2}}. \end{aligned} \end{equation*} \notag$

\Bibitem{GabKonIud23}

\by M.~R.~Gabdullin, S.~V.~Konyagin, V.~V.~Iudelevich

\paper Karatsuba's divisor problem and related questions

\jour Sb. Math.

\yr 2023

\vol 214

\issue 7

\pages 919--933

\mathnet{http://mi.mathnet.ru/eng/sm9815}

\crossref{https://doi.org/10.4213/sm9815e}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4681472}

\zmath{https://zbmath.org/?q=an:1534.11114}

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2023SbMat.214..919G}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001146029300002}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85180429388}

§ 1. Introduction

§ 2. Notation

§ 3. Auxiliary results

§ 4. Proof of Theorem 1.1

§ 5. Proof of Theorem 1.2

Bibliography