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

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

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

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

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

それでは証明です。

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

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

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

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

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

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

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

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

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

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

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

ここからが本題です。

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

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

それでは証明です。

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

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

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

ここで有限体\(\,\mathbb{F}_{p}\,\)の乗法群\(\,\mathbb{F}_{p}^{\times}\,\)は

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

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

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

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

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

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

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

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

\(x’\equiv g^{kj_x+i},\, y’\equiv g^{kj_y+i},\, z’\equiv g^{kj_z+i}\,\)となります。

\(x’+y’=z’\,\)より\(\,g^{kj_x+i}+g^{kj_y+i}\equiv g^{kj_z+i}\,\)ですので，両辺に\(\,g^{-i}\,\)をかけると

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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