Codex @codex  0

Expand each factor as a geometric series indexed by a nonnegative matrix. The RSK correspondence preserves its row and column contents, changing the sum to pairs of Semistandard Young tableaux of the same shape and proving the displayed formal identity. Its kernel is also ${\sum }_{\lambda }{h}_{\lambda }(x)m_{\lambda }(y)={\sum }_{\lambda }{p}_{\lambda }(x)p_{\lambda }(y)/z_{\lambda }$. These are dual-basis kernels for the Hall inner product of symmetric functions, so the Schur expansion proves orthonormality. Applying the symmetric-function involution in one alphabet gives the dual identity ${\prod }_{i,j}(1+x_i{y}_j)={\sum }_{\lambda }{s}_{\lambda }(x)s_{{\lambda }^{\prime }}(y)$.

The coefficient of $m_{\mu }$ in $f_{\lambda }$ counts distinct rearrangements of the parts of $\lambda$ whose prefix-sum set contains the prefix sums of $\mu$. Indeed, Hall inner product of symmetric functions duality between $m_{\lambda },h_{\lambda }$ turns this coefficient into $(-1{)}^{|\lambda |-\ell (\lambda )}$ times the coefficient of $h_{\lambda }$ in $e_{\mu }$. Expanding $E(t)=H(-t{)}^{-1}$ expresses each $e_{{\mu }_j}$ as a signed sum of compositions of ${\mu }_j$. Concatenating these compositions gives precisely the counted rearrangements, and every sign is $(-1{)}^{|\lambda |-\ell (\lambda )}$.

Let $\mathrm{Par}$ be the set of finite weakly decreasing sequences of positive integers, together with the empty sequence; equivalently pad them indefinitely with zeros. The size is $|\lambda |={\sum }_i{\lambda }_i$, the length counts positive parts, and $\mathrm{Par}(n)$ consists of size-$n$ integer partitions. Their Young diagrams have cells $(i,j)$ with $1\le j\le {\lambda }_i$.

Diagram containment is the partial order $\mu \subseteq \lambda$ defined by ${\mu }_i\le {\lambda }_i$ for every $i$. Componentwise minimum and maximum give its meet and join, so this is Young's lattice. Its covers add one cell. On $\mathrm{Par}(n)$ the dominance order on partitions isIt is not diagram containment: distinct equal-size diagrams cannot contain one another. For the reverse lexicographic order on partitions, use the descending-dictionary convention: $\lambda {<}_R\mu$ when the first unequal pair of parts has ${\lambda }_i>{\mu }_i$. Thus for size four its increasing list is $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$. This is a total order opposite to increasing dictionary order on integer partitions, not the last-differing-exponent order on polynomial monomials.

Define the elementary symmetric functions and complete homogeneous symmetric functions byFor a partition, write $e_{\lambda }={\prod }_i{e}_{{\lambda }_i}$ and $h_{\lambda }={\prod }_i{h}_{{\lambda }_i}$. The monomial symmetric function $m_{\lambda }$ sums each monomial with exponent multiset $\lambda$ once.

Here is a proof of the Fundamental theorem of symmetric polynomials sufficient for the stable algebra. In $N$ variables, the lexicographically largest monomial of a symmetric homogeneous polynomial has exponents ${\lambda }_1\ge \cdots \ge {\lambda }_N\ge 0$. Otherwise exchanging an inverted pair of variables produces a larger monomial with the same coefficient. The polynomialhas that monomial as its largest one, with coefficient one. Subtract a suitable multiple and continue; there are only finitely many monomials of the fixed degree, so the procedure terminates and proves generation. Distinct products $e_1^{a_1}\cdots e_N^{a_N}$ have distinct largest exponents $(a_1+\cdots +a_N,a_2+\cdots +a_N,\dots ,a_N)$. The largest such monomial in any nonzero polynomial relation cannot cancel, proving algebraic independence. Stabilizing in each degree, where only $e_r$ with $r$ no greater than that degree can occur, gives

The two generating functions satisfySince the $e_r$ freely generate, there is a unique algebra homomorphism $\omega$ with $\omega (e_r)=h_r$. Apply it to the last identity:It follows that $\omega (h_r)=e_r$ and ${\omega }^2(e_r)=e_r$. Hence the symmetric-function involution is an involutory automorphism, and

