Ein neuer Algorithmus für absteigende Basispotenzen im kubischen Körper

Ein neuer Algorithmus fur absteigende Basispotenzen im kubisehen Korper

Herrn Professor Dr. JOSEF NAAS zum 60. Geburtstag gewidmet

Von LEON B:ERNSTEIN in Tel-Aviv

(Eingegangen am 20. 1. 1966)

I. J. P. Algorithmus und Abanderungen

In einer Reihe fruherer Arbeiten ist es Verf. [I] gelungen, Periodizitat eines Algorithmus nachzuweisen, der an n - 1 in einem algebraischen Zahlenkorper K ( w ) gelegenen Zahlen ausgeubt wird. Dabei ist w eine algebraische Irrationalitat n-ten oder geringeren Grades, im allgemeinen Wurzel einer Gleichung mit rationalen Koeffizienten der Form

(1) f ( w ) = Z;=o ai w ~ - ~ ; no, a, =t= 0 ,

so da13 K (w) der durch w uber dem Korper der rationalen Zahlen erzeugte algebraische Zahlenkorper ist.

Die nach ihren Begrundern JACOBI [ 2 ] und PERRON [3] vom Verfasser JAGOBI-PERRONSCher Algorithmus (J. P. Algorithmus) benannte Rechen- vorschrift verlauft folgendermafilen :

Aus n - 1 vorgegebenen reellen Zahlen

ay), n y , . . . , U%-, (0) ( 2 ) werden neue Folgen von je n - 1 Zahlen durch folgende Verknupfungs- regeln gebildet

Dabei ist immer unter [XI die gmze Zahl X mit x 5 X < x + 1 zu ver- stehen,

(4) = [at)] ( I c = I, . . ., n - I; w = 0, I, . . .). 17 Math. Nachr. 1067, Bd. 33, H. 516

258 Benistein, Ein neuer Algorithmus

Gibt es eine nichtnegative Zahl s und eine naturliche Zahl t derart, da13 bf+G) = b(Z') il. (k = 1,. . . ) n - 1; v = s, s + 1, . . .) (5)

und sind die s, t die kleinsten Zahlen derartiger Beschaffenheit. so heil3en die s Zeilen

(6)

(7)

b p

b y

(k = 1 , . . . , n - 1; t' = 0, I , . . . , s - 1)

die (primitive) Vorperiode des Algorithmus und die t Zeilcn

(k = I. . . . . ? & - 1: 21 = 0, 1, . . . , f - 1 )

seine (primitive) Periode. 1st s = 0, so lieifit der Algorithmus rein yeriodisch; s und t heiBen Laenge der Vorperiode bzw. der Periode; die Summe s - t heiBt Lange des Algorithmus.

Die n - 1 Ausgangszahlen a!') hatteii in den Arbeiten des Verf. die Form

(6) ap' = a:') (w) = .q=, k, 7c' ( 8 = 1 , . . . , n - I),

wareii also Polynome ansteigenden Grades. und in dieser Reihenfolge wurde der A41gorithmus an ihnen ausgefuhrt .

Wie aus (3) ersichtlich, kommt es bei unendlicher Portsetzung cles Algorithmus einzig und allein auf das Bildungsgesetz der bv) an; diese haben im J. P. Algorithmus die Form (4); nun stellte es sich bald heraus, daB dieses Bildungsgesetz nur in ganz bestimmten, vom Verf. aufgedeckten, zwar unendlich vielen Zahlenkorpern K (w) zu Periodizitat des Algorithmus hinfuhrt, im allgemeinen aber darin zu versagen scheint, obgleich diese Frage zu den bisher ungeklarten und wahrscheinlich schwierigsten Pro- blemen der Zahientheorie gehoren diirfte. Auf den Spuren nach Periodizitgt hat nun Verf. einen abgeanderten, den sogenannten modifiizierten J . P. Algorithmus entdeckt, der so verlauft :

