Decomposition Numbers of SL_{3}(p^{n}) and SU_{3}(p^{n})

Leonard Chastkofsky Department Of Mathematics University of Georgia Athens, GA 30602

Introduction

In [1] we gave a technique for determining the characteristic p decomposition numbers of a Chevalley group G(p^{n}). We showed that in certain cases, the decomposition numbers for a projective indecomposable character Φ_{λ,n} can be determined by computing the trace of the product of certain matrices. In this paper we apply the results to the groups SL_{3}(p^{n}) and SU_{3}(p^{n}) to get explicit formulas for the multiplicities of decomposition numbers. We will show that the number of times a given integer k occurs as a decomposition number in Φ_{λ,n} has a generating function which is a combination of a rational function and a Dirichilet series. This result gives us an alternative approach to determining the Cartan invariants.

§1. Summary of Previous Results and Statement of Main Theorem

We review the results obtained in [1], as applied to SL_{3}(p^{n}) and SU_{3}(p^{n}).

Let Γ_{n} be either the group SL_{3}(p^{n}) or SU_{3}(p^{n}). Let X be the weight lattice for Γ_{n}. It is isomorphic to ℤ^{+} × ℤ^{+}. Let X_{p^{n}} be the subset of p^{n} - restricted weights, consisting of those elements of X whose coordinates in terms of the fundamental dominant weights lie between 0 and p^{n} − 1. The projective indecomposable characters are indexed by weights λ in X_{p^{n}}. Let Φ_{λ,n} be the projective indecomposable character indexed by λ.

Let W be the Weyl group. Let W_{a,p} be the affine Weyl group, that is, the semidirect product of W with translations by elements of p times the root lattice. Let W̃_{a,p} be the extended affine Weyl group, that is, the semidirect product of W with translations by elements of p times the weight lattice There are two W_{a,p}- alcoves in X_{p}. The top alcove consists of (r, s) in X_{p} with r + s ≥ p − 1, while the bottom alcove consists of those with r + s < p − 1. The results on decomposition numbers of Φ_{λ,n} in [1] assume that λ is deep enough in a W̃_{a,p} alcove. In this paper we shall always assume that λ satisfies this condition.

Let S_{3} be the following set of 12 matrices:

Typeset by AMS-TEX

S_{3} = \{ ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} )\}

From [1], we have the following:

\underline{Theorem 1.1:} There is a coding of Deligne-Lusztig characters of Γ_{n} by (X_{p}×W)^{n}. Denote the character coded by (α_{1}, …, α_{n}), α_{i} ∈ X_{p}×W by χ(α_{1}, …, α_{n}). For each i with 1 ≤ i ≤ n there is a subset A_{i} of X_{p}×W such that the set {χ(α_{1}, …, α_{n})|α_{i} ∈ A_{i}} gives a full set of irreducible characters, without repetition, which appear in Φ_{λ,n}. For each i with 1 ≤ i ≤ n, there is a map M_{i} from X_{p} × W to S_{3} such that the multiplicity of the irreducible character χ(α_{1}, …, α_{n}) in Φ_{λ,n} is equal to

T r( ∏_{i=1}^{n} M_{i}(α_{i})). Moreover,

1) If 2 ≤ i ≤ n and M_{i} ∈ S_{3}, M_{i} ≠ ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) then there is

exactly one α_{i} ∈ A_{i} with M_{i}(α_{i}) = M_{i}.

2) If 2 ≤ i ≤ n and M_{i} ∈ S_{3}, M_{i} = ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) then there are

exactly two α_{i} ∈ A_{i} with M_{i}(α_{i}) = M_{i}.

3) If λ is in the top alcove of X_{p} , the only matrix which can occur as M_{1}(α_{1})

is ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ), which occurs for exactly six such α_{1}.

4) If λ is in the bottom alcove of X_{p} , the only matrices which can occur as

M_{1}(α_{1}) are ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ), ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ), ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) and ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) each of

which occur for exactly six such α_{1}.

\underline{Remark:} In the case of SU_{3}(p^{n}), there is actually another ”twisting” matrix, M_{π} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ), which occurs as a factor in the product. However, as the

argument at the end of 5.2 in [1] shows, adding this matrix as a factor merely permutes the set of matrices occurring for SL_{3}(p^{n}). Thus the theorem is also true for SU_{3}(p^{n}), as stated.

For a sequence (M_{1}, …, M_{n}) ∈ (S_{3})^{n} define β(M_{1}, …, M_{n}) to be the number of

M_{i} , 2 ≤ i ≤ n which are equal to ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ).

\underline{Corollary 1.2:} 1) Suppose that λ is in the top alcove of X_{p}. The number of times which the integer k occurs as a decomposition number in Φ_{λ,n} is equal to 6 times ∑ 2^{β(M_{1},...,M_{n})}, where the sum is over sequences (M_{1}, …, M_{n}) ∈ (S_{3})^{n} with

M_{1} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) and with T r(∏ M_{i}) = k.

2)Suppose that λ is in the bottom alcove of X_{p}. The number of times which the integer k occurs as a decomposition number in Φ_{λ,n} is equal to 6 times ∑ 2^{β(M_{1},...,M_{n})},

where the sum is over sequences (M_{1}, …, M_{n}) ∈ (S_{3})^{n} with M_{1} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ),

( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ),( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) and with T r(∏ M_{i}) = k.

Define d̃_{n}^{1}(k) to be the number of times that k occurs as a decomposition number in Φ_{λ,n}, when λ is in the top alcove, and d̃_{n}^{2}(k) to be the number of times that k occurs as a decomposition number in Φ_{λ,n}, when λ is in the bottom alcove. For i = 1, 2, define

g̃_{i}(x, s) = ∑_{k,n} d̃_{n}^{i}(k)x^{n}k^{−s}.

If a and b are positive integers with a ≥ b, let l(a, b) be the number of steps needed to find the greatest common divisor of a and b by the subtractive algorithm. For k ≥ 1 define a polynomial f_{k}(x) as follows:

f_{k}(x) = ∑_{\begin{matrix}1≤a≤k \\ (k,a)=1 \end{matrix}} x^{l(k,a).}

Define ξ(x, s) to be

∑_{k≥2} f_{k}(x)k^{−s}.

These functions will be discussed in more detail in section 3.

\underline{Main Theorem :}For i = 1, 2,

g̃_{i}(x, s) = g_{i}(\frac{2x}{1 − 2x}, s)

where

g_{1}(x, s) = \frac{(1 − x)^{2}(1 − 2x)}{(1 + x)(1 − 4x + x^{2} − (x + x^{2})ξ(x, s))} − \frac{1 − x}{1 + x}

while

g_{2}(x, s) = \frac{(1 − x)^{2}}{1 − 4x + x^{2} − (x + x^{2})ξ(x, s)} − 1.

§2. Reduction of Rank

