Factorisation in number fields, some examples

Agnese Gini -- November 16, 2020.

Any non zero element $a\in \mathbb Z$ can be uniquely written as product of a unite $u$ and finite number of irriducible elements $q_1,\dots,q_n$.

SAGE function $\tt factor$ returns the factorisation over the integers, using by defalt PARI library.

In [38]:
print fa
-1 * 2^3 * 3 * 13

Informally, if we consider extensions of $\mathbb Z$, this fact is no longer true. Indeed, for example in $\mathbb Z[\sqrt{13}]$ we have $$-12=(1+\sqrt{13})(1-\sqrt{13})=-1\cdot 2\cdot 2\cdot 3.$$

The reason is that $\mathbb Z[\sqrt{13}]$ is not a factorial ring, and in some sense this ring is not the correct choice for working with $x=\sqrt{13}$.

Let $\mathbf K$ be any number field, as $\mathbf Q (\sqrt{13})$. It is not true that any order in $\bf K$ is a factorial ring. However, the maximal order $\mathcal O_\mathbf{K}$ is always a Dedekind domain. By SAGE we can compute the ring $\mathcal O_\mathbf{K}$.

In [39]:
K.<t> = QuadraticField(13)
In [40]:
[1/2*t + 1/2, t]

Notice that in our example we have that $\mathbb Z[\sqrt{13}]$ is strictly contained in $\mathcal O_\mathbf{K}$.

In Dedekind domains it is natural to consider prime ideals rather than elements. More precisely, it is possible to prove that any non zero ideal $I<\mathcal O_\mathbf{K}$ can be uniquely (up to order) written as product of prime ideals: $$ I=P_1\cdots P_k.$$

Let us consider two examples showing different behaviours.

Example 1.a

Let us consider the number field $\mathbf Q(a)$ defined by a root of $f(x)=x^3-3x-1$.

In [41]:
A.<x> = QQ[]
In [42]:
F.<a> = NumberField(f)
OF = F.ring_of_integers()
[1, a, a^2]
In [43]:

Notice that in this case $\mathcal O_\mathbf{F}={\bf Z}[a]$. Now, we want to factor the ideals $I=(10)=10\mathcal O_\mathbf{F}$ and $J=(12)=12\mathcal O_\mathbf{F}$. Using the factorisation method implemented in SAGE we obtain the following:

In [44]:
I = OF.ideal(10)
(Fractional ideal (2)) * (Fractional ideal (5))
In [45]:
J = OF.ideal(12)
(Fractional ideal (2))^2 * (Fractional ideal (-a^2 + 1))^3

Example 2.a

Let us consider the number field $\mathbf E=\mathbf Q(b)$ defined by a root of $g(x)=x^4+77$.

In [46]:
A.<x> = QQ[]
In [47]:
E.<b> = NumberField(g)
OE = E.ring_of_integers()
[1, b, b^2, b^3]
In [48]:

$\mathcal O_\mathbf{E}={\bf Z}[b]$. Now, we want to factor the ideals $I=(10)=10\mathcal O_\mathbf{E}$ and $J=(12)=12\mathcal O_\mathbf{E}$. Using SAGE, we obtain the following:

In [49]:
I = E.fractional_ideal(10)
(Fractional ideal (2, b + 1))^4 * (Fractional ideal (5))
In [50]:
J = E.fractional_ideal(12)
(Fractional ideal (2, b + 1))^8 * (Fractional ideal (3, b^2 + 1)) * (Fractional ideal (3, b + 1)) * (Fractional ideal (3, b - 1))


Let us comment these two examples. The extensions of the primes $2$ and $5$ are primes in the ring of integers of $\bf F$, namely $2$ and $5$ are inert. This implies that from the factorisation of 10 in $\bf Z$, we could directly obtain the factorisation of $I$, and partially the factorisation of $J$.

