Cím: Problémák és eredmények a prímszám-elméletben
Szerző(k):  Pintz János 
Füzet: 1977/december, 197 - 206. oldal  PDF file
Témakör(ök): Egyéb írások

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

1. A prímszámok számáról

 

A prímszám fogalmát már a görögök is ismerték. Euklidész könyvében szerepel, de valószínűleg Eratoszthenésztől (i. e. 276‐195) származik annak bizonyítása, hogy a prímszámok száma végtelen.* Tegyük fel ugyanis, hogy csak véges sok prímszám lenne, mégpedig p1, p2, ..., pk. Ekkor az
A=p1p2...pk+1(1.1)
szám nem lenne osztható a p1, ..., pk prímek egyikével sem (hanem 1 maradékot adna). De ez ellentmond annak, hogy minden számnak van prímosztója. (A bizonyítás a számelmélet alaptételének azon könnyebb részét használja fel, hogy minden szám előáll prímszámok szorzataként. Az alaptétel másik, lényegesen mélyebb része, hogy a fenti előállítás a tényezők sorrendjétől eltekintve egyértelmű, nem szükséges a bizonyításhoz.) Egy másik bizonyítás Eulertől (1707‐1783) a 18. századból származik. Tegyük fel ismét, hogy csak véges sok prím létezik. Legyenek ezek p1, p2,..., pk. Ekkor az
S=(1+1p1+1p12+...)(1+1p2+1p22+...)...(1+1pk+1pk2+...)(1.2)
szorzat elvégzésével a tagok
1p1α1p2α2...pkαk(αi0)(1.3)
alakúak lesznek, és minden ilyen típusú tag fellép, mégpedig pontosan egyszer. Így a számelmélet alaptétele szerint minden természetes szám reciprokát (pontosan egyszer) megkapjuk, tehát
S=n=11n.(1.4)

De a természetes számok reciprokösszegéből álló ún. harmonikus sor divergens, míg az (1.2) szorzat egy-egy tényezője a végtelen mértani sor összegképlete szerint 11-1pi, így az (1.2) szorzat értéke
S=1(1-1p1)...(1-1pk)(1.5)
egy adott véges szám. Ez az ellentmondás igazolja állításunkat.
Ebből a gondolatból levezethető az is, hogy a prímszámok reciprokösszege "végtelen'', azaz a
p1p(1.6)
sor divergens*. Ez azt jelenti, hogy a prímszámok elég sűrűn helyezkednek el a természetes számok között, hisz például a négyzetszámok száma is végtelen, de a
n=11n2(1.7)
összeg értéke véges. (Elég könnyen belátható, hogy az (1.7) összeg értéke 2-nél kisebb. Pontos értéke π26.)
Egy más irányú tétel viszont kimondja, hogy a prímszámok nincsenek túl sűrűn az egész számok között, nevezetesen az x-ig terjedő prímek számát π(x)-szel jelölve
limxπ(x)x=0.(1.8)
Másképp az összes természetes számnak csak "0 %-a'' prím. Ennek bizonyítása (amelyet a későbbiekben vázolunk) azon alapszik, hogy ha nagyon sok prím lenne egy adott határig, akkor utána majdnem minden szám osztható lenne ezek valamelyikével, tehát nem lehetne prím. Így érdekes módon fel fogjuk használni, hogy elég sok prím van, nevezetesen hogy
p(1-1p)=deflimni=1n(1-1pi)=0.(1.9)
Ugyanis, ha az (1.2)‐(1.5)-ben vázolt módon járunk el, de az összes prímet figyelembe vesszük, akkor az (1.4) összeg végtelen volta miatt azt kapjuk, hogy
1p(1-1p)=,(1.10)
azaz (1.9) valóban fennáll.
Legyen most
x=Mp1p2...pn(Mpozitív egész).(1.11)
Ekkor könnyen láthatóan azon x-nél kisebb számok száma, amelyek nem oszthatók a p1, ..., pn prímek egyikével sem (tehát amelyek szóba jönnek egyáltalán prímként az első n adott prímen kívül):
πn(x)=xi=1n(1-1pi)π(x)-n.(1.12)
Ezt (1.9)-cel összevetve adódik (1.8). Természetszerűleg vetődik fel a kérdés, hogy vajon mi a π(x) valódi nagyságrendje (hogy x-hez képest elhanyagolható, azt a fentiekből már tudjuk).
Legendre (1752‐1833) 1798-ban megjelent számelméleti könyvében azt a sejtést mondja ki, hogy*
π(x)Axlogx+B,(1.13)
ahol A=1 és B-1,0836. Ezen sejtést a néhány százezerig meglevő prímszámtáblázatok támasztották alá.
Ha a kisebb szerepet játszó B értékét nem vesszük figyelembe, akkor Legendre sejtése a határérték fogalmának felhasználásával
π(x)xlogx1,hax(1.14)
alakban írható.
C. F. Gauss (1777‐1855) már 15‐16 éves korában, 1792-93-ban foglalkozott a prímszámok eloszlásának empirikus tanulmányozásával, és azt az érdekes összefüggést találta, hogy az x nagyságú számok között átlagosan minden logx-edik szám prím, másképp ő a
π(x)lix=def2nx1logn(1.15)
közelítést találta. Némi számolással igazolható, hogy
lixxlogx1,hax,(1.16)
és így Gauss sejtése is az (1.14) formulát szolgáltatja.
Legendre-hoz hasonlóan azonban Gauss sem tudott semmit bizonyítani. Az előbb említett ifjúkori sejtését is csak 72 éves korában, 1849-ben, egy levélben említi. Valóban, Legendre és Gauss sejtése után kb. fél évszázaddal semminemű eredmény nem volt az (1.13)‐(1.16) sejtésekkel kapcsolatban, habár Gauss, a matematika fejedelme, éppen a számelmélet terén érte el legragyogóbb eredményeit.
 


