# First order of the renewal covering of the natural numbers

Alberto M. Campos

###### Abstract

This paper introduces a new type of covering process that covers the set of
natural numbers using renewal processes as objects. Inspired by the behavior
of prime numbers, the model in each step finds the smallest vacant point, $k$,
and place, starting in $k$, a renewal process with a step distribution given
by a geometric random variable with parameter $\frac{1}{k}$. The model depends
on its entire past, and small perturbations in its initial value can lead to
very different outcomes. Here, we expose a technique that finds the first-
order limit behavior for the number of objects placed until $n$, which
exhibits intriguing similarities to prime number distributions, having a
concentration around $n\mathrm{ln}\left(n\right)$.

##  1 Introduction

This paper studies a collection of dependent renewal processes that fully
covers the natural numbers, denoted by ${\mathbb{N}}=\\{1,2,\cdots\\}$. The
problem itself belongs to a class of probability problems related to covering
processes, where given a space, in this case ${\mathbb{N}}$, the process
performs a cover of ${\mathbb{N}}$ using random objects that for us will be
random renewal sets. In function of that, denote this process as a renewal
covering of the natural numbers. The problem treated in this paper resembles
the structure and behavior of prime numbers; this similarity is delicate and
will be addressed clearly after the statements of the theorem. However, when
defining the process, it is interesting for the reader to keep in mind a
parallel to the set of primes.

Given a set of i.i.d. random variable $(G_{k})_{k}$, define the renewal set
associated with the sequence $(G_{k})_{k}$ as the set
$\\{\sum_{k=1}^{n}G_{k}\\}_{n}\subseteq{\mathbb{N}}$. This paper always
considers $G_{k}$ to be distributed as a geometric random variable with some
parameter $p\in[0,1]$, denoted by $\mathrm{Geo}\left(p\right)$, where
$\mathbb{P}\left(\mathrm{Geo}\left(p\right)=k\right)=(1-p)^{k-1}p$ for
$k\in\\{1,2,\cdots\\}$.

Before giving a formal definition of the model, let us describe the process in
words. The process consists of a sequence $(P_{n})_{n}$ constructed through
induction.

  * •

Start by choosing $P_{1}=2$ almost surely.

  * •

In the set of points greater than $P_{1}$, i.e., $\\{3,4,\cdots\\}$, sample
for each point $k$ an independent Bernoulli $\xi_{k}^{1}$ with parameter
$\frac{1}{P_{1}}$ ($=\frac{1}{2}$). Whenever, $\\{\xi_{k}^{1}=1\\}$ occurs, we
say that $k$ is a random multiple of $P_{1}$.

  * •

Let $\mathcal{M}_{1}=\\{k\in\\{3,4,\cdots\\}:\xi_{k}^{1}=1\\}$ be the set of
random multiples of $P_{1}$, then take the smallest natural non-multiple of
$P_{1}$, i.e. $\min\left\\{\\{3,4,\cdots\\}\setminus\mathcal{M}_{1}\right\\}$,
to be the next element of the sequence $P_{2}$.

Notice that, with probability one, the set $\mathcal{M}_{1}$ is different from
$\\{3,4,\cdots\\}$, so one can construct the element $P_{2}$ almost surely.
Moreover, one have that
$P_{2}-P_{1}\sim\mathrm{Geo}\left(\left(1-\frac{1}{2}\right)\right)$.

With $n\geqslant 1$ assume that the elements $P_{1}$,$\cdots$ and $P_{n}$,
with its sets of multiples $\mathcal{M}_{1}$,$\cdots$ and $\mathcal{M}_{n}$.
To find the next pair of elements $P_{n+1}$ and $\mathcal{M}_{n+1}$, do as
follows:

  * •

The element $P_{n+1}$ is going to be the smallest natural greater than
$P_{n}$, that is not multiple of $P_{1}$, $\cdots$ and $P_{n}$, i.e.,
$\min\left\\{\\{P_{n}+1,P_{n}+2,\cdots\\}\setminus\bigcup_{k=1}^{n}\mathcal{M}_{k}\right\\}$.

  * •

With $P_{n+1}$ fixed, sample for each natural $k$ bigger than $P_{n+1}$, an
independent Bernoulli random variable $\xi_{k}^{n+1}$; Then, set
$\mathcal{M}_{n+1}=\\{k\in\\{P_{n+1}+1,P_{n+1}+2,\cdots\\}:\,\xi_{k}^{n+1}=1\\}$.

Equally to the first step in the construction, notice that $P_{n+1}$ exists
almost surely. And, by calculation, we get
$P_{j}-P_{j-1}\sim\mathrm{Geo}\left(\prod_{k=1}^{j}\left(1-\frac{1}{P_{j}}\right)\right)$.

The construction above resembles the structure of prime numbers, where the
next prime is the smallest number that is not a multiple of any previous
prime. However, the problem proposed here is random and depends on all its
past to be described, so the values and behavior of the process can be very
different from those known from algebra. Let us go ahead and say that with
high probability, the value of the random variable $P_{n}$ is different from
the value of the $n-th$ prime.

Locally, the process may be different from the prime numbers, however, it will
be demonstrated that the total number of objects needed to cover the interval
$\\{2,3,\cdots,n\\}$ corresponds in first order to the number of primes up to
the value $n$, that is, the prime counting function $\pi(n)$. Since $P_{n}$ is
not a prime number, to avoid a possible misleading notation, denote $P_{n}$ as
the $n-th$ generator; one can think of it as a random-ideal generator in the
context of algebra.

To describe the process rigorously, consider the space of increasing sequence
$\Omega=\\{(q_{n})_{n}:q_{n}\in{\mathbb{N}},\,q_{n}>q_{n-1}\\}$. Let
$\mathcal{F}_{n}$ be the $\sigma-$algebra generated by the cylinder of size
$n$, that is, $\\{(q_{1},\cdots,q_{k})\in{\mathbb{N}}^{k}:1\leqslant
q_{1}<q_{2}<\cdots<q_{k},\,k\leqslant n\\}$, and set
$\mathcal{F}=\sigma\left(\bigcup_{n}\mathcal{F}_{n}\right)$ the cylinder
$\sigma-$algebra.

In such a measurable space, define inductively the renewal covering of the
natural numbers. For this, define a set of  generators $(P_{n})_{n}$
inductively. Where $P_{1}=2$ almost surely, and for each $n>1$ set:

$\displaystyle P_{n+1}$
$\displaystyle=P_{n}+\mathrm{Geo}\left(\prod_{k=1}^{n}\left(1-\frac{1}{P_{k}}\right)\right).$
(1)

Where, for any $j\geqslant 1$, given a increasing sequence of naturals
$1\leqslant a_{1}<\cdots<a_{n}$, the geometric satisfies:

$\displaystyle\mathbb{P}\left(\mathrm{Geo}\left(\prod_{k=1}^{n}\left(1-\frac{1}{P_{k}}\right)\right)=j\middle|P_{1}=a_{1},\cdots,P_{n}=a_{n}\right)$
$\displaystyle\quad\,\quad\,=\mathbb{P}\left(\mathrm{Geo}\left(\prod_{k=1}^{n}\left(1-\frac{1}{a_{k}}\right)\right)=j\right).$
(2)

In words, this means that the parameter of the geometric depends in the value
of the first $n$ elements, i.e. belongs to
$\mathcal{F}_{n}=\sigma(P_{1},\cdots,P_{n})$, but fixed the values of
$(P_{1},\cdots,P_{n})$ the value of the geometric is independent. To simplify
the notation in the proof, it is worth to define the random parameter:

$\displaystyle\lambda_{n}=\prod_{k=1}^{n}\left(1-\frac{1}{P_{k}}\right).$ (3)

Our result consists of finding the first-order term of the sequence
$(P_{n})_{n}$, thus doing a law of large numbers for such a sequence.

######  Theorem 1.

Consider $(P_{n})_{n}$ a renewal covering of the natural numbers defined
above. Then:

$\displaystyle\frac{P_{n}}{n\mathrm{ln}\left(n\right)}\to 1\quad\text{ almost
surely}.$

At first glance, the model and the result do not seem surprising, since they
consist of a law of large numbers for the sum of geometric random variables.
However, the process depends on all its past,
$P_{n}\in\mathcal{F}_{n-1}=\sigma(P_{1},\cdots,P_{n-1})$, and the model is a
non-Markovian process; small perturbations in its initial value can lead to
very different outcomes. To the best of our knowledge, the way the paper deals
with the dependencies of the process is a novelty.

This idea of creating random prime numbers is not new in the literature.
Landau in 1903, [8], showed using local analytic lemmas how to derive
information about the zeta function using the set of primes. Then, in $1937$,
Beurling proposed an inverse problem, the Beurling generalized prime systems
[3], where fixing a sequence $(P_{n})_{n}$, and controlling the size of the
multiplicative semigroup generated by it, is possible to control how dense
such a set is. The idea behind Beurling’s construction was to create
conditions under which if the prime numbers were satisfied, the Riemann
hypothesis would be true. This line of study is very active and has several
applications and contributions; see Diamond (2005) [5] and Olofsson (2011)
[10].

Another set of techniques, associated with random primes, is to define a
random prime gap with some distribution, usually
$\mathrm{Geo}\left(\ln^{-1}\left(n\right)\right)$. The analyzes of such
sequence of random gaps can provide insight into the behavior of the prime
numbers; see Crammer [4], where in $1936$ he conjectured that the prime gap is
of order $\ln^{2}\left(n\right)$.

This paper shifts the focus of the deterministic zeta function to a random
perspective that tries to see this algebraic structure as some fixed point in
the sense of limiting distribution. The goal is not to create a random model
that copies the prime numbers but to see if in this random process of filling
gaps there exists a deterministic law of large numbers. It is left as an open
problem to determine all the first-order terms for processes where, for some
$\alpha>0$ the generators behave as
$P_{n+1}=P_{n}+\mathrm{Geo}\left(\prod_{k=1}^{n}\left(1-P_{k}^{-\alpha}\right)\right)$.

Another difference between this article and the previous literature is the
notation and the way the results are expressed. Generally, number theory and
renewal theory work with the inverse function, while in this text, due to the
techniques developed, we chose to work with the sequence $(P_{n})_{n}$.
Despite this difference, it is simple to show that, with the concentration of
$P_{n}$, inverting it, the number of generators until $n$ concentrates around
$\frac{n}{\mathrm{ln}\left(n\right)}$.

To clarify some connection’s, due to Dursatt (1999) [7] and Rosser (1941)
[12], the $n-th$ prime $p_{n}$, for $n\geqslant 7$ satisfies:

$\displaystyle
n\mathrm{ln}\left(n\right)+n\ln{\mathrm{ln}\left(n\right)}-n\leqslant
p_{n}\leqslant n\mathrm{ln}\left(n\right)+n\ln{\mathrm{ln}\left(n\right)}.$
(4)

Our proof shows that the renewal covering have the first order term in the
limit behaving equal to the prime number. We believe that the second order
term is also present in the problem, but the same is not true for the third-
order term, leaving open the following conjecture:

######  Conjecture 1.

Consider $(P_{n})_{n}$ a renewal covering of the natural numbers defined
above. Then, there exists a random variable $Z$, such that:

$\displaystyle\frac{P_{n}-n\mathrm{ln}\left(n\right)-n\ln{\mathrm{ln}\left(n\right)}}{n}\overset{D}{\implies}Z,$

where the convergence is in distribution.

Organization. The structure of the paper is organized as follows: Section 2
provides an sketch of the proof. Sections 3 and 4 discuss the behavior of the
random variable $\lambda_{n}$. In Section 5, a type of concentration result
for the sequence $P_{n}$ is exposed. Section 6 translates these fluctuations
into the law of large numbers, thereby proving Theorem 1.

Notations.The set of integers is denoted by
${\mathbb{Z}}=\\{\cdots,-1,0,1,\cdots\\}$, the set of real numbers is going to
be $\mathbb{R}$. The symbol $\forall$ means "for all" and the symbol $\exists$
means "exists".

Acknowledgment. The author would like to thank Marco Aymone for his insightful
discussions and valuable information regarding the literature on random
primes.

##  2 Proof Sketch of the proof

