text:
# Untitled Document

Some representations of nongraded Lie algebras of generalized Witt type111AMS Subject Classification - Primary: 17B10, 17B65, 17B66, 17B68, 17B70
Supported by a grant from National Educational Department of China.

(appeared in J.Alg. 246 (2001), 721-738)

Yucai Su222Email: ycsu@sjtu.edu.cn

Department of Mathematics, Shanghai Jiaotong University, Shanghai 200030, China

and

Jianhua Zhou333Email: jhzhou@seu.edu.cn

Department of Applied Mathematics, Southeast University Nanjing 210096, China

In a paper by Xu, some simple Lie algebras of generalized Cartan type were constructed, using the mixtures of grading operators and down-grading operators. Among them, are the simple Lie algebras of generalized Witt type, which are in general nongraded and have no torus. In this paper, some representations of these simple Lie algebras of generalized Witt type are presented.

1. INTRODUCTION

The four well-known series of infinite dimensional simple Lie algebras of Cartan type have played important roles in the structure theory of Lie algebras. Generalizations of the simple Lie algebras of Witt type have been obtained by Kawamoto \[Kaw\], Dokovic and Zhao \[DZ1,DZ2\], Xu \[X1\] and Zhao \[Z2\]. Passman \[P\] studied the Lie algebras $`𝒜𝒟=𝒜𝒟`$ of generalized Witt type constructed from the pair of a commutative associative algebra $`𝒜`$ with an identity element and its commutative derivation subalgebra $`𝒟`$ over a field $`IF`$ of arbitrary characteristic. Xu \[X1\] studied some of these simple Lie algebras of generalized Witt type and other generalized Cartan types Lie algebras, based on the pairs of the tensor algebra of the group algebra of an additive subgroup of $`IF^n`$ with the polynomial algebra in several variables and the subalgebra of commuting locally finite derivations. Su, Xu and Zhang \[SXZ\], Su and Xu \[SX\] determined the structure spaces of the generalized simple Lie algebras of Witt type and of special type constructed in \[X1\]. Su and Zhao \[SZ2\] determined the second cohomology group and gave some representations of some Lie algebras of generalized Witt type.

The Lie algebras associated with vertex algebras, the Lie algebras generated by conformal algebras are in general nongraded and nonlinear Lie algebras \[BXZ,X2\]. The algebraic aspects of quantum field theory are the representation theory of the Lie algebras generated by conformal algebras \[K\]. However, not much work has been known on the representation theory of the nongraded and nonlinear Lie algebras. Su and Zhao \[SZ3\] defined the Lie algebras of Weyl type $`𝒜[𝒟]=𝒜IF[𝒟]`$, which are in general nongraded and nonlinear, where $`𝒜`$ is a commutative associative algebra with an identity element over a field $`IF`$ of arbitrary characteristic, and $`IF[𝒟]`$ is the polynomial algebra of a commutative derivation subalgebra $`𝒟`$ of $`𝒜`$. They also determined in \[SZ4\] the isomorphism classes and automorphism groups of the associative and Lie algebras of Weyl type $`𝒜[𝒟]`$, where $`IF`$ is a field of characteristic zero, $`𝒟`$ is a commuting subalgebra of locally finite but not locally nilpotent derivations of $`𝒜`$.

In this paper, we shall consider some representations of the (in general, nongraded) Lie algebras of generalized Witt type defined by Xu \[X1\] below.

Denote by $`IF`$ an algebraically closed field of characteristic zero. Let $`\mathrm{}_1,\mathrm{}_2,\mathrm{}_3`$ be three nonnegative integers such that $`\mathrm{}=\mathrm{}_1+\mathrm{}_2+\mathrm{}_3>0`$. For any $`m,nZZ`$, we use the notation

$$\overline{m,n}=\{m,m+1,\mathrm{},n\}\text{ if }mn,\text{ or }\overline{m,n}=\mathrm{}\text{ if }m>n.$$
$`(1.1)`$
Take a nondegenerate additive subgroup $`\mathrm{\Gamma }`$ of $`IF^{\mathrm{}_2+\mathrm{}_3}`$ in the sense that $`\mathrm{\Gamma }`$ contains an $`IF`$-basis of $`IF^{\mathrm{}_2+\mathrm{}_3}`$. For convenience, elements $`\alpha \mathrm{\Gamma }`$ will be written as

$$\alpha =(\alpha _1,\alpha _2,\mathrm{},\alpha _{\mathrm{}})\text{ with }\alpha _1=\alpha _2=\mathrm{}=\alpha _\mathrm{}_1=0.$$
$`(1.2)`$
For any $`iZZ_+=\{0,1,2,\mathrm{}\}`$, $`p\overline{1,\mathrm{}}`$, we denote

$$i_{[p]}=(0,\mathrm{},0,{}_{i}{}^{}{}_{}{}^{^p},0,\mathrm{},0)ZZ_+^{\mathrm{}}.$$
$`(1.3)`$
Elements in $`ZZ_+^{\mathrm{}}`$ will be denoted by

$$\stackrel{}{i}=(i_1,i_2,\mathrm{},i_{\mathrm{}}),$$
$`(1.4)`$
while elements in $`ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$ will be denoted by (1.4) with $`i_{\mathrm{}_1+\mathrm{}_2+1}=\mathrm{}=i_\mathrm{}1=i_{\mathrm{}}=0`$.

Let $`𝒜`$ be the semi-group algebra $`IF[\mathrm{\Gamma }\times ZZ_+^{\mathrm{}_1+\mathrm{}_2}]`$ with $`IF`$-basis $`\{x^\alpha t^\stackrel{}{i}|(\alpha ,\stackrel{}{i})\mathrm{\Gamma }\times ZZ_+^{\mathrm{}_1+\mathrm{}_2}\}`$ and the algebraic operation

$$x^\alpha t^\stackrel{}{i}x^\beta t^\stackrel{}{j}=x^{\alpha +\beta }t^{\stackrel{}{i}+\stackrel{}{j}}$$
$`(1.5)`$
for $`(\alpha ,\stackrel{}{i}),(\beta ,\stackrel{}{j})\mathrm{\Gamma }\times ZZ_+^{\mathrm{}_1+\mathrm{}_2}.`$ Denote the identity element $`x^0t^0`$ by 1. Define the linear transformations (derivations) $`\{_1^{},_2^{},\mathrm{},_{\mathrm{}_1+\mathrm{}_2}^{},_{\mathrm{}_1+1}^+,_{\mathrm{}_1+2}^+,\mathrm{},_{\mathrm{}}^+\}`$ on $`𝒜`$ by

$$_p^{}(x^\alpha t^\stackrel{}{i})=i_px^\alpha t^{\stackrel{}{i}1_{[p]}},_q^+(x^\alpha t^\stackrel{}{i})=\alpha _qx^\alpha t^\stackrel{}{i},$$
$`(1.6)`$
for all $`p\overline{1,\mathrm{}_1+\mathrm{}_2},q\overline{\mathrm{}_1+1,\mathrm{}}`$, where in the first equation, if $`\stackrel{}{i}1_{[p]}ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$ then $`i_p=0`$ and the right-hand side is treated as zero. The operators $`_p^{}`$ are called down-grading operators and $`_q^+`$ are grading operators. Set

$$_p=_p^{},_q=_q^{}+_q^+,_r=_r^+,$$
$`(1.7)`$
for $`p\overline{1,\mathrm{}_1},q\overline{\mathrm{}_1+1,\mathrm{}_1+\mathrm{}_2},r\overline{\mathrm{}_1+\mathrm{}_2+1,\mathrm{}}.`$ Observe that $`_p`$ is locally nilpotent if $`p\overline{1,\mathrm{}_1}`$; locally finite if $`p\overline{\mathrm{}_1+1,\mathrm{}_1+\mathrm{}_2}`$; semi-simple if $`p\overline{\mathrm{}_1+\mathrm{}_2+1,\mathrm{}}`$. Set $`𝒟=_{p=1}^{\mathrm{}}IF_p`$.

It is proved in \[SXZ\] that the pairs $`(𝒜,𝒟)`$ constructed above for different parameters $`(\mathrm{}_1,\mathrm{}_2,\mathrm{}_3;\mathrm{\Gamma })`$ enumerate all the pairs $`(𝒜,𝒟)`$ of a commutative associative algebra $`𝒜`$ with an identity element and its finite-dimensional commutative locally-finite derivation subalgebra $`𝒟`$ such that $`𝒜`$ is $`𝒟`$-simple and $`_𝒟\mathrm{ker}=IF.`$

The $`IF`$-vector space

$$W=W(\mathrm{}_1,\mathrm{}_2,\mathrm{}_3,\mathrm{\Gamma })=𝒜𝒟=\underset{p=1}{\overset{\mathrm{}}{}}𝒜_p,$$
$`(1.8)`$
forms a Lie algebra under the usual bracket

$$[x^\alpha t^\stackrel{}{i}_p,x^\beta t^\stackrel{}{j}_q]=x^{\alpha +\beta }t^{\stackrel{}{i}+\stackrel{}{j}}(\beta _p_q\alpha _q_p)+j_px^{\alpha +\beta }t^{\stackrel{}{i}+\stackrel{}{j}1_{[p]}}_qi_qx^{\alpha +\beta }t^{\stackrel{}{i}+\stackrel{}{j}1_{[q]}}_p,$$
$`(1.9)`$
for $`(\alpha ,\stackrel{}{i}),(\beta ,\stackrel{}{j})\mathrm{\Gamma }\times ZZ_+^{\mathrm{}_1+\mathrm{}_2},p,q\overline{1,\mathrm{}},`$ which is called a Lie Algebra of generalized Witt type constructed by Xu \[X1\]. In particular, $`W(\mathrm{},0,0,\{0\})`$ is a classical Witt algebra $`W_{\mathrm{}}^+`$ over the polynomial ring $`IF[t_1,\mathrm{},t_{\mathrm{}}]`$, and $`W(0,0,\mathrm{},ZZ^{\mathrm{}})`$ is a classical Witt algebra $`W_{\mathrm{}}`$ over the Laurent polynomial ring $`IF[x_1^{\pm 1},\mathrm{},x_{\mathrm{}}^{\pm 1}]`$, and more general, $`W(0,0,\mathrm{},\mathrm{\Gamma })`$ is a generalized Witt algebra considered in \[Z1\] and $`W(\mathrm{}_1,0,\mathrm{}_3,\mathrm{\Gamma })`$ is a generalized Witt algebra considered in \[DZ1,DZ2\]. Also, observe that $`W_1`$ is the classical centerless Virasoro algebra, $`W(0,0,1,\mathrm{\Gamma })`$ is a centerless higher rank Virasoro algebra (if $`\mathrm{\Gamma }IF`$ is finitely generated) \[PZ\] or a centerless generalized Virasoro algebra \[SZ1\] and $`W(0,1,0,\mathrm{\Gamma })`$ is a nongraded centerless Virasoro algebra \[SL\].

Eswara Rao \[E1,E2\] constructed some representations of $`W_{\mathrm{}}^+`$, Zhao \[Z1\] classified
$`W(0,0,\mathrm{},\mathrm{\Gamma })`$-modules with weight multiplicity 1. There is much more work on the Virasoro algebra and generalized Virasoro algebras. Mathieu \[M\] classified Harish-Chandra modules over the Virasoro algebra with a partial result also obtained in \[S1\]. Su generalized Mathieu’s result to super-Virasoro algebras and to higher rank Virasoro and super-Virasoro algebras \[S2,S3,S4\].

Since $`W(\mathrm{}_1,\mathrm{}_2,\mathrm{}_3,\mathrm{\Gamma })`$ in general does not have a torus, there is no concept of weight modules. However, motivated by \[SL\], we shall be able to consider the so-called generalized weight modules in Section 2 and give a classification of generalized weight modules with weight multiplicity 1 in Section 3. Our main result is Theorem 2.3.

Finally, we shall remark that our classification also applies to an arbitrary field of
characteristic zero as in Section 5 of \[Z1\].

2. PRELIMINARY AND MAIN RESULT

The Lie algebra $`W=W(\mathrm{}_1,\mathrm{}_2,\mathrm{}_3,\mathrm{\Gamma })`$ is in general nongraded in the sense that it can not be graded so that all homogeneous spaces are finite dimensional. Since $`W`$ in general does not contain a toral subalgebra, there is no concept of weight modules. However, we shall be able to consider the modules defined below.

A linear transformation $`T`$ of a $`IF`$-vector space $`V`$ is called locally finite if

$$\mathrm{dim}(\mathrm{span}_{IF}\{T^n(v)|nZZ_+\})<\mathrm{},$$
$`(2.1)`$
for all $`vV`$. $`T`$ is called semi-simple if there exists a $`IF`$-basis of $`\mathrm{span}_{IF}\{T^n(v)|nZZ_+\}`$ consisting of eigenvectors of $`T`$ for all $`vV`$; locally nilpotent if for any $`vV`$, there exists $`nZZ_+`$ (may depend on $`v`$) such that $`T^n(v)=0`$. A subspace $`U`$ of $`End(V)`$ is called locally finite or locally nilpotent if every element of $`U`$ is locally finite or locally nilpotent on $`V`$ respectively.

Denote

$$𝒟_1=\underset{p=1}{\overset{\mathrm{}_1}{}}IF_p,𝒟_2=\underset{p=\mathrm{}_1+1}{\overset{\mathrm{}_1+\mathrm{}_2}{}}IF_p,𝒟_3=\underset{p=\mathrm{}_1+\mathrm{}_2+1}{\overset{\mathrm{}}{}}IF_p.$$
$`(2.2)`$
For convenience, an element $`\beta IF^{\mathrm{}_2+\mathrm{}_3}`$ will be denoted as in (1.2) by $`\beta =(\beta _1,\beta _2,\mathrm{},\beta _{\mathrm{}})`$ with $`\beta _1=\beta _2=\mathrm{}=\beta _\mathrm{}_1=0`$. Let $`=_{p=1}^{\mathrm{}}a_p_p𝒟`$, we define

$$,\beta =\beta ()=\underset{p=\mathrm{}_1+1}{\overset{\mathrm{}}{}}a_p\beta _p.$$
$`(2.3)`$
By (1.6), (1.7), we see that $`\mathrm{ad}𝒟_1`$ is locally nilpotent and $`\mathrm{ad}𝒟`$ is locally finite on $`W`$. Thus, we can consider $`W`$-modules $`V`$ such that $`𝒟_1`$ and $`𝒟`$ act respectively locally nilpotently and locally finitely on $`V`$. For such a module $`V`$, we have

$$V=\underset{\beta IF^{\mathrm{}_2+\mathrm{}_3}}{}V_\beta ,V_\beta =\{vV|(\beta ())^n(v)=0\text{ for }𝒟\text{ and some }nZZ_+\}.$$
$`(2.4)`$
Let $`\beta IF^{\mathrm{}_2+\mathrm{}_3}`$. We set

$$V_\beta ^{(n)}=\{vV_\beta |(\beta ())^{n+1}(v)=0\text{ for }𝒟\},$$
$`(2.5)`$
for $`n0`$; and set

