# The number of prime factors of integers with dense divisors

Andreas Weingartner  Department of Mathematics, 351 West University Boulevard,
Southern Utah University, Cedar City, Utah 84720, USA<EMAIL_ADDRESS>
(Date: November 11, 2021)

###### Abstract.

We show that for integers $n$, whose ratios of consecutive divisors are
bounded above by an arbitrary constant, the normal order of the number of
prime factors is $C\log\log n$, where $C=(1-e^{-\gamma})^{-1}=2.280...$ and
$\gamma$ is Euler’s constant. We explore several applications and resolve a
conjecture of Margenstern about practical numbers.

###### 2010 Mathematics Subject Classification:

11N25, 11N37

##  1\. Introduction

We say that a positive integer $n$ is $t$-dense if the ratios of consecutive
divisors of $n$ do not exceed $t$. Let $\mathcal{D}(x,t)$ denote the set of
$t$-dense integers $n\leq x$ and write $D(x,t)=|\mathcal{D}(x,t)|$. Let
$\omega(n)$ (resp. $\Omega(n)$) be the number of prime factors of $n$, counted
without (resp. with) multiplicity.

Theorem 1 gives the average and normal order of $\omega(n)$ and $\Omega(n)$
for the $t$-dense integers. We write $\log_{2}x$ for $\log\log x$ and define
$E(x,t)$, the approximate expected value of $\omega(n)$ on $\mathcal{D}(x,t)$,
by

$E(x,t):=C\log_{2}x-(C-1)\log_{2}t,\quad C:=(1-e^{-\gamma})^{-1}=2.280291...$

######  Theorem 1.

Let $\xi(x)\to\infty$. Uniformly for $x\geq t\geq 2$,

$\frac{\sum_{n\in\mathcal{D}(x,t)}\omega(n)}{D(x,t)}=E(x,t)+O\left(1\right)$
(1)

and

$\Bigl{|}\left\\{n\in\mathcal{D}(x,t):|\omega(n)-E(x,t)|>\xi(x)\sqrt{\log_{2}x}\right\\}\Bigr{|}\ll\frac{D(x,t)}{\xi(x)^{2}}.$
(2)

These results also hold with $\Omega$ in place of $\omega$.

Note that $\log_{2}x\leq E(x,t)\leq C\log_{2}x+O(1)$, as $x\geq t\geq 2$. If
$t=x$, then $E(x,t)=\log_{2}x$ and $\mathcal{D}(x,t)=[1,x]\cap\mathbb{N},$ so
Theorem 1 contains the well-known results about the average and normal order
of $\omega(n)$ on $\mathbb{N}$. If $t\geq 2$ is constant, then
$E(x,t)=C\log_{2}x+O(1)$, so that the average and normal order of $\omega(n)$
for $t$-dense integers $n$ is $C\log_{2}n$.

The $t$-dense integers are a special case of a family of integer sequences
that arise as follows. Let $\theta$ be an arithmetic function. Let
$\mathcal{B}=\mathcal{B}_{\theta}$ be the set of positive integers containing
$n=1$ and all those $n\geq 2$ with prime factorization
$n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$, $p_{1}<p_{2}<\ldots<p_{k}$,
which satisfy

$p_{i}\leq\theta\big{(}p_{1}^{\alpha_{1}}\cdots
p_{i-1}^{\alpha_{i-1}}\big{)}\qquad(1\leq i\leq k).$ (3)

We write $\mathcal{B}(x)=\mathcal{B}\cap[1,x]$ and $B(x)=|\mathcal{B}(x)|$.
When $\theta(n)=nt$, then $\mathcal{B}$ is the set of $t$-dense integers [6,
10, 14]. If $\theta(n)=\sigma(n)+1$, where $\sigma(n)$ is the sum of the
positive divisors of $n$, then $\mathcal{B}$ is the set of practical numbers
[2, 6, 7, 8, 9, 10, 14], i.e. integers $n$ such that every $m\leq n$ can be
expressed as a sum of distinct positive divisors of $n$.

We will derive Corollaries 1 through 3 from Theorem 1 in Section 2.

######  Corollary 1.

Assume $\theta$ satisfies $\max(2,n)\leq\theta(n)\leq nf(n)$, where $f$ is
non-decreasing. Let $\xi(x)\to\infty$. We have

$\frac{\sum_{n\in\mathcal{B}(x)}\omega(n)}{B(x)}=C\log_{2}x\left\\{1+O\left(\left(\frac{\log
f(x)}{\log_{2}x}\right)^{1/3}\right)\right\\}$ (4)

and

$\Bigl{|}\bigl{\\{}n\in\mathcal{B}(x):|\omega(n)-C\log_{2}x|>\xi(x)\sqrt{\log_{2}x}\bigr{\\}}\Bigr{|}\ll
B(x)\frac{\log f(x)}{\xi(x)^{2}}.$ (5)

These results also hold with $\Omega$ in place of $\omega$.

Conjecture 5 of Margenstern [2] proposes that, for practical numbers,
$\sum_{n\in\mathcal{B}(x)}\omega(n)\sim\mu x/(\log x)^{\eta}$, for some
constants $\mu>0$ and $1/2<\eta<1$. The estimate (4) disproves this
conjecture, since $B(x)\sim c_{\theta}x/\log x$ by [14, Thm. 1.2], if
$\max(2,n)\leq\theta(n)\ll n(\log 2n)/(\log_{2}3n)^{1+\varepsilon}$ for $n\geq
1$.

Corollary 2 shows that almost all large practical numbers $n$ have about
$C\log_{2}n$ prime factors.

######  Corollary 2.

If $\theta$ satisfies $\max(2,n)\leq\theta(n)\ll n(\log 2n)^{o(1)}$, then the
average and normal order of $\omega(n)$ on $\mathcal{B}$ is $C\log_{2}n$. That
is, as $x\to\infty$,

$\sum_{n\in\mathcal{B}(x)}\omega(n)\sim\sum_{n\in\mathcal{B}(x)}C\log_{2}n$
(6)

and all but $o(B(x))$ integers $n\in\mathcal{B}(x)$ satisfy

$\omega(n)=(1+o(1))C\log_{2}n.$ (7)

These results also hold with $\Omega$ in place of $\omega$.

Let $\tau(n)$ be the number of positive divisors of $n$.

######  Corollary 3.

If $\theta$ satisfies $\max(2,n)\leq\theta(n)\ll n(\log 2n)^{o(1)}$, then

$(\log x)^{C\log 2-o(1)}<\frac{\sum_{n\in\mathcal{B}(x)}\tau(n)}{B(x)}\ll(\log
x)^{e\log 2},$ (8)

as $x\to\infty$, and all but $o(B(x))$ integers $n\in\mathcal{B}(x)$ satisfy

$\tau(n)=(\log n)^{C\log 2+o(1)}=(\log n)^{1.580577...+o(1)}.$ (9)

Conjecture 4 of Margenstern [2] says that, in the case of practical numbers,
$\sum_{n\in\mathcal{B}(x)}\tau(n)\sim\nu x(\log x)^{\delta}$, for constants
$1/2<\nu,\,\delta<1$. The estimate (8) implies $\delta\in[C\log 2-1,e\log
2-1]=[0.580...,0.884...]$, since $B(x)\asymp x/\log x$. In [17], we prove this
conjecture with $\delta=0.713...$ and some constant $\nu>0$.

The next two corollaries are improvements to the lower bounds of Theorems 1
and 3 of [5]. The proofs of both of these theorems rely on the fact that
almost all $n\in\mathcal{B}$ satisfy $\Omega(n)<(e+\varepsilon)\log_{2}n$.
With Corollary 2, this can be improved to
$\Omega(n)<(C+\varepsilon)\log_{2}n$, under the assumption $\theta(n)\ll
n(\log n)^{o(1)}$. In the lower bound of [5, Thm. 1] for the count of
practical numbers that are also shifted primes, which has an exponent of
$(e+1)\log(e+1)-e\log(e)+1+\varepsilon=3.16470...$, we can replace $e$ by $C$
to get $3.01711...$.

######  Corollary 4.

Fix a nonzero integer $h$ and assume $\theta$ satisfies

$\max(2,n)\leq\theta(n)\ll n(\log 2n)^{o(1)},\quad\theta(mn)\ll
m^{O(1)}\theta(n)\quad(n,m\in\mathbb{N}).$ (10)

We have

$\frac{x}{(\log x)^{3.01712}}\ll_{h}\bigl{|}\\{p\leq x:p\mbox{ prime},\
p-h\in\mathcal{B}\\}\bigr{|}\ll_{h}\frac{x}{(\log x)^{2}},$

where $h$ is not divisible by $\prod_{p\leq\theta(1)}p$ in the lower bound.

Similarly, in the lower bound of [5, Thm. 3] for the count of twin practical
numbers, which has an exponent of $2+4e\log 2+\varepsilon=9.53667...$, we can
replace $e$ by $C$ to get $8.32230...$

######  Corollary 5.

Fix a nonzero integer $h$ and assume $\theta$ satisfies (10). We have

$\frac{x}{(\log x)^{8.32231}}\ll_{h}\bigl{|}\\{n\leq
x:n\in\mathcal{B},n+h\in\mathcal{B}\\}\bigr{|}\ll_{h}\frac{x}{(\log x)^{2}}.$

For the lower bound, assume that (i) $n\in\mathcal{B}$ and $m\leq 3n/|h|$
imply $mn\in\mathcal{B}$, and (ii) if $\theta(1)<3$, then $h\in 2\mathbb{Z}$
if $\theta(2)\geq 3$, and $h\in 4\mathbb{Z}$ if $\theta(2)<3$.

Conditions (i) and (ii) in Corollary 5 are satisfied by the practical numbers
and by the $2$-dense integers for any nonzero even integer $h$, and by the
$t$-dense integers for any nonzero integer $h$, provided $t\geq 3$.

The $\varphi$-practical numbers [4, 12] are integers $n$ such that $x^{n}-1$
has a divisor in $\mathbb{Z}[x]$ of every degree up to $n$. Although not an
example of a set $\mathcal{B}_{\theta}$, they are a superset of
$\mathcal{B}_{\theta_{1}}$ with $\theta_{1}(n)=n+1$, and a subset of
$\mathcal{B}_{\theta_{2}}$ with $\theta_{2}(n)=n+2$. Therefore, Corollaries 1
through 5 also apply to the $\varphi$-practical numbers, provided $h$ is odd
in the lower bound of Corollary 4, while $h$ is even in the lower bound of
Corollary 5.

Theorem 1 is a consequence of Theorems 2 and 3. Theorem 2 gives an estimate
for

$D_{q}(x)=D_{q}(x,t):=|\\{n\in\mathcal{D}(x,t):q|n\\}|,$

when $q$ has a bounded number of prime factors. As in the case $q=1$ (see [14,
Thm. 1.3]), the main term contains the function $d(v)$, which is defined by
$d(v)=0$ for $v<0$ and

$d(v)=1-\int_{0}^{\frac{v-1}{2}}\frac{d(u)}{u+1}\
w\left(\frac{v-u}{u+1}\right)du\qquad(v\geq 0),$ (11)

where $w(u)$ denotes Buchstab’s function.

######  Theorem 2.

Let $k\in\mathbb{N}\cup\\{0\\}$ be fixed. Uniformly for $x\geq 1$, $t\geq 2$,
$q\in\mathbb{N}$ with $\Omega(q)=k$, $v=\log x/\log t$, we have

$\displaystyle D_{q}(x,t)$
$\displaystyle=xd(v)\eta_{q,t}\left\\{1+O_{k}\left(\frac{1}{\log
xt}+\frac{\log 2q\log qt}{\log^{2}xt}\right)\right\\}+O(1),$ (12)
$\displaystyle D_{q}(x,t)$
$\displaystyle=xd(v)\eta_{q,t}\left\\{1+O_{k}\left(\frac{\log 2q}{\log
2x}\right)\right\\},$ (13)

where

$q^{-1}\ll\eta_{q,t}\ll_{k}q^{-1}.$ (14)

######  Corollary 6.

Let $k\in\mathbb{N}\cup\\{0\\}$ be fixed. Uniformly for $x\geq 1$, $t\geq 2$,
$q\in\mathbb{N}$ with $\Omega(q)=k$, we have

$D_{q}(x,t)=\frac{c_{q}x}{\log xt}\left\\{1+O_{k}\left(\frac{1}{\log
xt}+\frac{\log^{2}qt}{\log^{2}xt}\right)\right\\}+O(1),$ (15)

where

$c_{q}=c_{q,t}=C\eta_{q,t}\log t,\quad q^{-1}\log t\ll c_{q}\ll_{k}q^{-1}\log
t,$ (16)

and

$D_{q}(x,t)\ll_{k}\frac{x\log t}{q\log xt}.$ (17)

The estimates (15) and (16) follow from (12) and (14), since
$d(v)=C(v+1)^{-1}\left\\{1+O\left((v+1)^{-2}\right)\right\\}$ by [13, Thm. 1].
The upper bound (17) follows from (13), because $D_{q}(x,t)=0$ if $q>x$.

Theorem 3 gives estimates for $c_{q}$ when $q$ is a prime or a product of two
primes. These estimates are needed to derive Theorem 1 from Theorem 2.

######  Theorem 3.

Let $p\leq q$ be primes. The constant factor in (15) satisfies

$c_{\theta}:=c_{1}=C(\log t-\gamma)+O\left(e^{-\sqrt{\log t}}\right),$ (18)
$qc_{q}=Cc_{\theta}\left\\{1+O\left(\frac{1}{\log
q}+\frac{\log^{2}t}{\log^{2}q}\right)\right\\}$ (19) $qc_{q}=c_{\theta}+C\log
q+O\left(\exp\left(-\sqrt{\log t}\right)\right)\quad(q\leq t),$ (20)
$pqc_{pq}=C^{2}c_{\theta}\left\\{1+O\left(\frac{1}{\log
p}+\frac{\log^{2}t}{\log^{2}p}+\frac{\log^{2}p}{\log^{2}q}\right)\right\\},$
(21) $pqc_{pq}=\left(Cc_{\theta}+C^{2}\log
p\right)\left\\{1+O\left(\frac{1}{\log
q}+\frac{\log^{2}t}{\log^{2}q}+e^{-\sqrt{\log t}}\right)\right\\}\quad(p\leq
t),$ (22) $pqc_{pq}=c_{\theta}+C\log pq+O\left(e^{-\sqrt{\log
t}}\right)\quad(p\leq q\leq t).$ (23)

In Section 2 we derive Corollaries 1, 2 and 3 from Theorem 1. Section 3
contains several lemmas, used in the proofs of Theorems 2 and 3, about members
of $\mathcal{B}$ that are multiples of a natural number $q$. The proof of
Theorem 2 is given in Section 4. In Section 5 we establish Theorem 3 with the
help of Corollary 6, which is a consequence of Theorem 2. Finally, in Section
6 we apply Theorems 2 and 3 to prove Theorem 1.

##  2\. Proof of Corollaries 1, 2 and 3

######  Lemma 1.

We have

$D(x,t)\ll\frac{x\log t}{\log xt}\qquad(x>1/t,t\geq 2),$ $D(x,t)\gg\frac{x\log
t}{\log xt}\qquad(x\geq 1,t\geq 2),$ $D(x/q,t)-D(q/t,t)\leq D_{q}(x,t)\leq
D(x/q,qt)\qquad(x\geq 0,t\geq 2,q\geq 1).$

###### Proof.

The first two estimates follow from [6, Thm. 1].

If $m\in\mathcal{D}(x/q,t)$ and $m>q/t$, then $mq\in\mathcal{D}_{q}(x,t)$.
This shows that $D(x/q,t)-D(q/t,t)\leq D_{q}(x,t)$.