D < w < D + 1 .

Es sei D eine geeignet gewiihlte Zahl und

(9) Dann gilt fur das Bildungsgesetz der a:') , die wegen (8) und den rationalen Operationen (3) im allgemeinen die Form a:') (w) haben,

(10)

(11) [ z a ] = D . also ist im Hinblick auf (10)

(12) Doch hat der modifizierte J. P. Algorithmus den fur den Zahlentheoretiker schwerwiegenden Nachteil, da13 hier die br) nicht notwendig ganze Zahlen

bl" = n y ( D ) (i = 1 , . . .. 7L - 1; 2, = 0, 1, . .).

1st D eine ganze rationale Zahl. so gilt naturlich

b:') =u~" ) ( [u . ] ) ( i = I,. . .. n - 1; 21 = 0, I,. . .).

Bernstein, Ein neuer Algorithmus 259

sind. Stellen wir diese beiden Bildungsgesetze der bp) einander gegeniiber, so haben wir :

fur den J . P. Algorithmus : br ) = [a?) (w)] , fur den modifizierten Algorithmus : bp) = a?) ([w]) . Nun kann Gleichheit beider Algorithmen eintreten, namlich

(13) und das war in meinen fruheren Arbeiten [I, a) - h)] tatsachlich der Fall. Dort hatten die n - 1 Ausgangszahlen meistens die Form:

[ap)(w)l = ar)([wl) (i = I, . . ., n - I; ZI = 0, I, . . .),

w, wz, . . . ) Wn-l. , n ~~

w = C/m , m positiv rational, n 2 2 . (14)

Nun hat Herr HASSE, dem ich die Anregung zum Studium des J . P. Al- gorithmus verdanke, die Frage aufgeworfen, ob Periodizitat auch bei einer anderen Anordnung der Potenzen von w als der durch (14) gegeben eintreten konnte. Dem aber haben sich alle Bemuhungen, sogar die modernster Rechenanlagen, bisher hartnackig widersetzt. Verf. ist es aber neuderdings gelungen, in einer umfangreichen, dem Crelle Journal eingereichten Arbeit, einen Algorithmus zu definieren, mittels dessen Periodizitat (zwar mit ziemlich grofjer Periodenlange) auch ini Falle absteigender Potenzen

1 , . . . ) w2, w als Ausgangswerte gewahlt, eintritt. Hier sind auch die by) wieder ganz- zahlig. Im kubischen Falle, also fur die Ausgangswerte

(15) w = ( D J + D, d natiirlich, dlD

handelt es sich (wie auch fur jedes nz 2 ) um einen reinperiodischen Al- gorithmus. Dieser hat fur n = 3 die Form

W n ~ 1 wn - 2

w2, w -+ D,

0 2 2 0 0 Dld D”ld 2 0 0 D D21d 2 Dld 0 D

11. Der neue Algorithmus

Der vomVerf. in der oben beschriebenen Arbeit angewandte Algorithmus ist im allgemeinen recht komplizierter Natur. Zwar hat er seine Kraft an der Periodizitat von wn-’, w”-~, . . . , w2, w als auch in den Fallen erprobt, 1 i*

260 Bernstein, Ein neuer Algorit~hmus

n wo w eine vie1 kompliziertere Irrationalitat als 1 m darstellt. Ob seine An- wendung dariiber hinaus Friichte tragen wird, ist noch nicht entschieden.

I n der vorliegenden Arbeit wird nun ein neuer Algorithmus eingefiihrt, der vor allem durch seine markante Einfachheit vielversprechend zii sein scheint. Er lehnt an den JAcoBIschen als auch a n den modifizierten Al- gorithmus an und umfaat beide als Spezialfalle. Es sei wieder

& ) = ap)(zu) f K ( w )

b!') = [aIz')([w])]

(i = 1. . . ., n - I; 2, = 0, I, . . .>. f 16) Dann gilt

