0/221/22

Számelmélet és valószínűségszámításRátz László Vándorgyűlés2021. július 3.

Freud Róbert
freudro8@gmail.com

2/22
A Csebisev-egyenlőtlenség két számelméleti alkalmazását mutatjuk
be, amelyek specmaton vagy erős szakkörön is tárgyalhatók. Azegyik Erdős Pál egy kedvenc problémájához kapcsolódik, a másikpedig Turán Pál egyszerű bizonyítása Hardy és Ramanujan hírestételére.
Mindkettő elmondható valószínűségszámítás nélkül is, de éppen avalószínűségi szemlélet mutatja meg a lényeget.

3/22
1. Csebisev-egyenlőtlenség (1867)
Informálisan: Egy valószínűségi változó nagy valószínűséggel avárható értékétől nem túl távoli értéket vesz fel. Itt a távolság„egysége” a szórás.
Pontosan: Ha a ξ valószínűségi változó várható értéke E és szórása
D, akkor tetszőleges c > 0-ra
1
P (|ξ − E| > cD) < 2 .
cEzt csak a legegyszerűbb, klasszikus valószínűségi mezőre fogjuk
alkalmazni, amikor ξ a v1 , v2 , . . . , vN értékek mindegyikét 1/N
valószínűséggel veszi fel. Ennek a speciális esetnek a bizonyítása
középiskolában is könnyen elmondható.

4/22

v1 + v2 + . . . + vNE=és D =Nazaz N E =PN

i=1 vi és N D =2r(v1 − E)2 + . . . + (vN − E)2,N

PN

2(v−E).
ii=1Legyen s, ahányszor |vi − E| > cD. Be kell látni, hogy s/N < 1/c2 .

2

ND =N
X
i=12(vi − E) >X|vi −E|>cD(vi − E)2 > s(cD)2 , így N > c2 s.

5/22
2. Csupa különböző összegErdős Pál egyik kedvenc problémája: Maximálisan hány pozitív egész adható meg n-ig, hogy közülük akárhány különbözőtösszeadva (beleértve az egytagú összegeket és az összes számösszegét is) mindig különböző számot kapunk?
Azaz 1 ≤ a1 < a2 < . . . < ak ≤ n, minden részösszeg különböző,mennyi a k maximuma (n függvényében)?
Ilyenek például a 2-hatványok, tehát max k ≥ 1 + ⌊log2 n⌋ > log2 n.

6/22Felső becslés: Megnézzük, hány részösszeg van és ezek milyen intervallumba eshetnek. Mivel minden részösszeg különböző egész szám,ezért legfeljebb annyi részösszeg lehet, mint amennyi az intervallum
hossza.
A részösszegek száma 2k − 1. Mindegyik legalább 1 és legfeljebbn + (n − 1) + . . . + (n − k + 1) ≤ nk − 1.

Minden részösszeg különböző, tehát 2k − 1 egésznek el kell férnie 1
és nk − 1 között. Ezért
2k − 1 ≤ nk − 1, azaz 2k ≤ nk.

7/22
2k ≤ nk.
Logaritmálva:(∗) k ≤ log2 n + log2 k ≤ 2 log2 n.
Ezt is logaritmálva:(∗∗) log2 k ≤ 1 + log2 log2 n.
(**)-ot beírva (*)-ba:k ≤ log2 n + log2 log2 n + 1.

8/22
Tehát
log2 n < max k < log2 n + log2 log2 n + 1.
max k
log2 log2 n + 11<.
<1+log2 nlog2 nmax klim= 1, azaz max k aszimptotikusan egyenlő log2 n-nel.
n→∞ log2 nErdős 500$: Igaz-e, hogy | max k − log2 n| korlátos?
Megjegyzés: Van a kettőhatványoknál eggyel(!) sűrűbb konstrukció,
ha n ≥ 221 .

9/22
A log2 log2 n-es hibatagot meg tudjuk felezni a Csebisev-egyenlőtlenséggel, ugyanis az összegek az [1, nk −1] intervallumban nem egyenletesen oszlanak el, hanem az átlag közelében sűrűbben helyezkednek el.
Legyen ξ az a valószínűségi változó, amelyik minden részösszeget(beleértve az üreset is) 1/2k valószínűséggel vesz fel.
Ez azt jelenti, hogy ξ egymástól függetlenül 1/2–1/2 valószínűséggelteszi be az összegbe az egyes aj -ket. Eszerint ξ az η1 , . . . , ηkfüggetlen valószínűségi változók összege, ahol ηj a 0 és aj értékeketPkveszi fel 1/2–1/2 valószínűséggel: ξ = j=1 ηj .
 a 2ajj
