Composition factors and representation stability

In 2017, my advisor asked me to compute a family of coefficients $c_{\lambda\mu}$ arising in the study of the Johnson homomorphism of the mapping class group.

Their connection with mapping class groups is not essential to this story. Instead, I want to describe how to compute them efficiently, and how expanding the range of computation revealed hints of a deeper structure among the coefficients.¹

Plethysms afoot

So, briefly, what are the coefficients $c_{\lambda\mu}$?

Recall that, given a partition $\lambda\vdash n$, the Schur functor $\mathbb S_\lambda$ assigns to a vector space $V$ the image of a Young symmetrizer acting on $V^{\otimes n}$. Two familiar examples are the symmetric powers $\mathbb S_{(n)}(V)=\operatorname{Sym}^n(V)$ and exterior powers $\mathbb S_{(1^n)}(V)=\bigwedge^n V$.

The free Lie algebra $\mathcal L(V)$ is the Lie algebra generated by $V$, subject only to antisymmetry and the Jacobi identity. It has a natural grading

$$\mathcal L(V)=\bigoplus_{n\geq 1}\mathcal L_n(V),$$

where $\mathcal L_n(V)$ consists of Lie expressions involving exactly $n$ inputs from $V$.

We are interested in the coefficients $c_{\lambda\mu}$ defined by the decomposition

$$\mathbb S_\mu\bigl(\mathcal L(V)\bigr) \cong \bigoplus_\lambda \mathbb S_\lambda(V)^{\oplus c_{\lambda\mu}}.$$

In other words, $c_{\lambda\mu}$ is the multiplicity of $\mathbb S_\lambda(V)$ in $\mathbb S_\mu(\mathcal L(V))$.²

How might we compute these coefficients?

The first observation is that the graded pieces of the free Lie algebra themselves admit Schur-functor decompositions:

$$\mathcal L_n(V)\cong \bigoplus_{\nu\vdash n}\mathbb S_\nu(V)^{\oplus m_\nu}.$$

Moreover, the multiplicities $m_\nu$ are well understood. They can be computed using symmetric-group characters, or by counting certain standard Young tableaux.³

So we know how to decompose $\mathcal L(V)$. The difficulty comes when we apply another Schur functor $\mathbb S_\mu$ to it.

This leads us directly to plethysm.

Plethysm describes the composition of Schur functors. Given partitions $\mu$ and $\nu$, we seek the decomposition

$$\mathbb S_\mu\bigl(\mathbb S_\nu(V)\bigr) \cong \bigoplus_{\lambda\vdash|\mu||\nu|} \mathbb S_\lambda(V)^{\oplus p_{\mu,\nu}^{\lambda}}.$$

The nonnegative integers $p_{\mu,\nu}^{\lambda}$ are the plethysm coefficients. In the language of symmetric functions, writing $s_\lambda$ for the Schur function associated with $\mathbb S_\lambda$, the same calculation is

$$s_\mu[s_\nu]=\sum_\lambda p_{\mu,\nu}^{\lambda}s_\lambda.$$

For our problem, let $\mathrm{Lie}_n=\sum_{\nu\vdash n}m_\nu s_\nu$ encode the degree-$n$ piece of the free Lie algebra. The coefficients we seek are precisely those in the expansion:⁴

$$s_\mu\left[\sum_{n\geq 1}\mathrm{Lie}_n\right] =\sum_\lambda c_{\lambda\mu}s_\lambda.$$

Thus the representation-theoretic question reduces to computing plethysms of symmetric functions.

Unfortunately, plethysm is notoriously difficult.⁵ Littlewood-Richardson coefficients, which govern tensor products of Schur functors, admit an elegant positive combinatorial rule. No comparably general positive rule is known for plethysm coefficients.⁶ Even determining which irreducible representations occur in a plethysm can be subtle, and general computations quickly become prohibitively expensive as the partitions grow.

Roll up your sleeves

Small examples of the coefficients $c_{\lambda\mu}$ can be computed by hand, but the calculations quickly become intractable. Sooner or later, one has to turn to a computer.

