Erste Beispiele

Sierpinski Dreieck

Wir spielen folgendes Spiel (Barnsley's Chaos Game):

Gegeben sei ein Dreieck mit den Eckpunkten $1,2,3$ . Wir wählen einen beliebigen Startpunkt $x_0$ , sowie einen beliebigen Punkt $P$ , und berechnen mit der Vorschrift
$x_1=\frac{x_0+P}{2}$
den Punkt $x_1$ . Fahre nach diesem Schema fort, um weitere Punkte zu bestimmen.

Am einfachsten geht's, wenn man sich rasch ein Programm schreibt, das obiges Verfahren ausführt.

  import random
  import matplotlib.pyplot as plt

  def sierpinski(n):
    vertices = [(0.0,0.0), (0.5,0.85), (1.0,0.0)]
    points = []
    x,y = random.choice(vertices) #Startpunkt
  
    for i in range(n):
      vx,vy = random.choice(vertices) #waehle zufaellige Ecke
    
      x = (vx+x)/2.0 #Mittelung
      y = (vy+y)/2.0
    
      points.append((x,y))
    
    plot(points)

Noch ein Hinweis zur verblüffenden Tatsache, dass das Random Game gegen den Attraktor Sierpinski-Dreieck konvergiert. Klar und mit einfachen Argumenten wird dies im YouTube Video von Robin Truax erklärt.

Es gibt eine weitere, erstaunliche Beziehung zum Pascal'schen Dreieck, die ich von Agnes Scott habe. Und zwar kriegt man das Sierpinski-Dreieck-Muster, wenn man im Pascal'schen Dreieck alle geraden Zahlen mit einer Farbe markiert.

Das dies so ist, sieht man wie folgt ein: Bezeichne $P_n$ die ersten $2^n$ Zeilen des Pascal-Dreiecks (PD). Wir zeigen, dass $P_{n+1}$ aus 3 Kopien von $P_n$ besteht, die ein Dreieck mit geraden Koeffizienten umgeben. Die ersten $2^n$ Zeilen von $P_{n+1}$ sind natürlich identisch mit den ersten $2^n$ Zeilen von $P_n$ . Wir wollen beweisen, dass für jeden Koeffizienten in $P_n$ die Koeffizienten an den entsprechenden Positionen in den unteren linken und unteren rechten Dreiecken von $P_{n+1}$ denselben Wert (mod 2) haben wie der Koeffizient in $P_n$ .

Die Beweisgrundlage bildet das Theorem von Lucas. Das folgende klassische Theorem wurde 1890 von Édouard Lucas bewiesen:

Theorem 1

Sei $p$ priom und $r,c$ in $p$ -adischer Notation:

r=r_k\dots r_1r_0=r_0+r_1p+\dots+r_kp^k\quad(0\leq r_i<p)

c=c_k\dots c_1c_0=c_0+c_1p+\dots+c_kp^k\quad(0\leq c_i<p)

Dann gilt:

\binom{r}{c}=\binom{r_0}{c_0}\binom{r_1}{c_1}\dots\binom{r_k}{c_k}\mod(p)

Ferner gilt wie üblich $\binom{r}{c}=0$ , falls $c>r$ .

Proof

Um das Pascalsche Dreieck modulo 2 zu untersuchen, setzen wir $p=2$ . Der Binomialkoeffizient $\binom{r}{c}$ in Zeile $r$ und Spalte $c$ von $P_n$ kann in binärer Darstellung geschrieben werden, da $r,c<2^n$ :

r = r_{n-1}\dots r_1r_0,\quad c = c_{n-1}\dots c_1c_0\quad(r_i,c_i\in\{0,1\}.

In $P_n$ entspricht der Koeffizient an der unteren linken Ecke $\binom{2^n+r}{2^n+c}$ und an der unteren rechten Ecke $\binom{2^n+r}{c}$ . Nach Lucas’ Theorem gilt:

\binom{2^n+r}{c} \equiv \binom{r}{c}\mod(2),\quad\binom{2^n+r}{2^n+c} \equiv \binom{r}{c}\mod(2).

Alle drei Binomialkoeffizienten haben somit denselben Wert modulo 2 und damit dieselbe Farbe im Pascalschen Dreieck (mod 2). Dies beweist den ersten Teil des rekursiven Verhaltens.

Wir zeigen nun, dass die drei äquivalenten Eckdreiecke von $P_{n+1}$ ein Dreieck aus geraden Zahlen umgeben. Die letzte Zeile von $P_n$ entspricht $r=2^n-1$ . Die nächste Zeile, $r=2^n$ , hat Spalten $0\leq c\leq 2^n$ . Die Werte in den äußersten Spalten ( $0$ und $2^n$ ) sind gleich 1, während für $1\leq c\leq 2^n-1$ mindestens ein Binärbit in $c$ gleich $1$ ist. Daher ist:

\binom{2^n}{c} = \binom{10\dots0}{0c_{n-1}\dots c_0} = \binom{1}{0}\dots\binom{0}{c_0} \equiv 0\mod(2)\quad\text{für }1\leq c \leq 2^n-1.

Die Zeile beginnt und endet mit einer ungeraden Zahl, alle anderen Werte sind gerade. In der nächsten Zeile gilt:

\binom{r+1}{c} = \binom{r}{c}+\binom{r}{c-1}.

Die Summe einer geraden und einer ungeraden Zahl ist ungerade, die Summe zweier gerader Zahlen ist gerade. Daher bleibt die Kette gerader Zahlen erhalten, jedoch reduziert sich ihre Länge um 1. In der letzten Zeile von $P_{n+1}$ gibt es keine geraden Zahlen mehr, da diese Zeile $2^{n+1}-1$ nur aus ungeraden Zahlen besteht:

\binom{2^{n+1}-1}{c} = \binom{11\dots11}{c_n\dots c_0} = \binom{1}{c_n}\dots\binom{1}{c_0} \equiv 1\mod(2).

Dies zeigt, dass $P_{n+1}$ das gewünschte Muster aus drei Kopien von $P_n$ und einem Dreieck aus geraden Zahlen besitzt.

Die "Blätterteig-Funktion"

Wir kneten einen Blätterteig. Bei der Herstellung wird folgendermassen vorgegangen:

Ein Stück der Länge, sagen wir $1$ , wird auf die doppelte Länge ausgewallt, $2$ , dann zusammengefaltet auf die Länge $1$ , dann wiederum auf die doppelte Länge $2$ ausgewallt, dann zusammengefaltet auf Länge $1$ , dann auf die doppelte Länge. Und so weiter ...

Exercise 1: Blätterteig

a) Gibt es Fixpunkte?

b) Was könnte mit Vorfixpunkte gemeint sein?