If $n\in\mathcal{D}(x,t)$ and $q|n$, we write $n=qm$ and observe that
$m\in\mathcal{D}(x/q,qt)$. Thus, $D_{q}(x,t)\leq D(x/q,qt)$. ∎

###### Proof of Corollary 1.

We first show (5). For $1\leq n\leq x$, we have $\max(2,n)\leq\theta(n)\leq
nf(n)\leq nf(x)$. Thus, $\mathcal{B}(x)\subset\mathcal{D}(x,f(x))$. If
$f(x)\leq x$, (2) yields

$\left|\left\\{n\in\mathcal{B}(x):|\omega(n)-E(x,f(x))|>\frac{\xi(x)}{2}\sqrt{\log_{2}x}\right\\}\right|\ll\frac{D(x,f(x))}{\xi(x)^{2}}.$

The assumption $\theta(n)\geq\max(2,n)$ implies $B(x)\gg x/\log x$, by [14,
Thm. 1.2]. By Lemma 1,

$\frac{D(x,f(x))}{\xi(x)^{2}}\ll\frac{x\log f(x)}{\xi(x)^{2}\log x}\ll
B(x)\frac{\log f(x)}{\xi(x)^{2}}.$

The result being trivial if $\log f(x)>\xi(x)^{2}$, we may assume $\log
f(x)\leq\xi(x)^{2}$, so that

$|E(x,f(x))-C\log_{2}x|=|(C-1)\log_{2}f(x)|\leq\frac{\xi(x)}{2}\sqrt{\log_{2}x},$

for $x\geq x_{0}$. Thus, (5) holds if $f(x)\leq x$. If $f(x)>x$, then
$\xi(x)^{2}\geq\log f(x)>\log x$, so that
$|\omega(n)-C\log_{2}x|>\xi(x)\sqrt{\log_{2}x}$ implies
$\omega(n)>\xi(x)>\sqrt{\log x}$. The result now follows from Nicolas’ Theorem
[3], an asymptotic estimate for the quantity $|\\{n\leq x:\Omega(n)=k\\}|$,
which easily implies

$|\\{n\leq x:\Omega(n)\geq y\log_{2}x\\}|\ll\frac{x}{(\log x)^{y\log 2-1}},$
(24)

uniformly for $x\geq 2$ and $y\geq 2+\delta$, for any fixed $\delta>0$.

Next, we show that (5) implies (4). From (24) we have

$|\\{n\leq x:\omega(n)\geq 6\log_{2}x\\}|\leq|\\{n\leq x:\Omega(n)\geq
6\log_{2}x\\}|\ll\frac{B(x)}{\log^{2}x}.$ (25)

Since $\omega(n)\leq\Omega(n)\ll\log n$, the contribution to
$\sum_{n\in\mathcal{B}(x)}\omega(n)$ from $n$ with $\omega(n)>6\log_{2}x$ is
$\ll B(x)/\log x$, while the contribution from $n$ with $\omega(n)\leq
6\log_{2}x$ and $|\omega(n)-C\log_{2}x|>\xi(x)\sqrt{\log_{2}x}$ is

$\ll(6\log_{2}x)B(x)\frac{\log f(x)}{\xi(x)^{2}},$

by (5). The contribution to $\sum_{n\in\mathcal{B}(x)}\omega(n)$ from $n$ with
$\omega(n)\leq 6\log_{2}x$ and
$|\omega(n)-C\log_{2}x|\leq\xi(x)\sqrt{\log_{2}x}$ is

$B(x)\left(1+O\left(\frac{\log
f(x)}{\xi(x)^{2}}+\frac{1}{\log^{2}x}\right)\right)C\log_{2}x\left(1+O\left(\frac{\xi(x)}{\sqrt{\log_{2}x}}\right)\right).$

If $\log f(x)\leq\log_{2}x$, (4) now follows with $\xi(x)=(\log
f(x))^{1/3}(\log_{2}x)^{1/6}$. If $\log f(x)>\log_{2}x$, (4) follows directly
from (25). The argument works the same with $\Omega(n)$ in place of
$\omega(n)$. ∎

###### Proof of Corollary 2.

Assume $\max(2,n)\leq\theta(n)\ll n(\log 2n)^{o(1)}$. Define $f(x)=\max_{n\leq
x}\theta(n)/n$, so that $f$ is non-decreasing and $f(x)=(\log x)^{o(1)}$ as
$x\to\infty$, that is $\log f(x)=o(\log_{2}x)$. The relation (6) follows from
(4). Choosing $\xi(x)=(\log f(x)\log_{2}x)^{1/4}$ in (5) yields (7). ∎

######  Lemma 2.

Let $\varepsilon>0$. For $2\leq\alpha\leq 4-\varepsilon$ we have

$\sum_{n\leq x\atop\Omega(n)\geq\alpha\log_{2}x}\tau(n)\ll x(\log
x)^{\alpha(\log 2-\log\alpha+1)-1}.$

###### Proof.

This is a variation of Exercise 05 in [1]. Write
$y^{\Omega(n)}=\sum_{d|n}f(d)$, so that $f(n)$ is multiplicative and
$f(p^{k})=y^{k}(1-1/y)$ for $k\geq 1$, by Möbius inversion. For $0\leq y\leq
2-\varepsilon$,

$\begin{split}\sum_{n\leq x}\tau(n)y^{\Omega(n)}&=\sum_{n\leq
x}\tau(n)\sum_{d|n}f(d)\leq\sum_{d\leq x}f(d)\tau(d)\sum_{m\leq x/d}\tau(m)\\\
&\leq x\log x\sum_{d\leq x}f(d)\tau(d)/d\leq x\log x\sum_{P^{+}(d)\leq
x}f(d)\tau(d)/d\\\ &=x\log x\prod_{p\leq x}\sum_{k\geq
0}f(p^{k})\tau(p^{k})/p^{k}\ll x(\log x)^{2y-1}.\end{split}$

If $1\leq y\leq 2-\varepsilon$, we get

$\sum_{n\leq x\atop\Omega(n)\geq\alpha\log_{2}x}\tau(n)y^{\alpha\log_{2}x}\ll
x(\log x)^{2y-1}.$

The result now follows with $y=\alpha/2$. ∎

###### Proof of Corollary 3.

Since $2^{\omega(n)}\leq\tau(n)\leq 2^{\Omega(n)}$ for all $n\geq 1$, the
estimate (9) and the lower bound in (8) follow at once from (7). For the upper
bound in (8), we write

$\sum_{n\in\mathcal{B}(x)\atop\Omega(n)\leq e\log_{2}x}\tau(n)\leq
B(x)2^{e\log_{2}x}=B(x)(\log x)^{e\log 2}$

and

$\sum_{n\in\mathcal{B}(x)\atop\Omega(n)\geq e\log_{2}x}\tau(n)\leq\sum_{n\leq
x\atop\Omega(n)\geq e\log_{2}x}\tau(n)\ll x(\log x)^{e\log 2-1}\ll B(x)(\log
x)^{e\log 2},$

by Lemma 2 with $\alpha=e$. ∎

##  3\. Multiples of $q$ in $\mathcal{B}$

In this section we develop some general identities for sets $\mathcal{B}$,
defined by (3), with

$\theta:\mathbb{N}\to\mathbb{R}\cup\\{\infty\\},\quad\theta(1)\geq
2,\quad\theta(n)\geq P^{+}(n)\quad(n\geq 2),$ (26)

where $P^{+}(n)$ denotes the largest prime factor of $n$. Let

$\Phi(x,y)=1_{x\geq 1}+|\\{2\leq n\leq x:P^{-}(n)>y\\}|,$

where $P^{-}(n)$ denotes the smallest prime factor of $n$. Let

$\psi(n):=\begin{cases}1&\mbox{if }n\in\mathcal{B}\\\
0&\mbox{else.}\end{cases}$

and define

