Hilbert-Kurve

Abb. 1: Das Hilbert-Polygon in sieben Iterationen, als achtes die Hilbert-Kurve

In der Mathematik ist die Hilbert-Kurve eine (stetige) Kurve, die – durch Wiederholung ihres Konstruktionsverfahrens – jedem beliebigen Punkt einer quadratischen Fläche beliebig nahe kommt und im Limes die Fläche vollständig ausfüllt. Die Hilbert-Kurve ist eine sogenannte FASS-Kurve, somit eine raumfüllende Kurve (engl. space-filling curve, abgekürzt SFC). Sie wurde 1891 von dem deutschen Mathematiker David Hilbert entdeckt. Die Möglichkeit, mit einer stetigen eindimensionalen Kurve ein zweidimensionales Gebiet komplett abdecken zu können, war den Mathematikern des neunzehnten Jahrhunderts neu (siehe auch Monsterkurve).

Die Hilbert-Kurve lässt sich durch Rekursion definieren und konstruieren. Die $n$-te Rekursionsstufe wird Hilbert-Kurve der $n$-ten Iteration (auch Hilbert-Polygon), $H_{n}$, genannt. Dessen euklidische Länge ist $2^{n}-2^{-n}$, das heißt, sie wächst exponentiell mit $n$. Der Limes $\textstyle H:=\lim _{n\to \infty }H_{n}$ hat aufgrund der Eigenschaft, raumfüllend zu sein, eine Hausdorff-Dimension von exakt 2.

Das Hilbert-Polygon (die Hilbert-Kurve) bringt die Punkte im Quadrat in eine lineare Reihenfolge, die Hilbert-Ordnung genannt wird. Mit ihrer Hilfe lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört binäres Suchen, binärer Suchbaum, Skip-Liste und andere.

Abb. 2: Farbkodierte Entfernungstabelle von Orten auf dem Hilbert-Polygon der 4. Iteration

Beim direkten Zugriff steht die Hilbert-Ordnung in Konkurrenz zu einem Zugriff, bei dem die linearen Ordnungen der Dimensionen in unterschiedlicher Rangigkeit zu einer lexikographischen Ordnung hintereinander geschaltet sind – im internen Speicher über ein mehrfach indiziertes Feld resp. im externen Speicher per wahlfreien Zugriff (Random Access). Wenn sich dies gut organisieren lässt, schneidet sie etwas schlechter ab. Sie ist aber überlegen, wenn es sich um eine ungefähre Suche handelt, an die sich eine sequentielle Suche anschließt, bei der Nachbarschaftsbeziehungen (engl. clustering) vorteilhaft ausgenutzt werden können. Dies ist bei mehrdimensionalen Räumen $\mathbb {R} ^{d}$, bei denen Nachbarschaft durch die euklidische Metrik definiert ist, häufig der Fall – beispielsweise, wenn auf geographische Merkmale eines Objekts über die Schlüssel Länge und Breite zugegriffen werden soll. Die Hilbert-Kurve ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung. Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter.

Die Zuordnung $h_{n}$ des Hilbert-Polygons der $n$-ten Iteration ist umkehrbar und kann zu beliebiger Feinheit gesteigert werden (s. Abb. 1). Dieses und die gute Nachbarschaftserhaltung hat eine Vielfalt von Anwendungen der Hilbert-Kurve in der Informatik eröffnet, so in der Bildverarbeitung, Datendarstellung, im Hochleistungsrechnen und in anderen Gebieten.

Konstruktionsverfahren

• 

  Abb. 3a: 1. Iteration $H_{1}$ der Hilbert-Kurve

• 

  Abb. 3b: Hilbert-Kurve $H_{2}$ der 2. Iteration

• 

  Abb. 3c: Hilbert-Kurve $H_{3}$ der 3. Iteration

• 

  Abb. 3d: 3D-Hilbert-Kurven, 1. bis 3. Iteration

Die Abb. 3a bis 3c aus dem definierenden Artikel zeigen die drei ersten Iterationen der Hilbert-Kurve. Bei der $n$-ten Iteration bringen $4^{n}$ Nummern die $4^{n}$ Intervalle (Teilstrecken der Linie oben in den Grafiken) und die $4^{n}$ Quadrate mit gleichen Nummern zur Entsprechung. Die verstärkten polygonalen Linien bringen genau diese Reihenfolge der Quadrate heraus.

Eine nachfolgende Iteration verfeinert – bei Intervallen wie bei Quadraten – die Schachtelung um den Faktor 4.

Iterationsschritte

Die Konstruktion der Hilbert-Kurve als einer raumfüllenden Kurve

${\begin{array}{llllll}h\;\colon &{\mathcal {I}}:=[0,1]:=\{t\mid 0\leq t\leq 1\}&\to &{\mathcal {I}}^{d}&=&\;\;[0,1]\times [0,1]\times \dotso \\&t&\mapsto &h(t)&=&(\;\;\;\underbrace {x\;\;\;\;,\;\;\;\;\,y\;\;\;\;,\;\dotso } _{d{\text{ Komponenten}}}\;\;\;)\\\end{array}}$

beruht auf einem rekursiven Verfahren:

1. Das zu füllende $d$-dimensionale Gebiet (Intervall) $[0,1]^{d}={\mathcal {I}}^{d}$ wird aufgeteilt in $2^{d}$ kongruente Teilgebiete, die die halbe Seitenlänge des („großen“) Ausgangsgebiets besitzen.
   Das Verfahren überführt damit 1D-Schachtelungen von Intervallen in 2D-Schachtelungen von Quadraten (oder in 3D-Schachtelungen von Würfeln), ist also inklusionserhaltend.
2. Für jedes Teilgebiet ist eine raumfüllende Kurve zu finden, die durch verkleinerte Verschiebung, Spiegelung und/oder Rotation der Vorgängerkurve gebildet wird. (Prinzip der Selbstähnlichkeit)
3. Die Spiegelungs- und Rotationsoperationen sind so zu wählen, dass sich die $2^{d}$ Teilkurven zu einer einzigen gerichteten Kurve zusammenfügen.

Dieser Artikel beschränkt sich fast ausschließlich auf die Dimensionszahl 2, also auf die Abbildung des Einheitsintervalls ${\mathcal {I}}$ auf das Einheitsquadrat ${\mathcal {Q}}:={\mathcal {I}}^{2}$. Bei dieser Dimensionszahl treten alle einschlägigen mathematischen Phänomene bereits in Erscheinung.

Während die Hilbert-Kurve (auf der Ausgabeseite) ein „Teilquadrat“ durchläuft (füllt), soll auch der Parameter $t$ auf der Eingabeseite das ihm entsprechende Teilintervall durchlaufen. Dies entspricht der Vorgabe, dass die Hilbert-Kurve in allen Bereichen »gleich schnell« voranschreitet.

Um dies sicherzustellen, wird als Intervallschachtelung auf der Parameterseite die („4-adische“) Darstellung von $t=:0_{4}.\!\tau _{1}\tau _{2}\tau _{3}\dotso \in {\mathcal {I}}$ im Quaternärsystem mit $\tau _{n}\in \{0,1,2,3\}$ gewählt. Es sei $t_{n}:=0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{n}$ gesetzt, so dass das $n$-te Intervall in der Schachtelung des Parameters $t$