The proof of Theorem 1 consists of a long argument with three main steps. This
outline will briefly explain each step, providing the general goals of the
main result. To motivate the reader, the explanation given here follows a
natural order (not the order of the proof). The best way to explain the proof
is to start with the objective of the second step, then show a brief argument
on how to finish the proof of the theorem, and finally explain the initial
step.

The main objective of the proof is to smooth out the dependence that exists in
the sequence $(P_{n})_{n}$. For this, in the second step of the proof, we
expose a concentration result for the sequence $(P_{n})_{n}$ that resembles
what is expected for the sums of independent geometric random variables.
Specifically, remember the definition of the parameter
$\lambda_{n}=\prod_{k=1}^{n}\left(1-\frac{1}{P_{k}}\right)$ and the fact that
$P_{n}$ is a sum of geometric random variables with parameter $\lambda_{n}$.
Then, for every $\varepsilon>0$ and $\alpha>1$, there exists
$n_{0}=n_{0}(\varepsilon,\alpha)$, such that with high probability:

$\displaystyle\mathbb{P}\left(\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|<\sqrt{n^{\alpha}},\,\forall
n>n_{0}\right)>1-\varepsilon.$ (5)

At first glance, this probability gives the concentration of the problem.
However, notice that $\lambda_{n}$ is also an unknown random variable. The
reader can think that result (5) is as a pseudo-concentration, that shows that
two random variables, $\mathcal{F}_{n}$ measurable, are close together.

The second object in this proof is subtle, but has a nice explanation.
Basically, it consists of transforming the pseudo concentration (5) into a law
of large numbers. To briefly explain how, start by recalling that any random
variable $\mathcal{F}_{n}$ measurable is written as a function $F$ of the
values of $P_{1}$, $\cdots$, $P_{n}$. Therefore, equation (5) has two
possibilities: The first case is when the difference between the random
variables is trivially true, and the second case is when the difference is not
trivial and thus not every sequence $(P_{n})_{n}$ will satisfy the equation.
For example, the function $F(x_{1},\cdots,x_{n})=x_{n}$ implies that
$P_{n}-F(P_{1},\cdots,P_{n})=0$ for every $n$, but the function
$F(x_{1},\cdots,x_{n})=x_{1}+\cdots+x_{n}$ implies that $P_{n}$ is close to
its summation; by some approximations, it is possible to relate the growth of
$P_{n}$ with an exponential growth (the only type in which its value is close
to its integral).

Curiously, in this paper, the inequality leads to an integral inequality that
can be related to a differential equation, and another field appears. The
solutions of the differential equation is the inverse function of the
logarithmic integral function, believed to be the right order of $\pi(n)$ see
[1]. In particular, the solution have a growth of order
$n\mathrm{ln}\left(n\right)+n\mathrm{ln}\left(\mathrm{ln}\left(n\right)\right)$,
and by some comparative arguments one can conclude that the values of $P_{n}$
are close to the solution of this differential equation.

The first step in proof, and what will imply in the pseudo-concentration, is a
tightness problem. As mentioned, when conditioning in the set of parameters
$\lambda_{n}$, the quenched problem satisfies the equation (5). To go from
quenched space to annealed space, the sequence $\lambda_{n}$ has to belong
with high probability to a specific set of sequences. More precisely,
$\lambda_{n}$ is going to be tight in the space of slowly varying sequences,
the sequences $(a_{n})_{n}$ such that for every $t>0$, $\frac{a_{nt}}{a_{n}}$
converges to one when $n$ grows.

##  3 Stochastic Domination

Let $X$ and $Y$ be two random variables, we say that $X$ stochastic dominate
$Y$ if $\mathbb{P}\left(X\geqslant x\right)\geqslant\mathbb{P}\left(Y\geqslant
x\right)$ for every $x\in\mathbb{R}$, whenever this happens, denote it as
$X\succeq_{est}Y$ or $Y\preceq_{est}X$. Specifically for geometric random
variables, let $1\geqslant p>q\geqslant 0$, when
$X\sim\mathrm{Geo}\left(q\right)$ and $Y\sim\mathrm{Geo}\left(p\right)$, then
$X\succeq_{est}Y$.

Stochastic domination is not concerned with the independence of random
variables. Therefore, just the fact that $X_{k}\succeq_{est}Y_{k}$ for every
$k\geqslant 0$ is not enough to conclude that
$\sum_{k=1}^{n}X_{k}\succeq_{est}\sum_{k=1}^{n}Y_{k}$. However, considering
the condition that the sequences $(X_{k})_{k}$ and $(Y_{k})_{k}$ are
independent, one can use the stochastic domination in each term to dominate
the sum. The renewal coverage o ${\mathbb{N}}$ does not satisfy the
independence condition, but due to the hypothesis imposed by the equation (1)
that condition on the values of $P_{n}$ the geometric random variable is
independent, it is possible to find similar results given specific events.

######  Lemma 1.

Let integers $n\geqslant 0$ and $m>0$, and set any $p\in[0,1]$. Define
$(G_{k})_{k}$ as an i.i.d. sequence, where
$G_{k}\sim\mathrm{Geo}\left(p\right)$. Then:

$\displaystyle\mathbf{1}\\{\lambda_{m}\leqslant
p\\}\sum_{k=m}^{m+n}\mathrm{Geo}\left(\lambda_{k}\right)$
$\displaystyle\succeq_{est}\mathbf{1}\\{\lambda_{m}\leqslant
p\\}\sum_{k=m}^{m+n}G_{k}.$

###### Proof.

The idea of the proof is to observe that $(\lambda_{n})_{n}$ is a monotonous
sequence, then if at some point the parameter become smaller than $p$, it will
stay smaller than $p$. Therefore, after this moment the parameter is smaller
than $p$, and the increment of the problem at each step stochastic dominates
an independent geometric with parameter $p$.

To be rigorous, the proof uses induction. Start by fixing $m>0$ and
$p\in[0,1]$. In the initial case, when $n=0$, define
$\Gamma_{m}^{0}=\\{(a_{1},\cdots,a_{m})\in{\mathbb{N}}^{m}:\prod_{k=1}^{m}\left(1-\frac{1}{a_{k}}\right)\leqslant
p,\,2\leqslant a_{1}<a_{2}<\cdots<a_{m}\\}$, and for any $x\in\mathbb{R}$, the
problem satisfies the following:

$\displaystyle\mathbb{P}\Big{(}\lambda_{m}\leqslant p\,$
$\displaystyle;\,\mathrm{Geo}\left(\lambda_{m}\right)\geqslant\,x\Big{)}$
$\displaystyle=\sum_{\vec{a}\in\Gamma_{m}^{0}}\mathbb{P}\left(\mathrm{Geo}\left(\lambda_{m}\right)\geqslant
x\,\middle|(P_{1},\cdots,P_{m})=\vec{a}\right)\mathbb{P}\left((P_{1},\cdots,P_{m})=\vec{a}\right).$

By condition (1) and independence of the random variables, since
$\mathrm{Geo}\left(q\right)\succeq_{est}\mathrm{Geo}\left(p\right)$ for any
values of $1\geqslant p>q\geqslant 0$, one get that:

$\displaystyle\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\mathrm{Geo}\left(\lambda_{m}\right)\geqslant x\right)$
$\displaystyle=\sum_{\vec{a}\in\Gamma_{m}^{0}}\mathbb{P}\left(\mathrm{Geo}\left(\prod_{k=1}^{m}\left(1-\frac{1}{a_{k}}\right)\right)\geqslant
x\right)\mathbb{P}\left((P_{1},\cdots,P_{m})=\vec{a}\right)$
$\displaystyle\geqslant\mathbb{P}\left(\lambda_{m}\leqslant
p\right)\mathbb{P}\left(G_{m}\geqslant
x\right)=\mathbb{P}\left(\lambda_{m}\leqslant p\,;\,G_{m}\geqslant x\right).$

Now, assume for any fixed $n-1\geqslant 0$ that:

$\displaystyle\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\sum_{k=m}^{m+n-1}\mathrm{Geo}\left(\lambda_{k}\right)\geqslant
x\right)\geqslant\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\sum_{k=m}^{m+n-1}G_{k}\geqslant x\right),\,\forall x\in\mathbb{R}.$ (6)

We are going to prove the same inequality for $n$. Let
$\Gamma^{n}_{m}=\\{(a_{1},\cdots,a_{m+n})\in{\mathbb{N}}^{m+n}:\prod_{k=1}^{m}\left(1-\frac{1}{a_{k}}\right)\leqslant
p,\,2\leqslant a_{1}<a_{2}<\cdots<a_{m+n}\\}$. Then, using condition (1), for
any $x\in\mathbb{R}$, it is true that:

$\displaystyle\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\sum_{k=m}^{m+n}\mathrm{Geo}\left(\lambda_{k}\right)\geqslant x\right)$
$\displaystyle=\sum_{\vec{a}\in\Gamma_{m}^{n}}\mathbb{P}\left(\mathrm{Geo}\left(\prod_{k=1}^{m+n}\left(1-\frac{1}{P_{k}}\right)\right)+P_{m+n-1}\geqslant
x+P_{m-1}\,;\,(P_{1},\cdots,P_{m+n})=\vec{a}\right)$
$\displaystyle=\sum_{\vec{a}\in\Gamma_{m}^{n+1}}\mathbb{P}\left(\mathrm{Geo}\left(\prod_{k=1}^{m+n}\left(1-\frac{1}{a_{k}}\right)\right)+a_{m+n-1}\geqslant
x+a_{m-1}\right)\mathbb{P}\left((P_{1},\cdots,P_{m+n})=\vec{a}\right)$
$\displaystyle\geqslant\sum_{\vec{a}\in\Gamma_{m}^{n+1}}\mathbb{P}\left(\mathrm{Geo}\left(p\right)+a_{m+n-1}\geqslant
x+a_{m-1}\right)\mathbb{P}\left((P_{1},\cdots,P_{m+n})=\vec{a}\right)$
$\displaystyle=\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,G_{m+n}+\sum_{k=m}^{m+n-1}\mathrm{Geo}\left(\lambda_{k}\right)\geqslant
x\right).$

Now, since $G_{m+n}$ is independent, conditioning in its value and using the
induction hypotheses of equation (6) , one get that:

$\displaystyle\mathbb{P}\Bigg{(}\lambda_{m}\leqslant p\,$
$\displaystyle;\,G_{m+n}+\sum_{k=m}^{m+n-1}\mathrm{Geo}\left(\lambda_{k}\right)\geqslant
x\Bigg{)}=$
$\displaystyle=\sum_{\ell=1}^{\infty}\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\sum_{k=m}^{m+n-1}\mathrm{Geo}\left(\lambda_{k}\right)\geqslant
x-\ell\right)\mathbb{P}\left(G_{n+m}=\ell\right)$
$\displaystyle\geqslant\sum_{\ell=1}^{\infty}\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\sum_{k=m}^{m+n-1}G_{k}\geqslant
x-\ell\right)\mathbb{P}\left(G_{n+m}=\ell\right)$
$\displaystyle=\mathbb{P}\left(\lambda_{m}\leqslant
p\,;\,\sum_{k=m}^{m+n}G_{k}\geqslant x\right).$

As desired. ∎

Analogously to the Lemma 1, it is possible to get the other side of the
stochastic domination.

######  Lemma 2.

Let $n>0$ be an integer and set $p\in[0,1]$. Define $(G_{k})_{k}$ as an i.i.d.
sequence, where $G_{k}\sim\mathrm{Geo}\left(p\right)$. Then:

$\displaystyle\mathbf{1}\\{\lambda_{k}\geqslant p,\forall k\geqslant
0\\}\sum_{k=1}^{n}\mathrm{Geo}\left(\lambda_{k}\right)$
$\displaystyle\preceq_{est}\mathbf{1}\\{\lambda_{k}\geqslant p,\forall
k\geqslant 0\\}\sum_{k=1}^{n}G_{k}.$

The proof is analogous and can be done following the same steps proved in
Lemma 1, so it is left as an exercise.

To make full use of the stochastic domination with respect to the sum of
independent geometric random variables, consider the classical result of large
deviation theory; see Section 2.7 of Durrett [6] for a proof.

######  Proposition 1.

