Algorithm for computing Class Group and Class Number?

Class_number

asked 2018-08-10 15:54:14 +0100

mathjain
51 ●5 ●7 ●10

I wanted to know what procedure does SAGE use for computing class numbers. I typed

sage : K = NumberField(x^2 + x + 1)

sage : K.class_number?

After that I got the documentation and further I opened this file ~/SageMath/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py

In that I looked for the place where I can find the class number snippet. It turns out that sage returns the order of class group, so I looked for class group snippet.

proof = proof_flag(proof)

    try:
        return self.__class_group[proof, names]
    except KeyError:
        pass
    except AttributeError:
        self.__class_group = {}
    k = self.pari_bnf(proof)
    cycle_structure = tuple( ZZ(c) for c in k.bnf_get_cyc() )

    # Gens is a list of ideals (the generators)
    gens = tuple( self.ideal(hnf) for hnf in k.bnf_get_gen() )

    G = ClassGroup(cycle_structure, names, self, gens, proof=proof)
    self.__class_group[proof, names] = G
    return G

But I couldn't understand where is the implementation of algorithm. Can anyone help me from here to reach where I can get the algorithm?

edit retag flag offensive close merge delete

add a comment

answered 2018-08-10 18:35:49 +0100

rburing

10929 ●4 ●80 ●218 https://www.rburing.nl/

updated 2018-08-10 19:18:57 +0100

Here Sage is letting PARI do the hard work, creating a "Buchmann's number field" (bnf), which is a data structure containing the defining data of the number field and invariants such as the class group structure. The section Class group, units, and the GRH of the page I linked earlier states that

Some of the functions starting with bnf are implementations of the sub-exponential algorithms for finding class and unit groups under GRH, due to Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier.

Some more names are dropped further along the page.

In the source code of PARI one sees that bnfinit corresponds to the C function bnfinit0 which calls Buchall_param, which seems to be doing much of the work. The source file credits McCurley and Buchmann. At this point it is probably it is easier to find a reference than it is to read Buchall_param.

Note that Sage's parameter proof tells PARI to run bnfcertify. From the same section quoted before:

Warning. Make sure you understand the above! By default, most of the bnf routines depend on the correctness of the GRH. In particular, any of the class number, class group structure, class group generators, regulator and fundamental units may be wrong, independently of each other. Any result computed from such a bnf may be wrong. The only guarantee is that the units given generate a subgroup of finite index in the full unit group. You must use bnfcertify to certify the computations unconditionally.

The source for bnfcertify0 refers to Zimmert's bound $B$ and consists of two phases. The first phase for the class group calls bnftestprimes and according to the User's Guide

Running this function successfully proves that the classes of all prime ideals of norm $\leq B$ belong to the subgroup of the class group generated by the factorbase used to compute the bnf (equal to the class group under GRH). If the condition is not true, then (GRH is false and) the function will run forever.

The second phase tests the units and relations, but I am not sure how.

edit flag offensive delete link

add a comment

Algorithm for computing Class Group and Class Number?

1 Answer

Your Answer

Question Tools

Stats

Related questions

Algorithm for computing Class Group and Class Number? edit

1 Answer

Your Answer

Question Tools

Stats

Related questions

Algorithm for computing Class Group and Class Number?