2021-06-28-114737.sagews

Press open to interact with this worksheet.

Once in interactive mode, use the mouse to click or highlight a block. Then use the "run" button on top or "shift + enter" to execute the block.

To make a new block click on one of the horizontal bars. Here you can add Sage code or type in comments.

In the following worksheet we demonstrate how to compute the class group of a quadratic field as well as decompose ideals over a set of generators for the class group.

# In the following, consider the quadratic field with fundamental discriminant -1363.
D = -1363
K = QuadraticField(D)
K

Number Field in a with defining polynomial x^2 + 1363 with a = 36.91882988394947?*I

# Ideal classes of O_K can be represented with reduced quadratic forms of discriminant -1363.

f = BinaryQF([7, 3, 49])
f.is_reduced()
f.discriminant()    # verify the form has the right discriminant

True -1363

# Composition of forms is denoted by multiplication, but the result is not necessarily reduced.

f*f
(f*f).reduced_form()

49*x^2 + 3*x*y + 7*y^2 7*x^2 - 3*x*y + 49*y^2

# If f = (a, b, c) is a reduced form, then its inverse is (a, -b, c)

g = BinaryQF([7, -3, 49])
g.is_reduced()

I = f*g
I.reduced_form()

True x^2 + x*y + 341*y^2

# The split prime ideals of K with norm less than Minkowski's bound generate the class group of K.
B = floor(K.minkowski_bound())
B

23

Q1. What are the ramified primes of K? Why do we not need to consider them when computing the class group?

Q2. What is the ideal class of an inert prime? Why do we not need to consider them when computing the class group?

# We can construct the forms corresponding to reduced prime ideals. This is the prime form above 7, with its conjugate given by its inverse.

p = 7
R = Integers(2*p)

a = p
b = int(sqrt(R(D)))        # square root of D mod 7
c = (b^2 - D)/(4*a)

f = BinaryQF([a, b, c])
f = f.reduced_form()
f

f.discriminant()

7*x^2 + 3*x*y + 49*y^2 -1363

Q4. Find the binary quadratic forms f1, f2, ..., fn corresponding to the split prime ideals with norm less than B.

# We now need relations of the form f1^x1 * f2^x2 * ... * fn^xn = I = (1, 1, 341).
# Since exponentiation of forms is not natively supported here is a (not efficient) function to help:

id = BinaryQF([1, 1, 341])

def inv(f):
    g = f.reduced_form()
    return BinaryQF([g[0], -g[1], g[2]]).reduced_form()

def ex(f, n):
    g = id
    for i in range(abs(n)):
        g *= f
    g = g.reduced_form()
    if n < 0:
        g = inv(g)
    return g

inv(f)
ex(f, 2) == (f * f).reduced_form()

7*x^2 - 3*x*y + 49*y^2 True

Q5. Write a function that generates n random numbers in [-10, 10]. Look for relations of the form f1^x1 * f2^x2 * ... * fn^xn = I = (1, 1, 341).

# Here is a simple example of working with matrices in Sage, especially adding rows to a matrix:

M = matrix([[1, 2, 4], [5, 4, 1], [2, 4, 3]])

rows = M.rows()
rows += [(5, 6, 7)]

matrix(rows)

[1 2 4] [5 4 1] [2 4 3] [5 6 7]

Q6. Construct the matrix with row vectors given by (x1, x2, ..., xn). Continue searching for relations as in Q3 until the matrix has full rank.

# Recall that the Hermite normal form of this matrix gives the structure of the class group of K.
# We can create the (upper triangular!) HNF by:

M.hermite_form()
print()

# and the Smith normal form by:

M.smith_form()

[1 2 4] [0 6 4] [0 0 5] ([ 1 0 0] [ 0 1 0] [ 0 0 30], [ 0 0 1] [ 0 1 0] [ 1 -25 -13], [ 3 7 8] [ -5 -11 -13] [ 5 10 12])

Q7. What is the structure of the class group? (Hint: the class number is less than 12. If you still aren't there, try adding more relations.)

Q8. Find elements of each possible order in the class group (hint: see page 3 of lecture 7).

Q9. Decompose the quadratic form (7, 3, 49) over the generators of the class group (hint: can be solved by inspection).

Q10. The class group is cyclic, so from Q8 we should have one generator of order equal to the class number, call it g. For the prime forms f above 7, 11, and 19, solve the discrete log problem f = g^x.