$\{t\mid t_{n}\leq t<t_{n}+4^{-n}\}=[t_{n},t_{n}+4^{-n}[\;=[\,0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{n},\;0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{n}{\overline {3}}\,[$

ist. Auf der Seite des Quadrats (Ausgabeseite) werden die Koordinaten $x=:0_{2}.\!\xi _{1}\xi _{2}\xi _{3}\dotso \in {\mathcal {I}}$ und $y=:0_{2}.\!\eta _{1}\eta _{2}\eta _{3}\dotso \in {\mathcal {I}}$ im Binärsystem („2-adisch“) dargestellt mit $\xi _{n},\eta _{n}\in \{0,1\}$. Die (abbrechenden) Koordinaten $(x_{n},y_{n})\in {\mathcal {I}}^{2}={\mathcal {Q}}$ mit $x_{n}:=0_{2}.\!\xi _{1}\xi _{2}\dotso \xi _{n}$ und $y_{n}:=0_{2}.\!\eta _{1}\eta _{2}\dotso \eta _{n}$ stehen dabei für das Teilquadrat, dessen linke untere Ecke (oder auch dessen Mittelpunkt) sie bedeuten, und die Folge der durch ${\bigl (}(x_{n},y_{n}){\bigr )}_{n\in \mathbb {N} }$ spezifizierten Quadrate, die die Seitenlänge $2^{-n}$ und die Fläche $4^{-n}$ haben, macht eine 2D-Intervallschachtelung in der Ebene aus. Diese 1D-, 2D- und $d$D-Schachtelungen seien als die „Rasterschachtelung“ $R:={\bigl (}R_{n}{\bigr )}_{n\in \mathbb {N} }$ (der Hilbert-Kurve) bezeichnet.

Die $n$-te Iteration der „Hilbert-Kurve“ ist eine geordnete Folge von $4^{n}$ (an genau einer Quadratseite zusmmenstoßenden) Quadraten, eine Folge, die am einfachsten durch einen gerichteten Polygonzug von Quadratmittelpunkt

${\bigl (}{\dot {x}}_{n}(t),{\dot {y}}_{n}(t){\bigr )}:={\bigl (}x_{n}(t)+2^{-n-1},y_{n}(t)+2^{-n-1}{\bigr )}$

zu Quadratmittelpunkt dargestellt wird. Dieser Polygonzug wird häufig als Hilbert-Polygon (engl. manchmal Hilbert pseudo curve) $H_{n}$ der $n$-ten Iteration bezeichnet (Beispiele sind die „Hilbert-Kurven“ der 1. bis 3. Iteration in den obigen Abbildungen). Der Polygonzug ist eine einfache Kurve mit Anfang, Ende und ohne Berührungen oder Überschneidungen. Alle Hilbert-Polygone derselben Iteration lassen sich durch eine Ähnlichkeitsabbildung ineinander überführen.

Offener Polygonzug

Im Folgenden wird gezeigt, wie die $4^{n}$ Quadrate eines Rasters $R_{n}$ in eine Reihenfolge gebracht werden, derart, dass sie bei wachsendem $n$ immer kleiner und schmaler werden, einander näher rücken und im Limes eine Kurve bilden. (Das ganze Einheitsquadrat füllen sie konstruktionsgemäß von Anfang an aus.)

Im Sinn des obigen Programms sei rekursiv angenommen, dass in einem Teilquadrat $\in R_{n}$ ein Kurvenpunkt der selbstähnlichen Hilbert-Kurve berechnet ist. Es geht nun darum, diesen Punkt so in das Quadrat $\in R_{n-1}$ zu holen, dass alle solche Punkte zusammen genommen einen einfach-zusammenhängenden Polygonzug (eine zusammenhängende Folge von Quadraten des Rasters $R_{n}$) und im Limes eine stetige Kurve ergeben. Eine solche Transformation lässt sich zerlegen in:

die naheliegende Skalierung (um den Faktor ${\tfrac {1}{2}}$),	(Skal)
eine (die Hilbert-Kurve charakterisierende) Parallelverschiebung und	(Parv)
eine Isometrie (= orthogonale Abbildung = Drehung und/oder Spiegelung).	(Ausr)

Für die Wahl der passenden Drehungen und/oder Spiegelungen ist die Festlegung hilfreich, wo ein Quadrat einer Rasterschachtelung $R_{n}$ von der Kurve betreten und wo es verlassen wird. Bei der Hilbert-Kurve sind dies die Ecken genau einer Quadratseite. Da es auch auf die Richtung und Orientierung ankommt, werde dieses Charakteristikum eines Quadrats im Raster mit dem Begriff „Ausrichtung“ (engl. orientation , state) versehen und die Ausrichtung „hoch–rechts–runter“ (resp. die Strecke ${(0,0){\underline {\color {Mulberry}\bullet \!\!\!\color {Green}\to }}(1,0)}$ für „Eintritt links unten–Austritt rechts unten“) mit dem Buchstaben $\mathbf {A}$ gekennzeichnet.

Aber auch die bloße Platzierung des Teilquadrats hängt von der Ausrichtung ab. Ist das große Quadrat $\in R_{n-1}$ (links in der Abbildung 4) gemäß $\mathbf {A}$ ausgerichtet, dann wird bei der Hilbert-Kurve das Quadrat $\in R_{n}$ abhängig von der Quaternärziffer $\tau =\tau _{n}$ in eines der vier Teilquadrate platziert, und zwar wird der Quaternärstelle $\tau =0$ das Teilquadrat links unten zugewiesen, der $\tau =1$ dasjenige links oben, der $\tau =2$ rechts oben und der Quaternärstelle $\tau =3$ das Teilquadrat rechts unten, also nach dem „Grundmotiv“ mit $x$ nach rechts und $y$ nach oben. Ein Grundmotiv für die 3-dimensionale Hilbert-Kurve ist .

Andere Ausrichtungen (als $\mathbf {A}$) lassen sich durch eine vorgeschaltete Isometrie aus der Diëdergruppe $D_{4}$ des Quadrats bewältigen.

Die zur Herstellung des einfach-zusammenhängenden Polygonzuges (und damit der im Limes stetigen Hilbert-Kurve) erforderlichen Drehungen und/oder Spiegelungen sind ebenfalls Isometrien aus $D_{4}$ und zusammen mit der Platzierung auszuführen. Diese Kombination wird im folgenden Abschnitt unter dem Begriff „Transformation“ beschrieben.

Transformation der rekursiven Teilquadrate auf das Einheitsquadrat

Abb. 4: Die Einbettung des Teilquadrats der $n$-ten Iteration rechts resp. eines seiner Punkte ${\color {Mulberry}\bullet }$ in das 4 mal so große Quadrat links – in welches Teilquadrat und wie, wird von der Quaternärziffer $\tau :=\tau _{n}$ abhängig gemacht.

Um den Wechsel der Ausrichtung von einer Iteration zur nächsten präzise zu spezifizieren, sei angenommen, dass beide Quadrate, das große (links in der Abbildung 4) wie das Teilquadrat (rechts), gemäß $\mathbf {A}$ ausgerichtet sind.

Die benötigten vier Transformationen hängen von der Quaternärziffer $\tau \in \{0,1,2,3\}$ ab und seien mit $T_{0},T_{1},T_{2}$ und $T_{3}$ bezeichnet:

$T_{1}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {x}{2}},{\tfrac {y+1}{2}}{\bigr )}$	$T_{2}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {x+1}{2}},{\tfrac {y+1}{2}}{\bigr )}$
$T_{0}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {y}{2}},{\tfrac {x}{2}}{\bigr )}$	$T_{3}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {2-y}{2}},{\tfrac {1-x}{2}}{\bigr )}$

Alle Transformationen skalieren zunächst die übergebenen Koordinaten $(x,y)$ des Punktes mit dem Faktor ${\tfrac {1}{2}}$, da die Teilquadrate die halbe Seitenlänge haben, und enthalten eine Verschiebung in das durch $\tau$ (s. o.) bestimmte Teilquadrat. Zudem ist von einer Transformation je nach Lage ggf. eine (von $\tau$ abhängige) Viertelrotation, Spiegelung, d. h. eine Kongruenzabbildung $\in D_{4}$ durchzuführen:

• Bei $\tau =0$ kommt die Transformation $T_{0}$ zum Zuge. Sie spiegelt ihr Argument an der »Hauptdiagonalen« (strichpunktiert in Abbildung 4), wodurch sich der Drehsinn des Quadrats ändert. Die Eintrittsecke ins Teilquadrat (links unten) bleibt erhalten.
  (Alle Übertritte von einem Quadrat zum nächsten sind in der Abbildung 6 als kurze blaugrüne Pfeile vom Grundmotiv des einen Quadrats diagonal zur Austrittsecke und von der Eintrittsecke des anderen Quadrats diagonal zu dessen Grundmotiv dargestellt.)
  Die Austrittsecke dieses Teilquadrats ist nachher links oben und führt zum nächsten Teilquadrat mit $\tau =1$.
• Die Zielquadrate bei den Transformationen $T_{1}$ und $T_{2}$ haben dieselbe Ausrichtung $\mathbf {A}$ mit Eintrittsecke links unten und Austrittsecke rechts unten, daher ist keine Spiegelung (und keine Drehung) erforderlich. Jedoch wird die Kurve skaliert in je eines der oberen Teilquadrate verschoben.
  $T_{1}$ verschiebt bei $\tau =1$ die Kurve um ${\tfrac {1}{2}}$ in $y$-Richtung, also ins linke obere Teilquadrat. $T_{2}$ verschiebt für $\tau =2$ die Kurve diagonal ins rechte obere Teilquadrat.
• Die Transformation $T_{3}$ spiegelt für $\tau =3$ ihr Argument an der »Nebendiagonalen« (strichpunktiert in Abbildung 4), wodurch der Drehsinn des Quadrats sich ändert. Danach wird das gespiegelte Ergebnis um ${\tfrac {1}{2}}$ in $x$-Richtung, also ins rechte untere Teilquadrat verschoben, so dass die Eintrittsecke rechts oben liegt und die Austrittsecke (rechts unten) mit dem des Ausgangsquadrates übereinstimmt.

Ersichtlich sind die Punkte $(x,y)$ über die sie enthaltenden Quadrate des 2D-Rasters $R_{n}$ in eine Reihenfolge gebracht, die der Reihenfolge der Intervalle des Parameters $t$ entspricht – sowohl bezüglich der 4 Teilquadrate des Vorgängerquadrats $\in R_{n-1}$ als auch bei den Übertritten zwischen den Vorgängerquadraten.

Dabei findet der Übertritt von einem Quadrat zum nachfolgenden Nachbarquadrat immer nur über eine gemeinsame Quadratseite statt (s. kurze blaugrüne Pfeile in der Abbildung 6), sodass sich beim Polygonzug von Quadratmittelpunkt zu Quadratmittelpunkt ausschließlich Teilstrecken gleicher Länge, der Seitenlänge, ergeben, die alle zu den Koordinatenachsen parallel und miteinander in einer linearen Kette verbunden sind – mit der offensichtlichen Konsequenz, dass die Hilbert-Kurve im Limes stetig ist. Die Teilstrecken des Polygons erfahren dabei nur Richtungswechsel $\in \{-90^{\circ },0,90^{\circ }\}$.

Die Abbildung 4 zeigt darüber hinaus, dass ausgehend von der Ausrichtung $\mathbf {A}$ zwei neue Ausrichtungen $\mathbf {D}$ („rechts-hoch-links“) und $\mathbf {B}$ („links-runter-rechts“) hinzukommen, und die Abbildungen 6 und 5, dass nur noch eine weitere Ausrichtung („runter-links-hoch“), genannt $\mathbf {C}$, fehlt, so dass es bei insgesamt vier Ausrichtungen bleibt. Die zugehörige Gruppe $V$ der benötigten Isometrien ist eine Untergruppe der Diedergruppe $D_{4}$ des Quadrats, wird erzeugt von der Drehung um 180° (Spiegelung am Quadratmittelpunkt) und einer Spiegelung an einer Diagonalen, hat also die Gruppenordnung vier, den Exponenten zwei und ist isomorph zur Kleinschen Vierergruppe.

Abb. 5: Hilbert-Polygon der ersten bis dritten Iteration.
Die Quadratmittelpunkte sind in der Reihenfolge des Hilbert-Index (Schrift gedreht) miteinander verbunden.
Der Hilbert-Index eines Teilquadrates mit Mittelpunkt $(x,y)$ findet sich am Schnittpunkt von $x$-Spalte mit $y$-Zeile.
Blass in den Quadratmitten die „absolute Ausrichtung“.
(Alle Zahlen im Binärsystem)

In der Abbildung 5 ist das große Quadrat, das Quadrat der $0$-ten Iteration (= Quadrat des Rasters $R_{0}$), gemäß $\mathbf {A}$ ausgerichtet – und dementsprechend in seiner Mitte gekennzeichnet. Da die Ausrichtung dieses Quadrats eine besondere Rolle spielt, wird sie als die „primäre Ausrichtung“ bezeichnet. Die „relativen Ausrichtungen“ der Quadrate höherer Iterationen sind rekursiv von Iteration zu Iteration den Regeln dieses Abschnitts gemäß entwickelt und als „absolute Ausrichtungen“ im Zentrum der Quadrate eingetragen. Die absolute Ausrichtung eines Quadrats ist also die Akkumulation der relativen Ausrichtungen aller seiner rekursiven Vorgänger.

Bemerkung

Weil im vorstehenden Abschnitt das Quadrat der Iteration $\in R_{n}$ »zeitlich« vor dem großen Quadrat $\in R_{n-1}$ als »vorhanden« angesehen wird, könnte man anzunehmen versucht sein, dass die (Ausrichtungen der) großen Quadrate (links) der höherwertigen Ziffern durch diejenigen spätererer Iterationen (rechts) beeinflusst würden. Das Gegenteil ist jedoch der Fall:

• Die absolute Ausrichtung des großen Quadrats beeinflusst (zusammen mit der Quaternärziffer $\tau _{n}$) direkt die absolute Ausrichtung des Teilquadrats.

