# Multiplicative complements I.

Anett Kocsis , Dávid Matolcsi , Csaba Sándor and György Tőtős Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS>Supported by the
ÚNKP-21-1 New National Excellence Program of the Ministry for Innovation and
Technology from the source of the National Research, Development and
Innovation Fund. Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>Supported by the ÚNKP-21-1 New National Excellence
Program of the Ministry for Innovation and Technology from the source of the
National Research, Development and Innovation Fund.Department of Stochastics,
Institute of Mathematics, Budapest University of Technology and Economics,
Műegyetem rkp. 3., H-1111, Budapest, Hungary. Department of Computer Science
and Information Theory, Budapest University of Technology and Economics,
Műegyetem rkp. 3., H-1111 Budapest, Hungary, MTA-BME Lendület Arithmetic
Combinatorics Research Group, ELKH, Műegyetem rkp. 3., H-1111 Budapest,
Hungary , MTA-BME Lendület Arithmetic Combinatorics Research Group H-1529 B.O.
Box, Hungary. Email<EMAIL_ADDRESS>This author was supported by the
NKFIH Grants No. K129335. Faculty of Mathematics and Computer Science, Babeş-
Bolyai University.

(January 2022)

###### Abstract

In this paper, we study how dense a multiplicative basis of order $h$ for
$\mathbb{Z}^{+}\\!$ can be, improving on earlier results. Upon introducing the
notion of a multiplicative complement, we present some tight density bounds.

##  1 Introduction

Let $\mathbb{Z}^{+}\\!$ denote the set of positive integers. For
$A\subseteq\mathbb{Z}^{+}\\!$ and $h\in\mathbb{Z}^{+}\\!$, the multiplicative
representation function $S_{A,h}(n)$ of order $h$ counts the ordered
representations of $n\in\mathbb{Z}^{+}\\!$ as a product of $h$ elements of
$A$; that is, we define

$S_{A,h}(n)=|\\{(a_{1},\ldots,a_{h}):a_{i}\in A\text{ and }a_{1}\cdots
a_{h}=n\\}|.$

We say that $A$ is a multiplicative basis of order $h$ for
$\mathbb{Z}^{+}\mkern-1.0mu$ if all positive integers can be written in the
form $a_{1}\cdots a_{h}$ for some $a_{i}\in A$, which we may also express as
having $S_{A,h}(n)\geq 1$ for all $n\in\mathbb{Z}^{+}\\!$. We denote the set
of multiplicative bases like $A$ by $\mathop{\rm MB}\nolimits_{h}$. The
counting function $A(n)$ now counts the elements of $A$ that are less than or
equal to $n$; that is, we write $A(n)=|A\cap\\{1,2,\ldots,n\\}|$. It is easy
to see that for $A\in\mathop{\rm MB}\nolimits_{h}$, the prime numbers are
necessarily members of $A$, and hence

$A(n)\geq\pi(n)=(1+o(1))\frac{n}{\log n}.$

In 1938, Raikov proved the following density bounds.

######  Theorem 1 ([6, Th. 1]).

Let $h\in\mathbb{Z}^{+}\\!$. Then:

  1. 1.

For all $A\in\mathop{\rm MB}\nolimits_{h}$, we have
$\displaystyle\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}\geq\frac{1}{\Gamma\left(\frac{1}{h}\right)}$.

  2. 2.

There exists $A\in\mathop{\rm MB}\nolimits_{h}$ with
$\displaystyle\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}<\infty$.

Note that $\Gamma\left(\frac{1}{h}\right)=(1+o(1))h$ as $h\to\infty$. In 2018,
Pach and Sándor improved upon these inequalities.

######  Theorem 2 ([4, Th. 3]).

Let $h\in\mathbb{Z}^{+}\\!$. Then:

  1. 1.

For all $A\in\mathop{\rm MB}\nolimits_{h}$, we have
$\displaystyle\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}\geq\frac{\sqrt{6}}{e\pi}$.

  2. 2.

There exists $C>0$ such that for each $h\geq 2$, one can find $A\in\mathop{\rm
MB}\nolimits_{h}$ with

$\mkern-100.0mu\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}=C.$

The following theorem provides an even better lower bound.

######  Theorem 3.

Let $h\in\mathbb{Z}^{+}\\!$. For all $A\in\mathop{\rm MB}\nolimits_{h}$, we
have
$\displaystyle\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}\geq\frac{\sqrt[h]{h!}}{\Gamma\left(\frac{1}{h}\right)}$.

Let us note that for $h\geq 2$, the sequence
$\frac{\sqrt[h]{h!}}{\Gamma\left(\frac{1}{h}\right)}$ is decreasing in $h$,
and its limit is $\frac{1}{e}$. Consequently:

######  Corollary 4.

With $h\geq 2$, for all $A\in\mathop{\rm MB}\nolimits_{h}$, we have
$\displaystyle\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}>\frac{1}{e}$.

For $A_{1},\ldots,A_{h}\subseteq\mathbb{Z}^{+}\\!$, we define the common
multiplicative representation function as

$S_{A_{1},\ldots,A_{h}}(n)=|\\{(a_{1},\ldots,a_{h}):a_{i}\in A_{i}\text{ and
}a_{1}\cdots a_{h}=n\\}|$

with $n\in\mathbb{Z}^{+}$. Raikov’s theorem may now be generalised to these
functions as follows.

######  Theorem 5.

Let $A_{1},\ldots,A_{h}\subseteq\mathbb{Z}^{+}\\!$. Pick
$\tau_{1},\ldots,\tau_{h}\in(0,1)$ such that
$\displaystyle\sum_{i=1}^{h}\tau_{i}=1$, and assume that

$\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}<\infty$

for $1\leq i\leq h$. Then, we have

$\left(\liminf_{x\to\infty}\frac{\sum_{n\leq
x}S_{A_{1},\ldots,A_{h}}(n)}{x}\right)\;\prod_{i=1}^{h}\;\frac{1}{\Gamma(\tau_{i})}\;\leq\;\prod_{i=1}^{h}\;\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}.$

Let $A_{i}\subseteq\mathbb{Z}^{+}$ for $1\leq i\leq h$. We shall refer to the
$h$-tuple $(A_{1},\ldots,A_{h})$ as a multiplicative complement of order $h$
if all positive integers can be written in the form $a_{1}\cdots a_{h}$ with
$a_{i}\in A_{i}$, which we may also express as having
$S_{A_{1},\ldots,A_{h}}(n)\geq 1$ for all $n\in\mathbb{Z}^{+}$. We denote the
set of multiplicative complements of order $h$ by $\mathop{\rm
MC}\nolimits_{h}$. The following is then a direct consequence of the above
theorem.

######  Corollary 6.

Let $h\in\mathbb{Z}^{+}\\!$ and $(A_{1},\ldots,A_{h})\in\mathop{\rm
MC}\nolimits_{h}$. Pick $\tau_{1},\ldots,\tau_{h}\in(0,1)$ such that
$\displaystyle\sum_{i=1}^{h}\tau_{i}=1$ and

$\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}<\infty$

for $1\leq i\leq h$. Then, we have

$\prod_{i=1}^{h}\;\frac{1}{\Gamma(\tau_{i})}\;\leq\;\prod_{i=1}^{h}\;\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}.$

This inequality is sharp.

######  Theorem 7.

