Пређи на садржај

Теорема простих бројева

С Википедије, слободне енциклопедије

У теорији бројева, теорема простих бројева (енгл. prime number theorem, PNT) описује асимптотску дистрибуцију простих бројева међу позитивним целим бројевима. То формализује интуитивну идеју да прости бројеви постају мање заступљени како постају већи у складу са прецизно квантификованом стопом којом до тога долази. Теорему су независно доказали Жак Адамар и Шарл Жан де ла Вале-Пусен 1896. године, користећи идеје које је увео Бернхард Риман (нарочито Риманову зета функцију).

Прва таква расподела је π(Н) ~ Н/лог(Н), где је π(Н) функција расподеле простих бројева и лог(Н) је природни логаритам од Н. То значи да за довољно велико Н, вероватноћа да је случајни цели број који није већи од Н прост број врло близу 1 / лог(Н). Следствено томе, за случајни цели број са највише 2н цифара (за довољно велико н) постоји приближно упола мања вероватноћа да ће он бити прост број као случајни цели број са највише н цифара. На пример, међу позитивним целим бројевима од највише 1000 цифара, један од 2300 је прост број (лог(101000) ≈ 2302,6), док је међу позитивним целим бројевима са највише 2000 цифара, приближно један од 4600 прост број (лог(102000) ≈ 4605,2). Другим речима, просечни размак између узастопних простих бројева међу првих Н целих бројевима је око лог(Н).[1]

Графикон који приказује однос функције расподеле простих бројева π(x) и две њене апроксимације, x / лог x и Ли(x). Како се x повећава (напомена: x оса је логаритамска), оба се односа крећу према 1. Однос за x / лог x конвергира одозго врло споро, док однос за Ли(x) брже конвергира одоздо.
Лог-лог графикон приказује апсолутну грешку од x / лог x и Ли(x), две апроксимације функције расподеле простих бројева π(x). За разлику од односа, разлика између π(x) и x / лог x се повећава без ограничења како се x повећава. С друге стране, Ли(x) − π(x) мања знак бесконачно много пута.

Нека је π(x) функција расподеле простих бројева која даје број простих бројева мањи или једнак са x, за сваки реални број x. На пример, π(10) = 4, јер постоје четири проста броја (2, 3, 5 и 7) мања или једнака од 10. Према теореми простих бројева тада је x / лог x добра апроксимација за π(x) (где лог значава природни логаритам), у смислу да је лимит количника две функције π(x) и x / лог x како се x повећава без ограничења једнак 1:

Ово је познато као асимптотски закон дистрибуције простих бројева. Користећи асимптотску нотацију овај резултат се може написати као

Ова нотација (и теорема) не говори о лимиту разлике две функције кад се x повећава без ограничења. Уместо тога, теорема наводи да x / лог x апроксимира π(x) у смислу да се релативна грешка ове апроксимације приближава 0, када се x повећава без ограничења.

Теорема простих бројева је еквивалентна тврђењу да н-ти прости број пн задовољава

асимптотска нотација поново указује на то да релативна грешка ове апроксимације приступа 0 кад се н повећава без ограничења. На пример, 2×1017-ти прости број је 8512677386048191063,[2] и (2×1017)лог(2×1017) заокружује се на 7967418752291744388, са релативном грешком од око 6,4%.

Теорема простих бројева је исто тако еквивалентна са

где су ϑ и ψ прва и друга Чебишева функција, респективно.

Табела π(x), x / лог x, анд ли(x)

[уреди | уреди извор]

У овој табели су упоређене вредности π(x) са две апроксимације x / лог x и ли(x). Задња колна, x / π(x), је просек размака између простих бројева испод x.