Das kann man übrigens schon beim Zeichnen von Hilbert-Polygonen zweier aufeinander folgender Iterationen feststellen, spielt für die Umkehrbarkeit der $h_{n}$ (s. Abschnitt #Hilbert-Polygon) eine große Rolle und wirkt sich auf die (Art der) Stetigkeit von $h$ (s. Abschnitt #Hilbert-Kurve) aus. Diese Abhängigkeit ist in der tabellarischen Abbildung 6 und im gleichwertigen Übergangsdiagramm der Abbildung 7 für alle vier vorkommenden Varianten (= Ausrichtungen) herausgearbeitet. Eine darauf basierende explizite Rekursionsformel für $h$ wird im entsprechenden Abschnitt vorgestellt.

Diskrete Mathematik

Hilbert-Polygon

Die Zuordnung des Hilbert-Polygons der $n$-ten Iteration ist

${\begin{array}{lrlllll}h_{n}\;\colon &{\mathcal {I}}&\to &{\mathcal {Q}}:=&\;\;{\mathcal {I}}&\times &{\mathcal {I}}\\&t&\mapsto &\displaystyle h_{n}(t)=h_{n}(t_{n})=&{\bigl (}x_{n}(t)=x_{n}(t_{n})&,&y_{n}(t)=y_{n}(t_{n}){\bigr )}\,.\\\end{array}}$

Das Bild $h_{n}({\mathcal {I}})$ ist bei endlichem $n$ eine diskrete Menge, und zwar

$h_{n}({\mathcal {I}})={\mathcal {I}}_{n}\times {\mathcal {I}}_{n}={\mathcal {I}}_{n}^{2}$   mit   ${\mathcal {I}}_{n}:=\{0,2^{-n},2\cdot 2^{-n},\dotso ,1-2^{-n}\}=\{0,1,2,\dotso ,2^{n}\!-\!1\}\cdot 2^{-n}$.

Die Koordinaten ${\bigl (}x_{n}(t),y_{n}(t){\bigr )}$ stehen dabei für linke untere Ecken von Quadraten des Rasters $R_{n}$. In graphischen Darstellungen wird die Reihenfolge der Quadrate, deretwegen ja der ganze Aufwand getrieben wird, am einfachsten durch Verbindungsstrecken (die aber genau genommen nicht zum Hilbert-Polygon gehören) zwischen den Quadraten sichtbar gemacht. Am deutlichsten wird diese Reihenfolge, wenn man statt der Ecken die Quadratmittelpunkte

${\bigl (}{\dot {x}}_{n}(t),\,{\dot {y}}_{n}(t){\bigr )}:={\bigl (}x_{n}(t)+2^{-n-1},\;y_{n}(t)+2^{-n-1}{\bigr )}$

nimmt, weil die Verbindungsstrecken verschiedener Iterationsstufen dann getrennt bleiben und Symmetrien klarer herauskommen.

Eingeschränkt auf die Menge ${\mathcal {I}}_{2n}=\{0,1,\dotso ,4^{n}\!-\!1\}\cdot 4^{-n}$ ist ${\hat {h}}_{n}:=h_{n}\!\mid _{{\mathcal {I}}_{2n}}$ umkehrbar und hat die Umkehrfunktion ${\hat {k}}_{n}$, die im Abschnitt Hilbert-Index behandelt wird. Nach Konstruktion ist ferner

${\hat {h}}_{n}(t\pm 4^{-n})\;\;\,=\;\;\,{\begin{cases}{\hat {h}}_{n}(t)\pm (2^{-n}\!\!\!\!\!\!&,\!\!\!\!\!\!&0&)\\{\hat {h}}_{n}(t)\pm (0&,&2^{-n}\!\!\!\!\!\!&)\,,\end{cases}}$

woraus die Implikation

$|t-t^{\prime }|\leq 4^{-n}\Longrightarrow {\bigl |}{\hat {h}}_{n}(t)-{\hat {h}}_{n}(t^{\prime }){\bigr |}\leq 2^{-n}$

folgt.

Bild- und Definitionsmenge von ${\hat {h}}_{n}$ lassen sich aufgrund ihrer Diskretheit in einfacher Weise so skalieren, dass sie ganzzahlig werden.

Bei den beiden folgenden Algorithmen t2xyR und t2xyI und beim Algorithmus xy2tR erfolgt die Auswertung (Hintereinanderausführung) der verketteten Transformationen wie bei Operatoren üblich rechts-assoziativ, also von rechts nach links. Auf die Programmabschnitte bezogen findet die Auswertung im rekursiven Aufstieg – »auf dem Rückweg« – statt. Damit sich überhaupt etwas ergibt, muss der »Hinweg« abgebrochen werden. Bei jedem Abbruchkriterium (im Pseudocode t2xyR formuliert mit der Genauigkeitsvariablen eps) wird der Punkt $(x,y)$ in das Rasterquadrat gebracht, das zum eingegebenen Teilintervall von $t$ gehört. Kurz: Die Abbildung bildet 1D-Raster korrekt auf 2D-Raster ab.

Es gibt aber eine wesentlich wirkungsmächtigere Überlegung:
Eine Abhängigkeit des $n$-ten Quadrats von Teilen der $(n+1)$-sten oder höherer Iterationsstufe existiert überhaupt nicht, weder hinsichtlich der Ziffern $\tau _{\nu }$ (mit $\nu >n$) des Parameters $t$ noch hinsichtlich der Ziffern $(\xi _{\nu },\eta _{\nu })$ der Koordinaten $(x,y)$ noch hinsichtlich der Ausrichtung der Quadrate. Wenn es eine Rekursion gibt, dann kann sie in der Richtung von grob zu fein aufgesetzt werden, bei der die Auswertung im rekursiven Abstieg erfolgt. Die hieraus hervorgehende Rekursionsformel hat den Vorteil, dass ein »Abbruchkriterium« nicht gebraucht wird. (Ein Ergebnis liegt nach einem Abbruch unmittelbar vor – einschließlich einer Angabe über die möglicherweise eingegangene Ungenauigkeit.) Sie zählt damit zu den potentiell unendlichen Verfahren und wird im Abschnitt #Explizite Rekursionsformel beispielhaft vorgestellt.

Rekursiver Algorithmus

Der nachfolgende Pseudocode t2xyR implementiert rekursiv die Abb. 4 mit $\mathbf {A}$ als Ausrichtung für Zwischen- wie Endergebnis. Er nimmt als Argument einen Parameter $t\in {\mathcal {I}}$ und eine Begrenzung eps$:=2^{-n}$ der Iterationstiefe. Zurückgegeben werden die Koordinaten der linken unteren Ecke eines Quadrates der $n$-ten Iteration.

Eingabe:	Parameter $t\in {\mathcal {I}}$
Ausgabe:	Koordinaten $x,y\in {\mathcal {I}}$
Auswertungsrichtung:	fein zu grob

 function t2xyR(t, eps) begin
   if eps > 1 then
     return (0, 0); // im Ergebnisquadrat die linke untere Ecke
   else
     q = floor(4*t);
     // Die Quaternärstelle q ∈ {0, 1, 2, 3} bestimmt,
     //   in welches Teilquadrat der Punkt gehört
     //   und wie er zu transformieren ist.
     r = 4*t – q;
     (x,y) = t2xyR(r, eps*2); // r ∈ I ↦ (x,y) ∈ Q
     switch q do
       case 0: return (y/2,         x/2);
       case 1: return (x/2,         y/2 + 1/2);
       case 2: return (x/2 + 1/2,   y/2 + 1/2);
       case 3: return (1–eps – y/2, 1/2–eps – x/2);
     end switch
   end if
 end function

Abb. 6: Die 4 Übersetzungs-
tabellen vom 4-adischen Parameter ${\color {green}\tau }$ zu den zwei 2-adischen Koordinaten ${\color {red}(\xi ,\eta )}$
– und zurück.
Pro „Ausrichtung“ eine Tabelle.

Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten

Bei der folgenden iterativen Lösung ist $n$ die Nummer der Iteration und $p:=2^{n}$ die Anzahl der 1D-Teilintervalle. Zurückgegeben wird die linke untere Ecke eines Quadrats. Der folgende Pseudocode t2xyI hat ganzzahlige Ein-/Ausgabe (d. h. es wird nicht auf Einheitsintervall oder -quadrat skaliert).

Eingabe:	Parameter $t\in \{0,1,\dotso ,p^{2}-1\}$
Ausgabe:	Koordinaten $x,y\in \{0,1,\dotso ,p-1\}$
Auswertungsrichtung:	fein zu grob

 function t2xyI(t, p) begin
   (x, y) = (0, 0); // im Ergebnisquadrat die linke untere Ecke
   for (m = 1; m < p; m *= 2) do // m wächst exponentiell
     rx = 1 & t/2;      // Binärziffer[1]: 0=links/1=rechts
     ry = 1 & (t ^ rx); // Binärziffer[0]
     (x, y) = rot(x, y, rx, ry, m);
     x += m * rx;
     y += m * ry;
     t /= 4; // zur nächsten Quaternärziffer
   end for
 return (x, y);
 end function

// Drehspiegelung eines Quadrates
 function rot(x, y, rx, ry, p) begin
   if (ry == 0) then
     if (rx == 1) then
       x = p–1 – x;
       y = p–1 – y;
     end if
     // vertausche x und y
     z = x;
     x = y;
     y = z;
   end if
 return (x, y);
 end function

Hierbei kommen die C-Operatoren ^ für bitweises XOR, & für bitweises UND, += für Inkrementieren, *=2 für Verdoppeln und /=2 für Halbieren zum Einsatz.

In der Funktion t2xyI bedeutet die Variable rx das Übereinstimmen des vorletzten Bits bei x und t; analog für ry und y mit dem letzten Bit.

Die Funktion (und ihre Umkehrung s. u.) benutzen die Funktion rot, um die Koordinaten x und y in einem Teilquadrat so zu spiegeln und zu drehen, dass die Teilstücke konsekutiv (stetig) zusammengefügt werden.

Explizite Rekursionsformel

Ist $t=:0_{4}.\!\tau _{1}\tau _{2}\tau _{3}\dotso \in {\mathcal {I}}$ eine 4-adische Darstellung des Parameters, dann lässt sich die (unendliche) Folge ${\bigl (}h_{n}(t){\bigr )}_{n\in \mathbb {N} }={\Bigl (}{\bigl (}x_{n}(t),y_{n}(t){\bigr )}{\Bigr )}_{n\in \mathbb {N} }$ auch als Rekursion über die Quadratmittelpunkte

${\bigl (}{\dot {x}}_{n}(t):=x_{n}(t)+2^{-n-1},\;\;{\dot {y}}_{n}(t):=y_{n}(t)+2^{-n-1}{\bigr )}$

und die „absolute“ Ausrichtung $a_{n}$ mit dem Rekursionsanfang

${\dot {x}}_{0}(t)={\tfrac {1}{2}}$	und
${\dot {y}}_{0}(t)={\tfrac {1}{2}}$	und
$a_{0}(t)=\mathbf {A}$	(Start mit der primären Ausrichtung $\mathbf {A}$)

und dem Rekursionsschritt

${\dot {x}}_{n}(t)$	$={\dot {x}}_{n-1}(t)+2^{-n-1}(2X_{a_{n-1}(t),\,\tau _{n}}-1)$	(RFh_x),
${\dot {y}}_{n}(t)$	$={\dot {y}}_{n-1}(t)\ +2^{-n-1}(2Y_{a_{n-1}(t),\,\tau _{n}}-1)$	(RFh_y) und
$a_{n}(t)$	$=A_{a_{n-1}(t),\,\tau _{n}}$	(RFh_a)

für $n\in \mathbb {N}$ schreiben. Die drei (4×4)-Matrizen

$X:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}0&0&1&1\\1&0&0&1\\1&1&0&0\\0&1&1&0\end{array}}\end{smallmatrix}}\right]\!,\,Y:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}0&1&1&0\\1&1&0&0\\1&0&0&1\\0&0&1&1\end{array}}\end{smallmatrix}}\right]\!,\;A:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}\mathbf {D} &\mathbf {A} &\mathbf {A} &\mathbf {B} \\\mathbf {C} &\mathbf {B} &\mathbf {B} &\mathbf {A} \\\mathbf {B} &\mathbf {C} &\mathbf {C} &\mathbf {D} \\\mathbf {A} &\mathbf {D} &\mathbf {D} &\mathbf {C} \end{array}}\end{smallmatrix}}\right]\;\;{\begin{smallmatrix}{\begin{array}{ll}\leftarrow &\mathbf {A} \\\leftarrow &\mathbf {B} \\\leftarrow &\mathbf {C} \\\leftarrow &\mathbf {D} \end{array}}\end{smallmatrix}}$

