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?
GRH – How Assuming GRH Helps Calculate Class Group
algebraic-number-theorynt.number-theory
Related Solutions
Suppose you have a diophantine problem whose solution is connected with the structure of the p-class group of a number field K. Then you have the following options:
- Use ideal arithmetic in the maximal order OK
- Replace OK by a suitable ring of S-integers with trivial p-class group
- Replace K by the Hilbert class field, which (perhaps) has trivial p-class group.
Experience with descent on elliptic curves has shown me that ultimately, the equations you have to solve in methods 1 and 2 are the same; moreover, the approach using ideals is a lot less technical than using factorial domains in S-integers (the class group relations come back in through the larger rank of the group of S-units). I am certain that the route via the Hilbert class field is even more technical: again, the unit group in the class field will produce more difficulties than a trivial class group will eliminate.
Edit. As an example illustrating my point in a very simple example, let me solve the diophantine equation $x^2 + 5y^2 = z^2$ in several different ways. I will always assume that $\gcd(x,y) = 1$.
1. Elementary Number Theory
The basic idea is factoring: from $5y^2 = (z+x)(z-x)$. Since $d = \gcd(z-x,z+x) = \gcd(2z,z+x) \mid 2$ we have $d = 1$ or $d = 2$; moreover we clearly have $z-x > 0$. This gives $z+x = da^2$, $z-x = 5db^2$ or $z+x = 5da^2$, $z-x = db^2$. Solving for $x$ and $z$ yields $$ x = \pm \frac d2 (a^2 - 5b^2), \quad y = dab. $$
2. Parametrization
Set $X = \frac xz$ and $Y = \frac yz$; then $X^2 + 5Y^2 = 1$. Take the line $Y = t(X+1)$ through the obvious point $(-1,0)$; the second point of intersection is given by $$ X = \frac{1-5t^2}{1+5t^2}, \quad Y = \frac{2t}{1+5t^2}. $$ Dehomogenizing using $t = \frac ba$ and $X = \frac xz$ etc. gives the projective parametrization $$ (x:y:z) = (a^2-5b^2:2ab:a^2+5b^2). $$ If $ab$ is odd, all coordinates are even, and we find $$ x = \frac12(a^2 - 5b^2), \quad y = ab; $$ if $a$ or $b$ is even we get $$ x = a^2 - 5b^2, \quad y = 2ab $$ as above.
3. Algebraic Number Theory
Consider the factorization $$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$ in the ring of integers of the number field $K = {\mathbb Q}(\sqrt{-5}\,)$. The class number of $K$ is $2$, and the ideal class is generated by the prime ideal ${\mathfrak p} = (2,1+\sqrt{-5}\,)$.
The ideal $(x + y\sqrt{-5}, x - y\sqrt{-5}\,)$ is either $(1)$ or ${\mathfrak p}$; thus $$ (x + y\sqrt{-5}\,) = {\mathfrak a}^2, \quad (x - y\sqrt{-5}\,) = {\mathfrak b}^2 $$ in the first and $$ (x + y\sqrt{-5}\,) = {\mathfrak p}{\mathfrak a}^2, \quad (x - y\sqrt{-5}\,) = {\mathfrak p}{\mathfrak b}^2 $$ in the second case.
The second case is impossible since the left hand side as well as ${\mathfrak a}^2$ are principal, but ${\mathfrak p}$ is not. We could have seen this immediately since $x$ and $y$ cannot both be odd.
In the first case, assume first that ${\mathfrak a} = (a + b\sqrt{-5}\,)$ is principal. Since the only units in ${\mathcal O}_K$ are $\pm 1$, this gives $x + y \sqrt{-5} = \pm(a+b\sqrt{-5}\,)^2$ and hence $$ x = \pm (a^2 - 5b^2), \quad y = \pm 2ab. $$ If ${\mathfrak a}$ is not principal, then ${\mathfrak p}{\mathfrak a} = (a+b\sqrt{-5}\,)$ is, and from $({\mathfrak p}{\mathfrak a})^2 = 2(x+y\sqrt{-5}\,)$ we similarly get $$ x = \pm \frac12(a^2 - 5b^2), \quad y = \pm ab. $$
4. S-Integers
The ring $R = {\mathbb Z}[\sqrt{-5}\,]$ is not a UFD, but $S = R[\frac12]$ is; in fact, $S$ is even norm-Euclidean for the usual norm in $S$ (the norm is the same as in $R$ except that powers of $2$ are dropped). It is also easily seen that $S^\times = \langle -1, 2 \rangle$. From $$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$ and the fact that the factors on the left hand side are coprime we deduce that $x + y\sqrt{-5} = \varepsilon \alpha^2$ for some unit $\varepsilon \in S^\times$ and some $\alpha \in S$. Subsuming squares into $\alpha$ we may assume that $\varepsilon \in \{\pm 1, \pm 2\}$. Setting $\alpha = \frac{a + b\sqrt{-5}}{2^t}$, where we may assume that $a$ and $b$ are not both even, we get $$ x + y \sqrt{-5} = \varepsilon \frac{a^2 - 5b^2 + 2ab\sqrt{-5}}{2^{2t}}. $$ It is easily seen that we must have $t = 0$ and $\varepsilon = \pm 1$ or $t = 1$ and $\varepsilon = \pm 2$; a simple calculation then yields the same formulas as above.
5. Hilbert Class Fields
The Hilbert class field of $K$ is given by $L = K(i)$. It is not too difficult to show that $L$ has class number $1$ (actually it is norm-Euclidean), and that its unit group is generated by $i = \sqrt{-1}$ and $\omega = \frac{1+\sqrt{5}}2$ (we only need to know that these units and their product are not squares). From $$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$ and the fact that the factors on the left hand side are coprime in ${\mathcal O}_K$ we deduce that $x + y \sqrt{-5} = \varepsilon \alpha^2$. Subsuming squares into $\alpha^2$ we may assume that $\varepsilon \in \{1, i, \omega, i\omega \}$. Applying the nontrivial automorphism of $L/K$ to $x + y \sqrt{-5} = \varepsilon \alpha^2$ we find $\varepsilon \alpha^2 = \varepsilon' {\alpha'}^2$. Since the ideal ${\mathfrak a} = (\alpha)$ is fixed and since $L/K$ is unramified, the ideal ${\mathfrak a}$ must be an ideal in ${\mathcal O}_K$. Thus either ${\mathfrak a} = (a+b\sqrt{-5}\,)$ is principal in $K$, or ${\mathfrak p} {\mathfrak a} = (a+b\sqrt{-5}\,)$ is; in the second case we observe that ${\mathfrak p} = (1+i)$ becomes principal in ${\mathcal O}_L$.
Thus either $$ x + y \sqrt{-5} = (a+b\sqrt{-5}\,)^2 \quad \text{or} \quad x + y \sqrt{-5} = i \Big(\frac{a+b\sqrt{-5}}{1+i}\,\Big)^2, $$ giving us the same formulas as above.
Avoiding ideal arithmetic in $K$ and only using the fact that ${\mathcal O}_L$ is a UFD seems to complicate the proof even more.
Edit 2 For good measure . . .
6. Hilbert 90
Consider, as above, the equation $X^2 + 5Y^2 = 1$. It shows that the element $X + Y \sqrt{-5}$ has norm $1$; by Hilbert 90, we must have $$ X + Y \sqrt{-5} = \frac{a+b\sqrt{-5}}{a-b\sqrt{-5}} = \frac{a^2 - 5b^2 + 2ab\sqrt{-5}}{a^2 + 5b^2}. $$ Dehomogenizing via $X = \frac xz$ and $Y = \frac yz$ yields the same projective parametrization as above, and we end up with the familiar formulas.
7. Binary Quadratic Forms The equation $x^2 + 5y^2 = z^2$ tells us that the form $Q_0(X,Y) = X^2 + 5Y^2$ with fundamental discriminant $\Delta = -20$ represents a square; this implies that $Q_0$ lies in the principal genus (which is trivial since $Q_0$ is the principal form), and that the representations of $z^2$ by $Q_0$ come from composing representations of $z$ by forms $Q_1$ with $Q_1^2 \sim Q_0$ with themselves.
There are only two forms with discriminant $\Delta$ whose square is equivalent to $Q_0$: the principal form $Q_0$ itself and the form $Q_1(X,Y) = 2X^2 + 2XY + 3Y^2$. Thus either $$ z = Q_0(a,b) = a^2 + 5b^2 \quad \text{or} \quad z = Q_1(a,b) = 2a^2 + 2ab + 3b^2. $$ The formulas for Gauss composition of forms immediately provide us with expressions for $x$ and $y$ in terms of $a$ and $b$, but they can also be checked easily by hand. In the first case, we get $$ x^2 + 5y^2 = (a^2 + 5b^2)^2 = (a^2 - 5b^2)^2 + 5(2ab)^2, $$ and in the second case we can reduce the equations to this one by observing that $2Q_1(a,b) = A^2 + 5b^2$ with $A = 2a+b$, which gives $$ x^2 + 5y^2 = \frac14\Big(A^2 + 5b^2\Big)^2 = \Big(\frac{A^2 - 5b^2}2\Big)^2 + 5(Ab)^2. $$
If I recall it correctly, the class number of the real cyclotomic field comes from its cubic subfield. Thus you might as well ask whether there is a connection between class numbers of quadratic fields ${\mathbb Q}(\sqrt{-p})$ and real cubic fields with prime conductor $p$ for primes $p \equiv 7 \bmod 12$. What little we know about class numbers comes either from analytic objects (zeta functions, class number formulas), class field theory, or elliptic curves. Since we are talking about abelian extensions of the rationals, I would expect an explanation for such a result to come from class field theory. But nothing I know could even be remotely responsible for such a relation. Indeed the only results that might be within reach would be "independence" results claiming that there are infinitely many fields for which one class number is divisible by a certain prime but the other is not.
The problem why there are so few relations between the two objects has to do with the fact that the compositum of the two fields is a cyclic sextic field, which only has two nontrivial subfields. The units of these subfields do not generate a group of finite index in the whole unit group, which for me means that we should not expect any relation between the class numbers of these objects.
On the other hand you never know; the class number $1$ for the quadratic field is connected with continued fraction expansions (see Zagier's book on quadratic fields and forms) - but real cubic cyclic fields seem to have preciously little to do with continued fractions.
Best Answer
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: