# Divisibility and primality in random walks

Michel J. G. WEBER  IRMA, UMR 7501, Université Louis-Pasteur et C.N.R.S., 7
rue René Descartes, 67084 Strasbourg Cedex, France. E-mail:
<EMAIL_ADDRESS>
###### Abstract.

In this paper we study the divisibility and primality properties of the
Bernoulli random walk. We improve or extend some of our divisibility results
to wide classes of iid or independent non iid random walks. We also obtain new
primality results for the Rademacher random walk. We study the value
distribution of divisors of the random walk in the Cramér model, and obtain a
general estimate of a similar kind to that of the Bernouilli model. Earlier
results on divisors and quasi-prime numbers in the Bernoulli model are
recorded, as well as some other recent in the Cramér random model, based on an
estimate due to Selberg.

###### Key words and phrases:

Divisibility, primality, random walk, binomial random walk, Bernoulli random
walk, Theta function, value distribution, quasi-prime numbers, prime numbers,
Rademacher random walk, i.i.d. sums, Cramér model, Riemann Hypothesis, Farey
series, prime number theorem, correlation properties.
2010 _Mathematics Subject Classification_ : Primary 11K65, 11N37, 60G50 ;
Secondary 11A25, 60E05, 60F15.

###### Contents

  1. 1 Introduction.
  2. 2 Preamble on summation methods.
  3. 3 Divisibility in the Bernoulli random walk.
    1. 3.1 Basic estimates.
    2. 3.2 Sharper uniform estimate and Theta function.
    3. 3.3 A way back along Pascal’s matrices.
    4. 3.4 Extension to all residue classes mod ($d$).
  4. 4 Divisibility properties in i.i.d. random walks.
  5. 5 Divisibility properties of non i.i.d. square integrable random walks.
  6. 6 Distribution of divisors of ${B_{n}B_{m}}$.
  7. 7 Divisibility and primality in the Rademacher random walk
    1. 7.1 Divisibility.
    2. 7.2 An extremal divisor case.
    3. 7.3 Primality.
    4. 7.4 Primality mod($k$).
  8. 8 Divisibility and primality in the Cramér random walk
    1. 8.1 Divisibility
    2. 8.2 Quasiprime and prime property.
    3. 8.3 Primality of ${P_{n}}$.
  9. A Proof of Theorem 6.6.

##  1\. Introduction.

In this paper we study divisibility and primality properties of the most
fundamental integer lattice random walks: the Bernoulli random walk and
Rademacher random walk. This is continuing previous works in [49], [50], [51],
[52], [53], [55], where these questions have been thoroughly investigated, as
well as other questions related to their asymptotic structural independence.
We next extend the study to the Cramér random walk on which Cramér’s model
built. This is an important example of independent, non identically
distributed random walk. A thorough probabilistic study of this model was
recently made in [46]. The case of a general square integrable lattice random
walk was very recently investigated. We prove in [44], [45] sharp divisibility
results valid for quite large classes of independent, identically distributed
(iid) lattice random walks, and obtain also divisibility results in
independent non identically distributed case. The used tools are new in this
context, and built on a remarkable coupling method and a recent improvement of
an important necessary condition of arithmetical type for the applicability of
the local limit theorem. We refer to Part IV of our 2009’s book [48], the
Chapters 11 and 13, which are devoted to divisors, and their applications in
Analysis, especially Fourier analysis.

Throughout let $\rho\in]0,1[$ and $\mathcal{B}(\rho)=\\{B_{n}(\rho),n\geq
1\\}$ denotes the binomial random walk,
$B_{n}(\rho)=\sum_{k=1}^{n}{\beta}_{k}(\rho)$, for each $n$, where
${\beta}(\rho)=\\{{\beta}_{i}(\rho),i\geq 1\\}$ is a sequence of iid binomial
random variables
(${\mathbb{P}}\\{{\beta}_{i}(\rho)=0\\}=1-{\mathbb{P}}\\{{\beta}_{i}(\rho)=1\\}=\rho$).
When $\rho=1/2$ we use the simplified notation $\mathcal{B}=\\{B_{n},n\geq
1\\}$, $B_{n}=\sum_{k=1}^{n}{\beta}_{k}$, for each $n$,
${\beta}=\\{{\beta}_{i},i\geq 1\\}$ being iid Bernoulli random variables. Let
also $\\{R_{n},n\geq 1\\}$, $R_{n}=\sum_{k=1}^{n}{\varepsilon}_{k}$, where
${\varepsilon}=\\{{\varepsilon}_{i},i\geq 1\\}$ is a sequence of iid
Rademacher random variables (${\mathbb{P}}\\{{\varepsilon}_{i}=\pm 1\\}=1/2$).
Further let $\mathcal{S}=\\{S_{n},n\geq 3\\}$, $S_{n}=\sum_{i=3}^{n}\xi_{i}$,
be the random walk associated to the Cramér model, $\xi_{i}$, $i\geq 3$, being
independent random variables defined by
${\mathbb{P}}\\{\xi_{i}=1\\}=1-{\mathbb{P}}\\{\xi_{i}=0\\}=\frac{1}{\log i}$.
The basic probability space on which these random variables are defined is
noted $({\Omega},{\mathcal{A}},{\mathbb{P}})$, and the corresponding
expectation symbol ${\mathbb{E}\,}$.

Notation and convention. – Throughout the paper, the letter $C$ denotes a
universal constant whose value may change at each occurence, and
$C_{{\alpha},{\beta},\ldots}$ denotes a constant depending only on the
parameters ${{\alpha},{\beta},\ldots}$. – We agree that $\sum_{\emptyset}=0$,
$\sup_{\emptyset}=0$.

##  2\. Preamble on summation methods.

In background of the study of the divisibility/primality questions related to
these models are often are summation methods, which may be of particular
efficiency, as they are linked between them through Tauberian results. We
first begin with some important facts. The uniform model (the uniform
distribution on $\\{0,1,2\ldots,n\\}$, for each $n$), also called the Kubilius
model, is related to Cesàro’s summation method, whereas the binomial model is
to Euler summation method, and there exist Tauberian theorems comparing
summation methods, in particular these two methods. Therefore fine
arithmetical results can be directly used, for one summation method (one
random model), depending on the rate of convergence in this one, to answer a
question concerning another random model.

######  Definition 2.1.

A set $A\subset{\mathbb{N}}$ has Cesàro density ${\lambda}$ of order 1
($C_{1}$–density ${\lambda}$), if

$\lim_{n\to\infty}\frac{\\#\\{j\leq n:j\in A\\}}{n}={\lambda}.$

Often, the most readily available information about a set of integers is that
it has $C_{1}$-Cesàro density with a given rate of convergence.

######  Definition 2.2.

A subset $A$ of ${\mathbb{N}}$ is said to have Euler density ${\lambda}$ with
parameter $\varrho$ (in short ${E}_{\varrho}$ density ${\lambda}$) if

$\lim_{n\to\infty}\sum_{j\in
A}{{n}\choose{j}}\varrho^{j}(1-\varrho)^{n-j}={\lambda}.$

Diaconis and Stein proved in [8] (Theorem 1) the following fundamental result:

######  Theorem 2.3.

For any $A\subset{\mathbb{N}}$, and $\varrho\in]0,1[$ the following assertions
are equivalent:

$\displaystyle({\rm i})$ $\displaystyle{\qquad}\hbox{\it$A$ has
${E}_{\varrho}$ density ${\lambda}$},$ $\displaystyle({\rm ii})$
$\displaystyle{\qquad}\lim_{t\to\infty}e^{-t}\sum_{j\in
A}\frac{t^{j}}{j!}={\lambda},$ $\displaystyle({\rm iii})$
$\displaystyle{\qquad}\hbox{\it for all
${\varepsilon}>0$},\quad\lim_{n\to\infty}\frac{\\#\\{j\in A:n\leq
j<n+{\varepsilon}\sqrt{n}\\}}{{\varepsilon}\sqrt{n}}={\lambda}.$

######  Remark 2.4.

The implication (ii)$\Rightarrow$(iii) was in fact first established by Jurkat
[16], and a proof using an extension of Wiener Tauberian theorem was given by
Moh in [21], not quoted in the paper.

An important consequence presented by the authors as the principal result of
the paper, is that:

(2.1) $\hbox{\it The existence and value of ${E}_{\varrho}$ density does not
depend on the value of $\varrho$}.$

A study of limit results in the present setting, for binomial random walks,
therefore reduces to the case of the Bernoulli random walk. As a consequence
of Theorem 3 in Diaconis and Stein [8], we have

######  Theorem 2.5.

If $A\subset{\mathbb{N}}$ has $E_{\varrho}$ density ${\lambda}$, then $A$ has
$C_{1}$ density ${\lambda}$. Conversely the following implication in which $g$
is assumed to be regularly varying at infinity with exponent ${\alpha}$,
$-1<{\alpha}\leq-1/2$, holds true

(2.2) $\Big{|}\frac{\\#\\{j\leq n:j\in A\\}}{n}-{\lambda}\Big{|}\leq
g(n)\qquad\\!\\!\\!\\!\\!\Longrightarrow\qquad\\!\\!\\!\\!\\!\Big{|}{\mathbb{P}}\\{B_{n}(\varrho)\in
A\\}-{\lambda}\Big{|}\leq Kg(n)n^{1/2}.$

See also Hardy [13], Theorem 149. Let $\\{{\alpha}_{k},k\geq 0\\}$ be a
sequence of reals, ${\lambda}$ real and ${\varepsilon}(n)$ be positive reals.
More generally, it follows from Lemma 6.3 that

$\displaystyle\Big{|}\frac{1}{n}\sum_{j=0}^{n-1}{\alpha}_{j}-{\lambda}\Big{|}\leq\frac{{\varepsilon}(n)}{n^{1/2}}\quad\Longrightarrow\quad\Big{|}\sum_{h=0}^{n}2^{-n}{{n}\choose{h}}{\alpha}_{h}-{\lambda}\Big{|}\leq\frac{C}{\sqrt{n}}\,\max_{1\leq\ell\leq
n}({\varepsilon}(\ell)\sqrt{\ell}).$

Let us illustrate this by giving an application to $k$-free numbers in
$\mathcal{B}(\rho)$, which is implicitly included in [8], (Corollary 4).

######  Definition 2.6.

An integer $s$ is said $k$-free if and only if it is not divisible be the
$k$-th power of any prime.

Leahey and Nymann proved in [18] among other papers, by using a formula
analogous to

$1-{\mathbb{P}}\\{B_{n}(\varrho)\ \hbox{is prime}\\}=-\sum_{2\leq d\leq
n}{\mu}(d){\mathbb{P}}\\{d|B_{n}(\varrho)\\},$

${\mu}$ being Möbius function, that

(2.3) $\lim_{n\to\infty}{\mathbb{P}}\big{\\{}B_{n}(\varrho)\ k\hbox{-{\rm
free}}\big{\\}}=\frac{1}{\zeta(k)},$

where $\zeta$ is the Riemann zeta function. A much more precise result holds:

######  Corollary 2.7.

For $k\geq 2$ integer,

(2.4) $\Big{|}{\mathbb{P}}\big{\\{}B_{n}(\varrho)\ k\hbox{-{\rm
free}}\big{\\}}-\frac{1}{\zeta(k)}\Big{|}\leq E(n),$

where

$E(n)\leq C\left(n^{\frac{1}{k}-1}\cdot e^{-Ak^{-8/5}\frac{(\log
n^{{3/5}}}{(\log\log n)^{1/5}}}\right).$

###### Proof.

Let ${\mathcal{Q}}_{k}$, ${\mathcal{Q}}_{k}(x)$ respectively denote the set of
$k$-free integers, and the number of $k$-free integers $\leq x$ ($k\geq 2$,
integer). By a result of Walfisz [39],

(2.5)
${\mathcal{Q}}_{k}(x)=\frac{x}{\zeta(k)}+{\mathcal{O}}\big{(}x^{\frac{1}{k}}.e^{-Ak^{-8/5}.\frac{(\log
x^{{3/5}}}{(\log\log x)^{1/5}}}\big{)}.$

Take $A={\mathcal{Q}}_{k}$ and note that

$\Big{|}\frac{\\#\\{j\leq n:j\in A\\}}{n}-\frac{1}{\zeta(k)}\Big{|}\leq g(n)$

with

$g(n)=n^{\frac{1}{k}-1}\cdot e^{-Ak^{-8/5}.\frac{(\log n^{{3/5}}}{(\log\log
n)^{1/5}}},$

Clearly $g(n)$ is regularly varying at infinity with exponent ${\alpha}$,
$-1<{\alpha}\leq-1/2$. Thus (2.4) follows. ∎

For $0$-density sequences, we have the following complementary result, which
does not appear in the literature.

######  Proposition 2.8.

Let $A$ be a set of integers of (natural) density $0$. Then for every $p>1$,

(2.6)
$\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}{\mathbb{P}}\\{B_{n}(\varrho)\in
A\\}^{p}=0.$

This follows from Hardy [14, ineq. 3]: Let $p>1$. Then for $0<\varrho<1$,
$a_{n}\geq 0$,

(2.7)
$\sum_{n=1}^{\infty}\left(\sum_{m=0}^{n}{{n}\choose{m}}\varrho^{m}(1-\varrho)^{n-m}a_{m}\right)^{p}\leq\varrho^{-1}\sum_{n=1}^{\infty}a_{n}^{p}.$

We refer to Apostol [1], McCarthy [19], Montgomery and Vaughan [22], Tenenbaum
[37] as bibliographical sources on arithmetical functions, and for results on
arithmetical properties of $r$-uples of integers, co-primality, pairwise co-
primality, least common multiple, and associated arithmetical functions. We
cite Tóth’s elaborated survey [38] for sharp limit results of this kind with
estimates of the remainder, Fernandez and Fernandez [11], for limiting moments
and distribution, for instance of gcd$(X^{n}_{1},\ldots,X^{n}_{n})$,
lcm$(X^{n}_{1},\ldots,X^{n}_{n})$ of arrays of independent uniformly
distributed random variables. These specialized arithmetical functions are not
considered here. In each case, however, what is investigated is often the
behavior for $n$ large of ${\mathbb{E}\,}f(T_{n})^{r}$, $r\geq 1$, where
$f(n)$ is one of these arithmetical functions, $f$ may be varying with $n$
(for arrays of random variables), $T_{n}=Y_{1}+\ldots+Y_{\nu(n)}$ (the
expectation symbol ${\mathbb{E}\,}$ corresponding to the underlying
probability space on which these random variables $Y_{j}$ are defined). Recall
that any arithmetical function $f(n)$ can be represented in the form

$f(n)=\sum_{d|n}\Phi(d).$

The function $\Phi(d)$ is defined by the Möbius inversion formula

$\Phi(n)=\sum_{d|n}\mu\Big{(}\frac{n}{d}\Big{)}f(d).$

For instance for the Bernoulli model,

${\mathbb{E}\,}f(n)=\sum_{d|n}{\mathbb{P}}\\{d|B_{n}\\}\,\Phi(d).$

See also sub-section 3.3. Hence the interest of having at disposal sharp
estimates of ${\mathbb{P}}\\{d|B_{n}\\}$ when both $d$ and $n$ vary. When
$\Phi(d)$ is such that the series $\sum\Phi(d)/d$ is absolutely convergent, we
recall that by Wintner’s Theorem

$\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}f(n)=\sum_{d=1}^{\infty}\frac{\Phi(d)}{d}.$

See Postnikov [26] p. 138. For many arithmetical functions $\Phi(d)$ is
simple. Here are some examples of mostly studied functions. Let $\mathcal{P}$
be the set of prime numbers and let the letter $p$ always denote a prime
number.

$\displaystyle{\sigma}_{s}(n)=\sum_{d|n}d^{s}$ the sum of $s$-powers of
divisors of $n$, $s\in{\mathbb{R}}$; $\displaystyle
J_{s}(n)=\sum_{d|n}d^{s}{\mu}\Big{(}\frac{n}{d}\Big{)}$ the generalized Euler
totient function, $s>0$; $\displaystyle w(n)=\sum_{p|n}\frac{\log p}{p}$
Davenport’s function; $\displaystyle\Phi(n)=\sum_{d|n}\frac{\log d}{d}$ Erdös
and Zaremba function; $\displaystyle\omega(n)=\sum_{p|n,p\in{\mathbb{P}}}1$
the prime divisor function;
$\displaystyle\Omega(n)=\sum_{p|n,p\in{\mathbb{P}}}p$ the sum of prime divisor
function; $\displaystyle\theta(n)=2^{{\omega}(n)}$ counting the number of
prime divisors of $n$.

The classical Euler totient function ${\varphi}(n)$ counting the number of
integers $k$ less than $n$ and such that $(k,n)=1$ is $J_{1}(n)$, and
${\sigma}_{0}(n)$ is the divisor function $d(n)$ counting the number of
divisors of $n$.

To the best of our knowledge, all divisibility results for a random walk
existing in the literature are in-probability results, except for [55]. It is
a pending question to know whether it is possible to derive almost sure
counterparts, from existing in-probability results using almost sure
convergence criteria, which is a far more complicated task. These criteria are
not familiar to number theorists. A random walk often has natural structural
independence properties. Therefore a study of almost sure
divisibility/primality in a random walk is possible, at the price of many
additional technicalities. That’s make the research in this domain attractive.
In the case of the Bernoulli random walk, it is not complicated to show that
the system

$\big{\\{}\chi\\{d|B_{n}\\},\ 2\leq d\leq n,\ n\geq 1\big{\\}}$

is a mixing system, namely the correlation function satisfies for each $d$ and
${\delta}$ greater than 2,

(2.8)
$\lim_{m-n\to\infty}{\mathbb{P}}\big{\\{}d|B_{n},{\delta}|B_{m}\big{\\}}-{\mathbb{P}}\\{d|B_{n}\\}{\mathbb{P}}\\{{\delta}|B_{m}\\}=0.$

The estimation of this correlation was made in [52], and is substancially
improved in [40].

The paper is organized as follows. In Sections 2-6 we study the divisors in
the Bernoulli random walk. We also study examples. Hitherto, the divisibility
or primality properties of general i.i.d. or independent non i.i.d. lattice
random walks, were not much explored and the results we present are mostly the
first. In Section 7, we describe the value distribution of divisors in the
Rademacher random walk and present some applications; we essentially study
primality properties. In Section 8, we study the value distribution of
divisors in the Cramér random walk, and record some primality results obtained
by the author.

##  3\. Divisibility in the Bernoulli random walk.

We study the probability ${\mathbb{P}}\\{d|B_{n}\\}$ when both $d$ and $n$
vary. We first prove a basic but handy estimate. Next we state a sharper and
nearly optimal estimate using Theta function, earlier established by the
author in [51]. Applications are given to:
${\mathbb{E}\,}{\sigma}_{-1}(B_{n})$, ${\mathbb{E}\,}d(B_{n})$,
${\mathbb{P}}\big{\\{}B_{n}\,,B_{m}\ \hbox{co-prime}\big{\\}}$,
${\mathbb{P}}\\{B_{n}\,\hbox{$z$-quasi-prime}\\}$,
${\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}$. We will also estimate the
probability ${\mathbb{P}}\\{D|B_{n}B_{m}\\}$ for $n<m$. The study of the
divisors of $B_{n}B_{m}$ is one piece of the estimation of the correlation
appearing in (2.8) when $n$ and $m$ are relatively near, details are given in
Section 6.

###  3.1. Basic estimates.

######  Proposition 3.1.

For any integers $d\leq n$,

(3.1) $\big{|}{\mathbb{P}}\\{d|B_{n}\\}-\frac{1}{d}\big{|}\leq{2\over
d}\sum_{1\leq j<d/2}e^{-{2nj^{2}/d^{2}}}.$

###### Proof.

From the formula

(3.2) $d\,\chi(d|B_{n})=\sum_{j=0}^{d-1}e^{2i\pi{j\over d}B_{n}},$

we get by integration,

(3.3) ${\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}={1\over d}\sum_{j=0}^{d-1}e^{i\pi
n{j\over d}}\big{(}\cos{\pi j\over d}\big{)}^{n}.$

As
$e^{in(\pi-x)}\cos^{n}(\pi-x)=(-1)^{n}e^{-inx}(-1)^{n}\cos^{n}x=e^{-inx}\cos^{n}x$,
we have in fact by distinguishing the case $d$ even from the case $d$ odd, the
simplified form

(3.4) ${\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}={1\over d}+{2\over d}\sum_{1\leq
j<d/2}(\cos{\pi n{j\over d}})\big{(}\cos{\pi j\over d}\big{)}^{n}.$

Thus

$\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-\frac{1}{d}\big{|}\leq{2\over
d}\sum_{1\leq j<d/2}e^{n\log(1-2\sin^{2}{\pi j\over 2d})}.$

As $\sin x\geq(2/\pi)x$, $0\leq x\leq\pi/2$, it follows that
$\log(1-2\sin^{2}{\pi j\over 2d})\leq-2\sin^{2}{\pi j\over 2d}\leq-2({j\over
d})^{2}$. Thus

$\displaystyle\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-\frac{1}{d}\big{|}$
$\displaystyle\leq$ $\displaystyle{2\over d}\sum_{1\leq
j<d/2}e^{-{2nj^{2}/d^{2}}}.$

This implies Example 2 in [8] without using Taylor’s expansion or Ramus’
formula.

∎

Since $\sum_{j\geq 1}e^{-{2nj^{2}/d^{2}}}\leq Cd/\sqrt{n}$, we get the useful
estimate:

######  Corollary 3.2.

$\sup_{1\leq d\leq n}\,\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{1\over
d}\big{|}\,\leq\,{C\over\sqrt{n}}.$

where $C$ is an absolute constant.

Proposition 3.1 is already sharp enough to imply the useful bound below.

######  Proposition 3.3.

$\sup_{n\geq
1}\sum_{d<\sqrt{n}}\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{1\over
d}\big{|}<\infty.$

###### Proof.

Let $A$ and $m$ be positive reals. Then for $d\geq 1$,

$\int_{m\over d+1}^{m\over d}e^{-At^{2}}{dt\over t}\geq e^{-A({m\over
d})^{2}}\int_{m\over d+1}^{m\over d}{dt\over t}=e^{-A({m\over
d})^{2}}\log(1+{1\over d})\geq{1\over 2d}e^{-A({m\over d})^{2}},$

since $\log 1+x\geq\frac{x}{2}$, if $0\leq x\leq 1$. Writing $n=\nu^{2}$ and
letting $m=\nu j$, $A=2$ gives

${1\over d}\sum_{j=1}^{d}e^{-2({\nu j\over d})^{2}}\leq
2\sum_{j=1}^{d}\int_{\nu j\over d+1}^{\nu j\over d}e^{-2t^{2}}{dt\over t}.$

Let $H=\sum_{1\leq d<\nu}\big{\\{}{1\over d}\sum_{1\leq j\leq d}e^{-2({\nu
j\over d})^{2}}\big{\\}}$. By permuting the order of summation, we get

$\displaystyle H$ $\displaystyle\leq$ $\displaystyle 2\sum_{1\leq
d<\nu}\Big{\\{}\sum_{1\leq j\leq d}\int_{\nu j\over d+1}^{\nu j\over
d}e^{-2t^{2}}{dt\over t}\Big{\\}}=2\sum_{1\leq j<\nu}\sum_{j\leq
d<\nu}\int_{\nu j\over d+1}^{\nu j\over d}e^{-2t^{2}}{dt\over t}$
$\displaystyle\leq$ $\displaystyle 2\sum_{1\leq j<\nu}\int_{{\nu
j\over\nu+1}}^{\nu}e^{-2t^{2}}{dt\over
t}=2\int_{{\nu+1\over\nu}}^{\nu}\Big{(}\sum_{j=1}^{\min(\nu,{\nu+1\over\nu}t)}1\Big{)}e^{-2t^{2}}{dt\over
t}$ $\displaystyle\leq$ $\displaystyle 4\int_{{1\over
2}}^{\infty}e^{-2t^{2}}dt=C.$

Consequently, by using (3.1),

$\sum_{d<\sqrt{n}}\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{1\over
d}\big{|}\leq 2\sum_{d<\sqrt{n}}{1\over d}\sum_{1\leq
j<d/2}e^{-{2nj^{2}/d^{2}}}\leq 2H\leq C,$

as claimed.∎

Some applications: (1) An estimate of ${\mathbb{E}\,}d(B_{n})$. Proposition
3.3 implies the following estimate.

######  Proposition 3.4 (Weber [41], Prop. 6).

For some universal constant $C$, we have

$\sup_{n\geq 2}\,\big{|}{\mathbb{E}\,}d(B_{n})-\log n\big{|}\leq C.$

We refer to the cited article for the proof.

This estimate is certainly improvable. The same question arises with
${\mathbb{E}\,}d^{2}(B_{n})$. We remark that

(3.5) $\displaystyle{\mathbb{E}\,}d^{2}(B_{n})$ $\displaystyle=$
$\displaystyle\sum_{d\leq n\atop{\delta}\leq
n}{\mathbb{P}}\\{[d,{\delta}]|B_{n}\\}\,=\,\sum_{[d,{\delta}]\leq
n}{\mathbb{P}}\\{[d,{\delta}]|B_{n}\\}.$

A relevant result is the following

######  Theorem 3.5 (Shi-Weber [33], Th. 2.1).

(i) If $0<{\sigma}<1$, then

$\displaystyle\sum_{[d,{\delta}]\leq N}\frac{1}{[d,{\delta}]^{{\sigma}}}$
$\displaystyle=$
$\displaystyle\frac{3}{\pi^{2}}\cdot\frac{1}{1-{\sigma}}N^{1-{\sigma}}(\log
N)^{2}+\mathcal{O}\left(N^{1-{\sigma}}(\log N)\right).$

(ii) Further, if ${\sigma}=1$,

$\displaystyle\sum_{[d,{\delta}]\leq N}\frac{1}{[d,{\delta}]}$
$\displaystyle=$ $\displaystyle\frac{1}{\pi^{2}}(\log
N)^{3}+\mathcal{O}\left((\log N)^{2}\right).$

(2) Estimates of ${\mathbb{E}\,}{\sigma}_{-1}(B_{n})$ and
${\mathbb{P}}\big{\\{}B_{n}\,{\it and}\,B_{m}\ {\it coprime}\big{\\}}$. Recall
that ${\sigma}_{s}(k)$ (section 2) is a multiplicative function and that
${\sigma}_{-s}(n)=n^{-s}{\sigma}_{s}(n)$.

######  Corollary 3.6.

$\Big{|}{\mathbb{E}\,}{\sigma}_{-1}(B_{n})-\zeta(2)\Big{|}\leq\ C\,{\log
n\over\sqrt{n}}.$

###### Proof.

Writing that ${\sigma}_{-1}(B_{n})=\sum_{d\leq n}\frac{1}{d}\chi\\{d|B_{n}\\}$
since $B_{n}\leq n$, we have

${\mathbb{E}\,}{\sigma}_{-1}(B_{n})=\sum_{d\leq
n}\frac{1}{d}\,{\mathbb{P}}\\{d|B_{n}\\}.$

Now

${\mathbb{E}\,}{\sigma}_{-1}(B_{n})-\sum_{d\leq n}{1\over d^{2}}=\sum_{d\leq
n}{1\over d}\big{(}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{1\over d}\big{)}.$

Whence,

$\big{|}{\mathbb{E}\,}{\sigma}_{-1}(B_{n})-\sum_{d\leq n}{1\over
d^{2}}\big{|}\leq{C\over\sqrt{n}}\ \sum_{d\leq n}{1\over d}\leq\ C\,{\log
n\over\sqrt{n}}.$

Consequently,

$\Big{|}{\mathbb{E}\,}{\sigma}_{-1}(B_{n})-\zeta(2)\Big{|}\leq\ C\,{\log
n\over\sqrt{n}}.$

∎

######  Corollary 3.7.

We have for $n>m\geq 2$,

$\displaystyle{\mathbb{P}}\big{\\{}B_{n}\,{\it and}\,B_{m}\ {\it
coprime}\big{\\}}$ $\displaystyle=$ $\displaystyle\sum_{d\leq
m\wedge(n-m)}{{\mu}(d)\over d^{2}}$ $\displaystyle+\mathcal{O}\Big{(}{\log
m\over\sqrt{m\wedge(n-m)}}+\Big{(}{m\wedge(n-m)\over
m\vee(n-m)}\Big{)}^{1/2}\Big{)}.$

Moreover,

$\lim_{m\to\infty\atop{n}/{m}\to\infty}{\mathbb{P}}\big{\\{}(B_{n},B_{m})=1\big{\\}}=\frac{1}{\zeta(2)}.$

###### Proof.

By using Möbius inversion formula,

${\mathbb{P}}\big{\\{}(B_{n},B_{m})=1\big{\\}}=\sum_{d\leq
m\wedge(n-m)}{\mu}(d){\mathbb{P}}\\{d|S_{m}\\}\,{\mathbb{P}}\\{d|S_{n-m}\\}$
$=\sum_{d\leq
m\wedge(n-m)}{\mu}(d)\Big{(}{\mathbb{P}}\big{\\{}d|S_{m}\big{\\}}-{1\over
d}+{1\over d}\Big{)}\,\Big{(}{\mathbb{P}}\big{\\{}d|S_{n-m}\big{\\}}-{1\over
d}+{1\over d}\Big{)}$ $=\sum_{d\leq
m\wedge(n-m)}{\mu}(d)\Big{(}{\mathbb{P}}\big{\\{}d|S_{m}\big{\\}}-{1\over
d}+{1\over d}\Big{)}\,\Big{(}{\mathbb{P}}\big{\\{}d|S_{n-m}\big{\\}}-{1\over
d}+{1\over d}\Big{)}$ $=\sum_{d\leq m\wedge(n-m)}{\mu}(d)\Big{(}{1\over
d}+\mathcal{O}\big{(}{1\over\sqrt{m}}\big{)}\Big{)}\,\Big{(}{1\over
d}+\mathcal{O}\big{(}{1\over\sqrt{n-m}}\big{)}\Big{)}$ $=\sum_{d\leq
m\wedge(n-m)}{{\mu}(d)\over d^{2}}+\mathcal{O}\Big{(}\sum_{d\leq m}{1\over
d}\big{(}{1\over\sqrt{m}}+{1\over\sqrt{n-m}}\big{)}+\Big{(}{m\wedge(n-m)\over\sqrt{m(n-m)}}\Big{)}\Big{)}$
$=\sum_{d\leq m\wedge(n-m)}{{\mu}(d)\over d^{2}}+\mathcal{O}\Big{(}{\log
m(\sqrt{m}+\sqrt{n-m})\over\sqrt{m(n-m)}}+\Big{(}{m\wedge(n-m)\over
m\vee(n-m)}\Big{)}^{1/2}\Big{)}.$

For instance: — If $(\log m)^{2}<n-m\leq m$,

$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}B_{n}\,{\it and}\,B_{m}\ {\it
coprime}\big{\\}}-\sum_{d\leq n-m}{{\mu}(d)\over d^{2}}\Big{|}$
$\displaystyle=$ $\displaystyle\mathcal{O}\Big{(}{\log
m\over\sqrt{n-m}}+\Big{(}{n-m\over m}\Big{)}^{1/2}\Big{)}.$

— If $n\geq 2m$,

$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}B_{n}\,{\it and}\,B_{m}\ {\it
coprime}\big{\\}}-\sum_{d\leq m}{{\mu}(d)\over d^{2}}\Big{|}$ $\displaystyle=$
$\displaystyle\mathcal{O}\Big{(}{\log m\over\sqrt{m}}+\Big{(}{m\over
n-m}\Big{)}^{1/2}\Big{)}.$

