# The Schinzel-Szekeres function

Andreas Weingartner  Department of Mathematics, 351 West University Boulevard,
Southern Utah University, Cedar City, Utah 84720, USA<EMAIL_ADDRESS>
(Date: October 19, 2023)

###### Abstract.

We derive asymptotic estimates for distribution functions related to the
Schinzel-Szekeres function. These results are then used in three different
applications: the longest simple path in the divisor graph, a problem of Erdős
about a sum of reciprocals, and the small sieve of Erdős and Ruzsa.

##  1\. Introduction

The Schinzel-Szekeres function is defined as

$F(n)=\begin{cases}1&\quad(n=1)\\\ \max\\{d\,P^{-}(d):d|n,\ d>1\\}&\quad(n\geq
2),\end{cases}$

where $P^{-}(d)$ denotes the smallest prime factor of $d>1$ and
$P^{-}(1):=\infty$. This function appears implicitly in [11]. It plays a role
in various applications, such as a problem of Erdős considered by Schinzel and
Szekeres [11], the small sieve of Erdős and Ruzsa [6], the distribution of
divisors [7, 12, 16], and the length of the longest simple path in the divisor
graph [8, 13]. For the corresponding counting function

$A(x)=|\\{n\geq 1:F(n)\leq x\\}|,$

Schinzel and Szekeres [11] showed that $A(x)=o(x)$ as $x\to\infty$. Ruzsa [6]
found that there is a constant $c>0$ such that $A(x)\leq\frac{x}{\log^{c}x}$.
Tenenbaum [12, 13] improved this to $A(x)=\frac{x}{\log x}(\log\log x)^{O(1)}$
and Saias obtained $A(x)\asymp\frac{x}{\log x}$.

######  Theorem 1.

For $x\geq 2$, we have

$A(x)=\frac{ax}{\log x}\left(1+O\left(\frac{1}{\log x}\right)\right),$

where the constant $a=1.53796...$ is given by

$a=\frac{1}{1-e^{-\gamma}}\left(1-\gamma+\int_{1}^{\infty}A(t)g(t)\frac{dt}{t^{2}}\right),$

$\gamma$ is Euler’s constant and

$g(t)=\biggl{(}\sum_{p\leq t}\frac{\log p}{p-1}+\gamma-\log
t\biggr{)}\prod_{p\leq t}\left(1-\frac{1}{p}\right).$

###  1.1. The longest simple path in the divisor graph

The divisor graph of order $n$ consists of vertices $1,2,\ldots,n$ and an edge
between vertices $j,k$ if and only if $j|k$ or $k|j$. Let $f(n)$ be the
maximal number of vertices in a simple path of the divisor graph of order $n$.
Improving on earlier work by Pollington [3], Pomerance [4] and Tenenbaum [13],
Saias [8, 10] showed that $f(n)\asymp\frac{n}{\log n}$ and $f(n)\geq
A(n/2)>0.306\frac{n}{\log n}$ for $n\geq n_{0}$. With Theorem 1, we obtain the
following lower bound.

######  Corollary 1.

For all sufficiently large $n$,

$f(n)>0.76898\frac{n}{\log n}.$

###  1.2. A problem of Erdős

Erdős considered the question of how large $\sum_{n\in\mathcal{S}}\frac{1}{n}$
can be for a set $\mathcal{S}$ of integers up to $x$ with the property

(1) $m,n\in\mathcal{S}\text{ and }n\neq m\ \Rightarrow\
\operatorname{lcm}(m,n)>x.$

Define

$R(x)=\max_{\mathcal{S}}\sum_{n\in\mathcal{S}}\frac{1}{n},$

where the maximum is taken over all sets of integers
$\mathcal{S}\subset\\{2,3,\ldots,\lfloor x\rfloor\\}$ that have the
$\operatorname{lcm}$ property (1).

Erdős showed that $R(x)<2$ and conjectured [11] that $R(x)<1+o(1)$ as
$x\to\infty$. Lehman [2] improved this to $R(x)<\frac{7}{6}+\frac{1}{6x}$. It
seems that there are only two known cases where $R(x)>1$, namely
$R(5)=\frac{31}{30}$ from $\mathcal{S}=\\{2,3,5\\}$, and
$R(11)=\frac{4699}{4620}$ from $\mathcal{S}=\\{3,4,5,7,11\\}$. Schinzel and
Szekeres [11] showed that $R(x)\leq\frac{31}{30}$, with equality being
attained only at $x=5$. Moreover, they proved that $R(x)<c+o(1)$, where
$c=1.017262...$. They [11, Theorem 3] also established the lower bound
$R(x)>1-o(1)$, by way of $\mathcal{S}=\mathcal{B}(x)$, where

$\mathcal{B}(x)=\\{n\leq x:F(n)>x\text{ and }F(d)\leq x\text{ for all
}d|n,d<n\\}.$

It is not difficult to see [11, Proof of Thm. 3] that $\mathcal{B}(x)$ has the
$\operatorname{lcm}$ property (1).

######  Theorem 2.

For $x\geq 2$, we have

$\sum_{n\in\mathcal{B}(x)}\frac{1}{n}=1-\frac{\delta}{\log
x}+O\left(\frac{1}{(\log x)^{3/2}}\right),$

where $\delta:=a+\gamma-1-\beta=0.560...$, the constant $a$ is as in Theorem 1
and $\beta$ is given by (44). More precisely, $0.560374<\delta<0.560579$.

Theorem 2 allows us to improve the lower bound $R(x)>1-o(1)$ of Schinzel and
Szekeres to

$R(x)>1-\frac{\delta+o(1)}{\log x},\quad\delta=0.560...$

We can improve this further by making a small change to $\mathcal{B}(x)$,
based on the two known instances where $R(x)>1$. Let $\mathcal{B}^{\prime}(x)$
be the set obtained from $\mathcal{B}(x)$, by replacing every
$n\in(\frac{x}{6},\frac{x}{5}]\cap\mathcal{B}(x)$ by $\\{2n,3n,5n\\}$, and
every $n\in(\frac{x}{12},\frac{x}{11}]\cap\mathcal{B}(x)$ by
$\\{3n,4n,5n,7n,11n\\}$. Then $\mathcal{B}^{\prime}(x)\subset[1,x]$ and
$\mathcal{B}^{\prime}(x)$ has the $\operatorname{lcm}$ property (1).

######  Theorem 3.

For $x\geq 2$, we have

$R(x)\geq\sum_{n\in\mathcal{B}^{\prime}(x)}\frac{1}{n}=1-\frac{\kappa}{\log
x}+O\left(\frac{1}{(\log x)^{3/2}}\right),$

where $\kappa=0.543...$ is given by (48). More precisely,
$0.543595<\kappa<0.543804$.

It is clear that any other examples of $R(x)>1$, besides $x=5,11$, if they
exist, would lead to further small improvements. In the absence of such
examples, it seems plausible that Theorem 3 is best possible.

######  Question 1.

Is it true that $R(x)=1-\frac{\kappa+o(1)}{\log x}$ ?

###  1.3. The small sieve of Erdős and Ruzsa

Here the question is how small we can make the number of unsieved integers up
to $x$, after removing multiples of a set $\mathcal{S}$ with the property

(2) $\sum_{n\in\mathcal{S}}\frac{1}{n}\leq 1,\quad 1\notin\mathcal{S}.$

Define

$H(x)=\min_{\mathcal{S}}|\\{n\leq x:s\nmid n\text{ for all
}s\in\mathcal{S}\\}|,$

where the minimum is over all sets $\mathcal{S}$ satisfying (2). Ruzsa [6]
showed that $\frac{x}{\log x}\ll H(x)<\frac{x}{(\log x)^{c}}$ for some
constant $c>0$. Tenenbaum [12] improved the upper bound to
$H(x)\ll\frac{x}{\log x}(\log\log x)^{2}$, and Saias [8] established
$H(x)\ll\frac{x}{\log x}$ via the inequality
$H(x)\leq\max(A(x),B(x)+\sqrt{x})$, where $B(x)=|\mathcal{B}(x)|$.

Theorem 2 shows that $\mathcal{B}(x)$ satisfies (2), for all sufficiently
large $x$. After removing multiples of members of $\mathcal{B}(x)$, the
unsieved integers up to $x$ are exactly the members of

$\mathcal{A}(x)=\\{n\geq 1:F(n)\leq x\\}.$

Thus

$H(x)\leq A(x)=\frac{(a+o(1))x}{\log x}<\frac{1.53797x}{\log x},$

by Theorem 1, for all sufficiently large $x$. The term $-\frac{\delta}{\log
x}$ in Theorem 2 allows us to improve on this upper bound. For
$\frac{1}{x}\leq\tau\leq 1$, define

$\mathcal{B}_{\tau}(x)=\mathcal{B}(\tau x)\cup\\{p\in(\tau x,x]:p\text{
prime}\\},$

as in Ruzsa [6, Proof of the upper bound in Theorem I]. After removing
multiples of members of $\mathcal{B}_{\tau}(x)$, the unsieved integers up to
$x$ are exactly the members of $\mathcal{A}(\tau x)$. It follows that

$H(x)\leq H^{*}(x):=\min_{\tau\in\mathcal{T}(x)}A(\tau x),$

where

$\mathcal{T}(x)=\Bigl{\\{}\tau\geq
1/x:\sum_{n\in\mathcal{B}_{\tau}(x)}\frac{1}{n}\leq 1\Bigr{\\}}.$

With Theorems 1 and 2, we will establish an estimate for $H^{*}(x)$.

######  Theorem 4.

Let $a$ and $\delta$ be as in Theorems 1 and 2. For $x\geq 2$, we have

$H(x)\leq H^{*}(x)=\frac{ae^{-\delta}x}{\log x}+O\left(\frac{x}{(\log
x)^{3/2}}\right),$

where $ae^{-\delta}\approx 0.878$. More precisely,
$0.877992<ae^{-\delta}<0.878171$.

######  Corollary 2.

For all sufficiently large $x$, we have

$H(x)<\frac{0.879x}{\log x}.$

For $2\leq x\leq 40$, we find that $H^{*}(x)-H(x)\in\\{0,1\\}$. It seems
plausible that $H(x)\sim H^{*}(x)$ as $x\to\infty$.

######  Question 2.

Is it true that $H(x)\sim\frac{ae^{-\delta}x}{\log x}$ as $x\to\infty$ ?

Ruzsa [6] also considered the more general problem of estimating

$H(x,z)=\min_{\mathcal{S}}|\\{n\leq x:s\nmid n\text{ for all
}s\in\mathcal{S}\\}|,$

where the minimum now is over all sets $\mathcal{S}$ that satisfy

(3) $\sum_{n\in\mathcal{S}}\frac{1}{n}\leq z,\quad 1\notin\mathcal{S}.$

Let

$H^{*}(x,z):=\min_{\tau\in\mathcal{T}(x,z)}A(\tau x),$

where

$\mathcal{T}(x,z)=\Bigl{\\{}\tau\geq
1/x:\sum_{n\in\mathcal{B}_{\tau}(x)}\frac{1}{n}\leq z\Bigr{\\}}.$

######  Theorem 5.

Let $a$ and $\delta$ be as in Theorems 1 and 2. Let $\mu>-\delta$ be constant.
For $x\geq 2$, we have

$H\left(x,1+\frac{\mu}{\log x}\right)\leq H^{*}\left(x,1+\frac{\mu}{\log
x}\right)=\frac{ae^{-\delta-\mu}x}{\log x}+O\left(\frac{x}{(\log
x)^{3/2}}\right).$

Let $Z>1$ be fixed. Uniformly for $1\leq z\leq Z$, $x\geq 2$,

$H\left(x,z\right)\asymp\frac{x^{\exp(1-z)}}{\log x}.$

The last estimate improves Ruzsa’s result [6, Theorem I]

$\lim_{x\to\infty}\frac{\log H(x,z)}{\log x}=e^{1-z}.$

###  1.4. Integers with dense divisors

The significance of $F(n)$ to the distribution of divisors comes from
Tenenbaum’s identity [12, Lemma 2.2]

$\frac{F(n)}{n}=\max_{1\leq i<k}\frac{d_{i+1}}{d_{i}},$

where $1=d_{1}<d_{2}<\cdots<d_{k}=n$ is the increasing sequence of divisors of
$n$. Thus

$D(x,y):=|\\{n\leq x:F(n)/n\leq y\\}|$

