素数定理

素数定理（そすうていり、英: Prime number theorem、独: Primzahlsatz）とは自然数の中に素数がどのくらいの「割合」で含まれているかを述べる定理である。整数論において素数が自然数の中にどのように分布しているのかという問題は基本的な関心事である。しかし、分布についての数学的な証明は極めて難しく、まだ解明されていない事柄が多い。この定理は素数の分布の性質についての最も基本的な情報を与える。

歴史

素数定理は、18世紀末にカール・フリードリヒ・ガウスやアドリアン＝マリ・ルジャンドルによって予想された（ガウス自身の言によればそれは1792年のガウスが15歳のときである）。予想として公表されたのはルジャンドルの著『数の理論』であったが、ガウスは少年時代にの既に予想を立てていたことはガウスの死後の1863年に彼の全集が出版されるまでは知られておらず、ガウス自身は素数定理については友人エンケに一度だけ手紙（1849年）で触れただけであった^[1]。

その後パフヌティ・チェビシェフによる部分的な結果（1850年-1852年頃^[2]）や、ベルンハルト・リーマンによる新たな解析的方法が発表された^[3]が、最終的には1896年にシャルル＝ジャン・ド・ラ・ヴァレー・プーサン（英語版）とジャック・アダマール^[4]がそれぞれ独立に証明した。当初与えられた証明はゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグ^[5]とポール・エルデシュ^[6]は初等的な証明を与えた。ノーバート・ウィーナーや池原止戈夫らによるタウバー型定理によって、素数定理と「ゼータ関数が Re s = 1 上に零点を持たないこと」との同値性は既に確立されていたので、この複素解析学を用いない初等的な証明は当時大きな驚きをもって迎えられた。

定理の内容

以下、記号「${\displaystyle \sim }$」は次を表すとする。

任意の関数${\displaystyle f(x)(\neq 0),g(x)}$に対し、

${\displaystyle f(x)\sim g(x):\Leftrightarrow \lim _{x\to \infty }{\frac {g(x)}{f(x)}}=1}$

なお、上式が成立している場合、「xが十分大きい場合、${\displaystyle f(x)}$は${\displaystyle g(x)}$で近似できる」といえる。

素数定理は、具体的には次の式で表される。

${\displaystyle \pi (x)\sim \operatorname {Li} (x)}$

上式において、π(x) は素数計数関数 (prime counting function) で、x 以下の素数の個数を表す。また Li(x) は補正対数積分 (logarithmic integral) で、次の積分で定義される。

${\displaystyle \operatorname {Li} (x):=\int _{2}^{x}{\frac {\mathrm {d} t}{\log(t)}}=\operatorname {li} (x)-\operatorname {li} (2).}$

なお、この定理は1や2以外の正数を積分の下端とする場合にも成立するが、慣例的に最小の素数である 2 とすること(補正対数積分)が多い。

また、補正対数積分を1回部分積分すると、

${\displaystyle \int _{2}^{x}{\frac {\mathrm {d} t}{\log(t)}}={\frac {x}{\log(x)}}+O\left({\frac {x}{(\log(x))^{2}}}\right)}$

となる。ここで、 O はランダウの記号である。このことから、定理を次のように述べることもできる。

${\displaystyle \pi (x)\sim {\frac {x}{\log(x)}}}$

これは同様にx/log(x) で近似できるということを意味する。こちらのほうが近似精度は少し悪いが計算上扱い易い。さらに次のように変形した式は、π(x)/x すなわちx 以下の正整数に占める素数の割合の近似式を表す。

${\displaystyle {\frac {\pi (x)}{x}}\sim {\frac {1}{\log(x)}}}$

上の2通りの近似はx が小さくても比較的正確である（以下の表を参照）。

また、n 番目の素数を p_n とすると、n ≧ 6 に対して

${\displaystyle \log(n)+\log(\log(n))-1<{\frac {p_{n}}{n}}<\log(n)+\log(\log(n))}$

が成り立つ^[7][8]。

π(x), x/log(x), li(x) の表

表は π(x) 、 x/log(x) 、 li(x) の値とそれらの比較の表である。

近似の様子

