ラスクのMathematics for Everyone!

数学が得意な人もそうでない人もちょっとだけ楽しめるようなブログです。

離散的な世界に登場!差分系テイラー展開!(1)

みなさんご無沙汰しております。ラスクです。

連日うだるような暑さですが、どうぞ体調などにはお気をつけください。

さて、私事ですが先日大学の長期休暇に入りました。
もちろん休みといえども自分の勉強や研究の手を抜くわけにはいきませんが、普段よりは時間にゆとりができるので、このブログの更新ペースも一時的に上げていきたいと思っております。暑さに負けないよう尽力いたしますので、どうかお付き合いのほどよろしくお願いいたします!


では、本題に入りましょう。
今回のテーマは以前の記事で少し予告しました「差分系テイラー展開」です!!
予告してから、ずいぶんと時間がたってしまい申し訳ありません。

以前の記事では
べき乗和の公式を差分という方法を用いて考察する
という事をやりました。
その際、べき乗和の代わりに下降階乗冪の和というのを考えると以下のようなとてもきれいな公式が成り立つのでした。

\begin{align}
\sum_{k=1}^{n-1} k^{\underline{m}}=\frac{1}{m+1}n^{\underline{m+1}}\ (m\ge1)
\end{align}

詳しく知りたい方は是非、こちらをご覧ください。

mathforeveryone.hatenablog.com

そして今回は、「差分」という操作を軸にしてもう少し異なる内容、具体的には数値計算で用いられる「ニュートンの補間法」というものをご紹介します。

少し長くなりそうでしたので、全2回に分けてご説明しようと思います。
なので本記事では、どのような問題を考えるのかという導入と準備のための定義をいくつかしていきます。
そして次回の記事でニュートンの補間法の内容やその例をご紹介したいと思っております。

あまり前置きが長くなってもいけませんので、さっそく始めていきましょう。

補間法

今回考えるのは以下のような問題です。


与えられたn+1個の点
\begin{align}
(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n) \end{align}
(ただしx_i,y_i\in\mathbb{R}かつi\neq jならばx_i\neq x_j)
をすべて通るようなn次以下の多項式関数y=f(x)を求める。

つまり、xy平面上にそれぞれx座標が異なるn+1個の点が与えられていて、それらをすべて通る関数を求めようというわけです。これの意味について解説しましょう。

まず具体的な形がよくわからない関数が一つあったとします。このとき、まずその関数にn+1個の値を入れてみてそのデータを集めます。これが上でいうn+1個の点に当たるものです。科学的にはこれは実験をしてデータを集めていることに当たります。そしてそのn+1個のデータに見合うような多項式を見つけ、それによって元の関数を近似しようというわけです。
この操作は得られたn+1個の飛び飛びなデータから関数全体の形を近似しよう、つまり”間を埋めよう”としていることに他ならないので数値計算の分野では「補間法」と呼ばれ、得られた多項式のことを補間多項式といいます*1



例を見てみましょう。


例1(n=1の場合について)
n=1のときは与えられる点は2点(x_0,y_0),(x_1,y_1)ですから、これらを通る多項式関数としては1次関数
\begin{align}
y=\frac{y_1-y_0}{x_1-x_0}(x-x_0)+y_0
\end{align}
が取れます。正確に言えばy_0=y_1のときは定数関数(0次式)になってしまいますが、どちらにせよ上式の形で表現できています。


例2(n=2の場合について)
次にn=2のときは与えられている点は3点(x_0,y_0),(x_1,y_1),(x_2,y_2)ですから2次(以下)の多項式ですべての点を通るものが存在します。その関数を
\begin{align}
y=a+bx+cx^2\ (a,b,c\in\mathbb{R})
\end{align}
とおいて各係数a,b,cを求めてみましょう。この多項式が上の3点を通るという条件を素直に書き下せば
\begin{align}
\left\{ \begin{array}{l} y_0=a+bx_0+cx_0^2 \\ y_1=a+bx_1+cx_1^2 \\y_2=a+bx_2+cx_2^2 \end{array}\right. \tag{1}
\end{align}
となり、これを行列を使って書けば、
\begin{align}
\left(
\begin{array}{ccc}
1 & x_0 & x_0^2 \\
1 & x_1 & x_1^2 \\
1 & x_2 & x_2^2
\end{array}
\right)\left(
\begin{array}{ccc}
a\\
b\\
c
\end{array}
\right)
=\left(\begin{array}{ccc}
y_0 \\ y_1 \\ y_2
\end{array}
\right)
\end{align}
となります。このとき左辺の行列はヴァンデルモンド行列と呼ばれていて、その行列式は以下のような形になることが知られています。
\begin{align}
\mathrm{det}\left(
\begin{array}{ccc}
1 & x_0 & x_0^2 \\
1 & x_1 & x_1^2 \\
1 & x_2 & x_2^2
\end{array}
\right)=(x_1-x_0)(x_2-x_0)(x_2-x_1)
\end{align}
今、x_0,x_1,x_2はそれぞれ異なることから上の行列式0ではありません。
したがってヴァンデルモンド行列は逆行列を持ち連立方程式(1)はただ一つの解を持つことがわかります。
このようにしてa.b.cが求まり、3点を通る2次(以下の)多項式を求めることが出来るというわけです。



一般のnの場合でもそれぞれの式をn次関数の式に代入して連立方程式を解いて…という風に計算すれば原理的には、求めたい関数を得ることが出来ます。しかしこの方法には二つ問題点があります。
一つ目は皆さん、お気づきかもしれませんがこの「連立方程式を解く」という操作がnが大きくなるにつれてどんどん大変になっていきます*2。この方法を解決する手段として「ラグランジュの補間法」というものが考えられますが、これについてはまた次の機会にご紹介することにします。
二つ目はもっと実用的な問題点です。上のような素朴なやり方(もしくはラグランジュの補完法)でn+1個のデータを用いて補間多項式を計算したあと、もう一つ別のデータを追加し補間多項式を修正しようと思うと、計算を最初からやり直さなければならないのです。もちろん今のようにコンピュータが発展していればそこまで大きな問題ではないのかもしれませんが、もっと前の時代、それこそニュートンライプニッツたちが活躍していた時代であればこれは大問題です。
そこでそれをうまく解決したのがまさに「ニュートンの補間法」であります。

そこで以下では、それを扱うための準備をしていきます。


差分と差分商

差分

ニュートンの補間法」を説明するために、前の記事で定義した差分を一般化しておきましょう。
引き続き関数fからn+1個の点(データ)
\begin{align}
(x_0,f(x_0)),(x_1,f(x_1)),\ldots,(x_n,f(x_n))
\end{align}
が与えられているとして、差分を次のように定義します。


定義(差分)
x_iにおける(前進)差分\Delta f (x_i)
\begin{align}
\Delta f (x_i):=f(x_{i+1})-f(x_i)\ (i=0,1,\ldots,n-1)
\end{align}
と定義する。また高階の差分\Delta^k f(x_i)\ (k\ge2)
\begin{align}
\Delta^k f(x_i):=\Delta(\Delta^{k-{}1} f(x_i))\ (i=0,1,\ldots,n-k)
\end{align}
再帰的に定義する。ただし\Deltaf(x_i)に線形に作用するとする。

何を言っているかわかりにくいかもしれないので、少し説明を加えます。
まず、前半で言っていることはよいでしょう。ある点における値とその次の点での値の差をとっているだけです。
そして後半についてですが、再帰的に定義すると書いた通り、これは小さいkから順番に高階の差分を定めていくことになります。


実際にやってみましょう。

まず、二階の差分について定義により
\begin{align}
\Delta^2 f(x_i)&=\Delta(\Delta f(x_i)) \\
&=\Delta(f(x_{i+1})-f(x_i)) \\
&=\Delta f(x_{i+1})-\Delta f(x_i)\\
&=(f(x_{i+2})-f(x_{i+1}))-(f(x_{i+1})-f(x_i))\\
&=f(x_{i+2})-2f(x_{i+1})+f(x_i)
\end{align}
となります。途中で\Deltaを二つに分けたところで\Deltaの線形性を使っています*3
三階差分についても同様の計算をすることで
\begin{align}
\Delta^3 f(x_i)=f(x_{i+3})-3f(x_{i+2})+3f(x_{i+1})-f(x_i)
\end{align}
をえます。これは演習問題とします!!

このように順番に高階の差分を定めていくわけです。
ここで、この操作を図にまとめると次のようになります。

\begin{align}
\begin{array}{ccccccccc}
f(x_0)&\Delta f(x_0)&\Delta^2 f(x_0)&\Delta^3 f(x_0)\\
\\
f(x_0)&{}&{}&{}\\
{}&f(x_1)-f(x_0)&{}&{}\\
f(x_1)&{}&f(x_2)-2f(x_1)+f(x_0)&{}\\
{}&f(x_2)-f(x_1)&{}&f(x_3)-3(x_2)+3f(x_1)-f(x_0)\\
f(x_2)&{}&f(x_3)-2f(x_2)+f(x_1)&\\
{}&f(x_3)-f(x_2)&{}&\\
f(x_3)&{}&&{}\\
\end{array}
\end{align}


こうしてみると何をしているかが非常にわかりやすいですね。ただ左の方から順番に上下隣同士の差をとって表を埋めていっているだけです。

では次に差分商を定義しましょう!

差分商


定義(差分商)
まずx_i\ (i=0,\ldots,n)における0階の差分商を単に
\begin{align}
f[x_i]:=f(x_i)
\end{align}
とする。次にx_i,x_{i+1}\ (i=0,\ldots,n-1)における1階の差分商を
\begin{align}
f[x_i,x_{i+1}]:=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}
\end{align}
とする。さらに一般にx_i,x_{i+1},\ldots,x_{i+k}\ (i=0,\ldots,n-k)におけるk階の差分商を
\begin{align}
f[x_i,\ldots,x_{i+k}]:=\frac{f[x_{i+1},\ldots,x_{i+k}]-f[x_i,\ldots,x_{i+k-{}1}]}{x_{i+k}-x_i}
\end{align}
再帰的に定義する。