We have seen that the problem of determining how many times an integer k occurs as a decomposition number in Φ_{λ,n} is equivalent to determining how many times it occurs as the trace of a product of certain 3 × 3 matrices. We will now show that the problem can be reduced further to determining how many times it occurs as the trace of a product certain 2 × 2 matrices, belonging to a smaller set.

Let S_{2} = \{( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) , ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )\}.

Let S̄_{2} = S_{2} ∪ ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ).

We partition S_{3} into 4 subsets S_{∅} ,S_{σ_{1}}, S_{σ_{2}},andS_{σ_{1},σ_{2}}, as follows:

S_{∅} = \{( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} )\}

S_{σ_{1}} = \{( \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} )\}

S_{σ_{2}} = \{( \begin{matrix}1 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} )\}

S_{σ_{1},σ_{2}} = \{( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )\}.

We consider the matrices in S_{3} as being indexed by the elements 1,σ_{1},σ_{2} of the Weyl group. Note that in the columns corresponding to σ_{1} and σ_{2}, there is at most one non-zero entry. A matrix is placed in S_{σ_{1}} if there is a 1 in the σ_{1} column, but not in the σ_{2} column. A matrix is placed in S_{σ_{2}} if there is a 1 in the σ_{2} column, but not in the σ_{1} column. It is placed in S_{σ_{1},σ_{2}} if there is a 1 in both columns, and in S_{∅} if there is a 1 in neither.

We will now define a map θ : S_{3} → S_{2} Consider (M_{1}, …, M_{n}) ∈ S_{3}^{n}. Assign to this element the element θ (M_{1}, …, M_{n}) = (M′_{1}, …, M′_{n}) ∈ S_{2} as follows:

We consider the matrices in S_{2} as being indexed by 1 and the set {σ_{1}, σ_{2}}.

If there is a 1 (resp. 0) in the 1-1 entry of M_{i}, there is a 1 (resp. 0) in the 1-1 entry of M′_{i}.

If there are ones (resp. zeroes) in both the σ_{1}–1 and σ_{2}–1 entries of M_{i}, there is a 1 (resp. 0) in the {σ_{1}, σ_{2}}–1 entry of M′_{i}.

If there is a 1 in either the 1-σ_{1} or the 1-σ_{2} entry of M_{i}, there is a 1 in the 1–{σ_{1}, σ_{2}} entry of M′_{i}. Otherwise there is a 0 there.

If there are ones in the σ_{1}–σ_{1} and σ_{2}–σ_{2} entries of M_{i}, there is a 1 in the {σ_{1}, σ_{2}}–{σ_{1}, σ_{2}} entry of M′_{i}.

If there are zeroes in all the σ_{k}–σ_{l} entries of M_{i}, k, l = 1, 2, there is a 0 in the {σ_{1}, σ_{2}}–{σ_{1}, σ_{2}} entry of M′_{i}.

This assigns M′_{i} to 6 of the matrices in S_{3}. Thus we have:

If M_{i} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ).

If M_{i} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ).

If M_{i} = ( \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) or ( \begin{matrix}1 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ).

If M_{i} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ).

If M_{i} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ).

The assignment for each of the remaining 6 matrices depends on its position relative to the other M_{j}. We consider the M_{i} as being arranged on a circle, with nodes numbered 1 to n.

Suppose that there is a 1 (resp. 0)in the σ_{1}–1 entry and a 0 (resp. 1) in the σ_{2}–1 entry of M_{i}. Consider the first M_{j} preceding M_{i} on the circle which is not in S_{σ_{1},σ_{2}}; if M_{j} is in S_{σ_{1}}, then there is a 1 (resp. 0) in the {σ_{1}, σ_{2}}–1 entry of M′_{i}; if it is in S_{σ_{2}}, then there is a 0 (resp. 1) in that entry of M′_{i}; if it is in S_{∅}, then we assign the {σ_{1}, σ_{2}}–1 entry of M′_{i} arbitrarily; but we do so in such a way that in half the cases the assignments are equal to 1, while in half they are equal to 0. (This is not really essential, because the trace of the product in this case will be 0, but we do this for aesthetic reasons.) Note that there always is an M_{j} preceding M_{i} on the circle which is not in S_{σ_{1},σ_{2}}, even though we may need to go all the way around the circle to reach M_{i} itself.

Suppose that there is a 1 in the σ_{k}–σ_{l} position , with k = 1, 2 and k ≠ l. There is at most one such pair (k, l) for these 6 matrices. If the first M_{j} preceding M_{i} which is not in S_{σ_{1},σ_{2}} is in S_{σ_{k}}, then there is a 1 in the {σ_{1}, σ_{2}}–{σ_{1}, σ_{2}} entry of M′_{i}; if it is in S_{σ_{l}}, then there is a 0 in that entry ;if it is in S_{∅}, then we assign the {σ_{1}, σ_{2}}– {σ_{1}, σ_{2}}entry arbitrarily in such a way that half the assignments are 1, and half are 0.

To summarize, we have the following assignments, where for each choice of assignment, half the assignments are to the first matrix, and half to the second:

If M_{i} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) or ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) or ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ).

If M_{i} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ) then M′_{i} = ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) or ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ).

If M_{i} = ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) then M′_{i} = ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 \\ 0 & 0 \end{matrix} ).

We will show that this assignment preserves traces of products. To show this we will use graphs associated with the sets S_{2} and S_{3}.

Suppose that S is a set of 0–1 matrices each of which is indexed by a set V. We associate with S a colored directed graph G(S) as follows. We assume that there is a color C(M) for each M ∈ S. The vertices of G(S) are the elements of V. There is an edge of color C(M) from v to w if and only if the v–w entry of M ∈ S is 1.

It is easy to see that T r (∏ M_{i}) , M_{i} ∈ S is equal to the number of closed paths in G(S) with successive edges of colors C(M_{1})C(M_{2}) … C(M_{n}).

\underline{Proposition 2.1}: Let (M_{1}, …, M_{n}) ∈ S_{3}^{n} and let θ (M_{1}, …, M_{n}) = (M′_{1}, …, M′_{n}) ∈ S_{2}^{n} be defined as above. Assume that not all M_{i} are in S_{σ_{1},σ_{2}}. Then T r (∏ M_{i}) = T r (∏ M′_{i}). \underline{Proof}: We will show that the number of closed paths in G(S_{3}) with successive edges edges of colors C(M_{1}), C(M_{2}), …, C(M_{n}) is equal to the number of closed paths in G(S_{2}) with successive edges edges of colors C(M′_{1}), C(M′_{2}), …, C(M′_{n}) . Let E_{1}, E_{2}, …, E_{n} be edges in G(S_{3}), E_{i} of color C(M_{i}), which form a closed path in G(S_{3}). We will associate to each E_{i} an edge E′_{i} of color C(M′_{i}) in G(S_{2}) such that E′_{1}, E′_{2}, …, E′_{n} form a closed path in G(S_{2}) .

If E_{i} : 1 → 1 is an edge of color C(M_{i}), then there is an edge E′_{i} : 1 → 1 of color C(M′_{i}) .