counts the number of integers up to $x$ whose sequence of divisors grows by
factors of at most $y$. It may appear that the asymptotic estimates for
$D(x,y)$ in [16] should suffice to derive Theorem 1, but we have not been able
to do so. Instead, we derive Theorem 1 from new estimates for the more general

$D(x,y,z):=|\\{n\leq x:F(n)/n\leq y,\ P^{-}(n)>z\\}|,$

which has been considered previously by Saias [9] and the author [14].

In Section 2, we state these new estimates for $D(x,y,z)$, which are proved in
sections 3 through 5, with methods developed in [15, 16, 17] for the study of
$D(x,y)$. As a consequence, in Section 6, we are able to derive results, not
only for $A(x)$, but for the more general

$A(x,y,z):=|\\{n\leq x:F(n)\leq xy,P^{-}(n)>z\\}|,$

which are needed for the proofs of Theorems 2, 3, 4 and 5. In Section 7 we
give an algorithm for computing the constant factor in the asymptotic for
$A(x,y,z)$. We prove Theorem 2 in Section 8 and Theorem 3 in Section 9.
Section 10 contains the proofs of Theorems 4 and 5.

##  2\. Estimates for $D(x,y,z)$ and $A(x,y,z)$

Define

$u=\frac{\log x}{\log y},\quad v=\frac{\log x}{\log z},\quad
r=\frac{u}{v}=\frac{\log z}{\log y}.$

In [14, Theorem 1] we found that

(4) $D(x,y,z)=\frac{xd(u,v)}{\log z}+\frac{y}{\log y}-\frac{z}{\log
z}+O\left(\frac{x}{\log^{2}z}\right),\quad(x\geq y\geq z\geq 3/2),$

where the function $d(u,v)$ is defined by a certain difference-differential
equation [14, Eq. 3]. This definition of $d(u,v)$ is based on the Buchstab
identity

(5) $D(x,y,z)=1+\sum_{z<p\leq y}D(x/p,py,p-0),$

which follows from grouping the integers counted in $D(x,y,z)$ according to
their smallest prime factor $p$. In [15, 16] we used a different kind of
functional equation (i.e. Lemma 1 with $z=1$) to show that

$D(x,y)=x\eta(y)d(u)\left(1+O\left(\frac{1}{\log x}\right)\right)\quad(x\geq
y\geq 1),$

where $\eta(y)=1+O(1/\log y)$ and $d(u)$ is given by $d(u)=0$ for $u<0$ and

(6) $d(u)=1-\int_{0}^{\frac{u-1}{2}}\frac{d(t)}{t+1}\
\omega\left(\frac{u-t}{t+1}\right)\,\mathrm{d}t\qquad(u\geq 0).$

Here and throughout, $\omega(u)$ denotes Buchstab’s function. Equation (6) can
be solved with Laplace transforms to obtain [15, Theorem 1]

(7) $d(u)=\frac{C}{u+1}\left(1+O\left(\frac{1}{u^{2}}\right)\right),\quad
C=\frac{1}{1-e^{-\gamma}}=2.280291...$

The following theorems generalize these results to $d(u,v)$ and $D(x,y,z)$.

######  Theorem 6.

For $v\geq u\geq 1$ we have

$\begin{split}d(u,v)&=e^{-\gamma}(1-u/v)\,d(u)\left(1+O\left(\frac{1}{uv}\right)\right)=\frac{Ce^{-\gamma}(1-u/v)}{u+1}\left(1+O\left(\frac{1}{u^{2}}\right)\right).\end{split}$

We will use the following notation throughout. Let

$\Pi(z):=\prod_{p\leq
z}\left(1-\frac{1}{p}\right),\qquad\Sigma(z):=\sum_{p\leq z}\frac{\log
p}{p-1},$

and

(8) $\mathcal{E}(z):=\sup_{t\geq z}\left|\Sigma(t)+\gamma-\log
t\right|\ll_{\varepsilon}\exp\left\\{-(\log z)^{3/5-\varepsilon}\right\\},$

for any fixed $\varepsilon>0$, by the prime number theorem.

######  Theorem 7.

For $x\geq y\geq z\geq 3/2$,

(9) $D(x,y,z)=xd(u,v)e^{\gamma}\Pi(z)+\frac{x\beta_{y,z}}{\log
xy}+\frac{y}{\log y}-\frac{z}{\log z}+O\left(\frac{x\log y}{\log^{2}x\log
z}\right),$

where $\beta_{y,z}=c_{y,z}-C\Pi(z)\log(y/z)$ and $c_{y,z}$ is as in Theorem 8.
We have

(10) $|\beta_{y,z}|\leq C\Pi(z)(\mathcal{E}(z)+\mathcal{E}(y)).$

Note that Theorem 7 implies (4). Let $\chi(n)$ be the characteristic function
of the set

(11) $\mathcal{D}:=\\{n\in\mathbb{N}:F(n)/n\leq y,P^{-}(n)>z\\}.$

Let $\pi(y,z)$ be the number of primes $p$ satisfying $z<p\leq y$, that is

$\pi(y,z):=\sum_{z<p\leq y}1.$

######  Theorem 8.

For $x\geq y\geq z\geq 3/2$ and $y\ll\frac{x}{\log x}$ we have

(12) $D(x,y,z)=1+\frac{c_{y,z}x}{\log xy}\left\\{1+O\left(\frac{1}{\log
x}+\frac{\log^{2}y}{\log^{2}x}\right)\right\\},$

and, for $x\geq y\geq z\geq 3/2$,

(13) $D(x,y,z)=1+\pi(y,z)+\frac{c_{y,z}x}{\log
xy}\left\\{1+O\left(\frac{1}{\log
x}+\frac{\log^{2}y}{\log^{2}x}\right)\right\\},$

where $c_{y,z}$ is given by

(14) $c_{y,z}=C\sum_{n\geq
1}\frac{\chi(n)}{n}\bigl{(}\Sigma(yn)-\Sigma(z)-\log n\bigr{)}\Pi(yn).$

For $y\geq z\geq 1$,

(15) $\displaystyle c_{y,z}$ $\displaystyle=C\Pi(z)(\log
y-\gamma-\Sigma(z)+\zeta_{y,z}),\quad$
$\displaystyle|\zeta_{y,z}|\leq\mathcal{E}(y),$ (16) $\displaystyle c_{y,z}$
$\displaystyle=C\Pi(z)(\log(y/z)+\psi_{y,z}),$
$\displaystyle|\psi_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y),$ (17)
$\displaystyle c_{y,z}$ $\displaystyle=C(\Pi(z)-\Pi(y))\left(\log
y+\xi_{y,z}\right),$
$\displaystyle|\xi_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y),$ (18)
$\displaystyle c_{y,z}$ $\displaystyle\asymp(\Pi(z)-\Pi(y))\log y.$

Table 1. Values of the factor $c_{y,z}$. | $z=1$ | $z=2$ | $z=3$ | $z=5$
---|---|---|---|---
$y=2$ | 1.2248… | 0 | 0 | 0
$y=3$ | 2.0554… | 0.4315… | 0 | 0
$y=4$ | 2.4496… | 0.5242… | 0 | 0
$y=5$ | 2.9541… | 0.8402… | 0.2351… | 0
$y=6$ | 3.2477… | 0.9263… | 0.2574… | 0
$y=7$ | 3.6441… | 1.1573… | 0.4321… | 0.1544…

In Section 6, we will derive the following two theorems from Theorems 7 and 8.

######  Theorem 9.

For $x\geq y\geq z\geq 3/2$ we have

(19)
$A(x,y,z)=\pi(\sqrt{xy},z)+xd(u,v)e^{\gamma}\Pi(z)+\frac{\tau_{y,z}x}{\log
xy}+O\left(\frac{x\log y}{\log^{2}x\log z}\right),$

where $\tau_{y,z}=a_{y,z}-C\Pi(z)\log(y/z)$ and $a_{y,z}$ is as in Theorem 10.
We have

(20)
$\tau_{y,z}=C\Pi(z)\left(1+\eta_{y,z}\right),\qquad|\eta_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y).$

######  Theorem 10.

For $y\geq 1$, $z\geq 1$, $x\geq\max(2,y,z)$, we have

(21) $A(x,y,z)=1+\pi(\sqrt{xy},z)+\frac{a_{y,z}x}{\log
xy}\left(1+O\left(\frac{1}{\log
xy}+\frac{\log^{2}2zy}{\log^{2}xy}\right)\right).$

If $y\geq z\geq 1$,

(22) $a_{y,z}=C\Pi(z)\left(1-\gamma+\log
y-\Sigma(z)\right)+C\int_{1}^{\infty}A(t,y,z)g(yt)\frac{dt}{t^{2}},$

where $g(t)=(\Sigma(t)+\gamma-\log t)\Pi(t).$ If $z\geq y\geq 1$, then
$a_{y,z}=\frac{y}{z}a_{z,z}$.

For $y\geq z\geq 1$,

(23) $\displaystyle a_{y,z}$ $\displaystyle=C\Pi(z)\left(1-\gamma+\log
y-\Sigma(z)+\delta_{y,z}\right),\qquad$
$\displaystyle|\delta_{y,z}|\leq\mathcal{E}(y),$ (24) $\displaystyle a_{y,z}$
$\displaystyle=C\Pi(z)\left(1+\log(y/z)+\eta_{y,z}\right),\qquad$
$\displaystyle|\eta_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y).$

For $y\geq 1$, $z\geq 1$,

(25) $a_{y,z}\asymp\Pi(z)\log(1+y/z).$

Table 2. Values of the factor $a_{y,z}$. | $z=1$ | $z=2$ | $z=3$ | $z=5$
---|---|---|---|---
$y=1$ | 1.5379… | 0.4178… | 0.1583… | 0.0831…
$y=2$ | 3.0759… | 0.8357… | 0.3167… | 0.1662…
$y=3$ | 3.9184… | 1.2535… | 0.4751… | 0.2493…
$y=4$ | 4.4804… | 1.5153… | 0.6335… | 0.3325…
$y=5$ | 4.9557… | 1.7525… | 0.7918… | 0.4156…
$y=6$ | 5.3297… | 1.9280… | 0.9015… | 0.4987…

Theorem 1 follows from Theorem 10 with $y=z=1$. Theorems 9 and 10 sharpen
earlier results by Saias [8, Lem. 5] and the author [14, Thm. 1].

##  3\. Proof of Theorem 6

Let

$\Phi(x,z)=|\\{n\leq x:P^{-}(n)>z\\}|.$

Note that for $n\geq 2$ with prime factorization $n=p_{1}\cdots p_{k}$, where
$p_{1}\leq p_{2}\leq\ldots\leq p_{k}$, we have

$\frac{F(n)}{n}\leq y\quad\Leftrightarrow\quad p_{j+1}\leq y\prod_{1\leq i\leq
j}p_{i}\quad(0\leq j<k).$

######  Lemma 1.

For $x\geq 1$, $y\geq z\geq 1$ we have

$\Phi(x,z)=\sum_{n\leq x}\chi(n)\Phi(x/n,yn).$

###### Proof.

Every $m$ counted in $\Phi(x,z)$ factors uniquely as $m=nr$, where
$n\in\mathcal{D}$ and $P^{-}(r)>ny$. ∎

######  Lemma 2.

For $x\geq 1$, $y\geq z\geq 1$ we have

$D(x,y,z)-1=\Phi(x,z)-\Phi(x,y)-\sum_{z<n\leq\sqrt{x/y}}\chi(n)\bigl{(}\Phi(x/n,yn)-1\bigr{)}$

###### Proof.

This follows from Lemma 1, since $1\in\mathcal{D}$, $2\leq n\leq z\Rightarrow
n\notin\mathcal{D}$, and $n>\sqrt{x/y}\Rightarrow\Phi(x/n,yn)=1$. ∎

######  Lemma 3.

For $x\geq 1$, $z\geq 3/2$, we have

$\Phi(x,z)-1=x\Pi(z)+\frac{x(w(v)-e^{-\gamma})}{\log z}-\left.\frac{z}{\log
z}\right|_{x\geq z}+O\left(\frac{xe^{-v/3}}{\log^{2}z}\right),$

where $v=\frac{\log x}{\log z}$ and $w(v)$ is Buchstab’s function.

###### Proof.

This is Lemma 6 of [19]. ∎

