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

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

Прва таква расподела је $π(Н) ~ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}Н/лог(Н)$ , где је $π (Н)$ функција расподеле простих бројева и $лог(Н)$ је природни логаритам од $Н$ . То значи да за довољно велико $Н$ , вероватноћа да је случајни цели број који није већи од $Н$ прост број врло близу $1 / лог(Н)$ . Следствено томе, за случајни цели број са највише $2 н$ цифара (за довољно велико $н$ ) постоји приближно упола мања вероватноћа да ће он бити прост број као случајни цели број са највише $н$ цифара. На пример, међу позитивним целим бројевима од највише 1000 цифара, један од 2300 је прост број ( $лог(10 1000) \approx 2302,6$ ), док је међу позитивним целим бројевима са највише 2000 цифара, приближно један од 4600 прост број ( $лог(10 2000) \approx 4605,2$ ). Другим речима, просечни размак између узастопних простих бројева међу првих $Н$ целих бројевима је око $лог(Н)$ .^[1]

Исказ

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

\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\;\left[{\frac {x}{\log(x)}}\right]\;}}=1,

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

\pi (x)\sim {\frac {x}{\log x}}.

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

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

p_{n}\sim n\log(n),

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

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

\lim _{x\to \infty }{\frac {\vartheta (x)}{x}}=\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1,

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

Табела $π (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
10²	25	3.3	1.151	5.1	4.000
10³	168	23.0	1.161	10.0	5.952
10⁴	7003122900000000000♠1229	143.0	1.132	17.0	8.137
10⁵	7003959200000000000♠9592	906.0	1.104	38.0	10.425
10⁶	7004784980000000000♠78498	7003611600000000000♠6116.0	1.084	130.0	12.740
10⁷	7005664579000000000♠664579	7004441580000000000♠44158.0	1.071	339.0	15.047
10⁸	7006576145500000000♠5761455	7005332774000000000♠332774.0	1.061	754.0	17.357
10⁹	7007508475340000000♠50847534	7006259259200000000♠2592592.0	1.054	7003170100000000000♠1701.0	19.667
10¹⁰	7008455052511000000♠455052511	7007207580290000000♠20758029.0	1.048	7003310400000000000♠3104.0	21.975
10¹¹	7009411805481300000♠4118054813	7008169923159000000♠169923159.0	1.043	7004115880000000000♠11588.0	24.283
10¹²	7010376079120180000♠37607912018	7009141670519300000♠1416705193.0	1.039	7004382630000000000♠38263.0	26.590
10¹³	7011346065536839000♠346065536839	7010119928584520000♠11992858452.0	1.034	7005108971000000000♠108971.0	28.896
10¹⁴	7012320494175080200♠3204941750802	7011102838308636000♠102838308636.0	1.033	7005314890000000000♠314890.0	31.202
10¹⁵	7013298445704226690♠29844570422669	7011891604962452000♠891604962452.0	1.031	7006105261900000000♠1052619.0	33.507
10¹⁶	7014279238341033925♠279238341033925	7012780428984439300♠7804289844393.0	1.029	7006321463200000000♠3214632.0	35.812
10¹⁷	7015262355715765423♠2623557157654233	7013688837346932810♠68883734693281.0	1.027	7006795658900000000♠7956589.0	38.116
10¹⁸	7016247399542877408♠24739954287740860	7014612483070893536♠612483070893536.0	1.025	7007219495550000000♠21949555.0	40.420
10¹⁹	7017234057667276344♠234057667276344607	7015548162416936996♠5481624169369960.0	1.024	7007998777750000000♠99877775.0	42.725
10²⁰	7018222081960256091♠2220819602560918840	7016493471930446597♠49347193044659701.0	1.023	7008222744644000000♠222744644.0	45.028
10²¹	7019211272694860187♠21127269486018731928	7017446579871578168♠446579871578168707.0	1.022	7008597394254000000♠597394254.0	47.332
10²²	7020201467286689315♠201467286689315906290	7018406070400601962♠4060704006019620994.0	1.021	7009193235520800000♠1932355208.0	49.636
10²³	7021192532039160680♠1925320391606803968923	7019370835137665786♠37083513766578631309.0	1.020	7009725018621600000♠7250186216.0	51.939
10²⁴	7022184355997673492♠18435599767349200867866	7020339996354713708♠339996354713708049069.0	1.019	7010171469072780000♠17146907278.0	54.243
10²⁵	7023176846309399143♠176846309399143769411680	7021312851663784303♠3128516637843038351228.0	1.018	7010551609809390000♠55160980939.0	56.546
ОЕИС	А006880	А057835		А057752

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

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

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

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

N_{n}\sim {\frac {q^{n}}{n}}.

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

{\frac {x}{\log _{q}x}},

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

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

N_{n}={\frac {q^{n}}{n}}+O\left({\frac {q^{\frac {n}{2}}}{n}}\right).

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

q^{n}=\sum _{d\mid n}dN_{d},

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

N_{n}={\frac {1}{n}}\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)q^{d},

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