sind äquivalent zu den vier Übersetzungstabellen der Abbildung 6. Sie werden an ihrem ersten Index, dem Zeilenindex, durch die absolute Ausrichtung $a_{n-1}(t)\in \{\mathbf {A} ,\mathbf {B} ,\mathbf {C} ,\mathbf {D} \}$ indiziert. Das Ergebnis ist bei $X$, $Y$ und $A$ jeweils eine vierstellige Zeile, die zusammen genommen eine der Übersetzungstabellen darstellen. Jede Stelle (Spalte) einer solchen Zeile wird durch die Quaternärziffer $\tau _{n}\in \{0,1,2,3\}$ indiziert. Daraus resultiert (Gl.n RFh_x und RFh_y) das neue Ziffernpaar $(\xi _{n},\eta _{n})$ für den Punkt $(x,y)$ und die neue absolute Ausrichtung (Gl. RFh_a).

Die Folge ${\bigl (}({\dot {x}}_{n},{\dot {y}}_{n}){\bigr )}_{n\in \mathbb {N} }$ der Quadratmittelpunkte mit ${\dot {x}}_{n}:=0_{2}.\!\xi _{1}\xi _{2}\dotso \xi _{n}+2^{-n-1}$ und ${\dot {y}}_{n}:=0_{2}.\!\eta _{1}\eta _{2}\dotso \eta _{n}+2^{-n-1}$, steht für die 2D-Intervallschachtelung

${\begin{array}{lllll}&{\bigl (}[{\dot {x}}_{n}-2^{-n-1},&{\dot {x}}_{n}+2^{-n-1}]&\times \;[{\dot {y}}_{n}-2^{-n-1},&{\dot {y}}_{n}+2^{-n-1}]{\bigr )}_{n\in \mathbb {N} }\\=&{\bigl (}[x_{n},&x_{n}+2^{-n}]&\times \;[y_{n},&y_{n}+2^{-n}]{\bigr )}_{n\in \mathbb {N} },\\\end{array}}$

die $h(t)$ zum Limes hat.

Beweis der Rekursionsformel

Die Gleichung RFh_a akkumuliert – wie in der Erläuterung zur Abb. 6 ausgeführt – die relativen Ausrichtungen (Teil Ausr) zwischen Viertelquadrat und großem Quadrat und implementiert damit (zusammen mit der 2D-Intervallschachtelung (Teil Skal) der Gl.n RFh_x und RFh_y) die Transformationen $T_{0},T_{1},T_{2}$ und $T_{3}$ (Teil Parv) des Abschnitts #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat.

Erläuterungen zu den Abbildungen 6 und 7

Die oberste der vier Graphiken der Abb. 6, die für die Ausrichtung $\mathbf {A}$, ist ein Auszug aus der Abb. 4. Aus der Abb. 5 kann man die Daten zur zweiten und vierten Ausrichtung $\mathbf {B}$ und $\mathbf {D}$ direkt ablesen; für die dritte Ausrichtung $\mathbf {C}$ ergeben sie sich durch Übergang zum 4. Iterationsschritt in der Abb. 5. Da die Abb. 5 anhand der Regeln des Abschnitts #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat erstellt ist, werden diese Regeln auch von der Abb. 6 (und von den Matrizen $X,Y,A$ (s. o.) und den Hypermatrizen $T,B$ (s. u.)) eingehalten. Die vier Graphiken unterscheiden sich hinsichtlich des Charakteristikums Ausrichtung durch eine der Isometrien aus der Gruppe $V$. Anmerkungen Die Abbildung zeigt bei jeder der vier Ausrichtungen nur einen einzigen Rekursionsschritt. Das Zusammenfassen mehrerer Rekursionsschritte zu einem Schritt, also das Verbreitern der Ein- und Ausgabe auf mehr als eine Ziffer (bei beiden, 4-adischem Parameter und 2-adischen Koordinaten), ist eine reine Fleißaufgabe und vergrößert die Graphiken wie die von ihnen abgeleiteten Matrizen entsprechend. Es bleibt aber bei der Anzahl vier hinsichtlich der Übersetzungstabellen, die der Anzahl der Ausrichtungen und der Gruppenordnung der Gruppe $V$ entspricht. Das Verfahren bezeichnet M. Bader als recursion unrolling (dt. etwa Ab/Entrollen der Schleife). Es kann die Algorithmen wesentlich beschleunigen, weil weniger Schleifenkontrollanweisungen, Speicherzugriffe und/oder Programmaufrufe zu absolvieren sind. (Abgesehen davon können Bit-Shift-Operationen, die auf vielen Maschinen erforderlich wären, durch geschickte Wahl der Ziffernzahl eingespart werden.) Exemplarisch für 2 Iterationen: $X=\left\lbrack {\begin{matrix}\\\\\\\\\\\end{matrix}}\right.$ 00 01 01 00 00 00 01 01 10 10 11 11 11 10 10 11 $\left.{\begin{matrix}\\\\\\\\\\\end{matrix}}\right\rbrack$ ←   $\mathbf {A} \,=\,a$ 11 11 10 10 01 00 00 01 01 00 00 01 10 10 11 11 ←   $\mathbf {B} \,=\,a$ 11 10 10 11 11 11 10 10 01 01 00 00 00 01 01 00 ←   $\mathbf {C} \,=\,a$ 00 00 01 01 10 11 11 10 10 11 11 10 01 01 00 002 ←   $\mathbf {D} \,=\,a$ $Y=\left\lbrack {\begin{matrix}\\\\\\\\\\\end{matrix}}\right.$ 00 00 01 01 10 11 11 10 10 11 11 10 01 01 00 00 $\left.{\begin{matrix}\\\\\\\\\\\end{matrix}}\right\rbrack$ ←   $\mathbf {A} \,=\,a$ 11 10 10 11 11 11 10 10 01 01 00 00 00 01 01 00 ←   $\mathbf {B} \,=\,a$ 11 11 10 10 01 00 00 01 01 00 00 01 10 10 11 11 ←   $\mathbf {C} \,=\,a$ 00 01 01 00 00 00 01 01 10 10 11 11 11 10 10 112 ←   $\mathbf {D} \,=\,a$ $A=\left\lbrack {\begin{matrix}\\\\\\\\\\\end{matrix}}\right.$ $\mathbf {A}$ $\mathbf {D}$ $\mathbf {D}$ $\mathbf {C}$ $\mathbf {D}$ $\mathbf {A}$ $\mathbf {A}$ $\mathbf {B}$ $\mathbf {D}$ $\mathbf {A}$ $\mathbf {A}$ $\mathbf {B}$ $\mathbf {C}$ $\mathbf {B}$ $\mathbf {B}$ $\mathbf {A}$ $\left.{\begin{matrix}\\\\\\\\\\\end{matrix}}\right\rbrack$ ←   $\mathbf {A} \,=\,a$ $\mathbf {B}$ $\mathbf {C}$ $\mathbf {C}$ $\mathbf {D}$ $\mathbf {C}$ $\mathbf {B}$ $\mathbf {B}$ $\mathbf {A}$ $\mathbf {C}$ $\mathbf {B}$ $\mathbf {B}$ $\mathbf {A}$ $\mathbf {D}$ $\mathbf {A}$ $\mathbf {A}$ $\mathbf {B}$ ←   $\mathbf {B} \,=\,a$ $\mathbf {C}$ $\mathbf {B}$ $\mathbf {B}$ $\mathbf {A}$ $\mathbf {B}$ $\mathbf {C}$ $\mathbf {C}$ $\mathbf {D}$ $\mathbf {B}$ $\mathbf {C}$ $\mathbf {C}$ $\mathbf {D}$ $\mathbf {A}$ $\mathbf {D}$ $\mathbf {D}$ $\mathbf {C}$ ←   $\mathbf {C} \,=\,a$ $\mathbf {D}$ $\mathbf {A}$ $\mathbf {A}$ $\mathbf {B}$ $\mathbf {A}$ $\mathbf {D}$ $\mathbf {D}$ $\mathbf {C}$ $\mathbf {A}$ $\mathbf {D}$ $\mathbf {D}$ $\mathbf {C}$ $\mathbf {B}$ $\mathbf {C}$ $\mathbf {C}$ $\mathbf {D}$ ←   $\mathbf {D} \,=\,a$ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 00 01 02 03 10 11 12 13 20 21 22 23 30 31 32 334 ←   $\tau$ Die Abbildung 7 ist eine leichte Abwandlung der Fig. 4.1 aus J. Lawder. Sie zeigt im Wesentlichen dieselbe Information wie die Abbildung 6 – in der Art eines Zustandsübergangsdiagramms, bei dem der Übergang in die nächste Iterationsstufe (zum nächsten Viertelquadrat) als »Zustandsänderung« aufgefasst wird. Zum besseren Rechnen werden die Ausrichtungen als Restklassen $[1],[3],[5],[7]\in \mathbb {Z} /8\mathbb {Z}$ modulo 8 geschrieben, und zwar $\mathbf {A} :=[1],\,\mathbf {B} :=[3],\,\mathbf {C} :=[5],\,\mathbf {D} :=[7].$ Nur die primen Restklassen $\in (\mathbb {Z} /8\mathbb {Z} )^{\times }$ kommen als Ausrichtung vor. Zum Rechnen werden auch hier beide Verknüpfungen $\times$ sowie $+$ des Rings $\mathbb {Z} /8\mathbb {Z}$ gebraucht. Die Gruppe $V$ lässt sich als Matrizengruppe mit $v_{1}:=\left[{\begin{smallmatrix}{\begin{array}{rr}1&0\\0&1\end{array}}\end{smallmatrix}}\right]$ als Identität $[1]\!\to \![1],\;[3]\!\to \![3],\;[5]\!\to \![5],\;[7]\!\to \![7]$ ($\cong \;\times [1]$), $v_{5}:=\left[{\begin{smallmatrix}{\begin{array}{rr}-1&0\\0&-1\end{array}}\end{smallmatrix}}\right]$ als Punktspiegelung $[1]\!\to \![5],\;[3]\!\to \![7],\;[5]\!\to \![1],\;[7]\!\to \![3]$ ($\cong \;\times [5]$), $v_{7}:=\left[{\begin{smallmatrix}{\begin{array}{rr}0&1\\1&0\end{array}}\end{smallmatrix}}\right]$ als Spiegelung an der Hauptdiagonalen $[1]\!\to \![7],\;[3]\!\to \![5],\;[5]\!\to \![3],\;[7]\!\to \![1]$ ($\cong \;\times [7]$) und $v_{3}:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}0&-1\\-1&0\end{array}}\end{smallmatrix}}\right]$ als Spiegelung an der Nebendiagonalen $[1]\!\to \![3],\;[3]\!\to \![1],\;[5]\!\to \![7],\;[7]\!\to \![5]$ ($\cong \;\times [3]$) schreiben. Rechts vom $\cong$-Zeichen ist die Multiplikation mit einer primen Restklasse aufgeführt, die offensichtlich ein Ergebnis liefert, das der Anwendung der Matrix gemäß (Ausr) auf die Ausrichtung entspricht. Ferner ergibt sich $A=\left\lbrack {\begin{matrix}\\\\\\\\\\\end{matrix}}\right.$ $[7]$ $[1]$ $[1]$ $[3]$ $\left.{\begin{matrix}\\\\\\\\\\\end{matrix}}\right\rbrack$ $\leftarrow \,\,[1]\,=\,\mathbf {A} \,=\,a$ $[5]$ $[3]$ $[3]$ $[1]$ $\leftarrow \,\,[3]\,=\,\mathbf {B} \,=\,a$ $[3]$ $[5]$ $[5]$ $[7]$ $\leftarrow \,\,[5]\,=\,\mathbf {C} \,=\,a$ $[1]$ $[7]$ $[7]$ $[5]$ $\leftarrow \,\,[7]\,=\,\mathbf {D} \,=\,a$ $\uparrow$ $\uparrow$ $\uparrow$ $\uparrow$ $0$ $1$ $2$ $3$ $\leftarrow \,\tau$ als neues Erscheinungsbild der Matrix $A$. Die (Gl. RFh_a) ist dann gleichbedeutend mit der Formel $a_{n}(t)=A_{a_{n-1}(t),\,\tau _{n}}=\left\lbrace {\begin{matrix}\\\\\\\\\end{matrix}}\right.$ $-a_{n-1}(t)$   für   $\tau _{n}=0$ $a_{n-1}(t)$   für   $\tau _{n}=1$ $a_{n-1}(t)$   für   $\tau _{n}=2$ $[3]\times a_{n-1}(t)$   für   $\tau _{n}=3$ was bedeutet, dass die Ausrichtung $a_{n}(t)$ des dem Parameter $t=0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{n}\dotso$ in der $n$-ten Iteration zugeordneten Quadrates nur von der Ausrichtung $a_{n-1}$ und von der Quaternärziffer $\tau _{n}$ abhängt, und dass es keine weitere, insbesondere keine umgekehrte Abhängigkeit gibt, also dass $a_{n-1}$ von $a_{n}$ abhinge, wie man aus der Herleitung in Abschnitt #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat schließen könnte. Anhand der neuen Darstellung der Matrix $A$ verifiziert man leicht, dass $A_{a,\tau }+A_{[2]-a,\,3-\tau }=[2]$ (Sym1) für $a\in (\mathbb {Z} /8\mathbb {Z} )^{\times }$ und $\tau \in \{0,1,2,3\}$ gilt. Daraus folgt für $t=:0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{n}$ und $s:=0_{4}.\!\sigma _{1}\sigma _{2}\dotso \sigma _{n}$ mit $\sigma _{i}:=3-\tau _{i}$: $a_{n}(t)+a_{n}(s)=[2]$ (Sym2). Denn der Induktionsanfang ist $a_{0}(t)=[1]$ und $a_{0}(s)=[1]$. Ferner ist nach der Induktionsannahme $a_{n-1}(t)+a_{n-1}(s)=[2]$ und nach (Sym1) $a_{n}(t)+a_{n}(s)=A_{a_{n-1}(t),\,\tau _{n}}+A_{a_{n-1}(s),\,\sigma _{n}}=A_{a_{n-1}(t),\,\tau _{n}}+A_{[2]-a_{n-1}(t),\,3-\tau _{n}}=[2]$ . Aus (Sym2) und durch Inspektion der Matrix $X$ ergibt sich $X_{a_{n-1}(t),\,\tau _{n}}+X_{a_{n-1}(s),\,\sigma _{n}}=X_{a_{n-1}(t),\,\tau _{n}}+X_{[2]-a_{n-1}(t),\,3-\tau _{n}}=1$ und genauso bei $Y$ $Y_{a_{n-1}(t),\,\tau _{n}}\,-Y_{a_{n-1}(s),\,\sigma _{n}}\;=Y_{a_{n-1}(t),\,\tau _{n}}\,-Y_{[2]-a_{n-1}(t),\,3-\tau _{n}}\;=0$. Symmetrieeigenschaft: Für jedes $t\in {\mathcal {I}}$ ist $x(1-t)=1-x(t)$   und   $y(1-t)=y(t)$. Induktionsanfang: ${\dot {x}}_{0}(1-t)={\tfrac {1}{2}}=1-{\dot {x}}_{0}(t)$   und   ${\dot {y}}_{0}(1-t)={\tfrac {1}{2}}={\dot {y}}_{0}(t)$. Induktionsschritt: ${\begin{array}{lll}{\dot {x}}_{n}(1-t)&={\dot {x}}_{n-1}(1-t)&\quad +2^{-n-1}(2X_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&=1-{\dot {x}}_{n-1}(t)&\quad +2^{-n-1}(2X_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&=1-({\dot {x}}_{n}(t)&-2^{-n-1}(2X_{a_{n-1}(t),\,\tau _{n}}\!-1))\\&&\quad +2^{-n-1}(2X_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&=1-{\dot {x}}_{n}(t)&+2^{-n}(X_{a_{n-1}(t),\,\tau _{n}}+X_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&=1-{\dot {x}}_{n}(t)\end{array}}$ ${\begin{array}{lll}{\dot {y}}_{n}(1-t)&={\dot {y}}_{n-1}(1-t)&\quad +2^{-n-1}(2Y_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&={\dot {y}}_{n-1}(t)&\quad +2^{-n-1}(2Y_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&=({\dot {y}}_{n}(t)&-2^{-n-1}(2Y_{a_{n-1}(t),\,\tau _{n}}\!-1))\\&&\quad +2^{-n-1}(2Y_{a_{n-1}(s),\,\sigma _{n}}\!-1)\\&={\dot {y}}_{n}(t)&-2^{-n}(Y_{a_{n-1}(t),\,\tau _{n}}-Y_{a_{n-1}(s),\,\sigma _{n}})\\&={\dot {y}}_{n}(t)\end{array}}$

