【離散数学】ラムゼー数の応用は? 合同式上のフェルマーの最終定理との関連まで解説

2024.10/09

こんにちは!半沢です!

今回の記事では離散数学におけるラムゼー数(Ramsey number)の応用について解説したいと思います。

ラムゼー数の応用として特に私が面白いと感じている

mod  p\mathrm{mod}\,\,p\,上のフェルマーの最終定理との関連を中心に話していきたいと思います。

前回の記事で(狭義)ラムゼー数の定義については確認しているので,必要な方はご参照ください。

ぜひ読んでいってください。

整数論への応用

シューアの定理(Schur’s theorem)

まずは次節で使う下のシューアの定理を確認&証明していきましょう。

シューアの定理

任意の自然数k\,k\,に対し,自然数N\,N\,を十分大きくすると次の性質()\,(\ast)\,を持つようにできる。

性質()\,(\ast)\cdots\,NN\,元集合X={1,2,,N}\,X=\{1,2,\ldots,N\}\,k\,k\,色で彩色したとき,
XX\,は方程式x+y=z\,x+y=z\,の解として同じ色のみで彩色されたものを持つ。

証明の前にもしk\,k\,に対し性質()\,(\ast)\,を持つ自然数N\,N\,が存在したら,
nN\,n\geq N\,を満たす自然数n\,n\,も性質()\,(\ast)\,を満たすことを押さえておいてください。

なぜならn\,n\,元集合のk-\,k\text{-}彩色はN\,N\,元集合のk-\,k\text{-}彩色とみなせるためです。

そのためこれからの証明では性質()\,(\ast)\,を持つ自然数N\,N\,の存在性を示していきましょう。

それでは証明です。

前提としてNN\,元集合X={1,2,,N}\,X=\{1,2,\ldots,N\}\,k-\,k\text{-}彩色に使った色を
1,2,,k\,1,2,\ldots,k\,と書くことにします。

そして自然数k\,k\,に対してN\,N\,として

N=Rk(3,,3)N=R_k(3,\ldots,3)\,と取りましょう。

このときまず,完全グラフKN+1\,K_{N+1}\,(N+1)\,(N+1)\,個の点を1,2,,N+1\,1,2,\ldots, N+1\,とみなします。

その辺ij\,ij\,ij\,|i-j|\,X\,X\,において彩色されている色で塗ることにして,KN+1\,K_{N+1}\,k-\,k\text{-}辺彩色を作ります。

するとラムゼー数の定義から,ある色l  (1lk)\,l \,\,(1 \leq l\leq k)\,K3\,K_3\,が存在します。

このK3\,K_3\,3\,3\,つの頂点をa,b,c  (a<b<c)\,a,b,c\,\,(a\lt b\lt c)\,とすると,

もちろんba,cb,caX\,b-a,\,c-b,\,c-a\in X\,は色l\,l\,で塗られているので同色で,

(ba)+(cb)=ca(b-a)+(c-b)=c-a\,となります。

したがってx=ba,y=cb,z=ca\,x=b-a,\,y=c-b,\,z=c-a\,と取れば,題意は示されました。\quad\square

mod  p\mathrm{mod}\,\,p\,上のフェルマーの最終定理

ここからが本題です。

前節で示したシューアの定理を用いて,
素数p\,p\,が十分に大きいときmod  p\,\mathrm{mod}\,\,p\,上ではフェルマーの最終定理の反例が存在することを示していきましょう。

つまり次のことを証明します。

定理1\,1\,
任意の自然数k\,k\,に対し,自然数N\,N\,を十分大きくすると次の性質()\,(\ast)\,を持つようにできる。

性質()\,(\ast)\cdots\, p>Np\gt N\,を満たす任意の素数p\,p\,に対して,

xk+ykzk(modp)x^k+y^k\equiv z^k\pmod{p}\,を満たす自然数x,y,z\,x,y,z\,が存在する。

それでは証明です。

kk\,に対して,自然数N\,N\,を十分大きくすることでシューアの定理の性質()\,(\ast)\,N\,N\,が持つようにします。

そうしてp>N\,p\gt N\,を満たす素数p\,p\,について考えましょう。

以下では表記を簡略化するためmod  p\,\mathrm{mod}\,\,p\,は省略し,”\,\equiv\,”のみで合同であることを表すことにします。

ここで有限体Fp\,\mathbb{F}_{p}\,の乗法群Fp×\,\mathbb{F}_{p}^{\times}\,

Fp×={1,2,,p1}\mathbb{F}_{p}^{\times}=\{1,2,\ldots,p-1\}\,というp1(N)\,p-1(\geq N)\,元からなる集合ですね。

そこで性質()\,(\ast)\,が使えるように以下のようにk-\,k\text{-}彩色していく流れとなります。

Fp×\mathbb{F}_{p}^{\times}\,は巡回群であることが知られていますので,準備のためにその生成元の一つであるg\,g\,を取ってきます。

