Sz´ amelm´ eleti f¨ uggv´ enyek extrem´ alis nagys´ agrendje ´ th La ´szlo ´ Dr. To 2006
Bevezet´ es Ha sz´amelm´eleti f¨ uggv´enyek, pl. multiplikat´ıv vagy addit´ıv f¨ uggv´enyek nagys´agrendj´et vizsg´aljuk, akkor el˝osz¨or ´altal´aban az adott f¨ uggv´eny ´atlagos nagys´agrendj´et n´ezz¨ uk. Azt mondjuk, hogy f ´ atlagos nagys´ agrendje g, ha X X g(n), f (n) ∼ n≤x
n≤x
azaz f ¨osszegz´esi f¨ uggv´enye aszimptotikusan egyenl˝o g ¨osszegz´esi f¨ uggv´eny´evel, ahol g elemi f¨ uggv´enyekkel kifejezhet˝o ´es g-nek ismerj¨ uk az aszimptotikus viselked´es´et. P Tekints¨ uk pl. az f = σ f¨ uggv´enyt, ahol σ(n) = d|n d az n oszt´oinak ¨osszege. Akkor X
σ(n) ∼
n≤x
X π2 n, 6
n≤x
2
teh´at σ(n) ´atlagos nagys´agrendje π6 n, azaz ,,´atlagosan” n oszt´oinak sz´ama σ(n) ≈ 1, 644n. Hasonl´oan, ha f = ϕ az Euler-f¨ uggv´eny: ϕ(n) = #{k : 1 ≤ k ≤ n, (k, n) = 1}, akkor ebben az ´ertelemben ,,´atlagosan” ϕ(n) ≈ π62 n ≈ 0, 607n. Az ´atlagos nagys´agrend azonban csak el´egg´e pontatlan inform´aci´ot szolg´altat a f¨ uggv´eny viselked´es´ere vonatkoz´oan, nem mutatja ki azokat az ´ert´ekeket, amelyek nem tipikusak ´es amelyek ritk´an fordulnak el˝o. P oinak sz´ama, ´atlagos A τ oszt´of¨ uggv´enynek p´eld´aul, ahol τ (n) = d|n 1 az n oszt´ nagys´agrendje log n, ugyanakkor ,,majdnem minden” n-re τ (n) ≈ (log n)log 2 ≈ (log n)0,693 , ami a log τ (n) norm´alis nagys´agrendj´ere vonatkoz´o eredm´enyb˝ol k¨ovetkezik. A log n ´atlagos nagys´agrendet az az ar´anyaiban kis sz´am´ u n eredm´enyezi, amelyekre τ (n) sokkal nagyobb mint log n. (n) Azt mondjuk, hogy f norm´ alis nagys´ agrendje g, ha limstatn→∞ fg(n) = 1 (statisztikus hat´ar´ert´ek), azaz minden ε > 0 eset´en |f (n) − g(n)| < ε|g(n)| egy 1 s˝ ur˝ us´eg˝ u halmazon. Ha f nem korl´atos multiplikat´ıv f¨ uggv´eny ´es nem az n hatv´anya, akkor f -nek nem l´etezik n¨ovekv˝o norm´alis nagys´agrendje, l´asd B. J. Birch [B], 1967.1 Aσ´ es ϕ f¨ uggv´ enyek N´ezz¨ uk a σ ´es ϕ f¨ uggv´enyet. Ezekre σ(n) ≥ n + 1, φ(n) ≤ n − 1 minden n ≥ 2-re ´es az egyenl˝os´egek akkor ´es csak akkor igazak, ha n pr´ım. K´erd´es, hogy σ(n) ´es φ(n) az n-t˝ ol f¨ ugg˝oen milyen nagy, illetve milyen kicsi ´ert´ekeket vehet fel? 1 Ugyanakkor l´etezik addit´ıv f¨ uggv´enyek egy sz´eles oszt´ alya, amelyeknek van n¨ ovekv˝ o norm´ alis nagys´ agrendje.
1
1. T´ etel. L´eteznek olyan C1 ´es C2 pozit´ıv ´alland´ok, hogy minden n ≥ 2-re (1)
σ(n) < C1 n log n,
(2)
ϕ(n) > C2
n . log n
V´alaszthat´o C1 = 3 ´es C2 = 1/3. Bizony´ıt´ as. Minden n ≥ 2 eset´en σ(n) =
X
d=
Xn d|n
d|n
d
=n
X1 d|n
d
≤n
n X 1 < n(1 + log n) < 3n log n, k k=1
r r Y Y ϕ(n) Y 1 1 1 log 2 1 1 1 (1 − ) ≥ = )= ≥ ≥ > , (1 − ) ≥ (1 − n p pk k+1 r+1 2r 2 log n 3 log n p|n
k=1
k=1
ahol pk a k-adik pr´ım, r = ω(n) ´es haszn´altuk, hogy n ≥ 2r , log n ≥ r log 2. A C1 ´es C2 konstansok jav´ıthat´ok ha n ≥ 2, illetve ha n ≥ n0 . De enn´el l´enyegesebb k´erd´es, hogy jav´ıthat´ok-e az (1)-ben ´es (2)-ben szerepl˝o n log n ´es n/ log n f¨ uggv´enyek. Igazoljuk, hogy: 2. T´ etel. L´eteznek olyan C3 ´es C4 pozit´ıv ´alland´ok, hogy minden n ≥ 3-ra (3)
(4)
σ(n) < C3 n log log n,
ϕ(n) > C4
n . log log n
A (3) ´es (4) egyenl˝otlens´egeket egy er˝osebb eredm´enyb˝ol vezetj¨ uk le, amelyb˝ol az is k¨ovetkezik, hogy a jobb oldalon szerepl˝o f¨ uggv´enyek tov´abb nem jav´ıthat´ok. Maxim´ alis ´ es minim´ alis nagys´ agrend Bevezetj¨ uk a k¨ovetkez˝o fogalmakat: Defin´ıci´ o. Legyen f egy sz´amelm´eleti f¨ uggv´eny, g pedig egy n¨ovekv˝o f¨ uggv´eny, amelyre g(n) > 0, ha n ≥ n0 . Azt mondjuk, hogy f (egy) maxim´ alis (ill. minim´ alis) nagys´agrendje g, ha f (n) f (n) =1 ill. lim inf =1 . lim sup n→∞ g(n) n→∞ g(n) Itt az els˝o ¨osszef¨ ugg´es p´eld´aul azt jelenti, hogy i) minden ε > 0 eset´en l´etezik N (ε) u ´gy, hogy minden n ≥ N (ε)-ra f (n) < (1 + ε)g(n) ´es ii) minden ε > 0 eset´en f (n) > (1 − ε)g(n) v´egtelen sok n-re. 2
A g(n) f¨ uggv´eny nem egy´ertelm˝ uen meghat´arozott, szerepelhet benne egy 1-hez tart´ o t´enyez˝o. A σ(n) f¨ uggv´eny minim´alis nagys´agrendje n. Ez azonnali, mert σ(n) ≥ n, n ≥ 1 ´es minden p pr´ımre σ(p) 1 =1+ →1 (p → ∞). p p A ϕ(n) f¨ uggv´eny maxim´alis nagys´agrendje n. Ez is azonnali, mert ϕ(n) ≤ n, n ≥ 1 ´es minden p pr´ımre ϕ(p) 1 =1− →1 (p → ∞). p p ¨ nwall [G], 1913) A σ(n) f¨ 3. T´ etel. (T. H. Gro uggv´eny maxim´alis nagys´agrendje eγ n log log n, ahol γ az Euler-´alland´o. 4. T´ etel. (E. Landau [L], 1903) A ϕ(n) f¨ uggv´eny minim´alis nagys´agrendje e−γ n/ log log n, ahol γ az Euler-´alland´o. A 3. ´es 4. T´etelek k¨ovetkeznek az al´abbi eredm´enyb˝ol, amely a [TW] cikkben szerepl˝ o eredm´enyek speci´alis esete: 5. T´ etel. Legyen f ≥ 0 egy multiplikat´ıv sz´amelm´eleti f¨ uggv´eny ´es legyen Y 1 ρ(p) = sup f (pa ), ahol p pr´ım, R = 1− ρ(p). p a≥0 p Ha
−1 1) minden p pr´ımre ρ(p) ≤ 1 − p1 ´es
2) minden p pr´ımre l´etezik olyan ep kitev˝o, hogy log ep = o(log p) ´es f (pep ) ≥ 1 + p1 , akkor (5)
lim sup n→∞
f (n) = eγ R, log log n
azaz f (n) maxim´alis nagys´agrendje eγ R log log n. Bizony´ıt´ as. A felt´etelek miatt 1 + 1 p
1 p
≤ ρ(p) ≤
1−
1 p
−1
, ahonnan 1 −
1 p2
≤
1−
ρ(p) ≤ 1, ez´ert az R szorzat (abszol´ ut) konvergens.
Q A bizony´ıt´asban nem haszn´aljuk a pr´ımsz´aP mt´etelt. Elegend˝o a p≤x (1 − 1/p)−1 ∼ uggv´enyre vonatkoz´ o eγ log x, x → ∞, Mertens-k´eplet ´es θ(x) = p≤x log p Csebisev-f¨ θ(x) x ¨osszef¨ ubben igazolhat´ ok. Q ugg´es alkalmaz´asa, amelyek j´oval egyszer˝ Q Az n = pap sz´amot ´ırjuk fel n = n1 n2 alakban, ahol n1 = p|n,p≤log n pap (´es n2 -be ker¨ ul a t¨obbi pr´ımhatv´any). Akkor f (n1 ) ´es f (n2 ) ´ıgy becs¨ ulhet˝o: Y Y Y 1 −1 Y 1 ap f (n1 ) = f (p ) ≤ ρ(p) = 1− 1− ρ(p), p p p|n,p≤log n
p≤log n
p≤log n
p≤log n
ahonnan f (n1 ) ≤ 1 + o(1) eγ R log log n, haszn´alva a fenti Mertens-k´epletet. 3
n → ∞,
Megtehet˝o, hogy az n = n1 n2 alakban egy h(n) → ∞ n¨ovekv˝o f¨ uggv´enyt vesz¨ unk log n helyett, majd bel´atjuk, hogy h(n) = log n a megfelel˝o v´alaszt´as. Tov´abb´a, f (n2 ) =
Y
Y
f (pap ) ≤
≤ 1 + o(1) 1 −
1−
p|n,p>log n
p|n,p>log n
p|n,p>log n
Y
ρ(p) =
1 ρ(p) p
Y
1−
p|n, p>log n
1 −ω(n2 ) = 1 + o(1) eO(1/ log log n) = 1 + o(1), log n
1 −1 ≤ p
n → ∞,
ahol ω(n2 ) az n2 k¨ ul¨onb¨oz˝o pr´ımoszt´oinak a sz´ama ´es n ≥ n2 > (log n)ω(n2 ) alapj´an ω(n2 ) ≤ log n/ log log n. Teh´at (6) f (n) ≤ 1 + o(1) eγ R log log n, n → ∞. Most n´ezz¨ uk a ford´ıtott egyenl˝otlens´eget, pontosabban azt, hogy a lim sup el´erhet˝o. Azt fogjuk bel´atni, hogy a lim sup legal´abb (1 − ε)-szor annyi mint a t´etelben szerepl˝o. Adott ε > 0 eset´en legyen N olyan nagy, hogy Y
1 ) ≥ 1 − ε, p2
(1 −
p>N
´es p ≤ N eset´en v´alasszuk meg a kp kitev˝oket u ´gy, hogy Y Y f (pkp ) ≥ (1 − ε) ρ(p) p≤N
p≤N
Ha N ´es kp fixek, legyen x → ∞ ´es tekints¨ uk: Y Y pep . n(x) = pk p N
p≤N
Akkor Y Y Y Y 1 f n(x) = f (pkp ) f (pep ) ≥ (1 − ε) ρ(p) 1+ = p p≤N
= (1 − ε)
N
Y
1−
Y p
1−
N
Y 1 Y 1 −1 1 ρ(p) 1− 2 1− ≥ p p p p≤x
N
p≤N
≥ (1 − ε)
p≤N
1 p
ρ(p)
Y N
1 Y 1 −1 1− 2 1− ≥ p p p≤x
≥ (1 − ε)2 R(1 + o(1))eγ log x, haszn´alva ism´et a Mertens-k´epletet. Legyen E(x) = maxp≤x ep . Kapjuk, hogy X X X log n(x) ≤ kp log p+ ep log p ≤ O(1)+E(x) log p = O(1)+E(x)θ(x) xE(x), p≤N
p≤x
N
4
haszn´alva, hogy θ(x) x. A log ep = o(log p) felt´etelb˝ol log E(x) = o(log x) k¨ovetkezik ´es kapjuk, hogy log log n(x) ≤ O(1) + log E(x) + log x ≤ (1 + 2ε) log x, ha x el´eg nagy. K¨ovetkezik, hogy f (n(x)) ≥
(7)
(1 − ε)3 γ Re log log n(x). 1 + 2ε
A (6) ´es (7) ¨osszef¨ ugg´esek alapj´an a T´etel bizony´ıtott. Megjegyz´ es. A 3. ´es 4. T´etelek a k¨ovetkez˝o alakban is kimondhat´ok: min ϕ(n) ∼ e−γ x/ log log x.
max σ(n) ∼ eγ x log log x, n≤x
n≤x
Alkalmaz´ asok 1. Ha f (n) = σ(n)/n, akkor teljes¨ ulnek az 5. T´etel felt´etelei, mert 1 1 1 1 −1 σ(pa ) = 1 + + + · · · + < 1 − = ρ(p) pa p p2 pa p minden p pr´ımre ´es a ≥ 1-re, innen R = 1, tov´abb´a vehet˝o ep = 1, ´es kapjuk a (3) k´epletet. 2. Legyen f (n) = n/ϕ(n), akkor pa 1 −1 = 1 − = ρ(p) ϕ(pa ) p minden p pr´ımre ´es a ≥ 1-re, innen R = 1, vehet˝o itt is ep = 1, ´es kapjuk, hogy lim sup n→∞
n = eγ , ϕ(n) log log n
ami egyen´ert´ek˝ u a (4) k´eplettel. 3. M´as alkalmaz´asok is adhat´ok, pl. legyen f (n) = σ (e) (n)/n, ahol σ (e) P(n) az n exponenci´alis oszt´oinak az ¨osszege, amely multiplikat´ıv f¨ uggv´eny ´es σ (e) (pa ) = d|a pd . Most ρ(p) = 1 + p1 , ep = 2 ´es kapjuk, hogy (8)
lim sup n→∞
σ (e) (n) 6 = 2 eγ . n log log n π
Tov´ abbi megjegyz´ esek A fentekhez kapcsol´od´o eredm´enyek: 6. T´ etel. (G. Robin [R], 1984) Ha a Riemann-sejt´es igaz, akkor σ(n)/n < eγ log log n,
(9)
n ≥ 5041.
Ha a Riemann-sejt´es hamis, akkor (10)
σ(n)/n > eγ log log n,
v´egtelen sok n-re. 5
A σ(n)ϕ(n) ≤ n2 egyenl˝otlens´eg alapj´an σ(n)/n ≤ n/ϕ(n), n ≥ 1. Az n/ϕ(n) ´ert´ekeire vonatkozik a k¨ovetkez˝o 7. T´ etel. (J. L. Nicolas [N], 1983) Legyen pk a k-adik pr´ım ´es nk = p1 p2 · · · pk . Ha a Riemann-sejt´es igaz, akkor nk /ϕ(nk ) > eγ log log nk ,
(11)
k ≥ 1.
Ha a Riemann-sejt´es hamis, akkor (11) v´egtelen sok k-ra igaz ´es v´egtelen sok k-ra hamis. A τ f¨ uggv´eny minim´alis nagys´ agrendje g(n) = 2, mert τ (n) ≥ 2 minden n ≥ 2-re ´es τ (p) = 2 minden p pr´ımre. A τ f¨ uggv´eny maxim´alis nagys´agrendj´ere vonatkozik a k¨ovetkez˝ o: 8.
T´ etel. (S. Wigert [W], 1907) A log τ (n) f¨ uggv´eny maxim´alis nagys´agrendje azaz
log 2 log n log log n ,
(12)
lim sup n→∞
log τ (n) log log n = log 2. log n
Ez azt jelenti, hogy ha n ≥ N (ε), akkor τ (n) < exp((1 + ε) log 2 log n/ log log n) = 2(1+ε) log n/ log log n = n(1+ε) log 2/ log log n ´es v´egtelen sok n-re τ (n) > exp((1 − ε) log 2 log n/ log log n) = 2(1−ε) log n/ log log n = n(1−ε) log 2/ log log n . A 8. T´etelnek ´altal´anos´ıt´asa a k¨ovetkez˝o: 9. T´ etel. ([SS], 1975) Legyen f egy pozit´ıv f¨ uggv´eny, amelyre f (n) = O(nβ ), ahol β > 0 r¨ogz´ıtett. Legyen F olyan multiplikat´ıv f¨ uggv´eny, amelyre F (pa ) = f (a) minden pa (a ≥ 1) pr´ımhatv´anyra. Akkor (13)
lim sup n→∞
log F (n) log log n log f (a) = sup . log n a a≥1
Hivatkoz´ asok [B] B. J. Birch, Multiplicative functions with non-decreasing normal order. J. London Math. Soc., 42 (1967), 149151. [FS] J. Fabrykowski, M. V. Subbarao, The maximal order and the average order of the multiplicative function σ (e) (n), Th´eorie des nombres (Qu´ebec, PQ, 1987), 201-206, de Gruyter (Berlin – New York, 1989). ¨ nwall, Some asymptotic expressions in the theory of numbers, Trans. [G] T. H. Gro Amer. Math. Soc., 14 (1913), 113-122. [L] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig – Berlin, 1909. [N] J. -L. Nicolas, Petites valeurs de la fonction d’Euler, J. Number Theory 17 (1983), no. 3, 375-388. 6
[R] G. Robin, Grandes valeurs de la fonction somme des diviseurs et hypoth`ese de Riemann, J. Math. Pures Appl. (9) 63 (1984), no. 2, 187213. [SS] D. Suryanarayana, R. Sita Rama Chandra Rao, On the true maximum order of a class of arithmetical functions, Math. J. Okayama Univ., 17 (1975), 95-101. ´ th, E. Wirsing, The maximal order of a class of multiplicative arithmetical [TW] L. To functions, Annales Univ. Sci. Budapest., Sect. Comp., 22 (2003), 353-364. [W] S. Wigert Sur l’ordre de grandeur du nombre des diviseurs d’un entier, Arkiv. f¨ or Math. 3 (1907), 1-9.
7