There is at most one edge E_{i} : 1 → σ_{1} or E_{i} : 1 → σ_{2} of color C(M_{i}). If there is such an edge, then there is an edge E′_{i} : 1 → {σ_{1}, σ_{2}} of color C(M′_{i}) .

Suppose that there is an edge E_{i} : σ_{1} → 1 (resp. E_{i} : σ_{2} → 1 )of color C(M_{i}). If such an edge is part of a closed path in G(S_{3}), then the first M_{j} preceding M_{i} on the circle which is not in S_{σ_{1},σ_{2}} is in S_{σ_{1}} (resp. S_{σ_{2}}). Thus there is at most one such edge, and if there is one, there is also an edge E′_{i} : {σ_{1}, σ_{2}} → 1 of color C(M′_{i}).

There is an edge E_{i} : σ_{1} → σ_{1} of color C(M_{i}) if and only if there is an edge E_{i} : σ_{2} → σ_{2} of color C(M_{i}). Suppose there are such edges, and suppose that the first M_{j} preceding M_{i} on the circle which is not in S_{σ_{1},σ_{2}} is in S_{σ_{k}}. Then the only one of the 2 edges which can be part of a closed path is the E_{i} : σ_{k} → σ_{k}. There is a corresponding edge E′_{i} : {σ_{1}, σ_{2}} → {σ_{1}, σ_{2}} of color C(M′_{i}) .

There is at most one edge E_{i} : σ_{k} → σ_{l} with k = 1, 2 and k ≠ l of color C(M_{i}). If there is such an edge, then the first M_{j} preceding M_{i} on the circle which is not in S_{σ_{1},σ_{2}} is in S_{σ_{k}}. There is then also an edge E′_{i} : {σ_{1}, σ_{2}} → {σ_{1}, σ_{2}} of color C(M′_{i}) .

Conversely, it is clear that every edge E′ in G(S_{2}) which is part of a closed path arises in exactly one way from an edge E_{i} in the way just described. This proves the proposition.

\underline{Corollary 2.2:} 1) Suppose that λ is in the top alcove of X_{p}. The number of times which the integer k occurs as a decomposition number in Φ_{λ,n} is equal to 3 × 2^{n}

times the number of sequences (M′_{1}, …, M′_{n}) ∈ (S_{2})^{n} with M′_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) and with

T r(∏ M′_{i}) = k.

2) Suppose that λ is in the bottom alcove of X_{p}. The number of times which the integer k occurs as a decomposition number in Φ_{λ,n} is equal to 3 × 2^{n} times

the number of sequences (M′_{1}, …, M′_{n}) ∈ (S_{2})^{n} with M′_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ),( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) or

( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) and with T r(∏ M′_{i}) = k.

\underline{Proof}: 1) By 1.2, the number of times which the integer k occurs as a decomposition number in Φ_{λ,n} is equal to 6 times ∑ 2^{β(M_{1},...,M_{n})}, where the sum is over sequences

(M_{1}, …, M_{n}) ∈ (S_{3})^{n} with M_{1} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) and with T r(∏ M_{i}) = k. Let

β(M′_{1}, …, M′_{n}) be the number of M′_{i} , 2 ≤ i ≤ n which are equal to ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) . Note

that β(M_{1}, …, M_{n}) = βθ(M_{1}, …, M_{n}). For each sequence (M′_{1}, …, M′_{n}) ∈ (S_{2})^{n}

with M′_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ), there are 2^{n−1−β(M′_{1},...,M′_{n})} sequences (M_{1}, …, M_{n}) ∈ (S_{3})^{n}

with M_{1} = ( \begin{matrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) and θ (M_{1}, …, M_{n}) = (M′_{1}, …, M′_{n}) . Thus the number

of times which k occurs is equal to the sum over (M′_{1}, …, M′_{n}) ∈ (S_{2})^{n} with M′_{1} =

( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) of 6 × 2^{n−1−β(M′_{1},...,M′_{n})} × 2^{β(M′_{1},...,M′_{n})} = 3 × 2^{n}, as claimed.

2) is proved similarly.

This gives us the following result: \underline{Proposition 2.3:}The largest decomposition number occurring in Φ_{λ,n} is F_{n+1}, where F_{n} is the nth Fibonacci number (F_{1} = F_{2} = 1), and this occurs as a decomposition number 3 × 2^{n} times. \underline{Proof}: The largest trace which can occur as T r(∏ M_{i}) with (M_{1}, …, M_{n}) ∈ (S_{2})^{n}

and M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) is when M_{i} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) for 2 ≤ i ≤ n. The product is equal to

( \begin{matrix}F_{n} & F_{n−1} \\ F_{n} & F_{n−1} \end{matrix} ), whose trace is equal to F_{n+1}. .

§3. Subtractive Length Polynomials and Dirichilet Series

The problem of determining the decomposition numbers occurring in Φ_{λ,n} has been reduced to determining the integers which occur as traces of a product of n matrices in S_{2}. We will obtain recursions for the number of times that an integer k occurs as a product of n such matrices. The solution to these recursions involves certain polynomials which we now define.

If a and b are positive integers with a ≥ b, let l(a, b) be the number of steps needed to find the greatest common divisor of a and b by the subtractive algorithm. Recall that the subtractive algorithm proceeds from the observation that the g.c.d of a and b is the same as the g.c.d of b and a − b. Thus l(a, b) can be defined inductively as follows :

(3.1)  l(a, b) = \{ \begin{matrix}0, & if a = b \\ l(a − b, b) + 1, & if a − b ≥ b \\ l(b, a − b) + 1, & if a − b < b. \end{matrix}

The subtractive length in this definition is 1 less than in the more common one, where the algorithm proceeds one more step until the pair (1, 0) is reached. It is also 1 less than the sum of the partial quotients in the continued fraction representation of a/b.

Note that we have not defined l(a, b) for a < b. We leave l(a, b) undefined in this case. Thus, for example, when we have a summation wherein l(a, b) makes an appearance, it is understood that the summation is over (a, b) with a ≥ b.

\underline{Lemma 3.2}: If a and b are positive integers with a > b then l(a, b) = l(a, a − b). \underline{Proof}: By 3.1, l(a, a − b) is equal to either 1 + l(a − b, b) or 1 + l(b, a − b), which is the same as l(a, b).

For k ≥ 1 define a polynomial f_{k}(x) as follows:

f_{k}(x) = ∑_{\begin{matrix}1≤a≤k \\ (k,a)=1 \end{matrix}} x^{l(k,a).}

Here we are writing (k, a) for the g.c.d. of k and a.

\underline{Examples}: We give the values of f_{k}(x) for 1 ≤ k ≤ 8.

f_{1}(x) = 1
f_{2}(x) = x
f_{3}(x) = 2x^{2}
f_{4}(x) = 2x^{3}
f_{5}(x) = 2x^{3} + 2x^{4}

f_{6}(x) = 2x^{5}
f_{7}(x) = 4x^{4} + 2x^{6}
f_{8}(x) = 2x^{4} + 2x^{7}

We shall need the following later:

\underline{Lemma 3.3}:For any d dividing k we have

f_{k/d}(x) = ∑_{\begin{matrix}d≤a≤k \\ (k,a)=d \end{matrix}} x^{l(k,a)}.

\underline{Proof}:By definition,

f_{k/d}(x) = ∑_{\begin{matrix}1≤a′≤k/d \\ (k/d,a′)=1 \end{matrix}} x^{l(k/d,a′)}.

But (k, a) = d if and only if (k/d, a/d) = 1, and l(k, a) = l(k/d, a/d). We thus get the formula stated.

\underline{Lemma 3.4}:For any d dividing k, d ≠ k/2, k, we have

f_{k/d}(x) = 2x ∑_{\begin{matrix}a+b=k \\ (a,b)=d \end{matrix}} x^{l(a,b)}.

\underline{Proof}: If (k, a) = d, then (k, k − a) = d and l(k, a) = l(k, k − a). Since d is not equal to either k/2 or k, k − a is not equal to either 0 or a. Thus

f_{k/d}(x) = ∑_{\begin{matrix}d≤a≤k \\ (k,a)=d \end{matrix}} x^{l(k,a)}

= 2 ∑_{\begin{matrix}k/2<a<k \\ (k,a)=d \end{matrix}} x^{l(k,a)}

= 2 ∑_{\begin{matrix}k/2<a<k \\ (k,a)=d \end{matrix}} x^{l(a,k−a)+1}

= 2x ∑_{\begin{matrix}a+b=k \\ (a,b)=d \end{matrix}} x^{l(a,b)}

Define ξ(x, s) to be

∑ f_{k}(x)k^{−s},

the sum being over all k ≥ 2.

\underline{Proposition 3.5}: We have the following:

1)ξ(x, 0) = 1/(1 − 2x).
2)ξ(x, −1) = 2x/(1 − 3x).
3)ξ(x, −2) = 2x(2 − x)/(1 − 5x + 2x^{2}).

\underline{Proof}: The number of coprime pairs (k, a) with k > a and l(k, a) = n is 2^{n−1}, (see [3],Corollary to Theorem 1), from which 1) follows. The sum of (k, a) over k, a with k > a and l(k, a) = n is (2 × 3^{n−1}, 2 × 3^{n−2}), (see [3], Theorem 2), from which 2) follows.

Let ξ(x, −2) = ∑ c_{n}x^{n}. We claim that for n ≥ 1, c_{n+2} = 5c_{n+1} − 2c_{n}. To see this, note that c_{n} = ∑ k^{2}, the sum being over all pairs of positive integers (k, a) with k and a coprime, k > a, and l(k, a) = n. If (k, a) is such a pair, so is (k, k −a). These 2 pairs give rise to 4 pairs: (k+a, a), (k+a, k), (2k−a, k−a), (2k−a, k), each of length n+1, and 8 pairs: (k+2a, a), (k+2a, k+a), (2k+a, k), (2k+a, k+a), (3k− 2a, k − a), (3k − 2a, 2k − a), (3k − a, k), (3k − a, 2k − a), each of length n + 2. Thus c_{n+1} = ∑(k+a)^{2}+(2k−a)^{2} = ∑ 5k^{2}−2ka+2a^{2}, the sum over (k, a) with the same conditions as above; while c_{n+2} = ∑(k + 2a)^{2} + (2k − a)^{2} + (3k − a)^{2} + (3k − 2a)^{2} = ∑ 23k^{2} −10ka+10a^{2}, with the sum over (k, a) also with the same conditions. Thus c_{n+2} = 5c_{n+1} − 2c_{n} as claimed.

This shows that the coefficient of x^{n} in (1 − 5x + 2x^{2})ξ(x, −2) is 0 for n ≥ 3. Calculation then shows that (1 − 5x + 2x^{2})ξ(x, −2) = 4x − 2x^{2}, as claimed.

§4. Recursions:

Throughout this section a, b, c, d are assumed to be non-negative integers. If

n is an integer define d_{n}( \begin{matrix}a & b \\ c & d \end{matrix} ) to be the number of sequences M_{1}, M_{2}, …, M_{n}

with M_{i} ∈ S_{2} and ∏ M_{i} = ( \begin{matrix}a & b \\ c & d \end{matrix} ). If n ≤ 0 then this is defined to be 0. Define

P_{n−1}(S_{2}) to be the set of 2×2 matrices which can be written as a product ∏_{i=1}^{n} M_{i} with M_{i} ∈ S_{2}.

We record the effect of multiplying a matrix by an element of S_{2}:

\underline{Lemma 4.1}:

1) ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) · ( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}a & b \\ 0 & 0 \end{matrix} ) 1′) ( \begin{matrix}a & b \\ c & d \end{matrix} ) · ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) = ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} )

2) ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}0 & 0 \\ a & b \end{matrix} ) 2′) ( \begin{matrix}a & b \\ c & d \end{matrix} ) · ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}b & 0 \\ d & 0 \end{matrix} )

3) ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}a & b \\ a & b \end{matrix} ) 3′) ( \begin{matrix}a & b \\ c & d \end{matrix} ) · ( \begin{matrix}1 & 1 \\ 0 & 0 \end{matrix} ) = ( \begin{matrix}a + b & 0 \\ c + d & 0 \end{matrix} )

4) ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} )·( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}a & b \\ a + c & b + d \end{matrix} ) 4′) ( \begin{matrix}a & b \\ c & d \end{matrix} )·( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) = ( \begin{matrix}a + b & b \\ c + d & d \end{matrix} )

5) ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )·( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}a + c & b + d \\ a & b \end{matrix} ) 5′) ( \begin{matrix}a & b \\ c & d \end{matrix} )·( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}a + b & a \\ c + d & c \end{matrix} )

\underline{Lemma 4.2}:Suppose that d_{n} ( \begin{matrix}a & b \\ c & d \end{matrix} ) is non-zero. Then a ≥ b and c ≥ d. \underline{Proof}: This follows by induction using 4.1, 1)-5).

\underline{Lemma 4.3}: Assume that n ≥ 1. Suppose that d_{n}( \begin{matrix}a & 0 \\ c & d \end{matrix} ) is non-zero with a ≠ 0 and d ≠ 0. Then a = d = 1. We have

d_{n} ( \begin{matrix}1 & 0 \\ c & 1 \end{matrix} ) = \{ \begin{matrix}1, & if c = n \\ 0, & otherwise. \end{matrix}

\underline{Proof}: This is certainly true for n = 1. Assume that n ≥ 2. Write ( \begin{matrix}a & 0 \\ c & d \end{matrix} ) =

M_{1} · ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ), with ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ) ∈ P_{n−1}(S_{2}), and M_{1} ∈ S_{2}. By 4.1, we must have

M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ), a′ = a , b′ = 0, and d′ = d. By induction, a′ = d′ = 1, c′ = n − 1,

and d_{n−1} ( \begin{matrix}1 & 0 \\ c′ & 1 \end{matrix} ) = 1. Thus c = c′ + 1 = n and d_{n} ( \begin{matrix}1 & 0 \\ c & 1 \end{matrix} ) = 1.

\underline{Lemma 4.4}: d_{n} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = d_{n} ( \begin{matrix}c & d \\ a & b \end{matrix} ) for all n, a, b, c, d.

\underline{Proof}:This follows from the fact that the set S_{2} is left unchanged when the rows of all its matrices are interchanged.

Let D be the operator acting on a sequence {a_{n} : n ∈ ℤ} indexed by ℤ defined by Da_{n} := a_{n−1}. Denote the identity operator by I.

\underline{Lemma 4.5}: For all n, 1) If a > c then d_{n} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = Dd_{n} ( \begin{matrix}c & d \\ a − c & b − d \end{matrix} )

2) If c > a then d_{n} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = Dd_{n} ( \begin{matrix}a & b \\ c − a & d − b \end{matrix} ) .

\underline{Proof}: Write ( \begin{matrix}a & b \\ c & d \end{matrix} ) = M_{1} · ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ), with ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ) ∈ P_{n−1}(S_{2}), and M_{1} ∈

S_{2}. In case 1), by 4.1, we must have M_{1} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ), a′ = c , b′ = d, c′ = a − c, and d′ = b − d. In case 2), by 4.1, we must have M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ), a′ = a , b′ = b, c′ = c − a, and d′ = d − b. In either case the value of d_{n} is as stated.

\underline{Lemma 4.6}:Suppose that a > 1. Then

d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = D(2d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c≠0} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ))

.

\underline{Proof}: Write ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = M_{1} · ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ), with ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ) ∈ P_{n−1}(S_{2}), and M_{1} ∈

S_{2}. By 4.1, we must have either 1)M_{1} = ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ), a′ = a , b′ = 0, or 2)M_{1} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ), a′ = b′ = d′ = 0 and c′ = a. In case 1), we must also have d′ = 0 by

4.3. Thus d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = d_{n−1} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c} d_{n−1} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = 2d_{n−1} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) +

∑_{c≠0} d_{n−1} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ).

For n ∈ ℤ, define δ_{n} as follows:

δ_{n} = \{ \begin{matrix}1, & if n ≥ 1 \\ 0, & if n ≤ 0. \end{matrix}

\underline{Lemma 4.7}:For all n ∈ ℤ,

d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) = D(2d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c≠0} d_{n} ( \begin{matrix}1 & 0 \\ c & 0 \end{matrix} )) + δ_{n}.

\underline{Proof}: The proof is the same as for 4.5, except that in case 1) there is also the possibility that a′ = d′ = 1 , b′ = 0, and c′ = n − 1. This gives the extra +δ_{n} for n ≥ 2. The formula is easily checked directly for n = 1.

\underline{Lemma 4.8}:Suppose that a > 1. Then for all n ∈ ℤ,

d_{n} ( \begin{matrix}a & 0 \\ a & 0 \end{matrix} ) = D(3d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c≠0} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} )).

\underline{Proof}: Write ( \begin{matrix}a & 0 \\ a & 0 \end{matrix} ) = M_{1} · ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ), with ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ) ∈ P_{n−1}(S_{2}), and M_{1} ∈

S_{2}. By 4.1, we must have either 1)M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ), a′ = a , b′ = 0, or 2)M_{1} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) or ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) , and b′ = c′ = d′ = 0 and a′ = a. In case 1), we must also

have d′ = 0 by 4.3. Thus d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = 2d_{n−1} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c} d_{n−1} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) =

3d_{n−1} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c≠0} d_{n−1} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ).

\underline{Lemma 4.9}:For all n ∈ ℤ,

d_{n} ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) = D(3d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) + ∑_{c≠0} d_{n} ( \begin{matrix}1 & 0 \\ c & 0 \end{matrix} )) + δ_{n}.

\underline{Proof}: Repeat the proof of 4.7., using 4.8 instead of 4.5.

\underline{Lemma 4.10}:For all n, a ∈ ℤ,

d_{n} ( \begin{matrix}a & 0 \\ a & 0 \end{matrix} ) = (I + D)d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Proof}: By 4.6-4.9,

d_{n} ( \begin{matrix}a & 0 \\ a & 0 \end{matrix} ) − d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = d_{n−1} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Lemma 4.11}:Suppose that a > c > 0 and that the g.c.d. of a and c is d. For all n ∈ ℤ,

d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = D^{l(a,c)}d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

\underline{Proof}: By 4.4 and 4.5,

d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = \{ \begin{matrix}Dd_{n} ( \begin{matrix}a & 0 \\ a − c & 0 \end{matrix} ) , & if a > a − c \\ Dd_{n} ( \begin{matrix}a − c & 0 \\ a & 0 \end{matrix} ) , & if a < a − c \end{matrix}

The lemma follows using the definition of l(a, c) in 3.1.

\underline{Lemma 4.12}:Suppose that a > 0 and d|a. For all n ∈ ℤ,

∑_{\begin{matrix}d≤c≤a \\ (a,c)=d \end{matrix}} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

\underline{Proof}: By 4.11,

∑_{\begin{matrix}d≤c≤a \\ (a,c)=d \end{matrix}} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = ∑_{\begin{matrix}d≤c≤a \\ (a,c)=d \end{matrix}} D^{l(a,c)}d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

= f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

by 3.3. \underline{Lemma 4.13}: Suppose that a > 0 .For all n ∈ ℤ,

∑_{1≤c≤a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = ∑_{d|a} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

\underline{Proof}: By 4.11,

∑_{1≤c≤a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = ∑_{d|a} ∑_{d≤c≤a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} )

= ∑_{d|a} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

by 4.12. \underline{Lemma 4.14}: Suppose that a > 0 For all n, k ∈ ℤ with k ≥ 0,

∑_{ka+1≤c≤(k+1)a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = D^{k} ∑_{1≤c≤a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) .

\underline{Proof}:

∑_{ka+1≤c≤(k+1)a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = D ∑_{ka+1≤c≤(k+1)a} d_{n} ( \begin{matrix}a & 0 \\ c − a & 0 \end{matrix} )

= D ∑_{(k−1)a+1≤c≤ka} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} )

The result follows by induction. \underline{Lemma 4.15}: Assume that a > 0. For all n ∈ ℤ,

(I − D) ∑_{c≠0} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = ∑_{d|a} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

\underline{Proof}:

∑_{c≠0} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} ) = ∑_{k=0}^{∞} ∑_{ka+1≤c≤(k+1)a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} )

= ∑_{k=0}^{∞} D^{k} ∑_{1≤c≤a} d_{n} ( \begin{matrix}a & 0 \\ c & 0 \end{matrix} )

= ∑_{k=0}^{∞} D^{k} ∑_{d|a} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

The result follows upon multiplying both sides by I − D. \underline{Proposition 4.16}: Assume that a > 0. For all n ∈ ℤ,

(I − 4D + D^{2})d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = (D + D^{2}) ∑_{\begin{matrix}d|a \\ d≠a \end{matrix}} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Proof}: By 4.6 , 4.10 and 4.15,

(I − D)d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) = 2D(I − D)d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + D ∑_{d|a} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

= 2D(I − D)d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + (D + D^{2})d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} )

+ D ∑_{\begin{matrix}d|a \\ d≠a \end{matrix}} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

= (3D − D^{2})d_{n} ( \begin{matrix}a & 0 \\ 0 & 0 \end{matrix} ) + D ∑_{\begin{matrix}d|a \\ d≠a \end{matrix}} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

The result now follows from 4.10. \underline{Proposition 4.17}: Assume that a > 0. For all n ∈ ℤ,

(I − 4D + D^{2})d_{n} ( \begin{matrix}a & 0 \\ a & 0 \end{matrix} ) = (D + D^{2}) ∑_{\begin{matrix}d|a \\ d≠a \end{matrix}} f_{a/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

\underline{Proof}: This follows from 4.10 and 4.16. \underline{Proposition 4.18}: For all n ∈ ℤ,

(I − 4D + D^{2})d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) = \{ \begin{matrix}0, & if n ≠ 1 \\ 1, & if n = 1 \end{matrix}

\underline{Proof}: A computation similar to 4.16 gives

(I − 4D + D^{2})d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) = (I − D)δ_{n}

from which the result follows. \underline{Proposition 4.19}: For all n ∈ ℤ,

(I − 4D + D^{2})d_{n} ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) = \{ \begin{matrix}0, & if n ≠ 1, 2 \\ 1, & if n = 1, 2 \end{matrix}

\underline{Proof}:This time we have

(I − 4D + D^{2})d_{n} ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) = (I − D^{2})δ_{n}.

\underline{Lemma 4.20}:Assume that b > 0. For all n ∈ ℤ,

d_{n} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = \{ \begin{matrix}Dd_{n} ( \begin{matrix}a − b & b \\ c − d & d \end{matrix} ) , & if a − b > b \\ Dd_{n} ( \begin{matrix}b & a − b \\ d & c − d \end{matrix} ) , & if a − b < b \\ 2Dd_{n} ( \begin{matrix}b & d \\ b & d \end{matrix} ) , & if a − b = b and c − d = d \end{matrix}

\underline{Proof}: Write ( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ) · M_{n}, with ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ) ∈ P_{n−1}(S_{2}), and M_{n} ∈

S_{2}. By 4.1, we must have either 1) M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ), a′ = a − b , b′ = b, c′ = c − d,

and d′ = d, or 2) M_{n} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ), a′ = b , b′ = a − b, c′ = d, and d′ = c − d . Thus

d_{n} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = Dd_{n} ( \begin{matrix}a − b & b \\ c − d & d \end{matrix} ) + Dd_{n} ( \begin{matrix}b & a − b \\ d & c − d \end{matrix} ) .

If a − b > b, the second term on the right hand side is 0. If a − b < b, the first term on the right hand side is 0. If a − b = b and c − d = d, the two terms are equal. This proves the lemma.

\underline{Lemma 4.21}:Assume that a > b > 0 and that the g.c.d. of a and b is d. For all n ∈ ℤ,

d_{n} ( \begin{matrix}a & b \\ a & b \end{matrix} ) = 2D^{l(a,b)+1}d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} )

and

d_{n} ( \begin{matrix}a & b \\ 0 & 0 \end{matrix} ) = 2D^{l(a,b)+1}d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} )

\underline{Proof}: This follows from 4.20 and the definition of length in 3.1.

\underline{Lemma 4.22}: For all n ∈ ℤ,

∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ a & b \end{matrix} ) = ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

and

∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ 0 & 0 \end{matrix} ) = ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

\underline{Proof}:

∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ a & b \end{matrix} ) = ∑_{d|k} ∑_{\begin{matrix}a+b=k \\ (a,b)=d \end{matrix}} d_{n} ( \begin{matrix}a & b \\ a & b \end{matrix} )

= ∑_{\begin{matrix}d|k \\ d≠k/2,k \end{matrix}} ∑_{\begin{matrix}a+b=k \\ (a,b)=d \end{matrix}} 2D^{l(a,b)+1}d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) + Dd_{n} ( \begin{matrix}k/2 & 0 \\ k/2 & 0 \end{matrix} )

+ d_{n} ( \begin{matrix}k & 0 \\ k & 0 \end{matrix} )

= ∑_{\begin{matrix}d|k \\ d≠k/2,k \end{matrix}} ∑_{\begin{matrix}a+b=k \\ (a,b)=d \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) + f_{2}(D)d_{n} ( \begin{matrix}k/2 & 0 \\ k/2 & 0 \end{matrix} )

+ d_{n} ( \begin{matrix}k & 0 \\ k & 0 \end{matrix} ) (by 3.4)

= ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) + d_{n} ( \begin{matrix}k & 0 \\ k & 0 \end{matrix} )

= ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) .

The proof of the second statement is similar.

\underline{Lemma 4.23}: For all n ∈ ℤ,

∑_{b} d_{n} ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} ) = (I + D)d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + 2D ∑_{\begin{matrix}d|k \\ d≠0 \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Proof}: As in the proof of 4.13, using 4.21 we get

∑_{b≠0,k} d_{n} ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} ) = 2D ∑_{\begin{matrix}d|k \\ d≠0 \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

Since

d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + d_{n} ( \begin{matrix}k & k \\ 0 & 0 \end{matrix} ) = (I + D)d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) ,

the result is proved.

\underline{Lemma 4.24}: For all n ∈ ℤ,

(I − D) ∑_{c} d_{n} ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ) = (D + D^{2})d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + 2D^{2} ∑_{\begin{matrix}d|k \\ d≠0 \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Proof}: As in the proof of 4.15, using 4.21 we get

∑_{c≢0(modk)} d_{n} ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ) = ∑_{c≢0(modk)} d_{n} ( \begin{matrix}c & k \\ 0 & 0 \end{matrix} )

= ∑_{k+1≤c<k} ∑_{r=0}^{∞} D^{r}d_{n} ( \begin{matrix}c & k \\ 0 & 0 \end{matrix} )

= ∑_{1≤c<k} ∑_{r=0}^{∞} D^{r+1}d_{n} ( \begin{matrix}c & k \\ 0 & 0 \end{matrix} )

= ∑_{r=0}^{∞} 2D^{r+2} ∑_{\begin{matrix}d|k \\ d≠0 \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

On the other hand,

∑_{c≡0(modk)} d_{n} ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ) = ∑_{c≡0(modk)} d_{n} ( \begin{matrix}c & k \\ 0 & 0 \end{matrix} )

= (D + ∑_{r=2}^{∞} 2D^{r})d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} )

= (∑_{r=1}^{∞} D^{r} + ∑_{r=2}^{∞} D^{r})d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} )