Hilbert-Index

Die Funktionen $h_{n}$ und ${\hat {h}}_{n}$ haben die Bildmenge ${\mathcal {I}}_{n}\times {\mathcal {I}}_{n}={\mathcal {I}}_{n}^{2}$, die eine diskrete Menge ist. Die Einschränkung ${\hat {h}}_{n}=h_{n}\!\mid _{{\mathcal {I}}_{2n}}$ hat die Umkehrfunktion

${\begin{array}{lllll}{\hat {k}}_{n}\;\colon &{\mathcal {I}}_{n}&\times &{\mathcal {I}}_{n}&\to &{\mathcal {I}}_{2n}\\&(x&,&y)&\mapsto &{\hat {k}}_{n}(x,y):={\hat {h}}_{n}^{-1}(x,y)\;,\\\end{array}}$

genannt Hilbert-Index. Sie hat ihrerseits die Bildmenge ${\mathcal {I}}_{2n}$. Unter den Einschränkungen auf die diskreten Mengen ${\mathcal {I}}_{2n}$ resp. ${\mathcal {I}}_{n}^{2}$ sind die Funktionen ${\hat {h}}_{n}$ wie ${\hat {k}}_{n}$ umkehrbar eindeutig und es gilt ${\hat {k}}_{n}\circ {\hat {h}}_{n}=\operatorname {id} _{{\mathcal {I}}_{2n}}$ und ${\hat {h}}_{n}\circ {\hat {k}}_{n}=\operatorname {id} _{{\mathcal {I}}_{n}^{2}}$.

Werden ihre Argumente $x_{n}:=0_{2}.\!\xi _{1}\xi _{2}\dotso \xi _{n}\in {\mathcal {I}}_{n}$ und $y_{n}:=0_{2}.\!\eta _{1}\eta _{2}\dotso \eta _{n}\in {\mathcal {I}}_{n}$ gleichermaßen als Binärbrüche entwickelt, dann kann man auch beliebige ($\infty$-stellige) Koordinaten $x=:0_{2}.\!\xi _{1}\xi _{2}\xi _{3}\dotso \in {\mathcal {I}}$ und $y=:0_{2}.\!\eta _{1}\eta _{2}\eta _{3}\dotso \in {\mathcal {I}}$ zulassen, in der zu definierenden Funktion $k_{n}$ als erstes die überschüssigen Stellen $\xi _{n+1}\xi _{n+2}\dotso$ und $\eta _{n+1}\eta _{n+2}\dotso$ abschneiden, sodann ${\hat {k}}_{n}$ ausführen, die Einschränkung auf die diskrete Menge ${\mathcal {I}}_{n}^{2}$ aufheben und somit das ganze Einheitsquadrat ${\mathcal {I}}^{2}={\mathcal {Q}}$ zur Definitionsmenge von

${\begin{array}{lllll}k_{n}\;\colon &{\mathcal {I}}&\times &{\mathcal {I}}&\to &{\mathcal {I}}\\&(x&,&y)&\mapsto &k_{n}(x,y)\;,\\\end{array}}$

erklären, so dass ${\hat {k}}_{n}=k_{n}\!\mid _{{\mathcal {I}}_{n}^{2}}$ der Funktion vom Eingang des Abschnitts entspricht.

Die Rückabwicklung der Transformationen $T_{0},T_{1},T_{2}$ und $T_{3}$ ist in den nachfolgenden Algorithmen ausgeführt.

Rekursiver Algorithmus

Die Auswertungsrichtung des Algorithmus xy2tR ist entgegen der Intervallschachtelung.

