On the Least Common Multiple of Shifted Powers

Carlo Sanna Politecnico di Torino Department of Mathematical Sciences Corso Duca degli Abruzzi 24 10129 Torino Italy

                   carlo.sanna.dev@gmail.com

Abstract We determine the asymptotic behavior of log lcm(a + s_{1}, a^{2} + s_{2}, …, a^{n} + s_{n}), for a ≥ 2 an integer and (s_{n})_{n≥1} a periodic sequence in {−1, +1}. We also carry out the same analysis for (s_{n})_{n≥1} a sequence of independent and uniformly distributed random variables in {−1, +1}.

1 Introduction

Let (F_{n})_{n≥1} be the sequence of Fibonacci numbers, defined recursively by F_{1} = 1, F_{2} = 1, and F_{n+2} = F_{n+1} + F_{n}, for every integer n ≥ 1. Matiyasevich and Guy [10] proved that

log lcm(F_{1}, F_{2}, …, F_{n}) ∼ \frac{3 log(\frac{1+\sqrt{5}}{2})}{π^{2}} · n^{2},

as n → +∞, where lcm denotes the least common multiple. This result was generalized to Lucas sequences, Lehmer sequences, and other sequences with special divisibility properties [1–4,6,8,9,16]. In particular, for every integer a ≥ 2 we have

log lcm(a − 1, a^{2} − 1, …, a^{n} − 1) ∼ \frac{3 log a}{π^{2}} · n^{2}  (1)

and

log lcm(a + 1, a^{2} + 1, …, a^{n} + 1) ∼ \frac{4 log a}{π^{2}} · n^{2},  (2)

as n → +∞. Precisely, (1) follows from [9, Lemma 3] applied to the Lucas sequence (\frac{a^{n}−1}{a−1})_{n≥1}, while (2) follows from [6, Théorème] applied to the companion Lucas sequence (a^{n} + 1)_{n≥1}.

We generalize (1) and (2) by giving asymptotic formulas for least common multiples of sequences of shifted powers (a^{n} + s_{n})_{n≥1}, where (s_{n})_{n≥1} is a sequence of shifts in {−1, +1}. This is somehow similar to a previous work of the author [14], in which least common multiples of the sequence of shifted Fibonacci numbers (F_{n} + s_{n})_{n≥1} were studied.

Our first result regards periodic sequences of shifts.

Theorem 1. Let a ≥ 2 be an integer and let s = (s_{n})_{n≥1} be a periodic sequence in {−1, +1}. Then there exists an effectively computable rational number C_{s} > 0 such that

log lcm(a + s_{1}, a^{2} + s_{2}, …, a^{n} + s_{n}) ∼ C_{s} · \frac{log a}{π^{2}} · n^{2},  (3)

as n → +∞.

By “effectively computable” we mean that there exists an algorithm that, given as input the period of the periodic sequence s, returns as output the numerator and denominator of the rational number C_{s}. Indeed, we implemented such algorithm and we computed the constant C_{s} for periodic sequences with short period, see Table 1.

s  C_{s}  s  C_{s}  s  C_{s}  s  C_{s}
-  3  -+-- 27/8 --+-+ 319/96 +--+- 733/216
+  4  -++- 125/36 --++- 487/144 +--++ 769/216
-+  4  -+++ 38/9 --+++ 7687/2160 +-+-- 487/144
+-  3  +---  3  -+--- 101/32 +-+-+ 7687/2160
--+ 13/4 +--+ 7/2 -+--+ 319/96 +-++- 2123/576
-+- 105/32 +-++ 7/2 -+-+- 487/144 +-+++ 2219/576
-++ 173/48 ++-- 125/36 -+-++ 7687/2160 ++--- 487/144
+-- 105/32 ++-+ 38/9 -++-- 733/216 ++--+ 7687/2160
+-+ 173/48 +++- 27/8 -++-+ 769/216 ++-+- 2123/576
++- 47/12 ----+ 19/6 -+++- 2123/576 ++-++ 2219/576
---+ 7/2 ---+- 101/32 -++++ 2219/576 +++-- 2123/576
--+- 3 ---++ 319/96 +---- 101/32 +++-+ 2219/576
--++ 7/2 --+-- 101/32 +---+ 319/96 ++++- 39/10

Table 1: Values of C_{s} for periodic sequences s of period at most 5.

Our second result is an asymptotic formula for random sequences of shifts (see [5,7,12,13] for similar results on least common multiples of random sequences).

Theorem 2. Let a ≥ 2 be an integer and let (s_{n})_{n≥1} be a sequence of independent and uniformly distributed random variables in {−1, +1}. Then

log lcm(a + s_{1}, a^{2} + s_{2}, …, a^{n} + s_{n}) ∼ 6 Li_{2}(\frac{1}{2}) · \frac{log a}{π^{2}} · n^{2},  (4)

with probability 1−o(1), as n → +∞, where Li_{2}(z) := ∑_{k=1}^{∞} z^{k}/k^{2} is the dilogarithm function.

Remark 1. It is known that Li_{2}(\frac{1}{2}) = (π^{2} − 6(log 2)^{2})/12 (see, e.g., [17]), but in (4) we preferred to keep explicit the factor 6 Li_{2}(\frac{1}{2}) in order to ease the comparison with (1), (2), and (3). Numerically, we have 6 Li_{2}(\frac{1}{2}) = 3.493443 … so that the right-hand side of (4) is a bit less than the arithmetic mean of the right-hand sides of (1) and (2).

We leave the following questions to the interested reader: Question 1. Is there a simple characterization of the set E of sequences s = (s_{n})_{n≥1} in {−1, +1} such that the limit

L(s) := lim_{n→+∞} \frac{log lcm(a + s_{1}, a^{2} + s_{2}, …, a^{n} + s_{n})}{(log a/π^{2}) · n^{2}}

exists? (It follows from Lemma 3 below that L(s) does not depend on a.) Question 2. What is the image L(E)? Question 3. Does (an appropriate normalization of) the random variable on the left-hand side of (4) converge to some known distribution?

2 Notation

We employ the Landau-Bachmann “Big Oh” and “little oh” notations O and o, as well as the associated Vinogradov symbol ≪, with their usual meanings. For real random variables X_{n} and Y_{n}, depending on n, we say that “X_{n} ∼ Y_{n} with probability 1 − o(1) as n → +∞” if for every ε > 0 we have ℙ[|X_{n} − Y_{n}| > ε|Y_{n}|] = o_{ε}(1) as n → +∞. We let [m, n] and (m, n) denote the least common multiple and the greatest common divisor, respectively, of the two integers m and n. We reserve the letter p for prime numbers, and we let ν_{p}(n) denote the p-adic valuation of the positive integer n, that is, the exponent of p in the prime factorization of n. We write φ(n) and τ(n) for the Euler function and the number of positive divisors, respectively, of a natural number n.

3 Preliminaries

Hereafter, let a ≥ 2 be a fixed integer. Define the nth cyclotomic polynomial by

Φ_{n}(X) := ∏_{\begin{matrix}1 ≤ k ≤ n \\ (n,k) = 1 \end{matrix}} (X − e^{\frac{2πik}{n}} ) ,  (5)

for every integer n ≥ 1. It is well known that Φ_{n}(X) ∈ ℤ[X]. Moreover, from (5) we get that

a^{n} − 1 = ∏_{d ∈ D^{−}(n)} Φ_{d}(a) and a^{n} + 1 = ∏_{d ∈ D^{+}(n)} Φ_{d}(a),  (6)

for every integer n ≥ 1, where D^{−}(n) := {d ∈ ℕ : d | n} and D^{+}(n) := D^{−}(2n) \ D^{−}(n). We need two results about the sequence of integers (Φ_{d}(a))_{d∈ℕ}.

