SZAKDOLGOZAT
Prímszámok viselkedésének összehasonlítása véletlen változokkal rövid intervallumokon
Pejó Balázs
Témavezető: Sándor Csaba Ph.D. egyetemi docens BME Matematika Intézet, Sztochasztika Tanszék
BME 2012
Tartalomjegyzék 1. Bevezetés
4
2. Cramér-modell
5
2.1. A modell ismertetése . . . . . . . . . . . . . . . . . . . . . . .
5
2.2. A modell használata . . . . . . . . . . . . . . . . . . . . . . .
7
3. A prímszámok rövid intervallumokon
9
3.1. Mertens formula . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. Buchstab tétel . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3. ω(u) oszcillálása . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4. Maier eredménye . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5. Modell prímjei rövid intervallumkon . . . . . . . . . . . . . . . 26 4. Az eredmény általánosítása
29
5. Összegzés
32
"It’s evident that the primes are randomly distributed but, unfortunately, we don’t know what ’random’ means." R.C.Vaughan (1990)
1. Bevezetés A szakdolgozat fő témája a prímek elhelyezkedése, s modellezése véletlen sorozatokkal. Az eredeti Cramér-modellel foglalkozunk, s megemlítünk néhány alkalmazási területet (Fermat-, Mersenne-prímek), ugyanakkor felhívjuk a figyelmet a modell hibáira is (pl. páros prímek). Ezek után a prímszámok eloszlását vizsgáljuk meg tüzetesebben rövidebb intervallumokon. Ezen szakaszban részletezzük Buchstab eredményét, mely az Eratosztenészi szita általánosítása, Gallagher eredményét a prímek számára a számtani sorozatokban, Mertens formulát, és annak jelentőségét, végül ezek felhasználásával Helmuth Maier eredményét, mely megmutatja, hogy a prímek száma rövid intervallumokon eltér a Cramér-modell által megjósolttól. Továbbá a fent említett rövid intervallumokra igaz eredményeket (Buchstab, Maier) álltalánosítjuk számtani sorozatok rövid intervallumaira, s így új eredményt kapunk, mely hasonlóan eltérést mutat a valóság és a modell között.
4
2. Cramér-modell 2.1. A modell ismertetése Harald Cramér (1893-1985) -ről elnevezett modellt ő alkotta az 1930-as években. Célja az volt, hogy a valoszínűségszámításban elért eredményeket fel tudja használni a prímszámok viselkedésének vizsgálata során. 1. Tétel (Prímszámtétel, Hadamard & de la Vallée-Poussin, 1896). Z x X dt x π(x) = 1∼ ∼ = li(x) log(x) 2 log(t) p≤x Ebből látható, hogy a prímek x körül
1. ábra.
x , log(x)
1 log(x)
"sűrűséggel" vannak.
π(x) és a li(x)
1. Definíció (Cramér-modell). Legyen ξn (3 ≤ n ∈ N ) független valoszínűségi változók, és P(ξn = 1) =
1 log(n)
P(ξn = 0) = 1 −
Azaz a modellben egy 3 ≤ n ∈ N szám
5
1 log(n)
1 log(n)
valószínűséggel lesz "prím".
• ξn várható értéke: 1 1 1 E(ξn ) = 1 +0 1− = log(n) log(n) log(n) • A k-adik modellbeli prím m, ha m X
ξn = k és
n=3
m−1 X
ξn = k − 1
n=3
(Az első m − 2 Bernulli eloszlású váltózó k darab 1-est tartalmaz, míg az első m − 3 változó csak k − 1 -et.) 2. Tétel (Cramér-modell). Px n=3 ξn =1 =1 P lim x→∞ π(x) Bizonyítás. x
Z π(x) ∼ 2
dt ∼ log(t)
Z 3
x
x
x
X 1 X dt ∼ = E(ξn ) log(t) n=3 log(n) n=3
A nagy számok erős törvénye alapján a véletlen változó, és a várható értékének a hányadosa 1 kell hogy legyen (mert a szórás véges), ha x → ∞. Részletesebb bizonyítás a 17 tételben található, ahol a tétel helyességét rövid intervallumokra bizonyítjuk.
2. ábra. π(x) és a
x X
ξn egy lehetséges implementációja 200 illetve 2000-ig
n=3
6
2.2. A modell használata A modell sok nevezetes prímszámsejtést erősít meg, ezek közül kettőt ismertetek, a Fermat- és Mersenne-prímek számára vonatkozóakat. n
• Fermat-prímek (Fn = 22 + 1) A legnagyobb ismert Fermat-prím 2012-ben az F4 , és 4 < n ≤ 32-re Fn öszetett szám, bár csak n ≤ 11-re ismert azok prímfelbontása. Így a sejtés nyílván az, hogy véges sok ilyen alakú prím van. Ezt a modellünk igazolja, ugyanis 1
1 1 = n n 2 + 1) log(2 ) 2 log(2) P A Borel-Cantelli lemma szerint, Ai események esetén ha P(Ai ) < ∞, P(ξFn prím) =
∼
log(22n
akkor véges sok Ai esemény következik be. Ha Ai az az esemény, hogy az i-edik Fermat-szám prím, akkor ∞ X
P(ξFn prím) =
∞ X n=1
n=1
∞
1 X 1 = 2n log(2) log(2) n=1
n 1 1 <∞ = 2 log(2)
Így csak véges sok Fermat-prím létezhet. • Mersenne-prímek (Mp = 2p − 1) A sejtés szerint végtelen sok ilyen alakú prím van, ahol p prím (2012-ben 47 darab ilyen alakú prím ismert, a legnagyobb a p = 43.112.609-hez tartzik). P(ξMp prím) =
1 1 1 ∼ = p p log(2 − 1) log(2 ) p log(2)
És innen adódik, hogy X X P(ξMp prím) = p prím
X 1 1 1 = =∞ p log(2) log(2) p prím p p prím
És mivel azok az események, hogy két Mersenne-szám prím-e, független, így alkalmazható ismét a Borel-Cantelli lemma, mely szerint végteles sok ilyen alakú prím van.
7
Ugyanakkor a modellnek vannak hibái is, így nem jelenthető ki, hogy igaz a fenti állítások, csak az, hogy megerősiti a már meglévő sejtseket. A legszembetűnőbb különbség például, hogy a modellünkben asszimptotikusan egyenlő a páros és páratlan prímek száma, míg a valódi prímekre ez nyílván nem igaz. Általánosabban megfogalmazva: • Valódi prímek #{pn ≤ x; a ≡ pn mod m} =1 x−→∞ #{pn ≤ x; b ≡ pn mod m} lim
∀0 ≤ a, b < m esetén, ha (a, m) = (b, m) = 1. • Modell prímjei lim
x−→∞
#{pn ≤ x; a ≡ pn mod m} =1 #{pn ≤ x; b ≡ pn mod m}
∀0 ≤ a, b < m esetén. Azaz míg a valódi prímek a redukált maradékosztályokban helyezkednek el egyenletesen, addig a modell prímjei az összes maradékoszályban teszik ugyanezt.
8
3. A prímszámok rövid intervallumokon Ebben a részben a lim
π(x + Φ(x)) − π(x) Φ(x) log(x)
x→ ∞
=1
asszimptótikát kielégitő Φ(x) függvényt keressük, azaz azt a függvényt, mely az (x, x+Φ(x)) intervallum prímjeinek a számára ad formulát. [1]-ből tudjuk, hogy Φ(x)-re alsó korlát a Φ(x) = log(x)
log(log(x)) log(log(log(log(x)))) (log(log(log(x))))2
ugyanis ekkor az asszimptotika már nem igaz. A felső korlátot [2]-ből ismer23
jük: Φ(x) = x 42 esetén szintén hamis az állítás. A Riemann hipotézis egy 1
élesebb felső korlátot indukál: Φ(x) = x 2 + . Mi Helmuth Maier eredményével [3] foglalkozunk bővebben, mely a Φ(x) = logλ0 (x) választással mutatja meg, hogy lim sup x→∞
π(x + Φ(x)) − π(x) Φ(x) log(x)
> 1 > lim inf
π(x + Φ(x)) − π(x) Φ(x) log(x)
x→∞
ha λ0 > 1. A tétel az alábbi kvantitatív formában is igaz: ha 1 < λ0 < eγ , akkor lim sup x→∞
π(x + Φ(x)) − π(x) Φ(x) log(x)
>
eγ λ0
ahol γ az Euler konstans. E tétel bizonyításához szükségünk van Mertens, Gallagher és Buchstab eredményeire.
9
3.1. Mertens formula Mertens formula segítségével elő lehet állítani az Euler konstanst prímszámok segítségével. Ezelőtt egyik előállítási mód sem használta a prímeket ehhez. Néhány, ezek az előállítási módok közül: 2. Definíció (Euler-Gamma). Z 1 Z x Z ∞ x X 1 dn 1 −x −γ log log e log(x)dx = − e = − =− dx n n x 0 0 1 | 1 {z } log(x)
eγ = 1, 781 . . .
γ = 0, 577 . . .
e−γ = 0, 561 . . .
3. Tétel (Mertens formula). Y 1 e−γ W (x) := 1− ∼ p log(x) p<x Bizonyítás. ! Y Y 1 1 −γ log(x) ∼ e ⇒ log log(x) ∼ log(e−γ ) = −γ 1− 1− p p p<x p<x {z } | P 1 log 1− +log(log(x)) ( ) p<x p Belátjuk, hogy ez a kifejezésnek létezik határértéke, ha x → ∞. Azt, hogy ez az Eulergamma, nem áll módunkban bebizonyítani e szakdolgozat keretein belül (A teljes bizonyítás megtalálható [4]-ban). Mivel ∞ ∞ ∞ X X xk 1 1 1 X 1 log(1 − x) = − = − . , így log 1 − =− − kk kk k p p p p k=1 k=1 k=2 Ha most a log(log(x))-es tagtól eltekintünk, akkor a kifejezés a következőképpen írható: ! X ∞ ∞ X X 1 XX 1 1 X 1 1 log 1 − = − − =− − k p p k=2 p k p p<x k=2 pk k p<x p<x p<x • A kifejezés második tagja konvergens, mert ∞ ∞ XX XX X 1 1 X 1 1 1 < = = < 1 kk k 21− p p p p(p − 1) p p<x k=2 p<x k=2 p<x p<x x x X X 1 1 1 1 1 1 1 = − = 1 − + − + ··· − < 1 n(n − 1) n=2 n − 1 n 2 2 3 x n=2
10
∞ XX 1 Tehát = C1 pk k p<x k=2
• A kifejezés első tagját az Abel-átrendezés segítségével átalakítjuk. 4. Lemma (Abel-átrendezés). an valós sorozat, f (x) analitikus függX vény, C, D ∈ Z + , továbbá A(N ) := an . Ekkor n≤N
X
Z
D
an f (n) = A(C)f (C) − A(D)f (D) − C
C≤n
Így f (n) = n1 , f 0 (n) =
A(t)f 0 (t)dt
−1 ,C n2
= 2, D = x, an = 1 ha n prím, és 0 egyéb-
ként, így A(n) = π(n). Ezeket használva az Abel-formula a következőt adja: Z x X 1 X −1 1 1 π(t) 2 dt = = an f (n) = π(2) − π(x) − p c≤n
3.2. Buchstab tétel Az ókori görögországban már ismert volt eljárás a prímszámok megtalálására. Eratosztenészról elnevezett szita a következőképpen működik: írjuk fel x -ig a pozitív, 1-nél nagyobb egész számokat. Karikázzuk be a legkisebb bekarikázatlan számot, s annak többszöröseit. Ezt hajtsuk végre addig, amíg √ van x-nél kisebb bekarikázatlan szám. Ezzel a módszerrel megtaláljuk az √ összes prímet ( x, x) között. 3. Definíció (Általánosított szita). Nem
√
x-ig, hanem egy másik számig (y)
futtajuk az algoritmust. Ekkor azokat a számokat kapjuk meg, melyek relatív prímek az összes y-nál kisebb számmal. Φ(x, y) = #{n ∈ N : n ≤ x, p(n) ≥ y} ahol p(n) jelöli az n legkisebb prímosztóját. Erre a függvényre igaz az alábbi állítás: 5. Lemma (Indukció). ∀y < z esetén Φ(x, y) = Φ(x, z) +
X
Φ
y≤p
x ,p p
Bizonyítás. Legyen p prímet követő prím p0 . Ekkor Φ(x, p) − Φ(x, p0 ) = #{np ≤ x : p(np) ≥ p} = x #{n ≤ : p(n) ≥ p} = Φ p
x ,p p
Innen már adódik az állítás, ha az összes prímre átírjuk a Φ-t a kérdéses intervallumban. Φ(x, y)-re előszös Buchstabnak sikerült asszimptotikát adni, egy róla elnevezett függvény segítségével.
12
4. Definíció (Buchstab függvény). Legyen ha u ≤ 1
ω(u) = 0 ω(u) =
1 u 0
ha 1 < u < 2
(uω(u)) = ω(u − 1) ha 2 ≤ u Még mielött rátérnénk a fő állításra, vizsgáljuk meg ω(u) tulajdonságait.
3. ábra. ω(u) és az e−γ 6. Lemma (Buchstab függvény lapossága). ω(u)0 = O (Γ(u + 1)−1 ), ahol Γ az Gamma függvény. Bizonyítás. u > 2 esetén (uω(u))0 = ω(u − 1) ⇒ ω 0 (u) =
1 (ω(u − 1) − ω(u)) u
Ekkor ∃c ∈ [u−1, u] : ω 0 (c) = ω(u)−ω(u−1). Legyen M (u) := supt>u {|ω 0 (t)|}. |ω 0 (u)| =
1 0 1 1 |ω (c)| ≤ max {|ω 0 (t)|} ≤ M (u − 1) u u t∈[u−1,u] u
Ha v > u, akkor |ω 0 (v)| ≤ v −1 M (v − 1) ≤ u−1 M (u − 1), de ez minden v ≥ u -ra igaz, így M (u) ≤ u−1 M (u − 1). S innen már indukcióval adódik az állítás. 13
7. Lemma (Buchstab függvény konvergenciája). lim ω(u) = e−γ
u→∞
Bizonyítás. A bizonyítás megtalálható [5]-ben. E két lemma alapján a Buchstab függvény faktoriális gyorsasággal konvergál a határértékéhez, amit a 3. ábra is jól szemléltet. Most pedig térjünk rá a tételre [6]. 1
8. Tétel (Buchstab tétel). Legyen U>1 fix és x U ≤ y ≤
x , log(x)
továbbá
1 u
y = x . Ekkor Φ(x, y) ≈ ω(u)
x log(y)
Bizonyítás. Teljes indukcióval bizonyítunk. 1 < u ≤ 2 esetén 1
1
x2 ≤ y = xu ≤
x . log(x)
Φ(x, y) = π(x) − π(y) − O(1) = x x x y x +O = +O − = log(x) log(x)2 log(y) log(x) log(x)2 x 1 x x x +O +O = ω(u) u u1 log(x) log(x)2 log(y) log(x)2 Mert O
y log(y)
≤O
x log(x)
1 2
log(x)
=O
x log(x)2
.
Tehát u < 2-re igaz az állítás. Most használjuk az indukciós feltevést: u ∈ [N, N + 1], akkor 10 x u x ≤y=x ≤p<x ⇒p ≤x≤p ⇒p= ⇒ p 1 x log(x) log(p) = 0 log ⇒ u0 log(p) = log(x) − log(p) ⇒ u0 = −1 u p log(p) 1 N +1
1 u
1 N
N
N +1
14
1
ahol u0 ∈ [N − 1, N ]. Ekkor az indukciós lemma szerint, ha z = x N , akkor Φ(x, y) = x X x x p 0 Φ(x, z) + Φ , p = ω(N ) + ω(u ) = p log(z) log(p) y≤p
x u ≤p<x N 1
1
1
Ezt külön meg kell vizsgálni N = 2 esetén. x 3 ≤ y = x u ≤ p < x 2 . 1
1
Φ(x, z) = Φ(x, x N ) = Φ(x, x 2 ) =
x log(x)
x x x = 12 2 log(x) = ω(2)2 log(x) = ω(N )N log(x) ,
azaz az első felét megkaptuk. Most vizsgáljuk meg a szummában lévő kifejezést. Φ
x ,p = Φ p
10 ! x x x x u p p +O = , 2 x p p log p log x p
0
mert 1 < u ≤ 2. Most irjuk vissza elé a szummát. X X X x x x +O Φ ,p = 2 x p √ √ √ x y≤p< x y≤p< x p log y≤p< x p log p p
• Nézzük meg először a hibatagot: X X 1 x x x = 2 ≤ 2 ≤ 1 2 log(x) √ √ √ √ √ p x x 3 3 4 y≤p< x p log p x≤p< x p log p x≤p< x X 1 √ √ 4x X 1 = 4x (log(log( x))−log(log( 3 x))) = − 2 2 log(x) log(x) √ p √ p p< x p< 3 x 4x x ((c1 + log(log(x))) − (c2 + log(log(x)))) = O log(x)2 log(x)2 X
• Most nézzük meg a főtagot: X x x = = √ p log x √ p(log(x) − log(p)) y≤p< x y≤p< x p X X x 1 x log(x) = ω −1 log(x) log(p) √ p log(p) √ p log(p) −1 X
y≤p< x
log(p)
y≤p< x
15
Azaz a formula igaz N = 2 esetén. Most vizsgáljuk meg a többi esetben is. Az első taggal nem kell foglalkozni(az indukció miatt), csak a szummás kifejezéssel. Használjuk az Abel-átrendezést a következő alakban: 1 1 X X an f (n) = A(n)(f (n)−f (n+1))+A(y)f (y)−A x N f x N 1
1
y≤n<x N
y
1 Legyen f (n) = ω − 1 n log(n) 2 és an = log(n) ha n prím, egyébként 0. √ X X Ekkor A(N ) = an = log(p) = N + O e−C log(x) . A lapossági lemlog(x) log(n)
n
p
ma alapján ω(u) − ω(u + 1) = O(1). Az Abel-átrendezésben a szummában lévő kifejezést egyszerűsítsük le: A(n)(f (n) − f (n + 1)) ∼ log(x) 1 1 nω −1 − = log(n) n log(n)2 (n + 1) log(n + 1)2 (n + 1) log(n + 1)2 − n log(n)2 log(x) −1 ∼ nω log(n) n(n + 1) log(n)2 log(n + 1)2 log(n)2 log(x) −1 nω log(n) n2 log(n)4 És most foglalkozzunk maga a szummával. X
ω
1 y
log(x) 1 −1 = log(n) n log(n)2 dt
Z
1 xN
ω
y
log(x) z }| { v= log(t) Z u log(x) 1 1 t log(t)2 z}|{ −1 dt = ω(v − 1) dv = log(t) t log(t)2 t log(t)2 log(x) N Z u 1 1 (vω(v))0 = (uω(u) − N ω(N )) log(x) N log(x)
16
Most már csak a határok kell átalakítani. 1 1 A(y)f (y) − A x N f x N = yω
1 log(x) log(x) 1 1 − 1 −1 − xN ω 2 log(y) y log(y) log x N
1 1 2 ≤ 1 N x log x N 1 1 x c1 1 2 − c2 1 2 ≤ O log(x)2 u log x log x N
Mindezeket összerakva x +x Φ(x, y) = ω(N )N log(x) ω(N )N
X
ω
1 1 x u ≤p<x N
1 log(x) −1 = log(p) p log(p)
x 1 x x +x (uω(u) − N ω(N )) = uω(u) = ω(u) log(x) log(x) log(x) log(y)
Azaz az indukciós elv segítségével beláttuk, hogy Buchstab formulája helytálló minden x, y ∈ R esetén.
17
3.3. ω(u) oszcillálása Mielött rátérnénk Maier eredményére, be kell bizonyítanunk, hogy ω(u) ∀a ≥ 2 esetén [a−1, a] intervallumon "megkerüli" e−γ -t. Ehhez pedig további lemmákra van szükségünk.
4. ábra. ω(u) és az e−γ Legyen Z h(u) :=
∞
Rx
e−ux−x+
0
e−t −1 dt t
dx
0
9. Lemma (H analitikus, ha u > −1). 10. Lemma (uh0 (u − 1) + h(u) = 0). Bizonyítás. 0
Z
h (u − 1) =
∞
e
−ux+
e−t −1 dt 0 t
Rx
0 dx
0
Z = 0
Foglalkozzunk −h0 (u − 1)-el.
18
∞
(−x)e−ux+
Rx 0
e−t −1 dt t
dx
Z
∞ −ux xe | {z } e|
0
Rx 0
xe−ux e−ux R x e−t −1 dt − 0 t − 2 dx = } e| {z } − u u | {z } g
e−t −1 dt t
{z
f0
∞
g
f
0
Z 0
∞
xe−ux e−ux R x e−t −1 dt e−x − 1 − 0 t − 2 dx e u | {z u } | {z x } g0
f
Most foglalkozzunk külön-külön a kapott részekkel. Az elejénlévő rész a behelyettesítés után 1 1 0 − 0 − 2 e0 = 2 u u Most bontsuk 3 részre az integrálandó kifejezést ∞
xe−ux e−ux R x e−t −1 dt e−x − 1 − 2 e0 t dx = − − u u x 0 Z Z −1 ∞ −ux R x e−t −1 dt e−x −1 ∞ −ux R x e−t −1 dt −1 0 t xe e xe e 0 t − dx − dx− u 0 x u 0 x Z ∞ R x e−t −1 0 −1 −ux e e 0 t dt 2 u 0 Z
• Első tag Z Z h(u) −1 ∞ −ux R x e−t −1 dt e−x 1 ∞ −ux−x+R x e−t −1 dt 0 0 t t − xe e dx = e dx = u 0 x u 0 u • Második tag h(u−1)
−1 − u
Z 0
∞
xe−ux e
e−t −1 dt 0 t
Rx
−1 1 dx = − x u
19
zZ 0
∞
}| e−(u−1)x−x+
e−t −1 dt 0 t
Rx
{ dx
• Harmadik tag ∞
R x e−t −1 0 −ux e|{z} e 0 t dt = 0 {z } n | m0 ∞ m m n z n0 }| { z }| { Z ∞ z}|{ }| { z R −t 1 −ux R x e−t −1 dt −ux 0x e t−1 dt 0 t e e − (−u)e e = u2 0
−1 − 2 u
Z
0
1 −1 h(u − 1) 1 h(u − 1) = (0 − 1) + + u2 u u2 u Ezeket felhasználva az egész kifejezés h(u) h(u − 1) −1 h(u − 1) h(u) 1 + − + 2 + = 2 u u u u u u
−h0 (u − 1) =
És ez pont a bizonytandó kifejezés átrendezett alakja. 11. Lemma (h(u) → u1 ). Bizonyítás. Első lépésben vágjuk szét az integrálandó intervallumot két részre. Z
∞
h(u) =
e−ux−x+
Rx 0
e−t −1 dt t
dx =
0 √1 u
Z
e
R −ux−x+ 0x
e−t −1 dt t
∞
Z
e−ux−x+
dx +
Rx 0
e−t −1 dt t
dx
√1 u
0
• Első rész Mivel eO(x) = 1 + O(x) ha x → 0, így O(x)
zZ Z
√1 u
−ux−x+
e 0
0
x
e−(u+1)x −(u+1)
√1
u
}| { z }| 0 { e−t − 1 Z √1 dt u 1 t dx = 1 + O √ e−(u+1)x dx = u 0 1 u→∞ e−(u+1) √u 1 1 1 − z}|{ ∼ 1+O √ + u{z+ 1 } u + 1 u u | {z } | →0
→1
20
• Második rész <0
zZ Z
x
∞ −ux−x+
e
0
}| { e−t − 1 zZ dt t dx <
√1 u
e−(u+1)x −(u+1)
∞ √1 u
}|
∞
−(u+1)x
e
{ dx = 0 +
√1 u
−(u+1) √1u
e
u+1
A második részt dominálja az első ha u → ∞, így a határérték tényleg u1 . 12. Tétel (Előjelváltás). ω(u) − e−γ függvény előjelet vált minden [a − 1, a] inrervallumon, ha a ≥ 2. Bizonyítás. Legyen Z
a
ω(u)h(u)du + aω(a)h(a − 1)
f (a) = a−1
f 0 (a) = ω(a)h(a) − ω(a − 1)h(a − 1) + ω(a − 1)h(a − 1) + aω(a)
−h(a) =0 a
Tehát f konstans midnenhol. Tudjuk, hogy ω(u) → e−γ , így Z a ω(u)h(u)du + aω(a)h(a − 1) = lim a→∞ a−1 Z a 1 1 a −γ lim e−γ du + ae−γ = e−γ (log(a) − log(a − 1)) + e ∼ e−γ a→∞ a−1 u a−1 a−1 Így f ≡ e−γ . Definiáljuk g-t a következő modon: Z a g(u) = h(u)du + ah(a − 1) a−1
Ekkor g 0 (a) = 0∀a > 0 adódik. Mivel az integrálrész a végtelenben eltűnik, csak a másik tag játszik szerepet, aminek meg 1 a határértéke, ebből kapjuk, hogy a g konstans 1. Most kombináljuk össze f -et és g-t a következő modon: Z a (ω(u) − e−γ )h(u)du + (ω(u) − e−γ )ah(a − 1) = 0 a−1
Mivel h > 0, így vagy ω ≡ e−γ [a − 1, a]-n, vagy a ω(u) − e−γ függvény előjelet vált [a − 1, a]-n. Az első felvetés nyílván nem igaz ∀a esetén, így csak az maradt, hogy ∀[a − 1, a] intervallumot köteles előjelet váltani a függvényünk.
21
3.4. Maier eredménye Maier tételének bizonyításához a fent említett tételeken kívül szükségünk van további lemmákra. 5. Definíció (Jó modulus). q > 0 jó modulus, ha L(s, χ) 6= 0 az összes mod q karakterre, és ∀s ∈ R esetén σ >1−
C log(|q(|t| + 1)|)
Ez a definíció C-től függ. Y Legyen P (z) = p, azaz a z-nél kisebb prímek szorzata. p
13. Lemma (Létezés). Van olyan C > 0 konstans, hogy tetszőlegesen nagy z esetén P (z) jó modulus. Bizonyítás. A bizonyítása megtalálható [7]-ban. Jelölje π(x, q, a) azon prímek számát x-ig, melyek kielégítik a p ≡ a mod q egyenletet. 14. Lemma (Gallagher). √ 1 cD − log(x) π(x + h, q, a) − π(x, q, a) = (li(x + h) − li(x)) 1 + O e + e ϕ(q) ahol (a, q) = 1, x ≥ q D és
x 2
≤ h ≤ x.
Bizonyítás. E lemma bizonyítása teljes mértékben a [7]-ban található. Mi csak azt bizonyítjuk be, hogy li(x + h) − li(x) ∼
22
h log(x)
ha
x 2
≤ h ≤ x.
li(x + h) − li(x) = x+h x+h x x +O − +O = log(x + h) log(x) log2 (x + h) log2 (x) (x + h) log(x) − x(log(x + h)) x = +O log(x) log(x + h) log2 (x) h log(x) + O(x) x +O log(x)(log(x) + O(1)) log2 (x) mert log(x + h) = log(x) + log(x + h) − log(x) = log(x) + log 1 + hx = log(x) + O(1). h log(x) + O(x) x +O = log(x)(log(x) + O(1)) log2 (x) x h O(x) + +O = 1 log(x) (log(x) + O(1)) log2 (x) log(x) 1 + O log(x) x 1 h x h +O = +O 1 log(x) 1 + O log(x) log2 (x) log2 (x) log(x)
15. Tétel (Maier tétel). lim sup x→∞
π(x + logλ (x)) − π(x) logλ (x) log(x)
> 1 > lim inf
π(x + logλ (x)) − π(x)
x→∞
logλ (x) log(x)
ha λ > 1. Továbbá, ha 1 < λ0 < eγ , akkor lim sup x→∞
eγ π(x + logλ (x)) − π(x) > log(x)λ−1 λ0
Bizonyítás. Legyen D ≥ D0 , mely kielégíti a Gallagher-lemmát, illetve legyen C a Létezés lemmát kielégítő konstans. Ekkor minden z-hez tartozó P (z) jó modulus, ha z > eCD (z → ∞).
23
Válasszunk továbbá egy U (z) ≤ P (z) valós számot. Most definiáljuk az alábbi mátrixot: M = 1 + (P (z)D−1 + 1)P (z) 1 + (P (z)D−1 + 2)P (z) .. . 1 + (P (z)D−1 + P (z)D−1 )P (z)
...
U (z) + (P (z)D−1 + 1)P (z)
... ...
U (z) + (P (z)D−1 + 2)P (z) .. .
...
U (z) + (P (z)D−1 + P (z)D−1 )P (z)
azaz M = (ars ), ahol ars = s + rP (z), és az indexek az alábbiak szerint futnak: 1 ≤ s ≤ U (z), P (z)D−1 < r ≤ 2P (z)D−1 . Ekkor egy sor U (z) hosszú intervallum, míg egy oszlop P (z)D−1 elemű, P (z) differenciájú számtani sorozat. Jelölje π(M ) a prímek száma a mátrixban. Nyílvánvaló, hogy csak az olyan ars lehet prím, ahol (s, P (z)) = 1. Tehát csak bizonyos oszlopokban lehetnek prímek, nevezzük ezeket az oszlopokat jó oszlopoknak. Gallagher tétel miatt egy jó oszlopban a prímek száma: π(2P (z)D + s, P (z), s) − π(P (z)D + s, P (z), s) = 1 P (z)D (1 + O(e−CD )) ϕ(P (z)) log(P (z)D + s) Felhasználva a ϕ(P (z)) = P (z)W (z) és a log(P (z)D ) ≥ log(P (z)D + s) ≥ log(2P (z)D ) = log(2) + log(P (z)D ) azonosságokat, kapjuk, hogy 1 P (z)D (1 + O(e−CD )) = D ϕ(P (z)) log(P (z) + s) P (z)D−1 (1 + O(e−CD )) W (z) log(P (z)D ) Válasszuk U -t a következőképpen: U (z) = [z λ1 ] ahol λ1 > λ0 . Ekkor a (s, P (z)) = 1 kifejezés épp a Φ(z λ1 , z) darab s esetén lesz igaz, azaz a jó oszlopok száma Φ(z λ1 , z). Tehát π(M ) = Φ(z λ1 , z)
P (z)D−1 (1 + O(e−CD )) W (z) log(P (z)D )
24
A prímszámtételből levezethető, hogy z ∼ log(P (z)). Így az egyenlet π(M ) = Φ(log(P (z))λ1 , log(P (z)))
P (z)D−1 (1 + O(e−CD )) W (log(P (z))) log(P (z)D )
alakot ölti. Ha most Buchstab és Mertens eredményét felhasználjuk a következő formában: lim Φ(z λ , z) z→∞
log(z) = ω(λ) zλ
lim W (z) log(z) = e−γ z→∞
⇒ lim Φ(z λ , z)z −λ W −1 (z) = ω(λ)eγ z→∞
akkor
P (z)D−1 π(M ) = log(P (z))λ1 eγ ω(λ1 )(1 + O(e−CD )) D log(P (z) )
M -nek P (z)D−1 sora van, így van olyan sor, ahol minumum log(P (z))λ1 γ e ω(λ1 )(1 + O(e−CD )) log(P (z)D ) darab prím van. Osszuk ezt a sort log(P (z)D )λ0 darab intervallumra. Ekkor létezik olyan részintervallum, mely log(P (z))λ1 γ e ω(λ1 ) log(P (z)D ) log(P (z))λ1 log(P (z)D )λ0
(1 + O(e−CD )) =
log(P (z)D )λ0 γ e ω(λ1 )(1 + O(e−CD )) log(P (z)D )
darab prímet tartalmaz. Most térjünk vissza, a bizonyítandó állításhoz. Eddig a tört számlálójával foglalkoztunk. Most osszuk el a nevezővel. log(P (z)D )λ0 −1 eγ ω(λ1 )(1 + O(e−CD )) log(rP (z))λ0 −1 Mivel log(P (z)D ) ≤ log(rP (z)) ≤ log(2P (z)D ) = log(2) + log(P (z)D ), így a leosztás után eγ ω(λ1 )-t kapunk, ami az előjelváltás lemma miatt λ1 -től függően, hol nagyobb, hol kisebb mint egy. Tehát adtunk olyan log(x)λ hosszú sorozatot, ahol a prímek számának a hányadosa log(x)λ−1 -val nagyobb, illetve kisebb mint egy. A tétel 3. része ω(u) =
25
1 u
-ból következik, ha 1 < u ≤ 2.
3.5. Modell prímjei rövid intervallumkon Maier bebizonyította, hogy a lim
π(x + logλ (x)) − π(x) x→ ∞ logλ−1 (x)
π(x + logλ (x)) − π(x)
= lim
logλ (x) log(x)
x→ ∞
kifejezésnek nem létezik határértéke λ > 1 esetén (néha nagyobb, néha kisebb, mint 1). A Cramér modell viszont egy valószínűséggel egyet ad határértéknek. Az állítás belátásához szükségünk van a Chernoff-egyenlőtlenségre. 16. Tétel (Chernoff-egyenlőtlenség). Ha p1 , . . . , pn ∈ [0, 1], továbbá p ezek számtani átlaga, X1 . . . , Xn független valószínűségi változók, melyek ∀i ∈ [1, n] esetén P(Xi = 1 − pi ) = pi , P(Xi = −pi ) = 1 − pi . Ekkor E(Xi ) = 0. n X Legyen X = Xi , így E(X) = 0. Ha a>0, akkor i=1 −a2
P(X > a) < e 2pn
+
a3 2(pn)2
−a2
P(X < −a) < e 2pn
A véletlen prímek számának várható értéke (x, x + log(x)λ ) között x+[log(x)λ ]
X
x+[log(x)λ ]
X
E(ξn ) =
n=x
n=x
1 ∼ log(n) x+[log(x)λ ]
X n=x
1 1 = log(x)λ = log(x)λ−1 log(x) log(x)
17. Tétel (Cramér). Px+log(x)λ P
lim
x→ ∞
! Px+log(x)λ ξ ξ n n n=x n=x = lim Px+log(x) =1 =1 λ λ−1 x ∞ → log (x) E(ξ ) n n=x
26
5. ábra.
x X
x X
E(ξn ) és
n=3
ξn egy lehetséges kimenetelének a hányadosa
n=3
Bizonyítás. Módosítsuk ξn valószínűségi változóinkat, hogy alkalmazhassuk x+log(x)λ X Xn , a Chernoff egyenlőtlenséget. Legyen Xn = ξn − E(ξn ) és X = n=x
továbbá pi =
1 log(i)
P Xi = 1 −
és p = 1 log(i)
1 . log(x)
Ekkor
−1 P Xi = log(i)
1 = log(i)
=1−
1 log(i)
n = log(x)λ , s ezekből következik, hogy E(Xi ) = E(X) = 0. • Ekkor az egyik egyenlőtlenség a következő képpen írható: P
x+log(x)λ
x+log(x)λ
X
X
n=x
ξi −
−a2 1
2 log(x)λ ⇒ E(ξi ) < −a < e log(x)
n=x
Px+log(x)λ P
n=x
ξi
log(x)λ−1
27
a −1<− log(x)λ−1
!
−a2
< e 2 log(x)λ−1
Legyen a = log(x)λ−1 így Px+log(x)λ n=x
P
ξi
log(x)λ−1
! − 1 < −
<e
−2 log(x)λ−1 2
=
2 log(x)λ−2 − log(x) 2
e
λ−2 2 log(x) 2 1 = x
Alkalmazni szeretnénk a Borel-Cantelli lemmát, azaz szeretnénk, hogy a fenti kifejezés összegezhető legyen (különböző x-ekhez tartozó intervallumok esetén), amit a √
>
2 log(x)
λ log(x) 2
2 log(x)λ−2 2
> 1 feltétel garantál. Ezt az összes
kielégíti, legyen például =
2 log(x) λ
. Ha λ > 2 akkor → 0,
log(x) 2
azaz ekkor véges sok esetben következik be az az esemény, hogy a véletlen prímek száma és a várható értékük hányadosa nagyobb, mint 1 + . λ
• A másik egyenlőtlenség a = 2 log(x) 2 -el a következő alakot ölti: λ λ x+log(x)λ X −(2 log(x) 2 )2 (2 log(x) 2 )3 λ + λ−1 λ−1 λ−1 2(log(x) )2 P ξi − log(x) > 2 log(x) 2 < e 2 log(x) n=x
Egyszerűsítsük, majd ossszuk le az egyenlőtlenséget a fenti módon: Px+log(x)λ P
n=x
ξi
log(x)λ−1
! − 1 > 2 log(x)
1− λ 2
< e−2 log(x)+4 log(x)
2− λ 2
=
λ
1 log(x) 2 −1 log(x)1− λ2 1 4 log(x)1− λ2 −2+ 1c c x < x = x x2 x2 λ
Mert ha λ > 2, akkor 4 ≤
log(x) 2 −1 . c
λ
1
Továbbá 2 log(x)1− 2 → 0 és x−2+ c
összegezhető, ha c > 1, azaz beláttuk az állítás másik felét is, azaz a hányados véges sokszor van 1 − alatt. E két részt összetéve megkapjuk a bizonyítandó állítást.
28
4. Az eredmény általánosítása Maier eredménye a prímek eloszlásról szól rövid intervallumokon. Most mi ezt általánosítjuk számtani sorozatok rövid intervallumaira. Ehhez az általánosításhoz szükségünk van általánosítani egy két segédlemmánkat is, mintpéldául Buchstab tételét. 18. Tétel (Prímszámtétel számtani sorozatokra, de la Vallée-Poussin). p≡a(m)
X
1 = π(x, m, a) ∼
p<x
1 x ϕ(m) log(x)
• Buchstab tétel számtani sorozatokra 6. Definíció (Φ sorozatokra). Φa,m (x, y) = #{n : n ∈ N, n ≡ a mod m, n ≤ x, p(n) ≥ y} 1
ha (a, m) = 1 és y = x u . 19. Tétel (Buchstam tétel sorozatokra). Φa,m (x, y) ∼
ω(u) x ϕ(m) log(y)
ha u > 1, és a, m rögzített. Bizonyítás. A bizonyítás az eredeti Buchstab tétel bizonyítása alapján történik. Egy lépés kivételével működnek ebben az esetben is az akkor használt lépések. 20. Lemma (Indukciós lemma sorozatokra). y < z < x esetén X x Φa,m (x, y) = Φa,m (x, z) + Φap−1 ,m ,p p y≤p
mod m maradékosztályban.
29
Bizonyítás. Legyen p-t követő prím (maradékosztálytól függetlenül) p0 . Ekkor Φa,m (x, p) − Φa,m (x, p0 ) = #{np ≤ x : p(np) ≥ p, np ≡ a mod m} = x x −1 #{n ≤ : p(n) ≥ p, n ≡ ap mod m} = Φap−1 ,m ,p p p Ebből már adódik az állítás. A módosított lemmánk segítségével könnyen belátható a Buchstab tétel számtani sorozatokra, ugyanis a maradékosztálytól független Φ, így az, hogy a lemmában változik a maradékosztály, nem befolyásol semmit.
• Maier eredményéne számtani sorozatokra
A tétel ebben az esetben a következőképpen néz ki: 21. Tétel (Maier tétel sorozatokra). ∀(λ, m, a) > 0 esetén lim sup x→∞
π(x + logλ (x), m, a) − π(x, m, a) logλ−1 (x) ϕ(m)
1 > lim inf
>1
π(x + logλ (x), m, a) − π(x, m, a)
x→∞
logλ−1 (x) ϕ(m)
ha x → ∞ és (a, m) = 1. Bizonyítás. A modosított indukciós lemma segítségével teljesen analóg módon bizonyítható, mint az eredeti tétel. • Véletlen modell számtani sorozatokra
Mivel az eredeti modellben a "prímek" nincsenek tekintettel a és m viszonyára, így modosítanunk kell azt a következőképpen: 30
7. Definíció (Cramér modell sorozatokra). Fix a és m esetén 0 P(a + km prím) = P(ξa+km = 1) =
m 1 ϕ(m) log(a + km)
0 és ξa+km a többi esetben 0.
A valószínűsége annak, hogy egy szám prím legyen, az eredeti modellhez képest meg van szorozva 1 <
m -el, ϕ(m)
ami vezethez ahhoz, hogy P(a +
mk prím) > 1, ezért itt is van egy m-től függő határ(c) (az eredeti modellben n = 3), melynél kisebb számok nem lehetnek potenciális "prímek". De így csak véges sok tagot hagyunk el a sorozatunk elejéről, így az asszimptotika továbbra is fennáll. 22. Tétel (Cramér modell sorozatokra). P x−a 0 m ξa+km k= c−a m P = 1 = 1 π(x, m, a) Bizonyítás. A számlálóban megintcsak a nevező várható értékével asszimptotikus, így hasonló módon bizonyítható, mint az eredeti modell, illetve a 17 tétel. Az új modellünk rövid intervallumokon való viselkedésének a vizsgálata során hasonlóan járhatunk el, mint az eredeti vizsgálatánál, ugyanis amikor a Px+log(x)λ
n=x lim Px+log(x) λ
x→ ∞
n=x
ξn
ahol n ≡ a mod m
E(ξn )
hányadost vizsgáljuk, mind a számláló, mind a nevező kap egy szorzófaktort.
31
m -es ϕ(m)
5. Összegzés Tehát megismertük a Cramér modellt, annak előnyeit és hátrányait, s megvizsgáltuk tüzetesebben a Maier különbségét a modell és a valóság között. Ezalatt megismerkedtünk Buchstab, Mertens, Galagher, és sok már matematikus eredményével. Ezt követően álltalánosítottuk Maier eredményét a modell egy kis változtatásával számtani sorozatokra. Köszönetnyílvánítás Köszönöm Sándor Csabának a segítségét az eredmények feldolgozásában, illetve azok általánosításában.
32
Hivatkozások [1] R.A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13, 242-247, (1938). [2] Janos Pintz & Henryk Iwaniec, Primes in short intervals, Mh. Math. 98, 115-143, (1984). [3] Helmut Maier, Primes in short intervals, Michigan Math. J. Volume 32, Issue 2, 221-225, (1985). [4] A. E. Ingham, The distribution of prime numbers,London, p. 22, (1932).
[5] N. G. de Bruijn, On the number of uncancelled elements in the sieve of Eratosthenes, Netherl. Akad. Wetensch. Proc. 53, 803-812, (1950). [6] A. A. Buchstab, Asymptotic estimates of a general number theoritic function, Math. -Sb. (N.S.) 2(44), 1239-1246, (1981). [7] H. Maier, Chains of large gaps between consecutive primes, Adv. in Math. 39, (1981). [8] Andrew Granvilley, Harald Cramér and the distribution of prime numbers, Department of Mathematics, University of Georgia, Athens, GA, 30602, USA
33
