text:
# Quasiconvex Analysis of Backtracking Algorithms

## 1 Introduction

The topic of exponential-time exact algorithms for hard problems has led to much research in recent years . In contrast to the situation with polynomial time algorithms, one can not significantly increase the size of a solvable instance by waiting for Moore’s law to provide faster computers, so algorithmic improvement is especially important in this area. Several design principles are known for such algorithms, including dynamic programming  and randomized hill climbing , but the most common approach is a simple form of branch-and-bound in which one repeatedly performs some case analysis to find an appropriate structure in the problem instance, and then uses that structure to split the problem into several smaller subproblems which are solved by recursive calls to the algorithm.

As an example of this approach, a graph coloring algorithm of the author  uses a subroutine for listing each maximal independent set of at most $`k`$ vertices ($`k`$-MIS) in an $`n`$-vertex graph. This subroutine (slightly simplified for this example) repeatedly selects and applies one of the following cases:

* If the input graph $`G`$ contains a vertex $`v`$ of degree zero, recursively list each $`(k\mathrm{1})`$-MIS in $`G\{v\}`$ and append $`v`$ to each listed set.
* If the input graph $`G`$ contains a vertex $`v`$ of degree one, with neighbor $`u`$, recursively list each $`(k\mathrm{1})`$-MIS in $`GN(u)`$ and append $`u`$ to each listed set. Then, recursively list each $`(k\mathrm{1})`$-MIS in $`G\{u,v\}`$ and append $`v`$ to each listed set.
* If the input graph $`G`$ contains a path $`v_\mathrm{1}`$-$`v_\mathrm{2}`$-$`v_\mathrm{3}`$ of degree-two vertices, then, first, recursively list each $`(k\mathrm{1})`$-MIS in $`GN(v_\mathrm{1})`$ and append $`v_\mathrm{1}`$ to each listed set. Second, list each $`(k\mathrm{1})`$-MIS in $`GN(v_\mathrm{2})`$ and append $`v_\mathrm{2}`$ to each listed set. Finally, list each $`(k\mathrm{1})`$-MIS in $`G(\{v_\mathrm{1}\}N(v_\mathrm{3}))`$ and append $`v_\mathrm{3}`$ to each listed set. Note that, in the last recursive call, $`v_\mathrm{1}`$ may belong to $`N(v_\mathrm{3})`$ in which case the number of vertices is only reduced by three.
* If the input graph $`G`$ contains a vertex $`v`$ of degree three or more, recursively list each $`k`$-MIS in $`G\{v\}`$. Then, recursively list each $`(k\mathrm{1})`$-MIS in $`GN(v)`$ and append $`v`$ to each listed set.

It is not hard to see that any graph contains at least one of these cases. We can bound the worst-case number of output sets, as a recurrence in the variables $`n`$ and $`k`$:

