Limit theorems for the least common multiple of a random set of integers
Gerold Alsmeyer Zakhar Kabluchko Alexander Marynych
math.PR math.NT 60F05 (Primary) 11N37, 60F15 (secondary)



Limit theorems for the LCM of a random set of integers]Limit theorems for the least common multiple of a random set of integers


Inst. Math. Stochastics, Department of Mathematics and Computer Science, University of Münster, Orléans-Ring 10, D-48149, Münster, Germany
gerolda@uni-muenster.de


Inst. Math. Stochastics, Department of Mathematics and Computer Science, University of Münster, Orléans-Ring 10, D-48149, Münster, Germany
zakhar.kabluchko@uni-muenster.de


Faculty of Computer Science and Cybernetics, Taras Shevchenko National University of Kyiv, 01601 Kyiv, Ukraine
marynych@unicyb.kiev.ua
GA and ZK were partially supported by the Deutsche Forschungsgemeinschaft (SFB 878), AM was partially supported by the Alexander von Humboldt Foundation.

[2010]Primary: 60F05;  secondary 11N37, 60F15. Keywords: random set of integers, least common multiple, law of large numbers, central limit theorem, functional limit theorem, Gaussian process, von Mangoldt function, Chebyshev functions


Let L_n be the least common multiple of a random set of integers obtained from {1,…,n} by retaining each element with probability θ∈ (0,1) independently of the others. We prove that the process (log L_⌊ nt⌋)_t∈ [0,1], after centering and normalization, converges weakly to a certain Gaussian process that is not Brownian motion. Further results include a strong law of large numbers for log L_n as well as Poisson limit theorems in regimes when θ depends on n in an appropriate way.