Instead, in the ring of integers of $\bf E$ the extensions of $2$ is not prime; while $5$ is inert in $\bf E$, too. Those primes who do not generate prime ideals have different decompositions, i.e. $3{\cal O_{\bf F}}$ and $2{\cal O_{\bf E}}$ ramify completely and $3{\cal O_{\bf E}}$ is product of tree distinct primes, two with inertia degree one and one with inertia degree two.

These examples show that studying the decomposition of extensions of primes $p{\cal O}_K$ is particularly interesting. Thus, in the following section we discuss the problem of factoring ideals of the form $p{\cal O}_K$ for $p\in \bf Z$.

Finally, notice that in the first example we actually obtained the (unique) factorisation of 10 and 12 as elements: $$10=2\cdot 5 ~\text{and} ~12 =2^2\cdot (-a^2 + 1)^3.$$ Indeed, ${\cal O_{\bf F}}$ is an unique factorization domain. To verify this statement we can compute the class group via SAGE. Recall that being UFD for ring of integers is equivalent to be principal ideal domain and to have trivial class group.

In [51]:
Class group of order 1 of Number Field in a with defining polynomial x^3 - 3*x - 1

Notice that computing the Minkowski bound was actually sufficient, since it is 2 and we already observed that 2 is inert in $\bf F$.

In [52]:


Factoring $p{\cal O}_F$

Let $\bf F$ be a number field and $\alpha \in {\cal O}_{\bf F}$ be such that $\mathbf F=\mathbf Q(\alpha)$. The index of $\alpha$ is defined as $ ind(\alpha)=| {\cal O}_{\bf F}/ \mathbb Z[\alpha]| $.This value characterizes when it is possible to factor $p{\cal O}_{\bf F}$ by just computing the factorisation of a polynomial over ${\mathbb F}_p$.

${\bf Theorem ~ 1 ~(Kummer):}$ Let $f\in \mathbf Z[x]$ be the minimal polynomial of $\alpha$ over $\bf Z$ and suppose $p\not\mid ind(\alpha)$. Let be $$ \bar f = \prod_{j=1}^k\bar f_j^{e_j} \in {\mathbb F}_p[x]$$ the factorisation in monic irreducible polynomials, and define $P_j=(p,f_j(\alpha))$ where $f_j$ is any lift of $\bar f_j$ to $\mathbf Z[x]$. Then $$p{\cal O}_{\bf F}=\prod_{j=1}^kP_j^{e_j}. $$

Example 1.b

For the field $\bf F$ of Example 1.a, we have that $\mathcal O_\mathbf{F}={\bf Z}[a]$. Therefore, since $ind(a)=1$ any prime can be factored using ${\bf Theorem ~ 1}$. Now, we explicit the factorisation of the first part of the example.

In [53]:
R2.<y> = PolynomialRing(GF(2))
y^3 + y + 1
In [54]:
R5.<y> = PolynomialRing(GF(5))
y^3 + 2*y + 4

For $p=2,5$ the polynomial is irreducible, then $2\mathcal O_\mathbf{F}$ and $5\mathcal O_\mathbf{F}$ are prime.

In [55]:
R3.<y> = PolynomialRing(GF(3))
(y + 2)^3

Instead, $f$ is product of linear factors modulo 3. This implies that $3\mathcal O_\mathbf{F}=(3,\alpha+2)^3=(1-\alpha^2)^3$.

Example 2.b

For the field $\bf E$ of Example 2.a, we have that $\mathcal O_\mathbf{E}={\bf Z}[b]$. Therefore, since $ind(b)=1$ any prime can be factored using ${\bf Theorem ~ 1}$. Now, we explicit the factorisation of the first part of the example.

In [56]:
R2.<y> = PolynomialRing(GF(2))
(y + 1)^4

Then $2\mathcal O_\mathbf{E}=(2,b+1)^4$.

In [57]:
R3.<y> = PolynomialRing(GF(3))
(y + 1) * (y + 2) * (y^2 + 1)

