2016-02-05-round2.sagews

Feb 5, 2016: An Algorithm to Compute the Ring of Integers (conclusion)

William Stein

Today we will finish discussing details about how to explicitly turn the theoretical discussion from Monday and Wednesday into an explicit algorithm to compute the ring $R$ of integers of $K$, noting that it gives an algorithm to compute a $p$-maximal order, and that is often all we need for certain question.

1. Recall -- here's what we did on Monday and Wednesday:

Given $K = \QQ(\alpha)$, where $\alpha$ is a root of the irreducible integral monic $f$, the ring $S=\ZZ[\alpha]$ is an order (=subring of full rank) in the ring $R$ of integers of $K$.

Given an order $S$ and a prime $p$, let $$T = \{x \in K : xI_p \subset I_p\},$$ where $I_p = \{ x \in S : x^m \in pS\text{ for some } m\geq 1\}$ is the $p$-radical of $S$.

Then we proved that $S \subset T \subset \frac{1}{p}S$ and $S=T$ if and only if $S$ is $p$-maximal.

We also proved that $T = \frac{1}{p}U$ where $$U = \ker(S \to \text{End}(I_p / p I_p)).$$

Our goal for today is to see how to compute $T$. To really understand everything you need to know about Hermite normal form, and basically develop the analogue of everything you do in a linear algebra course, but over $\ZZ$ instead of a field. We will not do all of that, due to lack of time.

2. Computing $I_p$.

Lemma (see Lemma 6.1.6 of Cohen GTM 138): If $p^j \geq [K:\QQ]$ then $I_p/ p I_p \subset S/pS$ is the kernel of $x\mapsto x^{p^j}$.

Proof: exercise.

So to compute $I_p$, we take a $\ZZ$-basis $b_1,\ldots, b_n$ of $S$, raise each of these $b_i$ to the power $p^j$ and write down the matrix of whose coefficients $a_{i,j}$ are such that $b_i^{p^j} = \sum a_{i,j} b_i$. Then reduce this matrix modulo $p$ and compute its kernel.

The result is a basis of $I_p / p I_p$.

Then $I_p$ is got by taking the $\ZZ$-submodule of $K$ generated by any lift of this basis together with $pS$.

Let's do it!

%auto
def log(s, args):
    print s, args

def p_radical(S, p):
    """
    INPUT:
       - S -- an order in a number field K (assumed to be an absolute number field!)
       - p -- a prime number

    OUTPUT: the p-radical of S.
    """
    K = S.number_field()
    n = K.degree()
    log("n =", n)

    pj = p
    while pj < n:
        pj *= p
    log("p^j =", pj)

    powers = [x^pj for x in S.basis()]  # this could be optimized by reducing each time -- would be the bottlekneck right now
    log("powers =", powers)

    M = S.free_module()
    coords = [M.coordinates(list(y)) for y in powers]
    log("coords =", coords)

    A = matrix(GF(p), n, coords)
    log("matrix =", A)

    gens = []
    V = A.kernel()
    log("Kernel =", V)

    for b in V.basis():
        gens.append(M.linear_combination_of_basis(b.lift()))

    return M*p + M.span(gens)

K.<a> = NumberField(x^3 - 4)
S = K.order([2*a])
S
S.basis()

Order in Number Field in a with defining polynomial x^3 - 4 [1, 2*a, 4*a^2]

p = 2
I_p = p_radical(S, p); Ip

n = 3 p^j = 4 powers = [1, 64*a, 4096*a^2] coords = [[1, 0, 0], [0, 32, 0], [0, 0, 1024]] matrix = [1 0 0] [0 0 0] [0 0 0] Kernel = Vector space of degree 3 and dimension 2 over Finite Field of size 2 Basis matrix: [0 1 0] [0 0 1]

Error in lines 2-2 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> NameError: name 'Ip' is not defined

3. Compute the kernel $U$

Now that we have an explicit basis for $I_p$ as a $\ZZ$-submodule of $S$, we move on to computing the kernel of $\phi: S \to \text{End}(I_p / p I_p)=M_{n\times n}(\FF_p)$ explicitly.

Since $pS$ goes to $0$, we instead compute the action of $S/pS$ on the $\FF_p$-vector subspace $\text{End}(I_p / p I_p)$, then lift and combine with a basis for $pS$ to get $U$. This is just like what we did above to go from a kernel to having the full $I_p$.

