Enumeration of Primitive Totally Real Fields
This module contains functions for enumerating all primitive
totally real number fields of given degree and small discriminant.
Here a number field is called primitive if it contains no proper
subfields except .
See also sage.rings.number_field.totallyreal_rel, which handles the non-primitive case using relative extensions.
We use Hunter’s algorithm ([Cohen2000], Section 9.3) with modifications due to Takeuchi [Takeuchi1999] and the author [Voight2008].
We enumerate polynomials .
Hunter’s theorem gives bounds on
and
; then given
and
, one can recursively compute bounds on
, using the fact that the polynomial is totally real by
looking at the zeros of successive derivatives and applying
Rolle’s theorem. See [Takeuchi1999] for more details.
In this first simple example, we compute the totally real quadratic
fields of discriminant .
sage: enumerate_totallyreal_fields_prim(2,50)
[[5, x^2 - x - 1],
[8, x^2 - 2],
[12, x^2 - 3],
[13, x^2 - x - 3],
[17, x^2 - x - 4],
[21, x^2 - x - 5],
[24, x^2 - 6],
[28, x^2 - 7],
[29, x^2 - x - 7],
[33, x^2 - x - 8],
[37, x^2 - x - 9],
[40, x^2 - 10],
[41, x^2 - x - 10],
[44, x^2 - 11]]
sage: [ d for d in range(5,50) if (is_squarefree(d) and d%4 == 1) or (d%4 == 0 and is_squarefree(d/4)) ]
[5, 8, 12, 13, 17, 20, 21, 24, 28, 29, 33, 37, 40, 41, 44]
Next, we compute all totally real quintic fields of discriminant :
sage: ls = enumerate_totallyreal_fields_prim(5,10^5) ; ls
[[14641, x^5 - x^4 - 4*x^3 + 3*x^2 + 3*x - 1],
[24217, x^5 - 5*x^3 - x^2 + 3*x + 1],
[36497, x^5 - 2*x^4 - 3*x^3 + 5*x^2 + x - 1],
[38569, x^5 - 5*x^3 + 4*x - 1],
[65657, x^5 - x^4 - 5*x^3 + 2*x^2 + 5*x + 1],
[70601, x^5 - x^4 - 5*x^3 + 2*x^2 + 3*x - 1],
[81509, x^5 - x^4 - 5*x^3 + 3*x^2 + 5*x - 2],
[81589, x^5 - 6*x^3 + 8*x - 1],
[89417, x^5 - 6*x^3 - x^2 + 8*x + 3]]
sage: len(ls)
9
We see that there are 9 such fields (up to isomorphism!).
[Cohen2000] | Henri Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000. |
[Martinet1980] | Jacques Martinet, Petits discriminants des corps de nombres, Journ. Arithm. 1980, Cambridge Univ. Press, 1982, 151–193. |
[Takeuchi1999] | (1, 2) Kisao Takeuchi, Totally real algebraic number fields of degree 9 with small discriminant, Saitama Math. J. 17 (1999), 63–85 (2000). |
[Voight2008] | John Voight, Enumeration of totally real number fields of bounded root discriminant, Lect. Notes in Comp. Sci. 5011 (2008). |
This function enumerates primitive totally real fields of degree
with discriminant
; optionally one can specify the
first few coefficients, where the sequence
corresponds to
a[d]*x^n + ... + a[0]*x^(n-d)
where 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:
the list of fields with entries [d,f], where d is the discriminant and f is a defining polynomial, sorted by discriminant.
AUTHORS:
TESTS:
sage: len(enumerate_totallyreal_fields_prim(2,10**4))
3043
sage: len(enumerate_totallyreal_fields_prim(3,3**8))
237
sage: len(enumerate_totallyreal_fields_prim(5,5**7))
6
sage: len(enumerate_totallyreal_fields_prim(2,2**15)) # long time
9957
sage: len(enumerate_totallyreal_fields_prim(3,3**10)) # long time
2720
sage: len(enumerate_totallyreal_fields_prim(5,5**8)) # long time
103
This function returns the unconditional Odlyzko bound for the root discriminant of a totally real number field of degree n.
NOTE: The bounds for n > 50 are not necessarily optimal.
INPUT:
OUTPUT:
a lower bound on the root discriminant (as a real number)
EXAMPLES:
sage: [sage.rings.number_field.totallyreal.odlyzko_bound_totallyreal(n) for n in range(1,5)]
[1.0, 2.223, 3.61, 5.067]
AUTHORS:
NOTES: The values are calculated by Martinet [Martinet1980].
Converts seconds to a human-readable time string.
INPUT:
OUTPUT:
The time in days, hours, etc.
EXAMPLES:
sage: sage.rings.number_field.totallyreal.timestr(3765)
'1h 2m 45.0s'
Function used internally by the enumerate_totallyreal_fields_prim() routine. (Weeds the fields listed by [discriminant, polynomial] for isomorphism classes.) Returns the size of the resulting list.
EXAMPLES:
sage: ls = [[5,pari('x^2-3*x+1')],[5,pari('x^2-5')]]
sage: sage.rings.number_field.totallyreal.weed_fields(ls)
1
sage: ls
[[5, x^2 - 3*x + 1]]