REPRESENTATION THEORY An Electronic Journal of the American Mathematical Society Volume 00, Pages 000–000 (Xxxx XX, XXXX) S 1088-4165(XX)0000-0

SOME RESULTS OBTAINED BY APPLICATION OF THE LLT ALGORITHM

SINÉAD LYLE

Abstract. For every Hecke algebra of type A, we may define a decomposition matrix; the structure of each such matrix is well–known, but in general there is no way to compute the entries. An exception is the Hecke algebra H_{0} = H_{ℂ,ω}(𝔖_{n}), where ω is a root of unity in ℂ. Here a recursive algorithm, the LLT algorithm, will produce the decomposition matrices – in fact, the resulting matrix provides a ‘first approximation’ to the decomposition matrix of an arbitrary Hecke algebra of type A.

The LLT algorithm is, however, recursive on n. We show that, in the case of some simple partitions, it is possible to use the algorithm to obtain general results; in particular, given a Specht module corresponding to a partition with at most three parts, we will find its composition factors. We also give an indication of the situation in which the partition in question has four parts.

1. Introduction

In 1996, a recursive algorithm was published, which the authors claimed could determine the decomposition matrices of the Iwahori–Hecke algebra H_{0} = H_{ℂ,ω}(𝔖_{n}), where ω was a primitive eth root of unity in ℂ. Apart from being interesting in their own right, the decomposition matrices for H_{0} will provide information about an arbitrary Hecke algebra H = H_{F,q}(𝔖_{n}), including the symmetric group algebra F 𝔖_{n}.

This claim [4] has since been proved [1], and the resulting algorithm is known as the LLT algorithm. However, it is recursive on n, and even with specially designed computer programs, for example the GAP share package Specht [S^{+}95, 7], it is impractical to obtain results for large n. Nevertheless, in the case of some simple partitions, it has been possible to obtain explicit results. We concentrate here on partitions with at most three parts; we will determine the composition factors of any Specht module corresponding to such a partition. More detailed proofs of our results and further information concerning partitions with at most four parts appear in [5]; the arguments applied are similar to those given.

We begin by establishing some notation. We fix an integer e ≥ 2. Throughout, H_{0} will denote the Iwahori–Hecke algebra H_{ℂ,ω}(𝔖_{n}) where ω is a primitive eth root of unity in ℂ. It has been shown that H_{0} is a cellular algebra; accordingly for each partition λ of n, we define a cell H_{0}-module S^{λ} (known as the Specht module) and a H_{0}-module D^{λ}. We use the notation of Dipper and James [2] rather than taking the conjugate dual modules of some of the literature. Hence we define the

\begin{matrix}c \\ ◯ \end{matrix}1997 American Mathematical Society

2000 Mathematics Subject Classification. 20C08.

This work was supported by EPSRC grant 99800740. The author would like to thank Gordon James for his suggestions.

decomposition matrix of H_{0}: for λ, μ partitions of n and λ e-regular, set d_{μλ} = [S^{μ} : D^{λ}] to be the composition multiplicity of D^{λ} in S^{μ}. The matrix D = (d_{μλ}) where λ, μ are partitions of n and λ is e-regular is called the decomposition matrix of H_{0}; since {S^{λ} | λ a partition of n} form a complete set of pairwise inequivalent cell modules of H_{0}, and {D^{λ} | λ an e-regular partition of n} form a complete set of pairwise inequivalent irreducible H_{0}-modules, it agrees with the usual definition of a decomposition matrix.

We define a partial order on the set of partitions of n by saying that λ ⊵ μ if and only if

∑_{i=1}^{k} λ_{i} ≥ ∑_{i=1}^{k} μ_{i} for all k

and write λ ▷ μ if λ ⊵ μ and λ ≠ μ. Suppose that λ and μ are partitions of n with λ being e-regular. Then

(1) d_{λλ} = 1 and
(2) d_{μλ} = 0 unless λ ⊵ μ.

Hence by arranging the rows and columns of D in a suitable order, we get that D is lower unitriangular.

The LLT algorithm will compute these decomposition matrices.

2. The LLT algorithm

We begin by describing the LLT algorithm.

Definition. Let λ = (λ_{1}, λ_{2}, …) be a partition. Then the diagram of λ, denoted [λ], is the set of nodes {(i, j) | 1 ≤ j ≤ λ_{i} and i ≥ 1}.

The e-residue diagram of λ, is the diagram obtained by replacing each node by the number (j − i) mod e and the e-ladder diagram of λ is the diagram obtained by replacing each node by the number i − j + (j − 1)e.

Example. Let λ = (4, 2, 1) and e = 3. Then the diagram, e-residue diagram and e-ladder diagram of λ are respectively given by:

∗ ∗ ∗ ∗  0 1 2 0  0 2 4 6.
∗ ∗  2 0  1 3
∗  1  2

Definition. A node γ ∉ [λ] is said to be addable if [λ ∪ γ] is the diagram of a partition. A node γ ∈ [λ] is said to be removable if [λ \ γ] is the diagram of a partition.

Example. Let λ = (5, 3, 3, 1). Then the removable nodes are those indicated by an underscore in the first diagram and the addable nodes those indicated by a dot in the second.

∗ ∗ ∗ ∗ \underline{∗}  ∗ ∗ ∗ ∗ ∗ ·
∗ ∗ ∗  ∗ ∗ ∗ ·
∗ ∗ \underline{∗}  ∗ ∗ ∗
\underline{∗}  ∗ ·
·

Definition. Let λ, μ be partitions and suppose the e-residue diagram of μ is formed by adding d nodes, all of residue i, to the e-residue diagram of λ. Write λ ⟶^{d:i} μ. Define

F_{i}^{d}(λ) = ∑_{λ→^{d:i}μ} v^{N_{i}(λ,μ)}μ

where N_{i}(λ, μ) is given by

