Zyklisches Sieben

Zyklisches Sieben ist ein mathematisches Phänomen aus der Kombinatorik. Es tritt dann auf, wenn das Berechnen der erzeugenden Funktion an den Stellen der Einheitswurzeln gleichzeitig ein Abzählen von Symmetrieklassen von Objekten ist, auf die eine zyklische Gruppe wirkt.

Definition

Sei $X$ eine endlichen Menge und $C_{n}=\langle a\rangle$ eine zyklische Gruppe der Ordnung $n$, welche auf $X$ operiert. Sei $P(q)\in \mathbb {Z} [q]$ ein Polynom mit ganzzahligen Koeffizienten in $q$. Für ein $d\in \mathbb {Z}$ bezeichnen wir mit $\zeta ^{d}$ die Einheitswurzeln

$\zeta ^{d}:=\exp \left(2\pi \mathrm {i} {\tfrac {d}{n}}\right).$

Das Triple $(X,P(q),C_{n})$ besitzt das Zyklisches-Sieben-Phänomen (CSP von englisch cyclic sieving phenomenon) falls für alle $d\in \mathbb {Z}$ die Gleichung

$|\{x\in X\colon g^{d}\circ x=x\}|=P(\zeta ^{d})$

gilt. Das heißt, das Polynom ausgewertet an den Einheitswurzeln $\zeta ^{d}$ ist gleich der Anzahl der Element in $X$, für die $g^{d}\circ x=x$ gilt.

Da $P(1)=|X|$ gilt, ist $P(q)$ eine erzeugende Funktion von $X$ genannt das q-Analogon von $X$.

Beispiel

Sei $n,k\in \mathbb {N}$ mit $0\leq k\leq n$. Bezeichne mit $M_{k}=i_{1}i_{2}\dots i_{k}$ eine Multimenge auf $[n]:=\{1,2,\dots ,n\}$ mit $k$ Elementen und $1\leq i_{1}\leq i_{2}\leq \cdots \leq i_{k}\leq n$. Dann sei $X$ die Familie

$X=\left(\!\!{\dbinom {[n]}{k}}\!\!\right):=\{M_{k}\colon M_{k}\;{\text{ist eine }}k{\text{-Multimenge von }}[n]\}$

und für die Kardinalität gilt

$|X|={\binom {n+k-1}{k}}.$

Betrachte die zyklische Gruppe $C_{n}=\langle (1,2,\dots ,n)\rangle$. Dann wirkt die Gruppenoperation $g\in C_{n}$ auf $M_{k}$ wie folgt

$gM_{k}=g(i_{1})g(i_{2})\dots g(i_{k}).$

Als $P(q)$ wählen wir den q-Binomialkoeffizient

$P(q)={\binom {n+k-1}{k}}_{q}:={\frac {[n+k-1]_{q}!}{[k]_{q}![n-1]_{q}!}}$

wobei $[k]_{q}!:=[k]_{q}[k-1]_{q}\cdots [1]_{q}$ und $[k]_{q}:=1+q+q^{2}+\dots +q^{k-1}$ das q-Analogon von $k$ bezeichnet. Es lässt sich zeigen, dass das Tripel $(X,P(q),C_{n})$ das CSP besitzt.

Als konkretes Beispiel wähle $n=3,\;k=2$. Es gilt $X=\{11,22,33,12,13,23\}$ und $C_{3}=\{e,(1,2,3),(1,3,2)\}$. Sei $g=(1,2,3)$ dann ist

$(1,2,3)11=22,\quad (1,2,3)22=33\quad (1,2,3)33=11,\qquad (1,2,3)12=23,\qquad (1,2,3)13=12,\qquad (1,2,3)23=13.$

Dann ist das entsprechende Polynom

$P(q)={\binom {4}{2}}_{q}={\frac {[4]_{q}!}{[2]_{q}![2]_{q}!}}=1+q+2q^{2}+q^{3}+q^{4}.$

Literatur

• Per Alexandersson: The cyclic sieving phenomenon. (symmetricfunctions.com). 
• Bruce E Sagan: The cyclic sieving phenomenon: a survey. In: arXiv:abs/1008.0790 [math.CO]. 2010, arxiv:1008.0790 [abs]. 
• Reiner Victor, Dennis Stanton und Dennis White: What is... Cyclic Sieving? In: Notices of the American Mathematical Society. Band 61, Nr. 2, Februar 2014, S. 169–171, doi:10.1090/noti1084 (ams.org [PDF]).