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 ein- treten 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 (34) ergibt sich wegen (17)
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)
Bernstein, Ein neuer Algorithmus 263
~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
Bernstein, Ein neuer Algorithmus 265
Aus (42), (43) 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 be- wiesen, 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
Bernstein, Ein neuer Algorithmus 267
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)
Bernstein, Ein neuer Algorithmus 269
nun ist aber wegen D 2 4 I 2/D I = 0 ; also wird (67) b y ) = 0 . , bi3) = 2 0 .
Aus (66), (67) ergibt sich
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)
Aus (68) ergibt sich wegen (59)
b y ) = 0 ; hi4) = 0 . >
b f ) = 13D/6I; 6, (4) - - D / 2 , (69)
und aus (68), (69)
also wegen ( 3 ) , (61)
Aus (70) ergibt sich wegen (59)
(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 )
Aus (78) ergibt sich wegen (59)
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).