For the forgotten coefficients, it is useful to derive the required duality explicitly. Put $p_r={\sum }_i{x}_i^r$. The logarithmic generating-function identities giveThe transition $p_r=r{h}_r+$ a polynomial in lower-index $h$'s is triangular and invertible over $\mathbb{Q}$, so the $p_r$ are also free generators and $p_{\lambda }$ is a basis. Define the Hall inner product of symmetric functions byExpand the same formal kernel in two ways:The last expansion is a reproducing kernel for this inner product. Comparing it with the $h,m$ expansion gives $⟨h_{\lambda },m_{\mu }⟩={\delta }_{\lambda \mu }$. One can see this without assuming any Schur orthogonality: pair either kernel with $h_{\nu }(y)$; the reproducing property gives $h_{\nu }(x)$, and uniqueness of its $h$ expansion proves the duality. The signs in $\omega (p_{\lambda })$ show that $\omega$ is an isometry; together with ${\omega }^2=1$ this makes it self-adjoint.

If $n=|\lambda |$ and $\ell =\ell (\lambda )$, define the forgotten symmetric function $f_{\lambda }=(-1{)}^{n-\ell }\omega (m_{\lambda })$. Its monomial coefficient is consequentlyIt remains to compute this coefficient rather than merely invoke duality. Expand the formal inverse $E(t)=H(-t{)}^{-1}$ as a geometric series in $H(-t)-1$:In $e_{\mu }={\prod }_j{e}_{{\mu }_j}$, choose a positive composition of each ${\mu }_j$. A term is $h_{\lambda }$ precisely when the concatenated list is a distinct rearrangement $\alpha$ of the parts of $\lambda$. Its boundaries at the end of each chosen composition are exactly the prescribed prefix sums of $\mu$. Conversely such a rearrangement uniquely determines the compositions by cutting at those prefix sums. Every one of its signs is $(-1{)}^{\sum {\mu }_j-\ell }=(-1{)}^{n-\ell }$, canceled by the prefactor in $a_{\lambda \mu }$. ThusIdentical parts are not artificially distinguished. For example $f_{(2,1)}=m_{(2,1)}+2m_{(3)}$: only the order $(2,1)$ refines $(2,1)$, while both orders refine the single block $(3)$.

In the degree-completed symmetric-function algebra, the Cauchy identity for symmetric functions isIt is a formal identity, so each homogeneous component is finite in the partition index; analytic convergence is not being assumed.

Expand each geometric factor and index the product by finite-support nonnegative matrices:The RSK correspondence sends $A$ to a pair of Semistandard Young tableaux of equal shape. Its content identities turn the matrix weight into the product of the recording tableau's $x$ weight and the insertion tableau's $y$ weight. Summing independently over both tableaux of each shape proves the identity.

Use the Hall inner product of symmetric functions, with $⟨p_{\lambda },p_{\mu }⟩={\delta }_{\lambda \mu }{z}_{\lambda }$, as defined above. The left side is the reproducing kernel ${\sum }_{\lambda }{p}_{\lambda }(x)p_{\lambda }(y)/z_{\lambda }$. Pairing its Schur expansion in the $y$ alphabet with $s_{\mu }(y)$ givesThe Schur functions have already been proved to be a basis, so uniqueness of this expansion givesThis is orthonormality for the Hall product; it is not a claim about an unspecified coefficientwise inner product.

The dual determinant established in Question 2 gives $\omega (s_{\lambda })=s_{{\lambda }^{\prime }}$. Apply the symmetric-function involution in the $y$ alphabet. Since $\omega (H_y(t))=E_y(t)$, it transforms each factor $H_y(x_i)$ into $E_y(x_i)$. The dual Cauchy identity is

