Stern-Brocot-Baum

In der Mathematik ist der Stern-Brocot-Baum eine Darstellung aller streng positiven rationalen Zahlen in Form von irreduziblen Brüchen .

Sie wurde fast zeitgleich von dem deutschen Mathematiker Moritz Stern (1858) und dem französischen Uhrmacher Achille Brocot (1861) entdeckt.

Konstruktion

Der Stern-Brocot-Baum ist ein unendlicher binärer Baum, dessen Knoten durch irreduzible Brüche gekennzeichnet sind. Es wird durch Wiederholung gebaut, eine Etage nach der anderen.

Etage 1 enthält nur die Wurzel des Baumes, die den Bruch 1/1 trägt.

Die Stufe p +1 des Baums wird wie folgt konstruiert: Wir listen alle Bruchteile des endlichen Teilbaums auf, die Stufe p entsprechen , von links nach rechts gelesen. Wir fügen den Bruch 0/1 am Anfang der Liste und 1/0 am Ende der Liste ein und erhalten so eine Liste von 2 p +1 Brüchen (siehe Bild). In dieser Liste gehört einer von zwei Fraktionen zur Stufe p , einer von vier zur Stufe p- 1 und so weiter.

Mit jeder Fraktion, die zur Stufe p gehört , assoziieren wir ihre beiden Töchter der Ebene p + 1 , die wir erhalten, indem wir den Median mit jedem ihrer beiden Nachbarn in der Liste bilden: der Median der Fraktionen und ist der Bruch . ${\ frac mn}$ ${\ frac {m '} {n'}}$ ${\ frac {m + m '} {n + n'}}$

Beispiel: die ersten Stadien des Baumes

Hier sind die Listen der im Baum enthaltenen Fraktionen nach der Konstruktion jeder der ersten 4 Stufen (auch in der Zeichnung gezeigt), zu denen wir zuerst 0/1 und zuletzt 1/0 hinzugefügt haben. Auf jeder Etage wurden die zu dieser Etage hinzugefügten Fraktionen rot eingefärbt, die anderen sind die der vorherigen Etagen.

${\ displaystyle {\ begin {array} {lccccccccccccccccc} {\ text {Floor 1:}} & {\ frac {0} {1}} &&&&&&&& {\ color {red} {\ frac {1} {1}}} &&&&&&&& {\ frac {1} {0}} \\ {\ text {Floor 2:}} & {\ frac {0} {1}} &&&& {\ color {red} {\ frac {1} {2}} } &&&& {\ frac {1} {1}} &&&& {\ color {red} {\ frac {2} {1}}} &&&& {\ frac {1} {0}} \\ {\ text {Etage 3: }} & {\ frac {0} {1}} && {\ color {red} {\ frac {1} {3}}} && {\ frac {1} {2}} && {\ color {red} { \ frac {2} {3}}} && {\ frac {1} {1}} && {\ color {red} {\ frac {3} {2}}} && {\ frac {2} {1}} && {\ Farbe {rot} {\ frac {3} {1}}} && {\ frac {1} {0}} \\ {\ text {Floor 4:}} & {\ frac {0} {1} } & {\ color {red} {\ frac {1} {4}}} & {\ frac {1} {3}} & {\ color {red} {\ frac {2} {5}}} & { \ frac {1} {2}} & {\ color {red} {\ frac {3} {5}}} & {\ frac {2} {3}} & {\ color {red} {\ frac {3 } {4}}} & {\ frac {1} {1}} & {\ color {red} {\ frac {4} {3}}} & {\ frac {3} {2}} & {\ color {red} {\ frac {5} {3}}} & {\ frac {2} {1}} & {\ color {red} {\ frac {5} {2}}} & {\ frac {3} {1}} & {\ Farbe {rot} {\ frac {4} {1}}} & {\ frac {1} {0}} \ end {array}}}$

Elementare Eigenschaften: Verbindung mit Fareys Suiten

Der Stern-Brocot-Baum ist eng mit den Farey-Suiten verwandt . Recall , dass zwei Fraktionen irreduziblen m / n und m ‚ / n‘ sind nahe an Farey wenn wir haben :

{\ displaystyle m'n-mn '= 1}

In diesem Fall überprüfen wir (siehe unten), dass ihr Median in der Nähe von Farey liegt, rechts vom ersten, links vom zweiten. Dies hat insbesondere zur Folge, dass m / n < ( m + m' ) / ( n + n' ) < m' / n' ; wir folgern, dass in jeder Stufe p des Stern-Brocot-Baums die zugehörige Liste der 2 p + 1 Brüche, die im Unterbaum erscheinen, vom kleinsten zum größten geordnet ist und dass zwei aufeinanderfolgende Brüche in dieser Liste Nachbarn von Farey sind. Diese letzte Eigenschaft impliziert auch, dass alle im Baum vorkommenden Brüche irreduzibel sind.

Beachten Sie, dass der linke Zweig des Baums alle Einheitsbrüche enthält , während der rechte Zweig alle ganzen Zahlen enthält, die als Brüche mit einem Nenner gleich 1 geschrieben sind.

Auf jeder Ebene bilden die Nenner der Brüche in der zugehörigen Liste die Stern-Diatomeensequenz .

Stern-Brocot-Baum und euklidischer Algorithmus

