{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f665925d",
   "metadata": {},
   "source": [
    "# アイゼンシュタイン素数\n",
    "\n",
    "次のようにおきます。\n",
    "\n",
    "$$\n",
    "\\omega=\\frac{-1+i\\sqrt3}{2},\\qquad\n",
    "\\omega^2+\\omega+1=0.\n",
    "$$\n",
    "\n",
    "アイゼンシュタイン整数は $\\mathbb Z[\\omega]$ の元です。そのノルムは\n",
    "次のように表されます。\n",
    "\n",
    "$$\n",
    "N(a+b\\omega)\n",
    "  =(a+b\\omega)(a+b\\omega^2)\n",
    "  =a^2-ab+b^2.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebc4ae76",
   "metadata": {},
   "source": [
    "## 格子の一つの扇形領域を列挙する\n",
    "\n",
    "ここでも、有限領域から正の座標の順序を区別しない対を選びます。三角格子をなす\n",
    "アイゼンシュタイン整数の残りの扇形領域は、六つの単元と共役によってこの領域の\n",
    "対称なコピーとして得られます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "acce1602",
   "metadata": {},
   "outputs": [],
   "source": [
    "def eisensteinPoints : [(Integer, Integer)] :=\n",
    "  matchAll take 10 nats as set integer with\n",
    "    | $x :: $y :: _ -> (x, y)\n",
    "\n",
    "def eisensteinInteger (x : Integer) (y : Integer) : MathValue :=\n",
    "  x + y * w\n",
    "\n",
    "def eisensteinNorm (x : Integer) (y : Integer) : Integer :=\n",
    "  x ^ 2 - x * y + y ^ 2\n",
    "\n",
    "def eisensteinNorms : [(MathValue, Integer)] :=\n",
    "  map\n",
    "    (\\(x, y) -> (eisensteinInteger x y, eisensteinNorm x y))\n",
    "    eisensteinPoints\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5670036f",
   "metadata": {},
   "source": [
    "## 定義関係とノルムを確認する\n",
    "\n",
    "$\\omega^2+\\omega+1=0$ により、以下の出力の第1成分は0になります。\n",
    "ほかの成分からは、たとえば $1+2\\omega$ のノルムが $3$ であることを\n",
    "確認できます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0cd316dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(0, 3, \\{(w + 1, 1), (2 w + 1, 3), (w + 2, 3), (3 w + 1, 7), (2 w + 2, 4), (w + 3, 7), (4 w + 1, 13), (3 w + 2, 7), (2 w + 3, 7), (w + 4, 13)\\})$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(w ^ 2 + w + 1, eisensteinNorm 1 2, take 10 eisensteinNorms)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2b2794f",
   "metadata": {},
   "source": [
    "## 素数ノルムで絞り込む\n",
    "\n",
    "正の座標をもつこの扇形領域の内部では、整数として得られるノルムが素数ならば\n",
    "アイゼンシュタイン素数だと判定できます。ノルムが1の元 $1+\\omega$ は単元なので、\n",
    "自動的に除外されます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6c1deb81",
   "metadata": {},
   "outputs": [],
   "source": [
    "def eisensteinPrimes : [(MathValue, Integer)] :=\n",
    "  filter (\\(_, n) -> isPrime n) eisensteinNorms\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ef784b08",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$\\{(2 w + 1, 3), (w + 2, 3), (3 w + 1, 7), (w + 3, 7), (4 w + 1, 13), (3 w + 2, 7), (2 w + 3, 7), (w + 4, 13), (6 w + 1, 31), (5 w + 2, 19), (4 w + 3, 13), (3 w + 4, 13), (2 w + 5, 19), (w + 6, 31), (7 w + 1, 43), (5 w + 3, 19), (3 w + 5, 19), (w + 7, 43), (9 w + 1, 73), (7 w + 3, 37), (3 w + 7, 37), (w + 9, 73), (9 w + 2, 67), (7 w + 4, 37)\\}$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "take 24 eisensteinPrimes\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c4c3d8a",
   "metadata": {},
   "source": [
    "## 有理素数は異なる振る舞いをする\n",
    "\n",
    "通常の素数 $p\\ne3$ は、$\\mathbb Z[\\omega]$ において $p\\equiv1\\pmod3$ のとき\n",
    "分解し、$p\\equiv2\\pmod3$ のときは素数のままです。分岐する素数は3であり、\n",
    "次の分解をもちます。\n",
    "\n",
    "$$\n",
    "3=-\\omega^2(1-\\omega)^2.\n",
    "$$\n",
    "\n",
    "その基本因子のノルムは $3$ です。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "022d5128",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(3, 3)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "((1 - w) * (1 - w ^ 2), eisensteinNorm 1 (-1))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e574543d",
   "metadata": {},
   "source": [
    "## まとめ\n",
    "\n",
    "正方格子を三角格子に替えると、ノルムは $a^2+b^2$ から $a^2-ab+b^2$ へ\n",
    "変わりますが、計算の考え方は同じです。代数的整数を構造的に列挙し、素数判定を\n",
    "$\\mathbb Z$ 上の厳密な算術へ移します。\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
}