c) Findest du Vorfixpunkte?

d) Gibt es Zyklen der Länge $2$ ?

e) Gibt es Zyklen beliebiger Länge?

f) Wie sieht der Orbit von $\frac{\sqrt{2}}{2}$ aus?

Solution

Für die Funktion brauchen wir eine Fallunterscheidung:

f(x)=\begin{cases} 2x & 0\leq x\leq0.5\\ 2-2x & 0.5\leq x\leq1 \end{cases}

a) Die Fixpunktbedingungen liefern

\begin{align*} 2x &\stackrel{!}{=} x\\ x &= 0 \end{align*}

bzw.

\begin{align*} 2-2x &\stackrel{!}{=} x\\ 2 &= 3x\\ x &=\frac{2}{3} \end{align*}

Also sind $x_{1}=0$ und $x_{2}=\frac{2}{3}$ Fixpunkte.

b) Ich vermute, dass ein Vorfixpunkt ein Punkt ist, der nach unendlich vielen Iterationsschritten gegen einen Fixpunkt konvergiert.

c) Zum Beispiel $1$ , denn $f(1)=2-2=0$ ist nach einer Iteration beim Fixpunkt $0$ . Mit Reverse Engineering findet man unendlich viele weitere: $\frac{1}{2^{k}}, k\in\mathbb{N}$ , da $f^{-1}(1)=\frac{1}{2}$ . Auch $\frac{1}{3}$ ist Vorfixpunkt und somit $\frac{1}{3\cdot2^{k}}, k\in\mathbb{N}$ . Für $n\in\mathbb{N}, n>3$ ist $f^{-1}(\frac{n-1}{n})=2-2\cdot\frac{n-1}{n}=\frac{2n-2(n-1)}{n}=\frac{2}{n}\leq\frac{1}{2}$ und mündet vermutlich in Vorfixpunkten. Interessant ist die Untersuchung für Werte mit primen Nenner, $\frac{1}{p}$ oder Stammbrüche $\frac{1}{n}$ . Rationale Zahlen scheinen hierbei erfolgsversprechend.