$$T(n,k)=max\{\begin{array}{c}T(n\mathrm{1},k\mathrm{1})\hfill \\ \mathrm{2}T(n\mathrm{2},k\mathrm{1})\hfill \\ \mathrm{3}T(n\mathrm{3},k\mathrm{1})\hfill \\ T(n\mathrm{1},k)+T(n\mathrm{4},k\mathrm{1})\hfill \end{array}$$

As base cases, $`T(\mathrm{0},\mathrm{0})=\mathrm{1}`$, $`T(n,\mathrm{1})=\mathrm{0}`$, and $`T(n,k)=\mathrm{0}`$ for $`k>n`$. Each term in the overall maximization of the recurrence comes from a case in the case analysis; the recurrence uses the maximum of these terms because, in a worst-case analysis, the algorithm has no control over which case will arise. Each summand in each term comes from a recursive subproblem called for that case. It turns out that, for the range of parameters of interest $`n/\mathrm{4}kn/\mathrm{3}`$, the recurrence above is dominated by its last two terms, and has the solution $`T(n,k)=(\mathrm{4}/\mathrm{3})^n(\mathrm{3}^\mathrm{4}/\mathrm{4}^\mathrm{3})^k`$. We can also find graphs having this many $`k`$-MISs, so the analysis given by the recurrence is tight. Similar but somewhat more complicated multivariate recurrences have arisen in our algorithm for 3-coloring  with variables counting 3- and 4-value variables in a constraint satisfaction instance, and in our algorithm for the traveling salesman problem in cubic graphs  with variables counting vertices, unforced edges, forced edges, and 4-cycles of unforced edges.

These examples of recurrences have all had few enough terms that they can be solved by hand, but Table 1 depicts a recurrence, arising from unpublished work with J. Byskov on graph coloring algorithms, that is complex enough that hand solution seems unlikely. This recurrence was derived through an iterative process, starting from a simple case analysis of the problem, in which the worst cases for the algorithm were repeatedly identified and replaced by a larger number of better cases.

Our interest in this paper is in performing this type of analysis algorithmically: if we are given as input a recurrence such as the ones discussed above, can we efficiently determine its asymptotic solution, and determine which of the cases in the analysis are the critical ones for the performance of the backtracking algorithm that generated the recurrence? We show that the answer is yes, by expressing the problem as a quasiconvex program, a type of generalized linear program studied previously by the author and others with applications including finite element mesh smoothing , brain flat mapping, hyperbolic graph drawing, and conformal meshing , and multi-projector tiled display color gamut equalization . This quasiconvex programming formulation allows us to solve a $`\tau `$-term recurrence in $`O(\tau )`$ steps, each of which involves the solution of a constant number of algebraic equations; alternatively, we can apply any of several numerical hill-climbing techniques, which are guaranteed to converge to the global optimum of a quasiconvex program. We describe one such technique and provide two proof-of-concept implementations of it, one for exploratory analysis using floating point, and another using the XR exact real-number computation package for Python . The algorithms we describe are able to analyze recurrences such as the one in Table 1, producing asymptotic analysis of their behavior (here, we are interested in the asymptotics of $`T(n,\mathrm{0})`$) and identifying the cases that are bottlenecks for that analysis, typically within one or two seconds for a floating point evaluation sufficiently accurate for exploratory analysis of algorithms.

We first began using a weighting technique for upper bounding recurrences of this type in our previous work on graph coloring , without much regard to its completeness or generality until this paper. Despite some searching we have been unable to find relevant prior research on asymptotic analysis of similar multidimensional recurrences.

## 2 Formalization and Statement of Results

We assume that the input to our problem consists of the following items:

* An integer dimension $`d`$.
* A recurrence

$$F(x)=\underset{i}{max}\underset{j}{}F(x\delta _{i,j}),$$

where $`x`$ and $`\delta _{i,j}`$ are vectors in $`Z^d`$, and $`i`$ and $`j`$ are indices ranging over the cases and subproblems of the algorithm to be analyzed. We assume that, as base cases for the recurrence, $`F(\mathrm{0})=\mathrm{1}`$, and $`F(y)=\mathrm{0}`$ when $`y`$ can not reach the zero vector by any expansion of the recurrence.
* A target vector $`t`$ in $`Z^d`$.

The desired output is a description of the asymptotic behavior of the function $`f(n)=F(nt)`$. We call the expressions $`_jF(x\delta _{i,j})`$ terms of the recurrence, and their subexpressions $`F(x\delta _{i,j})`$ summands of the term. Much of what we describe here would generalize without difficulty to non-integer values of $`x`$ and $`\delta _{i,j}`$, and to non-integer multipliers on the summands of each term.

For our Python implementation, we represent the recurrence as a dictionary mapping case names to terms, with each term represented as a list of summands and each summand represented as a $`d`$-tuple of integers. For instance, the cardinality-bounded maximal independent set recurrence discussed in the introduction has the representation shown in Table 2. This Python representation also allows the inclusion of comments in the file containing the recurrence, describing in further detail the case analysis from which the recurrence arises.

We obtain the following results:

* We show that our recurrences can be upper bounded by linear univariate recurrences formed by weighting the variables, and that the optimal set of weights for this upper bound technique can be found efficiently using quasiconvex programming. The optimal basis for the quasiconvex program consists of the terms forming the worst cases for the recurrence.
* We describe a numerical improvement technique for quasiconvex programming, based on multi-gradient descent, and provide two implementations of this technique: one based on floating point arithmetic and capable of running at interactive speeds for exploratory algorithm analysis, and one using an exact arithmetic package for publishable guaranteed worst case bounds.
* We prove lower bounds showing that the upper bounds from our optimal weighting technique are tight to within a polynomial factor.

## 3 Upper Bounds

In this section we describe a weighting technique that can be used to obtain asymptotic upper bounds for our recurrences, and formulate the problem of optimizing the weights in order to obtain the best such upper bound.

Fix a vector $`wR^d`$, such that, for each summand $`F(x\delta _{i,j})`$ of the input recurrence, $`w\delta _{i,j}`$ is positive, let $`y`$ be a real variable, and define

$$F_w(y)=\underset{wxy}{max}F(x).$$

Then it is not hard to see, by using the recurrence for $`F(x)`$ to expand the right hand side of this definition, and interchanging the order in the maximization, that

$$F_w(y)\underset{i}{max}\underset{j}{}F_w(yw\delta _{i,j}).$$

As base cases set $`F_w(y)=\mathrm{1}`$ for $`\mathrm{0}y<min_{i,j}w\delta _{i,j}`$ and $`F_w(y)=\mathrm{0}`$ for $`y<\mathrm{0}`$. This resembles the recurrence defining $`F`$, but with a real instead of vector-valued argument. For linear univariate recurrences similar to this one, standard solution techniques such as generating functions and characteristic polynomials are commonly taught in freshman combinatorics courses. The recurrence for $`F_w`$ is nonlinear because of the maximization, and involves non-integer variables, but the same techniques apply:

###### Lemma 1

$`F_w(y)=O(c_w^y)`$, where $`c_w`$ is the unique positive root of the monotonic function

$$r_w(c)=\mathrm{1}\underset{i}{max}\underset{j}{}c^{w\delta _{i,j}}.$$

It will be convenient later to separate out this analysis into the different terms of the recurrence:

###### Lemma 2

Let $`c_{w,i}`$ denote the unique positive root of the monotonic function $`r_{w,i}(c)=\mathrm{1}_jc^{w\delta _{i,j}}`$. Then $`c_w=max_ic_{w,i}`$.

Since $`F_w`$ was defined as a maximum of values of $`F`$, this technique immediately leads to upper bounds for the target function $`f(n)=F(nt)`$:

###### Lemma 3

Let $`wR^d`$ be such that, for each summand $`F(x\delta _{i,j})`$ of the input recurrence, $`w\delta _{i,j}`$ is positive, and let $`wt=\mathrm{1}`$. Then $`f(n)F_w(n)=O(c_w^n)`$.

We call $`w`$ a weight vector, because if one interprets the coordinates of $`w`$ as weights of the different backtracking algorithm instance features counted by $`x`$, then $`wx`$ is the total weight of the instance. The recurrence for $`F_w`$ and its solution $`O(c_w^n)`$ describes the time for the backtracking algorithm as a function of instance weight. However, different choices of the weight vector will give different upper bounds $`O(c_w^n)`$ on the time used by the backtracking algorithm. Our task now is to select the best weight vector, that is, the one yielding the tightest upper bound. For convenience, we define $`c_w=c_{w,i}=+\mathrm{}`$ when $`w\delta _{i,j}`$ is non-positive for some $`j`$.

## 4 Quasiconvex Programming

In this section we find efficient algorithmic solutions for the optimal weighting problem formulated in the previous section.

A function $`q(w):R^dR`$ is called quasiconvex when its level sets $`q^\lambda =\{wR^dq(x)\lambda \}`$ are all convex. In particular, the points $`w`$ where $`q`$ achieves its minimum value (if a minimum exists) form a convex set, and an approximation to a value achieving the global minimum can be found numerically by local improvement techniques. If the functions $`q_i`$ for $`i`$ in some finite index set $`S`$ are all quasiconvex, then the function $`q_S(w)=max_{iS}q_i(w)`$ is also quasiconvex, and it becomes of interest to find a point where $`q_S`$ achieves its minimum value. Amenta et al.  define quasiconvex programming as a formalization of this search for the minimum of $`q_S`$. Linear programming can be seen as a special case of quasiconvex programming in which all the functions $`q_i`$ are linear.

More formally, Amenta et al. define a nested convex family to be a map $`\kappa (\lambda )`$ from the nonnegative real numbers to compact convex sets in $`R^d`$ such that if $`\lambda _\mathrm{1}<\lambda _\mathrm{2}`$ then $`\kappa (\lambda _\mathrm{1})\kappa (\lambda _\mathrm{2})`$, and such that for all $`\lambda `$, $`\kappa (\lambda )=_{\lambda ^{}>\lambda }\kappa (\lambda ^{})`$. Any nested convex family $`\kappa `$ determines a quasiconvex function $`q_\kappa (w)=inf\{\lambda |w\kappa (\lambda )\}`$ on $`R^d`$, with level sets $`q_\kappa ^\lambda =\kappa (\lambda )`$. Conversely, when $`q`$ is quasiconvex, the closures of the level sets $`q^\lambda `$, restricted to a compact convex subdomain of $`R^d`$, form a nested convex family.

Amenta et al. define a quasiconvex program to be formed by a set of nested convex families $`S=\{\kappa _\mathrm{1},\kappa _\mathrm{2},\mathrm{}\kappa _n\}`$; the task to be solved is finding the value

$$\lambda ^{}(S)=inf\left\{(\lambda ,w)|w\underset{\kappa _iS}{}\kappa _i(\lambda )\right\}$$

where the infimum is taken in the lexicographic ordering, first by $`\lambda `$ and then by the coordinates of $`w`$.

Quasiconvex programs can themselves be seen as a special case of generalized linear programs. These are optimization problems based on an objective function that maps sets to totally ordered values and that satisfies certain axioms ; quasiconvex programs are generalized linear programs because the function $`\lambda ^{}(S)`$ defined above satisfies these axioms . One consequence of this generalized linear programming formulation is that the value of any quasiconvex program is determined by a basis, a subset of the nested convex families with cardinality $`O(d)`$. Another consequence is that, when the dimension $`d`$ is bounded, quasiconvex programs can be solved by dual-simplex based randomized algorithms that perform a number of steps linear in the number of nested convex families in the input, where each step consists of solving a constant-sized subproblem.

As we now show, our problem of finding an optimal weight vector for our input recurrence can be expressed in this quasiconvex programming framework.

###### Lemma 4

Let $`c_{w,i}`$ be as defined in the previous section. Then the function $`q_i(w)=c_{w,i}`$ is quasiconvex.

###### Proof

We must show that $`q_i^\lambda =\{wc_{w,i}\lambda \}`$ is convex. Equivalently, expanding the definition of $`c_{w,i}`$ and using the monotonicity of the function $`r_{w,i}`$, we must show convexity of the set

$$q_i^\lambda =\{wr_{w,i}(\lambda )\mathrm{0}\}=\{w\underset{j}{}c^{w\delta _{i,j}}\mathrm{1}\}.$$

But each summand of the sum in the right expression is an exponential of a linear function of $`w`$, hence convex. A sum of convex functions is convex, and its level set is a convex set.

###### Corollary 1

We can find a pair $`(c,w)`$, where $`c=inf_wc_w`$, $`wt=\mathrm{1}`$, and $`w`$ is a limit point of a sequence $`w_{\mathrm{}}`$ with $`c_w_{\mathrm{}}`$ converging to $`c`$, as a solution to a quasiconvex program.

###### Proof

We form nested convex families from the closures of the level sets of the functions $`q_i(w)=c_{w,i}`$. The result follows from the definition of $`c_w=maxc_{w,i}`$.

###### Theorem 4.1

If $`(c,w)`$ is found as the optimal solution to the quasiconvex program defined as above for a recurrence for $`F(x)`$ with target vector $`t`$, then $`f(n)=F(nt)=O(c^n)`$.

###### Proof

If $`c_{w,i}=c<+\mathrm{}`$ for all terms $`i`$, the result follows from Lemma 3. And if some term has $`w\delta _{i,j}<\mathrm{0}`$, or has more than one summands, then $`c_{w,i}=+\mathrm{}`$ but any sequence $`w_{\mathrm{}}`$ converging to $`w`$ has $`c_w_{\mathrm{}}`$ converging to $`+\mathrm{}`$, so the the upper bound is infinite and the result is vacuously true. The only remaining case is that some terms have a single summand $`\delta _i`$ with $`w\delta _i=\mathrm{0}`$. Such terms can not contribute to asymptotic growth of $`F(nt)`$ and the result follows by applying Lemma 3 to the recurrence formed by omitting them from the definition of $`F`$.

Therefore, we can use quasiconvex programming to find the weight vector $`w`$ yielding the tightest possible upper bound $`O(c^n)`$ on the asymptotic behavior of our recurrences. Further, by finding a basis for the quasiconvex program, we can determine the recurrence terms that are critical for its asymptotics. The restriction $`wt=\mathrm{1}`$ does not affect quasiconvexity, and in fact aids in the solution of our problem by reducing the effective dimension of the quasiconvex program to $`d\mathrm{1}`$.

## 5 Implementation

In this section we discuss two implementations of our optimization algorithms. Our implementations use a numerical improvement technique which we call smooth quasiconvex programming and which will also feature in our later lower bound proof.

As stated earlier, generalized linear programming techniques can be used to solve our quasiconvex programs in $`O(\tau )`$ steps, where $`\tau `$ denotes the number of terms and each step consists of solving a constant sized subproblem. Such a subproblem has only a constant number of potential bases, and we can test a basis by solving an algebraic system of equations in the variables $`c^{w[k]}`$ where $`w[k]`$ denotes the $`k`$th coordinate of $`w`$. However this approach appears likely to be cumbersome in practice. Instead, we implemented a hill-climbing scheme for finding numerically the optimal value $`(c,w)`$ for our quasiconvex program and for certain other quasiconvex programs.

We have in mind two different purposes for an implementation of our analysis algorithm. First, such an implementation could be used for exploratory analysis: computing a rough estimate of the running time of an algorithm, with enough accuracy to determine whether it improves other similar algorithms for the same problem, and determining the worst cases in an algorithm’s case analysis, in order to refine that analysis to produce a better algorithm. For this sort of application, it is important that the running time be fast enough to be usable at interactive or near-interactive speeds; an implementation using floating point arithmetic is appropriate. Second, we would like to be able to publish guaranteed worst-case bounds on algorithms, for which approximate numeric schemes such as floating point that lack error bounds are inappropriate; in this setting the longer running times associated with exact or interval arithmetic may be acceptable.

With these considerations in mind, we implemented our algorithm twice, once using floating point and a second time using XR , an exact real-number computation package for the Python programming language . The results of the second implementation are guaranteed to be valid upper bounds for the recurrence in question. In XR, a real number $`\rho `$ is represented as a data structure that is capable of constructing a multiprecision integer representing the rounded value of $`\mathrm{2}^b\rho `$, for any integer $`b`$; this rounded value is required to be within unit distance of the true value. We extended this package so that it could evaluate as exact real numbers the values $`c_w`$ given an input vector $`w`$ the coordinates of which are also real numbers, by performing an appropriate binary search using the values of the function $`r_w(c)`$. We then implemented a quasiconvex programming algorithm to search for a sequence of vectors $`w_{\mathrm{}}`$ converging to the infimum $`(c,w)`$ of the quasiconvex program. We describe in more detail below our exact arithmetic implementation; our floating point implementation is similar.

If all functions $`q_i(w)`$ are quasiconvex, the function $`q(w)=max_iq_i(w)`$ is itself quasiconvex, so we can apply hill-climbing procedures to find its infimum. However, although in our application the individual functions $`q_i`$ are smooth, their maximum $`q`$ may not be smooth, so it is difficult to apply standard gradient descent techniques. The difficulty may be seen, for instance, in a simpler quasiconvex programming problem: determining the circumradius of a planar point set (Figure 1). A basis for the circumradius problem may consist of either two or three points; the quasiconvex functions used to solve the problem are simply the distances (or squared distances) from each input point, and the function $`q(w)`$ measures the distance from $`w`$ to the farthest point. But if a point set has only two points in its basis, and our hill climbing procedure for circumradius has reached a point $`w`$ equidistant from these two points and near but not on their midpoint, then improvements to the function value $`q(w)`$ may be found only by moving $`w`$ in a narrow range of directions towards the midpoint. Standard gradient descent algorithms may have a difficult time finding such an improvement direction. Similar behavior arises naturally in our recurrence analysis problem. For instance in a recurrence in  for the time bound of a TSP algorithm on cubic graphs, there are only two critical terms despite the problem being defined over a three-dimensional vector space, and these two terms lead to behavior very similar to the circumradius example.

To avoid these difficulties, we use the following algorithm, which we call smooth quasiconvex programming. We assume we are given as input a set of quasiconvex real functions $`q_i(w)`$. Further, we assume that for each $`i`$ we also can compute a vector-valued function $`q_i^{}(w)`$, satisfying the following properties:

1. If $`q_i(x)<q_i(w)`$, then $`(xw)q_i^{}(w)>\mathrm{0}`$, and
2. If $`q_i^{}(w)v>\mathrm{0}`$, then for all sufficiently small $`ϵ>\mathrm{0}`$, $`q_i(w+ϵv)<q_i(w)`$.

For the circumradius example, for instance, $`q_i^{}`$ should be a vector pointing from $`w`$ towards the $`i`$th input point. The requirements on $`q_i^{}`$ can be described geometrically, as follows: we assume that the level set $`q_i^\lambda `$ is a smooth convex set, one that has at each of its boundary points a unique tangent plane. The vector $`q_i^{}(x)`$ is then an inward-pointing normal vector to the tangent plane to $`q_i^{q(x)}`$ at $`x`$ (essentially it is just the negation of the gradient of $`q`$). The functions $`q_i(w)`$ arising in our recurrence analysis problem have this smoothness property, and (as we discuss in more detail in the next section) the vectors $`q_i^{}(w)`$ can be constructed by evaluating the partial derivatives for each of the coordinates of $`x`$ in the expression $`r_{x,i}(c_w)`$ at $`x=w`$.

Our smooth quasiconvex programming algorithm then consists of selecting an initial value for $`w`$, and a desired output tolerance, and repeating the following steps:

1. Compute the set of vectors $`q_i^{}(w)`$, for each $`i`$ such that $`q_i(w)`$ is within the desired tolerance of $`max_iq_i(w)`$.
2. Find a vector $`v`$ such that $`vq_i^{}(w)>\mathrm{0}`$ for each vector $`q_i^{}(w)`$ in the computed set. If no such vector exists, $`q(w)`$ is within the tolerance of its optimal value and the algorithm terminates.
3. Search for a value $`ϵ`$ for which $`q(w+ϵv)q(w)`$, and replace $`w`$ by $`w+ϵv`$.

Our actual implementation augments this procedure by an outer scaling loop that gradually decreases the tolerance, so that multiple terms of the recurrence can influence the computation in step 1 even when the current value of $`w`$ is only a rough approximation to the true optimum. We also terminate the loop when the improvement to $`q(w)`$ becomes much smaller than the tolerance, even when the termination condition of step 2 is not met, in order to handle situations in which the optimal basis is less than full-dimensional.

The search for a vector $`v`$ in step 2 can be expressed as a linear program. However, when the dimension of the quasiconvex program is at most two (equivalently, the number of variables in the recurrence to be solved is at most three) it can be solved more simply by sorting the vectors $`q_i^{}(w)`$ radially around the origin and choosing $`v`$ to be the average of two extreme vectors.

In our implementation of step 3, we perform a doubling search for the largest $`ϵ`$ leading to a smaller value of $`q(w+ϵv)`$, and then reduce the resulting $`ϵ`$ by a factor of two before replacing $`w`$, to attempt to control situations where the value $`w`$ oscillates around the true optimal value.

Both due to our use of exact real arithmetic, and due to the implementation in Python, a relatively slow interpreted language, our exact arithmetic implementation is not fast, taking several hours on a laptop computer to solve moderately sized 3-variable recurrences to 64 bits of precision. However our floating point implementation is able to run at interactive speeds, taking roughly one or two seconds on a recent-model laptop to solve recurrences such as the one in Table 1. We believe that significant improvements in runtime of our exact arithmetic implementation would be possible both by tuning the implementation and by using a faster software base. However it is encouraging that, in the trials we attempted, the algorithm appears to exhibit linear convergence to the correct function value as well as to the optimal weight vector coordinates: the number of iterations of the algorithm appears to be proportional to the number of bits of precision desired.

## 6 Lower Bounds

In this section we prove that the upper bounds found by our optimal weighting technique are tight to within a polynomial factor.

In order to find lower bounds for the asymptotic behavior of our recurrences, it is useful to have the following combinatorial interpretation of their values. For any $`xZ^d`$, let $`i^{}(x)=\mathrm{arg}\mathrm{max}_i_jF(x\delta _{i,j})`$. That is, $`i^{}`$ is the index of the term in the recurrence that determines the value of $`F(x)`$. If $`\mu (x):Z^dZ`$ is any function mapping vectors to recurrence term indices, define an infinite graph $`G_\mu `$, the vertices of which are vectors in $`Z^d`$, with an edge from $`x`$ to $`x\delta _{i,j}`$ whenever $`i=\mu (x)`$ and $`\delta _{i,j}`$ is a summand in term $`i`$ of the recurrence. Let $`\pi _\mu (x)`$ denote the number of paths from $`x`$ to zero in $`G_\mu `$. It is not hard to show by induction that $`\pi _i^{}(x)=F(x)`$, so $`F`$ can be interpreted as counting paths in a graph. Moreover, for any $`\mu `$, $`\pi _\mu (x)F(x)`$. An example of the graph $`G_i^{}`$, for the recurrence discussed in the introduction, is shown in Figure 2; each vertex $`x`$ in the figure is labeled with the number $`\pi _i^{}(x)=F(x)`$. We will find a lower bound for $`F(x)`$ by counting paths in a graph $`G_\mu `$, where $`\mu (x)`$ will not necessarily equal $`i^{}(x)`$.

Let $`\lambda ^{}(S)=(c,w)`$ be the optimal solution to the quasiconvex program formulated earlier for the upper bounds for our recurrence, and let $`B`$ be a basis of the quasiconvex program; that is, a minimal subset of terms of the recurrence such that the quasiconvex program formed from the subset has the same value $`\lambda ^{}(B)=\lambda ^{}(S)`$ as that for the whole recurrence. For any term $`i`$ in $`B`$, and any summand $`j`$ in term $`i`$, let $`p_{i,j}=c^{w\delta _{i,j}}`$, and let $`D_i=p_{i,j}\delta _{i,j}`$.

###### Lemma 5

For any term $`i`$ in $`B`$, $`_jp_{i,j}=\mathrm{1}`$.

###### Proof

If term $`i`$ has only one summand, then it belongs to $`B`$ exactly when $`w\delta _{i,j}=\mathrm{0}`$ and $`p_{i,j}=\mathrm{1}`$. Otherwise, $`q_i(w)`$ is continuous and term $`i`$ can belong to $`B`$ only when $`q_i(w)=c`$. But then $`r_w(c)=\mathrm{1}p_{i,j}=\mathrm{0}`$ since $`q_i`$ is defined as having the value that makes this equation true, so $`p_{i,j}=\mathrm{0}`$.

###### Lemma 6

The vector $`D_i`$ defined above is a scalar multiple of the vector $`q_i^{}`$ defined for the smooth quasiconvex programming algorithm of the previous section.

###### Proof

The vector $`q_i^{}(w)`$ is the vector such that $`q_i(w+ϵv)<w_i(w)`$ (for sufficiently small $`ϵ`$) if and only if $`vq_i^{}>\mathrm{0}`$. Expanding the definition of $`q_i`$, as the value $`c`$ such that $`r_{w,i}(c)=\mathrm{0}`$, we see that $`q_i^{}(w)`$ can equivalently be defined as a vector $`v`$ such that $`r_{w+ϵv,i}(c)>\mathrm{0}`$ (for sufficiently small $`ϵ`$) if and only if $`vq_i^{}>\mathrm{0}`$.Therefore, $`q_i^{}`$ can be computed as the gradient of the vector function $`\varphi (x)=r_{x,i}(c)`$, evaluated at $`x=w`$. Expanding this gradient by computing partial derivatives for each component of its vector argument, we arrive at the definition of $`D_i`$.

###### Lemma 7

There exist values $`b_i`$, $`\mathrm{0}b_i\mathrm{1}`$, so that $`b_i=\mathrm{1}`$ and so that $`b_iD_i`$ is a scalar multiple of the target vector $`t`$.

###### Proof

The smooth quasiconvex programming algorithm of the previous section will find an improvement to solution $`(c,w)`$ whenever there exists $`v`$, perpendicular to $`t`$, having positive dot product with all the vectors $`q_i^{}(w)`$. The pair $`(c,w)`$ used to define $`b_i`$ and $`D_i`$ is assumed optimal, so can not be improved. Therefore, $`v`$ does not exist and the origin must be contained in the convex hull of projections perpendicular to $`t`$ of the vectors $`q_i^{}`$. Any vector in the convex hull of a set of vectors can be expressed as a convex combination of those vectors, and the same convex combination (when viewed in $`R^d`$ rather than its projection perpendicular to $`t`$) has the property stated in the lemma.

We are now ready to describe the graph $`G_\mu `$ used in our lower bound construction. For each $`xZ^d`$, we choose $`\mu (x)`$ to be one of the terms in the basis $`B`$, independently at random, with probability $`b_i`$ for choosing term $`i`$. We then let $`G_\mu `$ be the infinite graph formed from $`\mu `$ as described at the start of the section. For each choice of $`\mu `$ the number of paths $`\pi _\mu (nt)`$ from $`nt`$ to the origin in $`G_\mu `$ forms a valid lower bound for the quantity $`f(n)=F(nt)`$ that we are trying to estimate, so the expected number of paths (averaged over the choice of $`\mu `$) also forms a valid lower bound.

To count the expected number of paths in $`G_\mu `$, we use the following random walk process. Start from the vertex $`nt`$, and then from any vertex $`x`$ choose randomly among the edges leading away from $`x`$, independently for each $`x`$. The set of edges at $`x`$ is in one-to-one correspondence with the summands of term $`\mu (x)`$, and we choose summand $`j`$ with probability $`p_{\mu (x),j}`$. As shown in Lemma 5 these probabilities add to one at each vertex. We continue this random walk process until we reach a vertex $`x`$ with $`wx=\mathrm{0}`$.

###### Lemma 8

If a path from $`nt`$ to the origin can be formed by the random walk described above, it has probability $`c^n`$ of being chosen.

###### Proof

More generally it is easy to show by induction on the length of the path that a path from $`x`$ to $`y`$ has probability $`c^{w(yx)}`$ of being chosen. The result follows from the choice of starting point $`x=nt`$ and the constraint that $`wt=\mathrm{1}`$.

###### Lemma 9

The random walk described above reaches the origin with probability $`\mathrm{\Omega }(n^{(\mathrm{1}d)/\mathrm{2}})`$.

###### Proof

By Lemma 7, the projections perpendicular to $`t`$ of the vertices of the path form an unbiased random walk in $`R^{d\mathrm{1}}`$, with $`O(n)`$ steps of constant size, and the result follows from the standard theory of such walks.

###### Theorem 6.1

$`f(n)=F(nt)=\mathrm{\Omega }(c^nn^{(\mathrm{1}d)/\mathrm{2}})`$.

###### Proof

By Lemmas 8 and 9, there is the given expected number of paths in $`G_\mu `$ from $`nt`$ to the origin. The result follows from the facts that this number of paths is less than the number of paths between the same two vertices in $`G_i^{}`$ (since $`i^{}`$ is defined to maximize the number of paths) and that the number of paths in $`G_i^{}`$ is exactly $`F(nt)`$.

## 7 Conclusions and Open Problems

We have shown that the solution to the recurrence

$$F(x)=\underset{i}{max}\underset{j}{}F(x\delta _{i,j}),$$

for $`x=nt`$ may be upper and lower bounded within a polynomial factor of $`c^n`$, where the number $`c`$ can be computed as the solution to a quasiconvex program defined from the recurrence and the target vector $`t`$.

It would be of interest to tighten these bounds: under what conditions can we determine the correct polynomial adjustment to the bound $`c^n`$? It is consistent with our observations so far that $`F(nt)=\mathrm{\Theta }(c^nn^{(|B|d)/\mathrm{2}})`$ where $`|B|`$ is the cardinality of a basis for the quasiconvex program. For instance this would fit the central binomial coefficients, with $`|B|=\mathrm{1}`$ and $`d=\mathrm{2}`$, as well as the recurrence used as an example at the start of this paper with $`|B|=d=\mathrm{2}`$. However there is too little evidence yet to state such a formula as a conjecture.

More generally, the work here is only a first step towards the automation of backtracking algorithm design and analysis. Perhaps it would also be possible to automatically perform some of the case analysis used to design backtracking algorithms, and to determine the appropriate variables to use in setting up the recurrences used to analyze those algorithms, before automatically solving those recurrences, at least for simple constraint satisfaction type problems. It would also be of interest to find ways of specifying algorithms of this type in such a way that their correctness can be proven automatically, especially in situations where repeated refinement based on our analysis tools has led to highly complex case analysis such as that appearing in Table 1. Also, while we can find tight worst-case bounds on the solution of the recurrence derived from an algorithm, it may not always be possible to construct an instance causing the algorithm itself to have that worst case time bound; it would be useful to determine conditions under which this recurrence-based analysis is tight.

In another direction, the proof of Theorem 6.1 hints at a theory of duality for quasiconvex programs that it would be of interest to explore.

## Acknowledgements

This research was supported in part by NSF grant CCR-9912338. I would like to thank Jesper Byskov and George Lueker for helpful discussions and comments on drafts of this paper, and Keith Briggs for help with programming using XR.


format: text

text:
# Cirrus models for local and high z SCUBA galaxies

## 1 Introduction

The need for several different components to understand the infrared and submillimetre spectral energy distributions (SEDs) of galaxies has been recognized for some time. Rowan-Robinson and Crawford (1989) modelled IRAS galaxy colour-colour diagrams in terms of three components, starburst, cirrus and AGN components. The cirrus component corresponded to the absorption of the general starlight of a galaxy by interstellar dust and reemission in the infrared, as identified in our Galaxy by Low et al (1984). Detailed models for the cirrus component were given by Rowan-Robinson (1992), but these did not include a treatment of the line emission from the PAH component. A model of the infrared emission of the solar neighbourhood that included the effect of small grains and PAHs was presented by Siebnmorgen & Krügel (1992). Efstathiou, Rowan-Robinson & Siebenmorgen (2000; hereafter ERS2000) have given the most detailed model to date of the evolution of the infrared emission from a starburst. In this paper we describe a tool which allows the cirrus emission to be modelled from 0.1-1000 $`\mu `$m and apply it both to local galaxies which have been mapped with SCUBA and to high redshift galaxies found in deep SCUBA surveys at 850 $`\mu `$m. Hitherto there has been a tendency to interpret these SCUBA galaxies as high redshift versions of Arp220, but Rowan-Robinson (2001) has pointed out that submillimetre counts and background radiation are much more naturally understood in terms of cirrus-like emission.

Silva et al (1998) and Granato et al (2000) have given models for infrared SEDs which include both starburst and cirrus components. These models take into account the distribution of dust and stars in the galaxy and incorporate a population synthesis model. The effect of changes in metallicity during the lifetime of a galaxy is also taken into account. The cirrus models we present here are simpler than those of Silva et al (1998) and Granato et al (2000) but appear to be just as good a representation of the observed SEDs of nearby normal galaxies. Starburst models that take into account the distribution of dust and stars were also presented by Krügel & Siebenmorgen (1994) and Siebenmorgen, Krügel & Laureijs (2001).

The layout of this paper is as follows: section 2 describes our cirrus model in detail, section 3 applies this model to nearby galaxies which have been mapped with SCUBA, section 4 discusses the application to high redshift SCUBA galaxies, and section 5 gives our discussion and conclusions.

## 2 The cirrus model

The ingredients of a cirrus model are (1) the input stellar radiation field, which has to be characterized both with regard to its spectrum and its intensity, (2) an interstellar dust model, with assumptions about its distribution and opacity, (3) a radiative transfer treatment of the interaction between the two to generate the output SED. Our goal is to provide a versatile tool which can be used for example in simulations of the galaxy formation history.

For specifying our input stellar radiation field we have used the Galaxy Isochrone Synthesis Spectral Evolution Library (GISSEL, Bruzual & Charlot 1993) that gives the ultraviolet to near infrared spectrum of radiation from a mass of stars as a function of time.

Stars form in dusty molecular clouds and spend a considerable amount of time inside them. During this phase, the stellar radiation is absorbed by molecular cloud dust and reprocessed to the infrared. We use the code of ERS2000 to compute the emission of the stellar population during this phase. The molecular cloud is assumed to disperse $`7.2\times 10^7`$ years after the instantaneous formation of stars inside it. However, well before $`7.2\times 10^7`$ years non-spherical evolution of the molecular cloud may allow a fraction $`f`$ of the starlight to escape without any dust absorption. We assume that this occurs at time $`t_m`$ after star formation. By further assuming that the radiation field in a galaxy is due to a large number of randomly oriented molecular clouds, their average emission (for stars in the age range $`t_m`$ to $`7.2\times 10^7`$ years) is approximately

$$(1f)S_\nu ^s+fS_\nu ^{}$$

where $`S_\nu ^s`$ is the emission from a spherical GMC (as computed by ERS2000) and $`S_\nu ^{}`$ is the emission from the stellar population in the absence of any molecular cloud dust (Bruzual & Charlot). The emission of stars younger than $`t_m`$ or older than $`7.2\times 10^7`$ years is assumed to be $`S_\nu ^s`$ or $`S_\nu ^{}`$ respectively. In fact for most of this paper we have simplified the model by assuming $`f=1`$. The effect of allowing $`f<1`$ is discussed in section 5.

Other parameters which have to be specified are the star formation history function $`\dot{\varphi }_{}(t)`$, the epoch at which this history begins, $`t_i`$, the epoch of observation, $`t`$, and the usual parameters for the stellar IMF. Since the quantity which determines the dust temperature is the intensity of the stellar radiation field, we have chosen to characterise this in terms of the ratio of the bolometric intensity of the radiation field to that in the stellar radiation field in the solar neighbourhood (Mathis et al 1983), $`\psi `$. The star-formation rate, $`\dot{\varphi }_{}(t)`$, is assumed to have an exponential form, with exponential time scale, $`\tau `$, and a Salpeter IMF from 0.1-125 $`M_{}`$ is assumed. The age of the galaxy, $`t_{}tt_i`$, can also be specified.

We use the dust grain model of Siebenmorgen and Krügel (1992), which incorporates a detailed treatment of small grains and PAHs, and then characterize the opacity of the interstellar dust by $`A_V`$. $`A_V`$ determines how much of the uv to near-ir light is absorbed by dust and reemitted in the infrared and submillimetre bands, and therefore controls the ratio of luminosity in the far infrared to the luminosity in the uv to near-ir. If $`A_V<<`$ 1, we are in the optically thin regime and the dust temperature will then be determined by $`\psi `$ and the shape of the input spectrum (determined by the star formation history). For $`A_V1`$ but not $`>>1`$, the dust will modify the emergent optical and uv spectrum significantly, but will still not result in any significant change to the dust temperature along the line of sight to the central plane of the galaxy. We make a further simplifying assumption, that for the purposes of modelling the galaxy’s emergent SED, we can characterize the galaxy by a single average value of $`\psi `$. Strictly speaking we should model the density distribution of both dust and stars and carry out a full radiative transfer calculation to compute the emergent spectrum. The emergent spectrum would essentially be a superposition of spectra corresponding to different values of $`\psi `$ at different locations through the galaxy. In practice we find that a single value of $`\psi `$ characterizes the emergent spectra very adequately.

To summarize, the parameters of the model that have to be set are $`\psi ,\tau ,t_{},A_V,f`$ and $`t_m`$. The parameters $`\tau ,t_{},f`$ and $`t_m`$ determine the shape of the optical SED, with $`A_V`$ determining the reddening to be applied to this and also, in a self-consistent manner, the bolometric luminosity of the infrared emission. $`\psi `$ determines the temperature of the different grain species in the model and hence the shape of the far infrared SED. There is also a slight dependence of grain temperature on the shape of the optical SED. For $`t_{}=0.25`$ Gyrs and $`\tau =6`$ Gyrs the temperature of the large classical grains is in the range 17-24K for $`\psi =1`$ and 28-41K for $`\psi =21`$. Note that the far-infrared emission is dominated by the emission of the largest and coolest grains. For $`t_{}=12.5`$ Gyrs and $`\tau =6`$ Gyrs the corresponding temperature ranges are 16-21K for $`\psi =1`$ and 26-36K for $`\psi =21`$.

Our code and a selection of models is available at http://astro.ic.ac.uk/$``$ane/cirrus-models.html

## 3 Application to nearby galaxies

Dunne & Eales (2001) have given the results of a SCUBA mapping program of 19 galaxies. The far infrared spectrum of four of these (N1614, I Zw 107, IR 1525+36, Arp 220) are obviously dominated by a starburst component. For a further 7 galaxies there is evidence from the 60/850 $`\mu `$m colours that a starburst component is present ($`log_{10}\frac{S(60)}{S(850)}>1.8`$). We also excluded NGC7541 because of the large flux correction applied to the 450$`\mu m`$ data by Dunne & Eales (2001). We have therefore modelled the SEDs of the remaining 7 galaxies, including optical and near infrared data from the literature, in terms of a cirrus component (Figure 1). The parameters for the models are given in Table 1. For NGC1667 we only give the fitted parameters in Table 1. The fits are extremely good and do not show evidence that a more elaborate cirrus model is required. The values of $`\psi `$ range from 2 to 8, and the values of $`A_V`$ range from 0.4 to 0.9. Such values are consistent with the local distribution function for the ratio $`log_{10}(L_{fir}/L_{opt})`$, which peaks at -0.7 and can be fitted with a Gaussian with $`\sigma `$ = 0.24 about this (Rowan-Robinson et al 1987). As pointed out by Rowan-Robinson (1992), the parameter $`\psi `$ is proportional to the mean surface brightness of the galaxy.

## 4 Application to high redshift SCUBA galaxies

The detection of a number of galaxies in blank field surveys with SCUBA et 850 $`\mu `$m (Hughes et al 1998, Eales et al 1999, Barger et al 1999, etc) and the realization that most of these are at redshift $`>`$ 1, with some probably at z $`>`$ 3, has had a big impact on ideas about galaxy formation and evolution. Most attempts to fit the SEDs of these galaxies (Hughes et al 1998, Downes et al 1999, Lutz et al 2001, etc) and most attempts to fit the 850 $`\mu `$m counts and background (Guiderdoni et al 1998, Dole et al 2001, Xu et al 2001, Franceschini et al 2001, Pearson 2001, Granato et al 2001) have assumed that we are looking at a very strongly evolving, deeply dust-embedded starburst population. However Rowan-Robinson (2001) argues that the natural interpretation of the submillimetre counts and background is in terms of a cirrus-type component. How can the latter picture be reconciled with the failure to identify many of the SCUBA galaxies with optical counterparts ? Obviously the dust optical depth must be higher than in local disk galaxies. However that is not an unreasonable expectation at z = 1-3. Calzetti and Heckman (1999) and Pei et al (1999) have predicted how the typical dust opacity in galaxies should evolve with epoch for star-formation histories typical of those derived from uv and infrared surveys. An increase of the average $`A_V`$ in the interstellar medium in galaxies by a factor of 2 or 3 over present-day values at z =1-2 is to be expected, because the increased gas-density in galaxies far outweighs the slight decline in metallicity over the same look-back time.

Here we have selected two samples of SCUBA high-z galaxies from SCUBA blank-field surveys, confining attention to those with the most reliable optical identification: (a) submm galaxies which have been confirmed by submillimetre interferometry (e.g. Lutz et al 2001), (b) submm galaxies from the 8 mJy survey (Scott et al 2001, Fox et al 2001) which have been confirmed by association with radio sources (Ivison et al 2002). For both these samples the optical and near infrared associations should be reasonably secure. For sample (a) we have the added bonus that the reality of the submillimetre source is confirmed.

To make use of the radio data we have extended our model to the radio regime by utilizing the well known far-infrared-radio correlation (Helou et al 1985). For $`\lambda >60\mu m`$ we add to the rest frame model SED $`S_\nu ^r`$ where

$$S_\nu ^r=2.7\times 10^3(2.58S_{60\mu m}+S_{100\mu m})\times (\frac{\nu }{1.4GHz})^{0.8}$$

where $`S_{60\mu m}`$ and $`S_{100\mu m}`$ are the 60 and 100$`\mu m`$ fluxes predicted by the model and $`\nu `$ is the frequency in Hz. The factor $`2.7\times 10^3`$ is the maximum value allowed by the far-infrared-radio correlation (Blain 1999).

The model allows us to self-consistently estimate the star formation rate (SFR) of the objects studied. Assuming $`t_{}=0.25`$Gyrs the SFR is given by

$$SFR=\frac{L_{bol}}{7.88\times 10^9}M_{}yr^1$$

where $`L_{bol}`$ is the bolometric luminosity of the object (in units of solar luminosity) which we obtain by integrating over the whole wavelength range covered by the models.

To test the predictions of our cirrus model we generated a grid of models in which we vary $`\psi `$ (in the range 1-21 in steps of 1) and $`A_V`$ (in the range 0 to 3 in steps of 0.1). For most of the sources in these samples the redshift is unknown so we treat it as a free parameter varying between 0 and 10 in steps of 0.1. For objects with data in only four bands (all of the objects in Lockman East and SMM00266+170) we fix $`\psi `$ to 6. For all the models we assume $`t_{}=0.25Gyrs`$, $`\tau =6`$ Gyrs, $`f=1`$ and $`t_m=0`$.

Minimum $`\chi ^2`$ fits of our cirrus model to the SEDs of these two samples of high z SCUBA galaxies are shown in Figures 2-4, with the parameters of the models given in Table 2. In N2 we model all the objects with robust radio associations except N2850.5 which is a blank field in all optical and near-IR bands, and N2850.13 which is detected only in K. In LE we exclude LE850.12 and LE850.18 which are detected only in the I band. LE850.1 is included in the sample with millimetre interferometry. Fits that exceed the upper limits are rejected. The quoted errors in $`z`$ indicate the spread in $`z`$ for fits with $`\chi ^2`$ less than $`\chi _{min}^2+1`$.

The fits we obtain are generally good. One notable exception is SMM02399-0136 where the high reduced $`\chi ^2`$ is almost entirely due to the radio point. Ivison et al. (1998) find evidence for an AGN in this object. Also, the high fitted value of $`\psi `$ in this object (the maximum value in our grid of models) is perhaps indicative of the presence of a circumnuclear starburst accompanying the AGN in this object. The fits to LE850.3 and LE850.7 (not plotted) are also poor. The steep radio spectrum of these objects may also suggest the presence of an AGN (Ivison et al 2002).

The values of $`\psi `$ are higher, typically, by a factor of 2-3 than the values for local galaxies, and the values of $`A_V`$ are also higher by a factor of 2-3. Although the values of $`A_V`$ are higher than in local galaxies, they are much lower (by one or two orders of magnitude) than would be expected in a typical molecular cloud undergoing a starburst. So these models are radically different from the typical dusty starburst model for these high-redshift submillimetre galaxies. Of course, because the bolometric luminosities correspond to high rates of star-formation, much of the optical and uv light which is illuminating the interstellar dust in our cirrus models is light that has escaped from a starburst region, for example by non-spherically symmetric evolution of the associated HII regions. It is also interesting to note that the $`A_V`$ we infer are comparable to those of molecular clouds in late stages of their evolution (about a few times $`10^7`$ years) as predicted by the starburst evolution model of ERS2000. As pointed out by the latter authors the predicted IRAS colours of these clouds are similar to those of cirrus galaxies.

With a few exceptions we are able to put fairly strong constraints to the redshifts of the sources we model. For SMMS14011+0252 Ivison et al. (2000) report a spectroscopic redshift of 2.56 which is consistent with our model. Smail et al. (2003) give a spectroscopic redshift of 2.38 for N2850.4 which is close to the deduced photometric redshift. For HDF850.1 there are two distinct minima, one at $`z=4.5`$ and one at around $`z=7.1`$. In Table 2 we give the fitted parameters for both models. For LE850.2 there is a broad minimum between $`z=4`$ and $`9`$.

Of the 23 objects in our samples, our models successfully fit the SEDs of 16 of them (70 $`\%`$). For 4 objects (17$`\%`$) we have insufficient data (fewer than 4 bands) to be able to test our model. For these objects we may need a higher optical depth model of the M82 or Arp 220 starburst type or values of $`A_V`$ ($`>3`$) from our cirrus model which are not really consistent with the ’$`A_V`$ not $`>>`$ 1’ requirement of our model. For 3 objects our fitted $`\psi `$ is close to the maximum in the range considered (21). We assumed the age of the starburst $`t_{}`$ = 0.25 Gyr in each case. This will underestimate the contribution of older, low-mass stars in the rest-frame near infrared if present. In the case of N2850.8 we do see evidence for such a near-IR excess.

## 5 Discussion and conclusions

Although the current state of observations of high-z SCUBA galaxies is insufficient to tell whether our models are better or worse than starburst models, the fits shown here demonstrate that it is premature to make an analogy between SCUBA galaxies and dusty ultraluminous starburst galaxies like Arp 220. Quite a modest dust optical depth ($`A_V13`$) combined with the redshifting of the optical and uv radiation is sufficient to explain why these galaxies are faint in the optical.

The inferred bolometric luminosities imply that enhanced star formation has taken place in these galaxies, so even if we are correct that the observed submillimetre emission arises mainly from cirrus emission, ie reemission from dust in the general interstellar medium of the galaxy, it is likely that some optical and ultraviolet light is intercepted by dust in the dense molecular gas from which the stars formed. Such emission would peak at $``$ 50 (1+z) $`\mu `$m and could easily contribute bolometric luminosities comparable to the cirrus luminosities of table 2 without being detectable at present. Estimates of the fraction of optical-uv light which escapes from star-forming regions in the local universe range from 25-50 $`\%`$. In Fig 4 we have also shown fits for a more elaborate model in which newly formed stars are completely shrouded in their molecular cloud for the first $`10^7`$ yrs, 50$`\%`$ of the starlight escapes to illuminate the interstellar dust from $`10^77.2\times 10^8`$ yrs (i.e. $`f=0.5`$ and $`t_m=10^7`$ years) and 100$`\%`$ escapes thereafter (cf the starburst evolution models of ERS2000). The starlight that escapes is reprocessed to the infrared in the same way as the pure cirrus model. We have generated a grid of models spanning the same parameter space in $`A_V`$, $`\psi `$ and $`z`$ as for the pure cirrus model. These models, when observed at 0.25 Gyr from the start of the starburst, are very similar to our pure cirrus models except for additional radiation peaking at 50 $`\mu `$m.

A critical test of our models would be to measure the angular extent of the millimetre or submillimetre sources in high-z galaxies. In our model these should be of order an arcsec, within range of current millimetre-wave interferometers, whereas the obscured nuclear starburst model would imply sizes an order of a magnitude smaller. Of course, this test would not be able to discriminate between our model and a model where star formation takes place in an extended highly obscured starburst.

There is a further factor at work which exaggerates the difference between the SCUBA galaxies and the high-redshift galaxies found in Lyman break surveys (Steidel et al 1999). Assuming that there is a spread in the typical optical depth of the interstellar medium, uv surveys will inevitably be biased towards galaxies with lower than average optical depth, while submm galaxies will be biased towards higher optical depth. According to this picture, if the Lyman break surveys could go a factor 10 deeper they would start to see the SCUBA galaxies, and if the SCUBA surveys could go a factor 10 deeper they would start to see the Lyman break galaxies. This is already hinted at by the analysis of Peacock et al (2000).

## Acknowledgements

This research has made use of the NASA/IPAC Extragalactic Database (NED) which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. The authors are grateful to Steve Warren, Jose Afonso, Stephen Serjeant, Gian Luigi Granato, Toshi Takagi, Dieter Lutz and Alberto Franceschini for their useful comments on an earlier version of this paper. We would also like to thank the anonymous referee for constructive comments and suggestions. Last, but not least, we would like to thank our collaborator Ralf Siebenmorgen for making his code for computing the emission from small grains and PAHs available to us. AE acknowledges support by PPARC.


text:
# Sequences related to the Pell generalized equation

## Abstract

We consider sequences of the type $`A_n=6A_{n1}A_{n2},A_0=r,A_1=s`$ ($`r`$ and $`s`$ integers) and show that all sequences that solve particular cases of the Pell generalized equation are expressible as a constant times one of four particular sequences of the same type.

Let $`\alpha =3+2\sqrt{2},\beta =32\sqrt{2}`$ be the roots of the polynomial $`x^26x+1`$. Note that $`\alpha +\beta =6,\alpha \beta =1,\alpha \beta =4\sqrt{2}`$. Also let $`\gamma =1+\sqrt{2},\delta =1\sqrt{2}`$. Then $`\gamma ^2=\alpha ,\delta ^2=\beta ,\gamma \delta =1`$. We take $`\gamma =\alpha ^{\frac{1}{2}},\delta =\beta ^{\frac{1}{2}}`$.

Consider the sequence $`A_n`$ defined by

$`A_n=6A_{n1}A_{n2},A_0=r,A_1=s,`$ (1)
where $`r`$ and $`s`$ are integers.

The object of this contribution is to show that all sequences of the type given by Equation 1 that solve particular cases of the Pell generalized equation (see ) are expressible as a constant times one of four particular sequences of the same type.

The generating function of $`A_n`$ is given by

$$g(x)=\frac{r+(s7r)x+(6rs)x^2}{(1x)(16x+x^2)},$$

from which we get the closed form

$$A_n=\frac{2s\gamma \alpha 2r\gamma }{8\sqrt{2}\gamma ^3}\alpha ^n\frac{2r\gamma \beta +2s\delta \beta }{8\sqrt{2}\delta ^3}\beta ^n.$$

Two important particular cases of Equation 1 are the sequences

$$T_n=\frac{\alpha ^n\beta ^n}{4\sqrt{2}},$$
(2)
$$L_n=\alpha ^n+\beta ^n.$$
(3)
The initial conditions are, respectively, $`T_0=0,T_1=1,`$ and $`L_0=2,L_1=6`$. They are, respectively, sequences A001109 and A003499 in . $`T_n`$ is related to triangular numbers: see . The relationships between $`T_n`$ and $`L_n`$ are of the same genre as those between Fibonacci and Lucas numbers: so a wealth of known identities relating Fibonacci and Lucas numbers translates to our pair.

Now we establish some identities concerning $`\alpha `$ and $`\beta `$ that allow us to introduce the other sequences necessary for our argument. First note that from $`\alpha +\beta +2\sqrt{\alpha \beta }=8`$ it follows $`\left(\alpha ^{\frac{1}{2}}+\beta ^{\frac{1}{2}}\right)^2=8`$, that is $`\alpha ^{\frac{1}{2}}+\beta ^{\frac{1}{2}}=2\sqrt{2}`$. Also from $`\alpha +\beta 2\sqrt{\alpha \beta }=4`$ it follows $`\left(\alpha ^{\frac{1}{2}}\beta ^{\frac{1}{2}}\right)^2=4`$, that is $`\alpha ^{\frac{1}{2}}\beta ^{\frac{1}{2}}=2`$. Then

1. $$\left(\alpha ^{n+\frac{1}{2}}+\beta ^{n+\frac{1}{2}}\right)\left(\alpha ^{\frac{1}{2}}\beta ^{\frac{1}{2}}\right)=\alpha ^{n+1}\alpha ^n+\beta ^n\beta ^{n+1},$$

from which we get

$$\frac{\alpha ^{n+\frac{1}{2}}+\beta ^{n+\frac{1}{2}}}{2\sqrt{2}}=T_{n+1}T_n=B_n,$$

which is sequence A001653 in . We have $`B_0=1,B_1=5`$.
2. $$\left(\alpha ^{n+\frac{1}{2}}+\beta ^{n+\frac{1}{2}}\right)\left(\alpha ^{\frac{1}{2}}+\beta ^{\frac{1}{2}}\right)=\alpha ^{n+1}+\alpha ^n+\beta ^n+\beta ^{n+1}.$$

Then

$`\sqrt{2}\left(\alpha ^{n+\frac{1}{2}}+\beta ^{n+\frac{1}{2}}\right)`$ $`=`$ $`{\displaystyle \frac{\alpha ^{n+1}+\alpha ^n+\beta ^n+\beta ^{n+1}}{2}}`$
$`=`$ $`{\displaystyle \frac{L_{n+1}+L_n}{2}}`$
$`=`$ $`E_n,`$
which is sequence A077445 in . We have $`E_0=4,E_1=20`$. We see that $`E_n=4B_n`$.
3. $$\left(\alpha ^{n+\frac{1}{2}}\beta ^{n+\frac{1}{2}}\right)\left(\alpha ^{\frac{1}{2}}+\beta ^{\frac{1}{2}}\right)=\alpha ^{n+1}+\alpha ^n\beta ^n\beta ^{n+1}.$$

From this we get

$$\alpha ^{n+\frac{1}{2}}\beta ^{n+\frac{1}{2}}=2(T_{n+1}+T_n)=C_n.$$

This is sequence A077444 in . We have $`C_0=2,C_1=14`$. We can write as well

$$C_n=\gamma ^{2n+1}+\delta ^{2n+1}.$$

Then $`\frac{C_n}{2}`$ are the NSW numbers (sequence A002315 in , also see ). Also $`\frac{C_n}{2}=R_{2n+1}`$, where the $`R_n`$ sequence gives the numerators of continued fraction convergents to $`\sqrt{2}`$ (sequence A001333 in ).
4. $$\left(\alpha ^{n+\frac{1}{2}}\beta ^{n+\frac{1}{2}}\right)\left(\alpha ^{\frac{1}{2}}\beta ^{\frac{1}{2}}\right)=\alpha ^{n+1}\alpha ^n\beta ^n+\beta ^{n+1}.$$

From this we get

$$\alpha ^{n+\frac{1}{2}}\beta ^{n+\frac{1}{2}}=\frac{L_{n+1}L_n}{2}=C_n.$$

Now we are going to study in more details the $`L_n`$ sequence. In the $`L_n`$ sequence there are hidden some sequences of squares. More precisely, we have that $`L_{2n}+2,\mathrm{\hspace{0.17em}2}(L_{2n}2),L_{2n+1}2,\mathrm{\hspace{0.17em}2}(L_{2n+1}+2)`$ are perfect squares.

1. $`L_n^2`$ $`=`$ $`(\alpha ^n+\beta ^n)^2`$
$`=`$ $`\alpha ^{2n}+\beta ^{2n}+2`$
$`=`$ $`L_{2n}+2.`$
2. $`(8T_n)^2`$ $`=`$ $`64\left({\displaystyle \frac{\alpha ^n\beta ^n}{4\sqrt{2}}}\right)^2`$
$`=`$ $`2(\alpha ^{2n}+\beta ^{2n}2)`$
$`=`$ $`2(L_{2n}2).`$
3. $`L_{2n+1}2`$ $`=`$ $`\alpha ^{2n+1}+\beta ^{2n+1}2`$
$`=`$ $`\left(\alpha ^{n+\frac{1}{2}}\beta ^{n+\frac{1}{2}}\right)^2`$
$`=`$ $`C_n^2.`$
4. $`2(L_{2n+1}+2)`$ $`=`$ $`2(\alpha ^{2n+1}+\beta ^{2n+1}+2)`$
$`=`$ $`\left(\sqrt{2}\left(\alpha ^{n+\frac{1}{2}}+\beta ^{n+\frac{1}{2}}\right)\right)^2`$
$`=`$ $`E_n^2.`$

Also we obtain easily

$$4(8T_n^2+1)=L_{2n}+2=L_n^2,$$
(4)
$$2C_n^2+8=2(L_{2n+1}+2)=E_n^2,$$
(5)
and finally

$$4(2B_n^21)=L_{2n+1}2=C_n^2,$$
(6)
which means that $`8T_n^2+1,\mathrm{\hspace{0.17em}2}C_n^2+8`$ and $`2B_n^21`$ are perfect squares.

After some tedious algebra we can write the following formula involving the square of $`A_n`$:

$$32A_n^2+2(r^2+s^26rs)=(r^2s^2)L_{2n2}+(6s^22rs)L_{2n1}.$$
(7)
We would like to find conditions on $`r`$ and $`s`$ under which the LHS can be reduced to a perfect square. This happens only if we can find values of $`r`$ and $`s`$ for which the RHS can be written as a constant times $`L_n`$ for some $`n`$: this because of the results obtained before for $`L_n`$. In this case we would have solutions to particular generalized Pell equations.

The first elementary cases arise when we set equal to zero one of the two coefficients on the RHS. If we set $`r^2=s^2`$ we get $`s=\pm r`$. If $`s=r`$ then $`A_0=r,A_1=r,A_2=5r,A_3=29r,\mathrm{}`$ so we can conclude $`A_n=rB_{n1}`$. If $`s=r`$ then $`A_0=r,A_1=r,A_2=7r,A_3=41r,\mathrm{}`$ so we can conclude $`A_n=r\frac{C_{n1}}{2}`$.

If we set $`6s^22rs=0`$ we obtain $`s=0`$ or $`3s=r`$. If $`s=0`$ then $`A_0=r,A_1=0,A_2=r,A_3=6r,\mathrm{}`$ so we can conclude $`A_n=rT_{n1}`$. If $`3s=r`$, setting $`r=3k`$ we have $`A_0=3k,A_1=k,A_2=3k,A_3=17k,\mathrm{}`$ so that $`A_n=k\frac{L_{n1}}{2}`$.

Now let $`a_0=2rs6s^2,a_1=r^2s^2`$ and define the recurrence

$$a_n=6a_{n1}a_{n2},n2.$$

Then

$`32A_n^2+2(r^2+s^26rs)`$ $`=`$ $`a_1L_{2n2}a_0L_{2n1}`$
$`=`$ $`a_1(6L_{2n1}L_{2n})a_0L_{2n1}`$
$`=`$ $`(6a_1a_0)L_{2n1}a_1L_{2n}`$
$`=`$ $`a_2L_{2n1}a_1L_{2n}`$
$`=`$ $`a_2(6L_{2n}L_{2n+1})a_1L_{2n}`$
$`=`$ $`(6a_2a_1)L_{2n}a_2L_{2n+1}`$
$`=`$ $`a_3L_{2n}a_2L_{2n+1}`$
$`=`$ $`\mathrm{}\mathrm{}\mathrm{}`$
So in general we have

$$32A_n^2+2(r^2+s^26rs)=a_{m+3}L_{2n+m}a_{m+2}L_{2n+m+1},m=2,1,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1}\mathrm{}$$

