tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

有限体上の楕円曲線とヤコブスタール和

前回の記事から引き続き、代数曲線の \bmod{p} での解の個数 について思いを馳せたいと思います。

前回の記事はこちら:
tsujimotter.hatenablog.com

なお今回の内容は、前回の記事の内容をまったく読んでいなくても理解できる内容となっています。


今回は、 p を素数とし、有限体  \mathbb{F}_p = \{0, 1, 2, \ldots, p-1\} 上定義された楕円曲線

 E\colon  y^2 = f(x) ( f(x) は3次関数)

の解の個数  \#E(\mathbb{F}_p) について考えます。楕円曲線の仮定(非特異性)より  f(x) は重根を持たないとします。



具体例の計算

雰囲気を掴むために、少しだけ例を計算します。具体的には

 E\colon y^2 = f(x) = x^3 + x

として考えましょう。

 p = 5 としたとき、 x, y = 0, 1, \ldots, 4 のすべての組を代入すると

 0^2 = 0^3 + 0
 0^2 = 2^3 + 2
 0^2 = 3^3 + 3

が成り立ちます。それ以外の組み合わせでは、等号( \bmod{p} の合同のこと)は成り立ちません。

これに無限遠点  \mathcal{O} を加えたものが、 \mathbb{F}_5 上の楕円曲線  E の有理点です。よって

 E(\mathbb{F}_5) = \{ \mathcal{O}, \; (0, 0), \; (2, 0), \; (3, 0) \}

となります。したがって、 \#E(\mathbb{F}_5) = 4 ということになりますね。


ほかにもたとえば、 p = 7 のとき  x, y = 0, 1, \ldots, 6 のすべての組を代入すると

 0^2 = 0^3 + 0
 3^2 = 1^3 + 1
 4^2 = 1^3 + 1
 3^2 = 3^3 + 3
 4^2 = 3^3 + 3
 2^2 = 5^3 + 5
 5^2 = 5^3 + 5

が成り立ちます。他の組み合わせでは等号は成り立ちません。

無限遠点   \mathcal{O} と合わせて

 E(\mathbb{F}_7) = \{ \mathcal{O}, \; (0, 0), \; (1, 3), \; (1, 4), \; (3, 3), \;  (3, 4), \;  (5, 2), \; (5, 5) \}

となります。したがって、 \#E(\mathbb{F}_7) = 8 ということになりますね。

解の個数はだいたい p + 1 個

一般の  p について、ざっくりと解の個数  \#E(\mathbb{F}_p) を見積もることを考えましょう。

ある  x \in \mathbb{F}_p に対してあり得るパターンとしては、 f(x) = 0 となるか、 f(x) p の平方剰余となるか、平方非剰余となるかのいずれかとなります。

  •  f(x) = 0 のとき:

 y = 0 となるので、 (x, 0) が解となります。

  •  f(x) p の平方剰余のとき:

 y^2 = f(x) となるような  y が2つ( \pm y)存在します。よって  (x,  y) (x, -y) の2個が解となります。

  •  f(x) p の平方剰余のとき:

 y^2 = f(x) となるような  y は存在しません。


したがって、解の総数は

 \begin{align} \#E(\mathbb{F}_p) = & \;\;  1\times (f(x)=0\text{ となる }x\text{ の個数}) \\
&+ 2\times (f(x)\text{ が平方剰余である }x\text{ の個数}) \\
&+ 0\times (f(x)\text{ が平方非剰余である }x\text{ の個数}) \\
&+ (\text{無限遠点の個数}) \end{align}

ということになります。


ここでもし

 (f(x)\text{ が平方剰余である }x\text{ の個数}) \approx (f(x)\text{ が平方非剰余である }x\text{ の個数})

であれば、

 \#E(\mathbb{F}_p) \approx p + 1

となるわけです。
 f(x) が重根を持たない仮定により、 f(x) の解の個数が奇数になることを使っています。)

したがって、有限体上の楕円曲線の有理点の個数はだいたい  p+1 個というわけですね。

ヤコブスタール和

この時点でだいぶ面白いですが、もっと正確に見積もることができれば嬉しいですね。

 \# E(\mathbb{F}_p) (p+1) の誤差

 |\# E(\mathbb{F}_p) - (p+1)|

は、どのように評価できるでしょうか。実は、ヤコブスタール和を使ってこの誤差を完全に決定できる、というのが今日まさに紹介したい話です。


ルジャンドル記号を用いて

 \displaystyle 1 + \left(\frac{f(x)}{p}\right)