A confession: this was the first time in my mathematical career that I had found myself turning to a computer for help. My first attempts were brute force and, unsurprisingly, rather inefficient. They only produced coefficients through degree 5.

There are 18 nonempty partitions through degree 5, giving the $18\times 18$ matrix below. Rows index the target partition $\lambda$ and columns the source partition $\mu$.

Figure 01 / coefficient computation

Through degree 5

18 partitions on each axis, shown as Young diagrams.

Rows index target partitions; columns index source partitions. Rose marks the diagonal; green marks nonzero entries below it. Blank cells are zero. Within each degree, partitions are ordered reverse lexicographically.

Two features are immediately clear: the diagonal consists entirely of 1s, and everything above it is zero. Both are simple to prove directly. Since $\mathcal L_1(V)=V$ and there are no degree-zero terms, the lowest-degree part of $\mathbb S_\mu(\mathcal L(V))$ is $\mathbb S_\mu(V)$ itself, in degree $|\mu|$.

What interests us, then, is what lies strictly below the diagonal. Through degree 5, there is little to suggest a deeper pattern.

The key insight to improve on the naive brute-force approach was to recast the coefficients $c_{\lambda\mu}$ as weighted counts of solutions to certain combinatorial arrangements I called decomposition puzzles. The underlying combinatorics of these puzzles imposed clear restrictions on the kinds of assemblies that are valid, allowing us to significantly reduce the search space.

Lie pieces

The building blocks through degree 5

ℓ₁degree 1

ℓ₂degree 2

ℓ₃degree 3

ℓ₄degree 4

ℓ₅degree 4

ℓ₆degree 5

ℓ₇degree 5

ℓ₈degree 5

ℓ₉degree 5

ℓ₁₀degree 5

Decompose

μ = (2, 1)

↓

(2)

(1)

→

Pair

PartLie piece

(2)

⊙

ℓ₂

⊗

(1)

⊙

ℓ₁

⊙ plethysm; ⊗ tensor product

→

Check the degree

Selected pairing

2×2+1×1=5

Degree-compatible

Swap the Lie pieces

2×1+1×2=4

Reject for degree 5

Assemble

Evaluate the plethysms and tensor product for the surviving pairing. Each shape appears once.

(3, 2)

target

(2, 2, 1)

(2, 1, 1, 1)

(1, 1, 1, 1, 1)

The pairing from Example 3.18 of the paper contributes 1 to $c_{(3,2),(2,1)}$.

At the level of degrees, plethysm becomes multiplication and tensor product becomes addition. In the example above, the chosen pairing has degree $2\times 2+1\times 1=5$. Swapping the Lie pieces gives $2\times 1+1\times 2=4$, immediately ruling out that pairing for a degree-5 target.

This cheap check is the starting point of shape analysis.⁷ By grouping decompositions with the same part sizes, I could perform the search once per shape and reuse the resulting instructions across many calculations. I will give the details below.

This was the algorithm described in my 2017 paper. It extended the computation to degree 14: a $507\times 507$ matrix containing 257,049 entries, compared with the original 324.

Visualizing these expanded coefficients revealed a striking block-stability pattern that immediately brought to mind Church, Ellenberg, and Farb's work on FI-modules.⁸ Blocks in one part of the matrix seemed to recur, with changes, farther down and to the right.

You can explore this observation yourself in the interactive figure below: toggle Show degree boundaries to separate the matrix into blocks of fixed source and target degree. Use the maximum-degree slider to compare the expanded table with the degree-5 calculation.

Figure 02 / coefficient computation

The expanded coefficient matrix

This interactive figure loads as it approaches the screen.

Preparing interactive figure...

Before examining that pattern, let us look more closely at the puzzles that made a computation of this size possible.

Decomposition puzzles

Return to the decomposition of the free Lie algebra, now indexing its irreducible summands individually:

$$\mathcal L(V)\cong \bigoplus_{i\geq 1}\mathbb S_{\ell_i}(V).$$

