この記事は
日曜数学 Advent Calendar 2017 - Adventar
12日目の記事です。
昨日はパヤシさんによる「芸術/自然と数学」
でした。自然現象や芸術作品の対称性の中に群が現れることが見れてとても楽しい記事でした。
昨日の記事でもわかるように、群はそれ自体だけでなく、どのように図形を変換するか、あるいはその変換で何が変わらないかを調べることが大きな問題となります。
今日の記事も、群とその作用の様子、つまり双対性を利用することで、整数のある種の性質が理解できるというおはなしです。
先日とある事情*1によりGauss周期について調べているとき、
さんからGauss和とGauss周期はFourier変換になっているらしいと教えてもらいました。
（Gauss和やGauss周期についてはクロネッカー・ウェーバーの定理と証明のあらすじ（その１） - tsujimotterのノートブックをご覧いただくと雰囲気がわかると思います。この記事自体を読むのには特に必要ありません。）
それについてgoogleで検索したところ、"The Fourier Transform and Equations over Finite Abelian Groups"というタイトルのlecture note
http://people.cs.uchicago.edu/~laci/reu02/fourier.pdf
を見つけたので、その内容を簡単にご紹介しようと思います。
上の文献では方程式のmod pでの解の個数をFourier変換を用いて調べていて、例えば次のような事実を証明できます。
方程式 x^k + y^k = z^k mod pを考える。
p > k^4+3であれば、上の方程式はx, y, zが全てpの倍数でないような解を必ず持つ。
k=1の場合、問題の式は単なる1次方程式 x + y = z mod pです。
- p=2とすると、整数を2で割ったあまりは0または1ですが、この定理ではpの倍数でない解を探しているので、解の候補としては1のみです。x=y=1とするとx+y=2ですがp=2で割ったあまりは0なのでz=0となってしまい、条件にあいません。つまりp=2の場合は条件を満たす解はありません。
- p=3とすると、3で割ったあまりは0, 1, 2の3通りで解の候補としては1または2です。この場合にはx=y=1とするとx+y=2でz=2とすればこれが解になります。つまりp=3の場合には条件を満たす解があります。
- p=5とすると、5で割ったあまりは0, 1, 2, 3, 4の5通りで、解の候補としては1から4です。上と同じようにx=y=1, z=2とすればこれが解です。つまりp=5の場合には条件を満たす解があります。
p=7以上でも同様に解を持つことがわかり、k=1であればp>2で上の方程式は必ず解を持つことがわかります。
次にk=2の場合ですが、方程式としてはx^2 + y^2 = z^2 mod pを考えます。
- p=2とすると、x=y=1とするとz=0となってしまい、これは条件を満たしません。
- p=3とすると、解の候補は1, 2のどちらかです。これらの2乗を計算すると、1^2=1であり2^2=4ですがp=3で割ったあまりは4=1なのでいずれの場合にもx^2=1となってしまいます。つまりx^2, y^2, z^2の候補は1のみで、条件にあう解は存在しません。
- p=5の場合、上と同様に計算するとx^2, y^2, z^2の候補は1と4のみです。したがってこれも条件を満たす解が存在しないことがわかります。
- p=7の場合、x^2たちの候補は1, 4, 2の3種類です。この場合にはx=y=1, z=3とすればx^2 + y^2 = 2, z^2 = 3^2 = 9 = 2 mod 7となり、これが解であることがわかります。
- p=11の場合、x^2たちの候補は1, 4, 9, 5, 3の5種類です。この場合はx=2, y=4, z=3とすれば2^2+4^2=20=9 mod 11, 3^2=9ということでこれが解になります。
実はこの場合にもこれ以上のpで必ず解を持つことが簡単に証明できます。
k=3の場合、方程式としてはx^3 + y^3 = z^3 mod pを考えることになります。
- p=2ではこれまでと同様に解がありません。
- p=3では1^3=1, 2^3=8=2mod3なので、x=y=1, z=2が解です。
- p=5では1^3=1, 2^3=3, 3^3=2, 4^3=4 mod 5なので、x=y=1, z=3が解です。
- p=7ではx^3=1または6になります。したがってこの場合には解がありません。
- p=11ではx=1, y=2, z=4とするとx^3 + y^3 = 9, z^3 = 64 = 9 mod 11なのでこれが解です。
- p=13ではx^3=1, 8, 12, 5のいずれかで、この場合には解がありません。
この先コンピュータに計算させるとp=47までは解があることがわかりました。
k=4の場合もコンピュータに計算させると50以下の素数ではp=2,3,5,13,17,41以外では解があります。またk=5では50以下の素数ではp=2,11,41以外では解があるようです。
コードは特に何も考えてないループと、numpyを使って少し早くしてみたものです。
gist11cae6e6ba81db7b5d04b937febca4d2
上のコードでp<500の範囲を調べると、k=5ではp=71,101では解がない、k=6ではp=157, 257では解がないなどがわかります。
このように、kが大きくなると解が存在するか判別することが難しくなりますが、上の定理はどんなkであってもp>k^4+3であれば必ず解を持つということを主張しています。
さて、ここからは証明の方針をご紹介します。より詳しく知りたい方は、上記文献をお読みいただくか、こちらのpdf
math_pdf/gaussfourier.pdf at master · unaoya/math_pdf · GitHub
をごらんください。
より一般的な設定として、Z mod pの方程式 x + y + z = 0 とZ mod pの部分集合A, B, Cに対し、x, y, zがそれぞれA, B, Cの元であるような解の個数を調べます。
A, B, Cの全ての元を考えると x + y + z の値はZ mod pのp通りになるので、x + y + z = 0となるのは平均的にはA, B, Cの元の個数の積をpで割ったものになると期待できます。
この平均値と実際の解の個数の誤差を評価します。
解の個数は0に台を持つδ関数の値 δ(x+y+z) の総和として計算でき、δ関数のFourier係数が全て1であることからGの各指標χによる値 χ(x+y+z) を合計すればわかります。
自明指標の寄与が上の平均値であり、非自明指標の寄与が誤差項であることがわかり、これをA, B, Cの特性関数のFourier係数で評価することができます。
次にC = {z^k | z \in Z mod p}の場合を考えると、Cの特性関数のFourier係数はGauss和を用いて記述できます。Gauss和の大きさを計算することで具体的に誤差項の評価をすることができます。
以上のことを用いて、誤差項の上限が平均値より小さい条件を求めることができ、その条件を満たせば元の方程式が解を持つことがわかります。
mod pで方程式の解の個数を数えるという問題は、素朴でありながら数学の奥深さを垣間見せてくれる、非常に面白い問題です。
またコンピュータを使って色々実験することができるというのも、今を生きる我々ならではの数学の楽しみ方ですね。
このあたりの話については
数学とコンピュータ Advent Calendar 2017 - Qiita
でも書かせていただく予定ですので、よろしければそちらもご覧ください。
明日の日曜数学Advent Calendarはasangi_a4acさんの「中和滴定について書きます」です。お楽しみに。
*1:参考画像