d) Gibt es Fixpunkte der Periode 2? Dazu müssen wir 4 Fälle anschauen. Der Startwert liegt unter $0.5$ bzw. oberhalb von $0.5$ ; er bleibt nach einer Iteration in diesem Bereich oder er wechselt den Fall. Nehmen wir zuerst an, dass Startwert $x_{0}$ sowie Funktionswert $f(x_{0})$ beide kleiner als $0.5$ sind:

\begin{align*} f(f(x)) &\stackrel{!}{=} x\\ 4x &= x \end{align*}

und es folgt $x=0$ , den wir bereits kennen. Oberhalb $0.5$ :

\begin{align*} f(f(x)) &\stackrel{!}{=} x\\ 2-2(2-2x) &= x\\ 4x-2 &= x\\ x &= \frac{2}{3} \end{align*}

Den kennen wir auch. Unten oben:

\begin{align*} f(f(x)) &\stackrel{!}{=} x\\ 2-2(2x) &= x\\ 2 &= 5x \end{align*}

Wir haben einen echten gefunden, nämlich $x_{3}=\frac{2}{5}$ . Schliesslich noch die letzte Variante, obwohl wir auch die Bahn von $x_{3}$ verfolgen könnten:

\begin{align*} f(f(x)) &\stackrel{!}{=} x\\ 2(2-2x) &= x\\ 4 &= 5x \end{align*}

Es ist also $x_{4}=\frac{4}{5}$ .

e) Dazu rechnet man am besten ein paar Beispiele durch und sucht nach Struktur. Ich habe beispielsweise Dreierzyklen ( $x=\frac{4}{9}$ oder $x=\frac{6}{7}$ ), Viererzyklen ( $x=\frac{2}{15}$ , $x=\frac{6}{17}$ oder $x=\frac{2}{17}$ ) und weitere gefunden. Exemplarisch sei die Suche nach Viererzyklen kommentiert: Von den $2^{4}=16$ Fallunterscheidungen müssen nur die wenigsten im Detail gerechnet werden, da man Zweierzyklen wieder erkennt und Fälle durch zyklische Fortsetzung identisch sind. Man findet im wesentlichen die neuen Kandidaten (oben, unten): uuuo, uuoo, ooou. Kombinatorisch folgt also, dass es sicher immer mindestens 2 neue $k$ -Zyklen gibt, nämlich uooo ... o und ouuu ... u mit den Werten $\frac{2}{2^{k}+1}$ bzw. $\frac{2}{2^{k}-1}$ .

f) Den Orbit von $\frac{\sqrt{2}}{2}$ lässt man am bequemsten berechnen. Zum Beispiel

x0 = 1/20
n = 10
def f(x=0):
  if x<0.5:
    return 2*x
  else:
    return 2-2*x
print(x0)
for k in range(n):
  x0 = f(x0)
  k = k+1
  print(x0)

$\frac{\sqrt{2}}{2}\not\in\mathbb{Q}$ wird nie zyklisch.