Satz des arktischen Kreises

Der Satz des arktischen Kreises (englisch arctic circle theorem) ist ein Resultat aus der Stochastik und der Kombinatorik, der sagt, dass bei einer zufälligen Parkettierung großer aztekischer Diamanten durch Dominosteine, das Muster außerhalb einer Kreisregion gefriert. Die Parkettierung wird dabei unter der Gleichverteilung gezogen, der Kreis wird arktischer Kreis genannt und ist ein Phasenübergang. Das darunterliegende Gesetz gehört zu den sogenannten universellen Gesetzen der Stochastik.

Der Satz wurde 1995 von William Jockusch, James Propp und Peter Shor bewiesen.^[1] 2002 zeigt dann Kurt Johansson, dass die Fluktuation des Randes um den arktischen Kreis zum sogenannten Airy-Prozess konvergiert, welcher der Tracy-Widom-Verteilung des GUE aus der Theorie der zufälligen Matrizen folgt.^[2] Die Verteilung beschreibt dort das Verhalten des größten Eigenwerts. Die Parkettierung des aztekischen Diamanten mit Dominosteinen kann als zufälliges Wachstumsmodell (englisch random growth model) aufgefasst werden und gehört zur KPZ-Universalitätsklasse.

Zuerst müssen einige Begriffe wie Zelle, Dominostein, aztekischer Diamant und Dominostein-Parkettierung (auch Domino-Tiling oder Domino-Tessellation genannt) eingeführt werden. Für das Verständnis empfiehlt es sich die Grafiken zu betrachten.

Ein ganzzahliges Quadratgitter der Form ${\displaystyle [a,a+1]\times [b,b+1]\subseteq \mathbb {R} ^{2}}$ mit ${\displaystyle a,b\in \mathbb {Z} }$ nennt man Zelle, das sind also Quadrate in ${\displaystyle \mathbb {R} ^{2}}$ mit Ecken in ${\displaystyle \mathbb {Z} ^{2}}$. Beispielsweise hat die Zelle ${\displaystyle [2,3]\times [3,4]}$ die Eckpunkte ${\displaystyle \{(2,3),(3,3),(2,4),(3,4)\}}$. Die Vereinigung zweier nebeneinanderliegenden Zellen nennt man Dominostein, entweder horizontal als ${\displaystyle 2\times 1}$-Dominostein oder vertikal als ${\displaystyle 1\times 2}$-Dominostein.

Ein aztekischer Diamant ${\displaystyle A_{n}}$ der Ordnung ${\displaystyle n}$ besteht aus der Vereinigung aller Zellen ${\displaystyle [a,a+1]\times [b,b+1]}$, welche komplett in der Region ${\displaystyle \{(x,y)\in |x|+|y|\leq n+1\}}$ liegen. Dies sind exakt ${\displaystyle 2n(n+1)}$ Zellen und man kann den aztekischen Diamant auch als folgende Menge schreiben^[3]

${\displaystyle A_{n}=\bigcup \limits _{a=-n}^{n-1}\bigcup \limits _{b=\max(-n-a-1,\,-n+a)}^{\min(n+a,\,n-a-1)}[a,a+1]\times [b,b+1].}$

Eine Dominostein-Parkettierung des aztekischen Diamant entsteht, wenn man den aztekischen Diamant mit nicht überlappenden Dominos vollständig überdeckt (englisch tiling), dabei können sowohl ${\displaystyle 2\times 1}$ als auch ${\displaystyle 1\times 2}$-Steine verwendet werden.

• 
  Aztekische Diamanten der Ordnung ${\displaystyle 1}$, ${\displaystyle 2}$ und ${\displaystyle 3}$
• 
  Ein aztekischer Diamant der Ordnung ${\displaystyle n=4}$
• 
  Eine Domino-Parkettierung
• 
  Die vier Typen von Dominosteinen mit ihren Höhenfunktionen (rot). (W) = West, (E) = Ost, (S) = Süd, (N) = Nord