(17) ( i = 1 . . . .. n - 1 ; u = 0, 1 , . . .). Der Kern der vorliegenden Arbeit liegt nun in folgendem

Satz. Es sei

1181 213 = ( D J + D , d nttturlich; i !d lD .

Fuhrt man an d e n Zahlen (19) 2c1, w

den Algorithmus ( 3 ) mittels des Bildungsgesetzes ( 1 7 ) durch, so wird der Al- gorithmus periodisch; die Vorperiode hat d i e Lange l und die Form

t 20) DL, D . Die Periode hat die Lange t = 9 und d i e Form

0 0 0 0 0 0 3 D2ld 3 D'/d 0

3D/2d 2 0 2 0 3DIPd 3 0 D (DD4 + 3dD)ld' D 3 0

Die Periodenlange ist jur alle Werte con D , d immer = 9 ; sie ist also priniitiv. Beweis. Da D, d 2 1, d ] D ; 0 < d < 30 ' + 3 0 + 1 , so

D < ( 0 3 + d)lI3 < D + 1 ,

gilt naturlich

(22) [w] = D .

Also wird hier

(23) by) = [ap)(D)] (i = 1, 2 ; v = 0, 1, . . .).

Bernstein, Ein iieuer Algorithmus 261

Wegen (24) .I"' = W2) ap = w

und im Hinblick auf (23) ist

blo' = [D?], (0) - D? (0) - b(0) = w2 - DZ;

bp) = [ D ] , b(0) = D, ( 2 5 ) b l - 7 2

(26) a1 1 L 2 a(o) - b(O) = w - D .

Nun ist wegen (18) w3 = 0 3 + d ; (w - D)(w2 + W D + 0 2 ) = d ,

( 2 7 ) ~ _ - 1 w? + W D + D'

w - D - d

Sus (3), (26)) (27) ergibt sich

w2 + W D + 0 2

d ( w + D) "'1' = 1 w + D'

"fl) = (28) 2

Wegen (17) ergibt sich aus (28)

also

Aus (28), (29) ergibt sich

und in1 Hinblick auf (3)

(W - D ) ( ~ w + D ) 2 d

== ; a f ' = w + D . ( 30)

Aus (30) ergibt sich wegen (17)

262 Bernstein, Ein neuer Algorithmus

Aus (30), (31) ergibt sicli

also, im Hinblick auf (3) und wegen (27)

Aus (32) erhaken wir im Hiliblick auf ( 1 7 )

also

somit, im Hinblick auf ( 3 )


Aus ( 3 4 ) , (35) ergibt sich

2 w + D 3 0 W - D -___ - - - b(*) - -

und daraus, im Hinblick auf (3) und wegen (27)

(36)

ad d '> -

2 d

wz + WD + D' = --___ -. ~~

I = - . W ' W

Aus (36) ergibt sich im Hinblick auf (17)


~2 - 2 w D + D' ( w - D ) ? - - - _ -

2 W W

und daraus, im Hinblick auf ( 3 )

(38) a:" =; (w - D)a; uy) = w .

Ails (38) ergibt sich im Hinblick auf (17)

bi6) = [ ( D - D)2]; bp) = [ D ] , also (39) bf') = 0; bf) = D,

und aus (38)) (39)

a?) - b?) = (w - D)2. a(") - b(6) = w - D , 2 2

also, im Hinblick auf (3) und (27)

w2 + W D + 0 2

d - ____ -

9

(w2 + W D + 0 2 ) 2

d2 w ~ + ~ w ~ D + ~ w ~ D ~ + ~ w D ~ + D ~

- _ ~ _ ~ -

264 Bernstein , Ein neuer Algorithmus

Aus (40) ergibt, sich im Hinblick auf (17)

Aus (-lo), (41) ergibt sich

(u) - D)(w + 2 D ) C l

- ~ - ~ ,