The partitions $\ell_i$ label Lie pieces, with repeated summands listed separately. A $\mu$-decomposition is a tuple $D=(\mu_1,\ldots,\mu_k)$ of nonempty partitions satisfying $\sum_j|\mu_j|=|\mu|$. Its iterated Littlewood-Richardson coefficient is

$$\alpha_\mu(D) =[s_\mu]\bigl(s_{\mu_1}\cdots s_{\mu_k}\bigr).$$

Retain only the decompositions with $\alpha_\mu(D)>0$. For each one, choose a tuple $I=(i_1,\ldots,i_k)$ of distinct Lie-piece indices and form the assembly

$$A(D,I)=\prod_{j=1}^k s_{\mu_j}[s_{\ell_{i_j}}],$$

where brackets denote plethysm. The multiplicity of a target partition $\lambda$ in this assembly is $\beta_\lambda(D,I)=[s_\lambda]A(D,I)$.

A pairing in which $\lambda$ occurs is a solution to the puzzle, with weight $\alpha_\mu(D)\beta_\lambda(D,I)$. Theorem 3.21 of the paper identifies $c_{\lambda\mu}$ with the sum over the set $\Sigma(\mu,\lambda)$ of distinct solutions:⁹

$$c_{\lambda\mu} =\sum_{\sigma\in\Sigma(\mu,\lambda)} \alpha_\mu(\sigma)\,\beta_\lambda(\sigma).$$

Shape analysis

Enumerating every assembly would still require too many expensive plethysms. The useful restriction comes from homogeneity: an assembly has degree $\sum_j|\mu_j|\,|\ell_{i_j}|$, so it can contribute to $\lambda\vdash d$ only when that sum equals $d$.

This condition depends on the decomposition only through its shape

$$\theta=(|\mu_1|,\ldots,|\mu_k|),$$

with the pieces ordered by decreasing size. Writing $r_i=|\ell_i|$ for the Lie-piece degrees, the condition becomes

$$\theta_1r_{i_1}+\cdots+\theta_kr_{i_k}=d.$$

The shape also gives an upper bound on the degrees of the Lie pieces we need to consider.¹⁰ The algorithm searches this smaller collection for degree-compatible pairings and caches their indices. These instructions can then be reused by every decomposition of the same shape.

Figure 03 / coefficient computation

Shape analysis

This interactive figure loads as it approaches the screen.

Preparing interactive figure...

For $\theta=(2,1)$ and target degree 5, the ten available Lie pieces give 90 ordered pairs. The bound restricts us to pieces of degree at most 3, leaving six pairs. The equation $2r_{i_1}+r_{i_2}=5$ then leaves just two: the degree pairs $(1,3)$ and $(2,1)$.

The instruction count is not itself a coefficient. For $\mu=(2,1)$ and $D=((2),(1))$, each of these two assemblies contributes one copy of the target $(3,2)$. The decomposition $D'=((1,1),(1))$ contributes one further copy, so the full weighted sum is

$$c_{(3,2),(2,1)}=3.$$

The algorithm and its computational range

For a fixed target degree $d$, the implementation computes all coefficients with $|\lambda|=d$ simultaneously:

1. Construct the instruction lookup for each shape and target degree.
2. Enumerate the decompositions with nonzero Littlewood-Richardson multiplicity.
3. Assemble the compatible instructions and accumulate their Schur coefficients with the appropriate weights and overcount correction.

The optimization does not eliminate plethysm; it avoids evaluating assemblies that cannot contribute.

The following comparison is from the experiments reported in the paper:

Quantity	Direct baseline	Decomposition-puzzle algorithm
Largest degree reached in the paper	5	14
Entries in the resulting full matrix	324	257,049
Time to compute through degree 5	119 seconds	0.239 seconds

The paper's "over 750-fold" claim refers to the expanded number of matrix entries. The degree-5 timing comparison is a separate result: roughly 498 times faster in that experiment.

These are timings from the 2017 experiments, not benchmarks of current versions of Sage.¹¹

Diagonal stabilization