はい、こんな感じです。定義の仕方としては差分と同じ再帰的な定義をしているので詳しい説明は省きますが、要はこれも小さいkから順番に高階の差分商が定義されていく仕組みになっています。
式の形を見てお分かりの通り、これは連続的な世界における微分を意識したものです。ただ、今は離散的な世界(というか離散的な値しかわかっていない状態)なので、x座標の変化率を0に飛ばすという極限操作が取れず、分母にはギャップが残ったままになっています。

差分の時と同様、上の再帰的な定義を図に書き表してみると次のようになります。

\begin{align}
\begin{array}{ccccccccccc}
f[x_0]&f[x_0,x_{1}]&f[x_0,x_{1},x_{2}]&f[x_0,x_{1},x_{2},x_{3}]\\
\\
f[x_0]&{}&{}&{}\\
{}&\frac{f[x_1]-f[x_0]}{x_1-x_0}&{}&{}\\
f[x_1]&{}&\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}&\\
{}&\frac{f[x_2]-f[x_1]}{x_2-x_1}&{}&\frac{f[x_1,x_2,x_3]-f[x_0,x_1,x_2]}{x_3-x_0}\\
f[x_2]&{}&\frac{f[x_2,x_3]-f[x_1,x_2]}{x_3-x_1}&\\
{}&\frac{f[x_3]-f[x_2]}{x_3-x_2}&{}&\\
f[x_3]&{}&&{}\\
\end{array}
\end{align}

ここで、f[x_i]などはf(x_i)という値を使って直接書き下すこともできますが、それをすると表が大変なことになるのでやめました。

この図はのちのち重要になってくるので是非覚えておいてください。この図の特徴から先ほど言った「新いデータを付け加えた時に初めから計算をし直す必要がない」という事が従います。

最後に少し具体的な値で計算をしてみましょう。

例34点(-2,4),(0,1),(1,2),(3.6)が与えられているとしましょう。差分と差分商をそれぞれ計算すると

\begin{align}
\begin{array}{ccccccccc}
f(x_0)&\Delta f(x_0)&\Delta^2 f(x_0)&\Delta^3 f(x_0)\\
\\
4&{}&{}&{}\\
{}&1-4=-3&{}&{}\\
1&{}&1-(-3)=4&{}\\
{}&2-1=1&{}&3-4=-1\\
2&{}&4-1=3&\\
{}&6-2=4&{}&\\
6&{}&&{}\\
\end{array}
\end{align}



\begin{align}
\begin{array}{ccccccccccc}
f[x_0]&f[x_0,x_{1}]&f[x_0,x_{1},x_{2}]&f[x_0,x_{1},x_{2},x_{3}]\\
\\
4&{}&{}&{}\\
{}&\frac{1-4}{0-(-2)}=-\frac{3}{2}&{}&{}\\
1&{}&\frac{1-(-\frac{3}{2})}{1-(-2)}=\frac{5}{6}&\\
{}&\frac{2-1}{1-0}=1&{}&\frac{\frac{1}{3}-\frac{5}{6}}{3-(-2)}=-\frac{1}{15}\\
2&{}&\frac{2-1}{3-0}=\frac{1}{3}&\\
{}&\frac{6-2}{3-1}=2&{}&\\
6&{}&&{}\\
\end{array}
\end{align}

となります。どのように計算すればよいかお分かりいただけたでしょうか?

まとめ

ということで、今回はここまでにしたいと思います。
この記事は準備のためのものなので、まず補間法という方法の問題意識を設定し、高階の差分や差分商を定義していきました。
次回からこれらの道具を使ってやりたかったことに入っていきますので、楽しみにお待ちください!!




では最後までご覧いただきありがとうございました!!

コメントはどんなものでも絶賛受け付け中です!
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします!

それではまた次回お会いいたしましょう!

f:id:rusk_mathematics:20190821165640p:plain

*1:多項式で近似しようとするのが常に良いとは限りませんし、そうでない補間法も多く存在しますが今回は多項式の場合に限定して話をします。

*2:4次くらいまでなら高校入試の連立方程式とかになりそうですね(笑)

*3:線形性とは和をバラバラにできて、定数倍を外に出せることです

グループ分けの基本!同値関係と商集合(1)

こんにちは、ラスクです!

先日、投稿したべき乗和についての記事が(結城先生のおかげもあり)様々な方に読んでいただけたようです。
自信作だったこともあり、とてもうれしいです!
皆様、ありがとうございます。

まだ読んでいない方は、こちらからどうぞ。
mathforeveryone.hatenablog.com

また、この記事で予告した「差分を用いたテイラー展開」の話はまだ準備中ですのでもう少しお待ちください。

さて、今回は学部1年生が集合論の授業で習うであろう「同値関係と商集合」について話していきます。
これは、入学したばかりの数学科の学生の多くが難しいと感じるものだと思っています。。
ただこの概念、わかってしまえば全く難しくないので、出来るだけ丁寧に解説していこうと思います。

全二回に分けてこのテーマを扱います。
まず、第一回となるこの記事では「同値関係」について考えていこうと思います。
「商集合」については次回の記事をお待ちください!



同値関係の定義

では始めていきましょう。
まず同値関係を考える前に、一般の二項関係の定義を見てみましょう。


