2016-02-08-class-groups.sagews

Feb 8, 2016: Class groups (part 1)

William Stein

1. Basic computation of the class group

Sage can compute with the group of ideal classes in a number field. The real hard work under the hood is done by PARI.

K.<a> = NumberField(x^2 + 23)
K

Number Field in a with defining polynomial x^2 + 23

K.class_number()

3

G = K.class_group()
G

Class group of order 3 with structure C3 of Number Field in a with defining polynomial x^2 + 23

G.gens()

(Fractional ideal class (2, 1/2*a - 1/2),)

I = G.gens()[0]
I

Fractional ideal class (2, 1/2*a - 1/2)

I^2

Fractional ideal class (2, 1/2*a + 1/2)

I^3

Trivial principal fractional ideal class

I^2 == I^4

False

I^2 == I^5

True

C = K.class_group()
for I in C:
    print I

Trivial principal fractional ideal class Fractional ideal class (2, 1/2*a - 1/2) Fractional ideal class (2, 1/2*a + 1/2)

z = C.gens()[0]; z

Fractional ideal class (2, 1/2*a - 1/2)

z.parent()

Class group of order 3 with structure C3 of Number Field in a with defining polynomial x^2 + 23

z.ideal()

Fractional ideal (2, 1/2*a - 1/2)

z.ideal().parent()

Monoid of ideals of Number Field in a with defining polynomial x^2 + 23

2. Proof

The most critical thing to know about computing with ideal class groups in Sage is that by default Sage does not assume unproven conjectures. This makes computing the class group in the first place ridicuously (exponentially!) hard.

Algorithms for computing class groups involve computing some bound $B$ so that every ideal class is equivalent to one with norm at most $B$. (You might remember that this was one approach to proving that the class group is finite with the $B$ coming from geometry of numbers...) To compute the class group, one finds such a $B$, does a bunch of clever stuff (e.g., writing down lots of principal ideals and factoring them) with ideals up to norm $B$, and determines the exact group structure.

With no unproven conjectures, $B$ is really large, in terms of the discriminant of the field.

There are conjectures -- such as GRH -- under which the bounds aren't so bad.

To tell Sage to allow unproved conjectures when computing class groups (which go beyond just GRH!), either explicitly pass in the proof=False flag, or use the proofs object.

# This does not seem like the most terrifying and intimidating field of all time...
K.<a> = NumberField(x^4 + x + 2016)
K

Number Field in a with defining polynomial x^4 + x + 2016

K.discriminant().factor()

3 * 41 * 1894802407

# No idea how long this would take:
%time K.class_number()

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 3791, in class_number return self.class_group(proof).order() File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 3760, in class_group k = self.pari_bnf(proof) File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 3602, in pari_bnf self._pari_bnf = f.bnfinit(1) File "sage/libs/pari/auto_gen.pxi", line 2964, in sage.libs.pari.gen.gen_auto.bnfinit (/projects/sage/sage-6.10/src/build/cythonized/sage/libs/pari/gen.c:19382) pari_catch_sig_on() File "sage/ext/interrupt/interrupt.pyx", line 88, in sage.ext.interrupt.interrupt.sig_raise_exception (/projects/sage/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:924) raise KeyboardInterrupt KeyboardInterrupt

CPU time: 23.50 s, Wall time: 23.69 s

# This is do-able:
%time K.class_number(proof=False)

1 CPU time: 15.97 s, Wall time: 16.00 s

# Click the restart button above... then:

proof.number_field(False)

K.<a> = NumberField(x^4 + x + 2016)
%time K.class_number()

1 CPU time: 33.73 s, Wall time: 33.75 s

proof.
︠525bf3fd-71f7-4c8b-a036-2b81b52a9809i︠
%md
Main point: explicitly computing class groups -- even of relative simple number fields -- is **REALLY DIFFICULT**.

Respect this problem.  It's not easy.

Here's an example record: http://147.210.16.88/archives/pari-dev-1312/msg00018.html

Main point: explicitly computing class groups -- even of relative simple number fields -- is REALLY DIFFICULT.

Respect this problem. It's not easy.

Here's an example record: http://147.210.16.88/archives/pari-dev-1312/msg00018.html

Exercise right now: How many real-quadratic fields $x^2 - d$ with $0<d<1000$ have class number 1?

n = 0
for d in [1..1000]:
    if is_fundamental_discriminant(d):
        if QuadraticField(d).class_number() # [...finish this...]

Error in lines 2-4 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "<string>", line 3 if QuadraticField(d).class_number() ^ SyntaxError: invalid syntax

Surprising Open Problem: Prove that there are infinitely numbers fields with class number 1.

PARI -- where this functionality in Sage comes from:

K.class_group??

   File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py
   Source:
       def class_group(self, proof=None, names='c'):
        r"""
        Return the class group of the ring of integers of this number
        field.

        INPUT:


        -  ``proof`` - if True then compute the class group
           provably correctly. Default is True. Call number_field_proof to
           change this default globally.

        -  ``names`` - names of the generators of this class
           group.


        OUTPUT: The class group of this number field.

        EXAMPLES::

            sage: K.<a> = NumberField(x^2 + 23)
            sage: G = K.class_group(); G
            Class group of order 3 with structure C3 of Number Field in a with defining polynomial x^2 + 23
            sage: G.0
            Fractional ideal class (2, 1/2*a - 1/2)
            sage: G.gens()
            (Fractional ideal class (2, 1/2*a - 1/2),)

        ::

            sage: G.number_field()
            Number Field in a with defining polynomial x^2 + 23
            sage: G is K.class_group()
            True
            sage: G is K.class_group(proof=False)
            False
            sage: G.gens()
            (Fractional ideal class (2, 1/2*a - 1/2),)

        There can be multiple generators::

            sage: k.<a> = NumberField(x^2 + 20072)
            sage: G = k.class_group(); G
            Class group of order 76 with structure C38 x C2 of Number Field in a with defining polynomial x^2 + 20072
            sage: G.0 # random
            Fractional ideal class (41, a + 10)
            sage: G.0^38
            Trivial principal fractional ideal class
            sage: G.1 # random
            Fractional ideal class (2, -1/2*a)
            sage: G.1^2
            Trivial principal fractional ideal class

        Class groups of Hecke polynomials tend to be very small::

            sage: f = ModularForms(97, 2).T(2).charpoly()
            sage: f.factor()
            (x - 3) * (x^3 + 4*x^2 + 3*x - 1) * (x^4 - 3*x^3 - x^2 + 6*x - 1)
            sage: [NumberField(g,'a').class_group().order() for g,_ in f.factor()]
            [1, 1, 1]
        """
        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

K.pari_bnf??

   File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py
   Source:
       def pari_bnf(self, proof=None, units=True):
        """
        PARI big number field corresponding to this field.

        INPUT:

        - ``proof`` -- If False, assume GRH.  If True, run PARI's
          ``bnfcertify()`` to make sure that the results are correct.

        - ``units`` -- (default: True) If True, insist on having
          fundamental units.  If False, the units may or may not be
          computed.

        OUTPUT:

        The PARI ``bnf`` structure of this number field.

        .. warning::

           Even with ``proof=True``, I wouldn't trust this to mean
           that everything computed involving this number field is
           actually correct.

        EXAMPLES::

            sage: k.<a> = NumberField(x^2 + 1); k
            Number Field in a with defining polynomial x^2 + 1
            sage: len(k.pari_bnf())
            10
            sage: k.pari_bnf()[:4]
            [[;], matrix(0,3), [;], ...]
            sage: len(k.pari_nf())
            9
            sage: k.<a> = NumberField(x^7 + 7); k
            Number Field in a with defining polynomial x^7 + 7
            sage: dummy = k.pari_bnf(proof=True)
        """
        proof = get_flag(proof, "number_field")
        # First compute bnf
        try:
            bnf = self._pari_bnf
        except AttributeError:
            f = self.pari_polynomial("y")
            if units:
                self._pari_bnf = f.bnfinit(1)
            else:
                self._pari_bnf = f.bnfinit()
            bnf = self._pari_bnf
        # Certify if needed
        if proof and not getattr(self, "_pari_bnf_certified", False):
            if bnf.bnfcertify() != 1:
                raise ValueError("The result is not correct according to bnfcertify")
            self._pari_bnf_certified = True
        return bnf

The real hard work is Sage using the function pari_bnf, which is really bnfinit in PARI. When proof is true (the default), there's also another call to PARI to prove that the result it output is right.

See http://pari.math.u-bordeaux.fr/Events/PARI2012/talks/bnfinit.pdf for somethin gabout how bnfinit works.

4. $S$-class group

Given a finite set $S$ of primes, the $S$-ideal class group is quotient of the class group by the subgroup generated by ideals in $S$.

K.<a> = NumberField(x^2 + 23)
K.S_class_group([])

S-class group of order 3 with structure C3 of Number Field in a with defining polynomial x^2 + 23

K.S_class_group([K.fractional_ideal([2, 1/2*a - 1/2])])  # kill one generator

S-class group of order 1 of Number Field in a with defining polynomial x^2 + 23

K.S_class_group([K.fractional_ideal([1/2*a - 1/2])])    # killing a principal ideal does nothing.

S-class group of order 3 with structure C3 of Number Field in a with defining polynomial x^2 + 23

︠1c848e49-6909-4fb2-a5a3-0c526ee4b007i︠
%md
**Exercise:**
1. Come up (by hook or crook) with an example of a field $K$ with a non-cyclic class group.
2. Find $S$ so for that field the $S$-class group is cyclic (and compute and show this).

Exercise:

1. Come up (by hook or crook) with an example of a field $K$ with a non-cyclic class group.

2. Find $S$ so for that field the $S$-class group is cyclic (and compute and show this).