Let $h\in\mathbb{Z}^{+}\\!$. Pick $\tau_{1},\ldots,\tau_{h}\in(0,1)$,
$a_{1},\ldots,a_{h}\in(0,\infty)$ with $\displaystyle\sum_{i=1}^{h}\tau_{i}=1$
and $\displaystyle\prod_{i=1}^{h}a_{i}=1$. Then, there exists
$(A_{1},\ldots,A_{h})\in\mathop{\rm MC}\nolimits_{h}$ such that

$\lim_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}=\frac{a_{i}}{\Gamma(\tau_{i})}$

for all $1\leq i\leq h$.

A simple corollary to these theorems may now be formulated.

######  Corollary 8.

Let $h\in\mathbb{Z}^{+}\\!$. Then:

  1. 1.

For all $(A_{1},\ldots,A_{h})\in\mathop{\rm MC}\nolimits_{h}$, we have
$\displaystyle\limsup_{x\to\infty}\max\\{A_{1}(x),\ldots,A_{h}(x)\\}\frac{\log^{1-\frac{1}{h}}x}{x}\geq\frac{1}{\Gamma\left(\frac{1}{h}\right)}$.

  2. 2.

There is $(A_{1},\ldots,A_{h})\in\mathop{\rm MC}\nolimits_{h}$ for which
$\displaystyle\lim_{x\to\infty}\max\\{A_{1}(x),\ldots,A_{h}(x)\\}\frac{\log^{1-\frac{1}{h}}x}{x}=\frac{1}{\Gamma\left(\frac{1}{h}\right)}$.

It is easy to see that if $(A_{1},\dots A_{h})\in\mathop{\rm
MC}\nolimits_{h}$, then we necessarily have $A_{1}\cup\cdots\cup
A_{h}\in\mathop{\rm MB}\nolimits_{h}$, and hence:

######  Corollary 9.

With $h\in\mathbb{Z}^{+}$, there exists $A\in\mathop{\rm MB}\nolimits_{h}$
such that

$\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}=\frac{h}{\Gamma\left(\frac{1}{h}\right)}.$

One can readily check that
$\frac{h}{\Gamma(\frac{1}{h})}=\frac{1}{\Gamma(1+\frac{1}{h})}$ and
$\displaystyle\min_{h\geq
2}\Gamma\Big{(}1+\frac{1}{h}\Big{)}=\frac{\sqrt{\pi}}{2}$. This yields the
next statement.

######  Corollary 10.

With $h\geq 2$, there exists $A\in\mathop{\rm MB}\nolimits_{h}$ such that

$\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}=\frac{2}{\sqrt{\pi}}.$

In 2018, Pach and Sándor also proved density bounds for the limit inferior.

######  Theorem 11 ([4, Th. 4]).

Let $h\in\mathbb{Z}^{+}\\!$. Then:

  1. 1.

For all $A\in\mathop{\rm MB}\nolimits_{h}$, we have
$\displaystyle\liminf\limits_{x\to\infty}\frac{A(x)}{\frac{x}{\log x}}>1$.

  2. 2.

For all $\varepsilon>0$, there exists $A\in\mathop{\rm MB}\nolimits_{h}$ with
$\displaystyle\liminf_{x\to\infty}\frac{A(x)}{\frac{x}{\log x}}\leq
1+\varepsilon$.

For multiplicative complements, we may formulate the analogue as follows.

######  Theorem 12.

Let $h\in\mathbb{Z}^{+}\\!$. Then:

  1. 1.

For all $(A_{1},A_{2},\ldots,A_{h})\in\mathop{\rm MC}\nolimits_{h}$, we have
$\displaystyle\liminf\limits_{x\to\infty}\frac{\max\\{A_{1}(x),\ldots,A_{h}(x)\\}}{\frac{x}{\log
x}}>\frac{1}{h}$.

  2. 2.

For all $\varepsilon>0$, there exists $(A_{1},\ldots,A_{h})\in\mathop{\rm
MC}\nolimits_{h}$ with
$\displaystyle\liminf_{x\to\infty}\frac{\max\\{A_{1}(x),\ldots,A_{h}(x)\\}}{\frac{x}{\log
x}}\leq\frac{1}{h}+\varepsilon$.

Let us, finally, propose some problems for further research. Note that for
$h\geq 2$, we have

$\mkern
14.0mu\frac{1}{e}<\frac{\sqrt[h]{h!}}{h\Gamma\left(1+\frac{1}{h}\right)}\leq\inf_{A\in\mathop{\rm
MB}\nolimits_{h}}\bigg{\\{}\limsup_{x\to\infty}\frac{A(x)}{\frac{x}{\log^{1-\frac{1}{h}}x}}\bigg{\\}}\leq\frac{1}{\Gamma\left(1+\frac{1}{h}\right)}\leq\frac{2}{\sqrt{\pi}}.$

######  Problem 1.

Is it true that for all $h\geq 2$ and $A\in\mathop{\rm MB}\nolimits_{h}$, we
have

$\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}x}{x}\geq\frac{1}{\Gamma\left(1+\frac{1}{h}\right)}\,?$

As answering this question seems to be hard, we shall simplify it. Note that
for $A\in\mathop{\rm MB}\nolimits_{2}$, we have

$\frac{\sqrt{2}}{\sqrt{\pi}}\leq\limsup_{x\to\infty}\frac{A(x)}{\frac{x}{\sqrt{\log
x}}}.$

######  Problem 2.

Is it true that there exists $\delta>0$ such that for all $A\in\mathop{\rm
MB}\nolimits_{2}$, we have

$\frac{\sqrt{2}}{\sqrt{\pi}}+\delta\leq\limsup_{x\to\infty}\frac{A(x)}{\frac{x}{\sqrt{\log
x}}}\,?$

Picking now $A\in\mathop{\rm MB}\nolimits_{2}$, obviously, $S_{A,2}(n)\geq 2$
holds as long as $n\in\mathbb{Z}^{+}\\!$ is not a perfect square, and so
$\displaystyle\sum_{n\leq x}S_{A,2}(n)\geq x-\lfloor\sqrt{x}\rfloor$. In
particular,

$\liminf_{x\to\infty}\frac{\sum_{n\leq x}S_{A,2}(n)}{x}\geq 2.$

Thus, according to Theorem 5, we can further reduce Problem 2 to the
following.

######  Problem 3.

Is it true that there exists $\delta_{0}>0$ such that for all $A\in\mathop{\rm
MB}\nolimits_{2}$, we have

$\liminf_{x\to\infty}\frac{\sum_{n\leq x}S_{A,2}(n)}{x}\geq 2+\delta_{0}\,?$

Concluding, note how Theorem 5 claims $\liminf$ to be finite. As for
$\limsup$, the analogue is:

######  Problem 4.

Let $h\in\mathbb{Z}^{+}$ and $(A_{1},\ldots,A_{h})\in\mathop{\rm
MC}\nolimits_{h}$. Pick $\tau_{1},\ldots,\tau_{h}\in(0,1)$ such that
$\displaystyle\sum_{i=1}^{h}\tau_{i}=1$ and

$\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}<\infty$

for $1\leq i\leq h$. Is it true that

$\limsup_{x\to\infty}\frac{\sum_{n\leq
x}S_{A_{1},\dots,A_{h}}(n)}{x}<\infty\,?$ (1.1)

##  2 Proofs

In what follows, for $A\subseteq\mathbb{Z}^{+}$, we write $A[s]=\sum_{a\in
A}\frac{1}{a^{s}}$, where $s>1$.

