On the Growth of Some Functions Related to z(n)

Abstract

The order of appearancez:Z>0→Z>0is an arithmetic function related to the Fibonacci sequence(Fn)n. This function is defined as the smallest positive integer solution of the congruenceFk≡0(modn). In this paper, we shall provide lower and upper bounds for the functions∑n≤xz(n)/n,∑p≤xz(p)and∑pr≤xz(pr).

1. Introduction

Perhaps the most important of the binary recurrences is the Fibonacci sequence_(Fn)n. This sequence starts with_F0=0and_F1=1and it satisfies the 2nd order recurrence relation_Fn+2=_Fn+1+_Fn(forn≥0). A well-known, explicit, formula for the nth Fibonacci number is called the Binet-formula

_Fn=^αn−^βn5,

whereα:=(1+5)/2andβ:=(1−5)/2. It follows from this formula that the estimates^αn−2≤_Fn≤^αn−1, hold for alln≥1.

The study of the divisibility properties of Fibonacci numbers has always been a popular area of research. For example, it is still an open problem to decide if there are infinitely many primes in that sequence. In order to study such kind of Diophantine problems, the arithmetic functionz:_Z>0→_Z>0was defined by settingz(n)=min{k≥1:n∣_Fk}. This function is called the order of appearance in the Fibonacci sequence. For more results onz(n) , see [1] and references therein.

In 1878, Lucas ([2], p. 300) established thatz(n) is well defined and, in 1975, J. Sallé [3] proved thatz(n)≤2n, for all positive integers n. This is the sharpest upper bound forz(n), since for example

z(n)=2nifandonlyifn=6·^5k,fork≥0.

However, apart from these cases this upper bound is very weak. For instance,z(2255)=20<¹⁰⁻²·2255 . In fact, Marques [4] gave sharper upper bounds forz(n)for all positive integersn≠6·^5k. These upper bounds depend on the number of distinct prime factors of n, denoted byω(n).

In the main stream of the Analytic Number Theory, we have the three following functions

H(x):=∑n≤x1n,ϑ(x):=∑p≤xlogpandψ(x):=∑n≤xΛ(n),

whereΛ(n)is the well-known von Mangoldt function defined aslogpifn=^pr, for some prime number p andr≥1 , and 0 otherwise (see, e.g., [5,6]). The functionsϑ(x)andψ(x)are called the first and the second Chebyshev functions, respectively. Note thatψ(x)can be rewritten as_∑^pr≤xlogp. Here (and in all what follows)_∑n≤x,_∑p≤xand_∑^pr≤xmean that the sum is taken over all positive integers, all prime numbers and all prime powers belonging to the interval[1,x], respectively.

Probably, the main importance of the functionsψandϑrelies in the proof of the celebrated Prime Number Theorem which states that

π(x)∼xlogx,

whereπ(x)=_∑p≤x1is the prime counting function. Indeed, the prime number theorem and the statementsϑ(x)∼xandψ(x)∼xare all equivalent. Heref(x)∼g(x)(asymptotic equivalence) means thatf(x)/g(x)tends to 1 asx→∞(in another way,f(x)=g(x)+o(g(x))whereo(g(x))means a functionh(x)with_limx→∞h(x)/g(x)=0). Actually, one has the following stronger fact

π(x)=xlogx+Ox^(logx)2.

Here we shall use the Landau symbols in their usual meaning, i.e., we say thatf(x)=O(g(x))(orf≪g), if there exists a positive constant M such that|f(x)|≤M|g(x)|, for all sufficiently large x. Also,f≍gmeans thatf≪gandg≪f.

Another function of great interest is the harmonic functionH(x)whose image forx∈_Z>0is called the xth harmonic number and denoted by_Hx. These numbers gained much attention with their relation to the Riemann hypothesis. In fact, the Riemann hypothesis is equivalent to prove that

d(n)≤_Hn+^e_Hn log_Hn,

for alln≥1, whered(n) is the sum of the positive divisors of n (see [7]). We observe that the harmonic series, i.e.,_limx→∞H(x)is a well-studied example of divergent series. In fact, it holds that

H(x)=logx+O(1),