定義(二項関係
Xを空でない集合とする。
このとき任意の2元の順序を持った(x,y)に対して関係をもつ/もたないが決められているとし、
\begin{align}
x\sim y:\Longleftrightarrow (x,y)は関係をもつ\\
x\nsim y :\Longleftrightarrow (x,y)は関係をもたない
\end{align}
と書くことにする。
このときXには二項関係\simが定められているという。

(上の定義は、あまり厳密な書き方ではありませんが、そこについてはちょっと目をつむることにします。)

結局、二項関係というのは順序を持った組(x,y)に対して「これはOK、これはNG」と○×をつけているようなものです。

ここで、注意しなければならないのは例えx\sim y(つまり(x,y)はOK)であったとしてもy\sim x(つまり(y,x)もOK)とは限らないことです。

例えば、整数の集合\mathbb{Z}に対して
\begin{align}
x\sim y :\Longleftrightarrow 0\le x-y
\end{align}
という二項関係が定められていたとしましょう。
するとx=15,y=8x-y=7\ge 0なので、x\sim yとなります。
しかしy-x=-7<0なのでy\nsim xとなってしまいます。
つまり一般の(同値関係かわからない)二項関係においては、順序をきちんと考えることが重要です
このことは後々でも大切になってくるので、覚えておいてください。


では二項関係のことが分かったうえで、本題である同値関係の定義を見ていきましょう。


定義(同値関係)
Xを空でない集合とする。このときXに定められた二項関係\simが以下の3つの条件を満たすとき同値関係であるという。
任意のx,y,z\in Xに対して
①(反射律) x\sim x
②(対称律) x\sim y\Longrightarrow y\sim x
③(推移律) x\sim y, y\sim z \Longrightarrow x\sim z  

どうでしょう、上で言っていることはお分かりになるでしょうか?
抽象的な数学の書き方に慣れていない方(それこそ学部1年生とか)は「???」となってしまうでしょう。
そこでこの記事では上の定義の意味を100%完璧に理解するという事を目標にしたいと思います!!

結論から言えば、同値関係というのは、集合をいくつかのグループに分けるために必要なものなのです。
関係を持つ者たちの集まりでグループを作って、集合を分けるために①~③の条件が必要になります。

そのことを納得するために、まずは上の定義に現れる3つの条件の言っていることを明確にしてから、最後にいくつかの例を見ていきます。
全部きちんと読む必要はないので、自分の知りたいと思うところだけ読んでいただければと思います。

3つの条件の意味

それでは3つの条件の意味を考えていきましょう!!


………といいたいところですが、
そこに入る前にどーーーーーーーしても説明しなければならないことが一つあります。
それは、定義の①から③の前に書いてある次のの文です。


Xに定められた二項関係\simが以下の3つの条件を満たすとき同値関係であるという。


このことから、同値関係というのは二項関係の一種であるという事がわかります。逆に言えば二項関係で3つの条件を満たせば、なんでも同値関係であるという事です。
このことをわかっていない人がとても多く、それが同値関係というものを意味不明にさせている一つの原因だと思います。

どういうことかというと、ここでの同値関係を高校で習う「同値=必要十分条件」と混同してしまう人がいるという事です。
実際、私が学部の授業で習ったときも
「は?同値って必要十分条件のことじゃないのかよ?意味わからんわー」
といっている人を何人もみました。

誤解を恐れずに言うと、ここでの同値関係は上で定義した二項関係の一種でしかなく、必要十分条件」とはまーーーーーーーーったく関係ありません。
おなじ"同値"という言葉を使っているので、ややこしいですがこのことは心にとめて置いてください。

では、改めて①~③の条件について考えていきます。

反射律

まずは

①(反射律) x\sim x

ですが、これは簡単です。
これはすべての元x自分自身と関係を持っているというものです。これがないと話になりません。

グループ分けの観点から言うと、これは
「自分は自分と同じグループに属している」
という事を保証していることになります……そうじゃなかったら意味が分かりませんね(笑)

対称律

次に

②(対称律)x\sim y\Longrightarrow y\sim x

です。これは(x,y)が関係を持っているなら(y,x)も関係を持っているという事を表しています。
つまり関係を持つ/持たないというのが、まさに対称なものになっているという事ですね。
このことは一般の二項関係については保証されていないのでした。


一つ簡単な例を考えてみます。ある人がある人に連絡が取れるかどうかという関係を見てみましょう。このとき、xさんからyさんに連絡を取れるのならば(基本的には)yさんからxさんに連絡を取ることもできるでしょう。
よってこの関係は対称律を満たします。


グループ分けの観点でいうと
xさんがyさんと同じグループならば、yさんはxさんと同じグループである」
という事を表しています……これもそうでなければ困りますね。

推移律

最後に

③(推移律) x\sim y, y\sim z \Longrightarrow x\sim z

です。これは(x,y)が関係を持ち、(y,z)も関係を持っているならば(x,z)も関係を持っているという事です。
つまり、xyがつながっていて、yzとつながっているならばxzも(yを介して)つながれるという事です。


また先の例でみれば、xさんからyさんに連絡が取れ、yさんからzさんに連絡が取れるのならば、xさんはyさんに頼んでzさんに連絡を取ることが出来ます。このようなことを推移律は言っているわけです。


グループ分けの観点では
xさんとyさんが同じグループ、yさんとzさんが同じグループならばxさんとzさんは同じグループである」
という事を言っています……やはりこれもそうでなければおかしいですね。


以上が、同値関係の3つの条件の意味になります。どうでしょう、わかってきたでしょうか?
簡単に図にまとめると次のようになります。

f:id:rusk_mathematics:20190628221856p:plain


以下では、同値関係の例とそうでない例を見ていきましょう!

同値関係の例やそうでない例

では、例を見ていきますがポイントを一つ。
同値関係を教わったときに、最初に言われる例として整数集合\mathbb{Z}における余りによる分類があげられます。この例も難しいものではないですが、まずはもっと素朴な例を見てみることにしましょう。
このあたりのことは数学的な概念というより、もっと一般的な概念につながるので普通の教科書とかには書きにくいのでしょう。

人類みな家族 VS. 孤独な世界

まずは非常に簡単な例を二つ。
唐突ですがXを人類全体のなす集合とします。このときX上の関係を
\begin{align}
x\sim y :\Longleftrightarrow yはxの家族である
\end{align}
と定義しましょう。このとき①自分は自分と家族で②自分にとって相手が家族ならば相手にとって自分も家族で③家族の家族は家族です*1。よってこの\sim同値関係という事になります。
もし、人類がみなアダムとイブという二人の子孫だとするならば、全員がこの同値関係によって結ばれることになります。
つまりこの同値関係では、全員が同じグループであり、人類みな家族であるという事です。

対して、
\begin{align}
x\sim y :\Longleftrightarrow yはxと同一人物である
\end{align}
としましょう。もちろんこれは同値関係ですが、ドッペルゲンガーがいないとするとこの同値関係では、自分は自分自身としかつながれません。つまり、自分のグループには自分しかいない、孤独な世界が出来上がります…悲しいですね。

f:id:rusk_mathematics:20190628221858p:plain

友達関係

では次に
\begin{align}
x\sim y:\Longleftrightarrow xはyと友達だ(と思っている)
\end{align}
という関係を見てみましょう。このとき皆が他人のことを友達かそうでないかきっちりと区別できているなら取り合えず二項関係であることはOKです。また①自分は自分自身と友達だというのもとりあえず認めましょう*2
しかし
xさんがyさんを友達だと思っているなら、yさんもxさんを友達だと思っている
というのは残念ながら成り立たないでしょう。また
③友達の友達は友達だ
というのも無理がありますね。
よって、この\simという言わば友達関係は同値関係にはならないわけです。ちょっと世知辛いですね。。

f:id:rusk_mathematics:20190628221857p:plain

余りによる分類

では最後に、さきほどいった整数集合\mathbb{Z}の余りによる分類を考えましょう。定義は以下の通りです
整数全体のなす集合\mathbb{Z}1以上の整数nに対して
\begin{align}
x\sim_n y:\Longleftrightarrow x\equiv y(\bmod n)
\end{align}
とする。つまり二つの整数x,yをそれぞれnで割ったとき余りが同じならば関係を持ち、異なれば関係を持たないという事です。
この関係が同値関係になることは…簡単なので省略します*3


では、例えばn=4としたとき\mathbb{Z}が全部でいくつのグループに分かれるかお分かりになるでしょうか??



そう!4つですね!
なぜなら、4で割った余りは0,1,2,34つしかなく、全ての整数が以下のようにどれかのグループに入るからです。
\begin{align}
(余り0):&\ldots,-8,-4,0,4,8,12,\ldots\\
(余り1):&\ldots,-7,-3,1,5,9,13,\ldots\\
(余り2):&\ldots,-6,-2,2,6,10,14,\ldots\\
(余り3):&\ldots,-5,-1,3,7,11,15,\ldots\\
\end{align}


このように\mathbb{Z}を余りによって分類することは受験数学でも必須のテクニックであり、また大学数学的に言ってもユークリッド環の分類というものの入り口になっていて非常に重要です。

最後に

いかがでしたでしょうか?同値関係わかっていただけましたか?
最初に定義を見た時より、見え方が変わったと思えたなら嬉しいです!

個人的な意見ですが、抽象的な数学の議論をしているとどうしても意味不明な定義が出てきます。そういう時はとてつもなく自明なものでもいいので、できるだけ簡単な例を考えてみることから始めてみると案外すんなり飲み込めることが多いです。
今回は人類全体の家族関係、友達関係を見るなどちょっと「数学なの?」と思えるような例まで出しました。でも逆に言えばこのような一般的な概念にまで通用するのが数学の概念のすごいところの一つだと思っています。同値関係とはグループを作るときの人間の思考を定式化したモノです。そう考えると、とっても自然なモノに思えてきますよね。


さて、今回はこのくらいにしましょう。
次回の内容ですが、今回グループ、グループといっていたものがあります。それをきちんと定式化するために商集合を導入し、またwell-definedという概念にも触れようと思います。これまた学部1,2年生の大敵ですが、今回これだけ同値関係を丁寧にみたので結構すんなりいけるのではないかと思っています。


では最後までご覧いただきありがとうございました!!

コメントはどんなものでも絶賛受け付け中です!
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします!

それではまた次回お会いいたしましょう!

f:id:rusk_mathematics:20190628221853p:plain

*1:若干微妙ですがまあ大丈夫でしょう

*2:自分のことくらい愛してあげましょう笑

*3:というより合同式の性質からあまりいうことがありません。

べき乗和の公式…差分からのアプローチ!!

皆さんご無沙汰しております。
約1か月ぶりのブログ更新となってしまいました*1
今更ですが、令和初投稿です(←言いたいだけです)。

さて、今回は「差分系和の公式」ということで話していきたいと思います。
これは高校生以上の方なら一度は目にしたことがあるだろう「べき乗和の公式」に関する話で、個人的にも非常に大好きなものです!!
きっと皆さんも気に入ってくれると信じています。

前提知識は高校の「数列」と「多項式の(いわゆる数Ⅱの)微積」のみですので是非眺めて見てください!

また、初めに言っておくと今回の話はみんな大好き『数学ガール(無印)』の内容を参考にしています。
なので、興味を持たれた方はぜひそちらの方も見てみてください!とても面白いですよ!!

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

べき乗和の公式

では、始めていきましょう。
皆さんは以下の公式たちを高校の時に覚えるように教えられたと思います。

\begin{align}
\sum_{k=1}^n k &=1+2+3+\ldots+n =\frac{1}{2}n(n+1)\\
\sum_{k=1}^n k^2 &=1^2+2^2+3^2+\ldots+n^2 =\frac{1}{6}n(n+1)(2n+1) \tag{1}\\
\sum_{k=1}^n k^3 &=1^3+2^3+3^3+\ldots+n^3 =\{\frac{1}{2}n(n+1)\}^2
\end{align}

これらの公式は多項式で定義された数列の和を計算する際の基本となるのはもちろんですが、ゼータ関数という非常に面白い対象への入り口とも考えることが出来ます。
おそらく、このような「べき乗和の公式」とは人間が根源的に知りたいと思っている興味の対象なのでしょう(?)

ちなみに、上に書いたのは3乗までの公式ですがこれを一般のm乗にした公式は関孝和やベルヌーイによって求められています。


べき乗和の公式(1)/ファウルハーバーの公式
\begin{align}
\sum_{k=1}^n k^m=\frac{1}{m+1}\sum_{i=0}^m {}_{m+1}C_i\ B_i\ n^{m+1-i}\ (m\ge0)\tag{☆}
\end{align}

ここでB_iとはベルヌーイ数と呼ばれる重要な数であり、以下のような式により逐次的に求まります
\begin{align}
B_0=1,\ \sum_{i=0}^n(-1)^i {}_{n+1}C_i\ B_i=0(n=1,2,\ldots)
\end{align}

具体的には
\begin{align}
B_0=1,B_1=-\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=-\frac{1}{30},\ldots
\end{align}
となります。
この公式も非常に美しく、ベルヌーイ数の話もいずれしたいですが今回はそちらには立ち入りません。気になる方はWikipediaへgo!

ja.wikipedia.org


それよりも例えば2乗の公式
\begin{align}
\sum_{m=1}^n m^2 &=1^2+2^2+3^2+\ldots+n^2 =\frac{1}{6}n(n+1)(2n+1)
\end{align}
をもう一度見て、シンプルな感想を考えてみてください。

なんかゴチャゴチャしてて覚えづらい…

というのが普通なのではないでしょうか?
もちろんこれは2乗に限った話ではなく、345乗と増やしていけばもっとゴチャゴチャします。
ただ何とかしたいと言っても、これはある意味完成されたものでこれ以上簡単にすることは残念ながらできません。

しかし
なぜこんなにゴチャゴチャするのか?という理由を考えることによって、少し形の変わった綺麗な公式を見つけることが出来ます。

今回はその話をしようと思います。結論を早く知りたい方は「下降階乗冪と和の公式」の節を読んでください!!

積分についてみてみると…

「べき乗和の公式」がゴチャゴチャする理由を考える前に以下の式を見てみましょう。
\begin{align}
\int_0^x t dt &= \frac{1}{2}x^2\\
\int_0^x t^2 dt &=\frac{1}{3}x^3 \tag{2}\\
\int_0^x t^3 dt &= \frac{1}{4}x^4
\end{align}
これは当たり前の公式ではありますが、改めてみると非常に綺麗で覚えやすいですね。このようなことが成り立つ理由はどこにあるのでしょうか?


そもそも、不定積分微分の逆演算だったので、(2)の式は

(\frac{1}{m}x^m)'=x^{m-1} (mは1以上の整数) \tag{3}

が成り立つことを言っているわけです。
このような綺麗な式が(たまたま)成り立つから不定積分の式は綺麗になるのです。


そして、(通常)微分積分連続的な世界で定義されるものです。

対して、今回のテーマである和\sum離散的な世界での積分に当たるものです。

では離散的な世界での微分に当たるものは??

察しの良い方はお気づきだと思いますが、それが今回のキーワードである差分です。
よって次の節では、差分を定義してそれについて考察していきましょう。

差分と和

という事で差分を定義しますが簡単のため整数全体(これを\mathbb{Z}で表します)の上で定義された関数を考えます。


定義(差分)
整数全体\mathbb{Z}上で定義された実数値関数f(x)に関してその差分\Delta f=f^{[1]}(x)
\begin{align}
\Delta f=f^{[1]}(x)=\frac{f(x+1)-f(x)}{(x+1)-x}=f(x+1)-f(x)
\end{align}
と定義する。

はい、こんな感じです。結局これは何をしているのかというと、もともと微分というのはある点における微小な変化量を見ていたわけですが、離散的な世界では極限という操作が実行できません。最も差が小さいとしても、それは1が限度なので、そこまで近づけた変化量を見ているわけです。

例えば、f(x)=x^2に対してその差分は
\begin{align}
f^{[1]}(x)&=f(x+1)-f(x)\\
&=(x+1)^2-x^2\\
&=2x+1
\end{align}
といった具合に計算できます。

そして少し注意は必要ですが、今定義した差分と和\sumは逆演算になっています。
実際、差分してから和をとった以下の計算をすると、
\begin{align}
\sum_{i=0}^{n-1} f^{[1]}(i)=\sum_{i=0}^{x-1} (f(i+1)-f(i))=f(n)-f(0)
\end{align}
となります。

注意するのは2点です。
①和が0からn-1までになっていること。
②最後に-f(0)というものがついていること。
①は最後の式にf(n)が出てくるよう調整したもので、②は積分定数(あるいは初期条件)のようなものです。
ここら辺は本質的なものではないので、よくわからなければ飛ばしても大丈夫です。


とにかく今、定義したことにより離散的な世界での微積分に対応するものが出来たわけです!

下降階乗冪と和の公式

それでは、上のような対応を意識しつつ連続的な世界での微積分の公式
(\frac{1}{m}x^m)'=x^{m-1} (mは1以上の整数) \tag{3}
を離散的な世界の公式へと変換したいと思います。

ここで、かなり天下りですが以下の関数を考えます。
\begin{align}
f(x)=x(x-1)\ldots(x-m+1) (xは整数、mは1以上の整数)
\end{align}
これは階乗の計算を最初のm個で止めたものです。
以下この関数をx^{\underline{m}}と書き、下降階乗冪と呼ぶことにします。

そして、ここがおもしろいところですが、この関数の差分を考えてみると次のようになります。

\Delta x^{\underline{m}}=(x+1)^{\underline{m}}-x^{\underline{m}}
=(x+1)x(x-1)\ldots(x-m+2)-x(x-1)\ldots(x-m+2)(x-m+1)
=x(x-1)\ldots(x-m+2)\{(x+1)-(x-m+1)\}
=mx(x-1)\ldots(x-m+2)
=mx^{\underline{m-1}}

つまり、こういう事です!


\displaystyle\Delta \frac{1}{m}x^{\underline{m}}=x^{\underline{m-1}} (mは1以上の整数) \tag{4}

どうでしょう!!だいぶ天下りであったとはいえ、離散的な世界の差分について(3)と同様の式を見つけることが出来ました!

そして、これを
\displaystyle\sum_{k=1}^{n-1}k^{\underline{m}}=\sum_{k=0}^{n-1}k^{\underline{m}}に注意して*2、和に関する式に直せば


差分系和の公式
\begin{align}
\sum_{k=1}^{n-1} k^{\underline{m}}=\frac{1}{m+1}n^{\underline{m+1}}\ (m\ge1) \tag{5}
\end{align}

を得ます。(ちなみにここで先のf(0)0なので消えています)

これで和に関しても積分と同じような美しい公式を得ることが出来ました。
結局通常のべき乗はどちらかといえば連続的な世界の計算に適しており、和という離散的なものとは相性が悪いわけです。
それに対して下降階乗冪という離散的な世界と相性のよいべきは、和の公式でも美しい形を保ってくれるというメカニズムになっています。
離散的なものと連続的なものは性質が大きく違うので、それを同時に扱ってしまっていることが「べき乗和の公式」を難しくしている要因なわけです。

ちょっと変わったべき乗和の公式へ

さて、これで終わってもよいのですがせっかくなのでもう少しこの公式を応用してみます。
差分に関する和の公式(5)は非常に綺麗な形で得られましたが、これを使って通常のべき乗和の公式をファウルハーバーの公式(☆)とは別の形で表してみましょう。

\displaystyle \sum_{k=1}^n k^mを求めたいわけですが、(5)を使うためm\ge1としておきます。
そしてk^mを下降階乗冪を使って以下のように表せることが知られています。
\begin{align}
k^m=\sum_{i=0}^m\left\{
\begin{array}{c}
m \\
i
\end{array}
\right\}k^{\underline{i}}
\end{align}
ここで\left\{
    \begin{array}{c}
      m \\
      i 
    \end{array} 
  \right\}(0\le i\le m)第2種スターリング数と呼ばれるもので以下の性質(漸化式)を持ちます。



\displaystyle\left\{\begin{array}{c}m \\ 0 \end{array} \right\}=0(m\ge 1),
\left\{\begin{array}{c}m \\ m \end{array} \right\}=1(m\ge 0)

\displaystyle\left\{\begin{array}{c}m \\ i \end{array} \right\}=\left\{\begin{array}{c}m-1 \\ i-1 \end{array} \right\}+i\left\{\begin{array}{c}m-1 \\ i \end{array} \right\} (1\le i\le m)

この漸化式により、第2種スターリング数は逐次的に求めることが出来ます。
例えば、
\begin{align}
\left\{\begin{array}{c}2 \\ 1 \end{array} \right\}=\left\{\begin{array}{c}1 \\ 0 \end{array} \right\}+1\times\left\{\begin{array}{c}1 \\ 1 \end{array} \right\}=0+1=1 \\
\left\{\begin{array}{c}3 \\ 2 \end{array} \right\}=\left\{\begin{array}{c}2 \\ 1 \end{array} \right\}+2\times\left\{\begin{array}{c}2 \\ 2 \end{array} \right\}=1+2=3
\end{align}
などと計算されます。

そしてこれを使うと\displaystyle \sum_{k=1}^n k^m(m \ge 1)は次のように表すことが出来ます。
\begin{align}
\sum_{k=1}^n k^m &=\sum_{k=1}^n \sum_{i=0}^m \left\{\begin{array}{c}m \\ i \end{array} \right\}k^{\underline{i}}\\
&=\sum_{i=0}^m \left\{\begin{array}{c}m \\ i \end{array} \right\}\sum_{k=1}^n k^{\underline{i}}\\
&=\sum_{i=0}^m \frac{1}{i+1}\left\{\begin{array}{c}m \\ i \end{array} \right\}(n+1)^{\underline{i+1}}(m\ge 1)
\end{align}

ここで2行目は和の順序の入れ替え、3行目で(5)を使っています。
この式も(☆)とは違った形のべき乗和の公式といえるのではないでしょうか?
結果だけもう一度書いておきます。


べき乗和の公式(2)
\begin{align}
\sum_{k=1}^n k^m=\sum_{i=0}^m \frac{1}{i+1}\left\{\begin{array}{c}m \\ i \end{array} \right\}(n+1)^{\underline{i+1}}\ (m\ge 1) \tag{☽}
\end{align}

例えばm=2としてみると
\begin{align}
(☽)&=\sum_{i=0}^2 \frac{1}{i+1}\left\{\begin{array}{c}2 \\ i \end{array} \right\}(n+1)^{\underline{i+1}}\\
&=\frac{1}{0+1}\left\{\begin{array}{c}2 \\ 0 \end{array} \right\}(n+1)^{\underline{0+1}}+\frac{1}{1+1}\left\{\begin{array}{c}2 \\ 1 \end{array} \right\}(n+1)^{\underline{1+1}}+\frac{1}{2+1}\left\{\begin{array}{c}2 \\ 2 \end{array} \right\}(n+1)^{\underline{2+1}}\\
&=0+\frac{1}{2}(n+1)n+\frac{1}{3}(n+1)n(n-1)\\
&=\ldots\\
&=\frac{1}{6}n(n+1)(2n+1)
\end{align}
となり、よく知られたものと一致します
m=3のときは…読者への演習問題とします*3


もちろんこの公式(☽)を使うにはスターリング数の値を知っていなければなりませんが、ファウルハーバーの公式(☆)もベルヌーイ数を知らなければいけないという点において同じです。
という事で、(☽)の公式も実用性という点においては(☆)と同じなのではないかと思っています。
ただし、(☽)には単なる冪ではなく下降階乗冪が残っています。この部分は通常の冪に直すこともできるのですが第1種スターリング数まで出てきて非常にゴチャゴチャするので止めました。
また細かいことですが(☽)の方はm=0では不成立であり、(☆)の方はm=0でも問題なく使えます。
ということで、総合的にはやはり(☆)の公式の方に軍配が上がるかもしれませんが僕は(☽)の公式も非常に綺麗だと思っています*4

また、どちらの公式にも共通することとして
「単純な係数を持つ多項式にはなっていない」
=「ベルヌーイ数、スターリング数というような特殊な数が必要」

という事があげられます。

これこそが、先ほど話した離散的なものと連続的なもののズレを表しており、ベルヌーイ数やスターリング数はそうしたズレに対するしわ寄せだと思うことが出来ます。

非常に面白いですね!!

終わりに

ということで、今回は差分系和の公式というタイトルで話してみました。いかがでしたでしょうか?
離散と連続というのは非常に大事な視点ですが、知らない人にとっては新鮮な考え方かもしれないので紹介させていただきました!
最後のべき乗和の話は個人的によく書けたのではないかと思っています(笑)

冒頭でもお話しした通り、下降階乗冪の話は『数学ガール(無印)』の方に、僕の説明よりも何十倍もわかりやすい説明があるので読んでみることをお勧めします!!!

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

最後になりますが、せっかく今回差分を定義したのでこの話をもう少し別の方向に進めた記事をいつか書きたいと思っています。
具体的には差分を用いたテイラー展開の話がしたいと思っています。
それが次回の記事になるのかどうかはわかりませんが完成しましたら、そちらのほうもご覧いただけるとうれしいです!




では最後までご覧いただきありがとうございました!!

コメントはどんなものでも絶賛受け付け中です!
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします!

それではまた次回お会いいたしましょう!

f:id:rusk_mathematics:20190527020028p:plain

*1:まぁ正直今後もこのくらいのペースになると思います。

*2:ここでm1以上としていないと困ります。

*3:一度言ってみたかったのです

*4:ただこの二つの公式おそらく式変形していけば片方から片方に移れるのだと思います。ただその辺の計算に弱いので、自分ではそれを示せませんでした。どなたか教えていただけたら嬉しいです。

中国剰余定理…その先にあるもの!!

こんにちは、ラスクです。

春は常に眠くて大変です…
でも数学をしていて、何かひらめいたときはハッと目が覚めますよね。
そんなときは眠かったのも忘れて必死に計算してしまいます。
まぁ単なる勘違いなことも多いのですが…


さて、今回は前回お話しした中国剰余定理をもう少し一般的に考えてみようという試みです。
一応、専門的な記事とみなしますが前回の記事(と合同式の知識)があれば無理なく読めると思うので、まだの方はぜひこちらを先にお読みください!
mathforeveryone.hatenablog.com

また、前回と今回の記事で私が伝えたいことを最後に書いたので、そこだけでも読んでくれたらうれしいです!!

復習とちょっとだけ一般化

前回の復習

では初めに前回やったことを思い出しておきましょう。
前回は次のような問題について考えていました。

p_1で割ってr_1余り、p_2で割ってr_2余るような整数がどのようなときに存在するか

そして、最終的な結論として


定理
p_1p_2が互いに素であれば、任意の余りの組み合わせr_1,r_2に対して上のような整数が(1からp_1p_2の最小公倍数Lの中にただ一つ)存在する

という事が得られ、これを中国剰余定理と呼んだのでした。

前回書いた表をもう一度載せておきます。

f:id:rusk_mathematics:20190415001759p:plain


思い出していただけましたでしょうか?

n個に一般化

では少し一般化していきます。ここからは、さすがに記述が面倒なのでここからは合同式をバンバン使っていきます!まだ合同式に慣れてない方でも難しいことはないので、ゆっくり調べながらお読みください。

ということで、次の問題を考えます。



整数0\le r_1\lt p_1,0\le r_2\lt p_2\ldots ,0\le r_n\lt p_nに対して、
\begin{align}
\begin{cases}
x&\equiv r_1 \pmod{p_1}\\
x&\equiv r_2 \pmod{p_2}\\
&\vdots\\
x&\equiv r_n \pmod{p_n}\\
\end{cases}\tag{1}
\end{align}
を満たすような整数xはどのようなときに存在するか。


いやー合同式を使うとすっきりしますね(笑)
内容としては先ほど2個で考えていたものを単にn個に増やしただけですね?
この場合でも"ほぼ"同じ結論が得られます。


定理
(整数p_1,p_2,\ldots,p_nの最小公倍数をLとしておく。)
p_1,p_2,\ldots,p_nがどの二つもそれぞれ互いに素であれば、任意の0\le r_1\lt p_1,0\le r_2\lt p_2,\ldots,0\le r_n \lt p_nに対して(1)を満たすような整数xが(1からLの中にただ一つ)存在する。

この定理も少し一般化されていますが中国剰余定理と呼びます。
これが成り立つ理由は前回説明したこととほぼ同じなので簡単に済ませますが、一つだけ注意しなければならないのは赤字て書いた部分です。この部分を

p_1,p_2,\ldots,p_nが互いに素ならば…

という文章に変えてしまうと、定理が成り立たなくなってしまいます。なぜでしょうか。

そもそも中国剰余定理の成り立つ理由の本質は

p_1,p_2,\ldots,p_nの最小公倍数L=余りの組み合わせの数p_1\times p_2\times\ldots\times p_n

という関係式が成り立つことでした。
ここで例えば、p_1=3,p_2=5,p_3=6として考えてみると確かにこの3つは全体としては公約数を持たず、互いに素ですが、その最小公倍数L=30となってしまいます。すると、
L\lt 3\times5\times 6=90
となってしまい余りの組み合わせ数に対して1からLまでの数が足りなくなってしまうのです。

これに対し
p_1,p_2,\ldots,p_nのどの二つも互いに素であれば
L=p_1\times p_2\times\ldots\times p_n
となるので無事に余りの組み合わせ数とLが一致します。

ということで、複数個の場合はそれぞれが互いに素であることが重要という事です。

以上で、中国剰余定理はn個の組み合わせに拡張できることの説明を終わります。

剰余環を使った表現

ではここからは、これまでの話を少し高級な道具を使って表現してみましょう!
これ以降に話すことはかなり厳密性に欠けるので、いろいろな方からおしかりを受けそうですが(笑)概要を抑えるという意味では問題ないはずなのでお許しください*1

剰余環の導入

まず、整数全体のことを\mathbb{Z}と書きます。これは覚えておいてください。また、この整数全体\mathbb{Z}正の整数pで割った余りでグループ分けしたもの\mathbb{Z}/p\mathbb{Z}と書きます。
今、\mathbb{Z}/p\mathbb{Z}の中身は次のように書けます。
\displaystyle\mathbb{Z}/p\mathbb{Z}=\{\bar{0},\bar{1},\ldots,\overline{p-1}\}
ここで\bar{a}というのはpで割ってa余るような整数全体を表しています。なので、p=5として具体的に表すと

\begin{align}
\bar{0}&=\{\ldots,-5,0,5,10\ldots\}\\
\bar{1}&=\{\ldots,-4,1,6,11,\ldots\}\\
\vdots\\
\bar{4}&=\{\ldots,-1,4,9,14,\ldots\}\\
\end{align}

となっています。
このとき、16は同じグループに入りますから\bar{1}のことを\bar{6}と書いてもよいです。この上についている横線の意味は、「この数字の入っているグループだよ~」という事なのです。なので極端なことを言えば\bar{4}のことを\overline{2019}と書いてもOKです。*2


さらにこの\mathbb{Z}/p\mathbb{Z}に対して演算(足し算と掛け算)を定義します。

あまり大学以降の数学に慣れていない方はギョッとするかもしれませんが、数学では、ある集合上に新たな演算を定義することがよくあります。
そうです!演算というのはもともとあるものではなく、定義をするものなのです!!!
そう思うと、数学というのがとても多様なものであると感じられるのではないでしょうか?


はい。それはさておき(笑)話を続けます。
演算を定義するといっても難しいことはありません。\mathbb{Z}/p\mathbb{Z}の要素は\bar{a}\bar{b}とあらわされていましたから、この二つの足し算や掛け算を
\begin{align}
\bar{a}+\bar{b}&:=\overline{a+b}\\
\bar{a}\times\bar{b}&:=\overline{a\times b}
\end{align}
とすればいいのです。…何を言っているかお分かりになるでしょうか?

p=5として、具体的に見ましょう。
\mathbb{Z}/5\mathbb{Z}の要素として今、\bar{2}\bar{3}を考えます。この二つの足し算は
\displaystyle\bar{2}+\bar{3}=\bar{5}
となります。これに間違いはありませんが、\bar{5}=\bar{0}でしたから
\displaystyle\bar{2}+\bar{3}=\bar{0}
と書くこともできます。同じように掛け算は
\displaystyle\bar{2}\times\bar{3}=\bar{6}=\bar{1}
となります。
つまり、この世界での演算は、普通に足し算や掛け算をした後にp=5で割った余りを考えればよいという事になります。


はい。これでめでたく演算が定義されたと思いきや、まだ問題があります。
なぜなら今、\bar{2}という要素は\bar{7}と書くこともできました。なので
\begin{align}
\bar{2}+\bar{3}と\bar{7}+\bar{3}
\end{align}
という二つの計算結果は同じにならないといけないわけです。(\bar{2}\bar{7}というのは見た目こそ違えどまったく同じものをあらわしている!)
幸い今はどちらも\bar{0}になってくれていますが、上のようなことをすべての場合で考え、きちんと整合性が取れていないと演算が定義されたとは言えません。
証明はしませんが、今の場合は足し算も掛け算も最終的にはきちんと定義できているのでご安心ください。このようなことが確かめられ、きちんと定義されていることを専門的にはwell-definedであるといいます。これは数学科に入学した大学生を最初に(?)苦しめる概念なのですが要は非の打ちどころがなく定義されているという事です。


ということで、長々と書きましたが\mathbb{Z}/p\mathbb{Z}に無事、演算が定義されました!!
この演算が定義された\mathbb{Z}/p\mathbb{Z}のことを\mathbb{Z}剰余環という風に呼びます。

定理の書き換え

では、剰余環を使って中国剰余定理を記述してみましょう。結論としては次のようになります。


定理
p_1,p_2,\ldots,p_nをどの二つも互いに素な正の整数とし、L=p_1p_2\ldots p_nとする。
このとき
\displaystyle\mathbb{Z}/L\mathbb{Z}\simeq\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}
が成り立つ。