N_{i}(λ, μ) = ∑_{γ∈[μ]\[λ]} (#{γ′ | γ′ an addable i-node of μ above γ}

− #{γ′ | γ′ a removable i-node of λ above γ}).

The term v may be regarded simply as a parameter.

Definition. The LLT algorithm can now be implemented. The algorithm works by calculating the ‘crystallized decomposition matrix’ of H_{0}. This is a lower unitriangular matrix with the same structure as the decomposition matrix of H_{0}, but whose lower triangular entries are elements of vℕ[v], where 0 is included as a natural number. The decomposition matrix of H_{0} is then obtained by setting v = 1. If λ is an e-regular partition of n, define B(λ) to be the column of the crystallized decomposition matrix indexed by λ. Since the LLT algorithm is recursive, we assume that we know B(μ) where μ is a partition of m and either m < n or m = n and λ ▷ μ. This is reasonable, since if n = 1 the crystallized decomposition matrix is simply the identity matrix and if μ dominates no other e-regular partition of n then B(μ) = μ.

To find B(λ) for given λ, we operate the LLT algorithm as follows.

(1) Write down the e-residue diagram of λ. Construct the partition τ by removing those nodes in [λ] with maximal ladder number. Suppose there are d such nodes and that they have (common) e-residue i.

(2) By assumption, we know B(τ). Set C_{λ} = F_{i}^{d}B(τ) with F_{i}^{d}B(τ) defined in the obvious manner from F_{i}^{d}(τ′). Then C_{λ} is of the form

C_{λ} = ∑_{λ⊵ν} c_{νλ}(v)ν

= B(λ) − ∑_{λ▷ν} α_{νλ}(v)B(ν)

where α_{νλ}(v) ∈ ℕ[v + v^{−1}] and c_{νλ}(v) ∈ ℕ[v, v^{−1}].

(3) Find the most dominant partition, ν_{0}, such that c_{ν_{0}λ}(v) does not belong to vℕ[v]. If no such partition exists then B(λ) = C_{λ} and we are done. Otherwise, α_{ν_{0}λ}(v) is the unique polynomial in v + v^{−1} such that the coefficient of v^{i} in α_{ν_{0}λ}(v) is equal to the coefficient of v^{i} in c_{ν_{0}λ}(v) for all i ≤ 0.

Replace C_{λ} with the element C_{λ} − α_{ν_{0}λ}(v)B(ν_{0}) and repeat step 3 until all the coefficients c_{νλ}(v) belong to vℕ[v] for λ ▷ ν.

Example. Consider λ = (3, 2) and e = 2. We wish to find B(3, 2).

(1) Find τ. The e-ladder diagram of λ is 0 1 2 1 2 . Hence τ is given by \begin{matrix}∗ & ∗ \\ ∗ \end{matrix}

where we have removed 2 nodes, both of e-residue 0.

(2) Looking up τ = (2, 1) we find that B(τ) = (2, 1). We calculate C_{λ} = F_{0}^{2}B(τ):

0 1 1 ⟶^{2:0} 0 1 0 1 0 + \begin{aligned}v & 0 & 1 & 0 \\ & 1 \\ & 0 \end{aligned} + \begin{aligned}v^{2} & 0 & 1 \\ & 1 & 0 \\ & 0 \end{aligned} .

(3) Since this is of the correct form,

B(3, 2) = (3, 2) + v(3, 1^{2}) + v^{2}(2^{2}, 1).

Example. Consider λ = (5) and e = 2. We wish to find B(5).

(1) Find τ. The e-ladder diagram of λ is 0 1 2 3 4 . Hence τ is given by ∗ ∗ ∗ ∗ where we have removed 1 node, of e-residue 0.

(2) Looking up τ = (4) we find that B(τ) = (4) + v(3, 1) + v(2, 1^{2}) + v^{2}(1^{4}). We calculate C_{λ} = F_{0}^{1}B(τ):

0 1 0 1 + \begin{aligned}v & 0 & 1 & 0 \\ & 1 \end{aligned} + \begin{aligned}v & 0 & 1 \\ & 1 \\ & 0 \end{aligned} + \begin{aligned}v^{2} & 0 \\ & 1 \\ & 0 \\ & 1 \end{aligned} ⟶^{1:0} ^{0 1 0 1 0}

+ 0 1 0 1 0 + \begin{aligned}v & 0 & 1 & 0 \\ & 1 \\ & 0 \end{aligned} + \begin{aligned}v & 0 & 1 & 0 \\ & 1 \\ & 0 \end{aligned} + \begin{aligned}v^{2} & 0 & 1 \\ & 1 & 0 \\ & 0 \end{aligned} + \begin{aligned}v^{2} & 0 \\ & 1 \\ & 0 \\ & 1 \\ & 0 \end{aligned} .

(3) This is not of the correct form. The partition ν = (3, 2) has coefficient 1 ∉ vℕ[v]. Hence α_{νλ}(v) = 1. We subtract B(3, 2) once from C_{λ} to get

(5) + (3, 2) + 2v(3, 1^{2}) + v^{2}(2^{2}, 1) + v^{2}(1^{5}) − [(3, 2) + v(3, 1^{2}) + v^{2}(2^{2}, 1)]
= (5) + v(3, 1^{2}) + v^{2}(1^{5}).

This is of the correct form, hence

B(5) = (5) + v(3, 1^{2}) + v^{2}(1^{5}).

Remark 2.1. There are two very useful facts which are not immediately apparent from this description. These are as follows.

• For a given partition μ of n and d, i ∈ ℕ suppose that F_{i}^{d}B(μ) is of the form

λ + v ∑_{λ▷ν} c_{νλ}(v)ν

for polynomials c_{νλ}(v) ∈ ℕ[v]. Then B(λ) = F_{i}^{d}B(μ).

• The partial order on the set of partitions of n gives that if ν has exactly s parts and μ exactly t parts with s < t then μ ⋭ ν. Suppose we only consider some dominant partitions, that is, those partitions with at most s parts. Given a partition λ, we would like to find out which such dominant Specht modules contain D^{λ} as a composition factor. The format of the LLT algorithm means that we can achieve this by simply ignoring, at every step, those partitions with more than s parts.

3. Partitions with at most 3 parts

Definition. Let B′_{s}(λ) be the truncated column of the crystallized decomposition matrix indexed by λ corresponding to only the rows containing partitions with at most s parts. Clearly if λ itself has more than s parts then B′_{s}(λ) = 0. For the rest of Section 3, we consider B′_{3}(λ), denoted simply B′(λ).

Theorem 3.1. Let 2 ≤ e < ∞ and suppose λ = (λ_{1}, λ_{2}) is a one or two part e-regular partion of (λ_{1} + λ_{2}) = n. Suppose that

λ_{1} − λ_{2} = ae + i − 1
λ_{2} = be + j − 1

where 0 ≤ i, j < e. Define

m_{2} = be − 1
m_{1} − m_{2} = ae − 1

so that λ = (m_{1} + i + j, m_{2} + j). Also if (i + j) > e, let

I = (i + j) − e.

Then B′(λ) is given by the following sums of partitions.

\underline{i, j = 0 :} (m_{1}, m_{2})

(\underline{i = 0, j > 0 :}) / (a = 1, b = 0 :)

(m_{1} + j, m_{2} + j) a ≥ 2, b = 0 :

(m_{1} + j, m_{2} + j) + v(m_{1} + j − e, m_{2} + e, j) a ≥ 1, b ≥ 1 :

(m_{1} + j, m_{2} + j) + v(m_{1} + j, m_{2}, j) + v^{2}(m_{1}, m_{2} + j, j)

(\underline{i > 0, j = 0 :}) / (a = 0, b = 1 :)

(m_{1} + i, m_{2}) a = 0, b ≥ 2 :

(m_{1} + i, m_{2}) + v(m_{1}, m_{2} − e + i, e) a ≥ 1, b ≥ 1 :

(m_{1} + i, m_{2}) + v(m_{1}, m_{2} + i) + v^{2}(m_{1}, m_{2}, i)

\underline{i, j > 0, i + j < e :} a = 0, b = 0 :

(m_{1} + i + j, m_{2} + j) a = 1, b = 0 :

(m_{1} + i + j, m_{2} + j) + v(m_{1} + j, m_{2} + i + j) a ≥ 2, b = 0 :

(m_{1} + i + j, m_{2} + j) + v(m_{1} + j, m_{2} + i + j) + v(m_{1} + i + j − e, m_{2} + e, j)+ v^{2}(m_{1} + j − e, m_{2} + e, i + j)

a = 0, b = 1 :

(m_{1} + i + j, m_{2} + j) + v(m_{1} + i + j, m_{2}, j) a = 0, b ≥ 2 :

(m_{1} + i + j, m_{2} + j) + v(m_{1} + i + j, m_{2}, j) + v(m_{1} + j, m_{2} + i + j − e, e)+ v^{2}(m_{1}, m_{2} + i + j − e, e + j)

a ≥ 1, b ≥ 1 :

(m_{1} + i + j, m_{2} + j) + v(m_{1} + j, m_{2} + i + j) + v(m_{1} + i + j, m_{2}, j)+ v^{2}(m_{1} + j, m_{2}, i + j) + v^{2}(m_{1}, m_{2} + i + j, j) + v^{3}(m_{1}, m_{2} + j, i + j)

\underline{i + j = e :} a = 0, b = 0 :

(m_{1} + e, m_{2} + j) a = 1, b = 0 :

(m_{1} + e, m_{2} + j) + v(m_{1} + j, m_{2} + e) a ≥ 2, b = 0 :

(m_{1} + e, m_{2} + j) + v(m_{1} + j, m_{2} + e) + v(m_{1}, m_{2} + e, j) a = 0, b = 1 :

(m_{1} + e, m_{2} + j) + v(m_{1} + e, m_{2}, j) a = 1, b = 1 :

(m_{1} + e, m_{2} + j) + v(m_{1} + j, m_{2} + e) + v(m_{1} + e, m_{2}, j) + v^{2}(m_{1}, m_{2} + j, e) a ≥ 2, b = 1 :

(m_{1} + e, m_{2} + j) + v(m_{1} + j, m_{2} + e) + v(m_{1} + e, m_{2}, j) + v(m_{1}, m_{2} + e, j)+ v^{2}(m_{1}, m_{2} + j, e)

a = 0, b ≥ 2 :

(m_{1} + e, m_{2} + j) + v(m_{1} + e, m_{2}, j) + v(m_{1} + j, m_{2}, e) a = 1, b ≥ 2 :

(m_{1} + e, m_{2} + j) + v(m_{1} + j, m_{2} + e) + v(m_{1} + e, m_{2}, j) + v(m_{1} + j, m_{2}, e)+ v^{2}(m_{1}, m_{2} + j, e)

a ≥ 2, b ≥ 2 :

(m_{1} + e, m_{2} + j) + v(m_{1} + j, m_{2} + e) + v(m_{1} + e, m_{2}, j) + v(m_{1} + j, m_{2}, e)+ v(m_{1}, m_{2} + e, j) + v^{2}(m_{1}, m_{2} + j, e)

\underline{i + j > e :} a = 0, b = 0 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) a = 1, b = 0 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + j, m_{2} + e + I)+ v^{2}(m_{1} + j, m_{2} + e, I)

a ≥ 2, b = 0 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + j, m_{2} + e + I)+ v^{2}(m_{1} + j, m_{2} + e, I) + v(m_{1} + I, m_{2} + e, j) + v^{2}(m_{1}, m_{2} + e + I, j)

a = 0, b = 1 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + e + I, m_{2}, j)+ v^{2}(m_{1} + e, m_{2} + I, j)

a = 1, b = 1 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + j, m_{2} + e + I)+ v^{2}(m_{1} + j, m_{2} + e, I) + v(m_{1} + e + I, m_{2}, j) + v^{2}(m_{1} + e, m_{2} + I, j)+ v^{2}(m_{1} + I, m_{2} + j, e) + v^{3}(m_{1}, m_{2} + j, e + I)

a ≥ 2, b = 1 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + j, m_{2} + e + I)+ v^{2}(m_{1} + j, m_{2} + e, I) + v(m_{1} + e + I, m_{2}, j) + v^{2}(m_{1} + e, m_{2} + I, j)+ v(m_{1} + I, m_{2} + e, j) + v^{2}(m_{1}, m_{2} + e + I, j) + v^{2}(m_{1} + I, m_{2} + j, e)+ v^{3}(m_{1}, m_{2} + j, e + I)

a = 0, b ≥ 2 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + e + I, m_{2}, j)+ v^{2}(m_{1} + e, m_{2} + I, j) + v(m_{1} + j, m_{2} + I, e) + v^{2}(m_{1} + j, m_{2}, e + I)

a = 1, b ≥ 2 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + j, m_{2} + e + I)+ v^{2}(m_{1} + j, m_{2} + e, I) + v(m_{1} + e + I, m_{2}, j) + v^{2}(m_{1} + e, m_{2} + I, j)+ v(m_{1} + j, m_{2} + I, e) + v^{2}(m_{1} + j, m_{2}, e + I) + v^{2}(m_{1} + I, m_{2} + j, e)+ v^{3}(m_{1}, m_{2} + j, e + I)

a ≥ 2, b ≥ 2 :

(m_{1} + e + I, m_{2} + j) + v(m_{1} + e, m_{2} + j, I) + v(m_{1} + j, m_{2} + e + I)+ v^{2}(m_{1} + j, m_{2} + e, I) + v(m_{1} + e + I, m_{2}, j) + v^{2}(m_{1} + e, m_{2} + I, j)+ v(m_{1} + j, m_{2} + I, e) + v^{2}(m_{1} + j, m_{2}, e + I) + v(m_{1} + I, m_{2} + e, j)+ v^{2}(m_{1}, m_{2} + e + I, j) + v^{2}(m_{1} + I, m_{2} + j, e) + v^{3}(m_{1}, m_{2} + j, e + I)

The proof will follow.

Corollary 3.2. We recover the decomposition matrix by setting v = 1. If λ is a partition with at most 2 parts and μ a partition with at most 3 parts then [S^{μ} : D^{λ}] is either 0 or 1 for any irreducible D^{λ}.

Remark 3.3. If e = 2 then the case a = 0 does not occur and the only cases for (i, j) are (i = 0, j = 0), (i = 1, j = 0), (i = 0, j = 1) and (i + j = e). In these situations, Theorem 3.1 still holds.

Example. Suppose e = 3 and λ = (8, 6). Using the definitions above, we get that (i, j) = (0, 1), (m_{1}, m_{2}) = (7, 5) and (a, b) = (1, 2). If we look up this case above, we find that

B′(λ) = (m_{1} + j, m_{2} + j) + v(m_{1} + j, m_{2}, j) + v^{2}(m_{1}, m_{2} + j, j)
= (8, 6) + v(8, 5, 1) + v^{2}(7, 6, 1)

and that D^{(8,6)} is a composition factor of S^{(8,6)}, S^{(8,5,1)} and S^{(7,6,1)}, each with multiplicity 1. Theorem 3.4 (The column addition theorem). [6] Let λ, μ be partitions of n where λ = (λ_{1}, …, λ_{s}) and μ = (μ_{1}, …, μ_{t}). Suppose

λ_{0} = \underbrace{(λ_{1} + k, …, λ_{s} + k, k, …, k)}_{l}

μ_{0} = \underbrace{(μ_{1} + k, …, λ_{t} + k, k, …, k)}_{l}

