Basic Algebraic Number Theory Calculations Using Sage

Math 581b, 2010-10-18

William Stein

{{{id=5| /// }}}

Defining Number Fields

{{{id=24| x = polygen(QQ,'x') # or you can do "x = var('x')", which is different but will also work K. = NumberField(x^4 - 2*x^2 - 1) K /// Number Field in a with defining polynomial x^4 - 2*x^2 - 1 }}} {{{id=26| a^4 - 2*a^2 - 1 /// 0 }}} {{{id=25| K. = QuadraticField(5); K /// Number Field in a with defining polynomial x^2 - 5 }}} {{{id=4| a^2 /// 5 }}} {{{id=28| K = CyclotomicField(15); K /// Cyclotomic Field of order 15 and degree 8 }}} {{{id=27| z = K.gen(); z /// zeta15 }}} {{{id=29| z^15 /// 1 }}}

Relative extensions (warning -- basic arithmetic is very slow in some relative extensions, due to the toy implementation.  See trac 9541.)

{{{id=31| K. = NumberField([x^2 - 2, x^2 - 3, x^2 - 5]); K /// Number Field in a with defining polynomial x^2 - 2 over its base field }}} {{{id=30| a^2 + b^2 + c^2 /// 10 }}} {{{id=34| 1/(a+b+c) /// (-1/12*c*b + 1/4)*a + 1/6*b }}} {{{id=32| K.base_field() /// Number Field in b with defining polynomial x^2 - 3 over its base field }}} {{{id=33| K.base_field().base_field() /// Number Field in c with defining polynomial x^2 - 5 }}} {{{id=17| /// }}}

Elements

{{{id=37| var('x') K. = NumberField(x^4 - 2*x^2 - 1); K /// Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 }}} {{{id=36| z = 3*alpha^2 + 5*alpha - 7; z /// 3*alpha^2 + 5*alpha - 7 }}} {{{id=35| show(z) ///
\newcommand{\Bold}[1]{\mathbf{#1}}3 \alpha^{2} + 5 \alpha - 7
}}} {{{id=39| z^10 /// -828907050*alpha^3 + 1165556429*alpha^2 + 2164036050*alpha - 1977685370 }}} {{{id=63| z.complex_embeddings() /// [-7.52622918303090, -8.24264068711929 - 3.21797126452791*I, -8.24264068711929 + 3.21797126452791*I, 8.01151055726947] }}} {{{id=64| points(z.complex_embeddings(), pointsize=50) /// }}} {{{id=41| z.norm() /// -4721 }}} {{{id=42| z.trace() /// -16 }}} {{{id=43| z.minpoly() /// x^4 + 16*x^3 + 10*x^2 - 1032*x - 4721 }}} {{{id=56| z.charpoly() /// x^4 + 16*x^3 + 10*x^2 - 1032*x - 4721 }}} {{{id=44| w = alpha^2 /// }}} {{{id=57| w.charpoly() /// x^4 - 4*x^3 + 2*x^2 + 4*x + 1 }}} {{{id=59| w.minpoly() /// x^2 - 2*x - 1 }}} {{{id=60| mat = w.matrix(); mat /// [0 0 1 0] [0 0 0 1] [1 0 2 0] [0 1 0 2] }}} {{{id=58| mat.charpoly() /// x^4 - 4*x^3 + 2*x^2 + 4*x + 1 }}} {{{id=61| /// }}} {{{id=11| /// }}}

Fractional Ideals

{{{id=55| K. = QuadraticField(-6); K /// Number Field in a with defining polynomial x^2 + 6 }}} {{{id=65| I = K.ideal(6); I /// Fractional ideal (6) }}} {{{id=54| F = I.factor(); F /// (Fractional ideal (2, a))^2 * (Fractional ideal (3, a))^2 }}} {{{id=66| P = F[0][0]; P /// Fractional ideal (2, a) }}} {{{id=67| P.is_principal() /// False }}} {{{id=68| P.norm() /// 2 }}} {{{id=71| Q = F[1][0]; Q /// Fractional ideal (3, a) }}} {{{id=69| k = Q.residue_field(); k /// Residue field of Fractional ideal (3, a) }}} {{{id=72| k.cardinality() /// 3 }}} {{{id=70| k(2+a) /// 2 }}} {{{id=10| parent(k(2).lift()) /// Integer Ring }}} {{{id=74| /// }}}

The Ring $\mathcal{O}_K$ of Integers

  • Compute basis
  • Discriminant
{{{id=47| K. = QuadraticField(5); K /// Number Field in a with defining polynomial x^2 - 5 }}} {{{id=48| OK = K.maximal_order(); OK /// Maximal Order in Number Field in a with defining polynomial x^2 - 5 }}} {{{id=49| OK.basis() /// [1/2*a + 1/2, a] }}} {{{id=45| var('x') K. = NumberField(x^3 + x^2 - 2*x + 8); K /// Number Field in alpha with defining polynomial x^3 + x^2 - 2*x + 8 }}} {{{id=46| OK = K.maximal_order(); OK /// Maximal Order in Number Field in alpha with defining polynomial x^3 + x^2 - 2*x + 8 }}} {{{id=19| OK.basis() /// [1, 1/2*alpha^2 + 1/2*alpha, alpha^2] }}} {{{id=53| /// }}} {{{id=52| /// }}} {{{id=51| /// }}}

Class Groups

{{{id=75| var('x') K. = NumberField(x^3 + x^2 - 2*x + 8); K /// Number Field in alpha with defining polynomial x^3 + x^2 - 2*x + 8 }}} {{{id=76| K.class_group() /// Class group of order 1 with structure of Number Field in alpha with defining polynomial x^3 + x^2 - 2*x + 8 }}}

(Bug in how the class group prints above: see trac 10141.)

{{{id=21| a = sqrt(1+sqrt(2)) f = RR(a).algdep(4); f /// x^4 - 2*x^2 - 1 }}} {{{id=23| K. = NumberField(f); K /// Number Field in a with defining polynomial x^4 - 2*x^2 - 1 }}} {{{id=22| K.class_number() /// 1 }}} {{{id=9| /// }}}

(Massive) Efficiency Tricks

  • Assume GRH+
  • Avoid factoring the discriminant (may require Sage >= 4.6.x)
{{{id=15| # This can make some number field computations, especially of # class groups, *massively* faster: proof.number_field(False) /// }}} {{{id=79| p = next_prime(10^50); q = next_prime(10^60) /// }}} {{{id=8| K. = NumberField(x^2 - p*q, maximize_at_primes=[p,q]) /// }}} {{{id=3| K.maximal_order() /// Maximal Order in Number Field in a with defining polynomial x^2 - 100000000000000000000000000000000000000000000000151000000000700000000000000000000000000000000000000000000001057 }}} {{{id=80| K. = NumberField(x^2 - p*q) /// }}}

This would take forever:

{{{id=81| K.maximal_order() /// ^CTraceback (most recent call last): File "", line 1, in File "_sage_input_139.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Sy5tYXhpbWFsX29yZGVyKCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmp6LnqPk/___code___.py", line 2, in exec compile(u'K.maximal_order()' + '\n', '', 'single') File "", line 1, in File "/Users/wstein/purple/psage-10.09.30/local/lib/python2.6/site-packages/sage/rings/number_field/number_field.py", line 5330, in maximal_order B = map(self, self._pari_integral_basis(v = v)) File "/Users/wstein/purple/psage-10.09.30/local/lib/python2.6/site-packages/sage/rings/number_field/number_field.py", line 3746, in _pari_integral_basis B = f.nfbasis(1 if self._assume_disc_small else 0) KeyboardInterrupt __SAGE__ }}} {{{id=82| /// }}}