2. Csebisev tételei
 

Az (1.14) formula másképp megfogalmazva azt állítja, hogy tetszőleges ε>0 esetén
(1-ε)xlogx<π(x)<(1+ε)xlogx,(2.1)
ha x meghalad egy ε-tól függő x0(ε) alsó korlátot.
P. L. Csebisev (1821‐1894) 1850-ben igen nagy lépést tett (1.14), azaz (2.1) igazolása felé. Bebizonyította ugyanis, hogy π(x) valódi nagyságrendje valóban xlogx, pontosabban, hogy x>x0-ra fennáll a
0,92129xlogx<π(x)<1,10556xlogx(2.2)
egyenlőtlenség. Azaz (2.1), ha nem is akármilyen kis pozitív ε-ra, de ε>0,08-ra már fennáll, azaz π(x) értéke ,,92 %-os pontossággal'' valóban xlogx.
A (2.2) formulából egyszerűen adódik a Csebisev-tételnek nevezett állítás*, mely szerint tetszőleges n természetes számra n és 2n között létezik prím. Ez ugyanis a
π(2n)-π(n)>0(2.3)
egyenlőtlenséget jelenti. Mármost egyszerűen látható, hogy ha n>n0 (adott alsó korlát), akkor (2.2) szerint
π(2n)-π(n)>0,922nlog2n-1,11nlogn>0.(2.4)
n<n0-ra az állítás prímszámtáblázat segítségével ellenőrizhető. A tételt szokás Bertrand-féle posztulátumnak is nevezni, mert az összefüggést Bertrand (1826‐1900) fedezte fel, de igazolása először Csebisevnek sikerült.
Csebisev bizonyítása (2.2)-re elemi eszközökkel történt, de meglehetősen bonyolult. Az alábbiakban vázolunk egy hasonló jellegű, de egyszerűbb utat, melyen keresztül egy adott c konstanssal a
π(x)<cxlogx(2.5)
becslés nyerhető. A következő, Erdős Páltól és Kalmár Lászlótól (1905‐1976) származó, újabb keletű bizonyítás lényege a
pnp<4n(2.6)
egyenlőtlenség, mely teljes indukcióval igazolható.
Páratlan n-ről páros (n+1)-re lépve az állítás nyilvánvalóan igaz marad. Páros n=2m-ről (2m+1)-re lépve viszont elég a
m+2p2m+1p<4m(2.7)
egyenlőtlenséget igazolni, hisz ez az indukciós feltevésből (n=m+1-re) adódó
pm+1p<4m+1(2.8)
egyenlőtlenséggel együtt valóban (2.6)-t adja n=2m+1-re. Másrészt a (2.7)-ben szereplő prímek mindegyike fellép a
(2m+1m)=(2m+1m+1)(2.9)
binomiális együtthatóban, így
m+2p2m+1p12[(2m+1m)+(2m+1m+1)]12i=02m+1(2m+1i).(2.10)
A jobb oldali összeg viszont a binomiális tétel szerint éppen
12(1+1)2m+1=1222m+1=4m,(2.11)
tehát (2.7), és így (2.6) is valóban teljesül.
(2.6)-ból már elég könnyen levezethető a (2.5) becslés. (Némi ügyeskedéssel bármilyen c>log4 elérhető x>x0(c) esetén.)
Csebisev másik érdekes eredménye, hogy ha π(x)xlogx-nek létezik határértéke x esetén, akkor a határérték csak 1 lehet. Ennek igazolásához felhasználta Euler (1707‐1783) ötletét, mely szerint u>1 esetén a
ζ(u)=defn-11nu(2.12)
konvergens sor által értelmezett függvény u=1 közelében felvett értékeiből bizonyos következtetést nyerhetünk a prímszámok eloszlására. Ugyanis (1.2)‐(1.5)-höz hasonlóan a számelmélet alaptétele szerint
ζ(u)=n=11nu=p(1+1pu+1p2u+...).(2.13)
A jobb oldali végtelen sok tényező mindegyikét a végtelen mértani sor összegképlete szerint összeadva adódik az igen fontos
ζ(u)=n=11nu=p11-1pu(2.14)
összefüggés.
 


