インテジャーズ

INTEGERS

数、特に整数に関する記事。

クラトフスキの閉包・補集合定理

定理 (Kuratowski, 1922) (X,\mathcal{O})を位相空間とする。このとき、Xの部分集合Aに対して閉包および補集合を取る操作を繰り返しても高々14個の集合しか得られない。また、実際に相異なる14個の集合が得られる例がある。

この定理の証明を解説します。

Kuratowskiモノイド

位相空間(X,\mathcal{O})に対する閉包、補集合を取る写像 2^X\to 2^Xをそれぞれ b, cと表す*1。また、\mathrm{id}\colon 2^X\to 2^Xは恒等写像とする。合成を積、\mathrm{id}を単位元とし、b,cが生成するモノイドをK(X,\mathcal{O})と表すことにする。

b^2=b, c^2=\mathrm{id}である。

f,g \in K(X,\mathcal{O})に対して大小関係 f\leq gを、任意のA\subset Xに対して f(A)\subset g(A)が成り立つことと定める。f\leq gかつ f\geq gであれば f=gである。

bは包含順序を保つので (A\subset B\subset X \Longrightarrow b(A)\subset b(B))、g_1\leq g_2であれば bg_1\leq bg_2が成り立つ。

cは包含順序を逆転させるので (A\subset B\subset X \Longrightarrow c(A)\supset c(B))、g_1\leq g_2であれば cg_1\geq cg_2が成り立つ。

内部を取る写像をiとすると、i=cbcである。任意の f\in K(X,\mathcal{O})に対して if\leq fである。

補題 bcbcbcb=bcbである。

証明. cbcbcb=ibcbなので、

cbcbcb \leq bcb.

よって、bの性質より

bcbcbcb\leq bbcb=bcb \tag{1}

が成り立つ。cbcb=ib\leq bなので、bの性質より

bcbcb\leq bb=b.

cの性質より、

cbcbcb\geq cb.

よって、bの性質より

bcbcbcb\geq bcb \tag{2}

が成り立つ。(1)(2)よりbcbcbcb=bcbが示された。 Q.E.D.

高々14個であることの証明。

命題 K(X,\mathcal{O})=\{\mathrm{id},b,c,bc,cb,bcb, cbc,bcbc,cbcb,bcbcb,cbcbc,bcbcbc,cbcbcb,cbcbcbc\} である。

証明. b^2=b, c^2=\mathrm{id}という性質からK(X,\mathcal{O})\mathrm{id}以外の任意の元はbcを交互に繰り返す文字列に還元される。bcbcbcbおよび8文字以上を使うこのような文字列は補題によって必ず長さを短く還元できるので証明が完了する。 Q.E.D.

14個得られる実例

X=\mathbb{R}として通常の位相を考える。

A:=(0,1)\cup (1,2)\cup \{3\} \cup ([4,5]\cap\mathbb{Q})

とせよ。

\begin{align}
A&=(0,1)\cup (1,2)\cup \{3\} \cup ([4,5]\cap\mathbb{Q})\\
b(A)&=[0,2]\cup\{3\}\cup[4,5]\\
c(A)&=(-\infty,0]\cup\{1\}\cup[2,3)\cup(3,4)\cup([4,5]\setminus\mathbb{Q})\cup (5,\infty)\\
bc(A)&=(-\infty,0]\cup\{1\}\cup[2,\infty)\\
cb(A)&=(-\infty,0)\cup(2,3)\cup(3,4)\cup(5,\infty)\\
bcb(A)&=(-\infty,0]\cup[2,4]\cup[5,\infty)\\
cbc(A)&=(0,1)\cup(1,2)\\
bcbc(A)&=[0,2]\\
cbcb(A)&=(0,2)\cup(4,5)\\
bcbcb(A)&=[0,2]\cup[4,5]\\
cbcbc(A)&=(-\infty,0)\cup(2,\infty)\\
bcbcbc(A)&=(-\infty,0]\cup[2,\infty)\\
cbcbcb(A)&=(-\infty,0)\cup(2,4)\cup(5,\infty)\\
cbcbcbc(A)&=(0,2)
\end{align}

の14個は全て相異なっている。

*1:閉包(closure)、補集合(complement)ともに頭文字はcであるが、閉包の方はよく\overline{A}で表すので、barのbを採用した。

