1 Introduction
Let
$(u_n)$
be a nondegenerate linear recurrence with integral values. Arithmetic relations between n and
$u_n$
have been studied by several authors. For example, the set of positive integers n such that n divides
$u_n$
has been studied by Alba González, Luca, Pomerance, and Shparlinski [Reference Alba González, Luca, Pomerance and Shparlinski2], assuming that the characteristic polynomial of
$(u_n)$
is separable, and by André-Jeannin [Reference André-Jeannin3], Luca and Tron [Reference Luca and Tron13], Sanna [Reference Sanna22], and Somer [Reference Somer28], when
$(u_n)$
is a Lucas sequence. Furthermore, Sanna [Reference Sanna24] showed that the set of natural numbers n such that
$\gcd (n, u_n) = 1$
has a natural density (see [Reference Mastrostefano and Sanna15] for a generalization). Mastrostefano and Sanna [Reference Mastrostefano14, Reference Sanna23] studied the moments of
$\log \!\big (\!\gcd (n, u_n)\big )$
and
$\gcd (n, u_n)$
when
$(u_n)$
is a Lucas sequence, and Jha and Nath [Reference Jha and Nath9] performed a similar study over shifted primes. Part of the interest in studying
$\gcd (n, u_n)$
resides in the fact that this task can be considered a simpler, albeit nontrivial, case of the general problem of studying the greatest common divisor (GCD) of terms of two linear recurrences, a problem that led to the famous Bugeaud–Corvaja–Zannier bound [Reference Bugeaud, Corvaja and Zannier5] and the difficult Ailon–Rudnick conjecture [Reference Ailon and Rudnick1]. (See the survey of Tron [Reference Tron30] for an extensive treatise on GCDs of terms of linear recurrences, especially Section 3 for these considerations on
$\gcd (n, u_n)$
.) Furthermore, more abstractly, when
$(u_n)$
is a Lucas sequence of discriminant
$\Delta _u$
, we have that
$(\gcd (n, u_n))$
is the GCD sequence naturally associated, by Silverman’s correspondence [Reference Silverman27], with the algebraic group
$\mathbb {G}_a \times \mathbb {G}_m(\sqrt {\Delta _u})$
, which is the product of the additive group with a twist of the multiplicative group.
Let
$(F_n)$
be the linear recurrence of Fibonacci numbers, which is defined by
$F_1 = F_2 = 1$
and
$F_{n + 2} = F_{n + 1} + F_n$
for every positive integer n. Sanna and Tron [Reference Sanna and Tron26] proved that, for each positive integer k, the set of positive integers n such that
$\gcd (n, F_n) = k$
has a natural density, which is given by an infinite series. Kim [Reference Kim11] and Jha [Reference Jha8] obtained formally analogous results in cases of elliptic divisibility sequences and orbits of polynomial maps, respectively. Let
$\mathcal {A}$
be the set of numbers of the form
$\gcd (n, F_n)$
, for some positive integer n. Leonetti and Sanna [Reference Leonetti and Sanna12] provided an effective method to enumerate the elements of
$\mathcal {A}$
in increasing order. In particular, the first elements of
$\mathcal {A}$
are
$$ \begin{align*} 1, \quad 2, \quad 5, \quad 7, \quad 10, \quad 12, \quad 13, \quad 17, \quad 24, \quad 25, \quad 26, \quad 29, \quad 34, \quad 35, \quad \dots \end{align*} $$
(see [17, A285058] for more terms). Then they proved that
$$ \begin{align} \#\mathcal{A}(x) \gg \frac{x}{\log x} \end{align} $$
for all
$x \geq 2$
. Their approach relied on a result of Cubre and Rouse [Reference Cubre and Rouse6], which in turn follows from Galois theory and the Chebotarev density theorem. Later, Jha and Sanna [Reference Jha and Sanna10, Proposition 1.4] obtained an elementary proof as an application of related arithmetic problem over shifted primes. Leonetti and Sanna [Reference Leonetti and Sanna12] also gave the upper bound
$\#\mathcal {A}(x) = o(x)$
as
$x \to +\infty $
, and asked for a more precise estimate. We prove the following upper bound on
$\#\mathcal {A}(x)$
.
Theorem 1.1 We have
$$ \begin{align*} \#\mathcal{A}(x) \ll \frac{x \log \log \log x}{\log \log x} \end{align*} $$
for all sufficiently large x.
In fact, we prove that an upper bound similar to that of Theorem 1.1 also holds when the sequence of Fibonacci numbers is replaced by a general nondegenerate Lucas sequence (see Theorem 3.1).
In light of the gap between the upper bound of Theorem 1.1 and the lower bound (1.1), it is natural to wonder which is the true order of
$\#\mathcal {A}(x)$
. By performing some numerical experiments (see Section 4), we found that
$\#\mathcal {A}(x)$
appears to be asymptotic to
$x / (\log x)^c$
, as
$x \to +\infty $
, for some constant
$c \approx 0.63$
(see Figure 1).
A plot of
$\#\mathcal {A}(x) / (x / (\log x)^c)$
for x up to
$10^6$
.
1.1 Notation
For every set of positive integers
$\mathcal {S}$
and for every
$x> 0$
, we define
$\mathcal {S}(x) := \mathcal {S} \cap [1, x]$
. Throughout, we reserve the letter p for prime numbers. We employ the Landau–Bachmann “Big Oh” and “little oh” notation O and o, as well as the associated Vinogradov symbols
$\ll $
and
$\gg $
. Moreover, we write
$f \asymp g$
to denote that
$f \ll g$
and
$f \gg g$
. Any dependence of the implied constants is explicitly stated or indicated with subscripts. In particular,
$O_u$
is a shortcut for
$O_{a_1, a_2}$
, and similarly for
$\ll _u$
,
$\gg _u$
, and
$\asymp _u$
. We let
$\operatorname {\mathrm {Li}}(x) := \int _2^x (\log t)^{-1}\,\mathrm {d}t$
denote the integral logarithm.
2 Preliminaries on Lucas sequences
In what follows, let
$(u_n)$
be a Lucas sequences, that is, a sequence of integers satisfying
$u_0 = 0$
,
$u_1 = 1$
, and
$u_n = a_1 u_{n - 1} + a_2 u_{n - 2}$
for every integer
$n \geq 2$
, where
$a_1, a_2$
are fixed nonzero relatively prime integers. Furthermore, assume that
$(u_n)$
is nondegenerate, which means that the ratio of the roots of the characteristic polynomial
$X^2 - a_1 X - a_2$
is not a root of unity. In particular, the discriminant
$\Delta _u := a_1^2 + 4a_2$
is nonzero.
For each positive integer m that is relatively prime with
$a_2$
, let
$z_u(m)$
be the rank of appearance of m in the Lucas sequence, that is, the smallest positive integer n such that m divides
$u_n$
. It is well known that
$z_u(m)$
exists (see, e.g., [Reference Renault20]). Furthermore, put
$\ell _u(m) := \operatorname {\mathrm {lcm}}\!\big (m, z_u(m)\big )$
and, for each positive integer n, let
$g_u(n) := \gcd (n, u_n)$
and
$\mathcal {A}_u := \big \{g_u(n) : n \in \mathbb {N}\big \}$
.
The next lemma collects some elementary properties of
$z_u$
,
$\ell _u$
,
$g_u$
, and
$\mathcal {A}_u$
.
Lemma 2.1 For all positive integers
$m,n$
and all prime numbers p, with
$p \nmid a_2$
, we have:
-
(i)
$m \mid u_n$
if and only if
$\gcd (m, a_2) = 1$
and
$z_u(m) \mid n$
. -
(ii)
$z_u(m) \mid z_u(n)$
whenever
$\gcd (mn, a_2) = 1$
and
$m \mid n$
. -
(iii)
$z_u(p)\mid p - (-1)^{p-1}\eta _u(p)$
, where
$$ \begin{align*} \eta_u(p) := \begin{cases} +1, & \text{ if } p \nmid \Delta_u \text{ and } \Delta_u \equiv x^2 \ \ \pmod p \text{ for some } x \in \mathbb{Z}, \\ -1, & \text{ if } p \nmid \Delta_u \text{ and } \Delta_u \not\equiv x^2 \ \ \pmod p \text{ for all } x \in \mathbb{Z},\\ 0, & \text{ if } p \mid \Delta_u. \end{cases} \end{align*} $$
-
(iv)
$z_u(p^n)=p^{e_u(p, n)}\,z_u(p)$
, where
$e_u(p, n)$
is some nonnegative integer less than n. -
(v)
$\ell _u(p^n) = p^n z_u(p)$
if
$p \nmid \Delta _u$
, and
$\ell _u(p^n) = p^n$
if
$p \mid \Delta _u$
. -
(vi)
$g_u(m) \mid g_u(n)$
whenever
$m \mid n$
. -
(vii)
$n \mid g_u(m)$
if and only if
$\gcd (n, a_2) = 1$
and
$\ell _u(n) \mid m$
. -
(viii)
$n \in \mathcal {A}_u$
if and only if
$\gcd (n, a_2) = 1$
and
$n = g_u\big (\ell _u(n)\big )$
. -
(ix)
$m \mid n$
whenever
$\gcd (mn, a_2) = 1$
,
$\ell _u(m) \mid \ell _u(n)$
, and
$n \in \mathcal {A}_u$
.
Proof (i)–(iv) are well-known properties of the rank of appearance of a Lucas sequence (see, e.g., [Reference Renault20], [Reference Ribenboim21, Chapter 1], or [Reference Sanna22, Section 2]), whereas (v)–(vii) follow easily from (i)–(iv) and from the definitions of
$\ell _u$
and
$g_u$
. Let us prove (viii). If
$n \in \mathcal {A}_u$
, then there exists a positive integer m such that
$n = g_u(m)$
. In particular,
$n \mid g_u(m)$
and, by (vii), we get that
$\gcd (n, a_2) = 1$
and
$\ell _u(n) \mid m$
. Therefore, by (vi), we have that
$g_u\big (\ell _u(n)\big ) \mid n$
. Since n divides both
$\ell _u(n)$
and
$u_{\ell _u(n)}$
(by (i)), it follows that
$n \mid g_u\big (\ell _u(n)\big )$
. Hence,
$n = g_u\big (\ell _u(n)\big )$
. The other implication is straightforward. Finally, (ix) follows quickly from (vii) and (viii).
For each positive integer d, let
$\mathcal {P}_{u,d}$
be the set of prime numbers p not dividing
$a_2$
and such that d divides
$z_u(p)$
. Cubre and Rouse [Reference Cubre and Rouse6] proved an asymptotic formula for
$\#\mathcal {P}_d(x)$
in the special case in which
$(u_n)$
is the sequence of Fibonacci numbers. Sanna [Reference Sanna25] extended this result to Lucas sequences (under some mild restrictions) and also provided an error term. In particular, as a consequence of [Reference Sanna25, Theorem 1.1], we have the following asymptotic formula.
Lemma 2.2 There exists a constant
$B_u> 0$
such that for all
$x \geq \exp (B_u d^{40})$
and for all odd positive integers d, with
$3 \nmid d$
if the square-free part of
$\Delta _u$
is equal to
$-3$
, we have that
$$ \begin{align} \#\mathcal{P}_d(x) = \delta_u(d) \operatorname{\mathrm{Li}}(x) + O_u\!\left(\frac{x}{(\log x)^{12/11}}\right) , \end{align} $$
where
$\delta _u(d)$
is a quantity satisfying
$\delta _u(d) \asymp _u 1 / d$
.
Proof If
$\Delta _u$
is not a square, then, from [Reference Sanna25, Theorem 1.1], we have that there exists a constant
$B_u> 0$
such that
$$ \begin{align} \#\mathcal{P}_d(x) = \delta_u(d) \operatorname{\mathrm{Li}}(x) + O_u\!\left(\frac{d}{\varphi(d)} \cdot \frac{x \, (\log \log x)^{\omega(d)}}{(\log x)^{9/8}}\right) , \end{align} $$
for all odd positive integers d, with
$3 \nmid d$
if the square-free part of
$\Delta _u$
is equal to
$-3$
, and for all
$x \geq \exp (B_u d^{40})$
, where
$\delta _u(d) \asymp _u 1 / d$
, whereas
$\varphi (d)$
and
$\omega (d)$
are the Euler totient function and the number of prime factors of d, respectively.
If
$\Delta _u$
is a square, then, by the Binet formula, we have that
$$ \begin{align*} u_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} \end{align*} $$
for every positive integer n, where
$\alpha := (a_1 - \sqrt {\Delta _u}) / 2$
and
$\beta := (a_1 + \sqrt {\Delta _u}) / 2$
are integers. Consequently, for every prime number p not dividing
$a_2 \Delta _u$
, we have that
$z_u(p)$
is equal to the multiplicative order of
$\alpha / \beta $
modulo p. Then (2.2) follows from a result of Moree [Reference Moree16, Lemma 1]. (Moree did not make explicit the factor
$d/\varphi (d)$
, but this can be easily done [cf. [Reference Sanna25, Lemma 6.3]].)
Note that we can assume that
$B_u$
(and consequently x) is sufficiently large. In particular, we have that
$d \leq (\log x)^{1/40}$
. Put
$\varepsilon := 1/330$
. By the classic lower bound for
$\varphi (d)$
(see, e.g., [Reference Tenenbaum29, Chapter I.5, Theorem 5.6]), we have that
$$ \begin{align*} \frac{d}{\varphi(d)} \ll \log \log d \ll \log \log \log x \leq (\log x)^{\varepsilon}. \end{align*} $$
Recall that
$\omega (d) \leq \big (1 + o(1)\big ) \log d / \log \log d$
as
$d \to +\infty $
(see, e.g., [Reference Tenenbaum29, Chapter I.5, Theorem 5.5]). Therefore, there exists an absolute constant
$C> 0$
such that if
$d> C$
, then
$$ \begin{align*} \omega(d) \leq (1 + \varepsilon) \frac{\log d}{\log \log d} \leq \left(\frac1{40} + 2\varepsilon\right) \frac{\log \log x}{\log \log \log x} , \end{align*} $$
and consequently
$(\log \log x)^{\omega (d)} \leq (\log x)^{\frac 1{40} + 2\varepsilon }$
. Furthermore, if
$d \leq C$
, then
$$ \begin{align*} (\log \log x)^{\omega(d)} \leq (\log x)^\varepsilon. \end{align*} $$
Thus, (2.1) follows.
Remark 2.3 In Lemma 2.2, the exponent
$12/11$
can be replaced by
$11/10 + \varepsilon $
, for every
$\varepsilon> 0$
, assuming that x is sufficiently large depending on
$\varepsilon $
.
We also need an upper bound for
$\#\mathcal {P}_{u,d}(x)$
.
Lemma 2.4 We have
$$ \begin{align*} \#\mathcal{P}_{u,d}(x) \ll_u \frac{x}{\varphi(d) \log (x / d)} \end{align*} $$
for all positive integers d and for all
$x> d$
.
Proof By Lemma 2.1 (iii), we have that
$$ \begin{align*} \#\mathcal{P}_{u,d}(x) \leq O_u(1) + \#\big\{p \leq x : p \equiv \pm 1 \ \ \pmod d \big\} \ll_u \frac{x}{\varphi(d) \log (x / d)} , \end{align*} $$
where we applied the Brun–Titchmarsh inequality [Reference Tenenbaum29, Chapter I.4, Theorem 4.16].
Now, we give an upper bound for the sum of reciprocals of primes in
$\mathcal {P}_{u,d}$
.
Lemma 2.5 We have
$$ \begin{align*} \sum_{p \,\in\, \mathcal{P}_{u,d}(x)} \frac1{p} = \delta_u(d)\log \log x + O_u\!\left(\frac{\log(2d)}{\varphi(d)}\right) \end{align*} $$
for all odd positive integers d, with
$3 \nmid d$
if the square-free part of
$\Delta _u$
is equal to
$-3$
, and for all
$x \geq 3$
.
Proof First, suppose that
$x < \exp (B_u d^{40})$
, where
$B_u$
is the constant of Lemma 2.2. Hence, we have that
$$ \begin{align*} \delta_u(d)\log \log x \ll_u \frac{\log \log x}{d} \ll_u \frac{\log(2d)}{d}. \end{align*} $$
Moreover, by [Reference Pomerance19, Theorem 1 and Remark 1], we have that
$$ \begin{align*} \sum_{\substack{p \,\leq\, x \\[1pt] p \,\equiv\, \pm 1 \ \ \pmod d}} \frac1{p} = \frac{2\log \log x}{\varphi(d)} + O\!\left(\frac{\log(2d)}{\varphi(d)}\right). \end{align*} $$
This together with Lemma 2.1 (iii) yields that
$$ \begin{align*} \sum_{p \,\in\, \mathcal{P}_{u,d}(x)} \frac1{p} \leq \frac{O_u(1)}{d} + \sum_{\substack{p \,\leq\, x \\[1pt] p \,\equiv\, \pm 1 \ \ \pmod d}} \frac1{p} \ll_u \frac1{d} + \frac{\log (2d)}{\varphi(d)}. \end{align*} $$
Hence, the claim follows. Now, suppose that
$x \geq \exp (B_u d^{40})$
. By partial summation, we have that
$$ \begin{align*} \sum_{p \,\in\, \mathcal{P}_{u,d}(x)} \frac1{p} = \frac{\#\mathcal{P}_{u,d}(x)}{x} + \int_1^x \frac{\#\mathcal{P}_{u,d}(t)}{t^2} \,\mathrm{d} t. \end{align*} $$
From Lemma 2.1
(iii), we get easily that
$\#\mathcal {P}_{u,d}(x) / x \ll _u 1/d$
. Thus, it remains to bound the integral. By Lemma 2.1
(iii) again, we have that
$\#\mathcal {P}_{u,d}(t)>0$
only if
$t\ge d-1$
, and that
$\#\mathcal {P}_{u,d}(t) \ll _u 1$
for
$t \in [1, 2d]$
. Hence, we have
$$ \begin{align*} \int_1^{2d} \frac{\#\mathcal{P}_{u,d}(t)}{t^2} \,\mathrm{d} t \ll_u \int_{d-1}^{2d} \frac{\mathrm{d} t}{t^2} \ll \frac1{d}. \end{align*} $$
By Lemma 2.4, we have that
$$ \begin{align*} \int_{2d}^{\exp(Bd^{40})} \frac{\#\mathcal{P}_{u,d}(t)}{t^2} \,\mathrm{d} t &\ll_u \int_{2d}^{\exp(B_u d^{40})} \frac{\mathrm{d} t}{\varphi(d) \,t \log(t / d)} \\ &= \left[ \frac{\log\log(t/d)}{\varphi(d)}\right]_{t \,=\, 2d}^{\exp(B_u d^{40})} \ll \frac{\log (2d)}{\varphi(d)}. \end{align*} $$
By Lemma 2.2, we have that
$$ \begin{align*} \int_{\exp(B_u d^{40})}^x \frac{\#\mathcal{P}_{u,d}(t)}{t^2} \,\mathrm{d} t &= \int_{\exp(B_u d^{40})}^x \frac{\delta_u(d) \operatorname{\mathrm{Li}}(t)}{t^2} \,\mathrm{d} t + O_u\!\left(\int_{\exp(B_u d^{40})}^x \frac{\mathrm{d}t}{t (\log t)^{12/11}} \right) \\ &= \delta_u(d) \left[\log \log t - \frac{\operatorname{\mathrm{Li}}(t)}{t} \right]_{t \,=\, \exp(B_u d^{40})}^x + O_u\!\left( \frac1{d^{40/11}} \right) \\ &= \delta_u(d) \left(\log \log x + O\big(\log (2d)\big) \right) + O_u\!\left( \frac1{d^{40/11}} \right) \\ &= \delta_u(d) \log \log x + O_u\!\left(\frac{\log (2d)}{d} \right). \end{align*} $$
Putting these together, the claim follows.
The following sieve result is a special case of [Reference Halberstam and Richert7, Theorem 7.2] (cf. [Reference Pollack18, Lemma 2.2]).
Lemma 2.6 We have
$$ \begin{align*} \#\{n\le x : p\mid n \Rightarrow p \notin \mathcal{P}\} \ll x \prod_{p \,\in\, \mathcal{P}(x)} \left(1 - \frac{1}{p}\right) , \end{align*} $$
for all
$x \ge 2$
and for all sets of prime numbers
$\mathcal {P}$
.
We also need the so-called Primitive Divisor Theorem for Lucas sequence [Reference Bilu, Hanrot and Voutier4].
Theorem 2.7 For every integer
$r \geq 31$
, there exists a prime number p such that
$z_u(p) = r$
.
3 Proof of Theorem 1.1
We shall prove the following more general result, of which Theorem 1.1 is a particular case.
Theorem 3.1 We have
$$ \begin{align*} \#\mathcal{A}_u(x) \ll_u \frac{x \log \log \log x}{\log \log x} \end{align*} $$
for all sufficiently large x.
Proof Let
$r := 30\prod _{p \mid 6\Delta _u} z_u(p) + 1$
. Since
$r \geq 31$
, it follows from Theorem 2.7 that there exists a prime number q such that
$z_u(q) = r$
. Furthermore, by Lemma 2.1
(i), we have that
$\gcd (6\Delta _u, u_r) = 1$
and so
$q \nmid 6\Delta _u$
. Note also that
$\gcd (6, r) = 1$
.
From Lemma 2.2, we know that
$\delta _u(dr) \geq C_u / d$
for every positive integer d with
$\gcd (6, d) = 1$
, where
$C_u> 0$
is a constant depending only on
$a_1, a_2$
. (Note that r is completely determined by
$a_1, a_2$
.) Suppose that
$x> 0$
is sufficiently large, and put
$$ \begin{align*} k := \left\lfloor \frac1{\log q} \log\!\left(\min(1, C_u) \, \frac{\log \log x}{\log \log \log x}\right)\right\rfloor \end{align*} $$
and
$d := q^k$
. Hence, we get that
$$ \begin{align*} d \leq \min(1, C_u) \, \frac{\log \log x}{\log \log \log x} \end{align*} $$
and so
$$ \begin{align*} \frac{\log d}{\delta_u(dr)} \leq \frac{d}{C_u} \log d \leq \frac{\log \log x}{\log \log \log x} \log d \leq \log \log x. \end{align*} $$
Therefore, we have that
$$ \begin{align} (\log x)^{\delta_u(dr)} \geq d \gg_u \frac{\log \log x}{\log \log \log x}. \end{align} $$
We split
$\mathcal {A}_u$
into two subsets:
$\mathcal {A}_u^\prime $
is the subset of
$\mathcal {A}_u$
consisting of integers without prime factors in
$\mathcal {P}_{u,dr}$
, and
$\mathcal {A}_u^{\prime \prime } := \mathcal {A}_u \setminus \mathcal {A}_u^\prime $
.
First, we give an upper bound on
$\#\mathcal {A}_u^\prime (x)$
. Note that
$\gcd (6, dr) = 1$
. By Lemmas 2.5 and 2.6, we get that
$$ \begin{align} \#\mathcal{A}_u^\prime(x) \ll x \prod_{p \,\in\, \mathcal{P}_{u,dr}(x)} \left(1-\frac{1}{p}\right) \leq x \exp\!\left(-\!\!\sum_{p \,\in\, \mathcal{P}_{u,dr}(x)} \frac1{p}\right) \ll_u \frac{x}{(\log x)^{\delta_u(dr)}} , \end{align} $$
where we also used the inequality
$1 - x \leq \exp (-x)$
, which holds for
$x \geq 0$
.
Now, we give an upper bound on
$\#\mathcal {A}_u^{\prime \prime }(x)$
. If
$n \in \mathcal {A}_u^{\prime \prime }$
, then n has a prime factor
$p \in \mathcal {P}_{u,dr}$
. Hence, we have that
$p \mid n$
and
$dr \mid z_u(p)$
. Thus, by Lemma 2.1
(ii), we get that
$z_u(p) \mid z_u(n)$
and so
$dr \mid \ell _u(n)$
. Recalling that
$d = q^k$
,
$z_u(q) = r$
, and
$q \nmid \Delta _u$
, by Lemma 2.1
(v), we have that
$\ell _u(d) = dr$
. Hence, we get that
$\ell _u(d) \mid \ell _u(n)$
and, by Lemma 2.1
(ix), it follows that
$d \mid n$
. Thus, all the elements of
$\mathcal {A}_u^{\prime \prime }$
are multiples of d. Consequently, we have that
$$ \begin{align} \#\mathcal{A}_u^{\prime\prime}(x) \leq \frac{x}{d}. \end{align} $$
Therefore, putting together (3.2) and (3.3), and using (3.1), we obtain that
$$ \begin{align*} \#\mathcal{A}_u(x) = \#\mathcal{A}_u^\prime(x) + \#\mathcal{A}_u^{\prime\prime}(x) \ll_u \frac{x}{(\log x)^{\delta_u(dr)}} + \frac{x}{d} \ll_u \frac{x \log \log \log x}{\log \log x} , \end{align*} $$
as desired. The proof is complete.
4 Numerical computations
We computed the elements of
$\mathcal {A} \cap [1, 10^6]$
by using a program written in C that employs Lemma 2.1
(viii). Note that computing
$g\big (\ell (n)\big )$
directly as
$\gcd \!\big (\ell (n), F_{\ell (n)}\big )$
would be prohibitive, in light of the exponential grown of Fibonacci numbers. Instead, we used the fact that
$$ \begin{align*} g\big(\ell(n)\big) = \gcd\!\big(\ell(n), F_{\ell(n)} \bmod \ell(n)\big), \end{align*} $$
and we computed Fibonacci numbers modulo an integer by efficient matrix exponentiation.
Acknowledgment
The authors would like to thank the anonymous referee for providing suggestions that improved the quality of the paper. C. Sanna is a member of GNSAGA of INdAM and of CrypTO, the group of Cryptography and Number Theory of the Politecnico di Torino.