この意味を読み解いていきましょう。
まあ、とはいっても前半はいいですね。

\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}
というのは直積といって、それぞれの要素の組を表しています。
今それぞれは各p_i(i=1,\ldots,n)で割った余りを考えていますから、まさに今まで考えていた余りの組み合わせを表しています!


p_1=3.p_2=5,p_3=8だとすれば、
(\bar{1},\bar{3},\bar{5})(\bar{0},\bar{2},\bar{2})などがそれにあたります。
今まではこれをr_1,r_2,r_3などとしていました。
このp_1,p_2,p_3についてはこの先も多用していきます。


また、この後半の数式に出てくる\simeqという記号は二つのものが同型であるという事を表していて、意味はざっくりいうと左辺と右辺が演算を保ったまま一対一に対応している、ということです。

対応のさせ方は以下の通りです。
\mathbb{Z}/L\mathbb{Z}=\{\bar{0},\ldots.\overline{L-1}\}
とあらわされていました。
この\bar{a}という要素の行き先をaを各p_i(i=1,\ldots,n)で割った余りとして定義します*3。この対応をf(\bar{a})=(r_1,r_2,\ldots,r_n)と書きましょう。


先のp_1,p_2,p_3ではL=120ですが、例えば
f(\overline{37})=(\bar{1},\bar{2},\bar{5})となり、
f(\overline{56})=(\bar{2},\bar{1},\bar{0})となります。

