Codes from Algebraic Number Fields

H.W. Lenstra, Jr.

Un/versiteit van Amsterdam, Mathematisch Instituut
P.O. Box 19268, 1000 GG Amsterdam, The Netherlands

INTRODUCTION

The geometry of numbers, coding theory, the Riemann hypothesis - the list of
key words for this lecture can be read s a partial history of the Stichting
Mathematisch Centrum. The lecture itself attempts to reflect the spirit of the
SMC by displaying a new connection between these subjects. Using ideas
from the geometry of numbers one can construct a class of codes from algebraic
number fields, and the study of the asymptotic properties of these codes
depends on the generalized Riemann hypothesis.
The construction described in this lecture is a generalization to algebraic
number fields of the following idea to make a code. Let P be a finite set of
prime numbers, and consider, for a suitable positive integer k, the set C of all
elements
c, = (imodp)peP e J J Z/pZ,

i = 1,2, . . . ,k.

peP

If, for i>j, the elements cc} of this set agree on many coordinates then the
difference / j is divisible by many primes, so also by their product. But this
difference is less than k, which may lead to a contradiction. This gives us control over the minimum distance of C.
The codes just described have several undesirable properties. First, they are
mixed codes in the sense that the alphabet size p is not constant. Secondly,
they are non-linear, although they are still 'half-linear' in the sense that for any
two distinct x,y&C one of y, y belongs to C. Thirdly, for bounded
alphabet size the above construction gives only finitely many codes. This
means that the usual 'asymptotic' way of judging the quality of a class of
codes, which we discuss in Section l, does not apply to them. Finally, the

96

H W Lenstra Jr

codes that we descnbed are m all respects inferior to the codes that are
obtained in an analogous way if one replaces the ring Z by the polynomial
ring fqiX] m one vanable over a suitably chosen fimte field F ? , and P by a
collection of polynomials of the form with e F ? These codes, the generahzed Reed-Solomon codes [6, Chapter 10, Section 8], have at least the same
mimmum distance and dimension, they are linear and non-rmxed, but they do
have the third shortcoming just mentioned
If we generahze the construction to algebraic number fields, s we do in Section 2, the Situation changes only slightly For any algebraic number field
different from Q it is true that the nng of integers has different pnme ideals
with isomorphic residue class fields Hence it would seem possible to make
non-rmxed codes by the same recipe However it turns out that it is better to
make non-rmxed codes by startmg from mixed codes that have a slight Variation in the alphabet size This leaves at least the possibility open to obtain
satisfactory asymptotic results (see the remark on r = q at the end of Section 3)
Our codes remam non-lmear, even the 'half-lmeanty' mentioned above
disappears
For fixed alphabet size, the new construction gives mfimtely many codes, so
that in pnnciple their quahty can be analyzed asymptotically Section 3 contams upper and lower bounds for how good our codes are These bounds can
be substantially improved if one assumes the truth of the generalized Riemann
hypothesis, but even then there is a considerable gap between the upper and
the lower bound
The new codes are the analogues, for number fields, of the codes constructed
by Goppa and Tsfasman [7, 12] from curves over fimte fields For the analogy
between number fields and curves over fimte fields, see [l, 14] If the generalized Riemann hypothesis is true our codes are, asymptotically speaking, not s
good s those of Goppa and Tsfasman Also, the latter codes are linear and
non-mixed
We finally note that there is a non-constructive element in the descnption of
our codes, so that it is still too early to ask for encoding and decoding algonthms It can be imagmed that lattice basis reduction algonthms [5] play a
role m this context
l CODES