First, we compute the linear map $\bar{\phi} : S/pS \to \text{End}(I_p / p I_p)$ which is from an $\FF_p$ vector space of dimension $n$ to one of $n^2$, so represented by a matrix with $n^3$ entries. (Cohen's book says "Unfortunately, in the round 2 algorithm, it seems unavoidable to use such large matrices.")

%auto
def phi_bar(S, p, I_p):
    # For each basis element of S, see how it acts on I_p modulo p*I_p.
    B = I_p.basis()  # basis of a free module
    log("I_p has basis ", B)
    B2 = [S(b) for b in B]
    log("Moving these elements into S for arithmetic: ", B2)
    rows = []
    for g in S.gens():
        row = sum([I_p.coordinates(list(g*c)) for c in B2], [])
        rows.append(row)
    log("rows of matrix: ", rows)
    phi_matrix = matrix(GF(p), rows)
    return phi_matrix

m = phi_bar(S, p, I_p)
m

I_p has basis [ (2, 0, 0), (0, 2, 0), (0, 0, 4) ] Moving these elements into S for arithmetic: [2, 2*a, 4*a^2] rows of matrix: [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, 0, 0, 0, 1, 16, 0, 0], [0, 0, 2, 16, 0, 0, 0, 32, 0]] [1 0 0 0 1 0 0 0 1] [0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 0]

m.kernel()

Vector space of degree 3 and dimension 1 over Finite Field of size 2 Basis matrix: [0 0 1]

%auto
def compute_U(S, p, I_p):
    mat = phi_bar(S, p, I_p)
    log("the matrix is ", mat)

    V = mat.kernel()
    log("kernel ", V)

    M = S.free_module()
    gens = []
    for b in V.basis():
        gens.append(M.linear_combination_of_basis(b.lift()))
    log("lift of kernel elements", gens)

    U = M*p + M.span(gens)
    log("adding together with p*S yields", U)

    return U

U = compute_U(S, p, I_p)

I_p has basis [ (2, 0, 0), (0, 2, 0), (0, 0, 4) ] Moving these elements into S for arithmetic: [2, 2*a, 4*a^2] rows of matrix: [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, 0, 0, 0, 1, 16, 0, 0], [0, 0, 2, 16, 0, 0, 0, 32, 0]] the matrix is [1 0 0 0 1 0 0 0 1] [0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 0] kernel Vector space of degree 3 and dimension 1 over Finite Field of size 2 Basis matrix: [0 0 1] lift of kernel elements [(0, 0, 4)] adding together with p*S yields Free module of degree 3 and rank 3 over Integer Ring Echelon basis matrix: [2 0 0] [0 4 0] [0 0 4]

%auto
def compute_T_from_U(S, U, p):
    return K.order([K(b/p) for b in U.basis()])

T = compute_T_from(S, U, p)
T
T.basis()

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> NameError: name 'compute_T_from' is not defined

S.basis()

[1, 2*a, 4*a^2]

S.index_in(T)

2

4. Put it all together.

%auto
def compute_T(S, p):
    I_p = p_radical(S, p)
    U   = compute_U(S, p, I_p)
    T   = compute_T_from_U(S, U, p)
    return T

K.<a> = NumberField(x^3 - 4)
S = K.order([2*a])
S2 = compute_T(S, 2)

n = 3 p^j = 4 powers = [1, 64*a, 4096*a^2] coords = [[1, 0, 0], [0, 32, 0], [0, 0, 1024]] matrix = [1 0 0] [0 0 0] [0 0 0] Kernel = Vector space of degree 3 and dimension 2 over Finite Field of size 2 Basis matrix: [0 1 0] [0 0 1] I_p has basis [ (2, 0, 0), (0, 2, 0), (0, 0, 4) ] Moving these elements into S for arithmetic: [2, 2*a, 4*a^2] rows of matrix: [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, 0, 0, 0, 1, 16, 0, 0], [0, 0, 2, 16, 0, 0, 0, 32, 0]] the matrix is [1 0 0 0 1 0 0 0 1] [0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 0] kernel Vector space of degree 3 and dimension 1 over Finite Field of size 2 Basis matrix: [0 0 1] lift of kernel elements [(0, 0, 4)] adding together with p*S yields Free module of degree 3 and rank 3 over Integer Ring Echelon basis matrix: [2 0 0] [0 4 0] [0 0 4]