are such that λ_{0}, μ_{0} are partitions of n + lk and λ_{0} is e-regular. Then

[S^{μ} : D^{λ}] = [S^{μ_{0}} : D^{λ_{0}}].

Corollary 3.5. Given any e-regular partition λ, we may use Theorem 3.1 to read off the multiplicity [S^{μ} : D^{λ}] for any Specht module S^{μ} such that μ has at most 3 parts.

Proof. Consider an e-regular partition λ. If λ has at most 2 parts, then Corollary 3.5 follows from Theorem 3.1, and if λ has more than 3 parts then it cannot be a composition factor of any Specht module S^{μ} where μ has at most 3 parts. Consider λ = (λ_{1}, λ_{2}, λ_{3}) having exactly 3 parts. From Theorem 3.1, we know which Specht modules corresponding to partitions with at most 2 parts contain D^{λ} as a composition factor. But S^{(μ_{1},μ_{2},μ_{3})} contains a composition factor D^{(λ_{1},λ_{2},λ_{3})} if and only if μ_{3} ≥ λ_{3} and S^{(μ_{1}−λ_{3},μ_{2}−λ_{3},μ_{3}−λ_{3})} contains a composition factor D^{(λ_{1}−λ_{3},λ_{2}−λ_{3})}, which information is known. □

Now let λ = (λ_{1}, λ_{2}, λ_{3}) be a partition with at most 3 parts. Write

λ = ( \begin{matrix}α_{1} & α_{2} & α_{3} \\ λ_{1} & λ_{2} & λ_{3} \end{matrix} )

where α_{i} is the e-residue of the last node on line i, with the convention that if λ_{2} = 0 then α_{2} = e − 2 and if λ_{3} = 0 then α_{3} = e − 3, that is, if we add a node to line i, that node will have residue α_{i} + 1. Note α_{i} is only defined up to modulus e; no distinction will be made between α_{i} and α_{i} + e. Let ≡ denote equivalence modulo e. Otherwise the notation is that defined in Theorem 3.1.

Proof of Theorem 3.1. A full proof of Theorem 3.1 is given in [5]. Here we only prove most cases when a, b ≥ 1, and the case that b = 0 and a ≥ 2. It is a simple matter to prove the remaining instances by induction, the proofs being very similar to those given, but it is necessary to consider each one individually.

Our proof uses some general results (see [6]); it is possible avoid these and proceed using only the LLT algorithm, but this is even more time consuming. For the remaining cases, the proof is by induction.

General Results:

(1) d_{μλ} ≠ 0 only if λ and μ have the same e-core.

(2) Carter’s criterion: Set h(i, j) to be the hook length of node (i, j), that is h(i, j) = λ_{i} + λ′_{j} − i − j + 1 where λ′ denotes the partion conjugate to λ. Over a field of characteristic 0, set ν_{e}(k) = 0 if e | k and −1 otherwise. Then if ν_{e}(h(a, c)) = ν_{e}(h(b, c)) for all nodes (a, c) and (b, c) in [λ] we have that S^{λ} is irreducible.

\underline{(1) i, j = 0}: Recall that m_{2} ≡ e − 1 and m_{1} ≡ e − 2. This partition has e-core (2e − 2, e − 1). If the Specht module corresponding to a partition μ has D^{(m_{1},m_{2})} as a composition factor, then μ has e-core (2e − 2, e − 1). Suppose μ = (μ_{1}, μ_{2}, μ_{3}) has such an e-core. Form the partition ν = (ν_{1}, ν_{2}, ν_{3}) by removing all possible horizontal e-rim hooks, that is hooks of leg length 0, from μ so that ν_{i} ≡ μ_{i} for all i and ν_{3}, ν_{2} − ν_{3}, ν_{1} − ν_{2} < e.

Now suppose that ν_{2} − ν_{3} < e − 1. Since μ and hence ν has e-core (2e − 2, e − 1), we have that ν_{2} ≥ e − 1 and hence we can remove a rim hook beginning at the node (2, ν_{2}) and working downwards. But this produces a partition whose second part is less than ν_{3} where ν_{3} ≤ e − 1 and which cannot have the correct e-core. Thus ν_{2} − ν_{3} = e − 1. A similar argument shows that ν_{1} − ν_{2} = e − 1. Hence ν = (ν_{3} + 2e − 2, ν_{3} + e − 1, ν_{3}) (where ν_{3} < e) is an e-core, and for it to have the correct form, we must have that ν_{3} = 0. But ν was formed by removing horizontal hooks from μ. Thus the only partitions with at most 3 parts and with such an

APPLYING THE LLT ALGORITHM 9

e-core are of the form (re − 2, se − 1, te) for some integers r, s, t and by Carter’s criterion, these are irreducible.

Hence B′(m_{1}, m_{2}) = (m_{1}, m_{2}).

Now assume that i > 0 and j > 0 unless otherwise stated.

\underline{(2) j = 0; a, b ≥ 1}: Proof is by induction on i for 1 ≤ i < e. i = 1: By (1), B′(m_{1}, m_{2}) = (m_{1}, m_{2}). Then F_{e−2}^{1}B′(m_{1}, m_{2}) is given by

( \begin{matrix}e − 3 & e − 3 & e − 3 \\ m_{1} & m_{2} & 0 \end{matrix} ) ⟶^{1,e−2} ( \begin{matrix}e − 2 & e − 3 & e − 3 \\ m_{1} + 1 & m_{2} & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 2 & e − 3 \\ m_{1} & m_{2} + 1 & 0 \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & e − 3 & e − 2 \\ m_{1} & m_{2} & 1 \end{matrix} )

which, since it is of the correct form, is equal to B′(m_{1} + 1, m_{2}). 2 ≤ i < e: Assume true for i − 1. Then F_{i−3}^{1}B′(m_{1} + i − 1, m_{2}) is given by

( \begin{matrix}i − 4 & e − 3 & e − 3 \\ m_{1} + i − 1 & m_{2} & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & i − 4 & e − 3 \\ m_{1} & m_{2} + i − 1 & 0 \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & e − 3 & i − 4 \\ m_{1} & m_{2} & i − 1 \end{matrix} )

⟶^{1,i−3} ( \begin{matrix}i − 3 & e − 3 & e − 3 \\ m_{1} + i & m_{2} & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & i − 3 & e − 3 \\ m_{1} & m_{2} + i & 0 \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & e − 3 & i − 3 \\ m_{1} & m_{2} & i \end{matrix} )

since e − 3 ≢ i − 3, i − 4 and m_{1} − m_{2}, m_{2} ≥ e − 1.

\underline{(3) i = 0; a, b ≥ 1}: Proof is by induction on j for 1 ≤ j < e. j = 1: By (1), B′(m_{1}, m_{2}) = (m_{1}, m_{2}). Then F_{e−2}^{2}B′(m_{1}, m_{2}) is given by

( \begin{matrix}e − 3 & e − 3 & e − 3 \\ m_{1} & m_{2} & 0 \end{matrix} ) ⟶^{2,e−2} ( \begin{matrix}e − 2 & e − 2 & e − 3 \\ m_{1} + 1 & m_{2} + 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 2 & e − 3 & e − 2 \\ m_{1} + 1 & m_{2} & 1 \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & e − 2 & e − 2 \\ m_{1} & m_{2} + 1 & 1 \end{matrix} )

2 ≤ j < e: Assume true for j − 1. Then F_{j−3}^{2}B′(m_{1} + j − 1, m_{2} + j − 1) is given by

( \begin{matrix}j − 4 & j − 4 & e − 3 \\ m_{1} + j − 1 & m_{2} + j − 1 & 0 \end{matrix} ) + v( \begin{matrix}j − 4 & e − 3 & j − 4 \\ m_{1} + j − 1 & m_{2} & j − 1 \end{matrix} ) +

v^{2}( \begin{matrix}e − 3 & j − 4 & j − 4 \\ m_{1} & m_{2} + j − 1 & j − 1 \end{matrix} ) ⟶^{2,j−3} ( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) +

v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & j − 3 & j − 3 \\ m_{1} & m_{2} + j & j \end{matrix} )

since e − 3 ≢ j − 3, j − 4 and m_{1} − m_{2}, m_{2} ≥ e − 1.

\underline{(4) i + j < e; a, b ≥ 1}: If j = e − 1, this case does not occur. Hence fix j with 1 ≤ j < e − 1. Proof is by induction on i for 1 ≤ i < e − j. i = 1: By (3), F_{j−2}^{1}B′(m_{1} + j, m_{2} + j) is given by

( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & j − 3 & j − 3 \\ m_{1} & m_{2} + j & j \end{matrix} )

⟶^{1,j−2} ( \begin{matrix}j − 2 & j − 3 & e − 3 \\ m_{1} + j + 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & j − 2 & e − 3 \\ m_{1} + j & m_{2} + j + 1 & 0 \end{matrix} ) +

v( \begin{matrix}j − 2 & e − 3 & j − 3 \\ m_{1} + j + 1 & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & j − 2 \\ m_{1} + j & m_{2} & j + 1 \end{matrix} ) +

v^{2}( \begin{matrix}e − 3 & j − 2 & j − 3 \\ m_{1} & m_{2} + j + 1 & j \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & j − 3 & j − 2 \\ m_{1} & m_{2} + j & j + 1 \end{matrix} )

2 ≤ i < e − j: Assume true for i − 1. Then F_{i+j−3}^{1}B′(m_{1} + i + j − 1, m_{2} + j) is given by

( \begin{matrix}i + j − 4 & j − 3 & e − 3 \\ m_{1} + i + j − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & i + j − 4 & e − 3 \\ m_{1} + j & m_{2} + i + j − 1 & 0 \end{matrix} ) +

v( \begin{matrix}i + j − 4 & e − 3 & j − 3 \\ m_{1} + i + j − 1 & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & i + j − 4 \\ m_{1} + j & m_{2} & i + j − 1 \end{matrix} ) +

v^{2}( \begin{matrix}e − 3 & i + j − 4 & j − 3 \\ m_{1} & m_{2} + i + j − 1 & j \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & j − 3 & i + j − 4 \\ m_{1} & m_{2} + j & i + j − 1 \end{matrix} )

10 SINÉAD LYLE

⟶^{1,i+j−3} ( \begin{matrix}i + j − 3 & j − 3 & e − 3 \\ m_{1} + i + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & i + j − 3 & e − 3 \\ m_{1} + j & m_{2} + i + j & 0 \end{matrix} ) +

v( \begin{matrix}i + j − 3 & e − 3 & j − 3 \\ m_{1} + i + j & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & i + j − 3 \\ m_{1} + j & m_{2} & i + j \end{matrix} ) +