Der Stern-Brocot-Baum ist ebenso wie die Farey-Sequenzen mit dem Algorithmus von Euklid verwandt ; dies ermöglicht es, bei gegebenem Bruchteil m / n den Weg zu berechnen, der von der Wurzel zu dieser führt.

Dazu verwenden wir den Bachet-Bézout Satz : Wenn wir davon ausgehen , dass m / n ist nicht reduzierbar, das heißt , dass m und n sind coprime, dann gibt es zwei ganze Zahlen m ‚ und n‘ , so daß m'n - mn ' = 1 ( oder mn' - m'n = 1); wenn wir außerdem annehmen, dass m und n verschieden und beide nicht null sind, dann können wir m ' und n' so wählen , dass 0 ≤ m '≤ m und 0 ≤ n' n (die Koeffizienten m ' und n ' erfüllen alle diese Einschränkungen werden direkt durch den erweiterten euklidischen Algorithmus berechnet ). In diesem Fall , wie wir oben gesehen haben, die Fraktionen m ‚ / n‘ und m / n sind nahe an Farey .

Wir setzen dann m '' = m - m ' und n' ' = n - n' ; wenn m'n - mn ' = 1 dann mn' '- m''n = 1, sonst mn' - m'n = 1 und damit m''n - mn '' = 1. Außerdem ist m / n der Median Bruchteil von m ' / n ' und m '' / n '' woraus wir m ' / n' < m / n < m '' n '' ableiten , wenn mn ' - m'n = 1, oder m '' / n '' < m / n < m ' / n' si m'n - mn ' = 1. Im Stern-Brocot-Baum ist der Bruch m / n die Tochter der beiden Brüche m '/ n' und m '' / n '' hat den höchsten Nenner, da sich dieser im untersten Stockwerk befindet, und wir bestimmen, ob es das Mädchen links oder rechts ist, abhängig vom Vorzeichen von m'n - mn' .

Wenn wir zum Beispiel den Bruch 2/5 betrachten, dann liefert uns Euklids Algorithmus -2 × 2 + 1 × 5 = 1. Wir folgern, dass 1/2 und (2 - 1) / (5 - 2 ) = 1/3 die Nachbarn von 2/5 in der Farey-Folge der Ordnung 5; da 1/3 den größten Nenner hat, ist sie Mutter von 2/5; außerdem impliziert die Gleichung -2 × 2 + 1 × 5 = 1 1/2 > 2/5, also 1/3 < 2/5, woraus wir ableiten, dass 2/5 die rechte Tochter von 1/3 ist.

Durch Iteration des obigen Arguments können wir durch Induktion zeigen, dass wir eine endliche Folge von Brüchen von der Tochter zur Mutter erzeugen, d. h. einen Pfad im Baum, der vom Anfangsbruch zur Wurzel führt. Dies liefert insbesondere einen Beweis für die Existenz jedes irreduziblen Bruchteils im Baum.

Aufzählung von Vernunftgründen

Die grundlegende Eigenschaft des Stern-Brocot-Baums besteht darin, dass er alle irreduziblen streng positiven Brüche nur einmal enthält. Wir leiten ein Verfahren zur Numerierung aller positiven rationalen Zahlen her, d. h. eine Bijektion der positiven rationalen Zahlen auf die positiven natürlichen Zahlen. Kurz gesagt assoziieren wir mit einem rationalen die ganze Zahl, deren Darstellung in der Basis 2 den Pfad von der Wurzel des Baums zum gewählten rationalen kodiert.

Bei einem gegebenen Bruch assoziieren wir damit eine Folge von 0 und 1, die den Pfad von der Wurzel des Baums darstellt und zu ihm führt. Wir definieren daher zwei "Schritte": Schritt 0 (links) und Schritt 1 (rechts) (in dem zitierten Buch werden diese mit L für links und R für rechts bezeichnet ). Zum Beispiel wird der Weg, der zum Bruch 2/5 führt, wie folgt dargestellt (0, 0, 1): Von der Wurzel gehen Sie zweimal nach links und dann einmal nach rechts. Zur Vereinfachung bezeichnen wir nun die Folgen von 0 und 1 als Binärwörter , zum Beispiel wird die Folge (0, 0, 1) durch das Binärwort 001 dargestellt.

Die Idee besteht nun darin, das einem Bruch zugeordnete binäre Wort als die Basis-2-Darstellung einer ganzen Zahl zu lesen . Da jedoch mehrere binäre Wörter dieselbe ganze Zahl darstellen können (zum Beispiel die Wörter 1, 01, 001, ..., stellen alle die ganze Zahl 1) dar, stellen wir der Darstellung des Pfades zunächst eine 1 voran. Nehmen wir l Beispiel l des rationalen 2/5 wird sein Weg durch das Wort 001 dargestellt, das, wenn ihm eine 1 vorangestellt wird, zu 1001 wird, was sich wie die Darstellung in der Basis 2 der ganzen Zahl 9 liest. In ähnlicher Weise ist das rationale 3/5 mit der ganzen Zahl verbunden . das rationale 5/2 mit usw. Somit weisen wir jedem rationalen eine eindeutige Zahl zu und umgekehrt können alle ganzen Zahlen zur Basis 2 als Pfad im Baum interpretiert werden, der zu einem rationalen führt. ${\ Displaystil (1010) _ {2} = 10}$ ${\ displaystyle (1110) _ {2} = 14}$