[
    Alexander Marynych
    December 30, 2023
======================





§ INTRODUCTION AND MAIN RESULTS


For n∈, let [n] denote the set {1,2,…,n}. Fixing a number 0<θ<1, remove each element in [n] with probability 1-θ, independently of all other elements in the set. Denote by A_n the random subset of remaining elements and by L_n:=(A_n) their least common multiple. In a recent article, Cilleruelo et al. <cit.> proved the following weak law of large numbers: As n→∞,

    log L_n/n  θlog(1/θ)/1-θ,

where  means convergence in probability. The result remains valid in the limiting case θ=1 when defining the right-hand side of (<ref>) as 1 as well, thus

    lim_n→∞log([n])/n = 1.

This is in fact a well-known consequence of the prime number theorem.

On the other hand, the derivation of results beyond (<ref>), like a strong law of large numbers or a central limit theorem for log L_n, seem to be open problems to our best knowledge. The purpose of this article is to not only provide limit theorems of this kind for both fixed θ and when θ varies with n, but also prove a functional limit theorem for the stochastic process

    t ↦ L_⌊ nt⌋,   t∈[0,1]

as n→∞. This latter result will actually be presented first and then yield a central limit theorem for log L_n as an immediate consequence (Corollary <ref>).



 §.§ A functional central limit theorem

In order to state the main result, we define the function

    g(z) := ∑_k≥ 1z^k(1-z^k)/k(k+1)

for |z|<1. It can be provided in closed form which is done in Remark <ref> below.


As n→∞, the following weak convergence holds true in the Skorokhod space D[0,1] of càdlàg functions endowed with the J_1-topology:

    (log L_⌊ nt⌋-log L_⌊ nt⌋/√(nlog n))_t∈ [0,1] J_1⟹ (G(t))_t∈[0,1],

where (G(t))_t∈[0,1] is a centered Gaussian process with covariance function

    [G(t)G(s)]= ∑_k≥ 1(t/k∧s/k) p_k - ∑_k,l≥ 1(t/k∧s/l)p_kp_l

for 0≤ s,t≤ 1, where p_k:=θ(1-θ)^k-1 for k∈. In particular,

    Var[G(t)]=g(1-θ)t.

The process (G(t))_t∈[0,1] a.s. has continuous paths.


A distributional property as well as a probabilistic representation of the limit process (G(t))_t∈[0,1] are given in the subsequent proposition.


(a) Let 𝒢_θ be a random variable with geometric distribution on , viz.

    {𝒢_θ=k} = p_k = θ(1-θ)^k-1,   k∈,

and B = (B(t))_t∈ [0,1] an independent standard Brownian motion. Then

    (G(t)+ [B(t/𝒢_θ)|B] )_t∈[0,1] d= (B(t 𝒢_θ^-1))_t∈[0,1],

where [·|B] denotes the conditional expectation and the process (G(t))_t∈ [0,1] is independent of (B(t))_t∈ [0,1],𝒢_θ on the left-hand side.



(b) If B_1,B_2,… denote independent standard Brownian motions, then

    (G(t))_t∈[0,1]    d= (√(θ(1-θ))∑_i≥ 1 (1-θ)^(i-1)/2.
         .×(B_i(t/i)- ∑_k≥ i+1θ(1-θ)^k-i-1 B_i(t/k)))_t∈[0,1].



Note that

    𝒢_θ^-1 = θlog(1/θ)/1-θ.

Three realisations of the process G, simulated by using the representation (<ref>), are shown in the right panel of Figure <ref>.





As already mentioned, the function g in (<ref>) can be found explicitly,  namely

    g(z) = z-1/z^2(log(1-z) + (1+z)log (1+z)),    |z|<1.


The graph of the variance g(1-θ), thus the variance of G(t)/t^1/2 for any 0<t≤ 1, is shown in the left panel of Figure <ref>. Indeed, it follows from (<ref>) that g(z)=h(z)-h(z^2),
where

    h(z) = ∑_k≥ 1z^k/k(k+1) = ∑_k≥ 1z^k/k-1/z∑_k≥ 1z^k+1/k+1 = 1+1-z/zlog (1-z)

for |z|<1.




It is known, see <cit.>, that

    log L_n    = θ∑_k≥ 1ψ(n/k)(1-θ)^k
       = nθlog (1/θ)/1-θ(1+O(exp{-C√(log (θ n))})),

where ψ is the second Chebyshev function, see (<ref>) below. Assuming the Riemann hypothesis the O-term can be substantially improved to

    log L_n=nθlog (1/θ)/1-θ(1+O(log^2n/√(n))),

see formula (6.2) in <cit.>.
However, even (<ref>) does not allow one to replace log L_⌊ nt⌋ in (<ref>) by ntθ(1-θ)^-1log (1/θ).


The following central limit theorem is an immediate consequence of Theorem <ref>.


As n→∞,

    log L_n-log L_n/√(nlog n) d→ √(g(1-θ)) 𝒩(0,1),

where 𝒩(0,1) is a standard normal random variable.


Expansion (<ref>) for the mean of log L_n in combination with an estimate of its variance provided in <cit.> will also allow us to prove the following strong version of (<ref>).


As n→∞,

    log L_n/n  θlog(1/θ)/1-θ.





 §.§ Poisson limit theorems

Two further theorems deal with the case when θ varies with n. In the first one it tends to zero at an appropriate speed, namely θ=θ(n)≃λ/n as n→∞ for some λ>0. Since the number of points retained in A_n is binomial with parameters n and θ and thus, for large n, approximately Poissonian with mean λ in the regime just defined, it should not surprise that the limit in the subsequent result is also Poisson. Let Π(λ) denote a Poisson random variable with mean λ.


Suppose that, as n→∞, θ=θ(n)≃λ/n for some λ>0. Then

    log L_n/log n d→ Π(λ)

as n→∞.


Another, in a sense antipodal regime in which the Poisson distribution appears is when θ=θ(n)→ 1 at an appropriate speed.


Suppose that, as n→∞, θ=θ(n) = 1- λ+ o(1)/nlog n for some λ>0. Then

    1/log n(∑_k=1^n Λ(k) - log L_n) d→ Π(λ/2)

as n→∞, where Λ denotes the von Mangoldt function defined by formula (<ref>) below.




§ PRELIMINARIES

In what follows, we let 𝒫 denote the set of prime numbers and m the set {m,2m,3m,…} of integral multiples of m∈. Recall that the von Mangoldt function Λ:↦ is defined as

    Λ(n)=
    log p,    if  n=p^k for some  k∈ and p∈𝒫,
    0,    otherwise.

We will also use the two Chebyshev functions ϑ and ψ. The first Chebyshev function ϑ:↦ is defined as

    ϑ(x) = ∑_p∈𝒫: p≤ xlog p,

and the second Chebyshev function ψ:↦ as

    ψ(x) = ∑_k≤ xΛ(k).

Recalling the identity

    log([n]) = ψ(n),

we state the following result taken from <cit.>, see Lemma 2.1 therein.


Let A be an arbitrary set of positive integers and (A) the least common multiple of the elements of A. Then

    log(A) = ∑_mΛ(m)I_A(m),

where

    I_A(m) :=
    1,    if  A∩ m∅,
    
    0,    otherwise.



Since

    log n = ∑_p∈𝒫log p ∑_k∈_{p^k | n} = ∑_p∈𝒫,k∈p^k | nlog p,

we further have

    log(A)    = ∑_p∈𝒫,k∈p^k |  (A)log p
       = ∑_p∈𝒫,k∈log p I_A(p^k) = ∑_mΛ(m) I_A(m),
    where
    p^k|(A)  ⟺   A∩{p^k,2p^k,3p^k,…,} = A∩ p^k  ∅

should be observed for the second equality.





§ PROOF OF THEOREM <REF>


The proof is divided into four steps. The first two steps provide that log L_n is well approximated by a sum of independent random variables. The third step will be to check that finite-dimensional distributions of the approximating sum converge to finite-dimensional distributions of the Gaussian process (G(t))_t∈[0,1]. In the fourth step, this will be improved to give the asserted functional limit theorem.



Step 1. By Lemma <ref>,

    log L_⌊ nt⌋    = log(A_⌊ nt⌋) = ∑_mΛ(m)I_A_⌊ nt⌋(m)
       = ∑_p∈𝒫log p∑_k≥ 1 I_A_⌊ nt⌋(p^k)
       = ∑_p∈𝒫log p  I_A_⌊ nt⌋(p) + ∑_p∈𝒫log p∑_k≥ 2 I_A_⌊ nt⌋(p^k)
       =: S_1(⌊ nt⌋) + S_2(⌊ nt⌋).

We will show first that, as n→∞,

    sup_t∈[0,1]S_2(⌊ nt⌋)/√(nlog n) → 0

which, by monotonicity of t↦ S_2(⌊ nt⌋), is equivalent to

    ∑_p∈𝒫log p∑_k≥ 2I_A_n(p^k)/√(nlog n) → 0.

By Markov's inequality, it suffices to verify

    ∑_p∈𝒫log p∑_k≥ 2 I_A_n(p^k)/√(nlog n) → 0

as n→∞. To this end, use Boole's inequality to obtain

    I_A_n(p^k) = {A_n∩ p^k∅} ≤ (∑_m≤ n/p^k{mp^k∈ A_n})∧ 1 ≤ nθ/p^k∧ 1.

Fix k≥ 2 and write

    ∑_p∈𝒫log p  I_A_n(p^k)    = ∑_p∈𝒫:p^k≤ nlog p  I_A_n(p^k)
       ≤ ∑_p∈𝒫:p^k≤ nlog p (nθ/p^k∧ 1)
       =nθ∑_p∈𝒫:(nθ)^1/k<p≤ n^1/klog p/p^k + ∑_p∈𝒫:p≤ (nθ)^1/klog p
       ≤ nθ∑_p∈𝒫:p>(nθ)^1/klog p/p^k + ∑_p∈𝒫:p≤ (nθ)^1/klog p.

For the first term in the previous line, Lemma <ref> in the Appendix provides the upper bound Cn^1/k for all n≥ 1 and some C>0. For the second sum we use the bound 
    ∑_p∈𝒫:p≤ (nθ)^1/klog p ≤ Cn^1/k

for all n and some C which follows from ∑_p∈𝒫:p≤ xlog p≃ x as x→∞, an equivalent form of the prime number theorem. In both esti­mates, the constant C does not depend on k. Summarizing, we arrive at the inequality

    ∑_p∈𝒫log p  I_A_n(p^k) ≤ C n^1/k

for all n≥ 1 and some positive constant C. Returning to (<ref>) and noting that summands in the numerator  are nonzero only for k≤log_2 n, (<ref>) implies

    ∑_p∈𝒫log p∑_k≥ 2 I_A_n(p^k)    ≤ C∑_k=2^⌈log_2 n⌉n^1/k
       ≤ C(√(n)+n^1/3log_2 n )=o(√(nlog n)),

as n→∞, and this proves (<ref>).



Step 2. We start with the decomposition

    S_1(⌊ nt⌋) = ∑_p∈𝒫log p  I_A_⌊ nt⌋(p) = S^(1,n)_1(t) + S^(2,n)_1(t),
    where
    S^(1,n)_1(t) := ∑_p∈𝒫:p≤√(n)log p  I_A_⌊ nt⌋(p)
    and
    S^(2,n)_1(t) := ∑_p∈𝒫:p>√(n)log p  I_A_⌊ nt⌋(p).

For the first sum, we then proceed as follows. Using the prime number theorem,

    sup_t∈[0,1]S^(1,n)_1(t) ≤ ∑_p∈𝒫:p≤√(n)log p ≃ √(n)

and therefore

    sup_t∈[0,1]S^(1,n)_1(t)/√(nlog n) ℙ→ 0
    as well as S^(1,n)_1(1)/√(nlog n) → 0

as n→∞.



In view of what has been shown so far, it remains to prove the asserted limit theorem for (S^(2,n)_1(t))_t∈ [0,1], i.e.

    (S^(2,n)_1(t)- S^(2,n)_1(t)/√(nlog n))_t∈ [0,1] J_1⟹ (G(t))_t∈[0,1],

which is possible because the processes (I_A_⌊ nt⌋(p))_t∈[0,1] and (I_A_⌊ nt⌋(q))_t∈[0,1] are independent for distinct primes p,q>√(n). For the latter, just observe that the sets p∩ [n] and q∩ [n] are disjoint for such p,q.



Step 3. Our aim is to show that, as n→∞,

    (∑_p∈𝒫:p>√(n)log p (I_A_⌊ nt⌋(p)- I_A_⌊ nt⌋(p))/√(nlog n))_t∈ [0,1] f.d.d.⟹  (G(t))_t∈[0,1].

First we show convergence of the covariances. For 0<s≤ t≤ 1, we have

    Cov   [S_1^(2,n)(t),S_1^(2,n)(s)]
       =∑_p∈𝒫∩(√(n),nt]∑_q∈𝒫∩(√(n),ns]log plog q  Cov[I_A_⌊ nt⌋(p),I_A_⌊ ns⌋(q)]
       =∑_p∈𝒫∩(√(n),ns]log^2p  Cov[I_A_⌊ nt⌋(p),I_A_⌊ ns⌋(p)]
       =∑_p∈𝒫∩(√(n),ns]log^2p   I_A_⌊ ns⌋(p)(1- I_A_⌊ nt⌋(p))
       =∑_p∈𝒫∩(√(n),ns]log^2p (1-(1-θ)^⌊ ns/p⌋)(1-θ)^⌊ nt/p⌋,

where the independence of (I_A_⌊ nt⌋(p))_t∈[0,1] and (I_A_⌊ nt⌋(q))_t∈[0,1] enters when passing to the second equality. By invoking Lemma <ref> in the Appendix, we infer for 0<s≤ t≤ 1

    lim_n→∞    Cov[S_1^(2,n)(t)/√(nlog n),S_1^(2,n)(s)/√(nlog n)]
       = ∑_j≥ 1(1-(1-θ)^j)∑_ i∈(tj/s-1,tj/s+t/s)(1-θ)^i(t/i∧s/j-t/i+1∨s/j+1)
       =: C_1(t,s).


In order to prove formula (<ref>) for C_1(t,s), write the latter in the form

    C_1(t,s)    = ∑_i,j≥ 1(1-(1-θ)^j)(1-θ)^i(t/i∧s/j-t/i+1∨s/j+1)^+
       = ∑_i,j≥ 1(∑_k=1^jp_k)(∑_l≥ i+1p_l)(t/i∧s/j-t/i+1∨s/j+1)^+
       = ∑_k≥ 1∑_l≥ 2p_kp_l∑_j≥ k∑_i=1^l-1(t/i∧s/j-t/i+1∨s/j+1)^+.

We claim that the inner double sum equals (s/k-t/l)^+. Consider two intervals (t/l,t] and (0,s/k]. Cover the first interval by the disjoint subintervals (t/(i+1),t/i], i=1,…,l-1 and, analogously, the second interval by the disjoint subintervals (s/(j+1),s/j], j≥ k. Then (t/i∧s/j-t/i+1∨s/j+1)^+ equals the length of the intersection of (t/(i+1),t/i] and (s/(j+1),s/j] and is zero if they are disjoint. The total sum of these lengths equals the length of the intersection of the original intervals (t/l,t] and  (0,s/k], thus (s/k-t/l)^+. Consequently,

    C_1(t,s) = ∑_k≥ 1∑_l≥ 2p_kp_l(s/k-t/l)^+ = ∑_k≥ 1∑_l≥ 1p_kp_l(s/k-t/l)^+,

where the second equality holds because (s/k-t)^+=0. Let η_1,η_2 be two independent geometric random variables on , viz.

    {η_1=k} = {η_2=k} = θ(1-θ)^k-1,   k∈.

Then

    C_1(t,s)    = (s/η_1-t/η_2)^+ = (s/η_1-s/η_1∧t/η_2)
       = ∑_k≥ 1s/kp_k - ∑_k,l≥ 1(s/k∧t/l)p_kp_l

which is the asserted result as s<t.



To complete the proof of (<ref>), it remains to verify the Lindeberg condition

    lim_n→∞∑_p∈𝒫∩(√(n),nt][|V_n,p(t)|^2_{|V_n,p(t)|>ε}] = 0.

for any t∈ [0,1] and ε>0, where

    V_n,p(t) := log p(I_A_⌊ nt⌋(p)- I_A_⌊ nt⌋(p))/√(nlog n)

for p∈𝒫∩ (√(n),n]. But this is obvious because |V_n,p(t)|≤√(log n/n) for all such p and t∈ [0,1], n∈.



Step 4. In order to finally show the functional limit theorem, we will apply Theorem 10.6 from <cit.> that provides general conditions for the convergence
of triangular arrays of row-wise independent processes to a Gaussian limit. Actually, this theorem yields convergence in the sense of convergence in the space of bounded functions with the usual supremum-norm, which is stronger. Convergence in D[0,1] with the J_1-topology follows as a direct consequence.

To conform with the notation in  <cit.>, put

    f_n,p(t):=log p  I_A_⌊ nt⌋(p)/√(nlog n)  and   F_n,p:=log p  I_A_n(p)/√(nlog n)

for p∈𝒫∩ (√(n),n]. Conditions (ii) and (iv) of Theorem 10.6 in <cit.> were checked in Step 3. Condition (iii) is obvious. The manageability of the family (f_n,p(·))_p (Condition (i) of Theorem 10.6 in <cit.>) follows from the monotonicity of
(f_n,p(t))_t∈ [0,1] in t for every fixed n and p, and the observation in the paragraph just before Theorem 11.17 in <cit.>. It remains to verify condition (v). To this end, introduce the function

    ρ_n(s,t) := (∑_p∈𝒫∩ (√(n),n]log^2p  | I_A_⌊ nt⌋(p)-I_A_⌊ ns⌋(p)|^2/nlog n)^1/2

for 0≤ s, t≤ 1. Note that

    | I_A_⌊ nt⌋(p)-I_A_⌊ ns⌋(p)|^2 = {I_A_⌊ nt⌋(p)-I_A_⌊ ns⌋(p)=1}
       = 1-{I_A_⌊ nt⌋(p)-I_A_⌊ ns⌋(p)=0}
       = (1-θ)^⌊ ns/p⌋-(1-θ)^⌊ nt/p⌋.
    and therefore   ρ_n(s,t) := (∑_p∈𝒫∩ (√(n),n]log^2p ((1-θ)^⌊ ns/p⌋-(1-θ)^⌊ nt/p⌋)/nlog n)^1/2

for 0<s≤ t≤ 1. Decomposing the numerator on the right-hand side as

    ∑_p∈𝒫∩ (√(n),n]   log^2p ((1-θ)^⌊ ns/p⌋-(1-θ)^⌊ nt/p⌋)
       = ∑_p∈𝒫∩ (√(n),ns]log^2p  (1-θ)^⌊ ns/p⌋ + ∑_p∈𝒫∩ (ns,n]log^2p
       - ∑_p∈𝒫∩ (√(n),nt]log^2p  (1-θ)^⌊ nt/p⌋ - ∑_p∈𝒫∩ (nt,n]log^2p,

and applying Lemma <ref> in conjunction with formula (<ref>) in the Appendix, we deduce

    lim_n→∞ρ_n(s,t)=√((1-h(1-θ))(t-s))

for 0<s≤ t≤ 1. Now let (s_n)_n≥ 1 and (t_n)_n≥ 1 be two deterministic sequences in [0,1] such that s_n-t_n→ 0 as n→∞. We must show that

    lim_n→∞ρ_n(s_n,t_n)=0,
    or, equivalently,lim_n→∞∑_p∈𝒫∩ (√(n),n]log^2p |(1-x)^⌊ ns_n/p⌋-(1-x)^⌊ nt_n/p⌋|/nlog n  = 0.

Putting u_n:=s_n∧ t_n and v_n:=s_n∨ t_n, this follows if

    lim_n→∞∑_p∈𝒫:p≤ nlog p ((1-θ)^⌊ nu_n/p⌋-(1-θ)^⌊ nv_n/p⌋)/n = 0.

Using Lemma <ref>, we find that, for a suitable constant C>0,

    1/n∑_p∈𝒫:p≤ n   log p((1-θ)^⌊ nu_n/p⌋-(1-θ)^⌊ nv_n/p⌋)
       ≤ (v_n-u_n)h(1-θ) + Cu_n/log (nu_n+2) + Cv_n/log (nv_n+2)
       ≤ (v_n-u_n)h(1-θ) + 2C/log (n+2),

and the last line converges to 0 because v_n-u_n=|s_n-t_n|→ 0, as n→∞.

It remains to note that Theorem 10.6 in <cit.> guarantees that the limit process a.s. has uniformly continuous paths. This completes the proof of Theorem <ref>.





§ PROOF OF PROPOSITION <REF>

(a) Since (G(t))_t∈[0,1] defined in Theorem <ref> is Gaussian, the same holds true for the process ([B(t/𝒢_θ)|B])_t∈[0,1] as one can readily see from the representation

    [B(t/𝒢_θ)|B]    = ∑_k≥ 1p_k B(t/k) =∑_k≥ 1p_k∫_0^∞_{z≤ t/k}  dB(z)
       = ∫_0^∞(∑_k≥ 1p_k_{z≤ t/k})  dB(z).

By the independence assumption, it is enough to check the equality of covariances which follows immediately from the identities

    Cov[[B(t/𝒢_θ)|B],[B(s/𝒢_θ)|B]]    = Cov[∑_k≥ 1p_k B(t/k),∑_l≥ 1p_lB(s/l)]
       = ∑_k,l≥ 1p_kp_l(t/k∧s/l)

and

    Cov[B(t(𝒢_θ^-1)),B(s(𝒢_θ^-1))] = (t∧ s)𝒢_θ^-1 = ∑_k≥ 1(s/k∧t/k)p_k

for 0≤ s,t≤ 1.



(b) Since the series on the right-hand side of (<ref>) is a centered Gaussian process, it suffices again to check the equality of covariances. We have

    √(θ(1-θ))∑_i≥ 1 (1-θ)^(i-1)/2(B_i(t/i)- ∑_k≥ i+1θ(1-θ)^k-i-1 B_i(t/k))
    
    =: ∑_i≥ 1∑_k≥ ia_ikB_i(t/k),

where

    a_ik:=
    θ^1/2 (1-θ)^i/2,    if k=i,
    
    -θ^3/2(1-θ)^k-i/2-1,    if k>i.

Using independence of B_1,B_2,… and the formula Cov[B_i(s),B_i(t)]=s∧ t, we obtain for its covariance function

    ρ(s,t) :=     Cov[∑_i≥ 1∑_k≥ ia_ikB_i(t/k),∑_j≥ 1∑_l≥ ja_jlB_j(s/l)]
    
    =    ∑_i≥ 1∑_k≥ i∑_l≥ ia_ika_il(t/k∧s/l) = ∑_k≥ 1∑_l≥ 1(t/k∧s/l)∑_i=1^k∧ la_ika_il.

If k=l, then

    ∑_i=1^k∧ la_ika_il    = ∑_i=1^ka_ik^2 = θ(1-θ)^k+θ^3∑_i=1^k-1 (1-θ)^2k-i-2
       = θ(1-θ)^k+θ^2(1-θ)^k-1(1-(1-θ)^k-1)
       = p_k-p_k^2 = p_k-p_kp_l,
    while for k<l∑_i=1^k∧ la_ika_il    = a_kka_kl+∑_i=1^k-1a_ika_il
       = -θ^2(1-θ)^l-1
    +
    θ^3∑_i=1^k-1(1-θ)^k+l-i-2 = -p_kp_l.

A combination of these results yields

    ρ(s,t) = ∑_k≥ 1s∧ t/kp_k - ∑_k,l≥ 1(t/k∧s/l)p_kp_l,

which shows the desired equality of distributions and completes the proof of Proposition <ref>.




§ PROOF OF THEOREM <REF>


For ε>0 and n∈, we define the events

    A_n(ε) := {|log L_n-log L_n|>ε log L_n}.

Proposition 2.2 from <cit.> provides us with

    Var[log L_n] = O(nlog^2n)

as n→∞ which in combination with the expansion of log L_n in (<ref>) implies that

    {A_n(ε)} ≤ Clog^2(n+1)/n

for all n≥ 1 and some constant C=C(ε,θ)>0. Putting n_k:=[klog^4k] for k≥ 1, it follows from (<ref>) that ∑_k≥ 2{A_n_k(ε)}<∞ for any ε>0 and thus

    lim_k→∞log L_n_k/log L_n_k = 1  a.s.

by the Borel-Cantelli lemma. For arbitrary n∈, let k(n) be such that n_k(n)≤ n<n_k(n)+1 and notice that, as a trivial consequence of (<ref>),

    lim_k→∞log L_n_k+1/log L_n_k = 1.

The proof of the theorem is now completed by a combination of the latter fact with (<ref>) and the inequalities

    log L_n_k/log L_n_k·log L_n_k/log L_n_k+1 ≤ log L_n/log L_n ≤ log L_n_k+1/log L_n_k+1·log L_n_k+1/log L_n_k,

valid for any n≥ 1.



§ PROOF OF THEOREMS <REF> AND <REF>




 §.§ Proof of Theorem <ref>

Let R(n) be the number of remaining integers in [n], i.e. R(n):=|A_n|, and note that R(n) has a binomial distribution with parameters n and θ(n). Since θ(n)≃λ/n, the classical Poisson limit theorem gives

    R(n) d→ Π(λ)

as n→∞. Let (X_1^(n),X_2^(n),…,X_R(n)^(n)) denote the ordered sample of remaining integers which, conditioned upon R(n)=k, has the same distribution as an ordered k-sample without replacement from the set [n]. In order to show that, as n→∞,

    log(X_1^(n),X_2^(n),…,X_R(n)^(n))/log n d→ Π(λ),

it is enough to show that, conditioned upon R(n)=k for any fixed k∈,

    log(X_1^(n),X_2^(n),…,X_k^(n))/log n → k

as n→∞. Given any finite set of positive integers {n_1,n_2,…,n_k}, we have that

    n_1n_2⋯ n_k/∏_1≤ i<j≤ k(n_i,n_j) ≤ (n_1,n_2,…,n_k) ≤ n_1n_2⋯ n_k.

For (<ref>), it hence suffices to verify that, given R(n)=k,

    ∑_i=1^klog X_i^(n)/log n → k
    and∑_1≤ i < j ≤ klog(X_i^(n),X_j^(n))/log n → 0.

Let (U_k^(n))_k∈ be a sequence of i.i.d. random variables with a uniform distribution on [n]. Then, as already stated above, the conditional law of (X_1^(n),…,X_k^(n)) given R(n)=k for any fixed k∈, is the same as the conditional law of (U_(1)^(n),…,U_(k)^(n)), the order statistics of (U_1^(n),…,U_k^(n)), given the event

    A_n,k := {U_i^(n) U_j^(n): i,j=1,…, k,i j,}.

Since {A_n,k} tends to 1 for any k∈ and n→∞, (<ref>) and (<ref>) are equivalent to

    ∑_i=1^klog U_i^(n)/log n → kandlog(U_1^(n),U_2^(n))/log n→ 0,

respectively. Assertion (<ref>) follows directly from

    lim_n→∞{1-ε<log U_1^(n)/log n≤ 1 } = lim_n→∞{n^1-ε<U_1^(n)≤ n} = 1

for any ε∈ (0,1) and Slutsky's lemma.



For (<ref>), we will in fact prove the stronger result that, as n→∞,

    log(U_1^(n),U_2^(n)) d→ ξ

for some proper nondegenerate random variable ξ to be defined below. Writing

    U_1^(n) = ∏_p∈𝒫p^λ_p(U_1^(n))  and   U_2^(n) = ∏_p∈𝒫p^λ_p(U_2^(n)),

where λ_p(m)≥ 0 is the power of prime p in the prime decomposition of m∈, we have

    log(U_1^(n),U_2^(n)) = ∑_p∈𝒫(λ_p(U_1^(n))∧λ_p(U_2^(n)))log p.

It is a simple fact, see for example the last display on p. 28 in <cit.>, that

    (λ_p(U_1^(n)))_p∈𝒫 d→ (Z_1,p)_p∈𝒫,

where (Z_1,p)_p∈𝒫 forms a sequence of independent random variables and Z_1,p has a geometric distribution on {0,1,2,…,} with parameter 1-1/p. Likewise,

    (λ_p(U_2^(n)))_p∈𝒫 d→ (Z_2,p)_p∈𝒫,

where (Z_1,p)_p∈𝒫d=(Z_2,p)_p∈𝒫, (Z_1,p)_p∈𝒫 and  (Z_2,p)_p∈𝒫 are independent. The series

    ξ := ∑_p∈𝒫(Z_1,p∧ Z_2,p)log p

converges a.s. because it has finite mean, viz.

    ∑_p∈𝒫 (Z_1,p∧ Z_2,p)log p = ∑_p∈𝒫log p/p^2-1<∞.

We note in passing that the explicit form of the distribution of ξ may be found in <cit.>.
According to Theorem 3.2 in <cit.>, a sufficient condition for (<ref>) is that

    lim_m→∞lim sup_n→∞{∑_p∈𝒫:p≥ m(λ_p(U_1^(n))∧λ_p(U_2^(n)))log p≥ε} = 0

for any ε>0. We will show the in fact stronger condition (by Markov's inequality)

    lim_m→∞lim sup_n→∞∑_p∈𝒫:p≥ m(λ_p(U_1^(n))∧λ_p(U_2^(n)))log p = 0.

To this end, note that

    (λ_p(U_1^(n))∧λ_p(U_2^(n))) = ∑_i≥ 1{λ_p(U_1^(n))≥ i,λ_p(U_2^(n))≥ i}
    
    = ∑_i≥ 1(1/n⌊n/p^i⌋)^2 ≤ ∑_i≥ 11/p^2i = 1/p^2-1.

Relation (<ref>) now follows from (<ref>), thus completing the proof of Theorem <ref>.



 §.§ Proof of Theorem <ref>

Using Lemma <ref>, we can write

    ∑_k=1^nΛ(k)-log L_n = ∑_k=1^nΛ(k)(1-I_A_n(k))

and infer

    ∑_k≤ n/2Λ(k)(1-I_A_n(k)) → 0   (n→∞)

from 

    {∑_k≤ n/2Λ(k)(1-I_A_n(k))>0} ≤ {I_A_n(k)=0 for some k≤ n/2}
    ≤ ∑_k≤ n/2{I_A_n(k)=0} ≤ ∑_k≤ n/2{k∉ A_n,2k∉ A_n}
    ≤n/2 (λ+o(1))^2log^2n/n^2.


Left with the sum ∑_n/2<k≤ nΛ(k)(1-I_A_n(k)), we note that the random variables {1-I_A_n(k): n/2<k≤ n} are independent indicators satisfying

    {1-I_A_n(k)=1} = {k∉ A_n} = 1-θ(n) ≃ λlog n/n

as n→∞. By definition of the von Mangoldt function Λ, we have

    ∑_n/2<k≤ nΛ(k)(1-I_A_n(k))    = ∑_p∈𝒫log p (1-I_A_n(p))_{n/2<p≤ n}
    
       +∑_p∈𝒫∑_l≥ 2log p (1-I_A_n(p^l))_{n/2<p^l≤ n}.

The expectation of the last term on the right-hand side equals

    (1-θ(n))   ∑_p∈𝒫∑_l≥ 2log p _{n/2<p^l≤ n}
       = (λ+o(1)) log n/n∑_p∈𝒫∑_l≥ 2log p _{n/2<p^l≤ n}
       ≤ (λ+o(1)) log n/n∑_p∈𝒫∑_l≥ 2log p _{p^l≤ n}
       = (λ+o(1))log n/n(ψ(n)-ϑ(n)),

where ψ and ϑ are the Chebyshev functions, see Formulae (<ref>) and (<ref>). By Theorem 4.1 in <cit.>,

    ψ(n)-ϑ(n) = O(√(n)log^2n)

as n→∞, and this in combination with Markov's inequality implies

    ∑_p∈𝒫∑_l≥ 2log p (1-I_A_n(p^l))_{n/2<p^l≤ n} → 0

as n→∞. It remains to show that

    ∑_p∈𝒫log p (1-I_A_n(p))_{n/2<p≤ n}/log n d→ Π(λ/2).

In view of the obvious inequalities

    log(n/2)∑_p∈𝒫(1-I_A_n(p))_{n/2<p≤ n}    ≤ ∑_p∈𝒫log p (1-I_A_n(p))_{n/2<p≤ n}
       ≤ log n∑_p∈𝒫(1-I_A_n(p))_{n/2<p≤ n},

the claim of the theorem follows from the observation that

    ∑_p∈𝒫∩ (n/2,n](1-I_A_n(p)) = ∑_p∈𝒫∩ (n/2,n]_{p∉ A_n} d→ Π(λ/2),   n→∞.

The latter convergence holds by the classic Poisson limit theorem for independent indicators, here Bernoulli variables with parameter 1-θ(n). The factor 1/2 in the parameter of the Poisson random variable appears because, with π(x) denoting the number of primes ≤ x,  the number of summands is π(n)-π(n/2)∼n/2log n, as n→∞ by the prime number theorem. The proof of Theorem <ref> is complete.




§ APPENDIX

We have used the following estimate for the tails of convergent series involving primes.

There exists a positive constant C such that, for all n∈ and k≥ 2,

    ∑_p∈𝒫:p≥ nlog p/p^k ≤ C/n^k-1.



For any n≥ 2 and with π(x) as above, integration by parts yields

    ∑_p∈𝒫:p≥ nlog p/p^k    = ∫_[n,∞)log x/x^k  dπ(x)
       = log x/x^kπ(x)|_n^∞ + ∫_n^∞π(x)kx^k-1log x-x^k-1/x^2k  dx
       ≤ ∫_n^∞π(x)kx^k-1log x/x^2k  dx.

By the prime number theorem, π(x)≤ C_1x/log x for some constant C_1>0 and all x≥ 2. Consequently,

    ∑_p∈𝒫:p≥ nlog p/p^k ≤ C_1k∫_n^∞ dx/x^k = C_1k/k-1n^1-k≤2C_1/n^k-1

and thus (<ref>) holds with C:=2C_1.



For any fixed x,t∈ (0,1),

    ∑_p∈𝒫:p∈ (√(n),nt]log^2p (1-x)^⌊ nt/p⌋ ≃ t· nlog n· h(1-x),

where h(x)=∑_k≥ 1x^k/k(k+1).


Let us first show that

    ∑_p∈𝒫:p≤ xlog^2p ≃ xlog x.

as x→∞. To this end, note that

    ∑_p≤ x,p∈𝒫log^2p = ∫_[2,x]log^2z  dπ(z) = π(z)log^2z|_2^x-∫_2^x 2π(z)log z/z  dz.

By another appeal to the prime number theorem, π(x)log^2x≃ xlog x and the integrand is bounded, i.e., the integral itself is O(x) as x→∞. This proves (<ref>) which in turn further provides us with the relation

    ∑_p∈𝒫∩ (nt/(k+1),nt/k]log^2p ≃ ntlog n/k(k+1)   (n→∞)

for any k∈ and t∈(0,1].

Now fix an arbitrary m∈ and write

    ∑_p∈𝒫∩ (√(n),nt](1-x)^⌊ nt/p⌋log^2p    = ∑_k=1^⌊√(n)t⌋(1-x)^k∑_p∈𝒫∩ (nt/(k+1),nt/k]log^2p
       = ∑_k=1^m(1-x)^k∑_p∈𝒫∩ (nt/(k+1),nt/k]log^2p
           +∑_k=m+1^⌊√(n)t⌋(1-x)^k∑_p∈𝒫∩ (nt/(k+1),nt/k]log^2p
       =: A_1(n,m)+A_2(n,m).

By (<ref>), we have

    lim_n→∞A_1(n,m)/nlog n = t∑_k=1^m(1-x)^k/k(k+1),

and for A_2(n,m), the estimate

    A_2(n,m)    ≤ ∑_k≥ m+1(1-x)^k∑_p∈𝒫:p≤ nlog^2p
       ≤ Cnlog n∑_k≥ m+1(1-x)^k = Cx^-1(1-x)^m+1nlog n

for some C>0 follows as a consequence of (<ref>). Hence,

    lim sup_n→∞A_2(n,m)/nlog n≤ Cx^-1(1-x)^m+1.

By combining these facts, we obtain

    t∑_k=1^m(1-x)^k/k(k+1) ≤ lim inf_n→∞∑_p∈𝒫∩ (√(n),nt](1-x)^⌊ nt/p⌋log^2p/nlog n
    ≤ lim sup_n→∞∑_p∈𝒫∩ (√(n),nt](1-x)^⌊ nt/p⌋log^2p/nlog n≤ t∑_k=1^m(1-x)^k/k(k+1) + Cx^-1(1-x)^m+1

for any fixed m∈. Sending m→∞ yields the assertion and completes the proof.


The next lemma forms an extension of the previous one and an important ingredient in the proof of our main theorem (convergence of covariances).


For any fixed x∈ (0,1) and 0<s≤ t≤ 1,

    1/nlog n∑_p∈𝒫∩ (√(n),ns](1-x)^⌊ nt/p⌋(1-(1-x)^⌊ ns/p⌋)log^2p 
    ≃ ∑_j≥ 1(1-(1-x)^j)∑_ i∈(tj/s-1,tj/s+t/s)(1-x)^i(t/i∧s/j-t/i+1∨s/j+1),

as n→∞.



We start by noting the equivalence

    ⌊ nt/p⌋=i  and  ⌊ ns/p⌋=j  ⟺   p∈(nt/i+1∨ns/j+1,nt/i∧ns/j],

where the interval on the right can be empty. Fix j∈ and let us find all integers i such that

    t/i+1∨s/j+1<t/i∧s/j.


If t/(i+1)<s/(j+1) or, equivalently, i>t(j+1)/s-1, then (<ref>) holds iff i<t(j+1)/s. If t/(i+1)≥ s/(j+1) or, equivalently, i≤ t(j+1)/s-1, then (<ref>) holds iff i>tj/s-1. Therefore, for any fixed j∈, (<ref>) holds iff

    tj/s-1<i<t(j+1)/s,

and this implies

    ∑_p∈𝒫∩ (√(n),ns]log^2p (1-x)^⌊ nt/p⌋(1-(1-x)^⌊ ns/p⌋)
         =∑_j=1^⌊√(n)s⌋(1-(1-x)^j)∑_i∈(tj/s-1,tj/s+t/s)(1-x)^i∑_p∈𝒫∩(nt/i+1∨ns/j+1,nt/i∧ns/j]log^2p.

It remains to note that, for any fixed j∈ and any integer i∈(tj/s-1,tj/s+t/s),

    ∑_p∈𝒫∩(nt/i+1∨ns/j+1,nt/i∧ns/j]log^2p ≃ (t/i∧s/j-t/i+1∨s/j+1)nlog n,

as n→∞. Now arguing in the same way as in the last part of the proof of Lemma <ref> and noting that the series

    ∑_j≥ 1(1-(1-x)^j)∑_i∈(tj/s-1,tj/s+t/s)(1-x)^i(t/i∧s/j-t/i+1∨s/j+1)

converges, we obtain the assertion of the lemma.



For any x∈(0,1), there exists C=C(x)>0 such that

    |∑_p∈𝒫:p≤ t(1-x)^⌊ t/p⌋log p - th(1-x)| ≤ Ct/log (t+2),

for all t≥ 0, where h is as defined in Lemma <ref>.


We may assume without loss of generality that t≥ t_0 for a fixed t_0. Recalling that ϑ denotes the first Chebyshev function defined by (<ref>), we can write

    ∑_p∈𝒫:p≤ tlog p  (1-x)^⌊ t/p⌋    = ∑_i=1^⌊ t⌋(1-x)^i∑_p∈𝒫∩ (t/(i+1),t/i]log p
       =∑_i=1^⌊ t⌋(1-x)^i(ϑ(t/i)-ϑ(t/i+1)).

Using the well-known inequality

    |ϑ(z)-z| ≤ C_1z/log (z+2),

valid for all z≥ 0 and some C_1>0, we obtain

    |∑_p∈𝒫:p≤ t(1-x)^⌊ t/p⌋log p - t∑_i=1^⌊ t⌋(1-x)^i/i(i+1)|
       ≤ 2C_1t/log (t+2)∑_i=1^⌊ t⌋(1-x)^i ≤ 2(1-x)C_1t/xlog (t+2).

Finally, since h(1-x)-∑_i=1^⌊ t⌋(1-x)^i/i(i+1)=∑_i≥⌊ t⌋+1(1-x)^i/i(i+1) satisfies the inequality

    t∑_i≥⌊ t⌋+1(1-x)^i/i(i+1) ≤ ∑_i≥⌊ t⌋+11/i(i+1) ≤ 1/⌊ t⌋+1,

we infer (<ref>) with C=C(x)=2(1-x)C_1/x+1 for all sufficiently large t.



amsplain