Let $p\in[0,1]$, and $(G_{k})_{k}$ and i.i.d. sequence with
$G_{k}\sim\mathrm{Geo}\left(p\right)$. Then, for every $\varepsilon>0$, there
exists a value $\mathcal{I}(\varepsilon)>0$ such that:

$\displaystyle\mathbb{P}\left(\left|\sum_{k=1}^{n}G_{k}-\frac{n}{p}\right|>\varepsilon
n\right)\leqslant\exp\\{-n\mathcal{I}(\varepsilon)\\}.$

With all the initial results and definitions of the stochastic domination, it
is possible to give the first two lemmas about the sequence $(P_{n})_{n}$ and
$(\lambda_{n})_{n}$. More specifically, it will be shown that almost surely
$\lambda_{n}$ converges to zero and that $(P_{n})_{n}$ grows faster than any
linear function.

######  Lemma 3.

The sequence $(\lambda_{n})_{n}$ converges to zero with probability one.

###### Proof.

For any $n>0$, the value of $\lambda_{n}$ is a product of numbers less than
one; therefore, it is a monotone bounded decreasing sequence and must converge
to some number with probability one. Now, assuming by absurd that it do not
converge to zero almost surely, then there exists an $c\in(0,1)$ such that:

$\displaystyle\mathbb{P}\left(\lambda_{n}\geqslant c,\,\forall n>0\right)>0.$
(7)

To finish, we are going to show that there exists an event $A$, such that
$\\{\\{\lambda_{n}\geqslant c,\,\forall n>0\\}\,;\,A\\}$ have the same
probability of the events $\\{\\{\lambda_{n}\geqslant c,\,\forall
n>0\\}\,;\,A^{c}\\}$ and $\\{\lambda_{n}\geqslant c,\,\forall n>0\\}$.
Implying that equation (7) is false, concluding this proof.

Notice that if $\\{\lambda_{n}\geqslant c,\,\forall n>0\\}$ occur, using the
formula of $\lambda_{n}$ in (3), and that $1-x\leqslant e^{-x}$ for all $x>0$,
one gets that:

$\displaystyle
c\leqslant\lambda_{n}=\prod_{k=1}^{n}\left(1-\frac{1}{P_{k}}\right)\leqslant\exp\\{-\sum_{k=1}^{n}\frac{1}{P_{k}}\\}.$

And thus, the summation $\sum_{k=1}^{n}\frac{1}{P_{k}}$ must converge. Then:

$\displaystyle\left\\{\lambda_{n}\geqslant c,\,\forall n>0\right\\}$
$\displaystyle=\left\\{\lambda_{n}\geqslant c,\,\forall
n>0\,;\,\sum_{k=1}^{\infty}\frac{1}{P_{k}}<\infty\right\\},\text{ and }$
$\displaystyle\mathbb{P}\left(\lambda_{n}\geqslant c,\,\forall n>0\right)$
$\displaystyle=\mathbb{P}\left(\lambda_{n}\geqslant c,\,\forall
n>0\,;\,\sum_{k=1}^{\infty}\frac{1}{P_{k}}<\infty\right).$

On the other hand, assuming that $\\{\lambda_{n}\geqslant c,\,\forall n>0\\}$
occurs, by Lemma 2, it is possible to stochastically dominate the random
variable $P_{n}$. Let $(G_{k})_{k}$ and i.i.d. sequence where
$G_{k}\sim\mathrm{Geo}\left(c\right)$, then:

$\displaystyle\mathbf{1}\\{\lambda_{n}\geqslant c,\forall n\geqslant
0\\}\sum_{k=1}^{n}\mathrm{Geo}\left(\lambda_{k}\right)$
$\displaystyle\preceq_{est}\mathbf{1}\\{\lambda_{n}\geqslant c,\forall
n\geqslant 0\\}\sum_{k=1}^{n}G_{k}.$ (8)

Since $P_{n}=2+\sum_{k=1}^{n}\mathrm{Geo}\left(\lambda_{k}\right)$, it is
possible to control its value using the independent sum of the geometric
random variable in the equation (8). Using the large deviation of Proposition
1 together with Borel-Cantelli, it is possible to conclude that the event
$\\{\exists n_{0}\text{ s.t. }P_{n}<\frac{2n}{c},\,\forall n>n_{0}\\}$ occurs
with probability one. But, if $P_{n}<\frac{2n}{c}$ for every $n>n_{0}$, then
$\sum_{k=1}^{\infty}\frac{1}{P_{k}}$ diverges. Thus:

$\displaystyle\mathbb{P}\left(\lambda_{n}\geqslant c,\,\forall
n\right)=\mathbb{P}\left(\lambda_{n}\geqslant c,\forall
n\,;\,\sum_{k=1}^{\infty}\frac{1}{P_{k}}=\infty\right).$

Concluding that for every $c>0$ the probability of the event
$\\{\lambda_{n}\geqslant c,\,\forall n>0\\}$ must be zero, and with
probability one, one get that $(\lambda_{n})_{n}$ converges to zero. ∎

######  Lemma 4.

For every $C>0$, the sequence $(P_{n})_{n}$ satisfies the following:

$\displaystyle\mathbb{P}\left(\exists n_{0}\text{ s.t. }P_{n}>Cn,\,\forall
n>n_{0}\right)=1.$

###### Proof.

This proof uses a similar approach of the stochastic domination in Lemma 3
where it is proven that $\lambda_{n}$ converges to zero almost surely. Here,
it is going to be used the stochastic domination of Lemma 1, where the random
variables $P_{n}$ will eventually dominates the sum of i.i.d. geometric random
variables with arbitrary small parameters, implying that $P_{n}>Cn$ for every
$C>0$ and $n$ large enough.

Notice that $(\lambda_{n})_{n}$ is a monotonous decreasing sequence with
probability one. Moreover, by Lemma 3, the sequence $(\lambda_{n})_{n}$
converges almost surely to zero, implying that for every $C>0$ and every small
$\varepsilon>0$, there exists a $n_{1}=n_{1}(\varepsilon,C)$ such that for
every $n>n_{1}$:

$\displaystyle\mathbb{P}\left(\lambda_{n}\leqslant\frac{1}{2C}\right)\geqslant
1-\varepsilon.$ (9)

Furthermore, when the parameter becomes smaller than $\frac{1}{2C}$, the
increment of the sequence $P_{n}$ will dominate a geometric random variable
with a parameter $\frac{1}{2C}$. Thus, letting $(G_{k})_{k}$ an i.i.d.
sequence where $G_{k}\sim\mathrm{Geo}\left(\frac{1}{2C}\right)$, using Lemma
1, one gets that:

$\displaystyle\mathbf{1}\left\\{\lambda_{n_{1}}\leqslant\frac{1}{2C}\right\\}P_{n_{1}+n}\succeq_{est}\mathbf{1}\left\\{\lambda_{n_{1}}\leqslant\frac{1}{2C}\right\\}\sum_{k=1}^{n}G_{k}.$
(10)

To finalize the proof, one can use Proposition 1 (large deviation principle)
and Borel Cantelli lemma, to get that the event $\\{\exists n_{0}\text{ s.t.
}$ $\sum_{k=1}^{n}\mathrm{Geo}\left(\frac{1}{2C}\right)>Cn,\,\forall
n>n_{0}\\}$ happens with probability one. Since $n_{1}=n_{1}(\varepsilon,C)$
is finite, using the probability of equation (9), one get:

$\displaystyle\mathbb{P}\left(\lambda_{n_{1}}\leqslant\frac{1}{2C}\,;\,\left\\{\exists
n_{0}\text{ s.t.
}\sum_{k=1}^{n}\mathrm{Geo}\left(\frac{1}{2C}\right)>Cn,\,\forall
n>n_{0}\right\\}\right)=\mathbb{P}\left(\lambda_{n_{1}}\leqslant\frac{1}{2C}\right)\geqslant
1-\varepsilon.$

Which concludes by stochastic domination in equation (10), that for every
$\varepsilon>0$:

$\displaystyle\mathbb{P}\left(\exists n_{0}\text{ s.t. }P_{n}>Cn,\,\forall
n>n_{0}\right)\geqslant 1-\varepsilon.$

And, since $\varepsilon>0$ is arbitrary, we conclude the proof. ∎

##  4 Tightness in the slowly varying

Our goal now is to find the fluctuations of the random variable $\lambda_{n}$
when $n$ is large. For this, we will show that the sequence $\lambda_{n}$
belongs to a class of sequences that have a well behavior at infinity with
probability one. Specifically, the set of slowly varying functions; see
Chapter 0 from [11]. Moreover, to be self-contained in this subsection, we
adapted the theory of slowly varying functions and prove the theorems needed
for our result.

For any number $x\in\mathbb{R}$, and sequence $(\gamma_{n})_{n}$, define
$\gamma(x)=\gamma_{\lceil x\rceil}$. Then, we say that $\gamma$ is slowly
varying at infinity if for every $t>0$, one get that:

$\displaystyle\lim_{x\to\infty}\frac{\gamma(xt)}{\gamma(x)}=1.$

Moreover, denote by $\mathrm{SV}_{0}$ the set of all slowly varying sequences
at infinity.

######  Lemma 5.

The random sequence $(\lambda_{n})_{n}$ belongs to $\mathrm{SV}_{0}$ with
probability one. More than this, for every $\varepsilon>0$, $\delta>0$ and
$t>0$, there exists $x_{0}=x_{0}(\varepsilon,\delta,t)$ such that:

$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\lambda(xt)}{\lambda(x)}\leqslant
1+\delta,\,\forall x>x_{0}\right)>1-\varepsilon.$ (11)

The quantitative equation 11 is reefer as a tightness result. To be precise,
note that $0<\lambda(x)\leqslant\frac{1}{2}$, and $(\lambda_{n})_{n}$ is a
monotonous decreasing sequence. Then, Lemma 5 shows that the random function
$\frac{\lambda(xt)}{\lambda(x)}$ concentrates its probability mass in the
compact $\prod_{k=1}^{\lfloor x_{0}\rfloor}[0,2]\times\prod_{k=\lceil
x_{0}\rceil}^{\infty}[1-\delta,1+\delta]$ (infinite product of compacts).

###### Proof.

This proof uses the Lemma 4 which proves $P_{n}$ grows faster than any linear
function, to show that the ratio $\frac{\lambda(xt)}{\lambda(x)}$ is close to
one with high probability.

For this, fix $t\geqslant 1$, then by the definition (3):

$\displaystyle\frac{\lambda(xt)}{\lambda(x)}$
$\displaystyle=\frac{\prod\limits_{k=1}^{\lfloor
xt\rfloor}\left(1-\frac{1}{P_{k}}\right)}{\prod\limits_{j=1}^{\lfloor
x\rfloor}\left(1-\frac{1}{P_{j}}\right)}=\prod_{k=\lceil x\rceil}^{\lfloor
xt\rfloor}\left(1-\frac{1}{P_{k}}\right).$

Since $P_{n}$ is a monotonous sequence and bigger than $2$ almost surely,
using that $1-x\leqslant e^{-x}$, one can concludes with $t\geqslant 1$ that:

$\displaystyle\left(1-\frac{1}{P_{\lceil x\rceil}}\right)^{x(t-1)}$
$\displaystyle\leqslant\frac{\lambda(xt)}{\lambda(x)}\leqslant 1,\text{ that
implies }$ $\displaystyle\exp\left\\{-\frac{x(t-1)}{2P_{\lceil
x\rceil}}\right\\}$
$\displaystyle\leqslant\frac{\lambda(xt)}{\lambda(x)}\leqslant 1.$ (12)

Using Lemma 4, for every $C>0$, exists $n_{1}=n_{1}(C,\varepsilon)$ such that:

$\displaystyle\mathbb{P}\left(P_{n}>Cn,\,\forall
n>n_{1}\right)=\sum_{k=0}^{n_{1}}\mathbb{P}\left(P_{k}<Ck,\,\\{P_{n}>Cn,\,\forall
n>k\\}\right)>1-\varepsilon.$

In particular, fixing $t\geqslant 1$ and any $\delta>0$, there exists
$C=C(\delta,t)$ accordingly so that

