Ober ,,kleinste" Losungen diophantischer Gleichungen. ERHARD SCHMIDT zum 75. Geburtstag gewidmet.

Von RICHARD VON MISES in Cambridge, Mass. (USA.).

(Eingegangen am 12. 6. 1950.)

In gewissen Problemen der Wahrscheinlichkeitsrechnung tritt die folgende Fragestellung auf , die in das Gebiet der diophantischen Gleichungen fd l t I).

Es sind n ganzzahlige Unbekannte durch m < n nicht-homogene lineare Glei- chungen verbunden. Gibt es zwei Losungen x und y (n-dimensionale Vektoren), so daB fur jedes v = 1 , 2 , . . . , n

(1) entweder 0 5 y, 5 x, oder 0 2 yy 2 x,

und nicht immer xv = yy, so heiBe y eine ,,kleinere" Losung als x. Eine Losung, zu der es keine kleinere gibt, heiBe eine ,,kleinste". Die Aufgabe ist, das Gebiet der kleinsten Losungen abzugrenzen.

Im folgenden wird zunachst fi ir beliebige n > nt gezeigt, dal3.die Anzahl (und das Gebiet) der kleinsten Losungen beschriinkt ist. Sodann wird kurz der einfachste Fall, m = 1 , besprochen und eine Beantwortung der Frage fiir m = 2 vorgeschlagen. Der Zweck dieser anspruchslosen Mitteilung ist nur der, zu einer vollstandigeren Behandlung anzuregen.

I. Beschriinktheit der kleinsten Losungen. Von den1 Gleichungssystem

n

2 apv x, = b, , p = 1 , 2 , . . . , m, n - m > 0

mit ganezahligen a,, und bfi werde vorausgesetzt : a) daB nicht alle b, verschwinden, b) da13 es eine ganzzahlige Losung besitzt, c) daB die Matrix der a,, den Rang m hat. Die Cesamtheit der Losungen bildet dann im n-dimensionalen Rsum ein

k-dimensionales Gitter (k n - m) ) das den Nullpunkt nicht als Gitterpunkt enthalt. Die Differenz zweier Losungen x - y = z ist ein Gittervektor, d. h. eine Losung der homogen gemachten Gleichungen (2). Wir wollen zeigen, da13

l) R. V. MISES, Uber Aufteilungs- und Besetzungs-Wahrscheinlichkeiten. Rev. Fec. Sci. Univ. Istanbul A 4 (1939), 145-163. Hier ist such eine Losung fur den Speziahll gegeben, der als Beispiel am Ende der vorliegenden Arbeit behandelt wird.

Math. Nachr. 1950/51, Bd.4, H. 1-6. 7

98 v. Mises, Vber ,,kleinste" Ueungen diophantiacher Gleichungen.

die Anzahl der Gitterpunkte, die im oben bezeichneten Sinn kleinste Losungen darstellen, beschriinkt ist.

Fiir E = 1 ist die Behauptung unmittelbar einleuchtend und wird uberdies am Ende des Abschnittes explizit bewiesen werden.

Fiir k 2 2 bestimmen die Usungen des homogenen Systems, ohne Beriick- sichtigung der Genzzahligkeit, auf der Einheitskugel ein (k - 1)-dimensionales Kontinuum K . 1st G, ein Gebiet auf der Einheitskugel, das keinen Punkt mit K gemeinsam hat, so besitzt fur jeden Vektor x, fur den z: I X I dem Gebiet G, angehort, der absolute Betrag mindestens einer der linken Seiten von (2) ein von Null verschiedenes Minimum M :

(3)