The proof of Theorem 3 and that of Theorem 5 are based on the next lemma,
coming from Raikov’s paper yet not explicitly stated there.

######  Lemma 1.

Choose $A\subseteq\mathbb{Z}^{+}\\!$ and $\tau\in(0,1)$ such that
$\displaystyle\limsup_{x\to\infty}A(x)\frac{\log^{1-\tau}x}{x}<\infty$. Then,

$\limsup_{s\searrow
1}(s-1)^{\tau}A[s]\leq\Gamma(\tau)\limsup_{x\to\infty}A(x)\frac{\log^{1-\tau}x}{x}.$

###### Proof.

We know that for all $s>1$, we have

$s\int_{1}^{\infty}\frac{A(x)}{x^{s+1}}dx=\sum_{a\in
A}s\int_{a}^{\infty}\frac{1}{x^{s+1}}dx=\sum_{a\in A}\frac{1}{a^{s}}=A[s].$

Pick now $a>\alpha$, where

$\mkern-4.0mu\alpha=\limsup_{x\to\infty}A(x)\frac{\log^{1-\tau}x}{x}.$

Then, there exists $x_{0}>1$ such that for all $x\geq x_{0}$, we have

$\frac{A(x)}{x}\leq\frac{a}{\log^{1-\tau}x}.$

Consequently,

$A[s]\leq
s\int_{1}^{x_{0}}\frac{A(x)}{x^{s+1}}dx+sa\int_{x_{0}}^{\infty}\frac{1}{x^{s}\log^{1-\tau}x}dx.$

Changing variable and writing $t=(s-1)\log x$ in the rightmost integral, we
get

$A[s]\leq
s\int_{1}^{x_{0}}\frac{A(x)}{x^{s+1}}dx+\frac{s}{(s-1)^{\tau}}a\int_{(s-1)\log
x_{0}}^{\infty}\\!\\!\\!\\!t^{\tau-1}e^{-t}dt.$

Introducing the gamma function, we may now rewrite the previous inequality as

$(s-1)^{\tau}A[s]\leq
s(s-1)^{\tau}\\!\\!\int_{1}^{x_{0}}\frac{A(x)}{x^{s+1}}dx-
sa\\!\\!\int_{0}^{(s-1)\log x_{0}}\\!\\!\\!t^{\tau-1}e^{-t}dt+\Gamma(\tau)sa.$

Since $s\searrow 1$, we have

$s(s-1)^{\tau}\\!\\!\int_{1}^{x_{0}}\frac{A(x)}{x^{s+1}}dx\to 0,\quad
sa\\!\\!\int_{0}^{(s-1)\log x_{0}}\\!\\!\\!t^{\tau-1}e^{-t}dt\to 0\;\text{ and
}\;\Gamma(\tau)sa\to\Gamma(\tau)a,$

and thus

$\limsup_{s\searrow 1}(s-1)^{\tau}A[s]\leq\Gamma(\tau)a.$

This proves the desired inequality. ∎

The following lemma improves on Raikov’s result.

######  Lemma 2.

For a multiplicative basis $A$ of order $h$ for $\mathbb{Z}^{+}$, we have

$\limsup_{s\searrow 1}(s-1)^{\frac{1}{h}}A[s]\geq\sqrt[h]{h!}\,.$

###### Proof.

Without loss of generality, we may assume that

$\mkern 20.0mu\limsup_{s\searrow 1}(s-1)^{\frac{1}{h}}A[s]=\alpha<\infty.$

Set $B=A\mkern 1.0mu\cup\mkern 1.0mu\\{a^{2}\mkern 1.0mu:\mkern 1.0mua\in
A\\}$. Then,

$\frac{1}{h!}A[s]^{h}+B[s]^{h-1}=\sum_{n\geq
1}\frac{1}{n^{s}}\left(\frac{S_{A,h}(n)}{h!}+S_{B,h-1}(n)\right).$

Given that $A$ is a multiplicative basis of order $h$ for $\mathbb{Z}^{+}\\!$,
we can write $n=a_{1}\cdots a_{h}$ for some $a_{i}\in A$. If $S_{B,h-1}(n)=0$,
then $a_{i}\neq a_{j}$ for all $i\,\neq\,j$, meaning that $S_{A,h}(n)\geq h!$.
That is, for all $n\geq 1$, we have

$\frac{S_{A,h}}{h!}+S_{B,h-1}(n)\geq 1.$

Consequently, for all $s>1$, we get

$\frac{1}{h!}A[s]^{h}+B[s]^{h-1}\geq\zeta(s).$

Note that $B[s]\leq A[s]+A[2s]$ for any $s>1$, and hence

$(s-1)B[s]^{h-1}\leq(s-1)A[2s]^{h-1}+\sum_{j=1}^{h-1}\binom{h-1}{j}\left((s-1)^{\frac{1}{j}}A[s]\right)^{j}A[2s]^{h-1-j}.$

Clearly, $A[2s]\to A[2]\leq\zeta(2)<\infty$ as $s\searrow 1$. Since
$\alpha<\infty$, for all $1\leq j\leq h-1$, we get

$\lim_{s\searrow 1}(s-1)^{\frac{1}{j}}A[s]=0,$

and so

$\lim_{s\searrow 1}(s-1)B[s]^{h-1}=0.$

Therefore, we can conclude that

$\limsup_{s\searrow 1}(s-1)\frac{1}{h!}A[s]^{h}\geq\limsup_{s\searrow
1}(s-1)\zeta(s)=1,$

which then completes the proof. ∎

###### Proof of theorem 3.

Using Lemma 1 and Lemma 2, for a multiplicative basis $A$ of order $h$, we
have

$\limsup_{x\to\infty}A(x)\frac{\log^{1-\frac{1}{h}}}{x}\geq\frac{1}{\Gamma(\frac{1}{h})}\limsup_{s\searrow
1}(s-1)^{\frac{1}{h}}A[s]\geq\frac{\sqrt[h]{h!}}{\Gamma(\frac{1}{h})}.$

∎

###### Proof of theorem 5.

We prove by contradiction. Suppose that

$\liminf_{x\to\infty}\frac{\sum_{n\leq
x}S_{A_{1},\dots,A_{h}}(n)}{x}>\prod_{i=1}^{h}\left(\Gamma(\tau_{i})\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}\right).$

Pick $G$ satisfying

$\prod_{i=1}^{h}\left(\Gamma(\tau_{i})\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}\right)<G<\liminf_{x\to\infty}\frac{\sum_{n\leq
x}S_{A_{1},\ldots,A_{h}}(n)}{x}.$

We can find $n_{0}>0$ such that for all $n\geq n_{0}$, we have

$b_{n}=\sum_{k\leq n}S_{A_{1},\dots,A_{h}}(k)\geq G\cdot n.$

Pick $n>n_{0}$ and $s>1$. Then,

$\displaystyle\sum_{k=1}^{n}\frac{S_{A_{1},\ldots,A_{h}}(k)}{k^{s}}$
$\displaystyle=\sum_{k=1}^{n}\frac{b_{k}-b_{k-1}}{k^{s}}=\frac{b_{n}}{n^{s}}+\sum_{k=1}^{n-1}\frac{b_{k}}{k}\left(\frac{k}{k^{s}}-\frac{k}{(k+1)^{s}}\right)$
$\displaystyle\geq G\mkern-4.0mu\sum_{n_{0}\leq
k<n}\mkern-4.0mu\left(\frac{1}{k^{s-1}}-\frac{1}{(k+1)^{s-1}}+\frac{1}{(k+1)^{s}}\right)\geq
G\mkern-8.0mu\sum_{n_{0}<k\leq n}\frac{1}{k^{s}}.$

It follows that

$\sum_{k=1}^{\infty}\frac{s_{A_{1},\dots,A_{h}}(k)}{k^{s}}\geq
G\cdot\zeta(s)-G\sum_{k\leq n_{0}}\frac{1}{k^{s}}.$

Note that $\displaystyle G\sum_{k\leq n_{0}}\frac{1}{k^{s}}$ tends to
$G\sum_{k\leq n_{0}}\frac{1}{k}$ as $s\searrow 1$, which expression is finite,
and thus

$\liminf_{s\searrow
1}(s-1)\sum_{k=1}^{n}\frac{S_{A_{1},\ldots,A_{h}}(k)}{k^{s}}\geq\liminf_{s\searrow
1}(s-1)G\zeta(s)=G.$

From

$\mkern-18.0mu\sum_{k=1}^{n}\frac{S_{A_{1},l\dots,A_{h}}(k)}{k^{s}}=\prod_{i=1}^{h}A_{i}[s]$

and using $\displaystyle\sum_{i=1}^{h}\tau_{i}=1$, we get

$G\leq\liminf_{s\searrow 1}(s-1)\prod_{i=1}^{h}A_{i}[s]=\liminf_{s\searrow
1}\prod_{i=1}^{h}\left((s-1)^{\tau_{i}}A_{i}[s]\right)\leq\prod_{i=1}^{h}\limsup_{s\searrow
1}(s-1)^{\tau_{i}}A_{i}[s].$

Using now Lemma 1, we get

$\limsup_{s\searrow
1}(s-1)^{\tau_{i}}A_{i}[s]\leq\Gamma(\tau_{i})\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}.$

Putting it all together, it follows that

$G\leq\prod_{i=1}^{h}\left(\Gamma(\tau_{i})\limsup_{x\to\infty}A_{i}(x)\frac{\log^{1-\tau_{i}}x}{x}\right)\mkern-2.0mu,$

which, however, contradicts the choice of $G$. ∎

###### Proof of Theorem 7.

We prove by showing that the set $P$ of prime numbers may be written as

$\mkern-10.0muP=P_{1}\cup\dots\cup P_{h}$ (2.1)

with $P_{i}\cap P_{j}=\emptyset$ for $i\neq j$ and with the partitions $P_{i}$
subject to

$P_{i}(x)=\tau_{i}\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$ (2.2)

and

$\lim_{x\to\infty}\bigg{(}\prod_{{p\leq x,\;p\in
P_{i}}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{\begin{subarray}{c}p\leq
x\end{subarray}}\frac{p-1}{p}\bigg{)}^{\tau_{i}}=a_{i}.$ (2.3)

In order to see why the existence of such a partition indeed implies the
theorem, we shall invoke the Wirsing–Odoni theorem (see [3, Pr. 4]).

######  Theorem.

(Wirsing–Odoni) Let $f$ be a multiplicative function. Assume that there exist
constants $u$, $v$ such that $0\leq f(p^{k})<uk^{v}$ for all primes $p$ and
all positive integers $k$. Assume further that there exist real numbers
$\xi>0$ and $1<r<2$ such that

$\sum\limits_{x\geq p\text{ prime}}f(p)=\xi\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{r}x}\Big{)}$

as $x\to\infty$. Then, the product

$C_{f}=\frac{1}{\Gamma(\xi)}\prod_{p\text{
prime}}\Big{(}1+\frac{f(p)}{p}+\frac{f(p^{2})}{p^{2}}+\frac{f(p^{3})}{p^{3}}+\cdots\Big{)}\Big{(}1-\frac{1}{p}\Big{)}^{\xi}$

over the primes is convergent (and positive), and

$\sum\limits_{n\leq
x}f(n)=C_{f}\frac{x}{\log^{1-\xi}x}+O\Big{(}\frac{x}{\log^{r-\xi}x}\Big{)}$

as $x\to\infty$.

Back to the proof, introduce

$A_{i}=\\{n:\textrm{each prime factor of $n$ belongs to the set $P_{i}$}\\}$

for $1\leq i\leq h$. We wish to apply the Wirsing–Odoni theorem to the
multiplicative function defined as $f(p^{k})=1$ if $p\in P_{i}$ and
$f(p^{k})=0$ if $p\notin P_{i}$ with $p$ a prime. It follows that

$\sum_{p\leq x}f(p)=P_{i}(x)=\tau_{i}\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)},$

and by condition (2.3), also

$C_{f}=\frac{1}{\Gamma(\tau_{i})}\prod_{p\textrm{
prime}}\Big{(}1+\frac{f(p)}{p}+\frac{f(p^{2})}{p^{2}}+\frac{f(p^{3})}{p^{3}}+\ldots\Big{)}\Big{(}1-\frac{1}{p}\Big{)}^{\tau_{i}}=\frac{a_{i}}{\Gamma(\tau_{i})}.$

According to the Wirsing–Odoni theorem, we have

$\sum_{n\leq
x}f(n)=A_{i}(x)=\Big{(}\frac{a_{i}}{\Gamma(\tau_{i})}+o(1)\Big{)}\frac{x}{\log^{1-\tau_{i}}x}.$

As $(A_{1},\ldots,A_{h})\mkern-1.0mu\in\mkern-1.0mu\mathop{\rm
MC}\nolimits_{h}$, we win.

The existence of a suitable partition subject to conditions (2.1), (2.2) and
(2.3) is shown via the following lemma.

######  Lemma 3.

Let $P=\\{p_{1},p_{2},\dots\\}$ be the set of prime numbers with
$p_{1}<p_{2}<\cdots$, and pick $0<\kappa\leq 1$. Consider now $Q\subseteq P$
subject to

$Q(x)=\kappa\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and such that there exists $K\in\mathbb{Z}^{+}\\!$ with

$Q\cap\\{p_{n},\ldots,p_{n+K}\\}\neq\emptyset$

for all $n\in\mathbb{Z}^{+}\\!$. Let $0<\tau<\kappa$, $a\in\mathbb{R}^{+}$.
Then, there exist $R\subseteq Q$ and $L\in\mathbb{Z}^{+}\\!$ such that for all
$n\in\mathbb{Z}^{+}\\!$,

$R\cap\\{p_{n}+,\ldots,p_{n+L}\\}\neq\emptyset,\quad R(x)=\tau\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
R}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq x}\frac{p-1}{p}\bigg{)}^{\tau}=a.$

The desired partition of the prime numbers now follows recursively. Indeed, it
is known that

$P(x)=\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}.$

Then, by Lemma 3, there exist $Q_{1}\subseteq Q_{0}=P$ and
$L_{1}\in\mathbb{Z}^{+}\\!$ such that for all $n\in\mathbb{Z}^{+}\\!$, we have

$Q_{1}\cap\\{p_{n},\ldots,p_{n+L_{1}}\\}\neq\emptyset,\quad
Q_{1}(x)=(\tau_{2}+\cdots+\tau_{h})\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
Q_{1}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{2}+\dots+\tau_{h}}=a_{2}\cdots a_{h}.$