3. Riemann-féle zétafüggvény
 

A fenti (2.14) formulából már látható az a meglepő dolog, hogy a prímszámok, tehát bizonyos diszkrét, különálló mennyiségek viselkedése kapcsolatban áll a ζ(u) folytonos valós függvény bizonyos tulajdonságaival. Ennél még megdöbbentőbb viszont az a tény, hogy (1.14) igazolásában a döntő lépés az volt, hogy az előbb bevezetett (2.12)-beli ζ(u) függvényben a változó legyen egy tetszőleges komplex szám, és ezen komplex függvény tulajdonságaiból következtessünk a prímszámok eloszlására. Ez a korszakalkotó gondolat B. Riemann (1826‐1866) érdeme, aki 1859-ben, akadémiai székfoglaló előadásában íly módon vázolt egy utat (1.14) bizonyításához. Ez a zseniális, 9 oldalas értekezés, (amely Riemannak egyébként egyetlen számelméleti munkája) talán az egész matematika történetében a legkitűnőbb dolgozat, annak ellenére, hogy (1.14)-et nem bizonyítja, ill. a vázolt gondolatmenet tele van bizonyítatlan feltevésekkel és megalapozatlan eljárásokkal. Ez a dolgozat indította el a komplex függvénytan több ágának mélyreható vizsgálatát, és így igen nehéz analitikus problémák megoldása után J. Hadamard (1865‐1963) és CH. J. De la Vallée Poussin (1866‐1962) kb. egy évszázaddal Legendre sejtésének kimondása, és csaknem 30 évvel Riemann értekezése után, 1896-ban egyidejűleg, egymástól függetlenül, bizonyította (1.14)-t, az ún. prímszámtételt.
 


4. A Riemann-sejtés
 