Demonstrationen

Irreduzibilität jeder Fraktion

Wir zeigen, dass jeder im Baum vorkommende Bruch durch Induktion irreduzibel ist .

Wir erinnern daran , dass die Liste im Zusammenhang mit der p-ten Etage des Stern-Brocot Baumes ist die Liste der Fraktionen in dem Unterbaum der Höhe enthielten p , liest von links nach rechts, auf die wir hinzufügen , 0/1 an der Spitze und 1/0 Schwanz. Wir werden die oben genannte Eigenschaft offiziell zeigen: Zwei aufeinanderfolgende Fraktionen in der Liste liegen in der Nähe von Farey. ${\ Displaystil 2 ^ {p + 1} -1}$

Initialisierung : Auf Stufe 0 ist es offensichtlich: Wir haben 1.1 - 0.0 = 1.

Vererbung : Nehmen wir durch Induktion die auf Stufe p verifizierte Eigenschaft an .

Konstruktionsbedingt sind die neuen Brüche, die in Stufe p + 1 erscheinen, Mediane (m + m')/(n + n'), wobei m/n und m'/n' in der mit Stufe p assoziierten Liste aufeinanderfolgend sind ; nach Induktionshypothese gilt m'n - mn '= 1 . Es sollte gesehen werden, dass die Brüche m / n , (m + m ') / (n + n') und m ' / n', die in der der Stufe p + 1 zugeordneten Liste aufeinanderfolgend sind, nahe bei Farey liegen, das abgeleitet wird aus folgenden Berechnungen:

$(m + m ') nm (n + n') = m'n-mn ' = 1,$

$m '(n + n') - (m + m ') n' = m'n-mn '= 1.$

Somit verifizieren alle Paare m / n und m '/ n' von aufeinanderfolgenden Bruchteilen der Liste, die der Stufe p + 1 zugeordnet sind , m'n - mn ' = 1, was eine Bézout-Beziehung ist, aus der wir insbesondere ableiten, dass m und n sind teilerfremd, so dass m / n (sowie m '/ n' ) irreduzibel ist.

Einzigartigkeit

Wir wollen zeigen, dass jeder streng positive Bruch höchstens einmal im Baum vorkommt. Dies ist eine Folge der Tatsache, dass die zugeordnete Liste in jeder Stufe streng ansteigt, was wiederum eine Folge der oben demonstrierten Tatsache ist, dass die aufeinanderfolgenden Brüche in der der Stufe p zugeordneten Liste nahe bei Farey liegen; tatsächlich impliziert m'n - mn '= 1 insbesondere, dass m' / n ' - m / n = 1 / nn' > 0, also m / n < m '/ n' .

Existenz

Wir haben bereits mit dem Euklid-Algorithmus gesehen, dass jeder irreduzible Bruch im Baum auftaucht. Eine weitere Demonstration wird hier gegeben.

Betrachten Sie einen irreduziblen Bruch mit der Bezeichnung a/b . Wir werden vier Folgen von ganzen Zahlen , , und durch Induktion über p bilden : ${\ Anzeigestil (m_ {p})}$ ${\ Anzeigestil (n_ {p})}$ ${\ displaystyle (m '_ {p})}$ ${\ displaystyle (n '_ {p})}$

Für p = 0 setzen wir , , und . ${\ Anzeigestil m_ {0} = 0}$ ${\ Anzeigestil n_ {0} = 1}$ ${\ displaystyle m '_ {0} = 1}$ ${\ displaystyle n '_ {0} = 0}$

In Schritt p stehen uns drei Fälle zur Verfügung:

${\ displaystyle {\ frac {m_ {p} + m '_ {p}} {n_ {p} + n' _ {p}}} = {\ frac {a} {b}}}$ : wir setzen dann und . ${\ displaystyle m_ {p + 1} = m '_ {p + 1} = a}$ ${\ displaystyle n_ {p + 1} = n '_ {p + 1} = b}$
${\ displaystyle {\ frac {m_ {p} + m '_ {p}} {n_ {p} + n' _ {p}}} <{\ frac {a} {b}}}$ : wir stellen ; ; und . ${\ displaystyle m_ {p + 1} = m_ {p} + m '_ {p}}$ ${\ displaystyle n_ {p + 1} = n_ {p} + n '_ {p}}$ ${\ displaystyle m '_ {p + 1} = m' _ {p}}$ ${\ displaystyle n '_ {p + 1} = n' _ {p}}$
${\ frac {m + m '} {n + n'}}> {\ frac ab}$ : wir stellen ; ; und . ${\ displaystyle m_ {p + 1} = m_ {p}}$ ${\ Displaystil n_ {p + 1} = n_ {p}}$ ${\ displaystyle m '_ {p + 1} = m_ {p} + m' _ {p}}$ ${\ displaystyle n '_ {p + 1} = n_ {p} + n' _ {p}}$

Diese Definition hat mehrere Konsequenzen, die leicht durch Wiederholung verifiziert werden können:

die vier Folgen von ganzen Zahlen , , und steigen (aber nicht streng ansteigend). ${\ Anzeigestil (m_ {p})}$ ${\ Anzeigestil (n_ {p})}$ ${\ displaystyle (m '_ {p})}$ ${\ displaystyle (n '_ {p})}$

für alle p Wenn die Brüche und verschieden sind, dann haben wir , sie sind aufeinanderfolgend in der der Stufe p zugeordneten Liste , also insbesondere nahe bei Farey, was insbesondere bedeutet, dass sie irreduzibel sind. Außerdem gehört einer der beiden zum Stadium p und daher gehört sein Median zum Stadium p + 1 . Tatsächlich gehört in der der Stufe p zugeordneten Liste einer von zwei Fraktionen zur Stufe p , folglich gehört der Median von zwei aufeinanderfolgenden Fraktionen zu der Stufe p + 1 . ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {p} / n_ {p} <a / b <m '_ {p} / n' _ {p}}$

