EIN LEMMA ÜBER PERLENKETTEN

VON

Andreas DRESS UND Christian SIEBENEICHER

Abstract: We establish a diagram providing various bijections related to the theory of necklaces (or ‘aperiodic words’) and clarifying the relationship between these bijections.

Ist E eine endliche Menge, σ : E ⟶ E eine zyklische Permutation von E und f : E ⟶ A eine Abbildung von E in die Menge A, dann nennt man das Paar (σ, f) eine Perlenkette (über E). Die Elemente der Menge E sind die Perlen des Perlenkette. Diese sind vermittels der Abbildung f durch Farben aus A gefärbt; die Perle ϵ ∈ E hat die Farbe f(ϵ). Die Komposition f ∘ σ^{i} liefert für jedes i ∈ N = {1, 2, …} eine weitere Färbungsabbildung und also auch eine weitere Perlenkette (σ, f ∘ σ^{i}). Stimmt die ursprüngliche Perlenkette (σ, f) für ein i mit σ^{i} ≠ 1_{E} mit (σ, f) überein, dann sagt man, (σ, f) sei periodisch. Eine nicht periodische Perlenkette heißt aperiodisch oder primitiv.

Ist die Permutation σ nicht notwendigerweise zyklisch, dann erhalten wir anstelle einer Perlenkette eine ganze Familie von Perlenketten (über E), eine Auslage von Perlenketten. Die einzelnen Perlenketten der Auslage sind gegeben durch die Einschränkung der Abbildung f : E ⟶ A auf die Zyklen von σ.

