Introduction to Algebraic Number Theory Calculations Using Sage

Math 581b, 2010-10-20

William Stein

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

Defining Number Fields

{{{id=97| NumberField /// }}} {{{id=24| # or you can do "x = var('x')", which is different but will also work x = polygen(QQ,'x') R. = PolynomialRing(QQ) R. = QQ[] 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=90| K = NumberField(x^4 - 2*x^2 - 1, 'alpha') /// }}} {{{id=89| K /// Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 }}} {{{id=91| alpha /// Traceback (most recent call last): File "", line 1, in File "_sage_input_15.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("YWxwaGE="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpMfLU4t/___code___.py", line 2, in exec compile(u'alpha' + '\n', '', 'single') File "", line 1, in NameError: name 'alpha' is not defined }}} {{{id=92| K.gen() /// alpha }}} {{{id=94| K.0 /// alpha }}} {{{id=93| alpha = K.0 s = (1+1/alpha)^10; s /// -120*alpha^3 + 164*alpha^2 + 336*alpha - 324 }}} {{{id=96| s.norm() /// 1024 }}} {{{id=95| show(s) ///
\newcommand{\Bold}[1]{\mathbf{#1}}-120 \alpha^{3} + 164 \alpha^{2} + 336 \alpha - 324
}}}

Remark: Magma (which you may also want to learn) is very similar.

{{{id=86| %magma R := PolynomialRing(RationalField()); K := NumberField(x^4 - 2*x^2 - 1); print K; /// Number Field with defining polynomial x^4 - 2*x^2 - 1 over the Rational Field }}} {{{id=98| %magma R := PolynomialRing(RationalField()); K := NumberField(x^4 - 2*x^2 - 17); print K; /// Number Field with defining polynomial x^4 - 2*x^2 - 17 over the Rational Field }}} {{{id=99| %magma K.1 /// K.1 }}} {{{id=100| %magma NumberField(x^4 + 17).1 /// $.1 }}}

Remark: Pari (which you also want to learn something of) is different.

{{{id=101| gp.nfinit? /// }}} {{{id=84| %gp k = nfinit(x^4 - 2*x^2 - 1); k /// [x^4 - 2*x^2 - 1, [2, 1], -1024, 1, [[1, -1.5537739740300373073441589530631469482, -0.64359425290558262473544343741820980891, 1.4142135623730950488016887242096980786; 1, 1.5537739740300373073441589530631469482, 0.64359425290558262473544343741820980891, 1.4142135623730950488016887242096980786; 1, 0.E-38 - 0.64359425290558262473544343741820980893*I, 0.E-38 + 1.5537739740300373073441589530631469482*I, -1.4142135623730950488016887242096980786 + 0.E-38*I], [1, -1.5537739740300373073441589530631469482, -0.64359425290558262473544343741820980891, 1.4142135623730950488016887242096980786; 1, 1.5537739740300373073441589530631469482, 0.64359425290558262473544343741820980891, 1.4142135623730950488016887242096980786; 1, -0.64359425290558262473544343741820980893, 1.5537739740300373073441589530631469482, -1.4142135623730950488016887242096980786; 1, 0.64359425290558262473544343741820980893, -1.5537739740300373073441589530631469482, -1.4142135623730950488016887242096980786], [1, -2, -1, 1; 1, 2, 1, 1; 1, -1, 2, -1; 1, 1, -2, -1], [4, 0, 0, 0; 0, 4, 4, 0; 0, 4, -4, 0; 0, 0, 0, 8], [8, 0, 0, 0; 0, 8, 4, 0; 0, 0, 4, 0; 0, 0, 0, 4], [2, 0, 0, 0; 0, 1, 1, 0; 0, 1, -1, 0; 0, 0, 0, 1], [2, [0, 2, 0, 0; 1, 0, 0, 2; 1, 0, 0, 0; 0, 1, 1, 0]]], [-1.5537739740300373073441589530631469482, 1.5537739740300373073441589530631469482, 0.E-38 - 0.64359425290558262473544343741820980893*I], [1, x, x^3 - 2*x, x^2 - 1], [1, 0, 1, 0; 0, 1, 0, 2; 0, 0, 0, 1; 0, 0, 1, 0], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1, -1, 0, 0, 0, 0, 2; 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0; 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, -1, 0, 1, -1, 0; 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]] }}} {{{id=83| gp.nfbasis? /// }}}

Special kinds of number fields:

{{{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 }}} {{{id=104| 1/((1+2*z)^3) /// -8878336/36264691*zeta15^7 + 14376704/36264691*zeta15^6 - 12283104/36264691*zeta15^5 + 5069520/36264691*zeta15^4 + 870160/36264691*zeta15^3 - 9827128/36264691*zeta15^2 + 10831182/36264691*zeta15 - 5302797/36264691 }}} {{{id=103| /// }}}

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

{{{id=108| K. =NumberField(x^2-5) /// }}} {{{id=110| R. = PolynomialRing(K) /// }}} {{{id=109| L. = K.extension(T^2 - c); L /// Number Field in b with defining polynomial T^2 - c over its base field }}} {{{id=111| b^4 /// 5 }}} {{{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=106| b^2 /// 3 }}} {{{id=105| a^2 /// 2 }}} {{{id=107| c^2 /// 5 }}} {{{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

  • define
  • do arithmetic
  • compute norm, trace, minpoly, charpoly
  • compute embeddings into C
{{{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=113| latex(z) /// 3 \alpha^{2} + 5 \alpha - 7 }}} {{{id=39| z^10 /// -828907050*alpha^3 + 1165556429*alpha^2 + 2164036050*alpha - 1977685370 }}} {{{id=63| z.complex_embeddings(200) /// [-7.5262291830309013903157285926866405051139018709206949621333, -8.2426406871192851464050661726290942357090156261308442195300 - 3.2179712645279131236772171870910490446210137122200382557808*I, -8.2426406871192851464050661726290942357090156261308442195300 + 3.2179712645279131236772171870910490446210137122200382557808*I, 8.0115105572694716831258609379448289765319331231823834011934] }}} {{{id=64| @interact def f(n=z): show(points(n.complex_embeddings(), pointsize=50)) ///
n 
}}} {{{id=114| phi = K.embeddings(RR); phi /// [ Ring morphism: From: Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 To: Real Field with 53 bits of precision Defn: alpha |--> -1.55377397403004, Ring morphism: From: Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 To: Real Field with 53 bits of precision Defn: alpha |--> 1.55377397403004 ] }}} {{{id=115| phi[0] /// Ring morphism: From: Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 To: Real Field with 53 bits of precision Defn: alpha |--> -1.55377397403004 }}} {{{id=116| phi = K.embeddings(K); phi /// [ Ring endomorphism of Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 Defn: alpha |--> alpha, Ring endomorphism of Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 Defn: alpha |--> -alpha ] }}} {{{id=117| K /// Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 }}} {{{id=118| f = phi[1]; f /// Ring endomorphism of Number Field in alpha with defining polynomial x^4 - 2*x^2 - 1 Defn: alpha |--> -alpha }}} {{{id=119| f(K.0) /// -alpha }}} {{{id=120| /// }}} {{{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=121| alpha.minpoly() /// x^4 - 2*x^2 - 1 }}} {{{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=122| K.power_basis() /// [1, alpha, alpha^2, alpha^3] }}} {{{id=123| mat = alpha.matrix(); mat /// [0 1 0 0] [0 0 1 0] [0 0 0 1] [1 0 2 0] }}} {{{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

  • define
  • factor as product of prime ideals
  • norm
  • reduce elements modulo
{{{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=124| for p in primes(30): print [P for P, e in K.ideal(p).factor()] /// [Fractional ideal (2, a)] [Fractional ideal (3, a)] [Fractional ideal (5, a + 2), Fractional ideal (5, a - 2)] [Fractional ideal (a + 1), Fractional ideal (-a + 1)] [Fractional ideal (11, a + 4), Fractional ideal (11, a - 4)] [Fractional ideal (13)] [Fractional ideal (17)] [Fractional ideal (19)] [Fractional ideal (23)] [Fractional ideal (29, a - 9), Fractional ideal (29, a + 9)] }}} {{{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| K.ring_of_integers() /// Maximal Order in Number Field in alpha with defining polynomial x^3 + x^2 - 2*x + 8 }}} {{{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| /// }}}