Return now to the pattern in the expanded matrix. The similarities between successive $(m,d)$- and $(m+1,d+1)$-blocks, where $m$ and $d$ are the source and target degrees, suggest adding a box to the first row of each indexing partition. Both degrees increase by one, while their difference stays fixed.

Write $\lambda^{+r}=(\lambda_1+r,\lambda_2,\ldots)$ for adding $r$ boxes to the first row. For a fixed pair $(\lambda,\mu)$, consider the sequence

$$c_{\lambda\mu},\quad c_{\lambda^{+1}\mu^{+1}},\quad c_{\lambda^{+2}\mu^{+2}},\quad\ldots$$

For example, the pair $\lambda=(2,2,1)$, $\mu=(1,1)$ gives the initial values $2,11,14$, followed by the value 14 through $r=9$, the endpoint of the degree-14 computation. The figure allows this sequence to be compared with other pairs, including any pair selected in the matrix.

Figure 04 / coefficient computation

Diagonal stabilization

This interactive figure loads as it approaches the screen.

Preparing interactive figure...

The computed plateaus suggest eventual constancy along these diagonals, rather than merely a similarity between finite blocks.

Conjecture 5.4 of the paper states that, for every fixed pair $\lambda,\mu$, there exist constants $N,C$ such that

$$c_{\lambda^{+r}\mu^{+r}}=C \qquad\text{for all }r\geq N.$$

The finite computation motivates this statement but does not prove it or determine the onset of permanent stabilization.

Representation stability via PD-modules

Chapter 5 of the thesis introduces PD-modules to describe this simultaneous growth. They organize representations indexed by two finite sets, with compatible maps that enlarge both sets by the same amount.¹² Schur-Weyl duality identifies our coefficients as multiplicities in a PD-module built from the free Lie algebra.

The key condition is finite generation in rank: for each fixed difference between the two degrees, finitely many generators suffice under these diagonal structure maps. Theorem 5.5.3 shows that PD-modules with this property satisfy representation stability.

For the free Lie algebra, finite generation comes from the same degree constraint used by the algorithm. At fixed rank $q=|\lambda|-|\mu|$, it gives

$$q=\sum_j|\mu_j|\bigl(|\ell_{i_j}|-1\bigr).$$

Every Lie piece of degree greater than one contributes at least $|\mu_j|$ to this sum. The total source degree assigned to such pieces is therefore at most $q$. All unbounded growth must occur in the factor paired with the unique degree-one Lie piece, $\mathcal L_1(V)=V$. This growth is encoded by the PD structure maps; the remaining assemblies have bounded degree and supply finitely many generators. Theorem 5.6.4 makes this argument precise.

It follows that our coefficients stabilize under simultaneous first-row augmentation. This is Theorem 5.6.5 of the thesis, proving the conjecture above.

The computation supplied evidence for the stability statement. The PD-module structure explains why it holds beyond the computed range.

Sources and reproducibility

The article follows An efficient algorithm computing composition factors of $T(V)^{\otimes n}$, especially Sections 2.3, 3.4, 5, and 6. The proof of stability is in Chapter 5 of my thesis; Chapter 4 develops the algorithm and its visualizations. The original Sage implementation is on GitHub.

Data provenance. The figures use freshly reconstructed coefficients, not values extracted from images or a recovered archive of the original run. They were computed from the defining plethysm using exact arithmetic, independently of the paper's puzzle algorithm.¹³ The download includes the partition order, source reference, and a matrix checksum. All interactions use this precomputed table; no algebra is evaluated in the browser.

Footnotes

1. Unpacking that structure turned out to be at the heart of my thesis. ↩

2. Work over a field $\mathbf{k}$ of characteristic zero. These are universal Schur-functor multiplicities: interpret the identities degree by degree, or evaluate on $V$ of sufficiently large dimension in each degree. For nonempty $\mu$, the decomposition extends over arbitrarily large degrees, but only finitely many partitions $\lambda$ contribute in any given degree. ↩