Then $3\mathcal O_\mathbf{E}=(3,b+1)(3,b+2)(3,b^2+1)$.

In [58]:
R5.<y> = PolynomialRing(GF(5))
y^4 + 2

Then $5\mathcal O_\mathbf{E}$ is prime.


Kummer's Theorem is not always applicable. Indeed, there exist number fields whose index is greater than 1. A famous example (Dedekind) is $\mathbf F=\mathbf Q(\alpha)$ where the minimal polynomial of $\alpha$ is $f(x)=x^3 + x^2 - 2x + 8$. It is possible to prove that for each $b\in \mathcal O_\mathbf{F}$ $ind(b)=0\mod 2$. This implies that $2\mathcal O_\mathbf{F}$ can not be factored via the above strategy. However, there exists a general decomposition method due to Buchman and H.W. Lenstra.

The $\textbf {Buchmann-Lenstra}$ algorithm is quite technical, and fully described in Cohen's book, $\textit{A course in computational algebraic number theory}$, at chapter 6. The main idea is to compute first a square free decomposition of the ideal $$p\mathcal O_F=\prod_{j=1}^s H_j^j \;\;\text{ where }\;\; H_j=\prod_{e_i=j}Q_i,$$ then using that quotients $\mathcal O_F/H_j$ are separable finite algebras over $\mathbb F_p$, one can recover the primes over $H_j$. Although it may seem complicated, this algorithm has some effective aspects, such as it is possible to perform certain operations $\mod p\mathcal O_\mathbf{F}$, namely on a $ \mathbb F_p$ vector space. In addition, it is possible to prove that it is not necessary to compute the maximal order, as it is sufficient to consider a $p$-maximal order $\cal O$, $i.e.$ $p\not\mid[\mathcal O_\mathbf{F}\colon \mathcal O]$.

Now, we apply the algorithm "by hand" in order to factor the ideal $2\mathcal O_\mathbf{F}$ in the Dedekind example. Even though we will not need all the steps of the algorithm, this is a pretty explanatory example.

Example 3

In [59]:
A.<x> = QQ[]
In [60]:
F.<a> = NumberField(f)
OF = F.ring_of_integers()
B=OF.basis(); B
[1, 1/2*a^2 + 1/2*a, a^2]
In [61]:
I = F.fractional_ideal(2); I
Fractional ideal (2)

We have to compute $I_2=\sqrt{2\mathcal O_\mathbf{F}}$ the $\it 2-radical$. Thus, the nilradical of $\mathcal O_\mathbf{F}/2\mathcal O_\mathbf{F}$ is kernel of the map $t\mapsto t^4$, since $2^2\ge 3=[\mathbf F\colon \mathbf Q] $.

In [62]:
[I.reduce(s^4) for s in B] 
[1, 1/2*a^2 + 1/2*a, a^2]

This tells us that the fourth power map is the identity over $\mathcal O_\mathbf{F}/2\mathcal O_\mathbf{F}$. Then we have that $I_2=2\mathcal O_\mathbf{F}$, hence $2\mathcal O_\mathbf{F}$ is square free. This implies that $A=\mathcal O_\mathbf{F}/2\mathcal O_\mathbf{F}$ is a separable finite algebra over $\mathbb F_2$.

We can easly determine the number of factors $k$ of $2{\cal O}_{\bf F}$. Indeed, $k$ is the dimension of fixed by the frobenius map, namely the kernel of the map $$\begin{matrix}\psi\colon &A&\rightarrow & A\\& t&\mapsto&t^p-t\end{matrix}$$ which is the number of possible embedding of ${\mathbb F_p}$ in $A$ ($p=2$). Notice that $k=1$ would mean that the algebra is irreducible, namely the ideal be prime.

In [63]:
[I.reduce(s^2-s) for s in B]
[0, 0, 0]

In this case $\ker\psi=A$, this implies that $2{\cal O}_{\bf F}$ has 3 factors. Hence, it splits completely over $\bf F$.