Set $P_{1}=Q_{0}\setminus Q_{1}$. As $\tau_{1}+\dots+\tau_{h}=1$ and
$a_{1}\cdots a_{h}=1$, we get

$P_{1}(x)=\tau_{1}\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
P_{1}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{1}}=a_{1}.$

Continuing in a similar fashion, say that we have already defined
$P_{1},\dots,P_{j}\subseteq P$ for some $1\leq j<h$ with $P_{u}\cap
P_{v}=\emptyset$ for $1\leq u<v\leq j$ and with the partitions $P_{i}$ subject
to

$P_{i}(x)=\tau_{i}\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
P_{i}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{i}}=a_{i}$

for $1\leq i\leq j$. Assume further that for

$Q_{j}=P\setminus(P_{1}\cup\cdots\cup P_{j}),$

there is a positive integer $L_{j}$ such that

$Q_{j}\cap\\{p_{n+1},\ldots,p_{n+L_{j}}\\}\neq\emptyset$

for all $n\in\mathbb{Z}^{+}$. Then,

$(P_{1}\cup\cdots\cup P_{j})(x)=(\tau_{1}+\cdots+\tau_{j})\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in P_{1}\cup\cdots\cup
P_{j}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{1}+\cdots+\tau_{j}}=a_{1}\cdots a_{j}.$

If $j\leq h-2$, then there exist $Q_{j+1}\subseteq Q_{j}$ and
$L_{j+1}\in\mathbb{Z}^{+}\\!$ such that for all $n\in\mathbb{Z}^{+}\\!$,

$Q_{j+1}\cap\\{p_{n},\ldots,p_{n+L_{j+1}}\\}\neq\emptyset,\quad
Q_{j+1}=(\tau_{j+2}+\cdots+\tau_{h})\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
Q_{j+1}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{j+2}+\cdots+\tau_{h}}=a_{j+2}\cdots a_{h}.$

As $\tau_{1}+\dots+\tau_{h}=1$ and $a_{1}\cdots a_{h}=1$, we get

$P_{j+1}(x)=\tau_{j+1}\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
P_{j+1}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{j+1}}=a_{j+1}.$

If $j=h-1$, set $P_{h}=Q_{h-1}=P\setminus(P_{1}\cup\cdots\cup P_{h-1})$. Note
that we have

$(P_{1}\cup\cdots\cup P_{h-1})(x)=(\tau_{1}+\cdots+\tau_{h-1})\frac{x}{\log
x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in P_{1}\cup\cdots\cup
P_{h-1}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{1}+\cdots+\tau_{h-1}}=a_{1}\cdots a_{h-1}.$

Once again, as $\tau_{1}+\cdots+\tau_{h}=1$ and $a_{1}\cdots a_{h}=1$, we get

$P_{h}(x)=\tau_{h}\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}$

and

$\lim_{x\to\infty}\bigg{(}\prod_{p\leq x,\;p\in
P_{h}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{p\leq
x}\frac{p-1}{p}\bigg{)}^{\tau_{h}}=a_{h},$

which then completes the argument.

It hence remains to prove Lemma 3.

###### Proof of Lemma 3.

Let us construct $R\subseteq Q$ by picking the elements of $Q$ and adding
$p\in Q$ to $R$ if $R(p-1)<\frac{\tau}{\kappa}Q(p)$. This then yields

$R(x)=\frac{\tau}{\kappa}Q(x)+O(1)$

and so

$R(x)=\tau\frac{x}{\log x}+O\Big{(}\frac{x}{\log^{2}x}\Big{)}.$ (2.4)

Consequently, with $N$ large enough,

$|R\cap\\{p_{n},p_{n+1},\ldots,p_{n+N-1}\\}|\geq 2,$ (2.5) $|(Q\setminus
R)\cap\\{p_{n},p_{n+1},\ldots,p_{n+N-1}\\}|\geq 2$ (2.6)

and there exist numbers $r\in R\cap\\{p_{n},p_{n+1},\ldots,p_{n+N-1}\\}$,
$s\in(Q\setminus R)\cap\\{p_{n},p_{n+1},\ldots,p_{n+N-1}\\}$ such that $r<s$
for all $n\in\mathbb{Z}^{+}\\!$. We can also find sequences $(r_{k})_{k}$,
$(s_{k})_{k}$ of primes with $r_{k}\in R\cap[p_{(k-1)N+1},p_{kN}]$,
$s_{k}\in(Q\setminus R)\cap[p_{(k-1)N+1},p_{kN}]$ such that $r_{k}<s_{k}$ for
all $k\in\mathbb{Z}^{+}$. Introducing

$q_{k}=\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})>0$

and

$q^{\prime}_{k}=\frac{1}{r_{k}}-\frac{1}{s_{k}},$

and referring to any function $f:\mathbb{Z}^{+}\to\\{-1,1\\}$ as a sign
function, the proof is now an application of the following lemma.

######  Lemma 4.

With notation as above:

  1. 1.

$\sum_{k=1}^{\infty}q_{k}<\infty$ (2.7)

  2. 2.

There exists an integer $M$ such that for any real number $s$ satisfying

$-\sum\limits_{k=M}^{\infty}q_{k}\leq s\leq\sum\limits_{k=M}^{\infty}q_{k},$

there exists a sign function $f$ with

$\sum\limits_{k=M}^{\infty}f(k)q_{k}=s.$

###### Proof.

To prove (1), first note that

$q_{k}=\frac{1}{r_{k}}+\frac{1}{2r_{k}^{2}}+O\Big{(}\frac{1}{r_{k}^{3}}\Big{)}-\Big{(}\frac{1}{s_{k}}+\frac{1}{2s_{k}^{2}}+O\Big{(}\frac{1}{s_{k}^{3}}\Big{)}\Big{)}=q^{\prime}_{k}+q^{\prime}_{k}\frac{r_{k}+s_{k}}{2r_{k}s_{k}}+O\Big{(}\frac{1}{r_{k}^{3}}\Big{)}=(1+o(1))q^{\prime}_{k}$

as $k\to\infty$. Hence, for $k$ large enough, we have
$0.5q_{k}<q_{k}^{\prime}<1.5q_{k}$. The intervals $[x,x+x^{0.6}]$ are known to
contain prime numbers for $x$ large enough (see e.g. [1]), so if $k$ is large
enough, we get

$s_{k}-r_{k}\leq p_{(k+1)N}-p_{kN+1}\leq Nr_{k}^{0.6}.$

It follows that

$q_{k}\leq
2q^{\prime}_{k}=2\frac{s_{k}-r_{k}}{r_{k}s_{k}}\leq\frac{2Nr_{k}^{0.6}}{r_{k}^{2}}=\frac{2N}{r_{k}^{1.4}}\leq\frac{2N}{k^{1.4}}$

for $k$ large enough, and so $\displaystyle\sum_{k=1}^{\infty}q_{k}$ is
finite, indeed.

As for (2), we shall turn to a classical result about numerical series (see
e.g. [5] p. 29, Exercise 131): if the assumptions

$b_{n}>0,\quad\sum_{n=1}^{\infty}b_{n}\text{ is finite}\quad\text{and}\quad
b_{k}\leq\sum_{n=k+1}^{\infty}b_{n}\text{ for all $n\in\mathbb{Z}^{+}$}$

are met and we have

$0\leq t\leq\sum_{n=1}^{\infty}b_{n},$

then there is a function $g:\mathbb{Z}^{+}\to\\{0,1\\}$ such that