$\lambda_{n}(s):=\frac{\psi(n)}{n^{s}}\prod_{p\leq\theta(n)}\left(1-\frac{1}{p^{s}}\right),\quad\lambda_{n}:=\lambda_{n}(1),$
$\mu_{n}(s):=\sum_{p\leq\theta(n)}\frac{\log p}{p^{s}-1}-\log
n,\quad\mu_{n}:=\mu_{n}(1).$

######  Lemma 3.

Let $\theta$ satisfy (26) and let $q_{1}\leq q_{2}\leq\ldots\leq q_{k}$ be
primes. For $x\geq 0$,

$\sum_{n\geq 1}\psi(n)\Phi\left(\frac{x}{n},\theta(n)\right)=\lfloor x\rfloor$
(27)

and

$\sum_{n\geq 1\atop q_{1}\cdots
q_{k}|n}\psi(n)\Phi\left(\frac{x}{n},\theta(n)\right)=\sum_{\theta(n)\geq
q_{k}\atop q_{1}\cdots
q_{k-1}|n}\psi(n)\Phi\left(\frac{x}{nq_{k}},\theta(n)\right).$ (28)

###### Proof.

The relation (27) is [15, Lemma 3]. We will show (28). Every $m\in q_{1}\cdots
q_{k}\mathbb{N}$ factors uniquely as $m=nr$ where $n\in\mathcal{B}$ and
$P^{-}(r)>\theta(n)$ if $r>1$. If $q_{1}\nmid n$ then $\theta(n)<q_{1}$. If
$q_{1}|n$, let $j$ be the largest index such that $q_{1}\cdots q_{j}|n$, so
that $q_{j+1}>\theta(n)$ if $j<k$. We count all integer multiples of
$q_{1}\cdots q_{k}$ up to $x$ according to $j$ and $n$:

$\left\lfloor\frac{x}{q_{1}\cdots
q_{k}}\right\rfloor=\sum_{\theta(n)<q_{1}}\psi(n)\Phi\left(\frac{x}{nq_{1}\cdots
q_{k}},\theta(n)\right)\\\ +\sum_{j=1}^{k-1}\sum_{\theta(n)<q_{j+1}\atop
q_{1}\cdots q_{j}|n}\psi(n)\Phi\left(\frac{x}{nq_{j+1}\cdots
q_{k}},\theta(n)\right)+\sum_{q_{1}\cdots
q_{k}|n}\psi(n)\Phi\left(\frac{x}{n},\theta(n)\right).$ (29)

We can now establish (28) by induction on $k$. When $k=1$, (29) and (27) yield
(28). For the inductive step, we write the inner sum of (29) as

$\sum_{\theta(n)<q_{j+1}\atop q_{1}\cdots q_{j}|n}=\sum_{q_{1}\cdots
q_{j}|n}-\sum_{\theta(n)\geq q_{j+1}\atop q_{1}\cdots q_{j}|n}$

and use the inductive hypothesis on the sum $\sum_{q_{1}\cdots q_{j}|n}$ to
get

$\sum_{\theta(n)<q_{j+1}\atop q_{1}\cdots
q_{j}|n}\psi(n)\Phi\left(\frac{x}{nq_{j+1}\cdots
q_{k}},\theta(n)\right)=\sum_{\theta(n)\geq q_{j}\atop q_{1}\cdots
q_{j-1}|n}\psi(n)\Phi\left(\frac{x}{nq_{j}\cdots q_{k}},\theta(n)\right)\\\
-\sum_{\theta(n)\geq q_{j+1}\atop q_{1}\cdots
q_{j}|n}\psi(n)\Phi\left(\frac{x}{nq_{j+1}\cdots q_{k}},\theta(n)\right).$

Thus, the sum over $j$ in (29) is telescoping and the result follows from
(27). ∎

######  Lemma 4.

Let $\theta$ satisfy (26) and let $q_{1}\leq q_{2}\leq\ldots\leq q_{k}$ be
primes. For $\operatorname{Re}(s)>1$ we have

$\sum_{n\geq 1}\lambda_{n}(s)=1$ (30)

and

$\sum_{n\geq 1\atop q_{1}\cdots
q_{k}|n}\lambda_{n}(s)=\frac{1}{q_{k}^{s}}\sum_{\theta(n)\geq q_{k}\atop
q_{1}\cdots q_{k-1}|n}\lambda_{n}(s).$ (31)

Both relations hold at $s=1$ if $B(x)=o(x)$.

###### Proof.

The relation (30) is [16, Lemma 1] when $\operatorname{Re}(s)>1$ and [15,
Theorem 1] when $s=1$. The proof of (31) mirrors that of (28). We first assume
$\operatorname{Re}(s)>1$. Every $m\in q_{1}\cdots q_{k}\mathbb{N}$ factors
uniquely as $m=nr$ where $n\in\mathcal{B}$ and $P^{-}(r)>\theta(n)$ if $r>1$.
If $q_{1}\nmid n$ then $\theta(n)<q_{1}$. If $q_{1}|n$, let $j$ be the largest
index such that $q_{1}\cdots q_{j}|n$, so that $q_{j+1}>\theta(n)$ if $j<k$.
We rearrange the terms of the Dirichlet series $\sum_{q_{1}\cdots
q_{k}|m}m^{-s}$ according to $n$ and $j$. After dividing by $\zeta(s)$, this
shows that, for $\operatorname{Re}(s)>1$,

$\frac{1}{(q_{1}\cdots
q_{k})^{s}}=\sum_{\theta(n)<q_{1}}\frac{\lambda_{n}(s)}{(q_{1}\cdots
q_{k})^{s}}+\sum_{j=1}^{k-1}\sum_{\theta(n)<q_{j+1}\atop q_{1}\cdots
q_{j}|n}\frac{\lambda_{n}(s)}{(q_{j+1}\cdots q_{k})^{s}}+\sum_{q_{1}\cdots
q_{k}|n}\lambda_{n}(s).$ (32)

We establish (31) by induction on $k$. When $k=1$, the result follows from
applying (30) to the first sum of (32). For the inductive step, note that the
inner sum in (32) is

$\begin{split}\sum_{\theta(n)<q_{j+1}\atop q_{1}\cdots
q_{j}|n}\frac{\lambda_{n}(s)}{(q_{j+1}\cdots q_{k})^{s}}&=\sum_{q_{1}\cdots
q_{j}|n}\frac{\lambda_{n}(s)}{(q_{j+1}\cdots q_{k})^{s}}-\sum_{\theta(n)\geq
q_{j+1}\atop q_{1}\cdots q_{j}|n}\frac{\lambda_{n}(s)}{(q_{j+1}\cdots
q_{k})^{s}}\\\ &=\sum_{\theta(n)\geq q_{j}\atop q_{1}\cdots
q_{j-1}|n}\frac{\lambda_{n}(s)}{(q_{j}\cdots q_{k})^{s}}-\sum_{\theta(n)\geq
q_{j+1}\atop q_{1}\cdots q_{j}|n}\frac{\lambda_{n}(s)}{(q_{j+1}\cdots
q_{k})^{s}},\\\ \end{split}$

by the inductive hypothesis. Thus, the sum over $j$ in (32) is a telescoping
sum and the result follows from (30).

If $B(x)=o(x)$, the validity of (31) at $s=1$ follows from (28), in much the
same way that the validity of (30) at $s=1$ follows from (27), which is
demonstrated in the proof of [15, Thm. 1]. ∎

######  Lemma 5.

Let $\theta$ satisfy (26) and let $q_{1}\leq q_{2}\leq\ldots\leq q_{k}$ be
primes. For $\operatorname{Re}(s)>1$ we have

$\sum_{n\geq 1}\lambda_{n}(s)\mu_{n}(s)=0$ (33)

and

$\sum_{n\geq 1\atop q_{1}\cdots
q_{k}|n}\lambda_{n}(s)\mu_{n}(s)=\frac{1}{q_{k}^{s}}\sum_{\theta(n)\geq
q_{k}\atop q_{1}\cdots q_{k-1}|n}\lambda_{n}(s)\bigl{(}\mu_{n}(s)-\log
q_{k}\bigr{)}.$ (34)