A következő probléma, hogy vajon milyen pontosan közelíti a π(x)-t xlogx, másképp, mit mondhatunk a
Π(x)-xlogx(4.1)
különbség nagyságáról. Már Riemann kiderítette, hogy az xlogx függvény helyett célszerűbb a Gauss által talált, (1.15)-ben definiált lix függvénytől vett eltérést vizsgálni.
Riemann 1859-es értekezésében kimondott egy híres sejtést, mely szerint ζ(s) komplex függvény összes komplex gyökének valós része 12. (Az eredeti, (2.12) formula ugyan csak olyan s számokra konvergens, amelyek valós része 1-nél nagyobb, de a ζ(s) függvény bizonyos módon értelmezhető valamennyi komplex számra az 1 kivételével.)
A Riemann-sejtés ma talán az egész matematika leghíresebb problémája. A sejtés döntő jelentősége, hogy következik belőle a
|Π(x)-lix|<cxlogx(4.2)
becslés (c egy adott konstans), tehát hogy a lix közelítő formula hibája legfeljebb x nagyságrendű (a logx faktortól eltekintve). Érdemes megemlíteni, hogy a (4.2) becslésből következik a Riemann-sejtés, azaz (4.2) ekvivalens a Riemann-sejtéssel. Elektronikus számítógéppel történő vizsgálatok igazolták, hogy ha a gyököket képzetes részük abszolút értékének növekvő sorrendjében rendezzük, akkor az első 3,5 millió gyök valóban a Res=12 (Re olvasd: s valós része) egyenesen helyezkedik el, ami mindenesetre a sejtés helyességét támasztja alá. Habár Riemann csak az első 6 gyököt számította ki, de mint hagyatékának rendezése közben talált jegyzetei tanúsítják, mélyebb oka is volt a sejtés kimondására. A Riemann-sejtés valamelyest a "bölcsek köve'' szerepét játssza a számelméletben, ugyanis helyességének igazolása egy csapásra igen sok, ettől (látszólag vagy valóban) távol álló probléma megoldását szolgáltatná (köteteket tesz ki azon cikkek száma, amelyek így kezdődnek: "tegyük fel, hogy a Riemann-sejtés helyes''). A bizonyítására irányuló kísérletek azonban az eltelt csaknem 120 évben kudarcot vallottak.
Felmerül a probléma, hogy vajon mi lehet a legjobb hibatag, tehát lehetséges-e az |π(x)-lix| mennyiségre x-nél is jobb felső becslés, pl. x4. Erhard Schmidt bizonyította be a századforduló táján, hogy a legjobb lehetséges hibatag x, azaz a Riemann-sejtés az elképzelhető legjobb becslést szolgáltatja.
Az |π(x)-lix| mennyiség felső becslése rendkívül fontos a számelmélet szempontjából. Már 3 évvel a prímszámtétel igazolása után, 1899-ben sikerült De la Vallée Poussinnek a
|π(x)-lix|<xelogx(4.3)
egyenlőtlenség bizonyítása. Az itt álló
xelogx(4.4)
hibatag kisebb nagyságrendű, mint akármiyen nagy N-re az
xlogNx(4.5)
mennyiség; de másrészt nagyobb, mint bármilyen kis konkrét δ>0-ra az
x1-δ(4.6)
kifejezés.
Ezek után a 20. században megkísérelték a (4.3) becslés élesítését. A probléma roppant nehézségét jelzi, hogy az eltelt csaknem 80 év alatt 4‐5-ször is megjavították ugyan a hibatagot, de egy (4.6) típusú hibatagtól még mindig reménytelenül messze vagyunk. A máig legjobb eredmény az 1958-ban Korobov és Vinogradov által bizonyított következő becslés
|π(x)-lix|<xe(logx)3/5.(4.7)
Tehát a 20. század mindössze egy tizeddel tudta a logx kitevőjét javítani.
 


5. Az analitikus számelmélet fő problémái
 