Lemma 1. We have (Φ_{m}(a), Φ_{n}(a)) | m, for all integers m > n ≥ 1.

Proof. Let d := (Φ_{m}(a), Φ_{n}(a)). By (6) we have that d divides (a^{m} − 1, a^{n} − 1) = a^{(m,n)} − 1. Moreover, since (m, n) < m, by (6) again we have that

d | Φ_{m}(a) | \frac{a^{m} − 1}{a^{(m,n)} − 1} ≡ 1 + a^{(m,n)} + (a^{(m,n)})^{2} + ⋯ + (a^{(m,n)})^{\frac{m}{(m,n)} −1} ≡ \frac{m}{(m, n)} (mod d).

Consequently, d divides m/(m, n) and, a fortiori, d divides m.

Lemma 2. We have log Φ_{n}(a) = φ(n) log a + O_{a}(1), for every integer n ≥ 1.

Proof. See [11, Lemma 2.1(iii)].

For every sequence s = (s_{n})_{n≥1} in {−1, +1}, let us define

ℓ_{a,s}(n) := lcm(a + s_{1}, a^{2} + s_{2}, …, a^{n} + s_{n})

and

L_{s}(n) := ⋃_{k ≤ n} D^{(s_{k})}(k),

for all integers n ≥ 1.

The next lemma will be fundamental in the proofs of Theorem 1 and Theorem 2.

Lemma 3. We have

log ℓ_{a,s}(n) = ∑_{d ∈ L_{s}(n)} φ(d) log a + O_{a}(\frac{n^{2}}{log n}) ,

for every integer n ≥ 2.

Proof. For every integer m ≥ 1, write m = m^{(≤)} · m^{(>)}, where m^{(≤)}, respectively m^{(>)}, is a positive integer having all the prime factors not exceeding 2n, respectively greater than 2n.

Suppose that p^{v} || ℓ_{a,s}(n), for some prime number p ≤ 2n and some integer v ≥ 1. Then p^{v} | a^{k} + s_{k} for some positive integer k ≤ n, and consequently p^{v} ≤ a^{n+1}. Therefore,

log ℓ_{a,s}^{(≤)}(n) = log( ∏_{\begin{matrix}p^{v} || ℓ_{a,s}(n) \\ p ≤ 2n \end{matrix}} p^{v}) ≤ log( ∏_{\begin{matrix}p^{v} || ℓ_{a,s}(n) \\ p ≤ 2n \end{matrix}} a^{n+1})

≤ #\{p : p ≤ 2n\} · (n + 1) log a ≪_{a} \frac{n^{2}}{log n},  (7)

since the number of primes not exceeding 2n is O(n/log n).

On the one hand, in light of Lemma 1, the integers Φ_{1}^{(>)}(a), …, Φ_{2n}^{(>)}(a) are pairwise coprime. Hence, also using (6), we have

ℓ_{a,s}^{(>)}(n) = lcm_{k = 1,...,n}(a^{k} + s_{k})^{(>)} = lcm_{k = 1,...,n} ∏_{d ∈ D^{(s_{k})}(n)} Φ_{d}^{(>)}(a)
= lcm_{k = 1,...,n} lcm_{d ∈ D^{(s_{k})}(n)} Φ_{d}^{(>)}(a) = lcm_{d ∈ L_{s}(n)} Φ_{d}^{(>)}(a) | lcm_{d ∈ L_{s}(n)} Φ_{d}(a).  (8)

On the other hand, using (6) again, we have

lcm_{d ∈ L_{s}(n)} Φ_{d}(a) = lcm_{k = 1,...,n} lcm_{d ∈ D^{(s_{k})}(n)} Φ_{d}(a) | lcm_{k = 1,...,n} ∏_{d ∈ D^{(s_{k})}(n)} Φ_{d}(a)
= lcm_{k = 1,...,n}(a^{k} + s_{k}) = ℓ_{a,s}(n).  (9)