This implies the second claim.∎

This suggests to study the following problem: Let $n_{1}<n_{2}<\ldots<n_{k}$
be positive integers such that

$\min\\{n_{j}/n_{i},1\leq i<j\leq k\\}$

is large. To estimate the probability that
$B_{n_{1}},B_{n_{2}},\ldots,B_{n_{k}}$ are mutually coprime, namely

${\mathbb{P}}\big{\\{}(B_{n_{i}},B_{n_{j}})=1,\forall 1\leq i<j\leq
k\big{\\}}.$

That problem is related to a nice notion: for a subset of an integer lattice,
to be visible from the origin, in this case the set of random points $(x,y)$
in ${\mathbb{N}}^{2}$, $x\neq y$, with coordinates in
$\\{B_{n_{1}},B_{n_{2}},\ldots,B_{n_{k}}\\}$. Referring to section 3.8 in
Apostol [1], we say that two lattice points $P$ and $Q$ are mutually visible
if the segment which join them contains no lattice points other than the
endpoints $P$ and $Q$. We also recall that two lattice points $(a,b)$ and
$(m,n)$ are mutually visible if and only if $(a-m,b-n)=1$, or equivalently if
and only if $(a-m,b-n)$ is visible from the origin. The standard case
presented in [1] has clear link with Farey series, and Dirichlet’s easy
estimate on the number of corresponding visible points is a particular case of
a much more general result having a direct link with Riemann Hypothesis (RH).
See [42] for more.

###  3.2. Sharper uniform estimate and Theta function.

One might believe in view of Proposition 3.3 that the central comparison term
is $\frac{1}{d}$. But this is not so. The right comparison term -with a
sharper remainder term \- turns up to be more complicated, and is equal to
${\Theta(d,n)\over d}$ where $\Theta(d,n)$ is the Theta function,

(3.6) $\displaystyle{\Theta(d,n)=\sum_{\ell\in{\mathbb{Z}}}e^{in\pi{\ell\over
d}-{n\pi^{2}\ell^{2}\over 2d^{2}}},}$

$d\geq 1,\ n\geq 1$ being integers.

The following Theorem proved in Weber [51], provides a uniform estimate on the
whole range of divisors.

######  Theorem 3.8 ([51], Theorem II).

(1) We have the following uniform estimate:

(3.7) $\sup_{2\leq d\leq
n}\Big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{\Theta(d,n)\over
d}\Big{|}={\mathcal{O}}\Big{(}\frac{(\log n)^{5/2}}{n^{3/2}}\Big{)}.$

(2) Further, for any ${\alpha}>0$,

(3.8) $\sup_{d<\pi\sqrt{n\over 2{\alpha}\log
n}}\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{1\over
d}\big{|}={\mathcal{O}}_{\varepsilon}\big{(}n^{-{\alpha}+{\varepsilon}}\big{)},{\qquad}\quad(\forall{\varepsilon}>0)$

and for any $0<\rho<1$,

(3.9)
$\sup_{d<(\pi/\sqrt{2})n^{(1-\rho)/2}}\big{|}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{1\over
d}\big{|}={\mathcal{O}}_{\varepsilon}\big{(}e^{-(1-{\varepsilon})n^{\rho}}\big{)},{\qquad}\quad(\forall
0<{\varepsilon}<1).$

This covers the critical region of divisors $d\sim\sqrt{n}$.

######  Remark 3.9.

Poisson summation formula: for $x\in{\mathbb{R}},\ 0\leq{\delta}\leq 1$,

(3.10) $\sum_{\ell\in{\mathbb{Z}}}e^{-(\ell+{\delta})^{2}\pi
x^{-1}}=x^{1/2}\sum_{\ell\in{\mathbb{Z}}}e^{2i\pi\ell{\delta}-\ell^{2}\pi x},$

implies that

(3.11) $\frac{\Theta(d,n)}{d}=\sqrt{{2\over\pi n}}\sum_{z\equiv
0\,(d)}e^{-{(2z-n)^{2}\over 2n}}.$

######  Remark 3.10.

Formulas (3.7), (3.11) show that the general problem of estimating
${\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}$ reduces to the one of estimating the
$d$ series

(3.12) $\sum_{j}e^{-\frac{(jd-\rho)^{2}}{2n}},$

the summation being either over even rational numbers $j$, or over odd
rational numbers $j$, $\rho$ denoting the residue class modulo $d$ of $n$.

######  Remark 3.11.

A study of the special case of square-free divisors is made in Shi-Weber [34].

In the same 2004’s paper [51], the distribution of the smallest prime divisor
of $B_{n}$ was further studied. Let $(a,b)$ denote the greatest common divisor
of the integers $a$ and $b$. Let $P^{-}(m)$ denotes the smallest prime divisor
of the integer $m>1$ (by convention $P^{-}(1)=+\infty$). More precisely, we
derived from Theorem 3.8 and elementary Erathostène’s sieve, sharp estimates
of the probability ${\mathbb{P}}\\{P^{-}(B_{n})>\zeta\\}$, providing the right
central comparison term together with an already satisfactory and exploitable
error term.

######  Theorem 3.12 ([51], Th. I).

There exist a positive real $c>0$ and constants $C_{0}$, $\zeta_{0}$ such that
for $n$ large enough, we have the following estimate

$\Big{|}\hskip
1.0pt{\mathbb{P}}\big{\\{}P^{-}(B_{n})>\zeta\big{\\}}-{e^{-\gamma}\over\log\zeta}\,\Big{|}\leq{C_{0}\over\log^{2}\zeta}{\qquad}\qquad(\,\zeta_{0}\leq\zeta\leq
n^{c/\log\log n}\,)$

where ${\gamma}$ is Euler’s constant.

######  Remark 3.13.

Sharpenings of Theorem 3.12 are the object of a separate work.

We illustrate this on some examples.

(1) Estimate of ${\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}$. We begin with
clarifying the link between this probability and the Prime Number Theorem
(PNT). We first remark that

${\mathbb{P}}\Big{\\{}\big{|}B_{n}-\frac{n}{2}\big{|}>\frac{1}{2}\sqrt{3n\log
n}\Big{\\}}\ll\frac{1}{n}.$

Next by the local limit theorem there exists a numerical constant $C_{0}$ such
that for all positive $n$

$\displaystyle\sup_{k}\,\Big{|}{\mathbb{P}}\big{\\{}\mathcal{B}_{n}=k\\}-\sqrt{\frac{2}{\pi
n}}e^{-{(2k-n)^{2}\over 2n}}\Big{|}\ \leq\ \ \frac{C_{0}}{n^{3/2}}.$

Accordingly,

${\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}=\sqrt{\frac{2}{\pi
n}}\sum_{p\in\mathcal{P}\cap[\frac{n}{2}-\frac{1}{2}\sqrt{3n\log
n},\frac{n}{2}+\frac{1}{2}\sqrt{3n\log n}]}e^{-{(2p-n)^{2}\over
2n}}+\mathcal{O}\Big{(}\frac{1}{n}\Big{)}.$

The summation index is of type $\mathcal{P}\cap[x,x+y]$, $y\asymp\sqrt{x\log
x}$; thus its cardinality relies upon extensions of the PNT and cannot in turn
be estimated. The best unconditional estimate (slightly improved by Heath-
Brown) is due to Huxley who showed in [14] that the PNT extends to intervals
of the type $[x,x+x^{\vartheta}]$,
$x^{\frac{7}{12}}\leq{\vartheta}\leq\frac{x}{(\log x)^{4}}$, namely

$\\#\\{[x,x+x^{\vartheta}]\cap\mathcal{P}\\}\sim{x^{\vartheta}}/{\log x}.$

Assuming RH, the best result known to us states as follows,

(3.13) $\pi(x)-\pi(x-y)\,=\,\int_{x-y}^{x}\frac{{\rm d}t}{\log
t}+\mathcal{O}\Big{(}x^{\frac{1}{2}}\log\Big{\\{}\frac{y}{x^{\frac{1}{2}}\log
x}\Big{\\}}\Big{)}$

for $y$ in the range $2x^{\frac{1}{2}}\log x\leq y\leq x$. Hence for $M\geq 2$
fixed,

(3.14) $\pi(x)-\pi(x-Mx^{\frac{1}{2}}\log
x)\sim\,x^{\frac{1}{2}}\big{\\{}M+\mathcal{O}\big{(}\log M\big{)}\big{\\}}.$

See Heath-Brown [15]. The interested reader will fruitfully refer to
Montgomery and Soundararajan [23], p. 595. Accordingly any result based on an
assumption on the size’s order of ${\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}$
like for instance $\geq(\log n)^{-{\alpha}}$, ${\alpha}>0$ -which has an easy
interpretation on the gap between consecutive primes- is of no peculiar
interest. On the other hand, it follows from Remark 8.6 that for some constant
$C>0$,

(3.15) $(\log n)\,{\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}\geq C,$

for all integers $n$ in a set of density 1.

By using Theorem 3.12, we get another formulation.

######  Theorem 3.14.

${\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}\,=\,\sqrt{{2\over\pi
n}}\sum_{k\in{\mathbb{Z}}}\Big{(}\sum_{d\leq n\atop
P^{+}(d)\leq\sqrt{n}}{\mu}(d)\,e^{-{(2kd-n)^{2}\over
2n}}\Big{)}+{\mathcal{O}}\Big{(}{\log^{5/2}n\over n}\Big{)}.$

We first prove

######  Proposition 3.15.

For any positive integer $n$ and any positive real $y$, we have

${\mathbb{P}}\\{P^{-}(B_{n})>y\\}\,=\,\sum_{d\leq n\,,\,P^{+}(d)\leq
y}{\mu}(d)\,{\Theta(d,n)\over d}+{\mathcal{O}}\Big{(}{\log^{5/2}n\over
n^{3/2}}\sum_{d\leq n\,,\,P^{+}(d)\leq y}|{\mu}(d)|\Big{)}.$

We need a Lemma.

######  Lemma 3.16.

For any positive integer $n$ and any positive real $y$, we have

(3.16) ${\mathbb{P}}\\{P^{-}(B_{n})>y\\}=\sum_{P^{+}(d)\leq
y}{\mu}(d){\mathbb{P}}\\{d|B_{n}\\}.$

###### Proof.

Recall that the characteristic function of the set of integers $n$ such that
$P^{-}(n)>y$,

$\eta(n;y)=\begin{cases}1\quad&\ \hbox{ if $P^{-}(n)>y$}\cr 0\quad&\ \hbox{ if
$P^{-}(n)\leq y$}.\end{cases}$

is multiplicative. Thus by the Möbius inversion formula

(3.17) $\eta(n;y)=\sum_{d|n\atop P^{+}(d)\leq y}{\mu}(d){\qquad}{\qquad}(n\geq
1).$

Therefore by integration the Lemma follows. ∎

###### Proof of Proposition 3.15.

This is a direct consequence of Estimate (3.7) in Theorem 3.8. ∎

###### Proof of Theorem 3.12.

It follows from Proposition 3.15, since $B_{n}$ is prime if and only if
$P^{-}(B_{n})>\sqrt{n}$, that

(3.18) ${\mathbb{P}}\\{B_{n}\,\hbox{ prime}\\}\,=\,\sum_{d\leq n\atop
P^{+}(d)\leq\sqrt{n}}{{\mu}(d)\over
d}\Theta(d,n)+{\mathcal{O}}\Big{(}{\log^{5/2}n\over n^{3/2}}\sum_{d\leq n\atop
P^{+}(d)\leq\sqrt{n}}|{\mu}(d)|\Big{)}.$

Consider the error term. Let $\Psi(x,y)=\\#\\{m\leq x:P^{+}(m)\leq y\\}$. By
Theorem 1 p. 359 in [37], we have

$\displaystyle\sum_{d\leq n\,,\,P^{+}(d)\leq
y}|{\mu}(d)|\,\leq\,\Psi(n,y)\,\ll\,y\,e^{-(\frac{\log n}{\log
y})/2}{\qquad}\quad(n\geq y\geq 2).$

Thus,

(3.19) ${\mathbb{P}}\\{P^{-}(B_{n})>y\\}\,=\,\sum_{d\leq n\,,\,P^{+}(d)\leq
y}{{\mu}(d)\over d}\Theta(d,n)+{\mathcal{O}}\Big{(}y\,{\log^{5/2}n\over
n^{3/2}}\,e^{-\frac{\log n}{\log y}/2}\Big{)}.$

The proof is completed by taking $y=\sqrt{n}$ and applying (3.11). ∎

Let $a$ be real and ${\sigma}_{a}(n)=\sum_{d|k}d^{a}$. In a similar way we get
for $a=-1$,

######  Theorem 3.17.

${\mathbb{E}\,}{\sigma}_{-1}(B_{n})\,=\,\sqrt{{2\over\pi n}}\sum_{d\leq
n}\frac{1}{d}\sum_{z\equiv 0\,(d)}e^{-{(2z-n)^{2}\over
2n}}+{\mathcal{O}}\Big{(}{\log^{3}n\over n^{3/2}}\Big{)}.$

(2) Estimates related to Erdös and Zaremba function. Let
$\Phi(n)=\sum_{d|n}\frac{\log d}{d}$. This function appears in the study of
good lattice points in numerical integration. Erdös and Zaremba [9] showed
that

$\limsup_{n\to\infty}\frac{\Phi(n)}{(\log\log n)^{2}}=e^{\gamma},$

${\gamma}$ being Euler’s constant. The proof is based on the identity

(3.20)
$\displaystyle\Phi(n)=\sum_{i=1}^{r}\sum_{\nu_{i}=1}^{{\alpha}_{i}}\frac{\log
p_{i}^{\nu_{i}}}{p_{i}^{\nu_{i}}}\sum_{{\delta}|np_{i}^{-{\alpha}_{i}}}\frac{1}{{\delta}},{\qquad}{\qquad}(n=p_{1}^{{\alpha}_{1}}\ldots
p_{r}^{{\alpha}_{r}}),$

Consider the function

$\Psi(n)=\sum_{d|n}\frac{(\log d)(\log\log d)}{d}.$

In this case a formula similar to (3.20) no longer holds, the ”log-linearity”
being lost due to the extra factor $\log\log d$. We showed in the recent work
[41] that

$\displaystyle\limsup_{n\to\infty}\,\frac{\Psi(n)}{(\log\log
n)^{2}(\log\log\log n)}\,=\,e^{\gamma}.$

This required a new approach, and the proof is considerably more complicated.

######  Corollary 3.18.

${\mathbb{E}\,}\Psi(B_{n})=\sum_{d\leq n}\frac{(\log d)(\log\log
d)\Theta(d,n)}{d^{2}}+{\mathcal{O}}\Big{(}\frac{(\log n)^{7/2}(\log\log
n)}{n^{3/2}}\Big{)}$

###### Proof.

Writing $\sum_{d|B_{n}}=\sum_{d\leq n\,,\,d|B_{n}}$ we get,

${\mathbb{E}\,}\Psi(B_{n})=\sum_{d\leq n}\frac{(\log d)(\log\log
d)}{d}\big{(}{\mathbb{P}}\big{\\{}d|B_{n}\big{\\}}-{\Theta(d,n)\over
d}+{\Theta(d,n)\over d}\big{)}.$

Whence by Theorem 3.8,

${\mathbb{E}\,}\Psi(B_{n})=\sum_{d\leq n}\frac{(\log d)(\log\log
d)\Theta(d,n)}{d^{2}}+{\mathcal{O}}\Big{(}\frac{(\log n)^{7/2}(\log\log
n)}{n^{3/2}}\Big{)}.$

