Enumeration of totally real fields: relative extensions

This module contains functions to enumerate primitive extensions \(L / K\), where \(K\) is a given totally real number field, with given degree and small root discriminant. This is a relative analogue of the problem described in sage.rings.number_field.totallyreal, and we use a similar approach based on a relative version of Hunter’s theorem.

In this first simple example, we compute the totally real quadratic fields of \(F = \QQ(\sqrt{2})\) of discriminant \(\le 2000\).

sage: ZZx.<x> = ZZ[]
sage: F.<t> = NumberField(x^2 - 2)
sage: enumerate_totallyreal_fields_rel(F, 2, 2000)
[[1600, x^4 - 6*x^2 + 4, xF^2 + xF - 1]]

>>> from sage.all import *
>>> ZZx = ZZ['x']; (x,) = ZZx._first_ngens(1)
>>> F = NumberField(x**Integer(2) - Integer(2), names=('t',)); (t,) = F._first_ngens(1)
>>> enumerate_totallyreal_fields_rel(F, Integer(2), Integer(2000))
[[1600, x^4 - 6*x^2 + 4, xF^2 + xF - 1]]

ZZx.<x> = ZZ[]
F.<t> = NumberField(x^2 - 2)
enumerate_totallyreal_fields_rel(F, 2, 2000)

There is indeed only one such extension, given by \(F(\sqrt{5})\).

Next, we list all totally real quadratic extensions of \(\QQ(\sqrt 5)\) with root discriminant \(\le 10\).

sage: F.<t> = NumberField(x^2 - 5)
sage: ls = enumerate_totallyreal_fields_rel(F, 2, 10^4)
sage: ls # random (the second factor is platform-dependent)
[[725, x^4 - x^3 - 3*x^2 + x + 1, xF^2 + (-1/2*t - 7/2)*xF + 1],
 [1125, x^4 - x^3 - 4*x^2 + 4*x + 1, xF^2 + (-1/2*t - 7/2)*xF + 1/2*t + 3/2],
 [1600, x^4 - 6*x^2 + 4, xF^2 - 2],
 [2000, x^4 - 5*x^2 + 5, xF^2 - 1/2*t - 5/2],
 [2225, x^4 - x^3 - 5*x^2 + 2*x + 4, xF^2 + (-1/2*t + 1/2)*xF - 3/2*t - 7/2],
 [2525, x^4 - 2*x^3 - 4*x^2 + 5*x + 5, xF^2 + (-1/2*t - 1/2)*xF - 1/2*t - 5/2],
 [3600, x^4 - 2*x^3 - 7*x^2 + 8*x + 1, xF^2 - 3],
 [4225, x^4 - 9*x^2 + 4, xF^2 + (-1/2*t - 1/2)*xF - 3/2*t - 9/2],
 [4400, x^4 - 7*x^2 + 11, xF^2 - 1/2*t - 7/2],
 [4525, x^4 - x^3 - 7*x^2 + 3*x + 9, xF^2 + (-1/2*t - 1/2)*xF - 3],
 [5125, x^4 - 2*x^3 - 6*x^2 + 7*x + 11, xF^2 + (-1/2*t - 1/2)*xF - t - 4],
 [5225, x^4 - x^3 - 8*x^2 + x + 11, xF^2 + (-1/2*t - 1/2)*xF - 1/2*t - 7/2],
 [5725, x^4 - x^3 - 8*x^2 + 6*x + 11, xF^2 + (-1/2*t + 1/2)*xF - 1/2*t - 7/2],
 [6125, x^4 - x^3 - 9*x^2 + 9*x + 11, xF^2 + (-1/2*t + 1/2)*xF - t - 4],
 [7225, x^4 - 11*x^2 + 9, xF^2 + (-1)*xF - 4],
 [7600, x^4 - 9*x^2 + 19, xF^2 - 1/2*t - 9/2],
 [7625, x^4 - x^3 - 9*x^2 + 4*x + 16, xF^2 + (-1/2*t - 1/2)*xF - 4],
 [8000, x^4 - 10*x^2 + 20, xF^2 - t - 5],
 [8525, x^4 - 2*x^3 - 8*x^2 + 9*x + 19, xF^2 + (-1)*xF - 1/2*t - 9/2],
 [8725, x^4 - x^3 - 10*x^2 + 2*x + 19, xF^2 + (-1/2*t - 1/2)*xF - 1/2*t - 9/2],
 [9225, x^4 - x^3 - 10*x^2 + 7*x + 19, xF^2 + (-1/2*t + 1/2)*xF - 1/2*t - 9/2]]