という値を考えると、

 \displaystyle 1 + \left(\frac{f(x)}{p}\right)  = \begin{cases} 1 & (f(x)=0) \\
2 & (f(x)\text{ は }p\text{ の平方剰余}) \\
0 & (f(x)\text{ は }p\text{ の平方非剰余})  \end{cases}

となります。ちゃんと個別の  x に対応する解の個数を表していますね。

したがって、解の総数は

 \displaystyle \begin{align} \#E(\mathbb{F}_p) &=  1 + \sum_{x=0}^{p-1} \left\{1 + \left(\frac{f(x)}{p}\right) \right\} \\
&=  p + 1 + \sum_{x=0}^{p-1} \left(\frac{f(x)}{p}\right) \end{align}

と表せることになります。


さて、ここで

 \displaystyle \sum_{x=0}^{p-1} \left(\frac{f(x)}{p}\right)

という和の値が決定できれば、解の個数が完全に決定できます。この和を ヤコブスタール和 といいます。

ヤコブスタール和は、以前の記事で紹介したことがありましたね。
tsujimotter.hatenablog.com


 E\colon y^2 = x^3 + x とヤコブスタール和

ここからは具体的な楕円曲線

 E\colon y^2 = f(x) = x^3 + x

を想定して、より具体的に解の個数をカウントすることを考えましょう。

なお、今回の話はより一般に
 E\colon y^2 = x^3 + Dx

という形の楕円曲線に適用できる話になっています。分かりやすさのために  D = 1 のケースで考えたいと思います。

このようにするとヤコブスタール和は

 \displaystyle \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right)

となります。ちょうど、前節の記事における  S(1) を計算することになります。


実は、前節の記事でやったこと、すなわち「 p = a^2 + b^2 をヤコブスタール和を使って具体的に書き下す」を逆に使うと、まさに今回の問題である解の個数を決定できるのです! これがすごく面白いので紹介しましょう。



 p \equiv 1 \pmod{4} のとき、フェルマーの2平方和定理 により

 p = a^2 + b^2

となるような整数  a, \; b の存在が保証されます。ここで  p は奇数なので、 a, b のいずれかは奇数ですが、 a は奇数で  b は偶数とします。 a\equiv 1 \pmod{4} となるようにとると、  a は一意的に定めることができます。

このとき、ヤコブスタール和  \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right) の値は

 \displaystyle \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right) = -2a

となるというのが、上の記事で示したことです。

注釈:
正確にいえば、上で示したことは  \pm 2a または  \pm 2b であることですが、p = 4n+1 のヤコブスタール和の合同式(この合同式は「素数と2次体の整数論」の問題5.55に載っています)
 \displaystyle \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right) \equiv - \binom{2n}{n} \pmod{p}

と、

 \displaystyle \binom{2n}{n} \equiv 2a \pmod{p}
(これはガウスによる定理ですが、たとえばこれ https://dalspace.library.dal.ca/bitstream/handle/10222/47610/Al-Shaghay-Abdullah-MSc-MATH-March-2014.pdf?sequence=1 のTheorem 1.1に主張が書いてあります)

を考えると、合同式

 \displaystyle \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right) \equiv - 2a \pmod{p}

が得られます。あとは両辺の値の取りうる範囲を考えることで、等式として  -2a が確定するようです。


したがって、楕円曲線  E\colon y^2 = x^3 + x の解の個数は、 p = a^2 + b^2, \; a \equiv 1 \pmod{4} と表したとき

 \# E(\mathbb{F}_p) =  p + 1  - 2a

と表せるということです。これは面白いですね!!


実際、冒頭の  p = 5 の具体例について考えてみると、 5 = 1^2 + 2^2 ですから  a = 1 です。これにより

 \# E(\mathbb{F}_5) = 5 + 1 - 2\cdot 1 = 4

となり、たしかに計算した結果と一致していますね。


その他の  p \equiv 1 \pmod{4} でも計算してみると、次のようになります:

 p \#E(\mathbb{F}_p) \#E(\mathbb{F}_p) - (p+1) a
 5 4 -2 1
 13 20 6 -3
 17 16 -2 1
 29 20 -10 5
 37 36 -2 1
 41 32 -10 5
 53 68 14 -7
 61 52 -10 5
 73 80 6 -3
 89 80 -10 5
 97 80 -18 9
 101 100 -2 1
 109 116 6 -3
 113 128 14 -7
 137 160 22 -11
 149 164 14 -7
 157 180 22 -11
 173 148 -26 13
 181 164 -18 9
 193 208 14 -7
 197 196 -2 1

