How does assuming GRH help us calculate class group?

Question

It seems that, almost all computer programs assume GRH to calculate $\mathbb{Q}(\zeta_p)$ for $p > 23$. I'm very curious how assuming the GRH, helps us to calculate class groups in practice. Can anyone give an explicit example of a number field (not necessarily $\mathbb{Q}(\zeta_p)$'s), and explicit calculation of the class group, based on assuming the GRH?

Answer 1

In general, to compute the class group of a number field $K$ of degree $n$ and discriminant $\Delta$, we need to find some bound $N$ such that the class group of $K$ is generated by primes of norm at most $N$. Unconditionally, we have the Minkowski bound $$M_K = \sqrt{\lvert \Delta \rvert} \left( \frac{4}{\pi} \right)^{s} \frac{n!}{n^n},$$ where $s$ is the number of conjugate pairs of complex places of $K$. Since $M_K$ is proportional to the square root of the absolute discriminant, it is often infeasible to check all primes up to that bound. To my knowledge, no sizable asymptotic improvement on this bound has been proven unconditionally.

However, assuming GRH, we have a vastly stronger bound due to Bach (1990): under GRH, the class group is generated by primes of norm at most $$B_K = 12 \log^2 \lvert \Delta \rvert.$$ A similar bound, asymptotically weaker in theory but stronger in practice for many fields of interest, is due to Belabas, Diaz y Diaz, and Friedman (2008).

Let's take $\mathbb{Q}(\zeta_{29})$ as an example: the Minkowski bound is $14956520729 \approx 1.4 \times 10^{10}$, so we would need to check about 64 million primes to provably compute the class group—not totally infeasible with supercomputers but certainly a very computationally intensive task. In contrast, the Bach bound is $99190$, while the version implemented in Magma using results of Belabas, Diaz y Diaz, and Friedman gives a bound of $826$. With this latter bound, Magma can compute the class group in $1.8$ seconds on my laptop, assuming there are no elements of the class group whose representatives all have norm greater than $826$ (the existence of which would contradict GRH).

References:

• Bach, E. “Explicit bounds for primality testing and related problems”. Mathematics of Computation 55 (1990), no. 191, pp. 355–380. [MR1023756]
• Belabas, K., Diaz y Diaz, F., and Friedman, E. “Small generators of the ideal class group”. Mathematics of Computation 77 (2008), no. 262, pp. 1185–1197. [MR2373197]