3. For $\nu\vdash n$, the multiplicity $m_\nu$ counts standard Young tableaux of shape $\nu$ whose major index is congruent to 1 modulo $n$. The major index is the sum of entries $i$ for which $i+1$ appears in a lower row. See Theorem 3.4 of the paper, following Stanley's Enumerative Combinatorics, Volume 2. ↩

4. Explicitly,

   $$\mathrm{Lie}_n=\frac{1}{n}\sum_{d\mid n} \mu_{\mathrm{Mob}}(d)\,p_d^{n/d},$$

   where $\mu_{\mathrm{Mob}}$ is the Mobius function and $p_d$ is the degree-$d$ power-sum symmetric function. The infinite sum is taken in the degree-completed ring of symmetric functions; computing through any fixed degree requires only finitely many homogeneous terms. ↩

5. Nick Fischer and Christian Ikenmeyer, The Computational Complexity of Plethysm Coefficients, Computational Complexity 29 (2020), Article 8, prove that computing plethysm coefficients is #P-hard and deciding positivity is NP-hard. Both results already hold for the symmetric-power family $s_{(n)}[s_{(m)}]$ with any fixed $m\geq 3$. In this same family, fixing the outer parameter $n$ permits polynomial-time computation; see Theorems 3.1-3.2 and Proposition 3.3. ↩

6. Richard P. Stanley poses the combinatorial interpretation problem as Problem 9 in Positivity Problems and Conjectures in Algebraic Combinatorics, in Mathematics: Frontiers and Perspectives (AMS, 2000), pp. 295-319. For a modern account of the open problem and computational techniques, see Laura Colmenarejo, Rosa Orellana, Franco Saliola, Anne Schilling, and Mike Zabrocki, The Mystery of Plethysm Coefficients, in Open Problems in Algebraic Combinatorics, Proceedings of Symposia in Pure Mathematics 110 (2024), pp. 275-292, especially Problem 1.1. ↩

7. See Proposition 3.24 and Figure 6 of the paper. Matching the target degree is a necessary condition; the subsequent assembly determines which target partitions occur and with what multiplicity. ↩

8. Thomas Church, Jordan S. Ellenberg, and Benson Farb, FI-modules and stability for representations of symmetric groups, Duke Mathematical Journal 164, no. 9 (2015), pp. 1833-1910. ↩

9. The weighted formula follows by iterating the Littlewood-Richardson rule for Schur functors of direct sums. Distinct solutions are taken modulo simultaneous permutation of the paired factors. The implementation fixes a representative decomposition and enumerates ordered instructions. If its distinct partitions occur $n_1,\ldots,n_t$ times, it corrects the overcount by $1/(n_1!\cdots n_t!)$. Repeated Lie pieces at distinct indices remain distinct summands. ↩

10. Order the shape parts decreasingly and the Lie-piece degrees $r_1,r_2,\ldots$ increasingly, counting multiplicities. Lemma 3.28 of the paper gives the upper bound

    $$\varphi(\theta,d)= \left\lfloor \frac{d-\sum_{j=1}^{k-1}\theta_jr_j}{\theta_k} \right\rfloor.$$

    Pairing the largest shape parts with the smallest available degrees leaves the greatest possible allowance for the remaining piece. ↩

11. Averages of ten runs on a 2.3 GHz Intel Core i7 with 16 GB of RAM, as reported in the paper. ↩

12. Formally, a PD-module is a functor $\mathsf{PD}\to\operatorname{Vect}_{\mathbf{k}}$. A morphism between pairs of finite sets consists of an injection in each coordinate and a bijection between their complements. Its values in bidegree $(i,n)$ are $(S_i,S_n)$-bimodules; the structure maps preserve the rank $n-i$. Sections 5.5 and 5.6 of the thesis give the stability theorem and the free-Lie construction. ↩

13. The exporter, scripts/generate-composition-data.py, uses degree-truncated power-sum plethysm with exact rational arithmetic. It checks character orthogonality, integrality, nonnegativity, the equal-degree identity, and examples from the original code. This is not a port or timing comparison of the original algorithm. ↩