which agrees with its very slow divergence.

In this paper, we are interested in studying the growth of the following Fibonacci versions ofH(x),ϑ(x)andψ(x), thus, the functions_ZH(x),_Zϑ(x)and_Zψ(x) (see Figure 1), for a positive real x, which are defined as

_ZH(x):=∑n≤xz(n)n,_Zϑ(x):=∑p≤xz(p)and_Zψ(x):=∑^pr≤xz(^pr).

First, observe that since1≤z(n)≤2n, then the following trivial estimates hold

logx≪H(x)≤_ZH(x)≤∑n≤x2≤2x.

However, we found the previous bounds by neglecting the contribution ofz(n)(which is much bigger than 1 and much smaller than2n, in almost all cases). In fact, by takingz(n)into account, we obtain

Theorem 1.

We have that

^(logx)2≪_ZH(x)≪x^(logx)1/3.

For the function_Zϑ(x), if we use thatz(p)≥1, we get

_Zϑ(x)≥∑p≤x1=π(x)≫xlogx.

Again, with an extra effort, we can improve this by proving that

Theorem 2.

We have that

x≪_Zϑ(x)≪^x2logx.

Since the number of prime powers in[1,x]is bigger thanπ(x), a similar direct inequality (that one for_Zϑ(x)) could be derived for_Zψ(x). However, by using the behavior ofz(^pr), we can obtain better estimates such as

Theorem 3.

We have that

x≪_Zψ(x)≪^x2logx.

Note that even with a larger number of possibilities in the sum of_Zψ(x), its bounds are the same (in order) than the ones for_Zϑ(x)(Theorem 2). The explanation for this, follows from the fact that the contribution, i.e., the number of powers of p (for example) belonging to[1,x]isO(logx)which iso(x). In other words, this amount is almost negligible (compared with x, in terms of order).

In a few words, the proof of the results combine some new (sharper upper bounds forz(n)due to Marques) and classical results (such as results due Abel, Sathé, Selberg) in Number Theory.

2. Auxiliary Results

In this section, we shall present some tools which will be very useful in the proofs. We start with some results due to Marques [4], which will be very helpful in our proof. Thus, we shall state his results as lemmas (in what follows, the 2-adic valuation of n is_ν2(n)=max{k≥0:^2k∣n}).

Lemma 1.We have

(i)

z(^2k)=3·^2k−2(fork≥3),z(^3k)=4·^3k−1(fork≥1) andz(^5k)=^5k(fork≥0).

(ii)

Ifp>5is a prime, then

z(^pk)≤p−5p^pk−1,fork≥1,

where, as usual,(aq)denotes the Legendre symbol of a with respect to a primeq>2.

Lemma 2.

Let n be an odd integer number withω(n)≥2, then

z(n)≤2·^{23ω(n)−_δn}n,

where

_δn=0,if5∤n;1,if5∣n.

Lemma 3.

Let n be an even integer number withω(n)≥2, it holds that

(i)

If_ν2(n)≥4, then

z(n)≤34·^{23ω(n)−_δn−1}n.

(ii)

If_ν2(n)=1, then

z(n)≤3n/2,ifω(n)=2and5∣n;2n,ifω(n)=2and5∤n;3·^{(2/3)ω(n)−_δn−1}n,ifω(n)>2.

(iii)

If_ν2(n)∈{2,3}, then

z(n)≤3n/2,ifω(n)=2and5∣n;n,ifω(n)=2and5∤n;^{(2/3)ω(n)−_δn−2}n,ifω(n)>2.

The next lemma is a powerful result in analytic number theory which is related to positive integers with fixed number of distinct prime factors.

Lemma 4

(Sathé–Selberg Formula). For any positive constant A, we have

#_Pk(x):=#{n≤x:ω(n)=k}∼Gk−1loglogxxlogx^{(loglogx)k−1}(k−1)!,

forx≥3and1≤k≤Aloglogx, where

G(z):=1Γ(1+z)∏pprime1+zp^1−1pz.

In the previous statementΓ(z)=_∫0∞ ^{xz−1 e−x}dx(forx>0) is the well-known Gamma function.

The proof of Lemma 4 can be found in [8,9].