つまり平たく言えば、0からL-1の数を各p_iで割った余りを並べて書いてだけです。


そして最後に演算を保つという意味ですが、これは
f(\bar{a}+\bar{b})=f(\bar{a})+f(\bar{b})

f(\bar{a}\times\bar{b})=f(\bar{a})\times f(\bar{b})
が成り立つという事。つまり、先に演算してからfで送っても、fで送ってから演算しても同じ結果になるという事です*4


これも先程までのp_1,p_2,p_3において
\begin{align}
f(\overline{37}+\overline{56})=f(\overline{93})=(\bar{0},\bar{3},\bar{5})=(\bar{1},\bar{2},\bar{5})+(\bar{2},\bar{1},\bar{0})=f(\overline{37})+f(\overline{56})\\
f(\overline{37}\times\overline{56})=f(\overline{32})=(\bar{2},\bar{2},\bar{0})=(\bar{1},\bar{2},\bar{5})\times(\bar{2},\bar{1},\bar{0})=f(\overline{37})+f(\overline{56})\\
\end{align}
と確かに成り立っています。このあたりの計算は剰余環やfという対応の理解を試すいい練習になるので是非自分で数字を決めて試してみてください。


ということで、各部分の説明が終わりました。
まとめると
\mathbb{Z}/L\mathbb{Z}\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}はそれぞれの余りを考えるfという対応によって、演算を保ちながら一対一に対応する。
という事になります。