The result follows upon multiplying both sides by I − D.

§5. More recursions:

If n and k are integers and M ∈ S_{2}, define d_{n}(M, k) to be the number of sequences M_{1}, M_{2}, …, M_{n} with M_{i} ∈ S_{2} , M_{1} = M, and T r(∏_{i=1}^{n} M_{i}) = k.

\underline{Lemma 5.1}: For all n, k ∈ ℤ, 1) If A = d_{n} ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) then

d_{n}(A, k) = ∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ a & b \end{matrix} ) − 2D ∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ 0 & 0 \end{matrix} )

2) If A = d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) then

d_{n}(A, k) = (I − D) ∑_{b} d_{n} ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} )

3) If A = d_{n} ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) then

d_{n}(A, k) = (I − D) ∑_{c} d_{n} ( \begin{matrix}0 & 0 \\ c & k \end{matrix} )

\underline{Proof}: 1)A matrix equal to ∏_{i=1}^{n} M_{i} with M_{i} ∈ S_{2}, trace equal to k and M_{1} = A is of the form ( \begin{matrix}a & b \\ a & b \end{matrix} ) with a+b = k. On the other hand, if ( \begin{matrix}a & b \\ a & b \end{matrix} ) = ∏_{i=1}^{n} M_{i} with

M_{i} ∈ S_{2} then either 1)M_{1} = A or 2) M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) or ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) and ∏_{i=2}^{n} M_{i} =

( \begin{matrix}a & b \\ 0 & 0 \end{matrix} ). Thus

∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ a & b \end{matrix} ) = d_{n}(A, k) + 2D ∑_{a+b=k} d_{n} ( \begin{matrix}a & b \\ 0 & 0 \end{matrix} ) .

This proves 1).

2) A matrix equal to ∏_{i=1}^{n} M_{i} with M_{i} ∈ S_{2} , trace equal to k and M_{1} = A is of the form ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} ) . On the other hand, if ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} ) = ∏_{i=1}^{n} M_{i} with M_{i} ∈ S_{2} then

either 1)M_{1} = A or 2) M_{1} = d_{n} ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) and ∏_{i=2}^{n} M_{i} = ( \begin{matrix}0 & 0 \\ k & b \end{matrix} ). Thus

∑_{b} d_{n} ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} ) = d_{n}(A, k) + D ∑_{b} d_{n} ( \begin{matrix}0 & 0 \\ k & b \end{matrix} )

= d_{n}(A, k) + D ∑_{b} d_{n} ( \begin{matrix}k & b \\ 0 & 0 \end{matrix} ) .

This proves 2).

3) A matrix equal to ∏_{i=1}^{n} M_{i} with M_{i} ∈ S_{2} , trace equal to k and M_{1} = A is of

the form ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ) . On the other hand, if ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ) = ∏_{i=1}^{n} M_{i} with M_{i} ∈ S_{2} then

either 1)M_{1} = A or 2) M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) and ∏_{i=2}^{n} M_{i} = ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ). Thus

∑_{c} d_{n} ( \begin{matrix}0 & 0 \\ c & k \end{matrix} ) = d_{n}(A, k) + D ∑_{c} d_{n} ( \begin{matrix}0 & 0 \\ c & k \end{matrix} )

This proves 3).

\underline{Proposition 5.2}: For all n, k ∈ ℤ, 1) If A = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) then

d_{n}(A, k) = (I − D) ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

2) If A = ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) then

d_{n}(A, k) = (I − D^{2})d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + 2D(I − D) ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

3) If A = ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) then

d_{n}(A, k) = D(I + D)d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + 2D^{2} ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Proof}: 1) By part 1) of 5.1 and 4.22

d_{n}(A, k) = ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ d & 0 \end{matrix} ) − 2D ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} )

= (I − D) ∑_{d|k} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

2) This follows from 5.1 part 2) and 4.23.

3) This follows from 5.1 part 3) and 4.24.

For n, k ∈ ℤ define

d_{n}^{1}(k) = d_{n}(( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) , k)

and

d_{n}^{2}(k) = d_{n}(( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) , k) + d_{n}(( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) , k) + d_{n}(( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) , k).

\underline{Proposition 5.3}: For all n, k ∈ ℤ with k ≥ 2,

D(I + D)d_{n}^{1}(k) = (I − D)^{2}(I − 2D)d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} )

and

Dd_{n}^{2}(k) = (I − D)^{2}d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) .

On the other hand,

d_{n}^{1}(1) = (I − D)d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} )

and

d_{n}^{2}(1) = 2d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) .

\underline{Proof}: The values for k = 1 follow from 5.2. Suppose that k ≥ 2. By 5.2,

d_{n}^{2}(k) = 2d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + (I + D) ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) .

Thus, using 4.16, we get

Dd_{n}^{2}(k) = 2Dd_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + (D + D^{2}) ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} )

= 2Dd_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) + ((I − 4D + D^{2})d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} )

= (I − D)^{2}d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} )

The formula for d_{n}^{1}(k) is proved similarly.

§6. Generating functions: We will now give generating functions for the multiplicities of decomposition numbers. \underline{Proposition 6.1}:

∑_{k,n} d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s} = \frac{x}{(1 − 4x + x^{2} − (x + x^{2})ξ(x, s))}

\underline{Proof}: We have

(1 − 4x + x^{2}) ∑_{n} d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) x^{n} = (I − 4D + D^{2}) ∑_{n} d_{n} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) x^{n}
= x

by 4.18. On the other hand,

(1 − 4x + x^{2}) ∑_{\begin{matrix}n,k \\ k≥2 \end{matrix}} d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s} = (I − 4D + D^{2}) ∑_{\begin{matrix}n,k \\ k≥2 \end{matrix}} d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}

= (D + D^{2}) ∑_{n} ∑_{k≥2} ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}

by 4.17. We also have

(x + x^{2})ξ(x, s) ∑_{k,n} d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s} = (x + x^{2}) ∑_{k≥2} f_{k}(x)k^{−s} ∑_{k,n} d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}

= (D + D^{2}) ∑_{n} ∑_{k≥2} ∑_{\begin{matrix}d|k \\ d≠k \end{matrix}} f_{k/d}(D)d_{n} ( \begin{matrix}d & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}.

Thus

(1 − 4x + x^{2} − (x + x^{2})ξ(x, s)) ∑_{k,n} d_{n} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s} = x,

which gives us the result.

For i = 1, 2, define g_{i}(x, s) = ∑_{k,n} d_{n}^{i}(k)x^{n}k^{−s}. \underline{Proposition 6.2}:

g_{1}(x, s) = \frac{(1 − x)^{2}(1 − 2x)}{(1 + x)(1 − 4x + x^{2} − (x + x^{2})ξ(x, s))} − \frac{1 − x}{1 + x}

while

g_{2}(x, s) = \frac{(1 − x)^{2}}{1 − 4x + x^{2} − (x + x^{2})ξ(x, s)} − 1.