D. Hilbert (1862‐1943) az 1900-as Párizsi Matematikai Világkongresszuson 23 híres problémát vetett fel, amelyeknek megoldását a 20. vagy azt követő századoktól várta. A problémák közül a 8. probléma valójában 3 hihetetlen nehézségű számelméleti probléma, melyek közül az első, legfontosabb (és valószínű legnehezebb) a már említett Riemann-sejtés. Ezzel kapcsolatban mondta Hilbert, hogy ha ezer év múlva feltámadna, első kérdése az lenne, hogy eldöntötték-e már a Riemann-hipotézis helyességét. A második számelméleti kérdés az ugyancsak híres Goldbach-sejtés. Goldbach (1690‐1764) egy 1742-ben Eulerhez írt levelében szerepel az a kérdés, vajon igaz-e, hogy minden 2-nél nagyobb páros szám előállítható 2 prímszám összegeként? A sejtésnek egy gyengített változata szerint minden 5-nél nagyobb páratlan szám előáll 3 prímszám összegeként. Az első változat a binér, a második a ternär Goldbach-sejtés nevet viseli. A harmadik, Hilbert által felvetett számelméleti probléma arra vonatkozik, vajon végtelen sok ikerprímpár van-e, azaz olyan (p, p+2) pár, amelynek mindkét tagja prím. Ezek a problémák 1900-ban teljesen megközelíthetetlenek voltak.
Az első lényeges eredményt az ikerprím problémával kapcsolatban Vigo Brun érte el 1920-ban, bizonyítván, hogy ha végtelen sok ikerprím létezik is, relatív arányuk az összes prímhez képest csekély, így pl. az ikerprímek reciprokösszege konvergens, míg az összes prím reciprokösszege divergens (ld. (1.6)).
G. H. Hardy (1877‐1947), Littlewood (1885‐1977) és Ramanujan (1887‐1920) a 20-as évek elején egy igen erős analitikus módszert dolgoztak ki ezen problémák kezelésére. Módszerük azonban csak félsiker volt, mivel csak bizonyos, igen mély függvénytani sejtésekből (melyek jellegükben a Riemann-hipotézisre hasonlítanak) sikerült levezetniük a ternär Goldbach-sejtést*. Az ikerprímek problémájára és a binér Goldbach-sejtésre azonban módszerükkel még plauzibilis analitikus hipotézisek feltevése esetén sem sikerült eredményt elérniük, így ezen módszerek háttérbe szorultak.
1930-ban Snyirelmann (1905‐1938) elemi módszerek segítségével igazolta, hogy minden elegendően nagy természetes szám előáll legfeljebb 800000 prím összegeként. Módszerének további javításával a 800000-s szám 2208-ra (Romanov, 1935) majd 67-re (Ricci, 1936) csökkent.
Végül 1937-ben I. M. Vinogradovnak az általa bevezetett trigonometrikus összegek elméletének segítségével sikerült a Hardy, Littlewood és Ramanujan bizonyításában szereplő analitikus sejtéseket kiiktatnia és a ternär Goldbach-problémát majdnem teljesen megoldania. Nevezetesen igazolta, hogy minden elegendően nagy páratlan szám előállítható 3 prímszám összegeként. Érdekes, hogy az eredeti bizonyítás semmilyen konkrét korlátot nem adott (és elvi okokból nem adhatott) azon számra, amelytől kezdve minden páratlan szám felírható 3 prím összegeként. Ma már ez a korlát ismert, de értéke kb. 10100 lévén, még mindig reménytelen lenne az ennél kisebb számokra a sejtést elektronikus számítógépek segítségével ellenőrizni. A bizonyításból könnyen levezethető volt az is, hogy majdnem minden páros szám előállítható 2 prímszám összegeként. Ez pontos alakban megfogalmazva azt jelenti, hogy ha azon N-nél kisebb páros számok számát, amelyek nem állnak elő 2 prím összegeként, A(N)-nel jelöljük, akkor
limNA(N)N=0.(5.1)