さて、このことがきちんといままで考えていた中国剰余定理と一致していることは理解できていますか?
キーポイントは一対一に対応するという事です。
まず、対応が一対一という事から、ことなる\mathbb{Z}/L\mathbb{Z}の要素がfによって同じ要素に送られることはありません。このことは0からL-1までの数が同じ余りの組み合わせを実現することはない、という事に対応しています。

つぎに、全ての\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}の要素はある\mathbb{Z}/L\mathbb{Z}の行き先になるという事は、まさに前回から考えていた
\begin{align}
\begin{cases}
x&\equiv r_1 \pmod{p_1}\\
x&\equiv r_2 \pmod{p_2}\\
&\vdots\\
x&\equiv r_n \pmod{p_n}\\
\end{cases}\tag{1}
\end{align}
という整数xが存在する、という事に対応しているわけです。

さらに今回は存在性だけではなく、演算もセットで考えたので、前回の中国剰余定理よりも少しパワーアップしています。
演算を保つというのは同型である、という事に関してなくてはならない性質なのです。
でないと、個数が等しければなんでも同型になってしまいます…


ということで、文章で長ったらしく書かれた中国剰余定理は
\displaystyle\mathbb{Z}/L\mathbb{Z}\simeq\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}
という一本の数式にまとめることが出来ました!
とてもかっこいい式ですよね!!!!