###### Proof.

Differentiate (30) and (31) with respect to $s$. ∎

##  4\. Proof of Theorem 2

The following estimate for $\Phi(x,y)$, which differs from the one we used in
[14], simplifies the proof of Theorem 2.

######  Lemma 6.

Uniformly, for $x\geq 0$, $y\geq 2$, we have

$\begin{split}\Phi(x,y)&=1_{x\geq 1}+x\prod_{p\leq
y}\left(1-\frac{1}{p}\right)+\frac{x}{\log
y}\\!\left\\{w(u)-e^{-\gamma}\\!-\left.\frac{y}{x}\right|_{x\geq
y}\\!\\!+O\left(\frac{e^{-u/3}}{\log y}\right)\\!\right\\}\\\ &=1_{x\geq
1}+x\prod_{p\leq y}\left(1-\frac{1}{p}\right)+O\left(\frac{xe^{-u/3}}{\log
y}\right),\end{split}$

where $u=\frac{\log\max(1,x)}{\log y}$ and $w(u)$ is Buchstab’s function.

###### Proof.

The second estimate follows from the first, since $w(u)-e^{-\gamma}\ll e^{-u}$
and, if $x\geq y\geq 2$, then $y/x\ll e^{-u/2}$.

When $x\geq y\geq 2$ and $\log y\geq(\log_{2}x)^{2}$, the first estimate
follows from combining equations (49), (52), (59) and (60) of [11, Sec.
III.6], with equation (6) of [11, Sec. III.5], where we estimate the integral
in (52) as

$\int_{0}^{\infty}|w^{\prime}(u-v)|y^{-v}dv\ll\int_{0}^{\infty}e^{-(u-v)/2}y^{-v}dv=\frac{e^{-u/2}}{\log
y-1/2}\asymp\frac{e^{-u/2}}{\log y}.$

When $x\geq y\geq 2$ and $\log y<(\log_{2}x)^{2}$, then $u\gg\sqrt{\log x}$
and the result follows from [11, Thm. III.6.1 and Thm. III.5.1].

When $x<y$, then $\Phi(x,y)=1_{x\geq 1}$ and $w(u)=0$, so that the result
follows from Mertens’ formula [11, Thm. I.1.11]. ∎

######  Lemma 7.

Assume $B(x)=B_{t}(x)$ is the counting function of a set
$\mathcal{B}_{t}\subset\mathbb{N}$ that depends on the parameter $t$. Assume

$B(x)=x\int_{1}^{\infty}\frac{B(y)}{y^{2}\log
yt}\left(e^{-\gamma}-w\left(\frac{\log x/y}{\log
yt}\right)\right)dy+R(x)\quad(x\geq 1),$

such that the integrals

$\alpha_{t}:=e^{-\gamma}\int_{1}^{\infty}\frac{B(y)}{y^{2}\log
yt}dy,\quad\beta_{t}:=\frac{-1}{\log t}\int_{1}^{\infty}R(y)\frac{dy}{y^{2}}$

converge. Then

$B(x)=x\eta_{t}d(v)+O\Bigl{\\{}1+x\beta_{t}(v+1)^{-3.03}+R(x)+I(x)+J(x)\Bigr{\\}},$

where $v=\log x/\log t$, $d(v)$ is given by (11),
$\eta_{t}=\alpha_{t}+\beta_{t}$,

$I(x)=\frac{x}{\log xt}\int_{x}^{\infty}R(y)\frac{dy}{y^{2}},\quad
J(x)=\frac{x}{(\log xt)^{3.03}}\int_{1}^{x}R(y)(\log
yt)^{2.03}\frac{dy}{y^{2}}.$

###### Proof.

We follow the second half of the proof of [14, Thm. 1.3]. The only
modification needed is the use of the improved estimates

$(v+1)d(v)=C+O((v+1)^{-2.03}),\quad(v\geq 0),$ (35)

and

$(v+1)^{2}d^{\prime}(v)=-C+O((v+1)^{-2.03}),\quad(v\geq 0).$ (36)

The estimate (35) is a consequence of [13, Cor. 6], while (36) follows from
inserting (35) in the proof of [13, Cor. 5]. In [14], we used slightly weaker
estimates for simplicity, with an exponent of $-2$ instead of $-2.03$ in the
error terms. In the proof of Theorem 2, the improved exponent will save a
factor of $\log_{2}x$ (when estimating the contribution from $R_{2}(x)$ to
$J(x)$). ∎

For $n\in\mathbb{N}$ with prime factorization $n=p_{1}\cdots p_{k}$, where
$p_{1}\leq\ldots\leq p_{k}$, define

$F(n):=\max_{1\leq j\leq k}p_{j}^{2}p_{j+1}\cdots p_{k}.$

######  Lemma 8.

If $x<\max(m,F(m)/t)$, then $D_{m}(x,t)=0$.

###### Proof.

Note that $n\in\mathcal{D}_{m}(x,t)$ if and only if $n\leq x$, $m|n$ and
$F(n)\leq nt$. Also, $m|n$ implies $F(m)\leq F(n)$. Thus, if $D_{m}(x,t)\neq
0$ and $n\in\mathcal{D}_{m}(x,t)$, then $m\leq n\leq x$ and $F(m)\leq F(n)\leq
nt\leq xt$, so $x\geq\max(m,F(m)/t)$. ∎

######  Lemma 9.

Let $n\geq 2$ with prime factorization $n=p_{1}\cdots p_{k}$,
$p_{1}\leq\ldots\leq p_{k}$. If $F(n)\leq x$, then $p_{k-j+1}\cdots p_{k}\leq
x^{1-2^{-j}}$ for $1\leq j\leq k$.

###### Proof.

We use induction on $j$. When $j=1$, the claim is that $p_{k}\leq x^{1/2}$,
which follows from $p_{k}^{2}\leq F(n)\leq x$, for all $k\geq 1$. Assume now
that the claim is correct for some $j\in\mathbb{N}$ and all $k\geq j$. Let
$k\geq j+1$. We have $p_{k-j}^{2}p_{k-j+1}\cdots p_{k}\leq F(n)\leq x$. Thus,
if $p_{k-j}p_{k-j+1}\cdots p_{k}\geq x^{1-2^{-j-1}}$, then $p_{k-j}\leq
x^{2^{-j-1}}$. By the inductive hypothesis,

$p_{k-j}(p_{k-j+1}\cdots p_{k})\leq x^{2^{-j-1}}x^{1-2^{-j}}=x^{1-2^{-j-1}},$

for all $k\geq j+1$. ∎

######  Lemma 10.

Let $k\geq 0$ be fixed. For $m\geq 1$ with $\Omega(m)=k$, $t\geq 2$ and
$x\geq\max(m,F(m)/t)$, we have

$\frac{x\log t\log 2m}{m\log xt\log 2x}\gg_{k}1.$

###### Proof.

This is obvious if $m=1$ or if $t\geq x^{2^{-k}}$. If $m\geq 2$ and
$t<x^{2^{-k}}$, then $F(m)\leq xt$ and Lemma 9 imply
$m\leq(xt)^{1-2^{-k}}<x^{1-4^{-k}}\ll_{k}x/(\log xt)^{2}$, from which the
claim follows. ∎

###### Proof of Theorem 2.

In the remainder of this paper, we write $D_{q}(x)$ for $D_{q}(x,t)$ and
$D(x)$ for $D(x,t)$. We will show by induction on $k\geq 0$ that, for
$k=\Omega(q)$, the estimates (12), (13) and (14) hold and that, for primes $r$
with $r\geq P^{+}(q)$, we have

$\sum_{n\in\mathcal{D}_{q}\atop n\geq
r/t}\Phi(x/rn,nt)-\frac{x}{r}\sum_{n\in\mathcal{D}_{q}\atop n\geq
r/t}\lambda_{n}\ll 1+\frac{x\log t\log qr\log
qrt}{qr\log^{3}xt}=:R_{2}(x,qr),$ (37)