Daniit ergibt sich im Hinblick auf ( 3 ) und ( 2 7 )

Aus (42) ergibt sich iiii Hinblick auf (l'i)

nun ist

und da 3D'ld ganz und 0 < 1i3D < 1 ist,, so ergibt sich



1

w + 2 0 ’ - 3 D 2 ~ + 6 0 3 + d - 3 0 2 ( ~ + 2 0 ) - - -

d (w + 2 0 )

w2 + u;D + D? - w D - 2 0 2 742 - D2 - - -

w + 2 0 w + 2 0 ’

und daraus im Hinblick auf (3)

= w2 - 0 2 . , C L ~ ~ ’ = w + 2 0 . (44) Aus (44) ergibt sich im Hinblick auf (17)

also big) = [DZ - 0 2 1 ; b y ) = [3 D] ,

(45) by) = 0; b y ) = 3 0 .

Aus (44), (45) ergibt sich a(9) - b(9) = w2 - 0 2 ; (9) - b(9) = w - D

I I a3 2

und daraus, im Hinblick auf (3) und (27)

Vergleicht man (28) mit (46), so ergibt sieh ,J!lo) = (1) L ,J2 3

a ( l o ) = ( 1 ) (47) 1 a1 ;

womit nachgewiesen ist, da13 der Algorithmus der Zahlen w2, w mit dem Bildungsgesetz [ap)( lwl )] fur die Zahlen b r ) (i = 1, 2 ; v = 0, 1 , . . .) periodisch ist init Vorperiodenlange s = 1 und Periodenlange t = 9. Die Formeln ( 2 5 ) , (as), (31), (33), (35), (37), (39), (41), (43), (45) sagen aus, da13 Vorperiode und Periode die im Xatz behauptete Form haben und primitiv sind, womit derselbe restlos bewiesen ist.

111. Einheiten irn Korper K(w)

I n einer- mit Professor HASSE gemeinsam verfal3ten Arbeit wurde bewiesen, dal3 fur

w = ( 0 3 + d)’I3; d , D naturlich; dl D

-)fjfj Bernstein, Ein neuer Algorithmus

eine Einheit des Korpers K ( w ) durch

(48) e =

gegeben ist. Da K ( w ) ein nur einfach-reeller Korper ist, hater nach LEJEUNE- DIRICHLET nur eine Grundeinheit. Ob die durch (48) gegebene es ist, konnte bisher nicht ent<schieden werden, wird aber vom Verf. vermutet. Verf. hegte die Hoffnung. daB. ahnlich wie im Falle (48), wo die Einheit mittels des J. P. Algorithmus ermittelt wurde, auch der neue Algorithmus eine Ein- heit des Korpers K ( w ) aufdecken miirde, die von der in (48) gegebenen Form abweicht.

Professor HASSE und Verf. haben bewiesen. daB im Falle eines perio- dischen J. P. Algorithmus mit s, t als Langen der Vorperiode bzw. der Periode (und ganzzahligen b f ) ) eine Einheit des Korpers K ( w ) gegeben ist durch

(W - D ) J (W - D)" d w3 - DJ

- - - -

= f l , - l a ( 8 + j ) . (49) 3=0 n-1

Also ist im Falle des n e u e n Algorithmus wegen s = 1, t - 1 = 8

e = nP a!,"+j). ( 50) J = o - Wie man nun leicht nachpriift, hat dieses Produkt die Form

ti? + w D + D? 2 ( w ? + w D + D 2 ) 2 w + D . ~ -- __ 2 w + D 2 d

w2 + w D + 0 2

. (w + D ) * d(w + D ) (51)