We write $d_{r}(u):=d(u,u/r)$ for $0<r\leq 1$ and $d_{0}(u):=e^{-\gamma}d(u)$.

######  Lemma 4.

For $u\geq 0$, $0<r\leq 1$ we have

$d_{r}(u)=\omega(u/r)-r\omega(u)-\int_{0}^{u}\frac{d_{r}(t)}{t+1}\,\omega\left(\frac{u-t}{t+1}\right)\mathrm{d}t.$

###### Proof.

When $u\leq 1$, this follows from the initial conditions for $d(u,v)$ [14, Eq.
(4)]. Assume $u>1$ and $0<r\leq 1$ are fixed. In Lemma 2, we estimate
$D(x,y,z)$ with (4) and apply

$\Phi(x,z)=\frac{x\omega(v)-z}{\log
z}+O\left(\frac{x}{\log^{2}z}\right),\quad(x\geq z\geq 3/2),$

which follows from Lemma 3. In the sum of Lemma 2, first estimate
$\Phi(x/n,yn)$, then use partial summation and estimate $D(x,y,z)$ with (4). ∎

Note that as $r\to 0$, the equation in Lemma 4 turns into the equation for
$d(u)$ in (6), multiplied by $e^{-\gamma}$.

In order to calculate Laplace transforms, we make the following change of
variables. Let

(26) $G_{r}(y)=d_{r}(e^{y}-1)\quad(0\leq r\leq 1),$ (27)
$\Omega_{r}(y)=\omega\left(\frac{e^{y}-1}{r}\right)\quad(0<r\leq
1),\qquad\Omega_{0}(y)=e^{-\gamma}.$

######  Lemma 5.

For $0\leq r\leq 1$ and $\mathrm{Re}(s)>0$ we have

$\widehat{G}_{r}(s)=\frac{\widehat{\Omega}_{r}(s)-r\widehat{\Omega}_{1}(s)}{1+\widehat{\Omega}_{1}(s)}.$

###### Proof.

In Lemma 4, changing variables $u=e^{\lambda}-1$, $t=e^{\mu}-1$, leads to

$G_{r}(\lambda)=\Omega_{r}(\lambda)-r\Omega_{1}(\lambda)-\int_{0}^{\lambda}G_{r}(\mu)\Omega_{1}(\lambda-\mu)d\mu.$

Calculating Laplace transform, we have, for $\mathrm{Re}(s)>0$ ,

$\widehat{G}_{r}(s)=\widehat{\Omega}_{r}(s)-r\widehat{\Omega}_{1}(s)-\widehat{G}_{r}(s)\widehat{\Omega}_{1}(s),$

which yields the stated result. ∎

###### Proof of Theorem 6.

Let $r=u/v$, $\lambda=\log(u+1)$, and

$E_{r}(\lambda):=\Omega_{r}(\lambda)-e^{-\gamma}-r(\Omega_{1}(\lambda)-e^{-\gamma}).$

Let $G(\lambda):=d(e^{\lambda}-1)$, where $d(u)$ is as in (6). As in the proof
of Lemma 5, equation (6) leads to

(28) $\widehat{G}(s)=\frac{1}{s(1+\widehat{\Omega}_{1}(s))},$

for $\mathrm{Re}(s)>0$. With Lemma 5, we find that

$\widehat{G}_{r}(s)=e^{-\gamma}(1-r)\widehat{G}(s)+\widehat{E}_{r}(s)s\widehat{G}(s).$

We have

(29) $s\widehat{G}(s)=\widehat{G^{\prime}}(s)+G(0)=\widehat{G^{\prime}}(s)+1$

and

(30)
$G^{\prime}(\lambda)=d^{\prime}(e^{\lambda}-1)e^{\lambda}=-Ce^{-\lambda}+O\left(e^{-3\lambda}\right),$

by Corollary 5 of [15]. Thus

(31)
$G_{r}(\lambda)=e^{-\gamma}(1-r)G(\lambda)+E_{r}(\lambda)+\int_{0}^{\lambda}E_{r}(\tau)\left(-Ce^{-(\lambda-\tau)}+O(e^{-3(\lambda-\tau)})\right)d\tau.$

Considering the two cases $0\leq r\leq 1/2$ and $1/2<r\leq 1$, we find that
for any fixed $A>0$ we have

$E_{r}(\tau)\ll_{A}r(1-r)e^{-A\tau}.$

Moreover,

$\int_{0}^{\infty}E_{r}(\tau)e^{\tau}d\tau=\int_{0}^{\infty}\left[(\omega(u/r)-e^{-\gamma})-r(\omega(u)-e^{-\gamma})\right]du=0.$

This shows that the integral in (31) amounts to $\ll r(1-r)e^{-3\lambda}$.
Thus (31) simplifies to

$G_{r}(\lambda)=e^{-\gamma}(1-r)G(\lambda)+O(r(1-r)e^{-3\lambda}),$

that is

$d_{r}(u)=e^{-\gamma}(1-r)d(u)+O(r(1-r)u^{-3}).$

The first estimate in Theorem 6 now follows, since $d(u)\asymp 1/u$ for $u\geq
1$. The second estimate follows from the first and (7). ∎

##  4\. Proof of Theorem 7

Let

$\delta(x)=\begin{cases}1&\mbox{if }x\geq 0\\\ 0&\mbox{if }x<0.\end{cases}$

######  Lemma 6.

For $x\geq 1$, $y\geq z\geq 3/2$,

$D(x,y,z)-1\ll\frac{x\log y}{\log xy\log z}.$

###### Proof.

If $x\geq z$, this follows from [8, Lemma 5]. If $x<z$ then $D(x,y,z)=1$. ∎

Define

(32) $E(x,y,z):=\frac{x\log y}{(\log xy)^{2}\log z}.$

######  Lemma 7.

For $x\geq 1$, $y\geq z\geq 3/2$,

$D(x,y,z)-1=\Phi(x,z)-\Phi(x,y)+O\left(E(x,y,z)\right)\\\
-x\sum_{z<n\leq\sqrt{x/y}}\frac{\chi(n)}{n}\left\\{\Pi(yn)+\frac{1}{\log
yn}\left(\omega\left(\frac{\log x/n}{\log
yn}\right)-e^{-\gamma}\right)\right\\}.$

###### Proof.

We use Lemma 2. The case $x\leq yz^{2}$ is trivial, since the sum in Lemma 2
vanishes. If $x>yz^{2}$, we use Lemma 3 to estimate each occurrence of
$\Phi(x/n,ny)-1$. The term $\frac{z\,\delta(x-z)}{\log z}$ contributes

$\sum_{z<n\leq\sqrt{x/y}}\chi(n)\frac{ny}{\log
ny}\ll\frac{\sqrt{xy}}{\log\sqrt{xy}}(D(\sqrt{x/y},y,z)-1)\ll E(x,y,z),$

by Lemma 6. For the contribution of the error term in Lemma 3, we can split
the interval $(z,\sqrt{x/y}]$ by powers of $2$ and use Lemma 6. This shows
that the error term in Lemma 3 contributes

$\begin{split}&\ll\sum_{z<n\leq\sqrt{x/y}}\chi(n)\frac{x}{n(\log
ny)^{2}}\exp\left(-\frac{\log xy}{3\log ny}\right)\\\
&\ll\sum_{z<n\leq\sqrt{x/y}}\frac{x\log y}{n(\log ny)^{3}\log
z}\exp\left(-\frac{\log xy}{6\log ny}\right)\ll E(x,y,z).\end{split}$

∎

######  Lemma 8.

For $y\geq z\geq 3/2$, we have $\displaystyle\Pi(z)=\sum_{n\geq
1}\frac{\chi(n)}{n}\Pi(yn).$

###### Proof.

Fix $y\geq z\geq 3/2$. In Lemma 7, use the estimate $\omega(t)-e^{-\gamma}\ll
e^{-t}$. The contribution from this error term can be estimated as in the
proof of Lemma 7. Use Lemma 6 for $D(x,y,z)-1$, divide the resulting equation
by $x$ and let $x\to\infty$. ∎

######  Lemma 9.

For $x\geq 1$, $y\geq z\geq 3/2$, we have

$D(x,y,z)-1=\frac{x(w(v)-e^{-\gamma})}{\log z}-\frac{x(w(u)-e^{-\gamma})}{\log
y}\\\ -x\sum_{n>z}\frac{\chi(n)}{n\log yn}\left(\omega\left(\frac{\log
x/n}{\log yn}\right)-e^{-\gamma}\right)\\\ +\frac{y\,\delta(x-y)}{\log
y}-\frac{z\,\delta(x-z)}{\log
z}+O\left(E(x,y,z)+\frac{xe^{-v/3}}{\log^{2}z}\right).$

###### Proof.

In Lemma 7, we use Mertens’ theorem to extend the sum to all $n>z$. This
changes the sum by $\ll E(x,y,z)$, since $\omega(t)=0$ when $t<1$. Approximate
$\Phi(x,z)$ and $\Phi(x,y)$ in Lemma 7 by Lemma 3. By Lemma 8, all terms with
Euler products cancel. The result now follows since $xe^{-u/3}/\log^{2}y\ll
E(x,y,z)$. ∎

######  Lemma 10.

For $x\geq 1$, $y\geq z\geq 3/2$, we have

(33) $D(x,y,z)-1=\frac{x\omega(v)}{\log z}-\frac{x\omega(u)}{\log y}\\\
+x\alpha_{y,z}-x\int_{1}^{x}\frac{D(t,y,z)-1}{t^{2}\log
ty}\,\omega\left(\frac{\log x/t}{\log ty}\right)\,\mathrm{d}t\\\
+\frac{y\,\delta(x-y)}{\log y}-\frac{z\,\delta(x-z)}{\log
z}+O\left(E(x,y,z)+\frac{xe^{-v/3}}{\log^{2}z}\right),$

where

$\alpha_{y,z}:=\frac{e^{-\gamma}}{\log y}-\frac{e^{-\gamma}}{\log
z}+e^{-\gamma}\int_{z}^{\infty}\frac{D(t,y,z)-1}{t^{2}\log ty}\,\mathrm{d}t.$

We have

(34) $\alpha_{y,z}=\Pi(z)-\frac{e^{-\gamma}}{\log z}+O\left(\frac{1}{\log
y\log z}\right).$

###### Proof.

Use partial summation on the sum in Lemma 9 to turn the sum over $n>z$ into an
integral $\int_{z}^{\infty}$. The two new error terms arising during partial
summation are found to be $\ll E(x,y,z)$, with the help of Lemma 6. After
separating the contribution from $e^{-\gamma}$ to the integral, we can change
the limits in the remaining integral from $\int_{z}^{\infty}$ to
$\int_{1}^{x}$, since $D(t,y,z)-1=0$ when $1\leq t\leq z$ and $\omega(t)=0$
for $t\leq 0$.

To see that (34) holds, put $x=y$ in (33) and use Lemma 3 to estimate
$D(x,x,z)-1=\Phi(x,z)-1$. The integral in (33) vanishes when $x=y$, since
$\omega(t)=0$ for $t<1$. ∎

###### Proof of Theorem 7.

For $x\geq 1$, $t\geq 1$, define $\lambda\geq 0$ and $\tau\geq 0$ by

$x=y^{e^{\lambda}-1},\quad t=y^{e^{\tau}-1}.$

Let

$H_{y,z}(\lambda):=\frac{D(y^{e^{\lambda}-1},y,z)-1}{y^{e^{\lambda}-1}}=\frac{D(x,y,z)-1}{x}\ll\frac{\log
y}{\log xy\log z},$

by Lemma 6. Let $G_{r}(\lambda)$ and $\Omega_{r}(\lambda)$ be as in (26) and
(27). Lemma 10 shows that for $\lambda\geq 0$ we have

$H_{y,z}(\lambda)=\frac{\Omega_{r}(\lambda)-r\Omega_{1}(\lambda)}{\log
z}+\alpha_{y,z}-\int_{0}^{\lambda}H_{y,z}(\tau)\Omega_{1}(\lambda-\tau)\,\mathrm{d}\tau+R_{y,z}(\lambda),$

where

$R_{y,z}(\lambda):=\frac{\delta\bigl{(}\lambda-\log
2\bigr{)}}{y^{e^{\lambda}-2}\log
y}-\frac{\delta\bigl{(}\lambda-\log(1+r)\bigr{)}}{y^{e^{\lambda}-(1+r)}\log
z}+O\left(\frac{e^{-2\lambda}}{\log y\log
z}+\frac{e^{-(e^{\lambda}-1)/(3r)}}{\log^{2}z}\right).$