für alle p , wenn die Fraktionen und gleich sind , dann sind sie beide gleich a / b , und so ist und für alle . ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {q} / n_ {q}}$ ${\ displaystyle m '_ {q} / n' _ {q}}$ ${\ displaystyle q \ geq p}$

Wir wollen zeigen, dass es ein p gibt, so dass ; wenn ein solches p existiert, dann, wenn man annimmt, dass es das kleinste ist, hat man und da der Median dann zur Stufe p + 1 gehört, zeigt dies, dass man im Baum gefunden hat. ${\ displaystyle a / b = m_ {p + 1} / n_ {p + 1} = m '_ {p + 1} / n' _ {p + 1}}$ ${\ displaystyle a / b = (m_ {p} + m '_ {p}) / (n_ {p} + n' _ {p})}$ $a / b$

Wie wir haben und als Ganzes folgern wir . Ebenso daraus leiten wir ab . Multipliziert man diese beiden Ungleichheiten bzw. und wir erhalten: . ${\ displaystyle a / b> m_ {p} / n_ {p}}$ ${\ displaystyle an_ {p} -bm_ {p}> 0}$ ${\ displaystyle an_ {p} -bm_ {p}}$ ${\ displaystyle an_ {p} -bm_ {p} \ geq 1}$ ${\ displaystyle a / b <m '_ {p} / n' _ {p}}$ ${\ displaystyle bm '_ {p} -an' _ {p} \ geq 1}$ ${\ displaystyle m '_ {p} + n' _ {p}}$ ${\ displaystyle m_ {p} + n_ {p}}$ ${\ displaystyle (m '_ {p} + n' _ {p}) (an_ {p} -bm_ {p}) + (m_ {p} + n_ {p}) (bm '_ {p} -an '_ {p}) \ geq m' _ {p} + n '_ {p} + m_ {p} + n_ {p}}$

Indem wir jedoch die Tatsache nutzen, dass und Nachbarn von Farey sind, haben wir: ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$

{\ displaystyle {\ begin {aligned} (m '_ {p} + n' _ {p}) (an_ {p} -bm_ {p}) + (m_ {p} + n_ {p}) (bm ' _ {p} -an '_ {p}) & = am' _ {p} n_ {p} + an_ {p} n '_ {p} -bm_ {p} m' _ {p} -bm_ {p } n '_ {p} + bm_ {p} m' _ {p} + bm '_ {p} n_ {p} -am_ {p} n' _ {p} -an_ {p}n '_ {p } \\ & = a (m '_ {p} n_ {p} -m_ {p} n' _ {p}) + b (m '_ {p} n_ {p} -m_ {p} n'_ {p}) \\ & = a + b \ end {ausgerichtet}}}

Deshalb haben wir endlich: . ${\ displaystyle a + b \ geq m '_ {p} + n' _ {p} + m_ {p} + n_ {p}}$

Die Folge von ganzen Zahlen ist daher begrenzt durch . Es kann daher nicht streng steigend sein, aber es ist steigend, weil es die Summe von vier steigenden Folgen ist, so dass es einen Rang p gibt, von dem aus es stationär ist. Aber dann müssen wir haben, sonst hätten wir und definitionsgemäß wäre mindestens eins (möglicherweise beide) von oder gleich dem Median, so dass die Summe strikt größer als wäre , was der Stationarität der Folge aus p widerspricht . ${\ displaystyle (m '_ {p} + n' _ {p} + m_ {p} + n_ {p})}$ $a + b$ ${\ displaystyle m_ {p} / n_ {p} = m '_ {p} / n' _ {p} = a / b}$ ${\ displaystyle m_ {p} / n_ {p} <a / b <m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {p + 1} / n_ {p + 1}}$ ${\ displaystyle m '_ {p + 1} / n' _ {p + 1}}$ ${\ displaystyle (m_ {p} + m_ {p + 1}) / (n_ {p} + n_ {p + 1})}$ ${\ displaystyle m_ {p + 1} + m '_ {p + 1} + n_ {p + 1} + n' _ {p + 1}}$ ${\ displaystyle m_ {p} + m '_ {p} + n_ {p} + n' _ {p}}$

Vergleich mit Euklids Algorithmuslid

Der Algorithmus von Euklid ermöglicht es, das Vorhandensein eines Bruchs im Baum ausgehend von diesem und durch aufeinanderfolgende euklidische Divisionen, die zur Wurzel hinaufgehen, zu zeigen, wodurch ein Pfad aufgebaut wird, der vom Bruch zur Wurzel führt. Die obige Demonstration geht in die andere Richtung: Ausgehend von der Wurzel erzeugen wir eine Reihe von Brüchen, die schließlich auf dem anfangs gegebenen endet und einen Weg erzeugt, der von der Wurzel zu ihr absteigt. Beachten Sie, dass derselbe Algorithmus, der auf eine reelle Zahl anstatt auf einen Bruch angewendet wird, es ermöglicht, den unendlichen Zweig von Brüchen zu konstruieren, der sich dieser reellen Zahl annähert.