∎

###  3.3. A way back along Pascal’s matrices.

Let $f(j)$ be an arithmetical function. Consider the column vector
${\boldsymbol{\nu}}=\big{(}f(1),f(2),\ldots,f(n)\big{)}$. Let $P_{n}$ be the
$n$-size lower triangular Pascal matrix:

$\displaystyle P_{n}={\left[\begin{matrix}1\cr 1&1\cr 1&2&1\cr
1&3&3&1\cr\vdots&\vdots&\vdots&\vdots&\ddots\cr{{n}\choose{1}}&{{n}\choose{2}}&{{n}\choose{3}}&{{n}\choose{4}}&\cdots&{{n}\choose{n}}\end{matrix}\right]}$

Then $P_{n}{\boldsymbol{\nu}}=\,{\boldsymbol{w}}$ where
${\boldsymbol{w}}=\big{(}{\mathbb{E}\,}f(B_{1}),2{\mathbb{E}\,}f(B_{2}),\ldots,2^{n}{\mathbb{E}\,}f(B_{n})\big{)}$.
Call and Velleman ([5], Th. 1) identified $P^{-1}_{n}$, which is
$DP_{n}D^{-1}$ with $D$ as indicated:

$\displaystyle P^{-1}_{n}={\left[\begin{matrix}1\cr-1&1\cr
1&-2&1\cr-1&3&-3&1\cr\vdots&\vdots&\vdots&\vdots&\ddots\cr{{n}\choose{1}}&{{n}\choose{2}}&{{n}\choose{3}}&{{n}\choose{4}}&\cdots&{{n}\choose{n}}\end{matrix}\right]}$
$\displaystyle
D={\left[\begin{matrix}1\cr&-1\cr&{}&1\cr&{}&{}&-1\cr&{}&{}&{}&{}&\ddots\cr&{}&{}&{}&{}&&(-1)^{n+1}\end{matrix}\right]}$

So that knowing ${\boldsymbol{w}}$ we have -at least theoretically- a way back
to know ${\boldsymbol{\nu}}$. In condensed form $P_{n}^{-1}=Q_{n}$, where
$Q_{n}$ is the $n\times n$ matrix defined by

(3.21) $Q_{n}(i,j)=\begin{cases}(-1)^{i-j}{{i-1}\choose{j-1}}\quad&\hbox{if
$i\geq j$,}\cr 0\quad&\hbox{otherwise.}\end{cases}$

######  Proposition 3.19.

Let $f(j)$ be an arithmetical function. Then

(3.22)
$f(i)=\sum_{j=1}^{i}(-1)^{i-j}2^{j}{{i-1}\choose{j-1}}{\mathbb{E}\,}f(B_{j}),{\qquad}\quad
i\geq 2.$

###  3.4. Extension to all residue classes mod ($d$).

Theorem 3.8 was recently extended to all residue classes mod ($d$) in Weber
[45] with application to divisors in iid square integrable random walks. The
estimate obtained is uniform over all residue classes.

######  Theorem 3.20 ([45], Th. 3.1).

There exist two absolute constants $C$ and $n_{0}$ such that for all $n\geq
n_{0}$,

$\sup_{u\geq 0}\,\sup_{d\geq
2}\Big{|}{\mathbb{P}}\big{\\{}d|B_{n}+u\big{\\}}-{1\over
d}\sum_{0\leq|j|<d}e^{i\pi(2un){j\over d}}\ e^{-n{\pi^{2}j^{2}\over
2d^{2}}}\Big{|}\leq C\,(\log n)^{5/2}n^{-3/2}.$

Put

(3.23) $\Theta_{u}(d,n)=\sum_{\ell\in{\mathbb{Z}}}e^{i\pi(2u+n){j\over d}}\
e^{-n{\pi^{2}j^{2}\over 2d^{2}}}.$

Note that $\Theta_{0}(d,n)=\Theta(d,n)$. As a corollary we get,

######  Corollary 3.21.

For some absolute constant $C$, we have

$\sup_{u\geq 0}\,\sup_{d\geq
2}\Big{|}{\mathbb{P}}\big{\\{}d|B_{n}+u\big{\\}}-{\Theta_{u}(d,n)\over
d}\Big{|}\leq C\,(\log n)^{5/2}n^{-3/2},$

for all $n\geq n_{0}$.

The proof is based on the lemma below.

######  Lemma 3.22.

For any integers $d\geq 2$, $n\geq 2$ and $u\geq 0$,

$\displaystyle{\mathbb{P}}\big{\\{}d|B_{n}+u\big{\\}}$ $\displaystyle=$
$\displaystyle{1\over d}+{2\over d}\sum_{1\leq
j<d/2}\cos\big{(}\pi(2u+n){j\over d}\big{)}\big{(}\cos{\pi j\over
d}\big{)}^{n}.$

##  4\. Divisibility properties in i.i.d. random walks.

Theorem 3.8 extends to i.i.d. square integrable random walks.

######  Theorem 4.1 (Weber [45], Th. 2.1).

Let $X$ be a square integrable random variable taking values in the lattice
$\mathcal{L}(v_{0},1)=\big{\\{}v_{k}=v_{0}+k,k\in{\mathbb{Z}}\big{\\}}$, and
let $f(k)={\mathbb{P}}\\{X=v_{k}\\}$, for each $k$. Assume that

(4.1) ${\vartheta}_{X}:=\sum_{k\in{\mathbb{Z}}}\min(f(k),f(k+1))>0.$

Let $X_{i}$, $i\geq 1$ be independent, identically distributed random
variables having same law than $X$, and let $S_{n}=\sum_{j=1}^{n}X_{j}$, for
each $n$. Let $\bar{\mu}=\\{{\mu}_{k},k\in{\mathbb{Z}}\\}$ be a sequence of
non-negative reals such that $0<{\mu}_{k}<f(k)$, if $f(k)>0$, ${\mu}_{k}=0$ if
$f(k)=0$, let ${\mu}=\sum_{k\in{\mathbb{Z}}}{\mu}_{k}$, and assume that
$1-{\mu}<{\vartheta}_{X}$. Let also non-negative reals
$\bar{\tau}=\\{\tau_{k},k\in{\mathbb{Z}}\\}$ be solutions of the (solvable)
equation: ${\tau_{k-1}+\tau_{k}\over 2}=f(k)-{\mu}_{k},$ for all
$k\in{\mathbb{Z}}$. Let ${\vartheta}=\sum_{k\in{\mathbb{Z}}}\tau_{k}=1-{\mu}.$
Further let $s(t)=\sum_{k\in{\mathbb{Z}}}{\mu}_{k}\,e^{2i\pi v_{k}t}$ and
$\rho$ be such that $1-{\vartheta}<\rho<1$. Let $\widetilde{X}$ be the random
variable associated to $X$ and $\bar{\mu}$, and defined by the relation
${\mathbb{P}}\\{\widetilde{X}=v_{k}\\}={\tau_{k}}/{{\vartheta}}$, for all
$k\in{\mathbb{Z}}$. Then the following results hold: (i) There exists
$\theta=\theta(\rho,{\vartheta})$ with $0<\theta<{\vartheta}$, $C$ and $N$
such that for $n\geq N$,

$\displaystyle\sup_{u\geq 0}\,\sup_{d\geq
2}\Big{|}{\mathbb{P}}\\{d|S_{n}+u\\}-{1\over d}-{1\over d}\sum_{0<|\ell|<d}$
$\displaystyle\Big{(}e^{(i\pi{\ell\over d}-{\pi^{2}\ell^{2}\over
2d^{2}})}{\vartheta}\,{\mathbb{E}\,}\,e^{2i\pi{\ell\over
d}\widetilde{X}}+s\big{(}{\ell\over d}\big{)}\Big{)}^{n}\Big{|}$
$\displaystyle\leq\frac{C}{\theta^{3/2}}\ \frac{(\log
n)^{5/2}}{n^{3/2}}+2\rho^{n}.$

(ii) Let $\mathcal{D}$ be a test set of divisors $\geq 2$,
$\mathcal{D}_{\varphi}$ be the section of $\mathcal{D}$ at height ${\varphi}$
and $|\mathcal{D}_{\varphi}|$ denote its cardinality. Then,

$\displaystyle\sum_{n=N}^{\infty}\ \sup_{u\geq 0}\,\sup_{{\varphi}\geq
2}\,{1\over|\mathcal{D}_{\varphi}|}\sum_{d\in\mathcal{D}_{\varphi}}\,\Big{|}{\mathbb{P}}\\{d|S_{n}+u\\}-{1\over
d}\Big{|}$ $\displaystyle\leq$
$\displaystyle\frac{C_{1}}{{\vartheta}}\,+\frac{C_{2}}{\theta^{3/2}}+\frac{2\rho^{2}}{1-\rho},$

where $C_{1}=\frac{2e^{{\pi^{2}/4}}}{(1-e^{-{\pi^{2}/16}})}$,
$C_{2}=C\,\sum_{n=N}^{\infty}\frac{(\log{n})^{5/2}}{({n})^{3/2}}$ .

Condition (4.1) defines an already very large class of random variables,
characterized by the property of having a Bernoulli part. That notion is due
to McDonald [20], who introduced an ingenious coupling method in the study of
a famous limit theorem: the local limit theorem which has interface with
Number Theory. This method is particularly relevant in our proof. Concretely,
let $\\{\tau_{k},k\in{\mathbb{Z}}\\}$ of non-negative reals such that

(4.2) $\tau_{k-1}+\tau_{k}\leq
2f(k),{\qquad}{\qquad}\sum_{k\in{\mathbb{Z}}}\tau_{k}={\vartheta}.$

For instance $\tau_{k}=\frac{{\vartheta}}{\nu_{X}}\,\min(f(k),f(k+1))$ is
suitable. Define a pair of random variables $(V,{\varepsilon})$ as follows:

(4.3)
$\displaystyle{\qquad}{\qquad}\begin{cases}{\mathbb{P}}\\{(V,{\varepsilon})=(v_{k},1)\\}=\tau_{k},\cr{\mathbb{P}}\\{(V,{\varepsilon})=(v_{k},0)\\}=f(k)-{\tau_{k-1}+\tau_{k}\over
2}.\end{cases}{\qquad}(\forall k\in{\mathbb{Z}})$

Then we have the following decomposition which iterates well to iid sums
$S_{n}$.

######  Lemma 4.2.

Let $L$ be a Bernoulli random variable which is independent of
$(V,{\varepsilon})$, and put $Z=V+{\varepsilon}L$. We have
$Z\buildrel\mathcal{D}\over{=}X$.

##  5\. Divisibility properties of non i.i.d. square integrable random walks.

Let $X=\\{X_{i},i\geq 1\\}$ be a sequence of independent variables taking
values in ${\mathbb{Z}}$, and let $S_{n}=\sum_{k=1}^{n}X_{k}$, for each $n$.
To our knowledge there is no study of divisors, in particular of their value
distribution, in general independent random walks. However divisibility is
present in the study the local limit theorem. The sequence $X$ is
_asymptotically uniformly distributed_ , in short a.u.d., if for any $d\geq 2$
and $m=0,1,\ldots,d-1$, we have

(5.1) $\lim_{n\to\infty}\ {\mathbb{P}}\\{S_{n}\equiv
m\,{\rm(mod)}\,d\\}=\frac{1}{d}.$

Let us assume that the random variables $X_{i}$ take values in a common
integer lattice $\mathcal{L}(v_{0},D)$, namely defined by the sequence
$v_{k}=v_{0}+Dk$, $k\in{\mathbb{Z}}$, $D>0$, and are square integrable, and
let

(5.2) $M_{n}={\mathbb{E}\,}S_{n},{\qquad}B_{n}^{2}={\rm Var}(S_{n})\to\infty.$

We say that the local limit theorem (in the usual form) is _applicable_ to $X$
if

(5.3)
$\sup_{N=v_{0}n+Dk}\Big{|}B_{n}\,{\mathbb{P}}\\{S_{n}=N\\}-{D\over\sqrt{2\pi}}e^{-{(N-M_{n})^{2}\over
2B_{n}^{2}}}\Big{|}=o(1),{\qquad}\quad n\to\infty.$

By well-known Rozanov’s result [29], the local limit theorem is applicable to
$X$ only if $X$ satisfies the a.u.d. property.

In a recent work based on Poisson summation formula, the stronger result is
proved, establishing an explicit link between the local limit theorem and the
a.u.d. property, through a quantitative estimate of the difference
${\mathbb{P}}\\{S_{n}\equiv\,m\\!\hbox{\rm{ (mod $h$)}}\\}-{1}/{h}$.

######  Theorem 5.1 (Weber [44], Th. 1.4).

Let $X=\\{X_{i},i\geq 1\\}$ be a sequence of independent variables taking
values in ${\mathbb{Z}}$, and let $S_{n}=\sum_{k=1}^{n}X_{k}$, for each $n$.
Assume that, ($\mathcal{A}$) For some function $1\leq\phi(t)\uparrow\infty$ as
$t\to\infty$, and some constant $C$, we have for all $n$

(5.4)
$\sup_{m\in{\mathbb{Z}}}\Big{|}B_{n}{\mathbb{P}}\big{\\{}S_{n}=m\big{\\}}-{1\over\sqrt{2\pi}}\
e^{-{(m-M_{n})^{2}\over 2B_{n}^{2}}}\Big{|}\,\leq\,{C\over\,\phi(B_{n})}.$

Then there exists a numerical constant $C_{1}$, such that for all
$0<{\varepsilon}\leq 1$, all $n$ such that $B_{n}\geq 6$, and all $h\geq 2$,

$\displaystyle\sup_{{\mu}=0,1,\ldots,h-1}\,$
$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}S_{n}\equiv\,{\mu}\ \hbox{\rm{ (mod
$h$)}}\big{\\}}-\frac{1}{h}\Big{|}$
$\displaystyle\leq{1\over\sqrt{2\pi}\,B_{n}}+\frac{2C}{h\,\sqrt{{\varepsilon}}\,\phi(B_{n})}+{\mathbb{P}}\Big{\\{}\frac{|S_{n}-M_{n}|}{B_{n}}>\frac{1}{\sqrt{\varepsilon}}\Big{\\}}+C_{1}\,e^{-1/(16{\varepsilon})}.$

It follows from the proof that $C_{1}=2e\sqrt{\pi}$ is suitable. Choosing
${\varepsilon}=\phi(B_{n})^{-2/3}$ and using Tchebycheff’s inequality, we get
the following

######  Corollary 5.2.

For all $n$ such that $B_{n}\geq 6$, and all $h\geq 2$, we have

(5.5)
$\displaystyle\sup_{{\mu}=0,1,\ldots,h-1}\,\Big{|}{\mathbb{P}}\big{\\{}S_{n}\equiv\,{\mu}\
\hbox{\rm{ (mod $h$)}}\big{\\}}-\frac{1}{h}\Big{|}\leq H_{n},$

with

(5.6) $\displaystyle
H_{n}={1\over\sqrt{2\pi}\,B_{n}}+\frac{1+2{C}/{h}}{\phi(B_{n})^{2/3}}+C_{1}\,e^{-(1/16)\phi(B_{n})^{2/3}}.$

Theorem 5.1 implies Rozanov’s result, since by definition such a function
$\phi$ exists if the local limit theorem is applicable to $X$.

Instead of assumption ($\mathcal{A}$), consider now the following assumption
($\mathcal{B}$)
${\vartheta}_{X_{j}}=\displaystyle{\sum_{k\in{\mathbb{Z}}}}{\mathbb{P}}\\{X_{j}=k\\}\wedge{\mathbb{P}}\\{X_{j}=k+1\\}>0$,
for each $j$, and
$\nu_{n}=\displaystyle{\sum_{j=1}^{n}}{\vartheta}_{j}\uparrow\infty$.

We have the following sharp results.

######  Theorem 5.3 ([44], Th. 4.3).

Let $D=1$. Suppose that assumption ($\mathcal{B}$) is fulfilled. Let
${\alpha}\\!>\\!{\alpha}^{\prime}\\!>\\!0$, $0\\!<\\!{\varepsilon}\\!<\\!1$.
Then for each $n$ such that

$|x|\leq\frac{1}{2}\sqrt{\frac{2{\alpha}\log(1-\epsilon)\nu_{n}}{(1-\epsilon)\nu_{n}}}{\qquad}\Rightarrow{\qquad}{\sin
x\over x}\geq({\alpha}^{\prime}/{\alpha})^{1/2},$

we have

$\displaystyle\sup_{u\geq 0}\,\sup_{d<\pi\sqrt{(1-\epsilon)\nu_{n}\over
2{\alpha}\log(1-\epsilon)\nu_{n}}}\ \Big{|}{\mathbb{P}}\\{d|S_{n}+u\\}-{1\over
d}\Big{|}$ $\displaystyle\leq$ $\displaystyle
2\,e^{-\frac{\epsilon^{2}}{2}\nu_{n}}+\,\big{(}(1-\epsilon)\nu_{n}\big{)}^{-{\alpha}^{\prime}}.$

######  Theorem 5.4 ([44], Th. 4.6).

Let $D=1$. Suppose that assumption ($\mathcal{B}$) is fulfilled. Let
$0<\rho<1$ and $0<{\varepsilon}<1$. Then for each $n$ such that

$|x|\leq\frac{1}{2}\,\sqrt{\frac{2}{((1-\epsilon)\nu_{n})^{1-\rho}}}{\qquad}\Rightarrow{\qquad}{\sin
x\over x}\geq\sqrt{1-{\varepsilon}}$

we have

$\displaystyle\sup_{u\geq
0}\,\sup_{d<(\pi/\sqrt{2})((1-{\varepsilon})\nu_{n})^{(1-\rho)/2}}\
\big{|}{\mathbb{P}}\\{d|S_{n}+u\\}-{1\over d}\big{|}$ $\displaystyle\leq$
$\displaystyle
2e^{-\frac{\epsilon^{2}}{2}\nu_{n}}+e^{-((1-\epsilon)\nu_{n})^{\rho}}.$

We refer the reader to [44] for the proofs of these results. We also refer to
our recent monograph with Szewczak [36] for more.

##  6\. Distribution of divisors of ${B_{n}B_{m}}$.

This task is more complicated. A key function is the (multiplicative) function

(6.1) $\displaystyle\varrho_{k}(D):=\\#\big{\\{}1\leq y\leq D:\
D|y^{2}+ky\big{\\}},{\qquad}k=0,1,\ldots$

which it is not so surprising in view of the elementary decomposition
$B_{n}B_{m}=B_{n}^{2}+B_{n}(B_{m}-B_{n})$. As mentioned in section 3, that
study is used in [40] in the control of the correlation function (2.8), more
precisely in the case $n<m\leq n+n^{c}$, $c>0$, $c$ being small, where the
following intermediate bound appears (hence also $\varrho_{k}(.)$),

$\displaystyle{\mathbb{P}}\\{d|B_{n}\,,\,{\delta}|B_{m}\\}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\\{d|B_{n}\,,\,{\delta}|B_{m}\,,\,B_{m}-B_{n}=0\\}+{\mathbb{P}}\\{d|B_{n}\,,\,{\delta}|B_{m}\,,\,B_{m}-B_{n}>0\\}$
$\displaystyle=$ $\displaystyle
2^{-(m-n)}\,{\mathbb{P}}\\{d|B_{n}\,,\,{\delta}|B_{n}\\}+{\mathbb{P}}\\{d|B_{n}\,,\,{\delta}|B_{m}\,,\,B_{m}-B_{n}>0\\}$
$\displaystyle\leq$ $\displaystyle
2^{-(m-n)}\,{\mathbb{P}}\\{[d,{\delta}]|B_{n}\\}+{\mathbb{P}}\\{d{\delta}|B_{n}B_{m}\,,\,B_{m}-B_{n}>0\\}.$

Note that ${\mathbb{P}}\\{d|B_{n}\,,\,{\delta}|B_{m}\\}>0$, only if
$m-n\geq(d,{\delta})$. By using independence, the characteristic function of
$B_{n}B_{m}$ expresses as follows

${\mathbb{E}\,}e^{i\upsilon B_{n}B_{m}}={1\over
2^{n}2^{m-n}}\sum_{k=0}^{m-n}{{m-n}\choose{k}}\sum_{h=0}^{n}{{n}\choose{h}}e^{i\upsilon(h^{2}+kh)}.$

And so, we begin with

(6.2) $\displaystyle{\qquad}{\mathbb{P}}\\{D|B_{n}B_{m}\\}$ $\displaystyle=$
$\displaystyle{\mathbb{E}\,}\Big{(}{1\over D}\sum_{j=0}^{D-1}e^{2i\pi{j\over
D}B_{n}B_{m}}\Big{)}$ (6.3) $\displaystyle=$ $\displaystyle{1\over
2^{m-n}}\sum_{k=0}^{m-n}{{m-n}\choose{k}}{1\over
D}\sum_{j=0}^{D-1}\Big{(}{1\over
2^{n}}\sum_{h=0}^{n}{{n}\choose{h}}e^{2i\pi{j\over D}(h^{2}+kh)}\Big{)}.$

######  Theorem 6.1.

For any ${\varepsilon}>0$, there exists a constant $C_{\varepsilon}$ depending
on ${\varepsilon}$ only, such that for any positive integers $n,m,D$ with
$m>n$

(6.4) $\Big{|}{\mathbb{P}}\\{D|B_{n}B_{m}\\}-{1\over
D2^{m-n}}\sum_{k=0}^{m-n}{{{m-n}\choose{k}}}\varrho_{k}(D)\Big{|}\leq
C_{\varepsilon}\left({D^{1+{\varepsilon}}\over n}\right)^{1/2}.$

The function $\varrho_{k}(D)$ will be made explicit in Theorem 6.6. A
combination of both results will lead to a useful bound of
${\mathbb{P}}\\{D|B_{n}B_{m}\\}$ stated in Theorem 6.8. We first prove Theorem
6.1. The main idea of the proof consists with controlling the difference

${\Delta}={1\over 2^{n}}\sum_{h=0}^{n}{{n}\choose{h}}e^{2i\pi{j\over
D}(h^{2}+kh)}-{1\over n}\sum_{h=0}^{n-1}e^{2i\pi{j\over D}(h^{2}+kh)},$

in which the first average is the last Euler sum in (6.2), and the second one,
its Cesàro means counterpart. Let $0\leq\ell\leq n$ be some integer,
$\ell=LD+{\mu}$, $0\leq{\mu}<D$. Obviously,

(6.6) $\displaystyle S:={1\over\ell}\sum_{h=0}^{\ell-1}e^{2i\pi{j\over
D}(h^{2}+kh)}$ $\displaystyle=$ $\displaystyle{1\over
D}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}+{1\over\ell}\sum_{h=0}^{{\mu}}e^{2i\pi{j\over D}(h^{2}+kh)}$
$\displaystyle+L\big{(}{1\over\ell}-{1\over
LD}\big{)}\sum_{h=0}^{D-1}e^{2i\pi{j\over D}(h^{2}+kh)}.$

It follows from (6.6), that for $j=1,\ldots,D$,

$\displaystyle\Big{|}S-{1\over D}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}\Big{|}$ $\displaystyle\leq$
$\displaystyle{1\over\ell}\Big{(}\big{|}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}\big{|}+\big{|}\sum_{h=0}^{{\mu}}e^{2i\pi{j\over
D}(h^{2}+kh)}\big{|}\Big{)}.$

We rewrite this for later use under the following form.

######  Lemma 6.2.

Let $\ell\geq 1$, $\ell\equiv{\mu}\,{\rm mod}(D)$ and $0\leq{\mu}<D$. For
$j=1,\ldots,D$,

