Math 582: computational number theory

Homework 5 -- due by Friday Feb 12 at 9am

Problem 3:

Explicitly run the Round 2 algorithm, using the code from class on Feb 5, to compute the ring of integers of a non-monogenic field (one whose ring of integers isn't generated by a single element), but starting with the order $\ZZ[\alpha]$ .

You can easily find such a field by Googling for nonmonogenic field.

R.<x> = QQ[]
K.<alpha> = NumberField(x^3 - x^2 - 2*x - 8) # Dedekind's example, see https://en.wikipedia.org/wiki/Monogenic_field
K.ring_of_integers().basis()

[1, 1/2*alpha^2 + 1/2*alpha, alpha^2]

# our startiong order
S = K.order(alpha) # it seems like ZZ[alpha] almost works...
S.discriminant().factor()

-1 * 2^2 * 503

# shows the only prime which S is not maximal at is 2.
# We only computed the discriminant of x^3 - x^2 - 2*x - 8
# so we aren't cheating here. Also it means we only have to
# run round 2 one time and we are garunteed to be done.

def consolelog(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()
    consolelog("n =", n)

    pj = ceil(log(n,p))
    consolelog("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
    consolelog("powers =", powers)

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

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

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

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

    return M*p + M.span(gens)
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
    consolelog("I_p has basis ", B)
    B2 = [S(b) for b in B]
    consolelog("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)
    consolelog("rows of matrix: ", rows)
    phi_matrix = matrix(GF(p), rows)
    return phi_matrix
def compute_U(S, p, I_p):
    mat = phi_bar(S, p, I_p)
    consolelog("the matrix is ", mat)

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

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

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

    return U
def compute_T_from_U(S, U, p):
    return K.order([K(b/p) for b in U.basis()])
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

T = compute_T(S,2)

n = 3
p^j = 2
powers = [1, alpha^2, 3*alpha^2 + 10*alpha + 8]
coords = [[1, 0, 0], [0, 0, 1], [8, 10, 3]]
matrix = [1 0 0]
[0 0 1]
[0 0 1]
Kernel = Vector space of degree 3 and dimension 1 over Finite Field of size 2
Basis matrix:
[0 1 1]
I_p has basis  [
(2, 0, 0),
(0, 1, 1),
(0, 0, 2)
]
Moving these elements into S for arithmetic:  [2, alpha^2 + alpha, 2*alpha^2]
rows of matrix:  [[1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 2, -1, 4, 2, 0, 8, 4, -1], [0, 0, 1, 8, 12, -4, 8, 20, -7]]
the matrix is  [1 0 0 0 1 0 0 0 1]
[0 0 1 0 0 0 0 0 1]
[0 0 1 0 0 0 0 0 1]
kernel  Vector space of degree 3 and dimension 1 over Finite Field of size 2
Basis matrix:
[0 1 1]
lift of kernel elements [(0, 1, 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 1 1]
[0 0 2]

T.basis()

[1, 1/2*alpha^2 + 1/2*alpha, alpha^2]

T == K.ring_of_integers()

True