まだまだこんなもんじゃない

今回は中国剰余定理をn個バージョンに一般化した後、それを剰余環という概念を用いてまとめていきました。
そのおかげで、とてもすっきりとしたものになったと思います。

でも
剰余環を導入した理由はそれだけではありません。
実はこの中国剰余定理、ほかにもいろいろな所で成り立つのです!

高校生で"余り"というものを考える概念は整数ともう一つあります。そう!多項式です!!
多項式バージョンの中国剰余定理を書くと次のようになります。


定理
\mathbb{R}[x]を実数係数の多項式全体とする(本当は実数である必要はない)。
またP_1,P_2,\ldots,P_nをどの二つも互いに素な多項式とし、L=P_1P_2\ldots P_nとする。
このとき
\mathbb{R}[x]/L\mathbb{R}[x]\simeq\mathbb{R}[x]/P_1\mathbb{R}[x]\times\ldots\times\mathbb{R}[x]/P_n\mathbb{R}[x]
が成り立つ。

これについて説明していると、記事の分量が2倍になってしまうので止めますが(笑)、ともかく多項式でも全く同様の定理が成り立つという事です。


実は整数と多項式というのは非常に性質が似ているものなのです。そんな風には見えませんよね。

そして、少し乱暴ですが、このようなものを(とても)抽象化したものが環という概念になります。
中国剰余定理は一般の環に対して成り立つということがわかっています。

最後に

前回以上に長くなってきているのでそろそろ終わりたいと思います(笑)

前回と今回の記事では中国剰余定理についてお話ししましたが、その中で私が伝えたいことは、
大学の授業で習うような一見複雑そうに見える概念も実はとてもシンプルで自然なものであることが多い
という事です。

思い出してみると、このテーマの導入は麻布中学の入試問題でした。そしてそれは決して難しいものではなく、誰もが理解できるようなシンプルなものです。
そのような問題をどんどん一般化するにつれて、剰余やwell-defined、同型、直積などの概念が現れ、最後には(少し無理矢理でしたが)環というものにまで触れることが出来ました。

そしてそこまでのステップは、どれもそこまでぶっ飛んだ発想ではなかったと思います。
大学の数学科で習うような概念はどれも抽象的なものばかりです。
でも、そのどれもが必要であるがゆえに生み出されたのです!!

ですから、複雑そうに見えてもすぐに諦めず、どんどん手を動かしてみてください。
きっと色々なものが自然に頭に入ってくるはずです!!


なにやら説教くさくなってしまいましたが(笑)、このブログではこれからも、できるだけ取っ掛かりは簡単に、大学レベルの数学に触れていこうと思います!!




コメントはどんなものでも絶賛受け付け中です!
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします!

それではまた次回お会いいたしましょう!

f:id:rusk_mathematics:20190424033102p:plain

*1:特に剰余類に関することはかなり曖昧なのでいつか別記事で書きます

*2:まあ普通は0から4の数を使って表しますが…

*3:もちろんここでもwell-definedであるかどうかの議論が必要です

*4:本当は環準同型であることを言うには単位元単位元に移すこともなくてはいけませんが今回はまだ環を定義していないので目を瞑ります

中学入試にも頻出!その名も中国剰余定理!

みなさま、こんにちは!

もう4月も中旬に差し掛かろうというのにまだまだ寒くてテンション下がり気味のラスクです↷↷
でも、今回がいよいよ本格的なブログの始動なのでテンション上げて頑張ります!!

最初という事で、内容は非常にシンプルなものを選びました。
なのでみなさま気軽な気持ちで読んでいってください!!

中学入試問題から

まず今回のテーマに直結する次の問題を考えてみてください。

4で割ると2余り、5で割ると3余る2けたの整数のうち、もっとも大きい数を求めなさい。
(H18 麻布中学校)

いかがでしょうか?とてもシンプルな問題ですよね。
おそらくこの問題を見て文章の意味が分からないという方は少ないと思います。そして、このような問題が超名門校である麻布中学で出ているのです。ちなみに、ほとんど同じ問題(数字違うだけ)が、こちらも超名門校の灘中2008年にも出ています。
中学入試というと、何やら込み入った問題を方程式などを使わずに解くというイメージが強い方も多いのではないでしょうか。
でも、この問題を見ると、そういったものばかりではないことがわかっていただけるのではないかと思います。

さて、話が脱線しそうなので、以下この問題の解説をしています。



とりあえず問題文で言われた数を列挙してみましょう。

(4で割って2余る数):2,6,10,14,{\bf 18},22,26,30,34,{\bf 38},42,46,50,54,{\bf 58},62,\ldots
(5で割って3余る数):3,8,13,{\bf 18},23,28,33,{\bf 38},43,48,53,{\bf 58},63,\ldots

太字で書いたものが共通して出てくる数になり、そこだけに注目すれば18から順に20ずつ大きくなるのがわかるでしょう。
したがって、この問題の答えは、 18+20\times4=98より \underline{98}となります。*1


はい…それだけです。これのどこがおもしろいのでしょうか?(笑)
それは問題文に出てくる数字を少し変えることで見えてきます。

そこで以下では

p_1で割ってr_1余り、p_2で割ってr_2余るような整数 (*)

が存在するかどうか、という事を考えていきたいと思います。

少し考察

とその前に、今観察したことをまとめておきましょう。くどく感じるかもしれないですが、大事な所なので読んでみてください。

まず、最初の問題の条件を満たす数は18から初めて20おきに出てきました。この20というのは、割る数であるp_1=4p_2=5最小公倍数です。
一般に(*)のような整数が何か一つ見つかれば、その数からp_1p_2の最小公倍数(Lとしましょう)だけずらしていった数も同じ性質を持ちます。

f:id:rusk_mathematics:20190415003723p:plain

このことから、何か一つ答えが見つかれば、その数から何度かLを引く(あるいは足す)ことによって答えを1からLまでの中に見つけることが出来ます。
先程の例でいえば、もし仮に18より先に3858という数が見つかってしまっても20を何回か引くことによって18を見つけることが出来るというわけです!

よって(*)のようなものが存在するかどうかを考えるときは1からLまでの数について調べればいいことになります!

さらに!
そんな1からLまでの整数の中で(*)の条件を満たすようなものはあるとしても一つだけです。
実際、二つの整数x_1,x_2がどちらも(*)の条件を満たすとするとx_1-x_2p_1p_2の公倍数となるので、x_1x_2は少なくともLだけ離れていなけらばならないのです。

これを言い換えれば、1からLまでの整数はそれぞれ異なる余りの組み合わせを実現するという事です。
これについてまだピンとこない人も、あまり気にせず続きを読んでみてください。


いろいろな数で試すと…

それでは、先ほど言った通り最初の問題の数を色々変えて実験してみましょう。

余りを変える

まずは、余りの組み合わせを変えてみて

4で割ると1余り、5で割ると4余る整数

を考えてみましょう。この場合も先程と同様に数を列挙しますが、上の考察から1から20までの数を書けば十分でしたね?

(4で割って1余る数):1,5,{\bf 9},13,17
(5で割って4余る数):4,{\bf 9},14,19

無事に9という数が見つかりました。
今、余りのパターンとして考えられるのは4*5=2020通りですが、そのすべてのパターンで試したものが下の表になります。

f:id:rusk_mathematics:20190415003810j:plain

どのパターンで試してもきちんと条件を満たす数が見つかりますことがわかりますね。ぜひみなさんもいくつか検算してみてください!

割る数を変える

