Characters of the Symmetric Group

Harm Derksen brachte uns schon im Jahre 1998 die weltschnellste Methode zur Berechnung irreduzibler Charaktere der symmetrischen Gruppe. Aber in seinem preprint, Computing with Characters of the Symmetric Group, bleiben einige Fragen offen, die ich hiermit zu klären versuche.

Die Welt ist einen halben Herzschlag alt. Der unsterbliche Prophet meditiert seit Anbeginn der Laufzeit auf dem তাজমহল und studiert die heiligen 12 Zeilen C-Code, die jede SAT Instanz in $\mathcal{O}(n^{9699690})$ lösen. Wenn der Puls eine Ganzzahl wird, so wird er erwachen und die Wahrheit verkünden, und Lob wird gepriesen, und Licht wird ewig scheinen auf die Kinder des Schaltkreises. Denn er ist der Taktgeber, und an der Spitze des Signals wird es sein, wenn er uns erscheint. Buch Arithmæl Circulæ, Vers 21:7

Kommentare zu Teil

Für eine Partition $\mu\vdash n$ werde ich $k\in\mu$ schreiben, wenn $\mu$ ein $k$ enthält (duh). Es sei dann $\mu\setminus k$ die Partition von $n-k$, die aus $\mu$ durch entfernen von $k$ entsteht. Um die Formel (2.3) einzusehen, wird zunächst behauptet, dass für $k\in\mu$ gilt: \[ k \cdot \frac{\partial p_\mu}{\partial p_k} \cdot \frac{|K^\mu|}{|\mu|!} = k \cdot \frac{\partial (p_{\mu_1}\cdots p_{\mu_r})}{\partial p_k} \cdot \frac{|K^\mu|}{|\mu|!} = \frac{|K^{\mu\setminus k}|}{|\mu\setminus k|!} \cdot p_{\mu\setminus k}. \] Dies ist tatsächlich recht klar, da \[ k\cdot b \cdot \frac{|K^\mu|}{|\mu|!} = \frac{|K^{\mu\setminus k}|}{|\mu\setminus k|!}, \] wenn $b$ die Multiplizität von $k$ in $\mu$ bezeichnet. Dies folgt aus (2.2). Der Faktor $b$ entsteht gerade beim Ableiten, damit ist die Formel also verifiziert. Was folgt ist etwas knapp, hier die vollständige Rechnung: \[ \begin{array}{rcl} k\cdot \frac{\partial s_\lambda}{\partial p_k} &=& \frac{1}{|\lambda|!} \sum_{|\mu|=|\lambda|} k\cdot |K^\mu|\cdot\chi_\lambda(K^\mu)\cdot \frac{\partial p_\mu}{\partial p_k} \\ &=& \sum_{|\mu|=|\lambda|} k\cdot \frac{\partial p_\mu}{\partial p_k}\cdot \frac{|K^\mu|}{|\mu|!}\cdot\chi_\lambda(K^\mu) \\ &=& \sum_{|\mu|=|\lambda|,~k\in\mu} \frac{|K^{\mu\setminus k}|}{|\mu\setminus k|!}\cdot p_{\mu\setminus k} \cdot \sum_{|\lambda'|=|\lambda|-k} a_k(\lambda,\lambda')\cdot \chi_{\lambda'}(K^{\mu\setminus k}) \\ &=& \sum_{|\lambda'|=|\lambda|-k} a_k(\lambda,\lambda')\cdot \sum_{|\mu|=|\lambda|,~k\in\mu} \frac{|K^{\mu\setminus k}|}{|\mu\setminus k|!} \chi_{\lambda'}(K^{\mu\setminus k}) p_{\mu\setminus k} \\ &=& \sum_{|\lambda'|=|\lambda|-k} a_k(\lambda,\lambda')\cdot \sum_{|\mu|=|\lambda|-k} \frac{|K^\mu|}{|\mu|!} \chi_{\lambda'}(K^\mu) p_\mu \\&=& \sum_{|\lambda'|=|\lambda|-k} a_k(\lambda,\lambda')\cdot s_{\lambda'} \end{array} \] Damit also $\langle k\cdot \partial s_\lambda/\partial p_k,\: s_\mu\rangle = a_k(\lambda,\mu)$ wie behauptet. # Wie man die Probleme mit den Algorithmen löst Nun mal angenommen, die Algorithmen machen wirklich, was sie sollen. Wie lösen wir dann die eigentlichen Probleme? Problem 1.1 Gegeben Koeffizienten $a_\lambda$ für alle $|\lambda|=n$, berechne \[ \chi := \sum_{|\lambda|=n} a_\lambda \chi_\lambda. \] Mit anderen Worten, bestimme $\sum_\lambda a_\lambda \cdot \chi_\lambda(K^\mu)$ für jedes $\mu\vdash n$. Lösung. Für zwei Partitionen $\lambda$ und $\lambda'$ bezeichnen wir mit $\langle\chi_\lambda, \chi_{\lambda'}\rangle$ das gewöhnliche Skalarprodukt der Charaktere. Wir beobachten dann, dass \[ \begin{array}{rcl} \sum_{|\lambda|=n} a_\lambda\cdot s_\lambda &=& \sum_{|\lambda|=|\lambda'|=n} \langle\chi_\lambda,\chi_{\lambda'}\rangle\cdot a_\lambda\cdot s_{\lambda'} \\&=& \sum_{|\lambda|=|\lambda'|=n}\frac{1}{n!}\cdot \left(\sum\nolimits_{|\mu|=n} |K^\mu| \chi_\lambda(K^\mu)\chi_{\lambda'}(K^\mu)\right)\cdot a_\lambda\cdot s_{\lambda'} \\ &=& \sum_{|\mu|=n} \frac{|K^\mu|}{n!} \cdot \sum_{|\lambda|=n} a_\lambda \cdot \chi_\lambda(K^\mu) \cdot \sum_{|\lambda'|=|\mu|} \chi_{\lambda'}(K^\mu) \cdot s_{\lambda'} \\ &=& \sum_{|\mu|=n} \frac{|K^\mu|}{n!} \cdot \sum\nolimits_{|\lambda|=n} a_\lambda\cdot \chi^\lambda(K^\mu) \cdot p_\mu \\ &=& \sum_{|\mu|=n} \frac{|K^\mu|}{n!} \cdot b_\mu \cdot p_\mu \end{array} \] Damit reicht es also, s_to_p für $B=\sum_\lambda a_\lambda s_\lambda$ aufzurufen, da die Ergebniskoeffizienten \[ \tilde b_\mu := \frac{|K^\mu|}{n!}\cdot b_\mu \] erfüllen und sich die gesuchten $b_\mu$ so einfach berechnen lassen. Problem 1.2 Gegeben Werte $b_\mu$, finde die Koeffizienten $a_\lambda$, so dass für $\chi=\sum_{|\lambda|=n} a_\lambda \chi_\lambda$ gilt, dass $\chi(K^\mu)=b_\mu$. Lösung. Da wir nun wissen, dass wir vermutlich p_to_s verwenden müssen, ist die Herausforderung eher gering. Beobachte: \[ \begin{array}{rcl} \sum_{|\lambda|=n} a_\lambda s_\lambda &=& \sum_{|\lambda|=n} a_\lambda \cdot \frac1{n!} \sum_{|\mu|=n} |K^\mu|\cdot \chi_\lambda(K^\mu) \cdot p_\mu \\ &=& \sum_{|\mu|=n} \frac{|K^\mu|}{n!}\cdot \left(\sum\nolimits_{|\lambda|=n} a_\lambda\cdot \chi_\lambda(K^\mu)\right) \cdot p_\mu = \sum_{|\mu|=n} \frac{|K^\mu|}{n!}\cdot b_\mu\cdot p_\mu \end{array} \] und somit rufen wir p_to_s für $A=\sum_\mu \tilde b_\mu p_\mu$ auf und erhalten die gesuchten Koeffizienten. Hierbei ist $\tilde b_\mu$ wie oben definiert. ## Ein modifizierter Algorithmus Am Ende von s_to_p wird $PD+(\int PC dp_k)/k$ zurückgegeben. Ich behaupte, diese Zeile kann leicht modifiziert werden, um einen Algorithmus zu erhalten, der $\sum_\mu b_\mu p_\mu$ anstatt von $\sum_\mu \tilde b_\mu p_\mu$ aus $\sum_\lambda a_\lambda s_\lambda$ berechnet. Die Modifikation lautet \[ \mathtt{RETURN}~~PD + p_k\cdot PC. \] Schreibe $P'C := p_k\cdot PC=\sum_{|\mu|=n} c_\mu p_\mu$, wobei $c_\mu=0$ wenn $\mu_1 > k$. Es bezeichne $\mathrm{mult}_k(\mu)$ die Häufigkeit, mit der $k$ in der Partition $\mu$ erscheint. Damit unterscheidet sich der $\mu$-te Koeffizient von $P'C$ von dem von $(\int PC dp_k)/k$ um einen Faktor von $k\cdot\mathrm{mult}_k(\mu)$. Ich erinnere daran, dass \[ |K^\mu| = \frac{n!}{\prod_k k^{\mathrm{mult}_k(\mu)}\cdot \mathrm{mult}_k(\mu)!} \] und nach unseren Überlegungen zu Problem 1 bedeutet dies, dass wir während der Rekursion in jedem Schritt verifizieren müssen, dass jeder Koeffizient einen Faktor von \[ \kappa_\mu := \prod_k k^{\mathrm{mult}_k(\mu)}\cdot \mathrm{mult}_k(\mu)! \] hinzugewinnt. In der Tat sieht man dies leicht durch Induktion. Wenn s_to_p mit $n=0$ oder $k=0$ aufgerufen wird ist die Aussage banal. Nach Induktionsvoraussetzung sind nun alle Koeffizienten von $PD$ bereits korrekt skaliert. Um die Koeffizienten von $(\int PC dp_k)/k$ zu skalieren, müssen wir gerade mit $k\cdot\mathrm{mult}_k(\mu)$ multiplizieren.