sage: [ f[0] for f in ls ]
[725, 1125, 1600, 2000, 2225, 2525, 3600, 4225, 4400, 4525, 5125, 5225, 5725, 6125, 7225, 7600, 7625, 8000, 8525, 8725, 9225]

sage: [NumberField(ZZx(x[1]), 't').is_galois() for x in ls]                         # needs sage.groups
[False, True, True, True, False, False, True, True, False, False, False, False, False, True, True, False, False, True, False, False, False]

>>> from sage.all import *
>>> F = NumberField(x**Integer(2) - Integer(5), names=('t',)); (t,) = F._first_ngens(1)
>>> ls = enumerate_totallyreal_fields_rel(F, Integer(2), Integer(10)**Integer(4))
>>> ls # random (the second factor is platform-dependent)
[[725, x^4 - x^3 - 3*x^2 + x + 1, xF^2 + (-1/2*t - 7/2)*xF + 1],
 [1125, x^4 - x^3 - 4*x^2 + 4*x + 1, xF^2 + (-1/2*t - 7/2)*xF + 1/2*t + 3/2],
 [1600, x^4 - 6*x^2 + 4, xF^2 - 2],
 [2000, x^4 - 5*x^2 + 5, xF^2 - 1/2*t - 5/2],
 [2225, x^4 - x^3 - 5*x^2 + 2*x + 4, xF^2 + (-1/2*t + 1/2)*xF - 3/2*t - 7/2],
 [2525, x^4 - 2*x^3 - 4*x^2 + 5*x + 5, xF^2 + (-1/2*t - 1/2)*xF - 1/2*t - 5/2],
 [3600, x^4 - 2*x^3 - 7*x^2 + 8*x + 1, xF^2 - 3],
 [4225, x^4 - 9*x^2 + 4, xF^2 + (-1/2*t - 1/2)*xF - 3/2*t - 9/2],
 [4400, x^4 - 7*x^2 + 11, xF^2 - 1/2*t - 7/2],
 [4525, x^4 - x^3 - 7*x^2 + 3*x + 9, xF^2 + (-1/2*t - 1/2)*xF - 3],
 [5125, x^4 - 2*x^3 - 6*x^2 + 7*x + 11, xF^2 + (-1/2*t - 1/2)*xF - t - 4],
 [5225, x^4 - x^3 - 8*x^2 + x + 11, xF^2 + (-1/2*t - 1/2)*xF - 1/2*t - 7/2],
 [5725, x^4 - x^3 - 8*x^2 + 6*x + 11, xF^2 + (-1/2*t + 1/2)*xF - 1/2*t - 7/2],
 [6125, x^4 - x^3 - 9*x^2 + 9*x + 11, xF^2 + (-1/2*t + 1/2)*xF - t - 4],
 [7225, x^4 - 11*x^2 + 9, xF^2 + (-1)*xF - 4],
 [7600, x^4 - 9*x^2 + 19, xF^2 - 1/2*t - 9/2],
 [7625, x^4 - x^3 - 9*x^2 + 4*x + 16, xF^2 + (-1/2*t - 1/2)*xF - 4],
 [8000, x^4 - 10*x^2 + 20, xF^2 - t - 5],
 [8525, x^4 - 2*x^3 - 8*x^2 + 9*x + 19, xF^2 + (-1)*xF - 1/2*t - 9/2],
 [8725, x^4 - x^3 - 10*x^2 + 2*x + 19, xF^2 + (-1/2*t - 1/2)*xF - 1/2*t - 9/2],
 [9225, x^4 - x^3 - 10*x^2 + 7*x + 19, xF^2 + (-1/2*t + 1/2)*xF - 1/2*t - 9/2]]
>>> [ f[Integer(0)] for f in ls ]
[725, 1125, 1600, 2000, 2225, 2525, 3600, 4225, 4400, 4525, 5125, 5225, 5725, 6125, 7225, 7600, 7625, 8000, 8525, 8725, 9225]

>>> [NumberField(ZZx(x[Integer(1)]), 't').is_galois() for x in ls]                         # needs sage.groups
[False, True, True, True, False, False, True, True, False, False, False, False, False, True, True, False, False, True, False, False, False]

F.<t> = NumberField(x^2 - 5)
ls = enumerate_totallyreal_fields_rel(F, 2, 10^4)
ls # random (the second factor is platform-dependent)
[ f[0] for f in ls ]
[NumberField(ZZx(x[1]), 't').is_galois() for x in ls]                         # needs sage.groups

