【離散数学】ラムゼー数の応用は? 合同式上のフェルマーの最終定理との関連まで解説
こんにちは!半沢です!
今回の記事では離散数学におけるラムゼー数(Ramsey number)の応用について解説したいと思います。
ラムゼー数の応用として特に私が面白いと感じている
上のフェルマーの最終定理との関連を中心に話していきたいと思います。
前回の記事で(狭義)ラムゼー数の定義については確認しているので,必要な方はご参照ください。
ぜひ読んでいってください。
整数論への応用
シューアの定理(Schur’s theorem)
まずは次節で使う下のシューアの定理を確認&証明していきましょう。
シューアの定理
任意の自然数に対し,自然数を十分大きくすると次の性質を持つようにできる。
性質元集合を色で彩色したとき,
は方程式の解として同じ色のみで彩色されたものを持つ。
証明の前にもしに対し性質を持つ自然数が存在したら,
を満たす自然数も性質を満たすことを押さえておいてください。
なぜなら元集合の彩色は元集合の彩色とみなせるためです。
そのためこれからの証明では性質を持つ自然数の存在性を示していきましょう。
それでは証明です。
前提として元集合の彩色に使った色を
色と書くことにします。
そして自然数に対してとして
と取りましょう。
このときまず,完全グラフの個の点をとみなします。
その辺をがにおいて彩色されている色で塗ることにして,の辺彩色を作ります。
するとラムゼー数の定義から,ある色のが存在します。
こののつの頂点をとすると,
もちろんは色で塗られているので同色で,
となります。
したがってと取れば,題意は示されました。
上のフェルマーの最終定理
ここからが本題です。
前節で示したシューアの定理を用いて,
素数が十分に大きいとき上ではフェルマーの最終定理の反例が存在することを示していきましょう。
つまり次のことを証明します。
定理
任意の自然数に対し,自然数を十分大きくすると次の性質を持つようにできる。
性質 を満たす任意の素数に対して,
を満たす自然数が存在する。
それでは証明です。
に対して,自然数を十分大きくすることでシューアの定理の性質をが持つようにします。
そうしてを満たす素数について考えましょう。
以下では表記を簡略化するためは省略し,””のみで合同であることを表すことにします。
ここで有限体の乗法群は
という元からなる集合ですね。
そこで性質が使えるように以下のように彩色していく流れとなります。
は巡回群であることが知られていますので,準備のためにその生成元の一つであるを取ってきます。
このとき以下のように彩色してきましょう。
彩色方法
について,となるが一意的に存在する。
そこでをで割った余りがならを色で彩色することにする。
要はの元を生成元の指数部分によって彩色(分類)した感じですね。
このときシューアの定理の性質から
ある色と,その色で彩色されたが存在してとなります。
色の彩色法から商としてある整数が存在して
となります。
よりですので,両辺にをかけると
が成り立ちます。
とすれば,求めたい自然数を得ることができるので,題意は示されました。
ラムゼー数の話がこうしてフェルマーの最終定理につながることはかなり面白いと感じます。
その他の応用
ここではその他の応用について話していきたいと思います。
前回の記事で解説した狭義ラムゼー数ではなく,広義ラムゼー数まで拡張すればハッピーエンド定理の証明につながります。
ハッピーエンド定理は凸多角形に関する幾何の定理でその主張も理解しやすいものなので,気になる方は参考図書などで調べてみると良いと思います。
もしくは広義ラムゼー数の解説が完了したら,加筆しようと考えているので,そちらをお待ちください。
ちなみに”ハッピーエンド”という名前は定理の主張に関するものでなく,その定理の証明の過程で数学者が結婚したことに由来します。
その他,情報理論やゲーム理論への応用があるらしいですが,私があまり詳しくないのでよく分かりません。
こちらに関しても私の知識が増えたら加筆しようと思っているので,誰か詳しい方がいたらぜひ教えてください。
まとめ
今回の記事ではラムゼー数の応用を解説いたしました。
ラムゼー数がフェルマーの最終定理につながるのはかなり面白かったですね。
もし「説明がわかりにくい」などのご意見がありましたら,
X(旧:Twitter)で#トイカラでつぶやいていただけると,できる限り対応します。
また「その他の応用についてもっと詳しく解説してほしい」といった要望が多ければ,加筆するつもりなのでX(旧:Twitter)でつぶやいていただけるとありがたいです。
ここまで読んでいただき,ありがとうございました。
参考図書
- Vašek Chvátal(著),秋山仁(監訳),小館崇子,酒井利訓,徳永伸一,松井泰子(訳)”ポール・エルデス:離散数学の魅力 伝説の講義”.初版.近代科学社.2023出版.257p.