では一方、割る数のほうを変えたらどうなるでしょう。

3で割ると2余り、8で割ると3余る整数

というものを考えると、
(3で割って2余る数):2,5,8,{\bf11},14,17,20,23
(8で割って3余る数):3,{\bf 11},19,
となって無事に見つかりますが*2

4で割ると2余り、6で割ると3余る整数

というものは
(4で割って2余る数):2,6,10
(6で割って3余る数):3,9
となり0から12(46の最小公倍数)までの間には見つかりません。すなわち、そんな整数は存在しないという事です

このように割る数の方の組み合わせ(p_1p_2)を変えると条件を満たす整数が存在したり、しなかったりすることがわかりました。

すると、当然の疑問として

「割る数がの組み合わせ(p_1p_2)がどういったものなら、全ての余りの組み合わせ(r_1r_2)に対して(*)の条件を満たす整数が存在するのか?」

という事が気になりますよね?
実はそれを解決してくれるのが今回のテーマである中国剰余定理なのです!

中国剰余定理

定理の内容は以下の通りです。


定理
p_1,p_2を正の整数とする。このときすべての0\le r_1\lt p_1,0\le r_2\lt p_2に対して
p_1で割ってr_1余り、p_2で割ってr_2余るような整数 (*)
が存在するための必要十分条件p_1,p_2が互いに素であることである。

この定理の内容は読み取れますでしょうか?
前半の部分は今まで考えてた問題を改めて書いただけです。
そして後半に出てくる互いに素というキーワードですがこれが重要です。


二つの整数が互いに素とは、公約数を1しか持たないということです。
そして、そのような整数p_1,p_2に対してのみ(*)を満たすような整数がすべての余りの組み合わせに見つかるというのが定理の主張です。


確かに上で考えた例を見てみると、p_1=4,p_2=5p_1=3,p_2=8の場合はどちらも互いに素なので答えが見つかっていますが、p_1=4,p_2=6の場合は互いに素でない(2という公約数を持つ)ので余りの組み合わせによっては答えが見つかりません。

ということで、なんとなく上の定理が正しそうな気がするわけですが、本当に正しいのかはもう少し考えなければいけません。
なので以下ではこの定理が成り立つ理由を説明していきます!

なぜ成り立つのか

といっても、先ほどの少し考察のところで述べたことを考えればすぐにわかります。
今、p_1,p_2を固定すると余りの組み合わせはp_1\times p_2通りあります。

また、
①(*)を満たすような整数が存在するとすれば、1からLの中にそのようなものがある。
1からLの整数はそれぞれ別の余りの組み合わせを実現する。

のでした。

いま、
p_1,p_2互いに素であればL=p_1\times p_2
そうでなければL\lt p_1\times p_2
という事が成り立ちます。

よって
p_1,p_2が互いに素であれば、余りの組み合わせの数とLが一致します。このことと②のことを合わせれば、全ての余りの組み合わせに対応できることがわかります。
逆にp_1,p_2が互いに素でなければ、余りの組み合わせの数よりもLの方が小さいので、全ての余りの組み合わせには対応できないという事になります。

以上のことをまとめると下のようになります。

f:id:rusk_mathematics:20190415001759p:plain

これが中国剰余定理が成り立つ理由です。納得できましたでしょうか?

終わりに

という事で今回は
p_1で割ってr_1余り、p_2で割ってr_2余るような整数
が存在するかどうかを考え、その結論である中国剰余定理を紹介しました。


複数の整数に関する初等的な性質を調べるときには互いに素かどうか、というのが重要になることが多いですが今回もそのうちの一つでした。ぜひ自分で何かp_1p_2を選んで上に書いたような表を完成させてみてください。数学をやるうえで大事な力の一つに<具体的にやってみる力>というのがあると思います。なので今回も自分で手を動かすことによって、きっとこの定理がより深く理解できるはずです。


また、今回は存在性にのみ着目して、どのようにすれば答えが見つかるのかというのには触れませんでしたがそれに関しても面白い方法があるのでぜひ調べてみてください。



さて、最初なので丁寧にやり過ぎて、かなり長くなってしまっているので(笑)そろそろ終わりたいと思います。
いやぁ短くまとめるのは難しいですね、次からもっと頑張ります…


最後に、実は今回紹介した中国剰余定理はおそらくもっとも弱い形で述べられています。
しかし
これがもう少し一般化されても本質は今回説明した通りなので、次回(?)はもう少しこの内容を専門的に定式化するとどうなるのか、というのを見ていきたいと思います*3。お楽しみに!





コメントはどんなものでも絶賛受け付け中です!
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします!

それではまた次回お会いいたしましょう!

f:id:rusk_mathematics:20190415003905p:plain

*1:もちろん、これが完璧な答案かと言われればNoですが法則を見極めて、答えを出すだけならばこれで十分でしょう。

*2:先ほど同様すべての余りの組み合わせに対して答えが見つかります

*3:中国剰余定理は現代数学においてもなくてはならないものなのです

このブログについて

みなさま、はじめまして!
私はラスクと申します。

この度、ラスクのMathematics for Everyone!というブログをはじめさせていただきました。
ブログを書くのは初めてのことなので至らない点もあるかと思いますが、どうぞよろしくお願いいたします。

これから、このブログに関する簡単な説明を述べたいと思います!

このブログのテーマ

まず一番大事なこのブログのテーマですが、それはずばり
「数学が得意な人もそうでない人もちょっとだけ楽しめるブログ」
です!どうでしょうか?(笑)
このテーマさえ読者の方に伝われば、今回の記事に関して私は大満足なのですがさすがにもう少し説明を加えます。

私は現在、大学院で数学を専攻しています。このブログでは、そんな私が高校や大学(学部時代)に知って面白いと感じたトピックに関していろいろと話していこうと思っています。
こういう話をすると大抵の人は
「難しそう…。私に理解できるかな…。」
と思ってしまいがちですが、そんなときこそこのブログのテーマを思い出してください!
きちんと「数学が得意でない人」にも(中学・高校生くらいなら)わかるようなトピックを選ぶつもりです!
具体的には中学入試などから話題を選んでくるつもりでいます。
ぜひ雰囲気をつかむだけでも見てみてください!

でも
それだけじゃ物足りない人もいると思います!というか、私が物足りません(笑)
なので大学の学部で習うような数学を扱った記事もきちんと書いていこうと思います。
私は代数が専門のため、どうしてもそちらの分野に話題が偏ってしまうと思いますが、とても面白い(と私は思っている)のでどうぞご期待ください!
(専門的な分野に関することはぜひ最後の注意に書いたこともお読みください)

以上がこのブログのおおざっぱな内容になりますが、次にこのブログの構成についてお話します。

このブログの構成

上に述べたように、このブログは
-すべての人向けの初等的な記事
- 数学が得意(専門)な人向けの応用的な記事
の2つのカテゴリーに分けられています。

きちんと二つのカテゴリーを用意し記事を分別しますので参考にしてください。

ただ!
このブログならでは(?)な特徴として、初等的な記事で扱ったことを、もう少し広い目で見たり、厳密に扱ったものを専門向けの記事で話すことがあります。この点がこのブログ一番のセールスポイントなのです(笑)
なので専門向けのカテゴリーに入っていてもぜひ一度のぞいてみてください。きっと面白いと感じることがあるはずです。

イメージキャラクター

一番大事(?)なことがもう一つありました!
このブログのアイコンになっている子ですが、名前を
「いんとちゃん」
といいます。可愛いでしょ???
ブログの内容が内容なのでそこまで多くは登場させられませんがこれからイメージキャラクターとして頑張ってもらいます!

注意

最後に大切な注意をいくつか申し上げます。

まず、上に書いた通りこのブログでは大学の数学科が扱うようなことも話題にしますが、それ以上に高度なものを扱うことは基本ありません。
なので、数学を専門とされている方(特に院生以上の方)の方が見ることによって新たな知見が得られるようなものにはなっていません。
そして、話題の種類としましても誰も知らないようなニッチな話題を取り上げるよりは、一般の方にもわかるような基本的な話題を重視します。なので、その界隈の人たちにとっては有名な話題が多くなってしまうかもしれません。
でも、「話す人が違えば、同じことでも違って見える」という言葉を私は信じているのでこの方針で行こうと思います。

また、細心の注意を払う予定ですが、私もまだまだ未熟なためどうしても間違いや誤植が見つかることがあると思います。
そのときはコメントで教えていただければ、対応させていただきます。
また、それ以外でもご意見・ご感想などはどんどん送ってください(笑)


細かい話をいろいろとしてしまいましたが、これからのんびり更新していこうと思うので皆さまどうぞよろしくお願いいたします!!
よろしければ、読者になるボタンとTwitterフォローもポチッとお願いします。


f:id:rusk_mathematics:20190409203827j:plain