たしかに、 \#E(\mathbb{F}_p) - (p+1) = -2a になっていることがわかりますね。


前回の記事でも、上と似たような結果を示していましたね。
tsujimotter.hatenablog.com

前回の記事は、 x^4 + y^4 + 1 = 0 の解の個数でしたが、今回は  y^2 = x^3 + x の解の個数です。しかし、今回はヤコブスタール和の性質があらかじめ分かっていたので、ずいぶんあっさりと求めることができました。


ここで、 p = a^2 + b^2 \geq a^2 なので  \sqrt{p} \geq |a| が成り立ちます。したがって、 \# E(\mathbb{F}_p) (p+1) の誤差の評価は

 |\# E(\mathbb{F}_p) - (p+1) | \leq 2 \sqrt{p}

と表すことができます。これはまさに 楕円曲線のハッセの定理 そのものですね!
tsujimotter.hatenablog.com


こんな風に、具体的な楕円曲線  E\colon y^2 = x^3 + x については、ヤコブスタール和を用いてハッセの定理を導くことができてしまうのです。すごいですね。

p = 4n+3 型の場合

ところで、 p \equiv 3 \pmod{4} のケースをやっていませんでしたが、この場合のヤコブスタール和は

 \displaystyle \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right) = 0

となります。

これは次のように示すことができます:

 p \equiv 3 \pmod{4} のとき、平方剰余の第1補充則より
 \displaystyle \left(\frac{-1}{p}\right)  = -1

である。これを使うと、以下のようにヤコブスタール和が計算できる:

 \displaystyle \begin{align} \sum_{x = 0}^{p-1} \left(\frac{x^3 + x}{p}\right) &= \sum_{x = 1}^{\frac{p-1}{2}} \left(\frac{x^3 + x}{p}\right) + \sum_{x = 1}^{\frac{p-1}{2}} \left(\frac{(-x)^3 + (-x)}{p}\right) \\
&= \sum_{x = 1}^{\frac{p-1}{2}} \left(\frac{x^3 + x}{p}\right) + \sum_{x = 1}^{\frac{p-1}{2}} \left(\frac{-1}{p}\right) \left(\frac{x^3 + x}{p}\right) \\
&= \sum_{x = 1}^{\frac{p-1}{2}} \left(\frac{x^3 + x}{p}\right) - \sum_{x = 1}^{\frac{p-1}{2}}  \left(\frac{x^3 + x}{p}\right) \\
&= 0
\end{align}

したがって、 p \equiv 3 \pmod{4} のときは

 \# E(\mathbb{F}_p) = p + 1

が成り立っています。

こっちの場合は、誤差が一切ないというわけなんですね!( p = 7 の具体例でも確かにそうでした。)


これもしかして「虚数乗法を持つ楕円曲線の場合、 \#E(\mathbb{F}_p) - (p+1)は半分の  p で 0 になる」という話に関係するのかな!?

実際、 E\colon y^2 = x^3 + x は、 \mathbb{Z}[\sqrt{-1}] に虚数乗法を持つ楕円曲線の具体例となっています。いろんな知識が繋がって楽しいですね!


面白くなってきたところですが、私の(現時点での)理解の最前線に到達しましたので、この辺りで筆を置くことにしましょう。

それでは、今日はこの辺で!


参考文献

今回の話は、木村巌先生のブログの「Jacobsthal和」シリーズの内容に影響を受けて書いています。大変勉強になりました。
iwaokimura.blogspot.com


また、最近ちょうど「ゆるにじたい(「素数と2次体の整数論」の勉強会)」にて、ヤコブスタール和の話に差し掛かりまして、その関係でヤコブスタール和に興味を持って調べていました。

素数と2次体の整数論 (数学のかんどころ 15)

素数と2次体の整数論 (数学のかんどころ 15)

  • 作者:青木 昇
  • 発売日: 2012/12/21
  • メディア: 単行本


まだちゃんと読めていませんが、関連する内容が以下の本にも載っていたかと思います。

探検! 数の密林・数論の迷宮

探検! 数の密林・数論の迷宮


楕円曲線の個数がだいたい  p+1 個になるという話は、下記の本の「第4章 有限体上の3次曲線」の冒頭部分に載っていました。

楕円曲線論入門

楕円曲線論入門


「虚数乗法を持つ楕円曲線の場合、 \#E(\mathbb{F}_p) - (p+1)は半分の  p で 0 になる」という話は、たしか下記の本の第4章で見た記憶があります。

ガロアとガロア理論 (MATH+)

ガロアとガロア理論 (MATH+)