わにたろうとわに子のぼうけん

これは私が1997年12月18日に執筆した物語を記録するものである。

登場人物

わにたろう
わに子
わにみ(おかあさん)
わにさぶろう(おとうさん)
ちゅん(すずめ)
スーパーきょうわくわるわるくじら王

f:id:integers:20190814202953p:plain

わにたろうとわに子のぼうけん


「わにたろうくんおきて」


わに子はぼうけんのすきな女のわにです。


「またぼうけんか。」


わにたろうはねむそうに言いました。


「わるい。」


わに子がおこって言いました。


「そうだ海できょうそうしない。」


わに子がたずねました。


「うん。いくよ。」


わにたろうが答えました。


「じゃあ行こう。」


わに子がうれしそうに言いました。


二人は北のしままできょうそうしましたが、わにたろうがとちゅうで、


「もうおよげないよう。」


となきました。


わに子は


「もう、しょうがないな。」


といってせなかにのせました。


なんとかしままでつきました。


二人はつかれたのでねむってしまいました。


「わに子なんか音しない。」


わにたろうが言いました。


「え、あ火山だよ。」


f:id:integers:20190814203123p:plain


二人はおきました。


二人はいそいで南のしまにいこうとしました。


二人は海に入っておよぎました。


南のしまにつきました。


「あれ、火山は、ゆめだったの。」


二人はいっしょに言いました。


「でもおよげたじゃん。」


わに子が言いました。


「まあね。」


わにたろうがじまんそうに言いました。


「あ、はちのすふんじゃった。」


とわにたろうが言いました。


f:id:integers:20190814203238p:plain


二人はおおいそぎでにげ回りました。


はちはにげました。でも、


「いたいよー。」


わにたろうがさされてしまいました。


がすぐなおりました。


そこへすずめのちゅんがきました。


「いっしょにあそばない。」


わに子が言いました。


「いいよ。」


ちゅんが言いました。


「遠足にいくんじゃなかったの。」


「ちゅうしになったの。」


「じゃんけんしない。」


「でももうおそいから帰るよ。」


ちゅんが言いました。


「バイバイ。」


わに子とわにたろうが言いました。


二人はふねにのって家に帰りました。


f:id:integers:20190814203403p:plain


f:id:integers:20190814203622p:plain


「今日はすごいぼうけんだったね。」


わに子が言いました。


「ねえ、おかあさん。」


わに子が言いました。


「なんだい。」


おかあさんのわにみが言いました。


「あのね 今日、すごいぼうけんしたんだよ。」


わにたろうが言いました。


f:id:integers:20190814203453p:plain


「もう わたしがいおうとしたのに。」


わに子がおこりました。


「けんかしちゃだめよ。」


とおかあさんにいわれ


「はい。」


と二人はちいさいこえで言いました。


二人は家ではなく外でまたねてしまいました。


f:id:integers:20190814203424p:plain


「ねえ、海にもぐらない。」


わにたろうは言いました。


「うん、いいよ。」


わに子が言いました。


二人はゆめのなかで海にもぐりました。


「ねえねえなにか光ってるよ、いってみない。」


「うんそうだね」


「あっおかねだ。」


f:id:integers:20190814203524p:plain


二人はよろこんだけどそのとき


「うわー。」


f:id:integers:20190814203824p:plain


二人はスーパーきょうわくわるわるくじら王にくわれてしまいました。


二人はおなかのなかでないているとさかなたちがきました。


f:id:integers:20190814203845p:plain


「どうしたんだい、スーパーきょうわくわるわるくじら王にたべられたのかい。」


わにたろうが言いました。


「うんそうなんだよ。」


さかなたちもないてしまいました。


「そうだ、計画をた(て)るんだ。」


さかなたちとわに子とわにたろうは計画をたてています。


f:id:integers:20190814203701p:plain


「まずしんでいるさかなをつなげてくじらのおなかをたたけばいいと思うけど。」


わにたろうがしんけんになって言いました。


「どうやってつなげるの。」


わに子が言いました。


みんな考えていると


「そうだ、くじらのよだれでひっつけたらいいんだよ。」


さかなたちが言いました。


みんな一づつつくりました。


