% To be compiled with AmsTeX 2.0 or later
%\documentstyle{amsppt}
\magnification=\magstephalf
% \nologo
\font\sans=cmss10
\def\ltextindent#1{\hbox to \hangindent{#1\hss}\ignorespaces}
\def\litem{\par\noindent\dimen0=\parindent%
\advance\dimen0 by-4pt
\hangindent=\dimen0\ltextindent}
\def\llitem{\par\noindent
\hangindent=\parindent\ltextindent}
\def\stno#1{\litem{\sans #1}}
\def\exno#1{\llitem{\rm #1}}
\def\t{\theta}
\def\p{\goth p}
\def\q{\goth q}
\def\om{\omega}
\def\eps{\varepsilon}
\def\Gal{\operatorname{Gal}}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\R{\Bbb R}
\def\F{\Bbb F}
\def\fp{\qed}
\def\bb{\bold b}
\def\N{\operatorname{\Cal N}}
\def\Tr{\operatorname{Tr}}
\def\ov#1{\overline{\vphantom{T}#1}}
\def\leg#1#2{\fracwithdelims(){#1}{#2}}
\def\gd{{\goth d}}
\def\isom{\simeq}
\def\disc{\operatorname{disc}}
\def\nli{\newline\indent}
\centerline{\bf Errata et Addenda to the Second Corrected Printing of the Book}
\smallskip
\centerline{\bf A Course in Computational Algebraic Number Theory}
\smallskip
\centerline{by \bf Henri Cohen}
\smallskip
\centerline{(19960419 version)}
\medskip
{\obeylines
Graduate Texts in Mathematics 138, Springer-Verlag, 1993,
Second Corrected Printing 1995, XXII + 534 pages.
ISBN 3-540-55640-0 Springer-Verlag Berlin Heidelberg New York
ISBN 0-387-55640-0 Springer-Verlag New York Berlin Heidelberg
\bigskip
p. VII\quad lines 1 and 2, put Serre and Stark in correct alphabetical order
p. VII\quad line -1, instead of ``Vallee'' read ``Vall\'ee''
p. XII\quad line 20, instead of ``being is'' read ``being''
p. XII\quad lines -4 to -2, replace text starting with ``For Chapter 7,..'' and ending with ``preparation'' by ``For Chapter 7, [Sil] and [Sil3] are excellent books, and contain numerous exercises''
p. 24\quad line 9, instead of ``result'' read ``results''
p. 30\quad line 4, instead of ``step 2'' read ``step 3''
p. 30\quad line 6, instead of ``odd value of $b$'' read ``odd value of $a$''
p. 34\quad line -12, instead of ``$01$, and hence $v_{\p}(p)=1$. But then we will have
$v_{\p}(\alpha+p)=1$ (otherwise $v_{\p}(p)=v_{\p}((p+\alpha)-\alpha)>1$),
and still $v_{\q}(\alpha+p)=0$ for all other primes $\q$ above $p$, and so
$v_p(\N(\alpha+p))=f$ as before, thus proving the lemma.\fp
Note that the condition $v_p(\N(\alpha))=f$, while sufficient, is not a
necessary condition (see Exercise 20).
Note also that if we write $\alpha=\sum_{1\le i\le k}\lambda_i\gamma_i$
where the $\gamma_i$ is some generating set of $\p$, we may always assume
that $|\lambda_i|\le p/2$ since $p\in\p$. In addition, if we choose
$\gamma_1=p$, we may assume that $\lambda_1=0$.
This suggests the following algorithm, which is simple minded but works
quite well.
\proclaim\nofrills{\bf Algorithm 4.7.10}{\rm\ (Two-Element
Representation of a Prime Ideal). }{\sans Given a
prime ideal $\p$ above $p$ by a system of $\Z_K$-generators $\gamma_i$ for
$(1\le i\le k)$, this algorithm computes a two-element representation
$(p,\alpha)$ for $\p$.
We assume that one knows the norm $p^f$ of $\p$ (this is always the case
in practice, and in any case it can be obtained by computing the HNF of
$\p$ from the given generators), and that $\gamma_1=p$ (if this is not the
case just add it to the list of generators).\smallskip
\stno{1.}\quad [Initialize] Set $R\gets1$.\smallskip
\stno{2.}\quad [Set coefficients] For $2\le i\le k$ set $\lambda_i\gets R$.\smallskip
\stno{3.}\quad [Compute $\alpha$ and check] Let
$\alpha\gets\sum_{2\le i\le m}\lambda_i\gamma_i$,
$n\gets\N(\alpha)/p^f$, where the norm is computed, for example, using
the sub-resultant algorithm (see Section 4.3). If $p\nmid n$,
then output $(p,\alpha)$ and terminate the algorithm.
Otherwise, set $n\gets\N(\alpha+p)/p^f$. If $p\nmid n$ then output
$(p,\alpha)$ and terminate the algorithm.\smallskip
\stno{4.}\quad [Decrease coefficients] Let $j$ be the largest $i\le k$
such that $\lambda_i\neq -R$ (we will always keep $\lambda_2\ge0$ so $j$
will exist). Set $\lambda_j\gets\lambda_j-1$ and for $j+1\le i\le m$ set
$\lambda_i\gets R$.\smallskip
\stno{5.}\quad [Search for first non-zero] Let $j$ be the smallest
$i\le k$ such that $\lambda_i\neq 0$. If no such $j$ exists (i.e.~if all
the $\lambda_i$ are equal to 0) set $R\gets R+1$ and go to step 2.
Otherwise go to step 3.}
\endproclaim
\medskip
{\bf Remarks.}
1) Steps 4 and 5 of this algorithm represent a standard backtracking
procedure. What we do essentially is to search for
$\alpha=\sum_{2\le i\le k}\lambda_i\gamma_i$, where the $\lambda_i$ are
integers between $-R$ and $R$. To avoid searching both for $\alpha$ and
$-\alpha$, we add the condition that the first non-zero $\lambda$ should
be positive. If the search fails, we start it again
with a larger value of $R$. Of course, some time will be wasted since many
old values of $\alpha$ will be recomputed, but in practice this has no
real importance, and in fact $R=1$ or $R=2$ is usually sufficient.
The remark made after Lemma 4.7.9 shows that the algorithm will stop
with $R\le p/2$.
2) It is often the case that one of the $\gamma_i$ for $2\le i\le k$ will
satisfy one of the conditions of step 3. Thus it is useful to test this
before starting the backtracking procedure.
We refer to [Poh-Zas] for extensive information on the use of two-element
representations.''
\smallskip
{\obeylines
p. 195\quad line -2, instead of ``{\it If $p=\prod_{i=1}^g\goth p_i$ is an unramified prime in $K$}'' read ``{\it If $p$ is an unramified prime in $K$ with $p\Z_K=\prod_{i=1}^g\goth p_i$}''
p. 197\quad line 10, instead of ``{\sl essential\/}'' read ``{\sl inessential\/}''
p. 199\quad line 10 and line 11, instead of ``$q_j$'' read ``$\frak q_j$''
p. 199\quad middle, instead of ``$p^{-1}=R+aR$'' read ``$\p^{-1}=R+aR$''
p. 201\quad line -4, instead of ``$Z[\theta]$'' read ``$\Z[\theta]$''
p. 203\quad line -4 until p. 204 line -12, replace completely by the following.
}
\smallskip
``To compute the inverse of an ideal $I$ given by a $\Z$-basis $\gamma_j$
represented by an $n\times n$ matrix $M$ on the integral basis as above,
we thus proceed as follows. Computing $T^{-1}$ we first obtain a
basis of the codifferent $\gd(K)^{-1}$. We then compute the {\it ideal}
product $I\gd(K)^{-1}$ by Hermite reduction of an $n\times n^2$ matrix
as explained in Section 4.7.1. If $N$ is the HNF matrix of this ideal
product, then by Proposition 4.8.19, the columns $(N^tT)^{-1}$ will form
a $\Z$-basis of the ideal $(I\gd(K)^{-1})^{-1}\gd(K)^{-1}=I^{-1}$, thus
giving the inverse of $I$ after another HNF. In paractice, it is better
to work only with integral ideals, and since we know that $\det(T)=d(K)$,
this means that we will replace $\gd(K)^{-1}$ by $d(K)\gd(K)^{-1}$ which
is an integral ideal.
\smallskip
This leads to the following algorithm.
\proclaim\nofrills{\bf Algorithm 4.8.21}{\rm\ (Ideal Inversion). }{\sans
Given an integral basis $(\om_i)_{1\le i\le n}$ of the ring of integers
of a number field $K$ and an integral ideal $I$ given by an $n\times n$
matrix $M$ whose columns give the coordinates of a $\Z$-basis $\gamma_j$
of $I$ on the $\om_i$, this algorithm computes the HNF of the inverse
ideal $I^{-1}$.\smallskip
\stno{1.}\quad [Compute $d(K)\gd(K)^{-1}$] Compute the $n\times n$ matrix
$T=(t_{i,j})$ such that $t_{i,j}=\Tr_{K/\Q}(\om_i\om_j)$. Set
$d\gets\det(T)$ (this is the determinant $d(K)$ of $K$ hence is usually
available with the $\om_i$ already). Finally, call $\delta_j$ the elements
of $\Z_K$ whose coordinates on the $\om_i$ are the columns of $dT^{-1}$
(thus the $\delta_j$ will be a $\Z$-basis of the integral ideal
$d(K)\gd(K)^{-1}$).\smallskip
\stno{2.}\quad [Compute $d(K)I\gd(K)^{-1}$] Let $N$ be the HNF of the
$n\times n^2$ matrix whose columns are the coordinates on
the integral basis of the $n^2$ products $\gamma_i\delta_j$ (the
columns of $N$ will form a $\Z$-basis of $d(K)I\gd(K)^{-1}$).\smallskip
\stno{3.}\quad [Compute $I^{-1}$] Set $P\gets d(K)(N^tT)^{-1}$, and let
$e$ be a common denominator for the entries of the matrix $P$. Let
$W$ be the HNF of $eP$. Output $(W,e)$ as the HNF of $I^{-1}$ and
terminate the algorithm.}\endproclaim\medskip
{\bf Remarks.}
\roster\item If many ideal inversions are to be done in the same number
field, step 1 should of course be done only once. In addition, it may
be useful to find a two-element representation for the integral ideal
$d(K)\gd(K)^{-1}$ since this will considerably speed up the ideal
multiplication of step 2. Algorithm 4.7.10 cannot directly be used for
that purpose since it is valid only for prime ideals, but similar
algorithms exist for general ideals (see Exercise 30). In addition,
if $\Z_K=\Z[\t]$ and if $P[X]$ is the minimal monic polynomial of $\t$,
then one can prove (see Exercise 33) that $\gd(K)$ is the principal
ideal generated by
$P'(\t)$, so the ideal multiplication of step 2 is even simpler.
\item If we want to compute the HNF of the different $\gd(K)$ itself,
we apply the above algorithm to the integral ideal $d(K)\gd(K)^{-1}$
(with $M=d(K)T^{-1}$) and multiply the resulting inverse by $d(K)$ to
get $\gd(K)$.''\endroster
\smallskip
{\obeylines
p. 204\quad (if the replacement above is not made) line -14, instead of ``$p_i$'' read ``$\frak p_i$''
p. 213\quad line -2, instead of ``Brauer-Siegel'' read ``Brauer-Siegel theorem''
p. 217\quad {\bf Addendum.} Add the following exercises.
}
\smallskip
\exno{``29.}\quad Let $\p$ be a prime ideal above the prime 2 in a
number field $K$ such that $e(\p/2)=2$. Show that the congruences
$x^2\equiv a\pmod{\p^3}$ have a solution for $a=-1$ and $a=-2$.
\smallskip
\exno{30.}\quad Let $I$ be an integral ideal in a number field $K$ and
let $\ell(I)$ be the positive generator of $I\cap\Z$.\nli
a) Show that
$$\ell(I)=\prod_{p\mid\N(I)}p^{\max_{\p\mid p}\lceil v_{\p}(I)/e(\p/p)\rceil}\enspace.$$\nli
b) Let $\alpha\in I$ be such that $(\N(I),\N(\alpha)/\N(I))=1$. Show that
$$I=\ell(I)\Z_K+\alpha\Z_K=\N(I)\Z_K+\alpha\Z_K$$
(this is a partial generalization of Lemma 4.7.9).\nli
c) Deduce from this an algorithm for finding a two-element representation
of $I$ analogous to Algorithm 4.7.10.\smallskip
\exno{31.}\quad Let $\p$ be a prime ideal in a number field $K$, and
denote by $p$ the prime number below $\p$, by $e=e(\p/p)$ the ramification
index, and by $f=f(\p/p)$ the residual degree of $\p$. The goal of this
exercise is to find the Abelian group structure of $\Z_K/\p^k$ and also of
$(\Z_K/\p^k)^*$ in a number of cases.\nli
a) Let $k\ge1$ be an integer, and let $k-1=qe+r$ be the Euclidean division
of $k-1$ by $e$, with $0\le r1$ be an integer'' read ``Let $h>1$ be an integer such that $h\equiv1\pmod{F_0F_1F_2F_3F_4}$''
p. 439\quad line -4, instead of ``modulo $p$'' read ``modulo $\frak p$''
p. 441\quad line -7, instead of ``$y=tx$'' read ``$x=ty$''
p. 446\quad line 5, -12 (twice) and line -8, instead of ``$n$'' read ``$N$''
p. 448\quad line 7, instead of ``$an=p^{v_p(a)-v_p(b)}b$'' read ``$an=p^{v_p(a)-v_p(b)}bm$''
p. 456\quad line 1, instead of ``{\sans If $p\ge3$}'' read ``{\sans If $p\ge3$ or $p=2$ and $k=2$}''
p. 456\quad line 7, instead of ``$j^2\left(\chi_{2,q}^{2^{k-3}},\chi_{2,q}^{2^{k-3}}\right)$'' read ``$j^2\left(\chi_{2,q}^{2^{k-3}},\chi_{2,q}^{3\cdot2^{k-3}}\right)$''
p. 457\quad line 4, instead of ``$2\delta_N$'' read ``$\delta_N$''
p. 459\quad line 16, instead of ``$Z/N\Z$'' read ``$\Z/N\Z$''
p. 464\quad line -8, instead of ``(resp. 6)'' read ``(resp. six)''
p. 467\quad Step 12, instead of ``{\sans P}'' read ``$P$''
p. 471\quad middle, instead of ``$(V,U,(U^2-D)/(4V)$'' read ``$(V,U,(U^2-D)/(4V))$''
p. 474\quad line 5, instead of ``[Coh-Len1]'' read ``(see Section 5.10.1 and [Coh-Len1])''
p. 497\quad Exercise 8, instead of ``$x\in\Z_K$'' read ``$x=a+b\theta\in\Z_K$'' and at the end replace ``.'' by ``, where $\leg{x}{\p}$ is defined in Exercise 19 of Chapter 4.''
p. 497\quad line 1 of Exercise 9, instead of ``numbers the'' read ``numbers, the''
p. 518\quad in [Bac-Sha], instead of ``in preparation'', read ``{\it Vol. 1: Efficient Algorithms\/}, MIT Press, Cambridge, Mass, 1996''
p. 521\quad after [Sil], insert the following.
}
\smallskip
``[{\bf Sil3}] J.~Silverman, {\it Advanced Topics in the Arithmetic of
Elliptic Curves\/}, Graduate texts in Math. {\bf 151}, Springer-Verlag,
New-York, 1994.
\smallskip
The long awaited sequel to [Sil].''
\smallskip
{\obeylines
p. 521\quad in [Arn], instead of ``(to appear)'', read ``{\bf 64} (1995), 335--361''
p. 521\quad after [Arn], insert the following new reference:
``[{\bf ARW}] S.~Arno, M.~Robinson and F.~Wheeler, {\it Imaginary quadratic fields with small odd class number\/}, to appear.''
p. 522\quad after [Bre2], insert the following new reference:
``[{\bf Bre3}] R.P.~Brent, {\it The first occurence of large gaps between successive primes}, Math. Comp. {\bf 27} (1973), 959--963''
p. 523\quad line -15, in [Coh-Mar3], instead of ``(to appear)'', read ``{\bf 63} (1994), 329--334''
p. 524\quad line 3, before [Duv] insert the following reference:
``[{\bf Duk}] W.~Duke, {\it Hyperbolic distribution functions and half-integral weight Maass forms\/}, Invent. Math. {\bf 92} (1988), 73--90.''
p. 525\quad middle, put the reference to [Mart] in correct alphabetical order between [Mah] and [Maz]
p. 526\quad add the complete references to [Nag] and [Nag-Kou] as follows:
``[{\bf Nag}] K.~Nagao, {\it An example of elliptic curve over $\Q(T)$ with rank $\ge13$\/}, Proc. Japan Acad. {\bf 70} (1994), 152--153.''
``[{\bf Nag-Kou}] K.~Nagao and T.~Kouya, {\it An example of elliptic curve over $\Q$ with rank $\ge21$\/}, Proc. Japan Acad. {\bf 70} (1994), 104--105.''
p. 530\quad insert index entry ``Duke, W.'', 293
p. 530\quad remove entry ``essential discriminantal divisors, 197''
p. 531\quad add entry ``inessential discriminantal divisor, 197, 357''
}
\end