(w' + w D + 0 2 ) '

1 c d' z o + 2 D - - a (W + 2 0 ) . U' . - . w? + W D + D?

X

(w' + w D + DZ)G - __-____ -

a4

(w' + ui D + D2)t;

a4 e =

; also ist d -

W - D Nun ist, gem613 (27) ul2 + u' D + D' =

__ im Korper K (w) , ist also Einheit ; sie ist die von Kiln liegt bereits

unserer friiheren Arbeit her bereits bekannte, dort sogar unter der schwgche- ren Voraussetzung d j D statt der hier zugrunde liegenden starkeren 2 d 1 D.

d (w - D):I

In einer friiheren Arbeit hat Verf. [I, c)] nachgewiesen, da13 mit

(53) u! = (DJ + 3 D)"3


der J. P. Algorithmus der Basis w, w2 periodisch wird. Diese Irrationalitat nimmt eine Sonderstellung ein und fallt nicht unter den in der Arbeit des Verf. [1, a)] untersuchten allgemeinen Fall w = (D” + d)’’’; der J. P. Algo- rithrnus obiger Basis im kubischen Fall hat namlich die Lange 7 mit Vor- periodenliinge s = 3 und Periodenliinge t = 4. Uberraschenderweise wird auch der Algorithmus, wie er hier gem513 (17) definiert ist, auf obige Basis angewandt, mif verkehrter Reihenfolge der Potenzen von w periodisch. und zwar gilt

(54) Fuhrt man an den Zahlen

Satz 2. Bs sei w = (D3 + 3 0 ) 1 1 3 ; Dnatiirlich 2 4; D = 2 m (m = 2, 3, . . .).

(55 ) w = p , w den Algorithmus (3) rnittels des Bildungsgesetxes (17) durch, so wird der Algorithmus periodisch; die Vorperiode hat die primitive Lange s = I und ist von der Form (56) D , D ; die Periode hat die primitive Lange t = 9 und ist von der Form

0 0 0 0

0 0 2

B 0

457) 0

Dl2

D/2

2 2 0

3 D D:’. + D 1 3 0

Beweis. Es ist

0 3 < D 3 + 3 D < D 3 + 3 0 2 + 3 D f l ,

D < w < D + l , also

und daher (58) l ~ l = D ; wie friiher gilt fur das Bildungsgesetz

(59) bju) = I aj’) ( D ) I (i = 1, 2 ; v = 0 , 1, . . .), Wegen (55), (59) ist

bi0) = 1 D’/D 1 ; 460) hio) = D ; b!jo’ = D .

b!jo) = 1 D 1 ,

268 Bernstein, Ein neuer Algorithmus

Es ist wegen (54) t C L + ZCD + D’

w’ + WD + D’ ____- ~ ~- -

1

W - D Z U ~ - DJ 9

1 (61) ___ ~ ~-

W - D 3 0 Aus ( 5 5 ) , (60) ergibt sich

also wegen ( 3 ) und (61)

Aus (64) ergibt sic11 wegen (59)

by:) = 0 . ( 6 5 ) 3 b y ) =; ., . Aus (B-C), (66) ergibt sicli

also wegen ( 3 ) mid (61)

Aus (G6) ergibt sicli wegen (59)


nun ist aber wegen D 2 4 I 2/D I = 0 ; also wird (67) b y ) = 0 . , bi3) = 2 0 .


2 ( ~ 2 + w D + D ' ) - 2 D ( 2 w + D ) S W ( W - D ) - ~ _ _ _ _ - u(3) - 0'3) = - .~

2zo + D 2 w + D ' 2 L

also wegen (3)


b y ) = 0 ; hi4) = 0 . >

b f ) = 13D/6I; 6, (4) - - D / 2 , (69)

und aus (68), (69)

also wegen ( 3 ) , (61)


(71) b r ) = 0 ; b f ) = 3 ,

und aus (70), (71)

bi5) = I 1/D I ; bp) = I 3 D'/D'I,

also wegen (3)

Aus ( 7 2 ) ergibt sich wegen (59)

(73) b y ) L= 0 . , bi') = D ,

und &us (72 ) , (73)

- 1

270 Bernstein, Ein ne'uer Algorithmus

