enumerate_totallyreal_fields_prim(n,
B,
a=[],
verbose=0,
return_seqs=False,
phc=False,
keep_fields=False,
t_2=False)
| source code
|
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 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).
If keep_fields, then keep fields up to B*log(B); if keep_fields is
an integer, then keep fields up to that integer.
If t_2 = T, then keep only polynomials with t_2 norm >= T.
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 -- boolean or string (default: False)
phc -- boolean or integer (default: False)
OUTPUT:
the list of fields with entries [d,f], where
d is the discriminant and f is a defining polynomial,
sorted by discriminant.
EXAMPLES:
In this first simple example, we compute the totally real quadratic
fields of discriminant <= 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 <= 10^5.
sage: enumerate_totallyreal_fields_prim(5,10^5)
[[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]]
We see that there are 9 such fields (up to isomorphism!).
NOTES:
This function uses Hunter's algorithm [C, Section 9.3] and
modifications due to Takeuchi [T] and the author [V].
We enumerate polynomials
f(x) = x^n + a[n-1]*x^(n-1) + ... + 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],
..., 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 [T] for more details.
REFERENCES:
[C] Henri Cohen, Advanced topics in computational number
theory, Graduate Texts in Mathematics, vol. 193,
Springer-Verlag, New York, 2000.
[T] Kisao Takeuchi, Totally real algebraic number fields of
degree 9 with small discriminant, Saitama Math. J.
17 (1999), 63--85 (2000).
[V] John Voight, Enumeration of totally real number fields
of bounded root discriminant, to appear in
Lect. Notes in Comp. Sci.
AUTHORS:
- John Voight (2007-09-03)
|