ON DECOMPOSITION NUMBERS AND BRANCHING COEFFICIENTS FOR SYMMETRIC AND SPECIAL LINEAR

GROUPS

ALEXANDER KLESHCHEV

Introduction

In [13] – [15] we have obtained results generalizing the classical Branching Theorem for symmetric groups to the case of modular representations. For example we have described the socle of the restriction, D^{λ} ↓_{Σ_{n−1}}, of an arbitrary (modular) irreducible representation D^{λ} of the symmetric group Σ_{n} to the natural subgroup Σ_{n−1}. In particular, it turns out that this socle is always multiplicity-free. However, the multiplicity of a composition factor in D^{λ} ↓_{Σ_{n−1}} does not need to be equal to 1. This is one of the phenomena which make the modular case very complicated in comparison with the case of ordinary representations. Moreover, it has been proved by James [7, Theorem C] that a composition multiplicity in D^{λ} ↓_{Σ_{n−1}} can take any value (a similar result has been obtained by Jantzen and Seitz [12, 3.3]). One of the main results of this paper describes the multiplicities of some composition factors in D^{λ} ↓_{Σ_{n−1}}. It contains the mentioned results of James and Jantzen-Seitz as a special case.

More precisely, let K be a field of characteristic p > 0 and let

λ = (l_{1} ≥ l_{2} ≥ ⋯ ≥ l_{m} > 0) (1)

be a partition of n. If 1 ≤ j ≤ m and l_{j} > l_{j+1} (l_{m+1} is interpreted as 0) we define a partition λ(j) of n − 1 as follows:

λ(j) = (l_{1}, …, l_{j−1}, l_{j} − 1, l_{j+1}, …, l_{m}). (2)

The Young diagram of λ(j) is obtained from that of λ by removing the last box in the j-th row. (Note that λ(j) meant a different thing in [14].) If λ is p-regular we denote by D^{λ} the corresponding irreducible KΣ_{n}-module.

We describe the multiplicity

[D^{λ} ↓_{Σ_{n−1}} : D^{λ(j)}]

for any j such that l_{j} > l_{j+1} and λ(j) is p-regular (i.e. for all cases where D^{λ(j)} makes sense).

1991 Mathematics Subject Classification. 20C05, 20G05.

Research supported by the National Science Foundation and the Royal Society.

Unlike “the case of zero characteristic”, in general there can be composition factors of D^{λ} ↓_{Σ_{n−1}} which are different from any D^{λ(j)}. However we can obtain more information about them, too, using the following trick. Let sgn_{n} be the sign representation of Σ_{n}. Then D^{λ}⊗sgn_{n} is the irreducible module D^{b_{n}(λ)} corresponding to a (p-regular) partition b_{n}(λ) described in [15], [5] and [1]. We clearly have

[D^{λ} ↓_{Σ_{n−1}} : D^{λ(j)}] = [(D^{λ} ⊗ sgn_{n}) ↓_{Σ_{n−1}}: (D^{λ(j)} ⊗ sgn_{n−1})] .

So if b_{n}(λ) = (μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{r} > 0), 1 ≤ k ≤ r and μ_{k} > μ_{k+1} then we also know the multiplicity

[D^{λ} ↓_{Σ_{n−1}} : D^{b_{n−1}((b_{n}(λ))(k))}] .

This often provides a lot of a new information since b_{n−1}((b_{n}(λ))(k)) is not generically of the form λ(j), cf. Example after Theorem 1.4. We note that in general there can be composition factors of D^{λ} ↓_{Σ_{n−1}} different from any λ(j) and b_{n−1}((b_{n}(λ))(k)), cf. the same example and [25].

The new information on the composition factors of D^{λ} ↓_{Σ_{n−1}} and their multiplicities allows us to improve the lower bound for dim D^{λ} obtained in [15] since we now consider multiple edges in the modular Young graph (and add some new edges).

For a partition λ of n written in the form (1) and integers i, j such that 1 ≤ i < j ≤ m, l_{i} < l_{i−1}, l_{j} > l_{j+1} (l_{0} and l_{m+1} are interpreted as +∞ and 0, respectively) we define a partition λ(i, j) of n as follows:

λ(i, j) = (l_{1}, …, l_{i−1}, l_{i} + 1, l_{i+1}, …, l_{j−1}, l_{j} − 1, l_{j+1}, …, l_{m}). (3)

The Young diagram of λ(i, j) is obtained from that of λ by moving the last box in the j-th row of λ to the end of its i-th row.

We denote by S^{λ} the Specht module corresponding to λ. The second main result of the paper is a description of the decomposition numbers

d_{λ,λ(i,j)} = [S^{λ} : D^{λ(i,j)}] .

Of course, we need to assume here that λ(i, j) is p-regular. Note that though dim Hom_{Σ_{n}}(S^{λ(i,j)}, S^{λ}) ≤ 1 (this is a special case of the main result of [3]), decomposition numbers d_{λ,λ(i,j)} can take any values.

Again, using a trick with tensoring by the sign representation, we can obtain additional information on the decomposition numbers. Indeed, we have

[S^{λ} : D^{λ(i,j)}] = [S^{λ} ⊗ sgn_{n} : D^{λ(i,j)} ⊗ sgn_{n}] .

So, in view of the isomorphism S^{λ} ⊗ sgn_{n} ≅ (S^{λ′})^{∗}, we also know all decomposition numbers of the form

[S^{λ} : D^{b_{n}(λ′(k,l))}]

where b_{n} is the Mullineux bijection and λ′ is the partition conjugate to λ.

We also compute the multiplicities

k_{λ,λ(i,j)} = [M^{λ} : Y^{λ(i,j)}]

of the Young modules Y^{λ(i,j)} in the permutation modules M^{λ} for arbitrary λ, i and j. We note that the constants k_{λ,μ} are modular analogues of the Kostka numbers. By Klyachko’s Theorem [17] (see also the proof of Theorem 4.6.3 in [18]) they can also be identified with the weight multiplicities of the irreducible polynomial GL_{n}(K)-representations.

Actually, in this paper we first work with the algebraic group SL_{n}(K). Then we translate the results obtained to the language of symmetric groups using Schur functors and Klyachko’s Theorem.

The results on the algebraic groups (of type A) obtained might have an independent interest so we mention here some of them. Let λ be a dominant weight. We denote by V (λ) and L(λ) the Weyl module and the irreducible module with highest weight λ over SL_{n}(K), respectively. For an arbitrary root α we find the weight multiplicity

dim L(λ)_{λ−α}

and the composition multiplicity

[V (λ) : L(λ − α)] .

In particular, it turns out that [V (λ) : L(λ − α)] can take any value though, by [3], the dimension of the space Hom_{SL_{n}(K)} (V (λ − α), V (λ)) is at most 1. Moreover we describe some bases of the weight space L(λ)_{λ−α}, see Theorems 8.6, 8.8 and 8.9. We also investigate the question when the weight multiplicity dim L(λ)_{λ−α} is minimal, provided non-zero components of λ are fixed. It turns out that for a weight in general position the minimal possible value for this multiplicity is given by a Fibonacci number.

Exact formulations of the main results are given in Section 1. The rest of the paper is organized as follows.

• Part I. Preliminary combinatorial results. – Section 2. Essential subsets.

– Section 3. Normality.

– Section 4. σ-subsets.

– Section 5. Recurrence formulas for the number of essential subsets.

– Section 6. Quasi-latticed sequences and sets.

• Part II. Main Results.

– Section 7. Preliminaries from representation theory.

– Section 8. Dimension and bases of the weight space L(λ)_{λ−α}.

– Section 9. Some composition multiplicities of L(λ)_{1}|A_{l−1}(K).

– Section 10. Decomposition numbers [V (λ) : L(λ − α)].

– Section 11. How to translate from SL_{n} to Σ_{n}.

Acknowledgement. Christine Bessenrodt has communicated to me the results of the computer calculations of the socle series for D^{λ} ↓_{Σ_{n−1}} , n ≤ 10, cf. [25], initiated by her and done by K. Timmerscheidt. I am very grateful to her for allowing me to use this important information.

1. Formulations of the main results

Throughout the paper:

K is a field of characteristic p > 0. All modules are supposed to be vector spaces over K.

ℤ_{+} is the set of non-negative integers.

For integers r, s we write r ≡ s for r ≡ s (mod p) and denote

[r, s] = {i ∈ ℤ | r ≤ i ≤ s},  (r, s] = {i ∈ ℤ | r < i ≤ s},
[r, s) = {i ∈ ℤ | r ≤ i < s},  (r, s) = {i ∈ ℤ | r < i < s}.

We consider a (fixed) partition λ of n written in the form (1). We always interpret l_{0} as +∞ and l_{m+1} as 0.

Definition of the following four series of KΣ_{n}-modules can be found in [8], [9]. M^{λ} the permutation module (on λ-tabloids); S^{λ} the Specht module; D^{λ} the irreducible module (if λ is p-regular); Y^{λ} the Young module.

Definition 1.1. Let {t_{1}, t_{2}, …, t_{u}} be a finite sequence with t_{i} = +1 or t_{i} = −1. We call such a sequence a sign sequence. (We consider the empty sequence as a sign sequence — this corresponds to the case u = 0).

Definition 1.2. Let T = {t_{1}, t_{2}, …, t_{u}} be a sign sequence.

(i) We call this sequence latticed if and only if ∑_{i=1}^{j} t_{i} ≥ 0 for all j = 1, 2, …, u. The empty sequence is latticed by definition.

(ii) We define ν(T) by setting

ν(T) = 1 + |{i | 1 ≤ i ≤ u, t_{i} = +1, and {t_{i+1}, t_{i+2}, …, t_{u}} is latticed}|,

if T is latticed and non-empty; ν(T) = 1, if T is empty; and ν(T) = 0, if T is not latticed.

Example. Let T = {+1, −1, +1}. Then ν(T) = 2. Indeed, the empty sequence is latticed so

{i | 1 ≤ i ≤ 3, t_{i} = +1, {t_{i+1}, t_{i+2}, …, t_{u}} is latticed} = {3}.

Let T = {−1, +1, +1, +1, +1}. Then ν(T) = 0 since T is not latticed.

Definition 1.3. Let λ be a partition of n written in the form (1). Assume 0 ≤ i < j ≤ m. Let {k_{1} > k_{2} > ⋯ > k_{u}} be the set of all integers k such that i < k < j and one of the following conditions holds:

(i) l_{k} > l_{k+1} and l_{k} − k ≡ l_{j} − j; (ii) l_{k} < l_{k−1} and l_{k} − k + 1 ≡ l_{j} − j. Now put T_{i,j}(λ) = {t_{1}, t_{2}, …, t_{u}} where t_{v} = +1, if the condition (i) holds for

k = k_{v}, and t_{v} = −1, if the condition (ii) holds for k = k_{v}, v = 1, 2, …, u. Also put T_{j}(λ) = T_{0,j}(λ).

Remark. (a) Clearly at most one of the conditions (i) and (ii) in Definition 1.3 holds for a fixed k = k_{v}. So the sequence T_{i,j}(λ) is well-defined.

(b) T_{i,j}(λ) may be empty.

Theorem 1.4. Let λ = (l_{1} ≥ l_{2} ≥ ⋯ ≥ l_{m} > 0) be a p-regular partition of n. Assume 1 ≤ j ≤ m, l_{j} > l_{j+1} (l_{m+1} is interpreted as 0) and λ(j) is p-regular. Then

[D^{λ} ↓_{Σ_{n−1}} : D^{λ(j)}] = ν(T_{j}(λ)).

Remark. The sequence T_{j}(λ) is latticed if and only if a removable node A = (j, l_{j}) is normal in the sense of [14] and [15]. Recall that the residue, res C, of a node C = (r, s) is defined as (s − r) (mod p). Now Theorem 1.4 can be reformulated as follows. The multiplicity [D^{λ} ↓_{Σ_{n−1}} : D^{λ(j)}] is equal to 1+(the number of the normal nodes B above A such that res B = res A), if A is normal, and is equal to 0 otherwise.

Example. (a) Let p = 3, λ = (5, 3, 2). The corresponding Young diagram then looks as follows (we have indicated the residues of all removable nodes and of some indent nodes, cf. Remark after Theorem 1.4 and [15]).

2 1 2 1 2

The sequence T_{3}(λ) is {−1, −1}. It is not latticed so D^{(5,3,1)} does not occur in D^{(5,3,2)} ↓_{Σ_{9}}, in view of Theorem 1.4. The sequence T_{2}(λ) = {+1}. We have ν(T_{2}(λ)) = 2. So [D^{(5,3,2)} ↓_{Σ_{9}}: D^{(5,2,2)}] = 2. The sequence T_{1}(λ) is empty. So [D^{(5,3,2)} ↓_{Σ_{9}}: D^{(4,3,2)}] = 1. Moreover, by [15] or [5], D^{(5,3,2)} ⊗ sgn_{10} ≅ D^{(6,2,2)}. Applying Theorem 1.4 as above, we have [D^{(6,2,2)} ↓_{Σ_{9}}: D^{(5,2,2)}] = 1. However D^{(5,2,2)} ⊗ sgn_{9} ≅ D^{(6,2,1)}. Therefore [D^{(5,3,2)} ↓_{Σ_{9}}: D^{(6,2,1)}] = 1. Summarizing, we obtain the following composition factors and multiplicities for D^{(5,3,2)} ↓_{Σ_{9}}.

Factor  D^{(4,3,2)} D^{(5,2,2)} D^{(6,2,1)}
Multiplicity  1  2  1

It follows from [25] that this is complete information about composition factors of the restriction D^{(5,3,2)} ↓_{Σ_{9}}. We add that by [15, 3.1], this restriction is indecomposable, self-dual and has a simple socle and a simple head both isomorphic to D^{(5,2,2)}.

(b) Let p = 3, λ = (3, 2, 2, 1, 1). The Young diagram is

2 1 2 1 2 0

This is an example where Theorem 1.4 is less effective. A reason for this is that λ(j) is 3-regular only for j = 5. If j = 5 we have T_{j}(λ) = {+1, +1}. So ν(T_{5}(λ)) = 3. Thus, [D^{(3,2,2,1,1)} ↓_{Σ_{8}}: D^{(3,2,2,1)}] = 3. Now apply the “sign trick”. We have D^{(3,2,2,1,1)} ⊗ sgn_{9} ≅ D^{(5,3,1)}. An application of Theorem 1.4 gives the equalities [D^{(5,3,1)} ↓_{Σ_{8}}: D^{(4,3,1)}] = 1 and [D^{(5,3,1)} ↓_{Σ_{8}}: D^{(5,2,1)}] = 2. Since D^{(4,3,1)} ⊗ sgn_{8} ≅ D^{(7,1)} and D^{(5,2,1)} ⊗ sgn_{8} ≅ D^{(4,2,2)}, we conclude that [D^{(3,2,2,1,1)} ↓_{Σ_{8}}: D^{(7,1)}] = 1 and [D^{(3,2,2,1,1)} ↓_{Σ_{8}}: D^{(4,2,2)}] = 2. Summarizing, we have:

Factor  D^{(3,2,2,1)} D^{(7,1)} D^{(4,2,2)}
Multiplicity  3  1  2

As the computer computations in [25] show, the complete set of the composition factors looks as follows.

Factor  D^{(3,2,2,1)} D^{(7,1)} D^{(4,2,2)} D^{(4,4)}
Multiplicity  3  1  2  1

Thus we “lose” D^{(4,4)} (which is actually the sign representation)!

By [15, 3.1], the restriction D^{(3,2,2,1,1)} ↓_{Σ_{8}} is indecomposable, self-dual and has a simple socle and a simple head both isomorphic to D^{(3,2,2,1)}.

Remark. (a) The following result is proved in [7, Theorem C] and [12, 3.3]. Let

λ = (λ_{1}^{a_{1}}, (λ_{1} − 1)^{p−1}, …, (λ_{1} − r + 1)^{p−1}, λ_{r+1}^{a_{r+1}}, …, λ_{d}^{a_{d}})

be a p-regular partition of n, with a_{r+1} ≠ p − 1 or λ_{r+1} < λ_{1} − r. Put j = a_{1} + (r − 1)(p − 1). Then [D^{λ} ↓_{Σ_{n−1}} : D^{λ(j)}] = r.

This is a special case of Theorem 1.4 since

T_{j}(λ) = \{\underbrace{+1, …, +1}_{r−1 times}\},

hence ν(T_{j}(λ)) = r for our j.

It would be important to describe the class of the partitions λ for which our method provides a complete set of composition factors of the restriction D^{λ} ↓_{Σ_{n−1}} and all the composition factors of D^{λ} ↓_{Σ_{n−1}} again belong to this class. For such partitions the lower bound given in Corollary 1.6 below provides the exact value of the dimension of D^{λ}. In [20] (cf. also [16]), a class of partitions is described, for which a much weaker lower bound obtained in [15, 2.2] gives the exact value for the dimension. Already that class is not too slim. This allows one to hope that the lower bound for dim D^{λ} given in Corollary 1.6 is actually equal to dim D^{λ} for some reasonably wide class of modules. But not in general, of course.

Recall that we denote by b_{n} the Mullineux bijection on the set of the p-regular partitions of n.

Definition 1.5. We define the multiple p-Young graph Y G as the oriented graph with vertices labelled by all p-regular partitions (of all positive integers). Two vertices λ and μ are connected by i arrows going from μ to λ if and only if one of the following conditions holds.

(i) μ = λ(j) and ν(T_{j}(λ)) = i for some j;

(ii) μ = b_{n−1}((b_{n}(λ))(k)) and ν(T_{k}(b_{n}(λ))) = i for some k such that (b_{n}(λ))(k) is p-regular.

The following result readily follows from Theorem 1.4 by induction on n, cf. the proof of [15, 2.2].

Corollary 1.6. dim D^{λ} ≥ ♯{paths from (1) to λ in Y G}.

We now define the notions necessary to describe some decomposition numbers of Σ_{n}.

Definition 1.7. Let J ≠ ∅ be a finite set of integers. Then J can be represented in the form

J = [b_{1}, c_{1}] ∪ [b_{2}, c_{2}] ∪ ⋯ ∪ [b_{N}, c_{N}]

where b_{i+1} − c_{i} > 1 for all i = 1, 2, …, N − 1. We call this representation the decomposition into the union of connected components.

Definition 1.8. Let T = {t_{1}, t_{2}, …, t_{u}} be a sign sequence.

(i) For 1 ≤ i ≤ j ≤ u we denote by T (i, j) the subsequence {t_{i}, t_{i+1}, …, t_{j}}. (ii) Let J be a subset in [1, u]. We call J a latticed subset (in [1, u] for T) if and

only if the following two conditions hold. (a) J ⊆ {i | t_{i} = −1};

(b) Let [1, u]\J = [b_{1}, c_{1}]∪[b_{2}, c_{2}]∪⋯∪[b_{N}, c_{N}] be the decomposition into the union of connected components. Then the sequences T (b_{i}, c_{i}), i = 1, 2, …, N, are latticed.

(iii) We denote by q(T) the number of the latticed subsets in [1, u] for T.

Remark. (a) For T = ∅ we have q(T) = 1 (the empty subset is interpreted as the only latticed subset in [1, 0] = ∅).

(b) In Lemma 6.7 we provide a recurrence formula for q(T) (in a more general setting of quasi-latticed subsets).

Definition 1.9. Let 1 ≤ i < j ≤ m. We define an integer Q_{i,j}(λ) as follows. We put Q_{i,j}(λ) = 0 if l_{j} − j ≢ l_{i} − i + 1. If l_{j} − j ≡ l_{i} − i + 1 we put Q_{i,j}(λ) = q(T_{i,j}(λ)) (cf. Definitions 1.3, 1.8(iii)).

Recall the partition λ(i, j) defined in (3).

Theorem 1.10. Let λ = (l_{1} ≥ l_{2} ≥ … l_{m} > 0) be a partition of n, 1 ≤ i < j ≤ m, l_{j} > l_{j+1} and l_{i} < l_{i−1} (l_{0} and l_{m+1} are interpreted as +∞ and 0, respectively). Assume the partition λ(i, j) is p-regular. Then

[S^{λ} : D^{λ(i,j)}] = Q_{i,j}(λ).

Remark. (a) Let A = (j, l_{j}), B = (i, l_{i} + 1). Then the Young diagram of λ(i, j) is obtained from that of λ by removing A and adding B. Now the condition l_{j} − j ≡ l_{i} − i + 1 in Definition 1.9 means res A = res B. By the Nakayama Conjecture (cf. [10, 6.1.21, 2.7.41]) this is a necessary condition for [S^{λ} : D^{λ(i,j)}] to be non-zero. (This condition is also sufficient in view of [8, 24.10].)

(b) The decomposition numbers [S^{λ} : D^{λ(i,j)}] can take any non-negative values. Indeed there exists many p-regular partitions λ such that the top d+1 indent nodes and the bottom d + 1 removable nodes have the same residue, say α, while all the other removable and indent nodes have residues different from α, for example as in the following picture.

α α  α α α  α  α α α · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·

Then the sequence T_{1,m}(λ) = \{\underbrace{+1, …, +1}_{d times}, \underbrace{−1, …, −1}_{d times}\}. Therefore Q_{1,m}(λ) =

d + 1.

It is explained in Section 11 how to identify the multiplicities [M^{λ} : Y^{λ(i,j)}] with weight multiplicities of the form L(μ)_{λ−α} where α is a root. The latter multiplicities are described below in Theorem 1.14.

We introduce some standard notation. Details can be found in [24], [11] and [2]. From now on till the end of this section we assume that K is algebraically closed. We denote by {α_{1}, α_{2}, …, α_{l}} a base in the root system A_{l}; {ω_{1}, ω_{2}, …, ω_{l}} the corresponding fundamental weights; A_{l}(K) ≅ SL_{l+1}(K) the universal Chevalley group of type A_{l} over K; V (λ) the Weyl module over A_{l}(K) with highest weight λ; L(λ) the irreducible module over A_{l}(K) with highest weight λ; L_{μ} the μ-weight space of a rational KA_{l}(K)-module L. We fix a dominant weight

λ = (λ_{1}, λ_{2}, …, λ_{l}) = λ_{1}ω_{1} + λ_{2}ω_{2} + ⋯ + λ_{l}ω_{l} (λ_{1}, λ_{2}, …, λ_{l} ∈ ℤ_{+}).

Note that any positive root in A_{l} has a form

α(r, s) = α_{r} + α_{r+1} + ⋯ + α_{s}

with 1 ≤ r ≤ s ≤ l.

We define the constants B(i, j), C(i, j) which play a crucial role in this paper (we also used them in [14]).

Definition 1.11. For 1 ≤ i ≤ j ≤ l we set

B(i, j) = B_{λ}(i, j) = j − i + ∑_{k=i}^{j} λ_{k}

C(i, j) = C_{λ}(i, j) = j − i + ∑_{k=i}^{j−1} λ_{k}.

From now on we assume that r, s are integers with 1 ≤ r ≤ s ≤ l. We first give an enumerative description of dim L(λ)_{λ−α}.

Definition 1.12. Let M, N ⊆ ℤ. We call an injective map d : M → N a weakly increasing (respectively, weakly decreasing) injection if m ≤ d(m) (respectively, m ≥ d(m)) for all m ∈ M.

In the following definition we introduce a class of subsets of (r, s] which are used to label a basis of the weight space L(λ)_{λ−α(r,s)}, see Theorem 8.6.

Definition 1.13. Let J ⊆ (r, s]. We call J non-essential (in (r, s] for λ) if and only if there exist t, u ∈ [r, s + 1] \ J, with t < u, and a weakly increasing injection d : {t} ∪ ((t, u) ∩ J) → [t, u), such that B(k, d(k)) ≡ 0 for all k ∈ {t} ∪ ((t, u) ∩ J).

Otherwise J is called essential (in (r, s] for λ). We denote by E(r, s) = E_{λ}(r, s) the set of all essential subsets in (r, s], and put

ε(r, s) = |E(r, s)|.

Example. (a) The empty set is non-essential in (r, s] if and only if B(t, d) ≡ 0 for some t, d with r ≤ t ≤ d ≤ s.

(b) Let j ∈ (r, s]. The set J = {j} is non-essential in (r, s] if and only if at least one of the following three conditions holds.

(i) B(t, d) ≡ 0 for some t, d with j < t ≤ d ≤ s; (ii) B(t, d) ≡ 0 for some t, d with r ≤ t ≤ d ≤ j − 2; (iii) there exist t ∈ [r, j − 1] and two distinct integers d(t), d(j) with d(t) ∈

[t, s], d(j) ∈ [j, s] and B(t, d(t)) ≡ 0, B(j, d(j)) ≡ 0.

Theorem 1.14. Let λ = λ_{1}ω_{1} + λ_{2}ω_{2} + ⋯ + λ_{l}ω_{l} be a dominant weight for the root system A_{l}, 1 ≤ r ≤ s ≤ l, α = α_{r} + α_{r+1} + ⋯ + α_{s} be a (positive) root, μ = λ − α. Then

dim L(λ)_{μ} = ε(r, s).

Remark. (a) In fact Theorem 1.14 is a special case of Theorems 8.6 and 8.8. In these theorems we construct two distinct bases of the weight space L(λ)_{μ} with elements labelled by the essential subsets. Another basis, whose elements are labelled by the so-called σ-subsets, is constructed in Theorem 8.9.

(b) Below we provide explicit formulas for dim L(λ)_{λ−α} (see Theorems 1.18 and 1.19).

Definition 1.15. Let M ⊆ (r, s]. We say that a set Z ⊆ (r, s] compensates M (in (r, s] for λ) if and only if there exists a weakly decreasing injection z : M → Z such that B(z(m), m) ≡ 0 for all m ∈ M.

We say that M is compensated (in (r, s] for λ) if and only if there exists a subset Z ⊆ (r, s] which compensates M (in (r, s] for λ).

Definition 1.16. Let r ≤ i ≤ s. We call i normal in [r, s] (for λ) if and only if λ_{i} ≢ 0 and the set M = {m ∈ (i, s] | B(i, m) ≡ 0} is compensated in (r, s] (for λ).

We set

σ(i, s) = σ_{λ}(i, s) = \begin{cases}1 & if i is normal in [r, s], \\ 0 & otherwise. \end{cases}

We also set

σ(i, j) = \begin{cases}1 & if j = i − 1, \\ −1 & if j = i − 2, \\ 0 & if j < i − 2. \end{cases}

Remark. (a) Clearly, i is normal in [r, s] if and only if it is normal in [i, s]. (b) Assume that λ_{r} ≢ 0, and let

{r = i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

Then r is normal in [r, s] if and only if for all j ∈ (1, k] with B(r, i_{j}) ≡ 0 there exist d(j), all distinct, such that 1 < d(j) < j and B(i_{d(j)}, i_{j}) ≡ 0. This observation made in Lemma 3.3 is very convenient when those i with λ_{i} ≢ 0 are known.

Definition 1.17. (i) We define an (s−r+1) by (s−r+1) matrix M(r, s) = M_{λ}(r, s) as follows.

ON DECOMPOSITION NUMBERS AND BRANCHING COEFFICIENTS 11

M(r, s) = [\begin{matrix}σ(r, r − 1) & σ(r, r) & ⋯ & σ(r, s − 2) & σ(r, s) \\ σ(r + 1, r − 1) & σ(r + 1, r) & ⋯ & σ(r + 1, s − 2) & σ(r + 1, s) \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ σ(s, r − 1) & σ(s, r) & ⋯ & σ(s, s − 2) & σ(s, s) \end{matrix}] .

(ii) Let

{i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

We define a matrix A(r, s) = A_{λ}(r, s) as a k by k matrix with entries a_{t,u} given by

a_{t,u} = \begin{cases}σ(i_{t}, i_{u−1}) + (i_{u+1} − i_{u} − 1)σ(i_{t}, i_{u}), & if 1 ≤ t < u < k; \\ σ(i_{t}, i_{k}), & if u = k; \\ −1, & if u = t − 1; \\ 0, & otherwise. \end{cases}

Example. (i)

M(r, r) = [σ(r, r)],

M(r, r + 1) = [\begin{matrix}σ(r, r − 1) & σ(r, r + 1) \\ σ(r + 1, r − 1) & σ(r + 1, r + 1) \end{matrix}] = [\begin{matrix}1 & σ(r, r + 1) \\ −1 & σ(r + 1, r + 1) \end{matrix}] ,

M(r, r + 2) = [\begin{matrix}σ(r, r − 1) & σ(r, r) & σ(r, r + 2) \\ σ(r + 1, r − 1) & σ(r + 1, r) & σ(r + 1, r + 2) \\ σ(r + 2, r − 1) & σ(r + 2, r) & σ(r + 2, r + 2) \end{matrix}]

= [\begin{matrix}1 & σ(r, r) & σ(r, r + 2) \\ −1 & 1 & σ(r + 1, r + 2) \\ 0 & −1 & σ(r + 2, r + 2) \end{matrix}] ,

M(r, r + 3) = [\begin{matrix}σ(r, r − 1) & σ(r, r) & σ(r, r + 1) & σ(r, r + 3) \\ σ(r + 1, r − 1) & σ(r + 1, r) & σ(r + 1, r + 1) & σ(r + 1, r + 3) \\ σ(r + 2, r − 1) & σ(r + 2, r) & σ(r + 2, r + 1) & σ(r + 2, r + 3) \\ σ(r + 3, r − 1) & σ(r + 3, r) & σ(r + 3, r + 1) & σ(r + 3, r + 3) \end{matrix}]

= [\begin{matrix}1 & σ(r, r) & σ(r, r + 1) & σ(r, r + 3) \\ −1 & 1 & σ(r + 1, r + 1) & σ(r + 1, r + 3) \\ 0 & −1 & 1 & σ(r + 2, r + 3) \\ 0 & 0 & −1 & σ(r + 3, r + 3) \end{matrix}] .

(ii) Denote σ(i_{t}, i_{u}) by σ_{t,u}, and put x_{t} = i_{t} − i_{t−1}. Then for k = 1 we have A(r, s) = [σ_{1,1}]; for k = 2 we have

A(r, s) = [\begin{matrix}x_{2} & σ_{1,2} \\ −1 & σ_{2,2} \end{matrix}];

for k = 3 we have

A(r, s) = [\begin{matrix}x_{2} & σ_{1,1} + (x_{3} − 1)σ_{1,2} & σ_{1,3} \\ −1 & x_{3} & σ_{2,3} \\ 0 & −1 & σ_{3,3} \end{matrix}];

for k = 4 we have

A(r, s) = [\begin{matrix}x_{2} & σ_{1,1} + (x_{3} − 1)σ_{1,2} & σ_{1,2} + (x_{4} − 1)σ_{1,3} & σ_{1,4} \\ −1 & x_{3} & σ_{2,2} + (x_{4} − 1)σ_{2,3} & σ_{2,4} \\ 0 & −1 & x_{4} & σ_{3,4} \\ 0 & 0 & −1 & σ_{4,4} \end{matrix}] .

Theorem 1.18. Let λ = λ_{1}ω_{1} + λ_{2}ω_{2} + ⋯ + λ_{l}ω_{l} be a dominant weight for the root system A_{l} and α = α_{r} + α_{r+1} + ⋯ + α_{s} be a positive root. Then

dim L(λ)_{λ−α} = det M_{λ}(r, s) = det A_{λ}(r, s).

In fact, we first prove recurrence formulas for dim L(λ)_{λ−α} given in in Theorem 1.19 below, and then observe that they are just cofactor expansions of det M_{λ}(r, s) and det A_{λ}(r, s) along the first rows! Part (ii) of Theorem 1.19 is convenient when those i with λ_{i} ≢ 0 are known. Other recurrence formulas for dim L(λ)_{λ−α} can be found in Corollary 8.10. Below we also give another expression of ε(r, s) = dim L(λ)_{λ−α} as a determinant, see (59).

Theorem 1.19. Let λ = λ_{1}ω_{1} + λ_{2}ω_{2} + ⋯ + λ_{l}ω_{l} be a dominant weight for the root system A_{l}, 1 ≤ r ≤ s ≤ l. For a positive root α(i, j) = α_{i} + α_{i+1} + ⋯ + α_{j} we denote d(i, j) = dim L(λ)_{λ−α(i,j)}. Then

(i) d(r, s) = σ(r, s) + ∑_{j=r+1}^{s} σ(r, j − 2)d(j, s).

(ii) Let {i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}. If I = ∅ then d(r, s) = 0. If I ≠ ∅ then

d(r, s) =σ(i_{1}, i_{k}) + (i_{2} − i_{1})d(i_{2}, i_{k})

+ ∑_{j=3}^{k} ((i_{j} − i_{j−1} − 1)σ(i_{1}, i_{j−1}) + σ(i_{1}, i_{j−2}))d(i_{j}, i_{k}).

Remark. Let {i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

If k ≤ 3 then dim L(λ)_{λ−α(r,s)} was known previously.

For k = 0, 1 the problem is trivial.

For k = 2 the answer can be found in [21, 8.6] (see also [23, p. 25]).

For k = 3 the weight multiplicity has also been described by Seitz (unpublished). We provide the explicit answers for k ≤ 4 in the next corollary (the proof of the

corollary is a straightforward application of Theorem 1.18 (or Theorem 1.19(ii)) and Remark (b) after Definition 1.16).

Corollary 1.20. Let

{i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

ON DECOMPOSITION NUMBERS AND BRANCHING COEFFICIENTS 13

Denote d(r, s) = dim L(λ)_{λ−α(r,s)}, B_{t,u} = B(i_{t}, i_{u}), x_{t} = i_{t} − i_{t−1}. Then (i) If k = 0 then d(r, s) = 0. (ii) If k = 1 then d(r, s) = 1. (iii) [21, 8.6] Let k = 2. Then

d(r, s) = \begin{cases}x_{2}, & if B_{1,2} ≡ 0, \\ x_{2} + 1, & otherwise. \end{cases}

(iv) Let k = 3. Then

d(r, s) = \begin{cases}x_{2}x_{3} + 1, & if B_{1,2} ≡ 0, B_{2,3} ≡ 0; \\ x_{2}(x_{3} + 1) + 1, & if B_{1,2} ≡ 0, B_{2,3} ≢ 0; \\ (x_{2} + 1)x_{3} + 1, & if B_{1,2} ≢ 0, B_{2,3} ≡ 0; \\ (x_{2} + 1)(x_{3} + 1) − 1, & if B_{1,2} ≢ 0, B_{2,3} ≢ 0, B_{1,3} ≡ 0; \\ (x_{2} + 1)(x_{3} + 1), & if B_{1,2} ≢ 0, B_{2,3} ≢ 0, B_{1,3} ≢ 0. \end{cases}

(v) Let k = 4. Then the value of d(r, s) can be found from the following table.

d(r, s)  B_{1,2} B_{1,3} B_{1,4} B_{2,3} B_{3,4} B_{2,4}
x_{2}x_{3}x_{4} + x_{2} + x_{4}  ≡ 0 any any ≡ 0 ≡ 0 any
(x_{2} + 1)x_{3}x_{4} + x_{2} + x_{4} + 1  ≢ 0 any any ≡ 0 ≡ 0 any
x_{2}x_{3}(x_{4} + 1) + x_{2} + x_{4} + 1  ≡ 0 any any ≡ 0 ≢ 0 any
(x_{2} + 1)x_{3}(x_{4} + 1) + x_{2} + x_{4} + 1  ≢ 0 any ≢ 0 ≡ 0 ≢ 0 any
as above  ≢ 0 ≢ 0 ≡ 0 ≡ 0 ≢ 0 ≡ 0
(x_{2} + 1)x_{3}(x_{4} + 1) + x_{2} + x_{4}  ≢ 0 ≡ 0 ≡ 0 ≡ 0 ≢ 0 any
as above  ≢ 0 ≢ 0 ≡ 0 ≡ 0 ≢ 0 ≢ 0
x_{2}(x_{3} + 1)x_{4} + x_{2} + x_{4}  ≡ 0 any any ≢ 0 ≡ 0 any
x_{2}(x_{3} + 1)x_{4} + x_{2} + x_{3}x_{4} + 1  ≢ 0 ≡ 0 any ≢ 0 ≡ 0 any
(x_{2} + 1)(x_{3} + 1)x_{4} + x_{2} + 1  ≢ 0 ≢ 0 any ≢ 0 ≡ 0 any
x_{2}x_{3}(x_{4} + 1) + (x_{2} + 1)x_{4} + 1  ≡ 0 any any ≢ 0 ≢ 0 ≡ 0
x_{2}(x_{3} + 1)x_{4} + x_{2}x_{3} + x_{3}(x_{4} + 1) + 1 ≢ 0 ≡ 0 any ≢ 0 ≢ 0 ≡ 0
(x_{2} + 1)x_{3}(x_{4} + 1) + (x_{2} + 1)x_{4} + 1 ≢ 0 ≢ 0 any ≢ 0 ≢ 0 ≡ 0
x_{2}(x_{3} + 1)(x_{4} + 1) + (x_{4} + 1)  ≡ 0 any any ≢ 0 ≢ 0 ≢ 0
x_{2}(x_{3} + 1)(x_{4} + 1) + x_{3}(x_{4} + 1) + 1 ≢ 0 ≡ 0 any ≢ 0 ≢ 0 ≢ 0
x_{2}(x_{3} + 1)(x_{4} + 1) + x_{3}(x_{4} + 1) + x_{4} ≢ 0 ≢ 0 ≡ 0 ≢ 0 ≢ 0 ≢ 0
(x_{2} + 1)(x_{3} + 1)(x_{4} + 1)  ≢ 0 ≢ 0 ≢ 0 ≢ 0 ≢ 0 ≢ 0

Now assume that those i ∈ [r, s] with λ_{i} ≢ 0 are fixed. What is the minimal value for dim L(λ)_{λ−α(r,s)}? Clearly, the maximal value is equal to the corresponding dimension in the case of zero characteristic, i.e. dim V (λ)_{λ−α(r,s)}. And it is well known that if

∅ ≠ {i ∈ [r, s] | λ_{i} ≢ 0} = {i_{1} < i_{2} < ⋯ < i_{k}}

then

dim V (λ)_{λ−α(r,s)} = ∏_{j=1}^{k−1}(i_{j} − i_{j−1} + 1),

see for example [12, 1.6].

Definition 1.21. Let i_{1} < i_{2} < ⋯ < i_{k} be integers. We define the integers f(i_{j}, i_{j+1}, …, i_{k}), j = k, k − 1, …, 1, by setting

f(i_{k}) = 1;
f(i_{k−1}, i_{k}) = i_{k} − i_{k−1};
f(i_{j}, i_{j+1}, …, i_{k}) = (i_{j+1} − i_{j})f(i_{j+1}, i_{j+2}, …, i_{k}) + f(i_{j+2}, i_{j+3}, …, i_{k}),
j = k − 2, k − 3, …, 1.

Example. Let i_{1} = r, i_{2} = r +1, i_{3} = r +2, …, i_{s−r+1} = s. Then f(r, r +1, …, s) = f_{s−r+1} where f_{j} denotes the j-th Fibonacci number defined by f_{1} = 1, f_{2} = 1 and f_{j} = f_{j−1} + f_{j−2} for j ≥ 3.

Proposition 1.22. Assume that

{i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0} ≠ ∅.

Then

dim L(λ)_{λ−α(r,s)} ≥ f(i_{1}, i_{2}, …, i_{k}).

Moreover,

dim L(λ)_{λ−α(r,s)} = f(i_{1}, i_{2}, …, i_{k}).

if and only if

B(i_{j}, i_{j+1}) ≡ 0 for all j = 1, 2, …, k − 1. (4)

The description of the multiplicities [V (λ) : L(λ − α)] is given in combinatorial terms which are very similar to those used for the description of [S^{λ} : D^{λ(i,j)}], cf. 1.8, 1.9 and 1.10. (In fact, we deduce the latter description from the former one). We have only to consider more general quasi-latticed sequences which consist of “+1”, “−1” or “0”. The exact formulations can be found in Sections 6 and 10. The main result is Theorem 10.6. Corollary 10.5 provides a recurrence formula for [V (λ) : L(λ − α)].

Part I. Preliminary combinatorial results

Throughout Part I:

l is a fixed positive integer;

r and s are always supposed to be integers which satisfy 1 ≤ r ≤ s ≤ l; λ = (λ_{1}, λ_{2}, …, λ_{l}), λ_{i} ∈ ℤ_{+}, i = 1, 2, …, l, is an l-tuple of non-negative integers

(in Part II we shall consider λ as a dominant weight for the root system A_{l}). We define the l-tuple λ(i) for any i = 1, 2, …, l by setting

λ(i) = (λ_{1}, …, λ_{i−1}, λ_{i} + 1, λ_{i+1}, …, λ_{l}). (5)

(The l-tuple λ(i) has nothing to do with the partition λ(j) from (2)!)

Recall the constants B(i, j) = B_{λ}(i, j) and C(i, j) = C_{λ}(i, j) defined in 1.11.

2. Essential subsets

In 1.13 we have defined the set E(r, s) = E_{λ}(r, s) which consists of the essential subsets in (r, s] for λ. We have also defined the integer ε(r, s) as the order of E(r, s).

Recall the l-tuples λ(i) defined in (5). Put

E′(r, s) = E_{λ(s)}(r, s), (6)

ε′(r, s) = |E′(r, s)| . (7)

The following two lemmas follow immediately from Definition 1.13.

Lemma 2.1. Let I, J ⊆ (r, s] and I ⊆ J. If I is essential in (r, s] then J is essential in (r, s].

Lemma 2.2. Let J ⊆ (r, s] be essential in (r, s] and q ∈ (r, s]\J. Then J ∩(r, q −1] is essential in (r, q − 1].

Lemma 2.3. Let I = {i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0} (i) If I = ∅ then ε(r, s) = 0; (ii) If I ≠ ∅ then ε(r, s) = ε(i_{1}, i_{k}).

Proof. (i) I = ∅ means λ_{i} ≡ 0 for i = r, r+1, …, s. In this case (r, s] is non-essential in (r, s]. Indeed, we can take

t = r, u = s + 1, d(t) = r, d(j) = j for all j ∈ (r, s]

in Definition 1.13, because B_{λ}(k, k) = λ_{k}. Now (i) follows from Lemma 2.1.

(ii) Let J ⊆ (r, s]. It is enough to prove that J is essential in (r, s] if and only if J ⊇ (r, i_{1}], J ⊇ (i_{k}, s] and γ(J) := J \ ((r, i_{1}] ∪ (i_{k}, s]) is essential in (i_{1}, i_{k}].

Assume J is essential in (r, s]. If there exists q ∈ (r, i_{1}] with q ∉ J then we may take

t = i_{1}, u = q, d(t) = i_{1}, d(j) = j for all j ∈ J ∩ (i_{1}, q)

in Definition 1.13. If there exists q ∈ (i_{k}, s] with q ∉ J then we may take

t = q, u = s + 1, d(t) = q, d(j) = j for all j ∈ J ∩ (q, s])

in Definition 1.13. Thus J ⊇ (r, i_{1}], J ⊇ (i_{k}, s].

Assume γ(J) is not essential in (i_{1}, i_{k}]. Then there exist t, u, d(t) and d(j) as in Definition 1.13. If t > i_{1} and u ≤ i_{k} this implies that J in non-essential in (r, s], and we are done.

Suppose t = i_{1}, u ≤ i_{k}. We choose t′ = r, d(j) = j for all j ∈ [i_{1}, i_{k}). Then

t′, u, d(t′), and d(j) for j ∈ J ∩ (t′, u)

work in Definition 1.13. Therefore J is non-essential in (r, s].

If t = i_{1}, u = i_{k} + 1 we need to take t′ as above, u′ = s + 1, d(j) = j for j = i_{k} + 1, i_{k} + 2, …, s in Definition 1.13.

The case t > i_{1}, u = i_{k} + 1 is considered similarly.

In the other direction, suppose J ⊇ (r, i_{1}], J ⊇ (i_{k}, s] and γ(J) is essential in (i_{1}, i_{k}]. If J is non-essential in (r, s] then there exist t, u, d(t), d(j) as in Definition 1.13. Since γ(J) is essential in (i_{1}, i_{k}] we have t = r or u = s + 1 or both, since otherwise t, u ∉ J implies t, u ∈ (i_{1}, i_{k}].

Assume t = r, u = s + 1. Since (i_{k}, s] ⊆ J ∩ (t, u) we have d(j) = j for all j ∈ (i_{k}, s]. So d(j) ≤ i_{k} for all j ∈ J ∩ (t, i_{k} + 1). Take u′ = i_{k} + 1, t′ = i_{1}. Then, since i_{1} ∈ J conditions of Definition 1.13 hold for u′, t′, d(t′), d(j) for j ∈ J ∩ (u′, t′) = γ(J) ∩ (u′, t′). So γ(J) is non-essential in (i_{1}, i_{k}].

The cases t = r, u < s + 1 and t > r, u = s + 1 are considered similarly.

Lemma 2.4. Let q ∈ (r, s], I ∈ E(r, q − 2), J ∈ E(q, s). Then I ∪ {q} ∪ J ∈ E(r, s). (If q = r + 1, the statement is interpreted as follows: J ∈ E(r + 1, s) implies {r + 1} ∪ J ∈ E(r, s)).

Proof. Assume the lemma is false. Then by Definition 1.13 there exist

t, u ∈ [r, s + 1] \ (I ∪ {q} ∪ J),

with t < u, and a weakly increasing injection

d : {t} ∪ ((t, u) ∩ (I ∪ {q} ∪ J)) → [t, u)

such that

B(k, d(k)) ≡ 0

for all k ∈ {t} ∪ ((t, u) ∩ (I ∪ {q} ∪ J)).

If u < q it follows from the definition that I is non-essential in (r, q − 2], which contradicts our assumption.

If u > q and t > q it follows from the definition that J is non-essential in (q, s], giving a contradiction with the assumption.

Let u > q, t < q. Then q ∈ (t, u) ∩ (I ∪ {q} ∪ J), so we have all distinct

d(q), d(j) for j ∈ (q, u) ∩ J,

such that

q ≤ d(q) < u, B(q, d(q)) ≡ 0

and

j ≤ d(j) < u, B(j, d(j)) ≡ 0 for all j ∈ (q, u) ∩ J.

Thus, we may take r = q, t = q and u = u in Definition 1.13 to prove that J is non-essential in (q, s], which contradicts the assumption.

We introduce a lexicographic order “<” on the set of all subsets of (r, s].

Definition 2.5. Let I = {i_{a} < i_{a−1} < ⋯ < i_{1}}, J = {j_{b} < j_{b−1} < ⋯ < j_{1}} be distinct subsets of (r, s]. We write I < J if and only if one of the following conditions holds

(i) there exists c ∈ [1, min(a, b)] such that i_{c} < j_{c} and i_{f} = j_{f} for all f ∈ [1, c); (ii) b > a and i_{f} = j_{f} for all f ∈ [1, a].

The following lemma follows immediately from Definition 2.5.

Lemma 2.6. Let I, J ⊆ (r, s]. Then I > J if and only if ((r, s] \ I) < ((r, s] \ J).

Definition 2.7. Let two subsets I, J ⊆ (r, s] be decomposed into connected components (see Definition 1.7):

I = I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{H} = [b_{1}, c_{1}] ∪ [b_{2}, c_{2}] ∪ ⋯ ∪ [b_{H}, c_{H}],
J = J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{N} = [β_{1}, γ_{1}] ∪ [β_{2}, γ_{2}] ∪ ⋯ ∪ [β_{N}, γ_{N}].

(i) We write I ≪ J if and only if for all v = 1, 2, …, H there exist u_{v} ∈ [1, N] such that b_{v} = β_{u_{v}}, c_{v} ≤ γ_{u_{v}}.

(ii) Let I ≪ J be as in (i). We define sets Δ_{v}(I, J), v = 0, 1, …, H by setting

Δ_{0}(I, J) = ∪_{w=1}^{u_{1}−1}J_{w};
Δ_{v}(I, J) = (J_{u_{v}} \ I_{v}) ∪ ( ∪_{w=u_{v}+1}^{u_{v+1}−1} J_{w}), v = 1, 2, …, H − 1;
Δ_{H}(I, J) = (J_{u_{H}} \ I_{H}) ∪ ( ∪_{w=u_{H}+1}^{N} J_{w}).

(iii) Let I ≪ J be as in (i) and Δ_{v}(I, J) be as in (ii). We say that I is linked with J if and only if for all v ∈ [0, H] there exists a weakly increasing injection

d : Δ_{v}(I, J) → (−∞, b_{v+1} − 2]

such that B(j, d(j)) ≡ 0 for all j ∈ Δ_{v}(I, J) (b_{H+1} is interpreted as s + 2). We denote {d(j) | j ∈ Δ_{v}(I, J)} by Ω_{v}(I, J).

Definition 2.8. For any J ⊆ (r, s] we define the subset Ĵ ⊆ (r, s] to be the minimal (with respect to “<”, see 2.5) subset such that Ĵ ≪ J and Ĵ is linked with J.

Remark. Ĵ is well defined since J is always linked with J.

Lemma 2.9. Let I ≠ J be two essential subsets in (r, s]. Then Î ≠ Ĵ.

Proof. Let Î = Ĵ and assume without loss of generality that J > I. Then J ⊈ I. So we can choose t to be the maximal integer with t ∈ J, t ∉ I. Then J∩(t, s] ⊆ I∩(t, s]. Now J > I implies

J ∩ (t, s] = I ∩ (t, s]. (8)

Note that

t ∉ Ĵ (9)

since otherwise t ∈ Ĵ = Î ⊆ I.

Let

J = J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{N} = [β_{1}, γ_{1}] ∪ [β_{2}, γ_{2}] ∪ ⋯ ∪ [β_{N}, γ_{N}],
Ĵ = [b_{1}, c_{1}] ∪ [b_{2}, c_{2}] ∪ ⋯ ∪ [b_{H}, c_{H}]

be decompositions into connected components. By Definition 2.7 we have b_{v} = β_{u_{v}}, c_{v} ≤ γ_{u_{v}} for some u_{v} ∈ [1, N], v = 1, 2, …, H. Let m ∈ [1, N] be such that t ∈ J_{m}.

Put Z_{0} = (r, b_{1}), Z_{v} = (c_{v}, b_{v+1}), v = 1, 2, …, H − 1, Z_{H} = (c_{H}, s]. Then (r, s] \ Ĵ = Z_{0} ⊔ Z_{1} ⊔ ⋯ ⊔ Z_{H}. By (9), t ∈ (r, s] \ Ĵ. So there exists f ∈ [0, H] such that t ∈ Z_{f}.

Set

X = [t, γ_{m}] ∪ (∪_{w=m+1}^{u_{f+1}−1}J_{w})

where u_{H+1} is interpreted as N + 1. We claim that

X ⊆ Δ_{f}(Ĵ, J). (10)

Indeed, if f = 0 then t < b_{1}, t ∈ J_{m} imply m < u_{1} since J_{u_{1}} = [β_{u_{1}}, γ_{u_{1}}] = [b_{1}, γ_{u_{1}}]. So

X = [t, γ_{m}] ∪ (∪_{w=m+1}^{u_{1}−1}J_{w}) ⊆ ∪_{w=1}^{u_{1}−1}J_{w} = Δ_{0}(Ĵ, J).

If f ∈ [1, H) then t ∈ (c_{f}, b_{f+1}), t ∈ J_{m} imply u_{f} ≤ m ≤ u_{f+1} − 1 since β_{u_{f}} = b_{f} ≤ c_{f}, b_{f+1} = β_{u_{f+1}}. So, taking into account that t > c_{f} we get

X = [t, γ_{m}] ∪ (∪_{w=m+1}^{u_{f+1}−1}J_{w}) ⊆ (J_{u_{f}} \ [b_{f}, c_{f}]) ∪ (∪_{w=u_{f} +1}^{u_{f+1}−1}J_{w}) = Δ_{f}(Ĵ, J).

The case f = H is considered similarly.

By Definition 2.7(iii), the embedding (10) implies that for all j ∈ X there exist d(j) ∈ [j, b_{f+1} − 2], all distinct, with B(j, d(j)) ≡ 0 (b_{H+1} is interpreted as s + 2).

Put u = b_{f+1} − 1. Then we have t ∈ [r, s] \ I, u ∈ (r, s + 1] \ I. Besides, using (8), we get

(t, u) ∩ I = (t, u) ∩ J = (t, b_{f+1} − 1) ∩ J = (t, β_{u_{f+1}} − 1) ∩ J = X \ {t}.

Thus we have t, u, d(t), d(j) for j ∈ I ∩ (t, u) = X \ {t} as in Definition 1.13. This shows that I is not essential in (r, s] which contradicts the assumptions of the lemma.

3. Normality

We have defined in 1.16 the normal integers i in [r, s] (for λ). Now we introduce some related notions.

Definition 3.1. We define the set N_{λ}(r, s) as follows. If r is not normal in [r, s] for λ we put N_{λ}(r, s) = ∅. If r is normal in [r, s] for λ set

N_{λ}(r, s) = {i ∈ [r, s] | i is normal in [r, s] for λ, and C_{λ}(r, i) ≡ 0}.

In what follows we shall denote

N(r, s) = N_{λ}(r, s),
N′(r, s) = N_{λ(s)}(r, s),
N̄(r, s) = N_{λ(r)}(r, s).

ON DECOMPOSITION NUMBERS AND BRANCHING COEFFICIENTS 19

We put

ν(r, s) = |N(r, s)| ,
ν′(r, s) = |N′(r, s)| ,
ν̄(r, s) = |N̄(r, s)| .

Remark. If r is normal in [r, s] then r ∈ N(r, s) since C_{λ}(r, r) = 0. So ν(r, s) ≠ 0 if and only if r is normal in [r, s]. Lemma 3.2. Let r ≤ i ≤ t ≤ s. If i is normal in [r, s] then i is normal in [r, t]. Proof. This follows immediately from Definition 1.16. Lemma 3.3. Let λ_{r} ≢ 0, and

{r = i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

Then r is normal in [r, s] if and only if for all j ∈ (1, k] with B(r, i_{j}) ≡ 0 there exist d(j), all distinct, such that d(j) ∈ (1, j) and B(i_{d(j)}, i_{j}) ≡ 0. Proof. This is essentially proved in [14, 4.3], cf. also [14, 4.2]. Lemma 3.4. Let r be normal in [r, s], and

{m_{t} < m_{t−1} < ⋯ < m_{1}} = {m ∈ (r, s] | B(r, m) ≡ 0},

{d_{u} < d_{u−1} < ⋯ < d_{1}} = {d ∈ (r, s] | C(r, d) ≡ 0}.

If u > t then there exists v ∈ [1, u] such that d_{v} is normal in [r, s]. Proof. Let v be the least integer in [1, u] such that |{m_{w} | m_{w} ≥ d_{v}}| < v. (11) Then v is well defined since |{m_{w} | m_{w} ≥ d_{u}}| ≤ t < u. Note that d_{v} ∉ {m_{1}, m_{2}, …, m_{t}}. (12) Indeed, let d_{v} = m_{q}. Then v > 1 since otherwise (11) implies {m_{w} | m_{w} ≥ d_{1}} = ∅ giving a contradiction. If v > 1 then by (11) we have |{m_{q}, m_{q−1}, …, m_{1}}| < v, i.e. q < v. On the other hand,

{m_{w} | m_{w} ≥ d_{v−1}} ⊆ {m_{q−1}, m_{q−2}, …, m_{1}}

since d_{v−1} > d_{v} = m_{q}. Hence

|{m_{w} | m_{w} ≥ d_{v−1}}| ≤ q − 1 < v − 1

which contradicts the choice of v.

From (12) we have λ_{d_{v}} = B(r, d_{v}) − C(r, d_{v}) ≡ B(r, d_{v}) ≢ 0, i.e. λ_{d_{v}} ≢ 0. (13)

Now note that |{m_{w} | m_{w} > d_{v}}| = v − 1. (14)

In fact, if v = 1, this follows from (11). If v > 1 and {m_{w} | m_{w} > d_{v}} < v − 1 then

|{m_{w} | m_{w} ≥ d_{v−1}}| ≤ |{m_{w} | m_{w} > d_{v}}| < v − 1.

This contradicts the choice of v.

If i ∈ [1, u] and m ∈ (d_{i}, s] then B(d_{i}, m) ≡ C(r, d_{i}) + B(d_{i}, m) = B(r, m), i.e.

(15) B(d_{i}, m) ≡ B(r, m) for any i ∈ [1, u] and m ∈ (d_{i}, s].

Now (15) and (14) imply

{m ∈ (d_{v}, s] | B(d_{v}, m) ≡ 0} = {m_{v−1} < m_{v−2} < ⋯ < m_{1}}. (16)

Finally we prove that

(17) {d_{1}, d_{2}, …, d_{v−1}} compensates {m_{1}, m_{2}, …, m_{v−1}} in (d_{v}, s].

We may assume that v > 1 since otherwise (17) is trivial. Note that, in view of (15), d_{i} < m_{j} implies B(d_{i}, m_{j}) ≡ 0 for all i, j. So it suffices to prove that d_{i} ≤ m_{i} for i = 1, 2, …, v − 1. We prove this by induction on i. If d_{1} > m_{1} we get v = 1 by the definition of v. But this contradicts our assumption. Let i ∈ [2, v − 1], and we have proved that d_{j} ≤ m_{j} for j = 1, 2, …, i − 1. If d_{i} > m_{i} then |{m_{w} | m_{w} ≥ d_{i}}| = i − 1 < i, which contradicts the choice of v since i < v.

Now d_{v} is normal in [r, s] by (13), (16) and (17).

Lemma 3.5. Assume that r < s. Then

ν(r, s) = \begin{cases}ν(r, s − 1) + 1 & if ν(r, s − 1) ≠ 0, λ_{s} ≢ 0, C(r, s) ≡ 0; \\ ν(r, s − 1) − 1 & if ν(r, s − 1) ≠ 0, λ_{s} ≢ 0, B(r, s) ≡ 0; \\ ν(r, s − 1) & otherwise. \end{cases}

Proof. Put ν = ν(r, s − 1). If ν = 0 then r is not normal in [r, s − 1] (see Remark after 3.1), hence r is not normal in [r, s] by Lemma 3.2, i.e. ν(r, s) = 0. So we may assume that ν ≠ 0. Let

N(r, s − 1) = {i_{1} = r < i_{2} < ⋯ < i_{ν}}. (18)

Then

λ_{i_{v}} ≢ 0 for any v = 1, 2, …, ν. (19)

It also follows from 3.2 that

N(r, s) ⊆ N(r, s − 1) ∪ {s}. (20)

Note that

(21) B(i_{t}, m) ≡ B(i_{u}, m) for any t < u and m ≥ i_{u}; B(i_{t}, i_{u}) ≢ 0 for any t < u. (22)

Indeed, B(i_{t}, m) ≡ C(i_{1}, i_{t}) + B(i_{t}, m) = B(i_{1}, m). Similarly, B(i_{u}, m) ≡ B(i_{1}, m). This proves (21). Now take m = i_{u} in (21). We have B(i_{t}, i_{u}) ≡ B(i_{u}, i_{u}) = λ_{i_{u}} ≢ 0 by (19).

Assume first that λ_{s} ≡ 0. Then s is not normal in [r, s]. So, taking into account (20), it suffices only to prove that i_{1}, i_{2}, …, i_{ν} are all normal in [r, s]. Let t ∈ [1, ν]. Since λ_{i_{t}} ≢ 0 by (19), we have only to show that

M = {m ∈ (i_{t}, s] | B(i_{t}, m) ≡ 0}

is compensated in (i_{t}, s]. Let

M′ = {m ∈ (i_{t}, s − 1] | B(i_{t}, m) ≡ 0}.

Then M′ is compensated in (r, s−1] since i_{t} is normal in [r, s−1]. If B(i_{t}, s) ≢ 0 then M = M′. Hence M is compensated in (i_{t}, s]. If B(i_{t}, s) ≡ 0 then M = M′ ∪ {s}. Let Z be a set which compensates M′ in (i_{t}, s − 1]. Then Z ∪ {s} compensates M = M′ ∪ {s} since B(s, s) = λ_{s} ≡ 0.

Now let λ_{s} ≢ 0. Then s is normal in [r, s].

Assume B(r, s) ≢ 0. Since r = i_{1} we have from (21) that B(i_{t}, s) ≢ 0 for all t = 1, 2, …, ν. Now as above all i_{1}, i_{2}, …, i_{ν} are normal in [r, s]. Taking into account (20), we get

N(r, s) = \begin{cases}\{i_{1}, i_{2}, …, i_{ν}\} & if C(r, s) ≢ 0; \\ \{i_{1}, i_{2}, …, i_{ν}\} ∪ \{s\} & if C(r, s) ≡ 0. \end{cases}

Finally, assume B(r, s) ≡ 0. Then C(r, s) = B(r, s) − λ_{s} ≡ −λ_{s} ≢ 0. So, in view of (20), it suffices to prove that i_{1}, i_{2}, …, i_{ν−1} are normal in [r, s] and i_{ν} is not.

We have i = r_{1} So (20) implies B(i_{t}, s) ≡ 0 for all t = 1, 2, …, ν. Therefore

\begin{matrix}\{m ∈ (i_{t}, s] | B(i_{t}, m) ≡ 0\} = \{m ∈ (i_{t}, s − 1] | B(i_{t}, m) ≡ 0\} ∪ \{s\}, \\ t = 1, 2, …, ν. \end{matrix} (23)

Put

M_{t} = {m ∈ (i_{t}, i_{t+1} − 1] | B(i_{t}, m) ≡ 0}, t = 1, 2, …, ν

(i_{ν+1} is interpreted as s). By Lemma 3.2, i_{t} is normal in [i_{t}, i_{t+1} − 1] so M_{t} is compensated in (i_{t}, i_{t+1} − 1] by some set Z_{t} ⊆ (i_{t}, i_{t+1} − 1], t = 1, 2, …, ν. Now,

(21) and (22) imply

{m ∈ (i_{t}, s] | B(i_{t}, m) ≡ 0} = M_{t} ⊔ M_{t+1} ⊔ ⋯ ⊔ M_{ν} ⊔ {s}, t = 1, 2, …, ν. (24)

If t < ν, this set is compensated in (i_{t}, s] by Z_{t} ⊔ Z_{t+1} ⊔ ⋯ ⊔ Z_{ν} ⊔ {i_{ν}} since B(i_{ν}, s) ≡ 0. Therefore, taking into account (19), it follows that i_{t} is normal in [r, s], t = 1, 2, …, ν − 1.

It remains to prove that i_{ν} is not normal in [r, s]. Let M_{ν} = {m_{1}, m_{2}, …, m_{q}}. Then

{m ∈ (i_{ν}, s] | B(i_{ν}, m) ≡ 0} = {m_{1}, m_{2}, …, m_{q}} ∪ {s},

cf. (24). Note that B(s, s) = λ_{s} ≢ 0. So if {m_{1}, m_{2}, …, m_{q}} ∪ {s} is compensated in (i_{ν}, s] then there exist elements d_{1}, d_{2}, …, d_{q}, d_{q+1} ∈ (i_{ν}, s − 1], all distinct, with B(d_{q+1}, s) ≡ 0 and B(d_{v}, m_{v}) ≡ 0 for v = 1, 2, …, q. However,

C(i_{ν}, d_{q+1}) = B(i_{ν}, s) − B(d_{q+1}, s) ≡ 0,
C(i_{ν}, d_{v}) = B(i_{ν}, m_{v}) − B(d_{v}, m_{v}) ≡ 0, v = 1, 2, …, q.

So

|{d ∈ (i_{ν}, s − 1] | C(i_{ν}, d) ≡ 0}| > |{m ∈ (i_{ν}, s − 1] | B(i_{ν}, m) ≡ 0}|.

By Lemma 3.4, there exists d ∈ (i_{ν}, s − 1] which is normal in [i_{ν}, s − 1], and such that C(i_{ν}, d) ≡ 0. Then d is normal in [r, s − 1], and C(r, d) ≡ C(r, i_{ν}) + C(i_{ν}, d) ≡ 0, i.e. d ∈ N(r, s − 1). This contradicts (18). Thus, {m ∈ (i_{ν}, s] | B(i_{ν}, m) ≡ 0} is not compensated in (i_{ν}, s]. Hence i_{ν} is not normal in [r, s].

Lemma 3.6. Let ν = ν(r, s) ≠ 0,

{r = i_{1} < i_{2} < ⋯ < i_{ν}} = N(r, s),

and 1 ≤ j ≤ ν, i_{j} ≤ i_{j+1} − 2. Then N(i_{j}, i_{j+1} − 2) = {i_{j}} (here i_{ν+1} is interpreted as s + 2).

Proof. Since i_{j} ∈ N(r, s) then i_{j} ∈ N(i_{j}, s). So, by Lemma 3.2, i_{j} ∈ N(i_{j}, i_{j+1} − 2). Assume there is i ∈ (i_{j}, i_{j+1} −2] such that i is normal in (i_{j}, i_{j+1} −2] and C(i_{j}, i) ≡ 0. We have C(r, i) = C(r, i_{j}) + C(i_{j}, i). Hence

C(r, i) ≡ 0. (25)

We shall prove that i is normal in [r, s]. Then (25) will imply i ∈ N(r, s) giving a contradiction.

In view of (25), we have

B(i, i_{j+1} − 1) ≡ C(r, i) + B(i, i_{j+1} − 1) = B(r, i_{j+1} − 1) = C(r, i_{j+1}) − 1 ≡ −1 ≢ 0.

So

i_{j+1} − 1 ∉ {m ∈ (i, s] | B(i, m) ≡ 0}. (26)

Moreover, for v ∈ [j + 1, ν] we similarly obtain

B(i, i_{v}) ≡ C(r, i) + B(i, i_{v}) = B(r, i_{v}) = C(r, i_{v}) + λ_{i_{v}} ≡ λ_{i_{v}}.

Since i_{v} is normal in [r, s] we have λ_{i_{v}} ≢ 0, see Definition 1.16. Thus

i_{v} ∉ {m ∈ (i, s] | B(i, m) ≡ 0}, j + 1 ≤ v ≤ ν. (27)

Put

M_{v} = {m ∈ (i_{v}, i_{v+1} − 1] | B(i_{v}, m) ≡ 0}, j + 1 ≤ v ≤ ν

(i_{ν+1} is interpreted as s + 2). Let m ∈ (i_{v}, i_{v+1} − 1], j + 1 ≤ v ≤ ν. Then

C(i, i_{v}) = C(r, i_{v}) − C(r, i) ≡ 0

by (25). Therefore

B(i, m) = C(i, i_{v}) + B(i_{v}, m) ≡ (i_{v}, m).

So it follows from (26) and (27) that

\begin{aligned}M : & = \{m ∈ (i, s] | B(i, m) ≡ 0\} \\ & = \{m ∈ (i, i_{j+1} − 2] | B(i, m) ≡ 0\} ⊔ M_{j+1} ⊔ ⋯ ⊔ M_{ν}. \end{aligned} (28)

Since i is normal in [i_{j}, i_{j+1} − 2] there exists a subset Z ⊆ (i, i_{j+1} − 2] which compensates {m ∈ (i, i_{j+1} − 2] | B(i, m) ≡ 0}. It follows from Lemma 3.2 that i_{v} is normal in [i_{v}, i_{v+1} − 1], j + 1 ≤ v ≤ ν. So for such v there exists Z_{v} ⊆ (i_{v}, i_{v+1} − 1] which compensates M_{v} in (i_{v}, i_{v+1} − 1]. Therefore Z ⊔ Z_{j+1} ⊔ ⋯ ⊔ Z_{ν} compensates M. Moreover, λ_{i} ≢ 0 since i is normal in [i_{j}, i_{j+1} − 1]. So i is normal in [r, s].

Lemma 3.7. Let ν = ν(r, s) > 1 and

{r = i_{1} < i_{2} < ⋯ < i_{ν}} = N(r, s).

Then ν′(i_{j}, i_{j+1} − 1) = 0 for all j = 1, 2, …, ν − 1.

Proof. Let j ∈ [1, ν − 1]. Put λ′ = λ(i_{j+1} − 1), cf. (5). Then

B_{λ′}(i_{j}, i_{j+1} − 1) ≡ 0. (29)

Indeed, we have

B_{λ′}(i_{j}, i_{j+1} − 1) = ∑_{v=i_{j}}^{i_{j+1}−2} λ_{v} + (λ_{i_{j+1}−1} + 1) + (i_{j+1} − 1) − i_{j}

= ∑_{v=i_{j}}^{i_{j+1}−1} λ_{v} + i_{j+1} − i_{j} = C_{λ}(i_{j}, i_{j+1}).

On the other hand,

C_{λ}(i_{j}, i_{j+1}) = C_{λ}(r, i_{j+1}) − C_{λ}(r, i_{j}) ≡ 0.

If i_{j} = i_{j+1} − 1 then B_{λ′}(i_{j}, i_{j+1} − 1) = B_{λ′}(i_{j}, i_{j}) = λ_{i_{j}} + 1. So (29) implies λ_{i_{j}} + 1 ≡ 0. Hence i_{j} is not normal in [i_{j}, i_{j}] for λ′. Therefore ν′(i_{j}, i_{j+1} − 1) = ν′(i_{j}, i_{j}) = 0.

Assume that i_{j} ≤ i_{j+1} − 2. By Lemma 3.6 we have N(i_{j}, i_{j+1} − 2) = i_{j}, whence ν(i_{j}, i_{j+1} − 2) = 1. Now by virtue of Lemma 3.5 and (29) we have ν′(i_{j}, i_{j+1} − 1) = ν(i_{j}, i_{j+1} − 2) − 1 = 0.

4. σ-subsets

In 1.16 we have defined integers σ(i, j) = σ_{λ}(i, j) for any i, j with 1 ≤ i, j ≤ l, j ≥ i − 1. Recall that σ(i, j) ∈ {0, 1}.

We also define

σ′(i, j) = σ_{λ(j)}(i, j); (30) σ̄(i, j) = σ_{λ(i)}(i, j). (31)

Besides essential subsets we shall need one more class of subsets called σ-subsets. It will turn out that the number of essential subsets in (r, s] is equal to the number of σ-subsets in (r, s].

Definition 4.1.

(i) Let J = {j_{1} < j_{2} < ⋯ < j_{f}} ⊆ (r, s]. We set

σ(J) = σ_{r,s}(J) = σ(r, j_{1} − 2)σ(j_{1}, j_{2} − 2) … σ(j_{f−1}, j_{f} − 2)σ(j_{f}, s),

if J ≠ ∅, and

σ(∅) = σ_{r,s}(∅) = σ(r, s).

(ii) A subset J ⊆ (r, s] is called a σ-subset (in (r, s] for λ) if and only if σ(J) ≠ 0.

Remark. Clearly σ(i, j) = 1 if and only if ν(i, j) > 0, and σ(i, j) = 0 if and only if ν(i, j) = 0, cf. Remark after Definition 3.1.

Lemma 4.2. ♯{σ-subsets in (r, s]} = ∑_{J⊆(r,s]} σ(J).

Proof. The lemma follows immediately from Definition 4.1 since σ(J) ≠ 0 if and only if σ(J) = 1.

Lemma 4.3. Let

J = {j_{1} < j_{2} < ⋯ < j_{f}} ⊆ (r, s]

be a non-empty σ-subset. Put j_{0} = r. Assume ν′(j_{v}, j_{v+1} − 1) = 0 for v = 0, 1, …, f − 1. Then ν(r, s) ≥ f + 1, and r < j_{1} < j_{2} < ⋯ < j_{f} are the minimal f + 1 elements of the set N(r, s).

Proof. Throughout the proof we interpret j_{f+1} as s + 2. Note that

λ_{j_{v}} ≢ 0, v = 0, 1, …, f. (32)

Indeed, σ(J) = 1 implies σ(j_{v}, j_{v+1} − 2) = 1 for v = 0, 1, …, f. For v = f we have σ(j_{f}, s) = 1. Hence j_{f} is normal in [j_{f}, s]. In particular, λ_{j_{f}} ≢ 0. Let v ∈ [0, f). If j_{v} ≤ j_{v+1} − 2 then σ(j_{v}, j_{v+1} − 2) ≠ 0 similarly yields λ_{j_{v}} ≢ 0. Let j_{v} = j_{v+1} − 1. Then σ′(j_{v}, j_{v+1} − 1) = 0 means that j_{v} is not normal in [j_{v}, j_{v}] for λ(j_{v}), i.e.

λ_{j_{v}} + 1 ≡ 0 if v ∈ [0, f) and j_{v+1} = j_{v} + 1. (33)

Therefore λ_{j_{v}} ≢ 0 again. This proves (32).

We claim that

C_{λ}(j_{v}, j_{v+1}) ≡ 0, v = 0, 1, …, f − 1. (34)

Indeed, if j_{v+1} = j_{v}+1 then C_{λ}(j_{v}, j_{v+1}) = λ_{j_{v}} +1 ≡ 0 by (33). Assume j_{v} ≤ j_{v+1}−2. We have ν(j_{v}, j_{v+1} − 2) > 0, ν′(j_{v}, j_{v+1} − 2) = 0. So Lemma 3.5 implies

(35)  ν(j_{v}, j_{v+1} − 2) = 1 for all v ∈ [0, f) such that j_{v} ≤ j_{v+1} − 2;
(36)  λ_{j_{v+1}−1} + 1 ≢ 0 for all v ∈ [0, f) such that j_{v} ≤ j_{v+1} − 2;

and

(37) B_{λ(j_{v+1}−1)}(j_{v}, j_{v+1} − 1) ≡ 0 for all v ∈ [0, f) such that j_{v} ≤ j_{v+1} − 2.

Note that

B_{λ(j_{v+1}−1)}(j_{v}, j_{v+1} − 1) = ∑_{w=j_{v}}^{j_{v+1}−2} λ_{w} + (λ_{j_{v+1}−1} + 1) + (j_{v+1} − 1) − j_{v} = C_{λ}(j_{v}, j_{v+1}).

Now (37) implies C(j_{v}, j_{v+1}) ≡ 0 for v ∈ [0, f) with j_{v} ≤ j_{v+1} − 2. This completes the proof of (34).

Since C(j_{v}, j_{w}) = C(j_{v}, j_{v+1}) + C(j_{v+1}, j_{v+2}) + ⋯ + C(j_{w−1}, j_{w}), (34) implies

C(j_{v}, j_{w}) ≡ 0 for any 0 ≤ v < w ≤ f. (38)

Put

M_{v} = {m ∈ (j_{v}, j_{v+1} − 2] | B(j_{v}, m) ≡ 0}, v = 0, 1, …, f.

Of course, M_{v} = ∅ if j_{v+1} = j_{v} + 1.

Assume j_{v} ≤ j_{v+1} − 2. Then σ(j_{v}, j_{v+1} − 2) = 1 means that j_{v} is normal in [j_{v}, j_{v+1} − 2]. Hence there exists Z_{v} ⊆ (j_{v}, j_{v+1} − 2] which compensates M_{v} in (j_{v}, j_{v+1} − 2]. If j_{v} − j_{v+1} − 1 we set Z_{v} = ∅. We claim that

{m ∈ (j_{v}, s] | B_{λ}(j_{v}, m) ≡ 0} = M_{v} ⊔ M_{v+1} ⊔ ⋯ ⊔ M_{f}, v = 0, 1, …, f. (39)

Indeed, using (38) we get for any w ∈ (v, f]:

B_{λ}(j_{v}, j_{w} − 1) = C_{λ}(j_{v}, j_{w}) − 1 ≡ −1 ≢ 0,
B(j_{v}, j_{w}) = C_{λ}(j_{v}, j_{w}) + λ_{j_{w}} ≡ λ_{j_{w}} ≢ 0,

where we have used (32) for the last inequality. Hence

{m ∈ (j_{v}, s] | B_{λ}(j_{v}, m) ≡ 0} ⊆ ∪_{w=v}^{f}(j_{w}, j_{w+1} − 2].

Let m ∈ (j_{w}, j_{w+1} − 2] for some w ∈ [v, f]. Then, using (38) again, we have

B_{λ}(j_{v}, m) = C_{λ}(j_{v}, j_{w}) + B_{λ}(j_{w}, m) ≡ B_{λ}(j_{w}, m).

This proves (39).

However, Z_{v} ⊔ Z_{v+1} ⊔ ⋯ ⊔ Z_{f} clearly compensates M_{v} ⊔ M_{v+1} ⊔ ⋯ ⊔ M_{f}. So, taking into account (32) we conclude that r = j_{0}, j_{1}, …, j_{f} are normal in [r, s]. In view of (38), C(r, j_{v}) ≡ 0 for v = 0, 1, …, f. So, moreover, j_{0}, j_{1}, …, j_{f} ∈ N(r, s).

It remains to prove that i ∈ (r, j_{f}) \ {j_{1}, j_{2}, …, j_{f−1}} implies i ∉ N(r, s). Assume not. We have

C(r, i) ≡ 0. (40)

Suppose first that i ∈ (j_{v}, j_{v+1} − 2]. Then j_{v} ≤ j_{v+1} − 2. So (35) implies N(j_{v}, j_{v+1} − 2) = {j_{v}}. In view of (38), we have

C(j_{v}, i) ≡ C(r, j_{v}) + C(j_{v}, i) = C(r, i) ≡ 0,

see (40). So if i is normal in [j_{v}, j_{v+1} − 2] we would have i ∈ N(j_{v}, j_{v+1} − 2) giving a contradiction. Thus, i is not normal in [j_{v}, j_{v+1} − 2]. By Lemma 3.2, i is not normal in [r, s]. This contradicts the assumption i ∈ N(r, s).

Now suppose i = j_{v+1} − 1. Then j_{v} ≤ j_{v+1} − 2. The equation (40) implies C_{λ}(r, j_{v+1} −1) ≡ 0. This together with C_{λ}(r, j_{v}) ≡ 0 yields λ_{j_{v+1}−1} +1 ≡ 0. However this contradicts (36).

Recall the constants ν(i, j), ν′(i, j) introduced in 3.1.

Definition 4.4. Let J = {j_{1} < j_{2} < ⋯ < j_{f}} ⊆ (r, s]. We set

ν(J) = ν_{r,s}(J) = ν′(r, j_{1} − 1)ν′(j_{1}, j_{2} − 1) … ν′(j_{f−1}, j_{f} − 1)ν(j_{f}, s),

if J ≠ ∅, and

ν(∅) = ν_{r,s}(∅) = ν(r, s).

Lemma 4.5. ♯ {σ-subsets in (r, s]} = ∑_{J⊆(r,s]} ν(J).

Proof. Step 1. We associate to any σ-subset M a subset φ(M). We shall prove in Step 3 that ν(φ(M)) ≠ 0.

Let M = {m_{1} < m_{2} < ⋯ < m_{h}} be a σ-subset (in (r, s] for λ). We interpret m_{0} as r. Put

\begin{aligned}φ(M) & = \{m_{w_{1}} < m_{w_{2}} < ⋯ < m_{w_{f}} \} \\ & = \{m_{w} | 1 ≤ w ≤ h, ν′(m_{w−1}, m_{w} − 1) ≠ 0\}. \end{aligned} (41)

We interpret w_{0} as 0.

Step 2. To any subset J with ν(J) ≠ 0 we associate ν(J) subsets J(x_{0}, x_{1}, …, x_{f}). We shall prove in Step 4 that they are σ-subsets.

Let J = {j_{1} < j_{2} < ⋯ < j_{f}} ⊆ (r, s] be a subset in (r, s] with ν(J) ≠ 0. We interpret j_{0} as r and j_{f+1} as s + 2.

Put ν_{v} = ν′(j_{v}, j_{v+1} − 1), v = 0, 1, …, f − 1; ν_{f} = ν(j_{f}, s). Then ν(J) = ν_{0}ν_{1} … ν_{f}. We define ν(J) subsets J(x_{0}, x_{1}, …, x_{f}); 1 ≤ x_{v} ≤ ν_{v}, v = 0, 1, …, f, as follows. Let

{j_{v} = i_{1}^{(v)} < i_{2}^{(v)} < ⋯ < i_{ν_{v}}^{(v)}} = N′(j_{v}, j_{v+1} − 1), v = 0, 1, …, f − 1, (42)

{j_{f} = i_{1}^{(f)} < i_{2}^{(f)} < ⋯ < i_{ν_{f}}^{(f)}} = N(j_{f}, s) (43)

(cf. 3.1 for the definition of N′(i, j)).

Now put

\begin{matrix}J(x_{0}, x_{1}, …, x_{f}) = J ∪ (∪_{v=0}^{f} ∪_{q_{v}=2}^{x_{v}} \{i_{q_{v}}^{(v)}\}) , \\ 1 ≤ x_{v} ≤ ν_{v}, v = 0, 1, …, f. \end{matrix} (44)

Step 3. We show that

ν(φ(M)) ≠ 0, and if we put φ(M) = {j_{1} < j_{2} < ⋯ < j_{f}} = J then
there are some values x_{0}, x_{1}, …, x_{f} such that M = J(x_{0}, x_{1}, …, x_{f}).

(45)

To prove (45) we first show that

ν′(m_{w_{v}}, m_{w_{v+1}} − 1) ≥ w_{v+1} − w_{v}, and
m_{w_{v}} < m_{w_{v}+1} < ⋯ < m_{w_{v+1}−1} are the minimal w_{v+1} − w_{v}
elements of the set N′(m_{w_{v}}, m_{w_{v+1}} − 1); v = 0, 1, …, f − 1.

(46)

Indeed, if w_{v} = w_{v+1} − 1 then ν′(m_{w_{v}}, m_{w_{v+1}} − 1) ≠ 0 by definition, cf. (41). So (46) is evident. Now assume w_{v} < w_{v+1} − 1. We want to apply Lemma 4.3 to

{m_{w_{v}}, m_{w_{v+1}} − 1} instead of {r, s},
λ′ = λ(m_{w_{v+1}} − 1) instead of λ, and
M^{v} = {m_{w_{v}+1} < m_{w_{v}+2} < ⋯ < m_{w_{v+1}−1}} instead of J = {j_{1} < j_{2} < ⋯ < j_{f}}.

We may do it because (a) M^{v} ≠ ∅ (since w_{v} < w_{v+1} − 1).

(b) M^{v} is a σ-subset in (m_{w_{v}}, m_{w_{v+1}} − 1] for λ′. Indeed, σ(m_{i}, m_{i+1} − 2) ≠ 0 for i ∈ [w_{v}, w_{v+1} − 1) since M is a σ-subset in (r, s]. And it remains to note that σ′(m_{w_{v+1}−1}, m_{w_{v+1}} − 1) ≠ 0 by the definition of w_{j}, cf. (41).

(c) ν′(m_{i}, m_{i+1} − 1) = 0 for i ∈ [w_{v}, w_{v+1} − 1) (by the definition of w_{j}, cf. (41)). Now Lemma 4.3 implies (46).

Similarly one proves

ν(m_{w_{f}} , s) ≥ h − w_{f} + 1, and m_{w_{f}} < m_{w_{f} +1} < ⋯ < m_{h}
are the h − w_{f} + 1 minimal elements of the set N(m_{w_{f}} , s).

(47)

Now (45) follows from (46) and (47).

Step 4. Let J = {j_{1} < j_{2} < ⋯ < j_{f} ⊆ (r, s], ν(J) ≠ 0. We show that

(48) J = J(x_{0}, x_{1}, …, x_{f}) is a σ-set for all admissible x_{0}, x_{1}, …, x_{f}.

For, we have to prove that σ(i_{u}^{(v)}, i_{u+1}^{(v)} − 2) = 1 for any u = 1, 2, …, x_{v} − 1, and σ(i_{x_{v}}^{(v)}, j_{v+1} − 2) = 1; v = 0, 1, …, f (cf. (42), (43)).

Let v ∈ [0, f), and u ∈ [1, x_{v}). Since σ(j, j − 1) = 1 for any integer j we may assume that i_{u}^{(v)} ≤ i_{u+1}^{(v)} − 2. Since i_{u}^{(v)} ∈ N′(j_{v}, j_{v+1} − 1) then i_{u}^{(v)} is normal in [i_{u}^{(v)}, i_{u+1}^{(v)} − 2] by Lemma 3.2. Therefore σ(i_{u}^{(v)}, i_{u+1}^{(v)} − 2) = 1. The case v = f, u ∈ [1, x_{f}) is considered similarly.

Let v ∈ [0, f). We may assume that i_{x_{v}}^{(v)} ≤ j_{v+1} − 2. Since i_{x_{v}}^{(v)} ∈ N′(i_{1}^{(v)}, j_{v+1} − 1) we have i_{x_{v}}^{(v)} is normal in [i_{x_{v}}^{(v)}, j_{v+1} − 2] by Lemma 3.2, i.e. σ(i_{u}^{(v)}, i_{u+1}^{(v)} − 2) = 1. The case v = f is considered similarly. Thus, (48) is proved.

Step 5. Let J = {j_{1} < j_{2} < ⋯ < j_{f} ⊆ (r, s], ν(J) ≠ 0. We show that

φ(J(x_{0}, x_{1}, …, x_{f})) = J. (49)

For, we have to prove that (a) ν′(i_{u}^{(v)}, i_{u+1}^{(v)} − 1) = 0 for all u ∈ [1, x_{f}), v = 0, 1, …, f and

(b) ν′(i_{x_{v}}^{(v)}, j_{v+1} − 1) ≠ 0, v = 0, 1, …, f − 1.

Since i_{x_{v}}^{(v)} ∈ N′(j_{v}, j_{v+1} − 1) (cf. (42), (43)) we have i_{x_{v}}^{(v)} is normal in [j_{v}, j_{v+1} − 1] for λ(j_{v+1} − 1), i.e. ν′(i_{x_{v}}^{(v)}, j_{v+1} − 1) ≠ 0, giving (b). To prove (a) we apply Lemma 3.7 with

{j_{v}, j_{v+1} − 1} instead of {r, s},
λ(j_{v+1} − 1) instead of λ, and
i_{1}^{(v)} < i_{2}^{(v)} < ⋯ < i_{ν_{v}}^{(v)} instead of i_{1} < i_{2} < ⋯ < i_{ν}.

The equality (49) is proved.

Thus, to every subset J ⊆ (r, s] with ν(J) ≠ 0 we have associated ν(J) distinct σ-subsets J(x_{0}, x_{1}, …, x_{f}), cf (44), (48). In view of (49), we also get that J(x_{0}, x_{1}, …, x_{f}) ≠ J′(x′_{0}, x′_{1}, …, x′_{f}) if J ≠ J′. On the other hand, any σ-subset has the form J(x_{0}, x_{1}, …, x_{f}) for some set J with ν(J) ≠ 0, cf. (45). This proves the lemma.

5. Recurrence formulas for the number of essential subsets

Definition 5.1. Let 1 ≤ t, u ≤ l, J ⊆ (t, u]. We call J regular (in (t, u] for λ) if and only if there exists a weakly increasing injection d : J → (t, u] such that B(j, d(j)) ≡ 0 for all j ∈ J.

Remark. (i) The empty set is regular by definition.

(ii) We do not assume t ≤ u in 5.1 since we shall need to consider formally ∅ as a regular subset in (r, r − 1] (in the proof of Proposition 5.5 below).

Lemma 5.2. Let J be a regular subset in (r, s]. Then for any j ∈ J the set M ∩(j, s] is non-essential in (j, s].

Proof. This follows immediately from Definitions 5.1 and 1.13.

We now prove a technical lemma which is only used to deduce Corollary 5.4.

Lemma 5.3. Let J ⊆ (r, s] be a regular subset. Then J is essential if and only if r is normal in [r, s] and J is maximal among the regular subsets in (r, s] (with respect to “<”, cf. 2.5).

Proof. Let J = {j_{1}, j_{2}, …, j_{f}}. Set

M = {m_{1} < m_{2} < ⋯ < m_{e}} = {m ∈ [r, s] | B(r, m) ≡ 0}.

Since J is regular there exist d_{1}, d_{2}, …, d_{f}, all distinct, with d_{i} ∈ [j_{i}, s] and B(j_{i}, d_{i}) ≡ 0, i = 1, 2, …, f. Put

D = {d_{1}, d_{2}, …, d_{f}}.

Assume J is essential. Then D ⊇ M. Indeed, if m ∈ M, m ∉ D then we can take t = r, u = s + 1, d(j_{i}) = d_{i}, i = 1, 2, …, f, d(t) = m in Definition 1.13, i.e. J is not essential.

Now r ∉ D implies r ∉ M, i.e. B(r, r) ≢ 0. Since B(r, r) = λ_{r} we get

λ_{r} ≢ 0. (50)

Let m_{i} = d_{v_{i}}, i = 1, 2, …, e. Then {j_{v_{1}}, j_{v_{2}}, …, j_{v_{e}}} compensates M. Together with (50) this means that r is normal in [r, s], cf. 1.16.

Next we prove that J is maximal among the regular subsets in (r, s]. We may assume that j_{f} < j_{f−1} < ⋯ < j_{1}. Let

I = {i_{g} < i_{g−1} < ⋯ < i_{1}} ⊆ (r, s]

be another regular subset. Assume I > J. Then, in view of 2.5, one of the following conditions holds:

(a) there exists c ∈ [1, min(f, g)] such that i_{v} = j_{v} for v ∈ [1, c), and i_{c} > j_{c};

(b) g > f and i_{v} = j_{v} for v ∈ [1, f].

Assume (a) holds. Since I is regular, there exist δ_{1}, δ_{2}, …, δ_{g}, all distinct, such that δ_{v} ∈ [i_{v}, s] and B(i_{v}, δ_{v}) ≡ 0 for all v ∈ [1, g]. However i_{v} = j_{v} for v ∈ [1, c). So B(j_{v}, δ_{v}) ≡ 0, v = 1, 2, …, c − 1. Moreover, {j_{1}, j_{2}, …, j_{c−1}} = J ∩ (i_{c}, s], and i_{c} ∉ J. So we may take t = i_{c}, u = s + 1, d(j_{v}) = δ_{v} for v ∈ [1, c) and d(t) = δ_{c} in Definition 1.13. Thus, J is not essential, giving a contradiction.

Case (b) is considered similarly.

In the other direction, let r be normal in [r, s] and J be maximal among the regular subsets in (r, s]. Suppose J is not essential.

Now it is convenient to assume that j_{1} < j_{2} < ⋯ < j_{f}.

By Definition 1.13 there exist t, u ∈ [r, s + 1] \ J, with t < u, and a weakly increasing injection δ : {t} ∪ ((t, u) ∩ J) → [t, u), such that B(k, δ(k)) ≡ 0 for all k ∈ {t} ∪ ((t, u) ∩ J).

Assume first that t > r. Let

(t, u) ∩ J = {j_{a} < j_{a+1} < ⋯ < j_{b}}.

Note that {t} ∪ (J ∩ (t, s]) > J since t ∉ J.

Moreover, we claim that {t} ∪ (J ∩ (t, s]) is regular in (r, s]. Indeed, notice that

{t} ∪ (J ∩ (t, s]) = t, j_{a}, j_{a+1}, …, j_{b}, j_{b+1}, …, j_{f}.

Besides, B(t, δ(t)) ≡ 0, B(j_{v}, δ(j_{v})) ≡ 0 for v ∈ [a, b], and B(j_{v}, d_{v}) ≡ 0 for v ∈ (b, f]. It remains to observe that

δ(t), δ(j_{a}), δ(j_{a+1}), …, δ(j_{b}), d_{b+1}, …, d_{f}

are all distinct since δ(t) < u and δ(j_{v}) < u for v ∈ [a, b], while d_{v} ≥ j_{v} > u for v ∈ (b, f].

Thus, we have proved that {t} ∪ (J ∩ (t, s]) > J and {t} ∪ (J ∩ (t, s]) is regular. This contradicts the assumptions on J.

Now assume that t = r. Put

J′ = {j_{1} < j_{2} < ⋯ < j_{b}} = J ∩ (r, u),
Δ = {δ(j_{1}), δ(j_{2}), …, δ(j_{b})},
M = {m_{1} < m_{2} < ⋯ < m_{h}} = {m ∈ (r, u) | B(r, m) ≡ 0}.

Since r is normal in [r, s] there exist z(m_{1}), z(m_{2}), …, z(m_{h}), all distinct, with z(m_{v}) ∈ (r, m_{v}] and B(z(m_{v}), m_{v}) ≡ 0, v = 1, 2, …, h. Put

Z = {z(m_{1}), z(m_{2}), …, z(m_{h})}.

Note that

δ : J′ → Δ  and  z : M → Z

are bijections.

Since B(r, δ(t)) ≡ 0 we have

δ(t) ∈ M. (51)

We claim that

Z ⊈ J′. (52)

Indeed, let Z ⊆ J′. Then there exist c_{v} ∈ [1, b] such that z(m_{v}) = j_{c_{v}}, v = 1, 2, …, h. We have

C(r, j_{c_{v}}) = C(r, z(m_{v})) = B(r, m_{v}) − B(z(m_{v}), m_{v}) ≡ 0.

So

B(r, δ(j_{c_{v}})) = C(r, j_{c_{v}}) + B(j_{c_{v}}, δ(j_{c_{v}})) ≡ 0, v = 1, 2, …, h.

Therefore δ(j_{c_{1}}), δ(j_{c_{2}}), …, δ(j_{c_{h}}) are h distinct elements of M. Since |M| = h this yields M ⊆ Δ, which contradicts (51) since δ(t) ∉ Δ.

We define an integer q and elements

z^{(0)},z^{(1)}, …, z^{(q)} ∈ Z;
j^{(1)}, …, j^{(q)} ∈ J′;
δ^{(1)}, …, δ^{(q)} ∈ Δ;
m^{(0)},m^{(1)}, …, m^{(q)} ∈ M

inductively as follows. Put

m^{(0)} = δ(t).

Then m^{(0)} ∈ M by (51). So we may define an element z^{(0)} ∈ Z by putting

z^{(0)} = z(m^{(0)}).

If z^{(0)} ∉ J′ we put q = 0.

Assume that i > 0, that z^{(v)}, m^{(v)} have been defined for all v ∈ [0, i), and that j^{(v)}, δ^{(v)} have been defined for all v ∈ [1, i). If z^{(i−1)} ∉ J′ we put q = i−1. Otherwise define z^{(i)}, j^{(i)}, δ^{(i)}, m^{(i)} as follows. Put

j^{(i)} = z^{(i−1)}.

Since z^{(i−1)} ∈ J′ we have j^{(i)} ∈ J′, and so we may set

δ^{(i)} = δ(j^{(i)}).

Since j^{(i)} ∈ Z we have j^{(i)} = z(m) for some m ∈ M. So

C(r, j^{(i)}) = C(r, z(m)) = B(r, m) − B(z(m), m) ≡ 0.

Hence

B(r, δ^{(i)}) = B(r, δ(j^{(i)})) = C(r, j^{(i)}) + B(j^{(i)}, δ(j^{(i)})) ≡ 0.

Thus, δ^{(i)} ∈ M since δ^{(i)} ∈ (r, u). So we may set

m^{(i)} = δ^{(i)}.

Finally put

z^{(i)} = z(m^{(i)}).

Recall that Z ⊈ J′ by (52). So to show that q is well defined, it suffices to prove that z^{(0)}, z^{(1)}, …, z^{(i)} are all distinct. If i = 0 this is trivial. Let i > 0, and z^{(0)}, z^{(1)}, …, z^{(i−1)} be all distinct. Since z^{(v)} = z(m^{(v)}), and z is bijective, it suffices to prove that m^{(0)}, m^{(1)}, …, m^{(i)} are all distinct. Recall that m^{(0)} = δ(t), m^{(v)} = δ^{(v)} for v ∈ [1, i]. So we have to prove that δ(t), δ^{(1)}, δ^{(2)}, …, δ^{(i)} are all distinct. However δ^{(1)}, δ^{(2)}, …, δ^{(i)} ∈ Δ, while δ(t) ∉ Δ. So it is enough to check that δ^{(1)}, δ^{(2)}, …, δ^{(i)} are all distinct. But δ^{(v)} = δ(j^{(v)}), v = 1, 2, …, i, and δ is bijective. So we need only to show that j^{(1)}, j^{(2)}, …, j^{(i)} are all distinct. Now it suffices to use j^{(v)} = z^{(v−1)}, v = 1, 2, …, i, and the inductive hypothesis.

Let us consider the set I = {z^{(q)}} ∪ J. By definition of q we have z^{(q)} ∉ J′. Since z^{(q)} ∈ (r, u), and J′ = J ∩ (r, u), we conclude that z^{(q)} ∉ J. Hence I > J.

We claim that I is regular. Indeed, δ^{(q)} = m^{(q)}, z^{(q)} = z(m^{(q)}). So

z^{(q)} ≤ δ^{(q)} and B(z^{(q)}, δ^{(q)}) ≡ 0. (53)

Let v ∈ [2, q]. Then j^{(v)} = z^{(v−1)} = z(m^{(v−1)}), m^{(v−1)} = δ^{(v−1)}. So

j^{(v)} ≤ δ^{(v−1)} and B(j^{(v)}, δ^{(v−1)}) ≡ 0 for v = 2, 3, …, q. (54)

Moreover, j^{(1)} = z^{(0)} = z(m^{(0)}), m^{(0)} = δ(t). So

j^{(1)} ≤ δ(t) and B(j^{(1)}, δ(t)) ≡ 0. (55)

We also have

B(j, δ(j)) ≡ 0 for j ∈ J′ \ {j^{(1)}, j^{(2)}, …, j^{(q)}}, (56)

and

B(j_{v}, d_{v}) ≡ 0 for v ∈ (b, f]. (57)

In view of (53)-(57), to prove that I is regular it suffices to check that

δ^{(1)}, δ^{(2)}, …, δ^{(q)}, δ(t), δ(j) for j ∈ J′ \ {j^{(1)}, j^{(2)}, …, j^{(q)}}, d_{b+1}, d_{b+2}, …, d_{f}

are all distinct. Note that d_{b+1}, d_{b+2}, …, d_{f} > u. On the other hand, δ^{(v)} < u, v = 1, 2, …, q; δ(t) < u; and δ(j) < u for j ∈ J′ \ {j^{(1)}, j^{(2)}, …, j^{(q)}}. So it is enough to verify that

δ^{(1)}, δ^{(2)}, …, δ^{(q)}, δ(t), δ(j) for j ∈ J′ \ {j^{(1)}, j^{(2)}, …, j^{(q)}}

are all distinct. But this follows immediately from the following facts:

(a) δ^{(v)} = δ(j^{(v)}), v = 1, 2, …, q;

(b) δ : J′ → Δ is bijective;

(c) δ(t) ∉ Δ.

Thus, we have found a regular set I > J. This contradicts our assumption.

Corollary 5.4. There exists an essential regular subset in (r, s] if and only if σ(r, s) = 1. In this case such a set is unique.

Proof. Recall that σ(r, s) = 1 if and only if r is normal in [r, s], cf. 1.13. Moreover, the set of regular subsets is always non-empty since ∅ is regular. Now the statement follows from 5.3.

Proposition 5.5. ε(r, s) = σ(r, s) + ∑_{v=r+1}^{s} σ(r, v − 2)ε(v, s).

Proof. Let v ∈ (r, s], and assume that σ(r, v − 2) = 1. Then by 5.4 there exists a unique essential regular subset I ⊆ (r, v − 2]. (If v = r + 1 we take I = ∅, cf. Remark after 5.1). Let J ∈ E(v, s). Then by Lemma 2.4, the set I ∪ {v} ∪ J is essential in (r, s]. We denote this set by Λ(v, J). Remark that Λ(v, J) is defined for any v ∈ (r, s] such that σ(r, v − 2) ≠ 0 and any J ∈ E(v, s). Note also that Λ(v, J) does not depend in I since I is uniquely determined by v.

Assume σ(r, s) = 1. Then by 5.4 there exists a unique essential regular subset I ⊆ (r, s]. We denote it by Λ_{0}.

Note that we have constructed σ(r, s) + ∑_{v=r+1}^{s} σ(r, v − 2)ε(v, s) essential subsets in (r, s]. But we need to check that they are all distinct, and that any essential subset has a form Λ(v, J) or Λ_{0}.

We first prove that v is uniquely determined by the set Λ(v, J) as follows. (∗) Let v ∈ (r, s], σ(r, v − 2) = 1, J ∈ E(v, s). Set m to be the maximal element of Λ(v, J) such that the following two conditions hold.

(a) m − 1 ∉ Λ(v, J);

(b) Λ(v, J) ∩ (r, m − 2] is regular in (r, m − 2].

Then m = v. Indeed, m = v clearly satisfies (a) and (b). Assume m > v. By (b), for all

x ∈ Λ(v, J) ∩ (r, m − 2] there exist δ(x), all distinct, with x ≤ δ(x) ≤ m − 2 and B(x, δ(x)) ≡ 0. Note that (a) and m > v imply v ∈ Λ(v, J) ∩ (r, m − 2]. So we may take r = v, s = s, J = J, t = v, u = m − 1 (see (a)), d(t) = δ(v), d(x) = δ(x) for x ∈ J ∩ (t, u) in Definition 1.13. Thus J is not essential in (v, s]. The contradiction obtained proves (∗).

Next, we prove

(∗∗) All the sets Λ(v, J) with v ∈ (r, s], σ(r, v − 2) = 1, J ∈ E(v, s)

are distinct. Moreover, if σ(r, s) = 1 then

Λ_{0} ∉ {Λ(v, J) | v ∈ (r, s], σ(r, v − 2) = 1, J ∈ E(v, s)}.

Indeed, it is clear that Λ(v, J_{1}) ≠ Λ(v, J_{2}) if J_{1} ≠ J_{2}. It also follows from (∗) that Λ(v_{1}, J_{1}) ≠ Λ(v_{2}, J_{2}) if v_{1} ≠ v_{2}. Finally, let σ(r, s) = 1. The set Λ_{0} is regular in (r, s] by definition. By Lemma 5.2, we get that Λ_{0} ∩ (v, s] is not essential in (v, s] for any v ∈ Λ_{0}. But Λ(v, J) ∩ (v, s] = J is essential in (v, s]. So Λ_{0} ≠ Λ(v, J) for all admissible v and J. Thus (∗∗) is proved.

It remains to prove that any essential subset in (r, s] coincides with one of the Λ(v, J) or Λ_{0}.

Let M ∈ E(r, s). If M is regular in (r, s] then M = Λ_{0} by 5.4. So we may assume that M is not regular. Let v be the maximal element of M such that

(1) v − 1 ∉ M;

(2) M ∩ (r, v − 2] is regular in (r, v − 2].

Note that v is well defined because (1) and (2) hold for v = min M.

We claim that M ∩ (v, s] is essential in (v, s]. Assume not. By Definition 1.13, there are t, u ∈ [v, s + 1] \ (M ∩ (v, s]), with t < u and a weakly increasing injection d : {t} ∪ ((M ∩ (v, s]) ∩ (t, u)) → [t, u) such that B(k, d(k)) ≡ 0 for all k ∈ {t} ∪ ((M ∩ (v, s]) ∩ (t, u)). (Note that actually (M ∩ (v, s]) ∩ (t, u) = M ∩ (t, u)).

If t > v then t ∈ (r, s]\M. Besides, u ∈ (r, s+1]\M, and thus M is not essential in (r, s], giving a contradiction.

Let t = v. Then M ∩ (r, u) is regular in (r, u), since M ∩ (r, v − 2] is regular in (r, v − 2], v − 1 ∉ M, and for all j ∈ M ∩ [v, u) there exist d(j), all distinct, with j ≤ d(j) < u, B(j, d(j)) ≡ 0. If (u, s] ∩ M = ∅ this implies that M is regular in (r, s], since u ∉ M. So we may assume (u, s] ∩ M ≠ ∅. Let m = min{(u, s] ∩ M}. Then m − 1 ≥ u, so m − 1 ∉ M. We also have M ∩ (r, m − 2] is regular in (r, m − 2]. Now m > u > v contradicts the choice of v.

Thus, M ∩ (v, s] is essential in (v, s].

Moreover, M ∩ (r, v − 2] is regular in (r, v − 2] by the definition of v, and is essential in (r, v − 2] by Lemma 2.2. Since M = (M ∩ (r, v − 2]) ∪ {v} ∪ (M ∩ (v, s]) we get M = Λ (v, M ∩ (v, s]).

Corollary 5.6.

(i) ε(r, s) = ∑_{J⊆(r,s]} σ(J); (ii) ε(r, s) = ♯{σ-subsets in (r, s]}; (iii) ε(r, s) = ∑_{J⊆(r,s]} ν(J); (iv) ε(r, s) = ν(r, s) + ∑_{v=r+1}^{s} ν′(r, v − 1)ε(v, s).

Proof. By Proposition 5.5,

ε(r, s) = σ(r, s) + ∑_{v=r+1}^{s} σ(r, v − 2)ε(v, s).

In particular, ε(r, r) = σ(r, r) which gives (i) for s = r since σ(∅) = σ(r, s). Assume (i) has been proved for all r′, s′ with s′ − r′ < s − r. Then (see Definition 4.1)

ε(r, s) = σ_{r,s}(∅) + ∑_{v=r+1}^{s} σ(r, v − 2) ∑_{J⊆(v,s]} σ_{v,s}(J)

= σ_{r,s}(∅) + ∑_{v=r+1}^{s} ∑_{J⊆(r,s],J≠∅,min J=v} σ_{r,s}(J)

= ∑_{J⊆(r,s]} σ_{r,s}(J).

Thus (i) is proved. Part (ii) follows from (i) and Lemma 4.2. Part (iii) follows from (ii) and Lemma 4.5. To prove (iv) note that

∑_{J⊆(r,s]} ν(J) = ν_{r,s}(∅) + ∑_{J⊆(r,s],J≠∅} ν_{r,s}(J)

= ν(r, s) + ∑_{v=r+1}^{s} ∑_{J⊆(r,s],J≠∅,min J=v} ν_{r,s}(J)

= ν(r, s) + ∑_{v=r+1}^{s} ν′(r, v − 1) ∑_{J⊆(v,s]} ν_{v,s}(J)

= ν(r, s) + ∑_{v=r+1}^{s} ν′(r, v − 1)ε(v, s),

in view of (iii).

Definition 5.7. Let J = {j_{1} < j_{2} < ⋯ < j_{f}} ⊆ (r, s]. We set

ε(J) = ε_{r,s}(J) = ε′(r, j_{1} − 1)ε′(j_{1}, j_{2} − 1) … ε′(j_{f−1}, j_{f} − 1)ε(j_{f}, s),
ε′(J) = ε′_{r,s}(J) = ε′(r, j_{1} − 1)ε′(j_{1}, j_{2} − 1) … ε′(j_{f−1}, j_{f} − 1)ε′(j_{f}, s),

if J ≠ ∅, and

ε(∅) = ε_{r,s}(∅) = ε(r, s), ε′(∅) = ε′_{r,s}(∅) = ε′(r, s).

Corollary 5.8.

(i) ν(r, s) = ∑_{J⊆(r,s]}(−1)^{|J|}ε(J); (ii) ν(r, s) = ε(r, s) − ∑_{v=r+1}^{s} ε′(r, v − 1)ν(v, s).

Proof. By Corollary 5.6(iv) we have

ν(r, s) = ε(r, s) − ∑_{v=r+1}^{s} ν′(r, v − 1)ε(v, s). (58)

We use induction on s − r to prove (i). If s = r then it follows from (58) that ν(r, r) = ε(r, r) = ε_{r,r}(∅), as desired. Assume s − r > 0, and (i) has been proved for all r′, s′ with s′ − r′ < s − r. Then it follows from (58) that

ν(r, s) = ε_{r,s}(∅) − ∑_{v=r+1}^{s} ∑_{J⊆(r,v−1]}(−1)^{|J|}ε′_{r,v−1}(J)ε(v, s)

= ε_{r,s}(∅) + ∑_{v=r+1}^{s} ∑_{J⊆(r,s],J≠∅,max J=v}(−1)^{|J|}ε_{r,s}(J)

= ∑_{J⊆(r,s]}(−1)^{|J|}ε_{r,s}(J).

Thus, (i) is proved. To prove (ii) note that

∑_{J⊆(r,s]}(−1)^{|J|}ε(J) = ε_{r,s}(∅) + ∑_{J⊆(r,s],J≠∅}(−1)^{|J|}ε_{r,s}(J)

= ε(r, s) + ∑_{v=r+1}^{s} ∑_{J⊆(r,s],J≠∅,min J=v}(−1)^{|J|}ε_{r,s}(J)

= ε(r, s) − ∑_{v=r+1}^{s} ε′(r, v − 1) ∑_{J⊆(v,s]}(−1)^{|J|}ε_{v,s}(J)

= ε(r, s) − ∑_{v=r+1}^{s} ε′(r, v − 1)ν(v, s),

in view of (i).

If we fix positions i between r and s with λ_{i} ≢ 0 then the recurrence formula from Proposition 5.5 can be improved:

Corollary 5.9. Assume that

{i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

Then ε(r, s) = 1 if k = 1, and

ε(r, s) =σ(i_{1}, i_{k}) + (i_{2} − i_{1})ε(i_{2}, i_{k})

+ ∑_{v=2}^{k−1} ((i_{v+1} − i_{v} − 1)σ(i_{1}, i_{v}) + σ(i_{1}, i_{v−1}))ε(i_{v+1}, i_{k})

if k ≥ 2.

Proof. By Lemma 2.3, ε(r, s) = ε(i_{1}, i_{k}). If k = 1 then ε(i_{1}, i_{k}) = ε(i_{1}, i_{1}) = 1, and we are done. Let k ≥ 2. Then by Proposition 5.5, we have

ε(i_{1}, i_{k}) =σ(i_{1}, i_{k}) + ∑_{t=i_{1}+1}^{i_{k}} σ(i_{1}, t − 2)ε(t, i_{k})

=σ(i_{1}, i_{k}) + ∑_{t=i_{1}+1}^{i_{2}} σ(i_{1}, t − 2)ε(t, i_{k})

+ ∑_{v=2}^{k−1} (σ(i_{1}, i_{v} − 1)ε(i_{v} + 1, i_{k}) + ∑_{t=i_{v}+2}^{i_{v+1}} σ(i_{1}, t − 2)ε(t, i_{k})) .

Let t ∈ (i_{1}, i_{2}]. By Lemma 2.3 we have ε(t, i_{k}) = ε(i_{2}, i_{k}) since λ_{i_{1}+1} ≡ λ_{i_{1}+2} ≡ ⋯ ≡ λ_{i_{2}−1} ≡ 0. Moreover, σ(i_{1}, t − 2) = σ(i_{1}, i_{1}) = 1, in view of Definition 1.16 and Lemma 3.3. So

∑_{t=i_{1}+1}^{i_{2}} σ(i_{1}, t − 2)ε(t, i_{k}) = (i_{2} − i_{1})ε(i_{2}, i_{k}).

Similarly we get

σ(i_{1}, i_{v} − 1) = σ(i_{1}, i_{v−1}), ε(i_{v} + 1, i_{k}) = ε(i_{v+1}, i_{k}), v = 2, 3, …, k − 1;

and

σ(i_{1}, t−2) = σ(i_{1}, i_{v}), ε(t, i_{k}) = ε(i_{v+1}, i_{k}), t ∈ [i_{v} +2, i_{v+1}], v = 2, 3, …, k−1.

So

∑_{t=i_{v}+2}^{i_{v+1}} σ(i_{1}, t − 2)ε(t, i_{k}) = (i_{v+1} − i_{v} − 1)σ(i_{1}, i_{v})ε(i_{v+1}, i_{k}),

and the statement follows.

Remark. Let T (r, s) = T_{λ}(r, s) be the following (s − r + 1) by (s − r + 1) matrix

[\begin{matrix}ν′(r, r) & ν′(r, r + 1) & ⋯ & ν′(r, s − 1) & ν(r, s) \\ −1 & ν′(r + 1, r + 1) & ⋯ & ν′(r + 1, s − 1) & ν(r + 1, s) \\ 0 & −1 & ⋯ & ν′(r + 2, s − 1) & ν(r + 2, s) \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ 0 & 0 & ⋯ & ν′(s − 1, s − 1) & ν(s − 1, s) \\ 0 & 0 & ⋯ & −1 & ν(s, s) \end{matrix}] .

Then Corollary 5.6(iii) can be reformulated as follows

ε(r, s) = det T (r, s). (59)

Right hand sides of the expressions for ε(r, s) from Corollary 5.6(i) and Corollary 5.9 can also be interpreted in terms of certain determinants (this is done in Theorem 1.18).

6. Quasi-latticed sequences and sets

Definition 6.1. Let T = {t_{1}, t_{2}, …, t_{m}} be a finite sequence with t_{i} =‘+1’,‘−1’ or ‘0’. We call such a sequence quasi-sign sequence. (The empty sequence is quasi-sign by definition.)

Definition 6.2. Let T = {t_{1}, t_{2}, …, t_{m}} be a quasi-sign sequence. We call it quasilatticed if and only if ∑_{i=1}^{j} t_{i} ≥ 0 for all j = 1, 2, …, m. (The empty sequence is quasi-latticed by definition.)

Definition 6.3. Let T = {t_{1}, t_{2}, …, t_{m}} be a quasi-sign sequence.

(i) For 1 ≤ i ≤ j ≤ m we denote by T (i, j) the subsequence {t_{i}, t_{i+1}, …, t_{j}}. (ii) Let J be a subset in [1, m]. We call J a quasi-latticed subset (in [1, m] for

T) if and only if the following two conditions hold (a) J ⊆ {i | t_{i} = −1 or t_{i} = ±};

(b) Let [1, m] \ J = [b_{1}, c_{1}] ∪ [b_{2}, c_{2}] ∪ ⋯ ∪ [b_{N}, c_{N}] be the decomposition into the union of connected components (see 1.7). Then the sequences T (b_{i}, c_{i}), i = 1, 2, …, N, are quasi-latticed.

(iii) We denote by q(T) the number of quasi-latticed subsets in [1, m] for T.

Remark. If T = ∅ we interpret q(T) = 1 (since the empty subset is the only quasilatticed subset in [1, 0] = ∅).

Recall that throughout Part I we assume that λ = (λ_{1}, λ_{2}, …, λ_{l}) ∈ ℤ_{+}^{l}.

Definition 6.4. We define a quasi-sign sequence T_{r,s}(λ) as follows. Let

{i_{1} < i_{2} < ⋯ < i_{m}}

be the set of all i ∈ (r, s) with λ_{i} > 0 and either B_{λ}(r, i) ≡ 0 or C_{λ}(r, i) ≡ 0 (or both). Then

T_{r,s}(λ) = {t_{1}, t_{2}, …, t_{m}}

where

t_{j} = \begin{cases}+1 & if B_{λ}(r, i) ≢ 0, C_{λ}(r, i) ≡ 0; \\ −1 & if B_{λ}(r, i) ≡ 0, C_{λ}(r, i) ≢ 0; \\ 0 & if B_{λ}(r, i) ≡ 0, C_{λ}(r, i) ≡ 0. \end{cases}

Remark. (a) If both B_{λ}(r, i) ≡ 0 and C_{λ}(r, i) ≡ 0 then we have λ_{i} ≡ 0.

(b) T_{r,s}(λ) may be empty. For example T_{r,r}(λ) is always empty.

Definition 6.5. We define the integer q_{r,s}(λ) as follows. Put

q_{r,s}(λ) = 0

if at least one of the following conditions holds.

(a) λ_{r} = 0;

(b) λ_{s} = 0;

(c) B_{λ}(r, s) ≢ 0.

Let λ_{r} > 0, λ_{s} > 0 and B_{λ}(r, s) ≡ 0. Then we put

q_{r,s}(λ) = q(T_{r,s}(λ)),

see 6.4, 6.3(iii).

In what follows we denote

q_{r,s} = q_{r,s}(λ),
q′_{r,s} = q_{r,s}(λ(s)) (see (5)).

Lemma 6.6. Let T = {t_{1}, t_{2}, …, t_{m}} be a quasi-sign sequence, and put T′ = {t_{1}, t_{2}, …, t_{m}, +1}. Then q(T) = q(T′).

Proof. This follows immediately from Definition 6.3.

Lemma 6.7. Let T = {t_{1}, t_{2}, …, t_{m}} be a quasi-sign sequence. For any j ∈ [1, m] put

T_{j}^{−} = {t_{1}, t_{2}, …, t_{j−1}}, T_{j}^{+} = {t_{j+1}, t_{j+2}, …, t_{m}}.

Also put

T_{≤0} = {j ∈ [1, m] | t_{j} = −1 or t_{j} = 0}.

Then

q(T) = x + ∑{q(T_{j}^{−}) | j ∈ T_{≤0}, T_{j}^{+} is quasi-latticed}

where x = 1 if T is quasi-latticed, and x = 0 otherwise.

Proof. The empty subset in [1, m] is quasi-latticed if and only if T is quasi-latticed, i.e. if and only if x = 1.

Let J be a non-empty quasi-latticed subset in [1, m]. Put j = max J. Then j ∈ T_{≤0}. Moreover T_{j}^{+} is quasi-latticed, and J ∩[1, j −1] is quasi-latticed in [1, j −1] for T_{j}^{−}.

On the other hand, if j ∈ T_{≤0} is such that T_{j}^{+} is quasi-latticed, and J′ is a quasilatticed subset in [1, j − 1] for T_{j}^{−} then J ∪ {j} is quasi-latticed in [1, m] for T and max J ∪ {j} = j.

This proves the lemma.

Lemma 6.8. Let r < s. Then r is normal in [r, s − 1] if and only if λ_{r} ≢ 0 and T_{r,s}(λ) is quasi-latticed.

Proof. Let

{i_{1}, i_{2}, …, i_{m}} = {i ∈ (r, s) | λ_{i} > 0, and B(r, i) ≡ 0 or C(r, i) ≡ 0},
T = T_{r,s}(λ) = {t_{1}, t_{2}, …, t_{m}},

see Definition 6.4. Put

J^{+} (resp., J^{−}, J^{0}) = {j ∈ [1, m] | t_{j} = +1 (resp., − 1, 0)}.

In view of 1.16 we may assume that λ_{r} ≢ 0.

Note that

I := {i ∈ (r, s − 1] | λ_{i} ≢ 0, B(r, i) ≡ 0} = {i_{j} | j ∈ J^{−}}.

Indeed, let j ∈ J^{−}. Then B(r, i_{j}) ≡ 0 by definition (see 6.4). Moreover,

λ_{i_{j}} = B(r, i_{j}) − C(r, i_{j}) ≡ −C(r, i_{j}) ≢ 0.

So i_{j} ∈ I. In the other direction, if B(r, i) ≡ 0 then i = i_{j} for j ∈ J^{−} ∪J^{±}. However, λ_{i} ≢ 0 implies C(r, i) ≢ 0 so j ∈ J^{−}.

Now, by virtue of Lemma 3.3, r is normal in [r, s − 1] if and only if for all i ∈ I there exist f(i) ∈ (r, i), all distinct, such that λ_{f(i)} ≢ 0 and B (f(i), i) ≡ 0. For such f(i) we have

C(r, f(i)) = B (r, i) − B (f(i), i) ≡ 0.

So f(i) = i_{d(i)} for some d(i) ∈ J^{+} ∪ J^{±}. Moreover, λ_{f(i)} ≢ 0 implies

B(r, f(i)) = C (r, f(i)) + λ_{f(i)} ≡ λ_{f(i)} ≢ 0.

So d(i) ∈ J^{+}. Thus if r is normal in [r, s − 1] then for all j ∈ J^{−} there exist d(j) ∈ J^{+}, all distinct, with 1 ≤ d(j) < j. This is equivalent to the fact that T is quasi-latticed. The argument is easily reversed.

To describe some decomposition numbers below we shall need the following recurrence formula for q_{r,s}. Recall the constants σ̄(i, j) defined in (31).

Proposition 6.9. Assume r < s, λ_{r} > 0, λ_{s} > 0, B_{λ}(r, s) ≡ 0. Then

q_{r,s} = q_{r,s−1} + σ(r, s − 1) + ∑_{i=r}^{s−2} q_{r,i}σ̄(i + 1, s − 1).

Moreover, if λ_{s} ≡ 0 then

q_{r,s} = q′_{r,s−1}.

Proof. It follows from Definition 6.5 that q_{r,s} = q(T_{r,s}(λ)).

Assume first that λ_{s} ≡ 0. Then

B_{λ(s−1)}(r, s − 1) = ∑_{u=r}^{s−2} λ_{u} + (λ_{s−1} + 1) + (s − 1) − r

= ∑_{u=r}^{s−1} λ_{u} + s − r ≡ ∑_{u=r}^{s} λ_{u} + s − r

= B_{λ}(r, s) ≡ 0.

So q′_{r,s−1} = q_{r,s−1}(T_{r,s−1}(λ(s − 1))), see Definition 6.5. Let

T_{r,s−1}(λ(s − 1)) = {u_{1}, u_{2}, …, u_{m}}.

Note that

B_{λ}(r, s − 1) = B_{λ}(r, s) − (λ_{s} + 1) ≡ −1 ≢ 0,
C_{λ}(r, s − 1) = B_{λ}(r, s − 1) − λ_{s−1}.

So C_{λ}(r, s − 1) ≡ 0 implies λ_{s−1} ≢ 0. Therefore either T_{r,s}(λ) = T_{r,s−1}(λ(s − 1)) or

T_{r,s}(λ) = {u_{1}, u_{2}, …, u_{m}, +1}. By Lemma 6.6 we have q(T_{r,s}(λ)) = q(T_{r,s−1}(λ(s −

1))). This proves q_{r,s} = q′_{r,s−1}.

Now, let us consider the general case (i.e. λ_{s} > 0 is arbitrary). Note that

B_{λ}(r, j) + B_{λ(j+1)}(j + 1, i) = B_{λ}(r, i),
B_{λ}(r, j) + C_{λ(j+1)}(j + 1, i) = C_{λ}(r, i)

for any i, j such that r ≤ j < i ≤ s. So we get

{i ∈ [j + 1, s − 1] | B_{λ}(r, i) ≡ 0}
= {i ∈ [j + 1, s − 1] | B_{λ(j+1)}(j + 1, i) ≡ 0}
for any j ∈ [r, s) with B_{λ}(r, j) ≡ 0.

(60)

{i ∈ [j + 1, s − 1] | C_{λ}(r, i) ≡ 0}
= {i ∈ [j + 1, s − 1] | C_{λ(j+1)}(j + 1, i) ≡ 0}
for any j ∈ [r, s) with B_{λ}(r, j) ≡ 0.

(61)

We put

{i_{1} < i_{2} < ⋯ < i_{m}} = {i ∈ (r, s) | λ_{i} > 0, and B_{λ}(r, i) ≡ 0 or C_{λ}(r, i) ≡ 0},

and

T = T_{r,s}(λ) = {t_{1}, t_{2}, …, t_{m}}.

Then by Lemma 6.7 we have

(62) q_{r,s} = q(T) = x + ∑ {q(T_{j}^{−}) | j ∈ T_{≤0}, T_{j}^{+} is quasi-latticed}

where x = 1 if T is quasi-latticed, and x = 0 otherwise.

We claim that

x = σ(r, s − 1) + q_{r,r}σ̄(r + 1, s − 1). (63)

Indeed, assume first λ_{r} ≢ 0. Then q_{r,r} = 0. Moreover, T is quasi-latticed if and only if r is normal in [r, s − 1] in view of Lemma 6.8. So x = σ(r, s − 1) (cf. Definition 1.16).

Now assume λ_{r} ≡ 0. Then σ(r, s − 1) = 0, q_{r,r} = 1 (since λ_{r} > 0). We have to consider two subcases: s = r + 1 and s > r + 1.

If s = r + 1 then σ̄(r + 1, s − 1) = 1 by Definition 1.16, so the right hand side of (63) is equal to 1. However, we also have x = 1 since the empty sequence is quasi-latticed by Definition 6.2.

Now consider the second subcase: s > r + 1. We again need to distinguish between two possibilities: λ_{r+1} + 1 ≡ 0 and λ_{r+1} + 1 ≢ 0.

If λ_{r+1} + 1 ≡ 0 then λ_{r+1} ≢ 0 and B_{λ}(r, r + 1) = λ_{r} + λ_{r+1} + 1 ≡ 0 since we have assumed λ_{r} ≡ 0. So i_{1} = r + 1, t_{1} = −1. Therefore T is not quasi-latticed, i.e. x = 0. On the other hand λ_{r+1} + 1 ≡ 0 implies that r + 1 is not normal in [r + 1, s − 1] for λ(r + 1), i.e. σ̄(r + 1, s − 1) = 0.

Finally, let λ_{r+1} + 1 ≢ 0. Since B_{λ}(r, r) = λ_{r} ≡ 0, equalities (60) and (61) imply

{i ∈ (r + 1, s) | B_{λ(r+1)}(r + 1, i) ≡ 0} = {i ∈ (r + 1, s) | B_{λ}(r, i) ≡ 0} ,
{i ∈ (r + 1, s) | C_{λ(r+1)}(r + 1, i) ≡ 0} = {i ∈ (r + 1, s) | C_{λ}(r, i) ≡ 0} .

Moreover,

B_{λ}(r, r + 1) = λ_{r} + λ_{r+1} + 1 ≢ 0 and C_{λ}(r, r + 1) = λ_{r} + 1 ≡ 1 ≢ 0.

So T_{r,s}(λ) = T_{r+1,s}(λ(r + 1)). But Lemma 6.8 implies that T_{r+1,s}(λ(r + 1)) is quasilatticed if and only if r + 1 is normal in [r + 1, s − 1] for λ(r + 1), i.e. if and only if σ̄(r + 1, s − 1) = 1. On the other hand, x = 1 if and only if T_{r,s}(λ) is quasi-latticed. Since T_{r,s}(λ) = T_{r+1,s}(λ(r + 1)) this proves the equality x = σ̄(r + 1, s − 1).

Thus (63) is completely proved.

We next claim that

(64) ∑{q(T_{j}^{−}) | j ∈ T_{≤0}, T_{j}^{+} is quasi-latticed} = ∑_{j∈T_{≤0}} q(T_{j}^{−})σ̄(i_{j} + 1, s − 1).

Let j ∈ T_{≤0}. If i_{j} = s − 1 then j = m, T_{j}^{+} = ∅ is quasi-latticed. Moreover, σ̄(i_{j} + 1, s − 1) = σ̄(s, s − 1) = 1 by definition. So q(T_{j}^{−}) occurs in both sides of (64).

Assume i_{j} < s − 1. Since j ∈ T_{≤0} we have B(r, i_{j}) ≡ 0. It follows from (60), (61) that

\begin{matrix}\{i ∈ (i_{j} + 1, s − 1] | B_{λ(i_{j}+1)}(i_{j} + 1, i) ≡ 0\} \\ = \{i ∈ (i_{j} + 1, s − 1] | B_{λ}(r, i) ≡ 0\} , \end{matrix} (65)

\begin{matrix}\{i ∈ (i_{j} + 1, s − 1] | C_{λ(i_{j}+1)}(i_{j} + 1, i) ≡ 0\} \\ = \{i ∈ (i_{j} + 1, s − 1] | C_{λ}(r, i) ≡ 0\} , \end{matrix} (66)

Note that B_{λ}(r, i_{j}) ≡ 0 also implies

C_{λ}(r, i_{j} + 1) = B_{λ}(r, i_{j}) + 1 ≡ 1 ≢ 0, (67)

B_{λ}(r, i_{j} + 1) = B_{λ}(r, i_{j}) + (λ_{i_{j}+1} + 1) ≡ λ_{i_{j}+1} + 1. (68)

If λ_{i_{j}+1} + 1 ≡ 0 then λ_{i_{j}+1} ≢ 0, and B_{λ}(r, i_{j} + 1) ≡ 0 by (68). Since i_{j} + 1 < s, this implies j < m, i_{j+1} = i_{j} + 1 and t_{j+1} = −1. So T_{j}^{+} is not quasi-latticed, i.e. q(T_{j}^{−}) does not occur in the left hand side of (64). On the other hand, λ_{i_{j}+1} + 1 ≡ 0 implies σ̄(i_{j} + 1, s − 1) = 0, so q(T_{j}^{−}) also does not occur in the right hand side of (64).

Let λ_{i_{j}} + 1 ≢ 0. Then (68) implies B_{λ}(r, i_{j} + 1) ≢ 0, which together with (67) and (65),(66) implies

T_{j}^{+} = T_{i_{j}+1,s}(λ(i_{j} + 1)). (69)

By Lemma 6.8, T_{i_{j}+1,s}(λ(i_{j} + 1)) is quasi-latticed if and only if i_{j} + 1 is normal in [i_{j} + 1, s − 1] for λ(i_{j} + 1), i.e. if and only if σ̄(i_{j} + 1, s − 1) = 1. So it follows from (69) that q(T_{j}^{−}) occurs in the left hand side of (64) if and only if it occurs in its right hand side. Thus (64) is completely proved.

Further, note that T_{j}^{−} = T_{r,i_{j}}(λ) for any j ∈ [1, m]. So for j ∈ T_{≤0} we have q(T_{j}^{−}) = q_{r,i_{j}}. Thus it follows from (62), (63) and (64) that

q_{r,s} = σ(r, s − 1) + q_{r,r}σ̄(r + 1, s − 1) + ∑_{j∈T_{≤0}} q_{r,i_{j}} σ̄(i_{j} + 1, s − 1). (70)

Assume i ∈ (r, s). Then q_{r,i} = 0 unless B(r, i) ≡ 0, λ_{i} > 0, i.e. q_{r,i} = 0 unless i = i_{j} for some j ∈ T_{≤0}. So we may rewrite (70) as

q_{r,s} = σ(r, s − 1) + q_{r,r}σ̄(r + 1, s − 1) + ∑_{i=r+1}^{s−1} q_{r,i}σ̄(i + 1, s − 1).

Since σ̄(s, s − 1) = 1 this is equivalent to

q_{r,s} = σ(r, s − 1) + q_{r,s−1} + ∑_{i=r}^{s−2} q_{r,i}σ̄(i + 1, s − 1),

as desired.

Part II. Main Results

Throughout Part II: l is a fixed positive integer; r and s are always assumed to be integers with 1 ≤ r ≤ s ≤ l; K is an algebraically closed field of characteristic p > 0; {α_{1}, α_{2}, …, α_{l}} is a base of the root system A_{l}; {ω_{1}, ω_{2}, …, ω_{l}} are the corresponding fundamental weights; P (A_{l}) = ℤω_{1} + ℤω_{2} + ⋯ + ℤω_{l} is the weight lattice; P_{+}(A_{l}) = ℤ_{+}ω_{1} + ℤ_{+}ω_{2} + ⋯ + ℤ_{+}ω_{l} is the set of dominant weights; α(r, s) = α_{r} + α_{r+1} + ⋯ + α_{s} ∈ A_{l}, 1 ≤ r ≤ s ≤ l. (Recall that any root in A_{l}

has a form ±α(r, s)); λ = (λ_{1}, λ_{2}, …, λ_{l}) = λ_{1}ω_{1} + λ_{2}ω_{2} + ⋯ + λ_{l}ω_{l} ∈ P_{+}(A_{l}).

7. Preliminaries from representation theory

We consider the standard Chevalley basis

{E_{i,j} (1 ≤ i ≠ j ≤ l + 1), E_{i,i} − E_{i+1,i+1} (1 ≤ i ≤ l)}

of the Lie algebra 𝔰l_{l+1}(ℂ) (see Remarks (a), (c) after Theorem 1 in [24]). We define a ℤ-algebra U_{ℤ} (resp., U_{ℤ}^{+}, U_{ℤ}^{−}) as the ℤ-subalgebra of the universal enveloping U(𝔰l_{l+1}(ℂ)) generated by all (E_{i,j})^{m}/m!, 1 ≤ i ≠ j ≤ l + 1 (resp., 1 ≤ i < j ≤ l + 1, 1 ≤ j < i ≤ l + 1). Put U_{K} = U_{ℤ} ⊗ K.

We define

X_{r,s}^{(m)} = ((E_{r,s+1})^{m}/m!) ⊗ 1 ∈ U_{K}, X_{r,s} = X_{r,s}^{(1)};
Y_{r,s}^{(m)} = ((E_{s+1,r})^{m}/m!) ⊗ 1 ∈ U_{K}, Y_{r,s} = Y_{r,s}^{(1)};
H_{r,s} = (E_{r,r} − E_{s+1,s+1}) ⊗ 1 ∈ U_{K}.

(Recall that we always assume 1 ≤ r ≤ s ≤ l).

For a weight μ ∈ P (A_{l}) we define U_{μ}^{+} and U_{−μ}^{−} to be generated (as vecor spaces) by the products

{X_{i_{1},j_{1}}^{(m_{1})}X_{i_{2},j_{2}}^{(m_{2})} … X_{i_{N} ,j_{N}}^{(m_{N})} |∑_{t=1}^{N} m_{t}α(i_{t}, j_{t}) = μ}

and

{Y_{i_{1},j_{1}}^{(m_{1})}Y_{i_{2},j_{2}}^{(m_{2})} … Y_{i_{N} ,j_{N}}^{(m_{N})} |∑_{t=1}^{N} m_{t}α(i_{t}, j_{t}) = μ} ,

respectively.

Let A_{l}(K) be the universal Chevalley group defined using the fixed Chevalley basis and considered as an algebraic group [24, Sections 3,5]. All modules over A_{l}(K) are assumed to be rational and finite-dimensional K-vector spaces. Then we may not to distinguish between A_{l}(K)- and U_{K}-modules, cf. [11].

If M is an A_{l}(K)-module and μ ∈ P (A_{l}) we denote by M_{μ} the μ-weight space of M.

Let V_{ℂ}(λ) be the complex irreducible 𝔰l_{l+1}(ℂ)-module with highest weight λ (recall that throughout Part II we assume λ ∈ P_{+}(A_{l})). We denote by e_{ℂ} a highest weight vector of V_{ℂ}(λ). Set

V_{ℤ}(λ) = U_{ℤ}e_{ℂ}, V (λ) = V_{ℤ}(λ) ⊗ K,
e_{+} = e_{ℂ} ⊗ 1 ∈ V (λ).

Then V (λ) is a U_{K}-module called Weyl module with highest weight λ. This module has a unique maximal proper submodule Θ(λ), and

L(λ) = V (λ)/Θ(λ)

is the irreducible module with highest weight λ. We denote by

v_{+} = e_{+} + Θ(λ) ∈ V (λ)/Θ(λ) = L(λ)

a highest weight vector of L(λ).

The next result is well known (It follows easily from [24, Theorem 2] and the fact that L(λ) = U_{K}L(λ).)

Lemma 7.1. L(λ)_{λ−μ} = U_{−μ}^{−}v_{+}.

We need to recall the notion of the first level introduced by Seitz.

Definition 7.2. The first level L(λ)_{1} of an irreducible module L(λ) is defined as

L(λ)_{1} = ⨁ {L(λ)_{μ}|μ = λ − α_{l} − ∑_{i=1}^{l−1} m_{i}α_{i} for some m_{i} ∈ ℤ}.

Let A_{l−1}(K) be a subgroup of A_{l}(K) generated by the root subgroups which correspond to all roots of the form ±α(i, j), 1 ≤ i ≤ j < l. Then L(λ)_{1} is a direct summand of the restriction L(λ) ↓_{A_{l−1}(K)}. In particular, we can consider L(λ)_{1} as an A_{l−1}(K)-module (see [12, 13] for more details). This module will be denoted by L(λ)_{1} | A_{l−1}(K).

If

μ = (μ_{1}, μ_{2}, …, μ_{l}) ∈ P (A_{l})

we denote

μ̄ = (μ_{1}, μ_{2}, …, μ_{l−1}) ∈ P (A_{l−1}).

Being considered as a character of the standard Cartan subgroups of A_{l−1}(K) ⊂ A_{l}(K), μ̄ is just a restriction of μ (see [13] for more details).

Lemma 7.3. Let μ, ν ∈ P (A_{l}), μ = λ − α_{l} − ∑_{i=1}^{l−1} n_{i}α_{i}, ν = λ − α_{l} − ∑_{i=1}^{l−1} m_{i}α_{i}. If μ̄ = ν̄ then μ = ν.

Proof. Let μ = (μ_{1}, μ_{2}, …, μ_{l}), ν = (ν_{1}, ν_{2}, …, ν_{l}). Then by [2, Table I] we have

μ_{1} = λ_{1} − 2n_{1} + n_{2};
μ_{i} = λ_{i} − 2n_{i} + n_{i−1} + n_{i+1}, i = 2, 3, …, l − 2;
μ_{l−1} = λ_{l−1} − 2n_{l−1} + n_{l−2} + 1;
μ_{l} = λ_{l} − 2 + n_{l−1};

and

ν_{1} = λ_{1} − 2m_{1} + m_{2};
ν_{i} = λ_{i} − 2m_{i} + n_{i−1} + n_{i+1}, i = 2, 3, …, l − 2;
ν_{l−1} = λ_{l−1} − 2m_{l−1} + m_{l−2} + 1;
ν_{l} = λ_{l} − 2 + m_{l−1}.

By assumption, μ_{i} = ν_{i} for i = 1, 2, …, l − 1. So

− 2n_{1} + n_{2} = −2m_{1} + m_{2};
− 2n_{i} + n_{i−1} + n_{i+1} = −2m_{i} + m_{i−1} + m_{i+1}, i = 2, 3, …, l − 2;
− 2n_{l−1} + n_{l−2} = −2m_{l−1} + m_{l−2}.

Therefore m_{i} = n_{i} for i = 1, 2, …, l − 1.

Lemma 7.4. Let μ = λ − ∑_{i=1}^{l} n_{i}α_{i}. Assume that n_{l} = 1 and n_{i} = 0 or 1 for i = 1, 2, …, l − 1. If L(μ̄) occurs as a composition factor of L(λ)_{1} | A_{l−1}(K) then μ = λ − α(t, l) for some t ∈ [1, l].

Proof. Denote L(λ)_{1} | A_{l−1}(K) by M, and let

0 = M^{(0)} ⊂ M^{(1)} ⊂ ⋯ ⊂ M^{(N)} = M

be a composition series. Assume M^{(j)}/M^{(j−1)} ≅ L(μ̄). We choose v ∈ M^{(j)} such that v + M^{(j−1)} ∈ M^{(j)}/M^{(j−1)} is a highest weight vector of M^{(j)}/M^{(j−1)} ≅ L(μ̄).

Without loss of generality we may assume that v ∈ L(λ)_{μ}. Indeed we may clearly assume that v ∈ Mμ̄. So

v = v_{ν} + v_{κ} + …

where v_{ν} ∈ L(λ)_{ν}, v_{κ} ∈ L(λ)_{κ}, …, μ̄ = ν̄ = κ̄ = …, and ν, κ, … are weights of the first level. In view of Lemma 7.3, we have μ = ν = κ = . . ..

Now, let t = min{i | 1 ≤ i ≤ l, n_{i} ≠ 0}. Then t is well defined since n_{l} = 1. We have to prove that n_{i} = 1 for i = t, t + 1, …, l. If not, let u ≥ t be the maximal such that n_{i} = 1 for all i ∈ [t, u]. Then u + 1 < l and n_{u+1} = 0.

Set η = ∑_{i=1}^{l} n_{i}α_{i} and δ = ∑_{i=u+2}^{l} n_{i}α_{i}. Then η = α(t, u) + δ.

Since v ∈ L(λ)_{μ}, Lemma 7.1 implies that there exists y ∈ U_{−η}^{−} with v = yv_{+}. Note that y = y_{1}y_{2} where y_{1} ∈ U_{−α(t,u)}^{−}, y_{2} ∈ U_{−δ}^{−}, and y_{1}y_{2} = y_{2}y_{1}.

Since v ≠ 0 there exists x ∈ U_{η}^{+} with xv = v_{+}. Again, x = x_{1}x_{2} where x_{1} ∈ U_{α(t,u)}^{+}, x_{2} ∈ U_{δ}^{+}, and x_{1}x_{2} = x_{2}x_{1}.

Clearly x_{1}y_{2} = y_{2}x_{1}.

The equation xv = v_{+} yields x_{1}x_{2}y_{1}y_{2}v_{+} = v_{+} which is equivalent to the equation x_{2}y_{2}x_{1}y_{1}v_{+} = v_{+}. So x_{1}y_{1}v_{+} ≠ 0, i.e. x_{1}y_{1}v_{+} = cv_{+} for some c ≠ 0. Since v+M^{(j−1)} is a primitive vector in M^{(j)}/M^{(j−1)} we have x_{1}v ∈ M^{(j−1)}. Since M^{(j−1)} is an A_{l−1}(K)-submodule of L(λ)_{1} | A_{l−1}(K) we have y_{1}x_{1}v ∈ M^{(j−1)}.

On the other hand,

y_{1}x_{1}v = y_{1}x_{1}y_{1}y_{2}v_{+} = y_{1}y_{2}x_{1}y_{1}v_{+} = y_{1}y_{2}cv_{+} = cv,

with c ≠ 0. This gives a contradiction.

Definition 7.5. Let J = {j_{1} < j_{2} < ⋯ < j_{f}} ⊆ (r, s]. We define an element Y_{r,s}(J) ∈ U_{−α(r,s)}^{−} by putting

Y_{r,s}(J) = Y_{r,j_{1}−1}Y_{j_{1},j_{2}−1} … Y_{j_{f} ,s}.

(Y_{r,s}(∅) is interpreted as Y_{r,s}).

Lemma 7.6. {Y_{r,s}(J) | J ⊆ (r, s]} is a basis of U_{−α(r,s)}^{−}.

Proof. This follows from [24, Theorem 2].

Recall the integers B(r, s), C(r, s) defined in 1.11. In [14, 2.3] we have also defined integers ζ_{r,s}(M, U) for any two subsets M, U ⊆ (r, s].

In what follows we use the (same) notation B(r, s), C(r, s), ζ_{r,s}(M, U), etc. for the elements B(r, s) ⊗ 1, C(r, s) ⊗ 1, ζ_{r,s}(M, U) ⊗ 1, etc., of ℤ ⊗ K ≅ K.

For any M ⊆ (r, s] put

T_{r,s}(M) = ∑_{U⊆(r,s]} ζ_{r,s}(M, U)Y_{r,s}(U) ∈ U_{−α(r,s)}^{−}.

The elements T_{r,s}(M) (more precisely their ℤ-forms) were introduced in [14, 2.5,2.6] as some iterations of Carter’s lowering operators. We formulate some important properties of T_{r,s}(M) for future reference. All of them follow immediately from the similar properties of the corresponding ℤ-forms which were proved in [14].

Lemma 7.7. [14, 2.17] (i) Let J ⊆ (r, s]. Set J̄ = (r, s] \ J. Then

T_{r,s}(J) = Y_{r,s}(J̄) + ∑_{I⊆(r,s],I<J̄}const_{I} Y_{r,s}(I)

(recall the order ‘<’ defined in 2.5). (ii) {T_{r,s}(J) | J ⊆ (r, s]} is a basis of U_{−α(r,s)}^{−}.

Lemma 7.8. [14, 2.14] Let r < i ≤ s, E ⊆ (r, i − 1], F ⊆ (i, s], e = max E if E ≠ ∅. Then

T_{r,i−1}(E)T_{i,s}(F) = T_{r,s}(E ∪ F) − T_{r,s}((E \ {e}) ∪ {i} ∪ F ) − C(e, i)T_{r,s}(E ∪ {i} ∪ F),

if E ≠ ∅, and

T_{r,i−1}(∅)T_{i,s}(F) = T_{r,s}(F) − C(r, i)T_{r,s}({i} ∪ F).

Recall that λ ∈ P_{+}(A_{l}) is a (fixed) dominant weight, and v_{+} is a highest weight vector vector of L(λ).

Lemma 7.9. [14, 3.2] We have T_{r,s}(J)v_{+} = 0 if and only if there exists

u ∈ (r, s + 1] \ J

and a weakly increasing bijection

d : {r} ∪ (J ∩ (r, u)) → [r, u)

such that B(k, d(k)) ≡ 0 for all k ∈ {r} ∪ (J ∩ (r, u)).

For any J ⊆ (r, s] there is a constant ξ_{r,s}(J) ∈ K such that

X_{r,r}X_{r+1,r+1} … X_{s,s}T_{r,s}(J)e_{+} = ξ_{r,s}(J)e_{+}

(recall that e_{+} is a highest weight vector of V (λ)). We refer the reader to [14, 2.10,2.9] for details (there is a misprint in [14, Definition 2.9] though: we must put ξ_{r,s}(∅) = ∏_{t=r}^{s} B(r, t)).

Lemma 7.10. [14, 2.11] Let J ⊆ (r, s] be a regular subset (see Definition 5.1), i.e. there exist d(j) for j ∈ J, all distinct, with j ≤ d(j), B(j, d(j)) ≡ 0. Put D = {d(j) | j ∈ J}. Then

ξ_{r,s}(J) = ∏_{t∈[r,s]\D} B(r, t).

In [14, 2.18], we also introduced certain elements Q_{r,s}(J) ∈ U_{α(r,s)}^{+}, J ⊆ (r, s]. We define constants h_{r,s}(I, J) ∈ K by

Q_{r,s}(I)T_{r,s}(J)e_{+} = h_{r,s}(I, J)e_{+}; I, J ⊆ (r, s].

(see Definition 2.22 in [14])

Recall the partial order ‘≪’ from Definition 2.7(i).

Lemma 7.11. [14, 2.25] Suppose that h_{r,s}(I, J) ≠ 0. Then I ≪ J.

Lemma 7.12. [14, 2.28] Let I ≪ J be as in Definition 2.7. Then

h_{r,s}(I, J) = ±ξ_{r,b_{1}−2}(Δ_{0}(I, J))ξ_{c_{H},s}(Δ_{H}(I, J)) ∏_{t=1}^{H−1} ξ_{c_{t},b_{t+1}−2}(Δ_{t}(I, J)).

Lemma 7.13. [14, 2.29] Let I ≪ J be as in Definition 2.7 and assume that I is linked with J (see 2.7(iii)). Then

h_{r,s}(I, J) =[ ∏_{d_{0}∈[r,b_{1}−2]\Ω_{0}(I,J)} B(r, d_{0})]

× [ ∏_{t=1}^{H−1} ∏_{d_{t}∈[c_{t},b_{t+1}−2]\Ω_{t}(I,J)} B(c_{t}, d_{t})][ ∏_{d_{H}∈[c_{H},s]\Ω_{H}(I,J)} B(c_{H}, d_{H})].

Definition 7.14. [14, 4.4] Assume that r < s and there exists i ∈ [r, s] such that λ_{i} ≢ 0. Then we say that Y_{r,s}v_{+} can be expressed through non-trivial subdivisions if and only if there exists (in L(λ)) an expression of the form.

Y_{r,s}v_{+} = ∑_{J⊆(r,s],J≠∅} c_{J}Y_{r,s}(J)v_{+}, c_{J} ∈ K.

Recall the function σ(r, s) defined in 1.16.

Lemma 7.15. [14, 4.6,4.2,4.3] Assume that r < s and there exists i ∈ [r, s] such that λ_{i} ≢ 0. Then Y_{r,s}v_{+} can be expressed through non-trivial subdivisions if and only if σ(r, s) = 0.

8. Dimension and bases of the weight space L(λ)_{λ−α}

The purpose of this section is to describe the weight space L(λ)_{λ−α} for any positive root α = α_{r} + α_{r+1} + ⋯ + α_{s}. We find three distinct bases in this space and obtain a combinatorial description of its dimension. We also deduce a recurrence formula for dim L(λ)_{λ−α} and investigate the question when dim L(λ)_{λ−α} takes its minimal value.

Lemma 8.1. A subset J ⊆ (r, s] is non-essential if and only if there exists i ∈ [r, s] \ J such that T_{i,s}(J ∩ (i, s])v_{+} = 0.

Proof. Assume that we found i ∈ [r, s] \ J such that T_{i,s}(J ∩ (i, s])v_{+} = 0. By Lemma 7.9, there exist u ∈ (i, s + 1] \ (J ∩ (i, s]) and integers d, d(j) for j ∈ (J ∩ (i, s]) ∩ (i, u) = J ∩ (i, u), all distinct, such that

i ≤ d < u, B(i, d) ≡ 0

and

j ≤ d(j) < u, B(j, d(j)) ≡ 0 for j ∈ J ∩ (i, u).

Now we may take

t = i, d(t) = d, u = u, d(j) = d(j)

in Definition 1.13. Thus J is not essential. The argument is easily reversed.

Set

(71) {T_{r,s}(J)v_{+} | J is essential in (r, s]} .

We want to prove that (71) is a basis of the weight space L(λ)_{λ−α(r,s)}. Corollary 8.3 is the first step in achieving this.

Lemma 8.2. Assume L(λ)_{λ−α(r,s)} ≠ 0 and let M ⊆ (r, s] be non-essential. Then T_{r,s}(M)v_{+} can be expressed as a linear combination of T_{r,s}(J)v_{+} with J > M and J essential.

Proof. Note that (r, s] is essential in (r, s]. Indeed, otherwise it follows from Definition 1.13 that λ_{r} ≡ λ_{r+1} ≡ ⋯ ≡ λ_{s} ≡ 0, whence L(λ)_{λ−α(r,s)} = 0. Thus there is at least one essential subset in (r, s].

Assume the statement of the lemma is false. Let M be the maximal (with respect to ”<”, cf. 2.5) subset such that M is non-essential and T_{r,s}(M)v_{+} can not be represented as a linear combination of some T_{r,s}(J)v_{+} with J ∈ E(r, s), J > M. Then T_{r,s}(M)v_{+} ≠ 0. So, by Lemma 8.1, there exists i ∈ (r, s] \ M with

T_{i,s}(M ∩ (i, s])v_{+} = 0. (72)

By Lemma 7.8, we have

T_{r,i−1}(M ∩ (r, i))T_{i,s}(M ∩ (i, s])
= T_{r,s}(M) − T_{r,s}((M \ { max (M ∩ (r, i))}) ∪ {i})
− C( max (M ∩ (r, i)), i)T_{r,s}(M ∪ {i}),

where we omit the second summand in the right hand side and interpret the value max (M ∩ (r, i)) as r if M ∩ (r, i) = ∅. Applying both sides of this equation to v_{+} and using (72), we get

T_{r,s}(M)v_{+} = T_{r,s}((M \ { max (M ∩ (r, i))}) ∪ {i})v_{+}
+ C( max (M ∩ (r, i)), i)T_{r,s}(M ∪ {i})v_{+}.

It now remains to note that

(M \ { max (M ∩ (r, i))}) ∪ {i} > M

since i > max (M ∩ (r, i)), i ∉ M, and

M ∪ {i} > M

since i ∉ M.

Corollary 8.3. Let μ = λ − α(r, s). Then the set ( 71) generates L(λ)_{μ} as a vector space.

Proof. Since any T_{r,s}(J) ∈ U_{−α(r,s)}^{−} we get that all T_{r,s}(J)v_{+} ∈ L(λ)_{μ}. In view of Lemmas 7.1 and 7.7(ii), it suffices to prove that any vector T_{r,s}(M)v_{+} with M ⊆ (r, s] is a linear combination of vectors from the set (71).

If L(λ)_{μ} = 0 then any T_{r,s}(M)v_{+} = 0, hence all M ⊆ (r, s] are non-essential by Lemma 8.1. We interpret the vector space generated by the empty set of vectors as 0.

So we may assume L(λ)_{μ} ≠ 0. Now it suffices to apply Lemma 8.2.

Recall the set Ĵ defined for any J ⊆ (r, s] in 2.8, and constants h_{r,s}(I, J) defined in Section 7 before Lemma 7.11.

Lemma 8.4. If T_{r,s}(J)v_{+} ≠ 0 then h_{r,s}(Ĵ, J) ≠ 0.

Proof. Let

J = [β_{1}, γ_{1}] ∪ [β_{2}, γ_{2}] ∪ ⋯ ∪ [β_{N}, γ_{N}],
Ĵ = [b_{1}, c_{1}] ∪ [b_{2}, c_{2}] ∪ ⋯ ∪ [b_{H}, c_{H}]

be decompositions into the connected components, cf. Definition 1.7. Then, by Definitions 2.8, 2.7, for all v = 1, 2, …, H there exist u_{v} ∈ [1, N] such that b_{v} = β_{u_{v}}, c_{v} ≤ γ_{u_{v}}.

By Lemma 7.13,

h_{r,s}(Ĵ, J) =[ ∏_{d_{0}∈[r,b_{1}−2]\Ω_{0}(Ĵ,J)} B(r, d_{0})]

× [ ∏_{t=1}^{H−1} ∏_{d_{t}∈[c_{t},b_{t+1}−2]\Ω_{t}(Ĵ,J)} B(c_{t}, d_{t})][ ∏_{d_{H}∈[c_{H},s]\Ω_{H}(Ĵ,J)} B(c_{H}, d_{H})].

If h_{r,s}(Ĵ, J) = 0 then some of the factors in this product is zero. If B(r, d_{0}) ≡ 0 for some d_{0} ∈ [r, b_{1} − 2] \ Ω_{0}(Ĵ, J) then T_{r,s}(J)v_{+} = 0 by Lemma 7.9 (we can take u = b_{1} − 1, d = d_{0} in that lemma). Let some B(c_{t}, d_{t}) = 0 for t ∈ [1, H], d_{t} ∈ [c_{t}, b_{t+1} − 2] \ Ω_{t}(Ĵ, J) (we interpret b_{H+1} as s + 2). Then Ĵ\ {c_{t}} is linked with J, which contradicts the definition of Ĵ, cf. 2.8.

Lemma 8.5. Let T_{r,s}(J)v_{+} ≠ 0. Then Ĵ is maximal among the subsets I ⊆ (r, s] such that h_{r,s}(I, J) ≠ 0.

50 ALEXANDER KLESHCHEV

Proof. In view of Lemma 8.4 we have only to prove that h_{r,s}(I, J) = 0 for any I > Ĵ. Assume on the contrary that I > Ĵ and h_{r,s}(I, J) ≠ 0. By Lemma 7.11 we have I ≪ J. (73)

Let

I = [x_{1}, y_{1}] ∪ [x_{2}, y_{2}] ∪ ⋯ ∪ [x_{G}, y_{G}],
Ĵ = [b_{1}, c_{1}] ∪ [b_{2}, c_{2}] ∪ ⋯ ∪ [b_{H}, c_{H}],
J = [β_{1}, γ_{1}] ∪ [β_{2}, γ_{2}] ∪ ⋯ ∪ [β_{N}, γ_{N}]

be decompositions into connected components. Since Ĵ ≪ J, Definition 2.7(i) yields b_{v} = β_{u_{v}} for some u_{v} ∈ [1, N], v = 1, 2, …, H. (74)

By Lemma 7.12,

h_{r,s}(I, J) = ± ∏_{v=0}^{G} ξ_{y_{v},x_{v+1}−2}(Δ_{t}(I, J)), (75)

where y_{0} and x_{G+1} are interpreted as r and s+2, respectively. Let i be the maximal integer with i ∈ I, i ∉ Ĵ. Such i is well defined since I > Ĵ implies I ⊈ Ĵ. There exists t ∈ [1, G] with i ∈ [x_{t}, y_{t}]. We claim that i = y_{t}. (76) Indeed, otherwise ∅ ≠ (i, y_{t}] ⊆ Ĵ, i ∉ Ĵ imply i + 1 = b_{v} for some v ∈ [1, H], i.e. i + 1 = β_{u_{v}} for some u_{v} ∈ [1, N] by (74). Hence i ∉ J. In particular, I ⊈ J which contradicts (73).

We shall prove that ξ_{y_{t},x_{t+1}−2}(Δ_{t}(I, J)) = 0. (77) Then (75) will imply h_{r,s}(I, J) = 0 giving a contradiction which proves our lemma.

To prove (77), note that the choice of i yields I ∩ (i, s] ⊆ Ĵ. Since Ĵ < I this implies I ∩ (i, s] = Ĵ∩ (i, s]. Since i = y_{t} by (76), we have I ∩ (i, s] = ∪_{v=t+1}^{G}[x_{v}, y_{v}]. Now i ∉ Ĵ implies Ĵ ∩ [y_{t}, s] = ∪_{v=t+1}^{G}[x_{v}, y_{v}]. (78)

Therefore [x_{G−v}, y_{G−v}] = [b_{H−v}, c_{H−v}], v = 0, 1, …, G − (t + 1). (79)

Put w = H − G + (t + 1). Then x_{t+1} = b_{w}. (80)

Indeed, if t < G this follows by putting v = G − (t + 1) in (79). If t = G (i.e. Ĵ ∩ [y_{t}, s] = ∅) then we interpret x_{G+1} = s + 2 = b_{H+1}.

Note that y_{t} ≤ x_{t+1} − 2 = b_{w} − 2, cf. (80). On the other hand, y_{t} > c_{w−1} since, in view of (78)-(80), we have

[y_{t}, s] ∩ Ĵ = ∪_{v=t+1}^{G}[x_{v}, y_{v}] = ∪_{v=w}^{H}[b_{v}, c_{v}].

Thus,

y_{t} ∈ (c_{w−1}, b_{w} − 2]. (81)

Taking into account y_{t} ∈ J we conclude that

y_{t} ∈ Δ_{w−1}(Ĵ, J). (82)

We also have Δ_{t}(I, J) ⊆ (y_{t}, x_{t+1} − 2] ⊆ (c_{w−1}, b_{w} − 2] in view of (81) and (80). On the other hand, Δ_{t}(I, J) ⊆ J. Summarizing, Δ_{t}(I, J) ⊆ Δ_{w−1}(Ĵ, J). Together with (82) this means that

{y_{t}} ⊔ Δ_{t}(I, J) ⊆ Δ_{w−1}(Ĵ, J). (83)

Since Ĵ is linked with J then, by Definition 2.7, for all j ∈ Δ_{w−1}(Ĵ, J) there exist d(j) ∈ [j, b_{w} − 2] = [j, x_{t+1} − 2] (cf. (80)), all distinct, such that B(j, d(j)) ≡ 0. So (83) implies that for all j ∈ {y_{t}} ⊔ Δ_{t}(I, J) there exist d(j) ∈ [j, x_{t+1} − 2], all distinct, such that B(j, d(j)) ≡ 0. Put

D = {d(j) | j ∈ Δ_{t}(I, J)}.

Then by Lemma 7.10 we have

ξ_{y_{t},x_{t+1}−2}(Δ_{t}(I, J)) = ∏_{v∈[y_{t},x_{t+1}−2]\D} B(y_{t}, v).

However, the last product is zero since B(y_{t}, d(y_{t})) = 0, and d(y_{t}) ∈ [y_{t}, x_{t+1} −2]\D. This proves (77) and the lemma.

Theorem 8.6. Let μ = λ − α(r, s). Then

{T_{r,s}(J)v_{+} | J is essential in (r, s]}

is a basis of L(λ)_{μ}.

Proof. In view of Corollary 8.3, we have only to prove that vectors of the set (71) are linearly independent. Assume that there exists a non-trivial linear combination of the form

∑ {c_{J}T_{r,s}(J)v_{+} | J ∈ E(r, s)} = 0.

Since all Ĵ for J ∈ E(r, s) are distinct by virtue of Lemma 2.9, we may choose M ⊆ (r, s] such that c_{M} ≠ 0, and Ĵ > M̂, J ∈ E(r, s) imply c_{J} = 0. Then by Lemma 8.5, we have

Q_{r,s}(M̂)T_{r,s}(J)v_{+} = h_{r,s}(M̂, J)v_{+} = 0

for any J with J ≠ M, c_{J} ≠ 0. So

0 = Q_{r,s}(M̂) ∑ {c_{J}T_{r,s}(J)v_{+} | J ∈ E(r, s)} = c_{M}h_{r,s}(M̂, M)v_{+} ≠ 0,

where the last inequality follows from Lemma 8.4, because T_{r,s}(M)v_{+} ≠ 0 for any essential M by Lemma 8.1.

We have proved that (71) is a basis of L(λ)_{λ−α(r,s)}. However the operators T_{r,s}(J) are quite difficult to compute. Actually they are defined using an inductive procedure (cf. [14, 2.5,2.3]). Our next goal is to construct a “PBW-type” basis in L(λ)_{λ−α(r,s)}, i.e. a basis consisting of vectors of the form

Y_{r,j_{1}−1}Y_{j_{1},j_{2}−1} … Y_{j_{f} ,s}v_{+}.

Elements of this new basis will also be parametrized by the essential subsets. The matrix relating the two bases is uni-triangular (see Lemma 7.7(i)).

Definition 8.7. For J ⊆ (r, s] we define a subset J̄ = (r, s] \ J.

Theorem 8.8. Let μ = λ − α(r, s). Then

(84) {Y_{r,s}(J̄)v_{+} | J ⊆ (r, s] is essential}

is a basis of L(λ)_{μ}.

Proof. It follows from Theorem 8.6 that dim L(λ)_{μ} = ε(r, s), cf. 1.13. So it suffices to prove that the set (84) generates L(λ)_{μ}. Now, by Lemmas 7.1 and 7.6, it is enough to show that any Y_{r,s}(M)v_{+} belongs to the vector space V generated by (84).

Assume not. Let M be a maximal subset in (r, s] such that Y_{r,s}(M̄)v_{+} ∉ V. Then M is non-essential. By Lemma 8.2 we have

T_{r,s}(M)v_{+} = ∑{c_{J}T_{r,s}(J)v_{+} | J ∈ E(r, s), J > M}. (85)

Lemma 7.7(i) implies that

T_{r,s}(I)v_{+} = Y_{r,s}(Ī)v_{+} + ∑_{F <Ī}const_{F} Y_{r,s}(F)v_{+} (86)

for any I ⊆ (r, s].

By Lemma 2.6, J > M implies J̄ < M̄, so F < J̄ implies F < M̄. Therefore it follows from (85) and (86) that Y_{r,s}(M̄)v_{+} is a linear combination of some Y_{r,s}(F)v_{+} with F < M̄. It follows from the choice of M that any Y_{r,s}(F)v_{+} with F < M̄ belongs to V. Hence Y_{r,s}(M)v_{+} ∈ V giving a contradiction with the choice of M.

We now want to describe one more “PBW-type” basis of L(λ)_{λ−α(r,s)}. The elements of this basis will be parametrized by the σ-subsets in (r, s], cf. 4.1, 5.6(ii).

Theorem 8.9. Let μ = λ − α(r, s). Then the set of vectors

(87) {Y_{r,s}(J)v_{+} | J ⊆ (r, s] is a σ-subset}

is a basis of L(λ)_{μ}.

Proof. By Corollary 5.6(ii), the number of the σ-subsets in (r, s] is equal to the number of the essential subsets in (r, s]. So, in view of Theorem 8.6, we have only to prove that the set (87) generates L(λ)_{μ}. By Lemmas 7.1 and 7.6, it is enough to show that any Y_{r,s}(M)v_{+} with M ⊆ (r, s] belongs to the vector space V generated by (87).

Let

I = {i_{1} < i_{2} < ⋯ < i_{f}}

be the maximal subset of (r, s] such that

Y_{r,s}(I)v_{+} = Y_{r,i_{1}−1}Y_{i_{1},i_{2}−1} … Y_{i_{f−1},i_{f} −1}Y_{i_{f} ,s}v_{+} ∉ V.

Then Y_{r,s}(I)v_{+} ≠ 0, and I is not a σ-subset, i.e.

σ(I) = σ(r, i_{1} − 2)σ(i_{1}, i_{2} − 2) … σ(i_{f−1}, i_{f} − 2)σ(i_{f}, s) = 0.

Assume σ(i_{f}, s) = 0. There exists i ∈ [i_{f}, s] with λ_{i} ≢ 0, since otherwise Y_{i_{f} ,s}v_{+} = 0 and hence Y_{r,s}(I)v_{+} = 0 giving a contradiction. Now, by Lemma 7.15,

Y_{i_{f} ,s}v_{+} = ∑_{J⊆(i_{f} ,s],J≠∅} c_{J}Y_{i_{f} ,s}(J)v_{+}.

Hence

Y_{r,s}(I)v_{+} = ∑_{J⊆(i_{f} ,s],J≠∅} c_{J}Y_{r,s}(I ∪ J)v_{+}.

Note that J ⊆ (i_{f}, s], J ≠ ∅ imply I ∪ J > I. So any Y_{r,s}(I ∪ J)v_{+} ∈ V. Therefore Y_{r,s}(I)v_{+} ∈ V giving a contradiction.

Thus we may assume that there exists t ∈ [0, f − 1] with σ(i_{t}, i_{t+1} − 2) = 0 (here i_{0} is interpreted as r). In particular, i_{t} ≤ i_{t+1} − 2 (cf. Definition 1.16). Denote

I_{1} = {i_{1}, i_{2}, …, i_{t−1}},
I_{2} = {i_{t+2}, i_{t+3}, …, i_{f}},
i = i_{t},
j = i_{t+1} − 1.

Then σ(i, j − 1) = 0, and

Y_{r,s}(I) = Y_{r,i−1}(I_{1})Y_{i,j}Y_{j+1,s}(I_{2}).

Assume first that i = j − 1. Then σ(i, j − 1) = 0 implies λ_{i} ≡ 0, hence Y_{i,i}v_{+} = 0. So using elementary commutation relations in U_{K} (see [14, 1.2]) we get

Y_{i,j}Y_{j+1,s}(I_{2})v_{+} = Y_{i,i+1}Y_{i+2,s}(I_{2})v_{+}
= ( − Y_{i,i}Y_{i+1,i+1} + Y_{i+1,i+1}Y_{i,i})Y_{i+2,s}(I_{2})v_{+}
= −Y_{i,i}Y_{i+1,i+1}Y_{i+2,s}(I_{2})v_{+} + Y_{i+1,i+1}Y_{i+2,s}(I_{2})Y_{i,i}v_{+}
= −Y_{i,i}Y_{i+1,i+1}Y_{i+2,s}(I_{2})v_{+}.

Therefore

Y_{r,s}(I)v_{+} = −Y_{r,i−1}(I_{1})Y_{i,i}Y_{i+1,i+1}Y_{i+2,s}(I_{2})v_{+} =
= −Y_{r,s}(I ∪ {i + 1})v_{+}.

Note that i + 1 ∉ I, so I ∪ {i + 1} > I. Therefore Y_{r,s}(I ∪ {i + 1})v_{+} ∈ V by the choice of I, giving a contradiction.

Now assume that i ≤ j −2. To apply Lemma 7.15, we make use of a commutation trick from the proof of Proposition 4.1 in [12].

By elementary commutation relations in U_{K} (see [14, 1.2]) we may write

Y_{i,j}Y_{j+1,s}(I_{2})v_{+} = ( − Y_{i,j−1}Y_{j,j} + Y_{j,j}Y_{i,j−1})Y_{j+1,s}(I_{2})v_{+}
= −Y_{i,j−1}Y_{j,j}Y_{j+1,s}(I_{2})v_{+} + Y_{j,j}Y_{j+1,s}(I_{2})Y_{i,j−1}v_{+}.

If λ_{u} ≡ 0 for all u ∈ [i, j − 1] then we get Y_{i,j−1}v_{+} = 0 so

Y_{i,j}Y_{j+1,s}(I_{2})v_{+} = −Y_{i,j−1}Y_{j,j}Y_{j+1,s}(I_{2})v_{+}.

Hence

Y_{r,s}(I)v_{+} = −Y_{r,i−1}(I_{1})Y_{i,j−1}Y_{j,j}Y_{j+1,s}(I_{2})v_{+} =
= −Y_{r,s}(I ∪ {j})v_{+}.

Since j ∉ I we get I ∪ {j} > I, hence Y_{r,s}(I ∪ {j})v_{+} ∈ V giving a contradiction.

Now assume there is u ∈ [i, j − 1] with λ_{u} ≢ 0. Then, in view of Lemma 7.15, the equality σ(i, j − 1) = 0 implies

Y_{i,j−1}v_{+} = ∑_{F ⊆(i,j−1],F ≠∅} Y_{i,j−1}(F)v_{+}.

So

Y_{j,j}Y_{j+1,s}(I_{2})Y_{i,j−1}v_{+} = Y_{j,j}Y_{j+1,s}(I_{2}) ∑_{F ⊆(i,j−1],F ≠∅} Y_{i,j−1}(F)v_{+}

= ∑_{F ⊆(i,j−1],F ≠∅} Y_{j,j}Y_{i,j−1}(F)Y_{j+1,s}(I_{2})v_{+}

= ∑_{F ⊆(i,j−1],F ≠∅} (Y_{i,j}(F)Y_{j+1,s}(I_{2}) + Y_{i,j−1}(F)Y_{j,j}Y_{j+1,s}(I_{2}))v_{+}.

Therefore

Y_{i,j}Y_{j+1,s}(I_{2})v_{+} = − Y_{i,j−1}Y_{j,j}Y_{j+1,s}(I_{2})v_{+}

+ ∑_{F ⊆(i,j−1],F ≠∅} (Y_{i,j}(F)Y_{j+1,s}(I_{2}) + Y_{i,j−1}(F)Y_{j,j}Y_{j+1,s}(I_{2}))v_{+}.

Hence

Y_{r,s}(I)v_{+} = Y_{r,i−1}(I_{1})Y_{i,j}Y_{j+1,s}(I_{2})v_{+} =

= −Y_{r,s}(I ∪ {j})v_{+} + ∑_{F ⊆(i,j−1],F ≠∅} (Y_{r,s}(I ∪ F) − Y_{r,s}(I ∪ {j} ∪ F))v_{+}.

Note that j ∉ I implies I ∪ {j} > I, and F ⊆ (i, j − 1], F ≠ ∅ imply I ∪ F > I, I ∪ {j} ∪ F > I. So, by the choice of I, the right hand side of the last equation belongs to V, hence Y_{r,s}(I)v_{+} belongs to V, giving a contradiction.

As a consequence of Theorems 8.6 and 8.9 we get an enumerative description of the weight multiplicity dim L(λ)_{λ−α(r,s)} as a number of essential subsets or a number of σ-subsets. Using combinatorial results obtained in Part I we can deduce recurrence formulas for this weight multiplicity.

Recall the functions ν, ν′ defined in 3.1.

Corollary 8.10. (i) dim L(λ)_{λ−α(r,s)} = ♯{essential subsets in (r, s]}; (ii) dim L(λ)_{λ−α(r,s)} = ♯{σ-subsets in (r, s]}; (iii) dim L(λ)_{λ−α(r,s)} = ν(r, s) + ∑_{i=r+1}^{s} ν′(r, i − 1) dim L(λ)_{λ−α(i,s)}; (iv) dim L(λ)_{λ−α(r,s)} = σ(r, s) + ∑_{i=r+1}^{s} σ(r, i − 2) dim L(λ)_{λ−α(i,s)};

(v) dim L(λ)_{λ−α(r,s)} = ∑_{J⊆(r,s]} ν(J); (vi) dim L(λ)_{λ−α(r,s)} = ∑_{J⊆(r,s]} σ(J); (vii) Let

I = {i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0}.

If I = ∅ then dim L(λ)_{λ−α(r,s)} = 0. Otherwise

dim L(λ)_{λ−α(r,s)} = dim L(λ)_{λ−α(i_{1},i_{k})} = σ(i_{1}, i_{k}) + (i_{2} − i_{1}) dim L(λ)_{λ−α(i_{2},i_{k})}

+ ∑_{t=3}^{k} ((i_{t} − i_{t−1} − 1)σ(i_{1}, i_{t−1}) + σ(i_{1}, i_{t−2})) dim L(λ)_{λ−α(i_{t},i_{k})}.

Proof. (i) and (ii) follow from Theorems 8.6 and 8.9. Now (iii) follows from Corollary 5.6(iv), (iv) follows from Proposition 5.5, (v) follows from Corollary 5.6(iii), and (vi) follows from Corollary 5.6(i). Finally, part (vii) follows from Lemma 2.3(i) and Corollary 5.9.

We illustrate how the formula 8.10(vii) works (we could also use 8.10(iii) instead of it to prove Proposition 8.11 below). Recall the “generalized Fibonacci numbers” f(i_{1}, i_{2}, …, i_{k}) defined in 1.21.

Proposition 8.11. Assume that

{i_{1} < i_{2} < ⋯ < i_{k}} = {i ∈ [r, s] | λ_{i} ≢ 0} ≠ ∅.

Then

dim L(λ)_{λ−α(r,s)} ≥ f(i_{1}, i_{2}, …, i_{k}).

Moreover,

dim L(λ)_{λ−α(r,s)} = f(i_{1}, i_{2}, …, i_{k})

if and only if

B(i_{j}, i_{j+1}) ≡ 0 for all j = 1, 2, …, k − 1. (88)

Proof. Put d(r, s) = dim L(λ)_{λ−α(r,s)}. We prove the proposition by induction on k. First note that d(r, s) = d(i_{1}, i_{k}) in view of 8.10(vii).

Let k = 1. Then we have d(r, s) = d(i_{1}, i_{1}) = 1 = f(i_{1}), as required. Let k = 2. Then, by Corollary 8.10(vii), we have

d(r, s) = σ(i_{1}, i_{2}) + (i_{2} − i_{1})d(i_{2}, i_{2}) = σ(i_{1}, i_{2}) + (i_{2} − i_{1}).

In view of Lemma 3.3, we have

σ(i_{1}, i_{2}) = \begin{cases}1, if B(i_{1}, i_{2}) ≢ 0; \\ 0, if B(i_{1}, i_{2}) ≡ 0. \end{cases}

Thus for k = 2, d(r, s) takes its minimal value if and only if (88) holds, and this value is equal to i_{2} − i_{1} = f(i_{1}, i_{2}).

Let k > 2, and assume the proposition has been proved for all k′ < k. By 8.10(vii) we have

d(r, s) =d(i_{1}, i_{k}) = σ(i_{1}, i_{k}) + (i_{2} − i_{1})d(i_{2}, i_{k})

+ ∑_{t=3}^{k} ((i_{t} − i_{t−1})σ(i_{1}, i_{t−1}) + σ(i_{1}, i_{t−2}))d(i_{t}, i_{k})

=σ(i_{1}, i_{k}) + (i_{2} − i_{1})d(i_{2}, i_{k}) + ((i_{3} − i_{2})σ(i_{1}, i_{2}) + σ(i_{1}, i_{1}))d(i_{3}, i_{k})

+ ∑_{t=4}^{k} ((i_{t} − i_{t−1})σ(i_{1}, i_{t−1}) + σ(i_{1}, i_{t−2}))d(i_{t}, i_{k}).

Since σ(i_{1}, i_{1}) = 1 we get

\begin{matrix}d(r, s) = & (i_{2} − i_{1})d(i_{2}, i_{k}) + d(i_{3}, i_{k}) + σ(i_{1}, i_{k}) + (i_{3} − i_{2})σ(i_{1}, i_{2})d(i_{3}, i_{k}) \\ + ∑_{t=4}^{k} ((i_{t} − i_{y−1})σ(i_{1}, i_{t−1}) + σ(i_{1}, i_{t−2}))d(i_{t}, i_{k}). \end{matrix} (89)

By the inductive hypothesis we have

d(i_{2}, i_{k}) ≥ f(i_{2}, i_{3}, …, i_{k}) and d(i_{3}, i_{k}) ≥ f(i_{3}, i_{4}, …, i_{k}).

So d(r, s) ≥ f(i_{2}, i_{3}, …, i_{k}).

On the other hand, if (88) holds then σ(i_{1}, i_{j}) = 0 for j ≥ 2 by virtue of Lemma 3.3. Using the inductive hypothesis we get

d(r, s) = (i_{2} − i_{1})d(i_{2}, i_{k}) + d(i_{3}, i_{k}) = (i_{2} − i_{1})f(i_{2}, i_{3}, …, i_{k}) + f(i_{3}, i_{4}, …, i_{k})
= f(i_{1}, i_{2}, …, i_{k}).

Finally, again by the inductive hypothesis we obtain

d(i_{2}, i_{k}) ≥ f(i_{2}, i_{3}, …, i_{k}), d(i_{3}, i_{k}) ≥ f(i_{3}, i_{4}, …, i_{k}); d(i_{2}, i_{k}) = f(i_{2}, i_{3}, …, i_{k}) if and only if B(i_{j}, i_{j+1}) = 0 for all j = 2, 3, …, k − 1; d(i_{3}, i_{k}) = f(i_{3}, i_{4}, …, i_{k}) if and only if B(i_{j}, i_{j+1}) = 0 for all j = 3, 4, …, k − 1.

Since all summands in the right hand side of (89) are non-negative this implies that d(r, s) = f(i_{1}, i_{2}, …, i_{k}) if and only if B(i_{j}, i_{j+1}) = 0 for j = 2, 3, …, k − 1 and σ(i_{1}, i_{j}) = 0 for j = 2, 3, …, k. By Lemma 3.3, this is equivalent to (88).

9. Some composition multiplicities of L(λ)_{1} | A_{l−1}(K).

Recall that for a weight ν = (ν_{1}, ν_{2}, …, ν_{l}) ∈ P (A_{l}) we denote by ν̄ the weight ν̄ = (ν_{1}, ν_{2}, …, ν_{l−1}) ∈ P (A_{l−1}), cf. Section 7. Throughout this section we denote

μ^{i} = \overline{λ − α(i, l)} ∈ P (A_{l−1}).

Note that α(i, l) = −ω_{i−1} + ω_{i} + ω_{l} (where ω_{0} is interpreted as 0 if i = 1). Since λ is supposed to be dominant throughout Part II, μ^{i} ∈ P_{+}(A_{l−1}) if and only if λ_{i} > 0.

Definition 9.1. We define the integers τ_{i}, i = 1, 2, …, l as follows. Put τ_{i} = 0 if λ_{i} = 0. Let λ_{i} > 0. Then define τ_{i} as the multiplicity of the irreducible A_{l−1}(K)- module L(μ^{i}) in L(λ)_{1} | A_{l−1}(K), i.e.

τ_{i} = [L(λ)_{1} | A_{l−1}(K) : L(μ^{i})] .

Recall the integers ε(r, s), ε′(r, s) defined in 1.13 and (7).

Lemma 9.2. Let 1 ≤ i ≤ l. Then

ε(i, l) = τ_{i} + ∑_{u=i+1}^{l} τ_{u}ε′(i, u − 1).

Proof. Note that L(λ)_{λ−α(i,l)} ⊆ L(λ)_{1}. In view of Lemma 7.3, this implies

L(λ)_{λ−α(i,l)} = (L(λ)_{1} | A_{l−1}(K))_{μ^{i}}. (90)

Assume that η ∈ P (A_{l}) is a weight of the first level of L(λ), i.e. L(λ)_{η} ⊆ L(λ)_{1}. Then η̄ ≥ μ^{i} if and only if and only η = λ − ∑_{u=i}^{l} n_{i}α_{i} with n_{l} = 1 and n_{u} = 0 or 1 for u = i, i+1, …, l−1 (take into account Lemma 7.3). If, moreover, L(η̄) occurs as a composition factor in L(λ) | A_{l−1}(K) then Lemma 7.4 implies that η = λ − α(j, l) for some j ∈ [i, l]. So we may write

L(λ)_{1} | A_{l−1}(K) ∼ ∑_{u=i}^{l} τ_{u}L(μ^{u}) + (∗) (91)

where (∗) stands for composition factorsL(μ) with μ ≱ μ^{i} (in P (A_{l−1})). It follows from (91) that

dim (L(λ)_{1} | A_{l−1}(K))_{μ^{i}} = ∑_{u=i}^{l} τ_{u} dim L(μ^{u})_{μ^{i}}. (92)

Now, by Corollary 8.10(i), we have

dim L(λ)_{λ−α(i,l)} = ε(i, l),

so (90) implies

dim (L(λ)_{1} | A_{l−1}(K))_{μ^{i}} = ε(i, l).

On the other hand, let u ∈ (i, l]. Note that

μ^{u} = ∑_{w=i}^{u−2} λ_{w}ω_{w} + (λ_{u−1} + 1)ω_{u−1} + (∗)

where (∗) stands for the summands of the form cω_{j} with j ∉ [i, u − 1]. However μ^{i} = μ^{u} − α(i, u − 1). So it follows from Corollary 8.10(i) that

dim L(μ^{u})_{μ^{i}} = ε′(i, u − 1) for u ∈ (i, l].

Besides, dim L(μ^{i})_{μ^{i}} = 1.

Now the lemma follows from (92).

Theorem 9.3. Let 1 ≤ i ≤ l. Then τ_{i} = ν(i, l) (cf. Definition 3.1).

Proof. We have by Corollary 5.8(ii)

ν(i, l) = ε(i, l) − ∑_{u=i+1}^{l} ν(u, l)ε′(i, u − 1).

However, by Lemma 9.2 we also have

τ_{i} = ε(i, l) − ∑_{u=i+1}^{l} τ_{u}ε′(i, u − 1).

Now the statement is obtained by the reverse induction on i = l, l − 1, …, 1.

If we consider the subgroup GL_{n−1} < SL_{n} rather than SL_{n−1} < SL_{n} then we can speak about multiplicities in the whole L(λ) ↓_{GL_{n−1}} instead of multiplicities in the first level. More precisely, let Ã_{l−1}(K) < A_{l}(K) be the subgroup generated by the subgroup A_{l−1}(K) and the whole Cartan subgroup of A_{l}(K) (see [13, Section 1] for more details). Then Ã_{l−1}(K) ≅ GL_{l}(K) is diagonally embedded into A_{l}(K) ≅ SL_{l+1}(K). The Cartan subgroups of Ã_{l−1}(K) and A_{l}(K) coincide. So characters of the Cartan subgroup of Ã_{l−1}(K) can be considered as elements of P (A_{l}). Then the (rational) irreducible modules over Ã_{l−1}(K) are parametrized by those λ = (λ_{1}, λ_{2}, …, λ_{l}) ∈ P (A_{l}) with λ_{1}, λ_{2}, …, λ_{l−1} ≥ 0, cf. [13]. The corresponding irreducible module is denoted by L̃(λ). Similarly, we denote the Weyl module over Ã_{l−1}(K) with highest weight λ by Ṽ (λ). (In [13] we wrote L(λ_{1}, …, λ_{l−1}, {λ_{l}}) for L̃(λ) , and V (λ_{1}, …, λ_{l−1}, {λ_{l}}) for Ṽ (λ)).

Of course, part (i) of the following Corollary is not new.

Corollary 9.4. (i) Assume that μ = λ− ∑_{i=1}^{l−1} n_{i}α_{i}, and L̃(μ) occurs as a composition factor of the restriction L(λ) ↓_{Ã_{l−1}(K)}. Then μ = λ, and

[L(λ) ↓_{Ã_{l−1}(K)}: L̃(λ)] = 1.

(ii) Assume that μ = λ − α_{l} − ∑_{i=1}^{l−1} n_{i}α_{i}, with n_{i} ≤ 1, i = 1, 2, …, l − 1. If L̃(μ) occurs as a composition factor of the restriction L(λ) ↓_{Ã_{l−1}(K)} then μ = λ − α(j, l), and

[L(λ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(j, l))] = ν(j, l).

Proof. It is proved in [22] that

⨁ {L_{ν} | ν has a form λ − ∑_{i=1}^{l−1} m_{i}α_{i}}

is an irreducible Ã_{l−1}(K)-submodule of L(λ) ↓_{Ã_{l−1}(K)} isomorphic to L̃(λ). Moreover, dim L(λ)_{λ} = 1 implies

[L(λ) ↓_{Ã_{l−1}(K)}: L̃(λ)] = 1.

This proves (i). Part (ii) follows from Lemmas 7.4, 7.3 and Theorem 9.3.

10. Decomposition numbers [V (λ) : L(λ − α)].

Throughout the section we denote

κ(r, s) = [V (λ) : L(λ − α(r, s))],

κ′(r, s) = [V (λ + ω_{s}) : L(λ + ω_{s} − α(r, s))],

z_{i} = \begin{cases}1, if λ_{i} > 0, \\ 0, if λ_{i} = 0. \end{cases}

The following result is well known.

Lemma 10.1. If λ_{r} > 0, λ_{r} ≡ 0 then [V (λ) : L(λ − α_{r})] = 1. Otherwise we have [V (λ) : L(λ − α_{r})] = 0.

Proof. One has

dim L(λ)_{λ−α_{r}} = \begin{cases}1, if λ_{r} ≢ 0 \\ 0, if λ_{r} ≡ 0. \end{cases}

Moreover,

dim V (λ)_{λ−α_{r}} = \begin{cases}1, if λ_{r} > 0 \\ 0, if λ_{r} = 0. \end{cases}

Now, the result follows from the equality

[V (λ) : L(λ − α_{r})] = dim V (λ)_{λ−α_{r}} − dim L(λ)_{λ−α_{r}}.

Lemma 10.2. [12, 1.7] Assume that [V (λ) : L(λ − α(r, s))] ≠ 0. Then we have λ_{r} > 0, λ_{s} > 0, B(r, s) ≡ 0.

Proof. Since α(r, s) = −ω_{r−1} + ω_{r} + ω_{s} − ω_{s+1}, we must have λ_{r} > 0, λ_{s} > 0 for λ − α(r, s) to be dominant. The equality B(r, s) ≡ 0 follows from the strong linkage principle, see [12, 1.7] for more details.

Recall the constants ν̄(i, j) defined in 3.1.

Proposition 10.3. Assume λ_{1} > 0. Then

κ(1, l) = 1 − ν(1, l) + ∑_{i=1}^{l−1} z_{i+1}κ′(1, i) − ∑_{i=1}^{l−1} ν̄(i + 1, l)κ(1, i). (93)

Proof. We consider the multiplicity

[V (λ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))]

of the irreducible Ã_{l−1}(K)-module L̃(λ − α(1, l)) in the restriction V (λ) ↓_{Ã_{l−1}(K)}. Put

V (λ)_{1} = ⨁ {V (λ)_{ν} | ν has a form λ − α_{l} − ∑_{i=1}^{l−1} m_{i}α_{i}}.

Then V (λ)_{1} is a direct summand of V (λ) ↓_{Ã_{l−1}(K)}. We denote it by V (λ)_{1} | Ã_{l−1}(K) in order to underline that V (λ)_{1} is considered as an Ã_{l−1}(K)-module. Clearly,

[V (λ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))] = [V (λ)_{1} | Ã_{l−1}(K) : L̃(λ − α(1, l))].

It follows from [4], [19] (cf. [12, 1.5] for details) that V (λ)_{1} | Ã_{l−1}(K) has a filtration whose factors are

{Ṽ (λ − α(i, l)) | 1 ≤ i ≤ l, λ_{i} > 0} .

Let 2 ≤ i ≤ l. Then

λ − α(i, l) = λ_{1}ω_{1} + ⋯ + λ_{i−2}ω_{i−2} + (λ_{i−1} + 1)ω_{i−1} + (∗)

where (∗) ∈ ℤω_{i} + ⋯ + ℤω_{l}. So each of the Ṽ (λ − α(i, l)), with 2 ≤ i ≤ l, λ_{i} > 0 contains a composition factor

L̃(λ − α(1, l)) = L̃(λ − α(i, l) − α(1, i − 1))

with multiplicity κ′(1, i − 1) by definition of κ (take into account [22]). Moreover, Ṽ (λ − α(1, l)) contains L̃(λ − α(1, l)) with multiplicity 1. Thus,

[V (λ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))] = 1 + ∑_{i=2}^{l} z_{i}κ′(1, i − 1). (94)

On the other hand, let

0 = V^{(0)} ⊂ V^{(1)} ⊂ ⋯ ⊂ V^{(N)} = V (λ)

be a composition series of the A_{l}(K)-module V (λ). Let μ ∈ P_{+}(A_{l}) and suppose L(μ) occurs as a factor of this composition series exactly x times. If x > 0 then μ ≤ λ. Moreover, if L̃(λ−α(1, l)) occurs y times as a composition factor of the restriction L(μ) ↓_{Ã_{l−1}(K)} then μ contributes xy factors L̃(λ − α(1, l)) into V (λ) ↓_{Ã_{l−1}(K)}. In view of Corollary 9.4, μ ≤ λ and y > 0 imply μ = λ or μ = λ − α(1, i) for some i ∈ [1, l].

Assume μ = λ. Then x = [V (λ) : L(λ)] = 1. Furthermore,

y = [L(λ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))] = ν(1, l)

by Corollary 9.4(ii). Thus μ = λ contributes ν(1, l) factors.

Let μ = λ − α(1, i), 1 ≤ i ≤ l. Then

x = [V (λ) : L(λ − α(1, i))] = κ(1, i).

Moreover, if i = l then

y = [L(λ − α(1, l)) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))] = 1

by Corollary 9.4(i). Assume now that i ∈ [1, l). Then

μ = λ − α(1, i) = (∗) + (λ_{i+1} + 1)ω_{i+1} + λ_{i+2}ω_{i+2} + ⋯ + λ_{l}ω_{l}

where (∗) ∈ ℤω_{1} + ⋯ + ℤω_{i}. Therefore

y = [L(μ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))] = [L(μ) ↓_{Ã_{l−1}(K)}: L̃(μ − α(i + 1, l))] = ν̄(i+1, l)

by Corollary 9.4(ii).

Summarizing we have

[V (λ) ↓_{Ã_{l−1}(K)}: L̃(λ − α(1, l))] = κ(1, l) + ν(1, l) + ∑_{i=1}^{l−1} κ(1, i)ν̄(i + 1, l).

Comparing this with (94) we get (93).

From Proposition 10.3 we immediately get (taking into account [22])

Corollary 10.4. Assume λ_{r} > 0. Then

κ(r, s) = 1 − ν(r, s) + ∑_{i=r}^{s−1} z_{i+1}κ′(r, i) − ∑_{i=r}^{s−1} ν̄(i + 1, s)κ(r, i).

Recall the constants σ̄(i, j) defined in (31). The next result provides a recurrence formula for the decomposition numbers κ(r, s) = [V (λ) : L(λ − α(r, s))]. In view of Lemmas 10.1 and 10.2, the assumptions are not very restrictive.

Corollary 10.5. Let 1 ≤ r < s ≤ l, λ_{r} > 0, λ_{s} > 0, B_{λ}(r, s) ≡ 0. Then

κ(r, s) = κ(r, s − 1) + σ(r, s − 1) + ∑_{i=r}^{s−2} κ(r, i)σ̄(i + 1, s − 1), (95)

if λ_{s} ≢ 0.

Moreover, if λ_{s} ≡ 0 then κ(r, s) = κ′(r, s − 1).

Remark. Actually one can prove that the equality (95) holds in the case λ_{s} ≡ 0, too. However we do not need to prove it here since it will follow from Theorem 10.6 and Proposition 6.9.

Proof. By Corollary 10.4, we have

κ(r, s) = 1 − ν(r, s) + ∑_{i=r}^{s−1} z_{i+1}κ′(r, i) − ∑_{i=r}^{s−1} ν̄(i + 1, s)κ(r, i),

κ(r, s − 1) = 1 − ν(r, s − 1) + ∑_{i=r}^{s−2} z_{i+1}κ′(r, i) − ∑_{i=r}^{s−2} ν̄(i + 1, s − 1)κ(r, i).

So

\begin{aligned}κ(r, s) − κ(r, s − 1) = & − (ν(r, s) − ν(r, s − 1)) + z_{s}κ′(r, s − 1) \\ & − ∑_{i=r}^{s−2} (ν̄(i + 1, s) − ν̄(i + 1, s − 1))κ(r, i) \\ & − ν̄(s, s)κ(r, s − 1). \end{aligned} (96)

Since λ_{s} > 0 we have

z_{s} = 1. (97)

Moreover, ν̄(s, s) ≠ 0 if and only if λ_{s} + 1 ≢ 0. But in this case

B(r, s − 1) = B(r, s) − (λ_{s} + 1) ≢ 0.

So κ(r, s − 1) = 0 in view of Lemma 10.2. Thus,

ν̄(s, s)κ(r, s − 1) = 0. (98)

By Lemma 3.5 we have

ν̄(i + 1, s) − ν̄(i + 1, s − 1)

= \begin{cases}1, & if ν̄(i + 1, s − 1) ≠ 0, λ_{s} ≢ 0, C_{λ(i+1)}(i + 1, s) ≡ 0; \\ −1, & if ν̄(i + 1, s − 1) ≠ 0, λ_{s} ≢ 0, B_{λ(i+1)}(i + 1, s) ≡ 0; \\ 0, & otherwise. \end{cases} (99)

Since B(r, s) ≡ 0, the same lemma implies

(100) − (ν(r, s) − ν(r, s − 1)) = \begin{cases}1, & if ν(r, s − 1) ≠ 0, λ_{s} ≢ 0; \\ 0, & otherwise. \end{cases}

Now assume λ_{s} ≡ 0. Then B(r, s − 1) = B(r, s) − (λ_{s} + 1) ≡ −1 ≢ 0. Therefore κ(r, s − 1) = 0 in view of Lemma 10.2. Now (96)-(100) imply κ(r, s) = κ′(r, s − 1).

Let λ_{s} ≢ 0. Then we have from (100)

− (ν(r, s) − ν(r, s − 1)) = σ(r, s − 1). (101)

Moreover, κ(r, i)(ν̄(i+1, s)−ν̄(i+1, s−1)) ≠ 0 implies κ(r, i) ≠ 0, hence B_{λ}(r, i) ≡ 0 by Lemma 10.2. Note that B_{λ}(r, s) = B_{λ}(r, i) + B_{λ(i+1)}(i + 1, s). So

κ(r, i)(ν̄(i + 1, s) − ν̄(i + 1, s − 1)) ≠ 0

implies B_{λ(i+1)}(i + 1, s) ≡ 0. But for such i we have, in view of (99),

−(ν̄(i + 1, s) − ν̄(i + 1, s − 1)) = σ̄(i + 1, s − 1).

Now (96)-(100) imply

κ(r, s) = κ(r, s − 1) + κ′(r, s − 1) + σ(r, s − 1) + ∑_{i=r}^{s−2} κ(r, i)σ̄(i + 1, s − 1).

It remains to note that B_{λ(s−1)}(r, s − 1) = B_{λ}(r, s) − λ_{s} ≢ 0 so κ′(r, s − 1) = 0 in view of Lemma 10.2.

Recall the constants q_{r,s}(λ) defined in 6.5.

Theorem 10.6. Let λ ∈ P_{+}(A_{l}), 1 ≤ r ≤ s ≤ l. Then

[V (λ) : L(λ − α_{r} − α_{r+1} − ⋯ − α_{s})] = q_{r,s}(λ).

Proof. We proceed by induction on s − r. If s − r = 0 then the result follows from 10.1 and 6.5. Let s − r > 0, and the theorem have been proved for all r′, s′ with s′ − r′ < s − r. If B(r, s) ≢ 0 or λ_{r} = 0 or λ_{s} = 0 then the result follows from 10.2 and 6.5. Assume B(r, s) ≡ 0, λ_{r} > 0, λ_{s} > 0. Then Corollary 10.5 yields

κ(r, s) = κ(r, s − 1) + σ(r, s − 1) + ∑_{i=r}^{s−2} κ(r, i)σ̄(i + 1, s − 1), if λ_{s} ≢ 0,

κ(r, s) = κ′(r, s − 1), if λ_{s} ≡ 0.

On the other hand,

q_{r,s} = q_{r,s−1} + σ(r, s − 1) + ∑_{i=r}^{s−2} q(r, i)σ̄(i + 1, s − 1), if λ_{s} ≢ 0,

q_{r,s} = q′_{r,s−1}, if λ_{s} ≡ 0

by Proposition 6.9. Now it suffices to apply the inductive hypothesis.

11. How to translate from SL_{n} to Σ_{n}

Throughout the section n = l + 1. We denote by ν′ the partition conjugate to a partition ν.

Let λ = (λ_{1}, λ_{2}, …, λ_{l}) ∈ P_{+}(A_{l}) be a dominant weight. Assume that

∑_{i=1}^{l} iλ_{i} = n.

Then we can define partitions of n:

φ_{n}(λ) = (λ_{1} + λ_{2} + ⋯ + λ_{l}, λ_{2} + ⋯ + λ_{l}, …, λ_{l}),
ψ_{n}(λ) = φ_{n}(λ)′.

We also define

ψ_{n}(0) = (n).

On the other hand, let us represent a partition μ of n in the form

μ = (μ_{1}^{b_{1}}, μ_{2}^{b_{2}}, …, μ_{k}^{b_{k}}); μ_{1} > μ_{2} > ⋯ > μ_{k}; b_{1}, b_{2}, …, b_{k} > 0.

If μ ≠ (n) we define a dominant weight w_{n}(μ) ∈ P_{+}(A_{l}) by setting

w_{n}(μ) = b_{k}ω_{μ_{k}} + b_{k−1}ω_{μ_{k−1}} + ⋯ + b_{1}ω_{μ_{1}}.

We also set

w_{n}((n)) = 0 ∈ P_{+}(A_{l}).

One clearly has

w_{n} ∘ ψ_{n} = id, ψ_{n} ∘ w_{n} = id .

The following fundamental result identifies the decomposition numbers of Σ_{n} with certain decomposition numbers of SL_{n} (the result follows immediately from the corresponding result for GL_{n} proved in [6]).

Proposition 11.1. [6] Let μ, ν be partitions of n and ν be p-regular. Then

[S^{μ} : D^{ν}] = [V (w_{n}(μ)) : L(w_{n}(ν))] .

The question on branching multiplicities for Σ_{n} can also be reduced to a similar question for SL_{n} (we assumed ν ≠ (n) in [13] but for ν = (n) the statement is trivial).

Proposition 11.2. [13, 2.12(v)] Let μ be a p-regular partition of n and ν be a p-regular partition of n − 1. Then

[D^{μ} ↓_{Σ_{n−1}}: D^{ν}] = [L(w_{n}(μ))_{1} | A_{l−1}(K) : L(w_{n−1}(ν))] .

Finally we can identify the multiplicities of the Young modules Y^{ν} in the permutation modules M^{μ} (over Σ_{n}) with weight multiplicities of the irreducible modules L(w_{n}(μ′)) (over SL_{n}). The next result is due to Klyachko.

Proposition 11.3. [17] (see also [18]) Let λ and μ be partitions of n. Then

[M^{λ} : Y^{μ}] = dim L(w_{n}(μ′))_{w_{n}(λ′)}.

We now explain how Theorem 1.4 can be deduced from Theorem 9.3 and Proposition 11.2.

Let λ = (l_{1} ≥ l_{2} ≥ ⋯ ≥ l_{m} > 0) be a p-regular partition of n. We may assume λ ≠ (n) since then Theorem 1.4 is evident. Recall that

λ(j) = (l_{1}, …, l_{j−1}, l_{j} − 1, l_{j+1}, …, l_{m})

(see (2)). Then

w_{n−1}(λ(j)) = \overline{w_{n}(λ) − α(l_{j}, l)}.

So in view of Proposition 11.2,

[D^{λ} ↓_{Σ_{n−1}}: D^{λ(j)}] = [L(w_{n}(λ))_{1} | A_{l−1}(K) : L(\overline{w_{n}(λ) − α(l_{j}, l)})] .

However, the multiplicities [L(w_{n}(λ))_{1} | A_{l−1}(K) : L(\overline{w_{n}(λ) − α(l_{j}, l)})] have been calculated in Theorem 9.3. Now to deduce Theorem 1.4 we need only to note that

l_{k} − l_{j} + j − k + 1 = B_{w_{n}(λ)}(l_{j}, l_{k})

for any 1 ≤ k < j ≤ m with l_{k} < l_{k−1} and l_{j} > l_{j+1}, (102)

and l_{k} − l_{j} + j − k = C_{w_{n}(λ)}(l_{j}, l_{k})

for any 1 ≤ k < j ≤ m with l_{k} > l_{k+1} and l_{j} > l_{j+1}. (103)

Moreover, note that if λ ≠ (n) then

w_{n}(λ(i, j)) = w_{n}(λ) − α(l_{j}, l_{i}).

So to deduce Theorem 1.10 it suffices to use Theorem 10.6, Proposition 11.1 and (102), (103).

Besides,

w_{n}(λ′) = w_{n}(λ(i, j)′) − α(i, j − 1).

So, by Proposition 11.3, the description of the multiplicities [M^{λ} : Y^{λ(i,j)}] follows immediately from Corollary 8.10.

References

1. C. Bessenrodt and J.B. Olsson. On residue symbols and the Mullineux conjecture, preprint, 1996.

2. N. Bourbaki. Groupes et Algebres de Lie, Hermann, Paris, 1968.

3. R. Carter and M. T. J. Payne. On homomorphisms between Weyl and Specht modules, Math. Proc. Camb. Phil. Soc. 87(1980), 131-145.

4. S. Donkin. Rational Representations of Algebraic Groups, volume 1140 of Lecture Notes in Mathematics. Springer-Verlag, Berlin/Heidelberg/New York, 1985.

5. B. Ford and A. Kleshchev. A proof of the Mullineux conjecture, preprint, 1995 (to appear in Math. Z.)

6. J. A. Green. Polynomial Representations of GL_{n}, volume 830 of Lecture Notes in Mathematics. Springer-Verlag, Berlin/Heidelberg/New York, 1980.

7. G. D. James. On the decomposition matrices of the symmetric groups, II, J. Algebra 43(1976), 45–54.

8. G. D. James. The Representation Theory of the Symmetric Groups, volume 682 of Lecture Notes in Mathematics. Springer, New York/Heidelberg/Berlin, 1978.

9. G. D. James. The representation theory of the symmetric groups. In The Arcata Conference on Representations of Finite Groups, number 47 in Proc. Sympos. Pure Math., pages 111–126. Amer. Math. Soc., 1987.

10. G. D. James and A. Kerber. The Representation Theory of the Symmetric Group. Addsion-Wesley, London, 1981.

11. J. C. Jantzen. Representations of Algebraic Groups, Academic Press, Orlando, 1987.

12. J. C. Jantzen and G. M. Seitz. On the representation theory of the symmetric groups. Proc. London Math. Soc. (3), 65(1992), 475–504.

13. A. S. Kleshchev. Branching rules for modular representations of symmetric groups, I. J. Algebra 178(1995), 493-511.

14. A. S. Kleshchev. Branching rules for modular representations of symmetric groups, II. J. Reine Angew. Math., 459(1995), 163–212.

15. A. S. Kleshchev. Branching rules for modular representations of symmetric groups, III. J. London Math. Soc. (2) 54(1996), 25-38.

16. A. S. Kleshchev. Completely splittable representations of symmetric groups, J. Algebra 181(1996), 584-592.

17. A. Klyachko. Direct summands of permutation modules, Sel. Math. Sov., 3(1983/84), 45-55.

18. S. Martin. Schur Algebras and Representation Theory. Cambridge, 1993.

19. O. Mathieu. Filtrations of G-modules. Ann. Scient. Ec. Norm. Sup. (2), 23(1990), 625-644.

20. O. Mathieu. On the dimension of some modular irreducible representations of the symmetric group, preprint, 1994.

21. G.M Seitz. The Maximal Subgroups of Classical Algebraic Groups. Mem. Amer. Math. Soc. 67(1987), 1-286.

22. S.D. Smith. Irreducible modules and parabolic subgroups. J. Algebra, 74(1982), 286-289.

23. I.D. Suprunenko. On restrictions of irreducible representations of the group SL(m, K) to classical groups. Preprint No 16(201), Inst. Math., Minsk, 1984.

24. R. Steinberg. Lectures on Chevalley Groups. Yale University, 1967.

25. K. Timmerscheidt. Socle series of the restrictions of irreducible Σ_{n}-modules to Σ_{n−1} in characteristics 2, 3, and 5, n ≤ 10. Results of computer calculations with MAGMA, Aberystwyth, 1994.

Department of Mathematics, University of Oregon, Eugene OR 97403, USA E-mail address: klesh@math.uoregon.edu