たたいてみるとまるいあながあいてみんなあなからでると


「やったー。」


とみんな言いましたが、そこはまだくじらのはのところでした。


みんながっかりしたけどつぎのさくせんをきめました。


「わにたろうくんがくじらのはをかんではをおったらいいと思うけど。」


とさかなたちが言いました。


みんなでれました。その時二人はゆめからおきました。


「またゆめだったのか」


二人はいっしょに言いました。


そのときおとうさんのわにさぶろうがしごとから帰ってきて


「こらなにしてんの。」


とおこられました。


「ごめんなさい。」


二人はおとうさんにいってわらいながら帰りました。


f:id:integers:20190814203917p:plain

Chebyshevによる(素数計数関数についての)Legendre予想の否定的解決について

Chebyshevは素数定理の弱い版である

\displaystyle c_1\frac{x}{\log  x} \leq \pi(x) \leq c_2\frac{x}{\log  x}

を示しており(c_1, c_2は正の定数), 極限\displaystyle \lim_{x\to \infty}\frac{\pi(x)\log x}{x}が存在するならば1でなければならないということを示していました.

実は彼はLegendre予想の否定という仕事もやっています(xに関する漸近挙動はx\to \inftyを考える).

Legendre予想 (1798/1808) \pi(x)
\displaystyle \pi(x)=\frac{Bx}{\log x-A+o(1)}\tag{1}
を満たし, 更にA=1.08366..., B=1が成り立つであろう.

とりあえず, これは素数定理より強い予想ですが, Aの値は間違えており, Chebyshevが次を示しました.

定理 (Chebyshev, 1848) (1)が成り立つのであれば, A=B=1でなければならない.

実はGaussは正しく予想していたようです. Chebyshevは\zeta^{(m)}(s)s\to 1+0の挙動を使って少し強い形で定理を証明し, 実際に極限が存在するという難しい部分はde la Valée Poussinが1899年に証明しています(素数定理の証明は1896年).

さて, 実は上記Chebyshevの定理は非常に簡単に証明できることがPintzによって指摘されています.

J. Pintz, On Legendre's prime number formula, Amer. Math. Monthly 87 (1980), 733-735.

その証明を紹介したいのですが, ちょうど私が執筆した素数定理の証明の本

note.mu

の中で示されている公式達を使わせていただくと簡単に紹介できるのでそうさせていただきます. この本では第一世代・第二世代・第三世代のビッグ・オー不等式があって, 第三世代まで行くと素数定理の証明が可能となったということが書かれています(なお, この記事ではビッグ・オー不等式としてではなく漸近公式のみを考えれば十分です).

一言で述べると, 上記Chebyshevの定理は第二世代の(von-Mangoldt関数版の)Mertensの第一定理から瞬殺されます. Pintzが

So it is curious that Legendre's conjecture (1.2) had remained open for 40 years.

とコメントしているのは納得です.

PintzによるChebyshevの定理の証明

\Lambda(n)はvon-Mangoldt関数(素数定理本 定義6.9). \psi(x)は第二Chebyshev関数(素数定理本 定義6.13). 実際には次を示す.

定理 (Pintz) \psi(x)
\displaystyle \psi(x)=Cx+\frac{(D+o(1) )x}{\log x}\tag{2}
を満たすのであれば, C=1かつD=0でなければならない.

補題  f(x)=o(g(x))であり, f(x), g(x)は任意のx\geq aに対して[a,x]でリーマン積分可能であるとする(a \in \mathbb{R}). \int_a^xg(t)\mathrm{d}t\to\infty \ (x \to \infty)であれば,
\displaystyle \int_a^xf(t)\mathrm{d}t=o\left(\int_a^xg(t)\mathrm{d}t\right)
が成り立つ.

証明. 任意に\varepsilon > 0をとり, t\geq cであれば \left|f(t)\right|\leq \varepsilon g(t)が成り立つとする. このとき,

\displaystyle \left|\int_a^xf(t)\mathrm{d}t\right| \leq \int_a^c\left|f(t)\right|\mathrm{d}t+\int_c^x\left|f(t)\right|\mathrm{d}t\leq A+\varepsilon\int_c^x\left|g(t)\right|\mathrm{d}t