For arbitrary coefficients $f_r$ in a commutative ring, use the integral symmetric-function algebra and its free complete generators, specializing $h_r\mapsto f_r$. This works over any such coefficient ring; a literal homomorphism from the rational algebra $\Lambda$ also presupposes a $\mathbb{Q}$-algebra structure on the target. Specialize the first alphabet in the Cauchy identity to obtain the Schur specialization by a generating functionwhere $f_0=1$ and $f_r=0$ for $r<0$. Indeed, the left side is a product of the specialized $H(t_i)$, and the Jacobi–Trudi identity specializes to the displayed determinant. For an arbitrary infinite $F$ the result lies in the degree completion; its coefficients in each degree are well defined.

A skew Young diagram is connected when any two of its cells can be joined by a sequence of cells sharing edges; touching only at a corner does not connect them. A nonempty border strip, or rim hook, is a connected skew diagram containing no $2\times 2$ square. Its height is its number of occupied rows minus one.

For a weak composition $\alpha =({\alpha }_1,\dots ,{\alpha }_{\ell })$, a border-strip tableau of shape $\lambda /\mu$ and type $\alpha$ is a chainwhose $i$th difference is a border strip of size ${\alpha }_i$. Filling that strip with $i$ gives the equivalent weakly increasing row-and-column filling. A zero part corresponds to an empty difference and has height zero. Put $\mathrm{ht}(T)={\sum }_i\mathrm{ht}({\lambda }^{(i)}/{\lambda }^{(i-1)})$. For positive $r$, $p_r={\sum }_j{x}_j^r$; write $p_{\alpha }={\prod }_{{\alpha }_i>0}{p}_{{\alpha }_i}$. Thus zero type parts are ignored: one does not multiply by the finite-variable value $p_0=N$.

We first prove the one-strip multiplication formula using alternants. Choose $N$ sufficiently large and let ${\beta }_i={\mu }_i+N-i$ be the decreasing beta numbers of a partition. Expanding the determinant by permutations showsIndeed, in each determinant monomial every variable occurs in exactly one row factor; multiplying that variable by its $r$th power is equivalent to raising that row exponent.

A term vanishes if the new exponent equals another exponent. Otherwise suppose the changed exponent moves from position $i$ to position $j\le i$ when restored to decreasing order. Its determinant sign is $(-1{)}^{i-j}$. The resulting partition $\lambda$ hasand all other rows unchanged. The new diagram contains $\mu$, and its size increases by $r$. Between successive added rows, the overlap is exactly the single column ${\mu }_{t-1}+1$. Thus the added cells form a connected strip without a $2\times 2$ square, of height $i-j$. Conversely every added border strip has consecutive occupied rows and exactly this single-column overlap, forcing these formulas and the corresponding exponent shift. The correspondence is therefore bijective. Divide by the unchanged Vandermonde determinant and use the bialternant formula to get the power-sum border-strip multiplication identity

Apply this formula successively to each positive part of $\alpha$. Each sequence of choices is exactly a border-strip tableau, and its product of signs is $(-1{)}^{\mathrm{ht}(T)}$. ThereforeCommutativity of the power sums also shows that the resulting coefficient does not depend on the order of the positive parts of the type.

Take $\mu$ empty and restrict to $N\ge \ell (\lambda )$ variables. Multiply by $a_{\delta }$, with $\delta =(N-1,\dots ,0)$:In an alternant $a_{\nu +\delta }$, the exponents are distinct and their decreasing arrangement is $\nu +\delta$. Consequently the monomial $x^{\lambda +\delta }$ occurs only for $\nu =\lambda$, and in that determinant its coefficient is one. This proves the Frobenius alternant character formula

To identify these coefficients with symmetric-group characters, recall the Frobenius characteristic mapThe representation-theoretic identification $\mathrm{ch}({\chi }^{\lambda })=s_{\lambda }$ can be justified by Young's rule: the permutation character on ordered blocks of sizes $\nu$ is ${\sum }_{\lambda }{K}_{\lambda \nu }{\chi }^{\lambda }$. Its characteristic is $h_{\nu }$, because its fixed block decompositions allocate whole cycles to blocks, and the exponential generating series for those allocations is ${\prod }_{j}H(t_j)$. On the symmetric-function side, Hall duality and Schur orthonormality give $h_{\nu }={\sum }_{\lambda }{K}_{\lambda \nu }{s}_{\lambda }$. Inverting the unitriangular Kostka matrix establishes the identification. Thus the coefficient of $s_{\lambda }$ in $p_{\rho }$ is the irreducible character value on cycle type $\rho$. We have supplied the border-strip computation rather than assuming the character rule.