このとき以下のようにk-\,k\text{-}彩色してきましょう。

彩色方法
xFp×x\in \mathbb{F}_{p}^{\times}\,について,xgr  (0r<p1)\,x\equiv g^{r}\,\,(0\leq r \lt p-1)\,となるr\,r\,が一意的に存在する。

そこでr\,r\,k\,k\,で割った余りがi  (0ik1)\,i\,\,(0\leq i \leq k-1)\,ならx\,x\,を色i\,i\,で彩色することにする。

要はFp×\,\mathbb{F}_{p}^{\times}\,の元を生成元の指数部分によって彩色(分類)した感じですね。

このときシューアの定理の性質()\,(\ast)\,から

ある色i  (0ik1)\,i\,\,(0\leq i \leq k-1)\,と,その色で彩色されたx,y,zFp×\,x’,y’,z’\in \mathbb{F}_{p}^{\times}\,が存在してx+y=z\,x’+y’=z’\,となります。

色の彩色法から商としてある整数jx,jy,jz\,j_x,j_y,j_z\,が存在して

xgkjx+i,ygkjy+i,zgkjz+ix’\equiv g^{kj_x+i},\, y’\equiv g^{kj_y+i},\, z’\equiv g^{kj_z+i}\,となります。

x+y=zx’+y’=z’\,よりgkjx+i+gkjy+igkjz+i\,g^{kj_x+i}+g^{kj_y+i}\equiv g^{kj_z+i}\,ですので,両辺にgi\,g^{-i}\,をかけると

gkjx+gkjygkjyg^{kj_x}+g^{kj_y}\equiv g^{kj_y}\,が成り立ちます。

x=gkjx,y=gkjy,z=gkjzx=g^{kj_x},y=g^{kj_y},z=g^{kj_z}\,とすれば,求めたい自然数x,y,z\,x,y,z\,を得ることができるので,題意は示されました。\quad \square

ラムゼー数の話がこうしてフェルマーの最終定理につながることはかなり面白いと感じます。

その他の応用

ここではその他の応用について話していきたいと思います。

前回の記事で解説した狭義ラムゼー数ではなく,広義ラムゼー数まで拡張すればハッピーエンド定理の証明につながります。

ハッピーエンド定理は凸多角形に関する幾何の定理でその主張も理解しやすいものなので,気になる方は参考図書[1]\,[1]\,などで調べてみると良いと思います。

もしくは広義ラムゼー数の解説が完了したら,加筆しようと考えているので,そちらをお待ちください。

ちなみに”ハッピーエンド”という名前は定理の主張に関するものでなく,その定理の証明の過程で数学者が結婚したことに由来します。

その他,情報理論やゲーム理論への応用があるらしいですが,私があまり詳しくないのでよく分かりません。

こちらに関しても私の知識が増えたら加筆しようと思っているので,誰か詳しい方がいたらぜひ教えてください。

まとめ

今回の記事ではラムゼー数の応用を解説いたしました。

ラムゼー数がフェルマーの最終定理につながるのはかなり面白かったですね。

もし「説明がわかりにくい」などのご意見がありましたら,
X(旧:Twitter)で#トイカラでつぶやいていただけると,できる限り対応します。

また「その他の応用についてもっと詳しく解説してほしい」といった要望が多ければ,加筆するつもりなのでX(旧:Twitter)でつぶやいていただけるとありがたいです。

ここまで読んでいただき,ありがとうございました。

参考図書

  • [1][1] Vašek Chvátal(著),秋山仁(監訳),小館崇子,酒井利訓,徳永伸一,松井泰子(訳)”ポール・エルデス:離散数学の魅力 伝説の講義”.初版.近代科学社.2023出版.257p.

人気記事ランキング

  • 【超基本_小学校レベル第9回】速さ 算数における時間の表し方・単位換算,時速・分速・秒速の変換,距離・速さ・時間の関係,平均の速さ

  • 【グラフ理論】隣接行列とは? 定義・イメージから隣接行列の固有値の重要性についても解説

  • 【超基本_小学校レベル第6回】四則演算の計算する順番 計算の工夫

  • 【受験生必見!】京大数学の整数問題に有効な「フェルマーの小定理」を紹介

  • 【東大受験生必見!】東大数学の体積問題の解き方 ~おまけ~

新着記事

  • 【解析学】リーマンゼータ関数の整数における特殊値は? 証明も含めて解説

    2025.04/03

  • 【複素解析学】cot\,\cot\,の部分分数分解! 留数定理による証明を解説

    2025.04/01

  • 【解析学】cot\,\cot\,の部分分数分解! 美しいヘルグロッツの技法による証明を解説

    2025.03/31

  • オリジナル問題集

    2025.03/21

  • 【グラフ理論】ライツアウトとは? 遊び方から全ライトがONの状態は消灯できることの証明まで解説

    2025.03/20