$$\overline{V}_\beta ^{(0)}=V_\beta ^{(0)},\overline{V}_\beta ^{(n)}=V_\beta ^{(n)}/V_\beta ^{(n1)},$$
$`(2.6)`$
for $`n1`$. Clearly,

$$V_\beta =\underset{nZZ_+}{}V_\beta ^{(n)}\text{ and }V_\beta \{0\}V_\beta ^{(0)}\{0\}.$$
$`(2.7)`$
For $`n0`$, we set

$$V^{(n)}=\underset{\beta IF^{\mathrm{}_2+\mathrm{}_3}}{}V_\beta ^{(n)},\overline{V}^{(n)}=\underset{\beta IF^{\mathrm{}_2+\mathrm{}_3}}{}\overline{V}_\beta ^{(n)}.$$
$`(2.8)`$
The above discussion leads us to the following definition.

Definition 2.1. A module $`V`$ over $`W`$ is called a generalized weight module if $`V`$ has a decomposition (2.4). For $`\beta IF^{\mathrm{}_2+\mathrm{}_3}`$, if $`V_\beta \{0\}`$, then $`V_\beta `$ is called the generalized weight space with weight $`\beta `$ and $`V_\beta ^{(0)}`$ is called the weight space with weight $`\beta `$. For an indecomposable generalized weight module $`V`$ over $`W`$, it is called a module of the intermediate series if $`\mathrm{dim}V_\beta ^{(0)}1`$ for all $`\beta IF^{\mathrm{}_2+\mathrm{}_3}`$; it is called a uniformly bounded module if there exists a nonnegative integer $`N`$ such that $`\mathrm{dim}V_\beta ^{(0)}N`$ for all $`\beta IF^{\mathrm{}_2+\mathrm{}_3}`$.

The aim of this paper is to classify all modules of the intermediate series over $`W`$. We shall assume that $`\mathrm{}_1+\mathrm{}_21`$ since the case for $`\mathrm{}_1+\mathrm{}_2=0`$ has been considered by Zhao \[Z1\]. We shall also assume that $`\mathrm{}_2+\mathrm{}_31`$ since $`W`$ is a classical Witt algebra if $`\mathrm{}_2+\mathrm{}_3=0`$. Note that $`W`$ is a centerless nongraded Virasoro algebra considered in \[SL\] if $`\mathrm{}=\mathrm{}_2=1`$. For convenience to the reader, we state below the main classification theorem in \[Z1\].

Theorem 2.2. (1) A module of the intermediate series over $`W(0,0,\mathrm{},\mathrm{\Gamma })`$ with $`\mathrm{}2`$ is a quotient module of $`A_{\alpha ,b},A(\beta )`$ or $`B(\beta )`$ for some suitable $`\alpha ,\beta IF^{\mathrm{}},bIF`$, where $`A_{\alpha ,b},A(\beta ),B(\beta )`$ all have $`IF`$-basis $`\{v_\mu |\mu \mathrm{\Gamma }\}`$ with the following actions:

$$\begin{array}{cc}A_{\alpha ,b}:& (x^\mu )v_\nu =,\alpha +\nu +b\mu v_{\mu +\nu },\\ A(\beta ):& (x^\mu )v_\nu =,\nu v_{\mu +\nu },\nu ,\mu +\nu 0,(x^\mu )v_\mu =0,(x^\mu )v_0=,\mu +\beta v_\mu ,\\ B(\beta ):& (x^\mu )v_\nu =,\mu +\nu v_{\mu +\nu },\nu ,\mu +\nu 0,(x^\mu )v_0=0,(x^\mu )v_\mu =,\mu +\beta v_0,\end{array}$$
$`\begin{array}{c}(2.9)\\ (2.10)\\ (2.11)\end{array}`$
for $`\mu ,\nu \mathrm{\Gamma },𝒟`$.

(2) $`A_{\alpha ,b}`$ is simple if and only if $`\alpha \mathrm{\Gamma }`$ or $`b0,1`$.

(3) each of $`A_{0,0},A_{0,1},A(\beta ),B(\beta )`$ has two composition factors: one is 1-dimensional (trivial) and the other is simple. The simple ones are denoted respectively by $`A_{0,0}^{},A_{0,1}^{},A^{}(\beta ),B^{}(\beta )`$. Then $`A_{0,1}^{},A^{}(\beta )`$ are simple submodules spanned by all basis element except $`v_0`$. $`A_{0,0}^{},B^{}(\beta )`$ are simple quotient modules modulo the trivial submodule spanned by $`v_0`$. We have $`A_{0,0}^{}A^{}(\beta ),A_{0,1}^{}B^{}(\beta )`$.

In this paper, we shall use the convention that if a notation which is not defined but techniquely appears in an expression, we always treat it as zero; for example, in the following theorem, we treat $`v_{\mu ,\stackrel{}{i}}`$ as zero if $`\stackrel{}{i}ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$.

The main result of this paper is the following theorem.

Theorem 2.3. (1) Suppose $`\mathrm{}_1+\mathrm{}_21,\mathrm{}_2+\mathrm{}_31`$. A module $`V`$ of the intermediate series over $`W(\mathrm{}_1,\mathrm{}_2,\mathrm{}_3,\mathrm{\Gamma })`$ is a subquotient module of $`A_{\alpha ,b}`$ for some suitable $`\alpha IF^{\mathrm{}_2+\mathrm{}_3},bIF`$, where $`A_{\alpha ,b}`$ is a module with $`IF`$-basis $`\{v_{\mu ,\stackrel{}{i}}|\mu \mathrm{\Gamma },\stackrel{}{i}ZZ_+^{\mathrm{}_1+\mathrm{}_2}\}`$ and the following action

$$A_{\alpha ,b}:(x^\mu t^\stackrel{}{i}_p)v_{\nu ,\stackrel{}{j}}=(\alpha _p+\nu _p+b\mu _p)v_{\mu +\nu ,\stackrel{}{i}+\stackrel{}{j}}+(j_p+bi_p)v_{\mu +\nu ,\stackrel{}{i}+\stackrel{}{j}1_{[p]}},$$
$`(2.12)`$
for $`\mu ,\nu \mathrm{\Gamma },\stackrel{}{i},\stackrel{}{j}ZZ_+^{\mathrm{}_1+\mathrm{}_2},p\overline{1,\mathrm{}}`$, where if $`i_p+j_p1<0`$ then $`i_p=j_p=0`$ and so $`j_p+bi_p=0`$ thus the second term of the right-hand side does not occur.

(2) $`A_{\alpha ,b}`$ is simple if and only if $`\alpha \mathrm{\Gamma }`$ or $`b0`$.

(3) $`A_{0,0}`$ has two composition factors: the trivial submodule $`IFv_{0,0}`$ and the simple quotient module $`A_{0,0}^{}=A_{0,0}/IFv_{0,0}`$. However, if $`\mathrm{}_1+\mathrm{}_22`$, then $`V^{}=A_{0,0}^{}`$ is not a module of the intermediate series since $`V^{}{}_{0}{}^{(0)}=\mathrm{span}_{IF}\{v_{0,1_{[p]}}|p\overline{1,\mathrm{}_1+\mathrm{}_2}\}`$ has dimension $`\mathrm{}_1+\mathrm{}_2>1`$.

(4) The possible isomorphisms between modules of the intermediate series are the following: (i) $`A_{\alpha ,b}A_{\beta ,d}\alpha \beta \mathrm{\Gamma },b=d`$. (ii) $`A_{0,0}^{}A_{0,1}`$ if $`\mathrm{}=\mathrm{}_2=1`$.

We would like to remark that unlike the case $`\mathrm{}_1+\mathrm{}_2=0`$, we do not have modules of types $`A(\alpha ),B(\alpha )`$ when $`\mathrm{}_1+\mathrm{}_2>0`$. It is also interesting to see that $`A_{0,1}`$ is simple, which is not the case for the Witt algebras (cf. Theorem 2.2(2)) and that $`A_{0,0}^{}A_{0,1}`$ if $`\mathrm{}=\mathrm{}_2=1`$.

3. PROOF OF THEOREM 2.3

Suppose that $`V`$ is a simple module of the intermediate series over $`W=W(\mathrm{}_1,\mathrm{}_2,\mathrm{}_3,\mathrm{\Gamma })`$, where $`\mathrm{}_1+\mathrm{}_21,\mathrm{}_2+\mathrm{}_31`$. We shall further suppose $`\mathrm{}2`$ since $`\mathrm{}=\mathrm{}_2=1`$ has been considered in \[SL\]. For any $`\alpha IF^{\mathrm{}_2+\mathrm{}_3}`$, let $`V(\alpha )=_{\mu \mathrm{\Gamma }}V_{\alpha +\mu }`$. Then obviously, $`V(\alpha )`$ is a submodule of $`V`$ and $`V`$ is a direct sum of different $`V(\alpha )`$. Since $`V`$ is simple, we must have $`V=V(\alpha )`$ for some $`\alpha IF^{\mathrm{}_2+\mathrm{}_3}`$.

Define a total order on $`ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$ as follows:

$$\stackrel{}{i}<\stackrel{}{j}|\stackrel{}{i}|<|\stackrel{}{j}|\text{ or }|\stackrel{}{i}|=|\stackrel{}{j}|\text{ but }p\text{ such that }i_p<j_p\text{ and }i_q=j_q\text{ for }q\overline{1,p1},$$
$`(3.1)`$
for $`\stackrel{}{i},\stackrel{}{j}ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$, where $`|\stackrel{}{i}|=_{p=1}^{\mathrm{}_1+\mathrm{}_2}i_p`$ is the level of $`\stackrel{}{i}`$.

We shall prove Theorem 2.3(1) in two cases.

Case 1. $`\alpha \mathrm{\Gamma }`$.

Observe that by (1.9), $`\mathrm{span}_{IF}\{x^\mu |\mu \mathrm{\Gamma },𝒟_2+𝒟_3\}`$ is the Witt algebra $`W(0,0,\mathrm{}_2+\mathrm{}_3,\mathrm{\Gamma })`$. Note that $`V^{(0)}=_{\mu \mathrm{\Gamma }}V_{\alpha +\mu }^{(0)}`$ is a $`W(0,0,\mathrm{}_2+\mathrm{}_3,\mathrm{\Gamma })`$-submodule of $`V`$. By Theorem 2.2, it is a simple $`W(0,0,\mathrm{}_2+\mathrm{}_3,\mathrm{\Gamma })`$-module of the intermediate series of type $`A_{\alpha ,b}`$ for some $`bIF`$. Thus there exists a $`IF`$-basis $`\{v_{\mu ,0}|\mu \mathrm{\Gamma }\}`$ of $`V^{(0)}`$ such that

$$(x^\mu )v_{\nu ,0}=,\alpha +\nu +b\mu v_{\mu +\nu ,0},$$
$`(3.2)`$
for $`\mu ,\nu \mathrm{\Gamma },𝒟_2+𝒟_3`$. We shall show that (3.2) also holds for $`𝒟_1`$ (It is possible that $`\mathrm{}_1=0`$, in this case, the arguments from here to (3.7) are trivial). Thus let $`=_p`$ with $`p\overline{1,\mathrm{}_1}`$. Then

$$(_q(\alpha _q+\nu _q))(t^{1_{[p]}}_p)v_{\nu ,0}=\delta _{p,q}_pv_{\nu ,0}+(t^{1_{[p]}}_p)(_q(\alpha _q+\nu _q))v_{\nu ,0}=0,$$
$`(3.3)`$
for $`q\overline{\mathrm{}_1+1,\mathrm{}}`$. Thus $`(t^{1_{[p]}}_p)v_{\nu ,0}V_{\alpha +\nu }^{(0)}`$ and so

$$(t^{1_{[p]}}_p)v_{\nu ,0}=c_{p,\nu }v_{\nu ,0}\text{ for some }c_{p,\nu }IF.$$
$`(3.4)`$
Similarly, we have

$$(x^\mu _p)v_{\nu ,0}=d_{p,\mu ,\nu }v_{\mu +\nu ,0}\text{ for some }d_{p,\mu ,\nu }IF.$$
$`(3.5)`$
Applying $`\mathrm{ad}x^\mu _q`$ for $`q\overline{\mathrm{}_1+1,\mathrm{}}`$ to (3.4), using (3.2), we obtain that $`c_{p,\nu }=c_{p,\mu +\nu }`$ if $`\alpha +\nu +b\mu 0`$, from this it is easily derived that $`c_{p,\nu }=c_p`$ does not depend on $`\nu \mathrm{\Gamma }`$. Now applying $`\mathrm{ad}x^\mu _p`$ to (3.4), we obtain

$$(t^{1_{[p]}}_p)(x^\mu _p)v_{\nu ,0}=(c_p1)(x^\mu _p)v_{\nu ,0}.$$
$`(3.6)`$
However, using (3.4), (3.5), $`(x^\mu _p)v_{\nu ,0}`$, if not zero, is an eigenvector of $`t^{1_{[p]}}_p`$ corresponding to eigenvalue $`c_{p,\mu +\nu }=c_p`$. Comparing this with (3.6) gives

$$(x^\mu _p)v_{\nu ,0}=0,$$
$`(3.7)`$
for $`p\overline{1,\mathrm{}_1}`$, which coincides with (3.2).

For any $`\mu \mathrm{\Gamma },0\stackrel{}{i}ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$, we define $`v_{\mu ,\stackrel{}{i}}`$ inductively as follows. Take

$$p^{}=p_\stackrel{}{i}^{}=\mathrm{min}\{p\overline{1,\mathrm{}_1+\mathrm{}_2}|i_p0\},p^{\prime \prime }=p_\mu ^{\prime \prime }=\mathrm{min}\{p\overline{\mathrm{}_1+1,\mathrm{}}|\alpha _p+\mu _p0\}.$$
$`(3.8)`$
Since $`\alpha \mathrm{\Gamma }`$, for any $`\mu \mathrm{\Gamma }`$, we have $`\alpha +\mu 0`$, i.e., there exists $`p\overline{\mathrm{}_1+1,\mathrm{}}`$ with $`\alpha _p+\mu _p0`$. Thus $`p^{\prime \prime }`$ in (3.8) is uniquely defined. Define

