Orbits unter einer Transformation
Definition (Orbit)
Seien A eine Menge, g : A → A und a ∈ A. Dann heißt die Folge
(gn(a))n ∈ ℕ = (a, g(a), g(g(a)), …)
der Orbit von a unter der Transformation g.
Die Potenzfolge a0, a1, a2, …, an, … eines Monoidelements a ist ein Beispiel für einen Orbit. Denn wegen
an = ℓan(e) = ran(e) für alle n ∈ ℕ
ist die Folge (an)n ∈ ℕ der Orbit des neutralen Elements e unter den Translationen ℓa, ra : A → A.
In vielen Orbits wiederholen sich die Folgenglieder periodisch. Hierzu präzisieren wir:
Definition (periodische Folge)
Eine Folge (an)n ∈ ℕ in einer beliebigen Menge A heißt (schließlich) periodisch, falls es ein n0 ≥ 0 und ein p ≥ 1 gibt mit
(+) an = an + p für alle n ≥ n0.
Das kleinste p wie in (+) heißt die Minimalperiode der Folge. Gilt (+) für n0 = 0, so heißt die Folge reinperiodisch.
Eine periodische Folge hat also die Form
a0, …, an0, …, an0 + p − 1, an0, …, an0 + p − 1, an0, …, an0 + p − 1, …
Ist die Folge reinperiodisch, so hat sie die Form
a0, …, ap − 1, a0, …, ap − 1, a0, …, ap − 1, …
Darstellung einer periodischen Folge (an)n ∈ ℕ. Der Kreis wird ab der Stelle n0 unendlich oft durchlaufen
Beispiel
Die bekanntesten Beispiele für periodische Folgen sind wahrscheinlich die Dezimalbrüche: Eine reelle Zahl x ist genau dann rational, wenn sie eine Dezimalbruchdarstellung x = ±n,d1d2d3… mit einer periodischen Folge (dn)n ≥ 1 von Dezimalstellen di ∈ { 0, …, 9 } besitzt.
Nach diesen Vorbereitungen zeigen wir nun:
Satz (periodische Orbits)
Seien A eine Menge, g : A → A und a ∈ A derart, dass der Orbit von a unter g nicht injektiv ist. Dann ist der Orbit periodisch. Speziell ist jeder Orbit in einer endlichen Menge periodisch.
Beweis
Da (gn(a))n ∈ ℕ nicht injektiv ist, gibt es minimale n0 ≥ 0 und p ≥ 1 mit
gn0(a) = gn0 + p(a).
Dann gilt aber
gn0 + n(a) = gn(gn0(a)) = gn(gn0 + p(a)) = gn0 + n + p für alle n ≥ 0,
sodass der Orbit die Minimalperiode p ab der Stelle n0 besitzt. Da es in einer endlichen Menge keine injektiven unendlichen Folgen gibt, folgt der Zusatz.
Als Korollar erhalten wir, dass jede Potenzfolge in einem endlichen Monoid periodisch ist. In den drei obigen Beispielen zu Potenzfolgen auf endlichen Transformationen ist (n0, p) gleich (1, 3), (0, 6) bzw. (2, 1).
Wir fassen die Ergebnisse noch einmal aus einem anderen Blickwinkel zusammen:
Orbits aus graphentheoretischer Sicht
Stellen wir uns eine Transformation f : A → A als gerichteten (möglicherweise unendlichen) Graphen mit der Eckenmenge A vor, bei dem eine Kante genau dann von a nach b zeigt, wenn f (a) = b gilt, so ist der Orbit von a unter f der unendlich lange Kantenzug, der bei a startet und stets den eindeutigen Pfeilen folgt. Der Orbit besucht genau dann nur endlich viele Ecken, wenn er eine Ecke zweimal besucht (d. h. wenn er kein Weg ist). In diesem Fall ist der Orbit ein (gerichteter) Kreis, oder er läuft irgendwann in einen Kreis hinein, den er nicht mehr verlassen kann. Dabei kann ein solcher gerichteter Kreis aus einer oder zwei Ecken bestehen (falls eine Ecke b mit f (b) = b besucht wird bzw. Ecken a, b mit f (a) = b und f (b) = a besucht werden).