for $x\geq\max(qr,F(qr)/t)$. Note that (13) and (35) imply

$D_{q}(x)\ll_{k}xd(v)\eta_{q,t}\asymp_{k}\frac{x\log t}{q\log xt},\quad(x\geq
1,q\geq 1,t\geq 2),$ (38)

since $D_{q}(x)=0$ if $q>x$.

When $k=0$, $q=1$, (12) is [14, Eq. (13)], (13) is [14, Thm. 1.3] and (14) is
[14, Eq. (6)]. To show (37) for $k=0$ and $q=1$, assume that $r$ is prime and
$x\geq\max(r,r^{2}/t)$. Equations (27) and (30) show that

$\begin{split}&\sum_{n\in\mathcal{D}\atop n\geq
r/t}\Phi(x/rn,nt)-\frac{x}{r}\sum_{n\in\mathcal{D}\atop n\geq
r/t}\lambda_{n}\\\ &=-\\{x/r\\}-\sum_{n\in\mathcal{D}\atop
n<r/t}\Phi(x/rn,nt)+\frac{x}{r}\sum_{n\in\mathcal{D}\atop n<r/t}\lambda_{n}\\\
&\ll 1+D(r/t)+\sum_{n\in\mathcal{D}\atop n<r/t}\frac{x}{rn\log
nt}\exp\left(-\frac{\log xt/r}{3\log nt}\right),\end{split}$ (39)

by the second estimate in Lemma 6. We have $D(r/t)\ll r\log t/(t\log r)$ by
Lemma 1, so $D(r/t)\ll R_{2}(x,r)$ follows from

$\frac{r}{\log^{2}r\log
rt}\ll\frac{xt/r}{\log^{3}xt}\asymp\frac{xt/r}{\log^{3}(xt/r)},$

since $xt/r\geq\sqrt{xt}$. This holds because $r\leq xt/r$. Finally, the last
sum in (39) is $\ll R_{2}(x,r)$ by Lemma 1. Thus, (37) holds for $k=0$.

For the inductive step, assume that (13) (and hence (38)) and (14) hold for
$q\in\mathbb{N}$ with $\Omega(q)=k$ for some $k\geq 0$. If $k\geq 1$, assume
that (37) holds for $\Omega(q)=k-1$. Let $r$ be a prime with $r\geq P^{+}(q)$
and write $m=qr$. We note that in the remainder of this proof, all implied
constants in the $\ll$ and big-O notation may depend on $k$.

We estimate the first sum in (28) with Lemma 6 and apply (31) to get

$\begin{split}D_{m}(x)&+\sum_{n\in\mathcal{D}_{m}}\frac{x}{n\log
nt}\left\\{w\left(\frac{\log x/n}{\log
nt}\right)-e^{-\gamma}-\left.\frac{n^{2}t}{x}\right|_{n^{2}\leq\frac{x}{t}}\\!+O\left(\frac{e^{-\frac{\log
x/n}{3\log nt}}}{\log nt}\right)\right\\}\\\ &=\sum_{n\in\mathcal{D}_{q}\atop
n\geq r/t}\Phi(x/rn,nt)-\frac{x}{r}\sum_{n\in\mathcal{D}_{q}\atop n\geq
r/t}\lambda_{n}.\end{split}$ (40)

The contribution from the last two terms in the first sum in (40) is

$\ll\tilde{R}_{1}(x):=\frac{x\log mt}{m(\log xt)^{2}},$

by Lemma 1. In the second application of this argument we will be able to
replace $\tilde{R}_{1}(x)$ by the smaller

$R_{1}(x):=\frac{x\log t}{m(\log xt)^{2}}.$

The error from applying Abel summation to the remaining terms of the first sum
in (40) is also $\ll\tilde{R}_{1}(x)$, since $w(u)-e^{-\gamma}\ll e^{-u}$ and
$w^{\prime}(u)\ll e^{-u}$. Thus,

$\begin{split}D_{m}(x)=&x\int_{1}^{\infty}\frac{D_{m}(y)}{y^{2}\log
yt}\left(e^{-\gamma}-w\left(\frac{\log x/y}{\log
yt}\right)\right)dy+O(\tilde{R}_{1}(x))\\\ &+\sum_{n\in\mathcal{D}_{q}\atop
n\geq r/t}\Phi(x/rn,nt)-\frac{x}{r}\sum_{n\in\mathcal{D}_{q}\atop n\geq
r/t}\lambda_{n}.\end{split}$ (41)

If $x/r<\max(q,F(q)/t,r/t)$, that is $x<\max(m,F(m)/t)$, then Lemma 8 shows
that the first sum in (41) vanishes, while the second sum is

$\ll\frac{x}{m}\min\left(1,\frac{\log t}{\log
r}\right)\ll\frac{x}{m}\min\left(1,\frac{\log t}{\log m}\right),$

by the inductive hypothesis (38) and since $\log r\leq\log m\leq\log
r^{k+1}\ll_{k}\log r$. Define

$R_{2}(x):=\begin{cases}\frac{x}{m}\min\left(1,\frac{\log t}{\log
m}\right)&\text{if }x<\max(m,F(m)/t)\\\ 1+\frac{x\log t\log m\log
mt}{m\log^{3}xt}&\text{if }x\geq\max(m,F(m)/t).\end{cases}$

Thus,

$D_{m}(x)=x\int_{1}^{\infty}\frac{D_{m}(y)}{y^{2}\log
yt}\left(e^{-\gamma}-w\left(\frac{\log x/y}{\log yt}\right)\right)dy+R(x)$
(42)

holds with $R(x)\ll\tilde{R}_{1}(x)+R_{2}(x)$ when $x<\max(m,F(m)/t)$.

Assume now that $x\geq\max(m,F(m)/t)$. If $k=0$ and $q=1$, we have already
shown that the last row of (41) is $\ll R_{2}(x)$. If $k\geq 1$, write $q=uv$
where $v=P^{+}(q)$. Equations (28) and (31) show that the last row of (41)
equals

$\begin{split}=&\sum_{n\in\mathcal{D}_{u}\atop n\geq
v/t}\Phi(x/nrv,nt)-\frac{x}{rv}\sum_{n\in\mathcal{D}_{u}\atop n\geq
v/t}\lambda_{n}-\sum_{n\in\mathcal{D}_{q}\atop
n<r/t}\Phi(x/nr,nt)+\frac{x}{r}\sum_{n\in\mathcal{D}_{q}\atop
n<r/t}\lambda_{n}\\\ =&S-T-(U-V),\end{split}$

say. Now $x\geq\max(m,F(m)/t)$ implies $x/r\geq\max(q,F(q)/t,r/t)$. The
inductive hypothesis (37) yields

$S-T\ll 1+\frac{(x/r)\log t\log q\log qt}{q\log^{3}(xt/r)}\ll 1+\frac{x\log
t\log m\log mt}{m\log^{3}xt}=R_{2}(x),$

since $xt/r\geq\sqrt{xt}$. The second estimate in Lemma 6 and (38) show that

$\begin{split}U-V&\ll D_{q}(r/t)+\sum_{n\in\mathcal{D}_{q}\atop
n<r/t}\frac{x}{nr\log nt}\exp\left(-\frac{\log\frac{x}{nr}}{3\log
nt}\right)\\\ &\ll\frac{r^{2}\log t}{mt\log r}+R_{2}(x)\ll
R_{2}(x),\end{split}$

where the last assertion is implied by

$\frac{r}{\log r\log m\log mt}\ll\frac{xt/r}{\log^{3}(xt/r)},$

which holds because $mt>m\geq r$ and $r\leq xt/r$. As the last row of (41) is
$\ll R_{2}(x)$, we have established that (37) holds for $\Omega(q)\leq k$ and
that (42) holds with $R(x)\ll\tilde{R}_{1}(x)+R_{2}(x)$.