Es folgt damus, dd3 fur jede Losung z, yon (2), fur die x: 1x1 nach (7, fiillt,

Es gibt aber nur endlich viele Gitterpunkte in einem Bereich, in dem 1x1 be- schriinkt ist.

1st andererseits B2 ein Gebiet auf der Einheitskugel, das einen inneren Punkt mit K gemein hat, so mu13 es in a, auch Punkte z geben, fiir die die Quotienten z1 : z2 : . - : z,, rationale Werte haben und eine Losung der homogenen Gleichungen bilden. Es existieren also auch Gitteruektoren, d. h. ganzzahlige z , die die homo- qenen Gleichungen befriedigen und f i i r die z : Iz I nach B, fiillt.

Diese Siitze wenden wir jetzt auf die 2n Sektoren des n-dimensionalen Raumes an, von denen jeder durch eine bestimmte Folge von n Vorzeichen charakteri- siert ist. Jeder Sektor schneidet auf der Einheitskugel ein Gebiet G aus. Dieses tJ ist entweder vom Typus B, oder vom Typus G, oder es hat mit K nur Rand- purikte gemeinsam.

Im ersten Fall kann der betreffende Sektor mit EinschluB seiner Riinder nur endlich viele Gitterpunkte enthalten, und wir brauchen uns um ihn nicht weiter zu kiimmern.

Fur einen Sektor der zweiten Gruppe gibt es einen Gittervektor z , so daB fur jeden Gitterpunkt 2 des Sektors z, xu 2 0 fur alle v . Sei z, von Null verschieden fur v = a, @, y , . . . und 1 der groBte absolute Betrag eines 2,. Dann ist y = x - z sicher dann eine kleinere Losung als 2, wenn alle Ix.1 fiir v = a, /3, y , . . . gro5er als 2 - 1 sind. Eine kleinste Losung x ist also an die Bedingung geknupft, da13 mindestens eine der Gleichungen

(4) Z" = 0, 5, = -&I, 5, = *2, . . . , 2, = f ( Z - 1)

fiir einen der Indizes v = a , 8, y , . . . erfiillt ist. Die Hinzufugung einer Glei- chung z, = const vermindert aber die Dimensionszahl des Gitters urn eine Ein- heit, auBer wenn x, = const aus den Gleichungen (2) folgt. Dies wurde aber vor- eussetzen, daB aus den homogen gemachten Gleichunged z, = 0 folgt, daB also v nicht zu den Indizes a, /3, y , . , . gehort. Somit mussen die kleinsten Losungen in dem jetzt 'betrachteten Sektor kleinste Usungen in einem von endlich vielen (k - 1)-dimensionalen Gittern sein.

v. Mises, Ober ,,kleinste" &tisungen diophantischer Gleichungen. 99

In einem Sektor der dritten Gruppe verhiilt sich jeder innere Teil so wie ein Sektor der ersten Art, d. h. er enthhlt nur beschrankt viele Gitterpunkte. Die Randpunkte miissen eine oder mehrere Gleichungen der Form. x, = 0 erfiillen. Jede solche Bedingung vermindert wieder die Diinensionszahl des Gitters urn eine Einheit, aul3er wenn die Gleichung xv = 0 fur das betreffende v aus (2) folgt. Tatsachlich konnen p < m solcher Gleichungen in (2) enthalten oder &us ihnen ableitbar sein. Dann lieat das ganze k-dimensionale Gitter in einem (n- p) - dimensionalen Raum und wir konnen von vornherein diesen betrachten, d. h. die betreffenden p VariabIen fortlassen. In diesem Fall gibt es keine weiteren Be- dingungen xv = 0, die aus den Grundgleichungen folgen, und die Sektoren des (n - p)-dimensionalen Raumes, die zum dritten Typus gehoren, enthalten aul3er endlich vielen Gitterpunkten im Innern nur solche, die auch Gitterpunkte eines oder mehrerer Gitter von weniger als k Dimensionen sind.

Somit ist gezeigt, daB die Anzahl der kleinsten Losungen im k-dimensionalen Gitter endIich ist, wenn dies fur alle Gitter vori k - 1 Dimensionen gilt.

Ein eindimensionales Gitter im n-dimensionalen Raum, das den Nullpunkt nicht als Gitterpunkt enthalt, besteht aus den Punkten

(6) x, = a , + pz, , v = 1 , 2 , . . . , n , wobei a, und z, feste, nicht fur alle v verschwindende ganze Zahlen sind'und p alle ganzen Zahlen von -w bis +oo durchliiuft. Bezeichnet r den groBten abso- luten Betrag der Quotienten a, : z, fur diejenigen v, fur die z, nicht Null ist, so gibt es zu jedem x niit eineni lpl 2 r eine ,,kleinere" Losung von ( 5 ) im Sinne von (1). 1st etwa p > r , so ist y mit den Koinponenten

yY = a, + ( p - l )z , kleiner als x. Denn fur diejenigen Y , fur die z, > 0, hat man

x , = a, + pz. 2 a, + 2 z, 2 0 und x, - yv = 2, > 0, 12, I

l a y i so daB das erste Paar von Ungleichheiten (1) erfullt ist. Fur die Tndizes mit z, < 0 ist

5, = a, + p z , s a, + z, z, 2 0 und x, - y, = z, < 0, was dem zweiten Paar (1) entspricht. Endlich ist xv = y, fur alle diejenigen Y, fur die z, = 0. In der gleichen Weise zeigt man, daB yy = a, + ( p + l)z, eine kleinere Losung von (5) ist, wenn p < - r . Die Gesamtzahl der kleinsten Losungen ist somit nicht groBer als 2[ r ] + 1 . Dies, zusammen mit den friiheren Uber- legungen uber die Zuruckfuhrbarkeit von k auf k - 1 , beweist die Beschriinkt- heit der kleinsten Losungen.

2. Der Fall e in e r (rleichung. Wir betrachten die Gleichung

(6) worin die a, und c nicht verschwindende ganze Zahlen sind. Die Existenz einer Lijsung vorausgesetzt, bildet die Gesamtheit der Losungen ein (n - l)-d' ]men- sionales Gitter im n-dimensionalen Raum.

alxl + a2x2 + - . . + a,,xn = c , n 2 2,

I*

100 v. Mises, uber ,,kleinste" Lijsungen diophantischer Gleichungen.

Werden n positive Zahlen A,, eingefiihrt durch n

I = 1 A, = A - I a,l , A = 2 l a , ] , v = 1 , 2 , . . . , n , (7)

so gilt folgendes Lemma.

Lemma 1. Sei x eine Losung von (6). Wenn fur irgendzin v

(8) Ie-a,.x,I > rA , , r Z O

gilt, so gibt es mindestens &a p + v, fur das

(9) I X P I > r und sgn (a, x,) = sgn ( c - a, x,) . Beweis. Sei, erstens, c - aV x, positiv, also grol3er als r A , . Dann ist die

linke Seite von (6) ohne das Glied a, x,, und urn so mehr die Sumnie der positiven Glieder allein, grol3er als r A . Waren aber alle IxFI in diesen Termen nicht groBer als r, so ware die Sumnie der Terme nicht groSer als die r-fache Summe der be- treffenden I up 1 , also sicher nicht groSer als rA. . In der gleichen Weise erledigt sich der Fall, daB c - a, xu negativ ist. Eine unmittelbare Folgerung ist

Lemma 2. Gelten fur irgendein r gleichzeitig die Ungleichheiten

(10) a,z, > 0, a,x, > c + rA,

(10') Q , x , < O , a,x,<C--A.,

so gibt es mindatens ein p =k v , f u r das

(11) I x!&1 > r wnd sgn(ap x,,) = -sgn(b, 2,).

eul3erdem hat beidenial a, xu - c dasselbe Vorzeichen wie a, 2,.

fiziert werden :

oder gkichzeitig

Beweis. In beiden Fiillen ist die Bedingung (8) von Lemma 1 erfiillt und

Die Bedingungen (10) und (10') konnen auch in der folgenden Weise modi-

Lemma 3. Die Folgemng (11) von Lemma 2 besteht auch zu Recht, wenn x,

x, > a 2 0 und x, > 2- + A,,

entweder den Bedingungen

(12) a, 1a.l

oder den Bedingungen

x, < -8 5 0 und

genugt. Beweis. Wenn a, > 0, so folgen aus (12) die Ungleichheiten (10) und aus

(12') die Ungleichheiten (10')- Fiir a, < 0 ist (10) eine Folge von (12') und (10') eine Folge von (12).

Nunmehr la;& sich die Frage nach den kleinsten Losungen von (6) leicht er- ledigen. 1st x eine Losung von (6), so gibt es zwei weiteJe Losungen y wie folgt :

(13) y,, = xp 'f a,, y, = x, f a,,, y, = xt fur 1 p , v.

v. Mises, Uber ,,kleinste" Losungen diophantischer Gleichungen. 10 I

Ih.mit eines dieser y (beidemal das obere oder beidemal das untere Vorzeichen) eine kleinere Losung als x ist, ist hinreichend, daB

( 1 4 ) I%l 2 14, I4 2 lad und au Berdem die Vorzeichenbedingung

(15) oder sgn (a,, xp) = -sgn (a, 2.)

erfullt ist. Haben etwa x, und a, gleiches, daher x, und a, ungleiches Zeichen, so hat xp - a , gleiches Zeichen wie x, und geringeren Betrag, ebenso xv + a, das Zeichen von x, und einan Betrag kleiner sls la,( usw.

Es bezeichne nun a, den grol3ten der Betrape von u2, a3, . . . , an, ebenso a, den groBten der Betraige von al, a3, . . . , a, usf. Wir setzen in die Bedingungen (12), (127 des dritten Lemmas

(157 s = Z v - l und r = l a y l - l

gin. Dann ist zunachst die Bedingung [ xyl > s 2 [a ,! - 1, sodann I .,,I > r = I a, I - 1 eriiillt und schlieBlich die Vorzeichenbedingung (15). Wir haben so- mit bewiesen, daB es zu jedem x, f i i r das ein x, den Ungleichheiten (12) oder (127 mit 8 und r von (15') geniigt, eine kleinere Losung gibt:

Satz 1. Damit x eine kleinste Losung von (6) ist, ist notwendig, dap jedes x, ( u = 1 , 2 , . . . , n) nicht groper ist als die gropere deer beiden Zahlen

sgn (a,,a, xp 2,) = - 1

und nicht kleiner als die kleinere der Cropen

-z,, + I , C

a" _ - A , I - i

Mit anderen Worten: Jedes x, mug einem Interm11 angehoren, das die beiden Intervalle

&(a, - und

Beispiele. Fur die Gleichung

x 1 + x , + . * . + x n = c

ist a, = 1,l a, I = 1 fiir jedes Y . Das erste Interval1 reduziert sich auf den Punkt 0, das zweite auf den Punkt c . Kleinste Losungen konnen nur solche sein, fiir die jedes x, dem von 0 und c begrenzten Interval1 angehbt.

Fiir die Gleichung

x1 = 2xa + 3x8 + . . . + nx, = c

sind (abgesehen von einer kleinen Modifikation fur v = n)

u nd

die beiden Intervalle, deren iiberdeckung das Interval1 fur xv bildet.

1 02 Y. Mises, ober ,,kleinste" Losungen diophantischer Gleichungen.

3. Der Fall z w e i er Gleichungen. Sind zwei Gleichungen vorgelegt, so schreiben wir sie in der Form

alx l + a2xa +. . . + anxn = G , n 2 3 . 4 x 1 + b a x s + . * - + b n x n . = d , (18)

Die Existenz eines Gitters von Losungen wird vorausgesetzt. Ohne die Allgemein- heit zu beschrlinken, nehmen wir an, a) daB alle cs, von Null oerschieden sind ; b) daB die Quotienten 6, : a, eine monotone Folge bilden:

Ein Vektor x , der (18) geniigt, erfullt auch jede der n Gleichungen

n 2 d x , q = c,, x = 1 , 2 , . . . , r t , '=I

worin

(21) S,, = arbx - a , b , , C, = cb, - -a , .

Werden drei voneinander verschiedene lndizes A, p, v gewahlt, so gibt es zu jedem x zwei weitere Losungen, definiert durch

(22) yt.= xi& d,,, y,, = x , , k & a , yI = xv f d t p , Y, = 5, fur L + a s p , v

(jedesmal die oberen oder jedesmal die unteren Vorzeichen). Damit eines dieser beiden y eine kleinere Losung als x ist, ist hinreichend,

daB erstens

(23) I Z A ] 2 I'pUI, 1x/.41 2 1 ' V L l J ~ l d ~ ~ l und zweitens die Vorzeichenbedingungen

(24) s,gn(xvSLp) = sw(ZLd,,,) = sgn(Xp&a)

zu Recht bestehen. Falls eine der Determinanten, etwa S,,, gull ist, hat ein Quotient dip: 61, fur alle A den gleichen Wert, und die Bedingungen (23)) (24) reduzieren sich darauf, daB fur irgendein x #= p , v

(25) Ixpl 2 ILI, [.,I r pqJ, sgn(xpL) = %n(.vdx,).

Unsere Aufgabe ist es, das Bestehen von (23), (24) oder von (25) &us Eigenschaften einer einzigen Komponente x,, ahzuleiten.

Zu diesem Zweck wenden wir unser Lemnia 3 auf die x-te der Gleichungen (20) an, in der d,, + 0 vorausgesetzt wird. Andog zu den GroBen A, und 6, im vorigen Absch nit t sei

n

A,, = A,, - 1 d,,, I , 4, = 2 A,, , 8, = max I Ll, & = I x , l**

('26)

aul3erdem

(26') S: = mas I d x v [ . x = l , 2 , . . . , n

Y. Mises, uber ,,kleinste" Losungen diophtmtischer Gleichungen. 103

In (12) setzen wir 8 = 6, - 1 und r = 6; - 1 . Dann besagt Lemma 3 (in seinem ersten Teil) : Wenn

-

so gibt es einen oder inehrere Indizesp, fiir die

(28) l x r I > 6: - 1 und sgn(z,,6,,) = -sgn(x,6,,).

Wir wahlen ein solches p und betrachten die p-te Gleichung (20) (in der x,, nicht auftritt, weil a,, = 0). 1st hier 6," = 0, so ist bereits bewiesen, daB ein x unter den Voraussetzungen (27) keine kleinste Losung sein kann. Denn nach (27) selbst ist ] ~ , ~ > I 6 ~ ~ [ - 1 , also &16,,l, nach (28) ist Ixp l>16xy[ -1 , also 2 I 6," I, und die Vorzeichenregel in (28) ist identisch mit der dritten der Beziehun- pen (25), die oben als'hinreichend fur die Existenz einer kleineren Losung in1 Fall a,,, = 0 erkannt wurden.

Es bleibt also nur der Fall 6," =I= 0 zu untersuchen. Urn Lemma 3 auf die p-te Gleichung anwenden zu konnen, erweitern wir die Voraussetzungen (27) dahin, daB die zweite Ungleichheit fur alle x , fiir die S,, $: 0, also auch fur x = p gelten soll. Es gibt dann ein oder niehrere 1, verschieden von v und von p (weil x , ~ in der Gleichung gal nicht vorkommt), fur die

(29) lxll > 6, - 1 und sgn(xaSpl) = -sgn(x,6,,).

Da die letzte Beziehung niit der ersten Gleichheit (24) identisch ist, erfullen x A , xp, 2, alle Bedingungen (23) und (24) bis auf das zweite Gleichheitszeichen in (24). Es bleibt also nur noch zu zeigen, daB immer solche A , p zu einem ge- gebenen v vorhmden sind, dal3

-

(30) 51 x, 6," 6 Y * z 0 .

Urn dies zu zeigen, benutzen wir die Anordnungsvorschrift, die in (19) ge- geben wurde. Aus ihr folgt, daB fur alle I , x

(31)

Daher ist die letzte Gleichung (28) gleichbedeutend mit

(a)

iind die letzte Gleichung (29) mit

sgn (a , a, Stx) = sgn (1 - x ) .

sgn(apa,xpz2,f = s p ( x -p) ( Y --)

(b) ??n(aAGXaxv) = %n(p - 4 ( y - P ) ,

woraus durch Multiplikation folgt :

(c) sgn(aaa,,zAq,) = s p ( x - p ) ( x - Y) (A - p ) ( v - p ) .

Dagegen besagt die zu beweisende Gleichung (30)

(4 Zu zeigen ist also, daB

sgn (aA aiL x1 xp) = sgn (A - v ) ( v - p) .

(32) ( x - p) ( x - 4 (2 - A (A - y ) > 0, d. i. di~D x und A beide auBerhalb oder beide innerhdb p , 1.1 liegen.

104 v. Miseu, Uber ,,kleinste“ Losungen diophantischer Gleichungen.

Es sind drei Fllle zu unterscheiden. Erstens kann es vorkommen, daB in der x-ten Gleichung (20) nur ein eiiiziges p existiert, das die Eigenschaften (28) besitzt. D a m ist fur jedes 1 =!= p , v, fur das I z, I > 6; - 1 , also auch fur L = 1, das Umgekehrte der Vorzeichenbedingung (28), also auch das Umgekehrte von (a) erfiillt :

(6) Aus (e) und (b) folgt aber

(33)

sgn (a1 a, z1 5,) = sgn ( x - 2) ( x - v) .

( 2 - p ) (v - p ) ( A --I (v - x ) > 0 .

Tatsachlich ist (32) eine notwendige Konsequenz von (33). Man kann dies durch direkte Rechnung oder durch Studieren der moglichen Anordnungen von 4 Zahlen oder, am besten, durch folgende merlegung beweisen. Die linken Seiten von (32) und (33) unterscheiden sich nur durch positive Faktoren yon den Doppel- verhaltnissen dl = ( x , A ; p, v) und d, = ( x , p; 1, v ) . Es ist aber bekannt, daB dl = 1 - d,; also folgt aus d, < 0, dal3 d, > 0. Damit ist fur den ersten Fall alles bewiesen.

Der zweite Fall ist der, dafi es’inehrere p gibt, €iir die (28) gilt, und mindestens eines, das von v nicht durch x getrennt wird. Dann wahlen wir unser p so, dal3 x aul3erhalb p, v bleibt und daB zwischen v und dem gewahlten p kein weiterer Index liegt, fiir den (28) gilt. Es miiBte aber fur jedes A , das etwa zwischen p und v liegt, (33) bestehen; dies6 Ungleichheit ist aber unvertraglich mit A inner- halb p, v. (In der Tat ist, abgesehen von zyklischen Permutationen und Um- kehrungen, A x v p die einzige Anordnung, die (33) entspricht.) Es liegt also 2. aul3erhalb p, Y , und mit x und 2 auBerhalb p, v ist (33) erfullt.

Der dritte Fall besteht darin, daB es zwar mehrere ,u gibt, die (28) genugen, aber alle von v durch x getrennt werden. Wir wlhlen dann unser p als das von v entfernteste, so daB fur ein etwaiges 2 auBerhalb p, v die Beziehung (33) gelten mul3te. Diese ist aber unvereinbar mit x innerhalb p, v. Daher kann A nur inner- halb p, v liegen und, wenn beide, x und A , in p, v fallen, ist wieder (32) befriedigt.

Was hiermit uber die kleinstea Losungen von (18) bewiesen wurde, ist der folgende

Satz 2. Damit x eine kleinate Lomng von (18) id, ist notwendig, dap j& x, (v = 1, 2, . . . , n ) nicht groper ist at% die gropte der Zahlen

(34) - cx 6;- 1 6,-1 und -+- AX”

ax, l L l und nicht kkiner .ale die kleinste der Chopen

wobei x alle Werte von 1 bia n durchliiuft, fur die a,, $: 0.

Fiir die praktischeAnwendung kann man bequemere, aber naturlich schwiiohere Bedingungen formulieren, indem man d, als das Maximum der A,, , ferner 8‘ als das Minimum aller nicht-verschwindenden I a,, I und schliefilich die Schranken m, und N, durch

(35)

v. Mises, uber ,,kleinste" Losungen diophantischer Gleichungen. 105

(immer nur fur x , fur die d,, $; 0) einfuhrt. Aus Satz 2 folgt dnnn, daB fur eine kleinste Losung 2 von (18) jedes 2, dem Innern oder dem Rand eines Intervalls angehoren mul3, dais die beiden Intervalle

einschliel3t. Als BeispieI diene das Gleichungspaar

z1+2, + . . - + x n = c , n 2 3. xl + 22, + . . . + n x n = d ,

Hier ist 6,, = L - x , C, = x c - d , 6' = 1, die Schranken M und n2 sind & (nl cI + I d 1) , es ist 6, = n - 1 und 8, gleich der grol3eren der beiden Zahlen v - 1 und n- Y . Da mit

d,=---1 2

das zweite Interval1 (36) stets das erste einschlieBt, findet man als notwendige Bedingung fur eine kleinste Losung

- n(n-1)

Dies Resultat ist im wesentlichen in der eingangs zitierten Veroffentlichung von 1939 enthalten.