Hat man a Farben zur Verfügung (#A = a < ∞), dann gibt es in einer n–elementigen Menge E genau n! · a^{n} Auslagen von Perlenketten. Die exponentielle erzeugende Funktion für die Auslagen von Perlenketten ist daher gleich

1 + ∑_{n=1}^{∞} n! · a^{n} \frac{t^{n}}{n!} = \frac{1}{1 − at}.

Für diese hat man die Produktzerlegung

\frac{1}{1 − at} = ∏_{n=1}^{∞} (\frac{1}{1 − t^{n}} )^{M(a,n)} ,

die sogenannte zyklotomische Identität, mit ganzzahligen Exponenten

M(a, n) = \frac{1}{n} ∑_{d|n} μ(d)a^{\frac{n}{d}}

(μ die Möbius–Funktion). Die Exponenten in der Produktzerlegung berechnet man am einfachsten, wenn man zur logarithmischen Ableitung der zyklotomischen Identität übergeht (cf. [G]). Da M(a, n) gleich der Anzahl der primitiven Perlenketten der Länge n ist, lag es nahe, nach einer kombinatorischen Interpretation der zyklotomischen Identität zu suchen. In [MR] liefern N.Metropolis und G.-C.Rota eine solche Interpretation. Die zentrale Rolle hierbei spielt eine Bijektion zwischen bestimmten Teilmengen der Menge der Auslagen von Perlenketten über [n] := {1, …, n} und der Menge [n]! der Permutationen von [n]. Ein andere kombinatorische Interpretation der zyklotomischen Identität ergibt sich (cf. [DS1]), wenn man symmetrische Potenzen der Menge P (A) der periodischen Funktionen auf der Menge Z der ganzen Zahlen mit Werten in der Menge A betrachtet.

Wir wollen hier nun eine recht narürlich erscheinende Bijektion angeben, die diese beiden Aspekte als Spezialfälle enthält. Hierzu betrachten wir für eine Perlenkette (σ, f) und eine Perle ϵ ∈ E die Abbildung

f_{σ}^{ϵ} : Z ⟶ A i ↦ f(σ^{i} ϵ),

die offensichtlich eine periodische Funktion auf Z mit Werten in A definiert. Man kann sie als Perle einer neuen Perlenkette auffassen, wenn man auf der Menge P (A) die Shift–Abbildung α : P (A) ⟶ P (A) dadurch definiert, daß man für g ∈ P (A) setzt:

(α g)(i) := g(i + 1) für alle i ∈ Z.

Auf der Bahn π_{(σ,f)} = {f_{σ}^{η} | η ∈ E} von f_{σ}^{ϵ}, der sogenannten Shift–Periode von (σ, f), induziert die Shift–Abbildung α eine zyklische Permutation, und man erhält eine Perlenkette, wenn man die Perlen (die Elemente) von π_{(σ,f)} mittels der Evaluationsabbildung an der Stelle 0, also mittels

ev : P (A) ⟶ A g ↦ g(0)

färbt. Wir bezeichnen diese Perlenkette ebenfalls mit π_{(σ,f)}. Sie ist offensichtlich primitiv. Geht man von einer Auslage von Perlenketten aus, dann erhält man auf diese Weise eine Auslage Π_{(σ,f)} von primitiven Perlenketten über der nunmehr ebenfalls mit Π_{(σ,f)} bezeichneten Menge {f_{σ}^{η} | η ∈ E}. Wir merken an, daß in der Auslage Π_{(σ,f)} in der Regel weniger Perlenketten enthalten sind als in der ursprünglichen Auslage (σ, f).

Um diesen Informationsverlust wenigstens teilweise wieder wettzumachen, betrachtet man die Funktion

u_{(σ,f)} : P (A) ⟶ N_{0} u_{(σ,f)}(g) := #{ϵ ∈ E | f_{σ}^{ϵ} = g}.

Sie veschwindet außerhalb von Π_{(σ,f)} und ist konstant auf den Shift–Perioden der zu (σ, f) gehörigen Perlenketten. Der konstante Wert von u_{(σ,f)} auf der Shift–Periode π ist gleich der Anzahl derjenigen Perlen aus E, die eine beliebige aber feste Perle von π als zugehörige periodische Funktion haben. Ist l die Länge der Periode π, dann ist die Anzahl der Perlen aus E, deren zugehörige periodische Funktion in π liegt, gleich l · u(π). Insbesondere folgt, daß die Menge

[u_{(σ,f)}] := {(g, k) | g ∈ P (A) und 1 ≤ k ≤ u_{(σ,f)}(g)} ⊂ P (A) × N_{0}

die gleiche Kardinalität hat wie die Menge E.

Für eine vollständige Rekonstruktion der ursprünglichen Auslage von Perlenketten aus der zugehörigen Auslage von primitiven Perlenketten ist es nützlich (nötig?), die Trägermenge E der Perlenkette zu normieren. Wir wählen E = [n] = {1, …, n}. Die natürliche Ordnung von [n] erlaubt es dann, die Funktion

\begin{matrix}k_{(σ,f)} : [n] ⟶ N_{0} \\ ν ↦ k_{(σ,f)}(ν) := #\{μ ∈ [n] | μ ≤ ν und f_{σ}^{μ} = f_{σ}^{ν}\} \end{matrix}

zu definieren und mit ihrer Hilfe die Abbildung

[n] ⟶ P (A) × N_{0} ν ↦ (f_{σ}^{ν}, k_{(σ,f)}(σ ν))

zu konstruieren. Diese Abbildung ist injektiv, und ihre Einschränkung auf das Bild liefert eine Bijektion Φ_{(σ,f)} : [n] ⟶ [u_{(σ,f)}].

Wir zeigen, daß die Auslage (σ, f) durch das Paar (u_{(σ,f)}, Φ_{(σ,f)}) eindeutig bestimmt ist. Hierzu setzen wir u := u_{(σ,f)}, Φ := Φ_{(σ,f)} und Φ(ν) := (g_{ν}, k_{ν}) und betrachten die ebenfalls mit ev bezeichnete Abbildung

ev : P (A) × N_{0} ⟶ A (g, k) ↦ g(0).

Dann hat man:

• ev ∘ Φ_{(σ,f)}(ν) = ev(f_{σ}^{ν}, k_{(σ,f)}(σν)) = f_{σ}^{ν}(0) = f(ν), und man sieht, daß die Färbungsabbildung f eindeutig durch das Paar (u_{(σ,f)}, Φ_{(σ,f)}) bestimmt ist.

• (g_{σ ν}, k_{σ ν}) = Φ_{(σ,f)}(σ ν) = (f_{σ}^{σ ν}, k_{(σ,f)}(σ(σ ν))), und also

g_{σ ν}(i) = f_{σ}^{σ ν}(i) = f(σ^{i}(σ ν)) = f(σ^{i+1} ν) = f_{σ}^{ν}(i + 1)
= g_{ν}(i + 1)
= α g_{ν}(i).

Es ist daher g_{σν} = α g_{ν}, und folglich gilt σ ν ∈ {μ ∈ [n] | g_{μ} = α g_{ν}}. Schreibt man also {μ ∈ [n] | g_{μ} = α g_{ν}} = {μ_{1}, μ_{2}, …, μ_{u(g_{ν})}} mit μ_{1} < μ_{2} < … < μ_{u(g_{ν})}, dann ist σ ν = μ_{k_{ν}} aufgrund der Definition der Abbildung k_{(σ,f)} ∘ σ. Der Wert der Permutation σ auf dem Element ν ∈ [n] ist also durch das Element Φ(ν) = (g_{ν}, k_{ν}) in [u] festgelegt und damit ist auch die Permutation σ eindeutig durch das Paar (u_{(σ,f)}, Φ_{(σ,f)}) bestimmt.

Insgesamt haben wir also eine bijektive Korrespondenz zwischen den Auslagen von Perlenketten in [n] und den zugehörigen Paaren (u_{(σ,f)}, Φ_{(σ,f)}). Diese erhält einen konzeptionellen Rahmen wenn wir die Mengen

s^{n}(P (A)):={u:P (A) → N_{0} | ∑_{g∈P (A)}u(g) = n , u(g)=u(αg) für alle g ∈P (A)}

S^{A}(n) := {(u, Φ) | u ∈ s^{n}(P (A)), Φ : [n] ⟶ [u] bijektiv}

und die Abbildungen

p : S^{A}(n) → A^{[n]} : (u, Φ) ↦ ev ∘ Φ

q : [n]! × A^{[n]} ⟶ s^{n}(P (A)) : (σ, f) ↦ u_{(σ,f)}

betrachten und dann alles in dem folgenden Diagramm arrangieren,

[figure: [n]! × A^{[n]}; A^{[n]}; s^{n}(P (A)); S^{A}(n); pr_{2}; q; p; pr_{1}]

in dem pr_{1} und pr_{2} die kanonischen Projektionen auf den ersten bzw. den zweiten Faktor sind und [n]! die Menge der Permutationen der Menge [n] bezeichnet.

Mit diesen Definitionen hat man dann das folgende

Lemma: Es gibt eine Bijektion Ψ : [n]! × A^{[n]} ⟶ S^{A}(n), die das Diagram kommutativ ergänzt:

[figure: [n]! × A^{[n]}; A^{[n]}; s^{n}(P (A)); S^{A}(n); pr_{2}; q; p; pr_{1}; Ψ]

Beweis: Man definiert die Abbildung Ψ : [n]! × A^{[n]} ⟶ S^{A}(n) durch (σ, f) ↦ (u_{(σ,f)}, Φ_{(σ,f)}). Es gilt dann

pr_{1} ∘ Ψ(σ, f) = u_{(σ,f)} = q(σ, f),

das rechte Dreieck des Diagrammes ist also kommutativ. Ferner hat man für jedes ν ∈ [n]

p ∘ Ψ(σ, f)(ν) = ev(Φ_{(σ,f)}(ν)) = ev(f_{σ}^{ν}, k_{(σ,f)}(σν))
= f_{σ}^{ν}(0) = f(σ^{0} ν)
= f(ν),

Ψ ergänzt also in der Tat das Diagramm kommutativ.

Die Injektivität von Ψ ist das unmittelbare Ergebnis der Diskussion der Zuordnung (σ, f) ↦ (u_{(σ,f)}, Φ_{(σ,f)}), und diese legt darüber hinaus auch nahe, wie man zu gegebenem (u, Φ) ∈ S^{A}(n) ein Urbild in [n]! × A^{[n]} findet. □

Korollar: 1 Es gibt eine Bijektion zwischen der Menge der Auslagen von Perlenketten in [n] mit Shift–Periode π und der Menge [n]! der Permutationen von [n] (cf. [MR]).

Beweis: Ist l die Länge der Periode π, dann ist n = k·l mit passendem k. Sei u : P (A) ⟶ N_{0} diejenige Funktion, die auf jedem der Elemente von π den Wert k hat und außerhalb von π verschwindet. Die Faser q^{−1}(u) von q über u ist offensichtlich gleich der Menge der Auslagen von Perlenketten in [n] mit der Shift–Periode π. Die Einschränkung der Bijektion Ψ auf q^{−1}(u) liefert eine Bijektion auf die Menge pr_{1}^{−1}(u) = {(u, Φ) ∈ S^{A}(n) | Φ : [n] → [u] bijektiv}. Die Komposition von Φ mit einer beliebigen Bijektion [u] → [n] liefert dann eine Bijektion der gewünschten Art. □

Die Fasern der Projektionsabbildungen pr_{1} und pr_{2} haben jeweils die Kardinalität n!. Deshalb haben auch die Fasern der Abbildungen p und q die Kardinalität n!. Insbesondere sind daher die Mengen s^{n}(P (A)) und A^{[n]} gleich mächtig, was in [DS1] in anderer Weise gezeigt wurde. Ist #A = a < ∞, dann erhält man das

Korollar: 2 Ist

Z(P (A), t) := 1 + ∑_{n=1}^{∞} #s^{n}(P (A)) · t^{n}

die ζ–Funktion der Menge P (A) im Sinne von [DS1], dann gilt

Z(P (A), t) = \frac{1}{1 − at}.

Die Menge P (A) zerfällt unter der Shift–Abbildung in disjunkte Zyklen. Da die ζ–Funktion einer disjunkten Vereinigung gleich dem Produkt der ζ–Funktionen der einzelnen Summanden ist (cf. [DS1]), ist Z(P (A), t) gleich dem Produkt der ζ–Funktionen der in P (A) gelegenen Zyklen. Die

ζ–Funktion eines Zyklus der Länge n ist aber gleich \frac{1}{1 − t^{n}} (cf. [DS1]). Das ergibt:

Korollar: 3 Die ζ–Funktion der Menge P (A) der periodischen Funktionen auf Z mit Werten in der Menge A besitzt die Produktzerlegung

\frac{1}{1 − at} = ∏_{n=1}^{∞} (\frac{1}{1 − t^{n}} )^{M(a,n)} ,

in der M(a, n) gleich der Anzahl der Zyklen der Länge n in P (A) oder, äquivalent hierzu, gleich der Anzahl der primitiven Perlenketten der Länge n ist.

Wie uns Volker Strehl mitteilte, haben N.G. de Bruijn und D.A. Klarner in [dBK] eine explizite Bijektion A^{[n]} ⟶ s^{n}(P (A)) angegegeben.

Im Rahmen unserer Überlegungen läßt sich zur Existenz solcher Bijektionen folgendes sagen. Sind s : A^{[n]} ⟶ [n]! × A^{[n]} und t : s^{n}(P (A)) ⟶ [n]! × A^{[n]} zwei Schnitte, d.h. ist pr_{1} ∘ s = 1_{A^{[n]}} und p ∘ t = 1_{s^{n}(P (A))}, dann induzieren die Einschränkungen von pr_{1} bzw. von p auf das Bild von s bzw. das Bild von t Bijektionen pr_{1} : Bild s ⟶ A^{[n]} bzw. p : Bild t ⟶ s^{n}(P (A)). Ist Bild s = Bild t, dann sind p ∘ s und pr_{1} ∘ t zueinander inverse Bijektionen zwischen A^{[n]} und s^{n}(P (A)).

Schnitte der angegebenen Art erhält man, wenn die Menge A linear geordnet ist und man auf der Menge A^{∗} aller Wörter über A die lexikographische Ordnung betrachtet.

Den Elementen der Mengen A^{[n]} und P (A) kann man in naheliegender Weise Wörter zuordnen: der Abbildung f : [n] ⟶ A das Wort f(1) ⋯ f(n) und der periodischen Funktion g mit der Periode k das Wort g(1) ⋯ g(k). Das erlaubt dann die Definition induzierter linearer Ordnungen auf A^{[n]} und P (A):

• f ⪯ f′ genau dann, wenn f(1) ⋯ f(n) ⪯ f′(1) ⋯ f′(n),

• g ⪯ g′ genau dann, wenn g(1) ⋯ g(k) ⪯ g′(1) ⋯ g′(k′) ist.

Diejenigen periodische Funktionen, die minimal sind in ihrer Shift–Periode, nennt man normal, die zugehörigen Wörter sind die sogenannten Lyndon– Wörter. Für Lyndon–Wörter hat man (cf. [BP, p. 362] und [L, p. 67])

• Ein Wort ist genau dann ein Lyndon–Wort, wenn es kleiner ist als jeder seiner echten Rechtsfaktoren.

• Sind l und m Lyndon–Wörter und ist l ⪯ m, dann ist auch lm ein Lyndon–Wort (und es ist lm ⪯ m).

• Ist w = l_{1}l_{2} ⋯ l_{k} ein Produkt von Lyndon–Wörtern, und ist l_{1} ⪰ l_{2} ⪰ … ⪰ l_{k}, dann ist l_{k} der kleinste Rechts–Faktor von w.

Ist f ∈ A^{[n]}, dann sei f = f_{1}f_{2} ⋯ f_{k} dasjenige Produkt von Lyndon–Wörtern, bei dem f_{k} ein möglichst kleiner Rechts–Faktor von f ist (mit der Länge l_{k}), f_{k−1} ein möglichst kleiner Rechts–Faktor von dem Restwort von f, das entsteht, wenn man den Rechtsfaktor f_{k} wegläßt usw. Es gilt dann f_{1} ⪰ f_{2} ⪰ … ⪰ f_{k}, und wenn wir gleiche Faktoren zusammenfassen können wir schreiben:

f = f_{1}^{u_{1}} ⋯ f_{k}^{u_{k}}.

Die Wörter f_{1}^{u_{1}}, f_{2}^{u_{2}}, …, f_{k}^{u_{k}} definieren dann Abbildungen

f_{1}^{u_{1}} : {1, …, u_{1}l_{1}} ⟶ A,
f_{2}^{u_{2}} : {u_{1}l_{1} + 1, …, u_{1}l_{1} + u_{2}l_{2}} ⟶ A,
⋮
f_{k}^{u_{k}} : {u_{1}l_{1} + … + u_{k−1}l_{k−1} + 1, …, n} ⟶ A,

die natürlich nichts anderes sind als die Einschränkungen von f auf das jeweilige Teilintervall von [n]. Betrachtet man auf jedem dieser Teilintervalle die zyklische Permutation, die jedem Element des Intervalls das nächstgrößere Element zuordnet und das letzte Element auf das erste abbildet, dann erhält man insgesamt eine Permutation σ_{f} von [n], und das Paar (σ_{f}, f) definiert daher eine Auslage von Perlenketten über [n]. Es ist klar, daß die Zuordnung f ↦ (σ_{f}, f) einen Schnitt s : A^{[n]} ⟶ [n]! × A^{[n]} definiert.

Ganz entsprechend kann man jedem Element u ∈ s^{n}(P (A)) eine Auslage von Perlenketten über [n] zuordnen, indem man zunächst die Shift–Perioden des Trägers von u mittels der in ihnen enthaltenen normalen Elemente nach absteigender Größe ordnet. Hat in dieser absteigenden Folge die i–te Shift– Periode die Länge l_{i} und hat u auf ihr den Wert u_{i}, dann ordnet man ihr das Teilintervall {u_{1}l_{1} + … u_{i−1}l_{i−1} + 1, …, u_{1}l_{1} + … + u_{i}l_{i}} von [n] zu. Es hat die Länge u_{i}l_{i}, und

{1, …, u_{1}l_{1}}∪{u_{1}l_{1} +1, …, u_{1}l_{1} +u_{2}l_{2}}∪…∪{u_{1}l_{1} +… u_{k−1}l_{k−1} +1, …, n}

ist eine disjunkte Zerlegung des Intervalles [n]. Auf jedem dieser Teilintervalle betrachtet man wieder die naheliegende zyklische Permutation und erhält so insgesamt eine Permutation σ_{u} von [n]. Das erste Element u_{1}l_{1}+… u_{i−1}l_{i−1}+1 des i–ten Teilintervalles färbt man mit der Farbe g(0) des normalen Elementes g der i–ten Shift–Periode, und seine Bilder unter den Iterierten von σ_{u} erhalten die Farbe des entsprechenden Iterierten von g unter dem Shift. Zusammen genommen liefert dies eine Färbung f_{u} des Intervalles [n] und also eine Auslage (σ_{u}, f_{u}) von Perlenketten, deren Bild unter p gleich u ist. Offensichtlich definiert die Zuordnung u ↦ (σ_{u}, f_{u}) einen Schnitt t : s^{n}(P (A)) ⟶ [n]! × A^{[n]}.

Aufgrund der Eigenschaften der Lyndon–Wörter ist es klar, daß die Bilder der Schnitte s und t übereinstimmen und die Abbildungen p∘s und pr_{1}∘t deshalb zueinander inverse Bijektionen zwischen A^{[n]} und s^{n}(P (A)) definieren. Dies liefert im wesentlichen die Konstruktion von de Bruin und Klarner.

Literatur

[BP] Berstel J., Perrin D. — Theory of Codes — Academic Press (1985).

[dBK] de Bruijn N.G., Klarner D.A. — Multisets of aperiodic cycles, SIAM J. Alg. Disc. Meth., vol. 3(1982), 359–368.

[DS1] Dress A.W.M., Siebeneicher Ch. — The Burnside Ring of the Infinite Cyclic Group and its Relations to The Necklace Algebra, λ–Rings and The Universal Ring of Witt Vectors(1987); to appear in: Advances in Mathematics.

[DS2] Dress A.W.M., Siebeneicher Ch. — On the Number of Solutions of Certain Linear Diophantine Equations, preprint Bielefeld (1988).

[G] Gauss C.F. — Werke Band II — Königliche Gesellschaft der Wissenschaften, Göttingen (1863), 219–222.

[L] Lothaire M. — Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Addison–Wesley Publishing Company (1983).

[MR] Metropolis N., Rota G.-C. — The cyclotomic Identity, Contemporary Mathematics, vol. 34 Amer. Math. Soc. (1984), 19–24.

Andreas Dress und Christian Siebeneicher, Universität Bielefeld, Fakultät für Mathematik, Postfach 10 01 31, D 33 501 Bielefeld electronic mail: dress@mathematik.uni-bielefeld.de

sieben@mathematik.uni-bielefeld.de.