トポロジー入門(第3回)

[場所1E303,203（月曜日3,4限）]

トポロジー入門のHP

トポロジー入門演習のHP

前回は距離空間の内点、内部、触点、閉包についてやりました。

その続きと、距離空間の連続性について行いました。

前回に引き続き $X$ とすると、適当な距離 $d$ を持つ距離空間とします。

命題

$A\subset X$ に対して、

$(\bar{A})^c=(A^c)^\circ$ が成り立つ。

(証明) $\forall x\in (\bar{A})^c\Leftrightarrow x\not\in \bar{A}$

$\Leftrightarrow \exists\epsilon >0(B_d(x,\epsilon)\cap A=\emptyset)\Leftrightarrow  \exists\epsilon >0(B_d(x,\epsilon)\subset A^c)$

$\Leftrightarrow x\in (A^c)^\circ$

となるため、$(\bar{A})^c=(A^c)^\circ$ が成り立ちます。

前回、

$D=\{(x,y)\in {\mathbb R}^2|x^2+y^2< 1\}$ と定義したときに、

$D'=\{(x,y)\in {\mathbb R}^2|x^2+y^2\ge 1\}\subset\bar{D}$

であることを示したので、今日は、その逆

$\bar{D}\subset D'$

を示しました。

上の例題を用いれば、

