{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f665925d",
   "metadata": {},
   "source": [
    "# Eisenstein Primes\n",
    "\n",
    "Let\n",
    "\n",
    "$$\n",
    "\\omega=\\frac{-1+i\\sqrt3}{2},\\qquad\n",
    "\\omega^2+\\omega+1=0.\n",
    "$$\n",
    "\n",
    "The Eisenstein integers are $\\mathbb Z[\\omega]$. Their norm is\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": [
    "## Enumerate one sector of the lattice\n",
    "\n",
    "We again use unordered positive coordinate pairs from a finite\n",
    "patch. The six units and conjugation generate the symmetric copies\n",
    "in the remaining sectors of the triangular Eisenstein lattice.\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": [
    "## Check the defining relation and norm\n",
    "\n",
    "The first component below is zero by\n",
    "$\\omega^2+\\omega+1=0$. The other entries show, for example, that\n",
    "$1+2\\omega$ has norm $3$.\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": [
    "## Filter by prime norm\n",
    "\n",
    "In the interior of this positive-coordinate sector, a prime integer\n",
    "norm certifies an Eisenstein prime. The norm-one element\n",
    "$1+\\omega$ is a unit and is automatically excluded.\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": [
    "## Rational primes behave differently here\n",
    "\n",
    "An ordinary prime $p\\ne3$ splits in $\\mathbb Z[\\omega]$ when\n",
    "$p\\equiv1\\pmod3$ and remains prime when $p\\equiv2\\pmod3$.\n",
    "The ramified prime is\n",
    "\n",
    "$$\n",
    "3=-\\omega^2(1-\\omega)^2.\n",
    "$$\n",
    "\n",
    "Its basic factor has norm $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": [
    "## Takeaway\n",
    "\n",
    "Replacing the square lattice by a triangular one changes the norm\n",
    "from $a^2+b^2$ to $a^2-ab+b^2$, but the computational idea is the\n",
    "same: enumerate algebraic integers structurally and transfer\n",
    "primality to exact arithmetic in $\\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
}