1

Eratosthenesの篩から素数の無限性と密度を暴く

170
0

※本記事は、はてなブログに投稿してたのを統合してMathlogの様式に合わせて移植したものになります。

以下、関数π,μ,をそれぞれ素数計数関数、Möbius関数、床関数とします。どれも有名な関数なので、それぞれがどのような関数なのかの説明は省略しますが、万が一分からないものがあったらggってWikiとか見てください。
また、関数P:[1,)N
P(x):=pxp:primep
で定めます。ただし、x[1,2)では空積を適用します。

さて今回は、Legendreが発見した、次の素数計数関数に関する等式で遊んでみようと思います。

1以上の実数xに対して
(1)π(x)=π(x)1+dP(x)μ(d)xd
が成り立つ。ただし、総和項はP(x)の正の約数全体に渡って和をとることを意味する。

まずはこれを証明しましょう。

まず、x[1,4)のときはπ(x)=0, P(x)=1より
π(x)=x1
を示すことになるが、これは
x[1,2)π(x)=0,x1=11=0x[2,3)π(x)=1,x1=21=1x[3,4)π(x)=2,x1=31=2
より成立する。

次に x[4,)のとき、P(x)は定義から
P(x)=i=1npi
と書ける。ここで、n:=π(x)であり、p1,p2,,pnx以下の素数を小さい順に並べたものとする。
すると、P(x)の1でない正の約数dは、空でない集合I{1,2,,n}を一意に選んで
d=iIpi
と書けるので、Iの元の個数で分けて考えると、示したい等式の総和項は
dPxμ(d)xd=μ(1)x+k=1nI{1,2,,n}|I|=kμ(iIpi)xiIpi=x+k=1nI{1,2,,n}|I|=k(1)kxiIpi=xk=1n(1)k1I{1,2,,n}|I|=kxiIpi
となる。また、この最右辺において
xiIpi=|iI{mpiZ1mx}|
とできるので、包除原理により
k=1n(1)k1I{1,2,,n}|I|=kxiIpi=k=1n(1)k1I{1,2,,n}|I|=k|iI{mpiZ1mx}|=|i=1n{mpiZ1mx}|
が成り立つ。

以上から
π(x)π(x)+1=x|i=1n{mpiZ1mx}|
を示せばよいことになるが、これはEratosthenesの篩を考えると成立はすぐに分かる。

すなわち、左辺はxより大きくx以下である素数と、素数でも合成数でもない正の整数1を合わせた整数の個数を表す。対して、右辺はx以下の正の整数であって、x以下のどの素数でも割り切れないものの個数を表すが、Eratosthenesの篩から分かるように、これには1とxより大きい素数しか残らない。なぜなら、もしx以下の正の合成数mであって、x以下のどの素数でも割り切れないものが存在すると仮定すると
xmpn+12>(x)2=x
となり矛盾するからである。

よって、両者の個数は一致するので、等式の成立が保証され、最初の等式が成り立つことが示された。

Eratosthenesの篩の部分の補足

x[1,4)では2xxが成り立つので、
xx<2xx
であることを考えると、Bertrandの仮説より、x<pxを満たす素数pが必ず存在する。

証明を読んだら分かると思いますが、実はこの等式(1)はEratosthenesの篩に大きく関係していたのでした。昔初めて篩を習ったときは、単なる素数を見つける手法としか思っていませんでしたが、このように式として表現されると、色々と応用が利きそうに感じます。

というわけで、(1)式を用いて2つの命題を証明します。

素数は無限に存在する。

以下、xを十分大きい正の実数とする。

まずπは増加関数なので、π(x)及びπ(x)xで共に有限の値に収束するか、もしくは共に正の無限大に発散する(すなわち、前者は素数が有限個であることを指し、後者は素数が無限個であることを指す)。

もし素数が有限個であると仮定すると
limx(π(x)π(x))=0
なので、(1)式でxとすれば
(2)limxdP(x)μ(d)xd=1
を得る。

次に、この総和を評価することを考える。そのために、Möbius関数と床関数について成り立つ不等式
μ(d)xdμ(d)xd1
を利用する。なぜこの不等式が成立するかというと、P(x)の定義からP(x)の任意の正の約数dに対してμ(d){±1}であり、μ(d)=1なら
μ(d)xdμ(d)xd1xdxd1xdxd1
μ(d)=1なら
μ(d)xdμ(d)xd1xdxd1xdxd1
となって、それぞれ明らかに成り立つことが分かるからである。