$(D')^c\subset (\bar{D})^c=(D^c)^\circ$ であることを示せば十分です。

${\bf x}\in (D')^c=\{{\bf x}\in {\mathbb R}^2|d^2({\bf x},{\bf 0})>1\}$とし、

$\epsilon=d^2({\bf x},{\bf 0})-1$ とします。

このとき、$d^2({\bf x},{\bf 0})\le d^2({\bf x},{\bf y})+d^2({\bf y},{\bf 0})$

であり、

$d^2({\bf y},{\bf 0})\ge d^2({\bf x},{\bf 0})-d^2({\bf x},{\bf y})>d^2({\bf x},{\bf 0})-\epsilon=1$

であるから、${\bf y}\in D^c$ となります。

よって、$B_d({\bf x},\epsilon)\subset D^c$ であるから、

${\bf x}\in (D^c)^\circ$ が成り立ちます。

よって、$D'\subset (D^c)^\circ=(\bar{D})^c$ となります。

つまり、$D'=\bar{D}$ であることがわかりました。

ここで、$A\subset X$ に対して、$\bar{A}\setminus A^\circ$ を$\partial A$ とかき、

境界、また$\partial A$ の点を境界点といいます。

よって今の場合、$\partial D=\bar{D}\setminus D^\circ=\{(x,y)\in {\mathbb R}^2|x^2+y^2=1\}$

となり、直感でいうところの"境界"の概念と一致します。

次の定理を示しました。

定理

$A\subset X$ とする。

$A^\circ$ は $A$ に包まれる最大の開集合である。

$\bar{A}$は $A$ を包む最小の閉集合である。

(証明)$A^\circ \subset A'\subset A$ となる開集合 $A'$ をとります。

$x\in A'$ とすると、開集合であることから、$\exists\epsilon>0(B_d(x,\epsilon)\subset A')$

を満たします。$A'\subset A$ であるから、$x$ は $A$ の内点です。

よって$x\in A^\circ$ となります。つまり、$A^\circ =A'$ となります。

故に、$A^\circ$ は $A$ に包まれる最大の開集合です。

同じように、

$A\subset A''\subset \bar{A}$ を満たす閉集合 $A''$ を取ります。

この補空間をとることで、

$(\bar{A})^c\subset (A'')^c\subset A^c$ となります。

特に、$(A'')^c$ は開集合になります。

命題から $(\bar{A})^c=(A^c)^\circ$ であり、$(A^c)^\circ$ は$A^c$ に包まれる最大の開集合であったから、$(A'')^c=(A^c)^\circ$ となります。よって、$A''=\bar{A}$ であることがわかります。

距離空間の連続性

$X,Y$ を距離空間として、 $f:X\to Y$ を写像とします。
$X,Y$ の距離を $d_X,d_Y$ としておきます。

このとき、$f$ の連続性について考えます。

連続性とは、直感的には「$a\in X$ に近い点は、$Y$ の $f(a)$ の近い点に写っている」

ということなのですが、近い点という言葉を明確にする必要あります。

最初の近い点は、2つ目の近い点とどのような関係になっているのか？

どれほど近いのなら繋がっていると言えるのか？

などすぐに答えにくいことがわかります。

よって、連続性を扱うのを一度放棄して、非連続性について考えるとすっきりします。

つまり、非連続性とは、

$a$ のどんなに近くにも、$f$ で写したときに、$f(a)$ から遠く離れた点のままになっている点があるということです。

遠く離れた点のままになっていることは、$a$ の近より方に寄らずに決める必要がありますから、

最初に遠くの距離 $E>0$ がとれて、そのときに、

$a$ のどんな近くにも点 $x$ が存在して、$f(x)$ が、$f(a)$ から $E$ より近くにいない。

式で言えば、

$\exists E>0 \forall \Delta>0(f(B_{d_X}(a,\Delta))\cap B_{d_Y}(f(a),E)^c\neq \emptyset)$

となります。

この命題を否定すれば連続性が得られるはずです。

よって、否定命題を書き記すと、

$\forall E>0\exists  \Delta>0(f(B_{d_X}(a,\Delta))\cap B_{d_Y}(f(a),E)^c= \emptyset)$

$\equiv \forall \epsilon>0\exists  \delta>0(f(B_{d_X}(a,\delta))\subset B_{d_Y}(f(a),\epsilon))$

$\equiv \forall \epsilon>0\exists  \delta>0\forall x\in X(x\in B_{d_X}(a,\delta)\to f(x)\in  B_{d_Y}(f(a),\epsilon))$

となります。

ここで連続性について定義しておきます。

定義3.1
$(X,d_X),(Y,d_Y)$ を距離空間とする。
写像 $f:X\to Y$ が $a\in X$ で連続であることを、
$\forall \epsilon>0$ に対して、ある$\delta>0$ が存在して、
$$f(B_{d_{X}}(a,\delta))\subset B_{d_Y}(f(a),\epsilon)$$
を満たすことをいう。
任意の $a\in X$ に対して $f$ が連続であるとき、$f$ は
連続であるという。

定義の中の $f(B_{d_{X}}(a,\delta))\subset B_{d_Y}(f(a),\epsilon)$ という条件は、
$f^{-1}$ を取って $B_{d_{X}}(a,\delta)\subset f^{-1}(B_{d_Y}(f(a),\epsilon))$
としても同じことです。


$(X,d_X)=(Y,d_Y)=({\mathbb R},d_1)$ であるとき、
$f$ は実数上の関数となりますが、
これが、連続であるとは、
$\forall \epsilon>0\exists  \delta>0\forall x\in X(x\in B_{d_1}(a,\delta)\to f(x)\in  B_{d_1}(f(a),\epsilon))$
となりますが、$(x\in B_{d_1}(a,\delta)$ は言い換えれば、$|x-a|<\delta$ と書き直せますから、
$\forall \epsilon>0\exists  \delta>0\forall x\in X(|x-a|<\delta \to |f(x)-f(a)|<\epsilon)$
となります。この定義は微積分の授業ででてきた関数の連続性のことを言っています。


次の定理を示しておきます。

定理3.2
$f:(X,d_X)\to (Y,d_Y)$ が連続であるとは、
$\forall U\in \mathcal{O}_Y$ ならば、$f^{-1}(U)\in \mathcal{O}_X$
をみたすことと同値である。

ここで、$\mathcal{O}_d$ は距離 $d$ による開集合全体(開集合系)
を表します。また、$\mathcal{O}_{d_X}=\mathcal{O}_X$ と略記しています。

(証明)
$f$ が連続であると仮定します。
$\forall U\in \mathcal{O}_{X}$ とし、$\forall a\in f^{-1}(U)$ とすると、
$f(a)\in U$ であり、$U$ が開集合であるから、$\epsilon>0$ が存在して、
$B_{d_Y}(f(a),\epsilon)\subset U$ を満たし、
$f$ の連続性からある$\delta>0$ が存在して、
$B_{d_X}(a,\delta)\subset f^{-1}(B_{d_Y}(f(a),\epsilon))\subset f^{-1}(U)$ となります。
よって、$f^{-1}(U)$ が開集合ということになります。

逆に $\forall U\in \mathcal{O}_Y\Rightarrow f^{-1}(U)\in \mathcal{O}_X$
が成り立つとします。
$a\in X$ に対して、
$\forall \epsilon>0$ に対して、
$B_{d_X}(a,\epsilon)$ は開集合であるから、
$f^{-1}(B_{d_Y}(f(a),\epsilon))$ は開集合ですから、
$a\in f^{-1}(B_{d_Y}(f(a),\epsilon))$ に対してある  $\delta>0$ が存在して。
$B_{d_X}(a,\delta)\subset f^{-1}(B_{d_Y}(f(a),\epsilon))$
が成り立つので、$f$ の $a$ での連続性が成り立ちます。
よって $f$ が連続となります。

$d(x,A)=\inf\{d(x,a)|a\in A\}$
とします。
このとき、
$\varphi_A:X\to {\mathbb R}$ を
$\varphi_A(x)=d(x,A)$ と定義します。
このとき、最後に次の定理を示しました。

定理3.3
$\varphi_A:X\to {\mathbb R}$
は連続である。

(証明)
$\forall x,y\in X(\varphi_A(x)-\varphi_A(y)\le d(x,y))$
が成り立つことを示します。
$\forall z\in A$ に対して $d(x,A)\le d(x,z)\le d(x,y)+d(y,z)$ が成り立ち、
$d(x,A)-d(y,z)\le d(x,y)$ であり、$d(x,y)$ は $\{d(x,A)-d(y,z)|z\in A\}$ の上界であるから、
$d(x,A)-d(y,A)\le d(x,y)$ が成り立ちます。
$x,y$ を入れ替えれば、
$-d(x,y)\le d(x,A)-d(y,A)$ も成り立つので、
$|\varphi_A(x)-\varphi_A(y)|\le d(x,y)$ が成り立ちます。

ここで、$\epsilon>0$ に対して、$\delta=\epsilon$ としておけば、
$d(x,a)\le \delta$ となる任意の $x$ に対して、
$|\varphi_A(x)-\varphi_A(y)|\le d(x,a)\le \epsilon$ であるから、
$\varphi_A(x)$ は $x=a$ で連続である。
よって、$\varphi_A:X\to {\mathbb R}$ は連続写像であることがわかりました。

距離空間 $(X,d)$ において、$A=\{a\}$ と $r>0$ に対して、
$\varphi_A^{-1}((-\infty,r))=B_d(a,r)$ となります。
$(-\infty ,r)$ は開集合であるから、$B_d(a,r)$ が開集合であることが
確認できます。
(ただ、$B_d(a,r)$ はすでに開集合であることは定義からわかるので
証明というわけではありません)

一般に、$\varphi_A^{-1}((-\infty,r))=\cup_{a\in A}B_d(a,\epsilon)$
であることがわかります。
この右辺も開集合であることが確認できます。
これも任意個の和集合が開集合であることが示されていた
ことでした。

トポロジー入門(第2回)

[場所1E303,203（月曜日3,4限）]

トポロジー入門のHP

トポロジー入門演習のHP

今日は開集合の性質を使って距離空間
の開集合の性質について以下の6つの定理を示しました。
ここでも証明を書いておきます。
講義中は証明したものでも以下では少し省略しているものもあります。

$U\subset X$ が開集合である定義は、
$\forall x\in U\exists\epsilon>0(B_d(x,\epsilon)\subset U)$
を満たすものをいいいました。

以下、$(X,d)$ を距離空間として共通して用います。
$X$ と書けばすべてこの距離空間とします。
また、$(X,d)$ の開集合をすべて合わせた集合を
開集合系といい、$\mathcal{O}_d$ と表すことにします。

定理2.1
$\emptyset,X\in \mathcal{O}_d$ である。

(証明) 空集合は元が取れないので、開集合の条件は無条件に成り立ちます。
よって空集合は開集合です。
$x\in X$ に対して、$B_d(x,\epsilon)\subset X$
であるので $X$ は開集合です。

注 空集合 $\emptyset$ は $\forall x(x\not\in \emptyset)$
を満たす唯一の集合です。
また、$A$ が開集合かどうかは、$x\in A$ が存在するときの条件しか
ありませんが、ということは元がとれない場合は無条件だということです。

定理2.2
$U,V\in \mathcal{O}_d$ とすると、$U\cup V$ と $U\cap V\in \mathcal{O}_d$ である。

(証明)
$U,V$ を開集合とします。
$\forall x\in U\cup V$ とすると、$x\in U$ もしくは　$x\in V$ です。
仮に、$x\in U$ としたら、
$\exists \epsilon>0(B_d(x,\epsilon)\subset U)$ です。
$U\subset U\cup V$ であるから、
$B_d(x,\epsilon)\subset U\cup V$ となり、$U\cup V$ が開集合であることが
わかります。
$x\in V$ であるときも同様です。
よって $U\cup V$ は開集合です。

同じように証明することで $U\cap V$ も開集合となります。

定理2.3
$x\in X$ と$\epsilon>0$ に対して、
$B_d(x,\epsilon)$ は開集合である。

(証明)
$y\in B_d(x,\epsilon)$ とし、$\delta=\epsilon-d(y,x)$ とおきます。
このとき、$\delta>0$ となります。
$\forall z\in B_d(y,\delta)$ とすると、
$d(z,x)\le d(z,y)+d(y,x)< \delta+d(y,x)=\epsilon$
となり、$z\in B_d(x,\epsilon)$ です。
ゆえに、$B_d(y,\delta)\subset B_d(x,\epsilon)$ が成り立ち、
$B_d(x,\epsilon)$ は開集合であることがわかります。


定理2.4
$x\in X$ に対して、$\{x\}$ は閉集合である。

(証明)
$\{x\}^c$ が開集合であることを示せば十分です。
$\forall y\in \{x\}^c$ とします。
$\delta=d(x,y)>0$ とします。
このとき、$\forall z\in B_d(y,\frac{\delta}{2})$
とすると、$d(x,y)\le d(x,z)+d(z,y)$ であり、
$d(x,z)\ge d(x,y)-d(z,y)=\delta-d(z,y)\ge \delta-\frac{\delta}{2}=\frac{\delta}{2}>0$
ですから、$x\neq z$ となります。
よって、$B_d(y,\frac{\delta}{2})\subset \{x\}^c$ であるから、
$\{x\}^c$ は開集合であることがわかりました。

この証明から、帰納法を使えば、開集合を有限個集めて共通集合を
とっても開集合であることがわかるし、
$\{U_\lambda\in \mathcal{O}_d|\in \lambda\in \Lambda\}$ のように
開集合を任意に持ってきたとしたら、
$\cup_{\lambda\in \Lambda}U_\lambda\in \mathcal{O}_d$ となります。

上のことをまとめますと、以下のようになります。
(I) $\emptyset,X\in \mathcal{O}_d$ となる。
(II) $n\in {\mathbb N}$ に対して、$U_1,U_2,\cdots, U_n\in \mathcal{O}_d$ である。
(III) 開集合の集まり $\{U_\lambda\in \mathcal{O}_d|\lambda\in \Lambda\}$ に対して、$\cup_{\lambda\in \Lambda}U_\lambda\in \mathcal{O}_d$ となる。


定義2.1
$(X,d)$ を距離空間とし、$A\subset X$ とする。
$x\in A$ が $A$ の内点であるとは、
$\exists\epsilon >0(B_d(x,\epsilon)\subset A)$
を満たすことである。
$A^\circ$ を $A$ の内点全体の集合を表し、
$A$ の内部という。

定義2.2
$(X,d)$ を距離空間とし、$A\subset X$ とする。
$x\in X$ が $A$ の蝕点であるとは、
$\forall \epsilon >0(B_d(x,\epsilon)\cap A\neq \emptyset)$
を満たすことである。
$\bar{A}$ を $A$ の蝕点全体の集合を表し、
$A$ の閉包という。

定理2.5
$A^\circ$ は開集合であり、$\bar{A}$ は閉集合である。

証明
$x\in A^\circ$ とすると、内点の定義から
$\exists \epsilon>0(B_d(x,\epsilon)\subset A)$ がわかります。
$B_d(x,\epsilon)$ は開集合であるから $\forall y\in B_d(x,\epsilon)$ に対して、
$\epsilon’>0(B_d(y,\epsilon')\subset B_d(x,\epsilon))$
が成り立ちます。
よって $B_d(y,\epsilon’)\subset A$ であるから $y\in A^\circ$ となります。
つまり、$B_d(x,\epsilon)\subset A^\circ$ ですから、
$A^\circ$ は開集合であることがわかります。

$(\bar{A})^c$ が開集合であることを示します。
$\forall x\in (\bar{A})^c$ とすると、$x\not\in \bar{A}$ であり、
$\exists \epsilon>0$ に対して、$B_d(x,\epsilon)\cap A= \emptyset$
となります。$y\in B_d(x,\epsilon)$ に対して、
$\exists \epsilon'>0(B_d(y,\epsilon’))$ であり、$B_d(y,\epsilon’)\cap A=\emptyset$
ですから、$y\in (\bar{A})^c$ となります。
つまり、$B_d(x,\epsilon)\subset (\bar{A})^c$ がわかりました。

定理2.6
$A$ が開集合 $\Leftrightarrow A=A^\circ$
$A$ が閉集合 $\Leftrightarrow A=\bar{A}$
を満たす。

(証明)
$A$ を開集合とします。$A^\circ\subset A$ ですから、$A^\circ\subset A$ を示せばよい
ことになります。このとき、$\forall x\in A$ としますと、
$\exists \epsilon>0(B_d(x,\epsilon)\subset A)$
が成り立ち、$x\in A^\circ$ となります。
よって、$A=A^\circ$ が成り立ちます。
逆に $A=A^\circ$ であるとすると、$A^\circ$ は開集合であったから $A$ は開集合
となります。

閉集合の場合も同様の証明なのでここでは省略します。

トポロジー入門(第1回)

[場所1E303,203（月曜日3,4限）]

トポロジー入門のHP

トポロジー入門演習のHP

今学期からトポロジー入門の授業をもつことになりました。
教科書は今のところ数理科学で連載している
「例題形式で探求する集合・位相」(第6章～)
です。

距離空間
今回は距離空間から始めました。
「例題形式で探求する集合・位相」でいえば、第6章の内容にあたります。
その前に集合の復習をしたのですが、それはここでは省略します。

定義[距離空間]
集合 $X$ に対して、関数 $d:X\times X\to {\mathbb R}$ が以下を満たすとき、
$d$ を距離関数という。
任意の$x,y,z\in X$ に対して
(1) $d(x,y)=0 \Leftrightarrow x=y$
(2) $d(x,y)=d(y,x)$
(3) $d(x,y)+d(y,z)\ge d(x,z)$
である。

距離関数 $d$ をもつ集合 $(X,d)$ を距離空間という。
(3)の不等式を三角不等式といいます。

数理科学では、
(1) $\forall x,y\in X(d(x,y)\ge 0\land d(x,y)\to x=y)$
と書いていますが、
この定義は間違っています。
この定義であると、$d(x,x)=0$ であることが示せません。

また、上の定義では $d(x,y)\ge 0$ であることは、
仮定されていませんが、
(2),(3)と、$d(x,x)=0$ であることから、
$d(x,y)+d(y,x)=2d(x,y)\ge d(x,x)=0$ であることから $d(x,y)\ge 0$
であることが示されます。
このことは数理科学のサポート情報にも載せました。
たまに、間違いを犯しているのでもしおかしいなと思ったら
このサポート情報をみてください。
また、サポート情報にもない場合は下のコメント欄やメールにて情報を
お寄せください。

開集合・閉集合
まず、開球体を定義します。

定義[開球体]
$(X,d)$ を距離空間とする。
$x\in X$ に対して、実数 $r>0$ に対して、$r$-開球体
$B_d(x,r)=\{y\in X|d(x,y)<r\}$ と定義する。

つぎに、以下を定義します。

定義[開集合・閉集合]
$(X,d)$ を距離空間とする。
$U\subset X$ が開集合であるとは、
$\forall x\in U\exists \epsilon >0(B_d(x,\epsilon)\subset U)$ である。
$F\subset X$ が閉集合であるとは、

$F^c$ が開集合であることである。

注意として、ある距離空間において、ある部分集合が開集合であるかどうかは、
その距離 $d$ に依存し、集合だけに依存しません。

距離空間の例を与えておきます。

例1、
${\mathbb R}^n$ にの2つ元
${\bf x}=(x_1,x_2,\cdots, x_n), {\bf y}=(y_1,y_2,\cdots y_n)$
に対して $d^n({\bf x},{\bf y})=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$
と定義すると、距離関数 $d:X\times X\to {\mathbb R}$
が与えられます。この距離関数によって与えられる距離空間を

ユークリッド空間 $({\mathbb R}^n,d^n)$ といいます。

例2
集合 $X$ に対して、$d:X\times X\to {\mathbb R}$ を
$$d(x,y)=\begin{cases}1&x\neq y\\0&x=y\end{cases}$$
と定義したとき、$d$ は $X$ 上の距離関数となり、
$(X,d)$ を離散距離空間いいます。

これらが距離空間であることは、上の距離空間であるための条件を
確かめればよいですが、ここでは省略します。
証明は例えば数理科学の「例題形式で...」の記事を見てください。

例2では、任意の1点集合 $\{x\}$ は $B_d(x,\frac{1}{2})$
ですので開集合ですが、例1ではどんな1点集合も開集合にはなりません。

というのも、実数空間 $({\mathbb R},d^1)$ において、$\forall x\in {\mathbb R}$ に
対して、 $B_d(x,\epsilon)\subset \{x\}$ である $\epsilon$ が
存在したとすると、$x+\frac{\epsilon}{2}\in B_d(x,\epsilon)$
であり、$x+\frac{\epsilon}{2}\not\in \{x\}$ ですから、
$B_d(x,\epsilon)\not\subset \{x\}$ となり矛盾します。
よって $\{x\}$ は開集合ではありません。

数学外書輪講I(第15回)

[場所1E501（月曜日5限）]

HPに行く

このページは7/29に行われた授業に基づいています。

完全グラフを完全二部グラフによって分割すること

についてやりました。

前々回(こちら)も同じ定理について証明してもらいましたが、

今回はマトウセクに書かれている線形代数を用いた方法です。

定理をもう一度書いておくと、次のようになります。

定理

もし、完全グラフ $K_n$ が部分完全二部グラフ $H_1,\cdots ,H_m$

によって分割することができるなら、$m\ge n-1$ である。

完全二部グラフによって分割できるとは、

完全グラフ $K_n$ の頂点と辺を用いて完全二部グラフ $H_j$ を

$m$ 個つくったとき、$K_n$ の辺の集合が、$H_1,\cdots, H_m$ の

辺の集合によってちょうど分割されるということになります。

つまり、$H_1,H_2,\cdots, H_m$ のそれぞれの辺の数の和は、ちょうど

${}_nC_2=n(n-1)/2$ 個ということになります。

$H_j$ の頂点の集合を $V(H_j)=X_j\sqcup Y_j$ とします。

いま、$n\times n$ 行列 $A_k=(a_{ij}^{(k)})$ を

$$a_{ij}^{(k)}=\begin{cases}1&i\in X_k\text{かつ}j\in Y_k\\0&otherwise\end{cases}$$

とします。

すると、$\text{rank}(A_k)=1$ であることはすぐわかります。

$A=\sum_{k=1}^mA_k$ とすると、

また、$A+A^t=J_n-I_n$ が成り立ちます。

ここで、$I_n$ は $n\times n$ 単位行列で、$J_n$ は $n\times n$ 行列で、

すべての成分が $1$ となる行列とします。

ここで、$\text{rank}(A)\le \sum_{i=1}^m\text{rank}(A_i)=m$

であり、$n-1\le \text{rank}(A)$ であることを示せればよいです。

$\text{rank}(A)\le n-2$ であるとします。
${\bf 1}$ をすべて $1$ からなる横ベクトルとします。
すると、$\begin{pmatrix}A\\{\bf 1}\end{pmatrix}$ のランクは $n-1$ 以下であるから、

このとき、${\bf x}\in {\mathbb R}^n$ が存在して、

$A{\bf x}={\bf 1}\cdot {\bf x}={\bf 0}$ かつ ${\bf x}\neq {\bf 0}$ となります。

このベクトル ${\bf x}$ を用いて、
$${\bf x}^t(A+A^t){\bf x}={\bf x}^t(J_n-I_n){\bf x}={\bf x}^tJ_n{\bf x}-{\bf x}^t\cdot {\bf x}=-{\bf x}^t\cdot {\bf x}<0$$
かつ、
$${\bf x}^t(A+A^t){\bf x}={\bf x}^tA{\bf x}+{\bf x}^tA^t{\bf x}={\bf x}^t\cdot {\bf 0}+{\bf 0}^t\cdot {\bf x}=0$$
となり、矛盾します。

背理法から、$n-1\le \text{rank}(A)$ であることがわかります。

よって、$n-1\le m$ であることがわかります。

数学外書輪講I(第14回)

[場所1E501（月曜日5限）]

HPに行く

このページは7/22に行われた授業に基づいています。

フィボナッチ数列を手早く計算する

これはマトウセクのMiniature 1に関する内容です。

フィボナッチ数列とは、
$F_{n+2}=F_{n+1}+F_n$　
かつ $F_0=0$ かつ $F_1=1$ を満たすものをいいます。

このフィボナッチ数列の第 $n$ 項 $F_n$ を計算するのに、
この漸化式を用いれば、大体 $n$ 回の加法によって計算されます。
この回数のオーダーを計算量ということにすると、
この計算量は $n$ ということになります。

今、${\bf v}_n=\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}$
とし、
$$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$$
とおくと、
$${\bf v}_{n+1}=M\cdot {\bf v}_n$$
が成り立ちます。そうすると、
${\bf v}_n=M^n\cdot {\bf v}_0$ となります。
ゆえに、${\bf v}_n$ を計算するのに $n$ 回の行列の掛け算を
計算することになりますので、やはり計算量は $n$ ということになります。

しかし、$n=2^m$ の場合、以下のように計算を工夫します。
$M^2=M\cdot  M$, $M^4=M^2\cdot M^2$, $M^8=M^4\cdot M^4,\cdots$
$M^{2^m}=(M^{2^{m-1}})^2$ として計算をするのです。
そうすると $M^{2^m}$ を計算するのに、$m$ 回の行列の掛け算を計算すればよい
つまり、$m$ 回の計算量ということになります。
$m=\log_2n$ だけ計算すればよいことになり、
この工夫により、計算量 $n$ からは大分改善されたことになります。

一般にはどうかというと、一般の自然数 $n$ は
$k_1<k_2<\cdots <k_t$ なる単調増加な自然数列を用いて、
$n=2^{k_1}+\cdots +2^{k_t}$
のように一意的に表すことができます。
これは２進法です。よって、特に、$2^{k_t}\le n<2^{k_t+1}$ となります。

よって、$M^n=M^{2^{k_1}}M^{2^{k_2}}\cdots M^{2^{k_t}}$
のように書くことができます。
$M^n$ を計算するに、上とおなじようにしてまずは、$M^{2^{k_t}}$
を計算します。
そのとき、$M^2, M^4,M^8,\cdots$ は計算されているので、
それを用いて、$M^{2^{k_1}}M^{2^{k_2}}\cdots M^{2^{k_t}}$ が計算できます。

このとき、最大 $k_t$ 回の積を計算することで、$M^n$ が計算できます。

よって、合計で計算量 $2k_t$ で $M^n$ が計算できることになります。
$2^{k_t}\le n$ であるから、$k_t \le \log_2n$ よって、$2\log_2n$ の
計算量となります。

フィボナッチ数列の一般項
これはマトウセクのMiniature 2の内容です。
上の数列の一般項 $F_n$ を線形代数を用いて計算します。
$(a_0,a_1,a_2,\cdots, a_n,\cdots )\in {\mathbb R}^\infty$
のように、数列の集合を考えます。この集合は各成分をそれぞれ足すことによって
また、それぞれの成分にスカラー倍することによって
ベクトル空間になります。
ふつうの有限次元ベクトル空間の構造の素直な拡張になっています。
$(a_0,a_1,a_2,\cdots, a_n,\cdots )=(a_n)$ と書くことにします。
$W=\{(a_n)\in {\mathbb R}^\infty|a_{n+2}=a_{n+1}+a_n\}$ とします。
このとき、$W$ は ${\mathbb R}^\infty$ の部分ベクトル空間となります。
その証明は省略します。
ただし、ゼロベクトルは ${\bf 0}=(0,0,\cdots)$ となります。

注意
また、フィボナッチ数列は、最初の2項が決まれば、3項目以降は一意的に決ま
ることに注意しておきます。

ここで、$W$ の次元を計算します。
${\bf v}_0=(1,0,1,1,2,3,\cdots )$, ${\bf v}_1=(0,1,1,2,3,5,\cdots)$ とします。
$c_0{\bf v}_0+c_1{\bf v}_1={\bf 0}$ とします。
このとき、$(c_0,c_1,\cdots)=(0,0,\cdots)$ となり、
各成分を比較することによって $c_0=c_1=0$ であるから、${\bf v}_0,{\bf v}_1$ は
1次独立になります。
また、${\bf v}=(a_0,a_1,a_2,\cdots)\in W$ とします。
このとき、${\bf v}-a_0{\bf v}_0-a_1{\bf v}_1=(0,0,\cdots)$
となり、上の注意から、この右辺も $W$ の元であるから、${\bf 0}$
そのものになります。

よって、${\bf v}=a_0{\bf v}_0+a_1{\bf v}_1$ であるから、
${\bf v}_0, {\bf v}_1$ は $W$ の基底となります。
ゆえに、$\dim(W)=2$ となります。

$\tau_1=\frac{1+\sqrt{5}}{2}$ $\tau_2=\frac{1-\sqrt{5}}{2}$
としますと、この数は、
$\tau^2=\tau+1$ の解です。

なので、
${\bf u}=(1,\tau_1,\tau_1^2,\cdots)$ と

${\bf v}=(1,\tau_2,\tau_2^2,\cdots)$ は

$W$ の元であることはすぐわかります。

また、$\tau_1\neq \tau_2$ であるから、

${\bf u}$ と ${\bf v}$ は平行ではないだから、

${\bf u},{\bf v}$ は1次独立となります。

${\bf u}, {\bf v}$ は $W$ の基底となります。

よって、${\bf v}_1=(F_0,F_1,F_2,\cdots)$ は

$\alpha {\bf u}+\beta {\bf v}$ となる実数 $\alpha,\beta\in {\mathbb R}$ 

が存在します。

この 0 番目の成分を比べると、

$\alpha+\beta =0$ であり、かつ
1番目の成分を比べると、

$\alpha\tau_1+\beta\tau_2=1$ の連立一次方程式を

解くと、

$\alpha=\frac{1}{\sqrt{5}}$, $\beta=-\frac{1}{\sqrt{5}}$ 

となります。

よって、${\bf v}_1=\frac{1}{\sqrt{5}}{\bf u}-\frac{1}{\sqrt{5}}{\bf v}$

となります。

よって、$n$ 番目の項は、

$$F_n=\frac{1}{\sqrt{5}}(\tau_1^n-\tau_2^n)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$

となります。

数学外書輪講I(第13回)

[場所1E501（月曜日5限）]

HPに行く

この内容は、7/19に行った外書輪講での授業に基づいています。

長方形を正方形で覆うこと

これは、マトウセクのMiniature 12に関する内容です。

内容は以下の定理についてです。

定理

辺の長さが $1$ と $x$ である長方形 $R$ を考えます。

ここで、$x$ はある無理数です。

このとき、内部を共有しない有限個の長方形によって

$R$ を覆うことはできない。

というものです。

この証明を線形代数を用いて行いました。

(証明)

もし、正方形 $Q_1,\cdots, Q_n$ によって、$R$ が覆えたとします。

ここで、$s_i$ を $Q_i$ の1辺の長さとします。

ここで、$\mathbb R$ は ${\mathbb Q}$ 係数の

ベクトル空間であることを用います。

特に、$1$ と $\alpha$ が1次独立であることと、$\alpha$ が

無理数であることは同値です。

$V\subset {\mathbb R}$ を $1, x,s_1,\cdots, s_n$  によって

生成されるベクトル空間とします。

今、

$f:V\to {\mathbb R}$ を

$f(1)=1$ かつ、$f(x)=-1$ となる線形写像とします。

そのような写像は、$b_1,\cdots, b_k$ を $V$ の基底として、

$b_1=1, b_2=x$ として取ることができます。

そのとき、$f(b_1)=1, f(b_2)=-1$ かつ、$f(b_i)=0$ $(i\ge 2)$

として取ればよく、取り方に矛盾しません。

今、2辺が $a,b$ となる長方形 $A$ に対して、$v(A)=f(a)f(b)\in {\mathbb R}$

を割り当てる関数 $v$ を考えます。

そのとき、簡単な考察から、

$v(R)=\sum_{i=1}^nv(Q_i)$ が成り立ちます。

よって、

$v(Q_i)=f(s_i)^2\ge 0$ となり、右辺は非負実数であるのに対して、

左辺は、

$v(R)=f(1)f(x)=-1$ であり、負の数となり、

矛盾します。

よって、$R$ は有限この

正方形で覆えないということになりました。

完全グラフを完全二部グラフによって分割すること

ある集合 $X$ を交わりのない2つの

集合 $A,B$ によって $X=A\sqcup B$ のように分割しておきます。

このとき、二部グラフというのは、$X$ 上のグラフで、

辺集合は必ず $A$ と $B$ の点を結んでいるものをいいます。

完全二部グラフというのは二部グラフとして考えられうる辺を

重複した辺を持たずに全て結んだ二部グラフのことを言います。

また、完全グラフは、グラフとして全ての頂点に対して

全ての頂点の組み合わせに対して、1つずつ辺を結んで

できるグラフのことです。

このとき、以下の定理が成り立ちます。

定理

もし、完全グラフ $K_n$ がある部分完全二部グラフ

$H_1,\cdots ,H_m$ によって分割したとき、

$m\ge n-1$ を満たす。

部分グラフ $H_i$ とは$K_n$ の頂点の部分集合を頂点集合とし、

$K_n$ の辺集合の部分集合を辺とするグラフのことを言います。

$H_i$ の二部グラフとしての分割 $A\sqcup B$ は適当に

決めるとします。

ここで分割とは、$K_n$ の辺を $H_1,\cdots ,H_m$ の辺で

全てひとつずつ覆うことを意味します。

なので、$H_1,\cdots, H_m$ の中で、頂点が重複していても構いません。

この証明として線形代数を用いる方法がありますが、

ここでは、多項式を用いた、Proofs from THE BOOK

に載っている、Tverberg の証明をします。

(証明)

$K_n$ が $H_1,\cdots, H_m$ のような完全二部グラフによって

分割できたとします。

ここで、$H_j$ の2つの頂点の集合を $L_j,R_j$ とします。

辺集合による分割に従って、以下の式を成立させることができます。

$$\sum_{i<j}x_ix_j=\sum_{k=1}^m(\sum_{a\in L_k}x_a\sum_{b\in R_k}x_b)$$

今、$m<n-1$ とすると、この等式が成り立たないことを示します。

ここで、$x_1+\cdots +x_n=0$ かつ $\sum_{a\in L_k}a_x=0$

を満たす$x_1,\cdots, x_n$ を考えます。

これは $m+1$ 個の線形な方程式だから、

ある $c_1,\cdots, c_n\in {\mathbb R}$ で、全て $0$ ではないような解が存在します。

そのような、$c_1,\cdots, c_n$ を取ってやると、$\sum_{i<j}c_ic_j=0$

が成り立つことがわかります。

しかし、

$$0=(c_1+\cdots+c_n)^2=\sum_{i=1}^nc_i^2+2\sum_{i<j}c_ic_j=\sum_{i=1}^nc_i^2>0$$

であることから、

矛盾します。

故に、$m\ge n-1$ であることがわかりました。

数学外書輪講I(第12回)

[場所1E501（月曜日5限）]

HPに行く

これは、7/8の外書輪講での授業の内容です。

シルベスターガレイの定理

今回は以下の定理を紹介してくれました。

シルベスターガレイの定理

平面上で同一直線上にない勝手な $n$ 点をとる。

そのとき、その $n$ 点のうちちょうど２点を含むような

平面上の直線が存在する。

(証明)
$\mathcal{P}$ を平面上の $n$ 点の集合とし、
$\mathcal{L}$ を $\mathcal{P}$ のうち少なくとも2点を通る
直線の集合とします。

$\{(P,\ell)\in \mathcal{P}\times \mathcal{L}|P\not\in \ell\}$ となる集合のうち、
$P$ から $\ell$ への距離が最小のものをとります。
それを、$(P_0,\ell_0)$ とします。

$P_0$ から $\ell_0$ への垂線の足を $Q$ とします。

ここで、$\ell_0$ が3点以上の点を含むとします。
そのとき、そのうち2点 $P_1, P_2$ が $Q$ を挟んで $\ell$ 上の同じ側
にあるとしてきます。それらのうち1つが $Q$ と一致しても構いません。

また、$P_1$ が $Q$ と $P_2$ の間にあると仮定しましょう。
このとき、$P_2$ と $P$ を結んだ直線を $\ell_1$ とおくと、
$P_1$ と $\ell_1$ との距離は、$P$ と $\ell_0$ との距離より短くなっています。

れは、$P$ と $\ell_0$ の距離が最小ということに反します。
故に、$\ell_0$ には2点以上の点を含まないことになります。

よって、シルベスターガレイの定理が導けました。
これによって、平面上の2 点には、
ちょうど2点を通る直線が存在することが示されました。

このことは平面であるから成り立ちますが、
他の空間では反例もあります。


また、次の定理も成り立ちます。
定理
平面上の$n(\ge 3)$ 点集合 $\mathcal{P}$ が一直線上に並んでいないとすると、
$\mathcal{P}$ の点を2点以上含む直線の集合 $\mathcal{L}$ は
$|\mathcal{L}|\ge n$ である。

証明
帰納法で示します。
もし、$n$ 点の場合が示されたとします。

$|\mathcal{P}|=n+1$ とします。
このとき、シルベスターガレイの
定理から、$\ell_0\in \mathcal{L}$ が存在して、$\ell_0$ は
$\mathcal{P}$ の点をちょうど2点含みます。

そのうち1点を$Q$ として、$\mathcal{P}'=\mathcal{P}\setminus \{Q\}$
とし、$\mathcal{L}'$ を $\mathcal{P}'$ のうち2点以上含む
直線の全体とします。もし、$\mathcal{P}'$ が1直線上に
乗らないとすると、帰納法の仮定から、$|\mathcal{L}'|\ge n$ であり、
$\ell_0\not\in \mathcal{L}'$ であり、
$\mathcal{L}'\cup\{\ell_0\}\subset \mathcal{L}$ であるから、$|\mathcal{L}|\ge n+1$
を満たします。
もし $\mathcal{P}$ が一直線上に乗るとすると、それらを$P_1,P_2,\cdots, P_n$ とすると、
$\overline{QP_i}\in \mathcal{L}$ であり、互いに異なるので、
$|\mathcal{L}|=n+1$ となり、この場合もやはり成り立ちます。

また、次の定理を示してもらいました。

定理
$X$ を3点以上を持つ点の集合とします。
そのとき、$A_1,\cdots A_m$ を$X$ の真部分集合とします。
もし、$X$ の各2点が、どこかの集合 $A_i$ のみに
存在するとしたら、$m\ge n$ である。

$X$ 自身を取ってしまうと、その中に、任意の
2点が含まれますから $m=1$ でOKになってしまいます。
なので、真部分集合ということになります。

また、この設定の一例として、平面上の有限点集合 $P$ に対して、
2点以上含む直線の集合 $\mathcal{L}$
があります。

(証明)
そのような$A_1,\cdots, A_m$ が存在したとして、
$x\in X$ に対して $x$ を含む $A_i$ の数を $r_x$ とします。
そのとき、仮定から、$2\le r_x<m$ です。
今、$x\in A_i=\{y_1,\cdots, y_k\}$ であるとすると、
$\{x,y_j\}$を含む集合は、$A_1,\cdots, A_m$ の中から、ちょうど
$A_{p_j}$ だけしかないので、それを並べることで、
$A_{p_1},\cdots, A_{p_m}$ は重複はなく条件から $r_x$ 以下しかありません。
よって、$m\le r_x$ です。つまり、$|A_i|\le r_x$ となります。

$m<n$ と仮定しましょう。このとき、$m|A_i|<nr_x$ であり、
$x\in A_i$ に対して、$m(n-|A_i|)>n(m-r_x)$ を満たします。
よって、
$\{(x,A_i)\in X\times \{A_1,\cdots, A_m\}|x\not\in A_i\}$ という集合を考えると、

$$1=\sum_{x\in X}\frac{1}{n}=\sum_{x\in X}\sum_{A_i:x\not\in A_i}\frac{1}{n(m-r_x)}>\sum_{A_i}\sum_{x\not\in A_i}\frac{1}{m(n-|A_i|)}$$
$$=\sum_{i=1}^m\frac{1}{m}\sum_{x\in X:x\not\in A_i}\frac{1}{n-|A_i|}=\sum_{i=1}^m\frac{1}{m}=1$$

となり矛盾します。
よって、$m\ge n$ であることがわかります。


(別証明)
この証明の別証明を隣接行列を用いて行うこともできます。
$X=\{x_1,\cdots, x_n\}$ とし、$A_1,\cdots A_m$ がそのような部分集合とします。

$B=(b_{ij})$ を
$$b_{ij}=\begin{cases}1&x_i\in A_j\\0&x_i\not\in A_j\end{cases}$$
とすると、
$$BB^t=\begin{pmatrix}r_{x_1}&1&\cdots&\cdots&1\\1&r_{x_2}&1&\cdots &1\\\cdots&\cdots&\cdots&\cdots&\cdots\\1&\cdots&\cdots &1&r_{x_n}\end{pmatrix}$$
$$=\begin{pmatrix}r_{x_1}-1&0&\cdots&\cdots&0\\0&r_{x_2}-1&0&\cdots &0\\\cdots&\cdots&\cdots&\cdots&\cdots\\0&\cdots&\cdots &0&r_{x_n}-1\end{pmatrix} +J$$
となります。ここで、$J$ は全ての成分が 1 である行列です。
この行列 $BB^t$ は正則行列です。
なぜなら、$\forall x\in A_i$ となる $i$ が唯1つしかないとすると、
そのような $A_i$ は $X$ と一致しないといけません。
よって、$r_{x_{i}}>2$ であることがわかります。
つまり、対角行列 $D$ と $J$ を用いて $BB^t=D+J$ と書いたときに、
$D$ の対角成分が全ての正の数ということになります。
この授業の第10回で書いたことと同じ議論をすることで、
$BB^t$ は正定値行列ということになります。
特に、$BB^t$ は正則行列となります。
故に、$\text{rank}(BB^t)=n$ となり、
$n=\text{rank}(BB^t)\le \text{rank}(B)\le \min\{n,m\}\le m$
であるから、$n\le m$ が成り立ちます。

数学外書輪講I(第11回)

[場所1E501（月曜日5限）]

HPに行く

これは7/1の外書輪講で行われた授業に基づいています。

オイラーの公式

ここでは多面体のオイラーの公式についての話をしてもらいました。

まず、グラフを考えます。

グラフとは、有限この頂点とその頂点を結ぶ有限この辺からなる幾何的対象物です。

各辺は必ずある頂点同士を結んでいないといけません。

規則としてはこれだけです。

このとき、オイラーは、以下の定理を発見しました。

オイラーの公式

もし、グラフが、平面上に、辺同士が互いに交わらないように描くことが

できたとすると、その頂点の数を $n$ 、辺の数を $e$、

グラフで分割された平面の領域の数を $f$ とするとき、

$$n-e+f=2$$

の関係式が成り立つ。

ここで、グラフで分割された領域として、無限のかなたに伸びる部分も

領域として数えます。

このオイラーの公式を用いると、ピックの公式を導けるので

それを証明してもらいました。

平面 ${\mathbb R}^2$ の上に等間隔に格子点 ${\mathbb Z}^2$ を用意し、

その点を適当に結んで下のような多角形

を作ったとします。下の多角形は一例です。

ピックの公式とは、以下の公式です。

ピックの公式

格子点を結んでできる多角形の面積は、

$$n_{\text{int}}+\frac{1}{2}n_{\text{bd}}-1$$

のように計算できます。

ここで、$n_{\text{int}}$ は、多角形の内部にある点の個数であり、

$n_{\text{bd}}$ は、多角形の辺上にある点の個数とします。

(オイラーの公式を用いたピックの公式の証明)

まず、内部に格子点を持たない三角形の面積が $1/2$ であることを示します。

そのような三角形を基本三角形と呼ぶことにします。

ある基本三角形の頂点を${\bf p}_0,{\bf p}_1,{\bf p}_2$としておきます。

また、平行移動をして、${\bf p}_0={\bf 0}$ としておきます。

このとき、${\bf 0},{\bf p}_1,{\bf p}_2,{\bf p}_1+{\bf p}_2$ 

は内部に格子点を持たない平行四辺形です。

この平行四辺形を平行移動をして、平面全体を覆ったときに、

それらの平行移動をしてできる平行四辺形はみな、内部に頂点を

含みません。

頂点全て ${\mathbb Z}^2$ はどこかの平行四辺形の頂点になっています。

つまり、

$(a,b)^t\in {\mathbb Z}^2$ は必ず、${\bf p}_1$ と${\bf p}_2$ の

整数を係数にもつ1次結合によって、$(a,b)^t=n{\bf p}_1+m{\bf p}_2$ のように

書き表すことができます。

よって、$(1,0)^t=n{\bf p}_1+m{\bf p}_2$ と $(0,1)^t=r{\bf p}_1+s{\bf p}_2$

としたとき、

$$\begin{pmatrix}1&0\\0&1\end{pmatrix}=({\bf p}_1,{\bf p}_2)\begin{pmatrix}n&r\\m&s\end{pmatrix}$$

となります。

この行列式をとることで、$1=\det({\bf p}_1,{\bf p}_2)\cdot \det\begin{pmatrix}n&r\\m&s\end{pmatrix}$

となり、各行列の行列式は整数を成分に持つから、特に、$\det({\bf p}_1,{\bf p}_2)=\pm1$

でなければなりません。この左辺の絶対値はこの平行四辺形の面積

を表すから、${\bf 0},{\bf p}_1,{\bf p}_2$ からなる基本三角形の

面積は $1/2$ であることがわかりました。

よって、任意の基本三角形の面積は $1/2$ であることがわかりました。

次に、任意の格子点を頂点とする多角形は、

多角形の $n_{\text{int}}$ 個の内部の点と $n_{\text{bd}}$ 個の

境界上の点を頂点を用いた、いくつかの三角形によって三角形分割をすることが

できることを用います。

ここで分割された三角形は、十分に辺を加えることによって、

基本三角形にしても良いことがわかります。

そうすると、平面がいくつかの基本三角形を面とするグラフによって

分割されることがわかります。$n,e,f$ を上で定義したグラフの

頂点、辺、領域の数とします。

このとき、三角形の個数は $f-1$ 個で、面積を $A$ とすると、

上で示したことから、

$$A=\frac{1}{2}(f-1)$$

となります。

辺の中で、多角形の内部にあるものの個数を $e_{\text{int}}$ とし、

境界にあるものの個数を $e_{\text{bd}}$ とします。

また、三角形には3辺あるので、含まれる基本三角形全ての辺の

数を数えると、$3(f-1)=2e_{\text{int}}+e_{\text{bd}}$

となります。

また、辺の数の総数が $e$ であるから、$e=e_{\text{int}}+e_{\text{bd}}$

が成り立ちます。

また、境界の頂点の個数は境界の辺の個数と一致するから、

$n_{\text{bd}}=e_{\text{bd}}$ が成り立ちます。

オイラーの公式にこの等式を代入することで、

$n_{\text{int}}-e_{\text{int}}+f=2$

が成り立ち、上の式にもこの等式を代入することで、

$3(f-1)=2e_{\text{int}}+n_{\text{bd}}$

となります。

この２つのしきから $e_{\text{int}}$ を消去することで、

$2n_{\text{int}}+n_{\text{bd}}=f+1$ 

が成り立ちます。

よって、

$$A=\frac{1}{2}(f-1)=\frac{1}{2}(2n_{\text{int}}+n_{\text{bd}}-2)=n_{\text{int}}+\frac{1}{2}n_{\text{bd}}-1$$

となり、ピックの公式を導けました。

数学外書輪講I(第10回)

[場所1E501（月曜日5限）]

HPに行く

これは6/24の外書輪講に行われた授業に基づいています。

ベルトランの仮説の後半

ここ(リンク)においてベルトランの仮説の前半について書きました。

まず、ベルトランの仮説とは次のような定理のことを言います。

定理

任意の正の整数 $n$ に対して、$n<p\le 2n$

となる素数 $p$ が存在する。

この定理を証明をするための発想として、
もし$n<p\le 2n$ となるような素数 $p$ が存在しないとすると、
二項係数 $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ の分子は、$n$ 以下の素数
しか現れないということになる。もしそのようなことが起これば
$n$ は十分に小さいことを証明できれば良い。

この定理の証明として、以下のようなステップで考えます。

Step 1

$n\le 511$ まででこの仮説が正しいことを証明する。

Step 2

$x\ge 2$ のときに、$\prod_{p\le x}p\le 4^{x-1}$ が成り立つことを示す。

ここで、$\prod_{p\le x}p$ は $x$ 以下の素数の全ての積

を表します。

Step 3

$\binom{2n}{n}$ を割り切る$2n$ 以下の素数 $p$ は、

$p>\sqrt{2n}$ を満たすなら、$p$ を割ることができる回数は

高々1回であり、$\frac{2}{3}n< p\le n$ を満たす素因数が現れない。

Step 4

$\binom{2n}{n}$ のある上からの評価をすること。

Step 5

定理の証明

前回の輪講までで、Step 2が終わりました。

Step 3の証明

ルジャンドルの定理から、

$\binom{2n}{n}$ を割り切る素数 $p$ の数はちょうど

$\sum_{k\ge 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)$

と計算できます。

ここで、$\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor< \frac{2n}{p^k}-2(\frac{n}{p^k}-1)=2$

ですから、上の和の各項は高々1です。

また、$p^k>2n$ となる $k$ に対しては、各項は $0$ ですから、

$\sum_{k\ge 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)\le\max\{r|p^r\le 2n\}$

となります。

特に、$p>\sqrt{2n}$ となるような素数 $p$ は $\max\{r|p^r\le 2n\}=1$ であるから、

$\sum_{k\ge 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)\le 1$ となります。

つまり、そのような素数 $p$ が $\binom{2n}{n}$ の約数になるとすると、

その $p$ のべきは高々1ということになります。

さらに、エルデシュによりますと、$\frac{2}{3}n< p\le n$ となる素因数は、

$\binom{2n}{n}$ には決して現れません。

というのも、もしそのような素数が存在したら、

$n!$ の中にはそのような素因数はただ1つ現れ、

$3p\le 2n$ ですから $(2n)!$ の中には、ただ2つだけ現れます。

よって、$\binom{2n}{n}$ ではちょうど割り切れてしまって素因数として

現れないからです。

Step 4の証明

Step 3を使うと、

$$\frac{4^n}{2n}\le \binom{2n}{n}\le \prod_{p\le \sqrt{2n}}(2n)\cdot \prod_{\sqrt{2n}<p\le \frac{2}{3}n}p\cdot \prod_{n<p\le 2n}p$$

が成り立ちます。

ここで、$n<p\le 2n$ となる素数の個数を

$P(n)$としますと、最後の項は、$(2n)^{P(n)}$ より大きいので、

$$4^n\le (2n)^{\sqrt{2n}}\cdot 4^{\frac{2}{3}n}\cdot (2n)^{P(n)+1}$$

を満たします。

よって、整理することで、

$$4^{\frac{1}{3}n}<(2n)^{\sqrt{2n}+P(n)+1}$$

を満たします。

Step 5の証明

この不等式の $\log_2$ を取ると、

$$\frac{2n}{3}<(\sqrt{2n}+1+P(n))\log_2(2n)\Leftrightarrow \frac{2n}{\log_2(2n)}-\sqrt{2n}-1<P(n)$$

を満たします。

よって $\log_2(2n)$ が $n$が大きくなると、$\sqrt{2n}$ に比べて圧倒的に

大きくなることを示せば良いのです。

つまり、$\sqrt{2n}-1>3\log_2(2n)$ であることがわかれば、

$$P(n)>\frac{2n-1}{3\log_2(2n)}-(\sqrt{2n}+1)=(\sqrt{2n}+1)\left(\frac{\sqrt{2n}-1}{3\log_2(2n)}-1\right)$$

となるので、$P(n)$ は正の数となります．

よって、$f(x)=\sqrt{x}-1-3\log_2x$ とおくと、

$$f'(x)=\frac{1}{2\sqrt{x}}-\frac{3}{(\log 2) x}=\frac{(\log 2)\sqrt{x}-6}{(2\log 2)x}$$

を満たします．

よって、$x>\left(\frac{6}{\log 2}\right)^2$ の場合に、$f(x)$ は単調増加になり、

$x\ge 2^{10}$ であれば、$f(x)$ は単調増加であり、

$f(2^{10})=2^5-1-3\cdot 10=1>0$ であるから、

$f(x)$ は $f(x)>0$ となります。

よって、$n\ge 512$ であるときに、$\sqrt{2n}-1-3\log_2(2n)>0$ が成り立つこと

つまり、$P(n)>0$ がわかります．

よって、$n\ge 512$ のときに、$n<p\le 2n$ を満たす素数 $p$ が存在することが

わかりました。

同じサイズを持つ共通集合

マトウセクのMiniature 4をやりました。

この話も極値集合論です。

次の定理を示してもらいました。

定理

$C_1,\cdots, C_m$ を互いに異なる空ではない $n$ 点集合の部分集合とする。

この時、$i\neq j$ なら $C_i\cap C_j$ が同じサイズの集合であるとき、

$n\ge m$ を満たす。

証明

まずは、条件から、$i\neq j$ のとき、$|C_i\cap C_j|=t$ であるとします。

ある $C_i$ のサイズが $t$ であるとします。

簡単のため、$i=1$ としておきます。

このとき、$j\neq 1$ のとき、$C_1\cap C_j\subset C_1$ であり、

これらはサイズが同じ集合であるから、

$C_1\cap C_j=C_1$ となります。

つまり、$C_1\subset C_j$ であることがわかります。

よって、$D_j:=C_j\setminus C_1$ と定義すると、

$D_j$ は重複のない相異なる $n$ 点集合の

部分集合となります。

つまり、$|D_1\sqcup D_2\sqcup\cdots \sqcup D_m|\le n$ ですから、

そのような $m$ はせいぜい $n$ 以下で抑えられます。

つまり、$m\le n$ となります。

次に、任意の $C_i$ に対して、$|C_i|>t$ であるとします。

このとき、

$m\times n$ 行列 $A=(a_{ij})$ を

$$a_{ij}=\begin{cases}1&j\in C_i\\0&otherwise.\end{cases}$$

と定義すると、

$B=AA^T$ はの $(i,i)$ 成分はちょうど $|C_{i}|=d_i$ であり、

$(i,j)$ 成分は $C_i\cap C_j|=t$ であることがわかります。

つまり、この行列は、

$$B=\begin{pmatrix}d_1&t&\cdots&\cdots&t\\t&d_2&t&\cdots&t\\\cdots&\cdots&\cdots&\cdots&\cdots\\t&\cdots&\cdots&t&d_m \end{pmatrix}$$

となります。

よって、この行列は正則になります。

この行列が正定値であることを示せれば良いです。

$B=tJ+\begin{pmatrix}d_1-t&0&\cdots&\cdots&0\\0&d_2-t&0&\cdots&0\\\cdots&\cdots&\cdots&\cdots&\cdots\\0&\cdots&\cdots&0&d_m-t \end{pmatrix}$ とおいておきます。ここで、$J$ は全ての成分が $1$ の行列です。

最後の対角行列を $D$ とおきます。

${\bf v}\in {\mathbb R}^m$ を ${\bf v}=(v_1,v_2\cdots, v_m)^t$ とします。

${\bf v}^tB{\bf v}={\bf v}^ttJ{\bf v}+{\bf v}^tD{\bf v}$ であり、

${\bf v}^tD{\bf v}=\sum_{i=1}^m(d_i-t)v_i^2>0$ です。

また、${\bf v}^ttJ{\bf v}=t(v_1+v_2+\cdots+v_m)^2\ge 0$ となります。

よって、${\bf v}^tB{\bf v}>0$ であることがわかったので、

$B$ は正定値行列であることがわかりました。

特に$B$は正則であり、$\text{rank}(B)=m$ となります。

一方、$B=AA^t$ であり、$\text{rank}(A)\le \min\{n,m\}$ ですから、

$m=\text{rank}(B)\le \text{rank}(A)\le \min\{n,m\}\le n$ ですから、

この場合も、$m\le n$ であることが言えます．

数学外書輪講I(第9回)

[場所1E501（月曜日5限）]

HPに行く

これは6月17日の分の内容です。

ユークリッド空間の中の n 点の集合

今回は、ユークリッド空間 ${\mathbb R}^n$ の中の $n+1$ 点は

その間の距離をどのように決めたときに、その点達

は実際存在しうるか？

という問題です。

Miniature 6 では ${\mathbb R}^2$ の中の4点が存在するか？

という問題でしたから、今回の話とは独立です

問題意識は似ていますが、本質的に違った証明になります。

$n+1$ 点は重複があっても良いですが、そのとき、

もし${\mathbb R}^n$ 上に乗っているとすると、すでに${\mathbb R}^n$

のなかの $n-1$ 次元アフィン空間 ${\mathbb R}^{n-1}$ と同じもの

に乗っていなければならず、次元が落ちた状況で考えることになります。

平面では、三角不等式を満たす3点は必ず3点として存在します。

三角不等式は必要条件でもあるので、三角不等式は平面上に3点が存在するための

必要十分条件ということになります。

今回は一般にどうか？ということです。つまり高次元化されています。

${\mathbb R}^n$ の中の $n+1$ 点の場合に、そのうちの任意の３点が三角不等式を満たす

ということも必要な条件なのですが、実はそれだけではないというのが

この問題の主題です。

定理は、実際以下のようになります。

定理

$m_{ij}$ を$i,j=0,1,\cdots, n$ とし、非負実数とし、$m_{ij}=m_{ji}$

とし、$m_{ii}=0$ とします。

このとき、ある${\bf p}_0,{\bf p}_1\cdots {\bf p}_n\in {\mathbb R}^{n}$ が存在して、

$m_{ij}=||{\bf p}_i-{\bf p}_j||$ であるための必要十分条件は、

$g_{ij}=\frac{1}{2}(m_{0i}^2+m_{0j}-m_{ij}^2)$ として $n\times n$ 行列 $G=(g_{ij})$ 

を構成したときに、$G$ が半正定値であることと同値である。

行列は半正定値であるとは、その固有値が全て0以上の実数で

あることです。

この定理は、$n+1$ 点の任意の３点に対して三角不等式を満たす

という条件より本質的に強い条件になっています。

$G=(g_{ij})$ が半正定値

であることは、$G$ が対称行列であることもあり、

$G=XX^t$ となる正方実行列 $X$ が存在することと同値です。

数学外書輪講I(第8回)

[場所1E501（月曜日5限）]

HPに行く

これは6月10日の分の内容です。

誤り訂正符号についてと平面上に奇数の距離をもつ4点集合についてやりました。

誤り訂正符号

とは、離れた距離の場所に電子信号を送るときに含まれるノイズを

いかに小さくすることができるか？という話です。

たとえば、0と1の列からなるような電子信号が送られたとき、

ある桁の数値が途中で何かの衝撃があって0を1として送られたとした時に、

受け取った側で何らかの操作をして、その間違い1を0に直すシステムです。

どうしてそのようなことができるのでしょうか？

例えば、マトウセクの本ではabcdの列を、aaabbbcccddd

に送るとしたら、

110000101111のように送られてきたものを直す時、(おそらく間違いは

少ないだろうから)3つずつの桁の中で多い方が正解と判断し、

111000111111

を送りたかったものとして直します。

このとき、1011というデータが送られたことになります。

このように、多少の間違いがあってもそれを正しいと思われる
ワードに訂正するシステムを誤り訂正符号といいます。

実は、このような誤りを訂正符号のためには、
4 bitの情報をわざわざ12 bitにして送る必要はありません。
もっと少ないbit数で十分です。

実は7 bitにしておけば、誤り訂正符号を作ることができます。

情報abcdに対して、たった3digit の情報efgを付け加えることて

abcdefg として送ることで謝り訂正符号を作ることができます。

まず、このような情報の列のことをワードといいます。

アルファベットの集合を$S$ と書けば、$n$ 桁のワードの集合は $S$ の $n$ この

ペア(直積)の集合であり $S^n$ とかくことができます。

今、$S$ として2元体 ${\mathbb F}_2$ (0,1の2つからなる体)とします。

${\mathbb F}_2^7$ につぎのように誤り訂正符号を構成します。

e=a+b+c

f=a+b+d

g=a+c+d

としますと、例えば1011というワードは、

1011001

というワードとして送られます。

このように最初の4つのワードを任意に与えれば自動的にのこりの3つのワードが
決まるので、

0,1の7個の任意の列は全部で $2^7=128$個ありますが、その中でたった7桁のワードとして
正しく送られなければならないものは次のたった16個の列のみです

$$C=\{0000000,0001011,0010101,0011110,0100110,0101101,0110011,0111000,1000111,1001100,1010010,1011001,1100001,1101010,1110100,1111111\}$$

これらをコードと呼ぶことにします。

ポイントは、どんなコードを持ってきても、少なくとも3つのbitを変えないと他のコードにならないということです。

ワード $w\in {\mathbb F}_2^7$ に対して $w$ のあるbit を1つ変えることで得られる他のワード $w’$
が得られたとします。このとき、$w$ と $w’$ の間に橋を掛けます。

このようにして ${\mathbb F}_2^7$ のすべてのワードに対して橋をかけます。

1つのグラフだと考えることもできます。

そうすると、あるコード $a$ のうちちょうど3つのbitを変えて他のコード $b$ に

なったとします。そうすると、$a$ と $b$ の間に2つのワード $x,y$ を通って

橋が $a, x,y,b$ のように橋が結ばれることになります。

もし、情報を送ったとき、$x$ として送られてしまった場合、
それを $a$ として直し、$y$ として送られてしまった場合、$b$ として直すことで一意的に近くのコードを直すことができます。例えば、$x$ に対してほかの直し方があるとすると、

$a,x,c$ のようにコード $a,c$ が橋でつながることになり、

3つ以上でdigit を変えないと他のコードにならないということに矛盾します。

よって、ワードを直せるとしたら一意的にコードを選ぶことができます。

注意しなければならないこととしてこのようにして直した

コードが直したかったものに本当になっているかどうかは保証はありません。

もしかして、1つ直すだけではなくて、4つ直さないとならないものかもしれません。

ただ、そのようなものはそんなに多くはないだろう

と考えるのです。

距離空間を用いて

このことを距離空間の言葉でいい直すことができます。

ワード全体に、次のような距離を入れるのが自然だと思うでしょう。

$w_1,w_2$ をワード $S^n$ の要素とします。
$d(w_1,w_2)$ をその桁のうち、異なる桁の個数とします。

例えば、

$d(0001011,0010101)=4$ となります。

そうすると、$d$ は距離の公理を満たしワード全体は距離空間になります。

距離空間とは、以下の性質を満たす関数

 $d:X\times X\to {\mathbb R}_{\ge 0}$ を持つ集合 $X$ のことです。

任意の $\forall x,y,z\in X$ に対して、

(1) $d(x,y)=0\Leftrightarrow x=y$

(2) $d(x,y)=d(y,x)$

(3) $d(x,y)+d(y,z)\ge d(x,z)$

を満たす。
この関数のことを距離関数と言います。

先ほどの $d$ もこの性質を満たすことをチェックしてください。

コード$C\subset S^n$ が $t$ 個の誤りを直すというのは、

$\forall u\in S^n$ に対して、$d(u,v)\le t$ となる $v\in C$ となる元が高々1つ存在する
ことを言います。

また、$d(C)=\min\{d(u,v)|u,v\in C,u\neq v\}$ とします。

このとき、以下が成り立ちます。

補題

$C\subset S^n$ が $t$ 個の誤りを直すことと、$d(C)\ge 2t+1$ ということは

同値である。

この証明は簡単なので証明してみてください。
こちら(リンク)にもその証明を載せています。

先ほどの例に戻ります。

このとき、$d(C)=3$ であることから、

コード $C$ は$t\le 1$ であることがわかります。

つまり、このコードは高々1個誤りを直すことができるということになります。

コードの生成

また、どのようにしてコードを作っていたかというと、

ワードの集合 ${\mathbb F}_2^n$ は、ベクトル空間を成しており、

情報 $v=abcd$ はベクトル $(a,b,c,d)$ とみなすことができます。

それをコード $w$ にするには、

生成行列 $G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{pmatrix}=(I_4|A)$ を用いて、

$w=G^t\cdot v$ のように書くことができます。

送りたいワードからコードを作るのに線型写像を用いています。

よって、コード全体の集合は、ベクトル空間をなします。

つまり、$L_{G^t}$ を $G^t$ による左からの積とします。

このとき、$C=\text{Im}(L_{G^t})$ となります。

線形写像の像の集合はベクトル空間であるので

特に $C$ にベクトル空間になります。

よって、$w\in {\mathbb F}_2^7$ が $C$ の元であるか

判定するのは、ある連立方程式 $P{\bf x}={\bf 0}$ の解であることがわかります。

この $P$ のことをパリティチェック行列と言います。

パリティチェック行列は、具体的には、$P=(-A^t |I_3)$ とすることで得られます。

なぜなら、$P\cdot G^t= (-A^t|I_3)\begin{pmatrix}I_3\\A^t\end{pmatrix}=-A^t+A^t=O$

なり、任意の $G^t$ の像の元 $w$ は、$P{\bf w}={\bf 0}$ を満たします。

平面上に奇数の距離を持つ4点は存在しない

これもマトウセクの本の中の話です。

表題の通り、${\mathbb R}^2$ の中の4点で、そのそれぞれの距離

が奇数となるような点が取れないという定理を証明します。

こちら(リンク)にも記事を書きました。
ちなみに、3点であれば、そのような3点はすぐ作れます。
ただし、三角不等式を満たさなければなりませんが。

そのような4点が取れたとして、矛盾を導きます。

1つの点を固定して、その点を原点として、残りの平面上の

${\bf a}.{\bf b},{\bf c}$ を用いて考えます。

そのとき、内積 $\langle {\bf a},{\bf b}\rangle, \langle {\bf b},{\bf c}\rangle, \langle {\bf b},{\bf c}\rangle$ の2倍も整数であり、$1\bmod 8$ となることが重要です。

例えば、$2\langle {\bf a},{\bf b}\rangle=||{\bf a}||^2+||{\bf b}||^2-||{\bf a}-{\bf b}||^2$

となるからです。

${\bf a},{\bf b},{\bf c}$ のグラム行列の2倍が正則になることがわかり、

一方、グラム行列の作り方から正則にならず、矛盾が導かれます。