$\displaystyle\exp\left\\{-\frac{x(t-1)}{2Cx}\right\\}>1-\delta,$

now taking $x_{0}=x_{0}(\varepsilon,\delta,t)=\lceil n_{1}\rceil$, one get
deterministically by equation (12) that if $\\{P_{n}>Cn,\,\forall n>n_{1}\\}$
occurs, then the ratio $\frac{\lambda(xt)}{\lambda(x)}$ belongs to
$(1-\delta,1]$, implying that:

$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\lambda(xt)}{\lambda(x)}\leqslant
1,\,\forall x>x_{0}\right)\geqslant\mathbb{P}\left(P_{n}>Cn,\,\forall
n>n_{1}\right)\geqslant 1-\varepsilon.$

Now, when $t\in(0,1)$, the problem satisfy:

$\displaystyle
1\leqslant\frac{\lambda(xt)}{\lambda(x)}\leqslant\left(1-\frac{1}{P_{\lceil
x\rceil}}\right)^{-x(1-t)}\leqslant\exp\left\\{\frac{x(1-t)}{P_{\lceil
x\rceil}}\right\\}$ (13)

Then, by choosing another value of $C=C(\delta,t)$ accordingly, one gets that
there exists $x_{0}^{*}=x_{0}^{*}(\varepsilon,\delta,t)$ such that that:

$\displaystyle\mathbb{P}\left(1\leqslant\frac{\lambda(xt)}{\lambda(x)}\leqslant
1+\delta,\,\forall x>x_{0}^{*}\right)\geqslant 1-\varepsilon.$

Moreover, by equation (11), since $\delta$ and $\varepsilon$ are arbitrary,
$(\lambda_{n})_{n}$ is monotonous, then one gets
$\lambda(x)\in\mathrm{SV}_{0}$ almost surely. Concluding the proof. ∎

The above result is also true for some sequences related to $\lambda_{n}$.
Specifically:

######  Corollary 1.

The random sequences $(\lambda_{n}^{-1})_{n}$ and $(\lambda_{n})^{-2}$ belongs
to $\mathrm{SV}_{0}$ with probability one. Moreover, for every
$\varepsilon>0$, $\delta>0$ and $t>0$, there exists
$x_{0}=x_{0}(\varepsilon,\delta,t)$ such that:

$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\lambda^{-1}(xt)}{\lambda^{-1}(x)}\leqslant
1+\delta,\,\forall x>x_{0}\right)>1-\varepsilon,$
$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\lambda^{-2}(xt)}{\lambda^{-2}(x)}\leqslant
1+\delta,\,\forall x>x_{0}\right)>1-\varepsilon.$

The proof follows the same ideas of Lemma 5, just noticing that if
$\sqrt{1-\delta}\leqslant\frac{\lambda^{-1}(xt)}{\lambda^{-1}(x)}\leqslant\sqrt{1+\delta}$,
then $1-\delta\leqslant\frac{\lambda^{-2}(xt)}{\lambda^{-2}(x)}\leqslant
1+\delta$. So, we left this proof as an exercise.

For slowly varying sequences $(\gamma_{n})_{n}$, it is possible to control the
sum of the values $\sum_{k=1}^{n}\frac{1}{\gamma_{n}}$ with some precision.
The theorem that propose such relation is called Karamatha’s theorem. In
essence, by controlling the fraction $\frac{\gamma^{-1}(xt)}{\gamma(x)}$, it
is possible to control the summation of these values, see Theorem 0.6 in S. I.
Resnick [11].

In this paper, it is not possible to directly apply Karamatha’s theorem, since
the sequence $\lambda_{n}$ is a distribution over $\mathrm{SV}_{0}$, and not
just a fixed sequence. To solve this, it is worth to observe the proof of such
theorems with some attention. Therefore, a simplified version of the original
theorem is proved.

######  Proposition 2 (Karamatha).

Consider any deterministic function $\gamma(x)\in\mathrm{SV}_{0}$, such that
$\gamma(x)>0$ for all $x>0$, then:

A- For every $\alpha>0$, one get that
$\lim\limits_{x\to\infty}x^{-\alpha}\gamma(x)=0.$

B- If $\gamma(x)$ is a monotonous increasing function, one get that:

$\displaystyle\lim\limits_{x\to\infty}\frac{\sum\limits_{k=1}^{x}\gamma(k)}{x\gamma(x)}=1.$

###### Proof.

To prove affirmation A with fixed $\gamma\in\mathrm{SV}_{0}$, take any $t>1$,
$\alpha>0$, and find $\delta>0$ that satisfies $1+\delta<t^{\alpha}$. Using
the definition of slowly varying functions, there exists
$x_{1}=x_{1}(\delta,t)$ such that for every $x>x_{1}$:

$\displaystyle\frac{\gamma(xt)}{\gamma(x)}\leqslant 1+\delta.$ (14)

This implies that for any $x>x_{1}$, there exist $x^{*}=x^{*}(x,x_{1})$ and an
integer $n\geqslant 0$, such that $x=x^{*}t^{n}$ for some
$x^{*}\in(x_{1},tx_{1}]$; Thus:

$\displaystyle
0\leqslant\frac{\gamma(x)}{x^{\alpha}}=\frac{\gamma(x^{*}t^{n})}{(x^{*}t)^{\alpha
n}}$ $\displaystyle=\frac{1}{(x^{*}t)^{\alpha
n}}\frac{\gamma(x^{*}t^{n})}{\gamma(x^{*}t^{n-1})}\cdots\frac{\gamma(x^{*}t)}{\gamma(x^{*})}\gamma(x^{*})$
$\displaystyle\leqslant\frac{\gamma(x^{*})}{{x^{*}}^{\alpha}}\left(\frac{1+\delta}{t^{\alpha}}\right)^{n}\leqslant\left(\frac{1+\delta}{t^{\alpha}}\right)^{n}\sup_{y\in(x_{1},tx_{1}]}\frac{\gamma(y)}{y^{\alpha}}.$
(15)

Since $1+\delta<t^{\alpha}$, one can conclude that
$\frac{1+\delta}{t^{\alpha}}<1$. Then, taking $x$ growing to $\infty$, since
the supreme is a finite number, one gets that $x^{-\alpha}\gamma(x)$ converges
to zero. Finishing the proof of A.

The proof B consists in finding an upper and lower bound for the summation
$\sum\limits_{k=1}^{x}\gamma(k)$. Fixing any integer $\ell>1$ and $\delta>0$,
using the fact that $\gamma(x)\in\mathrm{SV}_{0}$, there exists
$x_{0}(\delta,\ell)$ such that for every $x>x_{0}$:

$\displaystyle
1-\delta\leqslant\frac{\gamma\left(x\frac{j}{\ell}\right)}{\gamma(x)}\leqslant
1+\delta,\quad\forall j\in\\{1,\cdots,\ell\\}.$ (16)

Therefore, by the monotonicity of $\gamma(x)$, it is possible to conclude
that:

$\displaystyle\frac{\sum\limits_{k=1}^{x}\gamma(k)}{x\gamma(x)}$
$\displaystyle=\sum_{j=0}^{\ell-1}\frac{1}{x\gamma(x)}\sum_{k=\frac{j}{\ell}x+1}^{\frac{j+1}{\ell}x}\gamma(k)\leqslant\sum_{j=0}^{\ell-1}\frac{\frac{x}{\ell}\gamma\left(x\frac{j+1}{\ell}\right)}{x\gamma(x)}\leqslant
1+\delta.$

For the other side, note that:

$\displaystyle\frac{\sum\limits_{k=1}^{x}\gamma(k)}{x\gamma(x)}\geqslant\frac{\sum\limits_{k=1}^{\frac{x}{\ell}}\gamma(k)}{x\gamma(x)}+\frac{\ell-1}{\ell}(1-\delta)\geqslant\frac{\ell-1}{\ell}(1-\delta).$

In particular, for any $\ell>0$ fixed and $\delta>0$, there exists a
$x_{0}(\delta,\ell)$ such that for every $x>x_{0}$:

$\displaystyle(1-\delta)-\frac{(1-\delta)}{\ell}\leqslant\frac{\sum_{k=1}^{x}\gamma(k)}{x\gamma(x)}$
$\displaystyle\leqslant 1+\delta.$ (17)

The proof of affirmation B follows by choosing the value of $\delta$ and
$\ell$ accordingly. ∎

######  Remark 1.

The theorem proposed in Proposition 2 is simpler than the actual Karamatha’s
theorem, for more detail see Theorem 0.6 of [11].

Now, back to the random sequence $\lambda(x)$, it is possible to approximate
Karamatha’s theorems with high probability. Specifically:

######  Proposition 3.

For all $\varepsilon>0$ and $\delta>0$, there exists
$x_{0}=x_{0}(\varepsilon,\delta)$ such that:

$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\sum_{k=1}^{x}\frac{1}{\lambda(k)}}{\frac{x}{\lambda(x)}}\leqslant
1+\delta,\,\forall x>x_{0}\right)>1-\varepsilon.$ (18)

Moreover, for every $\alpha>0$ and $\eta>0$, there exists
$x_{1}=x_{1}(\varepsilon,\eta,\alpha)$ such that:

$\displaystyle\mathbb{P}\left(x^{-\alpha}\frac{1}{\lambda(x)}\leqslant\eta,\,\forall
x>x_{1}\right)>1-\varepsilon.$ (19)

###### Proof.

Using Corollary 1, for any $\varepsilon>0$, $\delta>0$, and $\ell>0$, there
exists $x_{0}=x_{0}(\varepsilon,\delta,\ell)$ such that

$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\lambda^{-1}\left(x\frac{j}{\ell}\right)}{\lambda^{-1}(x)}\leqslant
1+\delta,\forall x>x_{0},\,\forall
j\in\\{1,\cdots,\ell\\}\right)>1-\varepsilon.$ (20)

Then, by Karamathas’s Proposition 2, more precisely by equation (17), it is
true that:

$\displaystyle\mathbb{P}\left(1-\delta-\frac{(1-\delta)}{\ell}\leqslant\frac{\sum_{k=1}^{x}\frac{1}{\lambda(k)}}{\frac{x}{\lambda(x)}}\leqslant
1+\delta,\,\forall x>x_{0}\right)>1-\varepsilon.$

Again, by choosing $\delta$ and $\ell$ accordingly, one can conclude the
equation (18) as desired.

Now, to show equation (19), with fixed $\alpha>0$, $\eta>0$ and
$\varepsilon>0$, fix $t=2$, and let $\delta=\delta(\alpha)<2^{\alpha}-1$. In
particular, one get by Corollary 1, that there exists
$x_{1}^{\prime}=x_{1}^{\prime}(\varepsilon,\delta(\alpha))$ such that:

$\displaystyle\mathbb{P}\left(\frac{\frac{1}{\lambda(2x)}}{\frac{1}{\lambda\left(x\right)}}\leqslant
1+\delta,\forall x>x_{1}^{\prime}\right)>1-\frac{\varepsilon}{2}.$

Therefore, by equation (15) of Proposition 2, it is possible to concludes
that:

$\displaystyle\mathbb{P}\left(\frac{1}{x^{\alpha}\lambda(x)}\leqslant\eta,\forall
x>x_{1}^{\prime}\right)\geqslant\mathbb{P}\left(\left(\frac{1+\delta}{2^{\alpha}}\right)^{n}\sup_{y\in(x_{1}^{\prime},2x_{1}^{\prime}]}\frac{1}{y^{\alpha}\lambda(y)}<\eta\right).$

Finally, since $\lambda$ is monotonous, notice that
$\sup_{y\in(x_{1}^{\prime},2x_{1}^{\prime}]}\frac{1}{y^{\alpha}\lambda(y)}<\left(\lambda(2x_{1}^{\prime})(x_{1}^{\prime})^{\alpha}\right)^{-1}$
is a random variable with a finite mean. So, using the Markov inequality, it
is possible to find $M=M(x_{1}^{\prime},\alpha)$ such that:

$\displaystyle\mathbb{P}\left(\sup_{y\in(x_{1}^{\prime},2x_{1}^{\prime}]}\frac{\lambda(y)}{y^{\alpha}}<M\right)>1-\frac{\varepsilon}{2}.$