Eight out of 21 such fields are Galois (with Galois group \(C_4\) or \(C_2 \times C_2\)); the others have Galois closure of degree 8 (with Galois group \(D_8\)).

Finally, we compute the cubic extensions of \(\QQ(\zeta_7)^+\) with discriminant \(\le 17 \times 10^9\).

sage: F.<t> = NumberField(ZZx([1,-4,3,1]))
sage: F.disc()
49
sage: enumerate_totallyreal_fields_rel(F, 3, 17*10^9)  # not tested, too long time (258s on sage.math, 2013)
[[16240385609L, x^9 - x^8 - 9*x^7 + 4*x^6 + 26*x^5 - 2*x^4 - 25*x^3 - x^2 + 7*x + 1, xF^3 + (-t^2 - 4*t + 1)*xF^2 + (t^2 + 3*t - 5)*xF + 3*t^2 + 11*t - 5]]    # 32-bit
[[16240385609, x^9 - x^8 - 9*x^7 + 4*x^6 + 26*x^5 - 2*x^4 - 25*x^3 - x^2 + 7*x + 1, xF^3 + (-t^2 - 4*t + 1)*xF^2 + (t^2 + 3*t - 5)*xF + 3*t^2 + 11*t - 5]]     # 64-bit

>>> from sage.all import *
>>> F = NumberField(ZZx([Integer(1),-Integer(4),Integer(3),Integer(1)]), names=('t',)); (t,) = F._first_ngens(1)
>>> F.disc()
49
>>> enumerate_totallyreal_fields_rel(F, Integer(3), Integer(17)*Integer(10)**Integer(9))  # not tested, too long time (258s on sage.math, 2013)
[[16240385609L, x^9 - x^8 - 9*x^7 + 4*x^6 + 26*x^5 - 2*x^4 - 25*x^3 - x^2 + 7*x + 1, xF^3 + (-t^2 - 4*t + 1)*xF^2 + (t^2 + 3*t - 5)*xF + 3*t^2 + 11*t - 5]]    # 32-bit
[[16240385609, x^9 - x^8 - 9*x^7 + 4*x^6 + 26*x^5 - 2*x^4 - 25*x^3 - x^2 + 7*x + 1, xF^3 + (-t^2 - 4*t + 1)*xF^2 + (t^2 + 3*t - 5)*xF + 3*t^2 + 11*t - 5]]     # 64-bit

F.<t> = NumberField(ZZx([1,-4,3,1]))
F.disc()
enumerate_totallyreal_fields_rel(F, 3, 17*10^9)  # not tested, too long time (258s on sage.math, 2013)

AUTHORS:

  • John Voight (2007-11-03): initial version

sage.rings.number_field.totallyreal_rel.enumerate_totallyreal_fields_all(n, B, verbose=0, return_seqs=False, return_pari_objects=True)[source]

Enumerate all totally real fields of degree n with discriminant at most B, primitive or otherwise.

INPUT:

  • n – integer; the degree

  • B – integer; the discriminant bound

  • verbose – boolean or nonnegative integer or string (default: 0); give a verbose description of the computations being performed. If verbose is set to 2 or more, it outputs some extra information. If verbose is a string, it outputs to a file specified by verbose.

  • return_seqs – boolean (default: False); if True, then return the polynomials as sequences (for easier exporting to a file). This also returns a list of four numbers, as explained in the OUTPUT section below.

  • return_pari_objects – boolean (default: True); if both return_seqs and return_pari_objects are False then it returns the elements as Sage objects; otherwise it returns PARI objects.

EXAMPLES:

sage: enumerate_totallyreal_fields_all(4, 2000)
[[725, x^4 - x^3 - 3*x^2 + x + 1],
[1125, x^4 - x^3 - 4*x^2 + 4*x + 1],
[1600, x^4 - 6*x^2 + 4],
[1957, x^4 - 4*x^2 - x + 1],
[2000, x^4 - 5*x^2 + 5]]
sage: enumerate_totallyreal_fields_all(1, 10)
[[1, x - 1]]

>>> from sage.all import *
>>> enumerate_totallyreal_fields_all(Integer(4), Integer(2000))
[[725, x^4 - x^3 - 3*x^2 + x + 1],
[1125, x^4 - x^3 - 4*x^2 + 4*x + 1],
[1600, x^4 - 6*x^2 + 4],
[1957, x^4 - 4*x^2 - x + 1],
[2000, x^4 - 5*x^2 + 5]]
>>> enumerate_totallyreal_fields_all(Integer(1), Integer(10))
[[1, x - 1]]

