Asymptotics of Cubic Number Fields with Bounded Second Successive Minimum of the Trace Form
©2011
Masterarbeit
82 Seiten
Zusammenfassung
We present a new way of investigating totally real algebraic number fields of degree 3. Instead of making tables of number fields with restrictions only on the field discriminant and/or the signature as described by Pohst, Martinet, Diaz y Diaz, Cohen, and other authors, we bound not only the field discriminant and the signature but also the second successive minima of the trace form on the ring of integers O(K) of totally real cubic fields K. With this, we eventually obtain an asymptotic behaviour of the size of the set of fields which fulfill the given requirements. This asymptotical behaviour is only subject to the bound X for the second successive minima, namely the set in question will turn out to be of the size O(X^(5/2)). We introduce the necessary notions and definitions from algebraic number theory, more precisely from the theory of number fields and from class field theory as well as some analytical concepts such as (Riemann and Dedekind) zeta functions which play a role in some of the computations. From the boundedness of the second successive minima of the trace form of fields we derive bounds for the coefficients of the polynomials which define those fields, hence obtaining a finite set of such polynomials. We work out an elaborate method of counting the polynomials in this set and we show that errors that arise with this procedure are not of important order. We parametrise the polynomials so that we have the possibility to apply further concepts, beginning with the notion of minimality of the parametrization of a polynomial. Considerations about the consequences of allowing only minimal pairs (B,C) (as parametrization of a polynomial f(t)=t^3+at^2+bt+c) to be of interest as well as a bound for the number of Galois fields among all fields in question and their importance in the procedure of counting minimal pairs, polynomials, and fields finally lead to the proof that the number of fields K with second successive minimum M2(K) <= X divided by the size of the suitably "cut back" set of polynomials tends to 1 if X tends to infinity, particularly because the number of fields with more than one related minimal pair (B,C) is of negligible order. A considerable amount of work accounts for the computational investigation of the theory, namely we show how fast the convergence of the above-mentioned limit actually is by computing the value of the fraction for several values of X. Computational results are presented as comprehensive tables and graphs.
Leseprobe
Inhaltsverzeichnis
Contents
iv
5. The Rate of Convergence
53
5.1. The Main Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2. The Class Number Formula and Other Convergences . . . . . . 56
5.3. Technical Details and an Overview of the Computational Results 59
6. Summary and Outlook
62
A. Computational Results
66
B. Source Codes
68
References
71
List of Figures
v
List of Figures
1.
Value of the fraction
|P (X)|·X
-5/2
6/15
. . . . . . . . . . . . . . . . . . 20
2.
Value of the fraction
X
X
5/2
. . . . . . . . . . . . . . . . . . . . . . 57
3.
Value of the fraction 10
2
·
X
5/2
-|F (X)|
X
2
. . . . . . . . . . . . . . . 59
4.
Running time of Algorithm 2 in milliseconds . . . . . . . . . . . 61
5.
Graphs of
|F (X)| and X
5/2
. . . . . . . . . . . . . . . . . . . . 63
6.
Value of the fraction
X
5/2
|F (X)|
. . . . . . . . . . . . . . . . . . . . . 64
List of Tables
vi
List of Tables
1.
Value of the fraction
|P (X)|·X
-5/2
6/15
. . . . . . . . . . . . . . . . . . 20
2.
Value of the fraction
X
X
5/2
. . . . . . . . . . . . . . . . . . . . . . 58
3.
Value of the fraction
X
5/2
-|F (X)|
X
2
. . . . . . . . . . . . . . . . . . 59
4.
Overview: Computational results . . . . . . . . . . . . . . . . . 60
5.
Running time of Algorithm 2
. . . . . . . . . . . . . . . . . . . 61
6.
Size of the set P (X) for larger values of X . . . . . . . . . . . . 63
7.
Computational results . . . . . . . . . . . . . . . . . . . . . . . 67
List of Algorithms
vii
List of Algorithms
1.
Compute the number of fields K with M
2
(K)
X . . . . . . . 54
2.
Compute the number of fields K with M
2
(K)
X together
with
X
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Abstract (English)
viii
Abstract (English)
We present a new way of investigating totally real algebraic number fields of
degree 3. Instead of making tables of number fields with restrictions only on the
field discriminant and/or the signature as described by Pohst, Martinet, Diaz
y Diaz, Cohen, and other authors, we bound not only the field discriminant
and the signature but also the second successive minima of the trace form on
the ring of integers
O
K
of totally real cubic fields K. With this, we eventually
obtain an asymptotic behaviour of the size of the set of fields which fulfill the
given requirements. This asymptotical behaviour is only subject to the bound
X for the second successive minima, namely the set in question will turn out
to be of the size
O(X
5/2
).
We introduce the necessary notions and definitions from algebraic number
theory, more precisely from the theory of number fields and from class field
theory as well as some analytical concepts such as (Riemann and Dedekind) zeta
functions which play a role in some of the computations. From the boundedness
of the second successive minima of the trace form of fields we derive bounds for
the coefficients of the polynomials which define those fields, hence obtaining a
finite set of such polynomials. We work out an elaborate method of counting the
polynomials in this set and we show that errors that arise with this procedure
are not of important order. We parametrize the polynomials so that we have the
possibility to apply further concepts, beginning with the notion of minimality
of the parametrization of a polynomial. Considerations about the consequences
of allowing only minimal pairs (B, C) (as parametrization of a polynomial
f (t) = t
3
+ at
2
+ bt + c) to be of interest as well as a bound for the number of
Galois fields among all fields in question and their importance in the procedure
Abstract (English)
ix
of counting minimal pairs, polynomials, and fields finally lead to the proof that
the number of fields K with second successive minimum M
2
(K)
X divided
by the size of the suitably "cut back" set of polynomials tends to 1 if X tends
to infinity, particularly because the number of fields with more than one related
minimal pair (B, C) is of negligible order.
A considerable amount of work accounts for the computational investigation of
the theory, namely we show how fast the convergence of the above-mentioned
limit actually is by computing the value of the fraction for several values of X.
Computational results are presented as comprehensive tables and, as a vivid
representation, as graphs.
Abstract (German)
x
Abstract (German)
Es wird eine neue Art, total reelle algebraische Zahlkörper vom Grad 3 zu
untersuchen, vorgestellt. Anstatt Tabellen von Zahlkörpern mit beschränkter
Diskriminante und/oder Signatur zu erstellen (wie Pohst, Martinet, Diaz y
Diaz, Cohen und andere Autoren), beschränken wir außerdem die zweiten
sukzessiven Minima der Spurform auf
O
K
, dem Ring der ganzen Zahlen total
reeller kubischer Zahlkörper K. Es wird ein asymptotisches Verhalten für
die Kardinalität der Menge aller Körper, die diese Voraussetzungen erfüllen,
hergeleitet. Die Asymptotik ist dabei nur abhängig von der Schranke X für
die zweiten sukzessiven Minima und es wird gezeigt, dass die Kardinalität der
untersuchten Menge
O(X
5/2
) ist.
Wir führen die notwendigen Begriffe und Definitionen aus der algebraischen
Zahlentheorie, speziell aus der Theorie der Zahlkörper und der Klassenkörperthe-
orie, ein. Weiterhin werden einige analytische Konzepte wie (Riemannsche
und Dedekindsche) Zetafunktionen, die in einigen Berechnungen eine Rolle
spielen, eingeführt. Aus der Schranke für die zweiten sukzessiven Minima der
Spurform der Körper werden Schranken für die Koeffizienten der Polynome,
die diese Körper beschreiben, hergeleitet und als Resultat eine endliche Menge
solcher Polynome beschrieben. Es wird beschrieben, wie die Elemente dieser
Menge schnell und sinnvoll gezählt werden können, dabei wird gezeigt, dass
die dabei auftretenden Fehler asymptotisch nicht von Bedeutung sind. Die
Polynome werden parametrisiert, so dass weitere Konzepte angewandt werden
können, allen voran wird die Minimalität einer Parametrisierung eines Poly-
noms eingeführt. Nachdem beschrieben wurde, warum nur minimale Paare
(B, C) (als Parametrisierung eines Polynoms f (t) = t
3
+ at
2
+ bt + c) von
Abstract (German)
xi
Interesse sind und eine Schranke für die Anzahl der Galoiserweiterungen unter
den fraglichen Körpern sowie deren Bedeutung beim Zählen von minimalen
Paaren, Polynomen und Körpern hergeleitet wurde, wird schließlich gezeigt,
dass die Anzahl der Körper K mit zweitem sukzessiven Minimum M
2
(K)
X
dividiert durch die Kardinalität der passend "beschnittenen" Menge der Poly-
nome für X
gegen 1 konvergiert, was unter anderem daraus folgt, dass
die Anzahl der Körper mit mehr als einem zugehörigen minimalen Paar (B, C)
asymptotisch keine Rolle spielt.
Ein nicht unerheblicher Aufwand kommt der rechnerischen Untersuchung der
Theorie zugute. Es wird gezeigt, wie schnell die Konvergenz des genannten
Grenzwertes ist, indem der Wert des Bruchs für verschiedene X berechnet wird.
Die Ergebnisse werden als ausführliche Tabellen und, zur Veranschaulichung,
als Graphen dargestellt.
1. Introduction
1
1. Introduction
Algebraic number fields, particularly of small degree n, have been treated in
detail in several publications during the last years. The two textbooks by
Cohen (1993 and 2000), for example, offer lots of information about the topic
itself as well as a comprehensive list of references. The subject that has been
investigated the most is the computation of lists of number fields K with field
discriminant d(K) less than or equal to a given bound D and the computation
of the minimal value of the discriminant for a given degree n (and often also
signature (r
1
, r
2
)) of the number fields. The distinct cases of different degrees,
as well as the different numbers of real and complex embeddings, respectively,
are usually treated independently of each other since each case itself offers a
broad set of problems and questions. Comprehensive lists and many values
have been computed for the cases of fixed degree n
8 in Buchmann and Ford,
1989 (for n = 4), Buchmann et al., 1993 (also for n = 4), Pohst, 1975 (for
n = 5, 6, 7, 8), Pohst, 1982 (for n = 6) and Pohst et al., 1990 (for n = 8) where
some of them concentrate on only some choices for the signature while others
cover all of them. In some of the cases the applied methods and algorithms
have been notably improved over the years.
Each value for the degree n of the investigated fields represents a huge and
interesting set of problems and questions that can be treated on its own. The
case we will concentrate on in this thesis is n = 3. Algebraic number fields of
degree 3 are often referred to as cubic fields and, in a way, their investigation is
easier than the investigation of higher degree fields since the higher the degree
of the field, the higher the number of possible signatures (i.e. combinations
of real and complex embeddings of the field). Usual questions regarding cubic
1. Introduction
2
fields are, as in other cases, the number of fields with discriminant less than or
equal to a given bound as treated in Cohen, 2000, and the computation of the
density of discriminants of those fields as treated in Roberts, 2000, or, much
earlier, in Davenport and Heilbronn, 1969, and Davenport and Heilbronn, 1971.
In this thesis, we will concentrate only on totally real cubic fields. Totally
real fields are those fields K for which each embedding of K into the complex
numbers
C has an image that lies inside the real numbers R. An important
result will be based on the work of Cohn, 1954, on the density of abelian (and
hence totally real) cubic fields.
The purpose of this thesis is to show that the number of isomorphism classes
of cubic fields K whose second successive minima M
2
(K), as introduced by
Minkowski, are less than or equal to a given bound X is asymptotically equal (in
X) to the number of cubic polynomials defining these fields modulo a relation
P
which will be explained in detail. Loosely speaking, we will investigate how
to "cut back" the set of polynomials, which is bounded only by the choice of X
and a restriction on the coefficient of the quadratic term of the polynomials,
to obtain a new set of polynomials which has asymptotically the same size
as the set of isomorphism classes of cubic fields generated by polynomials of
the original set. Usually one would expect a finite set of polynomials P whose
coefficients are bounded by suitable values to be somewhat larger than the
set F of all isomorphism classes of cubic number fields generated by these
polynomials. The inequality
|F | |P | is clear although a general statement
about the difference of the two cardinalities cannot be made that simply.
The problems that have to be dealt with in the course of our investigation
are: how to count the polynomials in the set defined by the bound X and the
restriction on the coefficient of the quadratic term effectively? How to treat the
errors that arise when counting the polynomials in a more elaborate way than
just counting them one by one? How to represent the polynomials in a way so
that a universal correspondence between polynomials and isomorphism classes
of cubic fields can be introduced? Do we have to treat Galois fields different
from fields that are non-Galois?
1. Introduction
3
The thesis will treat these questions in reasonable order by investigating three
sets and mappings between them. The sets we will deal with are
F (X) =
{Isomorphism classes of cubic fields K | K is totally real,
M
2
(K)
X},
P (X) =
{f(t) = t
3
+ at
2
+ bt + c
| a, b, c Z, 0 a 2,
0 < a
2
- 2b X, d(f) > 0, f is irreducible}, and
P
(X) =
{(B, C) | (B, C) is a minimal parametrization of
an irreducible polynomial f with B, C > 0
}
where the notion of a minimal pair (B, C) as parametrization of a polynomial
f contains some inequalities which bound the set P
(X). The two mappings
we will investigate are
P (X)
F (X) and
P
(X)
F (X).
The first result regarding these sets is a statement about the size of the set
P (X) which will turn out to be
6
15
X
5/2
+
O(X
3/2
). The set P
(X) is somewhat
smaller than P (X) and its size will turn out to be asymptotically equal to
1
2
(5)
-1
6
15
X
5/2
with the factor
1
2
being due to the facts that we always have
B > 0 and that (B, C) and (B,
-C) always belong to fields of the same
isomorphism class (which is also the reason we allow only pairs (B, C) with
B, C > 0 in P
(X)). During the investigation of P
(X) we will find out that
the number of Galois fields among the set of all fields "belonging" to pairs
(B, C)
P
(X) (which imply that the related pair (B, C) is counted three
times instead of only once as it is the case for non-Galois fields) is negligible,
namely it is
O(X
3/2
). Furthermore we will bound the number of fields with
more than one related pair (B, C) to
O(X
2
) so that they do not play a role
in the asymptotical consideration as well. Putting all these results together,
we will prove that, based on the set P (X), we obtain the set P
(X) which is
asymptotically as "large" as the set F (X). Attention should be paid to the
1. Introduction
4
fact that
|F (X)| cannot be determined easier than by counting all its elements,
which means that there is no closed formula for this cardinality only subject
to the value of X. However, via the cardinality of P
(X), which we will get
to know asymptotically, we can make a statement about
|F (X)|, which is
also asymptotic. It makes sense to investigate and illustrate this asymptotical
behavior computationally, which will be done as a supplement and, in a way,
as an application of the theory.
We will begin with some preliminaries to introduce the notions and concepts
that we will run across repeatedly throughout the whole thesis in Chapter 2
where we give a short introduction into the most important notions in the
theory of number fields. Some concepts from class field theory will later be
important and we give the necessary definitions. In Chapter 3 we will build
the set of polynomials we are interested in by evaluating the consequences
of the few requirements we have on the polynomial coefficients which will
eventually lead to a finite set of polynomials of size
O(X
5/2
). We will see
that we can count the number of polynomials in this set faster than just to
count them one by one and we will evaluate the errors that arise when doing
that. Furthermore, as a first important result, we will see that the number of
reducible polynomials we have to think about is of negligible order. In order
to obtain a correspondence between polynomials and fields, we introduce a
parametrization of the polynomials in Chapter 4 where we will also see, as
an important result, that the number of Galois fields in question is negligible
which implies the desired correspondence. This will finally enable us to proof
the assumption that the number of fields in question is asymptotically equal to
the number of polynomials defining these fields modulo the relation
P
which,
in a way, "cuts back" the original set of polynomials. We will also see that
the portion of fields with more than one corresponding minimal pair (B, C) is
insignificant, which is essential. Finishing with a computational consideration
of the problems and an investigation of the speed of the convergence of the
limit we are considering in Chapter 5, we conclude the discussion of the theory.
Important algorithms are introduced and the quintessence of the computational
results is presented while more detailed information on the computational work
1. Introduction
5
(such as source codes) and detailed results can be found in Chapter 6 and in
the appendix.
Note that, in the computational part of the work, we often draw on built-in
functions of the utilized computer algebra system GP/PARI
1
assuming that
they work correctly and fast enough for our purposes--which, in one thing,
they do not quite do, as we will see. The bottleneck is the isomorphism-test
for two given number fields which is unfortunately responsible for the fact that
we have only been able to compute results for relatively small values of X. If
this test could be improved significantly--in general or for the special case
of totally real cubic fields, we would immediately be able to carry out much
more comprehensive computations and choose much larger values for X. Since
developing a "better" such test would break the mold of this thesis, we have to
be content with what is presented in the appendix.
Another way of getting rid of the described bottleneck up to some degree would
of course be the utilization of much more CPU time by using faster computers.
All computations have been carried out on a usual modern personal computer
so that there was no chance to obtain more or better results. More details on
the general computational setup will be given in Chapter 5.
1
The original plan of carrying out all computations with the computer algebra system
KASH has been overruled after spotting a bug in KASH that we did not want to bother
about, namely the irreducibility-test for polynomials, which does not work correctly.
Besides that, GP/PARI seems to be (at least for our purposes) several times faster than
KASH.
2. Preliminaries
6
2. Preliminaries
Let us begin with some preparations. We start with the essential definitions and
propositions we will build our theory upon although the fundamental algebraic
basics are assumed to be well-known (e.g. field extensions, irreducibility of
polynomials etc.) As a great reference for essential algebraic concepts (and
beyond), we recommend the textbook by Hungerford, 1974. The key elements
we will deal with are totally real algebraic number fields of degree 3. From the
beginning on, many of the definitions in this and the following chapters are
given in a way which is suitable for our special situation where we are looking
at cubic fields as algebraic field extensions of the rational numbers
Q of degree
3. Generalizations are usually straightforward and can easily be derived from
the more specialized case. However, if a more general formulation than the one
needed for our situation is of any interest (for whatever reason), or is as easy
to understand as the specialization to our case, this formulation is given (in
these cases, either the specialization to our case is trivial or it is given as a
remark) or we refer to an appropriate reference. As a solid introduction to the
topic of number fields in general, we refer to the textbook by Marcus, 1977.
2.1. The Theory of Number Fields
At first, we give the most important definition of a totally real algebraic
number field which will be essential throughout the whole thesis. We proceed
with several additional definitions to introduce notions which will be of high
importance for the whole discussion of the theory.
2. Preliminaries
7
Definition 2.1 (Totally real algebraic number field). An algebraic number
field K (in the following often only called number field or even just field) is a
finite degree field extension of the rational numbers
Q. Thus, Q is contained
in K and K can be considered as a finite-dimensional vector space over
Q. K
is called totally real if for all embeddings of K into the complex numbers
C,
the image lies inside the real numbers
R. Number fields of degree 3 are called
cubic fields.
For field elements
K we will now define the trace and norm as well as the
notion of conjugates and the characteristic polynomial.
Definition 2.2 (Trace and norm of a field element). Let (
1
, . . . ,
n
) be an
arbitrary basis of K. For each
K we have a transformation T
: K
K
defined by
T
(y) = y.
Hence, for every element
K there is an associated square matrix A() =
(a
ij
)
1i,jn
which is defined via
i
=
n
j=1
a
ij
j
, i
{1, . . . , n}.
The trace of the element , denoted Tr(), is defined as the trace of A() and
the norm of , denoted N(), is defined as the determinant of A() where
Tr(A()) is, as usual, the sum of the elements of the main diagonal of A().
An alternate and, in some cases, more vivid definition can be found in Hunger-
ford, 1974.
Definition 2.3 (Trace and norm of a field element in terms of K-monomorphisms).
Let F be a finite dimensional field extension of K and ¯
K
an algebraic closure
of K with F
¯
K. Let
1
, . . . ,
r
be the distinct K-monomorphisms with
j
: F
¯
K for all j
{1, .., r}. For F , the trace of is the element
Tr() = [F : K]
i
(
1
() +
2
() +
· · · +
r
())
2. Preliminaries
8
and the norm of is the element
N() = (
1
()
2
()
· · ·
r
())
[F :K]
i
where [F : K]
i
is the inseparable degree of F over K (see Hungerford, 1974,
Definition 6.10).
Definition 2.4 (Conjugates and degree of a field element). Let K be a number
field of degree n. For
K we define its conjugates
(1)
, . . . ,
(n)
as the n roots
of the minimal polynomial p
(t) of in K. As usual, p
Q[t] is the monic
polynomial of least degree k such that p
() = 0. The number k is called degree
of the field element . We denote the k distinct values among the set of the
(j)
by
1
, . . . ,
k
.
Definition 2.5 (Characteristic polynomial of a field element). Let K be a
number field of degree n. For
K we define the characteristic polynomial of
as
(t) :=
n
j=1
(t
-
(j)
)
where
(j)
are the n conjugates of .
Remark 2.6. Let k be the degree of a field element in a number field K =
Q(x)
of degree n. Then k
| n and an equivalent definition of the trace and the norm
of can be given in terms of
(1)
, . . . ,
(n)
and
1
, . . . ,
k
. With m :=
n
k
we have
Tr() =
n
j=1
(j)
= m
k
j=1
j
for the trace as well as
N() =
n
j=1
(j)
=
k
j=1
j
m
2. Preliminaries
9
for the norm (see Milne, 2009, Proposition 2.19 and Corollary 2.20). The
minimal polynomial p
can of course be written as
p
(t) = t
k
- a
k-1
t
k-1
+
· · · + (-1)
k
a
0
and the characteristic polynomial
is given by
(t) =
k
j=1
(t
-
j
)
m
so that altogether this leads to the fact that we can use Tr() =
-ma
k-1
and N() = a
m
0
, respectively, as expressions for the trace and the norm of .
In particular, for field elements of degree n, we have Tr() =
-a
n-1
and
N() = a
0
. A root x of the polynomial f which defines the number field K is
an example for a field element of degree n.
A fact we will later make use of is given by the following lemma. The lemma
is formulated for the case n = 3 which we are more interested in than in the
general case and for which the necessary calculations are more vivid than for
the general case. However, the result can easily be generalized to arbitrary
number fields.
Lemma 2.7.
Let K be a totally real number field of degree 3. If
(t) = t
3
-at
2
+
bt
-c is the characteristic polynomial of K then for Q the characteristic
polynomial of
K is given by
(t) = t
3
- at
2
+
2
bt
-
3
c
.
Proof. For 1
j 3 let
(j)
R be the conjugates of . By simple computation
we obtain
(t) = (t
-
(1)
)(t
-
(2)
)(t
-
(3)
)
= t
3
- t
2
(
(1)
+
(2)
+
(3)
)
+ t(
(1)
(2)
+
(1)
(3)
+
(2)
(3)
)
-
(1)
(2)
(3)
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2011
- ISBN (PDF)
- 9783961162468
- ISBN (Paperback)
- 9783956366802
- Dateigröße
- 486 KB
- Sprache
- Englisch
- Institution / Hochschule
- Technische Universität Berlin
- Erscheinungsdatum
- 2018 (Juni)
- Note
- 1,7
- Schlagworte
- Algorithms Number Fields Minimalpaar Minimality Minimal Pair Asymptotics