v^{2}( \begin{matrix}e − 3 & i + j − 3 & j − 3 \\ m_{1} & m_{2} + i + j & j \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & j − 3 & i + j − 3 \\ m_{1} & m_{2} + j & i + j \end{matrix} )

since i + j − 4 ≢ j − 3, e − 3 and i + j − 3 ≢ j − 3, e − 3 and m_{1} − m_{2}, m_{1} ≥ e − 1.

\underline{(5) i + j = e; a, b = 1}: Note that m_{1} = m_{1} − m_{2} = e − 1. Fixing j, proof comes from (4) and (3). By (3), unless j = e − 1, F_{e−3}^{1}B′(m_{1} + e − 1, m_{2} + j) is given by

( \begin{matrix}e − 4 & e + j − 3 & e − 3 \\ m_{1} + e − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e + j − 3 & e − 4 & e − 3 \\ m_{1} + j & m_{2} + e − 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 4 & e − 3 & e + j − 3 \\ m_{1} + e − 1 & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & e − 4 \\ m_{1} + j & m_{2} & e − 1 \end{matrix} ) +

v^{2}( \begin{matrix}e − 3 & e − 4 & j − 3 \\ m_{1} & m_{2} + e − 1 & j \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & j − 3 & e − 4 \\ m_{1} & m_{2} + j & e − 1 \end{matrix} )

⟶^{1,e−3} ( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + i + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j & m_{2} + i + j & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} + i + j & m_{2} & j \end{matrix} ) +v^{2}( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} & m_{2} + j & i + j \end{matrix} ) where i + j = e.

If j = e − 1 then i = 1, and by (3) F_{j−2}^{1}B′(m_{1} + j, m_{2} + j) is given by

( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & j − 3 & j − 3 \\ m_{1} & m_{2} + j & j \end{matrix} )

⟶^{1,j−2} ( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + j + 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j & m_{2} + j + 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} + j + 1 & m_{2} & j \end{matrix} ) +v^{2}( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} & m_{2} + j & j + 1 \end{matrix} ) where 1 + j = e.

\underline{(6) i + j > e; a, b = 1}: Note that m_{2} = m_{1} −m_{2} = e−1. Case j = 1 does not occur, so fix j with 2 ≤ j < e and use induction on I for 1 ≤ I < j. I = 1 (i + j = e + 1): By (5), F_{e−2}^{1}B′(m_{1} + e, m_{2} + j) is given by

( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + i + j − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j & m_{2} + i + j − 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} + i + j − 1 & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} & m_{2} + j & i + j − 1 \end{matrix} )

⟶^{1,e−2} ( \begin{matrix}e − 2 & j − 3 & e − 3 \\ m_{1} + e + 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & j − 3 & e − 2 \\ m_{1} + e & m_{2} + j & 1 \end{matrix} ) +

v( \begin{matrix}j − 3 & e − 2 & e + j − 3 \\ m_{1} + j & m_{2} + e + 1 & 0 \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & e − 2 \\ m_{1} + j & m_{2} + e & 1 \end{matrix} ) +

v( \begin{matrix}e − 2 & e − 3 & j − 3 \\ m_{1} + e + 1 & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & e − 2 & j − 3 \\ m_{1} + e & m_{2} + 1 & j \end{matrix} ) +

v^{2}( \begin{matrix}e − 2 & e + j − 3 & e − 3 \\ m_{1} + 1 & m_{2} + j & e \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & e + j − 3 & e − 2 \\ m_{1} & m_{2} + j & e + 1 \end{matrix} )

2 ≤ I < j: Assume true for I − 1. Then F_{I−3}^{1}B′(m_{1} + e + I − 1, m_{2} + j) is given by

( \begin{matrix}I − 4 & j − 3 & e − 3 \\ m_{1} + e + I − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & j − 3 & I − 4 \\ m_{1} + e & m_{2} + j & I − 1 \end{matrix} ) +

v( \begin{matrix}j − 3 & I − 4 & e − 3 \\ m_{1} + j & m_{2} + e + I − 1 & 0 \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & I − 4 \\ m_{1} + j & m_{2} + e & I − 1 \end{matrix} ) +

v( \begin{matrix}I − 4 & e − 3 & j − 3 \\ m_{1} + e + I − 1 & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & I − 4 & j − 3 \\ m_{1} + e & m_{2} + I − 1 & j \end{matrix} ) +

v^{2}( \begin{matrix}I − 4 & j − 3 & e − 3 \\ m_{1} + I − 1 & m_{2} + j & e \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & j − 3 & I − 4 \\ m_{1} & m_{2} + j & e + I − 1 \end{matrix} )

⟶^{1,e+I−3} ( \begin{matrix}I − 3 & j − 3 & e − 3 \\ m_{1} + e + I & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & j − 3 & I − 3 \\ m_{1} + e & m_{2} + j & I \end{matrix} ) +

v( \begin{matrix}j − 3 & I − 3 & e − 3 \\ m_{1} + j & m_{2} + e + I & 0 \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & I − 3 \\ m_{1} + j & m_{2} + e & I \end{matrix} ) +

v( \begin{matrix}I − 3 & e − 3 & j − 3 \\ m_{1} + e + I & m_{2} & j \end{matrix} ) + v^{2}( \begin{matrix}e − 3 & I − 3 & j − 3 \\ m_{1} + e & m_{2} + I & j \end{matrix} ) +

v^{2}( \begin{matrix}I − 3 & j − 3 & e − 3 \\ m_{1} + I & m_{2} + j & e \end{matrix} ) + v^{3}( \begin{matrix}e − 3 & j − 3 & I − 3 \\ m_{1} & m_{2} + j & e + I \end{matrix} )

since I − 4 ≢ j − 3, e − 3 and I − 3 ≢ j − 3, e − 3 and a, b = 1.

The proof for the case i + j ≥ e where

(1) a = 1 and b ≥ 2

(2) a ≥ 2 and b = 1

(3) a, b ≥ 2

is then very similar to the proofs of (5) and (6).

Let us now assume that Theorem 3.1 holds for b = 0 and a = 1; this can be easily shown by induction. We will prove the case that b = 0 and a ≥ 2.

\underline{(7) i = 0; a = 2; b = 0}: Note that m_{2} = −1, m_{1} − m_{2} = 2e − 1. Use induction on j for 1 ≤ j < e. j = 1: By assumption, F_{e−2}^{1}B′(m_{1}, m_{2} + j) is given by

( \begin{matrix}e − 3 & e − 2 & e − 3 \\ m_{1} & 0 & 0 \end{matrix} ) + v( \begin{matrix}e − 2 & e − 3 & e − 3 \\ m_{1} + 1 − e & e − 1 & 0 \end{matrix} )

⟶^{1,e−2} ( \begin{matrix}e − 2 & e − 2 & e − 3 \\ m_{1} + 1 & 0 & 0 \end{matrix} ) + v( \begin{matrix}e − 2 & e − 3 & e − 2 \\ m_{1} + 1 − e & e − 1 & 1 \end{matrix} )

(Note m_{2} + j = 0 and m_{1} − e + 1 = e − 1.) 2 ≤ j < e: Assume true for j − 1. Then F_{j−3}^{2}B′(m_{1} + j − 1, m_{2} + j − 1) is given by

( \begin{matrix}j − 4 & j − 4 & e − 3 \\ m_{1} + j − 1 & m_{2} + j − 1 & 0 \end{matrix} ) + v( \begin{matrix}j − 4 & e − 3 & j − 4 \\ m_{1} + j − e − 1 & m_{2} + e & j − 1 \end{matrix} )

⟶^{2,j−3} ( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j − e & m_{2} + e & j \end{matrix} )

since j − 4 ≢ e − 3.

\underline{(8) i + j < e; a = 2; b = 0}: Note that m_{2} = −1, m_{1} − m_{2} = 2e − 1. Case j = e − 1 does not occur, so fix j with 1 ≤ j < e − 1 and use induction on i for 1 ≤ i < e − j. i = 1: By (7), F_{j−2}^{1}B′(m_{1} + j, m_{2} + j) is given by

( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j − e & m_{2} + e & j \end{matrix} )

⟶^{1,j−2} ( \begin{matrix}j − 2 & j − 3 & e − 3 \\ m_{1} + j + 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & j − 2 & e − 3 \\ m_{1} + j & m_{2} + j + 1 & 0 \end{matrix} ) +

v( \begin{matrix}j − 2 & e − 3 & j − 3 \\ m_{1} + j − e + 1 & m_{2} + e & j \end{matrix} ) + v^{2} ( \begin{matrix}j − 3 & e − 3 & j − 2 \\ m_{1} + j − e & m_{2} + e & j + 1 \end{matrix} )

2 ≤ i < j: Assume true for i − 1. Then F_{i+j−3}^{1}B′(m_{1} + i + j − 1, m_{2} + j) is given by

( \begin{matrix}i + j − 4 & j − 3 & e − 3 \\ m_{1} + i + j − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & i + j − 4 & e − 3 \\ m_{1} + j & m_{2} + i + j − 1 & 0 \end{matrix} ) +

v( \begin{matrix}i + j − 4 & e − 3 & j − 3 \\ m_{1} + i + j − e − 1 & m_{2} + e & j \end{matrix} ) + v^{2} ( \begin{matrix}j − 3 & e − 3 & i + j − 4 \\ m_{1} + j − e & m_{2} + e & i + j − 1 \end{matrix} )

⟶^{1,i+j−3} ( \begin{matrix}i + j − 3 & j − 3 & e − 3 \\ m_{1} + i + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & i + j − 3 & e − 3 \\ m_{1} + j & m_{2} + i + j & 0 \end{matrix} ) +

v( \begin{matrix}i + j − 3 & e − 3 & j − 3 \\ m_{1} + i + j − e & m_{2} + e & j \end{matrix} ) + v^{2} ( \begin{matrix}j − 3 & e − 3 & i + j − 3 \\ m_{1} + j − e & m_{2} + e & i + j \end{matrix} )

since i + j − 4 ≢ j − 3, e − 3 and i + j − 3 ≢ j − 3, e − 3.

\underline{(9) i + j = e; a = 2; b = 0}: Note that m_{2} = −1, m_{1} − m_{2} = 2e − 1. Fixing j, proof comes from (7) and (8). By (8), if j < e − 1, F_{e−3}^{1}B′(m_{1} + e − 1, m_{2} + j) is given by

( \begin{matrix}e − 4 & j − 3 & e − 3 \\ m_{1} + e − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 4 & e − 3 \\ m_{1} + j & m_{2} + e − 1 & 0 \end{matrix} )