$t=\sum_{n=1}^{\infty}g(n)b_{n}$

(noting that in the excercise, the assumption that $b_{n}\leq b_{n+1}$ for all
$n\in\mathbb{Z}^{+}$ is unnecessary).

Now, if

$-\sum_{n=1}^{\infty}b_{n}\leq s\leq\sum_{n=1}^{\infty}b_{n},$

then there is a function $g:\mathbb{Z}^{+}\to\\{0,1\\}$ such that

$\sum_{n=1}^{\infty}g(n)b_{n}=\frac{s}{2}+\frac{1}{2}\sum_{n=1}^{\infty}b_{n}.$

In particular, $f(n)=2g(n)-1$ defines a sign function $f$, and we have

$\sum_{n=1}^{\infty}f(n)b_{n}=s.$

Hence, it suffices to show that there is a positive integer $M$ such that

$q_{n}<\sum\limits_{k=n+1}^{\infty}q_{k}$

holds for $n\geq M$.

It is known that for $x$ large enough, there are at least
$\frac{1}{2}\frac{x}{\log x}$ prime numbers between $x$ and $2x$, so there are
at least $\frac{1}{2N}\frac{r_{n}}{\log r_{n}}$ prime numbers $r_{k}$ between
$r_{n}$ and $2r_{n}$. For all these primes, we get

$q_{k}^{\prime}=\frac{s_{k}-r_{k}}{s_{k}r_{k}}\geq\frac{2}{(2r_{n})^{2}}$

and so

$q_{k}\geq\frac{1}{4r_{n}^{2}}.$

Hence,

$\sum_{r_{n}<r_{k}<2r_{n}}q_{k}\geq\frac{1}{2N}\frac{r_{n}}{\log
r_{n}}\frac{1}{4r_{n}^{2}}=\frac{1}{8Nr_{n}\log r_{n}}$

for $n$ large enough. It follows that

$q_{n}\leq\frac{2N}{r_{n}^{1.4}},$

and since we have

$\frac{1}{8Nr_{n}\log r_{n}}\geq\frac{2N}{r_{n}^{1.4}}$

for $n$ large enough, the proof of Lemma 4 is complete. ∎

We may now finish the proof of Lemma 3. As per the Wirsing–Odoni’s theorem and
(2.4), the limit

$\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
R\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\tau\log\Big{(}\frac{p}{p-1}\Big{)}\bigg{)}$

exists and is finite. By part (1) of Lemma 4, the limit

$c=\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
R\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\tau\log\Big{(}\frac{p}{p-1}\Big{)}-\sum\limits_{r_{k},s_{k}<x}\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}\bigg{)}$

also exists and is finie. Set
$H=\\{r_{k}:k\in\mathbb{Z}^{+}\\}\cup\\{s_{k}:k\in\mathbb{Z}^{+}\\}$.
Conditions (2.5) and (2.6) imply that

$\sum\limits_{p\in R\setminus H}\log\Big{(}\frac{p}{p-1}\Big{)}\;\textrm{ and
}\sum\limits_{p\in(Q\setminus R)\setminus H}\log\Big{(}\frac{p}{p-1}\Big{)}$

are divergent series, although $\log(\frac{p}{p-1})\to 0$ as $p\to\infty$ with
$p\in R\setminus H$ or $p\in(Q\setminus R)\setminus H$.

At this point, we are to conditionally replace some elements of $R$, keeping
the symmetric difference with the newly defined sets $R^{\prime}$ and
$R^{\prime\prime}$ finite. On the one hand, if

$c>\log(a)+\frac{1}{2}\sum\limits_{k=M}^{\infty}q_{k},$

then we may drop finitely many elements from $R\setminus H$ to get
$R^{\prime}\subseteq R$ such that

$\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
R^{\prime}\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\tau\log\Big{(}\frac{p}{p-1}\Big{)}-\sum\limits_{r_{k},s_{k}<x}\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}\bigg{)}=\log(a)-d,$
(2.8)

where $-\frac{1}{2}\sum\limits_{k=M}^{\infty}q_{k}\leq
d\leq\frac{1}{2}\sum\limits_{k=M}^{\infty}q_{k}.$ On the other hand, if

$c<\log(a)-\frac{1}{2}\sum\limits_{k=M}^{\infty}q_{k},$

then we may add finitely many elements from $(Q\setminus R)\setminus H$ to $R$
to get $R^{\prime}\supseteq R$ such that (2.8) holds. This yields $R^{\prime}$
that satisfy $(R^{\prime}\cap H)=\\{r_{k}:k\in\mathbb{Z}^{+}\\}$,
$|R^{\prime}\bigtriangleup R|<\infty$ as well as (2.8).

For the next step, note that by Lemma 4, there exists a sign function $f$ such
that $\frac{1}{2}\sum\limits_{k=M}^{\infty}f(k)q_{k}=d$. We introduce

$R^{\prime\prime}=\left(R^{\prime}\setminus\\{r_{k}:f(k)=-1\\}\right)\cup\\{s_{k}:f(k)=-1\\}.$

Then, we get

$\begin{split}&\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\
p\in
R^{\prime\prime}\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\tau\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}\bigg{)}=\\\
&\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
R^{\prime}\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\sum_{r_{k}<x,\;f(k)=-1}\log\Big{(}\frac{r_{k}}{r_{k}-1}\Big{)}-\log\Big{(}\frac{s_{k}}{s_{k}-1}\Big{)}-\tau\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}\bigg{)}=\\\
&\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
R^{\prime}\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\tau\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\sum_{r_{k}<x}\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}-\\\
&\mkern
23.0mu\sum_{r_{k}<x,\;f(k)=-1}\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}+\sum_{r_{k}<x,\;f(k)=1}\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}\bigg{)}=\\\
&\lim_{x\to\infty}\bigg{(}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
R^{\prime}\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\tau\sum_{\begin{subarray}{c}p\leq
x\end{subarray}}\log\Big{(}\frac{p}{p-1}\Big{)}-\\\ &\mkern
51.0mu\sum_{r_{k}<x}\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}+\sum_{r_{k}<x}f(k)\frac{\log(\frac{r_{k}}{r_{k}-1})-\log(\frac{s_{k}}{s_{k}-1})}{2}\bigg{)}=\log(a)-d+d=\log(a).\end{split}$

In particular,

$\lim_{x\to\infty}\bigg{(}\prod_{\begin{subarray}{c}p\leq x\\\ p\in
R^{\prime\prime}\end{subarray}}\frac{p}{p-1}\bigg{)}\bigg{(}\prod_{\begin{subarray}{c}p\leq
x\end{subarray}}\frac{p-1}{p}\bigg{)}^{\tau}=a.$

By construction, there exists $N_{1}$ such that $|R(x)-R^{\prime}(x)|\leq
N_{1}$, and we have $|R^{\prime}(x)-R^{\prime\prime}(x)|\leq 1$ for all
$x\in\mathbb{Z}^{+}\\!$, so

$|R^{\prime\prime}(x)-R(x)|\leq N^{\prime}+1.$ (2.9)

Now, by (2.4), we have

$R^{\prime\prime}(x)=\tau\frac{x}{\log x}+O(\frac{x}{\log^{2}x}).$

Also, by (2.5), we have $|R\cap\\{p_{n},\ldots,p_{n+(N^{\prime}+2)N-1}\\}|\geq
2N^{\prime}+3$ for all $n\in\mathbb{Z}^{+}\\!$. By (2.9), we thus get