S.index_in(S2)

2

S3 = compute_T(S2, 2)
S3.basis()

n = 3 p^j = 4 powers = [1, 64*a, 256*a^2] coords = [[1, 0, 0], [0, 32, 0], [0, 0, 128]] matrix = [1 0 0] [0 0 0] [0 0 0] Kernel = Vector space of degree 3 and dimension 2 over Finite Field of size 2 Basis matrix: [0 1 0] [0 0 1] I_p has basis [ (2, 0, 0), (0, 2, 0), (0, 0, 2) ] Moving these elements into S for arithmetic: [2, 2*a, 2*a^2] rows of matrix: [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, 0, 0, 0, 2, 8, 0, 0], [0, 0, 2, 8, 0, 0, 0, 8, 0]] the matrix is [1 0 0 0 1 0 0 0 1] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] kernel Vector space of degree 3 and dimension 2 over Finite Field of size 2 Basis matrix: [0 1 0] [0 0 1] lift of kernel elements [(0, 2, 0), (0, 0, 2)] adding together with p*S yields Free module of degree 3 and rank 3 over Integer Ring Echelon basis matrix: [2 0 0] [0 2 0] [0 0 2] [1, a, a^2]

S2.index_in(S3)

4

S.index_in(S3)

8

S3.free_module() / S.free_module()

Finitely generated module V/W over Integer Ring with invariants (2, 4)

S4 = compute_T(S3, 2)
S4

n = 3 p^j = 4 powers = [1, 4*a, 16*a^2] coords = [[1, 0, 0], [0, 4, 0], [0, 0, 16]] matrix = [1 0 0] [0 0 0] [0 0 0] Kernel = Vector space of degree 3 and dimension 2 over Finite Field of size 2 Basis matrix: [0 1 0] [0 0 1] I_p has basis [ (2, 0, 0), (0, 1, 0), (0, 0, 1) ] Moving these elements into S for arithmetic: [2, a, a^2] rows of matrix: [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, 0, 0, 0, 1, 2, 0, 0], [0, 0, 2, 2, 0, 0, 0, 4, 0]] the matrix is [1 0 0 0 1 0 0 0 1] [0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 0] kernel Vector space of degree 3 and dimension 1 over Finite Field of size 2 Basis matrix: [0 0 1] lift of kernel elements [(0, 0, 1)] adding together with p*S yields Free module of degree 3 and rank 3 over Integer Ring Echelon basis matrix: [2 0 0] [0 2 0] [0 0 1] Order in Number Field in a with defining polynomial x^3 - 4

S3.index_in(S4)

2

S5 = compute_T(S4, 2)

n = 3 p^j = 4 powers = [1, 4*a, a^2] coords = [[1, 0, 0], [0, 4, 0], [0, 0, 2]] matrix = [1 0 0] [0 0 0] [0 0 0] Kernel = Vector space of degree 3 and dimension 2 over Finite Field of size 2 Basis matrix: [0 1 0] [0 0 1] I_p has basis [ (2, 0, 0), (0, 1, 0), (0, 0, 1/2) ] Moving these elements into S for arithmetic: [2, a, 1/2*a^2] rows of matrix: [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, 0, 0, 0, 2, 1, 0, 0], [0, 0, 2, 1, 0, 0, 0, 1, 0]] the matrix is [1 0 0 0 1 0 0 0 1] [0 0 0 0 0 0 1 0 0] [0 0 0 1 0 0 0 1 0] kernel Vector space of degree 3 and dimension 0 over Finite Field of size 2 Basis matrix: [] lift of kernel elements [] adding together with p*S yields Free module of degree 3 and rank 3 over Integer Ring Echelon basis matrix: [2 0 0] [0 2 0] [0 0 1]

S5.index_in(S4)

1

S

Order in Number Field in a with defining polynomial x^3 - 4

S2

Order in Number Field in a with defining polynomial x^3 - 4

S3

Order in Number Field in a with defining polynomial x^3 - 4

S4

Order in Number Field in a with defining polynomial x^3 - 4

S5

Order in Number Field in a with defining polynomial x^3 - 4