+v( \begin{matrix}e − 4 & e − 3 & j − 3 \\ m_{1} − 1 & m_{2} + e & j \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & e − 4 \\ m_{1} + j − e & m_{2} + e & e − 1 \end{matrix} )

⟶^{1,e−3} ( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + i + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j & m_{2} + i + j & 0 \end{matrix} ) +

12 SINÉAD LYLE

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} + i + j − e & m_{2} + e & j \end{matrix} )

since j − 3 ≢ e − 3, e − 4. If j = e − 1 then i = 1 and by (7) F_{e−3}^{1}B′(m_{1} + j, m_{2} + j) is given by

( \begin{matrix}e − 4 & e − 4 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e − 4 & e − 3 & e − 4 \\ m_{1} + j − e & m_{2} + e & j \end{matrix} )

⟶^{1,e−3} ( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + j + 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j & m_{2} + j + 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} + j − e + 1 & m_{2} + e & j \end{matrix} ) (Note m_{2} + e = j.)

\underline{(10) i + j > e; a = 2; b = 0}: Note that m_{2} = −1, m_{1} − m_{2} = 2e − 1. Case j = 1 does not occur, so fix j with 2 ≤ j < e and use induction on I, for 1 ≤ I < j. I = 1 (i + j = e + 1): By (9), F_{e−2}^{1}B′(m_{1} + e, m_{2} + j) is given by

( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + i + j − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j & m_{2} + i + j − 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} & m_{2} + i + j − 1 & j \end{matrix} ) ⟶^{1,e−2} ( \begin{matrix}e − 2 & j − 3 & e − 3 \\ m_{1} + e + 1 & m_{2} + j & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & j − 3 & e − 2 \\ m_{1} + e & m_{2} + j & 1 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 2 & e − 3 \\ m_{1} + j & m_{2} + e + 1 & 0 \end{matrix} ) +

v^{2} ( \begin{matrix}j − 3 & e − 3 & e − 2 \\ m_{1} + j & m_{2} + e & 1 \end{matrix} ) + v ( \begin{matrix}e − 2 & e − 3 & j − 3 \\ m_{1} + 1 & m_{2} + e & j \end{matrix} ) +

v^{2}( \begin{matrix}e − 3 & e − 2 & j − 3 \\ m_{1} & m_{2} + e + 1 & j \end{matrix} )

2 ≤ I < j: Assume true for I − 1. Then F_{I−3}^{1}B′(m_{1} + e + I − 1, m_{2} + j) is given by

( \begin{matrix}I − 4 & j − 3 & e − 3 \\ m_{1} + e + I − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & j − 3 & I − 4 \\ m_{1} + e & m_{2} + j & I − 1 \end{matrix} ) +

v( \begin{matrix}j − 3 & I − 4 & e − 3 \\ m_{1} + j & m_{2} + e + I − 1 & 0 \end{matrix} ) + v^{2}( \begin{matrix}j − 3 & e − 3 & I − 4 \\ m_{1} + j & m_{2} + e & I − 1 \end{matrix} ) +

v ( \begin{matrix}I − 4 & e − 3 & j − 3 \\ m_{1} + I − 1 & m_{2} + e & j \end{matrix} ) + v^{2} ( \begin{matrix}e − 3 & I − 4 & j − 3 \\ m_{1} & m_{2} + e + I − 1 & j \end{matrix} )

⟶^{1,I−3} ( \begin{matrix}I − 3 & j − 3 & e − 3 \\ m_{1} + e + I & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}e − 3 & j − 3 & I − 3 \\ m_{1} + e & m_{2} + j & I \end{matrix} ) +

v( \begin{matrix}j − 3 & I − 3 & e − 3 \\ m_{1} + j & m_{2} + e + I & 0 \end{matrix} ) + v^{2} ( \begin{matrix}j − 3 & e − 3 & I − 3 \\ m_{1} + j & m_{2} + e & I \end{matrix} ) +

v ( \begin{matrix}I − 3 & e − 3 & j − 3 \\ m_{1} + I & m_{2} + e & j \end{matrix} ) + v^{2} ( \begin{matrix}e − 3 & I − 3 & j − 3 \\ m_{1} & m_{2} + e + I & j \end{matrix} )

since I − 4 ≢ j − 3, e − 3 and I − 3 ≢ j − 3, e − 3.

\underline{(11) a > 2; b = 0}: We only need to prove the case when a = 3, i = 0, j = 1. The proof for all other cases of a = 3, b = 0 then follows exactly from (7 − 10) above, and the case a > 3 follows by an obvious induction. By (9), F_{e−2}^{1}B′(m_{1} + j − 1, m_{2} + j) is given by

( \begin{matrix}e − 3 & j − 3 & e − 3 \\ m_{1} + j − 1 & m_{2} + j & 0 \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & e − 3 \\ m_{1} + j − e & m_{2} + j + e − 1 & 0 \end{matrix} ) +

v( \begin{matrix}e − 3 & e − 3 & j − 3 \\ m_{1} + j − e − 1 & m_{2} + e & j \end{matrix} )

⟶^{1,e−2} ( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j & m_{2} + j & 0 \end{matrix} ) + ( \begin{matrix}j − 3 & j − 3 & e − 3 \\ m_{1} + j − e & m_{2} + j + e & 0 \end{matrix} ) +

v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j − e & m_{2} + e & j \end{matrix} ) + v( \begin{matrix}j − 3 & e − 3 & j − 3 \\ m_{1} + j − e & m_{2} + e & j \end{matrix} ) +

v^{2} ( \begin{matrix}e − 3 & j − 3 & j − 3 \\ m_{1} − e & m_{2} + e + j & j \end{matrix} )

The coefficient of (m_{1} + j − e, m_{2} + j + e, 0) is equal to 1 so this equation is not of the correct form. However, by (3) B′(m_{1} + j − e, m_{2} + j + e, 0) is given by

(m_{1} + j − e, m_{2} + j + e) + v(m_{1} + j − e, m_{2} + e, j) + v^{2}(m_{1} − e, m_{2} + e + j, j).

Hence

B′(m_{1} + j, m_{2} + j) = (m_{1} + j, m_{2} + j) + v(m_{1} + j − e, m_{2} + e, j).
□

We now use the information from Theorem 3.1 to deduce the following Theorem.

Theorem 3.6. Let e > 3. (See Remark 3.8.) Consider the Specht module S^{(μ_{1},μ_{2},μ_{3})}. For x ∈ ℕ, define |x| such that |x| ≡ x mod e and 0 ≤ |x| < e. Let

l = |μ_{1} + 2|
k = |μ_{2} + 1|
s = |μ_{3}|

and let the following shorthand denote the given inequalities:

• α := μ_{2} − μ_{3} < e − 1

• β := μ_{2} − μ_{3} > e − 1

• γ := μ_{1} − μ_{2} < e − 1

• δ := μ_{1} − μ_{2} > e − 1 Label the partitions with at most 3 parts which correspond to the irreducible

modules as follows.

(1) (μ_{1}, μ_{2}, μ_{3})

(2) (μ_{1} − l + k, μ_{2} + l − k, μ_{3})

(3) (μ_{1} − l + k + e, μ_{2} + l − k − e, μ_{3})

(4) (μ_{1} − l + k, μ_{2} − k + s, μ_{3} + l − s)

(5) (μ_{1} − l + k + e, μ_{2} − k + s − e, μ_{3} + l − s)

(6) (μ_{1} − l + s, μ_{2}, μ_{3} + l − s)

(7) (μ_{1}, μ_{2} − k + s, μ_{3} + k − s)

(8) (μ_{1} + e, μ_{2} − k + s − e, μ_{3} + k − s)

(9) (μ_{1} − l + s, μ_{2} + l − k, μ_{3} + k − s)

(10) (μ_{1} − l + s + e, μ_{2} + l − k − e, μ_{3} + k − s)

(11) (μ_{1} − l + k, μ_{2} − k + s + e, μ_{3} + l − s − e)

(12) (μ_{1} − l + k + e, μ_{2} − k + s, μ_{3} + l − s − e)

(13) (μ_{1} − l + k + 2e, μ_{2} − k + s − e, μ_{3} + l − s − e)

(14) (μ_{1} − l + s + e, μ_{2}, μ_{3} + l − s − e)

(15) (μ_{1}, μ_{2} − k + s + e, μ_{3} + k − s − e)

(16) (μ_{1} + e, μ_{2} − k + s, μ_{3} + k − s − e)

(17) (μ_{1} − l + s, μ_{2} + e + l − k, μ_{3} + k − s − e)

(18) (μ_{1} − l + s + e, μ_{2} + l − k, μ_{3} + k − s − e)

(19) (μ_{1} − l + s + 2e, μ_{2} + l − k − e, μ_{3} + k − s − e)

(20) (μ_{1} − l + k + e, μ_{2} − k + s + e, μ_{3} + l − s − 2e)

(21) (μ_{1} − l + s + 2e, μ_{2}, μ_{3} + l − s − 2e)

(22) (μ_{1} − l + s + e, μ_{2} + l − k + e, μ_{3} + k − s − 2e)

(23) (μ_{1} + e, μ_{2}, μ_{3} − e)

(24) (μ_{1} − l + k, μ_{2} + l − k + e, μ_{3} − e)

(25) (μ_{1} − l + k + e, μ_{2} + l − k, μ_{3} − e) The composition factors of S^{(μ_{1},μ_{2},μ_{3})} are given by the following tables. All the

partitions listed in 1 − 25 above are distinct, and each composition factor occurs with multiplicity 1.

14 SINÉAD LYLE

\underline{A : μ_{3} = 0}

1  2  3
l = k  ⋆
k > l = 0 μ_{2} < e − 1 ⋆
μ_{2} > e − 1 ⋆  ⋆
k > l > 0  ⋆  ⋆
l > k  μ_{2} < e − 1 ⋆
μ_{2} ≥ e − 1 ⋆  ⋆

\underline{B : 1 ≤ μ_{3} < e}

1  2  3  4  5  6  7  8  9  10
l = k = s  ⋆
l = k > s  ⋆
s > l = k  ⋆  ⋆  ⋆  ⋆
l > k = s  ⋆  ⋆
k = s > l  ⋆  ⋆  ⋆
k > l = s α  ⋆
β  ⋆  ⋆
l = s > k α  γ  ⋆  ⋆
α  δ  ⋆  ⋆  ⋆
β  γ  ⋆  ⋆
β  δ  ⋆  ⋆  ⋆
k > l > s  ⋆  ⋆
l > s > k α  ⋆  ⋆  ⋆  ⋆  ⋆
β  ⋆  ⋆  ⋆  ⋆
s > k > l α  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
β  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
l > k > s α  ⋆
β  ⋆  ⋆
k > s > l α  ⋆  ⋆
β  ⋆  ⋆  ⋆  ⋆
s > l > k α  γ  ⋆  ⋆  ⋆
α  δ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
β  γ  ⋆  ⋆  ⋆  ⋆
β  δ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆

\underline{C : μ_{3} = e}

1  2  3  11 12 14 15 16 18 19 23 24 25
l = k = 0  ⋆
l = k > 0  ⋆  ⋆  ⋆  ⋆
l > k = 0  ⋆  ⋆  ⋆  ⋆
k > l = 0 α  γ  ⋆  ⋆  ⋆  ⋆
α  δ  ⋆  ⋆  ⋆  ⋆
β  γ  ⋆  ⋆  ⋆  ⋆
β  δ  ⋆  ⋆  ⋆  ⋆
l > k > 0 α  γ  ⋆  ⋆  ⋆
α  δ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
β  γ  ⋆  ⋆  ⋆  ⋆  ⋆
β  δ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
k > l > 0 α  γ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
α  δ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
β  γ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆
β  δ  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆  ⋆

\underline{D : e < μ_{3} < 2e}_{\begin{aligned}& & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 23 & 24 & 25 \\ l = k = s & & & ⋆ \\ l = k > s & & & ⋆ & & & & & & & & & & & & & ⋆ & ⋆ & ⋆ \\ s > l = k & & & ⋆ & & & & & ⋆ & ⋆ & ⋆ \\ l > k = s & & & ⋆ & & ⋆ & & & & & & & & & & & ⋆ & & & & & & & & ⋆ \\ k = s > l & & & ⋆ & ⋆ & & & & ⋆ & & & & & & & & & & & & & & & ⋆ \\ k > l = s & α & γ & ⋆ & & & & & & & & & & & & & & & ⋆ & & & & ⋆ & ⋆ \\ & α & δ & ⋆ & & & & & & & & & & & & & & ⋆ & ⋆ & & & & ⋆ \\ & β & γ & ⋆ & ⋆ & & & & & & & & & & & & & & & & & & ⋆ & ⋆ \\ & β & δ & ⋆ & ⋆ & & & & & & & & & & & & & ⋆ & & & & & ⋆ \\ s = l > k & α & γ & ⋆ & & & & & & & ⋆ & & & & & & & & & & & & ⋆ & & ⋆ \\ & α & δ & ⋆ & & & & & & ⋆ & ⋆ & & & & & & & & & & & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & & & & & & & & & & & & & & & & ⋆ & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & & & ⋆ & & & & & & & & & & & & & ⋆ \\ l > k > s & α & γ & ⋆ & & & & & & & & & & & & & ⋆ & & & & & ⋆ \\ & α & δ & ⋆ & & & & & & & & & & & & & ⋆ & ⋆ & ⋆ & & ⋆ & ⋆ \\ & β & γ & ⋆ & & ⋆ & & & & & & & & & ⋆ & & ⋆ & & & & & & & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & & & & & & & & ⋆ & & ⋆ & ⋆ & ⋆ & & ⋆ & & & & ⋆ \\ k > s > l & α & γ & ⋆ & & & & & ⋆ & & & & & ⋆ & & & ⋆ & & & & ⋆ \\ & α & δ & ⋆ & & & & & ⋆ & & & & & & & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ \\ & β & γ & ⋆ & ⋆ & & ⋆ & & ⋆ & & & & & ⋆ & & & ⋆ & & & & & & & ⋆ \\ & β & δ & ⋆ & ⋆ & & ⋆ & & ⋆ & & & & & & & & ⋆ & ⋆ & ⋆ & ⋆ & & & & ⋆ \\ s > l > k & α & γ & ⋆ & & & & & ⋆ & & & & ⋆ & & ⋆ & & ⋆ \\ & α & δ & ⋆ & & & & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & ⋆ & ⋆ & & & & & & ⋆ & & ⋆ & & & & & & & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & & ⋆ & & & & & & & & ⋆ \\ k > l > s & α & γ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & & ⋆ & & ⋆ & ⋆ \\ & α & δ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & & ⋆ & & ⋆ \\ & β & γ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & & & ⋆ & & ⋆ & ⋆ \\ & β & δ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & & & ⋆ & & ⋆ \\ l > s > k & α & γ & ⋆ & & ⋆ & & & & ⋆ & ⋆ & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & ⋆ & & ⋆ \\ & α & δ & ⋆ & & ⋆ & & & & ⋆ & ⋆ & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & & & ⋆ & & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & ⋆ & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & & & ⋆ & & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & ⋆ \\ s > k > l & α & γ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & & & & & ⋆ & & & ⋆ & ⋆ \\ & α & δ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & & & & & ⋆ & & & ⋆ \\ & β & γ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & & ⋆ & & & & & & & & ⋆ & & & ⋆ & ⋆ \\ & β & δ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & & ⋆ & & & & & & & & ⋆ & & & ⋆ \end{aligned}}

\underline{E : μ_{3} ≥ 2e}_{\begin{aligned}& & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ l = k = s & & & ⋆ \\ l = k > s & & & ⋆ & & & & & & & & & & & & & ⋆ & ⋆ & ⋆ \\ s > l = k & & & ⋆ & & & & & ⋆ & ⋆ & ⋆ \\ l > k = s & & & ⋆ & & ⋆ & & & & & & & & & & & ⋆ & & & & & & & & & & & ⋆ \\ k = s > l & & & ⋆ & ⋆ & & & & ⋆ & & & & & & & & & & & & & & & & & & ⋆ \\ k > l = s & α & γ & ⋆ & & & & & & & & & & & & & & & ⋆ & & & & & & & ⋆ & ⋆ \\ & α & δ & ⋆ & & & & & & & & & & & & & & ⋆ & ⋆ & & & & & & & ⋆ \\ & β & γ & ⋆ & ⋆ & & & & & & & & & & & & & & & & & & & & & ⋆ & ⋆ \\ & β & δ & ⋆ & ⋆ & & & & & & & & & & & & & ⋆ & & & & & & & & ⋆ \\ s = l > k & α & γ & ⋆ & & & & & & & ⋆ & & & & & & & & & & & & & & & ⋆ & & ⋆ \\ & α & δ & ⋆ & & & & & & ⋆ & ⋆ & & & & & & & & & & & & & & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & & & & & & & & & & & & & & & & & & & ⋆ & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & & & ⋆ & & & & & & & & & & & & & & & & ⋆ \\ l > k > s & α & γ & ⋆ & & & & & & & & & & & & & ⋆ & & & & & ⋆ & ⋆ & ⋆ \\ & α & δ & ⋆ & & & & & & & & & & & & & ⋆ & ⋆ & ⋆ & & ⋆ & ⋆ & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & & & & & & & & ⋆ & & ⋆ & & & & & & ⋆ & ⋆ & & & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & & & & & & & & ⋆ & & ⋆ & ⋆ & ⋆ & & ⋆ & & & ⋆ & & & & ⋆ \\ k > s > l & α & γ & ⋆ & & & & & ⋆ & & & & & ⋆ & & & ⋆ & & & & ⋆ \\ & α & δ & ⋆ & & & & & ⋆ & & & & & & & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ \\ & β & γ & ⋆ & ⋆ & & ⋆ & & ⋆ & & & & & ⋆ & & & ⋆ & & & & & & & & & & ⋆ \\ & β & δ & ⋆ & ⋆ & & ⋆ & & ⋆ & & & & & & & & ⋆ & ⋆ & ⋆ & ⋆ & & & & & & & ⋆ \\ s > l > k & α & γ & ⋆ & & & & & ⋆ & & & & ⋆ & & ⋆ & & ⋆ \\ & α & δ & ⋆ & & & & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & ⋆ & ⋆ & & & & & & ⋆ & & ⋆ & & & & & & & & & & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & & ⋆ & & & & & & & & & & & ⋆ \\ k > l > s & α & γ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & & ⋆ & & & & ⋆ & ⋆ & ⋆ \\ & α & δ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & & ⋆ & & & & ⋆ & ⋆ \\ & β & γ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & & & ⋆ & & & & ⋆ & ⋆ & ⋆ \\ & β & δ & ⋆ & ⋆ & & & & & & & & & ⋆ & ⋆ & & ⋆ & ⋆ & & & ⋆ & & & & ⋆ & ⋆ \\ l > s > k & α & γ & ⋆ & & ⋆ & & & & ⋆ & ⋆ & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & & & & ⋆ & & ⋆ \\ & α & δ & ⋆ & & ⋆ & & & & ⋆ & ⋆ & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & & & & ⋆ \\ & β & γ & ⋆ & & ⋆ & & & & ⋆ & & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & & & & ⋆ & & ⋆ \\ & β & δ & ⋆ & & ⋆ & & & & ⋆ & & & ⋆ & & ⋆ & ⋆ & ⋆ & & & & ⋆ & & & & & ⋆ \\ s > k > l & α & γ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & & & & & ⋆ & & & & & & ⋆ & ⋆ \\ & α & δ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & ⋆ & & & & & & & & ⋆ & & & & & & ⋆ \\ & β & γ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & & ⋆ & & & & & & & & ⋆ & & & & & & ⋆ & ⋆ \\ & β & δ & ⋆ & ⋆ & & ⋆ & ⋆ & ⋆ & ⋆ & & ⋆ & & & & & & & & ⋆ & & & & & & ⋆ \end{aligned}}

APPLYING THE LLT ALGORITHM 17

The proof uses the following Lemma, in which, for a Specht module S^{μ}, we note the composition factors of S^{μ} which correspond to partitions with at most 2 parts. (As previously noted, the multiplicity of each such composition factor is 1.) Lemma 3.7. Let e ≥ 3 and μ = (μ_{1}, μ_{2}, μ_{3}). We use the notation of Theorem 3.6. Suppose μ_{3} = 0. Then

(1) If l = k then S^{(μ_{1},μ_{2})} has a composition factor D^{(μ_{1},μ_{2})}.

(2) If l > k and μ_{2} < e − 1 then S^{(μ_{1},μ_{2})} has a composition factor D^{(μ_{1},μ_{2})}.

(3) If l > k and μ_{2} ≥ e − 1 then S^{(μ_{1},μ_{2})} has composition factors D^{(μ_{1},μ_{2})} and D^{(μ_{1}+k−l+e,μ_{2}−k+l−e)}.

(4) If k > l = 0 and μ_{2} > e − 1 then S^{(μ_{1},μ_{2})} has composition factors D^{(μ_{1},μ_{2})} and D^{(μ_{1}+k−l,μ_{2}−k+l)}.