enumerate_totallyreal_fields_all(4, 2000)
enumerate_totallyreal_fields_all(1, 10)
sage.rings.number_field.totallyreal_rel.enumerate_totallyreal_fields_rel(F, m, B, a=[], verbose=0, return_seqs=False, return_pari_objects=True)[source]

This function enumerates (primitive) totally real field extensions of degree \(m>1\) of the totally real field F with discriminant \(d \leq B\); optionally one can specify the first few coefficients, where the sequence a corresponds to a polynomial by

a[d]*x^n + ... + a[0]*x^(n-d)

if length(a) = d+1, so in particular always a[d] = 1.

Note

This is guaranteed to give all primitive such fields, and seems in practice to give many imprimitive ones.

INPUT:

  • F – number field; the base field

  • m – integer; the degree

  • B – integer; the discriminant bound

  • a – list (default: []); the coefficient list to begin with

  • verbose – boolean or nonnegative integer or string (default: 0); give a verbose description of the computations being performed. If verbose is set to 2 or more then it outputs some extra information. If verbose is a string then it outputs to a file specified by verbose.

  • return_seqs – boolean (default: False); if True, then return the polynomials as sequences (for easier exporting to a file). This also returns a list of four numbers, as explained in the OUTPUT section below.

  • return_pari_objects – boolean (default: True); if both return_seqs and return_pari_objects are False then it returns the elements as Sage objects; otherwise it returns PARI objects.

OUTPUT:

  • the list of fields with entries [d,fabs,f], where d is the discriminant, fabs is an absolute defining polynomial, and f is a defining polynomial relative to \(F\), sorted by discriminant.

  • if return_seqs is True, then the first field of the list is a list containing the count of four items as explained below

    • the first entry gives the number of polynomials tested

    • the second entry gives the number of polynomials with its discriminant having a large enough square divisor

    • the third entry is the number of irreducible polynomials

    • the fourth entry is the number of irreducible polynomials with discriminant at most \(B\)

EXAMPLES:

sage: ZZx.<x> = ZZ[]
sage: F.<t> = NumberField(x^2 - 2)
sage: enumerate_totallyreal_fields_rel(F, 1, 2000)
[[1, [-2, 0, 1], xF - 1]]
sage: enumerate_totallyreal_fields_rel(F, 2, 2000)
[[1600, x^4 - 6*x^2 + 4, xF^2 + xF - 1]]
sage: enumerate_totallyreal_fields_rel(F, 2, 2000, return_seqs=True)
[[9, 6, 5, 0], [[1600, [4, 0, -6, 0, 1], [-1, 1, 1]]]]

>>> from sage.all import *
>>> ZZx = ZZ['x']; (x,) = ZZx._first_ngens(1)
>>> F = NumberField(x**Integer(2) - Integer(2), names=('t',)); (t,) = F._first_ngens(1)
>>> enumerate_totallyreal_fields_rel(F, Integer(1), Integer(2000))
[[1, [-2, 0, 1], xF - 1]]
>>> enumerate_totallyreal_fields_rel(F, Integer(2), Integer(2000))
[[1600, x^4 - 6*x^2 + 4, xF^2 + xF - 1]]
>>> enumerate_totallyreal_fields_rel(F, Integer(2), Integer(2000), return_seqs=True)
[[9, 6, 5, 0], [[1600, [4, 0, -6, 0, 1], [-1, 1, 1]]]]

ZZx.<x> = ZZ[]
F.<t> = NumberField(x^2 - 2)
enumerate_totallyreal_fields_rel(F, 1, 2000)
enumerate_totallyreal_fields_rel(F, 2, 2000)
enumerate_totallyreal_fields_rel(F, 2, 2000, return_seqs=True)

AUTHORS:

  • John Voight (2007-11-01)

sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)[source]

Return all integral elements of the totally real field \(K\) whose embeddings lie numerically within the bounds specified by the list C. The output is architecture dependent, and one may want to expand the bounds that define C by some epsilon.

INPUT:

  • K – a totally real number field

  • C – list [[lower, upper], ...] of lower and upper bounds, for each embedding

EXAMPLES:

sage: x = polygen(QQ)
sage: K.<alpha> = NumberField(x^2 - 2)
sage: eps = 10e-6
sage: C = [[0-eps, 5+eps], [0-eps, 10+eps]]
sage: ls = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)
sage: sorted(a.trace() for a in ls)
[0, 2, 4, 4, 4, 6, 6, 6, 6, 8, 8, 8, 10, 10, 10, 10, 12, 12, 14]
sage: len(ls)
19

sage: v = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)
sage: sorted(v)
[0, -alpha + 2, 1, -alpha + 3, 2, 3, alpha + 2, 4, alpha + 3, 5, alpha + 4,
 2*alpha + 3, alpha + 5, 2*alpha + 4, alpha + 6, 2*alpha + 5, 2*alpha + 6,
 3*alpha + 5, 2*alpha + 7]

>>> from sage.all import *
>>> x = polygen(QQ)
>>> K = NumberField(x**Integer(2) - Integer(2), names=('alpha',)); (alpha,) = K._first_ngens(1)
>>> eps = RealNumber('10e-6')
>>> C = [[Integer(0)-eps, Integer(5)+eps], [Integer(0)-eps, Integer(10)+eps]]
>>> ls = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)
>>> sorted(a.trace() for a in ls)
[0, 2, 4, 4, 4, 6, 6, 6, 6, 8, 8, 8, 10, 10, 10, 10, 12, 12, 14]
>>> len(ls)
19

>>> v = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)
>>> sorted(v)
[0, -alpha + 2, 1, -alpha + 3, 2, 3, alpha + 2, 4, alpha + 3, 5, alpha + 4,
 2*alpha + 3, alpha + 5, 2*alpha + 4, alpha + 6, 2*alpha + 5, 2*alpha + 6,
 3*alpha + 5, 2*alpha + 7]

x = polygen(QQ)
K.<alpha> = NumberField(x^2 - 2)
eps = 10e-6
C = [[0-eps, 5+eps], [0-eps, 10+eps]]
ls = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)
sorted(a.trace() for a in ls)
len(ls)
v = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)
sorted(v)

A cubic field:

sage: x = polygen(QQ)
sage: K.<a> = NumberField(x^3 - 16*x +16)
sage: eps = 10e-6
sage: C = [[0-eps,5+eps]]*3
sage: v = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)

>>> from sage.all import *
>>> x = polygen(QQ)
>>> K = NumberField(x**Integer(3) - Integer(16)*x +Integer(16), names=('a',)); (a,) = K._first_ngens(1)
>>> eps = RealNumber('10e-6')
>>> C = [[Integer(0)-eps,Integer(5)+eps]]*Integer(3)
>>> v = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)

x = polygen(QQ)
K.<a> = NumberField(x^3 - 16*x +16)
eps = 10e-6
C = [[0-eps,5+eps]]*3
v = sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)

Note that the output is platform dependent (sometimes a 5 is listed below, and sometimes it isn’t):

sage: sorted(v)
[-1/2*a + 2, 1/4*a^2 + 1/2*a, 0, 1, 2, 3, 4,...-1/4*a^2 - 1/2*a + 5,
 1/2*a + 3, -1/4*a^2 + 5]

>>> from sage.all import *
>>> sorted(v)
[-1/2*a + 2, 1/4*a^2 + 1/2*a, 0, 1, 2, 3, 4,...-1/4*a^2 - 1/2*a + 5,
 1/2*a + 3, -1/4*a^2 + 5]

sorted(v)
class sage.rings.number_field.totallyreal_rel.tr_data_rel(F, m, B, a=None)[source]

Bases: object

This class encodes the data used in the enumeration of totally real fields for relative extensions.

We do not give a complete description here. For more information, see the attached functions; all of these are used internally by the functions in totallyreal_rel.py, so see that file for examples and further documentation.

incr(f_out, verbose=False, haltk=0)[source]

‘Increment’ the totally real data to the next value which satisfies the bounds essentially given by Rolle’s theorem, and return the next polynomial in the sequence f_out.

The default or usual case just increments the constant coefficient; then inductively, if this is outside of the bounds we increment the next higher coefficient, and so on.

If there are no more coefficients to be had, returns the zero polynomial.

INPUT:

  • f_out – integer sequence; to be written with the coefficients of the next polynomial

  • verbose – boolean or nonnegative integer (default: False); print verbosely computational details. It prints extra information if verbose is set to 2 or more.

  • haltk – integer; the level at which to halt the inductive coefficient bounds

OUTPUT: the successor polynomial as a coefficient list