6
$\begingroup$

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the discriminant, I guess.)

This would also be of interest in special cases like fields with a given degree or signature. The simplest one would be the family of imaginary quadratic fields: in this setting there is Swan's algorithm (which actually computes reduced bases for all ideals of least norms in their class), which takes (I think) at most $m^3$ steps to do $\mathbb{Q}(\sqrt{-m})$ when implemented without more thought. Is there a better algorithm known, or is there a speedy implementation of Swan's algorithm?

$\endgroup$
2
  • $\begingroup$ Here is an open question I have wondered about: What is an upper complexity bound for the calculation of the class number of a cyclotomic field of conductor $m$? Since the degrees of these fields differ, currently known results are not yet able to address this problem. $\endgroup$ Nov 3, 2013 at 2:55
  • $\begingroup$ This sounds nice; you should probably ask it as a separate question since the focus here (for me at least, and it seems for the papers linked in the answers also) was on fields with bounded degree (also, a new question has probably a better chance to be aswered, and will be more useful when answered, than a comment on an old question). $\endgroup$ Nov 4, 2013 at 10:39

4 Answers 4

6
$\begingroup$

In the case of quadratic fields there is a very nice paper of Andy Booker (see http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01850-3/home.html ) which uses the Burgess bounds on character sums (among other ideas) to compute the class number. The running time is always $O(D^{1/2+\epsilon})$ and if the GRH is true then the algorithm executes in time $O(D^{1/4+\epsilon})$. I think this is the best that is known. If one wants all class numbers up to a point then there are other clever algorithms based on the trace formula for doing this (see work of Jacobson, Ramachandran and Williams; Springer Lecture notes in CS vol 4076).

Note: As Edgardo observes there are faster randomized algorithms, and also earlier algorithms that rely on GRH (either running in heuristically subexponential time, or in time $D^{1/4+\epsilon}$). But these use GRH in an essential way in that the algorithm halts only if GRH is true. A subtle difference in Booker's algorithm is that it is guaranteed to halt; only the analysis of how long it takes to halt depends on GRH.

$\endgroup$
2
  • $\begingroup$ Great answer for this special case, thanks! It should be noted that the algorithm computes the class-number alone (using analytic number theory) without using a basis or an enumeration for the class-group (contrary to those in Igor Rivin and Matt Young's answers). $\endgroup$ Oct 30, 2013 at 9:42
  • $\begingroup$ Also, the liked paper by Booker contains reference to the (conditional) sub-exponential algorithm mentioned in the (somewhat cryptic) answer by Edgardo below. $\endgroup$ Oct 31, 2013 at 8:50
2
$\begingroup$

J. Buchmann and M. Pohst in a 1989 paper show that the class group can be computed in time of order $D^{1+\epsilon},$ where $D$ is the discriminant.

$\endgroup$
1
  • $\begingroup$ Thanks! I guess this answer the question pretty well; I'll wait to see if anybody has anything else to contribute before accepting it since the formulation of my question was pretty open. A few remarks on the algorithm for those who don't want to have to go to the likned paper: it computes a basis for the class-group, and then computes the order of each of its elements. It uses the order generated by the powers of a root (if this is the whole integer ring then it is OK, otherwise they rely on some other work by Pohst and H. Zassenhaus). $\endgroup$ Oct 29, 2013 at 17:20
2
$\begingroup$

In the special case of an imaginary quadratic field of discriminant $-D$, one can use reduction theory to compute the class number in around $D^{1/2}$ steps. Computing the class number boils down to counting binary quadratic forms $ax^2 + bxy + cy^2$ with $a \geq 1$, $b^2 - 4ac = -D$, and $|b| \leq a \leq c$. In particular, this means $4ac = b^2 + D \leq ac + D$, so $ac \leq D/3$, and so $a \leq \sqrt{D/3}$. For each $a$, given its prime factorization, it is easy to quickly check if $b^2 \equiv D \pmod{4a}$ is solvable, and find all $b$'s that solve this quadratic congruence. Then given $b$ and $a$, we find $c$ by $c = (b^2+D)/(4a)$. The problem of getting the prime factorization of $a$ is not a problem since we want to do this for each $a \leq \sqrt{D/3}$. It is easy to get the prime factorizations of all $a$'s at once by the sieve of Eratosthenes. I believe this method takes at most $D^{1/2} \log^C D$ steps for some small $C$.

$\endgroup$
1
  • $\begingroup$ Thanks! I believe this is the algorithm given in H. Cohen's book (where I should have looked before asking...). It feels like it should be optimal if you want to get reduced bases for the (minimal norm) ideal classes in addition. $\endgroup$ Oct 30, 2013 at 9:45
2
$\begingroup$

Index calculus works, and much faster (although it is randomized); search for "subexponential class group".

$\endgroup$
1
  • 5
    $\begingroup$ Any chance that this answer can be made more informative or explanatory? $\endgroup$
    – Todd Trimble
    Oct 29, 2013 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.