$$v_{\mu ,\stackrel{}{i}}=(\alpha _{p^{\prime \prime }}+\mu _{p^{\prime \prime }})^1((t^{1_{[p^{}]}}_{p^{\prime \prime }})v_{\mu ,\stackrel{}{i}1_{[p^{}]}}(i_{p^{\prime \prime }}\delta _{p^{},p^{\prime \prime }}+\delta _{p^{},p^{\prime \prime }}b)v_{\mu ,\stackrel{}{i}1_{[p^{\prime \prime }]}}).$$
$`(3.9)`$
Claim 1. For $`p\overline{1,\mathrm{}},(\mu ,\stackrel{}{i})\mathrm{\Gamma }\times ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$, we have

$$_pv_{\mu ,\stackrel{}{i}}=(\alpha _p+\mu _p)v_{\mu ,\stackrel{}{i}}+i_pv_{\mu ,\stackrel{}{i}1_{[p]}}.$$
$`(3.10)`$
If $`\stackrel{}{i}=0`$, (3.10) follows from (3.2) and (3.7). Suppose $`\stackrel{}{i}>0`$. By (3.9) and the inductive assumption on the order of $`\stackrel{}{i}`$, (3.10) is equivalent to

$$\begin{array}{c}(\alpha _{p^{\prime \prime }}+\mu _{p^{\prime \prime }})^1(\delta _{p,p^{}}_{p^{\prime \prime }}v_{\mu ,\stackrel{}{i}1_{[p^{}]}}+(i_p\delta _{p,p^{}})(t^{1_{[p^{}]}}_{p^{\prime \prime }})v_{\mu ,\stackrel{}{i}1_{[p]}1_{[p^{}]}}\\ (i_{p^{\prime \prime }}\delta _{p^{},p^{\prime \prime }}+\delta _{p^{},p^{\prime \prime }}b)(i_p\delta _{p,p^{\prime \prime }})v_{\mu ,\stackrel{}{i}1_{[p]}1_{[p^{\prime \prime }]}})\\ =i_pv_{\mu ,\stackrel{}{i}1_{[p]}}.\end{array}$$
$`(3.11)`$
We shall verify (3.11) case by case as follows. Case (i): $`pp^{},p^{\prime \prime }`$. In this case, since $`p_{\stackrel{}{i}1_{[p]}}^{}=p^{}`$, (3.11) is precisely the definition (3.9) with $`\stackrel{}{i}`$ replaced by $`\stackrel{}{i}1_{[p]}`$. Case (ii): $`p=p^{}p^{\prime \prime }`$. Then (3.11) becomes

$$\begin{array}{c}(\alpha _{p^{\prime \prime }}+\mu _{p^{\prime \prime }})^1((\alpha _{p^{\prime \prime }}+\mu _{p^{\prime \prime }})v_{\mu ,\stackrel{}{i}1_{[p^{}]}}+i_{p^{\prime \prime }}v_{\mu ,\stackrel{}{i}1_{[p^{}]}1_{[p^{\prime \prime }]}}+(i_p^{}1)(t^{1_{[p^{}]}}_{p^{\prime \prime }})v_{\mu ,\stackrel{}{i}2_{[p^{}]}}\\ i_{p^{\prime \prime }}i_p^{}v_{\mu ,\stackrel{}{i}1_{[p^{}]}1_{[p^{\prime \prime }]}})\\ =i_p^{}v_{\mu ,\stackrel{}{i}1_{[p^{}]}}.\end{array}$$
$`(3.12)`$
Since $`i_p^{}>0`$ by (3.8), if $`i_p^{}=1`$, then (3.12) holds trivially; if $`i_p^{}>1`$, then $`p_{\stackrel{}{i}1_{[p^{}]}}^{}=p^{}`$ and (3.12) holds by definition (3.9) with $`\stackrel{}{i}`$ replaced by $`\stackrel{}{i}1_{[p^{}]}`$. The proofs for Case (iii): $`p=p^{\prime \prime }p^{}`$ and Case (iv): $`p=p^{}=p^{\prime \prime }`$ are exactly analogous.

Claim 2. For $`p\overline{1,\mathrm{}_1+\mathrm{}_2},q\overline{1,\mathrm{}},\mu ,\lambda \mathrm{\Gamma }`$, we have

$$\begin{array}{ccc}(x^\mu _q)v_{\lambda ,1_{[p]}}& =& (\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,1_{[p]}}+\delta _{p,q}v_{\mu +\lambda ,0},\\ (x^\mu t^{1_{[p]}}_q)v_{\lambda ,0}& =& (\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,1_{[p]}}+\delta _{p,q}bv_{\mu +\lambda ,0}.\end{array}$$
$`\begin{array}{c}(3.13)\\ (3.14)\end{array}`$
Let $`p^{\prime \prime }=p_\lambda ^{\prime \prime }`$ be as defined in (3.8). Then $`p^{\prime \prime }\mathrm{}_1+1`$. If $`p^{\prime \prime }>\mathrm{}_1+1`$, using inductive assumption, we can suppose that (3.13) holds for all $`\lambda \mathrm{\Gamma }`$ with $`p_\lambda ^{\prime \prime }<p^{\prime \prime }`$.

As in the proof of (3.4), it is straightforward to verify

$$(x^\mu _q)v_{\lambda ,1_{[p]}}(\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,1_{[p]}},(x^\mu t^{1_{[p]}}_q)v_{\lambda ,0}(\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,1_{[p]}}V_{\alpha +\mu +\lambda }^{(0)}.$$
$`(3.15)`$
Thus we can suppose

$$\begin{array}{ccc}(x^\mu _q)v_{\lambda ,1_{[p]}}& =& (\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,1_{[p]}}+(\delta _{p,q}+d_{p,q}^{\mu ,\lambda })v_{\mu +\lambda ,0},\\ (x^\mu t^{1_{[p]}}_q)v_{\lambda ,0}& =& (\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,1_{[p]}}+(\delta _{p,q}b+e_{p,q}^{\mu ,\lambda })v_{\mu +\lambda ,0},\end{array}$$
$`\begin{array}{c}(3.16)\\ (3.17)\end{array}`$
for some $`d_{p,q}^{\mu ,\lambda },e_{p,q}^{\mu ,\lambda }IF`$. By (3.9), (3.10), we have

$$d_{p,q}^{0,\lambda }=0,e_{p,p^{\prime \prime }}^{0,\lambda }=0.$$
$`(3.18)`$
We shall be careful that the second equation of (3.18) only holds for $`p^{\prime \prime }`$ not for general $`q`$ by definition (3.9) and (3.17). Using (3.16), (3.17) in

$$\begin{array}{c}[x^\mu _q,x^\nu _r]v_{\lambda ,1_{[p]}}=x^{\mu +\nu }(\nu _q_r\mu _r_q)v_{\lambda ,1_{[p]}},\\ [x^\mu _q,x^\nu t^{1_{[p]}}_r]v_{\lambda ,0}=(x^{\mu +\nu }t^{1_{[p]}}(\nu _q_r\mu _r_q)+\delta _{p,q}x^{\mu +\nu }_r)v_{\lambda ,0},\end{array}$$
$`(3.19)`$
we obtain (in the following, for convenience, for any $`\mu \mathrm{\Gamma }`$, we denote $`\overline{\mu }=\alpha +\mu `$)

$$\begin{array}{c}(\overline{\lambda }_r+b\nu _r)d_{p,q}^{\mu ,\nu +\lambda }+(\overline{\lambda }_q+\nu _q+b\mu _q)d_{p,r}^{\nu ,\lambda }(\overline{\lambda }_q+b\mu _q)d_{p,r}^{\nu ,\mu +\lambda }(\overline{\lambda }_r+\mu _r+b\nu _r)d_{p,q}^{\mu ,\lambda }\\ \nu _qd_{p,r}^{\mu +\nu ,\lambda }+\mu _rd_{p,q}^{\mu +\nu ,\lambda }=0,\\ (\overline{\lambda }_r+b\nu _r)d_{p,q}^{\mu ,\nu +\lambda }+(\overline{\lambda }_q+\nu _q+b\mu _q)e_{p,r}^{\nu ,\lambda }(\overline{\lambda }_q+b\mu _q)e_{p,r}^{\nu ,\mu +\lambda }\nu _qe_{p,r}^{\mu +\nu ,\lambda }+\mu _re_{p,q}^{\mu +\nu ,\lambda }=0.\end{array}$$
$`\begin{array}{c}(3.20)\\ \text{(3.21)}\end{array}`$
First assume that $`q\overline{1,\mathrm{}_1}`$. Then the second, third and fifth terms of (3.20) vanish, so do the second, third, fourth terms of (3.21). Thus

$$\begin{array}{c}(\overline{\lambda }_r+b\nu _r)d_{p,q}^{\mu ,\nu +\lambda }(\overline{\lambda }_r+\mu _r+b\nu _r)d_{p,q}^{\mu ,\lambda }+\mu _rd_{p,q}^{\mu +\nu ,\lambda }=0,\\ (\overline{\lambda }_r+b\nu _r)d_{p,q}^{\mu ,\nu +\lambda }+\mu _re_{p,q}^{\mu +\nu ,\lambda }=0,\end{array}$$
$`\begin{array}{c}(3.22)\\ (3.23)\end{array}`$
for $`q\overline{1,\mathrm{}_1}`$. Let $`\nu =0`$ in (3.23), we obtain

$$\overline{\lambda }_rd_{p,q}^{\mu ,\lambda }+\mu _re_{p,q}^{\mu ,\lambda }=0,$$
$`(3.24)`$
for $`q\overline{1,\mathrm{}_1}`$. Subtract (3.23) from (3.22) and making use of (3.24), we obtain

$$(\mu _r+\nu _r)(\overline{\lambda }_r+\mu _r+b\nu _r)d_{p,q}^{\mu ,\lambda }\mu _r(\overline{\lambda }_r+\mu _r+\nu _r)d_{p,q}^{\mu +\nu ,\lambda }=0,$$
$`(3.25)`$
for $`q\overline{1,\mathrm{}_1}`$. Replacing $`\nu `$ by $`\mu `$, and replacing $`\mu `$ by $`2\mu `$ and $`\nu `$ by $`\mu `$ in (3.25), we obtain respectively

$$\begin{array}{c}2\mu _r(\overline{\lambda }_r+(1+b)\mu _r)d_{p,q}^{\mu ,\lambda }\mu _r(\overline{\lambda }_r+2\mu _r)d_{p,q}^{2\mu ,\lambda }=0,\\ \mu _r(\overline{\lambda }_r+(2b)\mu _r)d_{p,q}^{2\mu ,\lambda }2\mu _r(\overline{\lambda }_r+\mu _r)d_{p,q}^{\mu ,\lambda }=0.\end{array}$$
$`(3.26)`$
By (3.18), we can suppose $`\mu 0`$. Choose $`r\overline{\mathrm{}_1+1,\mathrm{}}`$ with $`\mu _r0`$. If $`b0,1`$, then the calculation of the determinant of the coefficients of (3.26) shows that $`d_{p,q}^{\mu ,\lambda }=0`$ and so $`e_{p,q}^{\mu ,\lambda }=0`$ by (3.23) for all $`p\overline{1,\mathrm{}_1+\mathrm{}_2},q\overline{1,\mathrm{}_1},\mu ,\lambda \mathrm{\Gamma }`$.

Assume that $`b=0`$ (the proof for $`b=1`$ is exactly analogous). Replacing $`\nu `$ by $`\nu \mu `$ in (3.25) shows that

$$d_{p,q}^{\mu ,\lambda }=\frac{\mu _r}{\overline{\lambda }_r+\mu _r}c_{p,q},e_{p,q}^{\mu ,\lambda }=\frac{\overline{\lambda }_r}{\overline{\lambda }_r+\mu _r}c_{p,q},\text{ for some }c_{p,q}IF,$$
$`(3.27)`$
if $`\lambda _r,\mu _r,\overline{\lambda }_r+\mu _r0`$, where the second equation follows from (3.24). Using this and (3.23), we obtain that (3.27) holds for all $`\mu ,\lambda `$ with $`\overline{\lambda }_r+\mu _r0`$. In particular, $`e_{p,q}^{0,\lambda }=c_{p,q}`$. As in the proof of (3.7), we have $`(t^{1_{[p]}}_q)v_{\lambda ,0}=0`$ if $`pq`$ and $`q\overline{1,\mathrm{}_1}`$, i.e., $`c_{p,q}=0`$ if $`pq`$ and $`q\overline{1,\mathrm{}_1}`$. Suppose $`p=q\overline{1,\mathrm{}_1}`$. Then by (3.17), (3.27) and using $`[t^{1_{[q]}}_q,t^{i_{[q]}}_q]=(i1)t^{i_{[q]}}_q`$, we can prove by induction on $`i`$ that $`(t^{i_{[q]}}_q)v_{\lambda ,0}=ic_{q,q}v_{\lambda ,i_{[q]}1_{[q]}}`$. Applying $`\mathrm{ad}x^\mu _q`$ to this gives that $`(x^\mu t^{i_{[q]}1_{[q]}}_q)v_{\lambda ,0}=c_{q,q}(x^\mu _q)v_{\lambda ,i_{[q]}1_{[q]}}`$. In particular, taking $`i=2`$ and comparing this with (3.17), (3.27), we obtain that $`c_{q,q}=0`$. This proves that (3.13), (3.14) hold for $`q\overline{1,\mathrm{}_1}`$.

Now assume that $`q\overline{\mathrm{}_1+1,\mathrm{}}`$. Our strategy is to prove that $`d_{p,q}^{\mu ,\nu }=0`$ under some conditions on $`\mu ,\nu `$ and then to obtain the result in general. Thus, first we assume that $`\lambda `$ satisfies

$$\overline{\lambda }_q0,\lambda _q0\text{ for all }q\overline{\mathrm{}_1+1,\mathrm{}}.$$
$`(3.28)`$
Suppose that $`\mu \mathrm{\Gamma }`$ satisfies

$$\mu _q0,q\overline{\mathrm{}_1+1,\mathrm{}},\text{ and }\lambda _{\mathrm{}_1+1}\pm \mu _{\mathrm{}_1+1}0\text{ and so }p_{\lambda \pm \mu }^{\prime \prime }=\mathrm{}_1+1p^{\prime \prime }.$$
$`(3.29)`$
Then by taking $`\nu =0`$ and $`r=p^{\prime \prime }`$ in (3.21), using (3.18) or the inductive assumption on $`p^{\prime \prime }`$, we obtain that

$$\overline{\lambda }_{p^{\prime \prime }}d_{p,q}^{\mu ,\lambda }+\mu _{p^{\prime \prime }}e_{p,q}^{\mu ,\lambda }=0,$$
$`(3.30)`$
holds under condition (3.29). Let $`\nu =\mu ,r=q`$ in (3.21), using (3.30), we obtain that

$$(\overline{\lambda }_q+b\mu _q)(\overline{\lambda }_{p^{\prime \prime }}+2\mu _{p^{\prime \prime }})d_{p,q}^{\mu ,\mu +\lambda }\overline{\lambda }_{p^{\prime \prime }}(\overline{\lambda }_q+(b+1)\mu _q)d_{p,q}^{\mu ,\lambda }=0,$$
$`(3.31)`$
holds under condition (3.29). Let $`\nu =\mu ,r=q`$ in (3.20), we obtain

$$(\overline{\lambda }_qb\mu _q)d_{p,q}^{\mu ,\lambda \mu }+(\overline{\lambda }_q+(b1)\mu _q)d_{p,q}^{\mu ,\lambda }(\overline{\lambda }_q+b\mu _q)d_{p,q}^{\mu ,\mu +\lambda }(\overline{\lambda }_q+(1b)\mu _q)d_{p,q}^{\mu ,\lambda }=0.$$
$`(3.32)`$
Replacing $`\mu `$ by $`\mu `$ and $`\lambda `$ by $`\lambda +\mu `$ in (3.31), we obtain

$$(\overline{\lambda }_q+(1b)\mu _q)(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})d_{p,q}^{\mu ,\lambda }(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_qb\mu _q)d_{p,q}^{\mu ,\mu +\lambda }=0.$$
$`(3.33)`$
Replacing $`\lambda `$ by $`\lambda \mu `$ in (3.31), we obtain

$$(\overline{\lambda }_q+(b1)\mu _q)(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})d_{p,q}^{\mu ,\lambda }(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})(\overline{\lambda }_q+b\mu _q)d_{p,q}^{\mu ,\lambda \mu }=0.$$
$`(3.34)`$
Let $`\tau =(\overline{\lambda }_{p^{\prime \prime }}^2\mu _{p^{\prime \prime }}^2)(\overline{\lambda }_q^2(b\mu _q)^2)`$. Multiplying (3.32) by $`\tau `$ and using (3.33), (3.34), we have

$$\begin{array}{c}(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})^2(\overline{\lambda }_qb\mu _q)^2(\overline{\lambda }_q+(b1)\mu _q)d_{p,q}^{\mu ,\lambda }+(\overline{\lambda }_q+(b1)\mu _q)\tau d_{p,q}^{\mu ,\lambda }\\ (\overline{\lambda }_q+(1b)\mu _q)\tau d_{p,q}^{\mu ,\lambda }(\overline{\lambda }_q+b\mu _q)^2(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})^2(\overline{\lambda }_q+(1b)\mu _q)d_{p,q}^{\mu ,\lambda }=0.\end{array}$$
$`(3.35)`$
i.e.

$$(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_qb\mu _q)\sigma d_{p,q}^{\mu ,\lambda }+(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})(\overline{\lambda }_q+b\mu _q)\sigma d_{p,q}^{\mu ,\lambda }=0,$$
$`(3.36)`$
where

$$\begin{array}{cc}\sigma (\mu )& =(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_qb\mu _q)(\overline{\lambda }_q+(b1)\mu _q)(\overline{\lambda }_q+(1b)\mu _q)(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})(\overline{\lambda }_q+b\mu _q)\\ & =2((b2)\overline{\lambda }_{p^{\prime \prime }}\overline{\lambda }_q\mu _q+\overline{\lambda }_q^2\mu _{p^{\prime \prime }}+b(1b)\mu _{p^{\prime \prime }}\mu _q^2).\end{array}$$
$`(3.37)`$
Thus if we assume that $`\sigma (\mu )0`$, then we obtain

$$(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_qb\mu _q)d_{p,q}^{\mu ,\lambda }+(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})(\overline{\lambda }_q+b\mu _q)d_{p,q}^{\mu ,\lambda }=0.$$
$`(3.38)`$
Assume that

$$(\overline{\lambda }_q+(b+n)\mu _q)(\overline{\lambda }_{p^{\prime \prime }}+(n+2)\mu _{p^{\prime \prime }})0\text{ for all }nZZ_+=\{0,1,2,\mathrm{}\}.$$
$`(3.39)`$
Then using (3.31) recursively, we obtain

$$d_{p,q}^{\mu ,n\mu +\lambda }=\frac{\overline{\lambda }_{p^{\prime \prime }}(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_q+(b+n)\mu _q)}{(\overline{\lambda }_q+b\mu _q)(\overline{\lambda }_{p^{\prime \prime }}+n\mu _{p^{\prime \prime }})(\overline{\lambda }_{p^{\prime \prime }}+(n+1)\mu _{p^{\prime \prime }})}d_{p,q}^{\mu ,\lambda }\text{ for }nZZ_+\text{.}$$
$`(3.40)`$
Thus

$${}_{n\mathrm{}}{}^{}{}_{}{}^{\mathrm{lim}}nd_{p,q}^{\mu ,n\mu +\lambda }=\frac{\overline{\lambda }_{p^{\prime \prime }}(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})\mu _q}{\mu _{p^{\prime \prime }}^2(\overline{\lambda }_q+b\mu _q)}d_{p,q}^{\mu ,\lambda }\text{ for }nZZ_+\text{.}$$
$`(3.41)`$
(We shall remark that since we are encountering only rational functions on $`n`$, and when $`\mu ,\lambda `$, etc. are fixed, we can regard functions as defined in some extension field of the rational field $`Q\text{ }\text{ }`$. Thus the limit has meaning.) In (3.20), setting $`r=q`$ and setting $`\mu ,\nu ,\lambda `$ to be $`2\mu ,\mu ,2n\mu +\lambda \mathrm{\Gamma }`$ respectively, we obtain

$$\begin{array}{c}(\overline{\lambda }_q+2n\mu _qb\mu _q)d_{p,q}^{2\mu ,2n\mu +\lambda \mu }+(\overline{\lambda }_q+2n\mu _q\mu _q+2b\mu _q)d_{p,q}^{\mu ,2n\mu +\lambda }\\ (\overline{\lambda }_q+2n\mu _q+2b\mu _q)d_{p,q}^{\mu ,2(n+1)\mu +\lambda }(\overline{\lambda }_q+2n\mu _q+2\mu _qb\mu _q)d_{p,q}^{2\mu ,2n\mu +\lambda }+3\mu _qd_{p,q}^{\mu ,2n\mu +\lambda }=0.\end{array}$$
$`(3.42)`$
Taking the limit of $`n\mathrm{}`$, using (3.41) (we assume that conditions (3.29), (3.39) also hold for $`2\mu ,\mu `$), by noting that the sum of the second term and the third term vanishes and so does the last term, we obtain

$$\frac{(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})}{(\overline{\lambda }_q\mu _q+2b\mu _q)}d_{p,q}^{2\mu ,\lambda \mu }\frac{\overline{\lambda }_{p^{\prime \prime }}(\overline{\lambda }_{p^{\prime \prime }}+2\mu _{p^{\prime \prime }})}{(\overline{\lambda }_q+2b\mu _q)}d_{p,q}^{2\mu ,\lambda }=0.$$
$`(3.43)`$
In (3.20), setting $`r,\mu ,\nu `$ to be $`q,2\mu ,\mu `$ respectively, using (3.31), (3.38), (3.43), we deduce

$$d_{p,q}^{2\mu ,\lambda }=\frac{(\overline{\lambda }_{p^{\prime \prime }}+2\mu _{p^{\prime \prime }})(\overline{\lambda }_q+b\mu _q)}{2(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_q+2b\mu _q)}d_{p,q}^{\mu ,\lambda }.$$
$`(3.44)`$
Using (3.44) in (3.43), we obtain

$$\frac{(\overline{\lambda }_{p^{\prime \prime }}\mu _{p^{\prime \prime }})(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})^2(\overline{\lambda }_q+(b1)\mu _q)}{2\overline{\lambda }_{p^{\prime \prime }}(\overline{\lambda }_q+(2b1)\mu _q)^2}d_{p,q}^{\mu ,\lambda \mu }\frac{\overline{\lambda }_{p^{\prime \prime }}(\overline{\lambda }_{p^{\prime \prime }}+2\mu _{p^{\prime \prime }})^2(\overline{\lambda }_q+b\mu _q)}{2(\overline{\lambda }_{p^{\prime \prime }}+\mu _{p^{\prime \prime }})(\overline{\lambda }_q+2b\mu _q)^2}d_{p,q}^{\mu ,\lambda }=0$$
$`(3.45)`$
Observe that the determinant of the coefficients of $`d_{p,q}^{\mu ,\lambda \mu },d_{p,q}^{\mu ,\lambda }`$ in (3.34), (3.45) is a nonzero rational function on $`\mu `$ (when $`\lambda `$ is fixed), denote it by $`\mathrm{\Delta }(\mu )`$. Thus we can choose $`\mu \mathrm{\Gamma }`$ such that $`\mathrm{\Delta }(\mu )0`$, then we obtain that $`d_{p,q}^{\mu ,\lambda }=0`$. Note that any element $`\mu \mathrm{\Gamma }`$ can be expressed as a sum of two elements $`\mu =\mu ^{}+\mu ^{\prime \prime }`$ such that $`\mu ^{},\mu ^{\prime \prime },\mu ^{}\mu ^{\prime \prime }`$ all satisfy conditions (3.29), (3.39) and $`\sigma (\mu ^{}),\sigma (\mu ^{\prime \prime }),\mathrm{\Delta }(\mu ^{}),\mathrm{\Delta }(\mu ^{\prime \prime })0`$. Then by taking $`r=q,\mu =\mu ^{},\nu =\mu ^{\prime \prime }`$ in (3.20), we obtain that $`d_{p,q}^{\mu ,\lambda }=0`$ for all $`\mu \mathrm{\Gamma }`$. If $`\lambda `$ does not satisfy (3.28), then using (3.20) again, we can again deduce that $`d_{p,q}^{\mu ,\lambda }=0`$. Then (3.30) and (3.21) show that $`e_{p,q}^{\mu ,\lambda }=0`$. This proves Claim 2.

Claim 3. For $`p\overline{1,\mathrm{}_1+\mathrm{}_2},q\overline{1,\mathrm{}},\mu ,\lambda \mathrm{\Gamma },\stackrel{}{i}ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$, we have

$$\begin{array}{ccc}(t^{1_{[p]}}_q)v_{\lambda ,\stackrel{}{i}}& =& (\alpha _q+\lambda _q)v_{\lambda ,\stackrel{}{i}+1_{[p]}}+(i_q+\delta _{p,q}b)v_{\lambda ,\stackrel{}{i}+1_{[p]}1_{[q]}},\\ (x^\mu _q)v_{\lambda ,\stackrel{}{i}+1_{[p]}}& =& (\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,\stackrel{}{i}+1_{[p]}}+(i_q+\delta _{p,q})v_{\mu +\lambda ,\stackrel{}{i}+1_{[p]}1_{[q]}},\\ (x^\mu t^{1_{[p]}}_q)v_{\lambda ,\stackrel{}{i}}& =& (\alpha _q+\lambda _q+b\mu _q)v_{\mu +\lambda ,\stackrel{}{i}+1_{[p]}}+(i_q+\delta _{p,q}b)v_{\mu +\lambda ,\stackrel{}{i}+1_{[p]}1_{[q]}}.\end{array}$$
$`\begin{array}{c}(3.46)\\ (3.47)\\ (3.48)\end{array}`$
Suppose $`\stackrel{}{i}0`$. We shall use induction on $`\stackrel{}{i}`$. Let $`p^{}=p_\stackrel{}{i}^{},p^{\prime \prime }=p_\lambda ^{\prime \prime }`$. Suppose $`q=p^{\prime \prime }`$. If $`pp^{}`$, then $`p_{\stackrel{}{i}+1_{[p]}}^{}=p`$ and so (3.46) is the definition (3.9). If $`p>p^{}`$, then using (3.9), we obtain that $`(t^{1_{[p]}}_{p^{\prime \prime }})v_{\lambda ,\stackrel{}{i}}`$ is equal to

$$\begin{array}{c}(\alpha _{p^{\prime \prime }}+\lambda _{p^{\prime \prime }})^1((\delta _{p^{},p^{\prime \prime }}t^{1_{[p]}}_{p^{\prime \prime }}\delta _{p,p^{\prime \prime }}t^{1_{[p^{}]}}_{p^{\prime \prime }})v_{\lambda ,\stackrel{}{i}1_{[p^{}]}}\\ +t^{1_{[p^{}]}}_{p^{\prime \prime }}((\alpha _{p^{\prime \prime }}+\lambda _{p^{\prime \prime }})v_{\lambda ,\stackrel{}{i}+1_{[p]}1_{[p^{}]}}+(i_{p^{\prime \prime }}\delta _{p^{},p^{\prime \prime }}+\delta _{p,p^{\prime \prime }}b)v_{\lambda ,\stackrel{}{i}+1_{[p]}1_{[p^{}]}1_{[p^{\prime \prime }]}})\\ (i_{p^{\prime \prime }}\delta _{p^{},p^{\prime \prime }}+\delta _{p^{},p^{\prime \prime }}b)(t^{1_{[p]}}_{p^{\prime \prime }})v_{\lambda ,\stackrel{}{i}1_{[p^{\prime \prime }]}}),\end{array}$$
$`(3.49)`$
which is equal to the right-hand side of (3.46) by inductive assumption and by noting that $`\stackrel{}{i}+1_{[p]}1_{[p^{}]}<\stackrel{}{i}`$ since $`p>p^{}`$ (cf. (3.1)). If $`qp^{\prime \prime }`$, we can prove (3.46) similarly. Using induction, as in the proofs of (3.16), (3.17), we see that (3.47), (3.48) hold up to some elements in $`V_{\alpha +\mu +\lambda }^{(0)}`$. Now the proof is exactly analogous to that of Claim 2.

Claim 4. $`B=\{v_{\mu ,\stackrel{}{i}}|(\mu ,\stackrel{}{i})\mathrm{\Gamma }\times ZZ_+^{\mathrm{}_1+\mathrm{}_2}\}`$ is an $`IF`$-basis of $`V`$.