x	π(x)[9]	π(x) − x/log(x)[10]	π(x)/(x/log(x))	li(x) − π(x)[11]	x/π(x)[注釈 1]	x/log(x)[12]	li(x)[13]
10	4	−0.343	0.921	2.166	2.500	4.343	6.166
102	25	3.285	1.151	5.126	4.000	21.715	30.126
103	168	23	1.161	10	5.952	145	178
104	1,229	143	1.132	17	8.137	1,086	1,246
105	9,592	906	1.104	38	10.425	8,686	9,630
106	78,498	6,116	1.084	130	12.740	72,382	78,628
107	664,579	44,158	1.071	339	15.047	620,421	664,918
108	5,761,455	332,774	1.061	754	17.357	5,428,681	5,762,209
109	50,847,534	2,592,592	1.054	1,701	19.667	48,254,942	50,849,235
1010	455,052,511	20,758,029	1.048	3,104	21.975	434,294,482	455,055,615
1011	4,118,054,813	169,923,159	1.043	11,588	24.283	3,948,131,654	4,118,066,401
1012	37,607,912,018	1,416,705,193	1.039	38,263	26.590	36,191,206,825	37,607,950,281
1013	346,065,536,839	11,992,858,452	1.034	108,971	28.896	334,072,678,387	346,065,645,810
1014	3,204,941,750,802	102,838,308,636	1.033	314,890	31.202	3,102,103,442,166	3,204,942,065,692
1015	29,844,570,422,669	891,604,962,452	1.031	1,052,619	33.507	28,952,965,460,217	29,844,571,475,288
1016	279,238,341,033,925	7,804,289,844,393	1.029	3,214,632	35.812	271,434,051,189,532	279,238,344,248,557
1017	2,623,557,157,654,233	68,883,734,693,281	1.027	7,956,589	38.116	2,554,673,422,960,305	2,623,557,165,610,822
1018	24,739,954,287,740,860	612,483,070,893,536	1.025	21,949,555	40.420	24,127,471,216,847,324	24,739,954,309,690,415
1019	234,057,667,276,344,607	5,481,624,169,369,960	1.024	99,877,775	42.725	228,576,043,106,974,646	234,057,667,376,222,382
1020	2,220,819,602,560,918,840	49,347,193,044,659,701	1.023	222,744,644	45.028	2,171,472,409,516,259,138	2,220,819,602,783,663,484
1021	21,127,269,486,018,731,928	446,579,871,578,168,707	1.022	597,394,254	47.332	20,680,689,614,440,563,221	21,127,269,486,616,126,182
1022	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1.021	1,932,355,208	49.636	197,406,582,683,296,285,296	201,467,286,691,248,261,498
1023	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	1.020	7,250,186,216	51.939	1,888,236,877,840,225,337,614	1,925,320,391,614,054,155,139
1024	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	1.019	17,146,907,278	54.243	18,095,603,412,635,492,818,797	18,435,599,767,366,347,775,144
1025	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	1.018	55,160,980,939	56.546	173,717,792,761,300,731,060,452	176,846,309,399,198,930,392,619
1026	1,699,246,750,872,437,141,327,603	28,883,358,936,853,188,823,261	1.017	155,891,678,121	58.850	1,670,363,391,935,583,952,504,342	1,699,246,750,872,593,033,005,724
1027	16,352,460,426,841,680,446,427,399	267,479,615,610,131,274,163,365	1.0166	508,666,658,006	61.153	16,084,980,811,231,549,172,264,034	16,352,460,426,842,189,113,085,405
1028	157,589,269,275,973,410,412,739,598	2,484,097,167,669,186,251,622,127	1.016	1,427,745,660,374	63.456	155,105,172,108,304,224,161,117,471	157,589,269,275,974,838,158,399,972

π(10²⁴) の値はもともとリーマン予想を仮定して計算されたが^[14]、その後無条件で証明された^[15]。

算術級数の素数定理

この定理はまた、算術級数（等差数列）中の素数に関しても拡張されており、これを算術級数の素数定理という：

すなわち、算術級数 {an + b} (a > 0、a と b は互いに素) に含まれる素数で、x 以下のものの数を π_a,b(x) で表すとき、

${\displaystyle \pi _{a,b}(x)\sim {\frac {1}{\phi (a)}}\operatorname {Li} (x)}$

