FAUSSKY 1959 KiowaLU! TiifX.r/vs

WPUCATE

NATIONAL BUREAU OF STANDARDS REPORT

3052

Some Computational Problems in Algebraic Number Theory

by

Olga Taussky

\

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Sinclair Weeks, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Aslin, Director THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following listing of

the divisions and sections engaged in technical work. In general, each section is engaged in special*

ized research, development, and engineering in the field indicated by its title. A brief description

of the activities, and of the resultant reports and publications, appears on the inside of the back

cover of this report.

Electricity. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Applied Electricity. Electrochemistry.

Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels. Cryogenic Engineering.

Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry. Solid State

Physics. Electron Physics. Atomic Physics. Neutron Measurements. Infrared Spectroscopy.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

Chemistry. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry.

Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing and Specifications. Polymer Structure. Organic Plastics. Dental Research.

Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy. Corrosion.

Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Concreting Materials. Constitution and Microstructure. Chemistry of Mineral Products.

Building Technology. Structural Engineering. Fire Protection. Heating and Air Conditioning. Floor, Roof, and Wall Coverings. Codes and Specifications.

Applied Mathematics. Numerical Analysis. Computation. Statistical Engineering. Machine

Development.

Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic

Instrumentation.

Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

Ordnance Development. These three divisions are engaged in a broad program of research

Electromechanical Ordnance, and development in advanced ordnance. Activities include

Ordnance Electronics. basic and applied research, engineering, pilot production, field testing, and evaluation of a wide variety of ordnance materiel. Special skills and facilities of other

NBS divisions also contribute to this program. The activity is sponsored by the Department of

Defense.

Missile Development. Missile research and development: engineering, dynamics, intelligence,

instmmentation, evaluation. Combustion in jet engines. These activities are sponsored by the

Department of Defense. • Office of Basic Instrumentation • Office of Weights and Measures.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

1102-10-1104 January 15, 1954 3052

Some Computational Problems in Algebraic Number Theory

fcy

Olga Taussky

The preparation of this paper was supported (in part)

under a contract between the National Science Foundation

and the National Bureau of Standards

.

<NBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

The publication, reprin Approved for public release by the

unless permission is obt Director of the National Institute of

25 ,D.c, Such permisi Standards and Technology (NIST)

cally prepared If that 0 n October 9, 2015

ait, Is prohibited

ards, Washington

I has been speclfl1 for Its own use.

Some Computatio 1 F . 2 mi in Algebraic I- \ m Ti so y

. hv

01 q a Taos sky

It is frequently claimed that many facts in ordinary

number theory can be fully understood only through their

generalization to algebraic number fields. A typical fact

is the exceptional role played by the prime number 2 in many

cases. However, in number fields one proves with ease that

ell numbers \ -

£ play an VJ - w > t io i 1 role when £

is a root

of unity. Another 83 mple is the quadratic law of reciprocity for which a really illuminating proof is o .iy I o trad;

by acipg number fields. Also the Fermat problem is frequently

a 1 1 a cl©d vi a : i; umb 5 a f i a 1 d s . However, the study of number theory in these fields provides its own difficulties and has still to deal with many

open problems. Progress in this subject is particularly hindered by the greatly increased difficulties of numerical examples compared to the rational field.

In this brief report concerning computational problems in

algebraic number theory only problems concerning - the most fundamental concepts are mentioned. A list of tablework concerning algebraic number fields - there is not much of it -

The preparation of this paper was supported (in part) u

a contract l at ?e tl •• National Science Found ctlo" f N a t ion a 1 Bure a u of St a & d

a

rd s .
.

-
~2

can be found in Lehmer's Guide [ 1 ] . Many other problems

have come up (see e.g. [2]).

1 . Integral bases . It is known that for fields of degree

> 3 an integral base cannot always be found which consists of

the powers of a single algebraic integer only. Although the

existence of an integral base for any field is easily established, its construction presents difficulties (see e.g. [3]).

2 . F actorization, of rational primes in number fields . An ordinary prime number p will, in general, not remain a prime number in a given algebraic number field F , but split

up into a product of powers of prime ideals:

e. e > =

>’

i •••?.. •

Apart from a finite number of primes p, namely the- divisors

of the disc rirainant of F, we have e_; - 1 , The question is: what are the possible values of r and

f . of the ? Further, since norm = p

' , what are the f . ? The laws which govern these numbers are not known to full extent in all fields. A great number of important facts are

known about them and their structure is completely clarified

in eyclotomic fields and their subfields. The extensions

of class field theory to general algebraic extensions have

not yet cleared up the decomposition laws of rational primes

in arbitrary fields. So special numerical work in this
.

.

;
connection is very desirable. Recently Kuroda [4] computed

n soma results concerning non -abelian fields of degree 2".

Like many other computations in algebraic number theory,

the splitting of rational primes can be treated by rational

methods only. This fact matters very much if computation by

automatic computing machinery is considered. Only the knowledge of the irreducible polynomial £(x) a zero of which generates the field in question is needed.

For the following facts hold for all but a finite number

) of primes [5]. Let

e, e

i r

f (x) = P, . . . F (p)

i f

where P . is an irreducible polynomial mod p and P. r P«. mod p

i =/ k. Then p splits up in the form

e o

1 •** |r

3. wive re If the degree of Fj is i. then norm

J;. = p

0. Ore [6 n] extended the method just described to include all prime numbers by considering congruences mod p

l

where r is sufficiently large.

3. Units . Other important problems arise in connection

with the units in fields. To find the- units is not always

easy. The main problem is to find a set of base units.

In complex quadratic fields there are no units apart from

roots of unity. In real quadratic fields there is one
'

.

D

.

.

.
-4—

base unit £ and .oil other units are of the form + £"'

,

n = 0, ±1} ±2, .i « f

. If d is the discriminant of the field then

the unit 6 is of the form (x + y vd)/2 where x, y are the

smallest positive solutions of (x - dy )/4 = + 1 . There

is a rational routine method for finding £ by means of continued fractions. It is being used on 3EAC , the National

Bureau of Standards Eastern Automatic Computer.

A routine method for finding a' unit in cyclic cubic field

which together with its conjugates generates all the units

was given by Basse [3],

Units in non cyclic cubic fields were treated by several

authors (see [9] where more references can be found, see

also [ 1 ])

.

Let p > 2, be a prime number. The base unit of the field

generated by Vp can be put into the form (t + u vp)/2. decently Ankeny, Artin, Chowla [10] inquired whether u P 0(p).

They verified this for p

= 5(3) and p < 2000. This eonjectur

was later verified by K. Goldberg on SEAC up to p < 100,000.

4. Ideal classes and class numbers . Tables for the class

numbers of real quadratic fields have been made by Irtce [ll]

and for the cyclic cubic fields by Basse [3], Basse has a routine method for finding the class numbers in cyclic cubic

fields, but it is rather complicated.

If no routine method is aimed at, the work is sometimes

simpler. A bound for the class number and a method for com-
'

.

.
_c_

pus ting it is given by the k nowp thee rem:

In each class there is g 75 id eel whose i~-orm does not

exc eed v Id 1 whe r e d i s th

3

d iscr i r> ant of i h

e

field. A

s h a r ' y > bO " d Is ( t- ~ * V

1,1

n

n

1 dl , (-33 [ 12 ]). It is furt

Down that

im ( s - i ) ^ ( s )

where h Is the class number, and

rp a*

... . 2 l(2./0.

2

V / d|

Here R Is the regulator of the field, d the discriminant,

tv the number of roots of unity, r, the number of real con- jugate fields, 2?2 the number of complex ones, and

r f.) -e... J-

' (nopin/®)"

where ja. runs through all ideals in the f ield. [This sum

converges for all s > l].

Although this expression for the class number is very

complicated it is yet very useful.

F u rt-her , there are many facts v/h e:;: knowledge can cut

clown the work considerably in special cases. Quite a umber

of facts are known about the class number in cyclotoraic

fields and their subfields. These fields have been investigated more closely, partly because they are more accessible,
,
-- 0-

:3 <S r tly because of their importance to the Fermat problem.

Many results concerning class numbers in these fields go back