A binér Goldbach-sejtés felé vezető másik döntő lépést 1947-ben Rényi Alfréd (1921‐1970) tette, aki igazolta, hogy minden elegendően nagy páros szám előáll 2 olyan szám összegeként, melyek egyike prím, másika pedig legfeljebb K prímtényezőből áll, ahol K adott szám.
Érdekes módon a bizonyítás módszere hasonló eredményt szolgáltatott az ikerprím problémára is, mely szerint végtelen sok olyan p prím van, amelyre p+2 legfeljebb K prímtényezőből áll. 1950-ben Selberg kimutatta (bár bizonyítását nem publikálta), hogy minden elég nagy páros szám előáll
2m=P2+P3(5.2)
alakban, ahol Pi olyan számot jelent, amelynek legfeljebb i prímtényezője van, és hasonló eredmény áll az ikerprím problémára is. Ezen módszer érdekessége, hogy a Goldbach-sejtés és az ikerprím-probléma rendkívül szoros kapcsolatban van, és az egyikre nyert eredménnyel analóg eredményt ad a másik esetre is. Buchstab 1965-ben igazolta, hogy minden elég nagy páros szám P1+P3 alakba írható (ill. végtelen sok p prím létezik, amelyre (p+2) legfeljebb 3 prímtényezőből áll). Végül 1966-ban J. Chen azt bizonyította, hogy az elég nagy páros számok előállnak P1+P2 alakban is, és hasonlóképp végtelen sok p prím van, melyre (p+2) legfeljebb 2 prímtényező szorzata.
Bár ezzel a Goldbach-sejtés és az ikerprím probléma látszólag karnyújtásnyi közelségbe került, az utolsó lépés megtétele igen nehéznek tűnik. Annál is inkább, mert E. Bombieri kimutatta, hogy az eddig alkalmazott módszerek biztosan nem alkalmasak a Goldbach-sejtés és az ikerprím-probléma megoldására.
Végül említsük meg az analitikus számelmélet negyedik fő problémáját, az egymást követő prímek differenciájának kérdését. (Csebisev tétele szerint pl. N és 2N közt van prím.) E. Landau (1877‐1939) az 1912-es Cambridge-i Matematikai Világkongresszuson így jellemezte azt a problémát, mely szerint bármely 2 szomszédos négyzetszám közt van prím. Ennek egy kicsit gyengített változata szerint mindig található prím az
[N,N+N1/2+ε](5.3)
intervallumban, ha N>N0(ε) (ε-tól függő konstans). Ez a probléma valóban egy fokkal egyszerűbbnek tűnik az előbb felsorolt 3 problémánál, és viszonylag nagy előrehaladást sikerült elérni bizonyításában. Az (5.3) alatt szereplő könnyebb változatának helyessége triviálisan következnék a Riemann-hipotézis (4.2) alakjának helyességéből, de annak eldöntése nélkül is remény van a probléma megoldására. (Az eredeti formája, bár csak csekély változtatást tartalmaz, jóval nehezebbnek tűnik, és nem következik a Riemann-sejtésből.) Érdemes megemlíteni, hogy ugyanakkor a Goldbach‐ és ikerprím problémák nem következményei a Riemann-hipotézisnek.
(4.3)-ból viszonylag könnyen levezethető, hogy N>N0 esetén van prím az
[N,N+NelogN](5.4)
intervallumban, ugyanakkor semmilyen ϑ<1-gyel nem következik (4.3)-ból, hogy az
[N,N+Nϑ](5.5)
intervallum is tartalmaz prímet. Hoheisel komoly érdeme, hogy 1930-ban mégis igazolta, hogy az (5.5) intervallumban elég nagy N-re mindig van prím, ha
ϑ=1-133000.(5.6)
Később Ingham ezt ϑ=3861 értékkel igazolta, melyből például következik, hogy bármely 2 szomszédos köbszám között van prím, egy bizonyos határtól kezdve. Ezt jó 30 évvel később Montgomery ϑ=0,6-re javította. Majd az utóbbi években Huxley ϑ=7/12 értékkel, igazolta, hogy az (5.5) intervallum tartalmaz prímet. Jelenleg a négy fő probléma közül ennek megoldása látszik a legreményteljesebbnek.

* Ennek bizonyítása megtalálható lapunk 1., 2. évfolyam 4., 5. számában. (1950.)

* A továbbiakban p mindig prímet jelöl.

*logx-en a természetes logaritmust értjük. Alapszáma e=limn(1+1n)n2,72.

*Csebisev-tétel bizonyítása megtalálható lapunk 1. évfolyamának 4. 5. 7. számában. (1947.)

* Ramanujanról lapunk ez évi október ‐ novemberi számában közöltünk cikket.