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 = ZZ['x']
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]]

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]
[False, True, True, True, False, False, True, True, False, False, False, False, False, True, True, False, False, True, False, False, False]

Eight out of 21 such fields are Galois (with Galois group \(C_4\) or \(C_2 \times C_2\)); the others have 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

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)

Enumerates 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 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.

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]]

TESTS:

Each of the outputs must be elements of Sage if return_pari_objects is set to False:

sage: enumerate_totallyreal_fields_all(2, 10)
[[5, x^2 - x - 1], [8, x^2 - 2]]
sage: enumerate_totallyreal_fields_all(2, 10)[0][1].parent()
Interface to the PARI C library
sage: enumerate_totallyreal_fields_all(2, 10, return_pari_objects=False)[0][1].parent()
Univariate Polynomial Ring in x over Rational Field

In practice most of these will be found by enumerate_totallyreal_fields_prim(), which is guaranteed to return all primitive fields but often returns many non-primitive ones as well. For instance, only one of the five fields in the example above is primitive, but enumerate_totallyreal_fields_prim() finds four out of the five (the exception being \(x^4 - 6x^2 + 4\)).

The following was fixed in trac ticket #13101:

sage: enumerate_totallyreal_fields_all(8, 10^6)  # long time (about 2 s)
[]

sage.rings.number_field.totallyreal_rel.enumerate_totallyreal_fields_rel(F, m, B, a=[], verbose=0, return_seqs=False, return_pari_objects=True)

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 = ZZ['x']
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]]]]

TESTS:

Each of the outputs must be elements of Sage if return_pari_objects is set to False:

sage: enumerate_totallyreal_fields_rel(F, 2, 2000)[0][1].parent()
Interface to the PARI C library
sage: enumerate_totallyreal_fields_rel(F, 2, 2000, return_pari_objects=False)[0][0].parent()
Integer Ring
sage: enumerate_totallyreal_fields_rel(F, 2, 2000, return_pari_objects=False)[0][1].parent()
Univariate Polynomial Ring in x over Rational Field
sage: enumerate_totallyreal_fields_rel(F, 2, 2000, return_pari_objects=False)[0][2].parent()
Univariate Polynomial Ring in xF over Number Field in t with defining polynomial x^2 - 2
sage: enumerate_totallyreal_fields_rel(F, 2, 2000, return_seqs=True)[1][0][1][0].parent()
Rational Field

AUTHORS:

• John Voight (2007-11-01)

sage.rings.number_field.totallyreal_rel.integral_elements_in_box(K, C)

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\) – a 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]

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)

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]

class sage.rings.number_field.totallyreal_rel.tr_data_rel(F, m, B, a=None)

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)

This function ‘increments’ the totally real data to the next value which satisfies the bounds essentially given by Rolle’s theorem, and returns 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 – an 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.

EXAMPLES:

As this function is heavily used internally by the various enumeration routines, there is no separate test:

sage: pass # not tested