to Kummer and to Si. Weber. Later P. Furtwangler [ 1 3

?

'! *+ ] generalized some of their results, s.g» , he proved that the

class number of the field generated by the X ~th root of

unity is divisible by X if and only if the class number of

the field generated by the i-th root of unity is. Let further f 5 F be two subfields of the field of the \—tfo root

of unity and f c F. He then proved that the class number of

f divides that of F. Recently a book by Masse [15] appeared

which is concerned with the class number in these fields and

their largest real subfields . It contains many new theorems

and tables.

A. Scholz [l6], E. loaba [17]? 0. Taussky [l8] and others

studied the subfields of prime degree X of cyclotomic fields.

The subfield of degree X of the field generated by the p~th

root of unity (p a prime = 1 (-2) ) has a class number prime to

X • On the other hand, a subfield of degree X of the field

generated by the p^-th roots of unity has always a class

number divisible by X if p., = 1 ($)

,

= 1 (X) are two different primes and if the field is not contained in the field of

the p.,-th or the p^-th roots of unity. The class number of

o such a field is not divisible by X if one, at least, of

the two congruences

X^ = P 1 (p2

).» = P2

(p-j)

has oo rational solutions.

An example of such a case is i = 3? P-j = 7? P2 = 13. This

means that the class number of a cubic subfield of the field

of the 91 - st root of unity (which is not a subfield of the

field of the 7~th or 13~th root of unity) is divisible by 3?

but not by 9. for one of these fields it will now be shown

that its class number is actually 3.

It can easily be checked that

f(x) = x^ - 7. 1 3x f 3

# 7* 1 3 - 0

has discriminant 11 » 7

^* 13 ^ and that any of its roots 0 defines

a cyclic cubic field whose discriminant is 7

^* 13 ^. ^rqpi^a

refinement of Minkowski's theory (see [19]? also [ 12/yfor even

sharper results [ 20 J ) it follows that for a cyclic cubic

field with discriminant D there is in every ideal class an

ideal aAsuch that

2 —

no rm ML < ~ VD.

In our case this gives norm /A < 20. The prime numbers 3? 11?

19 split up into 3 factors in the field while 2,5? 17 remain

prime numbers. It is therefore only necessary to examine in

what classes the prime ideal factors of 3?11?19 lie. Since
.
-3-

the class number is divisible by 3 , but not by 9 , only the class numbers 6 , 12 , 15 come in question.

The class numbers 6 or 15 are impossible, since in such a case

the 2-class group or the 5 - class group of the field would have

to be cyclic. In this case let p be a prime ideal belonging

to a class of order 2 or 5. Let e.g., the 2-class group be

cyclic. In this case we would have

.,s a

where s is a generating automorphism of the Galois group of

the field and a is a rational integer. Hence

.3

This implies a J = 1(2) which implies a = 1(2). This means

that 1 and hence

the 5-class group.

In order to show that the class number 12 cannot occur,

we prove that the prime numbers 3> 11 , 19 are norms of numbers

or their third powers are. For this purpose we compute the

norms of some numbers x + yQ by means of the formula:

y ~ 1 . The same argument applies for

o 2 2 3

norm (x + y©) - x*" - ax y

+ bxy - c

y

J

if ©^ + aQ^ + b© + a = 0

•

We obtain:

norm (1 + 9) = -3* 11^

Ropra (2 - 9) - 3

2

*11

suorm (5 - 9) = —3

®

1

9

' iso no (3 - 9) = 3^.

The se facts imply that ths class number of the field is 3.

A treatment by rational methods is also possible for the

classes, at least in many cases [21 ], [22], [ 23 ]. If the

field admits an integral base which consists of the powers

of a single number, then there is a 1-1 correspondence between the ideal classes and the classes of nxo matrices s ‘as

where A is a fixed matrix with f(A) = 0. The elements a. v ,

JL i£ s.. A = (a.,), S = (S .

.

) are rational integers and S

jL & Ik ik

runs through all matrices with l3( = + 1

,

In complex quadratic fields the class number exceeds

unity apart from a finite number of cases. This was conjectured by Gauss and proved by Heilbronn [24-]. He also proves

with Linfoot [25] that for m > 163 , at most one further m

is possible such that the field F (fin) has class number unity.

It is still an open question whether there is a further m. Work by Lehmer [ 26 ] indicates that probably no further m

exists.

F0p class numbers in non-cyclic cubic fields , see again

[l] and [ 9

~\

.

5 . Principal ideali zation . 7TT¥tne r complicated computation concerns

- 10-

the application of the following famous theorem of Hilbert

([27]? theorem 9*+ 5 Zahlbericht) . Let f be a field and F a relatively cyclic extension of relative degree i of I a is a prime number). Let all prime ideals of f split up

in F into different prims ideals. Then there exists an ideal

in f which is not a principal ideal in f, but which is

principal in F. Further, that ideal in f lies in a class of

order X and the class number of f is divisible by Ji . If the class group of f is cyclic then there is no further

problem, but if the class group has at least 2 base classes

then the following problem arises?

Given such an f and F, which class of f is the one that

does go over into the principal class in F?

If f is a quadratic field ft(vm) and Z - 2 this is not too

difficult. However, if X - 3 the difficulties increase. In

the first place: one has to go a long way to find a field with

3-class number > 9 and oon-cyclic class group. The first

imaginary quadratic field with this property is FW-3299). it

has 3-class number 27. A field with 3-class number 9 and

non-cyclic class group is F (V-i+027) . Also for this arcbiem

a rational method was found to succeed (see [23], [ 29 ]).
:

' • ;
BIBLIOGRAPHY

1. D. H. Lehmer, Guide to tables in the theory of numbers . National Research Council, Washington, D. C.,

19*+

1

.

2. J. von Neumann and H. H. Go Id stine, A numerical study of

a conjecture by Knmme

r

« MTAC vol. 7(1953)

pp. 133-134.

' 1

3. M. Hall , Indices in cubic fields , Bull. Amer. Math. Soc

.

vol. 43(1937) , pp. 104-108. '

4. S. Kuroda, Uber die Zerlenung rationaler Primzahlon in

oeivissen nichtabelscher Koroern . Math. Soc,

Japan Jn,

f vol. 3(1951)? pp. 143-156.

5. R. Dedekind, Ge s immelte math. Werke I, Vieweg and 5ohn,

Braunschweig, 1930, pp. 202-232.

6. 0. Ore, Uber den Zns nmmerhanq t: wise hen den dei Inter end en

Gleichunoen und der Idealtheori® in alae- braischen Zahlkdroern (Erste Mitteilung)

,

Math. Armalen, vol. 96(1927)? pp. 313~352.

• 9 7. 0. 0 re, Uber den Zusammenhang zwischen den def f nierenden

Gleichunoen und der Idealtheorie in alneb raise hen Zahlkoroem (Zweite Mitteilung)

Math. Annalen, vol. 970927)? pp. 569-593.

