Enumeration of Primitive Totally Real Fields

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

See also sage.rings.number_field.totallyreal_rel, which handles the non-primitive case using relative extensions.

Algorithm

We use Hunter’s algorithm ([Cohen2000], Section 9.3) with modifications due to Takeuchi [Takeuchi1999] and the author [Voight2008].

We enumerate polynomials \(f(x) = x^n + a_{n-1} x^{n-1} + \dots + a_0\). Hunter’s theorem gives bounds on \(a_{n-1}\) and \(a_{n-2}\); then given \(a_{n-1}\) and \(a_{n-2}\), one can recursively compute bounds on \(a_{n-3}, \dots, a_0\), 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.

Examples

In this first simple example, we compute the totally real quadratic fields of discriminant \(\le 50\).

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 \(\le 10^5\):

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

References

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

Authors

  • John Voight (2007-09-01): Initial version.
  • John Voight (2007-09-19): Various optimization tweaks.
  • John Voight (2007-10-09): Added DSage module.
  • John Voight (2007-10-17): Added pari functions to avoid recomputations.
  • John Voight (2007-10-27): Separated DSage component.
  • Craig Citro and John Voight (2007-11-04): Additional doctests and type checking.
  • Craig Citro and John Voight (2008-02-10): Final modifications for submission.

sage.rings.number_field.totallyreal.enumerate_totallyreal_fields_prim(n, B, a=, []verbose=0, return_seqs=False, phc=False, keep_fields=False, t_2=False, just_print=False, return_pari_objects=True)

This function enumerates primitive totally real fields of degree \(n>1\) with discriminant \(d \leq B\); optionally one can specify the first few coefficients, where the sequence \(a\) 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:

  • n – (integer) the degree
  • B – (integer) the discriminant bound
  • a – (list, default: []) the coefficient list to begin with
  • verbose – (integer or string, default: 0) 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.
  • return_seqs – (boolean, default False) If True, then return the polynomials as sequences (for easier exporting to a file).
  • phc – boolean or integer (default: False)
  • keep_fields – (boolean or integer, default: False) If keep_fields is True, then keep fields up to B*log(B); if keep_fields is an integer, then keep fields up to that integer.
  • t_2 – (boolean or integer, default: False) If t_2 = T, then keep only polynomials with t_2 norm >= T.
  • just_print – (boolean, default: False): if just_print is not False, instead of creating a sorted list of totally real number fields, we simply write each totally real field we find to the file whose filename is given by just_print. In this case, we don’t return anything.
  • 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,f], where d is the discriminant and f is a defining polynomial, sorted by discriminant.

AUTHORS:

  • John Voight (2007-09-03)
  • Craig Citro (2008-09-19): moved to Cython for speed improvement

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

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

sage: enumerate_totallyreal_fields_prim(2, 10)
[[5, x^2 - x - 1], [8, x^2 - 2]]
sage: enumerate_totallyreal_fields_prim(2, 10)[0][1].parent()
Interface to the PARI C library
sage: enumerate_totallyreal_fields_prim(2, 10, return_pari_objects=False)[0][0].parent()
Integer Ring
sage: enumerate_totallyreal_fields_prim(2, 10, return_pari_objects=False)[0][1].parent()
Univariate Polynomial Ring in x over Rational Field
sage: enumerate_totallyreal_fields_prim(2, 10, return_seqs=True)[1][0][1][0].parent()
Rational Field
sage.rings.number_field.totallyreal.odlyzko_bound_totallyreal(n)

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:

  • n (integer) the degree

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:

  • John Voight (2007-09-03)

NOTES: The values are calculated by Martinet [Martinet1980].

sage.rings.number_field.totallyreal.timestr(m)

Converts seconds to a human-readable time string.

INPUT:

  • m – integer, number of seconds

OUTPUT:

The time in days, hours, etc.

EXAMPLES:

sage: sage.rings.number_field.totallyreal.timestr(3765)
'1h 2m 45.0s'
sage.rings.number_field.totallyreal.weed_fields(S, lenS=0)

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