Our last tool is a very useful formula due to Abel which makes an interplay between a discrete sum and an integral (continuous sum). More precisely,

Lemma 5

(Abel’s Summation Formula). Let_(an)nbe a sequence of real numbers and define its partial sumA(x):=_{∑n≤x an}. For a real numberx>1, let f be a continuously differentiable function on[1,x]. Then

∑n≤x_anf(n)=A(x)f(x)−_∫1xA(t)^f′(t)dt.

Remark 1.

We remark that, throughout what follows, the implied constants in ≪ and ≫ can be made explicit. Here, we decided to use asymptotic bounds in order to leave the text more readable. However, we shall provide the explicit inequalities for convenience of the reader (they can be found in [10], for example).

(i)

∑n≤x1n>log(x+1);

(ii)

ϑ(x)<1.000028x, forx>0andϑ(x)>0.998684x, forx>1319007;

(iii)

_pn<nlogn+nloglogn, forn≥6;

(iv)

xlogx<π(x)<1.25506xlogx, forx≥17.

As usual, from now on we use the well-known notation[a,b]={a,a+1,…,b−1,b}, for integersa<b.

Now we are ready to deal with the proof of our results. 3. The Proofs 3.1. The Proof of Theorem 1

Since, by definition,n∣_Fz(n), thenn≤_Fz(n)≤^αz(n)−1and soz(n)>logn/logα. Thus

_ZH(x)=∑n≤xz(n)n≫∑n≤xlognn.

Now, we shall use Lemma 5 for_an=1/nandf(x)=logx. Then

∑n≤xlognn=H(x)logx−_∫1xH(t)tdt.

SinceH(x)=logx+O(1)and_∫1xlogttdt=^(logx)2/2, then

∑n≤xlognn=(logx+O(1))logx−_∫1xlogt+O(1)tdt=12^(logx)2+O(logx)≫^(logx)2

and so_ZH(x)≫^(logx)2.

For the second part, we use Lemmas 1, 2 and 3 to derive that

z(n)≤7^23ω(n)n,

for alln>1. First, let us write_ZH(x)as

_ZH(x)=∑k=1h(x)∑n∈_Pk(x)z(n)n,

whereh(x)=max{ω(t):t≤x}. By using thatz(n)≤7·^(2/3)ω(n)n, we have

_ZH(x)≪∑k=1h(x)∑n∈_Pk(x)^23ω(n)≪∑k=1h(x)^23k#_Pk(x)

which can be written as

_ZH(x)≪∑k=1⌊loglogx⌋^23k#_Pk(x)+∑k≥⌊loglogx⌋+1^23k#_Pk(x).

Now, we shall use Lemma 4 to deal with the first sum in the right hand side above. SinceG(z)converges uniformly and absolutely in any bounded set, we have_maxz∈[0,1]{|G(z)|}≤C, for some positive constant C. Now, by Lemma 4 forA=1, we get|G(_zk)|≤C(for_zk:=(k−1)/loglogx<1) and

∑k=1⌊loglogx⌋^23k#_Pk(x)≪∑k=1⌊loglogx⌋^23kG_zk·xlogx^{(loglogx)k−1}(k−1)!≪xlogx∑k≥1^{(log(logx)2/3)k−1}(k−1)!≪xlogxexp(log^(logx)2/3)=x^(logx)1/3.

Therefore,

∑k=1⌊loglogx⌋^23k#_Pk(x)≪x^(logx)1/3.

For the second sum in the right hand side of (6), we use that#_Pk(x)≤xto obtain

∑k≥⌊loglogx⌋+1^23k#_Pk(x)≪^23loglogxx,

where we used that⌊loglogx⌋+1>loglogx. Since3/2>e3, then

^32loglogx>^e(loglogx)/3=^(logx)1/3.

Thus

∑k≥⌊loglogx⌋+1^23k#_Pk(x)≪x^(logx)1/3.

By combining (6), (7) and (8), we obtain the desired result.

3.2. The Proof of Theorem 2

By the Prime Number Theorem, we have thatϑ(x)∼x. In particular, it holds thatϑ(x)≫x. Sinceϑ(x)=_∑p≤xlogp, then

