A Riemann-Siegel zeta függvény kiugró értékeinek keresése A matematikai egyik legnehezebb problémája, avagy a prímszámok misztériuma
2013
A probléma fontossága és hatása a hétköznapi életre A prímszámok az egyik legfontosabb építőkövei a matematikának. Prímszámoknak nevezzük azokat az egynél nagyobb egész számokat, amelyeknek pontosan két osztójuk van: 1 és önmaga. Az első néhány prím tehát a 2, 3, 5, 7, 11, 13, 17, 19. Már időszámításunk előtt 300-ban Eukleidész elemi módszerekkel bizonyította, hogy a prímszámok végtelen sokan vannak, így a fenti sorozatnak nincsen legnagyobb eleme. A 18. században Gauss híres sejtése volt, hogy sikeres becslést adott a prímszámok számára x-ig. 1 millióig például 78.498 prím található. Gauss becslésével amely az x/ ln(x) képlettel írható le 72382 prímet kapunk, amely 92%-os pontosságot jelent. Minél nagyobb számot választunk, az érték egyre jobban közelíti a tényleges értéket. Ez a híres prímszámtétel, amelyet majd 1 évszázaddal később sikerült csak bizonyítani. További sok összefüggést sikerült a prímekről bizonyítani az évszázadok során, azonban azt megérteni, hogy milyen szabályszerűséget követve bukkannak fel az egész számok között, nem sikerült tisztázni. A Riemann-zeta függvény szoros összefüggésbe hozható a prímekkel. A matematikai egyik legfontosabb máig megoldatlan sejtése a Riemann-hipotézis, amelynek egyik megfogalmazása azt állítja, hogy a Riemann-zeta függvény gyökeinek szabálytalan eloszlása megegyezik a prímszámok eloszlásával. A sejtés tehát a prímszámok teljes szabályszerű eloszlását állítja, amelynek megoldása hatalmas áttörés lenne a prímszámelméletben. A prímszámok jelen vannak az élet minden területén. Amikor e-mailt küldünk, vagy biztonságos webkapcsolatot létesítünk, vagy éppen a bankkártyás fizetés során. Az egyik legelterjedtebb titkosító algoritmus az RSA, hatalmas prímszámok szorzatát használja fel titkosításhoz. A rejtjelrendszer biztonságát az adja, hogy nem ismert hatékony algoritmus nagy egész számok prímtényezőire bontására. Milyen hatása lehet egy tisztán matematikai kutatásnak a hétköznapi életben? A Riemann-zeta függvény kiugró értékeinek lokalizálása nem csak elméleti jelentőségű, hanem közvetlen hatása lehet a prímszámelmélet fejlődésére. Olyan értékek találatakor, amelyek nagysága nagymértékben eltér a várható értéktől, ott a zeta függvény szabálytalan viselkedése kísértetiesen hasonlít a prímszámok eloszlásában található szabálytalanságra. Minél több találatot sikerül összegyűjteni, annál több adatot lehet felhasználni statisztikai elemzésre, amely végül közelebb vihet bennünket a prímszámok eloszlásának megértésében. A prímszámok eloszlásának pontos megértésével hatékonyabb algoritmusokat írhatnánk az egész számok faktorizálására, vagy éppen biztonságosabb rejtjelrendszert tervezhetnénk.
A keresés matematikai háttere Ebben a fejezetben rövid áttekintést nyújtunk a kutatás matematikai hátteréről. Röviden bemutatjuk, hogy a kereső algoritmus milyen számelméleti összefüggések alapján lokalizálja a kiugró értékeket, így az érdeklődők egy átfogó képet kapnak arról, hogy mit is csinál a számítógépük a program futtatása során.
2
Georg Friedrich Bernhard Riemann a XIX. század közepén alkotta meg a zeta függvényt, amely a következőképpen definiálható: ζ(s) =
∞ X
1/ns , s ∈ C, s = σ + it
n=1
A ζ(s) függvénynek az s = −2, −4, −6, . . . helyeken felvett értéke zérus, azaz ζ(−2k) = 0 minden k = 1, 2, 3, . . . esetén. Ezeket hívjuk a ζ(s) függvény triviális gyökeinek. Vannak azonban nem −2k alakú gyökök, amelyekre nincsen egyszerű explicit formula. ζ(s)-nek a zérushoz legközelebbi ilyen nem triviális gyöke az s = 1/2 + 14.134725i környezetében található. Riemann a zeta függvény tanulmányozása közben azt vette észre, hogy a zeta függvény nem triviális gyökei mindig egy speciális egyenesen helyezkednek el, nevezetesen az s = 1/2 + it alakú egyenesen. A szakirodalom ezt az egyenest hívja kritikus egyenesnek, ehhez kapcsolódik a matematika talán egyik legfontosabb és máig megoldatlan problémája. Ez Riemann-hipotézis, amely azt állítja, hogy a Riemann zeta függvény nem triviális gyökei az s = 1/2 + it alakú függőleges egyenesen találhatóak. Riemann a kritikus egyenesen elhelyezkedő gyökök számítására kidolgozott egy formulát, amit nem publikált, csak valamivel később, 1930-ban fedezte fel újra Carl Siegel. A képlet√így most a Riemann-Siegel formula nevet viseli. A RiemannSiegel formula O( t) műveletet használ a kritikus egyenesen elhelyezkedő gyökök kiszámítására és az alábbi módon számolható: Z(t) = 2
ahol N =
$ q
N X
1 √ cos[θ(t) − t ln n] + O(t−1/4 ) , n n=1
%
t/2π és θ(t) = 2t log 2πt − 2t −
π 8
+
1 48t
+
7 5760t3
+ ···
Z(t) és ζ(s) között fennáll továbbá az alábbi fontos összefüggés: |Z(t)| =
ζ
!
1 + it 2
Jelenleg nem ismert olyan explicit formula, amivel Z(t) kiugró értékeit gyorsan, könnyen határozhatnánk meg. A projekt keretein belül olyan t jelölteket keresünk, amelyekre Z(t) értéke várhatóan nagy. A keresés az alábbi két módszer ötvözésén alapul:
Irracionális számok approximációja Az irracionális számok racionális számokkal való közelítése már régi probléma, és rengeteg eredmény található a témához kapcsolódóan. A 17. században J. Wallis és
3
C. Huygens kidolgozta a lánc törtek elméletét, amely ma is az egyik meghatározó matematikai apparátusa az irracionális számok approximációjának. 1842-ben Dirichlet bizonyította, hogy ha α irracionális, akkor végtelen sok pq racionális szám létezik, 355 amelyre teljesül az alábbi feltétel: |α − pq | < q12 . A π szám közelítésére a 113 egy 355 nagyon jó becslés, |π − 113 | < 0.000000267. A π lánctörtbe fejtésével számolhatóak további számok, amelyek egyre pontosabban közelítik meg a π jegyeit. A kutatásaink során olyan k egész számokat keresünk, amelyeket megszorozva több (mondjuk n) különböző irracionális számmal egésztől való eltérésük kicsi, pontosabban: kk ·
log pi k < , (1 ≤ i ≤ n) log 2
ahol k · k jelöli a legközelebbi egésztől való eltérést. Ez egy n-dimenziós szimultán diofantoszi approximációs probléma.
Új közelítő függvény bevezetése A kiugró értékek keresésére egy új függvényt vezetünk be, amely hasonló viselkedést mutat, mint az eredeti Z(t) függvény, azonban futási ideje O(ln(t). ln t/2π
F (t) =
X n=1
1 √ cos[θ(t) − t · ln n]) n
Figure 0.1: Z(t) s F(t) hasonló viselkedése F(t) számításából következtetni lehet Z(t) tényleges nagyságára. A gyakorlatban kiderült, hogy egy [a,b] intervallumon belül F(t) és Z(t) lokális maximuma, vagy
4
minimuma nagy százalékban ugyan azon t körül található egy maximum hibával. Másképpen fogalmazva, ahol Z(t) felveszi legnagyobb értékét egy intervallumban, ott várhatóan ugyan arra a t-re F(t)-nek is lokális maximuma vagy minimuma lesz. Több ezer értéket megvizsgálva, azt tapasztaltuk, hogy kiugró értékek keresése könnyebbé válik az új F (t) függvény segítségével. Jelen kutatás célja, hogy kiugró Z(t) értékeket keressünk. Ezen értékeket felhasználva új mintázatokat találhatunk a ζ(s) függvényben, amelyet felhasználva közelebb juthatunk a prímszámok misztériumának megértésében. A kutatás során minden egyes talált érték kiértékelésre kerül, amelyeket a www.riemann-siegel.com honlapon publikálunk.
5