és D2 (ηj ) =.
Itt E(ηj ) =22

10/22

Ekkor E(ξ) =kX

E(ηj ) =kX
aj
j=1

j=1

2.

Ugyanez közvetlenül is adódik, ha minden részösszeget a komplementerével összepárosítunk, hf.
Szórás: D2 (ξ) =kX

D2 (ηj ) =j=1

Ez is megy közvetlenül, hf.

k Xaj 2
j=12kn2<.
411/22√
Tehát D(ξ) < n k/2.
Csebisev pl. c = 2-vel: Az átlagtól a szórás kétszeresénél távolabb
eső összegek száma kevesebb, mint az összes összeg számának anegyedrésze.
√3Tehát több, mint 2 · összeg esik egy 4D(ξ) = 2n k hosszúságú
4intervallumba, amelynek a középpontja E(ξ).
kEzek az összegek mind különbözők, így√√8n kk 3k
2 · < 2n k, azaz 2 <.
43Ezt a korábbihoz hasonlóan kétszer logaritmálva kapjuk, hogylog2 log2 nk < log2 n ++ 2.
2További érdekességek: Freud–Gyarmati: Számelmélet 12.1.

12/22
3. Tipikusan kb. hány prímosztója van egy számnak?
(Vázlat. Részletek: Számelmélet könyv 6.7.)
Legyen ω(n) az n pozitív egész különböző prímosztóinak száma.
Pl. ω(20) = 2, ω(64) = 1.
Kb. mekkora az ω(n) az n függvényében?
Végtelen sok n-re, a prímhatványokra ω(n) = 1.
De bármilyen nagy is lehet: az első s prím szorzatára ω(n) = s, pl.
ω(2 · 3 · 5 · 7 · 11 · 13 · 17 · 19) = ω(9699690) = 8.
Nem nagyon látszik semmi szabályosság.

13/22Belátjuk, hogy egy jól ismert, „szép” f (n) függvénnyel mégis teljesül, hogy a legtöbb számra ω(n) kb. f (n). A „legtöbb” és „kb.”
kifejezések persze pontos matematikai tartalmat jelentenek.
Legyen t egy tetszőleges (nagy) pozitív egész. Először kiszámítjuk,hogy ω(n) átlagosan mekkora 1 és t között:ω(1) + ω(2) + . . . + ω(t)
W (t)
E=.
=tt14/22
ω(1) + ω(2) + . . . + ω(t)
W (t)
E=.
=tt
W (t) becsléséhez tekintsük azt a t × t-es mátrixot, amelynek az iedik sorában az ω(i)-t „számoljuk meg”, azaz minden j-edik helyre
1-et írunk, ahol a j az i valamelyik prímosztója, a többi helyre
pedig 0 kerül. Pl. t = 6-ra:
1 2 3 4 5 6
ω(1) = 000

0 000

ω(2) = 1010 000ω(3) = 100

1 000

ω(4) = 10

10 000ω(5) = 1000 0

10ω(6) = 201

1 000

15/22Tehát az i-edik sor j-edik eleme 1, ha j prímszám és osztója i-nek,egyébként pedig 0.
Hány 1-es van a mátrixban?
Soronként összegezvePt

i=1 ω(i) = W (t).

Ha j = p prímszám, akkor a p-edik oszlopban a p többszöröseinekmás
megfelelő helyeken áll 1, tehát itt ⌊t/p⌋ darab 1-es van, mindenX telem 0. Így oszloponként összegezve az 1-esek száma, aholpp≤taz összegzés csak a prímekre történik. A továbbiakban p, q mindig
prímszámot jelöl.
Xt
Tehát W (t) =.
pp≤t16/22
Vagyis az ω(n) átlaga 1 ≤ n ≤ t-re Xt
1W (t)
E==tt

p≤tp



=

X1
p≤tp



 − h(t), ahol 0 ≤ h(t) < 1.

Mivel a prímek reciprokösszege t-ig kb. ln ln t, ezért az ω(n) átlagosan kb. ennyi. Vagyis egy 1 és t közötti egésznek átlagosanln ln t különböző prímosztója van. Pl. t = 10100 -ra ez 5,44.
√Az ln ln x függvény nagyon √lassan növekszik. Pl. ln ln t =ln(ln t/2) = ln ln t − ln 2, ezért t és t között csak ln 2 a növekedés.
Ezért az 1 és t közötti „majdnem minden” n esetén „kb. ln ln t”
helyett nyugodtan mondhatunk „kb. ln ln n”-et is.