_Zϑ(x)=∑p≤xz(p)≫∑p≤xlogp=ϑ(x)≫x,

where we used thatz(p)>logp/logα.

For the second part, sincez(p)≤p+1≤3p/2, then

_Zϑ(x)=∑p≤xz(p)≪∑p≤xp≪x∑p≤x1=xπ(x)≪^x2logx

as desired.

3.3. The Proof of Theorem 3

Note that, by Theorem 2, we have

_Zψ(x)≥_Zϑ(x)≫x.

For the second part, since there exist exactly⌊logx/logp⌋powers of p in the interval[1,x], we can write_Zψ(x)as

_Zψ(x)=∑p≤x∑r≤logxlogpz(^pr).

By using Lemma 1 (ii), we get

_Zψ(x)=∑p≤x∑r≤logxlogpz(^pr)≤∑p≤x∑r≤logxlogp(p+1)^pr−1≪∑p≤x∑r≤logxlogp^pr.

Note that_{∑r≤logxlogp} ^pr≤(^plogxlogp+1−1)/(p−1)≪x. Then,

_Zψ(x)≪∑p≤xx=xπ(x)≪^x2logx,

which completes the proof.

4. Conclusions

In this paper, we study some problems related to the order (of appearance) in the Fibonacci sequence, denoted byz(n). This arithmetic function plays an important role in the comprehension of some Diophantine problems involving Fibonacci numbers (the most important one is the open problem about the existence of infinitely many Fibonacci prime numbers). The problems are related to the growth of Fibonacci versions of well-known number-theoretic functions (related to the Prime Number Theorem) like the first and second Chebyshev functions,ϑ(x)=_∑p≤xlogpandψ(x)=_∑^pr≤xlogpand the harmonic functionH(x)=_∑n≤x1/n. These Fibonacci-like functions are defined as_Zϑ(x)=_∑p≤xz(p),_Zψ(x)=_∑^pr≤xz(^pr)and_ZH(x)=_∑n≤xz(n)/n. In particular, we shall find effective bounds for these three functions. The proofs combine elementary facts related toz(n)(such as Marques’ upper bounds) together with some deep tools from Analytic Number Theory (such as Abel’s summation formula and Sathé–Selberg formula).

Figure 1. The graphs of the functionsZH(x),Zϑ(x)andZψ(x)forx∈(0,500].

Funding

The author was supported by Project of Excelence PrF UHK No. 2213/2020, University of Hradec Králové, Czech Republic.

Acknowledgments

The author thanks the anonymous referees for their careful corrections and very helpful and detailed comments, which have significantly improved the presentation of this paper.

Conflicts of Interest

The author declares no conflict of interest.

References

1. Trojovský, P. On Diophantine equations related to order of appearance in Fibonacci sequence. Mathematics 2019, 7, 1073.

2. Lucas, E. Théorie des fonctions numériques simplement périodiques. Am. J. Math. 1878, 1, 289-321.

3. Sallé, H.J.A. Maximum value for the rank of apparition of integers in recursive sequences. Fibonacci Quart. 1975, 13, 159-161.

4. Marques, D. Sharper upper bounds for the order of appearance in the Fibonacci sequence. Fibonacci Quart. 2013, 51, 233-238.

5. Hast, D.R.; Matei, V. Higher Moments of Arithmetic Functions in Short Intervals: A Geometric Perspective. Int. Math. Res. Not. 2019, 21, 6554-6584.

6. Visser, M. Primes and the Lambert W function. Mathematics 2018, 6, 56.

7. Lagarias, J. An elementary problem equivalent to the Riemann hypothesis. Am. Math. Monthly 2002, 109, 534-543.

8. Sathé, L.G. On a problem of Hardy on the distribution of integers having a given number of prime factors. J. Indian Math. Soc. 1953, 17, 63-141.

9. Selberg, A.A. Note on a Paper by L.G. Sathe. J. Indian Math. Soc. 1954, 18, 83-87.

10. De Koninck, J.-M.; Luca, F. Analytic Number Theory-Exploring the Anatomy of Integers; American Mathematical Society: Providence, RI, USA, 2012.