In particular, with $M>0$ fixed, one gets that exists
$x_{1}=x_{1}(\varepsilon,\eta,\alpha)$ such that:

$\displaystyle\mathbb{P}\left(\frac{\lambda(x)}{x^{\alpha}}\leqslant\eta,\forall
x>x_{1}\right)>1-\varepsilon.$

As desired. ∎

Moreover, using analogous arguments, it is possible to proof the same result
for the sequence $\lambda^{-2}(x)$, that is:

######  Corollary 2.

For all $\varepsilon>0$ and $\delta>0$, there exists
$x_{0}=x_{0}(\varepsilon,\delta)$ such that:

$\displaystyle\mathbb{P}\left(1-\delta\leqslant\frac{\sum_{k=1}^{x}\frac{1}{\lambda^{2}(k)}}{\frac{x}{\lambda^{2}(x)}}\leqslant
1+\delta,\,\forall x>x_{0}\right)>1-\varepsilon.$

Moreover, for every $\alpha>0$ and $\eta>0$, there exists
$x_{1}=x_{1}(\varepsilon,\eta,\alpha)$ such that:

$\displaystyle\mathbb{P}\left(x^{-\alpha}\frac{1}{\lambda^{2}(x)}\leqslant\eta,\,\forall
x>x_{1}\right)>1-\varepsilon.$

The proof of this Corollary is analogous to the proof of Proposition 3, and it
is left as an exercise.

##  5 Concentration results

This subsection will demonstrate two different types of concentration for the
random sequence $P_{n}$. Both results show that $P_{n}$ is concentrated around
the random variable $\sum_{k=1}^{n}\lambda^{-1}_{k}$. They follow the same
structure: In the quenched space, fixing any slowly varying sequence of
parameters, it is possible to apply classical concentration results in the sum
of geometric random variable; then using the tightness of the sequence
$(\lambda_{n})_{n}$ in the slowly varying space, it is possible to obtain such
a concentration in the annealed space. Specifically, the first result in Lemma
6 relies on Chebychev’s inequality, and the second result in Proposition 5 is
proven using a version of McDiarmid’s inequality, which makes it more precise.

######  Lemma 6.

Consider the dependent random variables $P_{n}$ and
$\sum_{k=1}^{n}\frac{1}{\lambda_{k}}$, where $\lambda_{k}$ is equal to
$\prod_{j=1}^{k}\left(1-\frac{1}{P_{j}}\right)$. For every $\alpha>1$, it is
true that:

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|>\sqrt{n^{\alpha}}\right)=0.$

###### Proof.

Concentration results for the random variable $P_{n}$ are very difficult to
find. The main issue is that a small perturbation in the initial values can
lead to very different outcomes due to the dependencies of $P_{n}$. However,
it is possible to study the limiting behavior of this random variable by
knowing what is the overall possible behavior of the parameters; then using
quenched and annealed techniques, it is possible to get the desired result.

Consider $\Gamma=\\{(\gamma)_{n}:\gamma_{n}\downarrow
0,\gamma(x)\in\mathrm{SV}_{0}\\}$, the set of all positive decreasing
sequences that also belong to the set of slowly varying sequences. Then, for
any fixed sequence $\gamma\in\Gamma$, define:

$\displaystyle
S_{n}(\gamma)=\sum_{k=1}^{n}\mathrm{Geo}\left(\gamma_{n}\right),$ (21)

where the geometric random variables are independent. In particular, by some
computations:

$\displaystyle\mathbb{E}\left(S_{n}(\gamma)\right)=\sum_{k=1}^{n}\frac{1}{\gamma_{k}},\text{
and
}\mathrm{Var}\left(S_{n}(\gamma)\right)=\sum_{k=1}^{n}\frac{1-\gamma_{k}}{\gamma_{k}^{2}}.$

Since $(\gamma_{n})_{n}$ is slowly varying, the sequences
$\left(\frac{1}{\gamma_{n}}\right)_{n}$ and
$\left(\frac{1}{\gamma_{n}^{2}}\right)_{n}$ are also slowly varying. This
means, using Proposition 2, that:

$\displaystyle\lim_{n\to\infty}\frac{\mathbb{E}\left(S_{n}(\gamma)\right)}{n\frac{1}{\gamma_{n}}}=1,\text{
and
}\lim_{n\to\infty}\frac{\mathrm{Var}\left(S_{n}(\gamma)\right)}{n\frac{1}{\gamma_{n}^{2}}}=1.$
(22)

So, for every $\alpha>1$, using Chebyshev’s inequality, Proposition 2 and the
limit of equation (22), one get that:

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\left|S_{n}(\gamma)-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\sqrt{n^{\alpha}}\right)\leqslant\lim_{n\to\infty}\frac{\mathrm{Var}\left(S_{n}(\gamma)\right)}{n\frac{1}{\gamma_{n}^{2}}}\frac{1}{n^{\alpha-1}\gamma^{2}_{n}}=0.$
(23)

To apply these results in the distribution of $\lambda_{n}$, consider
$(\gamma_{k})_{k=1}^{n}$ the first $n$ terms that belong to the sequence
$\gamma\in\Gamma$, set $d\lambda_{n}$ a measure over $[0,1]^{n}$ defined as:

$\displaystyle\mathbb{P}\left(\lambda_{1}=\gamma_{1},\cdots,\lambda_{n}=\gamma_{n}\right)=\int_{[0,1]^{n}}\mathbf{1}\\{\vec{x}=(\gamma_{1},\cdots,\gamma_{n})\\}d\lambda_{n}(\vec{x}).$

In particular, one have that:

$\displaystyle\mathbb{P}\left(\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|>\sqrt{n^{\alpha}}\right)=\int_{[0,1]^{n}}\mathbb{P}\left(\left|S_{n}(\gamma)-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\sqrt{n^{\alpha}}\right)d\lambda((\gamma_{k})_{k=1}^{n}).$
(24)

It is proved that for each fixed $\gamma$, the probability in question goes to
zero. This does not solve the problem, since the limit might not be uniform in
$n$, and $\lambda_{n}$ can give mass to sequences that is not possible to be
concentrated at time $n$. But this is not the case. Proposition 3 proves a
tightness condition for the random variable $\lambda_{n}$, that for every
$\varepsilon>0$, $\delta>0$, $\eta>0$ and $\alpha>1$, one get that exists
$n_{0}=n_{0}(\varepsilon,\delta,\eta,\alpha)$ such that:

$\displaystyle\mathbb{P}\left(1+\delta\geqslant\frac{\sum_{k=1}^{n}\frac{1}{\lambda(k)}}{\frac{n}{\lambda_{n}}}\geqslant
1-\delta,\,\forall n>n_{0}\right)>1-\frac{\varepsilon}{3}.$ (25)
$\displaystyle\mathbb{P}\left(1+\delta\geqslant\frac{\sum_{k=1}^{n}\frac{1}{\lambda^{2}(k)}}{\frac{n}{\lambda_{n}^{2}}}\geqslant
1-\delta,\,\forall n>n_{0}\right)>1-\frac{\varepsilon}{3}.$ (26)
$\displaystyle\mathbb{P}\left(n^{1-\alpha}\frac{1}{\lambda_{n}^{2}}\leqslant\eta,\,\forall
n>n_{0}\right)>1-\frac{\varepsilon}{3}.$ (27)

All the events have high probability, then the intersection of all three
events is going to have a probability greater then $1-\varepsilon$. Moreover,
by fixing any sequence $(\gamma_{n})_{n}$ that satisfies all the events, one
obtains for every $n>n_{0}$, using Chebyshev’s inequality:

$\displaystyle\mathbb{P}\left(\left|S_{n}(\gamma)-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\sqrt{n^{\alpha}}\right)\leqslant\frac{(1+\delta)n\frac{1}{\gamma_{n}^{2}}}{n\frac{1}{\gamma_{n}^{2}}}\frac{1}{n^{\alpha-1}\gamma_{n}^{2}}\leqslant\eta(1+\delta).$
(28)

Therefore, in the set $\Gamma$ of slowly varying sequences, there exist two
disjoint sets, the set formed by sequences that satisfies all tightness events
in equations (25),(26) and (27); and the set of sequences that do not. In the
set of sequences that satisfies all the events, the probability of
$\mathbb{P}\left(\left|S_{n}(\gamma)-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\sqrt{n^{\alpha}}\right)$
is bounded by $\eta(1+\delta)$. In sequences that do not satisfy one of the
events, the measure $d\lambda_{n}$ gives a mass less than $\varepsilon>0$.
Thus, by equation (24), for every $n>n_{0}$, one get:

$\displaystyle\mathbb{P}\left(\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|>\sqrt{n^{\alpha}}\right)\leqslant(1+\delta)\eta+\varepsilon.$

Since $\varepsilon$, $\delta$ and $\eta$ are arbitrary values, taking all
close to zero and choosing $n_{0}$ large enough. The concentration is proved
as desired. ∎

The result of Lemma 6 is not strong enough. We can not have any information
about the distribution of $P_{n}$ and the distribution of the sum
$\sum_{k=1}^{n}\frac{1}{\lambda_{k}}$ if they eventually come close together.
To make a sharper result, consider the following version of McDiarmid’s
inequality [9] for Geometric random variables. This proof will significantly
improve the polynomial decay of equation 23, making it summable.

######  Proposition 4.

Take $(\gamma_{n})_{n}$ any monotonous decreasing sequence such that
$\gamma(x)\in\mathrm{SV}_{0}$. Define the independent sum of geometric random
variables with parameters $\gamma_{k}$ as
$S_{n}(\gamma)=\sum_{k=1}^{n}\mathrm{Geo}\left(\gamma_{k}\right)$. Then, for
every $\varepsilon>0$, $\alpha>1$, there exists
$n_{0}=n_{0}(\varepsilon,\alpha)$ such that:

$\displaystyle\mathbb{P}\left(\left|S_{n}(\gamma)-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\sqrt{n^{\alpha}},\,\forall
n>n_{0}\right)\leqslant\varepsilon.$

###### Proof.

The proof consists in using McDiarmid’s inequality for the sum of independent
geometric random variables, but notice that the geometric random variable is
unbounded. To apply McDiarmird’s inequality, fix $\varepsilon>0$, then let
$\beta=\beta(\varepsilon)>1$ be such that
$\frac{1}{2^{\beta}}+\frac{1}{(1-\beta)2^{\beta-1}}<\frac{\varepsilon}{2}$.
Define the truncated random variable:

$\displaystyle
G_{k}=\mathrm{Geo}\left(\gamma_{k}\right)\mathbf{1}\left\\{\mathrm{Geo}\left(\gamma_{k}\right)\leqslant\beta\gamma_{k}^{-1}\ln{(k)}\right\\}.$

About the truncated random variable $G_{k}$, the probability that it is
different from $\mathrm{Geo}\left(\gamma_{k}\right)$ is equal to:

$\displaystyle\mathbb{P}\left(G_{k}\neq\mathrm{Geo}\left(\gamma_{k}\right)\right)=(1-\gamma_{k})^{\beta\gamma_{k}^{-1}\ln{(k)}}\leqslant\frac{1}{k^{\beta}}.$
(29)

Therefore, we can conclude that:

$\displaystyle\mathbb{P}\left(G_{k}=\mathrm{Geo}\left(\gamma_{k}\right),\,\forall
k\geqslant 2\right)\geqslant 1-\sum_{k=2}^{\infty}\frac{1}{k^{\beta}}\geqslant
1-\frac{1}{2^{\beta}}-\frac{1}{(1-\beta)2^{\beta-1}}>1-\frac{\varepsilon}{2}.$
(30)

Now, apply McDiarmid’s inequality in the truncate random variable $G_{k}$.
Before doing this, note that since $\gamma(x)\in\mathrm{SV}_{0}$, then
$\frac{1}{\gamma(x)}$, $\frac{\ln(x)}{\gamma(x)}$ and
$\frac{\ln^{2}(x)}{\gamma^{2}(x)}$ are also slowly varying. Thus, it is
possible to find a $n_{1}=n_{1}(\beta,\alpha)$ such that for every $n>n_{1}$:

$\displaystyle\frac{1}{2n^{\frac{\beta-1}{2}}}\left(\frac{1}{\gamma(n)}+\beta\frac{\mathrm{ln}\left(n\right)}{\gamma(n)}\right)<1,$
(31) $\displaystyle n^{-\alpha/2}\beta^{2}\frac{\ln^{2}{n}}{\gamma^{2}(n)}<1,$
(32)
$\displaystyle\frac{\sum_{k=1}^{n}\left(\frac{\ln{k}}{\gamma(k)}\right)^{2}}{n\left(\frac{\mathrm{ln}\left(n\right)}{\gamma(n)}\right)^{2}}\leqslant
2.$ (33)

Computing the expectation of $G_{k}$, one gets:

$\displaystyle\mathbb{E}\left(G_{k}\right)$
$\displaystyle=1+\sum_{k=1}^{\beta\gamma_{k}^{-1}\ln{k}}\left[(1-\gamma_{k})^{k}-(1-\gamma_{k})^{\beta\gamma_{k}^{-1}\ln{k}}\right]$
$\displaystyle=\frac{1}{\gamma_{k}}-(1-\gamma_{k})^{\beta\gamma_{k}^{-1}\ln{k}}\left(\frac{1}{\gamma_{k}}+\beta\gamma_{k}^{-1}\ln{k}\right)$
$\displaystyle\leqslant\mathbb{E}\left(\mathrm{Geo}\left(\gamma_{k}\right)\right)-\frac{1}{2k^{\beta}}\left(\frac{1}{\gamma_{k}}+\beta\frac{\ln{k}}{\gamma_{k}}\right).$

So, by equation (31), since $\beta>1$ and $\beta-\frac{\beta-1}{2}>1$, one
finds that $\mathbb{E}\left(\mathrm{Geo}\left(\gamma_{k}\right)-G_{k}\right)$
is summable. So, there exists $C=C(\beta)<\infty$, such that:

$\displaystyle\lim_{n\to\infty}\mathbb{E}\left(S_{n}(\gamma)\right)-\mathbb{E}\left(\sum_{k=1}^{n}G_{k}\right)\leqslant
C<\infty.$

Since $C$ is a finite constant, there exists
$n_{2}^{\prime}=n_{2}^{\prime}(\beta,\alpha)$ such that for every
$n>n_{2}^{\prime}$, one gets that $C<\frac{1}{2}\sqrt{n^{\alpha}}$.

Now, using MCDiarmid’s inequality for the truncated random variable $G_{k}$,
for any $\alpha>1$, one gets that:

$\displaystyle\mathbb{P}\left(\left|\sum_{k=1}^{n}\left(G_{k}-\mathbb{E}\left(G_{k}\right)\right)\right|>\sqrt{n^{\alpha}}\right)\leqslant
2\exp\left\\{-\frac{2n^{\alpha}}{\beta^{2}\sum_{k=1}^{n}(\gamma_{k}^{-1}\ln{k})^{2}}\right\\}$

Moreover, by equation (33) and (32) , for $n>n_{1}$:

$\displaystyle\mathbb{P}\left(\left|\sum_{k=1}^{n}\left(G_{k}-\mathbb{E}\left(G_{k}\right)\right)\right|>\sqrt{n^{\alpha}}\right)\leqslant
2\exp\left\\{-\frac{n^{\alpha-1}}{\beta^{2}(\gamma_{n}^{-1}\mathrm{ln}\left(n\right))^{2}}\right\\}\leqslant
2e^{-n^{\frac{\alpha-1}{2}}}.$

Which is summable. Thus, for every $\varepsilon>0$, there exists
$n_{2}=n_{2}(\varepsilon,\alpha,\beta)$ such that:

$\displaystyle\mathbb{P}\left(\left|\sum_{k=1}^{n}\left(G_{k}-\mathbb{E}\left(G_{k}\right)\right)\right|>\sqrt{n^{\alpha}},\forall
n>n_{2}\right)\leqslant\frac{\varepsilon}{2}.$

Now, taking $n_{0}=\max\\{n_{1},n_{2},n_{2}^{\prime}\\}$, by the triangular
inequality, it follows that:

$\displaystyle\mathbb{P}\left(\left|S_{n}(\gamma)-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\frac{\sqrt{n^{\alpha}}}{2},\,\forall
n>n_{0}\right)$
$\displaystyle\leqslant\frac{\varepsilon}{2}+\mathbb{P}\left(\left|\sum_{k=1}^{n}G_{k}-\sum_{k=1}^{n}\frac{1}{\gamma_{k}}\right|>\frac{\sqrt{n^{\alpha}}}{2},\forall
n>n_{0}\right)$ $\displaystyle\leqslant\frac{\varepsilon}{2}+$
$\displaystyle\mathbb{P}\left(\left|\sum_{k=1}^{n}(G_{k}-\mathbb{E}\left(G_{k}\right))\right|>\sqrt{n^{\alpha}},\forall
n>n_{0}\right)\leqslant\varepsilon.$

As desired. ∎

######  Remark 2.

Assuming Theorem 1 to be true, it is possible to get the truncation random
variable and the equation (30) to prove that the gap of the objects is bounded
by $\ln^{2}(n)$, as conjectured by Crammer.

######  Proposition 5.

Consider the dependent random variables $P_{n}$ and
$\sum_{k=1}^{n}\frac{1}{\lambda_{k}}$, where $\lambda_{k}$ is equal to
$\prod_{j=1}^{k}\left(1-\frac{1}{P_{j}}\right)$. For every $\alpha>1$, we have
that:

$\displaystyle\mathbb{P}\left(\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|\leqslant\sqrt{n^{\alpha}},\,\forall
n>n_{0}\right)\geqslant 1-\varepsilon.$

###### Proof.

Fix $\beta=2$, $\alpha>1$, and take any $\varepsilon>0$. Following the same
steps of Proposition 3, it is possible to conclude that exists
$x_{0}=x_{0}(\varepsilon,\alpha)$ such that:

$\displaystyle\mathbb{P}\left(\frac{1}{2x^{\frac{\beta-1}{2}}}\left(\frac{1}{\lambda(x)}+\beta\frac{\ln{x}}{\lambda(x)}\right)<1,\,\forall
x>x_{0}\right)>1-\frac{\varepsilon}{3}.$ (34)
$\displaystyle\mathbb{P}\left(x^{-\frac{\alpha-1}{2}}\beta^{2}\frac{\ln^{2}{x}}{\lambda^{2}(x)}<1,\forall
x>x_{0}\right)>1-\frac{\varepsilon}{3}$ (35)
$\displaystyle\mathbb{P}\left(\frac{\int\limits_{1}^{x}\left(\frac{\ln{y}}{\lambda(y)}\right)^{2}dy}{x\left(\frac{\ln{x}}{\lambda(x)}\right)^{2}}\leqslant
2,\,\forall x>x_{0}\right)>1-\frac{\varepsilon}{3}.$ (36)

So, analogous to equations (31), (32), and (33), every sequence $\gamma$ that
satisfies the events in equations (34), (35) and (36), has its difference
between the expectation of $S_{n}(\gamma)$ and $\sum_{k=1}^{n}G_{k}$ bounded
by $C=C(\beta)$. In addition, the probability of the event
$\\{\sum_{k=1}^{n}G_{k}-\mathbb{E}\left(G_{k}\right)|>\sqrt{n^{\alpha}}\\}$ is
uniformly bounded by $e^{-n^{\frac{\alpha-1}{2}}}$; therefore, it is possible
to find $n_{1}=n_{1}(\alpha,\varepsilon)$ such that:

$\displaystyle\mathbb{P}\left(\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|<\sqrt{n^{\alpha}},\forall
n>n_{1}\right)<1-\varepsilon.$

Finishing the proof of the proposition. ∎

##  6 First term in the law of large numbers

The random sequences $P_{n}$ and $\sum_{k=1}^{n}\lambda_{k}^{-1}$ are both
$\mathcal{F}_{n}$ measurable, which means that knowing the values of
$(P_{1},\cdots,P_{n})$ results in knowing the value of
$\sum_{k=1}^{n}\lambda_{k}^{-1}$. In function of that, we are going to shift
our random approach into a deterministic study where it will be exposed the
properties of deterministic sequences $(P_{n})_{n}$ that satisfy the event
$\left\\{\left|P_{n}-\sum_{k=1}^{n}\frac{1}{\lambda_{k}}\right|<\sqrt{n^{\alpha}},\forall
n>n_{0}\right\\}$. The easiest example of that affirmation is a direct
consequence of the fact that $\lambda_{n}\in\mathrm{SV}_{0}$ with probability
one, that is:

######  Proposition 6.

For every $\varepsilon>0$ and $\delta>0$, there exists
$n_{0}=n_{0}(\varepsilon,\delta)$ such that:

$\displaystyle\mathbb{P}\left(P_{n}\leqslant n^{1+\delta},\,\forall
n>n_{0}\right)\geqslant 1-\varepsilon,\text{ and}$
$\displaystyle\mathbb{P}\left((1+\delta)n\lambda_{n}^{-1}\geqslant
P_{n}\geqslant(1-\delta)n\lambda_{n}^{-1},\,\forall n>n_{0}\right)\geqslant
1-\varepsilon.$

###### Proof.

This proposition is a direct consequence of the results in Propositions 5 and
3, where by knowing that $\lambda_{n}$ is slowly varing and its sum is close
to the value of $P_{n}$, one can give bound to the value of $P_{n}$. For every
$\alpha\in(1,2)$, there exists $n_{0}$ such that with high probability the
event $\\{|P_{n}-\sum_{k=1}^{n}\lambda_{k}^{-1}|<\sqrt{n^{\alpha}},\,\forall
n>n_{0}\\}$ occurs. Moreover, since $\sum_{k=1}^{n}\lambda_{k}^{-1}$ is close
to $n\lambda_{n}^{-1}$, and slowly varying functions do not decay faster than
the polynomial, the proof is over. ∎

Before continuing, notice that the definition of the random parameter
$\lambda_{n}$ in equation (3), was only used to proof Lemma 5 which proves
that the sequence $(\lambda_{n})_{n}$ is slowly varying. All the results
presented before are still valid assuming that the sequence $(\gamma_{n})_{n}$
satisfy the properties of the Lemma 5. Now, to show that the sequence $P_{n}$
approaches the value of $n\mathrm{ln}\left(n\right)$, the formula of the
expression (3) will be used.

The choice of the value $n\mathrm{ln}\left(n\right)$ is not random. It comes
within a study of a continuous differential equation derived from Proposition
6. To briefly explain this choice as a limit, take
$\sum_{k=1}^{n}\prod_{j=1}^{k}\left(1-\frac{1}{P_{j}}\right)^{-1}$ and
approximate $1-x$ by $e^{-x}$. Then, exchanging summations with integrals, our
concentration is related with solutions $f(x)$ of the following integral
inequality:

$\displaystyle\left|f(x)-\int\limits_{0}^{x}dy\exp\left\\{\int\limits_{0}^{y}\frac{dz}{f(z)}\right\\}\right|<\sqrt{x^{\alpha}}.\,\forall
x>x_{0}.$

In particular, analyzing functions $f(x)$ such that
$f(x)=\int\limits_{0}^{x}dy\exp\left\\{\int\limits_{0}^{y}\frac{dz}{f(z)}\right\\}$,
the differential equation $f^{\prime}(x)=\ln{f(x)}$ appears; Such differential
equation have as solution the inverse function
$\left[\mathrm{li}^{-1}\right](x)$, where for every
$x\in\mathbb{R}\setminus\\{1\\}$, define the logarithmic integral function:

$\displaystyle\mathrm{li}(x)=\int\limits_{0}^{x}\frac{dt}{\ln{t}}.$

Where at $t=1$, for every $x>1$, the integral is interpreted as a a principal
value; See more of the function in [2]. Moreover, analyzing all such solutions
for any possible initial value, one gets that all solutions are represented by
$\frac{1}{c}\left[\mathrm{li}^{-1}\right]\left({cx}\right)$ for some $c>0$,
that imply in a leader term of order
$n\mathrm{ln}\left(n\right)+n\mathrm{ln}\left(\mathrm{ln}\left(n\right)\right)$.
The third term can be different in this set of solutions, and is the reason
why we expect Conjecture 1 to be true.