Statt mit nur ${\displaystyle 2}$ Typen von Dominosteinen zu arbeiten, werden wir eine weitere Struktur einführen, welche die Dominosteine in weitere Klassen unterteilt. Hierfür legt man ein Schachbrett über den aztekischen Diamanten, das heißt, die Zellen sind abwechselnd schwarz oder weiß. Dadurch erhält man ${\displaystyle 4}$ verschiedene Typen von Dominosteine, je nachdem, ob sie horizontal oder vertikal liegen und wo sich die schwarze respektive weiße Zelle befindet. Diese ${\displaystyle 4}$ Typen sind in der oben dargestellten Parkettierung mit ${\displaystyle 4}$ Farben dargestellt.

Horizontale Dominosteine werden als Nord-Dominosteine (N) bezeichnet, wenn deren linkes Quadrat weiß ist, und als Süd-Dominosteine (S), wenn deren linkes Quadrat schwarz ist. Vertikale Dominosteine werden als West-Dominosteine (W) bezeichnet, wenn deren oberes Quadrat weiß ist, und als Ost-Dominosteine (E), wenn deren oberes Quadrat schwarz ist.^[4] In der Grafik oben sind die Nordsteine gelb, die Südsteine blau, die Weststeine rot und die Oststeine grün.

Interessanterweise entstehen ${\displaystyle 4}$ Regionen in den Ecken des aztekischen Diamanten, welche jeweils nur aus einem Typ Dominostein bestehen, und welche durch einen inneren Kreis abgegrenzt sind. Dieser Kreis wird arktischer Kreis genannt und je größer die Ordnung ${\displaystyle n}$ ist, desto besser sieht man die Kreisform. Der arktische Kreis unterteilt den aztekischen Diamanten in zwei Regionen, die innere Region heißt gemäßigte Region und diejenige außerhalb des Kreises nennt man Polarregion, da dort in einer Ecke nur ein Typ von Dominostein vorkommt und die Steine „gefroren“ scheinen. Entsprechend nennt man die Polarregion, welche durch die Nord-Dominosteine gebildet wird, die Nordpolarregion und auf analoge Weise bezeichnet man die anderen ${\displaystyle 3}$ Polarregionen entsprechend der Steine, welche die Region bilden. Der innere Kreis von ${\displaystyle A_{n}}$ wird definiert als der innere Kreis in der Mitte von ${\displaystyle A_{n}}$, welcher den Radius ${\displaystyle n/{\sqrt {2}}}$ besitzt.

Die Menge der möglichen Domino-Parkettierungen von ${\displaystyle A_{n}}$ sei mit ${\displaystyle {\mathcal {T}}(A_{n})}$ notiert. Für die Anzahl gilt ${\displaystyle |{\mathcal {T}}(A_{n})|=2^{\binom {n+1}{2}}=2^{\frac {n(n+1)}{2}}}$.^[5] Für eine Parkettierung ${\displaystyle T\in {\mathcal {T}}(A_{n})}$ sei mit ${\displaystyle v(T)}$ die Anzahl vertikaler Dominosteine notiert.

Eine zufällige Parkettierung ${\displaystyle T}$ ist eine Parkettierung, die unter einer Wahrscheinlichkeitsverteilung gezogen wurde. Die Gleichverteilung ist durch die Wahrscheinlichkeitsfunktion ${\displaystyle P(T)={\tfrac {1}{|{\mathcal {T}}(A_{n})|}}}$ definiert und sei mit ${\displaystyle \operatorname {Uni} (A_{N})}$ notiert. Wir können ein Wahrscheinlichkeitsmaß auch mit Hilfe der Dominosteine konstruieren und geben hierfür den Dominosteinen ein Gewicht. Den horizontalen Dominosteinen wird jeweils das Gewicht ${\displaystyle 1}$ zugeteilt und den vertikalen Dominosteinen das Gewicht ${\displaystyle a}$. Dann kann man ein Maß wie folgt konstruieren:

${\displaystyle P(T)={\frac {a^{v(T)}}{\sum \limits _{T\in {\mathcal {T}}(A_{n})}a^{v(T)}}}.}$^[4]

Wenn man den vertikalen Dominosteinen das Gewicht ${\displaystyle a=1}$ zuteilt, dann erhält man wieder die Gleichverteilung. Um den arktischen Kreis zu erhalten, benötigt man ${\displaystyle a=1}$, ansonsten erhält man die arktische Ellipse.

Zu jedem Dominostein wird nun eine Höhenfunktionen eingeführt, das heißt eine Linie wird auf die Steine gezeichnet. Für die horizontale Dominostein seien zwei Ecken in ${\displaystyle (0,0)}$ und ${\displaystyle (1,2)}$. Dann zieht man für die West-Steine eine Linie von ${\displaystyle (0,1/2)}$ nach ${\displaystyle (1,3/2)}$ und für die Ost-Steine von ${\displaystyle (0,3/2)}$ nach ${\displaystyle (1,1/2)}$. Für die vertikalen Dominostein seien zwei Ecken in ${\displaystyle (0,0)}$ und ${\displaystyle (2,1)}$. Dann zieht man für die Süd-Steine eine Linie von ${\displaystyle (0,1/2)}$ nach ${\displaystyle (2,1/2)}$ und für den Nordstein zieht man keine Linie. Die Höhenfunktionen sind in der Grafik oben in rot ersichtlich. Beachte, dass die Konstruktion der Linien im Zusammenhang mit dem zugrundeliegenden Schachbrettmuster zu zusammenhängenden Linien zwischen den Rändern führt.

Dadurch entstehen Pfade von der westlichen Seite durch den aztekischen Diamanten auf die östliche Seite, welch sich nicht kreuzen, und eine Verbindung zur Theorie der stochastischen Prozess. Da die Nordsteine keine Linie haben, gibt es keinen Pfad durch die Nordpolarregion (gelb). Die Pfade gehen von ${\displaystyle A_{r}=(-n-1+r,-r+1/2)}$ nach ${\displaystyle B_{r}=(n+1-r,-r+1/2)}$ für ${\displaystyle 1\leq r\leq n}$. Der nördlichste Pfad erhält man für ${\displaystyle r=1}$, er geht von ${\displaystyle A_{1}=(-n,-1/2)}$ nach ${\displaystyle B_{1}=(n,-1/2)}$ und kann als Pfad ${\displaystyle t\to X_{n}(t)}$ verstanden werden, das heißt ${\displaystyle (X_{n}(t))_{-n\leq t\leq n}}$ bildet ein stochastischer Prozess, wobei ${\displaystyle n}$ die Ordnung des Diamanten und ${\displaystyle t}$ die Zeit ist. Der zugrundeliegende Prozess ${\displaystyle X_{n}(t)}$ wird Nordpolarregion-Grenzprozess („NPR-Grenzprozess“) genannt. Die Nordpolarregion besteht aus all diesen Nord-Dominosteinen, welche über ${\displaystyle X_{n}(t)}$ liegen.^[6]

Der Satz des arktischen Kreises lautet wie folgt:

Sei ${\displaystyle A_{n}}$ der aztekische Diamant der Ordnung ${\displaystyle n}$. Sei ${\displaystyle \varepsilon >0}$ fix, dann existiert ein ${\displaystyle N(\varepsilon )}$ so dass für alle ${\displaystyle n\geq N}$ jede zufällige Parkettierung ${\displaystyle T\sim \operatorname {Uni} (A_{n})}$ von ${\displaystyle A_{n}}$ mit Wahrscheinlichkeit ${\displaystyle p>1-\varepsilon }$ eine gemäßigte Region hat, deren Rand gleichmäßig innerhalb eines Abstands von ${\displaystyle \varepsilon n}$ zum inneren Kreises mit Radius ${\displaystyle n/{\sqrt {2}}}$ bleibt.^[7]