$\displaystyle\Big{|}\sum_{h=0}^{\ell-1}e^{2i\pi{j\over
D}(h^{2}+kh)}-{\ell\over D}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}\Big{|}$ $\displaystyle\leq$
$\displaystyle\big{|}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}\big{|}+\big{|}\sum_{h=0}^{{\mu}}e^{2i\pi{j\over
D}(h^{2}+kh)}\big{|}.$

Thus the study of ${\Delta}$ reduces to the one of the difference

${\Delta}^{\prime}={1\over 2^{n}}\sum_{h=0}^{n}{{n}\choose{h}}e^{2i\pi{j\over
D}(h^{2}+kh)}-{1\over D}\sum_{h=0}^{D-1}e^{2i\pi{j\over D}(h^{2}+kh)}.$

By linearity of Euler summation, it suffices to have at disposal a bound for
Euler sums, and we have a classical tool from the theory of divergent series.

######  Lemma 6.3.

Let $\\{a_{k},k\geq 0\\}$ be a sequence of reals. Put
$A_{\ell}=\sum_{k=0}^{\ell}a_{k}$, $\ell\geq 0$. There exists an absolute
constant $C$ such that for every positive integer $n$

(6.7)
$\big{|}\sum_{h=0}^{n}2^{-n}{{n}\choose{h}}a_{h}\big{|}\leq{C\over\sqrt{n}}\max_{\ell=0}^{n}\big{|}A_{\ell}\big{|}.$

This is easily seen by using Abel summation and well-known property of the
binomial distribution (Feller [10], p. 151). (A consequence is Theorem 149 in
Hardy [14].) Applying it with the choice

$a_{h}=e^{2i\pi{j\over D}(h^{2}+kh)}-{1\over D}\sum_{y=0}^{D-1}e^{2i\pi{j\over
D}(y^{2}+ky)}{\qquad}h=0,1,\ldots,n,$

we get in view of Lemma 6.2,

(6.8) $\displaystyle{\Delta}^{\prime}$ $\displaystyle\leq$
$\displaystyle{C\over\sqrt{n}}\max_{{\mu}=0}^{D-1}\big{|}\sum_{h=0}^{{\mu}}e^{2i\pi{j\over
D}(h^{2}+kh)}\big{|}.$

Whence the intermediate estimate.

######  Corollary 6.4.

For some absolute constant $C$,

(6.9) $\displaystyle\Big{|}\sum_{h=0}^{n}2^{-n}{{n}\choose{h}}e^{2i\pi{j\over
D}(h^{2}+kh)}-$ $\displaystyle{1\over D}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}\Big{|}$ (6.10)
$\displaystyle\leq{C\over\sqrt{n}}\bigg{(}\max_{{\mu}=0}^{D^{\prime}-1}\big{|}\sum_{h=0}^{{\mu}}e^{2i\pi{j^{\prime}\over
D^{\prime}}(h^{2}+kh)}\big{|}\bigg{)},$

where $j^{\prime}=j/(j,D)$, $D^{\prime}=D/(j,D)$.

The Lemma below is just a slight reformulation of Sarkösy’s estimate [30].

######  Lemma 6.5.

Let ${\alpha}$ be a real number and $a,q$ be positive integers such that
$(a,q)=1$ and $|{\alpha}-a/q|<1/q^{2}$. Then, for any positive integer $M$,

(6.11) $\displaystyle\sup_{k\geq
0}\,\big{|}\sum_{x=1}^{M}e^{2i\pi{\alpha}(x^{2}+kx)}\big{|}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{u=1-M}^{M-1}\Big{|}\sum_{y=\max(1-u,1)}^{\min(M,M-u)}e^{4i\pi{\alpha}uy}\Big{|}$
(6.12) $\displaystyle\leq$ $\displaystyle 49\Big{\\{}{M^{2}\over q}+(M\log
q)+q\log q\Big{\\}}.$

###### Proof.

The last inequality in (6.11) is precisely what is established in the proof of
Lemma 4 p. 128 in [30]. Let $T=\sum_{x=1}^{M}e^{2i\pi{\alpha}(x^{2}+kx)}$. On
expanding $|T|^{2}$, we get

$\displaystyle|T|^{2}$ $\displaystyle=$
$\displaystyle\sum_{y=1}^{M}\sum_{u=1-y}^{M-y}e^{2i\pi{\alpha}u(u+2y+k)}=\sum_{u=1-M}^{M-1}\sum_{y=\max(1-u,1)}^{\min(M,M-u)}e^{2i\pi{\alpha}u(u+2y+k)}$
$\displaystyle\leq$
$\displaystyle\sum_{u=1-M}^{M-1}\Big{|}\sum_{y=\max(1-u,1)}^{\min(M,M-u)}e^{4i\pi{\alpha}uy}\Big{|}.$

So that,

$\sup_{k\geq
0}\Big{|}\sum_{x=1}^{M}\sum_{y=1}^{M}e^{2i\pi{\alpha}(x^{2}-y^{2}+k(x-y))}\Big{|}^{2}\leq
49\Big{\\{}{M^{2}\over q}+(M\log q)+q\log q\Big{\\}},$

or

$\sup_{k\geq 0}\Big{|}\sum_{x=1}^{M}e^{2i\pi{\alpha}(x^{2}+kx)}\Big{|}\leq
7\Big{\\{}{M\over\sqrt{q}}+\sqrt{M\log q}+\sqrt{q\log q}\Big{\\}}.$

∎

We can now pass to the proof of Theorem 6.4.

###### Proof of Theorem 6.4.

Returning to (6.9), we get

$\displaystyle\sup_{k\geq 0}\big{|}\sum_{y=1}^{{\mu}}e^{2i\pi{j^{\prime}\over
D^{\prime}}(y^{2}+ky)}\big{|}$ $\displaystyle\leq$ $\displaystyle
7\Big{\\{}{{\mu}\over\sqrt{D^{\prime}}}+\sqrt{{\mu}\log
D^{\prime}}+\sqrt{D^{\prime}\log D^{\prime}}\Big{\\}}$
$\displaystyle({\mu}\leq D^{\prime})\quad$ $\displaystyle\leq$ $\displaystyle
7\Big{\\{}\sqrt{D^{\prime}}+2\sqrt{D^{\prime}\log D^{\prime}}\Big{\\}}$
$\displaystyle\leq$ $\displaystyle
C_{\varepsilon}(D^{\prime})^{1/2+{\varepsilon}}\leq
C_{\varepsilon}(D)^{1/2+{\varepsilon}},$

where $j^{\prime}=j/(j,D)$, $D^{\prime}=D/(j,D)$. Thus

(6.13) $\displaystyle\Big{|}\sum_{h=0}^{n}2^{-n}{{n}\choose{h}}e^{2i\pi{j\over
D}(h^{2}+kh)}-$ $\displaystyle{1\over D}\sum_{h=0}^{D-1}e^{2i\pi{j\over
D}(h^{2}+kh)}\Big{|}$ (6.14)
$\displaystyle\leq{C\over\sqrt{n}}\bigg{(}2+\max_{{\mu}=1}^{D^{\prime}-1}\big{|}\sum_{h=1}^{{\mu}}e^{2i\pi{j^{\prime}\over
D^{\prime}}(h^{2}+kh)}\big{|}\bigg{)}\leq{C_{\varepsilon}(D)^{1/2+{\varepsilon}}\over\sqrt{n}}.$

Whence,

(6.15) $\sup_{0\leq j<D}\sup_{0\leq k\leq
m-n}\Big{|}\sum_{h=0}^{n}2^{-n}{{n}\choose{h}}e^{2i\pi{j\over
D}(h^{2}+kh)}-{1\over D}\sum_{h=0}^{D-1}e^{i\pi{2j\over
D}(h^{2}+kh)}\Big{|}\leq C_{\varepsilon}\left({D^{1+{\varepsilon}}\over
n}\right)^{1/2}\\!\\!.$

As

(6.16) ${1\over D^{2}}\sum_{j=0}^{D-1}\sum_{h=0}^{D-1}e^{i\pi{2j\over
D}(h^{2}+kh)}={\\#\big{\\{}1\leq y\leq D:D|y^{2}+ky\big{\\}}\over
D}={\varrho_{k}(D)\over D}\\!,$

it follows

(6.17) $\sup_{0\leq k\leq m-n}\bigg{|}{1\over
D}\sum_{j=0}^{D-1}\sum_{h=0}^{n}2^{-n}{{n}\choose{h}}e^{2i\pi{j\over
D}(h^{2}+kh)}-{\varrho_{k}(D)\over D}\Bigg{|}\leq
C_{\varepsilon}\Big{(}{D^{1+{\varepsilon}}\over n}\Big{)}^{1/2}\\!\\!.$

By combining now (6.17) with (6.2), we obtain

$\Big{|}{\mathbb{P}}\\{D|B_{n}B_{m}\\}-\sum_{k=0}^{m-n}{{{m-n}\choose{k}}\over
2^{(m-n)}}{\varrho_{k}(D)\over D}\Big{|}\leq
C_{\varepsilon}\,\Big{(}{D^{1+{\varepsilon}}\over n}\Big{)}^{1/2}.$

∎

It remains to compute $\varrho_{k}(D)$. Introduce some notation. Let
$v_{p}(d)$ denote the $p$-adic valuation of $d$, $p$ being a prime number,
namely $p^{v_{p}(d)}||d$, also

(6.18) $\displaystyle D_{1/2}\,:=\,\prod_{p|D}p^{\lfloor{v_{p}(D)\over
2}\rfloor}.$

######  Theorem 6.6.

We have

$\varrho_{k}(D)=\begin{cases}\ \,D_{1/2}{\qquad}&\hbox{ if \ $k=0$,}\cr\
\,2^{\\#\\{p\,:\,1\leq v_{p}(k)<v_{p}(D)/2\\}}\,(k,D_{1/2}){\qquad}&\hbox{ if
\ $k\geq 1$.}\end{cases}$

The proof is given in Appendix. We deduce

######  Corollary 6.7.

For any positive integers $D,k$,

$\varrho_{k}(D)\leq 2^{{\omega}((k,D_{1/2}))}\,(k,D_{1/2}){\qquad}{\rm
and}{\qquad}\varrho_{0}(D)\leq\sqrt{D}.$

###### Proof.

Immediate. ∎

######  Theorem 6.8.

We have for any positive integers $n,m,D$,

$\displaystyle{\mathbb{P}}\\{D|B_{n}B_{m}\\}$ $\displaystyle\leq$
$\displaystyle{1\over
D}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\Big{(}\sum_{u|(D_{1/2}/d)}{\mu}(u)\,{\mathbb{P}}\\{ud|B_{m-n}\\}\Big{)}$
$\displaystyle+{1\over
2^{m-n}\sqrt{D}}+C_{\varepsilon}\left({D^{1+{\varepsilon}}\over
n}\right)^{1/2}.$

###### Proof.

By Theorem 6.1, for any ${\varepsilon}>0$, there exists a constant
$C_{\varepsilon}$ depending on ${\varepsilon}$ only, such that for any
positive integers $n,m,D$ with $m>n$

(6.19) $\Big{|}{\mathbb{P}}\\{D|B_{n}B_{m}\\}-{1\over
D2^{m-n}}\sum_{k=0}^{m-n}{{{m-n}\choose{k}}}\varrho_{k}(D)\Big{|}\leq
C_{\varepsilon}\left({D^{1+{\varepsilon}}\over n}\right)^{1/2}.$

By Corollary 6.7,

(6.20) $\displaystyle{1\over
D2^{m-n}}\sum_{k=0}^{m-n}{{m-n}\choose{k}}\,\varrho_{k}(D)\ =\
{\varrho_{0}(D)\over 2^{m-n}D}+{1\over
D2^{m-n}}\sum_{k=1}^{m-n}{{m-n}\choose{k}}\,\varrho_{k}(D)$ (6.21)
$\displaystyle\leq$ $\displaystyle{1\over 2^{m-n}\sqrt{D}}+{1\over
D2^{m-n}}\sum_{k=1}^{m-n}{{m-n}\choose{k}}2^{{\omega}((k,D_{1/2}))}\,(k,D_{1/2})$
(6.22) $\displaystyle=$ $\displaystyle{1\over 2^{m-n}\sqrt{D}}+{1\over
D2^{m-n}}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\sum_{k=1\atop(k,D_{1/2})=d}^{m-n}{{m-n}\choose{k}}.$

Let ${\delta}$ be the arithmetical function defined by

(6.23) $\displaystyle{\delta}(n)=\begin{cases}1\quad&{\rm if}\ n=1,\cr
0\quad&{\rm if}\ n\not=1.\end{cases}$

Recall that

(6.24) $\displaystyle\sum_{d|n}{\mu}(d)={\delta}(n).$

Consider first the sub-sum corresponding to $d=1$. We have

$\displaystyle{1\over
2^{m-n}}\sum_{k=1\atop(k,D_{1/2})=1}^{m-n}{{m-n}\choose{k}}$ $\displaystyle=$
$\displaystyle{1\over
2^{m-n}}\sum_{k=1}^{m-n}{{m-n}\choose{k}}{\delta}\big{(}(k,D_{1/2})\big{)}$
$\displaystyle=$ $\displaystyle{1\over
D2^{m-n}}\sum_{k=1}^{m-n}{{m-n}\choose{k}}\Big{(}\sum_{u|(k,D_{1/2})}{\mu}(u)\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{u|D_{1/2}}{\mu}(u){1\over
2^{m-n}}\sum_{k=1\atop u|k}^{m-n}{{m-n}\choose{k}}$ $\displaystyle=$
$\displaystyle\sum_{u|D_{1/2}}{\mu}(u)\,\big{(}{\mathbb{P}}\\{u|B_{m-n}\\}-{1\over
2^{m-n}}\big{)}$

Now let $(k,D_{1/2})=d>1$. Let $k={\kappa}d$. Then $(k,D_{1/2}/d)=1$, and so

$\displaystyle{1\over
2^{m-n}}\sum_{k=1\atop(k,D_{1/2})=d}^{m-n}{{m-n}\choose{k}}\ =\ {1\over
2^{m-n}}\sum_{1\leq{\kappa}\leq(m-n)/d\atop({\kappa},D_{1/2}/d)=1}{{m-n}\choose{{\kappa}d}}$
$\displaystyle=$ $\displaystyle{1\over
2^{m-n}}\sum_{1\leq{\kappa}\leq(m-n)/d}{{m-n}\choose{{\kappa}d}}{\delta}\big{(}({\kappa},D_{1/2}/d)\big{)}$
$\displaystyle=$ $\displaystyle{1\over
2^{m-n}}\sum_{1\leq{\kappa}\leq(m-n)/d}{{m-n}\choose{{\kappa}d}}\Big{(}\sum_{u|({\kappa},D_{1/2}/d)}{\mu}(u)\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{u|D_{1/2}/d}{\mu}(u){1\over
2^{m-n}}\sum_{1\leq{\kappa}\leq(m-n)/d\atop
u|{\kappa}}{{m-n}\choose{{\kappa}d}}$
$\displaystyle\buildrel({\kappa}=u\tau)\over{=}$
$\displaystyle\sum_{u|D_{1/2}/d}{\mu}(u){1\over 2^{m-n}}\sum_{1\leq ud\tau\leq
m-n}{{m-n}\choose{ud\tau}}$ $\displaystyle=$
$\displaystyle\sum_{u|(D_{1/2}/d)}{\mu}(u){1\over 2^{m-n}}\sum_{1\leq x\leq
m-n\atop ud|x}{{m-n}\choose{x}}$ $\displaystyle=$
$\displaystyle\sum_{u|(D_{1/2}/d)}{\mu}(u)\,\big{(}{\mathbb{P}}\\{ud|B_{m-n}\\}-{1\over
2^{m-n}}\big{)}$ $\displaystyle=$
$\displaystyle\sum_{u|(D_{1/2}/d)}{\mu}(u){\mathbb{P}}\\{ud|B_{m-n}\\}-{{\delta}(D_{1/2}/d)\over
2^{m-n}}.$

Consequently,

$\displaystyle{1\over
2^{m-n}}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\sum_{k=1\atop(k,D_{1/2})=d}^{m-n}{{m-n}\choose{k}}$
$\displaystyle=$
$\displaystyle\sum_{d|D_{1/2}}2^{{\omega}(d)}d\Big{(}\sum_{u|(D_{1/2}/d)}{\mu}(u)\,\big{(}{\mathbb{P}}\\{ud|B_{m-n}\\}-{{\delta}(D_{1/2}/d)\over
2^{m-n}}\Big{)}$ $\displaystyle=$
$\displaystyle\sum_{d|D_{1/2}}2^{{\omega}(d)}d\Big{(}\sum_{u|(D_{1/2}/d)}{\mu}(u)\,{\mathbb{P}}\\{ud|B_{m-n}\\}\Big{)}-{1\over
2^{m-n}}.$

We observe that ${\delta}(D_{1/2}/d)=0$ as long as $d<D_{1/2}$, and if
$d=D_{1/2}$, then the corresponding summand produces the contribution
$2^{{\omega}(D_{1/2})}D_{1/2}{\mathbb{P}}\\{D_{1/2}|B_{m-n}\\}-{1\over
2^{m-n}}$ (recalling that ${\mu}(1)=1$), whence the last line. By reporting
this in (6.20) we get

(6.25) $\displaystyle{1\over
D2^{m-n}}\sum_{k=0}^{m-n}{{m-n}\choose{k}}\,\varrho_{k}(D)$ $\displaystyle=$
$\displaystyle{1\over
D2^{m-n}}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\sum_{k=1\atop(k,D_{1/2})=d}^{m-n}{{m-n}\choose{k}}+{1\over
2^{m-n}\sqrt{D}}$ (6.27) $\displaystyle=$ $\displaystyle{1\over
D}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\Big{(}\sum_{u|(D_{1/2}/d)}{\mu}(u)\,{\mathbb{P}}\\{ud|B_{m-n}\\}\Big{)}$
$\displaystyle+{1\over 2^{m-n}\sqrt{D}}-{1\over D2^{m-n}}.$

By inserting now this into (6.19), we finally get

(6.29) $\displaystyle{\mathbb{P}}\\{D|B_{n}B_{m}\\}$ $\displaystyle\leq$
$\displaystyle{1\over
D}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\Big{(}\sum_{u|(D_{1/2}/d)}{\mu}(u)\,{\mathbb{P}}\\{ud|B_{m-n}\\}\Big{)}$
$\displaystyle+{1\over 2^{m-n}\sqrt{D}}-{1\over
D2^{m-n}}+C_{\varepsilon}\left({D^{1+{\varepsilon}}\over n}\right)^{1/2}$
(6.31) $\displaystyle\leq$ $\displaystyle{1\over
D}\sum_{d|D_{1/2}}2^{{\omega}(d)}d\Big{(}\sum_{u|(D_{1/2}/d)}{\mu}(u)\,{\mathbb{P}}\\{ud|B_{m-n}\\}\Big{)}$
$\displaystyle+{1\over
2^{m-n}\sqrt{D}}+C_{\varepsilon}\left({D^{1+{\varepsilon}}\over
n}\right)^{1/2}.$

This achieves the proof of Theorem 6.8. ∎

##  7\. Divisibility and primality in the Rademacher random walk

The primality properties in that case are more studied than divisibility. The
necessary value distribution results of divisors are taken from [54], which
contains an application to the functional equation of the Zeta-Riemann
function. An extremal divisor case is thoroughly investigated in [55]. The
proof deeply relies on mixing properties of the system
$\big{\\{}\chi\\{d|R_{n}\\},\ 2\leq d\leq n,\ n\geq 1\big{\\}}$.

###  7.1. Divisibility.

Put,

(7.1) $\displaystyle{\qquad}{\qquad}\Theta_{1}({\delta},M)$ $\displaystyle=$
$\displaystyle 2\
\displaystyle{\sum_{\ell\in{\mathbb{Z}}}e^{-{2M\pi^{2}\ell^{2}\over{\delta}^{2}}},}$
(7.2) $\displaystyle\Theta_{2}({\delta},M)$ $\displaystyle=$ $\displaystyle 2\
\displaystyle{\sum_{\ell=0}^{\infty}\big{\\{}e^{-{M\pi^{2}(2\ell)^{2}/2{\delta}^{2}}}-e^{-{M\pi^{2}(2\ell+1)^{2}/2{\delta}^{2}}}\big{\\}}-1.}$

We note that

(7.3) $\Theta_{1}({\delta},M)=2\,{\delta}/\sqrt{{2M\pi}}+\mathcal{O}(1)$

when ${\delta}\to\infty$, uniformly in any interval of $M$. The Theorem below
provides precise estimates of ${\mathbb{P}}\big{\\{}{\delta}|R_{M}\big{\\}}$.

######  Theorem 7.1 ([53], Th. 2.1).

Let ${\alpha}>{\alpha}^{\prime}>3/2$. There exist constants $C$,
${\delta}_{0}$ and $M_{0}$, depending on ${\alpha},{\alpha}^{\prime}$ only,
such that for any $M\geq M_{0}$, $M\geq{\delta}\geq{\delta}_{0}$: — if
${\delta}$ and $M$ are even,

(7.4)
$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}{\delta}|R_{M}\big{\\}}-{2+4\cos^{M}{2\pi\over{\delta}}\over{\delta}}\Big{|}\leq
M^{-{\alpha}^{\prime}},$ $\displaystyle\qquad\hbox{if}\ \
{\delta}<2\pi\sqrt{M\over{2{\alpha}\log M}},$ (7.5)
$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}{\delta}|R_{M}\big{\\}}-{1\over{\delta}}\Theta_{1}({\delta},M)\Big{|}\leq
C{\log^{5/2}M\over M^{3/2}},$ $\displaystyle\qquad\hbox{if}\ {\delta}\geq
2\pi\sqrt{M\over{2{\alpha}\log M}}.$

— if ${\delta}$ and $M$ are odd,

(7.6)
$\displaystyle\Big{|}{\mathbb{P}}\\{{\delta}|R_{M}\\}-{1+2(\cos{2\pi\over{\delta}})^{M}-2(\cos{\pi\over{\delta}})^{M}\over{\delta}}\Big{|}\leq
M^{-{\alpha}^{\prime}},$ $\displaystyle\hbox{if}\ \
{\delta}<2\pi\sqrt{M\over{2{\alpha}\log M}},$ (7.7)
$\displaystyle\Big{|}{\mathbb{P}}\\{{\delta}|R_{M}\\}-{\Theta_{2}({\delta},M)\over{\delta}}\Big{|}\leq
C{\log^{5/2}M\over M^{3/2}},$ $\displaystyle\hbox{if}\ {\delta}\ \geq
2\pi\sqrt{M\over{2{\alpha}\log M}}.$

###  7.2. An extremal divisor case.

Put successively,

$N_{1}=1,\qquad N_{k}=\inf\\{\,N>N_{k-1}\,:\,N\ {\rm even\ and}\
\,N|R_{N^{2}}\,\\},\qquad(k>1).$

The fact that this random sequence is well defined, can be deduced from our
result below.

The following fine asymptotic result exhibits an exponential growth of the
sequence $(N_{k})_{k}$.

######  Theorem 7.2 (Weber [55]).

Put $s=2\sum_{j\in{\mathbb{Z}}}e^{-2\pi^{2}j^{2}}$. For any $\tau>7/8$,

$\ \log N_{k}={k\over
s}+{\mathcal{O}}\big{(}k^{\tau}\big{)}\qquad\qquad\hbox{\it almost surely.}$