Our problem is solved if for some integer $`h`$

$$a_{m+2}=6h=T_2h,a_{m+3}=h=T_1h,$$

since then

$`32A_n^2+2(r^2+s^26rs)`$ $`=`$ $`hL_{2n+m}+6hL_{2n+m+1}`$
$`=`$ $`hL_{2n+m+2}.`$
Now

$`a_{m+1}`$ $`=`$ $`6a_{m+2}a_{m+3}`$
$`=`$ $`6T_2h+T_1h`$
$`=`$ $`T_3h,`$
$`a_m`$ $`=`$ $`6a_{m+1}a_{m+2}`$
$`=`$ $`6T_3h+T_2h`$
$`=`$ $`T_4h,`$
and so on. Then the conditions are

$$a_0=T_{m+4}h,a_1=T_{m+3}h.$$

For sake of simplicity, write $`T_{m+4}=t_1,T_{m+3}=t_0`$. So we have

$$2rs6s^2+t_1h=0,$$
(8)
$$r^2s^2+t_0h=0.$$
(9)
Solving for $`r`$ Equation 8 and solving for $`h`$ Equation 9 after insertion of the value for $`r`$ we get

$$h=\frac{2(s^2t_0+3s^2t_1\pm s^2)}{t_1^2}.$$

In obtaining this result we used the identity