Eingabe:	Koordinaten $x,y\in {\mathcal {I}}$
Ausgabe:	Parameter $t\in {\mathcal {I}}$
Auswertungsrichtung:	fein zu grob

 function xy2tR(x, y, eps) begin
   if eps > 1 then
     return 0; // im Ergebnisintervall der linke Rand
   end if
   eps *= 2;
   if x < 1/2 then
     if y < 1/2 then
       return ( 0 + xy2tR(2*y, 2*x, eps) )/4;
     else
       return ( 1 + xy2tR(2*x, 2*y – 1, eps) )/4;
     end if
   else
     if y >= 1/2 then
       return ( 2 + xy2tR(2*x – 1, 2*y – 1, eps) )/4;
     else
       return ( 3 + xy2tR(1–eps – 2*y, 2–eps – 2*x, eps) )/4;
     end if
   end if
 end function

Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten

Auch diese Aufgabe lässt sich iterativ programmieren. Die iterative Funktion xy2tI arbeitet in Richtung Schachtelung, in der Binär- oder Quaternärdarstellung also von hochrangigen Ziffern zu niedrigrangigen, geometrisch von einem großen Quadrat zu einem der 4 Teilquadrate. Sie benutzt die bei t2xyI eingeführte Unterfunktion rot.

Ist $n$ die Nummer der Iteration, dann ist $p:=2^{n}$ die Anzahl der 1D-Teilintervalle.

Eingabe:	Koordinaten $x,y\in \{0,1,\dotso ,p-1\}$
Ausgabe:	Parameter $t\in \{0,1,\dotso ,p^{2}-1\}$
Auswertungsrichtung:	grob zu fein

 function xy2tI(x, y, p) begin
   t = 0; // Summationsanfang
   for (p /= 2; p >= 1; p /= 2) do
     rx = (x & p) > 0;
     ry = (y & p) > 0;
     t += p * p * ((3 * rx) ^ ry);
     (x, y) = rot(x, y, rx, ry, p);
   end for
   return t;
 end function

Abb. 7: Die Ausrichtung $\mathbf {A} ,\mathbf {B} ,\mathbf {C}$ od. $\mathbf {D}$ bestimmt den großen Kasten. Darin 4 kleine Kästen. In jedem stehen sich Quaternärziffer ${\color {green}\tau }$ des Parameters und Binärziffern ${\color {red}(\xi ,\eta )}$ der 2 Koordinaten gegenüber; eines ist Schlüssel, das andere Wert. Der Schlüssel, welcher zutrifft, bestimmt den kleinen Kasten, den Wert und die nächste Ausrichtung.
Die runden Pfeile verweisen auf den großen Kasten mit dieser Ausrichtung.

Rekursionsformel für den Hilbert-Index

Sind $x=:0_{2}.\!\xi _{1}\xi _{2}\xi _{3}\dotso \in {\mathcal {I}}$ und $y=:0_{2}.\!\eta _{1}\eta _{2}\eta _{3}\dotso \in {\mathcal {I}}$ Darstellungen der Koordinaten $(x,y)$ im Binärsystem, dann lässt sich die (unendliche) Folge ${\bigl (}k_{n}(x,y){\bigr )}_{n\in \mathbb {N} }$ auch als Rekursion mit dem Rekursionsanfang

$\tau _{0}(x,y)=0$	und
$b_{0}(x,y)=\mathbf {A}$	(Start mit der primären Ausrichtung $\mathbf {A}$)

und dem Rekursionsschritt

$\tau _{n}(x,y)$	$=T_{b_{n-1}(x,y),\,\xi _{n},\,\eta _{n}}$	(RFk_$\tau$)
$b_{n}(x,y)$	$=B_{b_{n-1}(x,y),\,\xi _{n},\,\eta _{n}}$	(RFk_b)

für $n\in \mathbb {N}$ schreiben. Die (4×2×2)-Hypermatrizen

$T:={\begin{bmatrix}\left[{\begin{smallmatrix}{\begin{array}{rr}0&1\\3&2\end{array}}\end{smallmatrix}}\right]\\\left[{\begin{smallmatrix}{\begin{array}{rr}2&1\\3&0\end{array}}\end{smallmatrix}}\right]\\\left[{\begin{smallmatrix}{\begin{array}{rr}2&3\\1&0\end{array}}\end{smallmatrix}}\right]\\\left[{\begin{smallmatrix}{\begin{array}{rr}0&3\\1&2\end{array}}\end{smallmatrix}}\right]\end{bmatrix}},\;\,B:={\begin{bmatrix}\left[{\begin{smallmatrix}{\begin{array}{rr}\mathbf {D} &\mathbf {A} \\\mathbf {B} &\mathbf {A} \end{array}}\end{smallmatrix}}\right]\\\left[{\begin{smallmatrix}{\begin{array}{rr}\mathbf {B} &\mathbf {B} \\\mathbf {A} &\mathbf {C} \end{array}}\end{smallmatrix}}\right]\\\left[{\begin{smallmatrix}{\begin{array}{rr}\mathbf {C} &\mathbf {D} \\\mathbf {C} &\mathbf {B} \end{array}}\end{smallmatrix}}\right]\\\left[{\begin{smallmatrix}{\begin{array}{rr}\mathbf {A} &\mathbf {C} \\\mathbf {D} &\mathbf {D} \end{array}}\end{smallmatrix}}\right]\end{bmatrix}}\quad {\begin{matrix}{\begin{smallmatrix}{\begin{array}{rr}\leftarrow &\mathbf {A} \\\,\end{array}}\end{smallmatrix}}\\{\begin{smallmatrix}{\begin{array}{rr}\leftarrow &\mathbf {B} \\\,\end{array}}\end{smallmatrix}}\\{\begin{smallmatrix}{\begin{array}{rr}\leftarrow &\mathbf {C} \\\,\end{array}}\end{smallmatrix}}\\{\begin{smallmatrix}{\begin{array}{rr}\leftarrow &\mathbf {D} \\\,\end{array}}\end{smallmatrix}}\end{matrix}}$

sind zusammen genommen äquivalent zu den vier Übersetzungstabellen der Abbildung 6. Sie werden an erster Stelle, den Zeilen, durch die absolute Ausrichtung $b_{n-1}(x,y)\in \{\mathbf {A} ,\mathbf {B} ,\mathbf {C} ,\mathbf {D} \}$ indiziert. Das Ergebnis ist bei $T$ wie bei $B$ eine (2×2)-Untermatrix, die zusammen eine der Übersetzungstabellen darstellen. Jede wird ihrerseits durch das Binärziffernpaar $(\xi _{n},\eta _{n})$ indiziert. Daraus resultiert (Gl. RFk_$\tau$) die neue Quaternärziffer $\tau _{n}$ für den Parameter $t$ und (Gl. RFk_b) die neue absolute Ausrichtung $b_{n}(x,y)$.