The result extends to Bernoulli sequences ${\beta}=\\{{\beta}_{i},i\geq 1\\}$.
Write $B_{N}={\beta}_{1}+\ldots+{\beta}_{N}$, $N=1,2,\ldots$ Since
${\varepsilon}_{i}\buildrel{\mathcal{D}}\over{=}2{\beta}_{i}-1$, Theorem 7.2
gives the same estimate for the sequence

$M_{1}=1,\qquad M_{k}=\inf\\{\,M>M_{k-1}\ :\ M\ \textstyle{even\ and}\quad
M|\,2B_{M^{2}}\,\\},\qquad(k>1)$

The proof is intricate and long. We only give a sketch of the main steps.
First for $N$ even, one has the asymptotic estimate

(7.8)
$N{\mathbb{P}}\big{\\{}N|R_{N^{2}}\big{\\}}=s+{\mathcal{O}}\Big{(}{\log^{5/2}N\over
N^{2}}\Big{)}.$

Next it is necessary to have at disposal asymptotic estimates of the
correlation

${\mathbb{P}}\\{N|R_{N^{2}},M|R_{M^{2}}\\}-{\mathbb{P}}\\{N|R_{N^{2}}\\}{\mathbb{P}}\\{M|R_{M^{2}}\\}.$

This is a considerably more delicate task. The next statement is the crucial
step towards the proof of Theorem 7.2.

######  Lemma 7.3 ([55]).

There exists an absolute constant $C$, and for every ${\varepsilon}>0$, a
constant $C_{\varepsilon}$ depending on ${\varepsilon}$ only, such that for
any even positive integers $N\geq M$ large enough, a) if $\ M\leq N\leq
M+N/(\log N)^{1/2}$

$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}N|R_{N^{2}},M|R_{M^{2}}\big{\\}}-{\mathbb{P}}\big{\\{}N|R_{N^{2}}\big{\\}}{\mathbb{P}}\big{\\{}M|R_{M^{2}}\big{\\}}\Big{|}\leq
C\,{(\log N)^{1/2}\over N}{(\log M)^{1/2}\over M}.$

b) if $N>M+N/(\log N)^{1/2}$

$\displaystyle\Big{|}{\mathbb{P}}\big{\\{}N|R_{N^{2}},M|R_{M^{2}}\big{\\}}-$
$\displaystyle{\mathbb{P}}\big{\\{}N|R_{N^{2}}\big{\\}}{\mathbb{P}}\big{\\{}M|R_{M^{2}}\big{\\}}\Big{|}$
$\displaystyle\leq C_{\varepsilon}\,\Big{\\{}{(\log M)^{5/2}(\log
N)^{1/2}\over M^{2}N}+{1\over N^{2}}(\log
N)^{3/4\,\,+{\varepsilon}}\Big{\\}}.$

The next tool is Lemma 10 p. 45 in Sprindžuk [35], a typical criterion of
almost sure convergence, providing in addition an estimate of the remainder
term.

######  Lemma 7.4.

Let $\\{f_{l},l\geq 1\\}$ be a sequence of non negative random variables, and
let ${\varphi}=\\{{\varphi}_{l},l\geq 1\\}$, $m=\\{m_{l},l\geq 1\\}$ be two
sequences of non negative reals such that

(7.9) $0\leq{\varphi}_{l}\leq m_{l}\leq 1\qquad(l\geq 1).$

Write

$M_{n}=\sum_{1\leq l\leq n}m_{l}.$

Assume that $M_{n}\uparrow\infty$ and that the following condition is
satisfied

(7.10) ${\mathbb{E}\,}\ \big{|}\sum_{i\leq l\leq
j}(f_{l}-{\varphi}_{l})\big{|}^{2}\,\leq C\sum_{i\leq l\leq j}m_{l},\qquad
0\leq i\leq j<\infty.$

Then, for every $a>3/2$,

(7.11) $\sum_{1\leq l\leq n}f_{l}\ \buildrel a.s.\over{=}\sum_{1\leq l\leq
n}{\varphi}_{l}+{\mathcal{O}}\Bigl{(}M_{n}^{1/2}{\log}^{a}M_{n}\Big{)}.$

###  7.3. Primality.

######  Theorem 7.5 ([50]).

There exist two absolute constants $C_{1}$ and $C_{2}$ such that for any
integer $n\geq 3$,

${C_{1}\over\log n}\leq{\mathbb{P}}\\{R_{n}\ \hbox{is
prime}\\}\leq{C_{2}\over\log n}.$

In fact, for every ${\varepsilon}>0$,

${4\over\sqrt{2e\pi}\log n}-{C_{\varepsilon}\over
n^{1/2-{\varepsilon}}}\leq{\mathbb{P}}\\{R_{n}\ \hbox{is
prime}\\}\leq\sqrt{{2\over\pi}}\Big{(}\sum_{k=1}^{\infty}{2^{k}}e^{-2^{2k-1}}\Big{)}{1\over\log
n}+{C^{\prime}_{\varepsilon}\over n^{1/2-{\varepsilon}}},$

where the constants $C_{\varepsilon}$, $C_{\varepsilon}^{\prime}$ depend on
${\varepsilon}$ only.

The constants obtained are certainly not the best, and the limit
$\displaystyle{\lim_{n\to\infty}}(\log
n)\,{\mathbb{P}}\\{R_{n}\,\hbox{prime}\\}$ may exists.

###### Proof.

Put

$I_{k}(n)=[-2^{k}\sqrt{n},2^{k}\sqrt{n}],{\qquad}k=0,1,\ldots$

next

(7.12) $J_{k}(n)=\begin{cases}{\mathcal{P}}\cap I_{0}(n)&{\qquad}\hbox{if
$k=0$},\cr{\mathcal{P}}\cap\big{(}I_{k}(n)\backslash
I_{k-1}(n)\big{)}&{\qquad}\hbox{if $k\geq 1$},\end{cases}$

and let $k_{n}=\max\\{k:2^{k-1}\leq a\sqrt{2\log\log n}\\}$, where $a>0$ will
be chosen later on. Then

${\mathbb{P}}\\{R_{n}\ \hbox{
prime}\\}=\sum_{k=0}^{\infty}{\mathbb{P}}\\{R_{n}\in
J_{k}(n)\\}=\sum_{k=0}^{k_{n}}{\mathbb{P}}\\{R_{n}\in J_{k}(n)\\}+\rho_{n}.$

There exists a numerical constant $c$ ($c={4\over\sqrt{3\pi}}$ is suitable)
such that if $a>c\sqrt{2}$,

$\displaystyle{\mathbb{P}}\\{|R_{n}|>a\sqrt{2n\log\log n}\\}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\\{|{R_{n}\over\sqrt{n}}|>a\sqrt{2\log\log n}\\}$
$\displaystyle\leq$ $\displaystyle e^{-(2a^{2}/c^{2})\log\log
n}{\mathbb{E}\,}e^{{|R_{n}|^{2}/(c^{2}n)}}$ $\displaystyle\leq$
$\displaystyle{2\over(\log n)^{2a^{2}/c^{2}}}.$

Thus

$\rho_{n}\leq{\mathbb{P}}\\{|R_{n}|\geq a\sqrt{2n\log\log n}\\}\ll{1\over\log
n}.$

Besides,

${\mathbb{P}}\\{R_{n}\in J_{k}(n)\\}={\mathbb{P}}\\{R_{n}\in
J_{k}(n)\\}-{1\over\sqrt{2\pi n}}\sum_{p\in J_{k}(n)}e^{-{p^{2}\over
2n}}+{1\over\sqrt{2\pi n}}\sum_{p\in J_{k}(n)}e^{-{p^{2}\over 2n}}.$

By means of Theorem 7.1,

$\sum_{k=0}^{k_{n}}\Big{|}{\mathbb{P}}\\{R_{n}\in
J_{k}(n)\\}-{1\over\sqrt{2\pi n}}\sum_{p\in J_{k}(n)}e^{-{p^{2}\over
2n}}\Big{|}\leq{C_{\varepsilon}\over
n^{3/2-{\varepsilon}}}\sum_{k=0}^{k_{n}}\\#(J_{k}(n))\leq
C_{\varepsilon}n^{-1/2+{\varepsilon}}.$

The following estimates are classical: ([28], Th. 2 and Cor. 1, p. 69, and
[7], Lemma 5, p. 439)

$\displaystyle x/\log x\leq\pi(x)\leq x/(\log x-3/2),$ for any $x\geq 67$,
$\displaystyle\pi(2x)-\pi(x)\leq{x\over\log x},$
$\displaystyle{\qquad}\hbox{for any $x>1$}.$

Then

${4\over\sqrt{2e\pi}\log n}\leq{2\pi(\sqrt{n})\over\sqrt{2e\pi
n}}\leq{1\over\sqrt{2\pi n}}\sum_{p\in J_{0}(n)}e^{-{p^{2}\over
2n}}\leq{2\pi(\sqrt{n})\over\sqrt{2\pi n}}\leq{4\over(\log n-3)\sqrt{2\pi}}.$

And

$\displaystyle{1\over\sqrt{2\pi n}}\sum_{k=1}^{k_{n}}e^{-{p^{2}\over 2n}}\
\leq\ {2\over\sqrt{2\pi
n}}\sum_{k=1}^{k_{n}}{2^{k}\sqrt{n}\over\log(2^{k}\sqrt{n})}e^{-2^{2k-1}}\
\leq\
\sqrt{{2\over\pi}}\Big{(}\sum_{k=1}^{\infty}{2^{k}}e^{-2^{2k-1}}\Big{)}{1\over\log
n}.$

We deduce

${4\over\sqrt{2e\pi}\log n}\leq{1\over\sqrt{2\pi
n}}\sum_{k=0}^{k_{n}}e^{-{p^{2}\over
2n}}\leq\sqrt{{2\over\pi}}\Big{(}\sum_{k=1}^{\infty}{2^{k}}e^{-2^{2k-1}}\Big{)}{1\over\log
n}.$

From there, it follows immediately that

${4\over\sqrt{2e\pi}\log n}-{C_{\varepsilon}\over
n^{1/2-{\varepsilon}}}\leq{\mathbb{P}}\\{R_{n}\ \hbox{
prime}\\}\leq\sqrt{{2\over\pi}}\Big{(}\sum_{k=1}^{\infty}{2^{k}}e^{-2^{2k-1}}\Big{)}{1\over\log
n}+{C^{\prime}_{\varepsilon}\over n^{1/2-{\varepsilon}}}.$

Whence the claimed result. ∎

The following Theorem is complementing the above.

######  Theorem 7.6 ([50]).

Let $m>n$ be two odd positive integers. Then for some absolute constant $C$,
and every ${\varepsilon}>0$,

${\mathbb{P}}\\{R_{n}\ {\rm and}\ R_{m}\ \hbox{are
prime}\\}\leq{C\over\sqrt{m-n}\,\log
n}+C_{\varepsilon}n^{-1/2+{\varepsilon}}+{C\log\log^{+}(m-n)\over(\log
n)^{2}}.$

###### Proof.

Let $m>n$ be two odd positive integers. We have

(7.13) $\displaystyle{\mathbb{P}}\\{R_{n}\ {\rm and}\ R_{m}\hbox{ prime}\\}$
$\displaystyle=$ $\displaystyle{\mathbb{P}}\\{R_{n}\ {\rm and}\
R_{n}+(R_{m}-R_{n})\ \hbox{prime}\\}$ (7.14) $\displaystyle=$
$\displaystyle\sum_{|p|\leq n}{\mathbb{P}}\\{R_{n}=p\\}\Big{(}\sum_{|v|\leq
m-n\atop p+v\in{\mathcal{P}}}{\mathbb{P}}\\{R_{m-n}=v\\}\Big{)}$ (7.15)
$\displaystyle=$ $\displaystyle\sum_{|v|\leq m-n}\Big{(}\sum_{|p|\leq n\atop
p+v\in{\mathcal{P}}}{\mathbb{P}}\\{R_{n}=p\\}\Big{)}{\mathbb{P}}\\{R_{m-n}=v\\}.$

The summation term corresponding to $v=0$ equals to

(7.16) $\displaystyle\sum_{|p|\leq n\atop
p\in{\mathcal{P}}}{\mathbb{P}}\\{R_{n}=p\\}{\mathbb{P}}\\{R_{m-n}=0\\}$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\\{R_{n}\,\hbox{prime}\\}{\mathbb{P}}\\{R_{m-n}=0\\}$
(7.17) $\displaystyle\leq$
$\displaystyle{C\over\sqrt{m-n}}\,{\mathbb{P}}\\{R_{n}\,\hbox{prime}\\}\,\leq\,{C\over\sqrt{m-n}\,\log
n}$

since ${\mathbb{P}}\\{R_{m-n}=0\\}=2^{-(m-n)}{{m-n}\choose{{m-n\over
2}}}\sim{2\over\sqrt{2\pi(m-n)}}$. We next write for $|v|\leq m-n$,

$\sum_{|p|\leq n\atop
p+v\in{\mathcal{P}}}\Big{|}{\mathbb{P}}\\{R_{n}=p\\}-{1\over\sqrt{2\pi
n}}e^{-{p^{2}\over 2n}}\Big{|}\leq
C_{\varepsilon}n^{1-3/2+{\varepsilon}}=C_{\varepsilon}n^{-1/2+{\varepsilon}}.$

Further,

${1\over\sqrt{2\pi n}}\sum_{|p|\leq n\atop p+v\in{\mathcal{P}}}e^{-{p^{2}\over
2n}}={1\over\sqrt{2\pi n}}\sum_{k=0}^{\infty}\sum_{p\in J_{k}(n)\atop
p+v\in{\mathcal{P}}}e^{-{p^{2}\over 2n}},$

where $J_{k}(n)$ are defined in (7.12). Recall Siebert’s estimate [32]: let
$a\neq 0$, $b\neq 0$ be integers with $(a,b)=1$, $2|ab$. Then for $x>1$,

(7.18) $\sum_{p\leq x\atop ap+b\in{\mathcal{P}}}\leq 16{\omega}{x\over(\log
x)^{2}}\prod_{p|ab\atop p>2}\,\Big{(}{p-1\over
p-2}\Big{)},{\qquad}{\omega}=\prod_{p>2}\Big{(}1-\frac{1}{(p-1)^{2}}\Big{)}.$

Daboussi and Rivat’s observation [7], p. 440, that

$\frac{p-1}{p-2}=\Big{(}1-\frac{1}{p}\Big{)}^{-1}\Big{(}1-\frac{1}{(p-1)^{2}}\Big{)}^{-1}$

and when $h$ is even

$\prod_{p|h\atop p\geq 3}\Big{(}1-\frac{1}{p}\Big{)}=2\frac{{\varphi}(h)}{h},$

imply that for $x>1$ and any positive even number $h$,

(7.19) $\sum_{p\leq x\atop p+h\in{\mathcal{P}}}1\leq
8\prod_{p\atop(p,h)=1}\Big{(}1-\frac{1}{(p-1)^{2}}\Big{)}{x\over(\log
x)^{2}}{h\over{\varphi}(h)}\leq 8\,{x\over(\log x)^{2}}{h\over{\varphi}(h)}.$

In (7.13), the sums are indexed over pairs $(p,p+v)$ with $|p|\leq n$,
$|v|\leq m-n$. By symmetry, it suffices to restrict to the case $p>0$, $v<0$,
namely $(p,p-|v|)$. Consider three sub-cases: (a) $|v|<p$, (b) $|v|\geq 2p$,
(c) $p\leq|v|<2p$.

$\displaystyle{\rm(a)}$ $(p-|v|,p)$ with $1\leq p-|v|\leq n$, $|v|\leq m-n$.
$\displaystyle{\rm(b)}$ $(p,|v|-p)=(p,p+|v|-2p)$ with $1\leq p\leq n$,
${0\leq|v|-2p\leq m-n}.^{(*)}$ $\displaystyle{\rm(c)}$
$(|v|-p,p)=(|v|-p,|v|-p+2p-|v|)$ with $1\leq|v|-p\leq 2p-p=p\leq n$, $1\leq
2p-|v|\leq 2|v|-|v|=|v|\leq m-n$.

∗(The case $2p-|v|=0$ in (b) is treated in (7.16).) Thus the pairs $(p-|v|,p)$
are pairs $({\alpha},{\alpha}+h)$ of positive integers all satisfying
${\alpha}\leq n$, $h\leq m-n$. So that estimate (7.19) remains applicable to
this case, up to a multiplicative factor 4.

It follows that

$\\#\\{p\in J_{k}(n):p+v\in{\mathcal{P}}\\}\leq\\#\\{|p|\leq
2^{k}\sqrt{n}:p+v\in{\mathcal{P}}\\}\leq C{2^{k}\sqrt{n}\over(\log
2^{k}\sqrt{n})^{2}}{|v|\over{\varphi}(|v|)}.$

Hence,

${1\over\sqrt{2\pi n}}\sum_{k=0}^{\infty}\sum_{p\in J_{k}(n)\atop
p+v\in{\mathcal{P}}}e^{-{p^{2}\over 2n}}\leq{C\over(\log
n)^{2}}{|v|\over{\varphi}(|v|)}\sum_{k=0}^{\infty}2^{k}e^{-2^{2k-3}}\leq{C\over(\log
n)^{2}}{|v|\over{\varphi}(|v|)}.$

Consequently

$\sum_{|p|\leq n\atop p+v\in{\mathcal{P}}}{\mathbb{P}}\\{R_{n}=p\\}\leq
C_{\varepsilon}n^{-1/2+{\varepsilon}}+{C\over(\log
n)^{2}}{|v|\over{\varphi}(|v|)}.$

By reporting,

${\mathbb{P}}\\{R_{n}\ {\rm and}\ R_{m}\hbox{ prime}\\}=\sum_{|v|\leq
m-n}\Big{(}\sum_{|p|\leq n\atop
p+v\in{\mathcal{P}}}{\mathbb{P}}\\{R_{n}=p\\}\Big{)}{\mathbb{P}}\\{R_{m-n}=v\\}$
$\leq{C\over\sqrt{m-n}\,\log
n}+C_{\varepsilon}n^{-1/2+{\varepsilon}}+{C\over(\log n)^{2}}\sum_{0<|v|\leq
m-n}{|v|\over{\varphi}(|v|)}{\mathbb{P}}\\{R_{m-n}=v\\}.$
$\leq{C\over\sqrt{m-n}\,\log
n}+C_{\varepsilon}n^{-1/2+{\varepsilon}}+{C\over(\log n)^{2}}\
{\mathbb{E}\,}\,{|R_{m-n}|\over{\varphi}(|R_{m-n}|)}{\bf 1}_{\\{|R_{m-n}|\geq
1\\}}.$

We have obtained

$\displaystyle{\mathbb{P}}\\{R_{n}\ {\rm and}\ R_{m}\hbox{ prime}\\}$
$\displaystyle\leq$ $\displaystyle{C\over\sqrt{m-n}\,\log
n}+C_{\varepsilon}n^{-1/2+{\varepsilon}}$
$\displaystyle{\qquad}\quad+{C\over(\log n)^{2}}\
{\mathbb{E}\,}\,{|R_{m-n}|\over{\varphi}(|R_{m-n}|)}{\bf 1}_{\\{|R_{m-n}|\geq
1\\}}.$

We have the following estimates concerning ${\varphi}$ (Rosser and Schoenberg
[28], inequality 3.40 and 3.41), for $h\geq 3$

$\displaystyle\sum_{k=1}^{n}{k\over{\varphi}(k)}={\mathcal{O}}(n),$
$\displaystyle{|v|\over{\varphi}(|v|)}\leq
e^{\gamma}\log\log|v|+{2,50637\over\log\log|v|}\leq C\log\log|v|.$

We deduce

${\mathbb{P}}\\{R_{n}\ {\rm and}\ R_{m}\hbox{
prime}\\}\leq{C\over\sqrt{m-n}\,\log
n}+C_{\varepsilon}n^{-1/2+{\varepsilon}}+{C\log\log^{+}(m-n)\over(\log
n)^{2}}.$

∎

###  7.4. Primality mod($k$).

Theorem 7.5 can be extended to a larger class of random variables under
moderate integrability assumption (only the upper bound part is concerned).
Indeed, by using the Brun-Titchmarsh theorem and the local limit theorem, a
similar result is valid under a stronger form, the constraint made on $k$
below, is weak but the bound obtained, although sharp, should admit
improvments (maybe the $\log\log$ term can be dropped).

######  Theorem 7.7 ([50]).

Let $X$ be a symmetric random variable such that
${\mathbb{E}\,}X=0={\mathbb{E}\,}X^{3}$, ${\mathbb{E}\,}X^{2}=1$ and
${\mathbb{E}\,}|X|^{3+{\varepsilon}}<\infty$ for some ${\varepsilon}>0$. Let
$X_{i}$, $i\geq 1$ be independent copies of $X$ and for each positive integer
$n$, $S_{n}=X_{1}+\ldots+X_{n}$. Let $k$ be some positive integer and $\ell$
be an odd integer such that $(\ell,k)=1$ and $\sqrt{n\log\log n}/k\to\infty$.
Then for every $B>1$,

${\mathbb{P}}\Big{\\{}S_{n}\ \hbox{is prime},\,S_{n}\equiv\ell\ ({\rm
mod}\,k)\Big{\\}}={\mathcal{O}}_{B}\Big{\\{}{\sqrt{\log\log
n}\over\varphi(k)\log n}+{1\over(\log n)^{B}}\Big{\\}}.$

The proof uses the following local limit theorem due to Ibragimov, which
characterizes the speed of convergence in the i.i.d. case.

######  Proposition 7.8 ([24], p. 216).

Let $\\{X_{k},k\geq 1\\}$ be a sequence of centered i.i.d.
${\mathbb{Z}}$-valued random variables, with common distribution function $F$,
and unit variance. Put

$r_{n}=\sup_{k}\Big{|}\sqrt{n}{\mathbb{P}}\\{S_{n}=k\\}-{1\over\sqrt{2\pi}}e^{-{k^{2}\over
2n}}\Big{|}$