3. H. Basse, Arithme tische Bestimmung von Grundeinheit end

Klassenzahl i n zyklischen kubischert u n

d

biauadra t 1 s c he n Z

a

hlkoroer n, Abh. d dStrfes ch , Akad .d Miss . , Math . -naturv . Klasse , Jahrgang

1948, No. 2, Berlin, 1950 .

9. J.W.S. Cass els, The rati o nal s olutions of the diophantine

ecuatioo V

2, = x3 - Acta Math. vol.

320950), op. 243-273.

10. N. C. Ankeny, E. Art in, S. Chowla, The class number of rea l

quadratic number fi elds , Annals of Math. vol.

560952), pp. 5-79-4-93.

'

11. E. L. Ince, Cycles of reduced ideals in Quadratic field s. British Association for the Advancement of

Science, Math. Tables IV, London, 1934.

12. H. Masse, Zahle nt heor i-e , Akademie-Verlag , Berlin

; 19^c

;

%

1 *° 13. P. Fur twahgl e r , Uber die Klassensahlen Ahslscher Zahl- korper , Journ. reins angew. Math. vol. 1 3^

(1903), pp. 91-95.

1*t. P. Furtwangler, Ub-er die Klassenzahlen der Kpeisteilunqs- kdrper . Journ. reine angew. Math. vol. Ih-0

(19^1), pp. 29-32.

“

'

1 5 . H . Basse, User die Klassenzahl abelscher Zahlkoree ? , Ak ademie-Verlag , Berlin, 1952.

1 6 . A. Seholz , Zwei Bemerkimaen zum Klassenkoroert:: ::ra

, Jolirn.

reins angew. Math, vol. 1 61(1929), pp. 2C1-207,

17. E . In a b a , liber die Strnkt u ? der .l-Klas sengrunpe zyklischer

Zahlkdppor vom Primzahlgrad A , Jou rn . Fac