With a limit candidate, it will be proved that the random variable $P_{n}$
fluctuates around $n\mathrm{ln}\left(n\right)$.

######  Lemma 7.

For every $\varepsilon>0$, and integer $N>0$ we have that:

$\displaystyle\mathbb{P}\left(P_{n}>(1+\varepsilon)n\mathrm{ln}\left(n\right),\forall
n>N\right)=\mathbb{P}\left(P_{n}<(1-\varepsilon)n\mathrm{ln}\left(n\right),\,\forall
n>N\right)=0.$

###### Proof.

This proof consists in showing that bounding the value of $P_{n}$ creates a
bound for the summation $\sum_{k=1}^{n}\lambda_{n}^{-1}$ that do not grows in
the right scale. Without loss of generality, fix $\delta>0$ and assume $N$
large enough such that for every $n>N$, one get:

$\displaystyle
1+\delta\geqslant\frac{\int_{1}^{n}\ln^{\frac{1}{1+\varepsilon}}(t)dt}{n\ln^{\frac{1}{1+\varepsilon}}(n)}\geqslant
1-\delta$ $\displaystyle
1+\delta\geqslant\frac{\int_{1}^{n}\ln^{\frac{2}{2-\varepsilon}}(t)dt}{n\ln^{\frac{2}{2-\varepsilon}}(n)}\geqslant
1-\delta.$

Where it is used Karamatha’s results, Proposition 2, since $\ln^{\beta}(x)$ is
slowly varying for every $\beta\geqslant 0$.

The argument explored here, start by observing that $P_{n}$ and the summation
$\sum_{k=1}^{n}\lambda_{k}^{-1}$ are close together with high probability. The
next step is to find a special region, where if the generator $P_{n}$ belongs
to it, the distance of $P_{n}$ to $\sum_{k=1}^{n}\lambda_{k}^{-1}$ increases
faster than $\sqrt{n^{\alpha}}$. Implying that the generator with high
probability does not belong to such region.

Our region is the set of sequences where
$\\{P_{n}>(1+\varepsilon)n\mathrm{ln}\left(n\right),\forall n>N\\}$ occurs.
Start by dividing the summation in the time $N$, so one get:

$\displaystyle\sum_{k=1}^{n}\lambda_{k}^{-1}$
$\displaystyle=\sum_{k=1}^{N}\lambda_{k}^{-1}+\lambda_{N}^{-1}\sum_{k=N}^{n}\prod_{j=N+1}^{n}\left(1-\frac{1}{P_{j}}\right)^{-1}.$
(37)

Now, assuming that
$\\{P_{n}>(1+\varepsilon)n\mathrm{ln}\left(n\right),\,\forall n>N\\}$ happens,
it is possible to bound:

$\displaystyle\sum_{k=N}^{n}\prod_{j=N+1}^{k}\left(1-\frac{1}{P_{j}}\right)^{-1}$
$\displaystyle\leqslant\sum_{k=N}^{n}\exp\left\\{\sum_{j=N+1}^{k}\frac{1}{P_{j}}\right\\}$
$\displaystyle\leqslant\int\limits_{N}^{n}\exp\left\\{\int\limits_{N}^{t}\frac{dx}{\left(1+\varepsilon\right)x\ln{x}}\right\\}dt=\int\limits_{N}^{n}\frac{\ln^{\frac{1}{1+\varepsilon}}(t)}{\ln^{\frac{1}{1+\varepsilon}}(N)}dt$
$\displaystyle\leqslant\frac{(1+\delta)n\ln^{1/(1+\varepsilon)}(n)-(1-\delta)N\ln^{1/(1+\varepsilon)}(N)}{\ln^{\frac{1}{1+\varepsilon}}(N)}.$
(38)

Since $N$ is a fixed value, taking $n$ to infinity in equation (37), the
growth of $\sum_{k=1}^{n}\lambda_{k}^{-1}$ is bounded above by some constant
(depending in $N$) times $n\ln^{\frac{1}{1+\varepsilon}}(n)$. So, eventually,
this is smaller than $(1+\varepsilon)n\mathrm{ln}\left(n\right)$. Since with
high probability the values of $(P_{n})_{n}$ follow up the summation
$\sum_{k=1}^{n}\lambda_{k}^{-1}$, the generators cannot stay forever above
$(1+\varepsilon)n\mathrm{ln}\left(n\right)$.

In the other case, when
$\\{P_{n}<(1-\varepsilon)n\mathrm{ln}\left(n\right),\forall n>N\\}$ occurs, it
is also possible to assume, without loss of generality, that $N$ is large
enough so that $x<\frac{1}{(1-\varepsilon)N\mathrm{ln}\left(n\right)}$, in
particular $1-(1-\varepsilon)x\geqslant
e^{\left(1-\frac{\varepsilon}{2}\right)x}$, and:

$\displaystyle\sum_{k=1}^{n}\lambda_{k}^{-1}$
$\displaystyle\geqslant\sum_{k=N}^{n}\prod_{j=N+1}^{k}\left(1-\frac{1}{P_{j}}\right)^{-1}$
(39)
$\displaystyle\geqslant\frac{(1+\delta)n\ln^{1/\left(1-\frac{\varepsilon}{2}\right)}(n)-(1-\delta)N\ln^{1/\left(1-\frac{\varepsilon}{2}\right)}(N)}{\ln^{\frac{1}{1-\frac{\varepsilon}{2}}}(N)}.$

Again, notice that $n\ln^{1/(1-\frac{\varepsilon}{2})}(n)$ grows faster than
$n\mathrm{ln}\left(n\right)$, and the proof is over. ∎

######  Remark 3.

Given $c_{1}>c_{2}>0$ and some $a>0$. Consider the functions
$c_{1}n\ln^{\frac{1}{1+a}}{n}$ and $c_{2}n\ln{(n)}$. Both at $n=1$ are zero,
but since $c_{1}>c_{2}$, initially $c_{1}n\ln^{\frac{1}{1+a}}{n}\geqslant
c_{2}n\mathrm{ln}\left(n\right)$. Then, when
$n>\exp\left\\{\left(\frac{c_{1}}{c_{2}}\right)^{\frac{1+a}{a}}\right\\}$,
these functions invert and one gets $c_{1}n\ln^{\frac{1}{1+a}}{n}\leqslant
c_{2}n\mathrm{ln}\left(n\right)$. In the renewal covering of the natural
numbers, $c_{1}$ grows when $n$ is large and the constant $a$ is usually
small; thus, all results treated in this paper take an extremely long time to
occur.

The above Lemma with some careful treatment can give the law of large numbers
of the random variables $P_{n}$, by providing that these different orders of
growth blocks the process to recover.

Now, it is time to proof Theorem 1.

###### Proof of Theorem 1.

The proof is divided into two analogous parts: The first part shows that
$\limsup_{n}\frac{P_{n}}{n\mathrm{ln}\left(n\right)}=1$ almost surely, and the
second part shows that $\liminf_{n}\frac{P_{n}}{n\mathrm{ln}\left(n\right)}=1$
with probability one. Since the demonstrations are analogous, it will be
proven just that $\limsup_{n}\frac{P_{n}}{n\mathrm{ln}\left(n\right)}=1$
almost surely. The idea of the proof consists of dividing the space into
layers, like an onion, where the layers are of the form
$(1+ka)n\mathrm{ln}\left(n\right)$, for any fixed $a>0$ and
$k\in{\mathbb{N}}$. When $n$ is large, if the process tries to escape the
value $n\mathrm{ln}\left(n\right)$ and enters one of these onion layers, one
can use the bound founded in Lemma 7 to show that the summation
$\sum_{k=1}^{n}\lambda_{k}^{-1}$ never reach the next layer. Therefore, the
process that oscillates around $n\mathrm{ln}\left(n\right)$, and is close to
the sum $\sum_{k=1}^{n}\lambda_{k}^{-1}$, will not be able to grow larger than
$(1+a)n\ln{n}$, so it concentrates bellow $n\ln{n}$. Moreover, the same can be
done in the layers $(1-ka)n\mathrm{ln}\left(n\right)$ to prove that
$\liminf_{n}\frac{P_{n}}{n\mathrm{ln}\left(n\right)}=1$ almost surely.
Finishing the proof of Theorem 1.

Let any $\varepsilon>0$, $a>0$ and $\alpha\in(1,2)$, choose $\delta>0$ small
enough so that $(1+a)\frac{1+\delta}{1-\delta}<1+2a$. Then, find
$n_{0}=n_{0}(\varepsilon,\delta)$ such that with probability $1-\varepsilon$,
for every $n>n_{0}$, the sequences $(P_{n})_{n}$, $(\lambda_{n})_{n}$ and the
function $\ln^{\frac{1}{1+a}}(n)$ satisfies:

$\displaystyle\left|P_{n}-\sum_{k=1}^{n}\lambda_{k}^{-1}\right|<\sqrt{n^{\alpha}}$
(40) $\displaystyle
1+\delta\geqslant\frac{\sum_{k=1}^{n}\lambda_{k}^{-1}}{n\lambda_{n}^{-1}}\geqslant
1-\delta,$ (41) $\displaystyle
1+\delta\geqslant\frac{\int\limits_{1}^{n}\ln^{\frac{1}{1+a}}(x)dx}{n\ln^{\frac{1}{1+a}}(n)}\geqslant
1-\delta.$ (42)

When the process is around $n\mathrm{ln}\left(n\right)$ and tries to reach the
values of order $(1+2a)n\mathrm{ln}\left(n\right)$, it has to reach the value
$(1+a)n\mathrm{ln}\left(n\right)$. Moreover, there exists an up-crossing
event: a moment where the process is smaller or equal to
$(1+a)n\mathrm{ln}\left(n\right)$, and eventually reaches
$(1+2a)n\mathrm{ln}\left(n\right)$ without being smaller then
$(1+a)n\mathrm{ln}\left(n\right)$. The bounds proposed works in the upcrossing
event, and shows that the process cannot reach the next layer. See in Figure 1
a representation of what is going to happen in the proof.

$x\ln{x}$$(1+a)x\ln{x}$$(1+2a)x\ln{x}$ Figure 1: With the space divided in
layers of the form $(1+ka)x\ln{x}$, the process in red is trying to cross the
layer $(1+a)n\mathrm{ln}\left(n\right)$, but it is being blocked by a black
bound

With $a>0$ fixed and $n>n_{0}$, to simplify some calculations, assume the
following. First, suppose that
$\sum_{k=1}^{n}\lambda_{k}^{-1}=(1+a)n\mathrm{ln}\left(n\right)$. The second
assumption is to fix $(\lambda_{n})_{n}$ and $(P_{n})_{n}$ that satisfies
conditions (40) and (41), that is always possible with high probability. Then,
the proof will reach an absurdity when assuming the following condition that
imitates the upcrossing event, that is: for every $m>n$, until
$P_{m}>(1+2a)m\ln{m}$, the process satisfies $P_{m}>(1+a)m\ln{m}$.

Consider $\beta>1$, computing the summation
$\sum_{k=1}^{n^{\beta}}\lambda_{k}^{-1}$ in the interval $[1,n^{\beta}]$,
where in the value $n$, the process satisfied that
$\sum_{k=1}^{n}\lambda_{k}^{-1}=(1+a)n\mathrm{ln}\left(n\right)$, and by
hypotheses (41) it is true that
$\lambda_{n}^{-1}\leqslant\frac{(1+a)\ln{n}}{(1-\delta)}$. Then, it is
possible to get using inequality (6) the following:

$\displaystyle\sum_{k=1}^{n^{\beta}}\lambda_{k}^{-1}$
$\displaystyle=\sum_{k=1}^{n}\lambda_{k}^{-1}+\lambda_{n}^{-1}\sum_{k=n+1}^{n^{\beta}}\prod_{j=n+1}^{k}\left(1-\frac{1}{P_{j}}\right)$
$\displaystyle\leqslant(1+a)n\mathrm{ln}\left(n\right)+(1+a)\frac{\mathrm{ln}\left(n\right)}{1-\delta}\frac{\left((1+\delta)n^{\beta}\ln^{\frac{1}{1+a}}(n^{\beta})-(1-\delta)n\ln^{\frac{1}{1+a}}(n)\right)}{\ln^{\frac{1}{1+a}}(n)}$
$\displaystyle=\frac{(1+a)(1+\delta)}{1-\delta}\frac{\beta^{1/(1+a)}}{\beta}n^{\beta}\ln{n^{\beta}}\leqslant\frac{(1+a)(1+\delta)}{1-\delta}n^{\beta}\ln{n^{\beta}}.$
(43)