Референце

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

Литература

Хардy, Г. Х.; Литтлеwоод, Ј. Е. (1916). „Цонтрибутионс то тхе Тхеорy оф тхе Риеманн Зета-Фунцтион анд тхе Тхеорy оф тхе Дистрибутион оф Примес” (ПДФ). Ацта Матхематица. 41: 119—196. дои:10.1007/БФ02422942.
Гранвилле, Андреw (1995). „Харалд Црамéр анд тхе дистрибутион оф приме нумберс” (ПДФ). Сцандинавиан Ацтуариал Јоурнал. 1: 12—28. ЦитеСеерX 10.1.1.129.6847 . дои:10.1080/03461238.1995.10413946. Архивирано из оригинала (ПДФ) 23. 09. 2015. г. Приступљено 18. 02. 2020.
Буррис, Станлеy Н. (2001). Нумбер тхеоретиц денситy анд логицал лимит лаwс. Матхематицал Сурвеyс анд Монограпхс. 86. Провиденце, РИ: Америцан Матхематицал Социетy. ИСБН 0-8218-2666-2. Збл 0995.11001.
Кнопфмацхер, Јохн (1990) [1975]. Абстрацт Аналyтиц Нумбер Тхеорy (2нд изд.). Неw Yорк, НY: Довер Публисхинг. ИСБН 0-486-66344-2. Збл 0743.11002.
Монтгомерy, Хугх L.; Ваугхан, Роберт C. (2007). Мултиплицативе нумбер тхеорy I. Цлассицал тхеорy. Цамбридге студиес ин адванцед матхематицс. 97. стр. 278. ИСБН 0-521-84903-9. Збл 1142.11001.
Алина Цармен Цојоцару; M. Рам Муртy. Ан интродуцтион то сиеве метходс анд тхеир апплицатионс. Лондон Матхематицал Социетy Студент Теxтс. 66. Цамбридге Университy Пресс. стр. 35—38. ИСБН 0-521-61275-6.
Ландау, Едмунд (1903). „Неуер Беwеис дес Примзахлсатзес унд Беwеис дес Примидеалсатзес”. Матхематисцхе Аннален. 56 (4): 645—670. дои:10.1007/БФ01444310.
Дудек, Адриан W. (21. 8. 2014), „Он тхе Риеманн хyпотхесис анд тхе дифференце бетwеен примес”, Интернатионал Јоурнал оф Нумбер Тхеорy, 11 (3): 771—778, Бибцоде:2014арXив1402.6417Д, ИССН 1793-0421, арXив:1402.6417 , дои:10.1142/С1793042115500426
Ингхам, А.Е. (1932), Тхе Дистрибутион оф Приме Нумберс, Цамбридге Трацтс ин Матхематицс анд Матхематицал Пхyсицс, 30, Цамбридге Университy Пресс . Репринтед 1990, ISBN 978-0-521-39789-6, МР 1074573
Мазур, Баррy; Стеин, Wиллиам (2015), Приме Нумберс анд тхе Риеманн Хyпотхесис
Ницелy, Тхомас Р. (1999), „Неw маxимал приме гапс анд фирст оццурренцес”, Матхематицс оф Цомпутатион, 68 (227): 1311—1315, Бибцоде:1999МаЦом..68.1311Н, МР 1627813, дои:10.1090/С0025-5718-99-01065-0, Архивирано из оригинала 30. 12. 2014. г., Приступљено 18. 2. 2020 .

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

Хазеwинкел Мицхиел, ур. (2001). „Дистрибутион оф приме нумберс”. Енцyцлопаедиа оф Матхематицс. Спрингер. ISBN 978-1556080104.
Table of Primes by Anton Felkel.
Short video visualizing the Prime Number Theorem.
Prime formulas and Prime number theorem at MathWorld.
„Приме нумбер тхеорем”. ПланетМатх.
How Many Primes Are There?Архивирано на сајту Wayback Machine (15. октобар 2012) and The Gaps between Primes by Chris Caldwell, University of Tennessee at Martin.
Tables of prime-counting functions by Tomás Oliveira e Silva

[1] Хоффман, Паул (1998). Тхе Ман Wхо Ловед Онлy Нумберс. Неw Yорк: Хyперион Боокс. стр. 227. ИСБН 978-0-7868-8406-3. МР 1666054.

[2] „Приме Цуриос!: 8512677386048191063”. Приме Цуриос!. Университy оф Теннессее ат Мартин. 9. 10. 2011.

[Franke-3] „Цондитионал Цалцулатион оф $π (10 24)$ ”. Цхрис К. Цалдwелл. Архивирано из оригинала 25. 09. 2014. г. Приступљено 3. 8. 2010.

[PlattARXIV2012-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.

[1]

[2]

[3]

[4]

[5]