$$T_n^26T_nT_{n+1}+T_{n+1}^2=1.$$

This can be proved in the following way:

$$T_n^2=\frac{\alpha ^{2n}+\beta ^{2n}2}{32},T_{n+1}^2=\frac{\alpha ^{2n+2}+\beta ^{2n+2}2}{32},$$

$$T_nT_{n+1}=\frac{\alpha ^{2n+1}+\beta ^{2n+1}6}{32}.$$

Then

$$T_n^26T_nT_{n+1}+T_{n+1}^2=\frac{1}{32}(L_{2n}+L_{2n+2}6L_{2n+1}+32),$$

but

$$L_{2n}+L_{2n+2}6L_{2n+1}=0,$$

from which the desired identity.

If in $`h`$ we take the plus sign and insert into the expression for $`r`$ we get

$$r=\frac{s(t_01)}{t_1}.$$
(10)
On the other hand if we take the minus sign we obtain

$$r=\frac{s(t_0+1)}{t_1}.$$
(11)
Next we will prove the following identities

$$T_{2n+1}B_{n1}=(1+T_{2n})B_n,$$
(12)
$$T_{2n}L_{n1}=(1+T_{2n1})L_n.$$
(13)
Identity 12:

$`T_{2n+1}B_{n1}`$ $`=`$ $`{\displaystyle \frac{\alpha ^{2n+1}\beta ^{2n+1}}{4\sqrt{2}}}{\displaystyle \frac{\alpha ^{n\frac{1}{2}}+\beta ^{n\frac{1}{2}}}{2\sqrt{2}}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{3n+\frac{1}{2}}+\alpha ^{2n+1}\beta ^{n\frac{1}{2}}\alpha ^{n\frac{1}{2}}\beta ^{2n+1}\beta ^{3n+\frac{1}{2}}}{16}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{3n+\frac{1}{2}}+\alpha ^{n+1+\frac{1}{2}}\beta ^{n+1+\frac{1}{2}}\beta ^{3n+\frac{1}{2}}}{16}},`$
where we used several times the fact that $`\alpha \beta =1`$.

