数の文化第2回

小テストから以下のような同値類が浮かんできた

n ~ m ⇄ n=ab^2となる最小のa,m=cd^2 となる最小のbが等しい

∃c,b,d∈ℕ(n/b^2=m/d^2=c)

逆数の和がどれだけ大きいか

密度が大きいと発散する

調和級数すなわち、自然数全体は1

冪乗はlim(n→∞)logn/n

定理

素数の逆数の和は発散する

Erdosの証明

補題

自然数nはn=al^2という形に一意的に表せる

ただしaは1より大きい平方数では割れない

nを素因数分解する

n = Πpi^ei

eiが偶数のとき、pi^eiをlに入れる

eiが奇数の時piを1つaに入れて、pi^ei-1をlに入れる

証明

素数の逆数の和が収束すると仮定する

lim(n→∞)∑1/piが、有限の値Aに収束すると仮定

∑(i=1,k)1/pi≥A-1/2, ∑(i=k+1,∞)1/pi<1/2となる番号kが存在する

{p_i | i∈N, i≤k}を小さい素数の集合

{p_i | i∈N, i>k}を大きい素数の集合

このようなkに対して、自然数Nを十分大きく取る

N以下の自然数の集合をを2グループに分割する

集合A

少なくとも一つの大きい素数で割ることができる

その濃度をN1とする

集合B

すべての約数が小さい素数である

その濃度をN2とする

全体集合=集合A∪集合B

∅=集合A∩集合B

N1+N2=N

集合Aの濃度

pk+1の倍数はpk+1間隔で出現

(N/pk+1)個以下

()は床関数

同様に

pk+iの倍数はpk+i間隔で出現

(N/pk+i)個以下

()は床関数

N1 ≤ Σ(N/pk+i) = NΣ(1/pk+i) < N/2

重複して数を数えている可能性があるので、不等号

集合Bの濃度

nがBに属するとする

n=al^2という形に素因数分解する

このときa = Π(i=1,k)pi^e^i

e^iは0,1しか取らない

aのパターンは2^k個

kまでの素因数分解で十分なのは集合Bは小さい素数の積で表される数の集合だから

n = al^2≤ Nでa≥1であるから

l^2 ≤ N

l ≤ √N

よってlの選び方は√N

以上により、al^2の形で表される数の集合Bの個数は2^k√N以下

N2≤2^k√N

もし2^k√N<N/2であるなら矛盾する

変形すると2^2k+2 < N

2^k√N<N/2

2^k+1√N< N

2^2k+2 N < N^2

2^2k+2 < N

このようなkを取ることができる

なぜならkはいくらでも大きく取れるから

そのようなkを取るとN2 < N/2

N1+N2<N

N1 < N/2

N2 ≤ N/2

これは仮定に矛盾する

論理の話

ここでは古典論理を考える

P→Qと¬Q→¬Pの真偽は一致する

Pを「素数は有限個」

Qは「素数の逆数の和は収束する」

¬Pは「素数は無限個」

¬Qは「素数の逆数の和は発散する」

以下の命題の真偽は一致する

「素数は有限個」ならば「素数の逆数の和は収束する」

「素数の逆数の和は発散する」ならば「素数は無限個」

今回

「素数の逆数の和は発散する」を証明したので、「素数は無限個」も導かれる