\underline{Proof}: We have

g_{1}(x, s) = ∑_{n} d_{n}^{1}(1)x^{n} + ∑_{n} ∑_{k≥2} d_{n}^{1}(k)x^{n}k^{−s}

= (1 − x) ∑_{n} d_{n}^{1} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) x^{n} + \frac{(1 − x)^{2}(1 − 2x)}{x(1 + x)} ∑_{n} ∑_{k≥2} d_{n}^{1} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}

= \frac{x(1 − x)}{1 − 4x + x^{2}} + \frac{(1 − x)^{2}(1 − 2x)}{x(1 + x)} ∑_{n} ∑_{k≥1} d_{n}^{1} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}

− \frac{(1 − x)^{2}(1 − 2x)}{x(1 + x)} ∑_{n} d_{n}^{1} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) x^{n}

= \frac{x(1 − x)}{1 − 4x + x^{2}} + \frac{(1 − x)^{2}(1 − 2x)}{(1 + x)(1 − 4x + x^{2} − (x + x^{2})ξ(x, s))} − \frac{(1 − x)^{2}(1 − 2x)}{(1 + x)(1 − 4x + x^{2})}

which simplifies to the formula stated. Also,

g_{2}(x, s) = ∑_{n} d_{n}^{2}(1)x^{n} + ∑_{n} ∑_{k≥2} d_{n}^{2}(k)x^{n}k^{−s}

= 2 ∑_{n} d_{n}^{2} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) x^{n} + \frac{(1 − x)^{2}}{x} ∑_{n} ∑_{k≥2} d_{n}^{2} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s}

= \frac{2x}{1 − 4x + x^{2}} + \frac{1 − x^{2}}{x} ∑_{n} ∑_{k≥1} d_{n}^{2} ( \begin{matrix}k & 0 \\ 0 & 0 \end{matrix} ) x^{n}k^{−s} − \frac{(1 − x)^{2}}{x} ∑_{n} d_{n}^{2} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) x^{n}

= \frac{2x}{1 − 4x + x^{2}} + \frac{(1 − x)^{2}}{1 − 4x + x^{2} − (x + x^{2})ξ(x, s)} − \frac{(1 − x)^{2}}{1 − 4x + x^{2}}

which again simplifies to the formula stated.

If n and k are integers and define d̄_{n}^{1}(k) to be the number of sequences M_{1}, M_{2}, …, M_{n} with M_{i} ∈ S̄_{2} , M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) and T r(∏_{i=1}^{n} M_{i}) = k. Define d̄_{n}^{2}(k) to be the num-

ber of sequences M_{1}, M_{2}, …, M_{n} with M_{i} ∈ S̄_{2} , M_{1} = ( \begin{matrix}1 & 0 \\ 1 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ), or

( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) and T r(∏_{i=1}^{n} M_{i}) = k.

For i = 1, 2, define ḡ_{i}(x, s) = ∑_{k,n} d̄_{n}^{2}(k)x^{n}k^{−s}. \underline{Proposition 6.3}: For i = 1, 2 , ḡ_{i}(x, s) = g_{i}(x/(1 − x), s). \underline{Proof}: There are \binom{n−1}{j} choices of where to put exactly j identity matrices among M_{1}, M_{2}, …, M_{n} (M_{1} is not the identity matrix). Thus

d̄_{n}^{i}(k) = ∑_{j=0}^{n−1} \binom{n − 1}{j}d_{n−j}^{i}(k).

We therefore have

ḡ_{i}(x, s) = ∑_{k,n} d̄_{n}^{2}(k)x^{n}k^{−s}

= ∑_{k,n} ∑_{j=0}^{n−1} \binom{n − 1}{j}d_{n−j}^{i}(k)x^{n}k^{−s}

= ∑_{k,n} ∑_{j=0}^{∞} \binom{n − 1 + j}{j}d_{n}^{i}(k)x^{n+j}k^{−s}

= ∑_{k,n} d_{n}^{i}(k) (\frac{x}{1 − x})^{n} k^{−s}

where we are using the identity

(\frac{1}{1 − x})^{n} = ∑_{j=0}^{∞} \binom{n − 1 + j}{j}x^{j}.

This proves the proposition.

We can now prove our main theorem, stated in section 1. \underline{Proof of Main Theorem}: By 2.2, d̃_{n}^{i}(k) = 3×2^{n}d̄_{n}^{i}(k). Thus g̃_{i}(x, s) = 3ḡ_{i}(2x, s). The theorem thus follows from 6.2 and 6.3.

§7. Cartan Invariants: Our results allow us to compute certain Cartan invariants.

If Φ_{1} and Φ_{2} are projective indecomposable characters, let c(Φ_{1}, Φ_{2}) be the Cartan invariant corresponding to Φ_{1} and Φ_{2}, i.e., the number of times the irreducible character corresponding to Φ_{1} occurs in Φ_{2}. Compare the following with Theorems 5.2 and 5.3 in [1]. Compare also with the results in [2] and [4]. \underline{Theorem 7.1:} 1) Suppose that λ is in the top W_{a,p} - alcove of SL_{3}(p) and sufficiently deep in the interior of a W̃_{a,p} - alcove. The Cartan invariant c(Φ_{λ,n}, Φ_{λ,n}) of SL_{3}(p^{n}) or SU_{3}(p^{n}) is equal to the coefficient of x^{n} in the series expansion of 6x(1 − 2x)/(48x^{2} − 18x + 1) .

2)Suppose λ is in the bottom alcove of SL_{3}(p) and sufficiently deep in the interior of a W̃_{a,p} - alcove. Then the Cartan invariant c(Φ_{λ,n}, Φ_{λ,n}) of SL_{3}(p^{n}) or SU_{3}(p^{n}) is equal to the coefficient of x^{n} in the series expansion of 12x(1−4x)/(48x^{2} −18x+1). \underline{Proof}: We have c(Φ_{λ,n}, Φ_{λ,n}) = ∑_{k,n} d̃_{n}^{i}(k)x^{n}k^{2} = g̃_{i}(x, −2) = 3g_{i}(2x/(1 − 2x), −2), where i = 1 if λ is in the top alcove, and i = 2 if λ is in the bottom alcove. Using 6.2 and 3.5, part 3), we get the formula stated.

References:

[1] L. CHASTKOFSKY, Decomposition Numbers of Chevalley Groups, preprint [2] L. CHASTKOFSKY, On the Cartan invariants of a Chevalley group over

GF (p^{n}), J. Algebra 150 (1992), 388-401.

[3] L. CHASTKOFSKY, The Subtractive Euclidean Algorithm and Fibonacci Numbers, to appear in fibonacci Quarterly

[4.] YE JIA-CHEN, On the first Cartan invariant of the groups SL(3, p^{n}) and SU(3, p^{n}), in ”Lecture Notes in Mathematics”, Vol. 1185, pp.388-400, Springer-Verlag, New York/Berlin, 1986.