$`B_n(1+T_{2n})`$ $`=`$ $`{\displaystyle \frac{\alpha ^{n+\frac{1}{2}}+\beta ^{n+\frac{1}{2}}}{2\sqrt{2}}}+{\displaystyle \frac{\alpha ^{3n+\frac{1}{2}}\alpha ^{n+\frac{1}{2}}\beta ^{2n}+\alpha ^{2n}\beta ^{n+\frac{1}{2}}\beta ^{3n+\frac{1}{2}}}{16}}`$
$`=`$ $`{\displaystyle \frac{4\sqrt{2}\alpha ^{n+\frac{1}{2}}+4\sqrt{2}\beta ^{n+\frac{1}{2}}}{16}}+`$
$`+{\displaystyle \frac{\alpha ^{3n+\frac{1}{2}}\alpha ^{n+\frac{1}{2}}\beta ^{2n}+\alpha ^{2n}\beta ^{n+\frac{1}{2}}\beta ^{3n+\frac{1}{2}}}{16}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{n+1+\frac{1}{2}}\alpha ^{n+\frac{1}{2}}\beta +\alpha \beta ^{n+\frac{1}{2}}\beta ^{n+1+\frac{1}{2}}}{16}}+`$
$`+{\displaystyle \frac{\alpha ^{3n+\frac{1}{2}}\alpha ^{n+\frac{1}{2}}\beta ^{2n}+\alpha ^{2n}\beta ^{n+\frac{1}{2}}\beta ^{3n+\frac{1}{2}}}{16}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{3n+\frac{1}{2}}+\alpha ^{n+1+\frac{1}{2}}\beta ^{n+1+\frac{1}{2}}\beta ^{3n+\frac{1}{2}}}{16}},`$
where we used again $`\alpha \beta =1`$ and $`\alpha \beta 4\sqrt{2}`$. Hence