Then $r_{n}={\mathcal{O}}\big{(}n^{-(m+{\delta})/2}\big{)}$ for some integer
$m\geq 0$ and a real ${\delta}$, ${\delta}\in]0,1[$, if and only if

$\sup\big{\\{}h>0;\exists a\in{\mathbb{Z}}:{\mathbb{P}}\\{X_{1}\in
a+h{\mathbb{Z}}\\}=1\big{\\}}=1,$

and the two following conditions are realized:

(i) All moments of $X_{1}$ up to the order $m+2$ included exist and coincide
with those of the standard normal law.

(ii)

$\int_{|x|\geq
v}|x|^{m+2}F(dx)={\mathcal{O}}\big{(}v^{-{\delta}}\big{)}{\qquad}{\qquad}v\to\infty.$

###### Proof of Theorem 7.7.

As there exists ${\varepsilon}>0$ such that
${\mathbb{E}\,}|X|^{3+{\varepsilon}}<\infty$, $X$ satisfies the requirements
of Proposition 7.8 with $m=1$ and $0<{\delta}<1$,
${\delta}={\delta}({\varepsilon})$. Then

$\displaystyle\sup_{k}\big{|}\sqrt{n}{\mathbb{P}}\\{S_{n}=k\\}-{1\over\sqrt{2\pi}}e^{-{k^{2}\over
2n}}\big{|}={\mathcal{O}}\big{(}n^{-(1+{\delta})/2}\big{)},$

and

(7.20) $\displaystyle\big{|}\sum_{k\in
J}{\mathbb{P}}\\{S_{n}=k\\}-{1\over\sqrt{2\pi n}}\sum_{k\in J}e^{-{k^{2}\over
2n}}\big{|}\leq C{\\#\\{J\\}\over n^{1+({\delta}/2)}}.$

Besides, by means of a result of Robbins and Siegmund ([24], p. 314), if
${\alpha}>1$, $b>1$ are two arbitrary but fixed reals, there exists a constant
$C$ depending on ${\alpha}$, $b$ and $X$, an integer $n({\alpha})$ depending
on ${\alpha}$ only, such that for any $n\geq n({\alpha})$,

(7.21) $\displaystyle{\mathbb{P}}\Big{\\{}\exists m\geq
n:S_{m}>\sqrt{2{\alpha}(1+b)m\log\log m}\Big{\\}}\leq C(\log n)^{-b}(\log\log
n)^{-1/2}.$

As $X$ is symmetric, ${\mathbb{P}}\\{|S_{n}|>u\\}\leq
2{\mathbb{P}}\\{S_{n}>u\\}$; and thus it follows from (7.21) that

(7.22)
$\displaystyle{\mathbb{P}}\Big{\\{}|S_{n}|>\sqrt{2{\alpha}(1+b)n\log\log
n}\Big{\\}}\leq 2C(\log n)^{-b}(\log\log n)^{-1/2}.$

Let $k$, $\ell$ be coprime integers. Put

$J=\big{\\{}2\leq|p|\leq\sqrt{2{\alpha}(1+b)n\log\log n}:p\equiv\ell\ ({\rm
mod}\,k)\big{\\}}.$

Using (7.20) and (7.22) we have

(7.23) $\displaystyle\bigg{|}{\mathbb{P}}\Big{\\{}S_{n}\ \hbox{
prime},\,S_{n}\equiv\ell\ ({\rm mod}\,k)\Big{\\}}$
$\displaystyle-\sqrt{2\over\pi n}\sum_{j\in J}e^{-{j^{2}/2n}}\bigg{|}$ (7.24)
$\displaystyle\leq\ {C\\#\\{J\\}\over n^{1+({\delta}/2)}}+{2C\over(\log
n)^{b}(\log\log n)^{1/2}}.$

Whence

(7.25) $\displaystyle{\mathbb{P}}\Big{\\{}S_{n}\ \hbox{
prime},\,S_{n}\equiv\ell\ ({\rm mod}\,k)\Big{\\}}\leq\ {\\#(J)\over\sqrt{\pi
n}}+C^{\prime}(\log n)^{-b}(\log\log n)^{-1/2}.$

Using the notation $\pi(x;\ell,k):=\\#\big{\\{}p\leq x:p\equiv\ell\ ({\rm
mod}\,k)\big{\\}}$, we have

$\\#\big{\\{}2\leq p\leq\sqrt{2{\alpha}(1+b)n\log\log n}:p\equiv\ell\ ({\rm
mod}\,k)\big{\\}}=\pi(\sqrt{2{\alpha}(1+b)n\log\log n};\ell,k).$

By means of the Brun-Titchmarsh theorem (see for instance [37, p. 83]),

$\pi(x+y;\ell,k)-\pi(x;\ell,k)\leq(2+o(1)){y\over\varphi(k)\log(y/k)},$

as $y/k$ tends to infinity, where $\varphi$ is Euler’s totient function.

Letting $x=2$ and $y=\sqrt{2{\alpha}(1+b)n\log\log n}-2$, we have in
particular, as $\sqrt{n\log\log n}/k\to\infty$,

(7.26) $\displaystyle{\pi(\sqrt{2{\alpha}(1+b)n\log\log
n};\ell,k)\over\sqrt{n}}$ $\displaystyle\leq$
$\displaystyle{(2+o(1))\over\sqrt{n}}{\sqrt{2{\alpha}(1+b)n\log\log
n}\over\varphi(k)\log(\sqrt{2{\alpha}(1+b)n\log\log n}/k)}$ (7.27)
$\displaystyle\leq$ $\displaystyle C^{\prime\prime}{\sqrt{\log\log
n}\over\varphi(k)\log n}.$

By combining (7.26) with (7.25), we deduce that for all $n$ large enough, if
$\sqrt{n\log\log n}/k\to\infty$

${\mathbb{P}}\Big{\\{}S_{n}\ \hbox{ prime},\,S_{n}\equiv\ell\ ({\rm
mod}\,k)\Big{\\}}\leq C^{\prime\prime}{\sqrt{\log\log n}\over\varphi(k)\log
n}+C^{\prime}{1\over(\log n)^{b}(\log\log n)^{1/2}}.$

Consequently, for any $B>1$, there exists a constant $C(B)$, such that, as $n$
is large and $\sqrt{n\log\log n}/k\to\infty$

${\mathbb{P}}\Big{\\{}S_{n}\ \hbox{ prime},\,S_{n}\equiv\ell\ ({\rm
mod}\,k)\Big{\\}}\leq C(B)\Big{\\{}{\sqrt{\log\log n}\over\varphi(k)\log
n}+{1\over(\log n)^{B}}\Big{\\}}.$

∎

##  8\. Divisibility and primality in the Cramér random walk

Cramér’s probabilistic model basically consists with a sequence of independent
random variables $\xi_{i}$, defined for $i\geq 3$ by

(8.1) ${\mathbb{P}}\\{\xi_{i}=1\\}=\frac{1}{\log
i},{\qquad}\quad{\mathbb{P}}\\{\xi_{i}=0\\}=1-\frac{1}{\log i}.$

Let $m_{n}={\mathbb{E}\,}S_{n}=\sum_{j=3}^{n}\frac{1}{\log j}$, $B_{n}={\rm
Var}S_{n}=\sum_{j=3}^{n}\frac{1}{\log j}(1-\frac{1}{\log j})$. Cramér’s well-
known twin prime conjecture, which seems largely accepted, does not however
assert that there are any primes in the ‘primes’ of the model, which are the
instants of jump of the random walk $\\{S_{n},n\geq 1\\}$, recursively defined
by

(8.2) $P_{1}=\inf\\{n\geq
3:\xi_{n}=1\\},{\qquad}P_{\nu+1}=\inf\\{n>P_{\nu}:\xi_{n}=1\\}{\qquad}\quad\nu\geq
1.$

We refer to Granville [12], Pintz [24] and Montgomery and Soundararajan [23].
Our recent paper Weber [46] offers a probabilistic complementary study, in
particular of the ‘primes’ $P_{\nu}$ and of the primality properties of
$\\{S_{n},n\geq 1\\}$. Recall that the standard limit theorems are fulfilled,
and the invariance principle holds, derived from Sakhanenko’s. The law of the
iterated logarithm implies that

(8.3) $\\#\big{\\{}\nu\in\mathcal{C}:\nu\leq x\big{\\}}=\int_{2}^{x}\frac{{\rm
d}t}{\log t}+\mathcal{O}\big{(}\sqrt{x\log\log x}\big{)},$

with probability one. Cramér’s easier prediction on the order of magnitude of
the remainder in the ‘prime number theorem’, cannot be separated from the fact
that this one should also be sensitive to the subsequence on which it is
observed, as shown in [46]. Such a property is hardly conceivable and was
nowhere emphasized. In a work in progress, that study is transposed to other
random models for prime numbers.

###  8.1. Divisibility

The distribution of divisors of $S_{n}$ turns up to share similarities with
the one of Bernoulli sums. We prove the following result, which was only
stated in [46].

######  Theorem 8.1.

$\displaystyle{\mathbb{P}}\\{d|S_{n}\\}\,=\frac{1}{d}+\frac{1}{d}\sum_{1\leq
j\leq\frac{d}{\pi}(\log n)({{\alpha}\over 2n})^{1/2}}$ $\displaystyle e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}+\mathcal{O}\Big{(}\frac{d^{3}{\alpha}^{3}(\log
n)^{4}}{n^{3/2}}\Big{)}.$

Let ${\varphi}_{k}(t)$ be the characteristic function of $\xi_{k}$,
${\varphi}_{k}(t)={\mathbb{E}\,}e^{2i\pi\xi_{k}t}$. Let also

$\Phi_{n}(t)={\mathbb{E}\,}e^{2i\pi tS_{n}}=\prod_{k=1}^{n}{\varphi}_{k}(t),$

be the characteristic function of $S_{n}$. We prove the following estimate
with explicit constants.

######  Proposition 8.2.

We have $|\Phi_{n}(t)|\leq\exp\big{\\{}-2B_{n}\sin^{2}\pi t\big{\\}}$. Further

$\Phi_{n}(t)=e^{2i\pi tm_{n}-2B_{n}(\pi
t)^{2}+E_{n}(t)},{\qquad}\quad{\text{w}ith}\qquad|E_{n}(t)|\,\leq\,12\,m_{n}\,(\pi|t|)^{3}.$

In particular,

${\mathbb{E}\,}e^{iy\,\frac{S_{n}-m_{n}}{\sqrt{B_{n}}}}=e^{-\frac{y^{2}}{2}+E_{n}(y)},{\qquad}\quad{\text{a}nd}\qquad|E_{n}(y)|\,\leq
2\,\frac{\sqrt{\log n}\,|y|^{3}}{\sqrt{n}}.$

The proof crucially uses the Lemma below.

######  Lemma 8.3.

Let $m$ be a positive real and $p$ be a real such that $0<p<1$. Let ${\beta}$
be a random variable defined by ${\mathbb{P}}\\{{\beta}=0\\}=p$,
${\mathbb{P}}\\{{\beta}=m\\}=1-p=q$. Let ${\varphi}(t)={\mathbb{E}\,}e^{2i\pi
t{\beta}}$. Then we have the following estimates,

(i) For all real $t$, $|{\varphi}(t)|\leq\exp\big{\\{}-2pq\sin^{2}\pi
tm\big{\\}}$

(ii) If $q|\sin\pi tm|\leq 1/3$, then

$\displaystyle{\varphi}(t)$ $\displaystyle=$ $\displaystyle e^{q2i\pi
mt-2qp(\pi mt)^{2}+E},$

with $|E|\,\leq\,12q(\pi m|t|)^{3}$.

For sake of completeness we include the proof.

###### Proof.

(i) One verifies that $|{\varphi}(t)|^{2}=1-4pq\sin^{2}\pi mt.$ As moreover
$1-{\vartheta}\leq e^{-{\vartheta}}$ if ${\vartheta}\geq 0$, we obtain
$|{\varphi}(t)|^{2}\leq e^{-4pq\sin^{2}\pi mt}$.

(ii) Let $|u|\leq u_{0}<1$. From the series expansion of $\log(1+u)$, it
follows that

$\log(1+u)=u-\frac{u^{2}}{2}+R,{\qquad}\qquad|R|\leq|u|^{3}\,\sum_{j=0}^{\infty}\frac{|\theta|^{j}}{3+j}\leq\frac{|u|^{3}}{3(1-u_{0})}.$

Then $1+u=\exp\\{u-\frac{u^{2}}{2}+B\\}$, with $|B|\leq C_{0}\,|u|^{3}$ and
$C_{0}=\frac{1}{3(1-u_{0})}$.

Writing that ${\varphi}(t)=1+q\big{(}e^{2i\pi mt}-1\big{)}=1+u$, where
$|u|=2q|\sin\pi mt|\leq 2q\big{(}1\wedge\pi m|t|\big{)}$, we obtain

(8.4) ${\varphi}(t)=1+u=e^{q(e^{2i\pi
mt}-1)}\,e^{-\frac{u^{2}}{2}+B},{\qquad}\quad|B|\leq 8C_{0}\,q^{3}|\sin\pi
mt|^{3}.$

In order to estimate $u^{2}$, we let $A(t)=e^{2i\pi mt}-1-2i\pi mt+\frac{(2\pi
mt)^{2}}{2}$, and write $(e^{2i\pi mt}-1)^{2}$ under the form

$\displaystyle\ A(2t)-2A(t)-\big{\\{}-1-4i\pi mt+8(\pi
mt)^{2}\big{\\}}+2\big{\\{}-1-2i\pi mt+\frac{(2\pi mt)^{2}}{2}\big{\\}}+1$
$\displaystyle=A(2t)-2A(t)-(2\pi mt)^{2}.$

Then $(e^{2i\pi mt}-1)^{2}+(2\pi mt)^{2}=A(2t)-2A(t)$, and so
$\frac{u^{2}}{2}=-2q^{2}(\pi mt)^{2}+\frac{q^{2}}{2}(A(2t)-2A(t)).$

Let $u_{0}=\frac{2}{3}$ so that $C_{0}=1$. We assumed $q|\sin\pi tm|\leq 1/3$,
thus $|u|\leq 2/3$. We consequently get with (8.4),

(8.5) $\displaystyle{\varphi}(t)$ $\displaystyle=$ $\displaystyle
e^{q(e^{2i\pi mt}-1)-\frac{u^{2}}{2}+B}\,=\,e^{q(e^{2i\pi mt}-1)+2q^{2}(\pi
mt)^{2}-\frac{q^{2}}{2}(A(2t)-2A(t))+B}$ (8.6) $\displaystyle=$ $\displaystyle
e^{q2i\pi mt-2qp(\pi mt)^{2}+H+B},$

with $H=qA(t)-\frac{q^{2}}{2}(A(2t)-2A(t))$. By using the estimate (Lemma 4.14
in Kallenberg [17])

(8.7)
$\Big{|}e^{ix}-\sum_{k=0}^{n}\frac{(ix)^{k}}{k!}\Big{|}\,\leq\,\frac{2|x|^{n}}{n!}\wedge\frac{|x|^{n+1}}{(n+1)!},$

valid for any $x\in{\mathbb{R}}$ and $n\in{\mathbb{Z}}_{+}$, and letting
${\delta}(x)=x^{2}\big{(}1\wedge\frac{|x|}{6}\big{)}$, we get

(8.8) $\displaystyle|A(t)|$ $\displaystyle\leq$ $\displaystyle{\delta}(2\pi
m|t|).$

Using the rough bound ${\delta}(x)\leq\frac{|x|^{3}}{6}$, and
$|B|\leq\,8q^{3}\big{(}1\wedge\pi m|t|\big{)}^{3}$, we get

(8.9)
$|H|+|B|\,\leq\,2q|A(t)|+\frac{q^{2}}{2}|A(2t)|+|B|\,\leq\,\big{(}\frac{8}{3}q+\frac{4}{3}q^{2}+8q^{3}\big{)}(\pi
m|t|)^{3}\,\leq\,12q(\pi m|t|)^{3}.$

We conclude by inserting estimate (8.9) into (8.5). ∎

###### Proof of Proposition 8.2.

We apply Lemma 8.3. Here we have $m=1$, $q=\frac{1}{\log k}$. As
$|{\varphi}_{k}(t)|\leq\exp\big{\\{}-2(1-\frac{1}{\log k})(\frac{1}{\log
k})\sin^{2}\pi t\big{\\}}$, we get

$|\Phi_{n}(t)|\leq\exp\big{\\{}-2\sum_{k=3}^{n}(1-\frac{1}{\log
k})(\frac{1}{\log k})\sin^{2}\pi t\big{\\}}.$

Further condition $q|\sin\pi tm|\leq 1/3$ in Lemma 8.3 reduces for
${\varphi}_{k}(t)$ to $\frac{1}{\log k}|\sin\pi t|\leq 1/3$. Thus

(8.10) ${\varphi}_{k}(t)=e^{2i\pi(\frac{1}{\log k})t-2\pi^{2}(1-\frac{1}{\log
k})(\frac{1}{\log k})\,t^{2}+C_{k}(t)},$

where $|C_{k}(t)|\leq\,\frac{12(\pi|t|)^{3}}{\log k}$. Recalling that
$m_{n}=\sum_{j=3}^{n}\frac{1}{\log j}$, $B_{n}=\sum_{j=3}^{n}\frac{1}{\log
j}(1-\frac{1}{\log j})$, it follows that

(8.11) ${\mathbb{E}\,}e^{2i\pi tS_{n}}=\Phi_{n}(t)=e^{2i\pi
tm_{n}-2\pi^{2}B_{n}t^{2}+D_{n}(t)},$

and $|D_{n}(t)|\,\leq\,12\,m_{n}\,(\pi|t|)^{3}$. In particular,

(8.12)
${\mathbb{E}\,}e^{iy\,\frac{S_{n}-m_{n}}{\sqrt{B_{n}}}}=e^{-\frac{y^{2}}{2}+E_{n}(y)},$

with
$|E_{n}(y)|\,\leq\,\frac{3m_{n}}{2}\,(\frac{y}{\sqrt{B_{n}}})^{3}\,\leq\,2\,\frac{\sqrt{\log
n}|y|^{3}}{\sqrt{n}}$. This achieves the proof. ∎

###### Proof of Theorem 8.1.

We note that

(8.13) $\displaystyle{\mathbb{P}}\\{d|S_{n}\\}$ $\displaystyle=$
$\displaystyle{\mathbb{E}\,}\Big{(}\frac{1}{d}\sum_{j=0}^{d-1}e^{2i\pi
S_{n}\frac{j}{d}}\Big{)}\ =\
\frac{1}{d}+\frac{1}{d}\sum_{j=1}^{d-1}\Phi_{n}\big{(}\frac{j}{d}\big{)}$
(8.14) $\displaystyle=$
$\displaystyle\frac{1}{d}+\frac{1}{d}\sum_{j=1}^{d-1}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}.$

The elliptic Theta function

$\Theta(d,m_{n},B)=\sum_{\ell\in{\mathbb{Z}}}e^{im\pi{\ell\over
d}-{B\pi^{2}\ell^{2}\over 2d^{2}}},$

appears in the above estimate of ${\mathbb{P}}\\{d|S_{n}\\}$. Here $m=m_{n}$,
$B=B_{n}$ and we have $m_{n}\sim B_{n}\sim\frac{n}{\log n}$. Let
${\alpha}>{\alpha}^{\prime}>3/2$. Let

${\varphi}_{n}=(\log n)\big{(}{{\alpha}\over
2n}\big{)}^{1/2},\qquad\qquad\tau_{n}={\sin{\varphi}_{n}/2\over{\varphi}_{n}/2}.$

We assume $n$ sufficiently large, say $n\geq n_{0}$, for $\tau_{n}$ to be
greater than $({\alpha}^{\prime}/{\alpha})^{1/2}$. Consider two sectors

$A_{n}=]0,{\varphi}_{n}[,{\qquad}{\qquad}A^{\prime}_{n}=[{\varphi}_{n},{\pi\over
2}[.$

We write

$\displaystyle\sum_{j=1}^{d-1}$ $\displaystyle e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}$
$\displaystyle=\Big{(}\sum_{j\geq 1\,:\,{\pi j\over d}\in A_{n}}+\sum_{j\geq
1\,:\,{\pi j\over d}\in A^{\prime}_{n}}\Big{)}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}.$

Concerning the second sub-sum, the inequality ${\varphi}_{n}\leq{\pi j\over
d}<{\pi\over 2}$ implies that

$\displaystyle\sum_{j\geq 1\,:\,{\pi j\over d}\in
A^{\prime}_{n}}e^{-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}$ $\displaystyle\leq$
$\displaystyle\sum_{j\geq 1\,:\,{\pi j\over d}\in
A^{\prime}_{n}}e^{-2c\frac{n}{\log n}\,(\frac{\pi j}{d})^{2}}$
$\displaystyle\leq$ $\displaystyle\sum_{j\geq 1\,:\,{\pi j\over d}\in
A^{\prime}_{n}}e^{-c{\alpha}\,\log n}\leq dn^{-{\alpha}^{\prime}}.$

Therefore

$\displaystyle\Big{|}\sum_{j\geq 1:{\pi j\over d}\in A^{\prime}_{n}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}\Big{|}$
$\displaystyle\leq\sum_{j\geq 1:{\pi j\over d}\in
A^{\prime}_{n}}e^{-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}\big{(}1+\mathcal{O}(m_{n}\,d)\big{)}$
$\displaystyle\leq Cm_{n}d\sum_{j\geq 1:{\pi j\over d}\in
A^{\prime}_{n}}e^{-2c\frac{n}{\log n}\,(\frac{\pi j}{d})^{2}}$
$\displaystyle\leq Cm_{n}d\sum_{j\geq 1:{\pi j\over d}\in
A^{\prime}_{n}}e^{-c{\alpha}\,\log n}$ $\displaystyle\leq
C\big{(}\frac{n}{\log
n}\big{)}d^{2}n^{-{\alpha}^{\prime}}\,\leq\,Cd^{2}\,n^{1-{\alpha}^{\prime}}.$

Now, concerning the first sub-sum,

$\displaystyle\sum_{j\geq 1\,:\,{\pi j\over d}\in A_{n}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}$
$\displaystyle=$ $\displaystyle\sum_{1\leq j\leq\frac{d}{\pi}(\log
n)({{\alpha}\over 2n})^{1/2}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}$
$\displaystyle=$ $\displaystyle\sum_{1\leq j\leq\frac{d}{\pi}(\log
n)({{\alpha}\over 2n})^{1/2}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}\big{(}\,1+\mathcal{O}(m_{n}(\frac{j}{d})^{3})\,\big{)}.$

We have

$m_{n}\sum_{1\leq j\leq\frac{d}{\pi}(\log n)({{\alpha}\over
2n})^{1/2}}(\frac{j}{d})^{3}\,\leq\,C\,\frac{d^{2}{\alpha}^{2}(\log
n)^{3}}{n}.$

Thus

$\displaystyle\sum_{1\leq j\leq\frac{d}{\pi}(\log n)({{\alpha}\over
2n})^{1/2}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}\big{(}1+\mathcal{O}(m_{n}(\frac{j}{d})^{3})\big{)}$
$\displaystyle=$ $\displaystyle\sum_{1\leq j\leq\frac{d}{\pi}(\log
n)({{\alpha}\over 2n})^{1/2}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}$
$\displaystyle\quad+\mathcal{O}\Big{(}\sum_{1\leq j\leq\frac{d}{\pi}(\log
n)({{\alpha}\over
2n})^{1/2}}e^{-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}\Big{)}\Big{(}m_{n}\sum_{1\leq
j\leq\frac{d}{\pi}(\log n)({{\alpha}\over 2n})^{1/2}}(\frac{j}{d})^{3}\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{1\leq j\leq\frac{d}{\pi}(\log
n)({{\alpha}\over 2n})^{1/2}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}$
$\displaystyle\quad+\mathcal{O}\Big{(}\frac{d^{2}{\alpha}^{2}(\log
n)^{3}}{n}\sum_{1\leq j\leq\frac{d}{\pi}(\log n)({{\alpha}\over
2n})^{1/2}}e^{-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}\Big{)}$

Whence,

$\displaystyle\sum_{j\geq 1\,:\,{\pi j\over d}\in A_{n}}$ $\displaystyle
e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}+\mathcal{O}(m_{n}(\frac{j}{d})^{3})}$
$\displaystyle=\sum_{1\leq j\leq\frac{d}{\pi}(\log n)({{\alpha}\over
2n})^{1/2}}e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}+\mathcal{O}\Big{(}\frac{d^{3}{\alpha}^{3}(\log
n)^{4}}{n^{3/2}}\Big{)}.$

Combining both estimates gives

$\displaystyle{\mathbb{P}}\\{d|S_{n}\\}\,=\,\frac{1}{d}+\frac{1}{d}\sum_{1\leq
j\leq\frac{d}{\pi}(\log n)({{\alpha}\over 2n})^{1/2}}$ $\displaystyle e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}+\mathcal{O}(d^{2}n^{-{\alpha}^{\prime}})$
$\displaystyle{\qquad}+\mathcal{O}\Big{(}\frac{d^{3}{\alpha}^{3}(\log
n)^{4}}{n^{3/2}}\Big{)}$ $\displaystyle\,=\frac{1}{d}+\frac{1}{d}\sum_{1\leq
j\leq\frac{d}{\pi}(\log n)({{\alpha}\over 2n})^{1/2}}$ $\displaystyle e^{2i\pi
m_{n}(\frac{j}{d})-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}+\mathcal{O}\Big{(}\frac{d^{3}{\alpha}^{3}(\log
n)^{4}}{n^{3/2}}\Big{)}.$

