Next: 7.3 Binary Quadratic Forms Up: 7 Quadratic fields Previous: 7.1 Prime ideals

## 7.2 Naive computation of the class group

As shown earlier, each element of the class group of the order R is represented by an invertible ideal J with Nm(J) ; here = if DR > 0 and = (2/pi) if DR < 0. Now, if is the image of J under the involution, then we have seen above (by writing J as a product of primes) that J . = NmJR. Thus the involution acts on the class group by group inversion (which is a group homomorphism for abelian groups!). In particular, we know how to represent inverses in this set of representatives.

From the above discussion we see that one natural set of generators is to pick one prime ideal Pp lying over each split prime p and for each ramified prime p. We only need to consider primes satisfying the criterion p ; let S denote the set of such primes. Now we need to write relations. Suppose that T is the (finite) set of all integers n such that (1) n is a multiple of elements of T (2) For each prime divisor p of n, n/p . Each such n can be written uniquely as the norm of an ideal Jn that is a product of the ideals Pp. If we find an element in Jn so that Nm() n . . , then = Jn . In, where Nm(In) . We can thus write a natural factorisation of the ideal in terms of Pp and Qp. Note that when n , the existence of such an is guaranteed by the lemma proved in the previous section. To write these relations, it is sufficient find all numbers less than max(T) which are products of primes in S and write these elements as norms.

Now suppose we have a relation Ppnp = R with np 0. If Nm() , then we can find a factor Ppmp which has norm n larger than , but lying in T. Then, we can replace the above relation by

. Ppnp - mp = (/)Nm(In)R

Now the left hand side has integral norm and so we have obtained another relation. Moreover, the norm of the left hand side is smaller than the earlier norm. Thus we can always reduce any relation to a product of relations of the type given above.

To write the relations associated with elements of T as above we note that for each n in T we can construct a candidate for as follows. First of all we use Chinese Remainder theorem to find an integer an so that an = ap(mod p) for every p dividing n (if necessary we can actually use Hensel's lemma to replace ap by the root of the equation modulo the maximal power of p that divides n). Then, elements of the form x + y are candidates where y is some number less than n and x is the reduction modulo n of an . y. In addition, we can impose the condition that x + y lies in a specified region in . K with volume n (this region is a rectangle in the case DR > 0 and a circle in the case DR < 0). These conditions make the search for effective.

Now the numbers in T could be just short of , so that the norm of could be just short of . This is in general too big a collection of relations to handle. One way to simplify the approach is to make reductions to the set S on the basis of relations found. Thus, if we find that Pp has order k based on relations already found then we do not consider numbers n that are divisible by powers of p larger than k - 1. Similarly, if we found a relation expression Pp in terms of smaller primes in the set S, then we can drop multiples of p from further choices for n in T. Finally, we can use a Class Number formula'' to give an estimate in terms of lower and upper bounds for the size of the group. Once we find a group that is the correct range then there are techniques to verify that there are no more relations to be considered.

Thus the techniques described above could be used to compute the class group even for large DR. However, the main aim of this section was to show the possibility of making the computation. We will need some more effective techniques to deal with finite abelian groups before we can make the computation more efficient.

As a demonstration we now compute the class group of the discriminant 257. The associated polynomial is T2 - T - 64. The initial candidates for the set S consist of the primes 16, i. e. the set {2, 3, 5, 7, 11, 13}. Now, the polynomial becomes T2 + T modulo 2 so that 2 is split so it is in S. Now we have

 257 2(mod 3) and 257 2(mod 5)

which shows that 3 and 5 are non-split and thus not in S. The squares modulo 7 are 1, 4 and 2, while 257 5(mod 7); thus 7 is not in S either. We also check that

 257 4 22(mod 11) and 257 10 62(mod 13)

so that 11 and 13 are in S. We then see easily that T is

{22 = 2 . 11, 26 = 2 . 13, 32 = 25, 121 = 112, 143 = 11 . 13, 169 = 132}

We now compute the relations in succession. We lift the above roots 0(mod 2) and 7(mod 11) (of the equation T2 - T - 64) to the root 18 - 4(mod 22). Thus a candidate for is + 4, which has norm 44 = 22 . 11. Thus we obtain the relation P22 . P11. Next we lift the roots 0 mod2 and 10 mod13 to the root 10 mod26. Thus a candidate for is - 10 which has norm 26 = 2 . 13. Thus we obtain the relation P2 . P13. Next we have = , which has norm 64 = 26, which gives the relation P26. Next, we lift (using Hensel's lemma) the root 7(mod 11) to the root 18(mod 121) which gives = - 18 which has norm 242 = 2 . 112 so we have a relation P2 . P112. Now, we could calculate further but we notice that this says that the class group is a quotient of a group of order 3 that is generated by P2. Since it is clear that this ideal is not principal, it follows that the class group in this case is /3. Note that we did not use the rectangular bounds for the sizes of in this computation since all the numbers were small'' in any case, but in general we would need to use these restrictions as well.

Next: 7.3 Binary Quadratic Forms Up: 7 Quadratic fields Previous: 7.1 Prime ideals
Kapil Hari Paranjape 2002-10-20