Therefore, putting together (7), (8), and (9), we get that

log ℓ_{a,s}(n) = log( ∏_{d ∈ L_{s}(n)} Φ_{d}(a)) + O(log ℓ_{a,s}^{(≤)}(n))

= log( ∏_{d ∈ L_{s}(n)} Φ_{d}(a)) + O_{a}(\frac{n^{2}}{log n})

= ∑_{d ∈ L_{s}(n)} φ(d) log a + O_{a}(#L_{s}(n)) + O_{a}(\frac{n^{2}}{log n}) ,

where we used Lemma 2. The claim follows since L_{s}(n) ⊆ [1, 2n] and so #L_{s}(n) ≤ 2n.

For all integers r ≥ 0 and m ≥ 1, and for every x ≥ 1, let us define the arithmetic progression

A_{r,m}(x) := {n ≤ x : n ≡ r (mod m)}.

We need an asymptotic formula for a sum of the Euler totient function over an arithmetic progression. Lemma 4. Let r, m be positive integers and let z ∈ [0, 1). Then we have

∑_{n ∈ A_{r,m}(x)} φ(n)(1 − z^{⌊x/n⌋}) = \frac{3}{π^{2}} · c_{r,m} · \frac{(1 − z) Li_{2}(z)}{z} · x^{2} + O_{r,m}(x(log x)^{2}),

for every x ≥ 2, where

c_{r,m} := \frac{1}{m} ∏_{\begin{matrix}p | m \\ p | r \end{matrix}} (1 + \frac{1}{p})^{−1} ∏_{\begin{matrix}p | m \\ p ∤ r \end{matrix}} (1 − \frac{1}{p^{2}} )^{−1} ,

while for z = 0 the factor involving Li_{2}(z) is meant to be equal to 1, and the error term can be improved to O_{r,m}(x log x). Proof. See [14, Lemma 3.4, Lemma 3.5].

4 Proof of Theorem 1

For all integers r, m ≥ 1, let us define the sets

T_{r,m}^{−} := {t ∈ {1, …, 2m} : ∃v ≥ 1 s.t. tv ≡ r (mod m)},
T_{r,m}^{+} := \{t ∈ \{1, …, 2m\} : 2 | t, ∃v ≥ 1 s.t. 2 ∤ v and \frac{t}{2}v ≡ r (mod m)\}

and the associated values

θ_{r,m}^{−}(t) := (min{v ≥ 1 : tv ≡ r (mod m)})^{−1}  for each t ∈ T_{r,m}^{−},
θ_{r,m}^{+}(t) := 2(min\{v ≥ 1 : 2 ∤ v and \frac{t}{2}v ≡ r (mod m)\})^{−1}  for each t ∈ T_{r,m}^{+}.

The next lemma regards unions of D^{−}(k), respectively D^{+}(k), with k ∈ A_{r,m}(x). Lemma 5. Let r, m ≥ 1 be integers and let u ∈ {−1, +1}. Then we have

⋃_{k ∈ A_{r,m}(x)} D^{(u)}(k) = ⋃_{t ∈ T_{r,m}^{(u)}} A_{t,2m}(θ_{r,m}^{(u)}(t)x),

for every x ≥ 1. Proof. For u = +1, the claim is [14, Lemma 3.3]. For u = −1, the claim is [14, Lemma 3.2], taking into account that A_{t,m}(x) = A_{t,2m}(x) ∪ A_{t+m,2m}(x). Proof of Theorem 1. Let s = (s_{n})_{n≥1} be a periodic sequence in {−1, +1}, and let m be the length of its period. Moreover, let R_{s}^{(u)} := {r ∈ {1, …, m} : s_{r} = u} for u ∈ {−1, +1}.

By periodicity of s and by Lemma 5, it follows that

L_{s}(n) = ⋃_{u ∈ {−1,+1}} ⋃_{r ∈ R_{s}^{(u)}} ⋃_{k ∈ A_{r,m}(n)} D^{(u)}(k)

= ⋃_{u ∈ {−1,+1}} ⋃_{r ∈ R_{s}^{(u)}} ⋃_{t ∈ T_{r,m}^{(u)}} A_{t,2m}(θ_{r,m}^{(u)}(t)n)

= ⋃_{t ∈ T_{s}} A_{t,2m}(θ_{s}(t)n)

where

T_{s} := ⋃_{u ∈ {−1,+1}} ⋃_{r ∈ R_{s}^{(u)}} T_{r,m}^{(u)} = ⋃_{r = 1}^{m} T_{r,m}^{(s_{r})}

and

θ_{s}(t) := max{θ_{r,m}^{(u)}(t) : t ∈ T_{r,m}^{(u)} for some u ∈ {−1, +1}, r ∈ R_{s}^{(u)}} .

Hence, from Lemma 3 and Lemma 4 (with z = 0), we get that

log ℓ_{a,s}(n) = ∑_{t ∈ T_{s}} ∑_{d ∈ A_{t,2m}(θ_{s}(t)n)} φ(d) log a + O_{a}(\frac{n^{2}}{log n})

= C_{s} · \frac{log a}{π^{2}} · n^{2} + O_{a,m}(\frac{n^{2}}{log n}) ,

where

C_{s} := 3 ∑_{t ∈ T_{s}} c_{t,2m}θ_{s}(t)^{2}

is a positive rational number effectively computable in terms of s_{1}, …, s_{m}. Example 1. Let s be the periodic sequence with period −1, +1, +1, +1 of length m = 4. We have

T_{1,4}^{−} = \{1, 3, 5, 7\},  θ_{1,4}^{−}(1) = 1, θ_{1,4}^{−}(3) = \frac{1}{3}, θ_{1,4}^{−}(5) = 1, θ_{1,4}^{−}(7) = \frac{1}{3},
T_{2,4}^{+} = {4},  θ_{2,4}^{+}(4) = 2,
T_{3,4}^{+} = \{2, 6\},  θ_{3,4}^{+}(2) = \frac{2}{3}, θ_{3,4}^{+}(6) = 2,
T_{4,4}^{+} = {8},  θ_{4,4}^{+}(8) = 2,

so that T_{s} = {1, 2, 3, 4, 5, 6, 7, 8} and

θ_{s}(1) = 1,  θ_{s}(2) = \frac{2}{3},  θ_{s}(3) = \frac{1}{3},  θ_{s}(4) = 2,
θ_{s}(5) = 1,  θ_{s}(6) = 2,  θ_{s}(7) = \frac{1}{3},  θ_{s}(8) = 2.

Moreover, c_{r,8} = \frac{1}{6} if r is odd, and c_{r,8} = \frac{1}{12} if r is even. Therefore, we have C_{s} = 3 · (\frac{1}{6} · 1^{2} + \frac{1}{12} · (\frac{2}{3})^{2} + \frac{1}{6} · (\frac{1}{3})^{2} + \frac{1}{12} · 2^{2} + \frac{1}{6} · 1^{2} + \frac{1}{12} · 2^{2} + \frac{1}{6} · (\frac{1}{3})^{2} + \frac{1}{12} · 2^{2}) = \frac{38}{9}.

5 Proof of Theorem 2

Let s = (s_{n})_{n≥1} be a sequence of independent and uniformly distributed random variables in {−1, +1}. Moreover, define

I_{s}(n, d) := \begin{cases}1, & if d ∈ L_{s}(n); \\ 0, & otherwise, \end{cases}

for all integers n, d ≥ 1. The next lemma gives two expected values involving I_{s}(n, d). Lemma 6. We have

𝔼[I_{s}(n, d)] = 1 − 2^{−⌊n(2,d)/d⌋}  (10)

and

𝔼[I_{s}(n, d_{1})I_{s}(n, d_{2})] = 1 − 2^{−⌊n(2,d_{1})/d_{1}⌋} − 2^{−⌊n(2,d_{2})/d_{2}⌋}

+ 2^{−⌊n(2,d_{1})/d_{1}⌋−⌊n(2,d_{2})/d_{2}⌋+⌊n(2,[d_{1},d_{2}])/[d_{1},d_{2}]⌋} \begin{cases}1, & if ν_{2}(d_{1}) = ν_{2}(d_{2}); \\ 0, & otherwise, \end{cases}

for all integers d, d_{1}, d_{2} ≥ 1.

Proof. On the one hand, by the definitions of I_{s}(n, d) and L_{s}(n), we have

𝔼[I_{s}(n, d)] = ℙ[d ∈ L_{s}(n)] = 1 − ℙ[ ⋀_{k ≤ n} (d ∉ D^{(s_{k})}(k))] = 1 − ℙ[ ⋀_{\begin{matrix}k ≤ n \\ d | 2k \end{matrix}} (d ∉ D^{(s_{k})}(k))]

= 1 − ℙ[ ⋀_{\begin{matrix}k ≤ n \\ d | 2k \end{matrix}} ((d | k ∧ s_{k} = +1) ∨ (d ∤ k ∧ s_{k} = −1))] = 1 − 2^{−#\{k ≤ n: d | 2k\}}

= 1 − 2^{−⌊n(2,d)/d⌋},

which is (10).

On the other hand, by linearity of the expectation and by (10), we have

𝔼[I_{s}(n, d_{1})I_{s}(n, d_{2})] = 𝔼[I_{s}(n, d_{1}) + I_{s}(n, d_{2}) − 1 + (1 − I_{s}(n, d_{1}))(1 − I_{s}(n, d_{2}))]

= 𝔼[I_{s}(n, d_{1})] + 𝔼[I_{s}(n, d_{2})] − 1 + 𝔼[(1 − I_{s}(n, d_{1}))(1 − I_{s}(n, d_{2}))]

= 1 − 2^{−⌊n(2,d_{1})/d_{1}⌋} − 2^{−⌊n(2,d_{2})/d_{2}⌋} + ℙ[d_{1} ∉ L_{s}(n) ∧ d_{2} ∉ L_{s}(n)]. (11)

Let P be the probability at the end of (11).

Suppose for a moment that [d_{1}, d_{2}] ≤ 2n and that d_{1} and d_{2} have different 2-adic valuations, say ν_{2}(d_{1}) < ν_{2}(d_{2}), without loss of generality. Let h := [d_{1}, d_{2}]/2 and note that h is an integer not exceeding n. Furthermore, d_{1} ∈ D^{−}(h) and d_{2} ∈ D^{+}(h). Hence, no matter the value of s_{h}, at least one of d_{1}, d_{2} belongs to L_{s}(n), and consequently P = 0.

Now suppose that [d_{1}, d_{2}] > 2n or ν_{2}(d_{1}) = ν_{2}(d_{2}). In the second case, note that for every integer k such that [d_{1}, d_{2}] | 2k we have that either d_{1} | k and d_{2} | k, or d_{1} ∤ k and d_{2} ∤ k.

Therefore,

P = ℙ[ ⋀_{\begin{matrix}k ≤ n \\ d_{1} | 2k ∧ d_{2} ∤ 2k \end{matrix}} ((d_{1} | k ∧ s_{k} = +1) ∨ (d_{1} ∤ k ∧ s_{k} = −1))

∧ ⋀_{\begin{matrix}k ≤ n \\ d_{1} ∤ 2k ∧ d_{2} | 2k \end{matrix}} ((d_{2} | k ∧ s_{k} = +1) ∨ (d_{2} ∤ k ∧ s_{k} = −1))

∧ ⋀_{\begin{matrix}k ≤ n \\ d_{1} | 2k ∧ d_{2} | 2k \end{matrix}} ((d_{1} | k ∧ d_{2} | k ∧ s_{k} = +1) ∨ (d_{1} ∤ k ∧ d_{2} ∤ k ∧ s_{k} = −1))]

= 2^{−#{k ≤ n: d_{1} | 2k ∨ d_{2} | 2k}}
= 2^{−⌊n(2,d_{1})/d_{1}⌋−⌊n(2,d_{2})/d_{2}⌋+⌊n(2,[d_{1},d_{2}])/[d_{1},d_{2}]⌋},

and the proof is complete.

The following lemma is a simple upper bound for a sum of greatest common divisors. Lemma 7. We have

∑_{[d_{1}, d_{2}] ≤ n}(d_{1}, d_{2}) ≪ n^{2},

for every integer n ≥ 1. Proof. Let a_{i} := d_{i}/d for i = 1, 2, where d := (d_{1}, d_{2}). Then we have

∑_{[d_{1}, d_{2}] ≤ n}(d_{1}, d_{2}) = ∑_{d ≤ n} d ∑_{\begin{matrix}a_{1}a_{2} ≤ n/d \\ (a_{1}, a_{2}) = 1 \end{matrix}} 1 ≤ ∑_{d ≤ n} d ∑_{m ≤ n/d} τ(m)

≪ n ∑_{d ≤ n} log(\frac{n}{d}) = n (n log n − log(n!)) < n^{2},

where we used the upper bound ∑_{m≤x} τ(m) ≪ x log x (see, e.g., [15, Ch. I.3, Theorem 3.2]) and the inequality n! > (n/e)^{n}. Proof of Theorem 2. Let us define the random variable

X := ∑_{d ≤ 2n} φ(d) I_{s}(n, d).

From the linearity of expectation, Lemma 6, and Lemma 4, it follows that

𝔼[X] := ∑_{d ≤ 2n} φ(d) 𝔼[I_{s}(n, d)]

= ∑_{d ≤ 2n} φ(d) (1 − 2^{−⌊n(2,d)/d⌋})

= ∑_{d ∈ A_{1,2}(n)} φ(d) (1 − 2^{−⌊n/d⌋}) + ∑_{d ∈ A_{2,2}(2n)} φ(d) (1 − 2^{−⌊2n/d⌋})

= \frac{3}{π^{2}} (c_{1,2} + 4c_{2,2}) Li_{2}(\frac{1}{2}) n^{2} + O(n(log n)^{2})

= \frac{6}{π^{2}} Li_{2}(\frac{1}{2}) n^{2} + O(n(log n)^{2}).  (12)

Furthermore, from Lemma 6 and Lemma 7, we get that

𝕍[X] = 𝔼[X^{2}] − 𝔼[X]^{2}

= ∑_{d_{1}, d_{2} ≤ 2n} φ(d_{1}) φ(d_{2})(𝔼[I_{s}(n, d_{1})I_{s}(n, d_{2})] − 𝔼[I_{s}(n, d_{1})]𝔼[I_{s}(n, d_{2})])

≤ ∑_{[d_{1}, d_{2}] ≤ 2n} d_{1}d_{2} 2^{−⌊n(2,d_{1})/d_{1}⌋−⌊n(2,d_{2})/d_{2}⌋+⌊n(2,[d_{1},d_{2}])/[d_{1},d_{2}]⌋} (1 − 2^{−⌊n(2,[d_{1},d_{2}])/[d_{1},d_{2}]⌋})

≤ ∑_{[d_{1}, d_{2}] ≤ 2n} d_{1}d_{2} ⌊\frac{n(2, [d_{1}, d_{2}])}{[d_{1}, d_{2}]}⌋ ≪ n ∑_{[d_{1}, d_{2}] ≤ 2n}(d_{1}, d_{2}) ≪ n^{3},  (13)

where we also used the inequality 1 − 2^{−k} ≤ k/2, which holds for every integer k ≥ 0. Therefore, by Chebyshev’s inequality, (12), and (13), it follows that

ℙ[|X − 𝔼[X]| > ε 𝔼[X]] ≤ \frac{𝕍[X]}{(ε𝔼[X])^{2}} ≪ \frac{1}{ε^{2}n} = o_{ε}(1),

as n → +∞. Hence, again by (12), we have

X ∼ 𝔼[X] ∼ \frac{6}{π^{2}} Li_{2}(\frac{1}{2})n^{2},

with probability 1 − o(1). Finally, thanks to Lemma 3, we have

log ℓ_{a,s}(n) = X log a + O_{a}(\frac{n^{2}}{log n}) ,

and the asymptotic formula (4) follows.

6 Acknowledgments

The author is grateful to the anonymous referee for providing many suggestions that improved the quality of the paper. The author is a member of GNSAGA of INdAM and of CrypTO, the group of Cryptography and Number Theory of Politecnico di Torino.

References

[1] S. Akiyama, Lehmer numbers and an asymptotic formula for π, J. Number Theory 36 (1990), 328–331.

[2] S. Akiyama, A new type of inclusion exclusion principle for sequences and asymptotic formulas for ζ(k), J. Number Theory 45 (1993), 200–214.

[3] S. Akiyama, A criterion to estimate the least common multiple of sequences and asymptotic formulas for ζ(3) arising from recurrence relation of an elliptic function, Japan. J. Math. (N.S.) 22 (1996), 129–146.

[4] S. Akiyama and F. Luca, On the least common multiple of Lucas subsequences, Acta Arith. 161 (2013), 327–349.

[5] G. Alsmeyer, Z. Kabluchko, and A. Marynych, Limit theorems for the least common multiple of a random set of integers, Trans. Amer. Math. Soc. 372 (2019), 4585–4603.

[6] J.-P. Bézivin, Plus petit commun multiple des termes consécutifs d’une suite récurrente linéaire, Collect. Math. 40 (1989), 1–11 (1990).

[7] J. Cilleruelo, J. Rué, P. Šarka, and A. Zumalacárregui, The least common multiple of random sets of positive integers, J. Number Theory 144 (2014), 92–104.

[8] J. P. Jones and P. Kiss, An asymptotic formula concerning Lehmer numbers, Publ. Math. Debrecen 42 (1993), 199–213.

[9] P. Kiss and F. Mátyás, An asymptotic formula for π, J. Number Theory 31 (1989), 255–259.

[10] Y. V. Matiyasevich and R. K. Guy, A new formula for π, Amer. Math. Monthly 93 (1986), 631–635.

[11] C. Sanna, Practical numbers in Lucas sequences, Quaest. Math. 42 (2019), 977–983.

[12] C. Sanna, On the l.c.m. of random terms of binary recurrence sequences, J. Number Theory 213 (2020), 221–231.

[13] C. Sanna, On the least common multiple of random q-integers, Res. Number Theory 7 (2021), 16.

[14] C. Sanna, On the l.c.m. of shifted Fibonacci numbers, Int. J. Number Theory (in press)

https://doi.org/10.1142/S1793042121500743.

[15] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, 3rd edition, Vol. 163 of Graduate Studies in Mathematics, American Mathematical Society, 2015.

[16] B. Tropak, Some asymptotic properties of Lucas numbers, In Proceedings of the Regional Mathematical Conference (Kalsk, 1988), pp. 49–55. Pedagog. Univ. Zielona Góra, 1990.

[17] D. Zagier, The dilogarithm function. In Frontiers in Number Theory, Physics, and Geometry. II, pp. 3–65. Springer, 2007.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B37, 11N37. Keywords: asymptotic formula, least common multiple, power.

Received March 24 2021; revised versions received May 22 2021; June 12 2021. Published June 12 2021.

Return to Journal of Integer Sequences home page.