(5) If k > l = 0 and μ_{2} < e−1 then S^{(μ_{1},μ_{2})} has a composition factors D^{(μ_{1},μ_{2})}.

(6) If k > l > 0 then S^{(μ_{1},μ_{2})} has composition factors D^{(μ_{1},μ_{2})} and D^{(μ_{1}+k−l,μ_{2}−k+l)}. Suppose 0 < μ_{3} < e and l = k = 0. Then

(1) S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1},μ_{2}+μ_{3})}, D^{(μ_{1}+e,μ_{2}+μ_{3}−e)} and D^{(μ_{1}+μ_{3},μ_{2})}. Suppose 0 < μ_{3} < e and l = 0 and k ≠ 0. Then

(1) If s = k then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3},μ_{2})}.

(2) If s > k then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1}+k+e,μ_{2}+μ_{3}−e−k)}, D^{(μ_{1}+μ_{3},μ_{2})} and D^{(μ_{1}+k,μ_{2}+μ_{3}−k)}.

(3) If k > s and μ_{2} < e−1 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3},μ_{2})}.

(4) If k > s and μ_{2} > e−1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1}+k,μ_{2}+μ_{3}−k)}

and D^{(μ_{1}+μ_{3},μ_{2})}. Suppose 0 < μ_{3} < e and l ≠ 0 and k = 0. Then

(1) If s = l and μ_{2} = e−1 and μ_{1} −μ_{2} > e−1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1},μ_{2}+μ_{3})} and D^{(μ_{1}+e,μ_{2}+μ_{3}−e)}.

(2) If s = l and μ_{2} = e−1 and μ_{1}−μ_{2} < e−1 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+e,μ_{2}+μ_{3}−e)}.

(3) If s = l and μ_{2} ≠ e−1 and μ_{1}−μ_{2} > e−1 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1},μ_{2}+μ_{3})}.

(4) If s > l and μ_{2} = e−1 and μ_{1} −μ_{2} > e−1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1},μ_{2}+μ_{3})}, D^{(μ_{1}+e,μ_{2}+μ_{3}−e)}, D^{(μ_{1}+μ_{3}−l,μ_{2}+l)} and D^{(μ_{1}+μ_{3}+e−l,μ_{2}−e+l)}.

(5) If s > l and μ_{2} = e−1 and μ_{1}−μ_{2} < e−1 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3}+e−l,μ_{2}−e+l)}.

(6) If s > l and μ_{2} ≠ e−1 and μ_{1} −μ_{2} > e−1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1},μ_{2}+μ_{3})}, D^{(μ_{1}+e,μ_{2}+μ_{3}−e)} and D^{(μ_{1}+μ_{3}−l,μ_{2}+l)}.

(7) If l > s and μ_{2} = e−1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1},μ_{2}+μ_{3})}, D^{(μ_{1}+e,μ_{2}+μ_{3}−e)} and D^{(μ_{1}+μ_{3}+e−l,μ_{2}−e+l)}.

(8) If l > s and μ_{2} ≠ e − 1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1},μ_{2}+μ_{3})}

and D^{(μ_{1}+μ_{3}+e−l,μ_{2}−e+l)}. Suppose μ_{3} = e. Then

(1) If k > l > 0 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3},μ_{2})}.

(2) If k > l > 0 and μ_{1} − μ_{2} < e − 1 then S^{(μ_{1},μ_{2},μ_{3})} also has a composition factor D^{(μ_{1}−l+k,μ_{2}+μ_{3}−k+l)}.

(3) If l > k > 0 and μ_{2} > 2e − 1 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3}−l+k,μ_{2}−k+l)}.

(4) If k > l = 0 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3},μ_{2})}.

(5) If k > l = 0 and μ_{1} − μ_{2} < e − 1 then S^{(μ_{1},μ_{2},μ_{3})} also has a composition

factor D^{(μ_{1}+k,μ_{2}+μ_{3}−k)}.

(6) If l > k = 0 and then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3}−l,μ_{2}+l)}. Suppose e < μ_{3} < 2e − 1. Then

(1) If l = 0 and k > s then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3},μ_{2})}.

(2) If l = 0 and k > s and μ_{1}−μ_{2} < e−1 then S^{(μ_{1},μ_{2},μ_{3})} also has a composition

factor D^{(μ_{1}+k,μ_{2}+μ_{3}−k)}.

(3) If k = 0 and l > s then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+μ_{3}−l,μ_{2}+l)}. Moreover, only the above Specht modules contain composition factors correspond-

ing to 1 or 2 part partitions and these contain only the 1 or 2 part composition factors listed above.

Proof. The proof follows by consideration of Theorem 3.1. We shall now describe the situation whenever μ_{3} > e; the other cases follow similarly.

Consider S^{(μ_{1},μ_{2},μ_{3})} where μ_{3} > e. We wish to determine which partitions λ = (λ_{1}, λ_{2}) are such that D^{λ} is a composition factor of S^{μ}. Write λ = (m_{1}+i+j, m_{2}+j), as in the notation of Theorem 3.1. Then μ is of one of the following forms:

(m_{1} + j, m_{2}, e + I),
(m_{1}, m_{2} + j, e + I),
(m_{1}, m_{2} + i + j − e, e + j).

Now suppose λ = (m_{1} + e + I, m_{2} + j), as in the notation of Theorem 3.1, and μ = (m_{1} + j, m_{2}, e + I). Then S^{μ} has a composition factor D^{λ} if and only if λ satisfies b ≥ 2 and i + j > e. However λ is a partition such that b ≥ 2 and i + j > e if and only if μ = (m_{1} + j, m_{2}, e + I) is a partition such that, in the notation of Theorem 3.6, k = 0 and l > s and e < μ_{3} < 2e − 1. Then

λ = (m_{1} + e + I, m_{2} + j) = (μ_{1} + μ_{3} − l, μ_{2} + l).

Hence if μ = (μ_{1}, μ_{2}, μ_{3}) satisfies e < μ_{3} < 2e − 1 and k = 0 and l > s then S^{μ} has a composition factor D^{(μ_{1}+μ_{3}−l,μ_{2}+l)}.

Now, if λ = (m_{1} + e + I, m_{2} + j) and μ = (m_{1}, m_{2} + j, e + I) then S^{μ} has a composition factor D^{λ} if and only if λ satisfies a, b ≥ 1 and i + j > e. Moreover, λ = (m_{1} + i + j, m_{2} + j) is a partition such that a, b ≥ 1 and i + j > e if and only if μ = (m_{1} +j, m_{2}, e+I) is a partition such that l = 0 and k > s and e < μ_{3} < 2e−1. Hence if μ = (μ_{1}, μ_{2}, μ_{3}) satisfies e < μ_{3} < 2e − 1 and l = 0 and k > s then S^{μ} has a composition factor D^{(μ_{1}+μ_{3},μ_{2})}.

Finally, if λ = (m_{1} + i + j, m_{2} + j) and μ = (m_{1}, m_{2} + i + j − e, e + j) then S^{μ} has a composition factor D^{λ} if and only if λ satisfies a = 0 and b ≥ 2 and i + j < e. Moreover, λ is a partition such that a = 0 and b ≥ 2 and i + j < e if and only if μ = (m_{1}, m_{2} + i + j − e, e + j) is a partition such that l = 0 and k > s and μ_{1} − μ_{2} < e − 1 and e < μ_{3} < 2e − 1. Hence if μ = (μ_{1}, μ_{2}, μ_{3}) satisfies e < μ_{3} < 2e−1 and l = 0 and k > s and μ_{1} −μ_{2} < e−1 then S^{μ} has a composition factor D^{(μ_{1}+k,μ_{2}+μ_{3}−k)}.

□

The proof of Theorem 3.6 can then be deduced from Lemma 3.7 and Theorem 3.4 (the column addition theorem). We give some examples.

Example. Suppose that μ = (μ_{1}, μ_{2}, μ_{3}) is such that s > l = k and 1 ≤ μ_{3} < e. Then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(λ_{1},λ_{2},λ_{3})} if and only if μ_{3} ≥ λ_{3} and S^{(μ_{1}−λ_{3},μ_{2}−λ_{3},μ_{3}−λ_{3})} has a composition factor D^{(λ_{1}−λ_{3},λ_{2}−λ_{3})}. Fix α with 0 ≤ α ≤ μ_{3} and let

ν = (ν_{1}, ν_{2}, ν_{3}) = (μ_{1} − α, μ_{2} − α, μ_{3} − α).

Now by Lemma 3.7, if S^{ν} has a composition factor D^{(ξ_{1},ξ_{2})} then either α = μ_{3} or α = l = k.

If α = μ_{3} then S^{(ν_{1},ν_{2})} has a composition factor D^{(ν_{1},ν_{2})}. Hence S^{(μ_{1},μ_{2},μ_{3})} has a composition factor

D^{(μ_{1},μ_{2},μ_{3})}.

If α = l = k then S^{(ν_{1},ν_{2},ν_{3})} has composition factors

D^{(ν_{1},ν_{2}+ν_{3})}, D^{(ν_{1}+e,ν_{2}+ν_{3}−e)} and D^{(ν_{1}+ν_{3},ν_{2})}.

Hence (noting that μ_{3} = s and l = k), S^{(μ_{1},μ_{2},μ_{3})} has composition factors

D^{(μ_{1},μ_{2}+s−k,μ_{3}−s+k)}, D^{(μ_{1}+e,μ_{2}+s−k+e,μ_{3}−s+k)} and D^{(μ_{1}+s−l,μ_{2},μ_{3}−s+l)}.

These are all the composition factors of S^{μ}.

Example. Assume that the results of Theorem 3.6 hold for 0 ≤ μ_{3} ≤ e hold, and suppose that μ = (μ_{1}, μ_{2}, μ_{3}) is such that l > k = s and μ_{3} > e. Let

ν = (ν_{1}, ν_{2}, ν_{3}) = (μ_{1} − μ_{3} + e, μ_{2} − μ_{3} + e, e)

and define l′ = |ν_{1} + 2|; then l′ = l − k. Then S^{(ν_{1},ν_{2},ν_{3})} has composition factors

D^{(ν_{1},ν_{2},ν_{3})}  D^{(ν_{1}−l′+e,ν_{2}+l′−e,ν_{3})}
D^{(ν_{1}−l′+e,ν_{2},ν_{3}+l′−e)}  D^{(ν_{1}−l′+e,ν_{2}+l′,ν_{3}−e)}.

Hence S^{(μ_{1},μ_{2},μ_{3})} has composition factors

