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)

Enumerates all totally real fields of degree \(n\) with discriminant \(\le B\), primitive or otherwise.

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

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\)).

TESTS:

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)

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. If verbose == 1 (or 2), then print to the screen (really) verbosely; if verbose is a string, then print verbosely to the file specified by verbose. If return_seqs, then return the polynomials as sequences (for easier exporting to a file).

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 string (default: 0)
  • return_seqs – boolean (default: False)

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.

EXAMPLES:

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

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 to print verbosely computational details
  • 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

Previous topic

Enumeration of Primitive Totally Real Fields

Next topic

Field of Algebraic Numbers

This Page