{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a5ea1ca4",
   "metadata": {},
   "source": [
    "# ガウス素数\n",
    "\n",
    "ガウス整数は次の集合です。\n",
    "\n",
    "$$\n",
    "\\mathbb Z[i]=\\{a+bi\\mid a,b\\in\\mathbb Z\\}.\n",
    "$$\n",
    "\n",
    "その乗法的ノルムは、次のように定義されます。\n",
    "\n",
    "$$\n",
    "N(a+bi)=(a+bi)(a-bi)=a^2+b^2.\n",
    "$$\n",
    "\n",
    "座標軸上にないガウス整数は、そのノルムが通常の素数であるとき、かつそのときに\n",
    "限りガウス素数です。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85b08d75",
   "metadata": {},
   "source": [
    "## 格子の有限領域を列挙する\n",
    "\n",
    "Egisonの集合マッチャーを使い、$\\{1,\\ldots,10\\}$ から順序を区別しない\n",
    "対を選びます。これにより一つの開象限を調べればよく、符号、共役、あるいは\n",
    "単元 $\\{\\pm1,\\pm i\\}$ の乗算から得られる対称な同伴元を列挙せずに済みます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8038fc6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gaussianPoints : [(Integer, Integer)] :=\n",
    "  matchAll take 10 nats as set integer with\n",
    "    | $x :: $y :: _ -> (x, y)\n",
    "\n",
    "def gaussianInteger (x : Integer) (y : Integer) : MathValue :=\n",
    "  x + y * i\n",
    "\n",
    "def gaussianNorm (x : Integer) (y : Integer) : Integer :=\n",
    "  x ^ 2 + y ^ 2\n",
    "\n",
    "def gaussianNorms : [(MathValue, Integer)] :=\n",
    "  map\n",
    "    (\\(x, y) -> (gaussianInteger x y, gaussianNorm x y))\n",
    "    gaussianPoints\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c6480af",
   "metadata": {},
   "source": [
    "## ノルムは通常の整数になる\n",
    "\n",
    "最初のいくつかの出力には、代数的整数とその厳密なノルムが並んでいます。\n",
    "たとえば、$N(1+i)=2$ である一方、$N(2+2i)=8$ です。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b7a00992",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$\\{(i + 1, 2), (2 i + 1, 5), (i + 2, 5), (3 i + 1, 10), (2 i + 2, 8), (i + 3, 10), (4 i + 1, 17), (3 i + 2, 13), (2 i + 3, 13), (i + 4, 17)\\}$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "take 10 gaussianNorms\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b64f8a87",
   "metadata": {},
   "source": [
    "## 素数ノルムで絞り込む\n",
    "\n",
    "この領域では二つの座標がともに0でないため、整数として得られるノルムの素数判定だけで\n",
    "十分です。座標軸上の素数については別の規則が必要で、通常の素数 $p$ が\n",
    "ガウス素数のままであるのは、$p\\equiv3\\pmod4$ のとき、かつそのときに限ります。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9384c2be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gaussianPrimes : [(MathValue, Integer)] :=\n",
    "  filter (\\(_, n) -> isPrime n) gaussianNorms\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1eea0c98",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$\\{(i + 1, 2), (2 i + 1, 5), (i + 2, 5), (4 i + 1, 17), (3 i + 2, 13), (2 i + 3, 13), (i + 4, 17), (6 i + 1, 37), (5 i + 2, 29), (2 i + 5, 29), (i + 6, 37), (7 i + 2, 53), (5 i + 4, 41), (4 i + 5, 41), (2 i + 7, 53), (10 i + 1, 101), (8 i + 3, 73), (6 i + 5, 61), (5 i + 6, 61), (3 i + 8, 73)\\}$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "take 20 gaussianPrimes\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abf8a2b6",
   "metadata": {},
   "source": [
    "## 一行で見る乗法性\n",
    "\n",
    "有理素数 $2$ は $\\mathbb Z[i]$ では素数ではありません。\n",
    "\n",
    "$$\n",
    "2=(1+i)(1-i).\n",
    "$$\n",
    "\n",
    "この式から、$1+i$ のノルムも読み取れます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1fa048bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(2, 2)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "((1 + i) * (1 - i), gaussianNorm 1 1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e3a8fad",
   "metadata": {},
   "source": [
    "## まとめ\n",
    "\n",
    "乗法的ノルムを通じて、二次元格子上の素数判定を通常の整数の判定へ還元できました。\n",
    "格子の列挙はEgisonのパターンマッチが担い、厳密な記号計算によって各ガウス整数を\n",
    "読みやすい形のまま扱えます。\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Egison",
   "language": "egison",
   "name": "egison"
  },
  "language_info": {
   "codemirror_mode": "egison",
   "file_extension": ".egi",
   "mimetype": "text/x-egison",
   "name": "egison"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}