also in1 Hinblick auf ( 3 ) und (61)

rind atis (74). (75)

also. wegen (3) und (61)

Ails (76) ergibt, sich wegen (59)

Bernstein, Ein neuer Algorithmus

Nun ist

272

3 D 3 + D 1 D < - ; - = D + -- < D + I ;

3 D- 3 0

also wird

(77 ) by) = D ; b!j8) = 1 .

AUS (76), ( 7 7 ) ergibt sich

also wegen ( 3 )


by) = 0 . , b r ) = 3 D, (79 )

urid aus (78 ) , (79 )

also, wegen (3) und (61)

VergIeicht man (62) und (SO), so ergibt sich

(81) 1 *l 7 a, . Mit (81) ist die erste Behauptung des Satzes 2 . bewiesen; aus den Formeln (60), (63 ) , (65), (67)’ (69), ( 7 1 ) , (73 ) , ( 7 7 ) , ( 7 9 ) liest man die ubrjgen ab, womit der Satz restlos bewieseii ist. Man beachte auch, da13 Satz 2 nicht aus Satz 1 hergeleitet werden kann.

(-J10) = (0). aye) = (1)

Literatur

[I] LEON BERNSTEIN, a) PeriodicalContinued Fractions of degrec n by Jacobi’s Algorithm, J. Reine angew. Math. 213, 31-38 (1964). -, b) Representation of (Dn - d)Wasa periodic continued fraction by Jacobi’s Algo- rithm, diese Nachr. 29, 179-200 (1965). -, c) Periodicity of Jacobi’s Algorithm for a special type of Cubic Irrationals, J. Reine angew. Math. 213, 134-146 (1964).

272 Bernstein, Ein neuer Slgorithmus

-, d) Periodische Jacobische Algorithmen fu r eine unendliche Klasse Algebraischer Irrationalzahlen vom Grade n und einige unendiiche Kiassen Kubischer Irrational- zahlen. J. Reine angew. Math. 215j216, 76-83 (1944). -, e) Periodische Jacobi-Perronsche Algorithmen. Archiv der Math. XV, 421-429 ( 1964). -, f ) S e w Infinite Classes of Periodic Jacobi-Perron Algorithms, Pacific J. Math.

-, g) A periodic Jacobi-Perron Algorithm, Canadian J. Math. 17, 933-945 (1965). LEON BERNSTEIX und HELJfnT HASSE, h) Einheitenberechnung mittels des Jacobi-Perron-

schen Algorithmus. J. Reine angew. Math. 218, 51-69 (1965). LEOX BERNSTEIK, i) Rational Approximation of Algebraic Irrationals by means of a

Modified Jacobi-Perron Algorithm, Duke Nath. J. 32, Yo. 1, 161-176 (1965). -, j) Periodische Kettenbruche beliebiger Periodenlange. Math. Z. 86, 128-135 (1 964).

-, k) Explicite Solution of a n Algebraic Equation of degree n by means of a Modified Jacobi-Perron Algorithm, submitted t o Siam Publ. in 1966.

-, 1) Rational Approximation of Algebraic Sumbers, Proc. nat. Conference on data Pro- cessing, Rehovoth, 1964, IPA, pp. 91-105.

-, m) The Modified Algorithm of Jacobi-Perron, Its Theory and Application. Trans- actions and Nemoirs, AMS, submitted in 1965.

[ 2 ] C. G. JACOBI, Allgemeine Theorie der kettenbruchahnlichen Algorithmen, in welchen jede Zahl aus drei vorhergelienden gebildet wird. J. Reine angew. Math. 69 (1868).

[3] OSKAR PERRON, Grundlagen fur eine Theorie des Jacobischen Kettenbruchalgorithmus. Nath. Ann. 64 (1907).

16, SO. 2, 1-31 (1965).

Documents

Ein neuer Algorithmus für absteigende Basispotenzen im kubischen Körper