D^{(μ_{1},μ_{2},μ_{3})}  D^{(μ_{1}−l+k+e,μ_{2}+l−k−e,μ_{3})}
D^{(μ_{1}−l+k+e,μ_{2},μ_{3}+l−k−e)}  D^{(μ_{1}−l−k+e,μ_{2}+l−k,μ_{3}−e)}.

These are all the composition factors of S^{μ}.

Remark 3.8. If e = 3, Theorem 3.6 holds in all cases except whenever λ = (m, m, m). Then S^{λ} does not contain a composition factor D^{λ} (= 0), but all other entries are consistent. If e = 2 then Theorem 3.6 will give all the composition factors of any Specht module S^{(λ_{1},λ_{2},λ_{3})}, but may also produce some 2-singular (zero) composition factors. We now consider this situation in more detail. While the truncated columns B′(λ) when e = 2 were classified (using other methods) by James and Mathas in 1996 [3], the composition factors of the Specht modules were never explicitly computed.

We first produce an analogue of Lemma 3.7. Note that all the composition factors must be 2-regular, and let ≡ denote equivalence mod 2.

Lemma 3.9. Let e = 2.

Suppose μ_{3} = 0. Then (1) If μ_{1} > μ_{2} then S^{(μ_{1},μ_{2})} has a composition factor D^{(μ_{1},μ_{2})}.

(2) If μ_{1} ≡ μ_{2} and μ_{2} ≠ 0 then S^{(μ_{1},μ_{2})} has a composition factor D^{(μ_{1}+1,μ_{2}−1)}.

Suppose μ_{3} = 1. Then

(1) If μ_{1} ≡ 0 and μ_{2} ≡ 1 then S^{(μ_{1},μ_{2},μ_{3})} has composition factors D^{(μ_{1}+1,μ_{2})} and D^{(μ_{1}+2,μ_{2}−1)}.

(2) If μ_{1} ≡ 0 and μ_{2} ≡ 1 and μ_{1}−μ_{2} > 1 then S^{(μ_{1},μ_{2},μ_{3})} also has a composition factor D^{(μ_{1},μ_{2}+1)}.

(3) If μ_{1} ≡ μ_{2} ≡ 0 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+1,μ_{2})}.

(4) If μ_{1} ≡ μ_{2} ≡ 1 and μ_{1} − μ_{2} ≠ 0 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1},μ_{2}+1)}.

(5) If μ_{1} ≡ μ_{2} ≡ 1 and μ_{2} = 1 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor

D^{(μ_{1}+2,μ_{2}−1)}. Suppose μ_{3} = 2. Then

(1) If μ_{1} ≡ μ_{2} ≡ 0 then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+2,μ_{2})}.

(2) If μ_{1} ≡ μ_{2} ≡ 1 and μ_{1} > μ_{2} then S^{(μ_{1},μ_{2},μ_{3})} has a composition factor D^{(μ_{1}+1,μ_{2}+1)}.

Moreover, only the above Specht modules contain composition factors corresponding to 1 or 2 part partitions and these contain only the 1 or 2 part composition factors listed above.

Using Lemma 3.9 and the column addition theorem, we may deduce the following analogue of Theorem 3.6. We will use the more convenient notation of [3].

Theorem 3.10. Let e = 2 and suppose (μ_{1}, μ_{2}, μ_{3}) ≡ (α_{1}, α_{2}, α_{3}) mod 2. Label the partitions (λ_{1}, λ_{2}, λ_{3}) corresponding to the irreducible modules as follows.

(1) (μ_{1}, μ_{2})

(2) (μ_{1} + 1, μ_{2} − 1)

(3) (μ_{1}, μ_{2}, μ_{3})

(4) (μ_{1} + 1, μ_{2} − 1, μ_{3})

(5) (μ_{1}, μ_{2} + 1, μ_{3} − 1)

(6) (μ_{1} + 1, μ_{2}, μ_{3} − 1)

(7) (μ_{1} + 2, μ_{2} − 1, μ_{3} − 1)

(8) (μ_{1} + 1, μ_{2} + 1, μ_{3} − 2)

(9) (μ_{1} + 2, μ_{2}, μ_{3} − 2) The composition factors of S^{(μ_{1},μ_{2},μ_{3})} are given by the following tables. All the partitions listed in 1 − 9 above are distinct, and each composition factor occurs with multiplicity 1.

\underline{A : μ_{2} = 0} Then S^{(μ_{1})} ≅ D^{(μ_{1})}.

\underline{B : μ_{2} ≥ 1, μ_{3} = 0}

(0, 1) or (1, 0) ⋆
(0, 0) or (1, 1) ⋆  ⋆

(α_{1}, α_{2})  1  2

\underline{C : μ_{3} = 1}

(α_{1}, α_{2}, α_{3})  3  4  5  6  7
(1, 1, 1)  μ_{1} > μ_{2}  μ_{2} > μ_{3}  ⋆  ⋆  ⋆
μ_{2} = μ_{3}  ⋆  ⋆
μ_{1} = μ_{2}  μ_{2} > μ_{3}  ⋆
μ_{2} = μ_{3}  ⋆
(0, 0, 1)  μ_{1} > μ_{2}  μ_{2} > μ_{3} + 1 ⋆  ⋆  ⋆
μ_{2} = μ_{3} + 1 ⋆  ⋆
μ_{1} = μ_{2}  μ_{2} > μ_{3} + 1  ⋆  ⋆
μ_{2} = μ_{3} + 1  ⋆
(0, 1, 1)  μ_{1} > μ_{2} + 1 μ_{2} > μ_{3}  ⋆  ⋆  ⋆  ⋆
μ_{2} = μ_{3}  ⋆  ⋆
μ_{1} = μ_{2} + 1 μ_{2} > μ_{3}  ⋆  ⋆  ⋆
μ_{2} = μ_{3}  ⋆
(1, 0, 1)  ⋆

\underline{D : μ_{3} ≥ 2}

(α_{1}, α_{2}, α_{3})  3  4  5  6  7  8  9
(0, 0, 0) or (1, 1, 1) μ_{1} > μ_{2}  μ_{2} > μ_{3}  ⋆  ⋆  ⋆  ⋆
μ_{2} = μ_{3}  ⋆  ⋆
μ_{1} = μ_{2}  μ_{2} > μ_{3}  ⋆  ⋆
μ_{2} = μ_{3}  ⋆
(0, 0, 1) or (1, 1, 0) μ_{1} > μ_{2}  μ_{2} > μ_{3} + 1 ⋆  ⋆  ⋆  ⋆
μ_{2} = μ_{3} + 1 ⋆  ⋆  ⋆
μ_{1} = μ_{2}  μ_{2} > μ_{3} + 1  ⋆  ⋆
μ_{2} = μ_{3} + 1  ⋆
(1, 0, 0) or (0, 1, 1) μ_{1} > μ_{2} + 1 μ_{2} > μ_{3}  ⋆  ⋆  ⋆  ⋆
μ_{2} = μ_{3}  ⋆  ⋆
μ_{1} = μ_{2} + 1 μ_{2} > μ_{3}  ⋆  ⋆  ⋆
μ_{2} = μ_{3}  ⋆
(0, 1, 0) or (1, 0, 1)  ⋆

4. Partitions with at most four parts

Now that we have obtained the composition factors for all Specht modules corresponding to partitions with at most three parts, it is pertinent to ask whether the same methods will work for partitions with four parts, or indeed for s parts for any integer s. It has been shown [5] that for four part partitions this is indeed true; however the analogue of Theorem 3.1, written in the form of tables, takes up some 68 pages. We will not reproduce them here! However, we give a quick indication of the notation used.

Let 2 ≤ e < ∞ and suppose λ = (λ_{1}, λ_{2}, λ_{3}) is a one, two or three part e-regular partion of (λ_{1} + λ_{2} + λ_{3}) = n. Suppose that

λ_{1} − λ_{2} = ae + i − 1
λ_{2} − λ_{3} = be + j − 1
λ_{3} = ce + k − 1

where 0 ≤ i, j, k < e. Define

m_{3} = ce − 1
m_{2} − m_{3} = be − 1
m_{1} − m_{2} = ae − 1

so that λ = (m_{1} + i + j + k, m_{2} + j + k, m_{3} + k). The column B′_{4}(λ) depends on the integers a, b, c, and on which of the following identities holds for i, j, k. Assume that i, j, k > 0 unless otherwise stated.

• i, j, k = 0  • i + j + k < e
• j, k = 0  • i + j + k = e
• i, k = 0  • i + j < e, j + k < e, i + j + k > e
• k = 0, i + j < e  • i + j = e, j + k < e
• k = 0, i + j = e  • i + j > e, j + k < e
• k = 0, i + j > e  • i + j < e, j + k = e
• i, j = 0  • i + j = e, j + k = e
• j = 0, i + k < e  • i + j > e, j + k = e
• j = 0, i + k = e  • i + j < e, j + k > e
• j = 0, i + k > e  • i + j = e, j + k > e
• i = 0, j + k < e  • i + j > e, j + k > e, i + j + k < 2e
• i = 0, j + k = e  • i + j + k = 2e
• i = 0, j + k > e  • i + j + k > 2e

The results can be used to show that the maximum multiplicity of a composition factor D^{λ} in a Specht module S^{(μ_{1},μ_{2},μ_{3},μ_{4})} is 4, and that this multiplicity occurs; also, given an integer m, there exists a Specht module S^{(μ_{1},μ_{2},μ_{3},μ_{4})} with at least m composition factors.

References

[1] S. Ariki: On the decomposition numbers of the Hecke algebra of G(m,1,n), J. Math. Kyoto Univ., 36 (1996).

[2] R. Dipper and G.D. James: Representations of Hecke algebras of general linear gropus, Proc. LMS (3), 52 (1986) 20–52.

[3] G.D. James and A. Mathas: Hecke algebras of type A at q = −1, J. Algebra 184 (1996) 102–158.

[4] A. Lascoux, B. Leclerc and J.–Y. Thibon: Hecke algebras at roots of unity and crystal bases of quantum affine algebras, Comm Math. Phys., 181 (1996) 205–263.

[5] S. Lyle: Some topics in the representation theory of the symmetric and general linear groups, Ph.D. thesis, Imperial College, London (2003).

[6] A. Mathas: Iwahori–Hecke algebras and Schur algebras of the symmetric group, American Mathematical Society (1999).

[7] A. Mathas: Decomposition matrices of Hecke algebras of type A, Gap: groups, algorithms and programming, 3.4.4, RWTH Aachen (1997).

[S^{+}95] Martin Schönert et al. GAP – Groups, Algorithms, and Programming. Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, fifth edition (1995).

School of Mathematics and Statistics F07, University of Sydney, NSW 2006, Australia

E-mail address: sineadl@maths.usyd.edu.au