Now, we recursively decompose our ideal. Since $A$ is not a field, it must contain a non trivial idempotent, i.e. $e\in A $ such that $e^2=e$ and $e\ne0,1$. Therefore, setting $ J_1=( 2,e) $ and $ J_2=( 2,1-e) $ we have the non trivial decomposition $2{\cal O}_{\bf F}=J_1J_2$.

In general, we can find such $e$ in the kernel of $t\mapsto t^2-t$. In this case, the characteristic is $p=2$, so this map is actually $\psi$. Therefore, we can take $e=a^2$.

In [64]:
J1=F.fractional_ideal(a^2,2); J1
Fractional ideal (a^2 + 2*a - 2)
In [65]:
J2=F.fractional_ideal(2,1+a^2); J2
Fractional ideal (-a^2 + 2*a - 3)
In [66]:

Now, we iterate this decomposition strategy on $J_1$ and $J_2$.

${\cal O}_{\bf F}/J_i\simeq({\cal O}_{\bf F}/2{\cal O}_{\bf F})/(J_i/2{\cal O}_{\bf F})$, then we can use the function $\tt quotient\_char\_p$. This function takes as input an ideal $J$ contained in a $p{\cal O}_{\bf F}$ and return the quotient vector space $V=({\cal O}_{\bf F} \mod p)/(J_i\mod p)$, the homorphism $r\colon {\cal O}_{\bf F}\rightarrow V$ and the section $s\colon V\rightarrow {\cal O}_{\bf F}$.

In [67]:
from sage.rings.number_field.number_field_ideal import quotient_char_p
V1,r1,s1=quotient_char_p(J1, 2); V1
Vector space quotient V/W of dimension 2 over Finite Field of size 2 where
V: Vector space of dimension 3 over Finite Field of size 2
W: Vector space of degree 3 and dimension 1 over Finite Field of size 2
Basis matrix:
[0 0 1]

The dimension of ${\cal O}_{\bf F}/ J_1$ is 2, then $J_1$ can be further decomposed. The class of $b=(a^2 + a)/2$ is not trivial in ${\cal O}_{\bf F}/ J_1$, and clearly $b$ is idempotent.

In [68]:
1/2*a^2 + 1/2*a

Then, we set $J_{11}=J_1+b{\cal O}_{\bf F}$ and $J_{12}=J_1+(1-b){\cal O}_{\bf F}$.

In [69]:
J11=F.fractional_ideal(b)+J1; J11
Fractional ideal (-3/2*a^2 + 5/2*a - 4)
In [70]:
J12=F.fractional_ideal(1-b)+J1; J12
Fractional ideal (1/2*a^2 - 1/2*a + 1)
In [71]:

Here, we could actually end the example becuse we know $k=3$. For the sake of completeness, we make some other computations to verify our result.

First, we check that ${\cal O}_{\bf F}/J_2$ is a field. We have different possibilities, like computing the quotient as before or ask directly SAGE.

In [72]:
from sage.rings.number_field.number_field_ideal import quotient_char_p
V2,r2,s2=quotient_char_p(J2, 2); V2
Vector space quotient V/W of dimension 1 over Finite Field of size 2 where
V: Vector space of dimension 3 over Finite Field of size 2
W: Vector space of degree 3 and dimension 2 over Finite Field of size 2
Basis matrix:
[1 0 1]
[0 1 1]
In [73]:

Finally, we can compare our result with the output of the function $\tt factor$.

In [74]:
(Fractional ideal (1/2*a^2 - 1/2*a + 1)) * (Fractional ideal (-a^2 + 2*a - 3)) * (Fractional ideal (-3/2*a^2 + 5/2*a - 4))

$\bf Remark:$ We proved that ${\cal O}_{\bf F}$ splits completely. This also shows that Kummer strategy was impractical. Indeed, there are not three distinct linear polynomials in $\mathbb F_2[x]$.