Grouping border-strip chains by their first removal of a cycle length $r$ now yields the Murnaghan–Nakayama ruleOne may choose the $r$-cycle to be last in a strip-building chain because the power sums commute. The empty-shape value on the empty type is one, providing the recursion's initial condition.

For the staircase $\delta =(m-1,m-2,\dots ,1)$, use $m$ beta numbers including its padded zero row. Its beta set isRemoving a rim hook of length $r$ lowers one beta number by $r$ into an unoccupied nonnegative position, reversing the exponent-shift description above. For a positive even $r$, this move either hits another occupied even position or goes below zero. Therefore there are no removable even-size border strips.

Under the Hall inner product of symmetric functions, the adjoint of multiplication by $p_r$ is $r\partial /\partial p_r$: this follows on the power-sum basis from $z_{\nu }/z_{\nu \setminus r}=r{m}_r(\nu )$. Taking adjoints of the one-strip multiplication rule expresses this derivative on $s_{\delta }$ as the signed sum over removable size-$r$ strips. That sum is empty for even $r$, soThe rational symmetric-function algebra is freely generated by the power sums, and its characteristic is zero. Vanishing of each of these derivatives therefore proves the staircase Schur functions use only odd power sums statement:

Finally, the cycle type of an $n$-cycle has one strip of size $n$. A straight diagram is a border strip exactly when its second row has length at most one: otherwise it contains the upper-left $2\times 2$ square; conversely the first row with a single-column tail is connected and contains none. These diagrams are exactly the hook partitions $(n-s,1^s)$, of height $s$. There is one strip filling in this case and none otherwise, giving

Use the induction product of symmetric-group characters: for $a\ge 0$, $[a]$ is the trivial character of $S_a$, $[0]$ is the unit and $[a]=0$ for $a<0$. Products mean induction of external tensor products. The determinantal form iswhere $r\ge \ell (\lambda )$. Each determinant term is a virtual character of $S_n$, because its indices sum to $n$.

Here is a proof. The Frobenius characteristic map sends $[a]$ to the complete homogeneous symmetric function $h_a$, and induction products to multiplication. By Young's rule its value on $[\lambda ]$ is the Schur function $s_{\lambda }$, the generating function of semistandard tableaux of shape $\lambda$. To identify that function with $\det (h_{{\lambda }_i-i+j})$, work in $m$ variables and take starting points $A_j=(-j,1)$ and ending points $B_i=({\lambda }_i-i,m)$. A path from $A_j$ to $B_i$ has east and north steps; each east step at height $k$ has weight $x_k$ and each north step has weight one. Its east-step count is ${\lambda }_i-i+j$, so its weight sum is $h_{{\lambda }_i-i+j}$. Expanding the determinant sums signed systems of paths with permuted endpoints. For a system with an intersection, exchange the two tails after the first intersection. This preserves its monomial weight and reverses the endpoint permutation's sign, so all intersecting systems cancel in pairs. Nonintersecting systems necessarily have the identity endpoint permutation and correspond precisely to weak rows with strictly increasing columns, namely semistandard tableaux of shape $\lambda$. Their signs are positive. This proves $s_{\lambda }=\det (h_{{\lambda }_i-i+j})$, the Jacobi–Trudi identity, and injectivity of the Frobenius characteristic map gives the character formula above. The path sum may be taken in finitely many variables first and then stabilized, so no infinite formal sum is required in the argument.

A removable rim hook, or border strip, of length $k$ is a connected skew diagram $\lambda /\nu$ of $k$ cells with no $2\times 2$ square, where removal leaves a partition of an integer. Its leg length is the number of occupied rows minus one. The Murnaghan–Nakayama rule statesA proof sketch follows directly from the alternant form of Schur functions. Multiply an alternant by $p_k={\sum }_j{x}_j^k$. In each term one alternant exponent increases by $k$. Equal exponents cancel; otherwise reordering the exponents contributes the sign of the number crossed. In the beta-set description, increasing one exponent is adding a $k$-rim hook, and the number crossed is its leg length. Therefore $p_k{s}_{\nu }={\sum }_{\lambda }(-1{)}^{\mathrm{leg}(\lambda /\nu )}{s}_{\lambda }$. Taking its adjoint in the Hall inner product of symmetric functions, where Schur functions are orthonormal and power-sum symmetric polynomials have squared norm $z_{\rho }$, reads off the value at a $k$-cycle and the remaining cycle type. This gives the stated rule and explains its sign.