Calculating Laplace transforms, we obtain, for $\mathrm{Re}(s)>0$,

$\widehat{H}_{y,z}(s)=\frac{\widehat{\Omega}_{r}(s)-r\widehat{\Omega}_{1}(s)}{\log
z}+\frac{\alpha_{y,z}}{s}-\widehat{H}_{y,z}(s)\widehat{\Omega}_{1}(s)+\widehat{R}_{y,z}(s).$

By Lemma 5 and (28),

$\widehat{H}_{y,z}(s)=\frac{\widehat{G}_{r}(s)}{\log
z}+\alpha_{y,z}\widehat{G}(s)+\widehat{R}_{y,z}(s)s\widehat{G}(s).$

From (29) and (30), we obtain

$\begin{split}H_{y,z}(\lambda)=\frac{G_{r}(\lambda)}{\log
z}+\alpha_{y,z}G(\lambda)+R_{y,z}+\int_{0}^{\lambda}R_{y,z}(\tau)\Bigl{(}-Ce^{-(\lambda-\tau)}+O\bigl{(}e^{-3(\lambda-\tau)}\bigr{)}\Bigr{)}\,\mathrm{d}\tau.\end{split}$

In the remainder of this proof we may assume $x\geq y\geq z\geq 3/2$. The last
integral equals

$\begin{split}&e^{-\lambda}\int_{0}^{\infty}-CR_{y,z}(\tau)e^{\tau}\,\mathrm{d}\tau+O\left(\int_{\lambda}^{\infty}|R_{y,z}(\tau)|e^{\tau-\lambda}\,\mathrm{d}\tau+\int_{0}^{\lambda}|R_{y,z}(\tau)|\,e^{3(\tau-\lambda)}\,\mathrm{d}\tau\right)\\\
&=:e^{-\lambda}\kappa_{y,z}\ +\ O\left(\frac{e^{-\lambda}}{\log x\log
z}\right),\end{split}$

where

$\kappa_{y,z}\ll\frac{1}{\log y\log z}.$

Hence

$\begin{split}D(x,y,z)=&\frac{x\,d(u,v)}{\log
z}+x\alpha_{y,z}d(u)+\frac{x\,\kappa_{y,z}}{u+1}+\frac{y}{\log
y}-\frac{z}{\log z}+O\left(E(x,y,z)\right).\end{split}$

From (34) we have

$\alpha_{y,z}=\Pi(z)-\frac{e^{-\gamma}}{\log
z}+\rho_{y,z},\quad\rho_{y,z}\ll\frac{1}{\log y\log z},$

and, by Mertens’ theorem,

$\varepsilon_{z}:=\alpha_{y,z}-\rho_{y,z}=\Pi(z)-\frac{e^{-\gamma}}{\log
z}\ll\frac{1}{\log^{2}z}.$

With the estimate (7), we can write

$x\alpha_{y,z}d(u)=x(\varepsilon_{z}+\rho_{y,z})d(u)=x\varepsilon_{z}d(u)+\frac{xC\rho_{y,z}}{u+1}+O(E(x,y,z)).$

Thus

$\begin{split}D(x,y,z)=&\frac{x\,d(u,v)}{\log
z}+x\varepsilon_{z}d(u)+\frac{x\,\mu_{y,z}}{u+1}+\frac{y}{\log
y}-\frac{z}{\log z}+O\left(E(x,y,z)\right),\end{split}$

where

$\mu_{y,z}:=\kappa_{y,z}+C\rho_{y,z}\ll\frac{1}{\log y\log z}.$

If $v\ll 1$, that is $\log z\gg\log x$, then the result follows from Mertens’
theorem. Assume $v$ is sufficiently large. Then the first estimate in Theorem
6 shows that, with $r=u/v$,

$\begin{split}x\varepsilon_{z}d(u)&=x\varepsilon_{z}d(u,v)e^{\gamma}\left(1+\frac{r}{1-r}\right)\left(1+O\left(\frac{1}{uv}\right)\right)\\\
&=x\varepsilon_{z}d(u,v)e^{\gamma}+\frac{rx\varepsilon_{z}d(u,v)e^{\gamma}}{1-r}+O\left(\frac{x\varepsilon_{z}d(u,v)}{(1-r)uv}\right).\end{split}$

Since $d(u,v)\ll\frac{1-r}{u+1}$, the last error term is $\ll E(x,y,z)$. The
second estimate in Theorem 6 yields

$\frac{rx\varepsilon_{z}d(u,v)e^{\gamma}}{1-r}=x\frac{\varepsilon_{z}Cr}{u+1}+O(E(x,y,z)).$

The estimate (9) now follows with

$\beta_{y,z}:=(\log y)(\mu_{y,z}+\varepsilon_{z}Cr)\ll\frac{1}{\log z}.$

It remains to prove the stronger upper bound (10). For fixed $y\geq z\geq
3/2$, (9) and Theorem 6 yield

(35) $D(x,y,z)=\frac{c_{y,z}x}{\log
xy}+O_{y,z}\left(\frac{x}{\log^{2}x}\right),$

where

(36) $c_{y,z}=C\Pi(z)\log(y/z)+\beta_{y,z}.$

With (35) and the method in [17], just like in the derivation of the formula
for $c_{y}=c_{y,1}$ in [17], we derive (14). With (8) and Lemma 8, we obtain
(15) and (16). Comparing (16) with (36) establishes (10). ∎

##  5\. Proof of Theorem 8

For $y\geq z\geq 1$, let $\Lambda(y,z)$ be the natural density of integers
whose smallest prime factor is in the interval $(z,y]$, that is

$\Lambda(y,z):=\Pi(z)-\Pi(y)=\sum_{z<p\leq
y}\frac{\Pi(p-1)}{p}\asymp\sum_{z<p\leq y}\frac{1}{p\log p}.$

We first establish the following corollary to Theorem 7.

######  Corollary 3.

For $x\geq y\geq z\geq 3/2$ we have

(37) $D(x,y,z)=1+\pi(y,z)+\frac{Cx\Lambda(y,z)\bigl{(}\log
y+\xi_{y,z}\bigr{)}}{\log xy}\left(1+O\left(\frac{1}{\log
x}+\frac{\log^{2}y}{\log^{2}x}\right)\right),$

where

$|\xi_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y),\quad\log y+\xi_{y,z}\asymp\log
y.$

###### Proof.

If the interval $(z,y]$ does not contain a prime, then $D(x,y,z)=1$ and
$\pi(y,z)=\Lambda(y,z)=0$, so (37) holds. Assume $\pi(y,z)\geq 1$, so that
$\Lambda(y,z)>0$.

We first consider the case $y\leq x^{1/4}$. As in (5), we write

$D(x,y,z)=1+\sum_{z<p\leq y}D(x/p,py,p-0)$

and apply Theorem 7 to estimate each occurrence of $D(x/p,py,p-0)$. Note that
$x/p\geq py$, since $p\leq y$ and $y\leq x^{1/4}$. The contribution from
$y/\log y-z/\log z$ in Theorem 7 is

$<\sum_{z<p\leq y}\frac{py}{\log py}\leq\sum_{z<p\leq y}\frac{p^{2}y}{p\log
p}\leq\sum_{z<p\leq y}\frac{y^{3}}{p\log p}\ll x^{3/4}\Lambda(y,z).$

The contribution from the term $x\beta_{y,z}/\log xy$ in Theorem 7 is

$=\frac{x}{\log xy}\sum_{z<p\leq y}\frac{\beta_{py,p-0}}{p}=\frac{x}{\log
xy}\cdot C\Lambda(y,z)\xi_{y,z},$

where we define

$\xi_{y,z}:=\frac{1}{C\Lambda(y,z)}\sum_{z<p\leq y}\frac{\beta_{py,p-0}}{p}.$

The estimate (10) yields $|\xi_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y)$. With
the second estimate for $d(u,v)$ in Theorem 6, the contribution from the term
$xd(u,v)e^{\gamma}\Pi(z)$ in Theorem 7 is

$\frac{Cx\Lambda(y,z)\log y}{\log
xy}\left(1+O\left(\frac{\log^{2}y}{\log^{2}x}\right)\right).$

The contribution from the error term in Theorem 7 is

$\ll\frac{x\Lambda(y,z)\log y}{\log^{2}x}.$

We have

$\frac{x\log y\Lambda(y,z)}{(\log x)^{2}}\gg\frac{x\log
y}{\log^{2}x}\cdot\frac{\pi(y,z)}{y\log y}\gg\pi(y,z)\gg 1+\pi(y,z).$

The result now follows if $y>y_{0}$, since $\log y+\xi_{y,z}=\log
y+O(1)\asymp\log y$. If $y\leq y_{0}$, we also have $\log
y+\xi_{y,z}\asymp\log y$, since the preceding shows that

$D(x,y,z)=O\left(\frac{x}{\log^{2}x}\right)+\frac{Cx\Lambda(y,z)\bigl{(}\log
y+\xi_{y,z}\bigr{)}}{\log xy},$

and $D(x,y,z)\asymp_{y,z}\frac{x}{\log x}$ when $\frac{3}{2}\leq z\leq y\leq
y_{0}$ and $\pi(y,z)\geq 1$, by [5, Lemma 3]. This concludes the proof of the
case $y\leq x^{1/4}$.

If $y>x^{1/4}$, we use the estimate

$D(x,y,z)-1\leq\Phi(x,z)-1\ll\frac{x}{\log z}\qquad(x\geq 1,y\geq 1,z>1),$

which imples

$D(x,y,z)-1-\pi(y,z)=\sum_{z<p\leq y}(D(x/p,py,p-0)-1)\ll\sum_{z<p\leq
y}\frac{x}{p\log p}\asymp x\Lambda(y,z).$

The result now follows since $\log x\asymp\log y$ in this case. ∎

When $y\ll x/\log x$, the term $\pi(y,z)$ is absorbed by the error terms.

######  Corollary 4.

For $x\geq y\geq z\geq 3/2$ and $y\ll\frac{x}{\log x}$ we have

$D(x,y,z)=1+\frac{Cx\Lambda(y,z)\bigl{(}\log y+\xi_{y,z}\bigr{)}}{\log
xy}\left(1+O\left(\frac{1}{\log x}+\frac{\log^{2}y}{\log^{2}x}\right)\right),$

where

$|\xi_{y,z}|\leq\mathcal{E}(z)+\mathcal{E}(y),\quad\log y+\xi_{y,z}\asymp\log
y.$

###### Proof.

When $y\leq x^{1/4}$, the proof of Corollary 3 shows that $\pi(y,z)$ is
absorbed by the first error term. If $x^{1/4}<y\ll\frac{x}{\log x}$, we have

$\pi(y,z)\ll x\frac{\pi(y,z)}{y\log y}\leq x\sum_{z<p\leq y}\frac{1}{p\log
p}\ll x\Lambda(y,z)$

and the result follows from Corollary 3. ∎

###### Proof of Theorem 8.

For $y\geq z\geq 3/2$ fixed and $x\to\infty$, comparing (35) and Corollary 4
shows that

$c_{y,z}=C\Lambda(y,z)(\log y+\xi_{y,z}).$

The first estimate in Theorem 8 is Corollary 4 and the second one is Corollary
3. The formula for $c_{y,z}$ in (14) and the estimates (15) and (16) were
established in the proof of Theorem 7, while (17) and (18) follow from the
estimates for $\xi_{y,z}$ in Corollary 4. The numerical values of $c_{y,z}$ in
Table 1 are calculated as in [17]. ∎

##  6\. Proof of Theorems 9 and 10

Here we write $\chi_{y,z}(n)$ for the characteristic function of the set
$\mathcal{D}$ in (11).

######  Lemma 11.

Let $f:[1,\infty)\to\mathbb{C}$ be integrable. For $x\geq 1$, $y\geq 1$,
$z\geq 1$, we have

(38) $\int_{1}^{x}\sum_{n\leq
x/t}\chi_{yt,z}(n)f(nyt)\frac{dt}{t}=\int_{1}^{x}A(t,y,z)f(yt)\frac{dt}{t}.$

If $f(t)\ll 1/(t\log 2t)$, then

