ガウス素数¶
ガウス整数は次の集合です。
$$ \mathbb Z[i]=\{a+bi\mid a,b\in\mathbb Z\}. $$
その乗法的ノルムは、次のように定義されます。
$$ N(a+bi)=(a+bi)(a-bi)=a^2+b^2. $$
座標軸上にないガウス整数は、そのノルムが通常の素数であるとき、かつそのときに 限りガウス素数です。
格子の有限領域を列挙する¶
Egisonの集合マッチャーを使い、$\{1,\ldots,10\}$ から順序を区別しない 対を選びます。これにより一つの開象限を調べればよく、符号、共役、あるいは 単元 $\{\pm1,\pm i\}$ の乗算から得られる対称な同伴元を列挙せずに済みます。
def gaussianPoints : [(Integer, Integer)] :=
matchAll take 10 nats as set integer with
| $x :: $y :: _ -> (x, y)
def gaussianInteger (x : Integer) (y : Integer) : MathValue :=
x + y * i
def gaussianNorm (x : Integer) (y : Integer) : Integer :=
x ^ 2 + y ^ 2
def gaussianNorms : [(MathValue, Integer)] :=
map
(\(x, y) -> (gaussianInteger x y, gaussianNorm x y))
gaussianPoints
ノルムは通常の整数になる¶
最初のいくつかの出力には、代数的整数とその厳密なノルムが並んでいます。 たとえば、$N(1+i)=2$ である一方、$N(2+2i)=8$ です。
take 10 gaussianNorms
素数ノルムで絞り込む¶
この領域では二つの座標がともに0でないため、整数として得られるノルムの素数判定だけで 十分です。座標軸上の素数については別の規則が必要で、通常の素数 $p$ が ガウス素数のままであるのは、$p\equiv3\pmod4$ のとき、かつそのときに限ります。
def gaussianPrimes : [(MathValue, Integer)] :=
filter (\(_, n) -> isPrime n) gaussianNorms
take 20 gaussianPrimes
((1 + i) * (1 - i), gaussianNorm 1 1)
まとめ¶
乗法的ノルムを通じて、二次元格子上の素数判定を通常の整数の判定へ還元できました。 格子の列挙はEgisonのパターンマッチが担い、厳密な記号計算によって各ガウス整数を 読みやすい形のまま扱えます。