By (3.10), it is straightforward to verify that $`B`$ is $`IF`$-independent. So, it remains to prove that $`V`$ is spanned by $`B`$. For any $`\mu \mathrm{\Gamma },\stackrel{}{i}ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$, set

$$\begin{array}{c}V_{\alpha +\mu }^{[\stackrel{}{i}]}=\{vV_{\alpha +\mu }|\underset{p=1}{\overset{\mathrm{}}{}}(_p(\alpha _p+\mu _p))^{j_p}v=0,\stackrel{}{j}>\stackrel{}{i}\},V_{\alpha +\mu }^{(\stackrel{}{i})}=\underset{\stackrel{}{j}<\stackrel{}{i}}{}V_{\alpha +\mu }^{[\stackrel{}{j}]},\\ V^{[\stackrel{}{i}]}=\underset{\mu \mathrm{\Gamma }}{}V_{\alpha +\mu }^{[\stackrel{}{i}]},V^{(\stackrel{}{i})}=\underset{\mu \mathrm{\Gamma }}{}V_{\alpha +\mu }^{(\stackrel{}{i})}.\end{array}$$
$`(3.50)`$
Then

$$V_{\alpha +\mu }=\underset{\stackrel{}{j}ZZ_+^{\mathrm{}_1+\mathrm{}_2}}{}V_{\alpha +\mu }^{[\stackrel{}{j}]}\text{ and }v_{\mu ,\stackrel{}{i}}V_{\alpha +\mu }^{[\stackrel{}{i}]}\backslash V_{\alpha +\mu }^{(\stackrel{}{i})},\mu \mathrm{\Gamma },\stackrel{}{i}ZZ_+^{\mathrm{}_1+\mathrm{}_2},$$
$`(3.51)`$
by (3.10) and induction on $`\stackrel{}{i}`$. On the contrary, suppose that $`V`$ cannot be spanned by $`B`$ and that $`\stackrel{}{i}`$ is the minimal element in $`ZZ_+^{\mathrm{}_1+\mathrm{}_2}`$ such that there exists $`vV_{\alpha +\mu }^{[\stackrel{}{i}]}\backslash V_{\alpha +\mu }^{(\stackrel{}{i})}`$ such that $`v`$ is not in the space spanned by $`B`$. Then $`\stackrel{}{i}0`$. Let $`q`$ be the minimal index with $`i_q0`$. Then $`v^{}=(_q(\alpha _q+\mu _q))vV_{\alpha +_\mu }^{[\stackrel{}{i}1_{[q]}]}`$. By the assumption, $`v^{}`$ is in the space spanned by $`B`$. Thus

$$v^{\prime \prime }=v^{}cv_{\mu ,\stackrel{}{i}1_{[q]}}V_{\alpha +\mu }^{(\stackrel{}{i}1_{[q]})},$$
$`(3.52)`$
for some $`cIF`$. Let $`w=vci_q^1v_{\mu ,\stackrel{}{i}}`$. Given any $`\stackrel{}{j}\stackrel{}{i}`$. If $`j_q0`$, then $`\stackrel{}{j}1_{[q]}\stackrel{}{i}1_{[q]}`$, and by (3.10), (3.51), we have

$$\underset{p=1}{\overset{\mathrm{}}{}}(_p(\alpha _p+\mu _p))^{j_p}w=\underset{p=1}{\overset{\mathrm{}}{}}(_p(\alpha _p+\mu _p))^{j_p\delta _{p,q}}v^{\prime \prime }=0.$$
$`(3.53)`$
On the other hand, if $`j_q=0`$, then $`\stackrel{}{j}>\stackrel{}{i}`$, and so by (3.9), (3.50), we have

$$\underset{p=1}{\overset{\mathrm{}}{}}(_p(\alpha _p+\mu _p))^{j_p}w=\underset{p=1}{\overset{\mathrm{}}{}}(_p(\alpha _p+\mu _p))^{j_p}vci_q^1\underset{p=1}{\overset{\mathrm{}}{}}(_p(\alpha _p+\mu _p))^{j_p}v_{\mu ,\stackrel{}{i}}=0.$$
$`(3.54)`$
(3.53), (3.54) show that $`wV_{\alpha +\mu }^{(\stackrel{}{i})}`$ , and so $`w`$ is in the space spanned by $`B`$, a contradiction with that $`v`$ is not in the space spanned by $`B`$. Thus Claim 4 follows.

Now using Claim 3, we can obtain (2.12) by induction on $`\stackrel{}{i}`$. This proves Theorem 2.3(1) in this case.

Case 2. $`\alpha \mathrm{\Gamma }`$.

Then $`V(\alpha )=V(0)`$. Thus we can suppose $`\alpha =0`$. First assume that $`V=V_0`$. Then $`(x^\mu t^\stackrel{}{i}_q)VV_\mu =0`$ for all $`\mu \mathrm{\Gamma }\backslash \{0\}`$, and since $`W`$ is generated by $`x^\mu t^\stackrel{}{i}_q`$ with $`\mu 0`$, we have $`WV=0`$. Since $`V`$ is indecomposable, we obtain that $`V=IFv_{0,0}`$ must be the trivial submodule of $`A_{0,0}`$. Thus assume that there exists $`\mu \mathrm{\Gamma }\backslash \{0\}`$ such that $`V_\mu \{0\}`$. Then by \[SZ1\], $`V_\mu \{0\}`$ for all $`\mu \mathrm{\Gamma }\backslash \{0\}`$. Suppose $`V_0=\{0\}`$. Then $`V^{(0)}=_{\mu \mathrm{\Gamma }\backslash \{0\}}V_\mu ^{(0)}A_{0,0}^{}`$ as $`W(0,0,\mathrm{}_2+\mathrm{}_3,\mathrm{\Gamma })`$-modules, and

$$\mu _pv_{\mu ,0}=(x^{2\mu }_p)v_{\mu ,0}=(x^\mu _p)(x^\mu t^{1_{[p]}}_p)v_{\mu ,0}(x^\mu t^{1_{[p]}})(x^\mu _p)v_{\mu ,0}=0,$$
$`(3.55)`$
for all $`\mu \mathrm{\Gamma },p\overline{1,\mathrm{}_1+\mathrm{}_2}`$, which shows that $`\mathrm{}_2=0`$. Then by assumption, $`\mathrm{}_1,\mathrm{}_31`$. We have

$$\mu _{\mathrm{}}v_{\mu ,0}=(x^{2\mu }_{\mathrm{}})v_{\mu ,0}=([x^\mu _1,x^\mu t^{1_{[1]}}_{\mathrm{}}][x^\mu t^{1_{[1]}}_1,x^\mu _{\mathrm{}}])v_{\mu ,0}=0,$$
$`(3.56)`$
for all $`\mu \mathrm{\Gamma },`$ a contradiction since $`\mathrm{\Gamma }`$ is nondegenerate. Thus $`V_0\{0\}`$. Now as in Case 1, we obtain that (2.12) holds for all $`\mu ,\nu \mathrm{\Gamma }`$ with $`\nu ,\mu +\nu 0`$ (with suitable $`b`$). Keeping this in mind will help our understanding in the following discussion. If $`V^{(0)}`$ is a $`W(0,0,\mathrm{}_2+\mathrm{}_3,\mathrm{\Gamma })`$-module of the intermediate series of type $`A_{0,b}`$, then exactly as in Case 1, we can obtain Theorem 2.3(1). The only difference is that we shall define $`v_{0,\stackrel{}{i}}`$ to satisfy

$$(t^{2_{[p^{}]}}_p^{})v_{0,\stackrel{}{i}1_{[p^{}]}}=(i_p^{}+1)v_{0,\stackrel{}{i}},$$
$`(3.57)`$
(cf. (3.9)), where $`p^{}=p_\stackrel{}{i}^{}`$.

It remains to consider that the $`W(0,0,\mathrm{}_2+\mathrm{}_3,\mathrm{\Gamma })`$-module $`V^{(0)}`$ is one of the following four cases: $`A(\beta ),B(\beta ),A_{0,0}^{}IFv_{0,0},A_{0,1}^{}IFv_{0,0}`$. First suppose $`V^{(0)}=A(\beta )`$. Define $`v_{0,\stackrel{}{i}}`$ as in (3.57). Let $`p\overline{1,\mathrm{}_1+\mathrm{}_2},q\overline{\mathrm{}_1+1,\mathrm{}},\mu \mathrm{\Gamma }\backslash \{0\}`$. By applying $`\mathrm{ad}_r`$ to $`(x^\mu _q)v_{\mu ,1_{[p]}}`$, using $`(x^\mu _q)v_{\mu ,0}=0`$ by (2.10), we see that $`(x^\mu _q)v_{\mu ,1_{[p]}}V_0^{(0)}`$, i.e., $`(x^\mu _q)v_{\mu ,1_{[p]}}=c_{p,q,\mu }v_{0,0}`$ for some $`c_{p,q,\mu }IF`$. Applying $`\mathrm{ad}x^\nu _q`$ with $`\nu 0`$ to it, using (2.10), we obtain

$$\begin{array}{c}c_{p,q,\mu }(\nu _q+\beta _q)v_{\nu ,0}=(\mu _q\nu _q)(x^{\mu +\nu }_q)v_{\mu ,1_{[p]}}+x^\mu _q(\mu _qv_{\nu \mu ,1_{[p]}}+\delta _{p,q}v_{\nu \mu ,0})\\ =(\mu _q\nu _q)(\mu _qv_{\nu ,1_{[p]}}+\delta _{p,q}v_{\nu ,0})\mu _q((\nu _q\mu _q)v_{\nu ,1_{[p]}}+\delta _{p,q}v_{\nu ,0})+\delta _{p,q}(\nu _q\mu _q)v_{\nu ,0}\\ =\delta _{p,q}\mu _qv_{\nu ,0},\end{array}$$
$`(3.58)`$
for all $`\nu \mathrm{\Gamma }\backslash \{0\}`$. This shows that $`c_{p,q,\mu }=0`$ and so $`(x^\mu _q)v_{\mu ,1_{[p]}}=0`$. Applying $`\mathrm{ad}x^\nu _r`$ with $`\nu ,\mu +\nu 0,r\overline{\mathrm{}_1+1,\mathrm{}}`$ to this, we obtain

$$\begin{array}{ccc}0& =& x^{\mu +\nu }(\mu _r_q\nu _q_r)v_{\mu ,1_{[p]}}+x^\mu _q(\mu _rv_{\nu \mu ,1_{[p]}}+\delta _{p,r}v_{\nu \mu ,0})\\ & =& \mu _r(\mu _qv_{\nu ,1_{[p]}}+\delta _{p,q}v_{\nu ,0})\nu _q(\mu _rv_{\nu ,1_{[p]}}+\delta _{p,r}v_{\nu ,0})\\ & & \mu _r(\nu _q\mu _q)v_{\nu ,1_{[p]}}\delta _{p,q}\mu _rv_{\nu ,0}+\delta _{p,r}(\nu _q\mu _q)v_{\nu ,0})\\ & =& \delta _{p,r}\mu _qv_{\nu ,0},\end{array}$$
$`(3.59)`$
which is impossible. Thus the case $`V^{(0)}=A(\beta )`$ does not occur.

Next suppose $`V^{(0)}=B(\beta )`$. Let $`p\overline{1,\mathrm{}_1+\mathrm{}_2},q\overline{\mathrm{}_1+1,\mathrm{}},pq,\mu ,\nu ,\mu \pm \nu \mathrm{\Gamma }\backslash \{0\}`$. We shall calculate $`[x^\nu _q,x^\nu _p](x^\mu t^{1_{[p]}}_q)v_{\mu ,0}`$. It is equal to

$$\begin{array}{cc}(\nu _q_p+\nu _p_q)(x^\mu t^{1_{[p]}}_q)v_{\mu ,0}& =([\nu _q_p+\nu _p_q,x^\mu t^{1_{[p]}}_q]+(x^\mu t^{1_{[p]}}_q)(\nu _q_p+\nu _p_q))v_{\mu ,0}\\ & =\nu _q(\mu _q+\beta _q)v_{0,0}.\end{array}$$
$`(3.60)`$
On the other hand, it is equal to

$$\begin{array}{c}x^\nu _q([x^\nu _p,x^\mu t^{1_{[p]}}_q]v_{\mu ,0}(\mu _p+\nu _p)(x^\mu t^{1_{[p]}}_q)v_{\mu \nu ,0})\\ x^\nu _p([x^\nu _q,x^\mu t^{1_{[p]}}_q]v_{\mu ,0}+(\nu _q\mu _q)(x^\mu t^{1_{[p]}}_q)v_{\nu \mu ,0}).\end{array}$$
$`(3.61)`$
The first term of (3.61) is equal to

$$\begin{array}{c}x^\nu _q((x^{\mu \nu }_q+x^{\mu \nu }t^{1_{[p]}}(\mu _p_q+\nu _q_p))v_{\mu ,0}(\mu _p+\nu _p)(\nu _q)v_{\nu ,1_{[p]}})\\ =\nu _q(x^\nu _q)v_{\nu ,0}+x^\nu _q(2\mu _p\nu _qv_{\nu ,1_{[p]}}+\nu _qv_{\nu ,0})+\nu _q(\mu _p+\nu _p)(x^\nu _q)v_{\nu ,1_{[p]}}\\ =\nu _q(\nu _q+\beta _q)v_{0,0}2\mu _p\nu _q(x^\nu _q)v_{\nu ,1_{[p]}}\nu _q(\nu _q+\beta _q)v_{0,0}+\nu _q(\mu _p+\nu _p)(x^\nu _q)v_{\nu ,1_{[p]}}\\ =\nu _q(\nu _p\mu _p)(x^\nu _q)v_{\nu ,1_{[p]}}.\end{array}$$
$`(3.62)`$
Similarly, the second term of (3.61) is equal to

$$x^\nu _p((\mu _q\nu _q)(x^{\mu +\nu }t^{1_{[p]}}_q)v_{\mu ,0}+(\nu _q\mu _q)\nu _qv_{\nu ,1_{[p]}})=0.$$
$`(3.63)`$
(3.60)-(3.63) show that we obtain that $`(\mu _q+\beta _q)v_{0,0}=(\nu _p\mu _p)(x^\nu _q)v_{\nu ,1_{[p]}}`$ for all $`\mu ,\nu ,\nu \pm \nu \mathrm{\Gamma }\backslash \{0\}`$ with $`\nu _q0`$. This is impossible. Thus $`V^{(0)}=B(\beta )`$ does not occur either.

Now suppose $`V^{(0)}=A_{0,0}^{}IFv_{0,0}`$. Let $`\mu \mathrm{\Gamma },q\overline{1,\mathrm{}},p\overline{1,\mathrm{}_1+\mathrm{}_2}`$. Then $`(x^\mu _q)v_{\mu ,0}=0`$. Applying $`\mathrm{ad}_r,r\overline{1,\mathrm{}}`$ to $`u=(x^\mu t^{1_{[p]}}_q)v_{\mu ,0}`$, we see that $`uV_0^{(0)}`$, and so $`(x^\mu _q)u=0`$. Thus we have (3.55), which leads to $`\mathrm{}_2=0`$. So $`\mathrm{}_1,\mathrm{}_31`$. Let $`p\overline{1,\mathrm{}_1},q\overline{\mathrm{}_1+1,\mathrm{}},\mu ,\nu ,\nu \pm \mu \mathrm{\Gamma }\backslash \{0\}`$. We have $`(x^\mu t^{1_{[p]}}_q)v_{\mu ,0}=c_{p,q,\mu }v_{0,0}`$ for some $`c_{p,q,\mu }IF`$. Let $`=_{r=1}^\mathrm{}_1a_r_r𝒟_1`$ (cf. (2.2)). Then

$$c_{p,q,\mu }(x^\nu )v_{0,0}=[x^\nu ,x^\mu t^{1_{[p]}}_q]v_{\mu ,0}+(x^\mu t^{1_{[p]}}_q)(x^\nu )v_{\mu ,0}=a_px^{\mu +\nu }_qv_{\mu ,0}=a_p\mu _qv_{\nu ,0},$$
$`(3.64)`$
for all $`p\overline{1,\mathrm{}_1},q\overline{\mathrm{}_1+1,\mathrm{}},\mu ,\nu ,\nu \pm \mu \mathrm{\Gamma }\backslash \{0\}`$. This shows that $`(x^\nu )v_{0,0}0`$ for all $`\nu 0,𝒟_1\backslash \{0\}`$. Thus the linear map $`\tau :𝒟_1V_\nu ^{(0)}`$ defined by $`\tau ()=(x^\nu )v_{0,0}`$ is injective But $`\mathrm{dim}_{IF}V_\nu ^{(0)}=1`$, so $`\mathrm{}_1=1`$. Thus we can simply denote $`\stackrel{}{i}`$ just by $`iZZ_+`$. (3.64) shows that $`(x^\nu _1)v_{0,0}`$ does not depend on $`\nu `$. By rescaling $`v_{0,0}`$ if necessary, we can suppose $`(x^\nu _1)v_{0,0}=v_{\nu ,0}`$ for all $`\nu \mathrm{\Gamma }\backslash \{0\}`$. Now if we denote $`v_{0,0}^{}=0,v_{0,i}^{}=v_{0,i1}`$ and $`v_{\nu ,i}^{}=v_{\nu ,i},\nu 0`$, then as in case 1, we can prove

$$(x^\mu t^i_q)v_{\nu ,j}^{}=\{\begin{array}{cc}jv_{\mu +\nu ,i+j1}^{}& \text{if }q=1,\\ \nu _qv_{\mu +\nu ,i+j}^{}& \text{if }q>1.\end{array}$$
$`(3.65)`$
This shows that $`V=A_{0,0}^{}`$ as $`W(1,0,\mathrm{}1,\mathrm{\Gamma })`$-modules.

Finally suppose $`V^{(0)}=A_{0,1}^{}IFv_{0,0}`$. Then as above, we have $`\mathrm{}_2=0`$, and we also have (3.64) except the last equality which should now be $`a_p\nu _qv_{\nu ,0}`$. Since we can always take $`\nu `$ such that $`\nu _q\nu _q^{}`$ for all $`q,q^{}\overline{\mathrm{}_1,\mathrm{}_1},qq^{}`$. This shows that $`\mathrm{}_1=\mathrm{}_3=1`$. Thus $`A_{0,1}^{}=A_{0,0}^{}`$ as $`W(0,0,1,\mathrm{\Gamma })`$-modules and this case becomes the previous case. This completes the proof of Theorem 2.3(1).

The proof of the rest of Theorem 2.3 is standard (see also \[Z1,SL\]).

References

\[BXZ\] G. Benkart, X. Xu and K. Zhao, “Classical Lie superalgebras over the simple associative algebras,” preprint 2000.

\[DZ1\] D. Z. Dokovic, K. Zhao, “Derivations, isomorphisms, and second cohomology of generalized Witt algebras,” Trans. of Amer. Math. Soc., 350 (1998), 643-664.

\[DZ2\] D. Z. Dokovic, K. Zhao, “Generalized Cartan type $`W`$ Lie algebras in characteristic zero,” J. Alg., 195 (1997), 170-210.

\[E1\] S. Eswara Rao, “Irreducible representations of the Lie algebra of the diffeomorphisms of a $`d`$-dimensional torus,” J. Alg., 182 (1996), 401-421.

\[E2\] S. Eswara Rao, “Representations of Witt algebras,” Publ. Res. Inst. Math. Sci., 30 (1994), 191-201.

\[K\] V. G. Kac, Vertex Algebras for Beginners, University Lectures Series, Vol. 10, AMS. Providence RI, 1996.

\[Kaw\] N. Kawamoto, “Generalizations of Witt algebras over a field of characteristic zero,” Hiroshima Math. J., 16 (1986), 417-462.

\[M\] O. Mathieu, “Classification of Harish-Chandra modules over the Virasoro Lie algebra,” Invent. Math., 107 (1992), 225-234.

\[P\] D. P. Passman, “Simple Lie algebras of Witt type,” J. Alg., 206 (1998), 682-692.

\[PZ\] J. Patera, H. Zassenhaus, “The higher rank Virasoro algebras,” Comm. Math. Phys., 136 (1991), 1-14.

\[S1\] Y. Su, “A classification of indecomposable $`sl_2(C\text{ }\text{ })`$-modules and a conjecture of Kac on irreducible modules over the Virasoro algebra,” J. Alg., 161 (1993), 33-46.

\[S2\] Y. Su, “Harish-Chandra modules of the intermediate series over the high rank Virasoro algebras and high rank super-Virasoro algebras,” J. Math. Phys., 35 (1994), 2013-2023.

\[S3\] Y. Su, “Classification of Harish-Chandra modules over the super-Virasoro algebras,” Comm. Alg., 23 (1995), 3653-3675.

\[S4\] Y. Su, “Simple modules over the high rank Virasoro algebras,” Comm. Alg., in press.

\[SX\] Y. Su, X. Xu, “Structure of divergence-free Lie algebras,” to appear.

\[SXZ\] Y. Su, X. Xu and H. Zhang, “Derivation-simple algebras and the structures of Lie algebras of Witt type,” J. Alg., in press.

\[SZ1\] Y. Su, K. Zhao, “Generalized Virasoro and super-Virasoro algebras and modules of the intermediate series,” to appear.

\[SZ2\] Y. Su, K. Zhao, “Second cohomology group of generalized Witt type Lie algebras and certain representations,” to appear.

\[SZ3\] Y. Su, K. Zhao, “Simple algebras of Weyl type,” to appear in Sciences in China.

\[SZ4\] Y. Su, K. Zhao, “Isomorphism classes and automorphism groups of algebras of Weyl type,” to appear in Sciences in China.

\[SZh\] Y. Su, L. Zhu “Non-graded Virasoro and super-Virasoro algebras and modules of the intermediate series,” to appear

\[X1\] X. Xu, “New generalized simple Lie algebras of Cartan type over a field with characteristic 0,” J. Alg., 224 (2000), 23-58.

\[X2\] X. Xu, Algebraic Theory of Hamiltonian Superoperators, monograph, to appear.

\[Z1\] K. Zhao, “Harish-Chandra modules over generalized Witt algebras,” to appear.

\[Z2\] K. Zhao, “Isomorphisms between generalized Cartan type $`W`$ Lie algebras in characteristic zero,” Canadian J. Math., 50 (1998), 210-224.


format: text

text:
# Fast Power Spectrum Estimation

## 1 Introduction

Cosmological data sets are rapidly becoming very large, making the optimal analysis of data a challenging problem. Particularly large problems arise in the analysis of CMB data, galaxy power spectra and weak lensing data. For Gaussian random fields, the statistics are fully solvable, and the construction of optimal quadratic or maximum likelihood estimators is uniquely defined.

A full maximum likelihood analysis of COBE which contained 3890 pixels was done by Bunn & White (1997). The optimal analysis procedure requires $`𝒪(N^3)`$ operations for $`N`$ data points, which is generally very expensive, and prohibitive for many data sets. Data compression is possible through the use of a Karhunen-Loeve expansion in terms of “signal-to-noise” eigenmodes (Bond, 1995). The first compression step still costs $`O(N^3)`$, but subsequent analyses are accelerated. Faster procedures have been suggested, usually at the expense of optimality. The computation of correlation functions, for example, only costs $`𝒪(N\mathrm{log}N)`$ operations, and has been a popular quick algorithm (Pen et al., 2002; Szapudi et al., 2001). Similarly, a weighted Fourier Transform of the data is equally fast, and was proposed by Feldman et al. (1994). Pen et al. (2003) summarized the trade-off made in these approximations.

We consider a power spectrum estimator optimal if it minimizes the variance. The variance of the power is a four point function, which can be expressed in terms of two point functions for a Gaussian random field. One can show that a naive quadratic estimator applied to the Wiener filtered data set is optimal (Seljak, 1998). If the noise and signal covariance matrices commute, the correlation function and weighted Fourier techniques are optimal. If the signal-to-noise is less than unity on all scales, the correlation function is optimal. But in general none of these cases applies, in which case the historic fast estimators are suboptimal.

In this paper we present an algorithm which is fast and optimal, and works on a wide range of problems, geometries, and condition numbers. It is an extension of the iterative technique presented in Padmanabhan et al. (2002) to cover regimes of poor condition number.

The basic premise is that the forward operation of applying the signal and noise correlations to the data set an be done in $`𝒪(N\mathrm{log}N)`$ time. We then construct iterative techniques to achieve the inverse.

## 2 Maximum Likelihood

In this section we review the mathematical formulation of the power spectrum estimation problem. An observation is a data set of $`N`$ points sampled at positions $`x_i`$, written as a vector $`\mathrm{\Delta }_i`$. We take this vector to have zero expectation value. This vector is assumed to be the sum of signal plus noise, such that the expectation of the covariance matrix is

$$\mathrm{\Delta }_i\mathrm{\Delta }_j=C_{ij}^N+C_{ij}^S$$
(1)
for a noise covariance matrix $`𝐂^N`$ and a signal covariance $`𝐂^S`$. We parametrize the signal covariance matrix as a sum of $`n_b`$ band powers,

$$𝐂^S=\underset{\alpha =1}{\overset{n_b}{}}p_\alpha 𝐂_\alpha .$$
(2)
The log of the probability of the data given a model is

$$=\frac{1}{2}\mathrm{log}|𝐂^N+𝐂^S|\frac{\mathrm{\Delta }^T(𝐂^N+𝐂^S)^1\mathrm{\Delta }}{2}+\frac{n_b}{2}\mathrm{log}(2\pi )$$
(3)
We wish to find the set of parameters $`p_\alpha `$ which maximize the likelihood (3). Differentiating, one obtains a system of equations

$$\mathrm{Tr}[(𝐂^N+𝐂^S)^1𝐂_\alpha ]+\mathrm{\Delta }^t(𝐂^N+𝐂^S)^1𝐂_\alpha (𝐂^N+𝐂^S)^1\mathrm{\Delta }=0.$$
(4)
The Newton-Raphson solution for (4) starts with an initial guess $`p_\alpha ^0`$ and iterates

$$p_\beta ^{n+1}=p_\beta ^nf_\alpha G_{\alpha \beta }^1$$
(5)
where $`f_\alpha `$ is the left hand side of (4) and $`𝐆`$ is the Jacobian

$$G_{\alpha \beta }=2F_{\alpha \beta }\mathrm{\Delta }^t(𝐂^N+𝐂^S)^1𝐂_\alpha (𝐂^N+𝐂^S)^1𝐂_\beta (𝐂^N+𝐂^S)^1\mathrm{\Delta }\mathrm{\Delta }^t(𝐂^N+𝐂^S)^1𝐂_\beta (𝐂^N+𝐂^S)^1𝐂_\alpha (𝐂^N+𝐂^S)^1\mathrm{\Delta }.$$
(6)
$`𝐅`$ is the Fisher matrix defined as

$$F_{\alpha \beta }\frac{1}{2}\mathrm{Tr}[(𝐂^N+𝐂^S)^1𝐂_\beta (𝐂^N+𝐂^S)^1𝐂_\alpha ].$$
(7)
Newton-Raphson only convergences in the domain where the sign of the curvature does not change. But even for one degree of freedom, the Gaussian likelihood encounters an inflection point. Consider

$$2\mathrm{log}=\mathrm{log}(2\pi )2\mathrm{log}(\sigma )\frac{\mathrm{\Delta }^2}{\sigma ^2}.$$
(8)
We solve the equation

$$f(\sigma )\frac{1}{\sigma }\frac{\mathrm{\Delta }^2}{\sigma ^3}=0.$$
(9)
The solution is $`\sigma ^2=\mathrm{\Delta }^2`$, as one would expect. In one dimension the Jacobian is the derivative, $`f^{}(\sigma )=1/\sigma ^2+3\mathrm{\Delta }^2/\sigma ^4`$, which changes sign when $`\sigma ^2=3\mathrm{\Delta }^2`$. So the Newton-Raphson iteration (5) moves towards the correct root for guesses within a factor of 3 the true solution, but moves towards infinity for guesses that are too large.

An alternate representation is in terms of weighted quadratic estimators, where one first weights data by $`𝐖`$ and defines raw estimators $`q_\alpha `$ as

$$q_\alpha \mathrm{\Delta }^t𝐖^t𝐂_\alpha 𝐖\mathrm{\Delta }\mathrm{Tr}[\mathrm{𝐖𝐂}_\alpha 𝐖C_N].$$
(10)
The estimators of power $`\stackrel{~}{p}_\alpha =F_{\alpha \beta }^1q_\beta `$. A Wiener filter choice is $`𝐖=(𝐂^N+𝐂^S)^1`$. If interpreted in terms of the maximum likelihood iteration (5), it amounts to an initial guess $`p_\beta ^0=0`$, with residual $`f_\alpha =q_\alpha `$. We used the expectation value $`𝐆=𝐅`$. This converges after a single iteration. Of course, we had assumed that we already knew the optimal weights for the Wiener filter. The quadratic estimator (10) does not have convergence limitations. One can start with an approximate guess for the covariance $`𝐂^S`$, and iterate.

In both the maximum likelihood and the quadratic estimation processes, a number of expensive operations are required. The most common one is the solution to the Wiener filter, $`(𝐂^N+𝐂^S)^1\mathrm{\Delta }`$. We will discuss in section 3 how to achieve using a fast algorithm, after which we only need to address the trace evaluation, which we do in section 6.

## 3 Iterative Solution

For stationary processes, the correlation matrices depend only on the separation distance between points. This makes them diagonal in Fourier space. Noise matrices are often diagonal in real space, or in a time stream space. For now we assume that a fast $`𝒪(NlogN)`$ method exists to evaluate the forward operation. In section 7 we present several fast procedures which imlement this.

For concreteness, we assume that the signal correlation is a diagonal matrix in Fourier space, while the noise matrix is diagonal in real space. We concentrate on the problem

$$(𝐒+𝐍)x=y.$$
(11)
The first requirement is that (11) can be evaluated quickly. This is demonstrated for a range of problems in section 4. We will express all vectors in real space. We can evaluate $`y`$ in $`𝒪(N\mathrm{log}(N))`$ operations as $`y=𝐍x+𝐒x`$. The underrelaxed Jacobi iterative solution is

$$x^{n+1}=x^n+(\overline{S}𝐈+𝐍)^1\left[y(𝐒+𝐍)x^n\right].$$
(12)
$`\overline{S}`$ is our relaxation parameter, to be determined below. Define the error of the $`n`$th iteration as the difference between the true solution $`x`$ and the current guess, $`e^n=x^nx`$. Substituting into (12), we have

$$e^n=\left[𝐈(\overline{S}𝐈+𝐍)^1(𝐒+𝐍)\right]^ne^0𝐄^ne^0.$$
(13)
$`𝐄`$ is called the error matrix. We define the spectral radius of a matrix $`𝐌`$ as $`\rho (𝐌)`$ to be the maximum absolute eigenvalue of $`𝐌`$. Since $`\rho (𝐀+𝐁)\rho (𝐀)+\rho (𝐁)`$, the sufficient condition for (13) to converge is

$$\overline{S}\rho (𝐒).$$
(14)
We can prove (14) by expanding the matrix product in (13) into two positive definite terms each with spectral radius less than unity, $`\rho [(\overline{S}𝐈+𝐍)^1𝐍]<1`$ and $`\rho [(\overline{S}𝐈+𝐍)^1𝐒]<1`$. The first inequality is trivial since the two terms are simultaneously diagonal. The second inequality follows by expanding its inverse, and noting that the smallest eigenvalue of the inverse is larger than one.

When $`𝐍`$ is diagonal, we obtain optimal convergence with $`\overline{S}=(S_0+S_{\mathrm{}})/2`$, i.e. the average of the largest and smallest eigenvalue of the noise matrix. For practical purposes, we have never encountered convergence problems with this choice, and always found better convergence than using the hard bound (14).

In real space, (13) can be visualized as follows. We take an error vector $`e^n`$, multiply one copy by the pixel noise, and convolve another copy with the two point correlation function. We add the two resulting vectors, and divide by the pixel noise plus a constant corresponding to the amplification factor for the wave with the largest signal power. We then subtract this from the original vector $`e^n`$. The convergence is rapid if it pointwise converges to zero. The pixels which are slowest to converge are those where the noise is much smaller than $`\overline{S}`$ when we inject a wave corresponding to the smallest eigenvalue of the signal correlation. The worst pixel converges as

$$|e^n|_{\mathrm{}}[1(N_0+S_0)/(N_0+\overline{S})]^n$$
(15)
where $`N_0`$ is the smallest eigenvalue of $`𝐍`$, $`S_0`$ is the smallest eigenvalue of $`𝐒`$, and $`\overline{S}`$ is the largest eigenvalue. It takes $`(N_0+\overline{S})/(N_0+S_0)`$ steps to decrease the error by an $`e`$-fold. The rate is related to the condition number of $`𝐒`$, and the lower limit for $`𝐍`$. It is apparent that choosing $`\overline{S}`$ larger than necessary slows the convergence down.

The convergence rate is limited by the condition number of $`𝐒+𝐍`$. Consider the problem of power spectrum estimation on an irregular region with constant noise. We can express this problem on a larger enclosing domain, and write $`N_{ii}^1=0`$ on the padding region. $`𝐍^1`$ is not invertible in this case. But we can write

$$(\mathrm{𝐒𝐍}^1+𝐈)𝐍x=y.$$
(16)
Setting $`u=𝐍x`$, we first solve (16) for $`u`$, and then evaluate $`x=𝐍^1u`$, where zero entries on the diagonal of $`𝐍^1`$ becomes a non-problem. The problem instead arises when the noise is small. Large and small is defined relative to the signal. Since the signal covers a spectrum of values, we shall use the mean value $`S_M`$ as reference point. We factor $`𝐍=\mathrm{𝐇𝐋}`$, where $`𝐇=𝐍`$ when $`𝐍>S_M`$ and equal to one otherwise. We can now generalize (16) to

$$(\mathrm{𝐒𝐇}^1+𝐋)𝐇x=y,$$
(17)
and define $`u=𝐇x`$. The iterative solution becomes

$$u^{n+1}=u^n+(\overline{S}𝐇^1+𝐋)^1\left[y(\mathrm{𝐒𝐇}^1+𝐋)u^n\right].$$
(18)
The convergence criterion (14) is still a sufficient condition for the Jacobi iteration (18), but may be quite non-optimal. We can instead use an iterative estimate of $`\overline{S}=\rho (\mathrm{𝐒𝐇}^1)`$ using a power iteration. To prove the convergence of (18), we use the same argument as for (14), with the second inequality holding since $`\mathrm{𝐇𝐒}^1𝐇^1`$ is a similarity transformation on $`𝐒`$ which preserves eigenvalues. Should $`𝐒`$ have a large dynamic range, we can similarly factor it $`𝐒=\mathrm{𝐓𝐔}`$

$$(\mathrm{𝐓𝐇}^1+𝐔^1𝐋)𝐇x=𝐔^1y,$$
(19)
with an iteration

$$u^{n+1}=u^n+(\overline{T}𝐇^1+\overline{U}^1𝐋)^1\left[y(\mathrm{𝐓𝐇}^1+𝐔^1𝐋)u^n\right].$$
(20)
A similar argument shows this to be a convergent iteration if we choose $`\overline{T}=\rho (T)`$ and $`\overline{U}=1/\rho (𝐔^1)`$.

The iterative approach also allows us to compute the $`\chi ^2=\mathrm{\Delta }^T(𝐂^N+𝐂^S)^1\mathrm{\Delta }`$ of the solution iteratively, as well as any expression involving the contraction of vectors, such as (10). The likelihood itself requires computing a determinant, which does not fall into this framework. The trace evaluations needed in Equations (4,6) will be addressed below.

## 4 Convolution and boundaries

### 4.1 Multi-level FFT

Consider a point set contained within an irregular domain $`\mathrm{\Omega }`$ with isolated boundary conditions. We imbed this domain $`\mathrm{\Omega }`$ in the smallest enclosing rectangle $`L`$. The multiplication by the signal matrix is just a convolution by the correlation function with isolated boundary conditions, which can be performed using an FFT on a domain twice as wide as $`L`$. The operation $`y=𝐒x`$ sets the value at every point $`y_i`$ to the sum over all points $`x`$ weighted by the correlation function at the separation. We can map any discrete set of points onto a regular grid using an interpolation of some order (Hockney & Eastwood, 1988).

For this iterative technique, we only rely on each of the forward operations to be evaluated rapidly. The operation of the signal on the data can always be performed in $`𝒪(N\mathrm{log}N)`$ time on a spatial grid by considering it a convolution, which can be performed on a tree, even if the geometry is complex, the coordinate system is unevenly sampled, or the coordinates are otherwise not appropriate for a Fourier transform, for example on the celestial sphere. Again, several methods are possible, with tradeoffs in complexity of the algorithm against computational time. As discussed in Padmanabhan et al. (2002), several levels of grids can be employed to accelerate the process. Open boundaries can be implemented, and one can add short range pair summations, much in analogy to N-body codes (Hockney & Eastwood, 1988). If correlations on a whole sphere are desired, a spherical harmonic transform can be applied for convolutions on the coarse grid followed by FFT’s on the fine grids. While spherical harmonic transforms cost $`𝒪(N^{3/2})`$, the base is only the number of coarse grid cells, and one expects to be dominated by the $`𝒪(N\mathrm{log}N)`$ of the fine grid in general.

### 4.2 Tree

Just as in N-body simulations, the optimal algorithm depends on the clustering of points. An alternative way of evaluating the signal correlation applied to a data vector $`𝐒\mathrm{\Delta }`$ is through tree summation. This approach is very general, and does not slow down under strong clustering. A stationary signal correlation is a convolution, and we can express it as

$$u(\stackrel{}{x}_i)𝐒\mathrm{\Delta }=\underset{j}{}\mathrm{\Delta }(\stackrel{}{x}_j)G(|\stackrel{}{x}_i\stackrel{}{x}_j|).$$
(21)
While Equation (21) is an $`N^2`$ process, we note that it can be approximated to high accuracy through a multipole expansion. Points can be bunched together into nodes. Each node has the mean position of its constituent points (center of mass), a quadrupole moment, and the sum the masses. So instead of summing over all points, it is sufficient to sum over a smaller number of nodes. Let us describe the mass distribution of node $`k`$ by $`\rho _k(\stackrel{}{x})`$. The convolution over the node is

$`u(\stackrel{}{x}_i)`$ $``$ $`𝐒\mathrm{\Delta }={\displaystyle \underset{k}{}}{\displaystyle 𝑑x\rho _k(\stackrel{}{x})G(|\stackrel{}{x}_i\stackrel{}{x}|)}`$ (22)
$`=`$ $`{\displaystyle \underset{k}{}}\left[M_kG(|\stackrel{}{x}_i\stackrel{}{x}_k|)+{\displaystyle \rho _k(\stackrel{}{x})r^\alpha r^\beta _\alpha _\beta G(|\stackrel{}{x}_i\stackrel{}{x}_k|)}+𝒪(G^{\prime \prime \prime })\right].`$
The mass $`M_k=\rho _k`$, and dipole term was cancelled by the choice $`\stackrel{}{x}_k=\frac{1}{M_k}\stackrel{}{x}\rho _k(\stackrel{}{x})`$, and The second term in (22) can be rewritten in terms of the quadrupole moments $`Q_{\alpha \beta }=r^\alpha r^\beta \rho _k`$ with $`r^\alpha =\stackrel{}{x}_k^\alpha \stackrel{}{x}^\alpha `$ as

$$u(\stackrel{}{x}_i)=\underset{k}{}\left\{M_kG(|\stackrel{}{x}_i\stackrel{}{x}_k|)+Q_{\alpha \beta }^k\left[(\delta _{\alpha \beta }\widehat{r}^\alpha \widehat{r}^\beta )\frac{G^{}(|\stackrel{}{x}_i\stackrel{}{x}_k|)}{|\stackrel{}{x}_i\stackrel{}{x}_k|}+\widehat{r}^\alpha \widehat{r}^\beta G^{\prime \prime }(|\stackrel{}{x}_i\stackrel{}{x}_k|)\right]+𝒪(G^{\prime \prime \prime })\right\}.$$
(23)
$`\widehat{r}\stackrel{}{r}/|r|`$ is the unit separation between the target point and the node center of mass. By comparing the quadrupole to the monopole, we obtain an estimate of the error in the truncation. Should this error be larger than our tolerance, we break the sum into subcomponents of the node.

The tree needs only be constructed once, so we should invest sufficient computing resources into this step to minimize the truncation errors arising from the tree. One starts by defining a top node, which includes all points. Since our goal is to maximize locality of particles, we shall subdivide each node by cutting it in half by a line perpendicular to the major axis of the quadrupole. We want to place the cut such that the quadrupole of the subnodes is minimized. This cut line can be determined through bisection. One first cuts through the center of mass, and determines the quadrupole of each subnode. We then displace the cutline towards the node with the larger quadrupole. Let $`r_m=\sqrt{\lambda _{\mathrm{max}}}`$ be the square root of the largest eigenvalue of the parent node. We then displace the cutting line by an amount proportional to $`r_m`$ times 1 minus the ratio of quadrupoles of the subnodes. We repeat this process on each subnode until each node contains exactly one point. The resulting binary tree is not balanced, since the number of particles in each child node is not equal. The depth of the tree is not determined in advance.

The truncation error in the quadrupole tree for a power law correlation function $`G(R)R^n`$ is

$$e\frac{r_m^3G^{\prime \prime \prime }(R)}{G(R)}=n(n+1)(n+2)\left(\frac{r_m}{R}\right)^3.$$
(24)
Reducing $`r_m`$ by a factor of two reduces the error by a factor of 8. But the quadrupole is proportional to the node area, so the computational cost has increased a factor of 4. Let $`n_2`$ be the number of desired binary digits of accuracy. Then the quadrupole truncated tree has a computational cost $`(2^{n_2})^{2/3}`$. If very high accuracy is desired, one should go to high multipole order. An order $`n_O`$ multipole evaluation in two spatial dimensions costs $`𝒪(n_O)`$ operations, so the total node cost $`n_O^2`$. At high multipole moments, it makes sense to reduce the node size $`r_m`$ since we gain rapidly. The optimal $`n_O`$ is thus slightly smaller than $`n_2`$. Asymptotically, the cost of the tree slightly less than $`n_2^2`$.

A simple tree decomposition to implement does not use the quadrupole information. For each node, we find the particle which is furthest from the center of mass. We store this distance with each node. We subdivide the node into two subnodes by a cut perpendicular to the line connecting the furthest particle to the center of mass. The cut is chosen such that the two subnodes have an equal number of particles. When walking the tree, we check that the maximal radius of the node is sufficiently smaller than the distance to the node. This tree is faster to build, since no quadrupole evaluations are required, and for each node the bisection only costs linear time in the number of particles in the node. It also minimizes the worst case error at each node.

## 5 Multiscale Acceleration

The convergence rate of equation (18) is primarily limited by the condition number of $`𝐒`$, since the relaxation parameter $`\overline{S}`$ is yields rapid convergence on modes with correlation power close to $`\overline{S}`$. We can, for example, project the error $`𝐞`$ onto the eigenvectors of $`𝐒`$. Since we chose $`\overline{S}`$ to be the largest eigenvalue of $`𝐒`$, the corresponding eigenvector converges to zero error after one iteration. We thus consider breaking the iterative solution into blocks of the eigenspace of $`𝐒`$, for which the corresponding eigenvalues have a small dynamic range. If we can use a different relaxation parameter for each block, the iteration proceeds rapidly. Let us write a complete set of $`n_b`$ band power projection operators $`𝐏_i`$ which sum to the identity matrix. Multiplication by the projection can also be expressed as a convolution, for which the tree algorithm described above can also be used. We generalize the iteration from equation (20)

$$u^{n+1}=u^n+\underset{i}{}(\overline{T}_i𝐇^1+\overline{U}_i^1𝐋)^1𝐏_i\left[y(\mathrm{𝐓𝐇}^1+𝐔^1𝐋)u^n\right].$$
(25)
The error on the iteration is again

$$e^n=\left[𝐈\underset{i}{}(\overline{T}_i𝐇^1+\overline{U}_i^1𝐋)^1𝐏_i(\mathrm{𝐓𝐇}^1+𝐔^1𝐋)\right]^ne^0.$$
(26)
We set the relaxation parameters $`\overline{T}_i=\rho (P_i𝐓)+T_{\mathrm{}}`$ and $`\overline{U}_i=1/\rho (P_i𝐔^1)+U_{\mathrm{}}`$. In the continuous Fourier decomposition limit, we have

$$e^{n+1}(x)=e^n(x)d^2kd^2x^{}\mathrm{exp}[i𝐤(𝐱𝐱^{})]\frac{P(𝐤)+N(𝐱^{})}{P(𝐤)+N(𝐱)}e^n(𝐱^{}).$$
(27)
The error matrix (27) is zero on the diagonal. If there is no signal, $`P(k)=0`$, the error matrix is zero everywhere, and the convergence is exact after one iteration. When the signal is dominant, we can neglect $`N(x)`$, and the error matrix is again zero. Similarly, the error matrix is zero for two elements whenever $`N(x^{})=N(x)`$.

We can solve the error matrix exactly for two degrees of freedom. In this case, we write the noise matrix as

$$𝐍=\left(\begin{array}{cc}n_1& 0\\ 0& n_2\end{array}\right).$$
(28)
The orthogonal Fourier transform matrix $`𝐅`$ is

$$𝐅=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right).$$
(29)
We have two projection matrices

$$𝐏_1=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),𝐏_2=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right).$$
(30)
The signal correlation matrix is

$$𝐒=𝐅^1\left(\begin{array}{cc}s_1& 0\\ 0& s_2\end{array}\right)𝐅.$$
(31)
The error expression is then

$$e^n=\left\{𝐈[((s_1+s_{\mathrm{}})𝐈+𝐍)^1𝐅^1𝐏_1+((s_2+s_{\mathrm{}})𝐈+𝐍)^1𝐅^1𝐏_2](\mathrm{𝐒𝐅}+\mathrm{𝐅𝐍})\right\}^ne^0$$
(32)
For $`s_{\mathrm{}}=0`$, the eigenvalues of this expression can be directly evaluated

$$\lambda =\pm i\frac{(n_1n_2)(s_1s_2)}{\sqrt{(n_1+s_1)(n_2+s_2)(n_1+s_2)(n_2+s_1)}}.$$
(33)
If we take $`n_i`$ and $`s_i`$ to be sorted positively in ascending order, we see the qualitative features of the convergence. Convergence is very rapid if either $`𝐍`$ or $`𝐒`$ is well conditioned. It is poor if $`n_1+s_1`$ is very small compared to all the other differences in the problem, and can even fail to converge if $`|\lambda |>1`$. To treat the most extreme case, we set $`s_1=n_1=0`$. Then the iteration (32) will converge optimally for $`s_{\mathrm{}}\mathrm{min}(s_2,n_2)`$, and the maximal eigenvalue is $`\lambda <1/2`$ for any choice of $`n_2,s_2`$. At least in this scenario, we have shown that even this potentially extremely ill-conditioned system converges rapidly, better than a factor of two on each iteration.

In the continuum limit (27), we can estimate convergence in some limiting cases. If $`N(x^{})P(k)`$ is large the $`k`$ integral turns the power spectrum into a correlation function, $`\xi (𝐱^{}𝐱)/N(𝐱^{})`$, while if it is very small, the matrix element is given by the inverse correlation function $`N(𝐱)\xi ^1(𝐱𝐱^{})`$. In either case, the matrix is very small.

When the signal matrix contains a large number of zero entries, setting $`T_{\mathrm{}}`$ to the mean value of the noise appears to be a robust choice. In general, we break the sum (26) into $`\mathrm{log}_2(𝐒)`$ terms, each of which costs $`𝒪(N\mathrm{log}N)`$ operations.

To test these concepts, we implemented a one dimensional example. 65536 grid points were used with periodic boundary conditions, and a power law signal correlation function $`P(k)=256/k`$, where $`k`$ is the integer wave number on the grid. The noise variance in each grid point is a random number chosen uniformly from 0.35 to 1.35. We first run the straight iteration (12) for 500 iterations. The vector $`\stackrel{}{x}`$ was chosen randomly, from which $`\stackrel{}{y}`$ was computed. We define the scaled infinity error $`e_{\mathrm{}}=|x^nx|_{\mathrm{}}\sqrt{65536/x_i^2}`$. This error is plotted as boxes in figure 1.

In this situation, we have $`\overline{S}128`$, $`S_0=1/256`$ and $`N_0=0.35`$. From equation (15) we expect to take up to about 366 iterations to reduce the error by an $`e`$-fold. This is consistent with the performance seen in figure 1.

Then we applied the multiscale accelerated iteration (25). We chose 16 bands, so the computational cost is about 16 times higher, but the convergence is much better as we see in the crosses in figure 1. The two sets of points have comparable computational cost, and the multiscale converges much better. We note that the convergence rate for the Jacobi iteration scales as the condition number, which is proportionate to the number of grid points, while the multiscale convergence is independent of that. The Jacobi iteration is still very fast compared to a brute force $`N^3`$ solution of this problem. Each of the iterative methods here take a matter of minutes on a workstation, while a brute force method takes of order a year.

It is instructive to compare this multiscale approach to traditional multigrid aceleration methods. We solve an arbitrary linear equation

$$𝐋u=b$$
(34)
for some linear operator $`𝐋`$. The simplest procedure applies a Jacobi iteration

$$u^{n+1/2}=\left(1𝐃^1𝐋\right)u^n+𝐃^1b,$$
(35)
where $`𝐃`$ is the diagonal part of $`𝐋`$. We then have a restriction operator $``$ which maps the vector $`u`$ onto a coarser vector $`u_1=u`$. In this coarser space, we need to have a coarsened version of the operator, denoted $`\stackrel{~}{𝐋}`$, for which we now solve the coarsened system

$$\stackrel{~}{𝐋}u_1^{n+1/2}=\mathrm{\Delta }b_1^{n+1}(b𝐋u^{n+1/2}).$$
(36)
One recursively applies multigrid to this coarsened system. For purposes of analysis, we assume that the coarse grid equation (36) was solved exactly. We inject this coarse grid correction using the coarse-to-fine grid prolongation operator $`𝒫`$

$`u^{n+1}`$ $`=`$ $`𝒫\stackrel{~}{𝐋}^1\mathrm{\Delta }b^{n+1/2}+u^{n+1/2}`$ (37)
$`=`$ $`u^n+\left[𝒫\stackrel{~}{𝐋}^1(1𝐃^1𝐋)+𝐃^1\right](b𝐋u^n).`$
The error can be written as

$$e^n=\left[(1𝒫\stackrel{~}{𝐋}^1𝐋)(1𝐃^1𝐋)\right]^ne^0.$$
(38)
The standard Jacobi iteration only has the right term in parenthesis. For the Laplace operator $`𝐋=^2=k^2`$, we can see in Fourier space that this term is dominated by small $`k`$, i.e. large scales, for which the term is unity, and convergence is slow. But on large scales, the restriction and prolongation operators basically commute with everything, and the first term is very small. So we see that convergence is rapid on all scales for the Laplace operator.

In correlation problems, the linear operator is typically an inverse power of the wave number, $`Lk^n`$, for which the large scales actually converse rapidly, but the small scales don’t. On these small scales, the prolongation and restriction operators introduce large errors, and the convergence is not aided by this multigrid decomposition. One can remedy this problem by multiplying both sides of the equation by a sufficiently large power of $`k`$. Or one can recast the equation (11) as $`(𝐒^1+𝐍^1)𝐍x=𝐒^1y`$, and solve the system using only inverse matrices. But as we had seen in equations (15,33), the convergence is generally limited by a bad condition number on the noise matrix $`𝐍`$. Let us consider the above 2x2 example, choosing the case when $`n_1=s_1=0`$. For the coarse grid, the only conceivable operator is the scalar $`\stackrel{~}{𝐋}=(s_2+n_2)/2`$. The restriction to a one cell coarse grid is the average of the two cells, and vice versa. The iterator error (38) is then

$$e^n=𝐄^ne^0\left[\left(\begin{array}{cc}1& \frac{n_2}{s_2+n_2}\\ 0& \frac{s_2}{s_2+n_2}\end{array}\right)\left(\begin{array}{cc}0& 1\\ \frac{s_2}{s_2+2n_2}& 0\end{array}\right)\right]^ne^0.$$
(39)
The term in the right parentheses is the error for a standard Jacobi iteration without multigrid, and the left term is the multigrid acceleration. In a pure Jacobi iteration, the eigenvalues are $`\lambda =\pm \sqrt{\frac{s_2}{s_2+2n_2}}`$, which tends to 1 as $`n_2`$ tends to zero and is thus slowly convergent in some cases. The combined error matrix has eigenvalues $`\lambda =\frac{s_2(n_2\pm i\sqrt{3n_2+2s_2}\sqrt{5n_2+2s_2})}{2(n_2+s_2)(2n_2+s_2)}`$, which are still always less than one, but approach 1 as $`n_2`$ approaches zero. The full multigrid scheme thus does not solve the illconditioning problem of the noise matrix. As we showed above, the generalized multiscale decomposition proposed here (32) is always well conditioned and converges by a factor of 2 every iteration for any choice of signal or noise. The computational cost of the multiscale method is logarithmically more expensive.

In practice, maps often has ragged edges, defect, and other excisions, which generically give rise to large entries in the noise matrix, and make it ill-conditioned. For polarization maps, large regions of the signal matrix may also be very small (e.g. the $`B`$-mode discussed below). Multigrid methods must bin pixels with widely varying noise, which generically gives rise to convergence problems. The prologation of the inverse of the coarse grid operator $`\stackrel{~}{𝐋}^1`$ does not necessarily cancel the fine grid operator $`𝐋`$ on coarse scales. We conclude that the multiscale procedure proposed here is more general than multigrid.

## 6 Trace Evaluation

Evaluation of Equation (4) requires not only solving linear equations, but also the evaluation of a trace. We propose a rapid evaluation similar to that used in Oh et al. (1999). Consider a vector $`v_i`$ with random elements which are either +1 or -1. Then

$$v_iv_j=\delta _{ij}.$$
(40)
Thus,

$$v^T(𝐂^N+𝐂^S)^1𝐂_\alpha v=\mathrm{Tr}[(𝐂^N+𝐂^S)^1𝐂_\alpha ].$$
(41)
The vector equation on the left only requires solving linear systems, which we can evaluate rapidly.

If we now construct a series of orthogonal vectors $`v`$, then an average over $`N`$ vectors makes (41) exact. We construct an orthogonal sequence by setting the first vector to be +1 for the first half elements, and -1 for the second half, the second vector +1 for the first and third quartile, and -1 on the remainder, etc. We then apply a random shuffle permutation on each vector, which results in a random orthogonal sequence. Each of these operations is $`𝒪(N)`$.

For a diagonal matrix, a single iteration is always exact. For a positive definite matrix, the convergence rate is approximately

$$\frac{|\delta \mathrm{Tr}|}{\mathrm{Tr}}\frac{1}{\sqrt{n}}\frac{\left(\lambda _i^2\right)^{1/2}}{\mathrm{Tr}}$$
(42)
where $`N`$ is the linear size of the matrix, and $`n`$ is the number of iterations. If the eigenvalues are of comparable magnitude, the RHS of (13) is $`1/\sqrt{Nn}`$. In the worst case, all eigenvalues except for one is zero, in which case the convergence is $`1/\sqrt{n}`$.

When we replace the trace by a stochastic estimate as done in equation (41), the corresponding Jacobian (6) in the maximum likelihood solution is no longer symmetric. The strategy to test for the sign of the eigenvalues may fail in this case, since eigenvalues are no longer guaranteed to be real. Empirically, we find that checking the eigenvalues of the symmetrized Jacobian works as a good indicator of convergence problems. When the sign of the eigenvalues is incorrect, we use the symmetrized eigensystem to correct the iteration direction. This symmetrized jacobian only gives first order convergence, instead of the second order expected from the exact Newton-Raphson. So we simply switch to the standard iteration in the vicinity of the solution, and find rapid convergence to machine precision.

## 7 Implementation

We will discuss the implementation for weak lensing and galaxy angular power spectrum analysis. Statistical weak lensing allows a measurement of the gravitational field of the dark matter by measuring the induced alignments of background galaxy shapes. Most recent analyses have relied on the correlation function, which is an inverse noise weighted quadratic estimator. Computing the two point correlation function is in general not an optimal estimator of the power. Being a quadratic estimator, it weights each data bin by only its local noise. Each correlation function bin $`q_i`$ is an inverse noise $`N^1`$ weighted estimator of the data $`\mathrm{\Delta }`$ for a bilinear form $`Q_i`$:

$$q^i=\mathrm{\Delta }^TN^1Q_iN^1\mathrm{\Delta }$$
(43)
while an optimal estimator (10) should have used $`(S+N)^1`$ as its weights instead. In the limit that signal to noise is small, the correlation function is optimal, similarly it is optimal if the signal and noise covariance matrices commute. For weak lensing surveys, on small scales signal to noise is small, while on larger scales the coverage is reasonably uniform, so a correlation function is not a very poor estimator. As described in Pen et al. (2003), the correlation function computation is $`O(N\mathrm{log}N)`$, so is very fast.

Alternatively, one can grid the data and perform optimal analysis as described in Hu & White (2001). Due to the large cost $`O(N^3)`$, large grid cells must be chosen, leading to non-optimality in the binning. The algorithm in this paper combines the advantages of both approaches.

We can consider each galaxy to have two observables, $`g_1,g_2`$, as well as a position. Our goal is to measure the correlations described as two power spectra. The noise on each data points tends to be very large, usually much larger than the signal. In this regime, the straight Jacobi iteration (12) has good convergence according to equation (15), and we may be able to do without multiscale acceleration.

In general, the observed galaxy ellipticity is related to the reduced shear, $`g_i=\gamma _i/(1\kappa )`$, which depends on both the shear $`\gamma `$ and the convergence $`\kappa `$. In weak lensing, $`\kappa 0`$, and we equate the expectation value of the galaxy alignment with the shear. The covariance is

$$g_i(x_\alpha )g_j(x_\beta )=c_{ij}(x_\alpha x_\beta )+\delta _{\alpha \beta }\delta _{ij}g^2/2.$$
(44)
The last term should be the intrinsic ellipticity of the source plane galaxy. But that is not directly observable. The observed ellipticity is the sum of the actual ellipticity and the lensing induced ellipticity. In weak lensing, we will ignore the induced ellipticity. This corresponds to forcing $`c_{ij}(0)=0`$, i.e. forcing the power spectrum to have zero mean.

A generic spin two correlation function $`c_{ij}`$ can be described in terms of two power spectra. The first one, called ’electric’, or ’div-like’ describes the divergence of the polarization field, $`C_l^E`$, and is induced by weak lensing. The second one, called ’magnetic’ or ’curl-like’ describes the curl of the polarization field, $`C_l^B`$. From these, we construct two correlation functions,

$`c_+(\theta )`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle l𝑑lC^E(l)J_0(l\theta )}+C^B(l)J_4(l\theta )`$
$`c_{}(\theta )`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle l𝑑lC^E(l)J_0(l\theta )}C^B(l)J_4(l\theta )`$ (45)
We can express

$$c_{ij}=\left(\begin{array}{cc}c_++c_{}\mathrm{cos}(4\varphi )& c_{}\mathrm{sin}(4\varphi )\\ c_{}\mathrm{sin}(4\varphi )& c_+c_{}\mathrm{cos}(4\varphi )\end{array}\right)$$
(46)
in terms of the angle $`\mathrm{tan}^1\varphi =\mathrm{\Delta }y/\mathrm{\Delta }x`$ between the two galaxy positions.

To test the procedure, we used a real weak lensing survey geometry as described by Pen et al. (2003). The galaxy positions are shown in figure 2, which corresponds to the survey geometry. It is apparent that the geometry is highly irregular, where the survey geometry contributes significantly more power on all scales than the intrinsic cosmic signal. To generate the simulated power spectrum, we randomly rotated the actual galaxies from the survey, and added the shear field from the simulation. The random rotation erases all two point information.

We generated a spin-2 Gaussian random fields consisting of a pure E mode, and sampled that field at the galaxy positions. The mock catalog consists of the original galaxy rotated by a random angle, and with its ellipticity divided by 2 to present a more significant challenge to the condition number. To this we added the Gaussian signal. Our multiscale procedure converged to machine precision after 8 iterations in double precision.

Figure 3 shows the angular power spectrum recovered from a simulated galaxy survey.

We see that the power spectrum of the noise crosses from small at large scales to dominant for $`l>1000`$, so a pure noise weighted correlation analysis is non-optimal at large angular scales.

## 8 Conclusion

We have presented the framework to rapidly and optimally compute power spectra. Its computational cost is $`O(N\mathrm{log}N)`$, and involves a stochastic evaluation of traces. The latter converges to the exact result in $`N`$ iterations, yielding the exact solution in $`O(N^2\mathrm{log}N)`$ operations. In practice, many fewer iterations provide the answer to sufficient accuracy. The stochastic evaluation is also trivially run on a cluster of cheap computers, which are often readily available.

We have presented mathematical estimates of convergence, which is good in most practical applications. For the estimation of weak lensing power, only a few iterations are required to converge to machine precision.

For the upcoming lensing and CMB surveys such as the Canada-France-Hawaii-Telescope-Legacy-Survey, this rapid algorithm will allow an optimal analysis of the data in a tractable amount of computational effort.

I would like to thank Yannick Mellier and Ludovic van Waerbeke for providing the Virmos galaxy data sets.