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) $\leq$ $\delta_{R}^{}$; here $\delta_{R}^{}$ = $\sqrt{\vert D_R\vert}$ if D_R > 0 and $\delta_{R}^{}$ = (2/pi)$\sqrt{\vert D_R\vert}$ if D_R < 0. Now, if $\overline{J}$ is the image of J under the involution, then we have seen above (by writing J as a product of primes) that J ^. $\overline{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 P_p lying over each split prime p and for each ramified prime p. We only need to consider primes satisfying the criterion p $\leq$ $\delta_{R}^{}$; 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 $\leq$ $\delta_{R}^{}$. Each such n can be written uniquely as the norm of an ideal J_n that is a product of the ideals P_p. If we find an element $\alpha_{n}^{}$ in J_n so that Nm($\alpha_{n}^{}$) $\leq$ n ^. $\delta_{R}^{}$ ^. , then $\alpha_{n}^{}$ = J_n ^. I_n, where Nm(I_n) $\leq$ $\delta_{R}^{}$. We can thus write a natural factorisation of the ideal $\alpha_{n}^{}$ in terms of P_p and Q_p. Note that when n $\geq$ $\delta_{R}^{}$, the existence of such an $\alpha$ is guaranteed by the lemma proved in the previous section. To write these relations, it is sufficient find all numbers less than max(T)$\delta_{R}^{}$ which are products of primes in S and write these elements as norms.

Now suppose we have a relation $\prod_{p\in S}^{}$P_p^n_p = $\alpha$R with n_p $\geq$ 0. If Nm($\alpha$) $\geq$ $\delta_{R}^{}$, then we can find a factor $\prod_{p\in S}^{}$P_p^m_p which has norm n larger than $\delta_{R}^{}$, but lying in T. Then, we can replace the above relation by

$$\overline{I_n}$$ ^. $$\prod_{p\in S}^{}$$P_p^{n_p - m_p} = ($$\alpha$$/$$\alpha_{n}^{}$$)Nm(I_n)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 $\alpha_{n}^{}$ as follows. First of all we use Chinese Remainder theorem to find an integer a_n so that a_n = a_p(mod p) for every p dividing n (if necessary we can actually use Hensel's lemma to replace a_p by the root of the equation modulo the maximal power of p that divides n). Then, elements of the form x + y$\alpha$ are candidates where y is some number less than n and x is the reduction modulo n of a_n ^. y. In addition, we can impose the condition that x + y$\alpha$ lies in a specified region in $\mathbb {R}$ ^. K with volume n$\delta_{R}^{}$ (this region is a rectangle in the case D_R > 0 and a circle in the case D_R < 0). These conditions make the search for $\alpha_{n}^{}$ effective.

Now the numbers in T could be just short of $\delta_{R}^{2}$, so that the norm of $\alpha_{n}^{}$ could be just short of $\delta_{R}^{3}$. 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 P_p 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 P_p 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 D_R. 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 T² - T - 64. The initial candidates for the set S consist of the primes $\leq$ 16, i. e. the set {2, 3, 5, 7, 11, 13}. Now, the polynomial becomes T² + T modulo 2 so that 2 is split so it is in S. Now we have

$$\equiv \equiv$$ 257  and  257

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 $\equiv$ 5(mod 7); thus 7 is not in S either. We also check that

$$\equiv \equiv \equiv \equiv$$  and 

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

{22 = 2 ^. 11, 26 = 2 ^. 13, 32 = 2⁵, 121 = 11², 143 = 11 ^. 13, 169 = 13²}

We now compute the relations in succession. We lift the above roots 0(mod 2) and 7(mod 11) (of the equation T² - T - 64) to the root 18 $\equiv$ - 4(mod 22). Thus a candidate for $\alpha_{22}^{}$ is $\alpha$ + 4, which has norm 44 = 2^{2 .} 11. Thus we obtain the relation P₂^{2 .} P₁₁. Next we lift the roots 0 mod2 and 10 mod13 to the root 10 mod26. Thus a candidate for $\alpha_{26}^{}$ is $\alpha$ - 10 which has norm 26 = 2 ^. 13. Thus we obtain the relation P₂ ^. P₁₃. Next we have $\alpha_{32}^{}$ = $\alpha$, which has norm 64 = 2⁶, which gives the relation P₂⁶. Next, we lift (using Hensel's lemma) the root 7(mod 11) to the root 18(mod 121) which gives $\alpha_{121}^{}$ = $\alpha$ - 18 which has norm 242 = 2 ^. 11² so we have a relation P₂ ^. P₁₁². 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 P₂. Since it is clear that this ideal is not principal, it follows that the class group in this case is $\mathbb {Z}$/3$\mathbb {Z}$. Note that we did not use the rectangular bounds for the sizes of $\alpha_{n}^{}$ in this computation since all the numbers were ``small'' in any case, but in general we would need to use these restrictions as well.