This achieves the proof. ∎

Now as $\sum_{j\geq d/2}e^{-A\frac{j^{2}}{2d^{2}}}\leq e^{-cA}$, $c$ an
absolute constant, for all $d\geq 2$ and $A\geq 2$, we have

$\displaystyle\sum_{j>\frac{d}{\pi}(\log n)({{\alpha}\over
2n})^{1/2}}e^{-2\pi^{2}B_{n}\,(\frac{j}{d})^{2}}$
$\displaystyle\leq\sum_{j>\frac{d}{\pi}(\log n)({{\alpha}\over
2n})^{1/2}}e^{-A(\frac{n}{\log n})(\frac{j}{d})^{2}}$ $\displaystyle\leq
e^{-A^{\prime}(\frac{n}{\log n})(\frac{1}{d})^{2}(d(\log
n))^{2}({{\alpha}\over 2n}))}$ $\displaystyle\leq
e^{-A^{\prime\prime}{\alpha}\log n}=n^{-A^{\prime\prime}{\alpha}}.$

We therefore also have

######  Corollary 8.4.

$\displaystyle\Big{|}{\mathbb{P}}\\{d|S_{n}\\}-\frac{\Theta(d,m_{n},B_{n})}{d}\Big{|}\leq
C\ \frac{d^{3}{\alpha}^{3}(\log n)^{4}}{n^{3/2}}.$

We end the paper with recent results related to primality in the Cramér model.

###  8.2. Quasiprime and prime property.

We obtained in [46] -without assuming RH- a sharp estimate of
${\mathbb{P}}\\{S_{n}\ \text{prime}\,\\}$, for almost all $n$, namely for all
$n$, $n\to\infty$ through a set $\mathcal{S}$ of natural density $1$.

######  Theorem 8.5.

(i) For any constant $b>1/2$,

(8.15) ${\mathbb{P}}\\{S_{n}\ \text{prime}\,\\}\,=\,\frac{1}{\sqrt{2\pi
B_{n}}}\,\int_{m_{n}-\sqrt{2bB_{n}\log n}}^{m_{n}+\sqrt{2bB_{n}\log
n}}e^{-\frac{(t-m_{n})^{2}}{2B_{n}}}\,{\rm
d}\pi(t)+\mathcal{O}\Big{(}\frac{(\log n)^{3/2}}{\sqrt{n}}\Big{)},$

as $n\to\infty$, where $\pi(.)$ is the prime counting function. (ii) There
exists a set of integers $\mathcal{S}$ of density 1, such that

(8.16) ${\mathbb{P}}\\{S_{n}\ \text{prime}\,\\}\,=\,\frac{(1+o(1))}{\sqrt{2\pi
B_{n}}}\int_{m_{n}-\sqrt{2bB_{n}\log n}}^{m_{n}+\sqrt{2bB_{n}\log
n}}\,e^{-\frac{(t-m_{n})^{2}}{2B_{n}}}\,{\rm d}\pi(t),$

as $n\to\infty$, $n\in\mathcal{S}$. Further,

(8.17) $\liminf_{\mathcal{S}\ni n\to\infty}\ (\log n){\mathbb{P}}\\{S_{n}\
\hbox{prime}\\}\geq\frac{1}{\sqrt{2\pi e}\,}.$

The proof allows one (Remark 8.6) to treat other cases, so we included it.

###### Proof of Theorem 8.5..

(i) By Lemma 7.1 p. 240 in [24], for $0\leq x\leq B_{n}$

$\displaystyle{\mathbb{P}}\\{|S_{n}-m_{n}|\geq x\\}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\\{S_{n}-m_{n}\geq
x\\}+{\mathbb{P}}\\{-(S_{n}-m_{n})\geq x\\}$ $\displaystyle\leq$
$\displaystyle
2\,\exp\Big{\\{}-\frac{x^{2}}{2B_{n}}\Big{(}1-\frac{x}{2B_{n}}\Big{)}\Big{\\}},$

noticing that $\\{-\xi_{j}\\}_{j}$ also satisfies the conditions of
Kolmogorov’s Theorem. Let $b>b^{\prime}>1/2$. Then for all sufficiently large
$n$, since $\log B_{n}\sim\log n$,

(8.18) ${\mathbb{P}}\\{|S_{n}-m_{n}|\geq\sqrt{2bB_{n}\log n}\\}\leq
2\,n^{-b^{\prime}}.$

We have

$\displaystyle\Big{|}{\mathbb{P}}\\{S_{n}\in\mathcal{P}\\}$
$\displaystyle-{\mathbb{P}}\\{S_{n}\in\mathcal{P}\cap[m_{n}-\sqrt{2bB_{n}\log
n},m_{n}+\sqrt{2bB_{n}\log n}]\\}\Big{|}$
$\displaystyle\leq{\mathbb{P}}\\{|S_{n}-m_{n}|\geq\sqrt{2bB_{n}\log n}\\}$
$\displaystyle\leq n^{-b^{\prime}}.$

Further,

$\displaystyle\Big{|}{\mathbb{P}}\\{S_{n}\in\mathcal{P}\cap[m_{n}-\sqrt{2bB_{n}\log
n},m_{n}+\sqrt{2bB_{n}\log n}]\\}$
$\displaystyle-\sum_{{\kappa}\in\mathcal{P}\cap[m_{n}-\sqrt{2bB_{n}\log
n},m_{n}+\sqrt{2bB_{n}\log
n}]}\frac{e^{-\frac{({\kappa}-m_{n})^{2}}{2B_{n}}}}{\sqrt{2\pi B_{n}}}\Big{|}$
$\displaystyle\leq$
$\displaystyle\sum_{{\kappa}\in\mathcal{P}\cap[m_{n}-\sqrt{2bB_{n}\log
n},m_{n}+\sqrt{2bB_{n}\log
n}]}\Big{|}{\mathbb{P}}\\{S_{n}=\kappa\\}-\frac{e^{-\frac{({\kappa}-m_{n})^{2}}{2B_{n}}}}{\sqrt{2\pi
B_{n}}}\Big{|}$ $\displaystyle\leq$ $\displaystyle
C\,\\#\big{\\{}\mathcal{P}\cap[m_{n}-\sqrt{2bB_{n}\log
n},m_{n}+\sqrt{2bB_{n}\log n}]\big{\\}}\cdot\frac{(\log n)^{3/2}}{n}$
$\displaystyle\leq$ $\displaystyle C\,\sqrt{b}\ \frac{(\log
n)^{3/2}}{\sqrt{n}}.$

Therefore

(8.19)
$\Big{|}{\mathbb{P}}\\{S_{n}\in\mathcal{P}\\}-\sum_{{\kappa}\in\mathcal{P}\cap[m_{n}-\sqrt{2bB_{n}\log
n},m_{n}+\sqrt{2bB_{n}\log
n}]}\frac{e^{-\frac{({\kappa}-m_{n})^{2}}{2B_{n}}}}{\sqrt{2\pi
B_{n}}}\Big{|}\,\leq\,C\,\sqrt{b}\ \frac{(\log n)^{3/2}}{\sqrt{n}}.$

By expressing the inner sum as a Riemann-Stieltjes integral [1, p. 77], we get

(8.20)
${\mathbb{P}}\\{S_{n}\in\mathcal{P}\\}\,=\,\int_{m_{n}-\sqrt{2bB_{n}\log
n}}^{m_{n}+\sqrt{2bB_{n}\log
n}}\,\frac{e^{-\frac{(t-m_{n})^{2}}{2B_{n}}}}{\sqrt{2\pi B_{n}}}\,{\rm
d}\pi(t)+\mathcal{O}\Big{(}\frac{(\log n)^{3/2}}{\sqrt{n}}\Big{)}.$

(ii) We note that

(8.21)
$\displaystyle\int_{m_{n}-\sqrt{2bB_{n}}}^{m_{n}+\sqrt{2bB_{n}}}\,\frac{e^{-\frac{(t-m_{n})^{2}}{2B_{n}}}}{\sqrt{2\pi
B_{n}}}{\rm d}\pi(t)$ $\displaystyle\geq$ $\displaystyle L\
\frac{\pi(m_{n}+\sqrt{2bB_{n}})-\pi(m_{n}-\sqrt{2bB_{n}})}{\sqrt{B_{n}}},$

with $L=\frac{e^{-b}}{\sqrt{2\pi}}$. We use Theorem 4 in Selberg [31]. Let
$\Phi(x)$ be positive and increasing and such that $\frac{\Phi(x)}{x}$
decreasing for $x>0$. Further assume that

(8.22)
$\displaystyle{\rm(a)}\quad\lim_{x\to\infty}\frac{\Phi(x)}{x}=0{\qquad}{\qquad}{\rm(b)}\quad\liminf_{x\to\infty}\frac{\log\Phi(x)}{\log
x}>\frac{19}{77}.$

Then there exists a set $\mathcal{S}$ of positive reals of density one such
that

(8.23) $\lim_{\mathcal{S}\ni
x\to\infty}\frac{\pi(x+\Phi(x))-\pi(x)}{({\Phi(x)}/{\log x})}=1.$

Let $\Phi(x)=\sqrt{2bx}$. Then the requirements in (8.22) are fulfilled, and
so (8.23) holds true. Now let $C$ be some possibly large but fixed positive
number, as well as some positive real ${\delta}<1/2$. By (8.23), the set of
$x>0$, call it $\mathcal{S}_{\delta}$, such that

(8.24) $\pi(x+\Phi(x))-\pi(x)\,\geq\,(1-{\delta})\,\frac{\Phi(x)}{\log x}.$

has density 1. Note that
$\mathcal{S}_{{\delta}^{\prime}}\subseteq\mathcal{S}_{{\delta}^{\prime\prime}}$
if ${\delta}^{\prime}\leq{\delta}^{\prime\prime}$. Pick
$x\in\mathcal{S}_{\delta}$ and let ${\Delta}(x)=\pi(x+\Phi(x))-\pi(x)$. Note
that if $|y-x|\leq C$, $\big{|}\Phi(y)-\Phi(x)\big{|}=o(1)$ for $x$ large.
Thus for every $y\in[x-C,x+C]$, $\big{|}{\Delta}(y)-{\Delta}(x)\big{|}\,\leq
C^{\prime}$, and so

${\Delta}(y)\,\geq\,(1-{\delta})\,\frac{\Phi(x)}{\log x}-C^{\prime}.$

the constant $C^{\prime}$ depending on $C$ only. As
$\big{|}\frac{\Phi(x)}{\log x}-\frac{\Phi(y)}{\log
y}\big{|}\leq\frac{C}{2\sqrt{x}\log x}$, we have

${\Delta}(y)\,\geq\,(1-{\delta})\,\frac{\Phi(y)}{\log
y}-C^{\prime}-\frac{C}{2\sqrt{x}\log x}.$

Thus every $y\in[x-C,x+C]$ also satisfies

(8.25) ${\Delta}(y)\,\geq\,(1-2{\delta})\,\frac{\Phi(y)}{\log y},$

if $x$ is large enough.

Let $\nu=\nu(x)$ be the unique integer such that $m_{\nu-1}<x\leq m_{\nu}$. As
$m_{\nu}-m_{\nu-1}=o(1)$, $\nu\to\infty$, it follows that
$m_{\nu}\in[x-C,x+C]$ provided that $x$ is large enough, in which case we have
by (8.25),

(8.26)
$\frac{\pi(m_{\nu}+\Phi(m_{\nu}))-\pi(m_{\nu})}{\Phi(m_{\nu})}\geq\frac{1-2{\delta}}{\log
m_{\nu}}.$

Let $X\geq 1$ be a large positive integer and ${\varepsilon}$ a small positive
real. The number $N(X)$ of intervals $]{\mu}-1,{\mu}]$, ${\mu}\leq X$ such
that $\mathcal{S}_{\delta}\cap]{\mu}-1,{\mu}]\neq\emptyset$ verifies
$N(X)/X\sim 1$, $X\to\infty$, since $\mathcal{S}_{\delta}$ has density 1.

Given such an ${\mu}\leq X$, pick
$x\in\mathcal{S}_{\delta}\cap]{\mu}-1,{\mu}]$. We know (recalling that
$m_{\nu}-m_{\nu-1}=o(1)$, $\nu\to\infty$) that some $m_{\nu}$, $\nu=\nu(x)$
belongs to $]{\mu}-1-{\varepsilon},{\mu}+{\varepsilon}]$, and that (8.26) is
satisfied. The union of these intervals
$[{\mu}-1-{\varepsilon},{\mu}+{\varepsilon}]$ is contained in
$[1-{\varepsilon},X+{\varepsilon}]$. It follows that the number of $\nu$ such
that (8.26) is satisfied, forms a set of density 1.

We now use an induction argument in order to replace $2{\delta}$ in (8.26) by
a quantity ${\varepsilon}(\nu)$ which tends to 0 as $\nu$ tends to infinity
along some other set of density 1, which we shall build explicitly. Let
$\mathcal{T}_{n}$ be the set of $\nu$’s of density 1, corresponding to
${\delta}=\frac{1}{n}$, $n\geq 3$. Let $X_{3}$ be large enough so that
$\\#\\{\mathcal{T}_{3}\cap[1,X]\\}\geq X(1-1/3)$ for all $X\geq X_{3}$. Next
let $X_{4}>X_{3}$ be sufficiently large so that
$\\#\\{\mathcal{T}_{4}\cap[X_{3},X]\\}\geq X(1-1/4)$ for all $X\geq X_{4}$.
Like this we manufacture an increasing sequence $X_{j}$, verifying for all
$j\geq 3$,

$\\#\\{\mathcal{T}_{j}\cap[X_{j-1},X]\\}\geq X(1-1/j),{\qquad}{\qquad}{\rm
for\ all}\ X\geq X_{j}.$

The resulting set

$\mathcal{T}=\bigcup_{j=3}^{\infty}\mathcal{T}_{j}\cap[X_{j-1},X_{j}]$

has density 1 and further we have the inclusions

$\mathcal{T}\cap[X_{l-1},\infty)=\bigcup_{j=l}^{\infty}\mathcal{T}_{j}\cap[X_{j-1},X_{j}]\subset\mathcal{T}_{l}\cap\bigcup_{j=l}^{\infty}[X_{j-1},\infty)=\mathcal{T}_{l}\cap[X_{l-1},\infty),{\qquad}\quad
l\geq 4,$

as the sets $\mathcal{T}_{j}$ are decreasing with $j$ by definition.

We finally have by (8.21),

(8.27)
$\frac{\pi(m_{\nu}+\Phi(m_{\nu}))-\pi(m_{\nu})}{\Phi(m_{\nu})}\geq\frac{1-{\varepsilon}(\nu)}{\log
m_{\nu}},$

along $\mathcal{T}$, for some sequence of reals ${\varepsilon}(\nu)\downarrow
0$ as $\nu\to\infty$.

Therefore

(8.28)
$\displaystyle\int_{m_{\nu}-\sqrt{2bB_{\nu}}}^{m_{\nu}+\sqrt{2bB_{\nu}}}\,\frac{e^{-\frac{(t-m_{\nu})^{2}}{2B_{\nu}}}}{\sqrt{2\pi
B_{\nu}}}{\rm d}\pi(t)$ $\displaystyle\geq$ $\displaystyle L\
\frac{\pi(m_{\nu}+\sqrt{2bB_{\nu}})-\pi(m_{\nu}-\sqrt{2bB_{\nu}})}{\sqrt{B_{\nu}}}$
(8.29) $\displaystyle\geq$ $\displaystyle L\,\frac{1-{\varepsilon}(\nu)}{\log
m_{\nu}},$

for all $\nu\in\mathcal{T}$, recalling that $L=\frac{e^{-b}}{\sqrt{2\pi}}$.

Also

(8.30) $\liminf_{\mathcal{T}\ni\nu\to\infty}(\log\nu){\mathbb{P}}\\{S_{\nu}\
\hbox{prime}\\}\geq\frac{1}{\sqrt{2\pi e}\,}.$

It further follows from (8.20) that

(8.31) ${\mathbb{P}}\\{S_{\nu}\
\hbox{prime}\\}\,=\,\big{(}1+o(1)\big{)}\int_{m_{\nu}-\sqrt{2bB_{\nu}\log\nu}}^{m_{\nu}+\sqrt{2bB_{\nu}\log\nu}}\,\frac{e^{-\frac{(t-m_{\nu})^{2}}{2B_{\nu}}}}{\sqrt{2\pi
B_{\nu}}}\,{\rm d}\pi(t),$

all $\nu\in\mathcal{T}$. This completes the proof of Theorem 8.5. ∎

######  Remark 8.6.

The interested reader will have observed that the property
$m_{\nu}-m_{\nu-1}=o(1)$ is not fully used, in fact it suffices that
$m_{\nu}-m_{\nu-1}=\mathcal{O}(1)$, selecting at the beginning of the proof
$C$ sufficiently large. Thus the proof of Theorem 8.5 also adapt to the
Bernoulli case. In particular there exists a set of integers $\mathcal{U}$ of
density 1 such that

(8.32) $\liminf_{\mathcal{U}\ni\nu\to\infty}(\log\nu){\mathbb{P}}\\{B_{\nu}\
\hbox{prime}\\}>0.$

Let $\Pi_{z}=\prod_{p\leq z}p$. According to Pintz [25], an integer $m$ is
$z$-quasiprime, if $(m,\Pi_{z})=1$. Let
$S^{\prime}_{n}=\sum_{j=8}^{n}\xi_{j}$, $n\geq 8$. Note that the introduction
of $S^{\prime}_{n}$ in place of $S_{n}$ is not affecting Cramér’s conjecture.
The probability that $S^{\prime}_{n}$ be $z$-quasiprime is for all $n$ large
enough is studied in [46], Theorem 2.6. The proof is based on a randomization
argument.

######  Theorem 8.7.

We have for any $0<\eta<1$, and all $n$ large enough and
$\zeta_{0}\leq\zeta\leq\exp\big{\\{}\frac{c\log n}{\log\log n}\big{\\}}$,

$\displaystyle{\mathbb{P}}\big{\\{}S^{\prime}_{n}\hbox{\
$\zeta$-quasiprime}\big{\\}}\,\geq\,(1-\eta)\frac{e^{-\gamma}}{\log\zeta}.$

where $\gamma$ is Euler’s constant and $c$ is a positive constant.

###  8.3. Primality of ${P_{n}}$.

We also showed in [46] that when the ‘primes’ $P_{\nu}$ are observed along
moderately growing subsequences, then with probability 1, they ultimately
avoid any given infinite set of primes satisfying a reasonable tail’s
condition. We also test which infinite sequences of primes are ultimately
avoided by the ‘primes’ $P_{\nu}$, with probability 1.

######  Theorem 8.8.

Let $\mathcal{K}$ be an increasing sequence of naturals such that the series
$\sum_{k\in\mathcal{K}}k^{-{\beta}}$ converges for some
${\beta}\in]0,\frac{1}{2}[$. Let $\mathfrak{P}$ be an increasing sequence of
primes such that for some $b>1$,

$\sup_{k\in\mathcal{K}}\frac{\\#\\{\mathfrak{P}\cap[k,bk]\\}}{k^{\frac{1}{2}-{\beta}}}<\infty.$

Let also $\\{{\Delta}_{k},k\geq 1\\}$ be the instants of jump of the Bernoulli
sequence $\\{B_{k},k\geq 1\\}$. Then

$\displaystyle{\mathbb{P}}\big{\\{}{\Delta}_{k}\notin\mathfrak{P},\quad
k\in\mathcal{K}\ \hbox{ultimately}\big{\\}}=1.$

Further,

$\displaystyle{\mathbb{P}}\big{\\{}P_{\nu}\notin\mathfrak{P},\quad\nu\in\mathcal{K}\
\hbox{ultimately}\big{\\}}=1.$

Moreover (case ${\beta}=1/2$), let $\mathfrak{P}$ be such that
$\sum_{p\in\mathfrak{P},\,p>y}p^{-1/2}=\mathcal{O}\big{(}y^{-1/2}\big{)}$, and
$\mathcal{K}$ be such that $\sum_{k\in\mathcal{K}}k^{-1/2}<\infty$. Then

$\displaystyle{\mathbb{P}}\big{\\{}P_{\nu}\notin\mathfrak{P},\quad\nu\in\mathcal{K}\
\hbox{ultimately}\big{\\}}=1.$

##  Appendix A Proof of Theorem 6.6.

The following lemma is classical.

######  Lemma A.1.

Let $f\in{\mathbb{Z}}(X)$ and put $\varrho_{f}(d)=\\#\big{\\{}0\leq
y<d:d|f(y)\big{\\}}$. Then $\varrho_{f}$ is a multiplicative function.

The proof is long and technical because of many sub-cases entering into
consideration, which is natural when studying this kind of question. First
consider the case $k>0$, which is the main case. Recall that

$\displaystyle\varrho_{k}(D)=\\#\big{\\{}1\leq y\leq D:\
D|y^{2}+ky\big{\\}},{\qquad}\quad k=0,1,\ldots$

The function $\varrho_{k}(D)$ being multiplicative, it suffices to compute
$\varrho_{k}(p^{r})$. Observe to begin that

$\varrho_{k}(p^{r})=2,\quad r=1,2,\ldots{\qquad}\quad\hbox{if $p\not|k$}.$

Indeed, if $(y,p)=1$, then $p^{r}|y+k$ and there is only one solution given by
$y=\tilde{k}$ or $y=p^{r}-\tilde{k}$ where $\tilde{k}$ is the residue class of
$k$ modulo $p^{r}$. If $y=p^{s}Y$, $(Y,p)=1$, $1\leq s<r$, then
$p^{r}|y(y+k)\Leftrightarrow p^{r-s}|(p^{s}Y+k)$. And so $p|k$, which was
excluded. There is thus no solution of this kind. Finally, it remains one
extra solution $y=p^{r}$. Thus $\varrho_{k}(p^{r})=2$. We now assume that
$p|k$. We can range the solutions $y$ of the equation $p^{r}|y(y+k)$ in
disjoint classes of type $y=p^{s}Y$, with $(Y,p)=1$. When $r=1,2$ or $3$,
there is a direct simple computation.

Case $r=1$. We have $\varrho_{k}(p)=\\#\big{\\{}1\leq y\leq
p:\,p|y(y+k)\big{\\}}$. Since $p|k$, it follows that $p|y(y+k)\Leftrightarrow
p|y^{2}$. As $y\leq p$, the prime divisors of $y$ are less or equal to $p$ and
so are the prime divisors of $y^{2}$. There is thus only one solution: $y=p$.
Whence $\varrho_{k}(p)=1$.

Case $r=2$. We have $\varrho_{k}(p^{2})=\\#\big{\\{}1\leq y\leq
p^{2}:\,p^{2}|y(y+k)\big{\\}}$. As $p\|k$, If $(y,p)=1$, then
$p^{2}|y(y+k)\Leftrightarrow p^{2}|y+k$ and so $p|y$, which is impossible.
There is no solution of this type. If $y=pY$, with $(Y,p)=1$, then
$p^{2}|y(y+k)\Leftrightarrow p|(pY+k)$, which is satisfied. The number of
solutions is $\\#\\{Y\leq p:(Y,p)=1\\}=p-1$. The case $y=p^{2}Y$, with
$(Y,p)=1$ coincides with $y=p^{2}$. Therefore, $\varrho_{k}(p^{2})=p-1+1=p$.