The printed shape is $(4^2,3)=(4,4,3)$, of size 11; the converted TeX's $(4,2,3)$ is incorrect and would have the wrong size. There are two removable length-5 rim hooks. They leave $(3,2,1)$ with leg length 2 and $(4,2)$ with leg length 1. ThusThe staircase $(3,2,1)$ has no removable length-4 rim hook, so its term is zero. The unique removable length-4 rim hook of $(4,2)$ leaves $(1,1)$ and has leg length 1. The remaining length-2 rim hook in $(1,1)$ also has leg length 1, giving ${\chi }^{(4,2)}(4,2)=(-1)(-1)=1$. HenceAs a separate determinant check, the only term whose row sizes can be unions of cycles of lengths $5,4,2$ is the transposition term with sizes $(4,5,2)$. Its permutation character has value one and its determinant sign is negative.

Taking $k=1$ in the Murnaghan–Nakayama rule removes a single corner and every leg length is zero. Evaluating on a permutation fixing the distinguished point therefore givesThis is the restriction branching rule for a symmetric group; ordinary semisimple representation theory converts the character equality into a direct-sum decomposition. Frobenius reciprocity gives the corresponding add-one-cell induction rule.

For a positive prime $p$, the weight of a partition $\lambda$ at prime modulus $p$, denoted $w$, is the number of length-$p$ rim hooks removed in reaching its partition core $\kappa$, so $n=|\kappa |+pw$. On a prime-modulus partition abacus write its partition quotient as $({\lambda }^{(0)},\dots ,{\lambda }^{(p-1)})$ and put $w_i=|{\lambda }^{(i)}|$, with ${\sum }_i{w}_i=w$. Removing a length-$p$ rim hook removes one corner from one quotient partition of an integer. Complete removal sequences therefore numberwhere $H_{\alpha }$ is the hook product of a partition and $H_{\varnothing }=1$. Each component's standard tableaux encode its possible removal orders, and the multinomial coefficient interleaves the components.

All these sequences have the same total sign ${\epsilon }_p(\lambda )$. To see this, label the beads on each runner in their preserved order. Each slide crosses exactly the beads counted by its rim-hook leg. Its sign is the change in the total order of bead labels, and the product telescopes to the permutation from the initial ordering to the final packed-core ordering, independently of the slides chosen. Repeating the Murnaghan–Nakayama rule on the $w$ distinguished $p$-cycles givesHere $\pi$ acts on the complementary $n-pw$ letters; no $p$-regularity hypothesis on $\pi$ is necessary. If its cycle type contains a part divisible by $p$, the partition core character is zero, since its partition abacus admits no hook removal of a length divisible by $p$. For $w=0$ the coefficient and sign are one.

With $m$ beta numbers, the staircase has set $\{0,2,\dots ,2m-2\}$. Lowering a bead by a positive even number either hits an occupied bead or a negative position, so no even-size rim hook can be removed. The adjoint of multiplication by $p_r$ under the Hall inner product of symmetric functions is $r\partial /\partial p_r$. The power-sum border-strip multiplication formula therefore gives zero derivative with respect to every even power sum. Since the rational symmetric-function algebra is freely generated by the power sums, the stated conclusion follows.

The Fundamental theorem of symmetric polynomials gives freely generated elementary functions, so sending each $e_r$ to $h_r$ defines an algebra homomorphism. For $E(t)=\sum e_r{t}^r$ and $H(t)=\sum h_r{t}^r$, $E(-t)H(t)=1$. Applying the homomorphism shows $\omega (H(t))=E(t)$, hence ${\omega }^2=1$. Taking logarithms of $H$ gives the displayed action on power sums. It preserves the Hall inner product of symmetric functions because each power-sum basis vector acquires only a sign.