17/22
Abból azonban, hogy ln ln n az átlag, nem következik, hogy alegtöbb esetben ehhez közeli a függvényérték, lehetnének nagy ingadozások és úgy jön ki ez az átlag. Hardy és Ramanujan bonyolult módszerekkel belátták (1917), hogy nem így van, a „legtöbb” nszámnak tényleg kb. ln ln n prímosztója van.
Turán Pál adott erre egy egyszerű bizonyítást (1934), amiben
tulajdonképpen a Csebisev-egyenlőtlenséget használta (anélkül,hogy ennek tudatában lett volna), és ez lett a kiindulópontja avalószínűségszámítás számelméleti alkalmazásainak.
Legyen ξ az a valószínűségi változó, amelyik az ω(1), . . . , ω(t)értékek mindegyikét 1/t valószínűséggel veszi fel. Ekkor ennek
E ≈ ln ln t várható √értékét számoltuk ki. Belátjuk, hogy kicsi aszórás, kisebb, mint 3E. Ekkor a Csebisev-egyenlőtlenség
szerint√
ξ-nek E-től való eltérése nagy valószínűséggel E egy konstansszorosánál kisebb, azaz valóban majdnem minden n-nek kb. ln ln nkülönböző prímosztója van.

18/22
A szórás kiszámítása heurisztikusan (Gyenes Zoltán javaslata):A ξ változót fel tudjuk bontani prímenkénti indikátorváltozók
összegére. Legyen p prím és κp értéke 1/p valószínűséggel 1 („aszám osztható p-vel”) és (p −P1)/p valószínűséggel 0 („a szám nemosztható p-vel”). Ekkor ξ = p≤t κp .

Az összes pozitív egészre nézve a κp változók függetlenek. Ugyanis a különböző prímekkel való oszthatóságok a páronként relatív
prímség miatt egymástól függetlenek. Formálisan: a p-vel való oszthatóság valószínűsége 1/p és a p1 , . . . , pr prímek mindegyikével valóoszthatóság ugyanaz, mint a N = p1 · . . . · pr szorzattal való oszthatóság, tehát ennek a valószínűsége 1/N , ami valóban az 1/pi
valószínűségek szorzata.

19/22ξ=X

κp ;κp = 1 valószínűsége 1, κp = 0 valószínűsége 0.

p

1
E(κp ) =p

és1
D (κp ) =p2

p−1
p2

 2
p−1 1
1
1+= − 2.
ppp p

„Kicsit” csalva tekintsük úgy, hogy a κp változók elég nagy t-re az 1
és t közötti egészekre szorítkozva is függetlenek maradnak. Ekkor
D2 (ξ) =Xp≤t

D2 (κp ) =X1p≤tp−X 1p≤tp2≈ E.

20/22
A szórás pontosan: D (ξ) = E (ξ − E)
22E(ξ ) =tX
1t i=12ω (i) =2tX
1t i=1

ω(i)

X
p|i

= E(ξ 2 ) − E 2 .
1 XX
ω(i) =1=tp≤t p|i


1X X
1X X
1 + ω(v) =ω(vp) ≤=ttp≤t v≤t/pp≤t v≤t/p
 X
1t
1X X=+ω(v).
tptp≤tp≤t v≤t/p

Az egyenlő(tlen)ségek magyarázata rendre: deﬁníció — az (egyik)
ω(i)-re beírjuk a deﬁníciót — összegátrendezés — oszthatóságátírása — egy számot egy prímszámmal szorozva legfeljebb eggyel
nő a prímosztók száma — szétvágjuk az összeget két részre.

21/222E(ξ ) ≤ X
1tt

p≤t

1X X+
ω(v).
pt
p≤t v≤t/pAz első tag E. A második tag második szummája az átlagértéknéllátottak szerint$ t %X tXX ⌊p⌋tX1.
<<ω(v) =qpqpqv≤t/pq≤t/pq≤t/pq≤tTehát a teljes második tag kisebb, mint
X 21p≤tp

2= E + h(t) = E 2 + 2h(t)E + h2 (t) < E 2 + 2E.

Így E(ξ 2 ) < E 2 + 3E és D2 = E(ξ 2 ) − E 2 (ξ) < E 2 + 3E − E 2 = 3E.