This module contains functions to enumerate primitive extensions , where
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 of discriminant
.
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 .
Next, we list all totally real quadratic extensions of
with root discriminant
.
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
or
); the others have have Galois closure of degree 8
(with Galois group
).
Finally, we compute the cubic extensions of with
discriminant
.
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:
Enumerates all totally real fields of degree n with discriminant at most B, primitive or otherwise.
INPUT:
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 ).
The following was fixed in trac ticket #13101:
sage: enumerate_totallyreal_fields_all(8, 10^6) # long time (about 2 s)
[]
This function enumerates (primitive) totally real field extensions of
degree of the totally real field F with discriminant
;
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:
OUTPUT:
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:
Return all integral elements of the totally real field whose
embeddings lie numerically within the bounds specified by the
list
. The output is architecture dependent, and one may want
to expand the bounds that define C by some epsilon.
INPUT:
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]
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.
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:
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