(39) $\int_{1}^{\infty}\sum_{n\geq
1}\chi_{yt,z}(n)f(nyt)\frac{dt}{t}=\int_{1}^{\infty}A(t,y,z)f(yt)\frac{dt}{t}.$

###### Proof.

We have

$\begin{split}\int_{1}^{x}\sum_{n\leq
x/t}\chi_{yt,z}(n)f(nyt)\frac{dt}{t}&=\sum_{n\leq x\atop{F(n)\leq xy\atop
P^{-}(n)>z}}\int_{\max(1,F(n)/ny)}^{x/n}f(nyt)\frac{dt}{t}\\\ &=\sum_{n\leq
x\atop{F(n)\leq xy\atop
P^{-}(n)>z}}\int_{\max(n,F(n)/y)}^{x}f(yt)\frac{dt}{t}\\\
&=\int_{1}^{x}\sum_{n\leq t\atop{F(n)\leq yt\atop
P^{-}(n)>z}}f(yt)\frac{dt}{t}=\int_{1}^{x}A(t,y,z)f(yt)\frac{dt}{t},\end{split}$

which establishes (38). If $f(t)\ll 1/(t\log 2t)$, then
$\lim_{x\to\infty}\int_{1}^{x}A(t,y,z)f(yt)\frac{dt}{t}$ exists, since
$A(t,y,z)\leq A(yt)\ll yt/\log 2yt$. Lemma 6 and partial summation yield

$\sum_{n>x/t}\chi_{yt,z}(n)f(nyt)\ll\frac{\log yt}{yt\log xy},$

so that

$\int_{1}^{x}\sum_{n\leq
x/t}\chi_{yt,z}(n)f(nyt)\frac{dt}{t}=\int_{1}^{x}\sum_{n\geq
1}\chi_{yt,z}(n)f(nyt)\frac{dt}{t}+O\left(\frac{1}{\log xy}\right).$

Equation (39) now follows from (38) by taking the limit as $x\to\infty$. ∎

######  Corollary 5.

For $y\geq z$, we have

$\int_{1}^{\infty}A(t,y,z)\Pi(yt)\frac{dt}{t^{2}}=y\int_{y}^{\infty}A(t/y,y,z)\Pi(t)\frac{dt}{t^{2}}=\Pi(z).$

###### Proof.

The first and second expression are equal by a change of variables. That the
first expression equals $\Pi(z)$ follows from (39) with
$f(t)=\frac{1}{t}\Pi(t)$ and Lemma 8 with $y$ replaced by $yt$, i.e.
$\sum_{n\geq 1}\frac{\chi_{yt,z}(n)}{n}\Pi(nyt)=\Pi(z).$ ∎

###### Proof of Theorems 9 and 10.

Assume $x\geq y\geq z\geq 3/2$. We write $n=mpr$, where $F(n)=p^{2}r$,
$F(m)\leq p$, $F(r)\leq p^{2}r$ and $P^{-}(r)\geq p$. Sorting the integers $n$
in $\mathcal{A}(x,y,z)\setminus\mathcal{D}(x,y,z)$ according to $p$, we have

$(A-D)(x,y,z)=\sum_{z<p\leq\sqrt{xy}}\sum_{{m<p/y\atop F(m)\leq p}\atop
P^{-}(m)>z}\sum_{{r\leq xy/p^{2}\atop F(r)\leq p^{2}r}\atop P^{-}(r)\geq
p}1=\sum_{y<p\leq\sqrt{xy}}A^{\prime}(p/y,y,z)D(xy/p^{2},p^{2},p-1),$

where, for $x>1$, $y\geq z\geq 3/2$,

(40) $A^{\prime}(x,y,z):=|\\{n<x:F(n)\leq xy,\
P^{-}(n)>z\\}|=1+O\left(\frac{x\log y}{\log xy\log z}\right),$

by Lemma 5 of [8], if $x\geq z$. When $z>x$, then $A^{\prime}(x,y,z)=1$. Let
$M:=\max(y,(xy)^{1/5})$. With $E(x,y,z)$ as in (32), the contribution from
primes $p>M$ to $A(x,y,z)-D(x,y,z)$ is, by Lemma 6,

$\sum_{M<p\leq\sqrt{xy}}\left(1+O\left(\frac{p\log y}{y\log p\log
z}\right)\right)\left(1+O\left(\frac{xy}{p^{2}\log
xy}\right)\right)=\pi(\sqrt{xy},M)+O(E(x,y,z)).$

The contribution from the term $1$ in the estimate (12) and from primes $p\leq
M$ is

$\sum_{y<p\leq M}A^{\prime}(p/y,y,z)=\sum_{y<p\leq
M}\left(1+O\left(\frac{p\log y}{y\log p\log
z}\right)\right)=\pi(M,y)+O(E(x,y,z)).$

With (12) we obtain

$A(x,y,z)-D(x,y,z)=\pi(\sqrt{xy},y)+\sum_{y<p\leq
M}A^{\prime}(p/y,y,z)\frac{c_{p^{2},p-1}xy}{p^{2}\log xy}+O(E(x,y,z)).$

Since $c_{p^{2},p-1}\asymp 1$, extending the last sum to all $p>y$ adds $\ll
E(x,y,z)$. Thus

$A(x,y,z)-D(x,y,z)=\pi(\sqrt{xy},y)+\frac{\alpha_{y,z}x}{\log
xy}+O(E(x,y,z)),$

where

$\alpha_{y,z}:=\sum_{p>y}A^{\prime}(p/y,y,z)\frac{c_{p^{2},p-1}y}{p^{2}}\ll\frac{1}{\log
z}.$

The estimate (19) now follows from Theorem 7 with
$\tau_{y,z}=\beta_{y,z}+\alpha_{y,z}$. We will establish (20) below.

Define $a_{y,z}:=\alpha_{y,z}+c_{y,z}$. Together with (13) we conclude that,
for $x\geq y\geq z\geq 3/2$,

(41) $A(x,y,z)=1+\pi(\sqrt{xy},z)+\frac{a_{y,z}x}{\log
xy}+O\left(E(x,y,z)+\frac{x\log(1+y/z)\log^{2}y}{\log^{3}xy\log z}\right).$

We have $a_{y,z}\asymp\frac{\log(1+y/z)}{\log z}$, which is (25), to be
established below as a consequence of (41). This implies that, for $x\geq 1$,
$y\geq z\geq 3/2$,

(42)
$A(x,y,z)=1+\min(\pi(x,z),\pi(\sqrt{xy},z))+O\left(\frac{x\log(1+y/z)}{\log
xy\log z}\right).$

Note that (21) is implied by (42) if $y>x^{1/10}$, say. Thus we may assume
$y\leq x^{1/10}$. Repeating the above argument with (42) in place of (40), and
assuming $y\leq x^{1/10}$, we find that

$A(x,y,z)=1+\pi(\sqrt{xy},z)+\frac{a_{y,z}x}{\log
xy}+O\left(\frac{x\log(1+y/z)}{\log^{2}xy\log
z}+\frac{x\log(1+y/z)\log^{2}y}{\log^{3}xy\log z}\right),$

which yields (21), assuming (25), which will be established below from (41).

When $1\leq y\leq z\leq x$, the result follows since in that case
$A(x,y,z)=A(xy/z,z,z)$ and $a_{y,z}=a_{z,z}y/z$.

The estimate (41) clearly implies that for $y\geq z$ fixed and $x\to\infty$,

$\int_{1}^{x}A(t,y,z)\frac{dt}{t}\sim\frac{a_{y,z}x}{\log
x}\quad(x\to\infty).$

On the other hand, Lemma 11 with $f(t)=1$ yields

$\int_{1}^{x}A(t,y,z)\frac{dt}{t}=\int_{1}^{x}D(x/t,yt,z)\frac{dt}{t}.$

With the estimate (12), we find that the last integral is

$\frac{x}{\log
x}\int_{1}^{\infty}c_{yt,z}\frac{dt}{t^{2}}+O_{y,z}\left(\frac{x}{\log^{2}x}\right).$

Thus, for $y\geq z$,

(43) $a_{y,z}=\int_{1}^{\infty}c_{yt,z}\,\frac{dt}{t^{2}}.$

To show (22), we substitute (14) into (43) to get

$a_{y,z}=C\int_{1}^{\infty}\sum_{n\geq
1}\frac{\chi_{yt,z}(n)}{n}\bigl{(}\Sigma(nyt)-\Sigma(z)-\log
n\bigr{)}\Pi(nyt)\frac{dt}{t^{2}}.$

Now replace $\Sigma(nyt)-\Sigma(z)-\log n$ by
$(\Sigma(nyt)+\gamma-\log(nyt))+(\log(yt)-\gamma-\Sigma(z))$, and observe that

$\int_{1}^{\infty}\sum_{n\geq 1}\frac{\chi_{yt,z}(n)}{n}(\log
yt-\gamma-\Sigma(z))\Pi(nyt)\frac{dt}{t^{2}}\\\ =\Pi(z)\int_{1}^{\infty}(\log
yt-\gamma-\Sigma(z))\,\frac{dt}{t^{2}}=\Pi(z)(1+\log y-\gamma-\Sigma(z)),$

since $\sum_{n\geq 1}\frac{\chi_{yt,z}(n)}{n}\Pi(nyt)=\Pi(z),$ by Lemma 8.
Thus,

$a_{y,z}=C\Pi(z)(1+\log y-\gamma-\Sigma(z))+C\int_{1}^{\infty}\sum_{n\geq
1}\frac{\chi_{yt,z}(n)}{n}g(nyt)\frac{dt}{t^{2}}.$

By Lemma 11, with $f(u)=\frac{g(u)}{u}$, the last integral equals

$\int_{1}^{\infty}A(t,y,z)g(yt)\frac{dt}{t^{2}}.$

This concludes the proof of (22).

The estimates (23) and (24) follow from (22), Corollary 5 and (8).

The estimate (25) follows from (22) and the fact that, for $t\geq 1$,

$-0.12<\gamma-\log 2<\Sigma(t)+\gamma-\log t\leq\Sigma(3)+\gamma-\log 3<0.73.$

Indeed, from (22) we have

$\frac{a_{y,z}}{C\Pi(z)}=1+\log(y/z)-(\Sigma(z)+\gamma-\log
z)+\frac{1}{\Pi(z)}\int_{1}^{\infty}A(t,y,z)g(yt)\frac{dt}{t^{2}}.$

The bounds on $\Sigma(t)+\gamma-\log t$ imply that

$1+\log(y/z)-0.73-0.12<\frac{a_{y,z}}{C\Pi(z)}<1+\log(y/z)+0.12+0.73.$

Thus, for $y\geq z\geq 1$,

$C\Pi(z)(0.15+\log(y/z))<a_{y,z}<C\Pi(z)(1.85+\log(y/z)).$

When $y<z$, (25) follows from $a_{y,z}=a_{z,z}y/z$.

To deduce a relationship between $\tau_{y,z}$ and $a_{y,z}$, we equate the
estimates for $A(x,y,z)$ of Theorems 9 and 10, and use Theorem 6 to estimate
$d(u,v)$. This shows that $C\Pi(z)\log(y/z)+\tau_{y,z}=a_{y,z}$. The estimate
(20) now follows from (24). ∎

##  7\. An algorithm for computing $a_{y,z}$

Since $a_{y,z}=a_{z,z}y/z$ if $y<z$, we may assume $y\geq z\geq 1$. To
estimate the tail of the integral in (22), we write

$\Biggl{|}\int_{N}^{\infty}A(t,y,z)g(yt)\frac{dt}{t^{2}}\Biggr{|}\leq\mathcal{E}(yN)\,\varepsilon(N),$

where $\mathcal{E}(x)$ is as in (8) and

$\varepsilon(N)=\int_{N}^{\infty}A(t,y,z)\Pi(yt)\frac{dt}{t^{2}}=\Pi(z)-\int_{1}^{N}A(t,y,z)\Pi(yt)\frac{dt}{t^{2}},$

by Corollary 5. The last expression allows us to find $\varepsilon(N)$ on a
computer. Let

$J(N)=\int_{1}^{N}A(t,y,z)g(yt)\frac{dt}{t^{2}},$

which we can also find on a computer. Thus

$a_{y,z}=C\Pi(z)(1-\gamma+\log y-\Sigma(z))+C(J(N)+R(N)),$