Case $r=3$. We have $\varrho_{k}(p^{3})=\\#\big{\\{}1\leq y\leq p^{3}:\
p^{3}|y(y+k)\big{\\}}.$ If $(y,p)=1$, then $p^{3}|y(y+k)\Leftrightarrow
p^{3}|y+k$ and so $p|y$, which is impossible. There is no solution of this
type. If $y=pY$, with $(Y,p)=1$, then $p^{3}|y(y+k)\Leftrightarrow
p^{2}|(pY+k)$. If $v_{p}(k)\geq 2$, this implies that $p|Y$, which is
impossible, and so there is no solution of this type in that case. If
$v_{p}(k)=1$, write $k=pK$, we get $p|Y+K$. The number of solutions is
$\\#\\{Y\leq p^{2}:Y\equiv-K\,{\rm mod}(p)\\}=p$. If $y=p^{2}Y$, with
$(Y,p)=1$, then $p^{3}|y(y+k)\Leftrightarrow p|(p^{2}Y+k)$, which is always
realized. The number of solutions is $\\#\\{Y\leq p:(Y,p)=1\\}=p-1$. The extra
case is $y=p^{3}$. Therefore

(A.1) $\varrho_{k}(p^{3})=\begin{cases}2p\quad&{\rm if}\ \quad v_{p}(k)=1\cr
p\quad&{\rm if}\ \quad v_{p}(k)\geq 2.\end{cases}$

An additional sub-case thus appears. Summarizing

(A.2) $\varrho_{k}(p^{r})=\begin{cases}1\ &{\rm if}\ r=1,\cr p\ &{\rm if}\
r=2,\cr 2p\quad&{\rm if}\ r=3,\ v_{p}(k)=1.\cr p\ &{\rm if}\ r=3,\
v_{p}(k)\geq 2.\end{cases}$

Case $r\geq 4$. Put $r^{\prime}=\lfloor{r\over 2}\rfloor$. Then
$r^{\prime}\geq 2$. We have $\varrho_{k}(p^{r})=\\#\big{\\{}1\leq y\leq
p^{r}:\ p^{r}|y(y+k)\big{\\}}.$ If $(y,p)=1$, then
$p^{r}|y(y+k)\Leftrightarrow p^{r}|y+k$ and so $p|y$, which is excluded and
there is no solution.

Apart from the trivial solution $y=p^{r}$, the other possible solutions are of
type $y=p^{s}Y$, $(Y,p)=1$, $1\leq s<r$; and we shall distinguish three cases:

(i) $r^{\prime}<s<r$, (ii) $s=r^{\prime}$, (iii) $1\leq s<r^{\prime}$.

(i) Since $r^{\prime}<s<r$, then $r/2\leq s$, and so $1\leq r-s\leq s$.
Further $p^{r}|y(y+k)$ means $p^{r-s}|Y(p^{s}Y+k)$ or $p^{r-s}|p^{s}Y+k$,
which is possible if and only if $p^{r-s}|k$, namely $r-s\leq v_{p}(k)$. Thus

$\max(r^{\prime}+1,r-v_{p}(k))\leq s<r.$

We have $Y\leq p^{r-s}$, $(Y,p^{r-s})=1$. Their number is $\phi(p^{r-s})$
where $\phi$ is Euler’s function, and since $\phi(p^{r-s})=p^{r-s}(1-{1\over
p})$, the corresponding number of solutions is

$\displaystyle\sum_{\max(r^{\prime}+1,r-v_{p}(k))\leq s\leq
r-1}p^{r-s}(1-{1\over p})$ $\displaystyle=$ $\displaystyle(1-{1\over
p})\sum_{1\leq v\leq(r-r^{\prime}-1)\wedge v_{p}(k)}p^{v}$ $\displaystyle=$
$\displaystyle p\,{p^{(\lfloor{r-1\over 2}\rfloor)\wedge v_{p}(k)}-1\over
p-1}(1-{1\over p})$ $\displaystyle=$ $\displaystyle p^{\lfloor{r-1\over
2}\rfloor\wedge v_{p}(k)}-1.$

(ii) We consider solutions of type $y=p^{r^{\prime}}Y$, $(Y,p)=1$.

— If $r$ is odd, $r=2r^{\prime}+1$, then
$p^{2r^{\prime}+1}|p^{r^{\prime}}Y(p^{r^{\prime}}Y+k)$ means
$p^{r^{\prime}+1}|(p^{r^{\prime}}Y+k)$. So $p^{r^{\prime}}|k$ and thereby
$v_{p}(k)\geq r^{\prime}$. If $v_{p}(k)<r^{\prime}$, there is no solution. If
$v_{p}(k)>r^{\prime}$, it implies that $p|Y$ which is impossible and there is
again no solution. The remainding case $v_{p}(k)=r^{\prime}$ is the only one
providing solutions. Write $k=p^{r^{\prime}}K$, $(K,p)=1$, then $p|Y+K$. Since
$(K,p)=1$, the solutions are the numbers $Y$ such that $1\leq Y\leq
p^{r^{\prime}+1}$ and $Y\equiv-K\,{\rm mod}(p)$. Let $1\leq\kappa<p$ be such
that $K\equiv\kappa\,{\rm mod}(p)$. The number of solutions is

(A.3) $\\#\big{\\{}Y\leq p^{r^{\prime}+1}:Y\equiv-\kappa\ {\rm
mod}(p)\big{\\}}=\\#\big{\\{}-\kappa+jp:1\leq j\leq
p^{r^{\prime}}\big{\\}}=p^{r^{\prime}}.$

— If $r$ is even, $r=2r^{\prime}$, then
$p^{2r^{\prime}}|p^{r^{\prime}}Y(p^{r^{\prime}}Y+k)$ reduces to
$p^{r^{\prime}}|(p^{r^{\prime}}Y+k)$, so $p^{r^{\prime}}|k$. If
$v_{p}(k)<r^{\prime}$, there is no solution. If $v_{p}(k)\geq r^{\prime}$,
write $k=p^{v_{p}(k)}K$, $(K,p)=1$, this is always realized and the number of
solutions is

$\\#\big{\\{}Y\leq
p^{r^{\prime}}:(Y,p)=1\big{\\}}=\phi(p^{r^{\prime}})=p^{r^{\prime}}(1-{1\over
p}).$

(iii) We consider the last type of solutions: $y=p^{s}Y$, $(Y,p)=1$, $1\leq
s<r^{\prime}$. Notice first, since $s<r^{\prime}$ that $s<r/2$, and so
$r-s>r/2>s$. As $p^{r}|y(y+k)$ means $p^{r-s}|Yp^{s}+k$, we deduce that
$p^{s}|k$, namely $s\leq v_{p}(k)$. If $v_{p}(k)<s$, there is no solution. If
$v_{p}(k)>s$, then $p|Y$ which is impossible.

If $s=v_{p}(k)$, which requires $v_{p}(k)<r^{\prime}$, write
$k=p^{v_{p}(k)}K$, $(K,p)=1$. Then we get the equation $p^{r-2v_{p}(k)}|Y+K$;
so $Y\equiv-K\,{\rm mod}(p^{r-2v_{p}(k)})$. Let $1\leq\kappa<p^{r-2v_{p}(k)}$
be such that $K\equiv\kappa\,{\rm mod}(p^{r-2v_{p}(k)})$. The number of
solutions is

$\displaystyle\\#\big{\\{}Y\leq p^{r-v_{p}(k)}:Y$ $\displaystyle\equiv$
$\displaystyle-{\kappa}\ {\rm mod}(p^{r-2v_{p}(k)})\big{\\}}$ $\displaystyle=$
$\displaystyle\\#\big{\\{}-\kappa+jp^{r-2v_{p}(k)}:1\leq j\leq
p^{v_{p}(k)}\big{\\}}$ $\displaystyle=$ $\displaystyle p^{v_{p}(k)}.$

Summarizing the case $r\geq 4$, if $r$ is odd, $r=2r^{\prime}+1$

(A.4) $\varrho_{k}(p^{r})=\begin{cases}2p^{v_{p}(k)}&\quad\hbox{\rm if $1\leq
v_{p}(k)\leq r^{\prime}$},\cr p^{r^{\prime}}&\quad\hbox{\rm if
$v_{p}(k)>r^{\prime}$}.\end{cases}$

And if $r$ is even, $r=2r^{\prime}$

(A.5) $\varrho_{k}(p^{r})=\begin{cases}2p^{v_{p}(k)}&\quad\hbox{\rm if $1\leq
v_{p}(k)<r^{\prime}$},\cr p^{r^{\prime}}&\quad\hbox{\rm if $v_{p}(k)\geq
r^{\prime}$}.\end{cases}$

This remains true if $r=1,2,3$. Observe that ($v_{p}(k)<r^{\prime}$, $r$ even)
or ($v_{p}(k)\leq r^{\prime}$, $r$ odd) are equivalent to $v_{p}(k)<{r\over
2}$.

Therefore, for all $r\geq 2$

(A.6) $\varrho_{k}(p^{r})=\begin{cases}2&\quad{\rm if}\ p\not|k,\cr
2p^{v_{p}(k)}&\quad\hbox{\rm if}\ 1\leq v_{p}(k)<{r\over 2},\cr
p^{\lfloor{r\over 2}\rfloor}\ &\quad\hbox{\rm if}\ v_{p}(k)\geq{r\over
2}.\end{cases}$

Consequently

(A.7)
$\varrho_{k}(D)=\prod_{p|D}\varrho_{k}(p^{v_{p}(D)})=\prod_{v_{p}(k)<{v_{p}(D)/2}}(2p^{v_{p}(k)})\cdot\prod_{v_{p}(k)\geq{v_{p}(D)/2}}p^{\lfloor{v_{p}(D)\over
2}\rfloor}.$

Recall that

$D_{1/2}\,=\,\prod_{p|D}p^{\lfloor{v_{p}(D)\over 2}\rfloor}.$

We consider again several cases: — If $p$ is such that $v_{p}(D)=1$, then it
produces in the writing of $\varrho_{k}(D)$ only a factor 1, since
$v_{p}(k)<1/2$, so $v_{p}(k)=0$ and $\lfloor{v_{p}(D)\over 2}\rfloor=0$. — Now
let $p$ be such that $v_{p}(D)\geq 2$, and compare $v_{p}(D)/2$ with
$\lfloor{v_{p}(D)\over 2}\rfloor$. If $v_{p}(D)$ is even, both quantities are
equal. If $v_{p}(D)$ is odd, $v_{p}(D)=2z+1$, then $v_{p}(D)/2=z+1/2$,
$\lfloor{v_{p}(D)\over 2}\rfloor=z$. Thus in the latter case:

a) If $v_{p}(k)<{v_{p}(D)/2}$, namely $v_{p}(k)\leq z$, we get the factor
$2p^{v_{p}(k)}=2p^{\min(v_{p}(k),z)}=2p^{v_{p}((k,D_{1/2}))}$. If
$v_{p}(k)\geq{v_{p}(D)/2}$, namely $v_{p}(k)>z$, we have the factor
$p^{z}=p^{\min(v_{p}(k),z)}=p^{v_{p}((k,D_{1/2}))}$.

b) In the case $v_{p}(D)$ is even, if $v_{p}(k)<{v_{p}(D)/2}$, namely
$v_{p}(k)<z$, we have the factor
$2p^{v_{p}(k)}=2p^{\min(v_{p}(k),z)}=2p^{v_{p}((k,D_{1/2}))}$. If
$v_{p}(k)\geq{v_{p}(D)/2}=z$, we have the factor
$p^{z}=p^{\min(v_{p}(k),z)}=p^{v_{p}((k,D_{1/2}))}$.

Therefore the contribution of a prime $p$ such that $v_{p}(D)\geq 2$, is
either $2p^{v_{p}((k,D_{1/2}))}$ if $p$ is part of the first product, or
$p^{v_{p}((k,D_{1/2}))}$ if $p$ is part of the second.

A prime number $p$ is part of the first product, if and only if the inequation
$1\leq v_{p}(k)<v_{p}(D)/2$ is fulfilled. We therefore get the condensed form,

(A.8) $\displaystyle\varrho_{k}(D)=\prod_{p|D}\varrho_{k}(p^{v_{p}(D)})$
$\displaystyle=$
$\displaystyle\prod_{v_{p}(k)<{v_{p}(D)/2}}(2p^{v_{p}(k)})\cdot\prod_{v_{p}(k)\geq{v_{p}(D)/2}}p^{\lfloor{v_{p}(D)\over
2}\rfloor}$ (A.9) $\displaystyle=$ $\displaystyle 2^{\\#\\{p\,:\,1\leq
v_{p}(k)<v_{p}(D)/2\\}}\,\prod_{p}p^{\min(v_{p}(k),v_{p}(D)/2)}$ (A.10)
$\displaystyle=$ $\displaystyle 2^{\\#\\{p\,:\,1\leq
v_{p}(k)<v_{p}(D)/2\\}}\,(k,D_{1/2}).$

Finally, consider the case $k=0$, namely $\varrho_{0}(p^{r})=\\#\big{\\{}1\leq
y\leq p^{r}:\ p^{r}|y^{2}\big{\\}}$. Notice that
$\varrho_{0}(p)=\\#\big{\\{}1\leq y\leq p:\ p|y\big{\\}}=1$. Let $r>1$, and
write $y=p^{s}Y$, $(Y,p)=1$ and $1\leq s\leq r$. If $s=r$, there is the
trivial unique solution $y=p^{r}$. If $1\leq s<r$, $p^{r}|y^{2}\Rightarrow
2s\geq r$, in which case, the number of solutions is

$\\#\big{\\{}Y\leq p^{r-s}:(Y,p)=1\big{\\}}=\phi(p^{r-s})=p^{r-s}(1-{1\over
p}).$

Consequently $\varrho_{0}(p^{r})=1+\sum_{r/2\leq s<r}p^{r-s}(1-{1\over p})$ .
If $r$ is even, $r=2r^{\prime}$

$\varrho_{0}(p^{r})=1+\sum_{{\sigma}=1}^{r^{\prime}}p^{{\sigma}}(1-{1\over
p})=1+p\sum_{u=0}^{r^{\prime}-1}p^{u}(1-{1\over
p})=1+p\Big{(}{p^{r^{\prime}}-1\over p-1}\Big{)}({p-1\over
p})=p^{r^{\prime}},$

whereas if $r$ is odd, $r=2r^{\prime}+1$,
$\varrho_{0}(p^{r})=1+\sum_{{\sigma}=1}^{r^{\prime}}p^{{\sigma}}(1-{1\over
p})=p^{r^{\prime}}$. Thus

$\varrho_{0}(p^{r})=p^{\lfloor{r\over 2}\rfloor}.$

It follows that

$\varrho_{0}(D)=\prod_{p|D}p^{\lfloor{v_{p}(D)\over 2}\rfloor}\,=\,D_{1/2}.$

The proof is now complete.

Acknowledgments I thank Sanying Shi for exchanges around divisibility in
Bernoulli random walk.

## References

  * [1] T. M. Apostol, _Introduction to analytic number theory_. Springer-Verlag, New York-Heidelberg, (1976), Undergraduate Texts in Mathematics.
  * [2] T. M. Apostol, _Modular Functions and Dirichlet series in number theory_ , Second Edition. Springer-Verlag, New York-Heidelberg, (1990), Graduate Texts in Mathematics.
  * [3] R. Bellman, _A brief introduction to Theta functions_ , (1961), Holt, Rinehart and Winston, New-York.
  * [4] P. Billingsley, _Convergence of probability measures_ , (1968) John Wiley & Sons, Inc., New York-London-Sydney.
  * [5] G. S. Call and D. J. Velleman, Pascal’s matrices, _Amer. Math. Monthly_ 100, (1993) 372–376.
  * [6] H. Cramér, (1936) On the order of magnitude of the difference between consecutive primes, _Acta Arithmetica_ 2, 23-46.
  * [7] H. Daboussi and J. Rivat, (2000) Explicit upper bounds for exponential sums over primes, _Mathematics of computation_ 70, Number 233, 431–447.
  * [8] P. Diaconis and Ch. Stein, Some tauberian theorems related to coin tossing, _Ann. Prob._ , 6 No3 (1978) 483-490.
  * [9] P. Erdös and S. K. Zaremba, (1972) The arithmetical function $\sum_{d|n}\frac{\log d}{d}$, _Demonstratio Math._ 6, Part. 2, 575–579.
  * [10] W. Feller, (1968) _An Introduction to Probability Theory and its Applications_ , 1, 3rd ed. Wiley, New York.
  * [11] J. L. Fernandez and P. Fernandez, Divisibilities properties of random samples of integers, RACSAM (2021), 115: 26.
  * [12] A. Granville, Harald Cramér and the Distribution of Prime Numbers, _Scand. Actuarial J._ No. 1, (1995) 12–28.
  * [13] G.H. Hardy _Divergent series_ , (1963), Oxford at the Clarendon Press.
  * [14] G.H. Hardy, An inequality for Hausdorff means, _J. London Math. Soc._ 18 (1943), 46–50.
  * [15] D. R. Heath-Brown, The number of primes in a short interval, _J. reine angew. Math._ 389 (1988), 22–63.
  * [16] W.B. Jurkat, Ein funktionentheoretischer Beweis für $\mathcal{O}$-Taubersätze bei den Verfahren non Borel und Euler-Knopp, _Arch. Math._ 7 (1956), 278–283.
  * [17] O. Kallenberg, _Foundations of modern probability theory_ , (1997) Springer Verlag New-York.
  * [18] W. J. Leahey, and J. E. Nymann, On the probability that an integer chosen according to the binomial distribution be $k$-free, _The Rocky Mountain J. of Math._ 7, No 4 (1977) 769–774.
  * [19] P. J. McCarthy, Introduction to Arithmetical Functions, (Universitext), (1986), Springer-Verlag New-York Inc.
  * [20] D. MacDonald, A local limit theorem for large deviations of sums of independent, non-identically distributed random variables, _Annals of Prob._ 7 (1979) no. 3, 526–531.
  * [21] T. T. Moh, On a general Tauberian theorem, _Proc. Amer. Math. Soc._ 36, No 1 (1972) 167–172.
  * [22] H. L. Montgomery, R. C. Vaughan (2007) _Multiplicative Number Theory I. Classical Theory_ , Cambridge studies in advanced math, Cambridge University Press,
  * [23] H. L. Montgomery, K. Soundararajan, Primes in Short Intervals _Commun. Math. Phys._ 252, 589–617, (2004).
  * [24] V. V. Petrov, _Sums of Independent Random Variables_ , Ergebnisse der Math. und ihre Grenzgebiete 82, (1975) Springer.
  * [25] J. Pintz, Cramér vs. Cramér, On Cramér’s probabilistic model for primes, _Funct. Approx. Comment. Math._ 37, part 2, (2007) 361–376.
  * [26] A. G. Postnikov, _Introduction to analytic number theory_ , AMS Translation of mathematical monographs 68. (First publ. in Russian in 1971.) Amer. Math. Soc., 1988.
  * [27] A. Rényi, _Foundations of probability_ , (1970) Holden-Day series in probability and statistics.
  * [28] J. B. Rosser, L. Schoenfeld, (1962) Approximate formulas for some functions of prime numbers, _Illinois J. Math._ 6(1), 64–94.
  * [29] Y. A. Rozanov, On a local limit theorem for lattice distributions, _Theor. Prob. Appl._ , 2 (1957), no. 2, 260–265.
  * [30] A. Sárkőzy A., (1978) On difference sets of sequence of integers, _Acta Math. Acad. Sci. Hungar._ 31 (1-2),
  * [31] A. Selberg, On the normal density of primes in small intervals, and the difference between consecutive primes. _Arch. Math. Naturvid._ , 47 (1943), 87–105.
  * [32] H. Siebert, (1976) Montgomery’s weighted sieve for dimension two, _Monatsh. Math._ 82, 327–336.
  * [33] S. Shi and M. Weber, (2021) On Jordan double sums and related summatory functions, Preprint.
  * [34] S. Shi and M. Weber, (2022) Value distribution of squarefree divisors of Bernoulli sums, Preprint.
  * [35] V. G. Sprindžuk, (1979) _Metric theory of Diophantine approximations_ , Translated from the Russian and edited by Richard A. Silverman. With a foreword by Donald J. Newman. Scripta Series in Mathematics. V. H. Winston & Sons, Washington, D.C.; AHalsted Press Book, John Wiley & Sons, New York-Toronto, Ont.-London. xiii+156 pp.
  * [36] Szewczak, Z. and Weber M., _Classical and Almost Sure Local Limit Theorems_ , arXiv:2208.02700v1, (2022), 103 p. (in revision).
  * [37] G. Tenenbaum, _Introduction à la théorie analytique et probabiliste des nombres_ , (2008), Coll. Échelles Ed. Belin Paris.
  * [38] L. Tóth, A survey on Gcd-Sums functions, _Journal of Integer Sequences_ , Vol. 13 (2010), Article 10.8.1.
  * [39] A. Walfisz, _Weylsche Exponentialsummen in der neueren Zahlentherie._ , Mathematische Forschungsberichte, XV, V E B Deutscher Verlag der Wissenschaften (1963), Berlin.
  * [40] M. Weber, Correlation Properties of Divisors in the Bernoulli random walk, (2023).
  * [41] M. Weber, On infinite Möbius inversion, _Publ. Math. Debrecen_ Ref. no.: 9260, (2023), 1–12.
  * [42] M. Weber, On Farey sequence and quadratic Farey sums, _Research in Number Theory_ , 8, Article number 14, (2022) (25 p.).
  * [43] M. Weber An extension of a result of Erdös-Zaremba, _Glasgow Math. J._ , 63 (1), (2021), 193–222.
  * [44] M. Weber, On Rozanov’s theorem and strenghtened asymptotic uniform distribution, arXiv:2209.12228v1 (2022).
  * [45] M. Weber, A uniform semi-local limit theorem along sets of multiples for sums of i.i.d. random variables, arXiv:2209.12223v1, (2022), (in revision).
  * [46] M. Weber, (2021) Critical probabilistic characteristics of the Cramér model for primes and arithmetical properties, arXiv:2105.11020v1, (20p.).
  * [47] M. Weber, (2013) Instants of small amplitude of the Brownian motion and application to the Kubilius model, _Periodica Math. Hung._ 67 (1), 95–113.
  * [48] M. Weber, _Dynamical Systems and Processes_ , (2009) European Mathematical Society Publishing House, IRMA Lectures in Mathematics and Theoretical Physics 14 xiii+761p.
  * [49] M. Weber, (2008) Sampling the integers with a complete random walk (27 p.), _Unpublished_.
  * [50] M. Weber, (2008) Sur la probabilité ${\mathbb{P}}\\{S_{n}\,\hbox{est premier}\\}$ (15 p.), _Unpublished_.
  * [51] M. Weber, Small divisors of Bernoulli sums, _Indag. Math._ 18 No2 (2007), 281–293.
  * [52] M. Weber, (2007) Divisors of Bernoulli sums, Results der Math. 51, 141-179.
  * [53] M. Weber (2006) On the order of magnitude of the divisor function, _Acta Math. Sinica_ 22, No2, 377-382.
  * [54] M. Weber, (2005) Divisors, spin sums and the functional equation of the Zeta-Riemann function, _Periodica Math. Hungar._ 51 (1) 119-131.
  * [55] M. Weber, (2004) An arithmetical property of Rademacher sums, _Indag. Math._(_ N.S._)__ 15, 133–150.