%====================================================================== % FPSAC/SFCA '94 - Open Problem % % Proposed by % Jacob Katriel email: chr09kt@technion.technion.ac.il % Department of Chemistry % Technion - Israel Institute of Technology % 32000 Haifa % Israel % % (March 6, '94) %---------------------------------------------------------------------- % Prove, improve or disprove the conjectures stated in the following % paper (LaTeX file): % %====================================================================== %macropackage=latex \documentstyle[12pt]{article} \setlength{\topmargin}{-0.8in} \setlength{\headheight}{0.5in} \setlength{\headsep}{0.55in} \setlength{\textheight}{8.5in} \setlength{\oddsidemargin}{0.25in} \setlength{\textwidth}{6.5in} \renewcommand{\baselinestretch}{0.95} \sloppy \begin{center} \large FPSAC/SFCA '94 --- Problem Submission\\ {\small March 6, 1994}\\ \medskip \medskip {\small \sl Proposed by}\\ {\small Jacob Katriel}\\ {\small Department of Chemistry} \\ {\small Technion - Israel Institute of Technology} \\ {\small Haifa 32000, Israel}\\ \medskip \medskip {\small \sl Prove, improve or disprove the conjectures}\\ {\small \sl stated in the following paper.}\\ \end{center} \title {Combinatorial algorithms concerning the class-algebra of the symmetric group} \author{ Jacob Katriel\thanks{ email: chr09kt@technion.} \\ {\small \sl Department of Chemistry} \\ {\small \sl Technion - Israel Institute of Technology} \\ {\small \sl Haifa 32000, Israel} } \date{ } \begin{document} \setcounter{page}{1} \maketitle \begin{abstract} Two related problems concerning the symmetric group class-algebra are addressed: \noindent {\bf a.} A conjecture that specifies the set of class-sums present in the product of the single-cycle class-sum $[(p)]_n$ with the arbitrary class-sum $[(1)^{\ell_1}(2)^{\ell_2}\cdots (n)^{\ell_n}]_n$, as well as the value of the coefficient of each class-sum present, is proposed. \noindent {\bf b.} A conjecture concerning the construction of explicit expressions for the central characters ({\em i.e.,} the eigenvalues of the class-sums) is presented. \vspace{3 mm} Deux probl\`emes li\'es concernant l'alg\`ebre de classe du groupe sym\'etrique sont pr\'esent\'es: \noindent {\bf a.} On propose une conjecture qui pr\'ecise l'ensemble des sommes de classes pr\'esent dans le produit de $[(p)]_n$, la somme de classe d'un seul cycle, avec une somme de classe $[(1)^{\ell_1}(2)^{\ell_2}\cdots (n)^{\ell_n}]_n$ quelconque, ainsi que la valeur du coefficient de chaque somme de classe pr\'esente. \noindent {\bf 2.} On propose une conjecture concernant la construction d'expressions explicites pour les caract\`eres centraux ({\em i.e.,} les valeurs propres des sommes de classes). \end{abstract} \vspace{4 mm} \section{Introduction} \hspace*{6 mm} The class-algebra of the symmetric group has attracted considerable attention because of its many applications in mathematics as well as in physics and chemistry. The product of a pair of class-sums $C_1$ and $C_2$ is a linear combination of class-sums $C_i$ with non-negative integral coefficients $C_1\cdot C_2\Big{|}_{C_i}$, {\em i.e.,} \begin{equation} \label{eq:product} C_1 \cdot C_2 = \sum_{C_i\in CS_n} C_1\cdot C_2\Big{|}_{C_i} \; C_i \end{equation} Most of the results obtained on this topic ([1, 6-9, 21]) use the representation theoretic relation \begin{equation} \label{eq:coef} C_1 \cdot C_2\Big{|}_{C_i}=\frac{|C_1| \, |C_2|}{n!} \sum_{\Gamma} \frac{\chi_1^{\Gamma}\chi_2^{\Gamma}\chi_i^{\Gamma}}{|\Gamma|} \; , \end{equation} where $\Gamma$ ranges over the irreducible representations of $S_n$ ({\it i.e.}, over the partitions of $n$), $\chi_i^{\Gamma}$ is the value of the irreducible character $\Gamma$ on the class $C_i$, and $|C|, \, |\Gamma|$ stand for the order of the class $C$ and the degree of the irreducible representation $\Gamma$, respectively. Several attempts were reported to derive these coefficients using their combinatorial significance [2-5, 20]. A combinatorial study of the product of the class of transpositions with an arbitrary class of the symmetric group \cite{KatPal}, followed by a similar study of the class of three-cycles \cite{Katriel1}, motivated the formulation of a conjecture concerning the form of the product of a single-cycle class-sum of arbitrary length with an arbitrary class-sum in the symmetric group algebra [11-14]. This conjecture is reviewed in sections 2-5 of the present article. The class-sums of the symmetric group form a basis for the center of the corresponding group-algebra. Their eigenvalues, denoted $\lambda_C^{\Gamma}$, are related to the characters of the ordinary irreps via \begin{equation} \lambda_C^{\Gamma} = \frac{|C|}{|\Gamma|} \chi_C^{\Gamma} \;\; . \end{equation} The eigenvalues $\lambda_C^{\Gamma}$ are sometimes referred to as the central characters. A conjecture allowing the evaluation of these central characters for arbitrary class-sums in the symmetric group is presented in sections 6-9. \section {Representation of $[(p)]_n \cdot [*]_n$ in terms of reduced class-sums} \hspace*{6 mm} The product of a class-sum with cycle-structure $[(p)]_n \equiv [(p)(1)^{n-p}]_n$ and an arbitrary class-sum $[*]_n \,\equiv\,[(1)^{\ell_1}\,(2)^{\ell_2} \ldots (n)^{\ell_n}]_n$ is given by an expression of the form: $$ [(p)]_n \cdot [*]_n = {\displaystyle\sum_{ {r_1,\, r_2,\, \cdots,\, r_p^{\phantom{\prime}}} \atop {(r_1 + r_2 + \cdots +r_p \leq n)^{\phantom{\prime}}} } ^{\phantom{ {r_1,\, r_2,\, \cdots,\, r_p^{\phantom{\prime}}} \atop {(r_1 + r_2 + \cdots +r_p \leq n)^{\phantom{\prime}}} } } } \quad {\displaystyle\sum_{ {k,\ell_{\phantom{p}} } \atop {(k+\ell +p = {\scriptstyle \rm odd})_{\phantom{p}}} } ^{\phantom{ {k,\ell_p } \atop {(k+\ell +p = {\scriptstyle \rm odd})_p} } }} \quad {\displaystyle\sum_{(p_1,\, p_2,\, \cdots ,\, p_k )\vdash p } ^{\phantom {(p_1,\, p_2,\, \cdots ,\, p_k )\vdash p }} } \quad {\displaystyle\sum_{(p_1^{\prime},\, p_2^{\prime},\, \cdots ,\, p_{\ell}^{\prime}) \vdash p } ^{\phantom {(p_1^{\prime},\, p_2^{\prime},\, \cdots ,\, p_{\ell}^{\prime}) \vdash p } } } \quad { \displaystyle\sum_{ { {\scriptstyle \rm distinct \; connected}_{\phantom{\ell}} ^{\phantom{\prime}} } \atop {\quad {\scriptstyle \rm distributions}_{\phantom{\ell}} ^{\phantom{\prime}} } } ^{\phantom{ { {\scriptstyle \rm distinct connected}_{\phantom{\ell}} ^{\phantom{\prime}} } \atop {\quad {\scriptstyle \rm distributions}_{\phantom{\ell}} ^{\phantom{\prime}} } }} } $$ \begin{eqnarray} \label{eq:classprod} C<(\overbrace{r_1 + r_2 +\cdots +r_{p_1}}^{p_1}) (\overbrace{r_{p_1 +1} + \cdots}^{p_2} )\cdots (\overbrace{\cdots +r_p}^{p_k}); (\overbrace{\cdots }^{p_1^{\prime}})(\overbrace{\cdots }^{p_2^{\prime}}) \cdots (\overbrace{\cdots}^{p_{\ell}^{\prime}})> \qquad \nonumber \\ \qquad \qquad \qquad \cdot <(\overbrace{r_1 + r_2 +\cdots +r_{p_1}}^{p_1}) (\overbrace{r_{p_1 +1} + \cdots}^{p_2} )\cdots (\overbrace{\cdots +r_p}^{p_k}); (\overbrace{\cdots }^{p_1^{\prime}})(\overbrace{\cdots }^{p_2^{\prime}}) \cdots (\overbrace{\cdots}^{p_{\ell}^{\prime}})*> \end{eqnarray} \noindent To interprete this expression we make the following remarks:\hfill\break \noindent 1. The symbol $(p_1,\, p_2,\, \cdots , p_k)\vdash p$ stands for a partition of $p$ into $k$ non-vanishing parts $p_1 \geq p_2 \geq \cdots \geq p_k >0$ $\quad (p_1 + p_2 + \cdots + p_k = p)$. \noindent 2. The expression for $[(p)]_n \cdot [*]_n$ involves a sum over $p$ positive integral indices, $ r_1,\,r_2,\, \ldots ,\, r_p$ which satisfy $ r_1+r_2+\ldots+r_p\leq n$. The summand is a linear combination of terms, each of which is a product of an operator, to which we refer as the reduced class-sum, and a corresponding rational and non-negative numerical coefficient. The numerical coefficient will be referred to as the {\bf reduced class-coefficient} ({\sc rcc}). \noindent 3. The reduced class-sum is denoted by a symbol of the form \begin{equation} \label{eq:reducedclasssum} <(\overbrace{r_1 + r_2 +\cdots +r_{p_1}}^{p_1}) (\overbrace{r_{p_1 +1} + \cdots}^{p_2} )\cdots (\overbrace{\cdots +r_p}^{p_k}); (\overbrace{\cdots }^{p_1^{\prime}})(\overbrace{\cdots }^{p_2^{\prime}}) \cdots (\overbrace{\cdots}^{p_{\ell}^{\prime}})*> \end{equation} where the asterisk indicates that the reduced class-sum operates on the class-sum $*$. The {\sc rcc} corresponding to it is denoted by prefixing the letter $C$ to the symbol denoting the reduced class-sum, and suppressing the asterisk, on which the {\sc rcc} does not depend. As the symbol suggests, the reduced class-sum and its {\sc rcc} are specified by distinct distributions of the indices $r_1,\, r_2,\, \cdots,\, r_p$ within two sets of cycles, which are separated by a semicolon in the symbol. The indices $ r_1,\,r_2, \ldots,\, r_p$ are distributed in each of the two sets of cycles in a non-repetitive way. The length of each cycle is equal to the sum of a certain subset of indices. The number of indices whose sum specifies the length of a given cycle will be referred to as this cycle's {\bf index--length}. Thus a cycle of index-length $k$, say $ (r_1 + r_2 + \cdots + r_k)$, has an actual length that is at least k (when $ r_1 = r_2 = \cdots = r_k = 1$) and at most $ n-(p-k)$ (which is possible only if $ r_{k+1} = r_{k+2} = \cdots = r_p = 1$). A cycle of index-length $k$ will be denoted by $((k))$, when convenient. \noindent 4. For a particular set of values of the indices $r_1,\, r_2,\, \cdots ,\, r_p$, the reduced class-sum, (\ref{eq:reducedclasssum}), yields a linear combination of two class-sums from the original class-sum $\ast$: In one of them, a set of cycles of the lengths specified by one of the two sets of index-sums is eliminated and a set specified by the second is inserted. The other class is generated by interchanging the roles of the two sets of cycles. If either set contains a cycle of a length that does not appear in the original class $\ast$, the term involving the elimination of that set vanishes. \noindent 5. When the two sets of indexed cycles are related to one another by means of a permutation of indices that occupy equivalent positions, the term is referred to as self-associated and is defined to operate only once on the original class $\ast$. \noindent 6. The reduced class-sum is defined so as to imply that each class generated in the procedure described above should be multiplied by $$ \prod^n_{i=1} \Bigg[ i^{\lambda_i} \cdot \lambda_i ! {{\ell_i + \lambda_i - \mu_i} \choose {\lambda_i}}\Bigg] $$ where $\lambda_i$ is the number of cycles of actual length $i$ inserted, $\mu_i$ the number of cycles of that length eliminated and $\ell_i$ the number of cycles of the same length that were present in the original class $\ast$. \noindent 7. In order to specify the set of reduced class-sums which appear in the product $ [(p)]_n \cdot [*]_n$ we note: \noindent a. A cycle of length $ \lambda_i$ has parity $ \lambda_i + 1$. The elimination of one set of cycles and the insertion of another conserves parity if the difference between the number of cycles eliminated and that of the cycles inserted is even, and reverses it if this difference is odd. Thus, the above difference should be even if $p$ is odd and odd if $p$ is even. This is the origin of the condition $k + \ell + p = {\rm odd}$, specified in eq. (\ref{eq:classprod}). \noindent b. The distributions of $r_1,\, r_2,\, \cdots ,\, r_p$ within the two sets of cycles comprising any reduced class-sum should satisfy the following connectedness property: For any partitioning of these indices into two subsets there is at least one pair of indices - one from each subset - that appears in a common cycle. \noindent We note in passing that the set of reduced class-sums specified by these two conditions is in general overcomplete ({\it cf.} \cite{Katriel2}). \noindent 8. Making use of appropriately chosen (low $n$) special cases, the {\sc rcc}s can be determined by equating the products obtained using the expressions in terms of reduced class-sums with the products obtained using the representation-theoretic relation, eqs. (\ref{eq:product}, \ref{eq:coef}). This is the procedure that was originally used to determine the {\sc rcc}s corresponding to single-cycle class-sums with $p \leq 8$ ([11-13]). An incomplete representation-free algorithm is presented below. For {\sc rcc}s in which (at least) one of the two sets consists of a single cycle of index-length $p$, a closed form expression was derived in ref. \cite{Katriel2} using a result due to Boccara \cite{Boccara2}. \noindent \section {Elimination of fully imbedded cycles of a given length} \hspace*{6 mm} Recurrence relations have been formulated for terms containing cycles consisting of indices all of which are contained in the same cycle of the complementary set ([12-14]). >From now on $r_i$ will be abbreviated to $i$ within the cycles specifying an {\sc rcc} and greek letters $\alpha,\, \beta,\, \cdots$ will be used to highlight particular sets of indices. To formulate the recurrence relations we define two cycles of the same index-length which appear on the same side of the semicolon to be equivalent if their indices are distributed in an equivalent way within the cycles on the other side of the semicolon. The simplest recurrence relation, involving the elimination of a cycle of unit index-length, is \begin{eqnarray} \label{eq:rec1} &C < (\alpha + 1 + 2 + \cdots + k) A; ~ (\alpha) B > = \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\ & = {\frac {\displaystyle k} {\displaystyle \gamma_1 (B) + 1}} \cdot {\frac {\displaystyle \gamma_k (A) + 1} {\displaystyle \gamma_{k+1} (A) + 1}} ~ C < (1 + 2 + \cdots + k) A; ~B > \nonumber \end{eqnarray} where $ \gamma_1(B)$ is the number of cycles of unit index-length in B whose indices appear in \hfill\break $ (\alpha + 1 + 2 + \cdots + k)$; \hfill\break $ \gamma_{k+1}(A)$ is the number of cycles of index-length $k+1$ in A that are equivalent to \hfill \break $ (\alpha+1+2+\cdots +k)$;\hfill\break $ \gamma_{k}(A)$ is the number of cycles of index-length $k$ that are equivalent to $ (1+2+\cdots+k)$. As was explained in ref. \cite{Katriel2}, the use of the closed form expression for the single cycle {\sc rcc}s, and of the recurrence relation for {\sc rcc}s with a cycle of unit index-length, eq. (\ref{eq:rec1}), enables the determination of all the {\sc rcc}s needed for the evaluation of the product of $ [(p)(1)^{n-p}]_n$ with any class-sum of the form $ [(q)(1)^{n-q}]_n$. If $ q < p$ it may be more efficient to evaluate the same product using the $q$-index expression for $ [(q)]_n \cdot [(p)]_n$. The recurrence relation \begin{eqnarray} &C < (\alpha + \beta + 1 + 2 + \cdots + k) A; ~ (\alpha + \beta) B > = \qquad \qquad \qquad \\ & \qquad \qquad \qquad = {\displaystyle \sum_{ k_1 \leq k_2 \atop (k_1 + k_2 = k)} } {{\displaystyle k_1 k_2} \over {\displaystyle \gamma_2(B)+1}} {\displaystyle \sum_{\tau_{k_1 ,\,k_2}(B)}} {\frac {\displaystyle \gamma_{\tau_{k_1 ,\,k_2}}(A)+1} {\displaystyle \gamma_{k+2}(A) + 1}} C < \tau_{k_1 ,\,k_2} (B) A; B > \nonumber \end{eqnarray} \noindent involves the elimination of an imbedded cycle of index-length two. The symbol $\tau_{k_1, k_2}$ stands for a pair of cycles, of index-lengths $k_1$ and $k_2$ respectively, consisting of a particular distribution of the indices $1,\; 2,\; \cdots,\; k$. The sum runs over all index distributions which yield distinct {\sc rcc}s. Note that the range of this sum depends on the manner in which the $k_1 + k_2$ indices are distributed in $B$. $\gamma_{\tau_{k_1, k_2}}(A)$ is the number of pairs of cycles on the side of the semicolon containing $A$ which are equivalent to the pair specified by $\tau_{k_1, k_2}$. Note that the same cycle can appear in more than one pair. The other factors are defined in analogy with the previous recurrence relation. Recurrence relations involving imbedded cycles of higher index-lengths have been formulated \cite{Katriel4}. \section {Elimination rules for fully bridging cycles} \hspace*{6 mm} A cycle will be referred to as fully bridging if each one of the indices specifying its length belongs to a different cycle in the complementary set. The simplest type of term involving bridging cycles is of the form \begin{equation} \label{eq:bridge} C < ( \alpha + 1 + 2 + \cdots + k) (\beta + 1^{\prime} + 2^{\prime} + \cdots + k^{\prime}) A; ~ (\alpha + \beta) B > \end{equation} By a straightforward parity argument we conclude that elimination of the indices $\alpha$ and $\beta$ leads to the {\sc rcc} $C < (1 + 2 + \cdots + k + 1^{\prime} + 2^{\prime} + \cdots + k^{\prime}) A;\, B > $. However, if the $k + k^{\prime}$ indices comprising the amalgamated cycle can be distributed in the complementary set in ways that are not equivalent to the one in our original {\sc rcc}, eq. (\ref{eq:bridge}), the following symmetrized relation \begin{eqnarray} \sum_{\tau_{1,\, 2, \, \cdots,\, k^{\prime}}(B) } ~& C < (\alpha + 1 + 2 + \cdots + k)(\beta + 1^{\prime} + 2^{\prime} + \cdots + k^{\prime}) A; ~ (\alpha + \beta) B > ~ \cdot \cr \qquad & \cdot ~ \left( \gamma_2 (B) + 1 \right) ~ \cdot ~ {{\displaystyle \gamma_{k+1,\,k^{\prime} +1} (A) + 1}\over {\displaystyle \gamma_{k + k^{\prime}} (A) + 1}} ~= \cr \nonumber \\ & ~= ~ {{\displaystyle k + k^{\prime}}\over {\displaystyle 1 + \delta_{k,\, k^{\prime}} }} C < (1 + 2 + \cdots + k + 1^{\prime} + 2^{\prime} + \cdots + k^{\prime} ) A; ~ B > \end{eqnarray} where the sum runs over the distinct distributions of $1,\,2,\,\ldots \, k,\, 1^{\prime}, \, 2^{\prime}, \,\ldots, \, k^{\prime}$ in $B$, is found to hold. Elimination of bridging cycles of higher index-length has been considered \cite{Katriel4}. \section {Simple illustrations} \hspace*{6 mm} The simplest class-sum is the sum of transpositions, $[(2)]_n$. The product of this class-sum with an arbitrary class-sum of $S_n$ is given in terms of a single reduced class-sum specified by the pair of partitions $((2))$ and $((1))^2$. This pair satisfies the parity condition $k+\ell +p = {\rm odd}$. The unique distribution $(1+2);(1)(2)$ satisfies the connectedness condition as well. Thus, \begin{equation} \label{eq:transpositions} [(2)]_n \cdot [*]_n = \frac{1}{2} {\displaystyle \sum_{ {r_1, r_2} \atop {(r_1 +r_2 \leq n)} } } < (1+2);(1)(2)* > \end{equation} where the {\sc rcc} $C<(1+2);(1)(2)>=\frac{1}{2}$ can be determined either by use of the general expression for {\sc rcc}s containing a cycle of index-length $p$ (in this case, $p=2$), or by comparison of eq. (\ref{eq:transpositions}) with the trivial relation $[(2)]_2 \cdot [(2)]_2 =1$. A combinatorial proof of eq. (\ref{eq:transpositions}) was given in \cite{KatPal}. For $p=3$ we similarly obtain \begin{eqnarray} \label{Three} [(3)]_n \cdot [*]_n = {\displaystyle \sum_{{r_1,\, r_2,\, r_3} \atop {(r_1 +r_2 +r_3 \leq n)}} } \left\{ \frac{1}{3} <(1+2+3);(1+2+3)*> + \right.\qquad \qquad \\ \qquad \left. + \frac{1}{3} <(1+2+3);(1)(2)(3)*> + <(1+2)(3);(1)(2+3)*> \right\} \nonumber \end{eqnarray} A combinatorial proof of this result was given in \cite{Katriel1}. \section{Central characters for single-cycle class-sums} \hspace*{6mm} The central characters corresponding to the single-cycle class-sums $[(p)]_n$ have been investigated in ref. \cite{Katriel10}, where they have been shown to be expressible as polynomials in the symmetric power-sums over the ``contents'' of the Young diagram specifying the irrep; the ``content'' of a box in a Young diagram being the difference between its column index $j$ and its row index $i$. These symmetric power-sums are defined as follows \begin{equation} \sigma_k = \sum_{(i,j)\in \Gamma} (j-i)^k \;\; . \end{equation} A representation-free algorithm for constructing the expressions for the central characters $\lambda_{[(p)]_n}^{\Gamma}$ of single-cycle class-sums in terms of the symmetric power-sums over the ``contents'' was proposed in ref. \cite{Katriel20}. Extensive computations using this algorithm were presented in ref. \cite{Pauncz}, where explicit expressions for the central characters corresponding to class-sums consisting of a cycle of length up to 18 were constructed. It will be convenient to denote a partition of an integer $r$ into parts none of which is less than 2 by the multi-index $[n_2,\, n_3,\, \cdots ]$, where $\sum_{i \geq 2} i\cdot n_i =r$. The set of such partitions of $r$ will be denoted by $\Psi_2(r-1)$. Using these definitions the algorithm can be formulated as follows: \noindent \begin{itemize} \item The expression for $\lambda^{\Gamma}_{[(p)]_n}$ as a polynomial in $\sigma_1,\, \sigma_2,\, \ldots ,\, \sigma_{p-1}$ is of the form \begin{equation} \label{eq:Conj1} \lambda_{[(p)]_n}^{\Gamma} = \sum_{[n_2,\, n_3,\, \cdots,\, n_{p+1} ] \; \in \; \Psi_2^{\phantom{2}} (p)} f_{\phantom{p}}^{[n_2,\, n_3,\, \cdots,\, n_{p+1}]} (n) \prod_{i=1}^{p-1} \sigma_i^{n_{i+2}} \; . \end{equation} where $f_{\phantom{p}}^{[n_2,\, n_3,\, \cdots,\, n_{p+1}]} (n)$ is a polynomial of degree $n_2$ in $n$, whose coefficients depend on $[n_2,\, n_3,\, \cdots,\, n_{p+1}]$. \noindent \item The coefficient of $\sigma_{p-1}$ in the expression for $\lambda^{\Gamma}_{[(p)]_n}$ is equal to $1$. \noindent \item {\em {Lemma}}: For $p>n$, $\lambda^{\Gamma}_{[(p)]_n}$ vanishes. \end{itemize} To obtain the expression for the central characters corresponding to the single-cycle class-sum $[(p)]_n$ one should first obtain the form of the corresponding expression and then determine the values of the coefficients in the polynomials $f_{\phantom{p}}^{[n_2,\, n_3,\, \cdots,\, n_{p+1}]} (n)$ by constructing and solving an appropriate system of linear equations. The central characters of the first four single-cycle class-sums are \begin{equation} \label{eq:two} \lambda_{[(2)]_n}^{\Gamma} = \sigma_1 \end{equation} \begin{equation} \label{eq:three} \lambda_{[(3)]_n}^{\Gamma} = \sigma_2-\frac{1}{2}n(n-1) \end{equation} \begin{equation} \lambda_{[(4)]_n}^{\Gamma} = \sigma_3-(2n-3)\sigma_1 \end{equation} \begin{equation} \label{eq:five} \lambda_{[(5)]_n}^{\Gamma} = \sigma_4-(3n-10)\sigma_2-2\sigma_1^2 +\frac{1}{6}n(n-1)(5n-19) \end{equation} The first two, eqs. \ref{eq:two} and \ref{eq:three}, had been derived by Jucys \cite{Jucys} and by Suzuki \cite{Suzuki}. \section{Central characters for multi-cycle classes, using the class-algebraic relations} \hspace*{6mm} It had been shown by Kramer \cite{Kramer} that the single-cycle class-sums form polynomial generators of the center of the group-algebra of the symmetric group. An immediate implication is that the expressions for the central characters of arbitrary class-sums in the symmetric group can be expressed as polynomials in the expressions for the central characters corresponding to single-cycle class-sums. The explicit construction of these expressions depends on the algebraic relations satisfied by the various class-sums. More specifically, expressions for products of class-sums in terms of linear combinations of class-sums are needed. The combinatorial derivation of such expressions was presented in sections 2-5. Applying just the expressions for the products of the class of transpositions, eq. \ref{eq:transpositions}, and of the class of three-cycles, eq. \ref{Three}, we obtain the following relations $$[(2)]_n\cdot [(2)]_n = 2[(2)^2]_n +3[(3)]_n +\frac{1}{2}n(n-1) I_n$$ $$[(2)]_n\cdot [(3)]_n = [(2)(3)]_n +4[(4)]_n +2(n-2)[(2)]_n$$ $$[(2)]_n\cdot [(4)]_n = [(2)(4)]_n +5[(5)]_n +4[(2)^2]_n + 3(n-3)[(3)]_n$$ $$[(3)]_n\cdot [(3)]_n =2 [(3)^2]_n +5[(5)]_n +8[(2)^2]_n +(3n-8)[(3)]_n+\frac{1}{3}n(n-1)(n-2) I_n$$ \noindent where $I_n$ is the class of the identity. Using these expressions to construct expressions for multi-cycle class-sums in terms of single-cycle class-sums, along with the expressions for the central characters for the single-cycle class-sums, eqs. \ref{eq:two}-\ref{eq:five}, we obtain the following expressions for central characters corresponding to multi-cycle class-sums: \begin{equation} \label{eq:twotwo} \lambda_{[(2)^2]_n}^{\Gamma} =\frac{1}{2} \sigma_1^2 -\frac{3}{2}\sigma_2 +\frac{n(n-1)}{2} \end{equation} \begin{equation} \lambda_{[(2)(3)]_n}^{\Gamma} = \sigma_1 \sigma_2 -4 \sigma_3 -\frac{n^2-13n+16}{2}\sigma_1 \end{equation} \begin{equation} \lambda_{[(2)(4)]_n}^{\Gamma} = \sigma_1 \sigma_3 -5 \sigma_4 -(2n-11) \sigma_1^2 +(12n-35)\sigma_2 -\frac{4}{3}n(n-1)(2n-7) \end{equation} \begin{equation} \lambda_{[(3)^2]_n}^{\Gamma} =\frac{1}{2} \sigma_2^2 -\frac{5}{2}\sigma_4 -\frac{1}{2}(n^2-13n+30)\sigma_2 + 3\sigma_1^2 +\frac{1}{8} n(n-1)(n^2-13n+34) \end{equation} \section{A conjectured algorithm for arbitrary central \hfill\break characters} \hspace*{6mm} The algorithm presented in section 6 for the representation-free construction of the expressions for the central characters corresponding to single-cycle class-sums will now be generalized to arbitrary class-sums. A class-sum in $S_n$ is specified by a $k$-tuple of cycle-lengths $p_1,\, p_2,\, \cdots ,\, p_k$, none of which is less than 2. To obtain the expression for the corresponding central characters we construct all the partitions of $\{ 1,\, 2,\, \cdots ,\, k \}$ into $\ell$ (disjoint) sets $S_1 ,\; S_2 ,\, \cdots ,\, S_{\ell}$ where $1 \leq \ell \leq k$ and $S_1 \cup S_2 \cup \cdots \cup S_{\ell} = \{1,\, 2,\, \cdots ,\, k \}$. For each of these partitions we define an $\ell$-fusion of $p_1,\, p_2,\, \cdots ,\, p_k$ as an $\ell$-tuple $(\rho_1,\, \rho_2,\, \cdots ,\, \rho_{\ell})$ where $\rho_i = 2+ \sum_{j \in S_i} (p_j -1)$. The set of $\ell$-fusions of $p_1,\, p_2,\, \cdots ,\, p_k$ is denoted by $\psi_{\ell}(p_1,\, p_2,\, \cdots ,\, p_k)$. For each one of the integers $\rho_i$ belonging to an $\ell$-fusion we form all the partitions into parts none of which is less than 2, that are specified by the multi-indices $[n_2^{(i)},\, n_3^{(i)},\, \cdots ]$, defined in the Introduction. A multi-partition of the $\ell$-tuple $\rho_1,\, \rho_2,\, \cdots ,\, \rho_{\ell}$ is formed by summing the multi-indices corresponding to a set of $\ell$ partitions of the $\ell$ components $\rho_1,\, \rho_2,\, \cdots ,\, \rho_{\ell}$, entrywise, $$[n_2,\, n_3,\, \cdots ] = [\sum_{i=1}^{\ell} n_2^{(i)},\, \sum_{i=1}^{\ell} n_3^{(i)},\, \cdots ] \;\; .$$ The set of (distinct) multi-partitions of the $\ell$-tuple $\rho_1,\, \rho_2,\, \cdots,\, \rho_{\ell}$ is denoted by \hfill\break $\Phi_2(\rho_1,\, \rho_2 ,\, \cdots ,\, \rho_{\ell})$. We now form the ensemble of multi-partitions corresponding to all possible fusions of the $k$-tuple $(p_1,\, p_2,\, \cdots,\, p_k)$, $${\tilde{\Psi}}_2^{\phantom{2}} (p_1,\, p_2,\, \cdots,\, p_k)= \bigcup_{\ell=1}^k \;\;\; \bigcup_{{(\rho_1,\rho_2,\cdots ,\rho_{\ell}) {\phantom{space}} }\atop { {\phantom{space}} \in \psi_{\ell}^{\phantom{l}}(p_1, p_2, \cdots ,p_k) }} \Phi_2(\rho_1,\rho_2,\cdots ,\rho_{\ell}) \;\; .$$ The reduced ensemble of multi-partitions, denoted by $\Psi_2^{\phantom{2}} (p_1,p_2,\cdots ,p_k)$, is obtained from ${\tilde{\Psi}}_2^{\phantom{2}} (p_1,\, p_2,\, \cdots,\, p_k)$ by retaining only the multi-partition with the largest value of $n_2$ within each subset of multi-partitions with common $(n_3,\, n_4,\, \cdots)$. The conjectures and the Lemma presented in section 6 are generalized into: \begin{itemize} \item \noindent The expression for the central characters corresponding to a class consisting of $k$ cycles of lengths $p_1,\; p_2 ,\; \cdots ,p_k$, with $n-\sum_{i=1}^k p_i$ fixed-points (cycles of unit-length), is of the form \begin{equation} \lambda_{[(p_1)(p_2)\cdots(p_k)]_n}^{\Gamma} = \sum_{[n_2,\, n_3,\, \cdots] \in \Psi_2(p_1,\, p_2,\, \cdots ,\, p_k)} f^{[n_2,\, n_3,\, \cdots]}(n) \cdot \prod_{i \geq 2} \sigma_i^{n_{i+2}} \end{equation} where $f^{[n_2,\, n_3,\, \cdots]}(n)$ is a polynomial in $n$ of degree $n_2$. \noindent \item The coefficient of the term $\prod_{i=1}^k \sigma_{p_i -1}$ in the expression for the central characters corresponding to the class specified by the cycle lengths $p_1 ,\, p_2 ,\, \cdots ,\, p_k$ is $\Big( \prod_{m\geq 3} \nu_m! \Big)^{-1}$, where $\nu_m = \sum_{i=1}^{k} \delta (p_i, m) \;\; (m \geq 2)$ and $\delta(p_i,m)$ is Kronecker's delta. \noindent \item The expression for the central character vanishes when it is evaluated with respect to an irrep whose Young diagram consists of a smaller number of boxes than $\sum_{i=1}^k p_i$. \end{itemize} \section{An illustrative example of the application of the \hfill\break algorithm} \hspace*{6mm} For a class-sum consisting of two cycles of lengths $p_1$ and $p_2$ we have to consider the 1-fusion with $S_1=\{1,\, 2\}$ and the 2-fusion with $S_1=\{1\}$ and $S_2=\{2\}$. The former gives rise to $\rho_1=p_1 +p_2$, whereas the latter gives rise to $\rho_1=p_1 + 1$ and $\rho_2=p_2+1$. Thus, for $p_1 = p_2 = 2$ we have to consider multi-partitions of $(4)$ and of $(3,3)$ into parts none of which is less than $2$. The (reduced) ensemble of multi-partitions is $\{[n_3=2],\, [n_4=1],\,[n_2=2]\}$, giving rise to the following expression for the corresponding central characters $$\lambda_{[(2)^2]}^{\Gamma} = \alpha_0^{[n_3=2]} \sigma_1^2 + \alpha_0^{[n_4=1]} \sigma_2 + (\alpha_2^{[n_2=2]} n^2 + \alpha_1^{[n_2=2]} n + \alpha_0^{[n_2=2]}) \; .$$ >From the conjectures formulated in section 8 it follows that $\alpha_0^{[n_3=2]}=\frac{1}{2}$ and that the expression specified above should vanish for all Young diagrams with less than 4 boxes. Thus, for $n=0$ we obtain $\alpha_0^{[n_2=2]} = 0$ and for $n=1$ $\alpha_1^{[n_2=2]}=- \alpha_2^{[n_2=2]}$. For the irrep {\bf [2]} $\sigma_1=\sigma_2=1$, hence $\frac{1}{2}+\alpha_0^{[n_4=1]} +2\alpha_2^{[n_2=2]} =0$, and for the irrep {\bf [2,1]} $\sigma_1=0$ and $\sigma_2=2$, hence $2\alpha_0^{[n_4=1]} + 3\cdot 2 \alpha_2^{[n_2=2]} =0$. Thus, $\alpha_2^{[n_2=2]}=\frac{1}{2}$ and $\alpha_0^{[n_4=1]}= -\frac{3}{2}$. This is in agreement with eq. \ref{eq:twotwo}. \vfill\eject \noindent \begin{thebibliography}{99} \bibitem{Goupil3} F. B\'edard and A. Goupil, {\it Can. Math. Bull.} {\bf 35} (1992) 152. \bibitem{Bertram} E. A. Bertram and V. K. Wei, {\it SIAM J. Alg. Disc. Meth.} {\bf 1} (1980) 450. \bibitem{Boccara1} G. Boccara, {\it Discrete Math.} {\bf 23} (1978) 189. \bibitem{Boccara2} G. Boccara, {\it Discrete Math.} {\bf 29} (1980) 105. \bibitem{Boccara3} G. Boccara, {\it Discrete Math.} {\bf 38} (1982) 129. \bibitem{Goupil1} A. Goupil, {\it Discrete Math.} {\bf 79} (1989/90) 49. \bibitem{Goupil2} A. Goupil, {\it J. Combinatorial Theory A} in press. \bibitem{Jackson} D. M. Jackson, {\it Trans. Amer. Math. Soc.} {\bf 305} (1988) 317. \bibitem{James} G. James and A. Kerber, {\it The Representation Theory of the Symmetric Group,} \hfill \break Addison-Wesley, Reading, MA. 1981. \bibitem{Jucys} A. A. Jucys, {\it Rep. Math. Phys.} {\bf 5} (1974) 107. \bibitem{Katriel1} J. Katriel, {\it Int. J. Quantum Chem.} {\bf 35} (1989) 461. \bibitem{Katriel2} J. Katriel, {\it Int. J. Quantum Chem.} {\bf 39} (1991) 593. \bibitem{Katriel3} J. Katriel, {\it Israel J. Chem.} {\bf 31} (1991) 287. \bibitem{Katriel4} J. Katriel, {\it Int. J. Quantum Chem.} {\bf 47} (1993) 243. \bibitem{Katriel10} J. Katriel, {\it J. Phys. A} {\bf 24} (1991) 5227. \bibitem{Katriel20} J. Katriel, {\it J. Phys. A} {\bf 26} (1993) L 135. \bibitem{KatPal} J. Katriel and J. Paldus, in {\it Group Theoretical Methods in Physics} R. Gilmore, Ed., World Scientific, Singapore, 1987. pp. 503-506. \bibitem{Pauncz} J. Katriel and R. Pauncz, {\it Intern. J. Quantum Chem.} {\bf 48} (1993) 125. \bibitem{Kramer} P. Kramer, {\it Z. Naturforsch.} {\bf 21A} (1966) 657. \bibitem{Machi} A. Mach\'i, {\it Europ. J. Combinatorics} {\bf 13} (1992) 273. \bibitem{Stanley} R. P. Stanley, {\it Discrete Math.} {\bf 37} (1981) 255. \bibitem{Suzuki} M. Suzuki, {\it Proc. Symp. on Pure Mathematics}, American Mathematical Society, \hfill\break Providence, RI, Vol. {\bf 47} (1987) 317. \end{thebibliography} \end{document}