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

前回の記事から引き続き、代数曲線の $\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}$ のとき、平方剰余の第１補充則より

$\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}$