名前のない定理

マニアックな数学

大学では教えてくれない数学　ガウス和とガウステーブル3

第一回
box-white.hatenablog.com
前回
box-white.hatenablog.com

前回の内容をおさらいしておきましょう.

pを3で割って1余る素数p = 3n+1とし,gをpの原始根とする.pの0以外の剰余を次の3つのグループに分ける.

グループA:gの指数が3で割れるもの.g^0 , g^3 , g^6 \cdots
グループB:gの指数が3で割って1余るもの.g^1,g^4,g^7,\cdots
グループC:gの指数が3で割って2余るもの.g^2,g^5,g^8,\cdots

グループAの数に1を足すと再びグループAの数になるような剰余の個数を(AA),
グループAの数に1を足すとグループBの数になるような剰余の個数を(AB),
などと表わし,これらを3かける3の行列に並べたものを「ガウステーブル」と名付けた.

ガウステーブルは4つの自然数s,t,u,vを用いて
\begin{pmatrix} s & t & u \\ t & u & v \\ u & v & t \end{pmatrix}
と書ける.さらにs = v-1

前回得られた定理は次のようなものでした.
a = 3(v-t) -1 , b = 3(u-v) + 1とすると,p = a^2 + ab + b^2.

今回はここから始めましょう.今回の目標は次の定理になります.
定理1:pを3で割って1余る素数とする.p = 3n + 1このとき整数a,bが存在してp = a^2 + ab + b^2となるが,これは二項係数\binom{2n}{n}から計算することができる.
定理2:P_{1}を\binom{2n}{n}の法pに関する絶対最小剰余とすると,12p - 3P_{1}^2は平方数となる.

前回u,v,tからa,bを求めましたが,今度は逆にp = a^2 + ab + b^2となる自然数が分かっている状態で
u,v,tをa,bで表示する方法を考えていきます.
\begin{eqnarray} \left \{ \begin{array}{l} 3v-3t - 1 = a \\ 3u - 3v + 1 = b \\ v + t + u = n \\ \end{array} \right. \end{eqnarray}
となります.最後の等式はガウステーブルの第二行の総和がグループBに属する剰余の個数と等しいことに由来します.
この連立方程式を解くと
\begin{eqnarray} \left \{ \begin{array}{l} 9t = 3n-1 - 2a - b \\ 9u = 3n-1+a + 2b \\ 9v = 3n + 2 + a-b \\ \end{array} \right. \end{eqnarray}
となります.

ここで次の補題を証明しましょう.
補題1:
(i)
kがp-1の倍数でないならば,
\begin{eqnarray} \sum_{x = 1}^{p-1} x^k \equiv 0 \pmod{p} \end{eqnarray}
(ii)
kがp-1の倍数ならば,
\begin{eqnarray} \sum_{x = 1}^{p-1} x^k \equiv -1 \pmod{p} \end{eqnarray}
証明:(i)左辺を原始根で表示すると
\begin{eqnarray} \sum_{c = 0}^{p-2} g^{ck} \end{eqnarray}
となる.等比級数の公式から
\begin{eqnarray} (g^k -1) (\sum_{c=0}^{p-2}g^{ck}) \equiv g^{(p-1)k}-1 \pmod{p} \end{eqnarray}
となるが,gが原始根,kがp-1の倍数でないので(g^k-1) \not \equiv 0 \pmod{p}.
g^{p-1} \equiv 1 \pmod{p}であるので,右辺は0.従って総和が0と合同であることが分かった.

(ii)フェルマーの小定理から1 \leq x \leq p-1に対してx^{p-1} \equiv 1.それゆえ各項は1と合同.ゆえに
\begin{eqnarray} \sum_{x = 1}^{p-1} x^k \equiv p-1 \equiv -1 \pmod{p} \end{eqnarray}
が言えた.

次の和の剰余を二通りに計算します.
\begin{eqnarray} S_{1} = \sum_{x=1}^{p-1}(x^3 + 1)^{n} \end{eqnarray}
まず補題1を用いるとx^{3n}の項と定数項以外はすべて\equiv 0 \pmod{p}であり,その二つは\equiv -1 \pmod{p}なので
S_{1} \equiv -2 \pmod{p}であることが分かります.

今\omega \equiv g^n \pmod{p}で\omegaを定義すると,各項(x^3 + 1)^nは1,\omega,\omega^2のいずれかになることが分かります.それがいつ起こるのかを考えると,x^3 + 1がグループA,B,Cに属するとき,それぞれ1,\omega,\omega^2になることに気づけます.x^3は必ずグループAの数です.自然数dに対して合同方程式x^3 \equiv g^{3d} \pmod{p}は必ず3つの非合同な解を持ちます.これらを統合するとx^3 + 1が1,\omega,\omega^2と合同になるxの個数はそれぞれ3(AA),3(AB),3(AC)と等しくなります.ゆえにS_{1} \equiv 3(AA) + 3 \omega (AB) + 3 \omega^2 (AC)
この二つを等置して-2 \equiv 3(AA) + 3\omega (AB) + 3 \omega^2(AC)

\begin{eqnarray} S_{2} = \sum_{x=1}^{p-1}(x^3 + 1)^{2n} \end{eqnarray}
についても同様に-2 - \binom{2n}{n} \equiv 3(AA) + 3\omega^2(AB) + 3 \omega(AC)を導くことができます.

s,t,uを用いてこの状況を整理すると
\begin{eqnarray} \left \{ \begin{array}{l} s + \omega t + \omega^2 u \equiv -2 \\ s + \omega^2 t + \omega u \equiv -2 - \binom{2n}{n} \\ s + t + u \equiv n-1\\ \end{array} \right. \end{eqnarray}
となります.\binom{2n}{n} \equiv P_{1}とします.a,bをs,t,uに代入するとa \equiv (\omega-1)P_{1}/3 , b \equiv (\omega +2)P_{1}/3 \pmod{p}となります.ここからb-a \equiv P_{1}\pmod{p}となります.

補題2:p \geq 32ならば|a| < \frac{p}{4} , |b| < \frac{p}{4}.
証明:a^2 + ab + b^2 = \dfrac{1}{2}a^2 + \dfrac{1}{2}(a+b)^2 + \dfrac{1}{2}b^2 = pから\dfrac{1}{2}a^2 < p.またp \geq 32ならば2p \leq \left( \dfrac{p}{4} \right)^2.ゆえにa^2 < \left(\dfrac{p}{4} \right)^2から補題が示せた.

補題2からp \geq 32のとき,b-aは< \dfrac{p}{2}であり,それゆえP_{1}を絶対最小剰余とすると,b = a + P_{1}になります.これをa^2 + ab + b^2 = pに代入して二次方程式を解くと
a = \dfrac{1}{6}( -3 P_{1} \pm \sqrt{12p - 3P_{1}^2}) , b = a + P_{1}となります.

これで「定理1:pを3で割って1余る素数とする.p = 3n + 1このとき整数a,bが存在してp = a^2 + ab + b^2となるが,これは二項係数\binom{2n}{n}から計算することができる.」がp \geq 32のとき証明できました.\sqrt{12p - 3 P_{1}^2}は整数でなければならないので「定理2:P_{1}を\binom{2n}{n}の法pに関する絶対最小剰余とすると,12p - 3P_{1}^2は平方数となる.」も証明できました.p < 32のときは個別にこれらが成立することが示せてこれですべての3で割って1余る素数に対しての証明が完了しました.

次回
box-white.hatenablog.com