Ist eine der Koordinaten $\in E_{2}=\mathbb {N} _{0}2^{-\mathbb {N} _{0}}\,\cap \;]0,1[$, dann lässt sich durch entsprechende Wahl ihrer Binärdarstellung steuern, ob der links- oder der rechtsseitige Limes genommen werden soll.

Beweis der Rekursionsformel für die Umkehrfunktion Hilbert-Index

Das kleine Quadrat (rechts in der Abb. 4) bekommt gemäß (Gl. RFk_$\tau$) im großen Quadrat eine Nummer $\tau :=\tau _{n}=T_{b_{n-1}(x,y),\,\xi _{n},\,\eta _{n}}$, die der (absoluten) Ausrichtung $b_{n-1}(x,y)$ des großen Quadrats sowie der Lage des kleinen Quadrats im großen Quadrat, nämlich den Ziffern $(\xi _{n},\eta _{n})$, entspricht. Erstere legt fest, welche der 4 Übersetzungstabellen in Abb. 6 anzuwenden ist, und letztere legen fest, ob das kleine Quadrat ins linke untere (bei $(\xi _{n},\eta _{n})=(0,0)$), ins linke obere (bei $(\xi _{n},\eta _{n})=(0,1)$) etc. Teilquadrat gehört, woraus die Ziffer $\tau _{n}:=\tau$ resultiert. Dies geschieht in Einklang mit den Transformationen $T_{0}$ bis $T_{3}$ aus dem Abschnitt #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat, denn die Gleichung (RFk_b), die die absolute Ausrichtung rekursiv festlegt, ist eine Akkumulation der relativen Ausrichtungen, die durch jene Transformationen bewirkt werden.

Analysis

Im Limes, also bei $n=\infty$, kommt – wie ein Blitz aus heiterem Himmel – ein neues Problem auf, nämlich der plötzliche Verlust der umkehrbaren Eindeutigkeit sowohl bei der 4- wie bei der 2-adischen Darstellung.

Hilbert-Kurve

Mit den Hilbert-Polygonen lässt sich zu jedem positiven Abstand $\varepsilon >0$ eine Iterationsstufe $n\in \mathbb {N}$ angeben, so dass es zu jedem Punkt $(x,y)\in {\mathcal {Q}}$ des Einheitsquadrats einen Punkt $(x_{n},y_{n})$ des Rasters $R_{n}$ gibt, der geringeren Abstand ${\bigl |}(x_{n},y_{n})-(x,y){\bigr |}<\varepsilon$ hat. Das reicht aber nicht für eine vollständige Füllung des Quadrats. Diese kann nur durch einen Übergang zum Limes $\textstyle \lim _{n\to \infty }H_{n}$ erreicht werden. Der Limes

${\begin{array}{lllll}h\;\colon &{\mathcal {I}}&\to &{\mathcal {Q}}=&{\mathcal {I}}&\times &{\mathcal {I}}\\&t&\mapsto &\displaystyle \lim _{n\to \infty }h_{n}(t):=\lim _{n\to \infty }&{\bigl (}x_{n}(t)&,&y_{n}(t){\bigr )}&=:\;\;{\bigl (}x(t),y(t){\bigr )}\\\end{array}}$

existiert immerhin, da er aus der 2D-Intervallschachtelung

${\Bigl (}{\bigl [}x_{n}(t),x_{n}(t)+2^{-n}{\bigr ]}\times {\bigl [}y_{n}(t),y_{n}(t)+2^{-n}{\bigr ]}{\Bigr )}_{n\in \mathbb {N} }$

hervorgeht. Die Konvergenz ist eine gleichmäßige im folgenden Sinn: Für jedes $\varepsilon >0$ ist $N:={\bigl \lceil }\!-\!\log _{2}(\varepsilon ){\bigr \rceil }$ so, dass für alle Parameter $t\in {\mathcal {I}}$ und alle $n\in \mathbb {N}$ mit $n>N$

${\Bigl |}{\bigl (}x_{n}(t),y_{n}(t){\bigr )}-{\bigl (}x(t),y(t){\bigr )}{\Bigr |}\leq 2^{-n}<\varepsilon$

gilt.

Eigenschaften

1. $h$ ist rechtseindeutig, somit wohldefiniert und eine Funktion.
2. $h\,\colon \,{\mathcal {I}}\to {\mathcal {Q}}$ ist surjektiv.
3. $h$ ist nicht injektiv.
4. $h$ ist stetig, definiert also eine Kurve. Die Stetigkeit ist eine gleichmäßige.
5. Ist $\mathbf {A}$ die primäre Ausrichtung, dann ist $h$ symmetrisch zur Geraden $x={\tfrac {1}{2}}$:
         Für jedes $t\in {\mathcal {I}}$ ist $x(1-t)=1-x(t)$   und   $y(1-t)=y(t)$.
   Bei $\mathbf {D}$ als primärer Ausrichtung wäre es die Gerade $y={\tfrac {1}{2}}$
         und $x(1-t)=x(t)$   und   $y(1-t)=1-y(t)$.
6. Ist $h(t)=(x,y)$, dann ist
         $h{\Bigl (}{\frac {t}{4}}{\Bigr )}={\Bigl (}{\frac {y}{2}},{\frac {x}{2}}{\Bigr )}$.
7. Ist $t=:p/q=0_{4}.\!\tau _{1}\tau _{2}\tau _{3}\dotso \in \mathbb {Q}$ ein gekürzter Bruch mit der 4-adischen Periodenlänge $l$, also $q\mid (4^{l}-1)$, dann sind die Koordinaten $(x,y)$ von $h(t)\in \mathbb {Q} ^{2}$ beide rational mit einer 2-adischen Periodenlänge $\leq vl$, also $x\cdot (2^{vl}-1)\in \mathbb {Z} \ni y\cdot (2^{vl}-1)$ mit $v=4$ als der Gruppenordnung der Gruppe $V$.
8. $h$ ist nirgends differenzierbar.
9. $h$ ist Maß-erhaltend: Für jede Punktmenge $S\subset {\mathcal {I}}$ mit ein-dimensionalem Lebesgue-Maß $\mu$ hat das Bild $\cup _{t\in S}h(t)$ das $d$-dimensionale Lebesgue-Maß $\mu$.

Beweise der Eigenschaften

Zu Eigsch. 1:   $h$ ist Funktion. In der Tat ist $h$ nicht von vorne herein wohldefiniert, weil beim Übergang von einer reellen Zahl zu ihrer Quaternärentwicklung eine Weggabelung existiert: Zu einem gekürzten Bruch mit Viererpotenz im Nenner, also zu einem Element $t\in E_{4}:=\mathbb {N} _{0}4^{-\mathbb {N} _{0}}\,\cap \;]0,1[$, gibt es zwei Möglichkeiten der Darstellung. Beispielsweise hat der Bruch $t={\tfrac {1}{4}}$ die Darstellung mit einem Periode-04-Ende ${\tfrac {1}{4}}=\displaystyle 1\cdot 4^{-1}+\sum _{i=2}^{\infty }0\cdot 4^{-i}=0_{4}.1{\overline {0}}$ (die als die »abbrechende Darstellung« bezeichnet wird) und die mit einem 34-Ende ${\tfrac {1}{4}}=\displaystyle 0\cdot 4^{-1}+\sum _{i=2}^{\infty }3\cdot 4^{-i}=0_{4}.0{\overline {3}}$ . Diese Wahlmöglichkeit (Gleichheit) ist bei endlicher Stellenzahl nicht gegeben, im Limes $\textstyle \lim _{n\to \infty }$ aber sehr wohl, wo sie die für die Funktion erforderliche Rechtseindeutigkeit von $h$ gefährdet. Es kann aber gezeigt werden, dass sie sich auf das Ergebnis von $h$ nicht auswirkt. Wegen $h(0_{4}.\!{\overline {0}})=(0,0)$ muss gelten:       $\lim _{n\to \infty }T_{0}^{n}(0,0)=(0,0)=T_{0}(0,0)$. In der Tat ist ${\bigl (}T_{0}^{n}({\mathcal {Q}}){\bigr )}_{n\in \mathbb {N} }$ wegen $T_{0}({\mathcal {Q}})=T_{0}({\mathcal {I}}^{2})=({\mathcal {I}}/2)^{2}$ eine 2D-Intervallschachtelung mit dem für alle $(x,y)\in {\mathcal {Q}}$ existierenden Limes $\textstyle \lim _{n\to \infty }T_{0}^{n}(x,y)=(0,0)$. Für $\tau \in \{1,2,3\}$ muss wegen $0_{4}.\!{\bar {\tau }}{\overline {3}}=0_{4}.\!\tau {\overline {0}}$ (mit ${\bar {\tau }}$ als der Ziffer für $\tau -1$) gelten:       $T_{\tau -1}\circ \lim _{n\to \infty }T_{3}^{n}(1,0)=T_{\tau -1}(1,0)=T_{\tau }(0,0)$, damit $h(0_{4}.\!{\bar {\tau }}{\overline {3}})=h(0_{4}.\!\tau {\overline {0}})$ sein kann. In der Tat ist ${\bigl (}T_{3}^{n}({\mathcal {Q}}){\bigr )}_{n\in \mathbb {N} }$ wegen $T_{3}({\mathcal {Q}})=T_{3}({\mathcal {I}}^{2})={\bigl (}{\tfrac {1}{2}},0{\bigr )}+({\mathcal {I}}/2)^{2}$ eine 2D-Intervallschachtelung mit dem für alle $(x,y)\in {\mathcal {Q}}$ existierenden Limes $\textstyle \lim _{n\to \infty }T_{3}^{n}(x,y)=(1,0)$. Ferner ist $T_{0}\circ (1,0)={\bigl (}0,{\tfrac {1}{2}}{\bigr )}$ $=T_{1}(0,0)$ , $T_{1}\circ (1,0)={\bigl (}{\tfrac {1}{2}},{\tfrac {1}{2}}{\bigr )}$ $=T_{2}(0,0)$ und $T_{2}\circ (1,0)={\bigl (}1,{\tfrac {1}{2}}{\bigr )}$ $=T_{3}(0,0)$. Zu Eigsch. 2:   $h$ ist surjektiv. Zu einem Punkt $(x,y)\in {\mathcal {Q}}$ gibt es zwei 1D-Intervallschachtelungen $x_{n}:=0_{2}.\!\xi _{1}\xi _{2}\dotso \xi _{n}\to x$ und $y_{n}:=0_{2}.\!\eta _{1}\eta _{2}\dotso \eta _{n}\to y$. Für die Hilbert-Indizes $t_{n}:={\hat {k}}_{n}(x_{n},y_{n})$   gilt   ${\hat {h}}_{n}(t_{n})=(x_{n},y_{n})$, so dass ${\big (}t_{n}{\bigr )}_{n\in \mathbb {N} }$ eine 1D-Intervallschachtelung für einen Parameter $\lim _{n\to \infty }t_{n}=:t$ ist. Für diesen gilt ${\begin{array}{ll}h(t)&=h(\lim _{n\to \infty }t_{n})\\&=\lim _{n\to \infty }h(t_{n})\\&=\lim _{n\to \infty }{\hat {h}}_{n}(t_{n})\\&=\lim _{n\to \infty }(x_{n},y_{n})\\&=(x,y).\end{array}}$ Zu Eigsch. 3:   Dennoch ist $h$ nicht injektiv. ($h$ kann als surjektive und stetige (s. u.) Funktion von 1D nach 2D nach dem Satz von der Invarianz der Dimension nicht injektiv sein.) Die oben gebildeten 1D-Intervallschachtelungen sind genau dann mehrdeutig, wenn eine der beiden Koordinaten in $E_{2}=\mathbb {N} _{0}2^{-\mathbb {N} _{0}}\,\cap \;]0,1[$ liegt. Beispielsweise ist $h({\tfrac {1}{12}})=h({\tfrac {11}{12}})=(0,{\tfrac {1}{2}})$, $h({\tfrac {1}{2}})=h({\tfrac {1}{6}})=h({\tfrac {5}{6}})=({\tfrac {1}{2}},{\tfrac {1}{2}})$ (Ein Tripelpunkt) und $h({\tfrac {5}{48}})=h({\tfrac {7}{48}})=h({\tfrac {41}{48}})=h({\tfrac {43}{48}})=({\tfrac {1}{2}},{\tfrac {1}{4}})$ (Ein Quadrupelpunkt !) Jedes Teilquadrat enthält einen Quadrupelpunkt und damit abzählbar unendlich viele. Zu einem Punkt $(x,y)\in {\mathcal {Q}}$ gibt es maximal vier Parameterwerte $t\in {\mathcal {I}}$ mit $h(t)=(x,y)$. Zu Bildpunkten $(x,y)\in F_{2}:=({\mathcal {I}}\setminus E_{2})^{2}={\mathcal {Q}}\setminus {\bigl (}(E_{2}\times {\mathcal {I}})\cup ({\mathcal {I}}\times E_{2}){\bigr )}$ gibt es nur ein Urbild. Zu Eigsch. 4:   $h$ ist stetig. $h$ ist sogar Hölder-stetig (was die gleichmäßige Stetigkeit einschließt), und zwar zum Exponenten $d^{-1}$ mit $d$ als der Dimension des Zielraums $\mathbb {R} ^{d}$. $h$ bildet zwei benachbarte Intervalle stets auf zwei benachbarte Quadrate (mit gemeinsamer Seite) ab. Und da alle Quadrate späterer Iterationen den früheren treu bleiben (s. Abb. 4), folgt die gleichmäßige Stetigkeit. Zu Eigsch. 5:   $x(1-t)=1-x(t)$   und   $y(1-t)=y(t)$. Schon für alle $n\in \mathbb {N} ,t\in {\mathcal {I}}$ gilt aus Symmetriegründen ${\dot {x}}_{n}(1-t)=1-{\dot {x}}_{n}(t)$; genauso ${\dot {y}}_{n}(1-t)={\dot {y}}_{n}(t)$. (S. a. den Beweis für denselben Sachverhalt im Abschnitt #Explizite Rekursionsformel.) Die Eigsch. 6:   $h{\Bigl (}{\frac {t}{4}}{\Bigr )}={\Bigl (}{\frac {y}{2}},{\frac {x}{2}}{\Bigr )}$ ist eine direkte Folge der Transformation $T_{0}$. Iteriert ergibt sich $h{\Bigl (}{\frac {t}{16}}{\Bigr )}={\frac {h(t)}{4}}$. Zu Eigsch. 7:   $h({\mathcal {I}}\cap \mathbb {Q} )\subset \mathbb {Q}$. (Ist $p:=0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{l}$ eine 4-adische Periode der Länge $l$, dann ist $p\cdot (4^{l}-1)$ eine ganze Zahl.) Nach der expliziten Rekursionsformel hängt ein neues Ziffernpaar $\xi _{n},\eta _{n}$ nur von $a_{n-1},\tau _{n}$ ab. Wegen $\left\vert \{\mathbf {A} ,\mathbf {B} ,\mathbf {C} ,\mathbf {D} \}\right\vert =\left\vert V\right\vert =4$ gibt es von diesen Konstellationen $(a_{n-1},\tau _{n})\in \{\mathbf {A} ,\mathbf {B} ,\mathbf {C} ,\mathbf {D} \}\times \{\!\tau _{1},\tau _{2},\dotso ,\tau _{l}\}$ maximal $4\cdot l$   Stück, so dass sie wiederkehren müssen. Kehrt eine Konstellation (ihre Nummer sei $n$) zum ersten Mal (etwa bei der Nummer $\nu$) wieder, liegt eine schon mal dagewesene Ursache $(a_{n-1},\tau _{n})$ vor, so dass sich die Wirkungen, die Ziffern $\xi _{n}$ und $\eta _{n}$, wiederholen müssen, nämlich alle $\nu -n$ mal, und $\nu -n$ ist ein Teiler von $4l$. Daraus folgt für geeignetes $\mu \in \mathbb {N} _{0}$ sowohl $x\cdot (2^{4l}-1)\cdot 2^{\mu }\in \mathbb {Z}$ wie $y\cdot (2^{4l}-1)\cdot 2^{\mu }\in \mathbb {Z}$, also $(x,y)\in \mathbb {Q} ^{2}$. Der folgende Pseudocode t2xyQ nimmt den ganzzahligen Zähler und Nenner tn,td eines rationalen Parameters $t=$tn/td und produziert die ganzzahligen Zähler und Nenner xn,xd,yn,yd der 2 Koordinaten $(x,y)=$(xn/xd,yn/yd)$:=h($tn/td$)$. Die Wiederholung (s. o.) einer Konstellation (a,tn) und damit die Periodenlänge wird mittels des assoziativen Datenfeldes occurs festgestellt. Die Datenfelder X, Y und A beziehen sich auf die obigen Matrizen $X,Y$ und $A$. Der Doppelstern ** ist das Zeichen für Potenzierung. function t2xyQ(tn,td) begin // 0 ≤ tn ≤ td > 0 pos = 0; xp = 0; yp = 0; a = 0; // primäre Ausrichtung key = a+tn*4; // die Konstellation (a,tn) als Schlüssel while not defined(occurs[key]) do occurs[key] = pos; // die Nummer der Stelle mit (a,tn) ti = floor(tn*4/td); // Quaternärziffer ti: 0 ≤ ti ≤ 4 if ti > 3 then ti = 3; end if tn = tn*4 – ti*td; // 0 ≤ tn ≤ td xp = xp*2 + X[a,ti]; // obige Matrix X yp = yp*2 + Y[a,ti]; // obige Matrix Y a = A[a,ti]; // obige Matrix A key = a+tn*4; pos += 1; end while pl = pos–occurs[key]; // Vielfaches der 2-adischen Periodenlänge pot = 2**pl; per = pot–1; xd = per * 2**(pos–pl); // Nenner von x und y xn = xp div pot; // Vorperiode von x xp = xp–xn*pot; // Periode von x xn = xn*per+xp; // Zähler von x yn = yp div pot; // Vorperiode von y yp = yp–yn*pot; // Periode von y yn = yn*per+yp; // Zähler von y return (xn,xd, yn,xd); end function

Einige Zahlenbeispiele

Parameter $t$

$0$

${\tfrac {1}{3}}$

${\tfrac {2}{3}}$

$1$

${\tfrac {2}{5}}$

${\tfrac {1}{4}}$

${\tfrac {1}{5}}$

${\tfrac {1}{7}}$

${\tfrac {1}{9}}$

${\tfrac {1}{11}}$

${\tfrac {1}{13}}$

${\tfrac {1}{17}}$

${\tfrac {1}{19}}$

$h(t)$

$x(t)$

$0$

$0$

$1$

$1$

${\tfrac {1}{3}}$

$0$

${\tfrac {1}{5}}$

${\tfrac {26}{63}}$

${\tfrac {1}{3}}$

${\tfrac {14}{33}}$

${\tfrac {1}{3}}$

${\tfrac {1}{5}}$

${\tfrac {76}{511}}$

$y(t)$

$0$

$1$

$1$

$0$

$1$

${\tfrac {1}{2}}$

${\tfrac {2}{5}}$

${\tfrac {19}{63}}$

${\tfrac {2}{9}}$

${\tfrac {1}{11}}$

$0$

$0$

${\tfrac {55}{511}}$

Mehrfachpunkte

Parameter $t$

${\tfrac {1}{12}}$

${\tfrac {11}{12}}$

${\tfrac {1}{10}}$

${\tfrac {9}{10}}$

${\tfrac {3}{20}}$

${\tfrac {17}{20}}$

${\tfrac {1}{8}}$

${\tfrac {1}{24}}$

${\tfrac {5}{24}}$

${\tfrac {1}{2}}$

${\tfrac {1}{6}}$

${\tfrac {5}{6}}$

${\tfrac {5}{48}}$

${\tfrac {7}{48}}$

${\tfrac {41}{48}}$

${\tfrac {43}{48}}$

$h(t)$

$x(t)$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

$y(t)$

$0$

$0$

${\tfrac {1}{6}}$

${\tfrac {1}{6}}$

${\tfrac {1}{3}}$

${\tfrac {1}{3}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{2}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

${\tfrac {1}{4}}$

Umkehrfunktion

Erstens ist festzuhalten, dass $h$ wegen der fehlenden Injektivität nicht umkehrbar ist.

Obwohl die Einschränkung ${\hat {h}}_{n}=h_{n}\!\!\mid _{{\mathcal {I}}_{2n}}\!(t)$ für jedes $n\in \mathbb {N}$ mit dem Ergebnis ${\hat {k}}_{n}=k_{n}\!\mid _{{\mathcal {I}}_{n}^{2}}$ invertierbar ist, existiert zweitens der Limes

${\begin{array}{lllll}k\;\colon &[0,1]&\times &[0,1]&\to &[0,1]\\&(x&,&y)&\mapsto &\displaystyle \lim _{n\to \infty }k_{n}(x,y)\\\end{array}}$

nicht, wenn eine der beiden Koordinaten $x$ oder $y$ eine abbrechende Binärdarstellung hat, also in

$E_{2}:=\mathbb {N} _{0}2^{-\mathbb {N} _{0}}\,\cap \;]0,1[$

liegt. Nach der im Beweis der Nicht-Injektivität von $h$ gemachten Bemerkung sind dies dieselben Stellen, zu denen es mehr als ein Urbild gibt.

$k$ kann auch an diesen Stellen eindeutig gemacht werden durch die Vorschrift, dass die betreffende(n) Koordinate(n) $x$ oder/und $y$, wenn sie bei irgendeinem Rekursionsschritt genau auf die Mitte eines Intervalls fallen, stets

• der rechten (oberen) Intervallhälfte zugeschlagen werden (Vorschrift „+“, und damit als 0₂-Ende behandelt werden) oder
• der linken (unteren) Intervallhälfte (Vorschrift „–“, und somit als 1₂-Ende).

Da $h$ stetig ist, erfüllen die so konstruierten Urbilder $t$ die Beziehung $h(t)=(x,y)$. Es gibt somit (mindestens) vier verschiedene Funktionen

1. $k_{++}(x,y):=\lim _{n\to \infty ,\,\xi \searrow x,\,\eta \searrow y}\;k_{n}(\xi ,\eta )$ ,
2. $k_{+-}(x,y):=\lim _{n\to \infty ,\,\xi \searrow x,\,\eta \nearrow y}\;k_{n}(\xi ,\eta )$ ,
3. $k_{-+}(x,y):=\lim _{n\to \infty ,\,\xi \nearrow x,\,\eta \searrow y}\;k_{n}(\xi ,\eta )$ und
4. $k_{--}(x,y):=\lim _{n\to \infty ,\,\xi \nearrow x,\,\eta \nearrow y}\;k_{n}(\xi ,\eta )$ ,

die sich an den Stellen unterscheiden, an denen eine der beiden Koordinaten in $E_{2}$ liegt. An diesen Stellen sind die Funktionen $k_{\pm \pm }$ auch nicht stetig.

Eine solche Funktion $k_{\pm \pm }$ wird als Rechtsinverse (auch „Koretraktion“) von $h$ bezeichnet. Sie erfüllt die Beziehung

$h\circ k_{\pm \pm }=\operatorname {id} _{\mathcal {Q}}$ ,

die gleichbedeutend ist mit der Implikation

$k_{\pm \pm }(x,y)=t\;\Longrightarrow \;h(t)=(x,y)$ .

Eigenschaften

1. Alle $k_{++},k_{+-},k_{-+},k_{--}$ sind Funktionen.
2. Die Lösungsmenge ${\bigl \{}t\in {\mathcal {I}}\mid h(t)=(x,y){\bigr \}}$ zu einem Punkt $(x,y)\in {\mathcal {Q}}$ ist
         ${\bigl \{}k_{++}(x,y),\;k_{+-}(x,y),\;k_{-+}(x,y),\;k_{--}(x,y){\bigr \}}$.
   Ihre Elementeanzahl ist zwischen 1 und 4.
3. Alle Funktionen $k_{++},k_{+-},k_{-+},k_{--}$ sind injektiv.
4. Eingeschränkt auf $F_{2}=({\mathcal {I}}\setminus E_{2})^{2}$ ist $k$ eindeutig, also
         $k_{++}(x,y)=k_{+-}(x,y)=k_{-+}(x,y)=k_{--}(x,y)$ für $(x,y)\in F_{2}.$
5. Keine Funktion $k_{++},k_{+-},k_{-+},k_{--}$ ist stetig.
6. Keine Funktion $k_{++},k_{+-},k_{-+},k_{--}$ ist surjektiv.
7. Sind die Koordinaten $(x,y)$ rational mit den beziehentlichen binären Periodenlängen $l_{x},l_{y}$, dann ist
         $t:=k_{\pm \pm }(x,y)\in \mathbb {Q}$
   mit $t\cdot (4^{vl_{x}l_{y}}-1)\in \mathbb {Z}$ und $v=4$ als der Gruppenordnung der Gruppe $V$.

Beweise der Eigenschaften

Zu Eigsch. 1:   $k_{\pm \pm }$ ist eine Funktion. Der Limes der #Rekursionsformel für den Hilbert-Index definiert die Funktion $k_{++}$. Zu Eigsch. 2:   Zu $(x,y)\in Q$ gibt es maximal 4 Parameterwerte $t$ mit $h(t)=(x,y)$. S. Beweis von: $h$ ist nicht injektiv. Zu Eigsch. 3:   $k_{\pm \pm }$ ist injektiv. Eine Rechtsinverse ist injektiv. Zu Eigsch. 4:   Die Punkte $(x,y)\in F_{2}=({\mathcal {I}}\setminus E_{2})^{2}$ haben nur ein Urbild $h^{-1}{\bigl (}\{(x,y)\}{\bigr )}$. Zu Eigsch. 5:   $k_{\pm \pm }$ ist nicht stetig. An den Mehrfachpunkten unterscheiden sich mindestens 2 der Funktionen $k_{++},k_{+-},k_{-+},k_{--}$, d. h. linksseitiger oder/und rechtsseitiger Grenzwert. Also ist keine der Funktionen dort stetig. Zu Eigsch. 6:   Kein $k_{\pm \pm }$ ist surjektiv. Wie gezeigt, gibt es mehrere Rechtsinversen