We need to estimate $I(x)$ and $J(x)$ from Lemma 7. For this purpose we may
assume that $x\geq\max(m,F(m)/t)$. If not, Lemma 8 shows that $D_{m}(x)=0$, so
that (12) holds since the main term in (12) is absorbed by the error terms. We
find that $I(x)+J(x)\ll\tilde{R}_{1}(x)+R_{2}(x)$ and $\beta_{t}\ll\frac{\log
m}{m\log t}$ so that $x\beta_{t}(v+1)^{-3}\ll R_{2}(x)$.

The conclusion of Lemma 7 is that

$D_{m}(x)=x\eta_{m,t}d(v)+O\bigl{(}\tilde{R}_{1}(x)+R_{2}(x)\bigr{)}.$ (43)

The lower bound in Lemma 1 yields $\eta_{m,t}\gg m^{-1}$. Lemma 11 shows that
$\eta_{m,t}\ll_{k}m^{-1}$. Together with (43), Lemmas 8 and 10, this implies

$D_{m}(x)\ll_{k}\frac{x\log t}{m\log xt},\quad(x\geq 1,t\geq 2,\Omega(m)\leq
k+1).$ (44)

Running through this proof a second time with this upper bound replacing the
one in Lemma 1, we can replace $\tilde{R}_{1}(x)$ by $R_{1}(x)$ to obtain

$D_{m}(x)=x\eta_{m,t}d(v)+O\bigl{(}R_{1}(x)+R_{2}(x)\bigr{)},$

where $1/m\ll\eta_{m,t}\ll_{k}1/m$. This shows that (12) and (14) hold with
$q$ replaced by $m=qr$.

To see that (12) implies (13), note that the term $O(1)$ is acceptable by
Lemma 10, provided $x\geq\max(m,F(m)/t)$. If $x<\max(m,F(m)/t)$, then
$D_{m}(x)=0$ and $x<F(m)\leq m^{2}$, so (13) (with $q$ replaced by $m$)
follows from $\log x\leq 2\log m$. This completes the proof of Theorem 2. ∎

######  Lemma 11.

Assume that (43) holds for $m$ with $\Omega(m)\leq k+1$, and that
$\eta_{q,t}\ll_{k}q^{-1}$ for $\Omega(q)\leq k$. Then
$\eta_{m,t}\ll_{k}m^{-1}$ for $\Omega(m)=k+1$.

###### Proof.

Let $m=qr$ where $r$ is prime and $r\geq P^{+}(q)$. Equation (34) yields

$\sum_{n\geq 1\atop qr|n}\lambda_{n}(s)\mu_{n}(s)=\frac{1}{r^{s}}\sum_{n\geq
r/t\atop q|n}\lambda_{n}(s)\bigl{(}\mu_{n}(s)-\log r\bigr{)}.$

As in [16], we let $s=1+1/\log^{2}N$ and split the sum on the left according
to $n\leq N$ and $n>N$. As $N\to\infty$, the contribution from $n\leq N$
converges to (see [16, Lemma 3]) $\sum_{qr|n}\lambda_{n}\mu_{n}$, while the
contribution from $n>N$ converges to (see [16, Lemma 4])
$-c_{qr}(1-e^{-\gamma}),$ by (43), where $\eta_{qr,t}=Cc_{qr}\log t$. Applying
the same reasoning to the sum on the right-hand side, we get

$\sum_{n\geq 1\atop
qr|n}\lambda_{n}\mu_{n}-c_{qr}(1-e^{-\gamma})=\frac{1}{r}\Bigl{(}\sum_{n\geq
r/t\atop q|n}\lambda_{n}\bigl{(}\mu_{n}-\log
r\bigr{)}-c_{q}(1-e^{-\gamma})\Bigr{)}.$

Since $\mu_{n}\ll\log t$ , we obtain

$rc_{qr}\ll S\log t+S\log r+c_{q},\quad S:=r\sum_{n\geq 1\atop
qr|n}\lambda_{n}=\sum_{n\geq r/t\atop q|n}\lambda_{n},$

by (31). Now $\eta_{q,t}\ll q^{-1}$ and (44) holds with $q$ in place of $m$.
Thus, $c_{q}\ll q^{-1}\log t$ and $S=\sum_{n\geq r/t\atop q|n}\lambda_{n}\ll
q^{-1}\min(1,\log t/\log r).$ This shows that $rc_{qr}\ll q^{-1}\log t$, which
is the desired result. ∎

##  5\. Proof of Theorem 3

###### Proof of (18), (19) and (20).

The estimate (18) is [16, Cor. 3]. Equation (34), with $k=1$ and $q_{1}=q$
prime, is

$\sum_{n\geq 1\atop q|n}\lambda_{n}(s)\mu_{n}(s)=\frac{1}{q^{s}}\sum_{n\geq
q/t}\lambda_{n}(s)\bigl{(}\mu_{n}(s)-\log q\bigr{)}.$ (45)

As in [16], we let $s=1+1/\log^{2}N$ and split the sum on the left according
to $n\leq N$ and $n>N$. As $N\to\infty$, the contribution from $n\leq N$
converges to (see [16, Lemma 3]) $\sum_{n\geq 1\atop q|n}\lambda_{n}\mu_{n}$,
while the contribution from $n>N$ converges to (see [16, Lemma 4])
$-c_{q}(1-e^{-\gamma}),$ by Corollary 6. Applying the same reasoning to the
right-hand side of (45), we get

$\sum_{n\geq 1\atop
q|n}\lambda_{n}\mu_{n}-c_{q}(1-e^{-\gamma})=\frac{1}{q}\Bigl{(}\sum_{n\geq
q/t}\lambda_{n}\bigl{(}\mu_{n}-\log
q\bigr{)}-c_{\theta}(1-e^{-\gamma})\Bigr{)}.$

With the estimate [16, Lemma 13]

$\mu_{n}=\log t-\gamma+O\left(e^{-\sqrt{\log nt}}\right),$ (46)

we obtain

$qc_{q}(1-e^{-\gamma})=S\log
q+c_{\theta}(1-e^{-\gamma})+O\left(Se^{-\sqrt{\log\max(q,t)}}\right),$ (47)

where

$S:=\sum_{n\geq q/t}\lambda_{n}=q\sum_{n\geq 1\atop q|n}\lambda_{n},$

by (31). If $q\leq t$, then $S=1$ by (30), so that (20) follows from (47).

In general, we have

$S=\frac{e^{-\gamma}c_{\theta}}{\log q}\left(1+O\left(\frac{1}{\log
q}+\frac{\log^{2}t}{\log^{2}q}\right)\right),\quad(q\geq 2,\,t\geq 2).$ (48)

If $q\leq t$, this holds because $S=1$ and $c_{\theta}\asymp\log t$. If $q\geq
t$, (48) follows from applying Abel summation to $S=\sum_{n\geq
q/t}\lambda_{n}$, together with Mertens’ formula and Corollary 6 (with $q=1$).
Combining (48) with (47) proves (19). ∎

###### Proof of (21), (22) and (23).

Equation (34), with $k=2$ and $q_{1}=p\leq q_{2}=q$ is

$\sum_{n\geq 1\atop pq|n}\lambda_{n}(s)\mu_{n}(s)=\frac{1}{q^{s}}\sum_{n\geq
q/t\atop p|n}\lambda_{n}(s)\bigl{(}\mu_{n}(s)-\log q\bigr{)}.$ (49)

As in [16], we let $s=1+1/\log^{2}N$ and split the sum on the left according
to $n\leq N$ and $n>N$. As $N\to\infty$, the contribution from $n\leq N$
converges to (see [16, Lemma 3]) $\sum_{pq|n}\lambda_{n}\mu_{n}$, while the
contribution from $n>N$ converges to (see [16, Lemma 4])
$-c_{pq}(1-e^{-\gamma}),$ by Corollary 6. Applying the same reasoning to the
right-hand side of (49), we get