.

Sci., Imp. Univ. Tokyo, vol. IV 2(19*+0),

op. 61-1 1 5.

13. 0. Tans sky, A remark on an ramified deer field s. J. London

Math. Soc vol. 12(1937), pp. 36-3o.

19. H. Mi- ":ows ii, Dlehteste qltterformige Lags rung kongmer-t vr Korper , Gott. Nachr. 190*+ , pp. 311-355.

20. H. davenport, Note on the product of three home ,, mejoys

line i ? forms . J. London Math. Soc. vol. l6

"(19^-1) , pp. 93-101.

21. 0. Taus si-/ , On a theorem of Latimer end MacDuffes , Can. J.

Math.

/ vol. l('i9*+9), pp. 300-302,

22. 0 . Tan s s ky , Classes of matrices d qu adratic fields , Pec.

J. of Math.

f vol. 1(1951)5 an. 127-132.

. 0. Tans, ky, Class - ma tp

i

c e s and Q

:

a d r

a

\ t- i

c

,.1 A II

J. London Math. Soc. vol. 27(1952), on.

237-239. '

9r. Ii. He i 1 b r o nn , On the class-number ir imaa'.a ary quadratic fields . Quart. J. Math. Oxford vol .5(1 93'+)~

pp. 150-160. '

25. H. Heilbronn and E. H. Liofoot, Or. the imaginary quadr atic

corpora of class-nym"- 0 ? ore , Quart. J . Math.

Oxford, vol. 50 93*+) , pp. 293 _ 301 .

- 13-

26. D. H. Lehmer, On imaginary quadratic fields whose class

number is unity . Bull. Amer. Math. Soc.,

vol. 39(1933), p. 360.

27. D. Hilbert, Gesammelte Abhandlunoen I, Springer, Berlin,

1932.

23. A. Scholz and Olga Ta«-,sky, Die Hauptideale der kubischen

Klas senko rper imaginbr quadratischer Zahl- korper : ihre rechnerische Bestimmunq und ihr

Einfluss anf den Klassenkoroerturm . J. reine

angew. Math. vol. 1 71

C

1 93^) , pp . i"9 -1+1 .

29. 0. Taussky, Arnold Scholz zum Gedachtnis . Math. Nachr. vol.

7(1952), ppT 375-336. '

National Bureau of Standards

Washington, D. G.

THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The functions of the National Bureau of Standards are set forth in the Act of Congress, March

3, 1901, as amended by Congress in Public Law 619, 1950. These include the development and

maintenance of the national standards of measurement and the provision of means and methods

for making measurements consistent with these standards; the determination of physical constants and properties of materials; the development of methods and instruments for testing materials,

devices, and structures; advisory services to Government Agencies on scientific and technical

problems; invention and development of devices to serve special needs of the Government; and the

development of standard practices, codes, and specifications. The work includes basic and applied

research, development, engineering, instrumentation, testing, evaluation, calibration services, and

various consultation and information services. A major portion of the Bureau’s work is performed

for other Government Agencies, particularly the Department of Defense and the Atomic Energy

Commission. The scope of activities is suggested by the listing of divisions and sections on the

inside of the front cover.

Reports and Publications

The results of the Bureau’s work take the form of either actual equipment and devices or published papers and reports. Reports are issued to the sponsoring agency of a particular project or program. Published papers appear either in the Bureau’s own series of publications or in the

journals of professional and scientific societies. The Bureau itself publishes three monthly periodicals, available from the Government Printing Office: The Journal of Research, which presents

complete papers reporting technical investigations; the Technical News Bulletin, which presents

summary and preliminary reports on work in progress; and Basic Radio Propagation Predictions,

which provides data for determining the best frequencies to use for radio communications throughout

the world. There are also five series of nonperiodical publications: The Applied Mathematics

Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous

Publications.

Information on the Bureau’s publications can be found in NBS Circular 460, Publications of

the National Bureau of Standards ($1.00). Information on calibration services and fees can be

found in NBS Circular 483, Testing by the National Bureau of Standards (25 cents). Both are

available from the Government Printing Office. Inquiries regarding the Bureau’s reports and

publications should be addressed to the Office of Scientific Publications, National Bureau of Standards, Washington 25, D. C.
J

I

I

)