$$T_{2n+1}B_{n1}=(1+T_{2n})B_n=\frac{C_{3n}+C_{n+1}}{16}.$$

Identity 13:

$`T_{2n}L_{n1}`$ $`=`$ $`{\displaystyle \frac{\alpha ^{2n}\beta ^{2n}}{4\sqrt{2}}}(\alpha ^{n1}+\beta ^{n1})`$
$`=`$ $`{\displaystyle \frac{\alpha ^{3n1}+\alpha ^{2n}\beta ^{n1}\alpha ^{n1}\beta ^{2n}\beta ^{3n1}}{4\sqrt{2}}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{3n1}+\alpha ^{n+1}\beta ^{n+1}\beta ^{3n1}}{4\sqrt{2}}}.`$
$`(1+T_{2n1})L_n`$ $`=`$ $`\alpha ^n+\beta ^n+(\alpha ^n+\beta ^n){\displaystyle \frac{\alpha ^{2n1}\beta ^{2n1}}{4\sqrt{2}}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{n+1}\alpha ^n\beta +\alpha \beta ^n\beta ^{n+1}}{4\sqrt{2}}}+`$
$`+{\displaystyle \frac{\alpha ^{3n1}\alpha ^n\beta ^{2n1}+\alpha ^{2n1}\beta ^n\beta ^{3n1}}{4\sqrt{2}}}`$
$`=`$ $`{\displaystyle \frac{\alpha ^{3n1}+\alpha ^{n+1}\beta ^{n+1}\beta ^{3n1}}{4\sqrt{2}}}.`$
Hence

$$T_{2n}L_{n1}=(1+T_{2n1})L_n=T_{3n1}+T_{n+1}.$$

Along these lines we can prove these two other identities

$$(T_{2n}1)C_n=T_{2n+1}C_{n1}=\frac{B_{3n}B_{n+1}}{2},$$
(14)
$$(T_{2n+1}1)T_{n+1}=T_nT_{2n+2}=\frac{L_{3n+2}L_{n+2}}{32}.$$
(15)
Going back to Equation 10 if $`m=2k`$ we get using Identity 15

$$\frac{s}{r}=\frac{T_{k+2}}{T_{k+1}},$$

from which

$$r=\mu T_{k+1}=A_0,s=\mu T_{k+2}=A_1,$$

so that $`A_n=\mu T_{n+k+1}.`$ If $`m=2k+1`$ we get using Identity 14

$$\frac{s}{r}=\frac{C_{k+2}}{C_{k+1}},$$

from which

$$r=\mu C_{k+1}=A_0,s=\mu C_{k+2}=A_1,$$

so that $`A_n=\mu C_{n+k+1}.`$ On the other hand in the case of Equation 11 if $`m=2k`$ we get using Identity 9

$$\frac{s}{r}=\frac{L_{k+2}}{L_{k+1}},$$

from which

$$r=\mu L_{k+1}=A_0,s=\mu L_{k+2}=A_1,$$

so that $`A_n=\mu L_{n+k+1}.`$ Finally if $`m=2k+1`$ we get using Identity 8

$$\frac{s}{r}=\frac{B_{k+2}}{B_{k+1}},$$

from which

$$r=\mu B_{k+1}=A_0,s=\mu B_{k+2}=A_1,$$

so that $`A_n=\mu B_{n+k+1}.`$

The conclusion is that any sequence we looked for is expressible as a constant times one of the four sequences $`L_n`$, $`T_n`$, $`B_n`$ and $`C_n`$.


text:
# Untitled Document

SIMPLE MODULES OVER THE HIGHER RANK

SUPER-VIRASORO ALGEBRAS

(Appeared in Lett.Math.Phys. 53 (2000), 263-272)

Yucai Su111Supported by a grant from National Educational Department of China

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

Email: ycsu@sjtu.edu.cn

Abstract. It is proved that uniformly bounded simple modules over higher rank super-Virasoro algebras are modules of the intermediate series, and that simple modules with finite dimensional weight spaces are either modules of the intermediate series or generalized highest weight modules.

Mathematics Subject Classification (2000): 17B68, 17B70, 17B65

Keywords: higher rank super-Virasoro algebra, uniformly bounded module, module of the intermediate series, generalized highest weight module.

§1. Introduction

The Virasoro algebra Vir, playing a fundamental role in two dimensional conformal quantum field theory, is the universal central extension of the complex Lie algebra of the polynomial vector fields on the circle . The notion of higher rank Virasoro algebras and the notion of higher rank super-Virasoro algebras were introduced in  and the notions of generalized Virasoro and super-Virasoro algebras were introduced in . Kac  conjectured a theorem that a simple Vir-module with finite dimensional weight spaces is either a module of the intermediate series or else a highest or lowest weight module. This theorem was partially proved in  and fully proved in  and then generalized to the super-Virasoro algebras in , and was in some sense generalized to the higher rank Virasoro algebras in . In this paper, we shall obtain a similar result for the higher rank super-Virasoro algebras, thus completing the proof of the theorem conjectured by the author in . In \[12,\] by using the above mentioned theorem, we gave a theorem on indecomposable Vir-modules. Using our result here, we shall have a better understanding on the simple modules over the higher rank super-Virasoro algebras and it may be possible to give in some extent a classification of the uniformly bounded modules over the higher rank super-Virasoro algebras. This is also our motivation to present the result here.

Let $`n`$ be a positive integer. Let $`M`$ be an $`n`$-dimensional $`ZZ`$-submodule of $`C\text{ }\text{ }`$, and let $`sC\text{ }\text{ }`$ such that $`2sM`$. The rank $`n`$ super-Virasoro algebra (or a higher rank super-Virasoro algebra if $`n2`$) is the Lie superalgebra $`\text{SVir}\text{[}M,s\text{]}=\text{SVir}_0\text{SVir}_1`$, where SVir$`_0`$ has a basis $`\{L_\mu ,c|\mu M\}`$ and SVir$`_1`$ has a basis $`\{G_\eta |\eta s+M\}`$, with the commutation relations

$$\begin{array}{cc}[L_\mu ,L_\nu ]=(\nu \mu )L_{\mu +\nu }\delta _{\mu +\nu ,0}\frac{\mathrm{\hspace{0.17em}1}}{12}(\mu ^3\mu )c,& [L_\mu ,G_\eta ]=(\eta \frac{\mu }{2})G_{\mu +\eta },\\ [G_\eta ,G_\lambda ]=2L_{\eta +\lambda }\delta _{\eta +\lambda ,0}\frac{\mathrm{\hspace{0.17em}1}}{3}(\eta ^2\frac{\mathrm{\hspace{0.17em}1}}{4})c,& [L_\mu ,c]=[G_\eta ,c]=0,\end{array}$$
$`(1.1)`$
for $`\mu ,\nu M,\eta ,\lambda s+M.`$ Then SVir$`_0`$ is the higher rank Virasoro algebra SVir\[$`M`$\]. It is proved in  that a module of the intermediate series (i.e., a module with all the dimensions of the weight spaces of “even” or “odd” part are $`1`$) over SVir\[$`M,s`$\] is one of the three series of the modules $`SA_{a,b},SA_a^{},SB_a^{}`$ or their quotient modules for suitable $`a,b,a^{}C\text{ }\text{ }`$, where $`SA_{a,b},SA_a^{}`$ have basis $`\{x_\mu |\mu M\}\{y_\eta |\eta s+M\}`$ and $`SB_a^{}`$ has basis $`\{x_\eta |\eta s+M\}\{y_\mu |\mu M\}`$ such that $`c`$ acts trivially and such that

$$\begin{array}{c}\begin{array}{ccc}SA_{a,b}:& L_\mu x_\nu =(a+\nu +\mu b)x_{\mu +\nu },& L_\mu y_\eta =(a+\eta +\mu (b\frac{\mathrm{\hspace{0.17em}1}}{2}))y_{\mu +\eta }\\ & G_\lambda x_\nu =y_{\lambda +\nu },& G_\lambda y_\eta =(a+\eta +2\lambda (b\frac{\mathrm{\hspace{0.17em}1}}{2}))x_{\lambda +\eta }\end{array}\\ \begin{array}{cccc}SA_a^{}:& L_\mu x_\nu =(\nu +\mu )x_{\mu +\nu },\nu 0,& L_\mu v_0=\mu (\mu +a^{})v_\mu ,& L_\mu y_\eta =(\eta +\frac{\mu }{2})y_{\mu +\eta }\\ & G_\lambda x_\nu =y_{\lambda +\nu },\nu 0,& G_\lambda x_0=(2\lambda +a^{})y_\lambda ,& G_\lambda y_\eta =(\eta +\lambda )x_{\lambda +\eta }\end{array}\\ \begin{array}{cccc}SB_a^{}:& L_\mu x_\eta =(\eta +\frac{\mu }{2})x_{\mu +\eta },& L_\mu y_\nu =\nu y_{\mu +\nu },\nu \mu ,& L_\mu y_\mu =\mu (\mu +a^{})y_0,\\ & G_\lambda x_\eta =y_{\lambda +\eta },\eta \lambda ,& G_\lambda x_\lambda =(2\lambda +a^{})y_0,& G_\lambda y_\nu =\nu x_{\lambda +\nu },\end{array}\end{array}$$
$`\begin{array}{c}(1.2\mathrm{a})\\ \\ \\ (1.2\mathrm{b})\\ \\ \\ (1.2\mathrm{c})\end{array}`$
for $`\mu ,\nu M,\lambda ,\eta s+M`$. In this paper, we shall prove the following theorem which was conjectured by the author in .

Theorem 1.1. A uniformly bounded simple SVir\[$`M,s`$\]-module is a module of the intermediate series.

A SVir\[$`M,s`$\]-module $`V`$ is called a generalized highest module if it is generated by a weight vector $`v`$ such that there exists a $`ZZ`$-basis $`B=\{d_1,\mathrm{},d_n\}`$ of $`M`$ such that