By the choice of $\delta>0$, for any $\beta>1$ the sum value never reaches the
curve $(1+2a)x\ln{x}$, as desired.

To finish the proof, let us generalize our initial assumptions. The first
assumption is that the function starts at the value
$(1+a)n\mathrm{ln}\left(n\right)$, to generalize this affirmation, consider
the process between $(1+a)n\mathrm{ln}\left(n\right)$ and
$\left(1+\frac{3a}{2}\right)n\mathrm{ln}\left(n\right)$.Therefore, analyzing
the process starting from the first point where an upcrossing
$(1+a)n\mathrm{ln}\left(n\right)$ to
$\left(1+\frac{5}{2}a\right)n\mathrm{ln}\left(n\right)$ occurs, the error in
the initial position of the crossing will not interfere with the bound.

Moreover, to finish the proof, since for every $a>0$, by Lemma 7, one sees
that $P_{n}$ cannot stay greater than $(1+a)n\mathrm{ln}\left(n\right)$ for
ever, so it must be close to $n\mathrm{ln}\left(n\right)$. Thus, eventually,
for every $a>0$, when $n$ is large, it will return and will never do an
upcrossing to $(1+2a)n\mathrm{ln}\left(n\right)$ again. Since $a>0$ is
arbitrary, this get that:

$\displaystyle\mathbb{P}\left(\limsup_{n\to\infty}\frac{P_{n}}{n\mathrm{ln}\left(n\right)}=1\right)=1.$

The proof of $\liminf_{n\to\infty}\frac{P_{n}}{n\mathrm{ln}\left(n\right)}=1$
is analogous, just taking the $n$ large enough to get the inequality (39). ∎

## References

  * [1] The Riemann Hypothesis: A Resource for the Afficionado and Virtuoso Alike.  Springer New York, 2008.
  * [2] Milton Abramowitz and I A Stegun, editors.  Handbook of mathematical functions.  Dover Books on Mathematics. Dover Publications, Mineola, NY, June 1965\.
  * [3] Arne Beurling.  Analyse de la loi asymptotique de la distribution des nombres premiers généralisés. i: Mémoire dédié à m. holmgren.  Acta Mathematica, 68(0):255–291, 1937.
  * [4] Harald Cramér.  On the order of magnitude of the difference between consecutive prime numbers.  Acta Arithmetica, 2(1):23–46, 1936.
  * [5] Harold G. Diamond, Hugh L. Montgomery, and Ulrike M.A. Vorhauer.  Beurling primes with large oscillation.  Mathematische Annalen, 334(1):1–36, November 2005.
  * [6] Rick Durrett.  Probability: Theory and Examples.  Cambridge University Press, April 2019.
  * [7] Pierre Dusart.  The $k^{th}$ prime is greater than $k(lnk+lnlnk-1)$ for $k\geqslant 2$.  Mathematics of Computation, 68(225):411–415, 1999.
  * [8] Edmund Landau.  Neuer beweis des primzahlsatzes und beweis des primidealsatzes.  Mathematische Annalen, 56(4):645–670, December 1903.
  * [9] Colin McDiarmid.  On the method of bounded differences, page 148–188.  Cambridge University Press, August 1989.
  * [10] Rikard Olofsson.  Properties of the beurling generalized primes.  Journal of Number Theory, 131(1):45–58, January 2011.
  * [11] Sidney I. Resnick.  Preliminaries, page 1–37.  Springer New York, 1987.
  * [12] Barkley Rosser.  Explicit bounds for some functions of prime numbers.  American Journal of Mathematics, 63(1):211, January 1941.


# Proof of Euclid’s Theorem Using Ferrers Diagrams

Anton Shakov

(September 2023)

###### Abstract

Ferrers Diagrams are typically used to visually represent integer partitions.
We introduce a way to use Ferrers diagrams to represent integers in terms of
their prime factors. This leads to a natural lower bound on the number of
primes less than a given integer $[\pi(2^{n})\geq\frac{n}{\mathbf{lg}(n+1)}]$.

We construct a bijection $\mathcal{B}$ from the natural numbers
$\mathbf{N}=\\{1,2,3,\cdots\\}$ to Ferrers Diagrams [1] for integer
partitions, which we will refer to simply as figures. Let $n\in\mathbf{N}$. We
will draw the figure $\mathcal{B}(n)$.

By the Fundamental Theorem of Arithmetic, $n$ has a unique decomposition into
prime numbers $p_{\alpha}$ up to order.

$n=p_{\alpha_{1}}^{\beta_{1}}p_{\alpha_{2}}^{\beta_{2}}\cdots
p_{\alpha_{s}}^{\beta_{s}}.$

The $\alpha_{i}$ denotes the index of each prime on the whole set $\mathbf{N}$
(i.e. $p_{1}=2$, $p_{2}=3$, $p_{3}=5$, etc.) To avoid ambiguity in drawing
$\mathcal{B}(n)$, assume $\alpha_{i}<\alpha_{i+1}$ for all $i$ in the above
decomposition.

For each prime $p_{\alpha_{i}}$ in the decomposition of $n$, we stack a row of
$\alpha_{i}$ squares for each instance that $p_{\alpha_{i}}$ divides $n$ (so
we stack $\beta_{i}$ rows of length $\alpha_{i}$ for each $i$ in the range
$1\leq i\leq s$).

Therefore $\mathcal{B}(n)$ is represented by:

$\alpha_{1}$$\beta_{1}$$\alpha_{2}$$\beta_{2}$$\alpha_{s}$$\beta_{s}$$\uparrow$$\downarrow$$\uparrow$$\downarrow$$\uparrow$$\downarrow$

For some specific examples, we write out $\mathcal{B}(n)$ for $n\leq 10$:

$n$ | Prime factors of $n$ |  $\mathcal{B}(n)$
---|---|---
1 | - |  $\emptyset$
2 | $p_{{}_{1}}$ |
3 | $p_{{}_{2}}$ |
4 | $p_{{}_{1}}^{{}_{2}}$ |
5 | $p_{{}_{3}}$ |
6 | $p_{{}_{1}}p_{{}_{2}}$ |
7 | $p_{{}_{4}}$ |
8 | $p_{{}_{1}}^{{}_{3}}$ |
9 | $p_{{}_{2}}^{{}_{2}}$ |
10 | $p_{{}_{1}}p_{{}_{3}}$ |

######  Remark 1.

$\mathcal{B}(2^{k})$ will be a vertical $k\times 1$ figure.
$\mathcal{B}(p_{k})$ will be a horizontal $1\times k$ figure, where $p_{k}$ is
the $k$th prime.

######  Lemma 1.

For figures $f,g\in\mathcal{B}(\mathbf{N})$, $f$ is a subfigure of $g$
$\implies\mathcal{B}^{-1}(f)\leq\mathcal{B}^{-1}(g)\text{ on }\mathbf{N}$.

###### Proof.

Let $f\subseteq g$ denote that $f$ is a subfigure of $g$. More precisely, we
will take $f\subseteq g$ to mean that figure $g$ covers figure $f$ without any
protruding squares upon aligning the bottom left corners. If $f=g$, there are
clearly no protruding squares and we get
$\mathcal{B}^{-1}(f)=\mathcal{B}^{-1}(g)$. We now assume $f\neq g$. Suppose
$f\subset g$. If we index the lengths of rows of $f$ as $\\{f_{1},\cdots
f_{k}\\}$ and the lengths of rows of $g$ as $\\{g_{1},\cdots,g_{s}\\}$ then
the following must be true:

  * •

$k\leq s$

  * •

$f_{i}\leq g_{i}$ for all $i$

If either of the statements were false, there would be a protruding square
upon aligning $g$ with $f$. We cannot have that both $s=k$ and $f_{i}=g_{i}$
for all $i$, since $f$ and $g$ are distinct by assumption. Therefore, either
$k<s$ or there exists some $j$ such that $f_{j}<g_{j}$.

If $k<s$, then $\mathcal{B}^{-1}(g)$ has strictly more prime divisors than
$\mathcal{B}^{-1}(f)$ which are of the same or greater size (since $f_{i}\leq
g_{i}$ for all $i$). Therefore, $\mathcal{B}^{-1}(f)<\mathcal{B}^{-1}(g)$.

If there exists some $j$ such that $f_{j}<g_{j}$, then $\mathcal{B}^{-1}(g)$
has at least as many prime divisors as $\mathcal{B}^{-1}(f)$ (since $k\leq s$)
which are at least as great (since $f_{i}\leq g_{i}$ for all $i$), with at
least one being strictly greater than its counterpart. Therefore,
$\mathcal{B}^{-1}(f)<\mathcal{B}^{-1}(g)$.

∎

######  Lemma 2.

let $f\in\mathcal{B}(\mathbf{N})$ be an $i\times j$ rectangle, Then the number
of distinct subfigures of $f$ is ${i+j\choose j}$.

###### Proof.

We count the number of distinct subfigures of an $i\times j$ rectangle by
viewing them as combinations of $i+1$ values $\\{0,1,\cdots,i\\}$ (which
correspond to the lengths of the rows) distributed with repetition throughout
$j$ different slots (the number of rows).

The formula for combinations with repetition given $a$ values and $b$ slots is
${a+b-1\choose b}$. We take $a=i+1$ and $b=j$. ∎

######  Remark 2.

We let:

  * •

$\mathbf{lg}(x)$ denote the base-2 logarithm

  * •

$\pi(x)$ denote the prime counting function  [2].

######  Theorem 1.

There are infinitely many prime numbers.
$[\pi(2^{n})\geq\frac{n}{\mathbf{lg}(n+1)}]$

###### Proof.

Let $M=\\{1,2,\cdots,2^{n}\\}$ be the set of the first $2^{n}$ integers for
some $n\in\mathbf{N}$. Let $k$ be the number of primes in $M$. We prove a
lower bound on $k$ in terms of $n$.

Clearly, $|M|=2^{n}$. Consider $\mathcal{B}(M)$, the set of Ferrers figures
corresponding to each of the integers in $M$. The maximum number of rows
attained by any figure in $\mathcal{B}(M)$ is $n$ since by Lemma 1,
$\mathcal{B}(2^{n})$ is the earliest figure with $n$ or more rows. By
assumption, there are only $k$ primes in $M$ so the maximum row length
attained by any figure in $\mathcal{B}(M)$ is $k$. It follows that all figures
in $\mathcal{B}(M)$ are subfigures of an $n\times k$ rectangle. Therefore, by
Lemma 2, $|\mathcal{B}(M)|$ is bounded above by ${n+k\choose k}$.

$\displaystyle 2^{n}=|M|=|\mathcal{B}(M)|$ $\displaystyle\leq{n+k\choose k}$
$\displaystyle=\frac{(n+k)!}{n!k!}$
$\displaystyle=\frac{1}{k!}(n+1)(n+2)\cdots(n+k)$
$\displaystyle=(n+1)(\frac{n+2}{2})\cdots(\frac{n+k}{k})$
$\displaystyle=(n+1)(\frac{n}{2}+1)\cdots(\frac{n}{k}+1)$
$\displaystyle\leq(n+1)^{k}$

The last inequality fails for $k>\frac{n}{\mathbf{lg}(n+1)}$, meaning there
must be at least $\frac{n}{\mathbf{lg}(n+1)}$ primes in the set $M$. Since $n$
was arbitrary and the expression $\frac{n}{\mathbf{lg}(n+1)}$ is unbounded
above, the statement of Theorem 1 follows. ∎

## References

  * [1] Eric W. Weisstein  “Ferrers Diagram”, From MathWorld–A Wolfram Web Resource  URL: https://mathworld.wolfram.com/FerrersDiagram.html
  * [2] Eric W. Weisstein  “Prime Counting Function”, From MathWorld–A Wolfram Web Resource  URL: https://mathworld.wolfram.com/PrimeCountingFunction.html