Fortsetzungsbrüche

Jeder Bruch lässt eine endliche kontinuierliche Bruchentwicklung zu, deren Koeffizienten die sukzessiven Quotienten sind, die durch den Euklid-Algorithmus berechnet werden . Derselbe euklidische Algorithmus, der es ermöglicht, den Pfad zu finden, der von der Wurzel des Stern-Brocot-Baums zu einem gegebenen Bruch führt, kann ableiten, dass die Entwicklung in einem Kettenbruch diesen Pfad kodiert. Genau wenn $[ q 1 ; q 2 , ..., q p , 1] = [ q 1 ; q 2 , ..., q p + 1]$ ist die Kettenbruchentwicklung des Bruches $m / n$ , die beiden Töchter von $m / n$ im Stern-Brocot-Baum haben die Kettenbruchentwicklung:

$[ Q 1 ; q 2 , ..., q p + 1, 1] = [ q 1 ; q 2 , ..., q p + 2]$ ,
$[ Q 1 ; q 2 , ..., q p , 1, 1] = [ q 1 ; q 2 , ..., q p 2]$ .

Wir ableiten , durch Induktion , daß die Fraktion $m / n$ erscheint in der Stufe $q 1 + ... + q n$ und dass die Sequenz $( Q 1 + ... + q n )$ beschreibt den Weg , um es von der Wurzel führenden $1/1$ : gehen Sie $q 1$ Schritt nach rechts, dann $q 2$ Schritte nach links usw. bis $q p$ Schritt nach links, wenn $p gerade$ ist, nach rechts, wenn $p$ ungerade ist.

Mit anderen Worten, der Weg zum Expansionsbruch $[ q 1 ; q 2 , ..., q p , 1]$ wird durch das Wort codiert $1 q 1 0 Q 2 ... ε q p$ , wo $ε$ ist das Symbol $0$ , wenn $p$ gerade ist, $1$ , wenn $p$ ungerade ist.

Zum Beispiel ist die Kettenbruchentwicklung von 2/5 $[0; 2, 1, 1] = [0; 2, 2]$ was Pfad $001 entspricht$ : 0 Schritte nach rechts, dann 2 Schritte nach links, dann einen Schritt nach rechts. Wir können auch berechnen, dass die Kettenbruchentwicklung von 17/12 $[1; 2, 2, 2] = [1; 2, 2, 1, 1],$ während der Pfad im Baum, der zu 17/12 führt, durch das Wort $100110$ repräsentiert wird .

Demonstration

Nennen wir die Höhe von der Zahl . Wir nehmen durch Induktion an, dass jeder Bruchteil der Körpergröße kleiner oder gleich oben im Stern-Brocot-Baum auftritt . Wir stellen zunächst fest, dass die beiden mutmaßlichen Töchter von groß sind, und da sie oben erscheinen (ihre Mutter befindet sich oben ), haben wir durch Induktion die Gleichheit von Höhe und Boden des Baumes gut nachgewiesen. $m / n$ ${\ displaystyle N = q_ {1} + \ cdots + q_ {p}}$ $NICHT$ $NICHT$ $m / n$ $N + 1$ $N + 1$ $NICHT$

Es bleibt noch zu zeigen, dass diese beiden Fraktionen tatsächlich die Töchter von sind . Dazu finden wir die beiden Nachbarn von in der dem Stockwerk zugeordneten Liste . $m / n$ $m / n$ $NICHT$

Beginnen wir mit zwei vorläufigen Erinnerungen. Zu den Eigenschaften von Farey-Nachbarschaften gehört insbesondere die Tatsache, dass, wenn und Nachbarn von Farey sind, jeder Bruchteil, der sich strikt zwischen den beiden befindet, durch Iteration der Medianoperation von und erhalten wird , daher beiden notwendigerweise auf einer höheren Ebene im Stern erscheint. Brocot-Baum. $a / b$ $ein '/b'$ ${\ Anzeigestil a '' / b ''}$ $a / b$ $ein '/b'$

Auf der anderen Seite ist if ein Kettenbruch, dessen reduzierte for durch die Rekursion gegeben ist: ${\ displaystyle [q_ {1}; q_ {2}, \ Punkte, q_ {p}]}$ ${\ displaystyle m_ {k} / n_ {k} = [q_ {1}; q_ {2}, ..., q_ {k}]}$ ${\ displaystyle k = 1, \ Punkte, p}$

${\ displaystyle m _ {- 1} = 0}$ , , , ; ${\ Anzeigestil m_ {0} = 1}$ ${\ displaystyle n _ {- 1} = 1}$ ${\ Anzeigestil n_ {0} = 0}$
${\ displaystyle m_ {k + 1} = m_ {k} q_ {k + 1} + m_ {k-1}}$ , . ${\ displaystyle n_ {k + 1} = n_ {k} q_ {k + 1} + n_ {k-1}}$

Vor allem, da wir ${\ displaystyle m / n = [q_ {1}, \ Punkte, q_ {p} +1]}$