これより
dP(x)μ(d)xddP(x)(μ(d)xd1)=xdP(x)μ(d)ddP(x)1
と評価できる。さらに
dP(x)μ(d)d=μ(1)+k=1nI{1,2,,n}|I|=kμ(iIpi)iIpi=1+k=1nI{1,2,,n}|I|=k(1)kiIpi=1+k=1n(1)kI{1,2,,n}|I|=kiI1pi=i=1n(11pi)=pxp:prime(11p)
および
dP(x)1=d(P(x))=2n=2π(x)
と計算できる(ただしd:NNは約数個数関数)ので
dP(x)μ(d)xdxpxp:prime(11p)2π(x)
が従う。この不等式でxとしてみると、素数が有限個であると仮定したことから
limx2π(x),limxpxp:prime(11p)
は共に正の有限値に収束するので
limx(xpxp:prime(11p)2π(x))=
となり、従って
limxdP(x)μ(d)xd=
が成り立つ。

これは、(2)式に明らかに矛盾する。ゆえに、素数が有限個だと仮定していたので、背理法により素数は無限に存在することが示された。

なんと、素数の無限性を証明できてしまいました。多分あまり知られていない証明法だと思います。

次に、素数密度零定理(正式名称知りません)を証明します。

素数密度零定理

素数は
limxπ(x)x=0
が成り立つ。

実は、この証明のために(1)式を少し改変する必要があるのですが、天下り的になることを避けるために、まずはそのままの形で試してみようと思います(つまり、今から書くものは証明しようとして失敗したものになります)。

(1)式を用いてπ(x)を上から評価する。π(x)は正値関数なので、その評価式をxで割ったものがxで0に収束することを言えばよい。

さて、まず明らかにπ(x)xが成り立つので
π(x)=π(x)1+dP(x)μ(d)xdx1+dP(x)μ(d)xd
を得る。また、素数の無限性の証明と同じ要領で
μ(d)xdμ(d)xd+1
が成り立つことが分かるので、総和項は
dP(x)μ(d)xdx1+dP(x)(μ(d)xd+1)=xdP(x)μ(d)d+dP(x)1=xpxp:prime(11p)+2π(x)
と評価できる。よって
π(x)x1x1x+pxp:prime(11p)+2π(x)x
となり、xで右辺第一項・第二項は明らかに0に収束、さらに
limxpxp:prime(11p)=1ζ(1)=0
となる。しかし
limx2π(x)x=
が成り立つので、このままでは冒頭で述べた方針で証明できないことが発覚する。

何が問題なのかというと、xが大きすぎるために、誤差として出てきた2π(x)がとても邪魔だということです(Wikiによると、この誤差は(1)式の証明に用いた包除原理によるものらしいです)。

これをどうにかするために(1)式を手直しする必要があるわけです。といっても、式の構造を大幅に変えようとするとEratosthenesの篩の本質を失ってしまう可能性があるので、xのみをどうにかしたい気持ちがあります。

そこで、次の不等式に辿り着きます。

f(x)xを満たす関数f(x)に対して
(3)π(x)π(f(x))1+dP(f(x))μ(d)xd
が成り立つ。

一応軽く証明しておきましょう。

(3)式は、定理1と同様に包除原理を用いた議論をすることによって
(4)π(x)π(f(x))+1x|pf(x)p:prime{mpZ1mx}|
と同値であることが分かる。

(4)式について、左辺はf(x)より大きくx以下である素数と、素数でも合成数でもない正の整数1を合わせた整数の個数を表す。対して、右辺はx以下の正の整数であって、f(x)以下のどの素数でも割り切れないものの個数を表すが、Eratosthenesの篩の考えから、これはf(x)より大きい素数のみを素因数としてもつ正の整数と1を合わせた整数の個数に等しい。

よって、明らかに前者(左辺)より後者(右辺)の方が個数が多いので、(4)式は成立し、ゆえに(3)式が示された。

さて、この不等式(3)を用いた素数密度零定理の証明を考えると、証明においてネックだった2π(x)2π(f(x))となり、2π(f(x))2f(x)より2f(x)xが0に収束するようなf(x)をとればよいわけです。

改めてキチンと書きましょう。

命題3

(3)式においてf(x)=logxとしてみると、
π(x)π(logx)1+dP(logx)μ(d)xdlogx1+dP(logx)μ(d)xdlogx1+dP(logx)(μ(d)xd+1)=logx1+xplogxp:prime(11p)+2π(logx)logx1+xplogxp:prime(11p)+2logx
となるので、2logx=elog2logx=xlog2<xであることに注意すると
π(x)xlogxx1x+plogxp:prime(11p)+2logxx0(x)
が成り立ち
limxπ(x)x=0
が従う。

これで証明は完了です。

いかがでしたでしょうか。素数の無限性や素数密度の情報を自明には含まないEratosthenesの篩からこんなに色々証明できて、僕は凄く面白いと思いました。

まだまだ弄れそうな気がするので、もっと色々考えてみたいですね。

投稿日:202182
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

京大理学部B3数理科学系

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中