$|R^{\prime\prime}\cap\\{p_{n},\ldots,p_{n+(N^{\prime}+2)N-1}\\}|\geq 1,$

which, then, completes the proof of Lemma 3. ∎

With that, we have demonstrated Theorem 7. ∎

###### Proof of theorem 12.

The proof of part (1) is an application of Theorem 11. If
$(A_{1},\ldots,A_{h})\in\mathop{\rm MC}\nolimits_{h}$, then
$A_{1}\cup\cdots\cup A_{h}\in\mathop{\rm MB}\nolimits_{h}$ and

$(A_{1}\cup A_{2}\cup\ldots\cup A_{h})(x)\leq
h\max\\{A_{1}(x),\dots,A_{h}(x)\\}.$

It now follows from Theorem 11 that

$\liminf_{x\to\infty}\frac{(A_{1}\cup\cdots\cup A_{h})(x)}{\frac{x}{\log
x}}>1,$

and so

$\liminf_{x\to\infty}\frac{\max\\{A_{1}(x),\ldots,A_{h}(x)\\}}{\frac{x}{\log
x}}>\frac{1}{h},$

which was to be shown.

We now prove part (2). The construction is based on the construction given by
Pach and Sándor in their proof of Theorem 11. Set $[n]=\\{1,\ldots,n\\}$ for
$n\in\mathbb{Z}^{+}$. We shall construct a strictly increasing sequence
$\left(n_{i}\right)_{i}\subseteq\mathbb{Z}^{+}$ and sets
$A_{1}^{i},A_{2}^{i},\ldots A_{h}^{i}\subset[n_{i}]$ such that the following
conditions hold for all $i\geq 1$:

  1. 1.

$A_{1}^{i},A_{2}^{i},\ldots A_{h}^{i}$ are multiplicative complements for
$[n_{i}]$;

  2. 2.

$\max\\{|A_{1}^{i}|,\ldots,|A_{h}^{i}|\\}\leq\left(\frac{1}{h}+\varepsilon\right)\frac{n_{i}}{\log
n_{i}}$;

  3. 3.

$A_{j}^{i}\cap[n_{i-1}]=A_{j}^{i-1}\>\text{for all }1\leq j\leq h$.

The sets $A_{j}=\bigcup_{i}A_{j}^{i}$ for $1\leq j\leq h$ then constitute
multiplicative complements of order $h$. Moreover, condition 3 ensures that
$A_{j}\cap[n_{i}]=A_{j}^{i}$, and by condition 2, we get

$\max\\{A_{1}(n_{i}),\ldots,A_{h}(n_{i})\\}\leq\Big{(}\frac{1}{h}+\varepsilon\Big{)}\frac{n_{i}}{\log
n_{i}}$

and hence

$\liminf_{x\to\infty}\max\\{A_{1}(x),\ldots,A_{h}(x)\\}\frac{\log
x}{x}\leq\frac{1}{h}+\varepsilon.$

Let us set $n_{0}=N=\left\lceil\frac{256}{\varepsilon^{2}}\right\rceil+1$ and
$A_{1}^{0}=A_{2}^{0}=\ldots=A_{h}^{0}=[n_{0}]$. We define the sequence
$\left(n_{i}\right)_{i}$ and the sets $A_{1}^{i},A_{2}^{i},\ldots A_{h}^{i}$
recursively. Setting $x=n_{i}$, we shall pick $y=n_{i+1}$ large enough.
Conditions on $y$ are imposed as we proceed with the proof. The first two
conditions are $x<\frac{\varepsilon}{5}\mkern 2.0muy$ and $x^{2}\\!<y$. We
define

$A_{j}^{i+1}=A_{j}^{i}\cup F_{0}\cup F_{1}\cup F_{2}\cup F_{3}^{j},\text{
where}$

$\displaystyle F_{0}$ $\displaystyle=\left\\{i:x<i<xy^{2/3}\right\\}\\!,$
$\displaystyle F_{1}$
$\displaystyle=\left\\{pv:y^{2/3}<p<\frac{y}{x},\;p\text{ is
prime},\,v\leq\sqrt{x}\right\\}\\!,$ $\displaystyle F_{2}$
$\displaystyle=\left\\{pv:\frac{y}{x}<p\leq\frac{y}{N},\;p\text{ is
prime},\,v\leq\sqrt{\frac{y}{p}}\right\\}\\!,$ $\displaystyle F_{3}^{j}$
$\displaystyle=\left\\{p:\frac{y}{N}<p\leq y,\;p\text{ is
prime}\colon\pi(p)\equiv j\;({\rm mod}\;h)\right\\}\\!.$

Note that if $y>x^{2}$, then we have $\min(y^{2/3},y/x)>x$, so for all $1\leq
j\leq h$, the elements of $A_{j}^{i+1}\setminus A_{j}^{i}$ are larger than
$x$. In particular, condition (3) is met.

We now use induction to show that every number $m:\;1\leq m\leq y$ can be
written in the form $m=st$ with $s\in A_{j}^{i+1}$ and $t\in A_{k}^{i+1}$ for
some $1\leq j\neq k\leq h$. Having this representation implies at once that
$A_{1}^{i+1},A_{2}^{i+1},\ldots,A_{h}^{i+1}$ are multiplicative complements
for $[y]$ since $1\in A_{j}$ for all $1\leq j\leq h$. Pick hence $m\leq y$. It
is easy to see that $m$ can be written as $m=uv$ with $v\leq u$ such that
either $u\leq y^{2/3}$ or $u>y^{2/3}$ is a prime number (e.g., see [2]).

First, assume that $u\leq y^{2/3}$ is a prime number. If $x<v$, then both $u$
and $v$ lie in $(x,y^{2/3}x]$, so we have $u,v\in A_{1}^{i+1}\cap
A_{2}^{i+1}$, and we may write $m=uv$ with $u\in A_{1}^{i+1}$ and $v\in
A_{2}^{i+1}$. If $v\leq x$, then we distinguish two cases:

  * •

If $x<uv$, then $m$ can be written as $m=(uv)\cdot 1$ since $uv$ lies in
$(x,y^{2/3}x]$.

  * •

If $uv\leq x$, then $m=uv$ can be written as $m=st$ with $s\in A_{j}^{i}$,
$t\in A_{k}^{i}$ for some $1\leq j\neq k\leq h$ by the induction hypothesis.

Assume now $u>y^{2/3}$ to be some prime $p$.

  * •

If $y^{2/3}<p\leq y/x$, then $p\in F_{1}\subset A_{1}^{i+1}\cap A_{2}^{i+1}$,
and as $m\leq y$, we have $v=m/p\leq y/p\leq y^{1/3}$. If $x<v$, then $v\in
F_{0}\subset A_{1}^{i+1}\cap A_{2}^{i+1}$, so $m$ can be written as $m=p\mkern
1.0muv$ with $p\in A_{1}^{i+1}$, $v\in A_{2}^{i+1}$. If $v\leq x$, then by the
induction hypothesis, $v$ can be written as $v=v_{1}v_{2}$ with $v_{1}\in
A_{j}^{i}$, $v_{2}\in A_{k}^{i}$ for some $1\leq j\neq k\leq h$. Without loss
of generality, we may assume that $v_{1}\leq v_{2}$. Then, since
$v_{1}\leq\sqrt{v_{1}v_{2}}=\sqrt{v}\leq\\!\sqrt{x}$, we have $p\mkern
1.0muv_{1}\in F_{1}\subset A_{j}^{i+1}\cap A_{k}^{i+1}$ and $v_{2}\in
A_{k}^{i}\subset A_{k}^{i+1}$, and hence $m$ can be written as
$m=(pv_{1})v_{2}$ with $p\mkern 1.0muv_{1}\in A_{j}^{i+1}$, $v_{2}\in
A_{k}^{i+1}$.

  * •