{\ displaystyle {\ frac {m} {n}} = {\ frac {m_ {p-1} (q_ {p} +1) + m_ {p-2}} {n_ {p-1} (q_ { p} +1) + n_ {p-2}}} = {\ frac {m_ {p-1} q_ {p} + m_ {p-2} + m_ {p-1}} {n_ {p-1 } q_ {p} + n_ {p-2} + n_ {p-1}}} = {\ frac {m_ {p} + m_ {p-1}} {n_ {p} + n_ {p-1} }}}

Betrachten Sie den Kettenbruch . Dieser ist ein Nachbar von Farey . Tatsächlich können wir die folgende Berechnung durchführen: ${\ displaystyle m '/ n' = [q_ {1}, \ Punkte, q_ {n-1}] = m_ {p-1} / n_ {p-1}}$ $m / n$

{\ displaystyle {\ begin {ausgerichtet} m_ {k + 1} n_ {k} -m_ {k} n_ {k + 1} & = (m_ {k} q_ {k + 1} + m_ {k-1} ) n_ {k} -m_ {k} (n_ {k} q_ {k + 1} + n_ {k-1}) \\ & = - (m_ {k} n_ {k-1} -m_ {k- 1} n_ {k}) \ end {ausgerichtet}}}

woraus wir durch Induktion das und damit das ableiten und sind Farey für nahe . Mit anderen Worten, die Kürzungen von zwei Kettenbrüchen, deren erster ein Präfix des zweiten ist und deren Länge sich von 1 unterscheidet, liegen nahe bei Farey. Daher und sind Nachbarn von Farey. Oder ist Höhe, während Höhe ist , nach Induktionshypothese oben ist , also sind beide in der Liste, die mit der Geschichte verbunden ist , und sind daher darin aufeinanderfolgend. ${\ displaystyle m_ {k + 1} n_ {k} -m_ {k} n_ {k + 1} = (- 1) ^ {k + 1}}$ ${\ displaystyle m_ {k} / n_ {k} = [q_ {1}, \ Punkte, q_ {k}]}$ ${\ displaystyle m_ {k + 1} / n_ {k + 1} = [q_ {1}, \ Punkte, q_ {k + 1}]}$ ${\ displaystyle k = 1, \ Punkte, p}$ ${\ displaystyle m / n = [q_ {1}, \ Punkte, q_ {p} +1]}$ ${\ displaystyle m '/ n' = [q_ {1}, \ Punkte, q_ {p-1}]}$ $m / n$ $NICHT$ $m '/ n'$ ${\ displaystyle N '= q_ {1} + \ cdots q_ {p-1} -1 <N}$ $m '/ n'$ $NICHT'$ $NICHT$

Wir folgern, dass eines der beiden Mädchen von oben ihr Median ist: $m / n$ $N + 1$

{\ displaystyle {\ begin {aligned} {\ frac {m + m '} {n + n'}} & = {\ frac {m_ {p-1} (q_ {p} +1) + m_ {p- 2} + m_ {p-1}} {n_ {p-1} (q_ {p} +1) + n_ {p-2} + n_ {p-1}}} \\ & = {\ frac {m_ {p-1} (q_ {p} +2) + m_ {p-2}} {n_ {p-1} (q_ {p} +2) + n_ {p-2}}} \ end {ausgerichtet} }}

das ist die erwartete Kürzung des Kettenbruchs. ${\ displaystyle [q_ {1}, \ Punkte, q_ {p} +2]}$

Betrachten Sie nun den Bruch . Also haben wir: ${\ displaystyle m '' / n '' = [q_ {1}, \ Punkte, q_ {p}] = m_ {p} / n_ {p}}$

{\ displaystyle {\ begin {aligned} m''n-mn '' & = m_ {p} (n_ {p} + n_ {p-1}) - (m_ {p} + m_ {p-1}) n_ {p} \\ & = m_ {p} n_ {p-1} -m_ {p-1} n_ {p} \\ & = (-1) ^ {p} \ end {ausgerichtet}}}

damit wieder und sind Nachbarn von Farey. Aber ist die Höhe also durch Induktion, ist im Obergeschoss , ist also in der Liste mit dem Stockwerk verbunden . Daher ist die andere Tochter von ihr Median: $m'' / n''$ $m / n$ $m'' / n''$ ${\ displaystyle N '' = q_ {1} + \ cdots + q_ {p} -1 = N-1}$ $m'' / n''$ $N-1$ $m / n$ $NICHT$ $m / n$

{\ displaystyle {\ begin {aligned} {\ frac {m + m ''} ​​​​{n + n ''}} & = {\ frac {m_ {p} + m_ {p-1} + m_ {p }} {n_ {p} + n_ {p-1} + n_ {p}}} \\ & = {\ frac {2m_ {p} + m_ {p-1}} {2n_ {p} + n_ {p -1 }}} \ end {ausgerichtet}}}

das ist die Kürzung des Kettenbruchs, wie angegeben. ${\ displaystyle [q_ {1}, \ Punkte, q_ {p}, 2]}$

Diese Korrespondenz zwischen Kettenbrüchen und dem Stern-Brocot-Baum ist die Grundlage der Definition der Funktion? von Minkowski : Informell entspricht dies der reellen Zahl, die mit einem Zweig des Teilbaums des Stern-Brocot-Baums verbunden ist, der in $1/2$ verwurzelt ist (als unendliche stetige Bruchentwicklung einer reellen Zahl kleiner als 1 gesehen) mit der reellen Zahl, die mit demselben Zweig verbunden ist aber im dyadischen Baum , also zum Realen, dessen Erweiterung zur Basis 2, gesehen als unendliche Folge von 0 und 1, den Ast kodiert.

Bei einem Bruch kleiner 1, dessen Erweiterung in einen Kettenbruch also die Form $[0; q 1 , ..., q p ]$ , die Funktion? betrachtet den Weg ausgehend vom Bruch $1/2,$ der daher danach $q 1 - 1, ..., q p$ codiert wird $,$ und ordnet ihm das dyadische Rational zu, das an derselben Position im dyadischen Baum erscheint; dies wird berechnet, indem man das Wort $1 q 1 -1 0 q 2 ... ε q p betrachtet,$ das den Pfad codiert, indem man eine 1 am Ende hinzufügt, was $1 q 1 -1 0 q 2 ... ε q p 1 .$ ergibt und Lesen des erhaltenen Wortes als Erweiterung in Basis 2 eines dyadischen Rationalen.

Zum Beispiel $2/5$ hat für die Erweiterung $[0; 2, 2] = [0; 2, 1, 1]$ . Der Weg, der vom Bruch $1/2$ dorthin führt, wird daher unten codiert $(1, 1)$ , was das Binärwort $0 1 1 1 1 = 011$ ergibt . Dieses Wort wird als binäre Erweiterung des dyadischen Rationalen $(0,011) 2 = 1/4 + 1/8 = 3/8$ gelesen . Ebenso hat $5/7$ für die Erweiterung $[0; 1, 2, 1, 1]$ , also wird sein Weg von $1/2$ danach codiert $(0, 2, 1)$ , daher das Binärwort $0 0 1 2 0 1 1 = 1101$ was schließlich die Erweiterung binär $(0,1101) 2 = 1/2 + 1/4 + 1/16 = 13/16$ .

Matrixalgorithmus

Wir geben hier eine Methode an, die den Matrixkalkül verwendet , um einen Bruch zu bestimmen, der seine Position im Stern-Brocot-Baum kennt, was eine Variante der Berechnung der Reduktionen seiner Expansion in einen Kettenbruch ist. Zur besseren Lesbarkeit werden wir in diesem Abschnitt die Pfade als Wörter im Alphabet kodieren, die aus den beiden Buchstaben G (für Bewegungen nach links) und D (für Bewegungen nach rechts) bestehen.

Besteht also ein Wort S aus G und D , so definieren wir f (S) als den S korrespondierenden Bruch , also den Leistungsbruch ausgehend von der Wurzel und entlang des von S codierten Weges . Wenn zum Beispiel S = GGD ist, dann ist f (S) = 2/5.

Wir betrachten nur 2x2-Matrizen oder 1x2-Spaltenmatrizen. Bei einer gegebenen Spaltenmatrix bezeichnen wir die rationale . Wenn und zwei Spalte Matrizen sind, deren Median ist ; die Terminologie ist damit begründet, dass der Bruch der Median im oben definierten Sinne von Brüchen und ist . ${\ Beginn {pmatrix} m \\ n \ Ende {pmatrix}}$ ${\ displaystyle q {\ begin {pmatrix} m \\ n \ end {pmatrix}}}$ ${\ frac mn}$ $V_{1}$ $V_ {2}$ $V_ {1} + V_ {2}$ ${\ displaystyle q (V_ {1} + V_ {2})}$ ${\ displaystyle q (V_ {1})}$ ${\ displaystyle q (V_ {2})}$

Beachten Sie, dass der Median von und durch Anwenden der Matrix aus den beiden Blöcken und auf die Spaltenmatrix erhalten wird ; und da das gleiche Ergebnis mit der Blockmatrix erhalten wird . Zusammenfassend : $V_{1}$ $V_ {2}$ ${\ begin {pmatrix} V_ {1} & V_ {2} \ end {pmatrix}}$ $V_{1}$ $V_ {2}$ ${\ displaystyle {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}$ ${\ Anzeigestil V_ {1} + V_ {2} = V_ {2} + V_ {1}}$ ${\ displaystyle {\ begin {pmatrix} V_ {2} & V_ {1} \ end {pmatrix}}}$

{\ displaystyle V_ {1} + V_ {2} = {\ begin {pmatrix} V_ {1} & V_ {2} \ end {pmatrix}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} V_ {2} & V_ {1} \ end {pmatrix}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}

Durch die Definition des Stern-Brocot Baum, jede Fraktion erscheint als der Median von zwei Fraktionen und von denen eine auf dem Boden unmittelbar darüber befindet. Die Idee des Matrixalgorithmus besteht darin, zu berechnen und nicht ; genauer werden wir die Matrix berechnen . Wir folgern daraus, da wir das gerade gesehen haben . ${\ Anzeigestil q (V)}$ ${\ displaystyle q (P_ {1})}$ ${\ displaystyle q (P_ {2})}$ $P_ {1}$ $P_ {2}$ $V$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ $V$ ${\ displaystyle V = {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}$

Dazu bemerken wir, dass wenn als Median von und erhalten wird , dann die beiden linken und rechten Töchter von jeweils die Mediane von und und von und sind . Mit anderen Worten, wir gehen von der Matrix, die mit verbunden ist, zu den Matrizen, die mit ihrer linken Tochter verbunden sind, und mit ihrer rechten Tochter verbunden. ${\ Anzeigestil q (V)}$ ${\ displaystyle q (P_ {1})}$ ${\ displaystyle q (P_ {2})}$ ${\ Anzeigestil q (V)}$ ${\ displaystyle q (P_ {1})}$ ${\ Anzeigestil q (V)}$ ${\ Anzeigestil q (V)}$ ${\ displaystyle q (P_ {2})}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ Displaystil V = P_ {1} + P_ {2}}$ ${\ displaystyle {\ begin {pmatrix} P_ {1} + P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} + P_ {2} \ end {pmatrix}}}$

Dies führt zu definieren, seitdem haben wir: und . ${\ hat G} = {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}}, \, {\ hat D} = {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ Ende {pmatrix}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}} {\ hat {G}} = {\ begin {pmatrix} P_ {2} + P_ {1} & P_ { 1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}} {\ hat {D}} = {\ begin {pmatrix} P_ {2} & P_ {2} + P_ { 1} \ end {pmatrix}}}$