In this section we follow MANIN [7, Section 2], except that we do not require
codes to be linear
Let q be an integer, q>\, and V a set of cardmality q, to be referred to s
the alphabet For each integer 3=0 we define a metric w on the set V" by lettmg w(x,y) be the number of coordmates where a n d / differ A code over V
is a non-empty set C that for some integer 3=0 is a subset of V" The
number n is called the ward length of the code The dimension dim(C) of the
code is defined to be (log#C)/(log<7), where # denotes cardmality The
mimmum distance or simply distance d(C) of the code C is the mimmum of the
numbers w(x,y) if (x,y) runs over all pairs of disnct elements of C, for
# C - l this is + oo

Codes 1mm algebraic number fields

97

We are mterested m findmg codes for which the dimension and the distance
are large s functions of the word length. Each code C of positive word length
n and positive dimension gives nse to a pomt (d(C)/n, dim(CVn) of the umt
square [0, l] 2 . If C runs over all such codes we ob tarn a sequence of points in
the umt square, and we denote by Uq the set of limit points of this sequence
(If q is a prime power, this set contams the correspondmg set from [7].)
As in [7] we have the followmg result (but not necessanly with the same
function aq)
THEOREM

(1.1). There is contmuous function 9 .[0, 1][0, 1] such that

Uq = {(x,R): 0<<1, 0< <,(*)}

The function aq assumes the value l m x0, is strictly decreasmg on the mterval
[Q,(q-l)/ql
and vamshes on the mterval [(q~l)/q,\]
Moreover, for
\)/q one has

where

(sketch). It is easy to make codes that show that the points in the umt
square that he on the coordmate axes belong to Uq. Next let (x,R)&Uq.
Tnvial constructions on codes, such s omitting code words or changing
letters, show that the rectangle [0,x]X[Q,R] is contamed m Uq. Other constructions, such s projecting a code CC.V" to V"~l or mtersecting it with a
suitably embedded V""1 C.Vn, show that the line segments connecting (x,R)
with (Q,R/(l-x))
and (x/(l-R),0)
are contamed m Uq (These line Segments form part of the lines connecting (x,R) with (1,0) and (0,1).)
These results imply that Uq can be descnbed, s m the theorem, by means
of a non-increasing function aq, that aq is contmuous except possibly at 0, and
that it is stnctly decreasmg on the mterval where it does not vamsh
The Plotkin bound [13, Theorem 5.25] implies that aq vamshes on
[(q - \)/q, 1], and by the above results this leads to the upper bound stated m
the theorem. The lower bound is the Gilbert-Varshamov bound [13, Theorem
519] It imphes connuity of aq at = 0
This concludes the proof of the theorem
PROOF

For better upper bounds on aq we refer to [13, Chapter 5] Only recently a

better lower bound was found, and only for relavely large q. This was done
with the help of modular curves and Shimura curves over fimte fields [12].
The followmg result is useful m companng the asymptotic properties of the
codes that we shall construct with the Gilbert-Varshamov bound

98

H W Lenstra Jr
(12) Lei r eR, r 3* l Then the line

PROPOSITION

log<?
is tangent to the graph of q at the point (XO,RQ), where
X

q +r -

log?

(q+r-\)\oiq
The proof is straightforward
2 NUMBER FIELDS

Let K be a numberfield,i e a field that is of fimte degree m over the field Q of

rational numbers, and let s,ieZ be such that there is an isomorphism
K<^QU^KSXC' of R-algebras Denote by A the ring of mtegers of K, and
by the absolute value of its discnminant over Z The norm 9l( of a nonzero pnme ideal of A is the cardmahty of its residue class field A /t> For
background on algebraic number theory we refer to [2, 11]
THEOREM (21) Let K be a number field, and s, t, s above Let r,q be mtegers
sattsjymg Kr<:q, and write

n = s+t + #$

rssgiCW^sS for some

here p ranges over the non-zero pnme ideals of the ring of mtegers of K Then
for any positive integer d there exists a code of word length n over an alphabet of
q letters with distance at least d and dimenswn at least

Let it first be assumed that K is totally real, s = m, t=0 Under

the embedding KCKQn^Mm
the nng A becomes a lattice, and if F denotes
a fundamental domain for A then F has volume vol(F)= /
Let U be the set of those (,)= elRm for which
PROOF

1 </

" > /m for

This is an open subset of R m , and vol(t/) = r" + 1 ~' /

In analogy with the construction mentioned in the mtroducon one would
now be inchned to make a code from the set U A A basic prmciple of the
geometry of numbers suggests that #U^A
is approximately equal to
vol(i/)/ VA", but it turns out that the error term may dommate To solve this
problem we average over all translations of U, which is a 'non-constructive'
element in the descnption of the code
Let denote the charactenstic function of U We have

Codes from algebratc number fields

99
=

/ X(y~z)dz = 2

/x(z)dz

X(z)dz

ye/4 z&yF

y&A zef

= vol(C7) = /

zeR

where we use that Um is the disjoint union of the sets^y F, yeA. It follows
that there exists ze^ 1 with #((z + i/)rU)Ssvol(l/)/V~. Let such a z be
chosen, and put C= (z + U) n A. Then we have
n + l-rf

" VA '
Let K={0,1, , ? - ! } . For each ye{l,2, , / } we define a map
z + {/-> V by dividing the projection of z + U on the y'-th coordinate axis into q
intervals of equal length; i.e., the point z + (*,)"= , ez + U is mapped toveVif

Restricting this map to C we obtain a map^ :C-K

For each t> s in the defim'tion of n choose a positive integer k () with
/<9lO)*(p)s9 and an injective map /^ ( ) - Let / P : C ^ F be the composed map CC^-X/^ ( P ) -K.
Combining all maps fjt ff we obtain a map / :C-* V". We claim that
^y, then w(f(x),f(y))^d

where w denotes the Hamming distance (see Section 1). To prove this, let be
the number of / s for which fj(x)=fj(y) and b the number of jj's for which
/ p (x)=/p(y), so that a+b=n -w(f(x\f(y)).
Denote by N-.K-^Q the absolute value of the norm function. We estimate N(x y) in two ways. On the
one hand, all conjugates of xy are less than r("+ ^-d)/m m a ]j S C ) j u t e v a } u e
and of them are even a factor q smaller, so
N(x-y)

< rn + l-d/q" < r + \-d-<,_

On the other hand, y is a non-zero algebraic integer belonging to b of the

ideals p*^', which each have norm at least r, so that
N(x -y) > rb.
It follows that b<n +\-da, so w(f(x),f(y)) = n-ab>d. This proves
the claim.
It follows in particular that / is injective. Hence the code /[ClC V" has
dimension (log#C)/(log^), which is at least (( + 1 d)logr log \/)/ (logg).
By the claim, the distance of /[C] is at least d.
This proves the theorem in the case that K is totally real. To deal with the
general case in the same way one needs an analogue, in the complex plane, of
a real interval that is divided into q intervals that are q times s small. More
precisely, one needs the following result.

1 00

H W Lenstra, Jr

For every positive integer q there exists subset of the euchdecm plane that hos
area q/2 and diameter *iVq, and that can be written s the umon of q sets of
diameter <1.
If q is a square this is proved by subdividing a square of area q/2 into q
squares in the obvious way. We leave the elementary proof of the general case
to the reader. The result can actually be improved, which gives rise to a
slightly better lower bound for the dimension of the code, if />0.
This completes the proof of the theorem.
To describe the asymptotic properties of the codes from Theorem (2.1) we
introduce the following quantity. Let r,q be s in the theorem. Then we
define
. , .
.. . , losV
A (q,r) - hminf ,

nlogq
the liminf rangmg over all number fields K, up to isomorphism, with n, s
in the theorem.
COROLLARY

(2.2). The segment of the hne

for which Q^x, R ^ l lies entirely m the code domam Uq.

This is an immediate consequence of Theorem (2.1) and the results of Section 1.
3. ASYMPTOTICS

Let A (q,r) be s defined in Section 2.

PROPOSITION (3.1). There are positive constants c\, c2 such that
and A(q,q)^?c2/]ogqfor all mtegers r,q with \<.r*iq.

A(q,r)'^cl/q

PROOF. For a number field , let m,A, be s in Section 2. Known lower

bounds for discriminants (see [9]) imply that there is a positive constant c 3
such that logA>c 3 m for all Kj^Q.
Moreover, it is obvious that
n < w ( l + ir(qj), where ir(q) denotes the number of prime numbers ^q, and
that n^2m if r=q. Since Tr(q)^c4q/logq for some positive constant c 4 and
all q, the proposition follows. This proves (3.1).
It is amusing to note that the first inequality of (3.1) can also be deduced
from (1.1) and (2.2), s follows. It is easy to see that n is maximal if r is the
least integer ^Vq; so let this be the case. Putting x = (q \)/q in (2.2) and
using that ^ vanishes in this point one finds that

Codes from algebraic number fields

101

so A (q,r)^l/(2q), s required.
The second inequality of (3.1) is best possible, apart from the value of the
constant, s we shall see in (3.4). The first inequality of (3.1) can be sharpened
if we assume the generahzed Riemann hypothesis:
(GRH) for every number field K, the Dedekmd zetafunctwn has no complex
zeroes with real part larger than 1/2.
PROPOSITION (3.2). Let for every integer q > l and every number field K the
quantity Bq(K) be defined by
Ba(K) = (\(

Here the summatwn ranges over non-zero prime ideals lp of the ring of mtegers of
K, and s,f,A,9lG>) are s m Section 2. Further, denotes Euler's constant. Suppose moreover that (GRH) is true. Thenfor every integer q>\ we have
limsup B9(K) < l,
the limsup ranging over all number fields K, up to tsomorphism.
PROOF. This is an easy consequence of WeiPs 'explicit formulae' in the theory
of pnme numbers, cf. [9, 10, 4]. This proves (3.2).
PROPOSITION (3.3). Assume (GRH). Thenfor all mtegers r,q with \<r<q one
has
^W'';-

/-

Vq l
PROOF. This follows from (3.2) by a direct calculation. This proves (3.3).
Next I consider upper bounds.
PROPOSITION (3.4). There is a positive constant c$ such that
for all mtegers r, q with Kr<q.
PROOF. By the theory of infinite class field towers [2, Chapter IX] there exists
a number field E such that the maximal totally unramified extension L of E is
of infinite degree over E. We let K rnge over the finite extensions of E that
are contained in L, and for each K we let m,,s,t,n be s in Section 2. Each
K is unramified over E, so the number A1/m is independent of K. Also, one
has n ^s +1 ^m II. It follows that

r f log VA
hminf
K,ECKCJL

7
logg

102

H.W. Lenstra, Jr.

for some positive constant c 5 . This proves (3.4).

By (3.1), the inequality of (3.4) is best possible for r = q, apart from the value
of the constant. If r is much smaller than q we can again use the generalized
Riemann hypothesis to obtain a better result. For the sake of definiteness I
choose r to be the least integer
(3.5). Suppose that (GRH) is Irue. Then there is a positive consuch that for every integer q>\
we have A(q, [(q + l)/2])

PROPOSITION

stant c6

The proof depends on two lemmas.

LEMMA (3.6). Suppose that q is an integer, q>\,
integers. Write

and that k,l are positive

where p, denotes the i-th prime number. Suppose that thefollowing two conditions
are satisfied.
(i) fc + l<j(/-l) 2 -(/-l);
(ii) there are at least k prime numbers p with Vq/2 =/? i \fq for which the
Legendre symbol (
) equals 1.
Then we have
A

(q, [(q-

PROOF. Let E be the imaginary quadratic field with discriminant d. Each/?

s in (ii) generates a principal prime ideal of the ring of integers of E with
9/2<9())4. Let S be a set of k such prime ideals. Denote by L the maximal totally unramified extension of E in which all t>eS split completely.
Using a slight generalization of the theory of infinite class field towers (see [4,
Section 14]) one deduces from inequality (i) that L is of infinite degree over E.
(Since all JieS are principal, the number / from [4, Section 14] equals / l,
and p=k + l.) To prove the lemma, let now K rnge over the finite extensions
of E that are contained in L, s in the proof of (3.4). As before, the number
A1/m is independent of K, and putting K=E one sees that it equals vd. Also,
since each feeS splits completely in K one has n^t + [K:E]-#S = -m(l+k)
for each K. This proves (3.6).
LEMMA (3.7). Assume (GRH). Then for every positive real number c1 there is a
positive real number c% with the following property.
Let d be a positive integer for which d is the discriminant of a quadratic

Codes from algebraic number fields

1 03

field. Then for every real number with x>c 8 (logrf) 2 the number of odd prime
numbers p for which

w at least c7(log</)2/loglogi/.
PROOF. This is proved by a slight adaptation of the proof of [8, Theorem 13.1;
pp. 120, 123, 124] (the weight function (l n/N) should be changed so s to
count primes in the right interval). I thank H.L. MONTGOMERY for pointing
this out to me.
PROOF OF (3.5). For any integer 1^7, let k =k(l) be the largest integer satisfying (3.6)(i), and let d-d(l) be s in (3.6). Then we have

\ogd ~ /-log/,

k ~ (l/4)(lo gi /) 2 /(loglo gi /) 2

for /-oo, so there is certainly a positive constant c 7 such that

fcsSc7(logi02/loglogi/ for all /3*7. Let c 8 be the number that Lemma (3.7)
guarantees to exist.
Now let q be an integer, q> l, and choose the integer / s large s possible
subject to the condition Vq^cs(\ogd(l))2.
We suppose that q is sufficiently
large for / to be well-defined and > 7 . By the choice of c 7 and Lemma (3.7),
the conditions of (3.6) are satisfied for k=k(l) and /, so (3.6) gives us an upper
bound on A (q, [(q + 1)/2]). We have
c9q}/\
k ~ (l/4)(lo gi /) 2 /(loglo gi /) 2 ~ c
for certain positive constants c 9 , c IO , s </-oo. It follows that the upper
bound from (3.6) leads to the upper bound stated in Proposition (3.5), at least
for q sufficiently large. For the remaining values of q one can apply (3.4).
This proves (3.5).
We discuss the implications of our estimates for coding theory.
The first inequality of (3.1) yields a rather crude upper bound for how good
we can expect our codes to be. I do not know how this bound compares to
the best upper bounds that are known for the function aq of Section 1. It is
conceivable that these, together with (2.2), lead to a better lower bound for

A(q,r).
The second inequality of (3.1) shows that it is not advisable to apply our
construction only with r =q. By (1.2) that would at best lead to codes that are
comparable to the codes realizing the Gilbert-Varshamov bound.
Proposition (3.3) is the analogue of the result that was proved by DRINFELD
and VLADUT [3] for function fields of curves over finite fields. For very small
q, such s q2, it shows that one should not expect our codes to lead to a
point (x,R) of the code domain Ug with and R positive. For large q, Propositions (3.3) and (1.2) show that one can still hope to find codes that beat the
Gilbert-Varshamov bound. In the case of function fields this hope was indeed

104

H W Lenstra, Jr

realized for certain values of q, see [12].

It is apparently harder to construct good codes from number fields. Proposition (3.4) leads to codes whose performance is comparable to the GilbertVarshamov bound. Proposition (3.5) shows that much better codes can be
made, for large q, if one again accepts (GRH). However, these codes are not
s good s those made with function fields, and there remains a substantial
gap between the bounds of (3.3) and (3.5). The analogy with function fields
suggests that (3.3) is nearer to the truth than (3.5).
RjEFERENCES
1. E. ARTIN,

2.
3.

4.

5.
6.
7.
8.
9.

10.
11.

12.

13.
14.

G. WHAPLES (1945). Axiomatic charactenzation of fields by the

product formula for valuations. Bull. Amer. Math. Soc. 51, 469-492; pp.
202-225 in: The Collected Papers of Emil Artin, Addison-Wesley Publishing Company, Reading 1965.
J.W.S. CASSELS, A. FRHLICH (eds.) (1967). Algebraic Number Theory,
Academic Press, London.
V.G. DRINFELD, S.G. VLADUT (1983). On the number of points on an
algebraic curve (in Russian). Funktsional. Anal. i. Pnlozhen. 17 (1), 68-69;
English translation: Functional Anal. Appl. 17, 53-54.
Y. IHARA (1983). How many pnmes decompose completely in an infinite
unramified Galois extension of a global field? / . Math. Soc. Japan 35,
693-709.
A.K. LENSTRA, H.W. LENSTRA, JR., L. Lovsz (1982). Factoring polynomials with rational coefficients. Math. Ann. 261, 515-534.
FJ. MAC WILLIAMS, N.J. A. SLOANE (1978). The Theory of ErrorCorrectmg Codes, North-Holland Publishing Company, Amsterdam.
Yu.I. MANIN, (1981). What is the maximum number of points on a curve
over F2? / . Fac. Sa. Univ. Tokyo Sect. IA Math. 28, 715-720.
H.L. MONTGOMERY (1971). Topics m Multiphcave Number Theory, Lecture Notes m Math. 227, Springer-Verlag, Heidelberg.
G. POITOU (1977). Minorations de discriminants (d'apres A.M. Odlyzko).
Semmaire Bourbaki 28 (1975/76), no. 479, pp. 136-153 in: Lecture Notes m
Math. 567, Springer-Verlag, Heidelberg.
G. POITOU. Sur les petits discriminants. Semmaire Delange-Pisot-Poitou
(Theorie des nombres) 18 (1976/77), no. 6.
P. SAMUEL (1967). Theorie Algebnque des Nombres, Hermann, Paris;
English translation: Algebraic Theory of Numbers, Houghton Mifflm Company, Boston 1970.
M.A. TSFASMAN, S.G. VLADUT, TH. ZINK (1982). Modular curves,
Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound.
Math. Nachr. 109, 21-28.
J.H. VAN LINT (1982). Introductwn to Codmg Theory, Graduate Texts m
Math. 86, Springer-Verlag, New York.
A. WEIL (1939). Sur Panalogie entre les corps de nombres algebnques et
les corps de fonctions algebnques. Revue Scient. 77, 104-106; pp. 236-240
in: Oeuvres Saentifiques l Collected Papers, vol. I, Springer-Verlag, New
York 1979.