Prímszámtétel – definíció, magyarázat és története a számelméletben

Prímszámtétel: definíció, magyarázat és története a számelméletben — hogyan oszlanak el a prímszámok, az n/ln(n) képlet és a történelmi bizonyítások áttekintése.

Prímszámtétel a számelmélet egyik alapvető tétele, amely a prímszámok eloszlását írja le nagy számok között. Formális értelemben a tétel azt mondja ki, hogy ha π(x) jelöli az x-nél nem nagyobb pozitív prímszámok számát, akkor

• lim_{x→∞} π(x) / (x / ln x) = 1, azaz röviden π(x) ~ x / ln x.

Más, finomabb megfogalmazás szerint a prímszámok sűrűsége az x környezetében megközelítőleg 1 / ln x, így a véletlenszerűen választott, körülbelül N nagyságrendű számban a prímszám előfordulásának valószínűsége körülbelül 1 / ln N. (Itt ln a természetes alapú logaritmus.) Ennek egyszerű következménye, hogy az első N egész szám között az egymást követő prímszámok közötti átlagos különbség nagyjából ln(N).

Magyarázat, egyszerű példák

Gyakorlati példa: egy véletlenszerűen választott, pontosan n számjegyű pozitív egész szám valószínűsége, hogy prímszám, megközelítőleg 1 / ln(10^n) = 1 / (n ln 10). Így például:

• 1000 számjegyű számok esetén ln(10^1000) = 1000·ln(10) ≈ 2302,6, tehát nagyjából minden 2300–2303. szám lesz prímszám;
• 2000 számjegyűeknél ln(10^2000) ≈ 4605,2, tehát nagyjából minden 4600–4606. szám lesz prímszám.

Az egyszerű következtetés a gyakorlatban azt jelenti, hogy nagy prímszámok keresése (például kriptográfiai alkalmazásokhoz) véletlenszerű mintavételezéssel hatékony: várhatóan körülbelül ln N próbára van szükség egy N nagyságrendű prímszám megtalálásához.

Történet és bizonyítások

A tétel története ismert személyekhez kötődik: a tizenöt éves Carl Friedrich Gauss már 1793 körül feltűntezett egy kapcsolatra a prímszámok és a logaritmusok között, és Adrien‑Marie Legendre 1798-ban függetlenül is hasonló következtetésre jutott. Legendre egy közelítő képletet javasolt (π(x) ≈ x / (ln x − B), egy bizonyos B konstanssal), de a pontos aszimptotikus állítást csak jóval később sikerült bizonyítani.

Az első teljes bizonyítást 1896-ban Jacques Hadamard és Charles‑Jean de La Vallée Poussin adták meg függetlenül. Mindketten komplex analízist alkalmaztak, különösen a Riemann‑féle zétafüggvény analitikus tulajdonságait, és megmutatták, hogy a zétafüggvénynek nincs zérusa az egyenes Re(s)=1 közelében (pontosabban létezik egy zérómentes régió a tengely környékén). Ez a zérómentesség kulcsfontosságú volt a prímszámtétel bizonyításában.

1948–49-ben Atle Selberg és Paul Erdős „elemi” bizonyítást adottak (az „elemi” itt azt jelenti, hogy nem használták a komplex függvények fogalmát), amely új, kombinatorikus és analitikus eszközökre épült. Bár Selberg–Erdős bizonyítása rövidebb és meglepő volt, a modern elméletben a zétafüggvény vizsgálata továbbra is központi szerepet játszik.

Pontosabb közelítések és finomítások

A π(x) ≈ x / ln x állításnál pontosabb közelítés a logaritmikus integrál li(x) = ∫_2^x dt / ln t, amely általában jobb közelítést ad: π(x) ~ li(x). A tételhez kapcsolódó hibahatárok és közelítések aktív kutatási területet jelentenek. Az általános nemfeltételes eredmények egyre jobb explicit hibabecsléseket adnak; a leghatékonyabb nem-triviális hibahatárok bizonyítása a zétafüggvény zéróhelyeinek eloszlásával függ össze.

A Riemann‑hipotézis (RH) erősebb állítás a zétafüggvény zéróhelyeiről; ha RH igaz, akkor sokkal szorosabb hibabecslések lennének a π(x)-re, konkrétan az a feltétel erősebb hibahatárt adna (közelítőleg O(x^{1/2} ln x)). Jelenleg azonban az RH megoldatlan, ezért a legjobb bizonyított általános hibahatárok gyengébbek.

Következmények és általánosítások

• A prímszámtétel alapvető szerepet játszik a számelméletben és alkalmazásokban (például a prímszámok előfordulási gyakoriságának ismerete fontos a kriptográfiában, ahol nagy prímek gyors megtalálása szükséges).
• Vannak általánosítások különböző számhalmazokra vagy feltételek mellett: például a prímszámteóriában a Dirichlet‑féle prímszámtétel aritmetikai sorozatokra (aritmetikai sorozatokban végtelen sok prímszám létezik, és sűrűségük is meghatározható) a Dirichlet L‑függvények analógiája révén.
• Chebyshev‑féle függvények (θ(x) és ψ(x)) és kapcsolódó technikák gyakran használatosak a bizonyításokban és a határok javításában.

Rövid összefoglalás

A prímszámtétel a prímszámok ritkulását írja le: a prímszámok sűrűsége nagyszámoknál megközelítőleg 1 / ln x, ami formalizálható azzal, hogy π(x) ~ x / ln x. A tételt Gauss és Legendre sejtette, a teljes bizonyítást Hadamard és de La Vallée Poussin adta meg 1896‑ban, majd Selberg és Erdős elemi bizonyítást mutattak be. A kérdés továbbra is kapcsolódik mély problémákhoz a zétafüggvény és a Riemann‑hipotézis körül, valamint sok alkalmazásban (például kriptográfiában) fontos szerepet játszik.

Kérdések és válaszok

K: Mi az a prímszámtétel?

K: A prímszámok egyenletesen oszlanak el a számtartományban?

K: Mit formalizál a prímszámtétel?

K: Mekkora a valószínűsége annak, hogy 1 és egy adott szám közötti prímszámot találunk?

K: A 2n számjegyű prímszám eltalálásának valószínűsége nagyobb, mint az n számjegyű prímszám eltalálásának valószínűsége?

K: Ki bizonyította be a prímszámtételt?

K: Mekkora az első N egész szám közül az egymást követő prímszámok közötti átlagos különbség?

Keresés betűvel