\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{booktabs}
\usepackage{cite}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

% Custom commands
\DeclareMathOperator*{\lcm}{lcm}
\DeclareMathOperator{\Li}{Li}
\uchyph=0

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{conjecture}{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{question}{Question}

\begin{center}
\vskip 1cm{\LARGE\bf 
On the Least Common Multiple of 
\vskip .1in
Shifted Powers
}
\vskip 1cm
\large
Carlo Sanna \\
Politecnico di Torino \\
Department of Mathematical Sciences \\
Corso Duca degli Abruzzi 24\\
10129 Torino \\
Italy \\
\href{mailto:carlo.sanna.dev@gmail.com}{\tt carlo.sanna.dev@gmail.com} \\
\end{center}

\vskip .2 in

\begin{abstract} 
We determine the asymptotic behavior of $\log\lcm(a + s_1, a^2 + s_2, \dots, a^n + s_n)$, for $a \geq 2$ an integer and $(s_n)_{n \geq 1}$ a periodic sequence in $\{-1, +1\}$.
We also carry out the same analysis for $(s_n)_{n \geq 1}$ a sequence of independent and uniformly distributed random variables in $\{-1, +1\}$.
\end{abstract}

\section{Introduction}

Let $(F_n)_{n \geq 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 \geq 1$.
Matiyasevich and Guy~\cite{MR1712797} proved that
\begin{equation*}
\log \lcm (F_1, F_2, \dots, F_n) \sim \frac{3 \log\!\left(\tfrac{1 + \sqrt{5}}{2}\right)}{\pi^2} \cdot n^2 ,
\end{equation*}
as $n \to +\infty$, where $\lcm$ denotes the least common multiple.
This result was generalized to Lucas sequences, Lehmer sequences, and other sequences with special divisibility properties~\cite{MR1077711, MR1242715, MR1394375, MR3150887, MR1078087, MR1229668, MR993902, MR1114366}.
In~particular, for every integer $a \geq 2$ we have
\begin{equation}\label{equ:plus-formula}
\log\lcm(a - 1, a^2 - 1, \dots, a^n - 1) \sim \frac{3 \log a}{\pi^2} \cdot n^2
\end{equation}
and
\begin{equation}\label{equ:minus-formula}
\log\lcm(a + 1, a^2 + 1, \dots, a^n + 1) \sim \frac{4 \log a}{\pi^2} \cdot n^2 ,
\end{equation}
as $n \to +\infty$.
More precisely, \eqref{equ:plus-formula} follows from~\cite[Lemma~3]{MR993902} applied to the Lucas sequence $\left(\frac{a^n - 1}{a - 1}\right)_{n \geq 1}$, while \eqref{equ:minus-formula} follows from~\cite[Th\'eor\`eme, p.~2]{MR1078087} applied to the companion Lucas sequence $(a^n + 1)_{n \geq 1}$.

We generalize \eqref{equ:plus-formula} and \eqref{equ:minus-formula} by giving asymptotic formulas for least common multiples of sequences of \emph{shifted powers} $(a^n + s_n)_{n \geq 1}$, where $(s_n)_{n \geq 1}$ is a sequence of \emph{shifts} in $\{-1, +1\}$.
This is somehow similar to a previous work of the author~\cite{PreprintSanna0}, in which least common multiples of the sequence of shifted Fibonacci numbers $(F_n + s_n)_{n \geq 1}$ were studied.

Our first result regards periodic sequences of shifts.

\begin{theorem}\label{thm:periodic}
Let $a \geq 2$ be an integer and let $\mathbf{s} = (s_n)_{n \geq 1}$ be a periodic sequence in $\{-1, +1\}$.
Then there exists an effectively computable rational number $C_\mathbf{s} > 0$ such that
\begin{equation}\label{equ:periodic}
\log\lcm(a + s_1, a^2 + s_2, \dots, a^n + s_n) \sim C_\mathbf{s} \cdot \frac{\log a}{\pi^2} \cdot n^2 ,
\end{equation}
as $n \to +\infty$.
\end{theorem}

By ``effectively computable'' we mean that there exists an algorithm that, given as input the period of the periodic sequence $\mathbf{s}$, returns as output the numerator and denominator of the rational number $C_\mathbf{s}$.
Indeed, we implemented such algorithm and we computed the constant $C_\mathbf{s}$ for periodic sequences with short period, see Table~\ref{tab:sCs}.

\begin{table}[h]
\begin{center}
\begin{tabular}{cc|cc|cc|cc}
  \toprule
  $\mathbf{s}$ & $C_{\mathbf{s}}$ & $\mathbf{s}$ & $C_{\mathbf{s}}$ & $\mathbf{s}$ & $C_{\mathbf{s}}$ & $\mathbf{s}$ & $C_{\mathbf{s}}$ \\\hline
  \texttt{-} & $3$ & \texttt{-+--} & $27/8$ & \texttt{--+-+} & $319/96$ & \texttt{+--+-} & $733/216$\rule{0pt}{2.6ex}\\
  \texttt{+} & $4$ & \texttt{-++-} & $125/36$ & \texttt{--++-} & $487/144$ & \texttt{+--++} & $769/216$\\
  \texttt{-+} & $4$ & \texttt{-+++} & $38/9$ & \texttt{--+++} & $7687/2160$ & \texttt{+-+--} & $487/144$\\
  \texttt{+-} & $3$ & \texttt{+---} & $3$ & \texttt{-+---} & $101/32$ & \texttt{+-+-+} & $7687/2160$\\
  \texttt{--+} & $13/4$ & \texttt{+--+} & $7/2$ & \texttt{-+--+} & $319/96$ & \texttt{+-++-} & $2123/576$\\
  \texttt{-+-} & $105/32$ & \texttt{+-++} & $7/2$ & \texttt{-+-+-} & $487/144$ & \texttt{+-+++} & $2219/576$\\
  \texttt{-++} & $173/48$ & \texttt{++--} & $125/36$ & \texttt{-+-++} & $7687/2160$ & \texttt{++---} & $487/144$\\
  \texttt{+--} & $105/32$ & \texttt{++-+} & $38/9$ & \texttt{-++--} & $733/216$ & \texttt{++--+} & $7687/2160$\\
  \texttt{+-+} & $173/48$ & \texttt{+++-} & $27/8$ & \texttt{-++-+} & $769/216$ & \texttt{++-+-} & $2123/576$\\
  \texttt{++-} & $47/12$ & \texttt{----+} & $19/6$ & \texttt{-+++-} & $2123/576$ & \texttt{++-++} & $2219/576$\\
  \texttt{---+} & $7/2$ & \texttt{---+-} & $101/32$ & \texttt{-++++} & $2219/576$ & \texttt{+++--} & $2123/576$\\
  \texttt{--+-} & $3$ & \texttt{---++} & $319/96$ & \texttt{+----} & $101/32$ & \texttt{+++-+} & $2219/576$\\
  \texttt{--++} & $7/2$ & \texttt{--+--} & $101/32$ & \texttt{+---+} & $319/96$ & \texttt{++++-} & $39/10$\\
  \bottomrule
\end{tabular}
\end{center}
\caption{Values of $C_\mathbf{s}$ for periodic sequences $\mathbf{s}$ of period at most $5$.}
\label{tab:sCs}
\end{table}

Our second result is an asymptotic formula for random sequences of shifts (see~\cite{MR4091939, MR4220046, MR3239153, MR4009436} for similar results on least common multiples of random sequences). 

\begin{theorem}\label{thm:random}
Let $a \geq 2$ be an integer and let $(s_n)_{n \geq 1}$ be a sequence of independent and uniformly distributed random variables in $\{-1, +1\}$.
Then
\begin{equation}\label{equ:random}
\log\lcm(a + s_1, a^2 + s_2, \dots, a^n + s_n) \sim 6 \Li_2\!\big(\tfrac1{2}\big) \cdot \frac{\log a}{\pi^2} \cdot n^2 ,
\end{equation}
with probability $1 - o(1)$, as $n \to +\infty$, where $\Li_2(z) := \sum_{k = 1}^\infty z^k / k^2$ is the dilogarithm function. 
\end{theorem}

\begin{remark}
It is known that $\Li_2\!\big(\tfrac1{2}\big) = \big(\pi^2 - 6(\log 2)^2\big) / 12$ (see, e.g.,~\cite{MR2290758}), but in~\eqref{equ:random} we preferred to keep explicit the factor $6 \Li_2\!\big(\tfrac1{2}\big)$ in order to ease the comparison with~\eqref{equ:plus-formula}, \eqref{equ:minus-formula}, and~\eqref{equ:periodic}.
Numerically, we have $6 \Li_2\!\big(\tfrac1{2}\big) = 3.493443\dots$ so that the right-hand side of~\eqref{equ:random} is a bit less than the arithmetic mean of the right-hand sides of~\eqref{equ:plus-formula} and~\eqref{equ:minus-formula}.
\end{remark}

We leave the following questions to the interested reader:
\begin{question}\label{que:limit}
Is there a simple characterization of the set $\mathcal{E}$ of sequences $\mathbf{s} = (s_n)_{n \geq 1}$ in $\{-1, +1\}$ such that the limit
\begin{equation*}
L(\mathbf{s}) := \lim_{n \to +\infty} \frac{\log\lcm(a + s_1, a^2 + s_2, \dots, a^n + s_n)}{(\log a / \pi^2) \cdot n^2}
\end{equation*}
exists? (It follows from Lemma~\ref{lem:logellsn} below that $L(\mathbf{s})$ does not depend on $a$.)
\end{question}

\begin{question}
What is the image $L(\mathcal{E})$?
\end{question}

\begin{question}
Does (an appropriate normalization of) the random variable on the left-hand side of~\eqref{equ:random} converge to some known distribution?
\end{question}

\section{Notation}

We employ the Landau-Bachmann ``Big Oh'' and ``little oh'' notations $O$ and $o$, as well as the associated Vinogradov symbol $\ll$, with their usual meanings.
For real random variables $X_n$ and $Y_n$, depending on $n$, we say that ``$X_n \sim Y_n$ with probability $1 - o(1)$ as $n \to +\infty$'' if for every $\varepsilon > 0$ we have $\mathbb{P}\big[|X_n - Y_n| > \varepsilon|Y_n|\big] = o_\varepsilon(1)$ as $n \to +\infty$.
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 $\nu_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 $\varphi(n)$ and $\tau(n)$ for the Euler function and the number of positive divisors, respectively, of a natural number $n$.

\section{Preliminaries}

Hereafter, let $a \geq 2$ be a fixed integer.
Define the \emph{$n$th cyclotomic polynomial} by
\begin{equation}\label{equ:cyclo}
\Phi_n(X) := \prod_{\substack{1 \,\leq\, k \,\leq\, n \\ (n, k) \,=\, 1}} \left(X - \mathrm{e}^{\frac{2 \pi \mathbf{i} k}{n}}\right) ,
\end{equation}
for every integer $n \geq 1$.
It is well known that $\Phi_n(X) \in \mathbb{Z}[X]$.
Moreover, from~\eqref{equ:cyclo} we get that
\begin{equation}\label{equ:shiftedan}
a^n - 1 = \prod_{d \,\in\, \mathcal{D}^-(n)} \Phi_d(a) \quad \text{ and } \quad a^n + 1 = \prod_{d \,\in\, \mathcal{D}^+(n)} \Phi_d(a) ,
\end{equation}
for every integer $n \geq 1$, where $\mathcal{D}^-(n) := \{d \in \mathbb{N} : d \mid n\}$ and $\mathcal{D}^+(n) := \mathcal{D}^-(2n) \setminus \mathcal{D}^-(n)$.

We need two results about the sequence of integers $(\Phi_d(a))_{d \in \mathbb{N}}$.

\begin{lemma}\label{lem:gcdPhi}
We have $(\Phi_m(a), \Phi_n(a)) \mid m$, for all integers $m > n \geq 1$.
\end{lemma}
\begin{proof}
Let $d := (\Phi_m(a), \Phi_n(a))$.
By~\eqref{equ:shiftedan} we have that $d$ divides $(a^m - 1, a^n - 1) = a^{(m, n)} - 1$.
Moreover, since $(m, n) < m$, by~\eqref{equ:shiftedan} again we have that
\begin{equation*}
d \mid \Phi_m(a) \mid \frac{a^m - 1}{a^{(m, n)} - 1} \equiv 1 + a^{(m,n)} + \big(a^{(m,n)}\big)^2 + \cdots + \big(a^{(m,n)}\big)^{\frac{m}{(m, n)} - 1} \equiv \frac{m}{(m, n)} \!\!\!\!\pmod d .
\end{equation*}
Consequently, $d$ divides $m / (m, n)$ and, a fortiori, $d$ divides $m$.
\end{proof}

\begin{lemma}\label{lem:asympPhi}
We have $\log \Phi_n(a) = \varphi(n) \log a + O_a(1)$, for every integer $n \geq 1$.
\end{lemma}
\begin{proof}
See~\cite[Lemma~2.1(iii)]{MR4003803}.
\end{proof}

For every sequence $\mathbf{s} = (s_n)_{n \geq 1}$ in $\{-1, +1\}$, let us define
\begin{equation*}
\ell_{a,\mathbf{s}}(n) := \lcm(a + s_1, a^2 + s_2, \dots, a^n + s_n) 
\end{equation*}
and
\begin{equation*}
\mathcal{L}_\mathbf{s}(n) := \bigcup_{k \,\leq\, n} \mathcal{D}^{(s_k)}(k) ,
\end{equation*}
for all integers $n \geq 1$.

The next lemma will be fundamental in the proofs of Theorem~\ref{thm:periodic} and Theorem~\ref{thm:random}.

\begin{lemma}\label{lem:logellsn}
We have
\begin{equation*}
\log \ell_{a,\mathbf{s}}(n) = \sum_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \varphi(d) \log a + O_a\!\left(\frac{n^2}{\log n}\right) ,
\end{equation*}
for every integer $n \geq 2$.
\end{lemma}
\begin{proof}
For every integer $m \geq 1$, write $m = m^{(\leq)} \cdot m^{(>)}$, where $m^{(\leq)}$, respectively $m^{(>)}$, is a positive integer having all the prime factors not exceeding $2n$, respectively greater than $2n$.

Suppose that $p^v \mid\mid \ell_{a,\mathbf{s}}(n)$, for some prime number $p \leq 2n$ and some integer $v \geq 1$.
Then $p^v \mid a^k + s_k$ for some positive integer $k \leq n$, and consequently $p^v \leq a^{n + 1}$.
Therefore,
\begin{align}\label{equ:smallprimes}
\log \ell_{a,\mathbf{s}}^{(\leq)}(n) &= \log\!\Big(\prod_{\substack{p^v \,\mid\mid\, \ell_{a,\mathbf{s}}(n) \\ p \,\leq\, 2n}} p^v \Big) \leq \log\!\Big(\prod_{\substack{p^v \,\mid\mid\, \ell_{a,\mathbf{s}}(n) \\ p \,\leq\, 2n}} a^{n + 1} \Big) \nonumber \\
 &\leq \#\{p : p \leq 2n\} \cdot (n + 1) \log a \ll_a \frac{n^2}{\log n} , 
\end{align}
since the number of primes not exceeding $2n$ is $O(n / \!\log n)$.

On the one hand, in light of Lemma~\ref{lem:gcdPhi}, the integers $\Phi_1^{(>)}(a), \dots, \Phi_{2n}^{(>)}(a)$ are pairwise coprime.
Hence, also using~\eqref{equ:shiftedan}, we have
\begin{align}\label{equ:ellasgreater1}
\ell_{a,\mathbf{s}}^{(>)}(n) &= \lcm_{k \,=\, 1,\dots,n} (a^k + s_k)^{(>)} = \lcm_{k \,=\, 1,\dots,n} \prod_{d \,\in\, \mathcal{D}^{(s_k)}(n)} \Phi_d^{(>)}(a) \nonumber\\
 &= \lcm_{k \,=\, 1,\dots,n} \; \lcm_{d \,\in\, \mathcal{D}^{(s_k)}(n)} \Phi_d^{(>)}(a) = \lcm_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \Phi_d^{(>)}(a) \mid \lcm_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \Phi_d(a) .
\end{align}
On the other hand, using~\eqref{equ:shiftedan} again, we have
\begin{align}\label{equ:ellasgreater2}
\lcm_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \Phi_d(a) &= \lcm_{k \,=\, 1,\dots,n} \; \lcm_{d \,\in\, \mathcal{D}^{(s_k)}(n)} \Phi_d(a) \mid \lcm_{k \,=\, 1,\dots,n} \; \prod_{d \,\in\, \mathcal{D}^{(s_k)}(n)} \Phi_d(a) \nonumber\\
 &= \lcm_{k \,=\, 1,\dots,n} (a^k + s_k) = \ell_{a,\mathbf{s}}(n) .
\end{align}
Therefore, putting together~\eqref{equ:smallprimes},~\eqref{equ:ellasgreater1}, and~\eqref{equ:ellasgreater2}, we get that
\begin{align*}
\log \ell_{a,\mathbf{s}}(n) &= \log\!\Big(\prod_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \Phi_d(a) \Big) + O\!\left(\log \ell_{a,\mathbf{s}}^{(\leq)}(n)\right) \\
 &= \log\!\Big(\prod_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \Phi_d(a) \Big) + O_a\!\left(\frac{n^2}{\log n}\right) \\
 &= \sum_{d \,\in\, \mathcal{L}_\mathbf{s}(n)} \varphi(d)\log a + O_a(\#\mathcal{L}_\mathbf{s}(n)) + O_a\!\left(\frac{n^2}{\log n}\right) ,
\end{align*}
where we used Lemma~\ref{lem:asympPhi}.
The claim follows since $\mathcal{L}_\mathbf{s}(n) \subseteq [1, 2n]$ and so $\#\mathcal{L}_\mathbf{s}(n) \leq 2n$.
\end{proof}

For all integers $r \geq 0$ and $m \geq 1$, and for every $x \geq 1$, let us define the arithmetic progression
\begin{equation*}
\mathcal{A}_{r, m}(x) := \big\{n \leq x : n \equiv r \!\!\!\!\pmod m\big\} .
\end{equation*}
We need an asymptotic formula for a sum of the Euler totient function over an arithmetic progression.

\begin{lemma}\label{lem:phisum}
Let $r, m$ be positive integers and let $z \in {[0, 1)}$.
Then we have
\begin{equation*}
\sum_{n \,\in\, \mathcal{A}_{r,m}(x)} \varphi(n)\big(1 - z^{\lfloor x / n \rfloor}\big) = \frac{3}{\pi^2} \cdot c_{r,m} \cdot \frac{(1 - z) \Li_2(z)}{z} \cdot x^2 + O_{r,m}\big(x (\log x)^2\big) ,
\end{equation*}
for every $x \geq 2$, where
\begin{equation*}
c_{r, m} := \frac1{m} \prod_{\substack{p \,\mid\, m \\ \!\!p \,\mid\, r}} \left(1 + \frac1{p}\right)^{-1} \prod_{\substack{p \,\mid\, m \\ \!\! p \,\nmid\, r}} \left(1 - \frac1{p^2}\right)^{-1} ,
\end{equation*}
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)$. 
\end{lemma}
\begin{proof}
See~\cite[Lemma~3.4, Lemma~3.5]{PreprintSanna0}.
\end{proof}

\section{Proof of Theorem~\ref{thm:periodic}}

For all integers $r, m \geq 1$, let us define the sets
\begin{align*}
\mathcal{T}_{r,m}^{-} &:= \big\{t \in \{1,\dots,2m\} : \exists v \geq 1\text{ s.t. } tv \equiv r \!\!\!\pmod m \big\} , \\
\mathcal{T}_{r,m}^{+} &:= \big\{t \in \{1,\dots,2m\} : 2 \mid t,\, \exists v \geq 1\text{ s.t. } 2 \nmid v \text{ and } \tfrac{t}{2}v \equiv r \!\!\!\pmod m \big\}
\end{align*}
and the associated values
\begin{align*}
\theta_{r,m}^{-}(t) &:= \big(\!\min\{v \geq 1 : tv \equiv r \!\!\!\pmod m\}\big)^{-1} &\text{ for each } t &\in \mathcal{T}_{r,m}^{-} , \\
\theta_{r,m}^{+}(t) &:= 2\big(\!\min\{v \geq 1 : 2 \nmid v \text{ and } \tfrac{t}{2}v \equiv r \!\!\!\pmod m\}\big)^{-1} &\text{ for each } t &\in \mathcal{T}_{r,m}^{+} .
\end{align*}
The next lemma regards unions of $\mathcal{D}^-(k)$, respectively $\mathcal{D}^+(k)$, with $k \in \mathcal{A}_{r, m}(x)$.

\begin{lemma}\label{lem:Dunions}
Let $r, m \geq 1$ be integers and let $u \in \{-1, +1\}$.
Then we have
\begin{equation*}
\bigcup_{k \,\in\, \mathcal{A}_{r,m}(x)} \mathcal{D}^{(u)}(k) = \bigcup_{t \,\in\, \mathcal{T}_{r,m}^{(u)}} \mathcal{A}_{t, 2m}\big(\theta_{r,m}^{(u)}(t) x\big) ,
\end{equation*}
for every $x \geq 1$.
\end{lemma}
\begin{proof}
For $u = +1$, the claim is~\cite[Lemma~3.3]{PreprintSanna0}.
For $u = -1$, the claim is\cite[Lemma~3.2]{PreprintSanna0}, taking into account that $\mathcal{A}_{t, m}(x) = \mathcal{A}_{t, 2m}(x) \cup \mathcal{A}_{t + m, 2m}(x)$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:periodic}]
Let $\mathbf{s} = (s_n)_{n \geq 1}$ be a periodic sequence in $\{-1, +1\}$, and let $m$ be the length of its period.
Moreover, let $\mathcal{R}_\mathbf{s}^{(u)} := \{r \in \{1, \dots, m\} : s_r = u\}$ for $u \in \{-1, +1\}$.

By periodicity of $\mathbf{s}$ and by Lemma~\ref{lem:Dunions}, it follows that
\begin{align*}
\mathcal{L}_\mathbf{s}(n) &= \bigcup_{u \,\in\, \{-1, +1\}} \bigcup_{r \,\in\, \mathcal{R}_\mathbf{s}^{(u)}} \bigcup_{k \,\in\, \mathcal{A}_{r,m}(n)} \mathcal{D}^{(u)}(k) \\
 &= \bigcup_{u \,\in\, \{-1, +1\}} \bigcup_{r \,\in\, \mathcal{R}_\mathbf{s}^{(u)}} \bigcup_{t \,\in\, \mathcal{T}_{r, m}^{(u)}} \mathcal{A}_{t, 2m}\big(\theta_{r,m}^{(u)}(t)n\big) \\
 &= \bigcup_{t \,\in\, \mathcal{T}_\mathbf{s}} \mathcal{A}_{t, 2m}\big(\theta_{\mathbf{s}}(t) n\big)
\end{align*}
where
\begin{equation*}
\mathcal{T}_\mathbf{s} := \bigcup_{u \,\in\, \{-1, +1\}} \bigcup_{r \,\in\, \mathcal{R}_\mathbf{s}^{(u)}} \mathcal{T}_{r, m}^{(u)} = \bigcup_{r \,=\, 1}^m \mathcal{T}_{r, m}^{(s_r)}
\end{equation*}
and
\begin{equation*}
\theta_{\mathbf{s}}(t) := \max\!\left\{\theta_{r,m}^{(u)}(t) : t \in \mathcal{T}_{r, m}^{(u)} \text{ for some } u \in \{-1, +1\}, \, r \in \mathcal{R}_\mathbf{s}^{(u)} \right\} .
\end{equation*}
Hence, from Lemma~\ref{lem:logellsn} and Lemma~\ref{lem:phisum} (with $z = 0$), we get that
\begin{align*}
\log \ell_{a,\mathbf{s}}(n) &= \sum_{t \,\in\, \mathcal{T}_\mathbf{s}} \; \sum_{d \,\in\, \mathcal{A}_{t, 2m}(\theta_{\mathbf{s}}(t) n)} \varphi(d) \log a + O_a\!\left(\frac{n^2}{\log n}\right) \\
&= C_\mathbf{s} \cdot \frac{\log a}{\pi^2} \cdot n^2 + O_{a, m}\!\left(\frac{n^2}{\log n}\right) ,
\end{align*}
where
\begin{equation*}
C_\mathbf{s} := 3 \sum_{t \,\in\, \mathcal{T}_\mathbf{s}} c_{t, 2m} \theta_{\mathbf{s}}(t)^2 
\end{equation*}
is a positive rational number effectively computable in terms of $s_1, \dots, s_m$.
\end{proof}

\begin{example}
Let $\mathbf{s}$ be the periodic sequence with period $-1, +1, +1, +1$ of length $m = 4$.
We have
\begin{align*}
\mathcal{T}_{1,4}^{-} &= \{1, 3, 5, 7\}, &\quad \theta_{1,4}^{-}(1) &= 1, \quad \theta_{1,4}^{-}(3) = \tfrac1{3}, \quad \theta_{1,4}^{-}(5) = 1, \quad \theta_{1,4}^{-}(7) = \tfrac1{3} , \\
\mathcal{T}_{2,4}^{+} &= \{4\}, &\quad \theta_{2,4}^{+}(4) &= 2 , \\
\mathcal{T}_{3,4}^{+} &= \{2, 6\}, &\quad \theta_{3,4}^{+}(2) &= \tfrac{2}{3}, \quad \theta_{3,4}^{+}(6) = 2 , \\
\mathcal{T}_{4,4}^{+} &= \{8\}, &\quad \theta_{4,4}^{+}(8) &= 2 ,
\end{align*}
so that $\mathcal{T}_{\mathbf{s}} = \{1, 2, 3, 4, 5, 6, 7, 8\}$ and
\begin{align*}
\theta_{\mathbf{s}}(1) &= 1, &\quad \theta_{\mathbf{s}}(2) &= \tfrac{2}{3}, &\quad \theta_{\mathbf{s}}(3) &= \tfrac1{3}, &\quad \theta_{\mathbf{s}}(4) &= 2 , \\
\theta_{\mathbf{s}}(5) &= 1, &\quad \theta_{\mathbf{s}}(6) &= 2, &\quad \,\theta_{\mathbf{s}}(7) &= \tfrac1{3}, &\quad \theta_{\mathbf{s}}(8) &= 2 .
\end{align*}
Moreover, $c_{r, 8} = \tfrac1{6}$ if $r$ is odd, and $c_{r, 8} = \tfrac1{12}$ if $r$ is even.
Therefore, we have
\begin{equation*}
C_\mathbf{s} = 3\cdot \left(\tfrac1{6}\cdot 1^2 + \tfrac1{12}\cdot\left(\tfrac{2}{3}\right)^2 + \tfrac1{6}\cdot\left(\tfrac1{3}\right)^2 + \tfrac1{12}\cdot 2^2 + \tfrac1{6}\cdot 1^2 + \tfrac1{12}\cdot 2^2 + \tfrac1{6}\cdot \left(\tfrac1{3}\right)^2 + \tfrac1{12} \cdot 2^2\right) = \tfrac{38}{9} .
\end{equation*}
\end{example}

\section{Proof of Theorem~\ref{thm:random}}

Let $\mathbf{s} = (s_n)_{n \geq 1}$ be a sequence of independent and uniformly distributed random variables in $\{-1, +1\}$.
Moreover, define
\begin{equation*}
I_\mathbf{s}(n, d) := \begin{cases} 
 1, & \text{if $d \in \mathcal{L}_\mathbf{s}(n)$;} \\
 0, & \text{otherwise,}
\end{cases}
\end{equation*}
for all integers $n, d \geq 1$.
The next lemma gives two expected values involving $I_\mathbf{s}(n, d)$.

\begin{lemma}\label{lem:EIsd}
We have
\begin{equation}\label{equ:EIsd}
\mathbb{E}\big[I_\mathbf{s}(n, d)\big] = 1 - 2^{-\lfloor n (2, d) / d \rfloor}
\end{equation}
and
\begin{align*}
\mathbb{E}&\big[I_\mathbf{s}(n, d_1)I_\mathbf{s}(n, d_2)\big] = 1 - 2^{-\lfloor n(2,d_1)/d_1 \rfloor} - 2^{-\lfloor n(2,d_2)/d_2 \rfloor} \\
 &+ 2^{-\lfloor n (2, d_1) / d_1 \rfloor - \lfloor n (2, d_2) / d_2 \rfloor + \lfloor n (2, [d_1, d_2]) / [d_1, d_2] \rfloor} \begin{cases} 1, & \text{if $\nu_2(d_1) = \nu_2(d_2)$;} \\
 0, & \text{otherwise,} \end{cases}
\end{align*}
for all integers $d, d_1, d_2 \geq 1$.
\end{lemma}
\begin{proof}
On the one hand, by the definitions of $I_\mathbf{s}(n, d)$ and $\mathcal{L}_\mathbf{s}(n)$, we have
\begin{align*}
\mathbb{E}\big[I_\mathbf{s}(n, d)\big] &= \mathbb{P}\big[d \in \mathcal{L}_\mathbf{s}(n)\big] = 1 - \mathbb{P}\!\left[\bigwedge_{k \,\leq\, n} \big(d \notin \mathcal{D}^{(s_k)}(k)\big)\right] = 1 - \mathbb{P}\!\left[\bigwedge_{\substack{k \,\leq\, n \\[1pt] \;d \,\mid\, 2k}} \big(d \notin \mathcal{D}^{(s_k)}(k)\big)\right]\\
 &= 1 - \mathbb{P}\!\left[\bigwedge_{\substack{k \,\leq\, n \\[1pt] \;d \,\mid\, 2k}} \big((d \mid k \land s_k = +1) \lor (d \nmid k \land s_k = -1)\big)\right] = 1 - 2^{-\#\{k \,\leq\, n \,:\, d \,\mid\, 2k\}}\\
 &= 1 - 2^{-\lfloor n (2, d) / d \rfloor} ,
\end{align*}
which is~\eqref{equ:EIsd}.

On the other hand, by linearity of the expectation and by~\eqref{equ:EIsd}, we have
\begin{align}\label{equ:EIsd1Isd2P}
\mathbb{E}\big[I_\mathbf{s}(n, d_1)I_\mathbf{s}(n, d_2)\big] &= \mathbb{E}\big[I_\mathbf{s}(n, d_1) + I_\mathbf{s}(n, d_2) - 1 + \big(1 - I_\mathbf{s}(n, d_1)\big)\big(1 - I_\mathbf{s}(n, d_2)\big)\big] \nonumber \\
 &= \mathbb{E}\big[I_\mathbf{s}(n, d_1)\big] + \mathbb{E}\big[I_\mathbf{s}(n, d_2)\big] - 1 + \mathbb{E}\big[\big(1 - I_\mathbf{s}(n, d_1)\big)\big(1 - I_\mathbf{s}(n, d_2)\big)\big] \nonumber \\
 &= 1 - 2^{-\lfloor n(2,d_1)/d_1 \rfloor} - 2^{-\lfloor n(2,d_2)/d_2 \rfloor} + \mathbb{P}\big[d_1 \notin \mathcal{L}_\mathbf{s}(n) \land d_2 \notin \mathcal{L}_\mathbf{s}(n)\big] . 
\end{align}
Let $P$ be the probability at the end of~\eqref{equ:EIsd1Isd2P}.

Suppose for a moment that $[d_1, d_2] \leq 2n$ and that $d_1$ and $d_2$ have different $2$-adic valuations, say $\nu_2(d_1) < \nu_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 \in \mathcal{D}^-(h)$ and $d_2 \in \mathcal{D}^+(h)$.
Hence, no matter the value of $s_h$, at least one of $d_1, d_2$ belongs to $\mathcal{L}_\mathbf{s}(n)$, and consequently $P = 0$.

Now suppose that $[d_1, d_2] > 2n$ or $\nu_2(d_1) = \nu_2(d_2)$.
In the second case, note that for every integer $k$ such that $[d_1, d_2] \mid 2k$ we have that either $d_1 \mid k$ and $d_2 \mid k$, or $d_1 \nmid k$ and $d_2 \nmid k$.
Therefore,
\begin{align*}
P &= \mathbb{P}\!\left[\bigwedge_{\substack{k \,\leq\, n \\ d_1 \,\mid\, 2k \,\land\, d_2 \,\nmid\, 2k}} \big((d_1 \mid k \land s_k = +1) \lor (d_1 \nmid k \land s_k = -1)\big) \right. \\
 &\phantom{mmm}\land \bigwedge_{\substack{k \,\leq\, n \\ d_1 \,\nmid\, 2k \,\land\, d_2 \,\mid\, 2k}} \big((d_2 \mid k \land s_k = +1) \lor (d_2 \nmid k \land s_k = -1)\big) \\
 &\phantom{mmm}\left.\land \bigwedge_{\substack{k \,\leq\, n \\ d_1 \,\mid\, 2k \,\land\, d_2 \,\mid\, 2k}} \big((d_1 \mid k \land d_2 \mid k \land s_k = +1) \lor (d_1 \nmid k \land d_2 \nmid k \land s_k = -1)\big) \right] \\
 &= 2^{-\#\{k \,\leq\, n \,:\, d_1 \,\mid\, 2k \,\lor\, d_2 \,\mid\, 2k\}} \\
 &= 2^{-\lfloor n (2, d_1) / d_1 \rfloor - \lfloor n (2, d_2) / d_2 \rfloor + \lfloor n (2, [d_1, d_2]) / [d_1, d_2] \rfloor} ,
\end{align*} 
and the proof is complete.
\end{proof}

The following lemma is a simple upper bound for a sum of greatest common divisors.

\begin{lemma}\label{lem:gcdsum}
We have
\begin{equation*}
\sum_{[d_1\!,\, d_2] \,\leq\, n} (d_1, d_2) \ll n^2 ,
\end{equation*}
for every integer $n \geq 1$.
\end{lemma}
\begin{proof}
Let $a_i := d_i / d$ for $i=1,2$, where $d := (d_1, d_2)$.
Then we have
\begin{align*}
\sum_{[d_1\!,\, d_2] \,\leq\, n} (d_1, d_2) &= \sum_{d \,\leq\, n} d \sum_{\substack{a_1 a_2 \,\leq\, n / d \\ (a_1\!,\, a_2) \,=\, 1}} 1 \leq \sum_{d \,\leq\, n} d \sum_{m \,\leq\, n / d} \tau(m) \\
 &\ll n \sum_{d \,\leq\, n} \log\!\left(\frac{n}{d}\right) = n \left(n \log n - \log(n!)\right) < n^2,
\end{align*}
where we used the upper bound $\sum_{m \leq x} \tau(m) \ll x \log x$ (see, e.g.,~\cite[Ch.~I.3, Theorem~3.2]{MR3363366}) and the inequality $n! > (n / \mathrm{e})^n$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:random}]
Let us define the random variable
\begin{equation*}
X := \sum_{d \,\leq\, 2n} \varphi(d) \, I_\mathbf{s}(n, d) .
\end{equation*}
From the linearity of expectation, Lemma~\ref{lem:EIsd}, and Lemma~\ref{lem:phisum}, it follows that
\begin{align}\label{equ:EX}
\mathbb{E}[X] &:= \sum_{d \,\leq\, 2n} \varphi(d) \, \mathbb{E}\big[I_\mathbf{s}(n, d)] \nonumber \\
 &= \sum_{d \,\leq\, 2n} \varphi(d) \left(1 - 2^{-\lfloor n (2, d) / d \rfloor} \right) \nonumber \\
 &= \sum_{d \,\in\, \mathcal{A}_{1,2}(n)} \varphi(d) \left(1 - 2^{-\lfloor n / d \rfloor} \right) + \sum_{d \,\in\, \mathcal{A}_{2,2}(2n)} \varphi(d) \left(1 - 2^{-\lfloor 2n / d \rfloor} \right) \nonumber \\
 &= \frac{3}{\pi^2} \left(c_{1,2} + 4 c_{2,2}\right) \Li_2\!\big(\tfrac1{2}\big) \, n^2 + O\big(n(\log n)^2) \nonumber \\
 &= \frac{6}{\pi^2} \Li_2\!\big(\tfrac1{2}\big) \, n^2  + O\big(n(\log n)^2\big) . 
\end{align}
Furthermore, from Lemma~\ref{lem:EIsd} and Lemma~\ref{lem:gcdsum}, we get that
\begin{align}\label{equ:VX}
& \mathbb{V}[X] = \mathbb{E}\big[X^2\big] - \mathbb{E}[X]^2 \nonumber \\
 &= \sum_{d_1\!,\, d_2 \,\leq\, 2n} \varphi(d_1) \,\varphi(d_2) \Big(\mathbb{E}\big[I_\mathbf{s}(n, d_1)I_\mathbf{s}(n, d_2)\big] - \mathbb{E}\big[I_\mathbf{s}(n, d_1)\big] \mathbb{E}\big[I_\mathbf{s}(n, d_2)\big]\Big) \nonumber \\
 &\leq \sum_{[d_1\!,\, d_2] \,\leq\, 2n} d_1 d_2 \, 2^{-\lfloor n (2, d_1) / d_1 \rfloor - \lfloor n (2, d_2) / d_2 \rfloor + \lfloor n (2, [d_1, d_2]) / [d_1, d_2] \rfloor} \left(1 - 2^{-\lfloor n (2, [d_1, d_2]) / [d_1, d_2] \rfloor}\right) \nonumber \\
 &\leq \sum_{[d_1\!,\, d_2] \,\leq\, 2n} d_1 d_2 \left\lfloor \frac{n(2, [d_1, d_2])}{[d_1, d_2]} \right\rfloor \ll n \sum_{[d_1\!,\, d_2] \,\leq\, 2n} (d_1, d_2) \ll n^3 , 
\end{align}
where we also used the inequality $1 - 2^{-k} \leq k / 2$, which holds for every integer $k \geq 0$.

Therefore, by Chebyshev's inequality, \eqref{equ:EX}, and~\eqref{equ:VX}, it follows that
\begin{equation*}
\mathbb{P}\Big[\big|X - \mathbb{E}[X]\big| > \varepsilon \, \mathbb{E}[X] \Big] \leq \frac{\mathbb{V}[X]}{\big(\varepsilon \mathbb{E}[X]\big)^2} \ll \frac1{\varepsilon^2 n} = o_\varepsilon(1) ,
\end{equation*}
as $n \to +\infty$.
Hence, again by~\eqref{equ:EX}, we have
\begin{equation*}
X \sim \mathbb{E}[X] \sim \frac{6}{\pi^2} \Li_2\!\big(\tfrac1{2}\big) n^2 ,
\end{equation*} 
with probability $1 - o(1)$.
Finally, thanks to Lemma~\ref{lem:logellsn}, we have
\begin{equation*}
\log \ell_{a,\mathbf{s}}(n) = X \log a + O_a\!\left(\frac{n^2}{\log n}\right) ,
\end{equation*}
and the asymptotic formula~\eqref{equ:random} follows.
\end{proof}

\section{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.


\begin{thebibliography}{10}
\bibitem{MR1077711}
S.~Akiyama, Lehmer numbers and an asymptotic formula for {$\pi$}, {\em J.
  Number Theory} {\bf 36} (1990), 328--331.

\bibitem{MR1242715}
S.~Akiyama, A new type of inclusion exclusion principle for sequences and
  asymptotic formulas for {$\zeta(k)$}, {\em J. Number Theory} {\bf 45}
  (1993), 200--214.

\bibitem{MR1394375}
S.~Akiyama, A criterion to estimate the least common multiple of sequences and
  asymptotic formulas for {$\zeta(3)$} arising from recurrence relation of an
  elliptic function, {\em Japan. J. Math. (N.S.)} {\bf 22} (1996), 129--146.

\bibitem{MR3150887}
S.~Akiyama and F.~Luca, On the least common multiple of {L}ucas subsequences,
  {\em Acta Arith.} {\bf 161} (2013), 327--349.

\bibitem{MR4009436}
G.~Alsmeyer, Z.~Kabluchko, and A.~Marynych, Limit theorems for the least common
  multiple of a random set of integers, {\em Trans. Amer. Math. Soc.} {\bf 372} (2019), 4585--4603.

\bibitem{MR1078087}
J.-P. B\'{e}zivin, Plus petit commun multiple des termes cons\'{e}cutifs d'une
  suite r\'{e}currente lin\'{e}aire, {\em Collect. Math.} {\bf 40} (1989),
  1--11 (1990).

\bibitem{MR3239153}
J.~Cilleruelo, J.~Ru\'{e}, P.~\v{S}arka, and A.~Zumalac\'{a}rregui, The least
  common multiple of random sets of positive integers, {\em J. Number Theory}
  {\bf 144} (2014), 92--104.

\bibitem{MR1229668}
J.~P. Jones and P.~Kiss, An asymptotic formula concerning {L}ehmer numbers,
  {\em Publ. Math. Debrecen} {\bf 42} (1993), 199--213.

\bibitem{MR993902}
P.~Kiss and F.~M\'{a}ty\'{a}s, An asymptotic formula for {$\pi$}, {\em J.
  Number Theory} {\bf 31} (1989), 255--259.

\bibitem{MR1712797}
Y.~V. Matiyasevich and R.~K. Guy, A new formula for {$\pi$}, {\em Amer. Math.
  Monthly} {\bf 93} (1986), 631--635.

\bibitem{MR4003803}
C.~Sanna, Practical numbers in {L}ucas sequences, {\em Quaest. Math.} {\bf 42} (2019), 977--983.

\bibitem{MR4091939}
C.~Sanna, On the {l.c.m.} of random terms of binary recurrence sequences, {\em
  J. Number Theory} {\bf 213} (2020), 221--231.

\bibitem{MR4220046}
C.~Sanna, On the least common multiple of random {$q$}-integers, {\em Res.
  Number Theory} {\bf 7} (2021), 16.

\bibitem{PreprintSanna0}
C.~Sanna, On the {l.c.m.} of shifted {F}ibonacci numbers, {\em Int. J. Number
  Theory}  (in press) \url{https://doi.org/10.1142/S1793042121500743}.

\bibitem{MR3363366}
G.~Tenenbaum, {\em Introduction to {A}nalytic and {P}robabilistic {N}umber
  {T}heory}, 3rd edition,
  Vol.~163 of {\em Graduate Studies in Mathematics}, American
  Mathematical Society, 2015.

\bibitem{MR1114366}
B.~Tropak, Some asymptotic properties of {L}ucas numbers, In {\em Proceedings
  of the {R}egional {M}athematical {C}onference ({K}alsk, 1988)}, pp.~49--55.
  Pedagog. Univ. Zielona G\'{o}ra, 1990.

\bibitem{MR2290758}
D.~Zagier, The dilogarithm function.
\newblock In {\em Frontiers in {N}umber {T}heory, {P}hysics, and {G}eometry.
  {II}}, pp.~3--65. Springer, 2007.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11B37, 11N37.

\noindent \emph{Keywords: } asymptotic formula, least common multiple, power.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 24 2021; 
revised versions received May 22 2021; June 12 2021.
Published June 12 2021.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