$$L_\mu v=G_\lambda v=0,\mu =\underset{i=1}{\overset{n}{}}m_id_iM\backslash \{0\},\lambda =\underset{i=1}{\overset{n}{}}n_id_is+M\backslash \{0\},$$
$`(1.3)`$
with all coefficients $`m_iZZ_+,n_i\frac{\mathrm{\hspace{0.17em}1}}{2}ZZ_+.`$ The vector $`v`$ is called a generalized highest weight vector. Observe that a lowest weight module over the super-Virasoro algebras (i.e., when $`n=1`$) is a generalized highest weight module by this definition. In general, if a module $`V`$ has a weight space decomposition with all the dimensions of weight spaces being finite, then we shall call $`V`$ a weight module. The following theorem generalizes Kac’s conjecture in some sense.

Theorem 1.2. A weight SVir\[$`M,s`$\]-module is either a module of the intermediate series or a generalized highest weight module.

Thus the problem of the classification of simple weight modules is reduced to the problem of the classification of the generalized highest weight modules.

§2. Uniformly bounded modules

The goal of this section is to prove Theorem 1.1. We shall use induction on the rank of $`M`$, the results of , the structure of modules of the intermediate series defined in (1.2), and the defining relations (1.1) to obtain our result.

Thus suppose that $`V`$ is a uniformly bounded SVir\[$`M,s`$\]-module. Obviously $`c`$ must act trivially on such a module . Thus we shall ALWAYS omit $`c`$ in this section. Decompose $`V=V^{(0)}V^{(1)}`$ such that

$$\text{SVir}_iV^{(j)}V^{(i+j)},V^{(i)}=\underset{\mu C\text{ }\text{ }}{}V_\mu ^{(i)},\text{ where }V_\mu ^{(i)}=\{vV^{(i)}|L_0v=\mu v\},$$

for $`i,jZZ/2ZZ`$. For $`aC\text{ }\text{ }`$, define a submodule

$$V(a)=\underset{\mu M}{}V_{\mu +a}^{(0)}\underset{\lambda s+M}{}V_{\lambda +a}^{(1)},$$

for $`aC\text{ }\text{ }`$. Then $`V`$ is a direct sum of different $`V(a)`$. Since we assume that $`V`$ is simple, we have $`V=V(a)`$ for some $`aC\text{ }\text{ }.`$ Since $`V^{(i)},iZZ/2ZZ`$ are SVir$`_0`$-modules, by \[11, Lemma 2.1\], there exist nonnegative integers $`N^{(0)},N^{(1)}`$ such that

$$\mathrm{dim}V_{a+is+\mu }^{(i)}=N^{(i)}\text{ for all }\mu M\text{ with }a+is+\mu 0,i=0,1.$$

By interchanging $`V^{(0)}`$ with $`V^{(1)}`$ if necessary, we always suppose that $`N^{(0)}N^{(1)}`$.

Proof of Theorem 1.1. The result is obvious if $`N^{(1)}=0`$. Suppose that $`N^{(1)}1`$. If $`n=1`$, the result follows from . So assume that $`n2`$. Observe that

$$\mathrm{𝑆𝑉𝑖𝑟}[M,s]\mathrm{𝑆𝑉𝑖𝑟}[M^{},s^{}]\alpha C\text{ }\text{ }\text{ such that }M^{}=\alpha M\text{ and }s^{}\alpha sM^{}.$$

Thus we can always suppose that $`1M`$ and furthermore we can suppose that $`1`$ is a basis element of $`M`$ whenever necessary. So, we can take a $`ZZ`$-basis $`B=\{d_1=1,d_2,\mathrm{},d_{n1},d_n=d\}`$ of $`M`$ such that

$$M=M_1ZZd,M_1=ZZ\underset{i=2}{\overset{n1}{}}ZZd_i,2sM_1.$$
$`(2.1)`$
Let SVir\[$`M_1,s`$\] be the rank $`n1`$ super-Virasoro algebra generated by

$$\{L_\mu ,G_\lambda |\mu M_1,\lambda s+M_1\}.$$

For $`kZZ`$, let

$$V[k]=\underset{\mu M_1}{}V_{a+kd+\mu }^{(0)}\underset{\lambda s+M_1}{}V_{a+kd+\lambda }^{(1)},$$

which is a uniformly bounded SVir\[$`M_1,s`$\]-module. Since $`ZZdM_1=\{0\}`$, there exists at most one $`kZZ`$ such that $`a+kdM_1`$. Fix a $`k_0`$ such that

$$a+kdM_1,kk_0,$$
$`(2.2)`$
i.e., $`a+kd+\nu 0`$ for all $`kk_0,\nu M_1`$. First we take $`k=k_0`$. By inductive assumption, we can suppose that Theorem 1.1 holds for the rank $`n1`$ super-Virasoro algebra SVir\[$`M_1,s`$\]. Thus there exists a simple SVir\[$`M_1,s`$\]-submodule $`V[k,1]`$ of $`V[k]`$ such that $`V[k,1]`$ has the form $`SA_{a+kd,b}`$ in (1.2) (by (2.2), $`SA_{a+kd,b}`$ is simple), thus, there exists a basis

$$\{x_\mu |\mu M_1\}\{y_\lambda |\lambda s+M_1\},$$
$`(2.3)`$
of $`V[k,1]`$, such that

(1.2a) holds for all $`\mu ,\nu M_1,\lambda ,\eta s+M_1`$ with $`a`$ replaced by $`a+kd`$. $`(2.4)`$
Furthermore, among all simple submodules of $`V[k]`$, we choose $`V[k,1]`$ to be one such that the real part $`\mathrm{Re}(b)`$ of $`b`$ is minimum. Take a composition series of the SVir\[$`M_1,s`$\]-module $`V[k+1]`$:

$$0=V[k+1,0]V[k+1,1]\mathrm{}V[k+1,N]=V[k+1],$$
$`(2.5)`$
for some $`N`$. From this, we can observe that $`N=N^{(0)}=N^{(1)}`$. We shall choose the composition series (2.5) such that

$$V[k+1,i]/V[k+1,i1]SA_{a+(k+1)d,b^{}},$$
$`(2.6)`$
for some $`b^{}C\text{ }\text{ },i=1,\mathrm{}N,`$ where $`b^{}`$ may depend on $`i`$. Then, we have

$$L_dV[k,1]^{(0)}L_dV[k,1]L_dV[k]V[k+1],$$
$`(2.7)`$
where $`V[k,1]^{(0)}`$ is the “even” part of $`V[k,1]`$.

We shall divide the proof into some claims.

Claim 1. $`L_dV[k,1]^{(0)}0.`$

Suppose $`L_dV[k,1]^{(0)}=0.`$ Using the fact that

$$L_{\mu +md}=\underset{i=1}{\overset{m2}{}}(\mu +id)^1(\mathrm{ad}L_d)^mL_\mu ,G_{s+\mu +md}=\underset{i=1}{\overset{m2}{}}(s+\mu +\frac{i}{2}d)^1(\mathrm{ad}L_d)^mG_{s+\mu },$$

we obtain

$$L_{\mu +md}V[k,1]^{(0)}=G_{s+\mu +md}V[k,1]^{(0)}=0,\mu M_1,m>0.$$

Let $`_1`$ and $`_2`$ be the Lie super-subalgebras of SVir\[$`M,s`$\] generated by

$$\text{SVir}\text{[}M_1,s\text{]}\{L_d\}\text{ and }\{L_{\mu +md},G_{s+\mu +md}|\mu M_1,mZZ_+\backslash \{0\}\},$$

respectively. Then as space, we have $`\text{SVir}\text{[}M,s\text{]}=_1_2`$. By decomposing the universal enveloping algebra $`U(\text{SVir}\text{[}M,s\text{]})=U(_1)U(_2)`$, we obtain that

$$V=U(_1)U(_2)V[k,1]^{(0)}=U(_1)V[k,1]^{(0)}.$$

From this, we obtain that $`V_{\overline{\mu }+is+md}^{(i)}=0`$ for all $`\mu M_1,m>0,i=0,1`$. Thus $`N=0`$, contradicting the assumption that $`N=N^{(1)}1`$. Hence Claim 1 follows.

Now from (2.5), (2.7), we can take $`K0`$ to be the integer such that

$$L_dV[k,1]V[k+1,K],\text{ but }L_dV[k,1]V[k+1,K+1].$$
$`(2.8)`$
Furthermore, we can choose (2.5) to be a composition series such that $`K`$, defined by (2.8), is minimal possible among all composition series of $`V[k+1]`$. Then, we can take

$$\{x_\mu ^{}V[k+1,K+1]^{(0)}|\mu M_1\},$$
$`(2.9)`$
such that

$$(V[k+1,K+1]/V[k+1,K])^{(0)}=\mathrm{span}\{x_\mu ^{}+V[k+1,K]^{(0)}|\mu M_1\},$$

and such that there exist some $`b^{}C\text{ }\text{ }`$ and some $`a_\nu C\text{ }\text{ }`$ with

$$L_\mu x_\nu ^{}(a+(k+1)d+\nu +\mu b^{})x_{\mu +\nu }^{},L_dx_\nu a_\nu x_\nu ^{}(\mathrm{mod}V[k+1,K]^{(0)}),$$
$`(2.10)`$
for all $`\mu ,\nu M_1.`$

Now \[11, Lemmas 2.3-6\] shows that $`b^{}=b`$ and that by rescaling $`x_\nu ^{}`$ if necessary, we can suppose that $`a_\nu =a+kd+\nu +bd`$, and furthermore $`K=0`$, i.e., $`V[k+1,K]=0`$. Thus (2.10) becomes

$$L_\mu x_\nu ^{}=(a+(k+1)d+\nu +\mu b^{})x_{\mu +\nu }^{},L_dx_\nu =(a+kd+\nu +bd)x_\nu ^{}.$$
$`(2.11)`$
Since $`V[k+1,1]`$ is a SVir\[$`M_1,s`$\]-module of the intermediate series, there exists basis $`\{y_\lambda ^{}|\lambda s+M_1\}`$ of $`V[k+1,1]^{(1)}`$ such that

$$\begin{array}{c}\text{(1.2a) holds for all }\mu ,\nu M_1,\lambda ,\eta s+M_1\text{ with the symbols }x,y\text{ replaced}\\ \text{by symbols }x^{},y^{}\text{ respectively, and with }a\text{ replaced by }a+(k+1)d\text{.}\end{array}$$
$`(2.12)`$
By (2.8), $`L_dV[k,1]^{(1)}V[k+1,1]^{(1)}`$. Thus we can suppose

$$L_dy_\lambda =c_\lambda y_\lambda ^{}\text{ for some }c_\lambda C\text{ }\text{ },\lambda s+M_1.$$
$`(2.13)`$
Then by \[11, Lemma 2.3\], there exists nonzero scalar $`cC\text{ }\text{ }`$ such that

$$c_\lambda =c(a+kd+\lambda +d(b\frac{\mathrm{\hspace{0.17em}1}}{2})),\lambda s+M_1.$$

Claim 2. One can choose a suitable simple SVir\[$`M_1,s`$\]-submodule $`V[k,1]`$ of $`V[k]`$ such that $`L_dL_dV[k,1]V[k,1]`$.

Let $`W[k]`$ be the direct sum of ALL simple SVir\[$`M_1,s`$\]-submodules $`V[k,1]`$ of $`V[k]`$ of the same type: $`V[k,1]SA_{a+kd,b}`$ and let $`W[k+1]`$ be the direct sum of ALL simple SVir\[$`M_1,s`$\]-submodules $`V[k+1,1]`$ of $`V[k+1]`$ of the same type: $`V[k+1,1]SA_{a+(k+1)d,b}`$. Then the above discussion shows that $`L_dW[k]W[k+1]`$, and so we also have $`L_dW[k+1]W[k]`$ by replacing $`d`$ by $`d`$ in the above arguments. By Claim 1, $`W[k],W[k+1]`$ must have the same number, say, $`r`$, of composition factors. Choose a suitable basis $`\{x_\nu ^{(j)},y_{s+\nu }^{(j)}|\nu M_1,j=1,\mathrm{},r\}`$ of $`W[k]`$ such that $`x_0^{(1)}`$ is an eigenvector of $`L_dL_d`$ and

$$\begin{array}{cc}L_\mu X_\nu =(a+kd+\nu +\mu b)X_{\mu +\nu },& L_\mu Y_\eta =(a+kd+\eta +\mu (b\frac{\mathrm{\hspace{0.17em}1}}{2}))Y_{\mu +\eta }\\ G_\lambda X_\nu =Y_{\lambda +\nu },& G_\lambda Y_\eta =(a+kd+\eta +2\lambda (b\frac{\mathrm{\hspace{0.17em}1}}{2}))X_{\lambda +\eta },\end{array}$$
$`(2.14)`$
where

$$X_\nu =\left(\begin{array}{c}x_\nu ^{(1)}\\ \mathrm{}\\ x_\nu ^{(r)}\end{array}\right),Y_\eta =\left(\begin{array}{c}y_\eta ^{(1)}\\ \mathrm{}\\ y_\eta ^{(r)}\end{array}\right),\nu M_1,\eta s+M_1.$$
$`(2.15)`$
Then Claim 1, (2.11) and (2.13) allow us to choose a basis $`\{x_\nu ^{(j)},y_{s+\nu }^{}|\nu M_1,j=1,\mathrm{},r\}`$ of $`W[k+1]`$ such that

