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?

Improve this question
$\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$
    – graduate student
    Commented 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$
    – Jean Raimbault
    Commented Nov 4, 2013 at 10:39

4 Answers 4

Reset to default
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.

Improve this answer
$\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$
    – Jean Raimbault
    Commented 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$
    – Jean Raimbault
    Commented 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.

Improve this answer
$\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$
    – Jean Raimbault
    Commented 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$.

Improve this answer
$\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$
    – Jean Raimbault
    Commented Oct 30, 2013 at 9:45
2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .