Eisenstein Primes¶

Let

$$ \omega=\frac{-1+i\sqrt3}{2},\qquad \omega^2+\omega+1=0. $$

The Eisenstein integers are $\mathbb Z[\omega]$. Their norm is

$$ N(a+b\omega) =(a+b\omega)(a+b\omega^2) =a^2-ab+b^2. $$

Enumerate one sector of the lattice¶

We again use unordered positive coordinate pairs from a finite patch. The six units and conjugation generate the symmetric copies in the remaining sectors of the triangular Eisenstein lattice.

def eisensteinPoints : [(Integer, Integer)] :=
  matchAll take 10 nats as set integer with
    | $x :: $y :: _ -> (x, y)

def eisensteinInteger (x : Integer) (y : Integer) : MathValue :=
  x + y * w

def eisensteinNorm (x : Integer) (y : Integer) : Integer :=
  x ^ 2 - x * y + y ^ 2

def eisensteinNorms : [(MathValue, Integer)] :=
  map
    (\(x, y) -> (eisensteinInteger x y, eisensteinNorm x y))
    eisensteinPoints

Check the defining relation and norm¶

The first component below is zero by $\omega^2+\omega+1=0$. The other entries show, for example, that $1+2\omega$ has norm $3$.

(w ^ 2 + w + 1, eisensteinNorm 1 2, take 10 eisensteinNorms)

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

Filter by prime norm¶

In the interior of this positive-coordinate sector, a prime integer norm certifies an Eisenstein prime. The norm-one element $1+\omega$ is a unit and is automatically excluded.

def eisensteinPrimes : [(MathValue, Integer)] :=
  filter (\(_, n) -> isPrime n) eisensteinNorms

take 24 eisensteinPrimes

$\{(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)\}$

Rational primes behave differently here¶

An ordinary prime $p\ne3$ splits in $\mathbb Z[\omega]$ when $p\equiv1\pmod3$ and remains prime when $p\equiv2\pmod3$. The ramified prime is

$$ 3=-\omega^2(1-\omega)^2. $$

Its basic factor has norm $3$.

((1 - w) * (1 - w ^ 2), eisensteinNorm 1 (-1))

$(3, 3)$

Takeaway¶

Replacing the square lattice by a triangular one changes the norm from $a^2+b^2$ to $a^2-ab+b^2$, but the computational idea is the same: enumerate algebraic integers structurally and transfer primality to exact arithmetic in $\mathbb Z$.