$\sum_{n\geq 1\atop
pq|n}\lambda_{n}\mu_{n}-c_{pq}(1-e^{-\gamma})=\frac{1}{q}\Bigl{(}\sum_{n\geq
q/t\atop p|n}\lambda_{n}\bigl{(}\mu_{n}-\log
q\bigr{)}-c_{p}(1-e^{-\gamma})\Bigr{)}.$

We estimate $\mu_{n}$ with (46) to obtain

$qc_{pq}(1-e^{-\gamma})=T\log
q+c_{p}(1-e^{-\gamma})+O\left(T\exp\left(-\sqrt{\log\max(pt,q)}\right)\right),$
(50)

where

$T:=\sum_{n\geq q/t\atop p|n}\lambda_{n}=q\sum_{n\geq 1\atop
pq|n}\lambda_{n},$

by (31).

If $p\leq q\leq t$, then

$T=\sum_{n\geq 1\atop p|n}\lambda_{n}=\frac{1}{p}\sum_{n\geq
p/t}\lambda_{n}=\frac{1}{p}\sum_{n\geq 1}\lambda_{n}=\frac{1}{p},$

by (31) and (30). The estimate (23) now follows from (50) with $T=1/p$ and
$c_{p}$ estimated by (20).

In general, we have

$T=\frac{e^{-\gamma}c_{p}}{\log q}\left(1+O\left(\frac{1}{\log
q}+\frac{\log^{2}pt}{\log^{2}q}\right)\right),\quad(q\geq p\geq 2,\,t\geq 2).$
(51)

If $q<pt$, this is implied by $T\ll c_{p}/\log q$, which follows from (17)
(with $q$ replaced by $p$). If $q\geq pt$, we estimate $\lambda_{n}$ with
Mertens’ formula and use Abel summation and the estimate (15). The
contribution from the first two error terms in (15) is clearly acceptable,
while the term $O(1)$ contributes

$\ll\int_{q/t}^{\infty}\frac{dy}{y^{2}\log yt}\leq\frac{t}{q\log
q}\asymp\frac{c_{p}}{\log q}\cdot\frac{pt}{q\log t}\ll\frac{c_{p}}{\log
q}\cdot\frac{\log^{2}pt}{\log^{2}q}.$

Now substitute (51) into (50) and estimate $c_{p}$ with (19) to get (21), and
with (20) to get (22). ∎

##  6\. Proof of Theorem 1

###### Proof of (1)..

We have

$\sum_{n\in\mathcal{D}(x)}\omega(n)=\sum_{p\leq x}D_{p}(x)=xd(v)\sum_{p\leq
x}\eta_{p,t}\left(1+O\left(\frac{\log p}{\log x}\right)\right),$

by (13). The contribution from the error term is $\ll xd(v)\asymp D(x)$, since
$\eta_{p,t}\ll 1/p$ by (14). Now $\eta_{p,t}C\log t=c_{p}$ and
$\eta_{1,t}C\log t=c_{\theta}$, by Corollary 6. With (18), (19) and (20), we
find that

$\sum_{p\leq x}\eta_{p,t}=\frac{1}{C\log t}\sum_{p\leq
x}c_{p}=\frac{c_{\theta}}{C\log t}(E(x,t)+O(1))=\eta_{1,t}(E(x,t)+O(1)).$

The result now follows from (13) with $q=1$, that is
$D(x)=xd(v)\eta_{1,t}(1+O(1/\log x))$.

To see that (1) remains valid when $\omega$ is replaced by $\Omega$, note that

$\sum_{n\in\mathcal{D}(x)}(\Omega(n)-\omega(n))=\sum_{n\in\mathcal{D}(x)}\sum_{k\geq
2}\sum_{p^{k}|n}1=\sum_{p\leq x}\sum_{k\geq 2}D_{p^{k}}(x)\ll\frac{x\log
t}{\log xt}\ll D(x),$

by Lemma 1. ∎

###### Proof of (2)..

We have

$\sum_{n\in\mathcal{D}(x)}\omega(n)^{2}=\sum_{p,q\leq
x}D_{pq}(x)+O\Bigl{(}\sum_{p\leq x}D_{p}(x)\Bigr{)},$

where $p,q$ run over primes. The last term is $\ll D(x)\log_{2}x$, by (1).
Thus, (13) yields

$\sum_{n\in\mathcal{D}(x)}\omega(n)^{2}=O(D(x)\log_{2}x)+xd(v)\sum_{p,q\leq
x}\eta_{pq,t}\left(1+O\left(\frac{\log pq}{\log x}\right)\right).$

Since $\eta_{pq,t}\ll 1/pq$, the contribution from the error term is $\ll
xd(v)\log_{2}x\ll D(x)\log_{2}x$. With (21), (22) and (23), we find that

$\begin{split}\sum_{p,q\leq x}\eta_{pq,t}=\frac{1}{C\log t}\sum_{p,q\leq
x}c_{pq}&=\frac{c_{\theta}}{C\log t}\bigl{(}E(x,t)^{2}+O(\log_{2}x)\bigr{)}\\\
&=\eta_{1,t}\bigl{(}E(x,t)^{2}+O(\log_{2}x)\bigr{)}.\end{split}$

Combining this with (1) and (13) (with $q=1$), we get

$\sum_{n\in\mathcal{D}(x)}(\omega(n)-E(x,t))^{2}\ll D(x)\log_{2}x,$

which implies (2). This estimate remains valid if $\omega(n)$ is replaced by
$\Omega(n)$, since

$\sum_{n\in\mathcal{D}(x)}(\Omega(n)-\omega(n))^{2}\leq\sum_{p\neq q\leq
x}\sum_{k,j\geq 2}D_{p^{k}q^{j}}(x)+\sum_{p\leq x}\sum_{k\geq
2}2kD_{p^{k}}(x)\ll D(x),$

by Lemma 1. ∎

## Acknowledgments

The author thanks Eric Saias and the anonymous referee for several very
helpful suggestions.

## References

  * [1] R. R. Hall and G. Tenenbaum, Divisors, Cambridge University Press, 1988.
  * [2] M. Margenstern, Les nombres pratiques: théorie, observations et conjectures, J. Number Theory 37 (1991), 1–36.
  * [3] J.-L. Nicolas, Sur la distribution des nombres entiers ayant une quantité fixée de facteurs premiers, Acta Arith. 44 (1984), 191–200.
  * [4] C. Pomerance, L. Thompson, A. Weingartner, On integers $n$ for which $X^{n}-1$ has a divisor of every degree, Acta Arith. 175 (2016), no. 3, 225–243.
  * [5] C. Pomerance and A. Weingartner, On primes and practical numbers, arXiv: 2007.11062
  * [6] E. Saias, Entiers à diviseurs denses 1, J. Number Theory 62 (1997), 163–191.
  * [7] W. Sierpiński, Sur une propriété des nombres naturels, Ann. Mat. Pura Appl. (4) 39 (1955), 69–74.
  * [8] A. K. Srinivasan, Practical numbers, Current Sci. 17 (1948), 179–180.
  * [9] B. M. Stewart, Sums of distinct divisors, Amer. J. Math. 76 (1954), 779–785.
  * [10] G. Tenenbaum, Sur un problème de crible et ses applications, Ann. Sci. École Norm. Sup. (4) 19 (1986), 1–30.
  * [11] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics, Vol. 46, Cambridge Univ. Press, Cambridge, 1995.
  * [12] L. Thompson, Polynomials with divisors of every degree, J. Number Theory 132 (2012), 1038–1053.
  * [13] A. Weingartner, Integers with dense divisors 3, J. Number Theory 142 (2014), 211-222.
  * [14] A. Weingartner, Practical numbers and the distribution of divisors, Q. J. Math. 66 (2015), no. 2, 743–758.
  * [15] A. Weingartner, A sieve problem and its application, Mathematika 63 (2017), no. 1, 213–229.
  * [16] A. Weingartner, On the constant factor in several related asymptotic estimates, Math. Comp. 88 (2019), no. 318, 1883–1902.
  * [17] A. Weingartner, The mean number of divisors for rough, dense and practical numbers, preprint arXiv:2104.07137.