If $y/x<p$ and $y/N\leq p$, then $p\in F_{3}^{1}\cup F_{3}^{2}\cup\ldots\cup
F_{3}^{h}$, so there exists $1\leq j\leq h$ such that $p\in A_{j}^{i+1}$ and
$v=m/p\leq y/p\leq N$. Consequently, there exists $1\leq k\leq h$, $k\neq j$
such that $v\in A_{k}^{i+1}$ since $[N]\subseteq A_{1}^{i+1}\cap\cdots\cap
A_{h}^{i+1}$. In particular, $m$ can be written as $m=p\mkern 1.0muv$.

  * •

If $y/x<p<y/N$, then there exists $j$ with $N\leq j\leq x-1$ and
$y/(j+1)<p\leq y/j$, so we have $v\leq\frac{y}{p}<x$. By the induction
hypothesis, we can find $v_{1}\in A_{j}^{i}$, $v_{2}\in A_{k}^{i}$ for $1\leq
j\neq k\leq h$ such that $v=v_{1}v_{2}$. As before, without loss of
generality, we may assume that $v_{1}\leq v_{2}$, so we have
$v_{1}\leq\sqrt{v}\leq\sqrt{y/p}$. Then, $pv_{1}\in
F_{2}\subset(A_{j}^{i+1}\cap A_{k}^{i+1})$ and $v_{2}\in A_{k}^{i}\subset
A_{k}^{i+1}$, and hence $m$ can be written as $m=(pv_{1})v_{2}$ with
$pv_{1}\in A_{j}^{i+1}$, $v_{2}\in A_{k}^{i+1}$.

This shows that condition (1) is also met.

We now prove that for all $1\leq j\leq h$, condition (2) is met for
$A_{j}^{i+1}$ and $y=n_{i+1}$. If $x^{4}<y$, then

$|A_{j}^{i}\cup F_{0}|=|A_{j}^{i}\cup\\{i:x<i\leq y^{2/3}x\\}|\leq
y^{2/3}x<y^{11/12}<\frac{\varepsilon}{5}\,\frac{y}{\log y}$

for $y$ large enough. Moreover, if $x^{4}<y$ and $x\geq
N>\frac{256}{\varepsilon^{2}}$, then

$\displaystyle|F_{1}|$ $\displaystyle=|\\{pv:y^{2/3}<p\leq y/x,\;p\text{ is a
prime},\;v<\sqrt{x}\\}|$ $\displaystyle\leq\pi(y/x)\sqrt{x}\leq
2\frac{y/x}{\log(y/x)}\sqrt{x}=2\frac{y}{\log
y}\frac{1}{\sqrt{x}}\frac{1}{1-\frac{\log x}{\log
y}}\leq\frac{\varepsilon}{5}\,\frac{y}{\log y}.$

If $y>x^{200/\varepsilon}$, then

$\displaystyle|F_{2}|$ $\displaystyle=|\\{pv:y/x<p\leq y/N,\;p\text{ is a
prime},\;v\leq\sqrt{y/p}\\}|$ $\displaystyle\leq|\\{pv:\exists j:N\leq j\leq
x-1,\;y/(j+1)<p\leq y/j,\;p\text{ is a prime},\;v\leq\sqrt{j+1}\\}|$
$\displaystyle\leq\sum\limits_{j=N}^{x-1}\bigg{(}\pi\Big{(}\frac{y}{j}\Big{)}-\pi\Big{(}\frac{y}{j+1}\Big{)}\bigg{)}\sqrt{j+1}.$

Note that with $x$ fixed and as $y\to\infty$, we have
$\pi\big{(}\frac{y}{j}\big{)}=\frac{y}{j\log y}+o\big{(}\frac{y}{j(\log
y)^{1.5}}\big{)}$, yielding

$\pi\Big{(}\frac{y}{j}\Big{)}-\pi\Big{(}\frac{y}{j+1}\Big{)}=\frac{1}{j(j+1)}\frac{y}{\log
y}+o\Big{(}\frac{y}{j(\log y)^{1.5}}\Big{)}$

(for instance, it suffices to take $y=x^{x}$). Hence, we may write

$\sum\limits_{j=N}^{x-1}\bigg{(}\pi\Big{(}\frac{y}{j}\Big{)}-\pi\Big{(}\frac{y}{j+1}\Big{)}\bigg{)}\sqrt{j+1}=\bigg{(}\sum\limits_{j=N}^{x-1}\frac{1}{j\sqrt{j+1}}\bigg{)}\frac{y}{\log
y}+o\Big{(}\frac{\sqrt{x}}{\sqrt{\log y}}\Big{)}\frac{y}{\log y},$

where

$\sum\limits_{j=N}^{x-1}\frac{1}{j\sqrt{j+1}}<\int_{\frac{256}{\varepsilon^{2}}}^{\infty}\frac{1}{x^{3/2}}dx=\frac{\varepsilon}{8}.$

In particular, we have

$|\\{pv:y/x<p\leq y/N,\;p\text{ is a
prime},\;v\leq\sqrt{y/p}\\}|\leq\frac{\varepsilon}{5}\,\frac{y}{\log y}$

for $y$ large enough relative to $x$. This accounts now for the last term in
the decomposition of $A_{j}^{i+1}$ as

$|F_{3}^{j}|=|\\{p:y/N<p\leq y,\;p\text{ is a prime},\;\pi(p)\equiv j\;{\rm
mod}\;h\\}|\leq
1+\frac{\pi(y)}{h}\leq\left(\frac{1}{h}+\frac{\varepsilon}{5}\right)\frac{y}{\log
y}$

for $y$ sufficiently large. Putting this all together, for all $1\leq j\leq h$
and for $y$ sufficiently large, we get

$|A_{j}^{i+1}|\leq|A_{j}^{i}|+|F_{0}|+|F_{1}|+|F_{2}|+|F_{3}^{j}|\leq\Big{(}\frac{1}{h}+\varepsilon\Big{)}\frac{y}{\log
y},$

completing the proof. ∎

## Bibliography

  * [1] R. C. Baker, G. Harma, J. Pintz, The difference between consecutive primes. II., Proc. London Math. Soc. 83 (2001), no. 3, 532–562.
  * [2] P. Erdős, On sequences of integers no one of which divides the product of two others and on some related problems, Tomsk. Gos. Univ. Uchen. Zap, 2 (1938), 74–82.
  * [3] S. Finch, G. Martin and P. Sebah, Roots of unity and nullity modulo $n$, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2729–2743.
  * [4] P. P. Pach; and C. Sándor, Multiplicative bases and an Erdős problem, Combinatorica 38 (2018), no. 5, 1175–1203.
  * [5] G. Pólya, G. Szegő, Problems and Theorems in Analysis I., Springer 2004\.
  * [6] D. Raikov, On multiplicative bases for the natural series, Matematicheskii Sbornik 45 (1938), no. 3, 569–576.