と評価できる. ここで, A:=\int_a^c\left|f(t)\right|\mathrm{d}t. 仮定よりxが十分大きければ

\displaystyle \left.\left|\int_a^xf(t)\mathrm{d}t\right|\right/\int_a^xg(t)\mathrm{d}t \leq 2\varepsilon

とできる. Q.E.D.

Pintzの定理からChebyshevの定理が出ること(この部分は基本的ということでPintzの論文には書かれていない): Abelの総和公式(素数定理本 命題5.1)においてa_n=\frac{\Lambda(n)}{\log n}, \varphi(x)=\log xとすると, \displaystyle \sum_{2\leq n\leq x}a_n\varphi(n)=\psi(x)であり,

\displaystyle \sum_{2\leq n \leq x}a_n=\sum_{p^k\leq x}\frac{\log p}{k\log p}=\sum_{k=1}^{\infty}\frac{1}{k}\pi(x^{\frac{1}{k}}),

\displaystyle \sum_{k=2}^{\infty}\frac{1}{k}\pi(x^{\frac{1}{k}}) \leq\sum_{k=2}^{[\log_2x]}\sqrt{x}=O(\sqrt{x}\log x)=o\left(\frac{x}{\log^2x}\right)

なので, 補題より

\displaystyle \psi(x)=\pi(x)\log x+o\left(\frac{x}{\log x}\right)-\int_2^x\frac{\pi(t)}{t}\mathrm{d}t+o\left(\int_2^x\frac{\mathrm{d}t}{\log^2t}\right)

を得る. Chebyshevの定理を証明するために(1)が成立すると仮定する. \frac{1}{1-X}=1+X+o(X), (X\to 0)に注意すれば,

\displaystyle \pi(x)\log x=\frac{Bx}{1-\frac{A+o(1)}{\log x}}=Bx+\frac{B(A+o(1) )x}{\log x}+o\left(\frac{x}{\log x}\right).

\pi(t)=\frac{Bt}{\log t}+O\left(\frac{t}{\log^2t}\right)より, 素数定理本 補題4.4によって

\displaystyle \int_2^x\frac{\pi(t)}{t}\mathrm{d}t=B\int_2^x\frac{\mathrm{d}t}{\log t}+O\left(\int_2^x\frac{\mathrm{d}t}{\log ^2t}\right).

素数定理本 補題4.5(4), (6)より

\displaystyle O\left(\int_2^x\frac{\mathrm{d}t}{\log^2t}\right)=o\left(\frac{x}{\log x}\right), \quad \int_2^x\frac{\pi(t)}{t}\mathrm{d}t=\frac{Bx}{\log x}+o\left(\frac{x}{\log x}\right).

である. 以上をまとめると,

\displaystyle \psi(x)=Bx+\frac{(B(A-1)+o(1) )x}{\log x}

の成立がわかった. よって, Pintzの定理が正しければ, B=1およびB(A-1)=0が従い, A=B=1となる. Q.E.D.

Pintzの定理の証明. (2)の成立を仮定する. 素数定理本 命題6.18(17)より

\displaystyle \sum_{n\leq x}\frac{\Lambda(n)}{n}=\log x+O(1)\tag{3}

が成り立つ(今は(2)の成立を仮定しているため \psi(x)=O(x)が使用可能であり, 従って命題6.18(17)の証明(=シャピロのタウバー型定理の証明)で比較的難しかった部分の議論は全て不要であることに注意). また, Abelの総和公式をa_n=\Lambda(n) \ (n\geq 2), \varphi(x)=\frac{1}{x}として適用すれば

\displaystyle \sum_{n\leq x}\frac{\Lambda(n)}{n}=\frac{\psi(x)}{x}+\int_2^x\frac{\psi(t)}{t^2}\mathrm{d}t

が得られる. 仮定より右辺は

\displaystyle O(1)+\int_2^x\frac{C+\frac{D+o(1)}{\log t}}{t}\mathrm{d}t=C\log x+(D+o(1) )\log \log x\tag{4}

が成り立つ. ここで,

\displaystyle \int_2^x\frac{\mathrm{d}t}{t\log t}=\log \log x-\log \log 2

と補題を使った. (3), (4)が両立するためには, C=1, D=0でなければならない. Q.E.D.