where $|R(N)|\leq\mathcal{E}(yN)\,\varepsilon(N).$ For a table with values of
$\mathcal{E}(2^{k})$ for $24\leq k\leq 38$, see [18, Lemma 4]. With $N=2^{33}$
and $y=z=1$, we find that $a=a_{1,1}=1.53796...$

##  8\. Proof of Theorem 2

De la Vallée Poussin [1] showed that $\sum_{p\leq
x}\\{\frac{x}{p}\\}=(1-\gamma+o(1))\frac{x}{\log x}$. His proof can easily be
adapted to obtain an explicit error term.

######  Lemma 12.

For $x\geq 2$, we have

$\sum_{p\leq x}\left\\{\frac{x}{p}\right\\}=(1-\gamma)\frac{x}{\log
x}+O\left(\frac{x}{(\log x)^{2}}\right).$

######  Lemma 13.

For every prime $p$,

$|\\{n\in\mathcal{B}(x):P^{-}(n)=p\\}|=A(x/p,p,p)\qquad(x\geq p).$

###### Proof.

For $x\geq p$,

$p\mathcal{A}(x/p,p,p-1)=\\{n\in\mathcal{A}(x):P^{-}(n)=p\\}\cup\\{n\in\mathcal{B}(x):P^{-}(n)=p\\}.$

Thus,

$|\\{n\in\mathcal{B}(x):P^{-}(n)=p\\}|=A(x/p,p,p-1)-|\\{n\in\mathcal{A}(x):P^{-}(n)=p\\}|\\\
=A(x/p,p,p).$

∎

Since $\lfloor
x\rfloor=A(x)+\sum_{n\in\mathcal{B}(x)}\left\lfloor\frac{x}{n}\right\rfloor,$
Theorem 2 follows from Theorems 1 and 11.

######  Theorem 11.

For $x\geq 2$, we have

$\sum_{n\in\mathcal{B}(x)}\left\\{\frac{x}{n}\right\\}=\frac{(1-\gamma+\beta)x}{\log
x}+O\left(\frac{x}{(\log x)^{3/2}}\right),$

where

(44) $\beta=\sum_{p\geq 2}\beta_{p}:=\sum_{p\geq
2}\left(\int_{p}^{p^{2}}\frac{a_{y,p-1}}{yp}dy-\sum_{2\leq k\leq
p}\frac{a_{kp,p-1}}{kp}\right)=0.554...$

and $\beta_{p}\ll\frac{1}{p\log p}$. More precisely,
$0.554604<\beta<0.554806$.

###### Proof.

We write

$\sum_{n\in\mathcal{B}(x)}\left\\{\frac{x}{n}\right\\}=\sum_{p\geq
2}\sum_{n\in\mathcal{B}(x)\atop
P^{-}(n)=p}\left\\{\frac{x}{n}\right\\}=S_{1}+S_{2}+S_{3},$

where

$S_{3}:=\sum_{\sqrt{x}<p\leq
x}\left\\{\frac{x}{p}\right\\}=(1-\gamma)\frac{x}{\log
x}+O\left(\frac{x}{(\log x)^{2}}\right),$

by Lemma 12. With the trivial estimate $\\{x/n\\}<1$ and Lemma 13, we have

(45) $S_{2}:=\sum_{U<p\leq\sqrt{x}}\sum_{n\in\mathcal{B}(x)\atop
P^{-}(n)=p}\left\\{\frac{x}{n}\right\\}\leq\sum_{U<p\leq\sqrt{x}}A(x/p,p,p)\ll\frac{x}{(\log
x)(\log U)},$

since (42) implies

$A(x/p,p,p)\ll\pi(\sqrt{x})+\frac{x}{p(\log p)(\log x)}.$

It remains to estimate

$S_{1}:=\sum_{p\leq U}\sum_{n\in\mathcal{B}(x)\atop
P^{-}(n)=p}\left\\{\frac{x}{n}\right\\}=\sum_{p\leq U}\sum_{1\leq
k<p}\sum_{\frac{x}{(k+1)p}<m\leq\frac{x}{kp}\atop F(m)\leq x,\ P^{-}(m)\geq
p}\left(\frac{x}{mp}-k\right).$

The innermost sum equals

$-\int_{kp}^{(k+1)p}\left(\frac{y}{p}-k\right)dA(x/y,y,p-1)\\\
=-A(x/y,y,p-1)\left(\frac{y}{p}-k\right)\Bigl{|}_{kp}^{(k+1)p}+\frac{1}{p}\int_{kp}^{(k+1)p}A(x/y,y,p-1)dy,$

as a result of integration by parts. Theorem 10 yields

(46) $A(x/y,y,p-1)=\frac{a_{y,p-1}x}{y\log
x}+O\left(\frac{x\log(1+\frac{y}{p})}{y(\log x)^{2}\log p}+\frac{x\log
y\log(1+\frac{y}{p})}{y(\log x)^{3}}\right),$

for $p\leq y\leq p^{2}\leq x^{1/3}$. We find that the last sum over $m$ equals

$\frac{\beta_{p,k}x}{\log x}+O\left(\frac{x\log(k+1)}{p(\log p)k(\log
x)^{2}}+\frac{x\log p\log(k+1)}{pk(\log x)^{3}}\right),$

where

$\beta_{p,k}:=\int_{kp}^{(k+1)p}\frac{a_{y,p-1}}{yp}dy-\frac{a_{(k+1)p,p-1}}{(k+1)p},$

provided $U\leq x^{1/6}$. Note that $\beta_{p}:=\sum_{1\leq
k<p}\beta_{p,k}\ll\frac{1}{p\log p}$ for each prime $p$, as the two innermost
sums in the definition of $S_{1}$ amount to $<A(x/p,p,p)$, by the trivial
estimate $\\{x/n\\}<1$, as in the case of $S_{2}$. Summing over $1\leq k<p$
and then over $p\leq U$, the contribution from the error term is

$\ll\frac{x\log U}{(\log x)^{2}}+\frac{x(\log U)^{3}}{(\log x)^{3}},$

while the main term contributes

$\frac{\beta x}{\log x}+O\left(\sum_{p>U}\frac{\beta_{p}x}{\log
x}\right)=\frac{\beta x}{\log x}+O\left(\frac{x}{(\log x)(\log U)}\right).$

The result now follows with $\log U=\sqrt{\log x}$.

The numerical calculation of $\beta$ is based on formulas (44) and (22),
following the ideas of Section 7. ∎

##  9\. Proof of Theorem 3

To derive Theorem 3 from Theorem 2, we will need the following estimate.

######  Proposition 1.

Let $q\geq 1$ be a fixed integer. For $x\geq 2$, we have

$\sum_{n\in\mathcal{B}(x)\atop\frac{x}{q+1}<n\leq\frac{x}{q}}\frac{1}{n}=\frac{\mu_{q}}{\log
x}+O_{q}\left(\frac{1}{\log^{2}x}\right),$

where

(47)
$\mu_{q}=\log(1+1/q)+\sum_{p>q}\frac{1}{p}\left(a_{qp,p-1}-a_{(q+1)p,p-1}+\int_{qp}^{(q+1)p}a_{y,p-1}\frac{dy}{y}\right).$

We have $0.401720<\mu_{5}<0.401815$ and $0.197932<\mu_{11}<0.197989$.

We first show how Theorem 3 follows from Proposition 1 and Theorem 2.

###### Proof of Theorem 3.

Let $\mathcal{B}^{\prime}(x)$ be the set obtained from $\mathcal{B}(x)$, by
replacing every $n\in(\frac{x}{6},\frac{x}{5}]\cap\mathcal{B}(x)$ by
$\\{2n,3n,5n\\}$, and every
$n\in(\frac{x}{12},\frac{x}{11}]\cap\mathcal{B}(x)$ by
$\\{3n,4n,5n,7n,11n\\}$. Let $n_{1}\in(x/6,x/5]\cap\mathcal{B}(x)$,
$m_{1}\in\\{2,3,5\\}$, $n_{2}\in(x/12,x/11]\cap\mathcal{B}(x)$ and
$m_{2}\in\\{3,4,5,7,11\\}$. Then, $m_{i}n_{i}\notin\mathcal{B}(x)$ for
$i=1,2$. Also $n_{1}m_{1}\not=n_{2}m_{2}$. Indeed, if $n_{1}m_{1}=n_{2}m_{2}$
then $m_{2}>m_{1}$ and $m_{1}|m_{2}n_{2}$. If $(m_{1},m_{2})=(2,4)$ then
$2|n_{1}$, otherwise $m_{1}|n_{2}$. Either of these is impossible since
$n_{i}P^{-}(n_{i})>x$ implies $P^{-}(n_{1})>5$ and $P^{-}(n_{2})>11$.

Since $\mathcal{B}(x)$ has the $\operatorname{lcm}$ property (1), so does
$\mathcal{B}^{\prime}(x)$. Theorem 2 and Proposition 1 yield

$\sum_{n\in\mathcal{B}^{\prime}(x)}\frac{1}{n}=\sum_{n\in\mathcal{B}(x)}\frac{1}{n}+\frac{1}{30}\sum_{n\in\mathcal{B}(x)\atop\frac{x}{6}<n\leq\frac{x}{5}}\frac{1}{n}+\frac{79}{4620}\sum_{n\in\mathcal{B}(x)\atop\frac{x}{12}<n\leq\frac{x}{11}}\frac{1}{n}=1-\frac{\kappa}{\log
x}+O\left(\frac{1}{(\log x)^{3/2}}\right),$

where

(48) $\kappa=\delta-\mu_{5}\frac{1}{30}-\mu_{11}\frac{79}{4620}=0.543...$

More precisely, $0.543595<\kappa<0.543804$. ∎

###### Proof of Proposition 1.

This proof is similar to that of Theorem 11. Let $q\geq 1$ be a fixed integer.
Since $nP^{-}(n)>x$ for all $n\in\mathcal{B}(x)$,
$n\in\mathcal{B}(x)\cap(x/(q+1),x/q]$ implies $P^{-}(n)>q$. We write

$\sum_{n\in\mathcal{B}(x)\atop\frac{x}{q+1}<n\leq\frac{x}{q}}\frac{1}{n}=\sum_{p>q}\sum_{{n\in\mathcal{B}(x)\atop
P^{-}(n)=p}\atop\frac{x}{q+1}<n\leq\frac{x}{q}}\frac{1}{n}=S_{1}+S_{2}+S_{3},$

where

$S_{3}:=\sum_{\frac{x}{q+1}<p\leq\frac{x}{q}}\frac{1}{p}=\frac{\log(1+1/q)}{\log
x}+O\left(\frac{1}{(\log x)^{2}}\right),$

by the prime number theorem. With Lemma 13, we have

$S_{2}:=\sum_{U<p\leq\sqrt{x}}\sum_{{n\in\mathcal{B}(x)\atop
P^{-}(n)=p}\atop\frac{x}{q+1}<n\leq\frac{x}{q}}\frac{1}{n}\leq\sum_{U<p\leq\sqrt{x}}\frac{q+1}{x}A(x/p,p,p)\ll\frac{q+1}{(\log
x)(\log U)},$

as in (45). It remains to estimate

$S_{1}:=\sum_{q<p\leq U}\sum_{{n\in\mathcal{B}(x)\atop
P^{-}(n)=p}\atop\frac{x}{q+1}<n\leq\frac{x}{q}}\frac{1}{n}=\sum_{q<p\leq
U}\sum_{\frac{x}{(q+1)p}<m\leq\frac{x}{qp}\atop F(m)\leq x,\ P^{-}(m)\geq
p}\frac{1}{pm}$

The innermost sum equals

$-\int_{qp}^{(q+1)p}\frac{y}{px}dA(x/y,y,p-1)\\\
=-\frac{y}{px}A(x/y,y,p-1)\Bigl{|}_{qp}^{(q+1)p}+\frac{1}{px}\int_{qp}^{(q+1)p}A(x/y,y,p-1)dy,$

as a result of integration by parts. By (46), this equals

$\frac{\mu_{q,p}}{\log x}+O_{q}\left(\frac{1}{p(\log p)(\log
x)^{2}}+\frac{\log p}{p(\log x)^{3}}\right),$

where

$\mu_{q,p}:=\frac{1}{p}\left(a_{qp,p-1}-a_{(q+1)p,p-1}+\int_{qp}^{(q+1)p}\frac{a_{y,p-1}}{y}dy\right),$