So haben wir die Matrizen definiert, die den beiden linken und rechten Abstiegen von einer Mutter zu ihrer Tochter entsprechen; bleibt, den Prozess entlang des Pfads S zu iterieren (wir sagen, dass wir das Monoid der Wörter auf die Matrizen wirken lassen) durch die rekursive Definition:

if ist das leere Wort (das den Pfad von der Wurzel zu sich selbst darstellt) then ; ${\ Displaystil S = \ Epsilon}$ ${\ displaystyle {\ hat {S}} = {\ hat {\ epsilon}} = {\ begin {pmatrix} 1 & 0 \\ 0 & 1 \ end {pmatrix}}}$
if stellt einen Weg dar, der mit einer Linksbewegung endet, dann ; ${\ Anzeigestil S = TG}$ ${\ displaystyle {\ Hut {S}} = {\ Hut {T}} {\ Hut {G}}}$
if stellt einen Weg dar, der in einer geraden Bewegung endet, dann . ${\ Anzeigestil S = TD}$ ${\ displaystyle {\ Hut {S}} = {\ Hut {T}} {\ Hut {D}}}$

Beachten Sie, dass die Matrix die Form hat, wobei und die beiden Spaltenmatrizen sind, die den 2 Fraktionen 0/1 und 1/0 entsprechen, deren Median die Wurzel des Stern-Brocot-Baumes ist. Somit ermöglicht die dem leeren Pfad zugeordnete Matrix die Berechnung des dem leeren Pfad zugeordneten Bruchteils, nämlich der Wurzel des Baums. Wir bemerken, dass dies die Identitätsmatrix ist; Um diese Vereinfachung zu erreichen, haben wir die Reihenfolge der Matrizen umgekehrt und ziehen es vor, zu berechnen statt . ${\ Displaystil {\ Hut {\ Epsilon}}}$ ${\ displaystyle {\ begin {pmatrix} V_ {2} & V_ {1} \ end {pmatrix}}}$ ${\ displaystyle V_ {1} = {\ begin {pmatrix} 0 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle V_ {2} = {\ begin {pmatrix} 1 \\ 0 \ end {pmatrix}}}$ ${\ Displaystil {\ Hut {\ Epsilon}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$

Also , wenn das Wort , wo das ist G oder D dann die Matrix . $S$ ${\ displaystyle S_ {1} S_ {2} \ ldots S_ {n}}$ $Ja}$ ${\ Hut S}$ ${\ displaystyle {\ Hut {\ epsilon}} {\ Hut {S}} _ {1} \ Punkte {\ Hut {S}} _ {n} = {\ Hut {S}} _ {1} \ Punkte { \ Hut {S}} _ {n}}$

Dies gibt uns eine sehr schöne Möglichkeit, unseren Bruch zu berechnen : $f (S)$

{\ displaystyle f (S) = q \ left ({\ hat {S}} _ {1} {\ hat {S}} _ {2} \ ldots {\ hat {S}} _ {n} {\ begin {pmatrix} 1 \\ 1 \ Ende {pmatrix}} \ rechts)}

Am Beispiel des Pfades, der zum Bruch 2/5 führt, haben wir also: ${\ Anzeigestil S = GGD}$

${\ displaystyle {\ Hut {S}} = {\ Hut {G}} {\ Hut {G}} {\ Hut {D}} = {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end { pmatrix}} { \ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}} {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 1 \\ 2 & 3 \ Ende {pmatrix}}}$ damit endlich wie erwartet. ${\ displaystyle {\ hat {S}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} 2 \\ 5 \ end {pmatrix}}}$

Siehe auch

Zum Thema passende Artikel

Externe Links

Roger Mansuy, " Achille Brocot, Mathematiker in seiner Freizeit " , auf CultureMATH ,20. Mai 2008
(en) Eric W. Weisstein , „ Stern-Brocot Tree “ , auf MathWorld

Verweise

Linas Vepstas, " Das Minkowski-Fragezeichen und die Modulare Gruppe SL (2, Z) " ,2004

Konkrete Mathematik ( 2 th Ausgabe) an Ronald Graham , Donald Knuth und Oren Patashnik ( ISBN 978-2-7117-4824-2 )