x π(x) π(x) − x/лог x π(x)/x / лог x ли(x) − π(x) x/π(x)
10 4 −0.3 0.921 2.2 2.500
102 25 3.3 1.151 5.1 4.000
103 168 23.0 1.161 10.0 5.952
104 1229 143.0 1.132 17.0 8.137
105 9592 906.0 1.104 38.0 10.425
106 78498 6116.0 1.084 130.0 12.740
107 664579 44158.0 1.071 339.0 15.047
108 5761455 332774.0 1.061 754.0 17.357
109 50847534 2592592.0 1.054 1701.0 19.667
1010 455052511 20758029.0 1.048 3104.0 21.975
1011 4118054813 169923159.0 1.043 11588.0 24.283
1012 37607912018 1416705193.0 1.039 38263.0 26.590
1013 346065536839 11992858452.0 1.034 108971.0 28.896
1014 3204941750802 102838308636.0 1.033 314890.0 31.202
1015 29844570422669 891604962452.0 1.031 1052619.0 33.507
1016 279238341033925 7804289844393.0 1.029 3214632.0 35.812
1017 2623557157654233 68883734693281.0 1.027 7956589.0 38.116
1018 24739954287740860 612483070893536.0 1.025 21949555.0 40.420
1019 234057667276344607 5481624169369960.0 1.024 99877775.0 42.725
1020 2220819602560918840 49347193044659701.0 1.023 222744644.0 45.028
1021 21127269486018731928 446579871578168707.0 1.022 597394254.0 47.332
1022 201467286689315906290 4060704006019620994.0 1.021 1932355208.0 49.636
1023 1925320391606803968923 37083513766578631309.0 1.020 7250186216.0 51.939
1024 18435599767349200867866 339996354713708049069.0 1.019 17146907278.0 54.243
1025 176846309399143769411680 3128516637843038351228.0 1.018 55160980939.0 56.546
ОЕИС А006880 А057835 А057752

Вредност за π(1024) била је оригинално израчуната користећи Риманову хипотезу.[3] Од тада су безусловно верификоване.[4]

Аналог за несводљиве полиноме на коначном пољу

[уреди | уреди извор]

Постоји аналогна теорема простих бројева која описује „расподелу” несажимљивих полинома преко коначног поља; њен облик је упадљиво сличан са класичном теоремом простих бројева.

Да би се то прецизно изразило, може се узети да је Ф = ГФ(q) коначно поље са q елемената, за неко фиксно q, и да је Нн број монијских несажимљивих полинома преко Ф чији је степен једнак н. То јест, разматрају се полиноми са коефицијентима одабраним из Ф, који се не могу записати као производи полинома нижег степена. У овом окружењу, ти полиноми играју улогу простих бројева, јер су сви други монијски полиноми изграђени од њихових производа. Онда се може доказати да је

Ако се уради супституција x = qн, онда је десна страна само

чиме се појашњава аналогија. Како постоји тачно qн монијских полинома степена н (укључујући оне који су сажимљиви), то се може преформулирати на следећи начин: ако је монијски полином степена н рандомно изабран, онда је вероватноћа да је он несажимљив око 1/н.

Могуће је доказати и аналогну верзију Риманове хипотезе, наиме да је

Докази ових тврдњи далеко су једноставнији него у класичном случају. То обухвата кратако комбинаторично разматрање,[5] сумирано на следећи начин: сваки елемент степена н проширења Ф је корен неког несажимљивог полинома чији степен д дели н; при пребројавану ових корена су успостављена два различита приступа

где сума обухвата све дилиоце д од н. Мебијусова инверзија онда даје

где је μ(к) Мебијусова функција. (Ова формула је била позната Гаусу.) Главни члан се јавља за д = н, и није тешко везати преостале чланове. Израз „Риманове хипотезе” зависи од чињенице да највећи својствени дилилац од н не може да буде већи од н/2.

Референце

[уреди | уреди извор]
  1. ^ Хоффман, Паул (1998). Тхе Ман Wхо Ловед Онлy НумберсНеопходна слободна регистрација. Неw Yорк: Хyперион Боокс. стр. 227. ИСБН 978-0-7868-8406-3. МР 1666054. 
  2. ^ „Приме Цуриос!: 8512677386048191063”. Приме Цуриос!. Университy оф Теннессее ат Мартин. 9. 10. 2011. 
  3. ^ „Цондитионал Цалцулатион оф π(1024). Цхрис К. Цалдwелл. Архивирано из оригинала 25. 09. 2014. г. Приступљено 3. 8. 2010. 
  4. ^ Платт, Давид (2015). „Цомпутинг π(x) аналyтицаллy”. Матхематицс оф Цомпутатион. 84 (293): 1521—1535. МР 3315519. арXив:1203.5712Слободан приступ. дои:10.1090/С0025-5718-2014-02884-6. 
  5. ^ Цхеболу, Сунил; Минáч, Јáн (децембар 2011). „Цоунтинг Ирредуцибле Полyномиалс овер Фините Фиелдс Усинг тхе Инцлусион π Еxцлусион Принципле”. Матхематицс Магазине. 84 (5): 369—371. ЈСТОР 10.4169/матх.маг.84.5.369. арXив:1001.0409Слободан приступ. дои:10.4169/матх.маг.84.5.369. 

Литература

[уреди | уреди извор]

Спољашње везе

[уреди | уреди извор]