provided $U\leq x^{1/6}$. Note that $\mu_{q,p}\ll_{q}\frac{1}{p\log p}$ for
each prime $p$, as the innermost sum in the definition of $S_{1}$ amounts to
$<\frac{(q+1)}{x}A(x/p,p,p)$, as in the case of $S_{2}$. Summing over primes
$p$ with $q<p\leq U$, the contribution from the error term is

$\ll_{q}\frac{1}{(\log x)^{2}}+\frac{\log U}{(\log x)^{3}},$

while the main term contributes

$\frac{\mu_{q}-\log(1+1/q)}{\log x}+O_{q}\left(\sum_{p>U}\frac{\mu_{q,p}}{\log
x}\right)=\frac{\mu_{q}-\log(1+1/q)}{\log x}+O_{q}\left(\frac{1}{(\log x)(\log
U)}\right).$

The result now follows with $U=x^{1/6}$.

The numerical calculation of $\mu_{q}$ is based on formulas (47) and (22),
following the ideas of Section 7. ∎

##  10\. Proof of Theorems 4 and 5

###### Proof of Theorem 4.

Let $\tau<1$. It is easy to see that each $n\leq x$ is either a multiple of a
member of $\mathcal{B}_{\tau}(x)$, or a member of $\mathcal{A}(\tau x)$, but
not both. We write

$\sum_{n\in\mathcal{B}_{\tau}(x)}\frac{1}{n}=\sum_{n\in\mathcal{B}(\tau
x)}\frac{1}{n}+\sum_{\tau x<p\leq x}\frac{1}{p}=S_{1}+S_{2},$

say. Note that $\tau\in\mathcal{T}(x)$ implies $\tau x\to\infty$, or else
$S_{2}>1$. Thus $S_{1}\sim 1$, by Theorem 2. It follows that $S_{2}=o(1)$ and
$\log\tau=o(\log x)$. By Theorem 2 and the prime number theorem,

$\sum_{n\in\mathcal{B}_{\tau}(x)}\frac{1}{n}=1-\frac{\delta}{\log\tau
x}+\frac{\log 1/\tau}{\log x}+O\left(\frac{1}{(\log
x)^{3/2}}+\frac{\log^{2}1/\tau}{\log^{2}x}\right).$

This implies that

$\tau_{0}(x):=\min\mathcal{T}(x)=e^{-\delta}+O(1/\sqrt{\log x})$

and, by Theorem 1,

$H^{*}(x)=A(x\tau_{0}(x))=\frac{ae^{-\delta}x}{\log x}+O\left(\frac{x}{(\log
x)^{3/2}}\right).$

∎

###### Proof of Theorem 5.

As in the proof of Theorem 4, we find that, for fixed $\mu$, we have
$\tau_{0}(x,\mu):=\min\mathcal{T}(x,1+\mu/\log
x)=e^{-\delta-\mu}+O(1/\sqrt{\log x})$.

For the second claim we follow the proof of Ruzsa [6, Thm. I]. For the upper
bound we use again $H(x,z)\leq H^{*}(x,z)$. Since $S_{2}\leq z\leq Z$, any
$\tau\in\mathcal{T}(x,z)$ must satisfy $x\tau\geq x^{\eta}$ for a suitable
$\eta>0$ depending on $Z$ only. Thus $S_{1}=1+O(1/\log x)$ and we want to
choose $\tau$ as small as possible such that $S_{2}\leq z-S_{1}$, that is

$S_{2}=\log\frac{\log x}{\log x\tau}+O(1/\log x)\leq z-1+O(1/\log x).$

Denoting this value of $\tau$ by $\tau_{0}$, it follows that $x\tau_{0}\asymp
x^{e^{1-z}}$ and

$H(x,z)\leq A(x\tau_{0})\ll\frac{x\tau_{0}}{\log
x\tau_{0}}\asymp\frac{x^{e^{1-z}}}{\log x}.$

For the lower bound, we let $y:=H(x,z)\log x$ and we may assume that $y<x$, or
else there is nothing to prove. Let $\mathcal{S}$ be the optimal set in the
definition of $H(x,z)$. The primes in $(y,x]$ must belong to $\mathcal{S}$,
with at most $y/\log x$ exceptions. Thus

$\sum_{n\in\mathcal{S}\atop n>y}\frac{1}{n}\geq\sum_{y<p\leq
x}\frac{1}{p}-\frac{y}{\log x}\cdot\frac{1}{y}=\log\frac{\log x}{\log
y}+O\left(\frac{1}{\log x}\right).$

As before, we must have $y\geq x^{\eta}$ for a suitable $\eta>0$, or else the
last sum is too large. Let $U(y,\mathcal{S}):=|\\{n\leq
y:s\in\mathcal{S}\Rightarrow s\nmid n\\}|.$ Then
$U(y,\mathcal{S})+\sum_{n\in\mathcal{S}}\lfloor y/n\rfloor\geq\lfloor
y\rfloor$. Thus

$\sum_{n\in\mathcal{S}\atop n\leq y}\frac{1}{n}\geq
1-\frac{1+U(y,\mathcal{S})}{y}\geq 1-\frac{1+H(x,z)}{y}\geq
1-O\left(\frac{1}{\log x}\right).$

Thus,

$z\geq\sum_{n\in\mathcal{S}}\frac{1}{n}\geq 1+\log\frac{\log x}{\log
y}+O\left(\frac{1}{\log x}\right),$

that is $y\gg x^{e^{1-z}},$ which is the desired lower bound. ∎

## References

  * [1] C. de la Vallée Poussin, Sur les valeurs moyennes de certaines fonctions arithmétiques, Annales de la société scientifique de Bruxelles 22 (1898) 84–90.
  * [2] R. S. Lehman, Amer. Math. Monthly, 58 (1951), p. 345, problem 4365.
  * [3] A. D. Pollington, There is a long path in the divisor graph, Ars Combin. 16-B (1983), 303–304.
  * [4] C. Pomerance, On the longest simple path in the divisor graph, Congr. Numer. 40 (1983), 291–304.
  * [5] C. Pomerance and A. Weingartner, On primes and practical numbers, Ramanujan J. 57 (2022), no. 3, 981–1000.
  * [6] I. Z. Ruzsa, On the small sieve II. Sifting by composite numbers, J. Number Theory 14 (1982), 260–268.
  * [7] E. Saias, Entiers à diviseurs denses 1, J. Number Theory 62 (1997), 163–191.
  * [8] E. Saias, Applications des entiers à diviseurs denses, Acta Arith. 83 (1998), 225–240.
  * [9] E. Saias, Entiers à diviseurs denses 2, J. Number Theory 86 (2001), 39–49.
  * [10] E. Saias, Etude du graphe divisoriel 5, preprint arxiv:2107.03855
  * [11] A. Schinzel and G. Szekeres, Sur un problème de M. Paul Erdős, Acta Sci. Math.(Szeged) 20 (1959), 221–229.
  * [12] G. Tenenbaum, Sur un problème de crible et ses applications, Ann. Sci. École Norm. Sup. (4) 19 (1986), 1–30.
  * [13] G. Tenenbaum, Sur un problème de crible et ses applications, 2. Corrigendum et étude du graphe divisoriel. Ann. Sci. École Norm. Sup. (4) 28 (1995), 115–127.
  * [14] A. Weingartner, Integers with dense divisors, J. Number Theory 108 (2004), 1–17.
  * [15] A. Weingartner, Integers with dense divisors 3, J. Number Theory 142 (2014), 211–222.
  * [16] A. Weingartner, Practical numbers and the distribution of divisors, Q. J. Math. 66 (2015), no. 2, 743–758.
  * [17] A. Weingartner, On the constant factor in several related asymptotic estimates, Math. Comp. 88 (2019), no. 318, 1883–1902.
  * [18] A. Weingartner, The constant factor in the asymptotic for practical numbers, Int. J. Number Theory 16 (2020), no. 3, 629–638.
  * [19] A. Weingartner, The number of prime factors of integers with dense divisors, J. Number Theory 239 (2022), 57–77.


# Dark Patterns in the Interaction with Cookie Banners

Philip Hausner  Institute of Computer Science, Heidelberg
UniversityHeidelbergGermany<EMAIL_ADDRESS>and  Michael
Gertz  Institute of Computer Science, Heidelberg UniversityHeidelbergGermany
<EMAIL_ADDRESS>
(2021)

###### Abstract.

Dark patterns are interface designs that nudge users towards behavior that is
against their best interests. Since humans are often not even aware that they
are influenced by these malicious patterns, research has to identify ways to
protect web users against them. One approach to this is the automatic
detection of dark patterns which enables the development of tools that are
able to protect users by proactively warning them in cases where they face a
dark pattern. In this paper, we present ongoing work in the direction of
automatic detection of dark patterns, and outline an example to detect
malicious patterns within the domain of cookie banners.

dark patterns, cookie banner, pattern detection, privacy, web technologies

††copyright: custom††journalyear: 2021††doi: https://dbs.ifi.uni-
heidelberg.de/files/Team/phausner/publications/Hausner_Gertz_CHI2021.pdf††conference:
ACM CHI Virtual Conference on Human Factors in Computing Systems; May 08–13,
2021; Yokohama, Japan††booktitle: Position Paper at the Workshop ”What Can CHI
Do About Dark Patterns?” at the CHI Conference on Human Factors in Computing
Systems, May 8-13, 2021, Yokohama, Japan††price: 15.00††isbn: XXX-X-XXXX-
XXXX-X/XX/XX††ccs: Human-centered computing HCI theory, concepts and
models††ccs: Information systems World Wide Web††ccs: Security and privacy
Privacy protections

##  1\. Introduction

Web cookies are small files that store user data during or between browser
sessions. Cookies can benefit web site visitors in a variety of ways, e.g., by
storing user preferences or remembering a login on a page, and hence, can
generally improve user experience. However, recent studies have shown that the
large majority of today’s web cookies are employed to track users and collect
their data with the intent of serving them targeted ads (Urban et al., 2020).
By analyzing this vast amount of data, advertisement companies are able to
identify subtle behavioral patterns most users are probably unaware of. While
advertisers often claim otherwise, most consumers do not want to be tracked so
that companies can serve them ”more relevant advertisements”: A $2017$ study
showed that only about $3\%$ of users are willing to accept web wide tracking
cookies111https://assortedmaterials.com/2017/09/12/new-research-how-many-
consent-to-tracking/ (accessed on $3$. February $2021$), and research by Kulyk
et al. suggests that most site visitors solely agree to the usage of cookies
as a ”necessary evil” to access web pages (Kulyk et al., 2018). Hence, the
common practice of setting tracking cookies (not necessarily only for
advertisement purposes) for users ignores the privacy concerns of many
citizens. To address this issue, the European Union introduced the General
Data Protection Regulation (GDPR) in $2016$ (European Commission, [n. d.]). As
a result, many web pages introduced so-called cookie banners that are
frequently implemented as banners at the top or bottom of a page, or as a pop-
up that either informs the site visitor about the usage of cookies on the web
page, or asks for user consent to set cookies. The complexity of existing
banners varies widely, as can be seen in Figure 1. On one hand, Figure 1(a)
gives the user only the option between the acceptance of cookies or to leave
the web site, combined with a short informational text. On the other hand, in
Figure 1(b) the user is confronted with an information overload, and finally
with the choice to accept cookies or to manage the choices. The latter then
leads to a submenu presenting the user with a multitude of options to
customize their privacy settings. Moreover, one can easily identify that the
two choices in Figure 1(b) are not equal: While the button that gives consent
to cookies is highlighted by using a contrasting foreground color, the
alternative is less prominent and is displayed using just a slightly different
shade than the background color. This subtle difference in displaying
alternatives can already be identified as a method to nudge the unassuming
user towards accepting all available cookies, since the option to accept seems
to be the default choice, while the alternative (customizing cookies) is
illustrated as optional. Additionally, rejecting cookies is even harder for
consumers, since the option for rejection is situated in a separate submenu,
which subsequently requires significantly more clicks than to simply accept.
One way to think of this user manipulation is in the terms of Dark Patterns, a
term coined by Brignull in $2010$ (Brignull, 2010), and who described them as
”tricks used in [web sites] and apps that make you do things that you didn’t
mean to”, in this case accept to a variety of tracking cookies most users are
not interested in. Using a more recent taxonomy by Gray et al., this can be
interpreted as an instance of interface interference, particularly a case of
aesthetic manipulation (Gray et al., 2018), since the user is nudged towards a
decision simply by presenting two (or more) options as visually different, and
thereby presenting one as the default. Moreover, this can be seen as a case of
forced action, because usually the user has to interact with the cookie banner
and needs to take an action before they can enter the web site. In this case,
it can be classified as a version of ”Privacy Zuckering”, a pattern that
tricks users into sharing more information about themselves than they
intended.