が成り立つ。ここで φ(n) はオイラーの関数と呼ばれるもので、n と互いに素な n 以下の自然数の個数を表す。この漸近公式はルジャンドルやペーター・グスタフ・ディリクレによって予想されていたが、これもド・ラ・ヴァレー・プーサンによって証明された。近年、Ivan Soprounov により、より初等的な証明が発見された^[16]。

→詳細は「算術級数の素数定理」を参照

誤差評価

より詳しくは、現今最良の近似の誤差は次の結果である（ヴィノグラードフの素数定理）。充分大きな x について、

${\displaystyle \pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-{\frac {A(\log x)^{\frac {3}{5}}}{(\log \log x)^{\frac {1}{5}}}}\right)\right)}$ ただし ${\displaystyle A=0.2098}$.^[17]

さらに、1901年にヘルゲ・フォン・コッホは、もしリーマン予想が正しければ次のように誤差評価を改善できることを証明した^[18]。

${\displaystyle \pi (x)=\operatorname {Li} (x)+O\left({\sqrt {x}}\log(x)\right)}$

逆に、上記の評価式が成り立てばリーマン予想が成り立つことも知られている。

また前節で挙げた表を見れば分かるように、x が小さければ

${\displaystyle \pi (x)<\operatorname {Li} (x)}$

が成り立っている。これが全ての x で成り立つであろうと、ガウスやリーマンさえも予想していたが、これが正しくないことは1914年にジョン・エデンサー・リトルウッドが初めて示した。これが成り立たない最小の x をスキューズ数というが、具体的な値はほとんど分かっていない。なお、${\displaystyle \pi (x)}$ と ${\displaystyle \operatorname {Li} (x)}$ の大小は、x が大きくなるにつれて無限に入れ替わる^[19]。

リーマン関数

リーマンは、リーマン関数

${\displaystyle R(x)=\sum _{m=1}^{\infty }{\frac {\mu (m)}{m}}\operatorname {Li} (x)^{\frac {1}{m}}}$

を用いて、π(x) に関する以下の公式を与えた。

${\displaystyle \pi (x)=R(x)-\sum _{\rho }R(x^{\rho })}$

ただし、和はゼータ関数の複素零点 ρ 全体をわたる。

R(x) の項だけをとっても、これは Li(x) よりかなり良い近似を与える。

R(x) は、以下の級数を用いて計算可能である^[20]。

${\displaystyle R(x)=1+\sum _{n=1}^{\infty }\left\{{\frac {1}{n\zeta (n+1)}}\cdot {\frac {(\log(x))^{n}}{n!}}\right\}}$

有限体上の既約多項式での類似

有限体上の既約多項式の「分布」を記述する素数定理の類似がある。形式は古典的な素数定理の場合に全く同一に見える。

このことを詳しく述べるために、F = GF(q) を q 個の元を持つ有限体とし、ある固定された q に対し、N_n をモニックで既約な F 上の多項式で、次数が n となるものの数を表すとする。モニックな既約多項式とは、つまり、F の中に係数をもつ多項式と見て、小さな次数の積としては書くことができないような多項式とする。この設定では、モニックな既約多項式は、他の全てのモニックな多項式はモニックな既約多項式の積で書くことができるので、素数の役割を果たす。すると次のことを証明することができる。

${\displaystyle N_{n}\sim {\frac {q^{n}}{n}}}$

x = qⁿ を代入すると、この式の右辺は、

${\displaystyle {\frac {x}{\log _{q}x}}}$

であり、類似がより明白になる。qⁿ は次数 n のモニックな既約多項式であるので、このことは次のように言い換えることができる。次数 n のモニック多項式をランダムに選ぶと、既約である確率は、約 1/n である。

リーマン予想の類似、すなわち、

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

が成り立つことを証明することができる。

多項式についての命題の証明は、古典的な（数についての）命題の証明に比較して、非常に易しい。短い組み合わせ的な議論により証明することができる^[21]。まとめると、F の次数 n の拡大の全ての元は、n を割る次数 d のある既約多項式の根であり、2つの方法でこれらの根の数を数え上げることにより、

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

を成立させることができる。ここに和は n の因子 d の全てを渡る。よって、μ(k) をメビウス関数とすると、反転公式は、

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

である。（この公式をガウスは既に知っていた。）主要項は d = n であり、残余項の境界を示すことは難しくはない。多項式の「リーマン予想」の命題は、最大な n の n 未満の因子は n/2 よりも大きくはなり得ないという事実には依存しない。