$$L_dX_\nu =(a+kd+\nu +bd)X_\nu ^{},L_dY_\eta =c(a+kd+\eta +d(b\frac{\mathrm{\hspace{0.17em}1}}{2}))Y_\eta ^{},$$

where $`X_\nu ^{},Y_\eta ^{}`$ are the similar notations as in (2.15), and such that (2.14) holds for $`k`$ replaced by $`k+1`$ and $`X,Y`$ replaced by $`X^{},Y^{}`$. Similarly, with $`d`$ replaced by $`d`$ in the above arguments, we have

$$L_dX_\nu ^{}=(a+(k+1)d+\nu bd)AX_\nu ,L_dY_\eta ^{}=c^{}(a+(k+1)d+\eta d(b\frac{\mathrm{\hspace{0.17em}1}}{2}))AY_\eta ,$$

where $`A`$ is some constant $`r\times r`$ matrix and $`c^{}C\text{ }\text{ }\backslash \{0\}`$. Thus we have

$$L_dL_dX_\nu =(a+kd+\nu +bd)(a+(k+1)d+\nu bd)AX_\nu .$$
$`(2.16)`$
Since $`x_0^{(1)}`$ is an eigenvector of $`L_dL_d`$, on the first row of $`A`$, by (2.16), there is only one possible nonzero entry in the first position. If we choose

$$V[k,1]=\mathrm{span}_{C\text{ }\text{ }}\{x_\nu ^{(1)},y_{s+\nu }^{(1)}|\nu M_1\},$$

then we see that $`L_dL_dV[k,1]V[k,1]`$. This proves our Claim 2.

Now we can complete the proof of Theorem 1.1 as follows. Starting from $`k=k_0`$ and choosing $`V[k_0,1]`$ as in Claim 2, by induction on $`k>k_0`$, we can choose $`V[k,1]`$ to be the simple SVir\[$`M_1,s`$\]-submodule generated by $`L_dV[k1,1]`$. As in the proof of Claim 1, using $`L_dL_dV[k_0,1]V[k_0,1]`$, by induction on $`m`$, we have

$$L_{\nu +md}V[k,1]V[k+m,1],G_{\lambda +md}V[k,1]V[k+m,1],$$
$`(2.17)`$
for all $`\nu M_1,\lambda s+M_1,m,kZZ`$ such that $`kk_0,k+mk_0`$. Since $`V`$ is a simple SVir\[$`M,s`$\]-module, it must be generated by $`V[k_0,1]`$, thus by (2.17),

$$\mathrm{dim}V_{a+\nu +kd}^{(0)}=\mathrm{dim}V_{a+\lambda +kd}^{(1)}=1,\nu M_1,\lambda s+M_1,kk_0.$$

This shows that $`N=1`$, thus $`\mathrm{dim}V_{a+\nu }^{(0)}=1=\mathrm{dim}V_{a+\lambda }^{(1)}`$ for all $`\nu M,\lambda s+M`$ with $`a+\nu 0a+\lambda `$, from this one sees that we must also have $`\mathrm{dim}V_{a+\nu }^{(0)}1,\mathrm{dim}V_{a+\lambda }^{(1)}1`$ if $`a+\nu =0=a+\lambda `$. Thus $`V`$ must be a module of the intermediate series.

§3. Generalized highest weight modules

The aim of this section is to prove Theorem 1.2. This can be done by three lemmas below. We suppose $`n2`$ as for $`n=1`$, the result follows from .

Lemma 3.1. Let $`V`$ be a simple SVir\[$`M,s`$\]-module and let $`B=\{d_1,\mathrm{},d_n\}`$ be any $`ZZ`$-basis of $`M`$. If $`0vV`$ is a weight vector and $`kZZ_+`$ such that $`L_\mu v=0=G_\lambda v`$ for all

$$\begin{array}{c}\mu M_B^{(k)}=\{\mu M|\mu =\underset{i=1}{\overset{n}{}}m_id_i,\text{ all }km_iZZ_+\},\\ \lambda M_B^{(k)}=\{\lambda s+M|\lambda =\underset{i=1}{\overset{n}{}}n_id_i,\text{ all }km_i\frac{\mathrm{\hspace{0.17em}1}}{2}ZZ_+\},\end{array}$$

then $`V`$ is a generalized highest weight module.

Proof. Take

$$d_i^{}=\underset{j=1}{\overset{i}{}}(k+ij+1)d_j+k\underset{j=i+1}{\overset{n}{}}d_j,i=1,\mathrm{},n.$$

It is straightforward to check that the determinant of coefficients of $`\{d_1,\mathrm{},d_n\}`$ is 1, thus $`B^{}=\{d_1^{},\mathrm{},d_n^{}\}`$ is also a $`ZZ`$-basis of $`M`$. Now for any

$$0\mu ^{}=\underset{i=1}{\overset{n}{}}m_i^{}d_i^{}M_B^{}^{(0)}\text{ (so all }m_i^{}0\text{, at least one }m_i^{}>0\text{),}$$

we have $`\mu ^{}=_{i=1}^nm_id_i`$ with all coefficients

$$m_i=k\underset{j=1}{\overset{i1}{}}m_j^{}+\underset{j=i}{\overset{n}{}}(k+j+1i)m_j^{}k,$$

i.e., $`\mu ^{}M_B^{(k)}`$, thus $`L_\mu ^{}v=0`$. Similarly, for any $`0\lambda ^{}M_B^{}^{(0)}`$, we have $`G_\lambda ^{}v=0`$. Hence by definition (cf. (1.3) ), $`v`$ is a generalized highest weight vector and $`V`$ is a generalized highest weight module.

Lemma 3.2. Fix a $`ZZ`$-basis $`B=\{d_1,\mathrm{},d_n\}`$ of $`M`$. Let

$$\begin{array}{c}A=\{\mu M|\mu =\underset{i=1}{\overset{n}{}}m_id_i,\text{ all }m_i\{1,0,1\}\},\\ A^{}=\{\lambda s+M|\lambda =\underset{i=1}{\overset{n}{}}n_id_i,\text{ all }n_i\{1,\frac{\mathrm{\hspace{0.17em}1}}{2},0,\frac{\mathrm{\hspace{0.17em}1}}{2},1\}\},\end{array}$$

be two finite sets. For any $`\mu =_{i=1}^nm_id_iM`$, let

$$A_\mu =\{\nu M|\nu \mu A\},A_\mu ^{}=\{\lambda s+M|\lambda \mu A^{}\},$$

and let $``$ be the Lie super-subalgebra of SVir\[$`M,s`$\] generated by $`\{L_\nu |\nu A_\mu \}\{G_\lambda |\lambda A_\mu ^{}\}`$. Then there exists a $`ZZ`$-basis $`B^{}=\{d_1^{},\mathrm{},d_n^{}\}`$ of $`M`$ such that

$$\text{SVir}\text{[}M,s\text{]}_B^{}^{(k)}=\{L_\nu ,G_\lambda |\nu M_B^{}^{(k)},\lambda M_B^{}^{(k)}\}\text{ for some }kZZ_+.$$

Proof. If necessary, by replacing $`d_i`$ by $`d_i`$ (this does not change the sets $`A,A^{}`$, neither do $``$), we can suppose $`m_i0,`$ $`i=1,\mathrm{},n`$. First suppose that $`m_10,m_20`$. Take

$$\begin{array}{ccccc}d_1^{}=& m_2\mu +d_1& =& (\mu +d_1)+\underset{i=1}{\overset{m_21}{}}\mu =& (m_1m_2+1)d_1+m_2^2d_2+\underset{i=3}{\overset{n}{}}m_2m_id_i,\end{array}$$

$$\begin{array}{ccccc}d_2^{}=& m_1\mu d_2& =& (\mu d_2)+\underset{i=1}{\overset{m_11}{}}\mu =& m_1^2d_1+(m_1m_21)d_2+\underset{i=3}{\overset{n}{}}m_1m_id_i,\\ d_i^{}=& d_1^{}+d_i& =& (\mu +d_1+d_i)+\underset{i=1}{\overset{m_21}{}}\mu ,& i=3,\mathrm{},n.\end{array}$$

We can easily solve $`d_i,i=1,\mathrm{},n,`$ as an integral linear combination of $`B^{}=\{d_1^{},\mathrm{},d_n^{}\}`$, so $`B^{}`$ is a $`ZZ`$-basis of $`M`$. From the second equality of $`d_i^{}`$, we see $`L_{d_i^{}},i=1,\mathrm{},n`$. For example,

$$[L_\mu ,\mathrm{},[L_\mu ,L_{\mu +d_1}]\mathrm{}](m_21\text{ copies of }L_\mu )=aL_{d_1^{}},\text{ where }a=\underset{i=0}{\overset{m_22}{}}(i\mu +d_1)0,$$

so that the left-hand side is in $``$, thus $`L_{d_1^{}}`$ and so $`\{L_\nu |\nu M_B^{}^{(0)}\}`$. Similarly, $`\{G_\lambda |\lambda M_B^{}^{(0)}\}`$. Next suppose that some $`m_i=0`$, $`1in`$, say, $`m_1=0`$. Take

$$d_1^{}=\mu +d_1,d_i^{}=d_1^{}+d_i=\mu +d_1+d_i,i=2,\mathrm{},n.$$

Then as above $`B^{}=\{d_1^{},\mathrm{},d_n^{}\}`$ is a $`ZZ`$-basis of $`M`$ and $`\text{SVir}\text{[}M\text{]}__B^{}^{(0)}`$.

Lemma 3.3. A simple weight SVir\[$`M,s`$\]-module $`V`$ with dimensions of weight spaces not uniformly bounded is a generalized highest weight module.

Proof. Suppose conversely that $`V`$ is not a generalized highest weight module. For any $`\mu M`$, let $`A,A^{},A_\mu ,A_\mu ^{},`$ and $`B^{}`$ be as in Lemma 3.2. By Lemmas 3.1 and 3.2, for any $`0vV`$, we have $`\text{SVir}\text{[}M,s\text{]}_B^{}^{(k)}v0`$, thus, $`L_\nu v0`$ for some $`\nu A_\mu `$ or $`G_\lambda v0`$ for some $`\lambda A_\mu ^{}`$, i.e.,

$$\underset{\nu A_\mu }{}\mathrm{ker}(L_\nu |_V)\underset{\lambda A_\mu ^{}}{}\mathrm{ker}(G_\lambda |_V)=0.$$

In particular,

$$(\underset{\nu A_\mu }{}L_\nu \underset{\lambda A_\mu ^{}}{}G\lambda )|_{V_{a\mu }}:V_{a\mu }\underset{\nu A}{}V_{a+\nu }\underset{\lambda A^{}}{}V_{a+\lambda },$$

is an injection. Therefore, $`\mathrm{dim}V_{a\mu }N`$, where

$$N=\underset{\nu A}{}\mathrm{dim}V_{a+\nu }+\underset{\lambda A^{}}{}\mathrm{dim}V_{a+\lambda },$$

is a fixed finite integer since both $`A`$ and $`A^{}`$ are finite sets. As $`\mu M`$ is arbitrary, this proves that $`V`$ is uniformly bounded, a contradiction.

Now Theorem 1.2 follows from Lemma 3.3.

References

1 Gelfand, I. M., Fuchs, D. B.: Cohomologies of the Lie algebra of vector fields on the circle, Funct. Anal. Appl., 2 (1968), 92-39 (English translation 114-126).

2 Patera, J., Zassenhaus, H.: The higher rank Virasoro algebras, Comm. Math. Phys., 136 (1991), 1-14.

3 Su, Y.: 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.

4 Su, Y., Zhao, K.: Generalized Virasoro and super-Virasoro algebras and modules of the intermediate series, to appear.

5 Kac, V. G.: Some problems of infinite-dimensional Lie algebras and their representations, in: Lect. Notes in Math., 933, 117-126. Berlin, Heidelberg, New York: Springer, 1982.

6 Chari, V., Pressley, A.: Unitary representations of the Virasoro algebra and a conjecture of Kac, Compositio Math., 67 (1988), 315-342.

7 Martin, C., Piard, A.: Indecomposable modules over the Virasoro Lie algebra and a conjecture of V. Kac, Comm. Math. Phys., 137 (1991), 109-132.

8 Su, Y.: A classification of indecomposable $`sl_2\left(C\text{ }\text{ }\right)`$-modules and a conjecture of Kac on Irreducible modules over the Virasoro algebra, J. Alg., 161 (1993), 33-46.

9 Mathieu, O.: Classification of Harish-Chandra modules over the Virasoro Lie algebra, Invent. Math., 107 (1992), 225-234.

10 Su, Y.: Classification of Harish-Chandra modules over the super-Virasoro algebras, Comm. Alg., 23 (1995), 3653-3675.

11 Su, Y.: Simple modules over the High Rank Virasoro algebras,” Comm. Alg., in press.

12 Su, Y: On indecomposable modules over the Virasoro algebra, Sciences in China A, in press.