Besides the visual aspect, one can notice a second strategy in the above
example, namely that the accept option is framed positively by stating ”Yes,
I’m happy”, while the more neutral option leading to the privacy customization
page is framed in a neutral tone as well.

(a)

(b)

Figure 1. Cookie banners found on (a) www.argos.co.uk/ (accessed $2.$ Oct.
$2020$), and (b) www.theguardian.com/ (accessed $1.$ Feb. $2021$).

Recent work by Utz et al. (2019) and Luguri and Strahilevitz (2019) showed
that such design choices highly influence the decision making of users, and
hence, one can assume that designers include these patterns deliberately into
their work. Providing such insights is an important task, and we highly
appreciate the work that is done to establish best practices and guidelines
for designers to follow, such that they can avoid these malicious patterns.
However, since advertisement and the corresponding tracking of user behavior
is a crucial income source for many vendors, it can be assumed that even with
suitable guidelines at hand, some designers will implement dark patterns
nonetheless. For that reason, our work focuses on the automatic detection of
dark patterns on web pages, and in the following, we outline our current work
and give an example in the context of cookie banners. Throughout this work, we
stick to the taxonomy of Gray et al. (2018), and do not formulate our own
definition of dark patterns.

##  2\. Counteracting and Automatic Detection of Dark Patterns

Establishing best practices for designers to follow, such that they can avoid
dark patterns, is a valuable contribution, but does not address web designers
who use dark patterns willfully in their work. The protection of consumers
against malicious design patterns needs to incorporate other means as well.
Firstly, it is important to inform users about the usage of such patterns, and
counteracting this asymmetry of power by informing consumers is also part of a
study conducted by the Norwegian Consumer Council (2018). Secondly,
researchers like Luguri and Strahilevitz (2019) or Weinzierl (2020) evaluate
the (un)lawfulness of dark patterns, and discuss in which ways legislators can
enact restrictions to the usage of such malicious patterns. Thirdly, one
possibility is to warn consumers when they encounter usages of dark patterns
on the web. Our work approaches this last strategy, in which we aim to
automatically detect the usage of patterns on web pages. To the best of our
knowledge, there is not much work that was conducted in the general field of
pattern detection on web pages. One exception to this is the work by Mathur et
al. who used automatic crawling to detect dark patterns on shopping web sites.
However, their focus was on the creation of a dark pattern taxonomy and to
assess how common dark patterns are on the examined shopping web sites (Mathur
et al., 2019), while our goal is to build a general framework to detect dark
patterns on arbitrary web pages.

The challenges in this context are manifold. To begin with, web pages are
heterogeneous in nature. First, the content of web pages has a wide range of
topics, e.g., news, games, or shopping. Second, the structure of web pages is
heterogeneous as well, making it hard to design a general approach to detect
certain patterns in a diverse set of pages. Therefore, it is mandatory to
develop a framework to detect patterns on a wide range of web pages. This
model does not need to be specific to dark patterns, but should at least be
able to incorporate them easily. Taking the heterogeneity of web pages into
account, it is clear that purely rule-based methods are not sufficient to
tackle the problem of dark pattern detection. An additional problem is the
rarity of occurrences of dark patterns on web pages in contrast to regular
page elements or other more frequent patterns that have no malicious intent.
This makes it mandatory to consider solutions from the field of rare pattern
detection and unbalanced classification as well.

For these reasons, our efforts aim to solve the problem using machine learning
approaches to detect dark patterns as generically as possible. The employed
model is based on input features from the Document Object Model (DOM), a tree-
like representation of an HTML document, whereas each node of the DOM
represents a part of the web page’s document. In this tree, each node can be
treated as a potential candidate of representing a dark pattern, and the
detection can now be framed as a classification problem in which the algorithm
decides for each node if it is in fact a malicious pattern. To be more
precise, one can (and should) also consider subtrees of the DOM as a potential
pattern, but for the sake of simplicity we restrict the discussion to nodes in
this work. Since single elements of a web page are rarely a dark pattern in
isolation, one needs to also consider the neighborhood of elements, and most
often a node can only be classified as malicious if multiple conditions are
met. Therefore, graph neural networks offer a promising perspective, since the
DOM is already a tree, and hence, a hierarchical graph structure, and this
approach could take into account the neighborhood of a node as well. However,
considering that most neural architectures for classification need large
amounts of labeled data to be trained, the problem that dark patterns are in
fact a rare phenomenon becomes especially problematic. One approach to this
can be active learning, an annotation technique for machine learning problems
that queries those elements to a user for which the classification algorithm
is unsure and as a result only critical cases need to be manually labeled
(Aggarwal et al., 2014; Settles, 2009). This can enable researchers to reduce
the time consuming manual labeling process, whereas only an initial seeding
set of examples needs to be labeled, and during application time additional
samples can be gathered.

Lastly, the outlined approach does not consider dynamic aspects of dark
patterns. Often, dark patterns only emerge when the user interacts with a web
page or in the context of multiple web pages that are visited in succession.
Therefore, it is necessary to extend the model in ways that incorporate
dynamic aspects, e.g., by treating the DOM as a dynamic graph. However, our
current research does not consider this aspect yet, but aims to integrate it
in future iterations.

##  3\. Preliminary Results

Figure 2. An automatically extracted cookie banner from www.anhaenger-
ersatzteile24.de/. Colored borders are inserted via DOM manipulation of our
program. Most importantly, an orange border indicates a detected ”accept” and
green a detected ”reject” button. The dashed border indicates that the program
has found an instance of visual interference in the cookie banner and is the
lowest common ancestor of the ”accept” and ”reject” button.

Instead of directly approaching the more complex problem of generally
detecting dark patterns, this section limits itself to a more confined task,
the detection of problematic patterns within cookie banners. The algorithm
employs a bottom-up approach, in which first low-level elements containing
certain keywords are identified, and then larger segments of content around
these low-level elements are iterated to find suitable cookie banner
candidates. If multiple candidates are found, heuristics like the text length
are used to determine the cookie banner.

By applying the implemented algorithm to more than $4000$ German web
sites222Domains ending in .de and using the Python package polyglot for
language detection of text content on the web page. extracted from a list of
the top one million web sites according to
Alexa.com333https://www.kaggle.com/cheedcheed/top1m?select=top-1m.csv
(accessed on $3$. February $2021$), around $2800$ cookie banners were
extracted and analyzed. By utilizing features like the HTML tag of elements,
it was possible to obtain a large amount of clickable elements within the
banners. We then extracted textual features from those elements, and used
clustering techniques to find different groups of buttons with regard to their
textual content. Based on the initial clustering and a manual relabeling of
critical items, a Support Vector Classifier is trained to distinguish between
multiple button types. In this work, the most important distinction is between
”accept” and ”reject” buttons. By retrieving the CSS style information for
each element, it is possible to identify if the two options (”accept” and
”reject”) are visualized similarly. In cases where the visual appearance is
too dissimilar, site users can now be warned and it can be indicated that the
acceptance of all cookies is in fact not the only option, even if the web site
operator tries to suggest otherwise.

Figure 2 shows the outcome for a single web page, but nonetheless, the
implemented framework is powerful enough to detect cookie banners on a wide
range of web pages, and reliably identifies cases of aesthetic manipulation in
the form of dissimilarly visualized user choices.

##  4\. Limitations

The automatic detection of dark patterns has also limitations that need to be
acknowledged. First of all, not all types of dark patterns as classified by
Gray et al. (2018) will be detectable by the proposed framework. For example,
gamification is a problem that usually is not specific to web pages, but is
part of apps that cannot directly be addressed by the model. Another instance
is the ”roach motel”, a pattern that describes a situation a user can get into
very easily but where it is hard to get out again, e.g., by being forced to
send a physical letter to cancel a premium subscription. Oftentimes, it is not
disclosed at subscription time that such action is necessary, and hence, it is
hard to detect such an instance automatically. Finally, the detection of dark
patterns shares challenges with ad blockers. It is rarely possible to foresee
which new patterns are going to emerge, and as a result, detection measures
are always reactive, and rely on practitioners that constantly update the
existing pattern databases as well as engaged consumers that point out new
occurrences.

###### Acknowledgements.

This work is part of the Dark Pattern Detection Project (dapde), which is
funded by the German Federal Ministry of Justice and Consumer Protection.

## References

  * (1)
  * Aggarwal et al. (2014) Charu C. Aggarwal, Xiangnan Kong, Quanquan Gu, Jiawei Han, and Philip S. Yu. 2014\.  Active Learning: A Survey.  In _Data Classification: Algorithms and Applications_ , Charu C. Aggarwal (Ed.). CRC Press, 571–606.  http://www.crcnetbase.com/doi/abs/10.1201/b17320-23
  * Brignull (2010) Harry Brignull. 2010\.  Dark Patterns - User Interfaces Designed to Trick People, https://darkpatterns.org/.  (2010).
  * European Commission ([n. d.]) European Commission. [n. d.].  Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation) .  ([n. d.]).  https://eur-lex.europa.eu/legal-content/EN/TXT/PDF/?uri=CELEX:32016R0679
  * Gray et al. (2018) Colin M. Gray, Yubo Kou, Bryan Battles, Joseph Hoggatt, and Austin L. Toombs. 2018.  The Dark (Patterns) Side of UX Design. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_ _(CHI 2018)_. Association for Computing Machinery, New York, NY, USA, 1–14.  https://doi.org/10.1145/3173574.3174108
  * Kulyk et al. (2018) Oksana Kulyk, Annika Hilt, Nina Gerber, and Melanie Volkamer. 2018.  ”This Website Uses Cookies”: Users’ Perceptions and Reactions to the Cookie Disclaimer. In _European Workshop on Usable Security (EuroUSEC)_.  https://doi.org/10.14722/eurousec.2018.23012
  * Luguri and Strahilevitz (2019) Jamie Luguri and Lior Strahilevitz. 2019.  Shining a Light on Dark Patterns.  _University of Chicago, Public Law Working Paper_ 719 (2019).
  * Mathur et al. (2019) Arunesh Mathur, Gunes Acar, Michael Friedman, Elena Lucherini, Jonathan R. Mayer, Marshini Chetty, and Arvind Narayanan. 2019.  Dark Patterns at Scale: Findings from a Crawl of 11K Shopping Websites.  _PACMHCI_ 3, CSCW (2019), 81:1–81:32.  https://doi.org/10.1145/3359183
  * Norwegian Consumer Council (2018) Norwegian Consumer Council. 2018\.  Deceived by Design: How Tech Companies Use Dark Patterns to Discourage us from Exercising Our Rights to Privacy.  (2018).  https://fil.forbrukerradet.no/wp-content/uploads/2018/06/2018-06-27-deceived-by-design-final.pdf
  * Settles (2009) Burr Settles. 2009\.  _Active Learning Literature Survey_.  Technical Report.
  * Urban et al. (2020) Tobias Urban, Martin Degeling, Thorsten Holz, and Norbert Pohlmann. 2020.  Beyond the Front Page: Measuring Third Party Dynamics in the Field. In _WWW ’20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020_ , Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen (Eds.). ACM / IW3C2, 1275–1286.  https://doi.org/10.1145/3366423.3380203
  * Utz et al. (2019) Christine Utz, Martin Degeling, Sascha Fahl, Florian Schaub, and Thorsten Holz. 2019.  (Un)informed Consent: Studying GDPR Consent Notices in the Field. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019_ , Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM, 973–990.  https://doi.org/10.1145/3319535.3354212
  * Weinzierl (2020) Quirin Weinzierl. 2020\.  Dark Patterns als Herausforderung fuer das Recht - Rechtlicher Schutz vor der Ausnutzung von Verhaltensanomalien.  _Neue Zeitschrift fuer Verwaltungsrecht_ 15 (2020), 1–11.  https://rsw.beck.de/rsw/upload/NVwZ/NVwZ-Extra_2020_15.pdf