Der Satz sagt also, dass wenn ${\displaystyle n}$ groß genug ist, nahezu alle zufällig gewählten Domino-Parkettierungen eine gemäßigte Region haben, deren Rand innerhalb des kleinen Abstands von ${\displaystyle \varepsilon n}$ zum inneren Kreis mit Radius ${\displaystyle n/{\sqrt {2}}}$ bleiben. Der Rand der gemäßigten Region kann außerhalb des Kreises liegen, er ist aber in der Nähe des Kreises. Dieses Ereignis geschieht mit der Wahrscheinlichkeit ${\displaystyle 1-\varepsilon }$ und je größer ${\displaystyle n}$ ist, desto kleiner kann ${\displaystyle \varepsilon }$ gewählt werden.

Das Resultat von Johansson lautet wie folgt:

Sei ${\displaystyle X_{n}(t)}$ der oben definierte NPR-Grenzprozess und ${\displaystyle {\mathcal {A}}_{2}(t)}$ sei der Airy₂-Prozess, und weiter sei das Gewicht der vertikalen Dominosteine ${\displaystyle a=1}$. Dann konvergiert

${\displaystyle {\frac {X_{n}(2^{-1/6}n^{2/3}t)-n/{\sqrt {2}}}{2^{-5/6}n^{1/3}}}\to {\mathcal {A}}_{2}(t)-t^{2}}$

in Verteilung wenn ${\displaystyle n\to \infty }$, im Sinne der endlichdimensionalen Verteilungen.^[8]

Damit ist gemeint, dass für jede endliche Auswahl von Zeitpunkten ${\displaystyle t_{1},\dots ,t_{k}}$ der Prozess ${\displaystyle (X_{n}(t_{1}),\dots ,X_{n}(t_{k}))}$ gegen ${\displaystyle ({\mathcal {A}}_{2}(t_{1})-t_{1}^{2},\dots {\mathcal {A}}_{2}(t_{k})-t_{k}^{2})}$ konvergiert.

1. ↑ William Jockusch, James Propp und Peter Shor: Random domino tilings and the arctic circle theorem. 1995, arxiv:math/9801068v1. 
2. ↑ Kurt Johansson: The arctic circle boundary and the airy process. In: Institute of Mathematical Statistics (Hrsg.): The Annals of Probability. Band 33, Nr. 1, 2005, S. 1–30, doi:10.1214/009117904000000937. 
3. ↑ Dan Romik: Arctic circles, domino tilings and square Young tableaux. In: Ann. Probab. Band 40, Nr. 2, 2012, S. 611 - 647, doi:10.1214/10-AOP628. 
4. ↑ ^{a b} Kurt Johansson: The arctic circle boundary and the airy process. In: Institute of Mathematical Statistics (Hrsg.): The Annals of Probability. Band 33, Nr. 1, 2005, S. 1, doi:10.1214/009117904000000937. 
5. ↑ Elkies, G.; Kuperberg, M.; Larsen, J.; Propp, J.: Alternating sign matrices and domino tilings. In: Journal of Algebraic Combinatorics. Band 1, Nr. 2, 1992, S. 111–132 und 219–234. 
6. ↑ Kurt Johansson: The arctic circle boundary and the airy process. In: Institute of Mathematical Statistics (Hrsg.): The Annals of Probability. Band 33, Nr. 1, 2005, S. 2, doi:10.1214/009117904000000937. 
7. ↑ William Jockusch, James Propp und Peter Shor: Random domino tilings and the arctic circle theorem. 1995, S. 2. 
8. ↑ Kurt Johansson: The arctic circle boundary and the airy process. In: Institute of Mathematical Statistics (Hrsg.): The Annals of Probability. Band 33, Nr. 1, 2005, S. 3, doi:10.1214/009117904000000937.